1 /*-*- Mode: C; c-basic-offset: 8 -*-*/
4 This file is part of systemd.
6 Copyright 2010 Lennart Poettering
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.
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.
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/>.
37 struct hashmap_entry {
40 struct hashmap_entry *bucket_next, *bucket_previous;
41 struct hashmap_entry *iterate_next, *iterate_previous;
45 hash_func_t hash_func;
46 compare_func_t compare_func;
48 struct hashmap_entry *iterate_list_head, *iterate_list_tail;
52 #define BY_HASH(h) ((struct hashmap_entry**) ((uint8_t*) (h) + ALIGN(sizeof(Hashmap))))
54 unsigned string_hash_func(const void *p) {
59 hash = 31 * hash + (unsigned) *c;
64 int string_compare_func(const void *a, const void *b) {
68 unsigned trivial_hash_func(const void *p) {
69 return PTR_TO_UINT(p);
72 int trivial_compare_func(const void *a, const void *b) {
73 return a < b ? -1 : (a > b ? 1 : 0);
76 Hashmap *hashmap_new(hash_func_t hash_func, compare_func_t compare_func) {
79 if (!(h = malloc0(ALIGN(sizeof(Hashmap)) + NBUCKETS * ALIGN(sizeof(struct hashmap_entry*)))))
82 h->hash_func = hash_func ? hash_func : trivial_hash_func;
83 h->compare_func = compare_func ? compare_func : trivial_compare_func;
86 h->iterate_list_head = h->iterate_list_tail = NULL;
91 int hashmap_ensure_allocated(Hashmap **h, hash_func_t hash_func, compare_func_t compare_func) {
97 if (!(*h = hashmap_new(hash_func, compare_func)))
103 static void remove_entry(Hashmap *h, struct hashmap_entry *e) {
107 /* Remove from iteration list */
109 e->iterate_next->iterate_previous = e->iterate_previous;
111 h->iterate_list_tail = e->iterate_previous;
113 if (e->iterate_previous)
114 e->iterate_previous->iterate_next = e->iterate_next;
116 h->iterate_list_head = e->iterate_next;
118 /* Remove from hash table bucket list */
120 e->bucket_next->bucket_previous = e->bucket_previous;
122 if (e->bucket_previous)
123 e->bucket_previous->bucket_next = e->bucket_next;
125 unsigned hash = h->hash_func(e->key) % NBUCKETS;
126 BY_HASH(h)[hash] = e->bucket_next;
131 assert(h->n_entries >= 1);
135 void hashmap_free(Hashmap*h) {
145 void hashmap_clear(Hashmap *h) {
149 while (h->iterate_list_head)
150 remove_entry(h, h->iterate_list_head);
153 static struct hashmap_entry *hash_scan(Hashmap *h, unsigned hash, const void *key) {
154 struct hashmap_entry *e;
156 assert(hash < NBUCKETS);
158 for (e = BY_HASH(h)[hash]; e; e = e->bucket_next)
159 if (h->compare_func(e->key, key) == 0)
165 int hashmap_put(Hashmap *h, const void *key, void *value) {
166 struct hashmap_entry *e;
171 hash = h->hash_func(key) % NBUCKETS;
173 if ((e = hash_scan(h, hash, key))) {
175 if (e->value == value)
181 if (!(e = new(struct hashmap_entry, 1)))
187 /* Insert into hash table */
188 e->bucket_next = BY_HASH(h)[hash];
189 e->bucket_previous = NULL;
190 if (BY_HASH(h)[hash])
191 BY_HASH(h)[hash]->bucket_previous = e;
192 BY_HASH(h)[hash] = e;
194 /* Insert into iteration list */
195 e->iterate_previous = h->iterate_list_tail;
196 e->iterate_next = NULL;
197 if (h->iterate_list_tail) {
198 assert(h->iterate_list_head);
199 h->iterate_list_tail->iterate_next = e;
201 assert(!h->iterate_list_head);
202 h->iterate_list_head = e;
204 h->iterate_list_tail = e;
207 assert(h->n_entries >= 1);
212 int hashmap_replace(Hashmap *h, const void *key, void *value) {
213 struct hashmap_entry *e;
218 hash = h->hash_func(key) % NBUCKETS;
220 if ((e = hash_scan(h, hash, key))) {
225 return hashmap_put(h, key, value);
228 void* hashmap_get(Hashmap *h, const void *key) {
230 struct hashmap_entry *e;
235 hash = h->hash_func(key) % NBUCKETS;
237 if (!(e = hash_scan(h, hash, key)))
243 void* hashmap_remove(Hashmap *h, const void *key) {
244 struct hashmap_entry *e;
251 hash = h->hash_func(key) % NBUCKETS;
253 if (!(e = hash_scan(h, hash, key)))
262 void* hashmap_remove_value(Hashmap *h, const void *key, void *value) {
263 struct hashmap_entry *e;
269 hash = h->hash_func(key) % NBUCKETS;
271 if (!(e = hash_scan(h, hash, key)))
274 if (e->value != value)
282 void *hashmap_iterate(Hashmap *h, Iterator *i, const void **key) {
283 struct hashmap_entry *e;
290 if (*i == ITERATOR_LAST)
293 if (*i == ITERATOR_FIRST && !h->iterate_list_head)
296 e = *i == ITERATOR_FIRST ? h->iterate_list_head : (struct hashmap_entry*) *i;
299 *i = (Iterator) e->iterate_next;
317 void *hashmap_iterate_backwards(Hashmap *h, Iterator *i, const void **key) {
318 struct hashmap_entry *e;
325 if (*i == ITERATOR_FIRST)
328 if (*i == ITERATOR_LAST && !h->iterate_list_tail)
331 e = *i == ITERATOR_LAST ? h->iterate_list_tail : (struct hashmap_entry*) *i;
333 if (e->iterate_previous)
334 *i = (Iterator) e->iterate_previous;
352 void *hashmap_iterate_skip(Hashmap *h, const void *key, Iterator *i) {
354 struct hashmap_entry *e;
359 hash = h->hash_func(key) % NBUCKETS;
361 if (!(e = hash_scan(h, hash, key)))
369 void* hashmap_first(Hashmap *h) {
374 if (!h->iterate_list_head)
377 return h->iterate_list_head->value;
380 void* hashmap_last(Hashmap *h) {
385 if (!h->iterate_list_tail)
388 return h->iterate_list_tail->value;
391 void* hashmap_steal_first(Hashmap *h) {
397 if (!h->iterate_list_head)
400 data = h->iterate_list_head->value;
401 remove_entry(h, h->iterate_list_head);
406 unsigned hashmap_size(Hashmap *h) {
414 bool hashmap_isempty(Hashmap *h) {
419 return h->n_entries == 0;
422 int hashmap_merge(Hashmap *h, Hashmap *other) {
423 struct hashmap_entry *e;
430 for (e = other->iterate_list_head; e; e = e->iterate_next) {
433 if ((r = hashmap_put(h, e->key, e->value)) < 0)
441 Hashmap *hashmap_copy(Hashmap *h) {
446 if (!(copy = hashmap_new(h->hash_func, h->compare_func)))
449 if (hashmap_merge(copy, h) < 0) {