Redis — SDS API 详解

SDS 数据结构typedef char *sds;struct sdshdr {// 记录buf数组中已使用字节的数量// 等于SDS所保存字符串的长度int len;// 记录buf数组中未使用字节的数量int free;// 字节数组,用于保存字符串char buf[];};SDS API...

Future_LL

454人浏览 · 2020-04-18 15:59:26

Future_LL · 2020-04-18 15:59:26 发布

SDS 数据结构

typedef char *sds;
 
struct sdshdr {
    // 记录buf数组中已使用字节的数量
    // 等于SDS所保存字符串的长度
    int len;
    // 记录buf数组中未使用字节的数量
    int free;
    // 字节数组,用于保存字符串
    char buf[];
};

SDS API

函数名称作用复杂度
sdsnew 创建一个包含给定C字符串的SDS O(N)，N为给定C字符串的长度
sdsempty 创建一个不包含任何内容的空SDS O(1)
sdsfree 释放给定的SDS O(N)，N为被释放SDS的长度
sdslen 返回SDS已经使用过的空间字符数 O(1)，直接读取SDS的len属性来直接获得
sdsavail 返回SDS中未使用的空间字符数 O(1)，直接读取SDS的free属性来直接获得
sdsdup 创建一个给定SDS的副本 O(N)，N为给定SDS的长度
sdsclear 清空SDS中字符串保存的内容因为惰性空间释放策略，复杂的为O(1)
sdscat 将C字符串拼接到SDS字符串末尾 O(N)，N为被拼接C字符串的长度
sdscatsds 将SDS拼接到另一个SDS中 O(N)，N为被拼接SDS字符串的长度
sdscpy 将给定的C字符串复制并覆盖到SDS中的字符串 O(N)，N为被复制C字符串的长度
sdsgrowzero 用空字符将SDS扩展至给定的长度 O(N)，N为扩展新增的字节数
sdsrange SDS区间内的数据保留, 区间之外的数据覆盖或清除 O(N)，N为被保留数据的字节数
sdstrim 接受一个SDS和一个C字符串作为参数, 从移除SDS中移除所有在C字符串中出现过的字符 O(N^2)，N为给定C字符串的长度
sdscmp 对比两个SDS字符串是否相等 O(N)，N为两个SDS中较短的那个SDS的长度

API 实现

SDS 创建

创建一个空的sds，len和free都为0，buf数组也为空

sds sdsempty(void) {
    return sdsnewlen("",0);
}

创建一个sds（空的或非空）

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

其中均会调用sdsnewlen，这个函数主要是分配内存和赋值

sds sdsnewlen(const void *init, size_t initlen) {
    struct sdshdr *sh;
 
    sh = malloc(sizeof(struct sdshdr)+initlen+1);
#ifdef SDS_ABORT_ON_OOM
    if (sh == NULL) sdsOomAbort();
#else
    if (sh == NULL) return NULL;
#endif
    sh->len = initlen;
    sh->free = 0;
    if (initlen) {
        if (init) memcpy(sh->buf, init, initlen);
        else memset(sh->buf,0,initlen);
    }
    sh->buf[initlen] = '\0';
    return (char*)sh->buf;
}

SDS 长度操作

获取 sds 的数据长度

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

获取 sds 的空闲大小

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

更新 sds 的长度信息

void sdsupdatelen(sds s) {
    struct sdshdr *sh = (void*) (s-(sizeof(struct sdshdr)));
    int reallen = strlen(s);
    sh->free += (sh->len-reallen);
    sh->len = reallen;
}

SDS 扩容操作

static 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)*2;   //原先数据+新增数据 的两倍
    newsh = realloc(sh, sizeof(struct sdshdr)+newlen+1);
#ifdef SDS_ABORT_ON_OOM
    if (newsh == NULL) sdsOomAbort();
#else
    if (newsh == NULL) return NULL;
#endif
 
    newsh->free = newlen - len; //两倍数据-原先数据长度，后面free再减去新增数据长度addlen，即可保证free的大小和len的最终的大小相等
    return newsh->buf;
}

函数的参数 addlen是要增加的长度，首先它会跟 free 比较，如果 addlen 小，sds 放得下，无需扩容；如果 addlen 大，则需要扩容，重新分配内存，重新计算的数组大小是原先存放的数据加上新增数据之和的两倍(newlen)，因为一倍给 free，另外一倍存放最终的数据，目前的新 sds 中的free 大小是两倍长度 - 原先的数据大小。

SDS 追加在某个SDS的后面

sdscat 将字符串 t 追加在具有sds结构的 s 后面，并返回一个sds结构（如果没有扩容就是原先那个sds）

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

其中用到了sdscatlen

