Back to home page

Redis cross reference

 
 

    


0001 /* Hash Tables Implementation.
0002  *
0003  * This file implements in memory hash tables with insert/del/replace/find/
0004  * get-random-element operations. Hash tables will auto resize if needed
0005  * tables of power of two in size are used, collisions are handled by
0006  * chaining. See the source code for more information... :)
0007  *
0008  * Copyright (c) 2006-2012, Salvatore Sanfilippo <antirez at gmail dot com>
0009  * All rights reserved.
0010  *
0011  * Redistribution and use in source and binary forms, with or without
0012  * modification, are permitted provided that the following conditions are met:
0013  *
0014  *   * Redistributions of source code must retain the above copyright notice,
0015  *     this list of conditions and the following disclaimer.
0016  *   * Redistributions in binary form must reproduce the above copyright
0017  *     notice, this list of conditions and the following disclaimer in the
0018  *     documentation and/or other materials provided with the distribution.
0019  *   * Neither the name of Redis nor the names of its contributors may be used
0020  *     to endorse or promote products derived from this software without
0021  *     specific prior written permission.
0022  *
0023  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
0024  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
0025  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
0026  * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
0027  * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
0028  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
0029  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
0030  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
0031  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
0032  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
0033  * POSSIBILITY OF SUCH DAMAGE.
0034  */
0035 
0036 #include "fmacros.h"
0037 
0038 #include <stdio.h>
0039 #include <stdlib.h>
0040 #include <string.h>
0041 #include <stdarg.h>
0042 #include <assert.h>
0043 #include <limits.h>
0044 #include <sys/time.h>
0045 #include <ctype.h>
0046 
0047 #include "dict.h"
0048 #include "zmalloc.h"
0049 
0050 /* Using dictEnableResize() / dictDisableResize() we make possible to
0051  * enable/disable resizing of the hash table as needed. This is very important
0052  * for Redis, as we use copy-on-write and don't want to move too much memory
0053  * around when there is a child performing saving operations.
0054  *
0055  * Note that even when dict_can_resize is set to 0, not all resizes are
0056  * prevented: an hash table is still allowed to grow if the ratio between
0057  * the number of elements and the buckets > dict_force_resize_ratio. */
0058 static int dict_can_resize = 1;
0059 static unsigned int dict_force_resize_ratio = 5;
0060 
0061 /* -------------------------- private prototypes ---------------------------- */
0062 
0063 static int _dictExpandIfNeeded(dict *ht);
0064 static unsigned long _dictNextPower(unsigned long size);
0065 static int _dictKeyIndex(dict *ht, const void *key);
0066 static int _dictInit(dict *ht, dictType *type, void *privDataPtr);
0067 
0068 /* -------------------------- hash functions -------------------------------- */
0069 
0070 /* Thomas Wang's 32 bit Mix Function */
0071 unsigned int dictIntHashFunction(unsigned int key)
0072 {
0073     key += ~(key << 15);
0074     key ^=  (key >> 10);
0075     key +=  (key << 3);
0076     key ^=  (key >> 6);
0077     key += ~(key << 11);
0078     key ^=  (key >> 16);
0079     return key;
0080 }
0081 
0082 /* Identity hash function for integer keys */
0083 unsigned int dictIdentityHashFunction(unsigned int key)
0084 {
0085     return key;
0086 }
0087 
0088 static uint32_t dict_hash_function_seed = 5381;
0089 
0090 void dictSetHashFunctionSeed(uint32_t seed) {
0091     dict_hash_function_seed = seed;
0092 }
0093 
0094 uint32_t dictGetHashFunctionSeed(void) {
0095     return dict_hash_function_seed;
0096 }
0097 
0098 /* MurmurHash2, by Austin Appleby
0099  * Note - This code makes a few assumptions about how your machine behaves -
0100  * 1. We can read a 4-byte value from any address without crashing
0101  * 2. sizeof(int) == 4
0102  *
0103  * And it has a few limitations -
0104  *
0105  * 1. It will not work incrementally.
0106  * 2. It will not produce the same results on little-endian and big-endian
0107  *    machines.
0108  */
0109 unsigned int dictGenHashFunction(const void *key, int len) {
0110     /* 'm' and 'r' are mixing constants generated offline.
0111      They're not really 'magic', they just happen to work well.  */
0112     uint32_t seed = dict_hash_function_seed;
0113     const uint32_t m = 0x5bd1e995;
0114     const int r = 24;
0115 
0116     /* Initialize the hash to a 'random' value */
0117     uint32_t h = seed ^ len;
0118 
0119     /* Mix 4 bytes at a time into the hash */
0120     const unsigned char *data = (const unsigned char *)key;
0121 
0122     while(len >= 4) {
0123         uint32_t k = *(uint32_t*)data;
0124 
0125         k *= m;
0126         k ^= k >> r;
0127         k *= m;
0128 
0129         h *= m;
0130         h ^= k;
0131 
0132         data += 4;
0133         len -= 4;
0134     }
0135 
0136     /* Handle the last few bytes of the input array  */
0137     switch(len) {
0138     case 3: h ^= data[2] << 16;
0139     case 2: h ^= data[1] << 8;
0140     case 1: h ^= data[0]; h *= m;
0141     };
0142 
0143     /* Do a few final mixes of the hash to ensure the last few
0144      * bytes are well-incorporated. */
0145     h ^= h >> 13;
0146     h *= m;
0147     h ^= h >> 15;
0148 
0149     return (unsigned int)h;
0150 }
0151 
0152 /* And a case insensitive hash function (based on djb hash) */
0153 unsigned int dictGenCaseHashFunction(const unsigned char *buf, int len) {
0154     unsigned int hash = (unsigned int)dict_hash_function_seed;
0155 
0156     while (len--)
0157         hash = ((hash << 5) + hash) + (tolower(*buf++)); /* hash * 33 + c */
0158     return hash;
0159 }
0160 
0161 /* ----------------------------- API implementation ------------------------- */
0162 
0163 /* Reset a hash table already initialized with ht_init().
0164  * NOTE: This function should only be called by ht_destroy(). */
0165 static void _dictReset(dictht *ht)
0166 {
0167     ht->table = NULL;
0168     ht->size = 0;
0169     ht->sizemask = 0;
0170     ht->used = 0;
0171 }
0172 
0173 /* Create a new hash table */
0174 dict *dictCreate(dictType *type,
0175         void *privDataPtr)
0176 {
0177     dict *d = zmalloc(sizeof(*d));
0178 
0179     _dictInit(d,type,privDataPtr);
0180     return d;
0181 }
0182 
0183 /* Initialize the hash table */
0184 int _dictInit(dict *d, dictType *type,
0185         void *privDataPtr)
0186 {
0187     _dictReset(&d->ht[0]);
0188     _dictReset(&d->ht[1]);
0189     d->type = type;
0190     d->privdata = privDataPtr;
0191     d->rehashidx = -1;
0192     d->iterators = 0;
0193     return DICT_OK;
0194 }
0195 
0196 /* Resize the table to the minimal size that contains all the elements,
0197  * but with the invariant of a USED/BUCKETS ratio near to <= 1 */
0198 int dictResize(dict *d)
0199 {
0200     int minimal;
0201 
0202     if (!dict_can_resize || dictIsRehashing(d)) return DICT_ERR;
0203     minimal = d->ht[0].used;
0204     if (minimal < DICT_HT_INITIAL_SIZE)
0205         minimal = DICT_HT_INITIAL_SIZE;
0206     return dictExpand(d, minimal);
0207 }
0208 
0209 /* Expand or create the hash table */
0210 int dictExpand(dict *d, unsigned long size)
0211 {
0212     dictht n; /* the new hash table */
0213     unsigned long realsize = _dictNextPower(size);
0214 
0215     /* the size is invalid if it is smaller than the number of
0216      * elements already inside the hash table */
0217     if (dictIsRehashing(d) || d->ht[0].used > size)
0218         return DICT_ERR;
0219 
0220     /* Allocate the new hash table and initialize all pointers to NULL */
0221     n.size = realsize;
0222     n.sizemask = realsize-1;
0223     n.table = zcalloc(realsize*sizeof(dictEntry*));
0224     n.used = 0;
0225 
0226     /* Is this the first initialization? If so it's not really a rehashing
0227      * we just set the first hash table so that it can accept keys. */
0228     if (d->ht[0].table == NULL) {
0229         d->ht[0] = n;
0230         return DICT_OK;
0231     }
0232 
0233     /* Prepare a second hash table for incremental rehashing */
0234     d->ht[1] = n;
0235     d->rehashidx = 0;
0236     return DICT_OK;
0237 }
0238 
0239 /* Performs N steps of incremental rehashing. Returns 1 if there are still
0240  * keys to move from the old to the new hash table, otherwise 0 is returned.
0241  * Note that a rehashing step consists in moving a bucket (that may have more
0242  * thank one key as we use chaining) from the old to the new hash table. */
0243 int dictRehash(dict *d, int n) {
0244     if (!dictIsRehashing(d)) return 0;
0245 
0246     while(n--) {
0247         dictEntry *de, *nextde;
0248 
0249         /* Check if we already rehashed the whole table... */
0250         if (d->ht[0].used == 0) {
0251             zfree(d->ht[0].table);
0252             d->ht[0] = d->ht[1];
0253             _dictReset(&d->ht[1]);
0254             d->rehashidx = -1;
0255             return 0;
0256         }
0257 
0258         /* Note that rehashidx can't overflow as we are sure there are more
0259          * elements because ht[0].used != 0 */
0260         assert(d->ht[0].size > (unsigned)d->rehashidx);
0261         while(d->ht[0].table[d->rehashidx] == NULL) d->rehashidx++;
0262         de = d->ht[0].table[d->rehashidx];
0263         /* Move all the keys in this bucket from the old to the new hash HT */
0264         while(de) {
0265             unsigned int h;
0266 
0267             nextde = de->next;
0268             /* Get the index in the new hash table */
0269             h = dictHashKey(d, de->key) & d->ht[1].sizemask;
0270             de->next = d->ht[1].table[h];
0271             d->ht[1].table[h] = de;
0272             d->ht[0].used--;
0273             d->ht[1].used++;
0274             de = nextde;
0275         }
0276         d->ht[0].table[d->rehashidx] = NULL;
0277         d->rehashidx++;
0278     }
0279     return 1;
0280 }
0281 
0282 long long timeInMilliseconds(void) {
0283     struct timeval tv;
0284 
0285     gettimeofday(&tv,NULL);
0286     return (((long long)tv.tv_sec)*1000)+(tv.tv_usec/1000);
0287 }
0288 
0289 /* Rehash for an amount of time between ms milliseconds and ms+1 milliseconds */
0290 int dictRehashMilliseconds(dict *d, int ms) {
0291     long long start = timeInMilliseconds();
0292     int rehashes = 0;
0293 
0294     while(dictRehash(d,100)) {
0295         rehashes += 100;
0296         if (timeInMilliseconds()-start > ms) break;
0297     }
0298     return rehashes;
0299 }
0300 
0301 /* This function performs just a step of rehashing, and only if there are
0302  * no safe iterators bound to our hash table. When we have iterators in the
0303  * middle of a rehashing we can't mess with the two hash tables otherwise
0304  * some element can be missed or duplicated.
0305  *
0306  * This function is called by common lookup or update operations in the
0307  * dictionary so that the hash table automatically migrates from H1 to H2
0308  * while it is actively used. */
0309 static void _dictRehashStep(dict *d) {
0310     if (d->iterators == 0) dictRehash(d,1);
0311 }
0312 
0313 /* Add an element to the target hash table */
0314 int dictAdd(dict *d, void *key, void *val)
0315 {
0316     dictEntry *entry = dictAddRaw(d,key);
0317 
0318     if (!entry) return DICT_ERR;
0319     dictSetVal(d, entry, val);
0320     return DICT_OK;
0321 }
0322 
0323 /* Low level add. This function adds the entry but instead of setting
0324  * a value returns the dictEntry structure to the user, that will make
0325  * sure to fill the value field as he wishes.
0326  *
0327  * This function is also directly exposed to user API to be called
0328  * mainly in order to store non-pointers inside the hash value, example:
0329  *
0330  * entry = dictAddRaw(dict,mykey);
0331  * if (entry != NULL) dictSetSignedIntegerVal(entry,1000);
0332  *
0333  * Return values:
0334  *
0335  * If key already exists NULL is returned.
0336  * If key was added, the hash entry is returned to be manipulated by the caller.
0337  */
0338 dictEntry *dictAddRaw(dict *d, void *key)
0339 {
0340     int index;
0341     dictEntry *entry;
0342     dictht *ht;
0343 
0344     if (dictIsRehashing(d)) _dictRehashStep(d);
0345 
0346     /* Get the index of the new element, or -1 if
0347      * the element already exists. */
0348     if ((index = _dictKeyIndex(d, key)) == -1)
0349         return NULL;
0350 
0351     /* Allocate the memory and store the new entry */
0352     ht = dictIsRehashing(d) ? &d->ht[1] : &d->ht[0];
0353     entry = zmalloc(sizeof(*entry));
0354     entry->next = ht->table[index];
0355     ht->table[index] = entry;
0356     ht->used++;
0357 
0358     /* Set the hash entry fields. */
0359     dictSetKey(d, entry, key);
0360     return entry;
0361 }
0362 
0363 /* Add an element, discarding the old if the key already exists.
0364  * Return 1 if the key was added from scratch, 0 if there was already an
0365  * element with such key and dictReplace() just performed a value update
0366  * operation. */
0367 int dictReplace(dict *d, void *key, void *val)
0368 {
0369     dictEntry *entry, auxentry;
0370 
0371     /* Try to add the element. If the key
0372      * does not exists dictAdd will suceed. */
0373     if (dictAdd(d, key, val) == DICT_OK)
0374         return 1;
0375     /* It already exists, get the entry */
0376     entry = dictFind(d, key);
0377     /* Set the new value and free the old one. Note that it is important
0378      * to do that in this order, as the value may just be exactly the same
0379      * as the previous one. In this context, think to reference counting,
0380      * you want to increment (set), and then decrement (free), and not the
0381      * reverse. */
0382     auxentry = *entry;
0383     dictSetVal(d, entry, val);
0384     dictFreeVal(d, &auxentry);
0385     return 0;
0386 }
0387 
0388 /* dictReplaceRaw() is simply a version of dictAddRaw() that always
0389  * returns the hash entry of the specified key, even if the key already
0390  * exists and can't be added (in that case the entry of the already
0391  * existing key is returned.)
0392  *
0393  * See dictAddRaw() for more information. */
0394 dictEntry *dictReplaceRaw(dict *d, void *key) {
0395     dictEntry *entry = dictFind(d,key);
0396 
0397     return entry ? entry : dictAddRaw(d,key);
0398 }
0399 
0400 /* Search and remove an element */
0401 static int dictGenericDelete(dict *d, const void *key, int nofree)
0402 {
0403     unsigned int h, idx;
0404     dictEntry *he, *prevHe;
0405     int table;
0406 
0407     if (d->ht[0].size == 0) return DICT_ERR; /* d->ht[0].table is NULL */
0408     if (dictIsRehashing(d)) _dictRehashStep(d);
0409     h = dictHashKey(d, key);
0410 
0411     for (table = 0; table <= 1; table++) {
0412         idx = h & d->ht[table].sizemask;
0413         he = d->ht[table].table[idx];
0414         prevHe = NULL;
0415         while(he) {
0416             if (dictCompareKeys(d, key, he->key)) {
0417                 /* Unlink the element from the list */
0418                 if (prevHe)
0419                     prevHe->next = he->next;
0420                 else
0421                     d->ht[table].table[idx] = he->next;
0422                 if (!nofree) {
0423                     dictFreeKey(d, he);
0424                     dictFreeVal(d, he);
0425                 }
0426                 zfree(he);
0427                 d->ht[table].used--;
0428                 return DICT_OK;
0429             }
0430             prevHe = he;
0431             he = he->next;
0432         }
0433         if (!dictIsRehashing(d)) break;
0434     }
0435     return DICT_ERR; /* not found */
0436 }
0437 
0438 int dictDelete(dict *ht, const void *key) {
0439     return dictGenericDelete(ht,key,0);
0440 }
0441 
0442 int dictDeleteNoFree(dict *ht, const void *key) {
0443     return dictGenericDelete(ht,key,1);
0444 }
0445 
0446 /* Destroy an entire dictionary */
0447 int _dictClear(dict *d, dictht *ht)
0448 {
0449     unsigned long i;
0450 
0451     /* Free all the elements */
0452     for (i = 0; i < ht->size && ht->used > 0; i++) {
0453         dictEntry *he, *nextHe;
0454 
0455         if ((he = ht->table[i]) == NULL) continue;
0456         while(he) {
0457             nextHe = he->next;
0458             dictFreeKey(d, he);
0459             dictFreeVal(d, he);
0460             zfree(he);
0461             ht->used--;
0462             he = nextHe;
0463         }
0464     }
0465     /* Free the table and the allocated cache structure */
0466     zfree(ht->table);
0467     /* Re-initialize the table */
0468     _dictReset(ht);
0469     return DICT_OK; /* never fails */
0470 }
0471 
0472 /* Clear & Release the hash table */
0473 void dictRelease(dict *d)
0474 {
0475     _dictClear(d,&d->ht[0]);
0476     _dictClear(d,&d->ht[1]);
0477     zfree(d);
0478 }
0479 
0480 dictEntry *dictFind(dict *d, const void *key)
0481 {
0482     dictEntry *he;
0483     unsigned int h, idx, table;
0484 
0485     if (d->ht[0].size == 0) return NULL; /* We don't have a table at all */
0486     if (dictIsRehashing(d)) _dictRehashStep(d);
0487     h = dictHashKey(d, key);
0488     for (table = 0; table <= 1; table++) {
0489         idx = h & d->ht[table].sizemask;
0490         he = d->ht[table].table[idx];
0491         while(he) {
0492             if (dictCompareKeys(d, key, he->key))
0493                 return he;
0494             he = he->next;
0495         }
0496         if (!dictIsRehashing(d)) return NULL;
0497     }
0498     return NULL;
0499 }
0500 
0501 void *dictFetchValue(dict *d, const void *key) {
0502     dictEntry *he;
0503 
0504     he = dictFind(d,key);
0505     return he ? dictGetVal(he) : NULL;
0506 }
0507 
0508 dictIterator *dictGetIterator(dict *d)
0509 {
0510     dictIterator *iter = zmalloc(sizeof(*iter));
0511 
0512     iter->d = d;
0513     iter->table = 0;
0514     iter->index = -1;
0515     iter->safe = 0;
0516     iter->entry = NULL;
0517     iter->nextEntry = NULL;
0518     return iter;
0519 }
0520 
0521 dictIterator *dictGetSafeIterator(dict *d) {
0522     dictIterator *i = dictGetIterator(d);
0523 
0524     i->safe = 1;
0525     return i;
0526 }
0527 
0528 dictEntry *dictNext(dictIterator *iter)
0529 {
0530     while (1) {
0531         if (iter->entry == NULL) {
0532             dictht *ht = &iter->d->ht[iter->table];
0533             if (iter->safe && iter->index == -1 && iter->table == 0)
0534                 iter->d->iterators++;
0535             iter->index++;
0536             if (iter->index >= (signed) ht->size) {
0537                 if (dictIsRehashing(iter->d) && iter->table == 0) {
0538                     iter->table++;
0539                     iter->index = 0;
0540                     ht = &iter->d->ht[1];
0541                 } else {
0542                     break;
0543                 }
0544             }
0545             iter->entry = ht->table[iter->index];
0546         } else {
0547             iter->entry = iter->nextEntry;
0548         }
0549         if (iter->entry) {
0550             /* We need to save the 'next' here, the iterator user
0551              * may delete the entry we are returning. */
0552             iter->nextEntry = iter->entry->next;
0553             return iter->entry;
0554         }
0555     }
0556     return NULL;
0557 }
0558 
0559 void dictReleaseIterator(dictIterator *iter)
0560 {
0561     if (iter->safe && !(iter->index == -1 && iter->table == 0))
0562         iter->d->iterators--;
0563     zfree(iter);
0564 }
0565 
0566 /* Return a random entry from the hash table. Useful to
0567  * implement randomized algorithms */
0568 dictEntry *dictGetRandomKey(dict *d)
0569 {
0570     dictEntry *he, *orighe;
0571     unsigned int h;
0572     int listlen, listele;
0573 
0574     if (dictSize(d) == 0) return NULL;
0575     if (dictIsRehashing(d)) _dictRehashStep(d);
0576     if (dictIsRehashing(d)) {
0577         do {
0578             h = random() % (d->ht[0].size+d->ht[1].size);
0579             he = (h >= d->ht[0].size) ? d->ht[1].table[h - d->ht[0].size] :
0580                                       d->ht[0].table[h];
0581         } while(he == NULL);
0582     } else {
0583         do {
0584             h = random() & d->ht[0].sizemask;
0585             he = d->ht[0].table[h];
0586         } while(he == NULL);
0587     }
0588 
0589     /* Now we found a non empty bucket, but it is a linked
0590      * list and we need to get a random element from the list.
0591      * The only sane way to do so is counting the elements and
0592      * select a random index. */
0593     listlen = 0;
0594     orighe = he;
0595     while(he) {
0596         he = he->next;
0597         listlen++;
0598     }
0599     listele = random() % listlen;
0600     he = orighe;
0601     while(listele--) he = he->next;
0602     return he;
0603 }
0604 
0605 /* ------------------------- private functions ------------------------------ */
0606 
0607 /* Expand the hash table if needed */
0608 static int _dictExpandIfNeeded(dict *d)
0609 {
0610     /* Incremental rehashing already in progress. Return. */
0611     if (dictIsRehashing(d)) return DICT_OK;
0612 
0613     /* If the hash table is empty expand it to the initial size. */
0614     if (d->ht[0].size == 0) return dictExpand(d, DICT_HT_INITIAL_SIZE);
0615 
0616     /* If we reached the 1:1 ratio, and we are allowed to resize the hash
0617      * table (global setting) or we should avoid it but the ratio between
0618      * elements/buckets is over the "safe" threshold, we resize doubling
0619      * the number of buckets. */
0620     if (d->ht[0].used >= d->ht[0].size &&
0621         (dict_can_resize ||
0622          d->ht[0].used/d->ht[0].size > dict_force_resize_ratio))
0623     {
0624         return dictExpand(d, ((d->ht[0].size > d->ht[0].used) ?
0625                                     d->ht[0].size : d->ht[0].used)*2);
0626     }
0627     return DICT_OK;
0628 }
0629 
0630 /* Our hash table capability is a power of two */
0631 static unsigned long _dictNextPower(unsigned long size)
0632 {
0633     unsigned long i = DICT_HT_INITIAL_SIZE;
0634 
0635     if (size >= LONG_MAX) return LONG_MAX;
0636     while(1) {
0637         if (i >= size)
0638             return i;
0639         i *= 2;
0640     }
0641 }
0642 
0643 /* Returns the index of a free slot that can be populated with
0644  * an hash entry for the given 'key'.
0645  * If the key already exists, -1 is returned.
0646  *
0647  * Note that if we are in the process of rehashing the hash table, the
0648  * index is always returned in the context of the second (new) hash table. */
0649 static int _dictKeyIndex(dict *d, const void *key)
0650 {
0651     unsigned int h, idx, table;
0652     dictEntry *he;
0653 
0654     /* Expand the hash table if needed */
0655     if (_dictExpandIfNeeded(d) == DICT_ERR)
0656         return -1;
0657     /* Compute the key hash value */
0658     h = dictHashKey(d, key);
0659     for (table = 0; table <= 1; table++) {
0660         idx = h & d->ht[table].sizemask;
0661         /* Search if this slot does not already contain the given key */
0662         he = d->ht[table].table[idx];
0663         while(he) {
0664             if (dictCompareKeys(d, key, he->key))
0665                 return -1;
0666             he = he->next;
0667         }
0668         if (!dictIsRehashing(d)) break;
0669     }
0670     return idx;
0671 }
0672 
0673 void dictEmpty(dict *d) {
0674     _dictClear(d,&d->ht[0]);
0675     _dictClear(d,&d->ht[1]);
0676     d->rehashidx = -1;
0677     d->iterators = 0;
0678 }
0679 
0680 void dictEnableResize(void) {
0681     dict_can_resize = 1;
0682 }
0683 
0684 void dictDisableResize(void) {
0685     dict_can_resize = 0;
0686 }
0687 
0688 #if 0
0689 
0690 /* The following is code that we don't use for Redis currently, but that is part
0691 of the library. */
0692 
0693 /* ----------------------- Debugging ------------------------*/
0694 
0695 #define DICT_STATS_VECTLEN 50
0696 static void _dictPrintStatsHt(dictht *ht) {
0697     unsigned long i, slots = 0, chainlen, maxchainlen = 0;
0698     unsigned long totchainlen = 0;
0699     unsigned long clvector[DICT_STATS_VECTLEN];
0700 
0701     if (ht->used == 0) {
0702         printf("No stats available for empty dictionaries\n");
0703         return;
0704     }
0705 
0706     for (i = 0; i < DICT_STATS_VECTLEN; i++) clvector[i] = 0;
0707     for (i = 0; i < ht->size; i++) {
0708         dictEntry *he;
0709 
0710         if (ht->table[i] == NULL) {
0711             clvector[0]++;
0712             continue;
0713         }
0714         slots++;
0715         /* For each hash entry on this slot... */
0716         chainlen = 0;
0717         he = ht->table[i];
0718         while(he) {
0719             chainlen++;
0720             he = he->next;
0721         }
0722         clvector[(chainlen < DICT_STATS_VECTLEN) ? chainlen : (DICT_STATS_VECTLEN-1)]++;
0723         if (chainlen > maxchainlen) maxchainlen = chainlen;
0724         totchainlen += chainlen;
0725     }
0726     printf("Hash table stats:\n");
0727     printf(" table size: %ld\n", ht->size);
0728     printf(" number of elements: %ld\n", ht->used);
0729     printf(" different slots: %ld\n", slots);
0730     printf(" max chain length: %ld\n", maxchainlen);
0731     printf(" avg chain length (counted): %.02f\n", (float)totchainlen/slots);
0732     printf(" avg chain length (computed): %.02f\n", (float)ht->used/slots);
0733     printf(" Chain length distribution:\n");
0734     for (i = 0; i < DICT_STATS_VECTLEN-1; i++) {
0735         if (clvector[i] == 0) continue;
0736         printf("   %s%ld: %ld (%.02f%%)\n",(i == DICT_STATS_VECTLEN-1)?">= ":"", i, clvector[i], ((float)clvector[i]/ht->size)*100);
0737     }
0738 }
0739 
0740 void dictPrintStats(dict *d) {
0741     _dictPrintStatsHt(&d->ht[0]);
0742     if (dictIsRehashing(d)) {
0743         printf("-- Rehashing into ht[1]:\n");
0744         _dictPrintStatsHt(&d->ht[1]);
0745     }
0746 }
0747 
0748 /* ----------------------- StringCopy Hash Table Type ------------------------*/
0749 
0750 static unsigned int _dictStringCopyHTHashFunction(const void *key)
0751 {
0752     return dictGenHashFunction(key, strlen(key));
0753 }
0754 
0755 static void *_dictStringDup(void *privdata, const void *key)
0756 {
0757     int len = strlen(key);
0758     char *copy = zmalloc(len+1);
0759     DICT_NOTUSED(privdata);
0760 
0761     memcpy(copy, key, len);
0762     copy[len] = '\0';
0763     return copy;
0764 }
0765 
0766 static int _dictStringCopyHTKeyCompare(void *privdata, const void *key1,
0767         const void *key2)
0768 {
0769     DICT_NOTUSED(privdata);
0770 
0771     return strcmp(key1, key2) == 0;
0772 }
0773 
0774 static void _dictStringDestructor(void *privdata, void *key)
0775 {
0776     DICT_NOTUSED(privdata);
0777 
0778     zfree(key);
0779 }
0780 
0781 dictType dictTypeHeapStringCopyKey = {
0782     _dictStringCopyHTHashFunction, /* hash function */
0783     _dictStringDup,                /* key dup */
0784     NULL,                          /* val dup */
0785     _dictStringCopyHTKeyCompare,   /* key compare */
0786     _dictStringDestructor,         /* key destructor */
0787     NULL                           /* val destructor */
0788 };
0789 
0790 /* This is like StringCopy but does not auto-duplicate the key.
0791  * It's used for intepreter's shared strings. */
0792 dictType dictTypeHeapStrings = {
0793     _dictStringCopyHTHashFunction, /* hash function */
0794     NULL,                          /* key dup */
0795     NULL,                          /* val dup */
0796     _dictStringCopyHTKeyCompare,   /* key compare */
0797     _dictStringDestructor,         /* key destructor */
0798     NULL                           /* val destructor */
0799 };
0800 
0801 /* This is like StringCopy but also automatically handle dynamic
0802  * allocated C strings as values. */
0803 dictType dictTypeHeapStringCopyKeyValue = {
0804     _dictStringCopyHTHashFunction, /* hash function */
0805     _dictStringDup,                /* key dup */
0806     _dictStringDup,                /* val dup */
0807     _dictStringCopyHTKeyCompare,   /* key compare */
0808     _dictStringDestructor,         /* key destructor */
0809     _dictStringDestructor,         /* val destructor */
0810 };
0811 #endif