dict.c

   1 /* Hash Tables Implementation.
   2  *
   3  * This file implements in memory hash tables with insert/del/replace/find/
   4  * get-random-element operations. Hash tables will auto resize if needed
   5  * tables of power of two in size are used, collisions are handled by
   6  * chaining. See the source code for more information... :)
   7  *
   8  * Copyright (c) 2006-2009, Salvatore Sanfilippo <antirez at gmail dot com>
   9  * All rights reserved.
  10  *
  11  * Redistribution and use in source and binary forms, with or without
  12  * modification, are permitted provided that the following conditions are met:
  13  *
  14  *   * Redistributions of source code must retain the above copyright notice,
  15  *     this list of conditions and the following disclaimer.
  16  *   * Redistributions in binary form must reproduce the above copyright
  17  *     notice, this list of conditions and the following disclaimer in the
  18  *     documentation and/or other materials provided with the distribution.
  19  *   * Neither the name of Redis nor the names of its contributors may be used
  20  *     to endorse or promote products derived from this software without
  21  *     specific prior written permission.
  22  *
  23  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
  24  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  25  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  26  * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
  27  * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
  28  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
  29  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
  30  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
  31  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  32  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  33  * POSSIBILITY OF SUCH DAMAGE.
  34  */
  35
  36 #include "fmacros.h"
  37
  38 #include <stdio.h>
  39 #include <stdlib.h>
  40 #include <string.h>
  41 #include <stdarg.h>
  42 #include <assert.h>
  43
  44 #include "dict.h"
  45 #include "zmalloc.h"
  46
  47 /* ---------------------------- Utility funcitons --------------------------- */
  48
  49 static void _dictPanic(const char *fmt, ...)
  50 {
  51     va_list ap;
  52
  53     va_start(ap, fmt);
  54     fprintf(stderr, "\nDICT LIBRARY PANIC: ");
  55     vfprintf(stderr, fmt, ap);
  56     fprintf(stderr, "\n\n");
  57     va_end(ap);
  58 }
  59
  60 /* ------------------------- Heap Management Wrappers------------------------ */
  61
  62 static void *_dictAlloc(int size)
  63 {
  64     void *p = zmalloc(size);
  65     if (p == NULL)
  66         _dictPanic("Out of memory");
  67     return p;
  68 }
  69
  70 static void _dictFree(void *ptr) {
  71     zfree(ptr);
  72 }
  73
  74 /* -------------------------- private prototypes ---------------------------- */
  75
  76 static int _dictExpandIfNeeded(dict *ht);
  77 static unsigned int _dictNextPower(unsigned int size);
  78 static int _dictKeyIndex(dict *ht, const void *key);
  79 static int _dictInit(dict *ht, dictType *type, void *privDataPtr);
  80
  81 /* -------------------------- hash functions -------------------------------- */
  82
  83 /* Thomas Wang's 32 bit Mix Function */
  84 unsigned int dictIntHashFunction(unsigned int key)
  85 {
  86     key += ~(key << 15);
  87     key ^=  (key >> 10);
  88     key +=  (key << 3);
  89     key ^=  (key >> 6);
  90     key += ~(key << 11);
  91     key ^=  (key >> 16);
  92     return key;
  93 }
  94
  95 /* Identity hash function for integer keys */
  96 unsigned int dictIdentityHashFunction(unsigned int key)
  97 {
  98     return key;
  99 }
 100
 101 /* Generic hash function (a popular one from Bernstein).
 102  * I tested a few and this was the best. */
 103 unsigned int dictGenHashFunction(const unsigned char *buf, int len) {
 104     unsigned int hash = 5381;
 105
 106     while (len--)
 107         hash = ((hash << 5) + hash) + (*buf++); /* hash * 33 + c */
 108     return hash;
 109 }
 110
 111 /* ----------------------------- API implementation ------------------------- */
 112
 113 /* Reset an hashtable already initialized with ht_init().
 114  * NOTE: This function should only called by ht_destroy(). */
 115 static void _dictReset(dict *ht)
 116 {
 117     ht->table = NULL;
 118     ht->size = 0;
 119     ht->sizemask = 0;
 120     ht->used = 0;
 121 }
 122
 123 /* Create a new hash table */
 124 dict *dictCreate(dictType *type,
 125         void *privDataPtr)
 126 {
 127     dict *ht = _dictAlloc(sizeof(*ht));
 128
 129     _dictInit(ht,type,privDataPtr);
 130     return ht;
 131 }
 132
 133 /* Initialize the hash table */
 134 int _dictInit(dict *ht, dictType *type,
 135         void *privDataPtr)
 136 {
 137     _dictReset(ht);
 138     ht->type = type;
 139     ht->privdata = privDataPtr;
 140     return DICT_OK;
 141 }
 142
 143 /* Resize the table to the minimal size that contains all the elements,
 144  * but with the invariant of a USER/BUCKETS ration near to <= 1 */
 145 int dictResize(dict *ht)
 146 {
 147     int minimal = ht->used;
 148
 149     if (minimal < DICT_HT_INITIAL_SIZE)
 150         minimal = DICT_HT_INITIAL_SIZE;
 151     return dictExpand(ht, minimal);
 152 }
 153
 154 /* Expand or create the hashtable */
 155 int dictExpand(dict *ht, unsigned int size)
 156 {
 157     dict n; /* the new hashtable */
 158     unsigned int realsize = _dictNextPower(size), i;
 159
 160     /* the size is invalid if it is smaller than the number of
 161      * elements already inside the hashtable */
 162     if (ht->used > size)
 163         return DICT_ERR;
 164
 165     _dictInit(&n, ht->type, ht->privdata);
 166     n.size = realsize;
 167     n.sizemask = realsize-1;
 168     n.table = _dictAlloc(realsize*sizeof(dictEntry*));
 169
 170     /* Initialize all the pointers to NULL */
 171     memset(n.table, 0, realsize*sizeof(dictEntry*));
 172
 173     /* Copy all the elements from the old to the new table:
 174      * note that if the old hash table is empty ht->size is zero,
 175      * so dictExpand just creates an hash table. */
 176     n.used = ht->used;
 177     for (i = 0; i < ht->size && ht->used > 0; i++) {
 178         dictEntry *he, *nextHe;
 179
 180         if (ht->table[i] == NULL) continue;
 181
 182         /* For each hash entry on this slot... */
 183         he = ht->table[i];
 184         while(he) {
 185             unsigned int h;
 186
 187             nextHe = he->next;
 188             /* Get the new element index */
 189             h = dictHashKey(ht, he->key) & n.sizemask;
 190             he->next = n.table[h];
 191             n.table[h] = he;
 192             ht->used--;
 193             /* Pass to the next element */
 194             he = nextHe;
 195         }
 196     }
 197     assert(ht->used == 0);
 198     _dictFree(ht->table);
 199
 200     /* Remap the new hashtable in the old */
 201     *ht = n;
 202     return DICT_OK;
 203 }
 204
 205 /* Add an element to the target hash table */
 206 int dictAdd(dict *ht, void *key, void *val)
 207 {
 208     int index;
 209     dictEntry *entry;
 210
 211     /* Get the index of the new element, or -1 if
 212      * the element already exists. */
 213     if ((index = _dictKeyIndex(ht, key)) == -1)
 214         return DICT_ERR;
 215
 216     /* Allocates the memory and stores key */
 217     entry = _dictAlloc(sizeof(*entry));
 218     entry->next = ht->table[index];
 219     ht->table[index] = entry;
 220
 221     /* Set the hash entry fields. */
 222     dictSetHashKey(ht, entry, key);
 223     dictSetHashVal(ht, entry, val);
 224     ht->used++;
 225     return DICT_OK;
 226 }
 227
 228 /* Add an element, discarding the old if the key already exists */
 229 int dictReplace(dict *ht, void *key, void *val)
 230 {
 231     dictEntry *entry;
 232
 233     /* Try to add the element. If the key
 234      * does not exists dictAdd will suceed. */
 235     if (dictAdd(ht, key, val) == DICT_OK)
 236         return DICT_OK;
 237     /* It already exists, get the entry */
 238     entry = dictFind(ht, key);
 239     /* Free the old value and set the new one */
 240     dictFreeEntryVal(ht, entry);
 241     dictSetHashVal(ht, entry, val);
 242     return DICT_OK;
 243 }
 244
 245 /* Search and remove an element */
 246 static int dictGenericDelete(dict *ht, const void *key, int nofree)
 247 {
 248     unsigned int h;
 249     dictEntry *he, *prevHe;
 250
 251     if (ht->size == 0)
 252         return DICT_ERR;
 253     h = dictHashKey(ht, key) & ht->sizemask;
 254     he = ht->table[h];
 255
 256     prevHe = NULL;
 257     while(he) {
 258         if (dictCompareHashKeys(ht, key, he->key)) {
 259             /* Unlink the element from the list */
 260             if (prevHe)
 261                 prevHe->next = he->next;
 262             else
 263                 ht->table[h] = he->next;
 264             if (!nofree) {
 265                 dictFreeEntryKey(ht, he);
 266                 dictFreeEntryVal(ht, he);
 267             }
 268             _dictFree(he);
 269             ht->used--;
 270             return DICT_OK;
 271         }
 272         prevHe = he;
 273         he = he->next;
 274     }
 275     return DICT_ERR; /* not found */
 276 }
 277
 278 int dictDelete(dict *ht, const void *key) {
 279     return dictGenericDelete(ht,key,0);
 280 }
 281
 282 int dictDeleteNoFree(dict *ht, const void *key) {
 283     return dictGenericDelete(ht,key,1);
 284 }
 285
 286 /* Destroy an entire hash table */
 287 int _dictClear(dict *ht)
 288 {
 289     unsigned int i;
 290
 291     /* Free all the elements */
 292     for (i = 0; i < ht->size && ht->used > 0; i++) {
 293         dictEntry *he, *nextHe;
 294
 295         if ((he = ht->table[i]) == NULL) continue;
 296         while(he) {
 297             nextHe = he->next;
 298             dictFreeEntryKey(ht, he);
 299             dictFreeEntryVal(ht, he);
 300             _dictFree(he);
 301             ht->used--;
 302             he = nextHe;
 303         }
 304     }
 305     /* Free the table and the allocated cache structure */
 306     _dictFree(ht->table);
 307     /* Re-initialize the table */
 308     _dictReset(ht);
 309     return DICT_OK; /* never fails */
 310 }
 311
 312 /* Clear & Release the hash table */
 313 void dictRelease(dict *ht)
 314 {
 315     _dictClear(ht);
 316     _dictFree(ht);
 317 }
 318
 319 dictEntry *dictFind(dict *ht, const void *key)
 320 {
 321     dictEntry *he;
 322     unsigned int h;
 323
 324     if (ht->size == 0) return NULL;
 325     h = dictHashKey(ht, key) & ht->sizemask;
 326     he = ht->table[h];
 327     while(he) {
 328         if (dictCompareHashKeys(ht, key, he->key))
 329             return he;
 330         he = he->next;
 331     }
 332     return NULL;
 333 }
 334
 335 dictIterator *dictGetIterator(dict *ht)
 336 {
 337     dictIterator *iter = _dictAlloc(sizeof(*iter));
 338
 339     iter->ht = ht;
 340     iter->index = -1;
 341     iter->entry = NULL;
 342     iter->nextEntry = NULL;
 343     return iter;
 344 }
 345
 346 dictEntry *dictNext(dictIterator *iter)
 347 {
 348     while (1) {
 349         if (iter->entry == NULL) {
 350             iter->index++;
 351             if (iter->index >=
 352                     (signed)iter->ht->size) break;
 353             iter->entry = iter->ht->table[iter->index];
 354         } else {
 355             iter->entry = iter->nextEntry;
 356         }
 357         if (iter->entry) {
 358             /* We need to save the 'next' here, the iterator user
 359              * may delete the entry we are returning. */
 360             iter->nextEntry = iter->entry->next;
 361             return iter->entry;
 362         }
 363     }
 364     return NULL;
 365 }
 366
 367 void dictReleaseIterator(dictIterator *iter)
 368 {
 369     _dictFree(iter);
 370 }
 371
 372 /* Return a random entry from the hash table. Useful to
 373  * implement randomized algorithms */
 374 dictEntry *dictGetRandomKey(dict *ht)
 375 {
 376     dictEntry *he;
 377     unsigned int h;
 378     int listlen, listele;
 379
 380     if (ht->used == 0) return NULL;
 381     do {
 382         h = random() & ht->sizemask;
 383         he = ht->table[h];
 384     } while(he == NULL);
 385
 386     /* Now we found a non empty bucket, but it is a linked
 387      * list and we need to get a random element from the list.
 388      * The only sane way to do so is to count the element and
 389      * select a random index. */
 390     listlen = 0;
 391     while(he) {
 392         he = he->next;
 393         listlen++;
 394     }
 395     listele = random() % listlen;
 396     he = ht->table[h];
 397     while(listele--) he = he->next;
 398     return he;
 399 }
 400
 401 /* ------------------------- private functions ------------------------------ */
 402
 403 /* Expand the hash table if needed */
 404 static int _dictExpandIfNeeded(dict *ht)
 405 {
 406     /* If the hash table is empty expand it to the intial size,
 407      * if the table is "full" dobule its size. */
 408     if (ht->size == 0)
 409         return dictExpand(ht, DICT_HT_INITIAL_SIZE);
 410     if (ht->used == ht->size)
 411         return dictExpand(ht, ht->size*2);
 412     return DICT_OK;
 413 }
 414
 415 /* Our hash table capability is a power of two */
 416 static unsigned int _dictNextPower(unsigned int size)
 417 {
 418     unsigned int i = DICT_HT_INITIAL_SIZE;
 419
 420     if (size >= 2147483648U)
 421         return 2147483648U;
 422     while(1) {
 423         if (i >= size)
 424             return i;
 425         i *= 2;
 426     }
 427 }
 428
 429 /* Returns the index of a free slot that can be populated with
 430  * an hash entry for the given 'key'.
 431  * If the key already exists, -1 is returned. */
 432 static int _dictKeyIndex(dict *ht, const void *key)
 433 {
 434     unsigned int h;
 435     dictEntry *he;
 436
 437     /* Expand the hashtable if needed */
 438     if (_dictExpandIfNeeded(ht) == DICT_ERR)
 439         return -1;
 440     /* Compute the key hash value */
 441     h = dictHashKey(ht, key) & ht->sizemask;
 442     /* Search if this slot does not already contain the given key */
 443     he = ht->table[h];
 444     while(he) {
 445         if (dictCompareHashKeys(ht, key, he->key))
 446             return -1;
 447         he = he->next;
 448     }
 449     return h;
 450 }
 451
 452 void dictEmpty(dict *ht) {
 453     _dictClear(ht);
 454 }
 455
 456 #define DICT_STATS_VECTLEN 50
 457 void dictPrintStats(dict *ht) {
 458     unsigned int i, slots = 0, chainlen, maxchainlen = 0;
 459     unsigned int totchainlen = 0;
 460     unsigned int clvector[DICT_STATS_VECTLEN];
 461
 462     if (ht->used == 0) {
 463         printf("No stats available for empty dictionaries\n");
 464         return;
 465     }
 466
 467     for (i = 0; i < DICT_STATS_VECTLEN; i++) clvector[i] = 0;
 468     for (i = 0; i < ht->size; i++) {
 469         dictEntry *he;
 470
 471         if (ht->table[i] == NULL) {
 472             clvector[0]++;
 473             continue;
 474         }
 475         slots++;
 476         /* For each hash entry on this slot... */
 477         chainlen = 0;
 478         he = ht->table[i];
 479         while(he) {
 480             chainlen++;
 481             he = he->next;
 482         }
 483         clvector[(chainlen < DICT_STATS_VECTLEN) ? chainlen : (DICT_STATS_VECTLEN-1)]++;
 484         if (chainlen > maxchainlen) maxchainlen = chainlen;
 485         totchainlen += chainlen;
 486     }
 487     printf("Hash table stats:\n");
 488     printf(" table size: %d\n", ht->size);
 489     printf(" number of elements: %d\n", ht->used);
 490     printf(" different slots: %d\n", slots);
 491     printf(" max chain length: %d\n", maxchainlen);
 492     printf(" avg chain length (counted): %.02f\n", (float)totchainlen/slots);
 493     printf(" avg chain length (computed): %.02f\n", (float)ht->used/slots);
 494     printf(" Chain length distribution:\n");
 495     for (i = 0; i < DICT_STATS_VECTLEN-1; i++) {
 496         if (clvector[i] == 0) continue;
 497         printf("   %s%d: %d (%.02f%%)\n",(i == DICT_STATS_VECTLEN-1)?">= ":"", i, clvector[i], ((float)clvector[i]/ht->size)*100);
 498     }
 499 }
 500
 501 /* ----------------------- StringCopy Hash Table Type ------------------------*/
 502
 503 static unsigned int _dictStringCopyHTHashFunction(const void *key)
 504 {
 505     return dictGenHashFunction(key, strlen(key));
 506 }
 507
 508 static void *_dictStringCopyHTKeyDup(void *privdata, const void *key)
 509 {
 510     int len = strlen(key);
 511     char *copy = _dictAlloc(len+1);
 512     DICT_NOTUSED(privdata);
 513
 514     memcpy(copy, key, len);
 515     copy[len] = '\0';
 516     return copy;
 517 }
 518
 519 static void *_dictStringKeyValCopyHTValDup(void *privdata, const void *val)
 520 {
 521     int len = strlen(val);
 522     char *copy = _dictAlloc(len+1);
 523     DICT_NOTUSED(privdata);
 524
 525     memcpy(copy, val, len);
 526     copy[len] = '\0';
 527     return copy;
 528 }
 529
 530 static int _dictStringCopyHTKeyCompare(void *privdata, const void *key1,
 531         const void *key2)
 532 {
 533     DICT_NOTUSED(privdata);
 534
 535     return strcmp(key1, key2) == 0;
 536 }
 537
 538 static void _dictStringCopyHTKeyDestructor(void *privdata, void *key)
 539 {
 540     DICT_NOTUSED(privdata);
 541
 542     _dictFree((void*)key); /* ATTENTION: const cast */
 543 }
 544
 545 static void _dictStringKeyValCopyHTValDestructor(void *privdata, void *val)
 546 {
 547     DICT_NOTUSED(privdata);
 548
 549     _dictFree((void*)val); /* ATTENTION: const cast */
 550 }
 551
 552 dictType dictTypeHeapStringCopyKey = {
 553     _dictStringCopyHTHashFunction,        /* hash function */
 554     _dictStringCopyHTKeyDup,              /* key dup */
 555     NULL,                               /* val dup */
 556     _dictStringCopyHTKeyCompare,          /* key compare */
 557     _dictStringCopyHTKeyDestructor,       /* key destructor */
 558     NULL                                /* val destructor */
 559 };
 560
 561 /* This is like StringCopy but does not auto-duplicate the key.
 562  * It's used for intepreter's shared strings. */
 563 dictType dictTypeHeapStrings = {
 564     _dictStringCopyHTHashFunction,        /* hash function */
 565     NULL,                               /* key dup */
 566     NULL,                               /* val dup */
 567     _dictStringCopyHTKeyCompare,          /* key compare */
 568     _dictStringCopyHTKeyDestructor,       /* key destructor */
 569     NULL                                /* val destructor */
 570 };
 571
 572 /* This is like StringCopy but also automatically handle dynamic
 573  * allocated C strings as values. */
 574 dictType dictTypeHeapStringCopyKeyValue = {
 575     _dictStringCopyHTHashFunction,        /* hash function */
 576     _dictStringCopyHTKeyDup,              /* key dup */
 577     _dictStringKeyValCopyHTValDup,        /* val dup */
 578     _dictStringCopyHTKeyCompare,          /* key compare */
 579     _dictStringCopyHTKeyDestructor,       /* key destructor */
 580     _dictStringKeyValCopyHTValDestructor, /* val destructor */
 581 };