hashmap.c revision 729e3769c32242bbba26ea96900be005d52ce438
657a8c206b913d1ee578fd725f0b25eca5b77253Jan Friedel/*-*- Mode: C; c-basic-offset: 8; indent-tabs-mode: nil -*-*/
657a8c206b913d1ee578fd725f0b25eca5b77253Jan Friedel This file is part of systemd.
657a8c206b913d1ee578fd725f0b25eca5b77253Jan Friedel Copyright 2010 Lennart Poettering
657a8c206b913d1ee578fd725f0b25eca5b77253Jan Friedel systemd is free software; you can redistribute it and/or modify it
657a8c206b913d1ee578fd725f0b25eca5b77253Jan Friedel under the terms of the GNU General Public License as published by
657a8c206b913d1ee578fd725f0b25eca5b77253Jan Friedel the Free Software Foundation; either version 2 of the License, or
657a8c206b913d1ee578fd725f0b25eca5b77253Jan Friedel (at your option) any later version.
657a8c206b913d1ee578fd725f0b25eca5b77253Jan Friedel systemd is distributed in the hope that it will be useful, but
657a8c206b913d1ee578fd725f0b25eca5b77253Jan Friedel WITHOUT ANY WARRANTY; without even the implied warranty of
657a8c206b913d1ee578fd725f0b25eca5b77253Jan Friedel MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
657a8c206b913d1ee578fd725f0b25eca5b77253Jan Friedel General Public License for more details.
657a8c206b913d1ee578fd725f0b25eca5b77253Jan Friedel You should have received a copy of the GNU General Public License
657a8c206b913d1ee578fd725f0b25eca5b77253Jan Friedel along with systemd; If not, see <http://www.gnu.org/licenses/>.
657a8c206b913d1ee578fd725f0b25eca5b77253Jan Friedel const void *key;
657a8c206b913d1ee578fd725f0b25eca5b77253Jan Friedel struct hashmap_entry *bucket_next, *bucket_previous;
657a8c206b913d1ee578fd725f0b25eca5b77253Jan Friedel struct hashmap_entry *iterate_next, *iterate_previous;
657a8c206b913d1ee578fd725f0b25eca5b77253Jan Friedel struct hashmap_entry *iterate_list_head, *iterate_list_tail;
657a8c206b913d1ee578fd725f0b25eca5b77253Jan Friedel#define BY_HASH(h) ((struct hashmap_entry**) ((uint8_t*) (h) + ALIGN(sizeof(Hashmap))))
657a8c206b913d1ee578fd725f0b25eca5b77253Jan Friedelunsigned string_hash_func(const void *p) {
657a8c206b913d1ee578fd725f0b25eca5b77253Jan Friedel unsigned hash = 0;
657a8c206b913d1ee578fd725f0b25eca5b77253Jan Friedel const char *c;
657a8c206b913d1ee578fd725f0b25eca5b77253Jan Friedel for (c = p; *c; c++)
657a8c206b913d1ee578fd725f0b25eca5b77253Jan Friedelint string_compare_func(const void *a, const void *b) {
657a8c206b913d1ee578fd725f0b25eca5b77253Jan Friedel return strcmp(a, b);
657a8c206b913d1ee578fd725f0b25eca5b77253Jan Friedelunsigned trivial_hash_func(const void *p) {
657a8c206b913d1ee578fd725f0b25eca5b77253Jan Friedelint trivial_compare_func(const void *a, const void *b) {
657a8c206b913d1ee578fd725f0b25eca5b77253Jan FriedelHashmap *hashmap_new(hash_func_t hash_func, compare_func_t compare_func) {
657a8c206b913d1ee578fd725f0b25eca5b77253Jan Friedel if (!(h = malloc0(ALIGN(sizeof(Hashmap)) + NBUCKETS * ALIGN(sizeof(struct hashmap_entry*)))))
657a8c206b913d1ee578fd725f0b25eca5b77253Jan Friedel h->hash_func = hash_func ? hash_func : trivial_hash_func;
657a8c206b913d1ee578fd725f0b25eca5b77253Jan Friedel h->compare_func = compare_func ? compare_func : trivial_compare_func;
657a8c206b913d1ee578fd725f0b25eca5b77253Jan Friedel h->iterate_list_head = h->iterate_list_tail = NULL;
657a8c206b913d1ee578fd725f0b25eca5b77253Jan Friedelint hashmap_ensure_allocated(Hashmap **h, hash_func_t hash_func, compare_func_t compare_func) {
657a8c206b913d1ee578fd725f0b25eca5b77253Jan Friedel if (!(*h = hashmap_new(hash_func, compare_func)))
657a8c206b913d1ee578fd725f0b25eca5b77253Jan Friedelstatic void link_entry(Hashmap *h, struct hashmap_entry *e, unsigned hash) {
657a8c206b913d1ee578fd725f0b25eca5b77253Jan Friedel /* Insert into hash table */
657a8c206b913d1ee578fd725f0b25eca5b77253Jan Friedel /* Insert into iteration list */
657a8c206b913d1ee578fd725f0b25eca5b77253Jan Friedelstatic void unlink_entry(Hashmap *h, struct hashmap_entry *e, unsigned hash) {
657a8c206b913d1ee578fd725f0b25eca5b77253Jan Friedel /* Remove from iteration list */
657a8c206b913d1ee578fd725f0b25eca5b77253Jan Friedel e->iterate_next->iterate_previous = e->iterate_previous;
657a8c206b913d1ee578fd725f0b25eca5b77253Jan Friedel e->iterate_previous->iterate_next = e->iterate_next;
657a8c206b913d1ee578fd725f0b25eca5b77253Jan Friedel /* Remove from hash table bucket list */
657a8c206b913d1ee578fd725f0b25eca5b77253Jan Friedel e->bucket_next->bucket_previous = e->bucket_previous;
657a8c206b913d1ee578fd725f0b25eca5b77253Jan Friedel e->bucket_previous->bucket_next = e->bucket_next;
657a8c206b913d1ee578fd725f0b25eca5b77253Jan Friedelstatic void remove_entry(Hashmap *h, struct hashmap_entry *e) {
657a8c206b913d1ee578fd725f0b25eca5b77253Jan Friedel while ((p = hashmap_steal_first(h)))
657a8c206b913d1ee578fd725f0b25eca5b77253Jan Friedelstatic struct hashmap_entry *hash_scan(Hashmap *h, unsigned hash, const void *key) {
657a8c206b913d1ee578fd725f0b25eca5b77253Jan Friedel for (e = BY_HASH(h)[hash]; e; e = e->bucket_next)
657a8c206b913d1ee578fd725f0b25eca5b77253Jan Friedelint hashmap_put(Hashmap *h, const void *key, void *value) {
657a8c206b913d1ee578fd725f0b25eca5b77253Jan Friedelint hashmap_replace(Hashmap *h, const void *key, void *value) {
657a8c206b913d1ee578fd725f0b25eca5b77253Jan Friedelvoid* hashmap_remove(Hashmap *h, const void *key) {
657a8c206b913d1ee578fd725f0b25eca5b77253Jan Friedelint hashmap_remove_and_put(Hashmap *h, const void *old_key, const void *new_key, void *value) {
657a8c206b913d1ee578fd725f0b25eca5b77253Jan Friedelint hashmap_remove_and_replace(Hashmap *h, const void *old_key, const void *new_key, void *value) {
657a8c206b913d1ee578fd725f0b25eca5b77253Jan Friedel struct hashmap_entry *e, *k;
657a8c206b913d1ee578fd725f0b25eca5b77253Jan Friedelvoid* hashmap_remove_value(Hashmap *h, const void *key, void *value) {
657a8c206b913d1ee578fd725f0b25eca5b77253Jan Friedelvoid *hashmap_iterate(Hashmap *h, Iterator *i, const void **key) {
657a8c206b913d1ee578fd725f0b25eca5b77253Jan Friedel if (*i == ITERATOR_FIRST && !h->iterate_list_head)
657a8c206b913d1ee578fd725f0b25eca5b77253Jan Friedel e = *i == ITERATOR_FIRST ? h->iterate_list_head : (struct hashmap_entry*) *i;
657a8c206b913d1ee578fd725f0b25eca5b77253Jan Friedelvoid *hashmap_iterate_backwards(Hashmap *h, Iterator *i, const void **key) {
657a8c206b913d1ee578fd725f0b25eca5b77253Jan Friedel if (*i == ITERATOR_LAST && !h->iterate_list_tail)
657a8c206b913d1ee578fd725f0b25eca5b77253Jan Friedel e = *i == ITERATOR_LAST ? h->iterate_list_tail : (struct hashmap_entry*) *i;
657a8c206b913d1ee578fd725f0b25eca5b77253Jan Friedelvoid *hashmap_iterate_skip(Hashmap *h, const void *key, Iterator *i) {
657a8c206b913d1ee578fd725f0b25eca5b77253Jan Friedel return true;
657a8c206b913d1ee578fd725f0b25eca5b77253Jan Friedel return h->n_entries == 0;
657a8c206b913d1ee578fd725f0b25eca5b77253Jan Friedel for (e = other->iterate_list_head; e; e = e->iterate_next) {
657a8c206b913d1ee578fd725f0b25eca5b77253Jan Friedel struct hashmap_entry *e, *n;
657a8c206b913d1ee578fd725f0b25eca5b77253Jan Friedel /* The same as hashmap_merge(), but every new item from other
657a8c206b913d1ee578fd725f0b25eca5b77253Jan Friedel * is moved to h. This function is guaranteed to succeed. */
657a8c206b913d1ee578fd725f0b25eca5b77253Jan Friedel other_hash = other->hash_func(e->key) % NBUCKETS;
657a8c206b913d1ee578fd725f0b25eca5b77253Jan Friedelint hashmap_move_one(Hashmap *h, Hashmap *other, const void *key) {
657a8c206b913d1ee578fd725f0b25eca5b77253Jan Friedel if (!(copy = hashmap_new(h->hash_func, h->compare_func)))