ctags/main/keyword.c

   1 /*
   2 *   Copyright (c) 1998-2002, Darren Hiebert
   3 *
   4 *   This source code is released for free distribution under the terms of the
   5 *   GNU General Public License version 2 or (at your option) any later version.
   6 *
   7 *   Manages a keyword hash.
   8 */
   9
  10 /*
  11 *   INCLUDE FILES
  12 */
  13 #include "general.h"  /* must always come first */
  14
  15 #include <string.h>
  16 #include <ctype.h>
  17
  18 #include "debug.h"
  19 #include "keyword.h"
  20 #include "options.h"
  21 #include "routines.h"
  22
  23 /*
  24 *   DATA DECLARATIONS
  25 */
  26 typedef struct sHashEntry {
  27         struct sHashEntry *next;
  28         const char *string;
  29         langType language;
  30         int value;
  31 } hashEntry;
  32
  33 /*
  34 *   DATA DEFINITIONS
  35 */
  36 static const unsigned int TableSize = 2039;  /* prime */
  37 static hashEntry **HashTable = NULL;
  38
  39 /*
  40 *   FUNCTION DEFINITIONS
  41 */
  42
  43 static hashEntry **getHashTable (void)
  44 {
  45         static bool allocated = false;
  46
  47         if (! allocated)
  48         {
  49                 unsigned int i;
  50
  51                 HashTable = xMalloc (TableSize, hashEntry*);
  52
  53                 for (i = 0  ;  i < TableSize  ;  ++i)
  54                         HashTable [i] = NULL;
  55
  56                 allocated = true;
  57         }
  58         return HashTable;
  59 }
  60
  61 static hashEntry *getHashTableEntry (unsigned long hashedValue)
  62 {
  63         hashEntry **const table = getHashTable ();
  64         hashEntry *entry;
  65
  66         Assert (hashedValue < TableSize);
  67         entry = table [hashedValue];
  68
  69         return entry;
  70 }
  71
  72 static unsigned int hashValue (const char *const string, langType language)
  73 {
  74         const signed char *p;
  75         unsigned int h = 5381;
  76
  77         Assert (string != NULL);
  78
  79         /* "djb" hash as used in g_str_hash() in glib */
  80         for (p = (const signed char *)string; *p != '\0'; p++)
  81                 h = (h << 5) + h + tolower (*p);
  82
  83         /* consider language as an extra "character" and add it to the hash */
  84         h = (h << 5) + h + language;
  85
  86         return h;
  87 }
  88
  89 static hashEntry *newEntry (
  90                 const char *const string, langType language, int value)
  91 {
  92         hashEntry *const entry = xMalloc (1, hashEntry);
  93
  94         entry->next     = NULL;
  95         entry->string   = string;
  96         entry->language = language;
  97         entry->value    = value;
  98
  99         return entry;
 100 }
 101
 102 /*  Note that it is assumed that a "value" of zero means an undefined keyword
 103  *  and clients of this function should observe this. Also, all keywords added
 104  *  should be added in lower case. If we encounter a case-sensitive language
 105  *  whose keywords are in upper case, we will need to redesign this.
 106  */
 107 extern void addKeyword (const char *const string, langType language, int value)
 108 {
 109         const unsigned int index = hashValue (string, language) % TableSize;
 110         hashEntry *entry = getHashTableEntry (index);
 111
 112         if (entry == NULL)
 113         {
 114                 hashEntry **const table = getHashTable ();
 115                 table [index] = newEntry (string, language, value);
 116         }
 117         else
 118         {
 119                 hashEntry *prev = NULL;
 120
 121                 while (entry != NULL)
 122                 {
 123                         if (language == entry->language  &&
 124                                 strcmp (string, entry->string) == 0)
 125                         {
 126                                 Assert (("Already in table" == NULL));
 127                         }
 128                         prev = entry;
 129                         entry = entry->next;
 130                 }
 131                 if (entry == NULL)
 132                 {
 133                         Assert (prev != NULL);
 134                         prev->next = newEntry (string, language, value);
 135                 }
 136         }
 137 }
 138
 139 static int lookupKeywordFull (const char *const string, bool caseSensitive, langType language)
 140 {
 141         const unsigned int index = hashValue (string, language) % TableSize;
 142         hashEntry *entry = getHashTableEntry (index);
 143         int result = KEYWORD_NONE;
 144
 145         while (entry != NULL)
 146         {
 147                 if (language == entry->language &&
 148                         ((caseSensitive && strcmp (string, entry->string) == 0) ||
 149                          (!caseSensitive && strcasecmp (string, entry->string) == 0)))
 150                 {
 151                         result = entry->value;
 152                         break;
 153                 }
 154                 entry = entry->next;
 155         }
 156         return result;
 157 }
 158
 159 extern int lookupKeyword (const char *const string, langType language)
 160 {
 161         return lookupKeywordFull (string, true, language);
 162 }
 163
 164 extern int lookupCaseKeyword (const char *const string, langType language)
 165 {
 166         return lookupKeywordFull (string, false, language);
 167 }
 168
 169 extern void freeKeywordTable (void)
 170 {
 171         if (HashTable != NULL)
 172         {
 173                 unsigned int i;
 174
 175                 for (i = 0  ;  i < TableSize  ;  ++i)
 176                 {
 177                         hashEntry *entry = HashTable [i];
 178
 179                         while (entry != NULL)
 180                         {
 181                                 hashEntry *next = entry->next;
 182                                 eFree (entry);
 183                                 entry = next;
 184                         }
 185                 }
 186                 eFree (HashTable);
 187         }
 188 }
 189
 190 #ifdef DEBUG
 191
 192 static void printEntry (const hashEntry *const entry)
 193 {
 194         printf ("  %-15s %-7s\n", entry->string, getLanguageName (entry->language));
 195 }
 196
 197 static unsigned int printBucket (const unsigned int i)
 198 {
 199         hashEntry **const table = getHashTable ();
 200         hashEntry *entry = table [i];
 201         unsigned int measure = 1;
 202         bool first = true;
 203
 204         printf ("%2d:", i);
 205         if (entry == NULL)
 206                 printf ("\n");
 207         else while (entry != NULL)
 208         {
 209                 if (! first)
 210                         printf ("    ");
 211                 else
 212                 {
 213                         printf (" ");
 214                         first = false;
 215                 }
 216                 printEntry (entry);
 217                 entry = entry->next;
 218                 measure = 2 * measure;
 219         }
 220         return measure - 1;
 221 }
 222
 223 extern void printKeywordTable (void)
 224 {
 225         unsigned long emptyBucketCount = 0;
 226         unsigned long measure = 0;
 227         unsigned int i;
 228
 229         for (i = 0  ;  i < TableSize  ;  ++i)
 230         {
 231                 const unsigned int pass = printBucket (i);
 232
 233                 measure += pass;
 234                 if (pass == 0)
 235                         ++emptyBucketCount;
 236         }
 237
 238         printf ("spread measure = %ld\n", measure);
 239         printf ("%ld empty buckets\n", emptyBucketCount);
 240 }
 241
 242 #endif