动态字符串-sds

• 概述
• • • 数据结构
    • • 结构体
      • 内存图
    • sdsnewlen 创建新的 sds
    • sdsempty 创建新的 sds
    • sdsnew sdsdup 拷贝一个新字符串
    • sdsfree 释放sds字符串
    • sdsclear 清空sds字符串
    • sdsMakeRoomFor 扩充字符串的长度
    • sdsRemoveFreeSpace 回收 sds 中的空闲空间
    • sdsAllocSize 计算sdshdr分配的空间
    • sdsIncrLen 增加 sds 的长度
    • sdsgrowzero 扩充到指定长度，填充0
    • sdscatlen sdscat sdscatsds 追加字符串
    • sdscpylen sdscpylen 复制指定长度的字符串到sds中
    • 工具函数

概述

面向过程的C语言没有可变长的字符串，而面向对象语言里，Java有的final String字符串，StringBuffer、StringBuilder可变长对象，C++中有std::string字节流对象。Redis在sds.c、sds.h文中实现了动态可变字符串。

数据结构

结构体

sds数据结构是一个struct类型的结构体，len是分配的字符串空间的占用长度，free是剩余未使用的长度，buf是被sds指向的真实字符串，最后一个字节被’\0‘填充。

内存图

sdslen函数是获取sds字符串的已近使用长度，sdsavail函数是获取sds字符串的未使用的长度。 const sds s字符串是指向sdshdr中char buf[]的指针字符串，(void*)(s-(sizeof(struct sdshdr)))的含义为sds向前偏移8个字节的地址，其中，len为4个字节，free是4个字节，buf[]是不占用字节的。

/*
 * 返回 sds 实际保存的字符串的长度
 *
 * T = O(1)
 */
static inline size_t sdslen(const sds s) {
    struct sdshdr *sh = (void*)(s-(sizeof(struct sdshdr)));
    return sh->len;
}

/*
 * 返回 sds 可用空间的长度
 *
 * T = O(1)
 */
static inline size_t sdsavail(const sds s) {
    struct sdshdr *sh = (void*)(s-(sizeof(struct sdshdr)));
    return sh->free;
}

sdsnewlen 创建新的 sds

sdsnewlen创建一个新的sds字符串，init是一个void类型的数组，initlen是新字符串的长度，如果init为空就会使用zmalloc创建，不为空就会使用zcalloc创建（有关Redis内存分配操作可以看分享的的第一章）。分配空间时+1操作是为了给字符串增加一个结束符号’\0’。分配空间成功后如果initlen和init都不为空，就会使用memcpy(void *dest, const void *src, size_t n) 函数拷贝init到sh->buf中。
memcpy(void *dest, const void *src, size_t n) 返回的从源src所指的内存地址的起始位置开始拷贝n个字节到目标dest所指的内存地址的起始位置中。

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 中
	// T = O(N)
	if (initlen && init) {
		memcpy(sh->buf, init,
		       initlen);
	}
	// 以 \0 结尾
	sh->buf[initlen] = '\0';

	// 返回 buf 部分，而不是整个 sdshdr
	return (char *) sh->buf;
}

sdsempty 创建新的 sds

调用sdsnewlen创建一个长度为0的空串。

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

sdsnew sdsdup 拷贝一个新字符串

在程序设计时，经常会为了不影响原有变量，而去创建一个克隆拷贝一个新的变量去进行逻辑处理。sdsnew函数中就是给定一个init字符串，如果init不为空就传入有值的initlen。

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

sdsfree 释放sds字符串

sds 是指向sdshdr->bufd的指针，所以要向左偏移sizeof(struct sdshdr)个字节，找到结构体sdshdr分配的地址，调用zfree函数回收地址。

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

sdsclear 清空sds字符串

sdsclear函数是清空字符串，但是不回收空间，只是把sh->buf[0]置为了’\0’。在开发团队都遵守规范的清空下，此作法最高效。

void sdsclear(sds s) {

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

	// 重新计算属性
	sh->free += sh->len;
	sh->len = 0;

	// 将结束符放到最前面（相当于惰性地删除 buf 中的内容）
	sh->buf[0] = '\0';
}

