path: root/src/symtab.c

/* GNU m4 -- A simple macro processor
   Copyright (C) 1989, 90, 91, 92, 93, 94 Free Software Foundation, Inc.
  
   This program 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 2, or (at your option)
   any later version.
  
   This program 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 this program; if not, write to the Free Software
   Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
*/

/* This file handles all the low level work around the symbol table.  The
   symbol table is a simple chained hash table.  Each symbol is described
   by a struct symbol, which is placed in the hash table based upon the
   symbol name.  Symbols that hash to the same entry in the table are
   kept on a list, sorted by name.  As a special case, to facilitate the
   "pushdef" and "popdef" builtins, a symbol can be several times in the
   symbol table, one for each definition.  Since the name is the same,
   all the entries for the symbol will be on the same list, and will
   also, because the list is sorted, be adjacent.  All the entries for a
   name are simply ordered on the list by age.  The current definition
   will then always be the first found.  */

#include "m4.h"

/*----------------------------------------------------------------------.
| Initialise the symbol table, by allocating the necessary storage, and |
| zeroing all the entries.					        |
`----------------------------------------------------------------------*/

/* Pointer to symbol table.  */
symbol **symtab;

void
symtab_init (void)
{
  int i;
  symbol **s;

  s = symtab = (symbol **) xmalloc (hash_table_size * sizeof (symbol *));

  for (i = hash_table_size; --i >= 0;)
    *s++ = NULL;
}

/*--------------------------------------------------.
| Return a hashvalue for a string, from GNU-emacs.  |
`--------------------------------------------------*/

static int
hash (const char *s)
{
  register int val = 0;

  register const char *ptr = s;
  register char ch;

  while ((ch = *ptr++) != '\0')
    {
      if (ch >= 0140)
	ch -= 40;
      val = ((val << 3) + (val >> 28) + ch);
    };
  val = (val < 0) ? -val : val;
  return val % hash_table_size;
}

/*--------------------------------------------.
| Free all storage associated with a symbol.  |
`--------------------------------------------*/

static void
free_symbol (symbol *sym)
{
  if (SYMBOL_NAME (sym))
    xfree (SYMBOL_NAME (sym));
  if (SYMBOL_TYPE (sym) == TOKEN_TEXT)
    xfree (SYMBOL_TEXT (sym));
  xfree ((voidstar) sym);
}

/*------------------------------------------------------------------------.
| Search in, and manipulation of the symbol table, are all done by	  |
| lookup_symbol ().  It basically hashes NAME to a list in the symbol	  |
| table, and searched this list for the first occurence of a symbol with  |
| the name.								  |
| 									  |
| The MODE parameter determines what lookup_symbol () will do.  It can	  |
| either just do a lookup, do a lookup and insert if not present, do an	  |
| insertion even if the name is already in the list, delete the first	  |
| occurrence of the name on the list or delete all occurences of the name |
| on the list.								  |
`------------------------------------------------------------------------*/

