玩轉(zhuǎn)內(nèi)核鏈表list_head，如何管理不同類型節(jié)點的實現(xiàn)（萬字文）可以收藏

時間：2020-09-08 23:32:31

關(guān)鍵字：內(nèi)核節(jié)點

手機看文章

掃描二維碼
隨時隨地手機看文章

[導(dǎo)讀]? 在Linux內(nèi)核中，提供了一個用來創(chuàng)建雙向循環(huán)鏈表的結(jié)構(gòu) list_head。雖然linux內(nèi)核是用C語言寫的，但是list_head的引入，使得內(nèi)核數(shù)據(jù)結(jié)構(gòu)也可以擁有面向?qū)ο蟮奶匦?，通過使用操作list_head 的通用接口很容易實現(xiàn)代碼的重用，有點類似于C++的繼承機制（希望

在Linux內(nèi)核中，提供了一個用來創(chuàng)建雙向循環(huán)鏈表的結(jié)構(gòu) list_head。雖然linux內(nèi)核是用C語言寫的，但是list_head的引入，使得內(nèi)核數(shù)據(jù)結(jié)構(gòu)也可以擁有面向?qū)ο蟮奶匦?，通過使用操作list_head 的通用接口很容易實現(xiàn)代碼的重用，有點類似于C++的繼承機制（希望有機會寫篇文章研究一下C語言的面向?qū)ο髾C制）。

首先找到list_head結(jié)構(gòu)體定義，kernel/inclue/linux/types.h 如下：

struct list_head { struct list_head *next, *prev;};#define LIST_HEAD_INIT(name) { &(name), &(name) }

需要注意的一點是，頭結(jié)點head是不使用的，這點需要注意。

使用list_head組織的鏈表的結(jié)構(gòu)如下圖所示：

然后就開始圍繞這個結(jié)構(gòu)開始構(gòu)建鏈表，然后插入、刪除節(jié)點，遍歷整個鏈表等等，其實內(nèi)核已經(jīng)提供好了現(xiàn)成的接口，接下來就讓我們進入 kernel/include/linux/list.h中：

一. 創(chuàng)建鏈表

內(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){ WRITE_ONCE(list->next, list); list->prev = list;}

如：可以通過 LIST_HEAD(mylist) 進行初始化一個鏈表，mylist的prev 和 next 指針都是指向自己。

structlist_head mylist = {&mylist, &mylist} ;

但是如果只是利用mylist這樣的結(jié)構(gòu)體實現(xiàn)鏈表就沒有什么實際意義了，因為正常的鏈表都是為了遍歷結(jié)構(gòu)體中的其它有意義的字段而創(chuàng)建的，而我們mylist中只有 prev和next指針，卻沒有實際有意義的字段數(shù)據(jù)，所以毫無意義。

綜上，我們可以創(chuàng)建一個宿主結(jié)構(gòu)，然后在此結(jié)構(gòu)中再嵌套mylist字段，宿主結(jié)構(gòu)又有其它的字段（進程描述符 task_struct，頁面管理的page結(jié)構(gòu)，等就是采用這種方法創(chuàng)建鏈表的）。為簡便理解，定義如下：

struct mylist{ int type; char name[MAX_NAME_LEN]; struct list_head list;}

創(chuàng)建鏈表，并初始化

structlist_head myhead; INIT_LIST_HEAD(&myhead);

這樣我們的鏈表就初始化完畢，鏈表頭的myhead就prev 和 next指針分別指向myhead自己了，如下圖：

二. 添加節(jié)點

內(nèi)核已經(jīng)提供了添加節(jié)點的接口了

1. list_add

如下所示。根據(jù)注釋可知，是在鏈表頭head后方插入一個新節(jié)點new。

/** * 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. */static inline void list_add(struct list_head *new, struct list_head *head){ __list_add(new, head, head->next);}

list_add再調(diào)用__list_add接口