sdsMakeRoomFor 扩充字符串的长度

sdsMakeRoomFor函数为了增加鲁棒性，加入很多的校验。SDS_MAX_PREALLOC是一个define 定义的常量，他的最大的大小是1024*1024个字节。函数的扩容机制并不是根据addlen的长度实际分配的，原字符串大小加上新字符串的长度小于SDS_MAX_PREALLOC，对
newlen扩容两倍，否者分配newlen+SDS_MAX_PREALLOC的长度。

/*
 * 最大预分配长度
 */
#define SDS_MAX_PREALLOC (1024*1024)
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  (1024*1024)
		// 那么为它分配两倍于所需长度的空间
		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;
}

sdsRemoveFreeSpace 回收 sds 中的空闲空间

回收sds中的为使用的空间。sdsMakeRoomFor函数在扩容时，会导致sds字符串有很多的内存空间分配了但是未使用。sdsRemoveFreeSpace正好可以弥补它带来的内存开销。

sds sdsRemoveFreeSpace(sds s) {
	struct sdshdr *sh;

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

	// 进行内存重分配，让 buf 的长度仅仅足够保存字符串内容
	// T = O(N)
	sh = zrealloc(sh, sizeof(struct sdshdr) + sh->len + 1);

	// 空余空间为 0
	sh->free = 0;

	return sh->buf;
}

sdsAllocSize 计算sdshdr分配的空间

公式为：sdshdr 大小 + sdshdr->len +sdshdr->free +1（结束符）

size_t sdsAllocSize(sds s) {
	struct sdshdr *sh = (void *) (s - (sizeof(struct sdshdr)));
	return sizeof(*sh) + sh->len + sh->free + 1;
}

sdsIncrLen 增加 sds 的长度

此函数使用了Debug的assert断言功能，在sh->free >= incr或sh->free >= 0时都会使程序异常终止。通过incr来修改sdshdr的len与free的大小。

void sdsIncrLen(sds s, int incr) {
	struct sdshdr *sh = (void *) (s - (sizeof(struct sdshdr)));

	// 确保 sds 空间足够
	assert(sh->free >= incr);

	// 更新属性
	sh->len += incr;
	sh->free -= incr;

	// 这个 assert 其实可以忽略
	// 因为前一个 assert 已经确保 sh->free - incr >= 0 了
	assert(sh->free >= 0);

	// 放置新的结尾符号
	s[sh->len] = '\0';
}

sdsgrowzero 扩充到指定长度，填充0

调用sdsMakeRoomFor重新配分空间，最后调用memset把这一块内存空间的值设置为0。
void *memset(void *str, int c, size_t n) 复制字符 c（一个无符号字符）到参数 str 所指向的字符串的前 n 个字符。

sds sdsgrowzero(sds s, size_t len) {
	struct sdshdr *sh = (void *) (s - (sizeof(struct sdshdr)));
	size_t totlen, curlen = sh->len;
	// 如果 len 比字符串的现有长度小，
	// 那么直接返回，不做动作
	if (len <= curlen) { return s; }
	// 扩展 sds
	// T = O(N)
	s = sdsMakeRoomFor(s, len - curlen);
	// 如果内存不足，直接返回
	if (s == NULL) { return NULL; }
	/* Make sure added region doesn't contain garbage */
	// 将新分配的空间用 0 填充，防止出现垃圾内容
	// T = O(N)
	sh = (void *) (s - (sizeof(struct sdshdr)));
	//memset 将某一块内存中的内容全部设置为指定的值
	memset(s + curlen, 0, (len - curlen + 1)); /* also set trailing \0 byte */
	// 更新属性
	totlen = sh->len + sh->free;
	sh->len = len;
	sh->free = totlen - sh->len;
	// 返回新的 sds
	return s;
}

sdscatlen sdscat sdscatsds 追加字符串

