本文轉(zhuǎn)載自：http://blog.csdn.net/coding__madman/article/details/51325646
鏈表簡介：
鏈表是一種常用的數(shù)據(jù)結(jié)構(gòu)，它通過指針將一系列數(shù)據(jù)節(jié)點連接成一條數(shù)據(jù)鏈。相對于數(shù)組，鏈表具有更好的動態(tài)性，建立鏈表時無需預先知道數(shù)據(jù)總量，可以隨機分配空間，可以高效地在鏈表中的任意位置實時插入或者刪除數(shù)據(jù)。鏈表的開銷主要是訪問的順序性和組織鏈的空間損失。
?
內(nèi)核鏈表的好主要體現(xiàn)為兩點，1是可擴展性，2是封裝。可擴展性肯定是必須的，內(nèi)核一直都是在發(fā)展中的，所以代碼都不能寫成死代碼，要方便修改和追加。將鏈表常見的操作都進行封裝，使用者只關(guān)注接口，不需關(guān)注實現(xiàn)。分析內(nèi)核中的鏈表我們 可以做些什么呢？我覺得可以將其復用到用戶態(tài)編程中，以后在用戶態(tài)下編程就不需要寫一些關(guān)于鏈表的代碼了，直接將內(nèi)核中l(wèi)ist.h中的代碼拷貝過來用。也可以整理出my_list.h，在以后的用戶態(tài)編程中直接將其包含到C文件中。
?
?
1. 鏈表對比
傳統(tǒng)鏈表和內(nèi)核鏈表
傳統(tǒng)鏈表：一般指的是單向鏈表
struct List
{
struct list *next;//鏈表結(jié)點指針域
};
內(nèi)核鏈表：雙向循環(huán)鏈表 設(shè)計初衷是設(shè)計出一個通用統(tǒng)一的雙向鏈表！
struct list_head
{
?struct list_head ? ?*head, *prev;
};
list_head結(jié)構(gòu)包含兩個指向list_head結(jié)構(gòu)體的指針
prev和next，由此可見，內(nèi)核的鏈表具備雙鏈表功能，實際上，通常它都組織成雙向循環(huán)鏈表
2. 內(nèi)核鏈表使用
1. INIT_LIST_HEAD:創(chuàng)建鏈表
2. list_add:在鏈表頭插入節(jié)點
3. list_add_tail:在鏈表尾插入節(jié)點
4. list_del:刪除節(jié)點
5. list_entry:取出節(jié)點
6. list_for_each:遍歷鏈表
(如果我們不知道這些函數(shù)的參數(shù)以及函數(shù)內(nèi)部實現(xiàn)，學習查閱這些函數(shù)的參數(shù)或者實現(xiàn)代碼最好的方法還是直接查看內(nèi)核源碼,結(jié)和前面的用sourceInsight工具直接搜索這些函數(shù)的名字)
?
?
?
下面舉個例子：比如查閱INIT_LIST_HEAD函數(shù)，
這個是先將內(nèi)核源碼導入sourceInsight工程里面！源碼可以在官網(wǎng)上下載，然后在Linux下解壓（文件名Linux分大小寫，windows不分大小寫），然后通過Samba和映射網(wǎng)絡驅(qū)動器功能（前面的sourceInsight博文有講到），點擊R圖標左邊的那個圖標（像一個打開的一本書）
這樣可以很快的查看到代碼實現(xiàn)部分：在內(nèi)核Mkregtale.c文件中
?
[html]?view plaincopy
/*???*?This?is?a?simple?doubly?linked?list?implementation?that?matches?the???*?way?the?Linux?kernel?doubly?linked?list?implementation?works.???*/????struct?list_head?{??????struct?list_head?*next;?/*?next?in?chain?*/??????struct?list_head?*prev;?/*?previous?in?chain?*/??};?? 這個不含數(shù)據(jù)域的鏈表,可以嵌入到任何數(shù)據(jù)結(jié)構(gòu)中,例如可按如下方式定義含有數(shù)據(jù)域的鏈表：
?
[html]?view plaincopy
struct?score??{??????int?num;??????int?English;??????int?math;??????struct?list_head?list;//鏈表鏈接域??};????struct?list_head?score_head;//所建立鏈表的鏈表頭?? INIT_LIST_HEAD(&score_head);//初始化鏈表頭 完成一個雙向循環(huán)鏈表的創(chuàng)建
上面的紅色部分初始化一個已經(jīng)存在的list_head對象，score_head為一個結(jié)構(gòu)體的指針，這樣可以初始化堆棧以及全局區(qū)定義的score_head對象。調(diào)用INIT_LIST_HEAD()宏初始化鏈表節(jié)點，將next和prev指針都指向其自身，我們就構(gòu)造了一個空的雙循環(huán)鏈表。
?
初始化一個空鏈表：其實就是鏈表頭，用來指向第一個結(jié)點！定義結(jié)點并且初始化！然后雙向循環(huán)鏈表就誕生了
?
static 加在函數(shù)前，表示這個函數(shù)是靜態(tài)函數(shù)，其實際上是對作用域的限制，指該函數(shù)作用域僅局限于本文件。所以說，static 具有信息隱蔽的作用。而函數(shù)前加?inline?關(guān)鍵字的函數(shù)，叫內(nèi)聯(lián)函數(shù)，表 示編譯程序在調(diào)用這個函數(shù)時，立即將該函數(shù)展開。
?
?
[html]?view plaincopy
/*?Initialise?a?list?head?to?an?empty?list?*/??static?inline?void?INIT_LIST_HEAD(struct?list_head?*list)??{??????????list->next?=?list;??????list->prev?=?list;??}?? ?
?
list_add:在鏈表頭插入節(jié)點
?
[html]?view plaincopy
/**???*?list_add?-?add?a?new?entry???*?@new:?new?entry?to?be?added???*?@head:?list?head?to?add?it?after???*???*?Insert?a?new?entry?after?the?specified?head.???*?This?is?good?for?implementing?stacks.???*/??static?inline?void?list_add(struct?list_head?*new,?struct?list_head?*head)??{????__list_add(new,?head,?head->next);??}?? ?
[html]?view plaincopy
/*???*?Insert?a?new?entry?between?two?known?consecutive?entries.???*???*?This?is?only?for?internal?list?manipulation?where?we?know???*?the?prev/next?entries?already!???*/??#ifndef?CONFIG_DEBUG_LIST??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;??}??#else??extern?void?__list_add(struct?list_head?*new,????????????????????struct?list_head?*prev,????????????????????struct?list_head?*next);??#endif??
?
?list_add_tail:在鏈表尾插入節(jié)點
?
[html]?view plaincopy
/**???*?list_add_tail?-?add?a?new?entry???*?@new:?new?entry?to?be?added???*?@head:?list?head?to?add?it?before???*???*?Insert?a?new?entry?before?the?specified?head.???*?This?is?useful?for?implementing?queues.???*/??static?inline?void?list_add_tail(struct?list_head?*new,?struct?list_head?*head)??{??????__list_add(new,?head->prev,?head);??}?? ?
用法示例：
struct score
{
int num;
int English;
int math;
struct list_head list;//鏈表鏈接域
};
struct list_head score_head;//所建立鏈表的鏈表頭
//定義三個節(jié)點 然后插入到鏈表中
struct score stu1, stu2, stu3;
list_add_tail(&(stu1.list), &score_head);//使用尾插法
Linux 的每個雙循環(huán)鏈表都有一個鏈表頭，鏈表頭也是一個節(jié)點，只不過它不嵌入到宿主數(shù)據(jù)結(jié)構(gòu)中，即不能利用鏈表頭定位到對應的宿主結(jié)構(gòu)，但可以由之獲得虛擬的宿主結(jié)構(gòu)指針。
?
?
?list_del:刪除節(jié)點
?
[html]?view plaincopy
/*?Take?an?element?out?of?its?current?list,?with?or?without???*?reinitialising?the?links.of?the?entry*/??static?inline?void?list_del(struct?list_head?*entry)??{??????struct?list_head?*list_next?=?entry->next;??????struct?list_head?*list_prev?=?entry->prev;????????list_next->prev?=?list_prev;??????list_prev->next?=?list_next;????}??
?
list_entry:取出節(jié)點
?
[html]?view plaincopy
/**???*?list_entry?-?get?the?struct?for?this?entry???*?@ptr:the?&struct?list_head?pointer.???*?@type:the?type?of?the?struct?this?is?embedded?in.???*?@member:the?name?of?the?list_struct?within?the?struct.???*/??#define?list_entry(ptr,?type,?member)?\??????container_of(ptr,?type,?member)?? ?
?
[html]?view plaincopy
/**???*?container_of?-?cast?a?member?of?a?structure?out?to?the?containing?structure???*?@ptr:????the?pointer?to?the?member.???*?@type:???the?type?of?the?container?struct?this?is?embedded?in.???*?@member:?the?name?of?the?member?within?the?struct.???*???*/??#define?container_of(ptr,?type,?member)?({??????????\??????const?typeof(((type?*)0)->member)*__mptr?=?(ptr);????\???????????????(type?*)((char?*)__mptr?-?offsetof(type,?member));?})??
list_for_each:遍歷鏈表
[html]?view plaincopy
#define?list_for_each(pos,?head)?\??????for?(pos?=?(head)->next;?prefetch(pos->next),?pos?!=?(head);?\??????pos?=?pos->next)</span></span>?? ?
可以看出，使用了輔助指針pos,pos是從第一節(jié)點開始的，并沒有訪問頭節(jié)點，直到pos到達頭節(jié)點指針head的時候結(jié)束。 而且 這種遍歷僅僅是找到一個個結(jié)點的當前位置，那如何通過pos獲得起始結(jié)點的地址，從而可以引用結(jié)點的域？ list.h 中定義了 list_entry 宏： #define ? list_entry( ptr, type, member ) ?\ ( (type *) ( (char *) (ptr) ?- (unsigned long) ( &( (type *)0 ) ?-> ?member ) ) ) 分析：(unsigned long) ( &( (type *)0 ) ?-> ?member ) 把 0 地址轉(zhuǎn)化為 type 結(jié)構(gòu)的指針，然后獲取該 結(jié)構(gòu)中 member 域的指針，也就是獲得了 member 在type 結(jié)構(gòu)中的偏移量。其中??(char *) (ptr) 求 出的是 ptr?的絕對地址，二者相減，于是得到 type 類型結(jié)構(gòu)體的起始地址，即起始結(jié)點的地址。使用方法非常的巧妙！
比如下列用法：
?
struct score stu1, stu2, stu3;
struct list_head *pos;//定義一個結(jié)點指針
struct score *tmp;//定義一個score結(jié)構(gòu)體變量
?
[html]?view plaincopy
//遍歷整個鏈表，每次遍歷將數(shù)據(jù)打印出來??????list_for_each(pos,?&score_head)//這里的pos會自動被賦新值??????{??????????tmp?=?list_entry(pos,?struct?score,?list);??????????printk(KERN_WARNING"num:?%d,?English:?%d,?math:?%d\n",?tmp->num,?tmp->English,?tmp->math);??????}??
?
?
list_for_each_safe: 鏈表的釋放
?
[html]?view plaincopy
/**???*?list_for_each_safe?-?iterate?over?a?list?safe?against?removal?of?list?entry???*?@pos:the?&struct?list_head?to?use?as?a?loop?cursor.???*?@n:another?&struct?list_head?to?use?as?temporary?storage???*?@head:</span>the?head?for?your?list.???*/??#define?list_for_each_safe(pos,?n,?head)?\??????for?(pos?=?(head)->next,?n?=?pos->next;?pos?!=?(head);?\??????????pos?=?n,?n?=?pos->next)??
?
3. 內(nèi)核鏈表實現(xiàn)分析
4. 移植內(nèi)核鏈表（這里先貼出一個使用內(nèi)核鏈表的內(nèi)核模塊小例程）
mylist.c文件
?
[html]?view plaincopy
#include<linux/module.h>??#include<linux/init.h>??#include<linux/list.h>//包含內(nèi)核鏈表頭文件????struct?score??{??????int?num;??????int?English;??????int?math;??????struct?list_head?list;//鏈表鏈接域??};????struct?list_head?score_head;//所建立鏈表的鏈表頭????//定義三個節(jié)點?然后插入到鏈表中??struct?score?stu1,?stu2,?stu3;??struct?list_head?*pos;//定義一個結(jié)點指針??struct?score?*tmp;//定義一個score結(jié)構(gòu)體變量????int?mylist_init()??{??????INIT_LIST_HEAD(&score_head);//初始化鏈表頭?完成一個雙向循環(huán)鏈表的創(chuàng)建????????????stu1.num?=?1;??????stu1.English?=?59;??????stu1.math?=?99;????????????//然后將三個節(jié)點插入到鏈表中??????list_add_tail(&(stu1.list),?&score_head);//使用尾插法????????????stu2.num?=?2;??????stu2.English?=?69;??????stu2.math?=?98;??????list_add_tail(&(stu2.list),?&score_head);????????????stu3.num?=?3;??????stu3.English?=?89;??????stu3.math?=?97;??????list_add_tail(&(stu3.list),?&score_head);????????????//遍歷整個鏈表，每次遍歷將數(shù)據(jù)打印出來??????list_for_each(pos,?&score_head)//這里的pos會自動被賦新值??????{??????????tmp?=?list_entry(pos,?struct?score,?list);??????????printk(KERN_WARNING"num:?%d,?English:?%d,?math:?%d\n",?tmp->num,?tmp->English,?tmp->math);??????}????????????return?0;??}????void?mylist_exit()??{??????//退出時刪除結(jié)點??????list_del(&(stu1.list));??????list_del(&(stu2.list));??????printk(KERN_WARNING"mylist?exit!\n");??}????module_init(mylist_init);??module_exit(mylist_exit);??
Makefile文件
?
?
[html]?view plaincopy
obj-m?:=?mylist.o????KDIR?:=?/home/kernel/linux-ok6410????all:??????make?-C?$(KDIR)?M=$(PWD)?modules?CROSS_COMPILE=arm-linux-?ARCH=arm????????clean:??????rm?-f?*.o?*.ko?*.order?*.symvers??
?
在終端上加載運行內(nèi)核模塊：
這里rmmod 時會有個錯誤！不過沒大事！百度有很多解決方案！
總結(jié)
以上是生活随笔為你收集整理的Linux内核链表深度分析【转】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。
