feature(btree): calculating insertion position properly now

- fixed bug true was false when check if something was a nil btree node
(kind of dumb because we dont even nee that function that was to help us
out in the future but okay)

1 files changed, 19 insertions, 25 deletions

diff --git a/source/btree_impl.h b/source/btree_impl.h
index 7dda6c9..b7015bd 100644
--- a/source/btree_impl.h
+++ b/source/btree_impl.h
@@ -74,7 +74,7 @@ internal b32
 is_nil_btree_node(btree_node *node)
 {
     // NOTE(nasr): looks like a useless function but could be usefull when we implement a nil_btree_node 
-    return (node != NULL);
+    return (node == NULL);
 }
 
 // TODO(nasr): 1. splitting the tree when getting too big? (horizontally) 2. joining trees?
@@ -82,8 +82,8 @@ is_nil_btree_node(btree_node *node)
 internal b8 
 key_compare(key destination_key, key source_key)
 {
-    s32 source_index = source_key.header_index +  source_key.row_index;
-    s32 destination_index = destination_key.header_index +  destination_key.row_index;
+    s32 source_index      = source_key.header_index      + source_key.row_index;
+    s32 destination_index = destination_key.header_index + destination_key.row_index;
 
     if(destination_index > source_index) return 1;
     else if(destination_index < source_index) return -1;
@@ -96,20 +96,18 @@ internal s32
 btree_find_ipos(key k, btree_node *start_node)
 {
     s32 index = 0;
-    for (btree_node *current_node = start_node;
-         index < current_node->key_count && key_compare(k, current_node->keys[0]) < 0;
-         ++index);
+    // scan right while the node's key at [index] is strictly less than k
+    while (index < start_node->key_count && key_compare(start_node->keys[index], k) < 0)
+    {
+        ++index;
+    }
     return index;
-
-    return 0;
-
 }
 
 // NOTE(nasr): nodes that get passed as parameters should've already been loaded into memory
 internal void *
 btree_search(btree_node *node, key key)
 {
-
     s32 index = btree_find_ipos(key, node);
 
     if (index < node->key_count && key_compare(node->keys[index], key) == 0)
@@ -121,8 +119,6 @@ btree_search(btree_node *node, key key)
         return NULL;
     }
     return btree_search(node->children[index], key);
-
-    return NULL;
 }
 
 // TODO(nasr): split node when key_count == btree_ORDER - 1 (node is full)
@@ -131,18 +127,15 @@ btree_search(btree_node *node, key key)
 internal void
 btree_insert(mem_arena *arena, btree *tree, key key, void *payload)
 {
-
     if(is_nil_btree_node(tree->root)) 
     {
         tree->root = PushStructZero(arena, btree_node);
         tree->root->leaf = 1;
         tree->root->key_count = 0;
-
     }
 
     btree_node *current_node = tree->root;
 
-
     if (current_node->leaf)
     {
         // find the insertion position and shift keys right to make room
@@ -162,20 +155,23 @@ btree_insert(mem_arena *arena, btree *tree, key key, void *payload)
 
         if(current_node->key_count < (BTREE_ORDER - 1))
         {
-            current_node->key_count         += 1;
+            current_node->key_count += 1;
         }
         else {
             // TODO(nasr): creating a new branch / tree?
             // make a seperate function for this
-            s32 split_pos = current_node->parent->key_count / 2 - 1;
-            s32 updated_keycount_p = 0;
-            for(s32 index = 0; index <= split_pos; ++index)
+            // NOTE(nasr): only split through the parent when one actually exists;
+            // root splits need to be handled separately (promote mid key, create two children)
+            if(current_node->parent != NULL)
             {
-                 ++updated_keycount_p;
+                s32 split_pos = current_node->parent->key_count / 2 - 1;
+                s32 updated_keycount_p = 0;
+                for(s32 index = 0; index <= split_pos; ++index)
+                {
+                    ++updated_keycount_p;
+                }
+                current_node->parent->key_count = updated_keycount_p;
             }
-
-            current_node->parent->key_count = updated_keycount_p;
-
         }
     }
     // TODO(nasr): internal node case walk down then split on the way back up
@@ -185,7 +181,6 @@ btree_insert(mem_arena *arena, btree *tree, key key, void *payload)
 internal void
 btree_write(btree *bt)
 {
-
     unused(bt);
 #if 0
     temp_arena *temp_arena = temp_arena_begin(arena);
@@ -198,7 +193,6 @@ btree_write(btree *bt)
 
     temp_arena_end(temp);
 #endif
-
 }
 
 // - load the entire db into memory.