经验首页 前端设计 程序设计 Java相关 移动开发 数据库/运维 软件/图像 大数据/云计算 其他经验
当前位置:技术经验 » 数据库/运维 » Redis » 查看文章
Redis 设计与实现 9:五大数据类型之集合
来源:cnblogs  作者:小新是也  时间:2021/1/11 9:29:01  对本文有异议

集合对象的编码有两种:intsethashtable

编码一:intset

intset 的结构

整数集合 intset 是集合底层的实现之一,从名字就可以看出,这是专门为整数提供的集合类型。
其结构定义如下,在 intset.h

  1. typedef struct intset {
  2. // 编码方式
  3. uint32_t encoding;
  4. // 集合包含的元素数量
  5. uint32_t length;
  6. // 保存元素的数组
  7. int8_t contents[];
  8. } intset;
  • contents 中的元素,按照从小到大排序,并且不存在重复项。虽然元素定义是 int8_t 类型,但实际上,contents 存的元素类型取决于 encoding
  • encoding 有几个类型,定义在 intset.c
  1. #define INTSET_ENC_INT16 (sizeof(int16_t))
  2. #define INTSET_ENC_INT32 (sizeof(int32_t))
  3. #define INTSET_ENC_INT64 (sizeof(int64_t))
encoding 类型 字节
INTSET_ENC_INT16 int16_t 2
INTSET_ENC_INT32 int32_t 4
INTSET_ENC_INT64 int64_t 8

下图展示了包含了 1、2、3 三个整数元素的集合结构:

常见操作源码分析

源码在 intset.c

1. 创建空集合

创建一个空的 intset,一开始的编码是最小的 INTSET_ENC_INT16

  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. }

2. 搜索

因为集合中的整数存的是有序的,所以查找是用二分查找,时间复杂度 \(O(nlogn)\)

  1. uint8_t intsetFind(intset *is, int64_t value) {
  2. uint8_t valenc = _intsetValueEncoding(value);
  3. // 如果 value 的编码大于集合的编码,那肯定是不存在的
  4. // intsetSearch 是更底层的搜索,实现源码在下面,是个二分查找
  5. return valenc <= intrev32ifbe(is->encoding) && intsetSearch(is,value,NULL);
  6. }
  7. // 集合搜索,是二分查找。
  8. // 如果找到了,返回1,并且把位置设置到 pos 变量中
  9. // 如果找不到,返回0,可以插入值的位置设置到 pos 变量中
  10. static uint8_t intsetSearch(intset *is, int64_t value, uint32_t *pos) {
  11. int min = 0, max = intrev32ifbe(is->length)-1, mid = -1;
  12. int64_t cur = -1;
  13. // 数组判空
  14. if (intrev32ifbe(is->length) == 0) {
  15. if (pos) *pos = 0;
  16. return 0;
  17. } else {
  18. // 看是否比最大的大或者比最小的小,这种情况也直接返回不存在
  19. if (value > _intsetGet(is,max)) {
  20. if (pos) *pos = intrev32ifbe(is->length);
  21. return 0;
  22. } else if (value < _intsetGet(is,0)) {
  23. if (pos) *pos = 0;
  24. return 0;
  25. }
  26. }
  27. // 二分查找
  28. while(max >= min) {
  29. mid = ((unsigned int)min + (unsigned int)max) >> 1;
  30. cur = _intsetGet(is,mid);
  31. if (value > cur) {
  32. min = mid+1;
  33. } else if (value < cur) {
  34. max = mid-1;
  35. } else {
  36. break;
  37. }
  38. }
  39. if (value == cur) {
  40. if (pos) *pos = mid;
  41. return 1;
  42. } else {
  43. if (pos) *pos = min;
  44. return 0;
  45. }
  46. }

