#include <string.h>
#include <stdio.h>
#include "ht.h"

#define HT_REHASH_THRESHOLD 0.5

struct ht_s {
  NUM *keys;
  void **values;
  UNUM capability;
  /* REVIEW: What is the purpose of SIZE? */
  int size;
};

/* SIZE is a hint to the number of elements that might be put in the
   table.  In fact we will allocate more memory than this number, as a
   hash table works better if it is not fully used. */
ht *
new_ht(UNUM size)
{
  ht *htp = MYALLOC(ht, 1);

  if (htp == NULL) {
    fleprintf0("Fail to malloc\n");
    return NULL;
  }

  htp->capability = (size<<1)+(size>>1);
  htp->size = 0;
  htp->keys = MYALLOC(NUM, htp->capability);

  if (htp->keys == NULL) {
    fleprintf0("Fail to malloc\n");
    free(htp);
    return NULL;
  }

  htp->values = MYALLOC(void*, htp->capability);

  if (htp->values == NULL) {
    fleprintf0("Fail to malloc\n");
    free(htp->keys);
    free(htp);
    return NULL;
  }

  /* Initialize the keys to be -1 and the values to be NULL */
  memset(htp->keys, 0xff, sizeof (NUM) * htp->capability);
  memset(htp->values, 0, sizeof (NUM) * htp->capability);

  return htp;
}

void
destroy_ht(ht * restrict htp, int flag)
{
  switch (flag) {
  case 1:
    for (UNUM i = 0; i < htp->capability;)
      free(*(htp->values+i++));
    break;
  case 2:
    free(*(htp->values));
    break;
  default:
    break;
  }

  free(htp->values);

  free(htp->keys);

  free(htp);
}

static BOOL
ht_expand(ht *htp)
{
  NUM oldcap = htp->capability;
  htp->capability <<= 1;
  htp->capability++;

  NUM *newkeys = realloc(htp->keys, htp->capability);

  if (newkeys == NULL) {
    fleprintf0("Fail to realloc\n");
    return 1;
  }

  htp->keys = newkeys;

  memset(htp->keys+oldcap, 0xff,
         sizeof (NUM) * (htp->capability - oldcap));

  void **newvalues = realloc(htp->values, htp->capability);

  if (newvalues == NULL) {
    fleprintf0("Fail to realloc\n");
    return 1;
  }

  htp->values = newvalues;

  memset(htp->values+oldcap, 0,
         sizeof(NUM) * (htp->capability - oldcap));

  return 0;
}

BOOL
ht_insert(ht *htp, NUM key, void *value)
{
  if (htp->size+1 >= HT_REHASH_THRESHOLD * htp->capability)
    ht_expand(htp);

  NUM ikey = key % htp->capability;

  /* linear probing */
  for (NUM count = 0;
       count < htp->capability * HT_REHASH_THRESHOLD &&
         *(htp->keys+ikey) > 0 &&
         *(htp->keys+ikey) != key;
       count++)
    ikey = (ikey + 1) % htp->capability;

  if (*(htp->keys+ikey) < 0) {
    /* not inserted before */
    *(htp->keys+ikey) = key;
    *(htp->values+ikey) = value;
    (htp->size)++;
  } else if (*(htp->keys+ikey) == key) {
    *(htp->values+ikey) = value;
  } else {
    fleprintf("Fail to probe an appropriate slot for %ld, "
              "the result ikey = %ld\n",
              key, ikey);
    return 1;
  }

  /* fleprintf("ikey = %ld, size = %d, capability = %llu\n",
   *           ikey, htp->size, htp->capability); */

  return 0;
}

BOOL
ht_delete(ht * const restrict htp, NUM key, int flag)
{
  NUM ikey = key % htp->capability;

  /* linear probing */
  for (NUM count = 0;
       count < htp->capability * HT_REHASH_THRESHOLD &&
         *(htp->keys+ikey) > 0 &&
         *(htp->keys+ikey) != key;
       count++)
    ikey = (ikey + 1) % htp->capability;

  if (*(htp->keys+ikey) < 0) {
    /* not inserted before */
    return 0;
  } else if (*(htp->keys+ikey) == key) {
    (htp->size)--;
    *(htp->keys+ikey) = -1;
    if (flag) {
      free(*(htp->values+ikey));
      *(htp->values+ikey) = NULL;
    }
    return 0;
  } else {
    fleprintf("Fail to probe an appropriate slot for %ld, "
              "the result ikey = %ld\n",
              key, ikey);
    return 1;
  }

  return 0;
}

void *
ht_find(ht * const restrict htp, NUM key)
{
  NUM ikey = key % htp->capability;

  /* linear probing */
  for (NUM count = 0;
       count < htp->capability * HT_REHASH_THRESHOLD &&
         *(htp->keys+ikey) > 0 &&
         *(htp->keys+ikey) != key;
       count++)
    ikey = (ikey + 1) % htp->capability;

  if (*(htp->keys+ikey) == key)
    return *(htp->values+ikey);
  else if (*(htp->keys+ikey) > 0)
    fleprintf("Fail to probe an appropriate slot for %ld, "
              "with the result ikey = %ld\n",
              key, ikey);

  return NULL;
}