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

在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 =  %dn" , 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: %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;}

 

運行結(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: %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);}

上述代碼提取出來宿主節(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: %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 ???????? ：定義兩個不同類型的節(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]=%dt",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=%dn",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=%dn",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=%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");
}

運行結(jié)果如下：

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

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

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

《Understanding linux kernel》

《Linux device drivers》