一、描述

　　鏈表是一種常用的數(shù)據(jù)結(jié)構(gòu)，它通過指針將一系列數(shù)據(jù)節(jié)點(diǎn)連接成一條數(shù)據(jù)鏈。相對于數(shù)組，鏈表具有更好的動態(tài)性，建立鏈表時無需預(yù)先知道數(shù)據(jù)總量，可以隨機(jī)分配空間，可以高效地在鏈表中的任意位置實(shí)時插入或刪除數(shù)據(jù)。鏈表的開銷主要是訪問的順序性和組織鏈的空間損失。通常鏈表數(shù)據(jù)結(jié)構(gòu)至少包含兩個域：數(shù)據(jù)域和指針域，數(shù)據(jù)域用于存儲數(shù)據(jù)，指針域用于建立與下一個節(jié)點(diǎn)的聯(lián)系。Linux內(nèi)核中使用了大量的鏈表結(jié)構(gòu)來組織數(shù)據(jù)。這些鏈表大多采用了include/linux/list.h中實(shí)現(xiàn)的一套精彩的鏈表數(shù)據(jù)結(jié)構(gòu)。

二、結(jié)構(gòu)提及函數(shù)

結(jié)構(gòu)體一)1、結(jié)構(gòu)體：雙向循環(huán)鏈表
struct list_head
{
　　struct list_head *next, *prev;
};
2、相關(guān)函數(shù)
內(nèi)核驅(qū)動函數(shù)一）初始化
INIT_LIST_HEAD(list_head *head)

內(nèi)核驅(qū)動函數(shù)二）插入節(jié)點(diǎn)

list_add(struct list_head *new, struct list_head *head)
list_add_tail(struct list_head *new, struct list_head *head)

內(nèi)核驅(qū)動函數(shù)三）刪除節(jié)點(diǎn)
list_del(struct list_head *entry)

內(nèi)核驅(qū)動函數(shù)四）提取數(shù)據(jù)結(jié)構(gòu)(獲取一個節(jié)點(diǎn))
list_entry(ptr, type, member)

內(nèi)核驅(qū)動函數(shù)五）遍歷節(jié)點(diǎn)
list_for_each(pos, head)

內(nèi)核源碼一)函數(shù)原型內(nèi)核中的定義

//INIT_LIST_HEAD構(gòu)造雙向循環(huán)鏈表,將首尾相連
#define INIT_LIST_HEAD(ptr) do { (ptr)->next = (ptr); (ptr)->prev = (ptr);
} while (0)
#define list_for_each(pos, head)
for (pos = (head)->next; prefetch(pos->next), pos != (head);
pos = pos->next)
#define list_entry(ptr, type, member)
((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member)))

4、關(guān)于list_entry(ptr, type, member) 詳解

內(nèi)核源碼二)

#define list_entry(ptr, type, member)
((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member)))在0這個地址看做有一個虛擬的type類型的變量，那么取一個成員再取這個成員的地址，就是這個結(jié)構(gòu)體中這個成員的絕對地址 。
a)list_entry的原理結(jié)合代碼分析

typedef struct
{
int i;
int j;
}exp;
這個exp結(jié)構(gòu)體占用8個字節(jié)，假設(shè)聲明一個變量。
exp e1；
那么假如已知e1.j的地址，想知道e1的地址該如何辦呢？只要知道j在e1中的偏移，然后把j的地址減去這個偏移就是e1的地址了。
int *p = e1.j;
假設(shè)e1的地址是0x100，那么p就是0x104。
list_entry(p, exp, j);
變成：
(exp *)((char *)p-(unsigned long)(&((exp *)0)->j)) ,在exp結(jié)構(gòu)體中j成員的絕對地址是4，所以&((exp *)0)->j 就是4
&e1 == list_entry(p, exp, j)

實(shí)例一)三、使用案例:

#include
#include
#include
#include
#include
MODULE_LICENSE("GPL");
MODULE_AUTHOR("David Xie");
MODULE_DESCRIPTION("List Module");
MODULE_ALIAS("List module");
struct student
{
char name[100];
int num;
struct list_head list;
};
struct student *pstudent;//存儲student指針數(shù)組，在list_del，list_add使用
struct student *tmp_student;//臨時student節(jié)點(diǎn)
struct list_head student_list;//本程序中的循環(huán)鏈表
struct list_head *pos;//節(jié)點(diǎn)pos
int mylist_init(void)
{
int i = 0;
INIT_LIST_HEAD(&student_list);//初始化，構(gòu)造雙向循環(huán)鏈表
pstudent = kmalloc(sizeof(struct student)*5,GFP_KERNEL);//分配5個student的空間
memset(pstudent,0,sizeof(struct student)*5);
for(i=0;i<5;i++)
{
sprintf(pstudent[i].name,"Student%d",i+1);//賦值
pstudent[i].num = i+1;
list_add( &(pstudent[i].list), &student_list);//添加到循環(huán)鏈表中
}
list_for_each(pos,&student_list)
{
tmp_student = list_entry(pos,struct student,list);//獲得臨時student節(jié)點(diǎn)
printk("<0>student %d name: %sn",tmp_student->num,tmp_student->name);
}
return 0;
}
void mylist_exit(void)
{
int i ;
/* 將for換成list_for_each來遍歷刪除結(jié)點(diǎn)，觀察要發(fā)生的現(xiàn)象，并考慮解決辦法*/
for(i=0;i<5;i++)
{
list_del(&(pstudent[i].list));//刪除節(jié)點(diǎn)
}
kfree(pstudent);
}
module_init(mylist_init);
module_exit(mylist_exit);