[redis]SDSとチェーンテーブル

一、SDS
1、SDS構造体
redis3.2以前:bufのバイト数にかかわらず4バイトのlenで長さを格納し、短い文字列だけを格納する利点に空間を浪費する.例えばnameのみを格納すると、len=4は1バイト8ビットで表すことができる.

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

redis3.2以降:

struct __attribute__ ((__packed__)) sdshdr8 {
    uint8_t len; //      
    uint8_t alloc; //     
    unsigned char flags; //         SDS   3   ， 5   
    char buf[]; 
};
//........16、32、64

_attribute_ ((_packed_)) キーワードはバイトの位置合わせを解除するためです

struct test1 {
 char c;
 int i;
};

struct __attribute__ ((__packed__)) test2 {
 char c;
 int i;
};

int main()
{
 cout << "size of test1:" << sizeof(struct test1) << endl; //5
 cout << "size of test2:" << sizeof(struct test2) << endl; //8
}

これらの構造は、オフセットによってアクセスするchar[]内に存在することに注意してください.
graph TB subgraph header-->buf end
2、重要な関数の解析
sdsReqType
タイプの決定:sdsReqTypeは、入力されたchar[]の長さに基づいて、どのタイプのSDS構造体で記述すべきかという欠点を有する.

static inline char sdsReqType(size_t string_size) {
    if (string_size < 1<<5)
        return SDS_TYPE_5;
    if (string_size < 1<<8) //8         0-256
        return SDS_TYPE_8;
    if (string_size < 1<<16) //16  
        return SDS_TYPE_16;
#if (LONG_MAX == LLONG_MAX)
    if (string_size < 1ll<<32)
        return SDS_TYPE_32;
    return SDS_TYPE_64;
#else
    return SDS_TYPE_32;
#endif
}

sdsnewlen
長さ構造化char配列に基づいてstr自体の長さ+headの長さの配列を作成し、sdsnewはこれを呼び出してsdsバイト配列を作成します.

sds sdsnewlen(const void *init, size_t initlen) {
    void *sh; //  sds header      
    sds s; //char* s
    char type = sdsReqType(initlen); //  str     SDS header  
    if (type == SDS_TYPE_5 && initlen == 0) type = SDS_TYPE_8;
    int hdrlen = sdsHdrSize(type); //header   
    unsigned char *fp; //    

    sh = s_malloc(hdrlen+initlen+1); //   str  +header       
    ...
    memset(sh, 0, hdrlen+initlen+1); //     
    s = (char*)sh+hdrlen; //   header   buf     
    fp = ((unsigned char*)s)-1; //   header      sds header  
    switch(type) {
       ....
        case SDS_TYPE_8: {
//#define SDS_HDR_VAR(T,s) struct sdshdr##T *sh = (void*)((s)-(sizeof(struct sdshdr##T)));  
  //sh  header       s  buf        sh   header    
        SDS_HDR_VAR(8,s); //struct sdshdr8* sh = (void*)(s-sizeof(header))
        sh->len = initlen; //    
        sh->alloc = initlen; 
        *fp = type;//      
        break;
       }
       ......
    }
    if (initlen && init)
        memcpy(s, init, initlen); // str     buf 
    s[initlen] = '\0';
    return s;
}

sdslen、sdsavail
使用されているスペースと使用されていないスペースを返します.**ヘッダタイプに応じてポインタを変換し、直接sh->lenとsh->alloc-sh->len**で求める
sdscat、sdscatlen、sdsMakeRoomFor tをsに接合する、

