redisソース解析(一)動的文字列sds構造体


1.概要


 Redisは、ANSI C言語を使用してオープンソースで作成され、BSDプロトコルを遵守し、ネットワークをサポートし、メモリベースで持続可能なログ型、Key-Valueデータベースであり、複数の言語のAPIを提供しています.値(value)は、文字列(String)、ハッシュ(Map)、リスト(list)、セット(sets)、およびシーケンスセット(sorted sets)などのタイプであることができるため、通常、データ構造サーバと呼ばれる.
  このライブラリコードは優美で、実現が巧みで、学習に値するため、本編から最新バージョン4.0.11 redisのソースコード実現を学習する.このすべては、最も基礎的なデータ構造sdsから始まります.

2.sds構造


動的文字列sdsの実現は主にsdsである.cとsds.hでは、ヘッダファイルは主に構造体といくつかの基本関数を実現し、ソースファイルには動的文字列に必要な関数が定義される.基本機能はC++STLのvector動的配列と類似している.
次にsds構造体を見てみましょう.sds自体はchar*の別名にすぎず、ソースコードでは以下のように定義されています.
typedef char *sds;

  は、sds動的文字列の長さに応じて、異なるsdshdr構造体を定義し、sdsに対応する情報と最後のbuf(フレキシブル配列を使用して可変長)を格納する.
/*                  
 * Note: sdshdr5 is never used, we just access the flags byte directly.
 * However is here to document the layout of type 5 SDS strings. 
 */
struct __attribute__ ((__packed__)) sdshdr5 {
    unsigned char flags; /* 3 lsb of type, and 5 msb of string length */
    char buf[];
};

struct __attribute__ ((__packed__)) sdshdr8 {
    uint8_t len; /* used */
    uint8_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};

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[];
};

struct __attribute__ ((__packed__)) sdshdr32 {
    uint32_t len; /* used */
    uint32_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};

struct __attribute__ ((__packed__)) sdshdr64 {
    uint64_t len; /* used */
    uint64_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};


  ここで主な違いはlenとallocが採用しているタイプの長さが異なることであり、この2つの変数はそれぞれ現在のbufの長さと割り当てられたメモリサイズを表している.flagsは、現在どのタイプのsdshdrが使用されているかを表すために使用されます.

3.sds基本関数


次はsdsを見てみましょう.hで与えられた基本関数.まず、2つのマクロ定義を理解する必要があります.ソースコードは次のとおりです.
#define SDS_HDR_VAR(T,s) struct sdshdr##T *sh = (void*)((s)-(sizeof(struct sdshdr##T)));
#define SDS_HDR(T,s) ((struct sdshdr##T *)((s)-(sizeof(struct sdshdr##T))))

この2つのマクロ定義を見ていると、少し見覚えがあるのではないでしょうか.原理とcontainer_ofは同じですが、詳細はこちらを参考にしてください.コア思想は,構造体が仮想メモリに連続したアドレス空間(スタック)に格納され,オフセット量計算によりsdsに基づいてsdshdrのヘッダアドレスや他の構造体内変数のアドレスを取得し,それらの値を得ることができる.SDS_HDRはsdshdrのヘッダアドレスを返し、SDS_HDR_VARはsdshdrポインタshを確立し,shに値を付与した.
この2つのマクロ定義を理解すると、以下の関数は簡単です.例えば、sdslen()関数はSDS_です.HDRは、構造体ポインタを取得してlenの値を読み出す.
/*  sdshdr  ,   container_of  */
static inline size_t sdslen(const sds s) {
    unsigned char flags = s[-1];
    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;
        case SDS_TYPE_16:
            return SDS_HDR(16,s)->len;
        case SDS_TYPE_32:
            return SDS_HDR(32,s)->len;
        case SDS_TYPE_64:
            return SDS_HDR(64,s)->len;
    }
    return 0;
}

 sdsavial()関数はalloc-lenの値、すなわち現在の残りの空き領域を返します.