sdscatlen函数类似于Java中字符从apped()追加操作。把 长度为len的const void类型的 *t串，追加到sds s的末尾。首先使用sdsMakeRoomFor扩充空间，再使用memcpy函数进行字符串的拷贝，最后修改新串的len与free。sdscat 调用sdscatlen函数，会使用strlen库函数计算字符串的值，传递给
sdscatlen的size_t len。sdscatsds函数是将一个sds追加到另一个sds之后。

sds sdscatlen(sds s, const void *t, size_t len) {

	struct sdshdr *sh;

	// 原有字符串长度
	size_t curlen = sdslen(s);

	// 扩展 sds 空间
	// T = O(N)
	s = sdsMakeRoomFor(s, len);

	// 内存不足？直接返回
	if (s == NULL) { return NULL; }

	// 复制 t 中的内容到字符串后部
	// T = O(N)
	sh = (void *) (s - (sizeof(struct sdshdr)));
	memcpy(s + curlen, t, len);

	// 更新属性
	sh->len = curlen + len;
	sh->free = sh->free - len;

	// 添加新结尾符号
	s[curlen + len] = '\0';

	// 返回新 sds
	return s;
}

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

sdscpylen sdscpylen 复制指定长度的字符串到sds中

sdscpylen函数将字符串 t 的前 len 个字符复制到 sds s 当中，并在字符串的最后添加终结符。如果如果 sds 的长度少于 len 个字符，那么调用sdsMakeRoomFor函数进行扩容。
sdscpy函数是封装函数，通过计算字符串的长度，调用sdscpylen函数经行复制字符串。

sds sdscpylen(sds s, const char *t, size_t len) {

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

	// sds 现有 buf 的长度
	size_t totlen = sh->free + sh->len;

	// 如果 s 的 buf 长度不满足 len ，那么扩展它
	if (totlen < len) {
		// T = O(N)
		s = sdsMakeRoomFor(s, len - sh->len);
		if (s == NULL) { return NULL; }
		sh = (void *) (s - (sizeof(struct sdshdr)));
		totlen = sh->free + sh->len;
	}

	// 复制内容
	// T = O(N)
	memcpy(s, t, len);

	// 添加终结符号
	s[len] = '\0';

	// 更新属性
	sh->len = len;
	sh->free = totlen - len;

	// 返回新的 sds
	return s;
}

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

工具函数

int sdsll2str(char *s, long long value) ：数字 -> 字符串转换
int sdsull2str(char *s, unsigned long long v) ：无符号数字 -> 字符串转换
sds sdsfromlonglong(long long value)：longlong->sds
sds sdscatvprintf(sds s, const char *fmt, va_list ap)：格式化打印sds
sds sdscatprintf(sds s, const char *fmt, …) ：打印任意数量个字符串，并将这些字符串追加到给定 sds 的末尾
sds sdscatfmt(sds s, char const *fmt, …)：格式化字符串
sds sdstrim(sds s, const char *cset)：清除字符串中包含cset的字符
void sdsrange(sds s, int start, int end)：按照索引开始start，结束end截取字符串
void sdstolower(sds s)：sds全部转换小写
void sdstoupper(sds s) ：sds全部转换大写
int sdscmp(const sds s1, const sds s2)：比较字符串的大小，相等返回 0 ，s1 较大返回正数， s2 较大返回负数
sds *sdssplitlen(const char *s, int len, const char *sep, int seplen, int *count)：slipt拆分字符串，使用分隔符 sep 对 s 进行分割，返回一个 sds 字符串的数组，*count 为返回数组元素的数量
void sdsfreesplitres(sds *tokens, int count) ：释放字符串数组的内存，回收空间
sds sdscatrepr(sds s, const char p, size_t len)：把p变为带有“”号的字符串，追加到sds的末尾
int is_hex_digit(char c) ：判断是否是十六进制数，如果是返回正数
hex_digit_to_int(char c) ：十六进制转十进制
sds sdsmapchars(sds s, const char *from, const char *to, size_t setlen) ：在sds中，把from中出现了的字符，替换成字符to
sds sdsjoin(char **argv, int argc, char *sep) ：指定分隔符链接sds