src/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-2010, 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 #include <limits.h>
  44 #include <sys/time.h>
  45 #include <ctype.h>
  46
  47 #include "dict.h"
  48 #include "zmalloc.h"
  49
  50 /* Using dictEnableResize() / dictDisableResize() we make possible to
  51  * enable/disable resizing of the hash table as needed. This is very important
  52  * for Redis, as we use copy-on-write and don't want to move too much memory
  53  * around when there is a child performing saving operations.
  54  *
  55  * Note that even when dict_can_resize is set to 0, not all resizes are
  56  * prevented: an hash table is still allowed to grow if the ratio between
  57  * the number of elements and the buckets > dict_force_resize_ratio. */
  58 static int dict_can_resize = 1;
  59 static unsigned int dict_force_resize_ratio = 5;
  60
  61 /* -------------------------- private prototypes ---------------------------- */
  62
  63 static int _dictExpandIfNeeded(dict *ht);
  64 static unsigned long _dictNextPower(unsigned long size);
  65 static int _dictKeyIndex(dict *ht, const void *key);
  66 static int _dictInit(dict *ht, dictType *type, void *privDataPtr);
  67
  68 /* -------------------------- hash functions -------------------------------- */
  69
  70 /* Thomas Wang's 32 bit Mix Function */
  71 unsigned int dictIntHashFunction(unsigned int key)
  72 {
  73     key += ~(key << 15);
  74     key ^=  (key >> 10);
  75     key +=  (key << 3);
  76     key ^=  (key >> 6);
  77     key += ~(key << 11);
  78     key ^=  (key >> 16);
  79     return key;
  80 }
  81
  82 /* Identity hash function for integer keys */
  83 unsigned int dictIdentityHashFunction(unsigned int key)
  84 {
  85     return key;
  86 }
  87
  88 static int dict_hash_function_seed = 5381;
  89
  90 void dictSetHashFunctionSeed(unsigned int seed) {
  91     dict_hash_function_seed = seed;
  92 }
  93
  94 unsigned int dictGetHashFunctionSeed(void) {
  95     return dict_hash_function_seed;
  96 }
  97
  98 /* Generic hash function (a popular one from Bernstein).
  99  * I tested a few and this was the best. */
 100 unsigned int dictGenHashFunction(const unsigned char *buf, int len) {
 101     unsigned int hash = dict_hash_function_seed;
 102
 103     while (len--)
 104         hash = ((hash << 5) + hash) + (*buf++); /* hash * 33 + c */
 105     return hash;
 106 }
 107
 108 /* And a case insensitive version */
 109 unsigned int dictGenCaseHashFunction(const unsigned char *buf, int len) {
 110     unsigned int hash = dict_hash_function_seed;
 111
 112     while (len--)
 113         hash = ((hash << 5) + hash) + (tolower(*buf++)); /* hash * 33 + c */
 114     return hash;
 115 }
 116
 117 /* ----------------------------- API implementation ------------------------- */
 118
 119 /* Reset a hash table already initialized with ht_init().
 120  * NOTE: This function should only be called by ht_destroy(). */
 121 static void _dictReset(dictht *ht)
 122 {
 123     ht->table = NULL;
 124     ht->size = 0;
 125     ht->sizemask = 0;
 126     ht->used = 0;
 127 }
 128
 129 /* Create a new hash table */
 130 dict *dictCreate(dictType *type,
 131         void *privDataPtr)
 132 {
 133     dict *d = zmalloc(sizeof(*d));
 134
 135     _dictInit(d,type,privDataPtr);
 136     return d;
 137 }
 138
 139 /* Initialize the hash table */
 140 int _dictInit(dict *d, dictType *type,
 141         void *privDataPtr)
 142 {
 143     _dictReset(&d->ht[0]);
 144     _dictReset(&d->ht[1]);
 145     d->type = type;
 146     d->privdata = privDataPtr;
 147     d->rehashidx = -1;
 148     d->iterators = 0;
 149     return DICT_OK;
 150 }
 151
 152 /* Resize the table to the minimal size that contains all the elements,
 153  * but with the invariant of a USED/BUCKETS ratio near to <= 1 */
 154 int dictResize(dict *d)
 155 {
 156     int minimal;
 157
 158     if (!dict_can_resize || dictIsRehashing(d)) return DICT_ERR;
 159     minimal = d->ht[0].used;
 160     if (minimal < DICT_HT_INITIAL_SIZE)
 161         minimal = DICT_HT_INITIAL_SIZE;
 162     return dictExpand(d, minimal);
 163 }
 164
 165 /* Expand or create the hash table */
 166 int dictExpand(dict *d, unsigned long size)
 167 {
 168     dictht n; /* the new hash table */
 169     unsigned long realsize = _dictNextPower(size);
 170
 171     /* the size is invalid if it is smaller than the number of
 172      * elements already inside the hash table */
 173     if (dictIsRehashing(d) || d->ht[0].used > size)
 174         return DICT_ERR;
 175
 176     /* Allocate the new hash table and initialize all pointers to NULL */
 177     n.size = realsize;
 178     n.sizemask = realsize-1;
 179     n.table = zcalloc(realsize*sizeof(dictEntry*));
 180     n.used = 0;
 181
 182     /* Is this the first initialization? If so it's not really a rehashing
 183      * we just set the first hash table so that it can accept keys. */
 184     if (d->ht[0].table == NULL) {
 185         d->ht[0] = n;
 186         return DICT_OK;
 187     }
 188
 189     /* Prepare a second hash table for incremental rehashing */
 190     d->ht[1] = n;
 191     d->rehashidx = 0;
 192     return DICT_OK;
 193 }
 194
 195 /* Performs N steps of incremental rehashing. Returns 1 if there are still
 196  * keys to move from the old to the new hash table, otherwise 0 is returned.
 197  * Note that a rehashing step consists in moving a bucket (that may have more
 198  * thank one key as we use chaining) from the old to the new hash table. */
 199 int dictRehash(dict *d, int n) {
 200     if (!dictIsRehashing(d)) return 0;
 201
 202     while(n--) {
 203         dictEntry *de, *nextde;
 204
 205         /* Check if we already rehashed the whole table... */
 206         if (d->ht[0].used == 0) {
 207             zfree(d->ht[0].table);
 208             d->ht[0] = d->ht[1];
 209             _dictReset(&d->ht[1]);
 210             d->rehashidx = -1;
 211             return 0;
 212         }
 213
 214         /* Note that rehashidx can't overflow as we are sure there are more
 215          * elements because ht[0].used != 0 */
 216         assert(d->ht[0].size > (unsigned)d->rehashidx);
 217         while(d->ht[0].table[d->rehashidx] == NULL) d->rehashidx++;
 218         de = d->ht[0].table[d->rehashidx];
 219         /* Move all the keys in this bucket from the old to the new hash HT */
 220         while(de) {
 221             unsigned int h;
 222
 223             nextde = de->next;
 224             /* Get the index in the new hash table */
 225             h = dictHashKey(d, de->key) & d->ht[1].sizemask;
 226             de->next = d->ht[1].table[h];
 227             d->ht[1].table[h] = de;
 228             d->ht[0].used--;
 229             d->ht[1].used++;
 230             de = nextde;
 231         }
 232         d->ht[0].table[d->rehashidx] = NULL;
 233         d->rehashidx++;
 234     }
 235     return 1;
 236 }
 237
 238 long long timeInMilliseconds(void) {
 239     struct timeval tv;
 240
 241     gettimeofday(&tv,NULL);
 242     return (((long long)tv.tv_sec)*1000)+(tv.tv_usec/1000);
 243 }
 244
 245 /* Rehash for an amount of time between ms milliseconds and ms+1 milliseconds */
 246 int dictRehashMilliseconds(dict *d, int ms) {
 247     long long start = timeInMilliseconds();
 248     int rehashes = 0;
 249
 250     while(dictRehash(d,100)) {
 251         rehashes += 100;
 252         if (timeInMilliseconds()-start > ms) break;
 253     }
 254     return rehashes;
 255 }
 256
 257 /* This function performs just a step of rehashing, and only if there are
 258  * no safe iterators bound to our hash table. When we have iterators in the
 259  * middle of a rehashing we can't mess with the two hash tables otherwise
 260  * some element can be missed or duplicated.
 261  *
 262  * This function is called by common lookup or update operations in the
 263  * dictionary so that the hash table automatically migrates from H1 to H2
 264  * while it is actively used. */
 265 static void _dictRehashStep(dict *d) {
 266     if (d->iterators == 0) dictRehash(d,1);
 267 }
 268
 269 /* Add an element to the target hash table */
 270 int dictAdd(dict *d, void *key, void *val)
 271 {
 272     dictEntry *entry = dictAddRaw(d,key);
 273
 274     if (!entry) return DICT_ERR;
 275     dictSetVal(d, entry, val);
 276     return DICT_OK;
 277 }
 278
 279 /* Low level add. This function adds the entry but instead of setting
 280  * a value returns the dictEntry structure to the user, that will make
 281  * sure to fill the value field as he wishes.
 282  *
 283  * This function is also directly exposed to the user API to be called
 284  * mainly in order to store non-pointers inside the hash value, example:
 285  *
 286  * entry = dictAddRaw(dict,mykey);
 287  * if (entry != NULL) dictSetSignedIntegerVal(entry,1000);
 288  *
 289  * Return values:
 290  *
 291  * If key already exists NULL is returned.
 292  * If key was added, the hash entry is returned to be manipulated by the caller.
 293  */
 294 dictEntry *dictAddRaw(dict *d, void *key)
 295 {
 296     int index;
 297     dictEntry *entry;
 298     dictht *ht;
 299
 300     if (dictIsRehashing(d)) _dictRehashStep(d);
 301
 302     /* Get the index of the new element, or -1 if
 303      * the element already exists. */
 304     if ((index = _dictKeyIndex(d, key)) == -1)
 305         return NULL;
 306
 307     /* Allocate the memory and store the new entry */
 308     ht = dictIsRehashing(d) ? &d->ht[1] : &d->ht[0];
 309     entry = zmalloc(sizeof(*entry));
 310     entry->next = ht->table[index];
 311     ht->table[index] = entry;
 312     ht->used++;
 313
 314     /* Set the hash entry fields. */
 315     dictSetKey(d, entry, key);
 316     return entry;
 317 }
 318
 319 /* Add an element, discarding the old if the key already exists.
 320  * Return 1 if the key was added from scratch, 0 if there was already an
 321  * element with such key and dictReplace() just performed a value update
 322  * operation. */
 323 int dictReplace(dict *d, void *key, void *val)
 324 {
 325     dictEntry *entry, auxentry;
 326
 327     /* Try to add the element. If the key
 328      * does not exists dictAdd will suceed. */
 329     if (dictAdd(d, key, val) == DICT_OK)
 330         return 1;
 331     /* It already exists, get the entry */
 332     entry = dictFind(d, key);
 333     /* Set the new value and free the old one. Note that it is important
 334      * to do that in this order, as the value may just be exactly the same
 335      * as the previous one. In this context, think to reference counting,
 336      * you want to increment (set), and then decrement (free), and not the
 337      * reverse. */
 338     auxentry = *entry;
 339     dictSetVal(d, entry, val);
 340     dictFreeVal(d, &auxentry);
 341     return 0;
 342 }
 343
 344 /* dictReplaceRaw() is simply a version of dictAddRaw() that always
 345  * returns the hash entry of the specified key, even if the key already
 346  * exists and can't be added (in that case the entry of the already
 347  * existing key is returned.)
 348  *
 349  * See dictAddRaw() for more information. */
 350 dictEntry *dictReplaceRaw(dict *d, void *key) {
 351     dictEntry *entry = dictFind(d,key);
 352
 353     return entry ? entry : dictAddRaw(d,key);
 354 }
 355
 356 /* Search and remove an element */
 357 static int dictGenericDelete(dict *d, const void *key, int nofree)
 358 {
 359     unsigned int h, idx;
 360     dictEntry *he, *prevHe;
 361     int table;
 362
 363     if (d->ht[0].size == 0) return DICT_ERR; /* d->ht[0].table is NULL */
 364     if (dictIsRehashing(d)) _dictRehashStep(d);
 365     h = dictHashKey(d, key);
 366
 367     for (table = 0; table <= 1; table++) {
 368         idx = h & d->ht[table].sizemask;
 369         he = d->ht[table].table[idx];
 370         prevHe = NULL;
 371         while(he) {
 372             if (dictCompareKeys(d, key, he->key)) {
 373                 /* Unlink the element from the list */
 374                 if (prevHe)
 375                     prevHe->next = he->next;
 376                 else
 377                     d->ht[table].table[idx] = he->next;
 378                 if (!nofree) {
 379                     dictFreeKey(d, he);
 380                     dictFreeVal(d, he);
 381                 }
 382                 zfree(he);
 383                 d->ht[table].used--;
 384                 return DICT_OK;
 385             }
 386             prevHe = he;
 387             he = he->next;
 388         }
 389         if (!dictIsRehashing(d)) break;
 390     }
 391     return DICT_ERR; /* not found */
 392 }
 393
 394 int dictDelete(dict *ht, const void *key) {
 395     return dictGenericDelete(ht,key,0);
 396 }
 397
 398 int dictDeleteNoFree(dict *ht, const void *key) {
 399     return dictGenericDelete(ht,key,1);
 400 }
 401
 402 /* Destroy an entire dictionary */
 403 int _dictClear(dict *d, dictht *ht)
 404 {
 405     unsigned long i;
 406
 407     /* Free all the elements */
 408     for (i = 0; i < ht->size && ht->used > 0; i++) {
 409         dictEntry *he, *nextHe;
 410
 411         if ((he = ht->table[i]) == NULL) continue;
 412         while(he) {
 413             nextHe = he->next;
 414             dictFreeKey(d, he);
 415             dictFreeVal(d, he);
 416             zfree(he);
 417             ht->used--;
 418             he = nextHe;
 419         }
 420     }
 421     /* Free the table and the allocated cache structure */
 422     zfree(ht->table);
 423     /* Re-initialize the table */
 424     _dictReset(ht);
 425     return DICT_OK; /* never fails */
 426 }
 427
 428 /* Clear & Release the hash table */
 429 void dictRelease(dict *d)
 430 {
 431     _dictClear(d,&d->ht[0]);
 432     _dictClear(d,&d->ht[1]);
 433     zfree(d);
 434 }
 435
 436 dictEntry *dictFind(dict *d, const void *key)
 437 {
 438     dictEntry *he;
 439     unsigned int h, idx, table;
 440
 441     if (d->ht[0].size == 0) return NULL; /* We don't have a table at all */
 442     if (dictIsRehashing(d)) _dictRehashStep(d);
 443     h = dictHashKey(d, key);
 444     for (table = 0; table <= 1; table++) {
 445         idx = h & d->ht[table].sizemask;
 446         he = d->ht[table].table[idx];
 447         while(he) {
 448             if (dictCompareKeys(d, key, he->key))
 449                 return he;
 450             he = he->next;
 451         }
 452         if (!dictIsRehashing(d)) return NULL;
 453     }
 454     return NULL;
 455 }
 456
 457 void *dictFetchValue(dict *d, const void *key) {
 458     dictEntry *he;
 459
 460     he = dictFind(d,key);
 461     return he ? dictGetVal(he) : NULL;
 462 }
 463
 464 dictIterator *dictGetIterator(dict *d)
 465 {
 466     dictIterator *iter = zmalloc(sizeof(*iter));
 467
 468     iter->d = d;
 469     iter->table = 0;
 470     iter->index = -1;
 471     iter->safe = 0;
 472     iter->entry = NULL;
 473     iter->nextEntry = NULL;
 474     return iter;
 475 }
 476
 477 dictIterator *dictGetSafeIterator(dict *d) {
 478     dictIterator *i = dictGetIterator(d);
 479
 480     i->safe = 1;
 481     return i;
 482 }
 483
 484 dictEntry *dictNext(dictIterator *iter)
 485 {
 486     while (1) {
 487         if (iter->entry == NULL) {
 488             dictht *ht = &iter->d->ht[iter->table];
 489             if (iter->safe && iter->index == -1 && iter->table == 0)
 490                 iter->d->iterators++;
 491             iter->index++;
 492             if (iter->index >= (signed) ht->size) {
 493                 if (dictIsRehashing(iter->d) && iter->table == 0) {
 494                     iter->table++;
 495                     iter->index = 0;
 496                     ht = &iter->d->ht[1];
 497                 } else {
 498                     break;
 499                 }
 500             }
 501             iter->entry = ht->table[iter->index];
 502         } else {
 503             iter->entry = iter->nextEntry;
 504         }
 505         if (iter->entry) {
 506             /* We need to save the 'next' here, the iterator user
 507              * may delete the entry we are returning. */
 508             iter->nextEntry = iter->entry->next;
 509             return iter->entry;
 510         }
 511     }
 512     return NULL;
 513 }
 514
 515 void dictReleaseIterator(dictIterator *iter)
 516 {
 517     if (iter->safe && !(iter->index == -1 && iter->table == 0))
 518         iter->d->iterators--;
 519     zfree(iter);
 520 }
 521
 522 /* Return a random entry from the hash table. Useful to
 523  * implement randomized algorithms */
 524 dictEntry *dictGetRandomKey(dict *d)
 525 {
 526     dictEntry *he, *orighe;
 527     unsigned int h;
 528     int listlen, listele;
 529
 530     if (dictSize(d) == 0) return NULL;
 531     if (dictIsRehashing(d)) _dictRehashStep(d);
 532     if (dictIsRehashing(d)) {
 533         do {
 534             h = random() % (d->ht[0].size+d->ht[1].size);
 535             he = (h >= d->ht[0].size) ? d->ht[1].table[h - d->ht[0].size] :
 536                                       d->ht[0].table[h];
 537         } while(he == NULL);
 538     } else {
 539         do {
 540             h = random() & d->ht[0].sizemask;
 541             he = d->ht[0].table[h];
 542         } while(he == NULL);
 543     }
 544
 545     /* Now we found a non empty bucket, but it is a linked
 546      * list and we need to get a random element from the list.
 547      * The only sane way to do so is counting the elements and
 548      * select a random index. */
 549     listlen = 0;
 550     orighe = he;
 551     while(he) {
 552         he = he->next;
 553         listlen++;
 554     }
 555     listele = random() % listlen;
 556     he = orighe;
 557     while(listele--) he = he->next;
 558     return he;
 559 }
 560
 561 /* ------------------------- private functions ------------------------------ */
 562
 563 /* Expand the hash table if needed */
 564 static int _dictExpandIfNeeded(dict *d)
 565 {
 566     /* Incremental rehashing already in progress. Return. */
 567     if (dictIsRehashing(d)) return DICT_OK;
 568
 569     /* If the hash table is empty expand it to the intial size. */
 570     if (d->ht[0].size == 0) return dictExpand(d, DICT_HT_INITIAL_SIZE);
 571
 572     /* If we reached the 1:1 ratio, and we are allowed to resize the hash
 573      * table (global setting) or we should avoid it but the ratio between
 574      * elements/buckets is over the "safe" threshold, we resize doubling
 575      * the number of buckets. */
 576     if (d->ht[0].used >= d->ht[0].size &&
 577         (dict_can_resize ||
 578          d->ht[0].used/d->ht[0].size > dict_force_resize_ratio))
 579     {
 580         return dictExpand(d, ((d->ht[0].size > d->ht[0].used) ?
 581                                     d->ht[0].size : d->ht[0].used)*2);
 582     }
 583     return DICT_OK;
 584 }
 585
 586 /* Our hash table capability is a power of two */
 587 static unsigned long _dictNextPower(unsigned long size)
 588 {
 589     unsigned long i = DICT_HT_INITIAL_SIZE;
 590
 591     if (size >= LONG_MAX) return LONG_MAX;
 592     while(1) {
 593         if (i >= size)
 594             return i;
 595         i *= 2;
 596     }
 597 }
 598
 599 /* Returns the index of a free slot that can be populated with
 600  * an hash entry for the given 'key'.
 601  * If the key already exists, -1 is returned.
 602  *
 603  * Note that if we are in the process of rehashing the hash table, the
 604  * index is always returned in the context of the second (new) hash table. */
 605 static int _dictKeyIndex(dict *d, const void *key)
 606 {
 607     unsigned int h, idx, table;
 608     dictEntry *he;
 609
 610     /* Expand the hash table if needed */
 611     if (_dictExpandIfNeeded(d) == DICT_ERR)
 612         return -1;
 613     /* Compute the key hash value */
 614     h = dictHashKey(d, key);
 615     for (table = 0; table <= 1; table++) {
 616         idx = h & d->ht[table].sizemask;
 617         /* Search if this slot does not already contain the given key */
 618         he = d->ht[table].table[idx];
 619         while(he) {
 620             if (dictCompareKeys(d, key, he->key))
 621                 return -1;
 622             he = he->next;
 623         }
 624         if (!dictIsRehashing(d)) break;
 625     }
 626     return idx;
 627 }
 628
 629 void dictEmpty(dict *d) {
 630     _dictClear(d,&d->ht[0]);
 631     _dictClear(d,&d->ht[1]);
 632     d->rehashidx = -1;
 633     d->iterators = 0;
 634 }
 635
 636 void dictEnableResize(void) {
 637     dict_can_resize = 1;
 638 }
 639
 640 void dictDisableResize(void) {
 641     dict_can_resize = 0;
 642 }
 643
 644 #if 0
 645
 646 The following is code that we don't use for Redis currently, but that is part
 647 of the library.
 648
 649 /* ----------------------- Debugging ------------------------*/
 650
 651 #define DICT_STATS_VECTLEN 50
 652 static void _dictPrintStatsHt(dictht *ht) {
 653     unsigned long i, slots = 0, chainlen, maxchainlen = 0;
 654     unsigned long totchainlen = 0;
 655     unsigned long clvector[DICT_STATS_VECTLEN];
 656
 657     if (ht->used == 0) {
 658         printf("No stats available for empty dictionaries\n");
 659         return;
 660     }
 661
 662     for (i = 0; i < DICT_STATS_VECTLEN; i++) clvector[i] = 0;
 663     for (i = 0; i < ht->size; i++) {
 664         dictEntry *he;
 665
 666         if (ht->table[i] == NULL) {
 667             clvector[0]++;
 668             continue;
 669         }
 670         slots++;
 671         /* For each hash entry on this slot... */
 672         chainlen = 0;
 673         he = ht->table[i];
 674         while(he) {
 675             chainlen++;
 676             he = he->next;
 677         }
 678         clvector[(chainlen < DICT_STATS_VECTLEN) ? chainlen : (DICT_STATS_VECTLEN-1)]++;
 679         if (chainlen > maxchainlen) maxchainlen = chainlen;
 680         totchainlen += chainlen;
 681     }
 682     printf("Hash table stats:\n");
 683     printf(" table size: %ld\n", ht->size);
 684     printf(" number of elements: %ld\n", ht->used);
 685     printf(" different slots: %ld\n", slots);
 686     printf(" max chain length: %ld\n", maxchainlen);
 687     printf(" avg chain length (counted): %.02f\n", (float)totchainlen/slots);
 688     printf(" avg chain length (computed): %.02f\n", (float)ht->used/slots);
 689     printf(" Chain length distribution:\n");
 690     for (i = 0; i < DICT_STATS_VECTLEN-1; i++) {
 691         if (clvector[i] == 0) continue;
 692         printf("   %s%ld: %ld (%.02f%%)\n",(i == DICT_STATS_VECTLEN-1)?">= ":"", i, clvector[i], ((float)clvector[i]/ht->size)*100);
 693     }
 694 }
 695
 696 void dictPrintStats(dict *d) {
 697     _dictPrintStatsHt(&d->ht[0]);
 698     if (dictIsRehashing(d)) {
 699         printf("-- Rehashing into ht[1]:\n");
 700         _dictPrintStatsHt(&d->ht[1]);
 701     }
 702 }
 703
 704 /* ----------------------- StringCopy Hash Table Type ------------------------*/
 705
 706 static unsigned int _dictStringCopyHTHashFunction(const void *key)
 707 {
 708     return dictGenHashFunction(key, strlen(key));
 709 }
 710
 711 static void *_dictStringDup(void *privdata, const void *key)
 712 {
 713     int len = strlen(key);
 714     char *copy = zmalloc(len+1);
 715     DICT_NOTUSED(privdata);
 716
 717     memcpy(copy, key, len);
 718     copy[len] = '\0';
 719     return copy;
 720 }
 721
 722 static int _dictStringCopyHTKeyCompare(void *privdata, const void *key1,
 723         const void *key2)
 724 {
 725     DICT_NOTUSED(privdata);
 726
 727     return strcmp(key1, key2) == 0;
 728 }
 729
 730 static void _dictStringDestructor(void *privdata, void *key)
 731 {
 732     DICT_NOTUSED(privdata);
 733
 734     zfree(key);
 735 }
 736
 737 dictType dictTypeHeapStringCopyKey = {
 738     _dictStringCopyHTHashFunction, /* hash function */
 739     _dictStringDup,                /* key dup */
 740     NULL,                          /* val dup */
 741     _dictStringCopyHTKeyCompare,   /* key compare */
 742     _dictStringDestructor,         /* key destructor */
 743     NULL                           /* val destructor */
 744 };
 745
 746 /* This is like StringCopy but does not auto-duplicate the key.
 747  * It's used for intepreter's shared strings. */
 748 dictType dictTypeHeapStrings = {
 749     _dictStringCopyHTHashFunction, /* hash function */
 750     NULL,                          /* key dup */
 751     NULL,                          /* val dup */
 752     _dictStringCopyHTKeyCompare,   /* key compare */
 753     _dictStringDestructor,         /* key destructor */
 754     NULL                           /* val destructor */
 755 };
 756
 757 /* This is like StringCopy but also automatically handle dynamic
 758  * allocated C strings as values. */
 759 dictType dictTypeHeapStringCopyKeyValue = {
 760     _dictStringCopyHTHashFunction, /* hash function */
 761     _dictStringDup,                /* key dup */
 762     _dictStringDup,                /* val dup */
 763     _dictStringCopyHTKeyCompare,   /* key compare */
 764     _dictStringDestructor,         /* key destructor */
 765     _dictStringDestructor,         /* val destructor */
 766 };
 767 #endif