tagmanager/keyword.c

   1 /*
   2 *
   3 *   Copyright (c) 1998-2001, Darren Hiebert
   4 *
   5 *   This source code is released for free distribution under the terms of the
   6 *   GNU General Public License.
   7 *
   8 *   Manages a keyword hash.
   9 */
  10
  11 /*
  12 *   INCLUDE FILES
  13 */
  14 #include "general.h"    /* must always come first */
  15
  16 #include <string.h>
  17
  18 #include "keyword.h"
  19 #include "main.h"
  20 #include "options.h"
  21
  22 /*
  23 *   MACROS
  24 */
  25 #define HASH_EXPONENT   7       /* must be less than 17 */
  26
  27 /*
  28 *   DATA DECLARATIONS
  29 */
  30 typedef struct sHashEntry {
  31     struct sHashEntry *next;
  32     const char *string;
  33     langType language;
  34     int value;
  35 } hashEntry;
  36
  37 /*
  38 *   DATA DEFINITIONS
  39 */
  40 static const unsigned int TableSize = 1 << HASH_EXPONENT;
  41 static hashEntry **HashTable = NULL;
  42
  43 /*
  44 *   FUNCTION DEFINITIONS
  45 */
  46
  47 static hashEntry **getHashTable (void)
  48 {
  49     static boolean allocated = FALSE;
  50
  51     if (! allocated)
  52     {
  53         unsigned int i;
  54
  55         HashTable = xMalloc (TableSize, hashEntry*);
  56
  57         for (i = 0  ;  i < TableSize  ;  ++i)
  58             HashTable [i] = NULL;
  59
  60         allocated = TRUE;
  61     }
  62     return HashTable;
  63 }
  64
  65 static hashEntry *getHashTableEntry (unsigned long hashedValue)
  66 {
  67     hashEntry **const table = getHashTable ();
  68     hashEntry *entry;
  69
  70     Assert (hashedValue < TableSize);
  71     entry = table [hashedValue];
  72
  73     return entry;
  74 }
  75
  76 static unsigned long hashValue (const char *const string)
  77 {
  78     unsigned long value = 0;
  79     const unsigned char *p;
  80
  81     Assert (string != NULL);
  82
  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".
  85      */
  86     for (p = (const unsigned char *) string  ;  *p != '\0'  ;  ++p)
  87     {
  88         value <<= 1;
  89         if (value & 0x00000100L)
  90             value = (value & 0x000000ffL) + 1L;
  91         value ^= *p;
  92     }
  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.
  95      */
  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 */
  99
 100     return value;
 101 }
 102
 103 static hashEntry *newEntry (const char *const string,
 104                             langType language, int value)
 105 {
 106     hashEntry *const entry = xMalloc (1, hashEntry);
 107
 108     entry->next     = NULL;
 109     entry->string   = string;
 110     entry->language = language;
 111     entry->value    = value;
 112
 113     return entry;
 114 }
 115
 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.
 120  */
 121 extern void addKeyword (const char *const string, langType language, int value)
 122 {
 123     const unsigned long hashedValue = hashValue (string);
 124     hashEntry *tableEntry = getHashTableEntry (hashedValue);
 125     hashEntry *entry = tableEntry;
 126
 127 #ifdef TM_DEBUG
 128     fprintf(stderr, "Adding keyword %s to language %d\n", string, language);
 129 #endif
 130     if (entry == NULL)
 131     {
 132         hashEntry **const table = getHashTable ();
 133         hashEntry *new = newEntry (string, language, value);
 134
 135         table [hashedValue] = new;
 136     }
 137     else
 138     {
 139         hashEntry *prev = NULL;
 140
 141         while (entry != NULL)
 142         {
 143             if (language == entry->language  &&
 144                 strcmp (string, entry->string) == 0)
 145             {
 146                 Assert (("Already in table" == NULL));
 147             }
 148             prev = entry;
 149             entry = entry->next;
 150         }
 151         if (entry == NULL)
 152         {
 153             hashEntry *new = newEntry (string, language, value);
 154
 155             Assert (prev != NULL);
 156             prev->next = new;
 157         }
 158     }
 159 }
 160
 161 extern int lookupKeyword (const char *const string, langType language)
 162 {
 163     const unsigned long hashedValue = hashValue (string);
 164     hashEntry *entry = getHashTableEntry (hashedValue);
 165     int value = -1;
 166
 167     while (entry != NULL)
 168     {
 169         if (language == entry->language  &&  strcmp (string, entry->string) == 0)
 170         {
 171             value = entry->value;
 172             break;
 173         }
 174         entry = entry->next;
 175     }
 176     return value;
 177 }
 178
 179 extern void freeKeywordTable (void)
 180 {
 181     if (HashTable != NULL)
 182     {
 183         unsigned int i;
 184
 185         for (i = 0  ;  i < TableSize  ;  ++i)
 186         {
 187             hashEntry *entry = HashTable [i];
 188
 189             while (entry != NULL)
 190             {
 191                 hashEntry *next = entry->next;
 192                 eFree (entry);
 193                 entry = next;
 194             }
 195         }
 196         eFree (HashTable);
 197     }
 198 }
 199
 200 #ifdef TM_DEBUG
 201
 202 static void printEntry (const hashEntry *const entry)
 203 {
 204     printf ("  %-15s %-7s\n", entry->string, getLanguageName (entry->language));
 205 }
 206
 207 static unsigned int printBucket (const unsigned int i)
 208 {
 209     hashEntry **const table = getHashTable ();
 210     hashEntry *entry = table [i];
 211     unsigned int measure = 1;
 212     boolean first = TRUE;
 213
 214     printf ("%2d:", i);
 215     if (entry == NULL)
 216         printf ("\n");
 217     else while (entry != NULL)
 218     {
 219         if (! first)
 220             printf ("    ");
 221         else
 222         {
 223             printf (" ");
 224             first = FALSE;
 225         }
 226         printEntry (entry);
 227         entry = entry->next;
 228         measure = 2 * measure;
 229     }
 230     return measure - 1;
 231 }
 232
 233 extern void printKeywordTable (void)
 234 {
 235     unsigned long emptyBucketCount = 0;
 236     unsigned long measure = 0;
 237     unsigned int i;
 238
 239     for (i = 0  ;  i < TableSize  ;  ++i)
 240     {
 241         const unsigned int pass = printBucket (i);
 242
 243         measure += pass;
 244         if (pass == 0)
 245             ++emptyBucketCount;
 246     }
 247
 248     printf ("spread measure = %ld\n", measure);
 249     printf ("%ld empty buckets\n", emptyBucketCount);
 250 }
 251
 252 #endif
 253
 254 /* vi:set tabstop=8 shiftwidth=4: */