分类：Redis| 发布时间：2019-04-13 23:43:00
本文是 Redis 5 数据结构系列的第一篇，本系列主要讲解 Redis 5 底层数据结构的相关原理和实现细节。 本文主要讲的是 SDS（简单动态字符串）的结构和实现细节。
SDS 的源代码在 src/sds.h 和 src/sds.c 文件中。
和早期版本（Redis 3.0 以及更早版本）的 SDS 定义不同，Redis 5 中的 SDS 结构有如下几个版本：
struct __attribute__ ((__packed__)) sdshdr5 {
unsigned char flags; /* 最低位的 3 个比特表示类型，最高位的 5 个比特表示字符串的长度 */
char buf[];
};
struct __attribute__ ((__packed__)) sdshdr8 {
uint8_t len; /* 已用大小 */
uint8_t alloc; /* 分配的内存大小，不包括 sdshdr8 本身的大小，以及 NULL 结束符 */
unsigned char flags; /* 最低位的 3 个比特表示类型，最高位的 5 个比特未用 */
char buf[];
};
struct __attribute__ ((__packed__)) sdshdr16 {
uint16_t len; /* 已用大小 */
uint16_t alloc; /* 分配的内存大小，不包括 sdshdr16 本身的大小，以及 NULL 结束符 */
unsigned char flags; /* 最低位的 3 个比特表示类型，最高位的 5 个比特未用 */
char buf[];
};
struct __attribute__ ((__packed__)) sdshdr32 {
uint32_t len; /* 已用大小 */
uint32_t alloc; /* 分配的内存大小，不包括 sdshdr16 本身的大小，以及 NULL 结束符 */
unsigned char flags; /* 最低位的 3 个比特表示类型，最高位的 5 个比特未用 */
char buf[];
};
struct __attribute__ ((__packed__)) sdshdr64 {
uint64_t len; /* 已用大小 */
uint64_t alloc; /* 分配的内存大小，不包括 sdshdr16 本身的大小，以及 NULL 结束符 */
unsigned char flags; /* 最低位的 3 个比特表示类型，最高位的 5 个比特未用 */
char buf[];
};
#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
SDS 提供的接口会根据要保存的内容的大小自动选择合适的结构类型。 以上结构中，除了 sdshdr5 外其他结构都是类似的，都有一个 len 成员表示已用的空间，alloc 表示分配的 buf 的大小， 而 sdshdr5 直接将 len 信息放在了 flags 字段的高 5 位中，而且没有 alloc 字段，这意味着 sdshdr5 在分配空间的时候只会按照实际使用空间大小进行分配，不会出现还有未使用的空间的情况（除非使用了 sdsclear 等操作）。
以上结构中都有一个没有指定大小的 chr buf[] 数组成员，这其实就是 C99 标准的柔性数组 ，这个成员在结构中 本身并不占用内存空间，只是用于指定结构后面的内存。
SDS 有几个特性是我们需要注意的：
sds s = sdsnew("hello");
sds t = sdscat(s, " world");
在调用完 sdscat 后，应该使用 t 来进行后面的操作，并且所有原先对 s 的引用都应该改为 t，因为调用完 sdscat 后，s 原先的内存地址有可能已经被释放掉了。
在这部分我们将对 SDS 提供所有的 API 进行详细讲解。
typedef char *sds;
sds sdsnewlen(const void *init, size_t initlen);
sds sdsnew(const char *init);
sds sdsempty(void);
sds sdsdup(const sds s);
创建内容为 init 和 initlen 指定的 SDS 字符串，如果 init 为 NULL，则字符串会被初始化为长度为 initlen 的以 '\0' 填充的字符串，如果 init 为 SDS_NOINIT 则字符串为长度为 initlen 的未初始化的字符串。
可以看到 sds 实际就是字符串指针，实际上 sds 就是指向 sdshdrx 的 buf 位置，因此，SDS API 可以通过 sds[-1] 获取这个 sds header 的实际类型，从而根据类型获取 len，alloc 等信息。
而如果 sds 保存的是 C 函数兼容的字符串，则可以直接将 sds 传给 printf() 等 C 库函数。 字符串会以 '\0' 结尾（所有的 SDS 字符串都是这样），因此即使你通过如下方式创建 SDS：
mystring = sdsnewlen("abc",3);
你可以安全的将 mystring 传给 printf()，因为 mystring[3] 总是等于 '\0'。 SDS 是二进制安全的，即使在字符串中间保存 '\0' 字符也是没问题，这时你可以通过保存在 SDS header 的 length 获取 SDS 的真正长度（可以直接使用 sdslen 函数）。
创建一个内容为以 NULL 结尾的字符串，这个函数会通过 strlen 获取 init 的长度,然后调用带长度版本的 sdsnew。
sds sdsnew(const char *init) {
size_t initlen = (init == NULL) ? 0 : strlen(init);
return sdsnewlen(init, initlen);
}
创建空的 SDS，通过如下方式创建：
sds sdsempty(void) {
return sdsnewlen("",0);
}
复制一个 SDS
sds sdsdup(const sds s) {
return sdsnewlen(s, sdslen(s));
}
void sdsfree(sds s);
当 s 为 NULL 时，不作任何操作
sds sdsgrowzero(sds s, size_t len);
如果指定的长度比 SDS 本身的长度要小，则这个函数不会进行任何操作
sds sdscatlen(sds s, const void *t, size_t len);
sds sdscat(sds s, const char *t);
sds sdscatsds(sds s, const sds t);
追加长度为 len 的数据到 s 中，此函数执行完后，s 有可能不再有效，因此所有对 s 的引用必须替换为函数返回的指针。
sds sdscat(sds s, const char *t) {
return sdscatlen(s, t, strlen(t));
}
将 t 的数据追加到 s 中，内部调用 sdscatlen 实现。
sds sdscpylen(sds s, const char *t, size_t len);
sds sdscpy(sds s, const char *t);
调用完这两个函数后，s 可能就无效了，所有对 s 的引用都应该用函数的返回值替代。
sds sdscatvprintf(sds s, const char *fmt, va_list ap);
sds sdscatprintf(sds s, const char *fmt, ...);
sds sdscatfmt(sds s, char const *fmt, ...);
先用 vsnprintf 格式化数据，然后将格式化后的数据使用 sdscat 追加到 s 中。
内部调用 sdscatvprintf。比较有意思的是这个函数在头文件的声明：
#ifdef __GNUC__
sds sdscatprintf(sds s, const char *fmt, ...)
__attribute__((format(printf, 2, 3)));
#else
sds sdscatprintf(sds s, const char *fmt, ...);
#endif
如果使用的是 GNUC 则添加了 __attribute__((format(printf, 2, 3))) 声明。这个属性声明的详细作用可以查看： https://gcc.gnu.org/onlinedocs/gcc-8.3.0/gcc/Common-Function-Attributes.html#Common-Function-Attributes 这里简单讲解下这个属性声明的作用，对 sdscatprintf 函数参数进行类型检查，其中第二个参数为格式化参数，格式与 printf 的格式字符串一样， 从这个函数的第三个参数开始检查，添加此属性后，如果发现后面的参数格式与格式化字符串需要的格式不一致编译器会报 Warning。
前面两个格式化函数都使用了 C 函数的 vsnprintf，而这个函数通常很慢， 因此 SDS 自己实现了一个类似 sdscatvprintf 的高效的格式化函数。
但是这个函数只能处理部分与 printf 不兼容的格式说明符：
sds sdstrim(sds s, const char *cset);
void sdsrange(sds s, ssize_t start, ssize_t end);
void sdsupdatelen(sds s);
void sdsclear(sds s);
void sdstolower(sds s);
void sdstoupper(sds s);
去掉字符串两边的由 'cset' 里的字符组成的连续子串。
注意：无论从函数的声明还是源码的注释来看，在调用完这个函数后，都应该假设传进去的 SDS 已经无效。 但是从 Redis 5.0.4 版本的 sdstrim 的实现来看，传进去的 SDS 总是等于返回的 SDS。
假设有如下代码：
s = sdsnew("AA...AA.a.aa.aHelloWorld :::");
s = sdstrim(s,"Aa. :");
printf("%s\n", s);
结果应该为："HelloWorld"
将 SDS 变为一个只包含由 start 和 end 指定的范围的子字符串。
start 和 end 可以是负数，当为负数时，-1 表示最后一个字符，-2 表示倒数第二个字符，依次类推。 指定的区间是个闭区间，修改后的结果原地修改到字符串中。
比如有如下代码：
s = sdsnew("Hello World");
sdsrange(s,1,-1); => "ello World"
结果为： "ello World"
将 SDS 字符串的长度设置为 strlen() 所获得的长度，就是说当遇到第一个空字符串时就认为字符串已经结束了。
通常可以在手动修改字符串后，使用 sdsupdatelen 更新字符串的长度，比如：
s = sdsnew("foobar");
s[2] = '\0';
sdsupdatelen(s);
printf("%d\n", sdslen(s));
结果为 2，如果不调用 sdsupdatelen 结果应该为 6。
原地清除 SDS 的数据，这个函数只会将 SDS 的 len 设置为 0，以及将 buf[0] 设置为 '\0'。
对里面的每个字符调用 tolower()，将结果写回原地。
对里面的每个字符调用 toupper()，将结果写回原地。
int sdscmp(const sds s1, const sds s2);
用 memcmp() 比较两个 SDS 字符串。 返回值：
当两个 SDS 有相同前缀时，认为长的字符串比短的字符串要大。
sds *sdssplitlen(const char *s, ssize_t len, const char *sep, int seplen, int *count);
void sdsfreesplitres(sds *tokens, int count);
sds *sdssplitargs(const char *line, int *argc);
用 'sep' 分割 's'，返回一组 SDS 字符串，*count 为返回的字符串的大小。
当出现内存不足时，返回 NULL，sep 可以为多个字符，函数内部使用 memcmp 来判断 's' 里面是否有和 'sep' 一样的子串。
释放 sdssplitlen 返回的 SDS 数组。
将 line 分割为多个参数，每个参数都可能是如下的 "programming-language REPL-alike" 形式：
foo bar "newline are supported\n" and "\xff\x00otherstuff"
argc 保存了返回的 sds 数组的数量。
调用者需要使用 sdsfreesplitres() 释放返回的 SDS 数组。
需要注意的是 sdssplitargs() 可以解析 sdscatrepr() 返回的结果回原来的格式。
这个函数会在解析成功后返回 SDS 数组，如果传进来的是空字符串，返回的结果也不为 NULL（此时 argc 为 0）。 如果发现传进来的字符串是非法的（比如，双引号或者单引号不匹配）则会返回 NULL。
sds sdsjoin(char **argv, int argc, char *sep);
sds sdsjoinsds(sds *argv, int argc, const char *sep, size_t seplen);
sds sdsMakeRoomFor(sds s, size_t addlen);
void sdsIncrLen(sds s, ssize_t incr);
sds sdsRemoveFreeSpace(sds s);
size_t sdsAllocSize(sds s);
void *sdsAllocPtr(sds s);
扩大 SDS 的可用空间，使得返回的 SDS 至少有长度为 addlen 的可用空间。 这个函数不会改变 SDS 的 len 大小。
增加 SDS 的长度，并减少可用空间，同样会在字符串末尾添加空字符串。
这个函数的一个使用场景为使用 sdsMakeRoomFor() 为 SDS 创建了一部分可用空间， 然后直接追加了部分数据到 SDS，最后调用这个函数来设置 SDS 的长度。
当 incr 为负数时表示要缩短字符串。
例子：
oldlen = sdslen(s);
s = sdsMakeRoomFor(s, BUFFER_SIZE);
nread = read(fd, s+oldlen, BUFFER_SIZE);
// ... check for nread <= 0 and handle it ...
sdsIncrLen(s, nread);
重新创建 SDS 字符串，使得 SDS 不会有可用空间（就是 alloc == len）。
返回 SDS 所占用的内存大小，包括：
size_t sdsAllocSize(sds s) {
size_t alloc = sdsalloc(s);
return sdsHdrSize(s[-1])+alloc+1;
}
返回创建 SDS 时所申请的内存空间的指针 （通常来说返回的 SDS 都是指向数据部分）
void *sdsAllocPtr(sds s) {
return (void*) (s-sdsHdrSize(s[-1]));
}
void *sds_malloc(size_t size);
void *sds_realloc(void *ptr, size_t size);
void sds_free(void *ptr);
这几个函数主要用于外部程序使用，当外部需要自己创建 SDS 或者是否 SDS 时，需要使用这几个函数。
sds sdsfromlonglong(long long value);
sds sdscatrepr(sds s, const char *p, size_t len);
sds sdsmapchars(sds s, const char *from, const char *to, size_t setlen);
将一个 long long 保存为 SDS 字符串形式。比
sdscatprintf(sdsempty(),"%lld\n", value);
要快得多。
将 p 追加到 s 中，其中 s 为 escaped 字符串，这表示 p 中所有无法打印的字符都会被 escaped，如:
通过这个函数追加的字符串总是以双引号包含起来。
所有对 s 的引用必须替换为函数返回的指针。
将 s 中所有出现在 from 的字符替换为 to 中对应的字符。
比如：
sdsmapchars(mystring, "ho", "01", 2)
结果为 "0ell1"