chiark / gitweb /
journal: implement generic sharable mmap caching logic
[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
31 #define NBUCKETS 127
32
33 struct hashmap_entry {
34         const void *key;
35         void *value;
36         struct hashmap_entry *bucket_next, *bucket_previous;
37         struct hashmap_entry *iterate_next, *iterate_previous;
38 };
39
40 struct Hashmap {
41         hash_func_t hash_func;
42         compare_func_t compare_func;
43
44         struct hashmap_entry *iterate_list_head, *iterate_list_tail;
45         unsigned n_entries;
46
47         bool from_pool;
48 };
49
50 #define BY_HASH(h) ((struct hashmap_entry**) ((uint8_t*) (h) + ALIGN(sizeof(Hashmap))))
51
52 struct pool {
53         struct pool *next;
54         unsigned n_tiles;
55         unsigned n_used;
56 };
57
58 static struct pool *first_hashmap_pool = NULL;
59 static void *first_hashmap_tile = NULL;
60
61 static struct pool *first_entry_pool = NULL;
62 static void *first_entry_tile = NULL;
63
64 static void* allocate_tile(struct pool **first_pool, void **first_tile, size_t tile_size) {
65         unsigned i;
66
67         if (*first_tile) {
68                 void *r;
69
70                 r = *first_tile;
71                 *first_tile = * (void**) (*first_tile);
72                 return r;
73         }
74
75         if (_unlikely_(!*first_pool) || _unlikely_((*first_pool)->n_used >= (*first_pool)->n_tiles)) {
76                 unsigned n;
77                 size_t size;
78                 struct pool *p;
79
80                 n = *first_pool ? (*first_pool)->n_tiles : 0;
81                 n = MAX(512U, n * 2);
82                 size = PAGE_ALIGN(ALIGN(sizeof(struct pool)) + n*tile_size);
83                 n = (size - ALIGN(sizeof(struct pool))) / tile_size;
84
85                 p = malloc(size);
86                 if (!p)
87                         return NULL;
88
89                 p->next = *first_pool;
90                 p->n_tiles = n;
91                 p->n_used = 0;
92
93                 *first_pool = p;
94         }
95
96         i = (*first_pool)->n_used++;
97
98         return ((uint8_t*) (*first_pool)) + ALIGN(sizeof(struct pool)) + i*tile_size;
99 }
100
101 static void deallocate_tile(void **first_tile, void *p) {
102         * (void**) p = *first_tile;
103         *first_tile = p;
104 }
105
106 #ifndef __OPTIMIZE__
107
108 static void drop_pool(struct pool *p) {
109         while (p) {
110                 struct pool *n;
111                 n = p->next;
112                 free(p);
113                 p = n;
114         }
115 }
116
117 __attribute__((destructor)) static void cleanup_pool(void) {
118         /* Be nice to valgrind */
119
120         drop_pool(first_hashmap_pool);
121         drop_pool(first_entry_pool);
122 }
123
124 #endif
125
126 unsigned string_hash_func(const void *p) {
127         unsigned hash = 5381;
128         const signed char *c;
129
130         /* DJB's hash function */
131
132         for (c = p; *c; c++)
133                 hash = (hash << 5) + hash + (unsigned) *c;
134
135         return hash;
136 }
137
138 int string_compare_func(const void *a, const void *b) {
139         return strcmp(a, b);
140 }
141
142 unsigned trivial_hash_func(const void *p) {
143         return PTR_TO_UINT(p);
144 }
145
146 int trivial_compare_func(const void *a, const void *b) {
147         return a < b ? -1 : (a > b ? 1 : 0);
148 }
149
150 Hashmap *hashmap_new(hash_func_t hash_func, compare_func_t compare_func) {
151         bool b;
152         Hashmap *h;
153         size_t size;
154
155         b = is_main_thread();
156
157         size = ALIGN(sizeof(Hashmap)) + NBUCKETS * sizeof(struct hashmap_entry*);
158
159         if (b) {
160                 h = allocate_tile(&first_hashmap_pool, &first_hashmap_tile, size);
161                 if (!h)
162                         return NULL;
163
164                 memset(h, 0, size);
165         } else {
166                 h = malloc0(size);
167
168                 if (!h)
169                         return NULL;
170         }
171
172         h->hash_func = hash_func ? hash_func : trivial_hash_func;
173         h->compare_func = compare_func ? compare_func : trivial_compare_func;
174
175         h->n_entries = 0;
176         h->iterate_list_head = h->iterate_list_tail = NULL;
177
178         h->from_pool = b;
179
180         return h;
181 }
182
183 int hashmap_ensure_allocated(Hashmap **h, hash_func_t hash_func, compare_func_t compare_func) {
184         assert(h);
185
186         if (*h)
187                 return 0;
188
189         if (!(*h = hashmap_new(hash_func, compare_func)))
190                 return -ENOMEM;
191
192         return 0;
193 }
194
195 static void link_entry(Hashmap *h, struct hashmap_entry *e, unsigned hash) {
196         assert(h);
197         assert(e);
198
199         /* Insert into hash table */
200         e->bucket_next = BY_HASH(h)[hash];
201         e->bucket_previous = NULL;
202         if (BY_HASH(h)[hash])
203                 BY_HASH(h)[hash]->bucket_previous = e;
204         BY_HASH(h)[hash] = e;
205
206         /* Insert into iteration list */
207         e->iterate_previous = h->iterate_list_tail;
208         e->iterate_next = NULL;
209         if (h->iterate_list_tail) {
210                 assert(h->iterate_list_head);
211                 h->iterate_list_tail->iterate_next = e;
212         } else {
213                 assert(!h->iterate_list_head);
214                 h->iterate_list_head = e;
215         }
216         h->iterate_list_tail = e;
217
218         h->n_entries++;
219         assert(h->n_entries >= 1);
220 }
221
222 static void unlink_entry(Hashmap *h, struct hashmap_entry *e, unsigned hash) {
223         assert(h);
224         assert(e);
225
226         /* Remove from iteration list */
227         if (e->iterate_next)
228                 e->iterate_next->iterate_previous = e->iterate_previous;
229         else
230                 h->iterate_list_tail = e->iterate_previous;
231
232         if (e->iterate_previous)
233                 e->iterate_previous->iterate_next = e->iterate_next;
234         else
235                 h->iterate_list_head = e->iterate_next;
236
237         /* Remove from hash table bucket list */
238         if (e->bucket_next)
239                 e->bucket_next->bucket_previous = e->bucket_previous;
240
241         if (e->bucket_previous)
242                 e->bucket_previous->bucket_next = e->bucket_next;
243         else
244                 BY_HASH(h)[hash] = e->bucket_next;
245
246         assert(h->n_entries >= 1);
247         h->n_entries--;
248 }
249
250 static void remove_entry(Hashmap *h, struct hashmap_entry *e) {
251         unsigned hash;
252
253         assert(h);
254         assert(e);
255
256         hash = h->hash_func(e->key) % NBUCKETS;
257
258         unlink_entry(h, e, hash);
259
260         if (h->from_pool)
261                 deallocate_tile(&first_entry_tile, e);
262         else
263                 free(e);
264 }
265
266 void hashmap_free(Hashmap*h) {
267
268         if (!h)
269                 return;
270
271         hashmap_clear(h);
272
273         if (h->from_pool)
274                 deallocate_tile(&first_hashmap_tile, h);
275         else
276                 free(h);
277 }
278
279 void hashmap_free_free(Hashmap *h) {
280         if (!h)
281                 return;
282
283         hashmap_clear_free(h);
284         hashmap_free(h);
285 }
286
287 void hashmap_clear(Hashmap *h) {
288         if (!h)
289                 return;
290
291         while (h->iterate_list_head)
292                 remove_entry(h, h->iterate_list_head);
293 }
294
295 void hashmap_clear_free(Hashmap *h) {
296         void *p;
297
298         if (!h)
299                 return;
300
301         while ((p = hashmap_steal_first(h)))
302                 free(p);
303 }
304
305 static struct hashmap_entry *hash_scan(Hashmap *h, unsigned hash, const void *key) {
306         struct hashmap_entry *e;
307         assert(h);
308         assert(hash < NBUCKETS);
309
310         for (e = BY_HASH(h)[hash]; e; e = e->bucket_next)
311                 if (h->compare_func(e->key, key) == 0)
312                         return e;
313
314         return NULL;
315 }
316
317 int hashmap_put(Hashmap *h, const void *key, void *value) {
318         struct hashmap_entry *e;
319         unsigned hash;
320
321         assert(h);
322
323         hash = h->hash_func(key) % NBUCKETS;
324
325         if ((e = hash_scan(h, hash, key))) {
326
327                 if (e->value == value)
328                         return 0;
329
330                 return -EEXIST;
331         }
332
333         if (h->from_pool)
334                 e = allocate_tile(&first_entry_pool, &first_entry_tile, sizeof(struct hashmap_entry));
335         else
336                 e = new(struct hashmap_entry, 1);
337
338         if (!e)
339                 return -ENOMEM;
340
341         e->key = key;
342         e->value = value;
343
344         link_entry(h, e, hash);
345
346         return 1;
347 }
348
349 int hashmap_replace(Hashmap *h, const void *key, void *value) {
350         struct hashmap_entry *e;
351         unsigned hash;
352
353         assert(h);
354
355         hash = h->hash_func(key) % NBUCKETS;
356
357         if ((e = hash_scan(h, hash, key))) {
358                 e->key = key;
359                 e->value = value;
360                 return 0;
361         }
362
363         return hashmap_put(h, key, value);
364 }
365
366 void* hashmap_get(Hashmap *h, const void *key) {
367         unsigned hash;
368         struct hashmap_entry *e;
369
370         if (!h)
371                 return NULL;
372
373         hash = h->hash_func(key) % NBUCKETS;
374
375         if (!(e = hash_scan(h, hash, key)))
376                 return NULL;
377
378         return e->value;
379 }
380
381 bool hashmap_contains(Hashmap *h, const void *key) {
382         unsigned hash;
383         struct hashmap_entry *e;
384
385         if (!h)
386                 return false;
387
388         hash = h->hash_func(key) % NBUCKETS;
389
390         if (!(e = hash_scan(h, hash, key)))
391                 return false;
392
393         return true;
394 }
395
396 void* hashmap_remove(Hashmap *h, const void *key) {
397         struct hashmap_entry *e;
398         unsigned hash;
399         void *data;
400
401         if (!h)
402                 return NULL;
403
404         hash = h->hash_func(key) % NBUCKETS;
405
406         if (!(e = hash_scan(h, hash, key)))
407                 return NULL;
408
409         data = e->value;
410         remove_entry(h, e);
411
412         return data;
413 }
414
415 int hashmap_remove_and_put(Hashmap *h, const void *old_key, const void *new_key, void *value) {
416         struct hashmap_entry *e;
417         unsigned old_hash, new_hash;
418
419         if (!h)
420                 return -ENOENT;
421
422         old_hash = h->hash_func(old_key) % NBUCKETS;
423         if (!(e = hash_scan(h, old_hash, old_key)))
424                 return -ENOENT;
425
426         new_hash = h->hash_func(new_key) % NBUCKETS;
427         if (hash_scan(h, new_hash, new_key))
428                 return -EEXIST;
429
430         unlink_entry(h, e, old_hash);
431
432         e->key = new_key;
433         e->value = value;
434
435         link_entry(h, e, new_hash);
436
437         return 0;
438 }
439
440 int hashmap_remove_and_replace(Hashmap *h, const void *old_key, const void *new_key, void *value) {
441         struct hashmap_entry *e, *k;
442         unsigned old_hash, new_hash;
443
444         if (!h)
445                 return -ENOENT;
446
447         old_hash = h->hash_func(old_key) % NBUCKETS;
448         if (!(e = hash_scan(h, old_hash, old_key)))
449                 return -ENOENT;
450
451         new_hash = h->hash_func(new_key) % NBUCKETS;
452
453         if ((k = hash_scan(h, new_hash, new_key)))
454                 if (e != k)
455                         remove_entry(h, k);
456
457         unlink_entry(h, e, old_hash);
458
459         e->key = new_key;
460         e->value = value;
461
462         link_entry(h, e, new_hash);
463
464         return 0;
465 }
466
467 void* hashmap_remove_value(Hashmap *h, const void *key, void *value) {
468         struct hashmap_entry *e;
469         unsigned hash;
470
471         if (!h)
472                 return NULL;
473
474         hash = h->hash_func(key) % NBUCKETS;
475
476         if (!(e = hash_scan(h, hash, key)))
477                 return NULL;
478
479         if (e->value != value)
480                 return NULL;
481
482         remove_entry(h, e);
483
484         return value;
485 }
486
487 void *hashmap_iterate(Hashmap *h, Iterator *i, const void **key) {
488         struct hashmap_entry *e;
489
490         assert(i);
491
492         if (!h)
493                 goto at_end;
494
495         if (*i == ITERATOR_LAST)
496                 goto at_end;
497
498         if (*i == ITERATOR_FIRST && !h->iterate_list_head)
499                 goto at_end;
500
501         e = *i == ITERATOR_FIRST ? h->iterate_list_head : (struct hashmap_entry*) *i;
502
503         if (e->iterate_next)
504                 *i = (Iterator) e->iterate_next;
505         else
506                 *i = ITERATOR_LAST;
507
508         if (key)
509                 *key = e->key;
510
511         return e->value;
512
513 at_end:
514         *i = ITERATOR_LAST;
515
516         if (key)
517                 *key = NULL;
518
519         return NULL;
520 }
521
522 void *hashmap_iterate_backwards(Hashmap *h, Iterator *i, const void **key) {
523         struct hashmap_entry *e;
524
525         assert(i);
526
527         if (!h)
528                 goto at_beginning;
529
530         if (*i == ITERATOR_FIRST)
531                 goto at_beginning;
532
533         if (*i == ITERATOR_LAST && !h->iterate_list_tail)
534                 goto at_beginning;
535
536         e = *i == ITERATOR_LAST ? h->iterate_list_tail : (struct hashmap_entry*) *i;
537
538         if (e->iterate_previous)
539                 *i = (Iterator) e->iterate_previous;
540         else
541                 *i = ITERATOR_FIRST;
542
543         if (key)
544                 *key = e->key;
545
546         return e->value;
547
548 at_beginning:
549         *i = ITERATOR_FIRST;
550
551         if (key)
552                 *key = NULL;
553
554         return NULL;
555 }
556
557 void *hashmap_iterate_skip(Hashmap *h, const void *key, Iterator *i) {
558         unsigned hash;
559         struct hashmap_entry *e;
560
561         if (!h)
562                 return NULL;
563
564         hash = h->hash_func(key) % NBUCKETS;
565
566         if (!(e = hash_scan(h, hash, key)))
567                 return NULL;
568
569         *i = (Iterator) e;
570
571         return e->value;
572 }
573
574 void* hashmap_first(Hashmap *h) {
575
576         if (!h)
577                 return NULL;
578
579         if (!h->iterate_list_head)
580                 return NULL;
581
582         return h->iterate_list_head->value;
583 }
584
585 void* hashmap_first_key(Hashmap *h) {
586
587         if (!h)
588                 return NULL;
589
590         if (!h->iterate_list_head)
591                 return NULL;
592
593         return (void*) h->iterate_list_head->key;
594 }
595
596 void* hashmap_last(Hashmap *h) {
597
598         if (!h)
599                 return NULL;
600
601         if (!h->iterate_list_tail)
602                 return NULL;
603
604         return h->iterate_list_tail->value;
605 }
606
607 void* hashmap_steal_first(Hashmap *h) {
608         void *data;
609
610         if (!h)
611                 return NULL;
612
613         if (!h->iterate_list_head)
614                 return NULL;
615
616         data = h->iterate_list_head->value;
617         remove_entry(h, h->iterate_list_head);
618
619         return data;
620 }
621
622 void* hashmap_steal_first_key(Hashmap *h) {
623         void *key;
624
625         if (!h)
626                 return NULL;
627
628         if (!h->iterate_list_head)
629                 return NULL;
630
631         key = (void*) h->iterate_list_head->key;
632         remove_entry(h, h->iterate_list_head);
633
634         return key;
635 }
636
637 unsigned hashmap_size(Hashmap *h) {
638
639         if (!h)
640                 return 0;
641
642         return h->n_entries;
643 }
644
645 bool hashmap_isempty(Hashmap *h) {
646
647         if (!h)
648                 return true;
649
650         return h->n_entries == 0;
651 }
652
653 int hashmap_merge(Hashmap *h, Hashmap *other) {
654         struct hashmap_entry *e;
655
656         assert(h);
657
658         if (!other)
659                 return 0;
660
661         for (e = other->iterate_list_head; e; e = e->iterate_next) {
662                 int r;
663
664                 if ((r = hashmap_put(h, e->key, e->value)) < 0)
665                         if (r != -EEXIST)
666                                 return r;
667         }
668
669         return 0;
670 }
671
672 void hashmap_move(Hashmap *h, Hashmap *other) {
673         struct hashmap_entry *e, *n;
674
675         assert(h);
676
677         /* The same as hashmap_merge(), but every new item from other
678          * is moved to h. This function is guaranteed to succeed. */
679
680         if (!other)
681                 return;
682
683         for (e = other->iterate_list_head; e; e = n) {
684                 unsigned h_hash, other_hash;
685
686                 n = e->iterate_next;
687
688                 h_hash = h->hash_func(e->key) % NBUCKETS;
689
690                 if (hash_scan(h, h_hash, e->key))
691                         continue;
692
693                 other_hash = other->hash_func(e->key) % NBUCKETS;
694
695                 unlink_entry(other, e, other_hash);
696                 link_entry(h, e, h_hash);
697         }
698 }
699
700 int hashmap_move_one(Hashmap *h, Hashmap *other, const void *key) {
701         unsigned h_hash, other_hash;
702         struct hashmap_entry *e;
703
704         if (!other)
705                 return 0;
706
707         assert(h);
708
709         h_hash = h->hash_func(key) % NBUCKETS;
710         if (hash_scan(h, h_hash, key))
711                 return -EEXIST;
712
713         other_hash = other->hash_func(key) % NBUCKETS;
714         if (!(e = hash_scan(other, other_hash, key)))
715                 return -ENOENT;
716
717         unlink_entry(other, e, other_hash);
718         link_entry(h, e, h_hash);
719
720         return 0;
721 }
722
723 Hashmap *hashmap_copy(Hashmap *h) {
724         Hashmap *copy;
725
726         assert(h);
727
728         if (!(copy = hashmap_new(h->hash_func, h->compare_func)))
729                 return NULL;
730
731         if (hashmap_merge(copy, h) < 0) {
732                 hashmap_free(copy);
733                 return NULL;
734         }
735
736         return copy;
737 }
738
739 char **hashmap_get_strv(Hashmap *h) {
740         char **sv;
741         Iterator it;
742         char *item;
743         int n;
744
745         sv = new(char*, h->n_entries+1);
746         if (!sv)
747                 return NULL;
748
749         n = 0;
750         HASHMAP_FOREACH(item, h, it)
751                 sv[n++] = item;
752         sv[n] = NULL;
753
754         return sv;
755 }