[redis設計與實作][1]基本資料結構——sds

sds(simple dynamic string)：對c字元串的封裝，可修改、可自動伸縮的字元串實作。redis預設的字元串實作。

sds定義：（sds.h）

[cce lang=”c”]

struct sdshdr {

unsigned int len;

unsigned int free;

char buf[];

};

[/cce]

與c字元串的差別：

* 常數複雜度擷取字元串長度（字元串長度已經記錄在結構體中）

* 杜絕緩沖區溢出（每次操作前都會檢查空間是否充足，自動擴張和收縮）

* 減少修改字元串帶來的記憶體重配置設定次數：

*

* 空間預配置設定（提前預留白間）

* 惰性空間釋放（釋放的空間暫時保留，防止擴張）

* 二進制安全（不采用\0表示結束）

* 相容部分c字元串函數（buf數組多儲存了一個\0，用于相容部分c字元串函數）

api：

typedef char *sds;

建立一個字元串：sds sdsnew(const char *init);

sds sdsnew(const char *init) {

size_t initlen = (init == null) ? 0 : strlen(init);

return sdsnewlen(init, initlen);

}

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

struct sdshdr *sh;

//根據sdshdr結構配置設定記憶體，多一個用來放\0

if (init) {

sh = zmalloc(sizeof(struct sdshdr)+initlen+1);

} else {

sh = zcalloc(sizeof(struct sdshdr)+initlen+1);

if (sh == null) return null;

sh->len = initlen;

sh->free = 0;

//初始字元串不為null，複制過去，然後最後補上\0

if (initlen && init)

memcpy(sh->buf, init, initlen);

sh->buf[initlen] = ‘\0′;

return (char*)sh->buf;

拼接字元串：sds sdscat(sds s, const char *t);

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

return sdscatlen(s, t, strlen(t));

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

size_t curlen = sdslen(s);

s = sdsmakeroomfor(s,len);

if (s == null) return null;

sh = (void*) (s-(sizeof(struct sdshdr)));

memcpy(s+curlen, t, len);

sh->len = curlen+len;

sh->free = sh->free-len;

s[curlen+len] = ‘\0′;

return s;

sds sdsmakeroomfor(sds s, size_t addlen) {

struct sdshdr *sh, *newsh;

size_t free = sdsavail(s);

size_t len, newlen;

//仍然有空閑，直接傳回

if (free >= addlen) return s;

len = sdslen(s);

newlen = (len+addlen);

//新的空間比最大配置設定空間小，擴容兩倍

//#define sds_max_prealloc (1024*1024)

if (newlen < sds_max_prealloc) newlen *= 2; else newlen += sds_max_prealloc; //重新配置設定空間：sdshdr+字元串長度+1(\0) newsh = zrealloc(sh, sizeof(struct sdshdr)+newlen+1); if (newsh == null) return null; newsh->free = newlen – len;

return newsh->buf;

static inline size_t sdsavail(const sds s) {

struct sdshdr *sh = (void*)(s-(sizeof(struct sdshdr)));

return sh->free;

轉載自：https://coolex.info/blog/434.html