Redis源码阅读笔记-动态字符串(SDS)结构

原创
2018/09/05 22:44
阅读数 220

Redis中采用自定义的结构来保存字符串,在sds.h中:

/* Note: sdshdr5 is never used, we just access the flags byte directly.
 * However is here to document the layout of type 5 SDS strings. */
struct __attribute__ ((__packed__)) sdshdr5 {
    unsigned char flags; /* 3 lsb of type, and 5 msb of string length */
    char buf[];
};
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__)) sdshdr16 {
    uint16_t len; /* used */
    uint16_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr32 {
    uint32_t len; /* used */
    uint32_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};
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[];
};

SDS由4部分组成:

  • len: SDS字符串已经使用的空间(不包含C中字符串的结束符的长度1)。
  • alloc: 申请的空间大小,减去len就是未使用的空间,初始时和len一直。
  • flags: 使用低三位表示类型,细分SDS的分类。方便根据字符串的长度不同选择不用的SDS结构体,节省一部分空间。
  • buf: 用了C的不定长字符串。

PS: __attribute__ ((__packed__))关键字的解释,在C/C++中,建立一个结构体时,会进行字节对齐操作,使得结构体的大小比其变量占用的字节要多一些,当结构体上声明中加上__attribute__ ((__packed__)),则表示取消字节对齐,按照紧凑排列的方式。

// sds.h

typedef char *sds;

......
// 用法是 SDS_HDR(8, s),T传入的是 sdshdr 的数字,s是buf字符串的地址
// SDS_HDR_VAR(T,s) 的作用是从 传入的buf(参数s)的字符串地址 获得一个指向结构体的指针 sh
#define SDS_HDR_VAR(T,s) struct sdshdr##T *sh = (void*)((s)-(sizeof(struct sdshdr##T)));
// SDS_HDR(T, s),的作用是通过T,和传入的buf(参数s)的字符串地址,找到结构体的首地址
#define SDS_HDR(T,s) ((struct sdshdr##T *)((s)-(sizeof(struct sdshdr##T))))

// 函数的作用是通过传入的sds结构体的buf字符串地址,获得字符串的长度
static inline size_t sdslen(const sds s) {
    // 传入的s是结构体 sdshdr 中 buf 的字符串地址,所以s[-1] 指向 flags
    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)->len;
        case 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;
}

