Redisにおける双方向リンクリストの実装は、adlist.hとadlist.cというファイルに記述されています。
一、データ構造
Redisで実装されている双方向リンクリストは、一般的な双方向リンクリストと基本的に同じ構造を持っています。
単一ノード：
1 typedef struct listNode {
2 struct listNode *prev;
3 struct listNode *next;
4 void *value;
5 } listNode;
リスト本体：
1 typedef struct list {
2 listNode *head;
3 listNode *tail;
4 void *(*dup)(void *ptr);
5 void (*free)(void *ptr);
6 int (*match)(void *ptr, void *key);
7 unsigned long len;
8 } list;
リスト構造体は、関数ポインタを用いて値の複製、解放、比較操作を多様に対応できるよう設計されています。
イテレータ：
1 typedef struct listIter {
2 listNode *next;
3 int direction;
4 } listIter;
イテレータにはdirectionというメンバ変数があり、現在の走査方向を示すために使用されます。
データ構造の概要：
1 /*
2 +-------------------+ +----------------> +--------------+ <-------+
3 |listNode *head |--------+ |listNode *prev|-->NULL |
4 +-------------------+ +--------------+ |
5 |listNode *tail |--------+ |listNode *next|----+ |
6 +-------------------+ | +--------------+ | |
7 |void *(*dup)(...) | | |void *value | | |
8 +-------------------+ | +--------------+ | |
9 |void (*free)(...) | | | |
10 +-------------------+ | | |
11 |int (*match)(...) | | | |
12 +-------------------+ +----------------> +--------------+ <--+ |
13 |unsigned long len | |listNode *prev|---------+
14 +-------------------+ +--------------+
15 |listNode *next|-->NULL
16 +--------------+
17 |void *value |
18 +--------------+
19 */
二、リストの作成
Redisにおける初期双方向リンクリストの作成は比較的簡単で、メモリを確保し、メンバ変数に初期値を設定するだけです。
1 list *listCreate(void)
2 {
3 struct list *list;
4
5 if ((list = zmalloc(sizeof(*list))) == NULL)
6 return NULL;
7 list->head = list->tail = NULL;
8 list->len = 0;
9 list->dup = NULL;
10 list->free = NULL;
11 list->match = NULL;
12 return list;
13 }
Redisでは、先頭挿入、末尾挿入、指定位置挿入の3つの方法でノードを追加できますが、一般的な双方向リンクリストと同様のため、詳細は割愛します。
三、リストの解放
リスト内の各ノードのvalueはヒープ領域を指している可能性があるため、単にlist構造体をfreeするとメモリリークが発生します。各ノードのvalueを適切に解放してから、構造体を解放する必要があります。
全ノードのクリア：
1 void listEmpty(list *list)
2 {
3 unsigned long len;
4 listNode *current, *next;
5
6 current = list->head;
7 len = list->len;
8 while(len--) {
9 next = current->next;
10 //解放関数が指定されている場合は、その関数を使ってvalueを解放
11 if (list->free) list->free(current->value);
12 zfree(current);
13 current = next;
14 }
15 list->head = list->tail = NULL;
16 list->len = 0;
17 }
リスト全体の解放：
1 void listRelease(list *list)
2 {
3 listEmpty(list);
4 zfree(list);
5 }
同様に、Redisのリスト実装では単一ノードの削除操作も提供していますが、ここでは詳細を説明しません。
四、イテレータ操作
Redisではイテレータを取得するインターフェースが提供されています。
1 listIter *listGetIterator(list *list, int direction)
2 {
3 listIter *iter;
4
5 if ((iter = zmalloc(sizeof(*iter))) == NULL) return NULL;
6 if (direction == AL_START_HEAD)
7 iter->next = list->head;
8 else
9 iter->next = list->tail;
10 iter->direction = direction;
11 return iter;
12 }
AL_START_HEADを例に取ると、生成されたイテレータ構造は以下のようになります：
1 /*
2 +-------------------+ +---> +--------------+ <-------+----+
3 |listNode *head |----+ |listNode *prev|-->NULL | |
4 +-------------------+ +--------------+ | | +--------------+
5 |listNode *tail |----+ |listNode *next|----+ | +--|listNode *next|
6 +-------------------+ | +--------------+ | | +--------------+
7 |void *(*dup)(...) | | |void *value | | | |int direction |
8 +-------------------+ | +--------------+ | | +--------------+
9 |void (*free)(...) | | | |
10 +-------------------+ | | |
11 |int (*match)(...) | | | |
12 +-------------------+ +---> +--------------+ <--+ |
13 |unsigned long len | |listNode *prev|---------+
14 +-------------------+ +--------------+
15 |listNode *next|-->NULL
16 +--------------+
17 |void *value |
18 +--------------+
19 */
イテレータのnextメソッド：
1 listNode *listNext(listIter *iter)
2 {
3 listNode *current = iter->next;
4
5 if (current != NULL) {
6 if (iter->direction == AL_START_HEAD)
7 iter->next = current->next;
8 else
9 iter->next = current->prev;
10 }
11 return current;
12 }
一度nextを呼び出した後の構造：
1 /*
2 +-------------------+ +---> +--------------+ <-------+
3 |listNode *head |----+ |listNode *prev|-->NULL |
4 +-------------------+ +--------------+ | +--------------+
5 |listNode *tail |----+ |listNode *next|----+ | +--|listNode *next|
6 +-------------------+ | +--------------+ | | | +--------------+
7 |void *(*dup)(...) | | |void *value | | | | |int direction |
8 +-------------------+ | +--------------+ | | | +--------------+
9 |void (*free)(...) | | | | |
10 +-------------------+ | | | |
11 |int (*match)(...) | | | | |
12 +-------------------+ +---> +--------------+ <--+----|----+
13 |unsigned long len | |listNode *prev|---------+
14 +-------------------+ +--------------+
15 |listNode *next|-->NULL
16 +--------------+
17 |void *value |
18 +--------------+
19 */
再度呼び出した場合：
1 /*
2 +-------------------+ +---> +--------------+ <-------+
3 |listNode *head |----+ |listNode *prev|-->NULL |
4 +-------------------+ +--------------+ | +--------------+
5 |listNode *tail |----+ |listNode *next|----+ | +--|listNode *next|
6 +-------------------+ | +--------------+ | | | +--------------+
7 |void *(*dup)(...) | | |void *value | | | | |int direction |
8 +-------------------+ | +--------------+ | | | +--------------+
9 |void (*free)(...) | | | | |
10 +-------------------+ | | | |
11 |int (*match)(...) | | | | |
12 +-------------------+ +---> +--------------+ <--+ | +-->NULL
13 |unsigned long len | |listNode *prev|---------+
14 +-------------------+ +--------------+
15 |listNode *next|-->NULL
16 +--------------+
17 |void *value |
18 +--------------+
19 */
next関数を呼び出した後の戻り値は、呼び出し前のlistNodeのアドレスです。
五、その他の操作
Redisの双方向リンクリストは、さらに多くの操作を提供しています。その中で、指定されたキーの検索とリスト全体の複製は、イテレータの使用に依存し、カスタムの比較/複製メソッドを利用します。
これに加えて、疑似ランダム読み取り方式（内部では走査を実装）も提供されており、「範囲外」の場合はNULLを返します。また、負のインデックスをサポートしており、末尾からの位置を示します。回転操作（末尾ノードを先頭ノードの前に移動して新しい先頭にする）も可能です。もちろん、2つのリストを連結する操作もサポートしています。
Redis 5.0.7 ダウンロードリンク
http://download.redis.io/releases/redis-5.0.7.tar.gz
ソースコードの読解順序に関する参考：
https://github.com/huangz1990/blog/blob/master/diary/2014/how-to-read-redis-source-code.rst