tagmanager/keyword.c

   1 /*
   2 *   $Id$
   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 *tableEntry = getHashTableEntry (hashedValue);
 127         hashEntry *entry = tableEntry;
 128
 129         if (entry == NULL)
 130         {
 131                 hashEntry **const table = getHashTable ();
 132                 table [hashedValue] = newEntry (string, language, value);
 133         }
 134         else
 135         {
 136                 hashEntry *prev = NULL;
 137
 138                 while (entry != NULL)
 139                 {
 140                         if (language == entry->language  &&
 141                                 strcmp (string, entry->string) == 0)
 142                         {
 143                                 Assert (("Already in table" == NULL));
 144                         }
 145                         prev = entry;
 146                         entry = entry->next;
 147                 }
 148                 if (entry == NULL)
 149                 {
 150                         Assert (prev != NULL);
 151                         prev->next = newEntry (string, language, value);
 152                 }
 153         }
 154 }
 155
 156 extern int lookupKeyword (const char *const string, langType language)
 157 {
 158         const unsigned long hashedValue = hashValue (string);
 159         hashEntry *entry = getHashTableEntry (hashedValue);
 160         int result = -1;
 161
 162         while (entry != NULL)
 163         {
 164                 if (language == entry->language  &&  strcmp (string, entry->string) == 0)
 165                 {
 166                         result = entry->value;
 167                         break;
 168                 }
 169                 entry = entry->next;
 170         }
 171         return result;
 172 }
 173
 174 extern void freeKeywordTable (void)
 175 {
 176         if (HashTable != NULL)
 177         {
 178                 unsigned int i;
 179
 180                 for (i = 0  ;  i < TableSize  ;  ++i)
 181                 {
 182                         hashEntry *entry = HashTable [i];
 183
 184                         while (entry != NULL)
 185                         {
 186                                 hashEntry *next = entry->next;
 187                                 eFree (entry);
 188                                 entry = next;
 189                         }
 190                 }
 191                 eFree (HashTable);
 192         }
 193 }
 194
 195 #ifdef DEBUG
 196
 197 static void printEntry (const hashEntry *const entry)
 198 {
 199         printf ("  %-15s %-7s\n", entry->string, getLanguageName (entry->language));
 200 }
 201
 202 static unsigned int printBucket (const unsigned int i)
 203 {
 204         hashEntry **const table = getHashTable ();
 205         hashEntry *entry = table [i];
 206         unsigned int measure = 1;
 207         boolean first = TRUE;
 208
 209         printf ("%2d:", i);
 210         if (entry == NULL)
 211                 printf ("\n");
 212         else while (entry != NULL)
 213         {
 214                 if (! first)
 215                         printf ("    ");
 216                 else
 217                 {
 218                         printf (" ");
 219                         first = FALSE;
 220                 }
 221                 printEntry (entry);
 222                 entry = entry->next;
 223                 measure = 2 * measure;
 224         }
 225         return measure - 1;
 226 }
 227
 228 extern void printKeywordTable (void)
 229 {
 230         unsigned long emptyBucketCount = 0;
 231         unsigned long measure = 0;
 232         unsigned int i;
 233
 234         for (i = 0  ;  i < TableSize  ;  ++i)
 235         {
 236                 const unsigned int pass = printBucket (i);
 237
 238                 measure += pass;
 239                 if (pass == 0)
 240                         ++emptyBucketCount;
 241         }
 242
 243         printf ("spread measure = %ld\n", measure);
 244         printf ("%ld empty buckets\n", emptyBucketCount);
 245 }
 246
 247 #endif
 248
 249 /* vi:set tabstop=4 shiftwidth=4: */