Redis5.0源码 - 数据结构 - 简单动态字符串

 

在Redis中,没有直接使用C语言传统的字符串表示(以’\0’结尾的字符数组), 而是自己构建了一种名为简单动态字符串(simple dynamic string,SDS)的抽象类型,并将SDS用作Redis的默认字符串表示。

设计

  • 相关文件:sds.hsds.c

首先,sds被定义char*,sds的设计者希望sds不仅作为一个动态字符串使用,同时sds也应该兼容C类型的字符串操作

typedef char *sds;

某种类型sds header(不同类型的SDS仅最大存储字节数有区别)如下定义:

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[];
};

设计SDS Header时加入:

  • len:用于表示当前SDS已经使用空间的字节数。len的加入,可以使获取长度函数所需的时间复杂度降低到常数级复杂度O(1)。另外,还能保证二进制安全(binary-safe),不会像C语言字符串一样,因为字符串中间出现的’\0’而提前结束,能保证读取指定len长度的数据。SDS可以拿来存储任意类型的二进制。

  • alloc:用于表示当前SDS对象申请了多少的空间用于存储字符串(不包含头和’\0’)。例如buf申请了(20+1位’\0’)字节的空间,则alloc为20。

  • flags:低3位用于表示当前SDS的类型,高5位保留。

  • buf[]灵活数组类型是C99引入的语言特性。即在struct数据类型的最后一个数据成员,可以为一个未指明长度的数组类型。

注1:例如sds s; ... s默认指向buf[]成员的位置

注2__attribute__ ((__packed__))的作用就是告诉编译器取消结构在编译过程中的优化对齐,按照实际占用字节数进行对齐(默认会进行字节对齐,并填充空字节)。

注3:另外,SDS会在保存的数据末尾自动设置’\0’空字符,这样在做某些字符串比较时,可以直接使用C语言中的字符串比较函数。

常用API

函数 作用
sdsnew 创建一个包含C字符串init的SDS,通过调用sdsnewlen(init, initlen)实现,创建的SDS的alloc和len均为initlen
sdsempty 创建一个不包含的SDS,通过调用sdsnewlen("", 0)实现
sdsdup 创建一个给定sds的副本(copy操作),通过调用sdsnewlen(s, sdslen(s))实现
sdsfree 释放指定的SDS(释放所占用的内存空间)
sdslen 返回SDS的已使用空间字节数,即len
sdsavaid 返回SDS的未使用空间字节数,即alloc-len
sdsgrowzero 用空字符将SDS扩展到给定长度
sdscat 追加C字符串,通过调用sdscatlen实现,导致剩余空间不够用时,会使用sdsMakeRoomFor增加空间,当追加字符串后所需的总的空间大小小于1MB时,会申请2倍的总空间大小的字节数;否则额外申请1MB空间。
sdscatsds 追加SDS字符串,通过调用sdscatlen实现,同上。
sdsclear 用于清空字符串,但不会释放申请的内存空间,这种惰性空间释放可以减少了内存重分配操作的次数。
sdscpy 将指定C字符串复制到SDS中,覆盖原有字符串
sdscatprintf 追加fmt字符串
sdstrim 接受一个SDS和一个C字符串,在SDS字符串左右两端分别去除在C字符串中出现过的字符
sdscmp 比较两个SDS字符串是否相同
sdsrange 保留SDS指定区间内的数据
sdsmapchars 根据所给符from和to的映射关系,替换SDS字符串中的对应字符
sdsjoin 用指定分隔符插入C字符串的字符之间,构成一个SDS
sdsjoinsds 用指定分隔符插入SDS字符串的字符之间,构成一个新的SDS

懵逼点

C99中的灵活数组类型不占用空间

首先是这个宏,这个宏的作用是获取指定类型T的SDS头的指针

#define SDS_HDR(T,s) ((struct sdshdr##T *)((s)-(sizeof(struct sdshdr##T))))

使用该宏时,T传入SDS的类型,s传入sds字符串(成员buf[]的地址)。拿上面的sdshdr8为例,((s)-(sizeof(struct sdshdr8)))为什么能表示sds头的地址?

首先,上面讲到,buf[]是个灵活数组类型,它在这里只是起到一个标记的作用,表示在flags字段后面就是一个字符数组,或者说,它指明了紧跟在flags字段后面的这个字符数组在结构体中的偏移位置。而程序在为header分配的内存的时候,它并不占用内存空间。所以sizeof(struct sdshdr8)为3。

attribute((format(printf, 2, 3)))

在声明sdscatprintf函数时,给这个函数加上了__attribute__ format属性。

#ifdef __GNUC__
sds sdscatprintf(sds s, const char *fmt, ...)
	__attribute__((format(printf, 2, 3)));
#else
sds sdscatprintf(sds s, const char *fmt, ...);
#endif

__attribute__ format属性可以给被声明的函数加上类似printf或者scanf的特征,它可以使编译器检查函数声明和函数实际调用参数之间的格式化字符串是否匹配。format属性告诉编译器,按照printf, scanf等标准C函数参数格式规则对该函数的参数进行检查。

format的语法格式为:

format (archetype, string-index, first-to-check)
  • archetype 指定是哪种风格;
  • string-index 指定传入函数的第几个参数是格式化字符串;
  • first-to-check 指定从函数的第几个参数开始按上述规则进行检查。

敲重点!!!:可以用在自己封装调试信息的接口上。