玩轉(zhuǎn)內(nèi)核鏈表list_head，教你管理不同類型節(jié)點(diǎn)的實(shí)現(xiàn)，建議收藏

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

首先找到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) }

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

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

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

一. 創(chuàng)建鏈表

內(nèi)核提供了下面的這些接口來(lá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;}

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

structlist_head mylist = {&mylist, &mylist} ;

但是如果只是利用mylist這樣的結(jié)構(gòu)體實(shí)現(xiàn)鏈表就沒有什么實(shí)際意義了，因?yàn)檎５逆湵矶际菫榱吮闅v結(jié)構(gòu)體中的其它有意義的字段而創(chuàng)建的，而我們mylist中只有 prev和next指針，卻沒有實(shí)際有意義的字段數(shù)據(jù)，所以毫無(wú)意義。

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

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指針?lè)謩e指向myhead自己了，如下圖：

二. 添加節(jié)點(diǎn)

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

1.? list_add

如下所示。根據(jù)注釋可知，是在鏈表頭head后方插入一個(gè)新節(jié)點(diǎn)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);}

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

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

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

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

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

list_add

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

2. list_add_tail 接口

上面所講的list_add接口是從鏈表頭header后添加的節(jié)點(diǎn)。同樣，內(nèi)核也提供了從鏈表尾處向前添加節(jié)點(diǎn)的接口list_add_tail.讓我們來(lái)看一下它的具體實(shí)現(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）在一個(gè)特定的鏈表頭前面插入一個(gè)節(jié)點(diǎn)

（2）這個(gè)方法很適用于隊(duì)列的實(shí)現(xiàn)（why？）

進(jìn)一步把__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é)點(diǎn)（也可理解為在鏈表尾部開始插入節(jié)點(diǎn)，此時(shí)，header節(jié)點(diǎn)既是為節(jié)點(diǎn)，保持不變）

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

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

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

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

? (3) 插入第二個(gè)節(jié)點(diǎn)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é)點(diǎn)都是緊挨著 header_task表尾，而插入的第一個(gè)節(jié)點(diǎn)my_first_task排在了第一位，my_second_task排在了第二位，可得出：先插入的節(jié)點(diǎn)排在前面，后插入的節(jié)點(diǎn)排在后面，“先進(jìn)先出，后進(jìn)后出”，這不正是隊(duì)列的特點(diǎn)嗎（First in First out）！

三. 刪除節(jié)點(diǎn)

內(nèi)核同樣在list.h文件中提供了刪除節(jié)點(diǎn)的接口 list_del()， 讓我們看一下它的實(shí)現(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é)點(diǎn)了，但需注意，前提條件是這個(gè)節(jié)點(diǎn)是已知的，既在鏈表中真實(shí)存在，切prev，next指針都不為NULL。

四. 鏈表遍歷

內(nèi)核是同過(guò)下面這個(gè)宏定義來(lái)完成對(duì)list_head鏈表進(jìn)行遍歷的，如下 :

