keyword.c

   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
  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
  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
  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
 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  */
 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
 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
 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
 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
 206 static void printEntry (const hashEntry *const entry)
 207 {
 208         printf ("  %-15s %-7s\n", entry->string, getLanguageName (entry->language));
 209 }
 210
 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
 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: */