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