Redis整数集合

前言

        整数集合(intset)是集合键的底层实现之一，当一个集合只包含整数值元素，并且这个集合的元素数量不多时，Redis就会使用整数集合作为集合键的底层实现。

一. 整数集合的实现

        1.1 结构

        整数集合(intset)是Redis用于保存整数值的集合抽象数据结构，它可以保存类型为int16_t，int32_t或者int64_t的整数值，并且保证集合中不会出现重复元素。

        每个intset.h/intset结构表示一个整数集合：

typedef struct intset {
    //编码方式
    uint32_t encoding;
    //集合中包含元素的个数
    uint32_t length;
    //保存元素的数组
    int8_t contents[];
} intset;

        content数组是整数集合的底层实现：整数集合的每一个元素都是contents数组的一个数组项。各个项在数组中按值的大小从小到大有序地排列，并且数组中不包含任何重复项。

        length属性记录了整数集合包含的元素数量，也即是contents数组长度。

        虽然intset结构contents属性声明为int8_t类型的数组。但是实际上contents数组并不保持任何int8_t类型的值。contents数组的真正类型取决于encoding属性值。

• 如果encoding属性值为INTSET_ENC_INT16，那么contents就是一个int16_t类型的数组。数组里的每一项都是int16_t类型的整数值。
• 如果encoding属性值为INTSET_ENC_INT32，那么contents就是一个int32_t类型的数组。数组里的每一项都是int32_t类型的整数值。
• 如果encoding属性值为INTSET_ENC_INT64，那么contents就是一个int64_t类型的数组。数组里的每一项都是int64_t类型的整数值。

        下图展示了一个encoding为INTSET_ENC_INT64，length等于4的整数集合。contents数组按从小到大的顺序保存集合中的四个元素。因为每一个元素是int64_t类型的整数值，所以contents数组大小为sizeof(int64_t) * 4 = 64 * 4 = 256位。

        虽然contents数组保存的四个整数值中，只有-2675256175807981027真正需要int64_t类型来进行保存，而其他的1，3，4可以使用int16_t类型保存。不过根据整数集合的升级规则，当向一个底层位int16_t数组的整数集合添加一个int64_t类型的整数值时，整数集合中的所有元素都会被转化成int64_t类型。

        1.2 升级

        每当我们要将一个新元素添加到整数集合中，并且新元素的类型比整数集合现有的所有元素类型都要长时，整数集合需要先进行升级(upgrade)，然后才能将新元素添加到整数集合中。

        升级步骤：

1. 根据新元素类型，扩展整数集合底层数组的空间大小，并为新元素分配空间。
2. 将底层数组现有元素都转化成与新元素相同的类型，并将类型转化后的元素放置到正确位置上。而在放置元素过程中，需要维持底层数组有序性不变。
3. 将新元素添加到底层数组里。

        举个例子：

        现在有一个INTSET_ENC_INT16编码的整数集合，集合中包含三个int16_t类型的元素。纵隔占16*3=48位。

        现在要将类型int32_t的整数值65535添加到整数集合中。因为65535的类型int32_t比整数集合中的所有元素都长，所以需要对整数集合进行升级。

        升级首先要做的是，根据新类型长度，以及集合中元素数量(包括新元素)，对底层数组空间进行重新分配。

        现在整数集合中又四个元素，类型需要升级位int32_t，需要空间32 * 4 = 128位，如下图。虽然程序对底层数组进行了空间重新分配，但是，数组中原有的三个元素1，2，3类型仍然是int16_t。这些元素还是保存在数组contents的前48位。

        所以程序接下来需要做的是，将原来的三个元素转化成int32_t类型。并且将转化后的元素放置到正确的位上，并且需要维持底层数组的有序性。

        首先，因为元素3在1，2，3，65535四个元素中排第三。所以它被移动到contents数组的索引2的位置上，也就是数组64位至95位的空间内。

         接着，因为元素2在1，2，3，65535四个元素中排第二。所以它被移动到contents数组的索引1的位置上，也就是数组32位至63位的空间内。

        之后， 因为元素1在1，2，3，65535四个元素中排第一。所以它被移动到contents数组的索引0的位置上，也就是数组0位至31位的空间内。

        然后， 因为元素65535在1，2，3，65535四个元素中排第四。所以它被移动到contents数组的索引3的位置上，也就是数组96位至127位的空间内。

        最后，程序将encoding属性值从INTSET_ENC_INT16修改为INTSET_ENC_INT32，并将length属性值从3修改为4。

         因为每次向整数集合中添加新元素可能会引起升级，每次升级都需要对底层数组中已有元素进行类型转换，所以向整数集合添加新元素的时间复杂度为O(N)。

升级后新元素的摆放位置：

        因为引发升级的新元素的长度总是比整数集合现有所有元素的长度都大。所以这个新元素要么大于所有现有元素，要么小于所有现有元素。

        在新元素小于所有现有元素的情况下，新元素会被放置在底层数组的最开头(索引为0)

        在新元素大于所有现有元素的情况下，新元素会被放置在底层数组的最末尾(索引为length-1)

        1.3 升级的好处

        整数集合的升级策略有两个好处，一个是提升整数集合的灵活性，二是尽可能地节约内存。

• 提升灵活性

        因为C语言是静态类型语言，为了避免类型错误，我们一般不会将两种不同类型地值放在同一个数据结构里面。例如：我们只会用int16_t类型地数组来保存int16_t类型的值，只使用int32_t类型的数组来保存int32_t类型的值。

        因为整数集合可以通过自动升级底层数组来适应新元素，我们可以随意将int16_t，int_32_t或int64_t类型的整数添加到集合中，而不用担心类型错误。

• 节约内存

        让一个数组既能保存int16_t，int32_t或者int64_t类型的值最简单的做法就是直接使用int64_t类型的数组作为整数集合底层数组的实现。但是，这样一来，即使添加到整数集合里面的都是int16_t类型的值或者int32_t类型的值，数组都会需要用int64_t类型来保存，从而出现浪费内存的问题。

        而整数集合的做法既可以让集合同时保存三个类型的值，又可以确保升级操作只会在有需要的时候进行，这样实现尽可能地节约内存。

            1.4 降级

        整数集合不支持降级操作，一旦数组进行升级，编码就会一直保存升级后地状态。

        举个例子，即使我们将集合中唯一一个真正需要int64_t类型来保存地元素删除了，整数集合地编码(encoding)仍然会保持INTSET_ENC_INT64，底层数组地类型仍然是int64_t类型。

         1.5 整数集合API

 int intsetValidateIntegrity(const unsigned char *is, size_t size, int deep): 验证数据结构的完整性。当“deep”为0时，仅验证标头的完整性。当“deep”为1时，我们会确保没有重复或无序的记录。