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 PROCNAME(
"l_rbtreeCreate");
141 if (keytype != L_INT_TYPE && keytype != L_UINT_TYPE &&
142 keytype != L_FLOAT_TYPE && keytype)
143 return (
L_RBTREE *)ERROR_PTR(
"invalid keytype", procName, NULL);
146 t->keytype = keytype;
147 verify_properties(t);
164 PROCNAME(
"l_rbtreeLookup");
167 return (
RB_TYPE *)ERROR_PTR(
"tree is null\n", procName, NULL);
169 n = lookup_node(t, key);
170 return n == NULL ? NULL : &n->value;
192 node *n, *inserted_node;
194 PROCNAME(
"l_rbtreeInsert");
197 L_ERROR(
"tree is null\n", procName);
201 inserted_node = new_node(key, value, L_RED_NODE, NULL, NULL);
202 if (t->root == NULL) {
203 t->root = inserted_node;
207 int comp_result = compareKeys(t->keytype, key, n->key);
208 if (comp_result == 0) {
210 LEPT_FREE(inserted_node);
212 }
else if (comp_result < 0) {
213 if (n->left == NULL) {
214 n->left = inserted_node;
220 if (n->right == NULL) {
221 n->right = inserted_node;
228 inserted_node->parent = n;
230 insert_case1(t, inserted_node);
231 verify_properties(t);
247 PROCNAME(
"l_rbtreeDelete");
250 L_ERROR(
"tree is null\n", procName);
254 n = lookup_node(t, key);
255 if (n == NULL)
return;
256 if (n->left != NULL && n->right != NULL) {
258 node *pred = maximum_node(n->left);
260 n->value = pred->value;
265 child = n->right == NULL ? n->left : n->right;
266 if (node_color(n) == L_BLACK_NODE) {
267 n->color = node_color(child);
270 replace_node(t, n, child);
271 if (n->parent == NULL && child != NULL)
272 child->color = L_BLACK_NODE;
275 verify_properties(t);
295 if (*pt == NULL)
return;
304 destroy_helper(
node *n)
307 destroy_helper(n->left);
308 destroy_helper(n->right);
328 PROCNAME(
"l_rbtreeGetFirst");
331 return (
L_RBTREE_NODE *)ERROR_PTR(
"tree is null", procName, NULL);
332 if (t->root == NULL) {
333 L_INFO(
"tree is empty\n", procName);
361 PROCNAME(
"l_rbtreeGetNext");
364 return (
L_RBTREE_NODE *)ERROR_PTR(
"n not defined", procName, NULL);
376 while (n->parent && n->parent->right == n)
398 PROCNAME(
"l_rbtreeGetLast");
401 return (
L_RBTREE_NODE *)ERROR_PTR(
"tree is null", procName, NULL);
402 if (t->root == NULL) {
403 L_INFO(
"tree is empty\n", procName);
409 while (n && n->right)
431 PROCNAME(
"l_rbtreeGetPrev");
434 return (
L_RBTREE_NODE *)ERROR_PTR(
"n not defined", procName, NULL);
446 while (n->parent && n->parent->left == n)
466 count_helper(n, &count);
472 count_helper(
node *n, l_int32 *pcount)
479 count_helper(n->left, pcount);
480 count_helper(n->right, pcount);
495 PROCNAME(
"l_rbtreePrint");
497 L_ERROR(
"stream not defined\n", procName);
501 L_ERROR(
"tree not defined\n", procName);
505 print_tree_helper(fp, t->root, t->keytype, 0);
509 #define INDENT_STEP 4
512 print_tree_helper(FILE *fp,
520 fprintf(fp,
"<empty tree>");
523 if (n->right != NULL) {
524 print_tree_helper(fp, n->right, keytype, indent + INDENT_STEP);
526 for (i = 0; i < indent; i++)
528 if (n->color == L_BLACK_NODE) {
529 if (keytype == L_INT_TYPE)
530 fprintf(fp,
"%lld\n", n->key.itype);
531 else if (keytype == L_UINT_TYPE)
532 fprintf(fp,
"%llx\n", n->key.utype);
533 else if (keytype == L_FLOAT_TYPE)
534 fprintf(fp,
"%f\n", n->key.ftype);
536 if (keytype == L_INT_TYPE)
537 fprintf(fp,
"<%lld>\n", n->key.itype);
538 else if (keytype == L_UINT_TYPE)
539 fprintf(fp,
"<%llx>\n", n->key.utype);
540 else if (keytype == L_FLOAT_TYPE)
541 fprintf(fp,
"<%f>\n", n->key.ftype);
543 if (n->left != NULL) {
544 print_tree_helper(fp, n->left, keytype, indent + INDENT_STEP);
553 compareKeys(l_int32 keytype,
557 static char procName[] =
"compareKeys";
559 if (keytype == L_INT_TYPE) {
560 if (left.itype < right.itype)
562 else if (left.itype > right.itype)
567 }
else if (keytype == L_UINT_TYPE) {
568 if (left.utype < right.utype)
570 else if (left.utype > right.utype)
575 }
else if (keytype == L_FLOAT_TYPE) {
576 if (left.ftype < right.ftype)
578 else if (left.ftype > right.ftype)
584 L_ERROR(
"unknown keytype %d\n", procName, keytype);
594 if (!n || !n->parent || !n->parent->parent) {
595 L_ERROR(
"root and child of root have no grandparent\n",
"grandparent");
598 return n->parent->parent;
602 if (!n || !n->parent) {
603 L_ERROR(
"root has no sibling\n",
"sibling");
606 if (n == n->parent->left)
607 return n->parent->right;
609 return n->parent->left;
613 if (!n || !n->parent || !n->parent->parent) {
614 L_ERROR(
"root and child of root have no uncle\n",
"uncle");
617 return sibling(n->parent);
620 static l_int32 node_color(
node *n) {
621 return n == NULL ? L_BLACK_NODE : n->color;
629 result->value = value;
630 result->color = node_color;
632 result->right = right;
633 if (left != NULL) left->parent = result;
634 if (right != NULL) right->parent = result;
635 result->parent = NULL;
642 int comp_result = compareKeys(t->keytype, key, n->key);
643 if (comp_result == 0) {
645 }
else if (comp_result < 0) {
656 replace_node(t, n, r);
658 if (r->left != NULL) {
667 replace_node(t, n, L);
669 if (L->right != NULL) {
670 L->right->parent = n;
677 if (oldn->parent == NULL) {
680 if (oldn == oldn->parent->left)
681 oldn->parent->left = newn;
683 oldn->parent->right = newn;
686 newn->parent = oldn->parent;
691 if (n->parent == NULL)
692 n->color = L_BLACK_NODE;
698 if (node_color(n->parent) == L_BLACK_NODE)
705 if (node_color(uncle(n)) == L_RED_NODE) {
706 n->parent->color = L_BLACK_NODE;
707 uncle(n)->color = L_BLACK_NODE;
708 grandparent(n)->color = L_RED_NODE;
709 insert_case1(t, grandparent(n));
716 if (n == n->parent->right && n->parent == grandparent(n)->left) {
717 rotate_left(t, n->parent);
719 }
else if (n == n->parent->left && n->parent == grandparent(n)->right) {
720 rotate_right(t, n->parent);
727 n->parent->color = L_BLACK_NODE;
728 grandparent(n)->color = L_RED_NODE;
729 if (n == n->parent->left && n->parent == grandparent(n)->left) {
730 rotate_right(t, grandparent(n));
731 }
else if (n == n->parent->right && n->parent == grandparent(n)->right) {
732 rotate_left(t, grandparent(n));
734 L_ERROR(
"identity confusion\n",
"insert_case5");
738 static node *maximum_node(
node *n) {
740 L_ERROR(
"n not defined\n",
"maximum_node");
743 while (n->right != NULL) {
750 if (n->parent == NULL)
757 if (node_color(sibling(n)) == L_RED_NODE) {
758 n->parent->color = L_RED_NODE;
759 sibling(n)->color = L_BLACK_NODE;
760 if (n == n->parent->left)
761 rotate_left(t, n->parent);
763 rotate_right(t, n->parent);
769 if (node_color(n->parent) == L_BLACK_NODE &&
770 node_color(sibling(n)) == L_BLACK_NODE &&
771 node_color(sibling(n)->left) == L_BLACK_NODE &&
772 node_color(sibling(n)->right) == L_BLACK_NODE) {
773 sibling(n)->color = L_RED_NODE;
774 delete_case1(t, n->parent);
781 if (node_color(n->parent) == L_RED_NODE &&
782 node_color(sibling(n)) == L_BLACK_NODE &&
783 node_color(sibling(n)->left) == L_BLACK_NODE &&
784 node_color(sibling(n)->right) == L_BLACK_NODE) {
785 sibling(n)->color = L_RED_NODE;
786 n->parent->color = L_BLACK_NODE;
793 if (n == n->parent->left &&
794 node_color(sibling(n)) == L_BLACK_NODE &&
795 node_color(sibling(n)->left) == L_RED_NODE &&
796 node_color(sibling(n)->right) == L_BLACK_NODE) {
797 sibling(n)->color = L_RED_NODE;
798 sibling(n)->left->color = L_BLACK_NODE;
799 rotate_right(t, sibling(n));
800 }
else if (n == n->parent->right &&
801 node_color(sibling(n)) == L_BLACK_NODE &&
802 node_color(sibling(n)->right) == L_RED_NODE &&
803 node_color(sibling(n)->left) == L_BLACK_NODE) {
804 sibling(n)->color = L_RED_NODE;
805 sibling(n)->right->color = L_BLACK_NODE;
806 rotate_left(t, sibling(n));
812 sibling(n)->color = node_color(n->parent);
813 n->parent->color = L_BLACK_NODE;
814 if (n == n->parent->left) {
815 if (node_color(sibling(n)->right) != L_RED_NODE) {
816 L_ERROR(
"right sibling is not RED",
"delete_case6");
819 sibling(n)->right->color = L_BLACK_NODE;
820 rotate_left(t, n->parent);
822 if (node_color(sibling(n)->left) != L_RED_NODE) {
823 L_ERROR(
"left sibling is not RED",
"delete_case6");
826 sibling(n)->left->color = L_BLACK_NODE;
827 rotate_right(t, n->parent);
836 static void verify_property_1(
node *root);
837 static void verify_property_2(
node *root);
838 static void verify_property_4(
node *root);
839 static void verify_property_5(
node *root);
840 static void verify_property_5_helper(
node *n,
int black_count,
841 int* black_count_path);
844 static void verify_properties(
L_RBTREE *t) {
846 verify_property_1(t->root);
847 verify_property_2(t->root);
849 verify_property_4(t->root);
850 verify_property_5(t->root);
855 static void verify_property_1(
node *n) {
856 if (node_color(n) != L_RED_NODE && node_color(n) != L_BLACK_NODE) {
857 L_ERROR(
"color neither RED nor BLACK\n",
"verify_property_1");
860 if (n == NULL)
return;
861 verify_property_1(n->left);
862 verify_property_1(n->right);
865 static void verify_property_2(
node *root) {
866 if (node_color(root) != L_BLACK_NODE)
867 L_ERROR(
"root is not black!\n",
"verify_property_2");
870 static void verify_property_4(
node *n) {
871 if (node_color(n) == L_RED_NODE) {
872 if (node_color(n->left) != L_BLACK_NODE ||
873 node_color(n->right) != L_BLACK_NODE ||
874 node_color(n->parent) != L_BLACK_NODE) {
875 L_ERROR(
"children & parent not all BLACK",
"verify_property_4");
879 if (n == NULL)
return;
880 verify_property_4(n->left);
881 verify_property_4(n->right);
884 static void verify_property_5(
node *root) {
885 int black_count_path = -1;
886 verify_property_5_helper(root, 0, &black_count_path);
889 static void verify_property_5_helper(
node *n,
int black_count,
890 int* path_black_count) {
891 if (node_color(n) == L_BLACK_NODE) {
895 if (*path_black_count == -1) {
896 *path_black_count = black_count;
897 }
else if (*path_black_count != black_count) {
898 L_ERROR(
"incorrect black count",
"verify_property_5_helper");
902 verify_property_5_helper(n->left, black_count, path_black_count);
903 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()