From 4aa68c18936fad4a98da66bb45dd1cae27229399 Mon Sep 17 00:00:00 2001 From: Nathan Wagner Date: Fri, 14 Sep 2018 08:19:31 +0000 Subject: [PATCH] create combined single header for jsw library --- lib/jsw/jsw.h | 207 ++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 207 insertions(+) create mode 100644 lib/jsw/jsw.h diff --git a/lib/jsw/jsw.h b/lib/jsw/jsw.h new file mode 100644 index 0000000..0dff7a7 --- /dev/null +++ b/lib/jsw/jsw.h @@ -0,0 +1,207 @@ +#ifndef JSW_H +#define JSW_H + +/* + Andersson tree library + + > Created (Julienne Walker): September 10, 2005 + + AVL balanced tree library + + > Created (Julienne Walker): June 17, 2003 + > Modified (Julienne Walker): September 24, 2005 + + Hash table library using separate chaining + + > Created (Julienne Walker): August 7, 2005 + > Modified (Julienne Walker): August 11, 2005 + + 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. +*/ + +/* code modified for inclusion in zpm */ + +#include + +/* 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 + */ + +/* Opaque types */ +typedef struct jsw_atree jsw_atree_t; +typedef struct jsw_atrav jsw_atrav_t; + +/* 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 ); + +/* + * AVL tree + */ + +/* Opaque types */ +typedef struct jsw_avltree jsw_avltree_t; +typedef struct jsw_avltrav jsw_avltrav_t; + +/* 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 ); + +/* + * hash table + */ + +typedef struct jsw_hash jsw_hash_t; + +/* Application specific hash function */ +typedef unsigned (*hash_f) ( const void *key ); + +/* 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 ); + +/* + * red black tree + */ + +/* Opaque types */ +typedef struct jsw_rbtree jsw_rbtree_t; +typedef struct jsw_rbtrav jsw_rbtrav_t; + +/* 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 ); + +#endif -- 2.40.0