sds的定义：
redis没有直接使用C语言传统的字符串表示（以空字符结尾的字符数组，以下简称C字符串），而是构建了名为简单动态字符串（simple dynamic string, SDS）的抽象类型，并将SDS用作Redis的默认字符串表示。
在Redis里面，C字符串指挥作为字符串字面量（string literal)用在一些无须对字符串值进行修改的地方，比如打印日志：
serverLog(LL_WARNING,"Fail to fsync the AOF file: %s",strerror(errno));
当Redis需要的不仅仅是一个字符串字面量，而是一个可以被修改的字符串值时，Redis就会使用SDS来表示字符串值。
sds的结构：
#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
/* Note: sdshdr5 is never used, we just access the flags byte directly.
* However is here to document the layout of type 5 SDS strings. */
struct __attribute__ ((__packed__)) sdshdr5 {
unsigned char flags; /* 3 lsb of type, and 5 msb of string length */
char buf[];
};
struct __attribute__ ((__packed__)) sdshdr8 {
uint8_t len; /* used */
uint8_t alloc; /* excluding the header and null terminator */
unsigned char flags; /* 3 lsb of type, 5 unused bits */
char buf[];
};
struct __attribute__ ((__packed__)) sdshdr16 {
uint16_t len; /* used */
uint16_t alloc; /* excluding the header and null terminator */
unsigned char flags; /* 3 lsb of type, 5 unused bits */
char buf[];
};
struct __attribute__ ((__packed__)) sdshdr32 {
uint32_t len; /* used */
uint32_t alloc; /* excluding the header and null terminator */
unsigned char flags; /* 3 lsb of type, 5 unused bits */
char buf[];
};
struct __attribute__ ((__packed__)) sdshdr64 {
uint64_t len; /* used */
uint64_t alloc; /* excluding the header and null terminator */
unsigned char flags; /* 3 lsb of type, 5 unused bits */
char buf[];
};
知识点：
1.__attribute__ ((__packed__))的作用就是告诉编译器取消结构在编译过程中的优化对齐，按照实际占用字节数进行对齐，是 GCC 特有的语法。具体看以下两篇文章：
https://blog.csdn.net/wangzhaotongalex/article/details/22729215
https://winddoing.github.io/post/12087.html
2.LSB、MSB
LSB（Least Significant Bit），意为最低有效位。
MSB（Most Significant Bit），意为最高有效位。
具体看以下文章：
https://blog.csdn.net/qq_36187285/article/details/103946134
3.uint8_t\uint_16_t\uint32_t\uint64_t
这些数据类型中都带有_t, _t 表示这些数据类型是通过typedef定义的，而不是新的数据类型。也就是说，它们其实是我们已知的类型的别名。
/* exact-width unsigned integer types */
typedef unsigned char uint8_t;
typedef unsigned short int uint16_t;
typedef unsigned int uint32_t;
typedef unsigned __INT64 uint64_t;
具体看以下文章：
https://blog.csdn.net/weixin_42108484/article/details/82692087
4.英文解释：
excluding：除开
null terminator:结束符，'\0'
5.数据结构分析：
sdshr5:
flag:最低有效位的3位作为是sdshr5的标识，最高有效位的5位记录字符串长度
buf[]:字符数组记录内容
sdshr8/16/32/64:
len:记录字符串的真正长度
alloc:除去结构体中header和结束符的空间大小，表示目前可以容纳的字符串最大长度
flags:最低有效位的3位作为是sdshrX的标识,其余五位暂未使用
buf[]:字符数组记录内容
内存的布局示例图（sdshdr5header中只有flags）：
sds.h部分的宏定义：
#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)
1.SDS_TYPE_MASK的二进制的最低三个有效位是1，所以可以通过
sdshdr.flags&SDS_TYPE_MASK来获取到sds的具体类型
2.SDS_TYPE_BITS表示flags中表示类型的比特数为3
用法：SDS_TYPE_5 | (newlen << SDS_TYPE_BITS)
长度左移三位，再和SDS_TYPE_5(0)进行或操作，最后能得到sdshdr5中的flags
3.SDS_HDR_VAR(T,s)，这里需要注意宏定义中的##是将两个符号连接成一个，如sdshdr和8（T为8）合成sdshdr8。这里相当于有了一个sh的指针
用法：
SDS_HDR_VAR(8,s);
return sh->alloc - sh->len;
4.SDS_HDR(T,s)，获取sds的头指针
5.SDS_TYPE_5_LEN(f)，获取sdshdr5的长度
sds的优点：
1.常数复杂度获取字符串长度：
C字符串不记录自身长度信息，获取长度的时候必须遍历整个字符串，复杂度O(N),而sds分配空间专门记录长度。
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); //sdshdr5的header只有flags
case SDS_TYPE_8:
return SDS_HDR(8,s)->len; //SDS_HDR获取到sds的header
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;
}
知识点：
1.inline：从C99开始出现的。它要解决的问题很明确，对于那些短小精干频繁调用的函数，如果是inline的，编译的时候，函数调用位置会被替换成函数的代码块，省掉了函数调用的压栈出栈等操作，可以加快程序的执行速度，代价只是增加了一点点程序文件的体积
具体看以下文章：
https://www.maixj.net/ict/c-inline-24402
2.杜绝缓冲区溢出：
C字符串不记录自身长度带来的另一个问题是容易造成缓冲区溢出（buffer overflow),一般是没有事先分配好足够的空间给接下来的操作，如strcat。但SDS的API做类似操作的时候会先检查然后扩容。
#define SDS_MAX_PREALLOC (1024*1024)
sds sdscatsds(sds s, const sds t) {
return sdscatlen(s, t, sdslen(t));
}
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);
s[curlen+len] = '\0';
return s;
}
sds sdsMakeRoomFor(sds s, size_t addlen) {
void *sh, *newsh;
size_t avail = sdsavail(s); //目前s中未使用的长度
size_t len, newlen, reqlen;
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 = (char*)s-sdsHdrSize(oldtype); //获取s的header指针
reqlen = newlen = (len+addlen); //扩容后所需的长度
assert(newlen > len); /* Catch size_t overflow */
if (newlen < SDS_MAX_PREALLOC) //如果新长度小于1024*1024
newlen *= 2;
else
newlen += SDS_MAX_PREALLOC;
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); //header占的大小
assert(hdrlen + newlen + 1 > reqlen); /* Catch size_t overflow */
if (oldtype==type) {
newsh = s_realloc_usable(sh, hdrlen+newlen+1, &usable); //zrealloc_usable
if (newsh == NULL) return NULL;
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); //zmalloc_usable
if (newsh == NULL) return NULL;
memcpy((char*)newsh+hdrlen, s, len+1); //把原来buf中数据复制到新地址上
s_free(sh);
s = (char*)newsh+hdrlen;
s[-1] = type;
sdssetlen(s, len); //设置S的长度
}
usable = usable-hdrlen-1;
if (usable > sdsTypeMaxSize(type)) //每种类型的最大长度
usable = sdsTypeMaxSize(type);
sdssetalloc(s, usable);
return s;
}
知识点：
1.zrealloc_usable：zmalloc.c中会讲
2.zmalloc_usable：zmalloc.c中会讲
3.s[-1]:数组下标为-1的地址对于数组来说是越界访问了，但是这个地址是有意义的这个地址就是所申请的数组存储空间的首地址的向前偏移一个单位。sdshdr中的flags
4.s_free：zfree
3.减少了修改字符串时带来的内存重分配次数：
如同上面所说C语言容易发生的缓冲区溢出的情况，还有一种风险存在。比如截断（trim）操作的时候，程序需要通过内存重分配来释放字符串不再使用的那部分空间，如果忘记了就会产生内存泄漏。但内存重分配是开销较大的操作，对于redis中的经常需要修改的字符串来说并不是一个合理的设计。所以应该尽量减少内存的重分配次数：
3.1空间预分配：用于优化SDS的字符串增长操作，当API进行SDS空间扩展的时候，程序不仅和为SDS分配修改所必须要的空间，还会为SDS分配额外的未使用空间（具体回看sdshdr）。
extern const char *SDS_NOINIT;
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); //根据长度来获得具体类型
/* Empty strings are usually created in order to append. Use type 8
* since type 5 is not good at this. */
if (type == SDS_TYPE_5 && initlen == 0) type = SDS_TYPE_8;
int hdrlen = sdsHdrSize(type); //获取header的长度
unsigned char *fp; /* flags pointer. */
assert(initlen + hdrlen + 1 > initlen); /* Catch size_t overflow */
sh = s_malloc(hdrlen+initlen+1);
if (sh == NULL) return NULL;
if (init==SDS_NOINIT)
init = NULL;
else if (!init)
memset(sh, 0, hdrlen+initlen+1);
s = (char*)sh+hdrlen;
fp = ((unsigned char*)s)-1;
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);
s[initlen] = '\0';
return s;
}
知识点：
1.extern const char *SDS_NOINIT：
3.2惰性空间释放：用于优化SDS的字符串缩短操作，当API进行SDS空间缩短的时候，程序并不立即使用内存重分配来回收缩短后多出来的字节，而是使用len和alloc属性，先将长度记录下来。
sds sdstrim(sds s, const char *cset) {
char *start, *end, *sp, *ep;
size_t len;
sp = start = s;
ep = end = s+sdslen(s)-1;
while(sp <= end && strchr(cset, *sp)) sp++; //sp移动到s中没有该字符的地方
while(ep > sp && strchr(cset, *ep)) ep--;
len = (sp > ep) ? 0 : ((ep-sp)+1);
if (s != sp) memmove(s, sp, len);
s[len] = '\0';
sdssetlen(s,len);
return s;
}
知识点：
1.strchr:用来查找某字符在字符串中首次出现的位置
2.memmove：memmove() 与 memcpy() 类似都是用来复制 src 所指的内存内容前 num 个字节到 dest 所指的地址上。不同的是，memmove() 更为灵活，当src 和 dest 所指的内存区域重叠时，memmove() 仍然可以正确的处理，不过执行效率上会比使用 memcpy() 略慢些。