sds sdscatsds(sds s, const sds t) {
    return sdscatlen(s, t, sdslen(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;
    memcpy(s+curlen, t, len); //  copy
    sdssetlen(s, curlen+len); //      
    s[curlen+len] = '\0';
    return s;
}

sdsMakeRoomForは空間が十分であることを保証するためであり、十分に拡張しなければ、次はnewlenのコアコードであり、必要な長さよりも拡張し、複数回の拡張を防止する.事前配分を体現している
拡張は時間のかかる操作です

    if (avail >= addlen) return s;

    len = sdslen(s);
    sh = (char*)s-sdsHdrSize(oldtype);
    newlen = (len+addlen);
    if (newlen < SDS_MAX_PREALLOC) //#define SDS_MAX_PREALLOC (1024*1024)
        newlen *= 2;
    else
        newlen += SDS_MAX_PREALLOC;

sdstrim
csetの中でsで現れた削除、この関数は不活性な解放を体現して、空間を縮小しないで、lenだけを変えて、同時にcとの互換性を体現して、システムstrings関数でsdsを操作することができます

sds sdstrim(sds s, const char *cset) {
    char *start, *end, *sp, *ep;
    size_t len;

    sp = start = s;
    ep = end = s+sdslen(s)-1;
    while(sp <= end && strchr(cset, *sp)) sp++;
    while(ep > sp && strchr(cset, *ep)) ep--;
    len = (sp > ep) ? 0 : ((ep-sp)+1);
    if (s != sp) memmove(s, sp, len);
    s[len] = '\0';
    sdssetlen(s,len);
    return s;
}

3、メリット
A.長さの入手が便利
c文字列取得長さはchar配列,O(n)を便利にする必要があり,SDS構造体は長さを記録し,char配列を必要とせずに長さを知ることができる.
B.オーバーフロー防止
char配列はどれだけのスペースがあるか分からず、2つの文字列がつながっている間にオーバーフローする可能性がありますが、SDSは未使用のスペースを記録しており、拡張を効果的に割り当て、オーバーフローを防ぐことができます.
C.メモリの割り当てが便利で、使用効率が高い
従来のcのchar配列では、スペースが不足している場合は、手動で容量を拡張し、元のデータをコピーし、遮断する場合は、メモリの漏洩を防ぐためにスペースを削減する必要があります.しかし、SDSは、スペースの事前割り当て、不活性な解放などのポリシーを実行して、メモリを効率的に使用することができます.

空間事前分配:十分な空間を予め分配し、拡張回数

を減少する.

不活性解放SDSはfree未割当て空間フィールドを記録しているため、文字列を切断する際に直ちに要素をコピーして縮小する必要はなく、free数値を直接増加させ、lenを減少させ、その後文字列を増加させるにはlenだけ増加させ、freeを減少させ、書き込みを上書きすればよい.(free = alloc-len)

D.互換C
SDSは2つのフィールドを追加しただけで、データはchar[]bufに存在するため、cに内蔵された文字列処理関数を使用してSDSの下位バイト配列を処理することができます.

typedef char *sds;

だから文字列を処理するAPIにはchar*が入って文字列を処理するだけです.スペースが十分かどうかは、追加の情報で説明されています.
二、チェーン時計
チェーン時計なら参考にしてくださいhttps://www.cnblogs.com/biningooginind/p/12553163.html
redisのチェーンテーブル操作を基本的に参照します.
1、構造体

typedef struct listNode {
    struct listNode *prev;
    struct listNode *next;
    void *value; //void*               
} listNode;

2、特徴
チェーンテーブルの特徴:

削除、O(1)

挿入

遍歴アクセスO(n)

にはheadとtailポインタがあり、最後の要素へのアクセスの複雑さをO(1)

に低減する.

はlenの長さを持っていて、チェーンテーブルの長さ

を簡単に知ることができます.

デュアルチェーンテーブル構造で、前後の遍歴が便利

無環

マルチステート:データはvoidで指向され、任意のタイプのデータを格納することができ、各タイプにチェーンテーブル*

を書く必要はありません.

反復モード、チェーンテーブルに反復器があり、ノード

を巡回するのに便利です.

typedef struct listIter {
    listNode *next; //     
    int direction; //     forward or backward
} listIter;