[thirdparty/systemd.git] / src / 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 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 <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;
};

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

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

        for (c = p; *c; c++)
                hash = 31 * 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) {
        Hashmap *h;

        if (!(h = malloc0(ALIGN(sizeof(Hashmap)) + NBUCKETS * ALIGN(sizeof(struct hashmap_entry*)))))
                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;

        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);
        free(e);
}

void hashmap_free(Hashmap*h) {

        if (!h)
                return;

        hashmap_clear(h);

        free(h);
}

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

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

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 (!(e = new(struct hashmap_entry, 1)))
                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;

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

        return e->value;
}

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

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;
}
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
	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
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;
	46	};
	47
	48	#define BY_HASH(h) ((struct hashmap_entry*) ((uint8_t) (h) + ALIGN(sizeof(Hashmap))))
	49
	50	unsigned string_hash_func(const void *p) {
	51	unsigned hash = 0;
	52	const char *c;
	53
	54	for (c = p; *c; c++)
	55	hash = 31 * hash + (unsigned) *c;
	56
	57	return hash;
	58	}
	59
	60	int string_compare_func(const void a, const void b) {
	61	return strcmp(a, b);
	62	}
	63
	64	unsigned trivial_hash_func(const void *p) {
	65	return PTR_TO_UINT(p);
	66	}
	67
	68	int trivial_compare_func(const void a, const void b) {
	69	return a < b ? -1 : (a > b ? 1 : 0);
	70	}
	71
	72	Hashmap *hashmap_new(hash_func_t hash_func, compare_func_t compare_func) {
	73	Hashmap *h;
	74
	75	if (!(h = malloc0(ALIGN(sizeof(Hashmap)) + NBUCKETS * ALIGN(sizeof(struct hashmap_entry*)))))
	76	return NULL;
	77
	78	h->hash_func = hash_func ? hash_func : trivial_hash_func;
	79	h->compare_func = compare_func ? compare_func : trivial_compare_func;
	80
	81	h->n_entries = 0;
	82	h->iterate_list_head = h->iterate_list_tail = NULL;
	83
	84	return h;
	85	}
	86
034c6ed7 LP	87	int hashmap_ensure_allocated(Hashmap **h, hash_func_t hash_func, compare_func_t compare_func) {
	88	assert(h);
	89
	90	if (*h)
	91	return 0;
	92
	93	if (!(*h = hashmap_new(hash_func, compare_func)))
	94	return -ENOMEM;
	95
	96	return 0;
	97	}
	98
101d8e63 LP	99	static void link_entry(Hashmap h, struct hashmap_entry e, unsigned hash) {
	100	assert(h);
	101	assert(e);
	102
	103	/* Insert into hash table */
	104	e->bucket_next = BY_HASH(h)[hash];
	105	e->bucket_previous = NULL;
	106	if (BY_HASH(h)[hash])
	107	BY_HASH(h)[hash]->bucket_previous = e;
	108	BY_HASH(h)[hash] = e;
	109
	110	/* Insert into iteration list */
	111	e->iterate_previous = h->iterate_list_tail;
	112	e->iterate_next = NULL;
	113	if (h->iterate_list_tail) {
	114	assert(h->iterate_list_head);
	115	h->iterate_list_tail->iterate_next = e;
	116	} else {
	117	assert(!h->iterate_list_head);
	118	h->iterate_list_head = e;
	119	}
	120	h->iterate_list_tail = e;
	121
	122	h->n_entries++;
	123	assert(h->n_entries >= 1);
	124	}
	125
	126	static void unlink_entry(Hashmap h, struct hashmap_entry e, unsigned hash) {
60918275 LP	127	assert(h);
	128	assert(e);
	129
	130	/* Remove from iteration list */
	131	if (e->iterate_next)
	132	e->iterate_next->iterate_previous = e->iterate_previous;
	133	else
	134	h->iterate_list_tail = e->iterate_previous;
	135
	136	if (e->iterate_previous)
	137	e->iterate_previous->iterate_next = e->iterate_next;
	138	else
	139	h->iterate_list_head = e->iterate_next;
	140
	141	/* Remove from hash table bucket list */
	142	if (e->bucket_next)
	143	e->bucket_next->bucket_previous = e->bucket_previous;
	144
	145	if (e->bucket_previous)
	146	e->bucket_previous->bucket_next = e->bucket_next;
101d8e63	147	else
60918275	148	BY_HASH(h)[hash] = e->bucket_next;
60918275 LP	149
	150	assert(h->n_entries >= 1);
	151	h->n_entries--;
	152	}
	153
