首页 > 代码库 > Linux内核数据结构之链表
Linux内核数据结构之链表
与经典双向链表比较
??经典双向链表如图。其中有一个pre指针和一个next指针，数据是在链表的节点内。
??内核链表如图。每一个链表节点内只有一个pre指针和一个next指针，整个链表节点嵌入到了一个需要使用链表的结构体内。
内核链表介绍
??内核链表节点结构体定义如图。其中next指针指向下一个链表节点，prev指针指向前一个链表节点。
??前面已经说过，内核链表节点是嵌入到数据节点内的，那么就产生了一个问题，如何访问到链表所在结构体的指针呢？
??内核链表中通过list_entry宏来访问到链表所在结构体的指针，如下图。其中有3个参数ptr、type、member，根据注释可知，ptr是指向链表节点成员的指针变量，type就是链表节点嵌入的结构体，即包含数据成员的结构体，member是type结构体中定义的链表节点成员使用的名称。
??list_entry宏中还包含了2个宏，分别为container_of和container_of中使用的offsetof，分别如下两图。
??在GNU C中，圆括号包围的符合语句可以生成返回值，在container_of中，定义__mptr是为了防止出现ptr++等副作用。
??offsetof宏就是取type结构体中member成员相对于0地址的偏移量，最后通过__mptr减去这个偏移量，就可以获取到链表节点所在结构体的指针了。
常用函数
??INIT_LIST_HEAD：初始化一个链表头节点。
??list_add_tail：添加一个成员到链表尾。
??list_del：删除一个元素。
??如下图，在删除一个元素的时候，next和prev都不是指向null，而是分别指向了LIST_POISON1和LIST_POISON2两个指定的地址。这是为了防止有的节点申请内存错误的时候也是null，所以用了两个特定的地址，LIST_POISON1和LIST_POISON2都是低位地址，在内核空间申请内存时是不会出现的。
??List_empty：检查链表是否为空。
??list_for_each_entry：遍历链表，通过list_entry获取到外结构体指针。
内核链表的使用
??首先定义结构体，数据为ch和grade，ch保存学生姓名，grade保存学生成绩。
??然后定义one、two、three三名学生，给他们的姓名和分数赋值。定义一个链表头。
??调用INIT_LIST_HEAD进行初始化，然后one、two、three三个结点中list_head插入到链表中。
??最后调用list_for_each宏遍历输出链表，list_for_each中通过list_entry获取链表结点所在结构体。
#include<linux/kernel.h>
#include<linux/module.h>
#include<linux/list.h>
#include<linux/slab.h>
struct k_list
{
struct list_head test_list;
char ch;
int grade;
};
static __init int list_op_init(void)
{
struct k_list *one, *two, *three, *entry;
struct list_head test_head;
struct list_head *ptr;
one = kmalloc(sizeof(struct k_list *), GFP_KERNEL);
two = kmalloc(sizeof(struct k_list *), GFP_KERNEL);
three = kmalloc(sizeof(struct k_list *), GFP_KERNEL);
one->ch = ‘A‘;
two->ch = ‘B‘;
three->ch = ‘C‘;
one->grade = 90;
two->grade = 85;
three->grade = 88;
INIT_LIST_HEAD(&test_head);
list_add(&one->test_list, &test_head);
list_add(&two->test_list, &test_head);
list_add(&three->test_list, &test_head);
list_for_each(ptr, &test_head){
entry=list_entry(ptr, struct k_list, test_list);
printk(KERN_INFO "\n Hello %c,%d \n", entry->ch, entry->grade);
}
printk(KERN_INFO "\n Deleting first entry \n");
list_del(&one->test_list);
kfree((void *)one);
one = NULL;
list_for_each(ptr,&test_head){
entry=list_entry(ptr, struct k_list, test_list);
printk(KERN_INFO "\n Hello %c,%d \n", entry->ch, entry->grade);
}
printk(KERN_INFO "\n Deleting second entry \n");
list_del(&two->test_list);
kfree((void *)two);
two = NULL;
list_for_each(ptr, &test_head){
entry=list_entry(ptr, struct k_list, test_list);
printk(KERN_INFO "\n Hello %c,%d \n", entry->ch, entry->grade);
}
printk(KERN_INFO "\n Deleting third entry \n");
list_del(&three->test_list);
kfree((void *)three);
list_for_each(ptr, &test_head){
entry=list_entry(ptr, struct k_list, test_list);
printk(KERN_INFO "\n Hello %c,%d \n", entry->ch, entry->grade);
}
return 0;
}
static __exit void list_op_exit(void) {
printk(KERN_INFO "k_list module exit successfully! ...\n");
}
module_init(list_op_init);
module_exit(list_op_exit);Makefile文件内容如下：
obj-m += k_list.o
all:
make -C /lib/modules/$(shell uname -r)/build M=$(PWD) modules
clean:
make -C /lib/modules/$(shell uname -r)/build M=$(PWD) clean??以上代码是在Linux内核中编写，首先进行make，然后通过insmod加载内核模块，再通过dmesg可以查看输出结果，最后通过rmmod卸载内核模块。
??输出结果如下：
Linux内核数据结构之链表