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"
12 #define HEIGHT_LIMIT 64 /* Tallest allowable tree */
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 */
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) */
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 */
38 Checks the color of a red black node
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>
44 static int is_red ( jsw_rbnode_t *root )
46 return root != NULL && root->red == 1;
51 Performs a single red black rotation in the specified direction
52 This function assumes that all nodes are valid for a rotation
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>
59 static jsw_rbnode_t *jsw_single ( jsw_rbnode_t *root, int dir )
61 jsw_rbnode_t *save = root->link[!dir];
63 root->link[!dir] = save->link[dir];
64 save->link[dir] = root;
74 Performs a double red black rotation in the specified direction
75 This function assumes that all nodes are valid for a rotation
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>
82 static jsw_rbnode_t *jsw_double ( jsw_rbnode_t *root, int dir )
84 root->link[!dir] = jsw_single ( root->link[!dir], !dir );
86 return jsw_single ( root, dir );
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
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>
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
103 static jsw_rbnode_t *new_node ( jsw_rbtree_t *tree, void *data )
105 jsw_rbnode_t *rn = malloc ( sizeof *rn );
111 rn->data = tree->dup ( data );
112 rn->link[0] = rn->link[1] = NULL;
119 Creates and initializes an empty red black tree with
120 user-defined comparison, data copy, and data release operations
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>
127 The returned pointer must be released with jsw_rbdelete
130 jsw_rbtree_t *jsw_rbnew ( cmp_f cmp, dup_f dup, rel_f rel )
132 jsw_rbtree_t *rt = malloc ( sizeof *rt );
148 Releases a valid red black tree
150 <param name="tree">The tree to release</param>
152 The tree must have been created using jsw_rbnew
155 void jsw_rbdelete ( jsw_rbtree_t *tree )
157 jsw_rbnode_t *it = tree->root;
161 Rotate away the left links so that
162 we can treat this like the destruction
165 while ( it != NULL ) {
166 if ( it->link[0] == NULL ) {
167 /* No left links, just kill the node and move on */
169 tree->rel ( it->data );
173 /* Rotate away the left link and check again */
175 it->link[0] = save->link[1];
187 Search for a copy of the specified
188 node data in a red black tree
190 <param name="tree">The tree to search</param>
191 <param name="data">The data value to search for</param>
193 A pointer to the data value stored in the tree,
194 or a null pointer if no data could be found
197 void *jsw_rbfind ( jsw_rbtree_t *tree, void *data )
199 jsw_rbnode_t *it = tree->root;
201 while ( it != NULL ) {
202 int cmp = tree->cmp ( it->data, data );
208 If the tree supports duplicates, they should be
209 chained to the right subtree for this to work
211 it = it->link[cmp < 0];
214 return it == NULL ? NULL : it->data;
219 Insert a copy of the user-specified
220 data into a red black tree
222 <param name="tree">The tree to insert into</param>
223 <param name="data">The data value to insert</param>
225 1 if the value was inserted successfully,
226 0 if the insertion failed for any reason
229 int jsw_rbinsert ( jsw_rbtree_t *tree, void *data )
231 if ( tree->root == NULL ) {
233 We have an empty tree; attach the
234 new node directly to the root
236 tree->root = new_node ( tree, data );
238 if ( tree->root == NULL )
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;
247 /* Set up our helpers */
250 q = t->link[1] = tree->root;
252 /* Search down the tree for a place to insert */
255 /* Insert a new node at the first null link */
256 p->link[dir] = q = new_node ( tree, data );
261 else if ( is_red ( q->link[0] ) && is_red ( q->link[1] ) ) {
262 /* Simple red violation: color flip */
268 if ( is_red ( q ) && is_red ( p ) ) {
269 /* Hard red violation: rotations necessary */
270 int dir2 = t->link[1] == g;
272 if ( q == p->link[last] )
273 t->link[dir2] = jsw_single ( g, !last );
275 t->link[dir2] = jsw_double ( g, !last );
279 Stop working if we inserted a node. This
280 check also disallows duplicates in the tree
282 if ( tree->cmp ( q->data, data ) == 0 )
286 dir = tree->cmp ( q->data, data ) < 0;
288 /* Move the helpers down */
296 /* Update the root (it may be different) */
297 tree->root = head.link[1];
300 /* Make the root black for simplified logic */
309 Remove a node from a red black tree
310 that matches the user-specified data
312 <param name="tree">The tree to remove from</param>
313 <param name="data">The data value to search for</param>
315 1 if the value was removed successfully,
316 0 if the removal failed for any reason
319 The most common failure reason should be
320 that the data was not found in the tree
323 int jsw_rberase ( jsw_rbtree_t *tree, void *data )
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 */
331 /* Set up our helpers */
334 q->link[1] = tree->root;
337 Search and push a red node down
338 to fix red violations as we go
340 while ( q->link[dir] != NULL ) {
343 /* Move the helpers down */
346 dir = tree->cmp ( q->data, data ) < 0;
349 Save the node with matching data and keep
350 going; we'll do removal tasks at the end
352 if ( tree->cmp ( q->data, data ) == 0 )
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];
363 if ( !is_red ( s->link[!last] ) && !is_red ( s->link[last] ) ) {
370 int dir2 = g->link[1] == p;
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 );
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;
387 /* Replace and remove the saved node */
389 tree->rel ( f->data );
391 p->link[p->link[1] == q] =
392 q->link[q->link[0] == NULL];
396 /* Update the root (it may be different) */
397 tree->root = head.link[1];
399 /* Make the root black for simplified logic */
400 if ( tree->root != NULL )
411 Gets the number of nodes in a red black tree
413 <param name="tree">The tree to calculate a size for</param>
414 <returns>The number of nodes in the tree</returns>
416 size_t jsw_rbsize ( jsw_rbtree_t *tree )
423 Create a new traversal object
425 <returns>A pointer to the new object</returns>
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
432 jsw_rbtrav_t *jsw_rbtnew ( void )
434 return malloc ( sizeof ( jsw_rbtrav_t ) );
439 Release a traversal object
441 <param name="trav">The object to release</param>
443 The object must have been created with jsw_rbtnew
446 void jsw_rbtdelete ( jsw_rbtrav_t *trav )
453 Initialize a traversal object. The user-specified
454 direction determines whether to begin traversal at the
455 smallest or largest valued node
457 <param name="trav">The traversal object to initialize</param>
458 <param name="tree">The tree that the object will be attached to</param>
460 The direction to traverse (0 = ascending, 1 = descending)
462 <returns>A pointer to the smallest or largest data value</returns>
463 <remarks>For jsw_rbtree.c internal use only</remarks>
465 static void *start ( jsw_rbtrav_t *trav, jsw_rbtree_t *tree, int dir )
468 trav->it = tree->root;
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];
479 return trav->it == NULL ? NULL : trav->it->data;
484 Traverse a red black tree in the user-specified direction
486 <param name="trav">The initialized traversal object</param>
488 The direction to traverse (0 = ascending, 1 = descending)
491 A pointer to the next data value in the specified direction
493 <remarks>For jsw_rbtree.c internal use only</remarks>
495 static void *move ( jsw_rbtrav_t *trav, int dir )
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];
502 while ( trav->it->link[!dir] != NULL ) {
503 trav->path[trav->top++] = trav->it;
504 trav->it = trav->it->link[!dir];
508 /* Move to the next branch */
512 if ( trav->top == 0 ) {
518 trav->it = trav->path[--trav->top];
519 } while ( last == trav->it->link[dir] );
522 return trav->it == NULL ? NULL : trav->it->data;
527 Initialize a traversal object to the smallest valued node
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>
533 void *jsw_rbtfirst ( jsw_rbtrav_t *trav, jsw_rbtree_t *tree )
535 return start ( trav, tree, 0 ); /* Min value */
540 Initialize a traversal object to the largest valued node
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>
546 void *jsw_rbtlast ( jsw_rbtrav_t *trav, jsw_rbtree_t *tree )
548 return start ( trav, tree, 1 ); /* Max value */
553 Traverse to the next value in ascending order
555 <param name="trav">The initialized traversal object</param>
556 <returns>A pointer to the next value in ascending order</returns>
558 void *jsw_rbtnext ( jsw_rbtrav_t *trav )
560 return move ( trav, 1 ); /* Toward larger items */
565 Traverse to the next value in descending order
567 <param name="trav">The initialized traversal object</param>
568 <returns>A pointer to the next value in descending order</returns>
570 void *jsw_rbtprev ( jsw_rbtrav_t *trav )
572 return move ( trav, 0 ); /* Toward smaller items */