home *** CD-ROM | disk | FTP | other *** search
/ minnie.tuhs.org / unixen.tar / unixen / PDP-11 / Distributions / ucb / spencer_2bsd.tar.gz / 2bsd.tar / src / pi0 / hash.c < prev    next >
C/C++ Source or Header  |  1980-02-17  |  4KB  |  190 lines
  1. /* Copyright (c) 1979 Regents of the University of California */
  2. #
  3. /*
  4.  * pi - Pascal interpreter code translator
  5.  *
  6.  * Charles Haley, Bill Joy UCB
  7.  * Version 1.2 January 1979
  8.  *
  9.  *
  10.  * pxp - Pascal execution profiler
  11.  *
  12.  * Bill Joy UCB
  13.  * Version 1.2 January 1979
  14.  */
  15.  
  16. #include "0.h"
  17. #include "yy.h"
  18.  
  19. /*
  20.  * The definition for the segmented hash tables.
  21.  */
  22. struct ht {
  23.     int    *ht_low;
  24.     int    *ht_high;
  25.     int    ht_used;
  26. } htab[MAXHASH];
  27.  
  28. /*
  29.  * This is the array of keywords and their
  30.  * token values, which are hashed into the table
  31.  * by inithash.
  32.  */
  33. struct kwtab yykey[] {
  34.     "and",        YAND,
  35.     "array",    YARRAY,
  36.     "assert",    YASSERT,
  37.     "begin",    YBEGIN,
  38.     "case",        YCASE,
  39.     "const",    YCONST,
  40.     "div",        YDIV,
  41.     "do",        YDO,
  42.     "downto",    YDOWNTO,
  43.     "else",        YELSE,
  44.     "end",        YEND,
  45.     "file",        YFILE,
  46.     "for",        YFOR,
  47.     "forward",    YFORWARD,
  48.     "function",    YFUNCTION,
  49.     "goto",        YGOTO,
  50.     "if",        YIF,
  51.     "in",        YIN,
  52.     "label",    YLABEL,
  53.     "mod",        YMOD,
  54.     "nil",        YNIL,
  55.     "not",        YNOT,
  56.     "of",        YOF,
  57.     "or",        YOR,
  58.     "packed",    YPACKED,
  59.     "procedure",    YPROCEDURE,
  60.     "program",    YPROG,
  61.     "record",    YRECORD,
  62.     "repeat",    YREPEAT,
  63.     "set",        YSET,
  64.     "then",        YTHEN,
  65.     "to",        YTO,
  66.     "type",        YTYPE,
  67.     "until",    YUNTIL,
  68.     "var",        YVAR,
  69.     "while",    YWHILE,
  70.     "with",        YWITH,
  71.     "oct",        YOCT,     /* non-standard Pascal */
  72.     "hex",        YHEX,     /* non-standard Pascal */
  73.     0
  74. };
  75.  
  76. char    *lastkey    &yykey[sizeof yykey/sizeof yykey[0]];
  77.  
  78. /*
  79.  * Inithash initializes the hash table routines
  80.  * by allocating the first hash table segment using
  81.  * an already existing memory slot.
  82.  */
  83. #ifndef PI0
  84. inithash()
  85. #else
  86. inithash(hshtab)
  87.     int *hshtab;
  88. #endif
  89. {
  90.     register int *ip;
  91. #ifndef PI0
  92.     static int hshtab[HASHINC];
  93. #endif
  94.  
  95.     htab[0].ht_low = hshtab;
  96.     htab[0].ht_high = &hshtab[HASHINC];
  97.     for (ip = yykey; *ip; ip =+ 2)
  98.         hash(ip[0], 0)[0] = ip;
  99. }
  100.  
  101. /*
  102.  * Hash looks up the s(ymbol) argument
  103.  * in the string table, entering it if
  104.  * it is not found. If save is 0, then
  105.  * the argument string is already in
  106.  * a safe place. Otherwise, if hash is
  107.  * entering the symbol for the first time
  108.  * it will save the symbol in the string
  109.  * table using savestr.
  110.  */
  111. int *hash(s, save)
  112.     char *s;
  113.     int save;
  114. {
  115.     register int *h;
  116.     register i;
  117.     register char *cp;
  118.     int *sym;
  119.     struct ht *htp;
  120.     int sh;
  121.  
  122.     /*
  123.      * The hash function is a modular hash of
  124.      * the sum of the characters with the sum
  125.      * doubled before each successive character
  126.      * is added.
  127.      */
  128.     cp = s;
  129.     if (cp == NIL)
  130.         cp = token;    /* default symbol to be hashed */
  131.     i = 0;
  132.     while (*cp)
  133.         i = i*2 + *cp++;
  134.     sh = (i&077777) % HASHINC;
  135.     cp = s;
  136.     if (cp == NIL)
  137.         cp = token;
  138.     /*
  139.      * There are as many as MAXHASH active
  140.      * hash tables at any given point in time.
  141.      * The search starts with the first table
  142.      * and continues through the active tables
  143.      * as necessary.
  144.      */
  145.     for (htp = htab; htp < &htab[MAXHASH]; htp++) {
  146.         if (htp->ht_low == NIL) {
  147.             cp = calloc(2, HASHINC);
  148.             if (cp == -1) {
  149.                 yerror("Ran out of memory (hash)");
  150.                 pexit(DIED);
  151.             }
  152.             htp->ht_low = cp;
  153.             htp->ht_high = htp->ht_low + HASHINC;
  154.             cp = s;
  155.             if (cp == NIL)
  156.                 cp = token;
  157.         }
  158.         h = htp->ht_low + sh;
  159.         /*
  160.          * quadratic rehash increment
  161.          * starts at 1 and incremented
  162.          * by two each rehash.
  163.          */
  164.         i = 1;
  165.         do {
  166.             if (*h == 0) {
  167.                 if (htp->ht_used > (HASHINC * 3)/4)
  168.                     break;
  169.                 htp->ht_used++;
  170.                 if (save != 0) {
  171.                     *h = savestr(cp);
  172.                 } else
  173.                     *h = s;
  174.                 return (h);
  175.             }
  176.             sym = *h;
  177.             if (sym < lastkey && sym >= yykey)
  178.                 sym = *sym;
  179.             if (sym->pchar == *cp && strcmp(sym, cp) == 0)
  180.                 return (h);
  181.             h =+ i;
  182.             i =+ 2;
  183.             if (h >= htp->ht_high)
  184.                 h =- HASHINC;
  185.         } while (i < HASHINC);
  186.     }
  187.     yerror("Ran out of hash tables");
  188.     pexit(DIED);
  189. }
  190.