文章详情

短信预约信息系统项目管理师 报名、考试、查分时间动态提醒

请输入下面的图形验证码

提交验证

短信预约提醒成功

redis 5.0.7 源码阅读——整数集合intset

2021-05-12 22:30

关注

redis 5.0.7 源码阅读——整数集合intset

redis中整数集合intset相关的文件为:intset.h与intset.c

intset的所有操作与操作一个排序整形数组 int a[N]类似,只是根据类型做了内存上的优化。

一、数据结构

1 typedef struct intset {
2     uint32_t encoding;
3     uint32_t length;
4     int8_t contents[];
5 } intset;

intset的数据结构比较简单,使用了一个变长结构体,成员length记录当前成员数量,成员encoding记录当前的int类型,共有以下三种:

1 #define INTSET_ENC_INT16 (sizeof(int16_t))
2 #define INTSET_ENC_INT32 (sizeof(int32_t))
3 #define INTSET_ENC_INT64 (sizeof(int64_t))

并使用以下方法进行判断类型:

1 static uint8_t _intsetValueEncoding(int64_t v) {
2     if (v < INT32_MIN || v > INT32_MAX)
3         return INTSET_ENC_INT64;
4     else if (v < INT16_MIN || v > INT16_MAX)
5         return INTSET_ENC_INT32;
6     else
7         return INTSET_ENC_INT16;
8 }

intset是已排序好的整数集合,其大致结构如下:

1 

intset严格按照小端字节序进行存储,不论机器的字节序类型。如果是大端机器,需要进行转换,才进行存储。endianconv.h中有如下定义:

 1 #if (BYTE_ORDER == LITTLE_ENDIAN)
 2 #define memrev16ifbe(p) ((void)(0))
 3 #define memrev32ifbe(p) ((void)(0))
 4 #define memrev64ifbe(p) ((void)(0))
 5 #define intrev16ifbe(v) (v)
 6 #define intrev32ifbe(v) (v)
 7 #define intrev64ifbe(v) (v)
 8 #else
 9 #define memrev16ifbe(p) memrev16(p)
10 #define memrev32ifbe(p) memrev32(p)
11 #define memrev64ifbe(p) memrev64(p)
12 #define intrev16ifbe(v) intrev16(v)
13 #define intrev32ifbe(v) intrev32(v)
14 #define intrev64ifbe(v) intrev64(v)
15 #endif

具体实现在endianconv.c中,此处略过。

 

二、创建

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 }

刚创建好的intset是空的,默认使用最小的类型。其结构为:

1 

 

三、 操作

若有以下intset:

1 

现在插入一个数字6,需要调用以下方法:

 1 
 2 intset *intsetAdd(intset *is, int64_t value, uint8_t *success) {
 3     uint8_t valenc = _intsetValueEncoding(value);
 4     uint32_t pos;
 5     if (success) *success = 1;
 6 
 7     
10     if (valenc > intrev32ifbe(is->encoding)) {
11         
12         return intsetUpgradeAndAdd(is,value);
13     } else {
14         
17         if (intsetSearch(is,value,&pos)) {
18             if (success) *success = 0;
19             return is;
20         }
21 
22         is = intsetResize(is,intrev32ifbe(is->length)+1);
23         if (pos < intrev32ifbe(is->length)) intsetMoveTail(is,pos,pos+1);
24     }
25 
26     _intsetSet(is,pos,value);
27     is->length = intrev32ifbe(intrev32ifbe(is->length)+1);
28     return is;
29 }

