数据结构

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

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,而不是sdshdr。而sds指向的是sdshdr的buf字段。

各位可能还发现了一个叫做__attribute__ ((__packed__))的东西,不了解的小伙伴赶紧百度一下,它的作用大概就是告诉编译器取消结构在编译过程中的优化对齐,按照实际占用字节数进行对齐,是GCC特有的语法。这个功能是跟操作系统没关系,跟编译器有关,gcc编译器不是紧凑模式的。

取消内存对齐优化有什么用?

这个时候各位就会很迷惑,为啥一定要取消结构的优化对齐,第一个是为了减少sdshdr对内存的占用,想想在大型情况下,几百万个key,取消对齐带来的内存优化还是很客观的,第二个嘛,当然是为了操作方便,上文已经说了,一般的参数里面都是传入sds,而sds是指向的sdshdr的buf字段,下面来看一段代码:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

static inline size_t sdslen(const sds s) {

    unsigned char flags = s[-1];

    switch(flags&SDS_TYPE_MASK) {

        case SDS_TYPE_5:

            return SDS_TYPE_5_LEN(flags);

        case SDS_TYPE_8:

            return SDS_HDR(8,s)->len;

        case SDS_TYPE_16:

            return SDS_HDR(16,s)->len;

        case SDS_TYPE_32:

            return SDS_HDR(32,s)->len;

        case SDS_TYPE_64:

            return SDS_HDR(64,s)->len;

    }

    return 0;

}

这段代码是获取sds的长度的代码,可以看到,在代码中有s[-1],what happen?一般来说我们是不会这么用的,但是也能看出来s[-1]就是指向的s前面的字节的地址,而sds指向的是buf,并且有了__attribute__ ((__packed__))来取消字节对齐优化,正好就会指向sdshdr的flags字段,而flag字段便是来判断sds是何种类型的sdshdr,最后就可以通过转换成对应的sdshdr拿到len啦。对应s[-1]这种操作还有很多处出现,我就不一一解析了,列出来即可:sdsavail,sdssetlen,sdsinclen,sdsalloc,sdssetalloc

SDSHRD类型

| SDSHRD类型 | 描述 |

| :——–: | :———————————————————-: |

| sdshdr5 | 不会被使用,仅仅作为一个文档来使用,字符串长度在1«5以内,但是即便是被选择为sdshdr5,代码上也会转为sdshdr8 |

| sdshdr8 | 字符串长度在1«8以内 |

| sdshdr16 | 字符串长度在1«16以内 |

| sdshdr32 | 字符串长度在1«32以内 |

| sdshdr64 | 字符串长度在1«64以内,如果在32位的机器,是不存在的 |

描述中的信息,具体可以参照sdsReqType函数

API

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147

// 根据init和initlen创建一个新的sds

// 如果init是SDS_NOINIT,会创建一个空的sds

// 会根据initlen调用函数sdsHdrSize来选择对应的sdshdr类型

// sds占用的空间大小: hdrlen+initlen+1

// 初始化后的sdshdr,len和alloc都会被赋值为initlen

// 多申请的一个字节的内存,会直接赋值为'\0',意味这我们可以直接使用printf()函数直接打印sds

// 由于有len的存在,即便是字符串中有'\0'也不会丢失,所以是二进制安全的

sds sdsnewlen(const void *init, size_t initlen);

// 会通过strlen来计算出initlen的长度,然后直接调用sdsnewlen函数

sds sdsnew(const char *init);

// 直接调用sdsnewlen("",0),其实和调用sdsnewlen(SDS_NOINIT,0)没啥区别

sds sdsempty(void);

// 通过sdslen计算出s的长度,使用s的长度作为initlen,然后调用sdsnewlen函数

sds sdsdup(const sds s);

// 释放sds内存的函数

// 前文已经解释过,sds只是sdshdr的buf字段,所以释放sds的内存,实际上是释放咱们占用的sdshdr的所有内存

// 在sdsnewlen函数中的介绍中有说明,sds占用空间的大小==hdrlen+initlen+1,s其实就是指向的是initlen+1这一段内存

// 所以,计算出sdshdr的实际内存开始地址,我们需要s的地址减去其对应的sdshdr对应的空间占用长度

// 借助了sdsHdrSize函数来计算出s对应的sdshdr占用的空间长度,所以sdshdr的开始地址是:s-sdsHdrSize(s)

void sdsfree(sds s);

// 增长sds的空间长度,对扩张的部分置零,会调用sdsMakeRoomFor函数

sds sdsgrowzero(sds s, size_t len);

// sds连接

sds sdscatlen(sds s, const void *t, size_t len);

sds sdscat(sds s, const char *t);

sds sdscatsds(sds s, const sds t);



sds sdscpylen(sds s, const char *t, size_t len);

sds sdscpy(sds s, const char *t);



sds sdscatvprintf(sds s, const char *fmt, va_list ap);

#ifdef __GNUC__

sds sdscatprintf(sds s, const char *fmt, ...)

    __attribute__((format(printf, 2, 3)));

#else

sds sdscatprintf(sds s, const char *fmt, ...);

#endif



sds sdscatfmt(sds s, char const *fmt, ...);

sds sdstrim(sds s, const char *cset);

void sdsrange(sds s, ssize_t start, ssize_t end);

void sdsupdatelen(sds s);

void sdsclear(sds s);

int sdscmp(const sds s1, const sds s2);

sds *sdssplitlen(const char *s, ssize_t len, const char *sep, int seplen, int *count);

void sdsfreesplitres(sds *tokens, int count);

void sdstolower(sds s);

void sdstoupper(sds s);

sds sdsfromlonglong(long long value);

sds sdscatrepr(sds s, const char *p, size_t len);

sds *sdssplitargs(const char *line, int *argc);

sds sdsmapchars(sds s, const char *from, const char *to, size_t setlen);

sds sdsjoin(char **argv, int argc, char *sep);

sds sdsjoinsds(sds *argv, int argc, const char *sep, size_t seplen);



/* Low level functions exposed to the user API */

// 扩大sds的空间

// 如果不需要扩大,会立即返回

// 如果newlen < SDS_MAX_PREALLOC(1MB),会直接让newlen翻倍,否则,会让newlen增加SDS_MAX_PREALLOC

// 如果newlen对比s的长度扩张太多,会引起重新创建sdshdr的操作,还会涉及到s的拷贝操作

sds sdsMakeRoomFor(sds s, size_t addlen);

void sdsIncrLen(sds s, ssize_t incr);

sds sdsRemoveFreeSpace(sds s);

size_t sdsAllocSize(sds s);

void *sdsAllocPtr(sds s);



/* Export the allocator used by SDS to the program using SDS.

 * Sometimes the program SDS is linked to, may use a different set of

 * allocators, but may want to allocate or free things that SDS will

 * respectively free or allocate. */

void *sds_malloc(size_t size);

void *sds_realloc(void *ptr, size_t size);

void sds_free(void *ptr);