双向链表辅助接口

 内核中大量使用双向链表来维护相关数据的关系，特别是在一些数据处理模块上面；
 双向链表结构和接口分别在“linux/types.h"和"linux/list.h"中定义。

1 双向链表结构

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

2 该链表使用方法
  通常将这个链表内嵌到其他数据结构体里面，用来组成带有数据的一个链表， 示意图如下：

3 内核提供的接口
  这里是列出几个经常用到的接口，如果想了解更多的接口请查看"linux/list.h"头文件。

LIST_HEAD(name);      /*定义并初始化name变量*/
LIST_HEAD_INIT(name); /*初始化name变量*/

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

/*在head节点后面添加新节点，如果head为链表头，则添加在链表头部*/

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

     /*在head节点前面添加新节点，如果head为链表头，则添加在链表尾部*/

void list_del(struct list_head *entry);      /*删除链表中指定的节点*/
void list_del_init(struct list_head *entry); /*删除链表中指定的节点并重新初始化该节点*/

void list_move(struct list_head *list, struct list_head *head);

/*将list节点移动 到head节点后面*/

void list_move_tail(struct list_head *list, struct list_head *head);

/*将list节点移动到head节点前面*/

int list_empty(const struct list_head *head); /*判断链表是否为空，是的话返回1*/

void list_splice(const struct list_head *list, struct list_head *head);

/*将list链表添加到head节点后面*/

void *list_entry(struct list_head *ptr, type, member);

/*将ptr指针映射回指向包含它的大结构的指针*/

list_for_each(*pos, *head);               /*遍历链表，使用时需加{}*/
list_for_each_prev(*pos, *head);          /*向后遍历链表*/
list_for_each_entry(*pos, *head, member); /*遍历链表，并将大结构的指针赋给pos*/ list_for_each_entry_safe(*pos, *n, *head, member); /*同上*/

注意：使用链表时，千万要注意指针的使用，使用错误的指针可能会导致内核崩溃。

4 示例代码    list.rar  
 这里只使用几个接口进行演示。

#include <linux/module.h>
#include <linux/init.h>
#include <linux/list.h>
#include <linux/slab.h>

MODULE_LICENSE("Dual BSD/GPL");
MODULE_AUTHOR("Kozo");

/*自己定义的结构体,内嵌list_head结构体*/
struct my_struct{
    const char *name;
    int index;
    struct list_head list;
};

/*两种定义及初始化list_head结构的变量*/
//struct list_head head = LIST_HEAD_INIT(head);
LIST_HEAD(head);
static int __init demo_init(void)
{
    struct my_struct *task1;
    struct my_struct *task2;
    struct my_struct *task3;

    task1 = (struct my_struct *)kmalloc(sizeof(struct my_struct),GFP_KERNEL);
    task2 = (struct my_struct *)kmalloc(sizeof(struct my_struct),GFP_KERNEL);
    task3 = (struct my_struct *)kmalloc(sizeof(struct my_struct),GFP_KERNEL);

    task1->name="One";
    task1->index=1;
    task2->name="Two";
    task2->index=2;
    task3->name="Three";
    task3->index=3;

    list_add(&task1->list,&head);
    list_add(&task2->list,&head);
    list_add(&task3->list,&head);

    printk(KERN_DEBUG"added node\n");
    return 0;
}

static void __exit demo_exit(void)
{
    struct my_struct *task;
    struct my_struct *tmp = NULL;
    list_for_each_entry(task,&head,list){
        printk(KERN_DEBUG"name:%s,index:%d\n",task->name,task->index);
        if(tmp == NULL)
   /*注意，使用list_for_each_entry时，不能删除读取到节点，但可以删除该节点的前节点或后节点*/
            tmp = task;
        else
        {
            list_del(&tmp->list);
            kfree(tmp);
            tmp = task;
        }
    }
        list_del(&tmp->list);
        kfree(tmp);
    /*确认已经删除所有添加的节点*/
    list_for_each_entry(task,&head,list){
        printk(KERN_DEBUG"name:%s,index:%d\n",task->name,task->index);
    }
    printk("drop node,and free memory\n");
}
module_init(demo_init);
module_exit(demo_exit);

5 执行结果


注：转载时请注明出自:add358.blog.chinaunix.net