~drizzle-trunk/drizzle/development
» Revision
1819.5.236
(compared to revision 1819.5.262)
: plugin/innobase/ut/ut0rbt.c
« back to all changes in this revision
Viewing changes to plugin/innobase/ut/ut0rbt.c
- browse files at revision 1819.5.236
- compare with another revision
- download diff
- download tarball
- view history from revision 1819.5.236
- Committer: Stewart Smith
- Author(s): jyang
- Date: 2010-10-15 05:07:31 UTC
- mto: (2021.1.2 build) (1953.1.1 build) (1819.7.43 update-innobase)
- mto: This revision was merged to the branch mainline in revision 1924.
- Revision ID: stewart@flamingspork.com-20101015050731-9zdsfcq6anyi1zyj
Merge Revision revid:svn-v4:16c675df-0fcb-4bc9-8058-dcc011a37293:branches/zip:6790 from MySQL InnoDB
Original revid:svn-v4:16c675df-0fcb-4bc9-8058-dcc011a37293:branches/zip:6790
Original Authors: jyang
Original commit message:
branches/zip: Fix bug #51356: "many valgrind errors in error messages
with concurrent ddl". Null terminate the name string returned
from innobase_convert_identifier() call when reporting DB_DUPLICATE_KEY
error in create_table_def().
rb://266 approved by Marko
Original revid:svn-v4:16c675df-0fcb-4bc9-8058-dcc011a37293:branches/zip:6790
Original Authors: jyang
Original commit message:
branches/zip: Fix bug #51356: "many valgrind errors in error messages
with concurrent ddl". Null terminate the name string returned
from innobase_convert_identifier() call when reporting DB_DUPLICATE_KEY
error in create_table_def().
rb://266 approved by Marko
- files removed:
- plugin/innobase/include/ut0rbt.h
- files modified:
- plugin/innobase/CMakeLists.txt
added
removed
plugin/innobase/ut/ut0rbt.c
1
/*****************************************************************************
2
3
Copyright (c) 2006, 2009, Innobase Oy. All Rights Reserved.
4
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.
8
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.
12
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
16
17
*****************************************************************************/
18
19
/*******************************************************************//**
20
@file ut/ut0rbt.c
21
Red-Black tree implementation
22
23
Created 2007-03-20 Sunny Bains
24
***********************************************************************/
25
26
#include "ut0rbt.h"
27
28
/************************************************************************
29
Definition of a red-black tree
30
==============================
31
32
A red-black tree is a binary search tree which has the following
33
red-black properties:
34
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.
40
41
from (3) above, the implication is that on any path from the root
42
to a leaf, red nodes must not be adjacent.
43
44
However, any number of black nodes may appear in a sequence. */
45
46
#if defined(IB_RBT_TESTING)
47
#warning "Testing enabled!"
48
#endif
49
50
#define ROOT(t) (t->root->left)
51
#define SIZEOF_NODE(t) ((sizeof(ib_rbt_node_t) + t->sizeof_value) - 1)
52
53
/****************************************************************//**
54
Print out the sub-tree recursively. */
55
static
56
void
57
rbt_print_subtree(
58
/*==============*/
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 */
62
{
63
/* FIXME: Doesn't do anything yet */
64
if (node != tree->nil) {
65
print(node);
66
rbt_print_subtree(tree, node->left, print);
67
rbt_print_subtree(tree, node->right, print);
68
}
69
}
70
71
/****************************************************************//**
72
Verify that the keys are in order.
73
@return TRUE of OK. FALSE if not ordered */
74
static
75
ibool
76
rbt_check_ordering(
77
/*===============*/
78
const ib_rbt_t* tree) /*!< in: tree to verfify */
79
{
80
const ib_rbt_node_t* node;
81
const ib_rbt_node_t* prev = NULL;
82
83
/* Iterate over all the nodes, comparing each node with the prev */
84
for (node = rbt_first(tree); node; node = rbt_next(tree, prev)) {
85
86
if (prev && tree->compare(prev->value, node->value) >= 0) {
87
return(FALSE);
88
}
89
90
prev = node;
91
}
92
93
return(TRUE);
94
}
95
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 */
100
static
101
ibool
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 */
106
{
107
ulint result;
108
109
if (node != tree->nil) {
110
ulint left_height = rbt_count_black_nodes(tree, node->left);
111
112
ulint right_height = rbt_count_black_nodes(tree, node->right);
113
114
if (left_height == 0
115
|| right_height == 0
116
|| left_height != right_height) {
117
118
result = 0;
119
} else if (node->color == IB_RBT_RED) {
120
121
/* Case 3 */
122
if (node->left->color != IB_RBT_BLACK
123
|| node->right->color != IB_RBT_BLACK) {
124
125
result = 0;
126
} else {
127
result = left_height;
128
}
129
/* Check if it's anything other than RED or BLACK. */
130
} else if (node->color != IB_RBT_BLACK) {
131
132
result = 0;
133
} else {
134
135
result = right_height + 1;
136
}
137
} else {
138
result = 1;
139
}
140
141
return(result);
142
}
143
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. */
147
static
148
void
149
rbt_rotate_left(
150
/*============*/
151
const ib_rbt_node_t* nil, /*!< in: nil node of the tree */
152
ib_rbt_node_t* node) /*!< in: node to rotate */
153
{
154
ib_rbt_node_t* right = node->right;
155
156
node->right = right->left;
157
158
if (right->left != nil) {
159
right->left->parent = node;
160
}
161
162
/* Right's new parent was node's parent. */
163
right->parent = node->parent;
164
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;
170
} else {
171
/* Node must have been on the right. */
172
node->parent->right = right;
173
}
174
175
/* Finally, put node on right's left. */
176
right->left = node;
177
node->parent = right;
178
}
179
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. */
183
static
184
void
185
rbt_rotate_right(
186
/*=============*/
187
const ib_rbt_node_t* nil, /*!< in: nil node of tree */
188
ib_rbt_node_t* node) /*!< in: node to rotate */
189
{
190
ib_rbt_node_t* left = node->left;
191
192
node->left = left->right;
193
194
if (left->right != nil) {
195
left->right->parent = node;
196
}
197
198
/* Left's new parent was node's parent. */
199
left->parent = node->parent;
200
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;
206
} else {
207
/* Node must have been on the left. */
208
node->parent->left = left;
209
}
210
211
/* Finally, put node on left's right. */
212
left->right = node;
213
node->parent = left;
214
}
215
216
/****************************************************************//**
217
Append a node to the tree.
218
@return inserted node */
219
static
220
ib_rbt_node_t*
221
rbt_tree_add_child(
222
/*===============*/
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 */
226
{
227
/* Cast away the const. */
228
ib_rbt_node_t* last = (ib_rbt_node_t*) parent->last;
229
230
if (last == tree->root || parent->result < 0) {
231
last->left = node;
232
} else {
233
/* FIXME: We don't handle duplicates (yet)! */
234
ut_a(parent->result != 0);
235
236
last->right = node;
237
}
238
239
node->parent = last;
240
241
return(node);
242
}
243
244
/****************************************************************//**
245
Generic binary tree insert
246
@return inserted node */
247
static
248
ib_rbt_node_t*
249
rbt_tree_insert(
250
/*============*/
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 */
254
{
255
ib_rbt_bound_t parent;
256
ib_rbt_node_t* current = ROOT(tree);
257
258
parent.result = 0;
259
parent.last = tree->root;
260
261
/* Regular binary search. */
262
while (current != tree->nil) {
263
264
parent.last = current;
265
parent.result = tree->compare(key, current->value);
266
267
if (parent.result < 0) {
268
current = current->left;
269
} else {
270
current = current->right;
271
}
272
}
273
274
ut_a(current == tree->nil);
275
276
rbt_tree_add_child(tree, &parent, node);
277
278
return(node);
279
}
280
281
/****************************************************************//**
282
Balance a tree after inserting a node. */
283
static
284
void
285
rbt_balance_tree(
286
/*=============*/
287
const ib_rbt_t* tree, /*!< in: tree to balance */
288
ib_rbt_node_t* node) /*!< in: node that was inserted */
289
{
290
const ib_rbt_node_t* nil = tree->nil;
291
ib_rbt_node_t* parent = node->parent;
292
293
/* Restore the red-black property. */
294
node->color = IB_RBT_RED;
295
296
while (node != ROOT(tree) && parent->color == IB_RBT_RED) {
297
ib_rbt_node_t* grand_parent = parent->parent;
298
299
if (parent == grand_parent->left) {
300
ib_rbt_node_t* uncle = grand_parent->right;
301
302
if (uncle->color == IB_RBT_RED) {
303
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;
308
309
/* Move node up the tree. */
310
node = grand_parent;
311
312
} else {
313
314
if (node == parent->right) {
315
/* Right is a black node and node is
316
to the right, case 2 - move node
317
up and rotate. */
318
node = parent;
319
rbt_rotate_left(nil, node);
320
}
321
322
grand_parent = node->parent->parent;
323
324
/* Case 3. */
325
node->parent->color = IB_RBT_BLACK;
326
grand_parent->color = IB_RBT_RED;
327
328
rbt_rotate_right(nil, grand_parent);
329
}
330
331
} else {
332
ib_rbt_node_t* uncle = grand_parent->left;
333
334
if (uncle->color == IB_RBT_RED) {
335
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;
340
341
/* Move node up the tree. */
342
node = grand_parent;
343
344
} else {
345
346
if (node == parent->left) {
347
/* Left is a black node and node is to
348
the right, case 2 - move node up and
349
rotate. */
350
node = parent;
351
rbt_rotate_right(nil, node);
352
}
353
354
grand_parent = node->parent->parent;
355
356
/* Case 3. */
357
node->parent->color = IB_RBT_BLACK;
358
grand_parent->color = IB_RBT_RED;
359
360
rbt_rotate_left(nil, grand_parent);
361
}
362
}
363
364
parent = node->parent;
365
}
366
367
/* Color the root black. */
368
ROOT(tree)->color = IB_RBT_BLACK;
369
}
370
371
/****************************************************************//**
372
Find the given node's successor.
373
@return successor node or NULL if no successor */
374
static
375
ib_rbt_node_t*
376
rbt_find_successor(
377
/*===============*/
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() */
382
{
383
const ib_rbt_node_t* nil = tree->nil;
384
ib_rbt_node_t* next = current->right;
385
386
/* Is there a sub-tree to the right that we can follow. */
387
if (next != nil) {
388
389
/* Follow the left most links of the current right child. */
390
while (next->left != nil) {
391
next = next->left;
392
}
393
394
} else { /* We will have to go up the tree to find the successor. */
395
ib_rbt_node_t* parent = current->parent;
396
397
/* Cast away the const. */
398
next = (ib_rbt_node_t*) current;
399
400
while (parent != tree->root && next == parent->right) {
401
next = parent;
402
parent = next->parent;
403
}
404
405
next = (parent == tree->root) ? NULL : parent;
406
}
407
408
return(next);
409
}
410
411
/****************************************************************//**
412
Find the given node's precedecessor.
413
@return predecessor node or NULL if no predecesor */
414
static
415
ib_rbt_node_t*
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
421
rbt_prev() */
422
{
423
const ib_rbt_node_t* nil = tree->nil;
424
ib_rbt_node_t* prev = current->left;
425
426
/* Is there a sub-tree to the left that we can follow. */
427
if (prev != nil) {
428
429
/* Follow the right most links of the current left child. */
430
while (prev->right != nil) {
431
prev = prev->right;
432
}
433
434
} else { /* We will have to go up the tree to find the precedecessor. */
435
ib_rbt_node_t* parent = current->parent;
436
437
/* Cast away the const. */
438
prev = (ib_rbt_node_t*)current;
439
440
while (parent != tree->root && prev == parent->left) {
441
prev = parent;
442
parent = prev->parent;
443
}
444
445
prev = (parent == tree->root) ? NULL : parent;
446
}
447
448
return(prev);
449
}
450
451
/****************************************************************//**
452
Replace node with child. After applying transformations eject becomes
453
an orphan. */
454
static
455
void
456
rbt_eject_node(
457
/*===========*/
458
ib_rbt_node_t* eject, /*!< in: node to eject */
459
ib_rbt_node_t* node) /*!< in: node to replace with */
460
{
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;
466
} else {
467
ut_a(0);
468
}
469
/* eject is now an orphan but otherwise its pointers
470
and color are left intact. */
471
472
node->parent = eject->parent;
473
}
474
475
/****************************************************************//**
476
Replace a node with another node. */
477
static
478
void
479
rbt_replace_node(
480
/*=============*/
481
ib_rbt_node_t* replace, /*!< in: node to replace */
482
ib_rbt_node_t* node) /*!< in: node to replace with */
483
{
484
ib_rbt_color_t color = node->color;
485
486
/* Update the node pointers. */
487
node->left = replace->left;
488
node->right = replace->right;
489
490
/* Update the child node pointers. */
491
node->left->parent = node;
492
node->right->parent = node;
493
494
/* Make the parent of replace point to node. */
495
rbt_eject_node(replace, node);
496
497
/* Swap the colors. */
498
node->color = replace->color;
499
replace->color = color;
500
}
501
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 */
505
static
506
ib_rbt_node_t*
507
rbt_detach_node(
508
/*============*/
509
const ib_rbt_t* tree, /*!< in: rb tree */
510
ib_rbt_node_t* node) /*!< in: node to detach */
511
{
512
ib_rbt_node_t* child;
513
const ib_rbt_node_t* nil = tree->nil;
514
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);
518
519
ut_a(successor != nil);
520
ut_a(successor->parent != nil);
521
ut_a(successor->left == nil);
522
523
child = successor->right;
524
525
/* Remove the successor node and replace with its child. */
526
rbt_eject_node(successor, child);
527
528
/* Replace the node to delete with its successor node. */
529
rbt_replace_node(node, successor);
530
} else {
531
ut_a(node->left == nil || node->right == nil);
532
533
child = (node->left != nil) ? node->left : node->right;
534
535
/* Replace the node to delete with one of it's children. */
536
rbt_eject_node(node, child);
537
}
538
539
/* Reset the node links. */
540
node->parent = node->right = node->left = tree->nil;
541
542
return(child);
543
}
544
545
/****************************************************************//**
546
Rebalance the right sub-tree after deletion.
547
@return node to rebalance if more rebalancing required else NULL */
548
static
549
ib_rbt_node_t*
550
rbt_balance_right(
551
/*==============*/
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 */
555
{
556
ib_rbt_node_t* node = NULL;
557
558
ut_a(sibling != nil);
559
560
/* Case 3. */
561
if (sibling->color == IB_RBT_RED) {
562
563
parent->color = IB_RBT_RED;
564
sibling->color = IB_RBT_BLACK;
565
566
rbt_rotate_left(nil, parent);
567
568
sibling = parent->right;
569
570
ut_a(sibling != nil);
571
}
572
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) {
576
577
node = parent; /* Parent needs to be rebalanced too. */
578
sibling->color = IB_RBT_RED;
579
580
} else {
581
if (sibling->right->color == IB_RBT_BLACK) {
582
583
ut_a(sibling->left->color == IB_RBT_RED);
584
585
sibling->color = IB_RBT_RED;
586
sibling->left->color = IB_RBT_BLACK;
587
588
rbt_rotate_right(nil, sibling);
589
590
sibling = parent->right;
591
ut_a(sibling != nil);
592
}
593
594
sibling->color = parent->color;
595
sibling->right->color = IB_RBT_BLACK;
596
597
parent->color = IB_RBT_BLACK;
598
599
rbt_rotate_left(nil, parent);
600
}
601
602
return(node);
603
}
604
605
/****************************************************************//**
606
Rebalance the left sub-tree after deletion.
607
@return node to rebalance if more rebalancing required else NULL */
608
static
609
ib_rbt_node_t*
610
rbt_balance_left(
611
/*=============*/
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 */
615
{
616
ib_rbt_node_t* node = NULL;
617
618
ut_a(sibling != nil);
619
620
/* Case 3. */
621
if (sibling->color == IB_RBT_RED) {
622
623
parent->color = IB_RBT_RED;
624
sibling->color = IB_RBT_BLACK;
625
626
rbt_rotate_right(nil, parent);
627
sibling = parent->left;
628
629
ut_a(sibling != nil);
630
}
631
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) {
635
636
node = parent; /* Parent needs to be rebalanced too. */
637
sibling->color = IB_RBT_RED;
638
639
} else {
640
if (sibling->left->color == IB_RBT_BLACK) {
641
642
ut_a(sibling->right->color == IB_RBT_RED);
643
644
sibling->color = IB_RBT_RED;
645
sibling->right->color = IB_RBT_BLACK;
646
647
rbt_rotate_left(nil, sibling);
648
649
sibling = parent->left;
650
651
ut_a(sibling != nil);
652
}
653
654
sibling->color = parent->color;
655
sibling->left->color = IB_RBT_BLACK;
656
657
parent->color = IB_RBT_BLACK;
658
659
rbt_rotate_right(nil, parent);
660
}
661
662
return(node);
663
}
664
665
/****************************************************************//**
666
Delete the node and rebalance the tree if necessary */
667
static
668
void
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 */
673
{
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);
677
678
if (node->color == IB_RBT_BLACK) {
679
ib_rbt_node_t* last = child;
680
681
ROOT(tree)->color = IB_RBT_RED;
682
683
while (child && child->color == IB_RBT_BLACK) {
684
ib_rbt_node_t* parent = child->parent;
685
686
/* Did the deletion cause an imbalance in the
687
parents left sub-tree. */
688
if (parent->left == child) {
689
690
child = rbt_balance_right(
691
tree->nil, parent, parent->right);
692
693
} else if (parent->right == child) {
694
695
child = rbt_balance_left(
696
tree->nil, parent, parent->left);
697
698
} else {
699
ut_error;
700
}
701
702
if (child) {
703
last = child;
704
}
705
}
706
707
ut_a(last);
708
709
last->color = IB_RBT_BLACK;
710
ROOT(tree)->color = IB_RBT_BLACK;
711
}
712
713
/* Note that we have removed a node from the tree. */
714
--tree->n_nodes;
715
}
716
717
/****************************************************************//**
718
Recursively free the nodes. */
719
static
720
void
721
rbt_free_node(
722
/*==========*/
723
ib_rbt_node_t* node, /*!< in: node to free */
724
ib_rbt_node_t* nil) /*!< in: rb tree nil node */
725
{
726
if (node != nil) {
727
rbt_free_node(node->left, nil);
728
rbt_free_node(node->right, nil);
729
730
ut_free(node);
731
}
732
}
733
734
/****************************************************************//**
735
Free all the nodes and free the tree. */
736
UNIV_INTERN
737
void
738
rbt_free(
739
/*=====*/
740
ib_rbt_t* tree) /*!< in: rb tree to free */
741
{
742
rbt_free_node(tree->root, tree->nil);
743
ut_free(tree->nil);
744
ut_free(tree);
745
}
746
747
/****************************************************************//**
748
Create an instance of a red black tree.
749
@return an empty rb tree */
750
UNIV_INTERN
751
ib_rbt_t*
752
rbt_create(
753
/*=======*/
754
size_t sizeof_value, /*!< in: sizeof data item */
755
ib_rbt_compare compare) /*!< in: fn to compare items */
756
{
757
ib_rbt_t* tree;
758
ib_rbt_node_t* node;
759
760
tree = (ib_rbt_t*) ut_malloc(sizeof(*tree));
761
memset(tree, 0, sizeof(*tree));
762
763
tree->sizeof_value = sizeof_value;
764
765
/* Create the sentinel (NIL) node. */
766
node = tree->nil = (ib_rbt_node_t*) ut_malloc(sizeof(*node));
767
memset(node, 0, sizeof(*node));
768
769
node->color = IB_RBT_BLACK;
770
node->parent = node->left = node->right = node;
771
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));
776
777
node->color = IB_RBT_BLACK;
778
node->parent = node->left = node->right = tree->nil;
779
780
tree->compare = compare;
781
782
return(tree);
783
}
784
785
/****************************************************************//**
786
Generic insert of a value in the rb tree.
787
@return inserted node */
788
UNIV_INTERN
789
const ib_rbt_node_t*
790
rbt_insert(
791
/*=======*/
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 */
796
{
797
ib_rbt_node_t* node;
798
799
/* Create the node that will hold the value data. */
800
node = (ib_rbt_node_t*) ut_malloc(SIZEOF_NODE(tree));
801
802
memcpy(node->value, value, tree->sizeof_value);
803
node->parent = node->left = node->right = tree->nil;
804
805
/* Insert in the tree in the usual way. */
806
rbt_tree_insert(tree, key, node);
807
rbt_balance_tree(tree, node);
808
809
++tree->n_nodes;
810
811
return(node);
812
}
813
814
/****************************************************************//**
815
Add a new node to the tree, useful for data that is pre-sorted.
816
@return appended node */
817
UNIV_INTERN
818
const ib_rbt_node_t*
819
rbt_add_node(
820
/*=========*/
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 */
825
{
826
ib_rbt_node_t* node;
827
828
/* Create the node that will hold the value data */
829
node = (ib_rbt_node_t*) ut_malloc(SIZEOF_NODE(tree));
830
831
memcpy(node->value, value, tree->sizeof_value);
832
node->parent = node->left = node->right = tree->nil;
833
834
/* If tree is empty */
835
if (parent->last == NULL) {
836
parent->last = tree->root;
837
}
838
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);
843
844
++tree->n_nodes;
845
846
#if defined(IB_RBT_TESTING)
847
ut_a(rbt_validate(tree));
848
#endif
849
return(node);
850
}
851
852
/****************************************************************//**
853
Find a matching node in the rb tree.
854
@return NULL if not found else the node where key was found */
855
UNIV_INTERN
856
const ib_rbt_node_t*
857
rbt_lookup(
858
/*=======*/
859
const ib_rbt_t* tree, /*!< in: rb tree */
860
const void* key) /*!< in: key to use for search */
861
{
862
const ib_rbt_node_t* current = ROOT(tree);
863
864
/* Regular binary search. */
865
while (current != tree->nil) {
866
int result = tree->compare(key, current->value);
867
868
if (result < 0) {
869
current = current->left;
870
} else if (result > 0) {
871
current = current->right;
872
} else {
873
break;
874
}
875
}
876
877
return(current != tree->nil ? current : NULL);
878
}
879
880
/****************************************************************//**
881
Delete a node from the red black tree, identified by key.
882
@return TRUE if success FALSE if not found */
883
UNIV_INTERN
884
ibool
885
rbt_delete(
886
/*=======*/
887
ib_rbt_t* tree, /*!< in: rb tree */
888
const void* key) /*!< in: key to delete */
889
{
890
ibool deleted = FALSE;
891
ib_rbt_node_t* node = (ib_rbt_node_t*) rbt_lookup(tree, key);
892
893
if (node) {
894
rbt_remove_node_and_rebalance(tree, node);
895
896
ut_free(node);
897
deleted = TRUE;
898
}
899
900
return(deleted);
901
}
902
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 */
907
UNIV_INTERN
908
ib_rbt_node_t*
909
rbt_remove_node(
910
/*============*/
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
915
only const nodes */
916
{
917
/* Cast away the const. */
918
rbt_remove_node_and_rebalance(tree, (ib_rbt_node_t*) const_node);
919
920
/* This is to make it easier to do something like this:
921
ut_free(rbt_remove_node(node));
922
*/
923
924
return((ib_rbt_node_t*) const_node);
925
}
926
927
/****************************************************************//**
928
Find the node that has the lowest key that is >= key.
929
@return node satisfying the lower bound constraint or NULL */
930
UNIV_INTERN
931
const ib_rbt_node_t*
932
rbt_lower_bound(
933
/*============*/
934
const ib_rbt_t* tree, /*!< in: rb tree */
935
const void* key) /*!< in: key to search */
936
{
937
ib_rbt_node_t* lb_node = NULL;
938
ib_rbt_node_t* current = ROOT(tree);
939
940
while (current != tree->nil) {
941
int result = tree->compare(key, current->value);
942
943
if (result > 0) {
944
945
current = current->right;
946
947
} else if (result < 0) {
948
949
lb_node = current;
950
current = current->left;
951
952
} else {
953
lb_node = current;
954
break;
955
}
956
}
957
958
return(lb_node);
959
}
960
961
/****************************************************************//**
962
Find the node that has the greatest key that is <= key.
963
@return node satisfying the upper bound constraint or NULL */
964
UNIV_INTERN
965
const ib_rbt_node_t*
966
rbt_upper_bound(
967
/*============*/
968
const ib_rbt_t* tree, /*!< in: rb tree */
969
const void* key) /*!< in: key to search */
970
{
971
ib_rbt_node_t* ub_node = NULL;
972
ib_rbt_node_t* current = ROOT(tree);
973
974
while (current != tree->nil) {
975
int result = tree->compare(key, current->value);
976
977
if (result > 0) {
978
979
ub_node = current;
980
current = current->right;
981
982
} else if (result < 0) {
983
984
current = current->left;
985
986
} else {
987
ub_node = current;
988
break;
989
}
990
}
991
992
return(ub_node);
993
}
994
995
/****************************************************************//**
996
Find the node that has the greatest key that is <= key.
997
@return value of result */
998
UNIV_INTERN
999
int
1000
rbt_search(
1001
/*=======*/
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 */
1005
{
1006
ib_rbt_node_t* current = ROOT(tree);
1007
1008
/* Every thing is greater than the NULL root. */
1009
parent->result = 1;
1010
parent->last = NULL;
1011
1012
while (current != tree->nil) {
1013
1014
parent->last = current;
1015
parent->result = tree->compare(key, current->value);
1016
1017
if (parent->result > 0) {
1018
current = current->right;
1019
} else if (parent->result < 0) {
1020
current = current->left;
1021
} else {
1022
break;
1023
}
1024
}
1025
1026
return(parent->result);
1027
}
1028
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 */
1033
UNIV_INTERN
1034
int
1035
rbt_search_cmp(
1036
/*===========*/
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 */
1041
{
1042
ib_rbt_node_t* current = ROOT(tree);
1043
1044
/* Every thing is greater than the NULL root. */
1045
parent->result = 1;
1046
parent->last = NULL;
1047
1048
while (current != tree->nil) {
1049
1050
parent->last = current;
1051
parent->result = compare(key, current->value);
1052
1053
if (parent->result > 0) {
1054
current = current->right;
1055
} else if (parent->result < 0) {
1056
current = current->left;
1057
} else {
1058
break;
1059
}
1060
}
1061
1062
return(parent->result);
1063
}
1064
1065
/****************************************************************//**
1066
Get the leftmost node.
1067
Return the left most node in the tree. */
1068
UNIV_INTERN
1069
const ib_rbt_node_t*
1070
rbt_first(
1071
/*======*/
1072
const ib_rbt_t* tree) /* in: rb tree */
1073
{
1074
ib_rbt_node_t* first = NULL;
1075
ib_rbt_node_t* current = ROOT(tree);
1076
1077
while (current != tree->nil) {
1078
first = current;
1079
current = current->left;
1080
}
1081
1082
return(first);
1083
}
1084
1085
/****************************************************************//**
1086
Return the right most node in the tree.
1087
@return the rightmost node or NULL */
1088
UNIV_INTERN
1089
const ib_rbt_node_t*
1090
rbt_last(
1091
/*=====*/
1092
const ib_rbt_t* tree) /*!< in: rb tree */
1093
{
1094
ib_rbt_node_t* last = NULL;
1095
ib_rbt_node_t* current = ROOT(tree);
1096
1097
while (current != tree->nil) {
1098
last = current;
1099
current = current->right;
1100
}
1101
1102
return(last);
1103
}
1104
1105
/****************************************************************//**
1106
Return the next node.
1107
@return node next from current */
1108
UNIV_INTERN
1109
const ib_rbt_node_t*
1110
rbt_next(
1111
/*=====*/
1112
const ib_rbt_t* tree, /*!< in: rb tree */
1113
const ib_rbt_node_t* current)/*!< in: current node */
1114
{
1115
return(current ? rbt_find_successor(tree, current) : NULL);
1116
}
1117
1118
/****************************************************************//**
1119
Return the previous node.
1120
@return node prev from current */
1121
UNIV_INTERN
1122
const ib_rbt_node_t*
1123
rbt_prev(
1124
/*=====*/
1125
const ib_rbt_t* tree, /*!< in: rb tree */
1126
const ib_rbt_node_t* current)/*!< in: current node */
1127
{
1128
return(current ? rbt_find_predecessor(tree, current) : NULL);
1129
}
1130
1131
/****************************************************************//**
1132
Reset the tree. Delete all the nodes. */
1133
UNIV_INTERN
1134
void
1135
rbt_clear(
1136
/*======*/
1137
ib_rbt_t* tree) /*!< in: rb tree */
1138
{
1139
rbt_free_node(ROOT(tree), tree->nil);
1140
1141
tree->n_nodes = 0;
1142
tree->root->left = tree->root->right = tree->nil;
1143
}
1144
1145
/****************************************************************//**
1146
Merge the node from dst into src. Return the number of nodes merged.
1147
@return no. of recs merged */
1148
UNIV_INTERN
1149
ulint
1150
rbt_merge_uniq(
1151
/*===========*/
1152
ib_rbt_t* dst, /*!< in: dst rb tree */
1153
const ib_rbt_t* src) /*!< in: src rb tree */
1154
{
1155
ib_rbt_bound_t parent;
1156
ulint n_merged = 0;
1157
const ib_rbt_node_t* src_node = rbt_first(src);
1158
1159
if (rbt_empty(src) || dst == src) {
1160
return(0);
1161
}
1162
1163
for (/* No op */; src_node; src_node = rbt_next(src, src_node)) {
1164
1165
if (rbt_search(dst, &parent, src_node->value) != 0) {
1166
rbt_add_node(dst, &parent, src_node->value);
1167
++n_merged;
1168
}
1169
}
1170
1171
return(n_merged);
1172
}
1173
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 */
1179
UNIV_INTERN
1180
ulint
1181
rbt_merge_uniq_destructive(
1182
/*=======================*/
1183
ib_rbt_t* dst, /*!< in: dst rb tree */
1184
ib_rbt_t* src) /*!< in: src rb tree */
1185
{
1186
ib_rbt_bound_t parent;
1187
ib_rbt_node_t* src_node;
1188
ulint old_size = rbt_size(dst);
1189
1190
if (rbt_empty(src) || dst == src) {
1191
return(0);
1192
}
1193
1194
for (src_node = (ib_rbt_node_t*) rbt_first(src); src_node; /* */) {
1195
ib_rbt_node_t* prev = src_node;
1196
1197
src_node = (ib_rbt_node_t*)rbt_next(src, prev);
1198
1199
/* Skip duplicates. */
1200
if (rbt_search(dst, &parent, prev->value) != 0) {
1201
1202
/* Remove and reset the node but preserve
1203
the node (data) value. */
1204
rbt_remove_node_and_rebalance(src, prev);
1205
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);
1210
1211
++dst->n_nodes;
1212
}
1213
}
1214
1215
#if defined(IB_RBT_TESTING)
1216
ut_a(rbt_validate(dst));
1217
ut_a(rbt_validate(src));
1218
#endif
1219
return(rbt_size(dst) - old_size);
1220
}
1221
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 */
1226
UNIV_INTERN
1227
ibool
1228
rbt_validate(
1229
/*=========*/
1230
const ib_rbt_t* tree) /*!< in: RB tree to validate */
1231
{
1232
if (rbt_count_black_nodes(tree, ROOT(tree)) > 0) {
1233
return(rbt_check_ordering(tree));
1234
}
1235
1236
return(FALSE);
1237
}
1238
1239
/****************************************************************//**
1240
Iterate over the tree in depth first order. */
1241
UNIV_INTERN
1242
void
1243
rbt_print(
1244
/*======*/
1245
const ib_rbt_t* tree, /*!< in: tree to traverse */
1246
ib_rbt_print_node print) /*!< in: print function */
1247
{
1248
rbt_print_subtree(tree, ROOT(tree), print);
1249
}
Loggerhead is a web-based interface for Breezy
Version: 2.0.1