在之前對Redis的介紹中，可以看到鏈表的使用頻率非常高。

鏈表可以作為單獨的存儲結(jié)構(gòu)，比如客戶端的監(jiān)視鏈表記錄該客戶端監(jiān)視的所有鍵，服務(wù)器的模式訂閱鏈表記錄所有客戶端和它的模式訂閱。

鏈表也可以內(nèi)嵌到字典中作為字典的值類型，比如數(shù)據(jù)庫的監(jiān)視字典使用鏈表存儲監(jiān)視某個鍵的所有客戶端，服務(wù)器的訂閱字典使用鏈表存儲訂閱某個頻道的所有客戶端。

鏈表結(jié)構(gòu)

節(jié)點

Redis中的鏈表是雙向鏈表，即每一個節(jié)點都保存了它的前驅(qū)節(jié)點和后繼節(jié)點，用于提高操作效率。節(jié)點定義如下

//adlist.h /* 鏈表節(jié)點 */ typedef struct listNode {struct listNode *prev; /* 前驅(qū)節(jié)點 */struct listNode *next; /* 后繼節(jié)點 */void *value; /* 值 */ } listNode;

鏈表

鏈表結(jié)構(gòu)主要記錄了表頭節(jié)點和表尾節(jié)點，節(jié)點個數(shù)以及一些函數(shù)指針，定義如下

//adlist.h /* 鏈表 */ typedef struct list {listNode *head; /* 鏈表頭節(jié)點 */listNode *tail; /* 鏈表尾節(jié)點 */void *(*dup)(void *ptr); /* 節(jié)點值復(fù)制函數(shù) */void (*free)(void *ptr); /* 節(jié)點值析構(gòu)函數(shù) */int (*match)(void *ptr, void *key); /* 節(jié)點值匹配函數(shù) */unsigned long len; /* 鏈表長度 */ } list;

函數(shù)指針主要是對節(jié)點值的操作，包括復(fù)制，析構(gòu)，判斷是否相等

迭代器

此外，Redis還為鏈表提供迭代器的功能，主要是對鏈表節(jié)點的封裝，另外通過鏈表節(jié)點的前驅(qū)節(jié)點和后繼節(jié)點，可以輕松的完成向前移動和向后移動

//adlist.h /* 迭代器 */ typedef struct listIter {/* 指向?qū)嶋H的節(jié)點 */listNode *next;/* 迭代器方向，向前還是向后 */int direction; } listIter;

direction的值有兩個，向前和向后，由宏定義指出

//adlist.h #define AL_START_HEAD 0 /* 從頭到尾(向后) */ #define AL_START_TAIL 1 /* 從尾到頭(向前) */

鏈表操作

創(chuàng)建鏈表

鏈表的創(chuàng)建工作由listCreate函數(shù)完成，實際上就是申請鏈表內(nèi)存然后初始化成員變量

//adlist.c /* 創(chuàng)建一個空鏈表 */ list *listCreate(void) {struct list *list;/* 為鏈表申請內(nèi)存 */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; }

刪除鏈表

刪除一個鏈表比創(chuàng)建稍微麻煩一點，因為需要釋放每個節(jié)點中保存的值，沒錯，它正是調(diào)用free函數(shù)完成的

//adlist.c /* 釋放鏈表的內(nèi)存空間 */ void listRelease(list *list) {unsigned long len;listNode *current, *next;current = list->head;len = list->len;/* 遍歷鏈表，釋放每一個節(jié)點 */while(len--) {/* 記錄下一個節(jié)點 */next = current->next;/* 如果定義了節(jié)點值析構(gòu)函數(shù)，則調(diào)用 */if (list->free) list->free(current->value);/* 釋放節(jié)點內(nèi)存 */zfree(current);current = next;}/* 因為list* 也是動態(tài)申請的，所以也需要釋放 */zfree(list); }

在末尾插入節(jié)點

在其他模塊的實現(xiàn)上，經(jīng)常會看到向鏈表尾部添加節(jié)點的操作，它的實現(xiàn)由listAddNodeTail完成。函數(shù)首先為新節(jié)點申請內(nèi)存，然后將節(jié)點添加到鏈表中，這里需要根據(jù)鏈表之前是否為空執(zhí)行不同操作

• 鏈表為空，新節(jié)點將作為鏈表的頭節(jié)點和尾節(jié)點，新節(jié)點的前驅(qū)和后繼指針都為空
• 鏈表非空，新節(jié)點將作為鏈表的尾節(jié)點，之前的尾節(jié)點的后繼指針指向新節(jié)點，新節(jié)點的前驅(qū)指針指向之前的尾節(jié)點