/* * 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){ if (!__list_add_valid(new, prev, next)) return;
 next->prev = new; new->next = next; new->prev = prev; WRITE_ONCE(prev->next, new);}

其實就是在myhead鏈表頭后和鏈表頭后第一個節(jié)點之間插入一個新節(jié)點。然后這個新的節(jié)點就變成了鏈表頭后的第一個節(jié)點了。

接著上面步驟創(chuàng)建1個節(jié)點然后插入到myhead之后

struct mylist node1;node1.type = I2C_TYPE;strcpy(node1.name,"yikoulinux");list_add(&node1.list,&myhead);

然后在創(chuàng)建第二個節(jié)點，同樣把它插入到header_task之后

struct mylist node2;node2.type = I2C_TYPE;strcpy(node2.name,"yikoupeng");list_add(&node2.list,&myhead);

list_add

以此類推，每次插入一個新節(jié)點，都是緊靠著header節(jié)點，而之前插入的節(jié)點依次排序靠后，那最后一個節(jié)點則是第一次插入header后的那個節(jié)點。最終可得出：先來的節(jié)點靠后，而后來的節(jié)點靠前，“先進后出，后進先出”。所以此種結(jié)構(gòu)類似于 stack“堆?！?，而header_task就類似于內(nèi)核stack中的棧頂指針esp，它都是緊靠著最后push到棧的元素。

2. list_add_tail 接口

上面所講的list_add接口是從鏈表頭header后添加的節(jié)點。同樣，內(nèi)核也提供了從鏈表尾處向前添加節(jié)點的接口list_add_tail.讓我們來看一下它的具體實現(xiàn)。

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

從注釋可得出：（1）在一個特定的鏈表頭前面插入一個節(jié)點

（2）這個方法很適用于隊列的實現(xiàn)（why？）

進一步把__list_add（）展開如下：

/* * 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){ if (!__list_add_valid(new, prev, next)) return;
 next->prev = new; new->next = next; new->prev = prev; WRITE_ONCE(prev->next, new);}

所以，很清楚明了， list_add_tail就相當(dāng)于在鏈表頭前方依次插入新的節(jié)點（也可理解為在鏈表尾部開始插入節(jié)點，此時，header節(jié)點既是為節(jié)點，保持不變）

利用上面分析list_add接口的方法可畫出數(shù)據(jù)結(jié)構(gòu)圖形如下。

（1）創(chuàng)建一個鏈表頭（實際上應(yīng)該是表尾）代碼參考第一節(jié);

（2）插入第一個節(jié)點 node1.list , 調(diào)用

 struct mylist node1; node1.type = I2C_TYPE; strcpy(node1.name,"yikoulinux"); list_add_tail(&node1.list,&myhead);

(3) 插入第二個節(jié)點node2.list，調(diào)用

struct mylist node2; node2.type = I2C_TYPE; strcpy(node2.name,"yikoupeng"); list_add_tail(&node2.list,&myhead);

list_add_tail

依此類推，每次插入的新節(jié)點都是緊挨著 header_task表尾，而插入的第一個節(jié)點my_first_task排在了第一位，my_second_task排在了第二位，可得出：先插入的節(jié)點排在前面，后插入的節(jié)點排在后面，“先進先出，后進后出”，這不正是隊列的特點嗎（First in First out）！

三. 刪除節(jié)點

內(nèi)核同樣在list.h文件中提供了刪除節(jié)點的接口 list_del()，讓我們看一下它的實現(xiàn)流程

static inline void list_del(struct list_head *entry){ __list_del_entry(entry); entry->next = LIST_POISON1; entry->prev = LIST_POISON2;}/* * 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; WRITE_ONCE(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. */static inline void __list_del_entry(struct list_head *entry){ if (!__list_del_entry_valid(entry)) return;
 __list_del(entry->prev, entry->next);}

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

四. 鏈表遍歷

內(nèi)核是同過下面這個宏定義來完成對list_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_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.h 中也提供了list_replace(節(jié)點替換) list_move(節(jié)點移位) ，翻轉(zhuǎn)，查找等接口，這里就不在一一分析了。

五. 宿主結(jié)構(gòu)

1.找出宿主結(jié)構(gòu) list_entry(ptr, type, member)

上面的所有操作都是基于list_head這個鏈表進行的，涉及的結(jié)構(gòu)體也都是:

struct list_head { struct list_head *next, *prev;};

其實，正如文章一開始所說，我們真正更關(guān)心的是包含list_head這個結(jié)構(gòu)體字段的宿主結(jié)構(gòu)體，因為只有定位到了宿主結(jié)構(gòu)體的起始地址，我們才能對對宿主結(jié)構(gòu)體中的其它有意義的字段進行操作。

struct mylist{  int type; char name[MAX_NAME_LEN]; struct list_head list; };

那我們?nèi)绾胃鶕?jù)list這個字段的地址而找到宿主結(jié)構(gòu)node1的位置呢？list.h中定義如下：

/** * 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_head within the struct. */#define list_entry(ptr, type, member) \ container_of(ptr, type, member)

list.h中提供了list_entry宏來實現(xiàn)對應(yīng)地址的轉(zhuǎn)換，但最終還是調(diào)用了container_of宏，所以container_of宏的偉大之處不言而喻。

