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
|
/*
* Copyright (c) 2016-2018 David Leeds <davidesleeds@gmail.com>
*
* Hashmap is free software; you can redistribute it and/or modify
* it under the terms of the MIT license. See LICENSE for details.
*/
#ifndef __HASHMAP_H__
#define __HASHMAP_H__
#include <stddef.h>
/*
* Define HASHMAP_METRICS to compile in performance analysis
* functions for use in assessing hash function performance.
*/
/* #define HASHMAP_METRICS */
/*
* Define HASHMAP_NOASSERT to compile out all assertions used internally.
*/
/* #define HASHMAP_NOASSERT */
/*
* Macros to declare type-specific versions of hashmap_*() functions to
* allow compile-time type checking and avoid the need for type casting.
*/
#define HASHMAP_FUNCS_DECLARE(name, key_type, data_type) \
data_type *name##_hashmap_put(struct hashmap *map, \
const key_type *key, data_type *data); \
data_type *name##_hashmap_get(const struct hashmap *map, \
const key_type *key); \
data_type *name##_hashmap_remove(struct hashmap *map, \
const key_type *key); \
const key_type *name##_hashmap_iter_get_key( \
const struct hashmap_iter *iter); \
data_type *name##_hashmap_iter_get_data( \
const struct hashmap_iter *iter); \
void name##_hashmap_iter_set_data(const struct hashmap_iter *iter, \
data_type *data); \
int name##_hashmap_foreach(const struct hashmap *map, \
int (*func)(const key_type *, data_type *, void *), void *arg);
#define HASHMAP_FUNCS_CREATE(name, key_type, data_type) \
data_type *name##_hashmap_put(struct hashmap *map, \
const key_type *key, data_type *data) \
{ \
return (data_type *)hashmap_put(map, (const void *)key, \
(void *)data); \
} \
data_type *name##_hashmap_get(const struct hashmap *map, \
const key_type *key) \
{ \
return (data_type *)hashmap_get(map, (const void *)key); \
} \
data_type *name##_hashmap_remove(struct hashmap *map, \
const key_type *key) \
{ \
return (data_type *)hashmap_remove(map, (const void *)key); \
} \
const key_type *name##_hashmap_iter_get_key( \
const struct hashmap_iter *iter) \
{ \
return (const key_type *)hashmap_iter_get_key(iter); \
} \
data_type *name##_hashmap_iter_get_data( \
const struct hashmap_iter *iter) \
{ \
return (data_type *)hashmap_iter_get_data(iter); \
} \
void name##_hashmap_iter_set_data(const struct hashmap_iter *iter, \
data_type *data) \
{ \
hashmap_iter_set_data(iter, (void *)data); \
} \
struct __##name##_hashmap_foreach_state { \
int (*func)(const key_type *, data_type *, void *); \
void *arg; \
}; \
static inline int __##name##_hashmap_foreach_callback( \
const void *key, void *data, void *arg) \
{ \
struct __##name##_hashmap_foreach_state *s = \
(struct __##name##_hashmap_foreach_state *)arg; \
return s->func((const key_type *)key, \
(data_type *)data, s->arg); \
} \
int name##_hashmap_foreach(const struct hashmap *map, \
int (*func)(const key_type *, data_type *, void *), \
void *arg) \
{ \
struct __##name##_hashmap_foreach_state s = { func, arg }; \
return hashmap_foreach(map, \
__##name##_hashmap_foreach_callback, &s); \
}
struct hashmap_iter;
struct hashmap_entry;
/*
* The hashmap state structure.
*/
struct hashmap {
size_t table_size_init;
size_t table_size;
size_t num_entries;
struct hashmap_entry *table;
size_t (*hash)(const void *);
int (*key_compare)(const void *, const void *);
void *(*key_alloc)(const void *);
void (*key_free)(void *);
};
/*
* Initialize an empty hashmap.
*
* hash_func should return an even distribution of numbers between 0
* and SIZE_MAX varying on the key provided. If set to NULL, the default
* case-sensitive string hash function is used: hashmap_hash_string
*
* key_compare_func should return 0 if the keys match, and non-zero otherwise.
* If set to NULL, the default case-sensitive string comparator function is
* used: hashmap_compare_string
*
* initial_size is optional, and may be set to the max number of entries
* expected to be put in the hash table. This is used as a hint to
* pre-allocate the hash table to the minimum size needed to avoid
* gratuitous rehashes. If initial_size is 0, a default size will be used.
*
* Returns 0 on success and -errno on failure.
*/
int hashmap_init(struct hashmap *map, size_t (*hash_func)(const void *),
int (*key_compare_func)(const void *, const void *),
size_t initial_size);
/*
* Free the hashmap and all associated memory.
*/
void hashmap_destroy(struct hashmap *map);
/*
* Enable internal memory allocation and management of hash keys.
*/
void hashmap_set_key_alloc_funcs(struct hashmap *map,
void *(*key_alloc_func)(const void *),
void (*key_free_func)(void *));
/*
* Add an entry to the hashmap. If an entry with a matching key already
* exists and has a data pointer associated with it, the existing data
* pointer is returned, instead of assigning the new value. Compare
* the return value with the data passed in to determine if a new entry was
* created. Returns NULL if memory allocation failed.
*/
void *hashmap_put(struct hashmap *map, const void *key, void *data);
/*
* Return the data pointer, or NULL if no entry exists.
*/
void *hashmap_get(const struct hashmap *map, const void *key);
/*
* Remove an entry with the specified key from the map.
* Returns the data pointer, or NULL, if no entry was found.
*/
void *hashmap_remove(struct hashmap *map, const void *key);
/*
* Remove all entries.
*/
void hashmap_clear(struct hashmap *map);
/*
* Remove all entries and reset the hash table to its initial size.
*/
void hashmap_reset(struct hashmap *map);
/*
* Return the number of entries in the hash map.
*/
size_t hashmap_size(const struct hashmap *map);
/*
* Get a new hashmap iterator. The iterator is an opaque
* pointer that may be used with hashmap_iter_*() functions.
* Hashmap iterators are INVALID after a put or remove operation is performed.
* hashmap_iter_remove() allows safe removal during iteration.
*/
struct hashmap_iter *hashmap_iter(const struct hashmap *map);
/*
* Return an iterator to the next hashmap entry. Returns NULL if there are
* no more entries.
*/
struct hashmap_iter *hashmap_iter_next(const struct hashmap *map,
const struct hashmap_iter *iter);
/*
* Remove the hashmap entry pointed to by this iterator and returns an
* iterator to the next entry. Returns NULL if there are no more entries.
*/
struct hashmap_iter *hashmap_iter_remove(struct hashmap *map,
const struct hashmap_iter *iter);
/*
* Return the key of the entry pointed to by the iterator.
*/
const void *hashmap_iter_get_key(const struct hashmap_iter *iter);
/*
* Return the data of the entry pointed to by the iterator.
*/
void *hashmap_iter_get_data(const struct hashmap_iter *iter);
/*
* Set the data pointer of the entry pointed to by the iterator.
*/
void hashmap_iter_set_data(const struct hashmap_iter *iter, void *data);
/*
* Invoke func for each entry in the hashmap. Unlike the hashmap_iter_*()
* interface, this function supports calls to hashmap_remove() during iteration.
* However, it is an error to put or remove an entry other than the current one,
* and doing so will immediately halt iteration and return an error.
* Iteration is stopped if func returns non-zero. Returns func's return
* value if it is < 0, otherwise, 0.
*/
int hashmap_foreach(const struct hashmap *map,
int (*func)(const void *, void *, void *), void *arg);
/*
* Default hash function for string keys.
* This is an implementation of the well-documented Jenkins one-at-a-time
* hash function.
*/
size_t hashmap_hash_string(const void *key);
/*
* Default key comparator function for string keys.
*/
int hashmap_compare_string(const void *a, const void *b);
/*
* Default key allocation function for string keys. Use free() for the
* key_free_func.
*/
void *hashmap_alloc_key_string(const void *key);
/*
* Case insensitive hash function for string keys.
*/
size_t hashmap_hash_string_i(const void *key);
/*
* Case insensitive key comparator function for string keys.
*/
int hashmap_compare_string_i(const void *a, const void *b);
#ifdef HASHMAP_METRICS
/*
* Return the load factor.
*/
double hashmap_load_factor(const struct hashmap *map);
/*
* Return the average number of collisions per entry.
*/
double hashmap_collisions_mean(const struct hashmap *map);
/*
* Return the variance between entry collisions. The higher the variance,
* the more likely the hash function is poor and is resulting in clustering.
*/
double hashmap_collisions_variance(const struct hashmap *map);
#endif
#endif /* __HASHMAP_H__ */
|
