Move hash implementation to shared directory

5 files changed, 1 insertions, 367 deletions

diff --git a/libkmod/docs/Makefile.am b/libkmod/docs/Makefile.am
index 1fd6b90..cd3bb16 100644
--- a/libkmod/docs/Makefile.am
+++ b/libkmod/docs/Makefile.am
@@ -22,7 +22,6 @@ CFILE_GLOB = $(top_srcdir)/libkmod/libkmod.c $(top_srcdir)/libkmod/libkmod-modul
 
 IGNORE_HFILES = libkmod-internal.h \
 		libkmod-util.h \
-		libkmod-hash.h \
 		libkmod-index.h
 
 content_files = version.xml
diff --git a/libkmod/libkmod-hash.c b/libkmod/libkmod-hash.c
deleted file mode 100644
index 9b4d1f1..0000000
--- a/libkmod/libkmod-hash.c
+++ /dev/null
@@ -1,341 +0,0 @@
-/*
- * 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, write to the Free Software
- * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
- */
-
-#include <shared/util.h>
-
-#include "libkmod.h"
-#include "libkmod-hash.h"
-
-#include "libkmod-util.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;
-
-	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;
-}
diff --git a/libkmod/libkmod-hash.h b/libkmod/libkmod-hash.h
deleted file mode 100644
index ca0af05..0000000
--- a/libkmod/libkmod-hash.h
+++ /dev/null
@@ -1,22 +0,0 @@
-#pragma once
-
-#include <stdbool.h>
-
-struct hash;
-
-struct hash_iter {
-	const struct hash *hash;
-	unsigned int bucket;
-	unsigned int entry;
-};
-
-struct hash *hash_new(unsigned int n_buckets, void (*free_value)(void *value));
-void hash_free(struct hash *hash);
-int hash_add(struct hash *hash, const char *key, const void *value);
-int hash_add_unique(struct hash *hash, const char *key, const void *value);
-int hash_del(struct hash *hash, const char *key);
-void *hash_find(const struct hash *hash, const char *key);
-unsigned int hash_get_count(const struct hash *hash);
-void hash_iter_init(const struct hash *hash, struct hash_iter *iter);
-bool hash_iter_next(struct hash_iter *iter, const char **key,
-							const void **value);
diff --git a/libkmod/libkmod-internal.h b/libkmod/libkmod-internal.h
index 79f1a13..83a5bc2 100644
--- a/libkmod/libkmod-internal.h
+++ b/libkmod/libkmod-internal.h
@@ -146,9 +146,6 @@ void kmod_module_set_visited(struct kmod_module *mod, bool visited) __attribute_
 void kmod_module_set_builtin(struct kmod_module *mod, bool builtin) __attribute__((nonnull((1))));
 void kmod_module_set_required(struct kmod_module *mod, bool required) __attribute__((nonnull(1)));
 
-/* libkmod-hash.c */
-
-#include "libkmod-hash.h"
 
 /* libkmod-file.c */
 struct kmod_file *kmod_file_open(const struct kmod_ctx *ctx, const char *filename) _must_check_ __attribute__((nonnull(1,2)));
diff --git a/libkmod/libkmod.c b/libkmod/libkmod.c
index 89d70c3..3dc5a2b 100644
--- a/libkmod/libkmod.c
+++ b/libkmod/libkmod.c
@@ -32,6 +32,7 @@
 #include <sys/utsname.h>
 #include <sys/stat.h>
 
+#include <shared/hash.h>
 #include <shared/util.h>
 
 #include "libkmod.h"