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

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