整数集合(intset)是集合键的底层实现之一，当一个集合只包含整数值元素，并且这个集合的元素数量不多时，Redis就会使用整数集合作为集合键的底层实现。
1. 定义
整数集合(intset)是Redis用于保存整数值的集合抽象数据结构，它可以保存类型为int16_t、int32_t或者int64_t的整数值，并且保证集合中不会出现重复元素。
每个intset.h/intset结构表示一个整数集合：
typedef struct intset {
// 编码方式
uint32_t encoding;
// 集合包含的元素数量
uint32_t length;
// 保存元素的数组，数组里的元素不会重复，并按照从小到大排序
int8_t contents[];
} intset;
image
2. 升级
每当我们将一个新元素添加到整数集合时，并且这个新元素比原有的元素的类型都长时，整数集合需要进行升级，然后才能将新元素添加到整数集合里面。
升级整数集合并添加新元素共分为三步进行：
- 根据新元素的类型，扩展整数集合底层数组的空间大小，并为新元素分配空间。
- 将底层数组现有的所有元素都转换成与新元素相同的类型，并将类型转换后的元素放置到正确的位上，而且在放置元素的过程中，需要继续维持底层数组的有序性质不变。
- 将新元素添加到底层数组里面。
2.1 升级之后新元素的位置
因为引发升级的新元素的长度总是比整数集合现有元素的长度都大，所以这个新元素的值要么就大于所有现有元素，要么就小于所有现有元素。
- 在新元素小于所有现有元素的情况下，新元素会被放置在底层数组的最开头(索引0);
- 在新元素大于所有现有元素的情况下，新元素会被放置在底层数组的最末尾(索引length-1)。
3. 升级的好处
提升灵活性与节约内存
3.1 提升灵活性
因为C语言是静态类型语言，为了避免类型错误，我们通常不会将两种不同类型的值放在同一个数据结构里面。因为整数集合可以升级的特性，我们可以将任意类型的元素放入集合中，不用担心类型错误的问题。
3.2 节约内存
整数集合的做法可以让集合能同时保存多种不同类型的值，又可以确保升级操作只会在有需要的时候进行，节省内存。
4. 降级
整数集合不支持降级操作，一旦对数组进行了升级，编码就会一直保存升级后的状态。
5. 源码
5.1 intsetNew 创建一个新的压缩列表
/* Create an empty intset.
*
* 创建并返回一个新的空整数集合
*
* T = O(1)
*/
intset *intsetNew(void) {
// 为整数集合结构分配空间
intset *is = zmalloc(sizeof(intset));
// 设置初始编码
is->encoding = intrev32ifbe(INTSET_ENC_INT16);
// 初始化元素数量
is->length = 0;
return is;
}
5.2 intsetAdd 将给定元素添加到整数集合里面
/* Insert an integer in the intset
*
* 尝试将元素 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;
/* 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. */
// 如果 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
/* 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. */
// 在整数集合中查找 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 上的位置，用于设置新值
// 举个例子
// 如果数组为：
// | x | y | z | ? |
// |<----->|
// 而新元素 n 的 pos 为 1 ，那么数组将移动 y 和 z 两个元素
// | x | y | y | z |
// |<----->|
// 这样就可以将新元素设置到 pos 上了：
// | x | n | y | z |
// T = O(N)
if (pos < intrev32ifbe(is->length)) intsetMoveTail(is,pos,pos+1);
}
// 将新值设置到底层数组的指定位置中
_intsetSet(is,pos,value);
// 增一集合元素数量的计数器
is->length = intrev32ifbe(intrev32ifbe(is->length)+1);
// 返回添加新元素后的整数集合
return is;
}
/* Upgrades the intset to a larger encoding and inserts the given integer.
*
* 根据值 value 所使用的编码方式，对整数集合的编码进行升级，
* 并将值 value 添加到升级后的整数集合中。
*
* 返回值：添加新元素之后的整数集合
*
* T = O(N)
*/
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;
/* First set new encoding and resize */
// 更新集合的编码方式
is->encoding = intrev32ifbe(newenc);
// 根据新编码对集合（的底层数组）进行空间调整
// T = O(N)
is = intsetResize(is,intrev32ifbe(is->length)+1);
/* Upgrade back-to-front so we don'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. */
// 根据集合原来的编码方式，从底层数组中取出集合元素
// 然后再将元素以新编码的方式添加到集合中
// 当完成了这个步骤之后，集合中所有原有的元素就完成了从旧编码到新编码的转换
// 因为新分配的空间都放在数组的后端，所以程序先从后端向前端移动元素
// 举个例子，假设原来有 curenc 编码的三个元素，它们在数组中排列如下：
// | x | y | z |
// 当程序对数组进行重分配之后，数组就被扩容了（符号 ？ 表示未使用的内存）：
// | x | y | z | ? | ? | ? |
// 这时程序从数组后端开始，重新插入元素：
// | x | y | z | ? | z | ? |
// | x | y | y | z | ? |
// | x | y | z | ? |
// 最后，程序可以将新元素添加到最后 ？ 号标示的位置中：
// | x | y | z | new |
// 上面演示的是新元素比原来的所有元素都大的情况，也即是 prepend == 0
// 当新元素比原来的所有元素都小时（prepend == 1），调整的过程如下：
// | x | y | z | ? | ? | ? |
// | x | y | z | ? | ? | z |
// | x | y | z | ? | y | z |
// | x | y | x | y | z |
// 当添加新值时，原本的 | x | y | 的数据将被新值代替
// | new | x | y | z |
// T = O(N)
while(length--)
_intsetSet(is,length+prepend,_intsetGetEncoded(is,length,curenc));
/* Set the value at the beginning or the end. */
// 设置新值，根据 prepend 的值来决定是添加到数组头还是数组尾
if (prepend)
_intsetSet(is,0,value);
else
_intsetSet(is,intrev32ifbe(is->length),value);
// 更新整数集合的元素数量
is->length = intrev32ifbe(intrev32ifbe(is->length)+1);
return is;
}
5.3 intsetRemove 从整数集合中移除给定元素
/* Delete integer from intset
*
* 从整数集合中删除值 value 。
*
* *success 的值指示删除是否成功：
* - 因值不存在而造成删除失败时该值为 0 。
* - 删除成功时该值为 1 。
*
* T = O(N)
*/
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);
/* We know we can delete */
// 设置标识值为删除成功
if (success) *success = 1;
/* Overwrite value with tail and update length */
// 如果 value 不是位于数组的末尾
// 那么需要对原本位于 value 之后的元素进行移动
//
// 举个例子，如果数组表示如下，而 b 为删除的目标
// | a | b | c | d |
// 那么 intsetMoveTail 将 b 之后的所有数据向前移动一个元素的空间，
// 覆盖 b 原来的数据
// | a | c | d | d |
// 之后 intsetResize 缩小内存大小时，
// 数组末尾多出来的一个元素的空间将被移除
// | a | c | d |
if (pos < (len-1)) intsetMoveTail(is,pos+1,pos);
// 缩小数组的大小，移除被删除元素占用的空间
// T = O(N)
is = intsetResize(is,len-1);
// 更新集合的元素数量
is->length = intrev32ifbe(len-1);
}
return is;
}
5.4 intsetFind 检查给定值是否存在于集合
/* Determine whether a value belongs to this set
*
* 检查给定值 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);
}
/* Search for the position of "value".
*
* 在集合 is 的底层数组中查找值 value 所在的索引。
*
* Return 1 when the value was found and
* sets "pos" to the position of the value within the intset.
*
* 成功找到 value 时，函数返回 1 ，并将 *pos 的值设为 value 所在的索引。
*
* Return 0 when the value is not present in the intset
* and sets "pos" to the position where "value" can be inserted.
*
* 当在数组中没找到 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;
/* The value can never be found when the set is empty */
// 处理 is 为空时的情况
if (intrev32ifbe(is->length) == 0) {
if (pos) *pos = 0;
return 0;
} else {
/* Check for the case where we know we cannot find the value,
* but do know the insert position. */
// 因为底层数组是有序的，如果 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;
}
}
参考资料
- 《Redis设计与实现》
- 《Redis深度历险》
- Redis源码注释版 https://github.com/huangz1990/redis-3.0-annotated