因int16_t足以存储数字“6”,所以新插入数字的int类型与intset一致,然后需要查找插入的pos:

 1 static uint8_t intsetSearch(intset *is, int64_t value, uint32_t *pos) {
 2     int min = 0, max = intrev32ifbe(is->length)-1, mid = -1;
 3     int64_t cur = -1;
 4 
 5     
 6     if (intrev32ifbe(is->length) == 0) {
 7         if (pos) *pos = 0;
 8         return 0;
 9     } else {
10         
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 }

因intset是已排序好的,所以使用了二分查找。过程如下

 1 

6在intset中不存在,查找到需要插入到pos=5的位置,此时首先要扩展intset的content:

1 static intset *intsetResize(intset *is, uint32_t len) {
2     uint32_t size = len*intrev32ifbe(is->encoding);
3     is = zrealloc(is,sizeof(intset)+size);
4     return is;
5 }

扩展后:

1 

然后把原来在pos=5及之后的所有的元素向后移一格:

 1 static void intsetMoveTail(intset *is, uint32_t from, uint32_t to) {
 2     void *src, *dst;
 3     uint32_t bytes = intrev32ifbe(is->length)-from;
 4     uint32_t encoding = intrev32ifbe(is->encoding);
 5 
 6     if (encoding == INTSET_ENC_INT64) {
 7         src = (int64_t*)is->contents+from;
 8         dst = (int64_t*)is->contents+to;
 9         bytes *= sizeof(int64_t);
10     } else if (encoding == INTSET_ENC_INT32) {
11         src = (int32_t*)is->contents+from;
12         dst = (int32_t*)is->contents+to;
13         bytes *= sizeof(int32_t);
14     } else {
15         src = (int16_t*)is->contents+from;
16         dst = (int16_t*)is->contents+to;
17         bytes *= sizeof(int16_t);
18     }
19     memmove(dst,src,bytes);
20 }

移动后:

1 

其使用memmove,并不全修改未覆盖到的内存,所以此时pos=5的值 还是7

最后修改pos=5的值:

 1 static void _intsetSet(intset *is, int pos, int64_t value) {
 2     uint32_t encoding = intrev32ifbe(is->encoding);
 3 
 4     if (encoding == INTSET_ENC_INT64) {
 5         ((int64_t*)is->contents)[pos] = value;
 6         memrev64ifbe(((int64_t*)is->contents)+pos);
 7     } else if (encoding == INTSET_ENC_INT32) {
 8         ((int32_t*)is->contents)[pos] = value;
 9         memrev32ifbe(((int32_t*)is->contents)+pos);
10     } else {
11         ((int16_t*)is->contents)[pos] = value;
12         memrev16ifbe(((int16_t*)is->contents)+pos);
13     }
14 }

修改后并增加了length:

1 

 

如果此时要插入的数字是65536,超出了int16_t所能表示的范围,要先进行扩展int类型操作:

 1 static intset *intsetUpgradeAndAdd(intset *is, int64_t value) {
 2     uint8_t curenc = intrev32ifbe(is->encoding);
 3     uint8_t newenc = _intsetValueEncoding(value);
 4     int length = intrev32ifbe(is->length);
 5     int prepend = value < 0 ? 1 : 0;
 6 
 7     
 8     is->encoding = intrev32ifbe(newenc);
 9     is = intsetResize(is,intrev32ifbe(is->length)+1);
10 
11     
14     while(length--)
15         _intsetSet(is,length+prepend,_intsetGetEncoded(is,length,curenc));
16 
17     
18     if (prepend)
19         _intsetSet(is,0,value);
20     else
21         _intsetSet(is,intrev32ifbe(is->length),value);
22     is->length = intrev32ifbe(intrev32ifbe(is->length)+1);
23     return is;
24 }

因其超出原来的int类型所能表示的范围,若为正数,一定是最大的,则应该插入在intset最后,否则应该在最前面。扩展完之后,从后往前将原来的数字,以新的int类型,放置在新的位置上,保证不会有未处理的数字被覆盖,处理完整。

 

删除操作:

 1 intset *intsetRemove(intset *is, int64_t value, int *success) {
 2     uint8_t valenc = _intsetValueEncoding(value);
 3     uint32_t pos;
 4     if (success) *success = 0;
 5 
 6     if (valenc <= intrev32ifbe(is->encoding) && intsetSearch(is,value,&pos)) {
 7         uint32_t len = intrev32ifbe(is->length);
 8 
 9         
10         if (success) *success = 1;
11 
12         
13         if (pos < (len-1)) intsetMoveTail(is,pos+1,pos);
14         is = intsetResize(is,len-1);
15         is->length = intrev32ifbe(len-1);
16     }
17     return is;
18 }

找到指定元素之后,直接把后面的内存移至前面,然后resize。

 

redis 5.0.7 下载链接

http://download.redis.io/releases/redis-5.0.7.tar.gz

源码阅读顺序参考:

https://github.com/huangz1990/blog/blob/master/diary/2014/how-to-read-redis-source-code.rst

 

阅读原文内容投诉

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

软考中级精品资料免费领

  • 历年真题答案解析
  • 备考技巧名师总结
  • 高频考点精准押题
  • 2024年上半年信息系统项目管理师第二批次真题及答案解析(完整版)

    难度     813人已做
    查看
  • 【考后总结】2024年5月26日信息系统项目管理师第2批次考情分析

    难度     354人已做
    查看
  • 【考后总结】2024年5月25日信息系统项目管理师第1批次考情分析

    难度     318人已做
    查看
  • 2024年上半年软考高项第一、二批次真题考点汇总(完整版)

    难度     435人已做
    查看
  • 2024年上半年系统架构设计师考试综合知识真题

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

AI推送时光机
位置:首页-资讯-数据库
咦!没有更多了?去看看其它编程学习网 内容吧
首页课程
资料下载
问答资讯