Redis-チェーンテーブル
1618 ワード
定義#テイギ#
各チェーンテーブルノードはadlist.h/listNode構造を使用して表されます.
adlist.h/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のチェーンテーブルは、様々な異なるタイプの値を保存するために使用することができる.
各チェーンテーブルノードは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つの属性でノード値にタイプ固有の関数を設定できるので、チェーンテーブルはさまざまなタイプの値を保存するために使用できます.
まとめ