Redis 整数集合

整数集合是 Redis 用于保存整数值的有序的集合抽象数据结构，当一个集合只包含整数值元素，并且这个集合的元素数量不多时，Redis 就会使用整数集合作为集合键的底层实现。
它可以保存类型为int16_t，int32_t或者int64_t的整数值，并且保证集合中不会出现重复元素。

127.0.0.1:6379> SADD number 1 3 5 7 9
(integer) 5
127.0.0.1:6379> OBJECT ENCODING number
"intset"

整数集合的实现

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

• length 记录了整数集合包含的元素数量。
• contents 数组是整数集合的底层实现，整数集合的每个元素都是contents数组的一个数组项，虽然声明为int8_t类型的值，但是contents数组的真正类型取决于encoding属性的值。

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

  如果encodeing 属性的值为INTSET_ENC_INT16，那么contents就是一个int16_t类型的数值。其他以此类推。

intsetNew

intset *intsetNew(void) 
{
    // 为整数集合结构分配空间
    intset *is = zmalloc(sizeof(intset));  // 8 bytes
    // 设置初始编码
    is->encoding = intrev32ifbe(INTSET_ENC_INT16);
    // 初始化元素数量
    is->length = 0;

    return is;
}

image.png

升级

在插入元素时，新元素的类型比整数集合所有现有的元素的类型都要长时，整数集合需要先进行升级，然后才能将新元素添加到整数集合中。

升级整数集合并添加新元素分为3步进行：

• 根据新元素的类型，扩展整数集合底层数组的空间大小。
• 将底层数组现有的所有元素都转换成新元素相同的类型，并将类型转换后的元素放置到正确位上，而且在放置元素过程中，需要维持底层数组的有序性质不变。
• 将新元素添加到底层数组里面。

image.png

static intset *intsetUpgradeAndAdd(intset *is, int64_t value) 
{
    // 当前的编码方式
    uint8_t curenc = intrev32ifbe(is->encoding);
    // 新值所需的编码方式，_intsetValueEncoding 按照value的范围判断
    uint8_t newenc = _intsetValueEncoding(value);
    // 当前集合的元素数量
    int length = intrev32ifbe(is->length);

    // 根据 value 的值，决定是将它添加到底层数组的最前端还是最后端
    // 注意，因为 value 的编码比集合原有的其他元素的编码都要大
    // 所以 value 要么大于集合中的所有元素，要么小于集合中的所有元素
    // 因此，value 只能添加到底层数组的最前端或最后端
    int prepend = value < 0 ? 1 : 0;

    // 根据新编码对集合（的底层数组）进行空间调整，T = O(N)
    is = intsetResize(is,intrev32ifbe(is->length)+1);
    
    while(length--)
        _intsetSet(is,length+prepend,_intsetGetEncoded(is,length,curenc));
    
    // 设置新值，根据 prepend 的值来决定是添加到数组头还是数组尾
    prepend ? _intsetSet(is,0,value) : _intsetSet(is,intrev32ifbe(is->length),value);
    
    // 更新整数集合的元素数量
    is->length = intrev32ifbe(intrev32ifbe(is->length)+1);

    return is;
}

• 升级的好处
  • 提升灵活性
    因为整数集合可以通过自动升级底层数组来适应新元素，所以可以随意的将类型的整数添加到集合中。
  • 节约内存
  • 升级之后不存在降级，一旦对数组进行了升级，编码就会一直保持升级后的状态。

intsetAdd

因为每次向整数集合添加元素都可能会引起升级，而每次升级都需要对底层数组中已有的元素进行类型转换。所以向整数集合中添加新元素的时间复杂度为o(N)。

intset *intsetAdd(intset *is, int64_t value, uint8_t *success)
{
    uint8_t valenc = _intsetValueEncoding(value);
    uint32_t pos;
    // 如果 value 的编码比整数集合现在的编码要大，需要升级
    if (valenc > intrev32ifbe(is->encoding)) {
        return intsetUpgradeAndAdd(is,value);
    } 
    else {
        // 在整数集合中查找 value ，看他是否存在：
        // 如果存在，那么将 *success 设置为 0 ，并返回未经改动的整数集合
        // 如果不存在，那么可以插入 value 的位置将被保存到 pos 指针中
        if (intsetSearch(is,value,&pos)) {
            if (success) *success = 0;
            return is;
        }
        // 为 value 在集合中分配空间
        is = intsetResize(is,intrev32ifbe(is->length)+1);
        // 如果新元素不是被添加到底层数组的末尾
        // 那么需要对现有元素的数据进行移动，空出 pos 上的位置，用于设置新值
        // | x | y | z | ? |
        //     |<----->|
        // 而新元素 n 的 pos 为 1 ，那么数组将移动 y 和 z 两个元素
        // | x | y | y | z |
        //         |<----->|
        // 这样就可以将新元素设置到 pos 上了：
        // | x | n | y | z |
        if (pos < intrev32ifbe(is->length))
            intsetMoveTail(is,pos,pos+1);
    }
    // 将新值设置到底层数组的指定位置中
    _intsetSet(is,pos,value);

    // 增一集合元素数量的计数器
    is->length = intrev32ifbe(intrev32ifbe(is->length)+1);

    // 返回添加新元素后的整数集合
    return is;
}

假设执行SADD numbers 1

image.png

intsetRemove

intsetFind

检查给定值是否存在于集合中，因为底层数组有序，可通过二分查找，事件复杂度位O(logN)。

/*
 * 检查给定值 value 是否集合中的元素。
 * 是返回 1 ，不是返回 0 。
 * T = O(log N) (二分查找)
*/
uint8_t intsetFind(intset *is, int64_t value) 
{
    // 计算 value 的编码
    uint8_t valenc = _intsetValueEncoding(value);

    // 如果 value 的编码大于集合的当前编码，那么 value 一定不存在于集合
    // 当 value 的编码小于等于集合的当前编码时，
    // 才再使用 intsetSearch 进行查找
    return valenc <= intrev32ifbe(is->encoding) && intsetSearch(is,value,NULL);
}

intsetGet

uint8_t intsetGet(intset *is, uint32_t pos, int64_t *value) 
{
    // pos < intrev32ifbe(is->length) 
    // 检查 pos 是否符合数组的范围
    if (pos < intrev32ifbe(is->length)) {

        // 保存值到指针
        *value = _intsetGet(is,pos);

        // 返回成功指示值
        return 1;
    }

    // 超出索引范围
    return 0;
}

其他辅助函数

• _intsetValueEncoding
  返回适用于传入值 v 的编码方式，T = O(1)。

  //  返回适用于传入值 v 的编码方式
  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;
  }