#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