adlist.h/adlist.c
一、 adlist 的定義
由于 C 語言沒有內(nèi)置的鏈表這種常用的數(shù)據(jù)結(jié)構(gòu)，因此 Redis 實現(xiàn)了自己的鏈表實現(xiàn)。
Redis 對鏈表的實現(xiàn)，包括鏈表（ list ）、鏈表節(jié)點（ listNode ）以及鏈表迭代器（ listIter ）三個數(shù)據(jù)結(jié)構(gòu)。
其中，鏈表節(jié)點在 adlist.h/listNode 中進行了定義：
//鏈表節(jié)點
typedef struct listNode {
// 前置節(jié)點
struct listNode *prev;
// 后置節(jié)點
struct listNode *next;
// 節(jié)點的值
void *value;
} listNode;
多個鏈表節(jié)點通過 prve 和 next 指針組成雙端鏈表，如下圖所示：
在鏈表節(jié)點組成雙端鏈表后，由鏈表（ adlist.h/list ）來持有雙端鏈表的話，操作起來會更加方便。
鏈表在 adlist.h/list 中進行了定義：
//鏈表
typedef struct list {
// 表頭節(jié)點
listNode *head;
// 表尾節(jié)點
listNode *tail;
// 鏈表長度，即鏈表所包含的節(jié)點數(shù)量
unsigned long len;
// 節(jié)點值復(fù)制函數(shù)
void *(*dup)(void *ptr);
// 節(jié)點值釋放函數(shù)
void (*free)(void *ptr);
// 節(jié)點值對比函數(shù)
int (*match)(void *ptr, void *key);
} list;
下圖是一個 list 結(jié)構(gòu)與三個 listNode 結(jié)構(gòu)組成的鏈表：
迭代器在 adlist.h/listIter 中進行了定義：
//迭代器
typedef struct listIter {
// 當前迭代到的節(jié)點
listNode *next;
// 迭代的方向
// 0 表示從表頭向表尾進行迭代
// 1 表示從表尾向表頭進行迭代
int direction;
} listIter;
//迭代器進行迭代的方向
// 從表頭向表尾進行迭代
#define AL_START_HEAD 0
// 從表尾到表頭進行迭代
#define AL_START_TAIL 1
二、 adlist 的 API
adlist 的函數(shù)實現(xiàn)分為兩種，一種是通過宏定義的函數(shù)，一種是普通函數(shù)。
- 宏定義函數(shù)
| 函數(shù) | 作用 | 時間復(fù)雜度 |
|---|---|---|
| listLength | 返回給定鏈表的長度，即所包含的節(jié)點個數(shù) | O(1) |
| listFirst | 返回給定鏈表的表頭節(jié)點 | O(1) |
| listLast | 返回給定鏈表的表尾節(jié)點 | O(1) |
| listPrevNode | 返回給定鏈表節(jié)點的前一個結(jié)點 | O(1) |
| listNextNode | 返回給定鏈表節(jié)點的后一個結(jié)點 | O(1) |
| listNodeValue | 返回給定鏈表節(jié)點的值 | O(1) |
| listSetDupMethod | 將給定的函數(shù)設(shè)置為給定鏈表的節(jié)點值復(fù)制函數(shù) | O(1) |
| listSetFreeMethod | 將給定的函數(shù)設(shè)置為給定鏈表的節(jié)點值釋放函數(shù) | O(1) |
| listSetMatchMethod | 將給定的函數(shù)設(shè)置為給定鏈表的節(jié)點值對比函數(shù) | O(1) |
| listGetDupMethod | 返回給定鏈表當前正在使用的節(jié)點值復(fù)制函數(shù) | O(1) |
| listGetFree | 返回給定鏈表當前正在使用的節(jié)點值釋放函數(shù) | O(1) |
| listGetMatchMethod | 返回給定鏈表當前正在使用的節(jié)點值對比函數(shù) | O(1) |
- 普通函數(shù)
| 函數(shù) | 作用 | 時間復(fù)雜度 |
|---|---|---|
| listCreate | 創(chuàng)建一個不包含任何節(jié)點的空鏈表 | O(1) |
| listRelease | 釋放給定鏈表，包括鏈表中的所有節(jié)點 | O(N)，N為鏈表中的節(jié)點數(shù) |
| listAddNodeHead | 將包含給定值的新節(jié)點插入到給定鏈表的表頭 | O(1) |
| listAddNodeTail | 將包含給定值的新節(jié)點插入到給定鏈表的表尾 | O(1) |
| listInsertNode | 將包含給定值的新節(jié)點插入到給定節(jié)點的之前或之后 | O(1) |
| listDelNode | 從給定鏈表中刪除給定節(jié)點 | O(1) |
| listGetIterator | 為給定鏈表創(chuàng)建一個迭代器，并為其配置迭代方向 | O(1) |
| listNext | 返回迭代器當前所指向的鏈表節(jié)點 | O(1) |
| listReleaseIterator | 釋放給定迭代器 | O(1) |
| listDup | 復(fù)制給定鏈表，并返回復(fù)制后的副本 | O(N)，N為鏈表中的節(jié)點數(shù) |
| listSearchKey | 查找并返回鏈表中包含給定值的結(jié)點，查找方向為從頭至尾 | O(N)，N為鏈表中的節(jié)點數(shù) |
| listIndex | 查找并返回鏈表中在給定索引上的結(jié)點，索引值從零開始，可以為負（索引為負表示從表尾開始查找，-1 表示表尾節(jié)點，-2 表示倒數(shù)第二個結(jié)點） | O(N)，N為鏈表中的節(jié)點數(shù) |
| listRewind | 將給定迭代器的方向設(shè)置為從頭到尾（AL_START_HEAD），并將迭代指針重新指向表頭節(jié)點 | O(1) |
| listRewindTail | 將給定迭代器的方向設(shè)置從尾到頭（AL_START_TAIL），并將迭代指針重新指向表尾節(jié)點 | O(1) |
| listRotate | 將鏈表的表尾結(jié)點彈出，并插入到鏈表的表頭，成為新的表頭結(jié)點 | O(1) |
三、 adlist 的特性
雙端鏈表
鏈表節(jié)點有 prev 和 next 指針，所以獲取某節(jié)點的前后結(jié)點的復(fù)雜度都為O(1)。無環(huán)
鏈表無環(huán)，即鏈表的表頭結(jié)點的 prev 指針和表尾節(jié)點的 next 指針都指向 NULL ，所以在通過迭代器對鏈表進行訪問時（無論方向），都會以 NULL 為結(jié)尾，不會出現(xiàn)循環(huán)。帶有表頭結(jié)點和表尾結(jié)點
list 結(jié)構(gòu)帶有 head 和 tail 指針，所以獲取某鏈表的頭尾結(jié)點的復(fù)雜度都為O(1)。帶有鏈表長度
list 結(jié)構(gòu)帶有 len 屬性，所以獲取某鏈表的長度的復(fù)雜度僅為O(1)。多態(tài)
鏈表節(jié)點使用 void * 指針來持有節(jié)點值，所以鏈表可以用于保存各種類型的值。
