← Back to branch summary

~drizzle-trunk/drizzle/development

« back to all changes in this revision

Viewing changes to plugin/innobase/ut/ut0rbt.cc

  • Committer: Monty Taylor
  • Date: 2008-09-16 00:00:48 UTC
  • mto: This revision was merged to the branch mainline in revision 391.
  • Revision ID: monty@inaugust.com-20080916000048-3rvrv3gv9l0ad3gs
Fixed copyright headers in drizzled/

Show diffs side-by-side

added added

removed removed

Lines of Context:
plugin/innobase/ut/ut0rbt.cc
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.
10
 
 
11
 
This program is free software; you can redistribute it and/or modify it under
12
 
the terms of the GNU General Public License as published by the Free Software
13
 
Foundation; version 2 of the License.
14
 
 
15
 
This program is distributed in the hope that it will be useful, but WITHOUT
16
 
ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
17
 
FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
18
 
 
19
 
You should have received a copy of the GNU General Public License along with
20
 
this program; if not, write to the Free Software Foundation, Inc., 59 Temple
21
 
Place, Suite 330, Boston, MA 02111-1307 USA
22
 
 
23
 
*****************************************************************************/
24
 
/********************************************************************//**
25
 
Red-Black tree implementation
26
 
 
27
 
(c) 2007 Oracle/Innobase Oy
28
 
 
29
 
Created 2007-03-20 Sunny Bains
30
 
***********************************************************************/
31
 
 
32
 
#include "ut0rbt.h"
33
 
 
34
 
/**********************************************************************//**
35
 
Definition of a red-black tree
36
 
==============================
37
 
 
38
 
A red-black tree is a binary search tree which has the following
39
 
red-black properties:
40
 
 
41
 
   1. Every node is either red or black.
42
 
   2. Every leaf (NULL - in our case tree->nil) is black.
43
 
   3. If a node is red, then both its children are black.
44
 
   4. Every simple path from a node to a descendant leaf contains the
45
 
      same number of black nodes.
46
 
 
47
 
   from (3) above, the implication is that on any path from the root
48
 
   to a leaf, red nodes must not be adjacent.
49
 
 
50
 
   However, any number of black nodes may appear in a sequence.
51
 
 */
52
 
 
53
 
#if     defined(IB_RBT_TESTING)
54
 
#warning "Testing enabled!"
55
 
#endif
56
 
 
57
 
#define ROOT(t)         (t->root->left)
58
 
#define SIZEOF_NODE(t)  ((sizeof(ib_rbt_node_t) + t->sizeof_value) - 1)
59
 
 
60
 
/**********************************************************************//**
61
 
Print out the sub-tree recursively. */
62
 
static
63
 
void
64
 
