drizzle
C++ MySQL-protocol-compatible database server
Loading...
Searching...
No Matches
ut0rbt.cc
1/***************************************************************************/
24/********************************************************************/
31
32#include "ut0rbt.h"
33
34/**********************************************************************/
52
53#if defined(IB_RBT_TESTING)
54#warning "Testing enabled!"
55#endif
56
57#define ROOT(t) (t->root->left)
58#define SIZEOF_NODE(t) ((sizeof(ib_rbt_node_t) + t->sizeof_value) - 1)
59
60/**********************************************************************/
62static
63void
64rbt_print_subtree(
65/*==============*/
66 const ib_rbt_t* tree,
67 const ib_rbt_node_t* node,
68 ib_rbt_print_node print)
69{
70 /* FIXME: Doesn't do anything yet */
71 if (node != tree->nil) {
72 print(node);
73 rbt_print_subtree(tree, node->left, print);
74 rbt_print_subtree(tree, node->right, print);
75 }
76}
77
78/**********************************************************************/
81static
82ibool
83rbt_check_ordering(
84/*===============*/
85 const ib_rbt_t* tree)
86{
87 const ib_rbt_node_t* node;
88 const ib_rbt_node_t* prev = NULL;
89
90 /* Iterate over all the nodes, comparing each node with the prev */
91 for (node = rbt_first(tree); node; node = rbt_next(tree, prev)) {
92
93 if (prev && tree->compare(prev->value, node->value) >= 0) {
94 return(FALSE);
95 }
96
97 prev = node;
98 }
99
100 return(TRUE);
101}
102
103/**********************************************************************/
107static
108ibool
109rbt_count_black_nodes(
110/*==================*/
111 const ib_rbt_t* tree,
112 const ib_rbt_node_t* node)
113{
114 ulint result;
115
116 if (node != tree->nil) {
117 ulint left_height = rbt_count_black_nodes(tree, node->left);
118
119 ulint right_height = rbt_count_black_nodes(tree, node->right);
120
121 if (left_height == 0
122 || right_height == 0
123 || left_height != right_height) {
124
125 result = 0;
126 } else if (node->color == IB_RBT_RED) {
127
128 /* Case 3 */
129 if (node->left->color != IB_RBT_BLACK
130 || node->right->color != IB_RBT_BLACK) {
131
132 result = 0;
133 } else {
134 result = left_height;
135 }
136 /* Check if it's anything other than RED or BLACK. */
137 } else if (node->color != IB_RBT_BLACK) {
138
139 result = 0;
140 } else {
141
142 result = right_height + 1;
143 }
144 } else {
145 result = 1;
146 }
147
148 return(result);
149}
150
151/**********************************************************************/
154static
155void
156rbt_rotate_left(
157/*============*/
158 const ib_rbt_node_t* nil,
159 ib_rbt_node_t* node)
160{
161 ib_rbt_node_t* right = node->right;
162
163 node->right = right->left;
164
165 if (right->left != nil) {
166 right->left->parent = node;
167 }
168
169 /* Right's new parent was node's parent. */
170 right->parent = node->parent;
171
172 /* Since root's parent is tree->nil and root->parent->left points
173 back to root, we can avoid the check. */
174 if (node == node->parent->left) {
175 /* Node was on the left of its parent. */
176 node->parent->left = right;
177 } else {
178 /* Node must have been on the right. */
179 node->parent->right = right;
180 }
181
182 /* Finally, put node on right's left. */
183 right->left = node;
184 node->parent = right;
185}
186
187/**********************************************************************/
190static
191void
192rbt_rotate_right(
193/*=============*/
194 const ib_rbt_node_t* nil,
195 ib_rbt_node_t* node)
196{
197 ib_rbt_node_t* left = node->left;
198
199 node->left = left->right;
200
201 if (left->right != nil) {
202 left->right->parent = node;
203 }
204
205 /* Left's new parent was node's parent. */
206 left->parent = node->parent;
207
208 /* Since root's parent is tree->nil and root->parent->left points
209 back to root, we can avoid the check. */
210 if (node == node->parent->right) {
211 /* Node was on the left of its parent. */
212 node->parent->right = left;
213 } else {
214 /* Node must have been on the left. */
215 node->parent->left = left;
216 }
217
218 /* Finally, put node on left's right. */
219 left->right = node;
220 node->parent = left;
221}
222
223/**********************************************************************/
225static
226ib_rbt_node_t*
227rbt_tree_add_child(
228/*===============*/
229 const ib_rbt_t* tree,
230 ib_rbt_bound_t* parent,
231 ib_rbt_node_t* node)
232{
233 /* Cast away the const. */
234 ib_rbt_node_t* last = (ib_rbt_node_t*) parent->last;
235
236 if (last == tree->root || parent->result < 0) {
237 last->left = node;
238 } else {
239 /* FIXME: We don't handle duplicates (yet)! */
240 ut_a(parent->result != 0);
241
242 last->right = node;
243 }
244
245 node->parent = last;
246
247 return(node);
248}
249
250/**********************************************************************/
252static
253ib_rbt_node_t*
254rbt_tree_insert(
255/*============*/
256 ib_rbt_t* tree,
257 const void* key,
258 ib_rbt_node_t* node)
259{
260 ib_rbt_bound_t parent;
261 ib_rbt_node_t* current = ROOT(tree);
262
263 parent.result = 0;
264 parent.last = tree->root;
265
266 /* Regular binary search. */
267 while (current != tree->nil) {
268
269 parent.last = current;
270 parent.result = tree->compare(key, current->value);
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/**********************************************************************/
288static
289void
290rbt_balance_tree(
291/*=============*/
292 const ib_rbt_t* tree,
293 ib_rbt_node_t* node)
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/**********************************************************************/
379static
380ib_rbt_node_t*
381rbt_find_successor(
382/*===============*/
383 const ib_rbt_t* tree,
384 const ib_rbt_node_t* current)
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/**********************************************************************/
419static
420ib_rbt_node_t*
421rbt_find_predecessor(
422/*=================*/
423 const ib_rbt_t* tree,
424 const ib_rbt_node_t* current)
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/**********************************************************************/
459static
460void
461rbt_eject_node(
462/*===========*/
463 ib_rbt_node_t* eject,
464 ib_rbt_node_t* node)
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/**********************************************************************/
482static
483void
484rbt_replace_node(
485/*=============*/
486 ib_rbt_node_t* replace,
487 ib_rbt_node_t* node)
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/**********************************************************************/
510static
511ib_rbt_node_t*
512rbt_detach_node(
513/*============*/
514 const ib_rbt_t* tree,
515 ib_rbt_node_t* node)
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/**********************************************************************/
553static
554ib_rbt_node_t*
555rbt_balance_right(
556/*==============*/
557 const ib_rbt_node_t* nil,
558 ib_rbt_node_t* parent,
559 ib_rbt_node_t* sibling)
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/**********************************************************************/
613static
614ib_rbt_node_t*
615rbt_balance_left(
616/*=============*/
617 const ib_rbt_node_t* nil,
618 ib_rbt_node_t* parent,
619 ib_rbt_node_t* sibling)
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/**********************************************************************/
672static
673void
674rbt_remove_node_and_rebalance(
675/*==========================*/
676 ib_rbt_t* tree,
677 ib_rbt_node_t* node)
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/**********************************************************************/
724static
725void
726rbt_free_node(
727/*==========*/
728 ib_rbt_node_t* node,
729 ib_rbt_node_t* nil)
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/**********************************************************************/
741UNIV_INTERN
742void
744/*=====*/
745 ib_rbt_t* tree)
746{
747 rbt_free_node(tree->root, tree->nil);
748 ut_free(tree->nil);
749 ut_free(tree);
750}
751
752/**********************************************************************/
755UNIV_INTERN
756ib_rbt_t*
758/*=======*/
759 size_t sizeof_value,
760 ib_rbt_compare compare)
761{
762 ib_rbt_t* tree;
763 ib_rbt_node_t* node;
764
765 tree = (ib_rbt_t*) ut_malloc(sizeof(*tree));
766 memset(tree, 0, sizeof(*tree));
767
768 tree->sizeof_value = sizeof_value;
769
770 /* Create the sentinel (NIL) node. */
771 node = tree->nil = (ib_rbt_node_t*) ut_malloc(sizeof(*node));
772 memset(node, 0, sizeof(*node));
773
774 node->color = IB_RBT_BLACK;
775 node->parent = node->left = node->right = node;
776
777 /* Create the "fake" root, the real root node will be the
778 left child of this node. */
779 node = tree->root = (ib_rbt_node_t*) ut_malloc(sizeof(*node));
780 memset(node, 0, sizeof(*node));
781
782 node->color = IB_RBT_BLACK;
783 node->parent = node->left = node->right = tree->nil;
784
785 tree->compare = compare;
786
787 return(tree);
788}
789
790/**********************************************************************/
793UNIV_INTERN
794const ib_rbt_node_t*
796/*=======*/
797 ib_rbt_t* tree,
798 const void* key,
799 const void* value)
801{
802 ib_rbt_node_t* node;
803
804 /* Create the node that will hold the value data. */
805 node = (ib_rbt_node_t*) ut_malloc(SIZEOF_NODE(tree));
806
807 memcpy(node->value, value, tree->sizeof_value);
808 node->parent = node->left = node->right = tree->nil;
809
810 /* Insert in the tree in the usual way. */
811 rbt_tree_insert(tree, key, node);
812 rbt_balance_tree(tree, node);
813
814 ++tree->n_nodes;
815
816 return(node);
817}
818
819/**********************************************************************/
822UNIV_INTERN
823const ib_rbt_node_t*
825/*=========*/
826 ib_rbt_t* tree,
827 ib_rbt_bound_t* parent,
828 const void* value)
830{
831 ib_rbt_node_t* node;
832
833 /* Create the node that will hold the value data */
834 node = (ib_rbt_node_t*) ut_malloc(SIZEOF_NODE(tree));
835
836 memcpy(node->value, value, tree->sizeof_value);
837 node->parent = node->left = node->right = tree->nil;
838
839 /* If tree is empty */
840 if (parent->last == NULL) {
841 parent->last = tree->root;
842 }
843
844 /* Append the node, the hope here is that the caller knows
845 what s/he is doing. */
846 rbt_tree_add_child(tree, parent, node);
847 rbt_balance_tree(tree, node);
848
849 ++tree->n_nodes;
850
851#if defined(IB_RBT_TESTING)
852 ut_a(rbt_validate(tree));
853#endif
854 return(node);
855}
856
857/**********************************************************************/
860UNIV_INTERN
861const ib_rbt_node_t*
863/*=======*/
864 const ib_rbt_t* tree,
865 const void* key)
866{
867 const ib_rbt_node_t* current = ROOT(tree);
868
869 /* Regular binary search. */
870 while (current != tree->nil) {
871 int result = tree->compare(key, current->value);
872
873 if (result < 0) {
874 current = current->left;
875 } else if (result > 0) {
876 current = current->right;
877 } else {
878 break;
879 }
880 }
881
882 return(current != tree->nil ? current : NULL);
883}
884
885/**********************************************************************/
888UNIV_INTERN
889ibool
891/*=======*/
892 ib_rbt_t* tree,
893 const void* key)
894{
895 ibool deleted = FALSE;
896 ib_rbt_node_t* node = (ib_rbt_node_t*) rbt_lookup(tree, key);
897
898 if (node) {
899 rbt_remove_node_and_rebalance(tree, node);
900
901 ut_free(node);
902 deleted = TRUE;
903 }
904
905 return(deleted);
906}
907
908/**********************************************************************/
912UNIV_INTERN
913ib_rbt_node_t*
915/*============*/
916 ib_rbt_t* tree,
917 const ib_rbt_node_t* const_node)
921{
922 /* Cast away the const. */
923 rbt_remove_node_and_rebalance(tree, (ib_rbt_node_t*) const_node);
924
925 /* This is to make it easier to do something like this:
926 ut_free(rbt_remove_node(node));
927 */
928
929 return((ib_rbt_node_t*) const_node);
930}
931
932/**********************************************************************/
935UNIV_INTERN
936const ib_rbt_node_t*
938/*============*/
939 const ib_rbt_t* tree,
940 const void* key)
941{
942 ib_rbt_node_t* lb_node = NULL;
943 ib_rbt_node_t* current = ROOT(tree);
944
945 while (current != tree->nil) {
946 int result = tree->compare(key, current->value);
947
948 if (result > 0) {
949
950 current = current->right;
951
952 } else if (result < 0) {
953
954 lb_node = current;
955 current = current->left;
956
957 } else {
958 lb_node = current;
959 break;
960 }
961 }
962
963 return(lb_node);
964}
965
966/**********************************************************************/
969UNIV_INTERN
970const ib_rbt_node_t*
972/*============*/
973 const ib_rbt_t* tree,
974 const void* key)
975{
976 ib_rbt_node_t* ub_node = NULL;
977 ib_rbt_node_t* current = ROOT(tree);
978
979 while (current != tree->nil) {
980 int result = tree->compare(key, current->value);
981
982 if (result > 0) {
983
984 ub_node = current;
985 current = current->right;
986
987 } else if (result < 0) {
988
989 current = current->left;
990
991 } else {
992 ub_node = current;
993 break;
994 }
995 }
996
997 return(ub_node);
998}
999
1000/**********************************************************************/
1003UNIV_INTERN
1004int
1006/*=======*/
1007 const ib_rbt_t* tree,
1008 ib_rbt_bound_t* parent,
1009 const void* key)
1010{
1011 ib_rbt_node_t* current = ROOT(tree);
1012
1013 /* Every thing is greater than the NULL root. */
1014 parent->result = 1;
1015 parent->last = NULL;
1016
1017 while (current != tree->nil) {
1018
1019 parent->last = current;
1020 parent->result = tree->compare(key, current->value);
1021
1022 if (parent->result > 0) {
1023 current = current->right;
1024 } else if (parent->result < 0) {
1025 current = current->left;
1026 } else {
1027 break;
1028 }
1029 }
1030
1031 return(parent->result);
1032}
1033
1034/**********************************************************************/
1038UNIV_INTERN
1039int
1041/*===========*/
1042 const ib_rbt_t* tree,
1043 ib_rbt_bound_t* parent,
1044 const void* key,
1045 ib_rbt_compare compare)
1046{
1047 ib_rbt_node_t* current = ROOT(tree);
1048
1049 /* Every thing is greater than the NULL root. */
1050 parent->result = 1;
1051 parent->last = NULL;
1052
1053 while (current != tree->nil) {
1054
1055 parent->last = current;
1056 parent->result = compare(key, current->value);
1057
1058 if (parent->result > 0) {
1059 current = current->right;
1060 } else if (parent->result < 0) {
1061 current = current->left;
1062 } else {
1063 break;
1064 }
1065 }
1066
1067 return(parent->result);
1068}
1069
1070/**********************************************************************/
1072UNIV_INTERN
1073const ib_rbt_node_t*
1075/*======*/
1076 /* out leftmost node or NULL */
1077 const ib_rbt_t* tree) /* in: rb tree */
1078{
1079 ib_rbt_node_t* first = NULL;
1080 ib_rbt_node_t* current = ROOT(tree);
1081
1082 while (current != tree->nil) {
1083 first = current;
1084 current = current->left;
1085 }
1086
1087 return(first);
1088}
1089
1090/**********************************************************************/
1093UNIV_INTERN
1094const ib_rbt_node_t*
1096/*=====*/
1097 const ib_rbt_t* tree)
1098{
1099 ib_rbt_node_t* last = NULL;
1100 ib_rbt_node_t* current = ROOT(tree);
1101
1102 while (current != tree->nil) {
1103 last = current;
1104 current = current->right;
1105 }
1106
1107 return(last);
1108}
1109
1110/**********************************************************************/
1113UNIV_INTERN
1114const ib_rbt_node_t*
1116/*=====*/
1117 const ib_rbt_t* tree,
1118 const ib_rbt_node_t* current)
1119{
1120 return(current ? rbt_find_successor(tree, current) : NULL);
1121}
1122
1123/**********************************************************************/
1126UNIV_INTERN
1127const ib_rbt_node_t*
1129/*=====*/
1130 const ib_rbt_t* tree,
1131 const ib_rbt_node_t* current)
1132{
1133 return(current ? rbt_find_predecessor(tree, current) : NULL);
1134}
1135
1136/**********************************************************************/
1138UNIV_INTERN
1139void
1141/*======*/
1142 ib_rbt_t* tree)
1143{
1144 rbt_free_node(ROOT(tree), tree->nil);
1145
1146 tree->n_nodes = 0;
1147 tree->root->left = tree->root->right = tree->nil;
1148}
1149
1150/**********************************************************************/
1153UNIV_INTERN
1154ulint
1156/*===========*/
1157 ib_rbt_t* dst,
1158 const ib_rbt_t* src)
1159{
1160 ib_rbt_bound_t parent;
1161 ulint n_merged = 0;
1162 const ib_rbt_node_t* src_node = rbt_first(src);
1163
1164 if (rbt_empty(src) || dst == src) {
1165 return(0);
1166 }
1167
1168 for (/* No op */; src_node; src_node = rbt_next(src, src_node)) {
1169
1170 if (rbt_search(dst, &parent, src_node->value) != 0) {
1171 rbt_add_node(dst, &parent, src_node->value);
1172 ++n_merged;
1173 }
1174 }
1175
1176 return(n_merged);
1177}
1178
1179/**********************************************************************/
1184UNIV_INTERN
1185ulint
1187/*=======================*/
1188 ib_rbt_t* dst,
1189 ib_rbt_t* src)
1190{
1191 ib_rbt_bound_t parent;
1192 ib_rbt_node_t* src_node;
1193 ulint old_size = rbt_size(dst);
1194
1195 if (rbt_empty(src) || dst == src) {
1196 return(0);
1197 }
1198
1199 for (src_node = (ib_rbt_node_t*) rbt_first(src); src_node; /* */) {
1200 ib_rbt_node_t* prev = src_node;
1201
1202 src_node = (ib_rbt_node_t*)rbt_next(src, prev);
1203
1204 /* Skip duplicates. */
1205 if (rbt_search(dst, &parent, prev->value) != 0) {
1206
1207 /* Remove and reset the node but preserve
1208 the node (data) value. */
1209 rbt_remove_node_and_rebalance(src, prev);
1210
1211 /* The nil should be taken from the dst tree. */
1212 prev->parent = prev->left = prev->right = dst->nil;
1213 rbt_tree_add_child(dst, &parent, prev);
1214 rbt_balance_tree(dst, prev);
1215
1216 ++dst->n_nodes;
1217 }
1218 }
1219
1220#if defined(IB_RBT_TESTING)
1221 ut_a(rbt_validate(dst));
1222 ut_a(rbt_validate(src));
1223#endif
1224 return(rbt_size(dst) - old_size);
1225}
1226
1227/**********************************************************************/
1231UNIV_INTERN
1232ibool
1234/*=========*/
1235 const ib_rbt_t* tree)
1236{
1237 if (rbt_count_black_nodes(tree, ROOT(tree)) > 0) {
1238 return(rbt_check_ordering(tree));
1239 }
1240
1241 return(FALSE);
1242}
1243
1244/**********************************************************************/
1246UNIV_INTERN
1247void
1249/*======*/
1250 const ib_rbt_t* tree,
1251 ib_rbt_print_node print)
1252{
1253 rbt_print_subtree(tree, ROOT(tree), print);
1254}
#define ut_error
Definition ut0dbg.h:115
#define ut_a(EXPR)
Definition ut0dbg.h:105
UNIV_INTERN void ut_free(void *ptr)
Definition ut0mem.cc:294
UNIV_INTERN void * ut_malloc(ulint n)
Definition ut0mem.cc:235
UNIV_INTERN ib_rbt_node_t * rbt_remove_node(ib_rbt_t *tree, const ib_rbt_node_t *node)
Definition ut0rbt.cc:914
UNIV_INTERN void rbt_free(ib_rbt_t *tree)
Definition ut0rbt.cc:743
UNIV_INTERN const ib_rbt_node_t * rbt_lookup(const ib_rbt_t *tree, const void *key)
Definition ut0rbt.cc:862
UNIV_INTERN const ib_rbt_node_t * rbt_first(const ib_rbt_t *tree)
Definition ut0rbt.cc:1074
UNIV_INTERN void rbt_clear(ib_rbt_t *tree)
Definition ut0rbt.cc:1140
UNIV_INTERN const ib_rbt_node_t * rbt_add_node(ib_rbt_t *tree, ib_rbt_bound_t *parent, const void *value)
Definition ut0rbt.cc:824
UNIV_INTERN ibool rbt_validate(const ib_rbt_t *tree)
Definition ut0rbt.cc:1233
UNIV_INTERN const ib_rbt_node_t * rbt_next(const ib_rbt_t *tree, const ib_rbt_node_t *current)
Definition ut0rbt.cc:1115
UNIV_INTERN int rbt_search(const ib_rbt_t *tree, ib_rbt_bound_t *parent, const void *key)
Definition ut0rbt.cc:1005
UNIV_INTERN ib_rbt_t * rbt_create(size_t sizeof_value, ib_rbt_compare compare)
Definition ut0rbt.cc:757
UNIV_INTERN const ib_rbt_node_t * rbt_last(const ib_rbt_t *tree)
Definition ut0rbt.cc:1095
UNIV_INTERN ulint rbt_merge_uniq(ib_rbt_t *dst, const ib_rbt_t *src)
Definition ut0rbt.cc:1155
UNIV_INTERN void rbt_print(const ib_rbt_t *tree, ib_rbt_print_node print)
Definition ut0rbt.cc:1248
UNIV_INTERN const ib_rbt_node_t * rbt_upper_bound(const ib_rbt_t *tree, const void *key)
Definition ut0rbt.cc:971
UNIV_INTERN ulint rbt_merge_uniq_destructive(ib_rbt_t *dst, ib_rbt_t *src)
Definition ut0rbt.cc:1186
UNIV_INTERN int rbt_search_cmp(const ib_rbt_t *tree, ib_rbt_bound_t *parent, const void *key, ib_rbt_compare compare)
Definition ut0rbt.cc:1040
UNIV_INTERN const ib_rbt_node_t * rbt_lower_bound(const ib_rbt_t *tree, const void *key)
Definition ut0rbt.cc:937
UNIV_INTERN ibool rbt_delete(ib_rbt_t *tree, const void *key)
Definition ut0rbt.cc:890
UNIV_INTERN const ib_rbt_node_t * rbt_prev(const ib_rbt_t *tree, const ib_rbt_node_t *current)
Definition ut0rbt.cc:1128
UNIV_INTERN const ib_rbt_node_t * rbt_insert(ib_rbt_t *tree, const void *key, const void *value)
Definition ut0rbt.cc:795