-/*\r
- Red Black balanced tree library\r
-\r
- > Created (Julienne Walker): August 23, 2003\r
- > Modified (Julienne Walker): March 14, 2008\r
-*/\r
-#include "jsw_rbtree.h"\r
-\r
-#ifdef __cplusplus\r
-#include <cstdlib>\r
-\r
-using std::malloc;\r
-using std::free;\r
-using std::size_t;\r
-#else\r
-#include <stdlib.h>\r
-#endif\r
-\r
-#ifndef HEIGHT_LIMIT\r
-#define HEIGHT_LIMIT 64 /* Tallest allowable tree */\r
-#endif\r
-\r
-typedef struct jsw_rbnode {\r
- int red; /* Color (1=red, 0=black) */\r
- void *data; /* User-defined content */\r
- struct jsw_rbnode *link[2]; /* Left (0) and right (1) links */\r
-} jsw_rbnode_t;\r
-\r
-struct jsw_rbtree {\r
- jsw_rbnode_t *root; /* Top of the tree */\r
- cmp_f cmp; /* Compare two items */\r
- dup_f dup; /* Clone an item (user-defined) */\r
- rel_f rel; /* Destroy an item (user-defined) */\r
- size_t size; /* Number of items (user-defined) */\r
-};\r
-\r
-struct jsw_rbtrav {\r
- jsw_rbtree_t *tree; /* Paired tree */\r
- jsw_rbnode_t *it; /* Current node */\r
- jsw_rbnode_t *path[HEIGHT_LIMIT]; /* Traversal path */\r
- size_t top; /* Top of stack */\r
-};\r
-\r
-/**\r
- <summary>\r
- Checks the color of a red black node\r
- <summary>\r
- <param name="root">The node to check</param>\r
- <returns>1 for a red node, 0 for a black node</returns>\r
- <remarks>For jsw_rbtree.c internal use only</remarks>\r
-*/\r
-static int is_red ( jsw_rbnode_t *root )\r
-{\r
- return root != NULL && root->red == 1;\r
-}\r
-\r
-/**\r
- <summary>\r
- Performs a single red black rotation in the specified direction\r
- This function assumes that all nodes are valid for a rotation\r
- <summary>\r
- <param name="root">The original root to rotate around</param>\r
- <param name="dir">The direction to rotate (0 = left, 1 = right)</param>\r
- <returns>The new root ater rotation</returns>\r
- <remarks>For jsw_rbtree.c internal use only</remarks>\r
-*/\r
-static jsw_rbnode_t *jsw_single ( jsw_rbnode_t *root, int dir )\r
-{\r
- jsw_rbnode_t *save = root->link[!dir];\r
-\r
- root->link[!dir] = save->link[dir];\r
- save->link[dir] = root;\r
-\r
- root->red = 1;\r
- save->red = 0;\r
-\r
- return save;\r
-}\r
-\r
-/**\r
- <summary>\r
- Performs a double red black rotation in the specified direction\r
- This function assumes that all nodes are valid for a rotation\r
- <summary>\r
- <param name="root">The original root to rotate around</param>\r
- <param name="dir">The direction to rotate (0 = left, 1 = right)</param>\r
- <returns>The new root after rotation</returns>\r
- <remarks>For jsw_rbtree.c internal use only</remarks>\r
-*/\r
-static jsw_rbnode_t *jsw_double ( jsw_rbnode_t *root, int dir )\r
-{\r
- root->link[!dir] = jsw_single ( root->link[!dir], !dir );\r
-\r
- return jsw_single ( root, dir );\r
-}\r
-\r
-/**\r
- <summary>\r
- Creates an initializes a new red black node with a copy of\r
- the data. This function does not insert the new node into a tree\r
- <summary>\r
- <param name="tree">The red black tree this node is being created for</param>\r
- <param name="data">The data value that will be stored in this node</param>\r
- <returns>A pointer to the new node</returns>\r
- <remarks>\r
- For jsw_rbtree.c internal use only. The data for this node must\r
- be freed using the same tree's rel function. The returned pointer\r
- must be freed using C's free function\r
- </remarks>\r
-*/\r
-static jsw_rbnode_t *new_node ( jsw_rbtree_t *tree, void *data )\r
-{\r
- jsw_rbnode_t *rn = (jsw_rbnode_t *)malloc ( sizeof *rn );\r
-\r
- if ( rn == NULL )\r
- return NULL;\r
-\r
- rn->red = 1;\r
- rn->data = tree->dup ( data );\r
- rn->link[0] = rn->link[1] = NULL;\r
-\r
- return rn;\r
-}\r
-\r
-/**\r
- <summary>\r
- Creates and initializes an empty red black tree with\r
- user-defined comparison, data copy, and data release operations\r
- <summary>\r
- <param name="cmp">User-defined data comparison function</param>\r
- <param name="dup">User-defined data copy function</param>\r
- <param name="rel">User-defined data release function</param>\r
- <returns>A pointer to the new tree</returns>\r
- <remarks>\r
- The returned pointer must be released with jsw_rbdelete\r
- </remarks>\r
-*/\r
-jsw_rbtree_t *jsw_rbnew ( cmp_f cmp, dup_f dup, rel_f rel )\r
-{\r
- jsw_rbtree_t *rt = (jsw_rbtree_t *)malloc ( sizeof *rt );\r
-\r
- if ( rt == NULL )\r
- return NULL;\r
-\r
- rt->root = NULL;\r
- rt->cmp = cmp;\r
- rt->dup = dup;\r
- rt->rel = rel;\r
- rt->size = 0;\r
-\r
- return rt;\r
-}\r
-\r
-/**\r
- <summary>\r
- Releases a valid red black tree\r
- <summary>\r
- <param name="tree">The tree to release</param>\r
- <remarks>\r
- The tree must have been created using jsw_rbnew\r
- </remarks>\r
-*/\r
-void jsw_rbdelete ( jsw_rbtree_t *tree )\r
-{\r
- jsw_rbnode_t *it = tree->root;\r
- jsw_rbnode_t *save;\r
-\r
- /*\r
- Rotate away the left links so that\r
- we can treat this like the destruction\r
- of a linked list\r
- */\r
- while ( it != NULL ) {\r
- if ( it->link[0] == NULL ) {\r
- /* No left links, just kill the node and move on */\r
- save = it->link[1];\r
- tree->rel ( it->data );\r
- free ( it );\r
- }\r
- else {\r
- /* Rotate away the left link and check again */\r
- save = it->link[0];\r
- it->link[0] = save->link[1];\r
- save->link[1] = it;\r
- }\r
-\r
- it = save;\r
- }\r
-\r
- free ( tree );\r
-}\r
-\r
-/**\r
- <summary>\r
- Search for a copy of the specified\r
- node data in a red black tree\r
- <summary>\r
- <param name="tree">The tree to search</param>\r
- <param name="data">The data value to search for</param>\r
- <returns>\r
- A pointer to the data value stored in the tree,\r
- or a null pointer if no data could be found\r
- </returns>\r
-*/\r
-void *jsw_rbfind ( jsw_rbtree_t *tree, void *data )\r
-{\r
- jsw_rbnode_t *it = tree->root;\r
-\r
- while ( it != NULL ) {\r
- int cmp = tree->cmp ( it->data, data );\r
-\r
- if ( cmp == 0 )\r
- break;\r
-\r
- /*\r
- If the tree supports duplicates, they should be\r
- chained to the right subtree for this to work\r
- */\r
- it = it->link[cmp < 0];\r
- }\r
-\r
- return it == NULL ? NULL : it->data;\r
-}\r
-\r
-/**\r
- <summary>\r
- Insert a copy of the user-specified\r
- data into a red black tree\r
- <summary>\r
- <param name="tree">The tree to insert into</param>\r
- <param name="data">The data value to insert</param>\r
- <returns>\r
- 1 if the value was inserted successfully,\r
- 0 if the insertion failed for any reason\r
- </returns>\r
-*/\r
-int jsw_rbinsert ( jsw_rbtree_t *tree, void *data )\r
-{\r
- if ( tree->root == NULL ) {\r
- /*\r
- We have an empty tree; attach the\r
- new node directly to the root\r
- */\r
- tree->root = new_node ( tree, data );\r
-\r
- if ( tree->root == NULL )\r
- return 0;\r
- }\r
- else {\r
- jsw_rbnode_t head = {0}; /* False tree root */\r
- jsw_rbnode_t *g, *t; /* Grandparent & parent */\r
- jsw_rbnode_t *p, *q; /* Iterator & parent */\r
- int dir = 0, last = 0;\r
-\r
- /* Set up our helpers */\r
- t = &head;\r
- g = p = NULL;\r
- q = t->link[1] = tree->root;\r
-\r
- /* Search down the tree for a place to insert */\r
- for ( ; ; ) {\r
- if ( q == NULL ) {\r
- /* Insert a new node at the first null link */\r
- p->link[dir] = q = new_node ( tree, data );\r
-\r
- if ( q == NULL )\r
- return 0;\r
- }\r
- else if ( is_red ( q->link[0] ) && is_red ( q->link[1] ) ) {\r
- /* Simple red violation: color flip */\r
- q->red = 1;\r
- q->link[0]->red = 0;\r
- q->link[1]->red = 0;\r
- }\r
-\r
- if ( is_red ( q ) && is_red ( p ) ) {\r
- /* Hard red violation: rotations necessary */\r
- int dir2 = t->link[1] == g;\r
-\r
- if ( q == p->link[last] )\r
- t->link[dir2] = jsw_single ( g, !last );\r
- else\r
- t->link[dir2] = jsw_double ( g, !last );\r
- }\r
-\r
- /*\r
- Stop working if we inserted a node. This\r
- check also disallows duplicates in the tree\r
- */\r
- if ( tree->cmp ( q->data, data ) == 0 )\r
- break;\r
-\r
- last = dir;\r
- dir = tree->cmp ( q->data, data ) < 0;\r
-\r
- /* Move the helpers down */\r
- if ( g != NULL )\r
- t = g;\r
-\r
- g = p, p = q;\r
- q = q->link[dir];\r
- }\r
-\r
- /* Update the root (it may be different) */\r
- tree->root = head.link[1];\r
- }\r
-\r
- /* Make the root black for simplified logic */\r
- tree->root->red = 0;\r
- ++tree->size;\r
-\r
- return 1;\r
-}\r
-\r
-/**\r
- <summary>\r
- Remove a node from a red black tree\r
- that matches the user-specified data\r
- <summary>\r
- <param name="tree">The tree to remove from</param>\r
- <param name="data">The data value to search for</param>\r
- <returns>\r
- 1 if the value was removed successfully,\r
- 0 if the removal failed for any reason\r
- </returns>\r
- <remarks>\r
- The most common failure reason should be\r
- that the data was not found in the tree\r
- </remarks>\r
-*/\r
-int jsw_rberase ( jsw_rbtree_t *tree, void *data )\r
-{\r
- if ( tree->root != NULL ) {\r
- jsw_rbnode_t head = {0}; /* False tree root */\r
- jsw_rbnode_t *q, *p, *g; /* Helpers */\r
- jsw_rbnode_t *f = NULL; /* Found item */\r
- int dir = 1;\r
-\r
- /* Set up our helpers */\r
- q = &head;\r
- g = p = NULL;\r
- q->link[1] = tree->root;\r
-\r
- /*\r
- Search and push a red node down\r
- to fix red violations as we go\r
- */\r
- while ( q->link[dir] != NULL ) {\r
- int last = dir;\r
-\r
- /* Move the helpers down */\r
- g = p, p = q;\r
- q = q->link[dir];\r
- dir = tree->cmp ( q->data, data ) < 0;\r
-\r
- /*\r
- Save the node with matching data and keep\r
- going; we'll do removal tasks at the end\r
- */\r
- if ( tree->cmp ( q->data, data ) == 0 )\r
- f = q;\r
-\r
- /* Push the red node down with rotations and color flips */\r
- if ( !is_red ( q ) && !is_red ( q->link[dir] ) ) {\r
- if ( is_red ( q->link[!dir] ) )\r
- p = p->link[last] = jsw_single ( q, dir );\r
- else if ( !is_red ( q->link[!dir] ) ) {\r
- jsw_rbnode_t *s = p->link[!last];\r
-\r
- if ( s != NULL ) {\r
- if ( !is_red ( s->link[!last] ) && !is_red ( s->link[last] ) ) {\r
- /* Color flip */\r
- p->red = 0;\r
- s->red = 1;\r
- q->red = 1;\r
- }\r
- else {\r
- int dir2 = g->link[1] == p;\r
-\r
- if ( is_red ( s->link[last] ) )\r
- g->link[dir2] = jsw_double ( p, last );\r
- else if ( is_red ( s->link[!last] ) )\r
- g->link[dir2] = jsw_single ( p, last );\r
-\r
- /* Ensure correct coloring */\r
- q->red = g->link[dir2]->red = 1;\r
- g->link[dir2]->link[0]->red = 0;\r
- g->link[dir2]->link[1]->red = 0;\r
- }\r
- }\r
- }\r
- }\r
- }\r
-\r
- /* Replace and remove the saved node */\r
- if ( f != NULL ) {\r
- tree->rel ( f->data );\r
- f->data = q->data;\r
- p->link[p->link[1] == q] =\r
- q->link[q->link[0] == NULL];\r
- free ( q );\r
- }\r
-\r
- /* Update the root (it may be different) */\r
- tree->root = head.link[1];\r
-\r
- /* Make the root black for simplified logic */\r
- if ( tree->root != NULL )\r
- tree->root->red = 0;\r
-\r
- --tree->size;\r
- }\r
-\r
- return 1;\r
-}\r
-\r
-/**\r
- <summary>\r
- Gets the number of nodes in a red black tree\r
- <summary>\r
- <param name="tree">The tree to calculate a size for</param>\r
- <returns>The number of nodes in the tree</returns>\r
-*/\r
-size_t jsw_rbsize ( jsw_rbtree_t *tree )\r
-{\r
- return tree->size;\r
-}\r
-\r
-/**\r
- <summary>\r
- Create a new traversal object\r
- <summary>\r
- <returns>A pointer to the new object</returns>\r
- <remarks>\r
- The traversal object is not initialized until\r
- jsw_rbtfirst or jsw_rbtlast are called.\r
- The pointer must be released with jsw_rbtdelete\r
- </remarks>\r
-*/\r
-jsw_rbtrav_t *jsw_rbtnew ( void )\r
-{\r
- return (jsw_rbtrav_t*)malloc ( sizeof ( jsw_rbtrav_t ) );\r
-}\r
-\r
-/**\r
- <summary>\r
- Release a traversal object\r
- <summary>\r
- <param name="trav">The object to release</param>\r
- <remarks>\r
- The object must have been created with jsw_rbtnew\r
- </remarks>\r
-*/\r
-void jsw_rbtdelete ( jsw_rbtrav_t *trav )\r
-{\r
- free ( trav );\r
-}\r
-\r
-/**\r
- <summary>\r
- Initialize a traversal object. The user-specified\r
- direction determines whether to begin traversal at the\r
- smallest or largest valued node\r
- <summary>\r
- <param name="trav">The traversal object to initialize</param>\r
- <param name="tree">The tree that the object will be attached to</param>\r
- <param name="dir">\r
- The direction to traverse (0 = ascending, 1 = descending)\r
- </param>\r
- <returns>A pointer to the smallest or largest data value</returns>\r
- <remarks>For jsw_rbtree.c internal use only</remarks>\r
-*/\r
-static void *start ( jsw_rbtrav_t *trav, jsw_rbtree_t *tree, int dir )\r
-{\r
- trav->tree = tree;\r
- trav->it = tree->root;\r
- trav->top = 0;\r
-\r
- /* Save the path for later traversal */\r
- if ( trav->it != NULL ) {\r
- while ( trav->it->link[dir] != NULL ) {\r
- trav->path[trav->top++] = trav->it;\r
- trav->it = trav->it->link[dir];\r
- }\r
- }\r
-\r
- return trav->it == NULL ? NULL : trav->it->data;\r
-}\r
-\r
-/**\r
- <summary>\r
- Traverse a red black tree in the user-specified direction\r
- <summary>\r
- <param name="trav">The initialized traversal object</param>\r
- <param name="dir">\r
- The direction to traverse (0 = ascending, 1 = descending)\r
- </param>\r
- <returns>\r
- A pointer to the next data value in the specified direction\r
- </returns>\r
- <remarks>For jsw_rbtree.c internal use only</remarks>\r
-*/\r
-static void *move ( jsw_rbtrav_t *trav, int dir )\r
-{\r
- if ( trav->it->link[dir] != NULL ) {\r
- /* Continue down this branch */\r
- trav->path[trav->top++] = trav->it;\r
- trav->it = trav->it->link[dir];\r
-\r
- while ( trav->it->link[!dir] != NULL ) {\r
- trav->path[trav->top++] = trav->it;\r
- trav->it = trav->it->link[!dir];\r
- }\r
- }\r
- else {\r
- /* Move to the next branch */\r
- jsw_rbnode_t *last;\r
-\r
- do {\r
- if ( trav->top == 0 ) {\r
- trav->it = NULL;\r
- break;\r
- }\r
-\r
- last = trav->it;\r
- trav->it = trav->path[--trav->top];\r
- } while ( last == trav->it->link[dir] );\r
- }\r
-\r
- return trav->it == NULL ? NULL : trav->it->data;\r
-}\r
-\r
-/**\r
- <summary>\r
- Initialize a traversal object to the smallest valued node\r
- <summary>\r
- <param name="trav">The traversal object to initialize</param>\r
- <param name="tree">The tree that the object will be attached to</param>\r
- <returns>A pointer to the smallest data value</returns>\r
-*/\r
-void *jsw_rbtfirst ( jsw_rbtrav_t *trav, jsw_rbtree_t *tree )\r
-{\r
- return start ( trav, tree, 0 ); /* Min value */\r
-}\r
-\r
-/**\r
- <summary>\r
- Initialize a traversal object to the largest valued node\r
- <summary>\r
- <param name="trav">The traversal object to initialize</param>\r
- <param name="tree">The tree that the object will be attached to</param>\r
- <returns>A pointer to the largest data value</returns>\r
-*/\r
-void *jsw_rbtlast ( jsw_rbtrav_t *trav, jsw_rbtree_t *tree )\r
-{\r
- return start ( trav, tree, 1 ); /* Max value */\r
-}\r
-\r
-/**\r
- <summary>\r
- Traverse to the next value in ascending order\r
- <summary>\r
- <param name="trav">The initialized traversal object</param>\r
- <returns>A pointer to the next value in ascending order</returns>\r
-*/\r
-void *jsw_rbtnext ( jsw_rbtrav_t *trav )\r
-{\r
- return move ( trav, 1 ); /* Toward larger items */\r
-}\r
-\r
-/**\r
- <summary>\r
- Traverse to the next value in descending order\r
- <summary>\r
- <param name="trav">The initialized traversal object</param>\r
- <returns>A pointer to the next value in descending order</returns>\r
-*/\r
-void *jsw_rbtprev ( jsw_rbtrav_t *trav )\r
-{\r
- return move ( trav, 0 ); /* Toward smaller items */\r
+/*
+ Red Black balanced tree library
+
+ > Created (Julienne Walker): August 23, 2003
+ > Modified (Julienne Walker): March 14, 2008
+*/
+#include "jsw_rbtree.h"
+
+#ifdef __cplusplus
+#include <cstdlib>
+
+using std::malloc;
+using std::free;
+using std::size_t;
+#else
+#include <stdlib.h>
+#endif
+
+#ifndef HEIGHT_LIMIT
+#define HEIGHT_LIMIT 64 /* Tallest allowable tree */
+#endif
+
+typedef struct jsw_rbnode {
+ int red; /* Color (1=red, 0=black) */
+ void *data; /* User-defined content */
+ struct jsw_rbnode *link[2]; /* Left (0) and right (1) links */
+} jsw_rbnode_t;
+
+struct jsw_rbtree {
+ jsw_rbnode_t *root; /* Top of the tree */
+ cmp_f cmp; /* Compare two items */
+ dup_f dup; /* Clone an item (user-defined) */
+ rel_f rel; /* Destroy an item (user-defined) */
+ size_t size; /* Number of items (user-defined) */
+};
+
+struct jsw_rbtrav {
+ jsw_rbtree_t *tree; /* Paired tree */
+ jsw_rbnode_t *it; /* Current node */
+ jsw_rbnode_t *path[HEIGHT_LIMIT]; /* Traversal path */
+ size_t top; /* Top of stack */
+};
+
+/**
+ <summary>
+ Checks the color of a red black node
+ <summary>
+ <param name="root">The node to check</param>
+ <returns>1 for a red node, 0 for a black node</returns>
+ <remarks>For jsw_rbtree.c internal use only</remarks>
+*/
+static int is_red ( jsw_rbnode_t *root )
+{
+ return root != NULL && root->red == 1;
+}
+
+/**
+ <summary>
+ Performs a single red black rotation in the specified direction
+ This function assumes that all nodes are valid for a rotation
+ <summary>
+ <param name="root">The original root to rotate around</param>
+ <param name="dir">The direction to rotate (0 = left, 1 = right)</param>
+ <returns>The new root ater rotation</returns>
+ <remarks>For jsw_rbtree.c internal use only</remarks>
+*/
+static jsw_rbnode_t *jsw_single ( jsw_rbnode_t *root, int dir )
+{
+ jsw_rbnode_t *save = root->link[!dir];
+
+ root->link[!dir] = save->link[dir];
+ save->link[dir] = root;
+
+ root->red = 1;
+ save->red = 0;
+
+ return save;
+}
+
+/**
+ <summary>
+ Performs a double red black rotation in the specified direction
+ This function assumes that all nodes are valid for a rotation
+ <summary>
+ <param name="root">The original root to rotate around</param>
+ <param name="dir">The direction to rotate (0 = left, 1 = right)</param>
+ <returns>The new root after rotation</returns>
+ <remarks>For jsw_rbtree.c internal use only</remarks>
+*/
+static jsw_rbnode_t *jsw_double ( jsw_rbnode_t *root, int dir )
+{
+ root->link[!dir] = jsw_single ( root->link[!dir], !dir );
+
+ return jsw_single ( root, dir );
+}
+
+/**
+ <summary>
+ Creates an initializes a new red black node with a copy of
+ the data. This function does not insert the new node into a tree
+ <summary>
+ <param name="tree">The red black tree this node is being created for</param>
+ <param name="data">The data value that will be stored in this node</param>
+ <returns>A pointer to the new node</returns>
+ <remarks>
+ For jsw_rbtree.c internal use only. The data for this node must
+ be freed using the same tree's rel function. The returned pointer
+ must be freed using C's free function
+ </remarks>
+*/
+static jsw_rbnode_t *new_node ( jsw_rbtree_t *tree, void *data )
+{
+ jsw_rbnode_t *rn = (jsw_rbnode_t *)malloc ( sizeof *rn );
+
+ if ( rn == NULL )
+ return NULL;
+
+ rn->red = 1;
+ rn->data = tree->dup ( data );
+ rn->link[0] = rn->link[1] = NULL;
+
+ return rn;
+}
+
+/**
+ <summary>
+ Creates and initializes an empty red black tree with
+ user-defined comparison, data copy, and data release operations
+ <summary>
+ <param name="cmp">User-defined data comparison function</param>
+ <param name="dup">User-defined data copy function</param>
+ <param name="rel">User-defined data release function</param>
+ <returns>A pointer to the new tree</returns>
+ <remarks>
+ The returned pointer must be released with jsw_rbdelete
+ </remarks>
+*/
+jsw_rbtree_t *jsw_rbnew ( cmp_f cmp, dup_f dup, rel_f rel )
+{
+ jsw_rbtree_t *rt = (jsw_rbtree_t *)malloc ( sizeof *rt );
+
+ if ( rt == NULL )
+ return NULL;
+
+ rt->root = NULL;
+ rt->cmp = cmp;
+ rt->dup = dup;
+ rt->rel = rel;
+ rt->size = 0;
+
+ return rt;
+}
+
+/**
+ <summary>
+ Releases a valid red black tree
+ <summary>
+ <param name="tree">The tree to release</param>
+ <remarks>
+ The tree must have been created using jsw_rbnew
+ </remarks>
+*/
+void jsw_rbdelete ( jsw_rbtree_t *tree )
+{
+ jsw_rbnode_t *it = tree->root;
+ jsw_rbnode_t *save;
+
+ /*
+ Rotate away the left links so that
+ we can treat this like the destruction
+ of a linked list
+ */
+ while ( it != NULL ) {
+ if ( it->link[0] == NULL ) {
+ /* No left links, just kill the node and move on */
+ save = it->link[1];
+ tree->rel ( it->data );
+ free ( it );
+ }
+ else {
+ /* Rotate away the left link and check again */
+ save = it->link[0];
+ it->link[0] = save->link[1];
+ save->link[1] = it;
+ }
+
+ it = save;
+ }
+
+ free ( tree );
+}
+
+/**
+ <summary>
+ Search for a copy of the specified
+ node data in a red black tree
+ <summary>
+ <param name="tree">The tree to search</param>
+ <param name="data">The data value to search for</param>
+ <returns>
+ A pointer to the data value stored in the tree,
+ or a null pointer if no data could be found
+ </returns>
+*/
+void *jsw_rbfind ( jsw_rbtree_t *tree, void *data )
+{
+ jsw_rbnode_t *it = tree->root;
+
+ while ( it != NULL ) {
+ int cmp = tree->cmp ( it->data, data );
+
+ if ( cmp == 0 )
+ break;
+
+ /*
+ If the tree supports duplicates, they should be
+ chained to the right subtree for this to work
+ */
+ it = it->link[cmp < 0];
+ }
+
+ return it == NULL ? NULL : it->data;
+}
+
+/**
+ <summary>
+ Insert a copy of the user-specified
+ data into a red black tree
+ <summary>
+ <param name="tree">The tree to insert into</param>
+ <param name="data">The data value to insert</param>
+ <returns>
+ 1 if the value was inserted successfully,
+ 0 if the insertion failed for any reason
+ </returns>
+*/
+int jsw_rbinsert ( jsw_rbtree_t *tree, void *data )
+{
+ if ( tree->root == NULL ) {
+ /*
+ We have an empty tree; attach the
+ new node directly to the root
+ */
+ tree->root = new_node ( tree, data );
+
+ if ( tree->root == NULL )
+ return 0;
+ }
+ else {
+ jsw_rbnode_t head = {0}; /* False tree root */
+ jsw_rbnode_t *g, *t; /* Grandparent & parent */
+ jsw_rbnode_t *p, *q; /* Iterator & parent */
+ int dir = 0, last = 0;
+
+ /* Set up our helpers */
+ t = &head;
+ g = p = NULL;
+ q = t->link[1] = tree->root;
+
+ /* Search down the tree for a place to insert */
+ for ( ; ; ) {
+ if ( q == NULL ) {
+ /* Insert a new node at the first null link */
+ p->link[dir] = q = new_node ( tree, data );
+
+ if ( q == NULL )
+ return 0;
+ }
+ else if ( is_red ( q->link[0] ) && is_red ( q->link[1] ) ) {
+ /* Simple red violation: color flip */
+ q->red = 1;
+ q->link[0]->red = 0;
+ q->link[1]->red = 0;
+ }
+
+ if ( is_red ( q ) && is_red ( p ) ) {
+ /* Hard red violation: rotations necessary */
+ int dir2 = t->link[1] == g;
+
+ if ( q == p->link[last] )
+ t->link[dir2] = jsw_single ( g, !last );
+ else
+ t->link[dir2] = jsw_double ( g, !last );
+ }
+
+ /*
+ Stop working if we inserted a node. This
+ check also disallows duplicates in the tree
+ */
+ if ( tree->cmp ( q->data, data ) == 0 )
+ break;
+
+ last = dir;
+ dir = tree->cmp ( q->data, data ) < 0;
+
+ /* Move the helpers down */
+ if ( g != NULL )
+ t = g;
+
+ g = p, p = q;
+ q = q->link[dir];
+ }
+
+ /* Update the root (it may be different) */
+ tree->root = head.link[1];
+ }
+
+ /* Make the root black for simplified logic */
+ tree->root->red = 0;
+ ++tree->size;
+
+ return 1;
+}
+
+/**
+ <summary>
+ Remove a node from a red black tree
+ that matches the user-specified data
+ <summary>
+ <param name="tree">The tree to remove from</param>
+ <param name="data">The data value to search for</param>
+ <returns>
+ 1 if the value was removed successfully,
+ 0 if the removal failed for any reason
+ </returns>
+ <remarks>
+ The most common failure reason should be
+ that the data was not found in the tree
+ </remarks>
+*/
+int jsw_rberase ( jsw_rbtree_t *tree, void *data )
+{
+ if ( tree->root != NULL ) {
+ jsw_rbnode_t head = {0}; /* False tree root */
+ jsw_rbnode_t *q, *p, *g; /* Helpers */
+ jsw_rbnode_t *f = NULL; /* Found item */
+ int dir = 1;
+
+ /* Set up our helpers */
+ q = &head;
+ g = p = NULL;
+ q->link[1] = tree->root;
+
+ /*
+ Search and push a red node down
+ to fix red violations as we go
+ */
+ while ( q->link[dir] != NULL ) {
+ int last = dir;
+
+ /* Move the helpers down */
+ g = p, p = q;
+ q = q->link[dir];
+ dir = tree->cmp ( q->data, data ) < 0;
+
+ /*
+ Save the node with matching data and keep
+ going; we'll do removal tasks at the end
+ */
+ if ( tree->cmp ( q->data, data ) == 0 )
+ f = q;
+
+ /* Push the red node down with rotations and color flips */
+ if ( !is_red ( q ) && !is_red ( q->link[dir] ) ) {
+ if ( is_red ( q->link[!dir] ) )
+ p = p->link[last] = jsw_single ( q, dir );
+ else if ( !is_red ( q->link[!dir] ) ) {
+ jsw_rbnode_t *s = p->link[!last];
+
+ if ( s != NULL ) {
+ if ( !is_red ( s->link[!last] ) && !is_red ( s->link[last] ) ) {
+ /* Color flip */
+ p->red = 0;
+ s->red = 1;
+ q->red = 1;
+ }
+ else {
+ int dir2 = g->link[1] == p;
+
+ if ( is_red ( s->link[last] ) )
+ g->link[dir2] = jsw_double ( p, last );
+ else if ( is_red ( s->link[!last] ) )
+ g->link[dir2] = jsw_single ( p, last );
+
+ /* Ensure correct coloring */
+ q->red = g->link[dir2]->red = 1;
+ g->link[dir2]->link[0]->red = 0;
+ g->link[dir2]->link[1]->red = 0;
+ }
+ }
+ }
+ }
+ }
+
+ /* Replace and remove the saved node */
+ if ( f != NULL ) {
+ tree->rel ( f->data );
+ f->data = q->data;
+ p->link[p->link[1] == q] =
+ q->link[q->link[0] == NULL];
+ free ( q );
+ }
+
+ /* Update the root (it may be different) */
+ tree->root = head.link[1];
+
+ /* Make the root black for simplified logic */
+ if ( tree->root != NULL )
+ tree->root->red = 0;
+
+ --tree->size;
+ }
+
+ return 1;
+}
+
+/**
+ <summary>
+ Gets the number of nodes in a red black tree
+ <summary>
+ <param name="tree">The tree to calculate a size for</param>
+ <returns>The number of nodes in the tree</returns>
+*/
+size_t jsw_rbsize ( jsw_rbtree_t *tree )
+{
+ return tree->size;
+}
+
+/**
+ <summary>
+ Create a new traversal object
+ <summary>
+ <returns>A pointer to the new object</returns>
+ <remarks>
+ The traversal object is not initialized until
+ jsw_rbtfirst or jsw_rbtlast are called.
+ The pointer must be released with jsw_rbtdelete
+ </remarks>
+*/
+jsw_rbtrav_t *jsw_rbtnew ( void )
+{
+ return (jsw_rbtrav_t*)malloc ( sizeof ( jsw_rbtrav_t ) );
+}
+
+/**
+ <summary>
+ Release a traversal object
+ <summary>
+ <param name="trav">The object to release</param>
+ <remarks>
+ The object must have been created with jsw_rbtnew
+ </remarks>
+*/
+void jsw_rbtdelete ( jsw_rbtrav_t *trav )
+{
+ free ( trav );
+}
+
+/**
+ <summary>
+ Initialize a traversal object. The user-specified
+ direction determines whether to begin traversal at the
+ smallest or largest valued node
+ <summary>
+ <param name="trav">The traversal object to initialize</param>
+ <param name="tree">The tree that the object will be attached to</param>
+ <param name="dir">
+ The direction to traverse (0 = ascending, 1 = descending)
+ </param>
+ <returns>A pointer to the smallest or largest data value</returns>
+ <remarks>For jsw_rbtree.c internal use only</remarks>
+*/
+static void *start ( jsw_rbtrav_t *trav, jsw_rbtree_t *tree, int dir )
+{
+ trav->tree = tree;
+ trav->it = tree->root;
+ trav->top = 0;
+
+ /* Save the path for later traversal */
+ if ( trav->it != NULL ) {
+ while ( trav->it->link[dir] != NULL ) {
+ trav->path[trav->top++] = trav->it;
+ trav->it = trav->it->link[dir];
+ }
+ }
+
+ return trav->it == NULL ? NULL : trav->it->data;
+}
+
+/**
+ <summary>
+ Traverse a red black tree in the user-specified direction
+ <summary>
+ <param name="trav">The initialized traversal object</param>
+ <param name="dir">
+ The direction to traverse (0 = ascending, 1 = descending)
+ </param>
+ <returns>
+ A pointer to the next data value in the specified direction
+ </returns>
+ <remarks>For jsw_rbtree.c internal use only</remarks>
+*/
+static void *move ( jsw_rbtrav_t *trav, int dir )
+{
+ if ( trav->it->link[dir] != NULL ) {
+ /* Continue down this branch */
+ trav->path[trav->top++] = trav->it;
+ trav->it = trav->it->link[dir];
+
+ while ( trav->it->link[!dir] != NULL ) {
+ trav->path[trav->top++] = trav->it;
+ trav->it = trav->it->link[!dir];
+ }
+ }
+ else {
+ /* Move to the next branch */
+ jsw_rbnode_t *last;
+
+ do {
+ if ( trav->top == 0 ) {
+ trav->it = NULL;
+ break;
+ }
+
+ last = trav->it;
+ trav->it = trav->path[--trav->top];
+ } while ( last == trav->it->link[dir] );
+ }
+
+ return trav->it == NULL ? NULL : trav->it->data;
+}
+
+/**
+ <summary>
+ Initialize a traversal object to the smallest valued node
+ <summary>
+ <param name="trav">The traversal object to initialize</param>
+ <param name="tree">The tree that the object will be attached to</param>
+ <returns>A pointer to the smallest data value</returns>
+*/
+void *jsw_rbtfirst ( jsw_rbtrav_t *trav, jsw_rbtree_t *tree )
+{
+ return start ( trav, tree, 0 ); /* Min value */
+}
+
+/**
+ <summary>
+ Initialize a traversal object to the largest valued node
+ <summary>
+ <param name="trav">The traversal object to initialize</param>
+ <param name="tree">The tree that the object will be attached to</param>
+ <returns>A pointer to the largest data value</returns>
+*/
+void *jsw_rbtlast ( jsw_rbtrav_t *trav, jsw_rbtree_t *tree )
+{
+ return start ( trav, tree, 1 ); /* Max value */
+}
+
+/**
+ <summary>
+ Traverse to the next value in ascending order
+ <summary>
+ <param name="trav">The initialized traversal object</param>
+ <returns>A pointer to the next value in ascending order</returns>
+*/
+void *jsw_rbtnext ( jsw_rbtrav_t *trav )
+{
+ return move ( trav, 1 ); /* Toward larger items */
+}
+
+/**
+ <summary>
+ Traverse to the next value in descending order
+ <summary>
+ <param name="trav">The initialized traversal object</param>
+ <returns>A pointer to the next value in descending order</returns>
+*/
+void *jsw_rbtprev ( jsw_rbtrav_t *trav )
+{
+ return move ( trav, 0 ); /* Toward smaller items */
}
\ No newline at end of file
projects / jsw / blobdiff