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