#include <KeHashTable.h>

 using namespace Knight;

 struct KeHashNode

 {

 	KeHashNode *next;

 	uint32_t key_hash;

 	const void *key;

 	void *value;

 };

 namespace Knight

 {

 	class KeHashTable

 	{

 	public:

 		KeHashNode **buckets;

 		uint32_t num_buckets;

 		uint32_t shift;

 		uint32_t num_entries;

 		KeHashGenerator key_gen;

 		KeHashMarshal key_m;

 		KeHashMarshal val_m;

 		ke_allocator_t *node_alloc;

 		size_t key_offs;

 		size_t val_offs;

 		size_t node_size;

 		uint32_t grow_limit;

 		KeHashNode *free_list;

 		bool keep_free_list;

 	};

 }

 void *ke_DefHashMalloc(ke_allocator_t *alloc, size_t amt)

 {

 	return malloc(amt);

 }

 void ke_DefHashFree(ke_allocator_t *alloc, void *addr)

 {

 	free(addr);

 }

 ke_allocator_t s_DefHashAllocator = 

 {

 	ke_DefHashMalloc,

 	ke_DefHashFree,

 	NULL

 };

 KeHashTable *Knight::KE_CreateHashTable(

 	uint32_t bits,

 	KeHashGenerator key_gen,

 	const KeHashMarshal *key_marshal,

 	const KeHashMarshal *val_marshal,

 	ke_allocator_t *nodeAlloc,

 	bool keep_free_list)

 {

 	KeHashTable *table;

 	if (bits >= 27)

 	{

 		bits = 26;

 	}

 	else if (bits < 4)

 	{

 		bits = 4;

 	}

 	/* Validate marshals. */

 	if ((key_marshal->bytes != 0

 		 && key_marshal->ctor == NULL)

 		|| (val_marshal->bytes != 0

 			&& val_marshal->ctor == NULL))

 	{

 		return NULL;

 	}

 	table = new KeHashTable;

 	table->key_gen = key_gen;

 	table->key_m = *key_marshal;

 	table->val_m = *val_marshal;

 	table->num_entries = 0;

 	table->shift = bits;

 	table->node_alloc = nodeAlloc == NULL ? &s_DefHashAllocator : nodeAlloc;

 	table->num_buckets = (1 << bits);

 	table->grow_limit = (uint32_t)(0.9f * table->num_buckets);

 	table->keep_free_list = keep_free_list;

 	table->free_list = NULL;

 	table->buckets = (KeHashNode **)malloc(sizeof(KeHashNode *) * table->num_buckets);

 	memset(table->buckets, 0, sizeof(KeHashNode *) * table->num_buckets);

 	table->key_offs = sizeof(KeHashNode);

 	if (table->key_m.bytes != 0 && table->key_m.bytes % 8 != 0)

 	{

 		table->key_m.bytes += 8;

 		table->key_m.bytes -= (table->key_m.bytes % 8);

 	}

 	table->val_offs = table->key_offs + table->key_m.bytes;

 	table->node_size = table->val_offs + table->val_m.bytes;

 	return table;

 }

 #define KE_GET_BUCKET(tbl, hsh) (&(tbl)->buckets[((hsh) * 0x9E3779B9) >> (tbl)->shift])

 KeHashNode **ke_HashInternalFind(KeHashTable *table, uint32_t key_hash, const void *key)

 {

 	KeHashNode *node;

 	KeHashNode **bucket;

 	bucket = KE_GET_BUCKET(table, key_hash);

 	/* :TODO: move to the front once found? */

 	while ((node = *bucket) != NULL)

 	{

 		if (node->key_hash == key_hash

 			&& ((table->key_m.cmp != NULL && table->key_m.cmp(node->key, key))

 				 || node->key == key))

 		{

 			return bucket;

 		}

 		bucket = &node->next;

 	}

 	return bucket;

 }

 void ke_ResizeHashTable(KeHashTable *table, uint32_t new_shift)

 {

 	uint32_t entries;

 	KeHashNode *next;

 	KeHashNode *node;

 	KeHashNode **rbucket;

 	KeHashNode **old_buckets;

 	uint32_t old_num_buckets;

 	/* Save old data */

 	old_num_buckets = table->num_buckets;

 	old_buckets = table->buckets;

 	entries = table->num_entries;

 	/* Save new data */

 	table->num_buckets = (1 << new_shift);

 	table->shift = new_shift;

 	table->grow_limit = (uint32_t)(0.9f * table->num_buckets);

 	table->buckets = (KeHashNode **)malloc(sizeof(KeHashNode *) * table->num_buckets);

 	memset(table->buckets, 0, sizeof(KeHashNode *) * table->num_buckets);

 	/* For each old bucket... */

 	for (uint32_t i = 0;

 		 i < old_num_buckets && entries != 0;

 		 i++)

 	{

 		node = old_buckets[i];

 		/* Get each item in its list... */

 		while (node != NULL)

 		{

 			next = node->next;

 			/* Find the new replacement bucket it needs to go in. */

 			rbucket = KE_GET_BUCKET(table, node->key_hash);

 			/* Link this node to the next node in the new bucket. */

 			if (*rbucket == NULL)

 			{

 				node->next = NULL;

 			}

 			else

 			{

 				node->next = *rbucket;

 			}

 			/* Add us to the front of that bucket's list. */

 			*rbucket = node;

 			node = next;

 		}

 	}

 	free(old_buckets);

 }

 void Knight::KE_AddToHashTable(KeHashTable *table, const void *key, void *val)

 {

 	KeHashNode *node;

 	uint32_t key_hash;

 	KeHashNode **bucket;

 	key_hash = table->key_gen(key);

 	bucket = ke_HashInternalFind(table, key_hash, key);

 	if ((node = *bucket) != NULL)

 	{

 		/* Already in the table */

 		if ((table->val_m.cmp != NULL && table->val_m.cmp(node->value, val))

 			 || node->value == val)

 		{

 			return;

 		}

 		/* Destroy old value if it's set. */

 		if (node->value != NULL && table->val_m.dtor != NULL)

 		{

 			table->val_m.dtor(node->value);

 		}

 		/* Construct or set the new value. */

 		if (table->val_m.bytes != 0)

 		{

 			table->val_m.ctor(node->value, val);

 		}

 		else

 		{

 			node->value = val;

 		}

 		return;

 	}

 	/* If we're overloaded, we may need to resize. 

 	 * Right now, we do this if we hit a .9 entry:buckets ratio.

 	 */

 	if (table->num_entries >= table->grow_limit)

 	{

 		ke_ResizeHashTable(table, table->shift << 1);

 		bucket = ke_HashInternalFind(table, key_hash, key);

 	}

 	if (table->free_list != NULL)

 	{

 		node = table->free_list;

 		table->free_list = node->next;

 	}

 	else

 	{

 		node = (KeHashNode *)table->node_alloc->alloc(table->node_alloc, table->node_size);

 	}

 	if (table->key_m.bytes == 0)

 	{

 		node->key = key;

 	}

 	else

 	{

 		node->key = (char *)node + table->key_offs;

 		table->key_m.ctor((void *)node->key, key);

 	}

 	if (table->val_m.bytes == 0)

 	{

 		node->value = val;

 	}

 	else

 	{

 		node->value = (char *)node + table->val_offs;

 		table->val_m.ctor(node->value, val);

 	}

 	node->next = *bucket;

 	node->key_hash = key_hash;

 	*bucket = node;

 }

 inline void ke_CleanUpHashNode(KeHashTable *table, KeHashNode *node)

 {

 	/* Destroy old value if it's set. */

 	if (node->value != NULL && table->val_m.dtor != NULL)

 	{

 		table->val_m.dtor(node->value);

 	}

 	/* Destroy the key. */

 	if (table->key_m.dtor != NULL)

 	{

 		table->key_m.dtor(node->key);

 	}

 	/* Deallocate us as appropriate. */

 	if (table->keep_free_list)

 	{

 		node->next = table->free_list;

 		table->free_list = node;

 	}

 	else

 	{

 		table->node_alloc->dealloc(table->node_alloc, node);

 	}

 }

 void Knight::KE_RemoveFromHashTable(KeHashTable *table, const void *key)

 {

 	KeHashNode *node;

 	uint32_t key_hash;

 	KeHashNode **bucket;

 	key_hash = table->key_gen(key);

 	bucket = ke_HashInternalFind(table, key_hash, key);

 	if ((node = *bucket) == NULL)

 	{

 		return;

 	}

 	/* Link the bucket to its next (removing us). */

 	*bucket = node->next;

 	ke_CleanUpHashNode(table, node);

 }

 bool Knight::KE_FindInHashTable(KeHashTable *table, const void *key, void **value)

 {

 	KeHashNode *node;

 	uint32_t key_hash;

 	KeHashNode **bucket;

 	key_hash = table->key_gen(key);

 	bucket = ke_HashInternalFind(table, key_hash, key);

 	if ((node = *bucket) == NULL)

 	{

 		return false;

 	}

 	if (value != NULL)

 	{

 		*value = node->value;

 	}

 	return true;

 }

 void Knight::KE_DestroyHashTable(KeHashTable *table)

 {

 	KeHashNode *node, *next;

 	/* Turn off this caching! */

 	table->keep_free_list = false;

 	/* Find entries in buckets that need to be freed. */

 	for (uint32_t i = 0; i < table->num_buckets; i++)

 	{

 		node = table->buckets[i];

 		while (node != NULL)

 		{

 			next = node->next;

 			ke_CleanUpHashNode(table, node);

 			node = next;

 		}

 	}

 	/* Free the free list */

 	while (table->free_list != NULL)

 	{

 		next = table->free_list->next;

 		ke_CleanUpHashNode(table, table->free_list);

 		table->free_list = next;

 	}

 	/* Destroy everything now. */

 	free(table->buckets);

 	delete table;

 }

 void Knight::KE_ClearHashTable(KeHashTable *table)

 {

 	KeHashNode *node, *next;

 	/* Free every entry in the table. */

 	for (uint32_t i = 0; i < table->num_buckets; i++)

 	{

 		node = table->buckets[i];

 		while (node != NULL)

 		{

 			next = node->next;

 			ke_CleanUpHashNode(table, node);

 			node = next;

 		}

 	}

 }

 #if defined _MSC_VER && (defined _M_IX86 || defined _M_AMD64 || defined _M_X64)

 #pragma intrinsic(_rotl)

 #endif

 uint32_t Knight::KE_HashString(const void *str)

 {

 	uint32_t h;

 	const unsigned char *us;

 	h = 0;

 	for (us = (const unsigned char *)str; *us != 0; us++)

 	{

 #if defined _MSC_VER && (defined _M_IX86 || defined _M_AMD64 || defined _M_X64)

 		h = _rotl(h, 4) ^ *us;

 #else

 		h = ((h << 4) | (h >> 28)) ^ *us;

 #endif

 	}

 	return h;

 }