Linux內核設備驅動之內核中鏈表有什么用

小編給大家分享一下Linux內核設備驅動之內核中鏈表有什么用，相信大部分人都還不怎么了解，因此分享這篇文章給大家參考一下，希望大家閱讀完這篇文章后大有收獲，下面讓我們一起去了解一下吧！

/********************
 * 內核中鏈表的應用
 ********************/

(1)介紹

在Linux內核中使用了大量的鏈表結構來組織數據，包括設備列表以及各種功能模塊中的數據組織。這些鏈表大多采用在include/linux/list.h實現的一個相當精彩的鏈表數據結構。

鏈表數據結構的定義很簡單:

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

list_head結構包含兩個指向list_head結構的指針prev和next，內核的數據結構通常組織成雙循環鏈表。

和以前介紹的雙鏈表結構模型不同，這里的list_head沒有數據域。在Linux內核鏈表中，不是在鏈表結構中包含數據，而是在數據結構中包含鏈表節點。如：

struct my_struct{
 struct list_head list;
 unsigned long dog;
 void *cat;
};

linux中的鏈表沒有固定的表頭，從任何元素開始訪問都可以。遍歷鏈表僅僅需要從某個節點開始，沿指針訪問下一個節點，直到又重新回到最初這個節點就可以了。每個獨立的節點都可以被稱作是鏈表頭。

(2)鏈表的初始化

a.靜態

如果在編譯時靜態創建鏈表，并且直接引用它，如下：

struct my_struct mine={
 .lost = LIST_HEAD_INIT(mine.list);
 .dog = 0,
 .cat = NULL
};
//或
static LIST_HEAD(fox);
/*等于struct list_head fox = LIST_HEAD_INIT(fox); */

b.動態

struct my_struct *p;
p = kmalloc(GFP_KERNEL, sizeof(my_struct));
p->dog = 0;
p->cat = NULL;
INIT_LIST_HEAD(&p->list);

(3)操作鏈表

內核提供了一組函數來操作鏈表。

注意！這些函數都使用一個或多個list_head結構體指針作參數。定義在<linux/list.h>

a.增加節點

list_add(struct list_head *new, 
     struct list_head *head);
//向指定鏈表的head節點后面插入new節點

b.把節點增加到鏈表尾

list_add_tail(struct list_head *new, 
     struct list_head *head);
//向指定鏈表的head節點前面插入new節點

c.從鏈表刪除一個節點

list_del(struct list_head *entry);
//將entry從鏈表中移走

d.把節點從一個鏈表移到另一個鏈表

list_move(struct list_head *list, 
     struct list_head *head);

從一個鏈表中摘除list項，然后將其插入head的后面

e.list_empty(struct list_head *head);

鏈表為空返回非0值，否則返回0

f.合并鏈表

list_splice(struct list_head *list, 
      struct list_head *head);
//注意！新的鏈表不包括list節點

(4)遍歷鏈表

鏈表本身不重要，訪問到那個包含鏈表的結構體才重要

a.從鏈表指針獲得包含該鏈表的結構體的指針

list_entry(struct list_head *ptr,
      type_of_struct, 
      field_name);

• ptr: list_head指針

• type_of_struct: 包含ptr的結構體類型

• field_name: 結構體中鏈表字段的名字

如：

my_struct *p = (list_head *ptr, my_struct, list);

b.遍歷鏈表

list_for_each(struct list_head *cursor,
       struct list_head *list);
//常常和list_entry配套使用
//注意！用list_for_each遍歷時，不包括頭節點

c.遍歷的同時獲得大結構體指針

list_for_each_entry(type *cursor, 
      struct list_head *list,
      member);

d.遍歷鏈表的同時釋放每個被遍歷到的節點

list_for_each_entry_safe(type *cursor, 
     type *tmp;
     struct list_head *list,
     member);

以上是“Linux內核設備驅動之內核中鏈表有什么用”這篇文章的所有內容，感謝各位的閱讀！相信大家都有了一定的了解，希望分享的內容對大家有所幫助，如果還想學習更多知識，歡迎關注億速云行業資訊頻道！