path: root/src/htgen.h

/* config */

#include "xxhash.h"
#include <stdlib.h>
#include <string.h>

#if 1
#define HT_PREFIX  shash_
#define HT_VALTYPE char *
#define HT_VALTYPE_CREF const char *

/* should be able to be cast to uintmax_t without losing information */
#define HT_HASHTYPE XXH64_hash_t
#define HT_KEY_HASH(_val, _sz) XXH3_64bits(_val, _sz)

/* default load factor if variable: #define HT_LOADFACTOR_DEF (0.75f) */
/* or define a static load factor: #define HT_LOADFACTOR (0.75f) */

/* should take HT_VALTYPE_CREF and return HT_VALTYPE */
#define HT_VAL_COPY(_val, _sz) strdup(_val)

/* #define HT_VAL_STATIC_LEN sizeof(int) */
#define HT_VAL_GUESS_LEN(_val) strlen(_val)

/* this function shouldn't do anything if it is called with a value of HT_VAL_SENTINEL */
#define HT_VAL_FREE(_val) free(_val)

#define HT_VAL_SENTINEL NULL

#define HT_KEYTYPE char *
#define HT_KEYTYPE_CREF const char *

/* will receive two HT_KEYTYPEs */
/* bad equality function LOL (shouldn't use strcmp) */
#define HT_KEY_EQ(_val1, _len1, _val2, _len2) (((_len1) == (_len2)) && !strcmp(_val1, _val2))

#define HT_KEY_COPY(_key, _sz) (strdup(_key))
#define HT_KEY_FREE(_key) free(_key)

/* #define HT_KEY_STATIC_LEN sizeof(int) */
#define HT_KEY_GUESS_LEN(_val) strlen(_val)

#define HT_KEY_FMT "%s"
#define HT_VAL_FMT "%s"

#else

XXH64_hash_t ihash_hash_int(int i)
{
  return XXH3_64bits(&i, sizeof(int));
}

#define HT_PREFIX ihash_
#define HT_VALTYPE int
#define HT_VALTYPE_CREF int

#define HT_HASHTYPE XXH64_hash_t
#define HT_KEY_HASH(_val, _sz) ihash_hash_int(_val)

#define HT_VAL_COPY(_val, _sz) _val

/* #define HT_VAL_STATIC_LEN sizeof(int) */
#define HT_VAL_STATIC_LEN sizeof(int)

/* will receive two HT_KEYTYPEs */
#define HT_KEY_EQ(_val1, _sz1, _val2, _sz2) ((_val1) == (_val2))

#define HT_KEYTYPE int
#define HT_KEYTYPE_CREF int

#define HT_KEY_COPY(_key, _sz) _key
#define HT_KEY_FREE(_key)
#define HT_KEY_STATIC_LEN sizeof(int)

#define HT_KEY_FMT "%d"
#define HT_VAL_FMT "%d"

#endif

#define HT_MALLOC(_sz) malloc(_sz)
#define HT_CALLOC(_num, _sz) calloc(_num, _sz)
#define HT_REALLOC(_ptr, _newsz) realloc(_ptr, _newsz)
#define HT_FREE(_p) free(_p)

/* declarations */

#include <stddef.h>
#include <stdbool.h>
#include <stdio.h>

#define HT__CONCAT(_t1, _t2)  HT__CONCAT2(_t1, _t2)
#define HT__CONCAT2(_t1, _t2) _t1 ## _t2

#define HT__STR(_x) HT__STR2(_x)
#define HT__STR2(_x) #_x

#define HT__NS(_n) HT__CONCAT(HT_PREFIX, _n)
#define HT__TYPE HT__NS(t)
#define HT__TAG HT__NS(_ht_tag)

typedef struct HT__TAG HT__TYPE;

HT__TYPE *HT__NS(new)(void);

#ifdef HT_LOADFACTOR
#define HT__CREATE_SIG size_t cap
#else
#define HT__CREATE_SIG size_t cap, float load_factor
#endif

HT__TYPE *HT__NS(create)(HT__CREATE_SIG);

