1 /* hash.c: hash table support for functions and variables. */
2
3 /*
4 Functions and variables are cached in both internal and external
5 form for performance. Thus a variable which is never "dereferenced"
6 with a $ is passed on to rc's children untouched. This is not so
7 important for variables, but is a big win for functions, where a call
8 to yyparse() is involved.
9 */
10
11 #include "rc.h"
12 #include "sigmsgs.h"
13
14 static bool var_exportable(char *);
15 static bool fn_exportable(char *);
16 static int hash(char *, int);
17 static int find(char *, Htab *, int);
18 static void free_fn(rc_Function *);
19
20 Htab *fp;
21 Htab *vp;
22 static int fused, fsize, vused, vsize;
23 static char **env;
24 static int bozosize;
25 static int envsize;
26 static bool env_dirty = TRUE;
27 static char *dead = "";
28
29 #define HASHSIZE 64 /* rc was debugged with HASHSIZE == 2; 64 is about right for normal use */
30
inithash()31 extern void inithash() {
32 Htab *fpp, *vpp;
33 int i;
34 fp = ealloc(sizeof(Htab) * HASHSIZE);
35 vp = ealloc(sizeof(Htab) * HASHSIZE);
36 fused = vused = 0;
37 fsize = vsize = HASHSIZE;
38 for (vpp = vp, fpp = fp, i = 0; i < HASHSIZE; i++, vpp++, fpp++)
39 vpp->name = fpp->name = NULL;
40 }
41
42 #define ADV() {if ((c = *s++) == '\0') break;}
43
44 /* hash function courtesy of paul haahr */
45
hash(char * s,int size)46 static int hash(char *s, int size) {
47 int c, n = 0;
48 while (1) {
49 ADV();
50 n += (c << 17) ^ (c << 11) ^ (c << 5) ^ (c >> 1);
51 ADV();
52 n ^= (c << 14) + (c << 7) + (c << 4) + c;
53 ADV();
54 n ^= (~c << 11) | ((c << 3) ^ (c >> 1));
55 ADV();
56 n -= (c << 16) | (c << 9) | (c << 2) | (c & 3);
57 }
58 if (n < 0)
59 n = ~n;
60 return n & (size - 1); /* need power of 2 size */
61 }
62
rehash(Htab * ht)63 static bool rehash(Htab *ht) {
64 int i, j, size;
65 int newsize, newused;
66 Htab *newhtab;
67 if (ht == fp) {
68 if (fsize > 2 * fused)
69 return FALSE;
70 size = fsize;
71 } else {
72 if (vsize > 2 * vused)
73 return FALSE;
74 size = vsize;
75 }
76 newsize = 2 * size;
77 newhtab = ealloc(newsize * sizeof(Htab));
78 for (i = 0; i < newsize; i++)
79 newhtab[i].name = NULL;
80 for (i = newused = 0; i < size; i++)
81 if (ht[i].name != NULL && ht[i].name != dead) {
82 newused++;
83 j = hash(ht[i].name, newsize);
84 while (newhtab[j].name != NULL) {
85 j++;
86 j &= (newsize - 1);
87 }
88 newhtab[j].name = ht[i].name;
89 newhtab[j].p = ht[i].p;
90 }
91 if (ht == fp) {
92 fused = newused;
93 fp = newhtab;
94 fsize = newsize;
95 } else {
96 vused = newused;
97 vp = newhtab;
98 vsize = newsize;
99 }
100 efree(ht);
101 return TRUE;
102 }
103
104 #define varfind(s) find(s, vp, vsize)
105 #define fnfind(s) find(s, fp, fsize)
106
find(char * s,Htab * ht,int size)107 static int find(char *s, Htab *ht, int size) {
108 int h = hash(s, size);
109 while (ht[h].name != NULL && !streq(ht[h].name, s)) {
110 h++;
111 h &= size - 1;
112 }
113 return h;
114 }
115
lookup(char * s,Htab * ht)116 extern void *lookup(char *s, Htab *ht) {
117 int h = find(s, ht, ht == fp ? fsize : vsize);
118 return (ht[h].name == NULL) ? NULL : ht[h].p;
119 }
120
get_fn_place(char * s)121 extern rc_Function *get_fn_place(char *s) {
122 int h = fnfind(s);
123 env_dirty = TRUE;
124 if (fp[h].name == NULL) {
125 if (rehash(fp))
126 h = fnfind(s);
127 fused++;
128 fp[h].name = ecpy(s);
129 fp[h].p = enew(rc_Function);
130 } else
131 free_fn(fp[h].p);
132 return fp[h].p;
133 }
134
get_var_place(char * s,bool stack)135 extern Variable *get_var_place(char *s, bool stack) {
136 Variable *new;
137 int h = varfind(s);
138
139 env_dirty = TRUE;
140
141 if (vp[h].name == NULL) {
142 if (rehash(vp))
143 h = varfind(s);
144 vused++;
145 vp[h].name = ecpy(s);
146 vp[h].p = enew(Variable);
147 ((Variable *)vp[h].p)->n = NULL;
148 return vp[h].p;
149 } else {
150 if (stack) { /* increase the stack by 1 */
151 new = enew(Variable);
152 new->n = vp[h].p;
153 return vp[h].p = new;
154 } else { /* trample the top of the stack */
155 new = vp[h].p;
156 efree(new->extdef);
157 listfree(new->def);
158 return new;
159 }
160 }
161 }
162
delete_fn(char * s)163 extern void delete_fn(char *s) {
164 int h = fnfind(s);
165 if (fp[h].name == NULL)
166 return; /* not found */
167 env_dirty = TRUE;
168 free_fn(fp[h].p);
169 efree(fp[h].p);
170 efree(fp[h].name);
171 if (fp[(h+1)&(fsize-1)].name == NULL) {
172 --fused;
173 fp[h].name = NULL;
174 } else {
175 fp[h].name = dead;
176 }
177 }
178
delete_var(char * s,bool stack)179 extern void delete_var(char *s, bool stack) {
180 int h = varfind(s);
181 Variable *v;
182 if (vp[h].name == NULL)
183 return; /* not found */
184 env_dirty = TRUE;
185 v = vp[h].p;
186 efree(v->extdef);
187 listfree(v->def);
188 if (v->n != NULL) { /* This is the top of a stack */
189 if (stack) { /* pop */
190 vp[h].p = v->n;
191 efree(v);
192 } else { /* else just empty */
193 v->extdef = NULL;
194 v->def = NULL;
195 }
196 } else { /* needs to be removed from the hash table */
197 efree(v);
198 efree(vp[h].name);
199 if (vp[(h+1)&(vsize-1)].name == NULL) {
200 --vused;
201 vp[h].name = NULL;
202 } else {
203 vp[h].name = dead;
204 }
205 }
206 }
207
free_fn(rc_Function * f)208 static void free_fn(rc_Function *f) {
209 treefree(f->def);
210 efree(f->extdef);
211 }
212
initenv(char ** envp)213 extern void initenv(char **envp) {
214 int n;
215 for (n = 0; envp[n] != NULL; n++)
216 ;
217 n++; /* one for the null terminator */
218 if (n < HASHSIZE)
219 n = HASHSIZE;
220 env = ealloc((envsize = 2 * n) * sizeof (char *));
221 for (; *envp != NULL; envp++)
222 if (strncmp(*envp, "fn_", conststrlen("fn_")) == 0) {
223 if (!dashpee)
224 fnassign_string(*envp);
225 } else {
226 if (!varassign_string(*envp)) /* add to bozo env */
227 env[bozosize++] = *envp;
228 }
229 }
230
231 static char *neverexport[] = {
232 "apid", "apids", "bqstatus", "cdpath", "home",
233 "ifs", "path", "pid", "status", "*"
234 };
235
236 /* for a few variables that have default values, we export them only
237 if they've been explicitly set; maybeexport[n].flag is TRUE if this
238 has occurred. */
239 struct nameflag {
240 char *name;
241 bool flag;
242 };
243 static struct nameflag maybeexport[] = {
244 { "prompt", FALSE },
245 { "version", FALSE }
246 };
247
set_exportable(char * s,bool b)248 void set_exportable(char *s, bool b) {
249 int i;
250 for (i = 0; i < arraysize(maybeexport); ++i)
251 if (maybeexport[i].flag != b && streq(s, maybeexport[i].name))
252 maybeexport[i].flag = b;
253 }
254
var_exportable(char * s)255 static bool var_exportable(char *s) {
256 int i;
257 for (i = 0; i < arraysize(neverexport); i++)
258 if (streq(s, neverexport[i]))
259 return FALSE;
260 for (i = 0; i < arraysize(maybeexport); i++)
261 if (maybeexport[i].flag == FALSE && streq(s, maybeexport[i].name))
262 return FALSE;
263 return TRUE;
264 }
265
fn_exportable(char * s)266 static bool fn_exportable(char *s) {
267 int i;
268 if (strncmp(s, "sig", conststrlen("sig")) == 0) { /* small speed hack */
269 for (i = 0; i < NUMOFSIGNALS; i++)
270 if (streq(s, signals[i].name))
271 return FALSE;
272 if (streq(s, "sigexit"))
273 return FALSE;
274 }
275 return TRUE;
276 }
277
makeenv()278 extern char **makeenv() {
279 int ep, i;
280 char *v;
281 if (!env_dirty)
282 return env;
283 env_dirty = FALSE;
284 ep = bozosize;
285 if (vsize + fsize + 1 + bozosize > envsize) {
286 envsize = 2 * (bozosize + vsize + fsize + 1);
287 env = erealloc(env, envsize * sizeof(char *));
288 }
289 for (i = 0; i < vsize; i++) {
290 if (vp[i].name == NULL || vp[i].name == dead || !var_exportable(vp[i].name))
291 continue;
292 v = varlookup_string(vp[i].name);
293 if (v != NULL)
294 env[ep++] = v;
295 }
296 for (i = 0; i < fsize; i++) {
297 if (fp[i].name == NULL || fp[i].name == dead || !fn_exportable(fp[i].name))
298 continue;
299 env[ep++] = fnlookup_string(fp[i].name);
300 }
301 env[ep] = NULL;
302 qsort(env, (size_t) ep, sizeof(char *), starstrcmp);
303 return env;
304 }
305
whatare_all_vars(bool showfn,bool showvar)306 extern void whatare_all_vars(bool showfn, bool showvar) {
307 int i;
308 List *s;
309 if (showvar)
310 for (i = 0; i < vsize; i++)
311 if (vp[i].name != NULL && (s = varlookup(vp[i].name)) != NULL)
312 prettyprint_var(1, vp[i].name, s);
313 if (showfn)
314 for (i = 0; i < fsize; i++)
315 if (fp[i].name != NULL && fp[i].name != dead)
316 prettyprint_fn(1, fp[i].name, fnlookup(fp[i].name));
317 }
318