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.c | 374 +++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 374 insertions(+) create mode 100644 src/libs/uio/hashtable.c (limited to 'src/libs/uio/hashtable.c') 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 +#include +#include +#include + +#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); +} + -- cgit v1.2.3