adlist作為redis中的雙端鏈表，在Redis中被廣泛的應用到了很多地方，比如 slowlog的存儲，主從復制中報錯客戶端，list數據結構的實現等，很多都與此相關，所以也是非常重要的一個數據結構。
一）、Redis中雙端鏈表的數據結構
（推薦：redis視頻教程）
雙端鏈表（以下代碼定義在 src/adlist.h）：
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;
雙端鏈表的節點（以下代碼定義在 src/adlist.h）：
typedef?struct?listNode?{ ????struct?listNode?*prev;???//當前節點的上一個節點 ????struct?listNode?*next;???//當前節點的下一個節點 ????void?*value;?????//當前節點存儲的值，可以任意類型 }?listNode;
list 通過 head 和 tail兩個指針分別指向鏈表的頭尾兩端，使得遍歷鏈表可以從正反兩個順序進行遍歷，而 listNode 的void *value，則可以保存任意數據，并可以通過dup，free，match來自定義如何處理listNode的值。
二、雙端鏈表的簡單操作
創建鏈表（以下代碼定義在 src/adlist.c）：
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; }
追加到鏈表結尾（以下代碼定義在 src/adlist.c）：
list?*listAddNodeTail(list?*list,?void?*value) { ????listNode?*node;????//初始化node節點 ????//為新的node節點分配內存 ????if?((node?=?zmalloc(sizeof(*node)))?==?NULL) ????????return?NULL; ????//為node節點設置值 ????node->value?=?value; ???? ????if?(list->len?==?0)?{ ????????//如果空鏈表則?將頭尾指向?新節點?并后繼前驅節點設置為NULL ????????list->head?=?list->tail?=?node; ????????node->prev?=?node->next?=?NULL; ????}?else?{ ????????//否則將節點的前驅節點設置為原來的尾部節點 ????????node->prev?=?list->tail; ????????//由于追加到尾部，后繼節點為NULL ????????node->next?=?NULL; ????????//之前的尾部節點的后繼節點設置為新增的節點 ????????list->tail->next?=?node; ????????//將列表的尾部節點指針指向新增的節點 ????????list->tail?=?node; ????} ????//增加鏈表長度 ????list->len++; ????return?list; }
遍歷鏈表：
常用的遍歷鏈表有兩種方式，一個是根據鏈表長度通過while循環去手動遍歷，還有一種是用Redis雙端鏈表提供的迭代器來遍歷。
手動遍歷（以下代碼定義在 src/adlist.c 中的 內存釋放函數）：
void?listRelease(list?*list) { ????unsigned?long?len; ????//current表示當前遍歷的游標指針，next表示下次遍歷的游標指針（next作為臨時變量用于保存下一個節點） ????listNode?*current,?*next; ????//將current指向頭部節點 ????current?=?list->head; ????//計算長度（其實就是?listLength(list)） ????len?=?list->len; ????//通過長度遞減的方式進行遍歷，便利到長度為0的時候，遍歷結束 ????while(len--)?{ ????????//保存下次循環的節點指針 ????????next?=?current->next; ????????//釋放掉當前節點，如果設置釋放節點的回調函數，則執行用戶自定義的函數 ????????if?(list->free)?list->free(current->value); ????????zfree(current); ????????//將游標指向下個節點 ????????current?=?next; ????} ????zfree(list); }
迭代器方式遍歷請見下文。
三）、雙端鏈表的迭代器
Redis 為了方便對鏈表的迭代，對鏈表進行了迭代器的封裝，迭代器結構如下（以下代碼定義在 src/adlist.h）：
typedef?struct?listIter?{ ????listNode?*next;????//迭代器指向的下一個節點 ????//迭代方向，由于雙端鏈表保存了head和tail的值，所以可以進行兩個方向的迭代 ????//AL_START_HEAD表示從頭向后遍歷，AL_START_TAIL表示從尾部向前遍歷 ????int?direction; }?listIter;
?迭代器使用實例：
//l表示list結構，n表示listNode結構，listNode的值保存的是sds字符串 //創建迭代器對象 iter?=?listGetIterator(l,?AL_START_HEAD); //循環獲取下一個需要遍歷的節點 while?((n?=?listNext(iter)))?{ ????//輸出返回的節點n的value值 ????printf("Node?Value:?%sn",?listNodeValue(n)); }
? 版權聲明
文章版權歸作者所有，未經允許請勿轉載。
THE END
