initial commit of data structure code from jsw

Downloaded and unzipped from
http://www.eternallyconfuzzled.com

From that site: "All libraries are offered in the public domain"

diff --git a/jsw_atree.c b/jsw_atree.c
new file mode 100644 (file)
index 0000000..0029dde
--- /dev/null
+++ b/jsw_atree.c
@@ -0,0 +1,401 @@
+/*\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

diff --git a/jsw_atree.h b/jsw_atree.h
new file mode 100644 (file)
index 0000000..c7d52ce
--- /dev/null
+++ b/jsw_atree.h
@@ -0,0 +1,59 @@
+#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

diff --git a/jsw_avltree.c b/jsw_avltree.c
new file mode 100644 (file)
index 0000000..cc1f28c
--- /dev/null
+++ b/jsw_avltree.c
@@ -0,0 +1,426 @@
+/*\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

diff --git a/jsw_avltree.h b/jsw_avltree.h
new file mode 100644 (file)
index 0000000..089f8ef
--- /dev/null
+++ b/jsw_avltree.h
@@ -0,0 +1,60 @@
+#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

diff --git a/jsw_hlib.c b/jsw_hlib.c
new file mode 100644 (file)
index 0000000..e479272
--- /dev/null
+++ b/jsw_hlib.c
@@ -0,0 +1,414 @@
+/*\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

diff --git a/jsw_hlib.h b/jsw_hlib.h
new file mode 100644 (file)
index 0000000..7765cd8
--- /dev/null
+++ b/jsw_hlib.h
@@ -0,0 +1,124 @@
+#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

diff --git a/jsw_rand.c b/jsw_rand.c
new file mode 100644 (file)
index 0000000..a506441
--- /dev/null
+++ b/jsw_rand.c
@@ -0,0 +1,73 @@
+#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

diff --git a/jsw_rand.h b/jsw_rand.h
new file mode 100644 (file)
index 0000000..54ca83b
--- /dev/null
+++ b/jsw_rand.h
@@ -0,0 +1,13 @@
+#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

diff --git a/jsw_rbtree/jsw_rbtree.c b/jsw_rbtree/jsw_rbtree.c
new file mode 100644 (file)
index 0000000..ca1d8b2
--- /dev/null
+++ b/jsw_rbtree/jsw_rbtree.c
@@ -0,0 +1,581 @@
+/*\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

diff --git a/jsw_rbtree/jsw_rbtree.h b/jsw_rbtree/jsw_rbtree.h
new file mode 100644 (file)
index 0000000..bd7ba77
--- /dev/null
+++ b/jsw_rbtree/jsw_rbtree.h
@@ -0,0 +1,60 @@
+#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