整数集合简介 整数集合intset用于有序、无重复地保存多个整数值,根据集合中元素的值自动选择使用整数类型来保存元素,例如:如果intset中绝对值最大的整数可以用int32_t来保存,那么整个intset中所有元素都使用int32_t来保存。 如果当前intset所使用的类型
整数集合简介
整数集合intset用于有序、无重复地保存多个整数值,根据集合中元素的值自动选择使用整数类型来保存元素,例如:如果intset中绝对值最大的整数可以用int32_t来保存,那么整个intset中所有元素都使用int32_t来保存。
如果当前intset所使用的类型不能保存一个即将加入到该intset的新元素时候,需要对intset进行升级,比如新元素的类型是int64_t,而当前intset的类型是int32_t,那么升级就是先将intset中所有元素由int32_t转换为int64_t,然后再插入新元素。
对于int8_t,int32_t,int64_t我个人的理解就应该分别对应char,int,long long,使用int8_t,int32_t,int64_t应该是为了区分平台的差异吧,具体的可以查看stdint.h文件。
整数集合的数据结构
1 2 3 4 5 | typedef struct intset {
uint32_t encoding; //所使用类型的长度,4\8\16
uint32_t length; //元素个数
int8_t contents[]; //保存元素的数组
} intset;
|
登入後複製
encoding的值是下面三个常量中的一个:
#define INTSET_ENC_INT16 (sizeof(int16_t))
#define INTSET_ENC_INT32 (sizeof(int32_t))
#define INTSET_ENC_INT64 (sizeof(int64_t))
contents数组用来实际保存数据,数组中元素的特性:无重复元素;元素在数组中递增排列。
整数集合相关API介绍
函数名称
|
作用
|
复杂度
|
_intsetValueEncoding
|
获取给定整数的编码类型
|
O(1)
|
_intsetGet
|
根据索引获取整数值
|
O(1)
|
_intsetSet
|
根据索引设置给定整数值
|
O(1)
|
intsetNew
|
新建intset
|
O(1)
|
intsetResize
|
为给定的intset重新分配内存
|
O(1)
|
intsetSearch
|
查找给定的整数是否在intset中
|
O(logN)
|
intsetUpgradeAndAdd
|
先升级intset然后插入元素
|
O(N)
|
intsetAdd
|
直接添加元素
|
O(N)
|
intsetMoveTail
|
将intset中元素偏移
|
O(N)
|
intsetRemove
|
删除元素
|
O(N)
|
intsetRandom
|
随机返回一个intset中元素
|
O(1)
|
intsetLen
|
intset中元素的个数
|
O(1)
|
intsetBlobLen
|
intset所占的字节数
|
O(1)
|
重要API源码的简单解析
intsetAdd
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 | //添加一个整数
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);
//将从pos位置后面的值全部向后偏移一个位置,为新元素空出位置
if (pos < intrev32ifbe( is ->length)) intsetMoveTail( is ,pos,pos+1);
}
_intsetSet( is ,pos,value);//添加新元素
is ->length = intrev32ifbe(intrev32ifbe( is ->length)+1);
return is ;
}
|
登入後複製
intsetAdd函数添加一个元素value时,首先根据value的字节数与当前intset的encoding进行比较,分析intset是否需要升级,若需要升级则调用intsetUpdateAndAdd函数处理,否则如果value已存在intset中直接pass,不存在,那么先resize,接着将插入位置之后的所有元素向后偏移,添加value。
intsetMoveTail
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 | /**使用memmove对集合进行向后偏移,下标从0开始,并且已经Resize
例:前 | 1 | 2 | 3 | 4 | 5 | 6 | | |
from = 1, to = 3
length = 6
src = | 2 | 3 | 4 | 5 | 6 |
dst = | 4 | 5 | 6 | | |
bytes = 5 * sizeof(...)
后 | 1 | 2 | 3 | 2 | 3 | 4 | 5 | 6 |
偏移之前肯定需要用intsetResize函数,进行扩容,增加两个容量
如果不理解前后的变化,建议查看memmove源码,这里需要考虑到内存覆盖的问题
也就是为什么必须使用memmove而不能使用memcpy的原因
*/
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);
}
|
登入後複製
intsetUpdateAndAdd
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 | //对编码类型进行升级,O(n)
//需要插入的值,要么比当前集合中的最大值大,要么比集合中的最小值小,不然不需要升级
//比最大值大还是小,只需要根据value的正负即可判断
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;//决定新的值插入的位置(1表示头,0表示尾)
/* First set new encoding and resize */
is ->encoding = intrev32ifbe(newenc); //设置编码类型
is = intsetResize( is ,intrev32ifbe( is ->length)+1);//resize
/* 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. */
//通过_intsetGetEncoded得到升级前的该位置的整数值
//设置原来的整数集的值,如果prepend=1表示新值在头插入,那么原来的数值全部向后偏移
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 ;
}
|
登入後複製
intsetRemove
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | //删除一个整数
intset *intsetRemove(intset * is , int64_t value, int *success) {
uint8_t valenc = _intsetValueEncoding(value);
uint32_t pos;
if (success) *success = 0;
//value在原集合中
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 */
//如果 pos 不是 is 的最末尾,直接通过memmove内存覆盖的方式删除该整数值
//如果是末尾,直接resize删除
if (pos < (len-1)) intsetMoveTail( is ,pos+1,pos);
is = intsetResize( is ,len-1);//将空间缩小
is ->length = intrev32ifbe(len-1);
}
return is ;
}
|
登入後複製
intset添加元素流程图
小结
intset用于有序、无重复地保存多个整数值,它会根据元素的值,自动选择该用什么长度的整数类型来保存元素;
当添加新元素时,需要判断当前intset的编码类型能否保存新元素,如果不行需要对intset进行升级,升级后的intset中的元素会扩大其占有的字节数,但是值不发生改变;
intset只支持升级,不支持降级,因此相对而言会浪费内存;
intset中元素是有序排列的,因此使用折半查找的时间复杂度为O(logN)。
最后感谢黄健宏(huangz1990)的Redis设计与实现及其他对Redis2.6源码的相关注释对我在研究Redis2.8源码方面的帮助。