![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to hash.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [CSRG BSD Unix] / 43BSDTahoe / ucb / pascal / src|
Return to hash.c CVS log | Up to [CSRG BSD Unix] / 43BSDTahoe / ucb / pascal / src |
1.1 root 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: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.