Linux內(nèi)核鏈表是Linux內(nèi)核最經(jīng)典的數(shù)據(jù)結(jié)構(gòu)之一夷蚊，Linux內(nèi)核鏈表最大的優(yōu)點就是節(jié)省內(nèi)存拦耐，對鏈表的各項操作較快弯蚜，實現(xiàn)的思路耳目一新，而且在Linux內(nèi)核里頻繁使用攻锰，比如：內(nèi)存管理晾嘶，進程調(diào)度等。
Linux內(nèi)核鏈表是一個雙向循環(huán)鏈表娶吞，核心思想就是把鏈表結(jié)點放在數(shù)據(jù)結(jié)點里面垒迂，通過前后指針分別指向前后數(shù)據(jù)結(jié)點里面的鏈表結(jié)點，這樣就可以將各個數(shù)據(jù)結(jié)點連接在一起妒蛇。
一机断、鏈表結(jié)點定義
struct list_head {
struct list_head *next, *prev;
};
二、內(nèi)核鏈表初始化
#define LIST_HEAD_INIT(name) { &(name), &(name) }
#define LIST_HEAD(name) \
struct list_head name = LIST_HEAD_INIT(name)
static inline void INIT_LIST_HEAD(struct list_head *list)
{
list->next = list;
list->prev = list;
}
INIT_LIST_HEAD函數(shù)prev指針和next指針指向鏈表頭結(jié)點绣夺。LIST_HEAD_INIT宏初始化鏈表頭結(jié)點next指針和prev指針保存頭結(jié)點地址吏奸，實際上和INI_LIST_HEAD函數(shù)初始化效果一樣，LIST_HEAD宏就是鏈表結(jié)點的完整初始化陶耍。我們以實際代碼為例：
struct list_head list;
LIST_HEAD(list); //list = {&list, &list}
三奋蔚、內(nèi)核鏈表插入結(jié)點
/*
* Insert a new entry between two known consecutive entries.
*
* This is only for internal list manipulation where we know
* the prev/next entries already!
*/
#ifndef CONFIG_DEBUG_LIST
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;
}
#else
extern void __list_add(struct list_head *new,
struct list_head *prev,
struct list_head *next);
#endif
/**
* list_add - add a new entry
* @new: new entry to be added
* @head: list head to add it after
*
* Insert a new entry after the specified head.
* This is good for implementing stacks.
*/
#ifndef CONFIG_DEBUG_LIST
static inline void list_add(struct list_head *new, struct list_head *head)
{
__list_add(new, head, head->next);
}
#else
extern void list_add(struct list_head *new, struct list_head *head);
#endif
/**
* list_add_tail - add a new entry
* @new: new entry to be added
* @head: list head to add it before
*
* Insert a new entry before the specified head.
* This is useful for implementing queues.
*/
static inline void list_add_tail(struct list_head *new, struct list_head *head)
{
__list_add(new, head->prev, head);
}
我們作圖解釋會更容易理解內(nèi)核鏈表插入操作。
直接看代碼我們即可知道內(nèi)核鏈表實際上采用的是尾插法烈钞，并且有一個頭結(jié)點泊碑。
內(nèi)核鏈表插入結(jié)點前如圖1所示：
圖1
內(nèi)核鏈表插入結(jié)點后如圖2所示：
結(jié)合list_add_tail函數(shù)分析可知，假設(shè)鏈表list插入結(jié)點node毯欣，則next=list->next馒过，prev=list;再調(diào)用__list_add則可將新結(jié)點插入到鏈表里面。
四酗钞、內(nèi)核鏈表刪除結(jié)點
/*
* 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(struct list_head *entry)
{
__list_del(entry->prev, entry->next);
entry->next = LIST_POISON1;
entry->prev = LIST_POISON2;
}
#else
extern void list_del(struct list_head *entry);
#endif
直接分析代碼可知腹忽，刪除結(jié)點實際上就是將目標結(jié)點后面一個結(jié)點的前向指針指向目標結(jié)點的前向結(jié)點，目標結(jié)點的前向結(jié)點的后向指針指向目標結(jié)點的后向結(jié)點砚作，這樣就可以把目標結(jié)點分離出來了窘奏。
結(jié)尾
Linux內(nèi)核鏈表還有很多有意思的實現(xiàn)，例如遍歷葫录，獲取數(shù)據(jù)結(jié)點結(jié)構(gòu)體首地址等蔼夜，下一章再詳細分析。
