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
9struct llist_node {
10	struct llist_node *next;
11};
12
13struct 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
23static inline struct llist_node *
24llist_del_all(struct llist_head *head)
25{
26	return ((void *)atomic_readandclear_ptr((uintptr_t *)&head->first));
27}
28
29static inline struct llist_node *
30llist_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
45static inline bool
46llist_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
58static inline bool
59llist_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
72static inline void
73init_llist_head(struct llist_head *head)
74{
75	head->first = NULL;
76}
77
78static inline bool
79llist_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