阅读源码之前,先接几个问题,我觉得还蛮有意思的。
Q1:如何实现一个扩容方便且二进制安全(不会被\0打断)的字符串呢?
Q2:SDS如何兼容C语言函数呢?
Q3:SDS为了节约内存都秀了什么操作呢?
Q4:SDS是如何扩容的?
Q5:SDS是如何减少拷贝次数的?
题外话:这种模式我还挺喜欢的,也写过一些源码分析类的博客,但是感觉看完之后就没了,收效甚微。看nginx的时候,除了惊叹于其鬼斧神工的架构设计,以及比较火的那几点问题之后,也没学到多少编程技法(我主要编程技法都是在STL源码里学的,当然萃取是没看明白),不过如果采用这种启发式学习的方式可能会好一些,也能让人更愿意看源码吧。
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 { //该字段记录的字符串的长度,可以在常数时间获取 //由于有长度记录变量len,在读写字符串的时候不依赖于‘\0’,从而保证了二进制安全性。 uint8_t len; /* used */ //可存储的最大字符串长度为 2^8=256 uint8_t alloc; /* excluding the header and null terminator */ //低三位表示字符串的类型,高五位只在sd5中使用,不过看着架势sd5是被打入冷宫了呀。 unsigned char flags; /* 3 lsb of type, 5 unused bits */ //柔性数组,保存一个空字符作为buf的结尾,不计入len、alloc,以此兼容 C 语言的 strcmp、strcpy 等函数。 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[]; };
A String value can be at max 512 Megabytes in length,如果拿那个64来算,会只有这点吗?
但是一个字符串过大也没用。
使用柔性数组除了省内存,还有一个好处,柔型数组的内存和结构体是连续的,可以很方便的通过柔型数组的首地址偏移得到结构体的首地址。
接下来看一下是如何的节约内存的:
这是sdshdr5的,里面的 unsigned8 对应一个字节。后面的自行脑补。
sds sdsnewlen(const void *init, size_t initlen) { void *sh; sds s; char type = sdsReqType(initlen); /* 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; //SDS_TYPE_5 强制转换为 SDS_TYPE_8 int hdrlen = sdsHdrSize(type); //计算不同头部的所需的那个 unsigned 长度 unsigned char *fp; /* flags pointer. */ sh = s_malloc(hdrlen+initlen+1); //留了一个给‘\0’ if (sh == NULL) return NULL; if (init==SDS_NOINIT) init = NULL; else if (!init) memset(sh, 0, hdrlen+initlen+1); s = (char*)sh+hdrlen; //直接指向buf fp = ((unsigned char*)s)-1; //buf首地址偏移 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_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; }
至于为什么要把sd5打入冷宫?可能是因为太短了吧,承受变长风险能力不够、
/* Free an sds string. No operation is performed if 's' is NULL. */ void sdsfree(sds s) { if (s == NULL) return; s_free((char*)s-sdsHdrSize(s[-1])); //这里是直接释放内存了 }
不过这些优秀项目怎么能没有内存池呢,明着暗着都会有的。
/* Modify an sds string in-place to make it empty (zero length). * However all the existing buffer is not discarded but set as free space * so that next append operations will not require allocations up to the * number of bytes previously available. */ void sdsclear(sds s) { sdssetlen(s, 0); s[0] = '\0'; }
该有的都会有的。
扩容流程图:
/* 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 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; //此役过后,指向buf的指针被更新了 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; }
注意,分支上半部分是 realloc,下半部分是 malloc,注意区分二者区别。
__attribute__ ((__packed__))
在结构体声明当中,加上attribute ((packed))关键字,它可以做到让我们的结构体,按照紧凑排列的方式,占用内存。
简单的说,就是取消内存对齐。
这个 tip 哪里来的呢?翻到开头再看看。这个编程技法需要特别关注,稍不留神就错过了。
一般情况下,结构体会做内存对齐,以sd32为例,对齐前按4字节对齐,大小为12字节。取消对齐后,大小为9字节(buf不要面子的)。
而且,对齐后,可以直接通过 buf 的首地址向前偏移一位找到 flags ,如果不这样,各位可以自己思考一下要如何找到 flags,那就几乎成了一个 “鸡/蛋” 的死结了(不知道类型,怎么着偏移量?不知道偏移量,怎么找类型?)。
那各位自己解答开头的问题吧,溜了溜了。