[thirdparty/kmod.git] / shared / hash.c

/*
 * libkmod - interface to kernel module operations
 *
 * Copyright (C) 2011-2013  ProFUSION embedded systems
 *
 * This library 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.
 *
 * This library 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 this library; if not, see <http://www.gnu.org/licenses/>.
 */

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

#include <shared/hash.h>
#include <shared/util.h>

struct hash_entry {
	const char *key;
	const void *value;
};

struct hash_bucket {
	struct hash_entry *entries;
	unsigned int used;
	unsigned int total;
};

struct hash {
	unsigned int count;
	unsigned int step;
	unsigned int n_buckets;
	void (*free_value)(void *value);
	struct hash_bucket buckets[];
};

struct hash *hash_new(unsigned int n_buckets,
					void (*free_value)(void *value))
{
	struct hash *hash;

	n_buckets = ALIGN_POWER2(n_buckets);
	hash = calloc(1, sizeof(struct hash) +
		      n_buckets * sizeof(struct hash_bucket));
	if (hash == NULL)
		return NULL;
	hash->n_buckets = n_buckets;
	hash->free_value = free_value;
	hash->step = n_buckets / 32;
	if (hash->step == 0)
		hash->step = 4;
	else if (hash->step > 64)
		hash->step = 64;
	return hash;
}

void hash_free(struct hash *hash)
{
	struct hash_bucket *bucket, *bucket_end;

	if (hash == NULL)
		return;

	bucket = hash->buckets;
	bucket_end = bucket + hash->n_buckets;
	for (; bucket < bucket_end; bucket++) {
		if (hash->free_value) {
			struct hash_entry *entry, *entry_end;
			entry = bucket->entries;
			entry_end = entry + bucket->used;
			for (; entry < entry_end; entry++)
				hash->free_value((void *)entry->value);
		}
		free(bucket->entries);
	}
	free(hash);
}

static inline unsigned int hash_superfast(const char *key, unsigned int len)
{
	/* Paul Hsieh (http://www.azillionmonkeys.com/qed/hash.html)
	 * used by WebCore (http://webkit.org/blog/8/hashtables-part-2/)
	 * EFL's eina and possible others.
	 */
	unsigned int tmp, hash = len, rem = len & 3;

	len /= 4;

	/* Main loop */
	for (; len > 0; len--) {
		hash += get_unaligned((uint16_t *) key);
		tmp = (get_unaligned((uint16_t *)(key + 2)) << 11) ^ hash;
		hash = (hash << 16) ^ tmp;
		key += 4;
		hash += hash >> 11;
	}

	/* Handle end cases */
	switch (rem) {
	case 3:
		hash += get_unaligned((uint16_t *) key);
		hash ^= hash << 16;
		hash ^= key[2] << 18;
		hash += hash >> 11;
		break;

	case 2:
		hash += get_unaligned((uint16_t *) key);
		hash ^= hash << 11;
		hash += hash >> 17;
		break;

	case 1:
		hash += *key;
		hash ^= hash << 10;
		hash += hash >> 1;
	}

	/* Force "avalanching" of final 127 bits */
	hash ^= hash << 3;
	hash += hash >> 5;
	hash ^= hash << 4;
	hash += hash >> 17;
	hash ^= hash << 25;
	hash += hash >> 6;

	return hash;
}

/*
 * add or replace key in hash map.
 *
 * none of key or value are copied, just references are remembered as is,
 * make sure they are live while pair exists in hash!
 */
int hash_add(struct hash *hash, const char *key, const void *value)
{
	unsigned int keylen = strlen(key);
	unsigned int hashval = hash_superfast(key, keylen);
	unsigned int pos = hashval & (hash->n_buckets - 1);
	struct hash_bucket *bucket = hash->buckets + pos;
	struct hash_entry *entry, *entry_end;

	if (bucket->used + 1 >= bucket->total) {
		unsigned new_total = bucket->total + hash->step;
		size_t size = new_total * sizeof(struct hash_entry);
		struct hash_entry *tmp = realloc(bucket->entries, size);
		if (tmp == NULL)
			return -errno;
		bucket->entries = tmp;
		bucket->total = new_total;
	}

	entry = bucket->entries;
	entry_end = entry + bucket->used;
	for (; entry < entry_end; entry++) {
		int c = strcmp(key, entry->key);
		if (c == 0) {
			if (hash->free_value)
				hash->free_value((void *)entry->value);
			entry->key = key;
			entry->value = value;
			return 0;
		} else if (c < 0) {
			memmove(entry + 1, entry,
				(entry_end - entry) * sizeof(struct hash_entry));
			break;
		}
	}

	entry->key = key;
	entry->value = value;
	bucket->used++;
	hash->count++;
	return 0;
}

