redis下位データ構造のintset

最近、redisのソースコードでredisを学びたいです.普段の仕事ではあまり使われていませんが、redisに興味があります.結局、性能はいいです.redisはオープンソースのプロジェクトで、ソースコードを通じてredisを理解することができます.私は后で自分の学习を通じて、redisのソースコードについての招待状を书きます.投稿の主な内容は、ソースコードを詳細に説明することなく、コード設計を分析することです.間違ったところがあれば、指摘してください.ソースコードはreids 3.0.3バージョンです.
intset
一、intsetデータ構造
intsetは、整数セットを格納するためのデータ構造である.setの特徴は重複要素がなく、要素が無秩序であることです.しかしredisのintsetは要素が秩序化されたデータ構造である.
まずintsetの定義を見てみましょう.

typedef struct intset {
    uint32_t encoding;  //      
    uint32_t length;    //intset  ，    
    int8_t contents[];  //     
} intset;

まずintsetの関連操作と結びつけて、intsetの特徴について話します.以下、intsetの動作特徴を部分コードで説明する.
二、inetsetが提供する関連操作関数
intset対外暴露の関数:

intset *intsetNew(void);    //      intset
intset *intsetAdd(intset *is, int64_t value, uint8_t *success); //    
intset *intsetRemove(intset *is, int64_t value, int *success);  //    
uint8_t intsetFind(intset *is, int64_t value);  //    
int64_t intsetRandom(intset *is);   //      
uint8_t intsetGet(intset *is, uint32_t pos, int64_t *value);    //         
uint32_t intsetLen(intset *is); //  intset    
size_t intsetBlobLen(intset *is);   //  intset      

1.整数符号化

/* Note that these encodings are ordered, so:
 * INTSET_ENC_INT16  INT32_MAX)
        return INTSET_ENC_INT64;
    else if (v  INT16_MAX)
        return INTSET_ENC_INT32;
    else
        return INTSET_ENC_INT16;
}

int 16_をサポートt, int32_t, int64_t 4種類のストレージ.各タイプの値は、INTSET_を満たすように定義された空間サイズです.ENC_INT16 < INTSET_ENC_INT32 < INTSET_ENC_INT 64は、後のタイプの値ドメインが前の値ドメインを含む.
注意:intsetValueEncoding関数はstaticと宣言され、ファイル内部の関数であり、外部は表示されません.
2.指定した場所の要素を取得する

/* Return the value at pos, given an encoding. */
static int64_t _intsetGetEncoded(intset *is, int pos, uint8_t enc) {
    int64_t v64;
    int32_t v32;
    int16_t v16;
    //                   
    //intset         ，                      
    if (enc == INTSET_ENC_INT64) {
        memcpy(&v64,((int64_t*)is->contents)+pos,sizeof(v64));
        memrev64ifbe(&v64);
        return v64;
    } else if (enc == INTSET_ENC_INT32) {
        memcpy(&v32,((int32_t*)is->contents)+pos,sizeof(v32));
        memrev32ifbe(&v32);
        return v32;
    } else {
        memcpy(&v16,((int16_t*)is->contents)+pos,sizeof(v16));
        memrev16ifbe(&v16);
        return v16;
    }
}
/* Return the value at pos, using the configured encoding. */
static int64_t _intsetGet(intset *is, int pos) {
    // intset           
    return _intsetGetEncoded(is,pos,intrev32ifbe(is->encoding));
}

intset内部は整数を符号化して記憶するが、外部に露出するのはint 64_であるtタイプ.
内部ではデータを符号化して記憶することで、記憶スペースを節約することができる.
intsetはスモールエンドストレージなので、データの読み取りや書き込みには、サイズエンド変換が必要です.しかし、intsetは内部のデータ構造にすぎないと思っているので、ハードな要求をせずにサイズ端で保存することができます.
3.要素の挿入(intset再編成を引き起こす可能性がある)

/* Insert an integer in the intset */
intset *intsetAdd(intset *is, int64_t value, uint8_t *success) {
    uint8_t valenc = _intsetValueEncoding(value);
    uint32_t pos;
    if (success) *success = 1;
    /* Upgrade encoding if necessary. If we need to upgrade, we know that
     * this value should be either appended (if > 0) or prepended (if  intrev32ifbe(is->encoding)) {
        //  value        intset       ，      intset ，
        //    ，      intset     。  intset      ，
        //                  length+1   ，
        //     intsetUpgradeAndAdd  
        /* This always succeeds, so we don't need to curry *success. */
        return intsetUpgradeAndAdd(is,value);
    } else {
        /* Abort if the value is already present in the set.
         * This call will populate "pos" with the right position to insert
         * the value when it cannot be found. */
        //        ，   
        if (intsetSearch(is,value,&pos)) {
            if (success) *success = 0;
            return is;
        }
        //          ，                     。
        is = intsetResize(is,intrev32ifbe(is->length)+1);
        //         ，     
        if (pos length)) intsetMoveTail(is,pos,pos+1);   
    }
    _intsetSet(is,pos,value);
    is->length = intrev32ifbe(intrev32ifbe(is->length)+1);
    return is;
}

