一文带你快速搞懂动态字符串 SDS，面试不再懵逼
uint32_t len;
uint32_t alloc;
unsigned char flags;
char buf[];
};
struct attribute ((packed)) sdshdr64 {
uint64_t len;
uint64_t alloc;
unsigned char flags;
char buf[];
};
假设我们设置某个字符串为 hello，那么他 SDS 的可用长度 len 为 8，已用长度 len 为 6，如下图。注意：Redis会根据具体的字符长度，选择相应的sdshdr，但是各个类型都差不多，所以下图加简单画了。
?
我们可以看到是对字符数组的再封装，但是为什么呢，直接使用字符数组不是更简单吗？这要从 C 和 Java 语言的根本区别说起。
更快速的获取字符串长度
我们都知道 Java 的字符串有提供 length 方法，列表有提供 size 方法，我们可以直接获取大小。但是 C 却不一样，更偏向底层实现，所以没有直接的方法使用。这样就带来一个问题，如果我们想要获取某个数组的长度，就只能从头开始遍历，当遇到第一个’\0’则表示该数组结束。这样的速度太慢了，不能每次因为要获取长度就变量数组。所以设计了 SDS 数据结构，在原来的字符数组外面增加总长度，和已用长度，这样每次直接获取已用长度即可。复杂度为 O(1)。
数据安全，不会截断
如果传统字符串保存图片，视频等二进制文件，中间可能出现’\0’，如果按照原来的逻辑，会造成数据丢失。所以可以用已用长度来表示是否字符数组已结束。
获取常见值（抽象出常见方法）
在 sds.h 中写了一些常见方法，比如计算 sds 的长度（即 sdshdr 的 len），计算 sds 的空闲长度（即 sdshdr 的可用长度 alloc-已用长度 len），计算 sds 的可用长度(即 sdshdr 的 alloc)等等。但是大家有没有疑问，这不是一行代码搞定的事吗，为啥要抽象出方法呢？那么问题在于在上面，我们有将 sdshdr 分为五种类型，分别是 sdshdr5，sdshdr8，sdshdr16，sdshdr32，sdshdr64。那么我们在实际使用的时候，想要区分当前是哪个类型，并取其相应字段或设置相应字段。
//计算 sds 对应的字符串长度，其实上取得是字符串所对应的哪种 sdshdr 的 len 值
static inline size_t sdslen(const sds s) {
// 柔性数组不占空间，所以倒数第二位的是 flags
unsigned char flags = s[-1];
//flags 与上面定义的宏变量 7 做位运算
switch(flags&SDS_TYPE_MASK) {
case SDS_TYPE_5://0
return SDS_TYPE_5_LEN(flags);
case SDS_TYPE_8://1
return SDS_HDR(8,s)->len;//取上面结构体 sdshdr8 的 len
case SDS_TYPE_16://2
return SDS_HDR(16,s)->len;
case SDS_TYPE_32://3
return SDS_HDR(32,s)->len;
case SDS_TYPE_64://5
return SDS_HDR(64,s)->len;
}
return 0;
}
//计算 sds 对应的空余长度，其实上是 alloc-len
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;
}
//设置 sdshdr 的 len
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;
}
}
//给 sdshdr 的 len 添加多少大小
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;
}
}
//获取 sdshdr 的总长度
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;
}
//设置 sdshdr 的总长度
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;
}
}
创建对象
我们通过 sdsnew 方法来创建对象，显示通过判断 init 是否为空来确定初始大小，接着调用
方法 sdsnew（这边方法名一样，但是参数不一样，其为方法的重载），先根据长度确定类型（上面有提过五种类型，不记得的可以往上翻），然后根据类型分配相应的内存资源，最后追加 C 语言的结尾符’\0’。
sds sdsnew(const char *init) {
size_t initlen = (init == NULL) ? 0 : strlen(init);
return sdsnewlen(init, initlen);
}
sds sdsnewlen(const void *init, size_t initlen) {
void *sh;
sds s;
char type = sdsReqType(initlen);//根据长度确定类型
/*空字符串，用 sdshdr8，这边是经验写法，当想构造空串是为了放入超过 32 长度的字符串 */
if (type == SDS_TYPE_5 && initlen == 0) type = SDS_TYPE_8;
int hdrlen = sdsHdrSize(type);//到下一个方法，已经把他们放在一起了
unsigned char fp; / flags pointer. */
//分配内存
sh = s_malloc(hdrlen+initlen+1);
if (!init)
memset(sh, 0, hdrlen+initlen+1);
if (sh == NULL) return NULL;
s = (char*)sh+hdrlen;
fp = ((unsigned char*)s)-1;
//根据不同的类型，创建不同结构体，调用 SDS_HDR_VAR 函数
//为不同的结构体赋值,如已用长度 len,总长度 alloc
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 = initlen;
*fp = type;
break;
}
case SDS_TYPE_16: {
SDS_HDR_VAR(16,s);
sh->len = initlen;
sh->alloc = initlen;
*fp = type;
break;
}
case SDS_TYPE_32: {
SDS_HDR_VAR(32,s);
sh->len = initlen;
sh->alloc = initlen;
*fp = type;
break;
}
case SDS_TYPE_64: {
SDS_HDR_VAR(64,s);
sh->len = initlen;
sh->alloc = initlen;
*fp = type;
break;
}
}
if (initlen && init)
memcpy(s, init, initlen);
//最后追加'\0'
s[initlen] = '\0';
return s;
}
//根据实际字符长度确定类型
static inline char sdsReqType(size_t string_size) {
if (string_size < 1<<5)
return SDS_TYPE_5;
if (string_size < 1<<8)
return SDS_TYPE_8;
if (string_size < 1<<16)
return SDS_TYPE_16;
#if (LONG_MAX == LLONG_MAX)
if (string_size < 1ll<<32)
return SDS_TYPE_32;
#endif
return SDS_TYPE_64;
}
删除
String 类型的删除并不是直接回收内存，而是修改字符，让其为空字符，这其实是惰性释放，等待将来使用。在调用 sdsempty 方法时，再次调用上面的 sdsnewlen 方法。
/*修改 sds 字符串使其为空（零长度）。
*但是，所有现有缓冲区不会被丢弃，而是设置为可用空间
*这样，下一个 append 操作将不需要分配到
*当要缩短 SDS 保存的字符串时，程序并不立即使用内存充分配来回收缩短后多出来的字节，并等待将来使用。
void sdsclear(sds s) {
sdssetlen(s, 0);
s[0] = '\0';
}
sds sdsempty(void) {
return sdsnewlen("",0);
}
添加字符（扩容）重点！！！
添加字符串，sdscat 输入参数为 sds 和字符串 t，首先调用 sdsMakeRoomFor 扩容方法，再追加新的字符串，最后添加上结尾符’\0’。我们来看下扩容方法里面是如何实现的？第一步先调用常见方法中的 sdsavail 方法，获取还剩多少空闲空间。如果空闲空间大于要添加的字符串 t 的长度，则直接返回，不想要扩容。如果空闲空间不够，则想要扩容。第二步判断想要扩容多大，这边有分情况，如果目前的字符串小于1M，则直接扩容双倍，如果目前的字符串大于1M，则直接添加1M。第三个判断添加字符串之后的数据类型还是否和原来的一致，如果一致，则没啥事。如果不一致，则想要新建一个 sdshdr，把现有的数据都挪过去。
这样是不是有点抽象，举个例子，现在 str 的字符串为 hello，目前是 sdshdr8，总长度 50，已用 6，空闲 44。现在想要添加长度为 50 的字符 t，第一步想要看下是否要扩容，50 明显大于 44，需要扩容。第二步扩容多少，str 的长度小于 1M，所以扩容双倍，新的长度为 50*2=100。第三步 50+50 所对应 sdshdr 类型还是 sdshdr8 吗？明显还是 sdshdr8，所以不要数据迁移，还在原来的基础上添加 t 即可。
sds sdscat(sds s, const char *t) {
return sdscatlen(s, t, strlen(t));
}
sds sdscatlen(sds s, const void *t, size_t len) {
//调用 sds.h 里面的 sdslen，即取已用长度
size_t curlen = sdslen(s);
//扩容方法
s = sdsMakeRoomFor(s,len);
if (s == NULL) return NULL;
memcpy(s+curlen, t, len);
sdssetlen(s, curlen+len);
s[curlen+len] = '\0';
return s;
}
sds sdsMakeRoomFor(sds s, size_t addlen) {
void *sh, *newsh;
//调用 sds.h，获取空闲长度 alloc
size_t avail = sdsavail(s);
size_t len, newlen;
char type, oldtype = s[-1] & SDS_TYPE_MASK;
int hdrlen;
//空闲长度大于需要增加的，不需要扩容，直接返回
评论