Linux内核链表

luozhiyong131

链表是一种常用的数据结构，它通过指针将一系列数据节点连接成一条数据链。相对于数组，链表具有更好的动态性，建立链表时无需预先知道数据总量，可以随机分配空间，可以高效地在链表中的任意位置实时插入或删除数据。链表的开销主要是访问的顺序性和组织链的空间损失。通常链表数据结构至少包含两个域：数据域和指针域，数据域用于存储数据，指针域用于建立与下一个节点的联系。按照指针域的组织以及各个节点之间的联系形式，链表又可以分为单链表、双链表、循环链表等多种类型。在Linux内核中使用了大量的链表结构来组织数据。这些链表大多采用了[include/linux/list.h]中实现的一套精彩的链表数据结构。

 

内核链表

链表数据结构的定义：

struct list_head

{

struct list_head *next, *prev;

};

list_head结构包含两个指向list_head结构的指针prev和next，由此可见，内核的链表具备双链表功能，实际上，通常它都组织成双向循环链表。

 

Linux内核中提供的链表操作主要有：

l         初始化链表头

INIT_LIST_HEAD(list_head *head)

 

l         插入节点

list_add(struct list_head *new, struct list_head *head)

list_add_tail(struct list_head *new, struct list_head *head)

 

l         删除节点

list_del(struct list_head *entry)

 

l         提取数据结构

list_entry(ptr, type, member) 已知数据结构中的节点指针ptr，找出数据结构

 

l         遍历

list_for_each(struc list_head *pos, struc list_head *head)

 

实例：

#include <linux/kernel.h>

#include <linux/module.h>

#include <linux/init.h>

#include <linux/slab.h>

#include <linux/list.h>

 

MODULE_LICENSE("GPL");

MODULE_AUTHOR("David Xie");

MODULE_DESCRIPTION("List Module");

MODULE_ALIAS("List module");

 

struct student

{

    char name[100];

    int num;

    struct list_head list;

};

 

struct student *pstudent;

struct student *tmp_student;

struct list_head student_list;

struct list_head *pos;

 

int mylist_init(void)

{

    int i = 0;

   

    INIT_LIST_HEAD(&student_list);

   

    pstudent = kmalloc(sizeof(struct student)*5,GFP_KERNEL);

    memset(pstudent,0,sizeof(struct student)*5);

   

    for(i=0;i<5;i++)

    {

        sprintf(pstudent[i].name,"Student%d",i+1);

        pstudent[i].num = i+1;

        list_add( &(pstudent[i].list), &student_list);

    }

       

    list_for_each(pos,&student_list)

    {

        tmp_student = list_entry(pos,struct student,list);

        printk("<0>student %d name: %s\n",tmp_student->num,tmp_student->name);

    }

   

    return 0;

}

 

void mylist_exit(void)

{  

    int i ;

    /* 将for换成list_for_each来遍历删除结点，观察要发生的现象，并考虑解决办法*/

    for(i=0;i<5;i++)

    {

        list_del(&(pstudent[i].list));    

    }

   

    kfree(pstudent);

}

 

module_init(mylist_init);

module_exit(mylist_exit);