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

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, void **state, const void **key) {
        struct hashmap_entry *e;

        assert(state);

        if (!h)
                goto at_end;

        if (*state == (void*) -1)
                goto at_end;

        if (!*state && !h->iterate_list_head)
                goto at_end;

        e = *state ? *state : h->iterate_list_head;

        if (e->iterate_next)
                *state = e->iterate_next;
        else
                *state = (void*) -1;

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

        return e->value;

at_end:
        *state = (void *) -1;

        if (key)
                *key = NULL;

        return NULL;
}

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

        assert(state);

        if (!h)
                goto at_beginning;

        if (*state == (void*) -1)
                goto at_beginning;

        if (!*state && !h->iterate_list_tail)
                goto at_beginning;

        e = *state ? *state : h->iterate_list_tail;

        if (e->iterate_previous)
                *state = e->iterate_previous;
        else
                *state = (void*) -1;

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

        return e->value;

at_beginning:
        *state = (void *) -1;

        if (key)
                *key = NULL;

        return NULL;
}

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
	72	static void remove_entry(Hashmap h, struct hashmap_entry e) {
	73	assert(h);
	74	assert(e);
	75
	76	/* Remove from iteration list */
	77	if (e->iterate_next)
	78	e->iterate_next->iterate_previous = e->iterate_previous;
	79	else
	80	h->iterate_list_tail = e->iterate_previous;
	81
	82	if (e->iterate_previous)
	83	e->iterate_previous->iterate_next = e->iterate_next;
	84	else
85	h->iterate_list_head = e->iterate_next;
86
87	/* Remove from hash table bucket list */
88	if (e->bucket_next)
89	e->bucket_next->bucket_previous = e->bucket_previous;
90
91	if (e->bucket_previous)
92	e->bucket_previous->bucket_next = e->bucket_next;
93	else {
94	unsigned hash = h->hash_func(e->key) % NBUCKETS;
95	BY_HASH(h)[hash] = e->bucket_next;
96	}
97
98	free(e);
99
100	assert(h->n_entries >= 1);
101	h->n_entries--;
102	}
103
104	void hashmap_free(Hashmap*h) {
105
106	if (!h)
107	return;
108
11dd41ce	109	hashmap_clear(h);
60918275 LP	110
	111	free(h);
	112	}
	113
11dd41ce LP	114	void hashmap_clear(Hashmap *h) {
	115	if (!h)
	116	return;
	117
	118	while (h->iterate_list_head)
	119	remove_entry(h, h->iterate_list_head);
	120	}
	121
60918275 LP	122	static struct hashmap_entry hash_scan(Hashmap h, unsigned hash, const void *key) {
	123	struct hashmap_entry *e;
	124	assert(h);
	125	assert(hash < NBUCKETS);
	126
	127	for (e = BY_HASH(h)[hash]; e; e = e->bucket_next)
	128	if (h->compare_func(e->key, key) == 0)
	129	return e;
	130
	131	return NULL;
	132	}
	133
	134	int hashmap_put(Hashmap h, const void key, void *value) {
	135	struct hashmap_entry *e;
	136	unsigned hash;
	137
	138	assert(h);
	139
	140	hash = h->hash_func(key) % NBUCKETS;
	141
3158713e LP	142	if ((e = hash_scan(h, hash, key))) {
	143
	144	if (e->value == value)
	145	return 0;
	146
60918275	147	return -EEXIST;
3158713e	148	}
60918275 LP	149
	150	if (!(e = new(struct hashmap_entry, 1)))
	151	return -ENOMEM;
	152
	153	e->key = key;
	154	e->value = value;
	155
	156	/* Insert into hash table */
	157	e->bucket_next = BY_HASH(h)[hash];
	158	e->bucket_previous = NULL;
	159	if (BY_HASH(h)[hash])
	160	BY_HASH(h)[hash]->bucket_previous = e;
	161	BY_HASH(h)[hash] = e;
	162
	163	/* Insert into iteration list */
	164	e->iterate_previous = h->iterate_list_tail;
	165	e->iterate_next = NULL;
	166	if (h->iterate_list_tail) {
	167	assert(h->iterate_list_head);
	168	h->iterate_list_tail->iterate_next = e;
	169	} else {
	170	assert(!h->iterate_list_head);
	171	h->iterate_list_head = e;
	172	}
	173	h->iterate_list_tail = e;
	174
	175	h->n_entries++;
	176	assert(h->n_entries >= 1);
	177
	178	return 0;
	179	}
	180
3158713e LP	181	int hashmap_replace(Hashmap h, const void key, void *value) {
	182	struct hashmap_entry *e;
	183	unsigned hash;
	184
	185	assert(h);
	186
	187	hash = h->hash_func(key) % NBUCKETS;
	188
	189	if ((e = hash_scan(h, hash, key))) {
	190	e->value = value;
	191	return 0;
	192	}
	193
	194	return hashmap_put(h, key, value);
	195	}
	196