3. 指定位置获取

  1. // 如果获取得到,返回1,找到的值设置进 value 变量
  2. // 如果获取不到,返回 0
  3. uint8_t intsetGet(intset *is, uint32_t pos, int64_t *value) {
  4. if (pos < intrev32ifbe(is->length)) {
  5. *value = _intsetGet(is,pos);
  6. return 1;
  7. }
  8. // 位置如果大于长度,肯定就获取不到的
  9. return 0;
  10. }
  11. static int64_t _intsetGet(intset *is, int pos) {
  12. // 根据编码获取
  13. return _intsetGetEncoded(is,pos,intrev32ifbe(is->encoding));
  14. }
  15. static int64_t _intsetGetEncoded(intset *is, int pos, uint8_t enc) {
  16. int64_t v64;
  17. // ...
  18. // 根据编码的长度,从对应的位置后拷贝对应的字节返回
  19. if (enc == INTSET_ENC_INT64) {
  20. memcpy(&v64,((int64_t*)is->contents)+pos,sizeof(v64));
  21. memrev64ifbe(&v64);
  22. return v64;
  23. } else if (enc == INTSET_ENC_INT32) {
  24. // ...
  25. return v32;
  26. } else {
  27. // ...
  28. }
  29. }

4. 插入

插入的步骤如下:

  1. 检查如果插入的元素的编码大于集合编码,进行升级并插入
  2. 如果不需要升级,检查元素是否存在,如果存在,则直接返回
  3. 如果元素不存在,则扩容,在元素对应的位置插入值(它后面的元素则都往后挪)
  1. intset *intsetAdd(intset *is, int64_t value, uint8_t *success) {
  2. // 插入的元素的编码
  3. uint8_t valenc = _intsetValueEncoding(value);
  4. uint32_t pos;
  5. if (success) *success = 1;
  6. // 如果插入的元素的编码比当前集合的编码大,需要进行升级
  7. if (valenc > intrev32ifbe(is->encoding)) {
  8. return intsetUpgradeAndAdd(is,value);
  9. } else {
  10. // 先查找看元素已存在,如果存在,则直接返回
  11. if (intsetSearch(is,value,&pos)) {
  12. if (success) *success = 0;
  13. return is;
  14. }
  15. // 扩容
  16. is = intsetResize(is,intrev32ifbe(is->length)+1);
  17. // 将 pos 后的内存块向后挪动一个位置,给新值腾空间
  18. if (pos < intrev32ifbe(is->length)) intsetMoveTail(is,pos,pos+1);
  19. }
  20. // 把新值设置进 pos 位置上
  21. _intsetSet(is,pos,value);
  22. is->length = intrev32ifbe(intrev32ifbe(is->length)+1);
  23. return is;
  24. }
  25. static void intsetMoveTail(intset *is, uint32_t from, uint32_t to) {
  26. void *src, *dst;
  27. uint32_t bytes = intrev32ifbe(is->length)-from;
  28. uint32_t encoding = intrev32ifbe(is->encoding);
  29. if (encoding == INTSET_ENC_INT64) {
  30. src = (int64_t*)is->contents+from;
  31. dst = (int64_t*)is->contents+to;
  32. bytes *= sizeof(int64_t);
  33. } else if (encoding == INTSET_ENC_INT32) {
  34. // ...
  35. } else {
  36. // ...
  37. }
  38. memmove(dst,src,bytes);
  39. }

5. 升级

intset 插入元素的时候,会先检测元素的长度,判断元素应该属于什么编码(encoding)。
如果当前元素的编码,大于 intset 的编码(整个集合最长的编码),集合将进行升级后,才添加元素。

