redis-intset源码阅读

intset数据结构

typedef struct intset {

    // 编码方式
    uint32_t encoding;

    // 集合包含的元素数量
    uint32_t length;

    // 保存元素的数组
    int8_t contents[];

} intset;

特性

1. 元素类型只能是数字
2. 元素有三种类型：int16_t,int32_t,int64_t
3. 元素有序，不能重复
4. inset和sds一样，内存连续，就像数组一样
5. intset不提供降级操作，一旦对编码进行了升级，编码就会一直保持升级后的状态

使用场景

1. 主要用于集合(set)的底层实现之一
2. 当集合元素不大于设定值并且元素都是整数时

编码方式的获取

1. 这个函数试试判断传入的数据应该用什么数据类型进行存储
2. 需要注意一点的是INT32_MIN是负值的最小值（-2147483648）
   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;
   }
   

   }

大小端模式

1. 大端模式，是指数据的高字节保存在内存的低地址中，而数据的低字节保存在内存的高地址中，这样的存储模式有点儿类似于把数据当作字符串顺序处理：地址由小向大增加，而数据从高位往低位放
2. 小端模式，是指数据的高字节保存在内存的高地址中，而数据的低字节保存在内存的低地址中，这种存储模式将地址的高低和数据位权有效地结合起来，高地址部分权值高，低地址部分权值低，和我们的逻辑方法一致
   

添加元素

1. 还是老一套，判断encode，修改值；修改length值，添加到content中
2. 如果需要添加的值存在的话不会再进行添加

intset *intsetAdd(intset *is, int64_t value, uint8_t *success) {
    //printf("---------\n");
    //printf("start\n");
    // 计算编码 value 所需的长度
    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. */
    // 如果 value 的编码比整数集合现在的编码要大
    // 那么表示 value 必然可以添加到整数集合中
    // 并且整数集合需要对自身进行升级，才能满足 value 所需的编码
    if (valenc > intrev32ifbe(is->encoding)) {
        //printf("大于\n");
        /* This always succeeds, so we don't need to curry *success. */
        // T = O(N)
        return intsetUpgradeAndAdd(is, value);
    } else {
        //printf("小于\n");
        // 运行到这里，表示整数集合现有的编码方式适用于 value

        /* 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 ，看他是否存在：
        // - 如果存在，那么将 *success 设置为 0 ，并返回未经改动的整数集合
        // - 如果不存在，那么可以插入 value 的位置将被保存到 pos 指针中
        //   等待后续程序使用
        if (intsetSearch(is, value, &pos)) {
            //printf("存在\n");
            if (success) {
                *success = 0;
            }
            return is;
        }

        //printf("不存在，search后的pos值：%d\n", pos);

        // 运行到这里，表示 value 不存在于集合中
        // 程序需要将 value 添加到整数集合中

        // 为 value 在集合中分配空间
        is = intsetResize(is, intrev32ifbe(is->length) + 1);
        // 如果新元素不是被添加到底层数组的末尾
        // 那么需要对现有元素的数据进行移动，空出 pos 上的位置，用于设置新值
        // 举个例子
        // 如果数组为：
        // | x | y | z | ? |
        //     |<----->|
        // 而新元素 n 的 pos 为 1 ，那么数组将移动 y 和 z 两个元素
        // | x | y | y | z |
        //         |<----->|
        // 这样就可以将新元素设置到 pos 上了：
        // | x | n | y | z |
        // T = O(N)
        //printf("pos:%d\n", pos);
        //printf("is->length:%d\n", intrev32ifbe(is->length));
        if (pos < intrev32ifbe(is->length)) {
            //printf("pos<length\n");
            intsetMoveTail(is, pos, pos + 1);
        }
    }

    // 将新值设置到底层数组的指定位置中
    _intsetSet(is, pos, value);
    //printf("value:%lld\n", value);

    // 增加集合元素数量的计数器
    is->length = intrev32ifbe(intrev32ifbe(is->length) + 1);

    // 返回添加新元素后的整数集合
    return is;

    /* p.s. 上面的代码可以重构成以下更简单的形式：

    if (valenc > intrev32ifbe(is->encoding)) {
        return intsetUpgradeAndAdd(is,value);
    }

    if (intsetSearch(is,value,&pos)) {
        if (success) *success = 0;
        return is;
    } else {
        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;
    }
    */
}

搜索元素

1. 主要看看二分排序法
2. 如果该值不存在，会把该值的前一个元素的pos返回回来（比如要查找8，但是intset结构中只存在6这个元素，就会把6所在的pos返回）

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 */
    // 处理 is 为空时的情况
    if (intrev32ifbe(is->length) == 0) {
        if (pos) {
            *pos = 0;
        }
        printf("不存在,pos为：%d\n", *pos);
        return 0;
    } else {
        /* Check for the case where we know we cannot find the value,
         * but do know the insert position. */
        // 因为底层数组是有序的，如果 value 比数组中最后一个值都要大
        // 那么 value 肯定不存在于集合中，
        // 并且应该将 value 添加到底层数组的最末端
        if (value > _intsetGet(is, intrev32ifbe(is->length) - 1)) {
            if (pos) {
                *pos = intrev32ifbe(is->length);//返回最末端的pos
            }
            printf("最大值,pos为：%d\n", *pos);
            return 0;
        // 因为底层数组是有序的，如果 value 比数组中最前一个值都要小
        // 那么 value 肯定不存在于集合中，
        // 并且应该将它添加到底层数组的最前端
        } else if (value < _intsetGet(is,0)) {
            if (pos) {
                *pos = 0;
            }
            printf("最小值,pos为：%d\n", *pos);
            return 0;
        }
    }

    // 在有序数组中进行二分查找
    // T = O(log N)
    while(max >= min) {
        mid = (min+max) / 2;
        cur = _intsetGet(is, mid);
        if (value > cur) {
            min = mid + 1;
        } else if (value < cur) {
            max = mid - 1;
        } else {
            break;
        }
    }

    // 检查是否已经找到了 value
    if (value == cur) {
        if (pos) {
            *pos = mid;
        }
        return 1;
    } else {
        if (pos) {//返回前面的节点
            *pos = min;
        }
        return 0;
    }
}

