Redis【2】- SDS源码分析

redis

1 简介&基础用法

Redis 中用得最多的就是字符串，在 C 语言中其实可以直接使用 char* 字符数组来实现字符串，也有很多可以直接使用得函数。但是 Redis 并没有使用 C 语言原生的字符串，而是自己实现了一个 SDS（简单动态字符串，Simple Dynamic String）。

Redis 的 SDS 兼容了 C 语言的字符串类型的用法，

下面是 Redis 中 string 类型最常用的用法：

本地:0>set hello world
OK
本地:0>get hello
world
本地:0>type hello
string
本地:0>strlen hello
5

2 为什么 Redis 自实现字符串？

2.1 存储二进制的限制

C 语言的 char* 是以 \0 作为结束字符串的标识，如果需要存储的数据中本身就含有 \0 ，那就没有办法正确表示，而像图像这种数据，一般存储下来都是二进制格式的，所以 Redis 不能直接使用 char*。下面是 C 语言的 \0 对字符串长度判断的影响：

#include "stdio.h"  
#include "string.h"  
  
int main(void) {  
    char *a = "hello\0Wolrd";  
    char *b = "helloWolrd\0";  
    printf("字符串的长度：%lu\n",  
           strlen(a)  
    );    printf("字符串的长度：%lu\n",  
           strlen(b)  
    );}

输出结果则会不一样，\0 后面的数据会被截断：

字符串的长度：5
字符串的长度：10

在 SDS 结构中却能保证二进制安全，因为 SDS 保存了 len 属性，这就可以不适用 \0 这个标识来判断字符串是否结束。

2.2 操作效率问题

2.2.1 空间效率

2.2.1.1 预分配内存

原生的 C 语言字符串，在添加的时候，可能会因为可用空间不足，无法添加，而 Redis 追加字符串的时候，使用了预分配的策略，如果内存不够，先进行内存拓展，再追加，有效减少修改字符串带来的内存重新分配的次数。类似于 Java 中的 ArrayList，采取预分配，内部真实的容量一般都是大于实际的字符串的长度的，当字符串的长度小于 1MB 的时候，如果内存不够，扩容都是加倍现在的空间；如果字符串的长度已经超过了 1MB，扩容的时候也只会多扩 1MB 的空间，但是最大的字符串的长度是 512MB。

2.2.1.2 惰性空间释放

惰性空间释放用于优化 SDS 的字符串缩短操作，当 SDS 的 API 需要缩短字符串保存的字符串的时候，程序并不会立即使用内存重新分配来回缩短多出来的字节，而是使用 free 属性将这些字节的数量记录下来，并等待将来使用。

当然 SDS 也提供了 SDS 显式调用，真正的释放未使用的空间。

2.2.2 操作效率

原生的 C 语言在获取字符的长度的时候，底层实际是遍历，时间复杂度是 O(n) ，String 作为 Redis 用得最多的数据类型，获取字符串的长度是比较频繁的操作，肯定不能这么干，那就用一个变量把 String 的长度存储起来，获取的时候时间复杂度是 O(1)。

2.2.3 兼容性较好

Redis 虽然使用了 \0 来结尾，但是 sds 字符串的末端还是会遵循 c 语言的惯例，所以可以重用一部分<string. h> 的函数。比如对比的函数 strcasecmp ，可以用来对比 SDS 保存的字符串是否和另外一个字符串是否相同。

strcasecmp(sds->buf,"hello world");

3 源码解读

3.1 简单指针介绍

数组的指针操作：

#include <stdio.h>
int main() {
    printf("Hello, World!\n");
    char t[] = {'a','b','c','d'};
    char* s = t+1; // 指针前进一位
    char  bb = s[0];
    char  cc = s[1];
    char  dd = s[2];
    char  flag = s[-1]; // 指针后退一位等价于  char  flag = *(s - 1);  或者  char  *flag = s - 1;   printf("%c %c %c %c", *flag, bb, cc ,dd);
    printf("%c %c %c %c", flag, bb, cc ,dd);
    return 0;
}

最终输出结果：

Hello, World!
a b c d

3.1.1 sdshdr 巧妙的结构设计

SDS 的相关代码主要在下面两个文件：

sds. h：头文件
sds. c：源文件

SDS 定义在 sds. h 中，为了兼容 C 风格的字符串，给 char 取了个别名叫 sds :

