Redis数据结构源码解析(七) 整数集合

概念

整数集合（intset）是一个有序的、存储整型数据的结构。

关键字：有序的、整型的

conding决定了的element的长度，对应关系如下

基本结构

intset

typedef struct intset {  
    //编码
    uint32_t encoding;
    //元素个数
    uint32_t length;
    // 柔性数组，根据encoding 决定几个字节表示一个数组
    int8_t contents[];
} intset;

可以看到底层是通过数组实现

基本操作

查询

uint8_t intsetFind(intset *is, int64_t value) {  
　　uint8_t valenc = _intsetValueEncoding(value); //判断编码方式
　　//编码方式如果大于当前intset的编码方式，直接返回0。否则调用intsetSearch函数进行查找
　　return valenc <= intrev32ifbe(is->encoding) && intsetSearch(is,value,NULL);
}

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;  
    /*如果intset中没有元素，直接返回0 */
    if (intrev32ifbe(is->length) == 0) {  
      if (pos) *pos = 0;
      return 0;
    } else {
    /* 如果元素大于最大值或者小于最小值，直接返回0 */
    if (value > _intsetGet(is,max)) {  
      if (pos) *pos = intrev32ifbe(is->length);
        return 0;
    } else if (value < _intsetGet(is,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) { //查找到返回1，未查找到返回0  
      if (pos) *pos = mid;
      return 1;
    } else {
      if (pos) *pos = min;
      return 0;
     }
  }
}

其实比较简单，就是先做了一些基础的结构判断，因为是有序的可以通过二分查找快速查询。

总结

这应该是最简单的一个类型了，就是一个基于数组的有序集合，增删改查都使用到了二分查找。

致谢

• Redis源码解析 - 有赞技术团队