编码升级

1. 此处传入的value都是超过当前编码的值
2. 需要考虑更新编码可能当前value在首部（负值的时候）也可能在尾部

static intset *intsetUpgradeAndAdd(intset *is, int64_t value) {

    // 当前的编码方式
    uint8_t curenc = intrev32ifbe(is->encoding);

    // 新值所需的编码方式
    uint8_t newenc = _intsetValueEncoding(value);

    // 当前集合的元素数量
    int length = intrev32ifbe(is->length);

    // 根据 value 的值，决定是将它添加到底层数组的最前端还是最后端
    // 注意，因为 value 的编码比集合原有的其他元素的编码都要大
    // 所以 value 要么大于集合中的所有元素，要么小于集合中的所有元素
    // 因此，value 只能添加到底层数组的最前端或最后端
    // 此处需要考虑负数的情况，比如说现在是INTSET_ENC_INT16的编码方式，其范围为：-32768~32767，那么只有当value值大于32767的时候，或者小于-32768的时候才会进行扩容，因此，如果为负数就在最前端，为正数就在最后端
    int prepend = value < 0 ? 1 : 0;

    /* First set new encoding and resize */
    // 更新集合的编码方式
    is->encoding = intrev32ifbe(newenc);
    // 根据新编码对集合（的底层数组）进行空间调整
    // T = O(N)
    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. */
    // 根据集合原来的编码方式，从底层数组中取出集合元素
    // 然后再将元素以新编码的方式添加到集合中
    // 当完成了这个步骤之后，集合中所有原有的元素就完成了从旧编码到新编码的转换
    // 因为新分配的空间都放在数组的后端，所以程序先从后端向前端移动元素
    // 举个例子，假设原来有 curenc 编码的三个元素，它们在数组中排列如下：
    // | x | y | z | 
    // 当程序对数组进行重分配之后，数组就被扩容了（符号 ？ 表示未使用的内存）：
    // | x | y | z | ? |   ?   |   ?   |
    // 这时程序从数组后端开始，重新插入元素：
    // | x | y | z | ? |   z   |   ?   |
    // | x | y |   y   |   z   |   ?   |
    // |   x   |   y   |   z   |   ?   |
    // 最后，程序可以将新元素添加到最后 ？ 号标示的位置中：
    // |   x   |   y   |   z   |  new  |
    // 上面演示的是新元素比原来的所有元素都大的情况，也即是 prepend == 0
    // 当新元素比原来的所有元素都小时（prepend == 1），调整的过程如下：
    // | x | y | z | ? |   ?   |   ?   |
    // | x | y | z | ? |   ?   |   z   |
    // | x | y | z | ? |   y   |   z   |
    // | x | y |   x   |   y   |   z   |
    // 当添加新值时，原本的 | x | y | 的数据将被新值代替
    // |  new  |   x   |   y   |   z   |
    // T = O(N)
    while(length--) {//这里是从高位开始一个个向后移动，如果低位开始移动会存在覆盖问题
        _intsetSet(is, length + prepend, _intsetGetEncoded(is, length, curenc));
    }

    /* Set the value at the beginning or the end. */
    // 设置新值，根据 prepend 的值来决定是添加到数组头还是数组尾
    if (prepend) {
        _intsetSet(is, 0, value);
    }
    else {
        _intsetSet(is, intrev32ifbe(is->length), value);
    }

    // 更新整数集合的元素数量
    is->length = intrev32ifbe(intrev32ifbe(is->length) + 1);

    return is;
}