home *** CD-ROM | disk | FTP | other *** search
/ InfoMagic Source Code 1993 July / THE_SOURCE_CODE_CD_ROM.iso / gnu / m4-1.0.3 / symtab.c < prev    next >
Encoding:
C/C++ Source or Header  |  1992-12-19  |  6.6 KB  |  267 lines
  1. /*
  2.  * GNU m4 -- A simple macro processor
  3.  * Copyright (C) 1989-1992 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 2, 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.  * This file handles all the low level work around the symbol table.
  22.  * The symbol table is a simple chained hash table.  Each symbol is
  23.  * described by a struct symbol, which is placed in the hash table based
  24.  * upon the symbol name.  Symbols that hash to the same entry in the
  25.  * table are kept on a list, sorted by name.  As a special case, to
  26.  * facilitate the "pushdef" and "popdef" builtins, a symbol can be
  27.  * several times in the symbol table, one for each definition.  Since
  28.  * the name is the same, all the entries for the symbol will be on the
  29.  * same list, and will also, because the list is sorted, be adjacent.
  30.  * All the entries for a name are simply ordered on the list by age.
  31.  * The current definition will then always be the first found.
  32.  */
  33. #include "m4.h"
  34.  
  35. /*
  36.  * Initialise the symbol table, by allocating the necessary storage, and
  37.  * zeroing all the entries.
  38.  */
  39.  
  40. /* Pointer to symbol table.  */
  41. symbol **symtab;
  42.  
  43. void
  44. symtab_init (void)
  45. {
  46.   int i;
  47.   symbol **s;
  48.  
  49.   s = symtab = (symbol **) xmalloc (hash_table_size * sizeof (symbol *));
  50.  
  51.   for (i = hash_table_size; --i >= 0;)
  52.     *s++ = NULL;
  53. }
  54.  
  55. /* Return a hashvalue for a string, from GNU-emacs.  */
  56. static int
  57. hash (const char *s)
  58. {
  59.   register int val = 0;
  60.  
  61.   register const char *ptr = s;
  62.   register char ch;
  63.  
  64.   while ((ch = *ptr++) != '\0')
  65.     {
  66.       if (ch >= 0140)
  67.     ch -= 40;
  68.       val = ((val << 3) + (val >> 28) + ch);
  69.     };
  70.   val = (val < 0) ? -val : val;
  71.   return val % hash_table_size;
  72. }
  73.  
  74. /*
  75.  * free all storage associated with a symbol.
  76.  */
  77. static void
  78. free_symbol (symbol *sym)
  79. {
  80.   if (SYMBOL_NAME (sym))
  81.     xfree (SYMBOL_NAME (sym));
  82.   if (SYMBOL_TYPE (sym) == TOKEN_TEXT)
  83.     xfree (SYMBOL_TEXT (sym));
  84.   xfree ((char *) sym);
  85. }
  86.  
  87. /*
  88.  * Search in, and manipulation of the symbol table, are all done by
  89.  * lookup_symbol ().  It basically hashes NAME to a list in the symbol
  90.  * table, and searched this list for the first occurence of a symbol
  91.  * with the name.
  92.  *
  93.  * The MODE parameter determines what lookup_symbol () will do.  It can
  94.  * either just do a lookup, do a lookup and insert if not present, do an
  95.  * insertion even if the name is already in the list, delete the first
  96.  * occurrence of the name on the list or delete all occurences of the
  97.  * name on the list.
  98.  */
  99. symbol *
  100. lookup_symbol (const char *name, symbol_lookup mode)
  101. {
  102.   int h, cmp = 1;
  103.   symbol *sym, *prev;
  104.   symbol **spp;
  105.  
  106.   h = hash (name);
  107.   sym = symtab[h];
  108.  
  109.   for (prev = NULL; sym != NULL; prev = sym, sym = sym->next)
  110.     {
  111.       cmp = strcmp (SYMBOL_NAME (sym), name);
  112.       if (cmp >= 0)
  113.     break;
  114.     }
  115.  
  116.   /*
  117.    * If just searching, return status of search.
  118.    */
  119.   if (mode == SYMBOL_LOOKUP)
  120.     return cmp == 0 ? sym : NULL;
  121.  
  122.   /* Symbol not found.  */
  123.  
  124.   spp = (prev != NULL) ?  &prev->next : &symtab[h];
  125.  
  126.   switch (mode)
  127.     {
  128.  
  129.     case SYMBOL_INSERT:
  130.       /*
  131.        * Return the symbol, if the name was found in the table.
  132.        * Otherwise, just insert the name, and return the new symbol.
  133.        */
  134.       if (cmp == 0 && sym != NULL)
  135.     return sym;
  136.       /* Fall through.  */
  137.  
  138.     case SYMBOL_PUSHDEF:
  139.       /*
  140.        * Insert a name in the symbol table.  If there is already a
  141.        * symbol with the name, insert this in front of it, and mark
  142.        * the old symbol as "shadowed".
  143.        */
  144.       sym = (symbol *) xmalloc (sizeof (symbol));
  145.       SYMBOL_TYPE (sym) = TOKEN_VOID;
  146.       SYMBOL_TRACED (sym) = SYMBOL_SHADOWED (sym) = FALSE;
  147.       SYMBOL_NAME (sym) = xstrdup (name);
  148.  
  149.       SYMBOL_NEXT (sym) = *spp;
  150.       (*spp) = sym;
  151.  
  152.       if (mode == SYMBOL_PUSHDEF && cmp == 0)
  153.     {
  154.       SYMBOL_SHADOWED (SYMBOL_NEXT (sym)) = TRUE;
  155.       SYMBOL_TRACED (sym) = SYMBOL_TRACED (SYMBOL_NEXT (sym));
  156.     }
  157.       return sym;
  158.  
  159.     case SYMBOL_DELETE:
  160.       /*
  161.        * Delete all occurences of symbols with NAME.
  162.        */
  163.       if (cmp != 0 || sym == NULL)
  164.     return NULL;
  165.       do
  166.     {
  167.       *spp = SYMBOL_NEXT (sym);
  168.       free_symbol (sym);
  169.       sym = *spp;
  170.     }
  171.       while (sym != NULL && strcmp (name, SYMBOL_NAME (sym)) == 0);
  172.       return NULL;
  173.  
  174.     case SYMBOL_POPDEF:
  175.       /*
  176.        * Delete the first occurence of a symbol with NAME.
  177.        */
  178.       if (cmp != 0 || sym == NULL)
  179.     return NULL;
  180.       if (SYMBOL_NEXT (sym) != NULL && cmp == 0)
  181.     SYMBOL_SHADOWED (SYMBOL_NEXT (sym)) = FALSE;
  182.       *spp = SYMBOL_NEXT (sym);
  183.       free_symbol (sym);
  184.       return NULL;
  185.  
  186.     default:
  187.       internal_error ("Illegal mode to symbol_lookup ()");
  188.       break;
  189.     }
  190.   /* NOTREACHED */
  191. }
  192.  
  193.  
  194. /*
  195.  * The following function are used for the cases, where we want to do
  196.  * something to each and every symbol in the table.  The function
  197.  * hack_all_symbols () traverses the symbol table, and calls a specified
  198.  * function FUNC for each symbol in the table.  FUNC is called with a
  199.  * pointer to the symbol, and the DATA argument.
  200.  */
  201.  
  202. void
  203. hack_all_symbols (hack_symbol *func, char *data)
  204. {
  205.   int h;
  206.   symbol *sym;
  207.  
  208.   for (h = 0; h < HASHMAX; h++)
  209.     {
  210.       for (sym = symtab[h]; sym != NULL; sym = SYMBOL_NEXT (sym))
  211.     (*func) (sym, data);
  212.     }
  213. }
  214.  
  215.  
  216. #ifdef DEBUG_SYM
  217.  
  218. static void
  219. symtab_debug (void)
  220. {
  221.   token_type t;
  222.   token_data td;
  223.   char *text;
  224.   symbol *s;
  225.   int delete;
  226.  
  227.   while ((t = next_token (&td)) != NULL)
  228.     {
  229.       if (t != TOKEN_WORD)
  230.     continue;
  231.       text = TOKEN_DATA_TEXT (&td);
  232.       if (*text == '_')
  233.     {
  234.       delete = 1;
  235.       text++;
  236.     }
  237.       else
  238.     delete = 0;
  239.  
  240.       s = lookup_symbol (text, SYMBOL_LOOKUP);
  241.  
  242.       if (s == NULL)
  243.     printf ("Name `%s' is unknown\n", text);
  244.  
  245.       if (delete)
  246.     (void) lookup_symbol (text, SYMBOL_DELETE);
  247.       else
  248.     (void) lookup_symbol (text, SYMBOL_INSERT);
  249.     }
  250.   hack_all_symbols (dump_symbol);
  251. }
  252.  
  253.  
  254. static void
  255. symtab_print_list (int i)
  256. {
  257.   symbol *sym;
  258.  
  259.   printf ("Symbol dump #d:\n", i);
  260.   for (sym = symtab[i]; sym != NULL; sym = sym->next)
  261.     printf ("\tname %s, addr 0x%x, next 0x%x, flags%s%s\n",
  262.        SYMBOL_NAME (sym), sym, sym->next,
  263.        SYMBOL_TRACED (sym) ? " traced" : "",
  264.        SYMBOL_SHADOWED (sym) ? " shadowed" : "");
  265. }
  266. #endif
  267.