redis源码剖析(5)：基础数据结构inset

2024-04-27 22:48
文章标签 基础 源码 剖析 数据结构 redis inset

本文主要是介绍redis源码剖析(5)：基础数据结构inset，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

目录

 

1、intset概述

2、inset分析

2.1 定义

2.2 新增元素

2.3 升级

2.4 总结

1、intset概述

       整数集合是 redis 对外数据结构set的底层实现之一，当集合元素不大于设定值并且元素都是整数时，就会用intset作为set的底层数据结构。

2、inset分析

2.1 定义

inset结构体定义如下：

typedef struct intset {uint32_t encoding;  // 编码方式，一个元素所需要的内存大小uint32_t length;    // 集合长度int8_t contents[];  // 集合数组
} intset;

  • encoding为inset的编码方式，有3种编码方式，分别对应不同范围的整型：

      #define INTSET_ENC_INT16 (sizeof(int16_t))  // -32768~32767#define INTSET_ENC_INT32 (sizeof(int32_t))  // -2147483648~2147483647#define INTSET_ENC_INT64 (sizeof(int64_t))  // -2^63~2^63-1

    intset的编码是由最大的一个数决定的，如果有一个数是int64，那么整个inset的编码都是int64。

  • length是inset的整数个数
  • contents整数数组

   intset的内存是连续的，所有的数据增删改查操作都是在内存地址偏移的基础上进行的，并且整数的保存也是有序的，一个保存了5个int16的intset的内存示意图如下：

intest

由于intset是在内存上直接操作赋值，并且所存储的值都超过了一个字节，所以需要考虑大小端的问题：

大端模式，是指数据的高字节保存在内存的低地址中，而数据的低字节保存在内存的高地址中，这样的存储模式有点儿类似于把数据当作字符串顺序处理：地址由小向大增加，而数据从高位往低位放；这和我们的阅读习惯一致。
小端模式，是指数据的高字节保存在内存的高地址中，而数据的低字节保存在内存的低地址中，这种存储模式将地址的高低和数据位权有效地结合起来，高地址部分权值高，低地址部分权值低。

     redis 的所有存储方式都是小端存储，在endianconv.h中有一段大小端的宏定义，如果当前cpu的字节序为大端就进行相应的转换：

#if (BYTE_ORDER == LITTLE_ENDIAN)
#define memrev16ifbe(p)
#define memrev32ifbe(p)
#define memrev64ifbe(p)
#define intrev16ifbe(v) (v)
#define intrev32ifbe(v) (v)
#define intrev64ifbe(v) (v)
#else
#define memrev16ifbe(p) memrev16(p)
#define memrev32ifbe(p) memrev32(p)
#define memrev64ifbe(p) memrev64(p)
#define intrev16ifbe(v) intrev16(v)
#define intrev32ifbe(v) intrev32(v)
#define intrev64ifbe(v) intrev64(v)
#endif

      在intset相关的源码中有很多intrev32ifbe之类的操作就是在进行大小端转换。大小端深入的一些知识点就不在这做详解，可以自行google或百度。

2.2 新增元素

      这里针对intset的新增元素的过程做一个解析，因为这个过程涉及到了intset的升级、查找和插入。
      首先看新增元素的主体函数：

intset *intsetAdd(intset *is, int64_t value, uint8_t *success) {    // 新增uint8_t valenc = _intsetValueEncoding(value);   // 获取对应value编码uint32_t pos;if (success) *success = 1;if (valenc > intrev32ifbe(is->encoding)) {  // 编码大于当前，升级新增/* This always succeeds, so we don't need to curry *success. */return intsetUpgradeAndAdd(is,value);   // 升级并新增} else {if (intsetSearch(is,value,&pos)) {  // 查找是否存在，pos为小于value的最大值的posif (success) *success = 0;return is;}is = intsetResize(is,intrev32ifbe(is->length)+1);   // 重新多申请一个空间if (pos < intrev32ifbe(is->length)) intsetMoveTail(is,pos,pos+1);   // 如果没有找到pos是小于该数字的前一个， 将pos后数据后移一位}_intsetSet(is,pos,value);is->length = intrev32ifbe(intrev32ifbe(is->length)+1);return is;
}

       这个函数获取了value值对应的编码，这个编码是根据3种编码的数据范围确定的。如果待插入数据的编码大于当前intset的编码，就需要进行升级，这个先跳过，我们先看正常的新增流程。
