![[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] / 41BSD / cmd / pc0|
Return to hash.c CVS log | Up to [CSRG BSD Unix] / 41BSD / cmd / pc0 |
1.1 root 1: /* Copyright (c) 1979 Regents of the University of California */
2:
3: static char sccsid[] = "@(#)hash.c 1.1 8/27/80";
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: "assert", YASSERT,
27: "begin", YBEGIN,
28: "case", YCASE,
29: "const", YCONST,
30: "div", YDIV,
31: "do", YDO,
32: "downto", YDOWNTO,
33: "else", YELSE,
34: "end", YEND,
35: "file", YFILE,
36: "for", YFOR,
37: "forward", YFORWARD,
38: "function", YFUNCTION,
39: "goto", YGOTO,
40: "if", YIF,
41: "in", YIN,
42: "label", YLABEL,
43: "mod", YMOD,
44: "nil", YNIL,
45: "not", YNOT,
46: "of", YOF,
47: "or", YOR,
48: "packed", YPACKED,
49: "procedure", YPROCEDURE,
50: "program", YPROG,
51: "record", YRECORD,
52: "repeat", YREPEAT,
53: "set", YSET,
54: "then", YTHEN,
55: "to", YTO,
56: "type", YTYPE,
57: "until", YUNTIL,
58: "var", YVAR,
59: "while", YWHILE,
60: "with", YWITH,
61: "oct", YOCT, /* non-standard Pascal */
62: "hex", YHEX, /* non-standard Pascal */
63: "external", YEXTERN, /* non-standard Pascal */
64: 0
65: };
66:
67: char *lastkey = &yykey[sizeof yykey/sizeof yykey[0]];
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:
92: /*
93: * Hash looks up the s(ymbol) argument
94: * in the string table, entering it if
95: * it is not found. If save is 0, then
96: * the argument string is already in
97: * a safe place. Otherwise, if hash is
98: * entering the symbol for the first time
99: * it will save the symbol in the string
100: * table using savestr.
101: */
102: int *hash(s, save)
103: char *s;
104: int save;
105: {
106: register int *h;
107: register i;
108: register char *cp;
109: int *sym;
110: struct ht *htp;
111: int sh;
112:
113: /*
114: * The hash function is a modular hash of
115: * the sum of the characters with the sum
116: * doubled before each successive character
117: * is added.
118: */
119: cp = s;
120: if (cp == NIL)
121: cp = token; /* default symbol to be hashed */
122: i = 0;
123: while (*cp)
124: i = i*2 + *cp++;
125: sh = (i&077777) % HASHINC;
126: cp = s;
127: if (cp == NIL)
128: cp = token;
129: /*
130: * There are as many as MAXHASH active
131: * hash tables at any given point in time.
132: * The search starts with the first table
133: * and continues through the active tables
134: * as necessary.
135: */
136: for (htp = htab; htp < &htab[MAXHASH]; htp++) {
137: if (htp->ht_low == NIL) {
138: cp = (char *) calloc(sizeof ( int * ), HASHINC);
139: if (cp == -1) {
140: yerror("Ran out of memory (hash)");
141: pexit(DIED);
142: }
143: htp->ht_low = cp;
144: htp->ht_high = htp->ht_low + HASHINC;
145: cp = s;
146: if (cp == NIL)
147: cp = token;
148: }
149: h = htp->ht_low + sh;
150: /*
151: * quadratic rehash increment
152: * starts at 1 and incremented
153: * by two each rehash.
154: */
155: i = 1;
156: do {
157: if (*h == 0) {
158: if (htp->ht_used > (HASHINC * 3)/4)
159: break;
160: htp->ht_used++;
161: if (save != 0) {
162: *h = (int) savestr(cp);
163: } else
164: *h = s;
165: return (h);
166: }
167: sym = *h;
168: if (sym < lastkey && sym >= yykey)
169: sym = *sym;
170: if (sym->pchar == *cp && strcmp(sym, cp) == 0)
171: return (h);
172: h += i;
173: i += 2;
174: if (h >= htp->ht_high)
175: h -= HASHINC;
176: } while (i < HASHINC);
177: }
178: yerror("Ran out of hash tables");
179: pexit(DIED);
180: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.