关于c:Redis源码解读字典

2次阅读

共计 15479 个字符，预计需要花费 39 分钟才能阅读完成。

[toc]

dictEntry 的构造如下(Redis 7.0)：

typedef struct dictEntry {
    void *key; // 键
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v; // 值
    struct dictEntry *next;     /* Next entry in the same hash bucket. 即下一个节点 */
    void *metadata[];           /* An arbitrary number of bytes (starting at a
                                 * pointer-aligned address) of size as returned
                                 * by dictType's dictEntryMetadataBytes(). */} dictEntry;

能够比照《Redis 设计与实现》中的 dictEntry 构造，发现联合结构 v 中多了一个 double 的浮点数示意，metadata 是一块任意长度的数据，具体的长度由 dictType 中的 dictEntryMetadataBytes() 返回，作用相当于 privdata

dictType 是一系列操作字典的键和值的操作：

typedef struct dictType {uint64_t (*hashFunction)(const void *key); // 哈希函数
    void *(*keyDup)(dict *d, const void *key); // 复制键的函数
    void *(*valDup)(dict *d, const void *obj); // 复制值的函数
    int (*keyCompare)(dict *d, const void *key1, const void *key2); // 键的比拟
    void (*keyDestructor)(dict *d, void *key); // 键的销毁
    void (*valDestructor)(dict *d, void *obj); // 值的销毁
    int (*expandAllowed)(size_t moreMem, double usedRatio); // 字典里的哈希表是否容许扩容
    /* Allow a dictEntry to carry extra caller-defined metadata.  The
     * extra memory is initialized to 0 when a dictEntry is allocated. */
    /* 容许调用者向条目 (dictEntry) 中增加额定的元信息.
     * 这段额定信息的内存会在条目调配时被零初始化. */
    size_t (*dictEntryMetadataBytes)(dict *d);
} dictType;

该构造是为了实现字典的多态。

7.0 版本的字典构造如下：

struct dict {
    dictType *type;

    dictEntry **ht_table[2];
    unsigned long ht_used[2];

    long rehashidx; /* rehashing not in progress if rehashidx == -1 */

    /* Keep small vars at end for optimal (minimal) struct padding */
    int16_t pauserehash; /* If >0 rehashing is paused (<0 indicates coding error) */
    signed char ht_size_exp[2]; /* exponent of size. (size = 1<<exp) */
};

相比于《Redis 设计与实现》中的字典实现，改变较大，7.0 中去掉了 dictht 构造，即去掉了哈希构造。接下来介绍每个成员：

/*     type 下面曾经解释过了;
*    ht_table 即哈希表数组
*    ht_used 别离示意哈希表数组中各自曾经寄存键值对的个数
*    rehashidx 是 rehash 时用的，没有 rehash 时值为 1
*    pauserehash 则是示意 rehash 的状态，大于 0 时示意 rehash 暂停了，小于 0 示意出错了
*    ht_size_exp 则是示意两个哈希表数组的大小，通过 1 << ht_size_exp[0/1] 来计算
*/

咱们能够看到一行正文：/* Keep small vars at end for optimal (minimal) struct padding */，将小变量放在构造体的前面，为了最佳或最小的填充，即节俭空间。

dictIterator 是字典的迭代器

/* If safe is set to 1 this is a safe iterator, that means, you can call
 * dictAdd, dictFind, and other functions against the dictionary even while
 * iterating. Otherwise it is a non safe iterator, and only dictNext()
 * should be called while iterating. */
typedef struct dictIterator {
    dict *d;
    long index;
    int table, safe;
    dictEntry *entry, *nextEntry;
    /* unsafe iterator fingerprint for misuse detection. */
    unsigned long long fingerprint;
} dictIterator;

解释其成员：

/*    d 指向以后迭代的字典
*    index 示意指向的键值对索引
*    table 是哈希表的号码，ht[0]/ht[1]
*    safe 示意该迭代器是否平安。平安时能够掉用 dictAdd,dictFind 等等其余函数，不平安时只能调用 dictNext
*    entry 指向迭代器所指的键值对，nextEntry 指向下一个键值对
*    fingerprint 指纹, 用于查看不平安迭代器的误用
*/

