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