Redis 整型集合相关源码阅读笔记，源码文件 intset.h & intset.c。

1. intset 相关数据结构

1
2
3
4
5

typedef struct intset {
    uint32_t encoding;
    uint32_t length;
    int8_t contents[];
} intset;

  • encoding: intset 的编码方式

    • 有三种: INTSET_ENC_INT16, INTSET_ENC_INT32 和 INTSET_ENC_INT64
    • 在新插入的值超出当前编码的值范围时，编码会提升，但其提升后无法下降

  • length: intset 中的整数个数

    • 在 contents 存储的整数是有序的，因此可存储长度以用于二分查找
    • 为维护有序性以及采用正确的编码方式，每次插入删除会有内存重分配和内存拷贝过程，因此 intset 的长度不宜过长，其上限可在 redis.conf 中通过设置 set-max-intset-entries 进行配置，当整数集合中的元素个数超过此长度时，集合的底层实现会转为使用 dict

  • contents: contents 存储的整数是有序的，且不含重复值，其类型取决于 encoding 值。

2. intset APIs

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

/* Create an empty intset. */
intset *intsetNew(void);

/* Insert an integer in the intset, upgrade encoding if necessary.*/
intset *intsetAdd(intset *is, int64_t value, uint8_t *success);

/* Delete integer from intset */
intset *intsetRemove(intset *is, int64_t value, int *success);

/* Determine whether a value belongs to this set */
uint8_t intsetFind(intset *is, int64_t value);

/* Return random member */
int64_t intsetRandom(intset *is);

/* Get the value at the given position. When this position is
 * out of range the function returns 0, when in range it returns 1. */
uint8_t intsetGet(intset *is, uint32_t pos, int64_t *value);

/* Return intset length */
uint32_t intsetLen(const intset *is);

/* Return intset blob size in bytes. */
size_t intsetBlobLen(intset *is);