dict.c

Bug Summary

File:	src/dict.c
Warning:	line 672, column 27 Access to field 'next' results in a dereference of a null pointer (loaded from variable 'he')
Annotated Source Code

Press '?' to see keyboard shortcuts
Show analyzer invocation
clang -cc1 -triple x86_64-pc-linux-gnu -analyze -disable-free -disable-llvm-verifier -discard-value-names -main-file-name dict.c -analyzer-store=region -analyzer-opt-analyze-nested-blocks -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -setup-static-analyzer -mrelocation-model static -mthread-model posix -mframe-pointer=none -fmath-errno -fno-rounding-math -masm-verbose -mconstructor-aliases -munwind-tables -target-cpu x86-64 -dwarf-column-info -fno-split-dwarf-inlining -debugger-tuning=gdb -resource-dir /usr/lib/llvm-10/lib/clang/10.0.0 -D REDIS_STATIC= -I ../deps/hiredis -I ../deps/linenoise -I ../deps/lua/src -I ../deps/hdr_histogram -D USE_JEMALLOC -I ../deps/jemalloc/include -internal-isystem /usr/local/include -internal-isystem /usr/lib/llvm-10/lib/clang/10.0.0/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -O2 -Wno-c11-extensions -Wno-missing-field-initializers -std=c11 -fdebug-compilation-dir /home/netto/Desktop/redis-6.2.1/src -ferror-limit 19 -fmessage-length 0 -fgnuc-version=4.2.1 -fobjc-runtime=gcc -fdiagnostics-show-option -vectorize-loops -vectorize-slp -analyzer-output=html -faddrsig -o /tmp/scan-build-2021-03-14-133648-8817-1 -x c dict.c
1/* Hash Tables Implementation.
*
* This file implements in memory hash tables with insert/del/replace/find/
* get-random-element operations. Hash tables will auto resize if needed
* tables of power of two in size are used, collisions are handled by
* chaining. See the source code for more information... :)
*
* Copyright (c) 2006-2012, Salvatore Sanfilippo <antirez at gmail dot com>
* All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions are met:
*
*   * Redistributions of source code must retain the above copyright notice,
*     this list of conditions and the following disclaimer.
*   * Redistributions in binary form must reproduce the above copyright
*     notice, this list of conditions and the following disclaimer in the
*     documentation and/or other materials provided with the distribution.
*   * Neither the name of Redis nor the names of its contributors may be used
*     to endorse or promote products derived from this software without
*     specific prior written permission.
*
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
* AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
* ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
* LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
* CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
* SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
* INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
* CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
* ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
* POSSIBILITY OF SUCH DAMAGE.
*/

36#include "fmacros.h"

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>

46#include "dict.h"
47#include "zmalloc.h"
48#ifndef DICT_BENCHMARK_MAIN
49#include "redisassert.h"
50#else
51#include <assert.h>
52#endif

54/* Using dictEnableResize() / dictDisableResize() we make possible to
* enable/disable resizing of the hash table as needed. This is very important
* for Redis, as we use copy-on-write and don't want to move too much memory
* around when there is a child performing saving operations.
*
* Note that even when dict_can_resize is set to 0, not all resizes are
* prevented: a hash table is still allowed to grow if the ratio between
* the number of elements and the buckets > dict_force_resize_ratio. */
62static int dict_can_resize = 1;
63static unsigned int dict_force_resize_ratio = 5;

65/* -------------------------- private prototypes ---------------------------- */

67static int _dictExpandIfNeeded(dict *ht);
68static unsigned long _dictNextPower(unsigned long size);
69static long _dictKeyIndex(dict *ht, const void *key, uint64_t hash, dictEntry **existing);
70static int _dictInit(dict *ht, dictType *type, void *privDataPtr);

72/* -------------------------- hash functions -------------------------------- */

74static uint8_t dict_hash_function_seed[16];

76void dictSetHashFunctionSeed(uint8_t *seed) {
  memcpy(dict_hash_function_seed,seed,sizeof(dict_hash_function_seed));
78}

80uint8_t *dictGetHashFunctionSeed(void) {
  return dict_hash_function_seed;
82}

84/* The default hashing function uses SipHash implementation
* in siphash.c. */

87uint64_t siphash(const uint8_t *in, const size_t inlen, const uint8_t *k);
88uint64_t siphash_nocase(const uint8_t *in, const size_t inlen, const uint8_t *k);

90uint64_t dictGenHashFunction(const void *key, int len) {
  return siphash(key,len,dict_hash_function_seed);
92}

94uint64_t dictGenCaseHashFunction(const unsigned char *buf, int len) {
  return siphash_nocase(buf,len,dict_hash_function_seed);
96}

98/* ----------------------------- API implementation ------------------------- */

100/* Reset a hash table already initialized with ht_init().
* NOTE: This function should only be called by ht_destroy(). */
102static void _dictReset(dictht *ht)
103{
  ht->table = NULL((void*)0);
  ht->size = 0;
  ht->sizemask = 0;
  ht->used = 0;
108}

110/* Create a new hash table */
111dict *dictCreate(dictType *type,
      void *privDataPtr)
113{
  dict *d = zmalloc(sizeof(*d));

  _dictInit(d,type,privDataPtr);
  return d;
118}

120/* Initialize the hash table */
121int _dictInit(dict *d, dictType *type,
      void *privDataPtr)
123{
  _dictReset(&d->ht[0]);
  _dictReset(&d->ht[1]);
  d->type = type;
  d->privdata = privDataPtr;
  d->rehashidx = -1;
  d->pauserehash = 0;
  return DICT_OK0;
131}

133/* Resize the table to the minimal size that contains all the elements,
* but with the invariant of a USED/BUCKETS ratio near to <= 1 */
135int dictResize(dict *d)
136{
  unsigned long minimal;

  if (!dict_can_resize || dictIsRehashing(d)((d)->rehashidx != -1)) return DICT_ERR1;
  minimal = d->ht[0].used;
  if (minimal < DICT_HT_INITIAL_SIZE4)
      minimal = DICT_HT_INITIAL_SIZE4;
  return dictExpand(d, minimal);
144}

