/**********************************************************************
 * Copyright (c) 2005, 2009 Scapa Technologies Limited and others
 * All rights reserved. This program and the accompanying materials
 * are made available under the terms of the Eclipse Public License v1.0
 * which accompanies this distribution, and is available at
 * http://www.eclipse.org/legal/epl-v10.html
 * 
 * Contributors: 
 * Scapa Technologies Limited - Initial API and implementation
 *
 * Hoang M. Nguyen, Intel - Modified to support integer as key and (void *) as value
 *
 * $Id: hashtable.c,v 1.8 2009/09/10 21:17:40 jcayne Exp $
 *
 **********************************************************************/


#include "tptp/TPTPUtils.h"
#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
#include <string.h>
#include "tptp/hashtable.h"
#include "tptp/system.h"


/**  number to rehash (e.g. increase the size of the hash table) */
#define LOAD_FACTOR 0.75f


/* internal function prototypes */
long int getHash(tptp_uint32 key);
int match(Entry* entry, tptp_uint32 key) ;



/**
 *********************************************************
 *
 * @brief
 *    return indicator whether a given key matches the given entry
 *
 * @return
 *    0 -  no match
 *    nonzero - match
 *
 * @note 
 *    INTERNAL - UNSYNCHRONIZED
 *
 *********************************************************/

int match(Entry* entry, tptp_uint32 key) {
	int isEqual = 0 ;

	if (entry->key == key) {
		isEqual = 1 ;
	}
	return (isEqual) ;
}



/**
 *********************************************************
 *
 * @brief
 *    return indicator whether a given hash table contains the entry
 *    of a given key
 *
 * @return
 *    0 -       does not contain
 *    nonzero - yes, it contains
 *
 * @note 
 *    SYNCHRONIZED
 *
 *********************************************************/

BOOL containsKey(HashTable* hasht, tptp_uint32 key)
{
	Entry* entry;
	Entry** tab;

	long int hash;
	long int index;

	XMutexClaim(&hasht->mutex);

	tab = hasht->table;

	hash = getHash(key);
	index = (hash & 0x7FFFFFFF) % hasht->table_len;

	for (entry = tab[index]; entry != NULL; entry = (Entry*)entry->next) 
	{
		if (hash == entry->hash) 
		{
			if (match(entry,key)) 
			{
				XMutexRelease(&hasht->mutex);
				return TRUE;
			}
		}
	}

	XMutexRelease(&hasht->mutex);
	return FALSE;
}



/**
 *********************************************************
 *
 * @brief
 *    return the list of all keys in the hash table to the given array
 *
 * @return
 *    the number of keys in the hash table
 *
 * @note 
 *    SYNCHRONIZED
 *
 *********************************************************/

int tableKeysAsList(HashTable* table, tptp_uint32 list[], int list_size) 
{
	int i;
	int n;
	Entry* next;
	Entry* e;

	n = 0;

	XMutexClaim(&table->mutex);

	for (i = 0; i < table->table_len; i++) {
		if (table->table[i] != NULL) {

			//run down the list of entries and add them to the list_size
			e = table->table[i];
			
			while (e != NULL) {
				next = e->next;

				//add entry e to the list
				list[n++] = e->key;

				if (n == list_size) {
					XMutexRelease(&table->mutex);
					return list_size*2;
				}

				e = next;
			}

		}
	}

	XMutexRelease(&table->mutex);
	return n;
}



/**
 *********************************************************
 *
 * @brief
 *    Allocate a new hash entry
 *
 * @return
 *    Pointer to the newly allocated entry
 *
 * @note 
 *    INTERNAL - UNSYNCHRONIZED
 *
 *********************************************************/

Entry* createEntry(long int hash, tptp_uint32 key, Entry_value_ptr_t pValue, Entry* next) 
{
	Entry* e;

	e = (Entry*)tptp_malloc(sizeof(Entry));

	if (e == NULL) return NULL;

	e->hash = hash;

	e->key = key ;
	e->pValue = pValue;
	e->next = next;

	return e;
}



