/**
 * hashtable.c
 *   An implementation of hash tables, based loosely on code from K&R 2nd,
 *   pp. 143-145.
 */

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

#include <stdlib.h>     // For malloc
#include <string.h>     // For strcmp and strdup
#include <stdio.h>      // For printf
#include "hashtable.h"
#include "hashfun.h"


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

/**
 * Nodes in a list in one element of the hash table.
 */
struct element {          
  struct element *next;   // Next entry in the list
  char *key;            // The key
  char *value;          // The value
}; // struct element

// +-------------------+----------------------------------------------
// | Macros for Exam 3 |
// +-------------------+

#define ITERATE_TABLE(TABLE, ELT, CODE) \
  do \
    { \
      int i; \
      for (i = 0; i < TABLE->size; i++) \
        { \
          ELT = TABLE->contents[i]; \
          while (ELT != NULL) \
            { \
              CODE; \
              ELT = ELT->next; \
            } \
        } \
   } \
  while (0)


// +-----------------+------------------------------------------------
// | Local Functions |
// +-----------------+

/**
 * Find an element element in a hash table.  (Based on lookup in K&R.)
 */
struct element *
lookup (struct hashtable *hashtab, char *str)
{
  unsigned pos = hash (str) % hashtab->size;
  struct element *ep;

  for (ep = hashtab->contents[pos]; ep != NULL; ep = ep->next)
    if (strcmp (str, ep->key) == 0)
      return ep;   // found
  return NULL; // not found
} // lookup


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

int 
assign (struct hashtable *table, char *key, char *value)
{
  struct element *ep;

  // Is the element there?  If so, replace the value
  if ((ep = lookup (table, key)) != NULL)
    {
      // Allocate space for the new value
      char *newval = strdup (value);
      // Sanity check
      if (newval == NULL)
        return 0;
      // Remove the old value
      free (ep->value);
      ep->value = newval;
    } // if the element is already there

  // Otherwise, allocate a new cell and insert it
  else
    {
      unsigned hashval;

      // Allocate the new element
      ep = malloc (sizeof (struct element));
      if (ep == NULL)
        return 0;
      // Copy the key
      ep->key = strdup (key);
      if (ep->key == NULL)
        {
          free (ep);
          return 0;
        }
      // Copy the value
      ep->value = strdup (value);
      if (ep->value == NULL)
        {
          free (ep->key);
          free (ep);
          return 0;
        }

      // Insert it into the table
      hashval = hash (key) % table->size;
      ep->next = table->contents[hashval];
      table->contents[hashval] = ep;
      ++(table->elements);
    } // if the element is not already there

  // If we got this far, we succeeded
  return 1;
} // assign


char *
get (struct hashtable *hashtab, char *key)
{
  struct element *ep = lookup (hashtab, key);
  if (ep == NULL)
    return NULL;
  else
    return ep->value;
} // get

struct hashtable *
new_hashtable (int size)
{
  struct hashtable *hashtab;
  int i;

  // Allocate space for the hash table.
  hashtab = malloc (sizeof (struct hashtable));
  if (hashtab == NULL)
    return NULL;
  hashtab->size = size; // -> means "deref pointer and grab field"
  hashtab->elements = 0;

  // Allocate space for the real part of the hash table.
  hashtab->contents = malloc (size * sizeof (struct element *));

  // If we fail, clean up.
  if (hashtab->contents == NULL)
    {
      free (hashtab);
      return NULL;
    }

  // Clear out the table
  for (i = 0; i < size; i++)
    hashtab->contents[i] = NULL;

  // And we're done.
  return hashtab;
} // new_hashtable (int)

// +-----------------------+------------------------------------------
// | Functions from Exam 3 |
// +-----------------------+

void
old_print_table (struct hashtable *table)
{
  int i;
  struct element *tmp;

  for (i = 0; i < table->size; i++)
    {
      tmp = table->contents[i];
      while (tmp != NULL)
        {
          printf ("%s -> %s\n", tmp->key, tmp->value);
          tmp = tmp->next;
        } // while
    } // for
} // print_table

char *
old_find_key (struct hashtable *table, char *value)
{
  int i;
  struct element *elt;

  for (i = 0; i < table->size; i++)
    {
      elt = table->contents[i];
      while (elt != NULL)
        {
          if (strcmp (elt->value, value) == 0)
            return elt->key;
          elt = elt->next;
        } // while
    } // for

  return NULL;
} // find_key


// +----------------------+-------------------------------------------
// | Functions for Exam 3 |
// +----------------------+

void
print_table (struct hashtable *table)
{
  struct element *tmp;

  ITERATE_TABLE (table, tmp, 
                 printf ("%s -> %s\n", tmp->key, tmp->value));
} // print_table

char *
find_key (struct hashtable *table, char *value)
{
  struct element *elt;

  ITERATE_TABLE (table, elt, 
                 if (strcmp (elt->value, value) == 0) return elt->key);

  return NULL;
} // find_key

int 
count_values (struct hashtable *table, char *value)
{
  int count = 0;
  struct element *elt;

  ITERATE_TABLE (table, elt,
                 if (strcmp (elt->value, value) == 0) ++count);

  return count;
} // count_values