1 files changed, 36 insertions, 31 deletions

diff --git a/source/b_tree.h b/source/b_tree.h
index 43a33a6..0c4b1e1 100644
--- a/source/b_tree.h
+++ b/source/b_tree.h
@@ -2,39 +2,31 @@
 #ifndef B_TREE_H
 #define B_TREE_H
 
-// maximum height  of the tree the lower the lower the lower amount
+// maximum height of the tree the lower the lower the lower amount
 // of disk reads which translates into faster?
 #define B_TREE_ORDER 4
 
 typedef struct b_tree_node b_tree_node;
 struct b_tree_node
 {
-
     // store the values
     string8 keys[B_TREE_ORDER - 1];
-
-    // TODO(nasr): replace with someting more  generic?
+    // TODO(nasr): replace with something more generic?
     // NOTE(nasr): cons of void * -> no type safety
     // is there a way to still have some sort of that?
     void *payload_per_key[B_TREE_ORDER - 1];
-
     b_tree_node *parent;
     // handle to store children faster than linked list
-    // because now we can iteratate over the nodes instead of having cache misses
+    // because now we can iterate over the nodes instead of having cache misses
     // when jumping through linked nodes
     b_tree_node *children[B_TREE_ORDER];
-
-    // this shouldnt change things but could be a performance improvement on a bigger scale?? 
+    // this shouldn't change things but could be a performance improvement on a bigger scale??
     s32 *max_children;
-
     // NOTE(nasr): reference count ::: check how many leaves are using this node
     // also not needed for now because we don't free individual node because of arena allocator
     // s32 *refc;
-
     s32 key_count;
-
     b32 leaf;
-
 };
 
 typedef struct b_tree b_tree;
@@ -45,7 +37,6 @@ struct b_tree
     b_tree_node *root;
 };
 
-
 #ifdef B_TREE_IMPLEMENTATION
 ///////////////////////////////////////////////////////////////////////////////
 //- b_tree.c
@@ -60,11 +51,12 @@ btree_node_alloc(mem_arena *arena)
     return node;
 }
 
-// NOTE(nasr): @return the index of of the found element
+// NOTE(nasr): @return the index of the found element
 internal s32
-btree_node_find_pos(mem_arena *arena, string8 value, b_tree_node *node)
+btree_node_find_pos(string8 value, b_tree_node *node)
 {
-    for (s32 index = 0;  index < node->key_count && string8_cmp(node->keys[i], value) < 0; ++index);
+    s32 i = 0;
+    for (; i < node->key_count && string8_cmp(node->keys[i], value) < 0; ++i);
     return i;
 }
 
@@ -76,42 +68,55 @@ b_tree_create(mem_arena *arena, b_tree *tree)
     tree->root->key_count = 0;
 }
 
-// NOTE(nasr): nodes that get  passed as parameters should've already been loaded into memory
-internal void
+// NOTE(nasr): nodes that get passed as parameters should've already been loaded into memory
+internal void *
 b_tree_search(b_tree_node *node, string8 key)
 {
-    s32 found_index = btree_node_find_pos(node, key);
-    s32 i = 0;
+    s32 i = btree_node_find_pos(key, node);
 
-    if (found_index < node->key_count && string_compare(node->keys[index], key) == 0)
+    if (i < node->key_count && string8_cmp(node->keys[i], key) == 0)
     {
-        return node->rows[i];
+        return node->payload_per_key[i];
     }
     if (node->leaf)
     {
         return NULL;
-
     }
-
     return b_tree_search(node->children[i], key);
-
-    return NULL;
 }
 
+// TODO(nasr): split node when key_count == B_TREE_ORDER - 1 (node is full)
 internal void
-b_tree_insert(b_tree_node *current_node)
+b_tree_insert(mem_arena *arena, b_tree *tree, string8 key, void *payload)
 {
-    if(current_node->leaf)
+    b_tree_node *current_node = tree->root;
+
+    if (current_node->leaf)
     {
+        // find the insertion position and shift keys right to make room
+        s32 i = btree_node_find_pos(key, current_node);
+        for (s32 j = current_node->key_count; j > i; --j)
+        {
+            current_node->keys[j]            = current_node->keys[j - 1];
+            current_node->payload_per_key[j] = current_node->payload_per_key[j - 1];
+        }
+        current_node->keys[i]            = key;
+        current_node->payload_per_key[i] = payload;
 
+        if(current_node->key_count < (B_TREE_ORDER - 1))
+        {
+            current_node->key_count         += 1;
+        }
+        else {
+            // TODO(nasr): creating a new branch / tree?
+        }
     }
-
+    // TODO(nasr): internal node case walk down then split on the way back up
 }
 
 internal void
-b_tree_write()
+b_tree_write(b_tree *bt)
 {
-
     // TODO(nasr): write the b_tree to disk
 }