1
/*****************************************************************************
3
Copyright (c) 2006, 2009, Innobase Oy. All Rights Reserved.
5
This program is free software; you can redistribute it and/or modify it under
6
the terms of the GNU General Public License as published by the Free Software
7
Foundation; version 2 of the License.
9
This program is distributed in the hope that it will be useful, but WITHOUT
10
ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
11
FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
13
You should have received a copy of the GNU General Public License along with
14
this program; if not, write to the Free Software Foundation, Inc., 59 Temple
15
Place, Suite 330, Boston, MA 02111-1307 USA
17
*****************************************************************************/
19
/*******************************************************************//**
21
Red-Black tree implementation
23
Created 2007-03-20 Sunny Bains
24
***********************************************************************/
28
/************************************************************************
29
Definition of a red-black tree
30
==============================
32
A red-black tree is a binary search tree which has the following
35
1. Every node is either red or black.
36
2. Every leaf (NULL - in our case tree->nil) is black.
37
3. If a node is red, then both its children are black.
38
4. Every simple path from a node to a descendant leaf contains the
39
same number of black nodes.
41
from (3) above, the implication is that on any path from the root
42
to a leaf, red nodes must not be adjacent.
44
However, any number of black nodes may appear in a sequence. */
46
#if defined(IB_RBT_TESTING)
47
#warning "Testing enabled!"
50
#define ROOT(t) (t->root->left)
51
#define SIZEOF_NODE(t) ((sizeof(ib_rbt_node_t) + t->sizeof_value) - 1)
53
/****************************************************************//**
54
Print out the sub-tree recursively. */
59
const ib_rbt_t* tree, /*!< in: tree to traverse */
60
const ib_rbt_node_t* node, /*!< in: node to print */
61
ib_rbt_print_node print) /*!< in: print key function */
63
/* FIXME: Doesn't do anything yet */
64
if (node != tree->nil) {
66
rbt_print_subtree(tree, node->left, print);
67
rbt_print_subtree(tree, node->right, print);
71
/****************************************************************//**
72
Verify that the keys are in order.
73
@return TRUE of OK. FALSE if not ordered */
78
const ib_rbt_t* tree) /*!< in: tree to verfify */
80
const ib_rbt_node_t* node;
81
const ib_rbt_node_t* prev = NULL;
83
/* Iterate over all the nodes, comparing each node with the prev */
84
for (node = rbt_first(tree); node; node = rbt_next(tree, prev)) {
86
if (prev && tree->compare(prev->value, node->value) >= 0) {
96
/****************************************************************//**
97
Check that every path from the root to the leaves has the same count.
98
Count is expressed in the number of black nodes.
99
@return 0 on failure else black height of the subtree */
102
rbt_count_black_nodes(
103
/*==================*/
104
const ib_rbt_t* tree, /*!< in: tree to verify */
105
const ib_rbt_node_t* node) /*!< in: start of sub-tree */
109
if (node != tree->nil) {
110
ulint left_height = rbt_count_black_nodes(tree, node->left);
112
ulint right_height = rbt_count_black_nodes(tree, node->right);
116
|| left_height != right_height) {
119
} else if (node->color == IB_RBT_RED) {
122
if (node->left->color != IB_RBT_BLACK
123
|| node->right->color != IB_RBT_BLACK) {
127
result = left_height;
129
/* Check if it's anything other than RED or BLACK. */
130
} else if (node->color != IB_RBT_BLACK) {
135
result = right_height + 1;
144
/****************************************************************//**
145
Turn the node's right child's left sub-tree into node's right sub-tree.
146
This will also make node's right child it's parent. */
151
const ib_rbt_node_t* nil, /*!< in: nil node of the tree */
152
ib_rbt_node_t* node) /*!< in: node to rotate */
154
ib_rbt_node_t* right = node->right;
156
node->right = right->left;
158
if (right->left != nil) {
159
right->left->parent = node;
162
/* Right's new parent was node's parent. */
163
right->parent = node->parent;
165
/* Since root's parent is tree->nil and root->parent->left points
166
back to root, we can avoid the check. */
167
if (node == node->parent->left) {
168
/* Node was on the left of its parent. */
169
node->parent->left = right;
171
/* Node must have been on the right. */
172
node->parent->right = right;
175
/* Finally, put node on right's left. */
177
node->parent = right;
180
/****************************************************************//**
181
Turn the node's left child's right sub-tree into node's left sub-tree.
182
This also make node's left child it's parent. */
187
const ib_rbt_node_t* nil, /*!< in: nil node of tree */
188
ib_rbt_node_t* node) /*!< in: node to rotate */
190
ib_rbt_node_t* left = node->left;
192
node->left = left->right;
194
if (left->right != nil) {
195
left->right->parent = node;
198
/* Left's new parent was node's parent. */
199
left->parent = node->parent;
201
/* Since root's parent is tree->nil and root->parent->left points
202
back to root, we can avoid the check. */
203
if (node == node->parent->right) {
204
/* Node was on the left of its parent. */
205
node->parent->right = left;
207
/* Node must have been on the left. */
208
node->parent->left = left;
211
/* Finally, put node on left's right. */
216
/****************************************************************//**
217
Append a node to the tree.
218
@return inserted node */
223
const ib_rbt_t* tree, /*!< in: rbt tree */
224
ib_rbt_bound_t* parent, /*!< in: node's parent */
225
ib_rbt_node_t* node) /*!< in: node to add */
227
/* Cast away the const. */
228
ib_rbt_node_t* last = (ib_rbt_node_t*) parent->last;
230
if (last == tree->root || parent->result < 0) {
233
/* FIXME: We don't handle duplicates (yet)! */
234
ut_a(parent->result != 0);
244
/****************************************************************//**
245
Generic binary tree insert
246
@return inserted node */
251
ib_rbt_t* tree, /*!< in: rb tree */
252
const void* key, /*!< in: key for ordering */
253
ib_rbt_node_t* node) /*!< in: node hold the insert value */
255
ib_rbt_bound_t parent;
256
ib_rbt_node_t* current = ROOT(tree);
259
parent.last = tree->root;
261
/* Regular binary search. */
262
while (current != tree->nil) {
264
parent.last = current;
265
parent.result = tree->compare(key, current->value);
267
if (parent.result < 0) {
268
current = current->left;
270
current = current->right;
274
ut_a(current == tree->nil);
276
rbt_tree_add_child(tree, &parent, node);
281
/****************************************************************//**
282
Balance a tree after inserting a node. */
287
const ib_rbt_t* tree, /*!< in: tree to balance */
288
ib_rbt_node_t* node) /*!< in: node that was inserted */
290
const ib_rbt_node_t* nil = tree->nil;
291
ib_rbt_node_t* parent = node->parent;
293
/* Restore the red-black property. */
294
node->color = IB_RBT_RED;
296
while (node != ROOT(tree) && parent->color == IB_RBT_RED) {
297
ib_rbt_node_t* grand_parent = parent->parent;
299
if (parent == grand_parent->left) {
300
ib_rbt_node_t* uncle = grand_parent->right;
302
if (uncle->color == IB_RBT_RED) {
304
/* Case 1 - change the colors. */
305
uncle->color = IB_RBT_BLACK;
306
parent->color = IB_RBT_BLACK;
307
grand_parent->color = IB_RBT_RED;
309
/* Move node up the tree. */
314
if (node == parent->right) {
315
/* Right is a black node and node is
316
to the right, case 2 - move node
319
rbt_rotate_left(nil, node);
322
grand_parent = node->parent->parent;
325
node->parent->color = IB_RBT_BLACK;
326
grand_parent->color = IB_RBT_RED;
328
rbt_rotate_right(nil, grand_parent);
332
ib_rbt_node_t* uncle = grand_parent->left;
334
if (uncle->color == IB_RBT_RED) {
336
/* Case 1 - change the colors. */
337
uncle->color = IB_RBT_BLACK;
338
parent->color = IB_RBT_BLACK;
339
grand_parent->color = IB_RBT_RED;
341
/* Move node up the tree. */
346
if (node == parent->left) {
347
/* Left is a black node and node is to
348
the right, case 2 - move node up and
351
rbt_rotate_right(nil, node);
354
grand_parent = node->parent->parent;
357
node->parent->color = IB_RBT_BLACK;
358
grand_parent->color = IB_RBT_RED;
360
rbt_rotate_left(nil, grand_parent);
364
parent = node->parent;
367
/* Color the root black. */
368
ROOT(tree)->color = IB_RBT_BLACK;
371
/****************************************************************//**
372
Find the given node's successor.
373
@return successor node or NULL if no successor */
378
const ib_rbt_t* tree, /*!< in: rb tree */
379
const ib_rbt_node_t* current)/*!< in: this is declared const
380
because it can be called via
383
const ib_rbt_node_t* nil = tree->nil;
384
ib_rbt_node_t* next = current->right;
386
/* Is there a sub-tree to the right that we can follow. */
389
/* Follow the left most links of the current right child. */
390
while (next->left != nil) {
394
} else { /* We will have to go up the tree to find the successor. */
395
ib_rbt_node_t* parent = current->parent;
397
/* Cast away the const. */
398
next = (ib_rbt_node_t*) current;
400
while (parent != tree->root && next == parent->right) {
402
parent = next->parent;
405
next = (parent == tree->root) ? NULL : parent;
411
/****************************************************************//**
412
Find the given node's precedecessor.
413
@return predecessor node or NULL if no predecesor */
416
rbt_find_predecessor(
417
/*=================*/
418
const ib_rbt_t* tree, /*!< in: rb tree */
419
const ib_rbt_node_t* current) /*!< in: this is declared const
420
because it can be called via
423
const ib_rbt_node_t* nil = tree->nil;
424
ib_rbt_node_t* prev = current->left;
426
/* Is there a sub-tree to the left that we can follow. */
429
/* Follow the right most links of the current left child. */
430
while (prev->right != nil) {
434
} else { /* We will have to go up the tree to find the precedecessor. */
435
ib_rbt_node_t* parent = current->parent;
437
/* Cast away the const. */
438
prev = (ib_rbt_node_t*)current;
440
while (parent != tree->root && prev == parent->left) {
442
parent = prev->parent;
445
prev = (parent == tree->root) ? NULL : parent;
451
/****************************************************************//**
452
Replace node with child. After applying transformations eject becomes
458
ib_rbt_node_t* eject, /*!< in: node to eject */
459
ib_rbt_node_t* node) /*!< in: node to replace with */
461
/* Update the to be ejected node's parent's child pointers. */
462
if (eject->parent->left == eject) {
463
eject->parent->left = node;
464
} else if (eject->parent->right == eject) {
465
eject->parent->right = node;
469
/* eject is now an orphan but otherwise its pointers
470
and color are left intact. */
472
node->parent = eject->parent;
475
/****************************************************************//**
476
Replace a node with another node. */
481
ib_rbt_node_t* replace, /*!< in: node to replace */
482
ib_rbt_node_t* node) /*!< in: node to replace with */
484
ib_rbt_color_t color = node->color;
486
/* Update the node pointers. */
487
node->left = replace->left;
488
node->right = replace->right;
490
/* Update the child node pointers. */
491
node->left->parent = node;
492
node->right->parent = node;
494
/* Make the parent of replace point to node. */
495
rbt_eject_node(replace, node);
497
/* Swap the colors. */
498
node->color = replace->color;
499
replace->color = color;
502
/****************************************************************//**
503
Detach node from the tree replacing it with one of it's children.
504
@return the child node that now occupies the position of the detached node */
509
const ib_rbt_t* tree, /*!< in: rb tree */
510
ib_rbt_node_t* node) /*!< in: node to detach */
512
ib_rbt_node_t* child;
513
const ib_rbt_node_t* nil = tree->nil;
515
if (node->left != nil && node->right != nil) {
516
/* Case where the node to be deleted has two children. */
517
ib_rbt_node_t* successor = rbt_find_successor(tree, node);
519
ut_a(successor != nil);
520
ut_a(successor->parent != nil);
521
ut_a(successor->left == nil);
523
child = successor->right;
525
/* Remove the successor node and replace with its child. */
526
rbt_eject_node(successor, child);
528
/* Replace the node to delete with its successor node. */
529
rbt_replace_node(node, successor);
531
ut_a(node->left == nil || node->right == nil);
533
child = (node->left != nil) ? node->left : node->right;
535
/* Replace the node to delete with one of it's children. */
536
rbt_eject_node(node, child);
539
/* Reset the node links. */
540
node->parent = node->right = node->left = tree->nil;
545
/****************************************************************//**
546
Rebalance the right sub-tree after deletion.
547
@return node to rebalance if more rebalancing required else NULL */
552
const ib_rbt_node_t* nil, /*!< in: rb tree nil node */
553
ib_rbt_node_t* parent, /*!< in: parent node */
554
ib_rbt_node_t* sibling)/*!< in: sibling node */
556
ib_rbt_node_t* node = NULL;
558
ut_a(sibling != nil);
561
if (sibling->color == IB_RBT_RED) {
563
parent->color = IB_RBT_RED;
564
sibling->color = IB_RBT_BLACK;
566
rbt_rotate_left(nil, parent);
568
sibling = parent->right;
570
ut_a(sibling != nil);
573
/* Since this will violate case 3 because of the change above. */
574
if (sibling->left->color == IB_RBT_BLACK
575
&& sibling->right->color == IB_RBT_BLACK) {
577
node = parent; /* Parent needs to be rebalanced too. */
578
sibling->color = IB_RBT_RED;
581
if (sibling->right->color == IB_RBT_BLACK) {
583
ut_a(sibling->left->color == IB_RBT_RED);
585
sibling->color = IB_RBT_RED;
586
sibling->left->color = IB_RBT_BLACK;
588
rbt_rotate_right(nil, sibling);
590
sibling = parent->right;
591
ut_a(sibling != nil);
594
sibling->color = parent->color;
595
sibling->right->color = IB_RBT_BLACK;
597
parent->color = IB_RBT_BLACK;
599
rbt_rotate_left(nil, parent);
605
/****************************************************************//**
606
Rebalance the left sub-tree after deletion.
607
@return node to rebalance if more rebalancing required else NULL */
612
const ib_rbt_node_t* nil, /*!< in: rb tree nil node */
613
ib_rbt_node_t* parent, /*!< in: parent node */
614
ib_rbt_node_t* sibling)/*!< in: sibling node */
616
ib_rbt_node_t* node = NULL;
618
ut_a(sibling != nil);
621
if (sibling->color == IB_RBT_RED) {
623
parent->color = IB_RBT_RED;
624
sibling->color = IB_RBT_BLACK;
626
rbt_rotate_right(nil, parent);
627
sibling = parent->left;
629
ut_a(sibling != nil);
632
/* Since this will violate case 3 because of the change above. */
633
if (sibling->right->color == IB_RBT_BLACK
634
&& sibling->left->color == IB_RBT_BLACK) {
636
node = parent; /* Parent needs to be rebalanced too. */
637
sibling->color = IB_RBT_RED;
640
if (sibling->left->color == IB_RBT_BLACK) {
642
ut_a(sibling->right->color == IB_RBT_RED);
644
sibling->color = IB_RBT_RED;
645
sibling->right->color = IB_RBT_BLACK;
647
rbt_rotate_left(nil, sibling);
649
sibling = parent->left;
651
ut_a(sibling != nil);
654
sibling->color = parent->color;
655
sibling->left->color = IB_RBT_BLACK;
657
parent->color = IB_RBT_BLACK;
659
rbt_rotate_right(nil, parent);
665
/****************************************************************//**
666
Delete the node and rebalance the tree if necessary */
669
rbt_remove_node_and_rebalance(
670
/*==========================*/
671
ib_rbt_t* tree, /*!< in: rb tree */
672
ib_rbt_node_t* node) /*!< in: node to remove */
674
/* Detach node and get the node that will be used
675
as rebalance start. */
676
ib_rbt_node_t* child = rbt_detach_node(tree, node);
678
if (node->color == IB_RBT_BLACK) {
679
ib_rbt_node_t* last = child;
681
ROOT(tree)->color = IB_RBT_RED;
683
while (child && child->color == IB_RBT_BLACK) {
684
ib_rbt_node_t* parent = child->parent;
686
/* Did the deletion cause an imbalance in the
687
parents left sub-tree. */
688
if (parent->left == child) {
690
child = rbt_balance_right(
691
tree->nil, parent, parent->right);
693
} else if (parent->right == child) {
695
child = rbt_balance_left(
696
tree->nil, parent, parent->left);
709
last->color = IB_RBT_BLACK;
710
ROOT(tree)->color = IB_RBT_BLACK;
713
/* Note that we have removed a node from the tree. */
717
/****************************************************************//**
718
Recursively free the nodes. */
723
ib_rbt_node_t* node, /*!< in: node to free */
724
ib_rbt_node_t* nil) /*!< in: rb tree nil node */
727
rbt_free_node(node->left, nil);
728
rbt_free_node(node->right, nil);
734
/****************************************************************//**
735
Free all the nodes and free the tree. */
740
ib_rbt_t* tree) /*!< in: rb tree to free */
742
rbt_free_node(tree->root, tree->nil);
747
/****************************************************************//**
748
Create an instance of a red black tree.
749
@return an empty rb tree */
754
size_t sizeof_value, /*!< in: sizeof data item */
755
ib_rbt_compare compare) /*!< in: fn to compare items */
760
tree = (ib_rbt_t*) ut_malloc(sizeof(*tree));
761
memset(tree, 0, sizeof(*tree));
763
tree->sizeof_value = sizeof_value;
765
/* Create the sentinel (NIL) node. */
766
node = tree->nil = (ib_rbt_node_t*) ut_malloc(sizeof(*node));
767
memset(node, 0, sizeof(*node));
769
node->color = IB_RBT_BLACK;
770
node->parent = node->left = node->right = node;
772
/* Create the "fake" root, the real root node will be the
773
left child of this node. */
774
node = tree->root = (ib_rbt_node_t*) ut_malloc(sizeof(*node));
775
memset(node, 0, sizeof(*node));
777
node->color = IB_RBT_BLACK;
778
node->parent = node->left = node->right = tree->nil;
780
tree->compare = compare;
785
/****************************************************************//**
786
Generic insert of a value in the rb tree.
787
@return inserted node */
792
ib_rbt_t* tree, /*!< in: rb tree */
793
const void* key, /*!< in: key for ordering */
794
const void* value) /*!< in: value of key, this value
795
is copied to the node */
799
/* Create the node that will hold the value data. */
800
node = (ib_rbt_node_t*) ut_malloc(SIZEOF_NODE(tree));
802
memcpy(node->value, value, tree->sizeof_value);
803
node->parent = node->left = node->right = tree->nil;
805
/* Insert in the tree in the usual way. */
806
rbt_tree_insert(tree, key, node);
807
rbt_balance_tree(tree, node);
814
/****************************************************************//**
815
Add a new node to the tree, useful for data that is pre-sorted.
816
@return appended node */
821
ib_rbt_t* tree, /*!< in: rb tree */
822
ib_rbt_bound_t* parent, /*!< in: bounds */
823
const void* value) /*!< in: this value is copied
828
/* Create the node that will hold the value data */
829
node = (ib_rbt_node_t*) ut_malloc(SIZEOF_NODE(tree));
831
memcpy(node->value, value, tree->sizeof_value);
832
node->parent = node->left = node->right = tree->nil;
834
/* If tree is empty */
835
if (parent->last == NULL) {
836
parent->last = tree->root;
839
/* Append the node, the hope here is that the caller knows
840
what s/he is doing. */
841
rbt_tree_add_child(tree, parent, node);
842
rbt_balance_tree(tree, node);
846
#if defined(IB_RBT_TESTING)
847
ut_a(rbt_validate(tree));
852
/****************************************************************//**
853
Find a matching node in the rb tree.
854
@return NULL if not found else the node where key was found */
859
const ib_rbt_t* tree, /*!< in: rb tree */
860
const void* key) /*!< in: key to use for search */
862
const ib_rbt_node_t* current = ROOT(tree);
864
/* Regular binary search. */
865
while (current != tree->nil) {
866
int result = tree->compare(key, current->value);
869
current = current->left;
870
} else if (result > 0) {
871
current = current->right;
877
return(current != tree->nil ? current : NULL);
880
/****************************************************************//**
881
Delete a node from the red black tree, identified by key.
882
@return TRUE if success FALSE if not found */
887
ib_rbt_t* tree, /*!< in: rb tree */
888
const void* key) /*!< in: key to delete */
890
ibool deleted = FALSE;
891
ib_rbt_node_t* node = (ib_rbt_node_t*) rbt_lookup(tree, key);
894
rbt_remove_node_and_rebalance(tree, node);
903
/****************************************************************//**
904
Remove a node from the rb tree, the node is not free'd, that is the
905
callers responsibility.
906
@return deleted node but without the const */
911
ib_rbt_t* tree, /*!< in: rb tree */
912
const ib_rbt_node_t* const_node) /*!< in: node to delete, this
913
is a fudge and declared const
914
because the caller can access
917
/* Cast away the const. */
918
rbt_remove_node_and_rebalance(tree, (ib_rbt_node_t*) const_node);
920
/* This is to make it easier to do something like this:
921
ut_free(rbt_remove_node(node));
924
return((ib_rbt_node_t*) const_node);
927
/****************************************************************//**
928
Find the node that has the lowest key that is >= key.
929
@return node satisfying the lower bound constraint or NULL */
934
const ib_rbt_t* tree, /*!< in: rb tree */
935
const void* key) /*!< in: key to search */
937
ib_rbt_node_t* lb_node = NULL;
938
ib_rbt_node_t* current = ROOT(tree);
940
while (current != tree->nil) {
941
int result = tree->compare(key, current->value);
945
current = current->right;
947
} else if (result < 0) {
950
current = current->left;
961
/****************************************************************//**
962
Find the node that has the greatest key that is <= key.
963
@return node satisfying the upper bound constraint or NULL */
968
const ib_rbt_t* tree, /*!< in: rb tree */
969
const void* key) /*!< in: key to search */
971
ib_rbt_node_t* ub_node = NULL;
972
ib_rbt_node_t* current = ROOT(tree);
974
while (current != tree->nil) {
975
int result = tree->compare(key, current->value);
980
current = current->right;
982
} else if (result < 0) {
984
current = current->left;
995
/****************************************************************//**
996
Find the node that has the greatest key that is <= key.
997
@return value of result */
1002
const ib_rbt_t* tree, /*!< in: rb tree */
1003
ib_rbt_bound_t* parent, /*!< in: search bounds */
1004
const void* key) /*!< in: key to search */
1006
ib_rbt_node_t* current = ROOT(tree);
1008
/* Every thing is greater than the NULL root. */
1010
parent->last = NULL;
1012
while (current != tree->nil) {
1014
parent->last = current;
1015
parent->result = tree->compare(key, current->value);
1017
if (parent->result > 0) {
1018
current = current->right;
1019
} else if (parent->result < 0) {
1020
current = current->left;
1026
return(parent->result);
1029
/****************************************************************//**
1030
Find the node that has the greatest key that is <= key. But use the
1031
supplied comparison function.
1032
@return value of result */
1037
const ib_rbt_t* tree, /*!< in: rb tree */
1038
ib_rbt_bound_t* parent, /*!< in: search bounds */
1039
const void* key, /*!< in: key to search */
1040
ib_rbt_compare compare) /*!< in: fn to compare items */
1042
ib_rbt_node_t* current = ROOT(tree);
1044
/* Every thing is greater than the NULL root. */
1046
parent->last = NULL;
1048
while (current != tree->nil) {
1050
parent->last = current;
1051
parent->result = compare(key, current->value);
1053
if (parent->result > 0) {
1054
current = current->right;
1055
} else if (parent->result < 0) {
1056
current = current->left;
1062
return(parent->result);
1065
/****************************************************************//**
1066
Get the leftmost node.
1067
Return the left most node in the tree. */
1069
const ib_rbt_node_t*
1072
const ib_rbt_t* tree) /* in: rb tree */
1074
ib_rbt_node_t* first = NULL;
1075
ib_rbt_node_t* current = ROOT(tree);
1077
while (current != tree->nil) {
1079
current = current->left;
1085
/****************************************************************//**
1086
Return the right most node in the tree.
1087
@return the rightmost node or NULL */
1089
const ib_rbt_node_t*
1092
const ib_rbt_t* tree) /*!< in: rb tree */
1094
ib_rbt_node_t* last = NULL;
1095
ib_rbt_node_t* current = ROOT(tree);
1097
while (current != tree->nil) {
1099
current = current->right;
1105
/****************************************************************//**
1106
Return the next node.
1107
@return node next from current */
1109
const ib_rbt_node_t*
1112
const ib_rbt_t* tree, /*!< in: rb tree */
1113
const ib_rbt_node_t* current)/*!< in: current node */
1115
return(current ? rbt_find_successor(tree, current) : NULL);
1118
/****************************************************************//**
1119
Return the previous node.
1120
@return node prev from current */
1122
const ib_rbt_node_t*
1125
const ib_rbt_t* tree, /*!< in: rb tree */
1126
const ib_rbt_node_t* current)/*!< in: current node */
1128
return(current ? rbt_find_predecessor(tree, current) : NULL);
1131
/****************************************************************//**
1132
Reset the tree. Delete all the nodes. */
1137
ib_rbt_t* tree) /*!< in: rb tree */
1139
rbt_free_node(ROOT(tree), tree->nil);
1142
tree->root->left = tree->root->right = tree->nil;
1145
/****************************************************************//**
1146
Merge the node from dst into src. Return the number of nodes merged.
1147
@return no. of recs merged */
1152
ib_rbt_t* dst, /*!< in: dst rb tree */
1153
const ib_rbt_t* src) /*!< in: src rb tree */
1155
ib_rbt_bound_t parent;
1157
const ib_rbt_node_t* src_node = rbt_first(src);
1159
if (rbt_empty(src) || dst == src) {
1163
for (/* No op */; src_node; src_node = rbt_next(src, src_node)) {
1165
if (rbt_search(dst, &parent, src_node->value) != 0) {
1166
rbt_add_node(dst, &parent, src_node->value);
1174
/****************************************************************//**
1175
Merge the node from dst into src. Return the number of nodes merged.
1176
Delete the nodes from src after copying node to dst. As a side effect
1177
the duplicates will be left untouched in the src.
1178
@return no. of recs merged */
1181
rbt_merge_uniq_destructive(
1182
/*=======================*/
1183
ib_rbt_t* dst, /*!< in: dst rb tree */
1184
ib_rbt_t* src) /*!< in: src rb tree */
1186
ib_rbt_bound_t parent;
1187
ib_rbt_node_t* src_node;
1188
ulint old_size = rbt_size(dst);
1190
if (rbt_empty(src) || dst == src) {
1194
for (src_node = (ib_rbt_node_t*) rbt_first(src); src_node; /* */) {
1195
ib_rbt_node_t* prev = src_node;
1197
src_node = (ib_rbt_node_t*)rbt_next(src, prev);
1199
/* Skip duplicates. */
1200
if (rbt_search(dst, &parent, prev->value) != 0) {
1202
/* Remove and reset the node but preserve
1203
the node (data) value. */
1204
rbt_remove_node_and_rebalance(src, prev);
1206
/* The nil should be taken from the dst tree. */
1207
prev->parent = prev->left = prev->right = dst->nil;
1208
rbt_tree_add_child(dst, &parent, prev);
1209
rbt_balance_tree(dst, prev);
1215
#if defined(IB_RBT_TESTING)
1216
ut_a(rbt_validate(dst));
1217
ut_a(rbt_validate(src));
1219
return(rbt_size(dst) - old_size);
1222
/****************************************************************//**
1223
Check that every path from the root to the leaves has the same count and
1224
the tree nodes are in order.
1225
@return TRUE if OK FALSE otherwise */
1230
const ib_rbt_t* tree) /*!< in: RB tree to validate */
1232
if (rbt_count_black_nodes(tree, ROOT(tree)) > 0) {
1233
return(rbt_check_ordering(tree));
1239
/****************************************************************//**
1240
Iterate over the tree in depth first order. */
1245
const ib_rbt_t* tree, /*!< in: tree to traverse */
1246
ib_rbt_print_node print) /*!< in: print function */
1248
rbt_print_subtree(tree, ROOT(tree), print);
added
removed
storage/innodb_plugin/ut/ut0rbt.c