146/* Expand or create the hash table,
* when malloc_failed is non-NULL, it'll avoid panic if malloc fails (in which case it'll be set to 1).
* Returns DICT_OK if expand was performed, and DICT_ERR if skipped. */
149int _dictExpand(dict *d, unsigned long size, int* malloc_failed)
150{
  if (malloc_failed) *malloc_failed = 0;

  /* the size is invalid if it is smaller than the number of
   * elements already inside the hash table */
  if (dictIsRehashing(d)((d)->rehashidx != -1) || d->ht[0].used > size)
      return DICT_ERR1;

  dictht n; /* the new hash table */
  unsigned long realsize = _dictNextPower(size);

  /* Rehashing to the same table size is not useful. */
  if (realsize == d->ht[0].size) return DICT_ERR1;

  /* Allocate the new hash table and initialize all pointers to NULL */
  n.size = realsize;
  n.sizemask = realsize-1;
  if (malloc_failed) {
      n.table = ztrycalloc(realsize*sizeof(dictEntry*));
      *malloc_failed = n.table == NULL((void*)0);
      if (*malloc_failed)
          return DICT_ERR1;
  } else
      n.table = zcalloc(realsize*sizeof(dictEntry*));

  n.used = 0;

  /* Is this the first initialization? If so it's not really a rehashing
   * we just set the first hash table so that it can accept keys. */
  if (d->ht[0].table == NULL((void*)0)) {
      d->ht[0] = n;
      return DICT_OK0;
  }

  /* Prepare a second hash table for incremental rehashing */
  d->ht[1] = n;
  d->rehashidx = 0;
  return DICT_OK0;
188}

190/* return DICT_ERR if expand was not performed */
191int dictExpand(dict *d, unsigned long size) {
  return _dictExpand(d, size, NULL((void*)0));
193}

195/* return DICT_ERR if expand failed due to memory allocation failure */
196int dictTryExpand(dict *d, unsigned long size) {
  int malloc_failed;
  _dictExpand(d, size, &malloc_failed);
  return malloc_failed? DICT_ERR1 : DICT_OK0;
200}

202/* Performs N steps of incremental rehashing. Returns 1 if there are still
* keys to move from the old to the new hash table, otherwise 0 is returned.
*
* Note that a rehashing step consists in moving a bucket (that may have more
* than one key as we use chaining) from the old to the new hash table, however
* since part of the hash table may be composed of empty spaces, it is not
* guaranteed that this function will rehash even a single bucket, since it
* will visit at max N*10 empty buckets in total, otherwise the amount of
* work it does would be unbound and the function may block for a long time. */
211int dictRehash(dict *d, int n) {
  int empty_visits = n*10; /* Max number of empty buckets to visit. */
  if (!dictIsRehashing(d)((d)->rehashidx != -1)) return 0;

  while(n-- && d->ht[0].used != 0) {
      dictEntry *de, *nextde;

      /* Note that rehashidx can't overflow as we are sure there are more
       * elements because ht[0].used != 0 */
      assert(d->ht[0].size > (unsigned long)d->rehashidx)(__builtin_expect(!!((d->ht[0].size > (unsigned long)d->
rehashidx)), 1)?(void)0 : (_serverAssert("d->ht[0].size > (unsigned long)d->rehashidx"
,"dict.c",220),__builtin_unreachable()));
      while(d->ht[0].table[d->rehashidx] == NULL((void*)0)) {
          d->rehashidx++;
          if (--empty_visits == 0) return 1;
      }
      de = d->ht[0].table[d->rehashidx];
      /* Move all the keys in this bucket from the old to the new hash HT */
      while(de) {
          uint64_t h;

          nextde = de->next;
          /* Get the index in the new hash table */
          h = dictHashKey(d, de->key)(d)->type->hashFunction(de->key) & d->ht[1].sizemask;
          de->next = d->ht[1].table[h];
          d->ht[1].table[h] = de;
          d->ht[0].used--;
          d->ht[1].used++;
          de = nextde;
      }
      d->ht[0].table[d->rehashidx] = NULL((void*)0);
      d->rehashidx++;
  }

  /* Check if we already rehashed the whole table... */
  if (d->ht[0].used == 0) {
      zfree(d->ht[0].table);
      d->ht[0] = d->ht[1];
      _dictReset(&d->ht[1]);
      d->rehashidx = -1;
      return 0;
  }

  /* More to rehash... */
  return 1;
254}

256long long timeInMilliseconds(void) {
  struct timeval tv;

  gettimeofday(&tv,NULL((void*)0));
  return (((long long)tv.tv_sec)*1000)+(tv.tv_usec/1000);
261}

263/* Rehash in ms+"delta" milliseconds. The value of "delta" is larger 
* than 0, and is smaller than 1 in most cases. The exact upper bound 
* depends on the running time of dictRehash(d,100).*/
266int dictRehashMilliseconds(dict *d, int ms) {
  if (d->pauserehash > 0) return 0;

  long long start = timeInMilliseconds();
  int rehashes = 0;

  while(dictRehash(d,100)) {
      rehashes += 100;
      if (timeInMilliseconds()-start > ms) break;
  }
  return rehashes;
277}

279/* This function performs just a step of rehashing, and only if hashing has
* not been paused for our hash table. When we have iterators in the
* middle of a rehashing we can't mess with the two hash tables otherwise
* some element can be missed or duplicated.
*
* This function is called by common lookup or update operations in the
* dictionary so that the hash table automatically migrates from H1 to H2
* while it is actively used. */
287static void _dictRehashStep(dict *d) {
  if (d->pauserehash == 0) dictRehash(d,1);
289}

291/* Add an element to the target hash table */
292int dictAdd(dict *d, void *key, void *val)
293{
  dictEntry *entry = dictAddRaw(d,key,NULL((void*)0));

  if (!entry) return DICT_ERR1;
  dictSetVal(d, entry, val)do { if ((d)->type->valDup) (entry)->v.val = (d)->
type->valDup((d)->privdata, val); else (entry)->v.val
 = (val); } while(0);
  return DICT_OK0;
299}

