add btrie_map() for allocating free slot, remove isrm

[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 72758fb4517d822bfcf8b5bc1dced14d2ed80bfe..8cba6046a032c1d6f270cd90d9a0aeff425dc342 100644 (file)
--- a/lunaix-os/kernel/ds/btrie.c
+++ b/lunaix-os/kernel/ds/btrie.c
@@ -13,75 +13,216 @@
 #include <lunaix/mm/valloc.h>
 #include <lunaix/spike.h>
 
 #include <lunaix/mm/valloc.h>
 #include <lunaix/spike.h>
 

-#define BTRIE_INSERT 1
+enum btrie_traverse_mode {
+    BTRIE_FIND,
+    BTRIE_FIND_PARENT,
+    BTRIE_INSERT
+};
+struct btrie_locator
+{
+    enum btrie_traverse_mode mode;
+    int shifts;
+    unsigned long index;
+};
+
+static inline void
+__btrie_locator(struct btrie_locator* loc, 
+                unsigned long index, enum btrie_traverse_mode mode)
+{
+    loc->mode = mode;
+    loc->index = index;
+}
+
+static inline void
+__btrie_addchild(struct btrie* root,
+                 struct btrie_node* parent, struct btrie_node* child)
+{
+    if (unlikely(!parent->children)) {
+        parent->children = vcalloc(sizeof(parent), 1 << root->order);
+    }
+
+    parent->children_cnt++;
+    parent->children[child->index] = child;
+}
+
+static inline struct btrie_node*
+__btrie_get_child(struct btrie_node* node, int index)
+{
+    if (unlikely(!node->children)) {
+        return NULL;
+    }
+
+    return node->children[index];
+}
+
+static inline void
+__btrie_free_node(struct btrie_node* node)
+{
+    vfree_safe(node->children);
+    vfree(node);
+}

 
 

-struct btrie_node*
-__btrie_traversal(struct btrie* root, unsigned long index, int options)
+static inline bool
+__full_node(struct btrie* root, struct btrie_node* node)

 {
 {

-    unsigned long lz;
+    return node->children_cnt == 1 << root->order;
+}
+
+static inline struct btrie_node*
+__btrie_create(struct btrie* root, struct btrie_node* parent, int index)
+{
+    struct btrie_node* node;
+
+    node = vzalloc(sizeof(struct btrie_node));
+    node->index = index;
+    node->parent = parent;
+    
+    if (likely(parent)) {
+        llist_append(&root->btrie_root->nodes, &node->nodes);
+        __btrie_addchild(root, parent, node);
+    }
+
+    return node;
+}
+
+static struct btrie_node*
+__btrie_traversal(struct btrie* root, struct btrie_locator* locator)
+{
+    unsigned long lz, index;

     unsigned long bitmask;
     unsigned long i = 0;
     unsigned long bitmask;
     unsigned long i = 0;

-    struct btrie_node* tree = root->btrie_root;
+    struct btrie_node *subtree, *tree = root->btrie_root;

 
 

-    lz = index ? ICEIL(msbitl - clzl(index), root->order) : 0;
+    index = locator->index;
+    lz = index ? (msbitl - clzl(index)) / root->order : 0;

     lz = lz * root->order;
     bitmask = ((1 << root->order) - 1) << lz;
 
     // Time complexity: O(log_2(log_2(N))) where N is the index to lookup
     while (bitmask && tree) {
         i = (index & bitmask) >> lz;
     lz = lz * root->order;
     bitmask = ((1 << root->order) - 1) << lz;
 
     // Time complexity: O(log_2(log_2(N))) where N is the index to lookup
     while (bitmask && tree) {
         i = (index & bitmask) >> lz;

-        struct btrie_node *subtree = 0, *pos, *n;
+        subtree = __btrie_get_child(tree, i);

 
 

-        llist_for_each(pos, n, &tree->children, siblings)
+        if (!subtree && (locator->mode != BTRIE_FIND)) 

         {
         {

-            if (pos->index == i) {
-                subtree = pos;
-                break;
-            }
+            tree = __btrie_create(root, tree, i);

         }
         }

-
-        if (!subtree && (options & BTRIE_INSERT)) {
-            struct btrie_node* new_tree = vzalloc(sizeof(struct btrie_node));
-            new_tree->index = i;
-            new_tree->parent = tree;
-            llist_init_head(&new_tree->children);
-
-            llist_append(&tree->children, &new_tree->siblings);
-            llist_append(&root->btrie_root->nodes, &new_tree->nodes);
-            tree = new_tree;
-        } else {
+        else {

             tree = subtree;
         }
             tree = subtree;
         }

+
+        if (lz == root->order && locator->mode == BTRIE_FIND_PARENT)
+        {
+            break;
+        }
+

         bitmask = bitmask >> root->order;
         lz -= root->order;
     }
 
         bitmask = bitmask >> root->order;
         lz -= root->order;
     }
 

+    locator->shifts = lz;

     return tree;
 }
 
     return tree;
 }
 

+static unsigned long
+__btrie_alloc_slot(struct btrie* root, struct btrie_node **slot, 
+                   unsigned long start, unsigned long end)
+{
+    unsigned int index, od;
+    unsigned long result, mask, result_next;
+    struct btrie_node *tree, *subtree;
+    struct btrie_locator locator;
+    
+    result = 0;
+    od   = root->order;
+    mask = (1 << od) - 1;
+    tree = root->btrie_root;
+    
+    if (start) {
+        __btrie_locator(&locator, start, BTRIE_FIND_PARENT);
+        tree = __btrie_traversal(root, &locator);
+        result = start;
+    }
+    
+    while (tree && result < end) 
+    {
+        index = result & mask;
+        result_next = result << od;
+        
+        subtree = __btrie_get_child(tree, index);
+            
+        if (subtree) {
+            if (result >= start && !subtree->data) {
+                tree = subtree;
+                goto done;
+            }
+        }
+        else {
+            subtree = __btrie_create(root, tree, index);
+
+            if (result >= start)
+                goto done;
+
+            goto descend;
+        }
+
+        if (!__full_node(root, tree) && index != mask) {
+            result++;
+            continue;
+        }
+
+descend:
+        if (result_next >= end) {
+            tree = tree->parent;
+            result >>= od;
+            result++;
+            continue;
+        }
+
+        tree   = subtree;
+        result = result_next;
+    }
+
+    *slot = NULL;
+    return -1;
+
+done:
+    *slot = subtree;
+    return result;
+}
+

 void
 btrie_init(struct btrie* btrie, unsigned int order)
 {
 void
 btrie_init(struct btrie* btrie, unsigned int order)
 {

-    btrie->btrie_root = vzalloc(sizeof(struct btrie_node));
-    llist_init_head(&btrie->btrie_root->nodes);
-    llist_init_head(&btrie->btrie_root->children);
+    btrie->btrie_root = __btrie_create(btrie, NULL, 0);

     btrie->order = order;
     btrie->order = order;

+
+    llist_init_head(&btrie->btrie_root->nodes);

 }
 
 void*
 btrie_get(struct btrie* root, unsigned long index)
 {
 }
 
 void*
 btrie_get(struct btrie* root, unsigned long index)
 {

-    struct btrie_node* node = __btrie_traversal(root, index, 0);
+    struct btrie_node* node;
+    struct btrie_locator locator;
+    
+    __btrie_locator(&locator, index, BTRIE_FIND);
+    node = __btrie_traversal(root, &locator);

     if (!node) {
         return NULL;
     }
     if (!node) {
         return NULL;
     }

+

     return node->data;
 }
 
 void
 btrie_set(struct btrie* root, unsigned long index, void* data)
 {
     return node->data;
 }
 
 void
 btrie_set(struct btrie* root, unsigned long index, void* data)
 {

-    struct btrie_node* node = __btrie_traversal(root, index, BTRIE_INSERT);
+    struct btrie_node* node;
+    struct btrie_locator locator;
+    
+    __btrie_locator(&locator, index, BTRIE_INSERT);
+    node = __btrie_traversal(root, &locator);

     node->data = data;
 }
 
     node->data = data;
 }
 


@@ -90,29 +231,55 @@ __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 (llist_empty(&parent->children) && !parent->data) {
-            __btrie_rm_recursive(parent);
-        }
+    if (!parent) {
+        return;
+    }
+
+    parent->children[node->index] = NULL;
+    parent->children_cnt--;
+    __btrie_free_node(node);
+
+    if (!parent->children_cnt && !parent->data) {
+        __btrie_rm_recursive(parent);

     }
 }
 
     }
 }
 

+unsigned long
+btrie_map(struct btrie* root, 
+          unsigned long start, unsigned long end, void* data)
+{
+    struct btrie_node* node = NULL;
+    unsigned long alloced;
+
+    alloced = __btrie_alloc_slot(root, &node, start, end);
+    
+    if (!node)
+        return -1;
+
+    node->data = data;
+    return alloced;
+}
+

 void*
 btrie_remove(struct btrie* root, unsigned long index)
 {
 void*
 btrie_remove(struct btrie* root, unsigned long index)
 {

-    struct btrie_node* node = __btrie_traversal(root, index, 0);
+    void* data;
+    struct btrie_node* node;
+    struct btrie_locator locator;
+    
+    __btrie_locator(&locator, index, BTRIE_FIND);
+    node = __btrie_traversal(root, &locator);

     if (!node) {
         return 0;
     }
     if (!node) {
         return 0;
     }

-    void* data = node->data;
-    if (!llist_empty(&node->children)) {
+    
+    data = node->data;
+    if (!node->children_cnt) {

         node->data = NULL;
     } else {
         __btrie_rm_recursive(node);
     }
         node->data = NULL;
     } else {
         __btrie_rm_recursive(node);
     }

+

     return data;
 }
 
     return data;
 }
 


@@ -122,8 +289,8 @@ btrie_release(struct btrie* tree)
     struct btrie_node *pos, *n;
     llist_for_each(pos, n, &tree->btrie_root->nodes, nodes)
     {
     struct btrie_node *pos, *n;
     llist_for_each(pos, n, &tree->btrie_root->nodes, nodes)
     {

-        vfree(pos);
+        __btrie_free_node(pos);

     }
 
     }
 

-    vfree(tree->btrie_root);
+    __btrie_free_node(tree->btrie_root);

 }
\ No newline at end of file
 }
\ No newline at end of file