267 lines
7.3 KiB
C
267 lines
7.3 KiB
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 */
|