redis源码分析，SDS动态字符串

本文主要是介绍redis源码分析，SDS动态字符串，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

redis源码分析，SDS动态字符串

SDS [basic redis v6.0]，源码路径: src/sds.c, src/sds.h, src/sdsalloc.h
redis中的字符串类型为SDS（C dynamic strings）是一个动态类型字符串。 可以无限增长，理论上长度最大2^64

下面是redis中 SDS的结构

struct __attribute__ ((__packed__)) sdshdr32 {uint32_t len; /* buf已用长度 */uint32_t alloc; /* buf逻辑上预留长度，不包括结构体头部字段所占内存长度，并且不包含buf结尾的\0字符 */unsigned char flags; /* 字符串类型, 也表示了字符串的最长长度，可以动态增长 */char buf[]; /* 实际存储字符串的空间 */
};

• 其中 attribute ((packed)) 告诉编译器取消在编译过程中的内存对齐。关于内存对齐，网上有详细文章。
• uint32_t len; 其中uint32_t是typedef定义的。 还有uint8_t, uint16_t, uint32_t, uint64_t。实际的定义取决于编译器，具体如下

// Visual Studio 6 and Embedded Visual C++ 4 doesn't
// realize that, e.g. char has the same size as __int8
// so we give up on __intX for them.
#if (_MSC_VER < 1300)typedef signed char       int8_t;typedef signed short      int16_t;typedef signed int        int32_t;typedef unsigned char     uint8_t;typedef unsigned short    uint16_t;typedef unsigned int      uint32_t;
#elsetypedef signed __int8     int8_t;typedef signed __int16    int16_t;typedef signed __int32    int32_t;typedef unsigned __int8   uint8_t;typedef unsigned __int16  uint16_t;typedef unsigned __int32  uint32_t;
#endif
typedef signed __int64       int64_t;
typedef unsigned __int64     uint64_t;

• char buf[]; 属性为实际存储字符串的字符数组。具体长度取决于flags。也是sdshdr的类型
• uint32_t len; 属性buf已经使用的字节长度，也就想到与strlen(len)。和多数stl数据结构实现一样，因为strlen(len)时间复杂度为O(n),所以存储len，可以达到O(1)的时间取长度。
• uintew_t alloc; 为buf逻辑预留空间，不包含\0字符。其实alloc不一定等于实际的sizeof(buf)/sizeof(char)，因为buf为实际的预留空间,初始化时候len, alloc, sizeof(buf)/sizeof(char)均为字符串长度+1, 基本没有浪费内存. 而如果增长的化, buf长度一定是2⁸,2¹⁶,2³²,2⁶⁴(需要再减去结构体头部空间和\0字符)，而alloc也是预留空间长度，当字符串增长时，假设alloc小于增长后的len，那么alloc会增长，当alloc增长后的值大于2^flags时，结构体会重新构造，当然并不是真正构造结构体，只是操作内存函数重新分配了更大的一块空间，再进行内存拷贝。所以alloc值介于len和sizeof(buf)/sizeof(char)之间
• unsigned char flags; 为字符串的类型，有如下几个值，也就是整个结构体所占内存空间，初始化后所占内存为strlen(buf)+1, 而增长的话, 近似2^flags大小.

    /** #define SDS_TYPE_5  0* #define SDS_TYPE_8  1 // 对应长度为0 ~ 2^8-1, 假设字符串增长了的话, 那么结构体所占内存总是2^8大小* #define SDS_TYPE_16 2* #define SDS_TYPE_32 3* #define SDS_TYPE_64 4*/

下面来看一下redis对sds的内存初始化，即memory allocate

// 为了节省代码空间，假设分配的是32位的字符类型

sds sdsnewlen(const void *init, size_t initlen) {void *sh;sds s;char type = sdsReqType(initlen);    // if (initlen < 1<<32) {return SDS_TYPE_32}, 返回能满足所需的最小长度/* 不使用type 5，最少使用type8 */if (type == SDS_TYPE_5 && initlen == 0) type = SDS_TYPE_8;int hdrlen = sdsHdrSize(type);      // return sizeof(struct sdshdr32)， 即结构体头部字段所占用内存（buf为空数组的时候）unsigned char *fp;                  /* 指向flags字段 */assert(initlen + hdrlen + 1 > initlen); /* 判断整数溢出 */sh = s_malloc(hdrlen+initlen+1);    // 分配了结构体头部字段所占长度 + buf长度 + 空字符长度if (sh == NULL) return NULL; if (init==SDS_NOINIT)init = NULL;else if (!init)memset(sh, 0, hdrlen+initlen+1);s = (char*)sh+hdrlen;           // buf字段 内存开始位置fp = ((unsigned char*)s)-1;     // flags字段 内存所在位置switch(type) {case SDS_TYPE_5: {*fp = type | (initlen << SDS_TYPE_BITS);break;}case SDS_TYPE_8:  // { 和SDS_TYPE_32一样;  break;}case SDS_TYPE_16: // { 和SDS_TYPE_32一样;  break;}case SDS_TYPE_32: {SDS_HDR_VAR(32,s); // #define SDS_HDR_VAR(T,s) struct sdshdr##T *sh = (void*)((s)-(sizeof(struct sdshdr##T))); 即将指向buf的s指针 反序列化为结构体指针，同时赋值到shsh->len = initlen; // 因为空字符串, 所以len == alloc，若buf = ['a', 'b', 0, 0 ,0 ,0, ... ]sh->alloc = initlen;*fp = type;break;}case SDS_TYPE_64: // { 和SDS_TYPE_32一样;  break;}}if (initlen && init)memcpy(s, init, initlen);// 返回的是char*指针， typedef char* sdss[initlen] = '\0';return s;
}

