朝花夕拾-連結串列（二）

"Good code is its own best documentation." - Steve McConnell

「好程式碼本身就是最好的檔案。」 —— 史蒂夫·麥克康奈爾

0x00 大綱

0x01 前言

資料與結構的解耦

在上篇文章，我們通過將連結串列的節點放在具體資料型別的結構體內，這樣，抽象（連結串列結構）不再依賴於細節（資料型別），細節（資料型別）依賴於抽象（連結串列結構），利用依賴倒置的思想，完成了資料與結構的解耦，進而實現了通用的連結串列。

offsetof

offsetof 是定義在C標準庫標頭檔案<stddef.h>中的一個宏，它會生成一個型別為size_t的無符號整型，代表一個結構成員相對於結構體起始的位元組偏移量（offset）。

container_of

cotainer_of返回的是結構體成員所在結構體的起始地址（指標）,它的原理是用成員變數的起始地址減去成員變數在結構體內的偏移量（用offsetof求得）。

通用連結串列

有了上面三個理論基礎，我們就具備了建立通用連結串列的條件。下面將通過具體的程式碼來演示如何構造和使用這樣的連結串列結構，全程圖解，包你學會。

0x02 連結串列節點

我們的通用連結串列是一個雙向迴圈連結串列，它由一個連結串列頭節點list_head和若干個位於結構體中的中間節點list_node（注意不包括資料域部分）構成。

我們定義了一個名為struct list_head的結構體型別作為我們的連結串列節點，它包含一個指向前驅節點的指標*prev和一個指向後繼節點的指標*next。同時，為了方便後續的編碼和增強程式碼的可讀性，又定義了list_head和list_node兩個結構體型別別名，它們是同一種資料型別的不同名稱。

typedef struct list_head
{
    struct list_head *next, *prev;
} list_head, list_node;

下面的程式碼簡單說明了這種方法給我們帶來的語意上的便利，後面的程式碼範例將延續這樣的風格。

list_head head;// 等價於 struct list_head head;
list_node node;// 等價於 struct list_head node;

0x03 建立連結串列

/**
 * 初始化一個連結串列（頭）節點，它的前驅和後繼指標都指向自己
 * @param list: 需要初始化的節點的指標
 * @return void
**/
static inline void list_init(list_head *list)
{
    list->next = list;
    list->prev = list;
}

0x04 插入節點

任意位置的插入

/**
 * 將節點entry插入到prev和next之間
 * @param entry: 新節點的指標
 * @param prev: 指向插入位置前驅節點的指標
 * @param next: 指向插入位置後繼節點的指標
 * @return void
**/
static inline void __list_add(list_node *entry,
                              list_node *prev,
                              list_node *next)
{
    next->prev = entry;
    entry->next = next;
    entry->prev = prev;
    prev->next = entry;
}

插入到最前

/**
 * 將節點entry插入到頭節點之後
 * 頭插，新節點成為第一個節點
 * @param entry: 指向新節點的指標
 * @param head: 指向頭節點的指標
 * @return void
**/
static inline void list_add_head(list_node *entry,
                                 list_head *head)
{
    __list_add(entry, head, head->next);
}

插入到最後

/**
 * 將節點entry插入到頭節點之前
 * 尾插，新節點成為最後一個節點
 * @param entry: 指向新節點的指標
 * @param head: 指向頭節點的指標
 * @return void
**/
static inline void list_add_tail(list_node *entry,
                                 list_head *head)
{
    __list_add(entry, head->prev, head);
}

0x05 刪除節點

/**
 * 刪除節點
 * @param prev: 被刪除節點的前驅指標
 * @param head: 被刪除節點的後繼指標
 * @return void
**/
static inline void __list_del(list_node * prev,
                              list_node * next)
{
    next->prev = prev;
    prev->next = next;
}
/**
 * 刪除節點，並將其前驅指標和後繼指標指向NULL
 * @param prev: 指向被刪除節點的指標
 * @return void
**/
static inline void list_del(list_node *entry)
{
    __list_del(entry->prev, entry->next);
    entry->prev = entry->next = NULL;
}

可以看到，由於節點本身並不儲存資料，所以，在刪除連結串列節點的時候，也就不用考慮對資料域進行記憶體釋放的操作。

0x06 替換節點

/**
 * 替換節點
 * @param old: 指向被替換節點的指標
 * @param entry: 指向新節點的指標
 * @return void
**/
static inline void list_replace(list_node *old,
                                list_node *entry)
{
    entry->next = old->next;
    entry->next->prev = entry;
    entry->prev = old->prev;
    entry->prev->next = entry;
}

0x07 遍歷和獲取節點資料

遍歷連結串列

/**
 * 快速遍歷連結串列（不可進行刪除操作）
 * @param pos: 指向當前節點位置的指標
 * @param head: 指向頭節點的指標
 * @return void
**/
#define list_for_each(pos, head) \
    for (pos = (head)->next; pos != (head); pos = pos->next)
