arm驅動linux內核鏈表

一、描述

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

二、結構提及函數

結構體一)1、結構體：雙向循環鏈表
struct list_head
{
　　struct list_head *next, *prev;
};
2、相關函數
內核驅動函數一）初始化
INIT_LIST_HEAD(list_head *head)

內核驅動函數二）插入節點

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

內核驅動函數三）刪除節點
list_del(struct list_head *entry)

內核驅動函數四）提取數據結構(獲取一個節點)
list_entry(ptr, type, member)

內核驅動函數五）遍歷節點
list_for_each(pos, head)

內核源碼一)函數原型內核中的定義

//INIT_LIST_HEAD構造雙向循環鏈表,將首尾相連
#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、關于list_entry(ptr, type, member) 詳解

內核源碼二)

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

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

實例一)三、使用案例:

#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指針數組，在list_del，list_add使用
struct student *tmp_student;//臨時student節點
struct list_head student_list;//本程序中的循環鏈表
struct list_head *pos;//節點pos
int mylist_init(void)
{
int i = 0;
INIT_LIST_HEAD(&student_list);//初始化，構造雙向循環鏈表
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);//添加到循環鏈表中
}
list_for_each(pos,&student_list)
{
tmp_student = list_entry(pos,struct student,list);//獲得臨時student節點
printk("<0>student %d name: %sn",tmp_student->num,tmp_student->name);
}
return 0;
}
void mylist_exit(void)
{
int i ;
/* 將for換成list_for_each來遍歷刪除結點，觀察要發生的現象，并考慮解決辦法*/
for(i=0;i<5;i++)
{
list_del(&(pstudent[i].list));//刪除節點
}
kfree(pstudent);
}
module_init(mylist_init);
module_exit(mylist_exit);