home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 January / usenetsourcesnewsgroupsinfomagicjanuary1994.iso / sources / misc / volume20 / rc / part03 / hash.c < prev    next >
Encoding:
C/C++ Source or Header  |  1991-05-22  |  6.4 KB  |  335 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 "utils.h"
  13. #include "hash.h"
  14. #include "list.h"
  15. #include "tree.h"
  16. #include "footobar.h"
  17.  
  18. static boolean exportable(char *);
  19. static int hash(char *, int);
  20. static int find(char *, Htab *, int);
  21. static void free_fn(Function *);
  22.  
  23. Htab *fp;
  24. Htab *vp;
  25. static int fused, fsize, vused, vsize;
  26. static char **env;
  27. static int bozosize;
  28. static int envsize;
  29. static boolean env_dirty = TRUE;
  30. static char *dead = "";
  31.  
  32. #define HASHSIZE 64 /* rc was debugged with HASHSIZE == 2; 64 is about right for normal use */
  33.  
  34. void inithash(void) {
  35.     int i;
  36.     Htab *fpp, *vpp;
  37.  
  38.     fp = ealloc(sizeof(Htab) * HASHSIZE);
  39.     vp = ealloc(sizeof(Htab) * HASHSIZE);
  40.     fused = vused = 0;
  41.     fsize = vsize = HASHSIZE;
  42.  
  43.     for (vpp = vp, fpp = fp, i = 0; i < HASHSIZE; i++, vpp++, fpp++)
  44.         vpp->name = fpp->name = NULL;
  45. }
  46.  
  47. #define ADV()   {if ((c = *s++) == '\0') break;}
  48.  
  49. /* hash function courtesy of paul haahr */
  50.  
  51. static int hash(char *s, int size) {
  52.     int n = 0;
  53.     int c;
  54.  
  55.     while (1) {
  56.         ADV();
  57.         n += (c << 17) ^ (c << 11) ^ (c << 5) ^ (c >> 1);
  58.         ADV();
  59.         n ^= (c << 14) + (c << 7) + (c << 4) + c;
  60.         ADV();
  61.         n ^= (~c << 11) | ((c << 3) ^ (c >> 1));
  62.         ADV();
  63.         n -= (c << 16) | (c << 9) | (c << 2) | (c & 3);
  64.     }
  65.  
  66.     if (n < 0)
  67.         n = ~n;
  68.  
  69.     return n & (size - 1); /* need power of 2 size */
  70. }
  71.  
  72. static boolean rehash(Htab *ht) {
  73.     int i,j,size;
  74.     int newsize,newused;
  75.     Htab *newhtab;
  76.  
  77.     if (ht == fp) {
  78.         if (fsize > 2 * fused)
  79.             return FALSE;
  80.         size = fsize;
  81.     } else {
  82.         if (vsize > 2 * vused)
  83.             return FALSE;
  84.         size = vsize;
  85.     }
  86.  
  87.  
  88.     newsize = 2 * size;
  89.     newhtab = ealloc(newsize * sizeof(Htab));
  90.     for (i = 0; i < newsize; i++)
  91.         newhtab[i].name = NULL;
  92.  
  93.     for (i = newused = 0; i < size; i++)
  94.         if (ht[i].name != NULL && ht[i].name != dead) {
  95.             newused++;
  96.             j = hash(ht[i].name, newsize);
  97.             while (newhtab[j].name != NULL) {
  98.                 j++;
  99.                 j &= (newsize - 1);
  100.             }
  101.             newhtab[j].name = ht[i].name;
  102.             newhtab[j].p = ht[i].p;
  103.         }
  104.  
  105.     if (ht == fp) {
  106.         fused = newused;
  107.         fp = newhtab;
  108.         fsize = newsize;
  109.     } else {
  110.         vused = newused;
  111.         vp = newhtab;
  112.         vsize = newsize;
  113.     }
  114.  
  115.     efree(ht);
  116.     return TRUE;
  117. }
  118.  
  119. #define varfind(s) find(s,vp,vsize)
  120. #define fnfind(s) find(s,fp,fsize)
  121.  
  122. static int find(char *s, Htab *ht, int size) {
  123.     int h = hash(s, size);
  124.  
  125.     while (ht[h].name != NULL && !streq(ht[h].name,s)) {
  126.         h++;
  127.         h &= size - 1;
  128.     }
  129.  
  130.     return h;
  131. }
  132.  
  133. void *lookup(char *s, Htab *ht) {
  134.     int h = find(s, ht, ht == fp ? fsize : vsize);
  135.  
  136.     return (ht[h].name == NULL) ? NULL : ht[h].p;
  137. }
  138.  
  139. Function *get_fn_place(char *s) {
  140.     int h = fnfind(s);
  141.  
  142.     env_dirty = TRUE;
  143.  
  144.     if (fp[h].name == NULL) {
  145.         if (rehash(fp))
  146.             h = fnfind(s);
  147.         fused++;
  148.         fp[h].name = ecpy(s);
  149.         fp[h].p = enew(Function);
  150.     } else
  151.         free_fn(fp[h].p);
  152.  
  153.     return fp[h].p;
  154. }
  155.  
  156. Variable *get_var_place(char *s, boolean stack) {
  157.     Variable *new;
  158.     int h = varfind(s);
  159.  
  160.     env_dirty = TRUE;
  161.  
  162.     if (vp[h].name == NULL) {
  163.         if (rehash(vp))
  164.             h = varfind(s);
  165.         vused++;
  166.         vp[h].name = ecpy(s);
  167.         strcpy(vp[h].name, s);
  168.         vp[h].p = enew(Variable);
  169.         ((Variable *)vp[h].p)->n = NULL;
  170.         return vp[h].p;
  171.     } else {
  172.         if (stack) {    /* increase the stack by 1 */
  173.             new = enew(Variable);
  174.             new->n = vp[h].p;
  175.             return vp[h].p = new;
  176.         } else {    /* trample the top of the stack */
  177.             new = vp[h].p;
  178.             efree(new->extdef);
  179.             listfree(new->def);
  180.             return new;
  181.         }
  182.     }
  183. }
  184.  
  185. void delete_fn(char *s) {
  186.     int h = fnfind(s);
  187.  
  188.     if (fp[h].name == NULL)
  189.         return; /* not found */
  190.  
  191.     env_dirty = TRUE;
  192.  
  193.     free_fn(fp[h].p);
  194.     efree(fp[h].p);
  195.     efree(fp[h].name);
  196.     if (fp[h+1].name == NULL) {
  197.         --fused;
  198.         fp[h].name = NULL;
  199.     } else {
  200.         fp[h].name = dead;
  201.     }
  202. }
  203.  
  204. void delete_var(char *s, boolean stack) {
  205.     int h = varfind(s);
  206.     Variable *v;
  207.  
  208.     if (vp[h].name == NULL)
  209.         return; /* not found */
  210.  
  211.     env_dirty = TRUE;
  212.  
  213.     v = vp[h].p;
  214.     efree(v->extdef);
  215.     listfree(v->def);
  216.  
  217.     if (v->n != NULL) { /* This is the top of a stack */
  218.         if (stack) { /* pop */
  219.             vp[h].p = v->n;
  220.             efree(v);
  221.         } else { /* else just empty */
  222.             v->extdef = NULL;
  223.             v->def = NULL;
  224.         }
  225.     } else { /* needs to be removed from the hash table */
  226.         efree(v);
  227.         efree(vp[h].name);
  228.         if (vp[h+1].name == NULL) {
  229.             --vused;
  230.             vp[h].name = NULL;
  231.         } else {
  232.             vp[h].name = dead;
  233.         }
  234.     }
  235. }
  236.  
  237. static void free_fn(Function *f) {
  238.     treefree(f->def);
  239.     efree(f->extdef);
  240. }
  241.  
  242. void initenv(char **envp) {
  243.     int n;
  244.  
  245.     for (n = 0; envp[n] != NULL; n++)
  246.         ;
  247.     n++; /* one for the null terminator */
  248.  
  249.     if (n < HASHSIZE)
  250.         n = HASHSIZE;
  251.  
  252.     env = ealloc((envsize = 2 * n) * sizeof (char *));
  253.  
  254.     for (; *envp != NULL; envp++)
  255.         if (strncmp(*envp, "fn_", sizeof("fn_") - 1) == 0)
  256.             fnassign_string(*envp);
  257.         else
  258.             if (!varassign_string(*envp)) /* add to bozo env */
  259.                 env[bozosize++] = *envp;
  260. }
  261.  
  262. static boolean exportable(char *s) {
  263.     int i;
  264.     static char *notforexport[] = {
  265.         "sighup", "sigint", "sigquit", "sigterm", "sigexit",
  266.         "apid", "pid", "apid", "*", "ifs"
  267.     };
  268.  
  269.     for (i = 0; i < arraysize(notforexport); i++)
  270.         if (streq(s,notforexport[i]))
  271.             return FALSE;
  272.     return TRUE;
  273. }
  274.  
  275. char **makeenv(void) {
  276.     int ep, i;
  277.     char *v;
  278.  
  279.     if (!env_dirty)
  280.         return env;
  281.  
  282.     env_dirty = FALSE;
  283.     ep = bozosize;
  284.  
  285.     if (vsize + fsize + 1 + bozosize > envsize) {
  286.         envsize = 2 * (bozosize + vsize + fsize + 1);
  287.         env = erealloc(env, envsize * sizeof(char *));
  288.     }
  289.  
  290.     for (i = 0; i < vsize; i++) {
  291.         if (vp[i].name == NULL || !exportable(vp[i].name))
  292.             continue;
  293.         v = varlookup_string(vp[i].name);
  294.         if (v != NULL)
  295.             env[ep++] = v;
  296.     }
  297.     for (i = 0; i < fsize; i++) {
  298.         if (fp[i].name == NULL || !exportable(fp[i].name))
  299.             continue;
  300.         env[ep++] = fnlookup_string(fp[i].name);
  301.     }
  302.     env[ep] = NULL;
  303.     return env;
  304. }
  305.  
  306. void whatare_all_vars(void) {
  307.     int i;
  308.     List *s,*t;
  309.  
  310.     for (i = 0; i < vsize; i++)
  311.         if (vp[i].name != NULL && (s = varlookup(vp[i].name)) != NULL) {
  312.             fprint(1,"%s=%s", vp[i].name, (s->n == NULL ? "" : "("));
  313.             for (t = s; t->n != NULL; t = t->n)
  314.                 fprint(1,"%s ",strprint(t->w, FALSE, TRUE));
  315.             fprint(1,"%s%s\n",strprint(t->w, FALSE, TRUE), (s->n == NULL ? "" : ")"));
  316.         }
  317.     for (i = 0; i < fsize; i++)
  318.         if (fp[i].name != NULL)
  319.             fprint(1,"fn %s {%s}\n", fp[i].name, ptree(fnlookup(fp[i].name)));
  320. }
  321.  
  322. /* fake getenv() for readline() follows: */
  323.  
  324. #ifdef READLINE
  325. char *getenv(char *name) {
  326.     List *s;
  327.  
  328.     if (name == NULL || (s = varlookup(name)) == NULL)
  329.         return NULL;
  330.  
  331.     return s->w;
  332. }
  333. #endif
  334.  
  335.