Simple Dynamic String

[TOC]

简介

鉴于 c 没有提供一般的字符串处理方式，导致对字符串的各种处理都很麻烦，所以 redis 自身实现了一个 简单动态字符串 对象，用于操作所有的字符串，同时为了跟 c 兼容，所以 sds 在实现的时候保证了它能直接适用于 标准库 提供的各种 strxxx 函数。

因为这个实现本身不是很复杂，所以这里不会每个细节都介绍，而是选择主要的实现进行简单的说明。

typedef char *sds;
struct sdshdr {
    unsigned int len; // len 字段指的是当前 sds 的长度
    unsigned int free; // free 指的是 buff 中剩余的长度
    char buf[];
};

把 char* 定义成 sds 好处是，sds 其实就是 c 语言的字符串，能够兼容 c 标准库的 strXXX 函数。而上面定义的 sdshdr 事实上并不会直接返回给调用者，那它是如何做到兼容标准库的呢，答案就在于 sdshdr 的最后一个字段 buf。

实现

新建 sds 与如何兼容标准 C 字符串

我们先来说明每个字段的作用，然后在通过新建一个 sds 实例来说明实际的实现。

sds sdsnew(const char *init) {
    size_t initlen = (init == NULL) ? 0 : strlen(init);
    return sdsnewlen(init, initlen);
}

sds sdsnewlen(const char *init, size_t initlen) {
    struct sdshdr *sh;
    
    if (init) {
        sh = zmalloc(sizeof(struct sdshdr) + initlen + 1);
    }
    else {
        sh = zcalloc(sizeof(struct sdshdr) + initlen + 1);
    }
    
    if (sh == NULL) return NULL;
    
    sh->len = initlen;
    sh->free = 0;
    if (initlen && init)
        memcpy(sh->buf, init, initlen);
    sh->buf[initlen] = '\0';
    return (char*)sh->buf;
}

接着开始分析以上的实现，首先要创建一个新的 sds 实例，就要调用 sdsnew, 并传递一个初始内容 init, 并且算出初始内容 init 的长度 initlen, 接着调用 sdsnewlen，这里就是真正初始化 sds 实例的地方了。

首先会判断 init 是否为空，如果不为空，则调用 zmalloc，否则调用 zcalloc，这里是一个比较低层次的优化，如果 init 不为空的话，那稍后会以 init 的内容来填充 sdshdr 的 buf，所以就没必要再使用 zcalloc 来为他填充 0 了。 另一点需要注意的是我们看到，在申请内存时，申请的是实际大小再 +1, 这是因为，sds 的字符串都会以 '\0' 空字符为结束符，所以需要申请多一个字节大小的空间。 接下来的就都是常规的初始化，包括初始化长度、剩余空间(为 0, 因为申请的空间刚好可用于存放 init)、跟 buf。最后的 重点 就是，返回的是 sh->buf 而不是 sh。所以实际上返回的是一个指向 sh->buf 的指针，这也是 sds 能兼容 c 标准库的重点，我们这里提前说明，由于返回的是 sh->buf，所以之后所有的 sds 接口，在拿到参数 sds xxx 后，都会使用

struct sdshdr *sh = (void *)(s - (sizeof(struct sdshdr)));    

来得到指向 sdshdr 的正确指针。

获取 sds 长度 (sdslen)

因为 sdshdr 本身已经保存了当前字符串的长度，所以可以在 O(1) 的时间内获取到 sds 的长度，而不是类似 strlen，需要使用 O(n) 的时间来遍历字符串获取长度。唯一需要注意的是 长度是不包括 '\0' 字符的。

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

连接字符串 (sdscat、sdscatsds)

sds 提供的连接字符串函数，同时支持 C 字符串跟 sds 字符串，并且能在 O(n) 的时间内完成字符串的连接，下面我们来看看他的实现，连接 C 字符串跟连接 sds 虽然接口不同，但最终调用的实现都是一样的。

sds sdscat(sds s, const char *t) {
    return sdscatlen(s, t, strlen(t));
}

sds sdscatsds(sds s, const sds t) {
    return sdscatlen(s, t, sdslen(t));
}

从上面我们可以看出，两个接口的区别就只在于获取长度的方式不同，最终调用的实现都是 sdscatlen，接下来我们看看它的实现

sds sdscatlen(sds s, const void *t, size_t len) {
    struct sdshdr *h;
    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;
}

