home *** CD-ROM | disk | FTP | other *** search
/ The World of Computer Software / World_Of_Computer_Software-02-387-Vol-3of3.iso / m / m4v05as.zip / SYMTAB.C < prev    next >
C/C++ Source or Header  |  1992-02-22  |  7KB  |  274 lines
  1. /*
  2.  * GNU m4 -- A simple macro processor
  3.  * Copyright (C) 1989, 1990 Free Software Foundation, Inc. 
  4.  *
  5.  * This program is free software; you can redistribute it and/or modify
  6.  * it under the terms of the GNU General Public License as published by
  7.  * the Free Software Foundation; either version 1, or (at your option)
  8.  * any later version.
  9.  *
  10.  * This program is distributed in the hope that it will be useful,
  11.  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  12.  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13.  * GNU General Public License for more details.
  14.  *
  15.  * You should have received a copy of the GNU General Public License
  16.  * along with this program; if not, write to the Free Software
  17.  * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  18.  */
  19.  
  20. /*
  21.  * MS-DOS port (c) 1990 by Thorsten Ohl, ohl@gnu.ai.mit.edu
  22.  * This port is also distributed under the terms of the
  23.  * GNU General Public License as published by the
  24.  * Free Software Foundation.
  25.  *
  26.  * Please note that this file is not identical to the
  27.  * original GNU release, you should have received this
  28.  * code as patch to the official release.
  29.  *
  30.  * $Header: e:/gnu/m4/RCS/symtab.c 0.5.1.0 90/09/28 18:36:45 tho Exp $
  31.  */
  32.  
  33. /* 
  34.  * This file handles all the low level work around the symbol table.
  35.  * The symbol table is a simple chained hash table.  Each symbol is
  36.  * desribed by a struct symbol, which is placed in the hash table based
  37.  * upon the symbol name.  Symbols that hash to the same entry in the
  38.  * table are kept on a list, sorted by name.  As a special case, to
  39.  * facilitate the "pushdef" and "popdef" builtins, a symbol can be
  40.  * several times in the symbol table, one for each definition.  Since
  41.  * the name is the same, all the entries for the symbol will be on the
  42.  * same list, and will also, because the list is sorted, be adjacent.
  43.  * All the entries for a name are simply ordered on the list by age.
  44.  * The current definition will then always be the first found.
  45.  */
  46. #include "m4.h"
  47.  
  48. #ifdef MSDOS
  49. static int hash (char *s);
  50. static void free_symbol (struct symbol *sym);
  51. #endif /* MSDOS */
  52.  
  53. /* 
  54.  * Initialise the symbol table, by allocating the necessary storage, and
  55.  * zeroing all the entries.
  56.  */
  57.  
  58. /* Pointer to symbol table */
  59. symbol **symtab;
  60.  
  61. void 
  62. symtab_init()
  63. {
  64.     symtab = (symbol **)xmalloc(hash_table_size * sizeof(symbol*));
  65.     bzero((char *)symtab, hash_table_size * sizeof(symbol*));
  66. }
  67.  
  68. /* hash - retun a hashvalue for a string, from GNU-emacs. */
  69. static int 
  70. hash (s)
  71.     char *s;
  72. {
  73.     register int val = 0;
  74.  
  75.     register char *ptr = s, ch;
  76.  
  77.     while ((ch = *ptr++) != (char) NULL) {
  78.     if (ch >= 0140)
  79.         ch -= 40;
  80.     val = ((val<<3) + (val>>28) + ch);
  81.     };
  82.     val = (val < 0)?-val:val;
  83.     return val % hash_table_size;
  84. }
  85.  
  86. /* 
  87.  * free all storage associated with a symbol.
  88.  */
  89. static void 
  90. free_symbol(sym)
  91.     symbol *sym;
  92. {
  93.     if (SYMBOL_NAME(sym))
  94.     xfree(SYMBOL_NAME(sym));
  95.     if (SYMBOL_TYPE(sym) == TOKEN_TEXT)
  96.     xfree(SYMBOL_TEXT(sym));
  97.     xfree((char *)sym);
  98. }
  99.  
  100. /* 
  101.  * Search in, and manipulation of the symbol table, are all done by
  102.  * lookup_symbol().  It basically hashes NAME to a list in the symbol
  103.  * table, and searched this list for the first occurence of a symbol
  104.  * with the name.
  105.  *
  106.  * The MODE parameter determines what lookup_symbol() will do.  It can
  107.  * either just do a lookup, do a lookup and insert if not present, do an
  108.  * insertation even if the name is already in the list, delete the first
  109.  * occurence of the name on the list, og delete all occurences of the
  110.  * name on the list.
  111.  */
  112. symbol *
  113. lookup_symbol(name, mode)
  114.     char *name;
  115.     symbol_lookup mode;
  116. {
  117.     int h, cmp = 1;
  118.     symbol *sym, *prev;
  119.     symbol **spp;
  120.  
  121.     h = hash(name);
  122.     sym = symtab[h];
  123.  
  124.     for (prev = nil ; sym != nil; prev = sym, sym = sym->next) {
  125.     cmp = strcmp(SYMBOL_NAME(sym), name);
  126.     if (cmp >= 0)
  127.         break;
  128.     }
  129.  
  130.     /* 
  131.      * If just searching, return status of search.
  132.      */
  133.     if (mode == SYMBOL_LOOKUP)
  134.     return cmp == 0 ? sym : nil;
  135.  
  136.     /* symbol not found */
  137.  
  138.     spp = (prev != nil) ?  &prev->next : &symtab[h];
  139.  
  140.     switch (mode) {
  141.  
  142.     case SYMBOL_INSERT:
  143.     /* 
  144.      * Return the symbol, if the name was found in the table.
  145.      * Otherwise, just insert the name, and return the new symbol.
  146.      */
  147.     if (cmp == 0 && sym != nil)
  148.         return sym;
  149.     /* fall through */
  150.  
  151.     case SYMBOL_PUSHDEF:
  152.     /* 
  153.      * Insert a name in the symbol table.  If there is already a
  154.      * symbol with the name, insert this in front of it, and mark
  155.      * the old symbol as "shadowed".
  156.      */
  157.     sym = (symbol *)xmalloc(sizeof(struct symbol));
  158.     SYMBOL_TYPE(sym) = TOKEN_VOID;
  159.     SYMBOL_TRACED(sym) = SYMBOL_SHADOWED(sym) = false;
  160.     SYMBOL_NAME(sym) = xstrdup(name);
  161.  
  162.     SYMBOL_NEXT(sym) = *spp;
  163.     (*spp) = sym;
  164.  
  165.     if (mode == SYMBOL_PUSHDEF && cmp == 0) {
  166.         SYMBOL_SHADOWED(SYMBOL_NEXT(sym)) = true;
  167.         SYMBOL_TRACED(sym) = SYMBOL_TRACED(SYMBOL_NEXT(sym));
  168.     }
  169.     return sym;
  170.  
  171.     case SYMBOL_DELETE:
  172.     /* 
  173.      * Delete all occurences of symbols with NAME.
  174.      */
  175.     if (cmp != 0 || sym == nil)
  176.         return nil;
  177.     do {
  178.         *spp = SYMBOL_NEXT(sym);
  179.         free_symbol(sym);
  180.         sym = *spp;
  181.     } while (sym != nil && strcmp(name, SYMBOL_NAME(sym)) == 0);
  182.     return nil;
  183.  
  184.     case SYMBOL_POPDEF:
  185.     /* 
  186.      * Delete the first occurence of a symbol with NAME.
  187.      */
  188.     if (cmp != 0 || sym == nil)
  189.         return nil;
  190.     if (SYMBOL_NEXT(sym) != nil && cmp == 0)
  191.         SYMBOL_SHADOWED(SYMBOL_NEXT(sym)) = false;
  192.     *spp = SYMBOL_NEXT(sym);
  193.     free_symbol(sym);
  194.     return nil;
  195.     
  196.     default:
  197.     internal_error("Illegal mode to symbol_lokup()");
  198.     break;
  199.     }
  200.     /* NOTREACHED */
  201. }
  202.  
  203.  
  204. /* 
  205.  * The following function are used for the cases, where we want to do
  206.  * something to each and every symbol in the table.  The function
  207.  * hack_all_symbols() traverses the symbol table, and calls a specified
  208.  * function FUNC for each symbol in the table.  FUNC is called with a
  209.  * pointer to the symbol, and the DATA argument.
  210.  */
  211.  
  212. void 
  213. hack_all_symbols(func, data)
  214.     hack_symbol *func;
  215.     char *data;
  216. {
  217.     int h;
  218.     symbol *sym;
  219.  
  220.     for (h = 0; h < HASHMAX; h++) {
  221.     for (sym = symtab[h]; sym != nil; sym = SYMBOL_NEXT(sym))
  222.         (*func)(sym, data);
  223.     }
  224. }
  225.  
  226.  
  227. #ifdef DEBUG_SYM
  228.  
  229. symtab_debug()
  230. {
  231.     token_type t;
  232.     token_data td;
  233.     char *text;
  234.     symbol *s;
  235.     int delete;
  236.  
  237.     while ((t = next_token(&td)) != nil) {
  238.     if (t != TOKEN_WORD)
  239.         continue;
  240.     text = TOKEN_DATA_TEXT(&td);
  241.     if (*text == '_') {
  242.         delete = 1;
  243.         text++;
  244.     } else
  245.         delete = 0;
  246.  
  247.     s = lookup_symbol(text, SYMBOL_LOOKUP);
  248.  
  249.     if (s == nil)
  250.         printf("Name `%s' is unknown\n", text);
  251.  
  252.     if (delete)
  253.         (void)lookup_symbol(text, SYMBOL_DELETE);
  254.     else
  255.         (void)lookup_symbol(text, SYMBOL_INSERT);
  256.     }
  257.     hack_all_symbols(dump_symbol);
  258. }
  259.  
  260.  
  261. symtab_print_list(i)
  262.     int i;
  263. {
  264.     symbol *sym;
  265.  
  266.     printf("Symbol dump #d:\n", i);
  267.     for (sym = symtab[i]; sym != nil; sym = sym->next)
  268.     printf("\tname %s, addr 0x%x, next 0x%x, flags%s%s\n",
  269.            SYMBOL_NAME(sym), sym, sym->next,
  270.            SYMBOL_TRACED(sym) ? " traced" : "",
  271.            SYMBOL_SHADOWED(sym) ? " shadowed" : "");
  272. }
  273. #endif
  274.