301/* Low level add or find:
* This function adds the entry but instead of setting a value returns the
* dictEntry structure to the user, that will make sure to fill the value
* field as they wish.
*
* This function is also directly exposed to the user API to be called
* mainly in order to store non-pointers inside the hash value, example:
*
* entry = dictAddRaw(dict,mykey,NULL);
* if (entry != NULL) dictSetSignedIntegerVal(entry,1000);
*
* Return values:
*
* If key already exists NULL is returned, and "*existing" is populated
* with the existing entry if existing is not NULL.
*
* If key was added, the hash entry is returned to be manipulated by the caller.
*/
319dictEntry *dictAddRaw(dict *d, void *key, dictEntry **existing)
320{
  long index;
  dictEntry *entry;
  dictht *ht;

  if (dictIsRehashing(d)((d)->rehashidx != -1)) _dictRehashStep(d);

  /* Get the index of the new element, or -1 if
   * the element already exists. */
  if ((index = _dictKeyIndex(d, key, dictHashKey(d,key)(d)->type->hashFunction(key), existing)) == -1)
      return NULL((void*)0);

  /* Allocate the memory and store the new entry.
   * Insert the element in top, with the assumption that in a database
   * system it is more likely that recently added entries are accessed
   * more frequently. */
  ht = dictIsRehashing(d)((d)->rehashidx != -1) ? &d->ht[1] : &d->ht[0];
  entry = zmalloc(sizeof(*entry));
  entry->next = ht->table[index];
  ht->table[index] = entry;
  ht->used++;

  /* Set the hash entry fields. */
  dictSetKey(d, entry, key)do { if ((d)->type->keyDup) (entry)->key = (d)->type
->keyDup((d)->privdata, key); else (entry)->key = (key
); } while(0);
  return entry;
345}

347/* Add or Overwrite:
* Add an element, discarding the old value if the key already exists.
* Return 1 if the key was added from scratch, 0 if there was already an
* element with such key and dictReplace() just performed a value update
* operation. */
352int dictReplace(dict *d, void *key, void *val)
353{
  dictEntry *entry, *existing, auxentry;

  /* Try to add the element. If the key
   * does not exists dictAdd will succeed. */
  entry = dictAddRaw(d,key,&existing);
  if (entry) {
      dictSetVal(d, entry, val)do { if ((d)->type->valDup) (entry)->v.val = (d)->
type->valDup((d)->privdata, val); else (entry)->v.val
 = (val); } while(0);
      return 1;
  }

  /* Set the new value and free the old one. Note that it is important
   * to do that in this order, as the value may just be exactly the same
   * as the previous one. In this context, think to reference counting,
   * you want to increment (set), and then decrement (free), and not the
   * reverse. */
  auxentry = *existing;
  dictSetVal(d, existing, val)do { if ((d)->type->valDup) (existing)->v.val = (d)->
type->valDup((d)->privdata, val); else (existing)->v
.val = (val); } while(0);
  dictFreeVal(d, &auxentry)if ((d)->type->valDestructor) (d)->type->valDestructor
((d)->privdata, (&auxentry)->v.val);
  return 0;
373}

375/* Add or Find:
* dictAddOrFind() is simply a version of dictAddRaw() that always
* returns the hash entry of the specified key, even if the key already
* exists and can't be added (in that case the entry of the already
* existing key is returned.)
*
* See dictAddRaw() for more information. */
382dictEntry *dictAddOrFind(dict *d, void *key) {
  dictEntry *entry, *existing;
  entry = dictAddRaw(d,key,&existing);
  return entry ? entry : existing;
386}

388/* Search and remove an element. This is an helper function for
* dictDelete() and dictUnlink(), please check the top comment
* of those functions. */
391static dictEntry *dictGenericDelete(dict *d, const void *key, int nofree) {
  uint64_t h, idx;
  dictEntry *he, *prevHe;
  int table;

  if (d->ht[0].used == 0 && d->ht[1].used == 0) return NULL((void*)0);

  if (dictIsRehashing(d)((d)->rehashidx != -1)) _dictRehashStep(d);
  h = dictHashKey(d, key)(d)->type->hashFunction(key);

  for (table = 0; table <= 1; table++) {
      idx = h & d->ht[table].sizemask;
      he = d->ht[table].table[idx];
      prevHe = NULL((void*)0);
      while(he) {
          if (key==he->key || dictCompareKeys(d, key, he->key)(((d)->type->keyCompare) ? (d)->type->keyCompare(
(d)->privdata, key, he->key) : (key) == (he->key))) {
              /* Unlink the element from the list */
              if (prevHe)
                  prevHe->next = he->next;
              else
                  d->ht[table].table[idx] = he->next;
              if (!nofree) {
                  dictFreeKey(d, he)if ((d)->type->keyDestructor) (d)->type->keyDestructor
((d)->privdata, (he)->key);
                  dictFreeVal(d, he)if ((d)->type->valDestructor) (d)->type->valDestructor
((d)->privdata, (he)->v.val);
                  zfree(he);
              }
              d->ht[table].used--;
              return he;
          }
          prevHe = he;
          he = he->next;
      }
      if (!dictIsRehashing(d)((d)->rehashidx != -1)) break;
  }
  return NULL((void*)0); /* not found */
426}

428/* Remove an element, returning DICT_OK on success or DICT_ERR if the
* element was not found. */
430int dictDelete(dict *ht, const void *key) {
  return dictGenericDelete(ht,key,0) ? DICT_OK0 : DICT_ERR1;
432}

434/* Remove an element from the table, but without actually releasing
* the key, value and dictionary entry. The dictionary entry is returned
* if the element was found (and unlinked from the table), and the user
* should later call `dictFreeUnlinkedEntry()` with it in order to release it.
* Otherwise if the key is not found, NULL is returned.
*
* This function is useful when we want to remove something from the hash
* table but want to use its value before actually deleting the entry.
* Without this function the pattern would require two lookups:
*
*  entry = dictFind(...);
*  // Do something with entry
*  dictDelete(dictionary,entry);
*
* Thanks to this function it is possible to avoid this, and use
* instead:
*
* entry = dictUnlink(dictionary,entry);
* // Do something with entry
* dictFreeUnlinkedEntry(entry); // <- This does not need to lookup again.
*/
455dictEntry *dictUnlink(dict *ht, const void *key) {
  return dictGenericDelete(ht,key,1);
457}

459/* You need to call this function to really free the entry after a call
* to dictUnlink(). It's safe to call this function with 'he' = NULL. */
461void dictFreeUnlinkedEntry(dict *d, dictEntry *he) {
  if (he == NULL((void*)0)) return;
  dictFreeKey(d, he)if ((d)->type->keyDestructor) (d)->type->keyDestructor
((d)->privdata, (he)->key);
  dictFreeVal(d, he)if ((d)->type->valDestructor) (d)->type->valDestructor
((d)->privdata, (he)->v.val);
  zfree(he);
466}

