Redis源码阅读--简单动态字符串SDS

从5.20开始开一个新坑，嗯，520是个好的开始呢。“Redis源码阅读”主要解读阅读Redis源码的理解，阅读的源码版本不是最新的，慢慢来手动斜眼笑<-_<-

本文主要介绍如下内容：

简单动态字符串SDS
SDS的优点
SDS API
sds.c部分函数节选

简单动态字符串SDS

Redis中使用了一个叫SDS（simple dynamic string）的字符串,其关键定义如下：

/*
 * 类型别名，用于指向 sdshdr 的 buf 属性
 */
typedef char *sds;

/*
 * 保存字符串对象的结构
 */
struct sdshdr {
    
    // buf 中已占用空间的长度
    int len;

    // buf 中剩余可用空间的长度
    int free;

    // 数据空间
    char buf[];
};

初一看表示这不还是char *，这是坑爹呢，阅读了sds.h和sds.c文件后，发现事情并没有这表面看起来那么简单，嗯，作者是在下一盘很大的棋<-_<-

但我们仔细想想C语言传统的字符串就知道一些端倪了，传统的字符串用起来总感觉好像有点别扭，使用的时候没有python之类的字符串方便好用<-_<-

对于SDS，我们需要注意sds是指向了结构体中buf的这个空间的，只要记住了这点，我们看到如下的函数就不会表示奇怪了

/*
 * 返回 sds 实际保存的字符串的长度
 *
 * T = O(1)
 */
static inline size_t sdslen(const sds s) {
    struct sdshdr *sh = (void*)(s-(sizeof(struct sdshdr)));
    return sh->len;
}

此外，还需要留意，结构体sdshdr中还有len和free两个字段，分别表示sds的目前已经占用的空间的长度和剩余空间的长度。
其中char buf[]可以参考零长度数组

SDS的优点

常数复杂度获取字符串长度
杜绝缓冲区溢出
减少修改字符串时所需的内存重分配次数
二进制安全
兼容部分C字符串函数

这些优点都是相对于C字符串而言的：
常数复杂度获取字符串长度
这个很好理解，因为sdshdr结构中就已经有了长度len表示字符串长度，所以直接获取即可，时间复杂度为常数O(1)。

杜绝缓冲区溢出
C字符串本身不记录自身长度，比较容易出现缓冲区溢出（buffer overflow）问题。比如\<string.h>中的strcat函数可以将src字符串的内容拼接到dest字符串的末尾：

1	char strcat(char dest, const char *src);

如果dest的剩余空间不足以容纳src，那么就会产生缓冲区溢出。

减少修改字符串时所需的内存重分配次数
直接看sdsMakeRoomFor这个API代码一目了然: )

sds sdsMakeRoomFor(sds s, size_t addlen) {
    struct sdshdr *sh, *newsh;
    size_t free = sdsavail(s);
    size_t len, newlen;

    if (free >= addlen) return s;
    len = sdslen(s);
    sh = (void*) (s-(sizeof(struct sdshdr)));
    newlen = (len+addlen);
    if (newlen < SDS_MAX_PREALLOC)
        newlen *= 2;
    else
        newlen += SDS_MAX_PREALLOC;
    newsh = zrealloc(sh, sizeof(struct sdshdr)+newlen+1);
    if (newsh == NULL) return NULL;

    newsh->free = newlen - len;
    return newsh->buf;
}

二进制安全
C字符串中的字符必须符合某种编码（比如ASCII），并且除了字符串的末尾之外，字符串里面不能包含空字符，否则最先被程序读入的空字符将被误认为是字符串结尾，这些限制使得C字符串只能保存文本数据，而不能保存像图片、音频、视频、压缩文件这样的二进制数据。Redis中二进制安全请参考：
二进制安全是什么意思?

SDS API

详情请参考Redis的sds.h文件

#ifndef __SDS_H
#define __SDS_H


#define SDS_MAX_PREALLOC (1024*1024)

#include <sys/types.h>
#include <stdarg.h>

typedef char *sds;

struct sdshdr {
    int len;
    int free;
    char buf[];
};


static inline size_t sdslen(const sds s) {
    struct sdshdr *sh = (void*)(s-(sizeof(struct sdshdr)));
    return sh->len;
}


static inline size_t sdsavail(const sds s) {
    struct sdshdr *sh = (void*)(s-(sizeof(struct sdshdr)));
    return sh->free;
}

sds sdsnewlen(const void *init, size_t initlen);//创建一个指定长度的sds，接受一个指定的C字符串作为初始化值
sds sdsnew(const char *init);//根据给定的C字符串，创建一个相应的sds
sds sdsempty(void);////创建一个只包含空字符串””的sds
size_t sdslen(const sds s);
sds sdsdup(const sds s);//复制给定的sds
void sdsfree(sds s);//释放给定的sds
size_t sdsavail(const sds s);
sds sdsgrowzero(sds s, size_t len);//将给定的sds扩展到指定的长度，空余的部分用\0进行填充
sds sdscatlen(sds s, const void *t, size_t len);将一个C字符串追加到给定的sds对应sdshdr的buf
sds sdscat(sds s, const char *t);
sds sdscatsds(sds s, const sds t);
sds sdscpylen(sds s, const char *t, size_t len);//将一个C字符串复制到sds中，需要依据sds的总长度来判断是否需要扩展
sds sdscpy(sds s, const char *t);

sds sdscatvprintf(sds s, const char *fmt, va_list ap);
#ifdef __GNUC__
sds sdscatprintf(sds s, const char *fmt, ...)
    __attribute__((format(printf, 2, 3)));
