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