]>
Commit | Line | Data |
---|---|---|
f49f23ab HY |
1 | #ifndef LLIST_H |
2 | #define LLIST_H | |
3 | /* | |
4 | * Lock-less NULL terminated single linked list | |
5 | * | |
6 | * If there are multiple producers and multiple consumers, llist_add | |
7 | * can be used in producers and llist_del_all can be used in | |
8 | * consumers. They can work simultaneously without lock. But | |
9 | * llist_del_first can not be used here. Because llist_del_first | |
10 | * depends on list->first->next does not changed if list->first is not | |
11 | * changed during its operation, but llist_del_first, llist_add, | |
12 | * llist_add (or llist_del_all, llist_add, llist_add) sequence in | |
13 | * another consumer may violate that. | |
14 | * | |
15 | * If there are multiple producers and one consumer, llist_add can be | |
16 | * used in producers and llist_del_all or llist_del_first can be used | |
17 | * in the consumer. | |
18 | * | |
19 | * This can be summarized as follow: | |
20 | * | |
21 | * | add | del_first | del_all | |
22 | * add | - | - | - | |
23 | * del_first | | L | L | |
24 | * del_all | | | - | |
25 | * | |
26 | * Where "-" stands for no lock is needed, while "L" stands for lock | |
27 | * is needed. | |
28 | * | |
29 | * The list entries deleted via llist_del_all can be traversed with | |
30 | * traversing function such as llist_for_each etc. But the list | |
31 | * entries can not be traversed safely before deleted from the list. | |
32 | * The order of deleted entries is from the newest to the oldest added | |
33 | * one. If you want to traverse from the oldest to the newest, you | |
34 | * must reverse the order by yourself before traversing. | |
35 | * | |
36 | * The basic atomic operation of this list is cmpxchg on long. On | |
37 | * architectures that don't have NMI-safe cmpxchg implementation, the | |
38 | * list can NOT be used in NMI handler. So code uses the list in NMI | |
39 | * handler should depend on CONFIG_ARCH_HAVE_NMI_SAFE_CMPXCHG. | |
40 | */ | |
41 | ||
42 | struct llist_head { | |
43 | struct llist_node *first; | |
44 | }; | |
45 | ||
46 | struct llist_node { | |
47 | struct llist_node *next; | |
48 | }; | |
49 | ||
50 | #define LLIST_HEAD_INIT(name) { NULL } | |
51 | #define LLIST_HEAD(name) struct llist_head name = LLIST_HEAD_INIT(name) | |
52 | ||
53 | /** | |
54 | * init_llist_head - initialize lock-less list head | |
55 | * @head: the head for your lock-less list | |
56 | */ | |
57 | static inline void init_llist_head(struct llist_head *list) | |
58 | { | |
59 | list->first = NULL; | |
60 | } | |
61 | ||
62 | /** | |
63 | * llist_entry - get the struct of this entry | |
64 | * @ptr: the &struct llist_node pointer. | |
65 | * @type: the type of the struct this is embedded in. | |
66 | * @member: the name of the llist_node within the struct. | |
67 | */ | |
68 | #define llist_entry(ptr, type, member) \ | |
69 | container_of(ptr, type, member) | |
70 | ||
71 | /** | |
72 | * llist_for_each - iterate over some deleted entries of a lock-less list | |
73 | * @pos: the &struct llist_node to use as a loop cursor | |
74 | * @node: the first entry of deleted list entries | |
75 | * | |
76 | * In general, some entries of the lock-less list can be traversed | |
77 | * safely only after being deleted from list, so start with an entry | |
78 | * instead of list head. | |
79 | * | |
80 | * If being used on entries deleted from lock-less list directly, the | |
81 | * traverse order is from the newest to the oldest added entry. If | |
82 | * you want to traverse from the oldest to the newest, you must | |
83 | * reverse the order by yourself before traversing. | |
84 | */ | |
85 | #define llist_for_each(pos, node) \ | |
86 | for ((pos) = (node); pos; (pos) = (pos)->next) | |
87 | ||
88 | /** | |
89 | * llist_for_each_entry - iterate over some deleted entries of lock-less list of given type | |
90 | * @pos: the type * to use as a loop cursor. | |
91 | * @node: the fist entry of deleted list entries. | |
92 | * @member: the name of the llist_node with the struct. | |
93 | * | |
94 | * In general, some entries of the lock-less list can be traversed | |
95 | * safely only after being removed from list, so start with an entry | |
96 | * instead of list head. | |
97 | * | |
98 | * If being used on entries deleted from lock-less list directly, the | |
99 | * traverse order is from the newest to the oldest added entry. If | |
100 | * you want to traverse from the oldest to the newest, you must | |
101 | * reverse the order by yourself before traversing. | |
102 | */ | |
103 | #define llist_for_each_entry(pos, node, member) \ | |
104 | for ((pos) = llist_entry((node), typeof(*(pos)), member); \ | |
105 | &(pos)->member != NULL; \ | |
106 | (pos) = llist_entry((pos)->member.next, typeof(*(pos)), member)) | |
107 | ||
108 | /** | |
109 | * llist_empty - tests whether a lock-less list is empty | |
110 | * @head: the list to test | |
111 | * | |
112 | * Not guaranteed to be accurate or up to date. Just a quick way to | |
113 | * test whether the list is empty without deleting something from the | |
114 | * list. | |
115 | */ | |
116 | static inline int llist_empty(const struct llist_head *head) | |
117 | { | |
118 | return ACCESS_ONCE(head->first) == NULL; | |
119 | } | |
120 | ||
121 | void llist_add(struct llist_node *new, struct llist_head *head); | |
122 | void llist_add_batch(struct llist_node *new_first, struct llist_node *new_last, | |
123 | struct llist_head *head); | |
124 | struct llist_node *llist_del_first(struct llist_head *head); | |
125 | struct llist_node *llist_del_all(struct llist_head *head); | |
126 | #endif /* LLIST_H */ |