Second Extended Filesystem (ext2) and other improvements (#33)

[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 8a4380e4c19da2320979f8462a71c5ee367c9b1b..72758fb4517d822bfcf8b5bc1dced14d2ed80bfe 100644 (file)
--- a/lunaix-os/kernel/ds/btrie.c
+++ b/lunaix-os/kernel/ds/btrie.c
@@ -16,14 +16,17 @@
 #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, unsigned long index, int options)

 {
 {

-    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;
+    unsigned long lz;
+    unsigned long bitmask;
+    unsigned long i = 0;

     struct btrie_node* tree = root->btrie_root;
 
     struct btrie_node* tree = root->btrie_root;
 

+    lz = index ? ICEIL(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;
     // Time complexity: O(log_2(log_2(N))) where N is the index to lookup
     while (bitmask && tree) {
         i = (index & bitmask) >> lz;


@@ -49,24 +52,24 @@ __btrie_traversal(struct btrie* root, uint32_t index, int options)
         } else {
             tree = subtree;
         }
         } else {
             tree = subtree;
         }

-        bitmask = bitmask >> BTRIE_BITS;
-        lz -= BTRIE_BITS;
+        bitmask = bitmask >> root->order;
+        lz -= root->order;

     }
 
     return tree;
 }
 
 void
     }
 
     return tree;
 }
 
 void

-btrie_init(struct btrie* btrie, uint32_t trunc_bits)
+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 = vzalloc(sizeof(struct btrie_node));
     llist_init_head(&btrie->btrie_root->nodes);
     llist_init_head(&btrie->btrie_root->children);

-    btrie->truncated = trunc_bits;
+    btrie->order = order;

 }
 
 void*
 }
 
 void*

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

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


@@ -76,7 +79,7 @@ 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, unsigned long index, void* data)

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


@@ -98,7 +101,7 @@ __btrie_rm_recursive(struct btrie_node* node)
 }
 
 void*
 }
 
 void*

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

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