
/** @file  psHash.c
*
*  @brief Contains support for basic hashing functions.
*
*  This file will hold the functions for defining a hash table with arbitrary
*  data types, allocating/deallocating that hash table, adding and removing
*  data from that hash table, and listing all keys defined in the hash table.
*
*  @author Robert Lupton, Princeton University
*  @author Robert DeSonia, MHPCC
*  @author GLG, MHPCC
*
*  @version $Revision: 1.17 $ $Name: not supported by cvs2svn $
*  @date $Date: 2005-06-07 22:37:52 $
*
*  Copyright 2004-2005 Maui High Performance Computing Center, University of Hawaii
*/
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include "psHash.h"
#include "psMemory.h"
#include "psString.h"
#include "psTrace.h"
#include "psError.h"
#include "psConstants.h"

#include "psCollectionsErrors.h"

static psHashBucket* hashBucketAlloc(const char *key, psPtr data, psHashBucket* next);
static void hashBucketFree(psHashBucket* bucket);
static psPtr doHashWork(psHash* table, const char *key, psPtr data, psBool remove
                           );
static void hashFree(psHash* table);

/******************************************************************************
psHashKeyList(table): this function creates a linked list with an entry in
that list for every key in the hash table.
Inputs:
    table: a hash table
Return;
    The linked list
 *****************************************************************************/
psList* psHashKeyList(psHash* table)
{
    psS32 i = 0;                  // Loop index variable
    psList* myLinkList = NULL;  // The output data structure
    psHashBucket* ptr = NULL;   // Used to step thru linked list.

    if (table == NULL) {
        return NULL;
    }
    // Create the linked list
    myLinkList = psListAlloc(NULL);

    // Loop through every bucket in the hash table.  If that bucket is not
    // NULL, then add the bucket's key to the linked list.
    for (i = 0; i < table->nbucket; i++) {
        if (table->buckets[i] != NULL) {
            // Since a bucket contains a linked list of keys/data, we must
            // step trough each key in that linked list:

            ptr = table->buckets[i];
            while (ptr != NULL) {
                psListAdd(myLinkList, PS_LIST_HEAD, ptr->key);
                ptr = ptr->next;
            }
        }
    }

    // Return the linked list
    return (myLinkList);
}

/******************************************************************************
hashBucketAlloc(key, data, next): This procedure creates a new hash bucket
with the specified key, data, and next.
Inputs:
    key:  the new bucket's key pointer
    data: the new bucket's data pointer
    next: the new bucket's key pointer
Return:
    the new hash bucket.
 *****************************************************************************/
static psHashBucket* hashBucketAlloc(const char *key,
                                     psPtr data,
                                     psHashBucket* next)
{
    // Allocate memory for the new hash bucket.
    psHashBucket* bucket = psAlloc(sizeof(psHashBucket));

    psMemSetDeallocator(bucket, (psFreeFcn) hashBucketFree);

    // Initialize the bucket.
    bucket->key = psStringCopy(key);

    if (data == NULL) {
        // NOTE: Should we flag a warning message?
        bucket->data = NULL;
    } else {
        bucket->data = psMemIncrRefCounter(data);
    }

    bucket->next = next;

    return bucket;
}

/******************************************************************************
hashBucketFree(bucket): This procedure deallocates the specified
hash bucket.
Inputs:
    bucket: the hash bucket to be freed.
Return:
    NONE
 *****************************************************************************/
static void hashBucketFree(psHashBucket* bucket)
{
    if (bucket == NULL) {
        return;
    }

    psFree(bucket->key);

    psFree(bucket->data);
}

/******************************************************************************
psHashAlloc(nbucket): this procedure creates a new hash table with the
specified number of buckets.
Inputs:
    nbucket: initial number of buckets
Return:
    The new hash table.
 *****************************************************************************/
psHash* psHashAlloc(psS32 nbucket)        // initial number of buckets
{
    psS32 i = 0;                  // loop index variable

    // Create the new hash table.
    psHash* table = psAlloc(sizeof(psHash));

    psMemSetDeallocator(table, (psFreeFcn) hashFree);

    // Allocate memory for the buckets.
    table->buckets = psAlloc(nbucket * sizeof(psHashBucket* ));
    table->nbucket = nbucket;

    psTrace("utils.hash", 1, "Creating %d-element hash table\n", nbucket);

    // Initialize all buckets to NULL.
    for (i = 0; i < nbucket; i++)
    {
        table->buckets[i] = NULL;
    }

    // Return the new hash table.
    return table;
}

