/********************
 * 內(nèi)核中鏈表的應(yīng)用
 ********************/

(1)介紹

在Linux內(nèi)核中使用了大量的鏈表結(jié)構(gòu)來(lái)組織數(shù)據(jù)，包括設(shè)備列表以及各種功能模塊中的數(shù)據(jù)組織。這些鏈表大多采用在include/linux/list.h實(shí)現(xiàn)的一個(gè)相當(dāng)精彩的鏈表數(shù)據(jù)結(jié)構(gòu)。

鏈表數(shù)據(jù)結(jié)構(gòu)的定義很簡(jiǎn)單:

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

list_head結(jié)構(gòu)包含兩個(gè)指向list_head結(jié)構(gòu)的指針prev和next，內(nèi)核的數(shù)據(jù)結(jié)構(gòu)通常組織成雙循環(huán)鏈表。

和以前介紹的雙鏈表結(jié)構(gòu)模型不同，這里的list_head沒(méi)有數(shù)據(jù)域。在Linux內(nèi)核鏈表中，不是在鏈表結(jié)構(gòu)中包含數(shù)據(jù)，而是在數(shù)據(jù)結(jié)構(gòu)中包含鏈表節(jié)點(diǎn)。如：

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

linux中的鏈表沒(méi)有固定的表頭，從任何元素開(kāi)始訪問(wèn)都可以。遍歷鏈表僅僅需要從某個(gè)節(jié)點(diǎn)開(kāi)始，沿指針訪問(wèn)下一個(gè)節(jié)點(diǎn)，直到又重新回到最初這個(gè)節(jié)點(diǎn)就可以了。每個(gè)獨(dú)立的節(jié)點(diǎn)都可以被稱作是鏈表頭。

(2)鏈表的初始化

a.靜態(tài)

如果在編譯時(shí)靜態(tài)創(chuàng)建鏈表，并且直接引用它，如下：

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.動(dòng)態(tài)

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

(3)操作鏈表

內(nèi)核提供了一組函數(shù)來(lái)操作鏈表。

注意！這些函數(shù)都使用一個(gè)或多個(gè)list_head結(jié)構(gòu)體指針作參數(shù)。定義在<linux/list.h>

a.增加節(jié)點(diǎn)

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

b.把節(jié)點(diǎn)增加到鏈表尾

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

c.從鏈表刪除一個(gè)節(jié)點(diǎn)

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

d.把節(jié)點(diǎn)從一個(gè)鏈表移到另一個(gè)鏈表

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

從一個(gè)鏈表中摘除list項(xiàng)，然后將其插入head的后面

e.list_empty(struct list_head *head);

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

f.合并鏈表

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

(4)遍歷鏈表

鏈表本身不重要，訪問(wèn)到那個(gè)包含鏈表的結(jié)構(gòu)體才重要

a.從鏈表指針獲得包含該鏈表的結(jié)構(gòu)體的指針

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

• ptr: list_head指針
• type_of_struct: 包含ptr的結(jié)構(gòu)體類(lèi)型
• field_name: 結(jié)構(gòu)體中鏈表字段的名字

如：

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遍歷時(shí)，不包括頭節(jié)點(diǎn)

c.遍歷的同時(shí)獲得大結(jié)構(gòu)體指針

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

d.遍歷鏈表的同時(shí)釋放每個(gè)被遍歷到的節(jié)點(diǎn)

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

總結(jié)

以上就是這篇文章的全部?jī)?nèi)容了，希望本文的內(nèi)容對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，謝謝大家對(duì)腳本之家的支持。如果你想了解更多相關(guān)內(nèi)容請(qǐng)查看下面相關(guān)鏈接

最新評(píng)論