1 /*
2 * $Id: keyword.c 715 2009-07-06 03:31:00Z dhiebert $
3 *
4 * Copyright (c) 1998-2002, Darren Hiebert
5 *
6 * This source code is released for free distribution under the terms of the
7 * GNU General Public License.
8 *
9 * Manages a keyword hash.
10 */
11
12 /*
13 * INCLUDE FILES
14 */
15 #include "general.h" /* must always come first */
16
17 #include <string.h>
18
19 #include "debug.h"
20 #include "keyword.h"
21 #include "options.h"
22 #include "routines.h"
23
24 /*
25 * MACROS
26 */
27 #define HASH_EXPONENT 7 /* must be less than 17 */
28
29 /*
30 * DATA DECLARATIONS
31 */
32 typedef struct sHashEntry {
33 struct sHashEntry *next;
34 const char *string;
35 langType language;
36 int value;
37 } hashEntry;
38
39 /*
40 * DATA DEFINITIONS
41 */
42 static const unsigned int TableSize = 1 << HASH_EXPONENT;
43 static hashEntry **HashTable = NULL;
44
45 /*
46 * FUNCTION DEFINITIONS
47 */
48
getHashTable(void)49 static hashEntry **getHashTable (void)
50 {
51 static boolean allocated = FALSE;
52
53 if (! allocated)
54 {
55 unsigned int i;
56
57 HashTable = xMalloc (TableSize, hashEntry*);
58
59 for (i = 0 ; i < TableSize ; ++i)
60 HashTable [i] = NULL;
61
62 allocated = TRUE;
63 }
64 return HashTable;
65 }
66
getHashTableEntry(unsigned long hashedValue)67 static hashEntry *getHashTableEntry (unsigned long hashedValue)
68 {
69 hashEntry **const table = getHashTable ();
70 hashEntry *entry;
71
72 Assert (hashedValue < TableSize);
73 entry = table [hashedValue];
74
75 return entry;
76 }
77
hashValue(const char * const string)78 static unsigned long hashValue (const char *const string)
79 {
80 unsigned long value = 0;
81 const unsigned char *p;
82
83 Assert (string != NULL);
84
85 /* We combine the various words of the multiword key using the method
86 * described on page 512 of Vol. 3 of "The Art of Computer Programming".
87 */
88 for (p = (const unsigned char *) string ; *p != '\0' ; ++p)
89 {
90 value <<= 1;
91 if (value & 0x00000100L)
92 value = (value & 0x000000ffL) + 1L;
93 value ^= *p;
94 }
95 /* Algorithm from page 509 of Vol. 3 of "The Art of Computer Programming"
96 * Treats "value" as a 16-bit integer plus 16-bit fraction.
97 */
98 value *= 40503L; /* = 2^16 * 0.6180339887 ("golden ratio") */
99 value &= 0x0000ffffL; /* keep fractional part */
100 value >>= 16 - HASH_EXPONENT; /* scale up by hash size and move down */
101
102 return value;
103 }
104
newEntry(const char * const string,langType language,int value)105 static hashEntry *newEntry (
106 const char *const string, langType language, int value)
107 {
108 hashEntry *const entry = xMalloc (1, hashEntry);
109
110 entry->next = NULL;
111 entry->string = string;
112 entry->language = language;
113 entry->value = value;
114
115 return entry;
116 }
117
118 /* Note that it is assumed that a "value" of zero means an undefined keyword
119 * and clients of this function should observe this. Also, all keywords added
120 * should be added in lower case. If we encounter a case-sensitive language
121 * whose keywords are in upper case, we will need to redesign this.
122 */
addKeyword(const char * const string,langType language,int value)123 extern void addKeyword (const char *const string, langType language, int value)
124 {
125 const unsigned long hashedValue = hashValue (string);
126 hashEntry *entry = getHashTableEntry (hashedValue);
127
128 if (entry == NULL)
129 {
130 hashEntry **const table = getHashTable ();
131 table [hashedValue] = newEntry (string, language, value);
132 }
133 else
134 {
135 hashEntry *prev = NULL;
136
137 while (entry != NULL)
138 {
139 if (language == entry->language &&
140 strcmp (string, entry->string) == 0)
141 {
142 Assert (("Already in table" == NULL));
143 }
144 prev = entry;
145 entry = entry->next;
146 }
147 if (entry == NULL)
148 {
149 Assert (prev != NULL);
150 prev->next = newEntry (string, language, value);
151 }
152 }
153 }
154
lookupKeyword(const char * const string,langType language)155 extern int lookupKeyword (const char *const string, langType language)
156 {
157 const unsigned long hashedValue = hashValue (string);
158 hashEntry *entry = getHashTableEntry (hashedValue);
159 int result = -1;
160
161 while (entry != NULL)
162 {
163 if (language == entry->language && strcmp (string, entry->string) == 0)
164 {
165 result = entry->value;
166 break;
167 }
168 entry = entry->next;
169 }
170 return result;
171 }
172
freeKeywordTable(void)173 extern void freeKeywordTable (void)
174 {
175 if (HashTable != NULL)
176 {
177 unsigned int i;
178
179 for (i = 0 ; i < TableSize ; ++i)
180 {
181 hashEntry *entry = HashTable [i];
182
183 while (entry != NULL)
184 {
185 hashEntry *next = entry->next;
186 eFree (entry);
187 entry = next;
188 }
189 }
190 eFree (HashTable);
191 }
192 }
193
analyzeToken(vString * const name,langType language)194 extern int analyzeToken (vString *const name, langType language)
195 {
196 vString *keyword = vStringNew ();
197 int result;
198 vStringCopyToLower (keyword, name);
199 result = lookupKeyword (vStringValue (keyword), language);
200 vStringDelete (keyword);
201 return result;
202 }
203
204 #ifdef DEBUG
205
printEntry(const hashEntry * const entry)206 static void printEntry (const hashEntry *const entry)
207 {
208 printf (" %-15s %-7s\n", entry->string, getLanguageName (entry->language));
209 }
210
printBucket(const unsigned int i)211 static unsigned int printBucket (const unsigned int i)
212 {
213 hashEntry **const table = getHashTable ();
214 hashEntry *entry = table [i];
215 unsigned int measure = 1;
216 boolean first = TRUE;
217
218 printf ("%2d:", i);
219 if (entry == NULL)
220 printf ("\n");
221 else while (entry != NULL)
222 {
223 if (! first)
224 printf (" ");
225 else
226 {
227 printf (" ");
228 first = FALSE;
229 }
230 printEntry (entry);
231 entry = entry->next;
232 measure = 2 * measure;
233 }
234 return measure - 1;
235 }
236
printKeywordTable(void)237 extern void printKeywordTable (void)
238 {
239 unsigned long emptyBucketCount = 0;
240 unsigned long measure = 0;
241 unsigned int i;
242
243 for (i = 0 ; i < TableSize ; ++i)
244 {
245 const unsigned int pass = printBucket (i);
246
247 measure += pass;
248 if (pass == 0)
249 ++emptyBucketCount;
250 }
251
252 printf ("spread measure = %ld\n", measure);
253 printf ("%ld empty buckets\n", emptyBucketCount);
254 }
255
256 #endif
257
258 /* vi:set tabstop=4 shiftwidth=4: */
259