關(guān)于雙鏈表實(shí)現(xiàn)，一般教科書上定義一個(gè)雙向鏈表節(jié)點(diǎn)的方法如下：
復(fù)制代碼 代碼如下:
struct list_node{
stuct list_node *pre;
stuct list_node *next;
ElemType data;
}
即一個(gè)鏈表節(jié)點(diǎn)包含：一個(gè)指向前向節(jié)點(diǎn)的指針、一個(gè)指向后續(xù)節(jié)點(diǎn)的指針，以及數(shù)據(jù)域共三部分。
但查看linux內(nèi)核代碼中的list實(shí)現(xiàn)時(shí)，會(huì)發(fā)現(xiàn)其與教科書上的方法有很大的差別。
來(lái)看看linux是如何實(shí)現(xiàn)雙鏈表。
雙鏈表節(jié)點(diǎn)定義
復(fù)制代碼 代碼如下:
struct list_head {
struct list_head *next, *prev;
};
發(fā)現(xiàn)鏈表節(jié)點(diǎn)中根本就沒(méi)有數(shù)據(jù)域，這樣的鏈表有什么用？linux內(nèi)核中定義這樣的鏈表原因何在？
這是因?yàn)閘inux中是通過(guò)獨(dú)立定義一個(gè)鏈表結(jié)構(gòu)，并在結(jié)構(gòu)體中內(nèi)嵌一個(gè)鏈表節(jié)點(diǎn)來(lái)實(shí)現(xiàn)鏈表結(jié)構(gòu)的。這樣有一個(gè)好處就是能達(dá)到鏈表與結(jié)構(gòu)體分離的目的。如此一來(lái)，我們構(gòu)建好一個(gè)鏈表后，其結(jié)構(gòu)示意圖如下：
鏈表的定義及初始化宏定義：
復(fù)制代碼 代碼如下:
#define LIST_HEAD_INIT(name){(name),(name)}
#define LIST_HEAD(name) \
struct list_head name = LIST_HEAD_INIT(name)
#define INIT_LIST_HEAD(ptr) do { \
(ptr)->next = (ptr); (ptr)->prev = (ptr);\
} while (0)
LIST_HEAD(name)宏用來(lái)定義一個(gè)鏈表頭，并使他的兩個(gè)指針都指向自己。我們可以在程序的變量聲明處，直接調(diào)用LIST_HEAD(name)宏，來(lái)定義并初始化一個(gè)名為name的鏈表。也可以先聲明一個(gè)鏈表，然后再使用INIT_LIST_HEAD來(lái)初始化這個(gè)鏈表。
也即：
復(fù)制代碼 代碼如下:
LIST_HEAD(mylist);
與
struct list_head mylist;
INIT_LIST_HEAD(mylist);
是等價(jià)的。
插入操作
復(fù)制代碼 代碼如下:
/*僅供內(nèi)部調(diào)用
* Insert a new entry between two known consecutive entries.
* This is only for internal list manipulation where we know
* the prev/next entries already!
*/
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;
}
復(fù)制代碼 代碼如下:
//在頭節(jié)點(diǎn)后面插入一個(gè)節(jié)點(diǎn)
static inline void list_add(struct list_head *new, struct list_head *head)
{
__list_add(new, head, head->next);
}
//在尾節(jié)點(diǎn)后插入一個(gè)節(jié)點(diǎn)
static inline void list_add_tail(struct list_head *new, struct list_head *head)
{
__list_add(new, head->prev, head);
}
刪除操作
復(fù)制代碼 代碼如下:
static inline void __list_del(struct list_head * prev, struct list_head * next)
{
next->prev = prev;
prev->next = next;
}
static inline void list_del(struct list_head *entry)
{
__list_del(entry->prev, entry->next);
}
刪除鏈表節(jié)點(diǎn)的操作很簡(jiǎn)單，是通過(guò)將要?jiǎng)h除的節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)與后一個(gè)節(jié)點(diǎn)鏈接到一起。
鏈表節(jié)點(diǎn)替換操作
復(fù)制代碼 代碼如下:
static inline void list_replace(struct list_head *old,
struct list_head *new)
{
new->next = old->next;
new->next->prev = new;
new->prev = old->prev;
new->prev->next = new;
}
鏈表遍歷操作（重點(diǎn)在這里）
首先來(lái)看一個(gè)如何根據(jù)鏈表節(jié)點(diǎn)地址得到其所在結(jié)構(gòu)體的地址。
復(fù)制代碼 代碼如下:
#define list_entry(ptr, type, member) container_of(ptr, type, member)
//container_of宏的定義如下：
#define container_of(ptr, type, member)({\
const typeof(((type *)0)->member ) *__mptr = (ptr);\
(type *)( (char *)__mptr - offsetof(type,member) );})
//offsetof的宏定義如下：
#define offsetof(TYPE, MEMBER) ((size_t) ((TYPE *)0)->MEMBER)
將上述簡(jiǎn)化一下成為下面這樣：
#define list_entry(ptr, type, member) \
((type *)((char *)(ptr)-(size_t)(((type *)0)->member)))
是一個(gè)帶3個(gè)參數(shù)的宏，該宏的作用是獲取鏈表節(jié)點(diǎn)(ptr)所在結(jié)構(gòu)體的起始地址。有了這個(gè)宏，我們只要知道某一個(gè)鏈表節(jié)點(diǎn)指針，就可以通過(guò)該鏈表節(jié)點(diǎn)得到其所在結(jié)構(gòu)體的指針，從而，我們遍歷鏈表，也便可以達(dá)到遍歷我們自己定義的結(jié)構(gòu)體。第一個(gè)參數(shù)為一個(gè)地址，他是結(jié)構(gòu)體鏈表節(jié)點(diǎn)元素的地址，第二個(gè)參數(shù)是結(jié)構(gòu)體類型，第三個(gè)參數(shù)是鏈表節(jié)點(diǎn)元素在結(jié)構(gòu)體中的名字。
來(lái)仔細(xì)分析一下這個(gè)宏：
最外面的一層括號(hào)可以去掉，這是為了防止宏擴(kuò)展的，去掉如下：
(type *) ((char *)(ptr)-(size_t)(((type *)0)->member))
現(xiàn)在就比較清楚了，首先(type *)是C強(qiáng)制轉(zhuǎn)換操作，就是將后面的的數(shù)據(jù)轉(zhuǎn)化成type結(jié)構(gòu)的指針。而后面的操作可以再分解
(char *)(ptr) - (size_t)(((type *)0)->member)
這樣就是一個(gè)減法的操作，前面是一個(gè)指針，我們傳過(guò)去的結(jié)構(gòu)體鏈表節(jié)點(diǎn)元素的指針，這里被轉(zhuǎn)化成指向字符的。而后面是一個(gè)整形，可以再分解
(size_t) (((type *)0)->member)
顯然這個(gè)整形是一個(gè)指針轉(zhuǎn)化的，而這個(gè)指針又可以再分解，
((type *)0)->member
可以看出這個(gè)指針是一個(gè)變量取地址得到的，這個(gè)變量又是什么呢
((type *)0)->member
看起來(lái)有點(diǎn)奇怪，不過(guò)這個(gè)操作是整個(gè)宏中最精妙的，他將地址0轉(zhuǎn)化成type類型，接下來(lái)又取得這個(gè)結(jié)構(gòu)的member元素，member就是我們傳進(jìn)來(lái)的參數(shù)：元素在結(jié)構(gòu)體中的命名。其實(shí)((type *)0)->member取的變量是內(nèi)容是什么一點(diǎn)都不重要，重要的我們要取這個(gè)變量的地址。取完這個(gè)地址將它轉(zhuǎn)換成size_t類型，這樣這個(gè)數(shù)據(jù)就是((type *)0)->member相對(duì)與地址0的偏移?；氐缴厦娴哪莻€(gè)減法，將結(jié)構(gòu)體中鏈表節(jié)點(diǎn)元素的地址與他與結(jié)構(gòu)體首地址的偏移相減，不就得到了結(jié)構(gòu)體的地址了嗎。)(((type *)0)->member)))
最外面的一層括號(hào)可以去掉，這是為了防止宏擴(kuò)展的，去掉如下：
(type *) ((char *)(ptr)-(size_t)(((type *)0)->member))
現(xiàn)在就比較清楚了，首先(type *)是C強(qiáng)制轉(zhuǎn)換操作，就是將后面的數(shù)據(jù)轉(zhuǎn)化成type結(jié)構(gòu)的指針。而后面的操作可以再分解
(char *)(ptr) - (size_t)(((type *)0)->member)
這樣就是一個(gè)減法的操作，前面是一個(gè)指針，我們傳過(guò)去的結(jié)構(gòu)體元素的指針，這里被轉(zhuǎn)化成指向字符的。而后面是一個(gè)長(zhǎng)整形，可以再分解
(size_t) (((type *)0)->member)
顯然這個(gè)長(zhǎng)整形是一個(gè)指針轉(zhuǎn)化的，而這個(gè)指針又可以再分解，
((type *)0)->member
可以看出這個(gè)指針是一個(gè)變量取地址得到的，這個(gè)變量又是什么呢?
((type *)0)->member
起來(lái)有點(diǎn)奇怪，不過(guò)這個(gè)操作是整個(gè)宏中最精妙的，他將地址0轉(zhuǎn)化成type類型，接下來(lái)又取得這個(gè)結(jié)構(gòu)的member元素，member就是我們傳進(jìn)來(lái)的參數(shù)：元素在結(jié)構(gòu)體中的命名。其實(shí)((type *)0)->member取的變量是內(nèi)容是什么一點(diǎn)都不重要，重要的我們要取這個(gè)變量的地址。取完這個(gè)地址將它轉(zhuǎn)換成size_t類型，這樣這個(gè)數(shù)據(jù)就是((type *)0)->member相對(duì)與地址0的偏移?；氐缴厦娴哪莻€(gè)減法，將結(jié)構(gòu)體中元素的地址與他與結(jié)構(gòu)體首地址的偏移相減，便得到了結(jié)構(gòu)體的地址了。
鏈表的遍歷操作時(shí)通過(guò)一個(gè)宏來(lái)實(shí)現(xiàn)的：
復(fù)制代碼 代碼如下:
#define list_for_each(pos, head) \
for(pos = (head)->next, prefetch(pos->next);pos!=(head);\
pos = pos->next,prefetch(pos->next))
其中prefetch是用于性能優(yōu)化，暫時(shí)不用去管它。
從上述鏈表遍歷宏可以看出，其只是一次獲得了鏈表節(jié)點(diǎn)指針，在實(shí)際應(yīng)用中，我們都需要獲取鏈表節(jié)點(diǎn)所在結(jié)構(gòu)體的數(shù)據(jù)項(xiàng)，因此，通常將list_for_each和list_entry一起使用。為此，linux的list實(shí)現(xiàn)提供了另外一個(gè)接口如下：
復(fù)制代碼 代碼如下:
#define list_for_each_entry(pos, head, member)\
for(pos = list_entry((head)->next, typeof(*pos), member);\
prefetch(pos->member.next), pos->member != (head);\
pos = list_entry(pos->member.next, typeof(*pos), member))
有了這個(gè)接口，我們就可以通過(guò)鏈表結(jié)構(gòu)來(lái)遍歷我們實(shí)際的結(jié)構(gòu)體數(shù)據(jù)域了。
例如，我們定義了一個(gè)結(jié)構(gòu)體如下：
復(fù)制代碼 代碼如下:
struct mystruct{
ElemType1 data1;
ElemType2 data2;
strcut list_head anchor;//通常我們稱結(jié)構(gòu)體內(nèi)的鏈表節(jié)點(diǎn)為鏈表錨，因?yàn)樗卸ㄎ坏淖饔谩?BR>}
那么我們遍歷鏈表的代碼如下：
復(fù)制代碼 代碼如下:
struct mystruct *pos;
list_for_each_entry(pos,head,anchor){
mystruct *pStruct=pos;
//do something with pStruct.....
}
此外Linux鏈表還提供了兩個(gè)對(duì)應(yīng)于基本遍歷操作的"_safe"接口：list_for_each_safe(pos, n, head)、list_for_each_entry_safe(pos, n, head, member)，它們要求調(diào)用者另外提供一個(gè)與pos同類型的指針n，在for循環(huán)中暫存pos下一個(gè)節(jié)點(diǎn)的地址，避免因pos節(jié)點(diǎn)被釋放而造成的斷鏈。
當(dāng)然，linux鏈表不止提供上述接口，還有
復(fù)制代碼 代碼如下:
list_for_each_prev(pos, head)
list_for_each_prev_safe(pos, n, head)
list_for_each_entry_reverse(pos, head, member)
list_prepare_entry(pos, head, member)
static inline int list_empty_careful(const struct list_head *head)
static inline void list_del_init(struct list_head *entry)
static inline void list_move(struct list_head *list, struct list_head *head)
static inline void list_move_tail(struct list_head *list,
struct list_head *head)
static inline int list_empty(const struct list_head *head)
您可能感興趣的文章:- Linux 內(nèi)核通用鏈表學(xué)習(xí)小結(jié)
- Linux中的內(nèi)核鏈表實(shí)例詳解
- Linux內(nèi)核設(shè)備驅(qū)動(dòng)之proc文件系統(tǒng)筆記整理
- Linux內(nèi)核設(shè)備驅(qū)動(dòng)之高級(jí)字符設(shè)備驅(qū)動(dòng)筆記整理
- Linux內(nèi)核設(shè)備驅(qū)動(dòng)之Linux內(nèi)核模塊加載機(jī)制筆記整理
- Linux內(nèi)核設(shè)備驅(qū)動(dòng)地址映射筆記整理
- Linux內(nèi)核設(shè)備驅(qū)動(dòng)之Linux內(nèi)核基礎(chǔ)筆記整理
- 增強(qiáng)Linux內(nèi)核中訪問(wèn)控制安全的方法
- Linux 內(nèi)核空間與用戶空間實(shí)現(xiàn)與分析
- 詳解Linux內(nèi)核進(jìn)程調(diào)度函數(shù)schedule()的觸發(fā)和執(zhí)行時(shí)機(jī)
- Linux內(nèi)核設(shè)備驅(qū)動(dòng)之內(nèi)核中鏈表的使用筆記整理
