Linux 內(nèi)核通用鏈表學(xué)習(xí)小結(jié)
描述
在linux內(nèi)核中封裝了一個通用的雙向鏈表庫，這個通用的鏈表庫有很好的擴展性和封裝性，它給我們提供了一個固定的指針域結(jié)構(gòu)體，我們在使用的時候，只需要在我們定義的數(shù)據(jù)域結(jié)構(gòu)體中包含這個指針域結(jié)構(gòu)體就可以了，具體的實現(xiàn)、鏈接并不需要我們關(guān)心，只要調(diào)用提供給我們的相關(guān)接口就可以完成了。
傳統(tǒng)的鏈表結(jié)構(gòu)
struct node{
int key;
int val;
node* prev;
node* next;
}
linux 內(nèi)核通用鏈表庫結(jié)構(gòu)
提供給我們的指針域結(jié)構(gòu)體：
struct list_head {
struct list_head *next, *prev;
};
我們只需要包含它就可以：
struct node{
int val;
int key;
struct list_head* head;
}
可以看到通過這個 list_head 結(jié)構(gòu)就把我們的數(shù)據(jù)層跟驅(qū)動層分開了，而內(nèi)核提供的各種操作方法接口也只關(guān)心 list_head 這個結(jié)構(gòu)，也就是具體鏈接的時候也只鏈接這個list_head 結(jié)構(gòu)，并不關(guān)心你數(shù)據(jù)層定義了什么類型.
一些接口宏定義
//初始化頭指針
#define LIST_HEAD_INIT(name) { &(name), &(name) }
#define LIST_HEAD(name) \
struct list_head name = LIST_HEAD_INIT(name)
//遍歷鏈表
#define __list_for_each(pos, head) \
for (pos = (head)->next; pos != (head); pos = pos->next)
//獲取節(jié)點首地址(不是list_head地址，是數(shù)據(jù)層節(jié)點首地址)
#define list_entry(ptr, type, member) \
container_of(ptr, type, member)
//container_of在Linux內(nèi)核中是一個常用的宏，用于從包含在某個
//結(jié)構(gòu)中的指針獲得結(jié)構(gòu)本身的指針，通俗地講就是通過結(jié)構(gòu)體變
//量中某個成員的首地址進而獲得整個結(jié)構(gòu)體變量的首地址
#define container_of(ptr, type, member) ({ \
const typeof( ((type *)0)->member ) *__mptr = (ptr); \
(type *)( (char *)__mptr - offsetof(type,member) );})
#define offsetof(s,m) (size_t)&(((s *)0)->m)
使用方式
typedef struct node{
int val;
int key;
struct list_head* list;
}node;
//初始化頭指針
LIST_HEAD(head);
//創(chuàng)建節(jié)點
node* a = malloc(sizeof(node));
node* b = malloc(sizeof(node));
//插入鏈表 方式一
list_add(&a->list,&head);
list_add(&b->list,&head);
//插入鏈表 方式二
list_add_tail(&a->list,&head);
list_add_tail(&b->list,&head);
//遍歷鏈表
struct list_head* p;
struct node* n;
__list_for_each(p,head){
//返回list_head地址，然后再通過list_head地址反推
//節(jié)點結(jié)構(gòu)體首地址.
n = list_entry(pos,struct node,list);
}
list_add 接口，先入后出原則，有點類似于棧
list_add-先入后出模式
list_add_tail 接口，先入先出原則，有點類似于fifo
list_add-先入先出模式
我們的鏈表節(jié)點，實際在內(nèi)存中的展示形態(tài)
節(jié)點描述
可以看到最終的形態(tài)是，通過指向每個結(jié)構(gòu)體里面的 list_head 類型指針，然后把它們串聯(lián)起來的
list_entry 接口，通過結(jié)構(gòu)體變量某個成員的地址，反推結(jié)構(gòu)體首地址，就像 __list_for_each 接口只返回 list_head 地址，所以我們要通過這個成員地址在去獲取它本身的結(jié)構(gòu)體首地址，底層實現(xiàn)方法 container_of 宏
反推結(jié)構(gòu)體首地址
舉個例子
這個例子包括簡單的增、刪、遍歷
#include <linux/kernel.h>
#include <linux/module.h>
#include <linux/init.h>
#include <linux/slab.h>
#include <linux/list.h>
MODULE_LICENSE("GPL");
MODULE_AUTHOR("David Xie");
MODULE_DESCRIPTION("List Module");
MODULE_ALIAS("List module");
struct student //代表一個實際節(jié)點的結(jié)構(gòu)
{
char name[100];
int num;
struct list_head list; //內(nèi)核鏈表里的節(jié)點結(jié)構(gòu)
};
struct student *pstudent;
struct student *tmp_student;
struct list_head student_list;
struct list_head *pos;
int mylist_init(void)
{
int i = 0;
//初始化一個鏈表，其實就是把student_list的prev和next指向自身
INIT_LIST_HEAD(&student_list);
pstudent = kmalloc(sizeof(struct student)*5,GFP_KERNEL);//向內(nèi)核申請5個student結(jié)構(gòu)空間
memset(pstudent,0,sizeof(struct student)*5); //清空，這兩個函數(shù)可以由kzalloc單獨做到
for(i=0;i<5;i++)
{ //為結(jié)構(gòu)體屬性賦值
sprintf(pstudent[i].name,"Student%d",i+1);
pstudent[i].num = i+1;
//加入鏈表節(jié)點，list_add的話是在表頭插入，list_add_tail是在表尾插入
list_add( &(pstudent[i].list), &student_list);//參數(shù)1是要插入的節(jié)點地址，參數(shù)2是鏈表頭地址
}
list_for_each(pos,&student_list) //list_for_each用來遍歷鏈表，這是個宏定義
//pos在上面有定義
{
//list_entry用來提取出內(nèi)核鏈表節(jié)點對應(yīng)的實際結(jié)構(gòu)節(jié)點，即根據(jù)struct list_head來提取struct student
//第三個參數(shù)list就是student結(jié)構(gòu)定義里的屬性list
//list_entry的原理有點復(fù)雜，也是linux內(nèi)核的一個經(jīng)典實現(xiàn)，這個在上面那篇鏈接文章里也有講解
tmp_student = list_entry(pos,struct student,list);
//打印一些信息，以備驗證結(jié)果
printk("<0>student %d name: %s/n",tmp_student->num,tmp_student->name);
}
return 0;
}
void mylist_exit(void)
{
int i ;
/* 實驗：將for換成list_for_each來遍歷刪除結(jié)點，觀察要發(fā)生的現(xiàn)象，并考慮解決辦法 */
for(i=0;i<5;i++)
{
//額，刪除節(jié)點，只要傳個內(nèi)核鏈表節(jié)點就行了
list_del(&(pstudent[i].list));
}
//釋放空間
kfree(pstudent);
}
module_init(mylist_init);
module_exit(mylist_exit);
結(jié)束
linux 內(nèi)核提供的這個通用鏈表庫里面還有很多其他的接口，這里沒有詳細的一一舉例，有興趣的可以自己去看看，在源碼包 include/linux/list.h 文件里面，不過通過閱讀一些源代碼確實對我們也有很大的提高，可以看看高手是如何去設(shè)計并實現(xiàn)，還可以學(xué)到一些技巧以及對代碼細節(jié)的掌握~~.
以上就是本文的全部內(nèi)容，希望對大家的學(xué)習(xí)有所幫助，也希望大家多多支持本站。
版權(quán)聲明：本站文章來源標注為YINGSOO的內(nèi)容版權(quán)均為本站所有，歡迎引用、轉(zhuǎn)載，請保持原文完整并注明來源及原文鏈接。禁止復(fù)制或仿造本網(wǎng)站，禁止在非www.sddonglingsh.com所屬的服務(wù)器上建立鏡像，否則將依法追究法律責任。本站部分內(nèi)容來源于網(wǎng)友推薦、互聯(lián)網(wǎng)收集整理而來，僅供學(xué)習(xí)參考，不代表本站立場，如有內(nèi)容涉嫌侵權(quán)，請聯(lián)系alex-e#qq.com處理。
關(guān)注官方微信