首先是对于哈希表初始化的两个常量：

/* This is the initial size of every hash table */
#define DICT_HT_INITIAL_EXP      2
#define DICT_HT_INITIAL_SIZE     (1<<(DICT_HT_INITIAL_EXP))

很显著，哈希表的初始大小为 4

`dictFreeVal`

开释 val

#define dictFreeVal(d, entry) \
    if ((d)->type->valDestructor) \
        (d)->type->valDestructor((d), (entry)->v.val)

调用 dictType 中提供的 valDestructor 函数开释 val

`dictSetVal`

设置 val 的值

#define dictSetVal(d, entry, _val_) do { \
    if ((d)->type->valDup) \
        (entry)->v.val = (d)->type->valDup((d), _val_); \
    else \
        (entry)->v.val = (_val_); \
} while(0)

如果 dictType 提供了设置 val 值的办法则调用，没有则间接赋值

`dictSetSignedIntegerVal`

设置有符号的整型 val 值

#define dictSetSignedIntegerVal(entry, _val_) \
    do {(entry)->v.s64 = _val_; } while(0)

当然还有设置无符号的整型值、double 值

`dictFreeKey`

开释 key

#define dictFreeKey(d, entry) \
    if ((d)->type->keyDestructor) \
        (d)->type->keyDestructor((d), (entry)->key)

`dictSetKey`

设置 key 的值

#define dictSetKey(d, entry, _key_) do { \
    if ((d)->type->keyDup) \
        (entry)->key = (d)->type->keyDup((d), _key_); \
    else \
        (entry)->key = (_key_); \
} while(0)

`dictCompareKeys`

key 的比拟

#define dictCompareKeys(d, key1, key2) \
    (((d)->type->keyCompare) ? \
        (d)->type->keyCompare((d), key1, key2) : \
        (key1) == (key2))

如果 dictType 中的 keyCompare 指针不为空，则调用它进行比拟，否则间接用 == 比拟

`dictMetadata`

获取用户提供的元数据

#define dictMetadata(entry) (&(entry)->metadata)

`dictMetadataSize`

获取用户提供的元数据的长度

#define dictMetadataSize(d) ((d)->type->dictEntryMetadataBytes \
                             ? (d)->type->dictEntryMetadataBytes(d) : 0)

#define dictHashKey(d, key) (d)->type->hashFunction(key) // 获取 key 的哈希值
#define dictGetKey(he) ((he)->key)
#define dictGetVal(he) ((he)->v.val)
#define dictGetSignedIntegerVal(he) ((he)->v.s64)
#define dictGetUnsignedIntegerVal(he) ((he)->v.u64)
#define dictGetDoubleVal(he) ((he)->v.d)

// 获取哈希表的大小
#define DICTHT_SIZE(exp) ((exp) == -1 ? 0 : (unsigned long)1<<(exp))
// 哈希表的掩码(size - 1)
#define DICTHT_SIZE_MASK(exp) ((exp) == -1 ? 0 : (DICTHT_SIZE(exp))-1)

`dictSlots`

// 获取字典的总大小
#define dictSlots(d) (DICTHT_SIZE((d)->ht_size_exp[0])+DICTHT_SIZE((d)->ht_size_exp[1]))

`dictSize`

// 获取字典保留键值对的总数
#define dictSize(d) ((d)->ht_used[0]+(d)->ht_used[1])

// 判断以后是否在 rehash
#define dictIsRehashing(d) ((d)->rehashidx != -1)
// 暂停 rehash
#define dictPauseRehashing(d) (d)->pauserehash++
// 复原 rehash
#define dictResumeRehashing(d) (d)->pauserehash--

创立字典的接口是 dictCreate

dictCreate 为字典构造调配空间，并调用 _dictInit 进行初始化

在 _dictinit 中，又调用了 _dicrReset 进行成员设置

/* Create a new hash table */
dict *dictCreate(dictType *type)
{dict *d = zmalloc(sizeof(*d));

    _dictInit(d,type);
    return d;
}

/* Initialize the hash table */
int _dictInit(dict *d, dictType *type)
{_dictReset(d, 0);
    _dictReset(d, 1);
    d->type = type;
    d->rehashidx = -1;
    d->pauserehash = 0;
    return DICT_OK;
}

/* Reset hash table parameters already initialized with _dictInit()*/
static void _dictReset(dict *d, int htidx)
{d->ht_table[htidx] = NULL;
    d->ht_size_exp[htidx] = -1;
    d->ht_used[htidx] = 0;
}

在 _dictInit 中有一个宏 DICT_OK，它的定义为：

#define DICT_OK 0
#define DICT_ERR 1

用来标识操作是否胜利实现

个别批改字典都是为 rehash 做筹备，或者扩充容量或者放大容量。

放大字典大小，前提是以后没有在进行 rehash 以及 dict_can_resize 变量不为 0

dict_can_resize 是 dict.c 中定义的一个全局变量，用来批示 resize 是否进行

static int dict_can_resize = 1;

什么时候 dict_can_resize 会为 0 呢？

当 redis 在后盾进行长久化时，为了最大化地利用零碎的 copy on write 机制，会临时地将 dict_can_resize 设置为 0，防止执行 天然 rehash，从而缩小程序对内存的碰撞。长久化工作实现后，dict_can_resize 又会设置为 1

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

    if (!dict_can_resize || dictIsRehashing(d)) return DICT_ERR;
    minimal = d->ht_used[0];
    if (minimal < DICT_HT_INITIAL_SIZE)
        minimal = DICT_HT_INITIAL_SIZE;
    return dictExpand(d, minimal);
}

放大哈希表的大小，新的容量刚好能包容已有元素。minimal 等于已有元素的数量，而后在 _dictExpand 中，会将新容量的大小设置为刚好大于等于 minimal 的 2 的幂。

再来看 dictExpand，调用 _dictExpand 进行理论的扩容。

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

/* 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. */
int _dictExpand(dict *d, unsigned long size, int* malloc_failed)
{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->ht_used[0] > size)
        return DICT_ERR;

    /* the new hash table */
    dictEntry **new_ht_table;
    unsigned long new_ht_used;
    signed char new_ht_size_exp = _dictNextExp(size);

    /* Detect overflows */
    size_t newsize = 1ul<<new_ht_size_exp;
    if (newsize < size || newsize * sizeof(dictEntry*) < newsize)
        return DICT_ERR;

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

    /* Allocate the new hash table and initialize all pointers to NULL */
    if (malloc_failed) {new_ht_table = ztrycalloc(newsize*sizeof(dictEntry*));
        *malloc_failed = new_ht_table == NULL;
        if (*malloc_failed)
            return DICT_ERR;
    } else
        new_ht_table = zcalloc(newsize*sizeof(dictEntry*));

    new_ht_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_table[0] == NULL) {d->ht_size_exp[0] = new_ht_size_exp;
        d->ht_used[0] = new_ht_used;
        d->ht_table[0] = new_ht_table;
        return DICT_OK;
    }

    /* Prepare a second hash table for incremental rehashing */
    d->ht_size_exp[1] = new_ht_size_exp;
    d->ht_used[1] = new_ht_used;
    d->ht_table[1] = new_ht_table;
    d->rehashidx = 0;
    return DICT_OK;
}

_dictExpand 函数不是只为了 rehash，还能够初始化字典。_dictExpand 函数判断是否是 rehash 是通过判断 ht_table[0] 是否为空来判断的。也就是说如果调用 _dictExpand 的字典是非空的，则增容后的哈希表是放在 ht_table[1] 中的，所以须要调用者手动开释 ht_table[0]，将 ht_table[1] 放到 ht_table[0] 地位上。

rehash 扩容分为两种：

