/**********************************************************************
 * Copyright (c) 2005, 2007 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
 * $Id: hashtable.c,v 1.2 2007/04/06 01:14:33 jkubasta Exp $
 * 
 * Contributors: 
 * Scapa Technologies Limited - Initial API and implementation
 **********************************************************************/


#include "stdio.h"
#include "stdlib.h"
#include "memory.h"
#include "string.h"
#include "hashtable.h"
#include "system.h"


#define LOAD_FACTOR 0.75f

//INTERNAL - UNSYNCHRONIZED
int match(Entry* entry, char* key) {
	int c = 0;
	while (entry->key[c] != '\0' && key[c] != '\0') {
		if (entry->key[c] != key[c]) return 0;
		c++;
	}
	if (entry->key[c] == key[c]) {
		return 1;
	}
	return 0;
}

//SYNCHRONIZED
BOOL containsKey(HashTable* hasht, char* key)
{
	Entry* entry;
	Entry** tab;

	long int hash;
	long int index;

	XMutexClaim(&hasht->mutex);

	tab = hasht->table;

	hash = getHash((char*)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;
}

//SYNCHRONIZED
int tableKeysAsList(HashTable* table, char** 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;
}

//
// Allocate a new entry
//
//INTERNAL - UNSYNCHRONIZED
Entry* createEntry(long int hash, char* key, XINT64 value, Entry* next) {
	Entry* e;
	int len = strlen(key)+1;

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

	if (e == NULL) return NULL;

	e->hash = hash;
	e->key = malloc(sizeof(char) * len);
	memcpy(e->key,key,len);
	e->value = value;
	e->next = next;

	return e;
}

//
// Deallocate an entry
//
//INTERNAL - UNSYNCHRONIZED
void deleteEntry(Entry* e) {
	Entry* next;

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

		free(e->key);
		free(e);

		e = next;
	}
}	

//create - UNSYNCHRONIZED
HashTable* tableCreate() {
	int i = 0;

	HashTable* hasht;
	long int initialCapacity = 11;

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

	hasht->table = (Entry**)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;
}

//delete - 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;
		}
	}

	free(hasht->table);
	free(hasht);

}

//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);
}

//no modification - UNSYNCHRONIZED
int tableSize(HashTable* hasht) {
	return hasht->count;
}

//INTERNAL - UNSYNCHRONIZED
long int getHash(char* key) {
	long int n;
	long int hash = 0;

	for (n = 0; key[n] != '\0'; n++) {
		hash = (hash*n)+key[n];
	}

	return hash;
}

//SYNCHRONIZED
XINT64 tableGet(HashTable* hasht, char* key) {
	Entry* entry;
	Entry** tab;

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

	XMutexClaim(&hasht->mutex);

	tab = hasht->table;

	hash = getHash((char*)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->value;
			}
		}
	}

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

//SYNCHRONIZED
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**)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;
	}
	free(oldMap);
}

//SYNCHRONIZED
XINT64 tablePut(HashTable* hasht, char* key, XINT64 value) {
	Entry** tab;
	Entry* ent;
//	long int hash = (long int)key;
	long int hash = getHash((char*)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)) {
				XINT64 old = ent->value;
				ent->value = value;

				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,value,tab[index]);
	tab[index] = ent;
	
	hasht->count++;

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

//SYNCHRONIZED
void tableRemove(HashTable* hasht, char* key) 
{
	Entry* entry;
	Entry* prevEntry;
	Entry** tab;

	long int hash;
	long int index;

	XMutexClaim(&hasht->mutex);

	tab = hasht->table;

	hash = getHash((char*)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;

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