/* symbols.c -- Symbol Table Operations


This file is part of STAR, the Saturn Macro Assembler.

   STAR is not distributed by the Free Software Foundation. Do not ask
them for a copy or how to obtain new releases. Instead, send e-mail to
the address below. STAR is merely covered by the GNU General Public
License.

Please send your comments, ideas, and bug reports to
Jan Brittenson <bson@ai.mit.edu>

*/


/* Copyright (C) 1990, 1991 Jan Brittenson.

   STAR is free software; you can redistribute it and/or modify it
under the terms of the GNU General Public License as published by the
Free Software Foundation; either version 1, or (at your option) any
later version.

   STAR is distributed in the hope that it will be useful, but WITHOUT
ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
for more details.

   You should have received a copy of the GNU General Public License
along with STAR; see the file COPYING. If not, to obtain a copy, write
to the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139,
USA, or send e-mail to bson@ai.mit.edu. */


/* Notes regarding the hashing algorithm:
 *
 * The key is calculated by sequentially summing up characters while
 * shifting left once after each consequtive character, and finally
 * adding the number of characters. This means that the log2(SYM_NHASH)-1
 * last characters and the length are used in the key. For instance,
 * if SYM_NHASH is set to 8192, this means that the last 12 characters
 * and the string length are used. Some simple tests I've run suggests 
 * this is an almost perfect method for us.
 */

#include <stdio.h>
#include "star.h"
#include "symbols.h"


/* Create symbol table */
SYM_ROOT *sm_open(creator, destructor)
  char *(*creator)();
  void (*destructor)();
{
  SYM_ROOT *stmp;

  if(!(stmp = (SYM_ROOT *) (*creator)(sizeof(SYM_ROOT))))
    fatal("Can't allocate %d bytes for symbol table", sizeof(SYM_ROOT));

  bclear(stmp, sizeof *stmp);

  stmp->sm_create = creator;
  stmp->sm_destr  = destructor;

  return(stmp);
}


/* Hash string - see description above */
hash_symbol(cp)
  register char *cp;
{
  register unsigned sum, nchars;

  for(sum = nchars = 0; *cp; cp++, sum <<= 1, nchars++)
    sum += (unsigned char) toupper(*cp);

  sum += nchars;

  return(sum & (SYM_NHASH-1));
}


/* Search symbol table for symbol
 *
 * Return pointer to it if found, otherwise NULL.
 */
SYM_NODE *sm_find_sym(sm_root, snam)
  SYM_ROOT *sm_root;
  register char *snam;
{
  register SYM_NODE *ssp;
  
  if(!sm_root)
    return(NULL);


  /* Traverse symbol table searching for symbol */
  ssp = sm_root->sm_slot[ hash_symbol(snam) ];

  while(ssp)
    switch(scmp(snam, ssp->name))
      {
      case -1:	ssp = ssp->slt; break;
      case 1:	ssp = ssp->sgt; break;
      default:	return(ssp);
      }
  
  return(NULL);
}


/* Duplicate string with given constructor */
static char *sm_strdup(constr, str)
  char *(*constr)(), *str;
{
  char *tmp;
  extern char *strcpy();

  if(!(tmp = (*constr)(strlen(str)+1)))
    fatal("Can't allocate %d bytes for symbol name data", strlen(str)+1);

  return(strcpy(tmp, str));
}


/* Enter new symbol into table.
 *
 * Allocates new entry, allocates string space and binds symbol value.
 * The symbol is presumed NOT to exist. Check with 'sm_find_sym()' 
 * before calling this function.
 */
SYM_NODE *sm_enter_sym(sm_root, snam, vl, flg)
  SYM_ROOT *sm_root;
  char *snam;
  struct val vl;
  int flg;
{
  SYM_NODE *ssp, *parent_node;
  char *sp;
  int tmp, hashval;

  
  /* Search for place where symbol should be added */
  tmp = 0;
  hashval = hash_symbol(snam);
  ssp = sm_root->sm_slot[hashval];
  parent_node= NULL;

  while(ssp)
    switch(tmp = scmp(snam, ssp->name))
      {
      case -1:	parent_node = ssp; ssp = ssp->slt; break;
      case 1:	parent_node = ssp; ssp = ssp->sgt; break;
      case 0:
	{
	  sgnwrn("Possible assembler error: symbol `%s' already exists",
		 snam);
	  return(ssp);
	}
      }
  
  /* Allocate string space */
  sp = sm_strdup(sm_root->sm_create, snam);
  
  for(snam = sp; *snam = toupper(*snam); snam++);

  /* Create node */
  if(!(ssp = (SYM_NODE *) (*sm_root->sm_create)(sizeof(SYM_NODE))))
    fatal("Can't allocate %d bytes for symbol table entry", sizeof(SYM_NODE));
  
  /* Update hash table, if necessary, with new root node */
  if(!sm_root->sm_slot[hashval])
    sm_root->sm_slot[hashval] = ssp;
  else
    /* Else hang onto proper leg */
    if(parent_node)
      if(tmp == -1)
	parent_node->slt = ssp;
      else
	parent_node->sgt = ssp;
  
  ssp->slt = ssp->sgt = NULL;
  ssp->vlink = NULL;
  ssp->name = sp;
  ssp->value = vl;
  ssp->flags = flg;

  sm_root->nsymbols++;

  return(ssp);
}