なお、挿入されたデータの符号化タイプが現在のintsetの符号化タイプよりも大きい場合、新しい要素を格納できるようにintsetはタイプ拡張を行う必要がある.拡張タイプはintsetの中にあるすべての要素を新しいタイプに拡張します.これによりintsetを再編成する必要があります.元の要素の個数が多いと再編成に少し時間がかかります.しかしintsetは最大2回の再編を行う.再編成が可能であるため、intsetが大量の要素を格納するのに適していない理由の一つでもある.redisでintset要素のデフォルト構成個数が512に達すると、別のデータ構造で格納されます.
4.エレメントの検索

/* Search for the position of "value". Return 1 when the value was found and
 * sets "pos" to the position of the value within the intset. Return 0 when
 * the value is not present in the intset and sets "pos" to the position
 * where "value" can be inserted. */
static uint8_t intsetSearch(intset *is, int64_t value, uint32_t *pos) {
    int min = 0, max = intrev32ifbe(is->length)-1, mid = -1;
    int64_t cur = -1;
    /* The value can never be found when the set is empty */
    if (intrev32ifbe(is->length) == 0) {
        if (pos) *pos = 0;
        return 0;
    } else {
        /* Check for the case where we know we cannot find the value,
         * but do know the insert position. */
        if (value > _intsetGet(is,intrev32ifbe(is->length)-1)) {
            if (pos) *pos = intrev32ifbe(is->length);
            return 0;
        } else if (value = min) {
        mid = ((unsigned int)min + (unsigned int)max) >> 1;
        cur = _intsetGet(is,mid);
        if (value > cur) {
            min = mid+1;
        } else if (value encoding) && intsetSearch(is,value,NULL);
}

検索時間の複雑さはO(logn)であり,Nの比較が小さい場合には許容できるが,Nが大きい場合,例えば1000000の場合,比較回数は20回に達する可能性がある.
5.要素の削除(intset再編成は起こらない)

/* Delete integer from intset */
intset *intsetRemove(intset *is, int64_t value, int *success) {
    uint8_t valenc = _intsetValueEncoding(value);
    uint32_t pos;
    if (success) *success = 0;
    if (valenc <= intrev32ifbe(is->encoding) && intsetSearch(is,value,&pos)) {
        uint32_t len = intrev32ifbe(is->length);
        /* We know we can delete */
        if (success) *success = 1;
        /* Overwrite value with tail and update length */
        if (pos length = intrev32ifbe(len-1);
    }
    return is;
}

intsetは、要素を削除する際に要素のデータ型チェックを行わず、intsetの整数型を降格させ、intsetもこのような能力を別途提供しない.理由は、a.すべての要素をスキャンして、現在符号化タイプのダウングレードが必要かどうかを判断する必要があるからだと思います.b.ダウングレード符号化タイプは再編成を引き起こす.c.ダウングレード後にアップグレードが必要になる場合がありますが、不幸にも頻繁にアップグレードダウングレード再編成が発生した場合、パフォーマンスが不安定です.
挿入削除関数と組み合わせてintsetResizeを用い,zreallocを用いてメモリ領域の増減を行った.スペースを大きくするときは、新しいスペースを再割り当てするか、既存のスペースの最後に拡張します.スペースを小さくするときは、元のスペースを最後に小さくするだけです.このような方法では、メモリの破片が発生しにくい.
三、特徴(長所と短所は比較しなければならないが、ここでは比較していないため、長所と短所は明らかではないので、ここでは特徴だけを列挙した):
1.メモリ要素が緊密で、空間利用率が高く、頻繁に挿入削除することによってメモリフラグメントが発生しにくい配列.
2.整数符号化をサポートし、intset内のすべてのデータ要素の記憶タイプが一致している.新しくデータを挿入する場合、データのタイプが現在のintsetのデータ型より大きい場合、格納されている整数型を拡大することができます(ただし、intsetは符号化タイプを縮小する能力を提供しません).一定のプログラムでスペースを節約できますが、すべてのアクセスはタイプを考慮し、コードの複雑さを高める必要があります.
3.要素の個数を記録する長さフィールドがあり、要素の個数を取る操作は定数である.
4.秩序配列、検索要素O(logn)
5.要素を挿入する場合、N個以上の要素に移動する必要がある場合もあれば、符号化タイプをアップグレードし、intsetを再編成する場合もある.この2つの特徴のため、intsetは大量の要素を頻繁に挿入し、格納するのに適していない.
6.エレメントを削除する場合、N-1個以上のエレメントに移動する必要がある場合があります.
7.encoding、length、およびデータ要素を含むデータを小端形式で格納する.