Redisソースプロファイリング--両端チェーンテーブルSdlist

20359 ワード
Redis C-C++
>私のブログに引き続き注目してください:https://zcheng.ren今日、Redisの基本的なデータ構造である両端チェーンテーブルを分析し、その定義と実現は主にsdlistである.hとsdlist.cファイルにあります.主にリストキーの実装、トランザクションモジュールの入力コマンドとサーバモジュールの保存、サブスクリプションモジュールの複数のクライアントの保存などに使用されます.

sdlistのデータ構造


Redisは、両端チェーンテーブルの各ノードについて、以下のような構造体を定義する.
//       
typedef struct listNode {
    struct listNode *prev;  //        
    struct listNode *next;  //        
    void *value; //    
} listNode;
は、一般的な両端チェーンテーブルと異なり、チェーンテーブルノードの構造体を定義した後、チェーンテーブルの構造体を定義し、チェーンテーブルノードの管理を容易にするために使用され、その構造体は以下のように定義される.
typedef struct list {
    listNode *head;  //        
    listNode *tail;  //        
    void *(*dup)(void *ptr); //           
    void (*free)(void *ptr); //           
    int (*match)(void *ptr, void *key); //           
    unsigned long len; //     
} list;
Redisは、チェーンテーブルを実装する際に、両端無ループチェーンテーブルとして定義され、その概略図は以下の通りである.
さらに,Redisはその構造体に一連のマクロ定義関数を提供し,その構造体パラメータの操作を容易にする.
#define listLength(l) ((l)->len)  //   list  
#define listFirst(l) ((l)->head)  //   list     
#define listLast(l) ((l)->tail)   //   list     
#define listPrevNode(n) ((n)->prev)  //            
#define listNextNode(n) ((n)->next)  //            
#define listNodeValue(n) ((n)->value) //         

#define listSetDupMethod(l,m) ((l)->dup = (m))  //          
#define listSetFreeMethod(l,m) ((l)->free = (m))  //          
#define listSetMatchMethod(l,m) ((l)->match = (m))  //          

#define listGetDupMethod(l) ((l)->dup) //          
#define listGetFree(l) ((l)->free)  //          
#define listGetMatchMethod(l) ((l)->match)  //

sdlist反復構造


Redisはsdlistのために反復器構造を定義し,正と逆の順序でlist構造にアクセスできる.
typedef struct listIter {
    listNode *next; //        
    int direction; //     ，     
} listIter;

Directionパラメータの場合、Redisは2つのマクロ定義を提供します.
#define AL_START_HEAD 0  //     
#define AL_START_TAIL 1  //

sdlist基本操作


sdlist作成


sdlistはlistCreate関数を提供し、空のチェーンテーブルを作成します.
list *listCreate(void)
{
    struct list *list; //         

    if ((list = zmalloc(sizeof(*list))) == NULL) //     
        return NULL; 
    list->head = list->tail = NULL;  //               
    list->len = 0;  //     
    list->dup = NULL;    //           
    list->free = NULL;   //           
    list->match = NULL;  //           
    return list;
}

sdlist解放


sdlistはリストリストリスト関数を提供し、チェーンテーブル全体を解放します.
void listRelease(list *list)
{
    unsigned long len;
    listNode *current, *next;

    current = list->head;
    len = list->len;
    while(len--) {
        next = current->next;
        //             ，    
        if (list->free) list->free(current->value);
        zfree(current);  //       
        current = next;
    }
    zfree(list);  //      
}

ノードの挿入


sdlistはlistにノードを挿入する機能を完了するために3つの関数を提供します.

ノードを頭に挿入

//     list         
list *listAddNodeHead(list *list, void *value)
{
    listNode *node;

    if ((node = zmalloc(sizeof(*node))) == NULL)
        return NULL;
    node->value = value;
    if (list->len == 0) { //       
        list->head = list->tail = node;
        node->prev = node->next = NULL;
    } else {  //       
        node->prev = NULL;
        node->next = list->head;
        list->head->prev = node;
        list->head = node;
    }
    list->len++;  //   +1
    return list;
}

末尾へのノードの追加

//       list         
list *listAddNodeTail(list *list, void *value)
{
    listNode *node;

    if ((node = zmalloc(sizeof(*node))) == NULL)
        return NULL;
    node->value = value;
    if (list->len == 0) { //       
        list->head = list->tail = node;
        node->prev = node->next = NULL;
    } else {  //       
        node->prev = list->tail;
        node->next = NULL;
        list->tail->next = node;
        list->tail = node;
    }
    list->len++;  //   +1
    return list;
}

ノードを任意の場所に挿入