天然 rehash：used / size >= 1 时且 dict_can_resize 为 1
强制 rehash：used / size > dict_force_resize_ratio 该版本中 dict_force_resize_ratio 的值为 5

另外，当哈希表的负载因子小于 0.1 时，程序主动开始对哈希表执行膨胀操作。

Rehash 过程：创立一个新的哈希表 ht[1]，rehashidx 变成 0，依据 rehashidx 指向的桶进行数据的迁徙。当所有数据迁徙结束时，开释 ht[0]，将 ht[1] 迁徙到 ht[0]，ht[1] 置为空。

上面是 Rehash 的一个简略示例：

Rehash 之前：

Rehash 开始：

所有元素从新映射到 ht_table[1]：

表的转移，实现 Rehash：

Rehash 不是一步就实现的，否则数据量特地大时，迁徙数据会是一个很大的工程，可能会导致服务器暂停服务来迁徙数据，Rehash 是渐进式的，数据的迁徙产生在对数据的增删改查时，这样就将迁徙平摊在每个增删改查的操作上。

如果在 rehash 期间要执行增加键的操作，都是在 ht[1] 中进行的，而进行删改查等操作，会同时在两张表中进行。

每次 rehash 都是以 n 个桶为单位的，将每个桶上的链都移到新的哈希表上。一次 rehash 实现当前，如果之后还有桶要 rehash，则返回 1，如果 rehash 实现，则返回 0。然而实际上，rehashidx 指向的桶可能是空桶，所以为了效率，一次 rehash 最多要遍历 10n 个空桶，遍历完了 10 n 个空桶就会返回。

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_used[0] != 0) {
        dictEntry *de, *nextde;

        /* Note that rehashidx can't overflow as we are sure there are more
         * elements because ht[0].used != 0 */
        assert(DICTHT_SIZE(d->ht_size_exp[0]) > (unsigned long)d->rehashidx);
        while(d->ht_table[0][d->rehashidx] == NULL) {
            d->rehashidx++;
            if (--empty_visits == 0) return 1;
        }
        de = d->ht_table[0][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) & DICTHT_SIZE_MASK(d->ht_size_exp[1]);
            de->next = d->ht_table[1][h];
            d->ht_table[1][h] = de;
            d->ht_used[0]--;
            d->ht_used[1]++;
            de = nextde;
        }
        d->ht_table[0][d->rehashidx] = NULL;
        d->rehashidx++;
    }

    /* Check if we already rehashed the whole table... */
    if (d->ht_used[0] == 0) {zfree(d->ht_table[0]);
        /* Copy the new ht onto the old one */
        d->ht_table[0] = d->ht_table[1];
        d->ht_used[0] = d->ht_used[1];
        d->ht_size_exp[0] = d->ht_size_exp[1];
        _dictReset(d, 1);
        d->rehashidx = -1;
        return 0;
    }

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

销毁字典的接口是 dictRelease

dictRelease 调用_dictClear 来开释两个哈希表，并最初开释字典空间

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

    /* Free all the elements */
    for (i = 0; i < DICTHT_SIZE(d->ht_size_exp[htidx]) && d->ht_used[htidx] > 0; i++) {
        dictEntry *he, *nextHe;

        if (callback && (i & 65535) == 0) callback(d);

        if ((he = d->ht_table[htidx][i]) == NULL) continue;
        while(he) {
            nextHe = he->next;
            dictFreeKey(d, he);
            dictFreeVal(d, he);
            zfree(he);
            d->ht_used[htidx]--;
            he = nextHe;
        }
    }
    /* Free the table and the allocated cache structure */
    zfree(d->ht_table[htidx]);
    /* Re-initialize the table */
    _dictReset(d, htidx);
    return DICT_OK; /* never fails */
}

/* Clear & Release the hash table */
void dictRelease(dict *d)
{_dictClear(d,0,NULL);
    _dictClear(d,1,NULL);
    zfree(d);
}

_dictClear 的第三个参数是一个函数指针，但 dictRelease 在这里都传了空指针，所以暂且不论。_dictClear 遍历所有的索引，当该索引上有键值对时，则开释该索引上的整条链表。开释完所有键值对之后，再开释该哈希表并重置其成员。

