/**
 * hash.c
 *   Definition of a hash table type.
 */

// +-------------+----------------------------------------------------
// | Customizing |
// +-------------+

/*

1. To set the multipliers the hash function uses when hashing a string,
   set constants MULTIPLIERS (an array of integers) and NUM_MULTIPLIERS
   (the size of that array).

2. To set the default size of the hash table, set constant 
   INITIAL_TABLE_CAPACITY.

3. To set the policy for enlarging tables, change ENLARGE(CAPACITY).

*/


// +-------+----------------------------------------------------------
// | Notes |
// +-------+

/*

Structure of this file:

  * Instructions on customizing (see above)
  * Notes (these)
  * Headers (boring)
  * Constants/Macros (for customizing)
    * MULTIPLIERS
    * NUM_MULTIPLIERS
    * INITIAL_TABLE_CAPACITY
    * ENLARGE(CAPACITY)
  * Types
    * struct hash_element - one element in the hash table
    * struct hash_table - the hash table
  * Globals
    * hash_error - the latest error encountered (for testing)
  * Helpers
    * hashfun - The hash function
    * hashpos - Find the position in a table for a key
    * hash_enlarge - enlarge a hash table
  * Testing and Experiments
    * test_put - test the put function.  Used by hash_utest.
    * test_get - test the get function.  Used by hash_utest.
    * hash_utest - the unit tests
    * hashfun_examples - examples of the hash function.  
  * Exported Functions
    * hash_new
    * hash_put
    * hash_get

This hash table uses a linear-probe strategy.  Right now, the probe is a
bit primitive: We repeatedly add a constant number and hope that it does
not wrap.  Ideally, we'd make sure that the constant is relatively prime
to the table capacity so that we ensure that we find an empty space.

There's a slight issue in the design of put with a repeated key.  If
we know that there's enough space for the new value in the current value,
we just copy it over.  However, the check for enough space is strlen,
which is not appropriate after the first copy.  (It's safe, but it means
that there are times in which we could copy values that we do not.)

 */


// +---------+--------------------------------------------------------
// | Headers |
// +---------+

#include <limits.h>     // For INT_MIN
#include <stdio.h>      // For printf in unit tests and other tests.
#include <string.h>     // For strcmp
#include <strings.h>	// For bzero
#include <stdlib.h>     // For malloc, free

#include "hash.h"


// +-----------+------------------------------------------------------
// | Constants |
// +-----------+

#ifndef MULTIPLIERS
// The multipliers we use in computing the hash value.
#define MULTIPLIERS { 71, 73, 111, 257, 311 }
// The number of mulitpliers
#define NUM_MULTIPLIERS 5
#endif

#ifndef INITIAL_TABLE_CAPACITY
#define INITIAL_TABLE_CAPACITY 19
#endif

#ifndef ENLARGE
#define ENLARGE(CAPACITY) (1 + 2 * (CAPACITY));
#endif


// +-------+----------------------------------------------------------
// | Types |
// +-------+

/**
 * hash_element - An element in a hash table.
 */
struct hash_element
  {
    char *key;
    char *val;
  };
typedef struct hash_element *hash_element;

/**
 * hash_table - Our main type.
 */
struct hash_table 
  {
    struct hash_element **elements;
    int size;     // Number of elements in table
    int capacity; // Number of elements table can hold.
  }; // struct hash_table


// +---------+--------------------------------------------------------
// | Globals |
// +---------+

/**
 * The latest error we've encountered.
 */
char *hash_error = "";


// +---------+--------------------------------------------------------
// | Helpers |
// +---------+

/**
 * hashfun (char *str)
 *   Compute a hash value for str.
 */
static int 
hashfun (const char *str)
{
  static int multipliers[] = MULTIPLIERS;
  int result = 0;
  int i;
  for (i = 0; i < NUM_MULTIPLIERS; i++)
    {
      // Stop if the string is over
      if (! str[i]) break;
      // Add a value for the current multiplier
      result += str[i] * multipliers[i];
    } // for

  // Make sure that the return value is non-negative
  if (result == INT_MIN)
    return 0;
  if (result < 0)
    return -result;
  return result;
} // hashfun

/**
 * hashpos (hash table, char *key)
 *   Find the first cell that should hold key.  If there is no cell with
 *   key, returns a cell we can use to add key.
 */
static int 
hashpos (hash table, const char *key)
{
  int pos = (hashfun (key)) % table->capacity;
  while (1)
    {
      if (table->elements[pos] == NULL)
        return pos;
      if (strcmp (key, table->elements[pos]->key) == 0)
        return pos;
      pos = (pos + 1) % table->capacity;
    } // while
} // hashpos

