« back to all changes in this revision
Viewing changes to plugin/innobase/ut/ut0rbt.c
- browse files at revision 1819.7.68
- compare with another revision
- compare with revision 1992.6.11
- download diff
- download tarball
- view history from revision 1819.7.68
- Committer: Stewart Smith
- Date: 2010-11-11 06:56:57 UTC
- mto: (2021.1.2 build) (1953.1.1 build) (1819.9.64 update-innobase)
- mto: This revision was merged to the branch mainline in revision 1955.
- Revision ID: stewart@flamingspork.com-20101111065657-ndkuvs346txo8ejs
Merge initial InnoDB+ import.
This was applied by generating a patch between MySQL 5.1.50 InnoDB plugin and
the just-merged innodb+ from mysql-trunk revision-id: vasil.dimov@oracle.com-20100422110752-1zowoqxel5xx3z2e
Then, some manual merge resolving and it worked. This should make it much
easier to merge the rest of InnoDB 1.1 and 1.2 from the mysql tree using
my bzr-reapply script.
This takes us to InnoDB 1.1.1(ish).
This was applied by generating a patch between MySQL 5.1.50 InnoDB plugin and
the just-merged innodb+ from mysql-trunk revision-id: vasil.dimov@oracle.com-20100422110752-1zowoqxel5xx3z2e
Then, some manual merge resolving and it worked. This should make it much
easier to merge the rest of InnoDB 1.1 and 1.2 from the mysql tree using
my bzr-reapply script.
This takes us to InnoDB 1.1.1(ish).
- files added:
- plugin/innobase/include/os0file.ic
- files removed:
- plugin/innobase/include/srv0que.h
- files modified:
- plugin/innobase/btr/btr0btr.c
added
removed
plugin/innobase/ut/ut0rbt.c
1
/*****************************************************************************
2
3
Copyright (c) 2006, 2009, Innobase Oy. All Rights Reserved.
1
/***************************************************************************//**
2
3
Copyright (c) 2007, 2010, Innobase Oy. All Rights Reserved.
4
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.
4
10
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
16
22
17
23
*****************************************************************************/
18
19
/*******************************************************************//**
20
@file ut/ut0rbt.c
24
/********************************************************************//**
21
25
Red-Black tree implementation
22
26
27
(c) 2007 Oracle/Innobase Oy
28
23
29
Created 2007-03-20 Sunny Bains
24
30
***********************************************************************/
25
31
26
32
#include "ut0rbt.h"
27
33
28
/************************************************************************
34
/**********************************************************************//**
29
35
Definition of a red-black tree
30
36
==============================
31
37
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.
43
49
44
However, any number of black nodes may appear in a sequence. */
50
However, any number of black nodes may appear in a sequence.
51
*/
45
52
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)
52
59
53
/****************************************************************//**
60
/**********************************************************************//**
54
61
Print out the sub-tree recursively. */
55
62
static
56
63
void
57
64
rbt_print_subtree(
58
65
/*==============*/
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 */
62
69
{
63
70
/* FIXME: Doesn't do anything yet */
64
71
if (node != tree->nil) {
68
75
}
69
76
}
70
77
71
/****************************************************************//**
78
/**********************************************************************//**
72
79
Verify that the keys are in order.
73
80
@return TRUE of OK. FALSE if not ordered */
74
81
static
75
82
ibool
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 */
79
86
{
80
87
const ib_rbt_node_t* node;
81
88
const ib_rbt_node_t* prev = NULL;
93
100
return(TRUE);
94
101
}
95
102
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 */
101
108
ibool
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 */
106
113
{
107
114
ulint result;
108
115
141
148
return(result);
142
149
}
143
150
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. */
147
154
static
148
155
void
149
156
rbt_rotate_left(
150
157
/*============*/
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 */
153
160
{
154
161
ib_rbt_node_t* right = node->right;
155
162
177
184
node->parent = right;
178
185
}
179
186
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. */
183
190
static
184
191
void
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 */
189
196
{
190
197
ib_rbt_node_t* left = node->left;
191
198
213
220
node->parent = left;
214
221
}
215
222
216
/****************************************************************//**
217
Append a node to the tree.
218
@return inserted node */
223
/**********************************************************************//**
224
Append a node to the tree. */
219
225
static
220
226
ib_rbt_node_t*
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,
231
ib_rbt_node_t* node)
226
232
{
227
233
/* Cast away the const. */
228
234
ib_rbt_node_t* last = (ib_rbt_node_t*) parent->last;
241
247
return(node);
242
248
}
243
249
244
/****************************************************************//**
245
Generic binary tree insert
246
@return inserted node */
250
/**********************************************************************//**
251
Generic binary tree insert */
247
252
static
248
253
ib_rbt_node_t*
249
254
rbt_tree_insert(
250
255
/*============*/
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 */
256
ib_rbt_t* tree,
257
const void* key,
258
ib_rbt_node_t* node)
254
259
{
255
260
ib_rbt_bound_t parent;
256
261
ib_rbt_node_t* current = ROOT(tree);
278
283
return(node);
279
284
}
280
285
281
/****************************************************************//**
286
/**********************************************************************//**
282
287
Balance a tree after inserting a node. */
283
288
static
284
289
void
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 */
289
294
{
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;
369
374
}
370
375
371
/****************************************************************//**
376
/**********************************************************************//**
372
377
Find the given node's successor.
373
378
@return successor node or NULL if no successor */
374
379
static
375
380
ib_rbt_node_t*
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
381
rbt_next() */
383
const ib_rbt_t* tree, /*!< in: rb tree */
384
const ib_rbt_node_t* current) /*!< in: this is declared const
385
because it can be called via
386
rbt_next() */
382
387
{
383
388
const ib_rbt_node_t* nil = tree->nil;
384
389
ib_rbt_node_t* next = current->right;
408
413
return(next);
409
414
}
410
415
411
/****************************************************************//**
416
/**********************************************************************//**
412
417
Find the given node's precedecessor.
413
418
@return predecessor node or NULL if no predecesor */
414
419
static
448
453
return(prev);
449
454
}
450
455
451
/****************************************************************//**
456
/**********************************************************************//**
452
457
Replace node with child. After applying transformations eject becomes
453
458
an orphan. */
454
459
static
455
460
void
456
461
rbt_eject_node(
457
462
/*===========*/
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 */
460
465
{
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;
473
478
}
474
479
475
/****************************************************************//**
480
/**********************************************************************//**
476
481
Replace a node with another node. */
477
482
static
478
483
void
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 */
483
488
{
484
489
ib_rbt_color_t color = node->color;
485
490
499
504
replace->color = color;
500
505
}
501
506
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 */
505
510
static
506
511
ib_rbt_node_t*
507
512
rbt_detach_node(
508
513
/*============*/
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 */
511
516
{
512
517
ib_rbt_node_t* child;
513
518
const ib_rbt_node_t* nil = tree->nil;
542
547
return(child);
543
548
}
544
549
545
/****************************************************************//**
550
/**********************************************************************//**
546
551
Rebalance the right sub-tree after deletion.
547
552
@return node to rebalance if more rebalancing required else NULL */
548
553
static
549
554
ib_rbt_node_t*
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 */
555
560
{
556
561
ib_rbt_node_t* node = NULL;
557
562
602
607
return(node);
603
608
}
604
609
605
/****************************************************************//**
610
/**********************************************************************//**
606
611
Rebalance the left sub-tree after deletion.
607
612
@return node to rebalance if more rebalancing required else NULL */
608
613
static
609
614
ib_rbt_node_t*
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 */
615
620
{
616
621
ib_rbt_node_t* node = NULL;
617
622
662
667
return(node);
663
668
}
664
669
665
/****************************************************************//**
670
/**********************************************************************//**
666
671
Delete the node and rebalance the tree if necessary */
667
672
static
668
673
void
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 */
673
678
{
674
679
/* Detach node and get the node that will be used
675
680
as rebalance start. */
714
719
--tree->n_nodes;
715
720
}
716
721
717
/****************************************************************//**
722
/**********************************************************************//**
718
723
Recursively free the nodes. */
719
724
static
720
725
void
721
726
rbt_free_node(
722
727
/*==========*/
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 */
725
730
{
726
731
if (node != nil) {
727
732
rbt_free_node(node->left, nil);
731
736
}
732
737
}
733
738
734
/****************************************************************//**
739
/**********************************************************************//**
735
740
Free all the nodes and free the tree. */
736
741
UNIV_INTERN
737
742
void
738
743
rbt_free(
739
744
/*=====*/
740
ib_rbt_t* tree) /*!< in: rb tree to free */
745
ib_rbt_t* tree) /*!< in: rb tree to free */
741
746
{
742
747
rbt_free_node(tree->root, tree->nil);
743
748
ut_free(tree->nil);
744
749
ut_free(tree);
745
750
}
746
751
747
/****************************************************************//**
752
/**********************************************************************//**
748
753
Create an instance of a red black tree.
749
754
@return an empty rb tree */
750
755
UNIV_INTERN
751
756
ib_rbt_t*
752
757
rbt_create(
753
758
/*=======*/
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 */
756
761
{
757
762
ib_rbt_t* tree;
758
763
ib_rbt_node_t* node;
782
787
return(tree);
783
788
}
784
789
785
/****************************************************************//**
790
/**********************************************************************//**
786
791
Generic insert of a value in the rb tree.
787
792
@return inserted node */
788
793
UNIV_INTERN
789
794
const ib_rbt_node_t*
790
795
rbt_insert(
791
796
/*=======*/
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 */
796
801
{
797
802
ib_rbt_node_t* node;
798
803
811
816
return(node);
812
817
}
813
818
814
/****************************************************************//**
819
/**********************************************************************//**
815
820
Add a new node to the tree, useful for data that is pre-sorted.
816
821
@return appended node */
817
822
UNIV_INTERN
818
823
const ib_rbt_node_t*
819
824
rbt_add_node(
820
825
/*=========*/
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
824
to the node */
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
829
to the node */
825
830
{
826
831
ib_rbt_node_t* node;
827
832
849
854
return(node);
850
855
}
851
856
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 */
855
860
UNIV_INTERN
856
861
const ib_rbt_node_t*
857
862
rbt_lookup(
858
863
/*=======*/
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 */
861
866
{
862
867
const ib_rbt_node_t* current = ROOT(tree);
863
868
877
882
return(current != tree->nil ? current : NULL);
878
883
}
879
884
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 */
883
888
UNIV_INTERN
884
889
ibool
885
890
rbt_delete(
886
891
/*=======*/
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 */
889
894
{
890
895
ibool deleted = FALSE;
891
896
ib_rbt_node_t* node = (ib_rbt_node_t*) rbt_lookup(tree, key);
900
905
return(deleted);
901
906
}
902
907
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);
925
930
}
926
931
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 */
930
935
UNIV_INTERN
931
936
const ib_rbt_node_t*
932
937
rbt_lower_bound(
933
938
/*============*/
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 */
936
941
{
937
942
ib_rbt_node_t* lb_node = NULL;
938
943
ib_rbt_node_t* current = ROOT(tree);
958
963
return(lb_node);
959
964
}
960
965
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 */
964
969
UNIV_INTERN
965
970
const ib_rbt_node_t*
966
971
rbt_upper_bound(
967
972
/*============*/
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 */
970
975
{
971
976
ib_rbt_node_t* ub_node = NULL;
972
977
ib_rbt_node_t* current = ROOT(tree);
992
997
return(ub_node);
993
998
}
994
999
995
/****************************************************************//**
1000
/**********************************************************************//**
996
1001
Find the node that has the greatest key that is <= key.
997
1002
@return value of result */
998
1003
UNIV_INTERN
999
1004
int
1000
1005
rbt_search(
1001
1006
/*=======*/
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 */
1005
1010
{
1006
1011
ib_rbt_node_t* current = ROOT(tree);
1007
1012
1026
1031
return(parent->result);
1027
1032
}
1028
1033
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 */
1034
1039
int
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 */
1041
1046
{
1042
1047
ib_rbt_node_t* current = ROOT(tree);
1043
1048
1062
1067
return(parent->result);
1063
1068
}
1064
1069
1065
/****************************************************************//**
1066
Get the leftmost node.
1070
/**********************************************************************//**
1067
1071
Return the left most node in the tree. */
1068
1072
UNIV_INTERN
1069
1073
const ib_rbt_node_t*
1070
1074
rbt_first(
1071
1075
/*======*/
1072
const ib_rbt_t* tree) /* in: rb tree */
1076
/* out leftmost node or NULL */
1077
const ib_rbt_t* tree) /* in: rb tree */
1073
1078
{
1074
1079
ib_rbt_node_t* first = NULL;
1075
1080
ib_rbt_node_t* current = ROOT(tree);
1082
1087
return(first);
1083
1088
}
1084
1089
1085
/****************************************************************//**
1090
/**********************************************************************//**
1086
1091
Return the right most node in the tree.
1087
1092
@return the rightmost node or NULL */
1088
1093
UNIV_INTERN
1089
1094
const ib_rbt_node_t*
1090
1095
rbt_last(
1091
1096
/*=====*/
1092
const ib_rbt_t* tree) /*!< in: rb tree */
1097
const ib_rbt_t* tree) /*!< in: rb tree */
1093
1098
{
1094
1099
ib_rbt_node_t* last = NULL;
1095
1100
ib_rbt_node_t* current = ROOT(tree);
1102
1107
return(last);
1103
1108
}
1104
1109
1105
/****************************************************************//**
1110
/**********************************************************************//**
1106
1111
Return the next node.
1107
1112
@return node next from current */
1108
1113
UNIV_INTERN
1109
1114
const ib_rbt_node_t*
1110
1115
rbt_next(
1111
1116
/*=====*/
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 */
1114
1119
{
1115
1120
return(current ? rbt_find_successor(tree, current) : NULL);
1116
1121
}
1117
1122
1118
/****************************************************************//**
1123
/**********************************************************************//**
1119
1124
Return the previous node.
1120
1125
@return node prev from current */
1121
1126
UNIV_INTERN
1122
1127
const ib_rbt_node_t*
1123
1128
rbt_prev(
1124
1129
/*=====*/
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 */
1127
1132
{
1128
1133
return(current ? rbt_find_predecessor(tree, current) : NULL);
1129
1134
}
1130
1135
1131
/****************************************************************//**
1136
/**********************************************************************//**
1132
1137
Reset the tree. Delete all the nodes. */
1133
1138
UNIV_INTERN
1134
1139
void
1135
1140
rbt_clear(
1136
1141
/*======*/
1137
ib_rbt_t* tree) /*!< in: rb tree */
1142
ib_rbt_t* tree) /*!< in: rb tree */
1138
1143
{
1139
1144
rbt_free_node(ROOT(tree), tree->nil);
1140
1145
1142
1147
tree->root->left = tree->root->right = tree->nil;
1143
1148
}
1144
1149
1145
/****************************************************************//**
1150
/**********************************************************************//**
1146
1151
Merge the node from dst into src. Return the number of nodes merged.
1147
1152
@return no. of recs merged */
1148
1153
UNIV_INTERN
1149
1154
ulint
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 */
1154
1159
{
1155
1160
ib_rbt_bound_t parent;
1156
1161
ulint n_merged = 0;
1171
1176
return(n_merged);
1172
1177
}
1173
1178
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.
1180
1185
ulint
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 */
1185
1190
{
1186
1191
ib_rbt_bound_t parent;
1187
1192
ib_rbt_node_t* src_node;
1219
1224
return(rbt_size(dst) - old_size);
1220
1225
}
1221
1226
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 */
1236
1241
return(FALSE);
1237
1242
}
1238
1243
1239
/****************************************************************//**
1244
/**********************************************************************//**
1240
1245
Iterate over the tree in depth first order. */
1241
1246
UNIV_INTERN
1242
1247
void
1243
1248
rbt_print(
1244
1249
/*======*/
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 */
1247
1252
{
1248
1253
rbt_print_subtree(tree, ROOT(tree), print);
1249
1254
}
Loggerhead is a web-based interface for Breezy
Version: 2.0.1