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