/* Written by Max Hailperin <max@gac.edu>.  Maps a string to a struct sym*,
   with the property that textually equal strings are mapped to the same
   struct sym*.  The first time a string is seen, a new struct sym is
   allocated and initializeSym used to initialize fields other than name.
   Last change February 16, 1995. */

#include "symtab.h"
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

#define LG_INITIAL_SIZE 8
#define INITIAL_SIZE (1 << LG_INITIAL_SIZE)
#define GOLDEN_MULTIPLIER 2654435769UL   /* floor(2^31 * (sqrt(5)-1)) */

static struct bucket {
  struct sym *this;
  struct bucket *rest;
} **table = NULL;
static unsigned size, lg_size, count;

static struct bucket **findSlot(const char *s){
  /* use hashing to find the right bucket chain */
  const char *p;
  unsigned long h = 0, g;
  for(p = s; *p; p++){  /* this loop does the hashpjw computation */
    h = (h << 4) + *p;  /* see Aho, Sethi, and Ullman p. 436 */
    if((g = h&0xf0000000) != 0)
      h ^= (g | (g >> 24));
  }
  h *= GOLDEN_MULTIPLIER; /* these two lines do division hashing by */
  h >>= 32 - lg_size;;    /* golden ratio method; see Knuth vol. 3 */
  if(h >= size){
    fprintf(stderr, "There is a bug in symtab -- hash value is too big.\n");
    fprintf(stderr, "h = %lu, size = %u\n", h, size);
    exit(1);
  }
  return &table[h];
}

struct sym *stringToSym(const char *s){
  struct bucket **bp;

  if(table == NULL){ /* do initial setup */
    if(sizeof(unsigned long) * CHAR_BIT != 32){
      fprintf(stderr, "The symtab package needs rewriting for this machine.\n");
      fprintf(stderr, "The assumption of 32-bit wordsize is violated.\n");
      exit(1);
    }
    if((table = calloc(INITIAL_SIZE, sizeof(struct bucket *))) == NULL){
      fprintf(stderr, "Couldn't allocate space for symbol table.\n");
      exit(1);
    }
    size = INITIAL_SIZE;
    lg_size = LG_INITIAL_SIZE;
    count = 0;
  }

  bp = findSlot(s);

  { /* see if sym already exists in that bucket chain */
    struct bucket *b;
    for(b = *bp; b; b = b->rest)
      if(strcmp(b->this->name, s) == 0)
        return b->this;
  }

  { /* it doesn't, so insert at front of chain */
    struct bucket *b;
    if((b = malloc(sizeof(struct bucket))) == NULL){
      fprintf(stderr, "Couldn't allocate hash bucket for %s.\n", s);
      exit(1);
    }
    b->rest = *bp;
    *bp = b;
    if((b->this = malloc(sizeof(struct sym))) == NULL){
      fprintf(stderr, "Couldn't allocate sym structure for %s.\n", s);
      exit(1);
    }
    if((b->this->name = malloc(strlen(s)+1)) == NULL){
      fprintf(stderr, "Couldn't allocate space for symbol name %s.\n", s);
      exit(1);
    }
    strcpy(b->this->name, s);
    initializeSym(b->this);
    if(++count > size){
      /* rehash into twice as big a table */
      unsigned oldSize = size, i;
      struct bucket **oldTable = table;
      size *= 2; lg_size++;
      if((table = calloc(size, sizeof(struct bucket *))) == NULL){
        fprintf(stderr, "Couldn't allocate memory to grow hash table.\n");
        exit(1);
      }
      for(i = 0; i < oldSize; i++){
        struct bucket *b, *next_b;
        for(b = oldTable[i]; b; b = next_b){
          struct bucket **bp;
          next_b = b->rest; /* save before clobbering it */
          bp = findSlot(b->this->name);
          b->rest = *bp;
          *bp = b;
        }
      }
      free(oldTable);
    }
    return b->this;
  }
}