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