1 /***************************************************************************//**
2
3 Copyright (c) 2007, 2010, Oracle and/or its affiliates. All Rights Reserved.
4
5 This program is free software; you can redistribute it and/or modify
6 it under the terms of the GNU General Public License, version 2.0,
7 as published by the Free Software Foundation.
8
9 This program is also distributed with certain software (including
10 but not limited to OpenSSL) that is licensed under separate terms,
11 as designated in a particular file or component or in included license
12 documentation. The authors of MySQL hereby grant you an additional
13 permission to link the program and your derivative works with the
14 separately licensed software that they have included with MySQL.
15
16 This program is distributed in the hope that it will be useful,
17 but WITHOUT ANY WARRANTY; without even the implied warranty of
18 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
19 GNU General Public License, version 2.0, for more details.
20
21 You should have received a copy of the GNU General Public License along with
22 this program; if not, write to the Free Software Foundation, Inc.,
23 51 Franklin Street, Suite 500, Boston, MA 02110-1335 USA
24
25 *****************************************************************************/
26 /********************************************************************//**
27 Red-Black tree implementation
28
29 (c) 2007 Oracle/Innobase Oy
30
31 Created 2007-03-20 Sunny Bains
32 ***********************************************************************/
33
34 #include "ut0rbt.h"
35
36 /**********************************************************************//**
37 Definition of a red-black tree
38 ==============================
39
40 A red-black tree is a binary search tree which has the following
41 red-black properties:
42
43 1. Every node is either red or black.
44 2. Every leaf (NULL - in our case tree->nil) is black.
45 3. If a node is red, then both its children are black.
46 4. Every simple path from a node to a descendant leaf contains the
47 same number of black nodes.
48
49 from (3) above, the implication is that on any path from the root
50 to a leaf, red nodes must not be adjacent.
51
52 However, any number of black nodes may appear in a sequence.
53 */
54
55 #if defined(IB_RBT_TESTING)
56 #warning "Testing enabled!"
57 #endif
58
59 #define ROOT(t) (t->root->left)
60 #define SIZEOF_NODE(t) ((sizeof(ib_rbt_node_t) + t->sizeof_value) - 1)
61
62 /**********************************************************************//**
63 Print out the sub-tree recursively. */
64 static
65 void
rbt_print_subtree(const ib_rbt_t * tree,const ib_rbt_node_t * node,ib_rbt_print_node print)66 rbt_print_subtree(
67 /*==============*/
68 const ib_rbt_t* tree, /*!< in: tree to traverse */
69 const ib_rbt_node_t* node, /*!< in: node to print */
70 ib_rbt_print_node print) /*!< in: print key function */
71 {
72 /* FIXME: Doesn't do anything yet */
73 if (node != tree->nil) {
74 print(node);
75 rbt_print_subtree(tree, node->left, print);
76 rbt_print_subtree(tree, node->right, print);
77 }
78 }
79
80 /**********************************************************************//**
81 Verify that the keys are in order.
82 @return TRUE of OK. FALSE if not ordered */
83 static
84 ibool
rbt_check_ordering(const ib_rbt_t * tree)85 rbt_check_ordering(
86 /*===============*/
87 const ib_rbt_t* tree) /*!< in: tree to verfify */
88 {
89 const ib_rbt_node_t* node;
90 const ib_rbt_node_t* prev = NULL;
91
92 /* Iterate over all the nodes, comparing each node with the prev */
93 for (node = rbt_first(tree); node; node = rbt_next(tree, prev)) {
94
95 if (prev) {
96 int result;
97
98 if (tree->cmp_arg) {
99 result = tree->compare_with_arg(
100 tree->cmp_arg, prev->value,
101 node->value);
102 } else {
103 result = tree->compare(
104 prev->value, node->value);
105 }
106
107 if (result >= 0) {
108 return(FALSE);
109 }
110 }
111
112 prev = node;
113 }
114
115 return(TRUE);
116 }
117
118 /**********************************************************************//**
119 Check that every path from the root to the leaves has the same count.
120 Count is expressed in the number of black nodes.
121 @return 0 on failure else black height of the subtree */
122 static
123 ibool
rbt_count_black_nodes(const ib_rbt_t * tree,const ib_rbt_node_t * node)124 rbt_count_black_nodes(
125 /*==================*/
126 const ib_rbt_t* tree, /*!< in: tree to verify */
127 const ib_rbt_node_t* node) /*!< in: start of sub-tree */
128 {
129 ulint result;
130
131 if (node != tree->nil) {
132 ulint left_height = rbt_count_black_nodes(tree, node->left);
133
134 ulint right_height = rbt_count_black_nodes(tree, node->right);
135
136 if (left_height == 0
137 || right_height == 0
138 || left_height != right_height) {
139
140 result = 0;
141 } else if (node->color == IB_RBT_RED) {
142
143 /* Case 3 */
144 if (node->left->color != IB_RBT_BLACK
145 || node->right->color != IB_RBT_BLACK) {
146
147 result = 0;
148 } else {
149 result = left_height;
150 }
151 /* Check if it's anything other than RED or BLACK. */
152 } else if (node->color != IB_RBT_BLACK) {
153
154 result = 0;
155 } else {
156
157 result = right_height + 1;
158 }
159 } else {
160 result = 1;
161 }
162
163 return(result);
164 }
165
166 /**********************************************************************//**
167 Turn the node's right child's left sub-tree into node's right sub-tree.
168 This will also make node's right child it's parent. */
169 static
170 void
rbt_rotate_left(const ib_rbt_node_t * nil,ib_rbt_node_t * node)171 rbt_rotate_left(
172 /*============*/
173 const ib_rbt_node_t* nil, /*!< in: nil node of the tree */
174 ib_rbt_node_t* node) /*!< in: node to rotate */
175 {
176 ib_rbt_node_t* right = node->right;
177
178 node->right = right->left;
179
180 if (right->left != nil) {
181 right->left->parent = node;
182 }
183
184 /* Right's new parent was node's parent. */
185 right->parent = node->parent;
186
187 /* Since root's parent is tree->nil and root->parent->left points
188 back to root, we can avoid the check. */
189 if (node == node->parent->left) {
190 /* Node was on the left of its parent. */
191 node->parent->left = right;
192 } else {
193 /* Node must have been on the right. */
194 node->parent->right = right;
195 }
196
197 /* Finally, put node on right's left. */
198 right->left = node;
199 node->parent = right;
200 }
201
202 /**********************************************************************//**
203 Turn the node's left child's right sub-tree into node's left sub-tree.
204 This also make node's left child it's parent. */
205 static
206 void
rbt_rotate_right(const ib_rbt_node_t * nil,ib_rbt_node_t * node)207 rbt_rotate_right(
208 /*=============*/
209 const ib_rbt_node_t* nil, /*!< in: nil node of tree */
210 ib_rbt_node_t* node) /*!< in: node to rotate */
211 {
212 ib_rbt_node_t* left = node->left;
213
214 node->left = left->right;
215
216 if (left->right != nil) {
217 left->right->parent = node;
218 }
219
220 /* Left's new parent was node's parent. */
221 left->parent = node->parent;
222
223 /* Since root's parent is tree->nil and root->parent->left points
224 back to root, we can avoid the check. */
225 if (node == node->parent->right) {
226 /* Node was on the left of its parent. */
227 node->parent->right = left;
228 } else {
229 /* Node must have been on the left. */
230 node->parent->left = left;
231 }
232
233 /* Finally, put node on left's right. */
234 left->right = node;
235 node->parent = left;
236 }
237
238 /**********************************************************************//**
239 Append a node to the tree. */
240 static
241 ib_rbt_node_t*
rbt_tree_add_child(const ib_rbt_t * tree,ib_rbt_bound_t * parent,ib_rbt_node_t * node)242 rbt_tree_add_child(
243 /*===============*/
244 const ib_rbt_t* tree,
245 ib_rbt_bound_t* parent,
246 ib_rbt_node_t* node)
247 {
248 /* Cast away the const. */
249 ib_rbt_node_t* last = (ib_rbt_node_t*) parent->last;
250
251 if (last == tree->root || parent->result < 0) {
252 last->left = node;
253 } else {
254 /* FIXME: We don't handle duplicates (yet)! */
255 ut_a(parent->result != 0);
256
257 last->right = node;
258 }
259
260 node->parent = last;
261
262 return(node);
263 }
264
265 /**********************************************************************//**
266 Generic binary tree insert */
267 static
268 ib_rbt_node_t*
rbt_tree_insert(ib_rbt_t * tree,const void * key,ib_rbt_node_t * node)269 rbt_tree_insert(
270 /*============*/
271 ib_rbt_t* tree,
272 const void* key,
273 ib_rbt_node_t* node)
274 {
275 ib_rbt_bound_t parent;
276 ib_rbt_node_t* current = ROOT(tree);
277
278 parent.result = 0;
279 parent.last = tree->root;
280
281 /* Regular binary search. */
282 while (current != tree->nil) {
283
284 parent.last = current;
285
286 if (tree->cmp_arg) {
287 parent.result = tree->compare_with_arg(
288 tree->cmp_arg, key, current->value);
289 } else {
290 parent.result = tree->compare(key, current->value);
291 }
292
293 if (parent.result < 0) {
294 current = current->left;
295 } else {
296 current = current->right;
297 }
298 }
299
300 ut_a(current == tree->nil);
301
302 rbt_tree_add_child(tree, &parent, node);
303
304 return(node);
305 }
306
307 /**********************************************************************//**
308 Balance a tree after inserting a node. */
309 static
310 void
rbt_balance_tree(const ib_rbt_t * tree,ib_rbt_node_t * node)311 rbt_balance_tree(
312 /*=============*/
313 const ib_rbt_t* tree, /*!< in: tree to balance */
314 ib_rbt_node_t* node) /*!< in: node that was inserted */
315 {
316 const ib_rbt_node_t* nil = tree->nil;
317 ib_rbt_node_t* parent = node->parent;
318
319 /* Restore the red-black property. */
320 node->color = IB_RBT_RED;
321
322 while (node != ROOT(tree) && parent->color == IB_RBT_RED) {
323 ib_rbt_node_t* grand_parent = parent->parent;
324
325 if (parent == grand_parent->left) {
326 ib_rbt_node_t* uncle = grand_parent->right;
327
328 if (uncle->color == IB_RBT_RED) {
329
330 /* Case 1 - change the colors. */
331 uncle->color = IB_RBT_BLACK;
332 parent->color = IB_RBT_BLACK;
333 grand_parent->color = IB_RBT_RED;
334
335 /* Move node up the tree. */
336 node = grand_parent;
337
338 } else {
339
340 if (node == parent->right) {
341 /* Right is a black node and node is
342 to the right, case 2 - move node
343 up and rotate. */
344 node = parent;
345 rbt_rotate_left(nil, node);
346 }
347
348 grand_parent = node->parent->parent;
349
350 /* Case 3. */
351 node->parent->color = IB_RBT_BLACK;
352 grand_parent->color = IB_RBT_RED;
353
354 rbt_rotate_right(nil, grand_parent);
355 }
356
357 } else {
358 ib_rbt_node_t* uncle = grand_parent->left;
359
360 if (uncle->color == IB_RBT_RED) {
361
362 /* Case 1 - change the colors. */
363 uncle->color = IB_RBT_BLACK;
364 parent->color = IB_RBT_BLACK;
365 grand_parent->color = IB_RBT_RED;
366
367 /* Move node up the tree. */
368 node = grand_parent;
369
370 } else {
371
372 if (node == parent->left) {
373 /* Left is a black node and node is to
374 the right, case 2 - move node up and
375 rotate. */
376 node = parent;
377 rbt_rotate_right(nil, node);
378 }
379
380 grand_parent = node->parent->parent;
381
382 /* Case 3. */
383 node->parent->color = IB_RBT_BLACK;
384 grand_parent->color = IB_RBT_RED;
385
386 rbt_rotate_left(nil, grand_parent);
387 }
388 }
389
390 parent = node->parent;
391 }
392
393 /* Color the root black. */
394 ROOT(tree)->color = IB_RBT_BLACK;
395 }
396
397 /**********************************************************************//**
398 Find the given node's successor.
399 @return successor node or NULL if no successor */
400 static
401 ib_rbt_node_t*
rbt_find_successor(const ib_rbt_t * tree,const ib_rbt_node_t * current)402 rbt_find_successor(
403 /*===============*/
404 const ib_rbt_t* tree, /*!< in: rb tree */
405 const ib_rbt_node_t* current) /*!< in: this is declared const
406 because it can be called via
407 rbt_next() */
408 {
409 const ib_rbt_node_t* nil = tree->nil;
410 ib_rbt_node_t* next = current->right;
411
412 /* Is there a sub-tree to the right that we can follow. */
413 if (next != nil) {
414
415 /* Follow the left most links of the current right child. */
416 while (next->left != nil) {
417 next = next->left;
418 }
419
420 } else { /* We will have to go up the tree to find the successor. */
421 ib_rbt_node_t* parent = current->parent;
422
423 /* Cast away the const. */
424 next = (ib_rbt_node_t*) current;
425
426 while (parent != tree->root && next == parent->right) {
427 next = parent;
428 parent = next->parent;
429 }
430
431 next = (parent == tree->root) ? NULL : parent;
432 }
433
434 return(next);
435 }
436
437 /**********************************************************************//**
438 Find the given node's precedecessor.
439 @return predecessor node or NULL if no predecesor */
440 static
441 ib_rbt_node_t*
rbt_find_predecessor(const ib_rbt_t * tree,const ib_rbt_node_t * current)442 rbt_find_predecessor(
443 /*=================*/
444 const ib_rbt_t* tree, /*!< in: rb tree */
445 const ib_rbt_node_t* current) /*!< in: this is declared const
446 because it can be called via
447 rbt_prev() */
448 {
449 const ib_rbt_node_t* nil = tree->nil;
450 ib_rbt_node_t* prev = current->left;
451
452 /* Is there a sub-tree to the left that we can follow. */
453 if (prev != nil) {
454
455 /* Follow the right most links of the current left child. */
456 while (prev->right != nil) {
457 prev = prev->right;
458 }
459
460 } else { /* We will have to go up the tree to find the precedecessor. */
461 ib_rbt_node_t* parent = current->parent;
462
463 /* Cast away the const. */
464 prev = (ib_rbt_node_t*) current;
465
466 while (parent != tree->root && prev == parent->left) {
467 prev = parent;
468 parent = prev->parent;
469 }
470
471 prev = (parent == tree->root) ? NULL : parent;
472 }
473
474 return(prev);
475 }
476
477 /**********************************************************************//**
478 Replace node with child. After applying transformations eject becomes
479 an orphan. */
480 static
481 void
rbt_eject_node(ib_rbt_node_t * eject,ib_rbt_node_t * node)482 rbt_eject_node(
483 /*===========*/
484 ib_rbt_node_t* eject, /*!< in: node to eject */
485 ib_rbt_node_t* node) /*!< in: node to replace with */
486 {
487 /* Update the to be ejected node's parent's child pointers. */
488 if (eject->parent->left == eject) {
489 eject->parent->left = node;
490 } else if (eject->parent->right == eject) {
491 eject->parent->right = node;
492 } else {
493 ut_a(0);
494 }
495 /* eject is now an orphan but otherwise its pointers
496 and color are left intact. */
497
498 node->parent = eject->parent;
499 }
500
501 /**********************************************************************//**
502 Replace a node with another node. */
503 static
504 void
rbt_replace_node(ib_rbt_node_t * replace,ib_rbt_node_t * node)505 rbt_replace_node(
506 /*=============*/
507 ib_rbt_node_t* replace, /*!< in: node to replace */
508 ib_rbt_node_t* node) /*!< in: node to replace with */
509 {
510 ib_rbt_color_t color = node->color;
511
512 /* Update the node pointers. */
513 node->left = replace->left;
514 node->right = replace->right;
515
516 /* Update the child node pointers. */
517 node->left->parent = node;
518 node->right->parent = node;
519
520 /* Make the parent of replace point to node. */
521 rbt_eject_node(replace, node);
522
523 /* Swap the colors. */
524 node->color = replace->color;
525 replace->color = color;
526 }
527
528 /**********************************************************************//**
529 Detach node from the tree replacing it with one of it's children.
530 @return the child node that now occupies the position of the detached node */
531 static
532 ib_rbt_node_t*
rbt_detach_node(const ib_rbt_t * tree,ib_rbt_node_t * node)533 rbt_detach_node(
534 /*============*/
535 const ib_rbt_t* tree, /*!< in: rb tree */
536 ib_rbt_node_t* node) /*!< in: node to detach */
537 {
538 ib_rbt_node_t* child;
539 const ib_rbt_node_t* nil = tree->nil;
540
541 if (node->left != nil && node->right != nil) {
542 /* Case where the node to be deleted has two children. */
543 ib_rbt_node_t* successor = rbt_find_successor(tree, node);
544
545 ut_a(successor != nil);
546 ut_a(successor->parent != nil);
547 ut_a(successor->left == nil);
548
549 child = successor->right;
550
551 /* Remove the successor node and replace with its child. */
552 rbt_eject_node(successor, child);
553
554 /* Replace the node to delete with its successor node. */
555 rbt_replace_node(node, successor);
556 } else {
557 ut_a(node->left == nil || node->right == nil);
558
559 child = (node->left != nil) ? node->left : node->right;
560
561 /* Replace the node to delete with one of it's children. */
562 rbt_eject_node(node, child);
563 }
564
565 /* Reset the node links. */
566 node->parent = node->right = node->left = tree->nil;
567
568 return(child);
569 }
570
571 /**********************************************************************//**
572 Rebalance the right sub-tree after deletion.
573 @return node to rebalance if more rebalancing required else NULL */
574 static
575 ib_rbt_node_t*
rbt_balance_right(const ib_rbt_node_t * nil,ib_rbt_node_t * parent,ib_rbt_node_t * sibling)576 rbt_balance_right(
577 /*==============*/
578 const ib_rbt_node_t* nil, /*!< in: rb tree nil node */
579 ib_rbt_node_t* parent, /*!< in: parent node */
580 ib_rbt_node_t* sibling) /*!< in: sibling node */
581 {
582 ib_rbt_node_t* node = NULL;
583
584 ut_a(sibling != nil);
585
586 /* Case 3. */
587 if (sibling->color == IB_RBT_RED) {
588
589 parent->color = IB_RBT_RED;
590 sibling->color = IB_RBT_BLACK;
591
592 rbt_rotate_left(nil, parent);
593
594 sibling = parent->right;
595
596 ut_a(sibling != nil);
597 }
598
599 /* Since this will violate case 3 because of the change above. */
600 if (sibling->left->color == IB_RBT_BLACK
601 && sibling->right->color == IB_RBT_BLACK) {
602
603 node = parent; /* Parent needs to be rebalanced too. */
604 sibling->color = IB_RBT_RED;
605
606 } else {
607 if (sibling->right->color == IB_RBT_BLACK) {
608
609 ut_a(sibling->left->color == IB_RBT_RED);
610
611 sibling->color = IB_RBT_RED;
612 sibling->left->color = IB_RBT_BLACK;
613
614 rbt_rotate_right(nil, sibling);
615
616 sibling = parent->right;
617 ut_a(sibling != nil);
618 }
619
620 sibling->color = parent->color;
621 sibling->right->color = IB_RBT_BLACK;
622
623 parent->color = IB_RBT_BLACK;
624
625 rbt_rotate_left(nil, parent);
626 }
627
628 return(node);
629 }
630
631 /**********************************************************************//**
632 Rebalance the left sub-tree after deletion.
633 @return node to rebalance if more rebalancing required else NULL */
634 static
635 ib_rbt_node_t*
rbt_balance_left(const ib_rbt_node_t * nil,ib_rbt_node_t * parent,ib_rbt_node_t * sibling)636 rbt_balance_left(
637 /*=============*/
638 const ib_rbt_node_t* nil, /*!< in: rb tree nil node */
639 ib_rbt_node_t* parent, /*!< in: parent node */
640 ib_rbt_node_t* sibling) /*!< in: sibling node */
641 {
642 ib_rbt_node_t* node = NULL;
643
644 ut_a(sibling != nil);
645
646 /* Case 3. */
647 if (sibling->color == IB_RBT_RED) {
648
649 parent->color = IB_RBT_RED;
650 sibling->color = IB_RBT_BLACK;
651
652 rbt_rotate_right(nil, parent);
653 sibling = parent->left;
654
655 ut_a(sibling != nil);
656 }
657
658 /* Since this will violate case 3 because of the change above. */
659 if (sibling->right->color == IB_RBT_BLACK
660 && sibling->left->color == IB_RBT_BLACK) {
661
662 node = parent; /* Parent needs to be rebalanced too. */
663 sibling->color = IB_RBT_RED;
664
665 } else {
666 if (sibling->left->color == IB_RBT_BLACK) {
667
668 ut_a(sibling->right->color == IB_RBT_RED);
669
670 sibling->color = IB_RBT_RED;
671 sibling->right->color = IB_RBT_BLACK;
672
673 rbt_rotate_left(nil, sibling);
674
675 sibling = parent->left;
676
677 ut_a(sibling != nil);
678 }
679
680 sibling->color = parent->color;
681 sibling->left->color = IB_RBT_BLACK;
682
683 parent->color = IB_RBT_BLACK;
684
685 rbt_rotate_right(nil, parent);
686 }
687
688 return(node);
689 }
690
691 /**********************************************************************//**
692 Delete the node and rebalance the tree if necessary */
693 static
694 void
rbt_remove_node_and_rebalance(ib_rbt_t * tree,ib_rbt_node_t * node)695 rbt_remove_node_and_rebalance(
696 /*==========================*/
697 ib_rbt_t* tree, /*!< in: rb tree */
698 ib_rbt_node_t* node) /*!< in: node to remove */
699 {
700 /* Detach node and get the node that will be used
701 as rebalance start. */
702 ib_rbt_node_t* child = rbt_detach_node(tree, node);
703
704 if (node->color == IB_RBT_BLACK) {
705 ib_rbt_node_t* last = child;
706
707 ROOT(tree)->color = IB_RBT_RED;
708
709 while (child && child->color == IB_RBT_BLACK) {
710 ib_rbt_node_t* parent = child->parent;
711
712 /* Did the deletion cause an imbalance in the
713 parents left sub-tree. */
714 if (parent->left == child) {
715
716 child = rbt_balance_right(
717 tree->nil, parent, parent->right);
718
719 } else if (parent->right == child) {
720
721 child = rbt_balance_left(
722 tree->nil, parent, parent->left);
723
724 } else {
725 ut_error;
726 }
727
728 if (child) {
729 last = child;
730 }
731 }
732
733 ut_a(last);
734
735 last->color = IB_RBT_BLACK;
736 ROOT(tree)->color = IB_RBT_BLACK;
737 }
738
739 /* Note that we have removed a node from the tree. */
740 --tree->n_nodes;
741 }
742
743 /**********************************************************************//**
744 Recursively free the nodes. */
745 static
746 void
rbt_free_node(ib_rbt_node_t * node,ib_rbt_node_t * nil)747 rbt_free_node(
748 /*==========*/
749 ib_rbt_node_t* node, /*!< in: node to free */
750 ib_rbt_node_t* nil) /*!< in: rb tree nil node */
751 {
752 if (node != nil) {
753 rbt_free_node(node->left, nil);
754 rbt_free_node(node->right, nil);
755
756 ut_free(node);
757 }
758 }
759
760 /**********************************************************************//**
761 Free all the nodes and free the tree. */
762 UNIV_INTERN
763 void
rbt_free(ib_rbt_t * tree)764 rbt_free(
765 /*=====*/
766 ib_rbt_t* tree) /*!< in: rb tree to free */
767 {
768 rbt_free_node(tree->root, tree->nil);
769 ut_free(tree->nil);
770 ut_free(tree);
771 }
772
773 /**********************************************************************//**
774 Create an instance of a red black tree, whose comparison function takes
775 an argument
776 @return an empty rb tree */
777 UNIV_INTERN
778 ib_rbt_t*
rbt_create_arg_cmp(size_t sizeof_value,ib_rbt_arg_compare compare,void * cmp_arg)779 rbt_create_arg_cmp(
780 /*===============*/
781 size_t sizeof_value, /*!< in: sizeof data item */
782 ib_rbt_arg_compare
783 compare, /*!< in: fn to compare items */
784 void* cmp_arg) /*!< in: compare fn arg */
785 {
786 ib_rbt_t* tree;
787
788 ut_a(cmp_arg);
789
790 tree = rbt_create(sizeof_value, NULL);
791 tree->cmp_arg = cmp_arg;
792 tree->compare_with_arg = compare;
793
794 return(tree);
795 }
796
797 /**********************************************************************//**
798 Create an instance of a red black tree.
799 @return an empty rb tree */
800 UNIV_INTERN
801 ib_rbt_t*
rbt_create(size_t sizeof_value,ib_rbt_compare compare)802 rbt_create(
803 /*=======*/
804 size_t sizeof_value, /*!< in: sizeof data item */
805 ib_rbt_compare compare) /*!< in: fn to compare items */
806 {
807 ib_rbt_t* tree;
808 ib_rbt_node_t* node;
809
810 tree = (ib_rbt_t*) ut_malloc(sizeof(*tree));
811 memset(tree, 0, sizeof(*tree));
812
813 tree->sizeof_value = sizeof_value;
814
815 /* Create the sentinel (NIL) node. */
816 node = tree->nil = (ib_rbt_node_t*) ut_malloc(sizeof(*node));
817 memset(node, 0, sizeof(*node));
818
819 node->color = IB_RBT_BLACK;
820 node->parent = node->left = node->right = node;
821
822 /* Create the "fake" root, the real root node will be the
823 left child of this node. */
824 node = tree->root = (ib_rbt_node_t*) ut_malloc(sizeof(*node));
825 memset(node, 0, sizeof(*node));
826
827 node->color = IB_RBT_BLACK;
828 node->parent = node->left = node->right = tree->nil;
829
830 tree->compare = compare;
831
832 return(tree);
833 }
834
835 /**********************************************************************//**
836 Generic insert of a value in the rb tree.
837 @return inserted node */
838 UNIV_INTERN
839 const ib_rbt_node_t*
rbt_insert(ib_rbt_t * tree,const void * key,const void * value)840 rbt_insert(
841 /*=======*/
842 ib_rbt_t* tree, /*!< in: rb tree */
843 const void* key, /*!< in: key for ordering */
844 const void* value) /*!< in: value of key, this value
845 is copied to the node */
846 {
847 ib_rbt_node_t* node;
848
849 /* Create the node that will hold the value data. */
850 node = (ib_rbt_node_t*) ut_malloc(SIZEOF_NODE(tree));
851
852 memcpy(node->value, value, tree->sizeof_value);
853 node->parent = node->left = node->right = tree->nil;
854
855 /* Insert in the tree in the usual way. */
856 rbt_tree_insert(tree, key, node);
857 rbt_balance_tree(tree, node);
858
859 ++tree->n_nodes;
860
861 return(node);
862 }
863
864 /**********************************************************************//**
865 Add a new node to the tree, useful for data that is pre-sorted.
866 @return appended node */
867 UNIV_INTERN
868 const ib_rbt_node_t*
rbt_add_node(ib_rbt_t * tree,ib_rbt_bound_t * parent,const void * value)869 rbt_add_node(
870 /*=========*/
871 ib_rbt_t* tree, /*!< in: rb tree */
872 ib_rbt_bound_t* parent, /*!< in: bounds */
873 const void* value) /*!< in: this value is copied
874 to the node */
875 {
876 ib_rbt_node_t* node;
877
878 /* Create the node that will hold the value data */
879 node = (ib_rbt_node_t*) ut_malloc(SIZEOF_NODE(tree));
880
881 memcpy(node->value, value, tree->sizeof_value);
882 node->parent = node->left = node->right = tree->nil;
883
884 /* If tree is empty */
885 if (parent->last == NULL) {
886 parent->last = tree->root;
887 }
888
889 /* Append the node, the hope here is that the caller knows
890 what s/he is doing. */
891 rbt_tree_add_child(tree, parent, node);
892 rbt_balance_tree(tree, node);
893
894 ++tree->n_nodes;
895
896 #if defined(IB_RBT_TESTING)
897 ut_a(rbt_validate(tree));
898 #endif
899 return(node);
900 }
901
902 /**********************************************************************//**
903 Find a matching node in the rb tree.
904 @return NULL if not found else the node where key was found */
905 UNIV_INTERN
906 const ib_rbt_node_t*
rbt_lookup(const ib_rbt_t * tree,const void * key)907 rbt_lookup(
908 /*=======*/
909 const ib_rbt_t* tree, /*!< in: rb tree */
910 const void* key) /*!< in: key to use for search */
911 {
912 const ib_rbt_node_t* current = ROOT(tree);
913
914 /* Regular binary search. */
915 while (current != tree->nil) {
916 int result;
917
918 if (tree->cmp_arg) {
919 result = tree->compare_with_arg(
920 tree->cmp_arg, key, current->value);
921 } else {
922 result = tree->compare(key, current->value);
923 }
924
925 if (result < 0) {
926 current = current->left;
927 } else if (result > 0) {
928 current = current->right;
929 } else {
930 break;
931 }
932 }
933
934 return(current != tree->nil ? current : NULL);
935 }
936
937 /**********************************************************************//**
938 Delete a node indentified by key.
939 @return TRUE if success FALSE if not found */
940 UNIV_INTERN
941 ibool
rbt_delete(ib_rbt_t * tree,const void * key)942 rbt_delete(
943 /*=======*/
944 ib_rbt_t* tree, /*!< in: rb tree */
945 const void* key) /*!< in: key to delete */
946 {
947 ibool deleted = FALSE;
948 ib_rbt_node_t* node = (ib_rbt_node_t*) rbt_lookup(tree, key);
949
950 if (node) {
951 rbt_remove_node_and_rebalance(tree, node);
952
953 ut_free(node);
954 deleted = TRUE;
955 }
956
957 return(deleted);
958 }
959
960 /**********************************************************************//**
961 Remove a node from the rb tree, the node is not free'd, that is the
962 callers responsibility.
963 @return deleted node but without the const */
964 UNIV_INTERN
965 ib_rbt_node_t*
rbt_remove_node(ib_rbt_t * tree,const ib_rbt_node_t * const_node)966 rbt_remove_node(
967 /*============*/
968 ib_rbt_t* tree, /*!< in: rb tree */
969 const ib_rbt_node_t* const_node) /*!< in: node to delete, this
970 is a fudge and declared const
971 because the caller can access
972 only const nodes */
973 {
974 /* Cast away the const. */
975 rbt_remove_node_and_rebalance(tree, (ib_rbt_node_t*) const_node);
976
977 /* This is to make it easier to do something like this:
978 ut_free(rbt_remove_node(node));
979 */
980
981 return((ib_rbt_node_t*) const_node);
982 }
983
984 /**********************************************************************//**
985 Find the node that has the lowest key that is >= key.
986 @return node satisfying the lower bound constraint or NULL */
987 UNIV_INTERN
988 const ib_rbt_node_t*
rbt_lower_bound(const ib_rbt_t * tree,const void * key)989 rbt_lower_bound(
990 /*============*/
991 const ib_rbt_t* tree, /*!< in: rb tree */
992 const void* key) /*!< in: key to search */
993 {
994 ib_rbt_node_t* lb_node = NULL;
995 ib_rbt_node_t* current = ROOT(tree);
996
997 while (current != tree->nil) {
998 int result;
999
1000 if (tree->cmp_arg) {
1001 result = tree->compare_with_arg(
1002 tree->cmp_arg, key, current->value);
1003 } else {
1004 result = tree->compare(key, current->value);
1005 }
1006
1007 if (result > 0) {
1008
1009 current = current->right;
1010
1011 } else if (result < 0) {
1012
1013 lb_node = current;
1014 current = current->left;
1015
1016 } else {
1017 lb_node = current;
1018 break;
1019 }
1020 }
1021
1022 return(lb_node);
1023 }
1024
1025 /**********************************************************************//**
1026 Find the node that has the greatest key that is <= key.
1027 @return node satisfying the upper bound constraint or NULL */
1028 UNIV_INTERN
1029 const ib_rbt_node_t*
rbt_upper_bound(const ib_rbt_t * tree,const void * key)1030 rbt_upper_bound(
1031 /*============*/
1032 const ib_rbt_t* tree, /*!< in: rb tree */
1033 const void* key) /*!< in: key to search */
1034 {
1035 ib_rbt_node_t* ub_node = NULL;
1036 ib_rbt_node_t* current = ROOT(tree);
1037
1038 while (current != tree->nil) {
1039 int result;
1040
1041 if (tree->cmp_arg) {
1042 result = tree->compare_with_arg(
1043 tree->cmp_arg, key, current->value);
1044 } else {
1045 result = tree->compare(key, current->value);
1046 }
1047
1048 if (result > 0) {
1049
1050 ub_node = current;
1051 current = current->right;
1052
1053 } else if (result < 0) {
1054
1055 current = current->left;
1056
1057 } else {
1058 ub_node = current;
1059 break;
1060 }
1061 }
1062
1063 return(ub_node);
1064 }
1065
1066 /**********************************************************************//**
1067 Find the node that has the greatest key that is <= key.
1068 @return value of result */
1069 UNIV_INTERN
1070 int
rbt_search(const ib_rbt_t * tree,ib_rbt_bound_t * parent,const void * key)1071 rbt_search(
1072 /*=======*/
1073 const ib_rbt_t* tree, /*!< in: rb tree */
1074 ib_rbt_bound_t* parent, /*!< in: search bounds */
1075 const void* key) /*!< in: key to search */
1076 {
1077 ib_rbt_node_t* current = ROOT(tree);
1078
1079 /* Every thing is greater than the NULL root. */
1080 parent->result = 1;
1081 parent->last = NULL;
1082
1083 while (current != tree->nil) {
1084
1085 parent->last = current;
1086
1087 if (tree->cmp_arg) {
1088 parent->result = tree->compare_with_arg(
1089 tree->cmp_arg, key, current->value);
1090 } else {
1091 parent->result = tree->compare(key, current->value);
1092 }
1093
1094 if (parent->result > 0) {
1095 current = current->right;
1096 } else if (parent->result < 0) {
1097 current = current->left;
1098 } else {
1099 break;
1100 }
1101 }
1102
1103 return(parent->result);
1104 }
1105
1106 /**********************************************************************//**
1107 Find the node that has the greatest key that is <= key. But use the
1108 supplied comparison function.
1109 @return value of result */
1110 UNIV_INTERN
1111 int
rbt_search_cmp(const ib_rbt_t * tree,ib_rbt_bound_t * parent,const void * key,ib_rbt_compare compare,ib_rbt_arg_compare arg_compare)1112 rbt_search_cmp(
1113 /*===========*/
1114 const ib_rbt_t* tree, /*!< in: rb tree */
1115 ib_rbt_bound_t* parent, /*!< in: search bounds */
1116 const void* key, /*!< in: key to search */
1117 ib_rbt_compare compare, /*!< in: fn to compare items */
1118 ib_rbt_arg_compare
1119 arg_compare) /*!< in: fn to compare items
1120 with argument */
1121 {
1122 ib_rbt_node_t* current = ROOT(tree);
1123
1124 /* Every thing is greater than the NULL root. */
1125 parent->result = 1;
1126 parent->last = NULL;
1127
1128 while (current != tree->nil) {
1129
1130 parent->last = current;
1131
1132 if (arg_compare) {
1133 ut_ad(tree->cmp_arg);
1134 parent->result = arg_compare(
1135 tree->cmp_arg, key, current->value);
1136 } else {
1137 parent->result = compare(key, current->value);
1138 }
1139
1140 if (parent->result > 0) {
1141 current = current->right;
1142 } else if (parent->result < 0) {
1143 current = current->left;
1144 } else {
1145 break;
1146 }
1147 }
1148
1149 return(parent->result);
1150 }
1151
1152 /**********************************************************************//**
1153 Return the left most node in the tree. */
1154 UNIV_INTERN
1155 const ib_rbt_node_t*
rbt_first(const ib_rbt_t * tree)1156 rbt_first(
1157 /*======*/
1158 /* out leftmost node or NULL */
1159 const ib_rbt_t* tree) /* in: rb tree */
1160 {
1161 ib_rbt_node_t* first = NULL;
1162 ib_rbt_node_t* current = ROOT(tree);
1163
1164 while (current != tree->nil) {
1165 first = current;
1166 current = current->left;
1167 }
1168
1169 return(first);
1170 }
1171
1172 /**********************************************************************//**
1173 Return the right most node in the tree.
1174 @return the rightmost node or NULL */
1175 UNIV_INTERN
1176 const ib_rbt_node_t*
rbt_last(const ib_rbt_t * tree)1177 rbt_last(
1178 /*=====*/
1179 const ib_rbt_t* tree) /*!< in: rb tree */
1180 {
1181 ib_rbt_node_t* last = NULL;
1182 ib_rbt_node_t* current = ROOT(tree);
1183
1184 while (current != tree->nil) {
1185 last = current;
1186 current = current->right;
1187 }
1188
1189 return(last);
1190 }
1191
1192 /**********************************************************************//**
1193 Return the next node.
1194 @return node next from current */
1195 UNIV_INTERN
1196 const ib_rbt_node_t*
rbt_next(const ib_rbt_t * tree,const ib_rbt_node_t * current)1197 rbt_next(
1198 /*=====*/
1199 const ib_rbt_t* tree, /*!< in: rb tree */
1200 const ib_rbt_node_t* current) /*!< in: current node */
1201 {
1202 return(current ? rbt_find_successor(tree, current) : NULL);
1203 }
1204
1205 /**********************************************************************//**
1206 Return the previous node.
1207 @return node prev from current */
1208 UNIV_INTERN
1209 const ib_rbt_node_t*
rbt_prev(const ib_rbt_t * tree,const ib_rbt_node_t * current)1210 rbt_prev(
1211 /*=====*/
1212 const ib_rbt_t* tree, /*!< in: rb tree */
1213 const ib_rbt_node_t* current) /*!< in: current node */
1214 {
1215 return(current ? rbt_find_predecessor(tree, current) : NULL);
1216 }
1217
1218 /**********************************************************************//**
1219 Reset the tree. Delete all the nodes. */
1220 UNIV_INTERN
1221 void
rbt_clear(ib_rbt_t * tree)1222 rbt_clear(
1223 /*======*/
1224 ib_rbt_t* tree) /*!< in: rb tree */
1225 {
1226 rbt_free_node(ROOT(tree), tree->nil);
1227
1228 tree->n_nodes = 0;
1229 tree->root->left = tree->root->right = tree->nil;
1230 }
1231
1232 /**********************************************************************//**
1233 Merge the node from dst into src. Return the number of nodes merged.
1234 @return no. of recs merged */
1235 UNIV_INTERN
1236 ulint
rbt_merge_uniq(ib_rbt_t * dst,const ib_rbt_t * src)1237 rbt_merge_uniq(
1238 /*===========*/
1239 ib_rbt_t* dst, /*!< in: dst rb tree */
1240 const ib_rbt_t* src) /*!< in: src rb tree */
1241 {
1242 ib_rbt_bound_t parent;
1243 ulint n_merged = 0;
1244 const ib_rbt_node_t* src_node = rbt_first(src);
1245
1246 if (rbt_empty(src) || dst == src) {
1247 return(0);
1248 }
1249
1250 for (/* No op */; src_node; src_node = rbt_next(src, src_node)) {
1251
1252 if (rbt_search(dst, &parent, src_node->value) != 0) {
1253 rbt_add_node(dst, &parent, src_node->value);
1254 ++n_merged;
1255 }
1256 }
1257
1258 return(n_merged);
1259 }
1260
1261 /**********************************************************************//**
1262 Merge the node from dst into src. Return the number of nodes merged.
1263 Delete the nodes from src after copying node to dst. As a side effect
1264 the duplicates will be left untouched in the src.
1265 @return no. of recs merged */
1266 UNIV_INTERN
1267 ulint
rbt_merge_uniq_destructive(ib_rbt_t * dst,ib_rbt_t * src)1268 rbt_merge_uniq_destructive(
1269 /*=======================*/
1270 ib_rbt_t* dst, /*!< in: dst rb tree */
1271 ib_rbt_t* src) /*!< in: src rb tree */
1272 {
1273 ib_rbt_bound_t parent;
1274 ib_rbt_node_t* src_node;
1275 ulint old_size = rbt_size(dst);
1276
1277 if (rbt_empty(src) || dst == src) {
1278 return(0);
1279 }
1280
1281 for (src_node = (ib_rbt_node_t*) rbt_first(src); src_node; /* */) {
1282 ib_rbt_node_t* prev = src_node;
1283
1284 src_node = (ib_rbt_node_t*) rbt_next(src, prev);
1285
1286 /* Skip duplicates. */
1287 if (rbt_search(dst, &parent, prev->value) != 0) {
1288
1289 /* Remove and reset the node but preserve
1290 the node (data) value. */
1291 rbt_remove_node_and_rebalance(src, prev);
1292
1293 /* The nil should be taken from the dst tree. */
1294 prev->parent = prev->left = prev->right = dst->nil;
1295 rbt_tree_add_child(dst, &parent, prev);
1296 rbt_balance_tree(dst, prev);
1297
1298 ++dst->n_nodes;
1299 }
1300 }
1301
1302 #if defined(IB_RBT_TESTING)
1303 ut_a(rbt_validate(dst));
1304 ut_a(rbt_validate(src));
1305 #endif
1306 return(rbt_size(dst) - old_size);
1307 }
1308
1309 /**********************************************************************//**
1310 Check that every path from the root to the leaves has the same count and
1311 the tree nodes are in order.
1312 @return TRUE if OK FALSE otherwise */
1313 UNIV_INTERN
1314 ibool
rbt_validate(const ib_rbt_t * tree)1315 rbt_validate(
1316 /*=========*/
1317 const ib_rbt_t* tree) /*!< in: RB tree to validate */
1318 {
1319 if (rbt_count_black_nodes(tree, ROOT(tree)) > 0) {
1320 return(rbt_check_ordering(tree));
1321 }
1322
1323 return(FALSE);
1324 }
1325
1326 /**********************************************************************//**
1327 Iterate over the tree in depth first order. */
1328 UNIV_INTERN
1329 void
rbt_print(const ib_rbt_t * tree,ib_rbt_print_node print)1330 rbt_print(
1331 /*======*/
1332 const ib_rbt_t* tree, /*!< in: tree to traverse */
1333 ib_rbt_print_node print) /*!< in: print function */
1334 {
1335 rbt_print_subtree(tree, ROOT(tree), print);
1336 }
1337