void HT__NS(free)(HT__TYPE *ht);

void HT__NS(clear)(HT__TYPE *ht);

HT_VALTYPE HT__NS(get)(HT__TYPE *ht, HT_KEYTYPE_CREF key, bool *found);
HT_VALTYPE HT__NS(getn)(HT__TYPE *ht, HT_KEYTYPE_CREF key, size_t keylen, bool *found);

int HT__NS(put)(HT__TYPE *ht, HT_KEYTYPE_CREF key, HT_VALTYPE_CREF val);
int HT__NS(putn)(HT__TYPE *ht, HT_KEYTYPE_CREF key, size_t keylen, HT_VALTYPE_CREF val, size_t vallen);

int HT__NS(remove)(HT__TYPE *ht, HT_KEYTYPE_CREF key);
int HT__NS(removen)(HT__TYPE *ht, HT_KEYTYPE_CREF key, size_t keylen);

HT_VALTYPE HT__NS(pop)(HT__TYPE *ht, HT_KEYTYPE_CREF key, bool *found);
HT_VALTYPE HT__NS(popn)(HT__TYPE *ht, HT_KEYTYPE_CREF key, size_t keylen, bool *found);

/* implementations */

#if defined(HT_IMPLEMENTATIONS) || 1

#define HT__NODE HT__NS(_node)

#ifdef HT_LOADFACTOR
#define HT__LOADFACTOR_FIXED HT_LOADFACTOR
#define HT__LOADFACTOR(_unused) HT_LOADFACTOR
#else
#define HT__LOADFACTOR(_ht) ((_ht)->load_factor)
#endif

#ifdef HT_KEY_STATIC_LEN
#define HT__NODE_KEYLEN(_node) HT_KEY_STATIC_LEN
#define HT__NODE_KEYLEN_SET(_node, _unused)
#define HT__GUESS_KEYLEN(_node) HT_KEY_STATIC_LEN
#else
#define HT__NODE_KEYLEN(_node) ((_node)->keylen)
#define HT__NODE_KEYLEN_SET(_node, _len) (((_node)->keylen) = (_len))
#define HT__GUESS_KEYLEN(_key) HT_KEY_GUESS_LEN(_key)
#endif

#ifdef HT_VAL_STATIC_LEN
#define HT__NODE_VALLEN(_node) HT_VAL_STATIC_LEN
#define HT__NODE_VALLEN_SET(_node, _unused)
#define HT__GUESS_VALLEN(_val) HT_VAL_STATIC_LEN
#else
#define HT__NODE_VALLEN(_node) ((_node)->vallen)
#define HT__NODE_VALLEN_SET(_node, _len) (((_node)->vallen) = (_len))
#define HT__GUESS_VALLEN(_val) HT_VAL_GUESS_LEN(_val)
#endif

#ifndef HT_VAL_FREE
#define HT_VAL_FREE(_val)
#endif

#ifndef HT_LOADFACTOR_DEF
#define HT_LOADFACTOR_DEF (0.75f)
#endif

#ifndef HT_VAL_SENTINEL
#define HT_VAL_SENTINEL ((HT_VALTYPE)0)
#endif

#define HT__HASHTYPE HT__NS(_hash_t)
typedef HT_HASHTYPE HT__HASHTYPE;
#undef HT_HASHTYPE /* use the typedef (it acts better) */

typedef struct {
#ifndef HT_VAL_STATIC_LEN
  size_t vallen;
#endif

  HT_VALTYPE val;

#ifndef HT_KEY_STATIC_LEN
  size_t keylen;
#endif

  HT_KEYTYPE key;
  HT__HASHTYPE hash;

  bool full:1;
  bool deleted:1;
} HT__NODE;


struct HT__TAG {
  size_t capacity; /* hash table capacity (number of elements in table) */
  size_t rsize;    /* real size (number of elements full) */
  size_t asize;    /* active size (number of elements full and not deleted) */

#ifndef HT__LOADFACTOR_FIXED
  float load_factor;
#endif

  HT__NODE *table;
};

