[thirdparty/systemd.git] / src / shared / hashmap.c

/*-*- Mode: C; c-basic-offset: 8; indent-tabs-mode: nil -*-*/

/***
  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 Lesser General Public License as published by
  the Free Software Foundation; either version 2.1 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
  Lesser General Public License for more details.

  You should have received a copy of the GNU Lesser General Public License
  along with systemd; If not, see <http://www.gnu.org/licenses/>.
***/

#include <assert.h>
#include <stdlib.h>
#include <string.h>
#include <errno.h>

#include "util.h"
#include "hashmap.h"
#include "macro.h"

#define NBUCKETS 127

struct hashmap_entry {
        const void *key;
        void *value;
        struct hashmap_entry *bucket_next, *bucket_previous;
        struct hashmap_entry *iterate_next, *iterate_previous;
};

struct Hashmap {
        hash_func_t hash_func;
        compare_func_t compare_func;

        struct hashmap_entry *iterate_list_head, *iterate_list_tail;
        unsigned n_entries;

        bool from_pool;
};

#define BY_HASH(h) ((struct hashmap_entry**) ((uint8_t*) (h) + ALIGN(sizeof(Hashmap))))

struct pool {
        struct pool *next;
        unsigned n_tiles;
        unsigned n_used;
};

static struct pool *first_hashmap_pool = NULL;
static void *first_hashmap_tile = NULL;

static struct pool *first_entry_pool = NULL;
static void *first_entry_tile = NULL;

static void* allocate_tile(struct pool **first_pool, void **first_tile, size_t tile_size) {
        unsigned i;

        if (*first_tile) {
                void *r;

                r = *first_tile;
                *first_tile = * (void**) (*first_tile);
                return r;
        }

        if (_unlikely_(!*first_pool) || _unlikely_((*first_pool)->n_used >= (*first_pool)->n_tiles)) {
                unsigned n;
                size_t size;
                struct pool *p;

                n = *first_pool ? (*first_pool)->n_tiles : 0;
                n = MAX(512U, n * 2);
                size = PAGE_ALIGN(ALIGN(sizeof(struct pool)) + n*tile_size);
                n = (size - ALIGN(sizeof(struct pool))) / tile_size;

                p = malloc(size);
                if (!p)
                        return NULL;

                p->next = *first_pool;
                p->n_tiles = n;
                p->n_used = 0;

                *first_pool = p;
        }

        i = (*first_pool)->n_used++;

        return ((uint8_t*) (*first_pool)) + ALIGN(sizeof(struct pool)) + i*tile_size;
}

static void deallocate_tile(void **first_tile, void *p) {
        * (void**) p = *first_tile;
        *first_tile = p;
}

#ifndef __OPTIMIZE__

static void drop_pool(struct pool *p) {
        while (p) {
                struct pool *n;
                n = p->next;
                free(p);
                p = n;
        }
}

__attribute__((destructor)) static void cleanup_pool(void) {
        /* Be nice to valgrind */

        drop_pool(first_hashmap_pool);
        drop_pool(first_entry_pool);
}

#endif

unsigned string_hash_func(const void *p) {
        unsigned hash = 5381;
        const signed char *c;

        /* DJB's hash function */

        for (c = p; *c; c++)
                hash = (hash << 5) + hash + (unsigned) *c;

        return hash;
}

int string_compare_func(const void *a, const void *b) {
        return strcmp(a, b);
}

unsigned trivial_hash_func(const void *p) {
        return PTR_TO_UINT(p);
}

int trivial_compare_func(const void *a, const void *b) {
        return a < b ? -1 : (a > b ? 1 : 0);
}

