]> git.saurik.com Git - redis.git/blame - src/dict.c
Update makefile dependencies.
[redis.git] / src / dict.c
CommitLineData
ed9b544e 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 *
12d090d2 8 * Copyright (c) 2006-2010, Salvatore Sanfilippo <antirez at gmail dot com>
ed9b544e 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
23d4709d 36#include "fmacros.h"
37
ed9b544e 38#include <stdio.h>
39#include <stdlib.h>
40#include <string.h>
41#include <stdarg.h>
42#include <assert.h>
f2923bec 43#include <limits.h>
8ca3e9d1 44#include <sys/time.h>
1b1f47c9 45#include <ctype.h>
ed9b544e 46
47#include "dict.h"
48#include "zmalloc.h"
49
884d4b39 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
3856f147 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. */
884d4b39 58static int dict_can_resize = 1;
3856f147 59static unsigned int dict_force_resize_ratio = 5;
884d4b39 60
ed9b544e 61/* -------------------------- private prototypes ---------------------------- */
62
63static int _dictExpandIfNeeded(dict *ht);
f2923bec 64static unsigned long _dictNextPower(unsigned long size);
ed9b544e 65static int _dictKeyIndex(dict *ht, const void *key);
66static int _dictInit(dict *ht, dictType *type, void *privDataPtr);
67
68/* -------------------------- hash functions -------------------------------- */
69
70/* Thomas Wang's 32 bit Mix Function */
71unsigned 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 */
83unsigned int dictIdentityHashFunction(unsigned int key)
84{
85 return key;
86}
87
b362c111 88static int dict_hash_function_seed = 5381;
a48c8d87 89
90void dictSetHashFunctionSeed(unsigned int seed) {
91 dict_hash_function_seed = seed;
92}
93
94unsigned int dictGetHashFunctionSeed(void) {
95 return dict_hash_function_seed;
96}
97
ed9b544e 98/* Generic hash function (a popular one from Bernstein).
99 * I tested a few and this was the best. */
100unsigned int dictGenHashFunction(const unsigned char *buf, int len) {
a48c8d87 101 unsigned int hash = dict_hash_function_seed;
ed9b544e 102
103 while (len--)
104 hash = ((hash << 5) + hash) + (*buf++); /* hash * 33 + c */
105 return hash;
106}
107
1b1f47c9 108/* And a case insensitive version */
109unsigned int dictGenCaseHashFunction(const unsigned char *buf, int len) {
a48c8d87 110 unsigned int hash = dict_hash_function_seed;
1b1f47c9 111
112 while (len--)
113 hash = ((hash << 5) + hash) + (tolower(*buf++)); /* hash * 33 + c */
114 return hash;
115}
116
ed9b544e 117/* ----------------------------- API implementation ------------------------- */
118
119/* Reset an hashtable already initialized with ht_init().
120 * NOTE: This function should only called by ht_destroy(). */
5413c40d 121static void _dictReset(dictht *ht)
ed9b544e 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 */
130dict *dictCreate(dictType *type,
131 void *privDataPtr)
132{
d9dd352b 133 dict *d = zmalloc(sizeof(*d));
ed9b544e 134
5413c40d 135 _dictInit(d,type,privDataPtr);
136 return d;
ed9b544e 137}
138
139/* Initialize the hash table */
5413c40d 140int _dictInit(dict *d, dictType *type,
ed9b544e 141 void *privDataPtr)
142{
5413c40d 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;
ed9b544e 149 return DICT_OK;
150}
151
152/* Resize the table to the minimal size that contains all the elements,
085aaef3 153 * but with the invariant of a USED/BUCKETS ratio near to <= 1 */
5413c40d 154int dictResize(dict *d)
ed9b544e 155{
5413c40d 156 int minimal;
ed9b544e 157
5413c40d 158 if (!dict_can_resize || dictIsRehashing(d)) return DICT_ERR;
159 minimal = d->ht[0].used;
ed9b544e 160 if (minimal < DICT_HT_INITIAL_SIZE)
161 minimal = DICT_HT_INITIAL_SIZE;
5413c40d 162 return dictExpand(d, minimal);
ed9b544e 163}
164
165/* Expand or create the hashtable */
5413c40d 166int dictExpand(dict *d, unsigned long size)
ed9b544e 167{
5413c40d 168 dictht n; /* the new hashtable */
169 unsigned long realsize = _dictNextPower(size);
ed9b544e 170
171 /* the size is invalid if it is smaller than the number of
172 * elements already inside the hashtable */
5413c40d 173 if (dictIsRehashing(d) || d->ht[0].used > size)
ed9b544e 174 return DICT_ERR;
175
399f2f40 176 /* Allocate the new hashtable and initialize all pointers to NULL */
ed9b544e 177 n.size = realsize;
178 n.sizemask = realsize-1;
399f2f40 179 n.table = zcalloc(realsize*sizeof(dictEntry*));
5413c40d 180 n.used = 0;
ed9b544e 181
5413c40d 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 }
ed9b544e 188
5413c40d 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. */
199int 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) {
d9dd352b 207 zfree(d->ht[0].table);
5413c40d 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 */
05600eb8 216 assert(d->ht[0].size > (unsigned)d->rehashidx);
5413c40d 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) {
ed9b544e 221 unsigned int h;
222
5413c40d 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;
ed9b544e 231 }
5413c40d 232 d->ht[0].table[d->rehashidx] = NULL;
233 d->rehashidx++;
ed9b544e 234 }
5413c40d 235 return 1;
236}
ed9b544e 237
8ca3e9d1 238long 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 */
246int 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
5413c40d 257/* This function performs just a step of rehashing, and only if there are
4b53e736 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.
5413c40d 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. */
265static void _dictRehashStep(dict *d) {
266 if (d->iterators == 0) dictRehash(d,1);
ed9b544e 267}
268
269/* Add an element to the target hash table */
5413c40d 270int dictAdd(dict *d, void *key, void *val)
71a50956 271{
272 dictEntry *entry = dictAddRaw(d,key);
273
274 if (!entry) return DICT_ERR;
c0ba9ebe 275 dictSetVal(d, entry, val);
71a50956 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 expoed to user API to be called
284 * mainly in order to store non-pointers inside the hash value, example:
285 *
286 * entry = dictAddRaw(dict,mykey);
aa9a61cc 287 * if (entry != NULL) dictSetSignedIntegerVal(entry,1000);
71a50956 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 */
294dictEntry *dictAddRaw(dict *d, void *key)
ed9b544e 295{
296 int index;
297 dictEntry *entry;
5413c40d 298 dictht *ht;
299
300 if (dictIsRehashing(d)) _dictRehashStep(d);
ed9b544e 301
302 /* Get the index of the new element, or -1 if
303 * the element already exists. */
5413c40d 304 if ((index = _dictKeyIndex(d, key)) == -1)
71a50956 305 return NULL;
ed9b544e 306
6a7841eb 307 /* Allocate the memory and store the new entry */
5413c40d 308 ht = dictIsRehashing(d) ? &d->ht[1] : &d->ht[0];
d9dd352b 309 entry = zmalloc(sizeof(*entry));
ed9b544e 310 entry->next = ht->table[index];
311 ht->table[index] = entry;
5413c40d 312 ht->used++;
ed9b544e 313
314 /* Set the hash entry fields. */
c0ba9ebe 315 dictSetKey(d, entry, key);
71a50956 316 return entry;
ed9b544e 317}
318
121796f7 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. */
5413c40d 323int dictReplace(dict *d, void *key, void *val)
ed9b544e 324{
2069d06a 325 dictEntry *entry, auxentry;
ed9b544e 326
327 /* Try to add the element. If the key
328 * does not exists dictAdd will suceed. */
5413c40d 329 if (dictAdd(d, key, val) == DICT_OK)
121796f7 330 return 1;
ed9b544e 331 /* It already exists, get the entry */
5413c40d 332 entry = dictFind(d, key);
2069d06a 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;
c0ba9ebe 339 dictSetVal(d, entry, val);
340 dictFreeVal(d, &auxentry);
121796f7 341 return 0;
ed9b544e 342}
343
71a50956 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. */
350dictEntry *dictReplaceRaw(dict *d, void *key) {
351 dictEntry *entry = dictFind(d,key);
352
353 return entry ? entry : dictAddRaw(d,key);
354}
355
ed9b544e 356/* Search and remove an element */
5413c40d 357static int dictGenericDelete(dict *d, const void *key, int nofree)
ed9b544e 358{
5413c40d 359 unsigned int h, idx;
ed9b544e 360 dictEntry *he, *prevHe;
5413c40d 361 int table;
ed9b544e 362
5413c40d 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);
ed9b544e 366
5413c40d 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) {
c0ba9ebe 372 if (dictCompareKeys(d, key, he->key)) {
5413c40d 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) {
c0ba9ebe 379 dictFreeKey(d, he);
380 dictFreeVal(d, he);
5413c40d 381 }
d9dd352b 382 zfree(he);
5413c40d 383 d->ht[table].used--;
384 return DICT_OK;
ed9b544e 385 }
5413c40d 386 prevHe = he;
387 he = he->next;
ed9b544e 388 }
5413c40d 389 if (!dictIsRehashing(d)) break;
ed9b544e 390 }
391 return DICT_ERR; /* not found */
392}
393
394int dictDelete(dict *ht, const void *key) {
395 return dictGenericDelete(ht,key,0);
396}
397
398int dictDeleteNoFree(dict *ht, const void *key) {
399 return dictGenericDelete(ht,key,1);
400}
401
5413c40d 402/* Destroy an entire dictionary */
403int _dictClear(dict *d, dictht *ht)
ed9b544e 404{
f2923bec 405 unsigned long i;
ed9b544e 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;
c0ba9ebe 414 dictFreeKey(d, he);
415 dictFreeVal(d, he);
d9dd352b 416 zfree(he);
ed9b544e 417 ht->used--;
418 he = nextHe;
419 }
420 }
421 /* Free the table and the allocated cache structure */
d9dd352b 422 zfree(ht->table);
ed9b544e 423 /* Re-initialize the table */
424 _dictReset(ht);
425 return DICT_OK; /* never fails */
426}
427
428/* Clear & Release the hash table */
5413c40d 429void dictRelease(dict *d)
ed9b544e 430{
5413c40d 431 _dictClear(d,&d->ht[0]);
432 _dictClear(d,&d->ht[1]);
d9dd352b 433 zfree(d);
ed9b544e 434}
435
5413c40d 436dictEntry *dictFind(dict *d, const void *key)
ed9b544e 437{
438 dictEntry *he;
5413c40d 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) {
c0ba9ebe 448 if (dictCompareKeys(d, key, he->key))
5413c40d 449 return he;
450 he = he->next;
451 }
452 if (!dictIsRehashing(d)) return NULL;
ed9b544e 453 }
454 return NULL;
455}
456
58e1c9c1 457void *dictFetchValue(dict *d, const void *key) {
458 dictEntry *he;
459
460 he = dictFind(d,key);
c0ba9ebe 461 return he ? dictGetVal(he) : NULL;
58e1c9c1 462}
463
5413c40d 464dictIterator *dictGetIterator(dict *d)
ed9b544e 465{
d9dd352b 466 dictIterator *iter = zmalloc(sizeof(*iter));
ed9b544e 467
5413c40d 468 iter->d = d;
469 iter->table = 0;
ed9b544e 470 iter->index = -1;
4b53e736 471 iter->safe = 0;
ed9b544e 472 iter->entry = NULL;
473 iter->nextEntry = NULL;
474 return iter;
475}
476
4b53e736 477dictIterator *dictGetSafeIterator(dict *d) {
478 dictIterator *i = dictGetIterator(d);
479
480 i->safe = 1;
481 return i;
482}
483
ed9b544e 484dictEntry *dictNext(dictIterator *iter)
485{
486 while (1) {
487 if (iter->entry == NULL) {
5413c40d 488 dictht *ht = &iter->d->ht[iter->table];
4b53e736 489 if (iter->safe && iter->index == -1 && iter->table == 0)
490 iter->d->iterators++;
ed9b544e 491 iter->index++;
5413c40d 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];
ed9b544e 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
515void dictReleaseIterator(dictIterator *iter)
516{
4b53e736 517 if (iter->safe && !(iter->index == -1 && iter->table == 0))
518 iter->d->iterators--;
d9dd352b 519 zfree(iter);
ed9b544e 520}
521
522/* Return a random entry from the hash table. Useful to
523 * implement randomized algorithms */
5413c40d 524dictEntry *dictGetRandomKey(dict *d)
ed9b544e 525{
5413c40d 526 dictEntry *he, *orighe;
ed9b544e 527 unsigned int h;
528 int listlen, listele;
529
5413c40d 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 }
ed9b544e 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.
5413c40d 547 * The only sane way to do so is counting the elements and
ed9b544e 548 * select a random index. */
549 listlen = 0;
5413c40d 550 orighe = he;
ed9b544e 551 while(he) {
552 he = he->next;
553 listlen++;
554 }
555 listele = random() % listlen;
5413c40d 556 he = orighe;
ed9b544e 557 while(listele--) he = he->next;
558 return he;
559}
560
561/* ------------------------- private functions ------------------------------ */
562
563/* Expand the hash table if needed */
5413c40d 564static int _dictExpandIfNeeded(dict *d)
ed9b544e 565{
3856f147 566 /* Incremental rehashing already in progress. Return. */
5413c40d 567 if (dictIsRehashing(d)) return DICT_OK;
3856f147 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 {
5413c40d 580 return dictExpand(d, ((d->ht[0].size > d->ht[0].used) ?
581 d->ht[0].size : d->ht[0].used)*2);
3856f147 582 }
ed9b544e 583 return DICT_OK;
584}
585
586/* Our hash table capability is a power of two */
f2923bec 587static unsigned long _dictNextPower(unsigned long size)
ed9b544e 588{
f2923bec 589 unsigned long i = DICT_HT_INITIAL_SIZE;
ed9b544e 590
f2923bec 591 if (size >= LONG_MAX) return LONG_MAX;
ed9b544e 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'.
5413c40d 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. */
605static int _dictKeyIndex(dict *d, const void *key)
ed9b544e 606{
8ca3e9d1 607 unsigned int h, idx, table;
ed9b544e 608 dictEntry *he;
609
610 /* Expand the hashtable if needed */
5413c40d 611 if (_dictExpandIfNeeded(d) == DICT_ERR)
ed9b544e 612 return -1;
613 /* Compute the key hash value */
5413c40d 614 h = dictHashKey(d, key);
8ca3e9d1 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) {
c0ba9ebe 620 if (dictCompareKeys(d, key, he->key))
8ca3e9d1 621 return -1;
622 he = he->next;
623 }
624 if (!dictIsRehashing(d)) break;
ed9b544e 625 }
8ca3e9d1 626 return idx;
ed9b544e 627}
628
5413c40d 629void dictEmpty(dict *d) {
630 _dictClear(d,&d->ht[0]);
631 _dictClear(d,&d->ht[1]);
632 d->rehashidx = -1;
633 d->iterators = 0;
ed9b544e 634}
635
d54943b7 636void dictEnableResize(void) {
637 dict_can_resize = 1;
638}
639
640void dictDisableResize(void) {
641 dict_can_resize = 0;
642}
643
644#if 0
645
e337b260 646/* The following is code that we don't use for Redis currently, but that is part
647of the library. */
d54943b7 648
649/* ----------------------- Debugging ------------------------*/
650
ed9b544e 651#define DICT_STATS_VECTLEN 50
5413c40d 652static void _dictPrintStatsHt(dictht *ht) {
f2923bec 653 unsigned long i, slots = 0, chainlen, maxchainlen = 0;
654 unsigned long totchainlen = 0;
655 unsigned long clvector[DICT_STATS_VECTLEN];
ed9b544e 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");
f2923bec 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);
ed9b544e 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;
f2923bec 692 printf(" %s%ld: %ld (%.02f%%)\n",(i == DICT_STATS_VECTLEN-1)?">= ":"", i, clvector[i], ((float)clvector[i]/ht->size)*100);
ed9b544e 693 }
694}
695
5413c40d 696void 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
ed9b544e 704/* ----------------------- StringCopy Hash Table Type ------------------------*/
705
706static unsigned int _dictStringCopyHTHashFunction(const void *key)
707{
708 return dictGenHashFunction(key, strlen(key));
709}
710
b1e0bd4b 711static void *_dictStringDup(void *privdata, const void *key)
ed9b544e 712{
713 int len = strlen(key);
d9dd352b 714 char *copy = zmalloc(len+1);
ed9b544e 715 DICT_NOTUSED(privdata);
716
717 memcpy(copy, key, len);
718 copy[len] = '\0';
719 return copy;
720}
721
ed9b544e 722static 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
b1e0bd4b 730static void _dictStringDestructor(void *privdata, void *key)
ed9b544e 731{
732 DICT_NOTUSED(privdata);
733
d9dd352b 734 zfree(key);
ed9b544e 735}
736
737dictType dictTypeHeapStringCopyKey = {
b1e0bd4b
BK
738 _dictStringCopyHTHashFunction, /* hash function */
739 _dictStringDup, /* key dup */
740 NULL, /* val dup */
741 _dictStringCopyHTKeyCompare, /* key compare */
742 _dictStringDestructor, /* key destructor */
743 NULL /* val destructor */
ed9b544e 744};
745
746/* This is like StringCopy but does not auto-duplicate the key.
747 * It's used for intepreter's shared strings. */
748dictType dictTypeHeapStrings = {
b1e0bd4b
BK
749 _dictStringCopyHTHashFunction, /* hash function */
750 NULL, /* key dup */
751 NULL, /* val dup */
752 _dictStringCopyHTKeyCompare, /* key compare */
753 _dictStringDestructor, /* key destructor */
754 NULL /* val destructor */
ed9b544e 755};
756
757/* This is like StringCopy but also automatically handle dynamic
758 * allocated C strings as values. */
759dictType dictTypeHeapStringCopyKeyValue = {
b1e0bd4b
BK
760 _dictStringCopyHTHashFunction, /* hash function */
761 _dictStringDup, /* key dup */
762 _dictStringDup, /* val dup */
763 _dictStringCopyHTKeyCompare, /* key compare */
764 _dictStringDestructor, /* key destructor */
765 _dictStringDestructor, /* val destructor */
ed9b544e 766};
e0be2289 767#endif