/******************************************************************************
hashFree(table): This procedure deallocates the specified hash
table.  It loops through each bucket, and calls hashBucketFree() on that
bucket.
 
Inputs:
    table: a hash table
Return:
    NONE
 *****************************************************************************/
static void hashFree(psHash* table)
{
    psS32 i = 0;                  // Loop index variable.

    if (table == NULL) {
        return;
    }
    // Loop through each bucket in the hash table.  If that bucket is not
    // NULL, then free the bucket via a function call to hashBucketFree();
    for (i = 0; i < table->nbucket; i++) {

        // A bucket is composed of a linked list of buckets.
        while (table->buckets[i] != NULL) {
            psHashBucket* bucket = table->buckets[i];
            table->buckets[i] = bucket->next;
            psFree(bucket);
        }
    }

    // Free the bucket structure, then the hash table.
    psFree(table->buckets);
}

/******************************************************************************
doHashWork(table, key, data, remove): This is an internal
procedure which does the bulk of the work in using the hash table.  Depending
upon the input parameters, it will either insert a new key/data into the hash
table, retrieve the data for a specified key, or remove a key/data item.  If
we try to insert a key that already exists in the hash table, then we deallocate
the existing data/key item.
Inputs:
    table: a hash table
    key: the key to insert, retrieve, or remove.  Must not be NULL.
    data: the data to insert, if not NULL
    remove: set to non-zero if the key/data should be removed from the table.
Return:
    NONE
 
NOTE: consider removing this private function and simply putting the code
into the psHashInsert(), psHashLookup(), and psHashRemove().  Why?  Because
there is little common code between those functions.
  *****************************************************************************/
static psPtr doHashWork(psHash* table,
                        const char *key,
                        psPtr data, psBool remove
                           )
{
    psS64 hash = 1;          // This will contain an integer value

    // "hashed" from the key.
    char *tmpchar = NULL;       // Used in computing the hash function.
    psHashBucket* ptr = NULL;   // Used to retrieve the hash bucket.
    psHashBucket* optr = NULL;  // "original pointer": used to step

    // thru the linked list for a bucket.

    // The following condition should never be true, since this is a private
    // function, but I'm checking it anyway since future coders might change
    // the way this procedure is called.
    if ((table == NULL) || (key == NULL)) {
        psError(PS_ERR_BAD_PARAMETER_NULL, true,
                PS_ERRORTEXT_psHash_KEY_NULL);
        return NULL;
    }
    // NOTE: This is the originally supplied hash function.
    // for (psS32 i = 0, len = strlen(key); i < len; i++) {
    // hash = (hash << 1) ^ key[i];
    // }
    // hash &= (table->nbucket - 1);

    // This hash algorithm is from Sedgewick.  NOTE: must reread to ensure that
    // the size of the hash table is not required to be a prime number.
    tmpchar = (char *)key;
    for (hash = 0; *tmpchar != '\0'; tmpchar++) {
        hash = (64 * hash + *tmpchar) % (table->nbucket);
    }

    // NOTE: This should not be necessary, but for now, I'm checking bounds
    // anyway.
    if ((hash < 0) || (hash >= table->nbucket)) {
        psError(PS_ERR_UNKNOWN, true,
                "Internal hash function out of range (%d)", hash);
    }
    // ptr will have the correct hash bucket.
    ptr = table->buckets[hash];

    // We know the correct hash bucket, now we need to know what to do.
    // If the data parameter is NULL, then, by definition, this is a retrieve
    // or a remove operation on the hash table.

    if (data == NULL) {
        if (remove
           ) {
            // We search through the linked list for this bucket in
            // the hash table and look for an entry for this key.

            optr = ptr;
            while (ptr != NULL) {
                // Determine if this entry holds the correct key.
                if (strcmp(key, ptr->key) == 0) {
                    // The following lines of code are fairly standard ways
                    // of removing an item from a single-linked list.

                    psPtr data = ptr->data;

                    optr->next = ptr->next;
                    if (ptr == table->buckets[hash]) {
                        table->buckets[hash] = ptr->next;
                    }
                    psFree(ptr);

                    // By definition, the data associated with that key
                    // must be returned, not freed.
                    return data;
                }
                optr = ptr;
                ptr = ptr->next;
            }
            return NULL;                   // not in hash
        }
        else {
            // If we get here, then a retrieve operation is requested.  So,
            // we step trough the linked list at this bucket, and return the
            // data once we find it, or return NULL if we don't.
            while (ptr != NULL) {
                if (strcmp(key, ptr->key) == 0) {
                    return ptr->data;
                }
                ptr = ptr->next;
            }
            return NULL;                   // not in hash
        }
    } else {
        // We get here if this procedure was called with non-NULL data.
        // Therefore, we should insert that data into the hash table.
        // First, we search through the linked list for this bucket in
        // the hash table and look for a duplicate entry for this key.

        while (ptr != NULL) {
            if (strcmp(key, ptr->key) == 0) {
                // We have found this key in the hash table.

                psTrace("utils.hash.insert", 3, "Replacing data for %s\n", key);

                // NOTE: I have changed this behavior from the originally
                // supplied code.  Formerly, if itemFree was NULL, then
                // the new data was not inserted into the hash table.

                psFree(ptr->data);

                ptr->data = psMemIncrRefCounter(data);
                return data;
            }
            ptr = ptr->next;
        }
        // We did not found key in the linked list for this bucket of the hash
        // table.  So, we insert this data at the head of that linked list.

        table->buckets[hash] = hashBucketAlloc(key, data, table->buckets[hash]);
        return data;
    }
}

