/* Hashtable - a general purpose hash table
**
** Copyright 2001 pinc Software. All Rights Reserved.
** Released under the terms of the MIT license.
*/
 
 
#include <stdlib.h>
#include <stdarg.h>
#include <string.h>
 
#include "Hashtable.h"
 
 
/************************** standard string hash functions **************************/
 
 
unsigned int stringHash(const char *c)
{
	int len = strlen(c);
 
	return(*(int *)(c + len - 4));  // erstmal zum Testen
}
 
 
bool stringCompare(const char *a, const char *b)
{
	return(!strcmp(a, b));
}
 
 
// #pragma mark - Hashtable
 
 
Hashtable::Hashtable(int capacity, float loadFactor)
	:
	fIteratorIndex(-1)
{
	if (capacity < 0 || loadFactor <= 0)
		return;
 
	if (!capacity)
		capacity = 1;
 
	if (!(fTable = (struct Entry **)malloc(capacity * sizeof(void *))))
		return;
	memset(fTable,0,capacity * sizeof(void *));
 
	fThreshold = (int)(capacity * loadFactor);
	fModCount = 0;
	fLoadFactor = loadFactor;
	fCapacity = capacity;
 
	fHashFunc = (uint32 (*)(const void *))stringHash;
	fCompareFunc = (bool (*)(const void *, const void *))stringCompare;
}
 
 
Hashtable::~Hashtable()
{
	struct Entry **table = fTable;
 
	for(int32 index = fCapacity;--index >= 0;)
	{
		struct Entry *entry,*next;
 
		for(entry = table[index];entry;entry = next)
		{
			next = entry->next;
			delete entry;
		}
	}
	free(table);
}
 
 
void Hashtable::SetHashFunction(uint32 (*func)(const void *))
{
	fHashFunc = func;
}
 
 
void Hashtable::SetCompareFunction(bool (*func)(const void *, const void *))
{
	fCompareFunc = func;
}
 
 
bool Hashtable::IsEmpty() const
{
	return fCount == 0;
}
 
 
bool Hashtable::ContainsKey(const void *key)
{
	return GetHashEntry(key) ? true : false;
}
 
 
void *Hashtable::GetValue(const void *key)
{
	Entry *entry = GetHashEntry(key);
 
	return entry ? entry->value : NULL;
}
 
 
bool Hashtable::Put(const void *key, void *value)
{
	Entry *entry = GetHashEntry(key);
	int hash = fHashFunc(key);
	int index;
 
	if (entry)
		return true;
 
	fModCount++;
	if (fCount >= fThreshold)
		Rehash();
 
	index = hash % fCapacity;
 
	fTable[index] = new Entry(fTable[index], key, value);
	fCount++;
 
	return true;
}
 
 
void *Hashtable::Remove(const void *key)
{
	Entry **table,*entry,*prev;
	uint32 hash,(*func)(const void *);
	int32 index;
 
	table = fTable;
	hash = (func = fHashFunc)(key);
	index = hash % fCapacity;
 
	for(entry = table[index],prev = NULL;entry;entry = entry->next)
	{
		if ((func(entry->key) == hash) && fCompareFunc(entry->key,key))
		{
			void *value;
 
			fModCount++;
			if (prev)
				prev->next = entry->next;
			else
				table[index] = entry->next;
 
			fCount--;
			value = entry->value;
			delete entry;
 
			return value;
		}
		prev = entry;
	}
	return NULL;
}
 
 
status_t Hashtable::GetNextEntry(void **value)
{
	if (fIteratorIndex == -1)
	{
		fIteratorIndex = 0;
		fIteratorEntry = fTable[0];
	}
	else if (fIteratorEntry)
		fIteratorEntry = fIteratorEntry->next;
 
	// get next filled slot
	while (!fIteratorEntry && fIteratorIndex + 1 < fCapacity)
		fIteratorEntry = fTable[++fIteratorIndex];
 
	if (fIteratorEntry)
	{
		*value = fIteratorEntry->value;
		return B_OK;
	}
 
	return B_ENTRY_NOT_FOUND;
}
 
 
void Hashtable::Rewind()
{
	fIteratorIndex = -1;
}
 
 
void
Hashtable::MakeEmpty(int8 keyMode,int8 valueMode)
{
	fModCount++;
 
	for (int32 index = fCapacity; --index >= 0;) {
		Entry *entry, *next;
 
		for (entry = fTable[index]; entry; entry = next) {
			switch (keyMode) {
				case HASH_EMPTY_DELETE:
					// TODO: destructors are not called!
					delete (void*)entry->key;
					break;
				case HASH_EMPTY_FREE:
					free((void*)entry->key);
					break;
			}
			switch (valueMode) {
				case HASH_EMPTY_DELETE:
					// TODO: destructors are not called!
					delete entry->value;
					break;
				case HASH_EMPTY_FREE:
					free(entry->value);
					break;
			}
			next = entry->next;
			delete entry;
		}
		fTable[index] = NULL;
	}
	fCount = 0;
}
 
 
size_t
Hashtable::Size() const
{
	return fCount;
}
 
 
/** The hash table will be doubled in size, and rebuild.
 *  @return true on success
 */
 
bool Hashtable::Rehash()
{
	uint32 (*hashCode)(const void *) = fHashFunc;
	struct Entry **oldTable = fTable,**newtable;
	int oldCapacity = fCapacity;
	int newCapacity,i;
 
	newCapacity = oldCapacity * 2 + 1;
	if (!(newtable = (struct Entry **)malloc(newCapacity * sizeof(struct Entry *))))
		return false;
	memset(newtable,0,newCapacity*sizeof(struct Entry *));
 
	fModCount++;
	fThreshold = (int)(newCapacity * fLoadFactor);
	fTable = newtable;
	fCapacity = newCapacity;
 
	for (i = oldCapacity;i-- > 0;) {
		Entry *oldEntry,*entry = NULL;
		int index;
 
		for (oldEntry = oldTable[i];oldEntry;) {
			entry = oldEntry;  oldEntry = oldEntry->next;
 
			index = hashCode(entry->key) % newCapacity;
			entry->next = newtable[index];
			newtable[index] = entry;
		}
	}
	free(oldTable);
 
	return true;
}
 
 
Hashtable::Entry *Hashtable::GetHashEntry(const void *key)
{
	Entry **table,*entry;
	uint32 hash,(*func)(const void *);
 
	table = fTable;
	hash = (func = fHashFunc)(key);
 
	for(entry = table[hash % fCapacity];entry;entry = entry->next)
	{
		if ((func(entry->key) == hash) && fCompareFunc(entry->key,key))
			return entry;
	}
	return NULL;
}