升级整数集合并添加新元素共分为 3 步进行:

  1. 根据新元素的编码,扩展整数集合底层数组的空间大小,并为新元素分配空间。
  2. 将底层数组现有的所有元素都转换成与新元素相同的类型,并将类型转换后的元素放置到正确的位上,而且在放置元素的过程中,需要继续维持底层数组的有序性质不变。
  3. 将新元素添加到底层数组里面。
  1. // 升级并插入新值
  2. static intset *intsetUpgradeAndAdd(intset *is, int64_t value) {
  3. // 当前编码
  4. uint8_t curenc = intrev32ifbe(is->encoding);
  5. // 新的编码
  6. uint8_t newenc = _intsetValueEncoding(value);
  7. // 当前元素个数
  8. int length = intrev32ifbe(is->length);
  9. // value 的编码比其他的都大,那么这个 value 不是最大值就是最小值。
  10. // 如果是最大值就放在数组最后,最小值就放在数组最前面
  11. int prepend = value < 0 ? 1 : 0;
  12. // 设置 encoding 属性为新编码
  13. is->encoding = intrev32ifbe(newenc);
  14. // 根据新编码给扩展集合需要的空间,实现源码在下面
  15. is = intsetResize(is,intrev32ifbe(is->length)+1);
  16. // 从尾到头依次遍历挪动原来的值。为什么不从头到尾呢?因为数组是同一个,从头到尾会覆盖原来的值
  17. while(length--)
  18. // _intsetGetEncoded(is,length,curenc) 表示根据编码和位置获取值
  19. // prepend 为了确保如果 value 是最小的值,那么前面会留一个空位置
  20. _intsetSet(is,length+prepend,_intsetGetEncoded(is,length,curenc));
  21. if (prepend)
  22. // 当 value 是最小值时,放在第一个空位
  23. _intsetSet(is,0,value);
  24. else
  25. // 当 value 是最大值,放在最后一个位置
  26. _intsetSet(is,intrev32ifbe(is->length),value);
  27. // 长度加 1
  28. is->length = intrev32ifbe(intrev32ifbe(is->length)+1);
  29. return is;
  30. }
  31. // 整数集合重新分配内存
  32. static intset *intsetResize(intset *is, uint32_t len) {
  33. // 根据编码算出集合需要的空间
  34. uint32_t size = len*intrev32ifbe(is->encoding);
  35. // 分配内存
  36. is = zrealloc(is,sizeof(intset)+size);
  37. return is;
  38. }

6. 降级

并没有降级

7. 删除

删除的步骤如下:

  1. 找到值的位置 pos
  2. pos 后面的元素向前挪,覆盖掉 pos 上的元素
  3. 缩容:长度减一
  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. if (success) *success = 1;
  9. // 把删除位置后面的元素都挪到前面来,直接覆盖掉 pos 的元素
  10. if (pos < (len-1)) intsetMoveTail(is,pos+1,pos);
  11. // 再缩容
  12. is = intsetResize(is,len-1);
  13. is->length = intrev32ifbe(len-1);
  14. }
  15. return is;
  16. }

编码二:hashtable

hashtable 编码用的是字典 dict 作为底层实现,关于 dict,具体的前文 Redis 设计与实现 4:字典 dict 已经写了,包括了 dict 基本操作的源码解读。

下图展示了包含 "a"、"b"、"c"、"d" 四个元素的集合结构:

编码的转换

当集合对象满足以下两个条件时,采用 intset 编码:

  1. 所有元素都是整数
  2. 元素数量不超过512个(用通过 set-max-intset-entries 配置项配置)

不能同时满足以上两个条件,则采用 tablehash 编码。

原文链接:http://www.cnblogs.com/chenchuxin/p/14236875.html

 友情链接:直通硅谷  点职佳  北美留学生论坛

本站QQ群:前端 618073944 | Java 606181507 | Python 626812652 | C/C++ 612253063 | 微信 634508462 | 苹果 692586424 | C#/.net 182808419 | PHP 305140648 | 运维 608723728

W3xue 的所有内容仅供测试,对任何法律问题及风险不承担任何责任。通过使用本站内容随之而来的风险与本站无关。
关于我们  |  意见建议  |  捐助我们  |  报错有奖  |  广告合作、友情链接(目前9元/月)请联系QQ:27243702 沸活量
皖ICP备17017327号-2 皖公网安备34020702000426号