size_t HT__NS(_next_po2)(size_t in)
{
  size_t n = 1;
  while (n && n < in) n <<= 1;
  return n;
}

HT__TYPE *HT__NS(new)(void)
{
#ifdef HT__LOADFACTOR_FIXED
  return HT__NS(create)(0);
#else
  return HT__NS(create)(0, HT_LOADFACTOR_DEF);
#endif
}

HT__TYPE *HT__NS(create)(HT__CREATE_SIG)
{
  HT__TYPE *ht = HT_CALLOC(1, sizeof(HT__TYPE));
  if (!ht) return NULL;

#ifndef HT_LOADFACTOR
  if (load_factor < 0.0f || load_factor > 1.0f) {
    goto cleanup;
  } else if (load_factor == 0.0f) {
    load_factor = HT_LOADFACTOR_DEF;
  }

  ht->load_factor = load_factor;
#endif

  if (cap == 0) {
    cap = 16;
  } else {
    cap = HT__NS(_next_po2)(cap);
  }

  ht->capacity = cap;
  ht->table = HT_CALLOC(cap, sizeof(HT__NODE));
  if (!ht->table) {
    goto cleanup;
  }

  return ht;

cleanup:
  HT_FREE(ht->table);
  HT_FREE(ht);
  return NULL;
}

void HT__NS(free)(HT__TYPE *ht)
{
  if (!ht) return;

  HT__NS(clear)(ht);

  HT_FREE(ht->table);
  HT_FREE(ht);
}

void HT__NS(clear)(HT__TYPE *ht)
{
  for (size_t idx = 0; idx < ht->capacity; ++idx) {
    if (!ht->table[idx].full || ht->table[idx].deleted) continue;

    HT_KEY_FREE(ht->table[idx].key);
    HT_VAL_FREE(ht->table[idx].val);
    ht->table[idx].full = false;
  }

  ht->asize = ht->rsize = 0;
}

#define HT__KEY_MATCH_EXACT(_node, _hash, _key, _keylen) (((_node)->hash == (_hash)) && (HT_KEY_EQ((_node)->key, HT__NODE_KEYLEN(_node), _key, _keylen)))

HT__NODE *HT__NS(_search)(HT__NODE *table, size_t tablecap, const HT__HASHTYPE hash, HT_KEYTYPE_CREF key, size_t keylen, bool vacant)
{
  size_t tryidx = (size_t)((uintmax_t)hash % tablecap);
  size_t start = tryidx;

  HT__NODE *node;

  fprintf(stderr, "debug: trying %zu for " HT_KEY_FMT "\n", tryidx, key);

  do {
    node = table + tryidx;

    if (node->full && !node->deleted && HT__KEY_MATCH_EXACT(node, hash, key, keylen)) {
      fprintf(stderr, "found node %zu: matches\n", tryidx);
      return node;
    }

    if (vacant) {
      if (!node->full || node->deleted) {
        fprintf(stderr, "found node %zu: empty\n", tryidx);
        return node;
      }
    }

    tryidx = (tryidx + 1) % tablecap;
  } while (tryidx != start);

  return NULL;
}

HT__NODE *HT__NS(_search_ahead)(HT__NODE *table, HT__NODE *start, size_t tablecap, const HT__HASHTYPE hash, HT_KEYTYPE_CREF key, size_t keylen)
{
  size_t startidx = (size_t)((uintmax_t)hash % tablecap);
  size_t tryidx = ((start - table) + 1) % tablecap;

  HT__NODE *node;

  do {
    node = table + tryidx;

    if (!node->full) return NULL;

    if (!node->deleted && HT__KEY_MATCH_EXACT(node, hash, key, keylen)) {
      return node;
    }

    tryidx = (tryidx + 1) % tablecap;
  } while (tryidx != startidx);

  return NULL;
}

int HT__NS(_node_erase)(HT__TYPE *ht, HT__NODE *node)
{
  if (!node->full || node->deleted) return 0;
  node->deleted = true;
  --ht->asize;

  HT_KEY_FREE(node->key);
  HT_VAL_FREE(node->val);

  return 1;
}

