From e51d57e2da70ea2688a72602aeb5f7c4040e72b7 Mon Sep 17 00:00:00 2001 From: nasr Date: Fri, 13 Mar 2026 17:08:49 +0000 Subject: feature(main): binary tree insertions --- source/b_tree.h | 69 ++++++++++++++++++++++++++---------------------- source/base/base_error.h | 0 source/base/base_mem.c | 0 3 files changed, 37 insertions(+), 32 deletions(-) create mode 100644 source/base/base_error.h delete mode 100644 source/base/base_mem.c 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 } diff --git a/source/base/base_error.h b/source/base/base_error.h new file mode 100644 index 0000000..e69de29 diff --git a/source/base/base_mem.c b/source/base/base_mem.c deleted file mode 100644 index e69de29..0000000 -- cgit v1.3