Redisソースプロファイリング--両端チェーンテーブルSdlist
>私のブログに引き続き注目してください:https://zcheng.ren今日、Redisの基本的なデータ構造である両端チェーンテーブルを分析し、その定義と実現は主にsdlistである.hとsdlist.cファイルにあります.主にリストキーの実装、トランザクションモジュールの入力コマンドとサーバモジュールの保存、サブスクリプションモジュールの複数のクライアントの保存などに使用されます.
Redisは、両端チェーンテーブルの各ノードについて、以下のような構造体を定義する.
さらに,Redisはその構造体に一連のマクロ定義関数を提供し,その構造体パラメータの操作を容易にする.
Redisはsdlistのために反復器構造を定義し,正と逆の順序でlist構造にアクセスできる.
Directionパラメータの場合、Redisは2つのマクロ定義を提供します.
sdlistはlistCreate関数を提供し、空のチェーンテーブルを作成します.
sdlistはリストリストリスト関数を提供し、チェーンテーブル全体を解放します.
sdlistはlistにノードを挿入する機能を完了するために3つの関数を提供します.
sdlistはその反復器にいくつかの操作を提供し、反復器の取得、反復器の解放、反復器のリセット、次の反復器の取得などの操作を完了するために使用され、具体的なソースコードは以下の分析を参照してください.
リセット反復器は2種類に分けられます.1つは順方向反復器をリセットすることです.1つは逆方向反復器にリセットすることです.
sdlistはリストDup関数を提供し、チェーンテーブル全体をコピーします.
sdlistには2つの検索関数があります.1つは、指定されたノード値に基づいてチェーンテーブルでノードを検索することです.
2つ目は、シーケンス番号に基づいてノードを検索することです.
回転操作は、表の最後のノードを削除し、ヘッダーに挿入して新しいヘッダーになります.
sdlistのソースコードを分析して、本当に双方向チェーンテーブルの基本的な操作をすべて復習して、Redisの作者は本当に車輪を作るのが好きで、さすが車輪界の元祖です!これらの基本操作は簡単であるが,sdlist反復器の設計など,優れた設計を学ぶことができ,これらはRedisに関する操作の理解に大きな助けとなる.
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はその構造体に一連のマクロ定義関数を提供し,その構造体パラメータの操作を容易にする.
#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に関する操作の理解に大きな助けとなる.