From 9fa959d28f32ae94111296c238b1e76caf152078 Mon Sep 17 00:00:00 2001 From: Nathan Wagner Date: Thu, 3 Dec 2015 13:47:59 +0000 Subject: [PATCH] removed dos line ending carriage return --- jsw_atree.c | 802 +++++++++++++-------------- jsw_atree.h | 118 ++-- jsw_avltree.c | 852 ++++++++++++++-------------- jsw_avltree.h | 120 ++-- jsw_hlib.c | 828 ++++++++++++++-------------- jsw_hlib.h | 248 ++++----- jsw_rand.c | 144 ++--- jsw_rand.h | 26 +- jsw_rbtree/jsw_rbtree.c | 1160 +++++++++++++++++++-------------------- jsw_rbtree/jsw_rbtree.h | 120 ++-- 10 files changed, 2209 insertions(+), 2209 deletions(-) diff --git a/jsw_atree.c b/jsw_atree.c index 0029dde..ba66bd0 100644 --- a/jsw_atree.c +++ b/jsw_atree.c @@ -1,401 +1,401 @@ -/* - 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 - -using std::malloc; -using std::free; -using std::size_t; -#else -#include -#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 */ -} +/* + 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 + +using std::malloc; +using std::free; +using std::size_t; +#else +#include +#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 */ +} diff --git a/jsw_atree.h b/jsw_atree.h index c7d52ce..0faf528 100644 --- a/jsw_atree.h +++ b/jsw_atree.h @@ -1,59 +1,59 @@ -#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 - -using std::size_t; - -extern "C" { -#else -#include -#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 +#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 + +using std::size_t; + +extern "C" { +#else +#include +#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 diff --git a/jsw_avltree.c b/jsw_avltree.c index cc1f28c..f8910fb 100644 --- a/jsw_avltree.c +++ b/jsw_avltree.c @@ -1,426 +1,426 @@ -/* - AVL balanced tree library - - > Created (Julienne Walker): June 17, 2003 - > Modified (Julienne Walker): September 24, 2005 -*/ -#include "jsw_avltree.h" - -#ifdef __cplusplus -#include - -using std::malloc; -using std::free; -using std::size_t; -#else -#include -#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 */ -} +/* + AVL balanced tree library + + > Created (Julienne Walker): June 17, 2003 + > Modified (Julienne Walker): September 24, 2005 +*/ +#include "jsw_avltree.h" + +#ifdef __cplusplus +#include + +using std::malloc; +using std::free; +using std::size_t; +#else +#include +#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 */ +} diff --git a/jsw_avltree.h b/jsw_avltree.h index 089f8ef..aaaf76e 100644 --- a/jsw_avltree.h +++ b/jsw_avltree.h @@ -1,60 +1,60 @@ -#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 - -using std::size_t; - -extern "C" { -#else -#include -#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 +#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 + +using std::size_t; + +extern "C" { +#else +#include +#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 diff --git a/jsw_hlib.c b/jsw_hlib.c index e479272..6cc961a 100644 --- a/jsw_hlib.c +++ b/jsw_hlib.c @@ -1,414 +1,414 @@ -/* - 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 - -using std::malloc; -using std::free; -#else -#include -#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; -} +/* + 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 + +using std::malloc; +using std::free; +#else +#include +#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; +} diff --git a/jsw_hlib.h b/jsw_hlib.h index 7765cd8..78cbdd7 100644 --- a/jsw_hlib.h +++ b/jsw_hlib.h @@ -1,124 +1,124 @@ -#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 - -using std::size_t; - -extern "C" { -#else -#include -#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 +#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 + +using std::size_t; + +extern "C" { +#else +#include +#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 diff --git a/jsw_rand.c b/jsw_rand.c index a506441..24f28e1 100644 --- a/jsw_rand.c +++ b/jsw_rand.c @@ -1,73 +1,73 @@ -#include -#include -#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; +#include +#include +#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 diff --git a/jsw_rand.h b/jsw_rand.h index 54ca83b..b3d6850 100644 --- a/jsw_rand.h +++ b/jsw_rand.h @@ -1,13 +1,13 @@ -#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 +#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 diff --git a/jsw_rbtree/jsw_rbtree.c b/jsw_rbtree/jsw_rbtree.c index ca1d8b2..c5ec17c 100644 --- a/jsw_rbtree/jsw_rbtree.c +++ b/jsw_rbtree/jsw_rbtree.c @@ -1,581 +1,581 @@ -/* - Red Black balanced tree library - - > Created (Julienne Walker): August 23, 2003 - > Modified (Julienne Walker): March 14, 2008 -*/ -#include "jsw_rbtree.h" - -#ifdef __cplusplus -#include - -using std::malloc; -using std::free; -using std::size_t; -#else -#include -#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 */ -}; - -/** - - Checks the color of a red black node - - The node to check - 1 for a red node, 0 for a black node - For jsw_rbtree.c internal use only -*/ -static int is_red ( jsw_rbnode_t *root ) -{ - return root != NULL && root->red == 1; -} - -/** - - Performs a single red black rotation in the specified direction - This function assumes that all nodes are valid for a rotation - - The original root to rotate around - The direction to rotate (0 = left, 1 = right) - The new root ater rotation - For jsw_rbtree.c internal use only -*/ -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; -} - -/** - - Performs a double red black rotation in the specified direction - This function assumes that all nodes are valid for a rotation - - The original root to rotate around - The direction to rotate (0 = left, 1 = right) - The new root after rotation - For jsw_rbtree.c internal use only -*/ -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 ); -} - -/** - - 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 - - The red black tree this node is being created for - The data value that will be stored in this node - A pointer to the new node - - 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 - -*/ -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; -} - -/** - - Creates and initializes an empty red black tree with - user-defined comparison, data copy, and data release operations - - User-defined data comparison function - User-defined data copy function - User-defined data release function - A pointer to the new tree - - The returned pointer must be released with jsw_rbdelete - -*/ -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; -} - -/** - - Releases a valid red black tree - - The tree to release - - The tree must have been created using jsw_rbnew - -*/ -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 ); -} - -/** - - Search for a copy of the specified - node data in a red black tree - - The tree to search - The data value to search for - - A pointer to the data value stored in the tree, - or a null pointer if no data could be found - -*/ -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; -} - -/** - - Insert a copy of the user-specified - data into a red black tree - - The tree to insert into - The data value to insert - - 1 if the value was inserted successfully, - 0 if the insertion failed for any reason - -*/ -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; -} - -/** - - Remove a node from a red black tree - that matches the user-specified data - - The tree to remove from - The data value to search for - - 1 if the value was removed successfully, - 0 if the removal failed for any reason - - - The most common failure reason should be - that the data was not found in the tree - -*/ -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; -} - -/** - - Gets the number of nodes in a red black tree - - The tree to calculate a size for - The number of nodes in the tree -*/ -size_t jsw_rbsize ( jsw_rbtree_t *tree ) -{ - return tree->size; -} - -/** - - Create a new traversal object - - A pointer to the new object - - The traversal object is not initialized until - jsw_rbtfirst or jsw_rbtlast are called. - The pointer must be released with jsw_rbtdelete - -*/ -jsw_rbtrav_t *jsw_rbtnew ( void ) -{ - return (jsw_rbtrav_t*)malloc ( sizeof ( jsw_rbtrav_t ) ); -} - -/** - - Release a traversal object - - The object to release - - The object must have been created with jsw_rbtnew - -*/ -void jsw_rbtdelete ( jsw_rbtrav_t *trav ) -{ - free ( trav ); -} - -/** - - Initialize a traversal object. The user-specified - direction determines whether to begin traversal at the - smallest or largest valued node - - The traversal object to initialize - The tree that the object will be attached to - - The direction to traverse (0 = ascending, 1 = descending) - - A pointer to the smallest or largest data value - For jsw_rbtree.c internal use only -*/ -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; -} - -/** - - Traverse a red black tree in the user-specified direction - - The initialized traversal object - - The direction to traverse (0 = ascending, 1 = descending) - - - A pointer to the next data value in the specified direction - - For jsw_rbtree.c internal use only -*/ -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; -} - -/** - - Initialize a traversal object to the smallest valued node - - The traversal object to initialize - The tree that the object will be attached to - A pointer to the smallest data value -*/ -void *jsw_rbtfirst ( jsw_rbtrav_t *trav, jsw_rbtree_t *tree ) -{ - return start ( trav, tree, 0 ); /* Min value */ -} - -/** - - Initialize a traversal object to the largest valued node - - The traversal object to initialize - The tree that the object will be attached to - A pointer to the largest data value -*/ -void *jsw_rbtlast ( jsw_rbtrav_t *trav, jsw_rbtree_t *tree ) -{ - return start ( trav, tree, 1 ); /* Max value */ -} - -/** - - Traverse to the next value in ascending order - - The initialized traversal object - A pointer to the next value in ascending order -*/ -void *jsw_rbtnext ( jsw_rbtrav_t *trav ) -{ - return move ( trav, 1 ); /* Toward larger items */ -} - -/** - - Traverse to the next value in descending order - - The initialized traversal object - A pointer to the next value in descending order -*/ -void *jsw_rbtprev ( jsw_rbtrav_t *trav ) -{ - return move ( trav, 0 ); /* Toward smaller items */ +/* + Red Black balanced tree library + + > Created (Julienne Walker): August 23, 2003 + > Modified (Julienne Walker): March 14, 2008 +*/ +#include "jsw_rbtree.h" + +#ifdef __cplusplus +#include + +using std::malloc; +using std::free; +using std::size_t; +#else +#include +#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 */ +}; + +/** + + Checks the color of a red black node + + The node to check + 1 for a red node, 0 for a black node + For jsw_rbtree.c internal use only +*/ +static int is_red ( jsw_rbnode_t *root ) +{ + return root != NULL && root->red == 1; +} + +/** + + Performs a single red black rotation in the specified direction + This function assumes that all nodes are valid for a rotation + + The original root to rotate around + The direction to rotate (0 = left, 1 = right) + The new root ater rotation + For jsw_rbtree.c internal use only +*/ +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; +} + +/** + + Performs a double red black rotation in the specified direction + This function assumes that all nodes are valid for a rotation + + The original root to rotate around + The direction to rotate (0 = left, 1 = right) + The new root after rotation + For jsw_rbtree.c internal use only +*/ +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 ); +} + +/** + + 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 + + The red black tree this node is being created for + The data value that will be stored in this node + A pointer to the new node + + 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 + +*/ +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; +} + +/** + + Creates and initializes an empty red black tree with + user-defined comparison, data copy, and data release operations + + User-defined data comparison function + User-defined data copy function + User-defined data release function + A pointer to the new tree + + The returned pointer must be released with jsw_rbdelete + +*/ +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; +} + +/** + + Releases a valid red black tree + + The tree to release + + The tree must have been created using jsw_rbnew + +*/ +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 ); +} + +/** + + Search for a copy of the specified + node data in a red black tree + + The tree to search + The data value to search for + + A pointer to the data value stored in the tree, + or a null pointer if no data could be found + +*/ +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; +} + +/** + + Insert a copy of the user-specified + data into a red black tree + + The tree to insert into + The data value to insert + + 1 if the value was inserted successfully, + 0 if the insertion failed for any reason + +*/ +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; +} + +/** + + Remove a node from a red black tree + that matches the user-specified data + + The tree to remove from + The data value to search for + + 1 if the value was removed successfully, + 0 if the removal failed for any reason + + + The most common failure reason should be + that the data was not found in the tree + +*/ +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; +} + +/** + + Gets the number of nodes in a red black tree + + The tree to calculate a size for + The number of nodes in the tree +*/ +size_t jsw_rbsize ( jsw_rbtree_t *tree ) +{ + return tree->size; +} + +/** + + Create a new traversal object + + A pointer to the new object + + The traversal object is not initialized until + jsw_rbtfirst or jsw_rbtlast are called. + The pointer must be released with jsw_rbtdelete + +*/ +jsw_rbtrav_t *jsw_rbtnew ( void ) +{ + return (jsw_rbtrav_t*)malloc ( sizeof ( jsw_rbtrav_t ) ); +} + +/** + + Release a traversal object + + The object to release + + The object must have been created with jsw_rbtnew + +*/ +void jsw_rbtdelete ( jsw_rbtrav_t *trav ) +{ + free ( trav ); +} + +/** + + Initialize a traversal object. The user-specified + direction determines whether to begin traversal at the + smallest or largest valued node + + The traversal object to initialize + The tree that the object will be attached to + + The direction to traverse (0 = ascending, 1 = descending) + + A pointer to the smallest or largest data value + For jsw_rbtree.c internal use only +*/ +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; +} + +/** + + Traverse a red black tree in the user-specified direction + + The initialized traversal object + + The direction to traverse (0 = ascending, 1 = descending) + + + A pointer to the next data value in the specified direction + + For jsw_rbtree.c internal use only +*/ +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; +} + +/** + + Initialize a traversal object to the smallest valued node + + The traversal object to initialize + The tree that the object will be attached to + A pointer to the smallest data value +*/ +void *jsw_rbtfirst ( jsw_rbtrav_t *trav, jsw_rbtree_t *tree ) +{ + return start ( trav, tree, 0 ); /* Min value */ +} + +/** + + Initialize a traversal object to the largest valued node + + The traversal object to initialize + The tree that the object will be attached to + A pointer to the largest data value +*/ +void *jsw_rbtlast ( jsw_rbtrav_t *trav, jsw_rbtree_t *tree ) +{ + return start ( trav, tree, 1 ); /* Max value */ +} + +/** + + Traverse to the next value in ascending order + + The initialized traversal object + A pointer to the next value in ascending order +*/ +void *jsw_rbtnext ( jsw_rbtrav_t *trav ) +{ + return move ( trav, 1 ); /* Toward larger items */ +} + +/** + + Traverse to the next value in descending order + + The initialized traversal object + A pointer to the next value in descending order +*/ +void *jsw_rbtprev ( jsw_rbtrav_t *trav ) +{ + return move ( trav, 0 ); /* Toward smaller items */ } \ No newline at end of file diff --git a/jsw_rbtree/jsw_rbtree.h b/jsw_rbtree/jsw_rbtree.h index bd7ba77..1933bae 100644 --- a/jsw_rbtree/jsw_rbtree.h +++ b/jsw_rbtree/jsw_rbtree.h @@ -1,60 +1,60 @@ -#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 - -using std::size_t; - -extern "C" { -#else -#include -#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 +#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 + +using std::size_t; + +extern "C" { +#else +#include +#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 -- 2.40.0