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