summaryrefslogtreecommitdiff
path: root/docs/application/memory.md
diff options
context:
space:
mode:
Diffstat (limited to 'docs/application/memory.md')
-rw-r--r--docs/application/memory.md152
1 files changed, 20 insertions, 132 deletions
diff --git a/docs/application/memory.md b/docs/application/memory.md
index e7f05ba..44a3786 100644
--- a/docs/application/memory.md
+++ b/docs/application/memory.md
@@ -1,151 +1,39 @@
-# Memory Pool
+# Memory
---
-## Object Definitions
-
-```c
-#define KPL_ALLOC_POOL_SIZE 40
-
-#define KPL_ALLOC_WEIGHT 24
-
-#define KPL_ALLOC_HEADER(STRCUT) size_t obj_size : KPL_ALLOC_POOL_SIZE; uint32_t tree_weight : KPL_ALLOC_WEIGHT; STRCUT *prev
-
-typedef struct _kpl_alloc_obj {
- KPL_ALLOC_HEADER(_kpl_alloc_obj);
-} kpl_alloc_obj;
-
-#define KPL_ALLOC_TREE_HEADER(STRCUT) KPL_ALLOC_HEADER(STRUCT); STRUCT *next;
-
-typdef struct _kpl_alloc_tree_obj {
- KPL_ALLOC_TREE_HEADER(struct _kpl_alloc_tree_obj);
-} kpl_alloc_tree_obj;
+An allocator per Object definition with ring buffer pooling based
-typedef struct kpl_alloc {
- _Atomic size_t bytes_allocated;
- kpl_mutex mutex;
- kpl_alloc_obj *pool[KPL_ALLOC_POOL_SIZE]
-} kpl_alloc;
+# Single Allocation
-#define KPL_SLAB_HEADER(STRUCT) STRCUT *prev
+Once created never freed until shutdown
-typdef strcut _kpl_slab_obj {
- KPL_SLAB_HEADER(strcut _kpl_slab_obj);
-} kpl_slab_obj;
+# Pooling Allocations
-#define KPL_SLAB_LIST_HEADER(STRCUT) STRCUT *prev, *next
+## Ring Buffer
-typdef strcut _kpl_slab_list_obj {
- KPL_SLAB_LIST_HEADER(strcut _kpl_slab_list_obj);
-} kpl_slab_list_obj;
+## Fixed Sized Objects
-#define KPL_SLAB_TREE_HEADER(STRUCT) STRUCT *prev, *next; uint32_t tree_weight : KPL_ALLOC_WEIGHT
+## Dynamic Sized Objects
-typdef strcut _kpl_slab_tree_obj {
- KPL_SLAB_TREE_HEADER(struct _kpl_slab_tree_obj);
-} kpl_slab_tree_obj;
+Dynamically sized objects must be aligned to a power of two
-typdef struct _kpl_slab_bucket {
- struct _kpl_slab_bucket *next;
- uint8_t byte_obj_array[];
-} kpl_slab_bucket;
+Requires a ring buffer for each power of two
-typedef struct _kpl_slab {
- uint16_t obj_count, obj_index;
- uint32_t obj_size;
- kpl_slab_obj *pool;
- kpl_slab_bucket *bucket;
- kpl_mutex mutex;
-} kpl_slab;
-```
-
-# Alloc
-
-All allocated objects size must be aligned to the power of two
-
-## Pooling
-
-Each bucket in the `kpl_alloc.pool` represents two to the power of the bucket index
+## Object Definitions
-# Slab
+```c
+#define KPL_DYANMIC_OBJ_MIN_BITS 7
-## Pooling
+#define KPL_DYNAMIC_OBJ_MAX_BITS 27
-Objects for reuse are stored as a list by the `kpl_slab_obj.prev` on `kpl_slab.pool`
+#define KPL_DYNAMIC_OBJ_MIN_SIZE (1 << KPL_DYANMIC_OBJ_MIN_BITS)
-# AVL Tree For Slab And Alloc
+#define KPL_DYNAMIC_OBJ_MAX_SIZE (1 << KPL_DYNAMIC_OBJ_MAX_BITS)
-## AVL Tree Example
+#define KPL_DYNAMIC_OBJ_HEADER() int32_t obj_size;
-```c
-typedef struct _avl {
- int val, count;
- struct _avl *left, *right;
-} avl;
-
-
-int get_count(const avl *node) {
- return node ? node->count : 0;
-}
-
-int get_balance(const avl *node) {
- if (!node)
- return 0;
- return get_count(node->left) - get_count(node->right);
-}
-
-void right_rotate(avl **right) {
- avl *left = (*right)->left, *left_right = left->right;
- left->right = *right;
- (*right)->left = left_right;
- (*right)->count = MAX(get_count((*right)->left), get_count((*right)->right)) + 1;
- left->count = MAX(get_count(left->left), get_count(left->right)) + 1;
- *right = left;
-}
-
-void left_rotate(avl **left) {
- avl *right = (*left)->right, *right_left = right->left;
- right->left = *left;
- (*left)->right = right_left;
- (*left)->count = MAX(get_count((*left)->left), get_count((*left)->right)) + 1;
- right->count = MAX(get_count(right->left), get_count(right->right)) + 1;
- *left = right;
-}
-
-void insert(avl **parent, avl *node) {
- if (!*parent) {
- *parent = node;
- return;
- }
- if (node->val < (*parent)->val)
- insert(&(*parent)->left, node);
- else
- insert(&(*parent)->right, node);
- (*parent)->count = MAX(get_count((*parent)->left), get_count((*parent)->right)) + 1;
- int balance = get_balance(*parent);
- if (balance > 1 && get_balance((*parent)->left) >= 0)
- right_rotate(parent);
- if (balance > 1 && get_balance((*parent)->left) > 0) {
- left_rotate(&(*parent)->left);
- right_rotate(parent);
- }
- if (balance < -1 && get_balance((*parent)->right) <= 0)
- left_rotate(parent);
- if (balance < -1 && get_balance((*parent)->right) > 0) {
- right_rotate(&(*parent)->right);
- left_rotate(parent);
- }
-}
-
-struct TreeNode* sortedListToBST(struct ListNode* head) {
- avl *root = NULL;
- while (head) {
- avl *node = calloc(1, sizeof(avl));
- node->val = head->val;
- node->count = 1;
- head = head->next;
- insert(&root, node);
- }
- return (struct TreeNode*) root;
-}
+typedef struct {
+ KPL_DYNAMIC_OBJ_HEADER();
+} kpl_dynamic_obj;
```