数据结构

image.png

  1. typedef struct intset {
  2.     uint32_t encoding;
  3.     uint32_t length;
  4.     int8_t contents[];//一个字节
  5. } intset;
  7. int main() {
  9.     struct intset *set = malloc(sizeof(struct intset));
  10.     set->encoding = 1;
  11.     set->length = 2;
  12.     set->contents[0] = 1;
  13.     set->contents[1] = 22;
  15.     printf("内存地址0:%p\n", *&set);
  16.     printf("内存地址1:%p\n", &set->encoding);
  17.     printf("内存地址2:%p\n", &set->length);
  18.     printf("内存地址3:%p\n", &set->contents[0]);
  19.     printf("内存地址4:%p\n", &set->contents[1]);
  21.     free(set);
  22. }
  23. //output如下
  24. //内存地址0:0x7fd8b0c05a20
  25. //内存地址1:0x7fd8b0c05a20
  26. //内存地址2:0x7fd8b0c05a24
  27. //内存地址3:0x7fd8b0c05a28
  28. //内存地址4:0x7fd8b0c05a29

在Redis的整数集合中， contents 数组的大小取决于 encoding的编码

  1. #define INTSET_ENC_INT16 (sizeof(int16_t))
  2. #define INTSET_ENC_INT32 (sizeof(int32_t))
  3. #define INTSET_ENC_INT64 (sizeof(int64_t))
  4. //这里还涉及到字节顺

整数集合操作

创建

  • 创建一个结构体(malloc)，初始化 encoding length

    1. intset *intsetNew(void) {
    2.   intset *is = zmalloc(sizeof(intset));
    3.   is->encoding = intrev32ifbe(INTSET_ENC_INT16);
    4.   is->length = 0;
    5.   return is;
    6. }

    插入

    image.png

    查找(数据是否存在)

  • intset没有数据，返回

  • value大于最大 || value小于最小 ， 返回

  • 二分查找找到value （二分查找），算法无处不在

    • 数据存在，返回1

    • 数据不存在反问2

      1. static uint8_t intsetSearch(intset *is, int64_t value, uint32_t *pos) {
      2. //数组长度
      3. int min = 0, max = intrev32ifbe(is->length)-1, mid = -1;
      4. int64_t cur = -1;
      6. //整数集合没有数据
      7. if (intrev32ifbe(is->length) == 0) {
      8.    if (pos) *pos = 0;
      9.    return 0;
      10. } else {
      11.    //value大于最大 || value小于最小 ， 返回
      12.    if (value > _intsetGet(is,max)) {
      13.        if (pos) *pos = intrev32ifbe(is->length);
      14.        return 0;
      15.    } else if (value < _intsetGet(is,0)) {
      16.        if (pos) *pos = 0;
      17.        return 0;
      18.    }
      19. }
      20. //二分
      21. while(max >= min) {
      22.    mid = ((unsigned int)min + (unsigned int)max) >> 1;
      23.    cur = _intsetGet(is,mid);
      24.    if (value > cur) {
      25.        min = mid+1;
      26.    } else if (value < cur) {
      27.        max = mid-1;
      28.    } else {
      29.        break;
      30.    }
      31. }
      32. //是否找到数据
      33. if (value == cur) {
      34.    if (pos) *pos = mid;
      35.    return 1;
      36. } else {
      37.    if (pos) *pos = min;
      38.    return 0;
      39. }
      40. }

      删除

      image.png

      字节序

      大端字节序和小端字节序
      https://blog.erratasec.com/2016/11/how-to-teach-endian.html#.YjKhpxBByAl
      encoding如何进行判定

      1. /* Return the required encoding for the provided value. */
      2. static uint8_t _intsetValueEncoding(int64_t v) {
      3. //超过32位最大的和小于32位最小的，使用64位
      4. if (v < INT32_MIN || v > INT32_MAX)
      5.    return INTSET_ENC_INT64;
      6. else if (v < INT16_MIN || v > INT16_MAX)
      7.    //超过16位最大的和小于16位最小的，使用32位
      8.    return INTSET_ENC_INT32;
      9. else
      10.    //剩下的全部使用16位
      11.    return INTSET_ENC_INT16;
      12. }