`

redis2.6.9源码学习---dict

阅读更多

redis的hashtable------dict.c

先了解基本的struct

typedef struct dictEntry {
    void *key;
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
    } v;
    struct dictEntry *next;
} dictEntry;

typedef struct dictType {
    unsigned int (*hashFunction)(const void *key);
    void *(*keyDup)(void *privdata, const void *key);
    void *(*valDup)(void *privdata, const void *obj);
    int (*keyCompare)(void *privdata, const void *key1, const void *key2);
    void (*keyDestructor)(void *privdata, void *key);
    void (*valDestructor)(void *privdata, void *obj);
} dictType;

/* This is our hash table structure. Every dictionary has two of this as we
 * implement incremental rehashing, for the old to the new table. */
typedef struct dictht {
    dictEntry **table;
    unsigned long size;
    unsigned long sizemask;
    unsigned long used;
} dictht;

typedef struct dict {
    dictType *type;
    void *privdata;
    dictht ht[2];
    int rehashidx; /* rehashing not in progress if rehashidx == -1 */
    int iterators; /* number of iterators currently running */
} dict;

 这里先提醒一下dictType中都是hashtable dictEntry 绑定的指向哈希函数的指针变量,切不要混淆函数指针.

 

下面逐个分析dict.c中的方法

/* 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;
}

/* 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;
}
zmalloc分配内存给*d,参数dictType *type为*d的哈希函数,reset *d的两个hashtable,设置rehashidx=-1(在上面的结构注释中已说明:如果rehashidex==-1就不在rehashing过程中),设置迭代数为0.

 

/* Expand or create the hash table */
int dictExpand(dict *d, unsigned long size)
{
    dictht n; /* the new hash table */
    unsigned long realsize = _dictNextPower(size);
*******
/* Our hash table capability is a power of two */
static unsigned long _dictNextPower(unsigned long size)
{
    unsigned long i = DICT_HT_INITIAL_SIZE;

    if (size >= LONG_MAX) return LONG_MAX;
    while(1) {
        if (i >= size)
            return i;
        i *= 2;
    }
}
DICT_HT_INITIAL_SIZE 在dict.h中define为4,hashtable容量都是2的次方,容量不能超过LONG_MAX
*******
    /* 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;
**********
#define dictIsRehashing(ht) ((ht)->rehashidx != -1)
 我们*d如果是刚创建的,那肯定是-1,所以dictIsRehashing(d)为false,如果是扩张的,为true,此处used不能大于刚刚扩张的容量
*********

    /* 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;
    }
这里如果*d是新创建的将不会rehashing,否则将刚创建的hashtable n赋值给d的ht[1]以便于进行rehash

    /* Prepare a second hash table for incremental rehashing */
    d->ht[1] = n;
    d->rehashidx = 0;
    return DICT_OK;
}

 

/* Performs N steps of incremental rehashing. Returns 1 if there are still
 * keys to move from the old to the new hash table, otherwise 0 is returned.
 * Note that a rehashing step consists in moving a bucket (that may have more
 * thank one key as we use chaining) from the old to the new hash table. */
int dictRehash(dict *d, int n) {
    if (!dictIsRehashing(d)) return 0;

    while(n--) {
        dictEntry *de, *nextde;

        /* Check if we already rehashed the whole table... */
        if (d->ht[0].used == 0) {
            zfree(d->ht[0].table);
            d->ht[0] = d->ht[1];
            _dictReset(&d->ht[1]);
            d->rehashidx = -1;
            return 0;
        }
***********
如果d->ht[0].used == 0,释放table内存,将1赋值给0,再将1给reset,将rehashidx重新标记为-1(检查我们刚刚已经rehash过table,这样就不用向下去rehash了)
***********

        /* Note that rehashidx can't overflow as we are sure there are more
         * elements because ht[0].used != 0 */
        assert(d->ht[0].size > (unsigned)d->rehashidx);
        while(d->ht[0].table[d->rehashidx] == NULL) d->rehashidx++;
        // 取到最先开始有值的table,赋值给de,减少后面的while循环
        de = d->ht[0].table[d->rehashidx];
        /* Move all the keys in this bucket from the old to the new hash HT */
        while(de) {
            unsigned int h;

            nextde = de->next;
            /* Get the index in the new hash table */
            h = dictHashKey(d, de->key) & d->ht[1].sizemask;
            //通过上述绑定的哈希函数并与sizemask进行位运算得到key 的索引,后面将ht[0]赋值给ht[1],ht[1]的作用就在于此,可以说它就是为rehash而创建的,它相当于一个salve,rehash时作ht[1]的一个备份,最后ht[1] 又会赋值给ht[0],再reset ht[1]
            de->next = d->ht[1].table[h];
            d->ht[1].table[h] = de;
            d->ht[0].used--;
            d->ht[1].used++;
            de = nextde;
        }
        d->ht[0].table[d->rehashidx] = NULL;//清除ht[0]
        d->rehashidx++;//将rehash标识+1
    }
    return 1;
}

 

/* This function performs just a step of rehashing, and only if there are
 * no safe iterators bound to our hash table. When we have iterators in the
 * middle of a rehashing we can't mess with the two hash tables otherwise
 * some element can be missed or duplicated.
 *
 * This function is called by common lookup or update operations in the
 * dictionary so that the hash table automatically migrates from H1 to H2
 * while it is actively used. */
static void _dictRehashStep(dict *d) {
if (d->iterators == 0) dictRehash(d,1);
}
//迭代器为0时,rehash一次,目的就是将ht[1]赋值给ht[0]


/* Expand the hash table if needed */
static int _dictExpandIfNeeded(dict *d)
{
    /* Incremental rehashing already in progress. Return. */
    if (dictIsRehashing(d)) return DICT_OK;

    /* If the hash table is empty expand it to the intial size. */
    if (d->ht[0].size == 0) return dictExpand(d, DICT_HT_INITIAL_SIZE);
//这里用到了上面讲到的dictexpand方法,
    /* If we reached the 1:1 ratio, and we are allowed to resize the hash
     * table (global setting) or we should avoid it but the ratio between
     * elements/buckets is over the "safe" threshold, we resize doubling
     * the number of buckets. */
    if (d->ht[0].used >= d->ht[0].size &&
        (dict_can_resize ||
         d->ht[0].used/d->ht[0].size > dict_force_resize_ratio))
//dict_force_resize_radio定义为5,有点不解,为什么是5倍才expand
    {
        return dictExpand(d, ((d->ht[0].size > d->ht[0].used) ?
                                    d->ht[0].size : d->ht[0].used)*2);
    }
    return DICT_OK;
}

 

/* Returns the index of a free slot that can be populated with
 * an 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);//获取key的索引值
//遍历ht[0],ht[1]
    for (table = 0; table <= 1; table++) {
        idx = h & d->ht[table].sizemask;
//rehash中的 /* Get the index in the new hash table */
            h = dictHashKey(d, de->key) & d->ht[1].sizemask;
这里再&,取回idx
        /* 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))//哈希函数比较key,存在则返回-1
                return -1;
            he = he->next;
        }
        if (!dictIsRehashing(d)) break;
    }
    return idx;
}

/* 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 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 (dictIsRehashing(d)) _dictRehashStep(d);//这里rehash while1次

    /* Get the index of the new element, or -1 if
     * the element already exists. */
    if ((index = _dictKeyIndex(d, key)) == -1)//如果有相同的key就返回
        return NULL;

    /* Allocate the memory and store the new entry */
    ht = dictIsRehashing(d) ? &d->ht[1] : &d->ht[0];//上面_dictRehashStep将ht[0]赋值给了ht[1]
    entry = zmalloc(sizeof(*entry));//malloc新的内存
    entry->next = ht->table[index];//新的next是ht的index,可见是插入table的头部
    ht->table[index] = entry;
    ht->used++;

    /* Set the hash entry fields. */
    dictSetKey(d, entry, key)//哈希函数设置key
    return entry;
}

/* 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);//哈希函数设置val
    return DICT_OK;
}

 

dictEntry *dictFind(dict *d, const void *key)
{
    dictEntry *he;
    unsigned int h, idx, table;

    if (d->ht[0].size == 0) return NULL; /* We don't have a table at all 没有东东,找个屁啊,呵呵*/
    if (dictIsRehashing(d)) _dictRehashStep(d);//又是这一步
//下面的跟_dictKeyIndex内容相同
    h = dictHashKey(d, key);
    for (table = 0; table <= 1; table++) {
        idx = h & d->ht[table].sizemask;
        he = d->ht[table].table[idx];
        while(he) {
            if (dictCompareKeys(d, key, he->key))
                return he;
            he = he->next;
        }
        if (!dictIsRehashing(d)) return NULL;
    }
    return NULL;
}

/* Add an element, discarding the old if the key already exists.
 * Return 1 if the key was added from scratch, 0 if there was already an
 * element with such key and dictReplace() just performed a value update
 * operation. */
int dictReplace(dict *d, void *key, void *val)
{
    dictEntry *entry, auxentry;

    /* Try to add the element. If the key
     * does not exists dictAdd will suceed. */
    if (dictAdd(d, key, val) == DICT_OK)//直接add,没成功说明有相同的key
        return 1;
    /* It already exists, get the entry */
    entry = dictFind(d, key);
    /* Set the new value and free the old one. Note that it is important
     * to do that in this order, as the value may just be exactly the same
     * as the previous one. In this context, think to reference counting,
     * you want to increment (set), and then decrement (free), and not the
     * reverse. */
//后面的要注意,setval之后还有freeval,将老的entry释放,可见dictSetVal方法不是直接去修改entry的val,而是重新创建内存放新的val
    auxentry = *entry;
    dictSetVal(d, entry, val);
    dictFreeVal(d, &auxentry);
    return 0;
}

 

/* dictReplaceRaw() is simply a version of dictAddRaw() that always
 * returns the hash entry of the specified key, even if the key already
 * exists and can't be added (in that case the entry of the already
 * existing key is returned.)
 *
 * See dictAddRaw() for more information. */
dictEntry *dictReplaceRaw(dict *d, void *key) {
    dictEntry *entry = dictFind(d,key);

    return entry ? entry : dictAddRaw(d,key);
}
//这个方法并不能真正的replace key值,如果key存在则返回key对应的table,不然就key添加


//方法有点多,最后讲下redis.c serverCron会调用的方法
long long timeInMilliseconds(void) {
    struct timeval tv;

    gettimeofday(&tv,NULL);
    return (((long long)tv.tv_sec)*1000)+(tv.tv_usec/1000);
}

/* Rehash for an amount of time between ms milliseconds and ms+1 milliseconds */
int dictRehashMilliseconds(dict *d, int ms) {
    long long start = timeInMilliseconds();
    int rehashes = 0;

    while(dictRehash(d,100)) {
        rehashes += 100;
        if (timeInMilliseconds()-start > ms) break;
    }
    return rehashes;
}
//在1毫秒的时间里去rehash,每次while100次

 

  • 大小: 21.2 KB
分享到:
评论

相关推荐

    Redis-x64-5.0.14.msi和Redis-x64-5.0.14.zip

    解压后,你可以找到包括`redis-server.exe`、`redis-cli.exe`等在内的可执行文件,以及配置文件`redis.conf`。这种方式适合于需要自定义配置或手动管理服务的用户。通过编辑`redis.conf`,你可以调整Redis的各项参数...

    Redis稳定版 Redis-x64-5.0.14.1.zip

    本次提供的版本是Redis的稳定版——Redis-x64-5.0.14.1,针对64位操作系统设计。在深入探讨Redis之前,我们先了解下Redis的基本特性。 1. **数据类型**: Redis支持五大数据类型:字符串(String)、哈希(Hash)、列表...

    Redis安装包,Redis-x64-3.0.504 windows版安装包

    Redis安装包,Redis-x64-3.0.504 windows版安装包

    Redis windows下载 Redis-x64-3.2.100.zip

    redis-server --service-install redis.windows-service.conf --loglevel verbose 2 常用的redis服务命令。 卸载服务:redis-server --service-uninstall 开启服务:redis-server --service-start 停止服务:redis-...

    Redis-x64-3.2.100.zip

    redis-serviceinstall .cmd安装成服务脚本(redis设置成windows下的服务,redis-serviceinstall .cmd脚本内容如下) redis-server --service-install redis.windows-service.conf --loglevel verbose redis-server -...

    redis-stack-server 7.2.0 安装包合集

    redis-stack-server-7.2.0-v9.arm64.snap redis-stack-server-7.2.0-v9.bionic.arm64.tar.gz redis-stack-server-7.2.0-v9.bionic.x86_64.tar.gz redis-stack-server-7.2.0-v9.bullseye.x86_64.tar.gz redis-stack-...

    Redis-x64-5.0.14.1

    这个名为"Redis-x64-5.0.14.1"的压缩包是Redis针对Windows操作系统的64位版本,版本号为5.0.14.1。在Windows上运行Redis可能与Linux环境有所不同,但仍然提供了相同的核心功能。 1. **Redis的特性**: - **内存...

    Redis-x64-5.0.14 windows

    在Windows环境下,Redis-x64-5.0.14是Redis为64位Windows操作系统编译的一个版本,提供了在Windows上运行Redis的能力。本文将深入探讨Redis的基本概念、功能特性、安装与配置,以及在Windows平台上的使用方法。 ...

    Redis-x64-5.0.14.1 for Windows

    之前项目中要使用window下的...找了好久都只有Redis-x64-3.2.100的,后来发现有更高版本的。这里附件里面包括Redis-x64-5.0.14.1 for Windows版本 与及 原始下载地址。如果有新的版本的话,可以到在原始下载地址找到。

    Redis-x64-5.0.14.1 缓存程序

    总的来说,Redis-x64-5.0.14.1为Windows用户提供了一种在本地部署和使用Redis的便捷方式,适用于开发、测试和学习Redis的各种功能。其高效、灵活的特性和丰富的数据结构使其在分布式系统、微服务架构中广泛应用。

    Redis-x64-3.0.504安装包

    Redis-x64-3.0.504安装包是一个针对64位操作系统的Redis数据库服务器的安装程序。Redis是一款高性能、开源、基于键值对的数据存储系统,广泛应用于缓存、数据库、消息中间件等多个场景。这个版本是3.0.504,代表着在...

    redis2-nginx-module-0.15

    **Redis2-NGINX-Module 0.15 知识详解** Redis2-NGINX-Module 是一个用于 NGINX Web 服务器的扩展模块,它允许开发者将 NGINX 与 Redis 数据库集成,实现高效的数据缓存和交互。这个版本是 0.15,它提供了一系列...

    redis校验工具redis-full-check

    **Redis 全面检查工具:redis-full-check** Redis 是一款高性能的键值存储系统,广泛应用于缓存、数据库和消息中间件等场景。在实际应用中,为了确保 Redis 的稳定性和数据一致性,需要定期对 Redis 实例进行健康...

    Redis-x64-5.0.14.1.msi

    这个压缩包“Redis-x64-5.0.14.1.msi”显然是 Redis 的 Windows 64 位版本的安装程序,版本号为 5.0.14。下面将详细介绍 Redis 的核心概念、功能以及使用方法。 1. **Redis 简介**:Redis 是 Remote Dictionary ...

    Windows版本Redis-x64-5.0.14安装包

    本篇文章将详细讲解基于标题"Windows版本Redis-x64-5.0.14安装包"的Redis安装过程,以及如何在Windows上配置和使用Redis。 首先,你需要下载Redis的Windows版本,这里提到的是Redis-x64-5.0.14。这个版本适用于64位...

    Redis-x64-5.0.9.zip

    这个“Redis-x64-5.0.9.zip”压缩包包含的是适用于64位操作系统的Redis服务器的5.0.9版本。在本文中,我们将深入探讨Redis的主要特性和功能,以及如何安装和使用这个版本。 1. **Redis的数据类型**: - 字符串...

    flink-connector-redis-2.10-1.1.5-API文档-中文版.zip

    赠送jar包:flink-connector-redis_2.10-1.1.5.jar; 赠送原API文档:flink-connector-redis_2.10-1.1.5-javadoc.jar; 赠送源代码:flink-connector-redis_2.10-1.1.5-sources.jar; 赠送Maven依赖信息文件:flink-...

    Redis-x64-3.0.504.msi.zip

    在Windows环境下,Redis的安装通常以MSI(Microsoft Installer)格式的文件进行,就像提供的"Redis-x64-3.0.504.msi"。这个文件是专门为64位Windows操作系统设计的Redis 3.0.504版本的安装程序。 1. **Redis的基本...

Global site tag (gtag.js) - Google Analytics