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
15 struct table taliases; /* tracked aliases */
16 struct table builtins; /* built-in commands */
17 struct table aliases; /* aliases */
18 struct table keywords; /* keywords */
19 struct table homedirs; /* homedir() cache */
20
21 char *search_path; /* copy of either PATH or def_path */
22 const char *def_path; /* path to use if PATH not set */
23 char *tmpdir; /* TMPDIR value */
24 const char *prompt;
25 int cur_prompt; /* PS1 or PS2 */
26 int current_lineno; /* LINENO value */
27
28 static void texpand(struct table *, int);
29 static int tnamecmp(const void *, const void *);
30
31
32 unsigned int
hash(const char * n)33 hash(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
42 void
ktinit(struct table * tp,Area * ap,int tsize)43 ktinit(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
52 static void
texpand(struct table * tp,int nsize)53 texpand(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) */
87 struct tbl *
ktsearch(struct table * tp,const char * n,unsigned int h)88 ktsearch(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) */
110 struct tbl *
ktenter(struct table * tp,const char * n,unsigned int h)111 ktenter(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
152 void
ktdelete(struct tbl * p)153 ktdelete(struct tbl *p)
154 {
155 p->flag = 0;
156 }
157
158 void
ktwalk(struct tstate * ts,struct table * tp)159 ktwalk(struct tstate *ts, struct table *tp)
160 {
161 ts->left = tp->size;
162 ts->next = tp->tbls;
163 }
164
165 struct tbl *
ktnext(struct tstate * ts)166 ktnext(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
176 static int
tnamecmp(const void * p1,const void * p2)177 tnamecmp(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
184 struct tbl **
ktsort(struct table * tp)185 ktsort(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
206 void tprintinfo(struct table *tp);
207
208 void
tprintinfo(struct table * tp)209 tprintinfo(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 */
250