#include "util.h"

#include <string.h>
#include <math.h>

#ifndef NULL
#define NULL ((void *)(0))
#endif // NULL

// -- HashMap --

static unsigned int map_index(MapNode *,unsigned int,unsigned long,
                              const char *);

// Private

unsigned int map_index(MapNode *nodes, unsigned int size, unsigned long hash,
                       const char *key)
{
  unsigned int offset = hash % size;
  unsigned int i = offset;
  unsigned int roundtrip = 0xffffffff;  
  while (nodes[i].value &&
         nodes[i].hash != hash &&
         strcmp(nodes[i].key,key) != 0)
  {
    if (1 < offset)
      offset = (offset >> 1); // divide by 2
    else if (roundtrip == 0xffffffff)
      roundtrip = i;
    i = ((i + offset) % size);
    if (i == roundtrip)
      return 0xffffffff;
  }
  return i;
}

// Public

unsigned long map_hash(const char *str)
{
  // djb2
  unsigned long hash = 5381l; // x_0
  /* 5381 is 709th prime, 
     709 is 127th prime,
     127 is 31st prime, etc. */
  int ch;
  while ((ch = (int)(*str++)))
    hash = ((hash << 5) + hash) + ch; // x_i where 0 < i
  /* above is equivelant of (hash * 33 + ch)
     why 33? nobody knows exactly
     but it's likely due to (2^4)+1
     being good for hashing */
  return hash;
}

void * map_get(Map *map, const char *key)
{
  unsigned int idx;
  unsigned long hash = map_hash(key);

  idx = map_index(map->nodes, map->size, hash, key);
  if (idx == 0xffffffff)
    return NULL;
  return map->nodes[idx].value;
}

Map * map_put(Map *map, const char *key, void *value)
{
  static const unsigned int START_SIZE = ((unsigned int)0x0000000f);
  static const unsigned int MAX_SIZE =   ((unsigned int)0xf0000000);
  unsigned long hash;
  unsigned int i, idx;
  unsigned int key_length = (unsigned int)(strlen(key) * sizeof(char));
  if (NODEKEY_MAXLEN < key_length)
    return (Map *)NULL;
  
  if (!map)
  {
    map = (Map *)calloc(1,sizeof(Map));
    map->size = START_SIZE;
    map->count = 0;
    map->nodes = (MapNode *)calloc(map->size,sizeof(MapNode));
    for (i = 0; i < map->size; i++)
      map->nodes[i].value = NULL;
  }
  else if (map->count == map->size)
  {
    unsigned int new_size;
    MapNode *old_map, *new_map;

    new_size = (unsigned int)((((unsigned long)map->size) << 1) & 0xffffffff);
    if (!new_size)
      new_size = MAX_SIZE;
    if (new_size == map->size)
      return (Map *)NULL;
    
    new_map = (MapNode *)calloc(new_size, sizeof(MapNode));
    for (i = 0; i < new_size; i++)
      new_map[i].value = NULL;

    for (i = 0; i < map->size; i++)
    {
      if (map->nodes[i].value)
      {
        unsigned int index =
          map_index(new_map, new_size, map->nodes[i].hash,
                    map->nodes[i].key);
        if (index == 0xffffffff)
        {
          free(new_map);
          return (Map *)NULL;
        }

        memcpy(new_map[index].key, map->nodes[i].key, NODEKEY_MAXLEN);
        new_map[index].key_length = map->nodes[i].key_length;
        new_map[index].hash = map->nodes[i].hash;
        new_map[index].value = map->nodes[i].value;
      }
    }

    old_map = map->nodes;
    for (i = 0; i < map->size; i++)
      old_map[i].value = NULL;

    map->nodes = new_map;
    map->size += map->size;
    
    free(old_map);
  }

  map->count += 1;

  hash = map_hash(key);
  idx = map_index(map->nodes, map->size, hash, key);
  if (idx == 0xffffffff)
    return (Map *)NULL;

  for (i = 0; i < NODEKEY_MAXLEN; i++)
    map->nodes[idx].key[i] = '\0';

  map->nodes[idx].hash = hash;
  map->nodes[idx].value = value;
  map->nodes[idx].key_length = key_length;
  memcpy(map->nodes[idx].key, key, map->nodes[idx].key_length);
  
  return map;
}

void * map_remove(Map *map, const char *key)
{
  void *value;
  unsigned long hash = map_hash(key);
  unsigned int idx = map_index(map->nodes, map->size, hash, key);
  if (idx == 0xffffffff)
    return NULL;

  value = map->nodes[idx].value;
  if (value)
    map->nodes[idx].value = NULL;
  return value;
}