Mercurial > data_structures

view src/btree_mem.c @ 17:36561a63330a

find changesets by author, revision, files, or words in the commit message
initial btree in memory
author Eris Caffee<discordia@eldalin.com>
date Tue, 16 Oct 2012 19:57:23 -0500
parents
children ef2c6a831fb9
line source
1 #include <stdio.h>
2
3 #include <stdlib.h>
4 #include <stdbool.h>
5
6 #include "btree_mem.h"
7
8 // In btree_mem_node, child[0].keys <= key[0] < child[1].keys <= key[1] < child[2].keys ...
9 struct btree_mem_node
10 {
11 int nkeys;
12 void ** key;
13 void ** data;
14 struct btree_mem_node ** child;
15 bool leaf;
16 };
17
18 struct btree_mem_node * btree_mem_node_new (struct btree_mem * bt);
19 void btree_mem_node_delete (struct btree_mem_node * node);
20
21 struct btree_mem_node * btree_mem_node_find (struct btree_mem * bt, struct btree_mem_node * node, void * key, int * i);
22
23 void * btree_mem_node_insert (struct btree_mem * bt, struct btree_mem_node * node, void * key, void * data);
24 struct btree_mem_node * btree_mem_split_child (struct btree_mem * bt, struct btree_mem_node * x, int i, struct btree_mem_node * y);
25
26 ////////////////////////////////////////////////////////////////////////////////
27 struct btree_mem *
28 btree_mem_new(int min_degree, int (*cmp)(void *, void *))
29 {
30 struct btree_mem * bt = malloc(sizeof(struct btree_mem));
31 if (NULL == bt)
32 return NULL;
33
34 bt->mindeg = min_degree;
35 bt->cmp = cmp;
36
37 bt->root = btree_mem_node_new(bt);
38 if (NULL == bt->root)
39 {
40 free(bt);
41 return NULL;
42 }
43
44 return bt;
45 }
46
47 ////////////////////////////////////////////////////////////////////////////////
48 // IMPORTANT NOTE: All keys and data must be removed first or else memory
49 // will leak.
50 void
51 btree_mem_delete(struct btree_mem * bt)
52 {
53 // TODO: walk down the tree and delete all nodes.
54 free(bt);
55 }
56
57 ////////////////////////////////////////////////////////////////////////////////
58 struct btree_mem_node *
59 btree_mem_node_new(struct btree_mem * bt)
60 {
61 struct btree_mem_node * node = malloc(sizeof(struct btree_mem_node));
62 if (NULL == node)
63 return NULL;
64
65 int maxchild = 2*bt->mindeg;
66
67 node->key = malloc( (maxchild - 1) * sizeof(void *));
68 if (NULL == node->key)
69 {
70 free(node);
71 return NULL;
72 }
73
74 node->data = malloc( (maxchild - 1) * sizeof(void *));
75 if (NULL == node->data)
76 {
77 free(node->key);
78 free(node);
79 return NULL;
80 }
81
82 node->child = malloc( maxchild * sizeof(struct btree_mem_node *));
83 if (NULL == node->data)
84 {
85 free(node->data);
86 free(node->key);
87 free(node);
88 return NULL;
89 }
90
91 node->nkeys = 0;
92 node->leaf = false;
93
94 return node;
95 }
96
97 ////////////////////////////////////////////////////////////////////////////////
98 // IMPORTANT NOTE: All keys and data must be removed first or else memory
99 // will leak.
100 void
101 btree_mem_node_delete(struct btree_mem_node * node)
102 {
103 free(node->child);
104 free(node->data);
105 free(node->key);
106 free(node);
107 }
108
109 ////////////////////////////////////////////////////////////////////////////////
110 void *
111 btree_mem_find(struct btree_mem * bt, void * key)
112 {
113 int i;
114 struct btree_mem_node * node = btree_mem_node_find(bt, bt->root, key, &i);
115 if (NULL == node)
116 return NULL;
117 return node->data[i];
118 }
119
120 ////////////////////////////////////////////////////////////////////////////////
121 struct btree_mem_node *
122 btree_mem_node_find(struct btree_mem * bt, struct btree_mem_node * node, void * key, int * i)
123 {
124 *i = 0;
125 while (( *i < node->nkeys) && (bt->cmp(key, node->key[*i]) > 0) )
126 (*i)++;
127 if ( (*i < node->nkeys) && (bt->cmp(key, node->key[*i]) == 0) )
128 return node;
129 if (node->leaf)
130 return NULL;
131 else
132 return btree_mem_node_find(bt, node->child[*i], key, i);
133 }
134
135 ////////////////////////////////////////////////////////////////////////////////
136 void *
137 btree_mem_insert(struct btree_mem * bt, void * key, void * data)
138 {
139 return btree_mem_node_insert(bt, bt->root, key, data);
140 }
141
142 ////////////////////////////////////////////////////////////////////////////////
143 void *
144 btree_mem_node_insert(struct btree_mem * bt, struct btree_mem_node * node, void * key, void * data)
145 {
146 struct btree_node * r = bt->root;
147 if ((2 * bt->mindeg - 1) == node->nkeys)
148 {
149 struct btree_node * s = btree_mem_node_new(bt);
150 if (NULL == s)
151 return NULL;
152 bt->root = s;
153 s->child[0] = r;
154 btree_mem_split_child(bt, s, 1, r);
155 r = s;
156 }
157 return btree_mem_node_insert(bt, s, key, data);
158 }
159
160 ////////////////////////////////////////////////////////////////////////////////
161 // x - a non-full node
162 // y - a full node that is a child of x
163 // i - The index of y in x's child list. That is x->child[i] == y.
164 //
165 // Split y in half, adding the newly created node z as a new child of x.
166 // z will be placed after y in the child list.
167
168 struct btree_mem_node *
169 btree_mem_split_child(struct btree_mem * bt, struct btree_mem_node * x, int i, struct btree_mem_node * y)
170 {
171
172 // Allocate new node.
173 struct btree_mem_node * z = btree_mem_node_new(bt);
174 if (NULL == z)
175 return NULL;
176
177 // Load z with the second half of y's data;
178 z->leaf = y->leaf;
179 z->nkeys = bt->mindeg - 1;
180 for (int j = 0; j < bt->mindeg - 1; j++)
181 {
182 z->key[j] = y->key[j + bt->mindeg];
183 z->data[j] = y->data[j + bt->mindeg];
184 }
185 if (! y->leaf)
186 {
187 for (int j = 0; j < bt->mindeg)
188 z->child[j] = y->child[j + bt->mindeg];
189 }
190
191 // Update y's nkeys. We don't bother NULLing out the now unused key and data pointers.
192 y->nkeys = bt->mindeg - 1;
193
194 // Make a hole in x's child list for the new node z.
195 for (int j = x->nkeys; j > i; j--)
196 x->child[j+1] = x->child[j];
197 x->child[i] = z;
198
199 // Make a hole in x's key list for the new node z.
200 for (int j = x->nkeys - 1; j > i-1; j--)
201 {
202 x->key[j+1] = x->key[j];
203 x->data[j+1] = x->data[j];
204 }
205 x->key[i] = y->key[bt->mindeg-1];
206 x->data[i] = y->data[bt->mindeg-1];
207
208
209 x->nkeys += 1;
210
211 return z;
212 }
213
214 ////////////////////////////////////////////////////////////////////////////////
215 void *
216 btree_mem_remove(struct btree_mem * bt, void * key)
217 {
218
219 }
220