-
Notifications
You must be signed in to change notification settings - Fork 4
/
zhash.h
350 lines (310 loc) · 12.7 KB
/
zhash.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
#ifndef __ZHASH_H__
#define __ZHASH_H__
#include <stdint.h>
#ifdef __cplusplus
extern "C" {
#endif
#include "zarray.h"
// XXX const-ness
/**
* A hash table for structs and primitive types that stores entries by value.
* - The size of the key/values must be known at instantiation time, and remain fixed.
* e.g. for pointers: zhash_create(sizeof(void*), sizeof(void*)....)
* for structs: zhash_create(sizeof(struct key_struct), sizeof(struct value_struct)...)
* for bytes: zhash_create(sizeof(uint8_t), sizeof(uint8_t)...)
* - Entries are copied by value. This means you must always pass a reference to the start
* of 'key_size' and 'value_size' bytes, which you have already malloc'd or stack allocated
* - This data structure can be used to store types of any size, from bytes & doubles to
* user defined structs
* Note: if zhash stores pointers, user must be careful to manually manage the lifetime
* of the memory they point to.
**/
typedef struct zhash zhash_t;
// The contents of the iterator should be considered private. However,
// since our usage model prefers stack-based allocation of iterators,
// we must publicly declare them.
struct zhash_iterator {
zhash_t *zh;
// these point to the next bucket/bucket-entry to be examined.
int bucket;
int idx;
};
typedef struct zhash_iterator zhash_iterator_t;
/**
* Create, initializes, and returns an empty hash table structure. It is the
* caller's responsibility to call zhash_destroy() on the returned array when it
* is no longer needed.
*
* The size of values used in the hash and equals function must match 'keysz'.
* I.e. if keysz = sizeof(uint64_t), then hash() and equals() should accept
* parameters as *uint64_t.
*/
zhash_t *
zhash_create (size_t keysz, size_t valuesz,
uint32_t(*hash)(const void *a),
int(*equals)(const void *a, const void *b));
/**
* Frees all resources associated with the hash table structure which was
* created by zhash_create(). After calling, 'zh' will no longer be valid for storage.
*
* If 'zh' contains pointer data, it is the caller's responsibility to manage
* the resources pointed to by those pointers.
*/
void
zhash_destroy (zhash_t *zh);
/**
* Creates and returns a new identical copy of the zhash.
* If you're storing pointers, be sure not to double free their pointees!
* It is the caller's responsibility to call zhash_destroy() on the returned array
* when it is no longer needed (in addition to the zhash_destroy() call for the
* original zhash).
*/
zhash_t *
zhash_copy (zhash_t *other);
/**
* Determines whether the supplied key value exists as an entry in the zhash
* table. If zhash stores pointer types as keys, this function can differentiate
* between a non-existent key and a key mapped to NULL.
* Returns 1 if the supplied key exists in the zhash table, else 0.
*/
int
zhash_contains (const zhash_t *zh, const void *key);
/**
* Retrieves the value for the given key, if it exists, by copying its contents
* into the space pointed to by 'out_value', which must already be allocated.
* Returns 1 if the supplied key exists in the table, else 0, in which case
* the contents of 'out_value' will be unchanged.
*/
int
zhash_get (const zhash_t *zh, const void *key, void *out_value);
/**
* Similar to zhash_get(), but more dangerous. Provides a pointer to the zhash's
* internal storage. This can be used to make simple modifications to
* the underlying data while avoiding the memcpys associated with
* zhash_get and zhash_put. However, some zhash operations (that
* resize the underlying storage, in particular) render this pointer
* invalid. For maximum safety, call no other zhash functions for the
* period during which you intend to use the pointer.
* 'out_p' should be a pointer to the pointer which will be set to the internal
* data address.
*/
int
zhash_get_volatile (const zhash_t *zh, const void *key, void *out_p);
/**
* Adds a key/value pair to the hash table, if the supplied key does not already
* exist in the table, or overwrites the value for the supplied key if it does
* already exist. In the latter case, the previous contents of the key and value
* will be copied into the spaces pointed to by 'oldkey' and 'oldvalue', respectively,
* if they are not NULL.
*
* The key/value is added to / updated in the hash table by copying 'keysz' bytes
* from the data pointed to by 'key' and 'valuesz' bytes from the data pointed
* to by 'value'. It is up to the caller to manage the memory allocation of the
* passed-in values, zhash will store and manage a copy.
*
* NOTE: If the key is a pointer type (such as a string), the contents of the
* data that it points to must not be modified after the call to zhash_put(),
* or future zhash calls will not successfully locate the key (using either its
* previous or new value).
*
* NOTE: When using array data as a key (such as a string), the array should not
* be passed directly or it will cause a segmentation fault when it is dereferenced.
* Instead, pass a pointer which points to the array location, i.e.:
* char key[strlen];
* char *keyptr = key;
* zhash_put(zh, &keyptr, ...)
*
* Example:
* char * key = ...;
* zarray_t * val = ...;
* char * old_key = NULL;
* zarray_t * old_val = NULL;
* if (zhash_put(zh, &key, &val, &old_key, &old_value))
* // manage resources for old_key and old_value
*
* Returns 1 if the supplied key previously existed in the table, else 0, in
* which case the data pointed to by 'oldkey' and 'oldvalue' will be set to zero
* if they are not NULL.
*/
int
zhash_put (zhash_t *zh, const void *key, const void *value, void *oldkey, void *oldvalue);
/**
* Removes from the zhash table the key/value pair for the supplied key, if
* it exists. If it does, the contents of the key and value will be copied into
* the spaces pointed to by 'oldkey' and 'oldvalue', respectively, if they are
* not NULL. If the key does not exist, the data pointed to by 'oldkey' and
* 'oldvalue' will be set to zero if they are not NULL.
*
* Returns 1 if the key existed and was removed, else 0, indicating that the
* table contents were not changed.
*/
int
zhash_remove (zhash_t *zh, const void *key, void *oldkey, void *oldvalue);
/**
* Retrieves the current number of key/value pairs currently contained in the
* zhash table, or 0 if the table is empty.
*/
int
zhash_size (const zhash_t *zh);
/**
* Initializes an iterator which can be used to traverse the key/value pairs of
* the supplied zhash table via successive calls to zhash_iterator_next() or
* zhash_iterator_next_volatile().
*
* Any modifications to the zhash table structure will invalidate the
* iterator, with the exception of zhash_iterator_remove().
*/
void
zhash_iterator_init (zhash_t *zh, zhash_iterator_t *zit);
/**
* Retrieves the next key/value pair from a zhash table via the (previously-
* initialized) iterator. Copies the key and value data into the space
* pointed to by outkey and outvalue, respectively, if they are not NULL.
*
* Returns 1 if the call retrieved the next available key/value pair, else 0
* indicating that no entries remain, in which case the contents of outkey and
* outvalue will remain unchanged.
*/
int
zhash_iterator_next (zhash_iterator_t *zit, void *outkey, void *outvalue);
/**
* Similar to zhash_iterator_next() except that it retrieves a pointer to zhash's
* internal storage. This can be used to avoid the memcpys associated with
* zhash_iterator_next(). Call no other zhash functions for the
* period during which you intend to use the pointer.
* 'outkey' and 'outvalue' should be pointers to the pointers which will be set
* to the internal data addresses.
*
* Example:
* key_t *outkey;
* value_t *outvalue;
* if (zhash_iterator_next_volatile(&zit, &outkey, &outvalue))
* // access internal key and value storage via outkey and outvalue
*
* Returns 1 if the call retrieved the next available key/value pair, else 0
* indicating that no entries remain, in which case the pointers outkey and
* outvalue will remain unchanged.
*/
int
zhash_iterator_next_volatile (zhash_iterator_t *zit, void *outkey, void *outvalue);
/**
* Removes from the zhash table the key/value pair most recently returned via
* a call to zhash_iterator_next() or zhash_iterator_next_volatile() for the
* supplied iterator.
*/
void
zhash_iterator_remove (zhash_iterator_t *zit);
/**
* Calls the supplied function with a pointer to every key in the hash table in
* turn. The function will be passed a pointer to the table's internal storage
* for the key, which the caller should not modify, as the hash table will not be
* re-indexed. The function may be NULL, in which case no action is taken.
*/
void
zhash_map_keys (zhash_t *zh, void (*f)());
/**
* Calls the supplied function with a pointer to every value in the hash table in
* turn. The function will be passed a pointer to the table's internal storage
* for the value, which the caller may safely modify. The function may be NULL,
* in which case no action is taken.
*/
void
zhash_map_values (zhash_t *zh, void (*f)());
/**
* Calls the supplied function with a copy of every key in the hash table in
* turn. While zhash_map_keys() passes a pointer to internal storage, this function
* passes a copy of the actual storage. If the zhash stores pointers to data,
* functions like free() can be used directly with zhash_vmap_keys().
* The function may be NULL, in which case no action is taken.
*
* NOTE: zhash_vmap_keys() can only be used with pointer-data keys.
* Use with non-pointer keys (i.e. integer, double, etc.) will likely cause a
* segmentation fault.
*/
void
zhash_vmap_keys (zhash_t *vh, void (*f)());
/**
* Calls the supplied function with a copy of every value in the hash table in
* turn. While zhash_map_values() passes a pointer to internal storage, this function
* passes a copy of the actual storage. If the zhash stores pointers to data,
* functions like free() can be used directly with zhash_vmap_values().
* The function may be NULL, in which case no action is taken.
*
* NOTE: zhash_vmap_values() can only be used with pointer-data values.
* Use with non-pointer values (i.e. integer, double, etc.) will likely cause a
* segmentation fault.
*/
void
zhash_vmap_values (zhash_t *vh, void (*f)());
/**
* Returns an array which contains copis of all of the hash table's keys, in no
* particular order. It is the caller's responsibility to call zarray_destroy()
* on the returned structure when it is no longer needed.
*/
zarray_t *
zhash_keys (zhash_t *zh);
/**
* Returns an array which contains copis of all of the hash table's values, in no
* particular order. It is the caller's responsibility to call zarray_destroy()
* on the returned structure when it is no longer needed.
*/
zarray_t *
zhash_values (zhash_t *zh);
/**
* Defines a hash function which will calculate a zhash value for uint32_t input
* data. Can be used with zhash_create() for a key size of sizeof(uint32_t).
*/
uint32_t
zhash_uint32_hash (const void *a);
/**
* Defines a function to compare zhash values for uint32_t input data.
* Can be used with zhash_create() for a key size of sizeof(uint32_t).
*/
int
zhash_uint32_equals (const void *a, const void *b);
/**
* Defines a hash function which will calculate a zhash value for uint64_t input
* data. Can be used with zhash_create() for a key size of sizeof(uint64_t).
*/
uint32_t
zhash_uint64_hash (const void *a);
/**
* Defines a function to compare zhash values for uint64_t input data.
* Can be used with zhash_create() for a key size of sizeof(uint64_t).
*/
int
zhash_uint64_equals (const void *a, const void *b);
/////////////////////////////////////////////////////
// functions for keys that can be compared via their pointers.
/**
* Defines a hash function which will calculate a zhash value for pointer input
* data. Can be used with zhash_create() for a key size of sizeof(void*). Will
* use only the pointer value itself for computing the hash value.
*/
uint32_t
zhash_ptr_hash (const void *a);
/**
* Defines a function to compare zhash values for pointer input data.
* Can be used with zhash_create() for a key size of sizeof(void*).
*/
int
zhash_ptr_equals (const void *a, const void *b);
/////////////////////////////////////////////////////
// Functions for string-typed keys
/**
* Defines a hash function which will calculate a zhash value for string input
* data. Can be used with zhash_create() for a key size of sizeof(char*). Will
* use the contents of the string in computing the hash value.
*/
uint32_t
zhash_str_hash (const void *a);
/**
* Defines a function to compare zhash values for string input data.
* Can be used with zhash_create() for a key size of sizeof(char*).
*/
int
zhash_str_equals (const void *a, const void *b);
#ifdef __cplusplus
}
#endif
#endif //__ZHASH_H__