2 container_of

做linux驅(qū)動開發(fā)的同學(xué)是不是想到了LDD3這本書中經(jīng)常使用的一個非常經(jīng)典的宏定義！

container_of(ptr, type, member)

在LDD3這本書中的第三章字符設(shè)備驅(qū)動，以及第十四章驅(qū)動設(shè)備模型中多次提到，我覺得這個宏應(yīng)該是內(nèi)核最經(jīng)典的宏之一。那接下來讓我們揭開她的面紗：

此宏在內(nèi)核代碼 kernel/include/linux/kernel.h中定義（此處kernel版本為3.10；新版本4.13之后此宏定義改變，但實現(xiàn)思想保持一致）

而offsetof定義在 kernel/include/linux/stddef.h ，如下：

舉個例子，來簡單分析一下container_of內(nèi)部實現(xiàn)機制。

例如:

struct test{ int a; short b; char c;};struct test *p = (struct test *)malloc(sizeof(struct test));test_function(&(p->b));
int test_function(short *addr_b){ //獲取struct test結(jié)構(gòu)體空間的首地址 struct test *addr; addr = container_of(addr_b,struct test,b);}

展開container_of宏，探究內(nèi)部的實現(xiàn):

typeof ( ( (struct test *)0 )->b ) ; (1)typeof ( ( (struct test *)0 )->b ) *__mptr = addr_b ; (2)(struct test *)( (char *)__mptr - offsetof(struct test,b)) (3)

(1) 獲取成員變量b的類型 ,這里獲取的就是short 類型。這是GNU_C的擴展語法。

(2) 用獲取的變量類型，定義了一個指針變量 __mptr ,并且將成員變量 b的首地址賦值給它

(3) 這里的offsetof(struct test,b)是用來計算成員b在這個struct test 結(jié)構(gòu)體的偏移。__mptr

是成員b的首地址, 現(xiàn)在減去成員b在結(jié)構(gòu)體里面的偏移值，算出來的是不是這個結(jié)構(gòu)體的

首地址呀。

3. 宿主結(jié)構(gòu)的遍歷

我們可以根據(jù)結(jié)構(gòu)體中成員變量的地址找到宿主結(jié)構(gòu)的地址，并且我們可以對成員變量所建立的鏈表進行遍歷，那我們是不是也可以通過某種方法對宿主結(jié)構(gòu)進行遍歷呢？

答案肯定是可以的，內(nèi)核在list.h中提供了下面的宏：

/** * 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_head within the struct. */#define list_for_each_entry(pos, head, member) \ for (pos = list_first_entry(head, typeof(*pos), member); \ &pos->member != (head); \ pos = list_next_entry(pos, member))

其中，list_first_entry 和 list_next_entry宏都定義在list.h中，分別代表：獲取第一個真正的宿主結(jié)構(gòu)的地址；獲取下一個宿主結(jié)構(gòu)的地址。它們的實現(xiàn)都是利用list_entry宏。

/** * list_first_entry - get the first element from a list * @ptr: the list head to take the element from. * @type: the type of the struct this is embedded in. * @member: the name of the list_head within the struct. * * Note, that list is expected to be not empty. */#define list_first_entry(ptr, type, member) \ list_entry((ptr)->next, type, member)
/** * list_next_entry - get the next element in list * @pos: the type * to cursor * @member: the name of the list_head within the struct. */#define list_next_entry(pos, member) \ list_entry((pos)->member.next, typeof(*(pos)), member)

最終實現(xiàn)了宿主結(jié)構(gòu)的遍歷

#define list_for_each_entry(pos, head, member) \ for (pos = list_first_entry(head, typeof(*pos), member); \ &pos->member != (head); \ pos = list_next_entry(pos, member))

首先pos定位到第一個宿主結(jié)構(gòu)地址，然后循環(huán)獲取下一個宿主結(jié)構(gòu)地址，如果查到宿主結(jié)構(gòu)中的member成員變量（宿主結(jié)構(gòu)中struct list_head定義的字段）地址為head，則退出，從而實現(xiàn)了宿主結(jié)構(gòu)的遍歷。如果要循環(huán)對宿主結(jié)構(gòu)中的其它成員變量進行操作，這個遍歷操作就顯得特別有意義了。

我們用上面的 nod結(jié)構(gòu)舉個例子：

struct my_list *pos_ptr = NULL ; list_for_each_entry (pos_ptr, &myhead, list ) {  printk ("val = %d\n" , pos_ptr->val); }

實例1 一個簡單的鏈表的實現(xiàn)

為方便起見，本例把內(nèi)核的list.h文件單獨拷貝出來，這樣就可以獨立于內(nèi)核來編譯測試。

功能描述：

本例比較簡單，僅僅實現(xiàn)了單鏈表節(jié)點的創(chuàng)建、刪除、遍歷。

#include "list.h" #include <stdio.h> #include <string.h>
#define MAX_NAME_LEN 32#define MAX_ID_LEN 10
struct list_head myhead;
#define I2C_TYPE 1#define SPI_TYPE 2
char *dev_name[]={ "none", "I2C", "SPI"};
struct mylist{  int type; char name[MAX_NAME_LEN]; struct list_head list; };
void display_list(struct list_head *list_head){ int i=0; struct list_head *p; struct mylist *entry; printf("-------list---------\n"); list_for_each(p,list_head) { printf("node[%d]\n",i++); entry=list_entry(p,struct mylist,list); printf("\ttype: %s\n",dev_name[entry->type]); printf("\tname: %s\n",entry->name); } printf("-------end----------\n");}
int main(void){
 struct mylist node1; struct mylist node2;
 INIT_LIST_HEAD(&myhead);
 node1.type = I2C_TYPE; strcpy(node1.name,"yikoulinux");
 node2.type = I2C_TYPE; strcpy(node2.name,"yikoupeng");
 list_add(&node1.list,&myhead); list_add(&node2.list,&myhead);
 display_list(&myhead);
 list_del(&node1.list);
 display_list(&myhead); return 0;}

運行結(jié)果

實例2 如何在一個鏈表上管理不同類型的節(jié)點

功能描述：

本實例主要實現(xiàn)在同一個鏈表上管理兩個不同類型的節(jié)點，實現(xiàn)增刪改查的操作。

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

一個鏈表要想?yún)^(qū)分節(jié)點的不同類型，那么節(jié)點中必須要有信息能夠區(qū)分該節(jié)點類型，為了方便節(jié)點擴展，我們參考Linux內(nèi)核，定義一個統(tǒng)一類型的結(jié)構(gòu)體：

