[thirdparty/systemd.git] / hashmap.c

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

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