// This file is a part of the Framsticks GDK.
// Copyright (C) 1999-2014  Maciej Komosinski and Szymon Ulatowski.  See LICENSE.txt for details.
// Refer to http://www.framsticks.com/ for further information.

#include "hashtable.h"

int HashTable::hash(const char *s)
{
int h=0;
char c;
while(c=*(s++))
    h=31*h+c;
return h&0x7fffffff;
}

void HashTable::init(int initsize,float lo)
{
size=initsize;
load=lo;
threshold=(int)(load*(float)size);
tab=(HashEntry**)calloc(size,sizeof(HashEntry*));
count=0;
sync=0;
}

void HashTable::rehash(int newsize)
{
if (newsize==size) return;
HashEntry **newtab=(HashEntry**)calloc(newsize,sizeof(HashEntry*));
HashEntry **te=tab,*e,*ne;
int i;
for (int s=size;s>0;s--,te++)
    for (e=*te;e;)
	{
	    ne=e; e=e->next;
	    i=ne->hash%newsize;
	    ne->next=newtab[i];
	    newtab[i]=ne;
	}
free(tab);
tab=newtab;
size=newsize;
threshold=int(load*(float)size);
sync++;
}

void HashTable::clear()
{
HashEntry *e,**te,*next;
int n;
for (n=size,te=tab;n>0;n--,te++)
	for (e=*te;e;e=next)
		{
		next=e->next;
		delete e;
		}
if (tab) free(tab);
tab=0; size=0;
sync++;
}

HashTable::~HashTable()
{
clear();
}

void* HashTable::put(const SString& key,void *value)
{
int h=hash(key);
int i=h%size;
for (HashEntry *e=tab[i];e;e=e->next)
    {
    if (e->key==key)
	{
	void *v=e->value;
	e->value=value;
	return v;
	}
    }
if (count>=threshold) { rehash(2*size+1); i=h%size; }
HashEntry *e=new HashEntry(h,key,value);
e->next=tab[i];
tab[i]=e;
count++;
sync++;
return 0;
}

void* HashTable::remove(const SString& key)
{
int i=hash(key)%size;
HashEntry **ptr=tab+i,*e;
for (;e=*ptr;ptr=&e->next)
    {
    if (e->key==key)
	{
	*ptr=e->next;
	void *v=e->value;
	delete e;
	count--;
	sync++;
	return v;
	}
    }
return 0;
}

void* HashTable::remove(HashEntryIterator& it)
{
if (!it.entry) return 0;
HashEntry **ptr=tab+it.hashindex,*e;
for (;e=*ptr;ptr=&e->next)
    {
    if (e == it.entry)
	{
	it++;
	*ptr=e->next;
	void *v=e->value;
	delete e;
	count--;
	sync++;
	it.sync++;
	return v;
	}
    }
   return NULL; 
}

void* HashTable::get(const SString& key,int *reallygot)
{
int i=hash(key)%size;
for (HashEntry *e=tab[i];e;e=e->next)
	if (e->key==key) {if (reallygot) *reallygot=1; return e->value;}
return 0;
}

/////////

void HashEntryIterator::findNext()
{
while (hashindex < (ht->size-1))
	{
	hashindex++;
	if (entry=ht->tab[hashindex]) return;
	}
}


void HashEntryIterator::operator++()
{
if (entry) entry=entry->next;
if (!entry) findNext();
}

//////////////////////////

void HashTable::debugprint()
{
printf("HashTable: %d/%d (max %d)\n",count,size,threshold);
HashEntry *e,**te;
int n;
for (n=0,te=tab;n<size;n++,te++)
	if (e=*te)
	{
	printf(" %d:",n);
	for (;e;e=e->next)
		printf(" (%x)%s=%p",e->hash,(const char*)e->key,e->value);
	printf("\n");
	}
}

/**
stats[0]=buckets used
stats[1]=min keys in bucket
stats[2]=avg keys in bucket
stats[3]=max keys in bucket
 */
void HashTable::getstats(float *stats)
{
HashEntry *e,**te;
int used=0, ma=0, mi=count;
int c,n;
for (n=size,te=tab;n>0;n--,te++)
	{
	c=0;
	for (e=*te;e;e=e->next) c++;
	if (c>ma) ma=c;
	if ((c<mi)&&(c>0)) mi=c;
	if (c>0) used++;
	}
stats[0]=(float)used;
stats[1]=(float)((mi==count)?0:mi);
stats[2]=(float)count/(float)used;
stats[3]=(float)ma;
}