/**
 *********************************************************
 *
 * @brief
 *    Free a given entry
 *
 * @return
 *    The next entry in the list
 *
 * @note 
 *    INTERNAL - UNSYNCHRONIZED
 *
 *********************************************************/

void deleteEntry(Entry* e) {
	Entry* next;

	while (e != NULL) {
		next = e->next;

		if (e->pValue != NULL)
		{
			tptp_free(e->pValue) ;
			e->pValue = NULL ;
		}

		tptp_free(e);

		e = next;
	}
}	



/**
 *********************************************************
 *
 * @brief
 *    Create the hash table.
 *    This is a dynamic table where the size is automatically expanding
 *    to accommodate the increasing number of entries.
 *
 * @return
 *    The pointer to the newly created hash table
 *
 * @note 
 *    UNSYNCHRONIZED
 *
 *********************************************************/

HashTable* tableCreate() 
{
	HashTable* hasht;
	long int initialCapacity = 101;

	hasht = (HashTable*) tptp_malloc(sizeof(HashTable));

	hasht->table = (Entry**)tptp_malloc(initialCapacity * sizeof(Entry*));
	hasht->table_len = initialCapacity;

	memset(hasht->table,'\0',hasht->table_len * sizeof(Entry*));

	hasht->count = 0;

	hasht->threshold = (long int)(initialCapacity * LOAD_FACTOR);

	XMutexCreate(&hasht->mutex);

	return hasht;
}



/**
 *********************************************************
 *
 * @brief
 *    delete the given hash table.
 *    Note that this function will also free all storages holding
 *    the entry as well as the value.
 *
 * @note 
 *    UNSYNCHRONIZED
 *
 *********************************************************/

void tableDelete(HashTable* hasht) 
{
	int i = 0;

	XMutexDelete(&hasht->mutex);

	for (i = 0; i < hasht->table_len; i++) {
		if (hasht->table[i] != NULL) {
			deleteEntry(hasht->table[i]);
			hasht->table[i] = NULL;
		}
	}

	tptp_free(hasht->table);
	tptp_free(hasht);

}



/**
 *********************************************************
 *
 * @brief
 *    clear the hash table by freeing all entries it contains.
 *    Note that this function will also free all storages holding
 *    the entry as well as the value.
 *
 * @note 
 *    SYNCHRONIZED
 *
 *********************************************************/

void tableClear(HashTable* hasht) {
	int i = 0;

	XMutexClaim(&hasht->mutex);

	hasht->count = 0;

	for (i = 0; i < hasht->table_len; i++) {
		if (hasht->table[i] != NULL) {
			deleteEntry(hasht->table[i]);
			hasht->table[i] = NULL;
		}
	}

	XMutexRelease(&hasht->mutex);
}



/**
 *********************************************************
 *
 * @brief
 *    return the number of entries in the table
 *
 * @note 
 *    UNSYNCHRONIZED
 *
 *********************************************************/
int tableSize(HashTable* hasht) {
	return hasht->count;
}



/**
 *********************************************************
 *
 * @brief
 *    return the hash number of a given key
 *
 * @return
 *    0 -  no match
 *    nonzero - match
 *
 * @note 
 *    INTERNAL - UNSYNCHRONIZED
 *
 *********************************************************/
long int getHash(tptp_uint32 key) {
	return key;
}



/**
 *********************************************************
 *
 * @brief
 *    retrieve the entry in the table from the given key
 *
 * @return
 *    pointer to the matched entry if there is a match
 *    NULL if not found
 *
 * @note 
 *    SYNCHRONIZED
 *
 *********************************************************/

Entry_value_ptr_t tableGet(HashTable* hasht, tptp_uint32 key) {
	Entry* entry;
	Entry** tab;

	long int hash;
	long int index;

	XMutexClaim(&hasht->mutex);

	tab = hasht->table;

	hash = getHash( key );
	index = (hash & 0x7FFFFFFF) % hasht->table_len;

	for (entry = tab[index]; entry != NULL; entry = (Entry*)entry->next) {
		if (hash == entry->hash) {
			if (match(entry,key)) {

				XMutexRelease(&hasht->mutex);
				return entry->pValue;
			}
		}
	}

	XMutexRelease(&hasht->mutex);
	return (Entry_value_ptr_t)NULL;
}



