/** * @file hashMap.c * @ingroup collection * * Hashmap module * * @author Geoff Davis <geoff@circlemudsquared.org> * * @par Copyright: * Copyright (C) 2006 Geoff Davis <geoff@circlemudsquared.org><br> * Greg Buxton <greg@circlemudsquared.org> * * @par * Copyright (C) 1993, 94 by the Trustees of the Johns Hopkins University<br> * CircleMUD is based on DikuMUD, Copyright (C) 1990, 1991. * * @par * All rights reserved. See license.doc for complete information. * * @package cs * @version 1.0 */ #define __HASHMAP_C__ #include "base.h" #include "hashMap.h" #include "log.h" #include "memory.h" /* * hashmap functions */ /** * Removes all elements from a hashmap. * @param hashMap the hashmap to be cleared * @return none */ void hashMap_clear(hashMap_t *hashMap) { if (hashMap == NULL) { log("hashMap_clear(): invalid 'hashMap' hashMap_t."); } else if (hashMap->size) { /* Declare an iterator variable. */ register int i = 0; /* Iterate over the hashmap's entry table. */ for (i = 0; i < hashMap->entryTableSize; i++) { /* Delete any entries found in any hash list. */ while (hashMap->entryTable[i]) { hashMapPrivate_deleteEntry(hashMap, hashMap->entryTable[i]); } } } } /** * Returns whether a hashmap contains a particular key. * @param hashMap the hashmap whose contents are to be tested * @param key the key for which to test * @return true if the hashmap contains a matching key; * false otherwise */ bool hashMap_containsKey(hashMap_t *hashMap, const void *key) { if (hashMap == NULL) { log("hashMap_containsKey(): invalid 'hashMap' hashMap_t."); } else if (hashMap->size) { /* Find the entry for the user-provided key. */ hashMapEntry_t *entry = hashMapPrivate_getEntry(hashMap, key); if (entry) { return (TRUE); } } return (FALSE); } /** * Constructs a new hashmap. * @param entryTableSize the initial size of the hashmap entry table * @param hashFunction the hash function to be used to hash keys * @param keyFreeFunction the free function to be called for map keys * @param valueFreeFunction the free function to be called for map values * @return a new hashmap, or NULL */ hashMap_t *hashMap_create(size_t entryTableSize, hashFunction_t hashFunction, freeFunction_t keyFreeFunction, freeFunction_t valueFreeFunction) { if (hashFunction == NULL) { log("hashMap_create(): invalid 'hashFunction' hashFunction_t."); } else { /* Allocate memory for a hashMap_t. */ hashMap_t *hashMap = CIRCLE_ALLOCN(hashMap_t, 1); if (hashMap == NULL) { log("hashMap_create(): CIRCLE_ALLOCN() failed."); } else { /* If 'entryTableSize' is zero, pick a prime number. */ if (entryTableSize == 0) { entryTableSize = 1009; } /* Allocate memory for the hashmap's entry table. */ hashMap->entryTable = CIRCLE_ALLOCN(hashMapEntry_t*, entryTableSize); if (hashMap->entryTable == NULL) { log("hashMap_create(): CIRCLE_ALLOCN() failed."); free(hashMap); } else { /* Initialize the hashmap. */ hashMap->entryTableSize = entryTableSize; hashMap->keyFreeFunction = keyFreeFunction; hashMap->keyHashFunction = hashFunction; hashMap->valueFreeFunction = valueFreeFunction; return (hashMap); } } } return (NULL); } /** * Deletes a mapping from a hashmap. * @param hashMap the hashmap from which to remove a mapping * @param key the key of the mapping to be removed * @return true if the size of the hashmap was changed by this function; * false otherwise */ bool hashMap_delete(hashMap_t *hashMap, const void *key) { if (hashMap == NULL) { log("hashMap_delete(): invalid 'hashMap' hashMap_t."); } else if (hashMap->size) { /* Get the hashmap entry for the user-provided key. */ hashMapEntry_t *entry = hashMapPrivate_getEntry(hashMap, key); if (entry) { hashMapPrivate_deleteEntry(hashMap, entry); return (TRUE); } } return (FALSE); } /** * Frees a hashmap. * @param hashMap the hashmap to be freed * @return none */ void hashMap_free(hashMap_t *hashMap) { if (hashMap == NULL) { log("hashMap_free(): invalid 'hashMap' hashMap_t."); } else { hashMap_clear(hashMap); free(hashMap); } } /** * Returns the size of a hashmap. * @param hashMap the hashmap to be tested * @return the size of the hashmap, or zero (0) */ size_t hashMap_getSize(hashMap_t *hashMap) { if (hashMap == NULL) { log("hashMap_getSize(): invalid 'hashMap' hashMap_t."); } else { return (hashMap->size); } return (0); } /** * Returns the value for a given key. * @param hashMap the hashmap to be searched * @param key the key for which to retreive a value * @param defaultValue the value to be retuned if the key cannot be not found * @return the value associated with the key, the default value, or NULL */ void *hashMap_getValue(hashMap_t *hashMap, const void *key, void *defaultValue) { if (hashMap == NULL) { log("hashMap_getValue(): invalid 'hashMap' hashMap_t."); } else { /* Get the hashmap entry for the user-provided key. */ hashMapEntry_t *entry = hashMapPrivate_getEntry(hashMap, key); if (entry) { return (entry->value); } } return (defaultValue); } /** * Returns whether a hashmap is empty. * @param hashMap the hashmap to be tested * @return true if the hashmap is empty, having a size of zero (0); * false otherwise */ bool hashMap_isEmpty(hashMap_t *hashMap) { if (hashMap == NULL) { log("hashMap_isEmpty(): invalid 'hashMap' hashMap_t."); } else { if (hashMap->size == 0) { return (TRUE); } } return (FALSE); } /** * Inserts a key-to-value mapping into a hashmap. * @param hashMap the hashmap into which a mapping is to be inserted * @param key the key to be inserted * @param value the value to be inserted * @return true if the size of the hashmap was modified by this function; * false otherwise */ bool hashMap_insert(hashMap_t *hashMap, void *key, void *value) { if (hashMap == NULL) { log("hashMap_insert(): invalid 'hashMap' hashMap_t."); } else { /* Save off the original size of the hashmap. */ const size_t size = hashMap->size; /* Find the entry for the user-provided key. */ hashMapEntry_t *entry = hashMapPrivate_getEntry(hashMap, key); /* * If an entry was located, we will do an "in-place" insertion * by overwriting the its key and value. Otherwise, a new entry * must be inserted. */ if (entry) { /* If possible, free the entry's key. */ if (hashMap->keyFreeFunction) { hashMap->keyFreeFunction(entry->key); } /* If possible, free the entry's value. */ if (hashMap->valueFreeFunction) { hashMap->valueFreeFunction(entry->value); } /* Overwrite the entry's key and value. */ entry->key = key; entry->value = value; } else { /* Get a hash key for the user-provided key. */ const hashKey_t hashKey = hashMap->keyHashFunction(key); /* Calculate the entry table index where the entry is stored. */ const size_t entryTableIndex = hashKey % hashMap->entryTableSize; /* Allocate memory for a hashMapEntry_t. */ hashMapEntry_t *entry = CIRCLE_ALLOCN(hashMapEntry_t, 1); if (entry == NULL) { log("hashMap_insert(): CIRCLE_ALLOCN() failed."); } else { /* Initialize the new hash entry. */ entry->hashKey = hashKey; entry->key = key; entry->nextEntry = NULL; entry->value = value; /* Add the new hash entry to the hash list. */ entry->nextEntry = hashMap->entryTable[entryTableIndex]; hashMap->entryTable[entryTableIndex] = entry; /* Increment the size of the hashmap. */ hashMap->size++; } } if (size != hashMap->size) { return (TRUE); } } return (FALSE); } /* * hashmap iterator functions */ /** * Example of hashMapIterator implementation * @example hashMapIterator_example.c */ /** * Constructs a new hashmap iterator. * @param hashMap the hashmap to be iterated * @return a new hashmap iterator, or NULL */ hashMapIterator_t *hashMapIterator_create(hashMap_t *hashMap) { if (hashMap == NULL) { log("hashMapIterator_create(): invalid 'hashMap' hashMap_t."); } else { /* Allocate memory for a hashMapIterator_t. */ hashMapIterator_t *iter = CIRCLE_ALLOCN(hashMapIterator_t, 1); if (iter == NULL) { log("hashMapIterator_create(): CIRCLE_ALLOCN() failed."); } else { /* Initialize the new hashmap iterator. */ iter->hashMap = hashMap; iter->lastReturned = NULL; iter->nextEntryIndex = 0; iter->nextEntry = NULL; if (hashMap->size) { /* Find the first entry and set lastReturned to it */ while (hashMap->entryTable[iter->nextEntryIndex] == NULL && iter->nextEntryIndex < hashMap->entryTableSize) { ++iter->nextEntryIndex; } if (iter->nextEntryIndex < hashMap->entryTableSize) { iter->lastReturned = hashMap->entryTable[iter->nextEntryIndex]; } /* Advance */ ++iter->nextEntryIndex; /* Next is the nextEntry */ while (hashMap->entryTable[iter->nextEntryIndex] == NULL && iter->nextEntryIndex < hashMap->entryTableSize) { ++iter->nextEntryIndex; } if (iter->nextEntryIndex < hashMap->entryTableSize) { iter->nextEntry = hashMap->entryTable[iter->nextEntryIndex]; } return (iter); } else { iter->nextEntryIndex = hashMap->entryTableSize; } } } return (NULL); } /** * Frees a hashmap iterator. * @param iter the hashmap iterator to be freed * @return none */ void hashMapIterator_free(hashMapIterator_t *iter) { if (iter) { free(iter); iter = NULL; } } /** * Returns whether a hashmap iterator has more mappings. * @param iter the hashmap iterator to be tested * @return true if there are more mappings to be iterated; * false otherwise */ bool hashMapIterator_hasNext(hashMapIterator_t *iter) { if (iter == NULL) { log("hashMapIterator_hasNext(): invalid 'iter' hashMapIterator_t."); } else { if (iter->nextEntry) { return (TRUE); } } return (FALSE); } /** * Returns the key of the next mapping in the underlying hashmap and * advances the hashmap iterator. * @param iter the hashmap iterator to be advanced * @return the next key in the hashmap, or NULL */ void *hashMapIterator_nextKey(hashMapIterator_t *iter) { return (NULL); } /** * Returns the value of the next mapping in the underlying hashmap and * advances the hashmap iterator. * @param iter the hashmap iterator to be advanced * @return the next value in the hashmap, or NULL */ void *hashMapIterator_nextValue(hashMapIterator_t *iter) { return (NULL); } /** * Removes the last element returned by a hashmap iterator. * @param iter the hashmap iterator from which to remove an element * @return none */ void hashMapIterator_remove(hashMapIterator_t *iter) { if (iter == NULL) { log("hashMapIterator_remove(): invalid 'iter' hashMapIterator_t."); } else if (iter->lastReturned) { hashMapPrivate_deleteEntry(iter->hashMap, iter->lastReturned); iter->lastReturned = NULL; } } /* * private hashmap functions */ /** * Removes a hashmap entry from a hashmap and updates the hashmap size * using a pair of free functions. * @param hashMap the hashmap whose entry is to be unlinked * @param entry the entry to be removed * @param freeKeyFunction the free function to be called for each key * @param freeValueFunction the free function to be called for each value * @return none */ void hashMapPrivate_deleteEntry(hashMap_t *hashMap, hashMapEntry_t *entry) { if (hashMap == NULL) { log("hashMapPrivate_deleteEntry(): invalid 'hashMap' hashMap_t."); } else { /* Save off the current size of the hashmap. */ const size_t size = hashMap->size; /* Calculate the entry table index where the entry is stored. */ const size_t entryTableIndex = entry->hashKey % hashMap->entryTableSize; /* Declare an iterator variable. */ register hashMapEntry_t *tempEntry = NULL; if (hashMap->entryTable[entryTableIndex] == entry) { /* Delete the entry from the hash list. */ hashMap->entryTable[entryTableIndex] = entry->nextEntry; hashMap->size--; } else { /* Search the hash list for the specified hashmap entry. */ for (tempEntry = hashMap->entryTable[entryTableIndex]; tempEntry && tempEntry->nextEntry != entry; tempEntry = tempEntry->nextEntry); /* Delete the entry from the hash list. */ if (tempEntry && tempEntry->nextEntry == entry) { tempEntry->nextEntry = entry->nextEntry; hashMap->size--; } } if (size == hashMap->size) { log("hashMapPrivate_deleteEntry(): hashmap entry is not in hashmap."); } else { /* If possible, free the entry's key. */ if (hashMap->keyFreeFunction) { hashMap->keyFreeFunction(entry->key); } /* If possible, free the entry's value. */ if (hashMap->valueFreeFunction) { hashMap->valueFreeFunction(entry->value); } /* Now free the hashmap entry. */ free(entry); } } } /** * Returns the hashmap entry corresponding to a particular key. * @param hashMap the hashmap whose entry is to be retrieved * @return the matching hashmap entry, or NULL */ hashMapEntry_t *hashMapPrivate_getEntry(hashMap_t *hashMap, const void *key) { if (hashMap == NULL) { log("hashMapPrivate_getEntry(): invalid 'hashMap' hashMap_t."); } else if (hashMap->size) { /* Get a hash key for the user-provided key. */ const hashKey_t hashKey = hashMap->keyHashFunction(key); /* Calculate the entry table index where the entry is stored. */ const size_t entryTableIndex = hashKey % hashMap->entryTableSize; /* Declare an iterator variable. */ register hashMapEntry_t *entry = NULL; /* Search the hash list for the hash key. */ for (entry = hashMap->entryTable[entryTableIndex]; entry; entry = entry->nextEntry) { if (entry->hashKey == hashKey) { return (entry); } } } return (NULL); } /* * Let's see if we can fix up the iterators */ /** * Advance the hashMapIterator * * lastReturned is set with nextEntry * nextEntryIndex and nextEntry are advanced or NULL'd/max'd * * @param hashMapIterator_t to advance * */ void hashMapIterator_next(hashMapIterator_t *iter) { if (iter == NULL) { log("hashMapIterator_next(): Invalid hashMapIterator_t 'iter'."); } else { if (iter->nextEntry) { iter->lastReturned = iter->nextEntry; if (iter->hashMap->size) { if (iter->hashMap->entryTable[iter->nextEntryIndex] != NULL) { ++iter->nextEntryIndex; } while (iter->hashMap->entryTable[iter->nextEntryIndex] == NULL && iter->nextEntryIndex < iter->hashMap->entryTableSize) { ++iter->nextEntryIndex; } if (iter->nextEntryIndex < iter->hashMap->entryTableSize) { iter->nextEntry = iter->hashMap->entryTable[iter->nextEntryIndex]; } else { iter->nextEntry = NULL; } } else { iter->nextEntryIndex = iter->hashMap->entryTableSize; } } else { iter->nextEntryIndex = iter->hashMap->entryTableSize; iter->lastReturned = NULL; iter->nextEntry = NULL; } } } /** * Get the value pointed to by the current iterator entry */ void *hashMapIterator_getValue(hashMapIterator_t *iter) { if (iter) { if (iter->lastReturned) { return iter->lastReturned->value; } } return NULL; }