[thirdparty/kmod.git] / libkmod / libkmod-hash.c

/*
 * libkmod - interface to kernel module operations
 *
 * Copyright (C) 2011  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, write to the Free Software
 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
 */

#include "libkmod.h"
#include "libkmod-hash.h"

#include <stdlib.h>
#include <string.h>
#include <errno.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 = 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;
	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;
	const unsigned short *itr = (const unsigned short *)key;

	len /= 4;

	/* Main loop */
	for (; len > 0; len--) {
		hash += itr[0];
		tmp = (itr[1] << 11) ^ hash;
		hash = (hash << 16) ^ tmp;
		itr += 2;
		hash += hash >> 11;
	}

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

	case 2:
		hash += *itr;
		hash ^= hash << 11;
		hash += hash >> 17;
		break;

	case 1:
		hash += *(const char *)itr;
		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;
	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) {
			hash->free_value((void *)entry->value);
			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;
	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;
	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;
	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;

	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	*
	4	* Copyright (C) 2011 ProFUSION embedded systems
	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
	17	* License along with this library; if not, write to the Free Software
	18	* Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
	19	*/
	20
	21	#include "libkmod.h"
529148ea	22	#include "libkmod-hash.h"
7db08652 GSB	23
	24	#include <stdlib.h>
	25	#include <string.h>
	26	#include <errno.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	{
822913d7 LDM	50	struct hash *hash = calloc(1, sizeof(struct hash) +
822913d7 LDM	51	n_buckets * sizeof(struct hash_bucket));
7db08652 GSB	52	if (hash == NULL)
	53	return NULL;
	54	hash->n_buckets = n_buckets;
	55	hash->free_value = free_value;
	56	hash->step = n_buckets / 32;
	57	if (hash->step == 0)
	58	hash->step = 4;
	59	else if (hash->step > 64)
	60	hash->step = 64;
	61	return hash;
	62	}
	63