#else
sds sdscatprintf(sds s, const char *fmt, ...);
#endif

sds sdscatfmt(sds s, char const *fmt, ...);
sds sdstrim(sds s, const char *cset);
void sdsrange(sds s, int start, int end);
void sdsupdatelen(sds s);
void sdsclear(sds s);
int sdscmp(const sds s1, const sds s2);
sds *sdssplitlen(const char *s, int len, const char *sep, int seplen, int *count);//对给定的字符串s按照给定的sep分隔字符串来进行切割
void sdsfreesplitres(sds *tokens, int count);
void sdstolower(sds s);
void sdstoupper(sds s);
sds sdsfromlonglong(long long value);
sds sdscatrepr(sds s, const char *p, size_t len);
sds *sdssplitargs(const char *line, int *argc);
sds sdsmapchars(sds s, const char *from, const char *to, size_t setlen);
sds sdsjoin(char **argv, int argc, char *sep);

/* Low level functions exposed to the user API */
sds sdsMakeRoomFor(sds s, size_t addlen);
void sdsIncrLen(sds s, int incr);
sds sdsRemoveFreeSpace(sds s);
size_t sdsAllocSize(sds s);

#endif

sds.c部分函数节选

sds sdsnewlen(const void *init, size_t initlen);用指定的指针和长度创建一个新的sds，带注释的源码如下：

sds sdsnewlen(const void *init, size_t initlen) {

    struct sdshdr *sh;

    if (init) {
        // zmalloc不初始化所分配的内存
        sh = zmalloc(sizeof(struct sdshdr)+initlen+1);
    } else {
        // zcalloc 将分配的内存全部初始化为 0
        sh = zcalloc(sizeof(struct sdshdr)+initlen+1);
    }

    // 内存分配失败，返回
    if (sh == NULL) return NULL;

    // 设置初始化长度
    sh->len = initlen;
    // 新 sds 不预留任何空间
    sh->free = 0;
    // 如果有指定初始化内容，将它们复制到 sdshdr 的 buf 中
    // T = O(N)
    if (initlen && init)
        memcpy(sh->buf, init, initlen);
    // 以 \0 结尾
    sh->buf[initlen] = '\0';

    // 返回 buf 部分，而不是整个 sdshdr
    return (char*)sh->buf;
}

/* Create an empty (zero length) sds string. Even in this case the string
 * always has an implicit null term. */
sds sdsempty(void) {
    return sdsnewlen("",0);
}
/* Create a new sds string starting from a null termined C string. */
sds sdsnew(const char *init) {
    size_t initlen = (init == NULL) ? 0 : strlen(init);
    return sdsnewlen(init, initlen);
}

sdscatlen将t中长度为len的内容添加到s的后面

/* Append the specified binary-safe string pointed by 't' of 'len' bytes to the
 * end of the specified sds string 's'.
 *
 * After the call, the passed sds string is no longer valid and all the
 * references must be substituted with the new pointer returned by the call. */
sds sdscatlen(sds s, const void *t, size_t len) {
    struct sdshdr *sh;
    size_t curlen = sdslen(s);

    s = sdsMakeRoomFor(s,len);
    if (s == NULL) return NULL;
    sh = (void*) (s-(sizeof(struct sdshdr)));
    memcpy(s+curlen, t, len);
    sh->len = curlen+len;
    sh->free = sh->free-len;
    s[curlen+len] = '\0';
    return s;
}

sdstrim对sds左右两端进行修剪，清除其中cset指定的所有字符

/* Remove the part of the string from left and from right composed just of
 * contiguous characters found in 'cset', that is a null terminted C string.
 *
 * After the call, the modified sds string is no longer valid and all the
 * references must be substituted with the new pointer returned by the call.
 *
 * Example:
 *
 * s = sdsnew("AA...AA.a.aa.aHelloWorld     :::");
 * s = sdstrim(s,"A. :");
 * printf("%s\n", s);
 *
 * Output will be just "Hello World".
 */

sds sdstrim(sds s, const char *cset) {
    struct sdshdr *sh = (void*) (s-(sizeof(struct sdshdr)));
    char *start, *end, *sp, *ep;
    size_t len;

    sp = start = s;
    ep = end = s+sdslen(s)-1;
    while(sp <= end && strchr(cset, *sp)) sp++;
    while(ep > start && strchr(cset, *ep)) ep--;
    len = (sp > ep) ? 0 : ((ep-sp)+1);
    if (sh->buf != sp) memmove(sh->buf, sp, len);
    sh->buf[len] = '\0';
    sh->free = sh->free+(sh->len-len);
    sh->len = len;
    return s;
}

sdsjoin把参数argv的个字符串拼接起来，并且每个字符串之间用sep隔开

/* Join an array of C strings using the specified separator (also a C string).
 * Returns the result as an sds string. */
sds sdsjoin(char **argv, int argc, char *sep) {
    sds join = sdsempty();
    int j;

    for (j = 0; j < argc; j++) {
        join = sdscat(join, argv[j]);
        if (j != argc-1) join = sdscat(join,sep);
    }
    return join;
}

好了，关于SDS就介绍这么多，有兴趣的读者去读源码哦:)

参考资料

Redis设计与实现
 Redis内部数据结构详解之简单动态字符串(sds)
sizeof与strlen的区别
 C stdarg.h的使用

c语言中__attribute__的意义
 gcc中预定义的宏GNUC
vsnprintf函数用法
 memmove 和 memcpy的区别以及处理内存重叠问题