分类: 嵌入式
2011-09-19 16:35:19
链表是一种常用的数据结构,它通过指针将一系列数据节点连接成一条数据链。相对于数组,链表具有更好的动态性,建立链表时无需预先知道数据总量,可以随机分配空间,可以高效地在链表中的任意位置实时插入或删除数据。链表的开销主要是访问的顺序性和组织链的空间损失。通常链表数据结构至少包含两个域:数据域和指针域,数据域用于存储数据,指针域用于建立与下一个节点的联系。按照指针域的组织以及各个节点之间的联系形式,链表又可以分为单链表、双链表、循环链表等多种类型。在Linux内核中使用了大量的链表结构来组织数据。这些链表大多采用了[include/linux/list.h]中实现的一套精彩的链表数据结构。
内核链表
链表数据结构的定义:
struct list_head
{
struct list_head *next, *prev;
};
list_head结构包含两个指向list_head结构的指针prev和next,由此可见,内核的链表具备双链表功能,实际上,通常它都组织成双向循环链表。
Linux内核中提供的链表操作主要有:
l 初始化链表头
INIT_LIST_HEAD(list_head *head)
l 插入节点
list_add(struct list_head *new, struct list_head *head)
list_add_tail(struct list_head *new, struct list_head *head)
l 删除节点
list_del(struct list_head *entry)
l 提取数据结构
list_entry(ptr, type, member) 已知数据结构中的节点指针ptr,找出数据结构
l 遍历
list_for_each(struc list_head *pos, struc list_head *head)
实例:
#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;
struct student *tmp_student;
struct list_head student_list;
struct list_head *pos;
int mylist_init(void)
{
int i = 0;
INIT_LIST_HEAD(&student_list);
pstudent = kmalloc(sizeof(struct student)*5,GFP_KERNEL);
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);
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来遍历删除结点,观察要发生的现象,并考虑解决办法*/
for(i=0;i<5;i++)
{
list_del(&(pstudent[i].list));
}
kfree(pstudent);
}
module_init(mylist_init);
module_exit(mylist_exit);