Subversion Repositories planix.SVN

Rev

Rev 2 | Details | Compare with Previous | Last modification | View Log | RSS feed

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