struct device{ int type; char name[MAX_NAME_LEN]; struct list_head list;};

其中成員type表示該節(jié)點的類型：

#defineI2C_TYPE 1 #define SPI_TYPE 2

有了該結(jié)構(gòu)體，我們要定義其他類型的結(jié)構(gòu)體只需要包含該結(jié)構(gòu)體即可，這個思想有點像面向?qū)ο笳Z言的基類，后續(xù)派生出新的屬性叫子類，說到這，一口君又忍不住想挖個坑，寫一篇如何用C語言實現(xiàn)面向?qū)ο笏枷氲睦^承、多態(tài)、interface。

下面我們定義2種類型的結(jié)構(gòu)體：

i2c這種類型設(shè)備的專用結(jié)構(gòu)體：

struct i2c_node{ int data; unsigned int reg; struct device dev;};

spi這種類型設(shè)備的專用結(jié)構(gòu)體：

struct spi_node{  unsigned int reg; struct device dev;};

我特意讓兩個結(jié)構(gòu)體大小類型不一致。

結(jié)構(gòu)類型

鏈表頭結(jié)點定義

structlist_head device_list;

根據(jù)之前我們講解的思想，這個鏈表鏈接起來后，應(yīng)該是以下這種結(jié)構(gòu)：

節(jié)點的插入

我們定義的節(jié)點要插入鏈表仍然是要依賴list_add（），既然我們定義了struct device這個結(jié)構(gòu)體，那么我們完全可以參考linux內(nèi)核，針對不同的節(jié)點封裝函數(shù)，要注冊到這個鏈表只需要調(diào)用該函數(shù)即可。

實現(xiàn)如下：

設(shè)備i2c的注冊函數(shù)如下：

void i2c_register_device(struct device*dev){ dev.type = I2C_TYPE; strcpy(dev.name,"yikoulinux"); list_add(&dev->list,&device_list); }

設(shè)備spi的注冊函數(shù)如下：

void spi_register_device(struct device*dev){ dev.type = SPI_TYPE; strcpy(dev.name,"yikoupeng"); list_add(&dev->list,&device_list); }

我們可以看到注冊函數(shù)功能是填充了struct device 的type和name成員，然后再調(diào)用list_add（）注冊到鏈表中。這個思想很重要，因為Linux內(nèi)核中許許多多的設(shè)備節(jié)點也是這樣添加到其他的鏈表中的。要想讓自己的C語言編程能力得到質(zhì)的提升，一定要多讀內(nèi)核代碼，即使看不懂也要堅持看，古人有云：代碼讀百遍其義自見。

