git.ozlabs.org Git - ccan/blob - junkcode/dongre.avinash@gmail.com-clibutils/test/t_c_rb.c

   1 /** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** **\r
   2  *  This file is part of clib library\r
   3  *  Copyright (C) 2011 Avinash Dongre ( dongre.avinash@gmail.com )\r
   4  *\r
   5  *  Permission is hereby granted, free of charge, to any person obtaining a copy\r
   6  *  of this software and associated documentation files (the "Software"), to deal\r
   7  *  in the Software without restriction, including without limitation the rights\r
   8  *  to use, copy, modify, merge, publish, distribute, sublicense, and/or sell\r
   9  *  copies of the Software, and to permit persons to whom the Software is\r
  10  *  furnished to do so, subject to the following conditions:\r
  11  * \r
  12  *  The above copyright notice and this permission notice shall be included in\r
  13  *  all copies or substantial portions of the Software.\r
  14  * \r
  15  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR\r
  16  *  IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,\r
  17  *  FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE\r
  18  *  AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER\r
  19  *  LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,\r
  20  *  OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN\r
  21  *  THE SOFTWARE.\r
  22  ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** **/\r
  23 \r
  24 #include "c_lib.h"\r
  25 \r
  26 /*#include <stdio.h>\r
  27 #include <stdlib.h>\r
  28 #include <string.h>\r
  29 #include <assert.h>\r
  30 \r
  31 #define BLACK 0\r
  32 #define RED   1\r
  33 \r
  34 #define rb_sentinel &tree->sentinel \r
  35 \r
  36 static void*\r
  37     get_key ( struct clib_rb* tree, struct clib_rb_node* node) {\r
  38         if ( node ) \r
  39             return node->raw_data.key;\r
  40         return (void*)0;\r
  41     }\r
  42 \r
  43 static struct clib_rb_node*\r
  44     get_left (struct clib_rb* tree, struct clib_rb_node* node ) {\r
  45         if ( node->left != rb_sentinel && node->left != (struct clib_rb_node*)0 )\r
  46             return node->left;\r
  47         return (struct clib_rb_node*)0 ;\r
  48     }\r
  49 static struct clib_rb_node*\r
  50     get_right (struct clib_rb* tree, struct clib_rb_node* node ){\r
  51         if ( node->right != rb_sentinel && node->right != (struct clib_rb_node*)0 )\r
  52             return node->right;\r
  53         return (struct clib_rb_node*)0 ;\r
  54     }\r
  55 static struct clib_rb_node*\r
  56     get_parent ( struct clib_rb* tree,struct clib_rb_node* node ) {\r
  57         if ( node->parent != rb_sentinel && node->parent != (struct clib_rb_node*)0 )\r
  58             return node->parent;\r
  59         return (struct clib_rb_node*)0 ;\r
  60     }\r
  61 \r
  62 int \r
  63 compare_rb_e ( void*  l, void* r ) {\r
  64 \r
  65     int left =  0;\r
  66     int right = 0;\r
  67 \r
  68     if ( l ) left  = *(int*)l;\r
  69     if ( r ) right = *(int*)r;\r
  70 \r
  71     if ( left < right ) return -1;\r
  72     if ( left == right ) return 0;\r
  73 \r
  74     return 1;\r
  75 }\r
  76 \r
  77 void \r
  78 free_rb_e ( void* p ) {\r
  79     if ( p ) {\r
  80         free ( p );\r
  81     }\r
  82 }\r
  83 \r
  84 typedef struct test_data_tree {\r
  85     int element;\r
  86     int left;\r
  87     int right;\r
  88     int parent;\r
  89     int color;\r
  90 } TS;\r
  91 \r
  92 \r
  93 static struct clib_rb_node*\r
  94 pvt_find_clib_rb ( struct clib_rb* tree, clib_compare fn_c, void *key ) {\r
  95     struct clib_rb_node* node = tree->root;\r
  96     void* current_key = (void*)0;\r
  97     int compare_result = 0;\r
  98 \r
  99     current_key = (void*)malloc ( tree->size_of_key);\r
 100     memcpy ( current_key, key, tree->size_of_key);\r
 101 \r
 102     compare_result = (fn_c)(current_key, node->raw_data.key);\r
 103     while ((node != rb_sentinel) && (compare_result = (fn_c)(current_key, node->raw_data.key)) != 0 ){\r
 104         if ( compare_result < 0 ) {\r
 105             node = node->left;\r
 106         } else {\r
 107             node = node->right;\r
 108         }\r
 109     } \r
 110     free ( current_key );\r
 111     return node;\r
 112 }\r
 113 struct clib_rb_node*\r
 114 find(struct clib_rb* tree, void *key ) {\r
 115     return pvt_find_clib_rb ( tree, tree->compare_fn, key );\r
 116 }\r
 117 \r
 118 static void update_values ( void* v, int *l, int *r, int *p , int *e, struct clib_rb* tree ) {\r
 119     struct clib_rb_node *x;\r
 120     if ( get_key(tree,v)) \r
 121         *e = *(int*)get_key (tree,v);\r
 122     x = get_left(tree,v);\r
 123     if ( x )\r
 124         *l = *(int*)get_key(tree,x);\r
 125     x = get_right(tree,v);\r
 126     if (x) \r
 127         *r = *(int*)get_key(tree,x);\r
 128     x = get_parent ( tree, v );\r
 129     if (x)              \r
 130         *p = *(int*)get_key(tree,x);\r
 131 }\r
 132 \r
 133 static void \r
 134 test_each_elements(int l,int r, int p, int e,void* v, TS ts[], int i, \r
 135         struct clib_rb* tree) {\r
 136     assert ( ts[i].element == e);\r
 137     if (ts[i].left != 0 ) \r
 138         assert ( ts[i].left == l);\r
 139     else\r
 140         assert ((void* )0 == (void* )get_key(tree,get_left(tree,v)));\r
 141     if ( ts[i].right != 0 ) \r
 142         assert (ts[i].right == r);\r
 143     else\r
 144         assert ((void* )0 == (void* )get_key(tree,get_right(tree,v)));\r
 145     if (ts[i].parent != 0 ) \r
 146         assert (ts[i].parent == p);\r
 147     else\r
 148         assert ((void* )0 == (void* )get_key(tree,get_parent(tree,v)));\r
 149 }\r
 150 \r
 151 static void\r
 152 test_all_elements(struct clib_rb* tree, TS ts[], int size) {\r
 153     int i = 0;\r
 154     for ( i = 0; i < size; i++) {\r
 155         void* v = (void*)0;\r
 156         int l,r,p,e;\r
 157         v = find ( tree, &ts[i].element);\r
 158         update_values( v, &l,&r,&p,&e, tree);\r
 159         test_each_elements(l,r,p,e,v, ts, i, tree);\r
 160     }\r
 161 }\r
 162 \r
 163 static struct clib_rb* \r
 164 create_tree(TS ts[], int size) {\r
 165     int i = 0;\r
 166     struct clib_rb* tree = new_clib_rb( compare_rb_e,free_rb_e, (void*)0, sizeof(int),0);\r
 167     for ( i = 0; i < size; i++) {\r
 168         insert_clib_rb( tree, &(ts[i].element) ,(void*)0);\r
 169     }\r
 170     return tree;\r
 171 }\r
 172 \r
 173 \r
 174 void \r
 175 test_clib_rb() {\r
 176     int size;\r
 177     int size_after_delete;\r
 178     int i = 0;\r
 179     struct clib_rb* tree;\r
 180     struct clib_rb_node* node;\r
 181 \r
 182     TS ts[] = {\r
 183         {15,6,18,0,BLACK},{6,3,9,15,RED},{18,17,20,15,BLACK},\r
 184         {3,2,4,6,BLACK},{7,0,0,9,RED},{17,0,0,18,RED},\r
 185         {20,0,0,18,RED},{2,0,0,3,RED},{4,0,0,3,RED},{13,0,0,9,RED},     \r
 186         {9,7,13,6,BLACK}\r
 187     };\r
 188     TS ts_delete_leaf_13[] = {\r
 189         {15,6,18,0,BLACK},{6,3,9,15,RED},{18,17,20,15,BLACK},\r
 190         {3,2,4,6,BLACK},{7,0,0,9,RED},{17,0,0,18,RED},\r
 191         {20,0,0,18,RED},{2,0,0,3,RED},{4,0,0,3,RED},\r
 192         {9,7,0,6,BLACK}\r
 193     };  \r
 194     TS ts_delete_9[] = {\r
 195         {15,6,18,0,BLACK},{6,3,7,15,RED},{18,17,20,15,BLACK},\r
 196         {3,2,4,6,RED},{7,0,0,6,RED},{17,0,0,18,RED},\r
 197         {20,0,0,18,RED},{2,0,0,3,RED},{4,0,0,3,RED}\r
 198     };  \r
 199     TS ts_delete_15[] = {\r
 200         {6,3,7,17,RED},{18,0,20,17,BLACK},\r
 201         {3,2,4,6,RED},{7,0,0,6,RED},{17,6,18,0,RED},\r
 202         {20,0,0,18,RED},{2,0,0,3,RED},{4,0,0,3,RED}\r
 203     };                  \r
 204     TS ts_insert_1[] = {\r
 205         {6,3,17,0,BLACK},{18,0,20,17,BLACK},\r
 206         {3,2,4,6,RED},{7,0,0,17,RED},{17,7,18,6,RED},\r
 207         {20,0,0,18,RED},{2,1,0,3,BLACK},{4,0,0,3,BLACK},\r
 208         {1,0,0,2,RED}\r
 209     };                  \r
 210 \r
 211 \r
 212     size = (sizeof(ts)/sizeof(TS));\r
 213     tree = create_tree(ts,size);\r
 214     test_all_elements(tree, ts, size); \r
 215     {   \r
 216         i = 13; \r
 217         size = (sizeof(ts)/sizeof(TS));\r
 218         size_after_delete = (sizeof(ts_delete_leaf_13)/sizeof(TS));\r
 219         node = remove_clib_rb( tree, &i);\r
 220         if ( node != (struct clib_rb_node*)0  ) {\r
 221             free ( node->raw_data.key);\r
 222             free ( node);\r
 223         }\r
 224         test_all_elements(tree, ts_delete_leaf_13, size_after_delete);\r
 225     }\r
 226     {\r
 227         i = 9;  \r
 228         size_after_delete = (sizeof(ts_delete_9)/sizeof(TS));\r
 229         node = remove_clib_rb( tree, &i);\r
 230         if ( node != (struct clib_rb_node*)0  ) {\r
 231             free ( node->raw_data.key);\r
 232             free ( node);\r
 233         }\r
 234         test_all_elements(tree, ts_delete_9, size_after_delete);\r
 235     }\r
 236     {\r
 237         i = 15; \r
 238         size_after_delete = (sizeof(ts_delete_15)/sizeof(TS));\r
 239         node = remove_clib_rb( tree, &i);\r
 240         if ( node != (struct clib_rb_node*)0  ) {\r
 241             free ( node->raw_data.key);\r
 242             free ( node);\r
 243         }\r
 244         test_all_elements(tree, ts_delete_15, size_after_delete);\r
 245     }\r
 246     {\r
 247         int i = 1;\r
 248         insert_clib_rb( tree, &i, (void*)0);\r
 249         size_after_delete = (sizeof(ts_insert_1)/sizeof(TS));\r
 250         test_all_elements(tree, ts_insert_1, size_after_delete);\r
 251     }\r
 252     {\r
 253       delete_clib_rb(tree);\r
 254     }\r
 255 }*/\r