Redis source code learning (31), dictionary learning, dict.c (1)

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

1. First declare a dictionary structure , And allocate the corresponding memory .
2. call _dictInit Initialize Dictionary .
3. call _dictReset Initialize two hash tables in the dictionary .
4. 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

1. call dictAddRaw Add a hash node
2. Calculate the index value of the key , If the value already exists, an error is returned
3. If it's going on rehash Words , Nodes will be added to the second hash table
4. Call macro definition method dictSetKey Set the key of the hash node
5. Call macro definition method dictSetVal Set the value of the hash node

3 Learning summary

1. When adding a new hash node , If the node already exists, an error will be reported .
2. call dictHashKey Calculate the hash value of the key .
3. Then calculate the index position with hash value and dictionary mask .
4. Traverse two hash tables , Determine whether the key already exists .
5. If the dictionary is rehash In the words of , The new node will be added to the second hash table .
6. If the dictionary is rehash In the words of , Will go one step rehash The action of .