redis底层数据结构之dict 字典1-chhquan

st0627

//rehash函数，逐步对dict进行rehash　　
//redis并没有一次性完成对dict的rehash，而是把整个rehash过程分成许多小的rehash操作去完成，
　　
//每一次rehash都会处理至多一定数量的桶，由参数n指定。由于部分桶是空的，为防止rehash一直都访问
　　
//到空的桶使rehash过程耗时过多，函数里面设定最多访问 n*10 个桶。
　　
//redis为保持性能的稳定，会把一些有机会耗时较比多的操作，分成放多小的操作，rehash便是其中一个例子。
　　
/* 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. */
　　
int dictRehash(dict *d, int n) {
　　
    int empty_visits = n*10; /* Max number of empty buckets to visit. */
　　
    if (!dictIsRehashing(d)) return 0;
　　
    //访问ht[0]中的桶，如果桶非空，把桶中的元素放进ht[1]里。
　　
    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 */
　　
    //从rehashidx开始，rehashidx便是用来记录rehash过程状态的变量
　　
        assert(d->ht[0].size > (unsigned long)d->rehashidx);
　　
    //找出一个非空桶，总的访问次数受到 empty_visits 的限制
　　
        while(d->ht[0].table[d->rehashidx] == NULL) {
　　
            d->rehashidx++;
　　
            if (--empty_visits == 0) return 1;    //返回1表示rehash还没完成，需要进行进行
　　
        }
　　
        de = d->ht[0].table[d->rehashidx];
　　
    //移动桶中所有条目到ht[1]中
　　
        /* Move all the keys in this bucket from the old to the new hash HT */
　　
        while(de) {
　　
            unsigned int h;
　　
            nextde = de->next;
　　
            /* Get the index in the new hash table */
　　
            h = dictHashKey(d, 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;
　　
        d->rehashidx++;    //已经处理了rehashidx 号桶，下一个桶
　　
    }
　　
    //如果ht[0]已经没有条目了，可以把ht[1]切换到ht[0]，并重置ht[1]。
　　
    /* Check if we already rehashed the whole table... */
　　
    if (d->ht[0].used == 0) {
　　
        zfree(d->ht[0].table);    //释放ht[0]的桶空间
　　
        d->ht[0] = d->ht[1];
　　
        _dictReset(&d->ht[1]);
　　
        d->rehashidx = -1;
　　
        return 0;
　　
    }
　　
    /* More to rehash... */
　　
    return 1;
　　
}