ふわふわ時間

0%

Redis 源码之 sds

Redis 简单字符串的源码读后感 (超500字)。


源码文件 /src/sds.h & sdsalloc.h & /src/sds.c

sds 数据结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
typedef char *sds;  

// --------------------- sds 的头部结构 -------------------------------
/* 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[];
};

可以看出来,sds 本质还是 C 风格字符串,但是由于不需用 \0 作为结尾标志,所以 sds 是二进制安全的,但是为了兼容 C 风格字符串, sds 也以终止字符 \0 结尾,所以 sds 可以直接重用一部分 C 字符串函数库里面的函数。关于 sds 的头部结构,作者定义了四种不同类型的 sdshdr 供程序使用,区别只是存储 lenalloc 使用的整型长度不同,目的应该是为了节省内存。

四种不同类型的 sdshdr 结构一致,主要包括以下几个部分:

  • len:存储 buf 数组的长度,不包括终止字符 \0
  • allocbuf 数组的容量大小
  • flags:sdshdr 的类型

Tips: __attribute__ ((__packed__)) 的作用就是告诉编译器取消结构体在编译过程中的优化对齐,以紧凑模式来分配内存。按照实际占用字节数进行对齐,是 GCC 特有的语法。这个功能是跟操作系统没关系,跟编译器有关。

Tips: 在上述结构体定义中,字符数组 buf 的长度为 0,不占用额外的内存空间,buf 实际指向的是结构体之后的内存空间,如果给这个结构体分配的内容大于这个结构体实际大小,后面多余的部分就是这个 buf 的内容,也可用此类特性实现 C 语言变长数组。

辅助函数

重申:长度 ≠ 容量

获取字符数组 buf 的长度 len

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
// 不同 sdshdr 的类型码
#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

// 类型掩码
#define SDS_TYPE_MASK 7
// 用于 sdshdr 的位运算常量
#define SDS_TYPE_BITS 3
// 依据指向 buf 的指针,获取 sdshdr 的起始地址
#define SDS_HDR(T,s) ((struct sdshdr##T *)((s)-(sizeof(struct sdshdr##T))))
// 得到 sdshdr 的长度
#define SDS_TYPE_5_LEN(f) ((f)>>SDS_TYPE_BITS)

static inline size_t sdslen(const sds s) {
// 获取 flags 的值
// 由于结构体定义使用紧凑模式,所以 s 所指的地址紧接在存储 flags 的地址之后
// 从而 s[-1] 的内容即为 flags,注意不要和 Python 中的 -1 混淆
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;
}

Tips: 宏定义中的 ## 为符号连接操作符。

获取 buf 数组中的剩余可用空间大小

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
// 依据指向 buf 的指针,获取 sdshdr 的起始地址
#define SDS_HDR_VAR(T,s) struct sdshdr##T *sh = (void*)((s)-(sizeof(struct sdshdr##T)));

static inline size_t sdsavail(const sds s) {
unsigned char flags = s[-1];
switch(flags&SDS_TYPE_MASK) {
case SDS_TYPE_5: {
return 0;
}
case SDS_TYPE_8: {
SDS_HDR_VAR(8,s);
return sh->alloc - sh->len;
}
case SDS_TYPE_16: {
SDS_HDR_VAR(16,s);
return sh->alloc - sh->len;
}
case SDS_TYPE_32: {
SDS_HDR_VAR(32,s);
return sh->alloc - sh->len;
}
case SDS_TYPE_64: {
SDS_HDR_VAR(64,s);
return sh->alloc - sh->len;
}
}
return 0;
}

此处使用 SDS_HDR_VAR 而不使用 return SDS_HDR(T,s)->alloc - SDS_HDR(T,s)->len; 的原因可能如下:

  • 为了代码好看
  • 可以少计算一次

SDS_HDR_VAR 的宏定义最后的分号其实可以去掉,详情请见

设置 buf 数组的长度 len

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
static inline void sdssetlen(sds s, size_t newlen) {
unsigned char flags = s[-1];
switch(flags&SDS_TYPE_MASK) {
case SDS_TYPE_5:
{
// 获取存储 flags 的地址
unsigned char *fp = ((unsigned char*)s)-1;
// 低 3 位存 type,高 5 位存长度
*fp = SDS_TYPE_5 | (newlen << SDS_TYPE_BITS);
}
break;
case SDS_TYPE_8:
SDS_HDR(8,s)->len = newlen;
break;
case SDS_TYPE_16:
SDS_HDR(16,s)->len = newlen;
break;
case SDS_TYPE_32:
SDS_HDR(32,s)->len = newlen;
break;
case SDS_TYPE_64:
SDS_HDR(64,s)->len = newlen;
break;
}
}

增加 buf 数组的长度 len

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// newlen = len + inc
static inline void sdsinclen(sds s, size_t inc) {
unsigned char flags = s[-1];
switch(flags&SDS_TYPE_MASK) {
case SDS_TYPE_5:
{
unsigned char *fp = ((unsigned char*)s)-1;
unsigned char newlen = SDS_TYPE_5_LEN(flags)+inc;
*fp = SDS_TYPE_5 | (newlen << SDS_TYPE_BITS);
}
break;
case SDS_TYPE_8:
SDS_HDR(8,s)->len += inc;
break;
case SDS_TYPE_16:
SDS_HDR(16,s)->len += inc;
break;
case SDS_TYPE_32:
SDS_HDR(32,s)->len += inc;
break;
case SDS_TYPE_64:
SDS_HDR(64,s)->len += inc;
break;
}
}

此外还有获取/设置 buf 数组的容量 alloc 的函数,函数逻辑一致便不再赘述。

1
2
3
4
// 获取 `buf` 数组的容量 `alloc`
static inline size_t sdsalloc(const sds s);
// 设置 `buf` 数组的容量 `alloc`
static inline void sdssetalloc(sds s, size_t newlen);

Tips 关于 static inline

  • inline 的作用仅仅是建议编译器做内联开展处理,而不是强制。内联函数(inline)可以减少 CPU 的系统开销,并且程序的整体速度将加快,但当内联函数很大时,会有相反的作用,因此一般比较小的函数才使用内联函数。通常,程序执行时,处理器从内存中读取代码执行。当程序中调用一个函数时,程序跳到存储器中保存函数的位置,开始读取代码执行,执行完后再返回。为了提高速度,C 语言定义了 inline 函数,告诉编译器把函数代码在编译时直接拷贝到程序中,这样就不用执行时另外读取函数代码。
  • static 告诉编译器其他文件看不到这个函数,因此该函数只能在当前文件中被调用。

sds 基本操作

构造函数

  1. sdsnewlen

    根据指针 init 和长度 initlen 构造一个 sds。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    sds sdsnewlen(const void *init, size_t initlen) {
    void *sh; // 头部指针
    sds s; // 存储返回值
    /* static inline char sdsReqType(size_t string_size)
    * 根据字符串长度选择合适的 sdshdr 类型 */
    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;
    /* static inline int sdsHdrSize(char type)
    * 根据 type 返回 sdshdr 的存储空间大小 */
    int hdrlen = sdsHdrSize(type);
    unsigned char *fp; /* flags pointer. */

    /* #define s_malloc zmalloc
    * + 1 是为了存储 \0 */
    sh = s_malloc(hdrlen+initlen+1);
    /* const char *SDS_NOINIT = "SDS_NOINIT";
    * If SDS_NOINIT is used, the buffer is left uninitialized; */
    if (init==SDS_NOINIT)
    init = NULL;
    else if (!init)
    memset(sh, 0, hdrlen+initlen+1);
    if (sh == NULL) return NULL;
    // s 指向 buf 数组首地址
    s = (char*)sh+hdrlen;
    fp = ((unsigned char*)s)-1;
    // 填充 sdshdr 中的 len、alloc、flags
    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); // 填充 buf 字符数组的内容
    s[initlen] = '\0'; // 填充终止字符 \0
    return s; // s 指向 buf 数组首地址
    }

    可以发现生成的 sds 中有:\(len = alloc = initlen\)

  2. sdsempty

    构造一个空的 sds,可以看出 buf 数组长度即使为 0,该 sds 也包含 \0

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

  3. sdsnew

    根据一个 C 风格字符串构造一个 sds 。

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

  4. sdsdup

    复制一个 sds 。

    1
    2
    3
    sds sdsdup(const sds s) {
    return sdsnewlen(s, sdslen(s));
    }

  5. sdsfromlonglong

    将一个 long long 类型转换为 sds,该操作比直接调用 sdscatprintf(sdsempty(),"%lld\n", value); 高效得多。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    sds sdsfromlonglong(long long value) {
    // #define SDS_LLSTR_SIZE 21
    char buf[SDS_LLSTR_SIZE];
    /* int sdsll2str(char *s, long long value)
    * The function returns the length of the null-terminated string
    representation stored at 's'.
    * 's' must point to a string with room for at least
    SDS_LLSTR_SIZE bytes. */
    int len = sdsll2str(buf,value);

    return sdsnewlen(buf,len);
    }

析构函数(请不要沉迷 C++

  1. sdsclear —— 虚假的析构函数

    buf 数组长度设置为 0,但是可以发现并未调用 free,而是将其设置为空闲空间。

    1
    2
    3
    4
    void sdsclear(sds s) {
    sdssetlen(s, 0);
    s[0] = '\0';
    }

  2. sdsfree —— 真实的析构函数

    1
    2
    3
    4
    5
    6
    void sdsfree(sds s) {
    if (s == NULL) return;
    /* #define s_free zfree
    * (char*)s-sdsHdrSize(s[-1]) —— sds 头部的起始地址 */
    s_free((char*)s-sdsHdrSize(s[-1]));
    }

动态调整函数

  1. sdsMakeRoomFor —— 扩容

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    sds sdsMakeRoomFor(sds s, size_t addlen) {
    void *sh, *newsh; // 旧、新的头指针
    size_t avail = sdsavail(s); // 剩余可用空间大小
    size_t len, newlen;
    char type, oldtype = s[-1] & SDS_TYPE_MASK;
    int hdrlen; // 存储新的头部长度

    /* Return ASAP if there is enough space left. */
    if (avail >= addlen) return s;

    len = sdslen(s); // buf 数组目前长度
    sh = (char*)s-sdsHdrSize(oldtype); // 旧的头指针
    newlen = (len+addlen); // buf 数组将来长度
    /* #define SDS_MAX_PREALLOC (1024*1024)
    * 扩容策略:如果 buf 数组将来长度小于 1 M,按两倍给你扩容,大气
    * 如果 buf 数组将来长度不小于 1 M,比要求多给你扩 1 M,精打细算 */
    if (newlen < SDS_MAX_PREALLOC)
    newlen *= 2;
    else
    newlen += SDS_MAX_PREALLOC;

    // newtype (NT 新人类,大雾)
    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); // 新的头部长度
    if (oldtype==type) { // 不需要更改头部的 len 和 flags,直接扩充 buf 数组的容量
    // #define s_realloc zrealloc
    newsh = s_realloc(sh, hdrlen+newlen+1);
    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(hdrlen+newlen+1); // 申请新的内存空间
    if (newsh == NULL) return NULL;
    memcpy((char*)newsh+hdrlen, s, len+1); // len + 1,\0 也被复制
    s_free(sh); // 释放旧空间
    s = (char*)newsh+hdrlen; // 更新 buf 数组首地址
    s[-1] = type; // 更新 flags
    sdssetlen(s, len); // 设置 len,大小没变
    }
    sdssetalloc(s, newlen); // 更新 alloc
    return s;
    }

    可以发现该函数仅在当前剩余可用空间不足时进行扩容,采取的扩容策略类似 vector,可以在尽可能不浪费内存空间的基础上减少扩容操作的次数。当然扩容并不会改变 buf 数组的长度 len

  2. sdsRemoveFreeSpace —— 回收空闲空间

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    sds sdsRemoveFreeSpace(sds s) {
    void *sh, *newsh;
    char type, oldtype = s[-1] & SDS_TYPE_MASK;
    int hdrlen, oldhdrlen = sdsHdrSize(oldtype);
    size_t len = sdslen(s);
    size_t avail = sdsavail(s);
    sh = (char*)s-oldhdrlen;

    /* Return ASAP if there is no space left. */
    if (avail == 0) return s;

    /* Check what would be the minimum SDS header that is just good enough to
    * fit this string. */
    type = sdsReqType(len);
    hdrlen = sdsHdrSize(type);

    /* If the type is the same, or at least a large enough type is still
    * required, we just realloc(), letting the allocator to do the copy
    * only if really needed. Otherwise if the change is huge, we manually
    * reallocate the string to use the different header type. */
    if (oldtype==type || type > SDS_TYPE_8) {
    newsh = s_realloc(sh, oldhdrlen+len+1);
    if (newsh == NULL) return NULL;
    s = (char*)newsh+oldhdrlen;
    } else {
    newsh = s_malloc(hdrlen+len+1);
    if (newsh == NULL) return NULL;
    memcpy((char*)newsh+hdrlen, s, len+1);
    s_free(sh);
    s = (char*)newsh+hdrlen;
    s[-1] = type;
    sdssetlen(s, len);
    }
    sdssetalloc(s, len);
    return s;
    }

    该函数的基本流程和扩容操作类似,可以看出仅仅在旧的头部结构不为 sdshdr8 且新的头部结构为 sdshdr8 时,才会重新申请新的内存空间,不然只是在旧的 sds 基础上调用 zrealloc 调整 buf 数组的容量,使得 \(alloc = len\) 成立。

    注意调用 sdsRemoveFreeSpace 成功返回后,原指针可能会失效,请使用返回的新指针。

  3. sdsIncrLen —— 调整长度

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    void sdsIncrLen(sds s, ssize_t incr) {  // typedef long long ssize_t
    unsigned char flags = s[-1];
    size_t len;
    switch(flags&SDS_TYPE_MASK) {
    case SDS_TYPE_5: {
    // fp 指向存储 flags 的地址
    unsigned char *fp = ((unsigned char*)s)-1;
    unsigned char oldlen = SDS_TYPE_5_LEN(flags);
    /* 增长时需确保剩余可用空间大小充足
    * 缩短时需确保减少量不得超过现有长度 */
    assert((incr > 0 && oldlen+incr < 32) || (incr < 0 && oldlen >= (unsigned int)(-incr)));
    *fp = SDS_TYPE_5 | ((oldlen+incr) << SDS_TYPE_BITS);
    len = oldlen+incr;
    break;
    }
    case SDS_TYPE_8: {
    SDS_HDR_VAR(8,s);
    assert((incr >= 0 && sh->alloc-sh->len >= incr) || (incr < 0 && sh->len >= (unsigned int)(-incr)));
    len = (sh->len += incr);
    break;
    }
    case SDS_TYPE_16: {
    SDS_HDR_VAR(16,s);
    assert((incr >= 0 && sh->alloc-sh->len >= incr) || (incr < 0 && sh->len >= (unsigned int)(-incr)));
    len = (sh->len += incr);
    break;
    }
    case SDS_TYPE_32: {
    SDS_HDR_VAR(32,s);
    assert((incr >= 0 && sh->alloc-sh->len >= (unsigned int)incr) || (incr < 0 && sh->len >= (unsigned int)(-incr)));
    len = (sh->len += incr);
    break;
    }
    case SDS_TYPE_64: {
    SDS_HDR_VAR(64,s);
    assert((incr >= 0 && sh->alloc-sh->len >= (uint64_t)incr) || (incr < 0 && sh->len >= (uint64_t)(-incr)));
    len = (sh->len += incr);
    break;
    }
    default: len = 0; /* Just to avoid compilation warnings. */
    }
    s[len] = '\0'; // 设置终止字符 '\0'
    }

    需要注意的是,变量 incr 可正可负,所以在满足条件的基础上长度可增可减。

Append 操作

  1. sdsgrowzero

    buf 的数组长度增长到给定的 len,如果 \(len < currentLen\),则什么都不做。新增的字节部分,每一位都置为 0。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    sds sdsgrowzero(sds s, size_t len) {
    size_t curlen = sdslen(s);

    if (len <= curlen) return s;
    s = sdsMakeRoomFor(s,len-curlen);
    if (s == NULL) return NULL;

    /* Make sure added region doesn't contain garbage */
    memset(s+curlen,0,(len-curlen+1)); /* also set trailing \0 byte */
    sdssetlen(s, len);
    return s;
    }

  2. sdscatlen

    将二进制安全的字符串附加到现有的 buf 数组之后,注意该函数调用成功后,原指针可能会失效,请使用返回的新指针。

    • t:附加字符串首位地址
    • len:附加字符串长度

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    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;
    }

  3. sdscat

    将 C 风格字符串附加到现有的 buf 数组之后,注意该函数调用成功后,原指针可能会失效,请使用返回的新指针。

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

  4. sdscatsds

    拼接两个 sds,注意该函数调用成功后,原指针可能会失效,请使用返回的新指针。

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

  5. sdscatvprintf

    将格式化字符串拼接到 sds 之后,注意该函数调用成功后,原指针可能会失效,请使用返回的新指针。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    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;

    /* We try to start using a static buffer for speed.
    * If not possible we revert to heap allocation. */
    if (buflen > sizeof(staticbuf)) {
    buf = s_malloc(buflen);
    if (buf == NULL) return NULL;
    } else {
    buflen = sizeof(staticbuf);
    }

    /* Try with buffers two times bigger every time we fail to
    * fit the string in the current buffer size. */
    while(1) {
    // 设置哨兵,测试格式化字符串是否已全部写入 buf 中
    buf[buflen-2] = '\0';
    /* void va_copy(va_list dest, va_list src);
    * The va_copy macro copies src to dest. */
    va_copy(cpy,ap);
    /* int vsnprintf( char *restrict buffer, size_t bufsz,
    const char *restrict format, va_list vlist );
    * writes the results to a character string buffer. At most buflen - 1
    characters are written
    * The resulting character string will be terminated with a
    null character, unless buflen is zero. */
    vsnprintf(buf, buflen, fmt, cpy);
    /* void va_end(va_list ap);
    * The va_end macro performs cleanup for an ap object initialized by a call to va_start or va_copy */
    va_end(cpy);
    if (buf[buflen-2] != '\0') { // 当前 buf 不够长!
    if (buf != staticbuf) s_free(buf);
    buflen *= 2;
    buf = s_malloc(buflen);
    if (buf == NULL) return NULL;
    continue;
    }
    break; // 格式化字符串已全部写入 buf
    }

    /* Finally concat the obtained string to the SDS string and return it. */
    t = sdscat(s, buf);
    if (buf != staticbuf) s_free(buf);
    return t;
    }

    由于不知晓格式化字符串的长度,所以我们需要使用一个 while 循环来测试当前分配的 buf 字符数组的容量是否可以容纳该格式化字符串,每次失败时,我们将 buf 的容量翻倍。

  6. sdscatprintf

    将格式化字符串拼接到 sds 之后,注意该函数调用成功后,原指针可能会失效,请使用返回的新指针。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    sds sdscatprintf(sds s, const char *fmt, ...) {
    va_list ap;
    char *t;
    /* void va_start(va_list ap, parmN);
    * The va_start macro enables access to the variable arguments following
    the named argument parmN. */
    va_start(ap, fmt);
    t = sdscatvprintf(s,fmt,ap);
    va_end(ap);
    return t;
    }

  7. sdscatfmt

    将格式化字符串拼接到 sds 之后,但是比 sdscatprintf 更快,但是其支持以下几种格式化字符串:

    • %s - C String
    • %S - SDS string
    • %i - signed int
    • %I - 64 bit signed integer (long long, int64_t)
    • %u - unsigned int
    • %U - 64 bit unsigned integer (unsigned long long, uint64_t)
    • %% - Verbatim "%" character.

    1
    sds sdscatfmt(sds s, char const *fmt, ...);

  8. sdscatrepr

    将无法打印显式字符的字符数组的转义形式 (eg, "..." or "<hex-number>") 拼接到 sds 之后,注意该函数调用成功后,原指针可能会失效,请使用返回的新指针。

    1
    sds sdscatrepr(sds s, const char *p, size_t len);