822913d7	64	void hash_free(struct hash *hash)
7db08652	65	{
822913d7	66	struct hash_bucket bucket, bucket_end;
7db08652 GSB	67	bucket = hash->buckets;
	68	bucket_end = bucket + hash->n_buckets;
	69	for (; bucket < bucket_end; bucket++) {
	70	if (hash->free_value) {
822913d7	71	struct hash_entry entry, entry_end;
7db08652 GSB	72	entry = bucket->entries;
	73	entry_end = entry + bucket->used;
	74	for (; entry < entry_end; entry++)
	75	hash->free_value((void *)entry->value);
	76	}
	77	free(bucket->entries);
	78	}
	79	free(hash);
	80	}
	81
	82	static inline unsigned int hash_superfast(const char *key, unsigned int len)
	83	{
	84	/* Paul Hsieh (http://www.azillionmonkeys.com/qed/hash.html)
	85	* used by WebCore (http://webkit.org/blog/8/hashtables-part-2/)
	86	* EFL's eina and possible others.
	87	*/
	88	unsigned int tmp, hash = len, rem = len & 3;
	89	const unsigned short itr = (const unsigned short )key;
	90
	91	len /= 4;
	92
	93	/* Main loop */
	94	for (; len > 0; len--) {
	95	hash += itr[0];
	96	tmp = (itr[1] << 11) ^ hash;
	97	hash = (hash << 16) ^ tmp;
	98	itr += 2;
	99	hash += hash >> 11;
	100	}
	101
	102	/* Handle end cases */
	103	switch (rem) {
	104	case 3:
	105	hash += *itr;
	106	hash ^= hash << 16;
	107	hash ^= key[2] << 18;
	108	hash += hash >> 11;
	109	break;
	110
	111	case 2:
	112	hash += *itr;
	113	hash ^= hash << 11;
	114	hash += hash >> 17;
	115	break;
	116
	117	case 1:
	118	hash += (const char )itr;
	119	hash ^= hash << 10;
	120	hash += hash >> 1;
	121	}
	122
	123	/* Force "avalanching" of final 127 bits */
	124	hash ^= hash << 3;
	125	hash += hash >> 5;
	126	hash ^= hash << 4;
	127	hash += hash >> 17;
	128	hash ^= hash << 25;
	129	hash += hash >> 6;
	130
	131	return hash;
	132	}
	133
	134	/*
	135	* add or replace key in hash map.
136	*
137	* none of key or value are copied, just references are remembered as is,
138	* make sure they are live while pair exists in hash!
139	*/
822913d7	140	int hash_add(struct hash hash, const char key, const void *value)
7db08652 GSB	141	{
	142	unsigned int keylen = strlen(key);
	143	unsigned int hashval = hash_superfast(key, keylen);
	144	unsigned int pos = hashval % hash->n_buckets;
822913d7 LDM	145	struct hash_bucket *bucket = hash->buckets + pos;
822913d7 LDM	146	struct hash_entry entry, entry_end;
7db08652 GSB	147
	148	if (bucket->used + 1 >= bucket->total) {
	149	unsigned new_total = bucket->total + hash->step;
822913d7 LDM	150	size_t size = new_total * sizeof(struct hash_entry);
822913d7 LDM	151	struct hash_entry *tmp = realloc(bucket->entries, size);
7db08652 GSB	152	if (tmp == NULL)
	153	return -errno;
	154	bucket->entries = tmp;
	155	bucket->total = new_total;
	156	}
	157
	158	entry = bucket->entries;
	159	entry_end = entry + bucket->used;
	160	for (; entry < entry_end; entry++) {
	161	int c = strcmp(key, entry->key);
	162	if (c == 0) {
	163	hash->free_value((void *)entry->value);
	164	entry->value = value;
	165	return 0;
	166	} else if (c < 0) {
	167	memmove(entry + 1, entry,
822913d7	168	(entry_end - entry) * sizeof(struct hash_entry));
7db08652 GSB	169	break;
	170	}
	171	}
	172
	173	entry->key = key;
	174	entry->value = value;
	175	bucket->used++;
	176	hash->count++;
	177	return 0;
	178	}
	179
d7073807 LDM	180	/* similar to hash_add(), but fails if key already exists */
	181	int hash_add_unique(struct hash hash, const char key, const void *value)
	182	{
	183	unsigned int keylen = strlen(key);
	184	unsigned int hashval = hash_superfast(key, keylen);
	185	unsigned int pos = hashval % hash->n_buckets;
	186	struct hash_bucket *bucket = hash->buckets + pos;
	187	struct hash_entry entry, entry_end;
	188
	189	if (bucket->used + 1 >= bucket->total) {
	190	unsigned new_total = bucket->total + hash->step;
	191	size_t size = new_total * sizeof(struct hash_entry);
	192	struct hash_entry *tmp = realloc(bucket->entries, size);
	193	if (tmp == NULL)
	194	return -errno;
	195	bucket->entries = tmp;
	196	bucket->total = new_total;
	197	}
	198
	199	entry = bucket->entries;
	200	entry_end = entry + bucket->used;
	201	for (; entry < entry_end; entry++) {
	202	int c = strcmp(key, entry->key);
	203	if (c == 0)
	204	return -EEXIST;
	205	else if (c < 0) {
	206	memmove(entry + 1, entry,
	207	(entry_end - entry) * sizeof(struct hash_entry));
	208	break;
	209	}
	210	}
	211
	212	entry->key = key;
	213	entry->value = value;
	214	bucket->used++;
	215	hash->count++;
	216	return 0;
	217	}
	218
822913d7	219	static int hash_entry_cmp(const void pa, const void pb)
7db08652	220	{
822913d7 LDM	221	const struct hash_entry *a = pa;
822913d7 LDM	222	const struct hash_entry *b = pb;
7db08652 GSB	223	return strcmp(a->key, b->key);
	224	}
	225
