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