git.ozlabs.org Git - ccan/blob - junkcode/dongre.avinash@gmail.com-clibutils/src/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 <string.h>\r
  28 #include <assert.h>\r
  29 \r
  30 #define rb_sentinel &pTree->sentinel\r
  31 \r
  32 static void debug_verify_properties(struct clib_rb*);\r
  33 static void debug_verify_property_1(struct clib_rb*,struct clib_rb_node*);\r
  34 static void debug_verify_property_2(struct clib_rb*,struct clib_rb_node*);\r
  35 static int debug_node_color(struct clib_rb*,struct clib_rb_node* n);\r
  36 static void debug_verify_property_4(struct clib_rb*,struct clib_rb_node*);\r
  37 static void debug_verify_property_5(struct clib_rb*,struct clib_rb_node*);\r
  38 static void debug_verify_property_5_helper(struct clib_rb*,struct clib_rb_node*,int,int*);\r
  39 \r
  40 \r
  41 static void\r
  42 pvt_left_rotate(struct clib_rb *pTree, struct clib_rb_node *x){\r
  43     struct clib_rb_node *y;\r
  44     y = x->right;\r
  45     x->right = y->left;\r
  46     if (y->left != rb_sentinel)\r
  47         y->left->parent = x;\r
  48     if (y != rb_sentinel)\r
  49         y->parent = x->parent;\r
  50     if (x->parent){\r
  51         if (x == x->parent->left)\r
  52             x->parent->left = y;\r
  53         else\r
  54             x->parent->right = y;\r
  55     }\r
  56     else\r
  57         pTree->root = y;\r
  58     y->left = x;\r
  59     if (x != rb_sentinel)\r
  60         x->parent = y;\r
  61 }\r
  62 static void\r
  63 pvt_right_rotate(struct clib_rb *pTree, struct clib_rb_node *x) {\r
  64     struct clib_rb_node *y = x->left;\r
  65     x->left = y->right;\r
  66     if (y->right != rb_sentinel)\r
  67         y->right->parent = x;\r
  68     if (y != rb_sentinel)\r
  69         y->parent = x->parent;\r
  70     if (x->parent) {\r
  71         if (x == x->parent->right)\r
  72             x->parent->right = y;\r
  73         else\r
  74             x->parent->left = y;\r
  75     }\r
  76     else\r
  77         pTree->root = y;\r
  78     y->right = x;\r
  79     if (x != rb_sentinel)\r
  80         x->parent = y;\r
  81 }\r
  82 \r
  83 struct clib_rb*\r
  84 new_clib_rb(clib_compare fn_c,clib_destroy fn_ed, clib_destroy fn_vd ){\r
  85 \r
  86     struct clib_rb *pTree = (struct clib_rb*)malloc(sizeof(struct clib_rb));\r
  87     if ( pTree == (struct clib_rb*)0 )\r
  88         return (struct clib_rb*)0;\r
  89 \r
  90     pTree->compare_fn           = fn_c;\r
  91     pTree->destruct_k_fn        = fn_ed;\r
  92     pTree->destruct_v_fn        = fn_vd;\r
  93     pTree->root                 = rb_sentinel;\r
  94     pTree->sentinel.left        = rb_sentinel;\r
  95     pTree->sentinel.right       = rb_sentinel;\r
  96     pTree->sentinel.parent      = (struct clib_rb_node*)0 ;\r
  97     pTree->sentinel.color       = clib_black;\r
  98 \r
  99     return pTree;\r
 100 }\r
 101 static void\r
 102 pvt_rb_insert_fixup( struct clib_rb *pTree, struct clib_rb_node *x ) {\r
 103     while (x != pTree->root && x->parent->color == clib_red) {\r
 104         if (x->parent == x->parent->parent->left) {\r
 105             struct clib_rb_node *y = x->parent->parent->right;\r
 106             if (y->color == clib_red) {\r
 107                 x->parent->color         = clib_black;\r
 108                 y->color                 = clib_black;\r
 109                 x->parent->parent->color = clib_red;\r
 110                 x = x->parent->parent;\r
 111             } else {\r
 112                 if (x == x->parent->right){\r
 113                     x = x->parent;\r
 114                     pvt_left_rotate (pTree, x);\r
 115                 }\r
 116                 x->parent->color         = clib_black;\r
 117                 x->parent->parent->color = clib_red;\r
 118                 pvt_right_rotate (pTree, x->parent->parent);\r
 119             }\r
 120         } else {\r
 121             struct clib_rb_node *y = x->parent->parent->left;\r
 122             if (y->color == clib_red) {\r
 123                 x->parent->color         = clib_black;\r
 124                 y->color                 = clib_black;\r
 125                 x->parent->parent->color = clib_red;\r
 126                 x = x->parent->parent;\r
 127             } else {\r
 128                 if (x == x->parent->left) {\r
 129                     x = x->parent;\r
 130                     pvt_right_rotate (pTree, x);\r
 131                 }\r
 132                 x->parent->color         = clib_black;\r
 133                 x->parent->parent->color = clib_red;\r
 134                 pvt_left_rotate (pTree, x->parent->parent);\r
 135             }\r
 136         }\r
 137     }\r
 138     pTree->root->color = clib_black;\r
 139 }\r
 140 struct clib_rb_node*   \r
 141 find_clib_rb (struct clib_rb *pTree, void *key) {\r
 142     struct clib_rb_node *x = pTree->root;\r
 143 \r
 144     while (x != rb_sentinel) {\r
 145         int c = 0;\r
 146         void *cur_key ;\r
 147         get_raw_clib_object ( x->key, &cur_key );\r
 148         c = pTree->compare_fn (key, cur_key);\r
 149         free ( cur_key );\r
 150         if (c == 0) {\r
 151             break;\r
 152         } else {\r
 153             x = c < 0 ? x->left : x->right;\r
 154         }\r
 155     }\r
 156     if ( x == rb_sentinel )\r
 157         return (struct clib_rb_node*)0 ;\r
 158 \r
 159     return x;\r
 160 }\r
 161 \r
 162 clib_error  \r
 163 insert_clib_rb(struct clib_rb *pTree, void *k, size_t key_size, void *v, size_t value_size) {\r
 164 \r
 165     clib_error rc = CLIB_ERROR_SUCCESS;\r
 166     struct clib_rb_node *x;\r
 167         struct clib_rb_node *y;\r
 168         struct clib_rb_node *z;\r
 169 \r
 170     x = (struct clib_rb_node*)malloc (sizeof(struct clib_rb_node));\r
 171     if ( x == (struct clib_rb_node*)0  ) \r
 172         return CLIB_ERROR_MEMORY;\r
 173 \r
 174     x->left    = rb_sentinel;\r
 175     x->right   = rb_sentinel;\r
 176     x->color   = clib_red;\r
 177 \r
 178     x->key     = new_clib_object ( k, key_size );\r
 179     if ( v ) {\r
 180         x->value   = new_clib_object ( v, value_size );\r
 181     } else {\r
 182         x->value =  (struct clib_object*)0;\r
 183     }\r
 184 \r
 185     y = pTree->root;\r
 186     z = (struct clib_rb_node*)0 ;\r
 187 \r
 188     while (y != rb_sentinel) {\r
 189         int c = 0;\r
 190         void *cur_key;\r
 191                 void* new_key;\r
 192 \r
 193         get_raw_clib_object ( y->key, &cur_key );\r
 194         get_raw_clib_object ( x->key, &new_key );\r
 195 \r
 196         c = (pTree->compare_fn) ( new_key , cur_key);\r
 197         free ( cur_key );\r
 198         free ( new_key );\r
 199         if (c == 0) {\r
 200             /* TODO : Delete node here */\r
 201             return CLIB_RBTREE_KEY_DUPLICATE;\r
 202         }\r
 203         z = y;\r
 204         if ( c < 0 )\r
 205             y = y->left;\r
 206         else\r
 207             y = y->right;\r
 208     }    \r
 209     x->parent = z;\r
 210     if (z) {\r
 211         int c = 0;\r
 212         void *cur_key;\r
 213                 void* new_key;\r
 214         get_raw_clib_object ( z->key, &cur_key );\r
 215         get_raw_clib_object ( x->key, &new_key );\r
 216 \r
 217         c = pTree->compare_fn( new_key, cur_key);\r
 218         free ( cur_key );\r
 219         free ( new_key );\r
 220         if (c < 0) {\r
 221             z->left = x;\r
 222         } else {\r
 223             z->right = x;\r
 224         }\r
 225     }\r
 226     else\r
 227         pTree->root = x;\r
 228 \r
 229     pvt_rb_insert_fixup (pTree, x);\r
 230 \r
 231     debug_verify_properties ( pTree);\r
 232     return rc;\r
 233 }\r
 234 static void\r
 235 pvt_rb_remove_fixup( struct clib_rb *pTree, struct clib_rb_node *x ) {\r
 236     while (x != pTree->root && x->color == clib_black) {\r
 237         if (x == x->parent->left) {\r
 238             struct clib_rb_node *w = x->parent->right;\r
 239             if (w->color == clib_red) {\r
 240                 w->color         = clib_black;\r
 241                 x->parent->color = clib_red;\r
 242                 pvt_left_rotate (pTree, x->parent);\r
 243                 w = x->parent->right;\r
 244             }\r
 245             if (w->left->color == clib_black && w->right->color == clib_black) {\r
 246                 w->color = clib_red;\r
 247                 x = x->parent;\r
 248             } else {\r
 249                 if (w->right->color == clib_black)  {\r
 250                     w->left->color = clib_black;\r
 251                     w->color       = clib_red;\r
 252                     pvt_right_rotate (pTree, w);\r
 253                     w = x->parent->right;\r
 254                 }\r
 255                 w->color = x->parent->color;\r
 256                 x->parent->color = clib_black;\r
 257                 w->right->color = clib_black;\r
 258                 pvt_left_rotate (pTree, x->parent);\r
 259                 x = pTree->root;\r
 260             }\r
 261         } else {\r
 262             struct clib_rb_node *w = x->parent->left;\r
 263             if (w->color == clib_red) {\r
 264                 w->color = clib_black;\r
 265                 x->parent->color = clib_red;\r
 266                 pvt_right_rotate (pTree, x->parent);\r
 267                 w = x->parent->left;\r
 268             }\r
 269             if (w->right->color == clib_black && w->left->color == clib_black) {\r
 270                 w->color = clib_red;\r
 271                 x = x->parent;\r
 272             } else {\r
 273                 if (w->left->color == clib_black) {\r
 274                     w->right->color = clib_black;\r
 275                     w->color = clib_red;\r
 276                     pvt_left_rotate (pTree, w);\r
 277                     w = x->parent->left;\r
 278                 }\r
 279                 w->color = x->parent->color;\r
 280                 x->parent->color = clib_black;\r
 281                 w->left->color = clib_black;\r
 282                 pvt_right_rotate (pTree, x->parent);\r
 283                 x = pTree->root;\r
 284             }\r
 285         }\r
 286     }\r
 287     x->color = clib_black;\r
 288 }\r
 289 \r
 290 static struct clib_rb_node*  \r
 291 pvt_remove_clib_rb(struct clib_rb *pTree, struct clib_rb_node *z ) {\r
 292     struct clib_rb_node *x = (struct clib_rb_node*)0 ;\r
 293     struct clib_rb_node *y = (struct clib_rb_node*)0 ;\r
 294 \r
 295     if (z->left == rb_sentinel || z->right == rb_sentinel)\r
 296         y = z;\r
 297     else {\r
 298         y = z->right;\r
 299         while (y->left != rb_sentinel)\r
 300             y = y->left;\r
 301     }\r
 302     if (y->left != rb_sentinel)\r
 303         x = y->left;\r
 304     else\r
 305         x = y->right;\r
 306 \r
 307     x->parent = y->parent;\r
 308     if (y->parent)\r
 309     {\r
 310         if (y == y->parent->left)\r
 311             y->parent->left = x;\r
 312         else\r
 313             y->parent->right = x;\r
 314     }\r
 315     else\r
 316         pTree->root = x;\r
 317     if (y != z) {\r
 318         struct clib_object* tmp;\r
 319         tmp    = z->key;\r
 320         z->key = y->key;\r
 321         y->key = tmp;\r
 322 \r
 323         tmp      = z->value;\r
 324         z->value = y->value;\r
 325         y->value = tmp;\r
 326     }\r
 327     if (y->color == clib_black)\r
 328         pvt_rb_remove_fixup (pTree, x);\r
 329 \r
 330     debug_verify_properties ( pTree);\r
 331     return y;\r
 332 }\r
 333 \r
 334 struct clib_rb_node*\r
 335 remove_clib_rb (struct clib_rb *pTree, void *key) {\r
 336     struct clib_rb_node *z = (struct clib_rb_node*)0 ;\r
 337 \r
 338     z = pTree->root;\r
 339     while (z != rb_sentinel) {\r
 340         int c = 0;\r
 341         void *cur_key;\r
 342         get_raw_clib_object ( z->key, &cur_key );\r
 343         c = pTree->compare_fn (key, cur_key);\r
 344         free ( cur_key );\r
 345         if ( c == 0) {\r
 346             break;\r
 347         }\r
 348         else {\r
 349             z = ( c < 0) ? z->left : z->right;\r
 350         }\r
 351     }\r
 352     if (z == rb_sentinel)\r
 353         return (struct clib_rb_node*)0 ;\r
 354     return pvt_remove_clib_rb(pTree, z );\r
 355 }\r
 356 static void\r
 357 pvt_delete_clib_rb_node (struct clib_rb *pTree, struct clib_rb_node *x ) {\r
 358 \r
 359     void *key;\r
 360         void *value;\r
 361 \r
 362     if ( pTree->destruct_k_fn ) {\r
 363         get_raw_clib_object ( x->key, &key );\r
 364         pTree->destruct_k_fn ( key );\r
 365     }\r
 366     delete_clib_object( x->key );\r
 367 \r
 368     if ( x->value ) {\r
 369         if ( pTree->destruct_v_fn ) {\r
 370             get_raw_clib_object ( x->value, &value);\r
 371             pTree->destruct_v_fn ( value );\r
 372         }\r
 373         delete_clib_object( x->value );\r
 374     }\r
 375 }\r
 376 \r
 377 clib_error  \r
 378 delete_clib_rb(struct clib_rb *pTree) {\r
 379 \r
 380     clib_error rc = CLIB_ERROR_SUCCESS;\r
 381     struct clib_rb_node *z = pTree->root;\r
 382 \r
 383     while (z != rb_sentinel) {\r
 384         if (z->left != rb_sentinel)\r
 385             z = z->left;\r
 386         else if (z->right != rb_sentinel)\r
 387             z = z->right;\r
 388         else {\r
 389             pvt_delete_clib_rb_node ( pTree, z );\r
 390             if (z->parent) {\r
 391                 z = z->parent;\r
 392                 if (z->left != rb_sentinel){\r
 393                     free ( z->left );\r
 394                     z->left = rb_sentinel;\r
 395                 }else if (z->right != rb_sentinel){\r
 396                     free ( z->right );\r
 397                     z->right = rb_sentinel;\r
 398                 }\r
 399             } else {\r
 400                 free ( z );\r
 401                 z = rb_sentinel;\r
 402             }\r
 403         }\r
 404     }\r
 405     free ( pTree );\r
 406     return rc;\r
 407 }\r
 408 struct clib_rb_node *\r
 409 minimum_clib_rb( struct clib_rb *pTree, struct clib_rb_node *x ) {\r
 410         while ( x->left != rb_sentinel)\r
 411                 x = x->left;\r
 412         return x;\r
 413 }\r
 414 \r
 415 struct clib_rb_node *\r
 416 maximum_clib_rb( struct clib_rb *pTree, struct clib_rb_node *x ) {\r
 417         while ( x->right != rb_sentinel)\r
 418                 x = x->right;\r
 419         return x;\r
 420 }\r
 421 \r
 422 \r
 423 clib_bool \r
 424 empty_clib_rb(struct clib_rb *pTree) {\r
 425     if ( pTree->root != rb_sentinel )\r
 426         return clib_true;\r
 427     return clib_false;\r
 428 }\r
 429 struct clib_rb_node*\r
 430 tree_successor(struct clib_rb *pTree, struct clib_rb_node *x) {\r
 431         struct clib_rb_node *y = (struct clib_rb_node*)0;\r
 432         if ( x->right != rb_sentinel)\r
 433                 return minimum_clib_rb( pTree, x->right);\r
 434         \r
 435         if ( x  == maximum_clib_rb(pTree,pTree->root)) \r
 436                 return (struct clib_rb_node*)0;\r
 437 \r
 438         y = x->parent;\r
 439         while ( y != rb_sentinel && x == y->right ){\r
 440                 x = y;\r
 441                 y = y->parent;\r
 442         }\r
 443         return y;\r
 444 }\r
 445 \r
 446 \r
 447 void debug_verify_properties(struct clib_rb* t) {\r
 448     debug_verify_property_1(t,t->root);\r
 449     debug_verify_property_2(t,t->root);\r
 450     debug_verify_property_4(t,t->root);\r
 451     debug_verify_property_5(t,t->root);\r
 452 }\r
 453 \r
 454 void debug_verify_property_1(struct clib_rb *pTree,struct clib_rb_node* n) {\r
 455     assert(debug_node_color(pTree,n) == clib_red || debug_node_color(pTree,n) == clib_black);\r
 456     if (n == rb_sentinel) return;\r
 457     debug_verify_property_1(pTree,n->left);\r
 458     debug_verify_property_1(pTree,n->right);\r
 459 }\r
 460 \r
 461 void debug_verify_property_2(struct clib_rb *pTree,struct clib_rb_node* root) {\r
 462     assert(debug_node_color(pTree,root) == clib_black);\r
 463 }\r
 464 \r
 465 int debug_node_color(struct clib_rb *pTree,struct clib_rb_node* n) {\r
 466     return n == rb_sentinel ? clib_black : n->color;\r
 467 }\r
 468 \r
 469 void debug_verify_property_4(struct clib_rb *pTree,struct clib_rb_node* n) {\r
 470     if (debug_node_color(pTree,n) == clib_red) {\r
 471         assert (debug_node_color(pTree,n->left)   == clib_black);\r
 472         assert (debug_node_color(pTree,n->right)  == clib_black);\r
 473         assert (debug_node_color(pTree,n->parent) == clib_black);\r
 474     }\r
 475     if (n == rb_sentinel) return;\r
 476     debug_verify_property_4(pTree,n->left);\r
 477     debug_verify_property_4(pTree,n->right);\r
 478 }\r
 479 \r
 480 void debug_verify_property_5(struct clib_rb *pTree,struct clib_rb_node* root) {\r
 481     int black_count_path = -1;\r
 482     debug_verify_property_5_helper(pTree,root, 0, &black_count_path);\r
 483 }\r
 484 \r
 485 void debug_verify_property_5_helper(struct clib_rb *pTree,struct clib_rb_node* n, int black_count, int* path_black_count) {\r
 486     if (debug_node_color(pTree,n) == clib_black) {\r
 487         black_count++;\r
 488     }\r
 489     if (n == rb_sentinel) {\r
 490         if (*path_black_count == -1) {\r
 491             *path_black_count = black_count;\r
 492         } else {\r
 493             assert (black_count == *path_black_count);\r
 494         }\r
 495         return;\r
 496     }\r
 497     debug_verify_property_5_helper(pTree,n->left,  black_count, path_black_count);\r
 498     debug_verify_property_5_helper(pTree,n->right, black_count, path_black_count);\r
 499 }\r
 500 \r