redis源码学习-intset篇

intset介绍

redis中的inset用来保存整数集合，适用于无重复数字，且数据量小的场合。

intset分析

c中的大小端模式：
**大端存储：**把一个数的低位字节序的内容存放到高地址处，高位字节序的内容存放在低地址处。
**小端存储：**把一个数的低位字节序的内容存放到低地址处，高位字节序的内容存放在高地址处。
在redis中，全部使用小端存储。因此，引入了/src/endianconv.h和/src/endianconv.c负责统一判断机器本地的方式并处理。
数据结构：

/* Note that these encodings are ordered, so:
 * INTSET_ENC_INT16 < INTSET_ENC_INT32 < INTSET_ENC_INT64. */
#define INTSET_ENC_INT16 (sizeof(int16_t))
#define INTSET_ENC_INT32 (sizeof(int32_t))
#define INTSET_ENC_INT64 (sizeof(int64_t))

typedef struct intset {
    uint32_t encoding;
    uint32_t length;
    int8_t contents[];
} intset;

encoding为类型，定义在宏INTSET_ENC_INT16 ，INTSET_ENC_INT32 ，INTSET_ENC_INT64 中。length为集合的长度，contents为集合。
其中encoding的编码方式取决于集合中最大的数，如果存在一个int64，那么整个inset的encoding都为int64.
创建：

/* Create an empty intset. */
intset *intsetNew(void) {
    //调用zmalloc分配堆内存
    intset *is = zmalloc(sizeof(intset));
    //默认INTSET_ENC_INT16节约内存
    is->encoding = intrev32ifbe(INTSET_ENC_INT16);
    is->length = 0;
    return is;
}

初始化时全部默认使用INTSET_ENC_INT16 来节约内存。
新增：

/* Insert an integer in the intset */
intset *intsetAdd(intset *is, int64_t value, uint8_t *success) {
    //获取对应的value编码，看当前value是int几
    uint8_t valenc = _intsetValueEncoding(value);
    uint32_t pos;
    if (success) *success = 1;

    /* Upgrade encoding if necessary. If we need to upgrade, we know that
     * this value should be either appended (if > 0) or prepended (if < 0),
     * because it lies outside the range of existing values. */
    //假如说当前编码大于inset的最大编码，需要执行升级和新增的操作了
    if (valenc > intrev32ifbe(is->encoding)) {
        /* This always succeeds, so we don't need to curry *success. */
        return intsetUpgradeAndAdd(is,value);
    } else {
        /* Abort if the value is already present in the set.
         * This call will populate "pos" with the right position to insert
         * the value when it cannot be found. */
        //查找当前value是否存在，同时找到小于value的最大值是哪个，将这个值赋给pos
        if (intsetSearch(is,value,&pos)) {
            if (success) *success = 0;
            return is;
        }
        //多申请空间
        is = intsetResize(is,intrev32ifbe(is->length)+1);
        //如果没有找到当前value的前一个数字，那么就将pos数据后挪一位
        if (pos < intrev32ifbe(is->length)) intsetMoveTail(is,pos,pos+1);
    }

    _intsetSet(is,pos,value);
    is->length = intrev32ifbe(intrev32ifbe(is->length)+1);
    return is;
}
/* Return the required encoding for the provided value. */
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;
}

编码升级且新增：

/* Upgrades the intset to a larger encoding and inserts the given integer. */
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;

    /* First set new encoding and resize */
    is->encoding = intrev32ifbe(newenc);
    is = intsetResize(is,intrev32ifbe(is->length)+1);

    /* Upgrade back-to-front so we don't overwrite values.
     * Note that the "prepend" variable is used to make sure we have an empty
     * space at either the beginning or the end of the intset. */
    //从最后开始，将原有的数据进行迁移
    while(length--)
        _intsetSet(is,length+prepend,_intsetGetEncoded(is,length,curenc));

    /* Set the value at the beginning or the end. */
    //如果当前value值小于0，那么set到集合的头部
    if (prepend)
        _intsetSet(is,0,value);
    else
        _intsetSet(is,intrev32ifbe(is->length),value);
    is->length = intrev32ifbe(intrev32ifbe(is->length)+1);
    return is;
}

