intset.c

Redis中的intset，表示整数集合，用来存储整数，在set数据结构中用到。

intset的数据结构如下：

typedef struct intset {
    //编码
    //#define INTSET_ENC_INT16 (sizeof(int16_t))
    //#define INTSET_ENC_INT32 (sizeof(int32_t))
    //#define INTSET_ENC_INT64 (sizeof(int64_t))
    uint32_t encoding;
    //长度
    uint32_t length;
    //集合的内容，基于数组
    int8_t contents[];
} intset;

1. 新建intset

//创建一个空的intset对象
intset *intsetNew(void) {
    intset *is = zmalloc(sizeof(intset));
    //初始化编码为int16_t
    is->encoding = intrev32ifbe(INTSET_ENC_INT16);
    is->length = 0;
    return is;
}

2. 插入元素

//插入一个整数到intset
intset *intsetAdd(intset *is, int64_t value, uint8_t *success) {
    //获取value所属encoding
    uint8_t valenc = _intsetValueEncoding(value);
    //pos存储要插入的元素的索引
    uint32_t pos;
    //插入元素的状态
    if (success) *success = 1;
    
    //如果编码变了，那么就修改编码并插入新元素，编码一旦升级不可降级
    if (valenc > intrev32ifbe(is->encoding)) {
        /* This always succeeds, so we don't need to curry *success. */
        return intsetUpgradeAndAdd(is,value);
    } else {
        //由于intset是有序不重复数组，因此采用二分查找
        if (intsetSearch(is,value,&pos)) {
            //如果元素已经存在，则不插入，直接返回，success设置为0，插入不成功
            if (success) *success = 0;
            return is;
        }

        //插入元素需要调整及分配内存
        is = intsetResize(is,intrev32ifbe(is->length)+1);
        //移动数组结构内存
        if (pos < intrev32ifbe(is->length)) intsetMoveTail(is,pos,pos+1);
    }
    //在content数组的pos处插入元素value
    _intsetSet(is,pos,value);
    //修改length属性+1
    is->length = intrev32ifbe(intrev32ifbe(is->length)+1);
    return is;
}

判断encoding，决定是否升级。
二分查找要插入的元素是否存在，存在则直接返回，否则插入。
移动内存，插入元素，返回。

_intsetValueEncoding的实现如下:

/* 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))

//根据value值的范围确定encoding
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;
}

intsetUpgradeAndAdd的实现如下：

//升级intset到更高位数的encoding以及插入提供的整数
static intset *intsetUpgradeAndAdd(intset *is, int64_t value) {
    //当前的encoding
    uint8_t curenc = intrev32ifbe(is->encoding);
    //根据value确定新的encoding
    uint8_t newenc = _intsetValueEncoding(value);
    //当前的intset元素个数
    int length = intrev32ifbe(is->length);

    //通过prepend来确定该元素要在头还是尾插入
    int prepend = value < 0 ? 1 : 0;

    //修改encoding
    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. */

    //从后往前遍历修改encoding，prepend用来预留头插空间
    while(length--)
        _intsetSet(is,length+prepend,_intsetGetEncoded(is,length,curenc));

    /* Set the value at the beginning or the end. */
    //value < 0 则头插
    if (prepend)
        _intsetSet(is,0,value);
    //value > 0 则尾插
    else
        _intsetSet(is,intrev32ifbe(is->length),value);
    is->length = intrev32ifbe(intrev32ifbe(is->length)+1);
    return is;
}

intsetSearch的实现如下：

/* 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;

    //当intset内部没有元素，直接返回0
    if (intrev32ifbe(is->length) == 0) {
        if (pos) *pos = 0;
        return 0;
    } else {
        //如果目标值比最大值还大或者比最小值还小，那么直接返回0
        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;
        }
    }

    //查找到目标值，赋值索引，返回1
    if (value == cur) {
        if (pos) *pos = mid;
        return 1;
    } else {
        if (pos) *pos = min;
        return 0;
    }
}

3. 删除元素

/* Delete integer from intset */
//删除指定value
intset *intsetRemove(intset *is, int64_t value, int *success) {
    //获取encoding
    uint8_t valenc = _intsetValueEncoding(value);
    //存索引
    uint32_t pos;
    //成功标志
    if (success) *success = 0;

    //如果encoding符合标准且查找到pos
    if (valenc <= intrev32ifbe(is->encoding) && intsetSearch(is,value,&pos)) {
        uint32_t len = intrev32ifbe(is->length);

        /* We know we can delete */
        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;
}

4. 检查元素是否存在

//查找指定元素是否在集合中
uint8_t intsetFind(intset *is, int64_t value) {
    //确定encoding
    uint8_t valenc = _intsetValueEncoding(value);
    //有效性检测及二分查找
    return valenc <= intrev32ifbe(is->encoding) && intsetSearch(is,value,NULL);
}

5. 随机返回一个元素

int64_t intsetRandom(intset *is) {
    //pos = rand()%intrev32ifbe(is->length)
    return _intsetGet(is,rand()%intrev32ifbe(is->length));
}