![[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 / ooptcfront|
Return to table.c CVS log | Up to [Research Unix] / researchv10no / cmd / cfront / ooptcfront |
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 table_delete(char* s, TOK k, int ll ) ! 264: /* ! 265: deletes local class entry from keyword table ! 266: adjusts pointers if multiple entries ! 267: uses same lookup as table::look and table::insert ! 268: */ ! 269: { ! 270: Ptable t = ktbl; ! 271: register char * p; ! 272: register char * q; ! 273: register int i; ! 274: Pname n; ! 275: int rr; ! 276: ! 277: p = s; ! 278: i = 0; ! 279: while (*p) i += (i + *p++); /* i<<1 ^ *p++ better?*/ ! 280: rr = (0<=i) ? i : -i; ! 281: ! 282: // error ('d', "table_delete: %s ll: %d", s, ll ); ! 283: ! 284: Pname* np = t->entries; ! 285: int mx = t->hashsize; ! 286: short* hash = t->hashtbl; ! 287: int firsti = i = rr%mx; ! 288: ! 289: do { ! 290: if (hash[i] == 0) error('i',"table delete: not found: %s", s ); ! 291: n = np[hash[i]]; ! 292: if (n == 0) error('i',"table delete: hashed lookup"); ! 293: p = n->string; /* strcmp(n->n_string,s) */ ! 294: q = s; ! 295: // error( 'd', "table_delete: %s", p ); ! 296: while (*p && *q) ! 297: if (*p++ != *q++) goto nxt; ! 298: if (*p == *q) goto found; ! 299: nxt: ! 300: if (mx <= ++i) i = 0; /* wrap around */ ! 301: } while (i != firsti); ! 302: ! 303: found: ! 304: for (Pname prev = n; n; prev = n, n=n->n_tbl_list){ ! 305: // error( 'd', "table_delete: found: %s %k lex: %d", n->string, n->n_key, n->lex_level ); ! 306: if (n->n_key == k && n->lex_level == ll ) { ! 307: // error( 'd', "table_delete: prev: %d n: %d n->tbl_list: %d", prev, n, n->n_tbl_list); ! 308: if ( prev == n && n->n_tbl_list == 0 ) ! 309: hash[i] = 0; ! 310: else ! 311: prev->n_tbl_list = n->n_tbl_list; ! 312: return; ! 313: } ! 314: } ! 315: } ! 316: ! 317: /* ODI Notes ! 318: ! 319: moved new_key to lex. ! 320: ! 321: */
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.