dvander@2541: #include <string.h>
dvander@2226: #include <KeHashTable.h>
dvander@2226: 
dvander@2226: using namespace Knight;
dvander@2226: 
dvander@2226: struct KeHashNode
dvander@2226: {
dvander@2226: 	KeHashNode *next;
dvander@2226: 	uint32_t key_hash;
dvander@2226: 	const void *key;
dvander@2226: 	void *value;
dvander@2226: };
dvander@2226: 
dvander@2226: namespace Knight
dvander@2226: {
dvander@2226: 	class KeHashTable
dvander@2226: 	{
dvander@2226: 	public:
dvander@2226: 		KeHashNode **buckets;
dvander@2226: 		uint32_t num_buckets;
dvander@2226: 		uint32_t shift;
dvander@2226: 		uint32_t num_entries;
dvander@2226: 		KeHashGenerator key_gen;
dvander@2226: 		KeHashMarshal key_m;
dvander@2226: 		KeHashMarshal val_m;
dvander@2226: 		ke_allocator_t *node_alloc;
dvander@2226: 		size_t key_offs;
dvander@2226: 		size_t val_offs;
dvander@2226: 		size_t node_size;
dvander@2226: 		uint32_t grow_limit;
dvander@2226: 		KeHashNode *free_list;
dvander@2226: 		bool keep_free_list;
dvander@2226: 	};
dvander@2226: }
dvander@2226: 
dvander@2226: void *ke_DefHashMalloc(ke_allocator_t *alloc, size_t amt)
dvander@2226: {
dvander@2226: 	return malloc(amt);
dvander@2226: }
dvander@2226: 
dvander@2226: void ke_DefHashFree(ke_allocator_t *alloc, void *addr)
dvander@2226: {
dvander@2226: 	free(addr);
dvander@2226: }
dvander@2226: 
dvander@2226: ke_allocator_t s_DefHashAllocator = 
dvander@2226: {
dvander@2226: 	ke_DefHashMalloc,
dvander@2226: 	ke_DefHashFree,
dvander@2226: 	NULL
dvander@2226: };
dvander@2226: 
dvander@2226: KeHashTable *Knight::KE_CreateHashTable(
dvander@2226: 	uint32_t bits,
dvander@2226: 	KeHashGenerator key_gen,
dvander@2226: 	const KeHashMarshal *key_marshal,
dvander@2226: 	const KeHashMarshal *val_marshal,
dvander@2226: 	ke_allocator_t *nodeAlloc,
dvander@2226: 	bool keep_free_list)
dvander@2226: {
dvander@2226: 	KeHashTable *table;
dvander@2226: 
dvander@2226: 	if (bits >= 27)
dvander@2226: 	{
dvander@2226: 		bits = 26;
dvander@2226: 	}
dvander@2226: 	else if (bits < 4)
dvander@2226: 	{
dvander@2226: 		bits = 4;
dvander@2226: 	}
dvander@2226: 
dvander@2226: 	/* Validate marshals. */
dvander@2226: 	if ((key_marshal->bytes != 0
dvander@2226: 		 && key_marshal->ctor == NULL)
dvander@2226: 		|| (val_marshal->bytes != 0
dvander@2226: 			&& val_marshal->ctor == NULL))
dvander@2226: 	{
dvander@2226: 		return NULL;
dvander@2226: 	}
dvander@2226: 
dvander@2226: 	table = new KeHashTable;
dvander@2226: 	table->key_gen = key_gen;
dvander@2226: 	table->key_m = *key_marshal;
dvander@2226: 	table->val_m = *val_marshal;
dvander@2226: 	table->num_entries = 0;
dvander@2541: 	table->shift = 32 - bits;
dvander@2226: 	table->node_alloc = nodeAlloc == NULL ? &s_DefHashAllocator : nodeAlloc;
dvander@2226: 	table->num_buckets = (1 << bits);
dvander@2226: 	table->grow_limit = (uint32_t)(0.9f * table->num_buckets);
dvander@2226: 	table->keep_free_list = keep_free_list;
dvander@2226: 	table->free_list = NULL;
dvander@2226: 	table->buckets = (KeHashNode **)malloc(sizeof(KeHashNode *) * table->num_buckets);
dvander@2226: 	memset(table->buckets, 0, sizeof(KeHashNode *) * table->num_buckets);
dvander@2226: 
dvander@2226: 	table->key_offs = sizeof(KeHashNode);
dvander@2226: 	if (table->key_m.bytes != 0 && table->key_m.bytes % 8 != 0)
dvander@2226: 	{
dvander@2226: 		table->key_m.bytes += 8;
dvander@2226: 		table->key_m.bytes -= (table->key_m.bytes % 8);
dvander@2226: 	}
dvander@2226: 	
dvander@2226: 	table->val_offs = table->key_offs + table->key_m.bytes;
dvander@2226: 	table->node_size = table->val_offs + table->val_m.bytes;
dvander@2226: 
dvander@2226: 	return table;
dvander@2226: }
dvander@2226: 
dvander@2226: #define KE_GET_BUCKET(tbl, hsh) (&(tbl)->buckets[((hsh) * 0x9E3779B9) >> (tbl)->shift])
dvander@2226: 
dvander@2226: KeHashNode **ke_HashInternalFind(KeHashTable *table, uint32_t key_hash, const void *key)
dvander@2226: {
dvander@2226: 	KeHashNode *node;
dvander@2226: 	KeHashNode **bucket;
dvander@2226: 
dvander@2226: 	bucket = KE_GET_BUCKET(table, key_hash);
dvander@2226: 
dvander@2226: 	/* :TODO: move to the front once found? */
dvander@2226: 
dvander@2226: 	while ((node = *bucket) != NULL)
dvander@2226: 	{
dvander@2226: 		if (node->key_hash == key_hash
dvander@2226: 			&& ((table->key_m.cmp != NULL && table->key_m.cmp(node->key, key))
dvander@2226: 				 || node->key == key))
dvander@2226: 		{
dvander@2226: 			return bucket;
dvander@2226: 		}
dvander@2226: 		bucket = &node->next;
dvander@2226: 	}
dvander@2226: 
dvander@2226: 	return bucket;
dvander@2226: }
dvander@2226: 
dvander@2226: void ke_ResizeHashTable(KeHashTable *table, uint32_t new_shift)
dvander@2226: {
dvander@2226: 	uint32_t entries;
dvander@2226: 	KeHashNode *next;
dvander@2226: 	KeHashNode *node;
dvander@2226: 	KeHashNode **rbucket;
dvander@2226: 	KeHashNode **old_buckets;
dvander@2226: 	uint32_t old_num_buckets;
dvander@2226: 
dvander@2226: 	/* Save old data */
dvander@2226: 	old_num_buckets = table->num_buckets;
dvander@2226: 	old_buckets = table->buckets;
dvander@2226: 	entries = table->num_entries;
dvander@2226: 
dvander@2226: 	/* Save new data */
dvander@2226: 	table->num_buckets = (1 << new_shift);
dvander@2541: 	table->shift = 32 - new_shift;
dvander@2226: 	table->grow_limit = (uint32_t)(0.9f * table->num_buckets);
dvander@2226: 
dvander@2226: 	table->buckets = (KeHashNode **)malloc(sizeof(KeHashNode *) * table->num_buckets);
dvander@2226: 	memset(table->buckets, 0, sizeof(KeHashNode *) * table->num_buckets);
dvander@2226: 
dvander@2226: 	/* For each old bucket... */
dvander@2226: 	for (uint32_t i = 0;
dvander@2226: 		 i < old_num_buckets && entries != 0;
dvander@2226: 		 i++)
dvander@2226: 	{
dvander@2226: 		node = old_buckets[i];
dvander@2226: 		/* Get each item in its list... */
dvander@2226: 		while (node != NULL)
dvander@2226: 		{
dvander@2226: 			next = node->next;
dvander@2226: 			
dvander@2226: 			/* Find the new replacement bucket it needs to go in. */
dvander@2226: 			rbucket = KE_GET_BUCKET(table, node->key_hash);
dvander@2226: 
dvander@2226: 			/* Link this node to the next node in the new bucket. */
dvander@2226: 			if (*rbucket == NULL)
dvander@2226: 			{
dvander@2226: 				node->next = NULL;
dvander@2226: 			}
dvander@2226: 			else
dvander@2226: 			{
dvander@2226: 				node->next = *rbucket;
dvander@2226: 			}
dvander@2226: 
dvander@2226: 			/* Add us to the front of that bucket's list. */
dvander@2226: 			*rbucket = node;
dvander@2226: 
dvander@2226: 			node = next;
dvander@2226: 		}
dvander@2226: 	}
dvander@2226: 
dvander@2226: 	free(old_buckets);
dvander@2226: }
dvander@2226: 
dvander@2226: void Knight::KE_AddToHashTable(KeHashTable *table, const void *key, void *val)
dvander@2226: {
dvander@2226: 	KeHashNode *node;
dvander@2226: 	uint32_t key_hash;
dvander@2226: 	KeHashNode **bucket;
dvander@2226: 
dvander@2226: 	key_hash = table->key_gen(key);
dvander@2226: 	bucket = ke_HashInternalFind(table, key_hash, key);
dvander@2226: 
dvander@2226: 	if ((node = *bucket) != NULL)
dvander@2226: 	{
dvander@2226: 		/* Already in the table */
dvander@2226: 		if ((table->val_m.cmp != NULL && table->val_m.cmp(node->value, val))
dvander@2226: 			 || node->value == val)
dvander@2226: 		{
dvander@2226: 			return;
dvander@2226: 		}
dvander@2226: 
dvander@2226: 		/* Destroy old value if it's set. */
dvander@2226: 		if (node->value != NULL && table->val_m.dtor != NULL)
dvander@2226: 		{
dvander@2226: 			table->val_m.dtor(node->value);
dvander@2226: 		}
dvander@2226: 		
dvander@2226: 		/* Construct or set the new value. */
dvander@2226: 		if (table->val_m.bytes != 0)
dvander@2226: 		{
dvander@2226: 			table->val_m.ctor(node->value, val);
dvander@2226: 		}
dvander@2226: 		else
dvander@2226: 		{
dvander@2226: 			node->value = val;
dvander@2226: 		}
dvander@2226: 
dvander@2226: 		return;
dvander@2226: 	}
dvander@2226: 
dvander@2226: 	/* If we're overloaded, we may need to resize. 
dvander@2226: 	 * Right now, we do this if we hit a .9 entry:buckets ratio.
dvander@2226: 	 */
dvander@2226: 	if (table->num_entries >= table->grow_limit)
dvander@2226: 	{
dvander@2226: 		ke_ResizeHashTable(table, table->shift << 1);
dvander@2226: 		bucket = ke_HashInternalFind(table, key_hash, key);
dvander@2226: 	}
dvander@2226: 
dvander@2226: 	if (table->free_list != NULL)
dvander@2226: 	{
dvander@2226: 		node = table->free_list;
dvander@2226: 		table->free_list = node->next;
dvander@2226: 	}
dvander@2226: 	else
dvander@2226: 	{
dvander@2226: 		node = (KeHashNode *)table->node_alloc->alloc(table->node_alloc, table->node_size);
dvander@2226: 	}
dvander@2226: 	
dvander@2226: 	if (table->key_m.bytes == 0)
dvander@2226: 	{
dvander@2226: 		node->key = key;
dvander@2226: 	}
dvander@2226: 	else
dvander@2226: 	{
dvander@2226: 		node->key = (char *)node + table->key_offs;
dvander@2226: 		table->key_m.ctor((void *)node->key, key);
dvander@2226: 	}
dvander@2226: 
dvander@2226: 	if (table->val_m.bytes == 0)
dvander@2226: 	{
dvander@2226: 		node->value = val;
dvander@2226: 	}
dvander@2226: 	else
dvander@2226: 	{
dvander@2226: 		node->value = (char *)node + table->val_offs;
dvander@2226: 		table->val_m.ctor(node->value, val);
dvander@2226: 	}
dvander@2226: 
dvander@2226: 	node->next = *bucket;
dvander@2226: 	node->key_hash = key_hash;
dvander@2226: 	*bucket = node;
dvander@2226: }
dvander@2226: 
dvander@2226: inline void ke_CleanUpHashNode(KeHashTable *table, KeHashNode *node)
dvander@2226: {
dvander@2226: 	/* Destroy old value if it's set. */
dvander@2226: 	if (node->value != NULL && table->val_m.dtor != NULL)
dvander@2226: 	{
dvander@2226: 		table->val_m.dtor(node->value);
dvander@2226: 	}
dvander@2226: 
dvander@2226: 	/* Destroy the key. */
dvander@2226: 	if (table->key_m.dtor != NULL)
dvander@2226: 	{
dvander@2226: 		table->key_m.dtor(node->key);
dvander@2226: 	}
dvander@2226: 
dvander@2226: 	/* Deallocate us as appropriate. */
dvander@2226: 	if (table->keep_free_list)
dvander@2226: 	{
dvander@2226: 		node->next = table->free_list;
dvander@2226: 		table->free_list = node;
dvander@2226: 	}
dvander@2226: 	else
dvander@2226: 	{
dvander@2226: 		table->node_alloc->dealloc(table->node_alloc, node);
dvander@2226: 	}
dvander@2226: }
dvander@2226: 
dvander@2226: void Knight::KE_RemoveFromHashTable(KeHashTable *table, const void *key)
dvander@2226: {
dvander@2226: 	KeHashNode *node;
dvander@2226: 	uint32_t key_hash;
dvander@2226: 	KeHashNode **bucket;
dvander@2226: 
dvander@2226: 	key_hash = table->key_gen(key);
dvander@2226: 	bucket = ke_HashInternalFind(table, key_hash, key);
dvander@2226: 
dvander@2226: 	if ((node = *bucket) == NULL)
dvander@2226: 	{
dvander@2226: 		return;
dvander@2226: 	}
dvander@2226: 
dvander@2226: 	/* Link the bucket to its next (removing us). */
dvander@2226: 	*bucket = node->next;
dvander@2226: 
dvander@2226: 	ke_CleanUpHashNode(table, node);
dvander@2226: }
dvander@2226: 
dvander@2226: bool Knight::KE_FindInHashTable(KeHashTable *table, const void *key, void **value)
dvander@2226: {
dvander@2226: 	KeHashNode *node;
dvander@2226: 	uint32_t key_hash;
dvander@2226: 	KeHashNode **bucket;
dvander@2226: 
dvander@2226: 	key_hash = table->key_gen(key);
dvander@2226: 	bucket = ke_HashInternalFind(table, key_hash, key);
dvander@2226: 
dvander@2226: 	if ((node = *bucket) == NULL)
dvander@2226: 	{
dvander@2226: 		return false;
dvander@2226: 	}
dvander@2226: 
dvander@2226: 	if (value != NULL)
dvander@2226: 	{
dvander@2226: 		*value = node->value;
dvander@2226: 	}
dvander@2226: 
dvander@2226: 	return true;
dvander@2226: }
dvander@2226: 
dvander@2226: void Knight::KE_DestroyHashTable(KeHashTable *table)
dvander@2226: {
dvander@2226: 	KeHashNode *node, *next;
dvander@2226: 
dvander@2226: 	/* Turn off this caching! */
dvander@2226: 	table->keep_free_list = false;
dvander@2226: 
dvander@2226: 	/* Find entries in buckets that need to be freed. */
dvander@2226: 	for (uint32_t i = 0; i < table->num_buckets; i++)
dvander@2226: 	{
dvander@2226: 		node = table->buckets[i];
dvander@2226: 
dvander@2226: 		while (node != NULL)
dvander@2226: 		{
dvander@2226: 			next = node->next;
dvander@2226: 			ke_CleanUpHashNode(table, node);
dvander@2226: 			node = next;
dvander@2226: 		}
dvander@2226: 	}
dvander@2226: 
dvander@2226: 	/* Free the free list */
dvander@2226: 	while (table->free_list != NULL)
dvander@2226: 	{
dvander@2226: 		next = table->free_list->next;
dvander@2226: 		ke_CleanUpHashNode(table, table->free_list);
dvander@2226: 		table->free_list = next;
dvander@2226: 	}
dvander@2226: 
dvander@2226: 	/* Destroy everything now. */
dvander@2226: 	free(table->buckets);
dvander@2226: 	delete table;
dvander@2226: }
dvander@2226: 
dvander@2226: void Knight::KE_ClearHashTable(KeHashTable *table)
dvander@2226: {
dvander@2226: 	KeHashNode *node, *next;
dvander@2226: 
dvander@2226: 	/* Free every entry in the table. */
dvander@2226: 	for (uint32_t i = 0; i < table->num_buckets; i++)
dvander@2226: 	{
dvander@2226: 		node = table->buckets[i];
dvander@2226: 
dvander@2226: 		while (node != NULL)
dvander@2226: 		{
dvander@2226: 			next = node->next;
dvander@2226: 			ke_CleanUpHashNode(table, node);
dvander@2226: 			node = next;
dvander@2226: 		}
dvander@2226: 	}
dvander@2226: }
dvander@2226: 
dvander@2226: #if defined _MSC_VER && (defined _M_IX86 || defined _M_AMD64 || defined _M_X64)
dvander@2226: #pragma intrinsic(_rotl)
dvander@2226: #endif
dvander@2226: 
dvander@2226: uint32_t Knight::KE_HashString(const void *str)
dvander@2226: {
dvander@2226: 	uint32_t h;
dvander@2226: 	const unsigned char *us;
dvander@2226: 
dvander@2226: 	h = 0;
dvander@2226: 
dvander@2226: 	for (us = (const unsigned char *)str; *us != 0; us++)
dvander@2226: 	{
dvander@2226: #if defined _MSC_VER && (defined _M_IX86 || defined _M_AMD64 || defined _M_X64)
dvander@2226: 		h = _rotl(h, 4) ^ *us;
dvander@2226: #else
dvander@2226: 		h = ((h << 4) | (h >> 28)) ^ *us;
dvander@2226: #endif
dvander@2226: 	}
dvander@2226: 
dvander@2226: 	return h;
dvander@2226: }
dvander@2541: 
dvander@2541: bool Knight::KE_AreStringsEqual(const void* str1, const void* str2)
dvander@2541: {
dvander@2541:     return (strcmp((const char*)str1, (const char*)str2) == 0) ? true : false;
dvander@2541: }
dvander@2541: