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