| 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 | }
|
|---|
