pd.if.org Git - jsw/blob - jsw_hlib.h

   1 #ifndef JSW_HLIB\r
   2 #define JSW_HLIB\r
   3 \r
   4 /*\r
   5   Hash table library using separate chaining\r
   6 \r
   7     > Created (Julienne Walker): August 7, 2005\r
   8     > Modified (Julienne Walker): August 11, 2005\r
   9 \r
  10   This code is in the public domain. Anyone may\r
  11   use it or change it in any way that they see\r
  12   fit. The author assumes no responsibility for \r
  13   damages incurred through use of the original\r
  14   code or any variations thereof.\r
  15 \r
  16   It is requested, but not required, that due\r
  17   credit is given to the original author and\r
  18   anyone who has modified the code through\r
  19   a header comment, such as this one.\r
  20 */\r
  21 #ifdef __cplusplus\r
  22 #include <cstddef>\r
  23 \r
  24 using std::size_t;\r
  25 \r
  26 extern "C" {\r
  27 #else\r
  28 #include <stddef.h>\r
  29 #endif\r
  30 \r
  31 typedef struct jsw_hash jsw_hash_t;\r
  32 \r
  33 /* Application specific hash function */\r
  34 typedef unsigned (*hash_f) ( const void *key );\r
  35 \r
  36 /* Application specific key comparison function */\r
  37 typedef int      (*cmp_f) ( const void *a, const void *b );\r
  38 \r
  39 /* Application specific key copying function */\r
  40 typedef void    *(*keydup_f) ( const void *key );\r
  41 \r
  42 /* Application specific data copying function */\r
  43 typedef void    *(*itemdup_f) ( const void *item );\r
  44 \r
  45 /* Application specific key deletion function */\r
  46 typedef void     (*keyrel_f) ( void *key );\r
  47 \r
  48 /* Application specific data deletion function */\r
  49 typedef void     (*itemrel_f) ( void *item );\r
  50 \r
  51 typedef struct jsw_hstat {\r
  52   double load;            /* Table load factor: (M chains)/(table size) */\r
  53   double achain;          /* Average chain length */\r
  54   size_t lchain;          /* Longest chain */\r
  55   size_t schain;          /* Shortest non-empty chain */\r
  56 } jsw_hstat_t;\r
  57 \r
  58 /*\r
  59   Create a new hash table with a capacity of size, and\r
  60   user defined functions for handling keys and items.\r
  61 \r
  62   Returns: An empty hash table, or NULL on failure.\r
  63 */\r
  64 jsw_hash_t  *jsw_hnew ( size_t size, hash_f hash, cmp_f cmp,\r
  65                        keydup_f keydup, itemdup_f itemdup,\r
  66                        keyrel_f keyrel, itemrel_f itemrel );\r
  67 \r
  68 /* Release all memory used by the hash table */\r
  69 void         jsw_hdelete ( jsw_hash_t *htab );\r
  70 \r
  71 /*\r
  72   Find an item with the selected key\r
  73 \r
  74   Returns: The item, or NULL if not found\r
  75 */\r
  76 void        *jsw_hfind ( jsw_hash_t *htab, void *key );\r
  77 \r
  78 /*\r
  79   Insert an item with the selected key\r
  80 \r
  81   Returns: non-zero for success, zero for failure\r
  82 */\r
  83 int          jsw_hinsert ( jsw_hash_t *htab, void *key, void *item );\r
  84 \r
  85 /*\r
  86   Remove an item with the selected key\r
  87 \r
  88   Returns: non-zero for success, zero for failure\r
  89 */\r
  90 int          jsw_herase ( jsw_hash_t *htab, void *key );\r
  91 \r
  92 /*\r
  93   Grow or shrink the table, this is a slow operation\r
  94   \r
  95   Returns: non-zero for success, zero for failure\r
  96 */\r
  97 int          jsw_hresize ( jsw_hash_t *htab, size_t new_size );\r
  98 \r
  99 /* Reset the traversal markers to the beginning */\r
 100 void         jsw_hreset ( jsw_hash_t *htab );\r
 101 \r
 102 /* Traverse forward by one key */\r
 103 int          jsw_hnext ( jsw_hash_t *htab );\r
 104 \r
 105 /* Get the current key */\r
 106 const void  *jsw_hkey ( jsw_hash_t *htab );\r
 107 \r
 108 /* Get the current item */\r
 109 void        *jsw_hitem ( jsw_hash_t *htab );\r
 110 \r
 111 /* Current number of items in the table */\r
 112 size_t       jsw_hsize ( jsw_hash_t *htab );\r
 113 \r
 114 /* Total allowable number of items without resizing */\r
 115 size_t       jsw_hcapacity ( jsw_hash_t *htab );\r
 116 \r
 117 /* Get statistics for the hash table */\r
 118 jsw_hstat_t *jsw_hstat ( jsw_hash_t *htab );\r
 119 \r
 120 #ifdef __cplusplus\r
 121 }\r
 122 #endif\r
 123 \r
 124 #endif\r