Linux內(nèi)核源碼分析-鏈表代碼分析 
分析人：余旭 
分析時間：2005年11月17日星期四 11:40:10 AM 
雨 溫度：10-11度 
編號：1-4 類別：準(zhǔn)備工作 
Email：yuxu9710108@163.com 
時代背景：開始在www.linuxforum.net Linux內(nèi)核技術(shù)論壇上面發(fā)貼，在網(wǎng)友的幫忙下，解決了一些問題。 
版權(quán)聲明：版權(quán)保留。本文用作其他用途當(dāng)經(jīng)作者本人同意,轉(zhuǎn)載請注明作者姓名 
All Rights Reserved. If for other use,must Agreed By the writer.Citing this text,please claim the writer's name. 
Copyright (C) 2005 YuXu 
************************************************** 
-------------雙向循環(huán)鏈表--------------------------- 
來源于：list.h 
設(shè)計思想：盡可能的代碼重用，化大堆的鏈表設(shè)計為單個鏈表。 
鏈表的構(gòu)造：如果需要構(gòu)造某類對象的特定列表，則在其結(jié)構(gòu)中定義一個類型為list_head指針的成員，通過這個成員將這類對象連接起來，形成所需列表，并通過通用鏈表函數(shù)對其進(jìn)行操作。其優(yōu)點是只需編寫通用鏈表函數(shù)，即可構(gòu)造和操作不同對象的列表，而無需為每類對象的每種列表編寫專用函數(shù)，實現(xiàn)了代碼的重用。 

如果想對某種類型創(chuàng)建鏈表，就把一個list_head類型的變量嵌入到該類型中，用list_head中的成員和相對應(yīng)的處理函數(shù)來對鏈表進(jìn)行遍歷。如果想得到相應(yīng)的結(jié)構(gòu)的指針，使用list_entry可以算出來。 
-------------防止重復(fù)包含同一個頭文件--------------- 
#ifndef _LINUX_LIST_H 
#define _LINUX_LIST_H 
... 
#endif 
用于防止重復(fù)包含同一個list.h頭文件 
-----------struct list_head{}及初始化宏--------- 
struct list_head 
{ 
struct list_head *next, *prev; 
}; 
list_head從字面上理解，好像是頭結(jié)點的意思。但從這里的代碼來看卻是普通結(jié)點的結(jié)構(gòu)體。在后面的代碼中將list_head當(dāng)成普通的結(jié)點來處理。 

--LIST_HEAD_INIT()--LIST_HEAD()--INIT_LIST_HEAD()------ 
#define LIST_HEAD_INIT(name) { &(name), &(name) } 
#define LIST_HEAD(name) \ 
struct list_head name = LIST_HEAD_INIT(name) 
分析：name當(dāng)為結(jié)構(gòu)體struct list_head{}的一個結(jié)構(gòu)體變量，&(name)為該結(jié)構(gòu)體變量的地址。用name結(jié)構(gòu)體變量的始地址將該結(jié)構(gòu)體變量進(jìn)行初始化。 

#define INIT_LIST_HEAD(ptr) do { \ 
(ptr)->next = (ptr); (ptr)->prev = (ptr); \ 
} while (0) 
1.ptr為一個結(jié)構(gòu)體的指針，而name為一個結(jié)構(gòu)體變量； 
2.ptr使用時候，當(dāng)用括號，(ptr); 

------------__list_add()---list_add()------------- 
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; 
} 
1.普通的在兩個非空結(jié)點中插入一個結(jié)點，注意new,prev,next都不能是空值。 
2.即：適用于中間結(jié)點插入。首結(jié)點和尾結(jié)點則由于指針為空，不能用此函數(shù)。 
3.在prev指針和next指針?biāo)赶虻慕Y(jié)點之間插入new指針?biāo)赶虻慕Y(jié)點。 

static inline void list_add(struct list_head *new, struct list_head *head) 
{ 
__list_add(new, head, head->next); 
} 
在head和head->next兩指針?biāo)赶虻慕Y(jié)點之間插入new所指向的結(jié)點。 
即：在head指針后面插入new所指向的結(jié)點。此函數(shù)用于在頭結(jié)點后面插入結(jié)點。 
注意：對只有一個單個結(jié)點的鏈表，則head->next為空，list_add（）不能用。 

-------------list_add_tail()------------------- 
static inline void list_add_tail(struct list_head *new, struct list_head *head) 
{ 
__list_add(new, head->prev, head); 
} 
在頭結(jié)點指針head所指向結(jié)點的前面插入new所指向的結(jié)點。也相當(dāng)于在尾結(jié)點后面增加一個new所指向的結(jié)點。（條件是：head->prev當(dāng)指向尾結(jié)點） 
注意： 
1.head->prev不能為空，即若head為頭結(jié)點，其head->prev當(dāng)指向一個數(shù)值，一般為指向尾結(jié)點，構(gòu)成循環(huán)鏈表。 
2.對只有單個結(jié)點的頭結(jié)點調(diào)用此函數(shù)則會出錯。 

