From 7f6002caba3f0a6749820c2772161caf55b8d267 Mon Sep 17 00:00:00 2001 From: neonloop Date: Fri, 7 May 2021 20:00:12 +0000 Subject: Initial commit (uqm-0.8.0) --- src/libs/uio/hashtable.h | 157 +++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 157 insertions(+) create mode 100644 src/libs/uio/hashtable.h (limited to 'src/libs/uio/hashtable.h') 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) */ + + + -- cgit v1.2.3