2 Red Black balanced tree library
4 > Created (Julienne Walker): August 23, 2003
5 > Modified (Julienne Walker): March 14, 2008
7 #include "jsw_rbtree.h"
20 #define HEIGHT_LIMIT 64 /* Tallest allowable tree */
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 */
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) */
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 */
46 Checks the color of a red black node
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>
52 static int is_red ( jsw_rbnode_t *root )
54 return root != NULL && root->red == 1;
59 Performs a single red black rotation in the specified direction
60 This function assumes that all nodes are valid for a rotation
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>
67 static jsw_rbnode_t *jsw_single ( jsw_rbnode_t *root, int dir )
69 jsw_rbnode_t *save = root->link[!dir];
71 root->link[!dir] = save->link[dir];
72 save->link[dir] = root;
82 Performs a double red black rotation in the specified direction
83 This function assumes that all nodes are valid for a rotation
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>
90 static jsw_rbnode_t *jsw_double ( jsw_rbnode_t *root, int dir )
92 root->link[!dir] = jsw_single ( root->link[!dir], !dir );
94 return jsw_single ( root, dir );
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
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>
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
111 static jsw_rbnode_t *new_node ( jsw_rbtree_t *tree, void *data )
113 jsw_rbnode_t *rn = (jsw_rbnode_t *)malloc ( sizeof *rn );
119 rn->data = tree->dup ( data );
120 rn->link[0] = rn->link[1] = NULL;
127 Creates and initializes an empty red black tree with
128 user-defined comparison, data copy, and data release operations
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>
135 The returned pointer must be released with jsw_rbdelete
138 jsw_rbtree_t *jsw_rbnew ( cmp_f cmp, dup_f dup, rel_f rel )
140 jsw_rbtree_t *rt = (jsw_rbtree_t *)malloc ( sizeof *rt );
156 Releases a valid red black tree
158 <param name="tree">The tree to release</param>
160 The tree must have been created using jsw_rbnew
163 void jsw_rbdelete ( jsw_rbtree_t *tree )
165 jsw_rbnode_t *it = tree->root;
169 Rotate away the left links so that
170 we can treat this like the destruction
173 while ( it != NULL ) {
174 if ( it->link[0] == NULL ) {
175 /* No left links, just kill the node and move on */
177 tree->rel ( it->data );
181 /* Rotate away the left link and check again */
183 it->link[0] = save->link[1];
195 Search for a copy of the specified
196 node data in a red black tree
198 <param name="tree">The tree to search</param>
199 <param name="data">The data value to search for</param>
201 A pointer to the data value stored in the tree,
202 or a null pointer if no data could be found
205 void *jsw_rbfind ( jsw_rbtree_t *tree, void *data )
207 jsw_rbnode_t *it = tree->root;
209 while ( it != NULL ) {
210 int cmp = tree->cmp ( it->data, data );
216 If the tree supports duplicates, they should be
217 chained to the right subtree for this to work
219 it = it->link[cmp < 0];
222 return it == NULL ? NULL : it->data;
227 Insert a copy of the user-specified
228 data into a red black tree
230 <param name="tree">The tree to insert into</param>
231 <param name="data">The data value to insert</param>
233 1 if the value was inserted successfully,
234 0 if the insertion failed for any reason
237 int jsw_rbinsert ( jsw_rbtree_t *tree, void *data )
239 if ( tree->root == NULL ) {
241 We have an empty tree; attach the
242 new node directly to the root
244 tree->root = new_node ( tree, data );
246 if ( tree->root == NULL )
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;
255 /* Set up our helpers */
258 q = t->link[1] = tree->root;
260 /* Search down the tree for a place to insert */
263 /* Insert a new node at the first null link */
264 p->link[dir] = q = new_node ( tree, data );
269 else if ( is_red ( q->link[0] ) && is_red ( q->link[1] ) ) {
270 /* Simple red violation: color flip */
276 if ( is_red ( q ) && is_red ( p ) ) {
277 /* Hard red violation: rotations necessary */
278 int dir2 = t->link[1] == g;
280 if ( q == p->link[last] )
281 t->link[dir2] = jsw_single ( g, !last );
283 t->link[dir2] = jsw_double ( g, !last );
287 Stop working if we inserted a node. This
288 check also disallows duplicates in the tree
290 if ( tree->cmp ( q->data, data ) == 0 )
294 dir = tree->cmp ( q->data, data ) < 0;
296 /* Move the helpers down */
304 /* Update the root (it may be different) */
305 tree->root = head.link[1];
308 /* Make the root black for simplified logic */
317 Remove a node from a red black tree
318 that matches the user-specified data
320 <param name="tree">The tree to remove from</param>
321 <param name="data">The data value to search for</param>
323 1 if the value was removed successfully,
324 0 if the removal failed for any reason
327 The most common failure reason should be
328 that the data was not found in the tree
331 int jsw_rberase ( jsw_rbtree_t *tree, void *data )
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 */
339 /* Set up our helpers */
342 q->link[1] = tree->root;
345 Search and push a red node down
346 to fix red violations as we go
348 while ( q->link[dir] != NULL ) {
351 /* Move the helpers down */
354 dir = tree->cmp ( q->data, data ) < 0;
357 Save the node with matching data and keep
358 going; we'll do removal tasks at the end
360 if ( tree->cmp ( q->data, data ) == 0 )
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];
371 if ( !is_red ( s->link[!last] ) && !is_red ( s->link[last] ) ) {
378 int dir2 = g->link[1] == p;
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 );
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;
395 /* Replace and remove the saved node */
397 tree->rel ( f->data );
399 p->link[p->link[1] == q] =
400 q->link[q->link[0] == NULL];
404 /* Update the root (it may be different) */
405 tree->root = head.link[1];
407 /* Make the root black for simplified logic */
408 if ( tree->root != NULL )
419 Gets the number of nodes in a red black tree
421 <param name="tree">The tree to calculate a size for</param>
422 <returns>The number of nodes in the tree</returns>
424 size_t jsw_rbsize ( jsw_rbtree_t *tree )
431 Create a new traversal object
433 <returns>A pointer to the new object</returns>
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
440 jsw_rbtrav_t *jsw_rbtnew ( void )
442 return (jsw_rbtrav_t*)malloc ( sizeof ( jsw_rbtrav_t ) );
447 Release a traversal object
449 <param name="trav">The object to release</param>
451 The object must have been created with jsw_rbtnew
454 void jsw_rbtdelete ( jsw_rbtrav_t *trav )
461 Initialize a traversal object. The user-specified
462 direction determines whether to begin traversal at the
463 smallest or largest valued node
465 <param name="trav">The traversal object to initialize</param>
466 <param name="tree">The tree that the object will be attached to</param>
468 The direction to traverse (0 = ascending, 1 = descending)
470 <returns>A pointer to the smallest or largest data value</returns>
471 <remarks>For jsw_rbtree.c internal use only</remarks>
473 static void *start ( jsw_rbtrav_t *trav, jsw_rbtree_t *tree, int dir )
476 trav->it = tree->root;
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];
487 return trav->it == NULL ? NULL : trav->it->data;
492 Traverse a red black tree in the user-specified direction
494 <param name="trav">The initialized traversal object</param>
496 The direction to traverse (0 = ascending, 1 = descending)
499 A pointer to the next data value in the specified direction
501 <remarks>For jsw_rbtree.c internal use only</remarks>
503 static void *move ( jsw_rbtrav_t *trav, int dir )
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];
510 while ( trav->it->link[!dir] != NULL ) {
511 trav->path[trav->top++] = trav->it;
512 trav->it = trav->it->link[!dir];
516 /* Move to the next branch */
520 if ( trav->top == 0 ) {
526 trav->it = trav->path[--trav->top];
527 } while ( last == trav->it->link[dir] );
530 return trav->it == NULL ? NULL : trav->it->data;
535 Initialize a traversal object to the smallest valued node
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>
541 void *jsw_rbtfirst ( jsw_rbtrav_t *trav, jsw_rbtree_t *tree )
543 return start ( trav, tree, 0 ); /* Min value */
548 Initialize a traversal object to the largest valued node
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>
554 void *jsw_rbtlast ( jsw_rbtrav_t *trav, jsw_rbtree_t *tree )
556 return start ( trav, tree, 1 ); /* Max value */
561 Traverse to the next value in ascending order
563 <param name="trav">The initialized traversal object</param>
564 <returns>A pointer to the next value in ascending order</returns>
566 void *jsw_rbtnext ( jsw_rbtrav_t *trav )
568 return move ( trav, 1 ); /* Toward larger items */
573 Traverse to the next value in descending order
575 <param name="trav">The initialized traversal object</param>
576 <returns>A pointer to the next value in descending order</returns>
578 void *jsw_rbtprev ( jsw_rbtrav_t *trav )
580 return move ( trav, 0 ); /* Toward smaller items */