介紹下linux內(nèi)核的雙向鏈表的使用，接口定義在include/linux/list.h

結(jié)構(gòu)體

struct list_head {
    struct list_head *next;  // 指向下一個(gè)節(jié)點(diǎn)
    struct list_head *prev;  // 指向前一個(gè)節(jié)點(diǎn)
};

使用的時(shí)候，會(huì)把這個(gè)結(jié)構(gòu)體放在需要使用鏈表的結(jié)構(gòu)體里，放在結(jié)構(gòu)體里的任意位置都可以，讀取數(shù)據(jù)的時(shí)候，是從鏈表里拿到node后，通過(guò)container_of拿到node所在結(jié)構(gòu)體的地址，根據(jù)這個(gè)地址再來(lái)找結(jié)構(gòu)體里的其他成員。

所以，同一個(gè)鏈表里，是根據(jù)node把存放的內(nèi)容關(guān)聯(lián)串起來(lái)，再根據(jù)node拿到內(nèi)容的，而不關(guān)心這些node所在的內(nèi)容的結(jié)構(gòu)體是不是同一個(gè)結(jié)構(gòu)體。

struct zslnode {
    int seq;
    struct list_head node;
};

struct zslnode1 {
    int seq;  
    struct list_head node1;
    int seq1;
};

初始化

初始化有多種方式，常見(jiàn)的有LIST_HEAD_INIT和INIT_LIST_HEAD

作用是常見(jiàn)一個(gè)struct list_head變量，把里面的next和prev都指向自己。

增加

常用的增加分為兩種接口，往前增加list_add，往后增加list_add_tail。這倆接口都是調(diào)用的__list_add實(shí)現(xiàn)的，往前增加是__list_add(new, head, head->next)，往后是__list_add(new, head->prev, head)。

__list_add主要就是如下操作：

       next->prev = new;
       new->next = next;
       new->prev = prev;
       WRITE_ONCE(prev->next, new);

所以，增加節(jié)點(diǎn)其實(shí)就是在原來(lái)鏈表的的head->prev、head和head->next三個(gè)之間去增加。

head本身不存在鏈表上（即在head上去存數(shù)據(jù)遍歷的時(shí)候是取不到的），像是把雙向鏈表的首尾連接起來(lái)的節(jié)點(diǎn)，head->next永遠(yuǎn)指向鏈表第一個(gè)節(jié)點(diǎn)，head->prev指向最后一個(gè)節(jié)點(diǎn)。

這樣就容易理解__list_add里的賦值操作，去掉prev和next之間的聯(lián)系，然后把new增加到prev和next中間。

往前增加參數(shù)里prev是head，即首尾相連的點(diǎn)，next是head->next即鏈表第一位，new增加到中間就變成了鏈表第一位。

往后增加prev是鏈表最后一位，next是首尾相連的點(diǎn)，new增加到中間就變成了鏈表最后一位。

刪除

刪除常用的是list_del，最終調(diào)用的是__list_del，主要操作如下:

       next->prev = prev;
       WRITE_ONCE(prev->next, next);

即，后面一個(gè)節(jié)點(diǎn)的prev指向前面一個(gè)節(jié)點(diǎn)，前面一個(gè)節(jié)點(diǎn)的next指向后面。

遍歷

遍歷常用的是list_for_each_entry正向遍歷，list_for_each_entry_reverse反向遍歷,也還有不少別的變種，基本差不多。

       list_for_each_entry定義如下
       #define list_for_each_entry(pos, head, member)                           \
       for (pos = list_first_entry(head, typeof(*pos), member);   \
            !list_entry_is_head(pos, head, member);                 \
            pos = list_next_entry(pos, member))

找到第一個(gè)節(jié)點(diǎn)，然后一路next查找。第一個(gè)節(jié)點(diǎn)，前面有提到就是head->next，再通過(guò)list_entry拿結(jié)構(gòu)體地址，list_entry就是使用的container_of。

反向遍歷就是反過(guò)來(lái)，查找最后一個(gè)節(jié)點(diǎn)，即head->prev，然后一路prev往前查找node。

直到遍歷到list_entry_is_head停止，即發(fā)現(xiàn)自己就是head，&pos->member == (head)，這里&pos->member就是存儲(chǔ)的結(jié)構(gòu)體里指向node的地址。

實(shí)例

struct zslnode {
    int seq;
    struct list_head node;
};

struct zslnode1 {
    int seq1;	
    struct list_head node1;
    int seq2;
};

static void testlist(void)
{
	struct list_head list;
	struct zslnode next1;
	struct zslnode next2;	
	struct zslnode1 next3;
	struct zslnode pre1;	
	struct zslnode pre2;

	struct zslnode *tmpnode;
	struct zslnode1 *tmpnode1;

	INIT_LIST_HEAD(&list);

	next1.seq = 101;
	list_add_tail(&next1.node, &list);

	next2.seq = 102;
	list_add_tail(&next2.node, &list);

	next3.seq1 = 1000;
	next3.seq2 = 2000;
	list_add_tail(&next3.node1, &list);

	pre1.seq = 99;
	list_add(&pre1.node, &list);

	pre2.seq = 98;
	list_add(&pre2.node, &list);

	list_for_each_entry(tmpnode, &list, node) 
	{
		printk(KERN_INFO "tlist: seq:%d\n",tmpnode->seq);
	}

	list_del(&next2.node);

	list_for_each_entry(tmpnode1, &list, node1) 
	{
		printk(KERN_INFO "tlist1: seq:%d %d\n",tmpnode1->seq1,tmpnode1->seq2);
	}

}

運(yùn)行結(jié)果如下

注意事項(xiàng)

• 從掃描的邏輯來(lái)看，head的節(jié)點(diǎn)是不能被掃描到的，雖然只有head存在的話，能拿到數(shù)據(jù)（那是因?yàn)閔ead->next=head）。
• 從實(shí)例運(yùn)行結(jié)果tlist1的打印可以看到不同的結(jié)構(gòu)體可以放在一起處理，但是會(huì)出現(xiàn)內(nèi)存越界的情況，讀到不可控的內(nèi)容。
• List的內(nèi)容存放，都是用指針存放的，所以如果鏈表是全局變量的話，里面的節(jié)點(diǎn)也必須是全局或者靜態(tài)變量，不能是棧里的內(nèi)容，不然會(huì)有指針踩飛導(dǎo)致崩潰等問(wèn)題。

總結(jié)

以上為個(gè)人經(jīng)驗(yàn)，希望能給大家一個(gè)參考，也希望大家多多支持腳本之家。