list.h linux內核鏈表分析

list.h 頭文件中定義了一些Linux內核鏈表操作相關的函數，自己在學習數據結構時研究了一下裡面的程序，裡面的代碼確實是簡潔又高效。

Linux內核鏈表概述

在傳統鏈表程序中，結構體數據中必須要有一個自身結構體類型的指針，用於指向下一個結構體。一個程序中可能要用到多個鏈表，不同鏈表用的結構體不一定相同，因此不得不為每個種結構體定義一套鏈表操作。而Linux內核鏈表把鏈表指針域的相關操作單獨抽離出來，封裝成一套接口，每一種鏈表都可使用這個接口。如果需要構造某種類型的鏈表時，只要將 struct list_head 類型成員加入到結構體中，用 struct list_head 類型成員將各個結構體連接起來，形成一個雙向循環鏈表。使用的時候只需要調用list.h中相關函數，不用自己再為每種鏈表單獨定義一套函數。

鏈表結構體

[code]struct list_head
{
    struct list_head *next;
    struct list_head *prev;
};

看得出來這是一個雙向鏈表，裡面只有兩個指針，沒有其他任何數據項，其他操作函數也只針對這兩個指針。這就注定了list.h中的鏈表操作可以嵌入到其他任意類型結構體中，具有很強的通用性和靈活性。

定義鏈表頭

[code]#define LIST_HEAD_INIT(name) { &(name), &(name) }

#define LIST_HEAD(name) \
    struct list_head name = LIST_HEAD_INIT(name)

LIST_HEAD 宏用於定義並初始化鏈表頭。 LIST_HEAD 展開後形式為

[code]struct list_head name = {&name, &name}

可見LIST_HEAD定義鏈表頭的時候把前向指針和後向指針都初始化為自身。這時候鏈表是一個循環雙向空鏈表。
另外，也可以使用 INIT_LIST_HEAD 函數初始化鏈表頭：

[code]static inline void INIT_LIST_HEAD(struct list_head *list)
{
    list->next = list;
    list->prev = list;
}

這個鏈表頭是一個獨立的 struct list_head 結構體類型數據，而其他的結點，是用戶定義的結構體類型中 struct list_head 類型的成員。

添加結點

在兩個結點中間插入一個新結點

[code]static inline void __list_add(struct list_head *new,
                  struct list_head *prev,
                  struct list_head *next)
{
    next->prev = new;
    new->next = next;
    new->prev = prev;
    prev->next = new;
}

在鏈表頭部添加一個結點，就是在鏈表頭和第一個結點中間插入一個新結點

[code]static inline void list_add(struct list_head *new, struct list_head *head)
{
    __list_add(new, head, head->next);
}

在鏈表尾部添加一個結點。因為這是雙向循環鏈表，鏈表的最後一個結點就是鏈表頭的前一個結點，要在鏈表尾部加入結點，就在鏈表頭和鏈表頭的前一個結點中間插入結點。

[code]static inline void list_add_tail(struct list_head *new, struct list_head *head)
{
    __list_add(new, head->prev, head);
}

可見無論是在頭部加入結點還是在尾部加入結點，都只要一步就搞定，無需遍歷整個鏈表，這就是雙向循環鏈表的好處。

刪除結點

內核中刪除鏈表代碼如下

[code]/*
 * Delete a list entry by making the prev/next entries
 * point to each other.
 *
 * This is only for internal list manipulation where we know
 * the prev/next entries already!
 */
static inline void __list_del(struct list_head * prev, struct list_head * next)
{
    next->prev = prev;
    prev->next = next;
}

/**
 * list_del - deletes entry from list.
 * @entry: the element to delete from the list.
 * Note: list_empty() on entry does not return true after this, the entry is
 * in an undefined state.
 */
#ifndef CONFIG_DEBUG_LIST
static inline void __list_del_entry(struct list_head *entry)
{
    __list_del(entry->prev, entry->next);
}

static inline void list_del(struct list_head *entry)
{
    __list_del(entry->prev, entry->next);
    entry->next = LIST_POISON1;
    entry->prev = LIST_POISON2;
}
#else
extern void __list_del_entry(struct list_head *entry);
extern void list_del(struct list_head *entry);
#endif

用 list_del 函數刪除鏈表結點，首先用 __list_del 函數將結點從鏈表中移除，再把結點的前向指針指向和後向指針分別指向 LIST_POISON1 和 LIST_POISON2。 LIST_POISON1 和 LIST_POISON2 不是NULL，但引用到這兩個地址是會引起頁錯誤。我們在調試出錯代碼的時候經常會返回指針的值，我們很多時候出錯都是指針為NULL造成的，這時候我們如果發現是值是 LIST_POISON1 或 LIST_POISON2 的話，那我們馬上可以將注意力轉移到鏈表上來了，並且是因為誤用了一個已經從鏈表中刪除掉的節點。

鏈表遍歷

[code]/**
 * list_for_each    -   iterate over a list
 * @pos:    the &struct list_head to use as a loop cursor.
 * @head:   the head for your list.
 */
#define list_for_each(pos, head) \
    for (pos = (head)->next; pos != (head); pos = pos->next)

源碼中將鏈表的遍歷操作直接定義成宏，使用起來非常方便。但是如果在遍歷鏈表過程中，有對鏈表進行插入、刪除結點的操作，pos指針指向的內容被改變，就不能使用這種方法遍歷了，必須使用一種更安全的方法。

[code]/**
 * list_for_each_safe - iterate over a list safe against removal of list entry
 * @pos:    the &struct list_head to use as a loop cursor.
 * @n:      another &struct list_head to use as temporary storage
 * @head:   the head for your list.
 */
#define list_for_each_safe(pos, n, head) \
    for (pos = (head)->next, n = pos->next; pos != (head); \
        pos = n, n = pos->next)

list_for_each_save 又使用了另一個變量n，保存pos下一個結點的指針，這事及時pos被改變，也不會影響鏈表的遍歷操作。
這些方法在鏈表遍歷中得到的只是結構體中struct list_head類型成員的地址，而不是整個結構體的地址，要得到結構體的地址，要使用另一個宏定義。

[code]/**
 * list_entry - get the struct for this entry
 * @ptr:    the &struct list_head pointer.
 * @type:   the type of the struct this is embedded in.
 * @member: the name of the list_struct within the struct.
 */
#define list_entry(ptr, type, member) \
    container_of(ptr, type, member)

container_of 是一個根據結構體成員的地址獲取結構體地址的宏。這個宏的具體分析，可以參見我另一篇博客container_of 宏 分析
有了創建鏈表，添加結點，刪除結點，遍歷鏈表這些函數，就實現鏈表的基本操作了。lish.h 中還有很多高級及操作，比如鏈表結點移動，鏈表合並等，這裡就不一一介紹了。
流雲非晚