3 * Copyright (c) 1998-2001, Darren Hiebert
5 * This source code is released for free distribution under the terms of the
6 * GNU General Public License.
8 * Manages a keyword hash.
14 #include "general.h" /* must always come first */
25 #define HASH_EXPONENT 7 /* must be less than 17 */
30 typedef struct sHashEntry
{
31 struct sHashEntry
*next
;
40 static const unsigned int TableSize
= 1 << HASH_EXPONENT
;
41 static hashEntry
**HashTable
= NULL
;
44 * FUNCTION DEFINITIONS
47 static hashEntry
**getHashTable (void)
49 static boolean allocated
= FALSE
;
55 HashTable
= xMalloc (TableSize
, hashEntry
*);
57 for (i
= 0 ; i
< TableSize
; ++i
)
65 static hashEntry
*getHashTableEntry (unsigned long hashedValue
)
67 hashEntry
**const table
= getHashTable ();
70 Assert (hashedValue
< TableSize
);
71 entry
= table
[hashedValue
];
76 static unsigned long hashValue (const char *const string
)
78 unsigned long value
= 0;
79 const unsigned char *p
;
81 Assert (string
!= NULL
);
83 /* We combine the various words of the multiword key using the method
84 * described on page 512 of Vol. 3 of "The Art of Computer Programming".
86 for (p
= (const unsigned char *) string
; *p
!= '\0' ; ++p
)
89 if (value
& 0x00000100L
)
90 value
= (value
& 0x000000ffL
) + 1L;
93 /* Algorithm from page 509 of Vol. 3 of "The Art of Computer Programming"
94 * Treats "value" as a 16-bit integer plus 16-bit fraction.
96 value
*= 40503L; /* = 2^16 * 0.6180339887 ("golden ratio") */
97 value
&= 0x0000ffffL
; /* keep fractional part */
98 value
>>= 16 - HASH_EXPONENT
; /* scale up by hash size and move down */
103 static hashEntry
*newEntry (const char *const string
,
104 langType language
, int value
)
106 hashEntry
*const entry
= xMalloc (1, hashEntry
);
109 entry
->string
= string
;
110 entry
->language
= language
;
111 entry
->value
= value
;
116 /* Note that it is assumed that a "value" of zero means an undefined keyword
117 * and clients of this function should observe this. Also, all keywords added
118 * should be added in lower case. If we encounter a case-sensitive language
119 * whose keywords are in upper case, we will need to redesign this.
121 extern void addKeyword (const char *const string
, langType language
, int value
)
123 const unsigned long hashedValue
= hashValue (string
);
124 hashEntry
*tableEntry
= getHashTableEntry (hashedValue
);
125 hashEntry
*entry
= tableEntry
;
128 fprintf(stderr
, "Adding keyword %s to language %d\n", string
, language
);
132 hashEntry
**const table
= getHashTable ();
133 hashEntry
*new = newEntry (string
, language
, value
);
135 table
[hashedValue
] = new;
139 hashEntry
*prev
= NULL
;
141 while (entry
!= NULL
)
143 if (language
== entry
->language
&&
144 strcmp (string
, entry
->string
) == 0)
146 Assert (("Already in table" == NULL
));
153 hashEntry
*new = newEntry (string
, language
, value
);
155 Assert (prev
!= NULL
);
161 extern int lookupKeyword (const char *const string
, langType language
)
163 const unsigned long hashedValue
= hashValue (string
);
164 hashEntry
*entry
= getHashTableEntry (hashedValue
);
167 while (entry
!= NULL
)
169 if (language
== entry
->language
&& strcmp (string
, entry
->string
) == 0)
171 value
= entry
->value
;
179 extern void freeKeywordTable (void)
181 if (HashTable
!= NULL
)
185 for (i
= 0 ; i
< TableSize
; ++i
)
187 hashEntry
*entry
= HashTable
[i
];
189 while (entry
!= NULL
)
191 hashEntry
*next
= entry
->next
;
202 static void printEntry (const hashEntry
*const entry
)
204 printf (" %-15s %-7s\n", entry
->string
, getLanguageName (entry
->language
));
207 static unsigned int printBucket (const unsigned int i
)
209 hashEntry
**const table
= getHashTable ();
210 hashEntry
*entry
= table
[i
];
211 unsigned int measure
= 1;
212 boolean first
= TRUE
;
217 else while (entry
!= NULL
)
228 measure
= 2 * measure
;
233 extern void printKeywordTable (void)
235 unsigned long emptyBucketCount
= 0;
236 unsigned long measure
= 0;
239 for (i
= 0 ; i
< TableSize
; ++i
)
241 const unsigned int pass
= printBucket (i
);
248 printf ("spread measure = %ld\n", measure
);
249 printf ("%ld empty buckets\n", emptyBucketCount
);
254 /* vi:set tabstop=8 shiftwidth=4: */