//adlist.c /* 在鏈表尾部添加節(jié)點 */ list *listAddNodeTail(list *list, void *value) {listNode *node;/* 申請節(jié)點 */if ((node = zmalloc(sizeof(*node))) == NULL)return NULL;/* 記錄節(jié)點值 */node->value = value;/* 如果之前鏈表為空，那么插入一個節(jié)點后頭尾節(jié)點都是新節(jié)點 */if (list->len == 0) {list->head = list->tail = node;/* 設(shè)置前驅(qū)后繼節(jié)點 */node->prev = node->next = NULL;} else {/* 不為空，只改變尾節(jié)點 */node->prev = list->tail;node->next = NULL;list->tail->next = node;list->tail = node;}/* 節(jié)點個數(shù)加一 */list->len++;return list; }

迭代器移動

迭代器主要用于遍歷鏈表，而迭代器的重點在移動上，通過direction變量，可以得知迭代器移動的方向，又通過鏈表節(jié)點的前驅(qū)后繼節(jié)點，可以輕松實現(xiàn)移動操作

//adlist.c /* 移動迭代器，同時返回下一個節(jié)點 */ listNode *listNext(listIter *iter) {/* next指針是當前迭代器指向的節(jié)點指針 */listNode *current = iter->next;if (current != NULL) {/* 根據(jù)方向為next賦值 */if (iter->direction == AL_START_HEAD)iter->next = current->next;elseiter->next = current->prev;}/* 返回之前迭代器指向的節(jié)點 */return current; }

重置迭代器

此外，Redis提供了重置迭代器的操作，分別由listRewind和listRewindTail函數(shù)完成

/* 重置迭代器方向為從頭到尾，使迭代器指向頭節(jié)點 */ void listRewind(list *list, listIter *li) {li->next = list->head;li->direction = AL_START_HEAD; }/* 重置迭代器方向為從尾到頭，使迭代器指向尾節(jié)點 */ void listRewindTail(list *list, listIter *li) {li->next = list->tail;li->direction = AL_START_TAIL; }

鏈表搜索

有了迭代器的基礎(chǔ)，就可以實現(xiàn)鏈表搜索功能，即在鏈表中查找與某個值匹配的節(jié)點，需要利用迭代器遍歷鏈表

//adlist.c /* 查找值key，返回鏈表節(jié)點 */ listNode *listSearchKey(list *list, void *key) {listIter iter;listNode *node;/* 設(shè)置迭代器方向為從頭到尾，使其指向鏈表頭節(jié)點 */listRewind(list, &iter);/* 遍歷鏈表 */while((node = listNext(&iter)) != NULL) {/* 如果提供值匹配函數(shù)，則調(diào)用，否則使用==比較 */if (list->match) {if (list->match(node->value, key)) {return node;}} else {if (key == node->value) {return node;}}}return NULL; }

宏定義函數(shù)

除了上面提到的函數(shù)外，Redis還提供了一些宏定義函數(shù)，比如返回節(jié)點值，返回節(jié)點的前驅(qū)后繼節(jié)點等

//adlist.h /* 返回鏈表節(jié)點個數(shù) */ #define listLength(l) ((l)->len) /* 返回頭節(jié)點 */ #define listFirst(l) ((l)->head) /* 返回尾節(jié)點 */ #define listLast(l) ((l)->tail) /* 返回前驅(qū)節(jié)點 */ #define listPrevNode(n) ((n)->prev) /* 返回后繼節(jié)點 */ #define listNextNode(n) ((n)->next) /* 返回節(jié)點值 */ #define listNodeValue(n) ((n)->value)/* 設(shè)置鏈表的值復(fù)制，值析構(gòu)，值匹配函數(shù) */ #define listSetDupMethod(l,m) ((l)->dup = (m)) #define listSetFreeMethod(l,m) ((l)->free = (m)) #define listSetMatchMethod(l,m) ((l)->match = (m))/* 獲取鏈表的值賦值，值析構(gòu)，值匹配函數(shù) */ #define listGetDupMethod(l) ((l)->dup) #define listGetFree(l) ((l)->free) #define listGetMatchMethod(l) ((l)->match)

小結(jié)

由于鏈表結(jié)構(gòu)簡單，所以在實現(xiàn)上還是非常容易理解的。當然Redis中與鏈表有關(guān)的函數(shù)還有很多很多，這里僅僅介紹了一些常用操作，有興趣可以深入源碼查看

與50位技術(shù)專家面對面20年技術(shù)見證，附贈技術(shù)全景圖

總結(jié)

以上是生活随笔為你收集整理的Redis源码剖析（八）链表的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。