Redis数据结构之整数集合

水深无声 2022-11-06 12:54 206阅读 0赞

# 一：整数集合的实现 #

整数集合intset是集合键的底层实现方式之一，当一个集合只包含整数而且数量不是很多的时候，Redis就会整合集合作为集合键的底层实现方式。

*  整数集合是由intset.h/intset构成的

typedef struct intset {
        //编码方式
        uint32_t encoding;
        //集合包含元素的数量
        uint32_t length;
        //保存元素的数组
        int8_t contents[];
    } intset;

*  contents\[\]数组保存的是一个从小到大的有序的集合，而且集合中不包含重复的数据。
 *  尽管contents\[\]数组定义的类型为int8\_t，但是contents\[\]数组的实际类型是根据encoding的属性值来决定的。

如果encoding的属性值为INSERT\_ENC\_INT32，那么contents就是一个int32\_t类型的数组。

# 二：整数集合的升级 #

*  当整型的数组全部保存是int16\_t类型的元素，突然加入一个32位的数字，则会进行升级操作。

![20210309230712383.png][]

## 升级的步骤分为三步： ##

1：先根据新元素的类型进行扩展整数集合底层数组空间的大小，并为新元素分配空间。

![20210309231301642.png][]

2：将现有数组所有元素转换成与新元素相同的类型，并将转换后的元素放到对应的位置，在移动的过程中要维持之前的有序性不变。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NDY5MDU1_size_16_color_FFFFFF_t_70][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NDY5MDU1_size_16_color_FFFFFF_t_70 1][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NDY5MDU1_size_16_color_FFFFFF_t_70 2][]

3：将新元素插入到底层数组里面。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NDY5MDU1_size_16_color_FFFFFF_t_70 3][]

*  因为引发升级的新数据的长度比整数集合所有元素的长度都大，所有这个新元素的值要么就大于所有的元素，要么就小于所有的元素

如果加入的新数据小于整数数组的所有的元素，考虑到有序，则会放到数组的最开头（索引0）

如果加入的新数据大于整数数组的所有的元素，考虑到有序，则会放到数组的最末尾（索引为length-1）

## 升级的好处： ##

*  提升灵活性

避免不同类型错误的出现。

*  节约了内存

不用为了兼容32，16的数组，直接就赋值给整数集合类型为64位，知道需要用到的时候再去升级，这样在一定程度上面节约了内存。

整合集合暂时不支持降级处理。

# 三：整数集合API #

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NDY5MDU1_size_16_color_FFFFFF_t_70 4][]

intsetNew函数

/* Create an empty intset. */
    intset *intsetNew(void) {
        intset *is = zmalloc(sizeof(intset));
        is->encoding = intrev32ifbe(INTSET_ENC_INT16);
        is->length = 0;
        return is;
    }

intsetAdd函数

/* Insert an integer in the intset */
    intset *intsetAdd(intset *is, int64_t value, uint8_t *success) {
        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. */
        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. */
            if (intsetSearch(is,value,&pos)) {
                if (success) *success = 0;
                return is;
            }
    
            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;
    }

[20210309230712383.png]: /images/20221023/0735f39bb16147a0804ac24d9f573f43.png
[20210309231301642.png]: /images/20221023/b43e82f280904bf18667b4258d8bad81.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NDY5MDU1_size_16_color_FFFFFF_t_70]: /images/20221023/e4102d81c3914dc59167bef236493a9c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NDY5MDU1_size_16_color_FFFFFF_t_70 1]: /images/20221023/0c5fcb485cf442f6bf27cf478c16e97a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NDY5MDU1_size_16_color_FFFFFF_t_70 2]: /images/20221023/e896a91b32e9442da70913a1d7e65279.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NDY5MDU1_size_16_color_FFFFFF_t_70 3]: /images/20221023/58a13b82554247c2829b558e73981229.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NDY5MDU1_size_16_color_FFFFFF_t_70 4]: /images/20221023/74d3810f50a54e21969e81eba6dff28f.png