Redis源码阅读笔记-整数集合结构

Redis源码阅读笔记-整数集合结构

整数集合

《Redis设计与实现》

整数集合(intset)是Redis中集合键的底层实现之一,当一个集合只包含整数值元素,并且这个集合的元素不多时,Redis就会使用整数集合作为集合键的底层实现。

在Redis中,它可以保存类型为int16_tint32_tint64_t的的整数值,并且保证集合中不会出现重复元素。

代码结构

1
2
3
4
5
6
7
// intset.h

typedef struct intset {
uint32_t encoding; // 编码方式
uint32_t length; // 集合中的元素数量
int8_t contents[]; // 集合中保存元素的数组
} intset;
  • encoding: 有3种属性值INTSET_ENC_INT16INTSET_ENC_INT32INTSET_ENC_INT64用于表示保存在contents中的元素真正的类型:
    • INTSET_ENC_INT16: 表示contents中保存的是int16_t类型的整数值(-32768~32767)。
    • INTSET_ENC_INT32: 表示contents中保存的是int32_t类型的整数值(-2147483648~2147483647)。
    • INTSET_ENC_INT64: 表示contents中保存的是int64_t类型的整数值(-9223372036854775808~9223372036854775807)。
  • length: 表示的是集合中元素的数量,但不是contentsint8_t的长度。
  • contents: 集合中的元素是按值得大小,从小到大有序的保存在content中,并且不包含任何重复的项目;如果encodingINTSET_ENC_INT64,一个元素在contents中将会占8个int8_t的大小。

特点

《Redis设计与实现》

  • 整数集合是集合键的底层实现之一。
  • 整数集合的底层实现为数组,这个数组以有序、无重复的方式保存集合元素,在有需要时,程序会根据新添加元素的类型,改变这个数组的类型。
  • 升级操作为整数集合带来了操作上的灵活性,并且尽可能地节约了内存。
  • 整数集合只支持升级操作,不支持降级操作。

升级

当将一个新的元素加入到整数集合中,而且新的元素类型比整数集合现有的元素类型encoding要长,整数集合需要进行升级,扩展数组空间并将原有的元素都转换成更长的类型。

升级整数集合的顺序:

  1. 根据新元素的类型,扩展整数集合底层数组的空间大小,并为新元素分配空间。
  2. 将底层数组现有的所有元素都转换成与新元素相同的类型,并将类型转换后的元素放置到正确的位上,同时在这个过程中,要保持底层数组的有序性质不变。
  3. 将新元素添加到底层数组中。

升级的优点:

  • 灵活性,可以使数组很灵活的转换整数类型。
  • 节省内存。

降级

Redis中,整数集合不支持降级操作,所以一旦对数组进行了升级,编码会一直保持升级后的状态。

