Redis内部数据结构详解之整数集合(intset)

整数集合简介 整数集合intset用于有序、无重复地保存多个整数值，根据集合中元素的值自动选择使用整数类型来保存元素，例如：如果intset中绝对值最大的整数可以用int32_t来保存，那么整个intset中所有元素都使用int32_t来保存。 如果当前intset所使用的类型

整数集合简介

整数集合intset用于有序、无重复地保存多个整数值，根据集合中元素的值自动选择使用整数类型来保存元素，例如：如果intset中绝对值最大的整数可以用int32_t来保存，那么整个intset中所有元素都使用int32_t来保存。

如果当前intset所使用的类型不能保存一个即将加入到该intset的新元素时候，需要对intset进行升级，比如新元素的类型是int64_t，而当前intset的类型是int32_t，那么升级就是先将intset中所有元素由int32_t转换为int64_t，然后再插入新元素。

对于int8_t,int32_t,int64_t我个人的理解就应该分别对应char,int,long long，使用int8_t,int32_t,int64_t应该是为了区分平台的差异吧，具体的可以查看stdint.h文件。

整数集合的数据结构

typedef struct intset {
    uint32_t encoding; //所使用类型的长度，4\8\16
    uint32_t length; //元素个数
    int8_t contents[]; //保存元素的数组
} intset;

encoding的值是下面三个常量中的一个：

#define INTSET_ENC_INT16 (sizeof(int16_t))

#define INTSET_ENC_INT32 (sizeof(int32_t))

#define INTSET_ENC_INT64 (sizeof(int64_t))

contents数组用来实际保存数据，数组中元素的特性：无重复元素；元素在数组中递增排列。

整数集合相关API介绍

函数名称	作用	复杂度
_intsetValueEncoding	获取给定整数的编码类型	O(1)
_intsetGet	根据索引获取整数值	O(1)
_intsetSet	根据索引设置给定整数值	O(1)
intsetNew	新建intset	O(1)
intsetResize	为给定的intset重新分配内存	O(1)
intsetSearch	查找给定的整数是否在intset中	O(logN)
intsetUpgradeAndAdd	先升级intset然后插入元素	O(N)
intsetAdd	直接添加元素	O(N)
intsetMoveTail	将intset中元素偏移	O(N)
intsetRemove	删除元素	O(N)
intsetRandom	随机返回一个intset中元素	O(1)
intsetLen	intset中元素的个数	O(1)
intsetBlobLen	intset所占的字节数	O(1)

重要API源码的简单解析

intsetAdd

//添加一个整数
intset *intsetAdd(intset *is, int64_t value, uint8_t *success) {
    uint8_t valenc = _intsetValueEncoding(value); //得到类型的长度
    uint32_t pos;
    if (success) *success = 1;
    /* Upgrade encoding if necessary. If we need to upgrade, we know that
     * this value should be either appended (if > 0) or prepended (if < 0),
     * because it lies outside the range of existing values. */
    //需要升级，那么进行升级并插入新值
    if (valenc > intrev32ifbe(is->encoding)) {
        /* This always succeeds, so we don&#39;t need to curry *success. */
        return intsetUpgradeAndAdd(is,value);
    } else {//否则
        /* Abort if the value is already present in the set.
         * This call will populate "pos" with the right position to insert
         * the value when it cannot be found. */
        //如果该值在集合中已经存在，那么直接返回
        if (intsetSearch(is,value,&pos)) {
            if (success) *success = 0;
            return is;
        }
        is = intsetResize(is,intrev32ifbe(is->length)+1);
        //将从pos位置后面的值全部向后偏移一个位置，为新元素空出位置
        if (pos < intrev32ifbe(is->length)) intsetMoveTail(is,pos,pos+1);
    }
    _intsetSet(is,pos,value);//添加新元素
    is->length = intrev32ifbe(intrev32ifbe(is->length)+1);
    return is;
}

intsetAdd函数添加一个元素value时，首先根据value的字节数与当前intset的encoding进行比较，分析intset是否需要升级，若需要升级则调用intsetUpdateAndAdd函数处理，否则如果value已存在intset中直接pass，不存在，那么先resize，接着将插入位置之后的所有元素向后偏移，添加value。

intsetMoveTail