拷贝操作

  1. sdscpylen

    丢弃 sds 字符数组中的原内容,将长为 len 的字符串拷贝至 sds 的 buf 中。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    sds sdscpylen(sds s, const char *t, size_t len) {
    if (sdsalloc(s) < len) { // 容量不足,扩容
    s = sdsMakeRoomFor(s,len-sdslen(s));
    if (s == NULL) return NULL;
    }
    memcpy(s, t, len);
    s[len] = '\0';
    sdssetlen(s, len);
    return s;
    }

  2. sdscpy

    丢弃 sds 字符数组中的原内容,将 C 风格字符串拷贝至 sds 的 buf 中。

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

修剪操作

  1. sdstrim

    从 sds 两端开始遍历,出现在 C 风格字符串 cset 中的字符将会被删除。注意该函数调用成功后,原指针可能会失效,请使用返回的新指针。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    sds sdstrim(sds s, const char *cset) {
    char *start, *end, *sp, *ep;
    size_t len;

    sp = start = s; // 指向第一个字符
    ep = end = s+sdslen(s)-1; // 指向终止字符 `\0` 前一字符
    /* char *strchr(const char *str, int ch);
    * Finds the first occurrence of ch (after conversion to char as if
    by (char)ch) in the null-terminated byte string pointed to by str
    (each character interpreted as unsigned char).
    * 从前往后遍历 sds,如果当前指针所指字符出现在 cset 所指字符串中,则指针 +1 */
    while(sp <= end && strchr(cset, *sp)) sp++;
    /* 前一步遍历的终止条件不是越界时有 ep > sp
    * 从后往前遍历 sds,如果当前指针所指字符出现在 cset 所指字符串中,则指针 -1 */
    while(ep > sp && strchr(cset, *ep)) ep--;
    // 计算修剪后的字符串长度
    len = (sp > ep) ? 0 : ((ep-sp)+1);
    /* void* memmove( void* dest, const void* src, size_t count );
    * Copies count characters from the object pointed to by src to the object
    pointed to by dest*/
    if (s != sp) memmove(s, sp, len);
    s[len] = '\0';
    sdssetlen(s,len);
    return s;
    }

    可以发现函数在执行过程中并未调用 free,是否存在内存泄漏的风险?具体需要观察后续对该函数的调用场景进行分析,暂时 MARK。

    虽然作者提示原指针可能会失效,但是在函数中可以发现返回的就是原指针值,表示疑惑。

  2. sdsrange

    依据起始和结束索引下标修剪 sds 字符串,注意:

    • startend 可以为负数,类似数组的下标索引
    • 结果子串的范围为闭区间 \([start, end]\)
    • 该操作是就地进行的

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    void sdsrange(sds s, ssize_t start, ssize_t end) {
    size_t newlen, len = sdslen(s);

    if (len == 0) return;
    if (start < 0) { // 支持负数索引下标
    start = len+start;
    if (start < 0) start = 0; // 绝对值大于字符串长度的负数索引值置为 0
    }
    if (end < 0) {
    end = len+end;
    if (end < 0) end = 0;
    }
    // 计算子串长度
    newlen = (start > end) ? 0 : (end-start)+1;
    if (newlen != 0) {
    if (start >= (ssize_t)len) { // 起始索引值大于等于字符串长度,子串为空
    newlen = 0;
    } else if (end >= (ssize_t)len) { // 结束索引值大于等于字符串长度,置为 len-1
    end = len-1;
    // 因 end 更改,故更新子串长度
    newlen = (start > end) ? 0 : (end-start)+1;
    }
    } else {
    start = 0;
    }
    if (start && newlen) memmove(s, s+start, newlen);
    s[newlen] = 0; // 等价于 s[newlen] = '\0';
    sdssetlen(s,newlen);
    }

    同上,可以发现函数在执行过程中并未调用 free,是否存在内存泄漏的风险?具体需要观察后续对该函数的调用场景进行分析,暂时 MARK。

