Redis 中动态字符串 sds 相关的文件为: sds.h 与 sds.c
一, 数据结构
Redis 中定义了自己的数据类型 "sds", 用于描述 char*, 与一些数据结构
- typedef char *sds;
- /* 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[];
- };
定义结构体时, 加上了 __attribute__ ((__packed__)) 关键字, 用于取消字节对齐, 使其按照紧凑排列的方式, 占用内存. 这样做的目的并不仅仅只是为了节约内存的使用. 结构体最后有一个 char buf[], 查了资料之后了解到, 其只是定义一个数组符号, 并没有任何成员, 不占用结构体的内存空间, 其真实地址紧随结构体之后, 可实现变长结构体. 由此可以只根据 sds 字符串的真实地址, 取到 sds 结构体的任意成员变量数据. 如 flags:
- void func(const sds s)
- {
- unsigned char flags = s[-1];
- }
这个 flags, 从源码的注释上看, 其低三位用于表示 sds 类型, 高五位是当 sds 类型为 sdshdr5 时, 表明字符串长度的. 对于非 sdshdr5 的类型, 有专门的成员变量描述当前已使用的长度, 及总 buffer 长度.
sds 类型:
- #define SDS_TYPE_5 0
- #define SDS_TYPE_8 1
- #define SDS_TYPE_16 2
- #define SDS_TYPE_32 3
- #define SDS_TYPE_64 4
sds 定义了两个宏, 用于获取 sds 结构体首地址:
- #define SDS_HDR_VAR(T,s) struct sdshdr##T *sh = (void*)((s)-(sizeof(struct sdshdr##T)));
- #define SDS_HDR(T,s) ((struct sdshdr##T *)((s)-(sizeof(struct sdshdr##T))))
由此可见 sds 结构体的大致结构为:
/*
sdshdr5
+--------+----...---+
|00011000|abc\0 |
+--------+----...---+
|flags |buf
sdshdr8
+--------+--------+--------+----...---+
|00000011|00000011|00000001|abc\0 |
+--------+--------+--------+----...---+
|len |alloc |flags |buf
*/
sds 的一些常规操作, 如获取字符串长度, 获取剩余 buf 长度等, 都是其于以上操作, 首先根据 sds 字符串地址获取其 flags 的值, 根据 flags 低三位判断 sds 类型, 接着使用宏 SDS_HDR_VAR 或 SDS_HDR 进行操作. 如:
- #define SDS_TYPE_MASK 7 //0000,0111
- static inline size_t sdslen(const sds s) {
- // 获取 flags
- unsigned char flags = s[-1];
- // 根据 flags 低三位取类型, 根据类型做不同处理
- 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 结构体中的 len 与 alloc,len 表示的是 sds 字符串的当前长度, alloc 表示的是 buf 的总长度.
二, 一些操作.
首先是一个根据字符串长度来决定 sds 类型的方法
- static inline char sdsReqType(size_t string_size) {
- if (string_size <1<<5) //flags 高五位最大数字为 1<<5 - 1
- return SDS_TYPE_5;
- if (string_size < 1<<8) //uint8_t 最大数字为 1<<8 - 1
- return SDS_TYPE_8;
- if (string_size < 1<<16) //uint16_t 最大数字为 1<<16 - 1
- return SDS_TYPE_16;
- #if (LONG_MAX == LLONG_MAX) // 区分 32 位 / 64 位系统
- if (string_size < 1ll<<32)
- return SDS_TYPE_32;
- return SDS_TYPE_64;
- #else
- return SDS_TYPE_32;
- #endif
- }
创建一个新的 sds 结构体:
- sds sdsnewlen(const void *init, size_t initlen) {
- void *sh;
- sds s;
- char type = sdsReqType(initlen);
- 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;
- fp = ((unsigned char*)s)-1;
- switch(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;
- break;
- }
- case SDS_TYPE_16: {
- // 同 SDS_TYPE_8, 略
- }
- case SDS_TYPE_32: {
- // 同 SDS_TYPE_8, 略
- }
- case SDS_TYPE_64: {
- // 同 SDS_TYPE_8, 略
- }
- }
- if (initlen && init)
- memcpy(s, init, initlen);
- s[initlen] = '\0';
- return s;
- }
由外部指定初始字符串与初始长度. 先根据长度获取 sds 类型, 然后根据不同类型, 可以获得实际需要的总内存空间大小(包括 sds 结构体长度). 值得注意的是, 如果初始长度为 0 的情况下, 若为 SDS_TYPE_5, 则会被强制转为 SDS_TYPE_8. 根据源码的注释, 空串的定义, 通常是为了向后追加内容. SDS_TYPE_5 并不适合这种场景. 分配完内存空间之后, 设置好 sds 结构体的值, 再把初始字符串拷至 sds 字符串的实际初始位置上(如果有), 就可以了.
本方法做为最底层的 sds 字符串初始化接口, 被其它接口所调用, 如:
- // 空 string
- sds sdsempty(void) {
- return sdsnewlen("",0);
- }
- // 指定 string
- sds sdsnew(const char *init) {
- size_t initlen = (init == NULL) ? 0 : strlen(init);
- return sdsnewlen(init, initlen);
- }
- // 从现有 sds string 拷贝
- sds sdsdup(const sds s) {
- return sdsnewlen(s, sdslen(s));
- }
sds 的释放也不是简单地 free sds 字符串, 同样, 它要先找到 sds 结构体的首地址, 再进行 free:
- void sdsfree(sds s) {
- if (s == NULL) return;
- s_free((char*)s-sdsHdrSize(s[-1]));
- }
做为一个变长字符串, 与传统 c 字符串, 最大的区别, 是可以动态扩展, 就像 c++ stl 里的变长数组 vector 一样. sds 的扩容有自己的机制:
- 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);
- sh = (char*)s-sdsHdrSize(oldtype);
- newlen = (len+addlen);
- if (newlen <SDS_MAX_PREALLOC)
- newlen *= 2;
- else
- newlen += SDS_MAX_PREALLOC;
- 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) {
- 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);
- if (newsh == NULL) return NULL;
- memcpy((char*)newsh+hdrlen, s, len+1);
- s_free(sh);
- s = (char*)newsh+hdrlen;
- s[-1] = type;
- sdssetlen(s, len);
- }
- sdssetalloc(s, newlen);
- return s;
- }
本方法用于扩容 sds, 并可以指定长度. 首先其先取出了当前还空闲的 buf 长度, 方法如下:
- 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;
- }
若当前空闲的长度, 比需要的长度大, 则认为不用再额外分配空间, 直接 return. 否则就启用扩容操作.
扩容时, 先根据当前已使用的长度 len 与需要增加的长度 addlen, 算出一个初始新长度 newlen, 然后对其进行判断, 若 newlen 大于 1M, 则在 newlen 的基础上, 继续增加 1M, 否则直接翻倍. 然后再根据 newlen 的最终大小, 获取 sds 的新类型. 此时, 若类型依然为 SDS_TYPE_5, 也要强行修正为 SDS_TYPE_8. 因为 SDS_TYPE_5 类型并不知道当前空闲空间的大小. 此时, 若 sds 的新类型与原来相同, 则只需要调用 realloc 重新分配一下空间即可. 此方法会分配出一块新空间的同时, 把原来空间的内容拷过去, 并释放原有空间. 而 sds 类型发生改变的时候, 就需要手动新造一个新的 sds 了. 扩容完成之后, 需要修正一下当前已使用的空间 len, 与总 buf 大小 alloc.
扩容完成之后, 或者是其它什么操作, 如人工修改了 sds 字符串, 并更新的 len 的情况下, 会存在空闲空间太大的情况. 此时如果想释放这部分空间, sds 也提供了相应的操作:
- 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;
- /* Check what would be the minimum SDS header that is just good enough to
- * fit this string. */
- type = sdsReqType(len);
- hdrlen = sdsHdrSize(type);
- /* 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);
- 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;
- s[-1] = type;
- sdssetlen(s, len);
- }
- sdssetalloc(s, len);
- return s;
- }
操作与扩容类似, 同样是会根据 sds 类型是否发生变化 , 来决定是使用 realloc 还是重新造一个 sds.
除此之外, sds 还实现了一些转义, 数据类型转换, 一些类似 c 风格的字符串操作等. 如: strcpy,strcat,strlen,strcmp 等. 只是其更加多样化, 如 sds 的 strcat 实现, 就可以支持类似 printf 的方式. 如:
- /* Like sdscatprintf() but gets va_list instead of being variadic. */
- sds sdscatvprintf(sds s, const char *fmt, va_list ap) {
- va_list cpy;
- char staticbuf[1024], *buf = staticbuf, *t;
- size_t buflen = strlen(fmt)*2;
- /* We try to start using a static buffer for speed.
- * If not possible we revert to heap allocation. */
- if (buflen> sizeof(staticbuf)) {
- buf = s_malloc(buflen);
- if (buf == NULL) return NULL;
- } else {
- buflen = sizeof(staticbuf);
- }
- /* Try with buffers two times bigger every time we fail to
- * fit the string in the current buffer size. */
- while(1) {
- buf[buflen-2] = '\0';
- va_copy(cpy,ap);
- vsnprintf(buf, buflen, fmt, cpy);
- va_end(cpy);
- if (buf[buflen-2] != '\0') {
- if (buf != staticbuf) s_free(buf);
- buflen *= 2;
- buf = s_malloc(buflen);
- if (buf == NULL) return NULL;
- continue;
- }
- break;
- }
- /* Finally concat the obtained string to the SDS string and return it. */
- t = sdscat(s, buf);
- if (buf != staticbuf) s_free(buf);
- return t;
- }
- /* Append to the sds string 's' a string obtained using printf-alike format
- * specifier.
- *
- * After the call, the modified sds string is no longer valid and all the
- * references must be substituted with the new pointer returned by the call.
- *
- * Example:
- *
- * s = sdsnew("Sum is:");
- * s = sdscatprintf(s,"%d %d = %d",a,b,a+b).
- *
- * Often you need to create a string from scratch with the printf-alike
- * format. When this is the need, just use sdsempty() as the target string:
- *
- * s = sdscatprintf(sdsempty(), "... your format ...", args);
- */
- sds sdscatprintf(sds s, const char *fmt, ...) {
- va_list ap;
- char *t;
- va_start(ap, fmt);
- t = sdscatvprintf(s,fmt,ap);
- va_end(ap);
- return t;
- }
其它方法在此不再过多描述
三, sds 相比 c 的标准库优势:
1, 相比于 c 标准库, 获取字符串的 len 复杂读从 O(N)降低到 O(1),sds 结构中存储了字符串的长度, 所以类似 strlen(str)的操作不会成为 Redis 的性能瓶颈.
2, 在内存分配策略上, Redis 总是会尝试多分配一些空间, 比如小于 1MB 的字符串, 总是分配 2 倍内存空间, 对于大于 1MB 的空间追加 1MB 冗余空间, 这对于字符串操作 (如 strcat 等) 能减少重新内存分配的几率, 提升运行性能.
3,SDS 总是安全的, sds 总是会自动追加字符串结尾符号'\0', 有效防止溢出发生.
4, 惰性释放内存, 改变原字符串时, 标准库需要重新分配内存的复杂度为 O(N),SDS 最大为 O(N), 最优情况下无需重新分配内存空间.
源码阅读顺序参考:
其它参考资料:
来源: http://www.bubuko.com/infodetail-3393763.html