![[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 / optcfront|
Return to table.c CVS log | Up to [Research Unix] / researchv10no / cmd / cfront / optcfront |
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.