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)
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);
93 if (prev && tree->compare(prev->value, node->value) >= 0) {
109 rbt_count_black_nodes(
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;
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;
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;
236 if (last == tree->root || parent->result < 0) {
240 ut_a(parent->result != 0);
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);
299 node->color = IB_RBT_RED;
301 while (node != ROOT(tree) && parent->color == IB_RBT_RED) {
304 if (parent == grand_parent->left) {
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);
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;
395 while (next->left != nil) {
405 while (parent != tree->root && next == parent->right) {
407 parent = next->parent;
410 next = (parent == tree->root) ? NULL : parent;
421 rbt_find_predecessor(
435 while (prev->right != nil) {
445 while (parent != tree->root && prev == parent->left) {
447 parent = prev->parent;
450 prev = (parent == tree->root) ? NULL : parent;
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;
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;
520 if (node->left != nil && node->right != nil) {
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;
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);
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);
674 rbt_remove_node_and_rebalance(
683 if (node->color == IB_RBT_BLACK) {
686 ROOT(tree)->color = IB_RBT_RED;
688 while (child && child->color == IB_RBT_BLACK) {
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)
766 memset(tree, 0,
sizeof(*tree));
768 tree->sizeof_value = sizeof_value;
772 memset(node, 0,
sizeof(*node));
774 node->color = IB_RBT_BLACK;
775 node->parent = node->left = node->right = 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;
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);
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)
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;
899 rbt_remove_node_and_rebalance(tree, node);
923 rbt_remove_node_and_rebalance(tree, (
ib_rbt_node_t*) const_node);
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;
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;
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);
1045 ib_rbt_compare compare)
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);
1082 while (current != tree->nil) {
1084 current = current->left;
1102 while (current != tree->nil) {
1104 current = current->right;
1120 return(current ? rbt_find_successor(tree, current) : NULL);
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;
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) {
1193 ulint old_size = rbt_size(dst);
1195 if (rbt_empty(src) || dst == src) {
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);
1237 if (rbt_count_black_nodes(tree, ROOT(tree)) > 0) {
1238 return(rbt_check_ordering(tree));
1251 ib_rbt_print_node print)
1253 rbt_print_subtree(tree, ROOT(tree), print);