/**
 * hash_enlarge (table)
 *   Enlarge a hash table.  Return success/failure.
 */
static int
hash_enlarge (hash table)
{
  struct hash_element **old_elements = table->elements;
  struct hash_element *elem;
  int old_capacity = table->capacity;
  int i;

  table->capacity = ENLARGE(table->capacity);

  // Allocate space for the new table of elements.
  table->elements = malloc (sizeof (struct element *) * table->capacity);
  if (table->elements == NULL)
    {
      table->elements = old_elements;
      table->capacity = old_capacity;
      hash_error = "could not allocate new table";
      return 0;
    } 
  bzero (table->elements, sizeof (struct element *) * table->capacity);

  // Rehash everything.  
  table->size = 0;
  for (i = 0; i < old_capacity; i++)
    {
      if ((elem = old_elements[i]) != NULL)
        {
          table->elements[hashpos(table, elem->key)] = elem;
          old_elements[i] = NULL;
        } // If the cell is non empty
    } // for
 
   // And we're done.
  return 1;
} // hash_enlarge


// +----------------------+-------------------------------------------
// | Unit and Other Tests |
// +----------------------+

/**
 * test_put
 *   A tst of the put function.
 */
static void
test_put (hash table, 
          const char *key, const char *value, 
          int *tests, int *errors)
{
  printf ("put (%s,%s)\n", key, value);
  ++(*tests);
  if (! hash_put (table, key, value))
    {
      printf ("Could not add \"%s\" -> \"%s\" because %s\n", key, value, 
              hash_error);
      ++(*errors);
    }
} // test_put

/**
 * test_get
 *   A test of the get function.
 */
static void
test_get (hash table, 
          const char *key, 
          const char *expected, int *tests, int *errors)
{
  printf ("get (%s)\n", key);
  ++(*tests);
  char *result = hash_get (table, key);

  if (expected == NULL) 
    {
      if (result == NULL)
        return;
      printf ("For get(\"%s\"), expected NULL, got \"%s\"\n", key, result);
      ++(*errors);
    }

  else if (result == NULL)
    {
      printf ("For get(\"%s\"), expected \"%s\" got NULL\n", key, expected);
      ++(*errors);
    }

  else if (strcmp (expected, result) != 0)
    {
      printf ("For get(\"%s\"), expected \"%s\", got \"%s\"\n", 
              key, expected, result);
      ++(*errors);
    }
} // test_get

/**
 * hash_utest
 *   Unit tests for our hash function.    Returns the number of
 *   errors operations.
 */
int
hash_utest ()
{
  hash tab0 = hash_new ();      // Table 1
  hash tab1 = hash_new ();      // Table 2
  int i;                        // Eveyrone's favorite counter variable
  int tests = 0;                // Number of tests
  int errors = 0;               // Number of errors
  char key[128];                // A sample key
  char value[128];              // A sample value

  if (tab0 == NULL)
    return 1;
  if (tab1 == NULL)
    return 1;

  // Some simple tests.  We fill tab0 with a bunch of words, indexed
  // by (a) themselves, (b) their first character, and (c) their first
  // character converted to lowercase.  (Note: we've skipped X words.)
  const char *values[] = { 
    "Aardvark", "Bear",      "Cat",      "Dog",     "Elephant", 
    "Fox",      "Giraffe",   "Hare",     "Iguana",  "Jackalope", 
    "Kangaroo", "Lemur",     "Mandrill", "Newt",    "Opossum",      
    "Pig",      "Quahog",    "Rabbit",   "Snake",   "Tadpole",
    "Urial",    "Vulture",   "Wombat",   "Yak",     "Zebra"
  };
  int num_values = sizeof (values) / sizeof (char *);
  key[1] = '\0';
  // Add all the values
  for (i = 0; i < num_values; i++)
    {
      test_put (tab0, values[i], values[i], &tests, &errors);
      key[0] = values[i][0];
      test_put (tab0, key, values[i], &tests, &errors);
      key[0] += 'a' - 'A';
      test_put (tab0, key, values[i], &tests, &errors);
    } // for
  // Get all the values
  for (i = 0; i < num_values; i++)
    {
      test_get (tab0, values[i], values[i], &tests, &errors);
      key[0] = values[i][0];
      test_get (tab0, key, values[i], &tests, &errors);
      key[0] += 'a' - 'A';
      test_get (tab0, key, values[i], &tests, &errors);
    } // for

  // Try getting things not in the empty table
  test_get (tab1, "A", NULL, &tests, &errors);
  test_get (tab1, "B", NULL, &tests, &errors);

  // Try getting things not in the used table
  test_get (tab0, "", NULL, &tests, &errors);

  // Try putting something new in the used table.
  test_put (tab0, "A", "Animal", &tests, &errors);
  test_get (tab0, "A", "Animal", &tests, &errors);

  // Try putting something different in the second table
  test_put (tab1, "A", "Alpha", &tests, &errors);
  test_get (tab1, "A", "Alpha", &tests, &errors);
  test_get (tab0, "A", "Animal", &tests, &errors);

  // Change lots of values
  for (i = 0; i < num_values; i++)
    {
      strcpy (value, values[i]);
      value[0] = 'X';
      test_put (tab0, values[i], value, &tests, &errors);
      test_get (tab0, values[i], value, &tests, &errors);
    } // for

  // And we're done
  printf ("%d tests conducted.\n", tests);
  printf ("%d errors encountered.\n", errors);
  return errors;
} // hash_utest

