1 /* esl_red_black.c -- functions for implementing red-black trees */
2 #include "esl_config.h"
3
4 #include "easel.h"
5 #include "esl_red_black.h"
6 #define TEST_ITERATIONS 10000
7 //#define P7_CHECK_RED_BLACK // check tree for invariants after every change
8
9 #if defined(P7_CHECK_RED_BLACK) || defined(eslRED_BLACK_TESTDRIVE) // only compile these if we're using them in tests in order
10 // to keep GCC from complaining
11
12 // Checker function that we don't want visible everywhere
13 static int esl_red_black_doublekey_check_invariants(ESL_RED_BLACK_DOUBLEKEY *tree);
14 static int esl_red_black_doublekey_linked_list_test(ESL_RED_BLACK_DOUBLEKEY **head, ESL_RED_BLACK_DOUBLEKEY **tail);
15 #endif
16
17
esl_red_black_doublekey_Create()18 ESL_RED_BLACK_DOUBLEKEY * esl_red_black_doublekey_Create(){
19 int status; //return code from ESL_ALLOC. Needs to be declared so that the macro will compile
20 ESL_RED_BLACK_DOUBLEKEY *new_node;
21 ESL_ALLOC(new_node, sizeof(ESL_RED_BLACK_DOUBLEKEY));
22
23 new_node->parent = NULL;
24 new_node->large = NULL;
25 new_node->small = NULL;
26 return new_node;
27
28 // GOTO target used to catch error cases from ESL_ALLOC
29 ERROR:
30 return NULL;
31 }
32
33 void
esl_red_black_doublekey_Destroy(ESL_RED_BLACK_DOUBLEKEY * tree)34 esl_red_black_doublekey_Destroy(ESL_RED_BLACK_DOUBLEKEY *tree)
35 {
36 if (tree)
37 {
38 esl_red_black_doublekey_Destroy(tree->large);
39 esl_red_black_doublekey_Destroy(tree->small);
40 free(tree->contents);
41 free(tree);
42 }
43 }
44
45 void
esl_red_black_doublekey_linked_list_Destroy(ESL_RED_BLACK_DOUBLEKEY * head,ESL_RED_BLACK_DOUBLEKEY * tail)46 esl_red_black_doublekey_linked_list_Destroy(ESL_RED_BLACK_DOUBLEKEY *head, ESL_RED_BLACK_DOUBLEKEY *tail)
47 {
48 //int count=0;
49 if (head){
50 ESL_RED_BLACK_DOUBLEKEY *node = head;
51 while(node != tail){ // iterate around the circular loop until we
52 // get to where we started
53 ESL_RED_BLACK_DOUBLEKEY *next = node->small;
54 free(node->contents);
55 free(node);
56 node=next;
57 //count++;
58 }
59 }
60 // now free the tail node
61 free(tail->contents);
62 free(tail);
63 //count++;
64 //printf("esl_red_black_doublekey_linked_list_destroy freed %d nodes\n", count);
65 //note: we don't need to go down the tree->small path because the linked list is a set of nodes where large points to the next node
66 //in the list while small points to the previous, so there are no nodes on the small path that aren't also on the large
67 }
68
69
esl_red_black_doublekey_pool_Create(int number)70 ESL_RED_BLACK_DOUBLEKEY * esl_red_black_doublekey_pool_Create(int number){
71 int status; //return code from ESL_ALLOC. Needs to be declared so that the macro will compile
72 ESL_RED_BLACK_DOUBLEKEY *new_node;
73 ESL_ALLOC(new_node, number * sizeof(ESL_RED_BLACK_DOUBLEKEY));
74
75 // init nodes, forming into linked list by their larger pointers
76 int i;
77 for(i = 0; i < (number -1); i++){
78 new_node[i].parent = NULL;
79 new_node[i].large = &(new_node[i+1]);
80 new_node[i].small = NULL;
81 }
82
83 //special-case the last node in the chain
84 new_node[number-1].parent=NULL;
85 new_node[number-1].large=NULL;
86 new_node[number-1].small=NULL;
87
88 return new_node;
89
90 // GOTO target used to catch error cases from ESL_ALLOC
91 ERROR:
92 return NULL;
93 }
94
95 // Performs the rebalancings required to restore the red-black invariant in tree when node and its parent are both red
96 // returns the balanced tree. Assumes that someone else has checked to make sure that such a violation exists.
esl_red_black_doublekey_rebalance(ESL_RED_BLACK_DOUBLEKEY * tree,ESL_RED_BLACK_DOUBLEKEY * node)97 static ESL_RED_BLACK_DOUBLEKEY *esl_red_black_doublekey_rebalance(ESL_RED_BLACK_DOUBLEKEY *tree, ESL_RED_BLACK_DOUBLEKEY *node){
98
99 ESL_RED_BLACK_DOUBLEKEY *parent, *grandparent, *root, *uncle;
100
101 root = tree; // root starts out at the base of the original tree, but may change
102
103 parent = node->parent;
104 if (parent == NULL){
105 esl_fatal("Root node of tree passed to esl_red_black_doublekey_insert\n");
106 }
107
108 uint64_t parent_sibling_color;
109 grandparent = parent->parent;
110 if(grandparent == NULL){
111 esl_fatal("red-black violation: inserted node's parent was both red and graph root\n");
112 }
113
114 if(grandparent->large == parent){
115 // parent is the large child of its grandparent;
116 uncle = grandparent->small;
117 if(grandparent->small != NULL){
118 parent_sibling_color = grandparent->small->color;
119 }
120 else{
121 parent_sibling_color = ESL_RED_BLACK_COLOR_BLACK; // Null parent-sibling counts as
122 //black
123 }
124 }
125 else{
126 //parent is the small child of its grandparent
127 if(grandparent->large != NULL){
128 uncle = grandparent->large;
129 parent_sibling_color = grandparent->large->color;
130 }
131 else{
132 parent_sibling_color = ESL_RED_BLACK_COLOR_BLACK; // Null parent-sibling counts as
133 //black
134 }
135 }
136
137 //see http://pages.cs.wisc.edu/~paton/readings/Red-Black-Trees/
138 //for an explanation of the operations to restore red-black balance
139 //This code uses small = to the left on that page, large = to the right
140 if(parent_sibling_color == ESL_RED_BLACK_COLOR_RED){
141 // We need to push red to restore the red-black property
142 parent->color = ESL_RED_BLACK_COLOR_BLACK;
143 uncle->color = ESL_RED_BLACK_COLOR_BLACK;
144 grandparent->color = ESL_RED_BLACK_COLOR_RED;
145
146 if(grandparent->parent == NULL){
147 // grandparent is the top of the tree, so change its color back to black
148 // to maintain invariants
149 grandparent->color = ESL_RED_BLACK_COLOR_BLACK;
150 return tree;
151 }
152 else{
153 if(grandparent->parent->color == ESL_RED_BLACK_COLOR_RED){
154 //we've introduced a new red-red violation that we need to resolve
155 return esl_red_black_doublekey_rebalance(tree, grandparent);
156 }
157 }
158 }
159 else{
160 // need to do rotations
161 if(parent->small == node){
162 //We're on the small side of our parent
163 if(grandparent->small == parent){
164 // our parent was on the small side of our grandparent
165
166 grandparent->small = parent->large;
167 if(grandparent->small != NULL){
168 grandparent->small->parent = grandparent;
169 }
170
171 parent->large = grandparent;
172 if(grandparent->parent == NULL){
173 // grandparent was the original root of the tree
174 root = parent;
175 }
176 else{
177 //parent becomes the new child of great-grandparent
178 if(grandparent->parent->small == grandparent){
179 grandparent->parent->small = parent;
180 }
181 else{
182 grandparent->parent->large = parent;
183 }
184 }
185
186 parent->parent = grandparent->parent;
187 grandparent->parent = parent;
188
189 // done rotating, set the colors
190 parent->color = ESL_RED_BLACK_COLOR_BLACK;
191 grandparent->color = ESL_RED_BLACK_COLOR_RED;
192 node->color = ESL_RED_BLACK_COLOR_RED;
193 }
194 else{
195 // our parent was on the large side of our grandparent
196 if(grandparent->parent == NULL){
197 // grandparent was the root of the tree, so the node we're inserting
198 // becomes the new root
199 root = node;
200 }
201 else{
202 // current node replaces its grandparent as its great-grandparent's
203 // child
204 if(grandparent->parent->small == grandparent){
205 grandparent->parent->small = node;
206 }
207 else{
208 grandparent->parent->large = node;
209 }
210 }
211 node->parent = grandparent->parent;
212
213 grandparent->large = node->small;
214 if(grandparent->large != NULL){
215 grandparent->large->parent = grandparent;
216 }
217
218 parent->small = node->large;
219 if(parent->small != NULL){
220 parent->small->parent = parent;
221 }
222
223 node->small = grandparent;
224 grandparent->parent = node;
225
226 node->large = parent;
227 parent->parent = node;
228 node->color = ESL_RED_BLACK_COLOR_BLACK;
229 parent->color = ESL_RED_BLACK_COLOR_RED;
230 grandparent->color = ESL_RED_BLACK_COLOR_RED;
231 }
232 }
233 else{
234 //We're on the large side of our parent
235 if(grandparent->small == parent){
236 // our parent was on the small side of our grandparent
237
238 if(grandparent->parent == NULL){
239 // grandparent was the root of the tree, so the node we're inserting
240 // becomes the new root
241 root = node;
242 }
243 else{
244 // current node replaces its grandparent as its great-grandparent's
245 // child
246 if(grandparent->parent->small == grandparent){
247 grandparent->parent->small = node;
248 }
249 else{
250 grandparent->parent->large = node;
251 }
252 }
253 node->parent = grandparent->parent;
254
255 grandparent->small = node->large;
256 if(grandparent->small != NULL){
257 grandparent->small->parent = grandparent;
258 }
259
260 parent->large = node->small;
261 if(parent->large != NULL){
262 parent->large->parent = parent;
263 }
264
265 node->large = grandparent;
266 grandparent->parent = node;
267
268 node->small = parent;
269 parent->parent = node;
270 node->color = ESL_RED_BLACK_COLOR_BLACK;
271 parent->color = ESL_RED_BLACK_COLOR_RED;
272 grandparent->color = ESL_RED_BLACK_COLOR_RED;
273 }
274 else{
275 // our parent was on the large side of our grandparent
276 if(grandparent->parent == NULL){
277 // grandparent was the root of the tree
278 root = parent;
279 }
280 else{
281 //parent becomes the new child of great-grandparent
282 if(grandparent->parent->small == grandparent){
283 grandparent->parent->small = parent;
284 }
285 else{
286 grandparent->parent->large = parent;
287 }
288 }
289 parent->parent = grandparent->parent;
290
291 grandparent->large = parent->small;
292 if(parent->small != NULL){
293 parent->small->parent = grandparent;
294 }
295
296 parent->small = grandparent;
297 grandparent->parent = parent;
298
299 parent->color = ESL_RED_BLACK_COLOR_BLACK;
300 grandparent->color = ESL_RED_BLACK_COLOR_RED;
301 node->color = ESL_RED_BLACK_COLOR_RED;
302 }
303 }
304 }
305
306
307 #ifdef P7_CHECK_RED_BLACK
308 if(esl_red_black_doublekey_check_invariants(root) != eslOK){
309 printf("Red-black tree failed invariant check in esl_red_black_doublekey_insert\n");
310 }
311 #endif
312
313 return root; //return the modified tree
314 }
315
316
esl_red_black_doublekey_insert(ESL_RED_BLACK_DOUBLEKEY * tree,ESL_RED_BLACK_DOUBLEKEY * node)317 ESL_RED_BLACK_DOUBLEKEY * esl_red_black_doublekey_insert(ESL_RED_BLACK_DOUBLEKEY *tree, ESL_RED_BLACK_DOUBLEKEY *node){
318
319 node->color = ESL_RED_BLACK_COLOR_RED; //inserted nodes always start out red
320 node->small = NULL; // Inserted nodes have no children
321 node->large = NULL;
322
323 if(tree == NULL){
324 // tree is empty, so node is the new root
325 node->color = ESL_RED_BLACK_COLOR_BLACK; // root node is always black
326 return node;
327 }
328
329
330 // Otherwise, find the right place to insert the node
331 ESL_RED_BLACK_DOUBLEKEY *current, *parent;
332
333 current = tree; //start at the root of the tree
334
335 // tree-search to find the right insertion point
336 while(current != NULL){
337 parent = current;
338 if(node->key > current->key){
339 current = current->large;
340 }
341 else{
342 if(node->key < current->key){
343 current = current->small;
344 }
345 else{
346 // There was already a node in the tree with the same key, and we can't have
347 // two nodes in the tree with the same keys
348 return NULL;
349 }
350 }
351 }
352
353
354 //When we get here, parent contains the node that the new node will be a child of
355 node->parent = parent;
356 if(node->key < parent->key){
357 parent->small = node;
358 }
359 else{
360 parent->large = node;
361 } // note that parent->key == node->key would already have been detected and caused
362 // the insertion to fail.
363
364 // see if we need to rebalance
365 if(parent->color == ESL_RED_BLACK_COLOR_RED){
366 return(esl_red_black_doublekey_rebalance(tree, node));
367 }
368 else{
369 return(tree);
370 }
371 }
372
373
esl_red_black_doublekey_lookup(ESL_RED_BLACK_DOUBLEKEY * tree,double keyval)374 void * esl_red_black_doublekey_lookup(ESL_RED_BLACK_DOUBLEKEY *tree, double keyval){
375
376 ESL_RED_BLACK_DOUBLEKEY *current;
377
378 current = tree;
379
380 while(current != NULL){
381 if(current->key == keyval){ // We've found the node we're looking for
382 return(current->contents);
383 }
384 if(keyval > current->key){
385 current = current->large; // go down the large sub-tree
386 }
387 else{
388 current = current->small; // go down the small sub-tree
389 }
390 }
391
392 // if we get here, we searched to the bottom of the tree and didn't find
393 // what we were looking for
394 return NULL;
395
396 }
397
398
399 // Recursion function used by convert_to_sorted_linked. Using a separate recursion
400 // function allows us to do argument checking when the main function is called
401 // without having to repeat the argument check on each recursive sub-call.
esl_red_black_doublekey_convert_to_sorted_linked_recurse(ESL_RED_BLACK_DOUBLEKEY * tree,ESL_RED_BLACK_DOUBLEKEY ** head,ESL_RED_BLACK_DOUBLEKEY ** tail)402 static int esl_red_black_doublekey_convert_to_sorted_linked_recurse(ESL_RED_BLACK_DOUBLEKEY *tree, ESL_RED_BLACK_DOUBLEKEY **head, ESL_RED_BLACK_DOUBLEKEY **tail){
403
404 if(tree == NULL){
405 return eslOK; // Passing NULL tree to the recursion is fine, just means
406 // we've hit a leaf
407 }
408
409 // recursively sort the large side of the tree
410 esl_red_black_doublekey_convert_to_sorted_linked_recurse(tree->large, head, tail);
411
412 // add the current node to the sorted list
413
414 if(*tail != NULL){ // there was a large sub-tree of the original tree
415 tree->large = *tail; // node's key must be smaller than anything in its large sub-tree
416 (*tail)->small = tree;
417 }
418
419 if(*head == NULL){ // there weren't any nodes with larger keys than the root
420 *head = tree;
421 }
422 *tail = tree; //root of the tree is now the smallest node in the list
423
424 esl_red_black_doublekey_convert_to_sorted_linked_recurse(tree->small, head, tail);
425 return eslOK;
426
427
428 }
429
430 // Converts the input red-black tree into a doubly-linked list. Returns eslOK if the conversion
431 // succeeded. Returns a pointer to the node with the largest key in head, a pointer to the node
432 // with the smallest key in tail
433 // Code based on algorithm from http://www.geeksforgeeks.org/convert-a-given-binary-tree-to-doubly-linked-list-set-4/
esl_red_black_doublekey_convert_to_sorted_linked(ESL_RED_BLACK_DOUBLEKEY * tree,ESL_RED_BLACK_DOUBLEKEY ** head,ESL_RED_BLACK_DOUBLEKEY ** tail)434 int esl_red_black_doublekey_convert_to_sorted_linked(ESL_RED_BLACK_DOUBLEKEY *tree, ESL_RED_BLACK_DOUBLEKEY **head, ESL_RED_BLACK_DOUBLEKEY **tail){
435 if(tree == NULL){
436 return eslFAIL; // Can't proceed with a NULL base tree
437 }
438
439 // clear the head and tail pointers to avoid confusion if they were previously used
440 *head = NULL;
441 *tail = NULL;
442 esl_red_black_doublekey_convert_to_sorted_linked_recurse(tree, head, tail);
443 /*// recursively sort the large side of the tree
444 esl_red_black_doublekey_convert_to_sorted_linked_recurse(tree->large, head, tail);
445
446 // add the current node to the sorted list
447
448 if(*tail != NULL){ // there was a large sub-tree of the original tree
449 tree->large = *tail; // node's key must be smaller than anything in its large sub-tree
450 (*tail)->small = tree;
451 }
452
453 if(*head == NULL){ // there weren't any nodes with larger keys than the root
454 *head = tree;
455 }
456 *tail = tree; //root of the tree is now the smallest node in the list
457
458 esl_red_black_doublekey_convert_to_sorted_linked_recurse(tree->small, head, tail);
459 */
460 return eslOK;
461
462 }
463
464 #if defined(P7_CHECK_RED_BLACK) || defined(eslRED_BLACK_TESTDRIVE) // only compile these if we're using them in tests in order
465 // to keep GCC from complaining
466
467 // Checks a red-black tree to see if it maintains the red-black invaiants
468 // returns eslOK if so, eslFAIL if not
esl_red_black_doublekey_check_invariants(ESL_RED_BLACK_DOUBLEKEY * tree)469 int esl_red_black_doublekey_check_invariants(ESL_RED_BLACK_DOUBLEKEY *tree){
470 if(tree == NULL){
471 return eslFAIL; // Why are you calling this on a NULL tree?
472 }
473
474 if((tree->parent == NULL) && (tree->color !=ESL_RED_BLACK_COLOR_BLACK)){
475 printf("Detected red root node in esl_red_black_doublekey_check_invariants\n");
476 return eslFAIL;
477 }
478
479 if(tree->color == ESL_RED_BLACK_COLOR_RED){
480 //need to check our parent and children for no-double-red invariant
481 if(tree->parent != NULL){
482 if(tree->parent->color == ESL_RED_BLACK_COLOR_RED){
483 printf("Detected red parent of red node in esl_red_black_doublekey_check_invariants\n");
484 return eslFAIL;
485 }
486 }
487 if(tree->small != NULL){
488 if(tree->small->color == ESL_RED_BLACK_COLOR_RED){
489 printf("Detected red small child of red node in esl_red_black_doublekey_check_invariants\n");
490 return eslFAIL;
491 }
492 }
493 if(tree->large != NULL){
494 if(tree->large->color == ESL_RED_BLACK_COLOR_RED){
495 printf("Detected red large child of red node in esl_red_black_doublekey_check_invariants\n");
496 return eslFAIL;
497 }
498 }
499 }
500
501 // now, check connectivity of this node
502 if(tree->parent != NULL){
503 if((tree->parent->small != tree) && (tree->parent->large != tree)){
504 printf("Node's parent didn't have it as a child in esl_red_black_doublekey_check_invariants\n");
505 return eslFAIL;
506 }
507
508 if((tree->parent->small == tree) && (tree->parent->large == tree)){
509 printf("Node was both the small and large child of its parent in esl_red_black_doublekey_check_invariants\n");
510 return eslFAIL;
511 }
512 }
513 if(tree->small != NULL){
514 if(tree->small->parent != tree){
515 printf("Node's small child didn't have it as a parent in esl_red_black_doublekey_check_invariants\n");
516 }
517 }
518 if(tree->large != NULL){
519 if(tree->large->parent != tree){
520 printf("Node's large child didn't have it as a parent in esl_red_black_doublekey_check_invariants\n");
521 }
522 }
523
524 //If we get this far, then the current node maintains all the invariants we can easily
525 //check, so recurse
526 if((tree->small != NULL) && (esl_red_black_doublekey_check_invariants(tree->small) != eslOK)){
527 return eslFAIL;
528 }
529 if((tree->large != NULL) && (esl_red_black_doublekey_check_invariants(tree->large) != eslOK)){
530 return eslFAIL;
531 }
532
533 // If we get this far, then we haven't failed any of the checks and therefore have passed
534 return eslOK;
535 }
536
esl_red_black_doublekey_linked_list_test(ESL_RED_BLACK_DOUBLEKEY ** head,ESL_RED_BLACK_DOUBLEKEY ** tail)537 int esl_red_black_doublekey_linked_list_test(ESL_RED_BLACK_DOUBLEKEY **head, ESL_RED_BLACK_DOUBLEKEY **tail){
538 if((head == NULL )|| (tail==NULL)){
539 printf("Invalid head or tail pointer passed to esl_red_black_doublekey_linked_list_test\n");
540 return eslFAIL;
541 }
542 int count1=0;
543 int count2=0;
544 ESL_RED_BLACK_DOUBLEKEY *head_ptr = *head;
545 ESL_RED_BLACK_DOUBLEKEY *tail_ptr = *tail;
546 ESL_RED_BLACK_DOUBLEKEY *prev;
547 //start at the small end of the chain
548 while(tail_ptr != NULL){
549 count1++;
550 prev = tail_ptr;
551 if(tail_ptr->large != NULL){
552 if(tail_ptr->large->key <= tail_ptr->key){
553 esl_fatal("Mis-ordered keys when checking from low to high in esl_red_black_doublekey_linked_list_test\n");
554 return eslFAIL;
555 }
556 if(tail_ptr->large->small != tail_ptr){
557 esl_fatal("Incorrectly connected list when checking from low to high in esl_red_black_doublekey_linked_list_test\n");
558 return eslFAIL;
559 }
560 }
561 tail_ptr = tail_ptr->large;
562 }
563 if(prev != head_ptr){
564 esl_fatal("Traversing list from small to large didn't reach head in esl_red_black_doublekey_linked_list_test\n");
565 return eslFAIL;
566 }
567
568 //reset everything and go from big->small
569 head_ptr = *head;
570 tail_ptr = *tail;
571 while(head_ptr != NULL){
572 count2++;
573 prev = head_ptr;
574 if(head_ptr->small != NULL){
575 if(head_ptr->small->key >= head_ptr->key){
576 printf("Mis-ordered keys when checking from high to low in esl_red_black_doublekey_linked_list_test\n");
577 return eslFAIL;
578 }
579 if(head_ptr->small->large != head_ptr){
580 printf("Incorrectly connected list when checking from high to low in esl_red_black_doublekey_linked_list_test\n");
581 return eslFAIL;
582 }
583 }
584 head_ptr = head_ptr->small;
585 }
586 if(prev != tail_ptr){
587 printf("Traversing list from large to small didn't reach tail in esl_red_black_doublekey_linked_list_test\n");
588 return eslFAIL;
589 }
590 if (count1 != count2){
591 printf("Found %i nodes when going from large->small, but %i going in the other direction in esl_red_black_doublekey_linked_list_testn\n", count1, count2);
592 return eslFAIL;
593 }
594 else{
595 // printf("Found %i nodes going in both directions in esl_red_black_doublekey_linked_list_testn\n", count1);
596 // If we get here, we haven't failed any of the tests, so have succeeded
597 return eslOK;
598 }
599 }
600
601 /* Computes the maximum depth (depth of the deepest leaf) of a red-black tree */
esl_red_black_doublekey_max_depth(ESL_RED_BLACK_DOUBLEKEY * tree)602 uint32_t esl_red_black_doublekey_max_depth(ESL_RED_BLACK_DOUBLEKEY *tree){
603 uint32_t large_max, small_max;
604 if(tree == NULL){
605 return 0;
606 }
607 large_max = esl_red_black_doublekey_max_depth(tree->large);
608 small_max = esl_red_black_doublekey_max_depth(tree->small);
609 if(large_max > small_max){
610 return (large_max + 1);
611 }
612 else{
613 return (small_max + 1);
614 }
615 }
616 /* Computes the minimum depth (depth of the shallowest leaf) of a red-black tree */
esl_red_black_doublekey_min_depth(ESL_RED_BLACK_DOUBLEKEY * tree)617 uint32_t esl_red_black_doublekey_min_depth(ESL_RED_BLACK_DOUBLEKEY *tree){
618 uint32_t large_min, small_min;
619 if(tree == NULL){
620 return 0;
621 }
622 large_min = esl_red_black_doublekey_min_depth(tree->large);
623 small_min = esl_red_black_doublekey_min_depth(tree->small);
624 if(large_min > small_min){
625 return (small_min + 1);
626 }
627 else{
628 return (large_min + 1);
629 }
630 }
631 #endif
632
633 /*******************************************************************************************/
634 /* Unit test. Creates a red-black tree. Verifies that the tree obeys the */
635 /* red-black invariant. Finally, converts the tree into */
636 /* a sorted linked list and verifies the correctness of that list */
637 /*******************************************************************************************/
638
639 #ifdef eslRED_BLACK_TESTDRIVE
640 /* gcc -g -Wall -o test -I. -L. -DeslCLUSTER_TESTDRIVE esl_cluster.c -leasel -lm
641 */
642 #include "esl_config.h"
643
644 #include <stdio.h>
645 #include <stdlib.h>
646
647 #include "easel.h"
648 #include "esl_getopts.h"
649
650 int
main(int argc,char ** argv)651 main(int argc, char **argv)
652 {
653
654 ESL_RED_BLACK_DOUBLEKEY *tree, *new_tree, *node, **head, **tail;
655 int i;
656 ESL_RED_BLACK_DOUBLEKEY *head_ptr, *tail_ptr;
657
658 head_ptr = NULL;
659 tail_ptr = NULL;
660 head = &head_ptr; // need someplace to write return values
661 tail = &tail_ptr;
662 double my_key = 0.0;
663 int runs;
664 for(runs = 0; runs < 2; runs++){
665 tree = NULL;
666 for(i=0; i < TEST_ITERATIONS; i++){
667 node = esl_red_black_doublekey_Create(); // get a new node
668 new_tree = NULL;
669 double *contents = malloc(sizeof(double));
670 while(new_tree == NULL){ // handle the case where we generate the
671 // same random number twice
672 my_key = ((double)rand()/(double)RAND_MAX) * 1000;
673 node->key = my_key; // set its key
674 *contents = my_key;
675 node->contents = contents;
676 new_tree = esl_red_black_doublekey_insert(tree, node);
677 }
678 tree = new_tree;
679 if(0){
680 double *foo = (double *) esl_red_black_doublekey_lookup(tree, my_key);
681 if(foo == NULL || *foo != my_key){
682 esl_fatal("Failed to find key %lf after insertion\n", my_key);
683 }
684 if(esl_red_black_doublekey_max_depth(tree) > (2 * esl_red_black_doublekey_min_depth(tree))){
685 esl_fatal("Unbalanced tree found on iteration %d: maximum depth was %d, tree minimum depth was %d\n",i, esl_red_black_doublekey_max_depth(tree), esl_red_black_doublekey_min_depth(tree));
686 }
687 /* Check generated tree for consistency */
688 if(esl_red_black_doublekey_check_invariants(tree) != eslOK){
689 esl_fatal("Generated tree did not obey red-black invariants\n");
690 }
691 }
692 }
693 //printf("Tree maximum depth was %d, tree minimum depth was %d\n", esl_red_black_doublekey_max_depth(tree), esl_red_black_doublekey_min_depth(tree));
694 /* Check generated tree for consistency */
695 if(esl_red_black_doublekey_check_invariants(tree) != eslOK){
696 esl_fatal("Generated tree did not obey red-black invariants\n");
697 }
698
699 if(esl_red_black_doublekey_convert_to_sorted_linked(tree, head, tail) != eslOK){
700 esl_fatal("Conversion of tree to linked list failed\n");
701 }
702 if(esl_red_black_doublekey_linked_list_test(head, tail) != eslOK){
703 esl_fatal("Linked list failed consistency check\n");
704 }
705 esl_red_black_doublekey_linked_list_Destroy(*head, *tail);
706 }
707 for(runs = 0; runs < 2; runs++){
708 tree = NULL;
709 double keys[TEST_ITERATIONS];
710 for(i=0; i < TEST_ITERATIONS; i++){
711 // generate "random" floating-point number between 0 and 100000
712 node = esl_red_black_doublekey_Create(); // get a new node
713 double *contents = malloc(sizeof(double));
714 new_tree = NULL;
715 while(new_tree == NULL){ // handle the case where we generate the
716 // same random number twice
717 my_key = ((double)rand()/(double)RAND_MAX) * 1000;
718 node->key = my_key; // set its key
719 *contents = my_key;
720 keys[i] = my_key;
721 node->contents = contents;
722 new_tree = esl_red_black_doublekey_insert(tree, node);
723 }
724 tree = new_tree;
725 if(0){
726 double *foo = (double *) esl_red_black_doublekey_lookup(tree, my_key);
727 if(foo == NULL || *foo != my_key){
728 esl_fatal("Failed to find key %lf after insertion\n", my_key);
729 }
730 if(esl_red_black_doublekey_max_depth(tree) > (2 * esl_red_black_doublekey_min_depth(tree))){
731 esl_fatal("Unbalanced tree found on iteration %d: maximum depth was %d, tree minimum depth was %d\n",i, esl_red_black_doublekey_max_depth(tree), esl_red_black_doublekey_min_depth(tree));
732 }
733 /* Check generated tree for consistency */
734 if(esl_red_black_doublekey_check_invariants(tree) != eslOK){
735 esl_fatal("Generated tree did not obey red-black invariants\n");
736 }
737 }
738 }
739 //printf("Tree maximum depth was %d, tree minimum depth was %d\n", esl_red_black_doublekey_max_depth(tree), esl_red_black_doublekey_min_depth(tree));
740 /* Check generated tree for consistency */
741 if(esl_red_black_doublekey_check_invariants(tree) != eslOK){
742 esl_fatal("Generated tree did not obey red-black invariants\n");
743 }
744
745 for(i = 0; i < TEST_ITERATIONS; i++){
746 double *foo = (double *) esl_red_black_doublekey_lookup(tree, keys[i]);
747 if(foo == NULL || *foo != keys[i]){
748 esl_fatal("Failed to find key %lf at end of test 2, got %lf instead\n", keys[i], foo);
749 }
750 }
751 esl_red_black_doublekey_Destroy(tree);
752 }
753 return 0;
754 }
755
756 #endif
757