深入redis内部--字典实现
redis的字典定义和实现在dict.h和dict.c文件中。 1.字典结构 typedef *type;
*];
rehashidx;
iterators;
} dict;
其中涉及到数据结构,如下所示: ?1.1 字典类型,包含了一系列字典所需要用到的函数 typedef (*hashFunction)( *key);
*(*keyDup)( *privdata, *key);
*(*valDup)( *privdata, *obj);
(*keyCompare)( *privdata, *key1, *key2);
(*keyDestructor)( *privdata, *key);
(*valDestructor)( *privdata, *obj);
} dictType;
1.2 哈希表结构,每个字典有两个哈希表。当哈希表扩容时实现散列。 typedef ** size;
unsigned sizemask;
unsigned used;
} dictht;
1.3 dictEntry为字典的条目,其定义如下: typedef *key;
union {
* dictEntry *
2. 字典的遍历--字典遍历器 typedef **entry,* fingerprint;
注意:当safe=1时,该遍历器是安全的,即字典可以在遍历的同时执行dictAdd,dictFind,和别的函数。否则遍历器是不安全的,遍历时只能执行dictNext()。 ? ?迭代器提供了遍历字典中所有元素的方法,通过dicGetIterator()获得迭代器后,使用dictNext(dictIterator *)获得下一个元素。遍历的过程,先从ht[0]开始,依次从第一个桶table[0]开始遍历桶中的元素,然后遍历table[1],'***,table[size],若正在扩容,则会继续遍历ht[1]中的桶。遍历桶中元素时,依次访问链表中的每一个元素。 3.宏定义函数 dictFreeVal(d,entry)
((d)->type->->type->valDestructor((d)->privdata,(entry)-><span style="color: #0000ff;">#define dictSetVal(d,entry,val) do {
<span style="color: #0000ff;">if ((d)->type-><span style="color: #000000;">valDup) entry->v.val = (d)->type->valDup((d)-><span style="color: #000000;">privdata,val); <span style="color: #0000ff;">else<span style="color: #000000;"> entry->v.val =<span style="color: #000000;"> (val); } <span style="color: #0000ff;">while(<span style="color: #800080;">0<span style="color: #000000;">) <span style="color: #0000ff;">#define dictSetSignedIntegerVal(entry,val) <span style="color: #0000ff;">#define dictSetUnsignedIntegerVal(entry,val) <span style="color: #0000ff;">#define dictFreeKey(d,entry) <span style="color: #0000ff;">#define dictSetKey(d,key) do { <span style="color: #0000ff;">#define dictCompareKeys(d,key1,key2) &;span style="color: #000000;"> <span style="color: #0000ff;">#define dictHashKey(d,key) (d)->type->hashFunction(key) 4. 字典提供的api,有字典的创建,增加、删除、修改记录,还有迭代器(前面已经介绍)和自动扩容(下面介绍)。 dict *dictCreate(dictType *type, * dictExpand(dict *d,unsigned dictAdd(dict *d, *key, **dictAddRaw(dict *d, * dictReplace(dict *d, **dictReplaceRaw(dict *d, * dictDelete(dict *d, * dictDeleteNoFree(dict *d, * dictRelease(dict ** dictFind(dict *d, * *dictFetchValue(dict *d, * dictResize(dict **dictGetIterator(dict **dictGetSafeIterator(dict **dictNext(dictIterator * dictReleaseIterator(dictIterator **dictGetRandomKey(dict * dictPrintStats(dict * dictGenHashFunction( *key, dictGenCaseHashFunction( unsigned *buf, dictEmpty(dict * dictEnableResize( dictDisableResize( dictRehash(dict *d, dictRehashMilliseconds(dict *d, dictSetHashFunctionSeed(unsigned dictGetHashFunctionSeed();
5.外部定义变量 <span style="color: #0000ff;">extern <span style="color: #000000;"> dictType dictTypeHeapStringCopyKey;<span style="color: #0000ff;">extern<span style="color: #000000;"> dictType dictTypeHeapStrings; <span style="color: #0000ff;">extern dictType dictTypeHeapStringCopyKeyValue; ?6. 自动扩容 ? ? Redis使用标识dict_can_resize来记录字典是否可以扩容,可以使用dictEnableResize()方法和dictDisableResize()来改变此标识。使用dictResize()来扩容,但需要首先判断是否允许扩容及是否正在扩容。若可以扩容,则调用dictExpand()扩容,然后调用dictRehashMilliseconds()启动扩容,并指定扩容过程中记录的copy速度。请看程序: ? ?6.1 dictResize()
dictResize(dict *
</span><span style="color: #0000ff;">if</span> (!dict_can_resize || dictIsRehashing(d)) <span style="color: #0000ff;">return</span><span style="color: #000000;"> DICT_ERR;
minimal </span>= d->ht[<span style="color: #800080;">0</span><span style="color: #000000;">].used;
</span><span style="color: #0000ff;">if</span> (minimal <<span style="color: #000000;"> DICT_HT_INITIAL_SIZE)
minimal </span>=<span style="color: #000000;"> DICT_HT_INITIAL_SIZE;
</span><span style="color: #0000ff;">return</span><span style="color: #000000;"> dictExpand(d,minimal);
} ? ?6.2?dictExpand()
dictExpand(dict *d,unsigned realsize =
</span><span style="color: #008000;">/*</span><span style="color: #008000;"> the size is invalid if it is smaller than the number of
* elements already inside the hash table </span><span style="color: #008000;">*/</span>
<span style="color: #0000ff;">if</span> (<span style="color: #000000;">dictIsRehashing</span>(d) || d->ht[<span style="color: #800080;">0</span>].used ><span style="color: #000000;"> size)
</span><span style="color: #0000ff;">return</span><span style="color: #000000;"> DICT_ERR;
</span><span style="color: #008000;">/*</span><span style="color: #008000;"> Allocate the new hash table and initialize all pointers to NULL </span><span style="color: #008000;">*/</span><span style="color: #000000;">
n.size </span>=<span style="color: #000000;"> realsize;
n.sizemask </span>= realsize-<span style="color: #800080;">1</span><span style="color: #000000;">;
n.table </span>= zcalloc(realsize*<span style="color: #0000ff;">sizeof</span>(dictEntry*<span style="color: #000000;">));
n.used </span>= <span style="color: #800080;">0</span><span style="color: #000000;">;
</span><span style="color: #008000;">/*</span><span style="color: #008000;"> 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. </span><span style="color: #008000;">*/</span>
<span style="color: #0000ff;">if</span> (d->ht[<span style="color: #800080;">0</span>].table ==<span style="color: #000000;"> NULL) {
d</span>->ht[<span style="color: #800080;">0</span>] =<span style="color: #000000;"> n;
</span><span style="color: #0000ff;">return</span><span style="color: #000000;"> DICT_OK;
}
</span><span style="color: #008000;">/*</span><span style="color: #008000;"> Prepare a second hash table for incremental rehashing </span><span style="color: #008000;">*/</span><span style="color: #000000;">
d</span>->ht[<span style="color: #800080;">1</span>] =<span style="color: #000000;"> n;
d</span>->rehashidx = <span style="color: #800080;">0</span><span style="color: #000000;">;
</span><span style="color: #0000ff;">return</span><span style="color: #000000;"> DICT_OK;
} 6.3?
dictRehashMilliseconds(dict *d, start = rehashes = </span><span style="color: #0000ff;">while</span>(dictRehash(d,<span style="color: #800080;">100</span><span style="color: #000000;">)) {
rehashes </span>+= <span style="color: #800080;">100</span><span style="color: #000000;">;
</span><span style="color: #0000ff;">if</span> (timeInMilliseconds()-start > ms) <span style="color: #0000ff;">break</span><span style="color: #000000;">;
}
</span><span style="color: #0000ff;">return</span><span style="color: #000000;"> rehashes;
} (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |