linux设备驱动-3-基本数据结构

2017-07-20

引言

内核中使用的数据结构有双向链表、hash链表和单向链表，另外，红黑树和基树(radix数)也是内核使用的数据结构。

container是Linux中很重要的一个概念，使用container能实现对象封装。代码如下：

#define offsetof(TYPE,MEMBER) ((size_t)&((TYPE *)0)->MEMBER)
#define container_of(ptr,type,member)({\
    const typeof( ((type *)0)->member) *_mptr = (ptr);\
    (type *)( (char *)_mptr - offsetof(type,member) );\
})

通过这种方法巧妙地实现了通过结构的一个成员找到整个结构的地址。内核中大使用了这种方法。

1 双向链表

list 是双向链表的一个抽象，它的定义在/include/linux目录下。

定义

1
2
3

struct list_head{
    struct list_head *next,*prev;
}

list_head这个结构看起来怪怪的，它竟没有数据域！所以看到这个结构的人第一反应就是我们怎么访问数据？
其实list_head不是拿来单独用的，它一般被嵌到其它结构中，如：

struct student
{
    int id;
    char* name;
    struct list_head list;
};

此时list_head就作为它的父结构中的一个成员了，当我们知道list_head的地址（指针）时，我们可以通过list.c提供的宏 list_entry 来获得它的父结构的地址。

可以参见Linux 内核list_head学习（一）

list提供的list_entry使用了container,通过container可以从list找到整个数据对象，这样list就成为了一种通用的数据结构。

1 2	#define list_entry(ptr,type,member) container of(ptr,type,member)

方法

LIST_HEAD //定义并初始化一个list
list_add_tail // 在list尾部加一个成员
list_del //删除一个list成员
list_empty //将list置空
list_for_each //遍历链表
list_for_each_safe //遍历并且可以删除成员
list_for_each_entry //遍历，通过container方法返回结构指针

举例

#include<linux/init.h>
#include<linux/slab.h>
#include<linux/module.h>
#include<linux/kernel.h>
#include<linux/list.h>
MODULE_LICENSE("GPL");
MODULE_AUTHOR("joystorage");
MODULE_DESCRIPTION("My First  LKM for list_head!");
struct student
{
    int id;
    char* name;
    struct list_head list;
};
void print_student(struct student*);
static int testlist_init(void)
{
    struct student *stu1, *stu2, *stu3, *stu4;
    struct student *stu;
    
    // init a list head
    LIST_HEAD(stu_head);
    // init four list nodes
    stu1 = kmalloc(sizeof(*stu1), GFP_KERNEL);
    stu1->id = 1;
    stu1->name = "wyb";
    INIT_LIST_HEAD(&stu1->list);
    stu2 = kmalloc(sizeof(*stu2), GFP_KERNEL);
    stu2->id = 2;
    stu2->name = "wyb2";
    INIT_LIST_HEAD(&stu2->list);
    stu3 = kmalloc(sizeof(*stu3), GFP_KERNEL);
    stu3->id = 3;
    stu3->name = "wyb3";
    INIT_LIST_HEAD(&stu3->list);
    stu4 = kmalloc(sizeof(*stu4), GFP_KERNEL);
    stu4->id = 4;
    stu4->name = "wyb4";
    INIT_LIST_HEAD(&stu4->list);
    // add the four nodes to head
    list_add (&stu1->list, &stu_head);
    list_add (&stu2->list, &stu_head);
    list_add (&stu3->list, &stu_head);
    list_add (&stu4->list, &stu_head);
    // print each student from 4 to 1
    list_for_each_entry(stu, &stu_head, list)
    {
        print_student(stu);
    }
    // print each student from 1 to 4
    list_for_each_entry_reverse(stu, &stu_head, list)
    {
        print_student(stu);
    }
    // delete a entry stu2
    list_del(&stu2->list);
    list_for_each_entry(stu, &stu_head, list)
    {
        print_student(stu);
    }
    // replace stu3 with stu2
    list_replace(&stu3->list, &stu2->list);
    list_for_each_entry(stu, &stu_head, list)
    {
        print_student(stu);
    }
    return 0;
}
static void testlist_exit(void)
{
    printk(KERN_ALERT "*************************\n");
    printk(KERN_ALERT "testlist is exited!\n");
    printk(KERN_ALERT "*************************\n");
}
void print_student(struct student *stu)
{
    printk (KERN_ALERT "======================\n");
    printk (KERN_ALERT "id  =%d\n", stu->id);
    printk (KERN_ALERT "name=%s\n", stu->name);
    printk (KERN_ALERT "======================\n");
}
module_init(testlist_init);
module_exit(testlist_exit);

本文总阅读量次

本文由 Yu Zhang 发表于 Yu Zhang's Blog ,采用署名-非商业性使用-禁止演绎 3.0进行许可。
非商业转载请注明作者及出处。商业转载请联系作者本人。