朝花夕拾-鏈表（二）-有解無憂

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

“好代碼本身就是最好的檔案，” —— 史蒂夫·麥克康奈爾

0x00 大綱

0x00 大綱
0x01 前言
- 資料與結構的解耦
- offsetof
- container_of
- 通用鏈表
0x02 鏈表節點
0x03 創建鏈表
0x04 插入節點
- 任意位置的插入
- 插入到最前
- 插入到最后
0x05 洗掉節點
0x06 替換節點
0x07 遍歷和獲取節點資料
- 遍歷鏈表
- 獲取節點資料
0x08 小結

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

轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/539438.html

標籤：其他

上一篇：docker部署專案

下一篇：OpenGL 透明度