pd.if.org Git - jsw/blob - jsw_rbtree/jsw_rbtree.c

   1 /*\r
   2   Red Black balanced tree library\r
   3 \r
   4     > Created (Julienne Walker): August 23, 2003\r
   5     > Modified (Julienne Walker): March 14, 2008\r
   6 */\r
   7 #include "jsw_rbtree.h"\r
   8 \r
   9 #ifdef __cplusplus\r
  10 #include <cstdlib>\r
  11 \r
  12 using std::malloc;\r
  13 using std::free;\r
  14 using std::size_t;\r
  15 #else\r
  16 #include <stdlib.h>\r
  17 #endif\r
  18 \r
  19 #ifndef HEIGHT_LIMIT\r
  20 #define HEIGHT_LIMIT 64 /* Tallest allowable tree */\r
  21 #endif\r
  22 \r
  23 typedef struct jsw_rbnode {\r
  24   int                red;     /* Color (1=red, 0=black) */\r
  25   void              *data;    /* User-defined content */\r
  26   struct jsw_rbnode *link[2]; /* Left (0) and right (1) links */\r
  27 } jsw_rbnode_t;\r
  28 \r
  29 struct jsw_rbtree {\r
  30   jsw_rbnode_t *root; /* Top of the tree */\r
  31   cmp_f         cmp;  /* Compare two items */\r
  32   dup_f         dup;  /* Clone an item (user-defined) */\r
  33   rel_f         rel;  /* Destroy an item (user-defined) */\r
  34   size_t        size; /* Number of items (user-defined) */\r
  35 };\r
  36 \r
  37 struct jsw_rbtrav {\r
  38   jsw_rbtree_t *tree;               /* Paired tree */\r
  39   jsw_rbnode_t *it;                 /* Current node */\r
  40   jsw_rbnode_t *path[HEIGHT_LIMIT]; /* Traversal path */\r
  41   size_t        top;                /* Top of stack */\r
  42 };\r
  43 \r
  44 /**\r
  45   <summary>\r
  46   Checks the color of a red black node\r
  47   <summary>\r
  48   <param name="root">The node to check</param>\r
  49   <returns>1 for a red node, 0 for a black node</returns>\r
  50   <remarks>For jsw_rbtree.c internal use only</remarks>\r
  51 */\r
  52 static int is_red ( jsw_rbnode_t *root )\r
  53 {\r
  54   return root != NULL && root->red == 1;\r
  55 }\r
  56 \r
  57 /**\r
  58   <summary>\r
  59   Performs a single red black rotation in the specified direction\r
  60   This function assumes that all nodes are valid for a rotation\r
  61   <summary>\r
  62   <param name="root">The original root to rotate around</param>\r
  63   <param name="dir">The direction to rotate (0 = left, 1 = right)</param>\r
  64   <returns>The new root ater rotation</returns>\r
  65   <remarks>For jsw_rbtree.c internal use only</remarks>\r
  66 */\r
  67 static jsw_rbnode_t *jsw_single ( jsw_rbnode_t *root, int dir )\r
  68 {\r
  69   jsw_rbnode_t *save = root->link[!dir];\r
  70 \r
  71   root->link[!dir] = save->link[dir];\r
  72   save->link[dir] = root;\r
  73 \r
  74   root->red = 1;\r
  75   save->red = 0;\r
  76 \r
  77   return save;\r
  78 }\r
  79 \r
  80 /**\r
  81   <summary>\r
  82   Performs a double red black rotation in the specified direction\r
  83   This function assumes that all nodes are valid for a rotation\r
  84   <summary>\r
  85   <param name="root">The original root to rotate around</param>\r
  86   <param name="dir">The direction to rotate (0 = left, 1 = right)</param>\r
  87   <returns>The new root after rotation</returns>\r
  88   <remarks>For jsw_rbtree.c internal use only</remarks>\r
  89 */\r
  90 static jsw_rbnode_t *jsw_double ( jsw_rbnode_t *root, int dir )\r
  91 {\r
  92   root->link[!dir] = jsw_single ( root->link[!dir], !dir );\r
  93 \r
  94   return jsw_single ( root, dir );\r
  95 }\r
  96 \r
  97 /**\r
  98   <summary>\r
  99   Creates an initializes a new red black node with a copy of\r
 100   the data. This function does not insert the new node into a tree\r
 101   <summary>\r
 102   <param name="tree">The red black tree this node is being created for</param>\r
 103   <param name="data">The data value that will be stored in this node</param>\r
 104   <returns>A pointer to the new node</returns>\r
 105   <remarks>\r
 106   For jsw_rbtree.c internal use only. The data for this node must\r
 107   be freed using the same tree's rel function. The returned pointer\r
 108   must be freed using C's free function\r
 109   </remarks>\r
 110 */\r
 111 static jsw_rbnode_t *new_node ( jsw_rbtree_t *tree, void *data )\r
 112 {\r
 113   jsw_rbnode_t *rn = (jsw_rbnode_t *)malloc ( sizeof *rn );\r
 114 \r
 115   if ( rn == NULL )\r
 116     return NULL;\r
 117 \r
 118   rn->red = 1;\r
 119   rn->data = tree->dup ( data );\r
 120   rn->link[0] = rn->link[1] = NULL;\r
 121 \r
 122   return rn;\r
 123 }\r
 124 \r
 125 /**\r
 126   <summary>\r
 127   Creates and initializes an empty red black tree with\r
 128   user-defined comparison, data copy, and data release operations\r
 129   <summary>\r
 130   <param name="cmp">User-defined data comparison function</param>\r
 131   <param name="dup">User-defined data copy function</param>\r
 132   <param name="rel">User-defined data release function</param>\r
 133   <returns>A pointer to the new tree</returns>\r
 134   <remarks>\r
 135   The returned pointer must be released with jsw_rbdelete\r
 136   </remarks>\r
 137 */\r
 138 jsw_rbtree_t *jsw_rbnew ( cmp_f cmp, dup_f dup, rel_f rel )\r
 139 {\r
 140   jsw_rbtree_t *rt = (jsw_rbtree_t *)malloc ( sizeof *rt );\r
 141 \r
 142   if ( rt == NULL )\r
 143     return NULL;\r
 144 \r
 145   rt->root = NULL;\r
 146   rt->cmp = cmp;\r
 147   rt->dup = dup;\r
 148   rt->rel = rel;\r
 149   rt->size = 0;\r
 150 \r
 151   return rt;\r
 152 }\r
 153 \r
 154 /**\r
 155   <summary>\r
 156   Releases a valid red black tree\r
 157   <summary>\r
 158   <param name="tree">The tree to release</param>\r
 159   <remarks>\r
 160   The tree must have been created using jsw_rbnew\r
 161   </remarks>\r
 162 */\r
 163 void jsw_rbdelete ( jsw_rbtree_t *tree )\r
 164 {\r
 165   jsw_rbnode_t *it = tree->root;\r
 166   jsw_rbnode_t *save;\r
 167 \r
 168   /*\r
 169     Rotate away the left links so that\r
 170     we can treat this like the destruction\r
 171     of a linked list\r
 172   */\r
 173   while ( it != NULL ) {\r
 174     if ( it->link[0] == NULL ) {\r
 175       /* No left links, just kill the node and move on */\r
 176       save = it->link[1];\r
 177       tree->rel ( it->data );\r
 178       free ( it );\r
 179     }\r
 180     else {\r
 181       /* Rotate away the left link and check again */\r
 182       save = it->link[0];\r
 183       it->link[0] = save->link[1];\r
 184       save->link[1] = it;\r
 185     }\r
 186 \r
 187     it = save;\r
 188   }\r
 189 \r
 190   free ( tree );\r
 191 }\r
 192 \r
 193 /**\r
 194   <summary>\r
 195   Search for a copy of the specified\r
 196   node data in a red black tree\r
 197   <summary>\r
 198   <param name="tree">The tree to search</param>\r
 199   <param name="data">The data value to search for</param>\r
 200   <returns>\r
 201   A pointer to the data value stored in the tree,\r
 202   or a null pointer if no data could be found\r
 203   </returns>\r
 204 */\r
 205 void *jsw_rbfind ( jsw_rbtree_t *tree, void *data )\r
 206 {\r
 207   jsw_rbnode_t *it = tree->root;\r
 208 \r
 209   while ( it != NULL ) {\r
 210     int cmp = tree->cmp ( it->data, data );\r
 211 \r
 212     if ( cmp == 0 )\r
 213       break;\r
 214 \r
 215     /*\r
 216       If the tree supports duplicates, they should be\r
 217       chained to the right subtree for this to work\r
 218     */\r
 219     it = it->link[cmp < 0];\r
 220   }\r
 221 \r
 222   return it == NULL ? NULL : it->data;\r
 223 }\r
 224 \r
 225 /**\r
 226   <summary>\r
 227   Insert a copy of the user-specified\r
 228   data into a red black tree\r
 229   <summary>\r
 230   <param name="tree">The tree to insert into</param>\r
 231   <param name="data">The data value to insert</param>\r
 232   <returns>\r
 233   1 if the value was inserted successfully,\r
 234   0 if the insertion failed for any reason\r
 235   </returns>\r
 236 */\r
 237 int jsw_rbinsert ( jsw_rbtree_t *tree, void *data )\r
 238 {\r
 239   if ( tree->root == NULL ) {\r
 240     /*\r
 241       We have an empty tree; attach the\r
 242       new node directly to the root\r
 243     */\r
 244     tree->root = new_node ( tree, data );\r
 245 \r
 246     if ( tree->root == NULL )\r
 247       return 0;\r
 248   }\r
 249   else {\r
 250     jsw_rbnode_t head = {0}; /* False tree root */\r
 251     jsw_rbnode_t *g, *t;     /* Grandparent & parent */\r
 252     jsw_rbnode_t *p, *q;     /* Iterator & parent */\r
 253     int dir = 0, last = 0;\r
 254 \r
 255     /* Set up our helpers */\r
 256     t = &head;\r
 257     g = p = NULL;\r
 258     q = t->link[1] = tree->root;\r
 259 \r
 260     /* Search down the tree for a place to insert */\r
 261     for ( ; ; ) {\r
 262       if ( q == NULL ) {\r
 263         /* Insert a new node at the first null link */\r
 264         p->link[dir] = q = new_node ( tree, data );\r
 265 \r
 266         if ( q == NULL )\r
 267           return 0;\r
 268       }\r
 269       else if ( is_red ( q->link[0] ) && is_red ( q->link[1] ) ) {\r
 270         /* Simple red violation: color flip */\r
 271         q->red = 1;\r
 272         q->link[0]->red = 0;\r
 273         q->link[1]->red = 0;\r
 274       }\r
 275 \r
 276       if ( is_red ( q ) && is_red ( p ) ) {\r
 277         /* Hard red violation: rotations necessary */\r
 278         int dir2 = t->link[1] == g;\r
 279 \r
 280         if ( q == p->link[last] )\r
 281           t->link[dir2] = jsw_single ( g, !last );\r
 282         else\r
 283           t->link[dir2] = jsw_double ( g, !last );\r
 284       }\r
 285 \r
 286       /*\r
 287         Stop working if we inserted a node. This\r
 288         check also disallows duplicates in the tree\r
 289       */\r
 290       if ( tree->cmp ( q->data, data ) == 0 )\r
 291         break;\r
 292 \r
 293       last = dir;\r
 294       dir = tree->cmp ( q->data, data ) < 0;\r
 295 \r
 296       /* Move the helpers down */\r
 297       if ( g != NULL )\r
 298         t = g;\r
 299 \r
 300       g = p, p = q;\r
 301       q = q->link[dir];\r
 302     }\r
 303 \r
 304     /* Update the root (it may be different) */\r
 305     tree->root = head.link[1];\r
 306   }\r
 307 \r
 308   /* Make the root black for simplified logic */\r
 309   tree->root->red = 0;\r
 310   ++tree->size;\r
 311 \r
 312   return 1;\r
 313 }\r
 314 \r
 315 /**\r
 316   <summary>\r
 317   Remove a node from a red black tree\r
 318   that matches the user-specified data\r
 319   <summary>\r
 320   <param name="tree">The tree to remove from</param>\r
 321   <param name="data">The data value to search for</param>\r
 322   <returns>\r
 323   1 if the value was removed successfully,\r
 324   0 if the removal failed for any reason\r
 325   </returns>\r
 326   <remarks>\r
 327   The most common failure reason should be\r
 328   that the data was not found in the tree\r
 329   </remarks>\r
 330 */\r
 331 int jsw_rberase ( jsw_rbtree_t *tree, void *data )\r
 332 {\r
 333   if ( tree->root != NULL ) {\r
 334     jsw_rbnode_t head = {0}; /* False tree root */\r
 335     jsw_rbnode_t *q, *p, *g; /* Helpers */\r
 336     jsw_rbnode_t *f = NULL;  /* Found item */\r
 337     int dir = 1;\r
 338 \r
 339     /* Set up our helpers */\r
 340     q = &head;\r
 341     g = p = NULL;\r
 342     q->link[1] = tree->root;\r
 343 \r
 344     /*\r
 345       Search and push a red node down\r
 346       to fix red violations as we go\r
 347     */\r
 348     while ( q->link[dir] != NULL ) {\r
 349       int last = dir;\r
 350 \r
 351       /* Move the helpers down */\r
 352       g = p, p = q;\r
 353       q = q->link[dir];\r
 354       dir = tree->cmp ( q->data, data ) < 0;\r
 355 \r
 356       /*\r
 357         Save the node with matching data and keep\r
 358         going; we'll do removal tasks at the end\r
 359       */\r
 360       if ( tree->cmp ( q->data, data ) == 0 )\r
 361         f = q;\r
 362 \r
 363       /* Push the red node down with rotations and color flips */\r
 364       if ( !is_red ( q ) && !is_red ( q->link[dir] ) ) {\r
 365         if ( is_red ( q->link[!dir] ) )\r
 366           p = p->link[last] = jsw_single ( q, dir );\r
 367         else if ( !is_red ( q->link[!dir] ) ) {\r
 368           jsw_rbnode_t *s = p->link[!last];\r
 369 \r
 370           if ( s != NULL ) {\r
 371             if ( !is_red ( s->link[!last] ) && !is_red ( s->link[last] ) ) {\r
 372               /* Color flip */\r
 373               p->red = 0;\r
 374               s->red = 1;\r
 375               q->red = 1;\r
 376             }\r
 377             else {\r
 378               int dir2 = g->link[1] == p;\r
 379 \r
 380               if ( is_red ( s->link[last] ) )\r
 381                 g->link[dir2] = jsw_double ( p, last );\r
 382               else if ( is_red ( s->link[!last] ) )\r
 383                 g->link[dir2] = jsw_single ( p, last );\r
 384 \r
 385               /* Ensure correct coloring */\r
 386               q->red = g->link[dir2]->red = 1;\r
 387               g->link[dir2]->link[0]->red = 0;\r
 388               g->link[dir2]->link[1]->red = 0;\r
 389             }\r
 390           }\r
 391         }\r
 392       }\r
 393     }\r
 394 \r
 395     /* Replace and remove the saved node */\r
 396     if ( f != NULL ) {\r
 397       tree->rel ( f->data );\r
 398       f->data = q->data;\r
 399       p->link[p->link[1] == q] =\r
 400         q->link[q->link[0] == NULL];\r
 401       free ( q );\r
 402     }\r
 403 \r
 404     /* Update the root (it may be different) */\r
 405     tree->root = head.link[1];\r
 406 \r
 407     /* Make the root black for simplified logic */\r
 408     if ( tree->root != NULL )\r
 409       tree->root->red = 0;\r
 410 \r
 411     --tree->size;\r
 412   }\r
 413 \r
 414   return 1;\r
 415 }\r
 416 \r
 417 /**\r
 418   <summary>\r
 419   Gets the number of nodes in a red black tree\r
 420   <summary>\r
 421   <param name="tree">The tree to calculate a size for</param>\r
 422   <returns>The number of nodes in the tree</returns>\r
 423 */\r
 424 size_t jsw_rbsize ( jsw_rbtree_t *tree )\r
 425 {\r
 426   return tree->size;\r
 427 }\r
 428 \r
 429 /**\r
 430   <summary>\r
 431   Create a new traversal object\r
 432   <summary>\r
 433   <returns>A pointer to the new object</returns>\r
 434   <remarks>\r
 435   The traversal object is not initialized until\r
 436   jsw_rbtfirst or jsw_rbtlast are called.\r
 437   The pointer must be released with jsw_rbtdelete\r
 438   </remarks>\r
 439 */\r
 440 jsw_rbtrav_t *jsw_rbtnew ( void )\r
 441 {\r
 442   return (jsw_rbtrav_t*)malloc ( sizeof ( jsw_rbtrav_t ) );\r
 443 }\r
 444 \r
 445 /**\r
 446   <summary>\r
 447   Release a traversal object\r
 448   <summary>\r
 449   <param name="trav">The object to release</param>\r
 450   <remarks>\r
 451   The object must have been created with jsw_rbtnew\r
 452   </remarks>\r
 453 */\r
 454 void jsw_rbtdelete ( jsw_rbtrav_t *trav )\r
 455 {\r
 456   free ( trav );\r
 457 }\r
 458 \r
 459 /**\r
 460   <summary>\r
 461   Initialize a traversal object. The user-specified\r
 462   direction determines whether to begin traversal at the\r
 463   smallest or largest valued node\r
 464   <summary>\r
 465   <param name="trav">The traversal object to initialize</param>\r
 466   <param name="tree">The tree that the object will be attached to</param>\r
 467   <param name="dir">\r
 468   The direction to traverse (0 = ascending, 1 = descending)\r
 469   </param>\r
 470   <returns>A pointer to the smallest or largest data value</returns>\r
 471   <remarks>For jsw_rbtree.c internal use only</remarks>\r
 472 */\r
 473 static void *start ( jsw_rbtrav_t *trav, jsw_rbtree_t *tree, int dir )\r
 474 {\r
 475   trav->tree = tree;\r
 476   trav->it = tree->root;\r
 477   trav->top = 0;\r
 478 \r
 479   /* Save the path for later traversal */\r
 480   if ( trav->it != NULL ) {\r
 481     while ( trav->it->link[dir] != NULL ) {\r
 482       trav->path[trav->top++] = trav->it;\r
 483       trav->it = trav->it->link[dir];\r
 484     }\r
 485   }\r
 486 \r
 487   return trav->it == NULL ? NULL : trav->it->data;\r
 488 }\r
 489 \r
 490 /**\r
 491   <summary>\r
 492   Traverse a red black tree in the user-specified direction\r
 493   <summary>\r
 494   <param name="trav">The initialized traversal object</param>\r
 495   <param name="dir">\r
 496   The direction to traverse (0 = ascending, 1 = descending)\r
 497   </param>\r
 498   <returns>\r
 499   A pointer to the next data value in the specified direction\r
 500   </returns>\r
 501   <remarks>For jsw_rbtree.c internal use only</remarks>\r
 502 */\r
 503 static void *move ( jsw_rbtrav_t *trav, int dir )\r
 504 {\r
 505   if ( trav->it->link[dir] != NULL ) {\r
 506     /* Continue down this branch */\r
 507     trav->path[trav->top++] = trav->it;\r
 508     trav->it = trav->it->link[dir];\r
 509 \r
 510     while ( trav->it->link[!dir] != NULL ) {\r
 511       trav->path[trav->top++] = trav->it;\r
 512       trav->it = trav->it->link[!dir];\r
 513     }\r
 514   }\r
 515   else {\r
 516     /* Move to the next branch */\r
 517     jsw_rbnode_t *last;\r
 518 \r
 519     do {\r
 520       if ( trav->top == 0 ) {\r
 521         trav->it = NULL;\r
 522         break;\r
 523       }\r
 524 \r
 525       last = trav->it;\r
 526       trav->it = trav->path[--trav->top];\r
 527     } while ( last == trav->it->link[dir] );\r
 528   }\r
 529 \r
 530   return trav->it == NULL ? NULL : trav->it->data;\r
 531 }\r
 532 \r
 533 /**\r
 534   <summary>\r
 535   Initialize a traversal object to the smallest valued node\r
 536   <summary>\r
 537   <param name="trav">The traversal object to initialize</param>\r
 538   <param name="tree">The tree that the object will be attached to</param>\r
 539   <returns>A pointer to the smallest data value</returns>\r
 540 */\r
 541 void *jsw_rbtfirst ( jsw_rbtrav_t *trav, jsw_rbtree_t *tree )\r
 542 {\r
 543   return start ( trav, tree, 0 ); /* Min value */\r
 544 }\r
 545 \r
 546 /**\r
 547   <summary>\r
 548   Initialize a traversal object to the largest valued node\r
 549   <summary>\r
 550   <param name="trav">The traversal object to initialize</param>\r
 551   <param name="tree">The tree that the object will be attached to</param>\r
 552   <returns>A pointer to the largest data value</returns>\r
 553 */\r
 554 void *jsw_rbtlast ( jsw_rbtrav_t *trav, jsw_rbtree_t *tree )\r
 555 {\r
 556   return start ( trav, tree, 1 ); /* Max value */\r
 557 }\r
 558 \r
 559 /**\r
 560   <summary>\r
 561   Traverse to the next value in ascending order\r
 562   <summary>\r
 563   <param name="trav">The initialized traversal object</param>\r
 564   <returns>A pointer to the next value in ascending order</returns>\r
 565 */\r
 566 void *jsw_rbtnext ( jsw_rbtrav_t *trav )\r
 567 {\r
 568   return move ( trav, 1 ); /* Toward larger items */\r
 569 }\r
 570 \r
 571 /**\r
 572   <summary>\r
 573   Traverse to the next value in descending order\r
 574   <summary>\r
 575   <param name="trav">The initialized traversal object</param>\r
 576   <returns>A pointer to the next value in descending order</returns>\r
 577 */\r
 578 void *jsw_rbtprev ( jsw_rbtrav_t *trav )\r
 579 {\r
 580   return move ( trav, 0 ); /* Toward smaller items */\r
 581 }