国产成人久久,国产91色综合久久免费,欧美日韩激情在线一区二区

SDS(simple dynamic string)是redis提供的字符串的封裝，在redis中也是存在最廣泛的數(shù)據(jù)結(jié)構(gòu)，它也是很多其他數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)，所以才選擇先介紹SDS。 SDS也兼容部分C字符串API(strcmp,strlen)，它如何兼容C字符串我覺得也是有個(gè)很sao的操作，等看完我這篇博客你就明白了。在開始正式內(nèi)容前，我先拋幾個(gè)問題(有些也是面試高頻題)，帶著問題去學(xué)習(xí)也是一種非常好的學(xué)習(xí)方法。

C語言中也算是支持String了，為什么Redis還要自己封裝一個(gè)？
SDS中的D(dynamic)到底是什么含義？
SDS的數(shù)據(jù)結(jié)構(gòu)是啥樣的？為什么要那么設(shè)計(jì)？
SDS是如何兼容C字符串的?

Redis中sds相關(guān)的源碼都在src/sds.c 和src/sds.h中（鏈接可以直接跳轉(zhuǎn)到我中文注釋版redis源碼），其中sds.h中定義了所有SDS的api，當(dāng)然也實(shí)現(xiàn)了部分幾個(gè)api，比如sds長度、sds剩余可用空間……，不急著看代碼，我們先看下sds的數(shù)據(jù)結(jié)構(gòu)，看完后為什么代碼那么寫你就一目了然。

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

redis提供了sdshdr5 sdshdr8 sdshdr16 sdshdr32 sdshdr64這幾種sds的實(shí)現(xiàn)，其中除了sdshdr5比較特殊外，其他幾種sdshdr差不只在于兩個(gè)字段的類型差別。我就拿 sdshdr8和sdshdr16來舉例，其struct定義分別如下。

struct __attribute__ ((__packed__)) sdshdr8 {
    uint8_t len; /* 已使用空間大小 */
    uint8_t alloc; /* 總共可用的字符空間大小，應(yīng)該是實(shí)際buf的大小減1(因?yàn)閏字符串末尾必須是,不計(jì)算在內(nèi)) */
    unsigned char flags; /* 標(biāo)志位，主要是識(shí)別這是sdshdr幾，目前只用了3位，還有5位空余 */
    char buf[];   /* 真正存儲(chǔ)字符串的地方 */
};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[];
};

sdshdr32 sdshdr64也和上面的結(jié)構(gòu)一致，差別只在于len和alloc的數(shù)據(jù)類型不一樣而已。相較于c原生的字符串，sds多了len、alloc、flag三個(gè)字段來存儲(chǔ)一些額外的信息，redis考慮到了字符串拼接時(shí)帶來的巨大損耗，所以每次新建sds的時(shí)候會(huì)預(yù)分配一些空間來應(yīng)對(duì)未來的增長，sds和C string的關(guān)系熟悉JAVA的旁友可能會(huì)決定就好比java中String和StringBuffer的關(guān)系。正是因?yàn)轭A(yù)留空間的機(jī)制，所以redis需要記錄下來已分配和總空間大小，當(dāng)然可用空間可用直接算出來。
Redis源碼剖析之SDS

下一個(gè)問題，為什么redis費(fèi)心費(fèi)力要提供sdshdr5到sdshdr64這五種SDS呢？我覺著這只能說明Redis作者摳內(nèi)存摳到機(jī)制，犧牲了代碼的簡潔性換取了每個(gè)sds省下來的幾個(gè)字節(jié)的內(nèi)存空間。從sds初始化方法sdsnew和sdsnewlen中我們就可以看出，redis在新建sds時(shí)需要傳如初始化長度，然后根據(jù)初始化的長度確定用哪種sdshdr，小于2^8長度的用sdshdr8，這樣len和alloc只占用兩個(gè)字節(jié)，比較短字符串可能非常多，所以節(jié)省下來的內(nèi)存還是非常可觀的，知道了sds的數(shù)據(jù)結(jié)構(gòu)和設(shè)計(jì)原理，sdsnewlen的代碼就非常好懂了，如下：

