玩转内核链表list_head，教你管理不同类型节点的实现，建议收藏
扫描二维码
随时随地手机看文章
在Linux内核中，提供了一个用来创建双向循环链表的结构 list_head。虽然linux内核是用C语言写的，但是list_head的引入，使得内核数据结构也可以拥有面向对象的特性，通过使用操作list_head 的通用接口很容易实现代码的重用，有点类似于C++的继承机制（希望有机会写篇文章研究一下C语言的面向对象机制）。
首先找到list_head结构体定义，kernel/inclue/linux/types.h 如下：
struct list_head { struct list_head *next, *prev;};
需要注意的一点是，头结点head是不使用的，这点需要注意。
使用list_head组织的链表的结构如下图所示：
然后就开始围绕这个结构开始构建链表，然后插入、删除节点 ，遍历整个链表等等，其实内核已经提供好了现成的接口，接下来就让我们进入 kernel/include/linux/list.h中：
一. 创建链表
内核提供了下面的这些接口来初始化链表：
-
-
-
-
-
-
-
-
-
-
struct list_head name = LIST_HEAD_INIT(name) static inline void INIT_LIST_HEAD(struct list_head *list){ WRITE_ONCE(list->next, list); list->prev = list;}
如： 可以通过 LIST_HEAD(mylist) 进行初始化一个链表，mylist的prev 和 next 指针都是指向自己。
-
structlist_head mylist = {&mylist, &mylist} ;
但是如果只是利用mylist这样的结构体实现链表就没有什么实际意义了，因为正常的链表都是为了遍历结构体中的其它有意义的字段而创建的，而我们mylist中只有 prev和next指针，却没有实际有意义的字段数据，所以毫无意义。
综上，我们可以创建一个宿主结构，然后在此结构中再嵌套mylist字段，宿主结构又有其它的字段（进程描述符 task_struct，页面管理的page结构，等就是采用这种方法创建链表的）。为简便理解，定义如下：
-
-
-
-
-
struct mylist{ int type; char name[MAX_NAME_LEN]; struct list_head list;}
创建链表，并初始化
-
-
structlist_head myhead; INIT_LIST_HEAD(&myhead);
这样我们的链表就初始化完毕，链表头的myhead就prev 和 next指针分别指向myhead自己了，如下图：
二. 添加节点
内核已经提供了添加节点的接口了
1. list_add
如下所示。根据注释可知，是在链表头head后方插入一个新节点new。
-
-
-
-
-
-
-
-
-
-
-
-
/** * list_add - add a new entry * @new: new entry to be added * @head: list head to add it after * * Insert a new entry after the specified head. * This is good for implementing stacks. */static inline void list_add(struct list_head *new, struct list_head *head){ __list_add(new, head, head->next);}
list_add再调用__list_add接口
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
/* * Insert a new entry between two known consecutive entries. * * This is only for internal list manipulation where we know * the prev/next entries already! */static inline void __list_add(struct list_head *new, struct list_head *prev, struct list_head *next){ if (!__list_add_valid(new, prev, next)) return; next->prev = new;
下载文档
