gcc/cpphash.c

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