]>
Commit | Line | Data |
---|---|---|
60918275 LP |
1 | /*-*- Mode: C; c-basic-offset: 8 -*-*/ |
2 | ||
3 | #ifdef HAVE_CONFIG_H | |
4 | #include <config.h> | |
5 | #endif | |
6 | ||
7 | #include <assert.h> | |
8 | #include <stdlib.h> | |
9 | #include <string.h> | |
10 | #include <errno.h> | |
11 | ||
12 | #include "util.h" | |
13 | #include "hashmap.h" | |
14 | #include "macro.h" | |
15 | ||
16 | #define NBUCKETS 127 | |
17 | ||
18 | struct hashmap_entry { | |
19 | const void *key; | |
20 | void *value; | |
21 | ||
22 | struct hashmap_entry *bucket_next, *bucket_previous; | |
23 | struct hashmap_entry *iterate_next, *iterate_previous; | |
24 | }; | |
25 | ||
26 | struct Hashmap { | |
27 | hash_func_t hash_func; | |
28 | compare_func_t compare_func; | |
29 | ||
30 | struct hashmap_entry *iterate_list_head, *iterate_list_tail; | |
31 | unsigned n_entries; | |
32 | }; | |
33 | ||
34 | #define BY_HASH(h) ((struct hashmap_entry**) ((uint8_t*) (h) + ALIGN(sizeof(Hashmap)))) | |
35 | ||
36 | unsigned string_hash_func(const void *p) { | |
37 | unsigned hash = 0; | |
38 | const char *c; | |
39 | ||
40 | for (c = p; *c; c++) | |
41 | hash = 31 * hash + (unsigned) *c; | |
42 | ||
43 | return hash; | |
44 | } | |
45 | ||
46 | int string_compare_func(const void *a, const void *b) { | |
47 | return strcmp(a, b); | |
48 | } | |
49 | ||
50 | unsigned trivial_hash_func(const void *p) { | |
51 | return PTR_TO_UINT(p); | |
52 | } | |
53 | ||
54 | int trivial_compare_func(const void *a, const void *b) { | |
55 | return a < b ? -1 : (a > b ? 1 : 0); | |
56 | } | |
57 | ||
58 | Hashmap *hashmap_new(hash_func_t hash_func, compare_func_t compare_func) { | |
59 | Hashmap *h; | |
60 | ||
61 | if (!(h = malloc0(ALIGN(sizeof(Hashmap)) + NBUCKETS * ALIGN(sizeof(struct hashmap_entry*))))) | |
62 | return NULL; | |
63 | ||
64 | h->hash_func = hash_func ? hash_func : trivial_hash_func; | |
65 | h->compare_func = compare_func ? compare_func : trivial_compare_func; | |
66 | ||
67 | h->n_entries = 0; | |
68 | h->iterate_list_head = h->iterate_list_tail = NULL; | |
69 | ||
70 | return h; | |
71 | } | |
72 | ||
73 | static void remove_entry(Hashmap *h, struct hashmap_entry *e) { | |
74 | assert(h); | |
75 | assert(e); | |
76 | ||
77 | /* Remove from iteration list */ | |
78 | if (e->iterate_next) | |
79 | e->iterate_next->iterate_previous = e->iterate_previous; | |
80 | else | |
81 | h->iterate_list_tail = e->iterate_previous; | |
82 | ||
83 | if (e->iterate_previous) | |
84 | e->iterate_previous->iterate_next = e->iterate_next; | |
85 | else | |
86 | h->iterate_list_head = e->iterate_next; | |
87 | ||
88 | /* Remove from hash table bucket list */ | |
89 | if (e->bucket_next) | |
90 | e->bucket_next->bucket_previous = e->bucket_previous; | |
91 | ||
92 | if (e->bucket_previous) | |
93 | e->bucket_previous->bucket_next = e->bucket_next; | |
94 | else { | |
95 | unsigned hash = h->hash_func(e->key) % NBUCKETS; | |
96 | BY_HASH(h)[hash] = e->bucket_next; | |
97 | } | |
98 | ||
99 | free(e); | |
100 | ||
101 | assert(h->n_entries >= 1); | |
102 | h->n_entries--; | |
103 | } | |
104 | ||
105 | void hashmap_free(Hashmap*h) { | |
106 | ||
107 | if (!h) | |
108 | return; | |
109 | ||
110 | while (h->iterate_list_head) | |
111 | remove_entry(h, h->iterate_list_head); | |
112 | ||
113 | free(h); | |
114 | } | |
115 | ||
116 | static struct hashmap_entry *hash_scan(Hashmap *h, unsigned hash, const void *key) { | |
117 | struct hashmap_entry *e; | |
118 | assert(h); | |
119 | assert(hash < NBUCKETS); | |
120 | ||
121 | for (e = BY_HASH(h)[hash]; e; e = e->bucket_next) | |
122 | if (h->compare_func(e->key, key) == 0) | |
123 | return e; | |
124 | ||
125 | return NULL; | |
126 | } | |
127 | ||
128 | int hashmap_put(Hashmap *h, const void *key, void *value) { | |
129 | struct hashmap_entry *e; | |
130 | unsigned hash; | |
131 | ||
132 | assert(h); | |
133 | ||
134 | hash = h->hash_func(key) % NBUCKETS; | |
135 | ||
136 | if (hash_scan(h, hash, key)) | |
137 | return -EEXIST; | |
138 | ||
139 | if (!(e = new(struct hashmap_entry, 1))) | |
140 | return -ENOMEM; | |
141 | ||
142 | e->key = key; | |
143 | e->value = value; | |
144 | ||
145 | /* Insert into hash table */ | |
146 | e->bucket_next = BY_HASH(h)[hash]; | |
147 | e->bucket_previous = NULL; | |
148 | if (BY_HASH(h)[hash]) | |
149 | BY_HASH(h)[hash]->bucket_previous = e; | |
150 | BY_HASH(h)[hash] = e; | |
151 | ||
152 | /* Insert into iteration list */ | |
153 | e->iterate_previous = h->iterate_list_tail; | |
154 | e->iterate_next = NULL; | |
155 | if (h->iterate_list_tail) { | |
156 | assert(h->iterate_list_head); | |
157 | h->iterate_list_tail->iterate_next = e; | |
158 | } else { | |
159 | assert(!h->iterate_list_head); | |
160 | h->iterate_list_head = e; | |
161 | } | |
162 | h->iterate_list_tail = e; | |
163 | ||
164 | h->n_entries++; | |
165 | assert(h->n_entries >= 1); | |
166 | ||
167 | return 0; | |
168 | } | |
169 | ||
170 | void* hashmap_get(Hashmap *h, const void *key) { | |
171 | unsigned hash; | |
172 | struct hashmap_entry *e; | |
173 | ||
174 | if (!h) | |
175 | return NULL; | |
176 | ||
177 | hash = h->hash_func(key) % NBUCKETS; | |
178 | ||
179 | if (!(e = hash_scan(h, hash, key))) | |
180 | return NULL; | |
181 | ||
182 | return e->value; | |
183 | } | |
184 | ||
185 | void* hashmap_remove(Hashmap *h, const void *key) { | |
186 | struct hashmap_entry *e; | |
187 | unsigned hash; | |
188 | void *data; | |
189 | ||
190 | if (!h) | |
191 | return NULL; | |
192 | ||
193 | hash = h->hash_func(key) % NBUCKETS; | |
194 | ||
195 | if (!(e = hash_scan(h, hash, key))) | |
196 | return NULL; | |
197 | ||
198 | data = e->value; | |
199 | remove_entry(h, e); | |
200 | ||
201 | return data; | |
202 | } | |
203 | ||
204 | void *hashmap_iterate(Hashmap *h, void **state, const void **key) { | |
205 | struct hashmap_entry *e; | |
206 | ||
207 | assert(state); | |
208 | ||
209 | if (!h) | |
210 | goto at_end; | |
211 | ||
212 | if (*state == (void*) -1) | |
213 | goto at_end; | |
214 | ||
215 | if (!*state && !h->iterate_list_head) | |
216 | goto at_end; | |
217 | ||
218 | e = *state ? *state : h->iterate_list_head; | |
219 | ||
220 | if (e->iterate_next) | |
221 | *state = e->iterate_next; | |
222 | else | |
223 | *state = (void*) -1; | |
224 | ||
225 | if (key) | |
226 | *key = e->key; | |
227 | ||
228 | return e->value; | |
229 | ||
230 | at_end: | |
231 | *state = (void *) -1; | |
232 | ||
233 | if (key) | |
234 | *key = NULL; | |
235 | ||
236 | return NULL; | |
237 | } | |
238 | ||
239 | void *hashmap_iterate_backwards(Hashmap *h, void **state, const void **key) { | |
240 | struct hashmap_entry *e; | |
241 | ||
242 | assert(state); | |
243 | ||
244 | if (!h) | |
245 | goto at_beginning; | |
246 | ||
247 | if (*state == (void*) -1) | |
248 | goto at_beginning; | |
249 | ||
250 | if (!*state && !h->iterate_list_tail) | |
251 | goto at_beginning; | |
252 | ||
253 | e = *state ? *state : h->iterate_list_tail; | |
254 | ||
255 | if (e->iterate_previous) | |
256 | *state = e->iterate_previous; | |
257 | else | |
258 | *state = (void*) -1; | |
259 | ||
260 | if (key) | |
261 | *key = e->key; | |
262 | ||
263 | return e->value; | |
264 | ||
265 | at_beginning: | |
266 | *state = (void *) -1; | |
267 | ||
268 | if (key) | |
269 | *key = NULL; | |
270 | ||
271 | return NULL; | |
272 | } | |
273 | ||
274 | void* hashmap_first(Hashmap *h) { | |
275 | ||
276 | if (!h) | |
277 | return NULL; | |
278 | ||
279 | if (!h->iterate_list_head) | |
280 | return NULL; | |
281 | ||
282 | return h->iterate_list_head->value; | |
283 | } | |
284 | ||
285 | void* hashmap_last(Hashmap *h) { | |
286 | ||
287 | if (!h) | |
288 | return NULL; | |
289 | ||
290 | if (!h->iterate_list_tail) | |
291 | return NULL; | |
292 | ||
293 | return h->iterate_list_tail->value; | |
294 | } | |
295 | ||
296 | void* hashmap_steal_first(Hashmap *h) { | |
297 | void *data; | |
298 | ||
299 | if (!h) | |
300 | return NULL; | |
301 | ||
302 | if (!h->iterate_list_head) | |
303 | return NULL; | |
304 | ||
305 | data = h->iterate_list_head->value; | |
306 | remove_entry(h, h->iterate_list_head); | |
307 | ||
308 | return data; | |
309 | } | |
310 | ||
311 | unsigned hashmap_size(Hashmap *h) { | |
312 | ||
313 | if (!h) | |
314 | return 0; | |
315 | ||
316 | return h->n_entries; | |
317 | } | |
318 | ||
319 | bool hashmap_isempty(Hashmap *h) { | |
320 | ||
321 | if (!h) | |
322 | return true; | |
323 | ||
324 | return h->n_entries == 0; | |
325 | } |