[arm驱动]linux内核链表

一、描述

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

二、结构提及函数

1、结构体:双向循环链表
struct list_head
{
  struct list_head *next, *prev;
};
2、相关函数
初始化
INIT_LIST_HEAD(list_head *head)

插入节点
list_add(struct list_head *new, struct list_head *head)
list_add_tail(struct list_head *new, struct list_head *head)

删除节点
list_del(struct list_head *entry)

提取数据结构(获取一个节点)
list_entry(ptr, type, member)

遍历节点
list_for_each(pos, head)

3、函数原型内核中的定义

//INIT_LIST_HEAD构造双向循环链表,将首尾相连
#define INIT_LIST_HEAD(ptr) do {    (ptr)->next = (ptr); (ptr)->prev = (ptr);
} while (0)
#define list_for_each(pos, head)
    for (pos = (head)->next; prefetch(pos->next), pos != (head);
            pos = pos->next)
#define list_entry(ptr, type, member)
    ((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member)))


4、关于list_entry(ptr, type, member) 详解

a)内核函数的定义为:

#define list_entry(ptr, type, member)
   ((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member)))在0这个地址看做有一个虚拟的type类型的变量,那么取一个成员再取这个成员的地址,就是这个结构体中这个成员的绝对地址 。
b)实例分析

typedef struct
{
int i;
int j;
}exp;
这个exp结构体占用8个字节,假设声明一个变量。
exp e1;
那么假如已知e1.j的地址,想知道e1的地址该如何办呢?只要知道j在e1中的偏移,然后把j的地址减去这个偏移就是e1的地址了。
int *p = e1.j;
假设e1的地址是0x100,那么p就是0x104。
list_entry(p, exp, j);
变成:
(exp *)((char *)p-(unsigned long)(&((exp *)0)->j)) ,在exp结构体中j成员的绝对地址是4,所以&((exp *)0)->j 就是4
&e1 == list_entry(p, exp, j)

三、使用案例:

#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;//存储student指针数组,在list_del,list_add使用
struct student *tmp_student;//临时student节点
struct list_head student_list;//本程序中的循环链表
struct list_head *pos;//节点pos
int mylist_init(void)
{
    int i = 0;
    INIT_LIST_HEAD(&student_list);//初始化,构造双向循环链表
    pstudent = kmalloc(sizeof(struct student)*5,GFP_KERNEL);//分配5个student的空间
    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);//获得临时student节点
        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);

本文出自 “lilin9105” 博客,请务必保留此出处http://7071976.blog.51cto.com/7061976/1391684

[arm驱动]linux内核链表,古老的榕树,5-wow.com

郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。