部分代码解析

  • intset *intsetNew(void) 创建一个新的整数集合:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    /* Create an empty intset. */
    intset *intsetNew(void) {
    // 分配内存
    intset *is = zmalloc(sizeof(intset));
    // 默认 int16_t, 将 INTSET_ENC_INT16 转为 int32_t 格式保存到 encoding 中
    is->encoding = intrev32ifbe(INTSET_ENC_INT16);
    // 初始化长度 0
    is->length = 0;
    return is;
    }
  • intset *intsetAdd(intset *is, int64_t value, uint8_t *success) 给定元素value添加到整数集合is中,成功或者失败的标记将会传入success中:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    129
    130
    131
    132
    133
    134
    135
    136
    137
    138
    139
    140
    141
    142
    143
    144
    145
    146
    147
    148
    149
    150
    151
    152
    153
    154
    155
    156
    157
    158
    159
    160
    161
    162
    163
    164
    165
    166
    167
    168
    169
    170
    171
    172
    173
    174
    175
    176
    177
    178
    179
    180
    181
    182
    183
    184
    185
    186
    187
    188
    189
    190
    191
    192
    193
    194
    195
    196
    197
    198
    199
    200
    201
    202
    203
    204
    205
    206
    207
    208
    209
    210
    211
    212
    213
    214
    /* Insert an integer in the intset */
    intset *intsetAdd(intset *is, int64_t value, uint8_t *success) {
    // 通过_intsetValueEncoding()函数,判断value需要哪个整数的类型,并将类型传回valenc中
    uint8_t valenc = _intsetValueEncoding(value);
    uint32_t pos;
    // 将成功标志默认设为 1
    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. */
    // 执行升级并将值value添加进整数集合
    // 然后返回结果
    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. */
    // 在整数集合中查找值value是否已经存在
    // 如果value不存在于 整数集合is 中,pos的值将是值value适合插入的位置
    // 如果已经存在,将 *success 置为1,并返回
    if (intsetSearch(is,value,&pos)) {
    if (success) *success = 0;
    return is;
    }
    // 对 整数集合is 的内存空间进行扩展,添加一个元素的空间大小
    is = intsetResize(is,intrev32ifbe(is->length)+1);
    // 如果插入位置不是数组尾,则通过intsetMoveTail()调理数组中插入位置后的元素的位置
    if (pos < intrev32ifbe(is->length)) intsetMoveTail(is,pos,pos+1);
    }
    // 执行插入函数,将值value插入is的pos位置
    _intsetSet(is,pos,value);
    // 长度加1
    is->length = intrev32ifbe(intrev32ifbe(is->length)+1);
    return is;
    }

    /* Return the required encoding for the provided value. */
    // 判断传入的值大小是需要int16_t、int32_t 还是 int64_t
    // 并返回所需要的类型标识
    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;
    }

    /* Upgrades the intset to a larger encoding and inserts the given integer. */
    // 升级 并 将 value 插入 整数集合is 中
    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是否为负数
    int prepend = value < 0 ? 1 : 0;

    /* First set new encoding and resize */
    // 更新 整数集合is 中的整数类型 编码
    is->encoding = intrev32ifbe(newenc);
    // 为is中的数组重新分配大小
    // 大小 = 新整数类型的大小 * (is中原本元素的个数 + 1)
    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. */
    // 从后往前调整数组中的元素,这样就不会修改元素本来的顺序
    // 因为插入了value,而导致了 整数集合需要升级,则说明value要么是最大的正数,要么是最小的负数
    // 所以如果是负数,则数组中元素不仅要调整结构,还要往后移位,空出第一个空位
    // 如果是正数,则数组中元素只需要调整结构
    while(length--)
    // _intsetGetEncoded()是通过元素的索引和编码获取元素的值
    _intsetSet(is,length+prepend,_intsetGetEncoded(is,length,curenc));

    /* Set the value at the beginning or the end. */
    if (prepend)
    // 如果是负数,插入第一位
    _intsetSet(is,0,value);
    else
    // 如果是正数,插入最后一位
    _intsetSet(is,intrev32ifbe(is->length),value);
    // 长度加1
    is->length = intrev32ifbe(intrev32ifbe(is->length)+1);
    return is;
    }

    /* Return the value at pos, given an encoding. */
    static int64_t _intsetGetEncoded(intset *is, int pos, uint8_t enc) {
    // 通过传入的索引 pos 和 整数结构编码 enc 在 is 中获取元素的值
    int64_t v64;
    int32_t v32;
    int16_t v16;

    if (enc == INTSET_ENC_INT64) {
    memcpy(&v64,((int64_t*)is->contents)+pos,sizeof(v64));
    memrev64ifbe(&v64);
    return v64;
    } else if (enc == INTSET_ENC_INT32) {
    memcpy(&v32,((int32_t*)is->contents)+pos,sizeof(v32));
    memrev32ifbe(&v32);
    return v32;
    } else {
    memcpy(&v16,((int16_t*)is->contents)+pos,sizeof(v16));
    memrev16ifbe(&v16);
    return v16;
    }
    }

    /* 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. */
    // 在 is 中查找 value,如果存在则返回1,pos为值所在的位置
    // 如果值不存在,则返回0,pos为值value可插入的位置
    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 */
    if (intrev32ifbe(is->length) == 0) {
    if (pos) *pos = 0;
    return 0;
    } else {
    /* Check for the case where we know we cannot find the value,
    * but do know the insert position. */

    if (value > _intsetGet(is,intrev32ifbe(is->length)-1)) {
    // 判断值value是否大于集合is中的最大值
    if (pos) *pos = intrev32ifbe(is->length);
    return 0;
    } else if (value < _intsetGet(is,0)) {
    // 判断值value是否小于集合is中的最小值
    if (pos) *pos = 0;
    return 0;
    }
    }

    // 二分查找法 查找value的位置或者适合插入的位置
    while(max >= min) {
    // 通过 >> 1 进行除2操作
    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;
    }
    }

    if (value == cur) {
    if (pos) *pos = mid;
    return 1;
    } else {
    if (pos) *pos = min;
    return 0;
    }
    }

    /* Resize the intset */
    // 为整数集合is扩展数组空间,len为指定的元素个数
    static intset *intsetResize(intset *is, uint32_t len) {
    uint32_t size = len*intrev32ifbe(is->encoding);
    is = zrealloc(is,sizeof(intset)+size);
    return is;
    }

    // 在整数集合is中 从指定位置 from开始 拷贝 数据 到 to 位置
    static void intsetMoveTail(intset *is, uint32_t from, uint32_t to) {
    void *src, *dst;
    uint32_t bytes = intrev32ifbe(is->length)-from;
    uint32_t encoding = intrev32ifbe(is->encoding);

    if (encoding == INTSET_ENC_INT64) {
    src = (int64_t*)is->contents+from;
    dst = (int64_t*)is->contents+to;
    bytes *= sizeof(int64_t);
    } else if (encoding == INTSET_ENC_INT32) {
    src = (int32_t*)is->contents+from;
    dst = (int32_t*)is->contents+to;
    bytes *= sizeof(int32_t);
    } else {
    src = (int16_t*)is->contents+from;
    dst = (int16_t*)is->contents+to;
    bytes *= sizeof(int16_t);
    }
    memmove(dst,src,bytes);
    }

    /* Set the value at pos, using the configured encoding. */
    // 在is指定位置pos中将值修改为value
    static void _intsetSet(intset *is, int pos, int64_t value) {
    uint32_t encoding = intrev32ifbe(is->encoding);

    if (encoding == INTSET_ENC_INT64) {
    ((int64_t*)is->contents)[pos] = value;
    memrev64ifbe(((int64_t*)is->contents)+pos);
    } else if (encoding == INTSET_ENC_INT32) {
    ((int32_t*)is->contents)[pos] = value;
    memrev32ifbe(((int32_t*)is->contents)+pos);
    } else {
    ((int16_t*)is->contents)[pos] = value;
    memrev16ifbe(((int16_t*)is->contents)+pos);
    }
    }
  • intset *intsetRemove(intset *is, int64_t value, int *success) 将值value从整数集合*is中删除,如果成功,则*success为1,否则为0:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    /* Delete integer from intset */
    intset *intsetRemove(intset *is, int64_t value, int *success) {
    uint8_t valenc = _intsetValueEncoding(value);
    uint32_t pos;
    if (success) *success = 0;

    // 判断值是否在整数编码的范围内,如果是的话,调用intsetSearch()查找出 value 的位置
    if (valenc <= intrev32ifbe(is->encoding) && intsetSearch(is,value,&pos)) {
    // value 存在,并且位置在 pos

    uint32_t len = intrev32ifbe(is->length);

    /* We know we can delete */
    if (success) *success = 1;

    /* Overwrite value with tail and update length */
    // 如果value不是在数组末位,则将pos+1位置后的数据往前移1位,覆盖掉原本值value
    if (pos < (len-1)) intsetMoveTail(is,pos+1,pos);
    // 释放掉多出一位的内存空间
    is = intsetResize(is,len-1);
    // 长度减1
    is->length = intrev32ifbe(len-1);
    }
    return is;
    }

整数集合API

参考之《Redis设计与实现》

函数 作用
intset *intsetNew(void) 创建一个新的整数集合
intset *intsetAdd(intset *is, int64_t value, uint8_t *success) 将给定元素value添加到整数集合is中,成功或者失败的标记将会传入success
intset *intsetRemove(intset *is, int64_t value, int *success) 从整数集合is中移除给定元素value,成功或者失败的标记将会传入success
uint8_t intsetFind(intset *is, int64_t value) 检查给定元素value是否在整数集合is
int64_t intsetRandom(intset *is) 从整数集合is中随机返回一个元素
uint8_t intsetGet(intset *is, uint32_t pos, int64_t *value) 取出整数集合is底层数组中在给定索引pos上的元素并写入value中,如果给定的索引pos超出数组长度,函数返回0,否则返回1
uint32_t intsetLen(const intset *is) 返回整数集合is中的元素个数
size_t intsetBlobLen(intset *is) 返回整数集合is中占用的内存字节数