101d8e63 LP	154	static void remove_entry(Hashmap h, struct hashmap_entry e) {
	155	unsigned hash;
	156
	157	assert(h);
	158	assert(e);
	159
	160	hash = h->hash_func(e->key) % NBUCKETS;
	161
	162	unlink_entry(h, e, hash);
	163	free(e);
	164	}
	165
60918275 LP	166	void hashmap_free(Hashmap*h) {
	167
	168	if (!h)
	169	return;
	170
11dd41ce	171	hashmap_clear(h);
60918275 LP	172
	173	free(h);
	174	}
	175
11dd41ce LP	176	void hashmap_clear(Hashmap *h) {
	177	if (!h)
	178	return;
	179
	180	while (h->iterate_list_head)
	181	remove_entry(h, h->iterate_list_head);
	182	}
	183
60918275 LP	184	static struct hashmap_entry hash_scan(Hashmap h, unsigned hash, const void *key) {
	185	struct hashmap_entry *e;
	186	assert(h);
	187	assert(hash < NBUCKETS);
	188
	189	for (e = BY_HASH(h)[hash]; e; e = e->bucket_next)
	190	if (h->compare_func(e->key, key) == 0)
	191	return e;
	192
	193	return NULL;
	194	}
	195
	196	int hashmap_put(Hashmap h, const void key, void *value) {
	197	struct hashmap_entry *e;
	198	unsigned hash;
	199
	200	assert(h);
	201
	202	hash = h->hash_func(key) % NBUCKETS;
	203
3158713e LP	204	if ((e = hash_scan(h, hash, key))) {
	205
	206	if (e->value == value)
	207	return 0;
	208
60918275	209	return -EEXIST;
3158713e	210	}
60918275 LP	211
	212	if (!(e = new(struct hashmap_entry, 1)))
	213	return -ENOMEM;
	214
	215	e->key = key;
	216	e->value = value;
	217
101d8e63	218	link_entry(h, e, hash);
60918275	219
48507e66	220	return 1;
60918275 LP	221	}
60918275 LP	222
3158713e LP	223	int hashmap_replace(Hashmap h, const void key, void *value) {
	224	struct hashmap_entry *e;
	225	unsigned hash;
	226
	227	assert(h);
	228
	229	hash = h->hash_func(key) % NBUCKETS;
	230
	231	if ((e = hash_scan(h, hash, key))) {
101d8e63	232	e->key = key;
3158713e LP	233	e->value = value;
	234	return 0;
	235	}
	236
	237	return hashmap_put(h, key, value);
	238	}
	239
60918275 LP	240	void* hashmap_get(Hashmap h, const void key) {
	241	unsigned hash;
	242	struct hashmap_entry *e;
	243
	244	if (!h)
	245	return NULL;
	246
	247	hash = h->hash_func(key) % NBUCKETS;
	248
	249	if (!(e = hash_scan(h, hash, key)))
	250	return NULL;
	251
	252	return e->value;
	253	}
	254
	255	void* hashmap_remove(Hashmap h, const void key) {
	256	struct hashmap_entry *e;
	257	unsigned hash;
	258	void *data;
	259
	260	if (!h)
	261	return NULL;
	262
	263	hash = h->hash_func(key) % NBUCKETS;
	264
	265	if (!(e = hash_scan(h, hash, key)))
	266	return NULL;
	267
	268	data = e->value;
	269	remove_entry(h, e);
	270
	271	return data;
	272	}
	273
101d8e63 LP	274	int hashmap_remove_and_put(Hashmap h, const void old_key, const void new_key, void value) {
	275	struct hashmap_entry *e;
	276	unsigned old_hash, new_hash;
	277
	278	if (!h)
	279	return -ENOENT;
	280
	281	old_hash = h->hash_func(old_key) % NBUCKETS;
	282	if (!(e = hash_scan(h, old_hash, old_key)))
	283	return -ENOENT;
	284
	285	new_hash = h->hash_func(new_key) % NBUCKETS;
	286	if (hash_scan(h, new_hash, new_key))
	287	return -EEXIST;
	288
	289	unlink_entry(h, e, old_hash);
	290
	291	e->key = new_key;
	292	e->value = value;
	293
	294	link_entry(h, e, new_hash);
	295
	296	return 0;
	297	}
	298
