home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 January / usenetsourcesnewsgroupsinfomagicjanuary1994.iso / sources / misc / volume30 / rc / part02 / hash.c next >
Encoding:
C/C++ Source or Header  |  1992-05-30  |  6.6 KB  |  303 lines
  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(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.  
  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.  
  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.  
  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.  
  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.  
  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.  
  121. extern 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(Function);
  130.     } else
  131.         free_fn(fp[h].p);
  132.     return fp[h].p;
  133. }
  134.  
  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.  
  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.  
  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.  
  208. static void free_fn(Function *f) {
  209.     treefree(f->def);
  210.     efree(f->extdef);
  211. }
  212.  
  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 bool var_exportable(char *s) {
  232.     static char *notforexport[] = {
  233.         "apid", "pid", "apids", "*", "ifs"
  234.     };
  235.     int i;
  236.     for (i = 0; i < arraysize(notforexport); i++)
  237.         if (streq(s, notforexport[i]))
  238.             return FALSE;
  239.     return TRUE;
  240. }
  241.  
  242. static bool fn_exportable(char *s) {
  243.     int i;
  244.     if (strncmp(s, "sig", conststrlen("sig")) == 0) { /* small speed hack */
  245.         for (i = 0; i < NUMOFSIGNALS; i++)
  246.             if (streq(s, signals[i].name))
  247.                 return FALSE;
  248.         if (streq(s, "sigexit"))
  249.             return FALSE;
  250.     }
  251.     return TRUE;
  252. }
  253.  
  254. extern char **makeenv() {
  255.     int ep, i;
  256.     char *v;
  257.     if (!env_dirty)
  258.         return env;
  259.     env_dirty = FALSE;
  260.     ep = bozosize;
  261.     if (vsize + fsize + 1 + bozosize > envsize) {
  262.         envsize = 2 * (bozosize + vsize + fsize + 1);
  263.         env = erealloc(env, envsize * sizeof(char *));
  264.     }
  265.     for (i = 0; i < vsize; i++) {
  266.         if (vp[i].name == NULL || vp[i].name == dead || !var_exportable(vp[i].name))
  267.             continue;
  268.         v = varlookup_string(vp[i].name);
  269.         if (v != NULL)
  270.             env[ep++] = v;
  271.     }
  272.     for (i = 0; i < fsize; i++) {
  273.         if (fp[i].name == NULL || fp[i].name == dead || !fn_exportable(fp[i].name))
  274.             continue;
  275.         env[ep++] = fnlookup_string(fp[i].name);
  276.     }
  277.     env[ep] = NULL;
  278.     qsort(env, (SIZE_T) ep, sizeof(char *), starstrcmp);
  279.     return env;
  280. }
  281.  
  282. extern void whatare_all_vars() {
  283.     int i;
  284.     List *s;
  285.     for (i = 0; i < vsize; i++)
  286.         if (vp[i].name != NULL && (s = varlookup(vp[i].name)) != NULL)
  287.             prettyprint_var(1, vp[i].name, s);
  288.     for (i = 0; i < fsize; i++)
  289.         if (fp[i].name != NULL && fp[i].name != dead)
  290.             prettyprint_fn(1, fp[i].name, fnlookup(fp[i].name));
  291. }
  292.  
  293. /* fake getenv() for readline() follows: */
  294.  
  295. #ifdef READLINE
  296. extern char *getenv(const char *name) {
  297.     List *s;
  298.     if (name == NULL || vp == NULL || (s = varlookup((char *) name)) == NULL)
  299.         return NULL;
  300.     return s->w;
  301. }
  302. #endif
  303.