21
文章
7
分类
13
标签

redis源码阅读-整数集合

redis中整数集合（intset）用于有序、无重复地保存多个整数值， 根据元素的值，自动选择该用什么长度的整数类型来保存元素。

intset的结构体

1
2
3
4
5
typedef struct intset{
    uint32_t encoding;
    uint32_t length;
    int8_t contents[];
}intset;

在这个结构体中encoding用来保存元素所使用的类型的长度，length用来保存元素个数，contents保存实际的数据。有意思的是，对于int8_t，实际上contents保存的类型根据实际需要为数据中最大的类型，int8_t在此仅仅作为占位符。

intset的函数

定义在intset结构体中的函数或者说可以对其所做的操作涉及以下几种：
|函数签名|作用|
:-:|:-:
|intset intsetNew(void)|创建一个新的intset|
|intset intsetAdd(intset is, int64_t value, uint8_t success)|增添一个新的整数元素|
|intset intsetRemove(intset is, int64_t value, int success)|删除一个元素|
|uint8_t intsetFind(intset is, int64_t value)|检查给定值是否存在于集合|
|int64_t intsetRandom(intset is)|从整数集合中随机返回一个元素|
|uint8_t intsetGet(intset is, uint32_t pos, int64_t value)|获取元素|
|uint32_t intsetLen(const intset is)|元素个数|
|size_t intsetBlobLen(intset *is)|返回整数集合占用的内存字节数|

intset的主要运行

创建一个新的整数集合

intset *is = intsetNew()

当创建一个新的整数集合时，其默认将encoding赋值为_int16的大小，length设置为0。

添加新元素到 intset

当将元素添加到整数集合中时，其需要考虑以下情形：

  1. 元素已存在于集合，不做动作；
  2. 元素不存在于集合，并且添加新元素并不需要升级；
  3. 元素不存在于集合，但是要在升级之后，才能添加新元素；
    而且，intsetAdd 需要维持元素内容的以下性质：
    确保数组中没有重复元素；
    确保数组中的元素按由小到大排序；

所以添加元素函数intsetAdd的主要流程步骤可以如下：

添加新元素到 intset(需要升级)

接下来详细，看下当需要对contens进行升级时intsetAdd函数进行的操作。
该操作主要由intsetUpgradeAndAdd函数进行。

该函数的主要任务为：
1.对新元素进行检测，看保存的新元素需要什么类型编码；
2.将集合encoding属性的值设置为新编码类型，并根据新编码类型，对整个contetns数组进行内存重分配；
3.调整contents数组内原有元素在内存中的排列方式，从旧编码调整为新编码。
4.将新元素添加到集合中。

此处重点考虑下理解将旧的编码更改为新的编码。

假设有个intset，有三个用int16_t方式保存的数值，分别是1、2和3，结构如下：

1
intset->contents = [1,2,3];

内存排列如下：

1
2
bit   0     15     31     47
value    1      2      3

将一个长度为int32_t的值 65535加入到集合中。
1.将encoding设置。
2.根据encoding属性的值，对contents数组进行内存重分配。
重分配后，contents在内存中的排列如下：

1
2
bit   0     15     31     47     63     95    127
value    1      2      3

contens数组现在有4个int32_t值的空间。
3.因为原来的3个int16_t值还“挤在”contents前面的48个位里，所以程序需要移动它们并转换类型，让它们适应集合的新编码方式。
4.移除后，将新值65535添加到数组。

###升级有两个原则

  • 从较短整数到较长整数的转换，并不会更改元素里面的值
  • 集合编码元素的方式，由元素中长度最大的那个值来决定

##总结

  • Intset 用于有序、无重复地保存多个整数值，会根据元素的值，自动选择该用什么长度的整数类型来保存元素。
  • 当一个位长度更长的整数值添加到 intset 时，需要对 intset 进行升级，新 intset 中每个元素的位长度，会等于新添加值的位长度，但原有元素的值不变。
  • 升级会引起整个 intset 进行内存重分配，并移动集合中的所有元素，这个操作的复杂度为 O(N) 。
  • Intset 只支持升级，不支持降级。
  • Intset 是有序的，程序使用二分查找算法来实现查找操作，复杂度为 O(lgN)