chiark / gitweb /
journal: add native protocol to journald, and client side API to send journal messages
[elogind.git] / src / 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 General Public License as published by
10   the Free Software Foundation; either version 2 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   General Public License for more details.
17
18   You should have received a copy of the GNU 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 struct pool *first_hashmap_pool = NULL;
59 static void *first_hashmap_tile = NULL;
60
61 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         void *p;
281
282         while ((p = hashmap_steal_first(h)))
283                 free(p);
284
285         hashmap_free(h);
286 }
287
288 void hashmap_clear(Hashmap *h) {
289         if (!h)
290                 return;
291
292         while (h->iterate_list_head)
293                 remove_entry(h, h->iterate_list_head);
294 }
295
296 static struct hashmap_entry *hash_scan(Hashmap *h, unsigned hash, const void *key) {
297         struct hashmap_entry *e;
298         assert(h);
299         assert(hash < NBUCKETS);
300
301         for (e = BY_HASH(h)[hash]; e; e = e->bucket_next)
302                 if (h->compare_func(e->key, key) == 0)
303                         return e;
304
305         return NULL;
306 }
307
308 int hashmap_put(Hashmap *h, const void *key, void *value) {
309         struct hashmap_entry *e;
310         unsigned hash;
311
312         assert(h);
313
314         hash = h->hash_func(key) % NBUCKETS;
315
316         if ((e = hash_scan(h, hash, key))) {
317
318                 if (e->value == value)
319                         return 0;
320
321                 return -EEXIST;
322         }
323
324         if (h->from_pool)
325                 e = allocate_tile(&first_entry_pool, &first_entry_tile, sizeof(struct hashmap_entry));
326         else
327                 e = new(struct hashmap_entry, 1);
328
329         if (!e)
330                 return -ENOMEM;
331
332         e->key = key;
333         e->value = value;
334
335         link_entry(h, e, hash);
336
337         return 1;
338 }
339
340 int hashmap_replace(Hashmap *h, const void *key, void *value) {
341         struct hashmap_entry *e;
342         unsigned hash;
343
344         assert(h);
345
346         hash = h->hash_func(key) % NBUCKETS;
347
348         if ((e = hash_scan(h, hash, key))) {
349                 e->key = key;
350                 e->value = value;
351                 return 0;
352         }
353
354         return hashmap_put(h, key, value);
355 }
356
357 void* hashmap_get(Hashmap *h, const void *key) {
358         unsigned hash;
359         struct hashmap_entry *e;
360
361         if (!h)
362                 return NULL;
363
364         hash = h->hash_func(key) % NBUCKETS;
365
366         if (!(e = hash_scan(h, hash, key)))
367                 return NULL;
368
369         return e->value;
370 }
371
372 void* hashmap_remove(Hashmap *h, const void *key) {
373         struct hashmap_entry *e;
374         unsigned hash;
375         void *data;
376
377         if (!h)
378                 return NULL;
379
380         hash = h->hash_func(key) % NBUCKETS;
381
382         if (!(e = hash_scan(h, hash, key)))
383                 return NULL;
384
385         data = e->value;
386         remove_entry(h, e);
387
388         return data;
389 }
390
391 int hashmap_remove_and_put(Hashmap *h, const void *old_key, const void *new_key, void *value) {
392         struct hashmap_entry *e;
393         unsigned old_hash, new_hash;
394
395         if (!h)
396                 return -ENOENT;
397
398         old_hash = h->hash_func(old_key) % NBUCKETS;
399         if (!(e = hash_scan(h, old_hash, old_key)))
400                 return -ENOENT;
401
402         new_hash = h->hash_func(new_key) % NBUCKETS;
403         if (hash_scan(h, new_hash, new_key))
404                 return -EEXIST;
405
406         unlink_entry(h, e, old_hash);
407
408         e->key = new_key;
409         e->value = value;
410
411         link_entry(h, e, new_hash);
412
413         return 0;
414 }
415
416 int hashmap_remove_and_replace(Hashmap *h, const void *old_key, const void *new_key, void *value) {
417         struct hashmap_entry *e, *k;
418         unsigned old_hash, new_hash;
419
420         if (!h)
421                 return -ENOENT;
422
423         old_hash = h->hash_func(old_key) % NBUCKETS;
424         if (!(e = hash_scan(h, old_hash, old_key)))
425                 return -ENOENT;
426
427         new_hash = h->hash_func(new_key) % NBUCKETS;
428
429         if ((k = hash_scan(h, new_hash, new_key)))
430                 if (e != k)
431                         remove_entry(h, k);
432
433         unlink_entry(h, e, old_hash);
434
435         e->key = new_key;
436         e->value = value;
437
438         link_entry(h, e, new_hash);
439
440         return 0;
441 }
442
443 void* hashmap_remove_value(Hashmap *h, const void *key, void *value) {
444         struct hashmap_entry *e;
445         unsigned hash;
446
447         if (!h)
448                 return NULL;
449
450         hash = h->hash_func(key) % NBUCKETS;
451
452         if (!(e = hash_scan(h, hash, key)))
453                 return NULL;
454
455         if (e->value != value)
456                 return NULL;
457
458         remove_entry(h, e);
459
460         return value;
461 }
462
463 void *hashmap_iterate(Hashmap *h, Iterator *i, const void **key) {
464         struct hashmap_entry *e;
465
466         assert(i);
467
468         if (!h)
469                 goto at_end;
470
471         if (*i == ITERATOR_LAST)
472                 goto at_end;
473
474         if (*i == ITERATOR_FIRST && !h->iterate_list_head)
475                 goto at_end;
476
477         e = *i == ITERATOR_FIRST ? h->iterate_list_head : (struct hashmap_entry*) *i;
478
479         if (e->iterate_next)
480                 *i = (Iterator) e->iterate_next;
481         else
482                 *i = ITERATOR_LAST;
483
484         if (key)
485                 *key = e->key;
486
487         return e->value;
488
489 at_end:
490         *i = ITERATOR_LAST;
491
492         if (key)
493                 *key = NULL;
494
495         return NULL;
496 }
497
498 void *hashmap_iterate_backwards(Hashmap *h, Iterator *i, const void **key) {
499         struct hashmap_entry *e;
500
501         assert(i);
502
503         if (!h)
504                 goto at_beginning;
505
506         if (*i == ITERATOR_FIRST)
507                 goto at_beginning;
508
509         if (*i == ITERATOR_LAST && !h->iterate_list_tail)
510                 goto at_beginning;
511
512         e = *i == ITERATOR_LAST ? h->iterate_list_tail : (struct hashmap_entry*) *i;
513
514         if (e->iterate_previous)
515                 *i = (Iterator) e->iterate_previous;
516         else
517                 *i = ITERATOR_FIRST;
518
519         if (key)
520                 *key = e->key;
521
522         return e->value;
523
524 at_beginning:
525         *i = ITERATOR_FIRST;
526
527         if (key)
528                 *key = NULL;
529
530         return NULL;
531 }
532
533 void *hashmap_iterate_skip(Hashmap *h, const void *key, Iterator *i) {
534         unsigned hash;
535         struct hashmap_entry *e;
536
537         if (!h)
538                 return NULL;
539
540         hash = h->hash_func(key) % NBUCKETS;
541
542         if (!(e = hash_scan(h, hash, key)))
543                 return NULL;
544
545         *i = (Iterator) e;
546
547         return e->value;
548 }
549
550 void* hashmap_first(Hashmap *h) {
551
552         if (!h)
553                 return NULL;
554
555         if (!h->iterate_list_head)
556                 return NULL;
557
558         return h->iterate_list_head->value;
559 }
560
561 void* hashmap_last(Hashmap *h) {
562
563         if (!h)
564                 return NULL;
565
566         if (!h->iterate_list_tail)
567                 return NULL;
568
569         return h->iterate_list_tail->value;
570 }
571
572 void* hashmap_steal_first(Hashmap *h) {
573         void *data;
574
575         if (!h)
576                 return NULL;
577
578         if (!h->iterate_list_head)
579                 return NULL;
580
581         data = h->iterate_list_head->value;
582         remove_entry(h, h->iterate_list_head);
583
584         return data;
585 }
586
587 void* hashmap_steal_first_key(Hashmap *h) {
588         void *key;
589
590         if (!h)
591                 return NULL;
592
593         if (!h->iterate_list_head)
594                 return NULL;
595
596         key = (void*) h->iterate_list_head->key;
597         remove_entry(h, h->iterate_list_head);
598
599         return key;
600 }
601
602 unsigned hashmap_size(Hashmap *h) {
603
604         if (!h)
605                 return 0;
606
607         return h->n_entries;
608 }
609
610 bool hashmap_isempty(Hashmap *h) {
611
612         if (!h)
613                 return true;
614
615         return h->n_entries == 0;
616 }
617
618 int hashmap_merge(Hashmap *h, Hashmap *other) {
619         struct hashmap_entry *e;
620
621         assert(h);
622
623         if (!other)
624                 return 0;
625
626         for (e = other->iterate_list_head; e; e = e->iterate_next) {
627                 int r;
628
629                 if ((r = hashmap_put(h, e->key, e->value)) < 0)
630                         if (r != -EEXIST)
631                                 return r;
632         }
633
634         return 0;
635 }
636
637 void hashmap_move(Hashmap *h, Hashmap *other) {
638         struct hashmap_entry *e, *n;
639
640         assert(h);
641
642         /* The same as hashmap_merge(), but every new item from other
643          * is moved to h. This function is guaranteed to succeed. */
644
645         if (!other)
646                 return;
647
648         for (e = other->iterate_list_head; e; e = n) {
649                 unsigned h_hash, other_hash;
650
651                 n = e->iterate_next;
652
653                 h_hash = h->hash_func(e->key) % NBUCKETS;
654
655                 if (hash_scan(h, h_hash, e->key))
656                         continue;
657
658                 other_hash = other->hash_func(e->key) % NBUCKETS;
659
660                 unlink_entry(other, e, other_hash);
661                 link_entry(h, e, h_hash);
662         }
663 }
664
665 int hashmap_move_one(Hashmap *h, Hashmap *other, const void *key) {
666         unsigned h_hash, other_hash;
667         struct hashmap_entry *e;
668
669         if (!other)
670                 return 0;
671
672         assert(h);
673
674         h_hash = h->hash_func(key) % NBUCKETS;
675         if (hash_scan(h, h_hash, key))
676                 return -EEXIST;
677
678         other_hash = other->hash_func(key) % NBUCKETS;
679         if (!(e = hash_scan(other, other_hash, key)))
680                 return -ENOENT;
681
682         unlink_entry(other, e, other_hash);
683         link_entry(h, e, h_hash);
684
685         return 0;
686 }
687
688 Hashmap *hashmap_copy(Hashmap *h) {
689         Hashmap *copy;
690
691         assert(h);
692
693         if (!(copy = hashmap_new(h->hash_func, h->compare_func)))
694                 return NULL;
695
696         if (hashmap_merge(copy, h) < 0) {
697                 hashmap_free(copy);
698                 return NULL;
699         }
700
701         return copy;
702 }
703
704 char **hashmap_get_strv(Hashmap *h) {
705         char **sv;
706         Iterator it;
707         char *item;
708         int n;
709
710         sv = new(char*, h->n_entries+1);
711         if (!sv)
712                 return NULL;
713
714         n = 0;
715         HASHMAP_FOREACH(item, h, it)
716                 sv[n++] = item;
717         sv[n] = NULL;
718
719         return sv;
720 }