redis源码学习之整数集合

爱被打了一巴掌 2022-07-11 12:20 218阅读 0赞

# 整数集合 #

intset的底层实现比较简单，因为它所有的key都是整型，只是整型分为16bits、32bits和64bits这三种类型，当新插入的元素比当前集合中所有数还要长时，就要进行升级了，这部分源码很简单，主要就是升级部分。

# 数据结构 #

/*
     * intset 的编码方式
     */
    #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;//整数的编码方式：16bit 32bit 64bit
        uint32_t length;//元素个数
        int8_t contents[];//存储元素的容器
    }intset;

# 插入元素 #

跟数组操作类似，由于是有序表，因此底层查找使用二分查找，移动数组的操作使用memmove，另外还需考虑升级的情况。

intset *intsetAdd(intset *is, int64_t value, uint8_t *success) {
        // 计算编码 value 所需的长度
        uint8_t valenc = _intsetValueEncoding(value);
        uint32_t pos;
    
        // 默认设置插入为成功
        if (success) *success = 1;
        if (valenc > intrev32ifbe(is->encoding)) {
            /* This always succeeds, so we don't need to curry *success. */
            // T = O(N)
            //如果超过了当前intset的编码，则需要进行升级
            return intsetUpgradeAndAdd(is,value);
        } else {
            // 运行到这里，表示整数集合现有的编码方式适用于 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)) {
       //这里底层使用二分查找
                if (success) *success = 0;
                return is;
            }//表示元素存在，直接返回
    
            // 运行到这里，表示 value 不存在于集合中
            // 程序需要将 value 添加到整数集合中
    
            // 为 value 在集合中分配空间
            is = intsetResize(is,intrev32ifbe(is->length)+1);
            // 如果新元素不是被添加到底层数组的末尾
            // 那么需要对现有元素的数据进行移动，空出 pos 上的位置，用于设置新值
    
            if (pos < intrev32ifbe(is->length)) intsetMoveTail(is,pos,pos+1);//底层调用memmove
        }
    
        // 将新值设置到底层数组的指定位置中
        _intsetSet(is,pos,value);
    
        // 增一集合元素数量的计数器
        is->length = intrev32ifbe(intrev32ifbe(is->length)+1);
    
        // 返回添加新元素后的整数集合
        return is;
    
    
    }

## 升级 ##

最有意思的地方就在于升级了，比如现在集合中有1,2,3这三个元素，突然插入一个65535，那么就需要对原集合进行升级了，因为存储1,2,3只需要16bits整型即可，但65535需要32bits整型。

redis的做法，计算出升级之后所需要的总空间，对contents进行重新分配，再从后向前拷贝元素。譬如说：  
第一步：重新分配空间4\*32 = 128bits  
第二步：从后向前拷贝元素：先将3放到重新分配后索引2的位置，再将2放到重新分配后索引1的位置…最后将新加入的元素放到索引为3的位置。

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 只能添加到底层数组的最前端或最后端
        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);
    
    
        //_intsetGetEncoded直接使用数组名+pos的访问方式（而非[]操作符）
        //_intsetSet使用[]访问元素
        while(length--)
        //参数分别是：intset对象，待插入位置，当前元素
            _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;
    }