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