--- /dev/null
+/** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** **\r
+ * This file is part of clib library\r
+ * Copyright (C) 2011 Avinash Dongre ( dongre.avinash@gmail.com )\r
+ *\r
+ * Permission is hereby granted, free of charge, to any person obtaining a copy\r
+ * of this software and associated documentation files (the "Software"), to deal\r
+ * in the Software without restriction, including without limitation the rights\r
+ * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell\r
+ * copies of the Software, and to permit persons to whom the Software is\r
+ * furnished to do so, subject to the following conditions:\r
+ * \r
+ * The above copyright notice and this permission notice shall be included in\r
+ * all copies or substantial portions of the Software.\r
+ * \r
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR\r
+ * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,\r
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE\r
+ * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER\r
+ * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,\r
+ * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN\r
+ * THE SOFTWARE.\r
+ ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** **/\r
+\r
+#include "c_lib.h"\r
+\r
+#include <stdio.h>\r
+#include <string.h>\r
+#include <assert.h>\r
+\r
+#define rb_sentinel &pTree->sentinel\r
+\r
+static void debug_verify_properties(struct clib_rb*);\r
+static void debug_verify_property_1(struct clib_rb*,struct clib_rb_node*);\r
+static void debug_verify_property_2(struct clib_rb*,struct clib_rb_node*);\r
+static int debug_node_color(struct clib_rb*,struct clib_rb_node* n);\r
+static void debug_verify_property_4(struct clib_rb*,struct clib_rb_node*);\r
+static void debug_verify_property_5(struct clib_rb*,struct clib_rb_node*);\r
+static void debug_verify_property_5_helper(struct clib_rb*,struct clib_rb_node*,int,int*);\r
+\r
+\r
+static void\r
+pvt_left_rotate(struct clib_rb *pTree, struct clib_rb_node *x){\r
+ struct clib_rb_node *y;\r
+ y = x->right;\r
+ x->right = y->left;\r
+ if (y->left != rb_sentinel)\r
+ y->left->parent = x;\r
+ if (y != rb_sentinel)\r
+ y->parent = x->parent;\r
+ if (x->parent){\r
+ if (x == x->parent->left)\r
+ x->parent->left = y;\r
+ else\r
+ x->parent->right = y;\r
+ }\r
+ else\r
+ pTree->root = y;\r
+ y->left = x;\r
+ if (x != rb_sentinel)\r
+ x->parent = y;\r
+}\r
+static void\r
+pvt_right_rotate(struct clib_rb *pTree, struct clib_rb_node *x) {\r
+ struct clib_rb_node *y = x->left;\r
+ x->left = y->right;\r
+ if (y->right != rb_sentinel)\r
+ y->right->parent = x;\r
+ if (y != rb_sentinel)\r
+ y->parent = x->parent;\r
+ if (x->parent) {\r
+ if (x == x->parent->right)\r
+ x->parent->right = y;\r
+ else\r
+ x->parent->left = y;\r
+ }\r
+ else\r
+ pTree->root = y;\r
+ y->right = x;\r
+ if (x != rb_sentinel)\r
+ x->parent = y;\r
+}\r
+\r
+struct clib_rb*\r
+new_clib_rb(clib_compare fn_c,clib_destroy fn_ed, clib_destroy fn_vd ){\r
+\r
+ struct clib_rb *pTree = (struct clib_rb*)malloc(sizeof(struct clib_rb));\r
+ if ( pTree == (struct clib_rb*)0 )\r
+ return (struct clib_rb*)0;\r
+\r
+ pTree->compare_fn = fn_c;\r
+ pTree->destruct_k_fn = fn_ed;\r
+ pTree->destruct_v_fn = fn_vd;\r
+ pTree->root = rb_sentinel;\r
+ pTree->sentinel.left = rb_sentinel;\r
+ pTree->sentinel.right = rb_sentinel;\r
+ pTree->sentinel.parent = (struct clib_rb_node*)0 ;\r
+ pTree->sentinel.color = clib_black;\r
+\r
+ return pTree;\r
+}\r
+static void\r
+pvt_rb_insert_fixup( struct clib_rb *pTree, struct clib_rb_node *x ) {\r
+ while (x != pTree->root && x->parent->color == clib_red) {\r
+ if (x->parent == x->parent->parent->left) {\r
+ struct clib_rb_node *y = x->parent->parent->right;\r
+ if (y->color == clib_red) {\r
+ x->parent->color = clib_black;\r
+ y->color = clib_black;\r
+ x->parent->parent->color = clib_red;\r
+ x = x->parent->parent;\r
+ } else {\r
+ if (x == x->parent->right){\r
+ x = x->parent;\r
+ pvt_left_rotate (pTree, x);\r
+ }\r
+ x->parent->color = clib_black;\r
+ x->parent->parent->color = clib_red;\r
+ pvt_right_rotate (pTree, x->parent->parent);\r
+ }\r
+ } else {\r
+ struct clib_rb_node *y = x->parent->parent->left;\r
+ if (y->color == clib_red) {\r
+ x->parent->color = clib_black;\r
+ y->color = clib_black;\r
+ x->parent->parent->color = clib_red;\r
+ x = x->parent->parent;\r
+ } else {\r
+ if (x == x->parent->left) {\r
+ x = x->parent;\r
+ pvt_right_rotate (pTree, x);\r
+ }\r
+ x->parent->color = clib_black;\r
+ x->parent->parent->color = clib_red;\r
+ pvt_left_rotate (pTree, x->parent->parent);\r
+ }\r
+ }\r
+ }\r
+ pTree->root->color = clib_black;\r
+}\r
+struct clib_rb_node* \r
+find_clib_rb (struct clib_rb *pTree, void *key) {\r
+ struct clib_rb_node *x = pTree->root;\r
+\r
+ while (x != rb_sentinel) {\r
+ int c = 0;\r
+ void *cur_key ;\r
+ get_raw_clib_object ( x->key, &cur_key );\r
+ c = pTree->compare_fn (key, cur_key);\r
+ free ( cur_key );\r
+ if (c == 0) {\r
+ break;\r
+ } else {\r
+ x = c < 0 ? x->left : x->right;\r
+ }\r
+ }\r
+ if ( x == rb_sentinel )\r
+ return (struct clib_rb_node*)0 ;\r
+\r
+ return x;\r
+}\r
+\r
+clib_error \r
+insert_clib_rb(struct clib_rb *pTree, void *k, size_t key_size, void *v, size_t value_size) {\r
+\r
+ clib_error rc = CLIB_ERROR_SUCCESS;\r
+ struct clib_rb_node *x;\r
+ struct clib_rb_node *y;\r
+ struct clib_rb_node *z;\r
+\r
+ x = (struct clib_rb_node*)malloc (sizeof(struct clib_rb_node));\r
+ if ( x == (struct clib_rb_node*)0 ) \r
+ return CLIB_ERROR_MEMORY;\r
+\r
+ x->left = rb_sentinel;\r
+ x->right = rb_sentinel;\r
+ x->color = clib_red;\r
+\r
+ x->key = new_clib_object ( k, key_size );\r
+ if ( v ) {\r
+ x->value = new_clib_object ( v, value_size );\r
+ } else {\r
+ x->value = (struct clib_object*)0;\r
+ }\r
+\r
+ y = pTree->root;\r
+ z = (struct clib_rb_node*)0 ;\r
+\r
+ while (y != rb_sentinel) {\r
+ int c = 0;\r
+ void *cur_key;\r
+ void* new_key;\r
+\r
+ get_raw_clib_object ( y->key, &cur_key );\r
+ get_raw_clib_object ( x->key, &new_key );\r
+\r
+ c = (pTree->compare_fn) ( new_key , cur_key);\r
+ free ( cur_key );\r
+ free ( new_key );\r
+ if (c == 0) {\r
+ /* TODO : Delete node here */\r
+ return CLIB_RBTREE_KEY_DUPLICATE;\r
+ }\r
+ z = y;\r
+ if ( c < 0 )\r
+ y = y->left;\r
+ else\r
+ y = y->right;\r
+ } \r
+ x->parent = z;\r
+ if (z) {\r
+ int c = 0;\r
+ void *cur_key;\r
+ void* new_key;\r
+ get_raw_clib_object ( z->key, &cur_key );\r
+ get_raw_clib_object ( x->key, &new_key );\r
+\r
+ c = pTree->compare_fn( new_key, cur_key);\r
+ free ( cur_key );\r
+ free ( new_key );\r
+ if (c < 0) {\r
+ z->left = x;\r
+ } else {\r
+ z->right = x;\r
+ }\r
+ }\r
+ else\r
+ pTree->root = x;\r
+\r
+ pvt_rb_insert_fixup (pTree, x);\r
+\r
+ debug_verify_properties ( pTree);\r
+ return rc;\r
+}\r
+static void\r
+pvt_rb_remove_fixup( struct clib_rb *pTree, struct clib_rb_node *x ) {\r
+ while (x != pTree->root && x->color == clib_black) {\r
+ if (x == x->parent->left) {\r
+ struct clib_rb_node *w = x->parent->right;\r
+ if (w->color == clib_red) {\r
+ w->color = clib_black;\r
+ x->parent->color = clib_red;\r
+ pvt_left_rotate (pTree, x->parent);\r
+ w = x->parent->right;\r
+ }\r
+ if (w->left->color == clib_black && w->right->color == clib_black) {\r
+ w->color = clib_red;\r
+ x = x->parent;\r
+ } else {\r
+ if (w->right->color == clib_black) {\r
+ w->left->color = clib_black;\r
+ w->color = clib_red;\r
+ pvt_right_rotate (pTree, w);\r
+ w = x->parent->right;\r
+ }\r
+ w->color = x->parent->color;\r
+ x->parent->color = clib_black;\r
+ w->right->color = clib_black;\r
+ pvt_left_rotate (pTree, x->parent);\r
+ x = pTree->root;\r
+ }\r
+ } else {\r
+ struct clib_rb_node *w = x->parent->left;\r
+ if (w->color == clib_red) {\r
+ w->color = clib_black;\r
+ x->parent->color = clib_red;\r
+ pvt_right_rotate (pTree, x->parent);\r
+ w = x->parent->left;\r
+ }\r
+ if (w->right->color == clib_black && w->left->color == clib_black) {\r
+ w->color = clib_red;\r
+ x = x->parent;\r
+ } else {\r
+ if (w->left->color == clib_black) {\r
+ w->right->color = clib_black;\r
+ w->color = clib_red;\r
+ pvt_left_rotate (pTree, w);\r
+ w = x->parent->left;\r
+ }\r
+ w->color = x->parent->color;\r
+ x->parent->color = clib_black;\r
+ w->left->color = clib_black;\r
+ pvt_right_rotate (pTree, x->parent);\r
+ x = pTree->root;\r
+ }\r
+ }\r
+ }\r
+ x->color = clib_black;\r
+}\r
+\r
+static struct clib_rb_node* \r
+pvt_remove_clib_rb(struct clib_rb *pTree, struct clib_rb_node *z ) {\r
+ struct clib_rb_node *x = (struct clib_rb_node*)0 ;\r
+ struct clib_rb_node *y = (struct clib_rb_node*)0 ;\r
+\r
+ if (z->left == rb_sentinel || z->right == rb_sentinel)\r
+ y = z;\r
+ else {\r
+ y = z->right;\r
+ while (y->left != rb_sentinel)\r
+ y = y->left;\r
+ }\r
+ if (y->left != rb_sentinel)\r
+ x = y->left;\r
+ else\r
+ x = y->right;\r
+\r
+ x->parent = y->parent;\r
+ if (y->parent)\r
+ {\r
+ if (y == y->parent->left)\r
+ y->parent->left = x;\r
+ else\r
+ y->parent->right = x;\r
+ }\r
+ else\r
+ pTree->root = x;\r
+ if (y != z) {\r
+ struct clib_object* tmp;\r
+ tmp = z->key;\r
+ z->key = y->key;\r
+ y->key = tmp;\r
+\r
+ tmp = z->value;\r
+ z->value = y->value;\r
+ y->value = tmp;\r
+ }\r
+ if (y->color == clib_black)\r
+ pvt_rb_remove_fixup (pTree, x);\r
+\r
+ debug_verify_properties ( pTree);\r
+ return y;\r
+}\r
+\r
+struct clib_rb_node*\r
+remove_clib_rb (struct clib_rb *pTree, void *key) {\r
+ struct clib_rb_node *z = (struct clib_rb_node*)0 ;\r
+\r
+ z = pTree->root;\r
+ while (z != rb_sentinel) {\r
+ int c = 0;\r
+ void *cur_key;\r
+ get_raw_clib_object ( z->key, &cur_key );\r
+ c = pTree->compare_fn (key, cur_key);\r
+ free ( cur_key );\r
+ if ( c == 0) {\r
+ break;\r
+ }\r
+ else {\r
+ z = ( c < 0) ? z->left : z->right;\r
+ }\r
+ }\r
+ if (z == rb_sentinel)\r
+ return (struct clib_rb_node*)0 ;\r
+ return pvt_remove_clib_rb(pTree, z );\r
+}\r
+static void\r
+pvt_delete_clib_rb_node (struct clib_rb *pTree, struct clib_rb_node *x ) {\r
+\r
+ void *key;\r
+ void *value;\r
+\r
+ if ( pTree->destruct_k_fn ) {\r
+ get_raw_clib_object ( x->key, &key );\r
+ pTree->destruct_k_fn ( key );\r
+ }\r
+ delete_clib_object( x->key );\r
+\r
+ if ( x->value ) {\r
+ if ( pTree->destruct_v_fn ) {\r
+ get_raw_clib_object ( x->value, &value);\r
+ pTree->destruct_v_fn ( value );\r
+ }\r
+ delete_clib_object( x->value );\r
+ }\r
+}\r
+\r
+clib_error \r
+delete_clib_rb(struct clib_rb *pTree) {\r
+\r
+ clib_error rc = CLIB_ERROR_SUCCESS;\r
+ struct clib_rb_node *z = pTree->root;\r
+\r
+ while (z != rb_sentinel) {\r
+ if (z->left != rb_sentinel)\r
+ z = z->left;\r
+ else if (z->right != rb_sentinel)\r
+ z = z->right;\r
+ else {\r
+ pvt_delete_clib_rb_node ( pTree, z );\r
+ if (z->parent) {\r
+ z = z->parent;\r
+ if (z->left != rb_sentinel){\r
+ free ( z->left );\r
+ z->left = rb_sentinel;\r
+ }else if (z->right != rb_sentinel){\r
+ free ( z->right );\r
+ z->right = rb_sentinel;\r
+ }\r
+ } else {\r
+ free ( z );\r
+ z = rb_sentinel;\r
+ }\r
+ }\r
+ }\r
+ free ( pTree );\r
+ return rc;\r
+}\r
+struct clib_rb_node *\r
+minimum_clib_rb( struct clib_rb *pTree, struct clib_rb_node *x ) {\r
+ while ( x->left != rb_sentinel)\r
+ x = x->left;\r
+ return x;\r
+}\r
+\r
+struct clib_rb_node *\r
+maximum_clib_rb( struct clib_rb *pTree, struct clib_rb_node *x ) {\r
+ while ( x->right != rb_sentinel)\r
+ x = x->right;\r
+ return x;\r
+}\r
+\r
+\r
+clib_bool \r
+empty_clib_rb(struct clib_rb *pTree) {\r
+ if ( pTree->root != rb_sentinel )\r
+ return clib_true;\r
+ return clib_false;\r
+}\r
+struct clib_rb_node*\r
+tree_successor(struct clib_rb *pTree, struct clib_rb_node *x) {\r
+ struct clib_rb_node *y = (struct clib_rb_node*)0;\r
+ if ( x->right != rb_sentinel)\r
+ return minimum_clib_rb( pTree, x->right);\r
+ \r
+ if ( x == maximum_clib_rb(pTree,pTree->root)) \r
+ return (struct clib_rb_node*)0;\r
+\r
+ y = x->parent;\r
+ while ( y != rb_sentinel && x == y->right ){\r
+ x = y;\r
+ y = y->parent;\r
+ }\r
+ return y;\r
+}\r
+\r
+\r
+void debug_verify_properties(struct clib_rb* t) {\r
+ debug_verify_property_1(t,t->root);\r
+ debug_verify_property_2(t,t->root);\r
+ debug_verify_property_4(t,t->root);\r
+ debug_verify_property_5(t,t->root);\r
+}\r
+\r
+void debug_verify_property_1(struct clib_rb *pTree,struct clib_rb_node* n) {\r
+ assert(debug_node_color(pTree,n) == clib_red || debug_node_color(pTree,n) == clib_black);\r
+ if (n == rb_sentinel) return;\r
+ debug_verify_property_1(pTree,n->left);\r
+ debug_verify_property_1(pTree,n->right);\r
+}\r
+\r
+void debug_verify_property_2(struct clib_rb *pTree,struct clib_rb_node* root) {\r
+ assert(debug_node_color(pTree,root) == clib_black);\r
+}\r
+\r
+int debug_node_color(struct clib_rb *pTree,struct clib_rb_node* n) {\r
+ return n == rb_sentinel ? clib_black : n->color;\r
+}\r
+\r
+void debug_verify_property_4(struct clib_rb *pTree,struct clib_rb_node* n) {\r
+ if (debug_node_color(pTree,n) == clib_red) {\r
+ assert (debug_node_color(pTree,n->left) == clib_black);\r
+ assert (debug_node_color(pTree,n->right) == clib_black);\r
+ assert (debug_node_color(pTree,n->parent) == clib_black);\r
+ }\r
+ if (n == rb_sentinel) return;\r
+ debug_verify_property_4(pTree,n->left);\r
+ debug_verify_property_4(pTree,n->right);\r
+}\r
+\r
+void debug_verify_property_5(struct clib_rb *pTree,struct clib_rb_node* root) {\r
+ int black_count_path = -1;\r
+ debug_verify_property_5_helper(pTree,root, 0, &black_count_path);\r
+}\r
+\r
+void debug_verify_property_5_helper(struct clib_rb *pTree,struct clib_rb_node* n, int black_count, int* path_black_count) {\r
+ if (debug_node_color(pTree,n) == clib_black) {\r
+ black_count++;\r
+ }\r
+ if (n == rb_sentinel) {\r
+ if (*path_black_count == -1) {\r
+ *path_black_count = black_count;\r
+ } else {\r
+ assert (black_count == *path_black_count);\r
+ }\r
+ return;\r
+ }\r
+ debug_verify_property_5_helper(pTree,n->left, black_count, path_black_count);\r
+ debug_verify_property_5_helper(pTree,n->right, black_count, path_black_count);\r
+}\r
+\r
projects / ccan / blobdiff