From b8dc7e923f9cf71c3c722b872494fe639ba4621f Mon Sep 17 00:00:00 2001 From: Nathan Wagner Date: Thu, 30 Apr 2015 11:10:34 +0000 Subject: [PATCH] initial commit of data structure code from jsw Downloaded and unzipped from http://www.eternallyconfuzzled.com From that site: "All libraries are offered in the public domain" --- jsw_atree.c | 401 +++++++++++++++++++++++++++ jsw_atree.h | 59 ++++ jsw_avltree.c | 426 +++++++++++++++++++++++++++++ jsw_avltree.h | 60 +++++ jsw_hlib.c | 414 ++++++++++++++++++++++++++++ jsw_hlib.h | 124 +++++++++ jsw_rand.c | 73 +++++ jsw_rand.h | 13 + jsw_rbtree/jsw_rbtree.c | 581 ++++++++++++++++++++++++++++++++++++++++ jsw_rbtree/jsw_rbtree.h | 60 +++++ 10 files changed, 2211 insertions(+) create mode 100644 jsw_atree.c create mode 100644 jsw_atree.h create mode 100644 jsw_avltree.c create mode 100644 jsw_avltree.h create mode 100644 jsw_hlib.c create mode 100644 jsw_hlib.h create mode 100644 jsw_rand.c create mode 100644 jsw_rand.h create mode 100644 jsw_rbtree/jsw_rbtree.c create mode 100644 jsw_rbtree/jsw_rbtree.h diff --git a/jsw_atree.c b/jsw_atree.c new file mode 100644 index 0000000..0029dde --- /dev/null +++ b/jsw_atree.c @@ -0,0 +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 */ +} diff --git a/jsw_atree.h b/jsw_atree.h new file mode 100644 index 0000000..c7d52ce --- /dev/null +++ b/jsw_atree.h @@ -0,0 +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 diff --git a/jsw_avltree.c b/jsw_avltree.c new file mode 100644 index 0000000..cc1f28c --- /dev/null +++ b/jsw_avltree.c @@ -0,0 +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 */ +} diff --git a/jsw_avltree.h b/jsw_avltree.h new file mode 100644 index 0000000..089f8ef --- /dev/null +++ b/jsw_avltree.h @@ -0,0 +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 diff --git a/jsw_hlib.c b/jsw_hlib.c new file mode 100644 index 0000000..e479272 --- /dev/null +++ b/jsw_hlib.c @@ -0,0 +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; +} diff --git a/jsw_hlib.h b/jsw_hlib.h new file mode 100644 index 0000000..7765cd8 --- /dev/null +++ b/jsw_hlib.h @@ -0,0 +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 diff --git a/jsw_rand.c b/jsw_rand.c new file mode 100644 index 0000000..a506441 --- /dev/null +++ b/jsw_rand.c @@ -0,0 +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; +} \ No newline at end of file diff --git a/jsw_rand.h b/jsw_rand.h new file mode 100644 index 0000000..54ca83b --- /dev/null +++ b/jsw_rand.h @@ -0,0 +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 diff --git a/jsw_rbtree/jsw_rbtree.c b/jsw_rbtree/jsw_rbtree.c new file mode 100644 index 0000000..ca1d8b2 --- /dev/null +++ b/jsw_rbtree/jsw_rbtree.c @@ -0,0 +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 */ +} \ No newline at end of file diff --git a/jsw_rbtree/jsw_rbtree.h b/jsw_rbtree/jsw_rbtree.h new file mode 100644 index 0000000..bd7ba77 --- /dev/null +++ b/jsw_rbtree/jsw_rbtree.h @@ -0,0 +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 -- 2.40.0