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