chiark - git - mdw - e16/blob - epp/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, 675 Mass Ave, Cambridge, MA 02139, 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 static HASHNODE    *hashtab[HASHSIZE];
  29
  30 #include <string.h>
  31 #include <stdlib.h>
  32
  33 #define IS_IDCHAR(ch) is_idchar[(unsigned char)(ch)]
  34
  35 /*
  36  * return hash function on name.  must be compatible with the one
  37  * computed a step at a time, elsewhere
  38  */
  39 int
  40 hashf(const char *name, int len, int hashsize)
  41 {
  42    int                 r = 0;
  43
  44    while (len--)
  45       r = HASHSTEP(r, *name++);
  46
  47    return MAKE_POS(r) % hashsize;
  48 }
  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(const char *name, int len, int hash)
  62 {
  63    const char         *bp;
  64    HASHNODE           *bucket;
  65
  66    if (len < 0)
  67      {
  68         for (bp = name; IS_IDCHAR(*bp); bp++)
  69            ;
  70         len = bp - name;
  71      }
  72    if (hash < 0)
  73       hash = hashf(name, len, HASHSIZE);
  74
  75    bucket = hashtab[hash];
  76    while (bucket)
  77      {
  78         if (bucket->length == len
  79             && strncmp((const char *)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(HASHNODE * hp)
 102 {
 103
 104    if (hp->prev != NULL)
 105       hp->prev->next = hp->next;
 106    if (hp->next != NULL)
 107       hp->next->prev = hp->prev;
 108
 109    /* make sure that the bucket chain header that
 110     * the deleted guy was on points to the right thing afterwards. */
 111    if (hp == *hp->bucket_hdr)
 112       *hp->bucket_hdr = hp->next;
 113
 114    if (hp->type == T_MACRO)
 115      {
 116         DEFINITION         *d = hp->value.defn;
 117         struct reflist     *ap, *nextap;
 118
 119         for (ap = d->pattern; ap != NULL; ap = nextap)
 120           {
 121              nextap = ap->next;
 122              free(ap);
 123           }
 124         if (d->nargs >= 0)
 125            free(d->args.argnames);
 126         free(d);
 127      }
 128    free(hp);
 129 }
 130 /*
 131  * install a name in the main hash table, even if it is already there.
 132  *   name stops with first non alphanumeric, except leading '#'.
 133  * caller must check against redefinition if that is desired.
 134  * delete_macro () removes things installed by install () in fifo order.
 135  * this is important because of the `defined' special symbol used
 136  * in #if, and also if pushdef/popdef directives are ever implemented.
 137  *
 138  * If LEN is >= 0, it is the length of the name.
 139  * Otherwise, compute the length by scanning the entire name.
 140  *
 141  * If HASH is >= 0, it is the precomputed hash code.
 142  * Otherwise, compute the hash code.
 143  */
 144 HASHNODE           *
 145 install(const char *name, int len, enum node_type type, int ivalue, char *value,
 146         int hash)
 147 {
 148    HASHNODE           *hp;
 149    int                 i, bucket;
 150    const char         *p;
 151
 152    if (len < 0)
 153      {
 154         p = name;
 155         while (IS_IDCHAR(*p))
 156            p++;
 157         len = p - name;
 158      }
 159    if (hash < 0)
 160       hash = hashf(name, len, HASHSIZE);
 161
 162    i = sizeof(HASHNODE) + len + 1;
 163    hp = (HASHNODE *) xmalloc(i);
 164    bucket = hash;
 165    hp->bucket_hdr = &hashtab[bucket];
 166    hp->next = hashtab[bucket];
 167    hashtab[bucket] = hp;
 168    hp->prev = NULL;
 169    if (hp->next != NULL)
 170       hp->next->prev = hp;
 171    hp->type = type;
 172    hp->length = len;
 173    if (hp->type == T_CONST)
 174       hp->value.ival = ivalue;
 175    else
 176       hp->value.cpval = value;
 177    hp->name = ((char *)hp) + sizeof(HASHNODE);
 178    memcpy(hp->name, name, len);
 179    hp->name[len] = 0;
 180    return hp;
 181 }
 182
 183 void
 184 cpp_hash_cleanup(cpp_reader * pfile)
 185 {
 186    int                 i;
 187
 188    pfile = NULL;
 189    for (i = HASHSIZE; --i >= 0;)
 190      {
 191         while (hashtab[i])
 192            delete_macro(hashtab[i]);
 193      }
 194 }