![[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 / xptcfront|
Return to table.c CVS log | Up to [Research Unix] / researchv10no / cmd / cfront / xptcfront |
1.1 ! root 1: /*ident "@(#)ctrans:src/table.c 1.3" */ ! 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: nx->n_key = k; ! 131: if (nx->n_tbl_list || nx->n_table) error('i',"%n in two tables",nx); ! 132: /* use simple hashing with linear search for overflow */ ! 133: ! 134: p = s; ! 135: i = 0; ! 136: while (*p) i += (i + *p++); ! 137: if (i<0) i = -i; ! 138: firsti = i = i%mx; ! 139: ! 140: do { /* look for name "s" */ ! 141: if (hash[i] == 0) { ! 142: hash[i] = free_slot; ! 143: goto add_np; ! 144: } ! 145: n = np[hash[i]]; ! 146: if (n == 0) error('i',"hashed lookup"); ! 147: if (strcmp(n->string,s) == 0) goto found; ! 148: /* ! 149: p = n->string; ! 150: q = s; ! 151: while (*p && *q) if (*p++ != *q++) goto nxt; ! 152: if (*p == *q) goto found; ! 153: nxt: ! 154: */ ! 155: if (mx <= ++i) i = 0; /* wrap around */ ! 156: } while (i != firsti); ! 157: ! 158: error("N table full"); ! 159: ! 160: found: ! 161: ! 162: ! 163: for(;;) { ! 164: if ( k!=NESTED && n->n_key==k) { Nold = 1; return n; } ! 165: ! 166: if (n->n_tbl_list) ! 167: n = n->n_tbl_list; ! 168: else { ! 169: link = &(n->n_tbl_list); ! 170: goto re_allocate; ! 171: } ! 172: } ! 173: ! 174: add_np: ! 175: if (size <= free_slot) { ! 176: grow(2*size); ! 177: return insert(nx,k); ! 178: } ! 179: ! 180: link = &(np[free_slot++]); ! 181: ! 182: re_allocate: ! 183: { ! 184: Pname nw = new name; ! 185: *nw = *nx; ! 186: char* ps = new char[strlen(s)+1]; // copy string to safer store ! 187: strcpy(ps,s); ! 188: // Nstr++; ! 189: nw->string = ps; ! 190: nw->n_table = this; ! 191: *link = nw; ! 192: Nold = 0; ! 193: // Nname++; ! 194: return nw; ! 195: } ! 196: } ! 197: ! 198: void table::grow(int g) ! 199: { ! 200: short* hash; ! 201: register int j; ! 202: int mx; ! 203: register Pname* np; ! 204: Pname n; ! 205: ! 206: if (g <= free_slot) error('i',"table.grow(%d,%d)",g,free_slot); ! 207: if (g <= size) return; ! 208: //error('d',"grow %d %s %d->%d", this, (t_name)?t_name->string:"?", size, g+1); ! 209: size = mx = g+1; ! 210: ! 211: np = new Pname[mx]; ! 212: for (j=0; j<free_slot; j++) np[j] = entries[j]; ! 213: delete entries; ! 214: entries = np; ! 215: ! 216: delete hashtbl; ! 217: hashsize = mx = (g*3)/2; ! 218: hash = hashtbl = new short[mx]; ! 219: ! 220: for (j=1; j<free_slot; j++) { /* rehash(np[j]); */ ! 221: char * s = np[j]->string; ! 222: register char * p; ! 223: char * q; ! 224: register int i; ! 225: int firsti; ! 226: ! 227: p = s; ! 228: i = 0; ! 229: while (*p) i += (i + *p++); ! 230: if (i<0) i = -i; ! 231: firsti = i = i%mx; ! 232: ! 233: do { /* look for name "s" */ ! 234: if (hash[i] == 0) { ! 235: hash[i] = j; ! 236: goto add_np; ! 237: } ! 238: n = np[hash[i]]; ! 239: if (n == 0) error('i',"hashed lookup"); ! 240: p = n->string; /* strcmp(n->n_string,s) */ ! 241: q = s; ! 242: while (*p && *q) if (*p++ != *q++) goto nxt; ! 243: if (*p == *q) goto found; ! 244: nxt: ! 245: if (mx <= ++i) i = 0; /* wrap around */ ! 246: } while (i != firsti); ! 247: ! 248: error('i',"rehash??"); ! 249: ! 250: found: ! 251: error('i',"rehash failed"); ! 252: ! 253: add_np:; ! 254: } ! 255: } ! 256: ! 257: Pname table::get_mem(int i) ! 258: /* ! 259: return a pointer to the i'th entry, or 0 if it does not exist ! 260: */ ! 261: { ! 262: return (i<=0 || free_slot<=i) ? 0 : entries[i]; ! 263: } ! 264: ! 265: void table_delete(char* s, TOK k, int ll ) ! 266: /* ! 267: deletes local class entry from keyword table ! 268: adjusts pointers if multiple entries ! 269: uses same lookup as table::look and table::insert ! 270: */ ! 271: { ! 272: Ptable t = ktbl; ! 273: register char * p; ! 274: register char * q; ! 275: register int i; ! 276: Pname n; ! 277: int rr; ! 278: ! 279: p = s; ! 280: i = 0; ! 281: while (*p) i += (i + *p++); /* i<<1 ^ *p++ better?*/ ! 282: rr = (0<=i) ? i : -i; ! 283: ! 284: // error ('d', "table_delete: %s ll: %d", s, ll ); ! 285: ! 286: Pname* np = t->entries; ! 287: int mx = t->hashsize; ! 288: short* hash = t->hashtbl; ! 289: int firsti = i = rr%mx; ! 290: ! 291: do { ! 292: if (hash[i] == 0) error('i',"table delete: not found: %s", s ); ! 293: n = np[hash[i]]; ! 294: if (n == 0) error('i',"table delete: hashed lookup"); ! 295: p = n->string; /* strcmp(n->n_string,s) */ ! 296: q = s; ! 297: // error( 'd', "table_delete: %s", p ); ! 298: while (*p && *q) ! 299: if (*p++ != *q++) goto nxt; ! 300: if (*p == *q) goto found; ! 301: nxt: ! 302: if (mx <= ++i) i = 0; /* wrap around */ ! 303: } while (i != firsti); ! 304: ! 305: found: ! 306: for (Pname prev = n; n; prev = n, n=n->n_tbl_list){ ! 307: // error( 'd', "table_delete: found: %s %k lex: %d", n->string, n->n_key, n->lex_level ); ! 308: if (n->n_key == k && n->lex_level == ll ) { ! 309: // error( 'd', "table_delete: prev: %d n: %d n->tbl_list: %d", prev, n, n->n_tbl_list); ! 310: if ( prev == n && n->n_tbl_list == 0 ) ! 311: hash[i] = 0; ! 312: else ! 313: prev->n_tbl_list = n->n_tbl_list; ! 314: return; ! 315: } ! 316: } ! 317: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.