diff options
Diffstat (limited to 'docs/application/memory.md')
| -rw-r--r-- | docs/application/memory.md | 152 |
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; ``` |
