-/*\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 */
+}
projects / jsw / blobdiff