[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-private.h"

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

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

struct kmod_hash_bucket {
	struct kmod_hash_entry *entries;
	unsigned int used;
	unsigned int total;
};

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

struct kmod_hash *kmod_hash_new(unsigned int n_buckets,
					void (*free_value)(void *value))
{
	struct kmod_hash *hash = calloc(1, sizeof(struct kmod_hash) +
				n_buckets * sizeof(struct kmod_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 kmod_hash_free(struct kmod_hash *hash)
{
	struct kmod_hash_bucket *bucket, *bucket_end;
	bucket = hash->buckets;
	bucket_end = bucket + hash->n_buckets;
	for (; bucket < bucket_end; bucket++) {
		if (hash->free_value) {
			struct kmod_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 kmod_hash_add(struct kmod_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 kmod_hash_bucket *bucket = hash->buckets + pos;
	struct kmod_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 kmod_hash_entry);
		struct kmod_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 kmod_hash_entry));
			break;
		}
	}

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

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

void *kmod_hash_find(const struct kmod_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 kmod_hash_bucket *bucket = hash->buckets + pos;
	const struct kmod_hash_entry se = {
		.key = key,
		.value = NULL
	};
	const struct kmod_hash_entry *entry = bsearch(
		&se, bucket->entries, bucket->used,
		sizeof(struct kmod_hash_entry), kmod_hash_entry_cmp);
	if (entry == NULL)
		return NULL;
	return (void *)entry->value;
}

int kmod_hash_del(struct kmod_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 kmod_hash_bucket *bucket = hash->buckets + pos;
	struct kmod_hash_entry *entry, *entry_end;
	const struct kmod_hash_entry se = {
		.key = key,
		.value = NULL
	};

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

	entry_end = bucket->entries + bucket->used;
	memmove(entry, entry + 1,
		(entry_end - entry) * sizeof(struct kmod_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 kmod_hash_entry);
		struct kmod_hash_entry *tmp = realloc(bucket->entries, size);
		if (tmp) {
			bucket->entries = tmp;
			bucket->total = (steps_used + 1) * hash->step;
		}
	}

	return 0;
}
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"
	22	#include "libkmod-private.h"
	23
	24	#include <stdlib.h>
	25	#include <string.h>
	26	#include <errno.h>
	27
	28	struct kmod_hash_entry {
	29	const char *key;
	30	const void *value;
	31	};
	32
	33	struct kmod_hash_bucket {
	34	struct kmod_hash_entry *entries;
	35	unsigned int used;
	36	unsigned int total;
	37	};
	38
	39	struct kmod_hash {
	40	unsigned int count;
	41	unsigned int step;
	42	unsigned int n_buckets;
	43	void (free_value)(void value);
	44	struct kmod_hash_bucket buckets[];
	45	};
	46
c35347f1 LDM	47	struct kmod_hash *kmod_hash_new(unsigned int n_buckets,
c35347f1 LDM	48	void (free_value)(void value))
7db08652 GSB	49	{
	50	struct kmod_hash *hash = calloc(1, sizeof(struct kmod_hash) +
	51	n_buckets * sizeof(struct kmod_hash_bucket));
	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
	64	void kmod_hash_free(struct kmod_hash *hash)
	65	{
	66	struct kmod_hash_bucket bucket, bucket_end;
	67	bucket = hash->buckets;
	68	bucket_end = bucket + hash->n_buckets;
	69	for (; bucket < bucket_end; bucket++) {
	70	if (hash->free_value) {
	71	struct kmod_hash_entry entry, entry_end;
	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	*/
140	int kmod_hash_add(struct kmod_hash hash, const char key, const void *value)
141	{
142	unsigned int keylen = strlen(key);
143	unsigned int hashval = hash_superfast(key, keylen);
144	unsigned int pos = hashval % hash->n_buckets;
145	struct kmod_hash_bucket *bucket = hash->buckets + pos;
146	struct kmod_hash_entry entry, entry_end;
147
148	if (bucket->used + 1 >= bucket->total) {
149	unsigned new_total = bucket->total + hash->step;
150	size_t size = new_total * sizeof(struct kmod_hash_entry);
151	struct kmod_hash_entry *tmp = realloc(bucket->entries, size);
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,
168	(entry_end - entry) * sizeof(struct kmod_hash_entry));
169	break;
170	}
171	}
172
173	entry->key = key;
174	entry->value = value;
175	bucket->used++;
176	hash->count++;
177	return 0;
178	}
179
180	static int kmod_hash_entry_cmp(const void pa, const void pb)
181	{
182	const struct kmod_hash_entry *a = pa;
183	const struct kmod_hash_entry *b = pb;
184	return strcmp(a->key, b->key);
185	}
186
187	void kmod_hash_find(const struct kmod_hash hash, const char *key)
188	{
189	unsigned int keylen = strlen(key);
190	unsigned int hashval = hash_superfast(key, keylen);
191	unsigned int pos = hashval % hash->n_buckets;
192	const struct kmod_hash_bucket *bucket = hash->buckets + pos;
193	const struct kmod_hash_entry se = {
194	.key = key,
195	.value = NULL
196	};
197	const struct kmod_hash_entry *entry = bsearch(
198	&se, bucket->entries, bucket->used,
199	sizeof(struct kmod_hash_entry), kmod_hash_entry_cmp);
200	if (entry == NULL)
201	return NULL;
202	return (void *)entry->value;
203	}
204
205	int kmod_hash_del(struct kmod_hash hash, const char key)
206	{
207	unsigned int keylen = strlen(key);
208	unsigned int hashval = hash_superfast(key, keylen);
209	unsigned int pos = hashval % hash->n_buckets;
210	unsigned int steps_used, steps_total;
211	struct kmod_hash_bucket *bucket = hash->buckets + pos;
212	struct kmod_hash_entry entry, entry_end;
213	const struct kmod_hash_entry se = {
214	.key = key,
215	.value = NULL
216	};
217
218	entry = bsearch(&se, bucket->entries, bucket->used,
219	sizeof(struct kmod_hash_entry), kmod_hash_entry_cmp);
220	if (entry == NULL)
221	return -ENOENT;
222
223	entry_end = bucket->entries + bucket->used;
224	memmove(entry, entry + 1,
225	(entry_end - entry) * sizeof(struct kmod_hash_entry));
226
227	bucket->used--;
228	hash->count--;
229
230	steps_used = bucket->used / hash->step;
231	steps_total = bucket->total / hash->step;
232	if (steps_used + 1 < steps_total) {
233	size_t size = (steps_used + 1) *
234	hash->step * sizeof(struct kmod_hash_entry);
235	struct kmod_hash_entry *tmp = realloc(bucket->entries, size);
236	if (tmp) {
237	bucket->entries = tmp;
238	bucket->total = (steps_used + 1) * hash->step;
239	}
240	}
241
242	return 0;
243	}