Linux内核链表分析（带头双向循环链表）
上节我们对Linux内核链表的设计原理进行分析，理解了内核链表的设计的优点，并解决内核链表访问问题。本节我们主要将Linux内核中链表的实现库进行分析解释。
// 内核链表数据结构
struct list_head{
struct list_head *next, *prev;
};
// 初始化内核链表头节点： 头结点的next，prev指针都指向自己的地址
#define LIST_HEAD_INIT(name) { &(name), &(name) }
#define LIST_HEAD(name) \
struct list_head name = LIST_HEAD_INIT(name)
static inline void INIT_LIST_HEAD(struct list_head *list)
{
list->next = list;
list->prev = list;
}
图 1 初始化链表头节点
// 将new节点插入到prev之后，next之前
static inline void __list_add(struct list_head *new, struct list_head *prev, struct list_head *next)
{
next->prev = new; // 如图2：(1)
new->next = next; // 如图2：(2)
new->prev = prev; // 如图2：(3)
prev->next = new; // 如图2：(4)
}
// 将new节点插入到头结点之后
static inline void list_add(struct list_head *new, struct list_head *head)
{
__list_add(new, head, head->next);
}
// 将new节点插入到头结点之前
static inline void list_add_tail(struct list_head *new, struct list_head *head)
{
__list_add(new, head->prev, head);
}
图 2 新节点插入
static inline void __list_del(struct list_head * prev, struct list_head * next)
{
next->prev = prev;
prev->next = next;
}
static inline void list_del(struct list_head *entry)
{
__list_del(entry->prev, entry->next);
entry->next = LIST_POISON1;
entry->prev = LIST_POISON2;
}
图 3 链表节点删除
#define list_entry(ptr, type, member) \
container_of(ptr, type, member)
// 从头到尾遍历整个链表
#define list_for_each(pos, head) \
for (pos = (head)->next; pos != (head); pos = pos->next)
// 尾从到头遍历整个链表
#define list_for_each_prev(pos, head) \
for (pos = (head)->prev; pos != (head); pos = pos->prev)
// 安全的从头到尾遍历整个链表：在遍历的时候可以安全的删除节点
#define list_for_each_safe(pos, n, head) \
for (pos = (head)->next, n = pos->next; pos != (head); \
pos = n, n = pos->next)
// 安全的从尾到头遍历整个链表：在遍历的时候可以安全的删除节点
#define list_for_each_prev_safe(pos, n, head) \
for (pos = (head)->prev, n = pos->prev; \
pos != (head); \
pos = n, n = pos->prev)
// 从头到尾遍历整个链表，并用type *pos指针获取节点的首地址
#define list_for_each_entry(pos, head, member) \
for (pos = list_entry((head)->next, typeof(*pos), member); \
&pos->member != (head); \
pos = list_entry(pos->member.next, typeof(*pos), member))
// 从尾到头遍历整个链表，并用type *pos指针获取节点的首地址
#define list_for_each_entry_reverse(pos, head, member) \
for (pos = list_entry((head)->prev, typeof(*pos), member); \
&pos->member != (head); \
pos = list_entry(pos->member.prev, typeof(*pos), member))
测试例程（测试环境centos/ubuntu）：
#include "list.h"
#include <stdio.h>
struct stu{
int val;
struct list_head lists;
};
int main()
{
LIST_HEAD( head ); // 初始化头结点
struct stu s0 = { 10, {NULL, NULL}};
struct stu s1 = { 20, {NULL, NULL}};
struct stu s2 = { 30, {NULL, NULL}};
list_add( &s0.lists, &head ); // 头插法
list_add( &s1.lists, &head );
list_add_tail( &s2.lists, &head ); // 尾插法
struct list_head *ptr = NULL;
list_for_each(ptr, &head){ // 循环
struct stu *s = list_entry( ptr, struct stu, lists ); // 获取节点地址
printf("s->val = %d\n", s->val );
}
struct list_head *n = NULL;
list_for_each_safe( ptr, n, &head ){
struct stu *s = list_entry( ptr, struct stu, lists );
if( s->val == 20 ){
list_del( ptr );
}
}
struct stu *str = NULL;
list_for_each_entry( str, &head, lists ){
printf("s->val = %d\n", str->val );
}
return 0;
}
