Mercurial > data_structures
changeset 17:36561a63330a
initial btree in memory
author | Eris Caffee<discordia@eldalin.com> |
---|---|
date | Tue, 16 Oct 2012 19:57:23 -0500 |
parents | 5d8158ad2d61 |
children | ef2c6a831fb9 |
files | CMakeLists.txt src/btree_mem.c src/btree_mem.h src/btree_mem_test.c |
diffstat | 4 files changed, 269 insertions(+), 0 deletions(-) [+] |
line diff
1.1 --- a/CMakeLists.txt Thu Oct 04 23:07:48 2012 -0500 1.2 +++ b/CMakeLists.txt Tue Oct 16 19:57:23 2012 -0500 1.3 @@ -118,3 +118,8 @@ 1.4 ${trie_sedgewick_SRCS} 1.5 ) 1.6 1.7 +set (btree_mem_SRCS src/btree_mem.h src/btree_mem.c) 1.8 +add_executable (btree_mem_test 1.9 + src/btree_mem_test.c 1.10 + ${btree_mem_SRCS} 1.11 + ) 1.12 \ No newline at end of file
2.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000 2.2 +++ b/src/btree_mem.c Tue Oct 16 19:57:23 2012 -0500 2.3 @@ -0,0 +1,220 @@ 2.4 +#include <stdio.h> 2.5 + 2.6 +#include <stdlib.h> 2.7 +#include <stdbool.h> 2.8 + 2.9 +#include "btree_mem.h" 2.10 + 2.11 +// In btree_mem_node, child[0].keys <= key[0] < child[1].keys <= key[1] < child[2].keys ... 2.12 +struct btree_mem_node 2.13 + { 2.14 + int nkeys; 2.15 + void ** key; 2.16 + void ** data; 2.17 + struct btree_mem_node ** child; 2.18 + bool leaf; 2.19 + }; 2.20 + 2.21 +struct btree_mem_node * btree_mem_node_new (struct btree_mem * bt); 2.22 +void btree_mem_node_delete (struct btree_mem_node * node); 2.23 + 2.24 +struct btree_mem_node * btree_mem_node_find (struct btree_mem * bt, struct btree_mem_node * node, void * key, int * i); 2.25 + 2.26 +void * btree_mem_node_insert (struct btree_mem * bt, struct btree_mem_node * node, void * key, void * data); 2.27 +struct btree_mem_node * btree_mem_split_child (struct btree_mem * bt, struct btree_mem_node * x, int i, struct btree_mem_node * y); 2.28 + 2.29 +//////////////////////////////////////////////////////////////////////////////// 2.30 +struct btree_mem * 2.31 +btree_mem_new(int min_degree, int (*cmp)(void *, void *)) 2.32 + { 2.33 + struct btree_mem * bt = malloc(sizeof(struct btree_mem)); 2.34 + if (NULL == bt) 2.35 + return NULL; 2.36 + 2.37 + bt->mindeg = min_degree; 2.38 + bt->cmp = cmp; 2.39 + 2.40 + bt->root = btree_mem_node_new(bt); 2.41 + if (NULL == bt->root) 2.42 + { 2.43 + free(bt); 2.44 + return NULL; 2.45 + } 2.46 + 2.47 + return bt; 2.48 + } 2.49 + 2.50 +//////////////////////////////////////////////////////////////////////////////// 2.51 +// IMPORTANT NOTE: All keys and data must be removed first or else memory 2.52 +// will leak. 2.53 +void 2.54 +btree_mem_delete(struct btree_mem * bt) 2.55 + { 2.56 + // TODO: walk down the tree and delete all nodes. 2.57 + free(bt); 2.58 + } 2.59 + 2.60 +//////////////////////////////////////////////////////////////////////////////// 2.61 +struct btree_mem_node * 2.62 +btree_mem_node_new(struct btree_mem * bt) 2.63 + { 2.64 + struct btree_mem_node * node = malloc(sizeof(struct btree_mem_node)); 2.65 + if (NULL == node) 2.66 + return NULL; 2.67 + 2.68 + int maxchild = 2*bt->mindeg; 2.69 + 2.70 + node->key = malloc( (maxchild - 1) * sizeof(void *)); 2.71 + if (NULL == node->key) 2.72 + { 2.73 + free(node); 2.74 + return NULL; 2.75 + } 2.76 + 2.77 + node->data = malloc( (maxchild - 1) * sizeof(void *)); 2.78 + if (NULL == node->data) 2.79 + { 2.80 + free(node->key); 2.81 + free(node); 2.82 + return NULL; 2.83 + } 2.84 + 2.85 + node->child = malloc( maxchild * sizeof(struct btree_mem_node *)); 2.86 + if (NULL == node->data) 2.87 + { 2.88 + free(node->data); 2.89 + free(node->key); 2.90 + free(node); 2.91 + return NULL; 2.92 + } 2.93 + 2.94 + node->nkeys = 0; 2.95 + node->leaf = false; 2.96 + 2.97 + return node; 2.98 + } 2.99 + 2.100 +//////////////////////////////////////////////////////////////////////////////// 2.101 +// IMPORTANT NOTE: All keys and data must be removed first or else memory 2.102 +// will leak. 2.103 +void 2.104 +btree_mem_node_delete(struct btree_mem_node * node) 2.105 + { 2.106 + free(node->child); 2.107 + free(node->data); 2.108 + free(node->key); 2.109 + free(node); 2.110 + } 2.111 + 2.112 +//////////////////////////////////////////////////////////////////////////////// 2.113 +void * 2.114 +btree_mem_find(struct btree_mem * bt, void * key) 2.115 + { 2.116 + int i; 2.117 + struct btree_mem_node * node = btree_mem_node_find(bt, bt->root, key, &i); 2.118 + if (NULL == node) 2.119 + return NULL; 2.120 + return node->data[i]; 2.121 + } 2.122 + 2.123 +//////////////////////////////////////////////////////////////////////////////// 2.124 +struct btree_mem_node * 2.125 +btree_mem_node_find(struct btree_mem * bt, struct btree_mem_node * node, void * key, int * i) 2.126 + { 2.127 + *i = 0; 2.128 + while (( *i < node->nkeys) && (bt->cmp(key, node->key[*i]) > 0) ) 2.129 + (*i)++; 2.130 + if ( (*i < node->nkeys) && (bt->cmp(key, node->key[*i]) == 0) ) 2.131 + return node; 2.132 + if (node->leaf) 2.133 + return NULL; 2.134 + else 2.135 + return btree_mem_node_find(bt, node->child[*i], key, i); 2.136 + } 2.137 + 2.138 +//////////////////////////////////////////////////////////////////////////////// 2.139 +void * 2.140 +btree_mem_insert(struct btree_mem * bt, void * key, void * data) 2.141 + { 2.142 + return btree_mem_node_insert(bt, bt->root, key, data); 2.143 + } 2.144 + 2.145 +//////////////////////////////////////////////////////////////////////////////// 2.146 +void * 2.147 +btree_mem_node_insert(struct btree_mem * bt, struct btree_mem_node * node, void * key, void * data) 2.148 + { 2.149 + struct btree_node * r = bt->root; 2.150 + if ((2 * bt->mindeg - 1) == node->nkeys) 2.151 + { 2.152 + struct btree_node * s = btree_mem_node_new(bt); 2.153 + if (NULL == s) 2.154 + return NULL; 2.155 + bt->root = s; 2.156 + s->child[0] = r; 2.157 + btree_mem_split_child(bt, s, 1, r); 2.158 + r = s; 2.159 + } 2.160 + return btree_mem_node_insert(bt, s, key, data); 2.161 + } 2.162 + 2.163 +//////////////////////////////////////////////////////////////////////////////// 2.164 +// x - a non-full node 2.165 +// y - a full node that is a child of x 2.166 +// i - The index of y in x's child list. That is x->child[i] == y. 2.167 +// 2.168 +// Split y in half, adding the newly created node z as a new child of x. 2.169 +// z will be placed after y in the child list. 2.170 + 2.171 +struct btree_mem_node * 2.172 +btree_mem_split_child(struct btree_mem * bt, struct btree_mem_node * x, int i, struct btree_mem_node * y) 2.173 + { 2.174 + 2.175 + // Allocate new node. 2.176 + struct btree_mem_node * z = btree_mem_node_new(bt); 2.177 + if (NULL == z) 2.178 + return NULL; 2.179 + 2.180 + // Load z with the second half of y's data; 2.181 + z->leaf = y->leaf; 2.182 + z->nkeys = bt->mindeg - 1; 2.183 + for (int j = 0; j < bt->mindeg - 1; j++) 2.184 + { 2.185 + z->key[j] = y->key[j + bt->mindeg]; 2.186 + z->data[j] = y->data[j + bt->mindeg]; 2.187 + } 2.188 + if (! y->leaf) 2.189 + { 2.190 + for (int j = 0; j < bt->mindeg) 2.191 + z->child[j] = y->child[j + bt->mindeg]; 2.192 + } 2.193 + 2.194 + // Update y's nkeys. We don't bother NULLing out the now unused key and data pointers. 2.195 + y->nkeys = bt->mindeg - 1; 2.196 + 2.197 + // Make a hole in x's child list for the new node z. 2.198 + for (int j = x->nkeys; j > i; j--) 2.199 + x->child[j+1] = x->child[j]; 2.200 + x->child[i] = z; 2.201 + 2.202 + // Make a hole in x's key list for the new node z. 2.203 + for (int j = x->nkeys - 1; j > i-1; j--) 2.204 + { 2.205 + x->key[j+1] = x->key[j]; 2.206 + x->data[j+1] = x->data[j]; 2.207 + } 2.208 + x->key[i] = y->key[bt->mindeg-1]; 2.209 + x->data[i] = y->data[bt->mindeg-1]; 2.210 + 2.211 + 2.212 + x->nkeys += 1; 2.213 + 2.214 + return z; 2.215 + } 2.216 + 2.217 +//////////////////////////////////////////////////////////////////////////////// 2.218 +void * 2.219 +btree_mem_remove(struct btree_mem * bt, void * key) 2.220 + { 2.221 + 2.222 + } 2.223 +
3.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000 3.2 +++ b/src/btree_mem.h Tue Oct 16 19:57:23 2012 -0500 3.3 @@ -0,0 +1,21 @@ 3.4 +#ifndef BTREE_MEM_H_ 3.5 +#define BTREE_MEM_H_ 3.6 + 3.7 + 3.8 +struct btree_mem_node; 3.9 + 3.10 +struct btree_mem 3.11 + { 3.12 + int mindeg; 3.13 + struct btree_mem_node * root; 3.14 + int (*cmp)(void *, void *); 3.15 + }; 3.16 + 3.17 +struct btree_mem * btree_mem_new(int min_degree, int (*cmp)(void *, void *)); 3.18 +void btree_mem_delete(struct btree_mem * bt); 3.19 + 3.20 +void * btree_mem_insert(struct btree_mem * bt, void * key, void * data); 3.21 +void * btree_mem_find(struct btree_mem * bt, void * key); 3.22 +void * btree_mem_remove(struct btree_mem * bt, void * key); 3.23 + 3.24 +#endif
4.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000 4.2 +++ b/src/btree_mem_test.c Tue Oct 16 19:57:23 2012 -0500 4.3 @@ -0,0 +1,23 @@ 4.4 +#include <stdio.h> 4.5 +#include <stdlib.h> 4.6 +#include <string.h> 4.7 + 4.8 +#include "btree_mem.h" 4.9 + 4.10 +int 4.11 +cmp(void * a, void * b) 4.12 + { 4.13 + return strcmp(a, b); 4.14 + } 4.15 + 4.16 +int 4.17 +main(int argc, char ** argv) 4.18 + { 4.19 + struct btree_mem * bt = btree_mem_new(2, cmp); 4.20 + if (NULL == bt) 4.21 + { 4.22 + fprintf(stderr, "Unable to create new btree_mem\n"); 4.23 + exit(EXIT_FAILURE); 4.24 + } 4.25 + exit(EXIT_SUCCESS); 4.26 + }