Linux内核设备驱动之内核中链表的使用笔记整理

?

1 2 3

/********************   * 内核中链表的应用   ********************/

(1)介绍

在Linux内核中使用了大量的链表结构来组织数据，包括设备列表以及各种功能模块中的数据组织。这些链表大多采用在include/linux/list.h实现的一个相当精彩的链表数据结构。

链表数据结构的定义很简单:

?

1 2 3

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

list_head结构包含两个指向list_head结构的指针prev和next，内核的数据结构通常组织成双循环链表。

和以前介绍的双链表结构模型不同，这里的list_head没有数据域。在Linux内核链表中，不是在链表结构中包含数据，而是在数据结构中包含链表节点。如：

?

1 2 3 4 5

struct my_struct{   struct list_head list;   unsigned long dog;   void *cat; };

linux中的链表没有固定的表头，从任何元素开始访问都可以。遍历链表仅仅需要从某个节点开始，沿指针访问下一个节点，直到又重新回到最初这个节点就可以了。每个独立的节点都可以被称作是链表头。

(2)链表的初始化

a.静态

如果在编译时静态创建链表，并且直接引用它，如下：

?

1 2 3 4 5 6 7 8

struct my_struct mine={   .lost = LIST_HEAD_INIT(mine.list);   .dog = 0,   .cat = NULL }; //或 static LIST_HEAD(fox); /*等于struct list_head fox = LIST_HEAD_INIT(fox); */

b.动态

?

1 2 3 4 5

struct my_struct *p; p = kmalloc(GFP_KERNEL, sizeof (my_struct)); p->dog = 0; p->cat = NULL; INIT_LIST_HEAD(&p->list);

(3)操作链表

内核提供了一组函数来操作链表。

注意！这些函数都使用一个或多个list_head结构体指针作参数。定义在<linux/list.h>

a.增加节点

?

1 2 3

list_add( struct list_head * new ,       struct list_head *head); //向指定链表的head节点后面插入new节点

b.把节点增加到链表尾

?

1 2 3

list_add_tail( struct list_head * new ,       struct list_head *head); //向指定链表的head节点前面插入new节点

c.从链表删除一个节点

?

1 2	list_del( struct list_head *entry); //将entry从链表中移走

d.把节点从一个链表移到另一个链表

?

1 2	list_move( struct list_head *list,       struct list_head *head);

从一个链表中摘除list项，然后将其插入head的后面

?

1	e.list_empty( struct list_head *head);

链表为空返回非0值，否则返回0

f.合并链表

?

1 2 3

list_splice( struct list_head *list,        struct list_head *head); //注意！新的链表不包括list节点

(4)遍历链表

链表本身不重要，访问到那个包含链表的结构体才重要

a.从链表指针获得包含该链表的结构体的指针

?

1 2 3

list_entry( struct list_head *ptr,        type_of_struct,        field_name);

• ptr: list_head指针
• type_of_struct: 包含ptr的结构体类型
• field_name: 结构体中链表字段的名字

如：

?

1	my_struct *p = (list_head *ptr, my_struct, list);

b.遍历链表

?

1 2 3 4

list_for_each( struct list_head *cursor,         struct list_head *list); //常常和list_entry配套使用 //注意！用list_for_each遍历时，不包括头节点

c.遍历的同时获得大结构体指针

?

1 2 3

list_for_each_entry(type *cursor,        struct list_head *list,        member);

d.遍历链表的同时释放每个被遍历到的节点

?

1 2 3 4

list_for_each_entry_safe(type *cursor,       type *tmp;       struct list_head *list,       member);

总结

以上就是这篇文章的全部内容了，希望本文的内容对大家的学习或者工作具有一定的参考学习价值，谢谢大家对服务器之家的支持。如果你想了解更多相关内容请查看下面相关链接

原文链接：https://blog.csdn.net/morixinguan/article/details/79706265