Redis深度历险-整数集合（intset）

Redis中的集合在只有数字的情况下使用的是intset存储，主要代码在intset.c、intset.h中

结构体定义

typedef struct intset {
    uint32_t encoding;              //编码类型，支持16、32、64位整数
    uint32_t length;                    //数组长度
    int8_t contents[];              //不定长结构体，存储整数
} intset;

整数集合中只能用来存储整数，在contents是有序数组

intset的创建、插入、查找、删除

创建

intset *intsetNew(void) {
    intset *is = zmalloc(sizeof(intset));
    is->encoding = intrev32ifbe(INTSET_ENC_INT16);          //默认存储的是2字节整数
    is->length = 0;                                                                         //初始情况下数组长度为0
    return is;
}

插入

intset *intsetAdd(intset *is, int64_t value, uint8_t *success) {
    //计算出整数属于16位、32位还是64位整数
    uint8_t valenc = _intsetValueEncoding(value);
    uint32_t pos;
    if (success) *success = 1;

    //默认情况下intset存储的16位整数，如果插入的数据大于目前的编码所能支持的最大数就需要调整编码
    if (valenc > intrev32ifbe(is->encoding)) {
        return intsetUpgradeAndAdd(is,value);
    } else {
        //如果数组已经存在集合中直接返回，success为0表示已存在
        if (intsetSearch(is,value,&pos)) {
            if (success) *success = 0;
            return is;
        }
        //pos是元素插入的位置
                
        //扩容后挪移元素
        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;
}

因为在集合set中可以看到只在数据比较少时才使用intset存储，所以挪移元素的消耗还可以接受

查找元素

Redis中的集合是不能存储重复元素的，在插入前需要判断元素是否已存在

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;

    //集合为空的情况直接返回
    if (intrev32ifbe(is->length) == 0) {
        if (pos) *pos = 0;
        return 0;
    } else {
        //如果新插入的数据大于最大的数据则直接插入在最后面
        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;
    }
}

在intset保存的是有序数组，使用二分查找即可

删除元素

intset *intsetRemove(intset *is, int64_t value, int *success) {
    uint8_t valenc = _intsetValueEncoding(value);
    uint32_t pos;
    if (success) *success = 0;
        
    //先查找元素
    if (valenc <= intrev32ifbe(is->encoding) && intsetSearch(is,value,&pos)) {
        uint32_t len = intrev32ifbe(is->length);

        
        if (success) *success = 1;

        //直接将该元素后的数据往前挪移一个单位即可
        if (pos < (len-1)) intsetMoveTail(is,pos+1,pos);
        is = intsetResize(is,len-1);
        is->length = intrev32ifbe(len-1);
    }
    return is;
}

扩容

static intset *intsetResize(intset *is, uint32_t len) {
    uint32_t size = len*intrev32ifbe(is->encoding);
    is = zrealloc(is,sizeof(intset)+size);
    return is;
}

这里没有过多的操作直接使用realloc扩容，这里并没有两倍扩张不会太频繁了吗？

intset的编码提升

在插入数据的时候有可能元素大于16/32位所能表示的最大数，这时就需要调整编码

static intset *intsetUpgradeAndAdd(intset *is, int64_t value) {
    //当前编码格式
    uint8_t curenc = intrev32ifbe(is->encoding);
    //判断当前新元素的编码，属于16位、32位还是64位
    uint8_t newenc = _intsetValueEncoding(value);
    int length = intrev32ifbe(is->length);
    int prepend = value < 0 ? 1 : 0;

    //调整编码和空间大小，并没有挪移元素
    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;
}

总结

整数集合并没有设计的特别复杂，直接使用了有序数据来存储数据