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