1.定义

1.1 sds定义

typedef char* sds;

sds："Simple Dynamic String" ，简单动态字符串。

1.2 sdshdr定义

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[];
};

sdshdr："Simple Dynamic String Header" ，简单动态字符串的头部。
__attribute__ ((__packed__))：告诉编译器以紧凑的方式排列结构体成员，不进行字节对齐（：https://www.cnblogs.com/INnoVationv2/p/17579732.html）

其他成员的说明如下

struct __attribute__ ((__packed__)) sdshdr8 {
  	// 字符长度
    uint8_t len; 
  	// 已分配空间大小，不包括头部和终止符\0 
    uint8_t alloc; 
  	// 低3位表示SDS类型，高5位未使用
    unsigned char flags;
  	// 实际存储数据
    char buf[];
};

不同类型的sdshdr16，对应不同的字符串，当扩容时，sdshdr的类型会改变

1.3 说明

sds的header是隐藏的

比如有一个sds s1变量，这个变量的实际类型是char* s1，指向的是header中的char buf[]，当需要访问header的信息时，通过以下步骤进行访问

移动s1访问flags获取header类型
根据类型移动指针到header头部
将指针强转为对应header类型的指针
通过指针访问头部数据

比如获取sds的长度：

#define SDS_HDR(T,s) ((struct sdshdr##T *)((s)-(sizeof(struct sdshdr##T))))
#define SDS_TYPE_5_LEN(f) ((f)>>SDS_TYPE_BITS)

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;
}

假设s的长度是sdshdr8，SDS_HDR(8,s)->len就会被扩展为

((struct sdshdr8 *)((s)-(sizeof(struct sdshdr8))))

2.优点

2.1 减少内存分配次数

扩容逻辑

#define SDS_MAX_PREALLOC (1024*1024) //1MB

len = sdslen(s);
// newlen=原有字符串长度+新增字符串长度
newlen = (len+addlen);
assert(newlen > len);   /* Catch size_t overflow */
if (greedy == 1) {
    // 如果小于1MB，每次分配两倍大小的空间
    if (newlen < SDS_MAX_PREALLOC)
        newlen *= 2;
    else
        // 如果大于1MB，那每次多分配1MB
        newlen += SDS_MAX_PREALLOC;
}

如果启用greedy模式

目标字符串长度小于1MB，每次分配两倍大小的空间
如果大于1MB，那每次多分配1MB

比如现有长度是3，要追加一个长度为5的字符串，那么扩容后的长度就是16

好处

内存预分配，减少内存分配次数

缩容

当删除字符串中的部分字符时，默认情况下，在删除字符后，不会回收空间，之后如果再次写入，就无需分配空间，

也可以使用特定函数强制释放空间

2.2 杜绝缓冲区溢出

sds在追加字符串时，会检查原有sds的空间是否充足，如果不足，就会先分配好内存再追加，防止缓冲区溢出的发生

sds sdscatlen(sds s, const void *t, size_t len) {
    size_t curlen = sdslen(s);

  	// 检查空间是否充足，len是待插入字符串t的长度
    s = sdsMakeRoomFor(s,len);
    if (s == NULL) return NULL;
    memcpy(s+curlen, t, len);
    sdssetlen(s, curlen+len);
    s[curlen+len] = '\0';
    return s;
}

2.3 二进制安全

C语言字符串只能用于保存ascii字符，而不能保存任意二进制文件，原因是C语言字符串使用\0结尾，10进制表示就是0，很多函数都依赖这一特性，比如strcmp函数

int strcmp(const char *s1, const char *s2)
{
    for ( ; *s1 == *s2; s1++, s2++)
      if (*s1 == '\0')
        return 0;
    return ((*(unsigned char *)s1 < *(unsigned char *)s2) ? -1 : +1);
}

而二进制文件中0字符经常出现，所以不兼容

而在SDS中，header中保存了字符串长度，这样就杜绝了C语言字符串的问题，比如对比两个字符串，sdsde函数如下，使用memcmp + 数据长度进行比较，因此实现了二进制安全

int sdscmp(const sds s1, const sds s2) {
    size_t l1, l2, minlen;
    int cmp;

    l1 = sdslen(s1);
    l2 = sdslen(s2);
    minlen = (l1 < l2) ? l1 : l2;
    cmp = memcmp(s1,s2,minlen);
    if (cmp == 0) return l1>l2? 1: (l1<l2? -1: 0);
    return cmp;
}