Redis内部数据结构详解之整数集合(intset)
整数集合简介 整数集合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文件。
整数集合的数据结构
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
//添加一个整数 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 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 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
/**使用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
//对编码类型进行升级,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 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
//删除一个整数 intset *intsetRemove(intset *is, int64_t value, int *success) { uint8_t valenc = _intsetValueEncoding(value); uint32_t pos; if (success) *success = 0; //value在原集合中 if (valenc 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 length = intrev32ifbe(len-1); } return is; }
intset添加元素流程图
小结
intset用于有序、无重复地保存多个整数值,它会根据元素的值,自动选择该用什么长度的整数类型来保存元素;
当添加新元素时,需要判断当前intset的编码类型能否保存新元素,如果不行需要对intset进行升级,升级后的intset中的元素会扩大其占有的字节数,但是值不发生改变;
intset只支持升级,不支持降级,因此相对而言会浪费内存;
intset中元素是有序排列的,因此使用折半查找的时间复杂度为O(logN)。
最后感谢黄健宏(huangz1990)的Redis设计与实现及其他对Redis2.6源码的相关注释对我在研究Redis2.8源码方面的帮助。