Hashmap *hashmap_new(hash_func_t hash_func, compare_func_t compare_func) {
        bool b;
        Hashmap *h;
        size_t size;

        b = is_main_thread();

        size = ALIGN(sizeof(Hashmap)) + NBUCKETS * sizeof(struct hashmap_entry*);

        if (b) {
                h = allocate_tile(&first_hashmap_pool, &first_hashmap_tile, size);
                if (!h)
                        return NULL;

                memset(h, 0, size);
        } else {
                h = malloc0(size);

                if (!h)
                        return NULL;
        }

        h->hash_func = hash_func ? hash_func : trivial_hash_func;
        h->compare_func = compare_func ? compare_func : trivial_compare_func;

        h->n_entries = 0;
        h->iterate_list_head = h->iterate_list_tail = NULL;

        h->from_pool = b;

        return h;
}

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);

        /* Remove from iteration list */
        if (e->iterate_next)
                e->iterate_next->iterate_previous = e->iterate_previous;
        else
                h->iterate_list_tail = e->iterate_previous;

        if (e->iterate_previous)
                e->iterate_previous->iterate_next = e->iterate_next;
        else
                h->iterate_list_head = e->iterate_next;

        /* Remove from hash table bucket list */
        if (e->bucket_next)
                e->bucket_next->bucket_previous = e->bucket_previous;

        if (e->bucket_previous)
                e->bucket_previous->bucket_next = e->bucket_next;
        else
                BY_HASH(h)[hash] = e->bucket_next;

        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);

        if (h->from_pool)
                deallocate_tile(&first_entry_tile, e);
        else
                free(e);
}

void hashmap_free(Hashmap*h) {

        /* Free the hashmap, but nothing in it */

        if (!h)
                return;

        hashmap_clear(h);

        if (h->from_pool)
                deallocate_tile(&first_hashmap_tile, h);
        else
                free(h);
}

void hashmap_free_free(Hashmap *h) {

        /* Free the hashmap and all data objects in it, but not the
         * keys */

        if (!h)
                return;

        hashmap_clear_free(h);
        hashmap_free(h);
}

void hashmap_clear(Hashmap *h) {
        if (!h)
                return;

        while (h->iterate_list_head)
                remove_entry(h, h->iterate_list_head);
}

void hashmap_clear_free(Hashmap *h) {
        void *p;

        if (!h)
                return;

        while ((p = hashmap_steal_first(h)))
                free(p);
}

static struct hashmap_entry *hash_scan(Hashmap *h, unsigned hash, const void *key) {
        struct hashmap_entry *e;
        assert(h);
        assert(hash < NBUCKETS);

        for (e = BY_HASH(h)[hash]; e; e = e->bucket_next)
                if (h->compare_func(e->key, key) == 0)
                        return e;

        return NULL;
}

int hashmap_put(Hashmap *h, const void *key, void *value) {
        struct hashmap_entry *e;
        unsigned hash;

        assert(h);

        hash = h->hash_func(key) % NBUCKETS;

        if ((e = hash_scan(h, hash, key))) {

                if (e->value == value)
                        return 0;

                return -EEXIST;
        }

        if (h->from_pool)
                e = allocate_tile(&first_entry_pool, &first_entry_tile, sizeof(struct hashmap_entry));
        else
                e = new(struct hashmap_entry, 1);

        if (!e)
                return -ENOMEM;

        e->key = key;
        e->value = value;

        link_entry(h, e, hash);

        return 1;
}

int hashmap_replace(Hashmap *h, const void *key, void *value) {
        struct hashmap_entry *e;
        unsigned hash;

        assert(h);

        hash = h->hash_func(key) % NBUCKETS;

        if ((e = hash_scan(h, hash, key))) {
                e->key = key;
                e->value = value;
                return 0;
        }

        return hashmap_put(h, key, value);
}

void* hashmap_get(Hashmap *h, const void *key) {
        unsigned hash;
        struct hashmap_entry *e;

        if (!h)
                return NULL;

        hash = h->hash_func(key) % NBUCKETS;
        e = hash_scan(h, hash, key);
        if (!e)
                return NULL;

        return e->value;
}

bool hashmap_contains(Hashmap *h, const void *key) {
        unsigned hash;

        if (!h)
                return false;

        hash = h->hash_func(key) % NBUCKETS;

        if (!hash_scan(h, hash, key))
                return false;

        return true;
}

void* hashmap_remove(Hashmap *h, const void *key) {
        struct hashmap_entry *e;
        unsigned hash;
        void *data;

        if (!h)
                return NULL;

        hash = h->hash_func(key) % NBUCKETS;

        if (!(e = hash_scan(h, hash, key)))
                return NULL;

        data = e->value;
        remove_entry(h, e);

        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;
}

int hashmap_remove_and_replace(Hashmap *h, const void *old_key, const void *new_key, void *value) {
        struct hashmap_entry *e, *k;
        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 ((k = hash_scan(h, new_hash, new_key)))
                if (e != k)
                        remove_entry(h, k);

        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;

        if (!h)
                return NULL;

        hash = h->hash_func(key) % NBUCKETS;

        if (!(e = hash_scan(h, hash, key)))
                return NULL;

        if (e->value != value)
                return NULL;

        remove_entry(h, e);

        return value;
}

void *hashmap_iterate(Hashmap *h, Iterator *i, const void **key) {
        struct hashmap_entry *e;

        assert(i);

        if (!h)
                goto at_end;

        if (*i == ITERATOR_LAST)
                goto at_end;

        if (*i == ITERATOR_FIRST && !h->iterate_list_head)
                goto at_end;

        e = *i == ITERATOR_FIRST ? h->iterate_list_head : (struct hashmap_entry*) *i;

        if (e->iterate_next)
                *i = (Iterator) e->iterate_next;
        else
                *i = ITERATOR_LAST;

        if (key)
                *key = e->key;

        return e->value;

at_end:
        *i = ITERATOR_LAST;

        if (key)
                *key = NULL;

        return NULL;
}

void *hashmap_iterate_backwards(Hashmap *h, Iterator *i, const void **key) {
        struct hashmap_entry *e;

        assert(i);

        if (!h)
                goto at_beginning;

        if (*i == ITERATOR_FIRST)
                goto at_beginning;

        if (*i == ITERATOR_LAST && !h->iterate_list_tail)
                goto at_beginning;

        e = *i == ITERATOR_LAST ? h->iterate_list_tail : (struct hashmap_entry*) *i;

        if (e->iterate_previous)
                *i = (Iterator) e->iterate_previous;
        else
                *i = ITERATOR_FIRST;

        if (key)
                *key = e->key;

        return e->value;

at_beginning:
        *i = ITERATOR_FIRST;

        if (key)
                *key = NULL;

        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)
                return NULL;

        if (!h->iterate_list_head)
                return NULL;

        return h->iterate_list_head->value;
}

void* hashmap_first_key(Hashmap *h) {

        if (!h)
                return NULL;

        if (!h->iterate_list_head)
                return NULL;

        return (void*) h->iterate_list_head->key;
}

void* hashmap_last(Hashmap *h) {

        if (!h)
                return NULL;

        if (!h->iterate_list_tail)
                return NULL;

        return h->iterate_list_tail->value;
}

void* hashmap_steal_first(Hashmap *h) {
        void *data;

        if (!h)
                return NULL;

        if (!h->iterate_list_head)
                return NULL;

        data = h->iterate_list_head->value;
        remove_entry(h, h->iterate_list_head);

        return data;
}

void* hashmap_steal_first_key(Hashmap *h) {
        void *key;

        if (!h)
                return NULL;

        if (!h->iterate_list_head)
                return NULL;

        key = (void*) h->iterate_list_head->key;
        remove_entry(h, h->iterate_list_head);

        return key;
}

unsigned hashmap_size(Hashmap *h) {

        if (!h)
                return 0;

        return h->n_entries;
}

bool hashmap_isempty(Hashmap *h) {

        if (!h)
                return true;

        return h->n_entries == 0;
}

