X-Git-Url: http://www.chiark.greenend.org.uk/ucgi/~ianmdlvl/git?p=elogind.git;a=blobdiff_plain;f=hashmap.c;h=5a993b6e4761a36ba410c1f9b1cbba7a5de95a58;hp=a81bcc422ec219fea5c1d0d034c1c2856d112da7;hb=bab45044482dc012331c768c08d78a2d006485ad;hpb=3158713e0094fd32f58ee80c50ff54210c2dc411 diff --git a/hashmap.c b/hashmap.c index a81bcc422..5a993b6e4 100644 --- a/hashmap.c +++ b/hashmap.c @@ -1,8 +1,23 @@ /*-*- Mode: C; c-basic-offset: 8 -*-*/ -#ifdef HAVE_CONFIG_H -#include -#endif +/*** + This file is part of systemd. + + Copyright 2010 Lennart Poettering + + systemd is free software; you can redistribute it and/or modify it + under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 2 of the License, or + (at your option) any later version. + + systemd is distributed in the hope that it will be useful, but + WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + General Public License for more details. + + You should have received a copy of the GNU General Public License + along with systemd; If not, see . +***/ #include #include @@ -69,7 +84,46 @@ Hashmap *hashmap_new(hash_func_t hash_func, compare_func_t compare_func) { return h; } -static void remove_entry(Hashmap *h, struct hashmap_entry *e) { +int hashmap_ensure_allocated(Hashmap **h, hash_func_t hash_func, compare_func_t compare_func) { + assert(h); + + if (*h) + return 0; + + if (!(*h = hashmap_new(hash_func, compare_func))) + return -ENOMEM; + + return 0; +} + +static void link_entry(Hashmap *h, struct hashmap_entry *e, unsigned hash) { + assert(h); + assert(e); + + /* Insert into hash table */ + e->bucket_next = BY_HASH(h)[hash]; + e->bucket_previous = NULL; + if (BY_HASH(h)[hash]) + BY_HASH(h)[hash]->bucket_previous = e; + BY_HASH(h)[hash] = e; + + /* Insert into iteration list */ + e->iterate_previous = h->iterate_list_tail; + e->iterate_next = NULL; + if (h->iterate_list_tail) { + assert(h->iterate_list_head); + h->iterate_list_tail->iterate_next = e; + } else { + assert(!h->iterate_list_head); + h->iterate_list_head = e; + } + h->iterate_list_tail = e; + + h->n_entries++; + assert(h->n_entries >= 1); +} + +static void unlink_entry(Hashmap *h, struct hashmap_entry *e, unsigned hash) { assert(h); assert(e); @@ -90,17 +144,25 @@ static void remove_entry(Hashmap *h, struct hashmap_entry *e) { if (e->bucket_previous) e->bucket_previous->bucket_next = e->bucket_next; - else { - unsigned hash = h->hash_func(e->key) % NBUCKETS; + else BY_HASH(h)[hash] = e->bucket_next; - } - - free(e); assert(h->n_entries >= 1); h->n_entries--; } +static void remove_entry(Hashmap *h, struct hashmap_entry *e) { + unsigned hash; + + assert(h); + assert(e); + + hash = h->hash_func(e->key) % NBUCKETS; + + unlink_entry(h, e, hash); + free(e); +} + void hashmap_free(Hashmap*h) { if (!h) @@ -153,29 +215,9 @@ int hashmap_put(Hashmap *h, const void *key, void *value) { e->key = key; e->value = value; - /* Insert into hash table */ - e->bucket_next = BY_HASH(h)[hash]; - e->bucket_previous = NULL; - if (BY_HASH(h)[hash]) - BY_HASH(h)[hash]->bucket_previous = e; - BY_HASH(h)[hash] = e; - - /* Insert into iteration list */ - e->iterate_previous = h->iterate_list_tail; - e->iterate_next = NULL; - if (h->iterate_list_tail) { - assert(h->iterate_list_head); - h->iterate_list_tail->iterate_next = e; - } else { - assert(!h->iterate_list_head); - h->iterate_list_head = e; - } - h->iterate_list_tail = e; - - h->n_entries++; - assert(h->n_entries >= 1); + link_entry(h, e, hash); - return 0; + return 1; } int hashmap_replace(Hashmap *h, const void *key, void *value) { @@ -187,6 +229,7 @@ int hashmap_replace(Hashmap *h, const void *key, void *value) { hash = h->hash_func(key) % NBUCKETS; if ((e = hash_scan(h, hash, key))) { + e->key = key; e->value = value; return 0; } @@ -228,6 +271,31 @@ void* hashmap_remove(Hashmap *h, const void *key) { return data; } +int hashmap_remove_and_put(Hashmap *h, const void *old_key, const void *new_key, void *value) { + struct hashmap_entry *e; + unsigned old_hash, new_hash; + + if (!h) + return -ENOENT; + + old_hash = h->hash_func(old_key) % NBUCKETS; + if (!(e = hash_scan(h, old_hash, old_key))) + return -ENOENT; + + new_hash = h->hash_func(new_key) % NBUCKETS; + if (hash_scan(h, new_hash, new_key)) + return -EEXIST; + + unlink_entry(h, e, old_hash); + + e->key = new_key; + e->value = value; + + link_entry(h, e, new_hash); + + return 0; +} + void* hashmap_remove_value(Hashmap *h, const void *key, void *value) { struct hashmap_entry *e; unsigned hash; @@ -248,26 +316,26 @@ void* hashmap_remove_value(Hashmap *h, const void *key, void *value) { return value; } -void *hashmap_iterate(Hashmap *h, void **state, const void **key) { +void *hashmap_iterate(Hashmap *h, Iterator *i, const void **key) { struct hashmap_entry *e; - assert(state); + assert(i); if (!h) goto at_end; - if (*state == (void*) -1) + if (*i == ITERATOR_LAST) goto at_end; - if (!*state && !h->iterate_list_head) + if (*i == ITERATOR_FIRST && !h->iterate_list_head) goto at_end; - e = *state ? *state : h->iterate_list_head; + e = *i == ITERATOR_FIRST ? h->iterate_list_head : (struct hashmap_entry*) *i; if (e->iterate_next) - *state = e->iterate_next; + *i = (Iterator) e->iterate_next; else - *state = (void*) -1; + *i = ITERATOR_LAST; if (key) *key = e->key; @@ -275,7 +343,7 @@ void *hashmap_iterate(Hashmap *h, void **state, const void **key) { return e->value; at_end: - *state = (void *) -1; + *i = ITERATOR_LAST; if (key) *key = NULL; @@ -283,26 +351,26 @@ at_end: return NULL; } -void *hashmap_iterate_backwards(Hashmap *h, void **state, const void **key) { +void *hashmap_iterate_backwards(Hashmap *h, Iterator *i, const void **key) { struct hashmap_entry *e; - assert(state); + assert(i); if (!h) goto at_beginning; - if (*state == (void*) -1) + if (*i == ITERATOR_FIRST) goto at_beginning; - if (!*state && !h->iterate_list_tail) + if (*i == ITERATOR_LAST && !h->iterate_list_tail) goto at_beginning; - e = *state ? *state : h->iterate_list_tail; + e = *i == ITERATOR_LAST ? h->iterate_list_tail : (struct hashmap_entry*) *i; if (e->iterate_previous) - *state = e->iterate_previous; + *i = (Iterator) e->iterate_previous; else - *state = (void*) -1; + *i = ITERATOR_FIRST; if (key) *key = e->key; @@ -310,7 +378,7 @@ void *hashmap_iterate_backwards(Hashmap *h, void **state, const void **key) { return e->value; at_beginning: - *state = (void *) -1; + *i = ITERATOR_FIRST; if (key) *key = NULL; @@ -318,6 +386,23 @@ at_beginning: return NULL; } +void *hashmap_iterate_skip(Hashmap *h, const void *key, Iterator *i) { + unsigned hash; + struct hashmap_entry *e; + + if (!h) + return NULL; + + hash = h->hash_func(key) % NBUCKETS; + + if (!(e = hash_scan(h, hash, key))) + return NULL; + + *i = (Iterator) e; + + return e->value; +} + void* hashmap_first(Hashmap *h) { if (!h) @@ -390,6 +475,57 @@ int hashmap_merge(Hashmap *h, Hashmap *other) { return 0; } +void hashmap_move(Hashmap *h, Hashmap *other) { + struct hashmap_entry *e, *n; + + assert(h); + + /* The same as hashmap_merge(), but every new item from other + * is moved to h. This function is guaranteed to succeed. */ + + if (!other) + return; + + for (e = other->iterate_list_head; e; e = n) { + unsigned h_hash, other_hash; + + n = e->iterate_next; + + h_hash = h->hash_func(e->key) % NBUCKETS; + + if (hash_scan(h, h_hash, e->key)) + continue; + + other_hash = other->hash_func(e->key) % NBUCKETS; + + unlink_entry(other, e, other_hash); + link_entry(h, e, h_hash); + } +} + +int hashmap_move_one(Hashmap *h, Hashmap *other, const void *key) { + unsigned h_hash, other_hash; + struct hashmap_entry *e; + + if (!other) + return 0; + + assert(h); + + h_hash = h->hash_func(key) % NBUCKETS; + if (hash_scan(h, h_hash, key)) + return -EEXIST; + + other_hash = other->hash_func(key) % NBUCKETS; + if (!(e = hash_scan(other, other_hash, key))) + return -ENOENT; + + unlink_entry(other, e, other_hash); + link_entry(h, e, h_hash); + + return 0; +} + Hashmap *hashmap_copy(Hashmap *h) { Hashmap *copy;