haiku.git

/* 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;
}