整数集合(intset)
整数集合 intset 是 redis 中用于保存整数集合的数据类型，他可以保存为 16、32、或者 64 的整数值，且保证集合中不会出现重复的元素。
/* 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)) /* 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; }
inset.h/intset 结构表示一个整数集合：
typedef struct intset { // 编码方式 uint32_t encoding; // 集合包含的元素数量 uint32_t length; // 保存元素的数组 int8_t contents[]; } intset;
一个包含五个 int16_t 类型整数值的整数集合：
数据操作
1、数据查找
intset 查找（intsetSearch）采用的是折半查找方式，时间复杂度为 O(logN)
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; } }
2、插入与升级
当插入元素大于当前 intset 类型时，为了防止溢出，会对其进行升级操作。比如：向一个底层为 int_16_t 的整数集合中添加一个 int64_t 类型的整数值是，整数集合已有的所有原属都会转换为 int64_t 。
/* 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. */ 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; } 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 . 代码如下所示：
/* 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; }
升级整数集合并且添加新元素一共分为三个步骤：
1）根据新元素的类型，拓展整数集合底层数组的空间大小，并且为新元素分配空间。
2）将底层数组现有的元素都转成新原属相同的类型，并且将转换后的元素放置到正确的位上，而且放置元素的过程中，需要继续位置数组的有序性质不变。
3）将新元素加入到底层数组里面。
intset 操作优点
- 提升灵活性
可以通过自动升级底层数组来适应新的元素，所以可以将任意类型添加到集合，而不必贪心类型错误
- 节约内存
不同类型采用不同的类型的空间对其存储，从而避免空间浪费
- 降级：不支持降级
- 添加和删除
均需要进行 realloc 操作，因此慎用。
