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 0 : unsigned int dictIntHashFunction(unsigned int key)
72 : {
73 0 : key += ~(key << 15);
74 0 : key ^= (key >> 10);
75 0 : key += (key << 3);
76 0 : key ^= (key >> 6);
77 0 : key += ~(key << 11);
78 0 : key ^= (key >> 16);
79 0 : return key;
80 : }
81 :
82 : /* Identity hash function for integer keys */
83 0 : unsigned int dictIdentityHashFunction(unsigned int key)
84 : {
85 0 : return key;
86 : }
87 :
88 : static int dict_hash_function_seed = 5381;
89 :
90 53 : void dictSetHashFunctionSeed(unsigned int seed) {
91 53 : dict_hash_function_seed = seed;
92 53 : }
93 :
94 0 : unsigned int dictGetHashFunctionSeed(void) {
95 0 : 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 8564434 : unsigned int dictGenHashFunction(const unsigned char *buf, int len) {
101 8564434 : unsigned int hash = dict_hash_function_seed;
102 :
103 166933723 : while (len--)
104 149804855 : hash = ((hash << 5) + hash) + (*buf++); /* hash * 33 + c */
105 8564434 : return hash;
106 : }
107 :
108 : /* And a case insensitive version */
109 1780223 : unsigned int dictGenCaseHashFunction(const unsigned char *buf, int len) {
110 1780223 : unsigned int hash = dict_hash_function_seed;
111 :
112 10785816 : while (len--)
113 7225370 : hash = ((hash << 5) + hash) + (tolower(*buf++)); /* hash * 33 + c */
114 1780223 : return hash;
115 : }
116 :
117 : /* ----------------------------- API implementation ------------------------- */
118 :
119 : /* Reset an hashtable already initialized with ht_init().
120 : * NOTE: This function should only called by ht_destroy(). */
121 : static void _dictReset(dictht *ht)
122 : {
123 52671 : ht->table = NULL;
124 52671 : ht->size = 0;
125 52671 : ht->sizemask = 0;
126 52671 : ht->used = 0;
127 : }
128 :
129 : /* Create a new hash table */
130 17120 : dict *dictCreate(dictType *type,
131 : void *privDataPtr)
132 : {
133 17120 : dict *d = zmalloc(sizeof(*d));
134 :
135 : _dictInit(d,type,privDataPtr);
136 17120 : return d;
137 : }
138 :
139 : /* Initialize the hash table */
140 : int _dictInit(dict *d, dictType *type,
141 : void *privDataPtr)
142 : {
143 17120 : _dictReset(&d->ht[0]);
144 17120 : _dictReset(&d->ht[1]);
145 17120 : d->type = type;
146 17120 : d->privdata = privDataPtr;
147 17120 : d->rehashidx = -1;
148 17120 : d->iterators = 0;
149 17120 : 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 433 : int dictResize(dict *d)
155 : {
156 : int minimal;
157 :
158 433 : if (!dict_can_resize || dictIsRehashing(d)) return DICT_ERR;
159 34 : minimal = d->ht[0].used;
160 34 : if (minimal < DICT_HT_INITIAL_SIZE)
161 10 : minimal = DICT_HT_INITIAL_SIZE;
162 34 : return dictExpand(d, minimal);
163 : }
164 :
165 : /* Expand or create the hashtable */
166 13208 : int dictExpand(dict *d, unsigned long size)
167 : {
168 : dictht n; /* the new hashtable */
169 13208 : unsigned long realsize = _dictNextPower(size);
170 :
171 : /* the size is invalid if it is smaller than the number of
172 : * elements already inside the hashtable */
173 13208 : if (dictIsRehashing(d) || d->ht[0].used > size)
174 0 : return DICT_ERR;
175 :
176 : /* Allocate the new hashtable and initialize all pointers to NULL */
177 13208 : n.size = realsize;
178 13208 : n.sizemask = realsize-1;
179 13208 : n.table = zcalloc(realsize*sizeof(dictEntry*));
180 13208 : 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 13208 : if (d->ht[0].table == NULL) {
185 11771 : d->ht[0] = n;
186 11771 : return DICT_OK;
187 : }
188 :
189 : /* Prepare a second hash table for incremental rehashing */
190 1437 : d->ht[1] = n;
191 1437 : d->rehashidx = 0;
192 1437 : 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 1232079 : int dictRehash(dict *d, int n) {
200 1232079 : if (!dictIsRehashing(d)) return 0;
201 :
202 2738837 : while(n--) {
203 : dictEntry *de, *nextde;
204 :
205 : /* Check if we already rehashed the whole table... */
206 1507957 : if (d->ht[0].used == 0) {
207 1199 : zfree(d->ht[0].table);
208 1199 : d->ht[0] = d->ht[1];
209 1199 : _dictReset(&d->ht[1]);
210 1199 : d->rehashidx = -1;
211 1199 : 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 1506758 : assert(d->ht[0].size > (unsigned)d->rehashidx);
217 984421 : while(d->ht[0].table[d->rehashidx] == NULL) d->rehashidx++;
218 1506758 : de = d->ht[0].table[d->rehashidx];
219 : /* Move all the keys in this bucket from the old to the new hash HT */
220 5464287 : while(de) {
221 : unsigned int h;
222 :
223 2450771 : nextde = de->next;
224 : /* Get the index in the new hash table */
225 2450771 : h = dictHashKey(d, de->key) & d->ht[1].sizemask;
226 2450771 : de->next = d->ht[1].table[h];
227 2450771 : d->ht[1].table[h] = de;
228 2450771 : d->ht[0].used--;
229 2450771 : d->ht[1].used++;
230 2450771 : de = nextde;
231 : }
232 1506758 : d->ht[0].table[d->rehashidx] = NULL;
233 1506758 : d->rehashidx++;
234 : }
235 1230880 : return 1;
236 : }
237 :
238 2834 : long long timeInMilliseconds(void) {
239 : struct timeval tv;
240 :
241 2834 : gettimeofday(&tv,NULL);
242 2834 : 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 67 : int dictRehashMilliseconds(dict *d, int ms) {
247 67 : long long start = timeInMilliseconds();
248 67 : int rehashes = 0;
249 :
250 2880 : while(dictRehash(d,100)) {
251 2767 : rehashes += 100;
252 2767 : if (timeInMilliseconds()-start > ms) break;
253 : }
254 67 : 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 1229266 : if (d->iterators == 0) dictRehash(d,1);
267 : }
268 :
269 : /* Add an element to the target hash table */
270 1998552 : int dictAdd(dict *d, void *key, void *val)
271 : {
272 1998552 : dictEntry *entry = dictAddRaw(d,key);
273 :
274 1998552 : if (!entry) return DICT_ERR;
275 1980278 : dictSetVal(d, entry, val);
276 1980278 : 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);
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 2017851 : dictEntry *dictAddRaw(dict *d, void *key)
295 : {
296 : int index;
297 : dictEntry *entry;
298 : dictht *ht;
299 :
300 2017851 : if (dictIsRehashing(d)) _dictRehashStep(d);
301 :
302 : /* Get the index of the new element, or -1 if
303 : * the element already exists. */
304 2017851 : if ((index = _dictKeyIndex(d, key)) == -1)
305 18274 : return NULL;
306 :
307 : /* Allocate the memory and store the new entry */
308 1999577 : ht = dictIsRehashing(d) ? &d->ht[1] : &d->ht[0];
309 1999577 : entry = zmalloc(sizeof(*entry));
310 1999577 : entry->next = ht->table[index];
311 1999577 : ht->table[index] = entry;
312 1999577 : ht->used++;
313 :
314 : /* Set the hash entry fields. */
315 1999577 : dictSetKey(d, entry, key);
316 1999577 : 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 22092 : 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 22092 : if (dictAdd(d, key, val) == DICT_OK)
330 4552 : return 1;
331 : /* It already exists, get the entry */
332 17540 : 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 17540 : auxentry = *entry;
339 17540 : dictSetVal(d, entry, val);
340 17540 : dictFreeVal(d, &auxentry);
341 17540 : 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 19301 : dictEntry *dictReplaceRaw(dict *d, void *key) {
351 19301 : dictEntry *entry = dictFind(d,key);
352 :
353 19301 : return entry ? entry : dictAddRaw(d,key);
354 : }
355 :
356 : /* Search and remove an element */
357 953152 : 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 953152 : if (d->ht[0].size == 0) return DICT_ERR; /* d->ht[0].table is NULL */
364 233643 : if (dictIsRehashing(d)) _dictRehashStep(d);
365 233643 : h = dictHashKey(d, key);
366 :
367 242134 : for (table = 0; table <= 1; table++) {
368 238799 : idx = h & d->ht[table].sizemask;
369 238799 : he = d->ht[table].table[idx];
370 238799 : prevHe = NULL;
371 605052 : while(he) {
372 207275 : if (dictCompareKeys(d, key, he->key)) {
373 : /* Unlink the element from the list */
374 79821 : if (prevHe)
375 8615 : prevHe->next = he->next;
376 : else
377 71206 : d->ht[table].table[idx] = he->next;
378 79821 : if (!nofree) {
379 79821 : dictFreeKey(d, he);
380 79821 : dictFreeVal(d, he);
381 : }
382 79821 : zfree(he);
383 79821 : d->ht[table].used--;
384 79821 : return DICT_OK;
385 : }
386 127454 : prevHe = he;
387 127454 : he = he->next;
388 : }
389 158978 : if (!dictIsRehashing(d)) break;
390 : }
391 153822 : return DICT_ERR; /* not found */
392 : }
393 :
394 953152 : int dictDelete(dict *ht, const void *key) {
395 953152 : return dictGenericDelete(ht,key,0);
396 : }
397 :
398 0 : int dictDeleteNoFree(dict *ht, const void *key) {
399 0 : return dictGenericDelete(ht,key,1);
400 : }
401 :
402 : /* Destroy an entire dictionary */
403 17232 : int _dictClear(dict *d, dictht *ht)
404 : {
405 : unsigned long i;
406 :
407 : /* Free all the elements */
408 263225 : for (i = 0; i < ht->size && ht->used > 0; i++) {
409 : dictEntry *he, *nextHe;
410 :
411 245993 : if ((he = ht->table[i]) == NULL) continue;
412 278690 : while(he) {
413 169500 : nextHe = he->next;
414 169500 : dictFreeKey(d, he);
415 169500 : dictFreeVal(d, he);
416 169500 : zfree(he);
417 169500 : ht->used--;
418 169500 : he = nextHe;
419 : }
420 : }
421 : /* Free the table and the allocated cache structure */
422 17232 : zfree(ht->table);
423 : /* Re-initialize the table */
424 : _dictReset(ht);
425 17232 : return DICT_OK; /* never fails */
426 : }
427 :
428 : /* Clear & Release the hash table */
429 6308 : void dictRelease(dict *d)
430 : {
431 6308 : _dictClear(d,&d->ht[0]);
432 6308 : _dictClear(d,&d->ht[1]);
433 6308 : zfree(d);
434 6308 : }
435 :
436 5687199 : dictEntry *dictFind(dict *d, const void *key)
437 : {
438 : dictEntry *he;
439 : unsigned int h, idx, table;
440 :
441 5687199 : if (d->ht[0].size == 0) return NULL; /* We don't have a table at all */
442 5642392 : if (dictIsRehashing(d)) _dictRehashStep(d);
443 5642392 : h = dictHashKey(d, key);
444 6245109 : for (table = 0; table <= 1; table++) {
445 6008447 : idx = h & d->ht[table].sizemask;
446 6008447 : he = d->ht[table].table[idx];
447 14660180 : while(he) {
448 6098215 : if (dictCompareKeys(d, key, he->key))
449 3454929 : return he;
450 2643286 : he = he->next;
451 : }
452 2553518 : if (!dictIsRehashing(d)) return NULL;
453 : }
454 236662 : return NULL;
455 : }
456 :
457 1762161 : void *dictFetchValue(dict *d, const void *key) {
458 : dictEntry *he;
459 :
460 1762161 : he = dictFind(d,key);
461 1762161 : return he ? dictGetVal(he) : NULL;
462 : }
463 :
464 31493 : dictIterator *dictGetIterator(dict *d)
465 : {
466 31493 : dictIterator *iter = zmalloc(sizeof(*iter));
467 :
468 31493 : iter->d = d;
469 31493 : iter->table = 0;
470 31493 : iter->index = -1;
471 31493 : iter->safe = 0;
472 31493 : iter->entry = NULL;
473 31493 : iter->nextEntry = NULL;
474 31493 : return iter;
475 : }
476 :
477 151 : dictIterator *dictGetSafeIterator(dict *d) {
478 151 : dictIterator *i = dictGetIterator(d);
479 :
480 151 : i->safe = 1;
481 151 : return i;
482 : }
483 :
484 12555080 : dictEntry *dictNext(dictIterator *iter)
485 : {
486 : while (1) {
487 12555080 : if (iter->entry == NULL) {
488 7126069 : dictht *ht = &iter->d->ht[iter->table];
489 7126069 : if (iter->safe && iter->index == -1 && iter->table == 0)
490 151 : iter->d->iterators++;
491 7126069 : iter->index++;
492 7126069 : if (iter->index >= (signed) ht->size) {
493 32030 : if (dictIsRehashing(iter->d) && iter->table == 0) {
494 537 : iter->table++;
495 537 : iter->index = 0;
496 537 : ht = &iter->d->ht[1];
497 : } else {
498 : break;
499 : }
500 : }
501 7094576 : iter->entry = ht->table[iter->index];
502 : } else {
503 5429011 : iter->entry = iter->nextEntry;
504 : }
505 12523587 : if (iter->entry) {
506 : /* We need to save the 'next' here, the iterator user
507 : * may delete the entry we are returning. */
508 5429011 : iter->nextEntry = iter->entry->next;
509 5429011 : return iter->entry;
510 : }
511 : }
512 31493 : return NULL;
513 : }
514 :
515 31493 : void dictReleaseIterator(dictIterator *iter)
516 : {
517 31493 : if (iter->safe && !(iter->index == -1 && iter->table == 0))
518 151 : iter->d->iterators--;
519 31493 : zfree(iter);
520 31493 : }
521 :
522 : /* Return a random entry from the hash table. Useful to
523 : * implement randomized algorithms */
524 48320 : dictEntry *dictGetRandomKey(dict *d)
525 : {
526 : dictEntry *he, *orighe;
527 : unsigned int h;
528 : int listlen, listele;
529 :
530 48320 : if (dictSize(d) == 0) return NULL;
531 48318 : if (dictIsRehashing(d)) _dictRehashStep(d);
532 48318 : if (dictIsRehashing(d)) {
533 : do {
534 14145 : h = random() % (d->ht[0].size+d->ht[1].size);
535 23285 : he = (h >= d->ht[0].size) ? d->ht[1].table[h - d->ht[0].size] :
536 9140 : d->ht[0].table[h];
537 14145 : } while(he == NULL);
538 : } else {
539 : do {
540 116121 : h = random() & d->ht[0].sizemask;
541 116121 : he = d->ht[0].table[h];
542 116121 : } 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 48318 : listlen = 0;
550 48318 : orighe = he;
551 169496 : while(he) {
552 72860 : he = he->next;
553 72860 : listlen++;
554 : }
555 48318 : listele = random() % listlen;
556 48318 : he = orighe;
557 48318 : while(listele--) he = he->next;
558 48318 : 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 2017851 : if (dictIsRehashing(d)) return DICT_OK;
568 :
569 : /* If the hash table is empty expand it to the intial size. */
570 1166523 : 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 1157968 : if (d->ht[0].used >= d->ht[0].size &&
577 1207 : (dict_can_resize ||
578 4 : d->ht[0].used/d->ht[0].size > dict_force_resize_ratio))
579 : {
580 1203 : return dictExpand(d, ((d->ht[0].size > d->ht[0].used) ?
581 1203 : d->ht[0].size : d->ht[0].used)*2);
582 : }
583 1155554 : 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 13208 : unsigned long i = DICT_HT_INITIAL_SIZE;
590 :
591 13208 : if (size >= LONG_MAX) return LONG_MAX;
592 : while(1) {
593 18235 : if (i >= size)
594 13208 : return i;
595 5027 : 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 2017851 : static int _dictKeyIndex(dict *d, const void *key)
606 : {
607 : unsigned int h, idx, table;
608 : dictEntry *he;
609 :
610 : /* Expand the hashtable if needed */
611 2017851 : if (_dictExpandIfNeeded(d) == DICT_ERR)
612 0 : return -1;
613 : /* Compute the key hash value */
614 2017851 : h = dictHashKey(d, key);
615 3722172 : for (table = 0; table <= 1; table++) {
616 2870113 : idx = h & d->ht[table].sizemask;
617 : /* Search if this slot does not already contain the given key */
618 2870113 : he = d->ht[table].table[idx];
619 7463057 : while(he) {
620 1741105 : if (dictCompareKeys(d, key, he->key))
621 18274 : return -1;
622 1722831 : he = he->next;
623 : }
624 2851839 : if (!dictIsRehashing(d)) break;
625 : }
626 1999577 : return idx;
627 : }
628 :
629 2308 : void dictEmpty(dict *d) {
630 2308 : _dictClear(d,&d->ht[0]);
631 2308 : _dictClear(d,&d->ht[1]);
632 2308 : d->rehashidx = -1;
633 2308 : d->iterators = 0;
634 2308 : }
635 :
636 : #define DICT_STATS_VECTLEN 50
637 0 : static void _dictPrintStatsHt(dictht *ht) {
638 0 : unsigned long i, slots = 0, chainlen, maxchainlen = 0;
639 0 : unsigned long totchainlen = 0;
640 : unsigned long clvector[DICT_STATS_VECTLEN];
641 :
642 0 : if (ht->used == 0) {
643 0 : printf("No stats available for empty dictionaries\n");
644 : return;
645 : }
646 :
647 0 : for (i = 0; i < DICT_STATS_VECTLEN; i++) clvector[i] = 0;
648 0 : for (i = 0; i < ht->size; i++) {
649 : dictEntry *he;
650 :
651 0 : if (ht->table[i] == NULL) {
652 0 : clvector[0]++;
653 0 : continue;
654 : }
655 0 : slots++;
656 : /* For each hash entry on this slot... */
657 0 : chainlen = 0;
658 0 : he = ht->table[i];
659 0 : while(he) {
660 0 : chainlen++;
661 0 : he = he->next;
662 : }
663 0 : clvector[(chainlen < DICT_STATS_VECTLEN) ? chainlen : (DICT_STATS_VECTLEN-1)]++;
664 0 : if (chainlen > maxchainlen) maxchainlen = chainlen;
665 0 : totchainlen += chainlen;
666 : }
667 0 : printf("Hash table stats:\n");
668 0 : printf(" table size: %ld\n", ht->size);
669 0 : printf(" number of elements: %ld\n", ht->used);
670 0 : printf(" different slots: %ld\n", slots);
671 0 : printf(" max chain length: %ld\n", maxchainlen);
672 0 : printf(" avg chain length (counted): %.02f\n", (float)totchainlen/slots);
673 0 : printf(" avg chain length (computed): %.02f\n", (float)ht->used/slots);
674 0 : printf(" Chain length distribution:\n");
675 0 : for (i = 0; i < DICT_STATS_VECTLEN-1; i++) {
676 0 : if (clvector[i] == 0) continue;
677 0 : printf(" %s%ld: %ld (%.02f%%)\n",(i == DICT_STATS_VECTLEN-1)?">= ":"", i, clvector[i], ((float)clvector[i]/ht->size)*100);
678 : }
679 : }
680 :
681 0 : void dictPrintStats(dict *d) {
682 0 : _dictPrintStatsHt(&d->ht[0]);
683 0 : if (dictIsRehashing(d)) {
684 0 : printf("-- Rehashing into ht[1]:\n");
685 0 : _dictPrintStatsHt(&d->ht[1]);
686 : }
687 0 : }
688 :
689 27 : void dictEnableResize(void) {
690 27 : dict_can_resize = 1;
691 27 : }
692 :
693 27 : void dictDisableResize(void) {
694 27 : dict_can_resize = 0;
695 27 : }
696 :
697 : #if 0
698 :
699 : /* The following are just example hash table types implementations.
700 : * Not useful for Redis so they are commented out.
701 : */
702 :
703 : /* ----------------------- StringCopy Hash Table Type ------------------------*/
704 :
705 : static unsigned int _dictStringCopyHTHashFunction(const void *key)
706 : {
707 : return dictGenHashFunction(key, strlen(key));
708 : }
709 :
710 : static void *_dictStringDup(void *privdata, const void *key)
711 : {
712 : int len = strlen(key);
713 : char *copy = zmalloc(len+1);
714 : DICT_NOTUSED(privdata);
715 :
716 : memcpy(copy, key, len);
717 : copy[len] = '\0';
718 : return copy;
719 : }
720 :
721 : static int _dictStringCopyHTKeyCompare(void *privdata, const void *key1,
722 : const void *key2)
723 : {
724 : DICT_NOTUSED(privdata);
725 :
726 : return strcmp(key1, key2) == 0;
727 : }
728 :
729 : static void _dictStringDestructor(void *privdata, void *key)
730 : {
731 : DICT_NOTUSED(privdata);
732 :
733 : zfree(key);
734 : }
735 :
736 : dictType dictTypeHeapStringCopyKey = {
737 : _dictStringCopyHTHashFunction, /* hash function */
738 : _dictStringDup, /* key dup */
739 : NULL, /* val dup */
740 : _dictStringCopyHTKeyCompare, /* key compare */
741 : _dictStringDestructor, /* key destructor */
742 : NULL /* val destructor */
743 : };
744 :
745 : /* This is like StringCopy but does not auto-duplicate the key.
746 : * It's used for intepreter's shared strings. */
747 : dictType dictTypeHeapStrings = {
748 : _dictStringCopyHTHashFunction, /* hash function */
749 : NULL, /* key dup */
750 : NULL, /* val dup */
751 : _dictStringCopyHTKeyCompare, /* key compare */
752 : _dictStringDestructor, /* key destructor */
753 : NULL /* val destructor */
754 : };
755 :
756 : /* This is like StringCopy but also automatically handle dynamic
757 : * allocated C strings as values. */
758 : dictType dictTypeHeapStringCopyKeyValue = {
759 : _dictStringCopyHTHashFunction, /* hash function */
760 : _dictStringDup, /* key dup */
761 : _dictStringDup, /* val dup */
762 : _dictStringCopyHTKeyCompare, /* key compare */
763 : _dictStringDestructor, /* key destructor */
764 : _dictStringDestructor, /* val destructor */
765 : };
766 : #endif
|