int hashmap_merge(Hashmap *h, Hashmap *other) {
        struct hashmap_entry *e;

        assert(h);

        if (!other)
                return 0;

        for (e = other->iterate_list_head; e; e = e->iterate_next) {
                int r;

                if ((r = hashmap_put(h, e->key, e->value)) < 0)
                        if (r != -EEXIST)
                                return r;
        }

        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;

        assert(h);

        if (!(copy = hashmap_new(h->hash_func, h->compare_func)))
                return NULL;

        if (hashmap_merge(copy, h) < 0) {
                hashmap_free(copy);
                return NULL;
        }

        return copy;
}

char **hashmap_get_strv(Hashmap *h) {
        char **sv;
        Iterator it;
        char *item;
        int n;

        sv = new(char*, h->n_entries+1);
        if (!sv)
                return NULL;

        n = 0;
        HASHMAP_FOREACH(item, h, it)
                sv[n++] = item;
        sv[n] = NULL;

        return sv;
}

void *hashmap_next(Hashmap *h, const void *key) {
        unsigned hash;
        struct hashmap_entry *e;

        assert(h);
        assert(key);

        if (!h)
                return NULL;

        hash = h->hash_func(key) % NBUCKETS;
        e = hash_scan(h, hash, key);
        if (!e)
                return NULL;

        e = e->iterate_next;
        if (!e)
                return NULL;

        return e->value;
}
Commit	Line	Data
d6c9574f	1	/-- Mode: C; c-basic-offset: 8; indent-tabs-mode: nil --/
60918275	2
a7334b09 LP	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
5430f7f2 LP	9	under the terms of the GNU Lesser General Public License as published by
5430f7f2 LP	10	the Free Software Foundation; either version 2.1 of the License, or
a7334b09 LP	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
5430f7f2	16	Lesser General Public License for more details.
a7334b09	17
5430f7f2	18	You should have received a copy of the GNU Lesser General Public License
a7334b09 LP	19	along with systemd; If not, see <http://www.gnu.org/licenses/>.
	20	***/
	21
60918275 LP	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;
60918275 LP	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;
39c2a6f1 LP	46
39c2a6f1 LP	47	bool from_pool;
60918275 LP	48	};
	49
	50	#define BY_HASH(h) ((struct hashmap_entry*) ((uint8_t) (h) + ALIGN(sizeof(Hashmap))))
	51
39c2a6f1 LP	52	struct pool {
	53	struct pool *next;
	54	unsigned n_tiles;
	55	unsigned n_used;
	56	};
	57
6a39419f	58	static struct pool *first_hashmap_pool = NULL;
39c2a6f1 LP	59	static void *first_hashmap_tile = NULL;
39c2a6f1 LP	60
6a39419f	61	static struct pool *first_entry_pool = NULL;
39c2a6f1 LP	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
60918275	126	unsigned string_hash_func(const void *p) {
7dfe96ee LP	127	unsigned hash = 5381;
	128	const signed char *c;
	129
	130	/* DJB's hash function */
60918275 LP	131
60918275 LP	132	for (c = p; *c; c++)
7dfe96ee	133	hash = (hash << 5) + hash + (unsigned) *c;
60918275 LP	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) {
39c2a6f1	151	bool b;
60918275	152	Hashmap *h;
39c2a6f1 LP	153	size_t size;
	154
	155	b = is_main_thread();
	156
	157	size = ALIGN(sizeof(Hashmap)) + NBUCKETS * sizeof(struct hashmap_entry*);
60918275	158
39c2a6f1 LP	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	}
60918275 LP	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
39c2a6f1 LP	178	h->from_pool = b;
39c2a6f1 LP	179
60918275 LP	180	return h;
	181	}
	182
034c6ed7 LP	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
101d8e63 LP	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) {
60918275 LP	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;
101d8e63	243	else
60918275	244	BY_HASH(h)[hash] = e->bucket_next;
60918275 LP	245
	246	assert(h->n_entries >= 1);
	247	h->n_entries--;
	248	}
	249
101d8e63 LP	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);
39c2a6f1 LP	259
	260	if (h->from_pool)
	261	deallocate_tile(&first_entry_tile, e);
	262	else
	263	free(e);
