gcc/cpphash.c

   1 /* Part of CPP library.  (Macro hash table support.)
   2    Copyright (C) 1986, 87, 89, 92-95, 1996 Free Software Foundation, Inc.
   3    Written by Per Bothner, 1994.
   4    Based on CCCP program 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 "config.h"
  26 #include "system.h"
  27 #include "gansidecl.h"
  28 #include "cpplib.h"
  29 #include "cpphash.h"
  30
  31 extern char *xmalloc PARAMS ((unsigned));
  32
  33 /* Return hash function on name.  must be compatible with the one
  34    computed a step at a time, elsewhere  */
  35
  36 int
  37 hashf (name, len, hashsize)
  38      register const U_CHAR *name;
  39      register int len;
  40      int hashsize;
  41 {
  42   register int r = 0;
  43
  44   while (len--)
  45     r = HASHSTEP (r, *name++);
  46
  47   return MAKE_POS (r) % hashsize;
  48 }
  49
  50 /* Find the most recent hash node for name "name" (ending with first
  51    non-identifier char) installed by install
  52
  53    If LEN is >= 0, it is the length of the name.
  54    Otherwise, compute the length by scanning the entire name.
  55
  56    If HASH is >= 0, it is the precomputed hash code.
  57    Otherwise, compute the hash code.  */
  58
  59 HASHNODE *
  60 cpp_lookup (pfile, name, len, hash)
  61      cpp_reader *pfile ATTRIBUTE_UNUSED;
  62      const U_CHAR *name;
  63      int len;
  64      int hash;
  65 {
  66   register const U_CHAR *bp;
  67   register HASHNODE *bucket;
  68
  69   if (len < 0)
  70     {
  71       for (bp = name; is_idchar[*bp]; bp++) ;
  72       len = bp - name;
  73     }
  74
  75   if (hash < 0)
  76     hash = hashf (name, len, HASHSIZE);
  77
  78   bucket = hashtab[hash];
  79   while (bucket) {
  80     if (bucket->length == len && strncmp (bucket->name, name, len) == 0)
  81       return bucket;
  82     bucket = bucket->next;
  83   }
  84   return (HASHNODE *) 0;
  85 }
  86
  87 /*
  88  * Delete a hash node.  Some weirdness to free junk from macros.
  89  * More such weirdness will have to be added if you define more hash
  90  * types that need it.
  91  */
  92
  93 /* Note that the DEFINITION of a macro is removed from the hash table
  94    but its storage is not freed.  This would be a storage leak
  95    except that it is not reasonable to keep undefining and redefining
  96    large numbers of macros many times.
  97    In any case, this is necessary, because a macro can be #undef'd
  98    in the middle of reading the arguments to a call to it.
  99    If #undef freed the DEFINITION, that would crash.  */
 100
 101 void
 102 delete_macro (hp)
 103      HASHNODE *hp;
 104 {
 105
 106   if (hp->prev != NULL)
 107     hp->prev->next = hp->next;
 108   if (hp->next != NULL)
 109     hp->next->prev = hp->prev;
 110
 111   /* make sure that the bucket chain header that
 112      the deleted guy was on points to the right thing afterwards.  */
 113   if (hp == *hp->bucket_hdr)
 114     *hp->bucket_hdr = hp->next;
 115
 116   if (hp->type == T_MACRO)
 117     {
 118       DEFINITION *d = hp->value.defn;
 119       struct reflist *ap, *nextap;
 120
 121       for (ap = d->pattern; ap != NULL; ap = nextap)
 122         {
 123           nextap = ap->next;
 124           free (ap);
 125         }
 126       if (d->nargs >= 0)
 127         free (d->args.argnames);
 128       free (d);
 129     }
 130
 131   free (hp);
 132 }
 133
 134 /* Install a name in the main hash table, even if it is already there.
 135      name stops with first non alphanumeric, except leading '#'.
 136    caller must check against redefinition if that is desired.
 137    delete_macro () removes things installed by install () in fifo order.
 138    this is important because of the `defined' special symbol used
 139    in #if, and also if pushdef/popdef directives are ever implemented.
 140
 141    If LEN is >= 0, it is the length of the name.
 142    Otherwise, compute the length by scanning the entire name.
 143
 144    If HASH is >= 0, it is the precomputed hash code.
 145    Otherwise, compute the hash code.  */
 146
 147 HASHNODE *
 148 install (name, len, type, ivalue, value, hash)
 149      U_CHAR *name;
 150      int len;
 151      enum node_type type;
 152      int ivalue;
 153      char *value;
 154      int hash;
 155 {
 156   register HASHNODE *hp;
 157   register int i, bucket;
 158   register U_CHAR *p, *q;
 159
 160   if (len < 0) {
 161     p = name;
 162     while (is_idchar[*p])
 163       p++;
 164     len = p - name;
 165   }
 166
 167   if (hash < 0)
 168     hash = hashf (name, len, HASHSIZE);
 169
 170   i = sizeof (HASHNODE) + len + 1;
 171   hp = (HASHNODE *) xmalloc (i);
 172   bucket = hash;
 173   hp->bucket_hdr = &hashtab[bucket];
 174   hp->next = hashtab[bucket];
 175   hashtab[bucket] = hp;
 176   hp->prev = NULL;
 177   if (hp->next != NULL)
 178     hp->next->prev = hp;
 179   hp->type = type;
 180   hp->length = len;
 181   if (hp->type == T_CONST)
 182     hp->value.ival = ivalue;
 183   else
 184     hp->value.cpval = value;
 185   hp->name = ((U_CHAR *) hp) + sizeof (HASHNODE);
 186   p = hp->name;
 187   q = name;
 188   for (i = 0; i < len; i++)
 189     *p++ = *q++;
 190   hp->name[len] = 0;
 191   return hp;
 192 }
 193
 194 void
 195 cpp_hash_cleanup (pfile)
 196      cpp_reader *pfile ATTRIBUTE_UNUSED;
 197 {
 198   register int i;
 199   for (i = HASHSIZE; --i >= 0; )
 200     {
 201       while (hashtab[i])
 202         delete_macro (hashtab[i]);
 203     }
 204 }