![[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 [MW Coherent from dump] / coherent / a / usr / bob / korn|
Return to table.c CVS log | Up to [MW Coherent from dump] / coherent / a / usr / bob / korn |
1.1 root 1: static char *RCSid = "$Header: table.c,v 3.1 88/11/03 09:17:53 egisin Exp $";
2:
3: /*
4: * dynamic hashed associative table for commands and variables
5: */
6:
7: #include <stddef.h>
8: #include <stdlib.h>
9: #include <errno.h>
10: #include <setjmp.h>
11: #include "sh.h"
12: #include "table.h"
13:
14: #define INIT_TBLS 8 /* initial table size (power of 2) */
15:
16: static struct tstate {
17: int left;
18: struct tbl **next;
19: } tstate;
20:
21: static void texpand();
22:
23: unsigned int
24: hash(n)
25: register char * n;
26: {
27: register unsigned int h = 0;
28:
29: while (*n != '\0')
30: h = 2*h + *n++;
31: return h * (unsigned)32821L; /* scatter bits */
32: }
33:
34: #if 0
35: phash(s) char *s; {
36: printf("%2d: %s\n", hash(s)%32, s);
37: }
38: #endif
39:
40: void
41: tinit(tp, ap)
42: register struct table *tp;
43: register Area *ap;
44: {
45: tp->areap = ap;
46: tp->size = tp->free = 0;
47: tp->tbls = NULL;
48: }
49:
50: static void
51: texpand(tp, nsize)
52: register struct table *tp;
53: int nsize;
54: {
55: register int i;
56: register struct tbl *tblp, **p;
57: register struct tbl **ntblp, **otblp = tp->tbls;
58: int osize = tp->size;
59:
60: ntblp = alloc(sizeofN(struct tbl *, nsize), tp->areap);
61: for (i = 0; i < nsize; i++)
62: ntblp[i] = NULL;
63: tp->size = nsize;
64: tp->free = 8*nsize/10; /* table can get 80% full */
65: tp->tbls = ntblp;
66: if (otblp == NULL)
67: return;
68: for (i = 0; i < osize; i++)
69: if ((tblp = otblp[i]) != NULL)
70: if ((tblp->flag&DEFINED)) {
71: for (p = &ntblp[hash(tblp->name) & tp->size-1];
72: *p != NULL; p--)
73: if (p == ntblp) /* wrap */
74: p += tp->size;
75: *p = tblp;
76: tp->free--;
77: } else {
78: afree((Void*)tblp, tp->areap);
79: }
80: afree((Void*)otblp, tp->areap);
81: }
82:
83: struct tbl *
84: tsearch(tp, n, h)
85: register struct table *tp; /* table */
86: register char *n; /* name to enter */
87: unsigned int h; /* hash(n) */
88: {
89: register struct tbl **pp, *p;
90:
91: if (tp->size == 0)
92: return NULL;
93:
94: /* search for name in hashed table */
95: for (pp = &tp->tbls[h & tp->size-1]; (p = *pp) != NULL; pp--) {
96: if (*p->name == *n && strcmp(p->name, n) == 0
97: && (p->flag&DEFINED))
98: return p;
99: if (pp == tp->tbls) /* wrap */
100: pp += tp->size;
101: }
102:
103: return NULL;
104: }
105:
106: struct tbl *
107: tenter(tp, n, h)
108: register struct table *tp; /* table */
109: register char *n; /* name to enter */
110: unsigned int h; /* hash(n) */
111: {
112: register struct tbl **pp, *p;
113: register char *cp;
114:
115: if (tp->size == 0)
116: texpand(tp, INIT_TBLS);
117: Search:
118: /* search for name in hashed table */
119: for (pp = &tp->tbls[h & tp->size-1]; (p = *pp) != NULL; pp--) {
120: if (*p->name == *n && strcmp(p->name, n) == 0)
121: return p; /* found */
122: if (pp == tp->tbls) /* wrap */
123: pp += tp->size;
124: }
125:
126: if (tp->free <= 0) { /* too full */
127: texpand(tp, 2*tp->size);
128: goto Search;
129: }
130:
131: /* create new tbl entry */
132: for (cp = n; *cp != '\0'; cp++)
133: ;
134: p = (struct tbl *) alloc(offsetof(struct tbl, name[(cp-n)+1]), tp->areap);
135: p->flag = 0;
136: p->type = 0;
137: for (cp = p->name; *n != '\0';)
138: *cp++ = *n++;
139: *cp = '\0';
140:
141: /* enter in tp->tbls */
142: tp->free--;
143: *pp = p;
144: return p;
145: }
146:
147: void
148: tdelete(p)
149: register struct tbl *p;
150: {
151: p->flag = 0;
152: }
153:
154: void
155: twalk(tp)
156: register struct table *tp;
157: {
158: tstate.left = tp->size;
159: tstate.next = tp->tbls;
160: }
161:
162: struct tbl *
163: tnext()
164: {
165: while (--tstate.left >= 0) {
166: struct tbl *p = *tstate.next++;
167: if (p != NULL && (p->flag&DEFINED))
168: return p;
169: }
170: return NULL;
171: }
172:
173: static int
174: tnamecmp(p1, p2)
175: Void *p1, *p2;
176: {
177: return strcmp(((struct tbl *)p1)->name, ((struct tbl *)p2)->name);
178: }
179:
180: struct tbl **
181: tsort(tp)
182: register struct table *tp;
183: {
184: register int i;
185: register struct tbl **p, **sp, **dp;
186:
187: p = (struct tbl **)alloc(sizeofN(struct tbl *, tp->size+1), ATEMP);
188: sp = tp->tbls; /* source */
189: dp = p; /* dest */
190: for (i = 0; i < tp->size; i++)
191: if ((*dp = *sp++) != NULL && ((*dp)->flag&DEFINED))
192: dp++;
193: i = dp - p;
194: qsortp((Void**)p, (size_t)i, tnamecmp);
195: p[i] = NULL;
196: return p;
197: }
198:
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.