Redis源码学习：字符串，redis源码字符串
Redis源码学习：字符串
1.初识SDS
1.1 SDS定义
Redis定义了一个叫做sdshdr(SDS or simple dynamic string)的数据结构。SDS不仅用于 保存字符串，还用来当做缓冲区，例如AOF缓冲区或输入缓冲区等。如下所示，整数len和free分别表示buf数组中已使用的长度和剩余可用的长度，buf是一个原生C字符串，以\0结尾。
sds就是sdshdr中char buf[]的别名，后面能看到，各种操作函数的入参和返回值都是sds而非sdshdr。那sdshdr中的len和free如何访问到？不然不就白定义了吗？答案就是灵活的指针，各种SDS的函数都是：struct sdshdr *sh = (void *)(s - (sizeof(struct sdshdr)))，通过指针偏移计算出sdshdr的首地址。
关于字符串末尾的“\0”始终要注意：len和free中都没把“\0”算进去，例如为字符串”hello”创建sds，最终buf总长度是6，len为5，free为0。
/* 类型别名，用于指向 sdshdr 的 buf 属性 */
typedef char *sds;
/* 保存字符串对象的结构 */
struct sdshdr {
// buf 中已占用空间的长度
int len;
// buf 中剩余可用空间的长度
int free;
// 数据空间
char buf[];
};1.2 SDS操作
有了SDS就可以统一接口，所有字符串函数的操作对象都是SDS而非原生的C字符串。下面分析一些典型的字符串操作，看看SDS是如何实现的。代码注释来自于huangz所著Redis 3.0详细注释版。
1.2.1 新建SDS
Redis内部使用sdsnew()函数，并在其基础上提供了sdsnew()和sdsempty()两个函数。在sdsnew()中，若传入字符串init若为NULL，则创建一个buf只有1个字节的空SDS，否则buf长度是字符串长度加1。len置为字符串长度initlen，free置为0。注意最终返回buf部分，而不是整个sdshdr，这在前面介绍过的sdshdr.h中有定义：typedef char *sds。
/* 根据给定字符串 init ，创建一个包含同样字符串的 sds */
sds sdsnew(const char *init) {
size_t initlen = (init == NULL) ? 0 : strlen(init);
return sdsnewlen(init, initlen);
}
/* 创建并返回一个只保存了空字符串 "" 的 sds */
sds sdsempty(void) {
return sdsnewlen("", 0);
}
/* 根据给定的初始化字符串 init 和字符串长度 initlen 创建一个新的 sds */
sds sdsnewlen(const void *init, size_t initlen) {
struct sdshdr *sh;
// 根据是否有初始化内容，选择适当的内存分配方式
// T = O(N)
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 中
// 以 \0 结尾，T = O(N)
if (initlen && init)
memcpy(sh->buf, init, initlen);
sh->buf[initlen] = '\0';
// 返回 buf 部分，而不是整个 sdshdr
return (char*)sh->buf;
}1.2.2 扩展SDS空间
Redis需要的是一个可以修改的字符串值，所以SDS是可变的。当对SDS中的字符串修改时，长度难免会长了或者短了，这时就要根据需要对SDS进行扩展。Redis的算法比较简单，甚至与Java中ArrayList有些相像。空间不足时重新分配一块大小翻倍的内存，缩小时则维持不变。有一点区别是：在Redis中，如果要扩展的长度超过1MB，那么只会额外分配1MB而不会翻倍。比如修改一个字符串到10MB了，那最终SDS占用空间只是 10MB + 1MB + 1B(“\0”)。
/* 最大预分配长度 */
#define SDS_MAX_PREALLOC (1024*1024)
/* 对 sds 中 buf 的长度进行扩展，确保在函数执行之后，
buf 至少会有 addlen + 1 长度的空余空间（额外的 1 字节是为 \0 准备的）*/
sds sdsMakeRoomFor(sds s, size_t addlen) {
struct sdshdr *sh, *newsh;
// 获取 s 目前的空余空间长度
size_t free = sdsavail(s);
size_t len, newlen;
// s 目前的空余空间已经足够，无须再进行扩展，直接返回
if (free >= addlen) return s;
// 获取 s 目前已占用空间的长度
len = sdslen(s);
sh = (void*) (s-(sizeof(struct sdshdr)));
// s 最少需要的长度
newlen = (len + addlen);
// 根据新长度，为 s 分配新空间所需的大小
if (newlen < SDS_MAX_PREALLOC)
// 如果新长度小于 SDS_MAX_PREALLOC，那么为它分配两倍于所需长度的空间
newlen *= 2;
else
// 否则，分配长度为目前长度加上 SDS_MAX_PREALLOC
newlen += SDS_MAX_PREALLOC;
// T = O(N)
newsh = zrealloc(sh, sizeof(struct sdshdr) + newlen + 1);
// 内存不足，分配失败，返回
if (newsh == NULL) return NULL;
// 更新 sds 的空余长度
newsh->free = newlen - len;
// 返回 sds
return newsh->buf;
}
/* 返回 sds 实际保存的字符串的长度，T = O(1) */
static inline size_t sdslen(const sds s) {
struct sdshdr *sh = (void*)(s - (sizeof