/**
 *********************************************************
 *
 * @brief
 *    rehash the table (because it exceeds its load)
 *
 * @note 
 *    UNSYNCHRONIZED
 *
 *********************************************************/

void tableRehash(HashTable* hasht) {
	int i;
	Entry* old;
	Entry* ent;
	long int index;

	long int oldCapacity;
	Entry** oldMap;

	long int newCapacity;
	Entry** newMap;

	oldCapacity = hasht->table_len;
	oldMap = hasht->table;

	newCapacity = (oldCapacity * 2) + 1;
	newMap = (Entry**)tptp_malloc(newCapacity * sizeof(Entry*));

	hasht->threshold = (long int)(newCapacity * LOAD_FACTOR);
	hasht->table = newMap;
	hasht->table_len = newCapacity;

	memset(hasht->table,'\0',hasht->table_len * sizeof(Entry*));

	for (i = oldCapacity; i-- > 0;) {
		for (old = oldMap[i]; old != NULL; ) {
			ent = old;
			old = (Entry*)old->next;

			index = (ent->hash & 0x7FFFFFFF) % newCapacity;
			ent->next = newMap[index];
			newMap[index] = ent;
		}
		oldMap[i] = NULL;
	}
	tptp_free(oldMap);
}



/**
 *********************************************************
 *
 * @brief
 *    add a given entry (key & value) to the given hash table
 *
 * @return
 *    NULL if this is a new key
 *    Pointer of the existing value (being replaced) if the key is already there
 *
 * @note 
 *    SYNCHRONIZED
 *
 *********************************************************/

Entry_value_ptr_t tablePut(HashTable* hasht, tptp_uint32 key, Entry_value_ptr_t pValue) 
{
	Entry** tab;
	Entry* ent;

	long int hash = getHash( key );
	long int index;

	XMutexClaim(&hasht->mutex);

	tab = hasht->table;

	index = (hash & 0x7FFFFFFF) % hasht->table_len;

	for (ent = tab[index]; ent != NULL; ent = (Entry*)ent->next) {
		if (hash == ent->hash) {
			if (match(ent,key)) {
				Entry_value_ptr_t old = ent->pValue;
				ent->pValue = pValue;

				XMutexRelease(&hasht->mutex);
				return old;
			}
		}
	}

	if (hasht->count >= hasht->threshold) 
	{
		tableRehash(hasht);
		tab = hasht->table;
		index = (hash & 0x7FFFFFFF) % hasht->table_len;
	}

	ent = createEntry(hash,key,pValue,tab[index]);
	tab[index] = ent;
	
	hasht->count++;

	XMutexRelease(&hasht->mutex);
	return (Entry_value_ptr_t)NULL;
}



/**
 *********************************************************
 *
 * @brief
 *    remove the entry with the given key from the table.
 *
 *    This call will also free the value of the entry
 *    if it is not NULL.
 *
 * @return
 *    FALSE - Key is not found
 *    TRUE  - Sucessfully remove
 *
 * @note 
 *    SYNCHRONIZED
 *
 *********************************************************/
BOOL tableRemove(HashTable* hasht, tptp_uint32 key) 
{
	Entry* entry;
	Entry* prevEntry;
	Entry** tab;

	long int hash;
	long int index;

	XMutexClaim(&hasht->mutex);

	tab = hasht->table;

	hash = getHash(key);
	index = (hash & 0x7FFFFFFF) % hasht->table_len;

	prevEntry = NULL;
	for (entry = tab[index]; entry != NULL; entry = (Entry*)entry->next) 
	{
		if (hash == entry->hash) 
		{
			if (match(entry,key)) 
			{
				if (prevEntry == NULL)
					tab[index] = entry->next;
				else
					prevEntry->next = entry->next;

				entry->next = NULL;
				deleteEntry(entry);
				hasht->count--;
				XMutexRelease(&hasht->mutex);
				return TRUE;
			}
		}
		prevEntry = entry;
	}
	XMutexRelease(&hasht->mutex);
	return FALSE ;
}
