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