/**
 * @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;
}