# 2.11BSD#431 - /usr/src/ucb/pascal/pxp/hash.c

##### Functions

    hash              X
    inithash          X

##### Variables

    htab              X
    lastkey           X
    yykey             X

##### struct's

    ht                X

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

#### Defined functions

hash defined in line 110; used 8 times

- in line 97
- in /usr/src/ucb/pascal/pxp/0.h line 220
- in /usr/src/ucb/pascal/pxp/nl.c line 313
- in /usr/src/ucb/pascal/pxp/pas.y line 194-197(2), 555, 598
- in /usr/src/ucb/pascal/pxp/yylex.c line 101

inithash defined in line 83; used 1 times

- in /usr/src/ucb/pascal/pxp/yymain.c line 55

#### Defined variables

htab defined in line 25; used 4 times

- in line 94-95(2), 144(2)

lastkey defined in line 75; used 1 times

- in line 176

yykey defined in line 32; used 5 times

- in line 75(3), 96, 176

#### Defined struct's

ht defined in line 21; used 2 times

- in line 118(2)

Last modified: 1986-06-01 Generated: 2016-12-26 | Generated by src2html V0.67 page hit count: 692 |