整数集合

创建新 intset¶

intset.c/intsetNew 函数创建一个新的 intset ，并设置初始化值：

intset *is = intsetNew();

// intset->encoding = INTSET_ENC_INT16;
// intset->length 0;
// intset->contents = [];

注意 encoding 使用 INTSET_ENC_INT16 作为初始值。

添加新元素到 intset¶

创建 intset 之后，就可以对它添加新元素了。

添加新元素到 intset 的工作由 intset.c/intsetAdd 函数完成，需要处理以下三种情况：

1. 元素已存在于集合，不做动作；
2. 元素不存在于集合，并且添加新元素并不需要升级；
3. 元素不存在于集合，但是要在升级之后，才能添加新元素；

并且， intsetAdd 需要维持 intset->contents 的以下性质：

1. 确保数组中没有重复元素；
2. 确保数组中的元素按由小到大排序；

整个 intsetAdd 的执行流程可以表示为下图：

以下两个小节分别演示添加操作在升级和不升级两种情况下的执行过程。

添加新元素到 intset （不需要升级）¶

如果 intset 现有的编码方式适用于新元素， 则可直接将新元素添加到 intset ， 无须对 intset 进行升级。

以下代码演示了将三个 int16_t 类型的整数添加到集合的过程， 以及在添加过程中，集合的状态：

intset *is = intsetNew();

intsetAdd(is, 10, NULL);

// is->encoding = INTSET_ENC_INT16;
// is->length = 1;
// is->contents = [10];

intsetAdd(is, 5, NULL);

// is->encoding = INTSET_ENC_INT16;
// is->length = 2;
// is->contents = [5, 10];

intsetAdd(is, 12, NULL);

// is->encoding = INTSET_ENC_INT16;
// is->length = 3;
// is->contents = [5, 10, 12]

因为添加的三个元素都可以表示为 int16_t ， 因此 is->encoding 一直都是 INTSET_ENC_INT16 。

另一方面， is->length 和 is->contents 的值，则随着新元素的加入而被修改。

添加新元素到 intset （需要升级）¶

当要添加新元素到 intset ，并且 intset 当前的编码，不适用于新元素的编码时，就需要对 intset 进行升级。

以下代码演示了带升级的添加操作的执行过程：

intset *is = intsetNew();

intsetAdd(is, 1, NULL);

// is->encoding = INTSET_ENC_INT16;
// is->length = 1;
// is->contents = [1];                  // 所有值使用 int16_t 保存

intsetAdd(is, 65535, NULL);

// is->encoding = INTSET_ENC_INT32;     // 升级
// is->length = 2;
// is->contents = [1, 65535];           // 所有值使用 int32_t 保存

intsetAdd(is, 70000, NULL);

// is->encoding = INTSET_ENC_INT32;
// is->length = 3;
// is->contents = [1, 65535, 70000];

intsetAdd(is, 4294967295, NULL);

// is->encoding = INTSET_ENC_INT64;                 // 升级
// is->length = 4;
// is->contents = [1, 65535, 70000, 4294967295];    // 所有值使用 int64_t 保存

在添加 65535 和 4294967295 之后， encoding 属性的值，以及 contents 数组保存值的方式，都被改变了。

升级实例¶

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

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

其中， intset->contents 在内存中的排列如下：

bit     0    15    31    47
value   |  1  |  2  |  3  |

现在，我们将一个长度为 int32_t 的值 65535 加入到集合中， intset 需要执行以下步骤：

1. 将 encoding 属性设置为 INTSET_ENC_INT32 。

2. 根据 encoding 属性的值，对 contents 数组进行内存重分配。

   重分配完成之后， contents 在内存中的排列如下：

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

   contents 数组现在共有可容纳 4 个 int32_t 值的空间。

3. 因为原来的 3 个 int16_t 值还“挤在” contents 前面的 48 个位里， 所以程序需要移动它们并转换类型， 让它们适应集合的新编码方式。

   首先是移动 3 ：

   bit     0    15    31    47     63        95       127
   value   |  1  |  2  |  3  |  ?  |    3    |    ?    |
                          |             ^
                          |             |
                          +-------------+
                        int16_t -> int32_t
   

   接着移动 2 ：

   bit     0    15    31   47     63        95       127
   value   |  1  |  2  |    2     |    3    |    ?    |
                    |       ^
                    |       |
                    +-------+
               int16_t -> int32_t
   

   最后，移动 1 ：

   bit     0   15    31   47     63        95       127
   value   |    1     |    2     |    3    |    ?    |
               | ^
               V |
       int16_t -> int32_t
   

4. 最后，将新值 65535 添加到数组：

   bit     0   15    31   47     63        95       127
   value   |    1     |    2     |    3    |  65535  |
                                                ^
                                                |
                                               add
   

   将 intset->length 设置为 4 。

至此，集合的升级和添加操作完成，现在的 intset 结构如下：

intset->encoding = INTSET_ENC_INT32;
intset->length = 4;
intset->contents = [1, 2, 3, 65535];

第一，从较短整数到较长整数的转换，并不会更改元素里面的值。¶

在 C 语言中，从长度较短的带符号整数到长度较长的带符号整数之间的转换（比如从 int16_t 转换为 int32_t ）总是可行的（不会溢出）、无损的。

另一方面，从较长整数到较短整数之间的转换，可能是有损的（比如从 int32_t 转换为 int16_t ）。

因为 intset 只进行从较短整数到较长整数的转换（也即是，只“升级”，不“降级”），因此，“升级”操作并不会修改元素原有的值。

第二，集合编码元素的方式，由元素中长度最大的那个值来决定。¶

就像前面演示的例子一样， 当要将一个 int32_t 编码的新元素添加到集合时， 集合原有的所有 int16_t 编码的元素， 都必须转换为 int32_t 。

尽管这个集合真正需要用 int32_t 长度来保存的元素只有一个， 但整个集合的所有元素都必须转换为这种类型。

读取¶

有两种方式读取 intset 的元素，一种是 _intsetGet ，另一种是 intsetSearch ：

• _intsetGet 接受一个给定的索引 pos ，并根据 intset->encoding 的值进行指针运算，计算出给定索引在 intset->contents 数组上的值。
• intsetSearch 则使用二分查找算法，判断一个给定元素在 contents 数组上的索引。

写入¶

除了前面介绍过的 intsetAdd 和 intsetUpgradeAndAdd 之外， _intsetSet 也对集合进行写入操作： 它接受一个索引 pos ，以及一个 new_value ，将 contents 数组 pos 位置的值设为 new_value 。

删除¶

删除单个元素的工作由 intsetRemove 操作， 它先调用 intsetSearch 找到需要被删除的元素在 contents 数组中的索引， 然后使用内存移位操作，将目标元素从内存中抹去， 最后，通过内存重分配，对 contents 数组的长度进行调整。

降级¶

Intset 不支持降级操作。

Intset 定位为一种受限的中间表示， 只能保存整数值， 而且元素的个数也不能超过 redis.h/REDIS_SET_MAX_INTSET_ENTRIES （目前版本值为 512 ） 这些条件决定了它被保存的时间不会太长， 因此没有必要进行太复杂的操作，

当然，如果内存确实十分紧张的话，给 intset 添加降级功能也是可以实现的，不过这可能会让 intset 的代码增长一倍。