玩轉核心連結串列Llist_Head,教你管理不同型別節點的實現

語言: CN / TW / HK

在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,呼叫。

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

程式碼主要功能:

  1. 117-118          :定義兩個不同型別的節點dev1,dev2。
  2. 120                 :初始化裝置連結串列。
  3. 121-122、124:初始化節點資料。
  4. 123/125          :向連結串列device_list註冊這兩個節點。
  5. 126                :顯示該連結串列。
  6. 127                :刪除節點dev1。
  7. 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 512
struct 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短小精悍,讀者可以借鑑此文實現其他功能。