Redis教程

Redis 源码分析(二)动态字符串-sds

本文主要是介绍Redis 源码分析(二)动态字符串-sds,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

动态字符串-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内存图

/*
 * 返回 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

这篇关于Redis 源码分析(二)动态字符串-sds的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!