[thirdparty/systemd.git] / hashmap.c

/*-*- Mode: C; c-basic-offset: 8 -*-*/

/***
  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/>.
***/

#ifdef HAVE_CONFIG_H
#include <config.h>
#endif

#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 remove_entry(Hashmap *h, struct hashmap_entry *e) {
        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 {
                unsigned hash = h->hash_func(e->key) % NBUCKETS;
                BY_HASH(h)[hash] = e->bucket_next;
        }

        free(e);

        assert(h->n_entries >= 1);
        h->n_entries--;
}

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;

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

        return 0;
}

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

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

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
60918275 LP	1	/-- Mode: C; c-basic-offset: 8 --/
60918275 LP	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	#ifdef HAVE_CONFIG_H
	23	#include <config.h>
	24	#endif
	25
	26	#include <assert.h>
	27	#include <stdlib.h>
	28	#include <string.h>
	29	#include <errno.h>
	30
	31	#include "util.h"
	32	#include "hashmap.h"
	33	#include "macro.h"
	34
	35	#define NBUCKETS 127
	36
	37	struct hashmap_entry {
	38	const void *key;
	39	void *value;
60918275 LP	40	struct hashmap_entry bucket_next, bucket_previous;
	41	struct hashmap_entry iterate_next, iterate_previous;
	42	};
	43
	44	struct Hashmap {
	45	hash_func_t hash_func;
	46	compare_func_t compare_func;
	47
	48	struct hashmap_entry iterate_list_head, iterate_list_tail;
	49	unsigned n_entries;
	50	};
	51
	52	#define BY_HASH(h) ((struct hashmap_entry*) ((uint8_t) (h) + ALIGN(sizeof(Hashmap))))
	53
	54	unsigned string_hash_func(const void *p) {
	55	unsigned hash = 0;
	56	const char *c;
	57
	58	for (c = p; *c; c++)
	59	hash = 31 * hash + (unsigned) *c;
	60
	61	return hash;
	62	}
	63
	64	int string_compare_func(const void a, const void b) {
	65	return strcmp(a, b);
	66	}
	67
	68	unsigned trivial_hash_func(const void *p) {
	69	return PTR_TO_UINT(p);
	70	}
	71
	72	int trivial_compare_func(const void a, const void b) {
	73	return a < b ? -1 : (a > b ? 1 : 0);
	74	}
	75
	76	Hashmap *hashmap_new(hash_func_t hash_func, compare_func_t compare_func) {
	77	Hashmap *h;
	78
	79	if (!(h = malloc0(ALIGN(sizeof(Hashmap)) + NBUCKETS * ALIGN(sizeof(struct hashmap_entry*)))))
	80	return NULL;
	81
	82	h->hash_func = hash_func ? hash_func : trivial_hash_func;
	83	h->compare_func = compare_func ? compare_func : trivial_compare_func;
	84
	85	h->n_entries = 0;
	86	h->iterate_list_head = h->iterate_list_tail = NULL;
	87
	88	return h;
	89	}
	90
034c6ed7 LP	91	int hashmap_ensure_allocated(Hashmap **h, hash_func_t hash_func, compare_func_t compare_func) {
	92	assert(h);
	93
	94	if (*h)
	95	return 0;
	96
	97	if (!(*h = hashmap_new(hash_func, compare_func)))
	98	return -ENOMEM;
	99
	100	return 0;
	101	}
	102
60918275 LP	103	static void remove_entry(Hashmap h, struct hashmap_entry e) {
	104	assert(h);
	105	assert(e);
	106
	107	/* Remove from iteration list */
	108	if (e->iterate_next)
	109	e->iterate_next->iterate_previous = e->iterate_previous;
	110	else
	111	h->iterate_list_tail = e->iterate_previous;
	112
	113	if (e->iterate_previous)
	114	e->iterate_previous->iterate_next = e->iterate_next;
	115	else
	116	h->iterate_list_head = e->iterate_next;
	117
	118	/* Remove from hash table bucket list */
	119	if (e->bucket_next)
	120	e->bucket_next->bucket_previous = e->bucket_previous;
	121
	122	if (e->bucket_previous)
	123	e->bucket_previous->bucket_next = e->bucket_next;
	124	else {
	125	unsigned hash = h->hash_func(e->key) % NBUCKETS;
	126	BY_HASH(h)[hash] = e->bucket_next;
	127	}
	128
	129	free(e);
	130
	131	assert(h->n_entries >= 1);
	132	h->n_entries--;
	133	}
	134
	135	void hashmap_free(Hashmap*h) {
	136
	137	if (!h)
	138	return;
	139
11dd41ce	140	hashmap_clear(h);
60918275 LP	141
	142	free(h);
	143	}
	144
