BSD 4_4 development

[unix-history] / usr / src / contrib / rc-1.4 / hash.c

/* 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));
}