结构

整数集合 intset 主要在底层用来保存一系列整数类型的有序数字，这些整数的类型可以是 int16_t，int_32t，int64_t 中的任意一种，整数集合中的数据以紧凑格式排列在一段连续的内存空间中，整数集合会根据各自最适合的编码方式，对数据使用尽量少的内存空间进行存储，也避免了原生 C 语言中需要手动对不同整型格式手动进行格式转换的问题。

intset 结构体的定义在https://github.com/redis/redis/blob/7.2.4/src/intset.h#L35：

typedef struct intset {
    uint32_t encoding;
    uint32_t length;
    int8_t contents[];
} intset;

• encoding：记录 contents 数组中保存的整数的具体类型，分别有以下几种格式：
  • INTSET_ENC_INT16：表示存储 int16_t 类型的整数，范围在：-32678~32676
  • INTSET_ENC_INT32：表示存储了 int32_t 类型的整数，范围在：-2147483648~2147483647
  • INTSET_ENC_INT64：表示存储 int64_t 类型的整数，范围在：-9223372036854775808~9223372036854775807
• length：记录 contents 数组的长度
• contents[]：具体存储的整数值的列表

可以看出 intset 的结构和 SDS 是有一定的相似性，通过维护 length 字段，获取数组长度的复杂度降为 O(1)，通过 encoding 字段，统一维护数组列表的编码，方便内部在合适的时候对整数的类型进行格式转换。

升级

Redis 设计 intset 的初衷是为了尽可能小的为一系列的整数数组分配内存，如果一个整数集合中开始保存的是占用位数较小类型的整数，后续如果对集合加入编码较长的整数时候，intset 集合会把集合中保存的所有整数都转换成编码较长的格式，这个过程就是整数集合的升级过程。

比如：一个 intset 的初始编码格式 encoding=INTSET_ENC_INT16 ，那么这个集合中原有的整数都是按照16位的长度来分配内存的，后续如果向集合中添加一个 int32_t 格式的整数时候，按照旧的分配内存的规则不能满足新数据的存储，这时候整数集合就会先把所有保存的 int16_t 数字类型转换成 int32_t，并重新分配合适的内存，然后再加入新的 int32_t 数字到集合中。

源码中 intsetAdd() 函数用来对整数集合进行插入操作：

intset *intsetAdd(intset *is, int64_t value, uint8_t *success) {
    // 获取新插入数值对应的编码类型
    uint8_t valenc = _intsetValueEncoding(value);
    uint32_t pos;
    if (success) *success = 1;

    // 如果新加入数值的编码类型不满足当前集合的编码，开始升级操作
    if (valenc > intrev32ifbe(is->encoding)) {
        // 执行集合升级操作并加入
        return intsetUpgradeAndAdd(is,value);
    } else {
        // 集合中已经存在，则直接返回
        if (intsetSearch(is,value,&pos)) {
            if (success) *success = 0;
            return is;
        }

        is = intsetResize(is,intrev32ifbe(is->length)+1);
        if (pos < intrev32ifbe(is->length)) intsetMoveTail(is,pos,pos+1);
    }

    // 编码类型可以满足，就正常插入
    _intsetSet(is,pos,value);
    is->length = intrev32ifbe(intrev32ifbe(is->length)+1);
    return is;
}

具体看一下执行升级操作的函数 intsetUpgradeAndAdd(is,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;

    // 更新编码格式并分配内存空间
    is->encoding = intrev32ifbe(newenc);
    is = intsetResize(is,intrev32ifbe(is->length)+1);

    // 从尾到头开始对旧的数值按照新的编码重新加入集合
    while(length--)
        _intsetSet(is,length+prepend,_intsetGetEncoded(is,length,curenc));

    //对新节点插入集合头部或者尾部
    if (prepend)
        _intsetSet(is,0,value);
    else
        _intsetSet(is,intrev32ifbe(is->length),value);
    is->length = intrev32ifbe(intrev32ifbe(is->length)+1);
    return is;
}

集合升级时候之所以要从尾到头逆向遍历插入，是因为升级操作的对象还是在原来的内存空间上进行，新分配的内存是在原来集合的尾部，如果正向遍历操作，就会用前面的数字覆盖掉末尾部分的内容，相反如果逆向遍历，每次都会把尾部的数据重新放到新的尾部空间，不会出现数据被覆盖的情况。

与升级情况相对，如果后续 intset 中删除元素后如果当前集合的编码格式“过长”，整数集合却不会对集合进行“降级”的操作，这么做是为了防止后续如果再次插入长类型的数值时候重新对集合升级。

由于升级操作的存在，对整数集合添加元素的时间复杂度最坏是 O(N) 级别的。

查询

由于 intset 中 contents 数组中保存的内容是按照顺序排列在内存中的，因而 redis 中 intset 的查询操作可以通过二分查找的方法来完成，intset 的查询操作时间复杂度是 O(logN) 级别：

static uint8_t intsetSearch(intset *is, int64_t value, uint32_t *pos) {
    ...
    // 这里通过头尾获取的最大位置值和最小位置值开始二分查找
    while(max >= min) {
        // 通过位运算获取中间位置
        mid = ((unsigned int)min + (unsigned int)max) >> 1;
        cur = _intsetGet(is,mid);
        if (value > cur) {
            min = mid+1;
        } else if (value < cur) {
            max = mid-1;
        } else {
            break;
        }
    }
    ...
}