xref: /csrg-svn/usr.bin/pascal/src/hash.c (revision 14733)
1755Speter /* Copyright (c) 1979 Regents of the University of California */
2755Speter 
3*14733Sthien #ifndef lint
4*14733Sthien static	char sccsid[] = "@(#)hash.c 1.5 08/19/83";
5*14733Sthien #endif
6755Speter 
7755Speter #include "whoami.h"
8755Speter #include "0.h"
9*14733Sthien #include "tree_ty.h"		/* must be included for yy.h */
10755Speter #include "yy.h"
11755Speter 
12755Speter /*
13755Speter  * The definition for the segmented hash tables.
14755Speter  */
15755Speter struct ht {
16755Speter 	int	*ht_low;
17755Speter 	int	*ht_high;
18755Speter 	int	ht_used;
19755Speter } htab[MAXHASH];
20755Speter 
21755Speter /*
22755Speter  * This is the array of keywords and their
23755Speter  * token values, which are hashed into the table
24755Speter  * by inithash.
25755Speter  */
26755Speter struct kwtab yykey[] = {
27755Speter 	"and",		YAND,
28755Speter 	"array",	YARRAY,
29755Speter 	"begin",	YBEGIN,
30755Speter 	"case",		YCASE,
31755Speter 	"const",	YCONST,
32755Speter 	"div",		YDIV,
33755Speter 	"do",		YDO,
34755Speter 	"downto",	YDOWNTO,
35755Speter 	"else",		YELSE,
36755Speter 	"end",		YEND,
37755Speter 	"file",		YFILE,
38755Speter 	"for",		YFOR,
39755Speter 	"forward",	YFORWARD,
40755Speter 	"function",	YFUNCTION,
41755Speter 	"goto",		YGOTO,
42755Speter 	"if",		YIF,
43755Speter 	"in",		YIN,
44755Speter 	"label",	YLABEL,
45755Speter 	"mod",		YMOD,
46755Speter 	"nil",		YNIL,
47755Speter 	"not",		YNOT,
48755Speter 	"of",		YOF,
49755Speter 	"or",		YOR,
50755Speter 	"packed",	YPACKED,
51755Speter 	"procedure",	YPROCEDURE,
52755Speter 	"program",	YPROG,
53755Speter 	"record",	YRECORD,
54755Speter 	"repeat",	YREPEAT,
55755Speter 	"set",		YSET,
56755Speter 	"then",		YTHEN,
57755Speter 	"to",		YTO,
58755Speter 	"type",		YTYPE,
59755Speter 	"until",	YUNTIL,
60755Speter 	"var",		YVAR,
61755Speter 	"while",	YWHILE,
62755Speter 	"with",		YWITH,
637955Smckusick 	0,		0,	 /* the following keywords are non-standard */
647955Smckusick 	"oct",		YOCT,
657955Smckusick 	"hex",		YHEX,
667955Smckusick 	"external",	YEXTERN,
67755Speter 	0
68755Speter };
69755Speter 
707955Smckusick char *lastkey;
71755Speter 
72755Speter /*
73755Speter  * Inithash initializes the hash table routines
74755Speter  * by allocating the first hash table segment using
75755Speter  * an already existing memory slot.
76755Speter  */
77755Speter #ifndef PI0
78755Speter inithash()
79755Speter #else
80755Speter inithash(hshtab)
81755Speter 	int *hshtab;
82755Speter #endif
83755Speter {
84755Speter 	register int *ip;
85755Speter #ifndef PI0
86755Speter 	static int hshtab[HASHINC];
87755Speter #endif
88755Speter 
89755Speter 	htab[0].ht_low = hshtab;
90755Speter 	htab[0].ht_high = &hshtab[HASHINC];
91*14733Sthien 	for (ip = ((int *)yykey); *ip; ip += 2)
92*14733Sthien 		hash((char *) ip[0], 0)[0] = ((int) ip);
937955Smckusick 	/*
947955Smckusick 	 * If we are not running in "standard-only" mode,
957955Smckusick 	 * we load the non-standard keywords.
967955Smckusick 	 */
977955Smckusick 	if (!opt('s'))
987955Smckusick 		for (ip += 2; *ip; ip += 2)
99*14733Sthien 			hash((char *) ip[0], 0)[0] = ((int) ip);
1007955Smckusick 	lastkey = (char *)ip;
101755Speter }
102755Speter 
103755Speter /*
104755Speter  * Hash looks up the s(ymbol) argument
105755Speter  * in the string table, entering it if
106755Speter  * it is not found. If save is 0, then
107755Speter  * the argument string is already in
108755Speter  * a safe place. Otherwise, if hash is
109755Speter  * entering the symbol for the first time
110755Speter  * it will save the symbol in the string
111755Speter  * table using savestr.
112755Speter  */
113755Speter int *hash(s, save)
114755Speter 	char *s;
115755Speter 	int save;
116755Speter {
117755Speter 	register int *h;
118755Speter 	register i;
119755Speter 	register char *cp;
120755Speter 	int *sym;
121*14733Sthien 	struct cstruct *temp;
122755Speter 	struct ht *htp;
123755Speter 	int sh;
124755Speter 
125755Speter 	/*
126755Speter 	 * The hash function is a modular hash of
127755Speter 	 * the sum of the characters with the sum
128755Speter 	 * doubled before each successive character
129755Speter 	 * is added.
130755Speter 	 */
131755Speter 	cp = s;
132755Speter 	if (cp == NIL)
133755Speter 		cp = token;	/* default symbol to be hashed */
134755Speter 	i = 0;
135755Speter 	while (*cp)
136755Speter 		i = i*2 + *cp++;
137755Speter 	sh = (i&077777) % HASHINC;
138755Speter 	cp = s;
139755Speter 	if (cp == NIL)
140755Speter 		cp = token;
141755Speter 	/*
142755Speter 	 * There are as many as MAXHASH active
143755Speter 	 * hash tables at any given point in time.
144755Speter 	 * The search starts with the first table
145755Speter 	 * and continues through the active tables
146755Speter 	 * as necessary.
147755Speter 	 */
148755Speter 	for (htp = htab; htp < &htab[MAXHASH]; htp++) {
149755Speter 		if (htp->ht_low == NIL) {
150*14733Sthien 			cp = (char *) pcalloc(sizeof ( int * ), HASHINC);
1511833Speter 			if (cp == 0) {
152755Speter 				yerror("Ran out of memory (hash)");
153755Speter 				pexit(DIED);
154755Speter 			}
155*14733Sthien 			htp->ht_low = ((int *)cp);
156755Speter 			htp->ht_high = htp->ht_low + HASHINC;
157755Speter 			cp = s;
158755Speter 			if (cp == NIL)
159755Speter 				cp = token;
160755Speter 		}
161755Speter 		h = htp->ht_low + sh;
162755Speter 		/*
163755Speter 		 * quadratic rehash increment
164755Speter 		 * starts at 1 and incremented
165755Speter 		 * by two each rehash.
166755Speter 		 */
167755Speter 		i = 1;
168755Speter 		do {
169755Speter 			if (*h == 0) {
170755Speter 				if (htp->ht_used > (HASHINC * 3)/4)
171755Speter 					break;
172755Speter 				htp->ht_used++;
173755Speter 				if (save != 0) {
174755Speter 					*h = (int) savestr(cp);
175755Speter 				} else
176*14733Sthien 					*h = ((int) s);
177755Speter 				return (h);
178755Speter 			}
179*14733Sthien 			sym = ((int *) *h);
180*14733Sthien 			if (sym < ((int *) lastkey) && sym >= ((int *) yykey))
181*14733Sthien 				sym = ((int *) *sym);
182*14733Sthien 			temp = ((struct cstruct *) sym);
183*14733Sthien 			if (temp->pchar == *cp && pstrcmp((char *) sym, cp) == 0)
184755Speter 				return (h);
185755Speter 			h += i;
186755Speter 			i += 2;
187755Speter 			if (h >= htp->ht_high)
188755Speter 				h -= HASHINC;
189755Speter 		} while (i < HASHINC);
190755Speter 	}
191755Speter 	yerror("Ran out of hash tables");
192755Speter 	pexit(DIED);
193*14733Sthien 	return (NIL);
194*14733Sthien 
195755Speter }
196