Redis教程
redis源码阅读-数据结构篇-字典dict
本文主要是介绍redis源码阅读-数据结构篇-字典dict，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！
@
目录- 4. 字典实现 dict.h 和 dict.c
- 数据结构定义
- 部分宏定义
- 哈希函数（本部分可选跳过）
- Helper函数（可跳过，需要时阅读）
- dict 构造函数 O(1)
- dict 析构函数 O(N)
- hashtable 构造函数 O(1)
- dict resize O(1)
- rehash O(m)
- 限时rehash
- set k O(1)
- set kv O(1)
- get k O(1)
- update k O(1)
- update kv O(1)
- delete kv O(1)
- get iter O(1)
- delete iter O(1)
- 迭代 O(1)
- dict 随机key O(1)
- dict scan O(1)
4. 字典实现 dict.h 和 dict.c
数据结构定义
-
状态码
#define DICT_OK 0 // 操作成功 #define DICT_ERR 1 // 操作失败（或出错）
-
哈希表kv节点
typedef struct dictEntry { void *key; // 键 union { void *val; uint64_t u64; int64_t s64; } v; // 值 struct dictEntry *next; // 指向下个哈希表节点，形成链表 } dictEntry; -
哈希表
typedef struct dictht { dictEntry **table; // 哈希表数组 unsigned long size; // 哈希表大小 unsigned long sizemask; // 哈希表大小掩码，用于计算索引值，总是等于 size - 1 unsigned long used; // 该哈希表已有节点的数量 } dictht; -
kv操作函数
typedef struct dictType { unsigned int (*hashFunction)(const void *key); // 计算哈希值的函数 void *(*keyDup)(void *privdata, const void *key);// 复制键的函数 void *(*valDup)(void *privdata, const void *obj);// 复制值的函数 int (*keyCompare)(void *privdata, const void *key1, const void *key2);// 对比键的函数 void (*keyDestructor)(void *privdata, void *key); // 销毁键的函数 void (*valDestructor)(void *privdata, void *obj); // 销毁值的函数 } dictType; -
dict主角
typedef struct dict { dictType *type; // 类型特定函数 void *privdata; // 私有数据 dictht ht[2]; // 哈希表, 存在一个时占第一个，存在两个时正在rehash int rehashidx; // rehash 索引, 当 rehash 不在进行时，值为 -1 int iterators; // 目前正在运行的安全迭代器的数量 } dict; -
dict 迭代器
typedef struct dictIterator { dict *d; // 被迭代的字典 // table ：正在被迭代的哈希表号码，值可以是 0 或 1 。 // index ：迭代器当前所指向的哈希表索引位置。 // safe ：标识这个迭代器是否安全 int table, index, safe; // entry ：当前迭代到的节点的指针 // nextEntry ：当前迭代节点的下一个节点 // 因为在安全迭代器运作时， entry 所指向的节点可能会被修改， // 所以需要一个额外的指针来保存下一节点的位置， // 从而防止指针丢失 dictEntry *entry, *nextEntry; long long fingerprint; /* unsafe iterator fingerprint for misuse detection */ } dictIterator;
部分宏定义
#define DICT_HT_INITIAL_SIZE 4 // 哈希表初始大小
// 释放给定字典节点的值
#define dictFreeVal(d, entry) \
if ((d)->type->valDestructor) \
(d)->type->valDestructor((d)->privdata, (entry)->v.val)
// 设置给定字典节点的值
#define dictSetVal(d, entry, _val_) do { \
if ((d)->type->valDup) \
entry->v.val = (d)->type->valDup((d)->privdata, _val_); \
else \
entry->v.val = (_val_); \
} while(0)
...
// 比对两个键
#define dictCompareKeys(d, key1, key2) \
(((d)->type->keyCompare) ? \
(d)->type->keyCompare((d)->privdata, key1, key2) : \
(key1) == (key2))
#define dictHashKey(d, key) (d)->type->hashFunction(key) // 计算给定键的哈希值
#define dictGetKey(he) ((he)->key) // 返回获取给定节点的键
...
哈希函数（本部分可选跳过）
-
Thomas Wang's 32 bit Mix Function
unsigned int dictIntHashFunction(unsigned int key) { key += ~(key << 15); key ^= (key >> 10); key += (key << 3); key ^= (key >> 6); key += ~(key << 11); key ^= (key >> 16); return key; } -
Identity hash function for integer keys
unsigned int dictIdentityHashFunction(unsigned int key) { return key; } -
MurmurHash2, by Austin Appleby
unsigned int dictGenHashFunction(const void *key, int len) { /* 'm' and 'r' are mixing constants generated offline. They're not really 'magic', they just happen to work well. */ uint32_t seed = dict_hash_function_seed; const uint32_t m = 0x5bd1e995; const int r = 24; /* Initialize the hash to a 'random' value */ uint32_t h = seed ^ len; /* Mix 4 bytes at a time into the hash */ const unsigned char *data = (const unsigned char *)key; while(len >= 4) { uint32_t k = *(uint32_t*)data; k *= m; k ^= k >> r; k *= m; h *= m; h ^= k; data += 4; len -= 4; } /* Handle the last few bytes of the input array */ switch(len) { case 3: h ^= data[2] << 16; case 2: h ^= data[1] << 8; case 1: h ^= data[0]; h *= m; }; /* Do a few final mixes of the hash to ensure the last few * bytes are well-incorporated. */ h ^= h >> 13; h *= m; h ^= h >> 15; return (unsigned int)h; } -
a case insensitive hash function (based on djb hash)
unsigned int dictGenCaseHashFunction(const unsigned char *buf, int len) { unsigned int hash = (unsigned int)dict_hash_function_seed; while (len--) hash = ((hash << 5) + hash) + (tolower(*buf++)); /* hash * 33 + c */ return hash; }
关于hash函数，留坑待填，有时间会整理常见hash函数
Helper函数（可跳过，需要时阅读）
-
时间函数 O(1)
long long timeInMilliseconds(void) { struct timeval tv; gettimeofday(&tv,NULL); return (((long long)tv.tv_sec)*1000)+(tv.tv_usec/1000); } -
Fingerprint函数 O(1)
long long dictFingerprint(dict *d) { long long integers[6], hash = 0; int j; 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; for (j = 0; j < 6; j++) { hash += integers[j]; hash = (~hash) + (hash << 21); hash = hash ^ (hash >> 24); hash = (hash + (hash << 3)) + (hash << 8); hash = hash ^ (hash >> 14); hash = (hash + (hash << 2)) + (hash << 4); hash = hash ^ (hash >> 28); hash = hash + (hash << 31); } return hash; } -
重置/初始化 hashtable，不涉及内存 O(1)
static void _dictReset(dictht *ht) { ht->table = NULL; ht->size = 0; ht->sizemask = 0; ht->used = 0; } -
重置/初始化dict，不涉及内存 O(1)
int _dictInit(dict *d, dictType *type, void *privDataPtr) { _dictReset(&d->ht[0]); // 初始化两个哈希表的各项属性值 _dictReset(&d->ht[1]); // 但暂时还不分配内存给哈希表数组 d->type = type; // 设置类型特定函数 d->privdata = privDataPtr; // 设置私有数据 d->rehashidx = -1; // 设置哈希表 rehash 状态 d->iterators = 0; // 设置字典的安全迭代器数量 return DICT_OK; } -
dict进行一步rehash O(1)
static void _dictRehashStep(dict *d) { if (d->iterators == 0) dictRehash(d,1); } -
遍历释放某个hashtable，用户自定义释放内存，并重置 O(n)
int _dictClear(dict *d, dictht *ht, void(callback)(void *)) { unsigned long i; for (i = 0; i < ht->size && ht->used > 0; i++) { // 遍历整个哈希表 T = O(N) dictEntry *he, *nextHe; if (callback && (i & 65535) == 0) callback(d->privdata); if ((he = ht->table[i]) == NULL) continue; // 跳过空索引 while(he) { // 遍历整个链表 T = O(1) nextHe = he->next; dictFreeKey(d, he); // 删除键 dictFreeVal(d, he); // 删除值 zfree(he); // 释放节点 ht->used--; // 更新已使用节点计数 he = nextHe; // 处理下个节点 } } zfree(ht->table); // 释放哈希表结构 _dictReset(ht); // 重置哈希表属性 return DICT_OK; /* never fails */ } -
尝试expand，符合条件调用expand函数 O(1) / O(n)
static int _dictExpandIfNeeded(dict *d) { // 渐进式 rehash 已经在进行了，直接返回 if (dictIsRehashing(d)) return DICT_OK; // 如果字典（的 0 号哈希表）为空，那么创建并返回初始化大小的 0 号哈希表 T = O(1) if (d->ht[0].size == 0) return dictExpand(d, DICT_HT_INITIAL_SIZE); // 一下两个条件同时为真时，对字典进行扩展 // 1）字典已使用节点数和字典大小之间的比率大于 1 // 2）dict_can_resize 为真 或者 已使用节点数和字典大小之间的比率超过 dict_force_resize_ratio if (d->ht[0].used >= d->ht[0].size && (dict_can_resize || d->ht[0].used/d->ht[0].size > dict_force_resize_ratio)) { // 新哈希表的大小至少是目前已使用节点数的两倍 T = O(N) return dictExpand(d, d->ht[0].used * 2); } return DICT_OK; } -
返回合适的hashtable size O(1)
static unsigned long _dictNextPower(unsigned long size) { unsigned long i = DICT_HT_INITIAL_SIZE; if (size >= LONG_MAX) return LONG_MAX; while(1) { if (i >= size) return i; i *= 2; } } -
返回合适的新key对应的index O(1)
static int _dictKeyIndex(dict *d, const void *key) { unsigned int h, idx, table; dictEntry *he; if (_dictExpandIfNeeded(d) == DICT_ERR) // rehash O(1) / O(N) return -1; h = dictHashKey(d, key); // 计算 key 的哈希值 for (table = 0; table <= 1; table++) { idx = h & d->ht[table].sizemask; // 计算索引值 he = d->ht[table].table[idx]; // 查找 key 是否存在 T = O(1) while(he) { if (dictCompareKeys(d, key, he->key)) return -1; // 存在返回 -1 he = he->next; } if (!dictIsRehashing(d)) break; // 如果这时 rehash 正在进行，那么继续对 1 号哈希表进行 rehash } return idx; // 返回索引值 } -
返回合适的hashtable size
static unsigned long _dictNextPower(unsigned long size) { unsigned long i = DICT_HT_INITIAL_SIZE; if (size >= LONG_MAX) return LONG_MAX; while(1) { if (i >= size) return i; i *= 2; } }
dict 构造函数 O(1)
dict *dictCreate(dictType *type, void *privDataPtr) {
dict *d = zmalloc(sizeof(*d));
_dictInit(d, type, privDataPtr); //不涉及 hashtable 内存
return d;
}
dict 析构函数 O(N)
void dictRelease(dict *d) {
// 删除并清空两个哈希表
_dictClear(d,&d->ht[0],NULL);
_dictClear(d,&d->ht[1],NULL);
// 释放节点结构
zfree(d);
}
void dictEmpty(dict *d, void(callback)(void*)) {
// 删除并清空两个哈希表
_dictClear(d,&d->ht[0],callback);
_dictClear(d,&d->ht[1],callback);
// 重置属性
d->rehashidx = -1;
d->iterators = 0;
}
hashtable 构造函数 O(1)
int dictExpand(dict *d, unsigned long size) {
dictht n; // 新哈希表
unsigned long realsize = _dictNextPower(size); // 根据 size 参数，计算哈希表的大小
// 不能在字典正在 rehash 时进行
// 新 size 的值也不能小于 0 号哈希表的当前已使用节点
if (dictIsRehashing(d) || d->ht[0].used > size)
return DICT_ERR;
n.size = realsize;
n.sizemask = realsize-1;
n.table = zcalloc(realsize*sizeof(dictEntry*));// 为哈希表分配空间，并将所有指针指向 NULL
n.used = 0;
if (d->ht[0].table == NULL) { // 如果 0 号哈希表为空，那么这是一次初始化：
d->ht[0] = n; //程序将新哈希表赋给 0 号哈希表的指针，然后字典就可以开始处理键值对了。
return DICT_OK;
}
// 否则这是一次 rehash ：
d->ht[1] = n; // 程序将新哈希表设置为 1 号哈希表，
d->rehashidx = 0; // 并将字典的 rehash 标识打开，让程序可以开始对字典进行 rehash
return DICT_OK;
// 此函数并没初始化kv 或者 rehash kv，因此 O(1)
}
dict resize O(1)
用于初始化hashtable 或者 rehash
int dictResize(dict *d) {
int minimal;
// 不能在关闭 rehash 或者正在 rehash 的时候调用
if (!dict_can_resize || dictIsRehashing(d)) return DICT_ERR;
// 计算让比率接近 1：1 所需要的最少节点数量
minimal = d->ht[0].used;
if (minimal < DICT_HT_INITIAL_SIZE)
minimal = DICT_HT_INITIAL_SIZE;
return dictExpand(d, minimal); // 调整字典的大小 O(1)
}
rehash O(m)
int dictRehash(dict *d, int n) {
if (!dictIsRehashing(d)) return 0; // 只可以在 rehash 进行中时执行
while(n--) { // 进行 N 步迁移，N 为函数参数，N 为槽的个数
dictEntry *de, *nextde;
if (d->ht[0].used == 0) { // 如果旧 0 号哈希表为空，那么表示 rehash 执行完毕
zfree(d->ht[0].table); // 释放旧 0 号哈希表
d->ht[0] = d->ht[1]; // 0 号哈希表 指向 rehash 完毕的 1 号哈希表
_dictReset(&d->ht[1]); // 重置 1 号哈希表
d->rehashidx = -1; // 关闭 rehash 标识
return 0; // 返回 0 ，向调用者表示 rehash 已经完成
}
// 略过数组中为空的索引，找到下一个非空索引
while(d->ht[0].table[d->rehashidx] == NULL) d->rehashidx++;
de = d->ht[0].table[d->rehashidx]; // 指向该索引的链表表头节点
while(de) {
// 将链表中的所有节点迁移到新哈希表 T = O(1)
unsigned int h;
nextde = de->next;
// 保存下个节点的指针
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++;
// 更新 rehash 索引
}
return 1;
}
限时rehash
int dictRehashMilliseconds(dict *d, int ms) {
long long start = timeInMilliseconds();// 记录开始时间
int rehashes = 0;
while(dictRehash(d,100)) {// 100 为步长
rehashes += 100;
if (timeInMilliseconds()-start > ms) break; // 如果时间已过，跳出
}
return rehashes; // 返回rehash数量
}
set k O(1)
dictEntry *dictAddRaw(dict *d, void *key) {
int index;
dictEntry *entry;
dictht *ht;
// 如果条件允许的话，进行单步 rehash T = O(1)
if (dictIsRehashing(d)) _dictRehashStep(d);
if ((index = _dictKeyIndex(d, key)) == -1) // 计算键在哈希表中的索引值，存在返回null
return NULL;
ht = dictIsRehashing(d) ? &d->ht[1] : &d->ht[0];// rehash 添加到 1 号哈希表，否则 0 号
entry = zmalloc(sizeof(*entry)); // 为新节点分配空间
entry->next = ht->table[index]; // 将新节点插入到链表表头
ht->table[index] = entry;
ht->used++; // 更新哈希表已使用节点数量
dictSetKey(d, entry, key); // 设置新节点的键
return entry;
}
set kv O(1)
int dictAdd(dict *d, void *key, void *val) {
dictEntry *entry = dictAddRaw(d,key); // 尝试添加键到字典，并返回包含了这个键的新哈希节点
if (!entry) return DICT_ERR; // 键已存在，添加失败
dictSetVal(d, entry, val); // 键不存在，设置节点的值
return DICT_OK;
}
get k O(1)
dictEntry *dictFind(dict *d, const void *key) {
dictEntry *he;
unsigned int h, idx, table;
if (d->ht[0].size == 0) return NULL; // 空
// 如果条件允许的话，进行单步 rehash
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]; // 遍历给定索引上的链表的所有节点，查找 key
while(he) {
if (dictCompareKeys(d, key, he->key))
return he;
he = he->next;
}
if (!dictIsRehashing(d)) return NULL; // 没找到， rehash时 继续查找 1 号哈希表
}
return NULL; // 进行到这里时，说明两个哈希表都没找到
}
void *dictFetchValue(dict *d, const void *key) {
dictEntry *he;
he = dictFind(d,key);
return he ? dictGetVal(he) : NULL;
}
update k O(1)
dictEntry *dictReplaceRaw(dict *d, void *key) {
dictEntry *entry = dictFind(d,key);
return entry ? entry : dictAddRaw(d,key); //存在直接返回节点，不存在新建节点
}
update kv O(1)
int dictReplace(dict *d, void *key, void *val) {
dictEntry *entry, auxentry;
// 尝试set
if (dictAdd(d, key, val) == DICT_OK)
return 1;
// key 已经存在
entry = dictFind(d, key);
auxentry = *entry; // 先保存原有的值的指针
dictSetVal(d, entry, val); // 然后设置新的值
dictFreeVal(d, &auxentry); // 然后释放旧值
return 0;
}
delete kv O(1)
static int dictGenericDelete(dict *d, const void *key, int nofree) {
unsigned int h, idx;
dictEntry *he, *prevHe;
int table;
if (d->ht[0].size == 0) return DICT_ERR; // 空
// 进行单步 rehash ，T = O(1)
if (dictIsRehashing(d)) _dictRehashStep(d);
h = dictHashKey(d, key); // 计算哈希值
for (table = 0; table <= 1; table++) { // 选择哈希表 T = O(1)
idx = h & d->ht[table].sizemask; // 计算索引值
he = d->ht[table].table[idx]; // 指向该索引上的链表
prevHe = NULL;
while(he) { // 遍历链表上的所有节点 T = O(1)
if (dictCompareKeys(d, key, he->key)) { // 超找目标节点
if (prevHe) // 从链表中删除
prevHe->next = he->next;
else
d->ht[table].table[idx] = he->next;
if (!nofree) { // 释放调用键和值的释放函数？
dictFreeKey(d, he);
dictFreeVal(d, he);
}
zfree(he); // 释放节点本身
d->ht[table].used--; // 更新已使用节点数量
return DICT_OK; // 返回已找到信号
}
prevHe = he;
he = he->next;
}
if (!dictIsRehashing(d)) break; // 没找到， rehash时 继续查找 1 号哈希表
}
return DICT_ERR; // 没找到
}
int dictDelete(dict *ht, const void *key) {
return dictGenericDelete(ht,key,0);
}
int dictDeleteNoFree(dict *ht, const void *key) {
return dictGenericDelete(ht,key,1);
}
get iter O(1)
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;
}
dictIterator *dictGetSafeIterator(dict *d) {
dictIterator *i = dictGetIterator(d);
i->safe = 1;
return i;
}
delete iter O(1)
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);
}
迭代 O(1)
dictEntry *dictNext(dictIterator *iter) {
while (1) {
// 指向下个候选节点，待下面查
if (iter->entry == NULL) { // 1) 第一次迭代 2) 链表迭代完成，寻找下个链表
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++; // 迭代时增加index
if (iter->index >= (signed) ht->size) { // 当索引大于大小时，迭代完毕
if (dictIsRehashing(iter->d) && iter->table == 0) {// 如果还有1号hashtable
iter->table++;
iter->index = 0;
ht = &iter->d->ht[1];
} else { // 迭代彻底完成
break;
}
}
iter->entry = ht->table[iter->index]; // 指向 index 的链表头，交给下面判断
} else {
iter->entry = iter->nextEntry; // 正在迭代某个链表，指向链表的下个节点
}
if (iter->entry) { // 如果不为空，记录链表下个节点，返回
iter->nextEntry = iter->entry->next;
return iter->entry;
}
}
return NULL; // 迭代完毕
}
dict 随机key O(1)
dictEntry *dictGetRandomKey(dict *d) {
dictEntry *he, *orighe;
unsigned int h;
int listlen, listele;
// 字典为空
if (dictSize(d) == 0) return NULL;
// 进行单步 rehash
if (dictIsRehashing(d)) _dictRehashStep(d);
if (dictIsRehashing(d)) {// rehash ，1 号 hashtable 也算在内
do {
h = random() % (d->ht[0].size+d->ht[1].size);
he = (h >= d->ht[0].size) ? d->ht[1].table[h - d->ht[0].size] :
d->ht[0].table[h];
} while(he == NULL);
} else { // 否则，只算 0 号 hashtable
do {
h = random() & d->ht[0].sizemask;
he = d->ht[0].table[h];
} while(he == NULL);
}
listlen = 0;// 从这个链表随机返回一个节点
orighe = he;
while(he) { // 链表长度
he = he->next;
listlen++;
}
listele = random() % listlen;// 链表内索引
he = orighe;
while(listele--) he = he->next; // 按索引查找节点
return he;// 返回随机节点
}
int dictGetRandomKeys(dict *d, dictEntry **des, int count) {
int j; // hashtable id
int stored = 0; // 返回数量
if (dictSize(d) < count) count = dictSize(d);// 不超过 dictsize
while(stored < count) {
for (j = 0; j < 2; j++) {// 0 1 顺序遍历
unsigned int i = random() & d->ht[j].sizemask; // 随机 index，只取 1 次
int size = d->ht[j].size;
while(size--) {// 从 index 处的链表开始，一致向后迭代至 count 个
dictEntry *he = d->ht[j].table[i];
while (he) {
*des = he;
des++;
he = he->next;
stored++;
if (stored == count) return stored;
}
i = (i+1) & d->ht[j].sizemask;
}
assert(dictIsRehashing(d) != 0);
}
}
return stored;
}
dict scan O(1)
// helper 函数，留坑待填
/* Function to reverse bits. Algorithm from:
* http://graphics.stanford.edu/~seander/bithacks.html#ReverseParallel */
static unsigned long rev(unsigned long v) {
unsigned long s = 8 * sizeof(v);
unsigned long mask = ~0;
while ((s >>= 1) > 0) {
mask ^= (mask << s);
v = ((v >> s) & mask) | ((v << s) & ~mask);
}
return v;
}
// 只迭代 v 的链表，并返回下次迭代的下标
unsigned long dictScan(dict *d, unsigned long v, dictScanFunction *fn, void *privdata) {
dictht *t0, *t1;
const dictEntry *de;
unsigned long m0, m1;
if (dictSize(d) == 0) return 0; // 跳过空字典
if (!dictIsRehashing(d)) { // 迭代只有一个哈希表的字典
t0 = &(d->ht[0]); // 指向哈希表
m0 = t0->sizemask; // 记录 mask
de = t0->table[v & m0]; // 指向哈希桶
while (de) { // 遍历桶中的所有节点
fn(privdata, de);
de = de->next;
}
} else { // 迭代有两个哈希表的字典，指向两个哈希表
t0 = &d->ht[0];
t1 = &d->ht[1];
if (t0->size > t1->size) { // 确保 t0 比 t1 要小
t0 = &d->ht[1];
t1 = &d->ht[0];
}
m0 = t0->sizemask; // 记录掩码
m1 = t1->sizemask;
de = t0->table[v & m0]; // 指向桶，并迭代桶中的所有节点
while (de) {
fn(privdata, de);
de = de->next;
}
do { // 迭代大表中的桶，这些桶被索引的 expansion 所指向
de = t1->table[v & m1]; // 指向桶，并迭代桶中的所有节点
while (de) {
fn(privdata, de);
de = de->next;
}
v = (((v | m0) + 1) & ~m0) | (v & m0);
} while (v & (m0 ^ m1));
}
v |= ~m0;
v = rev(v);
v++;
v = rev(v);
return v;
}
这篇关于redis源码阅读-数据结构篇-字典dict的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
-
Redis安装入门：新手必读指南11-18
-
阿里云Redis项目实战入门教程11-08
-
阿里云Redis资料：新手入门与初级使用指南11-08
-
阿里云Redis教程：新手入门及实用指南11-08
-
阿里云Redis学习入门：新手必读指南11-07
-
阿里云Redis学习入门：从零开始的操作指南11-07
-
阿里云Redis学习：初学者指南11-07
-
阿里云Redis入门教程：轻松搭建与使用指南11-06
-
Redis项目实战：新手入门教程11-02
-
Redis入门教程：轻松掌握数据存储与操作10-22
-
Redis缓存入门教程：快速掌握Redis缓存基础知识10-22
-
Redis入门指南：轻松掌握Redis基础操作10-22
-
Redis Quicklist 竟让内存占用狂降50%？10-22
-
Redis学习：从入门到初级应用教程10-17
-
Redis入门：新手必读教程10-12
栏目导航
