1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
|
/**
* >> 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 */
|