822913d7	226	void hash_find(const struct hash hash, const char *key)
7db08652 GSB	227	{
	228	unsigned int keylen = strlen(key);
	229	unsigned int hashval = hash_superfast(key, keylen);
	230	unsigned int pos = hashval % hash->n_buckets;
822913d7 LDM	231	const struct hash_bucket *bucket = hash->buckets + pos;
822913d7 LDM	232	const struct hash_entry se = {
7db08652 GSB	233	.key = key,
	234	.value = NULL
	235	};
822913d7	236	const struct hash_entry *entry = bsearch(
7db08652	237	&se, bucket->entries, bucket->used,
822913d7	238	sizeof(struct hash_entry), hash_entry_cmp);
7db08652 GSB	239	if (entry == NULL)
	240	return NULL;
	241	return (void *)entry->value;
	242	}
	243
822913d7	244	int hash_del(struct hash hash, const char key)
7db08652 GSB	245	{
	246	unsigned int keylen = strlen(key);
	247	unsigned int hashval = hash_superfast(key, keylen);
	248	unsigned int pos = hashval % hash->n_buckets;
	249	unsigned int steps_used, steps_total;
822913d7 LDM	250	struct hash_bucket *bucket = hash->buckets + pos;
	251	struct hash_entry entry, entry_end;
	252	const struct hash_entry se = {
7db08652 GSB	253	.key = key,
	254	.value = NULL
	255	};
	256
	257	entry = bsearch(&se, bucket->entries, bucket->used,
822913d7	258	sizeof(struct hash_entry), hash_entry_cmp);
7db08652 GSB	259	if (entry == NULL)
	260	return -ENOENT;
	261
	262	entry_end = bucket->entries + bucket->used;
	263	memmove(entry, entry + 1,
822913d7	264	(entry_end - entry) * sizeof(struct hash_entry));
7db08652 GSB	265
	266	bucket->used--;
	267	hash->count--;
	268
	269	steps_used = bucket->used / hash->step;
	270	steps_total = bucket->total / hash->step;
	271	if (steps_used + 1 < steps_total) {
	272	size_t size = (steps_used + 1) *
822913d7 LDM	273	hash->step * sizeof(struct hash_entry);
822913d7 LDM	274	struct hash_entry *tmp = realloc(bucket->entries, size);
7db08652 GSB	275	if (tmp) {
	276	bucket->entries = tmp;
	277	bucket->total = (steps_used + 1) * hash->step;
	278	}
	279	}
	280
	281	return 0;
	282	}
d7073807 LDM	283
	284	unsigned int hash_get_count(const struct hash *hash)
	285	{
	286	return hash->count;
	287	}
8d1278d0 LDM	288
	289	void hash_iter_init(const struct hash hash, struct hash_iter iter)
	290	{
	291	iter->hash = hash;
	292	iter->bucket = 0;
	293	iter->entry = -1;
	294	}
	295
	296	bool hash_iter_next(struct hash_iter iter, const char *key,
	297	const void **value)
	298	{
	299	const struct hash_bucket *b = iter->hash->buckets + iter->bucket;
	300	const struct hash_entry *e;
	301
	302	iter->entry++;
	303
	304	if (iter->entry >= b->used) {
	305	iter->entry = 0;
	306
	307	for (iter->bucket++; iter->bucket < iter->hash->n_buckets;
	308	iter->bucket++) {
	309	b = iter->hash->buckets + iter->bucket;
	310
	311	if (b->used > 0)
	312	break;
	313	}
	314
	315	if (iter->bucket >= iter->hash->n_buckets)
	316	return false;
	317	}
	318
	319	e = b->entries + iter->entry;
	320
	321	if (value != NULL)
	322	*value = e->value;
	323	if (key != NULL)
	324	*key = e->key;
	325
	326	return true;
	327	}