redis整数集合

    2019年07月21日 Redis 字数:18624

整数集合

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

数据结构

typedef struct intset {
    // 表示存储的数据类型, 支持16位, 32位及64位整数
    uint32_t encoding;
    // 元素的个数
    uint32_t length;
    // 存储集合数据(从小到大排序)
    int8_t contents[];
} intset;

相关操作API

intsetNew: 创建一个新的整数集合

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

可以发现, 初始化一个整数集合就是为intset分配内存空间, 将数据类型设为int16_t, 此时的数组为null, 即没有分配内存空间.

intsetAdd: 往整数集合中添加一个新整数

// 添加成功, success为1, 添加失败success为0
intset *intsetAdd(intset *is, int64_t value, uint8_t *success) {
    // 判断新增元素所属的类型范围
    uint8_t valenc = _intsetValueEncoding(value);
    uint32_t pos;
    if (success) *success = 1;

    // 根据类型判断数组类型是否需要升级
    if (valenc > intrev32ifbe(is->encoding)) {
        return intsetUpgradeAndAdd(is,value);
    } else {
        // 不需要升级, 判断新添元素是否已经存在, 若存在,直接返回
        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;
}
  1. 判断新增元素所属的类型范围
    1. 如果新增元素大于当前集合的元素范围, 进行升级
    2. 否则判断新增元素是否已经存在
      1. 已存在, 直接返回
      2. 扩展数组空间
      3. 插入新元素

这个操作是整数就和的核心操作, 包含数组的升级操作, 数组空间扩展, 有序数组内元素查找, 有序数组内元素的插入, 由于在有序数组中插入元素, 也会涉及到元素的迁移.下面我们逐一解释.

数组的空间扩展

static intset *intsetResize(intset *is, uint32_t len) {
    uint32_t size = len*intrev32ifbe(is->encoding);
    is = zrealloc(is,sizeof(intset)+size);
    return is;
}
  1. 计算数组空间: 元素的个数与元素所占字节数的乘积
  2. 重新分配内存空间: intset结构体所占空间和数组所占内存空间之和

元素查找

// 查找元素所在数组中的位置, 若元素存在返回1, 并将索引位置存储在pos变量中
// 若不存在, 返回0, 并将value可以保存在数组中的索引位置保存在pos变量中
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;
    if (intrev32ifbe(is->length) == 0) {
        if (pos) *pos = 0;
        return 0;
    } else {
        // value大于数组中的最大值,说明不存在
        // 而且, 如果要把value插入数组中, value所属的索引位置为is->length
        if (value > _intsetGet(is,intrev32ifbe(is->length)-1)) {
            if (pos) *pos = intrev32ifbe(is->length);
            return 0;
        } else if (value < _intsetGet(is,0)) {
            // value小于数组中的最小值,说明不存在
            // 而且, 如果要把value插入数组中, value所属的索引位置为0
            if (pos) *pos = 0;
            return 0;
        }
    }
    
    // 否则进行二分查找
    while(max >= min) {
        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;
    }
}

数组升级

static intset *intsetUpgradeAndAdd(intset *is, int64_t value) {
    uint8_t curenc = intrev32ifbe(is->encoding);
    // 根据新值的范围确定值的类型
    uint8_t newenc = _intsetValueEncoding(value);
    int length = intrev32ifbe(is->length);
    
    // 由于需要升级, 新值必定是数组中的最大值或这最小值
    // 所以新值只能是新数组的第一个元素(最小值), 或者最后一个元素(最大值)
    int prepend = value < 0 ? 1 : 0;

    // 升级数组类型
    is->encoding = intrev32ifbe(newenc);
    // 扩充数组容量
    is = intsetResize(is,intrev32ifbe(is->length)+1);

    // 按照旧编码取出原来数组中的数据, 并以新的编码插入到新的数据中
    // 从后往前升级就不会出现元素被覆盖
    while(length--)
        _intsetSet(is,length+prepend,_intsetGetEncoded(is,length,curenc));

    // 如果是负数(最小值), 在索引0处插入新元素
    if (prepend)
        _intsetSet(is,0,value);
    else
        // 如果是正数(最大值), 在数组最后插入
        _intsetSet(is,intrev32ifbe(is->length),value);
    is->length = intrev32ifbe(intrev32ifbe(is->length)+1);
    return is;
}

insetFind: 检查给定的整数是否在集合中

uint8_t intsetFind(intset *is, int64_t value) {
    uint8_t valenc = _intsetValueEncoding(value);
    return valenc <= intrev32ifbe(is->encoding) && intsetSearch(is,value,NULL);
}
  1. 先判断查找的整数的类型是否小于等于当前数组的类型
    1. 如果不是, 直接返回不存在
    2. 否则使用二分查找查找该值是否存在.

intsetGet: 获取固定索引上的元素

// 获取的值存在value变量中
uint8_t intsetGet(intset *is, uint32_t pos, int64_t *value) {
    // 判断索引是否合法 
    if (pos < intrev32ifbe(is->length)) {
        // 使用索引获取值
        *value = _intsetGet(is,pos);
        return 1;
    }
    return 0;
}

static int64_t _intsetGet(intset *is, int pos) {
    // 使用整数类型和索引获取值
    return _intsetGetEncoded(is,pos,intrev32ifbe(is->encoding));
}


static int64_t _intsetGetEncoded(intset *is, int pos, uint8_t enc) {
    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;
    }
}

由于数组的类型是int8_t, 不能直接使用is->content[pos]直接获取, 这样获取到的值只有8位.所以需要将数组类型转换成相关类型, 然后使用memcpy拷贝.

intsetRemove: 删除整数集合中给定元素

intset *intsetRemove(intset *is, int64_t value, int *success) {
    uint8_t valenc = _intsetValueEncoding(value);
    uint32_t pos;
    if (success) *success = 0;

    if (valenc <= intrev32ifbe(is->encoding) && intsetSearch(is,value,&pos)) {
        uint32_t len = intrev32ifbe(is->length);
        if (success) *success = 1;
        if (pos < (len-1)) intsetMoveTail(is,pos+1,pos);
        is = intsetResize(is,len-1);
        is->length = intrev32ifbe(len-1);
    }
    return is;
}

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);
}
  1. 先判断要删除的值是否存在
    1. 不存在,则直接返回
    2. 否则找出要删除值在数组中的索引,然后进行删除, 由于要删除有序数组中的一个元素, 要涉及到元素搬移

为了提高元素搬移的效率, 使用memmove函数完成. memmove支持重叠内存的复制操作.

好处

  1. 灵活性

由于整数集合存在升级操作, 可以将int16_t, int32_t, int64_t三种类型的整数添加到集合中, 而不用担心出现类型错误.

  1. 节约内存

在强类型语言中, 一个数组可以同时保存int16_t, int32_t, int64_t三种类型的值, 最简单的是直接使用int64_t类型的数组作为集合的底层实现.但是当集合中只包含int16_t或者int32_t类型数据时, 会出现浪费内存的情况.

整数集合的实现中, 如果一直往集合中添加int16_t类型的值, 那么底层的实现一定是int16_t类型的数组, 只有将int32_t或者int64_t类型的数据添加到集合中时, 整数集合会对底层实现的数组进行升级.

请我喝杯咖啡

取消

感谢您的支持,我会继续写出更优秀的文章!

扫码支持
扫码支持
请我喝杯咖啡

打开微信扫一扫,即可进行扫码打赏哦

comments powered by Disqus