部分函数代码解析

  • sds sdsnewlen(const void *init, size_t initlen) 创建一个包含给定C字符串的SDS:

    	// sds.c
    
    	static inline char sdsReqType(size_t string_size) {
    	    if (string_size < 1<<5)
    	        // 字符串长度少于32 
    	        return SDS_TYPE_5;
    	    if (string_size < 1<<8)
    	        // 字符串长度少于256
    	        return SDS_TYPE_8;
    	    if (string_size < 1<<16)
    	        // 字符串长度少于65536
    	        return SDS_TYPE_16;
    	#if (LONG_MAX == LLONG_MAX)
    	    if (string_size < 1ll<<32)
    	        // 字符串长度少于2^32
    	        return SDS_TYPE_32;
    	#endif
    	    return SDS_TYPE_64;
    	}
    
    	/* Create a new sds string with the content specified by the 'init' pointer
    	 * and 'initlen'.
    	 * If NULL is used for 'init' the string is initialized with zero bytes.
    	 *
    	 * The string is always null-termined (all the sds strings are, always) so
    	 * even if you create an sds string with:
    	 *
    	 * mystring = sdsnewlen("abc",3);
    	 *
    	 * You can print the string with printf() as there is an implicit \0 at the
    	 * end of the string. However the string is binary safe and can contain
    	 * \0 characters in the middle, as the length is stored in the sds header. 	*/
    	sds sdsnewlen(const void *init, size_t initlen) {
    	    // *init 是字符串的首地址,initlen是字符串的长度(不包含字符串结束符)
    
    	    // 指向sds结构体的指针
    	    void *sh;
    	    sds s;
    
    	    // 根据字符串的长度,来指定sds的结构体
    	    // type 是表示sds的类型,具体数值查看sds.h
    	    char type = sdsReqType(initlen);
    
    	    // SDS_TYPE_5 不再使用,最小单位是SDS_TYPE_8
    	    /* 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. */
    
    	    // 申请结构体所需的内存,hdrlen是结构体的大小,initlen是字符串的长度,1是字符串结束符的长度
    	    sh = s_malloc(hdrlen+initlen+1);
    	    if (!init)
    	        memset(sh, 0, hdrlen+initlen+1);
    	    if (sh == NULL) return NULL;
    
    	    // s 指向了结构体中buf的首地址,为下面将字符串内容复制到buf中做准备
    	    s = (char*)sh+hdrlen;
    	    // fp 指向了结构体中flags的地址
    	    fp = ((unsigned char*)s)-1;
    	    switch(type) {
    
    	        // 下面是给sds结构体的len, alloc, fp赋值
    
    	        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;
    	            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;
    	        }
    	    }
    
    	    // 将 init 的字符串拷贝到结构体的 buf 中
    	    if (initlen && init)
    	        memcpy(s, init, initlen);
    
    	    // 给buf的末尾加上结束符
    	    s[initlen] = '\0';
    	    return s;
    	}
    
  • void sdsfree(sds s)释放给定的sds内存:

    	// sds.c
    
    	/* Free an sds string. No operation is performed if 's' is NULL. */
    	void sdsfree(sds s) {
    		 // 传入的s,是指向sds结构体中buf字符串的首地址的指针
    
    	    if (s == NULL) return;
    	    // s_free是zmalloc.c中的zfree()函数,释放内存
    	    // s[-1] 是获得指向sds结构体中flags的地址
    	    // sdsHdrSize(s[-1]) 则是获得对应的sds结构体的size
    	    // 所以(char*)s-sdsHdrSize(s[-1])则是获得指向sds结构体的地址
    	    s_free((char*)s-sdsHdrSize(s[-1]));
    	}
    
  • sds sdscat(sds s, const char *t)为sds字符串后追加字符串,可以看出,如果这个函数会分配一个额外的内存空间来作为预留使用:

    	// sds.c
    
    	/* Append the specified null termianted C string to the sds string 's'.
    	 *
    	 * After the call, the passed sds string is no longer valid and all the
    	 * references must be substituted with the new pointer returned by the call. */
    	sds sdscat(sds s, const char *t) {
        //通过sdscatlen拼接sds字符串, 将C字符串t拼接到sds字符串s上
    	    return sdscatlen(s, t, strlen(t));
    	}
    
    	/* Append the specified binary-safe string pointed by 't' of 'len' bytes to the
    	 * end of the specified sds string 's'.
    	 *
    	 * After the call, the passed sds string is no longer valid and all the
    	 * references must be substituted with the new pointer returned by the call. */
    	sds sdscatlen(sds s, const void *t, size_t len) {
    
       // 通过sdslen()获取sds字符串的长度curlen
    	    size_t curlen = sdslen(s);
    
    	    s = sdsMakeRoomFor(s,len);
    	    if (s == NULL) return NULL;
    	    // s为sds结构体中buf的地址指针,
    	    // s+curlen为当前sds中字符串的末尾地址
    	    // memcpy(s+curlen, t, len) 则是将字符串写入buf后
    	    memcpy(s+curlen, t, len);
    	    // 将sds的长度(len)设置为curlen+len
    	    sdssetlen(s, curlen+len);
    	    // 在字符串末尾添加结束字符
    	    s[curlen+len] = '\0';
    	    return s;
    	}
    
    	/* Enlarge the free space at the end of the sds string so that the caller
    	 * is sure that after calling this function can overwrite up to addlen
    	 * bytes after the end of the string, plus one more byte for nul term.
    	 *
    	 * Note: this does not change the *length* of the sds string as returned
    	 * by sdslen(), but only the free buffer space we have. */
    	// 给sds的字符空间增大addlen的大小
    	sds sdsMakeRoomFor(sds s, size_t addlen) {
    	    void *sh, *newsh;
    
    	    // sdsavail()是计算sds有多少空闲空间,所以avail是该sds的空闲空间
    	    size_t avail = sdsavail(s);
    	    size_t len, newlen;
    	    // s[-1]是指向该sds的flags,s[-1] & SDS_TYPE_MASK 则获得sds的结构体类型
    	    char type, oldtype = s[-1] & SDS_TYPE_MASK;
    	    int hdrlen;
    
    	    // 如果avail空闲空间比所需空间大,则直接返回
    	    /* Return ASAP if there is enough space left. */
    	    if (avail >= addlen) return s;
    
    	    // 获得sds的长度len
    	    len = sdslen(s);
    	    // 获得指向sds结构体的指针sh
    	    sh = (char*)s-sdsHdrSize(oldtype);
    	    newlen = (len+addlen);
    
    	    // 如果新的长度少于SDS_MAX_PREALLOC(1024*1024),则申请多一倍的空间作为预留
    	    if (newlen < SDS_MAX_PREALLOC)
    	        newlen *= 2;
    	    else
    	        // 如果新的长度大于等于SDS_MAX_PREALLOC(1024*1024),则申请多一个如果新的长度大于等于SDS_MAX_PREALLOC的空间作为预留
    	        newlen += SDS_MAX_PREALLOC;
    
    	    // 根据新的空间长度,获取sds的结构体类型
    	    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为新sds结构体的大小
    	    hdrlen = sdsHdrSize(type);
    	    if (oldtype==type) {
    	        // 当sds结构体类型不需要改变时
    	        // 通过realloc()在原本结构体上扩大内存
    	        newsh = s_realloc(sh, hdrlen+newlen+1);
    	        if (newsh == NULL) return NULL;
    	        // s指向结构体的buf
    	        s = (char*)newsh+hdrlen;
    	    } else {
    	        /* Since the header size changes, need to move the string forward,
    	         * and can't use realloc */
    
    	        // 因为sds结构体类型变了,所以需要重新分配内存
    
    	        newsh = s_malloc(hdrlen+newlen+1);
    	        if (newsh == NULL) return NULL;
    	        // 拷贝原本字符串到新的sds结构体的buf中
    	        memcpy((char*)newsh+hdrlen, s, len+1);
    	        // 释放旧的sds
    	        s_free(sh);
    	        // 各个属性重新赋值
    	        s = (char*)newsh+hdrlen;
    	        s[-1] = type;
    	        sdssetlen(s, len);
    	    }
    	    // 赋值sds新的alloc值
    	    sdssetalloc(s, newlen);
    	    return s;
    	}
    

