首页 > 代码库 > linux驱动开发要知道的那些知识（二）------list内核链表
linux驱动开发要知道的那些知识（二）------list内核链表
内核链表
链表数据结构简介
链表是一种常用的组织有序数据的数据结构，它通过指针将一系列数据节点连接成一条数据链，是线性表的一种重要实现方式。相对于数组，链表具有更好的动态性，建立链表时无需预先知道数据总量，可以随机分配空间，可以高效地在链表中的任意位置实时插入或删除数据。链表的开销主要是访问的顺序性和组织链的空间损失。
通常链表数据结构至少应包含两个域：数据域和指针域，数据域用于存储数据，指针域用于建立与下一个节点的联系。按照指针域的组织以及各个节点之间的联系形式，链表又可以分为单链表、双链表、循环链表等多种类型，下面分别给出这几类常见链表类型的示意图：
1． 单链表
图1 单链表
单链表是最简单的一类链表，它的特点是仅有一个指针域指向后继节点（next），因此，对单链表的遍历只能从头至尾（通常是NULL空指针）顺序进行。
2． 双链表
通过设计前驱和后继两个指针域，双链表可以从两个方向遍历，这是它区别于单链表的地方。如果打乱前驱、后继的依赖关系，就可以构成"二叉树"；如果再让首节点的前驱指向链表尾节点、尾节点的后继指向首节点（如图2中虚线部分），就构成了循环链表；如果设计更多的指针域，就可以构成各种复杂的树状数据结构。
在<linux/list>
struct list_head{
struct list_head *next,prev;
}
list_head结构包含两个指向list_head结构的指针prev和next，由此可见，内核的链表具备双链表功能，实际上，通常它都组织成双循环链表。
和第一节介绍的双链表结构模型不同，这里的list_head没有数据域。在Linux内核链表中，不是在链表结构中包含数据，而是在数据结构中包含链表节点。
下图为数据结构中链表和内核链表区别：
基于topeet 4412开发板 代码示例：
***********************************************************
#include <linux/init.h>
#include <linux/module.h>
#include <linux/list.h>
#include <linux/slab.h>
#include <linux/fs.h>
MODULE_LICENSE("Dua BSD/GPL");
#define STRUD_NUM 5
struct list_head strud_list;
struct strudent{
unsigned char name[20];
unsigned long int str_id;
unsigned int mark;
struct list_head list;
};
static struct strudent *strude=NULL;
static struct strudent *strude_tmp=NULL;
static struct list_head *pos=NULL;
static int __init strud_init(void)
{
int i=0;
printk(KERN_INFO "Test list use");
INIT_LIST_HEAD(&strud_list);
strude=kmalloc( sizeof(struct strudent)*STRUD_NUM,GFP_KERNEL);
if(strude==NULL){
printk(KERN_ERR"strude kmalloc is fail");
return -ENOMEM;
}
printk(KERN_INFO"strude kmalloc is success");
memset(strude,0,sizeof(struct strudent)*STRUD_NUM);
for(i=0;i<STRUD_NUM;i++)
{
sprintf(strude[i].name,"strudent%d",i+1);
strude[i].str_id=2013021001+i;
strude[i].mark=70+i*2;
list_add(&strude[i].list,&strud_list);
}
list_for_each(pos,&strud_list){
strude_tmp=list_entry(pos,struct strudent,list);
printk(KERN_INFO"strudent name %s\t strudent ID %d\t strudent maske %d\n" );
}
return 0;
}
static int __exit strud_exit(void)
{
int i;
printk(KERN_INFO"entry module exit...");
for(i=0;i<STRUD_NUM;i++)
{
list_del(&(strude[i].list));
}
kfree(strude);
return 0;
}
module_init(strud_init);
module_exit(strud_exit);
MODULE_AUTHOR("Songmao");
MODULE_DESCRIPTION("List tast");
***********************************************************
printk的打印级别
#define KERN_EMERG "<0>" /* system is unusable */
#define KERN_ALERT "<1>" /* action must be taken immediately */
#define KERN_CRIT "<2>" /* critical conditions */
#define KERN_ERR "<3>" /* error conditions */
#define KERN_WARNING "<4>" /* warning conditions */
#define KERN_NOTICE "<5>" /* normal but significant condition */
#define KERN_INFO "<6>" /* informational */
#define KERN_DEBUG "<7>" /* debug-level messages */
5、printk函数的使用
printk(打印级别 “要打印的信息”)
打印级别 既上面定义的几个宏
Sprintf()格式化输出
INIT_LIST_HEAD
list_add（struct list_head *new,struct list_head *head）添加链表数据
list_for_each(pos,head){...} 遍历链表其实看内核就是一个for循环的宏
list_entry(ptr,type,member) 取链表中的偏差值
list_del(struct list_head *old)删除list节点
kmalloc申请后需要memset清零下，因为kmalloc申请时并没有把它清零，如果以前申请这块地址的释放时没清零那这块地址就还有数据，不清零可能导致你数据错误。可以使用kzalloc，kzalloc实现了kmalloc以及memset的功能，一个函数起到了两个函数的作用
/* 以下为摘录************************************************************************
kmalloc() 与 kfree() 和get_free_page的区别
1,用于申请较小的、连续的物理内存：使用的是内存分配器slab一小片。申请的内存位于物理内存的映射区域。其正真的物理地址只相差一个固定的偏移。
可以用这两个宏来简单转换 __pa(address) ｛virt_to_phys()｝ 和 __va(address)｛phys_to_virt()｝
get_free_page()申请的内存是一整页，一页的大小一般是128K。它们的区别只有这一点不同，其它的都相同。
本质上讲，kmalloc()和get_free_page()最终调用实现都是相同的，只不过在调用最终函数时所传的flag不同而以。
2. void *kmalloc(size_t size, int flags) 分配的内存物理地址上连续,虚拟地址上也是连续
3. gfp_mask标志：
情形 相应标志
进程上下文，可以睡眠 GFP_KERNEL
进程上下文，不可以睡眠 GFP_ATOMIC
中断处理程序 GFP_ATOMIC
软中断 GFP_ATOMIC
Tasklet GFP_ATOMIC
用于DMA的内存，可以睡眠 GFP_DMA | GFP_KERNEL
用于DMA的内存，不可以睡眠 GFP_DMA | GFP_ATOMIC
4. void kfree(const void *ptr)
释放由kmalloc()分配出来的内存块
******************************************/
本文出自 “毛散人” 博客，请务必保留此出处http://songmao.blog.51cto.com/11700139/1876867
linux驱动开发要知道的那些知识（二）------list内核链表