redis的几个数据结构——sds

redis中的字符串都会存放在一种叫做sds的结构中,如下所示。

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; /* 已使用长度 */
    uint32_t alloc; /* 总长度 */
    unsigned char flags; /* 低三位存储类型,高五位预留 */
    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[];
};

其中各个字段的含义:

  • len:表示buf中已占用字节数。
  • alloc:表示buf中已分配字节数
  • flags:标识当前结构体的类型,比如是sdshdr5、sdshdr8等等。
  • buf:柔性数组,存储字符串。

假设有一个"redis"的字符串,则sds中是这样表示的:
graphviz-72760f6945c3742eca0df91a91cc379168eda82d
或者这样表示:
graphviz-5fccf03155ec72c7fb2573bed9d53bf8f8fb7878

对比原始的C字符串,这样子做的好处主要有以下这几个:

  1. 获取长度的时间复杂度O(1)
  2. 可高效执行append
  3. 杜绝缓冲区溢出
  4. 二进制安全

可以注意到SDS跟C字符串一样也是以'\0'为结尾,这样子可以复用C的一部分字符串函数。

其中,柔性数组的定义如下:

柔型数组:在C99 中,结构中的最后一个元素允许是未知大小的数组,这就叫做柔性数组(flexible array)成员(也叫伸缩性数组成员),但结构中的柔性数组成员前面必须至少一个其他成员。柔性数组成员允许结构中包含一个大小可变的数组。柔性数组成员只作为一个符号地址存在,而且必须是结构体的最后一个成员,sizeof 返回的这种结构大小不包括柔性数组的内存。柔性数组成员不仅可以用于字符数组,还可以是元素为其它类型的数组。包含柔性数组成员的结构用malloc ()函数进行内存的动态分配,并且分配的内存应该大于结构的大小,以适应柔性数组的预期大小。

typedef struct test
{
int a;
double b;
char c[];
};

分配内存:test *stpTest = (test )malloc(sizeof(test)+100sizeof(char));

c就是一个柔性数组成员,如果把stpTest指向的动态分配内存看作一个整体,c就是一个长度可以动态变化的结构体成员,柔性一词来源于此。c的长度为0,因此它不占用test的空间,同时stpTest->c就是“hello world”的首地址,不需要再使用( char * )( stpTest + 1 )这么丑陋的代码了。那个0个元素的数组没有占用空间,而后我们可以进行变长操作了。这样我们为结构体指针c分配了一块内存。用stpTest->c[n]就能简单地访问可变长元素。

comments powered by Disqus