468/* Destroy an entire dictionary */
469int _dictClear(dict *d, dictht *ht, void(callback)(void *)) {
  unsigned long i;

  /* Free all the elements */
  for (i = 0; i < ht->size && ht->used > 0; i++) {
      dictEntry *he, *nextHe;

      if (callback && (i & 65535) == 0) callback(d->privdata);

      if ((he = ht->table[i]) == NULL((void*)0)) continue;
      while(he) {
          nextHe = he->next;
          dictFreeKey(d, he)if ((d)->type->keyDestructor) (d)->type->keyDestructor
((d)->privdata, (he)->key);
          dictFreeVal(d, he)if ((d)->type->valDestructor) (d)->type->valDestructor
((d)->privdata, (he)->v.val);
          zfree(he);
          ht->used--;
          he = nextHe;
      }
  }
  /* Free the table and the allocated cache structure */
  zfree(ht->table);
  /* Re-initialize the table */
  _dictReset(ht);
  return DICT_OK0; /* never fails */
493}

495/* Clear & Release the hash table */
496void dictRelease(dict *d)
497{
  _dictClear(d,&d->ht[0],NULL((void*)0));
  _dictClear(d,&d->ht[1],NULL((void*)0));
  zfree(d);
501}

503dictEntry *dictFind(dict *d, const void *key)
504{
  dictEntry *he;
  uint64_t h, idx, table;

  if (dictSize(d)((d)->ht[0].used+(d)->ht[1].used) == 0) return NULL((void*)0); /* dict is empty */
  if (dictIsRehashing(d)((d)->rehashidx != -1)) _dictRehashStep(d);
  h = dictHashKey(d, key)(d)->type->hashFunction(key);
  for (table = 0; table <= 1; table++) {
      idx = h & d->ht[table].sizemask;
      he = d->ht[table].table[idx];
      while(he) {
          if (key==he->key || dictCompareKeys(d, key, he->key)(((d)->type->keyCompare) ? (d)->type->keyCompare(
(d)->privdata, key, he->key) : (key) == (he->key)))
              return he;
          he = he->next;
      }
      if (!dictIsRehashing(d)((d)->rehashidx != -1)) return NULL((void*)0);
  }
  return NULL((void*)0);
522}

524void *dictFetchValue(dict *d, const void *key) {
  dictEntry *he;

  he = dictFind(d,key);
  return he ? dictGetVal(he)((he)->v.val) : NULL((void*)0);
529}

531/* A fingerprint is a 64 bit number that represents the state of the dictionary
* at a given time, it's just a few dict properties xored together.
* When an unsafe iterator is initialized, we get the dict fingerprint, and check
* the fingerprint again when the iterator is released.
* If the two fingerprints are different it means that the user of the iterator
* performed forbidden operations against the dictionary while iterating. */
537long long dictFingerprint(dict *d) {
  long long integers[6], hash = 0;
  int j;

  integers[0] = (long) d->ht[0].table;
  integers[1] = d->ht[0].size;
  integers[2] = d->ht[0].used;
  integers[3] = (long) d->ht[1].table;
  integers[4] = d->ht[1].size;
  integers[5] = d->ht[1].used;

  /* We hash N integers by summing every successive integer with the integer
   * hashing of the previous sum. Basically:
   *
   * Result = hash(hash(hash(int1)+int2)+int3) ...
   *
   * This way the same set of integers in a different order will (likely) hash
   * to a different number. */
  for (j = 0; j < 6; j++) {
      hash += integers[j];
      /* For the hashing step we use Tomas Wang's 64 bit integer hash. */
      hash = (~hash) + (hash << 21); // hash = (hash << 21) - hash - 1;
      hash = hash ^ (hash >> 24);
      hash = (hash + (hash << 3)) + (hash << 8); // hash * 265
      hash = hash ^ (hash >> 14);
      hash = (hash + (hash << 2)) + (hash << 4); // hash * 21
      hash = hash ^ (hash >> 28);
      hash = hash + (hash << 31);
  }
  return hash;
567}

569dictIterator *dictGetIterator(dict *d)
570{
  dictIterator *iter = zmalloc(sizeof(*iter));

  iter->d = d;
  iter->table = 0;
  iter->index = -1;
  iter->safe = 0;
  iter->entry = NULL((void*)0);
  iter->nextEntry = NULL((void*)0);
  return iter;
580}

582dictIterator *dictGetSafeIterator(dict *d) {
  dictIterator *i = dictGetIterator(d);

  i->safe = 1;
  return i;
587}

589dictEntry *dictNext(dictIterator *iter)
590{
  while (1) {
      if (iter->entry == NULL((void*)0)) {
          dictht *ht = &iter->d->ht[iter->table];
          if (iter->index == -1 && iter->table == 0) {
              if (iter->safe)
                  dictPauseRehashing(iter->d)(iter->d)->pauserehash++;
              else
                  iter->fingerprint = dictFingerprint(iter->d);
          }
          iter->index++;
          if (iter->index >= (long) ht->size) {
              if (dictIsRehashing(iter->d)((iter->d)->rehashidx != -1) && iter->table == 0) {
                  iter->table++;
                  iter->index = 0;
                  ht = &iter->d->ht[1];
              } else {
                  break;
              }
          }
          iter->entry = ht->table[iter->index];
      } else {
          iter->entry = iter->nextEntry;
      }
      if (iter->entry) {
          /* We need to save the 'next' here, the iterator user
           * may delete the entry we are returning. */
          iter->nextEntry = iter->entry->next;
          return iter->entry;
      }
  }
  return NULL((void*)0);
622}

624void dictReleaseIterator(dictIterator *iter)
625{
  if (!(iter->index == -1 && iter->table == 0)) {
      if (iter->safe)
          dictResumeRehashing(iter->d)(iter->d)->pauserehash--;
      else
          assert(iter->fingerprint == dictFingerprint(iter->d))(__builtin_expect(!!((iter->fingerprint == dictFingerprint
(iter->d))), 1)?(void)0 : (_serverAssert("iter->fingerprint == dictFingerprint(iter->d)"
,"dict.c",630),__builtin_unreachable()));
  }
  zfree(iter);
633}

