? 在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 的通用接口很容易實(shí)現(xiàn)代碼的重用，有點(diǎn)類似于C++的繼承機(jī)制（希望有機(jī)會寫篇文章研究一下C語言的面向?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)如下圖所示：

?? ? ?然后就開始圍繞這個結(jié)構(gòu)開始構(gòu)建鏈表，然后插入、刪除節(jié)點(diǎn) ，遍歷整個鏈表等等，其實(shí)內(nèi)核已經(jīng)提供好了現(xiàn)成的接口，接下來就讓我們進(jì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) 進(jìn)行初始化一個鏈表，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ù)，所以毫無意義。

?? ? 綜上，我們可以創(chuàng)建一個宿主結(jié)構(gòu)，然后在此結(jié)構(gòu)中再嵌套mylist字段，宿主結(jié)構(gòu)又有其它的字段（進(jìn)程描述符 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é)點(diǎn)

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

1.? list_add?

????如下所示。根據(jù)注釋可知，是在鏈表頭head后方插入一個新節(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鏈表頭后和鏈表頭后第一個節(jié)點(diǎn)之間插入一個新節(jié)點(diǎn)。然后這個新的節(jié)點(diǎn)就變成了鏈表頭后的第一個節(jié)點(diǎn)了。

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

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

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

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

list_add?

以此類推，每次插入一個新節(jié)點(diǎn)，都是緊靠著header節(jié)點(diǎn)，而之前插入的節(jié)點(diǎn)依次排序靠后，那最后一個節(jié)點(diǎn)則是第一次插入header后的那個節(jié)點(diǎn)。最終可得出：先來的節(jié)點(diǎn)靠后，而后來的節(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.讓我們來看一下它的具體實(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）在一個特定的鏈表頭前面插入一個節(jié)點(diǎn)

（2）這個方法很適用于隊(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)，此時，header節(jié)點(diǎn)既是為節(jié)點(diǎn)，保持不變）

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

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

（2）插入第一個節(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) 插入第二個節(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表尾，而插入的第一個節(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)了，但需注意，前提條件是這個節(jié)點(diǎn)是已知的，既在鏈表中真實(shí)存在，切prev，next指針都不為NULL。

???

四. 鏈表遍歷

?? ?內(nèi)核是同過下面這個宏定義來完成對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這個鏈表進(jìn)行的，涉及的結(jié)構(gòu)體也都是:

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

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

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宏來實(shí)現(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之后此宏定義改變，但實(shí)現(xiàn)思想保持一致）

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

舉個例子，來簡單分析一下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宏，探究內(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ò)展語法。

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

(3) 這里的offsetof(struct test,b)是用來計(jì)算成員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)的地址，并且我們可以對成員變量所建立的鏈表進(jìn)行遍歷，那我們是不是也可以通過某種方法對宿主結(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中，分別代表：獲取第一個真正的宿主結(jié)構(gòu)的地址；獲取下一個宿主結(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定位到第一個宿主結(jié)構(gòu)地址，然后循環(huán)獲取下一個宿主結(jié)構(gòu)地址，如果查到宿主結(jié)構(gòu)中的member成員變量（宿主結(jié)構(gòu)中struct list_head定義的字段）地址為head，則退出，從而實(shí)現(xiàn)了宿主結(jié)構(gòu)的遍歷。如果要循環(huán)對宿主結(jié)構(gòu)中的其它成員變量進(jìn)行操作，這個遍歷操作就顯得特別有意義了。

?????? 我們用上面的 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);?}

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

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

功能描述：

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

#include "list.h" #include  #include 
#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;}

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

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

功能描述：

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

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

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

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

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

#define I2C_TYPE 1 #define SPI_TYPE 2

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

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

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

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

structlist_head device_list;

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

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

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

實(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（）注冊到鏈表中。這個思想很重要，因?yàn)長inux內(nèi)核中許許多多的設(shè)備節(jié)點(diǎn)也是這樣添加到其他的鏈表中的。要想讓自己的C語言編程能力得到質(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)的遍歷，在這里我們通過設(shè)備鏈表device_list開始遍歷，假設(shè)該節(jié)點(diǎn)名是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é)點(diǎn)的list成員，然后再利用container_of 得到我們定義的標(biāo)準(zhǔn)結(jié)構(gòu)體struct device，進(jìn)而解析出節(jié)點(diǎn)的類型，調(diào)用對應(yīng)節(jié)點(diǎn)顯示函數(shù)，這個地方其實(shí)還可以優(yōu)化，就是我們可以在struct device中添加一個函數(shù)指針，在xxx_unregister_device()函數(shù)中可以將該函數(shù)指針直接注冊進(jìn)來，那么此處代碼會更精簡高效一些。如果在做項(xiàng)目的過程中，寫出這種面向?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é)點(diǎn)的信息。

實(shí)例代碼

#include "list.h" #include  #include 
#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é)點(diǎn)dev1,dev2；
120???????????????? ：初始化設(shè)備鏈表；
121-122、124：初始化節(jié)點(diǎn)數(shù)據(jù)；
123/125 ???????? :向鏈表device_list注冊這兩個節(jié)點(diǎn)；
126 ?????????????? ：顯示該鏈表；
127 ?????????????? ：刪除節(jié)點(diǎn)dev1;
128 ? ? ? ? ? ? ? ? :顯示該鏈表。

程序運(yùn)行截圖

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

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

功能描述：

初始化兩個鏈表，實(shí)現(xiàn)兩個鏈表上節(jié)點(diǎn)的插入和移動。每個節(jié)點(diǎn)維護(hù)大量的臨時內(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)存，我們最好不要直定義個很大的數(shù)組，因?yàn)槎x的變量位于棧中，而一般的系統(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é)點(diǎn)，因?yàn)樵搶?shí)例是從實(shí)際項(xiàng)目中剝離出來，節(jié)點(diǎn)啟示是起到一個緩沖去的作用，數(shù)量不是無限的，所以在此我們默認(rèn)最多10個節(jié)點(diǎn)。

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

