redis6.0源码学习（二）sds
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了redis6.0源码学习（二）sds，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含8436字，纯文字阅读大概需要13分钟。
内容图文
redis6.0源码学习（二）sds
文章目录
1、数据结构
源码所在文件 sds.h 和 sds.c
sds的定义
typedef char *sds;
sds字符串根据字符串的长度，划分了五种结构体sdshdr5、sdshdr8、sdshdr16、sdshdr32、sdshdr64,分别对应的类型为SDS_TYPE_5、SDS_TYPE_8、SDS_TYPE_16、SDS_TYPE_32、SDS_TYPE_64
struct __attribute__ ((__packed__)) sdshdr5 {
unsigned char flags; /* 低3位用来存储类型，高5位用来存储长度 */
char buf[];
};
struct __attribute__ ((__packed__)) sdshdr8 {
uint8_t len; /* 字符串在buf中实际占用的字节数（不包括'\0'）*/
uint8_t alloc; /* 去除头长度和结束符'\0'后的总长度 */
unsigned char flags; /* 低位的3个bit位用来表示结构类型，其余5个bit位未使用 */
char buf[];
};
struct __attribute__ ((__packed__)) sdshdr16 {
uint16_t len; /* 字符串在buf中实际占用的字节数（不包括'\0'）*/
uint16_t alloc; /* excluding the header and null terminator */
unsigned char flags; /* 低位的3个bit位用来表示结构类型，其余5个bit位未使用 */
char buf[];
};
......
- __attribute__ ((__packed__)) 告诉编译分配的是紧凑内存，而不是字节对齐的方式。
- len表示字符串已使用的长度,buf长度
- alloc表示字符串的容量
- flags表示字符串类型标记SDS_TYPE_5、SDS_TYPE_8、SDS_TYPE_16、SDS_TYPE_32、SDS_TYPE_64
- buf[]表示柔性数组。在分配内存的时候会指向字符串的内容
2、sds创建
根据传入的字符串创建sds
/* 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);
}
下面是主要创建的逻辑
sds sdsnewlen(const void *init, size_t initlen) {
void *sh;
sds s;
//根据字符串长度获取SDS的类型
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;
int hdrlen = sdsHdrSize(type);
unsigned char *fp; /* flags pointer. */
//分配内存
sh = s_malloc(hdrlen+initlen+1);
if (sh == NULL) return NULL;
if (init==SDS_NOINIT)
init = NULL;
else if (!init)
memset(sh, 0, hdrlen+initlen+1);
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_HDR_VAR(16,s); //使用宏来获取sdshdr结构体指针
sh->len = initlen;
sh->alloc = initlen;
*fp = type;
break;
}
//......省略部分代码
}
if (initlen && init)
memcpy(s, init, initlen);
s[initlen] = '\0';
return s; //返回值的首地址是buf地址，而不是整个sds的首地址
}
总结步骤就是：
- 1、根据传入的字符串长度获取sds的类型（用适当的类型存储，减少内存消耗）。如果初始化长度initlen为0，通常被认为要进行append操作，直接设置SDS类型为SDS_TYPE_8。
- 2、分配内存，大小为：hdrlen+initlen+1 (hdrlen:类型结构体的大小，initlen：字符串大小， 1：\0 结束符的长度)
- 3、初始化sds结构体中alloc、len、 flag值
- 4、拷贝字符串到sds结构体， 添加结束符
3、sds扩容
扩容
/* 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); //获取sds目前空余的空间
size_t len, newlen;
char type, oldtype = s[-1] & SDS_TYPE_MASK; //获取sds类型
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) //新的长度小于1024*1024，即两倍的扩容
newlen *= 2;
else
newlen += SDS_MAX_PREALLOC; //新长度直接加上1024*1024大小
type = sdsReqType(newlen); //获取存储新sds的结构体类型
/* 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) {
//sds类型不变，重新分配内存
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 */
//sds类型发生改变，重新申请新内存
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); //更新sds已使用空间长度
}
sdssetalloc(s, newlen);//更新sds容量
return s;
}
步骤大致如下：
- 1、查看sds中是否有足够的剩余空间容纳addlen长度的字符串，有则返回，无则继续其它操作。
- 2、 计算需要重新分配的存储空间的长度，包括原sds长度与addlen，另外预备一部分的剩余空间。
- 3、如果新sds长度小于1M则默认两倍扩容，否则只 扩容 （1M + addlen） 大小
- 4、根据新的长度，得到新的sds头部类型，如果新的头部类型与原类型相同，则使用s_realloc分配更多的空间；如果新的头部类型与原类型不相同，则使用s_alloc重新分配内存，并将原sds内容copy到新分配的空间。
4、sds缩容
sds在缩容时，并不是立即释放内存。比如sdstrim函数
/* Remove the part of the string from left and from right composed just of
* contiguous characters found in 'cset', that is a null terminted C string.
*
* 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("AA...AA.a.aa.aHelloWorld :::");
* s = sdstrim(s,"Aa. :");
* printf("%s\n", s);
*
* Output will be just "Hello World".
*从 SDS 左右两端分别移除所有在 C 字符串中出现过的字符。
*接受一个 SDS 和一个 C 字符串作为参数， 从 SDS 左右两端分别移除所有在 C 字符串中出现过的字符。
*/
sds sdstrim(sds s, const char *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++;
while(ep > sp && strchr(cset, *ep)) ep--;
len = (sp > ep) ? 0 : ((ep-sp)+1);
if (s != sp) memmove(s, sp, len);
s[len] = '\0';
sdssetlen(s,len);
return s;
}
比如有个字符串s1=“REDIS”，对s1进行sdstrim(s1," S")操作，执行完该操作之后Redis不会立即回收减少的部分，也就是而是会分配给下一个需要内存的程序。
下面的函数是真正释放内存。
/* Reallocate the sds string so that it has no free space at the end. The
* contained string remains not altered, but next concatenation operations
* will require a reallocation.
*
* 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 sdsRemoveFreeSpace(sds s) {
void *sh, *newsh;
char type, oldtype = s[-1] & SDS_TYPE_MASK; //获取sds类型
int hdrlen, oldhdrlen = sdsHdrSize(oldtype); //获取sds头的长度
size_t len = sdslen(s);
size_t avail = sdsavail(s); //获取sds目前空余的空间
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); //更新sds已使用空间长度
}
sdssetalloc(s, len);//更新sds容量
return s;
}
和扩容的步骤基本相似。
5、总结
SDS和C字符串的区别
（1）获取字符串长度的时间复杂度
C字符串不记录字符串本身是长度，因此需要遍历字符串才能得到字符串的长度，时间复杂度为O(N)，SDS字符串用属性len记录了字符串的长度，因此获取字符串长度的时间复杂度为O(1)。
（2）缓冲区溢出
如果对C字符串使用strcat进行拼接，如果没有提前对字符串分配足够的内存，则会导致缓冲区溢出。但是SDS会提前对字符串所需要的内存进行检测。
（3）修改字符串时的内存重分配
当修改C字符串的时候，无论是增长/缩短字符串，都会通过内存重分配来扩展或者释放内存，否则就会导致缓冲区溢出或者内存泄漏。SDS在扩容是采用的是预分配机制避免了频繁扩容。
（4）二进制安全性
如果一个字符串保存的时候是什么样子，输出的时候也是什么样子，则称为二进制安全的，C字符串以’\0’作为字符串的结尾标识，会造成从中间截断字符串的情况。SDS使用len属性记录字符串的长度，因此保存二进制数据是安全的。也就是说sds中间也可以存在 \0 字符。
内容总结
以上是互联网集市为您收集整理的redis6.0源码学习（二）sds全部内容，希望文章能够帮你解决redis6.0源码学习（二）sds所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。
来源：【匿名】