#include "hash.h"
#include "constants.h"
#include "packet.h"

int hashmem=0;
int flag2=0;
int visits=0;
int rounds=0;
int finds=0;
int inserts=0;

/* This is also defined in khash.c, so if changed should be changed
   in both files */
static unsigned long prime_list[]={
  2,3,5,11,23,53,73,101,127,151,173,211,223,251,271,307,331,353,373,401,
  421,449,479,503,523,557,571,601,631,653,673,701,727,751,773,809,823,
  853,877,907,929,953,977,1009,1097,1201,1301,1409,1511,1601,1709,1801,
  1901,2003,2111,2203,2309,2411,2503,2609,2707,2801,2903,3001,3109,3203, 
  3301,3407,3511,3607,3701,3803,3907,4001,4111,4201,4327,4409,4507,4603,
  4703,4801,4903,5003,5101,5209,5303,5407,5501,5591,5701,5801,5903,6007,
  6101,6203,6301,6397,6521,6607,6701,6803,6907,7001,7103,7207,7307,7411,
  7507,7603,7703,7817,7901,8009,8101,8209,8311,8419,8501,8599,8699,8803,
  8923,9001,9103,9203,9311,9403,9511,9601,9719,9803,9901,10007,11003,12049,
  13033,14009,15013,16001,17011,18013,19001,20011,21089,22003,23003,24001,
  25013,26003,27011,28001,29009,30011,31013,32003,33029,34019,35023,36011,
  36943,37963,38993,40009,41051,42013,43003,44087,45083,46147,47161,48179,
  49169,50119,51001,52009,53069,54059,55001,56003,57037,58013,59023,60029,
  61091,62137,63277,64223,65089,66029,67103,68059,69193,70249,71059,72031,
  73039,74161,75011,76031,77153,78139,79043,80077,81049,82073,83203,84589,
  85447,86477,87281,88379,89101,90071,91159,92083,93053,94111,95153,96181,
  97301,98041,99109,100003};
static int prime_list_length = 222;		 

/* Function that tests if number is prime */
int test_prime(long num)
{
  long i;
  for(i=2;i<num;i++)
    if (num % i == 0)
      return FALSE;
  return TRUE;
}

/* Creating hash table 
   input: object to store the hash table in,
          desired size, minimum and maximum size,
	  and load factors for rehashing, key size,
          function that decides whether to clean the entry,
	  function that compares entries,
	  first and second hash function */
void create_hash(struct hash_table** HT, unsigned long size, 
		 unsigned long min_size, unsigned long max_size, 
		 double rlfh, double rlfl, int key_size, int data_size,
		 int (*cf)(void*), int (*cmp)(void*,void*),
		 unsigned long (*hash1)(void*,unsigned long)) 
{
  int i;
  
  struct hash_table* HashTable;

  /* Allocate space */
  HashTable = malloc(sizeof(struct hash_table));
  hashmem += (int)sizeof(struct hash_table);

  /* Test if desired sizes are prime and if not
     find prime numbers closest to the values that are given */

  if (!test_prime(size))
    {
      for(i=0;i<prime_list_length && size>prime_list[i];i++);
      if (i != prime_list_length)
	size = prime_list[i];
    }

  if (!test_prime(min_size))
    {
      for(i=0;i<prime_list_length && min_size>prime_list[i];i++);
      if (i != prime_list_length)
	min_size = prime_list[i];
    }

  if (!test_prime(max_size))
    {
      for(i=0;i<prime_list_length && max_size>prime_list[i];i++);
      if (i != prime_list_length)
	max_size = prime_list[i];
    }

  HashTable->entries = malloc(size*sizeof(struct hash_entry));
  hashmem += size*sizeof(struct hash_entry);
  
  /* Set all keys to EMPTY */
  HashTable->size = size;
  HashTable->filled = 0;
  HashTable->FULL_ALERT = FALSE;
  HashTable->data_size = data_size;
  HashTable->key_size = key_size;
  HashTable->min_size = min_size;
  HashTable->max_size = max_size;
  HashTable->clean = cf;
  HashTable->compare = cmp;
  HashTable->hash1 = hash1;
  for(i=0;(unsigned long)i<size;i++)
    {
      HashTable->entries[i].key = malloc(HashTable->key_size);
      HashTable->entries[i].data = malloc(HashTable->data_size);
      HashTable->entries[i].state = EMPTY;
      if (i>0)
	HashTable->entries[i].prev = i-1;
      else
	HashTable->entries[i].prev = NOT_FOUND;
      if ((unsigned long)i<size-1)
	HashTable->entries[i].next = i+1;
      else
	HashTable->entries[i].next = NOT_FOUND;
    }
  HashTable->empty = 0;
  *HT = HashTable;
}

/* Function that cleans unnecessary entries */
void clean_table(struct hash_table* HashTable)
{
  int i;
  for(i=0;(unsigned long)i<HashTable->size;i++)
      if (HashTable->entries[i].state == VALID && 
	  HashTable->clean(HashTable->entries[i].data))
	{
	  HashTable->entries[i].state = DELETED;
	  HashTable->filled--;
	}
}

/* Insert new key
   input: void* key, hash table to modify
          void* data to insert
   output: long index where key is stored, -1 if
           empty slot can not be found */   
