![[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 / ocfront|
Return to table.c CVS log | Up to [Research Unix] / researchv10no / cmd / cfront / ocfront |
1.1 ! root 1: /*ident "@(#)ctrans:src/table.c 1.1.1.6" */ ! 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: DB(if(Adebug>=1)fprintf(stderr,"\n*** table::table(%d,%x,%s)\n",sz,nx,n?n->string:"???"); ! 48: node::allocated=1; ! 49: { extern long node_id; node::id = ++node_id; } ! 50: ); ! 51: } ! 52: ! 53: ! 54: Pname table::look(char* s, TOK k) ! 55: /* ! 56: look for "s" in table, ignore entries which are not of "k" type ! 57: look and insert MUST be the same lookup algorithm ! 58: */ ! 59: { ! 60: Ptable t; ! 61: register char * p; ! 62: register char * q; ! 63: register int i; ! 64: Pname n; ! 65: int rr; ! 66: ! 67: // if (s == 0) error('i',"%d->look(0)",this); ! 68: // if (this == 0) error('i',"0->look(%s)",s); ! 69: // if (base != TABLE) error('i',"(%d,%d)->look(%s)",this,base,s); ! 70: ! 71: /* use simple hashing with linear search for overflow */ ! 72: ! 73: p = s; ! 74: i = 0; ! 75: while (*p) i += (i + *p++); /* i<<1 ^ *p++ better?*/ ! 76: rr = (0<=i) ? i : -i; ! 77: ! 78: for (t=this; t; t=t->next) { ! 79: /* in this and all enclosing scopes look for name "s" */ ! 80: Pname* np = t->entries; ! 81: int mx = t->hashsize; ! 82: short* hash = t->hashtbl; ! 83: int firsti = i = rr%mx; ! 84: ! 85: do { ! 86: if (hash[i] == 0) goto not_found; ! 87: n = np[hash[i]]; ! 88: if (n == 0) error('i',"hashed lookup"); ! 89: p = n->string; /* strcmp(n->n_string,s) */ ! 90: q = s; ! 91: while (*p && *q) ! 92: if (*p++ != *q++) goto nxt; ! 93: if (*p == *q) goto found; ! 94: nxt: ! 95: if (mx <= ++i) i = 0; /* wrap around */ ! 96: } while (i != firsti); ! 97: ! 98: found: ! 99: for (; n; n=n->n_tbl_list){ /* for all name "s"s look for a key match */ ! 100: if (n->n_key == k) return n; ! 101: } ! 102: ! 103: not_found:; ! 104: } ! 105: ! 106: return 0; /* not found && no enclosing scope */ ! 107: } ! 108: ! 109: bit Nold; /* non-zero if last insert() failed */ ! 110: ! 111: Pname table::insert(Pname nx, TOK k) ! 112: /* ! 113: the lookup algorithm MUST be the same as look ! 114: if nx is found return the older entry otherwise a copy of nx; ! 115: Nold = (nx found) ? 1 : 0; ! 116: */ ! 117: { ! 118: register char * p; ! 119: register int i; ! 120: Pname n; ! 121: Pname* np = entries; ! 122: Pname* link; ! 123: int firsti; ! 124: int mx = hashsize; ! 125: short* hash = hashtbl; ! 126: char* s = nx->string; ! 127: ! 128: if (s==0) error('i',"%p->insert(0,%k)",this,k); ! 129: nx->n_key = k; ! 130: if (nx->n_tbl_list || nx->n_table) error('i',"%n in two tables",nx); ! 131: /* use simple hashing with linear search for overflow */ ! 132: ! 133: p = s; ! 134: i = 0; ! 135: while (*p) i += (i + *p++); ! 136: if (i<0) i = -i; ! 137: firsti = i = i%mx; ! 138: ! 139: do { /* look for name "s" */ ! 140: if (hash[i] == 0) { ! 141: hash[i] = free_slot; ! 142: goto add_np; ! 143: } ! 144: n = np[hash[i]]; ! 145: if (n == 0) error('i',"hashed lookup"); ! 146: if (strcmp(n->string,s) == 0) goto found; ! 147: /* ! 148: p = n->string; ! 149: q = s; ! 150: while (*p && *q) if (*p++ != *q++) goto nxt; ! 151: if (*p == *q) goto found; ! 152: nxt: ! 153: */ ! 154: if (mx <= ++i) i = 0; /* wrap around */ ! 155: } while (i != firsti); ! 156: ! 157: error("N table full"); ! 158: ! 159: found: ! 160: ! 161: ! 162: for(;;) { ! 163: if ( k!=NESTED && n->n_key==k) { Nold = 1; return n; } ! 164: ! 165: if (n->n_tbl_list) ! 166: n = n->n_tbl_list; ! 167: else { ! 168: link = &(n->n_tbl_list); ! 169: goto re_allocate; ! 170: } ! 171: } ! 172: ! 173: add_np: ! 174: if (size <= free_slot) { ! 175: grow(2*size); ! 176: return insert(nx,k); ! 177: } ! 178: ! 179: link = &(np[free_slot++]); ! 180: ! 181: re_allocate: ! 182: { ! 183: Pname nw = new name; ! 184: *nw = *nx; ! 185: char* ps = new char[strlen(s)+1]; // copy string to safer store ! 186: strcpy(ps,s); ! 187: // Nstr++; ! 188: nw->string = ps; ! 189: nw->n_table = this; ! 190: *link = nw; ! 191: Nold = 0; ! 192: // Nname++; ! 193: return nw; ! 194: } ! 195: } ! 196: ! 197: void table::grow(int g) ! 198: { ! 199: short* hash; ! 200: register int j; ! 201: int mx; ! 202: register Pname* np; ! 203: Pname n; ! 204: ! 205: if (g <= free_slot) error('i',"table.grow(%d,%d)",g,free_slot); ! 206: if (g <= size) return; ! 207: //error('d',"grow %d %s %d->%d", this, (t_name)?t_name->string:"?", size, g+1); ! 208: size = mx = g+1; ! 209: ! 210: np = new Pname[mx]; ! 211: for (j=0; j<free_slot; j++) np[j] = entries[j]; ! 212: delete entries; ! 213: entries = np; ! 214: ! 215: delete hashtbl; ! 216: hashsize = mx = (g*3)/2; ! 217: hash = hashtbl = new short[mx]; ! 218: ! 219: for (j=1; j<free_slot; j++) { /* rehash(np[j]); */ ! 220: char * s = np[j]->string; ! 221: register char * p; ! 222: char * q; ! 223: register int i; ! 224: int firsti; ! 225: ! 226: p = s; ! 227: i = 0; ! 228: while (*p) i += (i + *p++); ! 229: if (i<0) i = -i; ! 230: firsti = i = i%mx; ! 231: ! 232: do { /* look for name "s" */ ! 233: if (hash[i] == 0) { ! 234: hash[i] = j; ! 235: goto add_np; ! 236: } ! 237: n = np[hash[i]]; ! 238: if (n == 0) error('i',"hashed lookup"); ! 239: p = n->string; /* strcmp(n->n_string,s) */ ! 240: q = s; ! 241: while (*p && *q) if (*p++ != *q++) goto nxt; ! 242: if (*p == *q) goto found; ! 243: nxt: ! 244: if (mx <= ++i) i = 0; /* wrap around */ ! 245: } while (i != firsti); ! 246: ! 247: error('i',"rehash??"); ! 248: ! 249: found: ! 250: error('i',"rehash failed"); ! 251: ! 252: add_np:; ! 253: } ! 254: } ! 255: ! 256: Pname table::get_mem(int i) ! 257: /* ! 258: return a pointer to the i'th entry, or 0 if it does not exist ! 259: */ ! 260: { ! 261: return (i<=0 || free_slot<=i) ? 0 : entries[i]; ! 262: } ! 263: ! 264: void new_key(char* s, TOK toknum, TOK yyclass) ! 265: /* ! 266: make "s" a new keyword with the representation (token) "toknum" ! 267: "yyclass" is the yacc token (for example new_key("int",INT,TYPE); ) ! 268: "yyclass==0" means yyclass=toknum; ! 269: */ ! 270: { ! 271: Pname n = new name(s); ! 272: Pname nn = ktbl->insert(n,0); ! 273: // if (Nold) error('i',"keyword %sD twice",s); ! 274: nn->base = toknum; ! 275: nn->syn_class = (yyclass) ? yyclass : toknum; ! 276: keys[(toknum==LOC)?yyclass:toknum] = s; ! 277: delete n; ! 278: } ! 279: ! 280: void table_delete(char* s, TOK k, int ll ) ! 281: /* ! 282: deletes local class entry from keyword table ! 283: adjusts pointers if multiple entries ! 284: uses same lookup as table::look and table::insert ! 285: */ ! 286: { ! 287: Ptable t = ktbl; ! 288: register char * p; ! 289: register char * q; ! 290: register int i; ! 291: Pname n; ! 292: int rr; ! 293: ! 294: p = s; ! 295: i = 0; ! 296: while (*p) i += (i + *p++); /* i<<1 ^ *p++ better?*/ ! 297: rr = (0<=i) ? i : -i; ! 298: ! 299: // error ('d', "table_delete: %s ll: %d", s, ll ); ! 300: ! 301: Pname* np = t->entries; ! 302: int mx = t->hashsize; ! 303: short* hash = t->hashtbl; ! 304: int firsti = i = rr%mx; ! 305: ! 306: do { ! 307: if (hash[i] == 0) error('i',"table delete: not found: %s", s ); ! 308: n = np[hash[i]]; ! 309: if (n == 0) error('i',"table delete: hashed lookup"); ! 310: p = n->string; /* strcmp(n->n_string,s) */ ! 311: q = s; ! 312: // error( 'd', "table_delete: %s", p ); ! 313: while (*p && *q) ! 314: if (*p++ != *q++) goto nxt; ! 315: if (*p == *q) goto found; ! 316: nxt: ! 317: if (mx <= ++i) i = 0; /* wrap around */ ! 318: } while (i != firsti); ! 319: ! 320: found: ! 321: for (Pname prev = n; n; prev = n, n=n->n_tbl_list){ ! 322: // error( 'd', "table_delete: found: %s %k lex: %d", n->string, n->n_key, n->lex_level ); ! 323: if (n->n_key == k && n->lex_level == ll ) { ! 324: // error( 'd', "table_delete: prev: %d n: %d n->tbl_list: %d", prev, n, n->n_tbl_list); ! 325: if ( prev == n && n->n_tbl_list == 0 ) ! 326: hash[i] = 0; ! 327: else ! 328: prev->n_tbl_list = n->n_tbl_list; ! 329: return; ! 330: } ! 331: } ! 332: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.