1 files changed, 374 insertions, 0 deletions
diff --git a/src/libs/uio/hashtable.c b/src/libs/uio/hashtable.c
new file mode 100644
index 0000000..1f376e1
--- /dev/null
+++ b/src/libs/uio/hashtable.c
@@ -0,0 +1,374 @@
+/*
+ * Copyright (C) 2003  Serge van den Boom
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of version 2 of the GNU General Public License as
+ * published by the Free Software Foundation.
+ * Nota bene: later versions of the GNU General Public License do not apply
+ * to this program.
+ *
+ * This program 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 General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+ *
+ */
+
+#ifndef HASHTABLE_INTERNAL
+	// If HASHTABLE_INTERNAL is already defined, this file is included
+	// as a template. In this case hashtable.h has already been included.
+#	define HASHTABLE_INTERNAL
+#	include "hashtable.h"
+#endif
+
+#include <stdlib.h>
+#include <assert.h>
+#include <string.h>
+#include <math.h>
+
+#include "mem.h"
+#include "uioport.h"
+
+static void HASHTABLE_(setup)(HASHTABLE_(HashTable) *HashTable,
+		uio_uint32 size);
+static void HASHTABLE_(resize)(HASHTABLE_(HashTable) *hashTable);
+static inline uio_uint32 nextPower2(uio_uint32 x);
+
+static inline HASHTABLE_(HashTable) *HASHTABLE_(allocHashTable)(void);
+static inline HASHTABLE_(HashEntry) *HASHTABLE_(newHashEntry)(uio_uint32 hash,
+		HASHTABLE_(Key) *key, HASHTABLE_(Value) *value,
+		HASHTABLE_(HashEntry) *next);
+static inline HASHTABLE_(HashEntry) *HASHTABLE_(allocHashEntry)(void);
+static inline void HASHTABLE_(freeHashEntry)(
+		HASHTABLE_(HashEntry) *entry);
+
+// Create a new HashTable.
+HASHTABLE_(HashTable) *
+HASHTABLE_(newHashTable)(
+		HASHTABLE_(HashFunction) hashFunction,
+		HASHTABLE_(EqualFunction) equalFunction,
+		HASHTABLE_(CopyFunction) copyFunction,
+		HASHTABLE_(FreeKeyFunction) freeKeyFunction,
+		HASHTABLE_(FreeValueFunction) freeValueFunction,
+		uio_uint32 initialSize,
+		double minFillQuotient,
+		double maxFillQuotient) {
+	HASHTABLE_(HashTable) *hashTable;
+
+	assert(maxFillQuotient >= minFillQuotient);
+	
+	hashTable = HASHTABLE_(allocHashTable)();
+	hashTable->hashFunction = hashFunction;
+	hashTable->equalFunction = equalFunction;
+	hashTable->copyFunction = copyFunction;
+	hashTable->freeKeyFunction = freeKeyFunction;
+	hashTable->freeValueFunction = freeValueFunction;
+
+	hashTable->minFillQuotient = minFillQuotient;
+	hashTable->maxFillQuotient = maxFillQuotient;
+	HASHTABLE_(setup)(hashTable, initialSize);
+
+	return hashTable;
+}
+
+// Add an entry to the HashTable.
+uio_bool
+HASHTABLE_(add)(HASHTABLE_(HashTable) *hashTable,
+		const HASHTABLE_(Key) *key, HASHTABLE_(Value) *value) {
+	uio_uint32 hash;
+	struct HASHTABLE_(HashEntry) *entry;
+
+	hash = HASHTABLE_(HASH)(hashTable, key);
+	entry = hashTable->entries[hash & hashTable->hashMask];
+	while (entry != NULL) {
+		if (HASHTABLE_(EQUAL)(hashTable, key, entry->key)) {
+			// key is already present
+			return false;
+		}
+		entry = entry->next;
+	}
+
+#ifdef HashTable_PROFILE
+	if (hashTable->entries[hash & hashTable->hashMask] != NULL)
+		hashTable->numCollisions++;
+#endif
+	hashTable->entries[hash & hashTable->hashMask] =
+			HASHTABLE_(newHashEntry)(hash,
+			HASHTABLE_(COPY)(hashTable, key), value,
+			hashTable->entries[hash & hashTable->hashMask]);
+
+	hashTable->numEntries++;
+	if (hashTable->numEntries > hashTable->maxSize)
+		HASHTABLE_(resize)(hashTable);
+
+	return true;
+}
+
+// Remove an entry with a specified Key from the HashTable.
+uio_bool
+HASHTABLE_(remove)(HASHTABLE_(HashTable) *hashTable,
+		const HASHTABLE_(Key) *key) {
+	uio_uint32 hash;
+	struct HASHTABLE_(HashEntry) **entry, *next;
+
+	hash = HASHTABLE_(HASH)(hashTable, key);
+	entry = &hashTable->entries[hash & hashTable->hashMask];
+	while (1) {
+		if (*entry == NULL)
+			return false;
+		if (HASHTABLE_(EQUAL)(hashTable, key, (*entry)->key)) {
+			// found the key
+			break;
+		}
+		entry = &(*entry)->next;
+	}
+	next = (*entry)->next;
+	HASHTABLE_(FREEKEY)(hashTable, (*entry)->key);
+	HASHTABLE_(FREEVALUE)(hashTable, (*entry)->value);
+	HASHTABLE_(freeHashEntry)(*entry);
+	*entry = next;
+
+	hashTable->numEntries--;
+	if (hashTable->numEntries < hashTable->minSize)
+		HASHTABLE_(resize)(hashTable);
+	
+	return true;
+}
+
+// Find the Value stored for some Key.
+HASHTABLE_(Value) *
+HASHTABLE_(find)(HASHTABLE_(HashTable) *hashTable,
+		const HASHTABLE_(Key) *key) {
+	uio_uint32 hash;
+	struct HASHTABLE_(HashEntry) *entry;
+
+	hash = HASHTABLE_(HASH)(hashTable, key);
+	entry = hashTable->entries[hash & hashTable->hashMask];
+	while (entry != NULL) {
+		if (HASHTABLE_(EQUAL)(hashTable, key, entry->key)) {
+			// found the key
+			return entry->value;
+		}
+		entry = entry->next;
+	}
+	return NULL;
+}
+
+// Returns the number of entries in the HashTable.
+uio_uint32
+HASHTABLE_(count)(const HASHTABLE_(HashTable) *hashTable) {
+	return hashTable->numEntries;
+}
+
+// Auxiliary function to (re)initialise the buckets in the HashTable.
+static void
+HASHTABLE_(setup)(HASHTABLE_(HashTable) *hashTable, uio_uint32 initialSize) {
+	if (initialSize < 4)
+		initialSize = 4;
+	hashTable->size = nextPower2(ceil(((double) initialSize) /
+			hashTable->maxFillQuotient));
+	hashTable->hashMask = hashTable->size - 1;
+	hashTable->minSize = ceil(((double) (hashTable->size >> 1))
+			* hashTable->minFillQuotient);
+	hashTable->maxSize = floor(((double) hashTable->size)
+			* hashTable->maxFillQuotient);
+	hashTable->entries = uio_calloc(hashTable->size,
+			sizeof (HASHTABLE_(HashEntry) *));
+	hashTable->numEntries = 0;
+#ifdef HashTable_PROFILE
+	hashTable->numCollisions = 0;
+#endif
+}
+
+// Resize the buckets in the HashTable.
+static void
+HASHTABLE_(resize)(HASHTABLE_(HashTable) *hashTable) {
+	HASHTABLE_(HashEntry) **oldEntries;
+	HASHTABLE_(HashEntry) *entry, *next;
+	HASHTABLE_(HashEntry) **newLocation;
+	uio_uint32 oldNumEntries;
+	uio_uint32 i;
+	
+	oldNumEntries = hashTable->numEntries;
+	oldEntries = hashTable->entries;
+
+	HASHTABLE_(setup)(hashTable, hashTable->numEntries);
+	hashTable->numEntries = oldNumEntries;
+	
+	i = 0;
+	while (oldNumEntries > 0) {
+		entry = oldEntries[i];
+		while (entry != NULL) {
+			next = entry->next;
+			newLocation = &hashTable->entries[entry->hash &
+					hashTable->hashMask];
+#ifdef HashTable_PROFILE
+			if (*newLocation != NULL)
+				hashTable->numCollisions++;
+#endif
+			entry->next = *newLocation;
+			*newLocation = entry;
+			oldNumEntries--;
+			entry = next;
+		}
+		i++;
+	}
+	
+	uio_free(oldEntries);
+}
+
+// Adapted from "Hackers Delight"
+// Returns the smallest power of two greater or equal to x.
+static inline uio_uint32
+nextPower2(uio_uint32 x) {
+	x--;
+	x |= x >> 1;
+	x |= x >> 2;
+	x |= x >> 4;
+	x |= x >> 8;
+	x |= x >> 16;
+	return x + 1;
+}
+
+// Get an iterator to iterate through all the entries in the HashTable.
+// NB: Iterator should be considered invalid if the HashTable is changed.
+// TODO: change this (make it thread-safe)
+//       this can be done by only marking items as deleted when
+//       there are outstanding iterators.
+HASHTABLE_(Iterator) *
+HASHTABLE_(getIterator)(const HASHTABLE_(HashTable) *hashTable) {
+	HASHTABLE_(Iterator) *iterator;
+	uio_uint32 i;
+
+	iterator = uio_malloc(sizeof (HASHTABLE_(Iterator)));
+	iterator->hashTable = hashTable;
+	
+	// Look for the first used bucket.
+	for (i = 0; i < iterator->hashTable->size; i++) {
+		if (iterator->hashTable->entries[i] != NULL) {
+			// Found a used bucket.
+			iterator->bucketNr = i;
+			iterator->entry = iterator->hashTable->entries[i];
+			return iterator;
+		}
+	}
+
+	// No entries were found.
+	iterator->bucketNr = i;
+	iterator->entry = NULL;
+	return iterator;
+}
+
+// Returns true if and only if there are no more entries in the hash table
+// for the Iterator to find.
+int
+HASHTABLE_(iteratorDone)(const HASHTABLE_(Iterator) *iterator) {
+	return iterator->bucketNr >= iterator->hashTable->size;
+}
+
+// Get the Key of the entry pointed to by an Iterator.
+HASHTABLE_(Key) *
+HASHTABLE_(iteratorKey)(HASHTABLE_(Iterator) *iterator) {
+	return iterator->entry->key;
+}
+
+// Get the Value of the entry pointed to by an Iterator.
+HASHTABLE_(Value) *
+HASHTABLE_(iteratorValue)(HASHTABLE_(Iterator) *iterator) {
+	return iterator->entry->value;
+}
+
+// Move the Iterator to the next entry in the HashTable.
+// Should not be called if the iterator is already past the last entry.
+HASHTABLE_(Iterator) *
+HASHTABLE_(iteratorNext)(HASHTABLE_(Iterator) *iterator) {
+	uio_uint32 i;
+
+	// If there's another entry in this bucket, use that.
+	iterator->entry = iterator->entry->next;
+	if (iterator->entry != NULL)
+		return iterator;
+
+	// Look for the next used bucket.
+	for (i = iterator->bucketNr + 1; i < iterator->hashTable->size; i++) {
+		if (iterator->hashTable->entries[i] != NULL) {
+			// Found another used bucket.
+			iterator->bucketNr = i;
+			iterator->entry = iterator->hashTable->entries[i];
+			return iterator;
+		}
+	}
+
+	// No more entries were found.
+	iterator->bucketNr = i;
+	iterator->entry = NULL;
+	return iterator;
+}
+
+// Free the Iterator.
+void
+HASHTABLE_(freeIterator)(HASHTABLE_(Iterator) *iterator) {
+	uio_free(iterator);
+}
+
+// Auxiliary function to allocate a HashTable.
+static inline HASHTABLE_(HashTable) *
+HASHTABLE_(allocHashTable)(void) {
+	return uio_malloc(sizeof (HASHTABLE_(HashTable)));
+}
+
+// Auxiliary function to create a HashEntry.
+static inline HASHTABLE_(HashEntry) *
+HASHTABLE_(newHashEntry)(uio_uint32 hash, HASHTABLE_(Key) *key,
+		HASHTABLE_(Value) *value, HASHTABLE_(HashEntry) *next) {
+	HASHTABLE_(HashEntry) *result;
+
+	result = HASHTABLE_(allocHashEntry)();
+	result->hash = hash;
+	result->key = key;
+	result->value = value;
+	result->next = next;
+	return result;
+}
+
+// Allocate a new HashEntry.
+static inline HASHTABLE_(HashEntry) *
+HASHTABLE_(allocHashEntry)(void) {
+	return uio_malloc(sizeof (HASHTABLE_(HashEntry)));
+}
+
+// Delete the HashTable.
+void
+HASHTABLE_(deleteHashTable)(HASHTABLE_(HashTable) *hashTable) {
+	uio_uint32 i;
+	HASHTABLE_(HashEntry) *entry, *next;
+	HASHTABLE_(HashEntry) **bucketPtr;
+
+	i = hashTable->numEntries;
+	bucketPtr = hashTable->entries;
+	while (i > 0) {
+		entry = *bucketPtr;
+		while (entry != NULL) {
+			next = entry->next;
+			HASHTABLE_(FREEKEY)(hashTable, entry->key);
+			HASHTABLE_(FREEVALUE)(hashTable, entry->value);
+			HASHTABLE_(freeHashEntry)(entry);
+			entry = next;
+			i--;
+		}
+		bucketPtr++;
+	}
+	uio_free(hashTable->entries);
+	uio_free(hashTable);
+}
+
+// Auxiliary function to deallocate a HashEntry.
+static inline void
+HASHTABLE_(freeHashEntry)(HASHTABLE_(HashEntry) *entry) {
+	uio_free(entry);
+}
+