/*
 * hash.c
 *
 */

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

#define	HASH_TABLE_SIZE	255

struct Symbol
{
  char			*name;
  char			**namePtr;
  char			*label;
  struct Bucket		*ports;
  char			*remainder;
  struct Bucket		*instances;
};

struct Bucket
{
  struct Symbol	*symbol;
  struct Bucket	*prev;
  struct Bucket *next;
};


void			InitHashTable ();
struct Symbol		*GetSymbol ();
static unsigned int	Key2Hash ();

void			NullSymbol ();

void			FirstBucket ();
void			LastBucket ();
void			AddBucket ();
struct Symbol		*InBucket ();


void InitHashTable (HashTable)
  struct Bucket *HashTable[HASH_TABLE_SIZE];
{
  unsigned int  i;

  for (i = 0; i < HASH_TABLE_SIZE; i ++)
  {
    HashTable[i] = 0;
  }
}


struct Symbol *GetSymbol (HashTable, SymbolName)
  struct Bucket *HashTable[HASH_TABLE_SIZE];
  char          *SymbolName;
{
  unsigned int  i;
  struct Bucket *theHash;

  i = Key2Hash (SymbolName) % HASH_TABLE_SIZE;
  if (!HashTable[i])
  {
    HashTable[i] = (struct Bucket *) malloc (sizeof (struct Bucket));
    HashTable[i]->symbol = (struct Symbol *) malloc (sizeof (struct Symbol));
    HashTable[i]->symbol->name = (char *) malloc (strlen (SymbolName) + 1);
    strcpy (HashTable[i]->symbol->name, SymbolName);
    HashTable[i]->prev = 0;
    HashTable[i]->next = 0;
    return HashTable[i]->symbol;
  }
  else
  {
    theHash = HashTable[i];
    while (theHash)
    {
      if (!strcmp (theHash->symbol->name, SymbolName))
        return theHash->symbol;
      else if (!theHash->next)
      {
        theHash->next = (struct Bucket *) malloc (sizeof (struct Bucket));
        theHash->next->symbol =
          (struct Symbol *) malloc (sizeof (struct Symbol));
        theHash->next->symbol->name = (char *) malloc (strlen (SymbolName) + 1);
        strcpy (theHash->next->symbol->name, SymbolName);
        theHash->next->prev = theHash;
        theHash->next->next = 0;
        return theHash->next->symbol;
      }
      else
        theHash = theHash->next;
    }
  }
}


#define	NBITS_IN_UNSIGNED       32
#define	THREE_QUARTERS          24
#define	ONE_EIGHTH              4
#define	HIGH_BITS               (~((unsigned)(~0) >> ONE_EIGHTH))

static unsigned int Key2Hash (key)
  char *key;
{
  unsigned int  hash = 0;
  unsigned int  temp;

  for ( ; *key; ++key)
  {
    hash = (hash << ONE_EIGHTH) + (unsigned int) *key;
    if (temp = hash & HIGH_BITS)
      hash = (hash ^ (temp >> THREE_QUARTERS)) & ~HIGH_BITS;
  }
  return hash;
}

#undef	NBITS_IN_UNSIGNED
#undef	THREE_QUARTERS
#undef	ONE_EIGHTH
#undef	HIGH_BITS


void NullSymbol (symbolPtr)
  struct Symbol *symbolPtr;
{
  symbolPtr->name = NULL;
  symbolPtr->namePtr = NULL;
  symbolPtr->label = NULL;
  symbolPtr->ports = NULL;
  symbolPtr->remainder = NULL;
  symbolPtr->instances = NULL;
}


void FirstBucket (bucketHdl)
  struct Bucket **bucketHdl;
{
  if (*bucketHdl)
    while ((*bucketHdl)->prev)
      *bucketHdl = (*bucketHdl)->prev;
}


void LastBucket (bucketHdl)
  struct Bucket **bucketHdl;
{
  if (*bucketHdl)
    while ((*bucketHdl)->next)
      *bucketHdl = (*bucketHdl)->next;
}


void AddBucket (bucketHdl)
  struct Bucket **bucketHdl;
{
  LastBucket (bucketHdl);
  if (!*bucketHdl)
  {
    *bucketHdl = (struct Bucket *) malloc (sizeof (struct Bucket));
    (*bucketHdl)->symbol = (struct Symbol *) malloc (sizeof (struct Symbol));
    NullSymbol ((*bucketHdl)->symbol);
    (*bucketHdl)->prev = NULL;
    (*bucketHdl)->next = NULL;
  }
  else
  {
    (*bucketHdl)->next = 
      (struct Bucket *) malloc (sizeof (struct Bucket));
    (*bucketHdl)->next->symbol =
      (struct Symbol *) malloc (sizeof (struct Symbol));
    NullSymbol ((*bucketHdl)->next->symbol);
    (*bucketHdl)->next->prev = *bucketHdl;
    (*bucketHdl)->next->next = NULL;
    *bucketHdl = (*bucketHdl)->next;
  }
}


struct Symbol *InBucket (bucketHdl, word)
  struct Bucket **bucketHdl;
  char          *word;
{
  FirstBucket (bucketHdl);
  if (!strcmp (*(*bucketHdl)->symbol->namePtr, word))
    return ((*bucketHdl)->symbol);
  else
    while ((*bucketHdl)->next)
    {
      *bucketHdl = (*bucketHdl)->next;
      if (!strcmp (*(*bucketHdl)->symbol->namePtr, word))
        return ((*bucketHdl)->symbol);
    }
  return (NULL);
}