#define INTSET_ENC_INT16 (sizeof(int16_t))
#define INTSET_ENC_INT32 (sizeof(int32_t))
#define INTSET_ENC_INT64 (sizeof(int64_t))
typedef struct intset {
uint32_t encoding; /* a */
uint32_t length; /* b */
int8_t contents[]; /* c */
} intset;
a) encoding 指定了编码方式，总共有 INTSET_ENC_INT16、INTSET_ENC_INT32、INTSET_ENC_INT64 三种。从宏定义可以看出，这三个值分别为 2、4、8。从字面意思可以看出三者能表示的范围是 16位整数、32位整数 以及 64位整数。
b) length 存储了整数集合的元素个数。
c) contents 为整数集合的柔性数组，元素类型并不一定是 int8_t 类型的。 contents 不占用结构体的大小，它只作为整数集合数据的首指针。整数集合中的元素按照从小到大的顺序在 contents 中排列起来。 2、编码方式
首先，我们来理解编码方式 encoding 的含义。需要明确的一点是，对于一个整数集合来说，所有的元素的编码一定是一致的（否则每个数都得存一个编码，而不是将它存在 intset 结构体内了），那么整个整数集合的编码取决于集合中“绝对值”最大的那个数（之所以是绝对值，因为整数包含正数和负数）。
通过那个绝对值最大的整数来获取编码，实现如下：
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;
}
/* Minimum of signed integral types. */
# define INT16_MIN (-32767-1)
# define INT32_MIN (-2147483647-1)
/* Maximum of signed integral types. */
# define INT16_MAX (32767)
# define INT32_MAX (2147483647)
static void _intsetSet(intset *is, int pos, int64_t value) {
uint32_t encoding = intrev32ifbe(is->encoding); /* a */
if (encoding == INTSET_ENC_INT64) {
((int64_t*)is->contents)[pos] = value; /* b */
memrev64ifbe(((int64_t*)is->contents)+pos); /* c */
} else if (encoding == INTSET_ENC_INT32) {
((int32_t*)is->contents)[pos] = value;
memrev32ifbe(((int32_t*)is->contents)+pos);
} else {
((int16_t*)is->contents)[pos] = value;
memrev16ifbe(((int16_t*)is->contents)+pos);
}
}
a) 大端序和小端序只是存储方式，encoding 在存储的时候进行了一次 intrev32ifbe 转换，取出来用的时候需要再进行一次 intrev32ifbe 转换（其实就是序列化和反序列化）。
b) 根据 encoding 的类型，将 contents 转换成指定类型的指针，然后用 pos 进行索引找到对应的内存位置，然后将 value 的值设置到对应的内存中。
c) memrev64ifbe 的实现参见 字节序 的 memrev64 函数，即将对应内存的值转换成小端序存储。 3、元素获取
获取 的含义就是给定整数集合以及一个位置，返回给定位置的元素的值。_intsetGet 实现如下：
static int64_t _intsetGetEncoded(intset *is, int pos, uint8_t enc) {
int64_t v64;
int32_t v32;
int16_t v16;
if (enc == INTSET_ENC_INT64) {
memcpy(&v64,((int64_t*)is->contents)+pos,sizeof(v64)); /* a */
memrev64ifbe(&v64); /* b */
return v64;
} else if (enc == INTSET_ENC_INT32) {
memcpy(&v32,((int32_t*)is->contents)+pos,sizeof(v32));
memrev32ifbe(&v32);
return v32;
} else {
memcpy(&v16,((int16_t*)is->contents)+pos,sizeof(v16));
memrev16ifbe(&v16);
return v16;
}
}
static int64_t _intsetGet(intset *is, int pos) {
return _intsetGetEncoded(is,pos,intrev32ifbe(is->encoding));
}
a) 根据 encoding 的类型，将 contents 转换成指定类型的指针，然后用 pos 进行索引找到对应的内存位置，将内存位置上的值拷贝到临时变量中；
b) 由于是直接的内存拷贝，所以取出来的值还是小端序的，那么在大端序的主机上得到的值是不对的，所以需要再做一次 memrev64ifbe 转换将值还原。 4、元素查找
由于整数集合是有序集合，所以查找某个元素是否在整数集合中，Redis 采用的是二分查找。intsetSearch 实现如下：
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;
if (intrev32ifbe(is->length) == 0) {
if (pos) *pos = 0; /* a */
return 0;
} else { /* b */
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; /* c */
cur = _intsetGet(is,mid);
if (value > cur) {
min = mid+1;
} else if (value < cur) {
max = mid-1;
} else {
break;
}
}
if (value == cur) { /* d */
if (pos) *pos = mid;
return 1;
} else {
if (pos) *pos = min;
return 0;
}
}
a) 整数集合为空，返回0表示查找失败；
b) value 的值比整数集合中的最大值还大，或者比最小值还小，则返回0表示查找失败；
c) 执行二分查找，将找到的值存在 cur 中；
d) 如果找到则返回1，表示查找成功，并且将 pos 设置为 mid 并返回；如果没找到则返回一个需要插入的位置。 5、内存重分配
由于 contents 的内存是动态分配的，所以每次进行元素插入或者删除的时候，都需要重新分配内存，这个实现放在 intsetResize 中，实现如下：
encoding 本身表示字节个数，所以乘上集合个数 len 就是 contents 数组需要的总字节数了，调用 zrealloc 进行内存重分配，然后返回重新分配后的地址。
注意：zrealloc 的返回值必须返回出去，因为 intset 在进行内存重分配以后，地址可能就变了。即 is = zrealloc(is, ...) 中，此 is 非彼 is。所以，所有调用 intsetResize 的函数都需要连带的返回新的 intset 指针。 6、编码升级
编码升级一定发生在元素插入，并且插入的元素的绝对值比整数集合中的元素都大的时候，所以我们把升级后的元素插入和编码升级放在一个函数实现，名曰 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; /* a */
is->encoding = intrev32ifbe(newenc);
is = intsetResize(is,intrev32ifbe(is->length)+1); /* b */
while(length--)
_intsetSet(is,length+prepend,_intsetGetEncoded(is,length,curenc)); /* c */
if (prepend)
_intsetSet(is,0,value);
else
_intsetSet(is,intrev32ifbe(is->length),value); /* d */
is->length = intrev32ifbe(intrev32ifbe(is->length)+1);
return is;
}
a) curenc 记录升级前的编码，newenc 记录升级后的编码；
b) 将整数集合 is 的编码设置成新的编码后，进行内存重分配；
c) 获取原先内存中的数据，设置到新内存中（注意：由于两段内存空间是重叠的，而且新内存的长度一定大于原先内存，所以需要从后往前进行拷贝）；
d) 当插入的值 value 为负数的时候，为了保证集合的有序性，需要插入到 contents 的头部；反之，插入到尾部；当 value 为负数时 prepend 为1，这样就可以保证在内存拷贝的时候将第 0 个位置留空。
如图展示了一个 (-32768, 0, 1, 32767) 的整数集合在插入数字 32768 后的升级的完整过程：
数据库
发布于：2021-07-08 13:16
|
阅读数：384
|
评论：0
QQ好友和群
QQ空间
