1/* $Id$Revision: */
2/* vim:set shiftwidth=4 ts=8: */
3
4/**********************************************************
5* See the LICENSE file for copyright information. *
6**********************************************************/
7
8#include "config.h"
9
10#include "red_black_tree.h"
11#include "stdio.h"
12
13/***********************************************************************/
14/* FUNCTION: RBTreeCreate */
15/**/
16/* INPUTS: All the inputs are names of functions. CompFunc takes to */
17/* void pointers to keys and returns 1 if the first argument is */
18/* "greater than" the second. DestFunc takes a pointer to a key and */
19/* destroys it in the appropriate manner when the node containing that */
20/* key is deleted. InfoDestFunc is similar to DestFunc except it */
21/* receives a pointer to the info of a node and destroys it. */
22/* PrintFunc receives a pointer to the key of a node and prints it. */
23/* PrintInfo receives a pointer to the info of a node and prints it. */
24/* If RBTreePrint is never called the print functions don't have to be */
25/* defined and NullFunction can be used. */
26/**/
27/* OUTPUT: This function returns a pointer to the newly created */
28/* red-black tree. */
29/**/
30/* Modifies Input: none */
31/***********************************************************************/
32
33rb_red_blk_tree* RBTreeCreate( int (*CompFunc) (const void*,const void*),
34 void (*DestFunc) (void*),
35 void (*InfoDestFunc) (void*),
36 void (*PrintFunc) (const void*),
37 void (*PrintInfo)(void*)) {
38 rb_red_blk_tree* newTree = NULL;
39 rb_red_blk_node* temp;
40
41 if (setjmp(rb_jbuf)) {
42 if (newTree) {
43 if (newTree->nil) free (newTree->nil);
44 free (newTree);
45 }
46 return NULL;
47 }
48 newTree=(rb_red_blk_tree*) SafeMalloc(sizeof(rb_red_blk_tree));
49 newTree->nil = newTree->root = NULL;
50 newTree->Compare= CompFunc;
51 newTree->DestroyKey= DestFunc;
52 newTree->PrintKey= PrintFunc;
53 newTree->PrintInfo= PrintInfo;
54 newTree->DestroyInfo= InfoDestFunc;
55
56 /* see the comment in the rb_red_blk_tree structure in red_black_tree.h */
57 /* for information on nil and root */
58 temp=newTree->nil= (rb_red_blk_node*) SafeMalloc(sizeof(rb_red_blk_node));
59 temp->parent=temp->left=temp->right=temp;
60 temp->red=0;
61 temp->key=0;
62 temp=newTree->root= (rb_red_blk_node*) SafeMalloc(sizeof(rb_red_blk_node));
63 temp->parent=temp->left=temp->right=newTree->nil;
64 temp->key=0;
65 temp->red=0;
66 return(newTree);
67}
68
69/***********************************************************************/
70/* FUNCTION: LeftRotate */
71/**/
72/* INPUTS: This takes a tree so that it can access the appropriate */
73/* root and nil pointers, and the node to rotate on. */
74/**/
75/* OUTPUT: None */
76/**/
77/* Modifies Input: tree, x */
78/**/
79/* EFFECTS: Rotates as described in _Introduction_To_Algorithms by */
80/* Cormen, Leiserson, Rivest (Chapter 14). Basically this */
81/* makes the parent of x be to the left of x, x the parent of */
82/* its parent before the rotation and fixes other pointers */
83/* accordingly. */
84/***********************************************************************/
85
86void LeftRotate(rb_red_blk_tree* tree, rb_red_blk_node* x) {
87 rb_red_blk_node* y;
88 rb_red_blk_node* nil=tree->nil;
89
90 /* I originally wrote this function to use the sentinel for */
91 /* nil to avoid checking for nil. However this introduces a */
92 /* very subtle bug because sometimes this function modifies */
93 /* the parent pointer of nil. This can be a problem if a */
94 /* function which calls LeftRotate also uses the nil sentinel */
95 /* and expects the nil sentinel's parent pointer to be unchanged */
96 /* after calling this function. For example, when RBDeleteFixUP */
97 /* calls LeftRotate it expects the parent pointer of nil to be */
98 /* unchanged. */
99
100 y=x->right;
101 x->right=y->left;
102
103 if (y->left != nil) y->left->parent=x; /* used to use sentinel here */
104 /* and do an unconditional assignment instead of testing for nil */
105
106 y->parent=x->parent;
107
108 /* instead of checking if x->parent is the root as in the book, we */
109 /* count on the root sentinel to implicitly take care of this case */
110 if( x == x->parent->left) {
111 x->parent->left=y;
112 } else {
113 x->parent->right=y;
114 }
115 y->left=x;
116 x->parent=y;
117
118#ifdef DEBUG_ASSERT
119 Assert(!tree->nil->red,"nil not red in LeftRotate");
120#endif
121}
122
123
124/***********************************************************************/
125/* FUNCTION: RighttRotate */
126/**/
127/* INPUTS: This takes a tree so that it can access the appropriate */
128/* root and nil pointers, and the node to rotate on. */
129/**/
130/* OUTPUT: None */
131/**/
132/* Modifies Input?: tree, y */
133/**/
134/* EFFECTS: Rotates as described in _Introduction_To_Algorithms by */
135/* Cormen, Leiserson, Rivest (Chapter 14). Basically this */
136/* makes the parent of x be to the left of x, x the parent of */
137/* its parent before the rotation and fixes other pointers */
138/* accordingly. */
139/***********************************************************************/
140
141void RightRotate(rb_red_blk_tree* tree, rb_red_blk_node* y) {
142 rb_red_blk_node* x;
143 rb_red_blk_node* nil=tree->nil;
144
145 /* I originally wrote this function to use the sentinel for */
146 /* nil to avoid checking for nil. However this introduces a */
147 /* very subtle bug because sometimes this function modifies */
148 /* the parent pointer of nil. This can be a problem if a */
149 /* function which calls LeftRotate also uses the nil sentinel */
150 /* and expects the nil sentinel's parent pointer to be unchanged */
151 /* after calling this function. For example, when RBDeleteFixUP */
152 /* calls LeftRotate it expects the parent pointer of nil to be */
153 /* unchanged. */
154
155 x=y->left;
156 y->left=x->right;
157
158 if (nil != x->right) x->right->parent=y; /*used to use sentinel here */
159 /* and do an unconditional assignment instead of testing for nil */
160
161 /* instead of checking if x->parent is the root as in the book, we */
162 /* count on the root sentinel to implicitly take care of this case */
163 x->parent=y->parent;
164 if( y == y->parent->left) {
165 y->parent->left=x;
166 } else {
167 y->parent->right=x;
168 }
169 x->right=y;
170 y->parent=x;
171
172#ifdef DEBUG_ASSERT
173 Assert(!tree->nil->red,"nil not red in RightRotate");
174#endif
175}
176
177/***********************************************************************/
178/* FUNCTION: TreeInsertHelp */
179/**/
180/* INPUTS: tree is the tree to insert into and z is the node to insert */
181/**/
182/* OUTPUT: none */
183/**/
184/* Modifies Input: tree, z */
185/**/
186/* EFFECTS: Inserts z into the tree as if it were a regular binary tree */
187/* using the algorithm described in _Introduction_To_Algorithms_ */
188/* by Cormen et al. This function is only intended to be called */
189/* by the RBTreeInsert function and not by the user */
190/***********************************************************************/
191
192void TreeInsertHelp(rb_red_blk_tree* tree, rb_red_blk_node* z) {
193 /* This function should only be called by InsertRBTree (see above) */
194 rb_red_blk_node* x;
195 rb_red_blk_node* y;
196 rb_red_blk_node* nil=tree->nil;
197
198 z->left=z->right=nil;
199 y=tree->root;
200 x=tree->root->left;
201 while( x != nil) {
202 y=x;
203 if (1 == tree->Compare(x->key,z->key)) { /* x.key > z.key */
204 x=x->left;
205 } else { /* x,key <= z.key */
206 x=x->right;
207 }
208 }
209 z->parent=y;
210 if ( (y == tree->root) ||
211 (1 == tree->Compare(y->key,z->key))) { /* y.key > z.key */
212 y->left=z;
213 } else {
214 y->right=z;
215 }
216
217#ifdef DEBUG_ASSERT
218 Assert(!tree->nil->red,"nil not red in TreeInsertHelp");
219#endif
220}
221
222/* Before calling Insert RBTree the node x should have its key set */
223
224/***********************************************************************/
225/* FUNCTION: RBTreeInsert */
226/**/
227/* INPUTS: tree is the red-black tree to insert a node which has a key */
228/* pointed to by key and info pointed to by info. */
229/**/
230/* OUTPUT: This function returns a pointer to the newly inserted node */
231/* which is guarunteed to be valid until this node is deleted. */
232/* What this means is if another data structure stores this */
233/* pointer then the tree does not need to be searched when this */
234/* is to be deleted. */
235/**/
236/* Modifies Input: tree */
237/**/
238/* EFFECTS: Creates a node node which contains the appropriate key and */
239/* info pointers and inserts it into the tree. */
240/***********************************************************************/
241
242rb_red_blk_node * RBTreeInsert(rb_red_blk_tree* tree, void* key, void* info) {
243 rb_red_blk_node * y;
244 rb_red_blk_node * x;
245 rb_red_blk_node * newNode;
246
247 if (setjmp(rb_jbuf))
248 return NULL;
249 x=(rb_red_blk_node*) SafeMalloc(sizeof(rb_red_blk_node));
250 x->key=key;
251 x->info=info;
252
253 TreeInsertHelp(tree,x);
254 newNode=x;
255 x->red=1;
256 while(x->parent->red) { /* use sentinel instead of checking for root */
257 if (x->parent == x->parent->parent->left) {
258 y=x->parent->parent->right;
259 if (y->red) {
260 x->parent->red=0;
261 y->red=0;
262 x->parent->parent->red=1;
263 x=x->parent->parent;
264 } else {
265 if (x == x->parent->right) {
266 x=x->parent;
267 LeftRotate(tree,x);
268 }
269 x->parent->red=0;
270 x->parent->parent->red=1;
271 RightRotate(tree,x->parent->parent);
272 }
273 } else { /* case for x->parent == x->parent->parent->right */
274 y=x->parent->parent->left;
275 if (y->red) {
276 x->parent->red=0;
277 y->red=0;
278 x->parent->parent->red=1;
279 x=x->parent->parent;
280 } else {
281 if (x == x->parent->left) {
282 x=x->parent;
283 RightRotate(tree,x);
284 }
285 x->parent->red=0;
286 x->parent->parent->red=1;
287 LeftRotate(tree,x->parent->parent);
288 }
289 }
290 }
291 tree->root->left->red=0;
292 return(newNode);
293
294#ifdef DEBUG_ASSERT
295 Assert(!tree->nil->red,"nil not red in RBTreeInsert");
296 Assert(!tree->root->red,"root not red in RBTreeInsert");
297#endif
298}
299
300/***********************************************************************/
301/* FUNCTION: TreeSuccessor */
302/**/
303/* INPUTS: tree is the tree in question, and x is the node we want the */
304/* the successor of. */
305/**/
306/* OUTPUT: This function returns the successor of x or NULL if no */
307/* successor exists. */
308/**/
309/* Modifies Input: none */
310/**/
311/* Note: uses the algorithm in _Introduction_To_Algorithms_ */
312/***********************************************************************/
313
314rb_red_blk_node* TreeSuccessor(rb_red_blk_tree* tree,rb_red_blk_node* x) {
315 rb_red_blk_node* y;
316 rb_red_blk_node* nil=tree->nil;
317 rb_red_blk_node* root=tree->root;
318
319 if (nil != (y = x->right)) { /* assignment to y is intentional */
320 while(y->left != nil) { /* returns the minium of the right subtree of x */
321 y=y->left;
322 }
323 return(y);
324 } else {
325 y=x->parent;
326 while(x == y->right) { /* sentinel used instead of checking for nil */
327 x=y;
328 y=y->parent;
329 }
330 if (y == root) return(nil);
331 return(y);
332 }
333}
334
335/***********************************************************************/
336/* FUNCTION: Treepredecessor */
337/**/
338/* INPUTS: tree is the tree in question, and x is the node we want the */
339/* the predecessor of. */
340/**/
341/* OUTPUT: This function returns the predecessor of x or NULL if no */
342/* predecessor exists. */
343/**/
344/* Modifies Input: none */
345/**/
346/* Note: uses the algorithm in _Introduction_To_Algorithms_ */
347/***********************************************************************/
348
349rb_red_blk_node* TreePredecessor(rb_red_blk_tree* tree, rb_red_blk_node* x) {
350 rb_red_blk_node* y;
351 rb_red_blk_node* nil=tree->nil;
352 rb_red_blk_node* root=tree->root;
353
354 if (nil != (y = x->left)) { /* assignment to y is intentional */
355 while(y->right != nil) { /* returns the maximum of the left subtree of x */
356 y=y->right;
357 }
358 return(y);
359 } else {
360 y=x->parent;
361 while(x == y->left) {
362 if (y == root) return(nil);
363 x=y;
364 y=y->parent;
365 }
366 return(y);
367 }
368}
369
370/***********************************************************************/
371/* FUNCTION: InorderTreePrint */
372/**/
373/* INPUTS: tree is the tree to print and x is the current inorder node */
374/**/
375/* OUTPUT: none */
376/**/
377/* EFFECTS: This function recursively prints the nodes of the tree */
378/* inorder using the PrintKey and PrintInfo functions. */
379/**/
380/* Modifies Input: none */
381/**/
382/* Note: This function should only be called from RBTreePrint */
383/***********************************************************************/
384
385void InorderTreePrint(rb_red_blk_tree* tree, rb_red_blk_node* x) {
386 rb_red_blk_node* nil=tree->nil;
387 rb_red_blk_node* root=tree->root;
388 if (x != tree->nil) {
389 InorderTreePrint(tree,x->left);
390 printf("info=");
391 tree->PrintInfo(x->info);
392 printf(" key=");
393 tree->PrintKey(x->key);
394 printf(" l->key=");
395 if( x->left == nil) printf("NULL"); else tree->PrintKey(x->left->key);
396 printf(" r->key=");
397 if( x->right == nil) printf("NULL"); else tree->PrintKey(x->right->key);
398 printf(" p->key=");
399 if( x->parent == root) printf("NULL"); else tree->PrintKey(x->parent->key);
400 printf(" red=%i\n",x->red);
401 InorderTreePrint(tree,x->right);
402 }
403}
404
405
406/***********************************************************************/
407/* FUNCTION: TreeDestHelper */
408/**/
409/* INPUTS: tree is the tree to destroy and x is the current node */
410/**/
411/* OUTPUT: none */
412/**/
413/* EFFECTS: This function recursively destroys the nodes of the tree */
414/* postorder using the DestroyKey and DestroyInfo functions. */
415/**/
416/* Modifies Input: tree, x */
417/**/
418/* Note: This function should only be called by RBTreeDestroy */
419/***********************************************************************/
420
421void TreeDestHelper(rb_red_blk_tree* tree, rb_red_blk_node* x) {
422 rb_red_blk_node* nil=tree->nil;
423 if (x != nil) {
424 TreeDestHelper(tree,x->left);
425 TreeDestHelper(tree,x->right);
426 tree->DestroyKey(x->key);
427 tree->DestroyInfo(x->info);
428 free(x);
429 }
430}
431
432
433/***********************************************************************/
434/* FUNCTION: RBTreeDestroy */
435/**/
436/* INPUTS: tree is the tree to destroy */
437/**/
438/* OUTPUT: none */
439/**/
440/* EFFECT: Destroys the key and frees memory */
441/**/
442/* Modifies Input: tree */
443/**/
444/***********************************************************************/
445
446void RBTreeDestroy(rb_red_blk_tree* tree) {
447 TreeDestHelper(tree,tree->root->left);
448 free(tree->root);
449 free(tree->nil);
450 free(tree);
451}
452
453
454/***********************************************************************/
455/* FUNCTION: RBTreePrint */
456/**/
457/* INPUTS: tree is the tree to print */
458/**/
459/* OUTPUT: none */
460/**/
461/* EFFECT: This function recursively prints the nodes of the tree */
462/* inorder using the PrintKey and PrintInfo functions. */
463/**/
464/* Modifies Input: none */
465/**/
466/***********************************************************************/
467
468void RBTreePrint(rb_red_blk_tree* tree) {
469 InorderTreePrint(tree,tree->root->left);
470}
471
472
473/***********************************************************************/
474/* FUNCTION: RBExactQuery */
475/**/
476/* INPUTS: tree is the tree to print and q is a pointer to the key */
477/* we are searching for */
478/**/
479/* OUTPUT: returns the a node with key equal to q. If there are */
480/* multiple nodes with key equal to q this function returns */
481/* the one highest in the tree */
482/**/
483/* Modifies Input: none */
484/**/
485/***********************************************************************/
486
487rb_red_blk_node* RBExactQuery(rb_red_blk_tree* tree, void* q) {
488 rb_red_blk_node* x=tree->root->left;
489 rb_red_blk_node* nil=tree->nil;
490 int compVal;
491 if (x == nil) return(0);
492 compVal=tree->Compare(x->key,(int*) q);
493 while(0 != compVal) {/*assignemnt*/
494 if (1 == compVal) { /* x->key > q */
495 x=x->left;
496 } else {
497 x=x->right;
498 }
499 if ( x == nil) return(0);
500 compVal=tree->Compare(x->key,(int*) q);
501 }
502 return(x);
503}
504
505
506/***********************************************************************/
507/* FUNCTION: RBDeleteFixUp */
508/**/
509/* INPUTS: tree is the tree to fix and x is the child of the spliced */
510/* out node in RBTreeDelete. */
511/**/
512/* OUTPUT: none */
513/**/
514/* EFFECT: Performs rotations and changes colors to restore red-black */
515/* properties after a node is deleted */
516/**/
517/* Modifies Input: tree, x */
518/**/
519/* The algorithm from this function is from _Introduction_To_Algorithms_ */
520/***********************************************************************/
521
522void RBDeleteFixUp(rb_red_blk_tree* tree, rb_red_blk_node* x) {
523 rb_red_blk_node* root=tree->root->left;
524 rb_red_blk_node* w;
525
526 while( (!x->red) && (root != x)) {
527 if (x == x->parent->left) {
528 w=x->parent->right;
529 if (w->red) {
530 w->red=0;
531 x->parent->red=1;
532 LeftRotate(tree,x->parent);
533 w=x->parent->right;
534 }
535 if ( (!w->right->red) && (!w->left->red) ) {
536 w->red=1;
537 x=x->parent;
538 } else {
539 if (!w->right->red) {
540 w->left->red=0;
541 w->red=1;
542 RightRotate(tree,w);
543 w=x->parent->right;
544 }
545 w->red=x->parent->red;
546 x->parent->red=0;
547 w->right->red=0;
548 LeftRotate(tree,x->parent);
549 x=root; /* this is to exit while loop */
550 }
551 } else { /* the code below is has left and right switched from above */
552 w=x->parent->left;
553 if (w->red) {
554 w->red=0;
555 x->parent->red=1;
556 RightRotate(tree,x->parent);
557 w=x->parent->left;
558 }
559 if ( (!w->right->red) && (!w->left->red) ) {
560 w->red=1;
561 x=x->parent;
562 } else {
563 if (!w->left->red) {
564 w->right->red=0;
565 w->red=1;
566 LeftRotate(tree,w);
567 w=x->parent->left;
568 }
569 w->red=x->parent->red;
570 x->parent->red=0;
571 w->left->red=0;
572 RightRotate(tree,x->parent);
573 x=root; /* this is to exit while loop */
574 }
575 }
576 }
577 x->red=0;
578
579#ifdef DEBUG_ASSERT
580 Assert(!tree->nil->red,"nil not black in RBDeleteFixUp");
581#endif
582}
583
584
585/***********************************************************************/
586/* FUNCTION: RBDelete */
587/**/
588/* INPUTS: tree is the tree to delete node z from */
589/**/
590/* OUTPUT: none */
591/**/
592/* EFFECT: Deletes z from tree and frees the key and info of z */
593/* using DestoryKey and DestoryInfo. Then calls */
594/* RBDeleteFixUp to restore red-black properties */
595/**/
596/* Modifies Input: tree, z */
597/**/
598/* The algorithm from this function is from _Introduction_To_Algorithms_ */
599/***********************************************************************/
600
601void RBDelete(rb_red_blk_tree* tree, rb_red_blk_node* z){
602 rb_red_blk_node* y;
603 rb_red_blk_node* x;
604 rb_red_blk_node* nil=tree->nil;
605 rb_red_blk_node* root=tree->root;
606
607 y= ((z->left == nil) || (z->right == nil)) ? z : TreeSuccessor(tree,z);
608 x= (y->left == nil) ? y->right : y->left;
609 if (root == (x->parent = y->parent)) { /* assignment of y->p to x->p is intentional */
610 root->left=x;
611 } else {
612 if (y == y->parent->left) {
613 y->parent->left=x;
614 } else {
615 y->parent->right=x;
616 }
617 }
618 if (y != z) { /* y should not be nil in this case */
619
620#ifdef DEBUG_ASSERT
621 Assert( (y!=tree->nil),"y is nil in RBDelete\n");
622#endif
623 /* y is the node to splice out and x is its child */
624
625 if (!(y->red)) RBDeleteFixUp(tree,x);
626
627 tree->DestroyKey(z->key);
628 tree->DestroyInfo(z->info);
629 y->left=z->left;
630 y->right=z->right;
631 y->parent=z->parent;
632 y->red=z->red;
633 z->left->parent=z->right->parent=y;
634 if (z == z->parent->left) {
635 z->parent->left=y;
636 } else {
637 z->parent->right=y;
638 }
639 free(z);
640 } else {
641 tree->DestroyKey(y->key);
642 tree->DestroyInfo(y->info);
643 if (!(y->red)) RBDeleteFixUp(tree,x);
644 free(y);
645 }
646
647#ifdef DEBUG_ASSERT
648 Assert(!tree->nil->red,"nil not black in RBDelete");
649#endif
650}
651
652
653/***********************************************************************/
654/* FUNCTION: RBEnumerate */
655/**/
656/* INPUTS: tree is the tree to look for keys >= low */
657/* and <= high with respect to the Compare function */
658/**/
659/* OUTPUT: stack containing pointers to the nodes between [low,high] */
660/**/
661/* Modifies Input: none */
662/***********************************************************************/
663
664stk_stack* RBEnumerate(rb_red_blk_tree* tree, void* low, void* high) {
665 stk_stack* enumResultStack;
666 rb_red_blk_node* nil=tree->nil;
667 rb_red_blk_node* x=tree->root->left;
668 rb_red_blk_node* lastBest=nil;
669
670 if (setjmp(rb_jbuf)) {
671 return NULL;
672 }
673 enumResultStack=StackCreate();
674 while(nil != x) {
675 if ( 1 == (tree->Compare(x->key,high)) ) { /* x->key > high */
676 x=x->left;
677 } else {
678 lastBest=x;
679 x=x->right;
680 }
681 }
682 while ( (lastBest != nil) && (1 != tree->Compare(low,lastBest->key))) {
683 StackPush(enumResultStack,lastBest);
684 lastBest=TreePredecessor(tree,lastBest);
685 }
686 return(enumResultStack);
687}
688
689
690
691
692
693
694
695