redisソース学習のチェーンテーブル

チェーンテーブルは古典的なデータ構造であり、redisの実現も古典的である.

にほうこうチェーンテーブル

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;

この後ろには3つの関数ポインタがあり、コピーコンストラクション関数、コンストラクション関数、コンパレータに似ています.

マクロ定義

redisソースコードには、set/getメソッドのように、チェーンテーブルのヘッダ情報を設定するためのマクロ定義がいくつか設計されています.

#define listLength(l) ((l)->len)
//            
// T = O(1)
#define listFirst(l) ((l)->head)
//            
// T = O(1)
#define listLast(l) ((l)->tail)
//            
// T = O(1)
#define listPrevNode(n) ((n)->prev)
//            
// T = O(1)
#define listNextNode(n) ((n)->next)
//         
// T = O(1)
#define listNodeValue(n) ((n)->value)

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

//             
// T = O(1)
#define listGetDupMethod(l) ((l)->dup)
//             
// T = O(1)
#define listGetFree(l) ((l)->free)
//             
// T = O(1)
#define listGetMatchMethod(l) ((l)->match)

操作

ソースコードを見てみると、基本的なチェーンテーブル操作です.しかしredisは、チェーンテーブルを反復するときに反復器構造をカスタマイズします.この構造には、主に次の位置を指すポインタと、反復方向(順方向反復か逆方向反復か)が含まれます.この反復器構造は、チェーンテーブルをコピーする場合など、ソースコードに広く適用されます.

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;

    //         
    iter = listGetIterator(orig, AL_START_HEAD);
    while((node = listNext(iter)) != NULL) {
        void *value;

        //          
        if (copy->dup) {//         
            value = copy->dup(node->value);
            if (value == NULL) {
                listRelease(copy);
                listReleaseIterator(iter);
                return NULL;
            }
        } else
            value = node->value;

        //         
        if (listAddNodeTail(copy, value) == NULL) {
            listRelease(copy);
            listReleaseIterator(iter);
            return NULL;
        }
    }

    //      
    listReleaseIterator(iter);

    //     
    return copy;
}

まとめ

チェーンテーブルは、リストキー、パブリッシュおよびサブスクリプション、スロークエリー、モニタなど、Redisの様々な機能を実現するために広く使用されており、双方向チェーンテーブルのノード構造に加えてチェーンテーブル全体を管理するヘッダノードを実現し、関連するAPIはチェーンテーブル操作である.