redis文字列実装sds

sds.c/sds.h
1.実現
sdsにおける文字列の実現はstringを包装するものである
定義:

/*
 *     ，     sdshdr   buf   
 */
typedef char *sds;

/*
 *           
 */
struct sdshdr {
    
    // buf          
    int len;

    // buf           
    int free;

    //     
    char buf[];
};

sizeof(struct sdshdr))は実際にはsds構造体のサイズであり、char buf[]はflexible array member(柔軟なアレイメンバーポインタ)で構造体のサイズを計算する場合は計上されず、文字列とsdsタイプの切り替えは以下の通りである.
const sds s;//charポインタを定義しbuf[]ヘッダアドレスを指す
struct sdshdr *sh = (void*)(s-(sizeof(struct sdshdr)));//文字列をsdsに変換できました
文字列としての初期アドレスs−構造体の大きさに相当し、構造体shの位置である
sh->lenは文字列の長さを指し、sh->freeはbufに残っている空き空間の長さを指し、時間複雑度はいずれもO(1)c文字列については「0」を末尾とする文字列遍歴取得長であるため時間複雑度O(N)、sdsはこれを判断基準としないが、c文字列と互換性があるため、buf配列には最後にこの「0」が加わる
2.メモリの割り当て
空間の事前割り当て:(1)現在free空間は十分で、直接戻る;(2)freeスペースが足りず、新規1 M未満、拡張スペースnewlen*2;(3)新たに1 Mより大きく、拡張空間+1 M

/*
 *   sds   buf        ，         ，
 * buf      addlen + 1        
 * （    1      \0    ）
 *
 *    
 *  sds ：           sds
 *               NULL
 *
 *    
 *  T = O(N)
 */
sds sdsMakeRoomFor(sds s, size_t addlen) {

    struct sdshdr *sh, *newsh;

    //    s          
    size_t free = sdsavail(s);

    size_t len, newlen;

    // s            ，       ，    
    if (free >= addlen) return s;

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

    // s        
    newlen = (len+addlen);

    //      ，  s           
    if (newlen < SDS_MAX_PREALLOC) //SDS_MAX_PREALLOC = 1024*1024
        //         SDS_MAX_PREALLOC 
        //                 
        newlen *= 2;
    else
        //   ，            SDS_MAX_PREALLOC
        newlen += SDS_MAX_PREALLOC;
    // T = O(N)
    newsh = zrealloc(sh, sizeof(struct sdshdr)+newlen+1);

    //     ，    ，  
    if (newsh == NULL) return NULL;

    //    sds      
    newsh->free = newlen - len;

    //    sds
    return newsh->buf;
}

不活性スペースの解放:
不活性空間解放とは、1つのsdsオブジェクトを短縮する場合、buf配列を直接ターゲット配列の長さに短縮するのではなく、sdsオブジェクトのlen属性の値のみを変更し、配列の余分な部分をfree属性に保存することで、後で可能なsdsオブジェクトの成長操作に空間を再割り当てする必要がないことを保証することを意味する.

/*
 *   sds         ，     cset        
 *
 *    sdsstrim(xxyyabcyyxy, "xy")     "abc"
 *
 *    ：
 *  T = O(M*N)，M   SDS   ， N   cset   。
 */
sds sdstrim(sds s, const char *cset) {
    struct sdshdr *sh = (void*) (s-(sizeof(struct sdshdr)));
    char *start, *end, *sp, *ep;
    size_t len;

    //        
    sp = start = s;
    ep = end = s+sdslen(s)-1;

    //   , T = O(N^2)
    while(sp <= end && strchr(cset, *sp)) sp++;
    while(ep > start && strchr(cset, *ep)) ep--;

    //    trim             
    len = (sp > ep) ? 0 : ((ep-sp)+1);
    
    //      ，       
    // T = O(N)
    if (sh->buf != sp) memmove(sh->buf, sp, len);

    //      
    sh->buf[len] = '\0';

    //     
    sh->free = sh->free+(sh->len-len);
    sh->len = len;

    //        sds
    return s;
}