/**使用memmove对集合进行向后偏移,下标从0开始，并且已经Resize
例:前 | 1 | 2 | 3 | 4 | 5 | 6 |   |   |
    from = 1, to = 3
    length = 6
    src = | 2 | 3 | 4 | 5 | 6 |
    dst = | 4 | 5 | 6 |   |   |
    bytes = 5 * sizeof(...)
   后 | 1 | 2 | 3 | 2 | 3 | 4 | 5 | 6 |
   偏移之前肯定需要用intsetResize函数，进行扩容，增加两个容量
   如果不理解前后的变化，建议查看memmove源码，这里需要考虑到内存覆盖的问题
   也就是为什么必须使用memmove而不能使用memcpy的原因
*/
static void intsetMoveTail(intset *is, uint32_t from, uint32_t to) {
    void *src, *dst;
    uint32_t bytes = intrev32ifbe(is->length)-from;
    uint32_t encoding = intrev32ifbe(is->encoding);
    if (encoding == INTSET_ENC_INT64) {
        src = (int64_t*)is->contents+from;
        dst = (int64_t*)is->contents+to;
        bytes *= sizeof(int64_t);
    } else if (encoding == INTSET_ENC_INT32) {
        src = (int32_t*)is->contents+from;
        dst = (int32_t*)is->contents+to;
        bytes *= sizeof(int32_t);
    } else {
        src = (int16_t*)is->contents+from;
        dst = (int16_t*)is->contents+to;
        bytes *= sizeof(int16_t);
    }
    memmove(dst,src,bytes);
}

intsetUpdateAndAdd

//对编码类型进行升级，O(n)
//需要插入的值，要么比当前集合中的最大值大，要么比集合中的最小值小，不然不需要升级
//比最大值大还是小，只需要根据value的正负即可判断
static intset *intsetUpgradeAndAdd(intset *is, int64_t value) {
    uint8_t curenc = intrev32ifbe(is->encoding); //当前编码类型
    uint8_t newenc = _intsetValueEncoding(value);//新的编码类型
    int length = intrev32ifbe(is->length);
    int prepend = value < 0 ? 1 : 0;//决定新的值插入的位置(1表示头，0表示尾)
    /* First set new encoding and resize */
    is->encoding = intrev32ifbe(newenc); //设置编码类型
    is = intsetResize(is,intrev32ifbe(is->length)+1);//resize

    /* Upgrade back-to-front so we don&#39;t overwrite values.
     * Note that the "prepend" variable is used to make sure we have an empty
     * space at either the beginning or the end of the intset. */
    //通过_intsetGetEncoded得到升级前的该位置的整数值
    //设置原来的整数集的值，如果prepend=1表示新值在头插入，那么原来的数值全部向后偏移
    while(length--)
        _intsetSet(is,length+prepend,_intsetGetEncoded(is,length,curenc));

    /* Set the value at the beginning or the end. */
    if (prepend) //在头插入
        _intsetSet(is,0,value);
    else //在尾插入
        _intsetSet(is,intrev32ifbe(is->length),value);
    is->length = intrev32ifbe(intrev32ifbe(is->length)+1);
    return is;
}

intsetRemove

//删除一个整数
intset *intsetRemove(intset *is, int64_t value, int *success) {
    uint8_t valenc = _intsetValueEncoding(value);
    uint32_t pos;
    if (success) *success = 0;
    //value在原集合中
    if (valenc <= intrev32ifbe(is->encoding) && intsetSearch(is,value,&pos)) {
        uint32_t len = intrev32ifbe(is->length);

        /* We know we can delete */
        if (success) *success = 1;

        /* Overwrite value with tail and update length */
        //如果 pos 不是 is 的最末尾，直接通过memmove内存覆盖的方式删除该整数值
        //如果是末尾，直接resize删除
        if (pos < (len-1)) intsetMoveTail(is,pos+1,pos);
        is = intsetResize(is,len-1);//将空间缩小
        is->length = intrev32ifbe(len-1);
    }
    return is;
}

intset添加元素流程图

 

小结

intset用于有序、无重复地保存多个整数值，它会根据元素的值，自动选择该用什么长度的整数类型来保存元素；

当添加新元素时，需要判断当前intset的编码类型能否保存新元素，如果不行需要对intset进行升级，升级后的intset中的元素会扩大其占有的字节数，但是值不发生改变；

intset只支持升级，不支持降级，因此相对而言会浪费内存；

intset中元素是有序排列的，因此使用折半查找的时间复杂度为O(logN)。

最后感谢黄健宏（huangz1990）的Redis设计与实现及其他对Redis2.6源码的相关注释对我在研究Redis2.8源码方面的帮助。