写在前面
以下内容是基于Redis 6.2.6 版本整理总结
一、整数集合（intset）
当一个集合只包含整数值元素，并且元素的个数不多时，Redis会使用整数集合作为集合键的底层实现。
1.1 整数集合的实现
整数集合可用保存的数据类型有：int16_t int32_t 和 int64_t 的整数值，并且保证集合中不会出现重复元素。
整数集合定义如下：
// src/intset.h typedef struct intset { uint32_t encoding; // 编码方式，后面会详细解释 uint32_t length; // 集合中元素的个数,也就是contents数组的长度 int8_t contents[]; // 保存元素的数组 } 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))
分析：
contents数组是整数集合的底层实现：整数集合中的每一个元素就是contents数组中的一个元素，每个元素在数组中按照从小到大的顺序排列，并且没有重复元素。
虽然，contents数组被声明为 int8_t 类型的数组，但实际上contents数组并不保存任何int8_t 类型的值，contents数组实际存储的类型取决于encoding的值。encoding的取值可以是：INTSET_ENC_INT16、INTSET_ENC_INT32 或 INTSET_ENC_INT64，每种编码的取值范围如下：
- INTSET_ENC_INT16 取值范围：[−2^15 ，2^15−1] 即：[-32768, 32767 ]
- INTSET_ENC_INT32 取值范围：[−2^31 ，2^31−1] 即：[-2147483648, 2147483647]
- INTSET_ENC_INT64 取值范围：[−2^63 ，2^63−1] 即：[-9223372036854775808, 9223372036854775807]
说明：n比特有符号整数的表示范围为：[−2^(n−1) ，2^(n−1)−1]
整数集合图示
1.2 整数集合的操作
每次往整数集合中插入新元素时，会检查新元素的类型，是不是比当前contents数组的类型长，如果是，整数集合需要先进行升级操作。比如：现在我们要把编码为int32_t的元素插入到整数集合里，因为65535的类型比集合中当前元素类型要长，所以要先对整数集合升级。
升级的好处：
- 灵活：C语言是静态类型的语言，为了避免类型错误，我们通常是一种类型就放到一种类型的数据结构里，如：我们一般会使用int16_t类型的数组保存int16_t类型的值，用int32_t类型数组保存int32_t类型的值。而整数集合允许随意的将不同类型的整型值添加到集合中，而不用担心类型错误。
- 节约内存：如果想让一个数组同时保存，int16_t、int32_t和int64_t的值，最简单的方式就是使用int64_t类型的数组，但是这会造成空间的浪费。inset只会在适当的时候才会触发升级操作，其他时间都是尽可能节约内存。
1.2.1 intset添加元素
inset插入元素
/* 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. */ // 待插入整数的编码类型大于当前contents数组的编码类型，需要先进行升级操作 if (valenc > intrev32ifbe(is->encoding)) { /* This always succeeds, so we don't need to curry *success. */ 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. */ // 插入之前先在集合里查找是否已经存在该元素，（二分查找） // 如果该元素已经存在，则直接返回；如果没有，则返回该元素待插入的数组下标，保存在pos中 if (intsetSearch(is,value,&pos)) { if (success) *success = 0; return is; } // 1 3 5 insert 2 pos: 1 // 扩展空间 is = intsetResize(is,intrev32ifbe(is->length)+1); // 如果pos 小于当前数组长度，将从pos位置开始的元素，同一往后挪一格，腾出pos的位置 if (pos < intrev32ifbe(is->length)) intsetMoveTail(is,pos,pos+1); } // 将待插入的元素，放在pos的位置 _intsetSet(is,pos,value); // 更新数组的长度 is->length = intrev32ifbe(intrev32ifbe(is->length)+1); return is; } // 整数集合升级 static intset *intsetUpgradeAndAdd(intset *is, int64_t value) { // 获取当前整数集合的编码 uint8_t curenc = intrev32ifbe(is->encoding); // 计算待插入元素value的编码 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; } // 二分查找插入位置 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; } } // 1 3 5 length：3 insert： 2 pos: 1 static 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); 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); } memmove(dst,src,bytes); }
插入元素步骤图解：
1.2.2 inset 删除元素：
/* Delete integer from intset */ intset *intsetRemove(intset *is, int64_t value, int *success) { // 获取待删除元素的编码 uint8_t valenc = _intsetValueEncoding(value); uint32_t pos; if (success) *success = 0; // 如果找到待删除元素及其pos if (valenc <= intrev32ifbe(is->encoding) && intsetSearch(is,value,&pos)) { uint32_t len = intrev32ifbe(is->length); /* We know we can delete */ if (success) *success = 1; /* Overwrite value with tail and update length */ // 把从待删除元素的后面所有节点，往前挪动一格 if (pos < (len-1)) intsetMoveTail(is,pos+1,pos); is = intsetResize(is,len-1); is->length = intrev32ifbe(len-1); } return is; }
二、总结
- 整数集合的底层实现是数组，这个数组以有序、无重复的方式存储元素，在需要时会根据新添加元素的类型升级数组的类型。
- 只支持升级操作，不支持降级操作
- 整数集合是有序集合的底层实现之一
