/*
 * GNU m4 -- A simple macro processor
 * Copyright (C) 1989, 1990 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 1, 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.
 */

/*
 * MS-DOS port (c) 1990 by Thorsten Ohl, ohl@gnu.ai.mit.edu
 * This port is also distributed under the terms of the
 * GNU General Public License as published by the
 * Free Software Foundation.
 *
 * Please note that this file is not identical to the
 * original GNU release, you should have received this
 * code as patch to the official release.
 *
 * $Header: e:/gnu/m4/RCS/symtab.c 0.5.1.0 90/09/28 18:36:45 tho Exp $
 */

/* 
 * This file handles all the low level work around the symbol table.
 * The symbol table is a simple chained hash table.  Each symbol is
 * desribed 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"

#ifdef MSDOS
static int hash (char *s);
static void free_symbol (struct symbol *sym);
#endif /* MSDOS */

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

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

void 
symtab_init()
{
    symtab = (symbol **)xmalloc(hash_table_size * sizeof(symbol*));
    bzero((char *)symtab, hash_table_size * sizeof(symbol*));
}

/* hash - retun a hashvalue for a string, from GNU-emacs. */
static int 
hash (s)
    char *s;
{
    register int val = 0;

    register char *ptr = s, ch;

    while ((ch = *ptr++) != (char) NULL) {
	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(sym)
    symbol *sym;
{
    if (SYMBOL_NAME(sym))
	xfree(SYMBOL_NAME(sym));
    if (SYMBOL_TYPE(sym) == TOKEN_TEXT)
	xfree(SYMBOL_TEXT(sym));
    xfree((char *)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
 * insertation even if the name is already in the list, delete the first
 * occurence of the name on the list, og delete all occurences of the
 * name on the list.
 */
symbol *
lookup_symbol(name, mode)
    char *name;
    symbol_lookup mode;
{
    int h, cmp = 1;
    symbol *sym, *prev;
    symbol **spp;

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

    for (prev = nil ; sym != nil; 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 : nil;

    /* symbol not found */

    spp = (prev != nil) ?  &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 != nil)
	    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(struct 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 == nil)
	    return nil;
	do {
	    *spp = SYMBOL_NEXT(sym);
	    free_symbol(sym);
	    sym = *spp;
	} while (sym != nil && strcmp(name, SYMBOL_NAME(sym)) == 0);
	return nil;

    case SYMBOL_POPDEF:
	/* 
	 * Delete the first occurence of a symbol with NAME.
	 */
	if (cmp != 0 || sym == nil)
	    return nil;
	if (SYMBOL_NEXT(sym) != nil && cmp == 0)
	    SYMBOL_SHADOWED(SYMBOL_NEXT(sym)) = false;
	*spp = SYMBOL_NEXT(sym);
	free_symbol(sym);
	return nil;
	
    default:
	internal_error("Illegal mode to symbol_lokup()");
	break;
    }
    /* NOTREACHED */
}


/* 
 * The following function are 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(func, data)
    hack_symbol *func;
    char *data;
{
    int h;
    symbol *sym;

    for (h = 0; h < HASHMAX; h++) {
	for (sym = symtab[h]; sym != nil; sym = SYMBOL_NEXT(sym))
	    (*func)(sym, data);
    }
}


#ifdef DEBUG_SYM

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

    while ((t = next_token(&td)) != nil) {
	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 == nil)
	    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);
}


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

    printf("Symbol dump #d:\n", i);
    for (sym = symtab[i]; sym != nil; 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
