/**
 * \file htab.c
 *
 * \brief Hashtable routines.
 * This code is largely ripped out of TinyMUSH 2.2.5, with tweaks
 * to make it Penn-compatible by Trivian.
 *
 *
 */

#include "config.h"
#include "copyrite.h"
#include <string.h>
#ifdef HAVE_STDINT_H
#include <stdint.h>
#endif
#include "conf.h"
#include "externs.h"

#include "htab.h"
#include "mymalloc.h"
#include "confmagic.h"

static HASHENT *hash_new(HASHTAB *htab, const char *key);
static int hash_val(register const char *k, int mask);

/* ---------------------------------------------------------------------------
 * hash_val: Compute hash value of a string for a hash table.
 */
/*#define NEW_HASH_FUN /**/
#ifdef NEW_HASH_FUN

/* This hash function adapted from http://burtleburtle.net/bob/hash/evahash.html */

/* The mixing step */
#define mix(a,b,c) \
{ \
  a=a-b;  a=a-c;  a=a^(c>>13); \
  b=b-c;  b=b-a;  b=b^(a<<8);  \
  c=c-a;  c=c-b;  c=c^(b>>13); \
  a=a-b;  a=a-c;  a=a^(c>>12); \
  b=b-c;  b=b-a;  b=b^(a<<16); \
  c=c-a;  c=c-b;  c=c^(b>>5);  \
  a=a-b;  a=a-c;  a=a^(c>>3);  \
  b=b-c;  b=b-a;  b=b^(a<<10); \
  c=c-a;  c=c-b;  c=c^(b>>15); \
}

/* The whole new hash function */
static int
hash_val(const char *k, int mask)
{
  uint32_t a, b, c;             /* the internal state */
  uint32_t len, length;         /* how many key bytes still need mixing */
  static uint32_t initval = 5432;       /* the previous hash, or an arbitrary value */

  /* Set up the internal state */
  length = len = strlen(k);
  a = b = 0x9e3779b9;           /* the golden ratio; an arbitrary value */
  c = initval;                  /* variable initialization of internal state */

   /*---------------------------------------- handle most of the key */
  while (len >= 12) {
    a =
      a + (k[0] + ((uint32_t) k[1] << 8) + ((uint32_t) k[2] << 16) +
           ((uint32_t) k[3] << 24));
    b =
      b + (k[4] + ((uint32_t) k[5] << 8) + ((uint32_t) k[6] << 16) +
           ((uint32_t) k[7] << 24));
    c =
      c + (k[8] + ((uint32_t) k[9] << 8) + ((uint32_t) k[10] << 16) +
           ((uint32_t) k[11] << 24));
    mix(a, b, c);
    k = k + 12;
    len = len - 12;
  }

   /*------------------------------------- handle the last 11 bytes */
  c = c + length;
  switch (len) {                /* all the case statements fall through */
  case 11:
    c = c + ((uint32_t) k[10] << 24);
  case 10:
    c = c + ((uint32_t) k[9] << 16);
  case 9:
    c = c + ((uint32_t) k[8] << 8);
    /* the first byte of c is reserved for the length */
  case 8:
    b = b + ((uint32_t) k[7] << 24);
  case 7:
    b = b + ((uint32_t) k[6] << 16);
  case 6:
    b = b + ((uint32_t) k[5] << 8);
  case 5:
    b = b + k[4];
  case 4:
    a = a + ((uint32_t) k[3] << 24);
  case 3:
    a = a + ((uint32_t) k[2] << 16);
  case 2:
    a = a + ((uint32_t) k[1] << 8);
  case 1:
    a = a + k[0];
    /* case 0: nothing left to add */
  }
  mix(a, b, c);
   /*-------------------------------------------- report the result */
  return c & mask;
}


#else                           /* NEW_HASH_FUN */
/** Compute a hash value for mask-style hashing.
 * Given a null key, return 0. Otherwise, add up the numeric value
 * of all the characters and return the sum modulo the size of the
 * hash table.
 * \param key key to hash.
 * \param hashmask hash table size to use as modulus.
 * \return hash value.
 */
int
hash_val(const char *key, int hashmask)
{
  int hash = 0;
  const char *sp;

  if (!key || !*key)
    return 0;
  for (sp = key; *sp; sp++)
    hash = (hash << 5) + hash + *sp;
  return (hash & hashmask);
}
#endif                          /* NEW_HASH_FUN */

/* ----------------------------------------------------------------------
 * hash_getmask: Get hash mask for mask-style hashing.
 */

/** Get the hash mask for mask-style hashing.
 * Given the data size, return closest power-of-two less than that size.
 * \param size data size.
 * \return hash mask.
 */
int
hash_getmask(int *size)
{
  int tsize;

  if (!size || !*size)
    return 0;

  for (tsize = 1; tsize < *size; tsize = tsize << 1) ;
  *size = tsize;
  return tsize - 1;
}

/** Initialize a hashtable.
 * \param htab pointer to hash table to initialize.
 * \param size size of hashtable.
 * \param data_size size of an individual datum to store in the table.
 */
void
hash_init(HASHTAB *htab, int size, int data_size, void (*free_data) (void *))
{
  htab->mask = get_hashmask(&size);
  htab->hashsize = size;
  htab->entries = 0;
  htab->buckets = mush_calloc(size, sizeof(HASHENT *), "hash_buckets");
  htab->entry_size = data_size;
  htab->free_data = free_data;
}

/** Return a hashtable entry given a key.
 * \param htab pointer to hash table to search.
 * \param key key to look up in the table.
 * \return pointer to hash table entry for given key.
 */
HASHENT *
hash_find(HASHTAB *htab, const char *key)
{
  int hval, cmp;
  HASHENT *hptr;

  if (!htab->buckets)
    return NULL;

  hval = hash_val(key, htab->mask);
  for (hptr = htab->buckets[hval]; hptr != NULL; hptr = hptr->next) {
    cmp = strcmp(key, hptr->key);
    if (cmp == 0) {
      return hptr;
    } else if (cmp < 0)
      break;
  }
  return NULL;
}

/** Return the value stored in a hash entry.
 * \param entry pointer to a hash table entry.
 * \return generic pointer to the stored value.
 */
void *
hash_value(HASHENT *entry)
{
  if (entry)
    return entry->data;
  else
    return NULL;
}

/** Return the key stored in a hash entry.
 * \param entry pointer to a hash table entry.
 * \return pointer to the stored key.
 */
char *
hash_key(HASHENT *entry)
{
  if (entry)
    return entry->key;
  else
    return NULL;
}

/** Resize a hash table.
 * \param htab pointer to hashtable.
 * \param size new size.
 */
void
hash_resize(HASHTAB *htab, int size)
{
  int i;
  HASHENT **oldarr;
  HASHENT **newarr;
  HASHENT *hent, *nent, *curr, *old;
  int hval;
  int osize;
  int mask;

  /* We don't want hashes outside these limits */
  if ((size < (1 << 4)) || (size > (1 << 20)))
    return;

  /* Save the old data we need */
  osize = htab->hashsize;
  oldarr = htab->buckets;

  mask = htab->mask = get_hashmask(&size);

  if (size == htab->hashsize)
    return;

  htab->hashsize = size;
  newarr =
    (HASHENT **) mush_calloc(size, sizeof(struct hashentry *), "hash_buckets");
  htab->buckets = newarr;

  for (i = 0; i < osize; i++) {
    hent = oldarr[i];
    while (hent) {
      nent = hent->next;
      hval = hash_val(hent->key, mask);
      for (curr = newarr[hval], old = NULL; curr; old = curr, curr = curr->next) {
        if (strcmp(curr->key, hent->key) > 0)
          break;
      }
      if (old) {
        old->next = hent;
        hent->next = curr;
      } else {
        hent->next = newarr[hval];
        newarr[hval] = hent;
      }
      hent = nent;
    }
  }
  mush_free(oldarr, "hash_buckets");

  return;
}

static HASHENT *
hash_new(HASHTAB *htab, const char *key)
{
  int hval;
  HASHENT *hptr, *curr, *old;

  hptr = hash_find(htab, key);
  if (hptr)
    return hptr;

  if (htab->entries > (htab->hashsize * HTAB_UPSCALE))
    hash_resize(htab, htab->hashsize << 1);

  hval = hash_val(key, htab->mask);
  htab->entries++;
  hptr = (HASHENT *) mush_malloc(HASHENT_SIZE, "hash_entry");
  hptr->key = mush_strdup(key, "hash_key");
  hptr->data = NULL;

  if (!htab->buckets[hval] || strcmp(key, htab->buckets[hval]->key) < 0) {
    hptr->next = htab->buckets[hval];
    htab->buckets[hval] = hptr;
    return hptr;
  }

  /* Insert in sorted order. There's always at least one item in 
     the chain already at this point. */
  old = htab->buckets[hval];
  for (curr = old->next; curr; old = curr, curr = curr->next) {
    /* Comparison will never be 0 because hash_add checks to see
       if the entry is already present. */
    if (strcmp(key, curr->key) < 0) {   /* Insert before curr */
      old->next = hptr;
      hptr->next = curr;
      return hptr;
    }
  }

  /* If we get here, we reached the end of the chain */
  old->next = hptr;
  hptr->next = NULL;

  return hptr;
}

/** Add an entry to a hash table.
 * \param htab pointer to hash table.
 * \param key key string to store data under.
 * \param hashdata void pointer to data to be stored.
 * \param extra_size unused.
 * \retval -1 failure.
 * \retval 0 success.
 */
int
hash_add(HASHTAB *htab, const char *key, void *hashdata,
         int extra_size __attribute__ ((__unused__)))
{
  HASHENT *hptr;

  if (hash_find(htab, key) != NULL) {
    return -1;
  }

  hptr = hash_new(htab, key);

  if (!hptr)
    return -1;

  hptr->data = hashdata;
  return 0;
}

/** Delete an entry in a hash table.
 * \param htab pointer to hash table.
 * \param entry pointer to hash entry to delete (and free).
 */
void
hash_delete(HASHTAB *htab, HASHENT *entry)
{
  int hval;
  HASHENT *hptr, *last;

  if (!entry)
    return;

  hval = hash_val(entry->key, htab->mask);
  last = NULL;
  for (hptr = htab->buckets[hval]; hptr; last = hptr, hptr = hptr->next) {
    if (entry == hptr) {
      if (last == NULL)
        htab->buckets[hval] = hptr->next;
      else
        last->next = hptr->next;
      mush_free(hptr->key, "hash_key");
      if (htab->free_data)
        htab->free_data(hptr->data);
      mush_free(hptr, "hash_entry");
      htab->entries--;
      return;
    }
  }

  if (htab->entries < (htab->hashsize * HTAB_DOWNSCALE))
    hash_resize(htab, htab->hashsize >> 1);
}

/** Flush a hash table, freeing all entries.
 * \param htab pointer to a hash table.
 * \param size size of hash table.
 */
void
hash_flush(HASHTAB *htab, int size)
{
  HASHENT *hent, *thent;
  int i;

  if (htab->buckets) {
    for (i = 0; i < htab->hashsize; i++) {
      hent = htab->buckets[i];
      while (hent != NULL) {
        thent = hent;
        hent = hent->next;
        mush_free(thent->key, "hash_key");
        if (htab->free_data)
          htab->free_data(thent->data);
        mush_free(thent, "hash_entry");
      }
      htab->buckets[i] = NULL;
    }
  }
  if (size == 0) {
    mush_free(htab->buckets, "hash_buckets");
    htab->buckets = NULL;
  } else if (size != htab->hashsize) {
    if (htab->buckets)
      mush_free(htab->buckets, "hash_buckets");
    hashinit(htab, size, htab->entry_size);
  } else {
    htab->entries = 0;
  }
}

/** Return the first entry of a hash table.
 * This function is used with hash_nextentry() to iterate through a 
 * hash table.
 * \param htab pointer to hash table.
 * \return first hash table entry.
 */
void *
hash_firstentry(HASHTAB *htab)
{
  int hval;

  for (hval = 0; hval < htab->hashsize; hval++)
    if (htab->buckets[hval]) {
      htab->last_hval = hval;
      htab->last_entry = htab->buckets[hval];
      return htab->buckets[hval]->data;
    }
  return NULL;
}

/** Return the first key of a hash table.
 * This function is used with hash_nextentry_key() to iterate through a 
 * hash table.
 * \param htab pointer to hash table.
 * \return first hash table key.
 */
char *
hash_firstentry_key(HASHTAB *htab)
{
  int hval;

  for (hval = 0; hval < htab->hashsize; hval++)
    if (htab->buckets[hval]) {
      htab->last_hval = hval;
      htab->last_entry = htab->buckets[hval];
      return htab->buckets[hval]->key;
    }
  return NULL;
}

/** Return the next entry of a hash table.
 * This function is used with hash_firstentry() to iterate through a 
 * hash table. hash_firstentry() must be called before calling
 * this function.
 * \param htab pointer to hash table.
 * \return next hash table entry.
 */
void *
hash_nextentry(HASHTAB *htab)
{
  int hval;
  HASHENT *hptr;

  hval = htab->last_hval;
  hptr = htab->last_entry;
  if (hptr->next) {
    htab->last_entry = hptr->next;
    return hptr->next->data;
  }
  hval++;
  while (hval < htab->hashsize) {
    if (htab->buckets[hval]) {
      htab->last_hval = hval;
      htab->last_entry = htab->buckets[hval];
      return htab->buckets[hval]->data;
    }
    hval++;
  }
  return NULL;
}

/** Return the next key of a hash table.
 * This function is used with hash_firstentry{,_key}() to iterate through a 
 * hash table. hash_firstentry{,_key}() must be called before calling
 * this function.
 * \param htab pointer to hash table.
 * \return next hash table key.
 */
char *
hash_nextentry_key(HASHTAB *htab)
{
  int hval;
  HASHENT *hptr;

  hval = htab->last_hval;
  hptr = htab->last_entry;
  if (hptr->next) {
    htab->last_entry = hptr->next;
    return hptr->next->key;
  }
  hval++;
  while (hval < htab->hashsize) {
    if (htab->buckets[hval]) {
      htab->last_hval = hval;
      htab->last_entry = htab->buckets[hval];
      return htab->buckets[hval]->key;
    }
    hval++;
  }
  return NULL;
}

/** Display a header for a stats listing.
 * \param player player to notify with header.
 */
void
hash_stats_header(dbref player)
{
  notify_format(player,
                "Table      Buckets Entries LChain  ECh  1Ch  2Ch  3Ch 4+Ch  AvgCh ~Memory");
}

/** Display stats on a hashtable.
 * \param player player to notify with stats.
 * \param htab pointer to the hash table.
 * \param hname name of the hash table.
 */
void
hash_stats(dbref player, HASHTAB *htab, const char *hname)
{
  int longest = 0, n;
  int lengths[5];
  double chainlens = 0.0;
  double totchains = 0.0;
  unsigned int bytes = 0;

  if (!htab || !hname)
    return;

  for (n = 0; n < 5; n++)
    lengths[n] = 0;
  bytes += sizeof(HASHTAB);
  bytes += htab->entry_size * htab->entries;
  if (htab->buckets) {
    bytes += HASHENT_SIZE * htab->hashsize;
    for (n = 0; n < htab->hashsize; n++) {
      int chain = 0;
      HASHENT *b;
      if (htab->buckets[n]) {
        for (b = htab->buckets[n]; b; b = b->next) {
          chain++;
          bytes += strlen(b->key) + 1;
        }
        if (chain > longest)
          longest = chain;
      }
      lengths[(chain > 4) ? 4 : chain]++;
      chainlens += chain;
    }
  }
  for (n = 1; n < 5; n++)
    totchains += lengths[n];

  notify_format(player,
                "%-10s %7d %7d %6d %4d %4d %4d %4d %4d %6.3f %7u", hname,
                htab->hashsize, htab->entries, longest, lengths[0], lengths[1],
                lengths[2], lengths[3], lengths[4],
                totchains > 0 ? chainlens / totchains : 0.0, bytes);
}