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