概述

这里假定读者已经具备关于链表（Linked List）的基本背景知识，若不太确定可以自行通过查看这部分资料进行复习。

/include/linux/types.hsource_code
1
2
3
struct list_head {
    struct list_head *next, *prev;
};
/tools/include/linux/list.hlist_add
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/*
 * Insert a new entry between two known consecutive entries.
 *
 * This is only for internal list manipulation where we know
 * the prev/next entries already!
 */
#ifndef CONFIG_DEBUG_LIST
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;
}
#else
extern void __list_add(struct list_head *new,
			      struct list_head *prev,
			      struct list_head *next);
#endif

/**
 * 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_sort

linux/lib/list_sort.clist_sort.c
1

container_of

附录

你所不知道的 C 語言: linked list 和非連續記憶體操作
The Linux Kernel API
Merge sort
linked-list-goog-taste