/* similar to hash_add(), but fails if key already exists */
int hash_add_unique(struct hash *hash, const char *key, const void *value)
{
	unsigned int keylen = strlen(key);
	unsigned int hashval = hash_superfast(key, keylen);
	unsigned int pos = hashval & (hash->n_buckets - 1);
	struct hash_bucket *bucket = hash->buckets + pos;
	struct hash_entry *entry, *entry_end;

	if (bucket->used + 1 >= bucket->total) {
		unsigned new_total = bucket->total + hash->step;
		size_t size = new_total * sizeof(struct hash_entry);
		struct hash_entry *tmp = realloc(bucket->entries, size);
		if (tmp == NULL)
			return -errno;
		bucket->entries = tmp;
		bucket->total = new_total;
	}

	entry = bucket->entries;
	entry_end = entry + bucket->used;
	for (; entry < entry_end; entry++) {
		int c = strcmp(key, entry->key);
		if (c == 0)
			return -EEXIST;
		else if (c < 0) {
			memmove(entry + 1, entry,
				(entry_end - entry) * sizeof(struct hash_entry));
			break;
		}
	}

	entry->key = key;
	entry->value = value;
	bucket->used++;
	hash->count++;
	return 0;
}

static int hash_entry_cmp(const void *pa, const void *pb)
{
	const struct hash_entry *a = pa;
	const struct hash_entry *b = pb;
	return strcmp(a->key, b->key);
}

void *hash_find(const struct hash *hash, const char *key)
{
	unsigned int keylen = strlen(key);
	unsigned int hashval = hash_superfast(key, keylen);
	unsigned int pos = hashval & (hash->n_buckets - 1);
	const struct hash_bucket *bucket = hash->buckets + pos;
	const struct hash_entry se = {
		.key = key,
		.value = NULL
	};
	const struct hash_entry *entry = bsearch(
		&se, bucket->entries, bucket->used,
		sizeof(struct hash_entry), hash_entry_cmp);
	if (entry == NULL)
		return NULL;
	return (void *)entry->value;
}

int hash_del(struct hash *hash, const char *key)
{
	unsigned int keylen = strlen(key);
	unsigned int hashval = hash_superfast(key, keylen);
	unsigned int pos = hashval & (hash->n_buckets - 1);
	unsigned int steps_used, steps_total;
	struct hash_bucket *bucket = hash->buckets + pos;
	struct hash_entry *entry, *entry_end;
	const struct hash_entry se = {
		.key = key,
		.value = NULL
	};

	entry = bsearch(&se, bucket->entries, bucket->used,
		sizeof(struct hash_entry), hash_entry_cmp);
	if (entry == NULL)
		return -ENOENT;

	if (hash->free_value)
		hash->free_value((void *)entry->value);

	entry_end = bucket->entries + bucket->used;
	memmove(entry, entry + 1,
		(entry_end - entry) * sizeof(struct hash_entry));

	bucket->used--;
	hash->count--;

	steps_used = bucket->used / hash->step;
	steps_total = bucket->total / hash->step;
	if (steps_used + 1 < steps_total) {
		size_t size = (steps_used + 1) *
			hash->step * sizeof(struct hash_entry);
		struct hash_entry *tmp = realloc(bucket->entries, size);
		if (tmp) {
			bucket->entries = tmp;
			bucket->total = (steps_used + 1) * hash->step;
		}
	}

	return 0;
}

unsigned int hash_get_count(const struct hash *hash)
{
	return hash->count;
}

void hash_iter_init(const struct hash *hash, struct hash_iter *iter)
{
	iter->hash = hash;
	iter->bucket = 0;
	iter->entry = -1;
}

