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