數(shù)組定義：

structmylist*list_array[BUFFER_NUM];

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

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

static ssize_t buffer_ring_init(){  int i=0;  for(i=0;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    list_add(&list_array[i]->list,&free_head);  }  return 0;}

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

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

遍歷鏈表

雖然可以通過數(shù)組遍歷鏈表，但是實(shí)際在操作過程中，在鏈表中各個節(jié)點(diǎn)的位置是錯亂的。所以最好從借助list節(jié)點(diǎn)來查找各個節(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]=%d\t",i++,entry->number);    if(i%4==0)    {      printf("\n");    }  }  }

節(jié)點(diǎn)移動

將節(jié)點(diǎn)從active_head鏈表移動到free_head鏈表，有點(diǎn)像生產(chǎn)者消費(fèi)者模型中的消費(fèi)者，吃掉資源后，就要把這個節(jié)點(diǎn)放置到空閑鏈表，讓生產(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é)點(diǎn)移動的思路是：

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

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

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

將節(jié)點(diǎn)從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);}

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

代碼實(shí)例

#include #include #include #include #include #include #include #include #include #include #include #include #include #include #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    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    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  {    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");
}

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

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

參考文檔：

? ? https://kernelnewbies.org/FAQ/LinkedLists

???《Understanding linux kernel》

???《Linux device drivers》

圖文講解｜玩轉(zhuǎn)內(nèi)核鏈表 list

1.? list_add?

2. list_add_tail 接口?

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

四. 鏈表遍歷

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

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

2 container_of

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

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

功能描述：

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

功能描述：

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

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

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

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

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

實(shí)例代碼

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

功能描述：

?

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

?

鏈表定義和初始化

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

遍歷鏈表

節(jié)點(diǎn)移動

代碼實(shí)例