8fe914ec LP	299	int hashmap_remove_and_replace(Hashmap h, const void old_key, const void new_key, void value) {
	300	struct hashmap_entry e, k;
	301	unsigned old_hash, new_hash;
	302
	303	if (!h)
	304	return -ENOENT;
	305
	306	old_hash = h->hash_func(old_key) % NBUCKETS;
	307	if (!(e = hash_scan(h, old_hash, old_key)))
	308	return -ENOENT;
	309
	310	new_hash = h->hash_func(new_key) % NBUCKETS;
	311
	312	if ((k = hash_scan(h, new_hash, new_key)))
	313	if (e != k)
	314	remove_entry(h, k);
	315
	316	unlink_entry(h, e, old_hash);
	317
	318	e->key = new_key;
	319	e->value = value;
	320
	321	link_entry(h, e, new_hash);
	322
	323	return 0;
	324	}
	325
3158713e LP	326	void* hashmap_remove_value(Hashmap h, const void key, void *value) {
	327	struct hashmap_entry *e;
	328	unsigned hash;
	329
	330	if (!h)
	331	return NULL;
	332
	333	hash = h->hash_func(key) % NBUCKETS;
	334
	335	if (!(e = hash_scan(h, hash, key)))
	336	return NULL;
	337
	338	if (e->value != value)
	339	return NULL;
	340
	341	remove_entry(h, e);
	342
	343	return value;
	344	}
	345
034c6ed7	346	void hashmap_iterate(Hashmap h, Iterator i, const void *key) {
60918275 LP	347	struct hashmap_entry *e;
60918275 LP	348
034c6ed7	349	assert(i);
60918275 LP	350
	351	if (!h)
	352	goto at_end;
	353
034c6ed7	354	if (*i == ITERATOR_LAST)
60918275 LP	355	goto at_end;
60918275 LP	356
034c6ed7	357	if (*i == ITERATOR_FIRST && !h->iterate_list_head)
60918275 LP	358	goto at_end;
60918275 LP	359
034c6ed7	360	e = i == ITERATOR_FIRST ? h->iterate_list_head : (struct hashmap_entry) *i;
60918275 LP	361
60918275 LP	362	if (e->iterate_next)
034c6ed7	363	*i = (Iterator) e->iterate_next;
60918275	364	else
034c6ed7	365	*i = ITERATOR_LAST;
60918275 LP	366
	367	if (key)
	368	*key = e->key;
	369
	370	return e->value;
	371
	372	at_end:
034c6ed7	373	*i = ITERATOR_LAST;
60918275 LP	374
	375	if (key)
	376	*key = NULL;
	377
	378	return NULL;
	379	}
	380
034c6ed7	381	void hashmap_iterate_backwards(Hashmap h, Iterator i, const void *key) {
60918275 LP	382	struct hashmap_entry *e;
60918275 LP	383
034c6ed7	384	assert(i);
60918275 LP	385
	386	if (!h)
	387	goto at_beginning;
	388
034c6ed7	389	if (*i == ITERATOR_FIRST)
60918275 LP	390	goto at_beginning;
60918275 LP	391
034c6ed7	392	if (*i == ITERATOR_LAST && !h->iterate_list_tail)
60918275 LP	393	goto at_beginning;
60918275 LP	394
034c6ed7	395	e = i == ITERATOR_LAST ? h->iterate_list_tail : (struct hashmap_entry) *i;
60918275 LP	396
60918275 LP	397	if (e->iterate_previous)
034c6ed7	398	*i = (Iterator) e->iterate_previous;
60918275	399	else
034c6ed7	400	*i = ITERATOR_FIRST;
60918275 LP	401
	402	if (key)
	403	*key = e->key;
	404
	405	return e->value;
	406
	407	at_beginning:
034c6ed7	408	*i = ITERATOR_FIRST;
60918275 LP	409
	410	if (key)
	411	*key = NULL;
	412
	413	return NULL;
	414	}
	415
