feat: nearly complete POSIX.1-2008 compliant terminal interface implementation

[lunaix-os.git] / lunaix-os / kernel / ds / btrie.c

diff --git a/lunaix-os/kernel/ds/btrie.c b/lunaix-os/kernel/ds/btrie.c
index fd173b9455c701b99ff60b12ed9ae7a3acb7b01c..5ce7687da18247862821ce0166b7d9521e3f5215 100644 (file)
--- a/lunaix-os/kernel/ds/btrie.c
+++ b/lunaix-os/kernel/ds/btrie.c
@@ -16,12 +16,12 @@
 #define BTRIE_INSERT 1
 
 struct btrie_node*
 #define BTRIE_INSERT 1
 
 struct btrie_node*

-__btrie_traversal(struct btrie* root, uint32_t index, int options)
+__btrie_traversal(struct btrie* root, u32_t index, int options)

 {
     index = index >> root->truncated;
 {
     index = index >> root->truncated;

-    uint32_t lz = index ? ROUNDDOWN(31 - __builtin_clz(index), BTRIE_BITS) : 0;
-    uint32_t bitmask = ((1 << BTRIE_BITS) - 1) << lz;
-    uint32_t i = 0;
+    u32_t lz = index ? ROUNDDOWN(31 - __builtin_clz(index), BTRIE_BITS) : 0;
+    u32_t bitmask = ((1 << BTRIE_BITS) - 1) << lz;
+    u32_t i = 0;

     struct btrie_node* tree = root->btrie_root;
 
     // Time complexity: O(log_2(log_2(N))) where N is the index to lookup
     struct btrie_node* tree = root->btrie_root;
 
     // Time complexity: O(log_2(log_2(N))) where N is the index to lookup


@@ -57,7 +57,7 @@ __btrie_traversal(struct btrie* root, uint32_t index, int options)
 }
 
 void
 }
 
 void

-btrie_init(struct btrie* btrie, uint32_t trunc_bits)
+btrie_init(struct btrie* btrie, u32_t trunc_bits)

 {
     btrie->btrie_root = vzalloc(sizeof(struct btrie_node));
     llist_init_head(&btrie->btrie_root->nodes);
 {
     btrie->btrie_root = vzalloc(sizeof(struct btrie_node));
     llist_init_head(&btrie->btrie_root->nodes);


@@ -66,7 +66,7 @@ btrie_init(struct btrie* btrie, uint32_t trunc_bits)
 }
 
 void*
 }
 
 void*

-btrie_get(struct btrie* root, uint32_t index)
+btrie_get(struct btrie* root, u32_t index)

 {
     struct btrie_node* node = __btrie_traversal(root, index, 0);
     if (!node) {
 {
     struct btrie_node* node = __btrie_traversal(root, index, 0);
     if (!node) {


@@ -76,35 +76,40 @@ btrie_get(struct btrie* root, uint32_t index)
 }
 
 void
 }
 
 void

-btrie_set(struct btrie* root, uint32_t index, void* data)
+btrie_set(struct btrie* root, u32_t index, void* data)

 {
     struct btrie_node* node = __btrie_traversal(root, index, BTRIE_INSERT);
     node->data = data;
 }
 
 void
 {
     struct btrie_node* node = __btrie_traversal(root, index, BTRIE_INSERT);
     node->data = data;
 }
 
 void

-__btrie_remove(struct btrie_node* node)
+__btrie_rm_recursive(struct btrie_node* node)

 {
     struct btrie_node* parent = node->parent;
 {
     struct btrie_node* parent = node->parent;

+

     if (parent) {
         llist_delete(&node->siblings);
         llist_delete(&node->nodes);
         vfree(node);
     if (parent) {
         llist_delete(&node->siblings);
         llist_delete(&node->nodes);
         vfree(node);

-        if (llist_empty(&parent->children)) {
-            __btrie_remove(parent);
+        if (llist_empty(&parent->children) && !parent->data) {
+            __btrie_rm_recursive(parent);

         }
     }
 }
 
 void*
         }
     }
 }
 
 void*

-btrie_remove(struct btrie* root, uint32_t index)
+btrie_remove(struct btrie* root, u32_t index)

 {
     struct btrie_node* node = __btrie_traversal(root, index, 0);
     if (!node) {
         return 0;
     }
     void* data = node->data;
 {
     struct btrie_node* node = __btrie_traversal(root, index, 0);
     if (!node) {
         return 0;
     }
     void* data = node->data;

-    __btrie_remove(node);
+    if (!llist_empty(&node->children)) {
+        node->data = NULL;
+    } else {
+        __btrie_rm_recursive(node);
+    }

     return data;
 }
 
     return data;
 }