list_add_tail

再看內(nèi)核另外一種插入方式，本質(zhì)都是調(diào)用__lis_add。不同的是，一個(gè)是頭部插入，一個(gè)是尾部插入。

?

/**
?*?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);
}

?

我們還是以示例輔助說(shuō)明：

首先創(chuàng)建一個(gè)鏈表頭：

?

LIST_HEAD(listHead);

?

然后創(chuàng)建第一個(gè)節(jié)點(diǎn)

?

struct?my_data_list?first_data?=
{?
????.val?=?1,
????.list?=?LIST_HEAD_INIT(first_data.list),
};

?

插入第一個(gè)節(jié)點(diǎn)：

?

list_add_tail(&first_data.list,?listHead);

?

緊接著插入第二個(gè)節(jié)點(diǎn)：

?

struct?my_data_list?second_data?=
{?
????.val?=?2,
????/*?也可以調(diào)用接口?初始化*/
????.list?=?LIST_HEAD_INIT(second_data.list),
};

list_add_tail(&second_data.list,?&listHead);

?

示意圖如下：

每次插入的新節(jié)點(diǎn)都是緊挨著 header 表尾，而插入的第一個(gè)節(jié)點(diǎn)排在了第一位，第二個(gè)排在了第二位。

先插入的節(jié)點(diǎn)排在前面，后插入的節(jié)點(diǎn)排在后面，“先進(jìn)先出，后進(jìn)后出”（First in First out,FIFO）！這不就是隊(duì)列嗎？

總結(jié)

由于是雙循環(huán)鏈表，看起來(lái)尾部插入和頭部插入是一樣的，其實(shí)不然。

我們?cè)賮?lái)對(duì)比尾部和頭部插入的區(qū)別：

頭部插入，結(jié)構(gòu)是逆序，屬于先進(jìn)后出，最主要的區(qū)別就是頭節(jié)點(diǎn)的prev指針指向第一個(gè)節(jié)點(diǎn)。

尾部插入，結(jié)構(gòu)是順序，屬于FIFO結(jié)構(gòu)，最主要的區(qū)別就是頭節(jié)點(diǎn)的next指針指向第一個(gè)節(jié)點(diǎn)。

list_add：頭部插入一個(gè)節(jié)點(diǎn)

list_add_tail：尾部插入一個(gè)節(jié)點(diǎn)

2.4 刪除節(jié)點(diǎn)

內(nèi)核同樣定義了刪除節(jié)點(diǎn)的接口 list_del

list_del：

?

static?inline?void?list_del(struct?list_head?*entry)
{
????/*?__list_del_entry(entry)?也行*/
?  __list_del(entry->prev,?entry->next);
????
????/*?指向特定的位置，反初始化?*/
?  entry->next?=?LIST_POISON1;
?  entry->prev?=?LIST_POISON2;
}

?

__list_del：這個(gè)接口，根據(jù)prev/next 刪除其節(jié)點(diǎn)，刪除的節(jié)點(diǎn)必須是已知的并且 prev 和 next 不為空

?

/*
?*?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_entry：刪除一個(gè)節(jié)點(diǎn)。

?

/**
?*?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.
?*/
static?inline?void?__list_del_entry(struct?list_head?*entry)
{
?  __list_del(entry->prev,?entry->next);
}

/**
?*?list_del_init?-?deletes?entry?from?list?and?reinitialize?it.
?*?@entry:?the?element?to?delete?from?the?list.
?*/
static?inline?void?list_del_init(struct?list_head?*entry)
{
?__list_del_entry(entry);
?INIT_LIST_HEAD(entry);
}

?

利用list_del(struct list_head *entry) 接口就可以刪除鏈表中的任意節(jié)點(diǎn)了，需注意，前提條件是這個(gè)節(jié)點(diǎn)是已知的，既在鏈表中真實(shí)存在，切prev，next指針都不為NULL。

被剔除下來(lái)的 my_data_list.list，prev、next 指針?lè)謩e被設(shè)為 LIST_POSITION2和LIST_POSITION1兩個(gè)特殊值，這樣設(shè)置是為了保證不在鏈表中的節(jié)點(diǎn)項(xiàng)不可訪問(wèn)–對(duì)LIST_POSITION1和LIST_POSITION2的訪問(wèn)都將引起頁(yè)故障。

與之相對(duì)應(yīng)，list_del_init()函數(shù)將節(jié)點(diǎn)從鏈表中解下來(lái)之后，調(diào)用LIST_INIT_HEAD()將節(jié)點(diǎn)置為空鏈狀態(tài)。

list_del() 和 list_del_init 是外部接口。__list_del() 和 __list_entry() 是內(nèi)核內(nèi)部節(jié)點(diǎn)。

list_del() 作用是刪除雙鏈表中的一個(gè)節(jié)點(diǎn)。并將節(jié)點(diǎn)的prev和next都指向特定位置，LIST_POSITION1和LIST_POSITION2。

list_del_init() 作用是刪除雙鏈表中的一個(gè)節(jié)點(diǎn)，并將節(jié)點(diǎn)的prev和next都指向自己，回到最開(kāi)始創(chuàng)建節(jié)點(diǎn)前的狀態(tài)。

2.5 搬移

內(nèi)核提供了將原本屬于一個(gè)鏈表的節(jié)點(diǎn)移動(dòng)到另一個(gè)鏈表的操作，并根據(jù)插入到新鏈表的位置分為兩類(lèi)：頭部搬移和尾部搬移。搬移的本質(zhì)就是刪除加插入。

頭部搬移

?

