【Redis】Redis内部数据结构之SDS

Sds：Simple Dynamic String 简单动态字符串。是Redis底层使用的数据结构。

Sds的定义都在Redis源码中的sds.h和sds.c文件中。

下面定义了几个sds的结构体：

 1 struct __attribute__ ((__packed__)) sdshdr5 {
 2     unsigned char flags; /* 3 lsb of type, and 5 msb of string length */
 3     char buf[];
 4 };
 5 struct __attribute__ ((__packed__)) sdshdr8 {
 6     uint8_t len; /* used */
 7     uint8_t alloc; /* excluding the header and null terminator */
 8     unsigned char flags; /* 3 lsb of type, 5 unused bits */
 9     char buf[];
10 };
11 struct __attribute__ ((__packed__)) sdshdr16 {
12     uint16_t len; /* used */
13     uint16_t alloc; /* excluding the header and null terminator */
14     unsigned char flags; /* 3 lsb of type, 5 unused bits */
15     char buf[];
16 };
17 struct __attribute__ ((__packed__)) sdshdr32 {
18     uint32_t len; /* used */
19     uint32_t alloc; /* excluding the header and null terminator */
20     unsigned char flags; /* 3 lsb of type, 5 unused bits */
21     char buf[];
22 };
23 struct __attribute__ ((__packed__)) sdshdr64 {
24     uint64_t len; /* used */
25     uint64_t alloc; /* excluding the header and null terminator */
26     unsigned char flags; /* 3 lsb of type, 5 unused bits */
27     char buf[];
28 };

其中，sdshdr5没有使用，主要是后面的几个结构，他们的字段都相似：

len 当前被使用的长度，就是字符串的长度

alloc 除开标头和空终止符，总的分配长度。

flags 实际上代表SDS的实际类型，因为对外展现的时候，肯定不是直接提供sdshdr5或者sdshdr8等，而是提供一个sds类型，但实际上sds就是封装了sdshdr5、sdshdr8等，我们可以看到源码中对类型的定义：

1 #define SDS_TYPE_5  0
2 #define SDS_TYPE_8  1
3 #define SDS_TYPE_16 2
4 #define SDS_TYPE_32 3
5 #define SDS_TYPE_64 4
6 #define SDS_TYPE_MASK 7
7 #define SDS_TYPE_BITS 3

buf[] 真正存储字符的字符数组。

下面，我们看看如何创建一个新的SDS，在sds.c文件中有定义sdsnew、sdsempty和sdsdup三个方法：

/* Create an empty (zero length) sds string. Even in this case the string
 * always has an implicit null term. */
sds sdsempty(void) {
    return sdsnewlen("",0);
}

/* 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);
}

/* Duplicate an sds string. */
sds sdsdup(const sds s) {
    return sdsnewlen(s, sdslen(s));
}

他们都调用了sdsnewlen方法，第一个参数为初始化内容，第二个参数为初始化长度：

 1 sds sdsnewlen(const void *init, size_t initlen) {
 2     void *sh;
 3     sds s;
 4     // 根据初始化长度获得SDS类型
 5     char type = sdsReqType(initlen);
 6     /* Empty strings are usually created in order to append. Use type 8
 7      * since type 5 is not good at this. */
 8     // 如果获得的SDS类型是sdshdr5，且初始化长度为0的话，则转换为sdshdr8，
 9     if (type == SDS_TYPE_5 && initlen == 0) type = SDS_TYPE_8;
10     // 获取数据结构的长度
11     int hdrlen = sdsHdrSize(type);
12     unsigned char *fp; /* flags pointer. */
13 
14     // 初始化sds空间
15     sh = s_malloc(hdrlen+initlen+1);
16     if (init==SDS_NOINIT)
17         init = NULL;
18     else if (!init)
19         memset(sh, 0, hdrlen+initlen+1);// 初始化分配的内存
20     if (sh == NULL) return NULL;
21     s = (char*)sh+hdrlen;
22     fp = ((unsigned char*)s)-1;
23 
24     // 设置flag
25     switch(type) {
26         case SDS_TYPE_5: {
27             *fp = type | (initlen << SDS_TYPE_BITS);
28             break;
29         }
30         case SDS_TYPE_8: {
31             SDS_HDR_VAR(8,s);
32             sh->len = initlen;
33             sh->alloc = initlen;
34             *fp = type;
35             break;
36         }
37         case SDS_TYPE_16: {
38             SDS_HDR_VAR(16,s);
39             sh->len = initlen;
40             sh->alloc = initlen;
41             *fp = type;
42             break;
43         }
44         case SDS_TYPE_32: {
45             SDS_HDR_VAR(32,s);
46             sh->len = initlen;
47             sh->alloc = initlen;
48             *fp = type;
49             break;
50         }
51         case SDS_TYPE_64: {
52             SDS_HDR_VAR(64,s);
53             sh->len = initlen;
54             sh->alloc = initlen;
55             *fp = type;
56             break;
57         }
58     }
59     
60     
61     if (initlen && init)
62         memcpy(s, init, initlen);
63     s[initlen] = '';
64     return s;
65 }