inset.c/inset.h
1 | typedef struct intset { |
length记录了整数集合中包含的元素个数，即contents数组的长度。
contents数组是整数集合的底层实现，整数集合中的一个元素就是contents数组的一个元素，其中的元素都是按照数值从小到大排序的，并且元素不重复。虽然contents数组被定义为int8_t类型，但其中的元素类型取决于encoding。
inset是Redis中的整数集合数据结构，只允许保存整数值。
inset之所以有三种表示编码格式的宏定义，是因为根据存储元素数值的大小，能够选取一个最“合适”的类型存储，既能够表示元素的大小，又可以节省空间。当插入的新元素编码要大于当前集合编码格式，则需要进行升级操作。
升级步骤主要分成三步：
- 根据新元素的类型，扩展整数集合的底层数组空间大小。
- 将底层数组中的元素全部转换成跟新元素一样的类型，并从后向前将元素放到相应的位置，保证跟原有顺序一样。
- 将新元素加入到底层数组中。如果因为加入新元素而导致类型调整，则新加入的元素只会在数组的开头或结尾处。
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
31static 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);
// 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;
}
这样升级的特点：
- 提高灵活性：通过自动升级底层数组来适应不同类型的新元素，不需要担心类型错误。
- 节约内存：整数集合即可以让集合保存三种不同类型的值，又可以确保升级操作只在需要的时候进行
- 不支持降级：一旦对数据进行升级后，编码就会一直保存升级后的状态。
添加或删除元素。在向底层数组中插入或删除新元素时，因为不会导致底层数组的类型变换，所以只需要计算出申请或清除固定的数组空间，进行整体移动后，再进行添加或删除操作。下面就是进行整体移动的函数：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
27static 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 = (Enc_t*)is->contents+from 记录移动开始的位置
// dst = (Enc_t*)is_.contents+to 记录移动结束的位置
// bytes *= sizeof(Enc_t) 计算一共要移动多少字节
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);
}
// 进行移动
// T = O(N)
memmove(dst,src,bytes);
}
1 | ### API |