gcc/cpphash.c

   1 /* Part of CPP library.  (Macro hash table support.)
   2    Copyright (C) 1986, 87, 89, 92, 93, 94, 1995 Free Software Foundation, Inc.
   3    Written by Per Bothner, 1994.
   4    Based on CCCP program by by Paul Rubin, June 1986
   5    Adapted to ANSI C, Richard Stallman, Jan 1987
   6
   7 This program is free software; you can redistribute it and/or modify it
   8 under the terms of the GNU General Public License as published by the
   9 Free Software Foundation; either version 2, or (at your option) any
  10 later version.
  11
  12 This program is distributed in the hope that it will be useful,
  13 but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15 GNU General Public License for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with this program; if not, write to the Free Software
  19 Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
  20
  21  In other words, you are welcome to use, share and improve this program.
  22  You are forbidden to forbid anyone else to use, share and improve
  23  what you give them.   Help stamp out software-hoarding!  */
  24
  25 #include "cpplib.h"
  26 #include "cpphash.h"
  27
  28 extern char *xmalloc PARAMS ((unsigned));
  29
  30 /* Define a generic NULL if one hasn't already been defined.  */
  31
  32 #ifndef NULL
  33 #define NULL 0
  34 #endif
  35
  36 #ifndef __STDC__
  37 #define const
  38 #define volatile
  39 #endif
  40
  41 /*
  42  * return hash function on name.  must be compatible with the one
  43  * computed a step at a time, elsewhere
  44  */
  45 int
  46 hashf (name, len, hashsize)
  47      register const U_CHAR *name;
  48      register int len;
  49      int hashsize;
  50 {
  51   register int r = 0;
  52
  53   while (len--)
  54     r = HASHSTEP (r, *name++);
  55
  56   return MAKE_POS (r) % hashsize;
  57 }
  58
  59 /*
  60  * find the most recent hash node for name name (ending with first
  61  * non-identifier char) installed by install
  62  *
  63  * If LEN is >= 0, it is the length of the name.
  64  * Otherwise, compute the length by scanning the entire name.
  65  *
  66  * If HASH is >= 0, it is the precomputed hash code.
  67  * Otherwise, compute the hash code.
  68  */
  69 HASHNODE *
  70 cpp_lookup (pfile, name, len, hash)
  71      struct parse_file *pfile;
  72      const U_CHAR *name;
  73      int len;
  74      int hash;
  75 {
  76   register const U_CHAR *bp;
  77   register HASHNODE *bucket;
  78
  79   if (len < 0)
  80     {
  81       for (bp = name; is_idchar[*bp]; bp++) ;
  82       len = bp - name;
  83     }
  84
  85   if (hash < 0)
  86     hash = hashf (name, len, HASHSIZE);
  87
  88   bucket = hashtab[hash];
  89   while (bucket) {
  90     if (bucket->length == len && strncmp (bucket->name, name, len) == 0)
  91       return bucket;
  92     bucket = bucket->next;
  93   }
  94   return (HASHNODE*) 0;
  95 }
  96
  97 /*
  98  * Delete a hash node.  Some weirdness to free junk from macros.
  99  * More such weirdness will have to be added if you define more hash
 100  * types that need it.
 101  */
 102
 103 /* Note that the DEFINITION of a macro is removed from the hash table
 104    but its storage is not freed.  This would be a storage leak
 105    except that it is not reasonable to keep undefining and redefining
 106    large numbers of macros many times.
 107    In any case, this is necessary, because a macro can be #undef'd
 108    in the middle of reading the arguments to a call to it.
 109    If #undef freed the DEFINITION, that would crash.  */
 110
 111 void
 112 delete_macro (hp)
 113      HASHNODE *hp;
 114 {
 115
 116   if (hp->prev != NULL)
 117     hp->prev->next = hp->next;
 118   if (hp->next != NULL)
 119     hp->next->prev = hp->prev;
 120
 121   /* make sure that the bucket chain header that
 122      the deleted guy was on points to the right thing afterwards. */
 123   if (hp == *hp->bucket_hdr)
 124     *hp->bucket_hdr = hp->next;
 125
 126   if (hp->type == T_MACRO)
 127     {
 128       DEFINITION *d = hp->value.defn;
 129       struct reflist *ap, *nextap;
 130
 131       for (ap = d->pattern; ap != NULL; ap = nextap)
 132         {
 133           nextap = ap->next;
 134           free (ap);
 135         }
 136       if (d->nargs >= 0)
 137         free (d->args.argnames);
 138       free (d);
 139     }
 140
 141   free (hp);
 142 }
 143 /*
 144  * install a name in the main hash table, even if it is already there.
 145  *   name stops with first non alphanumeric, except leading '#'.
 146  * caller must check against redefinition if that is desired.
 147  * delete_macro () removes things installed by install () in fifo order.
 148  * this is important because of the `defined' special symbol used
 149  * in #if, and also if pushdef/popdef directives are ever implemented.
 150  *
 151  * If LEN is >= 0, it is the length of the name.
 152  * Otherwise, compute the length by scanning the entire name.
 153  *
 154  * If HASH is >= 0, it is the precomputed hash code.
 155  * Otherwise, compute the hash code.
 156  */
 157 HASHNODE *
 158 install (name, len, type, ivalue, value, hash)
 159      U_CHAR *name;
 160      int len;
 161      enum node_type type;
 162      int ivalue;
 163      char *value;
 164      int hash;
 165 {
 166   register HASHNODE *hp;
 167   register int i, bucket;
 168   register U_CHAR *p, *q;
 169
 170   if (len < 0) {
 171     p = name;
 172     while (is_idchar[*p])
 173       p++;
 174     len = p - name;
 175   }
 176
 177   if (hash < 0)
 178     hash = hashf (name, len, HASHSIZE);
 179
 180   i = sizeof (HASHNODE) + len + 1;
 181   hp = (HASHNODE *) xmalloc (i);
 182   bucket = hash;
 183   hp->bucket_hdr = &hashtab[bucket];
 184   hp->next = hashtab[bucket];
 185   hashtab[bucket] = hp;
 186   hp->prev = NULL;
 187   if (hp->next != NULL)
 188     hp->next->prev = hp;
 189   hp->type = type;
 190   hp->length = len;
 191   if (hp->type == T_CONST)
 192     hp->value.ival = ivalue;
 193   else
 194     hp->value.cpval = value;
 195   hp->name = ((U_CHAR *) hp) + sizeof (HASHNODE);
 196   p = hp->name;
 197   q = name;
 198   for (i = 0; i < len; i++)
 199     *p++ = *q++;
 200   hp->name[len] = 0;
 201   return hp;
 202 }
 203
 204 void
 205 cpp_hash_cleanup (pfile)
 206      cpp_reader *pfile;
 207 {
 208   register int i;
 209   for (i = HASHSIZE; --i >= 0; )
 210     {
 211       while (hashtab[i])
 212         delete_macro (hashtab[i]);
 213     }
 214 }