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