635/* Return a random entry from the hash table. Useful to
* implement randomized algorithms */
637dictEntry *dictGetRandomKey(dict *d)
638{
  dictEntry *he, *orighe;
  unsigned long h;
  int listlen, listele;

  if (dictSize(d)((d)->ht[0].used+(d)->ht[1].used) == 0) return NULL((void*)0);
4
←
Assuming the condition is false→
5
←
Taking false branch→
  if (dictIsRehashing(d)((d)->rehashidx != -1)) _dictRehashStep(d);
6
←
Assuming the condition is false→
7
←
Taking false branch→
  if (dictIsRehashing(d)((d)->rehashidx != -1)) {
8
←
Taking false branch→
      do {
          /* We are sure there are no elements in indexes from 0
           * to rehashidx-1 */
          h = d->rehashidx + (randomULong()((unsigned long) genrand64_int64()) % (dictSlots(d)((d)->ht[0].size+(d)->ht[1].size) - d->rehashidx));
          he = (h >= d->ht[0].size) ? d->ht[1].table[h - d->ht[0].size] :
                                    d->ht[0].table[h];
      } while(he == NULL((void*)0));
  } else {
      do {
10
←
Loop condition is false.  Exiting loop→
          h = randomULong()((unsigned long) genrand64_int64()) & d->ht[0].sizemask;
          he = d->ht[0].table[h];
      } while(he == NULL((void*)0));
9
←
Assuming 'he' is not equal to NULL→
  }

  /* Now we found a non empty bucket, but it is a linked
   * list and we need to get a random element from the list.
   * The only sane way to do so is counting the elements and
   * select a random index. */
  listlen = 0;
  orighe = he;
  while(he) {
11
←
Loop condition is true.  Entering loop body→
12
←
Loop condition is true.  Entering loop body→
13
←
Assuming pointer value is null→
14
←
Loop condition is false. Execution continues on line 670→
      he = he->next;
      listlen++;
  }
  listele = random() % listlen;
  he = orighe;
  while(listele--) he = he->next;
15
←
Loop condition is true.  Entering loop body→
16
←
Loop condition is true.  Entering loop body→
17
←
Null pointer value stored to 'he'→
18
←
Loop condition is true.  Entering loop body→
19
←
Access to field 'next' results in a dereference of a null pointer (loaded from variable 'he')
  return he;
674}

676/* This function samples the dictionary to return a few keys from random
* locations.
*
* It does not guarantee to return all the keys specified in 'count', nor
* it does guarantee to return non-duplicated elements, however it will make
* some effort to do both things.
*
* Returned pointers to hash table entries are stored into 'des' that
* points to an array of dictEntry pointers. The array must have room for
* at least 'count' elements, that is the argument we pass to the function
* to tell how many random elements we need.
*
* The function returns the number of items stored into 'des', that may
* be less than 'count' if the hash table has less than 'count' elements
* inside, or if not enough elements were found in a reasonable amount of
* steps.
*
* Note that this function is not suitable when you need a good distribution
* of the returned items, but only when you need to "sample" a given number
* of continuous elements to run some kind of algorithm or to produce
* statistics. However the function is much faster than dictGetRandomKey()
* at producing N elements. */
698unsigned int dictGetSomeKeys(dict *d, dictEntry **des, unsigned int count) {
  unsigned long j; /* internal hash table id, 0 or 1. */
  unsigned long tables; /* 1 or 2 tables? */
  unsigned long stored = 0, maxsizemask;
  unsigned long maxsteps;

  if (dictSize(d)((d)->ht[0].used+(d)->ht[1].used) < count) count = dictSize(d)((d)->ht[0].used+(d)->ht[1].used);
  maxsteps = count*10;

  /* Try to do a rehashing work proportional to 'count'. */
  for (j = 0; j < count; j++) {
      if (dictIsRehashing(d)((d)->rehashidx != -1))
          _dictRehashStep(d);
      else
          break;
  }

  tables = dictIsRehashing(d)((d)->rehashidx != -1) ? 2 : 1;
  maxsizemask = d->ht[0].sizemask;
  if (tables > 1 && maxsizemask < d->ht[1].sizemask)
      maxsizemask = d->ht[1].sizemask;

  /* Pick a random point inside the larger table. */
  unsigned long i = randomULong()((unsigned long) genrand64_int64()) & maxsizemask;
  unsigned long emptylen = 0; /* Continuous empty entries so far. */
  while(stored < count && maxsteps--) {
      for (j = 0; j < tables; j++) {
          /* Invariant of the dict.c rehashing: up to the indexes already
           * visited in ht[0] during the rehashing, there are no populated
           * buckets, so we can skip ht[0] for indexes between 0 and idx-1. */
          if (tables == 2 && j == 0 && i < (unsigned long) d->rehashidx) {
              /* Moreover, if we are currently out of range in the second
               * table, there will be no elements in both tables up to
               * the current rehashing index, so we jump if possible.
               * (this happens when going from big to small table). */
              if (i >= d->ht[1].size)
                  i = d->rehashidx;
              else
                  continue;
          }
          if (i >= d->ht[j].size) continue; /* Out of range for this table. */
          dictEntry *he = d->ht[j].table[i];

          /* Count contiguous empty buckets, and jump to other
           * locations if they reach 'count' (with a minimum of 5). */
          if (he == NULL((void*)0)) {
              emptylen++;
              if (emptylen >= 5 && emptylen > count) {
                  i = randomULong()((unsigned long) genrand64_int64()) & maxsizemask;
                  emptylen = 0;
              }
          } else {
              emptylen = 0;
              while (he) {
                  /* Collect all the elements of the buckets found non
                   * empty while iterating. */
                  *des = he;
                  des++;
                  he = he->next;
                  stored++;
                  if (stored == count) return stored;
              }
          }
      }
      i = (i+1) & maxsizemask;
  }
  return stored;
765}

767/* This is like dictGetRandomKey() from the POV of the API, but will do more
* work to ensure a better distribution of the returned element.
*
* This function improves the distribution because the dictGetRandomKey()
* problem is that it selects a random bucket, then it selects a random
* element from the chain in the bucket. However elements being in different
* chain lengths will have different probabilities of being reported. With
* this function instead what we do is to consider a "linear" range of the table
* that may be constituted of N buckets with chains of different lengths
* appearing one after the other. Then we report a random element in the range.
* In this way we smooth away the problem of different chain lengths. */
778#define GETFAIR_NUM_ENTRIES15 15
779dictEntry *dictGetFairRandomKey(dict *d) {
  dictEntry *entries[GETFAIR_NUM_ENTRIES15];
  unsigned int count = dictGetSomeKeys(d,entries,GETFAIR_NUM_ENTRIES15);
  /* Note that dictGetSomeKeys() may return zero elements in an unlucky
   * run() even if there are actually elements inside the hash table. So
   * when we get zero, we call the true dictGetRandomKey() that will always
   * yield the element if the hash table has at least one. */
  if (count == 0) return dictGetRandomKey(d);
1
Assuming 'count' is equal to 0→
2
←
Taking true branch→
3
←
Calling 'dictGetRandomKey'→
  unsigned int idx = rand() % count;
  return entries[idx];
789}

