pd.if.org Git - zpackage/blob - lib/jsw/jsw.h

   1 #ifndef JSW_H
   2 #define JSW_H
   3
   4 /*
   5   Andersson tree library
   6
   7     > Created (Julienne Walker): September 10, 2005
   8
   9   AVL balanced tree library
  10
  11     > Created (Julienne Walker): June 17, 2003
  12     > Modified (Julienne Walker): September 24, 2005
  13
  14   Hash table library using separate chaining
  15
  16     > Created (Julienne Walker): August 7, 2005
  17     > Modified (Julienne Walker): August 11, 2005
  18
  19   Red Black balanced tree library
  20
  21     > Created (Julienne Walker): August 23, 2003
  22     > Modified (Julienne Walker): March 14, 2008
  23
  24   This code is in the public domain. Anyone may
  25   use it or change it in any way that they see
  26   fit. The author assumes no responsibility for
  27   damages incurred through use of the original
  28   code or any variations thereof.
  29
  30   It is requested, but not required, that due
  31   credit is given to the original author and
  32   anyone who has modified the code through
  33   a header comment, such as this one.
  34 */
  35
  36 /* code modified for inclusion in zpm */
  37
  38 #include <stddef.h>
  39
  40 /* User-defined item handling */
  41 typedef int   (*cmp_f) ( const void *p1, const void *p2 );
  42 typedef void *(*dup_f) ( void *p );
  43 typedef void  (*rel_f) ( void *p );
  44
  45 /*
  46  * Andersson tree
  47  */
  48
  49 /* Opaque types */
  50 typedef struct jsw_atree jsw_atree_t;
  51 typedef struct jsw_atrav jsw_atrav_t;
  52
  53 /* Andersson tree functions */
  54 jsw_atree_t *jsw_anew ( cmp_f cmp, dup_f dup, rel_f rel );
  55 void         jsw_adelete ( jsw_atree_t *tree );
  56 void        *jsw_afind ( jsw_atree_t *tree, void *data );
  57 int          jsw_ainsert ( jsw_atree_t *tree, void *data );
  58 int          jsw_aerase ( jsw_atree_t *tree, void *data );
  59 size_t       jsw_asize ( jsw_atree_t *tree );
  60
  61 /* Traversal functions */
  62 jsw_atrav_t *jsw_atnew ( void );
  63 void         jsw_atdelete ( jsw_atrav_t *trav );
  64 void        *jsw_atfirst ( jsw_atrav_t *trav, jsw_atree_t *tree );
  65 void        *jsw_atlast ( jsw_atrav_t *trav, jsw_atree_t *tree );
  66 void        *jsw_atnext ( jsw_atrav_t *trav );
  67 void        *jsw_atprev ( jsw_atrav_t *trav );
  68
  69 /*
  70  * AVL tree
  71  */
  72
  73 /* Opaque types */
  74 typedef struct jsw_avltree jsw_avltree_t;
  75 typedef struct jsw_avltrav jsw_avltrav_t;
  76
  77 /* AVL tree functions */
  78 jsw_avltree_t *jsw_avlnew ( cmp_f cmp, dup_f dup, rel_f rel );
  79 void           jsw_avldelete ( jsw_avltree_t *tree );
  80 void          *jsw_avlfind ( jsw_avltree_t *tree, void *data );
  81 int            jsw_avlinsert ( jsw_avltree_t *tree, void *data );
  82 int            jsw_avlerase ( jsw_avltree_t *tree, void *data );
  83 size_t         jsw_avlsize ( jsw_avltree_t *tree );
  84
  85 /* Traversal functions */
  86 jsw_avltrav_t *jsw_avltnew ( void );
  87 void           jsw_avltdelete ( jsw_avltrav_t *trav );
  88 void          *jsw_avltfirst ( jsw_avltrav_t *trav, jsw_avltree_t *tree );
  89 void          *jsw_avltlast ( jsw_avltrav_t *trav, jsw_avltree_t *tree );
  90 void          *jsw_avltnext ( jsw_avltrav_t *trav );
  91 void          *jsw_avltprev ( jsw_avltrav_t *trav );
  92
  93 /*
  94  * hash table
  95  */
  96
  97 typedef struct jsw_hash jsw_hash_t;
  98
  99 /* Application specific hash function */
 100 typedef unsigned (*hash_f) ( const void *key );
 101
 102 /* Application specific key copying function */
 103 typedef void    *(*keydup_f) ( const void *key );
 104
 105 /* Application specific data copying function */
 106 typedef void    *(*itemdup_f) ( const void *item );
 107
 108 /* Application specific key deletion function */
 109 typedef void     (*keyrel_f) ( void *key );
 110
 111 /* Application specific data deletion function */
 112 typedef void     (*itemrel_f) ( void *item );
 113
 114 typedef struct jsw_hstat {
 115   double load;            /* Table load factor: (M chains)/(table size) */
 116   double achain;          /* Average chain length */
 117   size_t lchain;          /* Longest chain */
 118   size_t schain;          /* Shortest non-empty chain */
 119 } jsw_hstat_t;
 120
 121 /*
 122   Create a new hash table with a capacity of size, and
 123   user defined functions for handling keys and items.
 124
 125   Returns: An empty hash table, or NULL on failure.
 126 */
 127 jsw_hash_t  *jsw_hnew ( size_t size, hash_f hash, cmp_f cmp,
 128                        keydup_f keydup, itemdup_f itemdup,
 129                        keyrel_f keyrel, itemrel_f itemrel );
 130
 131 /* Release all memory used by the hash table */
 132 void         jsw_hdelete ( jsw_hash_t *htab );
 133
 134 /*
 135   Find an item with the selected key
 136
 137   Returns: The item, or NULL if not found
 138 */
 139 void        *jsw_hfind ( jsw_hash_t *htab, void *key );
 140
 141 /*
 142   Insert an item with the selected key
 143
 144   Returns: non-zero for success, zero for failure
 145 */
 146 int          jsw_hinsert ( jsw_hash_t *htab, void *key, void *item );
 147
 148 /*
 149   Remove an item with the selected key
 150
 151   Returns: non-zero for success, zero for failure
 152 */
 153 int          jsw_herase ( jsw_hash_t *htab, void *key );
 154
 155 /*
 156   Grow or shrink the table, this is a slow operation
 157
 158   Returns: non-zero for success, zero for failure
 159 */
 160 int          jsw_hresize ( jsw_hash_t *htab, size_t new_size );
 161
 162 /* Reset the traversal markers to the beginning */
 163 void         jsw_hreset ( jsw_hash_t *htab );
 164
 165 /* Traverse forward by one key */
 166 int          jsw_hnext ( jsw_hash_t *htab );
 167
 168 /* Get the current key */
 169 const void  *jsw_hkey ( jsw_hash_t *htab );
 170
 171 /* Get the current item */
 172 void        *jsw_hitem ( jsw_hash_t *htab );
 173
 174 /* Current number of items in the table */
 175 size_t       jsw_hsize ( jsw_hash_t *htab );
 176
 177 /* Total allowable number of items without resizing */
 178 size_t       jsw_hcapacity ( jsw_hash_t *htab );
 179
 180 /* Get statistics for the hash table */
 181 jsw_hstat_t *jsw_hstat ( jsw_hash_t *htab );
 182
 183 /*
 184  * red black tree
 185  */
 186
 187 /* Opaque types */
 188 typedef struct jsw_rbtree jsw_rbtree_t;
 189 typedef struct jsw_rbtrav jsw_rbtrav_t;
 190
 191 /* Red Black tree functions */
 192 jsw_rbtree_t *jsw_rbnew ( cmp_f cmp, dup_f dup, rel_f rel );
 193 void          jsw_rbdelete ( jsw_rbtree_t *tree );
 194 void         *jsw_rbfind ( jsw_rbtree_t *tree, void *data );
 195 int           jsw_rbinsert ( jsw_rbtree_t *tree, void *data );
 196 int           jsw_rberase ( jsw_rbtree_t *tree, void *data );
 197 size_t        jsw_rbsize ( jsw_rbtree_t *tree );
 198
 199 /* Traversal functions */
 200 jsw_rbtrav_t *jsw_rbtnew ( void );
 201 void          jsw_rbtdelete ( jsw_rbtrav_t *trav );
 202 void         *jsw_rbtfirst ( jsw_rbtrav_t *trav, jsw_rbtree_t *tree );
 203 void         *jsw_rbtlast ( jsw_rbtrav_t *trav, jsw_rbtree_t *tree );
 204 void         *jsw_rbtnext ( jsw_rbtrav_t *trav );
 205 void         *jsw_rbtprev ( jsw_rbtrav_t *trav );
 206
 207 #endif