在Linux內核中，提供了一個用來創建雙向循環鏈表的結構 list_head。雖然linux內核是用C語言寫的，但是list_head的引入，使得內核數據結構也可以擁有面向對象的特性，通過使用操作list_head 的通用接口很容易實現代碼的重用，有點類似于C++的繼承機制（希望有機會寫篇文章研究一下C語言的面向對象機制）。

首先找到list_head結構體定義，kernel/inclue/linux/types.h 如下：

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

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

使用list_head組織的鏈表的結構如下圖所示：

然后就開始圍繞這個結構開始構建鏈表，然后插入、刪除節點，遍歷整個鏈表等等，其實內核已經提供好了現成的接口，接下來就讓我們進入 kernel/include/linux/list.h中：

一. 創建鏈表

內核提供了下面的這些接口來初始化鏈表：

#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這樣的結構體實現鏈表就沒有什么實際意義了，因為正常的鏈表都是為了遍歷結構體中的其它有意義的字段而創建的，而我們mylist中只有 prev和next指針，卻沒有實際有意義的字段數據，所以毫無意義。

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

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

創建鏈表，并初始化

structlist_head myhead; INIT_LIST_HEAD(&myhead);

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

二. 添加節點

內核已經提供了添加節點的接口了

1. list_add

如下所示。根據注釋可知，是在鏈表頭head后方插入一個新節點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再調用__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鏈表頭后和鏈表頭后第一個節點之間插入一個新節點。然后這個新的節點就變成了鏈表頭后的第一個節點了。

接著上面步驟創建1個節點然后插入到myhead之后

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

然后在創建第二個節點，同樣把它插入到header_task之后

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

list_add

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

2. list_add_tail 接口

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

