--- /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 <stdlib.h>\r
+#include <string.h>\r
+#include <assert.h>\r
+\r
+#define BLACK 0\r
+#define RED 1\r
+\r
+#define rb_sentinel &tree->sentinel \r
+\r
+static void*\r
+ get_key ( struct clib_rb* tree, struct clib_rb_node* node) {\r
+ if ( node ) \r
+ return node->raw_data.key;\r
+ return (void*)0;\r
+ }\r
+\r
+static struct clib_rb_node*\r
+ get_left (struct clib_rb* tree, struct clib_rb_node* node ) {\r
+ if ( node->left != rb_sentinel && node->left != (struct clib_rb_node*)0 )\r
+ return node->left;\r
+ return (struct clib_rb_node*)0 ;\r
+ }\r
+static struct clib_rb_node*\r
+ get_right (struct clib_rb* tree, struct clib_rb_node* node ){\r
+ if ( node->right != rb_sentinel && node->right != (struct clib_rb_node*)0 )\r
+ return node->right;\r
+ return (struct clib_rb_node*)0 ;\r
+ }\r
+static struct clib_rb_node*\r
+ get_parent ( struct clib_rb* tree,struct clib_rb_node* node ) {\r
+ if ( node->parent != rb_sentinel && node->parent != (struct clib_rb_node*)0 )\r
+ return node->parent;\r
+ return (struct clib_rb_node*)0 ;\r
+ }\r
+\r
+int \r
+compare_rb_e ( void* l, void* r ) {\r
+\r
+ int left = 0;\r
+ int right = 0;\r
+\r
+ if ( l ) left = *(int*)l;\r
+ if ( r ) right = *(int*)r;\r
+\r
+ if ( left < right ) return -1;\r
+ if ( left == right ) return 0;\r
+\r
+ return 1;\r
+}\r
+\r
+void \r
+free_rb_e ( void* p ) {\r
+ if ( p ) {\r
+ free ( p );\r
+ }\r
+}\r
+\r
+typedef struct test_data_tree {\r
+ int element;\r
+ int left;\r
+ int right;\r
+ int parent;\r
+ int color;\r
+} TS;\r
+\r
+\r
+static struct clib_rb_node*\r
+pvt_find_clib_rb ( struct clib_rb* tree, clib_compare fn_c, void *key ) {\r
+ struct clib_rb_node* node = tree->root;\r
+ void* current_key = (void*)0;\r
+ int compare_result = 0;\r
+\r
+ current_key = (void*)malloc ( tree->size_of_key);\r
+ memcpy ( current_key, key, tree->size_of_key);\r
+\r
+ compare_result = (fn_c)(current_key, node->raw_data.key);\r
+ while ((node != rb_sentinel) && (compare_result = (fn_c)(current_key, node->raw_data.key)) != 0 ){\r
+ if ( compare_result < 0 ) {\r
+ node = node->left;\r
+ } else {\r
+ node = node->right;\r
+ }\r
+ } \r
+ free ( current_key );\r
+ return node;\r
+}\r
+struct clib_rb_node*\r
+find(struct clib_rb* tree, void *key ) {\r
+ return pvt_find_clib_rb ( tree, tree->compare_fn, key );\r
+}\r
+\r
+static void update_values ( void* v, int *l, int *r, int *p , int *e, struct clib_rb* tree ) {\r
+ struct clib_rb_node *x;\r
+ if ( get_key(tree,v)) \r
+ *e = *(int*)get_key (tree,v);\r
+ x = get_left(tree,v);\r
+ if ( x )\r
+ *l = *(int*)get_key(tree,x);\r
+ x = get_right(tree,v);\r
+ if (x) \r
+ *r = *(int*)get_key(tree,x);\r
+ x = get_parent ( tree, v );\r
+ if (x) \r
+ *p = *(int*)get_key(tree,x);\r
+}\r
+\r
+static void \r
+test_each_elements(int l,int r, int p, int e,void* v, TS ts[], int i, \r
+ struct clib_rb* tree) {\r
+ assert ( ts[i].element == e);\r
+ if (ts[i].left != 0 ) \r
+ assert ( ts[i].left == l);\r
+ else\r
+ assert ((void* )0 == (void* )get_key(tree,get_left(tree,v)));\r
+ if ( ts[i].right != 0 ) \r
+ assert (ts[i].right == r);\r
+ else\r
+ assert ((void* )0 == (void* )get_key(tree,get_right(tree,v)));\r
+ if (ts[i].parent != 0 ) \r
+ assert (ts[i].parent == p);\r
+ else\r
+ assert ((void* )0 == (void* )get_key(tree,get_parent(tree,v)));\r
+}\r
+\r
+static void\r
+test_all_elements(struct clib_rb* tree, TS ts[], int size) {\r
+ int i = 0;\r
+ for ( i = 0; i < size; i++) {\r
+ void* v = (void*)0;\r
+ int l,r,p,e;\r
+ v = find ( tree, &ts[i].element);\r
+ update_values( v, &l,&r,&p,&e, tree);\r
+ test_each_elements(l,r,p,e,v, ts, i, tree);\r
+ }\r
+}\r
+\r
+static struct clib_rb* \r
+create_tree(TS ts[], int size) {\r
+ int i = 0;\r
+ struct clib_rb* tree = new_clib_rb( compare_rb_e,free_rb_e, (void*)0, sizeof(int),0);\r
+ for ( i = 0; i < size; i++) {\r
+ insert_clib_rb( tree, &(ts[i].element) ,(void*)0);\r
+ }\r
+ return tree;\r
+}\r
+\r
+\r
+void \r
+test_clib_rb() {\r
+ int size;\r
+ int size_after_delete;\r
+ int i = 0;\r
+ struct clib_rb* tree;\r
+ struct clib_rb_node* node;\r
+\r
+ TS ts[] = {\r
+ {15,6,18,0,BLACK},{6,3,9,15,RED},{18,17,20,15,BLACK},\r
+ {3,2,4,6,BLACK},{7,0,0,9,RED},{17,0,0,18,RED},\r
+ {20,0,0,18,RED},{2,0,0,3,RED},{4,0,0,3,RED},{13,0,0,9,RED}, \r
+ {9,7,13,6,BLACK}\r
+ };\r
+ TS ts_delete_leaf_13[] = {\r
+ {15,6,18,0,BLACK},{6,3,9,15,RED},{18,17,20,15,BLACK},\r
+ {3,2,4,6,BLACK},{7,0,0,9,RED},{17,0,0,18,RED},\r
+ {20,0,0,18,RED},{2,0,0,3,RED},{4,0,0,3,RED},\r
+ {9,7,0,6,BLACK}\r
+ }; \r
+ TS ts_delete_9[] = {\r
+ {15,6,18,0,BLACK},{6,3,7,15,RED},{18,17,20,15,BLACK},\r
+ {3,2,4,6,RED},{7,0,0,6,RED},{17,0,0,18,RED},\r
+ {20,0,0,18,RED},{2,0,0,3,RED},{4,0,0,3,RED}\r
+ }; \r
+ TS ts_delete_15[] = {\r
+ {6,3,7,17,RED},{18,0,20,17,BLACK},\r
+ {3,2,4,6,RED},{7,0,0,6,RED},{17,6,18,0,RED},\r
+ {20,0,0,18,RED},{2,0,0,3,RED},{4,0,0,3,RED}\r
+ }; \r
+ TS ts_insert_1[] = {\r
+ {6,3,17,0,BLACK},{18,0,20,17,BLACK},\r
+ {3,2,4,6,RED},{7,0,0,17,RED},{17,7,18,6,RED},\r
+ {20,0,0,18,RED},{2,1,0,3,BLACK},{4,0,0,3,BLACK},\r
+ {1,0,0,2,RED}\r
+ }; \r
+\r
+\r
+ size = (sizeof(ts)/sizeof(TS));\r
+ tree = create_tree(ts,size);\r
+ test_all_elements(tree, ts, size); \r
+ { \r
+ i = 13; \r
+ size = (sizeof(ts)/sizeof(TS));\r
+ size_after_delete = (sizeof(ts_delete_leaf_13)/sizeof(TS));\r
+ node = remove_clib_rb( tree, &i);\r
+ if ( node != (struct clib_rb_node*)0 ) {\r
+ free ( node->raw_data.key);\r
+ free ( node);\r
+ }\r
+ test_all_elements(tree, ts_delete_leaf_13, size_after_delete);\r
+ }\r
+ {\r
+ i = 9; \r
+ size_after_delete = (sizeof(ts_delete_9)/sizeof(TS));\r
+ node = remove_clib_rb( tree, &i);\r
+ if ( node != (struct clib_rb_node*)0 ) {\r
+ free ( node->raw_data.key);\r
+ free ( node);\r
+ }\r
+ test_all_elements(tree, ts_delete_9, size_after_delete);\r
+ }\r
+ {\r
+ i = 15; \r
+ size_after_delete = (sizeof(ts_delete_15)/sizeof(TS));\r
+ node = remove_clib_rb( tree, &i);\r
+ if ( node != (struct clib_rb_node*)0 ) {\r
+ free ( node->raw_data.key);\r
+ free ( node);\r
+ }\r
+ test_all_elements(tree, ts_delete_15, size_after_delete);\r
+ }\r
+ {\r
+ int i = 1;\r
+ insert_clib_rb( tree, &i, (void*)0);\r
+ size_after_delete = (sizeof(ts_insert_1)/sizeof(TS));\r
+ test_all_elements(tree, ts_insert_1, size_after_delete);\r
+ }\r
+ {\r
+ delete_clib_rb(tree);\r
+ }\r
+}*/\r
projects / ccan / blobdiff