今天來分析Redis的一個基本數據結構--雙端鏈表，其定義和實現主要在sdlist.h和sdlist.c文件中。其主要用在實現列表鍵、事務模塊保存輸入命令和伺服器模塊，訂閱模塊保存多個客戶端等。

sdlist的數據結構

Redis為雙端鏈表的每一個節點定義了如下的結構體。

// 鏈表節點定義ntypedef struct listNode {n struct listNode *prev; // 指向前一個節點n struct listNode *next; // 指向後一個節點n void *value; // 節點值n} listNode;n

與一般的雙端鏈表無異，定義了鏈表節點的結構體之後，下面就定義鏈表的結構體，用來方便管理鏈表節點，其結構體定義如下：

typedef struct list {n listNode *head; // 指向鏈表頭節點n listNode *tail; // 指向鏈表尾節點n void *(*dup)(void *ptr); // 自定義節點值複製函數n void (*free)(void *ptr); // 自定義節點值釋放函數n int (*match)(void *ptr, void *key); // 自定義節點值匹配函數n unsigned long len; // 鏈表長度n} list;n

Redis在實現鏈表的時候，定義其為雙端無環鏈表，其示意圖如下：

此外，Redis對其結構體提供了一系列的宏定義函數，方便操作其結構體參數

#define listLength(l) ((l)->len) // 獲取list長度n#define listFirst(l) ((l)->head) // 獲取list頭節點指針n#define listLast(l) ((l)->tail) // 獲取list尾節點指針n#define listPrevNode(n) ((n)->prev) // 獲取當前節點前一個節點n#define listNextNode(n) ((n)->next) // 獲取當前節點後一個節點n#define listNodeValue(n) ((n)->value) // 獲取當前節點的值nn#define listSetDupMethod(l,m) ((l)->dup = (m)) // 設定節點值複製函數n#define listSetFreeMethod(l,m) ((l)->free = (m)) // 設定節點值釋放函數n#define listSetMatchMethod(l,m) ((l)->match = (m)) // 設定節點值匹配函數nn#define listGetDupMethod(l) ((l)->dup) // 獲取節點值賦值函數n#define listGetFree(l) ((l)->free) // 獲取節點值釋放函數n#define listGetMatchMethod(l) ((l)->match) // 獲取節點值匹配函數n

sdlist迭代器結構

Redis為sdlist定義了一個迭代器結構，其能正序和逆序的訪問list結構。

typedef struct listIter {n listNode *next; // 指向下一個節點n int direction; // 方向參數，正序和逆序n} listIter;n

對於direction參數，Redis提供了兩個宏定義

#define AL_START_HEAD 0 // 從頭到尾n#define AL_START_TAIL 1 // 從尾到頭n

sdlist基本操作

sdlist創建

sdlist提供了listCreate函數來創建一個空的鏈表。

list *listCreate(void)n{n struct list *list; // 定義一個鏈表指針nn if ((list = zmalloc(sizeof(*list))) == NULL) // 申請內存n return NULL; n list->head = list->tail = NULL; // 空鏈表的頭指針和尾指針均為空n list->len = 0; // 設定長度n list->dup = NULL; // 自定義複製函數初始化n list->free = NULL; // 自定義釋放函數初始化n list->match = NULL; // 自定義匹配函數初始化n return list;n}n

sdlist釋放

sdlist提供了listRelease函數來釋放整個鏈表

void listRelease(list *list)n{n unsigned long len;n listNode *current, *next;nn current = list->head;n len = list->len;n while(len--) {n next = current->next;n // 如果定義了節點值釋放函數，需要調用n if (list->free) list->free(current->value);n zfree(current); // 釋放當前節點n current = next;n }n zfree(list); // 釋放鏈表頭n}n

插入節點

sdlist提供了三個函數來完成向list中插入一個節點的功能。

向頭部插入節點

// 該函數向list的頭部插入一個節點nlist *listAddNodeHead(list *list, void *value)n{n listNode *node;nn if ((node = zmalloc(sizeof(*node))) == NULL)n return NULL;n node->value = value;n if (list->len == 0) { // 如果鏈表為空n list->head = list->tail = node;n node->prev = node->next = NULL;n } else { // 如果鏈表非空n node->prev = NULL;n node->next = list->head;n list->head->prev = node;n list->head = node;n }n list->len++; // 長度+1n return list;n}n

向尾部添加節點

// 該函數可以在list的尾部添加一個節點nlist *listAddNodeTail(list *list, void *value)n{n listNode *node;nn if ((node = zmalloc(sizeof(*node))) == NULL)n return NULL;n node->value = value;n if (list->len == 0) { // 如果鏈表為空n list->head = list->tail = node;n node->prev = node->next = NULL;n } else { // 如果鏈表非空n node->prev = list->tail;n node->next = NULL;n list->tail->next = node;n list->tail = node;n }n list->len++; // 長度+1n return list;n}n

向任意位置插入節點

// 向任意位置插入節點n// 其中，old_node為插入位置n// value為插入節點的值n// after為0時表示插在old_node前面，為1時表示插在old_node後面nlist *listInsertNode(list *list, listNode *old_node, void *value, int after) {n listNode *node;nn if ((node = zmalloc(sizeof(*node))) == NULL)n return NULL;n node->value = value;n if (after) { // 向後插入n node->prev = old_node;n node->next = old_node->next;n // 如果old_node為尾節點的話需要改變tailn if (list->tail == old_node) {n list->tail = node;n }n } else { // 向前插入n node->next = old_node;n node->prev = old_node->prev;n // 如果old_node為頭節點的話需要改變headn if (list->head == old_node) {n list->head = node;n }n }n if (node->prev != NULL) {n node->prev->next = node;n }n if (node->next != NULL) {n node->next->prev = node;n }n list->len++;n return list;n}n

刪除節點

void listDelNode(list *list, listNode *node)n{n if (node->prev) // 刪除節點不為頭節點n node->prev->next = node->next;n else // 刪除節點為頭節點需要改變head的指向n list->head = node->next;n if (node->next) // 刪除節點不為尾節點n node->next->prev = node->prev;n else // 刪除節點為尾節點需要改變tail的指向n list->tail = node->prev;n if (list->free) list->free(node->value); // 釋放節點值n zfree(node); // 釋放節點n list->len--;n}n

迭代器相關操作

sdlist為其迭代器提供了一些操作，用來完成獲取迭代器，釋放迭代器，重置迭代器，獲取下一個迭代器等操作，具體源碼見如下分析。

獲取迭代器

listIter *listGetIterator(list *list, int direction)n{n listIter *iter; // 聲明迭代器nn if ((iter = zmalloc(sizeof(*iter))) == NULL) return NULL;n // 根據迭代方向來初始化itern if (direction == AL_START_HEAD)n iter->next = list->head;n elsen iter->next = list->tail;n iter->direction = direction;n return iter;n}n

釋放迭代器

void listReleaseIterator(listIter *iter) {n zfree(iter); // 直接調用zfree來釋放n}n

重置迭代器

重置迭代器分為兩種，一種是重置正向迭代器，一種是重置為逆向迭代器

// 重置為正向迭代器nvoid listRewind(list *list, listIter *li) {n li->next = list->head;n li->direction = AL_START_HEAD;n}n// 重置為逆向迭代器nvoid listRewindTail(list *list, listIter *li) {n li->next = list->tail;n li->direction = AL_START_TAIL;n}n

獲取下一個迭代器

// 根據direction屬性來獲取下一個迭代器nlistNode *listNext(listIter *iter)n{n listNode *current = iter->next;nn if (current != NULL) {n if (iter->direction == AL_START_HEAD)n iter->next = current->next;n elsen iter->next = current->prev;n }n return current;n}n

鏈表複製函數

sdlist提供了listDup函數，用於複製整個鏈表。

list *listDup(list *orig)n{n list *copy;n listIter iter;n listNode *node;nn if ((copy = listCreate()) == NULL)n return NULL;n // 複製節點值操作函數n copy->dup = orig->dup;n copy->free = orig->free;n copy->match = orig->match;n // 重置迭代器n listRewind(orig, &iter);n while((node = listNext(&iter)) != NULL) {n void *value;n // 複製節點n // 如果定義了dup函數，則按照dup函數來複制節點值n if (copy->dup) {n value = copy->dup(node->value);n if (value == NULL) {n listRelease(copy);n return NULL;n }n } else // 如果沒有則直接賦值n value = node->value;n // 依次向尾部添加節點n if (listAddNodeTail(copy, value) == NULL) {n listRelease(copy);n return NULL;n }n }n return copy;n}n

查找函數

sdlist提供了兩種查找函數。其一是根據給定節點值，在鏈表中查找該節點

listNode *listSearchKey(list *list, void *key)n{n listIter iter;n listNode *node;nn listRewind(list, &iter);n while((node = listNext(&iter)) != NULL) {n if (list->match) { // 如果定義了match匹配函數，則利用該函數進行節點匹配n if (list->match(node->value, key)) {n return node;n }n } else { // 如果沒有定義match，則直接比較節點值n if (key == node->value) { // 找到該節點n return node;n }n }n }n // 沒有找到就返回NULLn return NULL;n}n

其二是根據序號來查找節點

listNode *listIndex(list *list, long index) {n listNode *n;nn if (index < 0) { // 序號為負，則倒序查找n index = (-index)-1;n n = list->tail;n while(index-- && n) n = n->prev;n } else { // 正序查找n n = list->head;n while(index-- && n) n = n->next;n }n return n;n}n

鏈表旋轉函數

旋轉操作其實就是講表尾節點移除，然後插入到表頭，成為新的表頭

void listRotate(list *list) {n listNode *tail = list->tail;nn if (listLength(list) <= 1) return;nn // 取出表尾指針n list->tail = tail->prev;n list->tail->next = NULL;n // 將其移動到表頭並成為新的表頭指針n list->head->prev = tail;n tail->prev = NULL;n tail->next = list->head;n list->head = tail;n}n

sdlist小結

分析完sdlist的源碼，著實是把雙向鏈表的基本操作都複習了一遍，Redis的作者還真是喜歡造輪子，不愧是輪子界的鼻祖啊！雖然這些基本操作很簡單，但是可以學到一些優秀的設計，例如：sdlist迭代器的設計等，這些都對理解Redis的相關操作有著很大的幫助作用。