ctags/main/htable.c

   1 /*
   2 *
   3 *   Copyright (c) 2014, Red Hat, Inc.
   4 *   Copyright (c) 2014, Masatake YAMATO
   5 *
   6 *   This source code is released for free distribution under the terms of the
   7 *   GNU General Public License version 2 or (at your option) any later version.
   8 *
   9 *   Defines hashtable
  10 */
  11
  12 #include "general.h"
  13 #include "htable.h"
  14
  15 #ifndef MAIN
  16 #include <stdio.h>
  17 #include "routines.h"
  18 #else
  19 #include <stdlib.h>
  20 #ifndef xCalloc
  21 #define xCalloc(n,Type)    (Type *)calloc((size_t)(n), sizeof (Type))
  22 #endif
  23 #ifndef xMalloc
  24 #define xMalloc(n,Type)    (Type *)malloc((size_t)(n) * sizeof (Type))
  25 #endif
  26 #ifndef eFree
  27 #define eFree(x) free(x)
  28 #endif
  29 #endif  /* MAIN */
  30
  31 #include <string.h>
  32
  33
  34 typedef struct sHashEntry hentry;
  35 struct sHashEntry {
  36         void *key;
  37         void *value;
  38         hentry *next;
  39 };
  40
  41 struct sHashTable {
  42         hentry** table;
  43         unsigned int size;
  44         hashTableHashFunc hashfn;
  45         hashTableEqualFunc equalfn;
  46         hashTableDeleteFunc keyfreefn;
  47         hashTableDeleteFunc valfreefn;
  48         void *valForNotUnknownKey;
  49         hashTableDeleteFunc valForNotUnknownKeyfreefn;
  50 };
  51
  52 struct chainTracker {
  53         const void *const target_key;
  54         hashTableForeachFunc user_proc;
  55         void *user_data;
  56         hashTableEqualFunc equalfn;
  57 };
  58
  59 static hentry* entry_new (void *key, void *value, hentry* next)
  60 {
  61         hentry* entry = xMalloc (1, hentry);
  62
  63         entry->key = key;
  64         entry->value = value;
  65         entry->next = next;
  66
  67         return entry;
  68 }
  69
  70 static void entry_reset  (hentry* entry,
  71                                                   void *newkey,
  72                                                   void *newval,
  73                                                   hashTableDeleteFunc keyfreefn,
  74                                                   hashTableDeleteFunc valfreefn)
  75 {
  76         if (keyfreefn)
  77                 keyfreefn (entry->key);
  78         if (valfreefn)
  79                 valfreefn (entry->value);
  80         entry->key = newkey;
  81         entry->value = newval;
  82 }
  83
  84 static hentry* entry_destroy (hentry* entry,
  85                               hashTableDeleteFunc keyfreefn,
  86                               hashTableDeleteFunc valfreefn)
  87 {
  88         hentry* tmp;
  89
  90         entry_reset (entry, NULL, NULL, keyfreefn, valfreefn);
  91         tmp = entry->next;
  92         eFree (entry);
  93
  94         return tmp;
  95 }
  96
  97 static void  entry_reclaim (hentry* entry,
  98                             hashTableDeleteFunc keyfreefn,
  99                             hashTableDeleteFunc valfreefn)
 100 {
 101         while (entry)
 102                 entry = entry_destroy (entry, keyfreefn, valfreefn);
 103 }
 104
 105 static void *entry_find (hentry* entry, const void* const key, hashTableEqualFunc equalfn,
 106                                                  void *valForNotUnknownKey)
 107 {
 108         while (entry)
 109         {
 110                 if (equalfn( key, entry->key))
 111                         return entry->value;
 112                 entry = entry->next;
 113         }
 114         return valForNotUnknownKey;
 115 }
 116
 117 static bool             entry_delete (hentry **entry, const void *key, hashTableEqualFunc equalfn,
 118                               hashTableDeleteFunc keyfreefn, hashTableDeleteFunc valfreefn)
 119 {
 120         while (*entry)
 121         {
 122                 if (equalfn (key, (*entry)->key))
 123                 {
 124                         *entry = entry_destroy (*entry, keyfreefn, valfreefn);
 125                         return true;
 126                 }
 127                 entry = &((*entry)->next);
 128         }
 129         return false;
 130 }
 131
 132 static bool             entry_update (hentry *entry, void *key, void *value, hashTableEqualFunc equalfn,
 133                               hashTableDeleteFunc keyfreefn, hashTableDeleteFunc valfreefn)
 134 {
 135         while (entry)
 136         {
 137                 if (equalfn (key, entry->key))
 138                 {
 139                         entry_reset (entry, key, value, keyfreefn, valfreefn);
 140                         return true;
 141                 }
 142                 entry = entry->next;
 143         }
 144         return false;
 145 }
 146
 147 static bool  entry_foreach (hentry *entry, hashTableForeachFunc proc, void *user_data)
 148 {
 149         while (entry)
 150         {
 151                 if (!proc (entry->key, entry->value, user_data))
 152                         return false;
 153                 entry = entry->next;
 154         }
 155         return true;
 156 }
 157
 158 extern hashTable *hashTableNew    (unsigned int size,
 159                                    hashTableHashFunc hashfn,
 160                                    hashTableEqualFunc equalfn,
 161                                    hashTableDeleteFunc keyfreefn,
 162                                    hashTableDeleteFunc valfreefn)
 163 {
 164         hashTable *htable;
 165
 166         htable = xMalloc (1, hashTable);
 167         htable->size = size;
 168         htable->table = xCalloc (size, hentry*);
 169
 170         htable->hashfn = hashfn;
 171         htable->equalfn = equalfn;
 172         htable->keyfreefn = keyfreefn;
 173         htable->valfreefn = valfreefn;
 174         htable->valForNotUnknownKey = NULL;
 175         htable->valForNotUnknownKeyfreefn = NULL;
 176
 177         return htable;
 178 }
 179
 180 extern void hashTableSetValueForUnknownKey (hashTable *htable,
 181                                                                                         void *val,
 182                                                                                         hashTableDeleteFunc valfreefn)
 183 {
 184         if (htable->valfreefn)
 185                 htable->valfreefn (htable->valForNotUnknownKey);
 186
 187         htable->valForNotUnknownKey = val;
 188         htable->valForNotUnknownKeyfreefn = valfreefn;
 189 }
 190
 191 extern void       hashTableDelete (hashTable *htable)
 192 {
 193         if (!htable)
 194                 return;
 195
 196         hashTableClear (htable);
 197
 198         if (htable->valForNotUnknownKeyfreefn)
 199                 htable->valForNotUnknownKeyfreefn (htable->valForNotUnknownKey);
 200         eFree (htable->table);
 201         eFree (htable);
 202 }
 203
 204 extern void       hashTableClear (hashTable *htable)
 205 {
 206         unsigned int i;
 207         if (!htable)
 208                 return;
 209
 210         for (i = 0; i < htable->size; i++)
 211         {
 212                 hentry *entry;
 213
 214                 entry = htable->table[i];
 215                 entry_reclaim (entry, htable->keyfreefn, htable->valfreefn);
 216                 htable->table[i] = NULL;
 217         }
 218 }
 219
 220 extern void       hashTablePutItem    (hashTable *htable, void *key, void *value)
 221 {
 222         unsigned int i;
 223
 224         i = htable->hashfn (key) % htable->size;
 225         htable->table[i] = entry_new(key, value, htable->table[i]);
 226 }
 227
 228 extern void*      hashTableGetItem   (hashTable *htable, const void * key)
 229 {
 230         unsigned int i;
 231
 232         i = htable->hashfn (key) % htable->size;
 233         return entry_find(htable->table[i], key, htable->equalfn, htable->valForNotUnknownKey);
 234 }
 235
 236 extern bool     hashTableDeleteItem (hashTable *htable, const void *key)
 237 {
 238         unsigned int i;
 239
 240         i = htable->hashfn (key) % htable->size;
 241         return entry_delete(&htable->table[i], key,
 242                             htable->equalfn, htable->keyfreefn, htable->valfreefn);
 243 }
 244
 245 extern bool    hashTableUpdateItem (hashTable *htable, void *key, void *value)
 246 {
 247         unsigned int i;
 248
 249         i = htable->hashfn (key) % htable->size;
 250         bool r = entry_update(htable->table[i], key, value,
 251                                                   htable->equalfn, htable->keyfreefn, htable->valfreefn);
 252         if (!r)
 253                 htable->table[i] = entry_new(key, value, htable->table[i]);
 254         return r;
 255 }
 256
 257 extern bool    hashTableHasItem    (hashTable *htable, const void *key)
 258 {
 259         return hashTableGetItem (htable, key) == htable->valForNotUnknownKey? false: true;
 260 }
 261
 262 extern bool       hashTableForeachItem (hashTable *htable, hashTableForeachFunc proc, void *user_data)
 263 {
 264         unsigned int i;
 265
 266         for (i = 0; i < htable->size; i++)
 267                 if (!entry_foreach(htable->table[i], proc, user_data))
 268                         return false;
 269         return true;
 270 }
 271
 272 static bool track_chain (const void *const key, void *value, void *chain_data)
 273 {
 274         struct chainTracker *chain_tracker = chain_data;
 275
 276         if (chain_tracker->equalfn (chain_tracker->target_key, key))
 277         {
 278                 if (! chain_tracker->user_proc (key, value, chain_tracker->user_data))
 279                         return false;
 280         }
 281         return true;
 282 }
 283
 284 extern bool       hashTableForeachItemOnChain (hashTable *htable, const void *key, hashTableForeachFunc proc, void *user_data)
 285 {
 286         unsigned int i;
 287         struct chainTracker chain_tracker = {
 288                 .target_key = key,
 289                 .user_proc = proc,
 290                 .user_data = user_data,
 291                 .equalfn   = htable->equalfn,
 292         };
 293
 294         i = htable->hashfn (key) % htable->size;
 295         if (!entry_foreach(htable->table[i], track_chain, &chain_tracker))
 296                 return false;
 297         return true;
 298 }
 299
 300 static bool count (const void *const key CTAGS_ATTR_UNUSED, void *value CTAGS_ATTR_UNUSED, void *data)
 301 {
 302         int *c = data;
 303         ++*c;
 304         return true;
 305 }
 306
 307 extern unsigned int hashTableCountItem   (hashTable *htable)
 308 {
 309         int c = 0;
 310         hashTableForeachItem (htable, count, &c);
 311         return c;
 312 }
 313
 314 unsigned int hashPtrhash (const void * const x)
 315 {
 316         union {
 317                 const void * ptr;
 318                 unsigned int ui;
 319         } v;
 320         v.ui = 0;
 321         v.ptr = x;
 322
 323         return v.ui;
 324 }
 325
 326 bool hashPtreq (const void *const a, const void *const b)
 327 {
 328         return (a == b)? true: false;
 329 }
 330
 331
 332 /* http://www.cse.yorku.ca/~oz/hash.html */
 333 static unsigned long
 334 djb2(const unsigned char *str)
 335 {
 336         unsigned long hash = 5381;
 337         int c;
 338
 339         while ((c = *str++))
 340                 hash = ((hash << 5) + hash) + c; /* hash * 33 + c */
 341
 342         return hash;
 343 }
 344
 345 static unsigned long
 346 casedjb2(const unsigned char *str)
 347 {
 348         unsigned long hash = 5381;
 349         int c;
 350
 351         while ((c = *str++))
 352         {
 353                 if (('a' <= c) && (c <= 'z'))
 354                         c += ('A' - 'a');
 355                 hash = ((hash << 5) + hash) + c; /* hash * 33 + c */
 356         }
 357
 358         return hash;
 359 }
 360
 361
 362 unsigned int hashCstrhash (const void *const x)
 363 {
 364         const char *const s = x;
 365         return (unsigned int)djb2((const unsigned char *)s);
 366 }
 367
 368 bool hashCstreq (const void * const a, const void *const b)
 369 {
 370         return !!(strcmp (a, b) == 0);
 371 }
 372
 373 unsigned int hashInthash (const void *const x)
 374 {
 375        union tmp {
 376                unsigned int u;
 377                int i;
 378        } x0;
 379
 380        x0.u = 0;
 381        x0.i = *(int *)x;
 382        return x0.u;
 383 }
 384
 385 bool hashInteq (const void *const a, const void *const b)
 386 {
 387        int ai = *(int *)a;
 388        int bi = *(int *)b;
 389
 390        return !!(ai == bi);
 391 }
 392
 393
 394 unsigned int hashCstrcasehash (const void *const x)
 395 {
 396         const char *const s = x;
 397         return (unsigned int)casedjb2((const unsigned char *)s);
 398 }
 399
 400 bool hashCstrcaseeq (const void *const a, const void *const b)
 401 {
 402         return !!(strcasecmp (a, b) == 0);
 403 }