使用list_head建立双联表

2011年5月24日 由 edsionte 留言 »

内核中与链表有关的操作都集中在list.h文件中,该文件不仅定义了链表数据结构,而且包含大量对链表操作的函数。

下面通过一个内核模块简单说明内核双链表的用法。该内核模块的加载函数首先建立了一个具有N个节点的双链表,然后再遍历该链表;在该内核模块卸载函数中,依次将每个节点从双链表中删除,并释放每个节点所占用的内核空间的内存。

在具体说明该程序之前,有必要搞清楚两个概念:链表中的数据节点和链表节点。内核在list.h中定义的链表节点list_head称之为链表节点。该结构除了指向前后节点的指针外,并不包含任何数据变量。因此,在实际使用的过程中,我们必须将所需数据和链表节点封装在一个数据结构中,这个新的数据结构就是数据节点。比如,在示例程序中,我们的数据节点除了包含链表节点外,还包含一个数据成员num。

#define N 10
//链表节点
struct numlist {
	int num;//数据
	struct list_head list;//指向双联表前后节点的指针
};
struct numlist numhead;//头节点

在使用双联表的操作函数时也应该注意数据节点和链表节点之间的差异。所有与双联表有关的操作函数都是对链表节点的操作,也就是说我们应该对这些函数传入链表节点(或指针)而不是数据节点。

在加载函数中,我们通过INIT_LIST_HEAD宏初始化链表的头指针。通过查看该宏的定义可知,必须向其传入一个list_head结构的指针变量,因此我们将&numhead.list传入其中。

接着,通过循环分别创建N个数据节点,并在创建完每个节点后,将其加入整个双链表中。将节点加入双链表的过程是通过list_add_tail函数完成的,该函数将新节点加入到双链表的末尾。

static int __init doublelist_init(void)
{
	//初始化头节点
	struct numlist *listnode;//每次申请链表节点时所用的指针
	struct list_head *pos;
	struct numlist *p;
	int i;

	printk("doublelist is starting...\n");
	INIT_LIST_HEAD(&numhead.list);

	//建立N个节点,依次加入到链表当中
		for (i = 0; i < N; i++) {
		listnode = (struct numlist *)kmalloc(sizeof(struct numlist), GFP_KERNEL);
		listnode->num = i+1;
		list_add_tail(&listnode->list, &numhead.list);
		printk("Node %d has added to the doublelist...\n", i+1);
	}

加载函数创建完双链表后,紧接着又对该双链表进行了遍历操作。我们在上面说过双链表的操作函数是对链表节点list_head进行操作的,因此遍历宏list_for_each也是对链表节点的遍历。如果我们需要得到数据节点中每个成员的值,那么就必须获得当前数据节点的指针,也就是该节点的首地址。因此list_entry宏的作用就是通过当前正在遍历的链表节点的指针pos获得其所属数据节点的指针p。

这里特别说明一下list_entry宏的参数,pos所指向的list_head结构在numlist结构中的字段称为list。

	//遍历链表
	i = 1;
	list_for_each(pos, &numhead.list) {
		p = list_entry(pos, struct numlist, list);
		printk("Node %d's data:%d\n", i, p->num);
		i++;
	}

	return 0;
}

在卸载函数中将会依次删除链表中的节点。list_for_each_safe遍历宏是专门为删除链表结点而设计的,它在遍历当前节点对同时保存下一个节点的地址。因此在每次遍历的时候一方面使用list_del将当前链表节点从整个链表中删除,一方面使用kfree函数释放该数据节点所占的内存空间。

static void __exit doublelist_exit(void)
{
	struct list_head *pos, *n;
	struct numlist *p;
	int i;

	//依次删除N个节点
	i = 1;
	list_for_each_safe(pos, n, &numhead.list) {
		list_del(pos);//从双联表中删除当前节点
		p = list_entry(pos, struct numlist, list);//得到当前数据节点的首地址,即指针
		kfree(p);//释放该数据节点所占空间
		printk("Node %d has removed from the doublelist...\n", i++);
	}
	printk("doublelist is exiting..\n");
}

该实例程序的完整代码可在此下载。

广告位

2 条评论

  1. zhaoqiao说道:

    very good !
    study to you !

    [回复一下]

    edsionte 回复:

    @zhaoqiao, 一起加油。

    [回复一下]

发表评论

windows 7 ultimate product key

windows 7 ultimate product key

winrar download free

winrar download free

winzip registration code

winzip registration code

winzip free download

winzip free download

winzip activation code

winzip activation code

windows 7 key generator

windows 7 key generator

winzip freeware

winzip freeware

winzip free download full version

winzip free download full version

free winrar download

free winrar download

free winrar

free winrar

windows 7 crack

windows 7 crack

windows xp product key

windows xp product key

windows 7 activation crack

windows7 activation crack

free winzip

free winzip

winrar free download

winrar free download

winrar free

winrar free

download winrar free

download winrar free

windows 7 product key

windows 7 product key