1 /* 2 * Generic hash table implementation. 3 * 4 * Copyright (c) 2006 Dustin Sallings <dustin@spy.net> 5 */ 6 7 #ifndef GENHASH_H 8 #define GENHASH_H 1 9 #ifdef __cplusplus 10 extern "C" { 11 #endif 12 13 /*! \mainpage genhash 14 * 15 * \section intro_sec Introduction 16 * 17 * genhash is a generic hash table implementation in C. It's 18 * well-tested, freely available (MIT-license) and does what you need. 19 * 20 * \section docs_sec API Documentation 21 * 22 * Jump right into <a href="group___core.html">the API docs</a> to get started. 23 */ 24 25 /** 26 * \defgroup Core genhash core 27 */ 28 29 /** 30 * \addtogroup Core 31 * @{ 32 */ 33 34 /** 35 * Operations on keys and values in the hash table. 36 */ 37 struct lcb_hash_ops { 38 /** 39 * Function to compute a hash for the given value. 40 */ 41 int (*hashfunc)(const void *, lcb_size_t); 42 /** 43 * Function that returns true if the given keys are equal. 44 */ 45 int (*hasheq)(const void *, lcb_size_t, const void *, lcb_size_t); 46 /** 47 * Function to duplicate a key for storage. 48 */ 49 void *(*dup_key)(const void *, lcb_size_t); 50 /** 51 * Function to duplicate a value for storage. 52 */ 53 void *(*dup_value)(const void *, lcb_size_t); 54 /** 55 * Function to free a key. 56 */ 57 void (*free_key)(void *); 58 /** 59 * Function to free a value. 60 */ 61 void (*free_value)(void *); 62 }; 63 64 /** 65 * The hash table structure. 66 */ 67 typedef struct _genhash genhash_t ; 68 69 /** 70 * Type of update performed by an update function. 71 */ 72 enum update_type { 73 MODIFICATION, /**< This update is modifying an existing entry */ 74 NEW, /**< This update is creating a new entry */ 75 ALLOC_FAILURE 76 }; 77 78 /** 79 * Create a new generic hashtable. 80 * 81 * @param est the estimated number of items to store (must be > 0) 82 * @param ops the key and value operations 83 * 84 * @return the new genhash_t or NULL if one cannot be created 85 */ 86 genhash_t *genhash_init(lcb_size_t est, struct lcb_hash_ops ops); 87 88 /** 89 * Free a gen hash. 90 * 91 * @param h the genhash to free (may be NULL) 92 */ 93 void genhash_free(genhash_t *h); 94 95 /** 96 * Store an item. 97 * 98 * @param h the genhash 99 * @param k the key 100 * @param v the value 101 */ 102 int genhash_store(genhash_t *h, const void *k, lcb_size_t klen, 103 const void *v, lcb_size_t vlen); 104 105 /** 106 * Get the most recent value stored for the given key. 107 * 108 * @param h the genhash 109 * @param k the key 110 * 111 * @return the value, or NULL if one cannot be found 112 */ 113 void *genhash_find(genhash_t *h, const void *k, lcb_size_t klen); 114 115 /** 116 * Delete the most recent value stored for a key. 117 * 118 * @param h the genhash 119 * @param k the key 120 * 121 * @return the number of items deleted 122 */ 123 int genhash_delete(genhash_t *h, const void *k, lcb_size_t klen); 124 125 /** 126 * Delete all mappings of a given key. 127 * 128 * @param h the genhash 129 * @param k the key 130 * 131 * @return the number of items deleted 132 */ 133 int genhash_delete_all(genhash_t *h, const void *k, lcb_size_t klen); 134 135 /** 136 * Create or update an item in-place. 137 * 138 * @param h the genhash 139 * @param k the key 140 * @param v the new value to store for this key 141 * 142 * @return an indicator of whether this created a new item or updated 143 * an existing one 144 */ 145 enum update_type genhash_update(genhash_t *h, const void *k, lcb_size_t klen, 146 const void *v, lcb_size_t vlen); 147 148 /** 149 * Create or update an item in-place with a function. 150 * 151 * @param h hashtable 152 * @param key the key of the item 153 * @param upd function that will be called with the key and current 154 * value. Should return the new value. 155 * @param fr function to free the return value returned by the update 156 * function 157 * @param def default value 158 * 159 * @return an indicator of whether this created a new item or updated 160 * an existing one 161 */ 162 enum update_type genhash_fun_update(genhash_t *h, const void *key, lcb_size_t klen, 163 void * (*upd)(const void *k, const void *oldv, 164 lcb_size_t *ns, void *a), 165 void (*fr)(void *), 166 void *arg, 167 const void *def, lcb_size_t deflen); 168 169 /** 170 * Iterate all keys and values in a hash table. 171 * 172 * @param h the genhash 173 * @param iterfunc a function that will be called once for every k/v pair 174 * @param arg an argument to be passed to the iterfunc on each iteration 175 */ 176 void genhash_iter(genhash_t *h, 177 void (*iterfunc)(const void *key, lcb_size_t nkey, 178 const void *val, lcb_size_t nval, 179 void *arg), 180 void *arg); 181 182 /** 183 * Iterate all values for a given key in a hash table. 184 * 185 * @param h the genhash 186 * @param key the key to iterate 187 * @param iterfunc a function that will be called once for every k/v pair 188 * @param arg an argument to be passed to the iterfunc on each iteration 189 */ 190 void genhash_iter_key(genhash_t *h, const void *key, lcb_size_t nkey, 191 void (*iterfunc)(const void *key, lcb_size_t inkey, 192 const void *val, lcb_size_t inval, 193 void *arg), 194 void *arg); 195 196 /** 197 * Get the total number of entries in this hash table. 198 * 199 * @param h the genhash 200 * 201 * @return the number of entries in the hash table 202 */ 203 int genhash_size(genhash_t *h); 204 205 /** 206 * Remove all items from a genhash. 207 * 208 * @param h the genhash 209 * 210 * @return the number of items removed 211 */ 212 int genhash_clear(genhash_t *h); 213 214 /** 215 * Get the total number of entries in this hash table that map to the given 216 * key. 217 * 218 * @param h the genhash 219 * @param k a key 220 * 221 * @return the number of entries keyed with the given key 222 */ 223 int genhash_size_for_key(genhash_t *h, const void *k, lcb_size_t nkey); 224 225 /** 226 * Convenient hash function for strings. 227 * 228 * @param k a null-terminated string key. 229 * 230 * @return a hash value for this string. 231 */ 232 int genhash_string_hash(const void *k, lcb_size_t nkey); 233 234 /** 235 * @} 236 */ 237 238 #ifdef __cplusplus 239 } 240 #endif 241 #endif /* GENHASH_H */ 242