为了确保intset元素的唯一性，再插入之前会进行一次查找，intsetSearch函数定义如下：

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;/* The value can never be found when the set is empty */if (intrev32ifbe(is->length) == 0) {    // intset空值判断if (pos) *pos = 0;return 0;} else {if (value > _intsetGet(is,intrev32ifbe(is->length)-1)) {if (pos) *pos = intrev32ifbe(is->length);   // 如果value大于当前intset的最大值，将pos赋值为lengthreturn 0;} else if (value < _intsetGet(is,0)) {if (pos) *pos = 0;  // 如果value小于当前intset的最小值，将pos赋值为0return 0;}}while(max >= min) { // 二分查找mid = ((unsigned int)min + (unsigned int)max) >> 1; // (min+max)/2cur = _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;}
}

       上述函数的作用就是利用intset有序的特性，通过二分法对目标value进行查找，如果找到返回1，反之返回0，pos作为引用传入函数中，会被赋值为value在intset中对应的位置。
  intsetSearch中多次调用的_intsetGet是用来获取对应pos的value值的函数：

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) {    // 根据encode获取对应的值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;}
}

      可以看到intset在获取值的时候都是通过地址偏移、内存拷贝，然后进行大小端转换处理完成的。

      继续之前的新增元素流程，当查不到对应value时，会在原有内存的基础上进行realloc，多申请一个intset->encoding的内存。由于intset的内存为连续，因此插入时，比value大的元素都要向后移动一个intset->encoding，也就是intsetMoveTail函数干的活：

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); // 由于移动前后地址会有重叠，因此要利用memmove进行内存拷贝 memcpy无法保障结果正确性
}

       由于移动的操作是在原有内存地址基础上进行的，因此在这里不能用memcpy进行内存拷贝，需要用memmove。在内存重叠的情况下，memcpy在拷贝的过程中，可能部分地址在被拷贝之前就被新的值覆盖了，导致拷贝这部分地址时拷贝的并不是我们期望的值。依旧是老套路，感兴趣自己去google或百度吧！
       最后的_intsetSet和_intsetGet差不多，就不多讲了。

2.3 升级

      上面只介绍了intset普通的新增场景，那么当插入的value大于当前intset的encode时就需要对intset进行升级，以适应更大的值：

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;/* First set new encoding and resize */is->encoding = intrev32ifbe(newenc);is = intsetResize(is,intrev32ifbe(is->length)+1);/* Upgrade back-to-front so we don't overwrite values.* Note that the "prepend" variable is used to make sure we have an empty* space at either the beginning or the end of the intset. */while(length--) // 从尾部开始，将原有数据进行迁移_intsetSet(is,length+prepend,_intsetGetEncoded(is,length,curenc));/* Set the value at the beginning or the end. */if (prepend)    // 小于0在集合头部_intsetSet(is,0,value);else    // 在集合尾部_intsetSet(is,intrev32ifbe(is->length),value);is->length = intrev32ifbe(intrev32ifbe(is->length)+1);return is;
}

        首先当需要对原有intset进行升级时，插入的元素一定是大于当前intset的最大值或者小于当前intset的最小值的，因此带插入的value一定是在首尾，只需判断其正负即可。
       升级的操作主要是将原本数据的内存地址大小进行一个统一的变更，从原intset的length+prepend开始，一个一个扩展迁移。
       进行完扩展迁移之后把带插入的元素插入到头或尾即可。
       一个INTSET_ENC_INT16->INTSET_ENC_INT32的升级示例如下图：

intsetupgrade

2.4 总结

intset主要有以下特性：

  1. 内存连续，数值存储有序、无重复
  2. 有三种编码方式，通过升级的方式进行编码切换
  3. 不支持降级
  4. 小端存储

其他一些删除、随机获取value等api就不详细介绍了。老套路，源码在intset.h和intset.c中。

这篇关于redis源码剖析(5)：基础数据结构inset的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/941722。

相关文章

JAVA智听未来一站式有声阅读平台听书系统小程序源码

JAVA智听未来一站式有声阅读平台听书系统小程序源码

