Mercurial > data_structures
changeset 10:68f85ffc6029
Finished rbtree. Reworked the iterators in list. Minor tweaks to others.
| author | Eris Caffee <discordia@eldalin.com> |
|---|---|
| date | Fri, 28 Sep 2012 18:24:53 -0500 |
| parents | abdba37f67a2 |
| children | 8b09943f1a70 |
| files | CMakeLists.txt src/bst.c src/bst.h src/bst_test.c src/dequeue.c src/dequeue.h src/dequeue_test.c src/list.c src/list.h src/list_test.c src/pqueue.h src/queue.c src/queue.h src/queue_test.c src/rbtree.c src/rbtree.h src/ring_buffer.c src/ring_buffer.h src/stack.h |
| diffstat | 19 files changed, 318 insertions(+), 215 deletions(-) [+] |
line diff
1.1 --- a/CMakeLists.txt Fri Sep 28 03:08:25 2012 -0500 1.2 +++ b/CMakeLists.txt Fri Sep 28 18:24:53 2012 -0500 1.3 @@ -76,3 +76,8 @@ 1.4 add_executable (bst_test 1.5 ${bst_SRCS} 1.6 ) 1.7 + 1.8 +set (rbtree_SRCS src/rbtree.h src/rbtree.c src/rbtree_test.c) 1.9 +add_executable (rbtree_test 1.10 + ${rbtree_SRCS} 1.11 + )
2.1 --- a/src/bst.c Fri Sep 28 03:08:25 2012 -0500 2.2 +++ b/src/bst.c Fri Sep 28 18:24:53 2012 -0500 2.3 @@ -25,7 +25,6 @@ 2.4 struct bst_node * curr; 2.5 }; 2.6 2.7 -// Private functions. 2.8 void bst_data_walk_inorder(struct bst_node * node, void (*op)(void * data)); 2.9 void bst_data_walk_preorder(struct bst_node * node, void (*op)(void * data)); 2.10 void bst_data_walk_postorder(struct bst_node * node, void (*op)(void * data)); 2.11 @@ -35,11 +34,14 @@ 2.12 void * bst_data_search(struct bst * bst, struct bst_node * node, void * data); 2.13 void * bst_node_minimum(struct bst_node * node); 2.14 void * bst_node_maximum(struct bst_node * node); 2.15 + 2.16 void bst_node_free(struct bst_node * node); 2.17 2.18 struct bst_node * bst_node_search(struct bst * bst, struct bst_node * node, void * data); 2.19 +struct bst_node * bst_transplant(struct bst * bst, struct bst_node * a, struct bst_node * b); 2.20 2.21 -struct bst_node * bst_transplant(struct bst * bst, struct bst_node * a, struct bst_node * b); 2.22 +void bst_dump(struct bst * bst, void (*print_val)(void *) ); 2.23 +void bst_node_dump_preorder(struct bst * bst, struct bst_node * node, void (*print_val)(void *), int depth); 2.24 2.25 //////////////////////////////////////////////////////////////////////////////// 2.26 struct bst * 2.27 @@ -473,3 +475,23 @@ 2.28 return data; 2.29 } 2.30 2.31 +//////////////////////////////////////////////////////////////////////////////// 2.32 +void 2.33 +bst_dump(struct bst * bst, void (*print_val)(void *) ) 2.34 + { 2.35 + bst_node_dump_preorder(bst, bst->root, print_val, 0); 2.36 + } 2.37 + 2.38 +//////////////////////////////////////////////////////////////////////////////// 2.39 +void 2.40 +bst_node_dump_preorder(struct bst * bst, struct bst_node * node, void (*print_val)(void *), int depth) 2.41 + { 2.42 + for (int i=0; i < depth; i++) 2.43 + printf("\t"); 2.44 + print_val(node->data); 2.45 + printf("\n"); 2.46 + if (NULL != node->left) 2.47 + bst_node_dump_preorder(bst, node->left, print_val, depth+1); 2.48 + if (NULL != node->right) 2.49 + bst_node_dump_preorder(bst, node->right, print_val, depth+1); 2.50 + }
3.1 --- a/src/bst.h Fri Sep 28 03:08:25 2012 -0500 3.2 +++ b/src/bst.h Fri Sep 28 18:24:53 2012 -0500 3.3 @@ -10,20 +10,25 @@ 3.4 3.5 struct bst * bst_new(bool (*le)(void * a, void * b), bool (*eq)(void * a, void * b)); 3.6 void bst_delete(struct bst * bst); 3.7 -void * bst_insert(struct bst * bst, void * data); 3.8 -void * bst_search(struct bst * bst, void * data); 3.9 -void * bst_search_iterative(struct bst * bst, void * data); 3.10 -void * bst_minimum(struct bst * bst); 3.11 -void * bst_maximum(struct bst * bst); 3.12 -void bst_walk_inorder(struct bst * bst, void (*op)(void * data)); 3.13 -void bst_walk_preorder(struct bst * bst, void (*op)(void * data)); 3.14 -void bst_walk_postorder(struct bst * bst, void (*op)(void * data)); 3.15 -struct bst_iterator * bst_begin(struct bst * bst); 3.16 -struct bst_iterator * bst_end(struct bst * bst); 3.17 -struct bst_iterator * bst_next(struct bst_iterator * it); 3.18 -struct bst_iterator * bst_prev(struct bst_iterator * it); 3.19 -void * bst_value(struct bst_iterator * it); 3.20 -void * bst_find(struct bst_iterator * it, void * data); 3.21 -void * bst_remove(struct bst_iterator * it); 3.22 + 3.23 +void * bst_insert (struct bst * bst, void * data); 3.24 +void * bst_search (struct bst * bst, void * data); 3.25 +void * bst_search_iterative (struct bst * bst, void * data); 3.26 +void * bst_minimum (struct bst * bst); 3.27 +void * bst_maximum (struct bst * bst); 3.28 + 3.29 +void bst_walk_inorder (struct bst * bst, void (*op)(void * data)); 3.30 +void bst_walk_preorder (struct bst * bst, void (*op)(void * data)); 3.31 +void bst_walk_postorder (struct bst * bst, void (*op)(void * data)); 3.32 + 3.33 +struct bst_iterator * bst_begin (struct bst * bst); 3.34 +struct bst_iterator * bst_end (struct bst * bst); 3.35 +struct bst_iterator * bst_next (struct bst_iterator * it); 3.36 +struct bst_iterator * bst_prev (struct bst_iterator * it); 3.37 +void * bst_value (struct bst_iterator * it); 3.38 +void * bst_find (struct bst_iterator * it, void * data); 3.39 +void * bst_remove (struct bst_iterator * it); 3.40 + 3.41 +void bst_dump (struct bst * bst, void (*print_val)(void *) ); 3.42 3.43 #endif
4.1 --- a/src/bst_test.c Fri Sep 28 03:08:25 2012 -0500 4.2 +++ b/src/bst_test.c Fri Sep 28 18:24:53 2012 -0500 4.3 @@ -5,7 +5,12 @@ 4.4 4.5 #include "bst.h" 4.6 4.7 -#define MAX_NUMS 10 4.8 +#define MAX_NUMS 20 4.9 + 4.10 +void print_val(void * data) 4.11 + { 4.12 + printf("%d", *((int *) data)); 4.13 + } 4.14 4.15 bool le(void *a, void * b) 4.16 { 4.17 @@ -29,6 +34,19 @@ 4.18 4.19 int main(int argc, char ** argv) 4.20 { 4.21 + int sorted[100] = { 4.22 + 35005211, 42999170, 84353895, 135497281, 137806862, 149798315, 184803526, 233665123, 278722862, 294702567, 4.23 + 304089172, 336465782, 356426808, 412776091, 424238335, 468703135, 491705403, 511702305, 521595368, 572660336, 4.24 + 596516649, 608413784, 610515434, 628175011, 635723058, 709393584, 719885386, 749241873, 752392754, 756898537, 4.25 + 760313750, 783368690, 805750846, 846930886, 855636226, 859484421, 861021530, 939819582, 943947739, 945117276, 4.26 + 982906996, 1025202362, 1059961393, 1100661313, 1101513929, 1102520059, 1125898167, 1129566413, 1131176229, 1141616124, 4.27 + 1159126505, 1189641421, 1264095060, 1303455736, 1315634022, 1350490027, 1365180540, 1369133069, 1374344043, 1411549676, 4.28 + 1424268980, 1433925857, 1469348094, 1474612399, 1477171087, 1540383426, 1548233367, 1585990364, 1632621729, 1649760492, 4.29 + 1653377373, 1656478042, 1681692777, 1714636915, 1726956429, 1734575198, 1749698586, 1780695788, 1801979802, 1804289383, 4.30 + 1827336327, 1843993368, 1889947178, 1911759956, 1914544919, 1918502651, 1937477084, 1956297539, 1957747793, 1967513926, 4.31 + 1973594324, 1984210012, 1998898814, 2001100545, 2038664370, 2044897763, 2053999932, 2084420925, 2089018456, 2145174067, 4.32 + }; 4.33 + 4.34 struct bst * bst = bst_new(le, eq); 4.35 if (NULL == bst) 4.36 { 4.37 @@ -50,6 +68,7 @@ 4.38 } 4.39 4.40 *ip = rand(); 4.41 + // *ip = sorted[i]; 4.42 printf("%d\n", *ip); 4.43 if (NULL == bst_insert(bst, ip)) 4.44 { 4.45 @@ -60,6 +79,8 @@ 4.46 printf ("======================\n"); 4.47 4.48 4.49 + bst_dump(bst, print_val); 4.50 + 4.51 //////////////////////////////////////// 4.52 bst_walk_inorder(bst, print); 4.53
5.1 --- a/src/dequeue.c Fri Sep 28 03:08:25 2012 -0500 5.2 +++ b/src/dequeue.c Fri Sep 28 18:24:53 2012 -0500 5.3 @@ -12,7 +12,8 @@ 5.4 }; 5.5 5.6 //////////////////////////////////////////////////////////////////////////////// 5.7 -struct dequeue * dequeue_new(size_t const max) 5.8 +struct dequeue * 5.9 +dequeue_new(size_t const max) 5.10 { 5.11 if (max < 1) 5.12 return NULL; 5.13 @@ -39,7 +40,8 @@ 5.14 // NULL on error 5.15 // elem on success and the buffer is not full 5.16 // the overwritten element on success if the buffer was full 5.17 -void * dequeue_push_top(struct dequeue * deq, void * elem) 5.18 +void * 5.19 +dequeue_push_top(struct dequeue * deq, void * elem) 5.20 { 5.21 if ((NULL == deq) || (NULL == elem)) 5.22 return NULL; 5.23 @@ -59,7 +61,8 @@ 5.24 } 5.25 5.26 //////////////////////////////////////////////////////////////////////////////// 5.27 -void * dequeue_push_bottom(struct dequeue * deq, void * elem) 5.28 +void * 5.29 +dequeue_push_bottom(struct dequeue * deq, void * elem) 5.30 { 5.31 if ((NULL == deq) || (NULL == elem)) 5.32 return NULL; 5.33 @@ -79,7 +82,8 @@ 5.34 } 5.35 5.36 //////////////////////////////////////////////////////////////////////////////// 5.37 -void * dequeue_pop_top(struct dequeue * deq) 5.38 +void * 5.39 +dequeue_pop_top(struct dequeue * deq) 5.40 { 5.41 if (NULL == deq) 5.42 return NULL; 5.43 @@ -100,7 +104,8 @@ 5.44 } 5.45 5.46 //////////////////////////////////////////////////////////////////////////////// 5.47 -void * dequeue_pop_bottom(struct dequeue * deq) 5.48 +void * 5.49 +dequeue_pop_bottom(struct dequeue * deq) 5.50 { 5.51 if (NULL == deq) 5.52 return NULL; 5.53 @@ -122,7 +127,8 @@ 5.54 5.55 5.56 //////////////////////////////////////////////////////////////////////////////// 5.57 -size_t dequeue_size(struct dequeue * deq) 5.58 +size_t 5.59 +dequeue_size(struct dequeue * deq) 5.60 { 5.61 if (NULL == deq) 5.62 return 0; 5.63 @@ -130,7 +136,8 @@ 5.64 } 5.65 5.66 //////////////////////////////////////////////////////////////////////////////// 5.67 -void dequeue_delete(struct dequeue * deq) 5.68 +void 5.69 +dequeue_delete(struct dequeue * deq) 5.70 { 5.71 if (NULL != deq) 5.72 {
6.1 --- a/src/dequeue.h Fri Sep 28 03:08:25 2012 -0500 6.2 +++ b/src/dequeue.h Fri Sep 28 18:24:53 2012 -0500 6.3 @@ -7,10 +7,12 @@ 6.4 6.5 struct dequeue * dequeue_new(size_t const size); 6.6 void dequeue_delete(struct dequeue * deq); 6.7 -void * dequeue_push_top(struct dequeue * deq, void * elem); 6.8 -void * dequeue_pop_top(struct dequeue * deq); 6.9 -void * dequeue_push_bottom(struct dequeue * deq, void * elem); 6.10 -void * dequeue_pop_bottom(struct dequeue * deq); 6.11 -size_t dequeue_size(struct dequeue * deq); 6.12 + 6.13 +void * dequeue_push_top (struct dequeue * deq, void * elem); 6.14 +void * dequeue_pop_top (struct dequeue * deq); 6.15 +void * dequeue_push_bottom (struct dequeue * deq, void * elem); 6.16 +void * dequeue_pop_bottom (struct dequeue * deq); 6.17 + 6.18 +size_t dequeue_size (struct dequeue * deq); 6.19 6.20 #endif
7.1 --- a/src/dequeue_test.c Fri Sep 28 03:08:25 2012 -0500 7.2 +++ b/src/dequeue_test.c Fri Sep 28 18:24:53 2012 -0500 7.3 @@ -38,6 +38,7 @@ 7.4 printf("dequeue size is %zd\n", dequeue_size(deq)); 7.5 7.6 // Overfill the dequeue 7.7 + printf("Overfilling the queue. 5 failures are expected.\n"); 7.8 for (i=MAX; i < 2*MAX; i++) 7.9 { 7.10 ip = malloc(sizeof(int)); 7.11 @@ -50,7 +51,7 @@ 7.12 errno = 0; 7.13 if (NULL == dequeue_push_top(deq, (void *) ip)) 7.14 { 7.15 - perror("dequeue_push_top"); 7.16 + printf("dequeue_push_top failed\n"); 7.17 free(ip); 7.18 } 7.19 } 7.20 @@ -71,7 +72,7 @@ 7.21 *ip = i; 7.22 if (NULL == dequeue_push_top(deq, (void *) ip)) 7.23 { 7.24 - perror("dequeue_push"); 7.25 + printf("dequeue_push_top failed\n"); 7.26 free(ip); 7.27 } 7.28 }
8.1 --- a/src/list.c Fri Sep 28 03:08:25 2012 -0500 8.2 +++ b/src/list.c Fri Sep 28 18:24:53 2012 -0500 8.3 @@ -176,6 +176,10 @@ 8.4 return t; 8.5 } 8.6 8.7 + 8.8 + 8.9 + 8.10 + 8.11 //////////////////////////////////////////////////////////////////////////////// 8.12 // Intialize an iterator to point to the first element of the list 8.13 struct list_iterator * 8.14 @@ -213,72 +217,74 @@ 8.15 } 8.16 8.17 //////////////////////////////////////////////////////////////////////////////// 8.18 -// Move the iterator to the next element in the list, returning its value. 8.19 -void * 8.20 -list_next(struct list_iterator * lit) 8.21 +// Move the iterator to the next element in the list. 8.22 +struct list_iterator * 8.23 +list_next(struct list_iterator * it) 8.24 { 8.25 - if (NULL == lit) 8.26 + if (NULL == it) 8.27 return NULL; 8.28 8.29 - lit->curr = lit->curr->next; 8.30 - 8.31 - if (lit->curr) 8.32 - return lit->curr->data; 8.33 - 8.34 - return NULL; 8.35 + it->curr = it->curr->next; 8.36 + return it->curr; 8.37 } 8.38 8.39 //////////////////////////////////////////////////////////////////////////////// 8.40 -// Move the iterator to the previous element in the list, returning its value. 8.41 -void * 8.42 -list_prev(struct list_iterator * lit) 8.43 +// Move the iterator to the previous element in the list. 8.44 +struct list_iterator * 8.45 +list_prev(struct list_iterator * it) 8.46 { 8.47 - if (NULL == lit) 8.48 + if (NULL == it) 8.49 return NULL; 8.50 8.51 - lit->curr = lit->curr->prev; 8.52 - 8.53 - if (lit->curr) 8.54 - return lit->curr->data; 8.55 - 8.56 - return NULL; 8.57 + it->curr = it->curr->prev; 8.58 + return it->curr; 8.59 } 8.60 8.61 //////////////////////////////////////////////////////////////////////////////// 8.62 -// Remove the current element pointed to by the iterator, returning that elements value. 8.63 +// Remove the current element pointed to by the iterator. 8.64 +// Returns the data element that was removed so the caller can free it. 8.65 void * 8.66 -list_erase(struct list_iterator * lit) 8.67 +list_remove(struct list_iterator * it) 8.68 { 8.69 - if ( (NULL == lit) || (NULL == lit->curr) ) 8.70 + if ( (NULL == it) || (NULL == it->curr) ) 8.71 return NULL; 8.72 8.73 - if (lit->curr->prev) 8.74 - lit->curr->prev->next = lit->curr->next; 8.75 + if (it->curr->prev) 8.76 + it->curr->prev->next = it->curr->next; 8.77 8.78 - if (lit->curr->next) 8.79 - lit->curr->next->prev = lit->curr->prev; 8.80 + if (it->curr->next) 8.81 + it->curr->next->prev = it->curr->prev; 8.82 8.83 - struct list_node * temp = lit->curr; 8.84 - void * elem = lit->curr->data; 8.85 + struct list_node * temp = it->curr; 8.86 + void * elem = it->curr->data; 8.87 8.88 - lit->curr = lit->curr->next; 8.89 + it->curr = it->curr->next; 8.90 free(temp); 8.91 8.92 - lit->l->size--; 8.93 - if (0 == lit->l->size) 8.94 - lit->l->tail = lit->l->head = NULL; 8.95 + it->l->size--; 8.96 + if (0 == it->l->size) 8.97 + it->l->tail = it->l->head = NULL; 8.98 8.99 return elem; 8.100 } 8.101 8.102 //////////////////////////////////////////////////////////////////////////////// 8.103 +// Return the value of the element pointed to by the iterator. 8.104 +void * 8.105 +list_value(struct list_iterator * it) 8.106 + { 8.107 + if ( (NULL == it) || (NULL == it->curr) ) 8.108 + return NULL; 8.109 + return it->curr->data; 8.110 + } 8.111 + 8.112 +//////////////////////////////////////////////////////////////////////////////// 8.113 // Insert a new element after the one pointed to by the iterator. 8.114 // The iterator is then set to point to this new element. 8.115 -// Return the new elements value. 8.116 -void * 8.117 -list_insert_after(struct list_iterator * lit, void * elem) 8.118 +struct list_iterator * 8.119 +list_insert_after(struct list_iterator * it, void * elem) 8.120 { 8.121 - if ( (NULL == lit) || (NULL == elem) || (NULL == lit->curr) ) 8.122 + if ( (NULL == it) || (NULL == elem) || (NULL == it->curr) ) 8.123 return NULL; 8.124 8.125 struct list_node * new = malloc(sizeof(struct list_node)); 8.126 @@ -286,29 +292,28 @@ 8.127 return NULL; 8.128 8.129 new->data = elem; 8.130 - new->prev = lit->curr; 8.131 - if (lit->curr->next) 8.132 - lit->curr->next->prev = new; 8.133 - new->next = lit->curr->next; 8.134 - lit->curr->next = new; 8.135 + new->prev = it->curr; 8.136 + if (it->curr->next) 8.137 + it->curr->next->prev = new; 8.138 + new->next = it->curr->next; 8.139 + it->curr->next = new; 8.140 8.141 - lit->curr = new; 8.142 + it->curr = new; 8.143 8.144 - lit->l->size++; 8.145 - if (NULL == lit->curr->next) 8.146 - lit->l->tail = lit->curr; 8.147 + it->l->size++; 8.148 + if (NULL == it->curr->next) 8.149 + it->l->tail = it->curr; 8.150 8.151 - return elem; 8.152 + return it; 8.153 } 8.154 8.155 //////////////////////////////////////////////////////////////////////////////// 8.156 // Insert a new element before the one pointed to by the iterator. 8.157 // The iterator is then set to point to this new element. 8.158 -// Return the new elements value. 8.159 -void * 8.160 -list_insert_before(struct list_iterator * lit, void * elem) 8.161 +struct list_iterator * 8.162 +list_insert_before(struct list_iterator * it, void * elem) 8.163 { 8.164 - if ( (NULL == lit) || (NULL == elem) || (NULL == lit->curr) ) 8.165 + if ( (NULL == it) || (NULL == elem) || (NULL == it->curr) ) 8.166 return NULL; 8.167 8.168 struct list_node * new = malloc(sizeof(struct list_node)); 8.169 @@ -316,28 +321,18 @@ 8.170 return NULL; 8.171 8.172 new->data = elem; 8.173 - new->next = lit->curr; 8.174 - if (lit->curr->prev) 8.175 - lit->curr->prev->next = new; 8.176 - new->prev = lit->curr->prev; 8.177 - lit->curr->prev = new; 8.178 + new->next = it->curr; 8.179 + if (it->curr->prev) 8.180 + it->curr->prev->next = new; 8.181 + new->prev = it->curr->prev; 8.182 + it->curr->prev = new; 8.183 8.184 - lit->curr = new; 8.185 + it->curr = new; 8.186 8.187 - lit->l->size++; 8.188 - if (NULL == lit->curr->prev) 8.189 - lit->l->head = lit->curr; 8.190 + it->l->size++; 8.191 + if (NULL == it->curr->prev) 8.192 + it->l->head = it->curr; 8.193 8.194 - return elem; 8.195 + return it; 8.196 } 8.197 8.198 -//////////////////////////////////////////////////////////////////////////////// 8.199 -// Return the value of the element pointed to by the iterator. 8.200 -void * 8.201 -list_value(struct list_iterator * lit) 8.202 - { 8.203 - if ( (NULL == lit) || (NULL == lit->curr) ) 8.204 - return NULL; 8.205 - return lit->curr->data; 8.206 - } 8.207 -
9.1 --- a/src/list.h Fri Sep 28 03:08:25 2012 -0500 9.2 +++ b/src/list.h Fri Sep 28 18:24:53 2012 -0500 9.3 @@ -9,6 +9,7 @@ 9.4 9.5 struct list * list_new(void); 9.6 void list_delete(struct list * l); 9.7 + 9.8 size_t list_size(struct list * l); 9.9 void * list_push_back(struct list * l, void * elem); 9.10 void * list_pop_back(struct list * l); 9.11 @@ -17,13 +18,15 @@ 9.12 9.13 // The iterators are different than their c++ STL counterparts. 9.14 // They are bi-directional, and list_end points to the last element, not the empty space beyond the last elem. 9.15 -struct list_iterator * list_begin(struct list * l); 9.16 -struct list_iterator * list_end(struct list * l); 9.17 -void * list_next(struct list_iterator * lit); 9.18 -void * list_prev(struct list_iterator * lit); 9.19 -void * list_erase(struct list_iterator * lit); 9.20 -void * list_insert_after(struct list_iterator * lit, void * elem); 9.21 -void * list_insert_before(struct list_iterator * lit, void * elem); 9.22 -void * list_value(struct list_iterator * lit); 9.23 +struct list_iterator * list_begin (struct list * l); 9.24 +struct list_iterator * list_end (struct list * l); 9.25 +struct list_iterator * list_next (struct list_iterator * lit); 9.26 +struct list_iterator * list_prev (struct list_iterator * lit); 9.27 +struct list_iterator * list_find (struct list_iterator * it, void * data); 9.28 +void * list_remove (struct list_iterator * lit); 9.29 +void * list_value (struct list_iterator * lit); 9.30 + 9.31 +struct list_iterator * list_insert_after (struct list_iterator * lit, void * elem); 9.32 +struct list_iterator * list_insert_before (struct list_iterator * lit, void * elem); 9.33 9.34 #endif
10.1 --- a/src/list_test.c Fri Sep 28 03:08:25 2012 -0500 10.2 +++ b/src/list_test.c Fri Sep 28 18:24:53 2012 -0500 10.3 @@ -71,7 +71,7 @@ 10.4 10.5 10.6 ///////////////////////////////////// 10.7 - // Push back and pop back 10.8 + // Push back and pop front 10.9 for (int i = 0; i < MAX ; i++) 10.10 { 10.11 int * ip = malloc(sizeof(int)); 10.12 @@ -119,16 +119,18 @@ 10.13 printf("size %zd\n", list_size(l)); 10.14 10.15 struct list_iterator * lit; 10.16 + struct list_iterator * next; 10.17 int * ip; 10.18 10.19 printf("Walking front to back\n"); 10.20 - for (lit = list_begin(l); NULL != ip; ip = list_next( &lit)) 10.21 - printf("%d\n", *ip); 10.22 + for (next = lit = list_begin(l); NULL != next; next = list_next(lit)) 10.23 + printf("%d\n", *((int *) list_value(lit))); 10.24 + free(lit); 10.25 10.26 printf("Inserting 15 after 5\n"); 10.27 - for (ip = list_begin(l, &lit); NULL != ip; ip = list_next( &lit)) 10.28 + for (next = lit = list_begin(l); NULL != next ; next = list_next(lit)) 10.29 { 10.30 - if (5 == *ip) 10.31 + if (5 == *((int *) list_value(lit))) 10.32 { 10.33 int * newip = malloc(sizeof(int)); 10.34 if (NULL == newip) 10.35 @@ -137,7 +139,7 @@ 10.36 exit(EXIT_FAILURE); 10.37 } 10.38 *newip = 15; 10.39 - if (NULL == list_insert_after(&lit, newip)) 10.40 + if (NULL == list_insert_after(lit, newip)) 10.41 { 10.42 perror("malloc"); 10.43 exit(EXIT_FAILURE); 10.44 @@ -145,11 +147,12 @@ 10.45 break; 10.46 } 10.47 } 10.48 + free(lit); 10.49 10.50 printf("Inserting 20 before 8\n"); 10.51 - for (ip = list_begin(l, &lit); NULL != ip; ip = list_next( &lit)) 10.52 + for (next = lit = list_begin(l); NULL != next ; next = list_next(lit)) 10.53 { 10.54 - if (8 == *ip) 10.55 + if (8 == *((int *) list_value(lit))) 10.56 { 10.57 int * newip = malloc(sizeof(int)); 10.58 if (NULL == newip) 10.59 @@ -158,7 +161,7 @@ 10.60 exit(EXIT_FAILURE); 10.61 } 10.62 *newip = 20; 10.63 - if (NULL == list_insert_before(&lit, newip)) 10.64 + if (NULL == list_insert_before(lit, newip)) 10.65 { 10.66 perror("malloc"); 10.67 exit(EXIT_FAILURE); 10.68 @@ -166,22 +169,23 @@ 10.69 break; 10.70 } 10.71 } 10.72 + free(lit); 10.73 10.74 printf("size %zd\n", list_size(l)); 10.75 10.76 printf("Walking back to front\n"); 10.77 - for (ip = list_end(l, &lit); NULL != ip ; ip = list_prev(&lit)) 10.78 - printf("%d\n", *ip); 10.79 - 10.80 + for (next = lit = list_end(l); NULL != next ; next = list_prev(lit)) 10.81 + printf("%d\n", *((int *) list_value(lit))); 10.82 + free(lit); 10.83 10.84 printf("Erasing front to back\n"); 10.85 - list_begin(l, &lit); 10.86 - while (NULL != (ip = list_value(&lit))) 10.87 + lit = list_begin(l); 10.88 + while (NULL != (ip = list_remove(lit))) 10.89 { 10.90 printf("%d\n", *ip); 10.91 - list_erase(&lit); 10.92 free(ip); 10.93 } 10.94 + free(lit); 10.95 printf("size %zd\n", list_size(l)); 10.96 10.97 list_delete(l);
11.1 --- a/src/pqueue.h Fri Sep 28 03:08:25 2012 -0500 11.2 +++ b/src/pqueue.h Fri Sep 28 18:24:53 2012 -0500 11.3 @@ -8,9 +8,10 @@ 11.4 11.5 struct pqueue * pqueue_new(size_t max, bool (*comp)(void const * const a, void const * const b)); 11.6 void pqueue_delete(struct pqueue * pq); 11.7 -void * pqueue_push(struct pqueue * pq, void * elem); 11.8 -void * pqueue_pop(struct pqueue * pq); 11.9 -void * pqueue_peek(struct pqueue * pq); 11.10 -size_t pqueue_size(struct pqueue * pq); 11.11 + 11.12 +void * pqueue_push (struct pqueue * pq, void * elem); 11.13 +void * pqueue_pop (struct pqueue * pq); 11.14 +void * pqueue_peek (struct pqueue * pq); 11.15 +size_t pqueue_size (struct pqueue * pq); 11.16 11.17 #endif // ndef PQUEUE_
12.1 --- a/src/queue.c Fri Sep 28 03:08:25 2012 -0500 12.2 +++ b/src/queue.c Fri Sep 28 18:24:53 2012 -0500 12.3 @@ -12,13 +12,11 @@ 12.4 }; 12.5 12.6 //////////////////////////////////////////////////////////////////////////////// 12.7 -struct queue * queue_new(size_t const max) 12.8 +struct queue * 12.9 +queue_new(size_t const max) 12.10 { 12.11 if (max < 1) 12.12 - { 12.13 - errno = EINVAL; 12.14 return NULL; 12.15 - } 12.16 12.17 struct queue * queue = malloc(sizeof(struct queue)); 12.18 if (NULL == queue) 12.19 @@ -42,19 +40,14 @@ 12.20 // NULL on error 12.21 // elem on success and the buffer is not full 12.22 // the overwritten element on success if the buffer was full 12.23 -void * queue_push(struct queue * queue, void * elem) 12.24 +void * 12.25 +queue_push(struct queue * queue, void * elem) 12.26 { 12.27 if ((NULL == queue) || (NULL == elem)) 12.28 - { 12.29 - errno = EINVAL; 12.30 return NULL; 12.31 - } 12.32 12.33 if (queue->count == queue->max) 12.34 - { 12.35 - errno = ENOMEM; 12.36 return NULL; 12.37 - } 12.38 12.39 size_t end = (queue->start + queue->count) % queue->max; 12.40 12.41 @@ -65,13 +58,11 @@ 12.42 } 12.43 12.44 //////////////////////////////////////////////////////////////////////////////// 12.45 -void * queue_pop(struct queue * queue) 12.46 +void * 12.47 +queue_pop(struct queue * queue) 12.48 { 12.49 if (NULL == queue) 12.50 - { 12.51 - errno = EINVAL; 12.52 return NULL; 12.53 - } 12.54 12.55 if (0 == queue->count) 12.56 return NULL; 12.57 @@ -84,19 +75,18 @@ 12.58 } 12.59 12.60 //////////////////////////////////////////////////////////////////////////////// 12.61 -size_t queue_size(struct queue * queue) 12.62 +size_t 12.63 +queue_size(struct queue * queue) 12.64 { 12.65 if (NULL == queue) 12.66 - { 12.67 - errno = EINVAL; 12.68 - return -1; 12.69 - } 12.70 + return 0; 12.71 12.72 return queue->count; 12.73 } 12.74 12.75 //////////////////////////////////////////////////////////////////////////////// 12.76 -void queue_delete(struct queue * queue) 12.77 +void 12.78 +queue_delete(struct queue * queue) 12.79 { 12.80 if (NULL != queue) free(queue->data); 12.81 free(queue);
13.1 --- a/src/queue.h Fri Sep 28 03:08:25 2012 -0500 13.2 +++ b/src/queue.h Fri Sep 28 18:24:53 2012 -0500 13.3 @@ -7,8 +7,9 @@ 13.4 13.5 struct queue * queue_new(size_t const size); 13.6 void queue_delete(struct queue * queue); 13.7 -void * queue_push(struct queue * queue, void * elem); 13.8 -void * queue_pop(struct queue * queue); 13.9 -size_t queue_size(struct queue * queue); 13.10 + 13.11 +void * queue_push (struct queue * queue, void * elem); 13.12 +void * queue_pop (struct queue * queue); 13.13 +size_t queue_size (struct queue * queue); 13.14 13.15 #endif
14.1 --- a/src/queue_test.c Fri Sep 28 03:08:25 2012 -0500 14.2 +++ b/src/queue_test.c Fri Sep 28 18:24:53 2012 -0500 14.3 @@ -24,7 +24,10 @@ 14.4 ip = malloc(sizeof(int)); 14.5 *ip = i; 14.6 if (NULL == queue_push(q, (void *) ip)) 14.7 - perror("queue_push"); 14.8 + { 14.9 + printf("queue_push failed\n"); 14.10 + free(ip); 14.11 + } 14.12 } 14.13 14.14 // remove 5 items 14.15 @@ -43,7 +46,7 @@ 14.16 *ip = i; 14.17 if (NULL == queue_push(q, (void *) ip)) 14.18 { 14.19 - perror("queue_push"); 14.20 + printf("queue_push failed\n"); 14.21 free(ip); 14.22 } 14.23 }
15.1 --- a/src/rbtree.c Fri Sep 28 03:08:25 2012 -0500 15.2 +++ b/src/rbtree.c Fri Sep 28 18:24:53 2012 -0500 15.3 @@ -30,21 +30,26 @@ 15.4 struct rbtree_node * curr; 15.5 }; 15.6 15.7 -// Private functions. 15.8 -void rbtree_data_walk_inorder(struct rbtree * rbtree, struct rbtree_node * node, void (*op)(void * data)); 15.9 -void rbtree_data_walk_preorder(struct rbtree * rbtree, struct rbtree_node * node, void (*op)(void * data)); 15.10 -void rbtree_data_walk_postorder(struct rbtree * rbtree, struct rbtree_node * node, void (*op)(void * data)); 15.11 -void rbtree_node_walk_postorder(struct rbtree * rbtree, struct rbtree_node * node, void (*op)(struct rbtree_node * n)); 15.12 -void * rbtree_data_search(struct rbtree * rbtree, struct rbtree_node * node, void * data); 15.13 -void * rbtree_node_minimum(struct rbtree * rbtree, struct rbtree_node * node); 15.14 -void * rbtree_node_maximum(struct rbtree * rbtree, struct rbtree_node * node); 15.15 -void rbtree_node_free(struct rbtree_node * node); 15.16 -struct rbtree_node * rbtree_node_search(struct rbtree * rbtree, struct rbtree_node * node, void * data); 15.17 -struct rbtree_node * rbtree_transplant(struct rbtree * rbtree, struct rbtree_node * a, struct rbtree_node * b); 15.18 -void rbtree_rotate_left(struct rbtree * rbtree, struct rbtree_node * node); 15.19 -void rbtree_rotate_right(struct rbtree * rbtree, struct rbtree_node * node); 15.20 -void rbtree_insert_fixup(struct rbtree * rbtree, struct rbtree_node * node); 15.21 -void rbtree_remove_fixup(struct rbtree * rbtree, struct rbtree_node * node); 15.22 +void * rbtree_data_search (struct rbtree * rbtree, struct rbtree_node * node, void * data); 15.23 +void * rbtree_node_minimum (struct rbtree * rbtree, struct rbtree_node * node); 15.24 +void * rbtree_node_maximum (struct rbtree * rbtree, struct rbtree_node * node); 15.25 + 15.26 +void rbtree_data_walk_inorder (struct rbtree * rbtree, struct rbtree_node * node, void (*op)(void * data)); 15.27 +void rbtree_data_walk_preorder (struct rbtree * rbtree, struct rbtree_node * node, void (*op)(void * data)); 15.28 +void rbtree_data_walk_postorder (struct rbtree * rbtree, struct rbtree_node * node, void (*op)(void * data)); 15.29 +void rbtree_node_walk_postorder (struct rbtree * rbtree, struct rbtree_node * node, void (*op)(struct rbtree_node * n)); 15.30 + 15.31 +void rbtree_node_free (struct rbtree_node * node); 15.32 + 15.33 +struct rbtree_node * rbtree_node_search (struct rbtree * rbtree, struct rbtree_node * node, void * data); 15.34 + 15.35 +struct rbtree_node * rbtree_transplant (struct rbtree * rbtree, struct rbtree_node * a, struct rbtree_node * b); 15.36 +void rbtree_rotate_left (struct rbtree * rbtree, struct rbtree_node * node); 15.37 +void rbtree_rotate_right (struct rbtree * rbtree, struct rbtree_node * node); 15.38 +void rbtree_insert_fixup (struct rbtree * rbtree, struct rbtree_node * node); 15.39 +void rbtree_remove_fixup (struct rbtree * rbtree, struct rbtree_node * node); 15.40 + 15.41 +void rbtree_node_dump_preorder(struct rbtree * rbtree, struct rbtree_node * node, void (*print_val)(void *), int depth); 15.42 15.43 //////////////////////////////////////////////////////////////////////////////// 15.44 struct rbtree * 15.45 @@ -136,7 +141,6 @@ 15.46 return new->data; 15.47 } 15.48 15.49 - 15.50 //////////////////////////////////////////////////////////////////////////////// 15.51 void 15.52 rbtree_insert_fixup(struct rbtree * rbtree, struct rbtree_node * node) 15.53 @@ -373,7 +377,7 @@ 15.54 return NULL; 15.55 15.56 struct rbtree_node * min = rbtree->root; 15.57 - while (min->left) 15.58 + while (rbtree->nil != min->left) 15.59 min = min->left; 15.60 15.61 struct rbtree_iterator * it = malloc(sizeof(struct rbtree_iterator)); 15.62 @@ -393,7 +397,7 @@ 15.63 return NULL; 15.64 15.65 struct rbtree_node * max = rbtree->root; 15.66 - while (max->right) 15.67 + while (rbtree->nil != max->right) 15.68 max = max->right; 15.69 15.70 struct rbtree_iterator * it = malloc(sizeof(struct rbtree_iterator)); 15.71 @@ -428,7 +432,7 @@ 15.72 else 15.73 { 15.74 struct rbtree_node * min = it->curr->right; 15.75 - while (min->left) 15.76 + while (it->rbtree->nil != min->left) 15.77 min = min->left; 15.78 it->curr = min; 15.79 } 15.80 @@ -458,7 +462,7 @@ 15.81 else 15.82 { 15.83 struct rbtree_node * max = it->curr->left; 15.84 - while (max->right) 15.85 + while (it->rbtree->nil != max->right) 15.86 max = max->right; 15.87 it->curr = max; 15.88 } 15.89 @@ -702,3 +706,43 @@ 15.90 node->parent = y; 15.91 } 15.92 15.93 +//////////////////////////////////////////////////////////////////////////////// 15.94 +unsigned int rbtree_black_depth(struct rbtree * rbtree) 15.95 + { 15.96 + if ( (NULL == rbtree) || (NULL == rbtree->root) ) 15.97 + return 0; 15.98 + 15.99 + struct rbtree_node * node = rbtree->root; 15.100 + unsigned int black_depth = 0; 15.101 + 15.102 + while (rbtree->nil != node) 15.103 + { 15.104 + if (BLACK == node->color) 15.105 + black_depth++; 15.106 + node = node->left; 15.107 + } 15.108 + 15.109 + return black_depth; 15.110 + } 15.111 + 15.112 +//////////////////////////////////////////////////////////////////////////////// 15.113 +void 15.114 +rbtree_dump(struct rbtree * rbtree, void (*print_val)(void *) ) 15.115 + { 15.116 + rbtree_node_dump_preorder(rbtree, rbtree->root, print_val, 0); 15.117 + } 15.118 + 15.119 +//////////////////////////////////////////////////////////////////////////////// 15.120 +void 15.121 +rbtree_node_dump_preorder(struct rbtree * rbtree, struct rbtree_node * node, void (*print_val)(void *), int depth) 15.122 + { 15.123 + for (int i=0; i < depth; i++) 15.124 + printf("\t"); 15.125 + printf("%-8s", (BLACK == node->color ? "black" : "red")); 15.126 + print_val(node->data); 15.127 + printf("\n"); 15.128 + if (rbtree->nil != node->left) 15.129 + rbtree_node_dump_preorder(rbtree, node->left, print_val, depth+1); 15.130 + if (rbtree->nil != node->right) 15.131 + rbtree_node_dump_preorder(rbtree, node->right, print_val, depth+1); 15.132 + }
16.1 --- a/src/rbtree.h Fri Sep 28 03:08:25 2012 -0500 16.2 +++ b/src/rbtree.h Fri Sep 28 18:24:53 2012 -0500 16.3 @@ -10,22 +10,26 @@ 16.4 16.5 struct rbtree * rbtree_new(bool (*le)(void * a, void * b), bool (*eq)(void * a, void * b)); 16.6 void rbtree_delete(struct rbtree * rbtree); 16.7 -void * rbtree_insert(struct rbtree * rbtree, void * data); 16.8 -void * rbtree_search(struct rbtree * rbtree, void * data); 16.9 -void * rbtree_search_iterative(struct rbtree * rbtree, void * data); 16.10 -void * rbtree_minimum(struct rbtree * rbtree); 16.11 -void * rbtree_maximum(struct rbtree * rbtree); 16.12 16.13 -void rbtree_walk_inorder(struct rbtree * rbtree, void (*op)(void * data)); 16.14 -void rbtree_walk_preorder(struct rbtree * rbtree, void (*op)(void * data)); 16.15 -void rbtree_walk_postorder(struct rbtree * rbtree, void (*op)(void * data)); 16.16 +void * rbtree_insert (struct rbtree * rbtree, void * data); 16.17 +void * rbtree_search (struct rbtree * rbtree, void * data); 16.18 +void * rbtree_search_iterative (struct rbtree * rbtree, void * data); 16.19 +void * rbtree_minimum (struct rbtree * rbtree); 16.20 +void * rbtree_maximum (struct rbtree * rbtree); 16.21 16.22 -struct rbtree_iterator * rbtree_begin(struct rbtree * rbtree); 16.23 -struct rbtree_iterator * rbtree_end(struct rbtree * rbtree); 16.24 -struct rbtree_iterator * rbtree_next(struct rbtree_iterator * it); 16.25 -struct rbtree_iterator * rbtree_prev(struct rbtree_iterator * it); 16.26 -void * rbtree_value(struct rbtree_iterator * it); 16.27 -void * rbtree_find(struct rbtree_iterator * it, void * data); 16.28 -void * rbtree_remove(struct rbtree_iterator * it); 16.29 +void rbtree_walk_inorder (struct rbtree * rbtree, void (*op)(void * data)); 16.30 +void rbtree_walk_preorder (struct rbtree * rbtree, void (*op)(void * data)); 16.31 +void rbtree_walk_postorder (struct rbtree * rbtree, void (*op)(void * data)); 16.32 + 16.33 +struct rbtree_iterator * rbtree_begin (struct rbtree * rbtree); 16.34 +struct rbtree_iterator * rbtree_end (struct rbtree * rbtree); 16.35 +struct rbtree_iterator * rbtree_next (struct rbtree_iterator * it); 16.36 +struct rbtree_iterator * rbtree_prev (struct rbtree_iterator * it); 16.37 +void * rbtree_find (struct rbtree_iterator * it, void * data); 16.38 +void * rbtree_remove (struct rbtree_iterator * it); 16.39 +void * rbtree_value (struct rbtree_iterator * it); 16.40 + 16.41 +unsigned int rbtree_black_depth(struct rbtree * rbtree); 16.42 +void rbtree_dump(struct rbtree * rbtree, void (*print_val)(void *) ); 16.43 16.44 #endif
17.1 --- a/src/ring_buffer.c Fri Sep 28 03:08:25 2012 -0500 17.2 +++ b/src/ring_buffer.c Fri Sep 28 18:24:53 2012 -0500 17.3 @@ -12,13 +12,11 @@ 17.4 }; 17.5 17.6 //////////////////////////////////////////////////////////////////////////////// 17.7 -struct ring_buffer * ring_buffer_new(size_t const max) 17.8 +struct ring_buffer * 17.9 +ring_buffer_new(size_t const max) 17.10 { 17.11 if (max < 1) 17.12 - { 17.13 - errno = EINVAL; 17.14 return NULL; 17.15 - } 17.16 17.17 struct ring_buffer * rb = malloc(sizeof(struct ring_buffer)); 17.18 if (NULL == rb) 17.19 @@ -42,13 +40,11 @@ 17.20 // NULL on error 17.21 // elem on success and the buffer is not full 17.22 // the overwritten element on success if the buffer was full 17.23 -void * ring_buffer_write(struct ring_buffer * rb, void * elem) 17.24 +void * 17.25 +ring_buffer_write(struct ring_buffer * rb, void * elem) 17.26 { 17.27 if ((NULL == rb) || (NULL == elem)) 17.28 - { 17.29 - errno = EINVAL; 17.30 return NULL; 17.31 - } 17.32 17.33 size_t end = rb->start + rb->count; 17.34 void * ret = rb->data[end % rb->max]; 17.35 @@ -65,13 +61,11 @@ 17.36 } 17.37 17.38 //////////////////////////////////////////////////////////////////////////////// 17.39 -void * ring_buffer_read(struct ring_buffer * rb) 17.40 +void * 17.41 +ring_buffer_read(struct ring_buffer * rb) 17.42 { 17.43 if (NULL == rb) 17.44 - { 17.45 - errno = EINVAL; 17.46 return NULL; 17.47 - } 17.48 17.49 if (0 == rb->count) 17.50 return NULL; 17.51 @@ -84,19 +78,18 @@ 17.52 } 17.53 17.54 //////////////////////////////////////////////////////////////////////////////// 17.55 -size_t ring_buffer_size(struct ring_buffer * rb) 17.56 +size_t 17.57 +ring_buffer_size(struct ring_buffer * rb) 17.58 { 17.59 if (NULL == rb) 17.60 - { 17.61 - errno = EINVAL; 17.62 - return -1; 17.63 - } 17.64 + return 0; 17.65 17.66 return rb->count; 17.67 } 17.68 17.69 //////////////////////////////////////////////////////////////////////////////// 17.70 -void ring_buffer_delete(struct ring_buffer * rb) 17.71 +void 17.72 +ring_buffer_delete(struct ring_buffer * rb) 17.73 { 17.74 if (NULL != rb) free(rb->data); 17.75 free(rb);
18.1 --- a/src/ring_buffer.h Fri Sep 28 03:08:25 2012 -0500 18.2 +++ b/src/ring_buffer.h Fri Sep 28 18:24:53 2012 -0500 18.3 @@ -7,8 +7,9 @@ 18.4 18.5 struct ring_buffer * ring_buffer_new(size_t const size); 18.6 void ring_buffer_delete(struct ring_buffer * rb); 18.7 -void * ring_buffer_write(struct ring_buffer * rb, void * elem); 18.8 -void * ring_buffer_read(struct ring_buffer * rb); 18.9 -size_t ring_buffer_size(struct ring_buffer * rb); 18.10 + 18.11 +void * ring_buffer_write (struct ring_buffer * rb, void * elem); 18.12 +void * ring_buffer_read (struct ring_buffer * rb); 18.13 +size_t ring_buffer_size (struct ring_buffer * rb); 18.14 18.15 #endif
19.1 --- a/src/stack.h Fri Sep 28 03:08:25 2012 -0500 19.2 +++ b/src/stack.h Fri Sep 28 18:24:53 2012 -0500 19.3 @@ -7,8 +7,9 @@ 19.4 19.5 struct stack * stack_new(size_t const max); 19.6 void stack_delete(struct stack * s); 19.7 -void * stack_push(struct stack * s, void * elem); 19.8 -void * stack_pop(struct stack * s); 19.9 -size_t stack_size(struct stack * s); 19.10 + 19.11 +void * stack_push (struct stack * s, void * elem); 19.12 +void * stack_pop (struct stack * s); 19.13 +size_t stack_size (struct stack * s); 19.14 19.15 #endif