/*

 * Borrowed from 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 "hash.h"

/* endianess and alignments                                                 */

/* taken from kmod shared/util.h                                            */

/* ************************************************************************ */

#define get_unaligned(ptr)			\

({						\

	struct __attribute__((packed)) {	\

		typeof(*(ptr)) __v;		\

	} *__p = (typeof(__p)) (ptr);		\

	__p->__v;				\

})

#define put_unaligned(val, ptr)			\

do {						\

	struct __attribute__((packed)) {	\

		typeof(*(ptr)) __v;		\

	} *__p = (typeof(__p)) (ptr);		\

	__p->__v = (val);			\

} while (0)

static inline unsigned int ALIGN_POWER2(unsigned int u)

{

	return 1 << ((sizeof(u) * 8) - __builtin_clz(u - 1));

}

static inline size_t min(size_t a, size_t b)

{

	return a < b ? a : b;

}

struct hash_entry {

	const char *key;

	size_t keylen;

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

};

static inline int hash_key_cmp(const char *key1, size_t size1,

			       const char *key2, size_t size2)

{

	int rc;

	size_t size;

	size = min(size1, size2);

	rc = memcmp(key1, key2, size);

	if (rc != 0)

		return rc;

	return (int)(size1 - size2);

}

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_bin(struct hash *hash,

		 const char *key, size_t keylen, const void *value)

{

	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 = hash_key_cmp(key, keylen, entry->key, entry->keylen);

		if (c == 0) {

			if (hash->free_value)

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

			entry->key = key;

			entry->keylen = keylen;

			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->keylen = keylen;

	entry->value = value;

	bucket->used++;

	hash->count++;

	return 0;

}

/* similar to hash_add(), but fails if key already exists */

int hash_add_unique_bin(struct hash *hash,

			const char *key, size_t keylen, const void *value)

{

	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 = hash_key_cmp(key, keylen, entry->key, entry->keylen);

		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->keylen = keylen;

	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 hash_key_cmp(a->key, a->keylen, b->key, b->keylen);

}

void *hash_find_bin(const struct hash *hash, const char *key, size_t keylen)

{

	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,

		.keylen = keylen,

		.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_bin(struct hash *hash, const char *key, size_t keylen)

{

	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,

		.keylen = keylen,

		.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_bin(struct hash_iter *iter, const char **key,

			size_t *keylen,

			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;

	if (keylen != NULL)

		*keylen = e->keylen;

	return true;

}