智听未来，一站式有声阅读平台听书系统 🌟&nbsp;开篇：遇见未来，从“智听”开始 在这个快节奏的时代，你是否渴望在忙碌的间隙，找到一片属于自己的宁静角落？是否梦想着能随时随地，沉浸在知识的海洋，或是故事的奇幻世界里？今天，就让我带你一起探索“智听未来”——这一站式有声阅读平台听书系统，它正悄悄改变着我们的阅读方式，让未来触手可及！ 📚&nbsp;第一站：海量资源，应有尽有 走进“智听
阅读更多...
【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
零基础学习Redis(10) -- zset类型命令使用

零基础学习Redis(10) -- zset类型命令使用

zset是有序集合，内部除了存储元素外，还会存储一个score，存储在zset中的元素会按照score的大小升序排列，不同元素的score可以重复，score相同的元素会按照元素的字典序排列。 1. zset常用命令 1.1 zadd  zadd key [NX | XX] [GT | LT]   [CH] [INCR] score member [score member ...]
阅读更多...
6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

上篇：6.1.数据结构-c/c++模拟实现堆上篇（向下，上调整算法，建堆，增删数据）-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小)： 2.2 C语言代码（手写堆） 2.3 C++代码（使用优先级队列 priority_queue）
阅读更多...
Java ArrayList扩容机制 （源码解读）

Java ArrayList扩容机制 （源码解读）

结论：初始长度为10，若所需长度小于1.5倍原长度，则按照1.5倍扩容。若不够用则按照所需长度扩容。 一. 明确类内部重要变量含义         1：数组默认长度         2:这是一个共享的空数组实例，用于明确创建长度为0时的ArrayList ，比如通过 new ArrayList<>(0)，ArrayList 内部的数组 elementData 会指向这个 EMPTY_EL
阅读更多...
如何在Visual Studio中调试.NET源码

如何在Visual Studio中调试.NET源码

今天偶然在看别人代码时，发现在他的代码里使用了Any判断List<T>是否为空。 我一般的做法是先判断是否为null，再判断Count。 看了一下Count的源码如下： 1 [__DynamicallyInvokable]2 public int Count3 {4 [__DynamicallyInvokable]5 get
阅读更多...
工厂ERP管理系统实现源码（JAVA）

工厂ERP管理系统实现源码（JAVA）

工厂进销存管理系统是一个集采购管理、仓库管理、生产管理和销售管理于一体的综合解决方案。该系统旨在帮助企业优化流程、提高效率、降低成本，并实时掌握各环节的运营状况。 在采购管理方面，系统能够处理采购订单、供应商管理和采购入库等流程，确保采购过程的透明和高效。仓库管理方面，实现库存的精准管理，包括入库、出库、盘点等操作，确保库存数据的准确性和实时性。 生产管理模块则涵盖了生产计划制定、物料需求计划、
阅读更多...
【Linux 从基础到进阶】Ansible自动化运维工具使用

【Linux 从基础到进阶】Ansible自动化运维工具使用

Ansible自动化运维工具使用 Ansible 是一款开源的自动化运维工具，采用无代理架构（agentless），基于 SSH 连接进行管理，具有简单易用、灵活强大、可扩展性高等特点。它广泛用于服务器管理、应用部署、配置管理等任务。本文将介绍 Ansible 的安装、基本使用方法及一些实际运维场景中的应用，旨在帮助运维人员快速上手并熟练运用 Ansible。 1. Ansible的核心概念
阅读更多...
AI基础 L9 Local Search II 局部搜索

AI基础 L9 Local Search II 局部搜索

Local Beam search 对于当前的所有k个状态，生成它们的所有可能后继状态。 检查生成的后继状态中是否有任何状态是解决方案。 如果所有后继状态都不是解决方案，则从所有后继状态中选择k个最佳状态。 当达到预设的迭代次数或满足某个终止条件时，算法停止。 — Choose k successors randomly, biased towards good ones — Close
阅读更多...
《数据结构（C语言版）第二版》第八章-排序（8.3-交换排序、8.4-选择排序）

《数据结构（C语言版）第二版》第八章-排序（8.3-交换排序、8.4-选择排序）

8.3 交换排序 8.3.1 冒泡排序 【算法特点】 (1) 稳定排序。 (2) 可用于链式存储结构。 (3) 移动记录次数较多，算法平均时间性能比直接插入排序差。当初始记录无序，n较大时， 此算法不宜采用。 #include <stdio.h>#include <stdlib.h>#define MAXSIZE 26typedef int KeyType;typedef char In
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2