August's Box

Redis设计与实现笔记-章6.整数集合

整数集合(intset)是集合键的底层实现之一(当一个集合只包含整数值元素,并且元素数量不多时,不超过set_max_intset_entries的配置),可以保存int16_tint32_tint64_t的整数值且不会重复。

intset的定义

intset.h/intsetlink
1
2
3
4
5
6
7
8
typedef struct intset {
// 编码方式(INTSET_ENC_INT16,INTSET_ENC_INT32,INTSET_ENC_INT64)
uint32_t encoding;
// 集合包含的元素数量
uint32_t length;
// 保存元素的数组
int8_t contents[];
} intset;
  • intset里用contents数组来保存元素,虽然是按照int8_t来定义的,但是元素的类型取决于encoding。三种encoding类型分别为int16_tint32_tint64_t的大小,所以contents数组的实际大小为encoding*length
  • 各项元素在contents里面是按照从小到大的顺序保存的,当新增的元素类型比当前集合的编码长时,需要对集合进行升级,即将修改当前集合的编码方式并重新排列元素在contents数组里的位置并插入新的元素(所以任意时刻集合里保存的元素类型都是一样的,不存在不同类型存在同一集合中)

intset的升级

当新增的元素比当前编码的数据类型长时,需要进行升级(intsetUpgradeAndAdd

intset.c/intsetUpgradeAndAddlink
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
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;
}

升级的好处: 灵活,不需要关注int类型,统一处理;节约内存,相比于按int64_t来兼容所有int类型。

整数集合相关API

相关api定义在intset.h里,实现在intset.c,主要api如下:

函数 作用和代码逻辑 时间复杂度
intsetNew 创建新的整数集合,分配内存,设置编码默认为INTSET_ENC_INT16 O(1)
intsetAdd 将给定元素添加到整数集合:1. 获取插入值的编码长度,如果大于集合编码长度,进行升级插入 2. 如果插入值已经存在intsetSearch,标记success为0并返回 3. 分配内存,将插入位置pos后的元素后移intsetMoveTail,设置pos位置上的值_intsetSet,并更新length属性 O(N)
intsetRemove 删除整数集合中给定元素:1. 获取删除值的编码长度,如果大于集合编码长度或查找给定元素不存在intsetSearch时,返回并设置success为0 2. 将查找位置pos的元素前移intsetMoveTail,resizeintsetResize和设置length属性 O(N)
intsetFind 查找指定元素是否存在,根据查找元素编码长度和二分查找intsetSearch O(logN)
intsetRandom 从集合中随机返回一个元素 O(1)
intsetGet 返回给定pos上的元素 同上
intsetLen 返回集合长度 O(1),返回length属性
intsetBlobLen 返回集合占用字节数,sizeof(intset)+length*encoding O(1)