sds sdscatlen(sds s, 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;   //这个len是新增数据长度，sh->free大小是两倍长度减去原先数据长度，再减个len，即为free字段是原先数据长度加上新增的数据长度，保证和最终的sh->len大小一致
    s[curlen+len] = '\0';
    return s;
}

SDS 将字符串拷贝到SDS中，会覆盖掉原先的数据

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

sds sdscpylen(sds s, char *t, size_t len) {
    struct sdshdr *sh = (void*) (s-(sizeof(struct sdshdr)));
    size_t totlen = sh->free+sh->len;
 
    if (totlen < len) {
        s = sdsMakeRoomFor(s,len-totlen); //此处应该是len- sh->len
        if (s == NULL) return NULL;
        sh = (void*) (s-(sizeof(struct sdshdr)));
        totlen = sh->free+sh->len; //新的sh->free为两倍大小除去原先的数据长度，sh->len为原先的数据长度，现在相加，totlen值为两倍大小
    }
    memcpy(s, t, len);
    s[len] = '\0';
    sh->len = len;     //最终的sds中的len为拷贝的字符串的长度
    sh->free = totlen-len;   最终的sds中的free也为拷贝的字符串的长度（两倍减去了一倍）
    return s;
}

同样最后会保证 free 的大小和 len 的相同。

SDS 通过格式化输出的形式，追加到给定的SDS后

sds sdscatprintf(sds s, const char *fmt, ...) {
    va_list ap;
    char *buf, *t;
    size_t buflen = 32;
 
    va_start(ap, fmt);
    while(1) {
        buf = malloc(buflen);
#ifdef SDS_ABORT_ON_OOM
        if (buf == NULL) sdsOomAbort();
#else
        if (buf == NULL) return NULL;
#endif
        buf[buflen-2] = '\0';     //在倒数第二个打上标记，如果被覆盖了说明分配的内存不够
        vsnprintf(buf, buflen, fmt, ap);
        if (buf[buflen-2] != '\0') {
            free(buf);
            buflen *= 2;
            continue;
        }
        break;
    }
    va_end(ap);
    t = sdscat(s, buf);
    free(buf);
    return t;
}

此函数是以格式化输出的形式追加到给定的 sds 后面，首先默认分配32字节的内存，在倒数第二个字节打上结束标记，然后拷贝格式化输出的内容，如果倒数第二个字节被覆盖，说明分配的大小不够，采取的策略是翻倍尝试，最后调用前面的 sdscat 追加。

SDS 比较两个SDS
- ```
int sdscmp(sds s1, 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;
    return cmp;
}
```
- sds s1和s2保存的字符串长度可能不一样，如果长度一样的话，直接调用 memcmp 比较即可，如果不一样的话，首先需要计算出较小的长度 minlen，调用 memcmp 比较前 minlen 个字符串，如果前 minlen 个不一样的话，直接返回比较结果（此时已出胜负），如果前 minlen 个是一样的，则较长的为大。

SDS 对给定的字符串按给定的 sep 分隔符来切割

/* Split 's' with separator in 'sep'. An array
 * of sds strings is returned. *count will be set
 * by reference to the number of tokens returned.
 *
 * On out of memory, zero length string, zero length
 * separator, NULL is returned.
 *
 * Note that 'sep' is able to split a string using
 * a multi-character separator. For example
 * sdssplit("foo_-_bar","_-_"); will return two
 * elements "foo" and "bar".
 *
 * This version of the function is binary-safe but
 * requires length arguments. sdssplit() is just the
 * same function but for zero-terminated strings.
 */
sds *sdssplitlen(char *s, int len, char *sep, int seplen, int *count) {
    int elements = 0, slots = 5, start = 0, j;
 
    sds *tokens = malloc(sizeof(sds)*slots);
#ifdef SDS_ABORT_ON_OOM
    if (tokens == NULL) sdsOomAbort();
#endif
    if (seplen < 1 || len < 0 || tokens == NULL) return NULL;
    for (j = 0; j < (len-(seplen-1)); j++) {
        /* make sure there is room for the next element and the final one */
        if (slots < elements+2) {
            slots *= 2;
            sds *newtokens = realloc(tokens,sizeof(sds)*slots);
            if (newtokens == NULL) {
#ifdef SDS_ABORT_ON_OOM
                sdsOomAbort();
#else
                goto cleanup;
#endif
            }
            tokens = newtokens;
        }
        /* search the separator */
        if ((seplen == 1 && *(s+j) == sep[0]) || (memcmp(s+j,sep,seplen) == 0)) {
            tokens[elements] = sdsnewlen(s+start,j-start);
            if (tokens[elements] == NULL) {
#ifdef SDS_ABORT_ON_OOM
                sdsOomAbort();
#else
                goto cleanup;
#endif
            }
            elements++;
            start = j+seplen;
            j = j+seplen-1; /* skip the separator */
        }
    }
    /* Add the final element. We are sure there is room in the tokens array. */
    tokens[elements] = sdsnewlen(s+start,len-start);
    if (tokens[elements] == NULL) {
#ifdef SDS_ABORT_ON_OOM
                sdsOomAbort();
#else
                goto cleanup;
#endif
    }
    elements++;
    *count = elements;
    return tokens;
 
#ifndef SDS_ABORT_ON_OOM
cleanup:
    {
        int i;
        for (i = 0; i < elements; i++) sdsfree(tokens[i]);
        free(tokens);
        return NULL;
    }
#endif
}

