Linux内核链表-白红宇

Linux内核链表

阅读量：4286 次

发布时间：2019-05-27

本文共 2412 字，大约阅读时间需要 8 分钟。

链表是一种常用的数据结构，它通过指针将一系列数据节点连接成一条数据链。相对于数组，链表具有更好的动态性。建立链表时无需预先知道数据总量，可以随机分配空间，可以高效地在链表中的任意位置实时插入或删除数据。链表的开销主要是访问的顺序性和组织链的空间损失。

链表的结构有多种，如单向链表，双向链表等。Linux内核链表属于双向循环链表，但与传统的双向链表有所区别。链表的每个节点都含有数据域和指针域，传统的链表的指针域指向另一个节点，而Linux内核链表的指针域指向另一个节点的指针域。比如传统链表的节点结构为：

struct node{    int data;    struct node *prior;    struct node *next;};

而Linux内核链表的节点结构为：

struct node{    int data;    struct list_head list;};

list_head结构包含两个指向list_head结构的指针prev和next

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

不采用传统的链表结构而设计出新的链表结构是为了能够对链表进行统一的操作。即比如对于在链表插入节点，删除节点这些操作，传统的链表结构对于不同结构的节点需要有不同的函数来完成，而Linux内核链表可以采用统一的函数来完成。

内核链表的相关函数定义在<linux/list.h>头文件中，主要的函数有：

INIT_LIST_HEAD:创建链表list_add：在链表头插入节点list_add_tail：在链表尾插入节点list_del：删除节点list_entry：取出节点list_for_each：遍历链表

这些函数的具体使用方法可以通过查看内核代码学习。

由于是内核链表，因此编程实现的模块是内核模块。若要该模块是在开发板的Linux系统中运行，则Makefile的编写与之前的Makefile编写有些许差异，一个Makefile例子如下：

obj-m : mylist.oKDIR := /home/linux-tiny6410/all:    make -C $(KDIR) M=$(PWD) modules CROSS_COMPILE=arm-linux- ARCH=arm

内核模块代码如下：

#include 
   
    #include 
    
     #include 
     
      MODULE_AUTHOR("jx");MODULE_LICENSE("GPL");typedef struct student{    int num;    int english;    int math;    struct list_head list;}student;student stu1,stu2,stu3;struct list_head student_head;struct list_head *pos;student *tmp;static int test_init(void){    stu1.num=1;    stu1.english=90;    stu1.math=80;    stu2.num=2;    stu2.english=95;    stu2.math=85;    stu3.num=3;    stu3.english=96;    stu3.math=86;    INIT_LIST_HEAD(&student_head);/*创建链表*/    /*添加节点到链表中*/    list_add_tail(&(stu1.list),&student_head);    list_add_tail(&(stu2.list),&student_head);    list_add_tail(&(stu3.list),&student_head);    /*遍历链表，将所有数据打印出来*/    list_for_each(pos,&student_head)    {        tmp=list_entry(pos,student,list);        printk(KERN_EMERG "num is %d,the score of english is %d,the score of math is %d\n",tmp->num,tmp->english,tmp->math);    }    return 0;}static void test_exit(void){    list_del(&(stu1.list));    list_del(&(stu2.list));    list_del(&(stu3.list));} module_init(test_init);module_exit(test_exit);

链表相关的函数中，比较经典的函数是list_entry()，源代码为：

#define list_entry(ptr, type, member) \    container_of(ptr, type, member)#define container_of(ptr, type, member) ({          \    const typeof( ((type *)0)->member ) *__mptr = (ptr);    \    (type *)( (char *)__mptr - offsetof(type,member) );})

即根据指针域相对于该节点初始地址的偏移量以及指针域的地址找到该结点的初始地址，从而使节点结构指针能够指向该节点。

转载地址：http://brigi.baihongyu.com/

你可能感兴趣的文章