bool hash_iter_next(struct hash_iter *iter, const char **key,
							const void **value)
{
	const struct hash_bucket *b = iter->hash->buckets + iter->bucket;
	const struct hash_entry *e;

	iter->entry++;

	if (iter->entry >= b->used) {
		iter->entry = 0;

		for (iter->bucket++; iter->bucket < iter->hash->n_buckets;
							iter->bucket++) {
			b = iter->hash->buckets + iter->bucket;

			if (b->used > 0)
				break;
		}

		if (iter->bucket >= iter->hash->n_buckets)
			return false;
	}

	e = b->entries + iter->entry;

	if (value != NULL)
		*value = e->value;
	if (key != NULL)
		*key = e->key;

	return true;
}
Commit	Line	Data
7db08652 GSB	1	/*
	2	* libkmod - interface to kernel module operations
	3	*
e6b0e49b	4	* Copyright (C) 2011-2013 ProFUSION embedded systems
7db08652 GSB	5	*
	6	* This library is free software; you can redistribute it and/or
	7	* modify it under the terms of the GNU Lesser General Public
cb451f35 LDM	8	* License as published by the Free Software Foundation; either
cb451f35 LDM	9	* version 2.1 of the License, or (at your option) any later version.
7db08652 GSB	10	*
	11	* This library is distributed in the hope that it will be useful,
	12	* but WITHOUT ANY WARRANTY; without even the implied warranty of
	13	* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
	14	* Lesser General Public License for more details.
	15	*
	16	* You should have received a copy of the GNU Lesser General Public
dea2dfee	17	* License along with this library; if not, see <http://www.gnu.org/licenses/>.
7db08652 GSB	18	*/
7db08652 GSB	19
c2e4286b	20	#include <errno.h>
0db718ed	21	#include <inttypes.h>
7db08652 GSB	22	#include <stdlib.h>
7db08652 GSB	23	#include <string.h>
7db08652	24
0db718ed LDM	25	#include <shared/hash.h>
	26	#include <shared/util.h>
	27
822913d7	28	struct hash_entry {
7db08652 GSB	29	const char *key;
	30	const void *value;
	31	};
	32
822913d7 LDM	33	struct hash_bucket {
822913d7 LDM	34	struct hash_entry *entries;
7db08652 GSB	35	unsigned int used;
	36	unsigned int total;
	37	};
	38
822913d7	39	struct hash {
7db08652 GSB	40	unsigned int count;
	41	unsigned int step;
	42	unsigned int n_buckets;
	43	void (free_value)(void value);
822913d7	44	struct hash_bucket buckets[];
7db08652 GSB	45	};
7db08652 GSB	46
822913d7	47	struct hash *hash_new(unsigned int n_buckets,
c35347f1	48	void (free_value)(void value))
7db08652	49	{
82fc7d98 LDM	50	struct hash *hash;
	51
	52	n_buckets = ALIGN_POWER2(n_buckets);
	53	hash = calloc(1, sizeof(struct hash) +
	54	n_buckets * sizeof(struct hash_bucket));
7db08652 GSB	55	if (hash == NULL)
	56	return NULL;
	57	hash->n_buckets = n_buckets;
	58	hash->free_value = free_value;
	59	hash->step = n_buckets / 32;
	60	if (hash->step == 0)
	61	hash->step = 4;
	62	else if (hash->step > 64)
	63	hash->step = 64;
	64	return hash;
	65	}
	66
822913d7	67	void hash_free(struct hash *hash)
7db08652	68	{
822913d7	69	struct hash_bucket bucket, bucket_end;
4f17bb0b DR	70
	71	if (hash == NULL)
	72	return;
	73
7db08652 GSB	74	bucket = hash->buckets;
	75	bucket_end = bucket + hash->n_buckets;
	76	for (; bucket < bucket_end; bucket++) {
	77	if (hash->free_value) {
822913d7	78	struct hash_entry entry, entry_end;
7db08652 GSB	79	entry = bucket->entries;
	80	entry_end = entry + bucket->used;
	81	for (; entry < entry_end; entry++)
	82	hash->free_value((void *)entry->value);
	83	}
	84	free(bucket->entries);
	85	}
	86	free(hash);
	87	}
	88
	89	static inline unsigned int hash_superfast(const char *key, unsigned int len)
	90	{
	91	/* Paul Hsieh (http://www.azillionmonkeys.com/qed/hash.html)
	92	* used by WebCore (http://webkit.org/blog/8/hashtables-part-2/)
	93	* EFL's eina and possible others.
	94	*/
	95	unsigned int tmp, hash = len, rem = len & 3;
7db08652 GSB	96
	97	len /= 4;
	98
	99	/* Main loop */
	100	for (; len > 0; len--) {
af9080d9 LDM	101	hash += get_unaligned((uint16_t *) key);
af9080d9 LDM	102	tmp = (get_unaligned((uint16_t *)(key + 2)) << 11) ^ hash;
7db08652	103	hash = (hash << 16) ^ tmp;
a2c7d3e8	104	key += 4;
7db08652 GSB	105	hash += hash >> 11;
	106	}
	107
	108	/* Handle end cases */
	109	switch (rem) {
	110	case 3:
af9080d9	111	hash += get_unaligned((uint16_t *) key);
7db08652 GSB	112	hash ^= hash << 16;
	113	hash ^= key[2] << 18;
	114	hash += hash >> 11;
	115	break;
	116
	117	case 2:
af9080d9	118	hash += get_unaligned((uint16_t *) key);
7db08652 GSB	119	hash ^= hash << 11;
	120	hash += hash >> 17;
	121	break;
	122
	123	case 1:
a2c7d3e8	124	hash += *key;
7db08652 GSB	125	hash ^= hash << 10;
	126	hash += hash >> 1;
	127	}
	128
	129	/* Force "avalanching" of final 127 bits */
	130	hash ^= hash << 3;
	131	hash += hash >> 5;
	132	hash ^= hash << 4;
	133	hash += hash >> 17;
	134	hash ^= hash << 25;
	135	hash += hash >> 6;
	136
	137	return hash;
	138	}
	139
	140	/*
	141	* add or replace key in hash map.
	142	*
	143	* none of key or value are copied, just references are remembered as is,
	144	* make sure they are live while pair exists in hash!
	145	*/