11dd41ce LP	145	void hashmap_clear(Hashmap *h) {
	146	if (!h)
	147	return;
	148
	149	while (h->iterate_list_head)
	150	remove_entry(h, h->iterate_list_head);
	151	}
	152
60918275 LP	153	static struct hashmap_entry hash_scan(Hashmap h, unsigned hash, const void *key) {
	154	struct hashmap_entry *e;
	155	assert(h);
	156	assert(hash < NBUCKETS);
	157
	158	for (e = BY_HASH(h)[hash]; e; e = e->bucket_next)
	159	if (h->compare_func(e->key, key) == 0)
	160	return e;
	161
	162	return NULL;
	163	}
	164
	165	int hashmap_put(Hashmap h, const void key, void *value) {
	166	struct hashmap_entry *e;
	167	unsigned hash;
	168
	169	assert(h);
	170
	171	hash = h->hash_func(key) % NBUCKETS;
	172
3158713e LP	173	if ((e = hash_scan(h, hash, key))) {
	174
	175	if (e->value == value)
	176	return 0;
	177
60918275	178	return -EEXIST;
3158713e	179	}
60918275 LP	180
	181	if (!(e = new(struct hashmap_entry, 1)))
	182	return -ENOMEM;
	183
	184	e->key = key;
	185	e->value = value;
	186
	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;
	193
	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;
	200	} else {
	201	assert(!h->iterate_list_head);
	202	h->iterate_list_head = e;
	203	}
	204	h->iterate_list_tail = e;
	205
	206	h->n_entries++;
	207	assert(h->n_entries >= 1);
	208
	209	return 0;
	210	}
	211
3158713e LP	212	int hashmap_replace(Hashmap h, const void key, void *value) {
	213	struct hashmap_entry *e;
	214	unsigned hash;
	215
	216	assert(h);
	217
	218	hash = h->hash_func(key) % NBUCKETS;
	219
	220	if ((e = hash_scan(h, hash, key))) {
	221	e->value = value;
	222	return 0;
	223	}
	224
	225	return hashmap_put(h, key, value);
	226	}
	227
60918275 LP	228	void* hashmap_get(Hashmap h, const void key) {
	229	unsigned hash;
	230	struct hashmap_entry *e;
	231
	232	if (!h)
	233	return NULL;
	234
	235	hash = h->hash_func(key) % NBUCKETS;
	236
	237	if (!(e = hash_scan(h, hash, key)))
	238	return NULL;
	239
	240	return e->value;
	241	}
	242
	243	void* hashmap_remove(Hashmap h, const void key) {
	244	struct hashmap_entry *e;
	245	unsigned hash;
	246	void *data;
	247
	248	if (!h)
	249	return NULL;
	250
	251	hash = h->hash_func(key) % NBUCKETS;
	252
	253	if (!(e = hash_scan(h, hash, key)))
	254	return NULL;
	255
	256	data = e->value;
	257	remove_entry(h, e);
	258
	259	return data;
	260	}
	261
3158713e LP	262	void* hashmap_remove_value(Hashmap h, const void key, void *value) {
	263	struct hashmap_entry *e;
	264	unsigned hash;
	265
	266	if (!h)
	267	return NULL;
	268
	269	hash = h->hash_func(key) % NBUCKETS;
	270
	271	if (!(e = hash_scan(h, hash, key)))
	272	return NULL;
	273
	274	if (e->value != value)
	275	return NULL;
	276
	277	remove_entry(h, e);
	278
	279	return value;
	280	}
	281
034c6ed7	282	void hashmap_iterate(Hashmap h, Iterator i, const void *key) {
60918275 LP	283	struct hashmap_entry *e;
60918275 LP	284
034c6ed7	285	assert(i);
60918275 LP	286
	287	if (!h)
	288	goto at_end;
	289
034c6ed7	290	if (*i == ITERATOR_LAST)
60918275 LP	291	goto at_end;
60918275 LP	292
034c6ed7	293	if (*i == ITERATOR_FIRST && !h->iterate_list_head)
60918275 LP	294	goto at_end;
60918275 LP	295
034c6ed7	296	e = i == ITERATOR_FIRST ? h->iterate_list_head : (struct hashmap_entry) *i;
60918275 LP	297
60918275 LP	298	if (e->iterate_next)
034c6ed7	299	*i = (Iterator) e->iterate_next;
60918275	300	else
034c6ed7	301	*i = ITERATOR_LAST;
60918275 LP	302
	303	if (key)
	304	*key = e->key;
	305
	306	return e->value;
	307
	308	at_end:
034c6ed7	309	*i = ITERATOR_LAST;
60918275 LP	310
	311	if (key)
	312	*key = NULL;
	313
	314	return NULL;
	315	}
	316
