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

#define HT_REHASH_THRESHOLD 0.5

/* 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 = NULL;
  SAFE_MALLOC(ht, htp, 1, return NULL;);

  htp->capability = (size<<1)+(size>>1);
  htp->size = 0;

  /* For safer clean up */
  htp->keys = NULL;
  htp->values = NULL;
  htp->indices = NULL;

  SAFE_MALLOC(NUM, htp->keys, htp->capability, goto cleanup;);

  SAFE_MALLOC(void*, htp->values, htp->capability, goto cleanup;);

  SAFE_MALLOC(NUM, htp->indices, htp->capability, goto cleanup;);

  /* 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 (void*) * htp->capability);
  /* Initialize indices to be -1 */
  memset(htp->indices, 0xff, sizeof (NUM) * htp->capability);

  return htp;

 cleanup:
  if (htp->keys) free(htp->keys);
  if (htp->values) free(htp->values);
  if (htp->indices) free(htp->indices);
  free(htp);
  return NULL;
}

void
destroy_ht(ht * restrict htp, HT_DESTROY_FLAG flag)
{
  switch (flag) {
  case DESTROY_EVERY_NO_SELF:
  case DESTROY_EVERY_SELF:
    for (NUM i = 0; i < htp->size;)
      free(*(htp->values+i++));
    break;
  case DESTROY_FIRST_NO_SELF:
  case DESTROY_FIRST_SELF:
    free(*(htp->values));
    break;
  default:
    break;
  }

  free(htp->values);

  free(htp->keys);

  free(htp->indices);

  switch (flag) {
  case DESTROY_NONE_SELF:
  case DESTROY_EVERY_SELF:
  case DESTROY_FIRST_SELF:
    free(htp);
    break;
  default:
    break;
  }
}

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

  NUM *keys = NULL, size = htp->size;
  void **values = NULL;

  if (size) {
    SAFE_MALLOC(NUM, keys, size, goto cleanup;);
    SAFE_MALLOC(NUM, values, size, goto cleanup;);

    memcpy(keys, htp->keys, sizeof(NUM) * size);
    memcpy(values, htp->values, sizeof(void*) * size);
  }

  SAFE_REALLOC(NUM, htp->keys, htp->capability, goto cleanup;);

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

  SAFE_REALLOC(void*, htp->values, htp->capability, goto cleanup;);

  memset(htp->values, 0, sizeof(void*) * htp->capability);

  SAFE_REALLOC(NUM, htp->indices, htp->capability, goto cleanup;);

  memset(htp->indices, 0xff, sizeof (NUM) * htp->capability);

  htp->size = 0;

  for (NUM i = 0; i < size; i++)
    ht_insert(htp, *(keys+i), *(values+i));

  if (keys) free(keys);
  if (values) free(values);

  return 0;

 cleanup:
  if (keys) free(keys);
  if (values) free(values);
  return 1;
}

BOOL
ht_insert(ht *htp, NUM key, void *value)
{
  if (htp->size+1 >= HT_REHASH_THRESHOLD * htp->capability) {
    if (ht_expand(htp)) {
      fleprintf0("Fail to expand\n");
      return 1;
    }
  }

  NUM ikey = key % htp->capability;

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

  if (*(htp->indices+ikey) < 0) {
    /* not inserted before */
    *(htp->indices+ikey) = htp->size;

    /* Store the key and the value in the array. */
    *(htp->keys+htp->size) = key;
    *(htp->values+htp->size) = value;

    (htp->size)++;
  } else if (*(htp->keys+*(htp->indices+ikey)) == key) {
    *(htp->values+*(htp->indices+ikey)) = value;
  } else {
    fleprintf("Fail to probe an appropriate slot for %ld, "
              "the result ikey = %ld, last index = %ld, "
              "last key = %ld\n",
              key, ikey, *(htp->keys+*(htp->indices+ikey)),
              *(htp->indices+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->indices+ikey) > 0 &&
         *(htp->keys+*(htp->indices+ikey)) != key;
       count++)
    ikey = (ikey + 1) % htp->capability;

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

  return 0;
}

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

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

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

  return NULL;
}

P_ATTR
NUM
ht_size(CCR_MOD(ht *) htp)
{
  return (NUM) htp->size;
}

P_ATTR
void **
ht_values(CCR_MOD(ht *) htp)
{
  return htp->values;
}

P_ATTR
NUM *
ht_keys(CCR_MOD(ht *) htp)
{
  return htp->keys;
}