Redis之简单动态字符串（SDS）

由于传统的C语言字符串存在以下缺陷：

1. O(N)复杂度获取字符串长度；
2. 拷贝等操作可能导致缓存区溢出；
3. 字符串分配的空间没有余量，需要频繁重新分配内存；
4. 不适合存储二进制数据；

SDS的定义

redis自定义了一组SDS的字符串类型，用来存放需要修改的字符串对象。

// sds.h
/* 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.len：存储字符串使用的字符串长度，不包括‘\0’，使用len记录字符串长度使sds可以保存二进制数据；
sds.alloc：buf指向的内存块大小，不包括‘\0’。alloc的内存大小一般都比实际内存要大，拥有一部分余量，避免频繁重新分配；
sds.flag：上述几种结构体的标识，根据字符串长度生成，生成规则如下：

#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
#define SDS_TYPE_BITS 3

// 可以看到这里根据string size坐落在哪个2的幂次区间来选择sds的type
static inline char sdsReqType(size_t string_size) {
    if (string_size < 1<<5)
        return SDS_TYPE_5;
    if (string_size < 1<<8)
        return SDS_TYPE_8;
    if (string_size < 1<<16)
        return SDS_TYPE_16;
#if (LONG_MAX == LLONG_MAX)
    if (string_size < 1ll<<32)
        return SDS_TYPE_32;
    return SDS_TYPE_64;
#else
    return SDS_TYPE_32;
#endif
}

sds.buf：存储字符串的内存块，保持了以‘\0’结尾的习惯，这样可以复用C string的一些函数，避免重复造轮子；

SDS的结构图