![[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.