/**
 * hash.c
 *   A single hash table.  Taken from K&R 6.6.  Updated by SamR.
 */

// +------------+-----------------------------------------------------
// | Philosophy |
// +------------+

/*

Provides a "global" hash table.  (That is, there's one table that all
programs use.)

The hash table uses chaining, rather than linear probig, to store
elements.

The hash table is of a fixed size.  It will slow down significantly
when the number of elements is large.

 */


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

#include <stdlib.h>	// For malloc
#include <string.h>	// For strdup

#include "hash.h"


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

/**
 * The default size of a hash table.
 */
#define HASHSIZE 101


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

/**
 * A list of entries in the table.
 */
struct nlist
  {
    struct nlist *next;         // Next entry in the list
    char *name;                 // The name
    char *defn;                 // The definition
  };


// +--------+---------------------------------------------------------
// | Locals |
// +--------+

/**
 * The hash table.  Make sure it's filled with NULLs.
 */
static struct nlist *hashtab[HASHSIZE] = { (struct nlist *) NULL };


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

/**
 * hash(str)
 *   Form a hash value for string s.
 */
static unsigned
hash (char *str)
{
  unsigned hashval;
  for (hashval = 0; *str != '\0'; str++)
     hashval = *str + 31 * hashval;
   return hashval % HASHSIZE;
}  // hash

/**
 * lookup(name)
 *   Look up a name in the hash table.  Return the entry that contains
 *   the name.
 */
static struct nlist *
lookup (char *name)
{
  struct nlist *np;
  // Grab the list in the appropriate cell and look at each element
  //   in that list.
  for (np = hashtab[hash(name)]; np != NULL; np = np->next)
    {
      // If the current entry contains the string
      if (strcmp (name, np->name) == 0)
        {
          // Return that entry
          return np;
        } // if
    } // for
  // If we've gotten this far, it's not in the list
  return NULL;
} // lookup 

/**
 * install(name, defn)
 *   Put a name/defn pair in the hash table.
 */
static struct nlist *
install(char *name, char *defn)
{
  struct nlist *np;     // One list in the table
  unsigned int hashval; // The hash value of the name

  // Loop up the name to see if it's there already.
  np = lookup (name);

  // If there's not an entry
  if (np == NULL)
    {
      // Allocate space for a new entry
      np = (struct nlist *) malloc (sizeof (struct nlist));
      if (np == NULL)
        return NULL;
      // Make a copy of the name
      np->name = strdup (name);
      if (np->name == NULL)
        {
          free (np);
          return NULL;
        } // if we could not make a copy of the name
      // Make a copy of the definition
      np->defn = strdup (defn); 
      if (np->defn == NULL)
        {
          free (np->name);
          free (np);
          return NULL;
        } // if we could not make a copy of the definition
      // Find the appropriate list in the table and put it on the front
      hashval = hash(name);
      np->next = hashtab[hashval];
      hashtab[hashval] = np;
    } // if there's not yet an entry for name

  // If there's already a matching entry
  else
    {
      char *newdefn = strdup (defn);
      if (newdefn == NULL)
        return NULL;
      free (np->defn);
      np->defn = newdefn;
    } // if there's already a matching entry

  // And we're done
  return np;
} // install


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

int 
table_put (char *name, char *defn)
{
  struct nlist *np;     // The node that contains char/defn
  np = install (name, defn);
  if (np == NULL)
    return 0;
  else
    return 1;
} // table_put

char *
table_get (char *name)
{
  struct nlist *np;	// The node that contains the name
  np = lookup (name);
  if (np == NULL)
    return NULL;
  else
    return np->defn;
} // table_get