Redis中的intset，表示整數(shù)集合，用來存儲整數(shù)，在set數(shù)據(jù)結(jié)構(gòu)中用到。

intset的數(shù)據(jù)結(jié)構(gòu)如下：

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;
    //集合的內(nèi)容，基于數(shù)組
    int8_t contents[];
} intset;

1. 新建intset

//創(chuàng)建一個空的intset對象
intset *intsetNew(void) {
    intset *is = zmalloc(sizeof(intset));
    //初始化編碼為int16_t
    is->encoding = intrev32ifbe(INTSET_ENC_INT16);
    is->length = 0;
    return is;
}

2. 插入元素

//插入一個整數(shù)到intset
intset *intsetAdd(intset *is, int64_t value, uint8_t *success) {
    //獲取value所屬encoding
    uint8_t valenc = _intsetValueEncoding(value);
    //pos存儲要插入的元素的索引
    uint32_t pos;
    //插入元素的狀態(tài)
    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是有序不重復(fù)數(shù)組，因此采用二分查找
        if (intsetSearch(is,value,&pos)) {
            //如果元素已經(jīng)存在，則不插入，直接返回，success設(shè)置為0，插入不成功
            if (success) *success = 0;
            return is;
        }

        //插入元素需要調(diào)整及分配內(nèi)存
        is = intsetResize(is,intrev32ifbe(is->length)+1);
        //移動數(shù)組結(jié)構(gòu)內(nèi)存
        if (pos < intrev32ifbe(is->length)) intsetMoveTail(is,pos,pos+1);
    }
    //在content數(shù)組的pos處插入元素value
    _intsetSet(is,pos,value);
    //修改length屬性+1
    is->length = intrev32ifbe(intrev32ifbe(is->length)+1);
    return is;
}

判斷encoding，決定是否升級。
二分查找要插入的元素是否存在，存在則直接返回，否則插入。
移動內(nèi)存，插入元素，返回。

_intsetValueEncoding的實現(xiàn)如下:

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

//根據(jù)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的實現(xiàn)如下：

//升級intset到更高位數(shù)的encoding以及插入提供的整數(shù)
static intset *intsetUpgradeAndAdd(intset *is, int64_t value) {
    //當(dāng)前的encoding
    uint8_t curenc = intrev32ifbe(is->encoding);
    //根據(jù)value確定新的encoding
    uint8_t newenc = _intsetValueEncoding(value);
    //當(dāng)前的intset元素個數(shù)
    int length = intrev32ifbe(is->length);

    //通過prepend來確定該元素要在頭還是尾插入
    int prepend = value < 0 ? 1 : 0;

    //修改encoding
    is->encoding = intrev32ifbe(newenc);

   //調(diào)整及分配內(nèi)存空間
    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用來預(yù)留頭插空間
    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的實現(xiàn)如下：

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

    //當(dāng)intset內(nèi)部沒有元素，直接返回0
    if (intrev32ifbe(is->length) == 0) {
        if (pos) *pos = 0;
        return 0;
    } else {
        //如果目標(biāo)值比最大值還大或者比最小值還小，那么直接返回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;
        }
    }

    //查找到目標(biāo)值，賦值索引，返回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;
    //成功標(biāo)志
    if (success) *success = 0;

    //如果encoding符合標(biāo)準且查找到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;

        //移動內(nèi)存
        if (pos < (len-1)) intsetMoveTail(is,pos+1,pos);
        //釋放空間
        is = intsetResize(is,len-1);
        //修改元素個數(shù)
        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));
}