sds sdsnewlen(const void *init, size_t initlen) {
    void *sh;    sds s;    // 根據(jù)初始化的長度確定用哪種sdshdr    char type = sdsReqType(initlen);
    /* 空字符串大概率之后會(huì)Append，但sdshdr5不適合用來append，所以直接替換成sdshdr8 */    if (type == SDS_TYPE_5 && initlen == 0) type = SDS_TYPE_8;
    int hdrlen = sdsHdrSize(type);
    unsigned char *fp; /* flags pointer. */
    sh = s_malloc(hdrlen+initlen+1);
    if (sh == NULL) return NULL;
    if (init==SDS_NOINIT)
        init = NULL;    else if (!init)
        memset(sh, 0, hdrlen+initlen+1);
    /* 注意：返回的s并不是直接指向sds的指針，而是指向sds中字符串的指針，sds的指針還需要     * 根據(jù)s和hdrlen計(jì)算出來 */    s = (char*)sh+hdrlen;  
    fp = ((unsigned char*)s)-1;
    switch(type) {
        case SDS_TYPE_5: {            *fp = type | (initlen << SDS_TYPE_BITS);
            break;
        }        case SDS_TYPE_8: {            SDS_HDR_VAR(8,s);
            sh->len = initlen;
            sh->alloc = initlen;            *fp = type;
            break;
        }        case SDS_TYPE_16: {            SDS_HDR_VAR(16,s);
            sh->len = initlen;
            sh->alloc = initlen;            *fp = type;
            break;
        }        case SDS_TYPE_32: {            SDS_HDR_VAR(32,s);
            sh->len = initlen;
            sh->alloc = initlen;            *fp = type;
            break;
        }        case SDS_TYPE_64: {            SDS_HDR_VAR(64,s);
            sh->len = initlen;
            sh->alloc = initlen;            *fp = type;
            break;
        }    }    if (initlen && init)
        memcpy(s, init, initlen);    s[initlen] = '';
    return s;
}

SDS的使用

上面代碼中我特意標(biāo)注了一個(gè)注意，sdsnewlen()返回的sds指針并不是直接指向sdshdr的地址，而是直接指向了sdshdr中buf的地址。這樣做有啥好處？好處就是這樣可以兼容c原生字符串。buf其實(shí)就是C 原生字符串+部分空余空間，中間是特殊符號(hào)''隔開，‘’有是標(biāo)識(shí)C字符串末尾的符號(hào)，這樣就實(shí)現(xiàn)了和C原生字符串的兼容，部分C字符串的API也就可以直接使用了。當(dāng)然這也有壞處，這樣就沒法直接拿到len和alloc的具體值了，但是也不是沒有辦法。

當(dāng)我們拿到一個(gè)sds，假設(shè)這個(gè)sds就叫s吧，其實(shí)一開始我們對(duì)這個(gè)sds一無所知，連他是sdshdr幾都不知道，這時(shí)候可以看下s的前面一個(gè)字節(jié)，我們已經(jīng)知道sdshdr的數(shù)據(jù)結(jié)構(gòu)了，前一個(gè)字節(jié)就是flag，根據(jù)flag具體的值我們就可以推斷出s具體是哪個(gè)sdshdr，也可以推斷出sds的真正地址，相應(yīng)的就知道了它的len和alloc，知道了這點(diǎn)，下面這些有點(diǎn)晦澀的代碼就很好理解了。

oldtype = s[-1] & SDS_TYPE_MASK; // SDS_TYPE_MASK = 7 看下s前面一個(gè)字節(jié)(flag)推算出sdshdr的類型。 
// 這個(gè)宏定義直接推算出sdshdr頭部的內(nèi)存地址#define SDS_HDR(T,s) ((struct sdshdr##T *)((s)-(sizeof(struct sdshdr##T))))#define SDS_TYPE_5_LEN(f) ((f)>>SDS_TYPE_BITS)// 獲取sds支持的長度  static inline size_t sdslen(const sds s) {    unsigned char flags = s[-1];  // -1 相當(dāng)于獲取到了sdshdr中的flag字段  
    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;  // 宏替換獲取到sdshdr中的len
        ...        // 省略 SDS_TYPE_16 SDS_TYPE_32的代碼……         case SDS_TYPE_64:            return SDS_HDR(64,s)->len;
    }    return 0;
}// 獲取sds剩余可用空間大小 static inline size_t sdsavail(const sds s) {    unsigned char flags = s[-1];
    switch(flags&SDS_TYPE_MASK) {        case SDS_TYPE_5: {            return 0;
        }        case SDS_TYPE_8: {            SDS_HDR_VAR(8,s);
            return sh->alloc - sh->len;
        }        ...         // 省略 SDS_TYPE_16 SDS_TYPE_32的代碼……         case SDS_TYPE_64: {            SDS_HDR_VAR(64,s);
            return sh->alloc - sh->len;
        }    }    return 0;
}/* 返回sds實(shí)際的起始位置指針 */void *sdsAllocPtr(sds s) {    return (void*) (s-sdsHdrSize(s[-1]));
}