`dictAdd`

增加一个键值对到指定哈希表中

/* 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;
}

该函数调用了 dictAddRaw 函数，上面是 dictAddRaw 函数的定义：

/* 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.
 */

dictEntry *dictAddRaw(dict *d, void *key, dictEntry **existing)
{
    long index;
    dictEntry *entry;
    int htidx;

    if (dictIsRehashing(d)) _dictRehashStep(d);

    /* 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;

    /* 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. */
    htidx = dictIsRehashing(d) ? 1 : 0;
    size_t metasize = dictMetadataSize(d);
    entry = zmalloc(sizeof(*entry) + metasize);
    if (metasize > 0) {memset(dictMetadata(entry), 0, metasize);
    }
    entry->next = d->ht_table[htidx][index];
    d->ht_table[htidx][index] = entry;
    d->ht_used[htidx]++;

    /* Set the hash entry fields. */
    dictSetKey(d, entry, key);
    return entry;
}

该函数下面有一串正文，意思是：该函数增加一个 dictEntry 到哈希表中，但并不会设置值，将该构造返回给用户，将值的设置交给用户。这个函数也间接裸露给要调用的用户 API，次要是为了在哈希值外部存储非指针。

返回值：如果键曾经存在，则返回 NULL，并填充“*existing”如果 existing 不为 NULL，则应用现有条目。如果胜利增加了键，则返回哈希条目 (dictEntry) 以供调用者操作

咱们剖析函数的一个实现细节：能够看到函数首先会判断以后的哈希表是否在 rehash，如果在 rehash，则进行一次只迁徙一个桶的 rehash。_dictRehashStep 是实现一次只迁徙一个桶的 rehash。

所以当初咱们就晓得。dictAdd 调用 dictAddRaw，获取一个已插入的 dictEntry，而后实现值的设置。

在该函数中还调用了 _dictKeyIndex 函数，该函数实现如下：

函数返回 key 在哈希表中的索引，如果哈希表中存在该 key，则返回 -1，可选的输入参数 existing 会被填充成对应的 dictEntry。

须要留神的是，如果以后哈希表正在 rehash，则返回的索引始终是第二张哈希表的索引。

static long _dictKeyIndex(dict *d, const void *key, uint64_t hash, dictEntry **existing)
{
    unsigned long idx, table;
    dictEntry *he;
    if (existing) *existing = NULL;

    /* Expand the hash table if needed */
    if (_dictExpandIfNeeded(d) == DICT_ERR)
        return -1;
    for (table = 0; table <= 1; table++) {idx = hash & DICTHT_SIZE_MASK(d->ht_size_exp[table]);
        /* 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)) {if (existing) *existing = he;
                return -1;
            }
            he = he->next;
        }
        if (!dictIsRehashing(d)) break;
    }
    return idx;
}

`dictReplace`

如果 key 不存在，则增加 key，并设置 value，函数返回 1。如果 key 曾经存在，则更新 value 值，函数返回 0

int dictReplace(dict *d, void *key, void *val)
{
    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);
        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);
    dictFreeVal(d, &auxentry);
    return 0;
}

首先调用 dictAddRaw 函数，依据返回值判断 key 是否曾经在哈希表中，如果不存在，则 entry 不为空，设置 val 值并返回 1。如果 entry 为空，则进行值的更新。但要遵循先设置新值再开释旧值的程序。因为新值和旧值可能雷同，这种状况就须要思考援用计数，咱们应该先减少计数，再缩小计数。

`dictAddOrFind`

该函数总是返回一个指定 key 的 dictEntry。如果 key 曾经存在，则将其 dictEntry 返回；如果不存在，则将其增加并返回。

dictEntry *dictAddOrFind(dict *d, void *key) {
    dictEntry *entry, *existing;
    entry = dictAddRaw(d,key,&existing);
    return entry ? entry : existing;
}

`dictDelete`

删除元素

/* 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;
}

dictDelete 通过 dictGenericDelete 来删除哈希表中的元素。

如果没找到要删除的元素则返回 NULL，找到了则返回曾经开释的 dictEntry。

/* Search and remove an element. This is a 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;

    /* dict is empty */
    if (dictSize(d) == 0) return NULL;

    if (dictIsRehashing(d)) _dictRehashStep(d);
    h = dictHashKey(d, key);

    for (table = 0; table <= 1; table++) {idx = h & DICTHT_SIZE_MASK(d->ht_size_exp[table]);
        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;
                if (!nofree) {dictFreeUnlinkedEntry(d, he);
                }
                d->ht_used[table]--;
                return he;
            }
            prevHe = he;
            he = he->next;
        }
        if (!dictIsRehashing(d)) break;
    }
    return NULL; /* not found */
}

