抑郁症健康 > redis源码注释二：简单字符串sds.c sds.h

redis源码注释二：简单字符串sds.c sds.h

时间：2018-08-14 17:55:53

相关推荐

1. sds(Simple Dynamic String)简介

sds(Simple Dynamic String)简单动态字符串。

redis没有直接用char*，而是使用sds替代char*。为什么不用char*呢，只要有以下考虑：

因为char* 类型的功能单一，抽象层次低，并且不能高效地支持一些Redis 常用的操作（比如追加操作和长度计算操作），所以在Redis 程序内部，绝大部分情况下都会使用sds 而不是char* 来表示字符串。——《redis设计与实现》

那么redis中的sds是如何对char*改善的呢？如何在O(1)的时间内获得字符串长度，如何方便地进行追加操作？

从结构上就能简单地猜到：

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

redis定义了sdshdr8、sdshdr16、sdshdr32、sdshdr64，不同的结构体区别在于表示len和alloc的数据类型。

像sdshdr16的len类型为uint16_t，sdshdr8的为uint8_t。

改善主要在len和alloc上。

len表示当前字符串的长度，就是buf中字符串的长度，要获取字符串的长度只需要返回len就可以啦。时间复杂度O(1)。

alloc表示总共分配的长度，等于已经用的加上空闲的。如果要获取还有多少空闲的空间，使用alloc减去len就可以了。具体分配过程下面再讲。

flags用来表示是sdshdr8orsdshdr16orsdshdr32orsdshdr64。只用了低3比特。

综上，redis通过一层包装，将char*变为简单动态字符串。

这里有几个技巧性问题：

_ _attribute_ _ ((_ _packed_ _))是啥？

这个的作用是防止编译器自动对齐，编译器可能在结构体的变量支架插入空位置，已达到对齐的目的，写上__attribute_ ((packed))就能防止编译器自动对齐了。可参考：为什么要用 “attribute((packed)) ” 定义结构体sizeof(sdshdr8)是多少？

要回答这个问题，重点搞清楚char buf[]算不算到结构体的size中，答案是不算，所以sizeof(sdshdr8)结果为3.

为啥char buf[]不算到结构体的size中呢？因为它是个柔性数组，就是不知道大小的数组。详见：C语言柔性数组讲解

2. 头文件

头文件里有些比较骚气的技巧。。。

2.1 结构体定义

首先当然是结构体定义啦。