比如字符串 foo_-_bar_-_fun使用分割符_-_，分割符长度是3，最后得到3个（count的值）sds *结构的 tokens，tokens[0] 存放的是sds结构的 foo，tokens[1] 存放的是 sds 结构的 bar，tokens[2] 存放的是 sds 结构的 foo。

SDS 字符串范围操作

sdsrange----截取给定的sds，[start, end]字符串。如start为3，表示字符串中第4个字符，字符串下标从0开始，如为-1，表示是最后一个字符，同理-2表示倒数第2个字符。

sds sdsrange(sds s, long start, long end) {
    struct sdshdr *sh = (void*) (s-(sizeof(struct sdshdr)));
    size_t newlen, len = sdslen(s);
 
    if (len == 0) return s;
    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) {
        if (start >= (signed)len) start = len-1;
        if (end >= (signed)len) end = len-1;
        newlen = (start > end) ? 0 : (end-start)+1;
    } else {
        start = 0;
    }
    if (start != 0) memmove(sh->buf, sh->buf+start, newlen);
    sh->buf[newlen] = 0;
    sh->free = sh->free+(sh->len-newlen);
    sh->len = newlen;
    return s;
}

sdstrim---对给定sds，删除前端/后端在给定的C字符串中出现过的字符。

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 复制操作
- 返回一个新的sds，内容与给定的 s 相同。
- ```
sds sdsdup(const sds s) {
    return sdsnewlen(s, sdslen(s));
}
```

SDS 释放操作

void sdsfree(sds s) {
    if (s == NULL) return;
    free(s-sizeof(struct sdshdr));
}

CSDN学习社区

CSDN联合极客时间，共同打造面向开发者的精品内容学习社区，助力成长！

更多推荐

玩转 AIGC 工具，早点下班！

CSDN学习社区

用 OpenAI Assistants 做大模型应用开发

CSDN学习社区

1 小时解读鸿蒙 10 大热点问题

CSDN学习社区

所有评论(0)

查看更多评论

Future_LL

@Future_LL

已为社区贡献2条内容

函数名称	作用	复杂度
sdsnew	创建一个包含给定C字符串的SDS	O(N)，N为给定C字符串的长度
sdsempty	创建一个不包含任何内容的空SDS	O(1)
sdsfree	释放给定的SDS	O(N)，N为被释放SDS的长度
sdslen	返回SDS已经使用过的空间字符数	O(1)，直接读取SDS的len属性来直接获得
sdsavail	返回SDS中未使用的空间字符数	O(1)，直接读取SDS的free属性来直接获得
sdsdup	创建一个给定SDS的副本	O(N)，N为给定SDS的长度
sdsclear	清空SDS中字符串保存的内容	因为惰性空间释放策略，复杂的为O(1)
sdscat	将C字符串拼接到SDS字符串末尾	O(N)，N为被拼接C字符串的长度
sdscatsds	将SDS拼接到另一个SDS中	O(N)，N为被拼接SDS字符串的长度
sdscpy	将给定的C字符串复制并覆盖到SDS中的字符串	O(N)，N为被复制C字符串的长度
sdsgrowzero	用空字符将SDS扩展至给定的长度	O(N)，N为扩展新增的字节数
sdsrange	SDS区间内的数据保留, 区间之外的数据覆盖或清除	O(N)，N为被保留数据的字节数
sdstrim	接受一个SDS和一个C字符串作为参数, 从移除SDS中移除所有在C字符串中出现过的字符	O(N^2)，N为给定C字符串的长度
sdscmp	对比两个SDS字符串是否相等	O(N)，N为两个SDS中较短的那个SDS的长度

Redis — SDS API 详解

Future_LL

SDS 数据结构

SDS API

API 实现

SDS 创建

SDS 长度操作

SDS 扩容操作

SDS 追加在某个SDS的后面

SDS 将字符串拷贝到SDS中，会覆盖掉原先的数据

SDS 通过格式化输出的形式，追加到给定的SDS后

SDS 比较两个SDS

SDS 对给定的字符串按给定的 sep 分隔符来切割

SDS 字符串范围操作

SDS 复制操作

SDS 释放操作

所有评论(0)

Future_LL