From a9cb228861a6b0fad4d508c05c0614757a7f0a34 Mon Sep 17 00:00:00 2001 From: nasr Date: Mon, 13 Apr 2026 14:58:49 +0200 Subject: refactor(main): refactor directory structure --- source/btree_impl.h | 209 ---------------------------------------------------- 1 file changed, 209 deletions(-) delete mode 100644 source/btree_impl.h (limited to 'source/btree_impl.h') diff --git a/source/btree_impl.h b/source/btree_impl.h deleted file mode 100644 index b7015bd..0000000 --- a/source/btree_impl.h +++ /dev/null @@ -1,209 +0,0 @@ -/** - * >> api notes - * >> by Abdellah El Morabit - * - * - creation of a btree happens when doing an insertion on an - * empty btree where the root is null or nil - * - **/ - -/* single header b-tree implementation by Abdellah El Morabit */ -#ifndef BTREE_H -#define BTREE_H - -// maximum height of the tree the lower the lower the lower amount -// of disk reads which translates into faster? -#if 0 -global_variable read_only s16 btree_ORDER = 4; -#endif -#define BTREE_ORDER 4 - -//- NOTE(nasr): defining a key to improve sorting -// i think saying that a key is a combination of the column + row is a good way of appraoching this -typedef struct key key; -struct key -{ - s32 header_index; //- col number - s32 row_index; -}; - -typedef struct btree_node btree_node; -struct btree_node -{ - // store the key values of the sub nodes? if they are leaves? - key keys[BTREE_ORDER - 1]; - // 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? size not variable - void *payload_per_key[BTREE_ORDER - 1]; - btree_node *parent; - // handle to store children faster than linked list - // because now we can iterate over the nodes instead of having cache misses - // when jumping through linked nodes - btree_node *children[BTREE_ORDER]; - // 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; - - - // NOTE(nasr): do we hold the reference to the arena? or do we pass is it as a reference? - // this could solve memory location issues? -}; - - -typedef struct btree btree; -struct btree -{ - // NOTE(nasr): make sure this always stays in memory - // so that initial fetch never requires a disk read - btree_node *root; -}; - - - -#ifdef BTREE_IMPLEMENTATION -/////////////////////////////////////////////////////////////////////////////// -//- btree.c - - -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); -} - -// TODO(nasr): 1. splitting the tree when getting too big? (horizontally) 2. joining trees? - -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; - - if(destination_index > source_index) return 1; - else if(destination_index < source_index) return -1; - else return 0; -} - -// NOTE(nasr): @return the index of the found element -//- @param: start node could be the root node for all we care. but this enables optimizations in the future if we need them -internal s32 -btree_find_ipos(key k, btree_node *start_node) -{ - s32 index = 0; - // 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; -} - -// 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) - { - return node->payload_per_key[index]; - } - if (node->leaf) - { - return NULL; - } - return btree_search(node->children[index], key); -} - -// TODO(nasr): split node when key_count == btree_ORDER - 1 (node is full) -// -- each node has max btree_ORDER - 1 keys -// -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 - //- after: but what is this. we are expecting a new key.but we are looking for - //- its position in the tree is useless because it's non existent - - s32 i = btree_find_ipos(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 < (BTREE_ORDER - 1)) - { - current_node->key_count += 1; - } - else { - // TODO(nasr): creating a new branch / tree? - // make a seperate function for this - // 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) - { - 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; - } - } - } - // TODO(nasr): internal node case walk down then split on the way back up -} - - -internal void -btree_write(btree *bt) -{ - unused(bt); -#if 0 - temp_arena *temp_arena = temp_arena_begin(arena); - btree_node *root = bt->root; - - for(btree_node *bt = PushStruct(arena); root->next; next = root;) - { - - } - - temp_arena_end(temp); -#endif -} - -// - load the entire db into memory. -#if 0 -internal void -btree_load(mem_arena *arena) -{ - - -} -#endif - -#endif /* BTREE_IMPLEMENTATION */ -#endif /* BTREE_H */ -- cgit v1.3