![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to table.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [Research Unix] / researchv10no / cmd / cfront / cfront2.00|
Return to table.c CVS log | Up to [Research Unix] / researchv10no / cmd / cfront / cfront2.00 |
1.1 ! root 1: /*ident "@(#)ctrans:src/table.c 1.1.1.4" */ ! 2: /************************************************************************** ! 3: ! 4: C++ source for cfront, the C++ compiler front-end ! 5: written in the computer science research center of Bell Labs ! 6: ! 7: Copyright (c) 1984 AT&T, Inc. All Rights Reserved ! 8: THIS IS UNPUBLISHED PROPRIETARY SOURCE CODE OF AT&T, INC. ! 9: ! 10: table.c: ! 11: ! 12: *****************************************************************************/ ! 13: ! 14: #include "cfront.h" ! 15: ! 16: char* keys[MAXTOK+1]; ! 17: /* ! 18: keys[] holds the external form for tokens with fixed representation ! 19: illegal tokens and those with variable representation have 0 entries ! 20: */ ! 21: ! 22: /* ! 23: the class table functions assume that new initializes store to 0 ! 24: */ ! 25: ! 26: table::table(short sz, Ptable nx, Pname n) ! 27: /* ! 28: create a symbol table with "size" entries ! 29: the scope of table is enclosed in the scope of "nx" ! 30: ! 31: both the vector of class name pointers and the hash table ! 32: are initialized containing all zeroes ! 33: ! 34: to simplify hashed lookup entries[0] is never used ! 35: so the size of "entries" must be "size+1" to hold "size" entries ! 36: */ ! 37: { ! 38: base = TABLE; ! 39: t_name = n; ! 40: size = sz = (sz<=0) ? 2 : sz+1; ! 41: //fprintf(stderr,"table::table %d %s %d (%d %d)\n", this, (n)?n->string:"?", sz,(sz*3)/2); ! 42: entries = new Pname[sz]; ! 43: hashsize = sz = (sz*3)/2; ! 44: hashtbl = new short[sz]; ! 45: next = nx; ! 46: free_slot = 1; ! 47: } ! 48: ! 49: ! 50: Pname table::look(char* s, TOK k) ! 51: /* ! 52: look for "s" in table, ignore entries which are not of "k" type ! 53: look and insert MUST be the same lookup algorithm ! 54: */ ! 55: { ! 56: Ptable t; ! 57: register char * p; ! 58: register char * q; ! 59: register int i; ! 60: Pname n; ! 61: int rr; ! 62: ! 63: // if (s == 0) error('i',"%d->look(0)",this); ! 64: // if (this == 0) error('i',"0->look(%s)",s); ! 65: // if (base != TABLE) error('i',"(%d,%d)->look(%s)",this,base,s); ! 66: ! 67: /* use simple hashing with linear search for overflow */ ! 68: ! 69: p = s; ! 70: i = 0; ! 71: while (*p) i += (i + *p++); /* i<<1 ^ *p++ better?*/ ! 72: rr = (0<=i) ? i : -i; ! 73: ! 74: for (t=this; t; t=t->next) { ! 75: /* in this and all enclosing scopes look for name "s" */ ! 76: Pname* np = t->entries; ! 77: int mx = t->hashsize; ! 78: short* hash = t->hashtbl; ! 79: int firsti = i = rr%mx; ! 80: ! 81: do { ! 82: if (hash[i] == 0) goto not_found; ! 83: n = np[hash[i]]; ! 84: if (n == 0) error('i',"hashed lookup"); ! 85: p = n->string; /* strcmp(n->n_string,s) */ ! 86: q = s; ! 87: while (*p && *q) ! 88: if (*p++ != *q++) goto nxt; ! 89: if (*p == *q) goto found; ! 90: nxt: ! 91: if (mx <= ++i) i = 0; /* wrap around */ ! 92: } while (i != firsti); ! 93: ! 94: found: ! 95: for (; n; n=n->n_tbl_list){ /* for all name "s"s look for a key match */ ! 96: if (n->n_key == k) return n; ! 97: } ! 98: ! 99: not_found:; ! 100: } ! 101: ! 102: return 0; /* not found && no enclosing scope */ ! 103: } ! 104: ! 105: bit Nold; /* non-zero if last insert() failed */ ! 106: ! 107: Pname table::insert(Pname nx, TOK k) ! 108: /* ! 109: the lookup algorithm MUST be the same as look ! 110: if nx is found return the older entry otherwise a copy of nx; ! 111: Nold = (nx found) ? 1 : 0; ! 112: */ ! 113: { ! 114: register char * p; ! 115: register int i; ! 116: Pname n; ! 117: Pname* np = entries; ! 118: Pname* link; ! 119: int firsti; ! 120: int mx = hashsize; ! 121: short* hash = hashtbl; ! 122: char* s = nx->string; ! 123: ! 124: if (s==0) error('i',"%p->insert(0,%k)",this,k); ! 125: nx->n_key = k; ! 126: if (nx->n_tbl_list || nx->n_table) error('i',"%n in two tables",nx); ! 127: /* use simple hashing with linear search for overflow */ ! 128: ! 129: p = s; ! 130: i = 0; ! 131: while (*p) i += (i + *p++); ! 132: if (i<0) i = -i; ! 133: firsti = i = i%mx; ! 134: ! 135: do { /* look for name "s" */ ! 136: if (hash[i] == 0) { ! 137: hash[i] = free_slot; ! 138: goto add_np; ! 139: } ! 140: n = np[hash[i]]; ! 141: if (n == 0) error('i',"hashed lookup"); ! 142: if (strcmp(n->string,s) == 0) goto found; ! 143: /* ! 144: p = n->string; ! 145: q = s; ! 146: while (*p && *q) if (*p++ != *q++) goto nxt; ! 147: if (*p == *q) goto found; ! 148: nxt: ! 149: */ ! 150: if (mx <= ++i) i = 0; /* wrap around */ ! 151: } while (i != firsti); ! 152: ! 153: error("N table full"); ! 154: ! 155: found: ! 156: ! 157: ! 158: for(;;) { ! 159: if (n->n_key == k) { Nold = 1; return n; } ! 160: ! 161: if (n->n_tbl_list) ! 162: n = n->n_tbl_list; ! 163: else { ! 164: link = &(n->n_tbl_list); ! 165: goto re_allocate; ! 166: } ! 167: } ! 168: ! 169: add_np: ! 170: if (size <= free_slot) { ! 171: grow(2*size); ! 172: return insert(nx,k); ! 173: } ! 174: ! 175: link = &(np[free_slot++]); ! 176: ! 177: re_allocate: ! 178: { ! 179: Pname nw = new name; ! 180: *nw = *nx; ! 181: char* ps = new char[strlen(s)+1]; // copy string to safer store ! 182: strcpy(ps,s); ! 183: // Nstr++; ! 184: nw->string = ps; ! 185: nw->n_table = this; ! 186: *link = nw; ! 187: Nold = 0; ! 188: // Nname++; ! 189: return nw; ! 190: } ! 191: } ! 192: ! 193: void table::grow(int g) ! 194: { ! 195: short* hash; ! 196: register int j; ! 197: int mx; ! 198: register Pname* np; ! 199: Pname n; ! 200: ! 201: if (g <= free_slot) error('i',"table.grow(%d,%d)",g,free_slot); ! 202: if (g <= size) return; ! 203: //error('d',"grow %d %s %d->%d", this, (t_name)?t_name->string:"?", size, g+1); ! 204: size = mx = g+1; ! 205: ! 206: np = new Pname[mx]; ! 207: for (j=0; j<free_slot; j++) np[j] = entries[j]; ! 208: delete entries; ! 209: entries = np; ! 210: ! 211: delete hashtbl; ! 212: hashsize = mx = (g*3)/2; ! 213: hash = hashtbl = new short[mx]; ! 214: ! 215: for (j=1; j<free_slot; j++) { /* rehash(np[j]); */ ! 216: char * s = np[j]->string; ! 217: register char * p; ! 218: char * q; ! 219: register int i; ! 220: int firsti; ! 221: ! 222: p = s; ! 223: i = 0; ! 224: while (*p) i += (i + *p++); ! 225: if (i<0) i = -i; ! 226: firsti = i = i%mx; ! 227: ! 228: do { /* look for name "s" */ ! 229: if (hash[i] == 0) { ! 230: hash[i] = j; ! 231: goto add_np; ! 232: } ! 233: n = np[hash[i]]; ! 234: if (n == 0) error('i',"hashed lookup"); ! 235: p = n->string; /* strcmp(n->n_string,s) */ ! 236: q = s; ! 237: while (*p && *q) if (*p++ != *q++) goto nxt; ! 238: if (*p == *q) goto found; ! 239: nxt: ! 240: if (mx <= ++i) i = 0; /* wrap around */ ! 241: } while (i != firsti); ! 242: ! 243: error('i',"rehash??"); ! 244: ! 245: found: ! 246: error('i',"rehash failed"); ! 247: ! 248: add_np:; ! 249: } ! 250: } ! 251: ! 252: Pclass Ebase; ! 253: Pclass Epriv; /* extra return values from lookc() */ ! 254: ! 255: Pname table::get_mem(int i) ! 256: /* ! 257: return a pointer to the i'th entry, or 0 if it does not exist ! 258: */ ! 259: { ! 260: return (i<=0 || free_slot<=i) ? 0 : entries[i]; ! 261: } ! 262: ! 263: void new_key(char* s, TOK toknum, TOK yyclass) ! 264: /* ! 265: make "s" a new keyword with the representation (token) "toknum" ! 266: "yyclass" is the yacc token (for example new_key("int",INT,TYPE); ) ! 267: "yyclass==0" means yyclass=toknum; ! 268: */ ! 269: { ! 270: Pname n = new name(s); ! 271: Pname nn = ktbl->insert(n,0); ! 272: // if (Nold) error('i',"keyword %sD twice",s); ! 273: nn->base = toknum; ! 274: nn->syn_class = (yyclass) ? yyclass : toknum; ! 275: keys[(toknum==LOC)?yyclass:toknum] = s; ! 276: delete n; ! 277: } ! 278: ! 279: void table_delete(char* s, TOK k, int ll ) ! 280: /* ! 281: deletes local class entry from keyword table ! 282: adjusts pointers if multiple entries ! 283: uses same lookup as table::look and table::insert ! 284: */ ! 285: { ! 286: Ptable t = ktbl; ! 287: register char * p; ! 288: register char * q; ! 289: register int i; ! 290: Pname n; ! 291: int rr; ! 292: ! 293: p = s; ! 294: i = 0; ! 295: while (*p) i += (i + *p++); /* i<<1 ^ *p++ better?*/ ! 296: rr = (0<=i) ? i : -i; ! 297: ! 298: // error ('d', "table_delete: %s ll: %d", s, ll ); ! 299: ! 300: Pname* np = t->entries; ! 301: int mx = t->hashsize; ! 302: short* hash = t->hashtbl; ! 303: int firsti = i = rr%mx; ! 304: ! 305: do { ! 306: if (hash[i] == 0) error('i',"table delete: not found: %s", s ); ! 307: n = np[hash[i]]; ! 308: if (n == 0) error('i',"table delete: hashed lookup"); ! 309: p = n->string; /* strcmp(n->n_string,s) */ ! 310: q = s; ! 311: // error( 'd', "table_delete: %s", p ); ! 312: while (*p && *q) ! 313: if (*p++ != *q++) goto nxt; ! 314: if (*p == *q) goto found; ! 315: nxt: ! 316: if (mx <= ++i) i = 0; /* wrap around */ ! 317: } while (i != firsti); ! 318: ! 319: found: ! 320: for (Pname prev = n; n; prev = n, n=n->n_tbl_list){ ! 321: // error( 'd', "table_delete: found: %s %k lex: %d", n->string, n->n_key, n->lex_level ); ! 322: if (n->n_key == k && n->lex_level == ll ) { ! 323: // error( 'd', "table_delete: prev: %d n: %d n->tbl_list: %d", prev, n, n->n_tbl_list); ! 324: if ( prev == n && n->n_tbl_list == 0 ) ! 325: hash[i] = 0; ! 326: else ! 327: prev->n_tbl_list = n->n_tbl_list; ! 328: return; ! 329: } ! 330: } ! 331: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.