Chinaunix首页 | 论坛 | 博客
  • 博客访问: 7688818
  • 博文数量: 961
  • 博客积分: 15795
  • 博客等级: 上将
  • 技术积分: 16612
  • 用 户 组: 普通用户
  • 注册时间: 2010-08-07 14:23
文章分类

全部博文(961)

文章存档

2016年(1)

2015年(61)

2014年(41)

2013年(51)

2012年(235)

2011年(391)

2010年(181)

分类: 嵌入式

2011-09-19 16:35:19

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

 

内核链表

链表数据结构的定义:

struct list_head

{

struct list_head *next, *prev;

};

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

 

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

#include

#include

#include

#include

 

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);

阅读(1003) | 评论(0) | 转发(3) |
给主人留下些什么吧!~~