53#if defined(IB_RBT_TESTING)
54#warning "Testing enabled!"
57#define ROOT(t) (t->root->left)
58#define SIZEOF_NODE(t) ((sizeof(ib_rbt_node_t) + t->sizeof_value) - 1)
67 const ib_rbt_node_t* node,
68 ib_rbt_print_node print)
71 if (node != tree->nil) {
73 rbt_print_subtree(tree, node->left, print);
74 rbt_print_subtree(tree, node->right, print);
87 const ib_rbt_node_t* node;
88 const ib_rbt_node_t* prev = NULL;
93 if (prev && tree->compare(prev->value, node->value) >= 0) {
109rbt_count_black_nodes(
111 const ib_rbt_t* tree,
112 const ib_rbt_node_t* node)
116 if (node != tree->nil) {
117 ulint left_height = rbt_count_black_nodes(tree, node->left);
119 ulint right_height = rbt_count_black_nodes(tree, node->right);
123 || left_height != right_height) {
126 }
else if (node->color == IB_RBT_RED) {
129 if (node->left->color != IB_RBT_BLACK
130 || node->right->color != IB_RBT_BLACK) {
134 result = left_height;
137 }
else if (node->color != IB_RBT_BLACK) {
142 result = right_height + 1;
158 const ib_rbt_node_t* nil,
161 ib_rbt_node_t* right = node->right;
163 node->right = right->left;
165 if (right->left != nil) {
166 right->left->parent = node;
170 right->parent = node->parent;
174 if (node == node->parent->left) {
176 node->parent->left = right;
179 node->parent->right = right;
184 node->parent = right;
194 const ib_rbt_node_t* nil,
197 ib_rbt_node_t* left = node->left;
199 node->left = left->right;
201 if (left->right != nil) {
202 left->right->parent = node;
206 left->parent = node->parent;
210 if (node == node->parent->right) {
212 node->parent->right = left;
215 node->parent->left = left;
229 const ib_rbt_t* tree,
230 ib_rbt_bound_t* parent,
234 ib_rbt_node_t* last = (ib_rbt_node_t*) parent->last;
236 if (last == tree->root || parent->result < 0) {
240 ut_a(parent->result != 0);
260 ib_rbt_bound_t parent;
261 ib_rbt_node_t* current = ROOT(tree);
264 parent.last = tree->root;
267 while (current != tree->nil) {
269 parent.last = current;
270 parent.result = tree->compare(key, current->value);
272 if (parent.result < 0) {
273 current = current->left;
275 current = current->right;
279 ut_a(current == tree->nil);
281 rbt_tree_add_child(tree, &parent, node);
292 const ib_rbt_t* tree,
295 const ib_rbt_node_t* nil = tree->nil;
296 ib_rbt_node_t* parent = node->parent;
299 node->color = IB_RBT_RED;
301 while (node != ROOT(tree) && parent->color == IB_RBT_RED) {
302 ib_rbt_node_t* grand_parent = parent->parent;
304 if (parent == grand_parent->left) {
305 ib_rbt_node_t* uncle = grand_parent->right;
307 if (uncle->color == IB_RBT_RED) {
310 uncle->color = IB_RBT_BLACK;
311 parent->color = IB_RBT_BLACK;
312 grand_parent->color = IB_RBT_RED;
319 if (node == parent->right) {
324 rbt_rotate_left(nil, node);
327 grand_parent = node->parent->parent;
330 node->parent->color = IB_RBT_BLACK;
331 grand_parent->color = IB_RBT_RED;
333 rbt_rotate_right(nil, grand_parent);
337 ib_rbt_node_t* uncle = grand_parent->left;
339 if (uncle->color == IB_RBT_RED) {
342 uncle->color = IB_RBT_BLACK;
343 parent->color = IB_RBT_BLACK;
344 grand_parent->color = IB_RBT_RED;
351 if (node == parent->left) {
356 rbt_rotate_right(nil, node);
359 grand_parent = node->parent->parent;
362 node->parent->color = IB_RBT_BLACK;
363 grand_parent->color = IB_RBT_RED;
365 rbt_rotate_left(nil, grand_parent);
369 parent = node->parent;
373 ROOT(tree)->color = IB_RBT_BLACK;
383 const ib_rbt_t* tree,
384 const ib_rbt_node_t* current)
388 const ib_rbt_node_t* nil = tree->nil;
389 ib_rbt_node_t* next = current->right;
395 while (next->left != nil) {
400 ib_rbt_node_t* parent = current->parent;
403 next = (ib_rbt_node_t*) current;
405 while (parent != tree->root && next == parent->right) {
407 parent = next->parent;
410 next = (parent == tree->root) ? NULL : parent;
423 const ib_rbt_t* tree,
424 const ib_rbt_node_t* current)
428 const ib_rbt_node_t* nil = tree->nil;
429 ib_rbt_node_t* prev = current->left;
435 while (prev->right != nil) {
440 ib_rbt_node_t* parent = current->parent;
443 prev = (ib_rbt_node_t*)current;
445 while (parent != tree->root && prev == parent->left) {
447 parent = prev->parent;
450 prev = (parent == tree->root) ? NULL : parent;
463 ib_rbt_node_t* eject,
467 if (eject->parent->left == eject) {
468 eject->parent->left = node;
469 }
else if (eject->parent->right == eject) {
470 eject->parent->right = node;
477 node->parent = eject->parent;
486 ib_rbt_node_t* replace,
489 ib_rbt_color_t color = node->color;
492 node->left = replace->left;
493 node->right = replace->right;
496 node->left->parent = node;
497 node->right->parent = node;
500 rbt_eject_node(replace, node);
503 node->color = replace->color;
504 replace->color = color;
514 const ib_rbt_t* tree,
517 ib_rbt_node_t* child;
518 const ib_rbt_node_t* nil = tree->nil;
520 if (node->left != nil && node->right != nil) {
522 ib_rbt_node_t* successor = rbt_find_successor(tree, node);
524 ut_a(successor != nil);
525 ut_a(successor->parent != nil);
526 ut_a(successor->left == nil);
528 child = successor->right;
531 rbt_eject_node(successor, child);
534 rbt_replace_node(node, successor);
536 ut_a(node->left == nil || node->right == nil);
538 child = (node->left != nil) ? node->left : node->right;
541 rbt_eject_node(node, child);
545 node->parent = node->right = node->left = tree->nil;
557 const ib_rbt_node_t* nil,
558 ib_rbt_node_t* parent,
559 ib_rbt_node_t* sibling)
561 ib_rbt_node_t* node = NULL;
563 ut_a(sibling != nil);
566 if (sibling->color == IB_RBT_RED) {
568 parent->color = IB_RBT_RED;
569 sibling->color = IB_RBT_BLACK;
571 rbt_rotate_left(nil, parent);
573 sibling = parent->right;
575 ut_a(sibling != nil);
579 if (sibling->left->color == IB_RBT_BLACK
580 && sibling->right->color == IB_RBT_BLACK) {
583 sibling->color = IB_RBT_RED;
586 if (sibling->right->color == IB_RBT_BLACK) {
588 ut_a(sibling->left->color == IB_RBT_RED);
590 sibling->color = IB_RBT_RED;
591 sibling->left->color = IB_RBT_BLACK;
593 rbt_rotate_right(nil, sibling);
595 sibling = parent->right;
596 ut_a(sibling != nil);
599 sibling->color = parent->color;
600 sibling->right->color = IB_RBT_BLACK;
602 parent->color = IB_RBT_BLACK;
604 rbt_rotate_left(nil, parent);
617 const ib_rbt_node_t* nil,
618 ib_rbt_node_t* parent,
619 ib_rbt_node_t* sibling)
621 ib_rbt_node_t* node = NULL;
623 ut_a(sibling != nil);
626 if (sibling->color == IB_RBT_RED) {
628 parent->color = IB_RBT_RED;
629 sibling->color = IB_RBT_BLACK;
631 rbt_rotate_right(nil, parent);
632 sibling = parent->left;
634 ut_a(sibling != nil);
638 if (sibling->right->color == IB_RBT_BLACK
639 && sibling->left->color == IB_RBT_BLACK) {
642 sibling->color = IB_RBT_RED;
645 if (sibling->left->color == IB_RBT_BLACK) {
647 ut_a(sibling->right->color == IB_RBT_RED);
649 sibling->color = IB_RBT_RED;
650 sibling->right->color = IB_RBT_BLACK;
652 rbt_rotate_left(nil, sibling);
654 sibling = parent->left;
656 ut_a(sibling != nil);
659 sibling->color = parent->color;
660 sibling->left->color = IB_RBT_BLACK;
662 parent->color = IB_RBT_BLACK;
664 rbt_rotate_right(nil, parent);
674rbt_remove_node_and_rebalance(
681 ib_rbt_node_t* child = rbt_detach_node(tree, node);
683 if (node->color == IB_RBT_BLACK) {
684 ib_rbt_node_t* last = child;
686 ROOT(tree)->color = IB_RBT_RED;
688 while (child && child->color == IB_RBT_BLACK) {
689 ib_rbt_node_t* parent = child->parent;
693 if (parent->left == child) {
695 child = rbt_balance_right(
696 tree->nil, parent, parent->right);
698 }
else if (parent->right == child) {
700 child = rbt_balance_left(
701 tree->nil, parent, parent->left);
714 last->color = IB_RBT_BLACK;
715 ROOT(tree)->color = IB_RBT_BLACK;
732 rbt_free_node(node->left, nil);
733 rbt_free_node(node->right, nil);
747 rbt_free_node(tree->root, tree->nil);
760 ib_rbt_compare compare)
765 tree = (ib_rbt_t*)
ut_malloc(
sizeof(*tree));
766 memset(tree, 0,
sizeof(*tree));
768 tree->sizeof_value = sizeof_value;
771 node = tree->nil = (ib_rbt_node_t*)
ut_malloc(
sizeof(*node));
772 memset(node, 0,
sizeof(*node));
774 node->color = IB_RBT_BLACK;
775 node->parent = node->left = node->right = node;
779 node = tree->root = (ib_rbt_node_t*)
ut_malloc(
sizeof(*node));
780 memset(node, 0,
sizeof(*node));
782 node->color = IB_RBT_BLACK;
783 node->parent = node->left = node->right = tree->nil;
785 tree->compare = compare;
805 node = (ib_rbt_node_t*)
ut_malloc(SIZEOF_NODE(tree));
807 memcpy(node->value, value, tree->sizeof_value);
808 node->parent = node->left = node->right = tree->nil;
811 rbt_tree_insert(tree, key, node);
812 rbt_balance_tree(tree, node);
827 ib_rbt_bound_t* parent,
834 node = (ib_rbt_node_t*)
ut_malloc(SIZEOF_NODE(tree));
836 memcpy(node->value, value, tree->sizeof_value);
837 node->parent = node->left = node->right = tree->nil;
840 if (parent->last == NULL) {
841 parent->last = tree->root;
846 rbt_tree_add_child(tree, parent, node);
847 rbt_balance_tree(tree, node);
851#if defined(IB_RBT_TESTING)
864 const ib_rbt_t* tree,
867 const ib_rbt_node_t* current = ROOT(tree);
870 while (current != tree->nil) {
871 int result = tree->compare(key, current->value);
874 current = current->left;
875 }
else if (result > 0) {
876 current = current->right;
882 return(current != tree->nil ? current : NULL);
895 ibool deleted = FALSE;
896 ib_rbt_node_t* node = (ib_rbt_node_t*)
rbt_lookup(tree, key);
899 rbt_remove_node_and_rebalance(tree, node);
917 const ib_rbt_node_t* const_node)
923 rbt_remove_node_and_rebalance(tree, (ib_rbt_node_t*) const_node);
929 return((ib_rbt_node_t*) const_node);
939 const ib_rbt_t* tree,
942 ib_rbt_node_t* lb_node = NULL;
943 ib_rbt_node_t* current = ROOT(tree);
945 while (current != tree->nil) {
946 int result = tree->compare(key, current->value);
950 current = current->right;
952 }
else if (result < 0) {
955 current = current->left;
973 const ib_rbt_t* tree,
976 ib_rbt_node_t* ub_node = NULL;
977 ib_rbt_node_t* current = ROOT(tree);
979 while (current != tree->nil) {
980 int result = tree->compare(key, current->value);
985 current = current->right;
987 }
else if (result < 0) {
989 current = current->left;
1007 const ib_rbt_t* tree,
1008 ib_rbt_bound_t* parent,
1011 ib_rbt_node_t* current = ROOT(tree);
1015 parent->last = NULL;
1017 while (current != tree->nil) {
1019 parent->last = current;
1020 parent->result = tree->compare(key, current->value);
1022 if (parent->result > 0) {
1023 current = current->right;
1024 }
else if (parent->result < 0) {
1025 current = current->left;
1031 return(parent->result);
1042 const ib_rbt_t* tree,
1043 ib_rbt_bound_t* parent,
1045 ib_rbt_compare compare)
1047 ib_rbt_node_t* current = ROOT(tree);
1051 parent->last = NULL;
1053 while (current != tree->nil) {
1055 parent->last = current;
1056 parent->result = compare(key, current->value);
1058 if (parent->result > 0) {
1059 current = current->right;
1060 }
else if (parent->result < 0) {
1061 current = current->left;
1067 return(parent->result);
1077 const ib_rbt_t* tree)
1079 ib_rbt_node_t* first = NULL;
1080 ib_rbt_node_t* current = ROOT(tree);
1082 while (current != tree->nil) {
1084 current = current->left;
1097 const ib_rbt_t* tree)
1099 ib_rbt_node_t* last = NULL;
1100 ib_rbt_node_t* current = ROOT(tree);
1102 while (current != tree->nil) {
1104 current = current->right;
1117 const ib_rbt_t* tree,
1118 const ib_rbt_node_t* current)
1120 return(current ? rbt_find_successor(tree, current) : NULL);
1130 const ib_rbt_t* tree,
1131 const ib_rbt_node_t* current)
1133 return(current ? rbt_find_predecessor(tree, current) : NULL);
1144 rbt_free_node(ROOT(tree), tree->nil);
1147 tree->root->left = tree->root->right = tree->nil;
1158 const ib_rbt_t* src)
1160 ib_rbt_bound_t parent;
1162 const ib_rbt_node_t* src_node =
rbt_first(src);
1164 if (rbt_empty(src) || dst == src) {
1168 for (; src_node; src_node =
rbt_next(src, src_node)) {
1170 if (
rbt_search(dst, &parent, src_node->value) != 0) {
1191 ib_rbt_bound_t parent;
1192 ib_rbt_node_t* src_node;
1193 ulint old_size = rbt_size(dst);
1195 if (rbt_empty(src) || dst == src) {
1199 for (src_node = (ib_rbt_node_t*)
rbt_first(src); src_node; ) {
1200 ib_rbt_node_t* prev = src_node;
1202 src_node = (ib_rbt_node_t*)
rbt_next(src, prev);
1205 if (
rbt_search(dst, &parent, prev->value) != 0) {
1209 rbt_remove_node_and_rebalance(src, prev);
1212 prev->parent = prev->left = prev->right = dst->nil;
1213 rbt_tree_add_child(dst, &parent, prev);
1214 rbt_balance_tree(dst, prev);
1220#if defined(IB_RBT_TESTING)
1224 return(rbt_size(dst) - old_size);
1235 const ib_rbt_t* tree)
1237 if (rbt_count_black_nodes(tree, ROOT(tree)) > 0) {
1238 return(rbt_check_ordering(tree));
1250 const ib_rbt_t* tree,
1251 ib_rbt_print_node print)
1253 rbt_print_subtree(tree, ROOT(tree), print);
UNIV_INTERN void ut_free(void *ptr)
UNIV_INTERN void * ut_malloc(ulint n)
UNIV_INTERN ib_rbt_node_t * rbt_remove_node(ib_rbt_t *tree, const ib_rbt_node_t *node)
UNIV_INTERN void rbt_free(ib_rbt_t *tree)
UNIV_INTERN const ib_rbt_node_t * rbt_lookup(const ib_rbt_t *tree, const void *key)
UNIV_INTERN const ib_rbt_node_t * rbt_first(const ib_rbt_t *tree)
UNIV_INTERN void rbt_clear(ib_rbt_t *tree)
UNIV_INTERN const ib_rbt_node_t * rbt_add_node(ib_rbt_t *tree, ib_rbt_bound_t *parent, const void *value)
UNIV_INTERN ibool rbt_validate(const ib_rbt_t *tree)
UNIV_INTERN const ib_rbt_node_t * rbt_next(const ib_rbt_t *tree, const ib_rbt_node_t *current)
UNIV_INTERN int rbt_search(const ib_rbt_t *tree, ib_rbt_bound_t *parent, const void *key)
UNIV_INTERN ib_rbt_t * rbt_create(size_t sizeof_value, ib_rbt_compare compare)
UNIV_INTERN const ib_rbt_node_t * rbt_last(const ib_rbt_t *tree)
UNIV_INTERN ulint rbt_merge_uniq(ib_rbt_t *dst, const ib_rbt_t *src)
UNIV_INTERN void rbt_print(const ib_rbt_t *tree, ib_rbt_print_node print)
UNIV_INTERN const ib_rbt_node_t * rbt_upper_bound(const ib_rbt_t *tree, const void *key)
UNIV_INTERN ulint rbt_merge_uniq_destructive(ib_rbt_t *dst, ib_rbt_t *src)
UNIV_INTERN int rbt_search_cmp(const ib_rbt_t *tree, ib_rbt_bound_t *parent, const void *key, ib_rbt_compare compare)
UNIV_INTERN const ib_rbt_node_t * rbt_lower_bound(const ib_rbt_t *tree, const void *key)
UNIV_INTERN ibool rbt_delete(ib_rbt_t *tree, const void *key)
UNIV_INTERN const ib_rbt_node_t * rbt_prev(const ib_rbt_t *tree, const ib_rbt_node_t *current)
UNIV_INTERN const ib_rbt_node_t * rbt_insert(ib_rbt_t *tree, const void *key, const void *value)