Redis之整数集合
2021-08-21 本文已影响0人
slxixiha
整数集合的使用场景
整数集合时集合键的底层实现之一,当一个集合只包含数值元素,并且这个集合的元素数量不多时,Redis就会使用整数集合作为集合键的底层实现。
整数集合的定义
其实就是一个功能上类似std::set<int>的东西,排列有序且不支持重复,但是内部居然是数组,而且不预留空间,有点奇葩。
typedef struct intset {
uint32_t encoding;
uint32_t length;
int8_t contents[];
} intset;
intset.encoding:intset的实际数据格式,存在以下定义:
/* Note that these encodings are ordered, so:
* INTSET_ENC_INT16 < INTSET_ENC_INT32 < INTSET_ENC_INT64. */
#define INTSET_ENC_INT16 (sizeof(int16_t))
#define INTSET_ENC_INT32 (sizeof(int32_t))
#define INTSET_ENC_INT64 (sizeof(int64_t))
intset.length:content数组包含的元素的数量,按照实际编码格式进行计算
整数集合的结构图
整数集合.PNG升级
当现有元素的编码格式不够存下新元素的数值时,intset会对底层存储进行升级,例如将Int16升级成Int32。
升级代码如下:
/* Return the required encoding for the provided value. */
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;
}
/* Upgrades the intset to a larger encoding and inserts the given integer. */
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;
/* First set new encoding and resize */
is->encoding = intrev32ifbe(newenc);
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. */
while(length--)
_intsetSet(is,length+prepend,_intsetGetEncoded(is,length,curenc));
/* Set the value at the beginning or the end. */
if (prepend)
_intsetSet(is,0,value);
else
_intsetSet(is,intrev32ifbe(is->length),value);
is->length = intrev32ifbe(intrev32ifbe(is->length)+1);
return is;
}
- 根据新元素的类型,扩展整数集合底层数组的大小,并为新元素分配空间;
- 将现有数据都转换成新元素的类型,并调整元素的位置;
- 添加新元素(只会在头和尾部插入);
注意:只支持升级,不支持降级。