75 #include <config_auto.h>
78 #include "allheaders.h"
90 static void destroy_helper(
node *n);
91 static void count_helper(
node *n, l_int32 *pcount);
92 static void print_tree_helper(FILE *fp,
node *n, l_int32 keytype,
95 static l_int32 compareKeys(l_int32 keytype,
RB_TYPE left,
RB_TYPE right);
100 static l_int32 node_color(
node *n);
112 static node *maximum_node(
node *root);
119 static void verify_properties(
L_RBTREE *t);
121 #ifndef NO_CONSOLE_IO
122 #define VERIFY_RBTREE 0
139 if (keytype != L_INT_TYPE && keytype != L_UINT_TYPE &&
140 keytype != L_FLOAT_TYPE && keytype)
141 return (
L_RBTREE *)ERROR_PTR(
"invalid keytype", __func__, NULL);
144 t->keytype = keytype;
145 verify_properties(t);
163 return (
RB_TYPE *)ERROR_PTR(
"tree is null\n", __func__, NULL);
165 n = lookup_node(t, key);
166 return n == NULL ? NULL : &n->value;
188 node *n, *inserted_node;
191 L_ERROR(
"tree is null\n", __func__);
195 inserted_node = new_node(key, value, L_RED_NODE, NULL, NULL);
196 if (t->root == NULL) {
197 t->root = inserted_node;
201 int comp_result = compareKeys(t->keytype, key, n->key);
202 if (comp_result == 0) {
204 LEPT_FREE(inserted_node);
206 }
else if (comp_result < 0) {
207 if (n->left == NULL) {
208 n->left = inserted_node;
214 if (n->right == NULL) {
215 n->right = inserted_node;
222 inserted_node->parent = n;
224 insert_case1(t, inserted_node);
225 verify_properties(t);
242 L_ERROR(
"tree is null\n", __func__);
246 n = lookup_node(t, key);
247 if (n == NULL)
return;
248 if (n->left != NULL && n->right != NULL) {
250 node *pred = maximum_node(n->left);
252 n->value = pred->value;
257 child = n->right == NULL ? n->left : n->right;
258 if (node_color(n) == L_BLACK_NODE) {
259 n->color = node_color(child);
262 replace_node(t, n, child);
263 if (n->parent == NULL && child != NULL)
264 child->color = L_BLACK_NODE;
267 verify_properties(t);
287 if (*pt == NULL)
return;
296 destroy_helper(
node *n)
299 destroy_helper(n->left);
300 destroy_helper(n->right);
321 return (
L_RBTREE_NODE *)ERROR_PTR(
"tree is null", __func__, NULL);
322 if (t->root == NULL) {
323 L_INFO(
"tree is empty\n", __func__);
352 return (
L_RBTREE_NODE *)ERROR_PTR(
"n not defined", __func__, NULL);
364 while (n->parent && n->parent->right == n)
387 return (
L_RBTREE_NODE *)ERROR_PTR(
"tree is null", __func__, NULL);
388 if (t->root == NULL) {
389 L_INFO(
"tree is empty\n", __func__);
395 while (n && n->right)
418 return (
L_RBTREE_NODE *)ERROR_PTR(
"n not defined", __func__, NULL);
430 while (n->parent && n->parent->left == n)
450 count_helper(n, &count);
456 count_helper(
node *n, l_int32 *pcount)
463 count_helper(n->left, pcount);
464 count_helper(n->right, pcount);
480 L_ERROR(
"stream not defined\n", __func__);
484 L_ERROR(
"tree not defined\n", __func__);
488 print_tree_helper(fp, t->root, t->keytype, 0);
492 #define INDENT_STEP 4
495 print_tree_helper(FILE *fp,
503 fprintf(fp,
"<empty tree>");
506 if (n->right != NULL) {
507 print_tree_helper(fp, n->right, keytype, indent + INDENT_STEP);
509 for (i = 0; i < indent; i++)
511 if (n->color == L_BLACK_NODE) {
512 if (keytype == L_INT_TYPE)
513 fprintf(fp,
"%lld\n", n->key.itype);
514 else if (keytype == L_UINT_TYPE)
515 fprintf(fp,
"%llx\n", n->key.utype);
516 else if (keytype == L_FLOAT_TYPE)
517 fprintf(fp,
"%f\n", n->key.ftype);
519 if (keytype == L_INT_TYPE)
520 fprintf(fp,
"<%lld>\n", n->key.itype);
521 else if (keytype == L_UINT_TYPE)
522 fprintf(fp,
"<%llx>\n", n->key.utype);
523 else if (keytype == L_FLOAT_TYPE)
524 fprintf(fp,
"<%f>\n", n->key.ftype);
526 if (n->left != NULL) {
527 print_tree_helper(fp, n->left, keytype, indent + INDENT_STEP);
536 compareKeys(l_int32 keytype,
540 if (keytype == L_INT_TYPE) {
541 if (left.itype < right.itype)
543 else if (left.itype > right.itype)
548 }
else if (keytype == L_UINT_TYPE) {
549 if (left.utype < right.utype)
551 else if (left.utype > right.utype)
556 }
else if (keytype == L_FLOAT_TYPE) {
557 if (left.ftype < right.ftype)
559 else if (left.ftype > right.ftype)
565 L_ERROR(
"unknown keytype %d\n", __func__, keytype);
575 if (!n || !n->parent || !n->parent->parent) {
576 L_ERROR(
"root and child of root have no grandparent\n",
"grandparent");
579 return n->parent->parent;
583 if (!n || !n->parent) {
584 L_ERROR(
"root has no sibling\n",
"sibling");
587 if (n == n->parent->left)
588 return n->parent->right;
590 return n->parent->left;
594 if (!n || !n->parent || !n->parent->parent) {
595 L_ERROR(
"root and child of root have no uncle\n",
"uncle");
598 return sibling(n->parent);
601 static l_int32 node_color(
node *n) {
602 return n == NULL ? L_BLACK_NODE : n->color;
610 result->value = value;
611 result->color = node_color;
613 result->right = right;
614 if (left != NULL) left->parent = result;
615 if (right != NULL) right->parent = result;
616 result->parent = NULL;
623 int comp_result = compareKeys(t->keytype, key, n->key);
624 if (comp_result == 0) {
626 }
else if (comp_result < 0) {
637 replace_node(t, n, r);
639 if (r->left != NULL) {
648 replace_node(t, n, L);
650 if (L->right != NULL) {
651 L->right->parent = n;
658 if (oldn->parent == NULL) {
661 if (oldn == oldn->parent->left)
662 oldn->parent->left = newn;
664 oldn->parent->right = newn;
667 newn->parent = oldn->parent;
672 if (n->parent == NULL)
673 n->color = L_BLACK_NODE;
679 if (node_color(n->parent) == L_BLACK_NODE)
686 if (node_color(uncle(n)) == L_RED_NODE) {
687 n->parent->color = L_BLACK_NODE;
688 uncle(n)->color = L_BLACK_NODE;
689 grandparent(n)->color = L_RED_NODE;
690 insert_case1(t, grandparent(n));
697 if (n == n->parent->right && n->parent == grandparent(n)->left) {
698 rotate_left(t, n->parent);
700 }
else if (n == n->parent->left && n->parent == grandparent(n)->right) {
701 rotate_right(t, n->parent);
708 n->parent->color = L_BLACK_NODE;
709 grandparent(n)->color = L_RED_NODE;
710 if (n == n->parent->left && n->parent == grandparent(n)->left) {
711 rotate_right(t, grandparent(n));
712 }
else if (n == n->parent->right && n->parent == grandparent(n)->right) {
713 rotate_left(t, grandparent(n));
715 L_ERROR(
"identity confusion\n",
"insert_case5");
719 static node *maximum_node(
node *n) {
721 L_ERROR(
"n not defined\n",
"maximum_node");
724 while (n->right != NULL) {
731 if (n->parent == NULL)
738 if (node_color(sibling(n)) == L_RED_NODE) {
739 n->parent->color = L_RED_NODE;
740 sibling(n)->color = L_BLACK_NODE;
741 if (n == n->parent->left)
742 rotate_left(t, n->parent);
744 rotate_right(t, n->parent);
750 if (node_color(n->parent) == L_BLACK_NODE &&
751 node_color(sibling(n)) == L_BLACK_NODE &&
752 node_color(sibling(n)->left) == L_BLACK_NODE &&
753 node_color(sibling(n)->right) == L_BLACK_NODE) {
754 sibling(n)->color = L_RED_NODE;
755 delete_case1(t, n->parent);
762 if (node_color(n->parent) == L_RED_NODE &&
763 node_color(sibling(n)) == L_BLACK_NODE &&
764 node_color(sibling(n)->left) == L_BLACK_NODE &&
765 node_color(sibling(n)->right) == L_BLACK_NODE) {
766 sibling(n)->color = L_RED_NODE;
767 n->parent->color = L_BLACK_NODE;
774 if (n == n->parent->left &&
775 node_color(sibling(n)) == L_BLACK_NODE &&
776 node_color(sibling(n)->left) == L_RED_NODE &&
777 node_color(sibling(n)->right) == L_BLACK_NODE) {
778 sibling(n)->color = L_RED_NODE;
779 sibling(n)->left->color = L_BLACK_NODE;
780 rotate_right(t, sibling(n));
781 }
else if (n == n->parent->right &&
782 node_color(sibling(n)) == L_BLACK_NODE &&
783 node_color(sibling(n)->right) == L_RED_NODE &&
784 node_color(sibling(n)->left) == L_BLACK_NODE) {
785 sibling(n)->color = L_RED_NODE;
786 sibling(n)->right->color = L_BLACK_NODE;
787 rotate_left(t, sibling(n));
793 sibling(n)->color = node_color(n->parent);
794 n->parent->color = L_BLACK_NODE;
795 if (n == n->parent->left) {
796 if (node_color(sibling(n)->right) != L_RED_NODE) {
797 L_ERROR(
"right sibling is not RED",
"delete_case6");
800 sibling(n)->right->color = L_BLACK_NODE;
801 rotate_left(t, n->parent);
803 if (node_color(sibling(n)->left) != L_RED_NODE) {
804 L_ERROR(
"left sibling is not RED",
"delete_case6");
807 sibling(n)->left->color = L_BLACK_NODE;
808 rotate_right(t, n->parent);
817 static void verify_property_1(
node *root);
818 static void verify_property_2(
node *root);
819 static void verify_property_4(
node *root);
820 static void verify_property_5(
node *root);
821 static void verify_property_5_helper(
node *n,
int black_count,
822 int* black_count_path);
825 static void verify_properties(
L_RBTREE *t) {
827 verify_property_1(t->root);
828 verify_property_2(t->root);
830 verify_property_4(t->root);
831 verify_property_5(t->root);
836 static void verify_property_1(
node *n) {
837 if (node_color(n) != L_RED_NODE && node_color(n) != L_BLACK_NODE) {
838 L_ERROR(
"color neither RED nor BLACK\n",
"verify_property_1");
841 if (n == NULL)
return;
842 verify_property_1(n->left);
843 verify_property_1(n->right);
846 static void verify_property_2(
node *root) {
847 if (node_color(root) != L_BLACK_NODE)
848 L_ERROR(
"root is not black!\n",
"verify_property_2");
851 static void verify_property_4(
node *n) {
852 if (node_color(n) == L_RED_NODE) {
853 if (node_color(n->left) != L_BLACK_NODE ||
854 node_color(n->right) != L_BLACK_NODE ||
855 node_color(n->parent) != L_BLACK_NODE) {
856 L_ERROR(
"children & parent not all BLACK",
"verify_property_4");
860 if (n == NULL)
return;
861 verify_property_4(n->left);
862 verify_property_4(n->right);
865 static void verify_property_5(
node *root) {
866 int black_count_path = -1;
867 verify_property_5_helper(root, 0, &black_count_path);
870 static void verify_property_5_helper(
node *n,
int black_count,
871 int* path_black_count) {
872 if (node_color(n) == L_BLACK_NODE) {
876 if (*path_black_count == -1) {
877 *path_black_count = black_count;
878 }
else if (*path_black_count != black_count) {
879 L_ERROR(
"incorrect black count",
"verify_property_5_helper");
883 verify_property_5_helper(n->left, black_count, path_black_count);
884 verify_property_5_helper(n->right, black_count, path_black_count);
void l_rbtreeDelete(L_RBTREE *t, RB_TYPE key)
l_rbtreeDelete()
void l_rbtreePrint(FILE *fp, L_RBTREE *t)
l_rbtreePrint()
L_RBTREE_NODE * l_rbtreeGetLast(L_RBTREE *t)
l_rbtreeGetLast()
RB_TYPE * l_rbtreeLookup(L_RBTREE *t, RB_TYPE key)
l_rbtreeLookup()
L_RBTREE_NODE * l_rbtreeGetPrev(L_RBTREE_NODE *n)
l_rbtreeGetPrev()
L_RBTREE * l_rbtreeCreate(l_int32 keytype)
l_rbtreeCreate()
L_RBTREE_NODE * l_rbtreeGetNext(L_RBTREE_NODE *n)
l_rbtreeGetNext()
void l_rbtreeDestroy(L_RBTREE **pt)
l_rbtreeDestroy()
L_RBTREE_NODE * l_rbtreeGetFirst(L_RBTREE *t)
l_rbtreeGetFirst()
l_int32 l_rbtreeGetCount(L_RBTREE *t)
l_rbtreeGetCount()
void l_rbtreeInsert(L_RBTREE *t, RB_TYPE key, RB_TYPE value)
l_rbtreeInsert()