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

##### Functions

    hash              X
    inithash          X

##### Variables

    htab              X
    lastkey           X
    yykey             X

##### struct's

    ht                X

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

#### Defined functions

hash defined in line 117; used 9 times

- in line 96, 103
- in /usr/src/ucb/PORT/pascal/src/0.h line 712
- in /usr/src/ucb/PORT/pascal/src/nl.c line 408
- in /usr/src/ucb/PORT/pascal/src/pas.y line 207-211(2), 584, 637
- in /usr/src/ucb/PORT/pascal/src/yylex.c line 99

inithash defined in line 82; used 1 times

- in /usr/src/ucb/PORT/pascal/src/yymain.c line 61

#### Defined variables

htab defined in line 23; used 4 times

- in line 93-94(2), 152(2)

lastkey defined in line 74; used 2 times

- in line 104, 184

sccsid defined in line 8; never used
yykey defined in line 30; used 2 times

- in line 95, 184

#### Defined struct's

ht defined in line 19; used 2 times

- in line 126(2)

Last modified: 1985-06-05 Generated: 2016-12-26 | Generated by src2html V0.67 page hit count: 771 |