内核链表的应用,内核链表应用
内核链表的应用,内核链表应用
本文构建了一个双向循环的内核链表,然后对链表进行遍历并打印了数据,最后释放了链表节点。使用到的数据结构和链表操作函数如下:
struct list_head 内核提供的双向循环链表节点的结构体
LIST_HEAD(name) 该宏定义并初始化一个名为name的struct list_head类型节点
INIT_LIST_HEAD(name) 该宏初始化一个由name指向的 struct list_head类型节点,事先需要定义好一个struct list_head类型变量,
并将变量的指针赋给name,然后再使用该宏
list_for_each(pos, head) 该宏可以遍历以head为链表头的循环链表,pos是遍历到的每个节点,pos和head均为指针类型。
list_entry(ptr, type, number) 该宏可以得到type类型的结构体指针,number为包含在该type类型结构体中的struct list_head类型成员变量,
ptr为&number。返回值为指向type类型的指针。
list_for_each_safe(pos, n, head)该宏类似于list_for_each宏,区别在于每次遍历,n指向了pos的下一个节点。该宏可用于释放链表节点之用。
程序代码如下:
1 #include <linux/slab.h> 2 #include <linux/sched.h> 3 #include <linux/module.h> 4 #include <linux/kernel.h> 5 #include <linux/init.h> 6 #include <linux/list.h> 7 8 struct fox { 9 int data; 10 struct list_head list; 11 }; 12 13 int i; 14 struct list_head *temp; 15 struct fox *tmp; 16 LIST_HEAD(head); 17 18 static int __init test_init(void) 19 { 20 for (i = 0; i < 10; i++) { 21 tmp = kmalloc(sizeof(*tmp), GFP_KERNEL); 22 tmp->data = i; 23 INIT_LIST_HEAD(&tmp->list); 24 list_add_tail(&tmp->list, &head); 25 } 26 27 list_for_each(temp, &head) { 28 tmp = list_entry(temp, struct fox, list); 29 printk("<0> %d\n", tmp->data); 30 } 31 32 return 0; 33 } 34 35 static void __exit test_exit(void) 36 { 37 struct list_head *next; 38 39 printk("<1> byebye\n"); 40 list_for_each_safe(temp, next, &head) { 41 tmp = list_entry(temp, struct fox, list); 42 printk("<0> %d\n", tmp->data); 43 kfree(tmp); 44 } 45 } 46 47 module_init(test_init); 48 module_exit(test_exit); 49 MODULE_LICENSE("GPL");
需要注意的是,在释放链表时,不可以直接用list_del(pos)宏来删除节点,该宏仅仅是把struct list_head节点从其链表中卸下来,而且不释放。而我们需要删除的是fox结构体,所以只能使用本文中的这种方法,利用list_for_each_safe()宏,将需要释放的节点指针保存到pos中,同时将下一个节点指针保存在next中,这样就保证了释放节点时链表不会丢失。其实list_head节点是不用单独去释放的,该结构体一般会以结构体变量的形式保存在更大的结构体中,只要释放更大结构题即可。如本例所示的那样。
也可以用list_for_each_entry()和list_for_each_entry_safe()宏来完成,代码如下:
1 #include <linux/slab.h> 2 #include <linux/sched.h> 3 #include <linux/module.h> 4 #include <linux/kernel.h> 5 #include <linux/init.h> 6 #include <linux/list.h> 7 8 struct fox { 9 int data; 10 struct list_head list; 11 }; 12 13 int i; 14 struct fox *tmp; 15 LIST_HEAD(head); 16 17 static int __init test_init(void) 18 { 19 for (i = 0; i < 10; i++) { 20 tmp = kmalloc(sizeof(*tmp), GFP_KERNEL); 21 tmp->data = i; 22 INIT_LIST_HEAD(&tmp->list); 23 list_add_tail(&tmp->list, &head); 24 } 25 26 list_for_each_entry(tmp, &head, list) { 27 printk("<0> %d\n", tmp->data); 28 } 29 30 return 0; 31 } 32 33 static void __exit test_exit(void) 34 { 35 struct fox *next; 36 37 printk("<1> byebye\n"); 38 list_for_each_entry_safe(tmp, next, &head, list) { 39 printk("<0> %d\n", tmp->data); 40 kfree(tmp); 41 } 42 } 43 44 module_init(test_init); 45 module_exit(test_exit); 46 MODULE_LICENSE("GPL");
list_for_each_entry()是list_for_each()和list_entry()二者的结合体,在该程序中对二者进行了替换,使用起来更方便。
同样,list_for_each_entry_safe是list_for_each_safe()和list_entry()二者的结合体,在本程序中替换了二者。其余都不变。
设计函数,新建集合common,分别将两个指针指在A,B的第一个元素,若相同则将此元素加入集合common,并将两个指针同时向后移一位,若不同将数值较小的指针向后移一位,直到A或B的元素被历遍
链表是一种常用的组织有序数据的数据结构,它通过指针将一系列数据节点连接成一条数据链,是线性表的一种重要实现方式。相对于数组,链表具有更好的动态性,建立链表时无需预先知道数据总量,可以随机分配空间,可以高效地在链表中的任意位置实时插入或删除数据。链表的开销主要是访问的顺序性和组织链的空间损失。
通常链表数据结构至少应包含两个域:数据域和指针域,数据域用于存储数据,指针域用于建立与下一个节点的联系。按照指针域的组织以及各个节点之间的联系形式,链表又可以分为单链表、双链表、循环链表等多种类型,下面分别给出这几类常见链表类型的示意图:
1. 单链表
图1 单链表
单链表是最简单的一类链表,它的特点是仅有一个指针域指向后继节点(next),因此,对单链表的遍历只能从头至尾(通常是NULL空指针)顺序进行。
2. 双链表
图2 双链表
通过设计前驱和后继两个指针域,双链表可以从两个方向遍历,这是它区别于单链表的地方。如果打乱前驱、后继的依赖关系,就可以构成"二叉树";如果再让首节点的前驱指向链表尾节点、尾节点的后继指向首节点(如图2中虚线部分),就构成了循环链表;如果设计更多的指针域,就可以构成各种复杂的树状数据结构。
3. 循环链表
循环链表的特点是尾节点的后继指向首节点。前面已经给出了双循环链表的示意图,它的特点是从任意一个节点出发,沿两个方向的任何一个,都能找到链表中的任意一个数据。如果去掉前驱指针,就是单循环链表。
在Linux内核中使用了大量的链表结构来组织数据,包括设备列表以及各种功能模块中的数据组织。这些链表大多采用在[include/linux/list.h]实现的一个相当精彩的链表数据结构。本文的后继部分就将通过示例详细介绍这一数据结构的组织和使用。
--------------------------------------------------------------------------------
回页首
二、 Linux 2.6内核链表数据结构的实现
尽管这里使用2.6内核作为讲解的基础,但实际上2.4内核中的链表结构和2.6并没有什么区别。不同之处在于2.6扩充了两种链表数据结构:链表的读拷贝更新(rcu)和HASH链表(hlist)。这两种扩展都是基于最基本的list结构,因此,本文主要介绍基本链表结构,然后再简要介绍一下rcu和hlist。
链表数据结构的定义很简单(节选自[include/linux/list.h],以下所有代码,除非加以说明,其余均取自该文件):
struct list_head {
struct list_head *next, *prev;
};
list_head结构包含两个指向list_head结构的指针prev和next,由此可见,内核的链表具备双链表功能,实际上,通常它都组织成双循环链表。
和第一节介绍的双链表结构模型不同,这里的list_head没有数据域。在Linux内核链表中,不是在链表结构中包含数据,而是在数据结构中包含链表节点。
在数据结构课本中,链表的经典定义方式通常是这样的(以单链表为例):
struct list_node {
struct list_node *next;
ElemTypedata;
};
因为ElemType的缘故,对每一种数据项类型都需要定义各自的链表结构。有经验的C++程序员应该知道,标准模板库中的<list>采用的是C++ Template......余下全文>>
评论暂时关闭