1/*	$NetBSD: llist.h,v 1.7 2022/04/09 23:43:55 riastradh Exp $	*/
2
3/*-
4 * Copyright (c) 2018 The NetBSD Foundation, Inc.
5 * All rights reserved.
6 *
7 * This code is derived from software contributed to The NetBSD Foundation
8 * by Taylor R. Campbell.
9 *
10 * Redistribution and use in source and binary forms, with or without
11 * modification, are permitted provided that the following conditions
12 * are met:
13 * 1. Redistributions of source code must retain the above copyright
14 *    notice, this list of conditions and the following disclaimer.
15 * 2. Redistributions in binary form must reproduce the above copyright
16 *    notice, this list of conditions and the following disclaimer in the
17 *    documentation and/or other materials provided with the distribution.
18 *
19 * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
20 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
21 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
22 * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS
23 * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
24 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
25 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
26 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
27 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
28 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
29 * POSSIBILITY OF SUCH DAMAGE.
30 */
31
32#ifndef	_LINUX_LLIST_H_
33#define	_LINUX_LLIST_H_
34
35#include <sys/atomic.h>
36#include <sys/null.h>
37
38struct llist_head {
39	struct llist_node	*first;
40};
41
42struct llist_node {
43	struct llist_node	*next;
44};
45
46static inline void
47init_llist_head(struct llist_head *head)
48{
49
50	head->first = NULL;
51}
52
53#define	llist_entry(NODE, TYPE, FIELD)	container_of(NODE, TYPE, FIELD)
54
55static inline bool
56llist_empty(struct llist_head *head)
57{
58	bool empty;
59
60	empty = (atomic_load_acquire(&head->first) == NULL);
61
62	return empty;
63}
64
65static inline bool
66llist_add(struct llist_node *node, struct llist_head *head)
67{
68	struct llist_node *first;
69
70	do {
71		first = head->first;
72		node->next = first;
73		membar_release();
74	} while (atomic_cas_ptr(&head->first, first, node) != first);
75
76	return first == NULL;
77}
78
79static inline bool
80llist_add_batch(struct llist_node *first, struct llist_node *last,
81    struct llist_head *head)
82{
83	struct llist_node *next;
84
85	do {
86		next = atomic_load_consume(&head->first);
87		last->next = next;
88	} while (atomic_cas_ptr(&head->first, next, first) != next);
89
90	return next == NULL;
91}
92
93static inline struct llist_node *
94llist_del_all(struct llist_head *head)
95{
96	struct llist_node *first;
97
98	first = atomic_swap_ptr(&head->first, NULL);
99	membar_datadep_consumer();
100
101	return first;
102}
103
104static inline struct llist_node *
105llist_del_first(struct llist_head *head)
106{
107	struct llist_node *first;
108
109	do {
110		first = atomic_load_consume(&head->first);
111		if (first == NULL)
112			return NULL;
113	} while (atomic_cas_ptr(&head->first, first, first->next)
114	    != first);
115
116	return first;
117}
118
119#define	_llist_next(ENTRY, FIELD)					      \
120({									      \
121	__typeof__((ENTRY)->FIELD.next) _NODE =				      \
122	    atomic_load_consume(&(ENTRY)->FIELD.next);			      \
123	(_NODE == NULL ? NULL :						      \
124	    llist_entry(_NODE, __typeof__(*(ENTRY)), FIELD));		      \
125})
126
127#define	llist_for_each_safe(NODE, TMP, HEAD)				      \
128	for ((NODE) = (HEAD);						      \
129		(NODE) && ((TMP) = (NODE)->next, 1);			      \
130		(NODE) = (TMP))
131
132#define	llist_for_each_entry(ENTRY, NODE, FIELD)			      \
133	for ((ENTRY) = ((NODE) == NULL ? NULL :				      \
134		    (membar_datadep_consumer(),				      \
135			llist_entry(NODE, typeof(*(ENTRY)), FIELD)));	      \
136		(ENTRY) != NULL;					      \
137		(ENTRY) = _llist_next(ENTRY, FIELD))
138
139#define	llist_for_each_entry_safe(ENTRY, TMP, NODE, FIELD)		      \
140	for ((ENTRY) = ((NODE) == NULL ? NULL :				      \
141		    (membar_datadep_consumer(),				      \
142			llist_entry(NODE, typeof(*(ENTRY)), FIELD)));	      \
143		((ENTRY) == NULL ? 0 :					      \
144		    ((TMP) = _llist_next(ENTRY, FIELD), 1));		      \
145		(ENTRY) = (TMP))
146
147#endif	/* _LINUX_LLIST_H_ */
148