/******************** * 內核中鏈表的應用 ********************/
(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);
如：
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);
總結
以上就是這篇文章的全部內容了，希望本文的內容對大家的學習或者工作具有一定的參考學習價值，謝謝大家對VEVB武林網的支持。
新聞熱點
疑難解答