/**
 * 遍歷連結串列（可進行刪除操作）
 * @param pos: 指向當前節點位置的指標
 * @param n: 指向下一節點位置的指標
 * @param head: 指向頭節點的指標
 * @return void
**/
#define list_for_each_safe(pos, n, head) \
    for (pos = (head)->next, n = pos->next; pos != (head); \
        pos = n, n = pos->next)

獲取節點資料

/**
 * 獲得節點所在資料結構體的起始地址（指標）
 * @param ptr: 指向節點的指標
 * @param type: 資料結構體型別
 * @param member: 節點在資料結構體中被定義的變數名稱
 * @return void
**/
#define list_entry(ptr, type, member) \
    container_of(ptr, type, member)

0x08 小結

將上述的所有基本操作彙總後，得到我們的通用連結串列定義檔案list.h（你可以在Linux核心的原始碼中找到它，這裡的程式碼稍微作了一點修改）：

#ifndef LIST_H
#define LIST_H
#include <stddef.h>
#define container_of(ptr, type, member) \
    ((type *)((char *)(ptr)-offsetof(type,member)))
typedef struct list_head
{
    struct list_head *next, *prev;
} list_head, list_node;
/**
 * 初始化一個連結串列（頭）節點，它的前驅和後繼指標都指向自己
 * @param list: 需要初始化的節點的指標
 * @return void
**/
static inline void list_init(list_head *list)
{
    list->next = list;
    list->prev = list;
}
/**
 * 將節點entry插入到prev和next之間
 * @param entry: 新節點的指標
 * @param prev: 指向插入位置前驅節點的指標
 * @param next: 指向插入位置後繼節點的指標
 * @return void
**/
static inline void __list_add(list_node *entry,
                              list_node *prev,
                              list_node *next)
{
    next->prev = entry;
    entry->next = next;
    entry->prev = prev;
    prev->next = entry;
}
/**
 * 將節點entry插入到頭節點之後
 * 頭插，新節點成為第一個節點
 * @param entry: 指向新節點的指標
 * @param head: 指向頭節點的指標
 * @return void
**/
static inline void list_add_head(list_node *entry,
                                 list_head *head)
{
    __list_add(entry, head, head->next);
}
/**
 * 將節點entry插入到頭節點之前
 * 尾插，新節點成為最後一個節點
 * @param entry: 指向新節點的指標
 * @param head: 指向頭節點的指標
 * @return void
**/
static inline void list_add_tail(list_node *entry,
                                 list_head *head)
{
    __list_add(entry, head->prev, head);
}
/**
 * 刪除節點
 * @param prev: 被刪除節點的前驅指標
 * @param head: 被刪除節點的後繼指標
 * @return void
**/
static inline void __list_del(list_node * prev,
                              list_node * next)
{
    next->prev = prev;
    prev->next = next;
}
/**
 * 刪除節點，並將其前驅指標和後繼指標指向NULL
 * @param prev: 指向被刪除節點的指標
 * @return void
**/
static inline void list_del(list_node *entry)
{
    __list_del(entry->prev, entry->next);
    entry->prev = entry->next = NULL;
}
/**
 * 替換節點
 * @param old: 指向被替換節點的指標
 * @param entry: 指向新節點的指標
 * @return void
**/
static inline void list_replace(list_node *old,
                                list_node *entry)
{
    entry->next = old->next;
    entry->next->prev = entry;
    entry->prev = old->prev;
    entry->prev->next = entry;
}
/**
 * 判斷迴圈雙連結串列是否為空（只有頭節點）
 * @param head: 指向頭節點的指標
 * @return void
**/
static inline int list_empty(const list_head *head)
{
    return head->next == head;
}
/**
 * 快速遍歷連結串列（不可進行刪除操作）
 * @param pos: 指向當前節點位置的指標
 * @param head: 指向頭節點的指標
 * @return void
**/
#define list_for_each(pos, head) \
    for (pos = (head)->next; pos != (head); pos = pos->next)
/**
 * 遍歷連結串列（可進行刪除操作）
 * @param pos: 指向當前節點位置的指標
 * @param n: 指向下一節點位置的指標
 * @param head: 指向頭節點的指標
 * @return void
**/
#define list_for_each_safe(pos, n, head) \
    for (pos = (head)->next, n = pos->next; pos != (head); \
        pos = n, n = pos->next)
/**
 * 獲得節點所在資料結構體的起始地址（指標）
 * @param ptr: 指向節點的指標
 * @param type: 資料結構體型別
 * @param member: 節點在資料結構體中被定義的變數名稱
 * @return void
**/
#define list_entry(ptr, type, member) \
    container_of(ptr, type, member)
#endif // LIST_H