Redis源码学习基本数据结构之dict
2019-04-24 本文已影响0人
lixin_karl
字典（dictionary），又名映射（map）或关联数组（associative array）， 它是一种抽象数据结构，由一集键值对（key-value pairs）组成，各个键值对的键各不相同，程序可以将新的键值对添加到字典中，或者基于键进行查找、更新或删除等操作。
一、结构
//dict的一个数据表示 entry
typedef struct dictEntry {
void *key; //关键字
union {
void *val;
uint64_t u64;
int64_t s64;
double d;
} v; //val
struct dictEntry *next; //next
} dictEntry;
typedef struct dictType { //字典类型
uint64_t (*hashFunction)(const void *key); //hash函数
void *(*keyDup)(void *privdata, const void *key); //key复制函数
void *(*valDup)(void *privdata, const void *obj); //val复制函数
int (*keyCompare)(void *privdata, const void *key1, const void *key2);//key比较函数
void (*keyDestructor)(void *privdata, void *key); //key析构函数
void (*valDestructor)(void *privdata, void *obj); //val析构函数
} dictType;
typedef struct dictht { //32字节 hashTable 结构
dictEntry **table; //8字节 哈希表节点指针数组（俗称桶，bucket）
unsigned long size; //8字节 指针数组的大小(桶的数量)
unsigned long sizemask; /*8字节 指针数组的长度掩码，用于计算索引值 sizemask=size-1
这样保证索引值(sizemask&hash) 在数组有效索引范围内*/
unsigned long used; //8字节 hash表现有节点的数量
} dictht;
typedef struct dict { //96字节 字典结构
dictType *type; //8字节 字典的一些api表示的类型
void *privdata; //8字节 类型处理函数的私有数据
dictht ht[2]; //64字节 两个hashTable 用于rehash ht[0]是正常情况下的hashtable ht[1]是rehash要用到的
long rehashidx; /*8字节 记录 rehash 进度的标志，值为-1 表示 rehash 未进行 */
unsigned long iterators; /*8字节 当前运行的iterator的个数 */
} dict;
//如果safe为1的话 dict的一些api都可以调用 否则只能调用 dictNext
typedef struct dictIterator { //dictEntry迭代器
dict *d; //字典
long index; // 当前迭代器下标,初始化值为-1，因为0槽位不一定有数据。
int table; //哪个hash表 0 或者1
int safe; //安全标志 1 为安全
dictEntry *entry; //当前的entry
dictEntry *nextEntry; //下一个entry
long long fingerprint; //fingerprint是64字节的数字 它是表示给定时间内字典的状态
} dictIterator;
二、主要api
//hashTable 的初始化大小
#define DICT_HT_INITIAL_SIZE 4
/* ------------------------------- Macros ------------------------------------*/
//释放val
#define dictFreeVal(d, entry) \
if ((d)->type->valDestructor) \
(d)->type->valDestructor((d)->privdata, (entry)->v.val)
//设置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 dictSetSignedIntegerVal(entry, _val_) \
do { (entry)->v.s64 = _val_; } while(0)
//设置无符号数字值
#define dictSetUnsignedIntegerVal(entry, _val_) \
do { (entry)->v.u64 = _val_; } while(0)
//设置double浮点数
#define dictSetDoubleVal(entry, _val_) \
do { (entry)->v.d = _val_; } while(0)
//释放key
#define dictFreeKey(d, entry) \
if ((d)->type->keyDestructor) \
(d)->type->keyDestructor((d)->privdata, (entry)->key)
//设置key
#define dictSetKey(d, entry, _key_) do { \
if ((d)->type->keyDup) \
(entry)->key = (d)->type->keyDup((d)->privdata, _key_); \
else \
(entry)->key = (_key_); \
} while(0)
//比较key
#define dictCompareKeys(d, key1, key2) \
(((d)->type->keyCompare) ? \
(d)->type->keyCompare((d)->privdata, key1, key2) : \
(key1) == (key2))
//得到key的hash值
#define dictHashKey(d, key) (d)->type->hashFunction(key)
//得到key
#define dictGetKey(he) ((he)->key)
//得到val
#define dictGetVal(he) ((he)->v.val)
//得到有符号数字
#define dictGetSignedIntegerVal(he) ((he)->v.s64)
//得到无符号数字
#define dictGetUnsignedIntegerVal(he) ((he)->v.u64)
//得到double浮点数
#define dictGetDoubleVal(he) ((he)->v.d)
//hash表的槽数
#define dictSlots(d) ((d)->ht[0].size+(d)->ht[1].size)
//hash表的被使用的个数
#define dictSize(d) ((d)->ht[0].used+(d)->ht[1].used)
//hash表是否在rehashing
#define dictIsRehashing(d) ((d)->rehashidx != -1)
/* API */
dict *dictCreate(dictType *type, void *privDataPtr);//创建一个字典 各种初始化
int dictExpand(dict *d, unsigned long size);//扩大字典中hashtable的容量
int dictAdd(dict *d, void *key, void *val);//插入数据
dictEntry *dictAddRaw(dict *d, void *key, dictEntry **existing);//插入key
dictEntry *dictAddOrFind(dict *d, void *key);//要么找到dictEntry 要么插入新的dictEntry并返回
int dictReplace(dict *d, void *key, void *val);//替换val或者插入键值对
int dictDelete(dict *d, const void *key);//删除某个key
dictEntry *dictUnlink(dict *ht, const void *key);//不释放内存 应该随后调用dictFreeUnlinkedEntry()释放内存
void dictFreeUnlinkedEntry(dict *d, dictEntry *he);// 释放dictEntry内存
void dictRelease(dict *d); //释放字典
dictEntry * dictFind(dict *d, const void *key); //查找key
void *dictFetchValue(dict *d, const void *key); //得到key对应的值
int dictResize(dict *d); //重新hash到合适的程度
dictIterator *dictGetIterator(dict *d);//得到dict迭代器
dictIterator *dictGetSafeIterator(dict *d);//得到dict安全迭代器
dictEntry *dictNext(dictIterator *iter);// next
void dictReleaseIterator(dictIterator *iter);//释放迭代器内存
dictEntry *dictGetRandomKey(dict *d);//得到一个随机的dictEntry
dictEntry *dictGetFairRandomKey(dict *d);//得到一个随机的dictEntry
unsigned int dictGetSomeKeys(dict *d, dictEntry **des, unsigned int count);//得到一些dictEntry
void dictGetStats(char *buf, size_t bufsize, dict *d);//打印字典的状态
uint64_t dictGenHashFunction(const void *key, int len);//hash函数
uint64_t dictGenCaseHashFunction(const unsigned char *buf, int len);//hash函数
void dictEmpty(dict *d, void(callback)(void*));//清空字典
void dictEnableResize(void);//设置可以resize
void dictDisableResize(void);//设置不可以Resize
int dictRehash(dict *d, int n);// rehash
int dictRehashMilliseconds(dict *d, int ms);//rehash 时间限制
void dictSetHashFunctionSeed(uint8_t *seed);//设置hash函数的种子
uint8_t *dictGetHashFunctionSeed(void);//得到hash函数的种子
//遍历dict
unsigned long dictScan(dict *d, unsigned long v, dictScanFunction *fn, dictScanBucketFunction *bucketfn, void *privdata);
uint64_t dictGetHash(dict *d, const void *key);//得到key对应的hash值
dictEntry **dictFindEntryRefByPtrAndHash(dict *d, const void *oldptr, uint64_t hash);//根据指针hehash查找entry
三、主要函数解析
dictAdd
int dictAdd(dict *d, void *key, void *val)
{
dictEntry *entry = dictAddRaw(d,key,NULL);//返回新加的entry的首地址
//设置此entry的值
if (!entry) return DICT_ERR;
dictSetVal(d, entry, val);
return DICT_OK;
}
dictEntry *dictAddRaw(dict *d, void *key, dictEntry **existing)
{
long index;
dictEntry *entry;
dictht *ht;
if (dictIsRehashing(d)) _dictRehashStep(d);//如果需要rehash
//返回-1 表示此key存在
if ((index = _dictKeyIndex(d, key, dictHashKey(d,key), existing)) == -1)
return NULL;
//正在rehash的话 使用table1否则使用table0
ht = dictIsRehashing(d) ? &d->ht[1] : &d->ht[0];
entry = zmalloc(sizeof(*entry));
entry->next = ht->table[index];
ht->table[index] = entry;
ht->used++;
dictSetKey(d, entry, key);
return entry;
}
dictDelete
int dictDelete(dict *ht, const void *key) {
return dictGenericDelete(ht,key,0) ? DICT_OK : DICT_ERR;
}
//nofree 0 释放键值对内存 1 不释放
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);//hash值
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)) {//找到key相等的dictEntry
/* Unlink the element from the list */
if (prevHe)//槽位内的链表要更新next
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 he;
}
prevHe = he;
he = he->next;
}
if (!dictIsRehashing(d)) break;//如果没有rehash 直接不用再找了
}
return NULL; /* not found */
}
dictRehash
//rehash 过程 如果仍然有keys从老hash表移到新的hash表 返回1
//n 表示此次rehash 移动的个数
int dictRehash(dict *d, int n) {
int empty_visits = n*10; /*可以遇到的空槽的个数*/
if (!dictIsRehashing(d)) return 0;
while(n-- && d->ht[0].used != 0) {
dictEntry *de, *nextde;
assert(d->ht[0].size > (unsigned long)d->rehashidx);//size 必须要大于index的
while(d->ht[0].table[d->rehashidx] == NULL) {//走到下一个槽位
d->rehashidx++;
if (--empty_visits == 0) return 1;
}
de = d->ht[0].table[d->rehashidx];
// 从oldhash表中rehashidx位的数据开始rehash 把ht[0]中的de移动到ht[1]中
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++;
}
//如果hash表已经被重新rehash了 做相应的处理
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;
}
return 1;
}
dictNext
dictEntry *dictNext(dictIterator *iter)
{
while (1) {
if (iter->entry == NULL) {//如果当前 entry 为空 要找到第一个不为空的entry
dictht *ht = &iter->d->ht[iter->table];//拿到当前hash table
if (iter->index == -1 && iter->table == 0) {//说明是初始化的iter
if (iter->safe)
iter->d->iterators++;
else
iter->fingerprint = dictFingerprint(iter->d);
}
iter->index++;//顺着index往后找
if (iter->index >= (long) ht->size) {//index 大于size时
if (dictIsRehashing(iter->d) && iter->table == 0) {//那么如果能找到肯定在另一个table里面，跳到ht[1]寻找
iter->table++;
iter->index = 0;
ht = &iter->d->ht[1];
} else {//找到了 跳出循环
break;
}
}
iter->entry = ht->table[iter->index];
} else {//当前entry不为空 直接走流程
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;
}