整个实现除了 sdsMakeRoomFor 其他的都是常规操作，获取原始字符串的长度，用 sdsMakeRoomFor 申请内存，然后复制新的字符串到原始字符串后面，更新长度信息，更新剩余内存信息，在拼接后的字符串末尾添加 '\0'。

扩展 sds 存储空间

所以我们来看看 sdsMakeRoomFor 到底做了啥

// 扩展 s 的内存空间，以存放额外的 addlen 个长度的字符
sds sdsMakeRoomFor(sds s, size_t addlen) {
    struct adshdr *sh, *newsh;
    size_t free = sdsavail(s); // 获取 s 的剩余空间
    size_t len, newlen;
    
    if (free >= addlen) return s; // 如果剩余空间足够放下 addlen，则直接使用原来的 s
    
    // 到这里说明原有的空间不足以存放 addlen, 所以获取原有 s 的长度，
    // 然后计算新的所需内存大小
    len = sdslen(s);
    newlen = (len + addlen); 
    
    // 这里涉及到一个 sds 的内存申请策略，下面我们会详解
    if (newlen < SDS_MAX_PREALLOC)
        nrewlen *= 2;
    else
        newlen += SDS_MAX_PREALLOC;
        
    // 计算出新的大小后，重新分配内存
    newsh = zrealloc(sh, sizeof(struct sdshdr) + newlen + 1);
    if (newsh == NULL) return NULL;
    
    // 更新剩余大小，然后返回新的 sds
    newsh->free = newlen - len;
    return newsh->buf;
}

因为这里的说明篇幅较长，所以我把它加到代码的注释里了，然后这边需要再重点解释一下的就是 sds 的内存申请策略，在上面我们看到了一个 阀值，由 SDS_MAX_PREALLOC 定义了一个最大值

• 小于这个阀值的情况下，会申请所需内存的两倍大小，以备后续的 sds 操作，简而言之就是以空间换取时间，因为内存申请的代价是较高的。
• 另外一种情况是，如果所需内存已经超过阀值了，则返回申请的大小再加上阀值大小的内存块，这里是为了避免申请过于庞大的内存，造成内存使用压力激增。
• 这个大小一般定义为 2MB.

连接字符串 (sdscat, sdscatlen)

对于大部分的函数，都支持对 C 字符串跟 sds 的互操作，各个函数大致都命名为 sdsxxx 跟 sdsxxxsds，对于 cat 也是，所以之后的各个函数都不会每个都解释。 sdscat 是将 sds 跟其他的字符串连接起来，如果是传递的 C 字符串，那字符串必须以空字符结尾，另一点要注意的是，连接之后原本的 sds 指针会失效，需要使用的是由该函数返回的新的 sds 指针，以下是代码

sds sdscat(sds s, const char *t) {
    return sdscatlen(s, t, strlen(t));
}

sds sdscatlen(sds s, const char *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;
}

复制新的字符串覆盖现有 sds (sdscpy, sdscpylen)

将新的 C 字符串或者 sds 复制到指定的 sds 中，并会覆盖源 sds。

sds sdscpy(sds s, const char *t) {
    return sdscpylen(s, t, strlen(t));
}

sds sdscpylen(sds s, const char *t, size_t len) {
    struct sdshdr *sh = (void *)(s - (sizeof(struct sdshdr)));
    size_t totlen = sh->free + sh->len; // 原有的 buf 总空间
    
    if (totlen < len) { // 如果原有不足以存放新的字符串，则重新申请内存
        // 在原有 buf 的基础上，在申请一块内存，
        // 所以是 len - sh->len
        s = sdsMakeRoomFor(s, len - sh->len); 
        if (s == NULL) return NULL;
        sh = (void *)(s - (sizeof(struct sdshdr)));
        totlen = sh->free + sh->len;
    }
    
    memcpy(s, t, len); // 复制字符串到 sds 中
    s[len] = '\0';
    sh->len = len;
    sh->free = totlen - len;
    return s;
}

格式化输出字符串 拼接到 sds ( sdscattprint )

这个便捷的接口支持以 C 字符串相同的格式化方式来拼接新的字符串到现有的 sds, 当然，也可以直接提供一个空的 sds，用格式化字符串的方式来新建一个 sds。 使用这个接口的好处在于， sds 会帮使用者管理内存，而无需自己再尝试分配内存来格式化字符串，降低了使用的复杂度。

sds sdscatprintf(sds s, const char *fmt, ...) {
    va_list ap;
    char *t;
    va_start(ap, fmt);
    t = sdscatvprintf(s, fmt, ap);
    va_end(ap);
    return t;
}

