# Memory Pool

---

## Object Definitions

```c
#define KPL_ALLOC_POOL_SIZE 40

#define KPL_TREE_WEIGHT 24

#define KPL_ALLOC_HEADER(STRCUT) size_t obj_size : KPL_ALLOC_POOL_SIZE; uint32_t tree_weight : KPL_TREE_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;

typedef struct kpl_alloc {
    _Atomic size_t bytes_allocated;
    kpl_mutex mutex;
    kpl_alloc_obj *pool[KPL_ALLOC_POOL_SIZE]
} kpl_alloc;

#define KPL_SLAB_HEADER(STRUCT) STRCUT *prev

typdef strcut _kpl_slab_obj {
    KPL_SLAB_HEADER(strcut _kpl_slab_obj);
} kpl_slab_obj;

#define KPL_SLAB_LIST_HEADER(STRCUT) STRCUT *prev, *next

typdef strcut _kpl_slab_list_obj {
    KPL_SLAB_LIST_HEADER(strcut _kpl_slab_list_obj);
} kpl_slab_list_obj;

#define KPL_SLAB_TREE_HEADER(STRUCT) STRUCT *prev, *next; uin32_t tree_weight : KPL_TREE_WEIGHT

typdef strcut _kpl_slab_tree_obj {
    KPL_SLAB_TREE_HEADER(struct _kpl_slab_tree_obj);
} kpl_slab_tree_obj;

typedef struct _kpl_slab {
    KPL_ALLOC_HEADER(struct _kpl_slab);
    uint32_t obj_size, byte_index;
    kpl_slab_obj *pool;
    kpl_mutex mutex;
    uint8_t byte_array[MAX_SIZE];
} 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

# Slab

Allocated by `kpl_alloc`

## Pooling

Objects for reuse are stored as a list by the `kpl_slab_obj.prev` on `kpl_slab.pool`

# AVL Tree For Slab And Alloc

## AVL Tree Example

```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;
}
```