• 可以看到，redis是直接把整个结构体的内存申请出来，然后操作指针，访问结构体的每一个变量，因为指定了编译器不会对内存进行优化，所以指针的前后移动可以直接访问到每一个属性，而直接返回buf位置的指针，可以让使用者达到和char []同样的使用效果，其实在物理上还是实现上也确实没太大区别
• s_malloc()的空间基本等于字符数组长度, 所以初始化时几乎没有内存浪费
• 关于指针的移动访问变量，我写了一个示例代码：

#include <stdio.h>
#include <string.h>
#include <stdlib.h>struct __attribute__ ((__packed__)) Test {char a;int b;long long c;int* d;
};int main () {void* tp = malloc(sizeof(struct Test));// 初始化内存值均为0memset(tp, 0, sizeof(struct Test));// 将内存序列化为结构struct Test* t = (struct Test*)(tp);// 赋值属性t->a = 'a';t->b = 1;t->c = 2;t->d = &(t->b);// 通过指针移动访问属性printf("a:%c\n", *(char*)tp);tp += sizeof(char);printf("b:%d\n", *(int*)tp);tp += sizeof(int);printf("b:%lld\n", *(long long*)tp);tp += sizeof(long long);printf("b:%d\n", *(*(int**)tp));return 0;
}

实现更新len属性的函数

void sdsupdatelen(sds s) {size_t reallen = strlen(s);sdssetlen(s, reallen);
}

为什么会有这个函数？
因为当s = [‘a’, ‘b’, ‘c’, ‘\0’, 0, …]时
操作 s[2] = ‘\0’;
现在sdslen(s)时，结果是3， 因为sdslen(s)是调用SDS_HDR(32, s) > ->len,但是len字段没有被更新。
但是实际的长度是strlen(s) ==> 2， 所以需要调用sdsupdatelen() > 函数更新len值。
那为什么要用sdslen(s)而不直接用strlen(s)测字符串长度呢？
因为sdslen因为直接取len值，所以时间复杂度为O(1)，而strlen需要 > 遍历字符串数组，直到找到\0字符，所以时间复杂度为O(n)

动态增长实现

// 预留空间
sds sdsMakeRoomFor(sds s, size_t addlen) {void *sh, *newsh;size_t avail = sdsavail(s); // return alloc - lensize_t len, newlen;char type, oldtype = s[-1] & SDS_TYPE_MASK;int hdrlen;if (avail >= addlen) return s; // (alloc - len) > addlen，可用空间大于所需要空间len = sdslen(s);sh = (char*)s-sdsHdrSize(oldtype);newlen = (len+addlen);assert(newlen > len);   /* Catch size_t overflow */if (newlen < SDS_MAX_PREALLOC)newlen *= 2;elsenewlen += SDS_MAX_PREALLOC;type = sdsReqType(newlen); // 增长后的类型。假设原来是SDS_TYPE_8, 增长后长度大于2^8，所以type变为SDS_TYPE_16，若仍然小于2^8,则type 仍为SDS_TYPE_8if (type == SDS_TYPE_5) type = SDS_TYPE_8;hdrlen = sdsHdrSize(type);assert(hdrlen + newlen + 1 > len);  /* Catch size_t overflow */if (oldtype==type) {//因为结构体头部字段除了buf外长度并未改变,所以直接realloc即可newsh = s_realloc(sh, hdrlen+newlen+1);if (newsh == NULL) return NULL;s = (char*)newsh+hdrlen;} else {/* 上面的realloc实际也是进行空间判断，如果后面可用内存空间可以满足需求，则直接增长，返回空间，如果已被利用，则进行malloc在memcpy， 那么这里为什么不直接调用realloc呢？ 因为结构体头部len和alloc所占的空间变了， 即hdrlen变了，所以需要memcpy在拷贝过程中同时移动buf位置*/newsh = s_malloc(hdrlen+newlen+1);if (newsh == NULL) return NULL;memcpy((char*)newsh+hdrlen, s, len+1);s_free(sh);s = (char*)newsh+hdrlen;s[-1] = type;sdssetlen(s, len);}sdssetalloc(s, newlen);return s;
}

• 可以看到当oldtype==type时, 调用了realloc, 因为除了位于结构体内存末尾的buf, 其他字段长度并未改变.
• 而oldtype!=type时, 执行了malloc和memcpy, 基本等同于cpp 的new struct的内存构造过程

// append实现
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);   // append到预留的空间sdssetlen(s, curlen+len);   // 重新设置lens[curlen+len] = '\0';       // 增加\0return s;
}sds sdscat(sds s, const char *t) {return sdscatlen(s, t, strlen(t));
}

这篇关于redis源码分析，SDS动态字符串的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---