/*
 * An interface to hash tables for Pan-STARRS
 *
 * Collisions are handled by simple linked lists
 */
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include "psLib.h"

/*****************************************************************************/
/*
 * A bucket that holds an item of data
 */
typedef struct HashBucket {
    char *key;				// key for this item of data
    void *data;				// the data itself
    struct HashBucket *next;		// list of other possible keys
} HashBucket;

/*
 * An entire hash table
 */
struct HashTable {
    int nbucket;			// number of buckets
    HashBucket **buckets;		// the buckets themselves
};

/*****************************************************************************/
/*
 * Con/Destruct buckets
 */
static HashBucket *hashBucketAlloc(const char *key,
				   void *data,
				   HashBucket *next)
{
    HashBucket *bucket = psAlloc(sizeof(HashBucket));

    bucket->key = psStringCopy(key);
    bucket->data = psMemIncrRefCounter(data);
    bucket->next = next;

    return bucket;
}

static void hashBucketFree(
    HashBucket *bucket,			// bucket to free
    void (*itemFree)(void *item))	// how to free hashed data;
					// or NULL
{
    if (bucket == NULL) {
	return;
    }

    psFree(bucket->key);
    psMemDecrRefCounter(bucket->data);
    
    if (itemFree != NULL) {
	itemFree(bucket->data);
    }
    
    psFree(bucket);
}

/*****************************************************************************/
/*
 * Con/Destruct psHash tables
 */
psHash *psHashAlloc(void)
{
    int nbucket = 128;			// XXX initial number of buckets
    psHash *table = psAlloc(sizeof(psHash));
    table->buckets = psAlloc(nbucket*sizeof(HashBucket *));
    table->nbucket = nbucket;

    psTrace("utils.hash", 1, "Creating %d-element hash table\n", nbucket);
    
    for (int i = 0; i < nbucket; i++) {
	table->buckets[i] = NULL;
    }

    return table;
}

void psHashFree(psHash *table,		// hash table to be freed
		void (*itemFree)(void *item)) // how to free hashed data; or NULL
{
    if (table == NULL) {
	return;
    }
/*
 * Release data interned on the list, and delete the buckets
 */
    for (int i = 0; i < table->nbucket; i++) {
	if (table->buckets[i] != NULL) {
	    HashBucket *ptr = table->buckets[i];
	    while (ptr != NULL) {
		HashBucket *tmp = ptr->next;
		hashBucketFree(ptr, itemFree);
		ptr = tmp;
	    }
	}
    }

    psFree(table->buckets);
    psFree(table);
}

/*****************************************************************************/
/*
 * Here's the routine to do the work of insertion/retrieval/removal
 *
 * We need itemFree if the key is already in use and we're inserting
 *
 * N.b. this is NOT a good hash function! See Knuth for some better ones
 */
static void *doHashWork(
    psHash *table,			// table to insert in
    const char *key,			// key to use
    void *data,				// data to insert,
					// or (if NULL) retrieve/remove
    int remove,				// remove the item from the list?
    void (*itemFree)(void *item))	// how to free hashed data
					// or NULL
{
    long int hash = 1;

    for (int i = 0, len = strlen(key); i < len; i++) {
	hash = (hash << 1) ^ key[i];
    }

    hash &= (table->nbucket - 1);

    HashBucket *ptr = table->buckets[hash];
    /*
     * We've found the correct hash bucket, now we need to know what to do
     */
    if (data == NULL) {			// retrieve/remove
	if (remove) {
	    HashBucket *optr = ptr;
	    while (ptr != NULL) {
		if (strcmp(key, ptr->key) == 0) { // found it!
		    void *data = ptr->data;
		    optr->next = ptr->next;

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

		    psFree(ptr->key);
		    psFree(ptr);

		    return psMemDecrRefCounter(data); // return data
		}

		optr = ptr;
		ptr = ptr->next;
	    }
	} else {
	    while (ptr != NULL) {
		if (strcmp(key, ptr->key) == 0) { // found it!
		    return ptr->data;
		}
		
		ptr = ptr->next;
	    }
	}

	return NULL;			// not in hash
    } else {				// insert
	while (ptr != NULL) {
	    if (strcmp(key, ptr->key) == 0) { // found it!
		if (itemFree == NULL) {
		    return NULL;	// can't insert
		}			

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

		itemFree(psMemDecrRefCounter(ptr->data));
		ptr->data = psMemIncrRefCounter(data);

		return data;
	    }

	    ptr = ptr->next;
	}
	/*
	 * Not found, so insert at the front of the list
	 */
	table->buckets[hash] = hashBucketAlloc(key, data, table->buckets[hash]);

	return data;
    }
}    

/*****************************************************************************/
/*
 * Insert a value into a hash table
 */
void *psHashInsert(psHash *table,	// table to insert in
		   const char *key,	// key to use
		   void *data,		// data to insert
		   void (*itemFree)(void *item)) // how to free hashed data;
					// or NULL
{
    return doHashWork(table, key, data, 0, itemFree);
}

/*****************************************************************************/
/*
 * Lookup a value in a hash table
 */
void *psHashLookup(psHash *table,	// table to lookup key in
		   const char *key)	// key to lookup
{
    return doHashWork(table, key, NULL, 0, NULL);
}

/*****************************************************************************/
/*
 * Remove and return a value from a hash table
 */
void *psHashRemove(psHash *table,	// table to lookup key in
		   const char *key)	// key to lookup
{
    return doHashWork(table, key, NULL, 1, NULL);
}
