redis数据结构-SDS
【摘要】 sds在redis中,存储字符串的结构称为 sds (Simple Dynamic String) 简单动态字符串在源码sds.h中定义如下:typedef char *sds;/* Note: sdshdr5 is never used, we just access the flags byte directly. * However is here to document the la...
sds
在redis中,存储字符串的结构称为 sds (Simple Dynamic String) 简单动态字符串
在源码sds.h中定义如下:
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[];
};可以看出,sds其实只是一个char 的一个别名,实现sds的完整数据结构包括了 sdshdr\ 的结构
attribute ((packed))
这个语法是gcc编译器的特有的语法,表示结构体将不使用内存对齐技术,而是使用紧凑模式存储结构体,例如:
#include<stdio.h>
#include<stdlib.h>
#include <string.h>
struct Test1 {
char a;//1
uint8_t b;//1
uint32_t c;//4
uint64_t d;//8
};
struct __attribute__ ((__packed__)) Test2 {
char a;//1
uint8_t b;//1
uint32_t c;//4
uint64_t d;//8
};
int main() {
printf("%ld\n", sizeof(struct Test1));//16
printf("%ld\n", sizeof(struct Test2));//14
return 0;
}在这个例子中,内存存储为:
在Test1 中,最大的直接为unit64 占用8字节,为了内存对齐,则会额外分配一个新的8字节,用于存储其他属性,其他属性如果存的下就存,存不下就开辟新的8字节,用于内存对齐
而在Test2中,使用了紧凑模式,字节数等于成员占用内存数,节省了一部分内存
sds存储结构
在sds中,8的存储结构如下:
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[];
};如图:
可以看到,sdshdr8的内存地址,包含了len,alloc,flags,buff则存储了sds的指针和字符串数据,那么可以发现,sds指针-1的位置,是flag
unsigned char flags = s[-1];flags低三位表示类型,通过flags能知道具体存储的类型:
unsigned char flags = s[-1];
switch(flags&SDS_TYPE_MASK) {
case SDS_TYPE_5:
{
unsigned char *fp = ((unsigned char*)s)-1;
*fp = SDS_TYPE_5 | (newlen << SDS_TYPE_BITS);
}
break;
case SDS_TYPE_8:
SDS_HDR(8,s)->len = newlen;
break;
case SDS_TYPE_16:
SDS_HDR(16,s)->len = newlen;
break;
case SDS_TYPE_32:
SDS_HDR(32,s)->len = newlen;
break;
case SDS_TYPE_64:
SDS_HDR(64,s)->len = newlen;
break;
}通过类型,可以知道前面的结构体的类型,从而知道结构体的长度,sds的指针位置-结构体长度=sdshdr的指针位置:
#define SDS_HDR(T,s) ((struct sdshdr##T *)((s)-(sizeof(struct sdshdr##T))))这样,我们就知道了sds和sdshdr之间的关系
创建字符串
申请长度为 sdshdr结构体长度+字符串长度+1的内存空间,为什么需要+1呢?因为存储字符串时,会额外存储 "\0"用于结尾:
sh = trymalloc?
s_trymalloc_usable(hdrlen+initlen+1, &usable) :
s_malloc_usable(hdrlen+initlen+1, &usable);这样,sds字符串的指针位置,就等于 sdshdr指针+sdshdr长度
s = (char*)sh+hdrlen;最后,通过memcpy,将字符串的值复制到sds的上,加上\0,就完成了
if (initlen && init)
memcpy(s, init, initlen);
s[initlen] = '\0';动态扩容字符串
当需要动态扩容字符串时,先计算新的长度数量,贪婪模式下,将扩充为2倍:
if (greedy == 1) {
if (newlen < SDS_MAX_PREALLOC)
newlen *= 2;
else
newlen += SDS_MAX_PREALLOC;
}计算新长度需要使用的sdshdr结构体类型,判断旧结构体类型是否一致
如果类型一致,则只需要额外分配新的内存空间即可
if (oldtype==type) {
newsh = s_realloc_usable(sh, hdrlen+newlen+1, &usable);
if (newsh == NULL) return NULL;
s = (char*)newsh+hdrlen;
}如果不一致,则需要类似于新增的逻辑,重新分配一块新的内存空间,将旧数据拷贝到新空间中
newsh = s_malloc_usable(hdrlen+newlen+1, &usable);
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);
【版权声明】本文为华为云社区用户原创内容，转载时必须标注文章的来源（华为云社区）、文章链接、文章作者等基本信息， 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）