`dictUnlink` 与 `dictFreeUnlinkedEntry`

dictUnlink 函数是从哈希表中删除 key，但 key，value 和 dictEntry 并没有被开释，须要调用 dictFreeUnlinkedEntry 函数来开释这些资源。如果 key 在哈希表中找到了，则返回对应的 dictEntry，如果没找到则返回 NULL

dictEntry *dictUnlink(dict *d, const void *key) {return dictGenericDelete(d,key,1);
}

/* 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);
}

`dictFind`

查找 key，找到了返回其 dictEntry；否则返回 NULL

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

    if (dictSize(d) == 0) return NULL; /* dict is empty */
    if (dictIsRehashing(d)) _dictRehashStep(d);
    h = dictHashKey(d, key);
    for (table = 0; table <= 1; table++) {idx = h & DICTHT_SIZE_MASK(d->ht_size_exp[table]);
        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;
}

正文完

c

发表至： c#

2022-05-16

0

关于c++:ACM博弈论SG函数入门1从巴什博奕到尼姆游戏

关于c++:C面试八股文C中指针引用解引用和取地址有什么不同

关于c++:C内存管理

阿里短信回持net-sdk的bug导致生产服务cpu-100排查

关于git:git-commit-规范

关于c:Redis源码解读字典

四个数据结构

dictEntry

dictType

dict

dictIterator

常量与一系列宏

`dictFreeVal`

`dictSetVal`

`dictSetSignedIntegerVal`

`dictFreeKey`

`dictSetKey`

`dictCompareKeys`

`dictMetadata`

`dictMetadataSize`

获取 key 和 val 的宏

对于哈希表大小的宏

`dictSlots`

`dictSize`

对于 rehash 的宏

创立 / 销毁 / 批改字典

创立字典

批改字典

dictResize

dictExpand

Rehash

销毁字典

键的操作

`dictAdd`

`dictReplace`

`dictAddOrFind`

`dictDelete`

`dictUnlink` 与 `dictFreeUnlinkedEntry`

`dictFind`

站内搜索

关于c:Redis源码解读字典

四个数据结构

dictEntry

dictType

dict

dictIterator

常量与一系列宏

dictFreeVal

dictSetVal

dictSetSignedIntegerVal

dictFreeKey

dictSetKey

dictCompareKeys

dictMetadata

dictMetadataSize

获取 key 和 val 的宏

对于哈希表大小的宏

dictSlots

dictSize

对于 rehash 的宏

创立 / 销毁 / 批改字典

创立字典

批改字典

dictResize

dictExpand

Rehash

销毁字典

键的操作

dictAdd

dictReplace

dictAddOrFind

dictDelete

dictUnlink 与 dictFreeUnlinkedEntry

dictFind

站内搜索

`dictFreeVal`

`dictSetVal`

`dictSetSignedIntegerVal`

`dictFreeKey`

`dictSetKey`

`dictCompareKeys`

`dictMetadata`

`dictMetadataSize`

`dictSlots`

`dictSize`

`dictAdd`

`dictReplace`

`dictAddOrFind`

`dictDelete`

`dictUnlink` 与 `dictFreeUnlinkedEntry`

`dictFind`