Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with HTTPS or Subversion.

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