1 // clang-format off
2
3 /* Hash Tables Implementation.
4 *
5 * This file implements in memory hash tables with insert/del/replace/find/
6 * get-random-element operations. Hash tables will auto resize if needed
7 * tables of power of two in size are used, collisions are handled by
8 * chaining. See the source code for more information... :)
9 *
10 * Copyright (c) 2006-2012, Salvatore Sanfilippo <antirez at gmail dot com>
11 * All rights reserved.
12 *
13 * Redistribution and use in source and binary forms, with or without
14 * modification, are permitted provided that the following conditions are met:
15 *
16 * * Redistributions of source code must retain the above copyright notice,
17 * this list of conditions and the following disclaimer.
18 * * Redistributions in binary form must reproduce the above copyright
19 * notice, this list of conditions and the following disclaimer in the
20 * documentation and/or other materials provided with the distribution.
21 * * Neither the name of Redis nor the names of its contributors may be used
22 * to endorse or promote products derived from this software without
23 * specific prior written permission.
24 *
25 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
26 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
27 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
28 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
29 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
30 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
31 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
32 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
33 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
34 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
35 * POSSIBILITY OF SUCH DAMAGE.
36 */
37
38 #include <stdio.h>
39 #include <stdlib.h>
40 #include <stdint.h>
41 #include <string.h>
42 #include <stdarg.h>
43 #include <limits.h>
44 #include <sys/time.h>
45
46 #pragma GCC visibility push(default)
47 #include "siphash.c.inc"
48 #pragma GCC visibility pop
49
50 #include "dict.h"
51 #include "redismodule.h"
52 #include <assert.h>
53 #include "../rmalloc.h"
54
stringsHashFunction(const void * key)55 static uint64_t stringsHashFunction(const void *key){
56 return dictGenHashFunction(key, strlen((char*)key));
57 }
58
redisStringsHashFunction(const void * key)59 static uint64_t redisStringsHashFunction(const void *key){
60 const RedisModuleString* keyStr = key;
61 size_t len;
62 const char* str = RedisModule_StringPtrLen(keyStr, &len);
63 return dictGenHashFunction(str, len);
64 }
65
stringsKeyCompare(void * privdata,const void * key1,const void * key2)66 static int stringsKeyCompare(void *privdata, const void *key1, const void *key2){
67 const char* strKey1 = key1;
68 const char* strKey2 = key2;
69
70 return strcmp(strKey1, strKey2) == 0;
71 }
72
redisStringsKeyCompare(void * privdata,const void * key1,const void * key2)73 static int redisStringsKeyCompare(void *privdata, const void *key1, const void *key2){
74 const RedisModuleString* strKey1 = key1;
75 const RedisModuleString* strKey2 = key2;
76
77 return RedisModule_StringCompare((RedisModuleString*)strKey1, (RedisModuleString*)strKey2) == 0;
78 }
79
stringsKeyDestructor(void * privdata,void * key)80 static void stringsKeyDestructor(void *privdata, void *key){
81 rm_free(key);
82 }
83
redisStringsKeyDestructor(void * privdata,void * key)84 static void redisStringsKeyDestructor(void *privdata, void *key){
85 const RedisModuleString* keyStr = key;
86 RedisModule_FreeString(NULL, (RedisModuleString*)keyStr);
87 }
88
stringsKeyDup(void * privdata,const void * key)89 static void* stringsKeyDup(void *privdata, const void *key){
90 return rm_strdup((char*)key);
91 }
92
redisStringsKeyDup(void * privdata,const void * key)93 static void* redisStringsKeyDup(void *privdata, const void *key){
94 const RedisModuleString* keyStr = key;
95 RedisModule_RetainString(NULL, (RedisModuleString*)keyStr);
96 return (void*)key;
97 }
98
99 dictType dictTypeHeapStrings = {
100 .hashFunction = stringsHashFunction,
101 .keyDup = stringsKeyDup,
102 .valDup = NULL,
103 .keyCompare = stringsKeyCompare,
104 .keyDestructor = stringsKeyDestructor,
105 .valDestructor = NULL,
106 };
107
108 dictType dictTypeHeapRedisStrings = {
109 .hashFunction = redisStringsHashFunction,
110 .keyDup = redisStringsKeyDup,
111 .valDup = NULL,
112 .keyCompare = redisStringsKeyCompare,
113 .keyDestructor = redisStringsKeyDestructor,
114 .valDestructor = NULL,
115 };
116
117 /* Using dictEnableResize() / dictDisableResize() we make possible to
118 * enable/disable resizing of the hash table as needed. This is very important
119 * for Redis, as we use copy-on-write and don't want to move too much memory
120 * around when there is a child performing saving operations.
121 *
122 * Note that even when dict_can_resize is set to 0, not all resizes are
123 * prevented: a hash table is still allowed to grow if the ratio between
124 * the number of elements and the buckets > dict_force_resize_ratio. */
125 static int dict_can_resize = 1;
126 static unsigned int dict_force_resize_ratio = 5;
127
128 /* -------------------------- private prototypes ---------------------------- */
129
130 static int _dictExpandIfNeeded(dict *ht);
131 static unsigned long _dictNextPower(unsigned long size);
132 static long _dictKeyIndex(dict *ht, const void *key, uint64_t hash, dictEntry **existing);
133 static int _dictInit(dict *ht, dictType *type, void *privDataPtr);
134
135 /* -------------------------- hash functions -------------------------------- */
136
137 static uint8_t dict_hash_function_seed[16];
138
dictSetHashFunctionSeed(uint8_t * seed)139 void dictSetHashFunctionSeed(uint8_t *seed) {
140 memcpy(dict_hash_function_seed,seed,sizeof(dict_hash_function_seed));
141 }
142
dictGetHashFunctionSeed(void)143 uint8_t *dictGetHashFunctionSeed(void) {
144 return dict_hash_function_seed;
145 }
146
147 /* The default hashing function uses SipHash implementation
148 * in siphash.c. */
149
150 uint64_t siphash(const uint8_t *in, const size_t inlen, const uint8_t *k);
151 uint64_t siphash_nocase(const uint8_t *in, const size_t inlen, const uint8_t *k);
152
dictGenHashFunction(const void * key,int len)153 uint64_t dictGenHashFunction(const void *key, int len) {
154 return siphash(key,len,dict_hash_function_seed);
155 }
156
dictGenCaseHashFunction(const unsigned char * buf,int len)157 uint64_t dictGenCaseHashFunction(const unsigned char *buf, int len) {
158 return siphash_nocase(buf,len,dict_hash_function_seed);
159 }
160
161 /* ----------------------------- API implementation ------------------------- */
162
163 /* Reset a hash table already initialized with ht_init().
164 * NOTE: This function should only be called by ht_destroy(). */
_dictReset(dictht * ht)165 static void _dictReset(dictht *ht)
166 {
167 ht->table = NULL;
168 ht->size = 0;
169 ht->sizemask = 0;
170 ht->used = 0;
171 }
172
173 /* Create a new hash table */
dictCreate(dictType * type,void * privDataPtr)174 dict *dictCreate(dictType *type,
175 void *privDataPtr)
176 {
177 dict *d = rm_malloc(sizeof(*d));
178
179 _dictInit(d,type,privDataPtr);
180 return d;
181 }
182
183 /* Initialize the hash table */
_dictInit(dict * d,dictType * type,void * privDataPtr)184 int _dictInit(dict *d, dictType *type,
185 void *privDataPtr)
186 {
187 _dictReset(&d->ht[0]);
188 _dictReset(&d->ht[1]);
189 d->type = type;
190 d->privdata = privDataPtr;
191 d->rehashidx = -1;
192 d->iterators = 0;
193 return DICT_OK;
194 }
195
196 /* Resize the table to the minimal size that contains all the elements,
197 * but with the invariant of a USED/BUCKETS ratio near to <= 1 */
dictResize(dict * d)198 int dictResize(dict *d)
199 {
200 int minimal;
201
202 if (!dict_can_resize || dictIsRehashing(d)) return DICT_ERR;
203 minimal = d->ht[0].used;
204 if (minimal < DICT_HT_INITIAL_SIZE)
205 minimal = DICT_HT_INITIAL_SIZE;
206 return dictExpand(d, minimal);
207 }
208
209 /* Expand or create the hash table */
dictExpand(dict * d,unsigned long size)210 int dictExpand(dict *d, unsigned long size)
211 {
212 /* the size is invalid if it is smaller than the number of
213 * elements already inside the hash table */
214 if (dictIsRehashing(d) || d->ht[0].used > size)
215 return DICT_ERR;
216
217 dictht n; /* the new hash table */
218 unsigned long realsize = _dictNextPower(size);
219
220 /* Rehashing to the same table size is not useful. */
221 if (realsize == d->ht[0].size) return DICT_ERR;
222
223 /* Allocate the new hash table and initialize all pointers to NULL */
224 n.size = realsize;
225 n.sizemask = realsize-1;
226 n.table = rm_calloc(realsize, sizeof(dictEntry*));
227 n.used = 0;
228
229 /* Is this the first initialization? If so it's not really a rehashing
230 * we just set the first hash table so that it can accept keys. */
231 if (d->ht[0].table == NULL) {
232 d->ht[0] = n;
233 return DICT_OK;
234 }
235
236 /* Prepare a second hash table for incremental rehashing */
237 d->ht[1] = n;
238 d->rehashidx = 0;
239 return DICT_OK;
240 }
241
242 /* Performs N steps of incremental rehashing. Returns 1 if there are still
243 * keys to move from the old to the new hash table, otherwise 0 is returned.
244 *
245 * Note that a rehashing step consists in moving a bucket (that may have more
246 * than one key as we use chaining) from the old to the new hash table, however
247 * since part of the hash table may be composed of empty spaces, it is not
248 * guaranteed that this function will rehash even a single bucket, since it
249 * will visit at max N*10 empty buckets in total, otherwise the amount of
250 * work it does would be unbound and the function may block for a long time. */
dictRehash(dict * d,int n)251 int dictRehash(dict *d, int n) {
252 int empty_visits = n*10; /* Max number of empty buckets to visit. */
253 if (!dictIsRehashing(d)) return 0;
254
255 while(n-- && d->ht[0].used != 0) {
256 dictEntry *de, *nextde;
257
258 /* Note that rehashidx can't overflow as we are sure there are more
259 * elements because ht[0].used != 0 */
260 assert(d->ht[0].size > (unsigned long)d->rehashidx);
261 while(d->ht[0].table[d->rehashidx] == NULL) {
262 d->rehashidx++;
263 if (--empty_visits == 0) return 1;
264 }
265 de = d->ht[0].table[d->rehashidx];
266 /* Move all the keys in this bucket from the old to the new hash HT */
267 while(de) {
268 uint64_t h;
269
270 nextde = de->next;
271 /* Get the index in the new hash table */
272 h = dictHashKey(d, de->key) & d->ht[1].sizemask;
273 de->next = d->ht[1].table[h];
274 d->ht[1].table[h] = de;
275 d->ht[0].used--;
276 d->ht[1].used++;
277 de = nextde;
278 }
279 d->ht[0].table[d->rehashidx] = NULL;
280 d->rehashidx++;
281 }
282
283 /* Check if we already rehashed the whole table... */
284 if (d->ht[0].used == 0) {
285 rm_free(d->ht[0].table);
286 d->ht[0] = d->ht[1];
287 _dictReset(&d->ht[1]);
288 d->rehashidx = -1;
289 return 0;
290 }
291
292 /* More to rehash... */
293 return 1;
294 }
295
timeInMilliseconds(void)296 long long timeInMilliseconds(void) {
297 struct timeval tv;
298
299 gettimeofday(&tv,NULL);
300 return (((long long)tv.tv_sec)*1000)+(tv.tv_usec/1000);
301 }
302
303 /* Rehash for an amount of time between ms milliseconds and ms+1 milliseconds */
dictRehashMilliseconds(dict * d,int ms)304 int dictRehashMilliseconds(dict *d, int ms) {
305 long long start = timeInMilliseconds();
306 int rehashes = 0;
307
308 while(dictRehash(d,100)) {
309 rehashes += 100;
310 if (timeInMilliseconds()-start > ms) break;
311 }
312 return rehashes;
313 }
314
315 /* This function performs just a step of rehashing, and only if there are
316 * no safe iterators bound to our hash table. When we have iterators in the
317 * middle of a rehashing we can't mess with the two hash tables otherwise
318 * some element can be missed or duplicated.
319 *
320 * This function is called by common lookup or update operations in the
321 * dictionary so that the hash table automatically migrates from H1 to H2
322 * while it is actively used. */
_dictRehashStep(dict * d)323 static void _dictRehashStep(dict *d) {
324 if (d->iterators == 0) dictRehash(d,1);
325 }
326
327 /* Add an element to the target hash table */
dictAdd(dict * d,void * key,void * val)328 int dictAdd(dict *d, void *key, void *val)
329 {
330 dictEntry *entry = dictAddRaw(d,key,NULL);
331
332 if (!entry) return DICT_ERR;
333 dictSetVal(d, entry, val);
334 return DICT_OK;
335 }
336
337 /* Low level add or find:
338 * This function adds the entry but instead of setting a value returns the
339 * dictEntry structure to the user, that will make sure to fill the value
340 * field as he wishes.
341 *
342 * This function is also directly exposed to the user API to be called
343 * mainly in order to store non-pointers inside the hash value, example:
344 *
345 * entry = dictAddRaw(dict,mykey,NULL);
346 * if (entry != NULL) dictSetSignedIntegerVal(entry,1000);
347 *
348 * Return values:
349 *
350 * If key already exists NULL is returned, and "*existing" is populated
351 * with the existing entry if existing is not NULL.
352 *
353 * If key was added, the hash entry is returned to be manipulated by the caller.
354 */
dictAddRaw(dict * d,void * key,dictEntry ** existing)355 dictEntry *dictAddRaw(dict *d, void *key, dictEntry **existing)
356 {
357 long index;
358 dictEntry *entry;
359 dictht *ht;
360
361 if (dictIsRehashing(d)) _dictRehashStep(d);
362
363 /* Get the index of the new element, or -1 if
364 * the element already exists. */
365 if ((index = _dictKeyIndex(d, key, dictHashKey(d,key), existing)) == -1)
366 return NULL;
367
368 /* Allocate the memory and store the new entry.
369 * Insert the element in top, with the assumption that in a database
370 * system it is more likely that recently added entries are accessed
371 * more frequently. */
372 ht = dictIsRehashing(d) ? &d->ht[1] : &d->ht[0];
373 entry = rm_malloc(sizeof(*entry));
374 entry->next = ht->table[index];
375 ht->table[index] = entry;
376 ht->used++;
377
378 /* Set the hash entry fields. */
379 dictSetKey(d, entry, key);
380 return entry;
381 }
382
383 /* Add or Overwrite:
384 * Add an element, discarding the old value if the key already exists.
385 * Return 1 if the key was added from scratch, 0 if there was already an
386 * element with such key and dictReplace() just performed a value update
387 * operation. */
dictReplace(dict * d,void * key,void * val)388 int dictReplace(dict *d, void *key, void *val)
389 {
390 dictEntry *entry, *existing, auxentry;
391
392 /* Try to add the element. If the key
393 * does not exists dictAdd will succeed. */
394 entry = dictAddRaw(d,key,&existing);
395 if (entry) {
396 dictSetVal(d, entry, val);
397 return 1;
398 }
399
400 /* Set the new value and free the old one. Note that it is important
401 * to do that in this order, as the value may just be exactly the same
402 * as the previous one. In this context, think to reference counting,
403 * you want to increment (set), and then decrement (free), and not the
404 * reverse. */
405 auxentry = *existing;
406 dictSetVal(d, existing, val);
407 dictFreeVal(d, &auxentry);
408 return 0;
409 }
410
411 /* Add or Find:
412 * dictAddOrFind() is simply a version of dictAddRaw() that always
413 * returns the hash entry of the specified key, even if the key already
414 * exists and can't be added (in that case the entry of the already
415 * existing key is returned.)
416 *
417 * See dictAddRaw() for more information. */
dictAddOrFind(dict * d,void * key)418 dictEntry *dictAddOrFind(dict *d, void *key) {
419 dictEntry *entry, *existing;
420 entry = dictAddRaw(d,key,&existing);
421 return entry ? entry : existing;
422 }
423
424 /* Search and remove an element. This is an helper function for
425 * dictDelete() and dictUnlink(), please check the top comment
426 * of those functions. */
dictGenericDelete(dict * d,const void * key,int nofree)427 static dictEntry *dictGenericDelete(dict *d, const void *key, int nofree) {
428 uint64_t h, idx;
429 dictEntry *he, *prevHe;
430 int table;
431
432 if (d->ht[0].used == 0 && d->ht[1].used == 0) return NULL;
433
434 if (dictIsRehashing(d)) _dictRehashStep(d);
435 h = dictHashKey(d, key);
436
437 for (table = 0; table <= 1; table++) {
438 idx = h & d->ht[table].sizemask;
439 he = d->ht[table].table[idx];
440 prevHe = NULL;
441 while(he) {
442 if (key==he->key || dictCompareKeys(d, key, he->key)) {
443 /* Unlink the element from the list */
444 if (prevHe)
445 prevHe->next = he->next;
446 else
447 d->ht[table].table[idx] = he->next;
448 if (!nofree) {
449 dictFreeKey(d, he);
450 dictFreeVal(d, he);
451 rm_free(he);
452 }
453 d->ht[table].used--;
454 return he;
455 }
456 prevHe = he;
457 he = he->next;
458 }
459 if (!dictIsRehashing(d)) break;
460 }
461 return NULL; /* not found */
462 }
463
464 /* Remove an element, returning DICT_OK on success or DICT_ERR if the
465 * element was not found. */
dictDelete(dict * ht,const void * key)466 int dictDelete(dict *ht, const void *key) {
467 return dictGenericDelete(ht,key,0) ? DICT_OK : DICT_ERR;
468 }
469
470 /* Remove an element from the table, but without actually releasing
471 * the key, value and dictionary entry. The dictionary entry is returned
472 * if the element was found (and unlinked from the table), and the user
473 * should later call `dictFreeUnlinkedEntry()` with it in order to release it.
474 * Otherwise if the key is not found, NULL is returned.
475 *
476 * This function is useful when we want to remove something from the hash
477 * table but want to use its value before actually deleting the entry.
478 * Without this function the pattern would require two lookups:
479 *
480 * entry = dictFind(...);
481 * // Do something with entry
482 * dictDelete(dictionary,entry);
483 *
484 * Thanks to this function it is possible to avoid this, and use
485 * instead:
486 *
487 * entry = dictUnlink(dictionary,entry);
488 * // Do something with entry
489 * dictFreeUnlinkedEntry(entry); // <- This does not need to lookup again.
490 */
dictUnlink(dict * ht,const void * key)491 dictEntry *dictUnlink(dict *ht, const void *key) {
492 return dictGenericDelete(ht,key,1);
493 }
494
495 /* You need to call this function to really free the entry after a call
496 * to dictUnlink(). It's safe to call this function with 'he' = NULL. */
dictFreeUnlinkedEntry(dict * d,dictEntry * he)497 void dictFreeUnlinkedEntry(dict *d, dictEntry *he) {
498 if (he == NULL) return;
499 dictFreeKey(d, he);
500 dictFreeVal(d, he);
501 rm_free(he);
502 }
503
504 /* Destroy an entire dictionary */
_dictClear(dict * d,dictht * ht,void (callback)(void *))505 int _dictClear(dict *d, dictht *ht, void(callback)(void *)) {
506 unsigned long i;
507
508 /* Free all the elements */
509 for (i = 0; i < ht->size && ht->used > 0; i++) {
510 dictEntry *he, *nextHe;
511
512 if (callback && (i & 65535) == 0) callback(d->privdata);
513
514 if ((he = ht->table[i]) == NULL) continue;
515 while(he) {
516 nextHe = he->next;
517 dictFreeKey(d, he);
518 dictFreeVal(d, he);
519 rm_free(he);
520 ht->used--;
521 he = nextHe;
522 }
523 }
524 /* Free the table and the allocated cache structure */
525 rm_free(ht->table);
526 /* Re-initialize the table */
527 _dictReset(ht);
528 return DICT_OK; /* never fails */
529 }
530
531 /* Clear & Release the hash table */
dictRelease(dict * d)532 void dictRelease(dict *d)
533 {
534 _dictClear(d,&d->ht[0],NULL);
535 _dictClear(d,&d->ht[1],NULL);
536 rm_free(d);
537 }
538
dictFind(dict * d,const void * key)539 dictEntry *dictFind(dict *d, const void *key)
540 {
541 dictEntry *he;
542 uint64_t h, idx, table;
543
544 if (d->ht[0].used + d->ht[1].used == 0) return NULL; /* dict is empty */
545 if (dictIsRehashing(d)) _dictRehashStep(d);
546 h = dictHashKey(d, key);
547 for (table = 0; table <= 1; table++) {
548 idx = h & d->ht[table].sizemask;
549 he = d->ht[table].table[idx];
550 while(he) {
551 if (key==he->key || dictCompareKeys(d, key, he->key))
552 return he;
553 he = he->next;
554 }
555 if (!dictIsRehashing(d)) return NULL;
556 }
557 return NULL;
558 }
559
dictFetchValue(dict * d,const void * key)560 void *dictFetchValue(dict *d, const void *key) {
561 dictEntry *he;
562
563 he = dictFind(d,key);
564 return he ? dictGetVal(he) : NULL;
565 }
566
567 /* A fingerprint is a 64 bit number that represents the state of the dictionary
568 * at a given time, it's just a few dict properties xored together.
569 * When an unsafe iterator is initialized, we get the dict fingerprint, and check
570 * the fingerprint again when the iterator is released.
571 * If the two fingerprints are different it means that the user of the iterator
572 * performed forbidden operations against the dictionary while iterating. */
dictFingerprint(dict * d)573 long long dictFingerprint(dict *d) {
574 long long integers[6], hash = 0;
575 int j;
576
577 integers[0] = (long) d->ht[0].table;
578 integers[1] = d->ht[0].size;
579 integers[2] = d->ht[0].used;
580 integers[3] = (long) d->ht[1].table;
581 integers[4] = d->ht[1].size;
582 integers[5] = d->ht[1].used;
583
584 /* We hash N integers by summing every successive integer with the integer
585 * hashing of the previous sum. Basically:
586 *
587 * Result = hash(hash(hash(int1)+int2)+int3) ...
588 *
589 * This way the same set of integers in a different order will (likely) hash
590 * to a different number. */
591 for (j = 0; j < 6; j++) {
592 hash += integers[j];
593 /* For the hashing step we use Tomas Wang's 64 bit integer hash. */
594 hash = (~hash) + (hash << 21); // hash = (hash << 21) - hash - 1;
595 hash = hash ^ (hash >> 24);
596 hash = (hash + (hash << 3)) + (hash << 8); // hash * 265
597 hash = hash ^ (hash >> 14);
598 hash = (hash + (hash << 2)) + (hash << 4); // hash * 21
599 hash = hash ^ (hash >> 28);
600 hash = hash + (hash << 31);
601 }
602 return hash;
603 }
604
dictGetIterator(dict * d)605 dictIterator *dictGetIterator(dict *d)
606 {
607 dictIterator *iter = rm_malloc(sizeof(*iter));
608
609 iter->d = d;
610 iter->table = 0;
611 iter->index = -1;
612 iter->safe = 0;
613 iter->entry = NULL;
614 iter->nextEntry = NULL;
615 return iter;
616 }
617
dictGetSafeIterator(dict * d)618 dictIterator *dictGetSafeIterator(dict *d) {
619 dictIterator *i = dictGetIterator(d);
620
621 i->safe = 1;
622 return i;
623 }
624
dictNext(dictIterator * iter)625 dictEntry *dictNext(dictIterator *iter)
626 {
627 while (1) {
628 if (iter->entry == NULL) {
629 dictht *ht = &iter->d->ht[iter->table];
630 if (iter->index == -1 && iter->table == 0) {
631 if (iter->safe)
632 iter->d->iterators++;
633 else
634 iter->fingerprint = dictFingerprint(iter->d);
635 }
636 iter->index++;
637 if (iter->index >= (long) ht->size) {
638 if (dictIsRehashing(iter->d) && iter->table == 0) {
639 iter->table++;
640 iter->index = 0;
641 ht = &iter->d->ht[1];
642 } else {
643 break;
644 }
645 }
646 iter->entry = ht->table[iter->index];
647 } else {
648 iter->entry = iter->nextEntry;
649 }
650 if (iter->entry) {
651 /* We need to save the 'next' here, the iterator user
652 * may delete the entry we are returning. */
653 iter->nextEntry = iter->entry->next;
654 return iter->entry;
655 }
656 }
657 return NULL;
658 }
659
dictReleaseIterator(dictIterator * iter)660 void dictReleaseIterator(dictIterator *iter)
661 {
662 if (!(iter->index == -1 && iter->table == 0)) {
663 if (iter->safe)
664 iter->d->iterators--;
665 else
666 assert(iter->fingerprint == dictFingerprint(iter->d));
667 }
668 rm_free(iter);
669 }
670
671 /* Return a random entry from the hash table. Useful to
672 * implement randomized algorithms */
dictGetRandomKey(dict * d)673 dictEntry *dictGetRandomKey(dict *d)
674 {
675 dictEntry *he, *orighe;
676 unsigned long h;
677 int listlen, listele;
678
679 if (dictSize(d) == 0) return NULL;
680 if (dictIsRehashing(d)) _dictRehashStep(d);
681 if (dictIsRehashing(d)) {
682 do {
683 /* We are sure there are no elements in indexes from 0
684 * to rehashidx-1 */
685 h = d->rehashidx + (random() % (d->ht[0].size +
686 d->ht[1].size -
687 d->rehashidx));
688 he = (h >= d->ht[0].size) ? d->ht[1].table[h - d->ht[0].size] :
689 d->ht[0].table[h];
690 } while(he == NULL);
691 } else {
692 do {
693 h = random() & d->ht[0].sizemask;
694 he = d->ht[0].table[h];
695 } while(he == NULL);
696 }
697
698 /* Now we found a non empty bucket, but it is a linked
699 * list and we need to get a random element from the list.
700 * The only sane way to do so is counting the elements and
701 * select a random index. */
702 listlen = 0;
703 orighe = he;
704 while(he) {
705 he = he->next;
706 listlen++;
707 }
708 listele = random() % listlen;
709 he = orighe;
710 while(listele--) he = he->next;
711 return he;
712 }
713
714 /* This function samples the dictionary to return a few keys from random
715 * locations.
716 *
717 * It does not guarantee to return all the keys specified in 'count', nor
718 * it does guarantee to return non-duplicated elements, however it will make
719 * some effort to do both things.
720 *
721 * Returned pointers to hash table entries are stored into 'des' that
722 * points to an array of dictEntry pointers. The array must have room for
723 * at least 'count' elements, that is the argument we pass to the function
724 * to tell how many random elements we need.
725 *
726 * The function returns the number of items stored into 'des', that may
727 * be less than 'count' if the hash table has less than 'count' elements
728 * inside, or if not enough elements were found in a reasonable amount of
729 * steps.
730 *
731 * Note that this function is not suitable when you need a good distribution
732 * of the returned items, but only when you need to "sample" a given number
733 * of continuous elements to run some kind of algorithm or to produce
734 * statistics. However the function is much faster than dictGetRandomKey()
735 * at producing N elements. */
dictGetSomeKeys(dict * d,dictEntry ** des,unsigned int count)736 unsigned int dictGetSomeKeys(dict *d, dictEntry **des, unsigned int count) {
737 unsigned long j; /* internal hash table id, 0 or 1. */
738 unsigned long tables; /* 1 or 2 tables? */
739 unsigned long stored = 0, maxsizemask;
740 unsigned long maxsteps;
741
742 if (dictSize(d) < count) count = dictSize(d);
743 maxsteps = count*10;
744
745 /* Try to do a rehashing work proportional to 'count'. */
746 for (j = 0; j < count; j++) {
747 if (dictIsRehashing(d))
748 _dictRehashStep(d);
749 else
750 break;
751 }
752
753 tables = dictIsRehashing(d) ? 2 : 1;
754 maxsizemask = d->ht[0].sizemask;
755 if (tables > 1 && maxsizemask < d->ht[1].sizemask)
756 maxsizemask = d->ht[1].sizemask;
757
758 /* Pick a random point inside the larger table. */
759 unsigned long i = random() & maxsizemask;
760 unsigned long emptylen = 0; /* Continuous empty entries so far. */
761 while(stored < count && maxsteps--) {
762 for (j = 0; j < tables; j++) {
763 /* Invariant of the dict.c rehashing: up to the indexes already
764 * visited in ht[0] during the rehashing, there are no populated
765 * buckets, so we can skip ht[0] for indexes between 0 and idx-1. */
766 if (tables == 2 && j == 0 && i < (unsigned long) d->rehashidx) {
767 /* Moreover, if we are currently out of range in the second
768 * table, there will be no elements in both tables up to
769 * the current rehashing index, so we jump if possible.
770 * (this happens when going from big to small table). */
771 if (i >= d->ht[1].size)
772 i = d->rehashidx;
773 else
774 continue;
775 }
776 if (i >= d->ht[j].size) continue; /* Out of range for this table. */
777 dictEntry *he = d->ht[j].table[i];
778
779 /* Count contiguous empty buckets, and jump to other
780 * locations if they reach 'count' (with a minimum of 5). */
781 if (he == NULL) {
782 emptylen++;
783 if (emptylen >= 5 && emptylen > count) {
784 i = random() & maxsizemask;
785 emptylen = 0;
786 }
787 } else {
788 emptylen = 0;
789 while (he) {
790 /* Collect all the elements of the buckets found non
791 * empty while iterating. */
792 *des = he;
793 des++;
794 he = he->next;
795 stored++;
796 if (stored == count) return stored;
797 }
798 }
799 }
800 i = (i+1) & maxsizemask;
801 }
802 return stored;
803 }
804
805 /* Function to reverse bits. Algorithm from:
806 * http://graphics.stanford.edu/~seander/bithacks.html#ReverseParallel */
rev(unsigned long v)807 static unsigned long rev(unsigned long v) {
808 unsigned long s = 8 * sizeof(v); // bit size; must be power of 2
809 unsigned long mask = ~0;
810 while ((s >>= 1) > 0) {
811 mask ^= (mask << s);
812 v = ((v >> s) & mask) | ((v << s) & ~mask);
813 }
814 return v;
815 }
816
817 /* dictScan() is used to iterate over the elements of a dictionary.
818 *
819 * Iterating works the following way:
820 *
821 * 1) Initially you call the function using a cursor (v) value of 0.
822 * 2) The function performs one step of the iteration, and returns the
823 * new cursor value you must use in the next call.
824 * 3) When the returned cursor is 0, the iteration is complete.
825 *
826 * The function guarantees all elements present in the
827 * dictionary get returned between the start and end of the iteration.
828 * However it is possible some elements get returned multiple times.
829 *
830 * For every element returned, the callback argument 'fn' is
831 * called with 'privdata' as first argument and the dictionary entry
832 * 'de' as second argument.
833 *
834 * HOW IT WORKS.
835 *
836 * The iteration algorithm was designed by Pieter Noordhuis.
837 * The main idea is to increment a cursor starting from the higher order
838 * bits. That is, instead of incrementing the cursor normally, the bits
839 * of the cursor are reversed, then the cursor is incremented, and finally
840 * the bits are reversed again.
841 *
842 * This strategy is needed because the hash table may be resized between
843 * iteration calls.
844 *
845 * dict.c hash tables are always power of two in size, and they
846 * use chaining, so the position of an element in a given table is given
847 * by computing the bitwise AND between Hash(key) and SIZE-1
848 * (where SIZE-1 is always the mask that is equivalent to taking the rest
849 * of the division between the Hash of the key and SIZE).
850 *
851 * For example if the current hash table size is 16, the mask is
852 * (in binary) 1111. The position of a key in the hash table will always be
853 * the last four bits of the hash output, and so forth.
854 *
855 * WHAT HAPPENS IF THE TABLE CHANGES IN SIZE?
856 *
857 * If the hash table grows, elements can go anywhere in one multiple of
858 * the old bucket: for example let's say we already iterated with
859 * a 4 bit cursor 1100 (the mask is 1111 because hash table size = 16).
860 *
861 * If the hash table will be resized to 64 elements, then the new mask will
862 * be 111111. The new buckets you obtain by substituting in ??1100
863 * with either 0 or 1 can be targeted only by keys we already visited
864 * when scanning the bucket 1100 in the smaller hash table.
865 *
866 * By iterating the higher bits first, because of the inverted counter, the
867 * cursor does not need to restart if the table size gets bigger. It will
868 * continue iterating using cursors without '1100' at the end, and also
869 * without any other combination of the final 4 bits already explored.
870 *
871 * Similarly when the table size shrinks over time, for example going from
872 * 16 to 8, if a combination of the lower three bits (the mask for size 8
873 * is 111) were already completely explored, it would not be visited again
874 * because we are sure we tried, for example, both 0111 and 1111 (all the
875 * variations of the higher bit) so we don't need to test it again.
876 *
877 * WAIT... YOU HAVE *TWO* TABLES DURING REHASHING!
878 *
879 * Yes, this is true, but we always iterate the smaller table first, then
880 * we test all the expansions of the current cursor into the larger
881 * table. For example if the current cursor is 101 and we also have a
882 * larger table of size 16, we also test (0)101 and (1)101 inside the larger
883 * table. This reduces the problem back to having only one table, where
884 * the larger one, if it exists, is just an expansion of the smaller one.
885 *
886 * LIMITATIONS
887 *
888 * This iterator is completely stateless, and this is a huge advantage,
889 * including no additional memory used.
890 *
891 * The disadvantages resulting from this design are:
892 *
893 * 1) It is possible we return elements more than once. However this is usually
894 * easy to deal with in the application level.
895 * 2) The iterator must return multiple elements per call, as it needs to always
896 * return all the keys chained in a given bucket, and all the expansions, so
897 * we are sure we don't miss keys moving during rehashing.
898 * 3) The reverse cursor is somewhat hard to understand at first, but this
899 * comment is supposed to help.
900 */
dictScan(dict * d,unsigned long v,dictScanFunction * fn,dictScanBucketFunction * bucketfn,void * privdata)901 unsigned long dictScan(dict *d,
902 unsigned long v,
903 dictScanFunction *fn,
904 dictScanBucketFunction* bucketfn,
905 void *privdata)
906 {
907 dictht *t0, *t1;
908 const dictEntry *de, *next;
909 unsigned long m0, m1;
910
911 if (dictSize(d) == 0) return 0;
912
913 if (!dictIsRehashing(d)) {
914 t0 = &(d->ht[0]);
915 m0 = t0->sizemask;
916
917 /* Emit entries at cursor */
918 if (bucketfn) bucketfn(privdata, &t0->table[v & m0]);
919 de = t0->table[v & m0];
920 while (de) {
921 next = de->next;
922 fn(privdata, de);
923 de = next;
924 }
925
926 /* Set unmasked bits so incrementing the reversed cursor
927 * operates on the masked bits */
928 v |= ~m0;
929
930 /* Increment the reverse cursor */
931 v = rev(v);
932 v++;
933 v = rev(v);
934
935 } else {
936 t0 = &d->ht[0];
937 t1 = &d->ht[1];
938
939 /* Make sure t0 is the smaller and t1 is the bigger table */
940 if (t0->size > t1->size) {
941 t0 = &d->ht[1];
942 t1 = &d->ht[0];
943 }
944
945 m0 = t0->sizemask;
946 m1 = t1->sizemask;
947
948 /* Emit entries at cursor */
949 if (bucketfn) bucketfn(privdata, &t0->table[v & m0]);
950 de = t0->table[v & m0];
951 while (de) {
952 next = de->next;
953 fn(privdata, de);
954 de = next;
955 }
956
957 /* Iterate over indices in larger table that are the expansion
958 * of the index pointed to by the cursor in the smaller table */
959 do {
960 /* Emit entries at cursor */
961 if (bucketfn) bucketfn(privdata, &t1->table[v & m1]);
962 de = t1->table[v & m1];
963 while (de) {
964 next = de->next;
965 fn(privdata, de);
966 de = next;
967 }
968
969 /* Increment the reverse cursor not covered by the smaller mask.*/
970 v |= ~m1;
971 v = rev(v);
972 v++;
973 v = rev(v);
974
975 /* Continue while bits covered by mask difference is non-zero */
976 } while (v & (m0 ^ m1));
977 }
978
979 return v;
980 }
981
982 /* ------------------------- private functions ------------------------------ */
983
984 /* Expand the hash table if needed */
_dictExpandIfNeeded(dict * d)985 static int _dictExpandIfNeeded(dict *d)
986 {
987 /* Incremental rehashing already in progress. Return. */
988 if (dictIsRehashing(d)) return DICT_OK;
989
990 /* If the hash table is empty expand it to the initial size. */
991 if (d->ht[0].size == 0) return dictExpand(d, DICT_HT_INITIAL_SIZE);
992
993 /* If we reached the 1:1 ratio, and we are allowed to resize the hash
994 * table (global setting) or we should avoid it but the ratio between
995 * elements/buckets is over the "safe" threshold, we resize doubling
996 * the number of buckets. */
997 if (d->ht[0].used >= d->ht[0].size &&
998 (dict_can_resize ||
999 d->ht[0].used/d->ht[0].size > dict_force_resize_ratio))
1000 {
1001 return dictExpand(d, d->ht[0].used*2);
1002 }
1003 return DICT_OK;
1004 }
1005
1006 /* Our hash table capability is a power of two */
_dictNextPower(unsigned long size)1007 static unsigned long _dictNextPower(unsigned long size)
1008 {
1009 unsigned long i = DICT_HT_INITIAL_SIZE;
1010
1011 if (size >= LONG_MAX) return LONG_MAX + 1LU;
1012 while(1) {
1013 if (i >= size)
1014 return i;
1015 i *= 2;
1016 }
1017 }
1018
1019 /* Returns the index of a free slot that can be populated with
1020 * a hash entry for the given 'key'.
1021 * If the key already exists, -1 is returned
1022 * and the optional output parameter may be filled.
1023 *
1024 * Note that if we are in the process of rehashing the hash table, the
1025 * index is always returned in the context of the second (new) hash table. */
_dictKeyIndex(dict * d,const void * key,uint64_t hash,dictEntry ** existing)1026 static long _dictKeyIndex(dict *d, const void *key, uint64_t hash, dictEntry **existing)
1027 {
1028 unsigned long idx, table;
1029 dictEntry *he;
1030 if (existing) *existing = NULL;
1031
1032 /* Expand the hash table if needed */
1033 if (_dictExpandIfNeeded(d) == DICT_ERR)
1034 return -1;
1035 for (table = 0; table <= 1; table++) {
1036 idx = hash & d->ht[table].sizemask;
1037 /* Search if this slot does not already contain the given key */
1038 he = d->ht[table].table[idx];
1039 while(he) {
1040 if (key==he->key || dictCompareKeys(d, key, he->key)) {
1041 if (existing) *existing = he;
1042 return -1;
1043 }
1044 he = he->next;
1045 }
1046 if (!dictIsRehashing(d)) break;
1047 }
1048 return idx;
1049 }
1050
dictEmpty(dict * d,void (callback)(void *))1051 void dictEmpty(dict *d, void(callback)(void*)) {
1052 _dictClear(d,&d->ht[0],callback);
1053 _dictClear(d,&d->ht[1],callback);
1054 d->rehashidx = -1;
1055 d->iterators = 0;
1056 }
1057
dictEnableResize(void)1058 void dictEnableResize(void) {
1059 dict_can_resize = 1;
1060 }
1061
dictDisableResize(void)1062 void dictDisableResize(void) {
1063 dict_can_resize = 0;
1064 }
1065
dictGetHash(dict * d,const void * key)1066 uint64_t dictGetHash(dict *d, const void *key) {
1067 return dictHashKey(d, key);
1068 }
1069
1070 /* Finds the dictEntry reference by using pointer and pre-calculated hash.
1071 * oldkey is a dead pointer and should not be accessed.
1072 * the hash value should be provided using dictGetHash.
1073 * no string / key comparison is performed.
1074 * return value is the reference to the dictEntry if found, or NULL if not found. */
dictFindEntryRefByPtrAndHash(dict * d,const void * oldptr,uint64_t hash)1075 dictEntry **dictFindEntryRefByPtrAndHash(dict *d, const void *oldptr, uint64_t hash) {
1076 dictEntry *he, **heref;
1077 unsigned long idx, table;
1078
1079 if (d->ht[0].used + d->ht[1].used == 0) return NULL; /* dict is empty */
1080 for (table = 0; table <= 1; table++) {
1081 idx = hash & d->ht[table].sizemask;
1082 heref = &d->ht[table].table[idx];
1083 he = *heref;
1084 while(he) {
1085 if (oldptr==he->key)
1086 return heref;
1087 heref = &he->next;
1088 he = *heref;
1089 }
1090 if (!dictIsRehashing(d)) return NULL;
1091 }
1092 return NULL;
1093 }
1094
1095 /* ------------------------------- Debugging ---------------------------------*/
1096
1097 #define DICT_STATS_VECTLEN 50
_dictGetStatsHt(char * buf,size_t bufsize,dictht * ht,int tableid)1098 size_t _dictGetStatsHt(char *buf, size_t bufsize, dictht *ht, int tableid) {
1099 unsigned long i, slots = 0, chainlen, maxchainlen = 0;
1100 unsigned long totchainlen = 0;
1101 unsigned long clvector[DICT_STATS_VECTLEN];
1102 size_t l = 0;
1103
1104 if (ht->used == 0) {
1105 return snprintf(buf,bufsize,
1106 "No stats available for empty dictionaries\n");
1107 }
1108
1109 /* Compute stats. */
1110 for (i = 0; i < DICT_STATS_VECTLEN; i++) clvector[i] = 0;
1111 for (i = 0; i < ht->size; i++) {
1112 dictEntry *he;
1113
1114 if (ht->table[i] == NULL) {
1115 clvector[0]++;
1116 continue;
1117 }
1118 slots++;
1119 /* For each hash entry on this slot... */
1120 chainlen = 0;
1121 he = ht->table[i];
1122 while(he) {
1123 chainlen++;
1124 he = he->next;
1125 }
1126 clvector[(chainlen < DICT_STATS_VECTLEN) ? chainlen : (DICT_STATS_VECTLEN-1)]++;
1127 if (chainlen > maxchainlen) maxchainlen = chainlen;
1128 totchainlen += chainlen;
1129 }
1130
1131 /* Generate human readable stats. */
1132 l += snprintf(buf+l,bufsize-l,
1133 "Hash table %d stats (%s):\n"
1134 " table size: %ld\n"
1135 " number of elements: %ld\n"
1136 " different slots: %ld\n"
1137 " max chain length: %ld\n"
1138 " avg chain length (counted): %.02f\n"
1139 " avg chain length (computed): %.02f\n"
1140 " Chain length distribution:\n",
1141 tableid, (tableid == 0) ? "main hash table" : "rehashing target",
1142 ht->size, ht->used, slots, maxchainlen,
1143 (float)totchainlen/slots, (float)ht->used/slots);
1144
1145 for (i = 0; i < DICT_STATS_VECTLEN-1; i++) {
1146 if (clvector[i] == 0) continue;
1147 if (l >= bufsize) break;
1148 l += snprintf(buf+l,bufsize-l,
1149 " %s%ld: %ld (%.02f%%)\n",
1150 (i == DICT_STATS_VECTLEN-1)?">= ":"",
1151 i, clvector[i], ((float)clvector[i]/ht->size)*100);
1152 }
1153
1154 /* Unlike snprintf(), teturn the number of characters actually written. */
1155 if (bufsize) buf[bufsize-1] = '\0';
1156 return strlen(buf);
1157 }
1158
dictGetStats(char * buf,size_t bufsize,dict * d)1159 void dictGetStats(char *buf, size_t bufsize, dict *d) {
1160 size_t l;
1161 char *orig_buf = buf;
1162 size_t orig_bufsize = bufsize;
1163
1164 l = _dictGetStatsHt(buf,bufsize,&d->ht[0],0);
1165 buf += l;
1166 bufsize -= l;
1167 if (dictIsRehashing(d) && bufsize > 0) {
1168 _dictGetStatsHt(buf,bufsize,&d->ht[1],1);
1169 }
1170 /* Make sure there is a NULL term at the end. */
1171 if (orig_bufsize) orig_buf[orig_bufsize-1] = '\0';
1172 }
1173
1174 /* ------------------------------- Benchmark ---------------------------------*/
1175
1176 #ifdef DICT_BENCHMARK_MAIN
1177
1178 #include "sds.h"
1179
hashCallback(const void * key)1180 uint64_t hashCallback(const void *key) {
1181 return dictGenHashFunction((unsigned char*)key, sdslen((char*)key));
1182 }
1183
compareCallback(void * privdata,const void * key1,const void * key2)1184 int compareCallback(void *privdata, const void *key1, const void *key2) {
1185 int l1,l2;
1186 DICT_NOTUSED(privdata);
1187
1188 l1 = sdslen((sds)key1);
1189 l2 = sdslen((sds)key2);
1190 if (l1 != l2) return 0;
1191 return memcmp(key1, key2, l1) == 0;
1192 }
1193
freeCallback(void * privdata,void * val)1194 void freeCallback(void *privdata, void *val) {
1195 DICT_NOTUSED(privdata);
1196
1197 sdsfree(val);
1198 }
1199
1200 dictType BenchmarkDictType = {
1201 hashCallback,
1202 NULL,
1203 NULL,
1204 compareCallback,
1205 freeCallback,
1206 NULL
1207 };
1208
1209 #define start_benchmark() start = timeInMilliseconds()
1210 #define end_benchmark(msg) do { \
1211 elapsed = timeInMilliseconds()-start; \
1212 printf(msg ": %ld items in %lld ms\n", count, elapsed); \
1213 } while(0);
1214
1215 /* dict-benchmark [count] */
main(int argc,char ** argv)1216 int main(int argc, char **argv) {
1217 long j;
1218 long long start, elapsed;
1219 dict *dict = dictCreate(&BenchmarkDictType,NULL);
1220 long count = 0;
1221
1222 if (argc == 2) {
1223 count = strtol(argv[1],NULL,10);
1224 } else {
1225 count = 5000000;
1226 }
1227
1228 start_benchmark();
1229 for (j = 0; j < count; j++) {
1230 int retval = dictAdd(dict,sdsfromlonglong(j),(void*)j);
1231 assert(retval == DICT_OK);
1232 }
1233 end_benchmark("Inserting");
1234 assert((long)dictSize(dict) == count);
1235
1236 /* Wait for rehashing. */
1237 while (dictIsRehashing(dict)) {
1238 dictRehashMilliseconds(dict,100);
1239 }
1240
1241 start_benchmark();
1242 for (j = 0; j < count; j++) {
1243 sds key = sdsfromlonglong(j);
1244 dictEntry *de = dictFind(dict,key);
1245 assert(de != NULL);
1246 sdsfree(key);
1247 }
1248 end_benchmark("Linear access of existing elements");
1249
1250 start_benchmark();
1251 for (j = 0; j < count; j++) {
1252 sds key = sdsfromlonglong(j);
1253 dictEntry *de = dictFind(dict,key);
1254 assert(de != NULL);
1255 sdsfree(key);
1256 }
1257 end_benchmark("Linear access of existing elements (2nd round)");
1258
1259 start_benchmark();
1260 for (j = 0; j < count; j++) {
1261 sds key = sdsfromlonglong(rand() % count);
1262 dictEntry *de = dictFind(dict,key);
1263 assert(de != NULL);
1264 sdsfree(key);
1265 }
1266 end_benchmark("Random access of existing elements");
1267
1268 start_benchmark();
1269 for (j = 0; j < count; j++) {
1270 sds key = sdsfromlonglong(rand() % count);
1271 key[0] = 'X';
1272 dictEntry *de = dictFind(dict,key);
1273 assert(de == NULL);
1274 sdsfree(key);
1275 }
1276 end_benchmark("Accessing missing");
1277
1278 start_benchmark();
1279 for (j = 0; j < count; j++) {
1280 sds key = sdsfromlonglong(j);
1281 int retval = dictDelete(dict,key);
1282 assert(retval == DICT_OK);
1283 key[0] += 17; /* Change first number to letter. */
1284 retval = dictAdd(dict,key,(void*)j);
1285 assert(retval == DICT_OK);
1286 }
1287 end_benchmark("Removing and adding");
1288 }
1289 #endif
1290