1 /* $NetBSD: table.c,v 1.4 2003/06/23 11:39:04 agc Exp $ */
2
3 /*
4 * dynamic hashed associative table for commands and variables
5 */
6 #include <sys/cdefs.h>
7
8 #ifndef lint
9 __RCSID("$NetBSD: table.c,v 1.4 2003/06/23 11:39:04 agc Exp $");
10 #endif
11
12
13 #include "sh.h"
14
15 #define INIT_TBLS 8 /* initial table size (power of 2) */
16
17 static void texpand ARGS((struct table *tp, int nsize));
18 static int tnamecmp ARGS((void *p1, void *p2));
19
20
21 unsigned int
hash(n)22 hash(n)
23 register const char * n;
24 {
25 register unsigned int h = 0;
26
27 while (*n != '\0')
28 h = 2*h + *n++;
29 return h * 32821; /* scatter bits */
30 }
31
32 void
tinit(tp,ap,tsize)33 tinit(tp, ap, tsize)
34 register struct table *tp;
35 register Area *ap;
36 int tsize;
37 {
38 tp->areap = ap;
39 tp->tbls = NULL;
40 tp->size = tp->nfree = 0;
41 if (tsize)
42 texpand(tp, tsize);
43 }
44
45 static void
texpand(tp,nsize)46 texpand(tp, nsize)
47 register struct table *tp;
48 int nsize;
49 {
50 register int i;
51 register struct tbl *tblp, **p;
52 register struct tbl **ntblp, **otblp = tp->tbls;
53 int osize = tp->size;
54
55 ntblp = (struct tbl**) alloc(sizeofN(struct tbl *, nsize), tp->areap);
56 for (i = 0; i < nsize; i++)
57 ntblp[i] = NULL;
58 tp->size = nsize;
59 tp->nfree = 8*nsize/10; /* table can get 80% full */
60 tp->tbls = ntblp;
61 if (otblp == NULL)
62 return;
63 for (i = 0; i < osize; i++) {
64 if ((tblp = otblp[i]) != NULL) {
65 if ((tblp->flag&DEFINED)) {
66 for (p = &ntblp[hash(tblp->name)
67 & (tp->size-1)];
68 *p != NULL; p--)
69 if (p == ntblp) /* wrap */
70 p += tp->size;
71 *p = tblp;
72 tp->nfree--;
73 } else if (!(tblp->flag & FINUSE)) {
74 afree((void*)tblp, tp->areap);
75 }
76 }
77 }
78 afree((void*)otblp, tp->areap);
79 }
80
81 struct tbl *
tsearch(tp,n,h)82 tsearch(tp, n, h)
83 register struct table *tp; /* table */
84 register const char *n; /* name to enter */
85 unsigned int h; /* hash(n) */
86 {
87 register struct tbl **pp, *p;
88
89 if (tp->size == 0)
90 return NULL;
91
92 /* search for name in hashed table */
93 for (pp = &tp->tbls[h & (tp->size-1)]; (p = *pp) != NULL; pp--) {
94 if (*p->name == *n && strcmp(p->name, n) == 0
95 && (p->flag&DEFINED))
96 return p;
97 if (pp == tp->tbls) /* wrap */
98 pp += tp->size;
99 }
100
101 return NULL;
102 }
103
104 struct tbl *
tenter(tp,n,h)105 tenter(tp, n, h)
106 register struct table *tp; /* table */
107 register const char *n; /* name to enter */
108 unsigned int h; /* hash(n) */
109 {
110 register struct tbl **pp, *p;
111 register int len;
112
113 if (tp->size == 0)
114 texpand(tp, INIT_TBLS);
115 Search:
116 /* search for name in hashed table */
117 for (pp = &tp->tbls[h & (tp->size-1)]; (p = *pp) != NULL; pp--) {
118 if (*p->name == *n && strcmp(p->name, n) == 0)
119 return p; /* found */
120 if (pp == tp->tbls) /* wrap */
121 pp += tp->size;
122 }
123
124 if (tp->nfree <= 0) { /* too full */
125 texpand(tp, 2*tp->size);
126 goto Search;
127 }
128
129 /* create new tbl entry */
130 len = strlen(n) + 1;
131 p = (struct tbl *) alloc(offsetof(struct tbl, name[0]) + len,
132 tp->areap);
133 p->flag = 0;
134 p->type = 0;
135 p->areap = tp->areap;
136 p->u2.field = 0;
137 p->u.array = (struct tbl *)0;
138 memcpy(p->name, n, len);
139
140 /* enter in tp->tbls */
141 tp->nfree--;
142 *pp = p;
143 return p;
144 }
145
146 void
tdelete(p)147 tdelete(p)
148 register struct tbl *p;
149 {
150 p->flag = 0;
151 }
152
153 void
twalk(ts,tp)154 twalk(ts, tp)
155 struct tstate *ts;
156 struct table *tp;
157 {
158 ts->left = tp->size;
159 ts->next = tp->tbls;
160 }
161
162 struct tbl *
tnext(ts)163 tnext(ts)
164 struct tstate *ts;
165 {
166 while (--ts->left >= 0) {
167 struct tbl *p = *ts->next++;
168 if (p != NULL && (p->flag&DEFINED))
169 return p;
170 }
171 return NULL;
172 }
173
174 static int
tnamecmp(p1,p2)175 tnamecmp(p1, p2)
176 void *p1, *p2;
177 {
178 return strcmp(((struct tbl *)p1)->name, ((struct tbl *)p2)->name);
179 }
180
181 struct tbl **
tsort(tp)182 tsort(tp)
183 register struct table *tp;
184 {
185 register int i;
186 register struct tbl **p, **sp, **dp;
187
188 p = (struct tbl **)alloc(sizeofN(struct tbl *, tp->size+1), ATEMP);
189 sp = tp->tbls; /* source */
190 dp = p; /* dest */
191 for (i = 0; i < tp->size; i++)
192 if ((*dp = *sp++) != NULL && (((*dp)->flag&DEFINED) ||
193 ((*dp)->flag&ARRAY)))
194 dp++;
195 i = dp - p;
196 qsortp((void**)p, (size_t)i, tnamecmp);
197 p[i] = NULL;
198 return p;
199 }
200
201 #ifdef PERF_DEBUG /* performance debugging */
202
203 void tprintinfo ARGS((struct table *tp));
204
205 void
tprintinfo(tp)206 tprintinfo(tp)
207 struct table *tp;
208 {
209 struct tbl *te;
210 char *n;
211 unsigned int h;
212 int ncmp;
213 int totncmp = 0, maxncmp = 0;
214 int nentries = 0;
215 struct tstate ts;
216
217 shellf("table size %d, nfree %d\n", tp->size, tp->nfree);
218 shellf(" Ncmp name\n");
219 twalk(&ts, tp);
220 while ((te = tnext(&ts))) {
221 register struct tbl **pp, *p;
222
223 h = hash(n = te->name);
224 ncmp = 0;
225
226 /* taken from tsearch() and added counter */
227 for (pp = &tp->tbls[h & (tp->size-1)]; (p = *pp); pp--) {
228 ncmp++;
229 if (*p->name == *n && strcmp(p->name, n) == 0
230 && (p->flag&DEFINED))
231 break; /* return p; */
232 if (pp == tp->tbls) /* wrap */
233 pp += tp->size;
234 }
235 shellf(" %4d %s\n", ncmp, n);
236 totncmp += ncmp;
237 nentries++;
238 if (ncmp > maxncmp)
239 maxncmp = ncmp;
240 }
241 if (nentries)
242 shellf(" %d entries, worst ncmp %d, avg ncmp %d.%02d\n",
243 nentries, maxncmp,
244 totncmp / nentries,
245 (totncmp % nentries) * 100 / nentries);
246 }
247 #endif /* PERF_DEBUG */
248