-----------__list_del()---list_del()-------------- 
static inline void __list_del(struct list_head * prev, struct list_head * next) 
{ 
next->prev = prev; 
prev->next = next; 
} 
在prev和next指針?biāo)赶虻慕Y(jié)點之間，兩者互相所指。在后面會看到：prev為待刪除的結(jié)點的前面一個結(jié)點，next為待刪除的結(jié)點的后面一個結(jié)點。 

static inline void list_del(struct list_head *entry) 
{ 
__list_del(entry->prev, entry->next); 
entry->next = LIST_POISON1; 
entry->prev = LIST_POISON2; 
} 
刪除entry所指的結(jié)點，同時將entry所指向的結(jié)點指針域封死。 
對LIST_POISON1,LIST_POISON2的解釋說明： 
Linux 內(nèi)核中解釋：These are non-NULL pointers that will result in page faults under normal circumstances, used to verify that nobody uses non-initialized list entries. 
#define LIST_POISON1 ((void *) 0x00100100) 
#define LIST_POISON2 ((void *) 0x00200200) 
常規(guī)思想是：entry->next = NULL; entry->prev = NULL; 
注意：Linux內(nèi)核中的‘=’都與前后隔了一個空格，這樣比緊靠前后要清晰。 

---------------list_del_init()-------------------- 
static inline void list_del_init(struct list_head *entry) 
{ 
__list_del(entry->prev, entry->next); 
INIT_LIST_HEAD(entry); 
} 
刪除entry所指向的結(jié)點，同時將entry所指向的結(jié)點的next，prev指針域指向自身。 

-----------list_move()--list_move_tail()---------- 
static inline void list_move(struct list_head *list, struct list_head *head) 
{ 
__list_del(list->prev, list->next); 
list_add(list, head); 
} 
將list結(jié)點前后兩個結(jié)點互相指向彼此，刪除list指針?biāo)赶虻慕Y(jié)點，再將此結(jié)點插入head，和head->next兩個指針?biāo)赶虻慕Y(jié)點之間。 
即：將list所指向的結(jié)點移動到head所指向的結(jié)點的后面。 

static inline void list_move_tail(struct list_head *list, struct list_head *head) 
{ 
__list_del(list->prev, list->next); 
list_add_tail(list, head); 
} 
刪除了list所指向的結(jié)點，將其插入到head所指向的結(jié)點的前面，如果head->prev指向鏈表的尾結(jié)點的話，就是將list所指向的結(jié)點插入到鏈表的結(jié)尾。 

