| 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 January 1979 |
| 8 | * |
| 9 | * |
| 10 | * pxp - Pascal execution profiler |
| 11 | * |
| 12 | * Bill Joy UCB |
| 13 | * Version 1.2 January 1979 |
| 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 = calloc(2, 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 = 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 | } |