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