🌻 intset

• set 元素均为 整型 && 数据量少 时的底层数据结构
• set-max-intset-entries 512
• 小端存储

1. 数据结构

• 由 整数 组成的 有序集合，便于 二分查找，快速查找某个元素是否存在
• 在内存分配上，是 连续的一整块的内存空间
• 对 大整数 & 小整数 （按照 绝对值）采取不同的编码方法，尽量缩小内存占用

	intset	ziplist
数据类型	整型	整型、字符串等任意二进制
编码方式	所有数据同用 同一种 encoding	不同节点有各自的 encoding
有序性	数据根据 值 进行 有序 存放	按照加入顺序存放
数据查找	二分查找	顺序查找

typedef struct intset {
    uint32_t encoding; // 编码方式，每个元素采用 几个字节 来存储，有 3 种方式，编码方式可能会随着数据的添加而改变
    uint32_t length; // 元素个数
    int8_t contents[]; // 柔性数组，表示 encoding & length 后面紧跟着数据
} intset;

#define INTSET_ENC_INT16 (sizeof(int16_t))
#define INTSET_ENC_INT32 (sizeof(int32_t))
#define INTSET_ENC_INT64 (sizeof(int64_t))

---

2. 常用方法

概览

// 创建
intset *intsetNew(void);
// 添加
intset *intsetAdd(intset *is, int64_t value, uint8_t *success);
// 删除
intset *intsetRemove(intset *is, int64_t value, int *success);
// 查找
uint8_t intsetFind(intset *is, int64_t value);
// 随机返回一个
int64_t intsetRandom(intset *is);
// 指定位置查找
uint8_t intsetGet(intset *is, uint32_t pos, int64_t *value);
// 长度
uint32_t intsetLen(const intset *is);
size_t intsetBlobLen(intset *is);
int intsetValidateIntegrity(const unsigned char *is, size_t size, int deep);

1) 查找

// 在集合 is 中查找 value
uint8_t intsetFind(intset *is, int64_t value) {
    uint8_t valenc = _intsetValueEncoding(value); // 根据传入的值，判断是哪种 编码方式
    // value 所属的编码方式 < intset 编码方式 
    // 二分查找 value
    return valenc <= intrev32ifbe(is->encoding) && intsetSearch(is,value,NULL);
}

/* 根据传入的值，判断是哪种 编码方式 */
static uint8_t _intsetValueEncoding(int64_t v) {
    if (v < INT32_MIN || v > INT32_MAX)
        return INTSET_ENC_INT64;
    else if (v < INT16_MIN || v > INT16_MAX)
        return INTSET_ENC_INT32;
    else
        return INTSET_ENC_INT16;
}

/* 二分查找 value 的位置
 * 若存在，pos 指向该位置，并返回 1
 * 若不存在，pos 指向应该被插入的位置，并返回 0
 */
static uint8_t intsetSearch(intset *is, int64_t value, uint32_t *pos) {
    int min = 0, max = intrev32ifbe(is->length)-1, mid = -1;
    int64_t cur = -1;

    /* inset 为空，直接返回 */
    if (intrev32ifbe(is->length) == 0) {
        if (pos) *pos = 0;
        return 0;
    } else {
        /* 与 inset 两边界的值 比较 */
        if (value > _intsetGet(is,max)) {
            if (pos) *pos = intrev32ifbe(is->length);
            return 0;
        } else if (value < _intsetGet(is,0)) {
            if (pos) *pos = 0;
            return 0;
        }
    }

    // 二分
    while(max >= min) {
        mid = ((unsigned int)min + (unsigned int)max) >> 1;
        cur = _intsetGet(is,mid);
        if (value > cur) {
            min = mid+1;
        } else if (value < cur) {
            max = mid-1;
        } else {
            break;
        }
    }

    if (value == cur) {
        if (pos) *pos = mid;
        return 1;
    } else {
        if (pos) *pos = min;
        return 0;
    }
}

2) 插入元素

/* 向 intset 插入元素
 * 若已经存在该元素，success = 0
 * 若不存在该元素，插入该元素，success = 1
 */
intset *intsetAdd(intset *is, int64_t value, uint8_t *success) {
    uint8_t valenc = _intsetValueEncoding(value); // 获取编码方式
    uint32_t pos;
    if (success) *success = 1;

    /* 若插入元素的编码方式比 intset 现有编码方式大，则需要先升级 intset 的编码方式 */
    if (valenc > intrev32ifbe(is->encoding)) {
        /* 之前肯定不存在该元素，success === 1 */
        return intsetUpgradeAndAdd(is,value);
    } else {
        // 二分查找，判断存在，修改 success，直接返回
        if (intsetSearch(is,value,&pos)) {
            if (success) *success = 0;
            return is;
        }

        // 不存在，扩充内存，插入新元素
        is = intsetResize(is,intrev32ifbe(is->length)+1);
        if (pos < intrev32ifbe(is->length)) intsetMoveTail(is,pos,pos+1);
    }

    _intsetSet(is,pos,value);
    is->length = intrev32ifbe(intrev32ifbe(is->length)+1);
    return is;
}

---

3. set 的另一实现 dict

1) dict 实现的情况

1. intset 存储后，不满足 set-max-intset-entries 512 参数设置
2. 添加 非整型数据
3. 添加 整型数据，但无法用 64 位表示

2) 存储形式

• key - set 元素
• val - null

---

4. 交并差集

源码地址