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