void HT__NS(_search_ahead_erase)(HT__TYPE *ht, HT__NODE *start)
{
  HT__NODE *found = HT__NS(_search_ahead)(ht->table, start, ht->capacity, start->hash, start->key, start->keylen);
  if (!found) {
    return;
  }

  HT__NS(_node_erase)(ht, found);
}

int HT__NS(_node_set)(HT__TYPE *ht, HT__NODE *node, const HT__HASHTYPE hash, HT_KEYTYPE_CREF key, size_t keylen, HT_VALTYPE_CREF val, size_t vallen)
{
  if (node->full) {
    if (!node->deleted) {
      /* same key already present! replace */
      HT_VAL_FREE(node->val);

      node->val = HT_VAL_COPY(val, vallen);
      if (!node->val) return -1;

      HT__NODE_VALLEN_SET(node, vallen);

      /* size left unchanged (key replaced) */
      return 0;
    }

    node->key = HT_KEY_COPY(key, keylen);
    HT__NODE_KEYLEN_SET(node, keylen);
    node->hash = hash;

    node->val = HT_VAL_COPY(val, vallen);
    HT__NODE_VALLEN_SET(node, vallen);

    if (!node->val || !node->key) {
      HT_KEY_FREE(node->key);
      HT_VAL_FREE(node->val);
      return -1;
    }

    node->deleted = false; /* node is now filled */
    ++ht->asize;

    HT__NS(_search_ahead_erase)(ht, node);
    return 0;
  }

  /* fully new key */

  node->key = HT_KEY_COPY(key, keylen);
  HT__NODE_KEYLEN_SET(node, keylen);
  node->hash = hash;

  node->val = HT_VAL_COPY(val, vallen);
  HT__NODE_VALLEN_SET(node, vallen);

  if (!node->val || !node->key) {
    HT_KEY_FREE(node->key);
    HT_VAL_FREE(node->val);
    return -1;
  }

  node->deleted = false;
  node->full = true;

  ++ht->rsize;
  ++ht->asize;

  if (!node->val) return -1;

  return 0;
}

int HT__NS(_rehash)(HT__TYPE *ht, size_t newcap)
{
  HT__NODE *newtab = HT_CALLOC(newcap, sizeof(HT__NODE));
  if (!newtab) return -1;

  for (size_t idx = 0; idx < ht->capacity; ++idx) {
    if (!ht->table[idx].full || ht->table[idx].deleted) continue;

    HT__NODE *node = HT__NS(_search)(newtab, newcap, ht->table[idx].hash, ht->table[idx].key, HT__NODE_KEYLEN(ht->table + idx), true);
    if (!node) goto cleanup;

    memcpy(node, ht->table + idx, sizeof(HT__NODE));
  }

  HT_FREE(ht->table); /* point of no return */

  ht->table = newtab;
  ht->capacity = newcap;
  ht->rsize = ht->asize;

  return 0;

cleanup:
  HT_FREE(newtab);
  return -1;
}

int HT__NS(put)(HT__TYPE *ht, HT_KEYTYPE_CREF key, HT_VALTYPE_CREF val)
{
  return HT__NS(putn)(ht, key, 0, val, 0);
}

int HT__NS(putn)(HT__TYPE *ht, HT_KEYTYPE_CREF key, size_t keylen, HT_VALTYPE_CREF val, size_t vallen)
{
  if (ht->capacity * HT__LOADFACTOR(ht) < (ht->asize + 1)) {
    if (HT__NS(_rehash)(ht, ht->capacity << 1) < 0) return -1;
  }

  if (!keylen) keylen = HT__GUESS_KEYLEN(key);
  if (!vallen) vallen = HT__GUESS_VALLEN(val);

  const HT__HASHTYPE hash = HT_KEY_HASH(key, keylen);

  HT__NODE *node = HT__NS(_search)(ht->table, ht->capacity, hash, key, keylen, true);

  if (!node) { /* no vacant slots found */
    return -1; /* table is full or something! */
  }

  return HT__NS(_node_set)(ht, node, hash, key, keylen, val, vallen);
}