split 操作

  1. sdssplitlen

    使用长为 seplen 的二进制安全字符串 sep 作为分隔符,将长为 len 的二进制安全字符串 s 分割成 count 个 sds 字符串。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    sds *sdssplitlen(const char *s, ssize_t len, const char *sep, int seplen, int *count) {
    /* elements 存放当前 sds 字符串的个数
    * slots 存放当前已分配内存的 sds 指针数组 tokens 的大小 */
    int elements = 0, slots = 5;
    long start = 0, j;
    sds *tokens; // sds 指针数组

    if (seplen < 1 || len < 0) return NULL;

    tokens = s_malloc(sizeof(sds)*slots); // 先搞五个试试
    if (tokens == NULL) return NULL;

    if (len == 0) {
    *count = 0;
    return tokens;
    }
    // 字符串匹配过程
    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) {
    sds *newtokens;

    slots *= 2; // 扩容采取倍增策略
    newtokens = s_realloc(tokens,sizeof(sds)*slots);
    if (newtokens == NULL) goto cleanup;
    tokens = newtokens;
    }
    /* search the separator
    * int memcmp( const void* lhs, const void* rhs, size_t count );
    * Compares the first count characters of the objects pointed to by lhs and rhs*/
    if ((seplen == 1 && *(s+j) == sep[0]) || (memcmp(s+j,sep,seplen) == 0)) {
    tokens[elements] = sdsnewlen(s+start,j-start);
    if (tokens[elements] == NULL) goto cleanup;
    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) goto cleanup;
    elements++;
    *count = elements;
    return tokens;

    cleanup:
    {
    int i;
    for (i = 0; i < elements; i++) sdsfree(tokens[i]);
    s_free(tokens);
    *count = 0;
    return NULL;
    }
    }

  2. sdsfreesplitres

    1
    2
    3
    4
    5
    6
    7
    /* Free the result returned by sdssplitlen(), or do nothing if 'tokens' is NULL. */
    void sdsfreesplitres(sds *tokens, int count) {
    if (!tokens) return;
    while(count--)
    sdsfree(tokens[count]);
    s_free(tokens);
    }

  3. sdsplitargs

    • Split a line into arguments, where every argument can be in the following programming-language REPL-alike form: foo bar "newline are supported\n" and "\xff\x00otherstuff"
    • The number of arguments is stored into *argc, and an array of sds is returned.
    • The caller should free the resulting array of sds strings with sdsfreesplitres().

    1
    sds *sdssplitargs(const char *line, int *argc)

    偷个懒,用到时再看hhhhh

