redis源码解析（七）字典结构体函数介绍之二

素颜马尾好姑娘i 2022-04-14 03:37 190阅读 0赞

### 1. 简介 ###

字典结构是redis中的核心结构之一，本文继前文基础上介绍更多字典结构体的相关函数。

### 2.代码解析 ###

/* N步增量重哈希 * 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;
    
        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);
    
    		/*遇到空的就跳过*/
            while(d->ht[0].table[d->rehashidx] == NULL) { 
                d->rehashidx++;
                if (--empty_visits == 0) return 1;
            }
    		
            de = d->ht[0].table[d->rehashidx];
    		
            /* 将哈希表数据移到ht[1]中：平时使用的都是ht[0] * 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->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++;
        }
    
        /* 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;
    }

/*获取时间并转换为毫秒级*/
    long long timeInMilliseconds(void) 
    { 
        struct timeval tv;
    
        gettimeofday(&tv, NULL);
        return (((long long)tv.tv_sec) * 1000) + (tv.tv_usec / 1000);
    }

/* 在ms毫秒内进行重哈希 * Rehash for an amount of time between ms milliseconds and ms+1 milliseconds */
    int dictRehashMilliseconds(dict *d, int ms) 
    { 
        long long start = timeInMilliseconds();
        int rehashes = 0;
    
        while(dictRehash(d, 100)) { 
            rehashes += 100;
            if (timeInMilliseconds()-start > ms) break;
        }
        return rehashes;
    }

/* 一步重哈希，仅在迭代器为0时生效 * This function performs just a step of rehashing, and only if there are * no safe iterators bound to 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. */
    static void _dictRehashStep(dict *d) { 
        if (d->iterators == 0) dictRehash(d, 1);
    }

/* 在哈希表中增加新的项，调用dictAddRaw()函数 * Add an element to the target hash table */
    int dictAdd(dict *d, void *key, void *val)
    { 
        dictEntry *entry = dictAddRaw(d, key, NULL);
    
        if (!entry) return DICT_ERR;
        dictSetVal(d, entry, val);
        return DICT_OK;
    }

/* 底层添加、查找函数：第三项为NULL则添加，不为NULL则查找 * 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 he wishes. * * 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. */
    dictEntry *dictAddRaw(dict *d, void *key, dictEntry **existing)
    { 
        long index;
        dictEntry *entry;
        dictht *ht;
    
        if (dictIsRehashing(d)) _dictRehashStep(d);
    
        /* 获取key对应的索引 * Get the index of the new element, or -1 if * the element already exists. */
        if ((index = _dictKeyIndex(d, key, dictHashKey(d,key), existing)) == -1)
            return NULL;
    
        /* 分配空间并存储新的dictentry，在顶端插入 * 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->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);
        return entry;
    }

/* 添加或复写 * 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. */
    int dictReplace(dict *d, void *key, void *val)
    { 
        dictEntry *entry, *existing, auxentry;
    
        /* 调用dictAddRaw尝试添加key * 成功则返回，失败则继续执行复写操作 * Try to add the element. If the key * does not exists dictAdd will suceed. */
        entry = dictAddRaw(d, key, &existing);
        if (entry) { 
            dictSetVal(d, entry, val);
            return 1;
        }
    
        /* 执行到这里说明key-value键值对已存在，因此使用复写 * 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);
        dictFreeVal(d, &auxentry);
        return 0;
    }

/* 添加或查找：成功添加则返回entry，失败则返回existing * 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. */
    dictEntry *dictAddOrFind(dict *d, void *key) { 
        dictEntry *entry, *existing;
        entry = dictAddRaw(d, key, &existing);
        return entry ? entry : existing;
    }

/* 查找并删除 * Search and remove an element. This is an helper function for * dictDelete() and dictUnlink(), please check the top comment * of those functions. */
    static 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;
    
        if (dictIsRehashing(d)) _dictRehashStep(d);
        h = dictHashKey(d, key);
    
        for (table = 0; table <= 1; table++) { 
            idx = h & d->ht[table].sizemask;
            he = d->ht[table].table[idx];
            prevHe = NULL;
            while(he) { 
    			/*找到了就在链表中卸载并且释放空间*/
                if (key==he->key || dictCompareKeys(d, key, he->key)) { 
                    /* Unlink the element from the list */
                    if (prevHe)
                        prevHe->next = he->next;
                    else
                        d->ht[table].table[idx] = he->next;
    
    				/*nofree控制是否释放空间*/
                    if (!nofree) { 
                        dictFreeKey(d, he);
                        dictFreeVal(d, he);
                        zfree(he);
                    }
                    d->ht[table].used--;
                    return he;
                }
                prevHe = he;
                he = he->next;
            }
            if (!dictIsRehashing(d)) break;
        }
        return NULL; /* not found */
    }