1
/*****************************************************************************
3
Copyright (c) 2006, 2009, Innobase Oy. All Rights Reserved.
1
/***************************************************************************//**
3
Copyright (c) 2007, 2010, Innobase Oy. All Rights Reserved.
5
Portions of this file contain modifications contributed and copyrighted by
6
Sun Microsystems, Inc. Those modifications are gratefully acknowledged and
7
are described briefly in the InnoDB documentation. The contributions by
8
Sun Microsystems are incorporated with their permission, and subject to the
9
conditions contained in the file COPYING.Sun_Microsystems.
5
11
This program is free software; you can redistribute it and/or modify it under
6
12
the terms of the GNU General Public License as published by the Free Software
15
21
Place, Suite 330, Boston, MA 02111-1307 USA
17
23
*****************************************************************************/
19
/*******************************************************************//**
24
/********************************************************************//**
21
25
Red-Black tree implementation
27
(c) 2007 Oracle/Innobase Oy
23
29
Created 2007-03-20 Sunny Bains
24
30
***********************************************************************/
26
32
#include "ut0rbt.h"
28
/************************************************************************
34
/**********************************************************************//**
29
35
Definition of a red-black tree
30
36
==============================
41
47
from (3) above, the implication is that on any path from the root
42
48
to a leaf, red nodes must not be adjacent.
44
However, any number of black nodes may appear in a sequence. */
50
However, any number of black nodes may appear in a sequence.
46
53
#if defined(IB_RBT_TESTING)
47
54
#warning "Testing enabled!"
50
57
#define ROOT(t) (t->root->left)
51
58
#define SIZEOF_NODE(t) ((sizeof(ib_rbt_node_t) + t->sizeof_value) - 1)
53
/****************************************************************//**
60
/**********************************************************************//**
54
61
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 */
66
const ib_rbt_t* tree, /*!< in: tree to traverse */
67
const ib_rbt_node_t* node, /*!< in: node to print */
68
ib_rbt_print_node print) /*!< in: print key function */
63
70
/* FIXME: Doesn't do anything yet */
64
71
if (node != tree->nil) {
71
/****************************************************************//**
78
/**********************************************************************//**
72
79
Verify that the keys are in order.
73
80
@return TRUE of OK. FALSE if not ordered */
76
83
rbt_check_ordering(
77
84
/*===============*/
78
const ib_rbt_t* tree) /*!< in: tree to verfify */
85
const ib_rbt_t* tree) /*!< in: tree to verfify */
80
87
const ib_rbt_node_t* node;
81
88
const ib_rbt_node_t* prev = NULL;
96
/****************************************************************//**
103
/**********************************************************************//**
97
104
Check that every path from the root to the leaves has the same count.
98
105
Count is expressed in the number of black nodes.
99
106
@return 0 on failure else black height of the subtree */
102
109
rbt_count_black_nodes(
103
110
/*==================*/
104
const ib_rbt_t* tree, /*!< in: tree to verify */
105
const ib_rbt_node_t* node) /*!< in: start of sub-tree */
111
const ib_rbt_t* tree, /*!< in: tree to verify */
112
const ib_rbt_node_t* node) /*!< in: start of sub-tree */
144
/****************************************************************//**
151
/**********************************************************************//**
145
152
Turn the node's right child's left sub-tree into node's right sub-tree.
146
153
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 */
158
const ib_rbt_node_t* nil, /*!< in: nil node of the tree */
159
ib_rbt_node_t* node) /*!< in: node to rotate */
154
161
ib_rbt_node_t* right = node->right;
177
184
node->parent = right;
180
/****************************************************************//**
187
/**********************************************************************//**
181
188
Turn the node's left child's right sub-tree into node's left sub-tree.
182
189
This also make node's left child it's parent. */
185
192
rbt_rotate_right(
186
193
/*=============*/
187
const ib_rbt_node_t* nil, /*!< in: nil node of tree */
188
ib_rbt_node_t* node) /*!< in: node to rotate */
194
const ib_rbt_node_t* nil, /*!< in: nil node of tree */
195
ib_rbt_node_t* node) /*!< in: node to rotate */
190
197
ib_rbt_node_t* left = node->left;
213
220
node->parent = left;
216
/****************************************************************//**
217
Append a node to the tree.
218
@return inserted node */
223
/**********************************************************************//**
224
Append a node to the tree. */
221
227
rbt_tree_add_child(
222
228
/*===============*/
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 */
229
const ib_rbt_t* tree,
230
ib_rbt_bound_t* parent,
227
233
/* Cast away the const. */
228
234
ib_rbt_node_t* last = (ib_rbt_node_t*) parent->last;
244
/****************************************************************//**
245
Generic binary tree insert
246
@return inserted node */
250
/**********************************************************************//**
251
Generic binary tree insert */
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
260
ib_rbt_bound_t parent;
256
261
ib_rbt_node_t* current = ROOT(tree);
281
/****************************************************************//**
286
/**********************************************************************//**
282
287
Balance a tree after inserting a node. */
285
290
rbt_balance_tree(
286
291
/*=============*/
287
const ib_rbt_t* tree, /*!< in: tree to balance */
288
ib_rbt_node_t* node) /*!< in: node that was inserted */
292
const ib_rbt_t* tree, /*!< in: tree to balance */
293
ib_rbt_node_t* node) /*!< in: node that was inserted */
290
295
const ib_rbt_node_t* nil = tree->nil;
291
296
ib_rbt_node_t* parent = node->parent;
368
373
ROOT(tree)->color = IB_RBT_BLACK;
371
/****************************************************************//**
376
/**********************************************************************//**
372
377
Find the given node's successor.
373
378
@return successor node or NULL if no successor */
376
381
rbt_find_successor(
377
382
/*===============*/
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_t* tree, /*!< in: rb tree */
384
const ib_rbt_node_t* current) /*!< in: this is declared const
385
because it can be called via
383
388
const ib_rbt_node_t* nil = tree->nil;
384
389
ib_rbt_node_t* next = current->right;
411
/****************************************************************//**
416
/**********************************************************************//**
412
417
Find the given node's precedecessor.
413
418
@return predecessor node or NULL if no predecesor */
451
/****************************************************************//**
456
/**********************************************************************//**
452
457
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 */
463
ib_rbt_node_t* eject, /*!< in: node to eject */
464
ib_rbt_node_t* node) /*!< in: node to replace with */
461
466
/* Update the to be ejected node's parent's child pointers. */
462
467
if (eject->parent->left == eject) {
472
477
node->parent = eject->parent;
475
/****************************************************************//**
480
/**********************************************************************//**
476
481
Replace a node with another node. */
479
484
rbt_replace_node(
480
485
/*=============*/
481
ib_rbt_node_t* replace, /*!< in: node to replace */
482
ib_rbt_node_t* node) /*!< in: node to replace with */
486
ib_rbt_node_t* replace, /*!< in: node to replace */
487
ib_rbt_node_t* node) /*!< in: node to replace with */
484
489
ib_rbt_color_t color = node->color;
499
504
replace->color = color;
502
/****************************************************************//**
507
/**********************************************************************//**
503
508
Detach node from the tree replacing it with one of it's children.
504
509
@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 */
514
const ib_rbt_t* tree, /*!< in: rb tree */
515
ib_rbt_node_t* node) /*!< in: node to detach */
512
517
ib_rbt_node_t* child;
513
518
const ib_rbt_node_t* nil = tree->nil;
545
/****************************************************************//**
550
/**********************************************************************//**
546
551
Rebalance the right sub-tree after deletion.
547
552
@return node to rebalance if more rebalancing required else NULL */
550
555
rbt_balance_right(
551
556
/*==============*/
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 */
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 */
556
561
ib_rbt_node_t* node = NULL;
605
/****************************************************************//**
610
/**********************************************************************//**
606
611
Rebalance the left sub-tree after deletion.
607
612
@return node to rebalance if more rebalancing required else NULL */
610
615
rbt_balance_left(
611
616
/*=============*/
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 */
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 */
616
621
ib_rbt_node_t* node = NULL;
665
/****************************************************************//**
670
/**********************************************************************//**
666
671
Delete the node and rebalance the tree if necessary */
669
674
rbt_remove_node_and_rebalance(
670
675
/*==========================*/
671
ib_rbt_t* tree, /*!< in: rb tree */
672
ib_rbt_node_t* node) /*!< in: node to remove */
676
ib_rbt_t* tree, /*!< in: rb tree */
677
ib_rbt_node_t* node) /*!< in: node to remove */
674
679
/* Detach node and get the node that will be used
675
680
as rebalance start. */
717
/****************************************************************//**
722
/**********************************************************************//**
718
723
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 */
728
ib_rbt_node_t* node, /*!< in: node to free */
729
ib_rbt_node_t* nil) /*!< in: rb tree nil node */
726
731
if (node != nil) {
727
732
rbt_free_node(node->left, nil);
734
/****************************************************************//**
739
/**********************************************************************//**
735
740
Free all the nodes and free the tree. */
740
ib_rbt_t* tree) /*!< in: rb tree to free */
745
ib_rbt_t* tree) /*!< in: rb tree to free */
742
747
rbt_free_node(tree->root, tree->nil);
743
748
ut_free(tree->nil);
747
/****************************************************************//**
752
/**********************************************************************//**
748
753
Create an instance of a red black tree.
749
754
@return an empty rb tree */
754
size_t sizeof_value, /*!< in: sizeof data item */
755
ib_rbt_compare compare) /*!< in: fn to compare items */
759
size_t sizeof_value, /*!< in: sizeof data item */
760
ib_rbt_compare compare) /*!< in: fn to compare items */
758
763
ib_rbt_node_t* node;
785
/****************************************************************//**
790
/**********************************************************************//**
786
791
Generic insert of a value in the rb tree.
787
792
@return inserted node */
789
794
const ib_rbt_node_t*
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 */
797
ib_rbt_t* tree, /*!< in: rb tree */
798
const void* key, /*!< in: key for ordering */
799
const void* value) /*!< in: value of key, this value
800
is copied to the node */
797
802
ib_rbt_node_t* node;
814
/****************************************************************//**
819
/**********************************************************************//**
815
820
Add a new node to the tree, useful for data that is pre-sorted.
816
821
@return appended node */
818
823
const ib_rbt_node_t*
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
826
ib_rbt_t* tree, /*!< in: rb tree */
827
ib_rbt_bound_t* parent, /*!< in: bounds */
828
const void* value) /*!< in: this value is copied
826
831
ib_rbt_node_t* node;
852
/****************************************************************//**
857
/**********************************************************************//**
853
858
Find a matching node in the rb tree.
854
859
@return NULL if not found else the node where key was found */
856
861
const ib_rbt_node_t*
859
const ib_rbt_t* tree, /*!< in: rb tree */
860
const void* key) /*!< in: key to use for search */
864
const ib_rbt_t* tree, /*!< in: rb tree */
865
const void* key) /*!< in: key to use for search */
862
867
const ib_rbt_node_t* current = ROOT(tree);
877
882
return(current != tree->nil ? current : NULL);
880
/****************************************************************//**
881
Delete a node from the red black tree, identified by key.
885
/**********************************************************************//**
886
Delete a node indentified by key.
882
887
@return TRUE if success FALSE if not found */
887
ib_rbt_t* tree, /*!< in: rb tree */
888
const void* key) /*!< in: key to delete */
892
ib_rbt_t* tree, /*!< in: rb tree */
893
const void* key) /*!< in: key to delete */
890
895
ibool deleted = FALSE;
891
896
ib_rbt_node_t* node = (ib_rbt_node_t*) rbt_lookup(tree, key);
903
/****************************************************************//**
908
/**********************************************************************//**
904
909
Remove a node from the rb tree, the node is not free'd, that is the
905
910
callers responsibility.
906
911
@return deleted node but without the const */
924
929
return((ib_rbt_node_t*) const_node);
927
/****************************************************************//**
932
/**********************************************************************//**
928
933
Find the node that has the lowest key that is >= key.
929
934
@return node satisfying the lower bound constraint or NULL */
931
936
const ib_rbt_node_t*
934
const ib_rbt_t* tree, /*!< in: rb tree */
935
const void* key) /*!< in: key to search */
939
const ib_rbt_t* tree, /*!< in: rb tree */
940
const void* key) /*!< in: key to search */
937
942
ib_rbt_node_t* lb_node = NULL;
938
943
ib_rbt_node_t* current = ROOT(tree);
961
/****************************************************************//**
966
/**********************************************************************//**
962
967
Find the node that has the greatest key that is <= key.
963
968
@return node satisfying the upper bound constraint or NULL */
965
970
const ib_rbt_node_t*
968
const ib_rbt_t* tree, /*!< in: rb tree */
969
const void* key) /*!< in: key to search */
973
const ib_rbt_t* tree, /*!< in: rb tree */
974
const void* key) /*!< in: key to search */
971
976
ib_rbt_node_t* ub_node = NULL;
972
977
ib_rbt_node_t* current = ROOT(tree);
995
/****************************************************************//**
1000
/**********************************************************************//**
996
1001
Find the node that has the greatest key that is <= key.
997
1002
@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 */
1007
const ib_rbt_t* tree, /*!< in: rb tree */
1008
ib_rbt_bound_t* parent, /*!< in: search bounds */
1009
const void* key) /*!< in: key to search */
1006
1011
ib_rbt_node_t* current = ROOT(tree);
1026
1031
return(parent->result);
1029
/****************************************************************//**
1034
/**********************************************************************//**
1030
1035
Find the node that has the greatest key that is <= key. But use the
1031
1036
supplied comparison function.
1032
1037
@return value of result */
1035
1040
rbt_search_cmp(
1036
1041
/*===========*/
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
const ib_rbt_t* tree, /*!< in: rb tree */
1043
ib_rbt_bound_t* parent, /*!< in: search bounds */
1044
const void* key, /*!< in: key to search */
1045
ib_rbt_compare compare) /*!< in: fn to compare items */
1042
1047
ib_rbt_node_t* current = ROOT(tree);
1062
1067
return(parent->result);
1065
/****************************************************************//**
1066
Get the leftmost node.
1070
/**********************************************************************//**
1067
1071
Return the left most node in the tree. */
1069
1073
const ib_rbt_node_t*
1072
const ib_rbt_t* tree) /* in: rb tree */
1076
/* out leftmost node or NULL */
1077
const ib_rbt_t* tree) /* in: rb tree */
1074
1079
ib_rbt_node_t* first = NULL;
1075
1080
ib_rbt_node_t* current = ROOT(tree);
1085
/****************************************************************//**
1090
/**********************************************************************//**
1086
1091
Return the right most node in the tree.
1087
1092
@return the rightmost node or NULL */
1089
1094
const ib_rbt_node_t*
1092
const ib_rbt_t* tree) /*!< in: rb tree */
1097
const ib_rbt_t* tree) /*!< in: rb tree */
1094
1099
ib_rbt_node_t* last = NULL;
1095
1100
ib_rbt_node_t* current = ROOT(tree);
1105
/****************************************************************//**
1110
/**********************************************************************//**
1106
1111
Return the next node.
1107
1112
@return node next from current */
1109
1114
const ib_rbt_node_t*
1112
const ib_rbt_t* tree, /*!< in: rb tree */
1113
const ib_rbt_node_t* current)/*!< in: current node */
1117
const ib_rbt_t* tree, /*!< in: rb tree */
1118
const ib_rbt_node_t* current) /*!< in: current node */
1115
1120
return(current ? rbt_find_successor(tree, current) : NULL);
1118
/****************************************************************//**
1123
/**********************************************************************//**
1119
1124
Return the previous node.
1120
1125
@return node prev from current */
1122
1127
const ib_rbt_node_t*
1125
const ib_rbt_t* tree, /*!< in: rb tree */
1126
const ib_rbt_node_t* current)/*!< in: current node */
1130
const ib_rbt_t* tree, /*!< in: rb tree */
1131
const ib_rbt_node_t* current) /*!< in: current node */
1128
1133
return(current ? rbt_find_predecessor(tree, current) : NULL);
1131
/****************************************************************//**
1136
/**********************************************************************//**
1132
1137
Reset the tree. Delete all the nodes. */
1137
ib_rbt_t* tree) /*!< in: rb tree */
1142
ib_rbt_t* tree) /*!< in: rb tree */
1139
1144
rbt_free_node(ROOT(tree), tree->nil);
1142
1147
tree->root->left = tree->root->right = tree->nil;
1145
/****************************************************************//**
1150
/**********************************************************************//**
1146
1151
Merge the node from dst into src. Return the number of nodes merged.
1147
1152
@return no. of recs merged */
1150
1155
rbt_merge_uniq(
1151
1156
/*===========*/
1152
ib_rbt_t* dst, /*!< in: dst rb tree */
1153
const ib_rbt_t* src) /*!< in: src rb tree */
1157
ib_rbt_t* dst, /*!< in: dst rb tree */
1158
const ib_rbt_t* src) /*!< in: src rb tree */
1155
1160
ib_rbt_bound_t parent;
1156
1161
ulint n_merged = 0;
1171
1176
return(n_merged);
1174
/****************************************************************//**
1179
/**********************************************************************//**
1175
1180
Merge the node from dst into src. Return the number of nodes merged.
1176
1181
Delete the nodes from src after copying node to dst. As a side effect
1177
1182
the duplicates will be left untouched in the src.
1181
1186
rbt_merge_uniq_destructive(
1182
1187
/*=======================*/
1183
ib_rbt_t* dst, /*!< in: dst rb tree */
1184
ib_rbt_t* src) /*!< in: src rb tree */
1188
ib_rbt_t* dst, /*!< in: dst rb tree */
1189
ib_rbt_t* src) /*!< in: src rb tree */
1186
1191
ib_rbt_bound_t parent;
1187
1192
ib_rbt_node_t* src_node;
1219
1224
return(rbt_size(dst) - old_size);
1222
/****************************************************************//**
1227
/**********************************************************************//**
1223
1228
Check that every path from the root to the leaves has the same count and
1224
1229
the tree nodes are in order.
1225
1230
@return TRUE if OK FALSE otherwise */
1239
/****************************************************************//**
1244
/**********************************************************************//**
1240
1245
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 */
1250
const ib_rbt_t* tree, /*!< in: tree to traverse */
1251
ib_rbt_print_node print) /*!< in: print function */
1248
1253
rbt_print_subtree(tree, ROOT(tree), print);
added
removed
plugin/innobase/ut/ut0rbt.c
