当一个 Set 对象只包含整数值元素,且元素数量不大时,就会使用整数集合作为底层实现
整数集合结构设计
整数集合本质上是一块连续内存空间,它的结构定义如下:
// 整数集合
typedef struct intset {
uint32_t encoding; // 编码方式
uint32_t length; // 集合包含的元素数量
int8_t contents[]; // 保存元素的数组
} intset;
虽然 contents
被声明为 int8_t
类型的数组,但是实际上 contents
的真正类型取决于 encoding
的值
整数集合的升级操作
当将一个新元素加入时,如果新元素的类型比整数集合现有所有元素的类型都要长时,整数集合需要先进行升级,就是按新元素的类型扩展 contents
数组的空间大小,然后才能将新元素加入到整数集合中
升级过程不会重新分配一个新类型的数组,而是在原本的数组上扩展空间,然后在将每个元素按间隔类型大小分割(如: encoding
为 INTSET_ENC_INT16
,则每个元素的间隔就是 16 位)
举个例子,有一个整数集合里有 3 个类型为 int16_t
的元素:
要加入一个新元素 65535,这个新元素需要用 int32_t
类型来保存,所以整数集合要进行升级操作,首先需要为 contents
数组扩容(在原本空间之上再扩容 4x32 - 3x16 = 80 位)
扩容完成后,需要将之前的三个元素转换为 int32_t
类型,并将转换后的元素放置到正确的位上,同时需要维持有序性不变,整个转换过程如下:
为什么需要升级?
节省内存空间:存不下才升级,而不是一开始就用
int64_t
支持降级操作吗?
不支持,一旦对数组进行了升级,就会一直保持升级后的状态。比如前面的例子,如果删除了 65535 元素,整数集合的数组还是
int32_t
,并不会降级为int16_t
类型