節(jié)點的刪除

同理，節(jié)點的刪除，我們也統(tǒng)一封裝成函數(shù)，同樣只傳遞參數(shù)device即可：

void i2c_unregister_device(struct device *device){// struct i2c_node *i2c_device=container_of(dev, struct i2c_node, dev); list_del(&device->list);}void spi_unregister_device(struct device *device){// struct spi_node *spi_device=container_of(dev, struct spi_node, dev); list_del(&device->list);}

在函數(shù)中，可以用container_of提取出了設(shè)備節(jié)點的首地址，實際使用中可以根據(jù)設(shè)備的不同釋放不同的資源。

宿主結(jié)構(gòu)的遍歷

節(jié)點的遍歷，在這里我們通過設(shè)備鏈表device_list開始遍歷，假設(shè)該節(jié)點名是node，通過list_for_each（）可以得到node->dev->list的地址，然后利用container_of 可以得到node->dev、node的地址。

void display_list(struct list_head *list_head){ int i=0; struct list_head *p; struct device *entry;
 printf("-------list---------\n"); list_for_each(p,list_head) { printf("node[%d]\n",i++); entry=list_entry(p,struct device,list);
 switch(entry->type) { case I2C_TYPE: display_i2c_device(entry); break; case SPI_TYPE: display_spi_device(entry); break; default: printf("unknown device type!\n"); break; } display_device(entry); } printf("-------end----------\n");}

由以上代碼可知，利用內(nèi)核鏈表的統(tǒng)一接口，找個每一個節(jié)點的list成員，然后再利用container_of 得到我們定義的標(biāo)準(zhǔn)結(jié)構(gòu)體struct device，進而解析出節(jié)點的類型，調(diào)用對應(yīng)節(jié)點顯示函數(shù)，這個地方其實還可以優(yōu)化，就是我們可以在struct device中添加一個函數(shù)指針，在xxx_unregister_device()函數(shù)中可以將該函數(shù)指針直接注冊進來，那么此處代碼會更精簡高效一些。如果在做項目的過程中，寫出這種面向?qū)ο笏枷氲拇a，那么你的地址是肯定不一樣的。讀者有興趣可以自己嘗試一下。

void display_i2c_device(struct device *device){ struct i2c_node *i2c_device=container_of(device, struct i2c_node, dev); printf("\t i2c_device->data: %d\n",i2c_device->data); printf("\t i2c_device->reg: %#x\n",i2c_device->reg);}

void display_spi_device(struct device *device){ struct spi_node *spi_device=container_of(device, struct spi_node, dev); printf("\t spi_device->reg: %#x\n",spi_device->reg);}

上述代碼提取出來宿主節(jié)點的信息。

實例代碼

#include "list.h" #include <stdio.h> #include <string.h>
#define MAX_NAME_LEN 32#define MAX_ID_LEN 10
struct list_head device_list;
#define I2C_TYPE 1#define SPI_TYPE 2
char *dev_name[]={ "none", "I2C", "SPI"};
struct device{ int type; char name[MAX_NAME_LEN]; struct list_head list;};
struct i2c_node{ int data; unsigned int reg; struct device dev;};struct spi_node{  unsigned int reg; struct device dev;};void display_i2c_device(struct device *device){ struct i2c_node *i2c_device=container_of(device, struct i2c_node, dev);
 printf("\t i2c_device->data: %d\n",i2c_device->data); printf("\t i2c_device->reg: %#x\n",i2c_device->reg);}void display_spi_device(struct device *device){ struct spi_node *spi_device=container_of(device, struct spi_node, dev);
 printf("\t spi_device->reg: %#x\n",spi_device->reg);}void display_device(struct device *device){ printf("\t dev.type: %d\n",device->type); printf("\t dev.type: %s\n",dev_name[device->type]); printf("\t dev.name: %s\n",device->name);}void display_list(struct list_head *list_head){ int i=0; struct list_head *p; struct device *entry;
 printf("-------list---------\n"); list_for_each(p,list_head) { printf("node[%d]\n",i++); entry=list_entry(p,struct device,list);
 switch(entry->type) { case I2C_TYPE: display_i2c_device(entry); break; case SPI_TYPE: display_spi_device(entry); break; default: printf("unknown device type!\n"); break; } display_device(entry); } printf("-------end----------\n");}void i2c_register_device(struct device*dev){ struct i2c_node *i2c_device=container_of(dev, struct i2c_node, dev);
 i2c_device->dev.type = I2C_TYPE; strcpy(i2c_device->dev.name,"yikoulinux");
 list_add(&dev->list,&device_list); }void spi_register_device(struct device*dev){ struct spi_node *spi_device=container_of(dev, struct spi_node, dev);
 spi_device->dev.type = SPI_TYPE; strcpy(spi_device->dev.name,"yikoupeng");
 list_add(&dev->list,&device_list); }void i2c_unregister_device(struct device *device){ struct i2c_node *i2c_device=container_of(dev, struct i2c_node, dev);
 list_del(&device->list);}void spi_unregister_device(struct device *device){ struct spi_node *spi_device=container_of(dev, struct spi_node, dev);
 list_del(&device->list);}int main(void){
 struct i2c_node dev1; struct spi_node dev2;
 INIT_LIST_HEAD(&device_list); dev1.data = 1; dev1.reg = 0x40009000; i2c_register_device(&dev1.dev); dev2.reg = 0x40008000; spi_register_device(&dev2.dev);  display_list(&device_list); unregister_device(&dev1.dev); display_list(&device_list);  return 0;}