791/* Function to reverse bits. Algorithm from:
* http://graphics.stanford.edu/~seander/bithacks.html#ReverseParallel */
793static unsigned long rev(unsigned long v) {
  unsigned long s = CHAR_BIT8 * sizeof(v); // bit size; must be power of 2
  unsigned long mask = ~0UL;
  while ((s >>= 1) > 0) {
      mask ^= (mask << s);
      v = ((v >> s) & mask) | ((v << s) & ~mask);
  }
  return v;
801}

803/* dictScan() is used to iterate over the elements of a dictionary.
*
* Iterating works the following way:
*
* 1) Initially you call the function using a cursor (v) value of 0.
* 2) The function performs one step of the iteration, and returns the
*    new cursor value you must use in the next call.
* 3) When the returned cursor is 0, the iteration is complete.
*
* The function guarantees all elements present in the
* dictionary get returned between the start and end of the iteration.
* However it is possible some elements get returned multiple times.
*
* For every element returned, the callback argument 'fn' is
* called with 'privdata' as first argument and the dictionary entry
* 'de' as second argument.
*
* HOW IT WORKS.
*
* The iteration algorithm was designed by Pieter Noordhuis.
* The main idea is to increment a cursor starting from the higher order
* bits. That is, instead of incrementing the cursor normally, the bits
* of the cursor are reversed, then the cursor is incremented, and finally
* the bits are reversed again.
*
* This strategy is needed because the hash table may be resized between
* iteration calls.
*
* dict.c hash tables are always power of two in size, and they
* use chaining, so the position of an element in a given table is given
* by computing the bitwise AND between Hash(key) and SIZE-1
* (where SIZE-1 is always the mask that is equivalent to taking the rest
*  of the division between the Hash of the key and SIZE).
*
* For example if the current hash table size is 16, the mask is
* (in binary) 1111. The position of a key in the hash table will always be
* the last four bits of the hash output, and so forth.
*
* WHAT HAPPENS IF THE TABLE CHANGES IN SIZE?
*
* If the hash table grows, elements can go anywhere in one multiple of
* the old bucket: for example let's say we already iterated with
* a 4 bit cursor 1100 (the mask is 1111 because hash table size = 16).
*
* If the hash table will be resized to 64 elements, then the new mask will
* be 111111. The new buckets you obtain by substituting in ??1100
* with either 0 or 1 can be targeted only by keys we already visited
* when scanning the bucket 1100 in the smaller hash table.
*
* By iterating the higher bits first, because of the inverted counter, the
* cursor does not need to restart if the table size gets bigger. It will
* continue iterating using cursors without '1100' at the end, and also
* without any other combination of the final 4 bits already explored.
*
* Similarly when the table size shrinks over time, for example going from
* 16 to 8, if a combination of the lower three bits (the mask for size 8
* is 111) were already completely explored, it would not be visited again
* because we are sure we tried, for example, both 0111 and 1111 (all the
* variations of the higher bit) so we don't need to test it again.
*
* WAIT... YOU HAVE *TWO* TABLES DURING REHASHING!
*
* Yes, this is true, but we always iterate the smaller table first, then
* we test all the expansions of the current cursor into the larger
* table. For example if the current cursor is 101 and we also have a
* larger table of size 16, we also test (0)101 and (1)101 inside the larger
* table. This reduces the problem back to having only one table, where
* the larger one, if it exists, is just an expansion of the smaller one.
*
* LIMITATIONS
*
* This iterator is completely stateless, and this is a huge advantage,
* including no additional memory used.
*
* The disadvantages resulting from this design are:
*
* 1) It is possible we return elements more than once. However this is usually
*    easy to deal with in the application level.
* 2) The iterator must return multiple elements per call, as it needs to always
*    return all the keys chained in a given bucket, and all the expansions, so
*    we are sure we don't miss keys moving during rehashing.
* 3) The reverse cursor is somewhat hard to understand at first, but this
*    comment is supposed to help.
*/
887unsigned long dictScan(dict *d,
                     unsigned long v,
                     dictScanFunction *fn,
                     dictScanBucketFunction* bucketfn,
                     void *privdata)
892{
  dictht *t0, *t1;
  const dictEntry *de, *next;
  unsigned long m0, m1;

  if (dictSize(d)((d)->ht[0].used+(d)->ht[1].used) == 0) return 0;

  /* This is needed in case the scan callback tries to do dictFind or alike. */
  dictPauseRehashing(d)(d)->pauserehash++;

  if (!dictIsRehashing(d)((d)->rehashidx != -1)) {
      t0 = &(d->ht[0]);
      m0 = t0->sizemask;

      /* Emit entries at cursor */
      if (bucketfn) bucketfn(privdata, &t0->table[v & m0]);
      de = t0->table[v & m0];
      while (de) {
          next = de->next;
          fn(privdata, de);
          de = next;
      }

      /* Set unmasked bits so incrementing the reversed cursor
       * operates on the masked bits */
      v |= ~m0;

      /* Increment the reverse cursor */
      v = rev(v);
      v++;
      v = rev(v);

  } else {
      t0 = &d->ht[0];
      t1 = &d->ht[1];

      /* Make sure t0 is the smaller and t1 is the bigger table */
      if (t0->size > t1->size) {
          t0 = &d->ht[1];
          t1 = &d->ht[0];
      }

      m0 = t0->sizemask;
      m1 = t1->sizemask;

      /* Emit entries at cursor */
      if (bucketfn) bucketfn(privdata, &t0->table[v & m0]);
      de = t0->table[v & m0];
      while (de) {
          next = de->next;
          fn(privdata, de);
          de = next;
      }

      /* Iterate over indices in larger table that are the expansion
       * of the index pointed to by the cursor in the smaller table */
      do {
          /* Emit entries at cursor */
          if (bucketfn) bucketfn(privdata, &t1->table[v & m1]);
          de = t1->table[v & m1];
          while (de) {
              next = de->next;
              fn(privdata, de);
              de = next;
          }

          /* Increment the reverse cursor not covered by the smaller mask.*/
          v |= ~m1;
          v = rev(v);
          v++;
          v = rev(v);

          /* Continue while bits covered by mask difference is non-zero */
      } while (v & (m0 ^ m1));
  }

  dictResumeRehashing(d)(d)->pauserehash--;

  return v;
971}

973/* ------------------------- private functions ------------------------------ */

