基本介绍

当一个集合中只包含整数，并且元素的个数不是很多的话，redis 会用整数集合作为底层存储，它的一个优点就是可以节省很多内存，虽然字典结构的效率很高，但是它的实现结构相对复杂并且会分配较多的内存空间。
而我们的整数集合（intset）可以做到使用较少的内存空间却达到和字典一样效率的实现，但也是前提的，集合中只能包含整型数据并且数量不能太多。整数集合最多能存多少个元素在 redis 中也是有体现的。

intset中元素是有序排列的
查找效率是O(logn)

代码结构

typedef struct intset {
    uint32_t encoding; // encoding 记录当前 intset 使用编码，有三个取值
    uint32_t length;     // length 记录整数集合中目前存储了多少个元素
    int8_t contents[];   // contents 记录我们实际的数据集合
} intset;

encoding 记录当前 intset 使用编码，有三个取值：

#define INTSET_ENC_INT16 (sizeof(int16_t))
#define INTSET_ENC_INT32 (sizeof(int32_t))
#define INTSET_ENC_INT64 (sizeof(int64_t))

主要接口

intset *intsetNew(void); //初始化
intset *intsetAdd(intset *is, int64_t value, uint8_t *success); //添加元素
intset *intsetRemove(intset *is, int64_t value, int *success); //删除元素
uint8_t intsetFind(intset *is, int64_t value); //
int64_t intsetRandom(intset *is);
uint8_t intsetGet(intset *is, uint32_t pos, int64_t *value);
uint32_t intsetLen(const intset *is);
size_t intsetBlobLen(intset *is);
int intsetValidateIntegrity(const unsigned char *is, size_t size, int deep);

初始化

插入元素

取元素

intset取元素纯靠memcpy，牛批

static int64_t _intsetGetEncoded(intset *is, int pos, uint8_t enc) {
    int64_t v64;
    int32_t v32;
    int16_t v16;

    if (enc == INTSET_ENC_INT64) {
        memcpy(&v64,((int64_t*)is->contents)+pos,sizeof(v64));
        memrev64ifbe(&v64); //大小端转化
        return v64;
    } else if (enc == INTSET_ENC_INT32) {
        memcpy(&v32,((int32_t*)is->contents)+pos,sizeof(v32));
        memrev32ifbe(&v32);
        return v32;
    } else {
        memcpy(&v16,((int16_t*)is->contents)+pos,sizeof(v16));
        memrev16ifbe(&v16);
        return v16;
    }
}

升级

如果新加的元素比现在的编码长，就需要升级了，比如现在有4个int16的数据，新加入一个int32的数据，就要进行升级，要分配5个int32的空间，然后移动元素位置
原 intset 结构如下：

image.png

新 intset 结构会扩容成这样：

image.png

虽然数据占用的内存已经分配好了，但是还需要做的是迁移每个元素占用的比特位。
做法是这样的，假设我们的新元素是 int_32 类型的数值 65536，那么首先我们会将这个 65536 放到[128-159]比特位区间，然后将 78 放到[96-127]比特位区间，并向前以此类推，最后我们会得到升级完成之后 intset。

最后看看代码, 写在注释里

/* Upgrades the intset to a larger encoding and inserts the given integer. */
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; //value小于0就是1.value大于0是0，
                                                      //这是为了负数就插入最前面，正数插入最后面

    /* First set new encoding and resize */
    is->encoding = intrev32ifbe(newenc); // 改变编码
    is = intsetResize(is,intrev32ifbe(is->length)+1); //调用zrealloc()重新分配空间

    /*从后往前分配，就不会内存覆盖*/
    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;
}

小技巧

判断数据是int16/32/64

static uint8_t _intsetValueEncoding(int64_t v) {
    if (v < INT32_MIN || v > INT32_MAX)
        return INTSET_ENC_INT64;
    else if (v < INT16_MIN || v > INT16_MAX)
        return INTSET_ENC_INT32;
    else
        return INTSET_ENC_INT16;
}

参考：https://juejin.cn/post/6844903974231883790

6.intset——redis基础数据结构之整数集合