上面这个接口所做的全部就只是，将变长参处理的开始跟结束提取出来，让 sdscatvprintf 可以专注于格式化的操作。接着看具体的实现

sds sdscatvprintf(sds s, const char *fmt, va_list ap) {
    va_list cpy;
    char staticbuf[1024], *buf = staticbuf, *t;
    size_t buflen = strlen(fmt) * 2;    
    
    // 如果缓存数组的长度小于预估的字符串长度，则以预估的为准
    if (buflen > sizeof(staticbuf)) {
        buf = zmalloc(buflen);
        if (buf == NULL) return NULL;
    }
    else {
        buflen = sizeof(staticbuf);
    }   
    
    while (1) {
        // 放置哨兵
        buf[buflen - 1] = '\0';
        va_copy(cpy, ap);
        vsnprintf(buf, buflen, fmt, cpy);
        va_end(cpy);
        
        // 判断哨兵是否存在
        if (buf[buflen - 2] != '\0') {

            if (buf != staticbuf) zfree(buf);
            buflen *= 2;
            buf = zmalloc(buflen);
            if (buf == NULL) return NULL;
            continue;
        }
        break;
    }
    
    t = sdscat(s, buf);
    if (buf != staticbuf) zfree(buf);
    return t;

• 上面先尝试分配了 1024 个字节的缓存，然后计算出格式化字符串 fmt 的长度 buflen，如果预分配的 1024 个字节小于 buflen 的话，则以 buflen 为准。这么做的原因是因为想尽量不从堆中分配内存来格式化，尽可能的提高效率。
• 然后进入循环，不断的使用标准库的 vsnprintf 格式化字符串
  • 每次尝试都是使用 ap 的一份 copy，并且在格式化之前会在 buf 的倒数第二个位置先放置一个哨兵 '\0', 如果格式化后哨兵元素没有被覆盖，则说明 buf 的长度大于最终格式化后的长度，格式化成功。
  • 否则每次以两倍 buf 的大小重新扩展 buf，用于尝试格式化字符串。 在尝试期间会判断 buf 是否预先准备的 staticbuf，如果不是的话则尝试释放后重新分配。
• 最终调用 sdscat 把格式化好的字符串连接到 s 中并返回。

效率更高的格式化输出 ( sdscatfmt )

前面的 sdscatprint 主要是使用了标准库内置的格式化输出再加上了自身的一些内存管理，而 sdscatfmt 则是连格式化输出都是自己来实现，主要的区别就是处理各个内置的符号，如 %s、%d 等，同时也添加了对于 sds 字符串的支持 (%S)，并且如果字符串的处理是使用 %S 时，可以得到相较于标准库来说非常高的效率。下面我们来看看他的具体实现。

sds sdscatfmt(sds s, const char *fmt, ...) {
    struct sdshdr *sh = (void *)(s - (sizeof(struct sdshdr)));
    size_t initlen = sdslen(s);
    const char *f = fmt;
    int i;
    va_list ap;
    
    va_start(ap, fmt);
    i = initlen;
    // 遍历整个字符串，查找以 % 开头的字符
    while(*f) {
        // 
        case '%':
            next = *(f+1);
            f++;
            switch(next) {
            case 's':
            case 'S':
                // 处理字符串
                str = va_arg(ap, char *);
                l = (next == 's')? strlen(str) : sdslen(str);
                if (sh->free < l) {
                    s = sdsMakeRoomFor(s, l);
                    sh = (void *)(s - (sizeof(struct sdshdr)));
                }
                memcpy(s+i, str, l);
                sh->len += l;
                sh->free -= l;
                i += l;
                break;
            case 'i':
            case 'I':
                // 处理整数
                if (next == 'i')
                    num = var_arg(ap, int)
                else
                    num = va_arg(ap, long long);
                {
                    char buf[SDS_LLSTR_SIZE];
                    l = sdsll2str(buf, num);
                    if (sh->free < l) {
                        s = sdsMakeRoomFor(s, l);
                        sh = (void *)(s - sizeof(struct sdshdr)));
                    }
                    memcpy(s+i, buf, l);
                    sh->len += l;
                    sh->free -= l;
                    i += l;                
                }
                break;
            case 'u':
            case 'U':
                // 处理无符号整数
                if (next == 'u')
                    unum = va_arg(ap, unsigned int);
                else
                    unum = va_arg(ap, unsigned long long);
                {
                    char buf[SDS_LLSTR_SIZE];
                    l = sdsull2str(buf, unum);
                    if (sh->free < l) {
                        s = sdsMakeRoomFor(s, l);
                        sh = (void *)(s-(sizeof(struct sdshdr)));
                    }
                    memcpy(s+i, buf, l);
                    sh->len += l;
                    sh->free -= l;
                    i += l;
                }
                break;
            default:
                s[i++] = next;
                sh->len += 1;
                sh->free -= 1;
                break;
            }
        default:
            s[i++] = *f;
            sh->len += 1;
            sh->free -= 1;
            breka;
        }    
        f++;
    }
    va_end(ap);
    s[i] = '\0';
    return s;
}