//          
//   ，old_node     
//      value       
//      after 0     old_node  ， 1     old_node  
list *listInsertNode(list *list, listNode *old_node, void *value, int after) {
    listNode *node;

    if ((node = zmalloc(sizeof(*node))) == NULL)
        return NULL;
    node->value = value;
    if (after) { //     
        node->prev = old_node;
        node->next = old_node->next;
        //   old_node          tail
        if (list->tail == old_node) {
            list->tail = node;
        }
    } else {  //     
        node->next = old_node;
        node->prev = old_node->prev;
        //   old_node          head
        if (list->head == old_node) {
            list->head = node;
        }
    }
    if (node->prev != NULL) {
        node->prev->next = node;
    }
    if (node->next != NULL) {
        node->next->prev = node;
    }
    list->len++;
    return list;
}

ノードの削除

void listDelNode(list *list, listNode *node)
{
    if (node->prev) //          
        node->prev->next = node->next;
    else //             head   
        list->head = node->next;
    if (node->next)  //          
        node->next->prev = node->prev;
    else //             tail   
        list->tail = node->prev;
    if (list->free) list->free(node->value); //      
    zfree(node);  //     
    list->len--;
}

反復器関連アクション


sdlistはその反復器にいくつかの操作を提供し、反復器の取得、反復器の解放、反復器のリセット、次の反復器の取得などの操作を完了するために使用され、具体的なソースコードは以下の分析を参照してください.

反復の取得

listIter *listGetIterator(list *list, int direction)
{
    listIter *iter;  //      

    if ((iter = zmalloc(sizeof(*iter))) == NULL) return NULL;
    //           iter
    if (direction == AL_START_HEAD)
        iter->next = list->head;
    else
        iter->next = list->tail;
    iter->direction = direction;
    return iter;
}

かいほう反復器

void listReleaseIterator(listIter *iter) {
    zfree(iter); //     zfree   
}

反復のリセット


リセット反復器は2種類に分けられます.1つは順方向反復器をリセットすることです.1つは逆方向反復器にリセットすることです.
//         
void listRewind(list *list, listIter *li) {
    li->next = list->head;
    li->direction = AL_START_HEAD;
}
//         
void listRewindTail(list *list, listIter *li) {
    li->next = list->tail;
    li->direction = AL_START_TAIL;
}

次の反復を取得

//   direction           
listNode *listNext(listIter *iter)
{
    listNode *current = iter->next;

    if (current != NULL) {
        if (iter->direction == AL_START_HEAD)
            iter->next = current->next;
        else
            iter->next = current->prev;
    }
    return current;
}

チェーンテーブルコピー関数


sdlistはリストDup関数を提供し、チェーンテーブル全体をコピーします.
list *listDup(list *orig)
{
    list *copy;
    listIter iter;
    listNode *node;

    if ((copy = listCreate()) == NULL)
        return NULL;
    //          
    copy->dup = orig->dup;
    copy->free = orig->free;
    copy->match = orig->match;
    //      
    listRewind(orig, &iter);
    while((node = listNext(&iter)) != NULL) {
        void *value;
        //     
        //      dup  ，   dup        
        if (copy->dup) {
            value = copy->dup(node->value);
            if (value == NULL) {
                listRelease(copy);
                return NULL;
            }
        } else //          
            value = node->value;
        //          
        if (listAddNodeTail(copy, value) == NULL) {
            listRelease(copy);
            return NULL;
        }
    }
    return copy;
}

関数の検索


sdlistには2つの検索関数があります.1つは、指定されたノード値に基づいてチェーンテーブルでノードを検索することです.
listNode *listSearchKey(list *list, void *key)
{
    listIter iter;
    listNode *node;

    listRewind(list, &iter);
    while((node = listNext(&iter)) != NULL) {
        if (list->match) { //      match    ，            
            if (list->match(node->value, key)) {
                return node;
            }
        } else { //       match，        
            if (key == node->value) { //      
                return node;
            }
        }
    }
    //        NULL
    return NULL;
}

2つ目は、シーケンス番号に基づいてノードを検索することです.
listNode *listIndex(list *list, long index) {
    listNode *n;

    if (index < 0) {  //     ，     
        index = (-index)-1;
        n = list->tail;
        while(index-- && n) n = n->prev;
    } else { //     
        n = list->head;
        while(index-- && n) n = n->next;
    }
    return n;
}

チェーンテーブル回転関数


回転操作は、表の最後のノードを削除し、ヘッダーに挿入して新しいヘッダーになります.
void listRotate(list *list) {
    listNode *tail = list->tail;

    if (listLength(list) <= 1) return;

    //       
    list->tail = tail->prev;
    list->tail->next = NULL;
    //                 
    list->head->prev = tail;
    tail->prev = NULL;
    tail->next = list->head;
    list->head = tail;
}

sdlist小結


sdlistのソースコードを分析して、本当に双方向チェーンテーブルの基本的な操作をすべて復習して、Redisの作者は本当に車輪を作るのが好きで、さすが車輪界の元祖です!これらの基本操作は簡単であるが,sdlist反復器の設計など,優れた設計を学ぶことができ,これらはRedisに関する操作の理解に大きな助けとなる.
"tamperproof cookie "の作り方
[アルゴリズム]sds特別テーマ指導コード1