其他函数

  1. sdsupdatelen

    更新 sds 的长度 len,由于是调用 strlen,故只统计到终止字符 \0(不包括 \0

    1
    2
    3
    4
    void sdsupdatelen(sds s) {
    size_t reallen = strlen(s);
    sdssetlen(s, reallen);
    }

  2. sdsAllocSize

    返回分配内存空间的大小,包括:

    • 头部结构体的大小 sdsHdrSize
    • buf 数组容量 alloc
    • 终止字符 \0 的长度 1

    1
    2
    3
    4
    size_t sdsAllocSize(sds s) {
    size_t alloc = sdsalloc(s);
    return sdsHdrSize(s[-1])+alloc+1;
    }

  3. sdsAllocPtr

    返回 sds 头部起始地址。

    1
    2
    3
    void *sdsAllocPtr(sds s) {
    return (void*) (s-sdsHdrSize(s[-1]));
    }

  4. sdstolower

    转换为小写

    1
    2
    3
    4
    void sdstolower(sds s) {
    size_t len = sdslen(s), j;
    for (j = 0; j < len; j++) s[j] = tolower(s[j]);
    }

  5. sdstoupper

    转换为大写

    1
    2
    3
    4
    5
    void sdstoupper(sds s) {
    size_t len = sdslen(s), j;

    for (j = 0; j < len; j++) s[j] = toupper(s[j]);
    }

  6. sdscmp

    使用 memcmp 实现两个 sds 的比较操作

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    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;
    }

  7. sdsmapchars

    遍历 sds 字符串,将在字符串 from 中出现的字符替换成 to 中对应位置的字符,setlen 为字符串 fromto 的长度。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    sds sdsmapchars(sds s, const char *from, const char *to, size_t setlen) {
    size_t j, i, l = sdslen(s);

    for (j = 0; j < l; j++) {
    for (i = 0; i < setlen; i++) {
    if (s[j] == from[i]) {
    s[j] = to[i];
    break;
    }
    }
    }
    return s;
    }

  8. sdsjoin

    使用 C 风格字符串 sep 作为分隔符,将 C 风格字符串数组拼接为一个 sds。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    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;
    }

  9. sdsjoinsds

    类似于 sdsjoin,将 sds 字符串数组拼接为一个 sds。值得注意的是,使用的字符串分隔符是二进制安全的,而不是 C 风格字符串。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    sds sdsjoinsds(sds *argv, int argc, const char *sep, size_t seplen) {
    sds join = sdsempty();
    int j;

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