/* hash.c
 * This file is part of Decomp - a decompiler.  This file contains
 * generic hash table manipulation routines.
 *
 * Copyright (C) 2001 Jonathan duSaint <dusaint@earthlink.net>
 *
 * Started around 20 October 2001.
 */

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

#include "xas.h"


#define DEFAULT_HASH_SIZE 8191


/* hash_key
 * Create an index from 0 to SIZE - 1 using the NUL terminated string KEY.
 */
unsigned long
hash_key (char *key, unsigned long size)
{
  int k;
  unsigned long h, g;

  for (h = 0, k = 0; k < strlen (key); k++)
    {
      h = (h << 4) + (unsigned long)key[k];
      if ((g = h & 0xf0000000))
	{
	  h = h ^ (g >> 24);
	  h = h ^ g;
	}
    }

  return h % size;
}


/* hash_goodness
 * Return the "goodness" value of the hash table which is the
 * ratio of the number of filled buckets to the number of items
 * total.  The closer the value is to 1.0, the better.  This,
 * combined with the ratio of the number of filled buckets to
 * the table size can be used to determine how well the hashing
 * algorithm works.
 */
double
hash_goodness (hash_t table)
{
  double goodness;
  unsigned long filled_buckets = 0, k;

  for (k = 0; k < table->size; k++)
    if (table->table[k] != NULL) filled_buckets++;

  goodness = (double)filled_buckets / (double)table->items;

/*   if (debug) */
/*     printf ("hash goodness =  %lf\nfilled:total = %lf\n", goodness, */
/* 	    (double)filled_buckets / (double)table->size); */

  return (goodness);
}


/* hash_new
 * Create a new hash table.  If SIZE is 0, then the size is
 * DEFAULT_HASH_SIZE, otherwise it is SIZE.
 */
hash_t
hash_new (unsigned long size)
{
  hash_t table;

  if (size == 0) size = DEFAULT_HASH_SIZE;

  table = xmalloc (sizeof (struct hash_table));

  table->table = xmalloc (size * sizeof (struct hash_bucket));
  table->size = size;
  table->items = 0;

  return (table);
}

/* hash_add
 * Add DATA to TABLE using KEY.
 */
int
hash_add (hash_t table, char *key, void *data)
{
  unsigned long index;
  struct hash_bucket *tmp;

  index = hash_key (key, table->size);

  /* find empty bucket */
  if (table->table[index] != NULL)
    {
      tmp = table->table[index];
      while (tmp->next != NULL) tmp = tmp->next;

      tmp->next = xmalloc (sizeof (struct hash_bucket));
      tmp = tmp->next;
    }
  else
    {
      table->table[index] = xmalloc (sizeof (struct hash_bucket));
      tmp = table->table[index];
    }


  /* insert new data */
  tmp->next = NULL;
  tmp->key = key;
  tmp->key = xmalloc (strlen (key) + 1);
  strcpy (tmp->key, key);
  tmp->data = data;

  table->items++;

  return (0);
}

/* hash_get
 * Return the data indexed by KEY or NULL if the slot is empty.
 */
void *
hash_get (hash_t table, char *key)
{
  unsigned long index;
  struct hash_bucket *tmp;

  index = hash_key (key, table->size);

  tmp = table->table[index];

  while (tmp != NULL)
    {
      if (!strcmp (key, tmp->key)) return tmp->data;

      tmp = tmp->next;
    }

  /* only get here if the item wasn't found */
  return NULL;
}

/* hash_remove
 * Remove the data indexed by KEY from TABLE.
 */
void *
hash_remove (hash_t table, char *key)
{
  unsigned long index;
  struct hash_bucket *tmp, *del = NULL;
  void *data;

  index = hash_key (key, table->size);

  if (table->table[index] == NULL) return NULL;

  if (!strcmp (table->table[index]->key, key))
    {
      del = table->table[index];
      table->table[index] = table->table[index]->next;
    }
  else
    {
      tmp = table->table[index];

      while (tmp->next != NULL)
	{
	  if (!strcmp (tmp->next->key, key)) break;
	  else tmp = tmp->next;
	}

      if (tmp->next == NULL) return NULL;

      del = tmp->next;
      tmp->next = del->next;
    }

  data = del->data;
  xfree (del->key);
  xfree (del);

  return (data);
}

/* hash_walk
 * Walk through TABLE, returning keys one at a time.  If TABLE is NULL,
 * HASH_END is returned, and initialization is performed.
 */
char *
hash_walk (hash_t table)
{
  char *key;
  static unsigned long index;
  static struct hash_bucket *bucket;

  /* init */
  if (table == NULL)
    {
      index = 0;
      bucket = NULL;
      return HASH_END;
    }

  /* looking for buckets */
  if (bucket == NULL)
    {
      while (table->table[index] == NULL)
	{
	  index++;
	  if (index >= table->size) return HASH_END; /* signal done */
	}

      bucket = table->table[index];
    }

  key = bucket->key;
  bucket = bucket->next;

  return (key);
}

/* hash_delete
 * Delete TABLE.
 */
void
hash_delete (hash_t table)
{
  char *key;

  hash_walk (NULL);

  while ((key = hash_walk (table)) != HASH_END)
    hash_remove (table, key);

  xfree (table->table);
  xfree (table);
}

/* hash_rehash
 * Resize TABLE.  If SIZE is 0, then the new table is twice the size
 * of the old table, otherwise it has SIZE buckets.
 */
hash_t
hash_rehash (hash_t table, unsigned long size)
{
  char *key;
  hash_t new;

  if (size == 0)
    new = hash_new (2 * table->size);
  else
    new = hash_new (size);

  hash_walk (NULL);

  while ((key = hash_walk (table)) != HASH_END)
    {
      /*printf ("  adding %#lx\n", key);*/
      hash_add (new, key, hash_get (table, key));
      hash_remove (table, key);
    }

  hash_delete (table);

  return (new);
}

/* hash_print
 * Print all of the items in the hash table in a human-readable format.
 */
void
hash_print (hash_t table)
{
  unsigned long k;
  struct hash_bucket *tmp;

  for (k = 0; k < table->size; k++)
    {
      if (table->table[k] == NULL) continue;

      printf ("%ld: %s -> %p\n", k, table->table[k]->key,
	      table->table[k]->data);

      tmp = table->table[k]->next;

      while (tmp != NULL)
	{
	  printf ("  --> %s -> %p\n", tmp->key, tmp->data);
	  tmp = tmp->next;
	}
    }
}