Redis source code learning (30), dictionary learning, dict.h

Preface

   After our unremitting efforts , Finally, I finished learning the complex compressed list , Although I have finished my study , But you still need to review often , Reviewing the old and knowing the new can be a teacher , Otherwise, wouldn't it be a cursory study , Then forget the light .

   Today I begin to learn a new data structure , Dictionaries , The dictionary is Redis There are many application scenarios , Like other data structures, let's first learn about its header file dict.h .

1 Dictionaries

   stay Redis in , A dictionary is made up of hash tables , The hash table is composed of many hash nodes , The position of each hash node will calculate a hash value according to the key value to determine its position in the hash table .

2 Structure definition

2.1 dictEntry

typedef struct dictEntry {
    
    void *key;// Key value 
    union {
    
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;// value 
    struct dictEntry *next;// The next node in a hash bucket 
} dictEntry;

   This structure is the definition of hash node , There are 3 Key attributes ,key、v、next, Each represents a key 、 value 、 The next hash node with the same hash value , In the hash table, the hash node may calculate the same index position , Also known as hash conflict , At this time, you need to link these hash nodes at the same location .

2.2 dictType

typedef struct dictType {
    
    unsigned int (*hashFunction)(const void *key);// Calculation  hash  value 
    void *(*keyDup)(void *privdata, const void *key);// Copy key 
    void *(*valDup)(void *privdata, const void *obj);// Copy value 
    int (*keyCompare)(void *privdata, const void *key1, const void *key2);// Compare key values 
    void (*keyDestructor)(void *privdata, void *key);// Key delete 
    void (*valDestructor)(void *privdata, void *obj);// Value delete 
} dictType;

   This structure is some method definitions of hash table

2.3 dictht

typedef struct dictht {
    
    dictEntry **table;// Hash node pointer array 
    unsigned long size;// The length of the hash table 
    unsigned long sizemask;// Mask of hash table length , Generally equal to  size -1
    unsigned long used;// Number of hash nodes 
} dictht;

   This structure is the definition of hash table , There are 4 Attributes table 、size、sizemask、used, among size Indicates the length of the hash table ,sizemask It is used to calculate the index value of hash node ,used Indicates the number of hash nodes in the hash table .

2.4 dict

typedef struct dict {
    
    dictType *type; //  Type function structure pointer 
    void *privdata;//  Private data 
    dictht ht[2]; // Hashtable ,2  individual 
    long rehashidx; /* rehashing not in progress if rehashidx == -1 */ //rehashidx  speed of progress 
    int iterators; /* number of iterators currently running */ // Number of iterators currently running 
} dict;

   This connector is the definition of a dictionary , The structure has 5 Attributes .
   You can see dict It defines two dictht, The function of the two hash tables is to better solve the hash conflict and expand or shrink the hash table , Conduct rehash action , It is to recalculate the index of the hash node of the first hash table and put it into the new hash table .
  rehashidx This attribute represents the current rehash Progress .

3 Macro definition

#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 dictSetSignedIntegerVal(entry, _val_) \ do {
       entry->v.s64 = _val_; } while(0)

#define dictSetUnsignedIntegerVal(entry, _val_) \ do {
       entry->v.u64 = _val_; } while(0)

#define dictSetDoubleVal(entry, _val_) \ do {
       entry->v.d = _val_; } while(0)

#define dictFreeKey(d, entry) \ if ((d)->type->keyDestructor) \ (d)->type->keyDestructor((d)->privdata, (entry)->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)

#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)
#define dictGetVal(he) ((he)->v.val)
#define dictGetSignedIntegerVal(he) ((he)->v.s64)
#define dictGetUnsignedIntegerVal(he) ((he)->v.u64)
#define dictGetDoubleVal(he) ((he)->v.d)
#define dictSlots(d) ((d)->ht[0].size+(d)->ht[1].size)
#define dictSize(d) ((d)->ht[0].used+(d)->ht[1].used)
#define dictIsRehashing(d) ((d)->rehashidx != -1)

4 API

dict *dictCreate(dictType *type, void *privDataPtr);
int dictExpand(dict *d, unsigned long size);
int dictAdd(dict *d, void *key, void *val);
dictEntry *dictAddRaw(dict *d, void *key);
int dictReplace(dict *d, void *key, void *val);
dictEntry *dictReplaceRaw(dict *d, void *key);
int dictDelete(dict *d, const void *key);
int dictDeleteNoFree(dict *d, const void *key);
void dictRelease(dict *d);
dictEntry * dictFind(dict *d, const void *key);
void *dictFetchValue(dict *d, const void *key);
int dictResize(dict *d);
dictIterator *dictGetIterator(dict *d);
dictIterator *dictGetSafeIterator(dict *d);
dictEntry *dictNext(dictIterator *iter);
void dictReleaseIterator(dictIterator *iter);
dictEntry *dictGetRandomKey(dict *d);
unsigned int dictGetSomeKeys(dict *d, dictEntry **des, unsigned int count);
void dictPrintStats(dict *d);
unsigned int dictGenHashFunction(const void *key, int len);
unsigned int dictGenCaseHashFunction(const unsigned char *buf, int len);
void dictEmpty(dict *d, void(callback)(void*));
void dictEnableResize(void);
void dictDisableResize(void);
int dictRehash(dict *d, int n);
int dictRehashMilliseconds(dict *d, int ms);
void dictSetHashFunctionSeed(unsigned int initval);
unsigned int dictGetHashFunctionSeed(void);
unsigned long dictScan(dict *d, unsigned long v, dictScanFunction *fn, void *privdata);

5 Learning summary

1. Redis Chinese dictionary has two hash tables .
2. Redis In order to better resolve hash conflicts rehash action , Recalculate the hash value of the hash node .
3. Hash node dictEntry The pointer of the next hash node with the same index position is recorded in , Easy to find and traverse .
4. Several structures involved in the dictionary are dict、dictht、dictEntry Represent dictionary respectively 、 Hashtable 、 Hash node .
5. dictht Contains an array of hash nodes .