101d8e63 LP	264	}
101d8e63 LP	265
60918275 LP	266	void hashmap_free(Hashmap*h) {
60918275 LP	267
67f3c402 LP	268	/* Free the hashmap, but nothing in it */
67f3c402 LP	269
60918275 LP	270	if (!h)
	271	return;
	272
11dd41ce	273	hashmap_clear(h);
60918275	274
39c2a6f1 LP	275	if (h->from_pool)
	276	deallocate_tile(&first_hashmap_tile, h);
	277	else
	278	free(h);
60918275 LP	279	}
60918275 LP	280
449ddb2d	281	void hashmap_free_free(Hashmap *h) {
67f3c402 LP	282
	283	/* Free the hashmap and all data objects in it, but not the
	284	* keys */
	285
61b1477c LP	286	if (!h)
	287	return;
	288
9946996c	289	hashmap_clear_free(h);
449ddb2d LP	290	hashmap_free(h);
	291	}
	292
11dd41ce LP	293	void hashmap_clear(Hashmap *h) {
	294	if (!h)
	295	return;
	296
	297	while (h->iterate_list_head)
	298	remove_entry(h, h->iterate_list_head);
	299	}
	300
9946996c LP	301	void hashmap_clear_free(Hashmap *h) {
	302	void *p;
	303
61b1477c LP	304	if (!h)
61b1477c LP	305	return;
9946996c LP	306
	307	while ((p = hashmap_steal_first(h)))
	308	free(p);
	309	}
	310
60918275 LP	311	static struct hashmap_entry hash_scan(Hashmap h, unsigned hash, const void *key) {
	312	struct hashmap_entry *e;
	313	assert(h);
	314	assert(hash < NBUCKETS);
	315
	316	for (e = BY_HASH(h)[hash]; e; e = e->bucket_next)
	317	if (h->compare_func(e->key, key) == 0)
	318	return e;
	319
	320	return NULL;
	321	}
	322
	323	int hashmap_put(Hashmap h, const void key, void *value) {
	324	struct hashmap_entry *e;
	325	unsigned hash;
	326
	327	assert(h);
	328
	329	hash = h->hash_func(key) % NBUCKETS;
	330
3158713e LP	331	if ((e = hash_scan(h, hash, key))) {
	332
	333	if (e->value == value)
	334	return 0;
	335
60918275	336	return -EEXIST;
3158713e	337	}
60918275	338
39c2a6f1 LP	339	if (h->from_pool)
	340	e = allocate_tile(&first_entry_pool, &first_entry_tile, sizeof(struct hashmap_entry));
	341	else
	342	e = new(struct hashmap_entry, 1);
	343
	344	if (!e)
60918275 LP	345	return -ENOMEM;
	346
	347	e->key = key;
	348	e->value = value;
	349
101d8e63	350	link_entry(h, e, hash);
60918275	351
48507e66	352	return 1;
60918275 LP	353	}
60918275 LP	354
3158713e LP	355	int hashmap_replace(Hashmap h, const void key, void *value) {
	356	struct hashmap_entry *e;
	357	unsigned hash;
	358
	359	assert(h);
	360
	361	hash = h->hash_func(key) % NBUCKETS;
	362
	363	if ((e = hash_scan(h, hash, key))) {
101d8e63	364	e->key = key;
3158713e LP	365	e->value = value;
	366	return 0;
	367	}
	368
	369	return hashmap_put(h, key, value);
	370	}
	371
60918275 LP	372	void* hashmap_get(Hashmap h, const void key) {
	373	unsigned hash;
	374	struct hashmap_entry *e;
	375
	376	if (!h)
	377	return NULL;
	378
	379	hash = h->hash_func(key) % NBUCKETS;
67f3c402 LP	380	e = hash_scan(h, hash, key);
67f3c402 LP	381	if (!e)
60918275 LP	382	return NULL;
	383
	384	return e->value;
	385	}
	386
96342de6 LN	387	bool hashmap_contains(Hashmap h, const void key) {
96342de6 LN	388	unsigned hash;
96342de6 LN	389
	390	if (!h)
	391	return false;
	392
	393	hash = h->hash_func(key) % NBUCKETS;
	394
9f89986d	395	if (!hash_scan(h, hash, key))
96342de6 LN	396	return false;
	397
	398	return true;
	399	}
	400
60918275 LP	401	void* hashmap_remove(Hashmap h, const void key) {
	402	struct hashmap_entry *e;
	403	unsigned hash;
	404	void *data;
	405
	406	if (!h)
	407	return NULL;
	408
	409	hash = h->hash_func(key) % NBUCKETS;
	410
	411	if (!(e = hash_scan(h, hash, key)))
	412	return NULL;
	413
	414	data = e->value;
	415	remove_entry(h, e);
	416
	417	return data;
	418	}
	419
101d8e63 LP	420	int hashmap_remove_and_put(Hashmap h, const void old_key, const void new_key, void value) {
	421	struct hashmap_entry *e;
	422	unsigned old_hash, new_hash;
	423
	424	if (!h)
	425	return -ENOENT;
	426
	427	old_hash = h->hash_func(old_key) % NBUCKETS;
	428	if (!(e = hash_scan(h, old_hash, old_key)))
	429	return -ENOENT;
	430
	431	new_hash = h->hash_func(new_key) % NBUCKETS;
	432	if (hash_scan(h, new_hash, new_key))
	433	return -EEXIST;
	434
	435	unlink_entry(h, e, old_hash);
	436
	437	e->key = new_key;
	438	e->value = value;
	439
	440	link_entry(h, e, new_hash);
	441
	442	return 0;
	443	}
	444
8fe914ec LP	445	int hashmap_remove_and_replace(Hashmap h, const void old_key, const void new_key, void value) {
	446	struct hashmap_entry e, k;
	447	unsigned old_hash, new_hash;
	448
	449	if (!h)
	450	return -ENOENT;
	451
	452	old_hash = h->hash_func(old_key) % NBUCKETS;
	453	if (!(e = hash_scan(h, old_hash, old_key)))
	454	return -ENOENT;
	455
	456	new_hash = h->hash_func(new_key) % NBUCKETS;
	457
	458	if ((k = hash_scan(h, new_hash, new_key)))
	459	if (e != k)
	460	remove_entry(h, k);
	461
	462	unlink_entry(h, e, old_hash);
	463
	464	e->key = new_key;
	465	e->value = value;
	466
	467	link_entry(h, e, new_hash);
	468
	469	return 0;
	470	}
	471
3158713e LP	472	void* hashmap_remove_value(Hashmap h, const void key, void *value) {
	473	struct hashmap_entry *e;
	474	unsigned hash;
	475
	476	if (!h)
	477	return NULL;
	478
	479	hash = h->hash_func(key) % NBUCKETS;
	480
	481	if (!(e = hash_scan(h, hash, key)))
	482	return NULL;
	483
	484	if (e->value != value)
	485	return NULL;
	486
	487	remove_entry(h, e);
	488
	489	return value;
	490	}
	491
034c6ed7	492	void hashmap_iterate(Hashmap h, Iterator i, const void *key) {
60918275 LP	493	struct hashmap_entry *e;
60918275 LP	494
034c6ed7	495	assert(i);
60918275 LP	496
	497	if (!h)
	498	goto at_end;
	499
034c6ed7	500	if (*i == ITERATOR_LAST)
60918275 LP	501	goto at_end;
60918275 LP	502
034c6ed7	503	if (*i == ITERATOR_FIRST && !h->iterate_list_head)
60918275 LP	504	goto at_end;
60918275 LP	505
034c6ed7	506	e = i == ITERATOR_FIRST ? h->iterate_list_head : (struct hashmap_entry) *i;
60918275 LP	507
60918275 LP	508	if (e->iterate_next)
034c6ed7	509	*i = (Iterator) e->iterate_next;
60918275	510	else
034c6ed7	511	*i = ITERATOR_LAST;
60918275 LP	512
	513	if (key)
	514	*key = e->key;
	515
	516	return e->value;
	517
	518	at_end:
034c6ed7	519	*i = ITERATOR_LAST;
60918275 LP	520
	521	if (key)
	522	*key = NULL;
	523
	524	return NULL;
	525	}
	526
