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