rbt_print_subtree(
65
 
/*==============*/
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 */
69
 
{
70
 
        /* FIXME: Doesn't do anything yet */
71
 
        if (node != tree->nil) {
72
 
                print(node);
73
 
                rbt_print_subtree(tree, node->left, print);
74
 
                rbt_print_subtree(tree, node->right, print);
75
 
        }
76
 
}
77
 
 
78
 
/**********************************************************************//**
79
 
Verify that the keys are in order.
80
 
@return TRUE of OK. FALSE if not ordered */
81
 
static
82
 
ibool
83
 
rbt_check_ordering(
84
 
/*===============*/
85
 
        const ib_rbt_t*         tree)           /*!< in: tree to verfify */
86
 
{
87
 
        const ib_rbt_node_t*    node;
88
 
        const ib_rbt_node_t*    prev = NULL;
89
 
 
90
 
        /* Iterate over all the nodes, comparing each node with the prev */
91
 
        for (node = rbt_first(tree); node; node = rbt_next(tree, prev)) {
92
 
 
93
 
                if (prev && tree->compare(prev->value, node->value) >= 0) {
94
 
                        return(FALSE);
95
 
                }
96
 
 
97
 
                prev = node;
98
 
        }
99
 
 
100
 
        return(TRUE);
101
 
}
102
 
 
103
 
/**********************************************************************//**
104
 
Check that every path from the root to the leaves has the same count.
105
 
Count is expressed in the number of black nodes.
106
 
@return 0 on failure else black height of the subtree */
107
 
static
108
 
ibool
109
 
rbt_count_black_nodes(
110
 
/*==================*/
111
 
        const ib_rbt_t*         tree,           /*!< in: tree to verify */
112
 
        const ib_rbt_node_t*    node)           /*!< in: start of sub-tree */
113
 
{
114
 
        ulint   result;
115
 
 
116
 
        if (node != tree->nil) {
117
 
                ulint   left_height = rbt_count_black_nodes(tree, node->left);
118
 
 
119
 
                ulint   right_height = rbt_count_black_nodes(tree, node->right);
120
 
 
121
 
                if (left_height == 0
122
 
                    || right_height == 0
123
 
                    || left_height != right_height) {
124
 
 
125
 
                        result = 0;
126
 
                } else if (node->color == IB_RBT_RED) {
127
 
 
128
 
                        /* Case 3 */
129
 
                        if (node->left->color != IB_RBT_BLACK
130
 
                            || node->right->color != IB_RBT_BLACK) {
131
 
 
132
 
                                result = 0;
133
 
                        } else {
134
 
                                result = left_height;
135
 
                        }
136
 
                /* Check if it's anything other than RED or BLACK. */
137
 
                } else if (node->color != IB_RBT_BLACK) {
138
 
 
139
 
                        result = 0;
140
 
                } else {
141
 
 
142
 
                        result = right_height + 1;
143
 
                }
144
 
        } else {
145
 
                result = 1;
146
 
        }
147
 
 
148
 
        return(result);
149
 
}
150
 
 
151
 
/**********************************************************************//**
152
 
Turn the node's right child's left sub-tree into node's right sub-tree.
153
 
This will also make node's right child it's parent. */
154
 
static
155
 
void
156
 
rbt_rotate_left(
157
 
/*============*/
158
 
        const ib_rbt_node_t*    nil,            /*!< in: nil node of the tree */
159
 
        ib_rbt_node_t*          node)           /*!< in: node to rotate */
160
 
{
161
 
        ib_rbt_node_t*  right = node->right;
162
 
 
163
 
        node->right = right->left;
164
 
 
165
 
        if (right->left != nil) {
166
 
                right->left->parent = node;
167
 
        }
168
 
 
169
 
        /* Right's new parent was node's parent. */
170
 
        right->parent = node->parent;
171
 
 
172
 
        /* Since root's parent is tree->nil and root->parent->left points
173
 
        back to root, we can avoid the check. */
174
 
        if (node == node->parent->left) {
175
 
                /* Node was on the left of its parent. */
176
 
                node->parent->left = right;
177
 
        } else {
178
 
                /* Node must have been on the right. */
179
 
                node->parent->right = right;
180
 
        }
181
 
 
182
 
        /* Finally, put node on right's left. */
183
 
        right->left = node;
184
 
        node->parent = right;
185
 
}
186
 
 
187
 
/**********************************************************************//**
188
 
Turn the node's left child's right sub-tree into node's left sub-tree.
189
 
This also make node's left child it's parent. */
190
 
static
191
 
void
192
 
rbt_rotate_right(
193
 
/*=============*/
194
 
        const ib_rbt_node_t*    nil,            /*!< in: nil node of tree */
195
 
        ib_rbt_node_t*          node)           /*!< in: node to rotate */
196
 
{
197
 
        ib_rbt_node_t*  left = node->left;
198
 
 
199
 
        node->left = left->right;
200
 
 
201
 
        if (left->right != nil) {
202
 
                left->right->parent = node;
203
 
        }
204
 
 
205
 
        /* Left's new parent was node's parent. */
206
 
        left->parent = node->parent;
207
 
 
208
 
        /* Since root's parent is tree->nil and root->parent->left points
209
 
        back to root, we can avoid the check. */
210
 
        if (node == node->parent->right) {
211
 
            /* Node was on the left of its parent. */
212
 
            node->parent->right = left;
213
 
        } else {
214
 
            /* Node must have been on the left. */
215
 
            node->parent->left = left;
216
 
        }
217
 
 
218
 
        /* Finally, put node on left's right. */
219
 
        left->right = node;
220
 
        node->parent = left;
221
 
}
222
 
 
223
 
/**********************************************************************//**
224
 
Append a node to the tree. */
225
 
static
226
 
ib_rbt_node_t*
227
 
rbt_tree_add_child(
228
 
/*===============*/
229
 
        const ib_rbt_t* tree,
230
 
        ib_rbt_bound_t* parent,
231
 
        ib_rbt_node_t*  node)
232
 
{
233
 
        /* Cast away the const. */
234
 
        ib_rbt_node_t*  last = (ib_rbt_node_t*) parent->last;
235
 
 
236
 
        if (last == tree->root || parent->result < 0) {
237
 
                last->left = node;
238
 
        } else {
239
 
                /* FIXME: We don't handle duplicates (yet)! */
240
 
                ut_a(parent->result != 0);
241
 
 
242
 
                last->right = node;
243
 
        }
244
 
 
245
 
        node->parent = last;
246
 
 
247
 
        return(node);
248
 
}
249
 
 
250
 
/**********************************************************************//**
251
 
Generic binary tree insert */
252
 
static
253
 
ib_rbt_node_t*
254
 
rbt_tree_insert(
255
 
/*============*/
256
 
        ib_rbt_t*       tree,
257
 
        const void*     key,
258
 
        ib_rbt_node_t*  node)
259
 
{
260
 
        ib_rbt_bound_t  parent;
261
 
        ib_rbt_node_t*  current = ROOT(tree);
262
 
 
263
 
        parent.result = 0;
264
 
        parent.last = tree->root;
265
 
 
266
 
        /* Regular binary search. */
267
 
        while (current != tree->nil) {
268
 
 
269
 
                parent.last = current;
270
 
                parent.result = tree->compare(key, current->value);
271
 
 
272
 
                if (parent.result < 0) {
273
 
                        current = current->left;
274
 
                } else {
275
 
                        current = current->right;
276
 
                }
277
 
        }
278
 
 
279
 
        ut_a(current == tree->nil);
280
 
 
281
 
        rbt_tree_add_child(tree, &parent, node);
282
 
 
283
 
        return(node);
284
 
}
285
 
 
286
 
/**********************************************************************//**
287
 
Balance a tree after inserting a node. */
288
 
static
289
 
void
290
 
rbt_balance_tree(
291
 
/*=============*/
292
 
        const ib_rbt_t* tree,                   /*!< in: tree to balance */
293
 
        ib_rbt_node_t*  node)                   /*!< in: node that was inserted */
294
 
{
295
 
        const ib_rbt_node_t*    nil = tree->nil;
296
 
        ib_rbt_node_t*          parent = node->parent;
297
 
 
298
 
        /* Restore the red-black property. */
299
 
        node->color = IB_RBT_RED;
300
 
 
301
 
        while (node != ROOT(tree) && parent->color == IB_RBT_RED) {
302
 
                ib_rbt_node_t*  grand_parent = parent->parent;
303
 
 
304
 
                if (parent == grand_parent->left) {
305
 
                        ib_rbt_node_t*  uncle = grand_parent->right;
306
 
 
307
 
                        if (uncle->color == IB_RBT_RED) {
308
 
 
309
 
                                /* Case 1 - change the colors. */
310
 
                                uncle->color = IB_RBT_BLACK;
311
 
                                parent->color = IB_RBT_BLACK;
312
 
                                grand_parent->color = IB_RBT_RED;
313
 
 
314
 
                                /* Move node up the tree. */
315
 
                                node = grand_parent;
316
 
 
317
 
                        } else {
318
 
 
319
 
                                if (node == parent->right) {
320
 
                                        /* Right is a black node and node is
321
 
                                        to the right, case 2 - move node
322
 
                                        up and rotate. */
323
 
                                        node = parent;
324
 
                                        rbt_rotate_left(nil, node);
325
 
                                }
326
 
 
327
 
                                grand_parent = node->parent->parent;
328
 
 
329
 
                                /* Case 3. */
330
 
                                node->parent->color = IB_RBT_BLACK;
331
 
                                grand_parent->color = IB_RBT_RED;
332
 
 
333
 
                                rbt_rotate_right(nil, grand_parent);
334
 
                        }
335
 
 
336
 
                } else {
337
 
                        ib_rbt_node_t*  uncle = grand_parent->left;
338
 
 
339
 
                        if (uncle->color == IB_RBT_RED) {
340
 
 
341
 
                                /* Case 1 - change the colors. */
342
 
                                uncle->color = IB_RBT_BLACK;
343
 
                                parent->color = IB_RBT_BLACK;
344
 
                                grand_parent->color = IB_RBT_RED;
345
 
 
346
 
                                /* Move node up the tree. */
347
 
                                node = grand_parent;
348
 
 
349
 
                        } else {
350
 
 
351
 
                                if (node == parent->left) {
352
 
                                        /* Left is a black node and node is to
353
 
                                        the right, case 2 - move node up and
354
 
                                        rotate. */
355
 
                                        node = parent;
356
 
                                        rbt_rotate_right(nil, node);
357
 
                                }
358
 
 
359
 
                                grand_parent = node->parent->parent;
360
 
 
361
 
                                /* Case 3. */
362
 
                                node->parent->color = IB_RBT_BLACK;
363
 
                                grand_parent->color = IB_RBT_RED;
364
 
 
365
 
                                rbt_rotate_left(nil, grand_parent);
366
 
                        }
367
 
                }
368
 
 
369
 
                parent = node->parent;
370
 
        }
371
 
 
372
 
        /* Color the root black. */
373
 
        ROOT(tree)->color = IB_RBT_BLACK;
374
 
}
375
 
 
376
 
/**********************************************************************//**
377
 
Find the given node's successor.
378
 
@return successor node or NULL if no successor */
379
 
static
380
 
ib_rbt_node_t*
381
 
rbt_find_successor(
382
 
/*===============*/
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() */
387
 
{
388
 
        const ib_rbt_node_t*    nil = tree->nil;
389
 
        ib_rbt_node_t*          next = current->right;
390
 
 
391
 
        /* Is there a sub-tree to the right that we can follow. */
392
 
        if (next != nil) {
393
 
 
394
 
                /* Follow the left most links of the current right child. */
395
 
                while (next->left != nil) {
396
 
                        next = next->left;
397
 
                }
398
 
 
399
 
        } else { /* We will have to go up the tree to find the successor. */
400
 
                ib_rbt_node_t*  parent = current->parent;
401
 
 
402
 
                /* Cast away the const. */
403
 
                next = (ib_rbt_node_t*) current;
404
 
 
405
 
                while (parent != tree->root && next == parent->right) {
406
 
                        next = parent;
407
 
                        parent = next->parent;
408
 
                }
409
 
 
410
 
                next = (parent == tree->root) ? NULL : parent;
411
 
        }
412
 
 
413
 
        return(next);
414
 
}
415
 
 
416
 
/**********************************************************************//**
417
 
Find the given node's precedecessor.
418
 
@return predecessor node or NULL if no predecesor */
419
 
static
420
 
ib_rbt_node_t*
421
 
rbt_find_predecessor(
422
 
/*=================*/
423
 
        const ib_rbt_t*         tree,           /*!< in: rb tree */
424
 
        const ib_rbt_node_t*    current)        /*!< in: this is declared const
425
 
                                                because it can be called via
426
 
                                                rbt_prev() */
427
 
{
428
 
        const ib_rbt_node_t*    nil = tree->nil;
429
 
        ib_rbt_node_t*          prev = current->left;
430
 
 
431
 
        /* Is there a sub-tree to the left that we can follow. */
432
 
        if (prev != nil) {
433
 
 
434
 
                /* Follow the right most links of the current left child. */
435
 
                while (prev->right != nil) {
436
 
                        prev = prev->right;
437
 
                }
438
 
 
439
 
        } else { /* We will have to go up the tree to find the precedecessor. */
440
 
                ib_rbt_node_t*  parent = current->parent;
441
 
 
442
 
                /* Cast away the const. */
443
 
                prev = (ib_rbt_node_t*)current;
444
 
 
445
 
                while (parent != tree->root && prev == parent->left) {
446
 
                        prev = parent;
447
 
                        parent = prev->parent;
448
 
                }
449
 
 
450
 
                prev = (parent == tree->root) ? NULL : parent;
451
 
        }
452
 
 
453
 
        return(prev);
454
 
}
455
 
 
456
 
/**********************************************************************//**
457
 
Replace node with child. After applying transformations eject becomes
458
 
an orphan. */
459
 
static
460
 
void
461
 
rbt_eject_node(
462
 
/*===========*/
463
 
        ib_rbt_node_t*  eject,                  /*!< in: node to eject */
464
 
        ib_rbt_node_t*  node)                   /*!< in: node to replace with */
465
 
{
466
 
        /* Update the to be ejected node's parent's child pointers. */
467
 
        if (eject->parent->left == eject) {
468
 
                eject->parent->left = node;
469
 
        } else if (eject->parent->right == eject) {
470
 
                eject->parent->right = node;
471
 
        } else {
472
 
                ut_a(0);
473
 
        }
474
 
        /* eject is now an orphan but otherwise its pointers
475
 
        and color are left intact. */
476
 
 
477
 
        node->parent = eject->parent;
478
 
}
479
 
 
480
 
/**********************************************************************//**
481
 
Replace a node with another node. */
482
 
static
483
 
void
484
 
rbt_replace_node(
485
 
/*=============*/
486
 
        ib_rbt_node_t*  replace,                /*!< in: node to replace */
487
 
        ib_rbt_node_t*  node)                   /*!< in: node to replace with */
488
 
{
489
 
        ib_rbt_color_t  color = node->color;
490
 
 
491
 
        /* Update the node pointers. */
492
 
        node->left = replace->left;
493
 
        node->right = replace->right;
494
 
 
495
 
        /* Update the child node pointers. */
496
 
        node->left->parent = node;
497
 
        node->right->parent = node;
498
 
 
499
 
        /* Make the parent of replace point to node. */
500
 
        rbt_eject_node(replace, node);
501
 
 
502
 
        /* Swap the colors. */
503
 
        node->color = replace->color;
504
 
        replace->color = color;
505
 
}
506
 
 
507
 
/**********************************************************************//**
508
 
Detach node from the tree replacing it with one of it's children.
509
 
@return the child node that now occupies the position of the detached node */
510
 
static
511
 
ib_rbt_node_t*
512
 
rbt_detach_node(
513
 
/*============*/
514
 
        const ib_rbt_t* tree,                   /*!< in: rb tree */
515
 
        ib_rbt_node_t*  node)                   /*!< in: node to detach */
516
 
{
517
 
        ib_rbt_node_t*          child;
518
 
        const ib_rbt_node_t*    nil = tree->nil;
519
 
 
520
 
        if (node->left != nil && node->right != nil) {
521
 
                /* Case where the node to be deleted has two children. */
522
 
                ib_rbt_node_t*  successor = rbt_find_successor(tree, node);
523
 
 
524
 
                ut_a(successor != nil);
525
 
                ut_a(successor->parent != nil);
526
 
                ut_a(successor->left == nil);
527
 
 
528
 
                child = successor->right;
529
 
 
530
 
                /* Remove the successor node and replace with its child. */
531
 
                rbt_eject_node(successor, child);
532
 
 
533
 
                /* Replace the node to delete with its successor node. */
534
 
                rbt_replace_node(node, successor);
535
 
        } else {
536
 
                ut_a(node->left == nil || node->right == nil);
537
 
 
538
 
                child = (node->left != nil) ? node->left : node->right;
539
 
 
540
 
                /* Replace the node to delete with one of it's children. */
541
 
                rbt_eject_node(node, child);
542
 
        }
543
 
 
544
 
        /* Reset the node links. */
545
 
        node->parent = node->right = node->left = tree->nil;
546
 
 
547
 
        return(child);
548
 
}
549
 
 
550
 
/**********************************************************************//**
551
 
Rebalance the right sub-tree after deletion.
552
 
@return node to rebalance if more rebalancing required else NULL */
553
 
static
554
 
ib_rbt_node_t*
555
 
rbt_balance_right(
556
 
/*==============*/
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 */
560
 
{
561
 
        ib_rbt_node_t*          node = NULL;
562
 
 
563
 
        ut_a(sibling != nil);
564
 
 
565
 
        /* Case 3. */
566
 
        if (sibling->color == IB_RBT_RED) {
567
 
 
568
 
                parent->color = IB_RBT_RED;
569
 
                sibling->color = IB_RBT_BLACK;
570
 
 
571
 
                rbt_rotate_left(nil, parent);
572
 
 
573
 
                sibling = parent->right;
574
 
 
575
 
                ut_a(sibling != nil);
576
 
        }
577
 
 
578
 
        /* Since this will violate case 3 because of the change above. */
579
 
        if (sibling->left->color == IB_RBT_BLACK
580
 
            && sibling->right->color == IB_RBT_BLACK) {
581
 
 
582
 
                node = parent; /* Parent needs to be rebalanced too. */
583
 
                sibling->color = IB_RBT_RED;
584
 
 
585
 
        } else {
586
 
                if (sibling->right->color == IB_RBT_BLACK) {
587
 
 
588
 
                        ut_a(sibling->left->color == IB_RBT_RED);
589
 
 
590
 
                        sibling->color = IB_RBT_RED;
591
 
                        sibling->left->color = IB_RBT_BLACK;
592
 
 
593
 
                        rbt_rotate_right(nil, sibling);
594
 
 
595
 
                        sibling = parent->right;
596
 
                        ut_a(sibling != nil);
597
 
                }
598
 
 
599
 
                sibling->color = parent->color;
600
 
                sibling->right->color = IB_RBT_BLACK;
601
 
 
602
 
                parent->color = IB_RBT_BLACK;
603
 
 
604
 
                rbt_rotate_left(nil, parent);
605
 
        }
606
 
 
607
 
        return(node);
608
 
}
609
 
 
610
 
/**********************************************************************//**
611
 
Rebalance the left sub-tree after deletion.
612
 
@return node to rebalance if more rebalancing required else NULL */
613
 
static
614
 
ib_rbt_node_t*
615
 
rbt_balance_left(
616
 
/*=============*/
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 */
620
 
{
621
 
        ib_rbt_node_t*  node = NULL;
622
 
 
623
 
        ut_a(sibling != nil);
624
 
 
625
 
        /* Case 3. */
626
 
        if (sibling->color == IB_RBT_RED) {
627
 
 
628
 
                parent->color = IB_RBT_RED;
629
 
                sibling->color = IB_RBT_BLACK;
630
 
 
631
 
                rbt_rotate_right(nil, parent);
632
 
                sibling = parent->left;
633
 
 
634
 
                ut_a(sibling != nil);
635
 
        }
636
 
 
637
 
        /* Since this will violate case 3 because of the change above. */
638
 
        if (sibling->right->color == IB_RBT_BLACK
639
 
            && sibling->left->color == IB_RBT_BLACK) {
640
 
 
641
 
                node = parent; /* Parent needs to be rebalanced too. */
642
 
                sibling->color = IB_RBT_RED;
643
 
 
644
 
        } else {
645
 
                if (sibling->left->color == IB_RBT_BLACK) {
646
 
 
647
 
                        ut_a(sibling->right->color == IB_RBT_RED);
648
 
 
649
 
                        sibling->color = IB_RBT_RED;
650
 
                        sibling->right->color = IB_RBT_BLACK;
651
 
 
652
 
                        rbt_rotate_left(nil, sibling);
653
 
 
654
 
                        sibling = parent->left;
655
 
 
656
 
                        ut_a(sibling != nil);
657
 
                }
658
 
 
659
 
                sibling->color = parent->color;
660
 
                sibling->left->color = IB_RBT_BLACK;
661
 
 
662
 
                parent->color = IB_RBT_BLACK;
663
 
 
664
 
                rbt_rotate_right(nil, parent);
665
 
        }
666
 
 
667
 
        return(node);
668
 
}
669
 
 
670
 
/**********************************************************************//**
671
 
Delete the node and rebalance the tree if necessary */
672
 
static
673
 
void
674
 
rbt_remove_node_and_rebalance(
675
 
/*==========================*/
676
 
        ib_rbt_t*               tree,           /*!< in: rb tree */
677
 
        ib_rbt_node_t*          node)           /*!< in: node to remove */
678
 
{
679
 
        /* Detach node and get the node that will be used
680
 
        as rebalance start. */
681
 
        ib_rbt_node_t*  child = rbt_detach_node(tree, node);
682
 
 
683
 
        if (node->color == IB_RBT_BLACK) {
684
 
                ib_rbt_node_t*  last = child;
685
 
 
686
 
                ROOT(tree)->color = IB_RBT_RED;
687
 
 
688
 
                while (child && child->color == IB_RBT_BLACK) {
689
 
                        ib_rbt_node_t*  parent = child->parent;
690
 
 
691
 
                        /* Did the deletion cause an imbalance in the
692
 
                        parents left sub-tree. */
693
 
                        if (parent->left == child) {
694
 
 
695
 
                                child = rbt_balance_right(
696
 
                                        tree->nil, parent, parent->right);
697
 
 
698
 
                        } else if (parent->right == child) {
699
 
 
700
 
                                child = rbt_balance_left(
701
 
                                        tree->nil, parent, parent->left);
702
 
 
703
 
                        } else {
704
 
                                ut_error;
705
 
                        }
706
 
 
707
 
                        if (child) {
708
 
                                last = child;
709
 
                        }
710
 
                }
711
 
 
712
 
                ut_a(last);
713
 
 
714
 
                last->color = IB_RBT_BLACK;
715
 
                ROOT(tree)->color = IB_RBT_BLACK;
716
 
        }
717
 
 
718
 
        /* Note that we have removed a node from the tree. */
719
 
        --tree->n_nodes;
720
 
}
721
 
 
722
 
/**********************************************************************//**
723
 
Recursively free the nodes. */
724
 
static
725
 
void
726
 
rbt_free_node(
727
 
/*==========*/
728
 
        ib_rbt_node_t*  node,                   /*!< in: node to free */
729
 
        ib_rbt_node_t*  nil)                    /*!< in: rb tree nil node */
730
 
{
731
 
        if (node != nil) {
732
 
                rbt_free_node(node->left, nil);
733
 
                rbt_free_node(node->right, nil);
734
 
 
735
 
                ut_free(node);
736
 
        }
737
 
}
738
 
 
739
 
/**********************************************************************//**
740
 
Free all the nodes and free the tree. */
741
 
UNIV_INTERN
742
 
void
743
 
rbt_free(
744
 
/*=====*/
745
 
        ib_rbt_t*       tree)                   /*!< in: rb tree to free */
746
 
{
747
 
        rbt_free_node(tree->root, tree->nil);
748
 
        ut_free(tree->nil);
749
 
        ut_free(tree);
750
 
}
751
 
 
752
 
/**********************************************************************//**
753
 
Create an instance of a red black tree.
754
 
@return an empty rb tree */
755
 
UNIV_INTERN
756
 
ib_rbt_t*
757
 
rbt_create(
758
 
/*=======*/
759
 
        size_t          sizeof_value,           /*!< in: sizeof data item */
760
 
        ib_rbt_compare  compare)                /*!< in: fn to compare items */
761
 
{
762
 
        ib_rbt_t*       tree;
763
 
        ib_rbt_node_t*  node;
764
 
 
765
 
        tree = (ib_rbt_t*) ut_malloc(sizeof(*tree));
766
 
        memset(tree, 0, sizeof(*tree));
767
 
 
768
 
        tree->sizeof_value = sizeof_value;
769
 
 
770
 
        /* Create the sentinel (NIL) node. */
771
 
        node = tree->nil = (ib_rbt_node_t*) ut_malloc(sizeof(*node));
772
 
        memset(node, 0, sizeof(*node));
773
 
 
774
 
        node->color = IB_RBT_BLACK;
775
 
        node->parent = node->left = node->right = node;
776
 
 
777
 
        /* Create the "fake" root, the real root node will be the
778
 
        left child of this node. */
779
 
        node = tree->root = (ib_rbt_node_t*) ut_malloc(sizeof(*node));
780
 
        memset(node, 0, sizeof(*node));
781
 
 
782
 
        node->color = IB_RBT_BLACK;
783
 
        node->parent = node->left = node->right = tree->nil;
784
 
 
785
 
        tree->compare = compare;
786
 
 
787
 
        return(tree);
788
 
}
789
 
 
790
 
/**********************************************************************//**
791
 
Generic insert of a value in the rb tree.
792
 
@return inserted node */
793
 
UNIV_INTERN
794
 
const ib_rbt_node_t*
795
 
rbt_insert(
796
 
/*=======*/
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 */
801
 
{
802
 
        ib_rbt_node_t*  node;
803
 
 
804
 
        /* Create the node that will hold the value data. */
805
 
        node = (ib_rbt_node_t*) ut_malloc(SIZEOF_NODE(tree));
806
 
 
807
 
        memcpy(node->value, value, tree->sizeof_value);
808
 
        node->parent = node->left = node->right = tree->nil;
809
 
 
810
 
        /* Insert in the tree in the usual way. */
811
 
        rbt_tree_insert(tree, key, node);
812
 
        rbt_balance_tree(tree, node);
813
 
 
814
 
        ++tree->n_nodes;
815
 
 
816
 
        return(node);
817
 
}
818
 
 
819
 
/**********************************************************************//**
820
 
Add a new node to the tree, useful for data that is pre-sorted.
821
 
@return appended node */
822
 
UNIV_INTERN
823
 
const ib_rbt_node_t*
824
 
rbt_add_node(
825
 
/*=========*/
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 */
830
 
{
831
 
        ib_rbt_node_t*  node;
832
 
 
833
 
        /* Create the node that will hold the value data */
834
 
        node = (ib_rbt_node_t*) ut_malloc(SIZEOF_NODE(tree));
835
 
 
836
 
        memcpy(node->value, value, tree->sizeof_value);
837
 
        node->parent = node->left = node->right = tree->nil;
838
 
 
839
 
        /* If tree is empty */
840
 
        if (parent->last == NULL) {
841
 
                parent->last = tree->root;
842
 
        }
843
 
 
844
 
        /* Append the node, the hope here is that the caller knows
845
 
        what s/he is doing. */
846
 
        rbt_tree_add_child(tree, parent, node);
847
 
        rbt_balance_tree(tree, node);
848
 
 
849
 
        ++tree->n_nodes;
850
 
 
851
 
#if     defined(IB_RBT_TESTING)
852
 
        ut_a(rbt_validate(tree));
853
 
#endif
854
 
        return(node);
855
 
}
856
 
 
857
 
/**********************************************************************//**
858
 
Find a matching node in the rb tree.
859
 
@return NULL if not found else the node where key was found */
860
 
UNIV_INTERN
861
 
const ib_rbt_node_t*
862
 
rbt_lookup(
863
 
/*=======*/
864
 
        const ib_rbt_t* tree,                   /*!< in: rb tree */
865
 
        const void*     key)                    /*!< in: key to use for search */
866
 
{
867
 
        const ib_rbt_node_t*    current = ROOT(tree);
868
 
 
869
 
        /* Regular binary search. */
870
 
        while (current != tree->nil) {
871
 
                int     result = tree->compare(key, current->value);
872
 
 
873
 
                if (result < 0) {
874
 
                        current = current->left;
875
 
                } else if (result > 0) {
876
 
                        current = current->right;
877
 
                } else {
878
 
                        break;
879
 
                }
880
 
        }
881
 
 
882
 
        return(current != tree->nil ? current : NULL);
883
 
}
884
 
 
885
 
/**********************************************************************//**
886
 
Delete a node indentified by key.
887
 
@return TRUE if success FALSE if not found */
888
 
UNIV_INTERN
889
 
ibool
890
 
rbt_delete(
891
 
/*=======*/
892
 
        ib_rbt_t*       tree,                   /*!< in: rb tree */
893
 
        const void*     key)                    /*!< in: key to delete */
894
 
{
895
 
        ibool           deleted = FALSE;
896
 
        ib_rbt_node_t*  node = (ib_rbt_node_t*) rbt_lookup(tree, key);
897
 
 
898
 
        if (node) {
899
 
                rbt_remove_node_and_rebalance(tree, node);
900
 
 
901
 
                ut_free(node);
902
 
                deleted = TRUE;
903
 
        }
904
 
 
905
 
        return(deleted);
906
 
}
907
 
 
908
 
/**********************************************************************//**
909
 
Remove a node from the rb tree, the node is not free'd, that is the
910
 
callers responsibility.
911
 
@return deleted node but without the const */
912
 
UNIV_INTERN
913
 
ib_rbt_node_t*
914
 
rbt_remove_node(
915
 
/*============*/
916
 
        ib_rbt_t*               tree,           /*!< in: rb tree */
917
 
        const ib_rbt_node_t*    const_node)     /*!< in: node to delete, this
918
 
                                                is a fudge and declared const
919
 
                                                because the caller can access
920
 
                                                only const nodes */
921
 
{
922
 
        /* Cast away the const. */
923
 
        rbt_remove_node_and_rebalance(tree, (ib_rbt_node_t*) const_node);
924
 
 
925
 
        /* This is to make it easier to do something like this:
926
 
                ut_free(rbt_remove_node(node));
927
 
        */
928
 
 
929
 
        return((ib_rbt_node_t*) const_node);
930
 
}
931
 
 
932
 
/**********************************************************************//**
933
 
Find the node that has the lowest key that is >= key.
934
 
@return node satisfying the lower bound constraint or NULL */
935
 
UNIV_INTERN
936
 
const ib_rbt_node_t*
937
 
rbt_lower_bound(
938
 
/*============*/
939
 
        const ib_rbt_t* tree,                   /*!< in: rb tree */
940
 
        const void*     key)                    /*!< in: key to search */
941
 
{
942
 
        ib_rbt_node_t*  lb_node = NULL;
943
 
        ib_rbt_node_t*  current = ROOT(tree);
944
 
 
945
 
        while (current != tree->nil) {
946
 
                int result = tree->compare(key, current->value);
947
 
 
948
 
                if (result > 0) {
949
 
 
950
 
                        current = current->right;
951
 
 
952
 
                } else if (result < 0) {
953
 
 
954
 
                        lb_node = current;
955
 
                        current = current->left;
956
 
 
957
 
                } else {
958
 
                        lb_node = current;
959
 
                        break;
960
 
                }
961
 
        }
962
 
 
963
 
        return(lb_node);
964
 
}
965
 
 
966
 
/**********************************************************************//**
967
 
Find the node that has the greatest key that is <= key.
968
 
@return node satisfying the upper bound constraint or NULL */
969
 
UNIV_INTERN
970
 
const ib_rbt_node_t*
971
 
rbt_upper_bound(
972
 
/*============*/
973
 
        const ib_rbt_t* tree,                   /*!< in: rb tree */
974
 
        const void*     key)                    /*!< in: key to search */
975
 
{
976
 
        ib_rbt_node_t*  ub_node = NULL;
977
 
        ib_rbt_node_t*  current = ROOT(tree);
978
 
 
979
 
        while (current != tree->nil) {
980
 
                int result = tree->compare(key, current->value);
981
 
 
982
 
                if (result > 0) {
983
 
 
984
 
                        ub_node = current;
985
 
                        current = current->right;
986
 
 
987
 
                } else if (result < 0) {
988
 
 
989
 
                        current = current->left;
990
 
 
991
 
                } else {
992
 
                        ub_node = current;
993
 
                        break;
994
 
                }
995
 
        }
996
 
 
997
 
        return(ub_node);
998
 
}
999
 
 
1000
 
/**********************************************************************//**
1001
 
Find the node that has the greatest key that is <= key.
1002
 
@return value of result */
1003
 
UNIV_INTERN
1004
 
int
1005
 
rbt_search(
1006
 
/*=======*/
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 */
1010
 
{
1011
 
        ib_rbt_node_t*  current = ROOT(tree);
1012
 
 
1013
 
        /* Every thing is greater than the NULL root. */
1014
 
        parent->result = 1;
1015
 
        parent->last = NULL;
1016
 
 
1017
 
        while (current != tree->nil) {
1018
 
 
1019
 
                parent->last = current;
1020
 
                parent->result = tree->compare(key, current->value);
1021
 
 
1022
 
                if (parent->result > 0) {
1023
 
                        current = current->right;
1024
 
                } else if (parent->result < 0) {
1025
 
                        current = current->left;
1026
 
                } else {
1027
 
                        break;
1028
 
                }
1029
 
        }
1030
 
 
1031
 
        return(parent->result);
1032
 
}
1033
 
 
1034
 
/**********************************************************************//**
1035
 
Find the node that has the greatest key that is <= key. But use the
1036
 
supplied comparison function.
1037
 
@return value of result */
1038
 
UNIV_INTERN
1039
 
int
1040
 
rbt_search_cmp(
1041
 
/*===========*/
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 */
1046
 
{
1047
 
        ib_rbt_node_t*  current = ROOT(tree);
1048
 
 
1049
 
        /* Every thing is greater than the NULL root. */
1050
 
        parent->result = 1;
1051
 
        parent->last = NULL;
1052
 
 
1053
 
        while (current != tree->nil) {
1054
 
 
1055
 
                parent->last = current;
1056
 
                parent->result = compare(key, current->value);
1057
 
 
1058
 
                if (parent->result > 0) {
1059
 
                        current = current->right;
1060
 
                } else if (parent->result < 0) {
1061
 
                        current = current->left;
1062
 
                } else {
1063
 
                        break;
1064
 
                }
1065
 
        }
1066
 
 
1067
 
        return(parent->result);
1068
 
}
1069
 
 
1070
 
/**********************************************************************//**
1071
 
Return the left most node in the tree. */
1072
 
UNIV_INTERN
1073
 
const ib_rbt_node_t*
1074
 
rbt_first(
1075
 
/*======*/
1076
 
                                                /* out leftmost node or NULL */
1077
 
        const ib_rbt_t* tree)                   /* in: rb tree */
1078
 
{
1079
 
        ib_rbt_node_t*  first = NULL;
1080
 
        ib_rbt_node_t*  current = ROOT(tree);
1081
 
 
1082
 
        while (current != tree->nil) {
1083
 
                first = current;
1084
 
                current = current->left;
1085
 
        }
1086
 
 
1087
 
        return(first);
1088
 
}
1089
 
 
1090
 
/**********************************************************************//**
1091
 
Return the right most node in the tree.
1092
 
@return the rightmost node or NULL */
1093
 
UNIV_INTERN
1094
 
const ib_rbt_node_t*
1095
 
rbt_last(
1096
 
/*=====*/
1097
 
        const ib_rbt_t* tree)                   /*!< in: rb tree */
1098
 
{
1099
 
        ib_rbt_node_t*  last = NULL;
1100
 
        ib_rbt_node_t*  current = ROOT(tree);
1101
 
 
1102
 
        while (current != tree->nil) {
1103
 
                last = current;
1104
 
                current = current->right;
1105
 
        }
1106
 
 
1107
 
        return(last);
1108
 
}
1109
 
 
1110
 
/**********************************************************************//**
1111
 
Return the next node.
1112
 
@return node next from current */
1113
 
UNIV_INTERN
1114
 
const ib_rbt_node_t*
1115
 
rbt_next(
1116
 
/*=====*/
1117
 
        const ib_rbt_t*         tree,           /*!< in: rb tree */
1118
 
        const ib_rbt_node_t*    current)        /*!< in: current node */
1119
 
{
1120
 
        return(current ? rbt_find_successor(tree, current) : NULL);
1121
 
}
1122
 
 
1123
 
/**********************************************************************//**
1124
 
Return the previous node.
1125
 
@return node prev from current */
1126
 
UNIV_INTERN
1127
 
const ib_rbt_node_t*
1128
 
rbt_prev(
1129
 
/*=====*/
1130
 
        const ib_rbt_t*         tree,           /*!< in: rb tree */
1131
 
        const ib_rbt_node_t*    current)        /*!< in: current node */
1132
 
{
1133
 
        return(current ? rbt_find_predecessor(tree, current) : NULL);
1134
 
}
1135
 
 
1136
 
/**********************************************************************//**
1137
 
Reset the tree. Delete all the nodes. */
1138
 
UNIV_INTERN
1139
 
void
1140
 
rbt_clear(
1141
 
/*======*/
1142
 
        ib_rbt_t*       tree)                   /*!< in: rb tree */
1143
 
{
1144
 
        rbt_free_node(ROOT(tree), tree->nil);
1145
 
 
1146
 
        tree->n_nodes = 0;
1147
 
        tree->root->left = tree->root->right = tree->nil;
1148
 
}
1149
 
 
1150
 
/**********************************************************************//**
1151
 
Merge the node from dst into src. Return the number of nodes merged.
1152
 
@return no. of recs merged */
1153
 
UNIV_INTERN
1154
 
ulint
1155
 
rbt_merge_uniq(
1156
 
/*===========*/
1157
 
        ib_rbt_t*       dst,                    /*!< in: dst rb tree */
1158
 
        const ib_rbt_t* src)                    /*!< in: src rb tree */
1159
 
{
1160
 
        ib_rbt_bound_t          parent;
1161
 
        ulint                   n_merged = 0;
1162
 
        const   ib_rbt_node_t*  src_node = rbt_first(src);
1163
 
 
1164
 
        if (rbt_empty(src) || dst == src) {
1165
 
                return(0);
1166
 
        }
1167
 
 
1168
 
        for (/* No op */; src_node; src_node = rbt_next(src, src_node)) {
1169
 
 
1170
 
                if (rbt_search(dst, &parent, src_node->value) != 0) {
1171
 
                        rbt_add_node(dst, &parent, src_node->value);
1172
 
                        ++n_merged;
1173
 
                }
1174
 
        }
1175
 
 
1176
 
        return(n_merged);
1177
 
}
1178
 
 
1179
 
/**********************************************************************//**
1180
 
Merge the node from dst into src. Return the number of nodes merged.
1181
 
Delete the nodes from src after copying node to dst. As a side effect
1182
 
the duplicates will be left untouched in the src.
1183
 
@return no. of recs merged */
1184
 
UNIV_INTERN
1185
 
ulint
1186
 
rbt_merge_uniq_destructive(
1187
 
/*=======================*/
1188
 
        ib_rbt_t*       dst,                    /*!< in: dst rb tree */
1189
 
        ib_rbt_t*       src)                    /*!< in: src rb tree */
1190
 
{
1191
 
        ib_rbt_bound_t  parent;
1192
 
        ib_rbt_node_t*  src_node;
1193
 
        ulint           old_size = rbt_size(dst);
1194
 
 
1195
 
        if (rbt_empty(src) || dst == src) {
1196
 
                return(0);
1197
 
        }
1198
 
 
1199
 
        for (src_node = (ib_rbt_node_t*) rbt_first(src); src_node; /* */) {
1200
 
                ib_rbt_node_t*  prev = src_node;
1201
 
 
1202
 
                src_node = (ib_rbt_node_t*)rbt_next(src, prev);
1203
 
 
1204
 
                /* Skip duplicates. */
1205
 
                if (rbt_search(dst, &parent, prev->value) != 0) {
1206
 
 
1207
 
                        /* Remove and reset the node but preserve
1208
 
                        the node (data) value. */
1209
 
                        rbt_remove_node_and_rebalance(src, prev);
1210
 
 
1211
 
                        /* The nil should be taken from the dst tree. */
1212
 
                        prev->parent = prev->left = prev->right = dst->nil;
1213
 
                        rbt_tree_add_child(dst, &parent, prev);
1214
 
                        rbt_balance_tree(dst, prev);
1215
 
 
1216
 
                        ++dst->n_nodes;
1217
 
                }
1218
 
        }
1219
 
 
1220
 
#if     defined(IB_RBT_TESTING)
1221
 
        ut_a(rbt_validate(dst));
1222
 
        ut_a(rbt_validate(src));
1223
 
#endif
1224
 
        return(rbt_size(dst) - old_size);
1225
 
}
1226
 
 
1227
 
/**********************************************************************//**
1228
 
Check that every path from the root to the leaves has the same count and
1229
 
the tree nodes are in order.
1230
 
@return TRUE if OK FALSE otherwise */
1231
 
UNIV_INTERN
1232
 
ibool
1233
 
rbt_validate(
1234
 
/*=========*/
1235
 
        const ib_rbt_t* tree)           /*!< in: RB tree to validate */
1236
 
{
1237
 
        if (rbt_count_black_nodes(tree, ROOT(tree)) > 0) {
1238
 
                return(rbt_check_ordering(tree));
1239
 
        }
1240
 
 
1241
 
        return(FALSE);
1242
 
}
1243
 
 
1244
 
/**********************************************************************//**
1245
 
Iterate over the tree in depth first order. */
1246
 
UNIV_INTERN
1247
 
void
1248
 
rbt_print(
1249
 
/*======*/
1250
 
        const ib_rbt_t*         tree,           /*!< in: tree to traverse */
1251
 
        ib_rbt_print_node       print)          /*!< in: print function */
1252
 
{
1253
 
        rbt_print_subtree(tree, ROOT(tree), print);
1254
 
}