Mercurial > data_structures

view src/btree_mem.c @ 18:ef2c6a831fb9

find changesets by author, revision, files, or words in the commit message
Btree taking shape. Insert seems to be working
author Eris Caffee <discordia@eldalin.com>
date Wed, 17 Oct 2012 02:17:47 -0500
parents 36561a63330a
children 0bf94d0ed0b0
line source
1 /*
2 This is a fairly straightforward implementation of a B-Tree in memory modeled after
3 Cormen, et al., Introduction to Algorithms, Chapter 18
4 */
5
6 #include <stdio.h>
7
8 #include <stdlib.h>
9 #include <stdbool.h>
10
11 #include "btree_mem.h"
12
13 struct btree_mem_node
14 {
15 int nkeys;
16 void ** key;
17 void ** data;
18 struct btree_mem_node ** child;
19 bool leaf;
20 };
21
22 struct btree_mem_node * btree_mem_node_new (struct btree_mem * bt);
23 void btree_mem_node_delete (struct btree_mem_node * node);
24
25 struct btree_mem_node * btree_mem_node_find (struct btree_mem * bt, struct btree_mem_node * node, void * key, int * i);
26
27 void * btree_mem_node_insert (struct btree_mem * bt, struct btree_mem_node * node, void * key, void * data);
28 void * btree_mem_node_insert_nonfull (struct btree_mem * bt, struct btree_mem_node * node, void * key, void * data);
29
30 struct btree_mem_node * btree_mem_split_child (struct btree_mem * bt, struct btree_mem_node * x, int i);
31
32 void btree_mem_node_walk_inorder (struct btree_mem_node * node, void (*f)(int, void *, void *), int depth);
33
34 ////////////////////////////////////////////////////////////////////////////////
35 struct btree_mem *
36 btree_mem_new(int min_degree, int (*cmp)(void *, void *))
37 {
38 struct btree_mem * bt = malloc(sizeof(struct btree_mem));
39 if (NULL == bt)
40 return NULL;
41
42 bt->mindeg = min_degree;
43 bt->cmp = cmp;
44
45 bt->root = btree_mem_node_new(bt);
46 if (NULL == bt->root)
47 {
48 free(bt);
49 return NULL;
50 }
51
52 bt->root->leaf = true;
53 return bt;
54 }
55
56 ////////////////////////////////////////////////////////////////////////////////
57 // IMPORTANT NOTE: All keys and data must be removed first or else memory
58 // will leak.
59 void
60 btree_mem_delete(struct btree_mem * bt)
61 {
62 // TODO: walk down the tree and delete all nodes.
63 free(bt);
64 }
65
66 ////////////////////////////////////////////////////////////////////////////////
67 struct btree_mem_node *
68 btree_mem_node_new(struct btree_mem * bt)
69 {
70 struct btree_mem_node * node = malloc(sizeof(struct btree_mem_node));
71 if (NULL == node)
72 return NULL;
73
74 int maxchild = 2*bt->mindeg;
75
76 node->key = malloc( (maxchild - 1) * sizeof(void *));
77 if (NULL == node->key)
78 {
79 free(node);
80 return NULL;
81 }
82
83 node->data = malloc( (maxchild - 1) * sizeof(void *));
84 if (NULL == node->data)
85 {
86 free(node->key);
87 free(node);
88 return NULL;
89 }
90
91 node->child = malloc( maxchild * sizeof(struct btree_mem_node *));
92 if (NULL == node->data)
93 {
94 free(node->data);
95 free(node->key);
96 free(node);
97 return NULL;
98 }
99
100 for (int i = 0; i < maxchild - 1; i++)
101 {
102 node->key[i] = NULL;
103 node->data[i] = NULL;
104 node->child[i] = NULL;
105 }
106 node->child[maxchild-1] = NULL;
107
108 node->nkeys = 0;
109 node->leaf = false;
110
111 return node;
112 }
113
114 ////////////////////////////////////////////////////////////////////////////////
115 // IMPORTANT NOTE: All keys and data must be removed first or else memory
116 // will leak.
117 void
118 btree_mem_node_delete(struct btree_mem_node * node)
119 {
120 free(node->child);
121 free(node->data);
122 free(node->key);
123 free(node);
124 }
125
126 ////////////////////////////////////////////////////////////////////////////////
127 void *
128 btree_mem_find(struct btree_mem * bt, void * key)
129 {
130 int i;
131 struct btree_mem_node * node = btree_mem_node_find(bt, bt->root, key, &i);
132 if (NULL == node)
133 return NULL;
134 return node->data[i];
135 }
136
137 ////////////////////////////////////////////////////////////////////////////////
138 struct btree_mem_node *
139 btree_mem_node_find(struct btree_mem * bt, struct btree_mem_node * node, void * key, int * i)
140 {
141 *i = 0;
142 while (( *i < node->nkeys) && (bt->cmp(key, node->key[*i]) > 0) )
143 (*i)++;
144 if ( (*i < node->nkeys) && (bt->cmp(key, node->key[*i]) == 0) )
145 return node;
146 if (node->leaf)
147 return NULL;
148 else
149 return btree_mem_node_find(bt, node->child[*i], key, i);
150 }
151
152 ////////////////////////////////////////////////////////////////////////////////
153 void *
154 btree_mem_insert(struct btree_mem * bt, void * key, void * data)
155 {
156 struct btree_mem_node * s = bt->root;
157
158 printf("inserting >%d< >%s<\n", *((int *) key), (char *) data);
159 // If the root node is full, split it here.
160 if ((2 * bt->mindeg - 1) == s->nkeys)
161 {
162 printf("Root node is full: splitting\n");
163 s = btree_mem_node_new(bt);
164 if (NULL == s)
165 return NULL;
166 s->child[0] = bt->root;
167 bt->root = s;
168 btree_mem_split_child(bt, s, 0);
169 }
170 return btree_mem_node_insert_nonfull(bt, s, key, data);
171 }
172
173 ////////////////////////////////////////////////////////////////////////////////
174 void *
175 btree_mem_node_insert_nonfull(struct btree_mem * bt, struct btree_mem_node * node, void * key, void * data)
176 {
177 int i = node->nkeys - 1;
178 if (node->leaf)
179 {
180 printf("node is leaf: inserting\n");
181 while ( (i >= 0) && (bt->cmp(key, node->key[i]) < 0) )
182 {
183 node->key[i+1] = node->key[i];
184 i--;
185 }
186 node->key[i+1] = key;
187 node->data[i+1] = data;
188 node->nkeys++;
189 return key;
190 }
191 else
192 {
193 printf("node is not leaf: recursing\n");
194 while ( (i >= 0) && (bt->cmp(key, node->key[i]) < 0) )
195 i--;
196 i++;
197 printf("i %d\n", i);
198
199 /* // Does the child exist? If not we need to allocate it */
200 /* if (NULL == node->child[i]) */
201 /* { */
202 /* node->child[i] = btree_mem_node_new(bt); */
203 /* if (NULL == node->child[i]) */
204 /* return NULL; */
205 /* } */
206
207 if (node->child[i]->nkeys == (2 * bt->mindeg - 1))
208 {
209 printf("splitting before recursion\n");
210 if (NULL == btree_mem_split_child(bt, node, i))
211 return NULL;
212 if (bt->cmp(key, node->key[i]) > 0)
213 i++;
214 }
215 return btree_mem_node_insert_nonfull(bt, node->child[i], key, data);
216 }
217 }
218
219 ////////////////////////////////////////////////////////////////////////////////
220 // x - a non-full node
221 // i - The index of a full node y in x's child list.
222 //
223 // Split y in half, adding the newly created node z as a new child of x.
224 // z will be placed after y in the child list.
225
226 struct btree_mem_node *
227 btree_mem_split_child(struct btree_mem * bt, struct btree_mem_node * x, int i)
228 {
229
230 struct btree_mem_node * y = x->child[i];
231
232 // Allocate new node.
233 struct btree_mem_node * z = btree_mem_node_new(bt);
234 if (NULL == z)
235 return NULL;
236
237 // Load z with the second half of y's data;
238 z->leaf = y->leaf;
239 z->nkeys = bt->mindeg - 1;
240 for (int j = 0; j < bt->mindeg - 1; j++)
241 {
242 z->key[j] = y->key[j + bt->mindeg];
243 z->data[j] = y->data[j + bt->mindeg];
244 }
245 if (! y->leaf)
246 {
247 for (int j = 0; j < bt->mindeg; j++)
248 z->child[j] = y->child[j + bt->mindeg];
249 }
250
251 // Update y's nkeys.
252 y->nkeys = bt->mindeg - 1;
253
254 // Make a hole in x's child list for the new node z.
255 for (int j = x->nkeys; j >= i + 1; j--)
256 x->child[j+1] = x->child[j];
257 x->child[i+1] = z;
258
259 // Make a hole in x's key list for the new node z.
260 for (int j = x->nkeys - 1; j >= i; j--)
261 {
262 x->key[j+1] = x->key[j];
263 x->data[j+1] = x->data[j];
264 }
265 x->key[i] = y->key[bt->mindeg-1];
266 x->data[i] = y->data[bt->mindeg-1];
267
268 x->nkeys += 1;
269
270 /* // NULL out the now unused key and data pointers in y. */
271 /* for (int j = bt->mindeg; j < (2*bt->mindeg - 1); j++) */
272 /* { */
273 /* y->key[j] = NULL; */
274 /* y->data[j] = NULL; */
275 /* y->child[j] = NULL; */
276 /* } */
277 /* y->child[2*bt->mindeg - 1] = NULL; */
278
279 return z;
280 }
281
282 ////////////////////////////////////////////////////////////////////////////////
283 void *
284 btree_mem_remove(struct btree_mem * bt, void * key)
285 {
286
287 }
288
289 ////////////////////////////////////////////////////////////////////////////////
290 void
291 btree_mem_walk_inorder(struct btree_mem * bt, void (*f)(int, void *, void *))
292 {
293 btree_mem_node_walk_inorder(bt->root, f, 0);
294 }
295
296 ////////////////////////////////////////////////////////////////////////////////
297 void
298 btree_mem_node_walk_inorder(struct btree_mem_node * node, void (*f)(int, void *, void *), int depth)
299 {
300
301 // for (int i = 0; i < depth; i++)
302 // printf("\t");
303 // printf("nkeys %d\n", node->nkeys);
304 // printf("walking\n");
305 if (0 == node->nkeys)
306 {
307 // printf("no keys\n");
308 if (NULL != node->child[0])
309 {
310 // printf(": walking child\n");
311 btree_mem_node_walk_inorder(node->child[0], f, depth+1);
312 }
313 return;
314 }
315
316 // printf("walking %d keys\n", node->nkeys);
317 for (int i = 0; i < node->nkeys; i++)
318 {
319 if (! node->leaf)
320 btree_mem_node_walk_inorder(node->child[i], f, depth+1);
321 f(depth, node->key[i], node->data[i]);
322 }
323 if (! node->leaf)
324 btree_mem_node_walk_inorder(node->child[node->nkeys], f, depth+1);
325 }
326