typedef char *sds;

《Redis 设计与实现》中，解释的是 Redis 3.0 的代码，提到 sds 的实现结构 sdshdr 是这样的：

struct sdshdr {
    // 记录buf数组已使用字节的数量
    // 等于SDS所保存字符串的长度
    int len;
    
    // 记录buf数组中未使用的字节数
    int free;
    
    // 字节数组，用于保存字符串
    char buf[];
};

但是实际上 7.0 版本已经是长这样：

1. Sdshdr5 从未被使用，我们只是直接访问标志字节。

然而，这里文档标识 sdshdr5 的结构。
1. 结构定义使用了__attribute__ ((packed))声明为非内存对齐, 紧凑排列形式（取消编译阶段的内存优化对齐功能）
1. 如果定义了一个 sds *s, 可以非常方便的使用 s[-1] 获取到 flags 地址，避免了在上层调用各种类型判断。

struct __attribute__ ((__packed__)) sdshdr5 {
    unsigned char flags; /* 低 3 位存储类型，高 5 位存储字符串长度 */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr8 {
    uint8_t len; /* 已使用 */
    uint8_t alloc; /* 总分配的，不包括头部和空的终止符*/
    unsigned char flags; /* 低 3 位存储类型，高 5 位预留，还没使用 */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr16 {
    uint16_t len;  /* 已使用 */
    uint16_t alloc; /* 总分配的，不包括头部和空的终止符*/
    unsigned char flags;  /* 低 3 位存储类型，高 5 位预留，还没使用 */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr32 {
    uint32_t len; /* 已使用 */
    uint32_t alloc; /* 总分配的，不包括头部和空的终止符*/
    unsigned char flags;  /* 低 3 位存储类型，高 5 位预留，还没使用 */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr64 {
    uint64_t len; /* used */
    uint64_t alloc; /* 总分配的，不包括头部和空的终止符*/
    unsigned char flags;  /* 低 3 位存储类型，高 5 位预留，还没使用 */
    char buf[];
};

// 类型定义一共占用了 0，1，2，3，4 五个数字，也就是三位就可以标识，  
// 那么我们可以使用 flags&SDS_TYPE_MASK 来获取动态字符串对应的字符串类型

#define SDS_TYPE_5  0  
#define SDS_TYPE_8  1  
#define SDS_TYPE_16 2  
#define SDS_TYPE_32 3  
#define SDS_TYPE_64 4  
#define SDS_TYPE_MASK 7  
#define SDS_TYPE_BITS 3  
#define SDS_HDR_VAR(T,s) struct sdshdr##T *sh = (void*)((s)-(sizeof(struct sdshdr##T)));  
#define SDS_HDR(T,s) ((struct sdshdr##T *)((s)-(sizeof(struct sdshdr##T))))  
#define SDS_TYPE_5_LEN(f) ((f)>>SDS_TYPE_BITS)

上面定义了 4 种结构体，**Redis 根据不同的字符串的长度，来选择合适的结构体，每个结构体有对应数据部分和头部。

类型一共有这些：

#define SDS_TYPE_5  0  
#define SDS_TYPE_8  1  
#define SDS_TYPE_16 2  
#define SDS_TYPE_32 3  
#define SDS_TYPE_64 4

用二进制表示，只需要 3 位即可，这也是为什么上面的结构体 sdshdr5 里面的 flags 字段注释里写的：前三位表示类型，后 5 位用于表示字符串长度。

    unsigned char flags; /* 3 lsb of type, and 5 msb of string length */

而其他的 sds 结构体类型，因为长度太长了，存不下，所以后 5 位暂时没有作用，而是另外使用属性存储字符串的长度。

    uint8_t len; /* used */  
    uint8_t alloc; /* excluding the header and null terminator */

3.2 3.2 attribute 的作用是什么？

__attribute__ ((packed)) 的作用就是告诉编译器取消结构在编译过程中的优化对齐, 按照实际占用字节数进行对齐，是 GCC 特有的语法。这个功能是跟操作系统没关系，跟编译器有关，gcc 编译器不是紧凑模式的。

attribute__关键字主要是用来在函数或数据声明中设置其属性。给函数赋给属性的主要目的在于让编译器进行优化。函数声明中的__attribute((noreturn))，就是告诉编译器这个函数不会返回给调用者，以便编译器在优化时去掉不必要的函数返回代码。

__attribute__书写特征是：__attribute__前后都有两个下划线，并且后面会紧跟一对括弧，括弧里面是相应的__attribute__参数，其语法格式为：

__attribute__ ((attribute-list))

下面是实验的一些代码，实验环境为 Mac：

#include "stdio.h"  
  
struct One{ char ch; int a;} one;  
struct __attribute__ ((__packed__)) Tow{ char ch; int a;} tow;  
  
int main(void) {  
    printf("int 的内存大小：%lu\n",  
           sizeof(int)  
    );    printf("新结构体one的大小（不压缩）：%lu\n",  
           sizeof(one)  
    );    printf("新结构体tow的大小（压缩）：%lu\n",  
           sizeof(tow)  
    );}

运行结果：

int 的内存大小：4
新结构体one的大小（不压缩）：8
新结构体tow的大小（压缩）：5

编译器压缩优化（内存不对齐）后，确实体积从 8 变成了 5，缩小了不少，别看这小小的变化，其实在巨大的数量面前，就是很大的空间优化。

3.3 宏操作

redis 基于前面 sds 设计，定义了一些十分巧妙的宏操作：

3.3.1 通过 sds 获取不同类型 sdshdr 变量

/*  
* 宏操作  
* SDS_HDR_VAR(8,s);  
* 下面是对应宏定义翻译的产物  
* struct sdshdr8 *sh = (void*)((s)-(sizeof(struct sdshdr##T)));  
* 可以根据指向 buf 的sds变量s得到 sdshdr8 的指针,sh 是创建出来的变量  
*/  
#define SDS_HDR_VAR(T,s) struct sdshdr##T *sh = (void*)((s)-(sizeof(struct sdshdr##T)));

/**  
* 和上面类似  
* 根据指向buf的sds变量s得到sdshdr的指针，只不过这里是获取的是指针地址  
*/  
#define SDS_HDR(T,s) ((struct sdshdr##T *)((s)-(sizeof(struct sdshdr##T))))

3.3.2 获取 sdshdr5 字符串类型的长度

/**  
* 该函数就是获取sdshdr5字符串类型的长度，由于根本不使用sdshdr5类型，所以需要直接返回空，  
* 而flags成员使用最低三位有效位来表示类型，所以让f代表的flags的值右移三位即可  
*/  
#define SDS_TYPE_5_LEN(f) ((f)>>SDS_TYPE_BITS)

3.3.3 通过 sds 获取 len 的值

/**  
* 使用到了取消编译阶段的内存优化对齐功能，直接使用s[-1]获取到flags成员的值，  
* 然后根据flags&&SDS_TYPE_MASK来获取到动态字符串对应的类型进而获取动态字符串的长度。  
* SDS_TYPE_5_LEN 比较特殊一点，因为结构有点不一样  
*/  
static inline size_t sdslen(const sds s) {  
unsigned char flags = s[-1];  
switch(flags&SDS_TYPE_MASK) {  
case SDS_TYPE_5:  
return SDS_TYPE_5_LEN(flags);  
case SDS_TYPE_8:  
return SDS_HDR(8,s)->len;  
case SDS_TYPE_16:  
return SDS_HDR(16,s)->len;  
case SDS_TYPE_32:  
return SDS_HDR(32,s)->len;  
case SDS_TYPE_64:  
return SDS_HDR(64,s)->len;  
}  
return 0;  
}

3.4 创建新字符串

创建新的字符串一般是传递初始化的长度：

sds sdsnewlen(const void *init, size_t initlen) {  
	// 内部封装的函数，最后一个参数是是否尝试分配
    return _sdsnewlen(init, initlen, 0);  
}

下面我们看具体的函数实现：创建的返回的是指针，指向的是结构体中 buf 开始的位置，

sds _sdsnewlen(const void *init, size_t initlen, int trymalloc) {  
	// sh 指向sds分配开始的地方
    void *sh;
    // s 也是指针，指向 buf 开始的位置  
    sds s;
    // 不同长度返回不同的类型sds
    char type = sdsReqType(initlen);  
    /* Empty strings are usually created in order to append. Use type 8  
     * since type 5 is not good at this. */
    // 空字符串经常被创建出来之后，就会执行append操作，所以用type 8替换掉它，type 5 太短了。
    if (type == SDS_TYPE_5 && initlen == 0) type = SDS_TYPE_8;  
    // 获取整个struct的长度
    int hdrlen = sdsHdrSize(type);
    // flag 指针，标识sds 是哪一个类型的  
    unsigned char *fp; /* flags pointer. */
    // 可用大小  
    size_t usable;  
    // 防止溢出
    assert(initlen + hdrlen + 1 > initlen); /* Catch size_t overflow */ 
    // 分配内存,其中s_trymalloc_usable是调整内存,s_malloc_usable是新分配内存,是两种内存分配的方式,通过参数trymalloc控制（+1 是为了处理 \0）
    sh = trymalloc?  
        s_trymalloc_usable(hdrlen+initlen+1, &usable) :  
        s_malloc_usable(hdrlen+initlen+1, &usable);  
    // 分配不成功，提前结束
    if (sh == NULL) return NULL;
    // 如果需要完全为空的字符串，直接返回null  
    if (init==SDS_NOINIT)  
        init = NULL;  
    else if (!init)
        memset(sh, 0, hdrlen+initlen+1);  // 初始化 
    // s 指向数组 buf 的位置（从结构体往后加上hdrlen就是buf数组开头的位置） 
    s = (char*)sh+hdrlen;
    // buf数组的位置-1，就是flags字段的位置  
    fp = ((unsigned char*)s)-1;
    // 可用空间减去hdrlen（已用空间），再减1（‘\0‘）  
    usable = usable-hdrlen-1;
    // 如果可用空间大于当前结构体中alloc字段的大小,就使用alloc的最大值  
    if (usable > sdsTypeMaxSize(type))  
        usable = sdsTypeMaxSize(type);
    // 初始化不同类型的数组，字符串长度，可用大小和类型  
    switch(type) {  
        case SDS_TYPE_5: {  
            *fp = type | (initlen << SDS_TYPE_BITS);  
            break;  
        }        
        case SDS_TYPE_8: {  
            SDS_HDR_VAR(8,s);  
            sh->len = initlen;  
            sh->alloc = usable;  
            *fp = type;  
            break;  
        }        
        case SDS_TYPE_16: {  
            SDS_HDR_VAR(16,s);  
            sh->len = initlen;  
            sh->alloc = usable;  
            *fp = type;  
            break;  
        }        
        case SDS_TYPE_32: {  
            SDS_HDR_VAR(32,s);  
            sh->len = initlen;  
            sh->alloc = usable;  
            *fp = type;  
            break;  
        }        
        case SDS_TYPE_64: {  
            SDS_HDR_VAR(64,s);  
            sh->len = initlen;  
            sh->alloc = usable;  
            *fp = type;  
            break;  
        }
	}
	if (initlen && init)  
        memcpy(s, init, initlen);  
    s[initlen] = '\0';  
    return s;  
}

3.5 获取可用空间

SDS 和我平常所用到的 C 语言的原生字符串有差别，因为从获取可用空间的计算方法来看，并未考虑到字符串需要以 \0 结尾，结构体本身带有长度的成员 len，不需要 \0 来做字符串结尾的判定，而且不使用 \0 作为结尾有很多好处, 分配的减去使用的即可。

static inline size_t sdsavail(const sds s) {
    unsigned char flags = s[-1];
    switch(flags&SDS_TYPE_MASK) {
        case SDS_TYPE_5: {
            return 0;
        }
        case SDS_TYPE_8: {
            SDS_HDR_VAR(8,s);
            return sh->alloc - sh->len;
        }
        case SDS_TYPE_16: {
            SDS_HDR_VAR(16,s);
            return sh->alloc - sh->len;
        }
        case SDS_TYPE_32: {
            SDS_HDR_VAR(32,s);
            return sh->alloc - sh->len;
        }
        case SDS_TYPE_64: {
            SDS_HDR_VAR(64,s);
            return sh->alloc - sh->len;
        }
    }
    return 0;
}

3.6 设置 & 增加 sds 的长度

// 设置 sds 的长度
static inline void sdssetlen(sds s, size_t newlen) {
    unsigned char flags = s[-1];
    switch(flags&SDS_TYPE_MASK) {
        case SDS_TYPE_5:
            {
                unsigned char *fp = ((unsigned char*)s)-1;
                *fp = SDS_TYPE_5 | (newlen << SDS_TYPE_BITS);
            }
            break;
        case SDS_TYPE_8:
            SDS_HDR(8,s)->len = newlen;
            break;
        case SDS_TYPE_16:
            SDS_HDR(16,s)->len = newlen;
            break;
        case SDS_TYPE_32:
            SDS_HDR(32,s)->len = newlen;
            break;
        case SDS_TYPE_64:
            SDS_HDR(64,s)->len = newlen;
            break;
    }
}

// 增加 sds 的长度
static inline void sdsinclen(sds s, size_t inc) {
    unsigned char flags = s[-1];
    switch(flags&SDS_TYPE_MASK) {
        case SDS_TYPE_5:
            {
                unsigned char *fp = ((unsigned char*)s)-1;
                unsigned char newlen = SDS_TYPE_5_LEN(flags)+inc;
                *fp = SDS_TYPE_5 | (newlen << SDS_TYPE_BITS);
            }
            break;
        case SDS_TYPE_8:
            SDS_HDR(8,s)->len += inc;
            break;
        case SDS_TYPE_16:
            SDS_HDR(16,s)->len += inc;
            break;
        case SDS_TYPE_32:
            SDS_HDR(32,s)->len += inc;
            break;
        case SDS_TYPE_64:
            SDS_HDR(64,s)->len += inc;
            break;
    }
}

3.7 设置 & 获取已分配空间大小

/* sdsalloc() = sdsavail() + sdslen() */
// 获取 sds 已经分配的空间的大小
static inline size_t sdsalloc(const sds s) {
    unsigned char flags = s[-1];
    switch(flags&SDS_TYPE_MASK) {
        case SDS_TYPE_5:
            return SDS_TYPE_5_LEN(flags);
        case SDS_TYPE_8:
            return SDS_HDR(8,s)->alloc;
        case SDS_TYPE_16:
            return SDS_HDR(16,s)->alloc;
        case SDS_TYPE_32:
            return SDS_HDR(32,s)->alloc;
        case SDS_TYPE_64:
            return SDS_HDR(64,s)->alloc;
    }
    return 0;
}

// 设置 sds 已经分配的空间的大小
static inline void sdssetalloc(sds s, size_t newlen) {
    unsigned char flags = s[-1];
    switch(flags&SDS_TYPE_MASK) {
        case SDS_TYPE_5:
            /* Nothing to do, this type has no total allocation info. */
            break;
        case SDS_TYPE_8:
            SDS_HDR(8,s)->alloc = newlen;
            break;
        case SDS_TYPE_16:
            SDS_HDR(16,s)->alloc = newlen;
            break;
        case SDS_TYPE_32:
            SDS_HDR(32,s)->alloc = newlen;
            break;
        case SDS_TYPE_64:
            SDS_HDR(64,s)->alloc = newlen;
            break;
    }
}

3.8 扩大 sds 空间

/**
 * 扩大sds字符串末尾的空闲空间，以便调用者确信在调用此函数后可以覆盖到字符串末尾 addlen字节，再加上null term的一个字节。
 * 如果已经有足够的空闲空间，这个函数返回时不做任何操作，如果没有足够的空闲空间，它将分配缺失的部分，甚至更多:
 * 当greedy为1时，放大比需要的更多，以避免将来在增量增长时需要重新分配。
 * 当greedy为0时，将其放大到足够大以便为addlen腾出空间。
 * 注意:这不会改变sdslen()返回的sds字符串的长度，而只会改变我们拥有的空闲缓冲区空间。
 */
// 扩大sds空间
sds _sdsMakeRoomFor(sds s, size_t addlen, int greedy) {
    void *sh, *newsh;
    // 获取剩余可用的空间
    size_t avail = sdsavail(s);
    size_t len, newlen, reqlen;
    // 获取sds 具体数据类型
    char type, oldtype = s[-1] & SDS_TYPE_MASK;
    int hdrlen;
    size_t usable;

    /* Return ASAP if there is enough space left. */
    // 可用空间足够直接返回
    if (avail >= addlen) return s;

    // 已用字符长度
    len = sdslen(s);

    // sh 回溯到sds起始位置
    sh = (char*)s-sdsHdrSize(oldtype);

    // newlen 为最小需要的长度
    reqlen = newlen = (len+addlen);
    assert(newlen > len);   /* Catch size_t overflow */
    // 在newlen小于SDS_MAX_PREALLOC(1M)，对newlen进行翻倍，在newlen大于SDS_MAX_PREALLOC的情况下，让newlen加上SDS_MAX_PREALLOC。
    if (greedy == 1) {
        if (newlen < SDS_MAX_PREALLOC) // 小于1Kb 预分配2倍长度 = newlen + newlen
            newlen *= 2;
        else
            newlen += SDS_MAX_PREALLOC; // 多余1Mb 预分配 = newlen + 1Mb
    }

    // 获取新长度的类型
    type = sdsReqType(newlen);

    /* Don't use type 5: the user is appending to the string and type 5 is
     * not able to remember empty space, so sdsMakeRoomFor() must be called
     * at every appending operation. */
    if (type == SDS_TYPE_5) type = SDS_TYPE_8;

    // 新类型头部长度
    hdrlen = sdsHdrSize(type);
    // 校验是否溢出
    assert(hdrlen + newlen + 1 > reqlen);  /* Catch size_t overflow */
    if (oldtype==type) {
        /**
         * 本质上是 使用 zrealloc_usable函数，指针ptr必须为指向堆内存空间的指针，即由malloc函数、calloc函数或realloc函数分配空间的指针。
         * realloc函数将指针p指向的内存块的大小改变为n字节。
         * 1.如果n小于或等于p之前指向的空间大小，那么。保持原有状态不变。
         * 2.如果n大于原来p之前指向的空间大小，那么，系统将重新为p从堆上分配一块大小为n的内存空间，同时，将原来指向空间的内容依次复制到新的内存空间上，p之前指向的空间被释放。
         * relloc函数分配的空间也是未初始化的。
         */
        newsh = s_realloc_usable(sh, hdrlen+newlen+1, &usable);
        // 申请空间失败
        if (newsh == NULL) return NULL;
        // s指向新sds结构的buf开始位置
        s = (char*)newsh+hdrlen;
    } else {
        /* Since the header size changes, need to move the string forward,
         * and can't use realloc */
        // 数据结构发生变更，协议头部变更，需要从堆上重新申请数据空间
        newsh = s_malloc_usable(hdrlen+newlen+1, &usable);
        if (newsh == NULL) return NULL;
        // 系统copy，越过头部结构长度，复制s的有效数据集合
        memcpy((char*)newsh+hdrlen, s, len+1);
        // 释放旧空间
        s_free(sh);
        // s执行新的空间，buf起始位置
        s = (char*)newsh+hdrlen;
        // flag 赋值 头部的第三个有效字段
        s[-1] = type;
        // 更新有效数据长度
        sdssetlen(s, len);
    }
    // 实际可用数据空间
    usable = usable-hdrlen-1;
    if (usable > sdsTypeMaxSize(type))
        usable = sdsTypeMaxSize(type);
    // 更新分配的空间值
    sdssetalloc(s, usable);
    return s;
}

3.9 释放多余空间

/* 对sds中多余的空间进行释放  
* 重新分配sds字符串，使其末尾没有空闲空间。所包含的字符串保持不变，  
* 但下一个连接操作将需要重新分配。  
* 调用之后，传递的sds字符串不再有效，所有引用必须用调用返回的新指针替换。  
*/
sds sdsRemoveFreeSpace(sds s, int would_regrow) {  
	return sdsResize(s, sdslen(s), would_regrow);  
}

/**
 * 调整分配的大小，这可以使分配更大或更小，如果大小小于当前使用的len，数据将被截断。
 * 当将d_regrow参数设置为1时，它会阻止使用SDS_TYPE_5，这是在sds可能再次更改时所需要的。
 * 无论实际分配大小如何，sdsAlloc大小都将被设置为请求的大小，这样做是为了避免在调用者检测到它有多余的空间时重复调用该函数
 */
sds sdsResize(sds s, size_t size, int would_regrow) {
    void *sh, *newsh;
    char type, oldtype = s[-1] & SDS_TYPE_MASK;
    int hdrlen, oldhdrlen = sdsHdrSize(oldtype);
    size_t len = sdslen(s);
    sh = (char*)s-oldhdrlen;

    /* Return ASAP if the size is already good. */
    if (sdsalloc(s) == size) return s;

    /* Truncate len if needed. */
    if (size < len) len = size;

    /* Check what would be the minimum SDS header that is just good enough to
     * fit this string. */
    type = sdsReqType(size);
    if (would_regrow) {
        /* Don't use type 5, it is not good for strings that are expected to grow back. */
        if (type == SDS_TYPE_5) type = SDS_TYPE_8;
    }
    hdrlen = sdsHdrSize(type);

    /* If the type is the same, or can hold the size in it with low overhead
     * (larger than SDS_TYPE_8), we just realloc(), letting the allocator
     * to do the copy only if really needed. Otherwise if the change is
     * huge, we manually reallocate the string to use the different header
     * type. */
    int use_realloc = (oldtype==type || (type < oldtype && type > SDS_TYPE_8));
    size_t newlen = use_realloc ? oldhdrlen+size+1 : hdrlen+size+1;
    int alloc_already_optimal = 0;
    #if defined(USE_JEMALLOC)
        /* je_nallocx returns the expected allocation size for the newlen.
         * We aim to avoid calling realloc() when using Jemalloc if there is no
         * change in the allocation size, as it incurs a cost even if the
         * allocation size stays the same. */
        alloc_already_optimal = (je_nallocx(newlen, 0) == zmalloc_size(sh));
    #endif

    if (use_realloc && !alloc_already_optimal) {
        newsh = s_realloc(sh, newlen);
        if (newsh == NULL) return NULL;
        s = (char*)newsh+oldhdrlen;
    } else if (!alloc_already_optimal) {
        newsh = s_malloc(newlen);
        if (newsh == NULL) return NULL;
        memcpy((char*)newsh+hdrlen, s, len);
        s_free(sh);
        s = (char*)newsh+hdrlen;
        s[-1] = type;
    }
    s[len] = 0;
    sdssetlen(s, len);
    sdssetalloc(s, size);
    return s;
}

3.10 拼接字符串

将一个字符串拼接到原 sds 后面：

sds sdscatlen(sds s, const void *t, size_t len) {
    // 现在长度
    size_t curlen = sdslen(s);
    // 扩容
    s = sdsMakeRoomFor(s,len);
    if (s == NULL) return NULL;
    // 复制
    memcpy(s+curlen, t, len);
    // 设置长度
    sdssetlen(s, curlen+len);
    // 结尾'\0'
    s[curlen+len] = '\0';
    return s;
}

3.11 拷贝

sds sdscpylen(sds s, const char *t, size_t len) {
    // 长度不够需要扩容
    if (sdsalloc(s) < len) {
        s = sdsMakeRoomFor(s,len-sdslen(s));
        if (s == NULL) return NULL;
    }
    // 复制
    memcpy(s, t, len);
    // 末尾 '\0'
    s[len] = '\0';
    // 设置长度
    sdssetlen(s, len);
    return s;
}

4 SDS 的优点

1. 获取字符串的时间效率为 O (1)
1. 杜绝缓冲区的溢出，复制或者追加字符串之前，会对空间进行检查与拓展，并且预分配一些容量，减少分片内存的次数。
1. 可以存储二进制数据，含有 \0 则在读取时不会被截断。
1. 可以复用一部分 c 原生字符串的函数。

如果觉得文章对你有用，请随意赞赏

redis 缓存

Redis【2】- SDS源码分析

https://www.aphysia.cn/archives/redis-2---sdsyuan-ma-fen-xi

作者

秦怀

发布于

2023-09-10

更新于

2023-09-13

许可协议

CC BY 4.0

Redis【2】- SDS源码分析

1 简介&基础用法

2 为什么 Redis 自实现字符串？

2.1 存储二进制的限制

2.2 操作效率问题

2.2.1 空间效率

2.2.1.1 预分配内存

2.2.1.2 惰性空间释放

2.2.2 操作效率

2.2.3 兼容性较好

3 源码解读

3.1 简单指针介绍

3.1.1 sdshdr 巧妙的结构设计

3.2 3.2 attribute 的作用是什么？

3.3 宏操作

3.3.1 通过 sds 获取不同类型 sdshdr 变量

3.3.2 获取 sdshdr5 字符串类型的长度

3.3.3 通过 sds 获取 len 的值

3.4 创建新字符串

3.5 获取可用空间

3.6 设置 & 增加 sds 的长度

3.7 设置 & 获取已分配空间大小

3.8 扩大 sds 空间

3.9 释放多余空间

3.10 拼接字符串

3.11 拷贝

4 SDS 的优点

作者

发布于

更新于

许可协议

评论