1 /* Public domain. */
2
3 #ifndef _LINUXKPI_LINUX_LLIST_H
4 #define _LINUXKPI_LINUX_LLIST_H
5
6 #include <sys/types.h>
7 #include <machine/atomic.h>
8
9 struct llist_node {
10 struct llist_node *next;
11 };
12
13 struct llist_head {
14 struct llist_node *first;
15 };
16
17 #define LLIST_HEAD_INIT(name) { NULL }
18 #define LLIST_HEAD(name) struct llist_head name = LLIST_HEAD_INIT(name)
19
20 #define llist_entry(ptr, type, member) \
21 ((ptr) ? container_of(ptr, type, member) : NULL)
22
23 static inline struct llist_node *
llist_del_all(struct llist_head * head)24 llist_del_all(struct llist_head *head)
25 {
26 return ((void *)atomic_readandclear_ptr((uintptr_t *)&head->first));
27 }
28
29 static inline struct llist_node *
llist_del_first(struct llist_head * head)30 llist_del_first(struct llist_head *head)
31 {
32 struct llist_node *first, *next;
33
34 do {
35 first = head->first;
36 if (first == NULL)
37 return NULL;
38 next = first->next;
39 } while (atomic_cmpset_ptr((uintptr_t *)&head->first,
40 (uintptr_t)first, (uintptr_t)next) == 0);
41
42 return (first);
43 }
44
45 static inline bool
llist_add(struct llist_node * new,struct llist_head * head)46 llist_add(struct llist_node *new, struct llist_head *head)
47 {
48 struct llist_node *first;
49
50 do {
51 new->next = first = head->first;
52 } while (atomic_cmpset_ptr((uintptr_t *)&head->first,
53 (uintptr_t)first, (uintptr_t)new) == 0);
54
55 return (first == NULL);
56 }
57
58 static inline bool
llist_add_batch(struct llist_node * new_first,struct llist_node * new_last,struct llist_head * head)59 llist_add_batch(struct llist_node *new_first, struct llist_node *new_last,
60 struct llist_head *head)
61 {
62 struct llist_node *first;
63
64 do {
65 new_last->next = first = head->first;
66 } while (atomic_cmpset_ptr((uintptr_t *)&head->first,
67 (uintptr_t)first, (uintptr_t)new_first) == 0);
68
69 return (first == NULL);
70 }
71
72 static inline void
init_llist_head(struct llist_head * head)73 init_llist_head(struct llist_head *head)
74 {
75 head->first = NULL;
76 }
77
78 static inline bool
llist_empty(struct llist_head * head)79 llist_empty(struct llist_head *head)
80 {
81 return (head->first == NULL);
82 }
83
84 #define llist_for_each_safe(pos, n, node) \
85 for ((pos) = (node); \
86 (pos) != NULL && \
87 ((n) = (pos)->next, pos); \
88 (pos) = (n))
89
90 #define llist_for_each_entry_safe(pos, n, node, member) \
91 for (pos = llist_entry((node), __typeof(*pos), member); \
92 pos != NULL && \
93 (n = llist_entry(pos->member.next, __typeof(*pos), member), pos); \
94 pos = n)
95
96 #define llist_for_each_entry(pos, node, member) \
97 for ((pos) = llist_entry((node), __typeof(*(pos)), member); \
98 (pos) != NULL; \
99 (pos) = llist_entry((pos)->member.next, __typeof(*(pos)), member))
100
101 #endif
102