#include "hashmap.h"
#include <stdio.h>
#include <stdlib.h>

/* this should be prime */
#define TABLE_STARTSIZE 1021

#define ACTIVE 1

typedef struct {
  void* data;
  int flags;
  long key;
} hEntry;

struct s_hashmap{
  hEntry* table;
  long size, count;
};

static unsigned long isPrime(unsigned long val)
{
  int i, p, exp, a;
  
  for (i = 9; i--;)
  {
    a = (rand() % (val-4)) + 2;
    p = 1;
    exp = val-1;
    while (exp)
    {
      if (exp & 1)
        p = (p*a)%val;
      
      a = (a*a)%val;
      exp >>= 1;
    }
    
    if (p != 1)
      return 0;
  }
  
  return 1;
}

static int findPrimeGreaterThan(int val)
{
  if (val & 1)
    val+=2;
  else
    val++;
  
  while (!isPrime(val))
    val+=2;
  
  return val;
}

static void rehash(hashmap* hm)
{
  long size = hm->size;
  hEntry* table = hm->table;
  
  hm->size = findPrimeGreaterThan(size<<1);
  hm->table = (hEntry*)calloc(sizeof(hEntry), hm->size);
  hm->count = 0;
  
  while(--size >= 0)
    if (table[size].flags == ACTIVE)
      hashmapInsert(hm, table[size].data, table[size].key);
  
  free(table);
}

hashmap* hashmapCreate(int startsize)
{
  hashmap* hm = (hashmap*)malloc(sizeof(hashmap));
  
  if (!startsize)
    startsize = TABLE_STARTSIZE;
  else
    startsize = findPrimeGreaterThan(startsize-2);
  
  hm->table = (hEntry*)calloc(sizeof(hEntry), startsize);
  hm->size = startsize;
  hm->count = 0;
  
  return hm;
}

void hashmapInsert(hashmap* hash, const void* data, unsigned long key)
{
  long index, i, step;
  
  if (hash->size <= hash->count)
    rehash(hash);
  
  do
  {
    index = key % hash->size;
    step = (key % (hash->size-2)) + 1;
    
    for (i = 0; i < hash->size; i++)
    {
      if (hash->table[index].flags & ACTIVE)
      {
        if (hash->table[index].key == key)
        {
          hash->table[index].data = (void*)data;
          return;
        }
      }
      else
      {
        hash->table[index].flags |= ACTIVE;
        hash->table[index].data = (void*)data;
        hash->table[index].key = key;
        ++hash->count;
        return;
      }
      
      index = (index + step) % hash->size;
    }
    
    /* it should not be possible that we EVER come this far, but unfortunately
       not every generated prime number is prime (Carmichael numbers...) */
    rehash(hash);
  }
  while (1);
}

void* hashmapRemove(hashmap* hash, unsigned long key)
{
  long index, i, step;
  
  index = key % hash->size;
  step = (key % (hash->size-2)) + 1;
  
  for (i = 0; i < hash->size; i++)
  {
    if (hash->table[index].data)
    {
      if (hash->table[index].key == key)
      {
        if (hash->table[index].flags & ACTIVE)
        {
          hash->table[index].flags &= ~ACTIVE;
          --hash->count;
          return hash->table[index].data;
        }
        else /* in, but not active (i.e. deleted) */
          return 0;
      }
    }
    else /* found an empty place (can't be in) */
      return 0;
    
    index = (index + step) % hash->size;
  }
  /* everything searched through, but not in */
  return 0;
}

void* hashmapGet(hashmap* hash, unsigned long key)
{
  if (hash->count)
  {
    long index, i, step;
    index = key % hash->size;
    step = (key % (hash->size-2)) + 1;
    
    for (i = 0; i < hash->size; i++)
    {
      if (hash->table[index].key == key)
      {
        if (hash->table[index].flags & ACTIVE)
          return hash->table[index].data;
        break;
      }
      else
        if (!hash->table[index].data)
          break;
      
      index = (index + step) % hash->size;
    }
  }
  
  return 0;
}

long hashmapCount(hashmap* hash)
{
  return hash->count;
}

void hashmapDelete(hashmap* hash)
{
  free(hash->table);
  free(hash);
}