整数集合的实现
------------------

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

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

::

    typedef struct intset {
        
        // 编码方式
        uint32_t encoding;

        // 集合包含的元素数量
        uint32_t length;

        // 保存元素的数组
        int8_t contents[];

    } intset;

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

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

虽然 ``intset`` 结构将 ``contents`` 属性声明为 ``int8_t`` 类型的数组，
但实际上 ``contents`` 数组并不保存任何 ``int8_t`` 类型的值 ——
``contents`` 数组的真正类型取决于 ``encoding`` 属性的值：

- 如果 ``encoding`` 属性的值为 ``INTSET_ENC_INT16`` ，
  那么 ``contents`` 就是一个 ``int16_t`` 类型的数组，
  数组里的每个项都是一个 ``int16_t`` 类型的整数值
  （最小值为 ``-32,768`` ，最大值为 ``32,767`` ）。

- 如果 ``encoding`` 属性的值为 ``INTSET_ENC_INT32`` ，
  那么 ``contents`` 就是一个 ``int32_t`` 类型的数组，
  数组里的每个项都是一个 ``int32_t`` 类型的整数值
  （最小值为 ``-2,147,483,648`` ，最大值为 ``2,147,483,647`` ）。

- 如果 ``encoding`` 属性的值为 ``INTSET_ENC_INT64`` ，
  那么 ``contents`` 就是一个 ``int64_t`` 类型的数组，
  数组里的每个项都是一个 ``int64_t`` 类型的整数值
  （最小值为 ``-9,223,372,036,854,775,808`` ，最大值为 ``9,223,372,036,854,775,807`` ）。

..
    +-----------------------+---------------------------+-----------------------------------------------------------------------------------+
    | ``encoding`` 属性的值 | ``contents`` 属性的类型   | ``contents`` 数组保存的项                                                         |
    +=======================+===========================+===================================================================================+
    | ``INTSET_ENC_INT16``  | ``int16_t`` 数组          | ``int16_t`` 类型的整数值，最小值为 ``-32,768`` ，最大值为 ``32,767`` 。           |
    +-----------------------+---------------------------+-----------------------------------------------------------------------------------+
    | ``INTSET_ENC_INT32``  | ``int32_t`` 数组          | ``int32_t`` 类型的整数值，最小值为 ``-2,147,483,648`` ，                          |
    |                       |                           | 最大值为 ``2,147,483,647`` 。                                                     |
    +-----------------------+---------------------------+-----------------------------------------------------------------------------------+
    | ``INTSET_ENC_INT64``  | ``int64_t`` 数组          | ``int64_t`` 类型的整数值，最小值为 ``-9,223,372,036,854,775,808`` ，              |
    |                       |                           | 最大值为 ``9,223,372,036,854,775,807`` 。                                         |
    +-----------------------+---------------------------+-----------------------------------------------------------------------------------+

..
    因为 ``encoding`` 属性的值决定了每个数组项的大小，
    所以 ``contents`` 数组的空间大小可以使用公式 ``encoding * length`` 来计算，
    比如说：

    - 一个 ``length`` 为 ``3`` ，
      ``encoding`` 为 ``INTSET_ENC_INT32`` 的整数集合，
      它的 ``contents`` 数组的大小为 ``32 * 3 = 96`` 位，
      也即是 ``12`` 字节。

    - 一个 ``length`` 为 ``7`` ，
      ``encoding`` 为 ``INTSET_ENC_INT64`` 的整数集合，
      它的 ``contents`` 数组的大小为 ``64 * 7 = 448`` 位，
      也即是 ``56`` 字节。

    另外，
    在一般情况下，
    我们总是使用：

    ::

        array[i]

    的方式来索引数组项，
    但因为整数集合并不按类型声明来使用 ``contents`` 数组，
    所以我们不能使用：

    ::

        contents[i]

    的方式来索引数组项 ``i`` ，
    而是要根据 ``encoding`` 属性的值来进行指针计算并正确地索引数组项：

    - 如果 ``encoding`` 属性的值为 ``INTSET_ENC_INT16`` ，
      那么整数集合使用 ``((int16_t*)contents)+i`` 语句来索引数组的第 ``i`` 项。

    - 如果 ``encoding`` 属性的值为 ``INTSET_ENC_INT32`` ，
      那么整数集合使用 ``((int32_t*)contents)+i`` 语句来索引数组的第 ``i`` 项。

    - 如果 ``encoding`` 属性的值为 ``INTSET_ENC_INT64`` ，
      那么整数集合使用 ``((int64_t*)contents)+i`` 语句来索引数组的第 ``i`` 项。

图 6-1 展示了一个整数集合示例：

- ``encoding`` 属性的值为 ``INTSET_ENC_INT16`` ，
  表示整数集合的底层实现为 ``int16_t`` 类型的数组，
  而集合保存的都是 ``int16_t`` 类型的整数值。

- ``length`` 属性的值为 ``5`` ，
  表示整数集合包含五个元素。

- ``contents`` 数组按从小到大的顺序保存着集合中的五个元素。

- 因为每个集合元素都是 ``int16_t`` 类型的整数值，
  所以 ``contents`` 数组的大小等于 ``sizeof(int16_t) * 5 = 16 * 5 = 80`` 位。

.. graphviz::

    digraph {

        label = "\n 图 6-1    一个包含五个 int16_t 类型整数值的整数集合";

        rankdir = LR;

        node [shape = record];

        intset [label = " intset | encoding \n INTSET_ENC_INT16 | length \n 5 | <contents> contents "];

        //contents [label = " { { 0 位至 15 位 | <arrow> -6370 } | { 16 位至 31 位 | -5 } | { 32 位至 47 位 | 18 } | { 48 至 63 位 | 233 } | { 64 位至 79 位 | 14632 } } "];

        //intset:contents -> contents:arrow;

        contents [label = " { -6370 | -5 | 18 | 233 | 14632 } "];
        intset:contents -> contents;
    }

图 6-2 展示了另一个整数集合示例：

- ``encoding`` 属性的值为 ``INTSET_ENC_INT64`` ，
  表示整数集合的底层实现为 ``int64_t`` 类型的数组，
  而数组中保存的都是 ``int64_t`` 类型的整数值。

- ``length`` 属性的值为 ``4`` ，
  表示整数集合包含四个元素。

- ``contents`` 数组按从小到大的顺序保存着集合中的四个元素。

- 因为每个集合元素都是 ``int64_t`` 类型的整数值，
  所以 ``contents`` 数组的大小为 ``sizeof(int64_t) * 4 = 64 * 4 = 256`` 位。

.. graphviz::

    digraph {

        label = "\n 图 6-2    一个包含四个 int64_t 类型整数值的整数集合";

        rankdir = LR;

        node [shape = record];

        intset [label = " intset | encoding \n INTSET_ENC_INT64 | length \n 4 | <contents> contents "];

        contents [label = " { -2675256175807981027 | 1 | 3 | 5 } "];

        intset:contents -> contents:arrow;

    }

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

接下来的一节将对整数集合的升级操作进行详细的介绍。