随遇而安Inset基础
Redis会使用Intset来存储一些数量不太多，且都为符合条件的整数数据，实现如下，intset.h/inset：
typedef struct intset {
uint32_t encoding;
uint32_t length;
int8_t contents[];
} intset;
具体解释如下：
- encoding，用于存储Intset的编码类型，目前intset支持int16_t、int32_t、int64_t的整数类型。在intset.c给出了类型的定义：
#define INTSET_ENC_INT16 (sizeof(int16_t)) #define INTSET_ENC_INT32 (sizeof(int32_t)) #define INTSET_ENC_INT64 (sizeof(int64_t)) - length，代表intset中存储元素的个数。
- contents，代表实际存储元素的地方。contents数组中元素不会重复，并且是由小到大进行排列的。
这个结构体里面有一处迷惑读者的地方，就是int8_t contents[]，这里面int8_t仅起到占位符的作用，当创建的时，会创建一个INTSET_ENC_INT16类型的Intset，具体实现函数如下，inset.c#intsetNew()：
intset *intsetNew(void) {
intset *is = zmalloc(sizeof(intset));
is->encoding = intrev32ifbe(INTSET_ENC_INT16);
is->length = 0;
return is;
}
Intset升级
如果当前Intset的编码类型是INTSET_ENC_INT16，但是我们插入了一个范围在[-2^32 – 1,2^32]内的整数，Redis会对Intset执行升级操作，将intset的编码更是更新为INTSET_ENC_INT32，并对之前存储的数据进行内存重分配，具体实现函数如下，intset.c#intsetUpgradeAndAdd：
static intset *intsetUpgradeAndAdd(intset *is, int64_t value) {
uint8_t curenc = intrev32ifbe(is->encoding);
uint8_t newenc = _intsetValueEncoding(value);
int length = intrev32ifbe(is->length);
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));
if (prepend)
_intsetSet(is,0,value);
else
_intsetSet(is,intrev32ifbe(is->length),value);
is->length = intrev32ifbe(intrev32ifbe(is->length)+1);
return is;
}
具体解释如下：
- 获取当前的编码类型和需要更新到的编码类型；
- 获取当前intset的长度。
- 计算插入的值应该存放的位置。如果value小于0，则放在队首；否则，放在队尾。
- 更新intset的编码格式，同时进行扩容。
- 根据length游标，从队尾到队首一次进行数组元素的内存重分配。
- 根据存放的位置，将value添加到intset中去。
- 更新intset的长度。
- 返回intset，升级结束。
Intset查找
如果Redis向intset中添加值时，没有引发升级动作，那么将进入常规查找模式，具体实现函数代码如下，intset.c#intsetAdd()：
intset *intsetAdd(intset *is, int64_t value, uint8_t *success) {
uint8_t valenc = _intsetValueEncoding(value);
uint32_t pos;
if (success) *success = 1;
if (valenc > intrev32ifbe(is->encoding)) {
return intsetUpgradeAndAdd(is,value);
} else {
if (intsetSearch(is,value,&pos)) {
if (success) *success = 0;
return is;
}
is = intsetResize(is,intrev32ifbe(is->length)+1);
if (pos < intrev32ifbe(is->length)) intsetMoveTail(is,pos,pos+1);
}
_intsetSet(is,pos,value);
is->length = intrev32ifbe(intrev32ifbe(is->length)+1);
return is;
}
由于intset中数组的元素是按照从小到大的顺序进行排序的，所以Redis机智的采用了二分查找法进行查找，时间复杂度为O(logn)，具体实现函数代码如下，intset.c#intsetAdd()：
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;
// 校验intset是否为空
if (intrev32ifbe(is->length) == 0) {
if (pos) *pos = 0;
return 0;
} else {
// 校验待插入值是否已经超出了当前intset数组元素中最大值和最小值的的范围
if (value > _intsetGet(is,intrev32ifbe(is->length)-1)) {
if (pos) *pos = intrev32ifbe(is->length);
return 0;
} else if (value < _intsetGet(is,0)) {
if (pos) *pos = 0;
return 0;
}
}
// 二分查找法
while(max >= min) {
mid = ((unsigned int)min + (unsigned int)max) >> 1;
cur = _intsetGet(is,mid);
if (value > cur) {
min = mid+1;
} else if (value < cur) {
max = mid-1;
} else {
break;
}
}
// 校验是否已存在数据
if (value == cur) {
if (pos) *pos = mid;
return 1;
} else {
if (pos) *pos = min;
return 0;
}
}
具体解释如下：
- 判断intset是否为空，或是待插入值是否介于当前intset数组元素最小值~最大值范围之内。
- 二分查找，进行偏移。
- 将索引赋值给待插入位置指针。
内存偏移
intset在插入或者移除元素时，为了保证内存的连续性，会进行内存的扩张和收缩，具体实现函数如下，intset.c#intsetUpgradeAndAdd()：
static intset *intsetUpgradeAndAdd(intset *is, int64_t value) {
uint8_t curenc = intrev32ifbe(is->encoding);
uint8_t newenc = _intsetValueEncoding(value);
int length = intrev32ifbe(is->length);
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));
if (prepend)
_intsetSet(is,0,value);
else
_intsetSet(is,intrev32ifbe(is->length),value);
is->length = intrev32ifbe(intrev32ifbe(is->length)+1);
return is;
}
具体解释如下：
- 首先获取当前编码格式和待插入值的编码格式。
- 如果value的值小于0，那么它将被放在最前端，如果大于0，那么就放在队尾。
- 更新intset的编码方式，并根据编码方式，重新设置intset所需内存大小。
- 然后根据索引由后向前，依次遍历增加内存分配。
- 插入待插入的值。
- intset元素数量变更。