034c6ed7	317	void hashmap_iterate_backwards(Hashmap h, Iterator i, const void *key) {
60918275 LP	318	struct hashmap_entry *e;
60918275 LP	319
034c6ed7	320	assert(i);
60918275 LP	321
	322	if (!h)
	323	goto at_beginning;
	324
034c6ed7	325	if (*i == ITERATOR_FIRST)
60918275 LP	326	goto at_beginning;
60918275 LP	327
034c6ed7	328	if (*i == ITERATOR_LAST && !h->iterate_list_tail)
60918275 LP	329	goto at_beginning;
60918275 LP	330
034c6ed7	331	e = i == ITERATOR_LAST ? h->iterate_list_tail : (struct hashmap_entry) *i;
60918275 LP	332
60918275 LP	333	if (e->iterate_previous)
034c6ed7	334	*i = (Iterator) e->iterate_previous;
60918275	335	else
034c6ed7	336	*i = ITERATOR_FIRST;
60918275 LP	337
	338	if (key)
	339	*key = e->key;
	340
	341	return e->value;
	342
	343	at_beginning:
034c6ed7	344	*i = ITERATOR_FIRST;
60918275 LP	345
	346	if (key)
	347	*key = NULL;
	348
	349	return NULL;
	350	}
	351
034c6ed7 LP	352	void hashmap_iterate_skip(Hashmap h, const void key, Iterator i) {
	353	unsigned hash;
	354	struct hashmap_entry *e;
	355
	356	if (!h)
	357	return NULL;
	358
	359	hash = h->hash_func(key) % NBUCKETS;
	360
	361	if (!(e = hash_scan(h, hash, key)))
	362	return NULL;
	363
	364	*i = (Iterator) e;
	365
	366	return e->value;
	367	}
	368
60918275 LP	369	void* hashmap_first(Hashmap *h) {
	370
	371	if (!h)
	372	return NULL;
	373
	374	if (!h->iterate_list_head)
	375	return NULL;
	376
	377	return h->iterate_list_head->value;
	378	}
	379
	380	void* hashmap_last(Hashmap *h) {
	381
	382	if (!h)
	383	return NULL;
	384
	385	if (!h->iterate_list_tail)
	386	return NULL;
	387
	388	return h->iterate_list_tail->value;
	389	}
	390
	391	void* hashmap_steal_first(Hashmap *h) {
	392	void *data;
	393
	394	if (!h)
	395	return NULL;
	396
	397	if (!h->iterate_list_head)
	398	return NULL;
	399
	400	data = h->iterate_list_head->value;
	401	remove_entry(h, h->iterate_list_head);
	402
	403	return data;
	404	}
	405
	406	unsigned hashmap_size(Hashmap *h) {
	407
	408	if (!h)
	409	return 0;
	410
	411	return h->n_entries;
	412	}
	413
	414	bool hashmap_isempty(Hashmap *h) {
	415
	416	if (!h)
	417	return true;
	418
	419	return h->n_entries == 0;
	420	}
91cdde8a LP	421
	422	int hashmap_merge(Hashmap h, Hashmap other) {
	423	struct hashmap_entry *e;
	424
	425	assert(h);
	426
	427	if (!other)
	428	return 0;
	429
	430	for (e = other->iterate_list_head; e; e = e->iterate_next) {
	431	int r;
	432
	433	if ((r = hashmap_put(h, e->key, e->value)) < 0)
	434	if (r != -EEXIST)
	435	return r;
	436	}
	437
	438	return 0;
	439	}
	440
	441	Hashmap hashmap_copy(Hashmap h) {
	442	Hashmap *copy;
	443
	444	assert(h);
	445
	446	if (!(copy = hashmap_new(h->hash_func, h->compare_func)))
	447	return NULL;
	448
	449	if (hashmap_merge(copy, h) < 0) {
	450	hashmap_free(copy);
	451	return NULL;
	452	}
	453
	454	return copy;
	455	}