SDS与C字符串的区别

总结之《Redis设计与实现》

C字符串 SDS
获取字符串长度的复杂度为O(N) 通过SDS中的len属性,获取字符串的复杂度为O(1)
API是不安全的,可能会造成缓冲区溢出 API是安全的,不会造成缓冲区溢出,因为封装的函数都会去检查是否够剩余的内存地址
修改字符串长度N次必然需要执行N此内存重新分配 修改字符串长度N此最多需要执行N次内存分配,因为在字符串拼接等操作中,封装的函数会给SDS分配预留的内存空间,所以下次操作并不一定会引起内存重新分配。
只能保存文本数据 可以保存文本或二进制数据,因为SDS是通过len属性来判断字符串是否结束,而不是通过'\0'
可以使用所有<string.h>库中的函数 可以使用部分<string.h>库中的函数,因为SDS始终会将字符串结束符'\0'追加到字符串的末尾

SDS API

参考之《Redis设计与实现》

函数 作用 时间复杂度
sds sdsnewlen(const void *init, size_t initlen) 通过C字符串init和字符串长度initlen创建一个SDS字符串 O(N), N为长度initlen
sds sdsnew(const char *init) 通过C字符串init创建一个SDS字符串,实际上是调用sdsnewlen() O(N), N为字符串init长度
sds sdsempty(void) 创建一个空的SDS字符串,实际上调用sdsnewlen("", 0) O(1)
sds sdsdup(const sds s) 创建给定的SDS字符串s的副本(复制),实际上调用sdsnewlen(s, sdslen(s)) O(N)
void sdsfree(sds s) 释放给定的SDS O(N)
sds sdsgrowzero(sds s, size_t len) 将sds增长到指定的长度,如果指定的长度小于sds当前长度,则不进行操作 O(N)
sds sdscatlen(sds s, const void *t, size_t len) 将指定长度len的二进制安全字符t追加到sdss O(N)
sds sdscat(sds s, const char *t) 将指定字符串t追加到sdss上,实际上调用的是sdscatlen(s, t, strlen(t)) O(N)
sds sdscatsds(sds s, const sds t) 将指定sds字符串t追加到sdss上,实际上调用的是sdscatlen(s, t, sdslen(t)) O(N)
sds sdscpylen(sds s, const char *t, size_t len) 破坏性的修改sdss,将指定长度len的二进制安全字符串t赋值给s O(N)
sds sdscpy(sds s, const char *t) 将指定的C字符串t赋值给sdss O(N)
sds sdscatvprintf(sds s, const char *fmt, va_list ap) 将不定参apfmt中格式化为字符串,然后拼接到sdss
sds sdscatprintf(sds s, const char *fmt, ...) 将按fmt格式化后的字符串附加到sdss
sds sdscatfmt(sds s, char const *fmt, ...) 类似于sdscatprintf()函数,但速度更快,不依赖于libc实现的sprintf(); %s - C String,%S - SDS string,%i - signed int,%I - 64 bit signed integer (long long, int64_t),%u - unsigned int,%U - 64 bit unsigned integer (unsigned long long, uint64_t),%% - Verbatim "%" character
sds sdstrim(sds s, const char *cset) 从sdss左边和右边删除cset中含有的字符,知道遇到非匹配时停止。 O(N)
void sdsrange(sds s, ssize_t start, ssize_t end) 保留sdss给定区间内的数据,不在区间内的数据将会被覆盖或清除 O(N)
void sdsupdatelen(sds s) 将sdss的长度设置为strlen(s)的长度,即遇到第一个'\0'字符的长度 O(N)
void sdsclear(sds s) 清空sdss中的数据,实际操作是将sds中的len设为0,并将s[0]设为'\0' O(1)
int sdscmp(const sds s1, const sds s2) 对比两个sds字符串s1s2是否相同,实现上先对比长度,再对比内容 长度相同时O(N),长度不同时O(1)
sds *sdssplitlen(const char *s, ssize_t len, const char *sep, int seplen, int *count) 使用字符串sep分割sdssseplensep的长度,count是分割后返回的sds字符串个数
void sdsfreesplitres(sds *tokens, int count) 释放sdssplitlen()返回的结果的内存,tokens为返回的结果,count为返回的sds字符串个数
void sdstolower(sds s) 将sdss中的所有字符转为小写 O(N)
void sdstoupper(sds s) 将sdss中的所有字符转为大写 O(N)
sds sdsfromlonglong(long long value) 通过一个long long类型的value来创建sds字符串,性能比sdscatprintf(sdsempty(),"%lld\n", value)要好
sds sdscatrepr(sds s, const char *p, size_t len) 将指定长度len的字符串p附加到sdss中,但要检查p中的字符,如果是非打印字符,则要转成\n\r\a...."\x<hex-number>"的形式 O(N)
sds *sdssplitargs(const char *line, int *argc) 将命令行参数解析成sds数组,argc表示数组大小;返回的sds数组要使用sdsfreesplitres()函数释放内存
sds sdsmapchars(sds s, const char *from, const char *to, size_t setlen) sfrom字符集的字符映射成to中的对应字符集,setlen表示fromto中字符集的个数,二者必须严格一一对应
sds sdsjoin(char **argv, int argc, char *sep) 将C的字符串数组合并为sds字符串,argv为字符串数组的首地址,argc为数组的长度,sep为分隔符
sds sdsjoinsds(sds *argv, int argc, const char *sep, size_t seplen) 将sds字符串数组合并为sds字符串,argv为字符串数组的首地址,argc为数组的长度,sep为分隔符
展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
在线直播报名
返回顶部
顶部