Mercurial > data_structures
changeset 24:f27bdd5d40d0 tip
Ran more tests. Found another leak. Fixed it. Now it's really good. for (( MinDeg=2; MinDeg<=100; MinDeg++ )) ; do echo MinDeg 101 ; numwords 1000 | rev | valgrind --tool=memcheck --leak-check=full --show-reachable=yes ./btree_mem_test 101 2>&1 | grep "ERROR SUMMARY" ; done
| author | Eris Caffee <discordia@eldalin.com> |
|---|---|
| date | Fri, 19 Oct 2012 19:42:17 -0500 |
| parents | 36018adade6d |
| children | |
| files | src/btree_mem.c src/btree_mem_test.c |
| diffstat | 2 files changed, 24 insertions(+), 34 deletions(-) [+] |
line diff
1.1 --- a/src/btree_mem.c Fri Oct 19 18:19:39 2012 -0500 1.2 +++ b/src/btree_mem.c Fri Oct 19 19:42:17 2012 -0500 1.3 @@ -57,12 +57,6 @@ 1.4 #define DEBUG_BLOCK(x) 1.5 #endif 1.6 1.7 -void printit(int h, void * k, void * d) 1.8 - { 1.9 - for (int i = 0; i < h; i++) 1.10 - printf("\t"); 1.11 - printf("%d %s\n", *((int*)k), (char *) d); 1.12 - } 1.13 1.14 1.15 //////////////////////////////////////////////////////////////////////////////// 1.16 @@ -76,7 +70,7 @@ 1.17 bt->mindeg = min_degree; 1.18 bt->cmp = cmp; 1.19 1.20 - printf("Getting new root node\n"); 1.21 + DEBUG_BLOCK( printf("Getting new root node\n"); ); 1.22 bt->root = btree_mem_node_new(bt); 1.23 if (NULL == bt->root) 1.24 { 1.25 @@ -108,7 +102,7 @@ 1.26 if (NULL == node) 1.27 return NULL; 1.28 1.29 - printf("Allocated node %p\n", node); 1.30 + DEBUG_BLOCK( printf("Allocated node %p\n", node); ); 1.31 int maxchild = 2*bt->mindeg; 1.32 1.33 node->key = malloc( (maxchild - 1) * sizeof(void *)); 1.34 @@ -155,7 +149,7 @@ 1.35 void 1.36 btree_mem_node_delete(struct btree_mem_node * node) 1.37 { 1.38 - printf("Freeing node %p\n", node); 1.39 + DEBUG_BLOCK( printf("Freeing node %p\n", node); ); 1.40 free(node->child); 1.41 free(node->data); 1.42 free(node->key); 1.43 @@ -192,13 +186,13 @@ 1.44 void * 1.45 btree_mem_insert(struct btree_mem * bt, void * key, void * data) 1.46 { 1.47 - DEBUG_BLOCK( printf("Inserting key %d data >%s<\n", *((int *) key), (char *) data); ) 1.48 + DEBUG_BLOCK( printf("Inserting key %d data >%s<\n", *((int *) key), (char *) data); ); 1.49 struct btree_mem_node * s = bt->root; 1.50 1.51 // If the root node is full, split it here. 1.52 if ((2 * bt->mindeg - 1) == s->nkeys) 1.53 { 1.54 - printf("Splitting root node. Allocating new node\n"); 1.55 + DEBUG_BLOCK( printf("Splitting root node. Allocating new node\n"); ); 1.56 s = btree_mem_node_new(bt); 1.57 if (NULL == s) 1.58 return NULL; 1.59 @@ -216,7 +210,6 @@ 1.60 int i = node->nkeys - 1; 1.61 if (node->leaf) 1.62 { 1.63 - //DEBUG_BLOCK( printf("node->nkeys: %d\n", node->nkeys); ) 1.64 while ( (i >= 0) && (bt->cmp(key, node->key[i]) < 0) ) 1.65 { 1.66 node->key[i+1] = node->key[i]; 1.67 @@ -259,7 +252,7 @@ 1.68 struct btree_mem_node * y = x->child[i]; 1.69 1.70 // Allocate new node. 1.71 - printf("splitting child allocating new node\n"); 1.72 + DEBUG_BLOCK( printf("splitting child allocating new node\n"); ); 1.73 struct btree_mem_node * z = btree_mem_node_new(bt); 1.74 if (NULL == z) 1.75 return NULL; 1.76 @@ -364,7 +357,6 @@ 1.77 { 1.78 if (! node->leaf) 1.79 btree_mem_node_dump(node->child[i], f, depth+1); 1.80 - printf("node: %p nkeys %10d \t", node, node->nkeys); 1.81 f(depth, node->key[i], node->data[i]); 1.82 } 1.83 if (! node->leaf) 1.84 @@ -378,14 +370,14 @@ 1.85 if ( (NULL == bt) || (NULL == key) || (NULL == key_value) || (NULL == data_value) ) 1.86 return NULL; 1.87 1.88 - DEBUG_BLOCK( printf("Removing %d\n", *((int *) key)); ) 1.89 + DEBUG_BLOCK( printf("Removing %d\n", *((int *) key)); ); 1.90 void * data = btree_mem_node_remove(bt, bt->root, key, key_value, data_value); 1.91 if (NULL == data) 1.92 return NULL; 1.93 1.94 if ( (0 == bt->root->nkeys) && (bt->root->child[0]) ) 1.95 { 1.96 - DEBUG_BLOCK( printf("Freeing the root node\n"); ) 1.97 + DEBUG_BLOCK( printf("Freeing the root node\n"); ); 1.98 struct btree_mem_node * n = bt->root; 1.99 bt->root = bt->root->child[0]; 1.100 btree_mem_node_delete(n); 1.101 @@ -400,7 +392,7 @@ 1.102 btree_mem_node_remove(struct btree_mem * bt, struct btree_mem_node * node, void * key, void ** key_value, void ** data_value) 1.103 { 1.104 1.105 - DEBUG_BLOCK( btree_mem_node_print_keys(node); ) 1.106 + DEBUG_BLOCK( btree_mem_node_print_keys(node); ); 1.107 1.108 int i = node->nkeys - 1; 1.109 while ( (i >= 0) && (bt->cmp(key, node->key[i]) < 0) ) 1.110 @@ -411,11 +403,11 @@ 1.111 // key is in node at key[i] 1.112 *key_value = node->key[i]; 1.113 *data_value = node->data[i]; 1.114 - // printf("Will return key_value %p (%d) data_value %p (%s)\n", *key_value, *((int*)(*key_value)), *data_value, (char*)(*data_value)); 1.115 + 1.116 if (node->leaf) 1.117 { 1.118 // case 1 1.119 - DEBUG_BLOCK( printf("remove: case 1\n"); ) 1.120 + DEBUG_BLOCK( printf("remove: case 1\n"); ); 1.121 btree_mem_node_remove_key(node, i); 1.122 return *data_value; 1.123 } 1.124 @@ -442,7 +434,7 @@ 1.125 else 1.126 { 1.127 // case 2b 1.128 - DEBUG_BLOCK( printf("remove: case 2b\n"); ) 1.129 + DEBUG_BLOCK( printf("remove: case 2b\n"); ); 1.130 kp = btree_mem_node_find_next(next); 1.131 node->key[i] = kp->key[0]; 1.132 node->data[i] = kp->data[0]; 1.133 @@ -455,7 +447,7 @@ 1.134 else 1.135 { 1.136 // case 2c 1.137 - DEBUG_BLOCK( printf("remove: case 2c\n"); ) 1.138 + DEBUG_BLOCK( printf("remove: case 2c\n"); ); 1.139 btree_mem_node_add_key(bt, prev, node->key[i], node->data[i]); 1.140 btree_mem_node_remove_key(node, i); 1.141 for (int j = i+1; j <= node->nkeys+1; j++) 1.142 @@ -472,14 +464,14 @@ 1.143 { 1.144 if (node->leaf) 1.145 { 1.146 - DEBUG_BLOCK( printf("remove: key not found\n"); ) 1.147 + DEBUG_BLOCK( printf("remove: key not found\n"); ); 1.148 return NULL; 1.149 } 1.150 1.151 // key is in child[i+1], if anywhere 1.152 struct btree_mem_node * c = node->child[i+1]; 1.153 1.154 - DEBUG_BLOCK( printf("remove: key should be in node %p\n", c); ) 1.155 + DEBUG_BLOCK( printf("remove: key should be in node %p\n", c); ); 1.156 if (c->nkeys == bt->mindeg - 1) 1.157 { 1.158 struct btree_mem_node * prev = NULL; 1.159 @@ -490,7 +482,7 @@ 1.160 if (i+2 <= node->nkeys) 1.161 next = node->child[i+2]; 1.162 1.163 - DEBUG_BLOCK( printf("remove: prev %p next %p\n", prev, next); ) 1.164 + DEBUG_BLOCK( printf("remove: prev %p next %p\n", prev, next); ); 1.165 1.166 if ( (prev) && (prev->nkeys >= bt->mindeg) ) 1.167 { 1.168 @@ -501,7 +493,7 @@ 1.169 // move prev->child[prev->nkeys] into c->child[0] shifting over existing children 1.170 // prev->nkeys--; 1.171 1.172 - DEBUG_BLOCK( printf("remove: case 3a.1\n"); ) 1.173 + DEBUG_BLOCK( printf("remove: case 3a.1\n"); ); 1.174 1.175 btree_mem_node_add_key(bt, c, node->key[i-1], node->data[i-1]); 1.176 1.177 @@ -522,7 +514,7 @@ 1.178 // case 3a (with next sibling) 1.179 // Symmetric with the above 1.180 1.181 - DEBUG_BLOCK( printf("remove: case 3a.2\n"); ) 1.182 + DEBUG_BLOCK( printf("remove: case 3a.2\n"); ); 1.183 btree_mem_node_add_key(bt, c, node->key[i+1], node->data[i+1]); 1.184 1.185 node->key[i+1] = next->key[0]; 1.186 @@ -546,10 +538,7 @@ 1.187 else 1.188 { 1.189 // case 3b 1.190 - DEBUG_BLOCK( printf("remove: case 3b\n"); ) 1.191 - // printf("=====\n"); btree_mem_node_dump(node, printit, 0); printf("=====\n"); 1.192 - // printf("node %p i %d\n", node, i); fflush(stdout); 1.193 - // printf("adding %d to %p\n", *((int*)node->key[i+1]), (next ? next : prev)); fflush(stdout); 1.194 + DEBUG_BLOCK( printf("remove: case 3b\n"); ); 1.195 if (next) 1.196 btree_mem_node_merge(c, next); 1.197 else 1.198 @@ -561,13 +550,13 @@ 1.199 1.200 if (next) 1.201 { 1.202 - for (int j = i+2; j <= node->nkeys+1; j++) 1.203 + for (int j = i+2; j <= node->nkeys; j++) 1.204 node->child[j] = node->child[j+1]; 1.205 btree_mem_node_delete(next); 1.206 } 1.207 else 1.208 { 1.209 - for (int j = i; j <= node->nkeys+1; j++) 1.210 + for (int j = i; j <= node->nkeys; j++) 1.211 node->child[j] = node->child[j+1]; 1.212 btree_mem_node_delete(c); 1.213 c = prev;
2.1 --- a/src/btree_mem_test.c Fri Oct 19 18:19:39 2012 -0500 2.2 +++ b/src/btree_mem_test.c Fri Oct 19 19:42:17 2012 -0500 2.3 @@ -138,6 +138,8 @@ 2.4 // wackify_tree(bt); 2.5 print_tree(bt); 2.6 2.7 + 2.8 + printf("Deleting tree\n"); 2.9 int * k; 2.10 char * d; 2.11 for (int key = minkey; key <= maxkey; key++) 2.12 @@ -158,9 +160,8 @@ 2.13 else 2.14 free(d); 2.15 } 2.16 + } 2.17 print_tree(bt); 2.18 - } 2.19 - 2.20 2.21 btree_mem_delete(bt); 2.22