# HG changeset patch # User Eris Caffee # Date 1349124630 18000 # Node ID d359966ed8def853c8d792acbd123195754b293d # Parent 8b09943f1a70c81cf9acb2d85b7d727f18db835c Added trie diff -r 8b09943f1a70 -r d359966ed8de CMakeLists.txt --- a/CMakeLists.txt Fri Sep 28 19:37:10 2012 -0500 +++ b/CMakeLists.txt Mon Oct 01 15:50:30 2012 -0500 @@ -42,42 +42,64 @@ ################################################################################ -set (stack_SRCS src/stack.h src/stack.c src/stack_test.c) +set (stack_SRCS src/stack.h src/stack.c) add_executable (stack_test + src/stack_test.c ${stack_SRCS} ) -set (ring_buffer_SRCS src/ring_buffer.h src/ring_buffer.c src/ring_buffer_test.c) +set (ring_buffer_SRCS src/ring_buffer.h src/ring_buffer.c) add_executable (ring_buffer_test + src/ring_buffer_test.c ${ring_buffer_SRCS} ) -set (queue_SRCS src/queue.h src/queue.c src/queue_test.c) +set (queue_SRCS src/queue.h src/queue.c) add_executable (queue_test + src/queue_test.c ${queue_SRCS} ) -set (dequeue_SRCS src/dequeue.h src/dequeue.c src/dequeue_test.c) +set (dequeue_SRCS src/dequeue.h src/dequeue.c) add_executable (dequeue_test + src/dequeue_test.c ${dequeue_SRCS} ) -set (pqueue_SRCS src/pqueue.h src/pqueue.c src/pqueue_test.c) +set (pqueue_SRCS src/pqueue.h src/pqueue.c) add_executable (pqueue_test + src/pqueue_test.c ${pqueue_SRCS} ) -set (list_SRCS src/list.h src/list.c src/list_test.c) +set (list_SRCS src/list.h src/list.c) add_executable (list_test + src/list_test.c ${list_SRCS} ) -set (bst_SRCS src/bst.h src/bst.c src/bst_test.c) +set (bst_SRCS src/bst.h src/bst.c) add_executable (bst_test + src/bst_test.c ${bst_SRCS} ) -set (rbtree_SRCS src/rbtree.h src/rbtree.c src/rbtree_test.c) +set (rbtree_SRCS src/rbtree.h src/rbtree.c) add_executable (rbtree_test + src/rbtree_test.c ${rbtree_SRCS} + ${queue_SRCS} ) +target_link_libraries(rbtree_test m) + +set (ost_SRCS src/ost.h src/ost.c) +add_executable (ost_test + src/ost_test.c + ${ost_SRCS} + ) + +set (trie_SRCS src/trie.h src/trie.c) +add_executable (trie_test + src/trie_test.c + ${trie_SRCS} + ) diff -r 8b09943f1a70 -r d359966ed8de README --- a/README Fri Sep 28 19:37:10 2012 -0500 +++ b/README Mon Oct 01 15:50:30 2012 -0500 @@ -1,1 +1,30 @@ -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. +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. + +To build the test programs, run these commands from the top directory of the source tree: + +mkdir build +cd build +cmake .. +make + + +Included structures: + +Doubly linked list + list.h list.c list_test.c +Stack + stack.h stack.c stack_test.c +Ring buffer + ring_buffer.h ring_buffer.c ring_buffer_test.c +Queue + queue.h queue.c queue_test.c +Double ended queue + dequeue.h dequeue.c dequeue_test.c +Priority queue + pqueue.h pqueue.c pqueue_test.c +Binary search tree + bst.h bst.c bst_test.c +Red-black tree + rbtree.h rbtree.c rbtrree_test.c +Order statistic tree + ost.h ost.c ost_test.c diff -r 8b09943f1a70 -r d359966ed8de src/bst.c --- a/src/bst.c Fri Sep 28 19:37:10 2012 -0500 +++ b/src/bst.c Mon Oct 01 15:50:30 2012 -0500 @@ -40,7 +40,6 @@ struct bst_node * bst_node_search(struct bst * bst, struct bst_node * node, void * data); struct bst_node * bst_transplant(struct bst * bst, struct bst_node * a, struct bst_node * b); -void bst_dump(struct bst * bst, void (*print_val)(void *) ); void bst_node_dump_preorder(struct bst * bst, struct bst_node * node, void (*print_val)(void *), int depth); //////////////////////////////////////////////////////////////////////////////// @@ -420,7 +419,7 @@ struct bst_node * bst_transplant(struct bst * bst, struct bst_node * a, struct bst_node * b) { - if ( (NULL == a) || (NULL == b) ) + if (NULL == a) return NULL; if (NULL == a->parent) @@ -443,22 +442,24 @@ if ( (NULL == it) || (NULL == it->curr) ) return NULL; - struct bst_node * y; + // Get successor and save it + struct bst_iterator succ; + succ.curr = it->curr; + succ.bst = it->bst; + bst_next(&succ); if (NULL == it->curr->left) { bst_transplant(it->bst, it->curr, it->curr->right); - y = it->curr->right; } else if (NULL == it->curr->right) { bst_transplant(it->bst, it->curr, it->curr->left); - y = it->curr->left; } else { - y = bst_node_minimum(it->curr->right); - if (NULL != y->parent) + struct bst_node * y = bst_node_minimum(it->curr->right); + if (y->parent != it->curr) { bst_transplant(it->bst, y, y->right); y->right = it->curr->right; @@ -470,8 +471,16 @@ } void * data = it->curr->data; + it->curr->data = NULL; + it->curr->left = NULL; + it->curr->right = NULL; + it->curr->parent = NULL; free(it->curr); - it->curr = y; + + // Update it to point to saved successor + it->curr = succ.curr; + it->bst->size--; + return data; } @@ -479,6 +488,9 @@ void bst_dump(struct bst * bst, void (*print_val)(void *) ) { + if ( (NULL == bst) || (NULL == bst->root) ) + return; + bst_node_dump_preorder(bst, bst->root, print_val, 0); } @@ -495,3 +507,13 @@ if (NULL != node->right) bst_node_dump_preorder(bst, node->right, print_val, depth+1); } + +//////////////////////////////////////////////////////////////////////////////// +unsigned int +bst_size (struct bst * bst) + { + if (NULL == bst) + return 0; + return bst->size; + } + diff -r 8b09943f1a70 -r d359966ed8de src/bst.h --- a/src/bst.h Fri Sep 28 19:37:10 2012 -0500 +++ b/src/bst.h Mon Oct 01 15:50:30 2012 -0500 @@ -4,7 +4,6 @@ #include #include -struct bst_node; struct bst; struct bst_iterator; @@ -16,6 +15,7 @@ void * bst_search_iterative (struct bst * bst, void * data); void * bst_minimum (struct bst * bst); void * bst_maximum (struct bst * bst); +unsigned int bst_size (struct bst * bst); void bst_walk_inorder (struct bst * bst, void (*op)(void * data)); void bst_walk_preorder (struct bst * bst, void (*op)(void * data)); diff -r 8b09943f1a70 -r d359966ed8de src/bst_test.c --- a/src/bst_test.c Fri Sep 28 19:37:10 2012 -0500 +++ b/src/bst_test.c Mon Oct 01 15:50:30 2012 -0500 @@ -5,7 +5,7 @@ #include "bst.h" -#define MAX_NUMS 20 +#define MAX_NUMS 10 void print_val(void * data) { @@ -168,11 +168,23 @@ printf("%d\n", *((int *) bst_value(it))); while (bst_next(it)); free(it); + printf("=================\n"); + bst_dump(bst, print_val); + printf("=================\n"); //////////////////////////////////////// - bst_walk_inorder(bst, free_data); + it = bst_begin(bst); + while (d = bst_remove(it)) + { + printf("removed %d\n", *((int *) d)); + free(d); + } + free(it); + printf("After deletion the size is %d\n", bst_size(bst)); + bst_dump(bst, print_val); + bst_delete(bst); exit(EXIT_SUCCESS); diff -r 8b09943f1a70 -r d359966ed8de src/list.h --- a/src/list.h Fri Sep 28 19:37:10 2012 -0500 +++ b/src/list.h Mon Oct 01 15:50:30 2012 -0500 @@ -3,7 +3,6 @@ #include -struct list_node; struct list; struct list_iterator; diff -r 8b09943f1a70 -r d359966ed8de src/ost.c --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/ost.c Mon Oct 01 15:50:30 2012 -0500 @@ -0,0 +1,831 @@ +// Implemented as a red-black tree + +#include +#include + +#include "ost.h" + +enum ost_color { RED, BLACK }; + +struct ost_node + { + enum ost_color color; + unsigned int size; + struct ost_node * parent; + struct ost_node * left; + struct ost_node * right; + void * data; + }; + +struct ost + { + struct ost_node nil_node; + struct ost_node * nil; + struct ost_node * root; + size_t size; + bool (*le)(void * a, void * b); + bool (*eq)(void * a, void * b); + }; + +struct ost_iterator + { + struct ost * ost; + struct ost_node * curr; + }; + +void * ost_data_search (struct ost * ost, struct ost_node * node, void * data); +void * ost_node_minimum (struct ost * ost, struct ost_node * node); +void * ost_node_maximum (struct ost * ost, struct ost_node * node); + +void ost_data_walk_inorder (struct ost * ost, struct ost_node * node, void (*op)(void * data)); +void ost_data_walk_preorder (struct ost * ost, struct ost_node * node, void (*op)(void * data)); +void ost_data_walk_postorder (struct ost * ost, struct ost_node * node, void (*op)(void * data)); +void ost_node_walk_postorder (struct ost * ost, struct ost_node * node, void (*op)(struct ost_node * n)); + +void ost_node_free (struct ost_node * node); + +struct ost_node * ost_node_search (struct ost * ost, struct ost_node * node, void * data); + +struct ost_node * ost_transplant (struct ost * ost, struct ost_node * a, struct ost_node * b); +void ost_rotate_left (struct ost * ost, struct ost_node * node); +void ost_rotate_right (struct ost * ost, struct ost_node * node); +void ost_insert_fixup (struct ost * ost, struct ost_node * node); +void ost_remove_fixup (struct ost * ost, struct ost_node * node); + +void ost_node_dump_preorder(struct ost * ost, struct ost_node * node, void (*print_val)(void *), int depth); + +//////////////////////////////////////////////////////////////////////////////// +struct ost * +ost_new(bool (*le)(void * a, void * b), + bool (*eq)(void * a, void * b)) + { + if ( (NULL == le) || (NULL == eq) ) + return NULL; + + struct ost * ost = malloc(sizeof(struct ost)); + if (NULL == ost) + return NULL; + + ost->nil_node = (struct ost_node) { BLACK, 0, &ost->nil_node, &ost->nil_node, &ost->nil_node, NULL }; + ost->nil = &(ost->nil_node); + ost->root = ost->nil; + ost->size = 0; + ost->le = le; + ost->eq = eq; + return ost; + } + + +//////////////////////////////////////////////////////////////////////////////// +void +ost_delete(struct ost * ost) + { + if (NULL == ost) return; + if (0 < ost->size) + { + // Walk the tree and delete the nodes. + // This may cause memory leaks, so hopefully the user has already + // emptied the tree. + ost_node_walk_postorder(ost, ost->root, ost_node_free); + } + free(ost); + } + +//////////////////////////////////////////////////////////////////////////////// +void +ost_node_free(struct ost_node * node) + { + free(node); + } + +//////////////////////////////////////////////////////////////////////////////// +void * +ost_insert(struct ost * ost, void * data) + { + if ( (NULL == ost) || (NULL == data) ) + return NULL; + + struct ost_node * new = malloc(sizeof(struct ost_node)); + if (NULL == new) + return NULL; + new->left = new->right = new->parent = ost->nil; + new->color = RED; + new->size = 1; + new->data = data; + + if (ost->nil == ost->root) + { + ost->root = new; + new->color = BLACK; + new->parent = ost->nil; + ost->size = 1; + return new->data; + } + + struct ost_node * p = ost->nil; + struct ost_node * c = ost->root; + + while (ost->nil != c) + { + c->size++; + p = c; + if (ost->le(new->data, c->data)) + c = c->left; + else + c = c->right; + } + new->parent = p; + if (ost->le(new->data, p->data)) + p->left = new; + else + p->right = new; + + ost_insert_fixup(ost, new); + + ost->size++; + return new->data; + } + +//////////////////////////////////////////////////////////////////////////////// +void +ost_insert_fixup(struct ost * ost, struct ost_node * node) + { + if ( (NULL == ost) || (NULL == node) ) + return; + + while (RED == node->parent->color) + { + if (node->parent == node->parent->parent->left) + { + struct ost_node * y = node->parent->parent->right; + if (RED == y->color) + { + node->parent->color = BLACK; + y->color = BLACK; + node->parent->parent->color = RED; + node = node->parent->parent; + } + else + { + if (node == node->parent->right) + { + node = node->parent; + ost_rotate_left(ost, node); + } + node->parent->color = BLACK; + node->parent->parent->color = RED; + ost_rotate_right(ost, node->parent->parent); + } + } + else + { + struct ost_node * y = node->parent->parent->left; + if (RED == y->color) + { + node->parent->color = BLACK; + y->color = BLACK; + node->parent->parent->color = RED; + node = node->parent->parent; + } + else + { + if (node == node->parent->left) + { + node = node->parent; + ost_rotate_right(ost, node); + } + node->parent->color = BLACK; + node->parent->parent->color = RED; + ost_rotate_left(ost, node->parent->parent); + } + } + } + ost->root->color = BLACK; + } + +//////////////////////////////////////////////////////////////////////////////// +void +ost_walk_inorder(struct ost * ost, void (*op)(void * data)) + { + if ( (NULL == ost) || (ost->nil == ost->root) || (NULL == op) ) + return; + + ost_data_walk_inorder(ost, ost->root, op); + } + +//////////////////////////////////////////////////////////////////////////////// +void +ost_walk_postorder(struct ost * ost, void (*op)(void * data)) + { + if ( (NULL == ost) || (ost->nil == ost->root) || (NULL == op) ) + return; + + ost_data_walk_postorder(ost, ost->root, op); + } + +//////////////////////////////////////////////////////////////////////////////// +void +ost_walk_preorder(struct ost * ost, void (*op)(void * data)) + { + if ( (NULL == ost) || (ost->nil == ost->root) || (NULL == op) ) + return; + + ost_data_walk_preorder(ost, ost->root, op); + } + +//////////////////////////////////////////////////////////////////////////////// +void +ost_data_walk_inorder(struct ost * ost, struct ost_node * node, void (*op)(void * data)) + { + if (ost->nil != node) + { + ost_data_walk_inorder(ost, node->left, op); + op(node->data); + ost_data_walk_inorder(ost, node->right, op); + } + } + +//////////////////////////////////////////////////////////////////////////////// +void +ost_data_walk_postorder(struct ost * ost, struct ost_node * node, void (*op)(void * data)) + { + if (ost->nil != node) + { + ost_data_walk_postorder(ost, node->left, op); + ost_data_walk_postorder(ost, node->right, op); + op(node->data); + } + } + +//////////////////////////////////////////////////////////////////////////////// +void +ost_data_walk_preorder(struct ost * ost, struct ost_node * node, void (*op)(void * data)) + { + if (ost->nil != node) + { + op(node->data); + ost_data_walk_preorder(ost, node->left, op); + ost_data_walk_preorder(ost, node->right, op); + } + } + +//////////////////////////////////////////////////////////////////////////////// +void +ost_node_walk_postorder(struct ost * ost, struct ost_node * node, void (*op)(struct ost_node * n)) + { + if (ost->nil != node) + { + ost_node_walk_postorder(ost, node->left, op); + ost_node_walk_postorder(ost, node->right, op); + op(node); + } + } + +//////////////////////////////////////////////////////////////////////////////// +void * +ost_search(struct ost * ost, void * data) + { + if ( (NULL == ost) || (ost->nil == ost->root) || (NULL == data) ) + return NULL; + + return ost_data_search(ost, ost->root, data); + } + +//////////////////////////////////////////////////////////////////////////////// +// Recursive +void * +ost_data_search(struct ost * ost, struct ost_node * node, void * data) + { + if (ost->nil == node) + return NULL; + + if (ost->eq(data, node->data)) + return node->data; + + if (ost->le(data, node->data)) + return ost_data_search(ost, node->left, data); + else + return ost_data_search(ost, node->right, data); + } + +//////////////////////////////////////////////////////////////////////////////// +// Iterative +void * +ost_search_iterative(struct ost * ost, void * data) + { + if ( (NULL == ost) || (ost->nil == ost->root) || (NULL == data) ) + return NULL; + + struct ost_node * node = ost->root; + while (1) + { + if (ost->nil == node) + return NULL; + + if (ost->eq(data, node->data)) + return node->data; + + if (ost->le(data, node->data)) + node = node->left; + else + node = node->right; + } + } + +//////////////////////////////////////////////////////////////////////////////// +void * +ost_minimum(struct ost * ost) + { + if (NULL == ost) + return NULL; + + return ost_node_minimum(ost, ost->root); + } + +//////////////////////////////////////////////////////////////////////////////// +void * +ost_node_minimum(struct ost * ost, struct ost_node * node) + { + while ( (ost->nil != node) && (ost->nil != node->left) ) + node = node->left; + if (ost->nil == node) + return NULL; + return node->data; + } + +//////////////////////////////////////////////////////////////////////////////// +void * +ost_maximum(struct ost * ost) + { + if (NULL == ost) + return NULL; + + return ost_node_maximum(ost, ost->root); + } + +//////////////////////////////////////////////////////////////////////////////// +void * +ost_node_maximum(struct ost * ost, struct ost_node * node) + { + while ( (ost->nil != node) && (ost->nil != node->right) ) + node = node->right; + if (ost->nil == node) + return NULL; + return node->data; + } + +//////////////////////////////////////////////////////////////////////////////// +struct ost_iterator * +ost_begin(struct ost * ost) + { + if ( (NULL == ost) || (ost->nil == ost->root) ) + return NULL; + + struct ost_node * min = ost->root; + while (ost->nil != min->left) + min = min->left; + + struct ost_iterator * it = malloc(sizeof(struct ost_iterator)); + if (NULL == it) + return NULL; + + it->ost = ost; + it->curr = min; + return it; + } + +//////////////////////////////////////////////////////////////////////////////// +struct ost_iterator * +ost_end(struct ost * ost) + { + if ( (NULL == ost) || (ost->nil == ost->root) ) + return NULL; + + struct ost_node * max = ost->root; + while (ost->nil != max->right) + max = max->right; + + struct ost_iterator * it = malloc(sizeof(struct ost_iterator)); + if (NULL == it) + return NULL; + + it->ost = ost; + it->curr = max; + return it; + } + +//////////////////////////////////////////////////////////////////////////////// +struct ost_iterator * +ost_next(struct ost_iterator * it) + { + if ( (NULL == it) || (NULL == it->ost) || (it->ost->nil == it->curr) ) + return NULL; + + if (it->ost->nil == it->curr->right) + { + struct ost_node * p = it->curr; + it->curr = it->curr->parent; + while ( (it->ost->nil != it->curr) && (p == it->curr->right) ) + { + p = it->curr; + it->curr = it->curr->parent; + } + + if (it->curr == it->ost->nil) + return NULL; + } + else + { + struct ost_node * min = it->curr->right; + while (it->ost->nil != min->left) + min = min->left; + it->curr = min; + } + return it; + } + +//////////////////////////////////////////////////////////////////////////////// +struct ost_iterator * +ost_prev(struct ost_iterator * it) + { + if ( (NULL == it) || (NULL == it->ost) || (it->ost->nil == it->curr) ) + return NULL; + + if (it->ost->nil == it->curr->left) + { + struct ost_node * p = it->curr; + it->curr = it->curr->parent; + while ( (it->ost->nil != it->curr) && (p == it->curr->left) ) + { + p = it->curr; + it->curr = it->curr->parent; + } + + if (it->curr == it->ost->nil) + return NULL; + } + else + { + struct ost_node * max = it->curr->left; + while (it->ost->nil != max->right) + max = max->right; + it->curr = max; + } + return it; + } + +//////////////////////////////////////////////////////////////////////////////// +void * +ost_value(struct ost_iterator * it) + { + if ( (NULL == it) || (NULL == it->ost) || (it->ost->nil == it->curr) ) + return NULL; + + return it->curr->data; + } + +//////////////////////////////////////////////////////////////////////////////// +void * +ost_find(struct ost_iterator * it, void * data) + { + if ( (NULL == it) || (NULL == it->ost) || (it->ost->nil == it->ost->root) || (NULL == data) ) + return NULL; + + return ost_node_search(it->ost, it->ost->root, data); + } + +//////////////////////////////////////////////////////////////////////////////// +// Recursive +struct ost_node * +ost_node_search(struct ost * ost, struct ost_node * node, void * data) + { + if (ost->nil == node) + return NULL; + + if (ost->eq(data, node->data)) + return node; + + if (ost->le(data, node->data)) + return ost_node_search(ost, node->left, data); + else + return ost_node_search(ost, node->right, data); + } + +//////////////////////////////////////////////////////////////////////////////// +struct ost_node * +ost_transplant(struct ost * ost, struct ost_node * a, struct ost_node * b) + { + if ( (NULL == a) || (NULL == b) ) + return NULL; + + if (ost->nil == a->parent) + ost->root = b; + else if (a == a->parent->left) + a->parent->left = b; + else + a->parent->right = b; + + b->parent = a->parent; + + return a; + } + +//////////////////////////////////////////////////////////////////////////////// +void * +ost_remove(struct ost_iterator * it) + { + if ( (NULL == it) || (NULL == it->ost) || (it->ost->nil == it->curr) ) + return NULL; + + // Get successor and save it + struct ost_iterator succ; + succ.curr = it->curr; + succ.ost = it->ost; + ost_next(&succ); + + struct ost_node * x; + struct ost_node * y = it->curr; + enum ost_color original_color = y->color; + + if (it->ost->nil == it->curr->left) + { + x = it->curr->right; + ost_transplant(it->ost, it->curr, it->curr->right); + } + else if (it->ost->nil == it->curr->right) + { + x = it->curr->left; + ost_transplant(it->ost, it->curr, it->curr->left); + } + else + { + y = ost_node_minimum(it->ost, it->curr->right); + original_color = y->color; + x = y->right; + if (it->curr == y->parent) + x->parent = y; + else + { + ost_transplant(it->ost, y, y->right); + y->right = it->curr->right; + y->right->parent = y; + } + ost_transplant(it->ost, it->curr, y); + y->left = it->curr->left; + y->left->parent = y; + y->color = it->curr->color; + } + + if (BLACK == original_color) + ost_remove_fixup(it->ost, x); + + void * data = it->curr->data; + free(it->curr); + + // Update it to point to saved successor + it->curr = succ.curr; + it->ost->size--; + + return data; + } + +//////////////////////////////////////////////////////////////////////////////// +void +ost_remove_fixup(struct ost * ost, struct ost_node * node) + { + while ( (ost->root != node) && (BLACK == node->color) ) + { + if (node == node->parent->left) + { + struct ost_node * w = node->parent->right; + if (RED == w->color) + { + w->color = BLACK; + node->parent->color = RED; + ost_rotate_left(ost, node->parent); + w = node->parent->right; + } + if ( (BLACK == w->left->color) && (BLACK == w->right->color) ) + { + w->left->color = RED; + node = node->parent; + } + else + { + if (BLACK == w->right->color) + { + w->left->color = BLACK; + w->color = RED; + ost_rotate_right(ost, w); + w = node->parent->right; + } + w->color = node->parent->color; + node->parent->color = BLACK; + w->right->color = BLACK; + ost_rotate_left(ost, node->parent); + node = ost->root; + } + } + else + { + struct ost_node * w = node->parent->left; + if (RED == w->color) + { + w->color = BLACK; + node->parent->color = RED; + ost_rotate_right(ost, node->parent); + w = node->parent->left; + } + if ( (BLACK == w->right->color) && (BLACK == w->left->color) ) + { + w->right->color = RED; + node = node->parent; + } + else + { + if (BLACK == w->left->color) + { + w->right->color = BLACK; + w->color = RED; + ost_rotate_left(ost, w); + w = node->parent->left; + } + w->color = node->parent->color; + node->parent->color = BLACK; + w->left->color = BLACK; + ost_rotate_right(ost, node->parent); + node = ost->root; + } + } + } + node->color = BLACK; + } + +//////////////////////////////////////////////////////////////////////////////// +void +ost_rotate_left(struct ost * ost, struct ost_node * node) + { + if ( (NULL == ost) || (ost->nil == node) || (ost->nil == node->right) ) + return; + + struct ost_node * y = node->right; + + node->right = y->left; + if (ost->nil != y->left) + y->left->parent = node; + + y->parent = node->parent; + if (ost->nil == node->parent) + ost->root = y; + else if (node == node->parent->left) + node->parent->left = y; + else + node->parent->right = y; + + y->left = node; + node->parent = y; + + y->size = node->size; + node->size = node->left->size + node->right->size + 1; + } + +//////////////////////////////////////////////////////////////////////////////// +void +ost_rotate_right(struct ost * ost, struct ost_node * node) + { + if ( (NULL == ost) || (ost->nil == node) || (ost->nil == node->left) ) + return; + + struct ost_node * y = node->left; + + node->left = y->right; + if (ost->nil != y->right) + y->right->parent = node; + + y->parent = node->parent; + if (ost->nil == node->parent) + ost->root = y; + else if (node == node->parent->right) + node->parent->right = y; + else + node->parent->left = y; + + y->right = node; + node->parent = y; + + y->size = node->size; + node->size = node->left->size + node->right->size + 1; + } + +//////////////////////////////////////////////////////////////////////////////// +unsigned int ost_black_depth(struct ost * ost) + { + if ( (NULL == ost) || (NULL == ost->root) ) + return 0; + + struct ost_node * node = ost->root; + unsigned int black_depth = 0; + + while (ost->nil != node) + { + if (BLACK == node->color) + black_depth++; + node = node->left; + } + + return black_depth; + } + +//////////////////////////////////////////////////////////////////////////////// +void +ost_dump(struct ost * ost, void (*print_val)(void *) ) + { + if ( (NULL == ost) || (ost->nil == ost->root) ) + return; + ost_node_dump_preorder(ost, ost->root, print_val, 0); + } + +//////////////////////////////////////////////////////////////////////////////// +void +ost_node_dump_preorder(struct ost * ost, struct ost_node * node, void (*print_val)(void *), int depth) + { + for (int i=0; i < depth; i++) + printf("\t"); + printf("%-8s", (BLACK == node->color ? "black" : "red")); + print_val(node->data); + printf("\n"); + if (ost->nil != node->left) + ost_node_dump_preorder(ost, node->left, print_val, depth+1); + if (ost->nil != node->right) + ost_node_dump_preorder(ost, node->right, print_val, depth+1); + } + +//////////////////////////////////////////////////////////////////////////////// +struct ost_iterator * +ost_select(struct ost * ost, unsigned int i) + { + if ( (NULL == ost) || (ost->nil == ost->root) ) + return NULL; + + struct ost_iterator * it = malloc(sizeof(struct ost_iterator)); + if (NULL == it) + return NULL; + + it->ost = ost; + it->curr = ost->root; + return ost_select_subtree(it, i); + } + +//////////////////////////////////////////////////////////////////////////////// +struct ost_iterator * +ost_select_subtree(struct ost_iterator * it, unsigned int i) + { + if ( (NULL == it) || (NULL == it->ost) ) + return NULL; + + unsigned int r = it->curr->left->size + 1; + if (i == r) + return it; + else + { + if (i < r) + { + it->curr = it->curr->left; + return ost_select_subtree(it, i); + } + else + { + it->curr = it->curr->right; + return ost_select_subtree(it, i - r); + } + } + return it; + } + +//////////////////////////////////////////////////////////////////////////////// +unsigned int +ost_rank(struct ost_iterator * it) + { + if ( (NULL == it) || (NULL == it->ost) ) + return 0; + + unsigned int r = it->curr->left->size + 1; + struct ost_node * y = it->curr; + while (y != it->ost->root) + { + if (y == y->parent->right) + r += y->parent->left->size + 1; + y = y->parent; + } + return r; + } + +//////////////////////////////////////////////////////////////////////////////// +unsigned int +ost_size (struct ost * ost) + { + if (NULL == ost) + return 0; + return ost->size; + } + diff -r 8b09943f1a70 -r d359966ed8de src/ost.h --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/ost.h Mon Oct 01 15:50:30 2012 -0500 @@ -0,0 +1,40 @@ +#ifndef OST_H_ +#define OST_H_ + +#include +#include + +struct ost; +struct ost_iterator; + +struct ost * ost_new(bool (*le)(void * a, void * b), bool (*eq)(void * a, void * b)); +void ost_delete(struct ost * ost); + +void * ost_insert (struct ost * ost, void * data); +void * ost_search (struct ost * ost, void * data); +void * ost_search_iterative (struct ost * ost, void * data); +void * ost_minimum (struct ost * ost); +void * ost_maximum (struct ost * ost); +unsigned int ost_size (struct ost * ost); + +void ost_walk_inorder (struct ost * ost, void (*op)(void * data)); +void ost_walk_preorder (struct ost * ost, void (*op)(void * data)); +void ost_walk_postorder (struct ost * ost, void (*op)(void * data)); + +struct ost_iterator * ost_begin (struct ost * ost); +struct ost_iterator * ost_end (struct ost * ost); +struct ost_iterator * ost_next (struct ost_iterator * it); +struct ost_iterator * ost_prev (struct ost_iterator * it); +void * ost_find (struct ost_iterator * it, void * data); +void * ost_remove (struct ost_iterator * it); +void * ost_value (struct ost_iterator * it); + +unsigned int ost_black_depth(struct ost * ost); +void ost_dump(struct ost * ost, void (*print_val)(void *) ); + +struct ost_iterator * ost_select(struct ost * ost, unsigned int i); +struct ost_iterator * ost_select_subtree(struct ost_iterator * it, unsigned int i); +unsigned int ost_rank(struct ost_iterator * it); + + +#endif diff -r 8b09943f1a70 -r d359966ed8de src/ost_test.c --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/ost_test.c Mon Oct 01 15:50:30 2012 -0500 @@ -0,0 +1,142 @@ +#include +#include +#include + +#include "ost.h" + +void print_val(void * data) + { + printf("%d", *((int *) data)); + } + +bool le(void * a, void * b) + { + return *((int *) a) <= *((int *) b); + } + +bool eq(void * a, void * b) + { + return *((int *) a) == *((int *) b); + } + +#define MAX_NUMS 10 + +int main (int argc, char ** argv) + { + int sorted[100] = { + 35005211, 42999170, 84353895, 135497281, 137806862, 149798315, 184803526, 233665123, 278722862, 294702567, + 304089172, 336465782, 356426808, 412776091, 424238335, 468703135, 491705403, 511702305, 521595368, 572660336, + 596516649, 608413784, 610515434, 628175011, 635723058, 709393584, 719885386, 749241873, 752392754, 756898537, + 760313750, 783368690, 805750846, 846930886, 855636226, 859484421, 861021530, 939819582, 943947739, 945117276, + 982906996, 1025202362, 1059961393, 1100661313, 1101513929, 1102520059, 1125898167, 1129566413, 1131176229, 1141616124, + 1159126505, 1189641421, 1264095060, 1303455736, 1315634022, 1350490027, 1365180540, 1369133069, 1374344043, 1411549676, + 1424268980, 1433925857, 1469348094, 1474612399, 1477171087, 1540383426, 1548233367, 1585990364, 1632621729, 1649760492, + 1653377373, 1656478042, 1681692777, 1714636915, 1726956429, 1734575198, 1749698586, 1780695788, 1801979802, 1804289383, + 1827336327, 1843993368, 1889947178, 1911759956, 1914544919, 1918502651, 1937477084, 1956297539, 1957747793, 1967513926, + 1973594324, 1984210012, 1998898814, 2001100545, 2038664370, 2044897763, 2053999932, 2084420925, 2089018456, 2145174067, + }; + + struct ost * ost = ost_new(le, eq); + if (NULL == ost) + { + perror("ost_new"); + exit(EXIT_FAILURE); + } + + for (int i = 0; i < MAX_NUMS; ++i) + { + int * ip = malloc(sizeof(int)); + if (NULL == ip) + { + perror("malloc"); + exit(EXIT_FAILURE); + } + *ip = rand(); + // Be sure to set MAX_NUMS = 100 if you want to use the sorted array + // *ip = sorted[i]; + int * ip2; + if (NULL == (ip2 = ost_insert(ost, ip))) + { + printf("ost_insert failed\n"); + free(ip); + } + printf("inserting %d\n", *ip2); + } + + + // print the tree structure + ost_dump(ost, print_val); + fprintf(stderr, "black depth is %u\n", ost_black_depth(ost)); + + // Print the tree in value order with their ranks + struct ost_iterator * it; + struct ost_iterator * next; + for (next = it = ost_begin(ost); NULL != next; next = ost_next(it)) + printf("%-16d%u\n", *((int *) ost_value(it)), ost_rank(it)); + free(it); + + + // Get the first 5th and 10th elements + it = ost_select(ost, 1); + if (NULL == it) + { + printf("ost_select failed\n"); + exit(EXIT_FAILURE); + } + printf("1st order statistic is %d\n", *((int *) ost_value(it))); + free(it); + + it = ost_select(ost, 5); + if (NULL == it) + { + printf("ost_select failed\n"); + exit(EXIT_FAILURE); + } + printf("5th order statistic is %d\n", *((int *) ost_value(it))); + free(it); + + it = ost_select(ost, 10); + if (NULL == it) + { + printf("ost_select failed\n"); + exit(EXIT_FAILURE); + } + printf("10th order statistic is %d\n", *((int *) ost_value(it))); + free(it); + + + // Free the whole tree + void * d; + it = ost_begin(ost); + while (d = ost_remove(it)) + { + printf("removed %d\n", *((int *) d)); + free(d); + } + free(it); + printf("After deletion the size is %u\n", ost_size(ost)); + ost_dump(ost, print_val); + + + + // This next should fail + it = ost_select(ost, 1); + if (NULL != it) + { + printf("ost_select failed\n"); + exit(EXIT_FAILURE); + } + + ost_delete(ost); + ost = NULL; + + // This next should fail + it = ost_select(ost, 1); + if (NULL != it) + { + printf("ost_select failed\n"); + exit(EXIT_FAILURE); + } + + exit(EXIT_SUCCESS); + } diff -r 8b09943f1a70 -r d359966ed8de src/rbtree.c --- a/src/rbtree.c Fri Sep 28 19:37:10 2012 -0500 +++ b/src/rbtree.c Mon Oct 01 15:50:30 2012 -0500 @@ -1,7 +1,9 @@ #include #include +#include #include "rbtree.h" +#include "queue.h" enum rbtree_color { RED, BLACK }; @@ -529,14 +531,14 @@ void * rbtree_remove(struct rbtree_iterator * it) { - if ( (NULL == it) || (NULL == it->curr) ) + if ( (NULL == it) || (NULL == it->rbtree) || (it->rbtree->nil == it->curr) ) return NULL; - // Get predecessor and save it - struct rbtree_iterator pred; - pred.curr = it->curr; - pred.rbtree = it->rbtree; - rbtree_prev(&pred); + // Get successor and save it + struct rbtree_iterator succ; + succ.curr = it->curr; + succ.rbtree = it->rbtree; + rbtree_next(&succ); struct rbtree_node * x; struct rbtree_node * y = it->curr; @@ -577,9 +579,9 @@ void * data = it->curr->data; free(it->curr); - // Update it to point to pred's successor - rbtree_next(&pred); - it->curr = pred.curr; + // Update it to point to saved successor + it->curr = succ.curr; + it->rbtree->size--; return data; } @@ -729,6 +731,9 @@ void rbtree_dump(struct rbtree * rbtree, void (*print_val)(void *) ) { + if ( (NULL == rbtree) || (rbtree->nil == rbtree->root) ) + return; + rbtree_node_dump_preorder(rbtree, rbtree->root, print_val, 0); } @@ -746,3 +751,44 @@ if (rbtree->nil != node->right) rbtree_node_dump_preorder(rbtree, node->right, print_val, depth+1); } + +//////////////////////////////////////////////////////////////////////////////// +unsigned int +rbtree_size (struct rbtree * rbtree) + { + if (NULL == rbtree) + return 0; + return rbtree->size; + } + +//////////////////////////////////////////////////////////////////////////////// +void +rbtree_walk_breadth_first (struct rbtree * rbtree, void (*op)(void * data)) + { + if ( (NULL == rbtree) || (NULL == op) ) + return; + + if (0 == rbtree->size) + return; + + // Should really use a dynamically sized queue here. + struct queue * q = queue_new(rbtree->size); + if (NULL == q) + return; + + queue_push(q, rbtree->root); + + struct rbtree_node * node; + + while (node = queue_pop(q)) + { + if (rbtree->nil != node->left) + queue_push(q, node->left); + if (rbtree->nil != node->right) + queue_push(q, node->right); + op(node->data); + } + + queue_delete(q); + } + diff -r 8b09943f1a70 -r d359966ed8de src/rbtree.h --- a/src/rbtree.h Fri Sep 28 19:37:10 2012 -0500 +++ b/src/rbtree.h Mon Oct 01 15:50:30 2012 -0500 @@ -5,7 +5,6 @@ #include struct rbtree; -struct rbtree_node; struct rbtree_iterator; struct rbtree * rbtree_new(bool (*le)(void * a, void * b), bool (*eq)(void * a, void * b)); @@ -16,10 +15,12 @@ void * rbtree_search_iterative (struct rbtree * rbtree, void * data); void * rbtree_minimum (struct rbtree * rbtree); void * rbtree_maximum (struct rbtree * rbtree); +unsigned int rbtree_size (struct rbtree * rbtree); void rbtree_walk_inorder (struct rbtree * rbtree, void (*op)(void * data)); void rbtree_walk_preorder (struct rbtree * rbtree, void (*op)(void * data)); void rbtree_walk_postorder (struct rbtree * rbtree, void (*op)(void * data)); +void rbtree_walk_breadth_first (struct rbtree * rbtree, void (*op)(void * data)); struct rbtree_iterator * rbtree_begin (struct rbtree * rbtree); struct rbtree_iterator * rbtree_end (struct rbtree * rbtree); diff -r 8b09943f1a70 -r d359966ed8de src/rbtree_test.c --- a/src/rbtree_test.c Fri Sep 28 19:37:10 2012 -0500 +++ b/src/rbtree_test.c Mon Oct 01 15:50:30 2012 -0500 @@ -9,6 +9,11 @@ printf("%d", *((int *) data)); } +void print_val2(void * data) + { + printf("%d\n", *((int *) data)); + } + bool le(void * a, void * b) { return *((int *) a) <= *((int *) b); @@ -19,7 +24,7 @@ return *((int *) a) == *((int *) b); } -#define MAX_NUMS 100 +#define MAX_NUMS 128 int main (int argc, char ** argv) { @@ -75,14 +80,62 @@ printf("%d\n", *((int *) rbtree_value(it))); free(it); + // Free the whole tree + void * d; + it = rbtree_begin(rbtree); + while (d = rbtree_remove(it)) + { + printf("removed %d\n", *((int *) d)); + free(d); + } + free(it); + printf("After deletion the size is %u\n", rbtree_size(rbtree)); + rbtree_dump(rbtree, print_val); - // Free the whole tree - for (next = it = rbtree_begin(rbtree); NULL != next; next = rbtree_next(it)) - free(rbtree_value(it)); - free(it); rbtree_delete(rbtree); + + ////////////////////////////////////////// + // New tree to test beadth first walk + + printf("Walking a tree breadth first\n"); + rbtree = rbtree_new(le, eq); + if (NULL == rbtree) + { + perror("rbtree_new"); + exit(EXIT_FAILURE); + } + + for (int i = 0; i < 10; ++i) + { + int * ip = malloc(sizeof(int)); + if (NULL == ip) + { + perror("malloc"); + exit(EXIT_FAILURE); + } + *ip = rand(); + int * ip2; + if (NULL == (ip2 = rbtree_insert(rbtree, ip))) + { + printf("rbtree_insert failed\n"); + free(ip); + } + } + + + // print the tree structure + rbtree_dump(rbtree, print_val); + rbtree_walk_breadth_first(rbtree, print_val2); + + // Free the whole tree + it = rbtree_begin(rbtree); + while (d = rbtree_remove(it)) + free(d); + free(it); + rbtree_delete(rbtree); + exit(EXIT_SUCCESS); } diff -r 8b09943f1a70 -r d359966ed8de src/trie.c --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/trie.c Mon Oct 01 15:50:30 2012 -0500 @@ -0,0 +1,238 @@ +#include +#include +#include +#include + + +#include + + +struct trie_node + { + char key; + struct trie_node * child; + struct trie_node * sibling; + void * data; + }; + +struct trie + { + struct trie_node * root; + }; + +struct trie_node * trie_search_children(struct trie_node * node, char k); +void trie_visit_node(struct trie * trie, struct trie_node * node, void (*op)(char * k, void * d), char * key); +void trie_print_node(struct trie_node * node); +void trie_print_node(struct trie_node * node); +void trie_node_dump_preorder(struct trie * trie, struct trie_node * node, int depth); +void trie_node_dump_raw(struct trie_node * node, int depth); + +//////////////////////////////////////////////////////////////////////////////// +struct trie * +trie_new() + { + struct trie * trie = malloc(sizeof(struct trie)); + if (NULL == trie) + return NULL; + + trie->root = malloc(sizeof(struct trie_node)); + if (NULL == trie->root) + return NULL; + + trie->root->child = trie->root->sibling = NULL; + trie->root->key = '\0'; + trie->root->data = NULL; + + return trie; + } + +//////////////////////////////////////////////////////////////////////////////// +void +trie_delete(struct trie * trie) + { + if (NULL == trie) + return; + + free(trie); + } + +//////////////////////////////////////////////////////////////////////////////// +char * +trie_insert(struct trie * trie, char * key, void * data) + { + if ( (NULL == trie) || (NULL == key) ) + return NULL; + + struct trie_node * curr = trie->root; + struct trie_node * result; + + size_t len = strlen(key); + for (int i = 0; i <= len; ++i) + { + result = trie_search_children(curr, key[i]); + if (NULL == result) + { + // current char is not in the trie yet, allocate a new node and attach it to the children + struct trie_node * new = malloc(sizeof(struct trie_node)); + if (NULL == new) + return NULL; + new->key = tolower(key[i]); + new->child = new->sibling = NULL; + new->data = NULL; + + if (NULL == curr->child) + curr->child = new; + else + { + struct trie_node * p = curr->child; + while (p->sibling) + p = p->sibling; + p->sibling = new; + } + + curr = new; + } + else + curr = result; + } + + // At this point, curr is either pointing to a new \0 node with a NULL data pointer, + // or an existing \0 node with a valid data pointer (in which case we were asked to "insert" + // a key that was already present in the trie. + // For now I am simply ignoring collisions. We will update the data. + + curr->data = data; + return key; + } + +//////////////////////////////////////////////////////////////////////////////// +struct trie_node * +trie_search_children(struct trie_node * node, char k) + { + struct trie_node * p = node->child; + if (NULL == p) + return NULL; + + while ( (NULL != p) && (p->key != tolower(k)) ) + p = p->sibling; + return p; + } + +//////////////////////////////////////////////////////////////////////////////// +void * +trie_find(struct trie * trie, char * key) + { + if ( (NULL == trie) || (NULL == key) ) + return NULL; + + struct trie_node * node = trie->root; + size_t len = strlen(key); + for (int i = 0; i <= len; i++) + { + node = trie_search_children(node, key[i]); + if (NULL == node) + return NULL; + if ('\0' == key[i]) + return node->data; + } + + // Should never get here + return NULL; + } + +//////////////////////////////////////////////////////////////////////////////// +void * +trie_remove(struct trie * trie, char * key) + { + return NULL; + } + +//////////////////////////////////////////////////////////////////////////////// +void +trie_walk_keys(struct trie * trie, void (*op)(char * k, void * d)) + { + if (NULL == trie) + return; + trie_visit_node(trie, trie->root, op, ""); + } + +//////////////////////////////////////////////////////////////////////////////// +void +trie_visit_node(struct trie * trie, struct trie_node * node, void (*op)(char * k, void * d), char * key) + { + if ( (node->key == '\0') && (node != trie->root) ) + op(key, node->data); + else + { + size_t len = strlen(key); + char * k = malloc(len+2); + if (NULL == k) + return; + strcpy(k, key); + k[len] = node->key; + k[len+1] = '\0'; + struct trie_node * p = node->child; + while (NULL != p) + { + trie_visit_node(trie, p, op, k); + p = p->sibling; + } + } + } + +//////////////////////////////////////////////////////////////////////////////// +void trie_dump_raw(struct trie * trie) + { + if (NULL == trie) + return; + + int depth = -1; + trie_node_dump_raw(trie->root, depth); + } + +//////////////////////////////////////////////////////////////////////////////// +void +trie_node_dump_raw(struct trie_node * node, int depth) + { + for (int i=0; i < depth; i++) + printf(" "); + trie_print_node(node); + if (node->child) + trie_node_dump_raw(node->child, depth+1); + if (NULL != node->sibling) + trie_node_dump_raw(node->sibling, depth+1); + } + +//////////////////////////////////////////////////////////////////////////////// +void trie_dump(struct trie * trie) + { + if (NULL == trie) + return; + + int depth = -1; + trie_node_dump_preorder(trie, trie->root, depth); + } + +//////////////////////////////////////////////////////////////////////////////// +void +trie_node_dump_preorder(struct trie * trie, struct trie_node * node, int depth) + { + printf("%c", node->key); + if ( (node != trie->root) && ('\0' == node->key) ) + printf("\n"); + if (node->child) + trie_node_dump_preorder(trie, node->child, depth+1); + if (NULL != node->sibling) + { + for (int i=0; i < depth; i++) + printf(" "); + trie_node_dump_preorder(trie, node->sibling, depth); + } + } + +//////////////////////////////////////////////////////////////////////////////// +void +trie_print_node(struct trie_node * node) + { + printf("%p\tchild %p\tsibling %p\tkey %c\tdata %p\n", node, node->child, node->sibling, node->key, node->data); + } diff -r 8b09943f1a70 -r d359966ed8de src/trie.h --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/trie.h Mon Oct 01 15:50:30 2012 -0500 @@ -0,0 +1,18 @@ +#ifndef TRIE_H_ +#define TRIE_H_ + +struct trie; + +struct trie * trie_new(); +void trie_delete(struct trie * trie); + +char * trie_insert(struct trie * trie, char * key, void * data); +void * trie_find(struct trie * trie, char * key); +void * trie_remove(struct trie * trie, char * key); + +void trie_walk_keys(struct trie * trie, void (*op)(char * k, void * d) ); + +void trie_dump(struct trie * trie); +void trie_dump_raw(struct trie * trie); + +#endif diff -r 8b09943f1a70 -r d359966ed8de src/trie_test.c --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/trie_test.c Mon Oct 01 15:50:30 2012 -0500 @@ -0,0 +1,47 @@ +#include +#include + +#include "trie.h" + +void print_val(char * key, void * data) + { + printf("%s\n", key); + } + +int main(int argc, char ** argv) + { + struct trie * trie = trie_new(); + + char * words[] = { "hello", "interjection (used to express a greeting, answer a telephone, or attract attention.)", + "help", "to give or provide what is necessary to accomplish a task or satisfy a need.", + "helper", "a person or thing that helps or gives assistance, support, etc", + "helping", "the act of a person or thing that helps.", + "a", "indefinite article. Used before an initial consonant sound.", + "an", "indefinite article. the form of a before an initial vowel sound.", + "anna", "a female name", + "anne", "a female name", + "any", "one, a, an, or some; one or more without specification or identification", + "anyway", "in any case; anyhow; nonetheless; regardless", + "anyhow", "in any way whatever", + "anybody", "any person", + "Apple", "A computer manufacturer.", + "ABLE", "having necessary power, skill, resources, or qualifications", + NULL, NULL + }; + int i = 0; + while (words[i]) + { + trie_insert(trie, words[i], words[i+1]); + i += 2; + } + + trie_dump(trie); + + void * data = trie_find(trie, "any"); + if (NULL == data) + printf("Failed to find 'any'\n"); + else + printf("any: %s\n", (char *) data); + + exit(EXIT_SUCCESS); + }