/**
?*?list_move?-?delete?from?one?list?and?add?as?another's?head
?*?@list:?the?entry?to?move
?*?@head:?the?head?that?will?precede?our?entry
?*/
static?inline?void?list_move(struct?list_head?*list,?struct?list_head?*head)
{
?  __list_del_entry(list);
?  list_add(list,?head);
}

?

尾部搬移

?

/**
?*?list_move_tail?-?delete?from?one?list?and?add?as?another's?tail
?*?@list:?the?entry?to?move
?*?@head:?the?head?that?will?follow?our?entry
?*/
static?inline?void?list_move_tail(struct?list_head?*list,
??????struct?list_head?*head)
{
?  __list_del_entry(list);
?  list_add_tail(list,?head);
}

?

2.6 合并

內(nèi)核還提供兩組合并操作，將兩條鏈表合并在一起。

當(dāng) list1 被掛接到 list2 之后，作為原表頭指針的 list1 的next、prev仍然指向原來(lái)的節(jié)點(diǎn)，為了避免引起混亂，Linux提供了一個(gè)list_splice_init()函數(shù).該函數(shù)在將list合并到head鏈表的基礎(chǔ)上，調(diào)用INIT_LIST_HEAD(list)將list設(shè)置為空鏈。

?

static?inline?void?list_splice(const?struct?list_head?*list,?struct?list_head?*head);
static?inline?void?list_splice_init(struct?list_head?*list,?struct?list_head?*head);
static?inline?void?list_splice_tail(const?struct?list_head?*list,?struct?list_head?*head);
static?inline?void?list_splice_tail_init(struct?list_head?*list,?struct?list_head?*head);

?

示意圖如下：

另外一種方式類(lèi)似，只不過(guò)合并時(shí)斷開(kāi)的位置有所不同

2.7 替換

內(nèi)核還提供一組替換鏈表節(jié)點(diǎn)的操作。list_replace：將新的節(jié)點(diǎn)替換到舊的節(jié)點(diǎn)上。list_replace_init：將新的節(jié)點(diǎn)替換到舊的節(jié)點(diǎn)上。同時(shí)將舊的節(jié)點(diǎn)的prev和next指向自己，反初始化

?

static?inline?void?list_replace(struct?list_head?*old,?struct?list_head?*new);
static?inline?void?list_replace_init(struct?list_head?*old,?struct?list_head?*new);

?

2.8?遍歷操作

內(nèi)核提供了一組宏進(jìn)行遍歷操作。經(jīng)過(guò)一系列的增刪減改操作，我們終于到了遍歷的時(shí)候。

list_entry 宏

重頭戲來(lái)了，遍歷的關(guān)鍵就是這個(gè)list_entry 宏。本質(zhì)就是container_of 宏。

具體分析見(jiàn)上一篇文章。這個(gè)宏的主要作用就是獲取宿主結(jié)構(gòu)的指針地址。

前文提到，我們是以list 指針為節(jié)點(diǎn)組成的一條雙鏈表，遍歷的過(guò)程中只能得到list的地址，那么對(duì)于其所有者地址就是通過(guò)這個(gè)宏獲取的。

?

/**
*?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)

/*?根據(jù)list?倒推?my_list_data*/
list_entry(&my_list_data.list,?typeof(&my_list_data),?list)

?

list_for_each

list_for_each 它實(shí)際上是一個(gè)for循環(huán)，利用傳入的pos作為循環(huán)變量，從表頭head開(kāi)始，逐項(xiàng)向后（next方向）移動(dòng)pos，直至又回到head

?

/**
?*?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)

?

list_for_each_entry

遍歷每一個(gè)list,然后獲取其宿主結(jié)構(gòu)地址.

?

/**
?*?list_for_each_entry?-?iterate?over?list?of?given?type
?*?@pos:?the?type?*?to?use?as?a?loop?cursor.
?*?@head:?the?head?for?your?list.
?*?@member:?the?name?of?the?list_struct?within?the?struct.
?*/
#define?list_for_each_entry(pos,?head,?member)????
?for?(pos?=?list_entry((head)->next,?typeof(*pos),?member);?
??????&pos->member?!=?(head);??
??????pos?=?list_entry(pos->member.next,?typeof(*pos),?member))

?

list_for_each_prev

反向遍歷得到list.

?

/**
?*?list_for_each_prev?-?iterate?over?a?list?backwards
?*?@pos:?the?&struct?list_head?to?use?as?a?loop?cursor.
?*?@head:?the?head?for?your?list.
?*/
#define?list_for_each_prev(pos,?head)?
?for?(pos?=?(head)->prev;?pos?!=?(head);?pos?=?pos->prev)

?

list_for_each_entry_reverse

反向遍歷得到list,然后獲取其宿主結(jié)構(gòu)地址。

?

/**
*?list_for_each_entry_reverse?-?iterate?backwards?over?list?of?given?type.
*?@pos:?the?type?*?to?use?as?a?loop?cursor.
*?@head:?the?head?for?your?list.
*?@member:?the?name?of?the?list_struct?within?the?struct.
*/
#define?list_for_each_entry_reverse(pos,?head,?member)???
???for?(pos?=?list_entry((head)->prev,?typeof(*pos),?member);?
????????&pos->member?!=?(head);??
????????pos?=?list_entry(pos->member.prev,?typeof(*pos),?member))

?

3. 總結(jié)

本文詳細(xì)分析了 linux 內(nèi)核 中的雙鏈表結(jié)構(gòu)，以圖文的方式旨在幫助大家理解。

當(dāng)然還有很多接口限于篇幅沒(méi)有介紹，本文只列出了常用了接口，相信只要理解了前面雙鏈表的組成和插入過(guò)程，后面的刪除和遍歷就自然而然通了。

　　審核編輯：湯梓紅