typedef char *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[];};struct __attribute__ ((__packed__)) sdshdr8 {//...省略};struct __attribute__ ((__packed__)) sdshdr32 {//...省略};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[];};

关于结构体中参数的含义，第一节讲了，不再赘述。

2.2 骚气的宏定义

#define SDS_TYPE_8 1//代表sdshdr8#define SDS_TYPE_16 2//代表sdshdr16#define SDS_TYPE_32 3//代表sdshdr32#define SDS_TYPE_64 4//代表sdshdr64#define SDS_TYPE_MASK 7//掩码，保留低3位#define SDS_TYPE_BITS 3

flags的取值就是上面这几位。通过flags和SDS_TYPE_MASK就能判断出这个结构体是sdshdr8orsdshdr16orsdshdr32orsdshdr64。如：

switch(flags&SDS_TYPE_MASK) {case SDS_TYPE_5://...;case SDS_TYPE_8://...;case SDS_TYPE_16://...;case SDS_TYPE_32://...;case SDS_TYPE_64://...;}

下面这个宏定义比较骚气，看愣了：

#define SDS_HDR_VAR(T,s) struct sdshdr##T *sh = (void*)((s)-(sizeof(struct sdshdr##T)));//通过buf获得指向结构体头部的指针#define SDS_HDR(T,s) ((struct sdshdr##T *)((s)-(sizeof(struct sdshdr##T)))) //也是返回指向结构体头部的指针

sdshdr##T是什么东东，这就要说道##在宏定义中的含义了：将##左右两边的标签拼接在一起。也就是说sdshdr##T到最后变为了sdshdrT，T一般就是8 16 32 64，所以sdshdrT就是sdshdr8orsdshdr16orsdshdr32orsdshdr64，6666. ##参考宏定义中的"#"与“##”

那SDS_HDR_VAR(T,s)干了什么事呢？通过结构体中的buf得到指向结构体头部的指针，实现方式就是指针直接减去结构体的长度。从buf跳到头部。有点malloc/free的味道…

SDS_HDR(T,s)和SDS_HDR_VAR(T,s)类似。

2.3 几个inline函数

2.3.1 sdslen获取字符串长度

用到了上面说的骚气的宏定义SDS_HDR。

static inline size_t sdslen(const sds s) {//获取字符串的长度unsigned char flags = s[-1];//先通过buf获得falgs,即结构体类型switch(flags&SDS_TYPE_MASK) {case SDS_TYPE_5:return SDS_TYPE_5_LEN(flags);case SDS_TYPE_8:return SDS_HDR(8,s)->len;//SDS_HDR(8,s)获得指向结构体的指针，然后得到lencase SDS_TYPE_16:return SDS_HDR(16,s)->len;//与上面的一样case SDS_TYPE_32:return SDS_HDR(32,s)->len;case SDS_TYPE_64:return SDS_HDR(64,s)->len;}return 0;}

2.3.2 sdsavail当前可用长度

static inline size_t sdsavail(const sds s) {//获取当前剩余的长度unsigned char flags = s[-1];//先得到结构体类型switch(flags&SDS_TYPE_MASK) {case SDS_TYPE_5: {return 0;}case SDS_TYPE_8: {SDS_HDR_VAR(8,s);return sh->alloc - sh->len;//剩余的长度等于总共分配的减去已经使用的}case SDS_TYPE_16: {SDS_HDR_VAR(16,s);return sh->alloc - sh->len;//同上}case SDS_TYPE_32: {SDS_HDR_VAR(32,s);return sh->alloc - sh->len;}case SDS_TYPE_64: {SDS_HDR_VAR(64,s);return sh->alloc - sh->len;}}return 0;}

2.3.3 sdssetlen设置字符串长度

static inline void sdssetlen(sds s, size_t newlen) {//设置字符串长度为newlenunsigned char flags = s[-1];switch(flags&SDS_TYPE_MASK) {case SDS_TYPE_5://...break;case SDS_TYPE_8:SDS_HDR(8,s)->len = newlen;break;case SDS_TYPE_16://...case SDS_TYPE_32://...case SDS_TYPE_64://...}}

2.3.4 获取总共分配的长度sdsalloc

/* sdsalloc() = sdsavail() + sdslen() */static inline size_t sdsalloc(const sds s) {//获取总共分配的长度unsigned char flags = s[-1];switch(flags&SDS_TYPE_MASK) {case SDS_TYPE_5:return SDS_TYPE_5_LEN(flags);case SDS_TYPE_8:return SDS_HDR(8,s)->alloc;case SDS_TYPE_16:return SDS_HDR(16,s)->alloc;case SDS_TYPE_32:return SDS_HDR(32,s)->alloc;case SDS_TYPE_64:return SDS_HDR(64,s)->alloc;}return 0;}

。。。

剩下的几个比较简单，不写了。

3. 源文件中的函数

太枯燥了。。。简单的不介绍了。。。

3.1 根据字符串长度返回适当的sds的type

static inline char sdsReqType(size_t string_size) {//根据字符串长度返回适当的sds的typeif (string_size < 1<<5)return SDS_TYPE_5;if (string_size < 1<<8)return SDS_TYPE_8;//长度小于128返回SDS_TYPE_8if (string_size < 1<<16)return SDS_TYPE_16;//长度小于2^SDS_TYPE_16#if (LONG_MAX == LLONG_MAX)if (string_size < 1ll<<32)return SDS_TYPE_32;//长度小于2^32返回SDS_TYPE_32return SDS_TYPE_64;//长度大于2^32返回SDS_TYPE_64#elsereturn SDS_TYPE_32;#endif}

3.2 创建字符串sdsnewlen

函数原形：

sds sdsnewlen(const void *init, size_t initlen)

根据传入的const void *init和size_t initlen创建一个字符串。

size_t initlen表示创建的字符串的长度；

const void *init指向字符串内容。

举例：

mystring = sdsnewlen("abc",3);

如果init为空，字符串初始化为0，字符串总以\0结尾。

函数首先根据size_t initlen选择一个合适的结构体，因为sdshdr8中的len最大为127，如果申请的字符串长度大于127，只能使用len比127大的结构体。

然后malloc一段空间，设置结构体的type，len，alloc参数，最后将init指向的字符串拷贝到malloc出的空间。

sds sdsnewlen(const void *init, size_t initlen) {void *sh;sds s;char type = sdsReqType(initlen);//根据初始的长度选择一个合适的结构体类型,不然len可能表示不了那么大范围/* Empty strings are usually created in order to append. Use type 8* since type 5 is not good at this. */if (type == SDS_TYPE_5 && initlen == 0) type = SDS_TYPE_8;int hdrlen = sdsHdrSize(type);//获取结构体的长度unsigned char *fp; /* flags pointer. */sh = s_malloc(hdrlen+initlen+1);//最终申请的长度为结构体长度加上字符串长度if (init==SDS_NOINIT)init = NULL;else if (!init)memset(sh, 0, hdrlen+initlen+1);if (sh == NULL) return NULL;s = (char*)sh+hdrlen;//结构体中的buf, sh指向结构体头部，hdrlen为结构体的长度fp = ((unsigned char*)s)-1; //buf-1就是type了，也就是结构体中的flagsswitch(type) {case SDS_TYPE_5: {*fp = type | (initlen << SDS_TYPE_BITS);break;}case SDS_TYPE_8: {SDS_HDR_VAR(8,s);//获取指向结构体的指针sh->len = initlen;//设置字符串的长度sh->alloc = initlen;//设置分配的长度*fp = type;//flags设置为对应的类型break;}case SDS_TYPE_16: {SDS_HDR_VAR(16,s);sh->len = initlen;sh->alloc = initlen;*fp = type;break;}case SDS_TYPE_32: {SDS_HDR_VAR(32,s);sh->len = initlen;sh->alloc = initlen;*fp = type;break;}case SDS_TYPE_64: {SDS_HDR_VAR(64,s);sh->len = initlen;sh->alloc = initlen;*fp = type;break;}}if (initlen && init)memcpy(s, init, initlen);//前面只是分配了空间，这里才将字符串拷贝进分配的空间s[initlen] = '\0';//设置尾部return s;}

3.3 和sdsnewlen相关的操作

3.3.1 创建空串sdsempty

sds sdsempty(void) {return sdsnewlen("",0);//创建一个空串}

3.3.2 根据C string创建一个串sdsnew

/* Create a new sds string starting from a null terminated C string. */sds sdsnew(const char *init) {size_t initlen = (init == NULL) ? 0 : strlen(init);return sdsnewlen(init, initlen);//创建一个和init内容一样的字符串}

3.3.3 复制串sdsdup

sds sdsdup(const sds s) {return sdsnewlen(s, sdslen(s));//复制字符串s}

3.3.4 释放串sdsfree

void sdsfree(sds s) {if (s == NULL) return;s_free((char*)s-sdsHdrSize(s[-1]));//释放字符串}

s[-1]获取flags(结构体类型)

sdsHdrSize(s[-1])获取结构体长度

(char*)s-sdsHdrSize(s[-1])就获得指向结构体头部的指针。

3.3.5 更新字符串长度sdsupdatelen

void sdsupdatelen(sds s) {//更新字符串的长度，中途字符串被改变了要更新一下字符串长度，否则会出错size_t reallen = strlen(s);sdssetlen(s, reallen);}

举例：

s = sdsnew("foobar");s[2] = '\0';sdsupdatelen(s);printf("%d\n", sdslen(s));

不更新长度（调用sdsupdatelen）的话，输出的len就是6，但是这是错误的结果，所以更改了字符串要更新字符串的长度。

3.3.6 释放字符串sdsclear

要注意的是，sdsclear只是将字符串长度设置为0，串设置为空，但是为其分配的空间还在，没有释放，下次分配的时候就不用再malloc了。

void sdsclear(sds s) {//清空字符串，但是不将空间释放sdssetlen(s, 0);//设置长度为0s[0] = '\0';//字符串设置为空}

3.4 字符串扩容sdsMakeRoomFor–重要

这个函数有点意思，有点vector扩容的味道。

函数原型：

sds sdsMakeRoomFor(sds s, size_t addlen)

使s的空闲区长度达到addlen。

如果原来空闲区的长度足够addlen，直接返回；

如果原来空闲区的长度不够，那就要再分配了，再分配就会遇到各种问题，比如，原来的长度120，空闲区7，现在要求空闲区为10，整个alloc就是127+10=137，大于uint8_t表示范围了，此时就要更换结构体的类型。

sds sdsMakeRoomFor(sds s, size_t addlen) {void *sh, *newsh;size_t avail = sdsavail(s);//获取原来空闲区的大小size_t len, newlen;char type, oldtype = s[-1] & SDS_TYPE_MASK;//原来的结构体类型int hdrlen;/* Return ASAP if there is enough space left. */if (avail >= addlen) return s;//原来空闲区长度大于想要的，直接返回就行了。不用再分配len = sdslen(s);//获取原来的lensh = (char*)s-sdsHdrSize(oldtype);//原来指向结构体头部的指针newlen = (len+addlen);//新的长度if (newlen < SDS_MAX_PREALLOC)//新长度小于1Mnewlen *= 2;//双倍elsenewlen += SDS_MAX_PREALLOC;//否则直接加1M,1M还是挺大的type = sdsReqType(newlen);//根据扩张后的长度选择适当的结构体类型/* Don't use type 5: the user is appending to the string and type 5 is* not able to remember empty space, so sdsMakeRoomFor() must be called* at every appending operation. */if (type == SDS_TYPE_5) type = SDS_TYPE_8;hdrlen = sdsHdrSize(type);if (oldtype==type) {//新结构体与旧结构体相同，直接在原来的空间上realloc就行newsh = s_realloc(sh, hdrlen+newlen+1);if (newsh == NULL) return NULL;s = (char*)newsh+hdrlen;} else {/* Since the header size changes, need to move the string forward,* and can't use realloc */newsh = s_malloc(hdrlen+newlen+1);//由于结构体大小不一样，只能重新分配，不然根据s找不到flags/len/alloc参数if (newsh == NULL) return NULL;memcpy((char*)newsh+hdrlen, s, len+1);//将原来的字符串拷贝到新malloc的内存s_free(sh);//释放原来的串s = (char*)newsh+hdrlen;//新的bufs[-1] = type;//新的typesdssetlen(s, len);//新的len}sdssetalloc(s, newlen);//新的allocreturn s;}

3.5 字符串缩容sdsRemoveFreeSpace

字符串缩容会遇到和字符串扩容相同的问题，不同的是，缩容不用考虑缩成多少的问题，缩得只剩下len就可以了，扩容得考虑扩之后的长度是double一下还是+1M.

sds sdsRemoveFreeSpace(sds s) {void *sh, *newsh;char type, oldtype = s[-1] & SDS_TYPE_MASK;//获得原来的结构体类型int hdrlen, oldhdrlen = sdsHdrSize(oldtype);//原来的结构体头部长度size_t len = sdslen(s);size_t avail = sdsavail(s);//空闲区大小sh = (char*)s-oldhdrlen;//指向结构体头部的指针/* Return ASAP if there is no space left. */if (avail == 0) return s;//原来空闲区大小已经为0了，没必要缩容/* Check what would be the minimum SDS header that is just good enough to* fit this string. */type = sdsReqType(len);//选择合适的结构体，因为缩容之后alloc可能只需要更小的数据类型就能表示hdrlen = sdsHdrSize(type);//新的结构体头部大小hdr(header)/* If the type is the same, or at least a large enough type is still* required, we just realloc(), letting the allocator to do the copy* only if really needed. Otherwise if the change is huge, we manually* reallocate the string to use the different header type. */if (oldtype==type || type > SDS_TYPE_8) {newsh = s_realloc(sh, oldhdrlen+len+1);//新旧结构体相同，直接在原来的基础上realloc即可if (newsh == NULL) return NULL;s = (char*)newsh+oldhdrlen;} else {newsh = s_malloc(hdrlen+len+1); //结构体不同只能新开辟空间if (newsh == NULL) return NULL;memcpy((char*)newsh+hdrlen, s, len+1);//将原来的字符串拷贝过去s_free(sh);//释放原来的字符串s = (char*)newsh+hdrlen;//设置新的bufs[-1] = type;//新的typesdssetlen(s, len);//新的len}sdssetalloc(s, len);return s;}

3.6 移动字符串结尾sdsIncrLen

将结尾的\0前移或后退incr个字节，incr可正可负。

使用场景：

oldlen = sdslen(s);s = sdsMakeRoomFor(s, BUFFER_SIZE);nread = read(fd, s+oldlen, BUFFER_SIZE);... check for nread <= 0 and handle it ...sdsIncrLen(s, nread);//需要设置新的结尾

void sdsIncrLen(sds s, ssize_t incr) {//将结尾的\0前移或后退incr个字节unsigned char flags = s[-1];size_t len;switch(flags&SDS_TYPE_MASK) {case SDS_TYPE_5: {//...}case SDS_TYPE_8: {SDS_HDR_VAR(8,s);assert((incr >= 0 && sh->alloc-sh->len >= incr) || (incr < 0 && sh->len >= (unsigned int)(-incr)));len = (sh->len += incr);//得到新的位置，新位置为原len前进或后退incr个位置之后的break;}case SDS_TYPE_16: {//同上...}case SDS_TYPE_32: {//...}case SDS_TYPE_64: {//...}default: len = 0; /* Just to avoid compilation warnings. */}s[len] = '\0';//设置为结束符}

3.7 字符串拼接sdscatlen、sdscat

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

在字符串s后面拼接长度为len的字符串t.

sds sdscatlen(sds s, const void *t, size_t len) {//在s后面拼接长度为len的字符串tsize_t curlen = sdslen(s);s = sdsMakeRoomFor(s,len);//先保证空闲区的长度够lenif (s == NULL) return NULL;memcpy(s+curlen, t, len);//将t拷贝到s+curlensdssetlen(s, curlen+len);//设置新的s的长度s[curlen+len] = '\0'; //设置结尾return s;}

sdscatlen相关的函数：

sds sdscat(sds s, const char *t) {return sdscatlen(s, t, strlen(t));//在s后面拼接字符串t}

sds sdscatsds(sds s, const sds t) {return sdscatlen(s, t, sdslen(t));//在s后面拼接一个sds}

3.8 字符串拷贝

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

使用长度为len的字符串t覆盖字符串s。

sds sdscpylen(sds s, const char *t, size_t len) {//使用字符串t覆盖字符串sif (sdsalloc(s) < len) {s = sdsMakeRoomFor(s,len-sdslen(s));//保证被覆盖的s有足够的空间容纳tif (s == NULL) return NULL;}memcpy(s, t, len);//将t拷贝到ss[len] = '\0';//设置尾部sdssetlen(s, len);//设置长度return s;}

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

3.9 整数转字符串sdsll2str、sdsull2str

入门级：

int sdsll2str(char *s, long long value) {char *p, aux;unsigned long long v;size_t l;/* Generate the string representation, this method produces* an reversed string. */v = (value < 0) ? -value : value;//负数变为正数，正数还是正数p = s;do {*p++ = '0'+(v%10);//不断取最低位v /= 10;} while(v);if (value < 0) *p++ = '-';//负数加上负号/* Compute length and add null term. */l = p-s;//整数的长度*p = '\0';//字符串结尾/* Reverse the string. */p--;while(s < p) {//翻转字符串aux = *s;*s = *p;*p = aux;s++;p--;}return l;}

sdsull2str和sdsll2str类似，不再赘述。

sds sdsfromlonglong(long long value) {char buf[SDS_LLSTR_SIZE];int len = sdsll2str(buf,value);//将整数变为字符串放在buf中return sdsnewlen(buf,len);//通过buf构造sds}

3.10 trim

去掉s头部尾部在集合cset中的字符。

举例：

s = sdsnew("AA...AA.a.aa.aHelloWorld:::");s = sdstrim(s,"Aa. :");printf("%s\n", s);//Output will be just "HelloWorld".

sds sdstrim(sds s, const char *cset) {//去掉s头部尾部在集合cset中的字符char *start, *end, *sp, *ep;size_t len;sp = start = s;ep = end = s+sdslen(s)-1;while(sp <= end && strchr(cset, *sp)) sp++;//从前往后，字符在cset中就往后继续找while(ep > sp && strchr(cset, *ep)) ep--;//从后往前，字符在cset中就继续往前找len = (sp > ep) ? 0 : ((ep-sp)+1); //sp>ep说明整个字符串中的字符都在cset中，去完变成空串if (s != sp) memmove(s, sp, len);//将sp开始的搬到头部s[len] = '\0';sdssetlen(s,len);//设置长度return s;}

3.11 字符串比较sdscmp

返回值：

0：相同；

1：s1>s2;

-1：s1<s2

int sdscmp(const sds s1, const sds s2) {size_t l1, l2, minlen;int cmp;l1 = sdslen(s1);l2 = sdslen(s2);minlen = (l1 < l2) ? l1 : l2;cmp = memcmp(s1,s2,minlen);//先比较两者长度相同的部分if (cmp == 0) return l1>l2? 1: (l1<l2? -1: 0);//如果长度相同的部分也相同，则比较两者长度，如果长度也相同则返回0return cmp;//否则返回比较结果}

3.12 join

sds sdsjoin(char **argv, int argc, char *sep)

argv是一个字符串数组。argc是数组中字符串的数量。

seq是每两个字符串之间的分隔符，可以是单个字符也可以是一个串。

sds sdsjoin(char **argv, int argc, char *sep) {sds join = sdsempty();int j;//将字符串数组中的字符串串联起来，以seq为分割for (j = 0; j < argc; j++) {join = sdscat(join, argv[j]);if (j != argc-1) join = sdscat(join,sep);//除了最后一个argv中的字符串，每个后面都加上sep}return join;}