60918275 LP	197	void* hashmap_get(Hashmap h, const void key) {
	198	unsigned hash;
	199	struct hashmap_entry *e;
	200
	201	if (!h)
	202	return NULL;
	203
	204	hash = h->hash_func(key) % NBUCKETS;
	205
	206	if (!(e = hash_scan(h, hash, key)))
	207	return NULL;
	208
	209	return e->value;
	210	}
	211
	212	void* hashmap_remove(Hashmap h, const void key) {
	213	struct hashmap_entry *e;
	214	unsigned hash;
	215	void *data;
	216
	217	if (!h)
	218	return NULL;
	219
	220	hash = h->hash_func(key) % NBUCKETS;
	221
	222	if (!(e = hash_scan(h, hash, key)))
	223	return NULL;
	224
	225	data = e->value;
	226	remove_entry(h, e);
	227
	228	return data;
	229	}
	230
3158713e LP	231	void* hashmap_remove_value(Hashmap h, const void key, void *value) {
	232	struct hashmap_entry *e;
	233	unsigned hash;
	234
	235	if (!h)
	236	return NULL;
	237
	238	hash = h->hash_func(key) % NBUCKETS;
	239
	240	if (!(e = hash_scan(h, hash, key)))
	241	return NULL;
	242
	243	if (e->value != value)
	244	return NULL;
	245
	246	remove_entry(h, e);
	247
	248	return value;
	249	}
	250
60918275 LP	251	void hashmap_iterate(Hashmap h, void state, const void key) {
	252	struct hashmap_entry *e;
	253
	254	assert(state);
	255
	256	if (!h)
	257	goto at_end;
	258
	259	if (state == (void) -1)
	260	goto at_end;
	261
	262	if (!*state && !h->iterate_list_head)
	263	goto at_end;
	264
	265	e = state ? state : h->iterate_list_head;
	266
	267	if (e->iterate_next)
	268	*state = e->iterate_next;
	269	else
	270	state = (void) -1;
	271
	272	if (key)
	273	*key = e->key;
	274
	275	return e->value;
	276
	277	at_end:
	278	state = (void ) -1;
	279
	280	if (key)
	281	*key = NULL;
	282
	283	return NULL;
	284	}
	285
	286	void hashmap_iterate_backwards(Hashmap h, void state, const void key) {
	287	struct hashmap_entry *e;
	288
	289	assert(state);
	290
	291	if (!h)
	292	goto at_beginning;
	293
	294	if (state == (void) -1)
	295	goto at_beginning;
	296
	297	if (!*state && !h->iterate_list_tail)
	298	goto at_beginning;
	299
	300	e = state ? state : h->iterate_list_tail;
	301
	302	if (e->iterate_previous)
	303	*state = e->iterate_previous;
	304	else
	305	state = (void) -1;
	306
	307	if (key)
	308	*key = e->key;
	309
	310	return e->value;
	311
	312	at_beginning:
	313	state = (void ) -1;
	314
315	if (key)
316	*key = NULL;
317
318	return NULL;
319	}
320
321	void* hashmap_first(Hashmap *h) {
322
323	if (!h)
324	return NULL;
325
326	if (!h->iterate_list_head)
327	return NULL;
328
329	return h->iterate_list_head->value;
330	}
331
332	void* hashmap_last(Hashmap *h) {
333
334	if (!h)
335	return NULL;
336
337	if (!h->iterate_list_tail)
338	return NULL;
339
340	return h->iterate_list_tail->value;
341	}
342
343	void* hashmap_steal_first(Hashmap *h) {
344	void *data;
345
346	if (!h)
347	return NULL;
348
349	if (!h->iterate_list_head)
350	return NULL;
351
352	data = h->iterate_list_head->value;
353	remove_entry(h, h->iterate_list_head);
354
355	return data;
356	}
357
358	unsigned hashmap_size(Hashmap *h) {
359
360	if (!h)
361	return 0;
362
363	return h->n_entries;
364	}
365
366	bool hashmap_isempty(Hashmap *h) {
367
368	if (!h)
369	return true;
370
371	return h->n_entries == 0;
372	}
91cdde8a LP	373
	374	int hashmap_merge(Hashmap h, Hashmap other) {
	375	struct hashmap_entry *e;
	376
	377	assert(h);
	378
	379	if (!other)
	380	return 0;
	381
	382	for (e = other->iterate_list_head; e; e = e->iterate_next) {
	383	int r;
	384
	385	if ((r = hashmap_put(h, e->key, e->value)) < 0)
	386	if (r != -EEXIST)
	387	return r;
	388	}
	389
	390	return 0;
	391	}
	392
	393	Hashmap hashmap_copy(Hashmap h) {
	394	Hashmap *copy;
	395
	396	assert(h);
	397
	398	if (!(copy = hashmap_new(h->hash_func, h->compare_func)))
	399	return NULL;
	400
	401	if (hashmap_merge(copy, h) < 0) {
	402	hashmap_free(copy);
	403	return NULL;
	404	}
	405
	406	return copy;
	407	}