compilers/pcc/pcc-1.0.0/cc/ccom/symtabs.c

   1 /*      $Id: symtabs.c,v 1.19 2011/01/22 22:08:23 ragge Exp $   */
   2 /*
   3  * Copyright (c) 2003 Anders Magnusson (ragge@ludd.luth.se).
   4  * All rights reserved.
   5  *
   6  * Redistribution and use in source and binary forms, with or without
   7  * modification, are permitted provided that the following conditions
   8  * are met:
   9  * 1. Redistributions of source code must retain the above copyright
  10  *    notice, this list of conditions and the following disclaimer.
  11  * 2. Redistributions in binary form must reproduce the above copyright
  12  *    notice, this list of conditions and the following disclaimer in the
  13  *    documentation and/or other materials provided with the distribution.
  14  * 3. The name of the author may not be used to endorse or promote products
  15  *    derived from this software without specific prior written permission
  16  *
  17  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
  18  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  19  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
  20  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
  21  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  22  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  23  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  24  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  25  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
  26  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  27  */
  28
  29
  30 #include "pass1.h"
  31
  32 /*
  33  * These definitions are used in the patricia tree that stores
  34  * the strings.
  35  */
  36 #define LEFT_IS_LEAF            0x80000000
  37 #define RIGHT_IS_LEAF           0x40000000
  38 #define IS_LEFT_LEAF(x)         (((x) & LEFT_IS_LEAF) != 0)
  39 #define IS_RIGHT_LEAF(x)        (((x) & RIGHT_IS_LEAF) != 0)
  40 #define BITNO(x)                ((x) & ~(LEFT_IS_LEAF|RIGHT_IS_LEAF))
  41 #define CHECKBITS               8
  42
  43 struct tree {
  44         int bitno;
  45         struct tree *lr[2];
  46 };
  47
  48 static struct tree *firstname;
  49 int nametabs, namestrlen;
  50 static struct tree *firststr;
  51 int strtabs, strstrlen;
  52 static char *symtab_add(char *key, struct tree **, int *, int *);
  53
  54 #define P_BIT(key, bit) (key[bit >> 3] >> (bit & 7)) & 1
  55 #define getree() permalloc(sizeof(struct tree))
  56
  57 char *
  58 addname(char *key)
  59 {
  60         return symtab_add(key, &firstname, &nametabs, &namestrlen);
  61 }
  62
  63 char *
  64 addstring(char *key)
  65 {
  66         return symtab_add(key, &firststr, &strtabs, &strstrlen);
  67 }
  68
  69 /*
  70  * Add a name to the name stack (if its non-existing),
  71  * return its address.
  72  * This is a simple patricia implementation.
  73  */
  74 char *
  75 symtab_add(char *key, struct tree **first, int *tabs, int *stlen)
  76 {
  77         struct tree *w, *new, *last;
  78         int cix, bit, fbit, svbit, ix, bitno, len;
  79         char *m, *k, *sm;
  80
  81         /* Count full string length */
  82         for (k = key, len = 0; *k; k++, len++)
  83                 ;
  84
  85         switch (*tabs) {
  86         case 0:
  87                 *first = (struct tree *)newstring(key, len);
  88                 *stlen += (len + 1);
  89                 (*tabs)++;
  90                 return (char *)*first;
  91
  92         case 1:
  93                 m = (char *)*first;
  94                 svbit = 0; /* XXX why? */
  95                 break;
  96
  97         default:
  98                 w = *first;
  99                 bitno = len * CHECKBITS;
 100                 for (;;) {
 101                         bit = BITNO(w->bitno);
 102                         fbit = bit > bitno ? 0 : P_BIT(key, bit);
 103                         svbit = fbit ? IS_RIGHT_LEAF(w->bitno) :
 104                             IS_LEFT_LEAF(w->bitno);
 105                         w = w->lr[fbit];
 106                         if (svbit) {
 107                                 m = (char *)w;
 108                                 break;
 109                         }
 110                 }
 111         }
 112
 113         sm = m;
 114         k = key;
 115
 116         /* Check for correct string and return */
 117         for (cix = 0; *m && *k && *m == *k; m++, k++, cix += CHECKBITS)
 118                 ;
 119         if (*m == 0 && *k == 0)
 120                 return sm;
 121
 122         ix = *m ^ *k;
 123         while ((ix & 1) == 0)
 124                 ix >>= 1, cix++;
 125
 126         /* Create new node */
 127         new = getree();
 128         bit = P_BIT(key, cix);
 129         new->bitno = cix | (bit ? RIGHT_IS_LEAF : LEFT_IS_LEAF);
 130         new->lr[bit] = (struct tree *)newstring(key, len);
 131         *stlen += (len + 1);
 132
 133         if ((*tabs)++ == 1) {
 134                 new->lr[!bit] = *first;
 135                 new->bitno |= (bit ? LEFT_IS_LEAF : RIGHT_IS_LEAF);
 136                 *first = new;
 137                 return (char *)new->lr[bit];
 138         }
 139
 140
 141         w = *first;
 142         last = NULL;
 143         for (;;) {
 144                 fbit = w->bitno;
 145                 bitno = BITNO(w->bitno);
 146                 if (bitno == cix)
 147                         cerror("bitno == cix");
 148                 if (bitno > cix)
 149                         break;
 150                 svbit = P_BIT(key, bitno);
 151                 last = w;
 152                 w = w->lr[svbit];
 153                 if (fbit & (svbit ? RIGHT_IS_LEAF : LEFT_IS_LEAF))
 154                         break;
 155         }
 156
 157         new->lr[!bit] = w;
 158         if (last == NULL) {
 159                 *first = new;
 160         } else {
 161                 last->lr[svbit] = new;
 162                 last->bitno &= ~(svbit ? RIGHT_IS_LEAF : LEFT_IS_LEAF);
 163         }
 164         if (bitno < cix)
 165                 new->bitno |= (bit ? LEFT_IS_LEAF : RIGHT_IS_LEAF);
 166         return (char *)new->lr[bit];
 167 }
 168
 169 static struct tree *sympole[NSTYPES];
 170 static struct symtab *tmpsyms[NSTYPES];
 171 int numsyms[NSTYPES];
 172
 173 /*
 174  * Inserts a symbol into the symbol tree.
 175  * Returns a struct symtab.
 176  */
 177 struct symtab *
 178 lookup(char *key, int stype)
 179 {
 180         struct symtab *sym;
 181         struct tree *w, *new, *last;
 182         int cix, bit, fbit, svbit, bitno;
 183         int type, uselvl;
 184         intptr_t ix, match, code = (intptr_t)key;
 185
 186         type = stype & SMASK;
 187         uselvl = (blevel > 0 && type != SSTRING);
 188
 189         /*
 190          * The local symbols are kept in a simple linked list.
 191          * Check this list first.
 192          */
 193         if (blevel > 0)
 194                 for (sym = tmpsyms[type]; sym; sym = sym->snext)
 195                         if (sym->sname == key)
 196                                 return sym;
 197
 198         switch (numsyms[type]) {
 199         case 0:
 200                 if (stype & SNOCREAT)
 201                         return NULL;
 202                 if (uselvl) {
 203                         sym = getsymtab(key, stype|STEMP);
 204                         sym->snext = tmpsyms[type];
 205                         tmpsyms[type] = sym;
 206                         return sym;
 207                 }
 208                 sympole[type] = (struct tree *)getsymtab(key, stype);
 209                 numsyms[type]++;
 210                 return (struct symtab *)sympole[type];
 211
 212         case 1:
 213                 w = (struct tree *)sympole[type];
 214                 svbit = 0; /* XXX why? */
 215                 break;
 216
 217         default:
 218                 w = sympole[type];
 219                 for (;;) {
 220                         bit = BITNO(w->bitno);
 221                         fbit = (code >> bit) & 1;
 222                         svbit = fbit ? IS_RIGHT_LEAF(w->bitno) :
 223                             IS_LEFT_LEAF(w->bitno);
 224                         w = w->lr[fbit];
 225                         if (svbit)
 226                                 break;
 227                 }
 228         }
 229
 230         sym = (struct symtab *)w;
 231         match = (intptr_t)sym->sname;
 232
 233         ix = code ^ match;
 234         if (ix == 0)
 235                 return sym;
 236         else if (stype & SNOCREAT)
 237                 return NULL;
 238
 239 #ifdef PCC_DEBUG
 240         if (ddebug)
 241                 printf("        adding %s as %s at level %d\n",
 242                     key, uselvl ? "temp" : "perm", blevel);
 243 #endif
 244
 245         /*
 246          * Insert into the linked list, if feasible.
 247          */
 248         if (uselvl) {
 249                 sym = getsymtab(key, stype|STEMP);
 250                 sym->snext = tmpsyms[type];
 251                 tmpsyms[type] = sym;
 252                 return sym;
 253         }
 254
 255         /*
 256          * Need a new node. If type is SNORMAL and inside a function
 257          * the node must be allocated as permanent anyway.
 258          * This could be optimized by adding a remove routine, but it
 259          * may be more trouble than it is worth.
 260          */
 261         if (stype == (STEMP|SNORMAL))
 262                 stype = SNORMAL;
 263
 264         for (cix = 0; (ix & 1) == 0; ix >>= 1, cix++)
 265                 ;
 266
 267         new = stype & STEMP ? tmpalloc(sizeof(struct tree)) :
 268             permalloc(sizeof(struct tree));
 269         bit = (code >> cix) & 1;
 270         new->bitno = cix | (bit ? RIGHT_IS_LEAF : LEFT_IS_LEAF);
 271         new->lr[bit] = (struct tree *)getsymtab(key, stype);
 272         if (numsyms[type]++ == 1) {
 273                 new->lr[!bit] = sympole[type];
 274                 new->bitno |= (bit ? LEFT_IS_LEAF : RIGHT_IS_LEAF);
 275                 sympole[type] = new;
 276                 return (struct symtab *)new->lr[bit];
 277         }
 278
 279
 280         w = sympole[type];
 281         last = NULL;
 282         for (;;) {
 283                 fbit = w->bitno;
 284                 bitno = BITNO(w->bitno);
 285                 if (bitno == cix)
 286                         cerror("bitno == cix");
 287                 if (bitno > cix)
 288                         break;
 289                 svbit = (code >> bitno) & 1;
 290                 last = w;
 291                 w = w->lr[svbit];
 292                 if (fbit & (svbit ? RIGHT_IS_LEAF : LEFT_IS_LEAF))
 293                         break;
 294         }
 295
 296         new->lr[!bit] = w;
 297         if (last == NULL) {
 298                 sympole[type] = new;
 299         } else {
 300                 last->lr[svbit] = new;
 301                 last->bitno &= ~(svbit ? RIGHT_IS_LEAF : LEFT_IS_LEAF);
 302         }
 303         if (bitno < cix)
 304                 new->bitno |= (bit ? LEFT_IS_LEAF : RIGHT_IS_LEAF);
 305         return (struct symtab *)new->lr[bit];
 306 }
 307
 308 void
 309 symclear(int level)
 310 {
 311         struct symtab *s;
 312         int i;
 313
 314 #ifdef PCC_DEBUG
 315         if (ddebug)
 316                 printf("symclear(%d)\n", level);
 317 #endif
 318         if (level < 1) {
 319                 for (i = 0; i < NSTYPES; i++) {
 320                         s = tmpsyms[i];
 321                         tmpsyms[i] = 0;
 322                         if (i != SLBLNAME)
 323                                 continue;
 324                         while (s != NULL) {
 325                                 if (s->soffset < 0)
 326                                         uerror("label '%s' undefined",s->sname);
 327                                 s = s->snext;
 328                         }
 329                 }
 330         } else {
 331                 for (i = 0; i < NSTYPES; i++) {
 332                         if (i == SLBLNAME)
 333                                 continue; /* function scope */
 334                         while (tmpsyms[i] != NULL &&
 335                             tmpsyms[i]->slevel > level) {
 336                                 tmpsyms[i] = tmpsyms[i]->snext;
 337                         }
 338                 }
 339         }
 340 }
 341
 342 struct symtab *
 343 hide(struct symtab *sym)
 344 {
 345         struct symtab *new;
 346         int typ = sym->sflags & SMASK;
 347
 348         new = getsymtab(sym->sname, typ|STEMP);
 349         new->snext = tmpsyms[typ];
 350         tmpsyms[typ] = new;
 351
 352         warner(Wshadow, sym->sname, sym->slevel ? "local" : "global");
 353
 354 #ifdef PCC_DEBUG
 355         if (ddebug)
 356                 printf("\t%s hidden at level %d (%p -> %p)\n",
 357                     sym->sname, blevel, sym, new);
 358 #endif
 359         return new;
 360 }