本文从最基本的内核链表出发,引出初始化INIT_LIST_HEAD函数,然后介绍list_add,通过改变链表位置的问题引出list_for_each函数,然后为了获取容器结构地址,引出offsetof和container_of宏,并对内核链表设计原因作出了解释,一步步引导到list_for_each_entry,然后介绍list_del函数,通过在遍历时list_del链表的不安全行为,引出list_for_each_entry_safe函数,通过本文,我希望读者可以得到如下三个技能点:
1.能够熟练使用内核链表的相关宏和函数,并应用在项目中;
2.明白内核链表设计者们的意图,为什么要那样去设计链表的操作和提供那样的函数接口;
3.能够将内核链表移植到非GNU环境。
大多数人在学习数据结构的时候,链表都是第一个接触的内容,笔者也不列外,虽然自己实现过几种链表,但是在实际工作中,还是Linux内核的链表最为常用(同时笔者也建议大家使用内核链表,因为会了这个,其他的都会了),故总结一篇Linux内核链表的文章。
阅读本文之前,我假设你已经具备基本的链表编写经验。
核心链表的结构是双向循环链表,只有指针域,数据字段取决于使用链表的人的特定需求。内核列表设计理念:
[En]
The structure of the kernel linked list is a two-way circular linked list, only the pointer domain, and the data field depends on the specific needs of the person who uses the linked list. Philosophy of kernel list design:
既然链表不能包含万事万物,那么就让万事万物来包含链表。
假设以如下方式组织我们的数据结构: