/* htab.c - table hashing routines */

/* This code is ripped out of TinyMUSH 2.2. */
/* Minor tweaking to make in Penn-compatible by Trivian (xeno@mix.hive.no) */


#include "config.h"
#include "copyrite.h"
#ifdef I_STRING
#include <string.h>
#else
#include <strings.h>
#endif
#include "externs.h"
#include "intrface.h"
#include "htab.h"
#include "mymalloc.h"
#include "confmagic.h"

/* ---------------------------------------------------------------------------
 * hash_val: Compute hash value of a string for a hash table.
 */

int
hash_val(key, hashmask)
    const char *key;
    int hashmask;
{
  int hash = 0;
  const char *sp;

  /*
   * If the string pointer is null, return 0.  If not, add up the
   * numeric value of all the characters and return the sum,
   * modulo the size of the hash table.
   */

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

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

int
hash_getmask(size)
    int *size;
{
  int tsize;

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

  /* Get next power-of-two >= size, return power-1 as the mask
   * for ANDing
   */

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

void
hash_init(htab, size)
    HASHTAB *htab;
    int size;
{
  htab->mask = get_hashmask(&size);
  htab->hashsize = size;
  htab->entries = 0;
  htab->buckets = NULL;
}

HASHENT *
hash_find(htab, key)
    HASHTAB *htab;
    const char *key;
{
  int hval;
  HASHENT *hptr;

  if (!htab->buckets)
    return NULL;

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

void *
hash_value(entry)
    HASHENT *entry;
{
  if (entry)
    return entry->data;
  else
    return NULL;
}

char *
hash_key(entry)
    HASHENT *entry;
{
  if (entry)
    return entry->key;
  else
    return NULL;
}

void
hash_resize(htab, size)
    HASHTAB *htab;
    int size;
{
  int i;
  HASHENT **oldarr;
  HASHENT **newarr;
  HASHENT *hent, *nent;
  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_malloc(size * sizeof(struct hashentry *), "hash_buckets");
  htab->buckets = newarr;
  for (i = 0; i < size; i++)
    newarr[i] = NULL;

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

  return;
}

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

  if (!htab->buckets) {
    htab->buckets = (HASHENT **) mush_malloc(htab->hashsize * sizeof(HASHENT *), "hash_buckets");
    for (i = 0; i < htab->hashsize; i++)
      htab->buckets[i] = NULL;
  } else {
    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 + strlen(key) + 1, "hash_entry");
  strcpy(hptr->key, key);
  hptr->data = NULL;
  hptr->next = htab->buckets[hval];
  htab->buckets[hval] = hptr;
  return hptr;
}

int
hash_add(htab, key, hashdata)
    HASHTAB *htab;
    const char *key;
    void *hashdata;
{
  HASHENT *hptr;

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

  if (!hptr)
    return -1;

  hptr->data = hashdata;
  return 0;
}

void
hash_delete(htab, entry)
    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, "hash_entry");
      htab->entries--;
      return;
    }
  }

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

void
hash_flush(htab, size)
    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, "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);
  } else {
    htab->entries = 0;
  }
}

void *
hash_firstentry(htab)
    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;
}

void *
hash_nextentry(htab)
    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;
}