深入剖析 redis 数据结构 intset

intset 和 dict 都是 sadd 命令的底层数据结构，当添加的所有数据都是整数时，会使用前者；否则使用后者。 特别的 ，当遇到添加数据为字符串，即不能表示为整数时，redis 会把数据结构转换为 dict，即把 intset 中的数据全部搬迁到 dict。 本片展开的是 ints

intset 和 dict 都是 sadd 命令的底层数据结构，当添加的所有数据都是整数时，会使用前者；否则使用后者。特别的，当遇到添加数据为字符串，即不能表示为整数时，redis 会把数据结构转换为 dict，即把 intset 中的数据全部搬迁到 dict。

本片展开的是 intset，dict 的文章可以参看之前写的《深入剖析 redis 数据结构 dict》。

intset 结构体

intset 底层本质是一个有序的、不重复的、整型的数组，支持不同类型整数。

typedef struct intset {    // 每个整数的类型    uint32_t encoding;    // intset 长度    uint32_t length;    // 整数数组    int8_t contents[];} intset;

encoding 能下面的三个值：分别是 16，32 和 64位整数：

/* Note that these encodings are ordered, so:* INTSET_ENC_INT16 < INTSET_ENC_INT32 < INTSET_ENC_INT64. */#define INTSET_ENC_INT16 (sizeof(int16_t))#define INTSET_ENC_INT32 (sizeof(int32_t))#define INTSET_ENC_INT64 (sizeof(int64_t))

intset 搜索

intset 是有序的整数数组，可以用二分搜索查找。

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. */        // value 比最大元素还大        if (value > _intsetGet(is,intrev32ifbe(is->length)-1)) {            if (pos) *pos = intrev32ifbe(is->length);            return 0;        // value 比最小元素还小        } else if (value = min) {        mid = (min+max)/2;        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;    }}

intset 插入

intset 实现中比较远有意思的是插入算法部分。

/* 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  intrev32ifbe(is->encoding)) {        /* This always succeeds, so we don't need to curry *success. */        return intsetUpgradeAndAdd(is,value);    // 正常，分配内存，插入    } else {        // intset 内部不允许重复        /* 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;        }        // realloc        is = intsetResize(is,intrev32ifbe(is->length)+1);        // 迁移内存，腾出空间给新的数据。intsetMoveTail() 完成内存迁移工作        if (pos length)) intsetMoveTail(is,pos,pos+1);    }    // 在腾出的空间中设置新的数据    _intsetSet(is,pos,value);    // 更新 intset size    is->length = intrev32ifbe(intrev32ifbe(is->length)+1);    return is;}// 升级整数类型，譬如从 short->int。当插入数据的内存占用比原有数据大// 的时候，会被调用/* Upgrades the intset to a larger encoding and inserts the given integer. */static intset *intsetUpgradeAndAdd(intset *is, int64_t value) {    uint8_t curenc = intrev32ifbe(is->encoding);    uint8_t newenc = _intsetValueEncoding(value);    int length = intrev32ifbe(is->length);    // value0 尾插    int prepend = value encoding = intrev32ifbe(newenc);    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.<b style="color:transparent">本文来源gao@!dai!ma.com搞$$代^@码网*</b> */    while(length--)        _intsetSet(is,length+prepend,_intsetGetEncoded(is,length,curenc));    // valuelength),value);    // 更新 set size    is->length = intrev32ifbe(intrev32ifbe(is->length)+1);    return is;}

捣乱 2014-7-3

http://daoluan.net

原文地址：深入剖析 redis 数据结构 intset, 感谢原作者分享。

喜欢 (0)赏

[搞代码]

分享 (0)