034c6ed7	527	void hashmap_iterate_backwards(Hashmap h, Iterator i, const void *key) {
60918275 LP	528	struct hashmap_entry *e;
60918275 LP	529
034c6ed7	530	assert(i);
60918275 LP	531
	532	if (!h)
	533	goto at_beginning;
	534
034c6ed7	535	if (*i == ITERATOR_FIRST)
60918275 LP	536	goto at_beginning;
60918275 LP	537
034c6ed7	538	if (*i == ITERATOR_LAST && !h->iterate_list_tail)
60918275 LP	539	goto at_beginning;
60918275 LP	540
034c6ed7	541	e = i == ITERATOR_LAST ? h->iterate_list_tail : (struct hashmap_entry) *i;
60918275 LP	542
60918275 LP	543	if (e->iterate_previous)
034c6ed7	544	*i = (Iterator) e->iterate_previous;
60918275	545	else
034c6ed7	546	*i = ITERATOR_FIRST;
60918275 LP	547
	548	if (key)
	549	*key = e->key;
	550
	551	return e->value;
	552
	553	at_beginning:
034c6ed7	554	*i = ITERATOR_FIRST;
60918275 LP	555
	556	if (key)
	557	*key = NULL;
	558
	559	return NULL;
	560	}
	561
034c6ed7 LP	562	void hashmap_iterate_skip(Hashmap h, const void key, Iterator i) {
	563	unsigned hash;
	564	struct hashmap_entry *e;
	565
	566	if (!h)
	567	return NULL;
	568
	569	hash = h->hash_func(key) % NBUCKETS;
	570
	571	if (!(e = hash_scan(h, hash, key)))
	572	return NULL;
	573
	574	*i = (Iterator) e;
	575
	576	return e->value;
	577	}
	578
60918275 LP	579	void* hashmap_first(Hashmap *h) {
	580
	581	if (!h)
	582	return NULL;
	583
	584	if (!h->iterate_list_head)
	585	return NULL;
	586
	587	return h->iterate_list_head->value;
	588	}
	589
2e4a6ff4 LP	590	void* hashmap_first_key(Hashmap *h) {
	591
	592	if (!h)
	593	return NULL;
	594
	595	if (!h->iterate_list_head)
	596	return NULL;
	597
	598	return (void*) h->iterate_list_head->key;
	599	}
	600
60918275 LP	601	void* hashmap_last(Hashmap *h) {
	602
	603	if (!h)
	604	return NULL;
	605
	606	if (!h->iterate_list_tail)
	607	return NULL;
	608
	609	return h->iterate_list_tail->value;
	610	}
	611
	612	void* hashmap_steal_first(Hashmap *h) {
	613	void *data;
	614
	615	if (!h)
	616	return NULL;
	617
	618	if (!h->iterate_list_head)
	619	return NULL;
	620
	621	data = h->iterate_list_head->value;
	622	remove_entry(h, h->iterate_list_head);
	623
	624	return data;
	625	}
	626
22be093f LP	627	void* hashmap_steal_first_key(Hashmap *h) {
	628	void *key;
	629
	630	if (!h)
	631	return NULL;
	632
	633	if (!h->iterate_list_head)
	634	return NULL;
	635
	636	key = (void*) h->iterate_list_head->key;
	637	remove_entry(h, h->iterate_list_head);
	638
	639	return key;
	640	}
	641