这其中还调用了我们未曾分析过的 sdsll2str 以及 sdsull2str，这两个函数分别类似于 atoi 的反向操作，也就是将数字转换成字符串的表示形式，我们大致解释一下实现方式

int sdsll2str(char *s, long long value) {
    char *p, aux;
    unsigned long long v;
    size_t l;
    
    // 取每个数字上 10 的余数，然后除以 10，最后生成逆向的，
    // 也就是从个位开始到高位的数字
    v = (value < 0) ? -value : value;
    p = s;
    do {
        *p++ = '0' + (v%10);
        v /= 10;
    } while(v);
    if (value < 0) *p++ = '-';
    
    /* compute length and add null term */
    l = p - s;
    *p = '\0';
    
    /* 反转字符串得到正向的字符串 */
    p--;
    while (s<p) {
        aux = *s;
        *s = *p;
        *p = aux;
        s++;
        p--;
    }
    return l;
}

删除 sds 前后端的指定字符 ( sdstrim )

类似于其他语言里字符串的 string.trim 等处理，删除前后端的空格，而这个函数则是删除前后指定的字符串。 比如可以指定

sds s = sdsnew("AA..a.aaHelloWorld   :::");
s = sdstrim(s, "Aa. :");
printf("%s\n", s); // 输出 HelloWorld

下面是具体的实现

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

复制 sds 字符串 ( sdsdup )

有时候复制一个字符串也是很有用的，比如在测试的会使用一个测试字符串，不断的使用它的 copy 去测试。具体的实现可以为简单的调用 sdsnewlen,

sds sdsdup(sds s) {
    return sdsnewlen(s, sdslen(s));
}

截断 sds 字符串 ( sdsrange )

跟其他语言内置的 String.SubString 类似，sds 也提供了截断字符串的函数，而对比于其他的实现，sds 还提供了更便捷的使用方式：使用 -1 来表示字符串的最后一个字符, 然后用 -2 表示导数第二个字符，以此类推。如

sds s = sdsnew("Hello World");
sdsrange(s, 1, -2);
printf("%s\n", s); // 输出 ello Worl

下面看具体的实现

void sdsrange(sds s, int start, int end) {
    struct sdshdr *sh = (void *)(s - (sizeof(struct sdshdr)));
    size_t newlen, len = sdslen(s);
    
    if (len == 0) return;
    if (start < 0) {
        start = len + start;
        if (start < 0) start = 0;
    }
    if (end < 0) {
        end = len + end;
        if (end < 0) end = 0;
    }
    
    newlen = (start > end) ? 0 : (end-start)+1;
    if (newlen != 0) {
        // 如果开始长度大于长度，则截断为0.
        if (start >= (signed)len) {
            newlen = 0;
        }
        // 如果结束长度大于长度，则截断到原有的结尾
        else if (end >= (signed)len) {
            end = len-1;
            newlen = (start > end) ? 0 : (end-start)+1;
        }
    }
    else {
        // 如果新长度为 0 则从头开始
        start = 0;
    }
    if (start && newlen) memmove(sh->buf, sh->buf+start, newlen);
    sh->buf[newlen] = '\0';
    sh->free = sh->free+(sh->len-newlen);
    sh->len = newlen;
}

其他函数

以下是其他的便捷函数列表

// 从数字初始化 sds
sdsfromlonglong(long long value);
// 转换大小写
void sdstolower(sds s);
void sdstoupper(sds s);
// 比较 sds 字符串
// positive if s1 > s2; negative if s1 < s2
// 0 if s2 and s2 are exactly the same binary string
int sdscmp(const sds s1, const sds s2);
// 初始化空的 sds
sds sdsempty(void);
// 扩展 sds 字符串的长度
sds sdsgrowzero(sds s, size_t len);