034c6ed7 LP	416	void hashmap_iterate_skip(Hashmap h, const void key, Iterator i) {
	417	unsigned hash;
	418	struct hashmap_entry *e;
	419
	420	if (!h)
	421	return NULL;
	422
	423	hash = h->hash_func(key) % NBUCKETS;
	424
	425	if (!(e = hash_scan(h, hash, key)))
	426	return NULL;
	427
	428	*i = (Iterator) e;
	429
	430	return e->value;
	431	}
	432
60918275 LP	433	void* hashmap_first(Hashmap *h) {
	434
	435	if (!h)
	436	return NULL;
	437
	438	if (!h->iterate_list_head)
	439	return NULL;
	440
	441	return h->iterate_list_head->value;
	442	}
	443
	444	void* hashmap_last(Hashmap *h) {
	445
	446	if (!h)
	447	return NULL;
	448
	449	if (!h->iterate_list_tail)
	450	return NULL;
	451
	452	return h->iterate_list_tail->value;
	453	}
	454
	455	void* hashmap_steal_first(Hashmap *h) {
	456	void *data;
	457
	458	if (!h)
	459	return NULL;
	460
	461	if (!h->iterate_list_head)
	462	return NULL;
	463
	464	data = h->iterate_list_head->value;
	465	remove_entry(h, h->iterate_list_head);
	466
	467	return data;
	468	}
	469
	470	unsigned hashmap_size(Hashmap *h) {
	471
	472	if (!h)
	473	return 0;
	474
	475	return h->n_entries;
	476	}
	477
	478	bool hashmap_isempty(Hashmap *h) {
	479
	480	if (!h)
	481	return true;
	482
	483	return h->n_entries == 0;
	484	}
91cdde8a LP	485
	486	int hashmap_merge(Hashmap h, Hashmap other) {
	487	struct hashmap_entry *e;
	488
	489	assert(h);
	490
	491	if (!other)
	492	return 0;
	493
	494	for (e = other->iterate_list_head; e; e = e->iterate_next) {
	495	int r;
	496
	497	if ((r = hashmap_put(h, e->key, e->value)) < 0)
	498	if (r != -EEXIST)
	499	return r;
	500	}
	501
	502	return 0;
	503	}
	504
101d8e63 LP	505	void hashmap_move(Hashmap h, Hashmap other) {
	506	struct hashmap_entry e, n;
	507
	508	assert(h);
	509
	510	/* The same as hashmap_merge(), but every new item from other
	511	* is moved to h. This function is guaranteed to succeed. */
	512
	513	if (!other)
	514	return;
	515
	516	for (e = other->iterate_list_head; e; e = n) {
	517	unsigned h_hash, other_hash;
	518
	519	n = e->iterate_next;
	520
	521	h_hash = h->hash_func(e->key) % NBUCKETS;
	522
	523	if (hash_scan(h, h_hash, e->key))
	524	continue;
	525
	526	other_hash = other->hash_func(e->key) % NBUCKETS;
	527
	528	unlink_entry(other, e, other_hash);
	529	link_entry(h, e, h_hash);
	530	}
	531	}
	532
	533	int hashmap_move_one(Hashmap h, Hashmap other, const void *key) {
	534	unsigned h_hash, other_hash;
	535	struct hashmap_entry *e;
	536
	537	if (!other)
	538	return 0;
	539
	540	assert(h);
	541
	542	h_hash = h->hash_func(key) % NBUCKETS;
	543	if (hash_scan(h, h_hash, key))
	544	return -EEXIST;
	545
	546	other_hash = other->hash_func(key) % NBUCKETS;
	547	if (!(e = hash_scan(other, other_hash, key)))
	548	return -ENOENT;
	549
	550	unlink_entry(other, e, other_hash);
	551	link_entry(h, e, h_hash);
	552
	553	return 0;
	554	}
	555
91cdde8a LP	556	Hashmap hashmap_copy(Hashmap h) {
	557	Hashmap *copy;
	558
	559	assert(h);
	560
	561	if (!(copy = hashmap_new(h->hash_func, h->compare_func)))
	562	return NULL;
	563
	564	if (hashmap_merge(copy, h) < 0) {
	565	hashmap_free(copy);
	566	return NULL;
	567	}
	568
	569	return copy;
	570	}