Redis 數(shù)據(jù)結(jié)構(gòu) sds

sds 結(jié)構(gòu)簡介

sds 被稱為是 Hacking String. hack 的地方就在 sds 保存了字符串的長度以及剩余空間。sds 的實現(xiàn)在 sds.c 中。

sds 頭部的實現(xiàn)：

struct sdshdr {
   int len;
   int free;
   char buf[];
};

hacking sds

倘若使用指針即char *buf，分配內(nèi)存需要量兩個步驟：一次分配結(jié)構(gòu)體，一次分配char *buf，在是否內(nèi)存的時候也需要釋放兩次內(nèi)存：一次為char *buf，一次為結(jié)構(gòu)體內(nèi)存。而用長度為 0 的字符數(shù)組可以將分配和釋放內(nèi)存的次數(shù)都降低為 1 次，從而簡化內(nèi)存的管理。

http://wiki.jikexueyuan.com/project/redis/images/redis8.png" alt="" />

另外，長度為 0 的數(shù)組即 char buf[] 不占用內(nèi)存：

// char buf[] 的情況
struct sdshdr s;
printf("%d",sizeof(s));
// 8

// char *buf 的情況
struct sdshdr s;
printf("%d",sizeof(s));
// 12

Redis 中涉及較多的字符串操作，譬如 APPEND 命令。相比普通的字符串，sds 獲取字符串的長度以及剩余空間的復(fù)雜度都是 O(1)，前者需要 O(N)。

// 返回sdshdr.len
static inline size_t sdslen(const sds s) {
    struct sdshdr *sh = (void*)(s-(sizeof(struct sdshdr)));
    return sh->len;
}

// 返回sdshdr.free
static inline size_t sdsavail(const sds s) {
    struct sdshdr *sh = (void*)(s-(sizeof(struct sdshdr)));
    return sh->free;
}

sds.c 中還實現(xiàn)了針對 sds 的字符串操作函數(shù)，譬如分配，追加，釋放等，這些函數(shù)具體詳細(xì)的實現(xiàn)讀者可以自行剖析。