新增时，需要在原先申请的内存之上realloc，假如说新增的value在当前intset中间，那么从value之后的都需要向后移动一个encoding
删除：

/* Delete integer from intset */
intset *intsetRemove(intset *is, int64_t value, int *success) {
    uint8_t valenc = _intsetValueEncoding(value);
    uint32_t pos;
    if (success) *success = 0;
    //如果当前要删除的value编码已经大于当前intset的编码格式，说明value肯定不在intset里，无需操作
    if (valenc <= intrev32ifbe(is->encoding) && intsetSearch(is,value,&pos)) {
        //将value转为小端存储
        uint32_t len = intrev32ifbe(is->length);

        /* We know we can delete */
        if (success) *success = 1;

        /* Overwrite value with tail and update length */
        if (pos < (len-1)) intsetMoveTail(is,pos+1,pos);
        is = intsetResize(is,len-1);
        is->length = intrev32ifbe(len-1);
    }
    return is;
}

可以看到，删除时首先判断value的编码，假如编码明显不对那就什么都不做。在删除时并不做编码降级操作。由于此intset曾经出现过超大的数，那么再次出现的概率并不低，因此贸然降级的话，不仅当前需要处理intset的编码，而且以后升级的概况也很高，干脆多占点内存，避免麻烦与无用的时间消耗。
查找：

/* Determine whether a value belongs to this set */
uint8_t intsetFind(intset *is, int64_t value) {
    uint8_t valenc = _intsetValueEncoding(value);
    return valenc <= intrev32ifbe(is->encoding) && intsetSearch(is,value,NULL);
}
/* Search for the position of "value". Return 1 when the value was found and
 * sets "pos" to the position of the value within the intset. Return 0 when
 * the value is not present in the intset and sets "pos" to the position
 * where "value" can be inserted. */
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;

    /* The value can never be found when the set is empty */
    //判断空值
    if (intrev32ifbe(is->length) == 0) {
        if (pos) *pos = 0;
        return 0;
    } else {
        /* Check for the case where we know we cannot find the value,
         * but do know the insert position. */
        if (value > _intsetGet(is,max)) {
            //假如说现value已经大于当前intset中的最大了，那么修改pos为value，更新pos为最大值
            if (pos) *pos = intrev32ifbe(is->length);
            return 0;
        } else if (value < _intsetGet(is,0)) {
            //如果说当现value比当前intset中最小的还小，修改pos为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;
    }
}
/* Return the value at pos, using the configured encoding. */
static int64_t _intsetGet(intset *is, int pos) {
    return _intsetGetEncoded(is,pos,intrev32ifbe(is->encoding));
}
/* Return the value at pos, given an encoding. */
static int64_t _intsetGetEncoded(intset *is, int pos, uint8_t enc) {
    int64_t v64;
    int32_t v32;
    int16_t v16;

    if (enc == INTSET_ENC_INT64) {
        memcpy(&v64,((int64_t*)is->contents)+pos,sizeof(v64));
        memrev64ifbe(&v64);
        return v64;
    } else if (enc == INTSET_ENC_INT32) {
        memcpy(&v32,((int32_t*)is->contents)+pos,sizeof(v32));
        memrev32ifbe(&v32);
        return v32;
    } else {
        memcpy(&v16,((int16_t*)is->contents)+pos,sizeof(v16));
        memrev16ifbe(&v16);
        return v16;
    }
}

由于intset里保存的为有序数组，故在这里直接使用二分查找。
总体来说，redis在设计intset的时候，就定下了intset是仅仅用来存储数字的集合，而且里边无法存储相同的数字，也因此采用了简单粗暴的二分查找，整体性能一般。时间复杂度在O(log2n) 的级别，更何况在每次新增或删除时都有批量移动的操作。
与redis的sds，dict，hyperloglog等数据结构相比，intset的整体优化不够，足够简单算是唯一的优点了把。