代碼主要功能：

117-118 ：定義兩個不同類型的節(jié)點dev1,dev2；
120 ：初始化設(shè)備鏈表；
121-122、124：初始化節(jié)點數(shù)據(jù)；
123/125 :向鏈表device_list注冊這兩個節(jié)點；
126 ：顯示該鏈表；
127 ：刪除節(jié)點dev1;
128 :顯示該鏈表。

程序運行截圖

讀者可以試試如何管理更多類型的節(jié)點。

實例3 實現(xiàn)節(jié)點在兩個鏈表上自由移動

功能描述：

初始化兩個鏈表，實現(xiàn)兩個鏈表上節(jié)點的插入和移動。每個節(jié)點維護大量的臨時內(nèi)存數(shù)據(jù)。

節(jié)點創(chuàng)建

節(jié)點結(jié)構(gòu)體創(chuàng)建如下：

struct mylist{ int number; char type; char *pmem; //內(nèi)存存放地址，需要malloc struct list_head list;};

需要注意成員pmem，因為要維護大量的內(nèi)存，我們最好不要直定義個很大的數(shù)組，因為定義的變量位于棧中，而一般的系統(tǒng)給棧的空間是有限的，如果定義的變量占用空間太大，會導(dǎo)致棧溢出，一口君曾經(jīng)就遇到過這個bug。

鏈表定義和初始化

鏈表定義如下：

structlist_head active_head; struct list_head free_head;

初始化

INIT_LIST_HEAD(&free_head);INIT_LIST_HEAD(&active_head);

這兩個鏈表如下：

關(guān)于節(jié)點，因為該實例是從實際項目中剝離出來，節(jié)點啟示是起到一個緩沖去的作用，數(shù)量不是無限的，所以在此我們默認(rèn)最多10個節(jié)點。

我們不再動態(tài)創(chuàng)建節(jié)點，而是先全局創(chuàng)建指針數(shù)組，存放這10個節(jié)點的地址，然后將這10個節(jié)點插入到對應(yīng)的隊列中。

數(shù)組定義：

structmylist*list_array[BUFFER_NUM];

這個數(shù)組只用于存放指針，所以定義之后實際情況如下：

初始化這個數(shù)組對應(yīng)的節(jié)點：

static ssize_t buffer_ring_init(){ int i=0; for(i=0;i<BUFFER_NUM;i++){ list_array[i]=malloc(sizeof(struct mylist)); INIT_LIST_HEAD(&list_array[i]->list); list_array[i]->pmem=kzalloc(DATA_BUFFER_SIZE,GFP_KERNEL); } return 0;}

5：為下標(biāo)為i的節(jié)點分配實際大小為sizeof(structmylist)的內(nèi)存

6：初始化該節(jié)點的鏈表

7：為pmem成員從堆中分配一塊內(nèi)存

初始化完畢，鏈表實際情況如下：

節(jié)點插入

static ssize_t insert_free_list_all(){ int i=0;
 for(i=0;i<BUFFER_NUM;i++){ list_add(&list_array[i]->list,&free_head); } return 0;}

8：用頭插法將所有節(jié)點插入到free_head鏈表中

所有節(jié)點全部插入free鏈表后，結(jié)構(gòu)圖如下：

遍歷鏈表

雖然可以通過數(shù)組遍歷鏈表，但是實際在操作過程中，在鏈表中各個節(jié)點的位置是錯亂的。所以最好從借助list節(jié)點來查找各個節(jié)點。

show_list(&free_head);show_list(&active_head);

代碼實現(xiàn)如下：

void show_list(struct list_head *list_head){ int i=0; struct mylist*entry,*tmp; //判斷節(jié)點是否為空 if(list_empty(list_head)==true) { return; } list_for_each_entry_safe(entry,tmp,list_head,list) { printf("[%d]=%d\t",i++,entry->number); if(i%4==0) { printf("\n"); } } }

節(jié)點移動

將節(jié)點從active_head鏈表移動到free_head鏈表，有點像生產(chǎn)者消費者模型中的消費者，吃掉資源后，就要把這個節(jié)點放置到空閑鏈表，讓生產(chǎn)者能夠繼續(xù)生產(chǎn)數(shù)據(jù)，所以這兩個函數(shù)我起名eat、spit，意為吃掉和吐，希望你們不要覺得很怪異。

int eat_node(){ struct mylist*entry=NULL;
 if(list_empty(&active_head)==true) { printf("list active_head is empty!-----------\n"); } entry=list_first_entry(&active_head,struct mylist,list); printf("\t eat node=%d\n",entry->number); list_move_tail(&entry->list,&free_head);}

節(jié)點移動的思路是：

1. 利用list_empty判斷該鏈表是否為空

2. 利用list_first_entry從active_head鏈表中查找到一個節(jié)點，并用指針entry指向該節(jié)點

3. 利用list_move_tail將該節(jié)點移入到free_head鏈表，注意此處不能用list_add，因為這個節(jié)點我要從原鏈表把他刪除掉，然后插入到新鏈表。

將節(jié)點從free_head鏈表移動到active_head鏈表。

spit_node(){ struct mylist*entry=NULL;
 if(list_empty(&free_head)==true) { printf("list free_head is empty!-----------\n"); } entry=list_first_entry(&free_head,struct mylist,list); printf("\t spit node=%d\n",entry->number); list_move_tail(&entry->list,&active_head);}

大部分功能講解完了，下面我們貼下完整代碼。

代碼實例

#include <stdint.h>#include <stdio.h>#include <stdlib.h>#include <unistd.h>#include <byteswap.h>#include <string.h>#include <errno.h>#include <signal.h>#include <fcntl.h>#include <ctype.h>#include <termios.h>#include <sys/types.h>#include <sys/mman.h>#include <sys/ioctl.h>#include "list.h" // linux-3.14/scripts/kconfig/list.h
#undef NULL#define NULL ((void *)0)
enum { false = 0, true = 1};
#define DATA_TYPE 0x14#define SIG_TYPE 0x15
struct mylist{ int number; char type; char *pmem; struct list_head list;};#define FATAL do { fprintf(stderr, "Error at line %d, file %s (%d) [%s]\n",__LINE_,__FILE__,errno,strerror(errno));exit(1);}while(0)struct list_head active_head;struct list_head free_head;#define BUFFER_NUM 10#define DATA_BUFFER_SIZE 512struct mylist*list_array[BUFFER_NUM];

int born_number(int number){ struct mylist *entry=NULL;
 if(list_empty(&free_head)==true) { printf("list free_head is empty!----------------\n"); } entry = list_first_entry(&free_head,struct mylist,list); entry->type = DATA_TYPE; entry->number=number; list_move_tail(&entry->list,&active_head); }
int eat_node(){ struct mylist*entry=NULL;
 if(list_empty(&active_head)==true) { printf("list active_head is empty!-----------\n"); } entry=list_first_entry(&active_head,struct mylist,list); printf("\t eat node=%d\n",entry->number); list_move_tail(&entry->list,&free_head);}spit_node(){ struct mylist*entry=NULL;
 if(list_empty(&free_head)==true) { printf("list free_head is empty!-----------\n"); } entry=list_first_entry(&free_head,struct mylist,list); printf("\t spit node=%d\n",entry->number); list_move_tail(&entry->list,&active_head);}
void show_list(struct list_head *list_head){ int i=0; struct mylist*entry,*tmp;
 if(list_empty(list_head)==true) { return; } list_for_each_entry_safe(entry,tmp,list_head,list) { printf("[%d]=%d\t",i++,entry->number); if(i%4==0) { printf("\n"); } } }int list_num(struct list_head *list_head){ int i=0; struct mylist *entry,*tmp;// printf("----------show free list-------------\n"); list_for_each_entry_safe(entry,tmp,list_head,list) { i++; } return i;}static ssize_t buffer_ring_init(){ int i=0;
 for(i=0;i<BUFFER_NUM;i++){ list_array[i]=malloc(sizeof(struct mylist)); INIT_LIST_HEAD(&list_array[i]->list); list_array[i]->pmem=kzalloc(DATA_BUFFER_SIZE,GFP_KERNEL); list_add_tail(&list_array[i]->list,&free_head); } return 0;}static ssize_t insert_free_list_all(){ int i=0;
 for(i=0;i<BUFFER_NUM;i++){ list_add_tail(&list_array[i]->list,&free_head); } return 0;}static ssize_t buffer_ring_free(){ int buffer_count=0; struct mylist*entry=NULL; for(;buffer_count<BUFFER_NUM;buffer_count++) { free(list_array[buffer_count]->pmem); free(list_array[buffer_count]); } return 0;}
int main(int argc,char**argv){ INIT_LIST_HEAD(&free_head); INIT_LIST_HEAD(&active_head); buffer_ring_init(); insert_free_list_all(); born_number(1); born_number(2); born_number(3); born_number(4); born_number(5); born_number(6); born_number(7); born_number(8); born_number(9); born_number(10);
 printf("\n----------active list[%d]------------\n",list_num(&active_head)); show_list(&active_head); printf("\n--------------end-----------------\n");
 printf("\n----------free list[%d]------------\n",list_num(&free_head));  show_list(&free_head); printf("\n--------------end-----------------\n");
 printf("\n\n active list----------> free list \n");
 eat_node(); eat_node(); eat_node();
 printf("\n----------active list[%d]------------\n",list_num(&active_head)); show_list(&active_head); printf("\n--------------end-----------------\n");
 printf("\n----------free list[%d]------------\n",list_num(&free_head));  show_list(&free_head); printf("\n--------------end-----------------\n");

 printf("\n\n free list----------> active list \n");
 spit_node(); spit_node();
 printf("\n----------active list[%d]------------\n",list_num(&active_head)); show_list(&active_head); printf("\n--------------end-----------------\n");
 printf("\n----------free list[%d]------------\n",list_num(&free_head));  show_list(&free_head); printf("\n--------------end-----------------\n");
}

運行結(jié)果如下：

list_head短小精悍，讀者可以借鑒此文實現(xiàn)其他功能。

參考文檔：https://kernelnewbies.org/FAQ/LinkedLists

《Understanding linux kernel》

《Linux device drivers》

list.h比較長，就不在此貼出源碼，如果讀者想獲取這個文件，可以識別下面的二維碼填加一口君好友，索取該文件，一口君這還有大量的Linux學(xué)習(xí)資料。

一口君個人微信

添加一口君個人微信即送Linux、嵌入式等獨家入門視頻

→ 精選技術(shù)資料共享

→ 高手如云交流社群

本公眾號全部原創(chuàng)干貨已整理成一個目錄，請在公眾號里回復(fù)「 m 」獲?。』蛘哧P(guān)注點擊左下角「干貨」！

推薦閱讀

【1】手把手教Linux驅(qū)動1-模塊化編程
【2】手把手教Linux驅(qū)動2-模塊參數(shù)param和符號導(dǎo)出export用法
【3】手把手教Linux驅(qū)動3-之字符設(shè)備架構(gòu)詳解，有這篇就夠了
【4】手把手教Linux驅(qū)動4-進程、文件描述符、file、inode關(guān)系詳解
【5】如何在Linux上恢復(fù)誤刪除的文件或目錄

【6】三劍客grep、sed和awk用法
【7】一文講懂什么是vlan、三層交換機、網(wǎng)關(guān)、DNS、子網(wǎng)掩碼、MAC地址
【8】詳解實時查看網(wǎng)卡流量的幾款工具
【9】如何高效閱讀代碼？Linux大神拍了拍你并教給你這三個步驟
【10】500億美元！英偉達收購Arm倒計時！月底Arm或?qū)儆诿绹?span style="font-size: 14px;">

5T技術(shù)資源大放送！包括但不限于：C/C++，Linux，Python，Java，PHP，人工智能，單片機，樹莓派，等等。在公眾號內(nèi)回復(fù)「1024」，即可免費獲取??！

免責(zé)聲明：本文內(nèi)容由21ic獲得授權(quán)后發(fā)布，版權(quán)歸原作者所有，本平臺僅提供信息存儲服務(wù)。文章僅代表作者個人觀點，不代表本平臺立場，如有問題，請聯(lián)系我們，謝謝！