/******************************************************************************
psHashAdd(table, key, data): this procedure, which is part of
the public API, inserts a new key/data pair into the hash table.
Inputs:
    table: a hash table
    key: the key to use
    data: the data to insert.
Return:
    boolean value defining success or failure
 *****************************************************************************/
psBool psHashAdd(psHash* table,
                 const char *key,
                 psPtr data)
{
    PS_ASSERT_PTR_NON_NULL(table, false);
    PS_ASSERT_PTR_NON_NULL(key, false);
    PS_ASSERT_PTR_NON_NULL(data, false);

    return (doHashWork(table, key, data, false) != NULL);
}

/******************************************************************************
psHashLookup(table, key): this procedure, which is part of the public API,
looks up the specified key in the hash table and returns the data associated
with that key.
 
Inputs:
    table: a hash table
    key: the key to use
Return:
    The data associated with that key.
 *****************************************************************************/
psPtr psHashLookup(psHash* table,      // table to lookup key in
                   const char *key)     // key to lookup
{
    PS_ASSERT_PTR_NON_NULL(table, NULL);
    PS_ASSERT_PTR_NON_NULL(key, NULL);

    return doHashWork(table, key, NULL, false);
}

/******************************************************************************
psHashRemove(table, key): this procedure, which is part of the
public API, removes the specified key from the hash table.
Inputs:
    table: a hash table
    key: the key to remove
Return:
    boolean value defining success or failure
 *****************************************************************************/
psBool psHashRemove(psHash* table,
                    const char *key)
{
    psPtr data = NULL;
    psBool retVal = false;

    PS_ASSERT_PTR_NON_NULL(table, false);
    PS_ASSERT_PTR_NON_NULL(key, false);

    data = doHashWork(table, key, NULL, true);
    if (data != NULL) {
        retVal = true;
    } else {
        retVal = false;
    }

    return retVal;
}

psArray* psHashToArray(psHash* table)
{
    PS_ASSERT_PTR_NON_NULL(table, NULL);

    // first, let's just count the number of data elements to know what size
    // psArray we need to allocate.
    int nElements = 0;
    int nbucket = table->nbucket;
    for (int i = 0; i < nbucket; i++) {
        psHashBucket* tmpBucket = table->buckets[i];
        while (tmpBucket != NULL) {
            nElements++;
            tmpBucket = tmpBucket->next;
        }
    }

    psArray* result = psArrayAlloc(nElements);
    result->n = nElements;

    // now fill in the array with the hash table's data
    psPtr* data = result->data;
    for (int i = 0; i < nbucket; i++) {
        psHashBucket* tmpBucket = table->buckets[i];
        while (tmpBucket != NULL) {
            *(data++) = psMemIncrRefCounter(tmpBucket->data);
            tmpBucket = tmpBucket->next;
        }
    }

    return result;
}
