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

##### Functions

    hash              X
    inithash          X

##### Variables

    htab              X
    lastkey           X
    yykey             X

##### struct's

    ht                X

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

#### Defined functions

hash defined in line 113; used 8 times

- in line 100
- in /usr/src/ucb/pascal/pi/0.h line 615
- in /usr/src/ucb/pascal/pi/nl.c line 333
- in /usr/src/ucb/pascal/pi/pas.y line 201-204(2), 562, 605
- in /usr/src/ucb/pascal/pi/yylex.c line 104

inithash defined in line 86; used 1 times

- in /usr/src/ucb/pascal/pi/yymain.c line 59

#### Defined variables

htab defined in line 28; used 4 times

- in line 97-98(2), 147(2)

lastkey defined in line 78; used 1 times

- in line 179

yykey defined in line 35; used 5 times

- in line 78(3), 99, 179

#### Defined struct's

ht defined in line 24; used 2 times

- in line 121(2)

Last modified: 1981-07-10 Generated: 2016-12-26 | Generated by src2html V0.67 page hit count: 758 |