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