1 files changed, 157 insertions, 0 deletions
diff --git a/src/libs/uio/hashtable.h b/src/libs/uio/hashtable.h
new file mode 100644
index 0000000..eb4437f
--- /dev/null
+++ b/src/libs/uio/hashtable.h
@@ -0,0 +1,157 @@
+/*
+ * 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
+ *
+ */
+
+// The 'already included' check must be done slightly more complicated
+// than usually. This file may be included directly only once,
+// but it may be included my derivative HashTable definitions that use
+// this file as a template more than once.
+#if !defined(_HASHTABLE_H) || defined(HASHTABLE_GENERIC)
+#if defined(HASHTABLE_)
+#	define HASHTABLE_GENERIC
+#endif
+
+#include "types.h"
+#include "uioport.h"
+
+// Define to enable profiling.
+#define HashTable_PROFILE
+
+// You can use inline hash functions for extra speed, by using this file as
+// a template.
+// To do this, make a new .h and .c file. In the .h file, define the macros
+// (and typedefs) from the HASHTABLE_ block below.
+// In the .c file, #define HASHTABLE_INTERNAL, #include the .h file
+// and hashtable.c (in this order), and add the necessary functions.
+// If you do not need to free the Value, you can define HashTable_FREEVALUE
+// as a no-op.
+#ifndef HASHTABLE_
+#	define HASHTABLE_(identifier) HashTable ## _ ## identifier
+	typedef void HashTable_Key;
+	typedef void HashTable_Value;
+#	define HashTable_HASH(hashTable, hashValue) \
+		(hashTable)->hashFunction(hashValue)
+#	define HashTable_EQUAL(hashTable, hashKey1, hashKey2) \
+		(hashTable)->equalFunction(hashKey1, hashKey2)
+#	define HashTable_COPY(hashTable, hashKey) \
+		(hashTable)->copyFunction(hashKey)
+#	define HashTable_FREEKEY(hashTable, hashKey) \
+		(hashTable)->freeKeyFunction(hashKey)
+#	define HashTable_FREEVALUE(hashTable, hashValue) \
+		(hashTable)->freeValueFunction(hashValue)
+#endif
+
+
+
+typedef uio_uint32 (*HASHTABLE_(HashFunction))(const HASHTABLE_(Key) *);
+typedef uio_bool (*HASHTABLE_(EqualFunction))(const HASHTABLE_(Key) *,
+		const HASHTABLE_(Key) *);
+typedef HASHTABLE_(Value) *(*HASHTABLE_(CopyFunction))(
+		const HASHTABLE_(Key) *);
+typedef void (*HASHTABLE_(FreeKeyFunction))(HASHTABLE_(Key) *);
+typedef void (*HASHTABLE_(FreeValueFunction))(HASHTABLE_(Value) *);
+
+typedef struct HASHTABLE_(HashTable) HASHTABLE_(HashTable);
+typedef struct HASHTABLE_(HashEntry) HASHTABLE_(HashEntry);
+typedef struct HASHTABLE_(Iterator) HASHTABLE_(Iterator);
+
+struct HASHTABLE_(HashTable) {
+	HASHTABLE_(HashFunction) hashFunction;	
+			// Function creating a uio_uint32 hash of a key.
+	HASHTABLE_(EqualFunction) equalFunction;
+			// Function used to compare two keys.
+	HASHTABLE_(CopyFunction) copyFunction;
+			// Function used to copy a key.
+	HASHTABLE_(FreeKeyFunction) freeKeyFunction;
+			// Function used to free a key.
+	HASHTABLE_(FreeValueFunction) freeValueFunction;
+			// Function used to free a value. Called when an entry is
+			// removed using the remove function, or for entries
+			// still in the HashTable when the HashTable is deleted.
+
+	double minFillQuotient;
+			// How much of half of the hashtable needs to be filled
+			// before resizing to size/2.
+	double maxFillQuotient;
+			// How much of the hashTable needs to be filled before
+			// resizing to size*2.
+	uio_uint32 minSize;
+			// Resize to size/2 when below this size.
+	uio_uint32 maxSize;
+			// Resize to size*2 when above this size.
+	uio_uint32 size;
+			// The number of buckets in the hash table.
+	uio_uint32 hashMask;
+			// Mask to take on a the calculated hash value, to make it
+			// fit into the table.
+
+	HASHTABLE_(HashEntry) **entries;
+			// The actual entries
+
+	uio_uint32 numEntries;
+#ifdef HashTable_PROFILE
+	uio_uint32 numCollisions;
+#endif
+};
+
+struct HASHTABLE_(HashEntry) {
+	uio_uint32 hash;
+	HASHTABLE_(Key) *key;
+	HASHTABLE_(Value) *value;
+	HASHTABLE_(HashEntry) *next;
+};
+
+struct HASHTABLE_(Iterator) {
+	const HASHTABLE_(HashTable) *hashTable;
+	uio_uint32 bucketNr;
+	HASHTABLE_(HashEntry) *entry;
+};
+
+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);
+uio_bool HASHTABLE_(add)(HASHTABLE_(HashTable) *hashTable,
+		const HASHTABLE_(Key) *key, HASHTABLE_(Value) *value);
+uio_bool HASHTABLE_(remove)(HASHTABLE_(HashTable) *hashTable,
+		const HASHTABLE_(Key) *key);
+HASHTABLE_(Value) *HASHTABLE_(find)(
+		HASHTABLE_(HashTable) *hashTable, const HASHTABLE_(Key) *key);
+uio_uint32 HASHTABLE_(count)(const HASHTABLE_(HashTable) *hashTable);
+void HASHTABLE_(deleteHashTable)(HASHTABLE_(HashTable) *hashTable);
+HASHTABLE_(Iterator) *HASHTABLE_(getIterator)(
+		const HASHTABLE_(HashTable) *hashTable);
+int HASHTABLE_(iteratorDone)(const HASHTABLE_(Iterator) *iterator);
+HASHTABLE_(Key) *HASHTABLE_(iteratorKey)(HASHTABLE_(Iterator) *iterator);
+HASHTABLE_(Value) *HASHTABLE_(iteratorValue)(HASHTABLE_(Iterator) *iterator);
+HASHTABLE_(Iterator) *HASHTABLE_(iteratorNext)(HASHTABLE_(Iterator) *iterator);
+void HASHTABLE_(freeIterator)(HASHTABLE_(Iterator) *iterator);
+
+#ifndef HASHTABLE_INTERNAL
+#	undef HASHTABLE_
+#endif
+
+#endif /* !defined(_HASHTABLE_H) || defined(HASHTABLE_GENERIC) */
+
+
+