当前位置:网站首页>Redis source code learning (31), dictionary learning, dict.c (1)
Redis source code learning (31), dictionary learning, dict.c (1)
2022-07-07 04:02:00 【Traceless meaning】
1 dictCreate
1.1 Method statement
Create a new hash table
1.2 Method source code
/* Create a new hash table */
dict *dictCreate(dictType *type,
void *privDataPtr)
{
dict *d = zmalloc(sizeof(*d));// Allocate memory
_dictInit(d,type,privDataPtr);// Dictionary initialization
return d;
}
1.3 Related methods
1.3.1 _dictInit
/* Initialize the hash table */
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;
d->iterators = 0;
return DICT_OK;
}
1.3.2 _dictReset
/* Reset a hash table already initialized with ht_init(). * NOTE: This function should only be called by ht_destroy(). */
static void _dictReset(dictht *ht)
{
ht->table = NULL;
ht->size = 0;
ht->sizemask = 0;
ht->used = 0;
}
1.4 Code understanding
- First declare a dictionary structure , And allocate the corresponding memory .
- call _dictInit Initialize Dictionary .
- call _dictReset Initialize two hash tables in the dictionary .
- Set several attribute fields in the hash table to initial values .
2 dictAdd
2.1 Method statement
Add a hash node to the hash table .
2.2 Method source code
/* Add an element to the target hash table */
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;
}
2.3 Related codes
2.3.1 dictAddRaw
/* Low level add. 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 he wishes. * * 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); * if (entry != NULL) dictSetSignedIntegerVal(entry,1000); * * Return values: * * If key already exists NULL is returned. * If key was added, the hash entry is returned to be manipulated by the caller. */
dictEntry *dictAddRaw(dict *d, void *key)
{
int index;
dictEntry *entry;
dictht *ht;
// If the dictionary is in progress rahase in , Then proceed to step rahash
if (dictIsRehashing(d)) _dictRehashStep(d);
/* Get the index of the new element, or -1 if * the element already exists. */
// Get the built index
if ((index = _dictKeyIndex(d, key)) == -1)
return NULL;
/* Allocate the memory and store the new entry */
// If in rehash in Returns the second hash In the table
// Add the new hash node to the second hash In the table
ht = dictIsRehashing(d) ? &d->ht[1] : &d->ht[0];
entry = zmalloc(sizeof(*entry));
entry->next = ht->table[index];
ht->table[index] = entry;
ht->used++;
/* Set the hash entry fields. */
// Set hash build
dictSetKey(d, entry, key);
return entry;
}
2.3.2 _dictKeyIndex
/* Returns the index of a free slot that can be populated with * a hash entry for the given 'key'. * If the key already exists, -1 is returned. * * Note that if we are in the process of rehashing the hash table, the * index is always returned in the context of the second (new) hash table. */
static int _dictKeyIndex(dict *d, const void *key)
{
unsigned int h, idx, table;
dictEntry *he;
/* Expand the hash table if needed */
if (_dictExpandIfNeeded(d) == DICT_ERR)
return -1;
/* Compute the key hash value */
h = dictHashKey(d, key);
for (table = 0; table <= 1; table++) {
idx = h & d->ht[table].sizemask;
/* Search if this slot does not already contain the given key */
he = d->ht[table].table[idx];
while(he) {
if (dictCompareKeys(d, key, he->key))
return -1;
he = he->next;
}
if (!dictIsRehashing(d)) break;
}
return idx;
}
2.4 Code understanding
- call dictAddRaw Add a hash node
- Calculate the index value of the key , If the value already exists, an error is returned
- If it's going on rehash Words , Nodes will be added to the second hash table
- Call macro definition method dictSetKey Set the key of the hash node
- Call macro definition method dictSetVal Set the value of the hash node
3 Learning summary
- When adding a new hash node , If the node already exists, an error will be reported .
- call dictHashKey Calculate the hash value of the key .
- Then calculate the index position with hash value and dictionary mask .
- Traverse two hash tables , Determine whether the key already exists .
- If the dictionary is rehash In the words of , The new node will be added to the second hash table .
- If the dictionary is rehash In the words of , Will go one step rehash The action of .
边栏推荐
- tflite模型转换和量化
- 【mysql】mysql中行排序
- 二进制、八进制、十六进制
- Implementation steps of docker deploying mysql8
- Vernacular high concurrency (2)
- Binary, octal, hexadecimal
- AVL树插入操作与验证操作的简单实现
- ERROR: Could not build wheels for pycocotools which use PEP 517 and cannot be installed directly
- It's too convenient. You can complete the code release and approval by nailing it!
- Construction of Hisilicon universal platform: color space conversion YUV2RGB
猜你喜欢
随机推荐
手机号国际区号JSON格式另附PHP获取
Redis configuration and optimization of NoSQL
Probability formula
史上最全学习率调整策略lr_scheduler
SSL certificate deployment
Operational amplifier application summary 1
Class常量池与运行时常量池
NoSQL之Redis配置与优化
【开发软件】 tilipa开发者软件
On file uploading of network security
Implementation of binary search tree
[leetcode] 700 and 701 (search and insert of binary search tree)
什么是 BA ?BA怎么样?BA和BI是什么关系?
List interview common questions
Kotlin Android environment construction
vim —- 自己主动的按钮indent该命令「建议收藏」
[dpdk] dpdk sample source code analysis III: dpdk-l3fwd_ 001
运算放大器应用汇总1
力扣------路径总和 III
中青杯2022A题高校数学建模竞赛与课程教育思路分析