Mercurial > data_structures
changeset 12:d359966ed8de
Added trie
| author | Eris Caffee <discordia@eldalin.com> |
|---|---|
| date | Mon, 01 Oct 2012 15:50:30 -0500 |
| parents | 8b09943f1a70 |
| children | 7886d2da8cc4 |
| files | CMakeLists.txt README src/bst.c src/bst.h src/bst_test.c src/list.h src/ost.c src/ost.h src/ost_test.c src/rbtree.c src/rbtree.h src/rbtree_test.c src/trie.c src/trie.h src/trie_test.c |
| diffstat | 15 files changed, 1536 insertions(+), 36 deletions(-) [+] |
line diff
1.1 --- a/CMakeLists.txt Fri Sep 28 19:37:10 2012 -0500 1.2 +++ b/CMakeLists.txt Mon Oct 01 15:50:30 2012 -0500 1.3 @@ -42,42 +42,64 @@ 1.4 1.5 ################################################################################ 1.6 1.7 -set (stack_SRCS src/stack.h src/stack.c src/stack_test.c) 1.8 +set (stack_SRCS src/stack.h src/stack.c) 1.9 add_executable (stack_test 1.10 + src/stack_test.c 1.11 ${stack_SRCS} 1.12 ) 1.13 1.14 -set (ring_buffer_SRCS src/ring_buffer.h src/ring_buffer.c src/ring_buffer_test.c) 1.15 +set (ring_buffer_SRCS src/ring_buffer.h src/ring_buffer.c) 1.16 add_executable (ring_buffer_test 1.17 + src/ring_buffer_test.c 1.18 ${ring_buffer_SRCS} 1.19 ) 1.20 1.21 -set (queue_SRCS src/queue.h src/queue.c src/queue_test.c) 1.22 +set (queue_SRCS src/queue.h src/queue.c) 1.23 add_executable (queue_test 1.24 + src/queue_test.c 1.25 ${queue_SRCS} 1.26 ) 1.27 1.28 -set (dequeue_SRCS src/dequeue.h src/dequeue.c src/dequeue_test.c) 1.29 +set (dequeue_SRCS src/dequeue.h src/dequeue.c) 1.30 add_executable (dequeue_test 1.31 + src/dequeue_test.c 1.32 ${dequeue_SRCS} 1.33 ) 1.34 1.35 -set (pqueue_SRCS src/pqueue.h src/pqueue.c src/pqueue_test.c) 1.36 +set (pqueue_SRCS src/pqueue.h src/pqueue.c) 1.37 add_executable (pqueue_test 1.38 + src/pqueue_test.c 1.39 ${pqueue_SRCS} 1.40 ) 1.41 1.42 -set (list_SRCS src/list.h src/list.c src/list_test.c) 1.43 +set (list_SRCS src/list.h src/list.c) 1.44 add_executable (list_test 1.45 + src/list_test.c 1.46 ${list_SRCS} 1.47 ) 1.48 1.49 -set (bst_SRCS src/bst.h src/bst.c src/bst_test.c) 1.50 +set (bst_SRCS src/bst.h src/bst.c) 1.51 add_executable (bst_test 1.52 + src/bst_test.c 1.53 ${bst_SRCS} 1.54 ) 1.55 1.56 -set (rbtree_SRCS src/rbtree.h src/rbtree.c src/rbtree_test.c) 1.57 +set (rbtree_SRCS src/rbtree.h src/rbtree.c) 1.58 add_executable (rbtree_test 1.59 + src/rbtree_test.c 1.60 ${rbtree_SRCS} 1.61 + ${queue_SRCS} 1.62 ) 1.63 +target_link_libraries(rbtree_test m) 1.64 + 1.65 +set (ost_SRCS src/ost.h src/ost.c) 1.66 +add_executable (ost_test 1.67 + src/ost_test.c 1.68 + ${ost_SRCS} 1.69 + ) 1.70 + 1.71 +set (trie_SRCS src/trie.h src/trie.c) 1.72 +add_executable (trie_test 1.73 + src/trie_test.c 1.74 + ${trie_SRCS} 1.75 + )
2.1 --- a/README Fri Sep 28 19:37:10 2012 -0500 2.2 +++ b/README Mon Oct 01 15:50:30 2012 -0500 2.3 @@ -1,1 +1,30 @@ 2.4 -This is just a collection of basic data structures implemented in C. I did these as a refresher of things I've not had to do in a few years. (why make a dequeue by hand when then STL has a nice one ready to be used?) Thus, the emphasis is on clarity and demonstrating the fundamental technique. Performance and features are not the goal here. 2.5 +This is just a collection of basic data structures implemented in C. I did these as a refresher of things I've not had to do in a few years. (Why make a dequeue by hand when then STL has a nice one ready to be used?) Thus, the emphasis is on clarity and demonstrating the fundamental technique. Performance and features are not the goal here. 2.6 + 2.7 +To build the test programs, run these commands from the top directory of the source tree: 2.8 + 2.9 +mkdir build 2.10 +cd build 2.11 +cmake .. 2.12 +make 2.13 + 2.14 + 2.15 +Included structures: 2.16 + 2.17 +Doubly linked list 2.18 + list.h list.c list_test.c 2.19 +Stack 2.20 + stack.h stack.c stack_test.c 2.21 +Ring buffer 2.22 + ring_buffer.h ring_buffer.c ring_buffer_test.c 2.23 +Queue 2.24 + queue.h queue.c queue_test.c 2.25 +Double ended queue 2.26 + dequeue.h dequeue.c dequeue_test.c 2.27 +Priority queue 2.28 + pqueue.h pqueue.c pqueue_test.c 2.29 +Binary search tree 2.30 + bst.h bst.c bst_test.c 2.31 +Red-black tree 2.32 + rbtree.h rbtree.c rbtrree_test.c 2.33 +Order statistic tree 2.34 + ost.h ost.c ost_test.c
3.1 --- a/src/bst.c Fri Sep 28 19:37:10 2012 -0500 3.2 +++ b/src/bst.c Mon Oct 01 15:50:30 2012 -0500 3.3 @@ -40,7 +40,6 @@ 3.4 struct bst_node * bst_node_search(struct bst * bst, struct bst_node * node, void * data); 3.5 struct bst_node * bst_transplant(struct bst * bst, struct bst_node * a, struct bst_node * b); 3.6 3.7 -void bst_dump(struct bst * bst, void (*print_val)(void *) ); 3.8 void bst_node_dump_preorder(struct bst * bst, struct bst_node * node, void (*print_val)(void *), int depth); 3.9 3.10 //////////////////////////////////////////////////////////////////////////////// 3.11 @@ -420,7 +419,7 @@ 3.12 struct bst_node * 3.13 bst_transplant(struct bst * bst, struct bst_node * a, struct bst_node * b) 3.14 { 3.15 - if ( (NULL == a) || (NULL == b) ) 3.16 + if (NULL == a) 3.17 return NULL; 3.18 3.19 if (NULL == a->parent) 3.20 @@ -443,22 +442,24 @@ 3.21 if ( (NULL == it) || (NULL == it->curr) ) 3.22 return NULL; 3.23 3.24 - struct bst_node * y; 3.25 + // Get successor and save it 3.26 + struct bst_iterator succ; 3.27 + succ.curr = it->curr; 3.28 + succ.bst = it->bst; 3.29 + bst_next(&succ); 3.30 3.31 if (NULL == it->curr->left) 3.32 { 3.33 bst_transplant(it->bst, it->curr, it->curr->right); 3.34 - y = it->curr->right; 3.35 } 3.36 else if (NULL == it->curr->right) 3.37 { 3.38 bst_transplant(it->bst, it->curr, it->curr->left); 3.39 - y = it->curr->left; 3.40 } 3.41 else 3.42 { 3.43 - y = bst_node_minimum(it->curr->right); 3.44 - if (NULL != y->parent) 3.45 + struct bst_node * y = bst_node_minimum(it->curr->right); 3.46 + if (y->parent != it->curr) 3.47 { 3.48 bst_transplant(it->bst, y, y->right); 3.49 y->right = it->curr->right; 3.50 @@ -470,8 +471,16 @@ 3.51 } 3.52 3.53 void * data = it->curr->data; 3.54 + it->curr->data = NULL; 3.55 + it->curr->left = NULL; 3.56 + it->curr->right = NULL; 3.57 + it->curr->parent = NULL; 3.58 free(it->curr); 3.59 - it->curr = y; 3.60 + 3.61 + // Update it to point to saved successor 3.62 + it->curr = succ.curr; 3.63 + it->bst->size--; 3.64 + 3.65 return data; 3.66 } 3.67 3.68 @@ -479,6 +488,9 @@ 3.69 void 3.70 bst_dump(struct bst * bst, void (*print_val)(void *) ) 3.71 { 3.72 + if ( (NULL == bst) || (NULL == bst->root) ) 3.73 + return; 3.74 + 3.75 bst_node_dump_preorder(bst, bst->root, print_val, 0); 3.76 } 3.77 3.78 @@ -495,3 +507,13 @@ 3.79 if (NULL != node->right) 3.80 bst_node_dump_preorder(bst, node->right, print_val, depth+1); 3.81 } 3.82 + 3.83 +//////////////////////////////////////////////////////////////////////////////// 3.84 +unsigned int 3.85 +bst_size (struct bst * bst) 3.86 + { 3.87 + if (NULL == bst) 3.88 + return 0; 3.89 + return bst->size; 3.90 + } 3.91 +
4.1 --- a/src/bst.h Fri Sep 28 19:37:10 2012 -0500 4.2 +++ b/src/bst.h Mon Oct 01 15:50:30 2012 -0500 4.3 @@ -4,7 +4,6 @@ 4.4 #include <stddef.h> 4.5 #include <stdbool.h> 4.6 4.7 -struct bst_node; 4.8 struct bst; 4.9 struct bst_iterator; 4.10 4.11 @@ -16,6 +15,7 @@ 4.12 void * bst_search_iterative (struct bst * bst, void * data); 4.13 void * bst_minimum (struct bst * bst); 4.14 void * bst_maximum (struct bst * bst); 4.15 +unsigned int bst_size (struct bst * bst); 4.16 4.17 void bst_walk_inorder (struct bst * bst, void (*op)(void * data)); 4.18 void bst_walk_preorder (struct bst * bst, void (*op)(void * data));
5.1 --- a/src/bst_test.c Fri Sep 28 19:37:10 2012 -0500 5.2 +++ b/src/bst_test.c Mon Oct 01 15:50:30 2012 -0500 5.3 @@ -5,7 +5,7 @@ 5.4 5.5 #include "bst.h" 5.6 5.7 -#define MAX_NUMS 20 5.8 +#define MAX_NUMS 10 5.9 5.10 void print_val(void * data) 5.11 { 5.12 @@ -168,11 +168,23 @@ 5.13 printf("%d\n", *((int *) bst_value(it))); 5.14 while (bst_next(it)); 5.15 free(it); 5.16 + printf("=================\n"); 5.17 + bst_dump(bst, print_val); 5.18 + printf("=================\n"); 5.19 5.20 5.21 5.22 //////////////////////////////////////// 5.23 - bst_walk_inorder(bst, free_data); 5.24 + it = bst_begin(bst); 5.25 + while (d = bst_remove(it)) 5.26 + { 5.27 + printf("removed %d\n", *((int *) d)); 5.28 + free(d); 5.29 + } 5.30 + free(it); 5.31 + printf("After deletion the size is %d\n", bst_size(bst)); 5.32 + bst_dump(bst, print_val); 5.33 + 5.34 bst_delete(bst); 5.35 5.36 exit(EXIT_SUCCESS);
6.1 --- a/src/list.h Fri Sep 28 19:37:10 2012 -0500 6.2 +++ b/src/list.h Mon Oct 01 15:50:30 2012 -0500 6.3 @@ -3,7 +3,6 @@ 6.4 6.5 #include <stddef.h> 6.6 6.7 -struct list_node; 6.8 struct list; 6.9 struct list_iterator; 6.10
7.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000 7.2 +++ b/src/ost.c Mon Oct 01 15:50:30 2012 -0500 7.3 @@ -0,0 +1,831 @@ 7.4 +// Implemented as a red-black tree 7.5 + 7.6 +#include <stdio.h> 7.7 +#include <stdlib.h> 7.8 + 7.9 +#include "ost.h" 7.10 + 7.11 +enum ost_color { RED, BLACK }; 7.12 + 7.13 +struct ost_node 7.14 + { 7.15 + enum ost_color color; 7.16 + unsigned int size; 7.17 + struct ost_node * parent; 7.18 + struct ost_node * left; 7.19 + struct ost_node * right; 7.20 + void * data; 7.21 + }; 7.22 + 7.23 +struct ost 7.24 + { 7.25 + struct ost_node nil_node; 7.26 + struct ost_node * nil; 7.27 + struct ost_node * root; 7.28 + size_t size; 7.29 + bool (*le)(void * a, void * b); 7.30 + bool (*eq)(void * a, void * b); 7.31 + }; 7.32 + 7.33 +struct ost_iterator 7.34 + { 7.35 + struct ost * ost; 7.36 + struct ost_node * curr; 7.37 + }; 7.38 + 7.39 +void * ost_data_search (struct ost * ost, struct ost_node * node, void * data); 7.40 +void * ost_node_minimum (struct ost * ost, struct ost_node * node); 7.41 +void * ost_node_maximum (struct ost * ost, struct ost_node * node); 7.42 + 7.43 +void ost_data_walk_inorder (struct ost * ost, struct ost_node * node, void (*op)(void * data)); 7.44 +void ost_data_walk_preorder (struct ost * ost, struct ost_node * node, void (*op)(void * data)); 7.45 +void ost_data_walk_postorder (struct ost * ost, struct ost_node * node, void (*op)(void * data)); 7.46 +void ost_node_walk_postorder (struct ost * ost, struct ost_node * node, void (*op)(struct ost_node * n)); 7.47 + 7.48 +void ost_node_free (struct ost_node * node); 7.49 + 7.50 +struct ost_node * ost_node_search (struct ost * ost, struct ost_node * node, void * data); 7.51 + 7.52 +struct ost_node * ost_transplant (struct ost * ost, struct ost_node * a, struct ost_node * b); 7.53 +void ost_rotate_left (struct ost * ost, struct ost_node * node); 7.54 +void ost_rotate_right (struct ost * ost, struct ost_node * node); 7.55 +void ost_insert_fixup (struct ost * ost, struct ost_node * node); 7.56 +void ost_remove_fixup (struct ost * ost, struct ost_node * node); 7.57 + 7.58 +void ost_node_dump_preorder(struct ost * ost, struct ost_node * node, void (*print_val)(void *), int depth); 7.59 + 7.60 +//////////////////////////////////////////////////////////////////////////////// 7.61 +struct ost * 7.62 +ost_new(bool (*le)(void * a, void * b), 7.63 + bool (*eq)(void * a, void * b)) 7.64 + { 7.65 + if ( (NULL == le) || (NULL == eq) ) 7.66 + return NULL; 7.67 + 7.68 + struct ost * ost = malloc(sizeof(struct ost)); 7.69 + if (NULL == ost) 7.70 + return NULL; 7.71 + 7.72 + ost->nil_node = (struct ost_node) { BLACK, 0, &ost->nil_node, &ost->nil_node, &ost->nil_node, NULL }; 7.73 + ost->nil = &(ost->nil_node); 7.74 + ost->root = ost->nil; 7.75 + ost->size = 0; 7.76 + ost->le = le; 7.77 + ost->eq = eq; 7.78 + return ost; 7.79 + } 7.80 + 7.81 + 7.82 +//////////////////////////////////////////////////////////////////////////////// 7.83 +void 7.84 +ost_delete(struct ost * ost) 7.85 + { 7.86 + if (NULL == ost) return; 7.87 + if (0 < ost->size) 7.88 + { 7.89 + // Walk the tree and delete the nodes. 7.90 + // This may cause memory leaks, so hopefully the user has already 7.91 + // emptied the tree. 7.92 + ost_node_walk_postorder(ost, ost->root, ost_node_free); 7.93 + } 7.94 + free(ost); 7.95 + } 7.96 + 7.97 +//////////////////////////////////////////////////////////////////////////////// 7.98 +void 7.99 +ost_node_free(struct ost_node * node) 7.100 + { 7.101 + free(node); 7.102 + } 7.103 + 7.104 +//////////////////////////////////////////////////////////////////////////////// 7.105 +void * 7.106 +ost_insert(struct ost * ost, void * data) 7.107 + { 7.108 + if ( (NULL == ost) || (NULL == data) ) 7.109 + return NULL; 7.110 + 7.111 + struct ost_node * new = malloc(sizeof(struct ost_node)); 7.112 + if (NULL == new) 7.113 + return NULL; 7.114 + new->left = new->right = new->parent = ost->nil; 7.115 + new->color = RED; 7.116 + new->size = 1; 7.117 + new->data = data; 7.118 + 7.119 + if (ost->nil == ost->root) 7.120 + { 7.121 + ost->root = new; 7.122 + new->color = BLACK; 7.123 + new->parent = ost->nil; 7.124 + ost->size = 1; 7.125 + return new->data; 7.126 + } 7.127 + 7.128 + struct ost_node * p = ost->nil; 7.129 + struct ost_node * c = ost->root; 7.130 + 7.131 + while (ost->nil != c) 7.132 + { 7.133 + c->size++; 7.134 + p = c; 7.135 + if (ost->le(new->data, c->data)) 7.136 + c = c->left; 7.137 + else 7.138 + c = c->right; 7.139 + } 7.140 + new->parent = p; 7.141 + if (ost->le(new->data, p->data)) 7.142 + p->left = new; 7.143 + else 7.144 + p->right = new; 7.145 + 7.146 + ost_insert_fixup(ost, new); 7.147 + 7.148 + ost->size++; 7.149 + return new->data; 7.150 + } 7.151 + 7.152 +//////////////////////////////////////////////////////////////////////////////// 7.153 +void 7.154 +ost_insert_fixup(struct ost * ost, struct ost_node * node) 7.155 + { 7.156 + if ( (NULL == ost) || (NULL == node) ) 7.157 + return; 7.158 + 7.159 + while (RED == node->parent->color) 7.160 + { 7.161 + if (node->parent == node->parent->parent->left) 7.162 + { 7.163 + struct ost_node * y = node->parent->parent->right; 7.164 + if (RED == y->color) 7.165 + { 7.166 + node->parent->color = BLACK; 7.167 + y->color = BLACK; 7.168 + node->parent->parent->color = RED; 7.169 + node = node->parent->parent; 7.170 + } 7.171 + else 7.172 + { 7.173 + if (node == node->parent->right) 7.174 + { 7.175 + node = node->parent; 7.176 + ost_rotate_left(ost, node); 7.177 + } 7.178 + node->parent->color = BLACK; 7.179 + node->parent->parent->color = RED; 7.180 + ost_rotate_right(ost, node->parent->parent); 7.181 + } 7.182 + } 7.183 + else 7.184 + { 7.185 + struct ost_node * y = node->parent->parent->left; 7.186 + if (RED == y->color) 7.187 + { 7.188 + node->parent->color = BLACK; 7.189 + y->color = BLACK; 7.190 + node->parent->parent->color = RED; 7.191 + node = node->parent->parent; 7.192 + } 7.193 + else 7.194 + { 7.195 + if (node == node->parent->left) 7.196 + { 7.197 + node = node->parent; 7.198 + ost_rotate_right(ost, node); 7.199 + } 7.200 + node->parent->color = BLACK; 7.201 + node->parent->parent->color = RED; 7.202 + ost_rotate_left(ost, node->parent->parent); 7.203 + } 7.204 + } 7.205 + } 7.206 + ost->root->color = BLACK; 7.207 + } 7.208 + 7.209 +//////////////////////////////////////////////////////////////////////////////// 7.210 +void 7.211 +ost_walk_inorder(struct ost * ost, void (*op)(void * data)) 7.212 + { 7.213 + if ( (NULL == ost) || (ost->nil == ost->root) || (NULL == op) ) 7.214 + return; 7.215 + 7.216 + ost_data_walk_inorder(ost, ost->root, op); 7.217 + } 7.218 + 7.219 +//////////////////////////////////////////////////////////////////////////////// 7.220 +void 7.221 +ost_walk_postorder(struct ost * ost, void (*op)(void * data)) 7.222 + { 7.223 + if ( (NULL == ost) || (ost->nil == ost->root) || (NULL == op) ) 7.224 + return; 7.225 + 7.226 + ost_data_walk_postorder(ost, ost->root, op); 7.227 + } 7.228 + 7.229 +//////////////////////////////////////////////////////////////////////////////// 7.230 +void 7.231 +ost_walk_preorder(struct ost * ost, void (*op)(void * data)) 7.232 + { 7.233 + if ( (NULL == ost) || (ost->nil == ost->root) || (NULL == op) ) 7.234 + return; 7.235 + 7.236 + ost_data_walk_preorder(ost, ost->root, op); 7.237 + } 7.238 + 7.239 +//////////////////////////////////////////////////////////////////////////////// 7.240 +void 7.241 +ost_data_walk_inorder(struct ost * ost, struct ost_node * node, void (*op)(void * data)) 7.242 + { 7.243 + if (ost->nil != node) 7.244 + { 7.245 + ost_data_walk_inorder(ost, node->left, op); 7.246 + op(node->data); 7.247 + ost_data_walk_inorder(ost, node->right, op); 7.248 + } 7.249 + } 7.250 + 7.251 +//////////////////////////////////////////////////////////////////////////////// 7.252 +void 7.253 +ost_data_walk_postorder(struct ost * ost, struct ost_node * node, void (*op)(void * data)) 7.254 + { 7.255 + if (ost->nil != node) 7.256 + { 7.257 + ost_data_walk_postorder(ost, node->left, op); 7.258 + ost_data_walk_postorder(ost, node->right, op); 7.259 + op(node->data); 7.260 + } 7.261 + } 7.262 + 7.263 +//////////////////////////////////////////////////////////////////////////////// 7.264 +void 7.265 +ost_data_walk_preorder(struct ost * ost, struct ost_node * node, void (*op)(void * data)) 7.266 + { 7.267 + if (ost->nil != node) 7.268 + { 7.269 + op(node->data); 7.270 + ost_data_walk_preorder(ost, node->left, op); 7.271 + ost_data_walk_preorder(ost, node->right, op); 7.272 + } 7.273 + } 7.274 + 7.275 +//////////////////////////////////////////////////////////////////////////////// 7.276 +void 7.277 +ost_node_walk_postorder(struct ost * ost, struct ost_node * node, void (*op)(struct ost_node * n)) 7.278 + { 7.279 + if (ost->nil != node) 7.280 + { 7.281 + ost_node_walk_postorder(ost, node->left, op); 7.282 + ost_node_walk_postorder(ost, node->right, op); 7.283 + op(node); 7.284 + } 7.285 + } 7.286 + 7.287 +//////////////////////////////////////////////////////////////////////////////// 7.288 +void * 7.289 +ost_search(struct ost * ost, void * data) 7.290 + { 7.291 + if ( (NULL == ost) || (ost->nil == ost->root) || (NULL == data) ) 7.292 + return NULL; 7.293 + 7.294 + return ost_data_search(ost, ost->root, data); 7.295 + } 7.296 + 7.297 +//////////////////////////////////////////////////////////////////////////////// 7.298 +// Recursive 7.299 +void * 7.300 +ost_data_search(struct ost * ost, struct ost_node * node, void * data) 7.301 + { 7.302 + if (ost->nil == node) 7.303 + return NULL; 7.304 + 7.305 + if (ost->eq(data, node->data)) 7.306 + return node->data; 7.307 + 7.308 + if (ost->le(data, node->data)) 7.309 + return ost_data_search(ost, node->left, data); 7.310 + else 7.311 + return ost_data_search(ost, node->right, data); 7.312 + } 7.313 + 7.314 +//////////////////////////////////////////////////////////////////////////////// 7.315 +// Iterative 7.316 +void * 7.317 +ost_search_iterative(struct ost * ost, void * data) 7.318 + { 7.319 + if ( (NULL == ost) || (ost->nil == ost->root) || (NULL == data) ) 7.320 + return NULL; 7.321 + 7.322 + struct ost_node * node = ost->root; 7.323 + while (1) 7.324 + { 7.325 + if (ost->nil == node) 7.326 + return NULL; 7.327 + 7.328 + if (ost->eq(data, node->data)) 7.329 + return node->data; 7.330 + 7.331 + if (ost->le(data, node->data)) 7.332 + node = node->left; 7.333 + else 7.334 + node = node->right; 7.335 + } 7.336 + } 7.337 + 7.338 +//////////////////////////////////////////////////////////////////////////////// 7.339 +void * 7.340 +ost_minimum(struct ost * ost) 7.341 + { 7.342 + if (NULL == ost) 7.343 + return NULL; 7.344 + 7.345 + return ost_node_minimum(ost, ost->root); 7.346 + } 7.347 + 7.348 +//////////////////////////////////////////////////////////////////////////////// 7.349 +void * 7.350 +ost_node_minimum(struct ost * ost, struct ost_node * node) 7.351 + { 7.352 + while ( (ost->nil != node) && (ost->nil != node->left) ) 7.353 + node = node->left; 7.354 + if (ost->nil == node) 7.355 + return NULL; 7.356 + return node->data; 7.357 + } 7.358 + 7.359 +//////////////////////////////////////////////////////////////////////////////// 7.360 +void * 7.361 +ost_maximum(struct ost * ost) 7.362 + { 7.363 + if (NULL == ost) 7.364 + return NULL; 7.365 + 7.366 + return ost_node_maximum(ost, ost->root); 7.367 + } 7.368 + 7.369 +//////////////////////////////////////////////////////////////////////////////// 7.370 +void * 7.371 +ost_node_maximum(struct ost * ost, struct ost_node * node) 7.372 + { 7.373 + while ( (ost->nil != node) && (ost->nil != node->right) ) 7.374 + node = node->right; 7.375 + if (ost->nil == node) 7.376 + return NULL; 7.377 + return node->data; 7.378 + } 7.379 + 7.380 +//////////////////////////////////////////////////////////////////////////////// 7.381 +struct ost_iterator * 7.382 +ost_begin(struct ost * ost) 7.383 + { 7.384 + if ( (NULL == ost) || (ost->nil == ost->root) ) 7.385 + return NULL; 7.386 + 7.387 + struct ost_node * min = ost->root; 7.388 + while (ost->nil != min->left) 7.389 + min = min->left; 7.390 + 7.391 + struct ost_iterator * it = malloc(sizeof(struct ost_iterator)); 7.392 + if (NULL == it) 7.393 + return NULL; 7.394 + 7.395 + it->ost = ost; 7.396 + it->curr = min; 7.397 + return it; 7.398 + } 7.399 + 7.400 +//////////////////////////////////////////////////////////////////////////////// 7.401 +struct ost_iterator * 7.402 +ost_end(struct ost * ost) 7.403 + { 7.404 + if ( (NULL == ost) || (ost->nil == ost->root) ) 7.405 + return NULL; 7.406 + 7.407 + struct ost_node * max = ost->root; 7.408 + while (ost->nil != max->right) 7.409 + max = max->right; 7.410 + 7.411 + struct ost_iterator * it = malloc(sizeof(struct ost_iterator)); 7.412 + if (NULL == it) 7.413 + return NULL; 7.414 + 7.415 + it->ost = ost; 7.416 + it->curr = max; 7.417 + return it; 7.418 + } 7.419 + 7.420 +//////////////////////////////////////////////////////////////////////////////// 7.421 +struct ost_iterator * 7.422 +ost_next(struct ost_iterator * it) 7.423 + { 7.424 + if ( (NULL == it) || (NULL == it->ost) || (it->ost->nil == it->curr) ) 7.425 + return NULL; 7.426 + 7.427 + if (it->ost->nil == it->curr->right) 7.428 + { 7.429 + struct ost_node * p = it->curr; 7.430 + it->curr = it->curr->parent; 7.431 + while ( (it->ost->nil != it->curr) && (p == it->curr->right) ) 7.432 + { 7.433 + p = it->curr; 7.434 + it->curr = it->curr->parent; 7.435 + } 7.436 + 7.437 + if (it->curr == it->ost->nil) 7.438 + return NULL; 7.439 + } 7.440 + else 7.441 + { 7.442 + struct ost_node * min = it->curr->right; 7.443 + while (it->ost->nil != min->left) 7.444 + min = min->left; 7.445 + it->curr = min; 7.446 + } 7.447 + return it; 7.448 + } 7.449 + 7.450 +//////////////////////////////////////////////////////////////////////////////// 7.451 +struct ost_iterator * 7.452 +ost_prev(struct ost_iterator * it) 7.453 + { 7.454 + if ( (NULL == it) || (NULL == it->ost) || (it->ost->nil == it->curr) ) 7.455 + return NULL; 7.456 + 7.457 + if (it->ost->nil == it->curr->left) 7.458 + { 7.459 + struct ost_node * p = it->curr; 7.460 + it->curr = it->curr->parent; 7.461 + while ( (it->ost->nil != it->curr) && (p == it->curr->left) ) 7.462 + { 7.463 + p = it->curr; 7.464 + it->curr = it->curr->parent; 7.465 + } 7.466 + 7.467 + if (it->curr == it->ost->nil) 7.468 + return NULL; 7.469 + } 7.470 + else 7.471 + { 7.472 + struct ost_node * max = it->curr->left; 7.473 + while (it->ost->nil != max->right) 7.474 + max = max->right; 7.475 + it->curr = max; 7.476 + } 7.477 + return it; 7.478 + } 7.479 + 7.480 +//////////////////////////////////////////////////////////////////////////////// 7.481 +void * 7.482 +ost_value(struct ost_iterator * it) 7.483 + { 7.484 + if ( (NULL == it) || (NULL == it->ost) || (it->ost->nil == it->curr) ) 7.485 + return NULL; 7.486 + 7.487 + return it->curr->data; 7.488 + } 7.489 + 7.490 +//////////////////////////////////////////////////////////////////////////////// 7.491 +void * 7.492 +ost_find(struct ost_iterator * it, void * data) 7.493 + { 7.494 + if ( (NULL == it) || (NULL == it->ost) || (it->ost->nil == it->ost->root) || (NULL == data) ) 7.495 + return NULL; 7.496 + 7.497 + return ost_node_search(it->ost, it->ost->root, data); 7.498 + } 7.499 + 7.500 +//////////////////////////////////////////////////////////////////////////////// 7.501 +// Recursive 7.502 +struct ost_node * 7.503 +ost_node_search(struct ost * ost, struct ost_node * node, void * data) 7.504 + { 7.505 + if (ost->nil == node) 7.506 + return NULL; 7.507 + 7.508 + if (ost->eq(data, node->data)) 7.509 + return node; 7.510 + 7.511 + if (ost->le(data, node->data)) 7.512 + return ost_node_search(ost, node->left, data); 7.513 + else 7.514 + return ost_node_search(ost, node->right, data); 7.515 + } 7.516 + 7.517 +//////////////////////////////////////////////////////////////////////////////// 7.518 +struct ost_node * 7.519 +ost_transplant(struct ost * ost, struct ost_node * a, struct ost_node * b) 7.520 + { 7.521 + if ( (NULL == a) || (NULL == b) ) 7.522 + return NULL; 7.523 + 7.524 + if (ost->nil == a->parent) 7.525 + ost->root = b; 7.526 + else if (a == a->parent->left) 7.527 + a->parent->left = b; 7.528 + else 7.529 + a->parent->right = b; 7.530 + 7.531 + b->parent = a->parent; 7.532 + 7.533 + return a; 7.534 + } 7.535 + 7.536 +//////////////////////////////////////////////////////////////////////////////// 7.537 +void * 7.538 +ost_remove(struct ost_iterator * it) 7.539 + { 7.540 + if ( (NULL == it) || (NULL == it->ost) || (it->ost->nil == it->curr) ) 7.541 + return NULL; 7.542 + 7.543 + // Get successor and save it 7.544 + struct ost_iterator succ; 7.545 + succ.curr = it->curr; 7.546 + succ.ost = it->ost; 7.547 + ost_next(&succ); 7.548 + 7.549 + struct ost_node * x; 7.550 + struct ost_node * y = it->curr; 7.551 + enum ost_color original_color = y->color; 7.552 + 7.553 + if (it->ost->nil == it->curr->left) 7.554 + { 7.555 + x = it->curr->right; 7.556 + ost_transplant(it->ost, it->curr, it->curr->right); 7.557 + } 7.558 + else if (it->ost->nil == it->curr->right) 7.559 + { 7.560 + x = it->curr->left; 7.561 + ost_transplant(it->ost, it->curr, it->curr->left); 7.562 + } 7.563 + else 7.564 + { 7.565 + y = ost_node_minimum(it->ost, it->curr->right); 7.566 + original_color = y->color; 7.567 + x = y->right; 7.568 + if (it->curr == y->parent) 7.569 + x->parent = y; 7.570 + else 7.571 + { 7.572 + ost_transplant(it->ost, y, y->right); 7.573 + y->right = it->curr->right; 7.574 + y->right->parent = y; 7.575 + } 7.576 + ost_transplant(it->ost, it->curr, y); 7.577 + y->left = it->curr->left; 7.578 + y->left->parent = y; 7.579 + y->color = it->curr->color; 7.580 + } 7.581 + 7.582 + if (BLACK == original_color) 7.583 + ost_remove_fixup(it->ost, x); 7.584 + 7.585 + void * data = it->curr->data; 7.586 + free(it->curr); 7.587 + 7.588 + // Update it to point to saved successor 7.589 + it->curr = succ.curr; 7.590 + it->ost->size--; 7.591 + 7.592 + return data; 7.593 + } 7.594 + 7.595 +//////////////////////////////////////////////////////////////////////////////// 7.596 +void 7.597 +ost_remove_fixup(struct ost * ost, struct ost_node * node) 7.598 + { 7.599 + while ( (ost->root != node) && (BLACK == node->color) ) 7.600 + { 7.601 + if (node == node->parent->left) 7.602 + { 7.603 + struct ost_node * w = node->parent->right; 7.604 + if (RED == w->color) 7.605 + { 7.606 + w->color = BLACK; 7.607 + node->parent->color = RED; 7.608 + ost_rotate_left(ost, node->parent); 7.609 + w = node->parent->right; 7.610 + } 7.611 + if ( (BLACK == w->left->color) && (BLACK == w->right->color) ) 7.612 + { 7.613 + w->left->color = RED; 7.614 + node = node->parent; 7.615 + } 7.616 + else 7.617 + { 7.618 + if (BLACK == w->right->color) 7.619 + { 7.620 + w->left->color = BLACK; 7.621 + w->color = RED; 7.622 + ost_rotate_right(ost, w); 7.623 + w = node->parent->right; 7.624 + } 7.625 + w->color = node->parent->color; 7.626 + node->parent->color = BLACK; 7.627 + w->right->color = BLACK; 7.628 + ost_rotate_left(ost, node->parent); 7.629 + node = ost->root; 7.630 + } 7.631 + } 7.632 + else 7.633 + { 7.634 + struct ost_node * w = node->parent->left; 7.635 + if (RED == w->color) 7.636 + { 7.637 + w->color = BLACK; 7.638 + node->parent->color = RED; 7.639 + ost_rotate_right(ost, node->parent); 7.640 + w = node->parent->left; 7.641 + } 7.642 + if ( (BLACK == w->right->color) && (BLACK == w->left->color) ) 7.643 + { 7.644 + w->right->color = RED; 7.645 + node = node->parent; 7.646 + } 7.647 + else 7.648 + { 7.649 + if (BLACK == w->left->color) 7.650 + { 7.651 + w->right->color = BLACK; 7.652 + w->color = RED; 7.653 + ost_rotate_left(ost, w); 7.654 + w = node->parent->left; 7.655 + } 7.656 + w->color = node->parent->color; 7.657 + node->parent->color = BLACK; 7.658 + w->left->color = BLACK; 7.659 + ost_rotate_right(ost, node->parent); 7.660 + node = ost->root; 7.661 + } 7.662 + } 7.663 + } 7.664 + node->color = BLACK; 7.665 + } 7.666 + 7.667 +//////////////////////////////////////////////////////////////////////////////// 7.668 +void 7.669 +ost_rotate_left(struct ost * ost, struct ost_node * node) 7.670 + { 7.671 + if ( (NULL == ost) || (ost->nil == node) || (ost->nil == node->right) ) 7.672 + return; 7.673 + 7.674 + struct ost_node * y = node->right; 7.675 + 7.676 + node->right = y->left; 7.677 + if (ost->nil != y->left) 7.678 + y->left->parent = node; 7.679 + 7.680 + y->parent = node->parent; 7.681 + if (ost->nil == node->parent) 7.682 + ost->root = y; 7.683 + else if (node == node->parent->left) 7.684 + node->parent->left = y; 7.685 + else 7.686 + node->parent->right = y; 7.687 + 7.688 + y->left = node; 7.689 + node->parent = y; 7.690 + 7.691 + y->size = node->size; 7.692 + node->size = node->left->size + node->right->size + 1; 7.693 + } 7.694 + 7.695 +//////////////////////////////////////////////////////////////////////////////// 7.696 +void 7.697 +ost_rotate_right(struct ost * ost, struct ost_node * node) 7.698 + { 7.699 + if ( (NULL == ost) || (ost->nil == node) || (ost->nil == node->left) ) 7.700 + return; 7.701 + 7.702 + struct ost_node * y = node->left; 7.703 + 7.704 + node->left = y->right; 7.705 + if (ost->nil != y->right) 7.706 + y->right->parent = node; 7.707 + 7.708 + y->parent = node->parent; 7.709 + if (ost->nil == node->parent) 7.710 + ost->root = y; 7.711 + else if (node == node->parent->right) 7.712 + node->parent->right = y; 7.713 + else 7.714 + node->parent->left = y; 7.715 + 7.716 + y->right = node; 7.717 + node->parent = y; 7.718 + 7.719 + y->size = node->size; 7.720 + node->size = node->left->size + node->right->size + 1; 7.721 + } 7.722 + 7.723 +//////////////////////////////////////////////////////////////////////////////// 7.724 +unsigned int ost_black_depth(struct ost * ost) 7.725 + { 7.726 + if ( (NULL == ost) || (NULL == ost->root) ) 7.727 + return 0; 7.728 + 7.729 + struct ost_node * node = ost->root; 7.730 + unsigned int black_depth = 0; 7.731 + 7.732 + while (ost->nil != node) 7.733 + { 7.734 + if (BLACK == node->color) 7.735 + black_depth++; 7.736 + node = node->left; 7.737 + } 7.738 + 7.739 + return black_depth; 7.740 + } 7.741 + 7.742 +//////////////////////////////////////////////////////////////////////////////// 7.743 +void 7.744 +ost_dump(struct ost * ost, void (*print_val)(void *) ) 7.745 + { 7.746 + if ( (NULL == ost) || (ost->nil == ost->root) ) 7.747 + return; 7.748 + ost_node_dump_preorder(ost, ost->root, print_val, 0); 7.749 + } 7.750 + 7.751 +//////////////////////////////////////////////////////////////////////////////// 7.752 +void 7.753 +ost_node_dump_preorder(struct ost * ost, struct ost_node * node, void (*print_val)(void *), int depth) 7.754 + { 7.755 + for (int i=0; i < depth; i++) 7.756 + printf("\t"); 7.757 + printf("%-8s", (BLACK == node->color ? "black" : "red")); 7.758 + print_val(node->data); 7.759 + printf("\n"); 7.760 + if (ost->nil != node->left) 7.761 + ost_node_dump_preorder(ost, node->left, print_val, depth+1); 7.762 + if (ost->nil != node->right) 7.763 + ost_node_dump_preorder(ost, node->right, print_val, depth+1); 7.764 + } 7.765 + 7.766 +//////////////////////////////////////////////////////////////////////////////// 7.767 +struct ost_iterator * 7.768 +ost_select(struct ost * ost, unsigned int i) 7.769 + { 7.770 + if ( (NULL == ost) || (ost->nil == ost->root) ) 7.771 + return NULL; 7.772 + 7.773 + struct ost_iterator * it = malloc(sizeof(struct ost_iterator)); 7.774 + if (NULL == it) 7.775 + return NULL; 7.776 + 7.777 + it->ost = ost; 7.778 + it->curr = ost->root; 7.779 + return ost_select_subtree(it, i); 7.780 + } 7.781 + 7.782 +//////////////////////////////////////////////////////////////////////////////// 7.783 +struct ost_iterator * 7.784 +ost_select_subtree(struct ost_iterator * it, unsigned int i) 7.785 + { 7.786 + if ( (NULL == it) || (NULL == it->ost) ) 7.787 + return NULL; 7.788 + 7.789 + unsigned int r = it->curr->left->size + 1; 7.790 + if (i == r) 7.791 + return it; 7.792 + else 7.793 + { 7.794 + if (i < r) 7.795 + { 7.796 + it->curr = it->curr->left; 7.797 + return ost_select_subtree(it, i); 7.798 + } 7.799 + else 7.800 + { 7.801 + it->curr = it->curr->right; 7.802 + return ost_select_subtree(it, i - r); 7.803 + } 7.804 + } 7.805 + return it; 7.806 + } 7.807 + 7.808 +//////////////////////////////////////////////////////////////////////////////// 7.809 +unsigned int 7.810 +ost_rank(struct ost_iterator * it) 7.811 + { 7.812 + if ( (NULL == it) || (NULL == it->ost) ) 7.813 + return 0; 7.814 + 7.815 + unsigned int r = it->curr->left->size + 1; 7.816 + struct ost_node * y = it->curr; 7.817 + while (y != it->ost->root) 7.818 + { 7.819 + if (y == y->parent->right) 7.820 + r += y->parent->left->size + 1; 7.821 + y = y->parent; 7.822 + } 7.823 + return r; 7.824 + } 7.825 + 7.826 +//////////////////////////////////////////////////////////////////////////////// 7.827 +unsigned int 7.828 +ost_size (struct ost * ost) 7.829 + { 7.830 + if (NULL == ost) 7.831 + return 0; 7.832 + return ost->size; 7.833 + } 7.834 +
8.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000 8.2 +++ b/src/ost.h Mon Oct 01 15:50:30 2012 -0500 8.3 @@ -0,0 +1,40 @@ 8.4 +#ifndef OST_H_ 8.5 +#define OST_H_ 8.6 + 8.7 +#include <stddef.h> 8.8 +#include <stdbool.h> 8.9 + 8.10 +struct ost; 8.11 +struct ost_iterator; 8.12 + 8.13 +struct ost * ost_new(bool (*le)(void * a, void * b), bool (*eq)(void * a, void * b)); 8.14 +void ost_delete(struct ost * ost); 8.15 + 8.16 +void * ost_insert (struct ost * ost, void * data); 8.17 +void * ost_search (struct ost * ost, void * data); 8.18 +void * ost_search_iterative (struct ost * ost, void * data); 8.19 +void * ost_minimum (struct ost * ost); 8.20 +void * ost_maximum (struct ost * ost); 8.21 +unsigned int ost_size (struct ost * ost); 8.22 + 8.23 +void ost_walk_inorder (struct ost * ost, void (*op)(void * data)); 8.24 +void ost_walk_preorder (struct ost * ost, void (*op)(void * data)); 8.25 +void ost_walk_postorder (struct ost * ost, void (*op)(void * data)); 8.26 + 8.27 +struct ost_iterator * ost_begin (struct ost * ost); 8.28 +struct ost_iterator * ost_end (struct ost * ost); 8.29 +struct ost_iterator * ost_next (struct ost_iterator * it); 8.30 +struct ost_iterator * ost_prev (struct ost_iterator * it); 8.31 +void * ost_find (struct ost_iterator * it, void * data); 8.32 +void * ost_remove (struct ost_iterator * it); 8.33 +void * ost_value (struct ost_iterator * it); 8.34 + 8.35 +unsigned int ost_black_depth(struct ost * ost); 8.36 +void ost_dump(struct ost * ost, void (*print_val)(void *) ); 8.37 + 8.38 +struct ost_iterator * ost_select(struct ost * ost, unsigned int i); 8.39 +struct ost_iterator * ost_select_subtree(struct ost_iterator * it, unsigned int i); 8.40 +unsigned int ost_rank(struct ost_iterator * it); 8.41 + 8.42 + 8.43 +#endif
9.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000 9.2 +++ b/src/ost_test.c Mon Oct 01 15:50:30 2012 -0500 9.3 @@ -0,0 +1,142 @@ 9.4 +#include <stdio.h> 9.5 +#include <stdlib.h> 9.6 +#include <stdbool.h> 9.7 + 9.8 +#include "ost.h" 9.9 + 9.10 +void print_val(void * data) 9.11 + { 9.12 + printf("%d", *((int *) data)); 9.13 + } 9.14 + 9.15 +bool le(void * a, void * b) 9.16 + { 9.17 + return *((int *) a) <= *((int *) b); 9.18 + } 9.19 + 9.20 +bool eq(void * a, void * b) 9.21 + { 9.22 + return *((int *) a) == *((int *) b); 9.23 + } 9.24 + 9.25 +#define MAX_NUMS 10 9.26 + 9.27 +int main (int argc, char ** argv) 9.28 + { 9.29 + int sorted[100] = { 9.30 + 35005211, 42999170, 84353895, 135497281, 137806862, 149798315, 184803526, 233665123, 278722862, 294702567, 9.31 + 304089172, 336465782, 356426808, 412776091, 424238335, 468703135, 491705403, 511702305, 521595368, 572660336, 9.32 + 596516649, 608413784, 610515434, 628175011, 635723058, 709393584, 719885386, 749241873, 752392754, 756898537, 9.33 + 760313750, 783368690, 805750846, 846930886, 855636226, 859484421, 861021530, 939819582, 943947739, 945117276, 9.34 + 982906996, 1025202362, 1059961393, 1100661313, 1101513929, 1102520059, 1125898167, 1129566413, 1131176229, 1141616124, 9.35 + 1159126505, 1189641421, 1264095060, 1303455736, 1315634022, 1350490027, 1365180540, 1369133069, 1374344043, 1411549676, 9.36 + 1424268980, 1433925857, 1469348094, 1474612399, 1477171087, 1540383426, 1548233367, 1585990364, 1632621729, 1649760492, 9.37 + 1653377373, 1656478042, 1681692777, 1714636915, 1726956429, 1734575198, 1749698586, 1780695788, 1801979802, 1804289383, 9.38 + 1827336327, 1843993368, 1889947178, 1911759956, 1914544919, 1918502651, 1937477084, 1956297539, 1957747793, 1967513926, 9.39 + 1973594324, 1984210012, 1998898814, 2001100545, 2038664370, 2044897763, 2053999932, 2084420925, 2089018456, 2145174067, 9.40 + }; 9.41 + 9.42 + struct ost * ost = ost_new(le, eq); 9.43 + if (NULL == ost) 9.44 + { 9.45 + perror("ost_new"); 9.46 + exit(EXIT_FAILURE); 9.47 + } 9.48 + 9.49 + for (int i = 0; i < MAX_NUMS; ++i) 9.50 + { 9.51 + int * ip = malloc(sizeof(int)); 9.52 + if (NULL == ip) 9.53 + { 9.54 + perror("malloc"); 9.55 + exit(EXIT_FAILURE); 9.56 + } 9.57 + *ip = rand(); 9.58 + // Be sure to set MAX_NUMS = 100 if you want to use the sorted array 9.59 + // *ip = sorted[i]; 9.60 + int * ip2; 9.61 + if (NULL == (ip2 = ost_insert(ost, ip))) 9.62 + { 9.63 + printf("ost_insert failed\n"); 9.64 + free(ip); 9.65 + } 9.66 + printf("inserting %d\n", *ip2); 9.67 + } 9.68 + 9.69 + 9.70 + // print the tree structure 9.71 + ost_dump(ost, print_val); 9.72 + fprintf(stderr, "black depth is %u\n", ost_black_depth(ost)); 9.73 + 9.74 + // Print the tree in value order with their ranks 9.75 + struct ost_iterator * it; 9.76 + struct ost_iterator * next; 9.77 + for (next = it = ost_begin(ost); NULL != next; next = ost_next(it)) 9.78 + printf("%-16d%u\n", *((int *) ost_value(it)), ost_rank(it)); 9.79 + free(it); 9.80 + 9.81 + 9.82 + // Get the first 5th and 10th elements 9.83 + it = ost_select(ost, 1); 9.84 + if (NULL == it) 9.85 + { 9.86 + printf("ost_select failed\n"); 9.87 + exit(EXIT_FAILURE); 9.88 + } 9.89 + printf("1st order statistic is %d\n", *((int *) ost_value(it))); 9.90 + free(it); 9.91 + 9.92 + it = ost_select(ost, 5); 9.93 + if (NULL == it) 9.94 + { 9.95 + printf("ost_select failed\n"); 9.96 + exit(EXIT_FAILURE); 9.97 + } 9.98 + printf("5th order statistic is %d\n", *((int *) ost_value(it))); 9.99 + free(it); 9.100 + 9.101 + it = ost_select(ost, 10); 9.102 + if (NULL == it) 9.103 + { 9.104 + printf("ost_select failed\n"); 9.105 + exit(EXIT_FAILURE); 9.106 + } 9.107 + printf("10th order statistic is %d\n", *((int *) ost_value(it))); 9.108 + free(it); 9.109 + 9.110 + 9.111 + // Free the whole tree 9.112 + void * d; 9.113 + it = ost_begin(ost); 9.114 + while (d = ost_remove(it)) 9.115 + { 9.116 + printf("removed %d\n", *((int *) d)); 9.117 + free(d); 9.118 + } 9.119 + free(it); 9.120 + printf("After deletion the size is %u\n", ost_size(ost)); 9.121 + ost_dump(ost, print_val); 9.122 + 9.123 + 9.124 + 9.125 + // This next should fail 9.126 + it = ost_select(ost, 1); 9.127 + if (NULL != it) 9.128 + { 9.129 + printf("ost_select failed\n"); 9.130 + exit(EXIT_FAILURE); 9.131 + } 9.132 + 9.133 + ost_delete(ost); 9.134 + ost = NULL; 9.135 + 9.136 + // This next should fail 9.137 + it = ost_select(ost, 1); 9.138 + if (NULL != it) 9.139 + { 9.140 + printf("ost_select failed\n"); 9.141 + exit(EXIT_FAILURE); 9.142 + } 9.143 + 9.144 + exit(EXIT_SUCCESS); 9.145 + }
10.1 --- a/src/rbtree.c Fri Sep 28 19:37:10 2012 -0500 10.2 +++ b/src/rbtree.c Mon Oct 01 15:50:30 2012 -0500 10.3 @@ -1,7 +1,9 @@ 10.4 #include <stdio.h> 10.5 #include <stdlib.h> 10.6 +#include <math.h> 10.7 10.8 #include "rbtree.h" 10.9 +#include "queue.h" 10.10 10.11 enum rbtree_color { RED, BLACK }; 10.12 10.13 @@ -529,14 +531,14 @@ 10.14 void * 10.15 rbtree_remove(struct rbtree_iterator * it) 10.16 { 10.17 - if ( (NULL == it) || (NULL == it->curr) ) 10.18 + if ( (NULL == it) || (NULL == it->rbtree) || (it->rbtree->nil == it->curr) ) 10.19 return NULL; 10.20 10.21 - // Get predecessor and save it 10.22 - struct rbtree_iterator pred; 10.23 - pred.curr = it->curr; 10.24 - pred.rbtree = it->rbtree; 10.25 - rbtree_prev(&pred); 10.26 + // Get successor and save it 10.27 + struct rbtree_iterator succ; 10.28 + succ.curr = it->curr; 10.29 + succ.rbtree = it->rbtree; 10.30 + rbtree_next(&succ); 10.31 10.32 struct rbtree_node * x; 10.33 struct rbtree_node * y = it->curr; 10.34 @@ -577,9 +579,9 @@ 10.35 void * data = it->curr->data; 10.36 free(it->curr); 10.37 10.38 - // Update it to point to pred's successor 10.39 - rbtree_next(&pred); 10.40 - it->curr = pred.curr; 10.41 + // Update it to point to saved successor 10.42 + it->curr = succ.curr; 10.43 + it->rbtree->size--; 10.44 10.45 return data; 10.46 } 10.47 @@ -729,6 +731,9 @@ 10.48 void 10.49 rbtree_dump(struct rbtree * rbtree, void (*print_val)(void *) ) 10.50 { 10.51 + if ( (NULL == rbtree) || (rbtree->nil == rbtree->root) ) 10.52 + return; 10.53 + 10.54 rbtree_node_dump_preorder(rbtree, rbtree->root, print_val, 0); 10.55 } 10.56 10.57 @@ -746,3 +751,44 @@ 10.58 if (rbtree->nil != node->right) 10.59 rbtree_node_dump_preorder(rbtree, node->right, print_val, depth+1); 10.60 } 10.61 + 10.62 +//////////////////////////////////////////////////////////////////////////////// 10.63 +unsigned int 10.64 +rbtree_size (struct rbtree * rbtree) 10.65 + { 10.66 + if (NULL == rbtree) 10.67 + return 0; 10.68 + return rbtree->size; 10.69 + } 10.70 + 10.71 +//////////////////////////////////////////////////////////////////////////////// 10.72 +void 10.73 +rbtree_walk_breadth_first (struct rbtree * rbtree, void (*op)(void * data)) 10.74 + { 10.75 + if ( (NULL == rbtree) || (NULL == op) ) 10.76 + return; 10.77 + 10.78 + if (0 == rbtree->size) 10.79 + return; 10.80 + 10.81 + // Should really use a dynamically sized queue here. 10.82 + struct queue * q = queue_new(rbtree->size); 10.83 + if (NULL == q) 10.84 + return; 10.85 + 10.86 + queue_push(q, rbtree->root); 10.87 + 10.88 + struct rbtree_node * node; 10.89 + 10.90 + while (node = queue_pop(q)) 10.91 + { 10.92 + if (rbtree->nil != node->left) 10.93 + queue_push(q, node->left); 10.94 + if (rbtree->nil != node->right) 10.95 + queue_push(q, node->right); 10.96 + op(node->data); 10.97 + } 10.98 + 10.99 + queue_delete(q); 10.100 + } 10.101 +
11.1 --- a/src/rbtree.h Fri Sep 28 19:37:10 2012 -0500 11.2 +++ b/src/rbtree.h Mon Oct 01 15:50:30 2012 -0500 11.3 @@ -5,7 +5,6 @@ 11.4 #include <stdbool.h> 11.5 11.6 struct rbtree; 11.7 -struct rbtree_node; 11.8 struct rbtree_iterator; 11.9 11.10 struct rbtree * rbtree_new(bool (*le)(void * a, void * b), bool (*eq)(void * a, void * b)); 11.11 @@ -16,10 +15,12 @@ 11.12 void * rbtree_search_iterative (struct rbtree * rbtree, void * data); 11.13 void * rbtree_minimum (struct rbtree * rbtree); 11.14 void * rbtree_maximum (struct rbtree * rbtree); 11.15 +unsigned int rbtree_size (struct rbtree * rbtree); 11.16 11.17 void rbtree_walk_inorder (struct rbtree * rbtree, void (*op)(void * data)); 11.18 void rbtree_walk_preorder (struct rbtree * rbtree, void (*op)(void * data)); 11.19 void rbtree_walk_postorder (struct rbtree * rbtree, void (*op)(void * data)); 11.20 +void rbtree_walk_breadth_first (struct rbtree * rbtree, void (*op)(void * data)); 11.21 11.22 struct rbtree_iterator * rbtree_begin (struct rbtree * rbtree); 11.23 struct rbtree_iterator * rbtree_end (struct rbtree * rbtree);
12.1 --- a/src/rbtree_test.c Fri Sep 28 19:37:10 2012 -0500 12.2 +++ b/src/rbtree_test.c Mon Oct 01 15:50:30 2012 -0500 12.3 @@ -9,6 +9,11 @@ 12.4 printf("%d", *((int *) data)); 12.5 } 12.6 12.7 +void print_val2(void * data) 12.8 + { 12.9 + printf("%d\n", *((int *) data)); 12.10 + } 12.11 + 12.12 bool le(void * a, void * b) 12.13 { 12.14 return *((int *) a) <= *((int *) b); 12.15 @@ -19,7 +24,7 @@ 12.16 return *((int *) a) == *((int *) b); 12.17 } 12.18 12.19 -#define MAX_NUMS 100 12.20 +#define MAX_NUMS 128 12.21 12.22 int main (int argc, char ** argv) 12.23 { 12.24 @@ -75,14 +80,62 @@ 12.25 printf("%d\n", *((int *) rbtree_value(it))); 12.26 free(it); 12.27 12.28 + // Free the whole tree 12.29 + void * d; 12.30 + it = rbtree_begin(rbtree); 12.31 + while (d = rbtree_remove(it)) 12.32 + { 12.33 + printf("removed %d\n", *((int *) d)); 12.34 + free(d); 12.35 + } 12.36 + free(it); 12.37 + printf("After deletion the size is %u\n", rbtree_size(rbtree)); 12.38 + rbtree_dump(rbtree, print_val); 12.39 12.40 - // Free the whole tree 12.41 - for (next = it = rbtree_begin(rbtree); NULL != next; next = rbtree_next(it)) 12.42 - free(rbtree_value(it)); 12.43 - free(it); 12.44 12.45 12.46 rbtree_delete(rbtree); 12.47 12.48 + 12.49 + ////////////////////////////////////////// 12.50 + // New tree to test beadth first walk 12.51 + 12.52 + printf("Walking a tree breadth first\n"); 12.53 + rbtree = rbtree_new(le, eq); 12.54 + if (NULL == rbtree) 12.55 + { 12.56 + perror("rbtree_new"); 12.57 + exit(EXIT_FAILURE); 12.58 + } 12.59 + 12.60 + for (int i = 0; i < 10; ++i) 12.61 + { 12.62 + int * ip = malloc(sizeof(int)); 12.63 + if (NULL == ip) 12.64 + { 12.65 + perror("malloc"); 12.66 + exit(EXIT_FAILURE); 12.67 + } 12.68 + *ip = rand(); 12.69 + int * ip2; 12.70 + if (NULL == (ip2 = rbtree_insert(rbtree, ip))) 12.71 + { 12.72 + printf("rbtree_insert failed\n"); 12.73 + free(ip); 12.74 + } 12.75 + } 12.76 + 12.77 + 12.78 + // print the tree structure 12.79 + rbtree_dump(rbtree, print_val); 12.80 + rbtree_walk_breadth_first(rbtree, print_val2); 12.81 + 12.82 + // Free the whole tree 12.83 + it = rbtree_begin(rbtree); 12.84 + while (d = rbtree_remove(it)) 12.85 + free(d); 12.86 + free(it); 12.87 + rbtree_delete(rbtree); 12.88 + 12.89 exit(EXIT_SUCCESS); 12.90 }
13.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000 13.2 +++ b/src/trie.c Mon Oct 01 15:50:30 2012 -0500 13.3 @@ -0,0 +1,238 @@ 13.4 +#include <ctype.h> 13.5 +#include <stdlib.h> 13.6 +#include <stdbool.h> 13.7 +#include <string.h> 13.8 + 13.9 + 13.10 +#include <stdio.h> 13.11 + 13.12 + 13.13 +struct trie_node 13.14 + { 13.15 + char key; 13.16 + struct trie_node * child; 13.17 + struct trie_node * sibling; 13.18 + void * data; 13.19 + }; 13.20 + 13.21 +struct trie 13.22 + { 13.23 + struct trie_node * root; 13.24 + }; 13.25 + 13.26 +struct trie_node * trie_search_children(struct trie_node * node, char k); 13.27 +void trie_visit_node(struct trie * trie, struct trie_node * node, void (*op)(char * k, void * d), char * key); 13.28 +void trie_print_node(struct trie_node * node); 13.29 +void trie_print_node(struct trie_node * node); 13.30 +void trie_node_dump_preorder(struct trie * trie, struct trie_node * node, int depth); 13.31 +void trie_node_dump_raw(struct trie_node * node, int depth); 13.32 + 13.33 +//////////////////////////////////////////////////////////////////////////////// 13.34 +struct trie * 13.35 +trie_new() 13.36 + { 13.37 + struct trie * trie = malloc(sizeof(struct trie)); 13.38 + if (NULL == trie) 13.39 + return NULL; 13.40 + 13.41 + trie->root = malloc(sizeof(struct trie_node)); 13.42 + if (NULL == trie->root) 13.43 + return NULL; 13.44 + 13.45 + trie->root->child = trie->root->sibling = NULL; 13.46 + trie->root->key = '\0'; 13.47 + trie->root->data = NULL; 13.48 + 13.49 + return trie; 13.50 + } 13.51 + 13.52 +//////////////////////////////////////////////////////////////////////////////// 13.53 +void 13.54 +trie_delete(struct trie * trie) 13.55 + { 13.56 + if (NULL == trie) 13.57 + return; 13.58 + 13.59 + free(trie); 13.60 + } 13.61 + 13.62 +//////////////////////////////////////////////////////////////////////////////// 13.63 +char * 13.64 +trie_insert(struct trie * trie, char * key, void * data) 13.65 + { 13.66 + if ( (NULL == trie) || (NULL == key) ) 13.67 + return NULL; 13.68 + 13.69 + struct trie_node * curr = trie->root; 13.70 + struct trie_node * result; 13.71 + 13.72 + size_t len = strlen(key); 13.73 + for (int i = 0; i <= len; ++i) 13.74 + { 13.75 + result = trie_search_children(curr, key[i]); 13.76 + if (NULL == result) 13.77 + { 13.78 + // current char is not in the trie yet, allocate a new node and attach it to the children 13.79 + struct trie_node * new = malloc(sizeof(struct trie_node)); 13.80 + if (NULL == new) 13.81 + return NULL; 13.82 + new->key = tolower(key[i]); 13.83 + new->child = new->sibling = NULL; 13.84 + new->data = NULL; 13.85 + 13.86 + if (NULL == curr->child) 13.87 + curr->child = new; 13.88 + else 13.89 + { 13.90 + struct trie_node * p = curr->child; 13.91 + while (p->sibling) 13.92 + p = p->sibling; 13.93 + p->sibling = new; 13.94 + } 13.95 + 13.96 + curr = new; 13.97 + } 13.98 + else 13.99 + curr = result; 13.100 + } 13.101 + 13.102 + // At this point, curr is either pointing to a new \0 node with a NULL data pointer, 13.103 + // or an existing \0 node with a valid data pointer (in which case we were asked to "insert" 13.104 + // a key that was already present in the trie. 13.105 + // For now I am simply ignoring collisions. We will update the data. 13.106 + 13.107 + curr->data = data; 13.108 + return key; 13.109 + } 13.110 + 13.111 +//////////////////////////////////////////////////////////////////////////////// 13.112 +struct trie_node * 13.113 +trie_search_children(struct trie_node * node, char k) 13.114 + { 13.115 + struct trie_node * p = node->child; 13.116 + if (NULL == p) 13.117 + return NULL; 13.118 + 13.119 + while ( (NULL != p) && (p->key != tolower(k)) ) 13.120 + p = p->sibling; 13.121 + return p; 13.122 + } 13.123 + 13.124 +//////////////////////////////////////////////////////////////////////////////// 13.125 +void * 13.126 +trie_find(struct trie * trie, char * key) 13.127 + { 13.128 + if ( (NULL == trie) || (NULL == key) ) 13.129 + return NULL; 13.130 + 13.131 + struct trie_node * node = trie->root; 13.132 + size_t len = strlen(key); 13.133 + for (int i = 0; i <= len; i++) 13.134 + { 13.135 + node = trie_search_children(node, key[i]); 13.136 + if (NULL == node) 13.137 + return NULL; 13.138 + if ('\0' == key[i]) 13.139 + return node->data; 13.140 + } 13.141 + 13.142 + // Should never get here 13.143 + return NULL; 13.144 + } 13.145 + 13.146 +//////////////////////////////////////////////////////////////////////////////// 13.147 +void * 13.148 +trie_remove(struct trie * trie, char * key) 13.149 + { 13.150 + return NULL; 13.151 + } 13.152 + 13.153 +//////////////////////////////////////////////////////////////////////////////// 13.154 +void 13.155 +trie_walk_keys(struct trie * trie, void (*op)(char * k, void * d)) 13.156 + { 13.157 + if (NULL == trie) 13.158 + return; 13.159 + trie_visit_node(trie, trie->root, op, ""); 13.160 + } 13.161 + 13.162 +//////////////////////////////////////////////////////////////////////////////// 13.163 +void 13.164 +trie_visit_node(struct trie * trie, struct trie_node * node, void (*op)(char * k, void * d), char * key) 13.165 + { 13.166 + if ( (node->key == '\0') && (node != trie->root) ) 13.167 + op(key, node->data); 13.168 + else 13.169 + { 13.170 + size_t len = strlen(key); 13.171 + char * k = malloc(len+2); 13.172 + if (NULL == k) 13.173 + return; 13.174 + strcpy(k, key); 13.175 + k[len] = node->key; 13.176 + k[len+1] = '\0'; 13.177 + struct trie_node * p = node->child; 13.178 + while (NULL != p) 13.179 + { 13.180 + trie_visit_node(trie, p, op, k); 13.181 + p = p->sibling; 13.182 + } 13.183 + } 13.184 + } 13.185 + 13.186 +//////////////////////////////////////////////////////////////////////////////// 13.187 +void trie_dump_raw(struct trie * trie) 13.188 + { 13.189 + if (NULL == trie) 13.190 + return; 13.191 + 13.192 + int depth = -1; 13.193 + trie_node_dump_raw(trie->root, depth); 13.194 + } 13.195 + 13.196 +//////////////////////////////////////////////////////////////////////////////// 13.197 +void 13.198 +trie_node_dump_raw(struct trie_node * node, int depth) 13.199 + { 13.200 + for (int i=0; i < depth; i++) 13.201 + printf(" "); 13.202 + trie_print_node(node); 13.203 + if (node->child) 13.204 + trie_node_dump_raw(node->child, depth+1); 13.205 + if (NULL != node->sibling) 13.206 + trie_node_dump_raw(node->sibling, depth+1); 13.207 + } 13.208 + 13.209 +//////////////////////////////////////////////////////////////////////////////// 13.210 +void trie_dump(struct trie * trie) 13.211 + { 13.212 + if (NULL == trie) 13.213 + return; 13.214 + 13.215 + int depth = -1; 13.216 + trie_node_dump_preorder(trie, trie->root, depth); 13.217 + } 13.218 + 13.219 +//////////////////////////////////////////////////////////////////////////////// 13.220 +void 13.221 +trie_node_dump_preorder(struct trie * trie, struct trie_node * node, int depth) 13.222 + { 13.223 + printf("%c", node->key); 13.224 + if ( (node != trie->root) && ('\0' == node->key) ) 13.225 + printf("\n"); 13.226 + if (node->child) 13.227 + trie_node_dump_preorder(trie, node->child, depth+1); 13.228 + if (NULL != node->sibling) 13.229 + { 13.230 + for (int i=0; i < depth; i++) 13.231 + printf(" "); 13.232 + trie_node_dump_preorder(trie, node->sibling, depth); 13.233 + } 13.234 + } 13.235 + 13.236 +//////////////////////////////////////////////////////////////////////////////// 13.237 +void 13.238 +trie_print_node(struct trie_node * node) 13.239 + { 13.240 + printf("%p\tchild %p\tsibling %p\tkey %c\tdata %p\n", node, node->child, node->sibling, node->key, node->data); 13.241 + }
14.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000 14.2 +++ b/src/trie.h Mon Oct 01 15:50:30 2012 -0500 14.3 @@ -0,0 +1,18 @@ 14.4 +#ifndef TRIE_H_ 14.5 +#define TRIE_H_ 14.6 + 14.7 +struct trie; 14.8 + 14.9 +struct trie * trie_new(); 14.10 +void trie_delete(struct trie * trie); 14.11 + 14.12 +char * trie_insert(struct trie * trie, char * key, void * data); 14.13 +void * trie_find(struct trie * trie, char * key); 14.14 +void * trie_remove(struct trie * trie, char * key); 14.15 + 14.16 +void trie_walk_keys(struct trie * trie, void (*op)(char * k, void * d) ); 14.17 + 14.18 +void trie_dump(struct trie * trie); 14.19 +void trie_dump_raw(struct trie * trie); 14.20 + 14.21 +#endif
15.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000 15.2 +++ b/src/trie_test.c Mon Oct 01 15:50:30 2012 -0500 15.3 @@ -0,0 +1,47 @@ 15.4 +#include <stdio.h> 15.5 +#include <stdlib.h> 15.6 + 15.7 +#include "trie.h" 15.8 + 15.9 +void print_val(char * key, void * data) 15.10 + { 15.11 + printf("%s\n", key); 15.12 + } 15.13 + 15.14 +int main(int argc, char ** argv) 15.15 + { 15.16 + struct trie * trie = trie_new(); 15.17 + 15.18 + char * words[] = { "hello", "interjection (used to express a greeting, answer a telephone, or attract attention.)", 15.19 + "help", "to give or provide what is necessary to accomplish a task or satisfy a need.", 15.20 + "helper", "a person or thing that helps or gives assistance, support, etc", 15.21 + "helping", "the act of a person or thing that helps.", 15.22 + "a", "indefinite article. Used before an initial consonant sound.", 15.23 + "an", "indefinite article. the form of a before an initial vowel sound.", 15.24 + "anna", "a female name", 15.25 + "anne", "a female name", 15.26 + "any", "one, a, an, or some; one or more without specification or identification", 15.27 + "anyway", "in any case; anyhow; nonetheless; regardless", 15.28 + "anyhow", "in any way whatever", 15.29 + "anybody", "any person", 15.30 + "Apple", "A computer manufacturer.", 15.31 + "ABLE", "having necessary power, skill, resources, or qualifications", 15.32 + NULL, NULL 15.33 + }; 15.34 + int i = 0; 15.35 + while (words[i]) 15.36 + { 15.37 + trie_insert(trie, words[i], words[i+1]); 15.38 + i += 2; 15.39 + } 15.40 + 15.41 + trie_dump(trie); 15.42 + 15.43 + void * data = trie_find(trie, "any"); 15.44 + if (NULL == data) 15.45 + printf("Failed to find 'any'\n"); 15.46 + else 15.47 + printf("any: %s\n", (char *) data); 15.48 + 15.49 + exit(EXIT_SUCCESS); 15.50 + }