Linux内核设备驱动之内核中链表的使用笔记整理
/******************** *内核中链表的应用 ********************/
(1)介绍
在Linux内核中使用了大量的链表结构来组织数据，包括设备列表以及各种功能模块中的数据组织。这些链表大多采用在include/linux/list.h实现的一个相当精彩的链表数据结构。
链表数据结构的定义很简单:
structlist_head{
structlist_head*next,*prev;
};
list_head结构包含两个指向list_head结构的指针prev和next，内核的数据结构通常组织成双循环链表。
和以前介绍的双链表结构模型不同，这里的list_head没有数据域。在Linux内核链表中，不是在链表结构中包含数据，而是在数据结构中包含链表节点。如：
structmy_struct{
structlist_headlist;
unsignedlongdog;
void*cat;
};
linux中的链表没有固定的表头，从任何元素开始访问都可以。遍历链表仅仅需要从某个节点开始，沿指针访问下一个节点，直到又重新回到最初这个节点就可以了。每个独立的节点都可以被称作是链表头。
(2)链表的初始化
a.静态
如果在编译时静态创建链表，并且直接引用它，如下：
structmy_structmine={
.lost=LIST_HEAD_INIT(mine.list);
.dog=0,
.cat=NULL
};
//或
staticLIST_HEAD(fox);
/*等于structlist_headfox=LIST_HEAD_INIT(fox);*/
b.动态
structmy_struct*p; p=kmalloc(GFP_KERNEL,sizeof(my_struct)); p->dog=0; p->cat=NULL; INIT_LIST_HEAD(&p->list);
(3)操作链表
内核提供了一组函数来操作链表。
注意！这些函数都使用一个或多个list_head结构体指针作参数。定义在
a.增加节点
list_add(structlist_head*new, structlist_head*head); //向指定链表的head节点后面插入new节点
b.把节点增加到链表尾
list_add_tail(structlist_head*new, structlist_head*head); //向指定链表的head节点前面插入new节点
c.从链表删除一个节点
list_del(structlist_head*entry); //将entry从链表中移走
d.把节点从一个链表移到另一个链表
list_move(structlist_head*list, structlist_head*head);
从一个链表中摘除list项，然后将其插入head的后面
e.list_empty(structlist_head*head);
链表为空返回非0值，否则返回0
f.合并链表
list_splice(structlist_head*list, structlist_head*head); //注意！新的链表不包括list节点
(4)遍历链表
链表本身不重要，访问到那个包含链表的结构体才重要
a.从链表指针获得包含该链表的结构体的指针
list_entry(structlist_head*ptr, type_of_struct, field_name);
- ptr:list_head指针
- type_of_struct:包含ptr的结构体类型
- field_name:结构体中链表字段的名字
如：
my_struct*p=(list_head*ptr,my_struct,list);
b.遍历链表
list_for_each(structlist_head*cursor, structlist_head*list); //常常和list_entry配套使用 //注意！用list_for_each遍历时，不包括头节点
c.遍历的同时获得大结构体指针
list_for_each_entry(type*cursor, structlist_head*list, member);
d.遍历链表的同时释放每个被遍历到的节点
list_for_each_entry_safe(type*cursor, type*tmp; structlist_head*list, member);
总结
以上就是这篇文章的全部内容了，希望本文的内容对大家的学习或者工作具有一定的参考学习价值，谢谢大家对毛票票的支持。如果你想了解更多相关内容请查看下面相关链接