intset应用

• Redis在这种小数据量的条件下，会使用内存映射来代替内部数据结构。这就使得整数集合（intset）和压缩（ziplist）这两类节省内存的数据结构应运而生了
• 整数集合是集合键的底层实现之一，当一个集合只包含整数值元素，并且这个集合的元素数量不多时，Redis 就会使用整数集合作为集合键的底层实现
• 整数集合的底层实现为数组，这个数组有序、无重复的方式保存集合元素，在有需要时，程序会根据新添元素的类型，改变这个数组的类型
• 整数集合只支持升级操作，不支持降级操作

intset的数据结构

如果一个集合满足只保存整数元素和元素数量不多这两个条件，那么Redis就会采用intset来保存这个数据集

typedef struct intset {
    uint32_t encoding; // 编码模式
    uint32_t length; // 集合包含的元素数量
    int8_t contents[]; // 保存元素的数组
} intset;

其中，encoding字段表示该整数集合的编码模式，Redis提供三种模式的宏定义
// 可以看出，虽然contents部分指明的类型是int8_t，但是数据并不以这个类型存放
// 数据以int16_t类型存放，每个占2个字节，能存放-32768~32767范围内的整数
#define INTSET_ENC_INT16 (sizeof(int16_t)) 
// 数据以int32_t类型存放，每个占4个字节，能存放-2^32-1~2^32范围内的整数
#define INTSET_ENC_INT32 (sizeof(int32_t)) 
// 数据以int64_t类型存放，每个占8个字节，能存放-2^64-1~2^64范围内的整数
#define INTSET_ENC_INT64 (sizeof(int64_t)) 

• length字段用来保存集合中元素的个数
• contents字段用于保存整数，数组中的元素要求不含有重复的整数且按照从小到大的顺序排列。在读取和写入的时候，均按照指定的encoding编码模式读取和写入

升级

• 当intset中添加的整数超过当前编码类型的时候，intset会自定升级到能容纳该整数类型的编码模式
• Redis提供intsetUpgradeAndAdd函数来对整数集合进行升级然后添加数据
• 返回值：添加新元素之后的整数集合
• 根据值 value 所使用的编码方式，对整数集合的编码进行升级，并将值 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);
    // 根据 value 的值，决定是将它添加到底层数组的最前端还是最后端
    // 注意，因为 value 的编码比集合原有的其他元素的编码都要大
    // 所以 value 要么大于集合中的所有元素，要么小于集合中的所有元素
    // 因此，value 只能添加到底层数组的最前端或最后端
    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));
    // 设置新值，根据 prepend 的值来决定是添加到数组头还是数组尾
    if (prepend)
        _intsetSet(is,0,value);
    else
        _intsetSet(is,intrev32ifbe(is->length),value);
    // 更新整数集合的元素数量
    is->length = intrev32ifbe(intrev32ifbe(is->length)+1);
    return is;
}

inset基本操作

1. 创建intset
   Redis在创建intset集合时，默认采用int16_t编码格式

intset *intsetNew(void) {
    intset *is = zmalloc(sizeof(intset));
    is->encoding = intrev32ifbe(INTSET_ENC_INT16);
    is->length = 0;
    return is;
}

2. 添加元素
   intset在添加元素时需要判断新数据的大小，如果超出原编码格式能表示的范围，则调用上面的intsetUpgradeAndAdd函数进行添加，如果没有超出，则直接添加到指定位置

/*
 尝试将元素 value 添加到整数集合中。
 success 的值指示添加是否成功：
 如果添加成功，那么将 *success 的值设为 1 。
 因为元素已存在而造成添加失败时，将 *success 的值设为 0 。
 T = O(N)
 */

