]>
Commit | Line | Data |
---|---|---|
d6c9574f | 1 | /*-*- Mode: C; c-basic-offset: 8; indent-tabs-mode: nil -*-*/ |
60918275 | 2 | |
a7334b09 LP |
3 | /*** |
4 | This file is part of systemd. | |
5 | ||
6 | Copyright 2010 Lennart Poettering | |
7 | ||
8 | systemd is free software; you can redistribute it and/or modify it | |
5430f7f2 LP |
9 | under the terms of the GNU Lesser General Public License as published by |
10 | the Free Software Foundation; either version 2.1 of the License, or | |
a7334b09 LP |
11 | (at your option) any later version. |
12 | ||
13 | systemd is distributed in the hope that it will be useful, but | |
14 | WITHOUT ANY WARRANTY; without even the implied warranty of | |
15 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | |
5430f7f2 | 16 | Lesser General Public License for more details. |
a7334b09 | 17 | |
5430f7f2 | 18 | You should have received a copy of the GNU Lesser General Public License |
a7334b09 LP |
19 | along with systemd; If not, see <http://www.gnu.org/licenses/>. |
20 | ***/ | |
21 | ||
60918275 LP |
22 | #include <assert.h> |
23 | #include <stdlib.h> | |
24 | #include <string.h> | |
25 | #include <errno.h> | |
26 | ||
27 | #include "util.h" | |
28 | #include "hashmap.h" | |
29 | #include "macro.h" | |
9bf3b535 | 30 | #include "siphash24.h" |
60918275 | 31 | |
45fa9e29 | 32 | #define INITIAL_N_BUCKETS 31 |
60918275 LP |
33 | |
34 | struct hashmap_entry { | |
35 | const void *key; | |
36 | void *value; | |
60918275 LP |
37 | struct hashmap_entry *bucket_next, *bucket_previous; |
38 | struct hashmap_entry *iterate_next, *iterate_previous; | |
39 | }; | |
40 | ||
41 | struct Hashmap { | |
d5099efc | 42 | const struct hash_ops *hash_ops; |
60918275 LP |
43 | |
44 | struct hashmap_entry *iterate_list_head, *iterate_list_tail; | |
45fa9e29 LP |
45 | |
46 | struct hashmap_entry ** buckets; | |
47 | unsigned n_buckets, n_entries; | |
39c2a6f1 | 48 | |
9bf3b535 LP |
49 | uint8_t hash_key[HASH_KEY_SIZE]; |
50 | bool from_pool:1; | |
60918275 LP |
51 | }; |
52 | ||
39c2a6f1 LP |
53 | struct pool { |
54 | struct pool *next; | |
55 | unsigned n_tiles; | |
56 | unsigned n_used; | |
57 | }; | |
58 | ||
6a39419f | 59 | static struct pool *first_hashmap_pool = NULL; |
39c2a6f1 LP |
60 | static void *first_hashmap_tile = NULL; |
61 | ||
6a39419f | 62 | static struct pool *first_entry_pool = NULL; |
39c2a6f1 LP |
63 | static void *first_entry_tile = NULL; |
64 | ||
3febea3a | 65 | static void* allocate_tile(struct pool **first_pool, void **first_tile, size_t tile_size, unsigned at_least) { |
39c2a6f1 LP |
66 | unsigned i; |
67 | ||
45fa9e29 LP |
68 | /* When a tile is released we add it to the list and simply |
69 | * place the next pointer at its offset 0. */ | |
70 | ||
71 | assert(tile_size >= sizeof(void*)); | |
3febea3a | 72 | assert(at_least > 0); |
45fa9e29 | 73 | |
39c2a6f1 LP |
74 | if (*first_tile) { |
75 | void *r; | |
76 | ||
77 | r = *first_tile; | |
78 | *first_tile = * (void**) (*first_tile); | |
79 | return r; | |
80 | } | |
81 | ||
82 | if (_unlikely_(!*first_pool) || _unlikely_((*first_pool)->n_used >= (*first_pool)->n_tiles)) { | |
83 | unsigned n; | |
84 | size_t size; | |
85 | struct pool *p; | |
86 | ||
87 | n = *first_pool ? (*first_pool)->n_tiles : 0; | |
3febea3a | 88 | n = MAX(at_least, n * 2); |
39c2a6f1 LP |
89 | size = PAGE_ALIGN(ALIGN(sizeof(struct pool)) + n*tile_size); |
90 | n = (size - ALIGN(sizeof(struct pool))) / tile_size; | |
91 | ||
92 | p = malloc(size); | |
93 | if (!p) | |
94 | return NULL; | |
95 | ||
96 | p->next = *first_pool; | |
97 | p->n_tiles = n; | |
98 | p->n_used = 0; | |
99 | ||
100 | *first_pool = p; | |
101 | } | |
102 | ||
103 | i = (*first_pool)->n_used++; | |
104 | ||
105 | return ((uint8_t*) (*first_pool)) + ALIGN(sizeof(struct pool)) + i*tile_size; | |
106 | } | |
107 | ||
108 | static void deallocate_tile(void **first_tile, void *p) { | |
109 | * (void**) p = *first_tile; | |
110 | *first_tile = p; | |
111 | } | |
112 | ||
090cafa0 | 113 | #ifdef VALGRIND |
39c2a6f1 LP |
114 | |
115 | static void drop_pool(struct pool *p) { | |
116 | while (p) { | |
117 | struct pool *n; | |
118 | n = p->next; | |
119 | free(p); | |
120 | p = n; | |
121 | } | |
122 | } | |
123 | ||
124 | __attribute__((destructor)) static void cleanup_pool(void) { | |
125 | /* Be nice to valgrind */ | |
126 | ||
127 | drop_pool(first_hashmap_pool); | |
128 | drop_pool(first_entry_pool); | |
129 | } | |
130 | ||
131 | #endif | |
132 | ||
9bf3b535 LP |
133 | unsigned long string_hash_func(const void *p, const uint8_t hash_key[HASH_KEY_SIZE]) { |
134 | uint64_t u; | |
135 | siphash24((uint8_t*) &u, p, strlen(p), hash_key); | |
136 | return (unsigned long) u; | |
60918275 LP |
137 | } |
138 | ||
139 | int string_compare_func(const void *a, const void *b) { | |
140 | return strcmp(a, b); | |
141 | } | |
142 | ||
d5099efc MS |
143 | const struct hash_ops string_hash_ops = { |
144 | .hash = string_hash_func, | |
145 | .compare = string_compare_func | |
146 | }; | |
147 | ||
9bf3b535 LP |
148 | unsigned long trivial_hash_func(const void *p, const uint8_t hash_key[HASH_KEY_SIZE]) { |
149 | uint64_t u; | |
150 | siphash24((uint8_t*) &u, &p, sizeof(p), hash_key); | |
151 | return (unsigned long) u; | |
60918275 LP |
152 | } |
153 | ||
154 | int trivial_compare_func(const void *a, const void *b) { | |
155 | return a < b ? -1 : (a > b ? 1 : 0); | |
156 | } | |
157 | ||
d5099efc MS |
158 | const struct hash_ops trivial_hash_ops = { |
159 | .hash = trivial_hash_func, | |
160 | .compare = trivial_compare_func | |
161 | }; | |
162 | ||
9bf3b535 | 163 | unsigned long uint64_hash_func(const void *p, const uint8_t hash_key[HASH_KEY_SIZE]) { |
a4bcff5b | 164 | uint64_t u; |
9bf3b535 LP |
165 | siphash24((uint8_t*) &u, p, sizeof(uint64_t), hash_key); |
166 | return (unsigned long) u; | |
a4bcff5b LP |
167 | } |
168 | ||
169 | int uint64_compare_func(const void *_a, const void *_b) { | |
170 | uint64_t a, b; | |
a4bcff5b LP |
171 | a = *(const uint64_t*) _a; |
172 | b = *(const uint64_t*) _b; | |
a4bcff5b LP |
173 | return a < b ? -1 : (a > b ? 1 : 0); |
174 | } | |
175 | ||
d5099efc MS |
176 | const struct hash_ops uint64_hash_ops = { |
177 | .hash = uint64_hash_func, | |
178 | .compare = uint64_compare_func | |
179 | }; | |
180 | ||
de99c9dc LP |
181 | #if SIZEOF_DEV_T != 8 |
182 | unsigned long devt_hash_func(const void *p, const uint8_t hash_key[HASH_KEY_SIZE]) { | |
183 | uint64_t u; | |
184 | siphash24((uint8_t*) &u, p, sizeof(dev_t), hash_key); | |
185 | return (unsigned long) u; | |
186 | } | |
187 | ||
188 | int devt_compare_func(const void *_a, const void *_b) { | |
189 | dev_t a, b; | |
190 | a = *(const dev_t*) _a; | |
191 | b = *(const dev_t*) _b; | |
192 | return a < b ? -1 : (a > b ? 1 : 0); | |
193 | } | |
d5099efc MS |
194 | |
195 | const struct hash_ops devt_hash_ops = { | |
196 | .hash = devt_hash_func, | |
197 | .compare = devt_compare_func | |
198 | }; | |
de99c9dc LP |
199 | #endif |
200 | ||
a3b6fafe | 201 | static unsigned bucket_hash(Hashmap *h, const void *p) { |
d5099efc | 202 | return (unsigned) (h->hash_ops->hash(p, h->hash_key) % h->n_buckets); |
9bf3b535 LP |
203 | } |
204 | ||
205 | static void get_hash_key(uint8_t hash_key[HASH_KEY_SIZE], bool reuse_is_ok) { | |
206 | static uint8_t current[HASH_KEY_SIZE]; | |
207 | static bool current_initialized = false; | |
208 | ||
209 | /* Returns a hash function key to use. In order to keep things | |
210 | * fast we will not generate a new key each time we allocate a | |
211 | * new hash table. Instead, we'll just reuse the most recently | |
212 | * generated one, except if we never generated one or when we | |
213 | * are rehashing an entire hash table because we reached a | |
214 | * fill level */ | |
215 | ||
216 | if (!current_initialized || !reuse_is_ok) { | |
217 | random_bytes(current, sizeof(current)); | |
218 | current_initialized = true; | |
219 | } | |
220 | ||
221 | memcpy(hash_key, current, sizeof(current)); | |
a3b6fafe LP |
222 | } |
223 | ||
d5099efc | 224 | Hashmap *hashmap_new(const struct hash_ops *hash_ops) { |
39c2a6f1 | 225 | bool b; |
60918275 | 226 | Hashmap *h; |
39c2a6f1 LP |
227 | size_t size; |
228 | ||
229 | b = is_main_thread(); | |
230 | ||
45fa9e29 | 231 | size = ALIGN(sizeof(Hashmap)) + INITIAL_N_BUCKETS * sizeof(struct hashmap_entry*); |
60918275 | 232 | |
39c2a6f1 | 233 | if (b) { |
3febea3a | 234 | h = allocate_tile(&first_hashmap_pool, &first_hashmap_tile, size, 8); |
39c2a6f1 LP |
235 | if (!h) |
236 | return NULL; | |
237 | ||
29804cc1 | 238 | memzero(h, size); |
39c2a6f1 LP |
239 | } else { |
240 | h = malloc0(size); | |
241 | ||
242 | if (!h) | |
243 | return NULL; | |
244 | } | |
60918275 | 245 | |
d5099efc | 246 | h->hash_ops = hash_ops ? hash_ops : &trivial_hash_ops; |
60918275 | 247 | |
45fa9e29 | 248 | h->n_buckets = INITIAL_N_BUCKETS; |
60918275 LP |
249 | h->n_entries = 0; |
250 | h->iterate_list_head = h->iterate_list_tail = NULL; | |
251 | ||
45fa9e29 LP |
252 | h->buckets = (struct hashmap_entry**) ((uint8_t*) h + ALIGN(sizeof(Hashmap))); |
253 | ||
39c2a6f1 LP |
254 | h->from_pool = b; |
255 | ||
9bf3b535 | 256 | get_hash_key(h->hash_key, true); |
a3b6fafe | 257 | |
60918275 LP |
258 | return h; |
259 | } | |
260 | ||
d5099efc | 261 | int hashmap_ensure_allocated(Hashmap **h, const struct hash_ops *hash_ops) { |
45fa9e29 LP |
262 | Hashmap *q; |
263 | ||
034c6ed7 LP |
264 | assert(h); |
265 | ||
266 | if (*h) | |
267 | return 0; | |
268 | ||
d5099efc | 269 | q = hashmap_new(hash_ops); |
45fa9e29 | 270 | if (!q) |
034c6ed7 LP |
271 | return -ENOMEM; |
272 | ||
45fa9e29 | 273 | *h = q; |
034c6ed7 LP |
274 | return 0; |
275 | } | |
276 | ||
101d8e63 LP |
277 | static void link_entry(Hashmap *h, struct hashmap_entry *e, unsigned hash) { |
278 | assert(h); | |
279 | assert(e); | |
280 | ||
281 | /* Insert into hash table */ | |
45fa9e29 | 282 | e->bucket_next = h->buckets[hash]; |
101d8e63 | 283 | e->bucket_previous = NULL; |
45fa9e29 LP |
284 | if (h->buckets[hash]) |
285 | h->buckets[hash]->bucket_previous = e; | |
286 | h->buckets[hash] = e; | |
101d8e63 LP |
287 | |
288 | /* Insert into iteration list */ | |
289 | e->iterate_previous = h->iterate_list_tail; | |
290 | e->iterate_next = NULL; | |
291 | if (h->iterate_list_tail) { | |
292 | assert(h->iterate_list_head); | |
293 | h->iterate_list_tail->iterate_next = e; | |
294 | } else { | |
295 | assert(!h->iterate_list_head); | |
296 | h->iterate_list_head = e; | |
297 | } | |
298 | h->iterate_list_tail = e; | |
299 | ||
300 | h->n_entries++; | |
301 | assert(h->n_entries >= 1); | |
302 | } | |
303 | ||
304 | static void unlink_entry(Hashmap *h, struct hashmap_entry *e, unsigned hash) { | |
60918275 LP |
305 | assert(h); |
306 | assert(e); | |
307 | ||
308 | /* Remove from iteration list */ | |
309 | if (e->iterate_next) | |
310 | e->iterate_next->iterate_previous = e->iterate_previous; | |
311 | else | |
312 | h->iterate_list_tail = e->iterate_previous; | |
313 | ||
314 | if (e->iterate_previous) | |
315 | e->iterate_previous->iterate_next = e->iterate_next; | |
316 | else | |
317 | h->iterate_list_head = e->iterate_next; | |
318 | ||
319 | /* Remove from hash table bucket list */ | |
320 | if (e->bucket_next) | |
321 | e->bucket_next->bucket_previous = e->bucket_previous; | |
322 | ||
323 | if (e->bucket_previous) | |
324 | e->bucket_previous->bucket_next = e->bucket_next; | |
101d8e63 | 325 | else |
45fa9e29 | 326 | h->buckets[hash] = e->bucket_next; |
60918275 LP |
327 | |
328 | assert(h->n_entries >= 1); | |
329 | h->n_entries--; | |
330 | } | |
331 | ||
101d8e63 LP |
332 | static void remove_entry(Hashmap *h, struct hashmap_entry *e) { |
333 | unsigned hash; | |
334 | ||
335 | assert(h); | |
336 | assert(e); | |
337 | ||
a3b6fafe | 338 | hash = bucket_hash(h, e->key); |
101d8e63 | 339 | unlink_entry(h, e, hash); |
39c2a6f1 LP |
340 | |
341 | if (h->from_pool) | |
342 | deallocate_tile(&first_entry_tile, e); | |
343 | else | |
344 | free(e); | |
101d8e63 LP |
345 | } |
346 | ||
60918275 LP |
347 | void hashmap_free(Hashmap*h) { |
348 | ||
67f3c402 LP |
349 | /* Free the hashmap, but nothing in it */ |
350 | ||
60918275 LP |
351 | if (!h) |
352 | return; | |
353 | ||
11dd41ce | 354 | hashmap_clear(h); |
60918275 | 355 | |
45fa9e29 LP |
356 | if (h->buckets != (struct hashmap_entry**) ((uint8_t*) h + ALIGN(sizeof(Hashmap)))) |
357 | free(h->buckets); | |
358 | ||
39c2a6f1 LP |
359 | if (h->from_pool) |
360 | deallocate_tile(&first_hashmap_tile, h); | |
361 | else | |
362 | free(h); | |
60918275 LP |
363 | } |
364 | ||
449ddb2d | 365 | void hashmap_free_free(Hashmap *h) { |
67f3c402 LP |
366 | |
367 | /* Free the hashmap and all data objects in it, but not the | |
368 | * keys */ | |
369 | ||
61b1477c LP |
370 | if (!h) |
371 | return; | |
372 | ||
9946996c | 373 | hashmap_clear_free(h); |
449ddb2d LP |
374 | hashmap_free(h); |
375 | } | |
376 | ||
fabe5c0e LP |
377 | void hashmap_free_free_free(Hashmap *h) { |
378 | ||
379 | /* Free the hashmap and all data and key objects in it */ | |
380 | ||
381 | if (!h) | |
382 | return; | |
383 | ||
384 | hashmap_clear_free_free(h); | |
385 | hashmap_free(h); | |
386 | } | |
387 | ||
11dd41ce LP |
388 | void hashmap_clear(Hashmap *h) { |
389 | if (!h) | |
390 | return; | |
391 | ||
392 | while (h->iterate_list_head) | |
393 | remove_entry(h, h->iterate_list_head); | |
394 | } | |
395 | ||
9946996c LP |
396 | void hashmap_clear_free(Hashmap *h) { |
397 | void *p; | |
398 | ||
61b1477c LP |
399 | if (!h) |
400 | return; | |
9946996c LP |
401 | |
402 | while ((p = hashmap_steal_first(h))) | |
403 | free(p); | |
404 | } | |
405 | ||
fabe5c0e LP |
406 | void hashmap_clear_free_free(Hashmap *h) { |
407 | if (!h) | |
408 | return; | |
409 | ||
410 | while (h->iterate_list_head) { | |
411 | void *a, *b; | |
412 | ||
413 | a = h->iterate_list_head->value; | |
414 | b = (void*) h->iterate_list_head->key; | |
415 | remove_entry(h, h->iterate_list_head); | |
416 | free(a); | |
417 | free(b); | |
418 | } | |
419 | } | |
420 | ||
60918275 LP |
421 | static struct hashmap_entry *hash_scan(Hashmap *h, unsigned hash, const void *key) { |
422 | struct hashmap_entry *e; | |
423 | assert(h); | |
45fa9e29 | 424 | assert(hash < h->n_buckets); |
60918275 | 425 | |
45fa9e29 | 426 | for (e = h->buckets[hash]; e; e = e->bucket_next) |
d5099efc | 427 | if (h->hash_ops->compare(e->key, key) == 0) |
60918275 LP |
428 | return e; |
429 | ||
430 | return NULL; | |
431 | } | |
432 | ||
45fa9e29 | 433 | static bool resize_buckets(Hashmap *h) { |
45fa9e29 | 434 | struct hashmap_entry **n, *i; |
9bf3b535 LP |
435 | unsigned m; |
436 | uint8_t nkey[HASH_KEY_SIZE]; | |
45fa9e29 LP |
437 | |
438 | assert(h); | |
439 | ||
440 | if (_likely_(h->n_entries*4 < h->n_buckets*3)) | |
441 | return false; | |
442 | ||
443 | /* Increase by four */ | |
444 | m = (h->n_entries+1)*4-1; | |
445 | ||
446 | /* If we hit OOM we simply risk packed hashmaps... */ | |
447 | n = new0(struct hashmap_entry*, m); | |
448 | if (!n) | |
449 | return false; | |
450 | ||
9bf3b535 | 451 | /* Let's use a different randomized hash key for the |
a3b6fafe LP |
452 | * extension, so that people cannot guess what we are using |
453 | * here forever */ | |
9bf3b535 | 454 | get_hash_key(nkey, false); |
a3b6fafe | 455 | |
45fa9e29 | 456 | for (i = h->iterate_list_head; i; i = i->iterate_next) { |
9bf3b535 | 457 | unsigned long old_bucket, new_bucket; |
45fa9e29 | 458 | |
d5099efc | 459 | old_bucket = h->hash_ops->hash(i->key, h->hash_key) % h->n_buckets; |
45fa9e29 LP |
460 | |
461 | /* First, drop from old bucket table */ | |
462 | if (i->bucket_next) | |
463 | i->bucket_next->bucket_previous = i->bucket_previous; | |
464 | ||
465 | if (i->bucket_previous) | |
466 | i->bucket_previous->bucket_next = i->bucket_next; | |
467 | else | |
9bf3b535 | 468 | h->buckets[old_bucket] = i->bucket_next; |
45fa9e29 LP |
469 | |
470 | /* Then, add to new backet table */ | |
d5099efc | 471 | new_bucket = h->hash_ops->hash(i->key, nkey) % m; |
45fa9e29 | 472 | |
9bf3b535 | 473 | i->bucket_next = n[new_bucket]; |
45fa9e29 | 474 | i->bucket_previous = NULL; |
9bf3b535 LP |
475 | if (n[new_bucket]) |
476 | n[new_bucket]->bucket_previous = i; | |
477 | n[new_bucket] = i; | |
45fa9e29 LP |
478 | } |
479 | ||
480 | if (h->buckets != (struct hashmap_entry**) ((uint8_t*) h + ALIGN(sizeof(Hashmap)))) | |
481 | free(h->buckets); | |
482 | ||
483 | h->buckets = n; | |
484 | h->n_buckets = m; | |
9bf3b535 LP |
485 | |
486 | memcpy(h->hash_key, nkey, HASH_KEY_SIZE); | |
45fa9e29 LP |
487 | |
488 | return true; | |
489 | } | |
490 | ||
923041cb MS |
491 | static int __hashmap_put(Hashmap *h, const void *key, void *value, unsigned hash) { |
492 | /* For when we know no such entry exists yet */ | |
60918275 | 493 | |
923041cb | 494 | struct hashmap_entry *e; |
60918275 | 495 | |
45fa9e29 | 496 | if (resize_buckets(h)) |
a3b6fafe | 497 | hash = bucket_hash(h, key); |
45fa9e29 | 498 | |
39c2a6f1 | 499 | if (h->from_pool) |
3febea3a | 500 | e = allocate_tile(&first_entry_pool, &first_entry_tile, sizeof(struct hashmap_entry), 64U); |
39c2a6f1 LP |
501 | else |
502 | e = new(struct hashmap_entry, 1); | |
503 | ||
504 | if (!e) | |
60918275 LP |
505 | return -ENOMEM; |
506 | ||
507 | e->key = key; | |
508 | e->value = value; | |
509 | ||
101d8e63 | 510 | link_entry(h, e, hash); |
60918275 | 511 | |
48507e66 | 512 | return 1; |
60918275 LP |
513 | } |
514 | ||
923041cb MS |
515 | int hashmap_put(Hashmap *h, const void *key, void *value) { |
516 | struct hashmap_entry *e; | |
517 | unsigned hash; | |
518 | ||
519 | assert(h); | |
520 | ||
521 | hash = bucket_hash(h, key); | |
522 | e = hash_scan(h, hash, key); | |
523 | if (e) { | |
524 | if (e->value == value) | |
525 | return 0; | |
526 | return -EEXIST; | |
527 | } | |
528 | ||
529 | return __hashmap_put(h, key, value, hash); | |
530 | } | |
531 | ||
3158713e LP |
532 | int hashmap_replace(Hashmap *h, const void *key, void *value) { |
533 | struct hashmap_entry *e; | |
534 | unsigned hash; | |
535 | ||
536 | assert(h); | |
537 | ||
a3b6fafe | 538 | hash = bucket_hash(h, key); |
d99ae53a LP |
539 | e = hash_scan(h, hash, key); |
540 | if (e) { | |
101d8e63 | 541 | e->key = key; |
3158713e LP |
542 | e->value = value; |
543 | return 0; | |
544 | } | |
545 | ||
923041cb | 546 | return __hashmap_put(h, key, value, hash); |
3158713e LP |
547 | } |
548 | ||
d99ae53a LP |
549 | int hashmap_update(Hashmap *h, const void *key, void *value) { |
550 | struct hashmap_entry *e; | |
551 | unsigned hash; | |
552 | ||
553 | assert(h); | |
554 | ||
a3b6fafe | 555 | hash = bucket_hash(h, key); |
d99ae53a LP |
556 | e = hash_scan(h, hash, key); |
557 | if (!e) | |
558 | return -ENOENT; | |
559 | ||
560 | e->value = value; | |
561 | return 0; | |
562 | } | |
563 | ||
60918275 LP |
564 | void* hashmap_get(Hashmap *h, const void *key) { |
565 | unsigned hash; | |
566 | struct hashmap_entry *e; | |
567 | ||
568 | if (!h) | |
569 | return NULL; | |
570 | ||
a3b6fafe | 571 | hash = bucket_hash(h, key); |
67f3c402 LP |
572 | e = hash_scan(h, hash, key); |
573 | if (!e) | |
60918275 LP |
574 | return NULL; |
575 | ||
576 | return e->value; | |
577 | } | |
578 | ||
d99ae53a LP |
579 | void* hashmap_get2(Hashmap *h, const void *key, void **key2) { |
580 | unsigned hash; | |
581 | struct hashmap_entry *e; | |
582 | ||
583 | if (!h) | |
584 | return NULL; | |
585 | ||
a3b6fafe | 586 | hash = bucket_hash(h, key); |
d99ae53a LP |
587 | e = hash_scan(h, hash, key); |
588 | if (!e) | |
589 | return NULL; | |
590 | ||
591 | if (key2) | |
592 | *key2 = (void*) e->key; | |
593 | ||
594 | return e->value; | |
595 | } | |
596 | ||
96342de6 LN |
597 | bool hashmap_contains(Hashmap *h, const void *key) { |
598 | unsigned hash; | |
96342de6 LN |
599 | |
600 | if (!h) | |
601 | return false; | |
602 | ||
a3b6fafe LP |
603 | hash = bucket_hash(h, key); |
604 | return !!hash_scan(h, hash, key); | |
96342de6 LN |
605 | } |
606 | ||
60918275 LP |
607 | void* hashmap_remove(Hashmap *h, const void *key) { |
608 | struct hashmap_entry *e; | |
609 | unsigned hash; | |
610 | void *data; | |
611 | ||
612 | if (!h) | |
613 | return NULL; | |
614 | ||
a3b6fafe LP |
615 | hash = bucket_hash(h, key); |
616 | e = hash_scan(h, hash, key); | |
617 | if (!e) | |
60918275 LP |
618 | return NULL; |
619 | ||
620 | data = e->value; | |
621 | remove_entry(h, e); | |
622 | ||
623 | return data; | |
624 | } | |
625 | ||
c582a3b3 LP |
626 | void* hashmap_remove2(Hashmap *h, const void *key, void **rkey) { |
627 | struct hashmap_entry *e; | |
628 | unsigned hash; | |
629 | void *data; | |
630 | ||
631 | if (!h) { | |
632 | if (rkey) | |
633 | *rkey = NULL; | |
634 | return NULL; | |
635 | } | |
636 | ||
637 | hash = bucket_hash(h, key); | |
638 | e = hash_scan(h, hash, key); | |
639 | if (!e) { | |
640 | if (rkey) | |
641 | *rkey = NULL; | |
642 | return NULL; | |
643 | } | |
644 | ||
645 | data = e->value; | |
646 | if (rkey) | |
647 | *rkey = (void*) e->key; | |
648 | ||
649 | remove_entry(h, e); | |
650 | ||
651 | return data; | |
652 | } | |
653 | ||
101d8e63 LP |
654 | int hashmap_remove_and_put(Hashmap *h, const void *old_key, const void *new_key, void *value) { |
655 | struct hashmap_entry *e; | |
656 | unsigned old_hash, new_hash; | |
657 | ||
658 | if (!h) | |
659 | return -ENOENT; | |
660 | ||
a3b6fafe LP |
661 | old_hash = bucket_hash(h, old_key); |
662 | e = hash_scan(h, old_hash, old_key); | |
663 | if (!e) | |
101d8e63 LP |
664 | return -ENOENT; |
665 | ||
a3b6fafe | 666 | new_hash = bucket_hash(h, new_key); |
101d8e63 LP |
667 | if (hash_scan(h, new_hash, new_key)) |
668 | return -EEXIST; | |
669 | ||
670 | unlink_entry(h, e, old_hash); | |
671 | ||
672 | e->key = new_key; | |
673 | e->value = value; | |
674 | ||
675 | link_entry(h, e, new_hash); | |
676 | ||
677 | return 0; | |
678 | } | |
679 | ||
8fe914ec LP |
680 | int hashmap_remove_and_replace(Hashmap *h, const void *old_key, const void *new_key, void *value) { |
681 | struct hashmap_entry *e, *k; | |
682 | unsigned old_hash, new_hash; | |
683 | ||
684 | if (!h) | |
685 | return -ENOENT; | |
686 | ||
a3b6fafe LP |
687 | old_hash = bucket_hash(h, old_key); |
688 | e = hash_scan(h, old_hash, old_key); | |
689 | if (!e) | |
8fe914ec LP |
690 | return -ENOENT; |
691 | ||
a3b6fafe LP |
692 | new_hash = bucket_hash(h, new_key); |
693 | k = hash_scan(h, new_hash, new_key); | |
694 | if (k) | |
8fe914ec LP |
695 | if (e != k) |
696 | remove_entry(h, k); | |
697 | ||
698 | unlink_entry(h, e, old_hash); | |
699 | ||
700 | e->key = new_key; | |
701 | e->value = value; | |
702 | ||
703 | link_entry(h, e, new_hash); | |
704 | ||
705 | return 0; | |
706 | } | |
707 | ||
3158713e LP |
708 | void* hashmap_remove_value(Hashmap *h, const void *key, void *value) { |
709 | struct hashmap_entry *e; | |
710 | unsigned hash; | |
711 | ||
712 | if (!h) | |
713 | return NULL; | |
714 | ||
a3b6fafe | 715 | hash = bucket_hash(h, key); |
3158713e | 716 | |
45fa9e29 LP |
717 | e = hash_scan(h, hash, key); |
718 | if (!e) | |
3158713e LP |
719 | return NULL; |
720 | ||
721 | if (e->value != value) | |
722 | return NULL; | |
723 | ||
724 | remove_entry(h, e); | |
725 | ||
726 | return value; | |
727 | } | |
728 | ||
034c6ed7 | 729 | void *hashmap_iterate(Hashmap *h, Iterator *i, const void **key) { |
60918275 LP |
730 | struct hashmap_entry *e; |
731 | ||
034c6ed7 | 732 | assert(i); |
60918275 LP |
733 | |
734 | if (!h) | |
735 | goto at_end; | |
736 | ||
034c6ed7 | 737 | if (*i == ITERATOR_LAST) |
60918275 LP |
738 | goto at_end; |
739 | ||
034c6ed7 | 740 | if (*i == ITERATOR_FIRST && !h->iterate_list_head) |
60918275 LP |
741 | goto at_end; |
742 | ||
034c6ed7 | 743 | e = *i == ITERATOR_FIRST ? h->iterate_list_head : (struct hashmap_entry*) *i; |
60918275 LP |
744 | |
745 | if (e->iterate_next) | |
034c6ed7 | 746 | *i = (Iterator) e->iterate_next; |
60918275 | 747 | else |
034c6ed7 | 748 | *i = ITERATOR_LAST; |
60918275 LP |
749 | |
750 | if (key) | |
751 | *key = e->key; | |
752 | ||
753 | return e->value; | |
754 | ||
755 | at_end: | |
034c6ed7 | 756 | *i = ITERATOR_LAST; |
60918275 LP |
757 | |
758 | if (key) | |
759 | *key = NULL; | |
760 | ||
761 | return NULL; | |
762 | } | |
763 | ||
60918275 LP |
764 | void* hashmap_first(Hashmap *h) { |
765 | ||
766 | if (!h) | |
767 | return NULL; | |
768 | ||
769 | if (!h->iterate_list_head) | |
770 | return NULL; | |
771 | ||
772 | return h->iterate_list_head->value; | |
773 | } | |
774 | ||
2e4a6ff4 LP |
775 | void* hashmap_first_key(Hashmap *h) { |
776 | ||
777 | if (!h) | |
778 | return NULL; | |
779 | ||
780 | if (!h->iterate_list_head) | |
781 | return NULL; | |
782 | ||
783 | return (void*) h->iterate_list_head->key; | |
784 | } | |
785 | ||
60918275 LP |
786 | void* hashmap_steal_first(Hashmap *h) { |
787 | void *data; | |
788 | ||
789 | if (!h) | |
790 | return NULL; | |
791 | ||
792 | if (!h->iterate_list_head) | |
793 | return NULL; | |
794 | ||
795 | data = h->iterate_list_head->value; | |
796 | remove_entry(h, h->iterate_list_head); | |
797 | ||
798 | return data; | |
799 | } | |
800 | ||
22be093f LP |
801 | void* hashmap_steal_first_key(Hashmap *h) { |
802 | void *key; | |
803 | ||
804 | if (!h) | |
805 | return NULL; | |
806 | ||
807 | if (!h->iterate_list_head) | |
808 | return NULL; | |
809 | ||
810 | key = (void*) h->iterate_list_head->key; | |
811 | remove_entry(h, h->iterate_list_head); | |
812 | ||
813 | return key; | |
814 | } | |
815 | ||
60918275 LP |
816 | unsigned hashmap_size(Hashmap *h) { |
817 | ||
818 | if (!h) | |
819 | return 0; | |
820 | ||
821 | return h->n_entries; | |
822 | } | |
823 | ||
45fa9e29 LP |
824 | unsigned hashmap_buckets(Hashmap *h) { |
825 | ||
826 | if (!h) | |
827 | return 0; | |
828 | ||
829 | return h->n_buckets; | |
830 | } | |
831 | ||
60918275 LP |
832 | bool hashmap_isempty(Hashmap *h) { |
833 | ||
834 | if (!h) | |
835 | return true; | |
836 | ||
837 | return h->n_entries == 0; | |
838 | } | |
91cdde8a LP |
839 | |
840 | int hashmap_merge(Hashmap *h, Hashmap *other) { | |
841 | struct hashmap_entry *e; | |
842 | ||
843 | assert(h); | |
844 | ||
845 | if (!other) | |
846 | return 0; | |
847 | ||
848 | for (e = other->iterate_list_head; e; e = e->iterate_next) { | |
849 | int r; | |
850 | ||
a3b6fafe LP |
851 | r = hashmap_put(h, e->key, e->value); |
852 | if (r < 0 && r != -EEXIST) | |
853 | return r; | |
91cdde8a LP |
854 | } |
855 | ||
856 | return 0; | |
857 | } | |
858 | ||
101d8e63 LP |
859 | void hashmap_move(Hashmap *h, Hashmap *other) { |
860 | struct hashmap_entry *e, *n; | |
861 | ||
862 | assert(h); | |
863 | ||
864 | /* The same as hashmap_merge(), but every new item from other | |
865 | * is moved to h. This function is guaranteed to succeed. */ | |
866 | ||
867 | if (!other) | |
868 | return; | |
869 | ||
870 | for (e = other->iterate_list_head; e; e = n) { | |
871 | unsigned h_hash, other_hash; | |
872 | ||
873 | n = e->iterate_next; | |
874 | ||
a3b6fafe | 875 | h_hash = bucket_hash(h, e->key); |
101d8e63 LP |
876 | if (hash_scan(h, h_hash, e->key)) |
877 | continue; | |
878 | ||
a3b6fafe | 879 | other_hash = bucket_hash(other, e->key); |
101d8e63 LP |
880 | unlink_entry(other, e, other_hash); |
881 | link_entry(h, e, h_hash); | |
882 | } | |
883 | } | |
884 | ||
885 | int hashmap_move_one(Hashmap *h, Hashmap *other, const void *key) { | |
886 | unsigned h_hash, other_hash; | |
887 | struct hashmap_entry *e; | |
888 | ||
101d8e63 LP |
889 | assert(h); |
890 | ||
a3b6fafe | 891 | h_hash = bucket_hash(h, key); |
101d8e63 LP |
892 | if (hash_scan(h, h_hash, key)) |
893 | return -EEXIST; | |
894 | ||
bf3d3e2b MS |
895 | if (!other) |
896 | return -ENOENT; | |
897 | ||
a3b6fafe | 898 | other_hash = bucket_hash(other, key); |
45fa9e29 LP |
899 | e = hash_scan(other, other_hash, key); |
900 | if (!e) | |
101d8e63 LP |
901 | return -ENOENT; |
902 | ||
903 | unlink_entry(other, e, other_hash); | |
904 | link_entry(h, e, h_hash); | |
905 | ||
906 | return 0; | |
907 | } | |
908 | ||
91cdde8a LP |
909 | Hashmap *hashmap_copy(Hashmap *h) { |
910 | Hashmap *copy; | |
911 | ||
912 | assert(h); | |
913 | ||
d5099efc | 914 | copy = hashmap_new(h->hash_ops); |
45fa9e29 | 915 | if (!copy) |
91cdde8a LP |
916 | return NULL; |
917 | ||
918 | if (hashmap_merge(copy, h) < 0) { | |
919 | hashmap_free(copy); | |
920 | return NULL; | |
921 | } | |
922 | ||
923 | return copy; | |
924 | } | |
db1413d7 KS |
925 | |
926 | char **hashmap_get_strv(Hashmap *h) { | |
927 | char **sv; | |
928 | Iterator it; | |
729e3769 | 929 | char *item; |
db1413d7 KS |
930 | int n; |
931 | ||
729e3769 LP |
932 | sv = new(char*, h->n_entries+1); |
933 | if (!sv) | |
db1413d7 KS |
934 | return NULL; |
935 | ||
936 | n = 0; | |
729e3769 LP |
937 | HASHMAP_FOREACH(item, h, it) |
938 | sv[n++] = item; | |
db1413d7 KS |
939 | sv[n] = NULL; |
940 | ||
941 | return sv; | |
942 | } | |
3c1668da LP |
943 | |
944 | void *hashmap_next(Hashmap *h, const void *key) { | |
945 | unsigned hash; | |
946 | struct hashmap_entry *e; | |
947 | ||
3c1668da LP |
948 | assert(key); |
949 | ||
950 | if (!h) | |
951 | return NULL; | |
952 | ||
a3b6fafe | 953 | hash = bucket_hash(h, key); |
3c1668da LP |
954 | e = hash_scan(h, hash, key); |
955 | if (!e) | |
956 | return NULL; | |
957 | ||
958 | e = e->iterate_next; | |
959 | if (!e) | |
960 | return NULL; | |
961 | ||
962 | return e->value; | |
963 | } |