symbol *
lookup_symbol (const char *name, symbol_lookup mode)
{
  int h, cmp = 1;
  symbol *sym, *prev;
  symbol **spp;

  h = hash (name);
  sym = symtab[h];

  for (prev = NULL; sym != NULL; prev = sym, sym = sym->next)
    {
      cmp = strcmp (SYMBOL_NAME (sym), name);
      if (cmp >= 0)
	break;
    }

  /* If just searching, return status of search.  */

  if (mode == SYMBOL_LOOKUP)
    return cmp == 0 ? sym : NULL;

  /* Symbol not found.  */

  spp = (prev != NULL) ?  &prev->next : &symtab[h];

  switch (mode)
    {

    case SYMBOL_INSERT:

      /* Return the symbol, if the name was found in the table.
	 Otherwise, just insert the name, and return the new symbol.  */

      if (cmp == 0 && sym != NULL)
	return sym;
      /* Fall through.  */

    case SYMBOL_PUSHDEF:

      /* Insert a name in the symbol table.  If there is already a symbol
	 with the name, insert this in front of it, and mark the old
	 symbol as "shadowed".  */

      sym = (symbol *) xmalloc (sizeof (symbol));
      SYMBOL_TYPE (sym) = TOKEN_VOID;
      SYMBOL_TRACED (sym) = SYMBOL_SHADOWED (sym) = FALSE;
      SYMBOL_NAME (sym) = xstrdup (name);

      SYMBOL_NEXT (sym) = *spp;
      (*spp) = sym;

      if (mode == SYMBOL_PUSHDEF && cmp == 0)
	{
	  SYMBOL_SHADOWED (SYMBOL_NEXT (sym)) = TRUE;
	  SYMBOL_TRACED (sym) = SYMBOL_TRACED (SYMBOL_NEXT (sym));
	}
      return sym;

    case SYMBOL_DELETE:

      /* Delete all occurences of symbols with NAME.  */

      if (cmp != 0 || sym == NULL)
	return NULL;
      do
	{
	  *spp = SYMBOL_NEXT (sym);
	  free_symbol (sym);
	  sym = *spp;
	}
      while (sym != NULL && strcmp (name, SYMBOL_NAME (sym)) == 0);
      return NULL;

    case SYMBOL_POPDEF:

       /* Delete the first occurence of a symbol with NAME.  */

      if (cmp != 0 || sym == NULL)
	return NULL;
      if (SYMBOL_NEXT (sym) != NULL && cmp == 0)
	SYMBOL_SHADOWED (SYMBOL_NEXT (sym)) = FALSE;
      *spp = SYMBOL_NEXT (sym);
      free_symbol (sym);
      return NULL;

    default:
      M4ERROR ((warning_status, 0,
		"INTERNAL ERROR: Illegal mode to symbol_lookup ()"));
      abort ();
    }
}

/*----------------------------------------------------------------------.
| The following function is used for the cases, where we want to do     |
| something to each and every symbol in the table.  The function        |
| hack_all_symbols () traverses the symbol table, and calls a specified |
| function FUNC for each symbol in the table.  FUNC is called with a    |
| pointer to the symbol, and the DATA argument.			        |
`----------------------------------------------------------------------*/

void
hack_all_symbols (hack_symbol *func, const char *data)
{
  int h;
  symbol *sym;

  for (h = 0; h < hash_table_size; h++)
    {
      for (sym = symtab[h]; sym != NULL; sym = SYMBOL_NEXT (sym))
	(*func) (sym, data);
    }
}

#ifdef DEBUG_SYM

static void
symtab_debug (void)
{
  token_type t;
  token_data td;
  const char *text;
  symbol *s;
  int delete;

  while ((t = next_token (&td)) != NULL)
    {
      if (t != TOKEN_WORD)
	continue;
      text = TOKEN_DATA_TEXT (&td);
      if (*text == '_')
	{
	  delete = 1;
	  text++;
	}
      else
	delete = 0;

      s = lookup_symbol (text, SYMBOL_LOOKUP);

      if (s == NULL)
	printf ("Name `%s' is unknown\n", text);

      if (delete)
	(void) lookup_symbol (text, SYMBOL_DELETE);
      else
	(void) lookup_symbol (text, SYMBOL_INSERT);
    }
  hack_all_symbols (dump_symbol);
}

static void
symtab_print_list (int i)
{
  symbol *sym;

  printf ("Symbol dump #d:\n", i);
  for (sym = symtab[i]; sym != NULL; sym = sym->next)
    printf ("\tname %s, addr 0x%x, next 0x%x, flags%s%s\n",
	   SYMBOL_NAME (sym), sym, sym->next,
	   SYMBOL_TRACED (sym) ? " traced" : "",
	   SYMBOL_SHADOWED (sym) ? " shadowed" : "");
}

#endif /* DEBUG_SYM */