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