822913d7	146	int hash_add(struct hash hash, const char key, const void *value)
7db08652 GSB	147	{
	148	unsigned int keylen = strlen(key);
	149	unsigned int hashval = hash_superfast(key, keylen);
82fc7d98	150	unsigned int pos = hashval & (hash->n_buckets - 1);
822913d7 LDM	151	struct hash_bucket *bucket = hash->buckets + pos;
822913d7 LDM	152	struct hash_entry entry, entry_end;
7db08652 GSB	153
	154	if (bucket->used + 1 >= bucket->total) {
	155	unsigned new_total = bucket->total + hash->step;
822913d7 LDM	156	size_t size = new_total * sizeof(struct hash_entry);
822913d7 LDM	157	struct hash_entry *tmp = realloc(bucket->entries, size);
7db08652 GSB	158	if (tmp == NULL)
	159	return -errno;
	160	bucket->entries = tmp;
	161	bucket->total = new_total;
	162	}
	163
	164	entry = bucket->entries;
	165	entry_end = entry + bucket->used;
	166	for (; entry < entry_end; entry++) {
	167	int c = strcmp(key, entry->key);
	168	if (c == 0) {
1faec2c1 LP	169	if (hash->free_value)
1faec2c1 LP	170	hash->free_value((void *)entry->value);
86e19e9a	171	entry->key = key;
7db08652 GSB	172	entry->value = value;
	173	return 0;
	174	} else if (c < 0) {
	175	memmove(entry + 1, entry,
822913d7	176	(entry_end - entry) * sizeof(struct hash_entry));
7db08652 GSB	177	break;
	178	}
	179	}
	180
	181	entry->key = key;
	182	entry->value = value;
	183	bucket->used++;
	184	hash->count++;
	185	return 0;
	186	}
	187
d7073807 LDM	188	/* similar to hash_add(), but fails if key already exists */
	189	int hash_add_unique(struct hash hash, const char key, const void *value)
	190	{
	191	unsigned int keylen = strlen(key);
	192	unsigned int hashval = hash_superfast(key, keylen);
82fc7d98	193	unsigned int pos = hashval & (hash->n_buckets - 1);
d7073807 LDM	194	struct hash_bucket *bucket = hash->buckets + pos;
	195	struct hash_entry entry, entry_end;
	196
	197	if (bucket->used + 1 >= bucket->total) {
	198	unsigned new_total = bucket->total + hash->step;
	199	size_t size = new_total * sizeof(struct hash_entry);
	200	struct hash_entry *tmp = realloc(bucket->entries, size);
	201	if (tmp == NULL)
	202	return -errno;
	203	bucket->entries = tmp;
	204	bucket->total = new_total;
	205	}
	206
	207	entry = bucket->entries;
	208	entry_end = entry + bucket->used;
	209	for (; entry < entry_end; entry++) {
	210	int c = strcmp(key, entry->key);
	211	if (c == 0)
	212	return -EEXIST;
	213	else if (c < 0) {
	214	memmove(entry + 1, entry,
	215	(entry_end - entry) * sizeof(struct hash_entry));
	216	break;
	217	}
	218	}
	219
	220	entry->key = key;
	221	entry->value = value;
	222	bucket->used++;
	223	hash->count++;
	224	return 0;
	225	}
	226