SDS的擴(kuò)容

在做字符串拼接的時(shí)候，sds可能剩余的可用空間不足，這個(gè)時(shí)候需要擴(kuò)容，什么時(shí)候該擴(kuò)容，又該怎么擴(kuò)? 這是不得不考慮的問題。Java中很多數(shù)據(jù)結(jié)構(gòu)都有動(dòng)態(tài)擴(kuò)容的機(jī)制，比如和sds很類似的StringBuffer，HashMap，他們都會(huì)在使用過程中動(dòng)態(tài)判斷是否空間充足，而且基本上都采用了先指數(shù)擴(kuò)容，然后到一定大小限制后才開始線性擴(kuò)容的方式，Redis也不例外，Redis在10241024以內(nèi)都是2倍的方式擴(kuò)容，只要不超出10241024都是先額外申請(qǐng)200%的空間，但一旦總長度超過10241024字節(jié)，那每次最多只會(huì)擴(kuò)容10241024字節(jié)。 Redis中sds擴(kuò)容的代碼是在sdsMakeRoomFor()，可以看到很多字符串變更的API開頭都直接或者間接調(diào)用這個(gè)。和Java中StringBuffer擴(kuò)容不同的是，Redis這里還需要考慮不同字符串長度時(shí)sdshdr類型的變化，具體代碼如下：

// 擴(kuò)大sds的實(shí)際可用空間，以便后續(xù)能拼接更多字符串。 
// 注意：這里實(shí)際不會(huì)改變sds的長度，只是增加了更多可用的空間(buf) sds sdsMakeRoomFor(sds s, size_t addlen) {    void *sh, *newsh;    size_t avail = sdsavail(s);    size_t len, newlen;
    char type, oldtype = s[-1] & SDS_TYPE_MASK; // SDS_TYPE_MASK = 7 
    int hdrlen;    /* 如果有足夠的剩余空間，直接返回 */    if (avail >= addlen) return s;
    len = sdslen(s);
    sh = (char*)s-sdsHdrSize(oldtype);
    newlen = (len+addlen);
    // 在未超出SDS_MAX_PREALLOC前，擴(kuò)容都是按2倍的方式擴(kuò)容，超出后只能遞增 
    if (newlen < SDS_MAX_PREALLOC)  // SDS_MAX_PREALLOC = 1024*1024
        newlen *= 2;
    else
        newlen += SDS_MAX_PREALLOC;    type = sdsReqType(newlen);
    /*  在真正使用過程中不會(huì)用到type5，如果遇到type5直接使用type8*/    if (type == SDS_TYPE_5) type = SDS_TYPE_8;
    hdrlen = sdsHdrSize(type);
    if (oldtype==type) {
        newsh = s_realloc(sh, hdrlen+newlen+1);
        if (newsh == NULL) return NULL;
        s = (char*)newsh+hdrlen;
    } else {
        // 擴(kuò)容其實(shí)就是申請(qǐng)新的空間，然后把舊數(shù)據(jù)挪過去          newsh = s_malloc(hdrlen+newlen+1);
        if (newsh == NULL) return NULL;
        memcpy((char*)newsh+hdrlen, s, len+1);
        s_free(sh);        s = (char*)newsh+hdrlen;
        s[-1] = type;
        sdssetlen(s, len);
    }    sdssetalloc(s, newlen);    return s;
}

常用API