/*s   sdshdr      */
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;
        }
        case SDS_TYPE_16: {
            SDS_HDR_VAR(16,s);
            return sh->alloc - sh->len;
        }
        case SDS_TYPE_32: {
            SDS_HDR_VAR(32,s);
            return sh->alloc - sh->len;
        }
        case SDS_TYPE_64: {
            SDS_HDR_VAR(64,s);
            return sh->alloc - sh->len;
        }
    }
    return 0;
}

 関数sdssetlen()sdshdrの新しい長さを設定する
/*      */
static inline void sdssetlen(sds s, size_t newlen) {
    unsigned char flags = s[-1];
    switch(flags&SDS_TYPE_MASK) {
        case SDS_TYPE_5:
            {
                unsigned char *fp = ((unsigned char*)s)-1;
                *fp = SDS_TYPE_5 | (newlen << SDS_TYPE_BITS);
            }
            break;
        case SDS_TYPE_8:
            SDS_HDR(8,s)->len = newlen;
            break;
        case SDS_TYPE_16:
            SDS_HDR(16,s)->len = newlen;
            break;
        case SDS_TYPE_32:
            SDS_HDR(32,s)->len = newlen;
            break;
        case SDS_TYPE_64:
            SDS_HDR(64,s)->len = newlen;
            break;
    }
}

ジルコニウム関数sdsinclen()は既存のlenに基づいてincを増加させる
/*  Len        */
static inline void sdsinclen(sds s, size_t inc) {
    unsigned char flags = s[-1];
    switch(flags&SDS_TYPE_MASK) {
        case SDS_TYPE_5:
            {
                unsigned char *fp = ((unsigned char*)s)-1;
                unsigned char newlen = SDS_TYPE_5_LEN(flags)+inc;
                *fp = SDS_TYPE_5 | (newlen << SDS_TYPE_BITS);
            }
            break;
        case SDS_TYPE_8:
            SDS_HDR(8,s)->len += inc;
            break;
        case SDS_TYPE_16:
            SDS_HDR(16,s)->len += inc;
            break;
        case SDS_TYPE_32:
            SDS_HDR(32,s)->len += inc;
            break;
        case SDS_TYPE_64:
            SDS_HDR(64,s)->len += inc;
            break;
    }
}

 関数sdsalloc()は、sdshdr割り当ての空間サイズ、すなわちalloc値を返します.
/* alloc    +  
 * sdsalloc() = sdsavail() + sdslen() 
 */
static inline size_t sdsalloc(const sds s) {
    unsigned char flags = s[-1];
    switch(flags&SDS_TYPE_MASK) {
        case SDS_TYPE_5:
            return SDS_TYPE_5_LEN(flags);
        case SDS_TYPE_8:
            return SDS_HDR(8,s)->alloc;
        case SDS_TYPE_16:
            return SDS_HDR(16,s)->alloc;
        case SDS_TYPE_32:
            return SDS_HDR(32,s)->alloc;
        case SDS_TYPE_64:
            return SDS_HDR(64,s)->alloc;
    }
    return 0;
}

 関数sdssetalloc()sdshdrに新しいalloc値を設定する
/*  alloc*/
static inline void sdssetalloc(sds s, size_t newlen) {
    unsigned char flags = s[-1];
    switch(flags&SDS_TYPE_MASK) {
        case SDS_TYPE_5:
            /* Nothing to do, this type has no total allocation info. */
            break;
        case SDS_TYPE_8:
            SDS_HDR(8,s)->alloc = newlen;
            break;
        case SDS_TYPE_16:
            SDS_HDR(16,s)->alloc = newlen;
            break;
        case SDS_TYPE_32:
            SDS_HDR(32,s)->alloc = newlen;
            break;
        case SDS_TYPE_64:
            SDS_HDR(64,s)->alloc = newlen;
            break;
    }
}

4.まとめ


本文はsds動的文字列の構造体と最も基本的ないくつかの操作関数を紹介し,次の文章では「動的」を実現する機能関数をさらに分析する.