/** * 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）在一個特定的鏈表頭前面插入一個節點

（2）這個方法很適用于隊列的實現（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就相當于在鏈表頭前方依次插入新的節點（也可理解為在鏈表尾部開始插入節點，此時，header節點既是為節點，保持不變）

利用上面分析list_add接口的方法可畫出數據結構圖形如下。

（1）創建一個鏈表頭（實際上應該是表尾）代碼參考第一節;

（2）插入第一個節點 node1.list , 調用

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

(3) 插入第二個節點node2.list，調用

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

list_add_tail

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

三. 刪除節點

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

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) 接口就可以刪除鏈表中的任意節點了，但需注意，前提條件是這個節點是已知的，既在鏈表中真實存在，切prev，next指針都不為NULL。

四. 鏈表遍歷

內核是同過下面這個宏定義來完成對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(節點替換) list_move(節點移位) ，翻轉，查找等接口，這里就不在一一分析了。

五. 宿主結構

1.找出宿主結構 list_entry(ptr, type, member)

上面的所有操作都是基于list_head這個鏈表進行的，涉及的結構體也都是:

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

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

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

那我們如何根據list這個字段的地址而找到宿主結構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宏來實現對應地址的轉換，但最終還是調用了container_of宏，所以container_of宏的偉大之處不言而喻。

2 container_of

做linux驅動開發的同學是不是想到了LDD3這本書中經常使用的一個非常經典的宏定義！

container_of(ptr, type, member)

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

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

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

舉個例子，來簡單分析一下container_of內部實現機制。

例如:

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結構體空間的首地址     struct  test *addr;     addr =   container_of(addr_b,struct test,b);}

展開container_of宏，探究內部的實現:

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 結構體的偏移。__mptr

是成員b的首地址, 現在減去成員b在結構體里面的偏移值，算出來的是不是這個結構體的

首地址呀。

3. 宿主結構的遍歷

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

答案肯定是可以的，內核在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中，分別代表：獲取第一個真正的宿主結構的地址；獲取下一個宿主結構的地址。它們的實現都是利用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)

最終實現了宿主結構的遍歷

#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定位到第一個宿主結構地址，然后循環獲取下一個宿主結構地址，如果查到宿主結構中的member成員變量（宿主結構中struct list_head定義的字段）地址為head，則退出，從而實現了宿主結構的遍歷。如果要循環對宿主結構中的其它成員變量進行操作，這個遍歷操作就顯得特別有意義了。

我們用上面的 nod結構舉個例子：

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

實例1 一個簡單的鏈表的實現

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

功能描述：

本例比較簡單，僅僅實現了單鏈表節點的創建、刪除、遍歷。

#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;}

運行結果

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

功能描述：

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

結構體定義

一個鏈表要想區分節點的不同類型，那么節點中必須要有信息能夠區分該節點類型，為了方便節點擴展，我們參考Linux內核，定義一個統一類型的結構體：

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

其中成員type表示該節點的類型：

#defineI2C_TYPE 1 #define SPI_TYPE 2

有了該結構體，我們要定義其他類型的結構體只需要包含該結構體即可，這個思想有點像面向對象語言的基類，后續派生出新的屬性叫子類，說到這，一口君又忍不住想挖個坑，寫一篇如何用C語言實現面向對象思想的繼承、多態、interface。

下面我們定義2種類型的結構體：

i2c這種類型設備的專用結構體：

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

spi這種類型設備的專用結構體：

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

我特意讓兩個結構體大小類型不一致。

結構類型

鏈表頭結點定義

structlist_head device_list;

根據之前我們講解的思想，這個鏈表鏈接起來后，應該是以下這種結構：

節點的插入

我們定義的節點要插入鏈表仍然是要依賴list_add（），既然我們定義了struct device這個結構體，那么我們完全可以參考linux內核，針對不同的節點封裝函數，要注冊到這個鏈表只需要調用該函數即可。

實現如下：

設備i2c的注冊函數如下：

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

設備spi的注冊函數如下：

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

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

節點的刪除

同理，節點的刪除，我們也統一封裝成函數，同樣只傳遞參數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);}

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

宿主結構的遍歷

節點的遍歷，在這里我們通過設備鏈表device_list開始遍歷，假設該節點名是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");}

由以上代碼可知，利用內核鏈表的統一接口，找個每一個節點的list成員，然后再利用container_of 得到我們定義的標準結構體struct device，進而解析出節點的類型，調用對應節點顯示函數，這個地方其實還可以優化，就是我們可以在struct device中添加一個函數指針，在xxx_unregister_device()函數中可以將該函數指針直接注冊進來，那么此處代碼會更精簡高效一些。如果在做項目的過程中，寫出這種面向對象思想的代碼，那么你的地址是肯定不一樣的。讀者有興趣可以自己嘗試一下。

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

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

實例代碼

#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 ：定義兩個不同類型的節點dev1,dev2；
120 ：初始化設備鏈表；
121-122、124：初始化節點數據；
123/125 :向鏈表device_list注冊這兩個節點；
126 ：顯示該鏈表；
127 ：刪除節點dev1;
128 :顯示該鏈表。

程序運行截圖

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

實例3 實現節點在兩個鏈表上自由移動

功能描述：

初始化兩個鏈表，實現兩個鏈表上節點的插入和移動。每個節點維護大量的臨時內存數據。

節點創建

節點結構體創建如下：

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

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

鏈表定義和初始化

鏈表定義如下：

structlist_head active_head; struct list_head free_head;

初始化

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

這兩個鏈表如下：

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

我們不再動態創建節點，而是先全局創建指針數組，存放這10個節點的地址，然后將這10個節點插入到對應的隊列中。

數組定義：

structmylist*list_array[BUFFER_NUM];

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

初始化這個數組對應的節點：

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：為下標為i的節點分配實際大小為sizeof(structmylist)的內存

6：初始化該節點的鏈表

7：為pmem成員從堆中分配一塊內存

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

節點插入

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：用頭插法將所有節點插入到free_head鏈表中

所有節點全部插入free鏈表后，結構圖如下：

遍歷鏈表

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

show_list(&free_head);show_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");    }  }  }

節點移動

將節點從active_head鏈表移動到free_head鏈表，有點像生產者消費者模型中的消費者，吃掉資源后，就要把這個節點放置到空閑鏈表，讓生產者能夠繼續生產數據，所以這兩個函數我起名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);}

節點移動的思路是：

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

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

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

將節點從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");
}

運行結果如下：

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

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

《Understanding linux kernel》

《Linux device drivers》

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

一口君個人微信

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

→ 精選技術資料共享

→ 高手如云交流社群

本公眾號全部原創干貨已整理成一個目錄，請在公眾號里回復「m」獲取！或者關注點擊左下角「干貨」！

【6】三劍客grep、sed和awk用法
【7】一文講懂什么是vlan、三層交換機、網關、DNS、子網掩碼、MAC地址
【8】詳解實時查看網卡流量的幾款工具
【9】如何高效閱讀代碼？Linux大神拍了拍你并教給你這三個步驟
【10】500億美元！英偉達收購Arm倒計時！月底Arm或將屬于美國！

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

查看全文

亚洲欧美第一页_禁久久精品乱码_粉嫩av一区二区三区免费野_久草精品视频

您現在的位置是：首頁 > 技術閱讀 > 玩轉內核鏈表list_head，如何管理不同類型節點的實現（萬字文）可以收藏

玩轉內核鏈表list_head，如何管理不同類型節點的實現（萬字文）可以收藏

1. list_add

2. list_add_tail 接口

三. 刪除節點

四. 鏈表遍歷

五. 宿主結構

1.找出宿主結構 list_entry(ptr, type, member)

2 container_of

3. 宿主結構的遍歷

實例1 一個簡單的鏈表的實現

功能描述：

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

功能描述：

結構體定義

結構類型

節點的插入

節點的刪除

宿主結構的遍歷

實例代碼

實例3 實現節點在兩個鏈表上自由移動

功能描述：

節點創建

鏈表定義和初始化

節點插入

遍歷鏈表

節點移動

代碼實例