822913d7	227	static int hash_entry_cmp(const void pa, const void pb)
7db08652	228	{
822913d7 LDM	229	const struct hash_entry *a = pa;
822913d7 LDM	230	const struct hash_entry *b = pb;
7db08652 GSB	231	return strcmp(a->key, b->key);
	232	}
	233
822913d7	234	void hash_find(const struct hash hash, const char *key)
7db08652 GSB	235	{
	236	unsigned int keylen = strlen(key);
	237	unsigned int hashval = hash_superfast(key, keylen);
82fc7d98	238	unsigned int pos = hashval & (hash->n_buckets - 1);
822913d7 LDM	239	const struct hash_bucket *bucket = hash->buckets + pos;
822913d7 LDM	240	const struct hash_entry se = {
7db08652 GSB	241	.key = key,
	242	.value = NULL
	243	};
822913d7	244	const struct hash_entry *entry = bsearch(
7db08652	245	&se, bucket->entries, bucket->used,
822913d7	246	sizeof(struct hash_entry), hash_entry_cmp);
7db08652 GSB	247	if (entry == NULL)
	248	return NULL;
	249	return (void *)entry->value;
	250	}
	251
822913d7	252	int hash_del(struct hash hash, const char key)
7db08652 GSB	253	{
	254	unsigned int keylen = strlen(key);
	255	unsigned int hashval = hash_superfast(key, keylen);
82fc7d98	256	unsigned int pos = hashval & (hash->n_buckets - 1);
7db08652	257	unsigned int steps_used, steps_total;
822913d7 LDM	258	struct hash_bucket *bucket = hash->buckets + pos;
	259	struct hash_entry entry, entry_end;
	260	const struct hash_entry se = {
7db08652 GSB	261	.key = key,
	262	.value = NULL
	263	};
	264
	265	entry = bsearch(&se, bucket->entries, bucket->used,
822913d7	266	sizeof(struct hash_entry), hash_entry_cmp);
7db08652 GSB	267	if (entry == NULL)
	268	return -ENOENT;
	269
1faec2c1 LP	270	if (hash->free_value)
	271	hash->free_value((void *)entry->value);
	272
7db08652 GSB	273	entry_end = bucket->entries + bucket->used;
7db08652 GSB	274	memmove(entry, entry + 1,
822913d7	275	(entry_end - entry) * sizeof(struct hash_entry));
7db08652 GSB	276
	277	bucket->used--;
	278	hash->count--;
	279
	280	steps_used = bucket->used / hash->step;
	281	steps_total = bucket->total / hash->step;
	282	if (steps_used + 1 < steps_total) {
	283	size_t size = (steps_used + 1) *
822913d7 LDM	284	hash->step * sizeof(struct hash_entry);
822913d7 LDM	285	struct hash_entry *tmp = realloc(bucket->entries, size);
7db08652 GSB	286	if (tmp) {
	287	bucket->entries = tmp;
	288	bucket->total = (steps_used + 1) * hash->step;
	289	}
	290	}
	291
	292	return 0;
	293	}
d7073807 LDM	294
	295	unsigned int hash_get_count(const struct hash *hash)
	296	{
	297	return hash->count;
	298	}
8d1278d0 LDM	299
	300	void hash_iter_init(const struct hash hash, struct hash_iter iter)
	301	{
	302	iter->hash = hash;
	303	iter->bucket = 0;
	304	iter->entry = -1;
	305	}
	306
	307	bool hash_iter_next(struct hash_iter iter, const char *key,
	308	const void **value)
	309	{
	310	const struct hash_bucket *b = iter->hash->buckets + iter->bucket;
	311	const struct hash_entry *e;
	312
	313	iter->entry++;
	314
	315	if (iter->entry >= b->used) {
	316	iter->entry = 0;
	317
	318	for (iter->bucket++; iter->bucket < iter->hash->n_buckets;
	319	iter->bucket++) {
	320	b = iter->hash->buckets + iter->bucket;
	321
	322	if (b->used > 0)
	323	break;
	324	}
	325
	326	if (iter->bucket >= iter->hash->n_buckets)
	327	return false;
	328	}
	329
	330	e = b->entries + iter->entry;
	331
	332	if (value != NULL)
	333	*value = e->value;
	334	if (key != NULL)
	335	*key = e->key;
	336
	337	return true;
	338	}