現在的位置: 首頁 > 技術文章 > 基礎知識 > 正文

Linux中list_head結構體相關

2018年02月02日 基礎知識 ⁄ 共 3385字 ⁄ 字號 Linux中list_head結構體相關已關閉評論

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

下面就是kernel中的list_head結構定義:

struct list_head {

struct list_head *next, *prev;

};

list_head是linux?kernel中非常重要的一個結構體,是雙向鏈表的數據結構體,為了減少浪費,眾多鏈表都是用list_head以及其相關原語操作,list_head這個結構看起來怪怪的,它竟沒有數據域!所以看到這個結構的人第一反應就是我們怎么訪問數據?其實list_head不是拿來單獨用的,它一般被嵌到其它結構中:

比如所有的進程是靠它串聯在一起的,所有的inode也靠它串聯在一起等等。

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

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

list_head

list_head

特別注意的是,list_head中的指針存放的是另一個list_head的地址,而不是含有list_head結構的整個數據結構的地址;

舉例如下:

struct file_node{

char c;

struct list_head node;

};

此時list_head就作為它的父結構中的一個成員了,當我們知道list_head的地址(指針)時,我們可以通過list.c提供的宏 list_entry 來獲得它的父結構的地址。下面我們來看看list_entry的實現:(list_entry: 與container_of功能相同)

#define list_entry(ptr,type,member)\

container_of(ptr,type,member)

#define offsetof(TYPE,MEMBER) ((size_t)&((TYPE *)0)->MEMBER)

#define container_of(ptr,type,member) ( {\

const typeof( ((type*)0)->member ) *__mptr=(ptr);\

(type*)( (char*)__mptr - offsetof(type,member) );} )

這里涉及到三個宏,還是有點復雜的,我們一個一個來看:

#define offsetof(TYPE,MEMBER) ( (size_t)& ((TYPE *)0)-> MEMBER )

我們知道 0 地址內容是不能訪問的,但 0地址的地址我們還是可以訪問的, 這里用到一個取址運算符

(TYPE *)0 它表示將 0地址強制轉換為TYPE類型,((TYPE *)0)-> MEMBER 也就是從0址址找到TYPE 的成員MEMBER 。

我們結合上面的結構file_node來看

將實參代入 offset( struct file_node, node );最終將變成這樣:

( (size_t) & ((struct file_node*)0)-> node );這樣看的還是不很清楚,我們再變變:

struct file_node *p = NULL;

& p->node;

這樣應該比較清楚了,即求 p 的成員 node的地址,只不過p 為0地址,從0地址開始算成員node的地址,也就是 成員 node 在結構體 struct file_node中的偏移量。offset宏就是算MEMBER在TYPE中的偏移量的。

我們再看第二個宏

#define container_of(ptr,type,member) ( {\

const typeof( ((type*)0)->member ) *__mptr=(ptr);\

(type*)( (char*)__mptr - offsetof(type,member) );} )

這個宏是由兩個語句組成,最后container_of返回的結果就是第二個表達式的值。這里__mptr為中間變量,這就是list_head指針類型,它被初始化為ptr的值,而ptr就是當前所求的結構體中list_head節點的地址。為什么要用中間變量,這是考慮到安全性因素,如果傳進來一個ptr++,所有ptr++放在一個表達式中會有副作用,像 (p++)+(p++)之類。

(char*)__mptr 之所以要強制類型轉化為char是因為地址是以字節為單位的,而char的長度就是一個字節。

container_of的值是兩個地址相減,

剛說了__mptr是結構體中list_head節點的地址,offset宏求的是list_head節點MEMBER在結構體TYPE中的偏移量,那么__mptr減去它所在結構體中的偏移量,就是結構體的地址。

所以list_entry(ptr,type,member)宏的功能就是,由結構體成員地址求結構體地址。其中ptr 是所求結構體中list_head成員指針,type是所求結構體類型,member是結構體list_head成員名。通過下圖來總結一下:

list

list

 

列舉一些雙鏈表的常用操作:

雙向鏈表的遍歷——list_for_each

//注:這里prefetch 是gcc的一個優化選項,也可以不要

#define list_for_each(pos, head) \

for (pos = (head)->next; prefetch(pos->next), pos != (head); \

pos = pos->next)

生成雙向鏈表的頭結點——LIST_HEAD()

//LIST_HEAD() -- 生成一個名為name的雙向鏈表頭節點

#define LIST_HEAD(name) \

struct list_head name = LIST_HEAD_INIT(name)

static inline void INIT_LIST_HEAD(struct list_head *list)

{

list->next = list;

list->prev = list;

}

雙向鏈表的插入操作 -- list_add()

//將new所代表的結構體插入head所管理的雙向鏈表的頭節點head之后: (即插入表頭)

static inline void list_add(struct list_head *new, struct list_head *head)

{

__list_add(new, head, head->next);

}

static inline void __list_add( struct list_head *new, struct list_head *prev, struct list_head *next)

{

next->prev = new;

new->next = next;

new->prev = prev;

prev->next = new;

}

從list中刪除結點——list_del()

static inline void list_del(struct list_head *entry)

{

__list_del(entry->prev, entry->next);

entry->next = LIST_POISON1;

entry->prev = LIST_POISON2;

}

static inline void __list_del(struct list_head * prev, struct list_head * next)

{

next->prev = prev;

prev->next = next;

}

判斷鏈表是否為空(如果雙向鏈表head為空則返回真,否則為假)——list_empty()

static inline int list_empty(const struct list_head *head)

{

return head->next == head;

}

二八杠讨论心得
×