// 这个函数将游标v的元素放到privdata，并用算法推进cursor，
unsigned long dictScan(dict *d,
                       unsigned long v,
                       dictScanFunction *fn,
                       dictScanBucketFunction* bucketfn,
                       void *privdata)
{
    dictht *t0, *t1;
    const dictEntry *de, *next;
    unsigned long m0, m1;

    if (dictSize(d) == 0) return 0;

    /* Having a safe iterator means no rehashing can happen, see _dictRehashStep.
     * This is needed in case the scan callback tries to do dictFind or alike. */
    d->iterators++;

    if (!dictIsRehashing(d)) {
        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;
            }

            // 这里曾经有个bug，参考下面美团链接
            /* Increment the reverse cursor not covered by the smaller mask.*/
            v |= ~m1;
            v = rev(v);
            v++;
            v = rev(v);

            // 这个(m0 ^ m1)就是前面说到的高位，我认为这个循环只会执行两次，小数组的一个桶下标对应大数组的两个桶下标
            /* Continue while bits covered by mask difference is non-zero */
        } while (v & (m0 ^ m1));
    }

    /* undo the ++ at the top */
    d->iterators--;

    return v;
}

// 这里将非掩码部分置1，如上面说的并非截断
v |= ~m1;
// 翻转
v = rev(v);
// 自增
v++;
// 翻转回来
v = rev(v);

/* Function to reverse bits. Algorithm from:
 * http://graphics.stanford.edu/~seander/bithacks.html#ReverseParallel */
static unsigned long rev(unsigned long v) {
    unsigned long s = CHAR_BIT * 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;
}

/* Step 2: Iterate the collection.
    *
    * Note that if the object is encoded with a ziplist, intset, or any other
    * representation that is not a hash table, we are sure that it is also
    * composed of a small number of elements. So to avoid taking state we
    * just return everything inside the object in a single call, setting the
    * cursor to zero to signal the end of the iteration. */

/* Handle the case of a hash table. */
ht = NULL;
if (o == NULL) {
    ht = c->db->dict;
} else if (o->type == OBJ_SET && o->encoding == OBJ_ENCODING_HT) {
    ht = o->ptr;
} else if (o->type == OBJ_HASH && o->encoding == OBJ_ENCODING_HT) {
    ht = o->ptr;
    count *= 2; /* We return key / value for this type. */
} else if (o->type == OBJ_ZSET && o->encoding == OBJ_ENCODING_SKIPLIST) {
    zset *zs = o->ptr;
    ht = zs->dict;
    count *= 2; /* We return key / value for this type. */
}

if (ht) {
    void *privdata[2];
    /* We set the max number of iterations to ten times the specified
        * COUNT, so if the hash table is in a pathological state (very
        * sparsely populated) we avoid to block too much time at the cost
        * of returning no or very few elements. */
    long maxiterations = count*10;

    /* We pass two pointers to the callback: the list to which it will
        * add new elements, and the object containing the dictionary so that
        * it is possible to fetch more data in a type-dependent way. */
    privdata[0] = keys;
    privdata[1] = o;
    do {
        cursor = dictScan(ht, cursor, scanCallback, NULL, privdata);
    } while (cursor &&
            maxiterations-- &&
            listLength(keys) < (unsigned long)count);
} else if (o->type == OBJ_SET) {
    int pos = 0;
    int64_t ll;

    while(intsetGet(o->ptr,pos++,&ll))
        listAddNodeTail(keys,createStringObjectFromLongLong(ll));
    cursor = 0;
} else if (o->type == OBJ_HASH || o->type == OBJ_ZSET) {
    unsigned char *p = ziplistIndex(o->ptr,0);
    unsigned char *vstr;
    unsigned int vlen;
    long long vll;

    while(p) {
        ziplistGet(p,&vstr,&vlen,&vll);
        listAddNodeTail(keys,
            (vstr != NULL) ? createStringObject((char*)vstr,vlen) :
                                createStringObjectFromLongLong(vll));
        p = ziplistNext(o->ptr,p);
    }
    cursor = 0;
} else {
    serverPanic("Not handled encoding in SCAN.");
}