Linux内核链表设计

1
2
3
struct list_head {
	struct list_head *next, *prev;
};

双向循环链表。没有设计数据域，通用性和灵活性更好。 实际使用时，构成如下：

1
2
3
4
struct user_list {
	void* data;
	struct list_head list;
}

初始化设计：

1
2
3
4
5
#define LIST_HEAD_INIT(name) { &(name), &(name) }

// 初始化prev和next字段，让它们指向list_name变量本身
#define LIST_HEAD(name) \
	struct list_head name = LIST_HEAD_INIT(name)

添加元素：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// simple, clear, neat
static inline void __list_add(struct list_head *new,
			      struct list_head *prev,
			      struct list_head *next)
{
	next->prev = new;
	new->next = next;
	new->prev = prev;
	prev->next = new;
}


static inline void list_add(struct list_head *new, struct list_head *head)
{
	__list_add(new, head, head->next);
}


static inline void list_add_tail(struct list_head *new, struct list_head *head)
{
	__list_add(new, head->prev, head);
}

删除元素：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
static inline void __list_del(struct list_head * prev, struct list_head * next)
{
	next->prev = prev;
	prev->next = next;
}


/*
 * These are non-NULL pointers that will result in page faults
 * under normal circumstances, used to verify that nobody uses
 * non-initialized list entries.
 */
#define LIST_POISON1  ((void *) 0x00100100)
#define LIST_POISON2  ((void *) 0x00200200)


static inline void list_del(struct list_head *entry)
{
	__list_del(entry->prev, entry->next);
	entry->next = LIST_POISON1;
	entry->prev = LIST_POISON2;
}

通过 list_head 成员，找到整个结构体的地址：

1
2
3
4
5
6
7
8
#define list_entry(ptr, type, member) \
(                                    \
	(type*)                          \
	(                                \
		(char*)(ptr) -               \
		(unsigned long)( &((type*)0)->member ) \
	)                                \
)

type是包含 list_head 类型成员的自定义结构体，ptr 是 list_head ，指向 member 成员。 (unsigned long)( &((type*)0)->member )：从 0 地址定义的一个结构，得到 member 成员的偏移量。ptr 进行偏移之后，得到自定义结构体的地址。

遍历节点：

1
2
3
4
5
6
#define __list_for_each(pos, head) \
	for (pos = (head)->next; pos != (head); pos = pos->next)

#define list_for_each_safe(pos, n, head) \
	for (pos = (head)->next, n = pos->next; pos != (head); \
		pos = n, n = pos->next)

safe版本保存了临时的 next 节点，即使 pos 被删除了，也能通过 n 找到 next 节点。

更常用的类似 list_entry 是 container_of。

Notes Linux Kernel
Data Structure Linux Kernel

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！