---------------------list_empty(）------------- 
static inline int list_empty(const struct list_head *head) 
{ 
return head->next == head; 
} 
注意： 
1.如果是只有一個結(jié)點，head，head->next，head->prev都指向同一個結(jié)點，則這里會返回1，但鏈表卻不為空，仍有一個頭結(jié)點 
2.return 后面不帶括號，且為一個表達(dá)式。 
3.測試鏈表是否為空,但這個空不是沒有任何結(jié)點，而是只有一個頭結(jié)點。 

--------------------list_empty_careful(）--------- 
static inline int list_empty_careful(const struct list_head *head) 
{ 
struct list_head *next = head->next; 
return (next == head) && (next == head->prev); 
} 
分析： 
1.只有一個頭結(jié)點head，這時head指向這個頭結(jié)點，head->next,head->prev指向head，即：head==head->next==head->prev，這時候list_empty_careful（）函數(shù)返回1。 
2.有兩個結(jié)點，head指向頭結(jié)點，head->next,head->prev均指向后面那個結(jié)點，即：head->next==head->prev,而head!=head->next,head!=head->prev.所以函數(shù)將返回0 
3.有三個及三個以上的結(jié)點，這是一般的情況，自己容易分析了。 
注意：這里empty list是指只有一個空的頭結(jié)點，而不是毫無任何結(jié)點。并且該頭結(jié)點必須其head->next==head->prev==head 

---------------__list_splice()------------------ 
static inline void __list_splice(struct list_head *list, struct list_head *head) 
{ 
struct list_head *first = list->next; 
struct list_head *last = list->prev; 
struct list_head *at = head->next; 

first->prev = head; 
head->next = first; 

last->next = at; 
at->prev = last; 
} 

--------------------list_splice()---------------- 
/** 
* list_splice - join two lists 
* @list: the new list to add. 
* @head: the place to add it in the first list. 
*/ 
static inline void list_splice(struct list_head *list, struct list_head *head) 
{ 
if (!list_empty(list)) 
__list_splice(list, head); 
} 
分析： 
情況1： 
普遍的情況，每個鏈表都至少有3個以上的結(jié)點： 

====>此處作者畫了圖，可顯示不出來，郁悶！！！ 

========》待作者上傳一個word文檔，圖在里面。 
------------------------------------------------------------------------------------------- 


這種情況會丟棄list所指向的結(jié)點，這是特意設(shè)計的，因為兩個鏈表有兩個頭結(jié)點，要去掉一個頭結(jié)點。只要一個頭結(jié)點。 


--------------------------------------------------------------------------------------------------------------- 

特殊情況1： 
初始情況： 


------------------------------------------------------------------------ 

特殊情況2： 
初始情況： 

--------------------list_splice_init()----------------------------------- 
/** 
* list_splice_init - join two lists and reinitialise the emptied list. 
* @list: the new list to add. 
* @head: the place to add it in the first list. 
* 
* The list at @list is reinitialised 
*/ 
static inline void list_splice_init(struct list_head *list, 
struct list_head *head) 
{ 
if (!list_empty(list)) 
{ 
__list_splice(list, head); 
INIT_LIST_HEAD(list); 
} 
} 

--------------------\asm-i386\posix_types.h------- 
typedef unsigned int __kernel_size_t; 

------\linux\types.h---------size_t--------------- 
#ifndef _SIZE_T 
#define _SIZE_T 
typedef __kernel_size_t size_t; 
#endif 
-------------\linux\compiler-gcc4.h-------------- 
#define __compiler_offsetof(a,b) __builtin_offsetof(a,b) 
分析準(zhǔn)備：__compiler_offsetof(),為gcc編譯器中的編譯方面的參數(shù)，查閱gcc方面的文檔: 
--->gcc.pdf.Download from www.gnu.org。其中解釋如下： 
#define offsetof(type, member) __builtin_offsetof (type, member) 

自己分析：即：__builtin_offsetof(a,b)就是#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)。__builtin_offsetof(a,b)和offsetof(TYPE,MEMBER)本質(zhì)一樣的，只是offsetof()宏是由程序員自己來設(shè)計(詳見后面講解)。而__builtin_offsetof()宏就是在編譯器中已經(jīng)設(shè)計好了的函數(shù)，直接調(diào)用即可。明白了這個區(qū)別后，下面的代碼很好理解。 
-------\linux\stddef.h-----offsetof()----------- 
#define __compiler_offsetof(a,b) __builtin_offsetof(a,b) 
------------------------------- 
#undef offsetof 
#ifdef __compiler_offsetof 
#define offsetof(TYPE,MEMBER) __compiler_offsetof(TYPE,MEMBER) 
#else 
#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER) 
#endif 
1.對__compiler_offsetof()宏的分析： 
__compiler_offsetof來確認(rèn)編譯器中是否內(nèi)建了功能同offsetof()宏一樣的宏。若已經(jīng)內(nèi)建了這樣的宏，則offsetof()就是使用這個內(nèi)建宏__compiler_offsetof()即：__builtin_offsetof()宏。如果沒有定義__compiler_offsetof()宏，則offsetof()宏就由程序員來設(shè)計之。 

2.對offsetof()宏的分析：（以下引用論壇）---曾經(jīng)的騰訊QQ的筆試題。 
宿舍舍友參加qq筆試，回來討論一道選擇題，求結(jié)構(gòu)中成員偏移。 
想起Linux內(nèi)核鏈表，數(shù)據(jù)節(jié)點攜帶鏈表節(jié)點，通過鏈表訪問數(shù)據(jù)的方法，用到offsetof宏，今天把它翻了出來: 
#define offsetof(TYPE, MEMBER) ((size_t) & ((TYPE *)0)->MEMBER ) 

一共4步 
1. ( (TYPE *)0 ) 將零轉(zhuǎn)型為TYPE類型指針; 
2. ((TYPE *)0)->MEMBER 訪問結(jié)構(gòu)中的數(shù)據(jù)成員; 
3. &( ( (TYPE *)0 )->MEMBER )取出數(shù)據(jù)成員的地址; 
4.(size_t)(&(((TYPE*)0)->MEMBER))結(jié)果轉(zhuǎn)換類型.巧妙之處在于將0轉(zhuǎn)換成(TYPE*)，結(jié)構(gòu)以內(nèi)存空間首地址0作為起始地址，則成員地址自然為偏移地址； 
舉例說明： 
#include<stdio.h> 
typedef struct _test 
{ 
char i; 
int j; 
char k; 
}Test; 
int main() 
{ 
Test *p = 0; 
printf("%p\n", &(p->k)); 
} 
自己分析：這里使用的是一個利用編譯器技術(shù)的小技巧，即先求得結(jié)構(gòu)成員變量在結(jié)構(gòu)體中的相對于結(jié)構(gòu)體的首地址的偏移地址，然后根據(jù)結(jié)構(gòu)體的首地址為0，從而得出該偏移地址就是該結(jié)構(gòu)體變量在該結(jié)構(gòu)體中的偏移，即：該結(jié)構(gòu)體成員變量距離結(jié)構(gòu)體首的距離。在offsetof()中，這個member成員的地址實際上就是type數(shù)據(jù)結(jié)構(gòu)中member成員相對于結(jié)構(gòu)變量的偏移量。對于給定一個結(jié)構(gòu)，offsetof(type,member)是一個常量，list_entry()正是利用這個不變的偏移量來求得鏈表數(shù)據(jù)項的變量地址。