Redis源码阅读 - Redis数据结构整数集合(intset)

typedef struct intset {
    uint32_t encoding;   // 保存元素所使用的类型的长度
    uint32_t length;     // 元素个数
    int8_t contents[];   // 保存元素的数组
} intset;

// 定义encoding属性的可能取值
#define INTSET_ENC_INT16 (sizeof(int16_t))   // 16位存储的整数
#define INTSET_ENC_INT32 (sizeof(int32_t))
#define INTSET_ENC_INT64 (sizeof(int64_t))

intset *intsetNew(void) {
    intset *is = zmalloc(sizeof(intset));
    is->encoding = intrev32ifbe(INTSET_ENC_INT16);
    is->length = 0;
    return is;
}

intset *intsetAdd(intset *is, int64_t value, uint8_t *success) {   // 在整数集中插入一条数据
    uint8_t valenc = _intsetValueEncoding(value);   // 计算value需要的编码
    uint32_t pos;
    if (success) *success = 1;

    if (valenc > intrev32ifbe(is->encoding)) {  // 如果需要的编码大于当前编码，那就需要更新整数集的编码类型并插入
        return intsetUpgradeAndAdd(is,value);
    } else {
        if (intsetSearch(is,value,&pos)) {   // 如果值已经存在于集合了，直接返回。记录插入失败, 不存在也计算出需要插入的位置pos
            if (success) *success = 0;
            return is;
        }

        is = intsetResize(is,intrev32ifbe(is->length)+1);  // 给集合大小扩容1个长度
        if (pos < intrev32ifbe(is->length)) intsetMoveTail(is,pos,pos+1);
    }

    _intsetSet(is,pos,value);  // 插入值并更新长度
    is->length = intrev32ifbe(intrev32ifbe(is->length)+1);
    return is;
}

static intset *intsetUpgradeAndAdd(intset *is, int64_t value) {
    uint8_t curenc = intrev32ifbe(is->encoding);
    uint8_t newenc = _intsetValueEncoding(value);   // 计算存储新值需要的编码
    int length = intrev32ifbe(is->length);
    int prepend = value < 0 ? 1 : 0;    // 根据value的正负判断是前插还是后插， 负数就前插，正数后插，因为从小到大排序。

    is->encoding = intrev32ifbe(newenc);
    is = intsetResize(is,intrev32ifbe(is->length)+1);
    while(length--)
        _intsetSet(is,length+prepend,_intsetGetEncoded(is,length,curenc));   // 遍历原来的内容从最后一个元素开始倒序，更新到新的长度，注意这里不会覆盖因为新的内存大于旧的

    if (prepend)
        _intsetSet(is,0,value);
    else
        _intsetSet(is,intrev32ifbe(is->length),value);
    is->length = intrev32ifbe(intrev32ifbe(is->length)+1);
    return is;
}

static uint8_t intsetSearch(intset *is, int64_t value, uint32_t *pos) {     // 在整数集合中，查找一个值，如果设置了出参pos。记录该值在集合中的位置
    int min = 0, max = intrev32ifbe(is->length)-1, mid = -1;
    int64_t cur = -1;

    if (intrev32ifbe(is->length) == 0) {  // 当集合为空时，查找不到直接返回0 且出参pos也置0 
        if (pos) *pos = 0;
        return 0;
    } else {
        if (value > _intsetGet(is,max)) {      // 如果查找的值大于集合中的最大值或者小于最小值，直接返回0, 说明不存在
            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) {       // 找到了就赶回value的位置
        if (pos) *pos = mid;
        return 1;
    } else {
        if (pos) *pos = min;   // 如果没找到，就返回小于value的那个值的位置
        return 0;
    }
}