60918275 LP	642	unsigned hashmap_size(Hashmap *h) {
	643
	644	if (!h)
	645	return 0;
	646
	647	return h->n_entries;
	648	}
	649
	650	bool hashmap_isempty(Hashmap *h) {
	651
	652	if (!h)
	653	return true;
	654
	655	return h->n_entries == 0;
	656	}
91cdde8a LP	657
	658	int hashmap_merge(Hashmap h, Hashmap other) {
	659	struct hashmap_entry *e;
	660
	661	assert(h);
	662
	663	if (!other)
	664	return 0;
	665
	666	for (e = other->iterate_list_head; e; e = e->iterate_next) {
	667	int r;
	668
	669	if ((r = hashmap_put(h, e->key, e->value)) < 0)
	670	if (r != -EEXIST)
	671	return r;
	672	}
	673
	674	return 0;
	675	}
	676
101d8e63 LP	677	void hashmap_move(Hashmap h, Hashmap other) {
	678	struct hashmap_entry e, n;
	679
	680	assert(h);
	681
	682	/* The same as hashmap_merge(), but every new item from other
	683	* is moved to h. This function is guaranteed to succeed. */
	684
	685	if (!other)
	686	return;
	687
	688	for (e = other->iterate_list_head; e; e = n) {
	689	unsigned h_hash, other_hash;
	690
	691	n = e->iterate_next;
	692
	693	h_hash = h->hash_func(e->key) % NBUCKETS;
	694
	695	if (hash_scan(h, h_hash, e->key))
	696	continue;
	697
	698	other_hash = other->hash_func(e->key) % NBUCKETS;
	699
	700	unlink_entry(other, e, other_hash);
	701	link_entry(h, e, h_hash);
	702	}
	703	}
	704
	705	int hashmap_move_one(Hashmap h, Hashmap other, const void *key) {
	706	unsigned h_hash, other_hash;
	707	struct hashmap_entry *e;
	708
	709	if (!other)
	710	return 0;
	711
	712	assert(h);
	713
	714	h_hash = h->hash_func(key) % NBUCKETS;
	715	if (hash_scan(h, h_hash, key))
	716	return -EEXIST;
	717
	718	other_hash = other->hash_func(key) % NBUCKETS;
	719	if (!(e = hash_scan(other, other_hash, key)))
	720	return -ENOENT;
	721
	722	unlink_entry(other, e, other_hash);
	723	link_entry(h, e, h_hash);
	724
	725	return 0;
	726	}
	727
91cdde8a LP	728	Hashmap hashmap_copy(Hashmap h) {
	729	Hashmap *copy;
	730
	731	assert(h);
	732
	733	if (!(copy = hashmap_new(h->hash_func, h->compare_func)))
	734	return NULL;
	735
	736	if (hashmap_merge(copy, h) < 0) {
	737	hashmap_free(copy);
	738	return NULL;
	739	}
	740
	741	return copy;
	742	}
db1413d7 KS	743
	744	char *hashmap_get_strv(Hashmap h) {
	745	char **sv;
	746	Iterator it;
729e3769	747	char *item;
db1413d7 KS	748	int n;
db1413d7 KS	749
729e3769 LP	750	sv = new(char*, h->n_entries+1);
729e3769 LP	751	if (!sv)
db1413d7 KS	752	return NULL;
	753
	754	n = 0;
729e3769 LP	755	HASHMAP_FOREACH(item, h, it)
729e3769 LP	756	sv[n++] = item;
db1413d7 KS	757	sv[n] = NULL;
	758
	759	return sv;
	760	}
3c1668da LP	761
	762	void hashmap_next(Hashmap h, const void *key) {
	763	unsigned hash;
	764	struct hashmap_entry *e;
	765
	766	assert(h);
	767	assert(key);
	768
	769	if (!h)
	770	return NULL;
	771
	772	hash = h->hash_func(key) % NBUCKETS;
	773	e = hash_scan(h, hash, key);
	774	if (!e)
	775	return NULL;
	776
	777	e = e->iterate_next;
	778	if (!e)
	779	return NULL;
	780
	781	return e->value;
	782	}