long insert(void* key, struct hash_table* HashTable, int* outcome)
{
  unsigned long index;
  int trial = 0;
  visits++;
  inserts++;
  rounds++;

  /* If hash is full, give up */
  if (HashTable->filled == HashTable->max_size)
    return NOT_FOUND;

  /* Get the index where this should be */
  index = (HashTable->hash1(key,HashTable->size)); 
  
  /* Check if there is collision */
  if (HashTable->entries[index].state == VALID)
    {
      int original;
      /* Check if by chance this data is inside */
      if(HashTable->compare(HashTable->entries[index].key, key))
	{
	  *outcome = EXISTING;
	  return index;
	}
      /* Use first empty slot for insert */
      original = index;
      index = HashTable->empty;
      HashTable->empty = HashTable->entries[index].next;
      HashTable->entries[HashTable->empty].prev = NOT_FOUND;
          
      /* Now follow value path and adjust the last pointer to point to 
	 new data */
      while (HashTable->entries[original].next != NOT_FOUND)
	{
	  original = HashTable->entries[original].next;
	}
      HashTable->entries[original].next = index;
      HashTable->entries[index].prev = original;
    }
  else if (HashTable->entries[index].state == EMPTY)
    {
      /* Fix the gap in the array of empty slots that will be created
	 now that we do this insert */
      int prev = HashTable->entries[index].prev;
      int next = HashTable->entries[index].next;
      if (prev != NOT_FOUND)
	{
	  HashTable->entries[prev].next = next;
	}
      else
	{
	  HashTable->empty = next;
	  HashTable->entries[HashTable->empty].prev = NOT_FOUND;
	}
       if (next != NOT_FOUND)
	 {
	   HashTable->entries[next].prev = prev;
	 }
      HashTable->entries[index].prev = NOT_FOUND;
    }
  /* Insert key */
  memcpy(HashTable->entries[index].key, key, HashTable->key_size);
  HashTable->entries[index].state = VALID;
  HashTable->entries[index].next = NOT_FOUND;
  HashTable->filled++;
  *outcome = NEW;

  /* Set FULL_ALERT flag if hash is more than 90% full */
  if (HashTable->size == HashTable->max_size 
      && (double)HashTable->filled/HashTable->size > FULL_ALERT_LF)
        HashTable->FULL_ALERT = TRUE;
  else
    HashTable->FULL_ALERT = FALSE;

  return index;
}

/* Find a key
   input: void* key, hash table to search
   output: long index where key is stored, 
           NOT_FOUND is returned if key is not in the table */   
long find(void* key, struct hash_table* HashTable)
{
  unsigned long index;
  int trial = 0;
  finds++;
  visits++;
  rounds++;
  /* Keep looking for the key */
  index = (HashTable->hash1(key,HashTable->size)); 
  
  if (HashTable->entries[index].state == EMPTY ||
      HashTable->entries[index].state == DELETED) 
    return NOT_FOUND;

  if (!HashTable->compare(HashTable->entries[index].key, key))
    {
      rounds++;
      do
	{
	  index = HashTable->entries[index].next;
	  if (index == NOT_FOUND)
	    return NOT_FOUND;
	}while(!HashTable->compare(HashTable->entries[index].key, key));
      return index;
    }
  return index;
}
	  
/* Delete a key
   input: void* key, hash table to modify
   output: long index where key was stored, 
           NOT_FOUND is returned if key is not in the table */   
long delete(void* key, struct hash_table* HashTable)
{
  long index;

  index = find(key, HashTable);
  if (index != NOT_FOUND)
    {
      /* Delete the key. We will move other values from
	 value list here and the last spot will go to empty list,
	 to its head because this is the simplest approach.
	 This is costly but the assumption is that delete is not 
	 a frequent operation. */
      int next = HashTable->entries[index].next;
      int curr = index;
      int prev = HashTable->entries[index].prev;
        while(next != NOT_FOUND)
	{
	  memcpy(HashTable->entries[curr].data,
		 HashTable->entries[next].data, HashTable->data_size);
	  memcpy(HashTable->entries[curr].key,
		 HashTable->entries[next].key, HashTable->key_size);
	  prev = curr;
	  curr = next;
	  next = HashTable->entries[curr].next;
	}
      HashTable->entries[curr].state = EMPTY;
      if (prev != NOT_FOUND)
	{
	  HashTable->entries[prev].next = NOT_FOUND;
	}
      HashTable->entries[curr].next = HashTable->empty;
      HashTable->entries[HashTable->empty].prev = curr;
      HashTable->empty = curr;
      HashTable->entries[HashTable->empty].prev = NOT_FOUND;
      
      HashTable->filled--;
      return index;
    }
  else
    return NOT_FOUND;
}

void reset_table(struct hash_table* HashTable)
{
  int i;
  /* Set all keys to EMPTY */
  HashTable->filled = 0;
  HashTable->FULL_ALERT = FALSE;
  for(i=0;(unsigned long)i<HashTable->size;i++)
    {
      HashTable->entries[i].state = EMPTY;
      if (i>0)
	HashTable->entries[i].prev = i-1;
      else
	HashTable->entries[i].prev = NOT_FOUND;
      if ((unsigned long)i<HashTable->size-1)
	HashTable->entries[i].next = i+1;
      else
	HashTable->entries[i].next = NOT_FOUND;
    }
  HashTable->empty = 0;
}