/** * 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é)點(diǎn)替換)? list_move(節(jié)點(diǎn)移位)?，翻轉(zhuǎn)，查找等接口，這里就不在一一分析了。

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

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

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

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

其實(shí)，正如文章一開始所說(shuō)，我們真正更關(guān)心的是包含list_head這個(gè)結(jié)構(gòu)體字段的宿主結(jié)構(gòu)體，因?yàn)橹挥卸ㄎ坏搅怂拗鹘Y(jié)構(gòu)體的起始地址，我們才能對(duì)對(duì)宿主結(jié)構(gòu)體中的其它有意義的字段進(jìn)行操作。

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

那我們?nèi)绾胃鶕?jù)list這個(gè)字段的地址而找到宿主結(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宏來(lái)實(shí)現(xiàn)對(duì)應(yīng)地址的轉(zhuǎn)換，但最終還是調(diào)用了container_of宏，所以container_of宏的偉大之處不言而喻。

2 container_of

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

container_of(ptr, type, member)

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

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

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

舉個(gè)例子，來(lái)簡(jiǎn)單分析一下container_of內(nèi)部實(shí)現(xiàn)機(jī)制。

例如:

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宏，探究?jī)?nèi)部的實(shí)現(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的擴(kuò)展語(yǔ)法。

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

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

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

首地址呀 。

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

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

答案肯定是可以的，內(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中，分別代表：獲取第一個(gè)真正的宿主結(jié)構(gòu)的地址；獲取下一個(gè)宿主結(jié)構(gòu)的地址。它們的實(shí)現(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)

 

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

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

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

實(shí)例1 一個(gè)簡(jiǎn)單的鏈表的實(shí)現(xiàn)

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

功能描述：

本例比較簡(jiǎn)單，僅僅實(shí)現(xiàn)了單鏈表節(jié)點(diǎn)的創(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: %sn",dev_name[entry->type]);    printf("tname: %sn",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;}

 

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

實(shí)例2? 如何在一個(gè)鏈表上管理不同類型的節(jié)點(diǎn)

功能描述：

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

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

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

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

 

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

#defineI2C_TYPE 1 #define SPI_TYPE 2

有了該結(jié)構(gòu)體，我們要定義其他類型的結(jié)構(gòu)體只需要包含該結(jié)構(gòu)體即可，這個(gè)思想有點(diǎn)像面向?qū)ο笳Z(yǔ)言的基類，后續(xù)派生出新的屬性叫子類，說(shuō)到這，一口君又忍不住想挖個(gè)坑，寫一篇如何用C語(yǔ)言實(shí)現(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;};

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

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

鏈表頭結(jié)點(diǎn)定義

structlist_head device_list;

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

節(jié)點(diǎn)的插入

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

實(shí)現(xiàn)如下：

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

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

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

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

 

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

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

同理，節(jié)點(diǎn)的刪除，我們也統(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é)點(diǎn)的首地址，實(shí)際使用中可以根據(jù)設(shè)備的不同釋放不同的資源。

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

節(jié)點(diǎn)的遍歷，在這里我們通過(guò)設(shè)備鏈表device_list開始遍歷，假設(shè)該節(jié)點(diǎn)名是node，通過(guò)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)一接口，找個(gè)每一個(gè)節(jié)點(diǎn)的list成員，然后再利用container_of 得到我們定義的標(biāo)準(zhǔn)結(jié)構(gòu)體struct device，進(jìn)而解析出節(jié)點(diǎn)的類型，調(diào)用對(duì)應(yīng)節(jié)點(diǎn)顯示函數(shù)，這個(gè)地方其實(shí)還可以優(yōu)化，就是我們可以在struct device中添加一個(gè)函數(shù)指針，在xxx_unregister_device()函數(shù)中可以將該函數(shù)指針直接注冊(cè)進(jìn)來(lái)，那么此處代碼會(huì)更精簡(jiǎn)高效一些。如果在做項(xiàng)目的過(guò)程中，寫出這種面向?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: %dn",i2c_device->data);  printf("t  i2c_device->reg: %#xn",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: %#xn",spi_device->reg);}

上述代碼提取出來(lái)宿主節(jié)點(diǎn)的信息。

實(shí)例代碼

#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: %dn",i2c_device->data);  printf("t  i2c_device->reg: %#xn",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: %#xn",spi_device->reg);}void display_device(struct device *device){    printf("t  dev.type: %dn",device->type);    printf("t  dev.type: %sn",dev_name[device->type]);    printf("t  dev.name: %sn",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 ???????? ：定義兩個(gè)不同類型的節(jié)點(diǎn)dev1,dev2；

120???????????????? ：初始化設(shè)備鏈表；

121-122、124：初始化節(jié)點(diǎn)數(shù)據(jù)；

123/125 ???????? :向鏈表device_list注冊(cè)這兩個(gè)節(jié)點(diǎn)；

126 ?????????????? ：顯示該鏈表；

127 ?????????????? ：刪除節(jié)點(diǎn)dev1;

128 ? ? ? ? ? ? ? ? :顯示該鏈表。

程序運(yùn)行截圖

 

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

實(shí)例3? 實(shí)現(xiàn)節(jié)點(diǎn)在兩個(gè)鏈表上自由移動(dòng)

功能描述：

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

節(jié)點(diǎn)創(chuàng)建

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

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

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

鏈表定義和初始化

鏈表定義如下：

structlist_head active_head; struct list_head free_head;

初始化

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

這兩個(gè)鏈表如下：

關(guān)于節(jié)點(diǎn)，因?yàn)樵搶?shí)例是從實(shí)際項(xiàng)目中剝離出來(lái)，節(jié)點(diǎn)啟示是起到一個(gè)緩沖去的作用，數(shù)量不是無(wú)限的，所以在此我們默認(rèn)最多10個(gè)節(jié)點(diǎn)。

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

數(shù)組定義：

structmylist*list_array[BUFFER_NUM];

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

初始化這個(gè)數(shù)組對(duì)應(yīng)的節(jié)點(diǎn)：

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é)點(diǎn)分配實(shí)際大小為sizeof(structmylist)的內(nèi)存

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

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

初始化完畢，鏈表實(shí)際情況如下：

節(jié)點(diǎn)插入

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é)點(diǎn)插入到free_head鏈表中

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

 

 

遍歷鏈表

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

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

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

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

節(jié)點(diǎn)移動(dòng)

將節(jié)點(diǎn)從active_head鏈表移動(dòng)到free_head鏈表，有點(diǎn)像生產(chǎn)者消費(fèi)者模型中的消費(fèi)者，吃掉資源后，就要把這個(gè)節(jié)點(diǎn)放置到空閑鏈表，讓生產(chǎn)者能夠繼續(xù)生產(chǎn)數(shù)據(jù)，所以這兩個(gè)函數(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=%dn",entry->number);  list_move_tail(&entry->list,&free_head);}

節(jié)點(diǎn)移動(dòng)的思路是：

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

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

3. 利用list_move_tail將該節(jié)點(diǎn)移入到free_head鏈表，注意此處不能用list_add，因?yàn)檫@個(gè)節(jié)點(diǎn)我要從原鏈表把他刪除掉，然后插入到新鏈表。

將節(jié)點(diǎn)從free_head鏈表移動(dòng)到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=%dn",entry->number);  list_move_tail(&entry->list,&active_head);}

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

代碼實(shí)例

#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=%dn",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=%dn",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]=%dt",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("nn    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("nn    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");
}

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

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

list.h比較長(zhǎng)，需要回復(fù)：list。

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

《Understanding linux kernel》

《Linux device drivers》