/* hash.c: hash table support for functions and variables. */ /* Functions and variables are cached in both internal and external form for performance. Thus a variable which is never "dereferenced" with a $ is passed on to rc's children untouched. This is not so important for variables, but is a big win for functions, where a call to yyparse() is involved. */ #include "rc.h" #include "sigmsgs.h" static bool var_exportable(char *); static bool fn_exportable(char *); static int hash(char *, int); static int find(char *, Htab *, int); static void free_fn(Function *); Htab *fp; Htab *vp; static int fused, fsize, vused, vsize; static char **env; static int bozosize; static int envsize; static bool env_dirty = TRUE; static char *dead = ""; #define HASHSIZE 64 /* rc was debugged with HASHSIZE == 2; 64 is about right for normal use */ extern void inithash() { Htab *fpp, *vpp; int i; fp = ealloc(sizeof(Htab) * HASHSIZE); vp = ealloc(sizeof(Htab) * HASHSIZE); fused = vused = 0; fsize = vsize = HASHSIZE; for (vpp = vp, fpp = fp, i = 0; i < HASHSIZE; i++, vpp++, fpp++) vpp->name = fpp->name = NULL; } #define ADV() {if ((c = *s++) == '\0') break;} /* hash function courtesy of paul haahr */ static int hash(char *s, int size) { int c, n = 0; while (1) { ADV(); n += (c << 17) ^ (c << 11) ^ (c << 5) ^ (c >> 1); ADV(); n ^= (c << 14) + (c << 7) + (c << 4) + c; ADV(); n ^= (~c << 11) | ((c << 3) ^ (c >> 1)); ADV(); n -= (c << 16) | (c << 9) | (c << 2) | (c & 3); } if (n < 0) n = ~n; return n & (size - 1); /* need power of 2 size */ } static bool rehash(Htab *ht) { int i, j, size; int newsize, newused; Htab *newhtab; if (ht == fp) { if (fsize > 2 * fused) return FALSE; size = fsize; } else { if (vsize > 2 * vused) return FALSE; size = vsize; } newsize = 2 * size; newhtab = ealloc(newsize * sizeof(Htab)); for (i = 0; i < newsize; i++) newhtab[i].name = NULL; for (i = newused = 0; i < size; i++) if (ht[i].name != NULL && ht[i].name != dead) { newused++; j = hash(ht[i].name, newsize); while (newhtab[j].name != NULL) { j++; j &= (newsize - 1); } newhtab[j].name = ht[i].name; newhtab[j].p = ht[i].p; } if (ht == fp) { fused = newused; fp = newhtab; fsize = newsize; } else { vused = newused; vp = newhtab; vsize = newsize; } efree(ht); return TRUE; } #define varfind(s) find(s, vp, vsize) #define fnfind(s) find(s, fp, fsize) static int find(char *s, Htab *ht, int size) { int h = hash(s, size); while (ht[h].name != NULL && !streq(ht[h].name, s)) { h++; h &= size - 1; } return h; } extern void *lookup(char *s, Htab *ht) { int h = find(s, ht, ht == fp ? fsize : vsize); return (ht[h].name == NULL) ? NULL : ht[h].p; } extern Function *get_fn_place(char *s) { int h = fnfind(s); env_dirty = TRUE; if (fp[h].name == NULL) { if (rehash(fp)) h = fnfind(s); fused++; fp[h].name = ecpy(s); fp[h].p = enew(Function); } else free_fn(fp[h].p); return fp[h].p; } extern Variable *get_var_place(char *s, bool stack) { Variable *new; int h = varfind(s); env_dirty = TRUE; if (vp[h].name == NULL) { if (rehash(vp)) h = varfind(s); vused++; vp[h].name = ecpy(s); vp[h].p = enew(Variable); ((Variable *)vp[h].p)->n = NULL; return vp[h].p; } else { if (stack) { /* increase the stack by 1 */ new = enew(Variable); new->n = vp[h].p; return vp[h].p = new; } else { /* trample the top of the stack */ new = vp[h].p; efree(new->extdef); listfree(new->def); return new; } } } extern void delete_fn(char *s) { int h = fnfind(s); if (fp[h].name == NULL) return; /* not found */ env_dirty = TRUE; free_fn(fp[h].p); efree(fp[h].p); efree(fp[h].name); if (fp[(h+1)&(fsize-1)].name == NULL) { --fused; fp[h].name = NULL; } else { fp[h].name = dead; } } extern void delete_var(char *s, bool stack) { int h = varfind(s); Variable *v; if (vp[h].name == NULL) return; /* not found */ env_dirty = TRUE; v = vp[h].p; efree(v->extdef); listfree(v->def); if (v->n != NULL) { /* This is the top of a stack */ if (stack) { /* pop */ vp[h].p = v->n; efree(v); } else { /* else just empty */ v->extdef = NULL; v->def = NULL; } } else { /* needs to be removed from the hash table */ efree(v); efree(vp[h].name); if (vp[(h+1)&(vsize-1)].name == NULL) { --vused; vp[h].name = NULL; } else { vp[h].name = dead; } } } static void free_fn(Function *f) { treefree(f->def); efree(f->extdef); } extern void initenv(char **envp) { int n; for (n = 0; envp[n] != NULL; n++) ; n++; /* one for the null terminator */ if (n < HASHSIZE) n = HASHSIZE; env = ealloc((envsize = 2 * n) * sizeof (char *)); for (; *envp != NULL; envp++) if (strncmp(*envp, "fn_", conststrlen("fn_")) == 0) { if (!dashpee) fnassign_string(*envp); } else { if (!varassign_string(*envp)) /* add to bozo env */ env[bozosize++] = *envp; } } static bool var_exportable(char *s) { static char *notforexport[] = { "apid", "pid", "apids", "*", "ifs" }; int i; for (i = 0; i < arraysize(notforexport); i++) if (streq(s, notforexport[i])) return FALSE; return TRUE; } static bool fn_exportable(char *s) { int i; if (strncmp(s, "sig", conststrlen("sig")) == 0) { /* small speed hack */ for (i = 0; i < NUMOFSIGNALS; i++) if (streq(s, signals[i].name)) return FALSE; if (streq(s, "sigexit")) return FALSE; } return TRUE; } extern char **makeenv() { int ep, i; char *v; if (!env_dirty) return env; env_dirty = FALSE; ep = bozosize; if (vsize + fsize + 1 + bozosize > envsize) { envsize = 2 * (bozosize + vsize + fsize + 1); env = erealloc(env, envsize * sizeof(char *)); } for (i = 0; i < vsize; i++) { if (vp[i].name == NULL || vp[i].name == dead || !var_exportable(vp[i].name)) continue; v = varlookup_string(vp[i].name); if (v != NULL) env[ep++] = v; } for (i = 0; i < fsize; i++) { if (fp[i].name == NULL || fp[i].name == dead || !fn_exportable(fp[i].name)) continue; env[ep++] = fnlookup_string(fp[i].name); } env[ep] = NULL; qsort(env, (size_t) ep, sizeof(char *), starstrcmp); return env; } extern void whatare_all_vars() { int i; List *s; for (i = 0; i < vsize; i++) if (vp[i].name != NULL && (s = varlookup(vp[i].name)) != NULL) prettyprint_var(1, vp[i].name, s); for (i = 0; i < fsize; i++) if (fp[i].name != NULL && fp[i].name != dead) prettyprint_fn(1, fp[i].name, fnlookup(fp[i].name)); }