Redis的intset（整数集合）是一种用于存储整数集合的底层数据结构。它可以保存16位、32位或64位的整数值，并且保证集合中不会出现重复的元素 intset的数据结构定义如下：
ctypedef struct intset {
uint32_t encoding; // 编码方式
uint32_t length; // 集合中包含的元素数量
int8_t contents[]; // 保存元素的数组
} intset;
intset *intsetNew(void);
intset *intsetAdd(intset *is, int64_t value, uint8_t *success);
intset *intsetRemove(intset *is, int64_t value, int *success);
uint8_t intsetFind(intset *is, int64_t value);
int64_t intsetRandom(intset *is);
int64_t intsetMax(intset *is);
int64_t intsetMin(intset *is);
uint8_t intsetGet(intset *is, uint32_t pos, int64_t *value);
uint32_t intsetLen(const intset *is);
size_t intsetBlobLen(intset *is);
int intsetValidateIntegrity(const unsigned char *is, size_t size, int deep);
//************************************************************
// 编码类型
/* Create an empty intset. */
intset *intsetNew(void) {
intset *is = zmalloc(sizeof(intset));
is->encoding = intrev32ifbe(INTSET_ENC_INT16);
is->length = 0;
return is;
}
/* Resize the intset */
static intset *intsetResize(intset *is, uint32_t len) {
uint64_t size = (uint64_t)len*intrev32ifbe(is->encoding);
assert(size <= SIZE_MAX - sizeof(intset));
is = zrealloc(is,sizeof(intset)+size);
return is;
}
/* 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的底层实现是一个有序的数组，数组中的元素按照从小到大的顺序排列，并且数组中不包含重复的元素。数组的类型取决于encoding属性的值，如果encoding为INTSET_ENC_INT16，则数组的类型为int16_t；如果encoding为INTSET_ENC_INT32，则数组的类型为int32_t；如果encoding为INTSET_ENC_INT64，则数组的类型为int64_t
intset的底层实现源码中包含以下几个重要的函数：
_intsetValueEncoding(int64_t v)：根据给定的整数值v，判断其所需的编码方式（INTSET_ENC_INT16、INTSET_ENC_INT32或INTSET_ENC_INT64）
intsetSearch(intset *is, int64_t value, uint32_t *pos)：在intset中查找给定的整数值value，并返回其在数组中的位置pos。该函数使用二分查找算法，时间复杂度为O(logN)
intsetAdd(intset *is, int64_t value, uint8_t *success)：向intset中添加一个整数值value。如果value已经存在于intset中，则success为0；否则，success为1。如果value的编码方式大于当前intset的编码方式，则会进行升级操作。升级操作会重新分配内存，并将原有的元素转换为新的编码方式。如果value的编码方式小于等于当前intset的编码方式，则会将value插入到正确的位置，并调整数组的长度
intsetUpgradeAndAdd(intset *is, int64_t value)：升级intset并添加新的元素value。升级操作会重新分配内存，并将原有的元素转换为新的编码方式。然后，将新的元素value插入到正确的位置，并调整数组的长度
c/* Search for the position of "value". Return 1 when the value was found and
* sets "pos" to the position of the value within the intset. Return 0 when
* the value is not present in the intset and sets "pos" to the position
* where "value" can be inserted. */
// ***********************************************************
// 二分搜索
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 */
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. */
if (value > _intsetGet(is,max)) {
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;
}
}
// ************************************************************************
// 升级
/* 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;
}
// ******************************************************************
//
/* Insert an integer in the intset */
intset *intsetAdd(intset *is, int64_t value, uint8_t *success) {
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. */
// 如果需要升级编码，根据整数的值是正数还是负数，决定是追加还是前置
if (valenc > intrev32ifbe(is->encoding)) {
/* This always succeeds, so we don't need to curry *success. */
// 升级编码，返回新的 intset
return intsetUpgradeAndAdd(is, value);
} else {
/* 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. */
// 如果值已经存在于集合中，中止插入，并返回值的位置
if (intsetSearch(is, value, &pos)) {
if (success) *success = 0; // 插入失败，标记为失败
return is; // 返回原始的 intset，不进行插入操作
}
// 调整 intset 的大小，保证容纳新的元素
is = intsetResize(is, intrev32ifbe(is->length) + 1);
// 将值插入到指定位置，可能需要将后面的元素往后移动
if (pos < intrev32ifbe(is->length)) intsetMoveTail(is, pos, pos + 1);
}
// 在指定位置设置新值
_intsetSet(is, pos, value);
// 更新 intset 的长度
is->length = intrev32ifbe(intrev32ifbe(is->length) + 1);
return is; // 返回插入后的 intset
}
/* Return the value at pos, using the configured encoding. */
// 返回指定位置（pos）的值，使用配置的编码方式
static int64_t _intsetGet(intset *is, int pos) {
return _intsetGetEncoded(is, pos, intrev32ifbe(is->encoding));
}
/* Set the value at pos, using the configured encoding. */
// 设置指定位置（pos）的值，使用配置的编码方式
static void _intsetSet(intset *is, int pos, int64_t value) {
uint32_t encoding = intrev32ifbe(is->encoding); // 获取编码方式
if (encoding == INTSET_ENC_INT64) {
((int64_t*)is->contents)[pos] = value; // 在指定位置设置 64 位整数值
memrev64ifbe(((int64_t*)is->contents) + pos); // 反转字节序，确保字节序正确
} else if (encoding == INTSET_ENC_INT32) {
((int32_t*)is->contents)[pos] = value; // 在指定位置设置 32 位整数值
memrev32ifbe(((int32_t*)is->contents) + pos); // 反转字节序，确保字节序正确
} else {
((int16_t*)is->contents)[pos] = value; // 在指定位置设置 16 位整数值
memrev16ifbe(((int16_t*)is->contents) + pos); // 反转字节序，确保字节序正确
}
}
static void intsetMoveTail(intset *is, uint32_t from, uint32_t to) {
void *src, *dst;
uint32_t bytes = intrev32ifbe(is->length)-from; // 计算需要移动的字节数，从 from 到末尾的长度
uint32_t encoding = intrev32ifbe(is->encoding); // 获取集合的编码方式
if (encoding == INTSET_ENC_INT64) {
src = (int64_t*)is->contents+from; // 源地址，指向需要移动的起始位置
dst = (int64_t*)is->contents+to; // 目标地址，指向移动后的起始位置
bytes *= sizeof(int64_t); // 计算需要移动的字节数，以 64 位整数为单位
} else if (encoding == INTSET_ENC_INT32) {
src = (int32_t*)is->contents+from;
dst = (int32_t*)is->contents+to;
bytes *= sizeof(int32_t); // 计算需要移动的字节数，以 32 位整数为单位
} else {
src = (int16_t*)is->contents+from;
dst = (int16_t*)is->contents+to;
bytes *= sizeof(int16_t); // 计算需要移动的字节数，以 16 位整数为单位
}
memmove(dst, src, bytes); // 使用 memmove 进行内存移动，将数据从源地址复制到目标地址
}
intset的底层实现具有以下优点：
提升灵活性：intset可以自动升级底层数组来适应新的元素类型，因此可以将任意类型的整数值添加到集合中，而不必担心类型错误
节约内存：不同类型的整数值采用不同的编码方式存储，避免了内存的浪费
intset的底层实现在插入和升级操作时可能会进行内存重新分配，因此在使用时需要注意内存的使用情况
参考：
本文作者:yowayimono
本文链接:
版权声明:本博客所有文章除特别声明外，均采用 BY-NC-SA 许可协议。转载请注明出处！