intset *intsetAdd(intset *is, int64_t value, uint8_t *success) {
    // 计算编码 value 所需的长度
    uint8_t valenc = _intsetValueEncoding(value);
    uint32_t pos;
    // 默认设置插入为成功
    if (success) *success = 1;
    // 如果 value 的编码比整数集合现在的编码要大
    // 那么表示 value 必然可以添加到整数集合中
    // 并且整数集合需要对自身进行升级，才能满足 value 所需的编码
    if (valenc > intrev32ifbe(is->encoding)) {
        /* This always succeeds, so we don't need to curry *success. */
        // T = O(N)
        return intsetUpgradeAndAdd(is,value);
    } else {
        // 运行到这里，表示整数集合现有的编码方式适用于 value
        // 在整数集合中查找 value ，看他是否存在：
        // - 如果存在，那么将 *success 设置为 0 ，并返回未经改动的整数集合
        // - 如果不存在，那么可以插入 value 的位置将被保存到 pos 指针中
        //   等待后续程序使用
        if (intsetSearch(is,value,&pos)) {
            if (success) *success = 0;
            return is;
        }

        // 运行到这里，表示 value 不存在于集合中
        // 程序需要将 value 添加到整数集合中
        // 为 value 在集合中分配空间
        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;
}
/* 
 *在集合 is 的底层数组中查找值 value 所在的索引。
 * 成功找到 value 时，函数返回 1 ，并将 *pos 的值设为 value 所在的索引
 * 当在数组中没找到 value 时，返回 0 。
 * 并将 *pos 的值设为 value 可以插入到数组中的位置。
 * T = O(log N)
 */
static uint8_t intsetSearch(intset *is, int64_t value, uint32_t *pos) {
    int min = 0, max = intrev32ifbe(is->length)-1, mid = -1;
    int64_t cur = -1;
    // 处理 is 为空时的情况
    if (intrev32ifbe(is->length) == 0) {
        if (pos) *pos = 0;
        return 0;
    } else {

        // 因为底层数组是有序的，如果 value 比数组中最后一个值都要大
        // 那么 value 肯定不存在于集合中，
        // 并且应该将 value 添加到底层数组的最末端
        if (value > _intsetGet(is,intrev32ifbe(is->length)-1)) {
            if (pos) *pos = intrev32ifbe(is->length);
            return 0;
        // 因为底层数组是有序的，如果 value 比数组中最前一个值都要小
        // 那么 value 肯定不存在于集合中，
        // 并且应该将它添加到底层数组的最前端
        } else if (value < _intsetGet(is,0)) {
            if (pos) *pos = 0;
            return 0;
        }
    }

    // 在有序数组中进行二分查找
    // T = O(log N)
    while(max >= min) {
        mid = (min+max)/2;
        cur = _intsetGet(is,mid);
        if (value > cur) {
            min = mid+1;
        } else if (value < cur) {
            max = mid-1;
        } else {
            break;
        }
    }
    // 检查是否已经找到了 value
    if (value == cur) {
        if (pos) *pos = mid;
        return 1;
    } else {
        if (pos) *pos = min;
        return 0;
    }
}
 //向前或先后移动指定索引范围内的数组元素
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);
    // 根据编码格式做相应处理
    // src为待移动内存的初始位置
    // dst为需要移动到的内存块的初始位置
    // bytes为需要移动的字节数
    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);
}

3. 移除数据

intset *intsetRemove(intset *is, int64_t value, int *success) {
    // 计算 value 的编码方式
    uint8_t valenc = _intsetValueEncoding(value);
    uint32_t pos;
    // 默认设置标识值为删除失败
    if (success) *success = 0;
    // 当 value 的编码大小小于或等于集合的当前编码方式（说明 value 有可能存在于集合）
    // 并且 intsetSearch 的结果为真，那么执行删除
    // T = O(log N)
    if (valenc <= intrev32ifbe(is->encoding) && intsetSearch(is,value,&pos)) {
        // 取出集合当前的元素数量
        uint32_t len = intrev32ifbe(is->length);
        // 设置标识值为删除成功
        if (success) *success = 1;
        // 如果 value 不是位于数组的末尾
        // 那么需要对原本位于 value 之后的元素进行移动
        if (pos < (len-1)) intsetMoveTail(is,pos+1,pos);
        // 缩小数组的大小，移除被删除元素占用的空间
        // T = O(N)
        is = intsetResize(is,len-1);
        // 更新集合的元素数量
        is->length = intrev32ifbe(len-1);
    }
    return is;
}

4. 总结
   整数集合intset的底层实现为数组，该数组中的元素有序、无重复的存放，为了更好的节省内存，intset提供了升级操作，但是不支持降级操作