path: root/src/ht.c

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

#define HT_REHASH_THRESHOLD 0.5

P_ATTR
static NUM
num_hft(CCR_MOD(void *) key)
{
  if (key == NULL) {
    fleprintf0("Got NULL key!\n");
    return 0;
  }

  return *((NUM *) key);
}

P_ATTR
static BOOL
num_cft(CCR_MOD(void *) keya, CCR_MOD(void *) keyb)
{
  if ((keya == NULL && keyb != NULL) ||
      (keyb == NULL && keya != NULL))
    return 0;

  if (keya == NULL && keyb == NULL) return 1;

  return *((NUM *) keya) == *((NUM *) keyb);
}

/* 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.

   NARGS is the number of arguments to follow.  It should be between 0
   and 2 (inclusive).  If there are more than one argument, the first
   argument is used as the hashing function; if there are two
   arguments, the second argument is used as the comparison
   function. */
ht *
new_ht(UNUM size, int nargs, ...)
{

  if (nargs < 0 || nargs > 2) {
    fleprintf("NARGS should be between zero and two, but got %d\n",
              nargs);
    return NULL;
  }

  hash_func_t hft = num_hft;
  compare_func_t cft = num_cft;

  va_list args;

  if (nargs) {
    va_start(args, nargs);
    if (nargs >= 1) hft = va_arg(args, hash_func_t);
    if (nargs == 2) cft = va_arg(args, compare_func_t);
    va_end(args);
  }

  ht *htp = NULL;
  SAFE_MALLOC(ht, htp, 1, return NULL;);

  htp->capability = (size<<1)+(size>>1);
  htp->size = 0;
  htp->hf = hft;
  htp->cf = cft;

  /* 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_KEY_SELF:
  case DESTROY_KEY_NO_SELF:
  case DESTROY_EVERY_SELF:
  case DESTROY_EVERY_NO_SELF:
  case DESTROY_KEY_VALUE_FIRST_SELF:
  case DESTROY_KEY_VALUE_FIRST_NO_SELF:
    for (NUM i = 0; i < htp->size;)
      free(*(htp->keys+i++));
    break;
  case DESTROY_KEY_FIRST_SELF:
  case DESTROY_KEY_FIRST_NO_SELF:
  case DESTROY_EVERY_FIRST_SELF:
  case DESTROY_EVERY_FIRST_NO_SELF:
  case DESTROY_KEY_FIRST_VALUE_SELF:
  case DESTROY_KEY_FIRST_VALUE_NO_SELF:
    free(*(htp->keys));
    break;
  default:
    break;
  }

  switch (flag) {
  case DESTROY_VALUE_SELF:
  case DESTROY_VALUE_NO_SELF:
  case DESTROY_EVERY_SELF:
  case DESTROY_EVERY_NO_SELF:
  case DESTROY_KEY_FIRST_VALUE_SELF:
  case DESTROY_KEY_FIRST_VALUE_NO_SELF:
    for (NUM i = 0; i < htp->size;)
      free(*(htp->values+i++));
    break;
  case DESTROY_VALUE_FIRST_SELF:
  case DESTROY_VALUE_FIRST_NO_SELF:
  case DESTROY_EVERY_FIRST_SELF:
  case DESTROY_EVERY_FIRST_NO_SELF:
  case DESTROY_KEY_VALUE_FIRST_SELF:
  case DESTROY_KEY_VALUE_FIRST_NO_SELF:
    free(*(htp->values));
    break;
  default:
    break;
  }

  free(htp->values);

  free(htp->keys);

  free(htp->indices);

  switch (flag) {
  case DESTROY_NONE_SELF:
  case DESTROY_KEY_SELF:
  case DESTROY_KEY_FIRST_SELF:
  case DESTROY_VALUE_SELF:
  case DESTROY_VALUE_FIRST_SELF:
  case DESTROY_EVERY_SELF:
  case DESTROY_EVERY_FIRST_SELF:
  case DESTROY_KEY_FIRST_VALUE_SELF:
  case DESTROY_KEY_VALUE_FIRST_SELF:
    free(htp);
    break;
  default:
    break;
  }
}

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

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

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

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

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

  memset(htp->keys, 0, sizeof (void*) * 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;
}

#define PERTURBATION_SHIFT 5

/* On error return non-zero. */
static BOOL
ht_probe(CC_MOD(ht *) htp, CC_MOD(void *) key, NUM *result)
{
  NUM hashed = htp->hf(key);
  NUM ikey = hashed % htp->capability;
  unsigned long perturbation = hashed - ikey;

  for (NUM count = 0;
       count < htp->capability * HT_REHASH_THRESHOLD &&
       *(htp->indices+ikey) >= 0 &&
         /* continue if keys don't match */
         !(htp->cf
           (*(htp->keys+*(htp->indices+ikey)), key));
       count++) {
    ikey = 5 * ikey + 1 + perturbation;
    perturbation >>= PERTURBATION_SHIFT;
    ikey %= htp->capability;
  }

  if (*(htp->indices+ikey) >= 0 &&
      !(htp->cf(*(htp->keys+*(htp->indices+ikey)), key))) {
    /* failed for some reason */
    fleprintf("Fail to probe a location for the key, ikey = %ld, "
              "last index = %ld\n", ikey, *(htp->indices+ikey));
    return 1;
  }

  *result = ikey;

  /* if (*((NUM*) key) == 3) {
   *   fleprintf("ikey = %ld, result = %ld\n", ikey, *result);
   * } */
  return 0;
}

BOOL
ht_insert(ht * const restrict htp, void *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 = 0;

  /* check errors */
  if (ht_probe(htp, key, &ikey)) return 1;

  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 {
    /* error check is performed in ht_probe */
    *(htp->values+*(htp->indices+ikey)) = value;
  }

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

  return 0;
}

BOOL
ht_delete(ht * const restrict htp, void *key, HT_DELETE_FLAG flag)
{
  NUM ikey = 0;

  /* check errors */
  if (ht_probe(htp, key, &ikey)) return 1;

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

    switch (flag) {
    case DELETE_KEY:
    case DELETE_EVERY:
      free(*(htp->keys+*(htp->indices+ikey)));
      break;
    default:
      break;
    }

    switch (flag) {
    case DELETE_VALUE:
    case DELETE_EVERY:
      free(*(htp->values+*(htp->indices+ikey)));
      break;
    default:
      break;
    }

    *(htp->values+*(htp->indices+ikey)) = NULL;
    *(htp->keys+*(htp->indices+ikey)) = NULL;
    *(htp->indices+ikey) = -1;
  }

  return 0;
}

P_ATTR
void *
ht_find(CCR_MOD(ht *) htp, void *key)
{
  NUM ikey = 0;

  /* check errors */
  if (ht_probe(htp, key, &ikey)) return NULL;

  if (*(htp->indices+ikey) < 0) return NULL;

  return *(htp->values+*(htp->indices+ikey));
}

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
void **
ht_keys(CCR_MOD(ht *) htp)
{
  return htp->keys;
}