use trees without parent nodes

1 files changed, 84 insertions, 7 deletions

diff --git a/docs/application/memory.md b/docs/application/memory.md
index 61a59f9..a7eab83 100644
--- a/docs/application/memory.md
+++ b/docs/application/memory.md
@@ -5,20 +5,22 @@
 ## Object Definitions
 
 ```c
-#define KPL_ALLOC_HEADER(STRCUT) size_t obj_size : 56; int8_t tree_weight; STRCUT *prev
+#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_TREE_HEADER(STRUCT); STRUCT *next, *parent
+#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;
 
-#define KPL_ALLOC_POOL_SIZE 56
-
 typedef struct kpl_alloc {
     _Atomic size_t bytes_allocated;
     kpl_mutex mutex;
@@ -37,7 +39,7 @@ 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, *parent; int8_t tree_weight
+#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);
@@ -60,8 +62,6 @@ All allocated objects size must be aligned to the power of two
 
 Each bucket in the `kpl_alloc.pool` represents two to the power of the bucket index
 
-# AVL Tree For Slab And Alloc
-
 # Slab
 
 Allocated by `kpl_alloc`
@@ -69,3 +69,80 @@ 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;
+}
+```