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

你的名字 2022-04-14 06:51 164阅读 0赞

### 1. 简介 ###

本文继上文的基础上，分析剩余的字典相关函数源码。

### 2. 源码分析 ###

/* 查找并删除 * 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 */
    }
    
    /* 调用dictGenericDelete()函数完成删除key的功能 * Remove an element, returning DICT_OK on success or DICT_ERR if the * element was not found. */
    int dictDelete(dict *ht, const void *key) { 
        return dictGenericDelete(ht, key, 0) ? DICT_OK : DICT_ERR;
    }
    
    /* 调用dictGenericDelete()函数完成删除key的功能 * 从表中删除key，但是没有释放（第三项赋值1而不是0） * 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. */
    dictEntry *dictUnlink(dict *ht, const void *key) { 
        return dictGenericDelete(ht, key, 1);
    }
    
    /* 为dicUnlink()服务，释放key * 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. */
    void dictFreeUnlinkedEntry(dict *d, dictEntry *he) { 
        if (he == NULL) return;
        dictFreeKey(d, he);
        dictFreeVal(d, he);
        zfree(he);
    }
    
    /* 完全清除字典d的哈希表ht * Destroy an entire dictionary */
    int _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;
    
    		//i等于0并且回调函数传参不为空则回调callback
            if (callback && (i & 65535) == 0) callback(d->privdata);
    
            if ((he = ht->table[i]) == NULL) continue;
            while(he) { 
                nextHe = he->next;
                dictFreeKey(d, he);
                dictFreeVal(d, he);
                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_OK; /* never fails */
    }
    
    /* 清除两张表，完成释放 * Clear & Release the hash table */
    void dictRelease(dict *d)
    { 
        _dictClear(d, &d->ht[0], NULL);
        _dictClear(d, &d->ht[1], NULL);
        zfree(d);
    }
    
    /*根据key查找*/
    dictEntry *dictFind(dict *d, const void *key)
    { 
        dictEntry *he;
        uint64_t h, idx, table;
    
    	/* 空表 dict is empty */
        if (d->ht[0].used + 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];
            while(he) { 
                if (key==he->key || dictCompareKeys(d, key, he->key))
                    return he;
                he = he->next;
            }
            if (!dictIsRehashing(d)) return NULL;
        }
        return NULL;
    }
    
    void *dictFetchValue(dict *d, const void *key) { 
        dictEntry *he;
    
        he = dictFind(d,key);
        return he ? dictGetVal(he) : NULL;
    }
    
    /* 64位特征指纹码：类似于线程锁，用于保证迭代器安全 * 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. */
    long long dictFingerprint(dict *d) 
    { 
        long long integers[6], hash = 0;
        int j;
    
    	/* 将dict结构体中的几个状态放入到数组中，以便后面应用到64 bit MixFunctions中。 * dict结构体其实就是一个hash表的实现，而这些状态其实就是第一、第二哈希表的表地址、表大小与 * 已用条目的数量 */
        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;
    
        /* * 利用64 bit Mix Functions，将这些状态信息混合到hash中，组成最后的指纹，如果这些状态中有一个 * 出现变化，可以通过一个算法逆推出该状态变化之前的值。例如，d->ht[0].size发生变化，则我们可 * 以通过hash和其他的几个状态，逆推出d->ht[0].size的最初值。 * 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;
    }
    
    /*创建并返回dict的迭代器*/
    dictIterator *dictGetIterator(dict *d)
    { 
        dictIterator *iter = zmalloc(sizeof(*iter));
    
        iter->d = d;
        iter->table = 0;
        iter->index = -1;
        iter->safe = 0;
        iter->entry = NULL;
        iter->nextEntry = NULL;
        return iter;
    }
    
    /*调用dictGetIterator()函数创建安全迭代器*/
    dictIterator *dictGetSafeIterator(dict *d) 
    { 
        dictIterator *i = dictGetIterator(d);
    
        i->safe = 1;
        return i;
    }
    
    /* 根据迭代器获取下一个表项 */
    dictEntry *dictNext(dictIterator *iter)
    { 
        while (1) { 
            if (iter->entry == NULL) { 
                dictht *ht = &iter->d->ht[iter->table];
                if (iter->index == -1 && iter->table == 0) { 
                    if (iter->safe)
                        iter->d->iterators++;
                    else
                        iter->fingerprint = dictFingerprint(iter->d);
                }
                iter->index++;
                if (iter->index >= (long) ht->size) { 
                    if (dictIsRehashing(iter->d) && 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 dictReleaseIterator(dictIterator *iter)
    { 
        if (!(iter->index == -1 && iter->table == 0)) { 
            if (iter->safe)
                iter->d->iterators--;
            else
                assert(iter->fingerprint == dictFingerprint(iter->d));
        }
        zfree(iter);
    }
    
    /* 随机返回哈希表中的一项，用于随机算法 * Return a random entry from the hash table. Useful to * implement randomized algorithms */
    dictEntry *dictGetRandomKey(dict *d)
    { 
        dictEntry *he, *orighe;
        unsigned long h;
        int listlen, listele;
    
        if (dictSize(d) == 0) return NULL;
        if (dictIsRehashing(d)) _dictRehashStep(d);
        if (dictIsRehashing(d)) { 
            do { 
                /* We are sure there are no elements in indexes from 0 * to rehashidx-1 */
                h = d->rehashidx + (random() % (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);
        } else { 
            do { 
                h = random() & d->ht[0].sizemask;
                he = d->ht[0].table[h];
            } while(he == 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) { 
            he = he->next;
            listlen++;
        }
        listele = random() % listlen;
        he = orighe;
        while(listele--) he = he->next;
        return he;
    }
    
    /* 随机获取多个key * 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. */
    unsigned 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) < count) count = dictSize(d);
        maxsteps = count * 10;
    
        /* Try to do a rehashing work proportional to 'count'. */
        for (j = 0; j < count; j++) { 
            if (dictIsRehashing(d))
                _dictRehashStep(d);
            else
                break;
        }
    
        tables = dictIsRehashing(d) ? 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 = random() & 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;
                    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) { 
                    emptylen++;
                    if (emptylen >= 5 && emptylen > count) { 
                        i = random() & 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;
    }