redis源码解析（六）字典结构体基本函数介绍

拼搏现实的明天。 2022-04-16 06:38 144阅读 0赞

### 一. 简介 ###

字典结构是redis中的核心结构之一，本文介绍字典结构的基本函数

### 二. 源码解析 ###

首先是一些有用的宏定义的介绍

/*调用析构函数释放VAL*/
    #define dictFreeVal(d, entry) \ if ((d)->type->valDestructor) \ (d)->type->valDestructor((d)->privdata, (entry)->v.val)
    
    /*调用valDup函数完成赋值*/
    #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)
    
    /* 释放key */
    #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)
    
    
    /* 比较key1和key2对应的值 */
    #define dictCompareKeys(d, key1, key2) \ (((d)->type->keyCompare) ? \ (d)->type->keyCompare((d)->privdata, key1, key2) : \ (key1) == (key2))
    
    /* 返回dict的各个值 */
    #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)

然后是关于哈希值的计算：

static uint8_t dict_hash_function_seed[16];
    
    /* 设置、获取种子 */
    void dictSetHashFunctionSeed(uint8_t *seed) { 
        memcpy(dict_hash_function_seed, seed, sizeof(dict_hash_function_seed));
    } 
    
    uint8_t *dictGetHashFunctionSeed(void) { 
        return dict_hash_function_seed;
    }
    
    /* 根据key获取哈希值 * The default hashing function uses SipHash implementation * in siphash.c. */
    
    uint64_t siphash(const uint8_t *in, const size_t inlen, const uint8_t *k);
    uint64_t siphash_nocase(const uint8_t *in, const size_t inlen, const uint8_t *k);
    
    uint64_t dictGenHashFunction(const void *key, int len) { 
        return siphash(key, len, dict_hash_function_seed);
    }
    
    uint64_t dictGenCaseHashFunction(const unsigned char *buf, int len) { 
        return siphash_nocase(buf, len, dict_hash_function_seed);
    }

基本增删和清零函数如下

/* 哈希表清零 * 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;
    }
    
    /* 新建字典，调用初始化函数 * Create a new hash table */
    dict *dictCreate(dictType *type,
            void *privDataPtr)
    { 
        dict *d = zmalloc(sizeof(*d));
    
        _dictInit(d,type,privDataPtr);
        return d;
    }
    
    /* 初始化字典d，包括两个哈希表的初始化 * 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;
    }
    
    /* 字典重新设置大小 * Resize the table to the minimal size that contains all the elements, * but with the invariant of a USED/BUCKETS ratio near to <= 1 */
    int dictResize(dict *d)
    { 
        int minimal;
    
        if (!dict_can_resize || dictIsRehashing(d)) return DICT_ERR;
        minimal = d->ht[0].used;
        if (minimal < DICT_HT_INITIAL_SIZE)
            minimal = DICT_HT_INITIAL_SIZE;
        return dictExpand(d, minimal);
    }
    
    /* 字典的扩展或者创建（第一次扩展即创建） * Expand or create the hash table */
    int dictExpand(dict *d, unsigned long size)
    { 
        dictht n; /* the new hash table */
    	
    	/*返回realsize值为大于size的2的次方*/
        unsigned long realsize = _dictNextPower(size);
    
        /* 分配size要大于已用空间才有效 * the size is invalid if it is smaller than the number of * elements already inside the hash table */
        if (dictIsRehashing(d) || d->ht[0].used > size)
            return DICT_ERR;
    
        /* 如果size和已有size相等则无效 * Rehashing to the same table size is not useful. */
        if (realsize == d->ht[0].size) return DICT_ERR;
    
        /* 新建并初始化字典n * Allocate the new hash table and initialize all pointers to NULL */
        n.size = realsize;
        n.sizemask = realsize-1;
        n.table = zcalloc(realsize*sizeof(dictEntry*));
        n.used = 0;
    
        /* 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. */
        if (d->ht[0].table == NULL) { 
            d->ht[0] = n;
            return DICT_OK;
        }
    
        /* Prepare a second hash table for incremental rehashing */
        d->ht[1] = n;
        d->rehashidx = 0;
        return DICT_OK;
    }