home *** CD-ROM | disk | FTP | other *** search
/ Geek Gadgets 1 / ADE-1.bin / ade-dist / m4-1.4-src.tgz / tar.out / fsf / m4 / src / symtab.c < prev    next >
C/C++ Source or Header  |  1996-09-28  |  7KB  |  267 lines
  1. /* GNU m4 -- A simple macro processor
  2.    Copyright (C) 1989, 90, 91, 92, 93, 94 Free Software Foundation, Inc.
  3.   
  4.    This program is free software; you can redistribute it and/or modify
  5.    it under the terms of the GNU General Public License as published by
  6.    the Free Software Foundation; either version 2, or (at your option)
  7.    any later version.
  8.   
  9.    This program is distributed in the hope that it will be useful,
  10.    but WITHOUT ANY WARRANTY; without even the implied warranty of
  11.    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12.    GNU General Public License for more details.
  13.   
  14.    You should have received a copy of the GNU General Public License
  15.    along with this program; if not, write to the Free Software
  16.    Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  17. */
  18.  
  19. /* This file handles all the low level work around the symbol table.  The
  20.    symbol table is a simple chained hash table.  Each symbol is described
  21.    by a struct symbol, which is placed in the hash table based upon the
  22.    symbol name.  Symbols that hash to the same entry in the table are
  23.    kept on a list, sorted by name.  As a special case, to facilitate the
  24.    "pushdef" and "popdef" builtins, a symbol can be several times in the
  25.    symbol table, one for each definition.  Since the name is the same,
  26.    all the entries for the symbol will be on the same list, and will
  27.    also, because the list is sorted, be adjacent.  All the entries for a
  28.    name are simply ordered on the list by age.  The current definition
  29.    will then always be the first found.  */
  30.  
  31. #include "m4.h"
  32.  
  33. /*----------------------------------------------------------------------.
  34. | Initialise the symbol table, by allocating the necessary storage, and |
  35. | zeroing all the entries.                            |
  36. `----------------------------------------------------------------------*/
  37.  
  38. /* Pointer to symbol table.  */
  39. symbol **symtab;
  40.  
  41. void
  42. symtab_init (void)
  43. {
  44.   int i;
  45.   symbol **s;
  46.  
  47.   s = symtab = (symbol **) xmalloc (hash_table_size * sizeof (symbol *));
  48.  
  49.   for (i = hash_table_size; --i >= 0;)
  50.     *s++ = NULL;
  51. }
  52.  
  53. /*--------------------------------------------------.
  54. | Return a hashvalue for a string, from GNU-emacs.  |
  55. `--------------------------------------------------*/
  56.  
  57. static int
  58. hash (const char *s)
  59. {
  60.   register int val = 0;
  61.  
  62.   register const char *ptr = s;
  63.   register char ch;
  64.  
  65.   while ((ch = *ptr++) != '\0')
  66.     {
  67.       if (ch >= 0140)
  68.     ch -= 40;
  69.       val = ((val << 3) + (val >> 28) + ch);
  70.     };
  71.   val = (val < 0) ? -val : val;
  72.   return val % hash_table_size;
  73. }
  74.  
  75. /*--------------------------------------------.
  76. | Free all storage associated with a symbol.  |
  77. `--------------------------------------------*/
  78.  
  79. static void
  80. free_symbol (symbol *sym)
  81. {
  82.   if (SYMBOL_NAME (sym))
  83.     xfree (SYMBOL_NAME (sym));
  84.   if (SYMBOL_TYPE (sym) == TOKEN_TEXT)
  85.     xfree (SYMBOL_TEXT (sym));
  86.   xfree ((voidstar) sym);
  87. }
  88.  
  89. /*------------------------------------------------------------------------.
  90. | Search in, and manipulation of the symbol table, are all done by      |
  91. | lookup_symbol ().  It basically hashes NAME to a list in the symbol      |
  92. | table, and searched this list for the first occurence of a symbol with  |
  93. | the name.                                  |
  94. |                                       |
  95. | The MODE parameter determines what lookup_symbol () will do.  It can      |
  96. | either just do a lookup, do a lookup and insert if not present, do an      |
  97. | insertion even if the name is already in the list, delete the first      |
  98. | occurrence of the name on the list or delete all occurences of the name |
  99. | on the list.                                  |
  100. `------------------------------------------------------------------------*/
  101.  
  102. symbol *
  103. lookup_symbol (const char *name, symbol_lookup mode)
  104. {
  105.   int h, cmp = 1;
  106.   symbol *sym, *prev;
  107.   symbol **spp;
  108.  
  109.   h = hash (name);
  110.   sym = symtab[h];
  111.  
  112.   for (prev = NULL; sym != NULL; prev = sym, sym = sym->next)
  113.     {
  114.       cmp = strcmp (SYMBOL_NAME (sym), name);
  115.       if (cmp >= 0)
  116.     break;
  117.     }
  118.  
  119.   /* If just searching, return status of search.  */
  120.  
  121.   if (mode == SYMBOL_LOOKUP)
  122.     return cmp == 0 ? sym : NULL;
  123.  
  124.   /* Symbol not found.  */
  125.  
  126.   spp = (prev != NULL) ?  &prev->next : &symtab[h];
  127.  
  128.   switch (mode)
  129.     {
  130.  
  131.     case SYMBOL_INSERT:
  132.  
  133.       /* Return the symbol, if the name was found in the table.
  134.      Otherwise, just insert the name, and return the new symbol.  */
  135.  
  136.       if (cmp == 0 && sym != NULL)
  137.     return sym;
  138.       /* Fall through.  */
  139.  
  140.     case SYMBOL_PUSHDEF:
  141.  
  142.       /* Insert a name in the symbol table.  If there is already a symbol
  143.      with the name, insert this in front of it, and mark the old
  144.      symbol as "shadowed".  */
  145.  
  146.       sym = (symbol *) xmalloc (sizeof (symbol));
  147.       SYMBOL_TYPE (sym) = TOKEN_VOID;
  148.       SYMBOL_TRACED (sym) = SYMBOL_SHADOWED (sym) = FALSE;
  149.       SYMBOL_NAME (sym) = xstrdup (name);
  150.  
  151.       SYMBOL_NEXT (sym) = *spp;
  152.       (*spp) = sym;
  153.  
  154.       if (mode == SYMBOL_PUSHDEF && cmp == 0)
  155.     {
  156.       SYMBOL_SHADOWED (SYMBOL_NEXT (sym)) = TRUE;
  157.       SYMBOL_TRACED (sym) = SYMBOL_TRACED (SYMBOL_NEXT (sym));
  158.     }
  159.       return sym;
  160.  
  161.     case SYMBOL_DELETE:
  162.  
  163.       /* Delete all occurences of symbols with NAME.  */
  164.  
  165.       if (cmp != 0 || sym == NULL)
  166.     return NULL;
  167.       do
  168.     {
  169.       *spp = SYMBOL_NEXT (sym);
  170.       free_symbol (sym);
  171.       sym = *spp;
  172.     }
  173.       while (sym != NULL && strcmp (name, SYMBOL_NAME (sym)) == 0);
  174.       return NULL;
  175.  
  176.     case SYMBOL_POPDEF:
  177.  
  178.        /* Delete the first occurence of a symbol with NAME.  */
  179.  
  180.       if (cmp != 0 || sym == NULL)
  181.     return NULL;
  182.       if (SYMBOL_NEXT (sym) != NULL && cmp == 0)
  183.     SYMBOL_SHADOWED (SYMBOL_NEXT (sym)) = FALSE;
  184.       *spp = SYMBOL_NEXT (sym);
  185.       free_symbol (sym);
  186.       return NULL;
  187.  
  188.     default:
  189.       M4ERROR ((warning_status, 0,
  190.         "INTERNAL ERROR: Illegal mode to symbol_lookup ()"));
  191.       abort ();
  192.     }
  193. }
  194.  
  195. /*----------------------------------------------------------------------.
  196. | The following function is used for the cases, where we want to do     |
  197. | something to each and every symbol in the table.  The function        |
  198. | hack_all_symbols () traverses the symbol table, and calls a specified |
  199. | function FUNC for each symbol in the table.  FUNC is called with a    |
  200. | pointer to the symbol, and the DATA argument.                    |
  201. `----------------------------------------------------------------------*/
  202.  
  203. void
  204. hack_all_symbols (hack_symbol *func, const char *data)
  205. {
  206.   int h;
  207.   symbol *sym;
  208.  
  209.   for (h = 0; h < hash_table_size; h++)
  210.     {
  211.       for (sym = symtab[h]; sym != NULL; sym = SYMBOL_NEXT (sym))
  212.     (*func) (sym, data);
  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.   const 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. static void
  254. symtab_print_list (int i)
  255. {
  256.   symbol *sym;
  257.  
  258.   printf ("Symbol dump #d:\n", i);
  259.   for (sym = symtab[i]; sym != NULL; sym = sym->next)
  260.     printf ("\tname %s, addr 0x%x, next 0x%x, flags%s%s\n",
  261.        SYMBOL_NAME (sym), sym, sym->next,
  262.        SYMBOL_TRACED (sym) ? " traced" : "",
  263.        SYMBOL_SHADOWED (sym) ? " shadowed" : "");
  264. }
  265.  
  266. #endif /* DEBUG_SYM */
  267.