975/* Because we may need to allocate huge memory chunk at once when dict
* expands, we will check this allocation is allowed or not if the dict
* type has expandAllowed member function. */
978static int dictTypeExpandAllowed(dict *d) {
  if (d->type->expandAllowed == NULL((void*)0)) return 1;
  return d->type->expandAllowed(
                  _dictNextPower(d->ht[0].used + 1) * sizeof(dictEntry*),
                  (double)d->ht[0].used / d->ht[0].size);
983}

985/* Expand the hash table if needed */
986static int _dictExpandIfNeeded(dict *d)
987{
  /* Incremental rehashing already in progress. Return. */
  if (dictIsRehashing(d)((d)->rehashidx != -1)) return DICT_OK0;

  /* If the hash table is empty expand it to the initial size. */
  if (d->ht[0].size == 0) return dictExpand(d, DICT_HT_INITIAL_SIZE4);

  /* If we reached the 1:1 ratio, and we are allowed to resize the hash
   * table (global setting) or we should avoid it but the ratio between
   * elements/buckets is over the "safe" threshold, we resize doubling
   * the number of buckets. */
  if (d->ht[0].used >= d->ht[0].size &&
      (dict_can_resize ||
       d->ht[0].used/d->ht[0].size > dict_force_resize_ratio) &&
      dictTypeExpandAllowed(d))
  {
      return dictExpand(d, d->ht[0].used + 1);
  }
  return DICT_OK0;
1006}

1008/* Our hash table capability is a power of two */
1009static unsigned long _dictNextPower(unsigned long size)
1010{
  unsigned long i = DICT_HT_INITIAL_SIZE4;

  if (size >= LONG_MAX9223372036854775807L) return LONG_MAX9223372036854775807L + 1LU;
  while(1) {
      if (i >= size)
          return i;
      i *= 2;
  }
1019}

1021/* Returns the index of a free slot that can be populated with
* a hash entry for the given 'key'.
* If the key already exists, -1 is returned
* and the optional output parameter may be filled.
*
* Note that if we are in the process of rehashing the hash table, the
* index is always returned in the context of the second (new) hash table. */
1028static long _dictKeyIndex(dict *d, const void *key, uint64_t hash, dictEntry **existing)
1029{
  unsigned long idx, table;
  dictEntry *he;
  if (existing) *existing = NULL((void*)0);

  /* Expand the hash table if needed */
  if (_dictExpandIfNeeded(d) == DICT_ERR1)
      return -1;
  for (table = 0; table <= 1; table++) {
      idx = hash & d->ht[table].sizemask;
      /* Search if this slot does not already contain the given key */
      he = d->ht[table].table[idx];
      while(he) {
          if (key==he->key || dictCompareKeys(d, key, he->key)(((d)->type->keyCompare) ? (d)->type->keyCompare(
(d)->privdata, key, he->key) : (key) == (he->key))) {
              if (existing) *existing = he;
              return -1;
          }
          he = he->next;
      }
      if (!dictIsRehashing(d)((d)->rehashidx != -1)) break;
  }
  return idx;
1051}

1053void dictEmpty(dict *d, void(callback)(void*)) {
  _dictClear(d,&d->ht[0],callback);
  _dictClear(d,&d->ht[1],callback);
  d->rehashidx = -1;
  d->pauserehash = 0;
1058}

1060void dictEnableResize(void) {
  dict_can_resize = 1;
1062}

1064void dictDisableResize(void) {
  dict_can_resize = 0;
1066}

1068uint64_t dictGetHash(dict *d, const void *key) {
  return dictHashKey(d, key)(d)->type->hashFunction(key);
1070}

1072/* Finds the dictEntry reference by using pointer and pre-calculated hash.
* oldkey is a dead pointer and should not be accessed.
* the hash value should be provided using dictGetHash.
* no string / key comparison is performed.
* return value is the reference to the dictEntry if found, or NULL if not found. */
1077dictEntry **dictFindEntryRefByPtrAndHash(dict *d, const void *oldptr, uint64_t hash) {
  dictEntry *he, **heref;
  unsigned long idx, table;

  if (dictSize(d)((d)->ht[0].used+(d)->ht[1].used) == 0) return NULL((void*)0); /* dict is empty */
  for (table = 0; table <= 1; table++) {
      idx = hash & d->ht[table].sizemask;
      heref = &d->ht[table].table[idx];
      he = *heref;
      while(he) {
          if (oldptr==he->key)
              return heref;
          heref = &he->next;
          he = *heref;
      }
      if (!dictIsRehashing(d)((d)->rehashidx != -1)) return NULL((void*)0);
  }
  return NULL((void*)0);
1095}

1097/* ------------------------------- Debugging ---------------------------------*/

1099#define DICT_STATS_VECTLEN50 50
1100size_t _dictGetStatsHt(char *buf, size_t bufsize, dictht *ht, int tableid) {
  unsigned long i, slots = 0, chainlen, maxchainlen = 0;
  unsigned long totchainlen = 0;
  unsigned long clvector[DICT_STATS_VECTLEN50];
  size_t l = 0;

  if (ht->used == 0) {
      return snprintf(buf,bufsize,
          "No stats available for empty dictionaries\n");
  }

  /* Compute stats. */
  for (i = 0; i < DICT_STATS_VECTLEN50; i++) clvector[i] = 0;
  for (i = 0; i < ht->size; i++) {
      dictEntry *he;

      if (ht->table[i] == NULL((void*)0)) {
          clvector[0]++;
          continue;
      }
      slots++;
      /* For each hash entry on this slot... */
      chainlen = 0;
      he = ht->table[i];
      while(he) {
          chainlen++;
          he = he->next;
      }
      clvector[(chainlen < DICT_STATS_VECTLEN50) ? chainlen : (DICT_STATS_VECTLEN50-1)]++;
      if (chainlen > maxchainlen) maxchainlen = chainlen;
      totchainlen += chainlen;
  }

  /* Generate human readable stats. */
  l += snprintf(buf+l,bufsize-l,
      "Hash table %d stats (%s):\n"
      " table size: %lu\n"
      " number of elements: %lu\n"
      " different slots: %lu\n"
      " max chain length: %lu\n"
      " avg chain length (counted): %.02f\n"
      " avg chain length (computed): %.02f\n"
      " Chain length distribution:\n",
      tableid, (tableid == 0) ? "main hash table" : "rehashing target",
      ht->size, ht->used, slots, maxchainlen,
      (float)totchainlen/slots, (float)ht->used/slots);

  for (i = 0; i < DICT_STATS_VECTLEN50-1; i++) {
      if (clvector[i] == 0) continue;
      if (l >= bufsize) break;
      l += snprintf(buf+l,bufsize-l,
          "   %s%ld: %ld (%.02f%%)\n",
          (i == DICT_STATS_VECTLEN50-1)?">= ":"",
          i, clvector[i], ((float)clvector[i]/ht->size)*100);
  }

  /* Unlike snprintf(), return the number of characters actually written. */
  if (bufsize) buf[bufsize-1] = '\0';
  return strlen(buf);
1159}

