Redis-チェーンテーブル

1618 ワード

定義#テイギ#
各チェーンテーブルノードはadlist.h/listNode構造を使用して表されます.
typedef struct listNode {

    //     
    struct listNode *prev;

    //     
    struct listNode *next;

    //     
    void *value;

} listNode;

adlist.h/listリスト構造:
typedef struct list {

    //     
    listNode *head;

    //     
    listNode *tail;

    //           
    unsigned long len;

    // dup                
    void *(*dup)(void *ptr);

    // free                
    void (*free)(void *ptr);

    // match                            
    int (*match)(void *ptr, void *key);

} list;

機能:
Redisのチェーンテーブル実装の特性は以下のようにまとめることができる.
両端:チェーンテーブルノードにはprevとnextポインタがあり、あるノードの前置ノードと後置ノードを取得する複雑さはO(1)である.
ループなし:ヘッダノードのprevポインタとテーブルエンドノードのnextポインタはNULLを指し、チェーンテーブルへのアクセスはNULLを終点とします.
ヘッダポインタとテールポインタ付き:list構造のheadポインタとtailポインタにより,プログラムがチェーンテーブルのヘッダノードとテールノードを取得する複雑さはO(1)である.
チェーンテーブル長カウンタ付き:プログラムはlist構造のlen属性を使用してlistが持つチェーンテーブルノードをカウントし、プログラム取得チェーンテーブル中のノード数の複雑度はO(1)である.
マルチステート:チェーンテーブルノードはvoid*ポインタを使用してノード値を保存し、list構造のdup、free、matchの3つの属性でノード値にタイプ固有の関数を設定できるので、チェーンテーブルはさまざまなタイプの値を保存するために使用できます.
まとめ
  • チェーンテーブルは、リストキー、パブリッシュとサブスクリプション、遅いクエリー、モニタなど、Redisのさまざまな機能を実現するために広く使用されています.
  • 各チェーンテーブルノードはlistNode構造によって表され、各ノードには前置ノードと後置ノードを指すポインタがあるので、Redisのチェーンテーブル実装は両端チェーンテーブルである.
  • 各チェーンテーブルはリスト構造を用いて表され、この構造はヘッダノードポインタ、テーブルエンドノードポインタ、およびチェーンテーブル長などの情報を有する.
  • チェーンテーブルヘッダノードの前置ノードとテーブルエンドノードの後置ノードがNULLを指すため、Redisのチェーンテーブル実装は無ループチェーンテーブルである.
  • チェーンテーブルに異なるタイプの特定の関数を設定することによって、Redisのチェーンテーブルは、様々な異なるタイプの値を保存するために使用することができる.