当一个 Set 对象只包含整数值元素,且元素数量不大时,就会使用整数集合作为底层实现

整数集合结构设计

整数集合本质上是一块连续内存空间,它的结构定义如下:

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

虽然 contents 被声明为 int8_t 类型的数组,但是实际上 contents 的真正类型取决于 encoding 的值

整数集合的升级操作

当将一个新元素加入时,如果新元素的类型比整数集合现有所有元素的类型都要长时,整数集合需要先进行升级,就是按新元素的类型扩展 contents 数组的空间大小,然后才能将新元素加入到整数集合中

升级过程不会重新分配一个新类型的数组,而是在原本的数组上扩展空间,然后在将每个元素按间隔类型大小分割(如: encodingINTSET_ENC_INT16,则每个元素的间隔就是 16 位)

举个例子,有一个整数集合里有 3 个类型为 int16_t 的元素:

要加入一个新元素 65535,这个新元素需要用 int32_t 类型来保存,所以整数集合要进行升级操作,首先需要为 contents 数组扩容(在原本空间之上再扩容 4x32 - 3x16 = 80 位)

扩容完成后,需要将之前的三个元素转换为 int32_t 类型,并将转换后的元素放置到正确的位上,同时需要维持有序性不变,整个转换过程如下:

为什么需要升级?

节省内存空间:存不下才升级,而不是一开始就用 int64_t

支持降级操作吗?

不支持,一旦对数组进行了升级,就会一直保持升级后的状态。比如前面的例子,如果删除了 65535 元素,整数集合的数组还是 int32_t,并不会降级为 int16_t 类型