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
17static void     texpand     ARGS((struct table *tp, int nsize));
18static int      tnamecmp    ARGS((void *p1, void *p2));
19
20
21unsigned int
22hash(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
32void
33tinit(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
45static void
46texpand(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
81struct tbl *
82tsearch(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
104struct tbl *
105tenter(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
146void
147tdelete(p)
148	register struct tbl *p;
149{
150	p->flag = 0;
151}
152
153void
154twalk(ts, tp)
155	struct tstate *ts;
156	struct table *tp;
157{
158	ts->left = tp->size;
159	ts->next = tp->tbls;
160}
161
162struct tbl *
163tnext(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
174static int
175tnamecmp(p1, p2)
176	void *p1, *p2;
177{
178	return strcmp(((struct tbl *)p1)->name, ((struct tbl *)p2)->name);
179}
180
181struct tbl **
182tsort(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
203void tprintinfo ARGS((struct table *tp));
204
205void
206tprintinfo(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