1161void dictGetStats(char *buf, size_t bufsize, dict *d) {
  size_t l;
  char *orig_buf = buf;
  size_t orig_bufsize = bufsize;

  l = _dictGetStatsHt(buf,bufsize,&d->ht[0],0);
  buf += l;
  bufsize -= l;
  if (dictIsRehashing(d)((d)->rehashidx != -1) && bufsize > 0) {
      _dictGetStatsHt(buf,bufsize,&d->ht[1],1);
  }
  /* Make sure there is a NULL term at the end. */
  if (orig_bufsize) orig_buf[orig_bufsize-1] = '\0';
1174}

1176/* ------------------------------- Benchmark ---------------------------------*/

1178#ifdef DICT_BENCHMARK_MAIN

1180#include "sds.h"

1182uint64_t hashCallback(const void *key) {
  return dictGenHashFunction((unsigned char*)key, sdslen((char*)key));
1184}

1186int compareCallback(void *privdata, const void *key1, const void *key2) {
  int l1,l2;
  DICT_NOTUSED(privdata)((void) privdata);

  l1 = sdslen((sds)key1);
  l2 = sdslen((sds)key2);
  if (l1 != l2) return 0;
  return memcmp(key1, key2, l1) == 0;
1194}

1196void freeCallback(void *privdata, void *val) {
  DICT_NOTUSED(privdata)((void) privdata);

  sdsfree(val);
1200}

1202dictType BenchmarkDictType = {
  hashCallback,
  NULL((void*)0),
  NULL((void*)0),
  compareCallback,
  freeCallback,
  NULL((void*)0),
  NULL((void*)0)
1210};

1212#define start_benchmark() start = timeInMilliseconds()
1213#define end_benchmark(msg) do { \
  elapsed = timeInMilliseconds()-start; \
  printf(msg ": %ld items in %lld ms\n", count, elapsed); \
1216} while(0)

1218/* dict-benchmark [count] */
1219int main(int argc, char **argv) {
  long j;
  long long start, elapsed;
  dict *dict = dictCreate(&BenchmarkDictType,NULL((void*)0));
  long count = 0;

  if (argc == 2) {
      count = strtol(argv[1],NULL((void*)0),10);
  } else {
      count = 5000000;
  }

  start_benchmark();
  for (j = 0; j < count; j++) {
      int retval = dictAdd(dict,sdsfromlonglong(j),(void*)j);
      assert(retval == DICT_OK)(__builtin_expect(!!((retval == 0)), 1)?(void)0 : (_serverAssert
("retval == DICT_OK","dict.c",1234),__builtin_unreachable()));
  }
  end_benchmark("Inserting");
  assert((long)dictSize(dict) == count)(__builtin_expect(!!(((long)((dict)->ht[0].used+(dict)->
ht[1].used) == count)), 1)?(void)0 : (_serverAssert("(long)dictSize(dict) == count"
,"dict.c",1237),__builtin_unreachable()));

  /* Wait for rehashing. */
  while (dictIsRehashing(dict)((dict)->rehashidx != -1)) {
      dictRehashMilliseconds(dict,100);
  }

  start_benchmark();
  for (j = 0; j < count; j++) {
      sds key = sdsfromlonglong(j);
      dictEntry *de = dictFind(dict,key);
      assert(de != NULL)(__builtin_expect(!!((de != ((void*)0))), 1)?(void)0 : (_serverAssert
("de != NULL","dict.c",1248),__builtin_unreachable()));
      sdsfree(key);
  }
  end_benchmark("Linear access of existing elements");

  start_benchmark();
  for (j = 0; j < count; j++) {
      sds key = sdsfromlonglong(j);
      dictEntry *de = dictFind(dict,key);
      assert(de != NULL)(__builtin_expect(!!((de != ((void*)0))), 1)?(void)0 : (_serverAssert
("de != NULL","dict.c",1257),__builtin_unreachable()));
      sdsfree(key);
  }
  end_benchmark("Linear access of existing elements (2nd round)");

  start_benchmark();
  for (j = 0; j < count; j++) {
      sds key = sdsfromlonglong(rand() % count);
      dictEntry *de = dictFind(dict,key);
      assert(de != NULL)(__builtin_expect(!!((de != ((void*)0))), 1)?(void)0 : (_serverAssert
("de != NULL","dict.c",1266),__builtin_unreachable()));
      sdsfree(key);
  }
  end_benchmark("Random access of existing elements");

  start_benchmark();
  for (j = 0; j < count; j++) {
      dictEntry *de = dictGetRandomKey(dict);
      assert(de != NULL)(__builtin_expect(!!((de != ((void*)0))), 1)?(void)0 : (_serverAssert
("de != NULL","dict.c",1274),__builtin_unreachable()));
  }
  end_benchmark("Accessing random keys");

  start_benchmark();
  for (j = 0; j < count; j++) {
      sds key = sdsfromlonglong(rand() % count);
      key[0] = 'X';
      dictEntry *de = dictFind(dict,key);
      assert(de == NULL)(__builtin_expect(!!((de == ((void*)0))), 1)?(void)0 : (_serverAssert
("de == NULL","dict.c",1283),__builtin_unreachable()));
      sdsfree(key);
  }
  end_benchmark("Accessing missing");

  start_benchmark();
  for (j = 0; j < count; j++) {
      sds key = sdsfromlonglong(j);
      int retval = dictDelete(dict,key);
      assert(retval == DICT_OK)(__builtin_expect(!!((retval == 0)), 1)?(void)0 : (_serverAssert
("retval == DICT_OK","dict.c",1292),__builtin_unreachable()));
      key[0] += 17; /* Change first number to letter. */
      retval = dictAdd(dict,key,(void*)j);
      assert(retval == DICT_OK)(__builtin_expect(!!((retval == 0)), 1)?(void)0 : (_serverAssert
("retval == DICT_OK","dict.c",1295),__builtin_unreachable()));
  }
  end_benchmark("Removing and adding");
1298}
1299#endif