sds.c還有很多源碼我都沒有貼到，其他代碼本質(zhì)上都是圍繞sdshdr數(shù)據(jù)結(jié)構(gòu)和各種字符串操作寫的(基本上都是各種字符串新建、拼接、拷貝、擴(kuò)容……)，只要知道了sds的設(shè)計(jì)原理，相信你也能輕易寫出來，這里我就列一下所有sds相關(guān)的API，對(duì)源碼有興趣的旁友可以移步到src/sds.c，中文注釋版的API列表見src/sds.c

sds sdsnewlen(const void *init, size_t initlen);  // 新建一個(gè)容量為initlen的sds
sds sdsnew(const char *init); // 新建sds，字符串為null，默認(rèn)長度0 
sds sdsempty(void);  // 新建空字符“” 
sds sdsdup(const sds s); // 根據(jù)s的實(shí)際長度創(chuàng)建新的sds，目的是降低內(nèi)存的占用
void sdsfree(sds s); // 釋放sds 
sds sdsgrowzero(sds s, size_t len); // 把sds增長到指定的長度，增長出來的新的空間用0填充 
sds sdscatlen(sds s, const void *t, size_t len); // 在sds上拼接字符串t的指定長度部分 
sds sdscat(sds s, const char *t);  // 把字符串t拼接到sds上 
sds sdscatsds(sds s, const sds t); // 把兩個(gè)sds拼接在一起  
sds sdscpylen(sds s, const char *t, size_t len); //  把字符串t指定長度的部分拷貝到sds上 
sds sdscpy(sds s, const char *t); // 把字符串t拷貝到sds上 
sds sdscatvprintf(sds s, const char *fmt, va_list ap); // 把用printf格式化后的字符拼接到sds上 
sds sdscatfmt(sds s, char const *fmt, ...);   // 將多個(gè)參數(shù)格式化成一個(gè)字符串后拼接到sds上 
sds sdstrim(sds s, const char *cset);  // 在sds中移除開頭或者末尾在cset中的字符  
void sdsrange(sds s, ssize_t start, ssize_t end);  // 截取sds的子串 
void sdsupdatelen(sds s); // 更新sds字符串的長度 
void sdsclear(sds s);  // 清空sds中的內(nèi)容，但不釋放空間 
int sdscmp(const sds s1, const sds s2);  // sds字符串比較大小 
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); // 字符串轉(zhuǎn)小寫
void sdstoupper(sds s);  // 字符串轉(zhuǎn)大寫
sds sdsfromlonglong(long long value);  // 把一個(gè)long long型的數(shù)轉(zhuǎn)成sds  
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); // 把字符串?dāng)?shù)組按指定的分隔符拼接起來
sds sdsjoinsds(sds *argv, int argc, const char *sep, size_t seplen); // 把sds數(shù)組按指定的分隔符拼接起來
/* sds底層api */
sds sdsMakeRoomFor(sds s, size_t addlen);  // sds擴(kuò)容
void sdsIncrLen(sds s, ssize_t incr); // 擴(kuò)容指定長度
sds sdsRemoveFreeSpace(sds s); // 釋放sds占用的多余空間
size_t sdsAllocSize(sds s); // 返回sds總共占用的內(nèi)存大小
void *sdsAllocPtr(sds s); // 返回sds實(shí)際的起始位置指針
void *sds_malloc(size_t size); // 為sds分配空間 
void *sds_realloc(void *ptr, size_t size); // 
void sds_free(void *ptr);  // 釋放sds空間

結(jié)語

回到開篇的幾個(gè)問題，相信看完上面的內(nèi)容后你都能回答上來了，如果回答不上來那就再多看兩遍，本博客+源碼搭配服用效果更佳。

為了控制博客篇幅，這里只講解了核心代碼，很多API的源碼我都沒有貼上來(畢竟太多)，有興趣的同學(xué)可以再看下源碼 https://github.com/xindoo/redis/。

本文是Redis源碼剖析系列博文，同時(shí)也有與之對(duì)應(yīng)的Redis中文注釋版，有想深入學(xué)習(xí)Redis的同學(xué)，歡迎star和關(guān)注。 Redis中文注解版?zhèn)}庫：https://github.com/xindoo/redis
Redis源碼剖析專欄：https://zxs.io/s/1h
本文來自https://blog.csdn.net/xindoo