HT_VALTYPE HT__NS(get)(HT__TYPE *ht, HT_KEYTYPE_CREF key, bool *found)
{
  return HT__NS(getn)(ht, key, 0, found);
}

HT_VALTYPE HT__NS(getn)(HT__TYPE *ht, HT_KEYTYPE_CREF key, size_t keylen, bool *found)
{
  if (!keylen) keylen = HT__GUESS_KEYLEN(key);

  const HT__HASHTYPE hash = HT_KEY_HASH(key, keylen);
  HT__NODE *node = HT__NS(_search)(ht->table, ht->capacity, hash, key, keylen, false);

  if (!node) {
    if (found) *found = false;
    return HT_VAL_SENTINEL;
  }

  *found = true;
  return node->val;
}

int HT__NS(remove)(HT__TYPE *ht, HT_KEYTYPE_CREF key)
{
  return HT__NS(removen)(ht, key, 0);
}

int HT__NS(removen)(HT__TYPE *ht, HT_KEYTYPE_CREF key, size_t keylen)
{
  if (!keylen) keylen = HT__GUESS_KEYLEN(key);
  
  const HT__HASHTYPE hash = HT_KEY_HASH(key, keylen);
  HT__NODE *node = HT__NS(_search)(ht->table, ht->capacity, hash, key, keylen, false);
  
  if (!node) return 0;

  return HT__NS(_node_erase)(ht, node);
}

HT_VALTYPE HT__NS(pop)(HT__TYPE *ht, HT_KEYTYPE_CREF key, bool *found)
{
  return HT__NS(popn)(ht, key, 0, found);
}

HT_VALTYPE HT__NS(popn)(HT__TYPE *ht, HT_KEYTYPE_CREF key, size_t keylen, bool *found)
{
  if (!keylen) keylen = HT__GUESS_KEYLEN(key);

  const HT__HASHTYPE hash = HT_KEY_HASH(key, keylen);
  HT__NODE *node = HT__NS(_search)(ht->table, ht->capacity, hash, key, keylen, false);

  if (!node) {
    if (found) *found = false;
    return NULL;
  }

  if (found) *found = true;

  HT_VALTYPE val = node->val;
  node->val = HT_VAL_SENTINEL;
  HT__NS(_node_erase)(ht, node);
  return val;
}

void HT__NS(_debug_table)(HT__TYPE *ht)
{
  fprintf(stderr, HT__STR(HT__TYPE) " debug: cap: %zu, asize: %zu, rsize: %zu, lf: %f\n",
    ht->capacity, ht->asize, ht->rsize, HT__LOADFACTOR(ht));
  
  for (size_t n = 0; n < ht->capacity; ++n) {
    fprintf(stderr, "%zu: ", n);
    if (ht->table[n].full) {
      if (ht->table[n].deleted) {
        fprintf(stderr, "(deleted)\n");
      } else {
        fprintf(stderr, "(full " HT_KEY_FMT ":" HT_VAL_FMT ")\n", ht->table[n].key, ht->table[n].val);
      }
    } else {
      fprintf(stderr, "(empty)\n");
    }
  }
}

#endif

/* undefine all of the configuration parameters */

#undef HT_PREFIX
#undef HT_VALTYPE
#undef HT_VALTYPE_CREF

#undef HT_HASHTYPE
#undef HT_KEY_HASH

#undef HT_VAL_COPY
#undef HT_VAL_STATIC_LEN
#undef HT_VAL_GUESS_LEN

#undef HT_VAL_FREE
#undef HT_VAL_SENTINEL

#undef HT_KEYTYPE
#undef HT_KEYTYPE_CREF
#undef HT_KEY_EQ
#undef HT_KEY_COPY
#undef HT_KEY_FREE

#undef HT_KEY_STATIC_LEN
#undef HT_KEY_GUESS_LEN

#undef HT_KEY_FMT
#undef HT_VAL_FMT