/**
 * hashfun_examples
 *   Show examples of a our hash function in action.
 */
void
hashfun_examples ()
{
  static char *strings[] = { "alpha", "beta", "gamma", "a", "b", "c" };
  int num_strings = sizeof (strings) / sizeof(char *);
  int i;

  for (i = 0; i < num_strings; i++)
    {
      printf ("\"%10s\" -> %d\n", strings[i], hashfun (strings[i]));
    } // for
} // hashfun_examples


// +--------------------+---------------------------------------------
// | Exported Functions |
// +--------------------+

hash
hash_new (void)
{
  hash result = (hash) malloc (sizeof (struct hash_table));
  if (result == NULL)
    return result;
  result->size = 0;
  result->capacity = INITIAL_TABLE_CAPACITY;
  result->elements = malloc (sizeof (struct element *) * result->capacity);
  if (result->elements == NULL)
    {
      free (result);
      return NULL;
    }
  bzero (result->elements, sizeof (struct element *) * result->capacity);
  return result;
} // hash_new

int
hash_put (hash table, const char *key, const char *val)
{
  struct hash_element *elem;    // The element for the key/val pair.

  // Find the position into which we should put the key/value pair.
  int pos = hashpos (table, key);

  // If the element is not there
  if (table->elements[pos] == NULL)
    {
      // If we're about to makethe table too big, try to enlarge it.
      if (table->size > (table->capacity / 2))
        {
          if (! hash_enlarge (table))
            {
              hash_error = "could not enlarge hash table";
              return 0;
            }
          pos = hashpos (table, key);
        }
   
      // Allocate space for the new element and its fields.
      elem = (struct hash_element *) malloc (sizeof (struct hash_element));
      if (elem == NULL)
        {
          hash_error = "could not allocate space for new element";
          return 0;
        }
      elem->key = strdup (key);
      if (elem->key == NULL)
        {
          free (elem);
          hash_error = "could not allocate space for copy of key";
          return 0;
        }
      elem->val = strdup (val);
      if (elem->val == NULL)
        {
          free (elem->key);
          free (elem);
          hash_error = "could not allocate space for copy of value";
          return 0;
        } 

      // Put the new element in the table.
      table->elements[pos] = elem;
      ++table->size;

      // And we're done.
      return 1;
    } // if the key is not there

  // If key is supposed to be there and is not
  else if (strcmp (key, table->elements[pos]->key) != 0)
    {
      hash_error = "problem hashing key";
      return 0;
    }

  // If the key is there
  else
    {
      elem = table->elements[pos];
      // If possible, use the same memory.
      if (strlen (elem->val) <= strlen (val))
        strcpy (elem->val, val);
      // Otherwise, allocate more memory.
      else
        {
          char *newval = strdup (val);
          if (newval == NULL)
            {
              hash_error = "insufficient room for copy of value";
              return 0;
            }
          free (elem->val);
          elem->val = newval;
        }
      // And we're done
      return 1;
    }
} // hash_put

char *
hash_get (hash table, const char *key)
{
  int pos = hashpos (table, key);
  if (table->elements[pos] == NULL)
    return NULL;
  return table->elements[pos]->val;
} // hash_get

void
hash_free (hash table)
{
  int i;

  // Free the elements
  for (i = 0; i < table->capacity; i++)
    {
      if (table->elements[i] != NULL)
        {
          free (table->elements[i]->key);
          free (table->elements[i]->val);
          free (table->elements[i]);
          table->elements[i] = NULL;    // Be safe
        } // if current element is not null
    } // for each element

  // Free the array
  free (table->elements);

  // Free the rest
  free (table);
} // hash_free