--- /dev/null
+/*\r
+ Andersson tree library\r
+\r
+ > Created (Julienne Walker): September 10, 2005\r
+ > Corrections (James Bucanek): April 10, 2006\r
+ 1) Typo in jsw_aerase:\r
+ up != 0 should be top != 0\r
+ 2) Bug in jsw_aerase:\r
+ skew ( path[top] ) should be skew ( up )\r
+ split ( path[top] ) should be split ( up )\r
+ 3) Bug in skew and split macros:\r
+ Condition should test for nil\r
+ 4) Bug in jsw_aerase:\r
+ Search for successor should save the path\r
+*/\r
+#include "jsw_atree.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_anode {\r
+ int level; /* Horizontal level for balance */\r
+ void *data; /* User-defined content */\r
+ struct jsw_anode *link[2]; /* Left (0) and right (1) links */\r
+} jsw_anode_t;\r
+\r
+struct jsw_atree {\r
+ jsw_anode_t *root; /* Top of the tree */\r
+ jsw_anode_t *nil; /* End of tree sentinel */\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_atrav {\r
+ jsw_atree_t *tree; /* Paired tree */\r
+ jsw_anode_t *it; /* Current node */\r
+ jsw_anode_t *path[HEIGHT_LIMIT]; /* Traversal path */\r
+ size_t top; /* Top of stack */\r
+};\r
+\r
+/* Remove left horizontal links */\r
+#define skew(t) do { \\r
+ if ( t->link[0]->level == t->level && t->level != 0 ) { \\r
+ jsw_anode_t *save = t->link[0]; \\r
+ t->link[0] = save->link[1]; \\r
+ save->link[1] = t; \\r
+ t = save; \\r
+ } \\r
+} while(0)\r
+\r
+/* Remove consecutive horizontal links */\r
+#define split(t) do { \\r
+ if ( t->link[1]->link[1]->level == t->level && t->level != 0 ) { \\r
+ jsw_anode_t *save = t->link[1]; \\r
+ t->link[1] = save->link[0]; \\r
+ save->link[0] = t; \\r
+ t = save; \\r
+ ++t->level; \\r
+ } \\r
+} while(0)\r
+\r
+static jsw_anode_t *new_node ( jsw_atree_t *tree, void *data )\r
+{\r
+ jsw_anode_t *rn = (jsw_anode_t *)malloc ( sizeof *rn );\r
+\r
+ if ( rn == NULL )\r
+ return tree->nil;\r
+\r
+ rn->level = 1;\r
+ rn->data = tree->dup ( data );\r
+ rn->link[0] = rn->link[1] = tree->nil;\r
+\r
+ return rn;\r
+}\r
+\r
+jsw_atree_t *jsw_anew ( cmp_f cmp, dup_f dup, rel_f rel )\r
+{\r
+ jsw_atree_t *rt = (jsw_atree_t *)malloc ( sizeof *rt );\r
+\r
+ if ( rt == NULL )\r
+ return NULL;\r
+\r
+ /* Initialize sentinel */\r
+ rt->nil = (jsw_anode_t *)malloc ( sizeof *rt->nil );\r
+ if ( rt->nil == NULL ) {\r
+ free ( rt );\r
+ return NULL;\r
+ }\r
+\r
+ rt->nil->data = NULL; /* Simplifies some ops */\r
+ rt->nil->level = 0;\r
+ rt->nil->link[0] = rt->nil->link[1] = rt->nil;\r
+\r
+ /* Initialize tree */\r
+ rt->root = rt->nil;\r
+ rt->cmp = cmp;\r
+ rt->dup = dup;\r
+ rt->rel = rel;\r
+ rt->size = 0;\r
+\r
+ return rt;\r
+}\r
+\r
+void jsw_adelete ( jsw_atree_t *tree )\r
+{\r
+ jsw_anode_t *it = tree->root;\r
+ jsw_anode_t *save;\r
+\r
+ /* Destruction by rotation */\r
+ while ( it != tree->nil ) {\r
+ if ( it->link[0] == tree->nil ) {\r
+ /* Remove node */\r
+ save = it->link[1];\r
+ tree->rel ( it->data );\r
+ free ( it );\r
+ }\r
+ else {\r
+ /* Rotate right */\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
+ /* Finalize destruction */\r
+ free ( tree->nil );\r
+ free ( tree );\r
+}\r
+\r
+void *jsw_afind ( jsw_atree_t *tree, void *data )\r
+{\r
+ jsw_anode_t *it = tree->root;\r
+\r
+ while ( it != tree->nil ) {\r
+ int cmp = tree->cmp ( it->data, data );\r
+\r
+ if ( cmp == 0 )\r
+ break;\r
+\r
+ it = it->link[cmp < 0];\r
+ }\r
+\r
+ /* nil->data == NULL */\r
+ return it->data;\r
+}\r
+\r
+int jsw_ainsert ( jsw_atree_t *tree, void *data )\r
+{\r
+ if ( tree->root == tree->nil ) {\r
+ /* Empty tree case */\r
+ tree->root = new_node ( tree, data );\r
+ if ( tree->root == tree->nil )\r
+ return 0;\r
+ }\r
+ else {\r
+ jsw_anode_t *it = tree->root;\r
+ jsw_anode_t *path[HEIGHT_LIMIT];\r
+ int top = 0, dir;\r
+\r
+ /* Find a spot and save the path */\r
+ for ( ; ; ) {\r
+ path[top++] = it;\r
+ dir = tree->cmp ( it->data, data ) < 0;\r
+\r
+ if ( it->link[dir] == tree->nil )\r
+ break;\r
+\r
+ it = it->link[dir];\r
+ }\r
+\r
+ /* Create a new item */\r
+ it->link[dir] = new_node ( tree, data );\r
+ if ( it->link[dir] == tree->nil )\r
+ return 0;\r
+\r
+ /* Walk back and rebalance */\r
+ while ( --top >= 0 ) {\r
+ /* Which child? */\r
+ if ( top != 0 )\r
+ dir = path[top - 1]->link[1] == path[top];\r
+\r
+ skew ( path[top] );\r
+ split ( path[top] );\r
+\r
+ /* Fix the parent */\r
+ if ( top != 0 )\r
+ path[top - 1]->link[dir] = path[top];\r
+ else\r
+ tree->root = path[top];\r
+ }\r
+ }\r
+\r
+ ++tree->size;\r
+\r
+ return 1;\r
+}\r
+\r
+int jsw_aerase ( jsw_atree_t *tree, void *data )\r
+{\r
+ if ( tree->root == tree->nil )\r
+ return 0;\r
+ else {\r
+ jsw_anode_t *it = tree->root;\r
+ jsw_anode_t *path[HEIGHT_LIMIT];\r
+ int top = 0, dir, cmp;\r
+\r
+ /* Find node to remove and save path */\r
+ for ( ; ; ) {\r
+ path[top++] = it;\r
+\r
+ if ( it == tree->nil )\r
+ return 0;\r
+\r
+ cmp = tree->cmp ( it->data, data );\r
+ if ( cmp == 0 )\r
+ break;\r
+\r
+ dir = cmp < 0;\r
+ it = it->link[dir];\r
+ }\r
+\r
+ /* Remove the found node */\r
+ if ( it->link[0] == tree->nil\r
+ || it->link[1] == tree->nil )\r
+ {\r
+ /* Single child case */\r
+ int dir2 = it->link[0] == tree->nil;\r
+\r
+ /* Unlink the item */\r
+ if ( --top != 0 )\r
+ path[top - 1]->link[dir] = it->link[dir2];\r
+ else\r
+ tree->root = it->link[1];\r
+\r
+ tree->rel ( it->data );\r
+ free ( it );\r
+ }\r
+ else {\r
+ /* Two child case */\r
+ jsw_anode_t *heir = it->link[1];\r
+ jsw_anode_t *prev = it;\r
+\r
+ while ( heir->link[0] != tree->nil ) {\r
+ path[top++] = prev = heir;\r
+ heir = heir->link[0];\r
+ }\r
+\r
+ /*\r
+ Order is important!\r
+ (free item, replace item, free heir)\r
+ */\r
+ tree->rel ( it->data );\r
+ it->data = heir->data;\r
+ prev->link[prev == it] = heir->link[1];\r
+ free ( heir );\r
+ }\r
+\r
+ /* Walk back up and rebalance */\r
+ while ( --top >= 0 ) {\r
+ jsw_anode_t *up = path[top];\r
+\r
+ if ( top != 0 )\r
+ dir = path[top - 1]->link[1] == up;\r
+\r
+ /* Rebalance (aka. black magic) */\r
+ if ( up->link[0]->level < up->level - 1\r
+ || up->link[1]->level < up->level - 1 )\r
+ {\r
+ if ( up->link[1]->level > --up->level )\r
+ up->link[1]->level = up->level;\r
+\r
+ /* Order is important! */\r
+ skew ( up );\r
+ skew ( up->link[1] );\r
+ skew ( up->link[1]->link[1] );\r
+ split ( up );\r
+ split ( up->link[1] );\r
+ }\r
+\r
+ /* Fix the parent */\r
+ if ( top != 0 )\r
+ path[top - 1]->link[dir] = up;\r
+ else\r
+ tree->root = up;\r
+ }\r
+ }\r
+\r
+ --tree->size;\r
+\r
+ return 1;\r
+}\r
+\r
+size_t jsw_asize ( jsw_atree_t *tree )\r
+{\r
+ return tree->size;\r
+}\r
+\r
+jsw_atrav_t *jsw_atnew ( void )\r
+{\r
+ return malloc ( sizeof ( jsw_atrav_t ) );\r
+}\r
+\r
+void jsw_atdelete ( jsw_atrav_t *trav )\r
+{\r
+ free ( trav );\r
+}\r
+\r
+/*\r
+ First step in traversal,\r
+ handles min and max\r
+*/\r
+static void *start ( jsw_atrav_t *trav,\r
+ jsw_atree_t *tree, int dir )\r
+{\r
+ trav->tree = tree;\r
+ trav->it = tree->root;\r
+ trav->top = 0;\r
+\r
+ /* Build a path to work with */\r
+ if ( trav->it != tree->nil ) {\r
+ while ( trav->it->link[dir] != tree->nil ) {\r
+ trav->path[trav->top++] = trav->it;\r
+ trav->it = trav->it->link[dir];\r
+ }\r
+ }\r
+\r
+ /* Could be nil, but nil->data == NULL */\r
+ return trav->it->data;\r
+}\r
+\r
+/*\r
+ Subsequent traversal steps,\r
+ handles ascending and descending\r
+*/\r
+static void *move ( jsw_atrav_t *trav, int dir )\r
+{\r
+ jsw_anode_t *nil = trav->tree->nil;\r
+\r
+ if ( trav->it->link[dir] != nil ) {\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] != nil ) {\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_anode_t *last;\r
+\r
+ do {\r
+ if ( trav->top == 0 ) {\r
+ trav->it = nil;\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
+ /* Could be nil, but nil->data == NULL */\r
+ return trav->it->data;\r
+}\r
+\r
+void *jsw_atfirst ( jsw_atrav_t *trav, jsw_atree_t *tree )\r
+{\r
+ return start ( trav, tree, 0 ); /* Min value */\r
+}\r
+\r
+void *jsw_atlast ( jsw_atrav_t *trav, jsw_atree_t *tree )\r
+{\r
+ return start ( trav, tree, 1 ); /* Max value */\r
+}\r
+\r
+void *jsw_atnext ( jsw_atrav_t *trav )\r
+{\r
+ return move ( trav, 1 ); /* Toward larger items */\r
+}\r
+\r
+void *jsw_atprev ( jsw_atrav_t *trav )\r
+{\r
+ return move ( trav, 0 ); /* Toward smaller items */\r
+}\r
--- /dev/null
+#ifndef JSW_ATREE_H\r
+#define JSW_ATREE_H\r
+\r
+/*\r
+ Andersson tree library\r
+\r
+ > Created (Julienne Walker): September 10, 2005\r
+\r
+ This code is in the public domain. Anyone may\r
+ use it or change it in any way that they see\r
+ fit. The author assumes no responsibility for \r
+ damages incurred through use of the original\r
+ code or any variations thereof.\r
+\r
+ It is requested, but not required, that due\r
+ credit is given to the original author and\r
+ anyone who has modified the code through\r
+ a header comment, such as this one.\r
+*/\r
+#ifdef __cplusplus\r
+#include <cstddef>\r
+\r
+using std::size_t;\r
+\r
+extern "C" {\r
+#else\r
+#include <stddef.h>\r
+#endif\r
+\r
+/* Opaque types */\r
+typedef struct jsw_atree jsw_atree_t;\r
+typedef struct jsw_atrav jsw_atrav_t;\r
+\r
+/* User-defined item handling */\r
+typedef int (*cmp_f) ( const void *p1, const void *p2 );\r
+typedef void *(*dup_f) ( void *p );\r
+typedef void (*rel_f) ( void *p );\r
+\r
+/* Andersson tree functions */\r
+jsw_atree_t *jsw_anew ( cmp_f cmp, dup_f dup, rel_f rel );\r
+void jsw_adelete ( jsw_atree_t *tree );\r
+void *jsw_afind ( jsw_atree_t *tree, void *data );\r
+int jsw_ainsert ( jsw_atree_t *tree, void *data );\r
+int jsw_aerase ( jsw_atree_t *tree, void *data );\r
+size_t jsw_asize ( jsw_atree_t *tree );\r
+\r
+/* Traversal functions */\r
+jsw_atrav_t *jsw_atnew ( void );\r
+void jsw_atdelete ( jsw_atrav_t *trav );\r
+void *jsw_atfirst ( jsw_atrav_t *trav, jsw_atree_t *tree );\r
+void *jsw_atlast ( jsw_atrav_t *trav, jsw_atree_t *tree );\r
+void *jsw_atnext ( jsw_atrav_t *trav );\r
+void *jsw_atprev ( jsw_atrav_t *trav );\r
+\r
+#ifdef __cplusplus\r
+}\r
+#endif\r
+\r
+#endif\r
--- /dev/null
+/*\r
+ AVL balanced tree library\r
+\r
+ > Created (Julienne Walker): June 17, 2003\r
+ > Modified (Julienne Walker): September 24, 2005\r
+*/\r
+#include "jsw_avltree.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_avlnode {\r
+ int balance; /* Balance factor */\r
+ void *data; /* User-defined content */\r
+ struct jsw_avlnode *link[2]; /* Left (0) and right (1) links */\r
+} jsw_avlnode_t;\r
+\r
+struct jsw_avltree {\r
+ jsw_avlnode_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_avltrav {\r
+ jsw_avltree_t *tree; /* Paired tree */\r
+ jsw_avlnode_t *it; /* Current node */\r
+ jsw_avlnode_t *path[HEIGHT_LIMIT]; /* Traversal path */\r
+ size_t top; /* Top of stack */\r
+};\r
+\r
+/* Two way single rotation */\r
+#define jsw_single(root,dir) do { \\r
+ jsw_avlnode_t *save = root->link[!dir]; \\r
+ root->link[!dir] = save->link[dir]; \\r
+ save->link[dir] = root; \\r
+ root = save; \\r
+} while (0)\r
+\r
+/* Two way double rotation */\r
+#define jsw_double(root,dir) do { \\r
+ jsw_avlnode_t *save = root->link[!dir]->link[dir]; \\r
+ root->link[!dir]->link[dir] = save->link[!dir]; \\r
+ save->link[!dir] = root->link[!dir]; \\r
+ root->link[!dir] = save; \\r
+ save = root->link[!dir]; \\r
+ root->link[!dir] = save->link[dir]; \\r
+ save->link[dir] = root; \\r
+ root = save; \\r
+} while (0)\r
+\r
+/* Adjust balance before double rotation */\r
+#define jsw_adjust_balance(root,dir,bal) do { \\r
+ jsw_avlnode_t *n = root->link[dir]; \\r
+ jsw_avlnode_t *nn = n->link[!dir]; \\r
+ if ( nn->balance == 0 ) \\r
+ root->balance = n->balance = 0; \\r
+ else if ( nn->balance == bal ) { \\r
+ root->balance = -bal; \\r
+ n->balance = 0; \\r
+ } \\r
+ else { /* nn->balance == -bal */ \\r
+ root->balance = 0; \\r
+ n->balance = bal; \\r
+ } \\r
+ nn->balance = 0; \\r
+} while (0)\r
+\r
+/* Rebalance after insertion */\r
+#define jsw_insert_balance(root,dir) do { \\r
+ jsw_avlnode_t *n = root->link[dir]; \\r
+ int bal = dir == 0 ? -1 : +1; \\r
+ if ( n->balance == bal ) { \\r
+ root->balance = n->balance = 0; \\r
+ jsw_single ( root, !dir ); \\r
+ } \\r
+ else { /* n->balance == -bal */ \\r
+ jsw_adjust_balance ( root, dir, bal ); \\r
+ jsw_double ( root, !dir ); \\r
+ } \\r
+} while (0)\r
+\r
+/* Rebalance after deletion */\r
+#define jsw_remove_balance(root,dir,done) do { \\r
+ jsw_avlnode_t *n = root->link[!dir]; \\r
+ int bal = dir == 0 ? -1 : +1; \\r
+ if ( n->balance == -bal ) { \\r
+ root->balance = n->balance = 0; \\r
+ jsw_single ( root, dir ); \\r
+ } \\r
+ else if ( n->balance == bal ) { \\r
+ jsw_adjust_balance ( root, !dir, -bal ); \\r
+ jsw_double ( root, dir ); \\r
+ } \\r
+ else { /* n->balance == 0 */ \\r
+ root->balance = -bal; \\r
+ n->balance = bal; \\r
+ jsw_single ( root, dir ); \\r
+ done = 1; \\r
+ } \\r
+} while (0)\r
+\r
+static jsw_avlnode_t *new_node ( jsw_avltree_t *tree, void *data )\r
+{\r
+ jsw_avlnode_t *rn = (jsw_avlnode_t *)malloc ( sizeof *rn );\r
+\r
+ if ( rn == NULL )\r
+ return NULL;\r
+\r
+ rn->balance = 0;\r
+ rn->data = tree->dup ( data );\r
+ rn->link[0] = rn->link[1] = NULL;\r
+\r
+ return rn;\r
+}\r
+\r
+jsw_avltree_t *jsw_avlnew ( cmp_f cmp, dup_f dup, rel_f rel )\r
+{\r
+ jsw_avltree_t *rt = (jsw_avltree_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
+void jsw_avldelete ( jsw_avltree_t *tree )\r
+{\r
+ jsw_avlnode_t *it = tree->root;\r
+ jsw_avlnode_t *save;\r
+\r
+ /* Destruction by rotation */\r
+ while ( it != NULL ) {\r
+ if ( it->link[0] == NULL ) {\r
+ /* Remove node */\r
+ save = it->link[1];\r
+ tree->rel ( it->data );\r
+ free ( it );\r
+ }\r
+ else {\r
+ /* Rotate right */\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
+void *jsw_avlfind ( jsw_avltree_t *tree, void *data )\r
+{\r
+ jsw_avlnode_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
+ it = it->link[cmp < 0];\r
+ }\r
+\r
+ return it == NULL ? NULL : it->data;\r
+}\r
+\r
+int jsw_avlinsert ( jsw_avltree_t *tree, void *data )\r
+{\r
+ /* Empty tree case */\r
+ if ( tree->root == NULL ) {\r
+ tree->root = new_node ( tree, data );\r
+ if ( tree->root == NULL )\r
+ return 0;\r
+ }\r
+ else {\r
+ jsw_avlnode_t head = {0}; /* Temporary tree root */\r
+ jsw_avlnode_t *s, *t; /* Place to rebalance and parent */\r
+ jsw_avlnode_t *p, *q; /* Iterator and save pointer */\r
+ int dir;\r
+\r
+ /* Set up false root to ease maintenance */\r
+ t = &head;\r
+ t->link[1] = tree->root;\r
+\r
+ /* Search down the tree, saving rebalance points */\r
+ for ( s = p = t->link[1]; ; p = q ) {\r
+ dir = tree->cmp ( p->data, data ) < 0;\r
+ q = p->link[dir];\r
+\r
+ if ( q == NULL )\r
+ break;\r
+ \r
+ if ( q->balance != 0 ) {\r
+ t = p;\r
+ s = q;\r
+ }\r
+ }\r
+\r
+ p->link[dir] = q = new_node ( tree, data );\r
+ if ( q == NULL )\r
+ return 0;\r
+\r
+ /* Update balance factors */\r
+ for ( p = s; p != q; p = p->link[dir] ) {\r
+ dir = tree->cmp ( p->data, data ) < 0;\r
+ p->balance += dir == 0 ? -1 : +1;\r
+ }\r
+\r
+ q = s; /* Save rebalance point for parent fix */\r
+\r
+ /* Rebalance if necessary */\r
+ if ( abs ( s->balance ) > 1 ) {\r
+ dir = tree->cmp ( s->data, data ) < 0;\r
+ jsw_insert_balance ( s, dir );\r
+ }\r
+\r
+ /* Fix parent */\r
+ if ( q == head.link[1] )\r
+ tree->root = s;\r
+ else\r
+ t->link[q == t->link[1]] = s;\r
+ }\r
+\r
+ ++tree->size;\r
+\r
+ return 1;\r
+}\r
+\r
+int jsw_avlerase ( jsw_avltree_t *tree, void *data )\r
+{\r
+ if ( tree->root != NULL ) {\r
+ jsw_avlnode_t *it, *up[HEIGHT_LIMIT];\r
+ int upd[HEIGHT_LIMIT], top = 0;\r
+ int done = 0;\r
+\r
+ it = tree->root;\r
+\r
+ /* Search down tree and save path */\r
+ for ( ; ; ) {\r
+ if ( it == NULL )\r
+ return 0;\r
+ else if ( tree->cmp ( it->data, data ) == 0 )\r
+ break;\r
+\r
+ /* Push direction and node onto stack */\r
+ upd[top] = tree->cmp ( it->data, data ) < 0;\r
+ up[top++] = it;\r
+\r
+ it = it->link[upd[top - 1]];\r
+ }\r
+\r
+ /* Remove the node */\r
+ if ( it->link[0] == NULL || it->link[1] == NULL ) {\r
+ /* Which child is not null? */\r
+ int dir = it->link[0] == NULL;\r
+\r
+ /* Fix parent */\r
+ if ( top != 0 )\r
+ up[top - 1]->link[upd[top - 1]] = it->link[dir];\r
+ else\r
+ tree->root = it->link[dir];\r
+\r
+ tree->rel ( it->data );\r
+ free ( it );\r
+ }\r
+ else {\r
+ /* Find the inorder successor */\r
+ jsw_avlnode_t *heir = it->link[1];\r
+ void *save;\r
+ \r
+ /* Save this path too */\r
+ upd[top] = 1;\r
+ up[top++] = it;\r
+\r
+ while ( heir->link[0] != NULL ) {\r
+ upd[top] = 0;\r
+ up[top++] = heir;\r
+ heir = heir->link[0];\r
+ }\r
+\r
+ /* Swap data */\r
+ save = it->data;\r
+ it->data = heir->data;\r
+ heir->data = save;\r
+\r
+ /* Unlink successor and fix parent */\r
+ up[top - 1]->link[up[top - 1] == it] = heir->link[1];\r
+\r
+ tree->rel ( heir->data );\r
+ free ( heir );\r
+ }\r
+\r
+ /* Walk back up the search path */\r
+ while ( --top >= 0 && !done ) {\r
+ /* Update balance factors */\r
+ up[top]->balance += upd[top] != 0 ? -1 : +1;\r
+\r
+ /* Terminate or rebalance as necessary */\r
+ if ( abs ( up[top]->balance ) == 1 )\r
+ break;\r
+ else if ( abs ( up[top]->balance ) > 1 ) {\r
+ jsw_remove_balance ( up[top], upd[top], done );\r
+\r
+ /* Fix parent */\r
+ if ( top != 0 )\r
+ up[top - 1]->link[upd[top - 1]] = up[top];\r
+ else\r
+ tree->root = up[0];\r
+ }\r
+ }\r
+\r
+ --tree->size;\r
+ }\r
+\r
+ return 1;\r
+}\r
+\r
+size_t jsw_avlsize ( jsw_avltree_t *tree )\r
+{\r
+ return tree->size;\r
+}\r
+\r
+jsw_avltrav_t *jsw_avltnew ( void )\r
+{\r
+ return malloc ( sizeof ( jsw_avltrav_t ) );\r
+}\r
+\r
+void jsw_avltdelete ( jsw_avltrav_t *trav )\r
+{\r
+ free ( trav );\r
+}\r
+\r
+/*\r
+ First step in traversal,\r
+ handles min and max\r
+*/\r
+static void *start ( jsw_avltrav_t *trav, jsw_avltree_t *tree, int dir )\r
+{\r
+ trav->tree = tree;\r
+ trav->it = tree->root;\r
+ trav->top = 0;\r
+\r
+ /* Build a path to work with */\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
+ Subsequent traversal steps,\r
+ handles ascending and descending\r
+*/\r
+static void *move ( jsw_avltrav_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_avlnode_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
+void *jsw_avltfirst ( jsw_avltrav_t *trav, jsw_avltree_t *tree )\r
+{\r
+ return start ( trav, tree, 0 ); /* Min value */\r
+}\r
+\r
+void *jsw_avltlast ( jsw_avltrav_t *trav, jsw_avltree_t *tree )\r
+{\r
+ return start ( trav, tree, 1 ); /* Max value */\r
+}\r
+\r
+void *jsw_avltnext ( jsw_avltrav_t *trav )\r
+{\r
+ return move ( trav, 1 ); /* Toward larger items */\r
+}\r
+\r
+void *jsw_avltprev ( jsw_avltrav_t *trav )\r
+{\r
+ return move ( trav, 0 ); /* Toward smaller items */\r
+}\r
--- /dev/null
+#ifndef JSW_AVLTREE_H\r
+#define JSW_AVLTREE_H\r
+\r
+/*\r
+ AVL balanced tree library\r
+\r
+ > Created (Julienne Walker): June 17, 2003\r
+ > Modified (Julienne Walker): September 24, 2005\r
+\r
+ This code is in the public domain. Anyone may\r
+ use it or change it in any way that they see\r
+ fit. The author assumes no responsibility for \r
+ damages incurred through use of the original\r
+ code or any variations thereof.\r
+\r
+ It is requested, but not required, that due\r
+ credit is given to the original author and\r
+ anyone who has modified the code through\r
+ a header comment, such as this one.\r
+*/\r
+#ifdef __cplusplus\r
+#include <cstddef>\r
+\r
+using std::size_t;\r
+\r
+extern "C" {\r
+#else\r
+#include <stddef.h>\r
+#endif\r
+\r
+/* Opaque types */\r
+typedef struct jsw_avltree jsw_avltree_t;\r
+typedef struct jsw_avltrav jsw_avltrav_t;\r
+\r
+/* User-defined item handling */\r
+typedef int (*cmp_f) ( const void *p1, const void *p2 );\r
+typedef void *(*dup_f) ( void *p );\r
+typedef void (*rel_f) ( void *p );\r
+\r
+/* AVL tree functions */\r
+jsw_avltree_t *jsw_avlnew ( cmp_f cmp, dup_f dup, rel_f rel );\r
+void jsw_avldelete ( jsw_avltree_t *tree );\r
+void *jsw_avlfind ( jsw_avltree_t *tree, void *data );\r
+int jsw_avlinsert ( jsw_avltree_t *tree, void *data );\r
+int jsw_avlerase ( jsw_avltree_t *tree, void *data );\r
+size_t jsw_avlsize ( jsw_avltree_t *tree );\r
+\r
+/* Traversal functions */\r
+jsw_avltrav_t *jsw_avltnew ( void );\r
+void jsw_avltdelete ( jsw_avltrav_t *trav );\r
+void *jsw_avltfirst ( jsw_avltrav_t *trav, jsw_avltree_t *tree );\r
+void *jsw_avltlast ( jsw_avltrav_t *trav, jsw_avltree_t *tree );\r
+void *jsw_avltnext ( jsw_avltrav_t *trav );\r
+void *jsw_avltprev ( jsw_avltrav_t *trav );\r
+\r
+#ifdef __cplusplus\r
+}\r
+#endif\r
+\r
+#endif\r
--- /dev/null
+/*\r
+ Hash table library using separate chaining\r
+\r
+ > Created (Julienne Walker): August 7, 2005\r
+ > Modified (Julienne Walker): August 11, 2005\r
+ Added a cast for malloc to enable clean\r
+ compilation as C++\r
+*/\r
+#include "jsw_hlib.h"\r
+\r
+#ifdef __cplusplus\r
+#include <cstdlib>\r
+\r
+using std::malloc;\r
+using std::free;\r
+#else\r
+#include <stdlib.h>\r
+#endif\r
+\r
+typedef struct jsw_node {\r
+ void *key; /* Key used for searching */\r
+ void *item; /* Actual content of a node */\r
+ struct jsw_node *next; /* Next link in the chain */\r
+} jsw_node_t;\r
+\r
+typedef struct jsw_head {\r
+ jsw_node_t *first; /* First link in the chain */\r
+ size_t size; /* Length of the chain */\r
+} jsw_head_t;\r
+\r
+struct jsw_hash {\r
+ jsw_head_t **table; /* Dynamic chained hash table */\r
+ size_t size; /* Current item count */\r
+ size_t capacity; /* Current table size */\r
+ size_t curri; /* Current index for traversal */\r
+ jsw_node_t *currl; /* Current link for traversal */\r
+ hash_f hash; /* User defined key hash function */\r
+ cmp_f cmp; /* User defined key comparison function */\r
+ keydup_f keydup; /* User defined key copy function */\r
+ itemdup_f itemdup; /* User defined item copy function */\r
+ keyrel_f keyrel; /* User defined key delete function */\r
+ itemrel_f itemrel; /* User defined item delete function */\r
+};\r
+\r
+static jsw_node_t *new_node ( void *key, void *item, jsw_node_t *next )\r
+{\r
+ jsw_node_t *node = (jsw_node_t *)malloc ( sizeof *node );\r
+\r
+ if ( node == NULL )\r
+ return NULL;\r
+\r
+ node->key = key;\r
+ node->item = item;\r
+ node->next = next;\r
+\r
+ return node;\r
+}\r
+\r
+static jsw_head_t *new_chain ( void )\r
+{\r
+ jsw_head_t *chain = (jsw_head_t *)malloc ( sizeof *chain );\r
+\r
+ if ( chain == NULL )\r
+ return NULL;\r
+\r
+ chain->first = NULL;\r
+ chain->size = 0;\r
+\r
+ return chain;\r
+}\r
+\r
+/*\r
+ Create a new hash table with a capacity of size, and\r
+ user defined functions for handling keys and items.\r
+\r
+ Returns: An empty hash table, or NULL on failure.\r
+*/\r
+jsw_hash_t *jsw_hnew ( size_t size, hash_f hash, cmp_f cmp,\r
+ keydup_f keydup, itemdup_f itemdup,\r
+ keyrel_f keyrel, itemrel_f itemrel )\r
+{\r
+ jsw_hash_t *htab = (jsw_hash_t *)malloc ( sizeof *htab );\r
+ size_t i;\r
+\r
+ if ( htab == NULL )\r
+ return NULL;\r
+\r
+ htab->table = (jsw_head_t **)malloc ( size * sizeof *htab->table );\r
+\r
+ if ( htab->table == NULL ) {\r
+ free ( htab );\r
+ return NULL;\r
+ }\r
+\r
+ /* Empty chains have no head */\r
+ for ( i = 0; i < size; i++ )\r
+ htab->table[i] = NULL;\r
+\r
+ htab->size = 0;\r
+ htab->capacity = size;\r
+ htab->curri = 0;\r
+ htab->currl = NULL;\r
+ htab->hash = hash;\r
+ htab->cmp = cmp;\r
+ htab->keydup = keydup;\r
+ htab->itemdup = itemdup;\r
+ htab->keyrel = keyrel;\r
+ htab->itemrel = itemrel;\r
+\r
+ return htab;\r
+}\r
+\r
+/* Release all memory used by the hash table */\r
+void jsw_hdelete ( jsw_hash_t *htab )\r
+{\r
+ size_t i;\r
+\r
+ /* Release each chain individually */\r
+ for ( i = 0; i < htab->capacity; i++ ) {\r
+ jsw_node_t *save, *it;\r
+\r
+ if ( htab->table[i] == NULL )\r
+ continue;\r
+\r
+ it = htab->table[i]->first;\r
+\r
+ for ( ; it != NULL; it = save ) {\r
+ save = it->next;\r
+ htab->keyrel ( it->key );\r
+ htab->itemrel ( it->item );\r
+ free ( it );\r
+ }\r
+\r
+ free ( htab->table[i] );\r
+ }\r
+\r
+ /* Release the hash table */\r
+ free ( htab->table );\r
+ free ( htab );\r
+}\r
+\r
+/*\r
+ Find an item with the selected key\r
+\r
+ Returns: The item, or NULL if not found\r
+*/\r
+void *jsw_hfind ( jsw_hash_t *htab, void *key )\r
+{\r
+ unsigned h = htab->hash ( key ) % htab->capacity;\r
+\r
+ /* Search the chain only if it exists */\r
+ if ( htab->table[h] != NULL ) {\r
+ jsw_node_t *it = htab->table[h]->first;\r
+\r
+ for ( ; it != NULL; it = it->next ) {\r
+ if ( htab->cmp ( key, it->key ) == 0 )\r
+ return it->item;\r
+ }\r
+ }\r
+\r
+ return NULL;\r
+}\r
+\r
+/*\r
+ Insert an item with the selected key\r
+\r
+ Returns: non-zero for success, zero for failure\r
+*/\r
+int jsw_hinsert ( jsw_hash_t *htab, void *key, void *item )\r
+{\r
+ unsigned h = htab->hash ( key ) % htab->capacity;\r
+ void *dupkey, *dupitem;\r
+ jsw_node_t *new_item;\r
+\r
+ /* Disallow duplicate keys */\r
+ if ( jsw_hfind ( htab, key ) != NULL )\r
+ return 0;\r
+\r
+ /* Attempt to create a new item */\r
+ dupkey = htab->keydup ( key );\r
+ dupitem = htab->itemdup ( item );\r
+\r
+ new_item = new_node ( dupkey, dupitem, NULL );\r
+\r
+ if ( new_item == NULL )\r
+ return 0;\r
+\r
+ /* Create a chain if the bucket is empty */\r
+ if ( htab->table[h] == NULL ) {\r
+ htab->table[h] = new_chain();\r
+\r
+ if ( htab->table[h] == NULL ) {\r
+ htab->keyrel ( new_item->key );\r
+ htab->itemrel ( new_item->item );\r
+ free ( new_item );\r
+ return 0;\r
+ }\r
+ }\r
+\r
+ /* Insert at the front of the chain */\r
+ new_item->next = htab->table[h]->first;\r
+ htab->table[h]->first = new_item;\r
+\r
+ ++htab->table[h]->size;\r
+ ++htab->size;\r
+\r
+ return 1;\r
+}\r
+\r
+/*\r
+ Remove an item with the selected key\r
+\r
+ Returns: non-zero for success, zero for failure\r
+*/\r
+int jsw_herase ( jsw_hash_t *htab, void *key )\r
+{\r
+ unsigned h = htab->hash ( key ) % htab->capacity;\r
+ jsw_node_t *save, *it;\r
+\r
+ if ( htab->table[h] == NULL )\r
+ return 0;\r
+\r
+ it = htab->table[h]->first;\r
+\r
+ /* Remove the first node in the chain? */\r
+ if ( htab->cmp ( key, it->key ) == 0 ) {\r
+ htab->table[h]->first = it->next;\r
+\r
+ /* Release the node's memory */\r
+ htab->keyrel ( it->key );\r
+ htab->itemrel ( it->item );\r
+ free ( it );\r
+\r
+ /* Remove the chain if it's empty */\r
+ if ( htab->table[h]->first == NULL ) {\r
+ free ( htab->table[h] );\r
+ htab->table[h] = NULL;\r
+ }\r
+ else\r
+ --htab->table[h]->size;\r
+ }\r
+ else {\r
+ /* Search for the node */\r
+ while ( it->next != NULL ) {\r
+ if ( htab->cmp ( key, it->next->key ) == 0 )\r
+ break;\r
+\r
+ it = it->next;\r
+ }\r
+\r
+ /* Not found? */\r
+ if ( it->next == NULL )\r
+ return 0;\r
+\r
+ save = it->next;\r
+ it->next = it->next->next;\r
+\r
+ /* Release the node's memory */\r
+ htab->keyrel ( save->key );\r
+ htab->itemrel ( save->item );\r
+ free ( save );\r
+\r
+ --htab->table[h]->size;\r
+ }\r
+\r
+ /* Erasure invalidates traversal markers */\r
+ jsw_hreset ( htab );\r
+\r
+ --htab->size;\r
+\r
+ return 1;\r
+}\r
+\r
+/*\r
+ Grow or shrink the table, this is a slow operation\r
+ \r
+ Returns: non-zero for success, zero for failure\r
+*/\r
+int jsw_hresize ( jsw_hash_t *htab, size_t new_size )\r
+{\r
+ jsw_hash_t *new_htab;\r
+ jsw_node_t *it;\r
+ size_t i;\r
+\r
+ /* Build a new hash table, then assign it to the old one */\r
+ new_htab = jsw_hnew ( new_size, htab->hash, htab->cmp,\r
+ htab->keydup, htab->itemdup, htab->keyrel, htab->itemrel );\r
+\r
+ if ( new_htab == NULL )\r
+ return 0;\r
+\r
+ for ( i = 0; i < htab->capacity; i++ ) {\r
+ if ( htab->table[i] == NULL )\r
+ continue;\r
+\r
+ for ( it = htab->table[i]->first; it != NULL; it = it->next )\r
+ jsw_hinsert ( new_htab, it->key, it->item );\r
+ }\r
+\r
+ /* A hash table holds copies, so release the old table */\r
+ jsw_hdelete ( htab );\r
+ htab = new_htab;\r
+\r
+ return 1;\r
+}\r
+\r
+/* Reset the traversal markers to the beginning */\r
+void jsw_hreset ( jsw_hash_t *htab )\r
+{\r
+ size_t i;\r
+\r
+ htab->curri = 0;\r
+ htab->currl = NULL;\r
+\r
+ /* Find the first non-empty bucket */\r
+ for ( i = 0; i < htab->capacity; i++ ) {\r
+ if ( htab->table[i] != NULL )\r
+ break;\r
+ }\r
+\r
+ htab->curri = i;\r
+\r
+ /* Set the link marker if the table was not empty */\r
+ if ( i != htab->capacity )\r
+ htab->currl = htab->table[i]->first;\r
+}\r
+\r
+/* Traverse forward by one key */\r
+int jsw_hnext ( jsw_hash_t *htab )\r
+{\r
+ if ( htab->currl != NULL ) {\r
+ htab->currl = htab->currl->next;\r
+\r
+ /* At the end of the chain? */\r
+ if ( htab->currl == NULL ) {\r
+ /* Find the next chain */\r
+ while ( ++htab->curri < htab->capacity ) {\r
+ if ( htab->table[htab->curri] != NULL )\r
+ break;\r
+ }\r
+\r
+ /* No more chains? */\r
+ if ( htab->curri == htab->capacity )\r
+ return 0;\r
+\r
+ htab->currl = htab->table[htab->curri]->first;\r
+ }\r
+ }\r
+\r
+ return 1;\r
+}\r
+\r
+/* Get the current key */\r
+const void *jsw_hkey ( jsw_hash_t *htab )\r
+{\r
+ return htab->currl != NULL ? htab->currl->key : NULL;\r
+}\r
+\r
+/* Get the current item */\r
+void *jsw_hitem ( jsw_hash_t *htab )\r
+{\r
+ return htab->currl != NULL ? htab->currl->item : NULL;\r
+}\r
+\r
+/* Current number of items in the table */\r
+size_t jsw_hsize ( jsw_hash_t *htab )\r
+{\r
+ return htab->size;\r
+}\r
+\r
+/* Total allowable number of items without resizing */\r
+size_t jsw_hcapacity ( jsw_hash_t *htab )\r
+{\r
+ return htab->capacity;\r
+}\r
+\r
+/* Get statistics for the hash table */\r
+jsw_hstat_t *jsw_hstat ( jsw_hash_t *htab )\r
+{\r
+ jsw_hstat_t *stat;\r
+ double sum = 0, used = 0;\r
+ size_t i;\r
+\r
+ /* No stats for an empty table */\r
+ if ( htab->size == 0 )\r
+ return NULL;\r
+\r
+ stat = (jsw_hstat_t *)malloc ( sizeof *stat );\r
+\r
+ if ( stat == NULL )\r
+ return NULL;\r
+\r
+ stat->lchain = 0;\r
+ stat->schain = (size_t)-1;\r
+\r
+ for ( i = 0; i < htab->capacity; i++ ) {\r
+ if ( htab->table[i] != NULL ) {\r
+ sum += htab->table[i]->size;\r
+\r
+ ++used; /* Non-empty buckets */\r
+\r
+ if ( htab->table[i]->size > stat->lchain )\r
+ stat->lchain = htab->table[i]->size;\r
+\r
+ if ( htab->table[i]->size < stat->schain )\r
+ stat->schain = htab->table[i]->size;\r
+ }\r
+ }\r
+\r
+ stat->load = used / htab->capacity;\r
+ stat->achain = sum / used;\r
+\r
+ return stat;\r
+}\r
--- /dev/null
+#ifndef JSW_HLIB\r
+#define JSW_HLIB\r
+\r
+/*\r
+ Hash table library using separate chaining\r
+\r
+ > Created (Julienne Walker): August 7, 2005\r
+ > Modified (Julienne Walker): August 11, 2005\r
+\r
+ This code is in the public domain. Anyone may\r
+ use it or change it in any way that they see\r
+ fit. The author assumes no responsibility for \r
+ damages incurred through use of the original\r
+ code or any variations thereof.\r
+\r
+ It is requested, but not required, that due\r
+ credit is given to the original author and\r
+ anyone who has modified the code through\r
+ a header comment, such as this one.\r
+*/\r
+#ifdef __cplusplus\r
+#include <cstddef>\r
+\r
+using std::size_t;\r
+\r
+extern "C" {\r
+#else\r
+#include <stddef.h>\r
+#endif\r
+\r
+typedef struct jsw_hash jsw_hash_t;\r
+\r
+/* Application specific hash function */\r
+typedef unsigned (*hash_f) ( const void *key );\r
+\r
+/* Application specific key comparison function */\r
+typedef int (*cmp_f) ( const void *a, const void *b );\r
+\r
+/* Application specific key copying function */\r
+typedef void *(*keydup_f) ( const void *key );\r
+\r
+/* Application specific data copying function */\r
+typedef void *(*itemdup_f) ( const void *item );\r
+\r
+/* Application specific key deletion function */\r
+typedef void (*keyrel_f) ( void *key );\r
+\r
+/* Application specific data deletion function */\r
+typedef void (*itemrel_f) ( void *item );\r
+\r
+typedef struct jsw_hstat {\r
+ double load; /* Table load factor: (M chains)/(table size) */\r
+ double achain; /* Average chain length */\r
+ size_t lchain; /* Longest chain */\r
+ size_t schain; /* Shortest non-empty chain */\r
+} jsw_hstat_t;\r
+\r
+/*\r
+ Create a new hash table with a capacity of size, and\r
+ user defined functions for handling keys and items.\r
+\r
+ Returns: An empty hash table, or NULL on failure.\r
+*/\r
+jsw_hash_t *jsw_hnew ( size_t size, hash_f hash, cmp_f cmp,\r
+ keydup_f keydup, itemdup_f itemdup,\r
+ keyrel_f keyrel, itemrel_f itemrel );\r
+\r
+/* Release all memory used by the hash table */\r
+void jsw_hdelete ( jsw_hash_t *htab );\r
+\r
+/*\r
+ Find an item with the selected key\r
+\r
+ Returns: The item, or NULL if not found\r
+*/\r
+void *jsw_hfind ( jsw_hash_t *htab, void *key );\r
+\r
+/*\r
+ Insert an item with the selected key\r
+\r
+ Returns: non-zero for success, zero for failure\r
+*/\r
+int jsw_hinsert ( jsw_hash_t *htab, void *key, void *item );\r
+\r
+/*\r
+ Remove an item with the selected key\r
+\r
+ Returns: non-zero for success, zero for failure\r
+*/\r
+int jsw_herase ( jsw_hash_t *htab, void *key );\r
+\r
+/*\r
+ Grow or shrink the table, this is a slow operation\r
+ \r
+ Returns: non-zero for success, zero for failure\r
+*/\r
+int jsw_hresize ( jsw_hash_t *htab, size_t new_size );\r
+\r
+/* Reset the traversal markers to the beginning */\r
+void jsw_hreset ( jsw_hash_t *htab );\r
+\r
+/* Traverse forward by one key */\r
+int jsw_hnext ( jsw_hash_t *htab );\r
+\r
+/* Get the current key */\r
+const void *jsw_hkey ( jsw_hash_t *htab );\r
+\r
+/* Get the current item */\r
+void *jsw_hitem ( jsw_hash_t *htab );\r
+\r
+/* Current number of items in the table */\r
+size_t jsw_hsize ( jsw_hash_t *htab );\r
+\r
+/* Total allowable number of items without resizing */\r
+size_t jsw_hcapacity ( jsw_hash_t *htab );\r
+\r
+/* Get statistics for the hash table */\r
+jsw_hstat_t *jsw_hstat ( jsw_hash_t *htab );\r
+\r
+#ifdef __cplusplus\r
+}\r
+#endif\r
+\r
+#endif\r
--- /dev/null
+#include <limits.h>\r
+#include <time.h>\r
+#include "jsw_rand.h"\r
+\r
+#define N 624\r
+#define M 397\r
+#define A 0x9908b0dfUL\r
+#define U 0x80000000UL\r
+#define L 0x7fffffffUL\r
+\r
+/* Internal state */\r
+static unsigned long x[N];\r
+static int next;\r
+\r
+/* Initialize internal state */\r
+void jsw_seed ( unsigned long s )\r
+{\r
+ int i;\r
+\r
+ x[0] = s & 0xffffffffUL;\r
+\r
+ for ( i = 1; i < N; i++ ) {\r
+ x[i] = ( 1812433253UL \r
+ * ( x[i - 1] ^ ( x[i - 1] >> 30 ) ) + i );\r
+ x[i] &= 0xffffffffUL;\r
+ }\r
+}\r
+\r
+/* Mersenne Twister */\r
+unsigned long jsw_rand ( void )\r
+{\r
+ unsigned long y, a;\r
+ int i;\r
+\r
+ /* Refill x if exhausted */\r
+ if ( next == N ) {\r
+ next = 0;\r
+\r
+ for ( i = 0; i < N - 1; i++ ) {\r
+ y = ( x[i] & U ) | x[i + 1] & L;\r
+ a = ( y & 0x1UL ) ? A : 0x0UL;\r
+ x[i] = x[( i + M ) % N] ^ ( y >> 1 ) ^ a;\r
+ }\r
+\r
+ y = ( x[N - 1] & U ) | x[0] & L;\r
+ a = ( y & 0x1UL ) ? A : 0x0UL;\r
+ x[N - 1] = x[M - 1] ^ ( y >> 1 ) ^ a;\r
+ }\r
+\r
+ y = x[next++];\r
+\r
+ /* Improve distribution */\r
+ y ^= (y >> 11);\r
+ y ^= (y << 7) & 0x9d2c5680UL;\r
+ y ^= (y << 15) & 0xefc60000UL;\r
+ y ^= (y >> 18);\r
+\r
+ return y;\r
+}\r
+\r
+/* Portable time seed */\r
+unsigned jsw_time_seed()\r
+{\r
+ time_t now = time ( 0 );\r
+ unsigned char *p = (unsigned char *)&now;\r
+ unsigned seed = 0;\r
+ size_t i;\r
+\r
+ for ( i = 0; i < sizeof now; i++ )\r
+ seed = seed * ( UCHAR_MAX + 2U ) + p[i];\r
+\r
+ return seed;\r
+}
\ No newline at end of file
--- /dev/null
+#ifndef JSW_RAND_H\r
+#define JSW_RAND_H\r
+\r
+/* Seed the RNG. Must be called first */\r
+void jsw_seed ( unsigned long s );\r
+\r
+/* Return a 32-bit random number */\r
+unsigned long jsw_rand ( void );\r
+\r
+/* Seed with current system time */\r
+unsigned jsw_time_seed();\r
+\r
+#endif\r
--- /dev/null
+/*\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
+}
\ No newline at end of file
--- /dev/null
+#ifndef JSW_RBTREE_H\r
+#define JSW_RBTREE_H\r
+\r
+/*\r
+ Red Black balanced tree library\r
+\r
+ > Created (Julienne Walker): August 23, 2003\r
+ > Modified (Julienne Walker): March 14, 2008\r
+\r
+ This code is in the public domain. Anyone may\r
+ use it or change it in any way that they see\r
+ fit. The author assumes no responsibility for \r
+ damages incurred through use of the original\r
+ code or any variations thereof.\r
+\r
+ It is requested, but not required, that due\r
+ credit is given to the original author and\r
+ anyone who has modified the code through\r
+ a header comment, such as this one.\r
+*/\r
+#ifdef __cplusplus\r
+#include <cstddef>\r
+\r
+using std::size_t;\r
+\r
+extern "C" {\r
+#else\r
+#include <stddef.h>\r
+#endif\r
+\r
+/* Opaque types */\r
+typedef struct jsw_rbtree jsw_rbtree_t;\r
+typedef struct jsw_rbtrav jsw_rbtrav_t;\r
+\r
+/* User-defined item handling */\r
+typedef int (*cmp_f) ( const void *p1, const void *p2 );\r
+typedef void *(*dup_f) ( void *p );\r
+typedef void (*rel_f) ( void *p );\r
+\r
+/* Red Black tree functions */\r
+jsw_rbtree_t *jsw_rbnew ( cmp_f cmp, dup_f dup, rel_f rel );\r
+void jsw_rbdelete ( jsw_rbtree_t *tree );\r
+void *jsw_rbfind ( jsw_rbtree_t *tree, void *data );\r
+int jsw_rbinsert ( jsw_rbtree_t *tree, void *data );\r
+int jsw_rberase ( jsw_rbtree_t *tree, void *data );\r
+size_t jsw_rbsize ( jsw_rbtree_t *tree );\r
+\r
+/* Traversal functions */\r
+jsw_rbtrav_t *jsw_rbtnew ( void );\r
+void jsw_rbtdelete ( jsw_rbtrav_t *trav );\r
+void *jsw_rbtfirst ( jsw_rbtrav_t *trav, jsw_rbtree_t *tree );\r
+void *jsw_rbtlast ( jsw_rbtrav_t *trav, jsw_rbtree_t *tree );\r
+void *jsw_rbtnext ( jsw_rbtrav_t *trav );\r
+void *jsw_rbtprev ( jsw_rbtrav_t *trav );\r
+\r
+#ifdef __cplusplus\r
+}\r
+#endif\r
+\r
+#endif\r