Phase 1 of deprecating liburcu-signal
[urcu.git] / include / urcu / lfstack.h
CommitLineData
d3d3857f
MJ
1// SPDX-FileCopyrightText: 2010-2012 Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
2//
3// SPDX-License-Identifier: LGPL-2.1-or-later
4
d3bfcb24
MD
5#ifndef _URCU_LFSTACK_H
6#define _URCU_LFSTACK_H
7
8/*
d3bfcb24 9 * Userspace RCU library - Lock-Free Stack
d3bfcb24
MD
10 */
11
12#ifdef __cplusplus
13extern "C" {
14#endif
15
7294103b
MD
16#include <stdbool.h>
17#include <pthread.h>
18
19/*
20 * Lock-free stack.
21 *
22 * Stack implementing push, pop, pop_all operations, as well as iterator
23 * on the stack head returned by pop_all.
24 *
25 * Synchronization table:
26 *
27 * External synchronization techniques described in the API below is
28 * required between pairs marked with "X". No external synchronization
29 * required between pairs marked with "-".
30 *
31 * cds_lfs_push __cds_lfs_pop __cds_lfs_pop_all
32 * cds_lfs_push - - -
33 * __cds_lfs_pop - X X
34 * __cds_lfs_pop_all - X -
35 *
36 * cds_lfs_pop_blocking and cds_lfs_pop_all_blocking use an internal
37 * mutex to provide synchronization.
38 */
39
40/*
41 * struct cds_lfs_node is returned by cds_lfs_pop, and also used as
42 * iterator on stack. It is not safe to dereference the node next
43 * pointer when returned by cds_lfs_pop.
44 */
d3bfcb24
MD
45struct cds_lfs_node {
46 struct cds_lfs_node *next;
47};
48
7294103b
MD
49/*
50 * struct cds_lfs_head is returned by __cds_lfs_pop_all, and can be used
51 * to begin iteration on the stack. "node" needs to be the first field
52 * of cds_lfs_head, so the end-of-stack pointer value can be used for
53 * both types.
54 */
55struct cds_lfs_head {
56 struct cds_lfs_node node;
57};
58
48a8832b
MD
59struct __cds_lfs_stack {
60 struct cds_lfs_head *head;
61};
62
d3bfcb24 63struct cds_lfs_stack {
7294103b
MD
64 struct cds_lfs_head *head;
65 pthread_mutex_t lock;
d3bfcb24
MD
66};
67
48a8832b 68/*
e9349020
MD
69 * In C, the transparent union allows calling functions that work on
70 * both struct cds_lfs_stack and struct __cds_lfs_stack on any of those
71 * two types.
28757437 72 *
e9349020
MD
73 * In C++, implement static inline wrappers using function overloading
74 * to obtain an API similar to C.
087bce43
MD
75 *
76 * Avoid complaints from clang++ not knowing the transparent union
77 * attribute.
48a8832b 78 */
087bce43
MD
79#if defined(__clang__)
80#pragma clang diagnostic push
81#pragma clang diagnostic ignored "-Wignored-attributes"
82#endif
5135c0fd 83typedef union {
48a8832b
MD
84 struct __cds_lfs_stack *_s;
85 struct cds_lfs_stack *s;
087bce43
MD
86} __attribute__((__transparent_union__)) cds_lfs_stack_ptr_t;
87#if defined(__clang__)
88#pragma clang diagnostic pop
89#endif
48a8832b 90
d3bfcb24
MD
91#ifdef _LGPL_SOURCE
92
93#include <urcu/static/lfstack.h>
94
95#define cds_lfs_node_init _cds_lfs_node_init
96#define cds_lfs_init _cds_lfs_init
200d100e 97#define cds_lfs_destroy _cds_lfs_destroy
817a0178 98#define __cds_lfs_init ___cds_lfs_init
7294103b 99#define cds_lfs_empty _cds_lfs_empty
d3bfcb24 100#define cds_lfs_push _cds_lfs_push
7294103b
MD
101
102/* Locking performed internally */
103#define cds_lfs_pop_blocking _cds_lfs_pop_blocking
104#define cds_lfs_pop_all_blocking _cds_lfs_pop_all_blocking
105
106/* Synchronize pop with internal mutex */
107#define cds_lfs_pop_lock _cds_lfs_pop_lock
108#define cds_lfs_pop_unlock _cds_lfs_pop_unlock
109
110/* Synchronization ensured by the caller. See synchronization table. */
111#define __cds_lfs_pop ___cds_lfs_pop
112#define __cds_lfs_pop_all ___cds_lfs_pop_all
d3bfcb24
MD
113
114#else /* !_LGPL_SOURCE */
115
7294103b
MD
116/*
117 * cds_lfs_node_init: initialize lock-free stack node.
118 */
d3bfcb24 119extern void cds_lfs_node_init(struct cds_lfs_node *node);
7294103b
MD
120
121/*
200d100e
MD
122 * cds_lfs_init: initialize lock-free stack (with locking). Pair with
123 * cds_lfs_destroy().
7294103b 124 */
d3bfcb24
MD
125extern void cds_lfs_init(struct cds_lfs_stack *s);
126
48a8832b 127/*
200d100e
MD
128 * cds_lfs_destroy: destroy lock-free stack (with lock). Pair with
129 * cds_lfs_init().
130 */
131extern void cds_lfs_destroy(struct cds_lfs_stack *s);
132
133/*
134 * __cds_lfs_init: initialize lock-free stack (without lock).
135 * Don't pair with any destroy function.
48a8832b
MD
136 */
137extern void __cds_lfs_init(struct __cds_lfs_stack *s);
138
7294103b
MD
139/*
140 * cds_lfs_empty: return whether lock-free stack is empty.
141 *
142 * No memory barrier is issued. No mutual exclusion is required.
143 */
48a8832b 144extern bool cds_lfs_empty(cds_lfs_stack_ptr_t s);
7294103b 145
d3bfcb24
MD
146/*
147 * cds_lfs_push: push a node into the stack.
148 *
149 * Does not require any synchronization with other push nor pop.
150 *
151 * Returns 0 if the stack was empty prior to adding the node.
152 * Returns non-zero otherwise.
153 */
48a8832b 154extern bool cds_lfs_push(cds_lfs_stack_ptr_t s,
d3bfcb24
MD
155 struct cds_lfs_node *node);
156
157/*
7294103b
MD
158 * cds_lfs_pop_blocking: pop a node from the stack.
159 *
160 * Calls __cds_lfs_pop with an internal pop mutex held.
161 */
162extern struct cds_lfs_node *cds_lfs_pop_blocking(struct cds_lfs_stack *s);
163
164/*
165 * cds_lfs_pop_all_blocking: pop all nodes from a stack.
166 *
167 * Calls __cds_lfs_pop_all with an internal pop mutex held.
168 */
169extern struct cds_lfs_head *cds_lfs_pop_all_blocking(struct cds_lfs_stack *s);
170
171/*
172 * cds_lfs_pop_lock: lock stack pop-protection mutex.
173 */
174extern void cds_lfs_pop_lock(struct cds_lfs_stack *s);
175
176/*
177 * cds_lfs_pop_unlock: unlock stack pop-protection mutex.
178 */
179extern void cds_lfs_pop_unlock(struct cds_lfs_stack *s);
180
181/*
182 * __cds_lfs_pop: pop a node from the stack.
d3bfcb24
MD
183 *
184 * Returns NULL if stack is empty.
185 *
7294103b 186 * __cds_lfs_pop needs to be synchronized using one of the following
d3bfcb24
MD
187 * techniques:
188 *
f9b5c2b6
MD
189 * 1) Calling __cds_lfs_pop under rcu read lock critical section.
190 * Both __cds_lfs_pop and __cds_lfs_pop_all callers must wait for a
191 * grace period to pass before freeing the returned node or pushing
192 * the node back into the stack. It is valid to overwrite the content
193 * of cds_lfs_node immediately after __cds_lfs_pop and
194 * __cds_lfs_pop_all.
7294103b
MD
195 * 2) Using mutual exclusion (e.g. mutexes) to protect __cds_lfs_pop
196 * and __cds_lfs_pop_all callers.
197 * 3) Ensuring that only ONE thread can call __cds_lfs_pop() and
198 * __cds_lfs_pop_all(). (multi-provider/single-consumer scheme).
d3bfcb24 199 */
48a8832b 200extern struct cds_lfs_node *__cds_lfs_pop(cds_lfs_stack_ptr_t s);
7294103b
MD
201
202/*
203 * __cds_lfs_pop_all: pop all nodes from a stack.
204 *
205 * __cds_lfs_pop_all does not require any synchronization with other
206 * push, nor with other __cds_lfs_pop_all, but requires synchronization
207 * matching the technique used to synchronize __cds_lfs_pop:
208 *
209 * 1) If __cds_lfs_pop is called under rcu read lock critical section,
f9b5c2b6
MD
210 * both __cds_lfs_pop and __cds_lfs_pop_all callers must wait for a
211 * grace period to pass before freeing the returned node or pushing
212 * the node back into the stack. It is valid to overwrite the content
213 * of cds_lfs_node immediately after __cds_lfs_pop and
214 * __cds_lfs_pop_all. No RCU read-side critical section is needed
215 * around __cds_lfs_pop_all.
7294103b
MD
216 * 2) Using mutual exclusion (e.g. mutexes) to protect __cds_lfs_pop and
217 * __cds_lfs_pop_all callers.
218 * 3) Ensuring that only ONE thread can call __cds_lfs_pop() and
219 * __cds_lfs_pop_all(). (multi-provider/single-consumer scheme).
220 */
48a8832b 221extern struct cds_lfs_head *__cds_lfs_pop_all(cds_lfs_stack_ptr_t s);
d3bfcb24
MD
222
223#endif /* !_LGPL_SOURCE */
224
7294103b
MD
225/*
226 * cds_lfs_for_each: Iterate over all nodes returned by
227 * __cds_lfs_pop_all.
228 * @__head: node returned by __cds_lfs_pop_all (struct cds_lfs_head pointer).
229 * @__node: node to use as iterator (struct cds_lfs_node pointer).
230 *
231 * Content written into each node before push is guaranteed to be
232 * consistent, but no other memory ordering is ensured.
233 */
234#define cds_lfs_for_each(__head, __node) \
235 for (__node = &__head->node; \
236 __node != NULL; \
237 __node = __node->next)
238
239/*
240 * cds_lfs_for_each_safe: Iterate over all nodes returned by
241 * __cds_lfs_pop_all, safe against node deletion.
242 * @__head: node returned by __cds_lfs_pop_all (struct cds_lfs_head pointer).
243 * @__node: node to use as iterator (struct cds_lfs_node pointer).
244 * @__n: struct cds_lfs_node pointer holding the next pointer (used
245 * internally).
246 *
247 * Content written into each node before push is guaranteed to be
248 * consistent, but no other memory ordering is ensured.
249 */
250#define cds_lfs_for_each_safe(__head, __node, __n) \
251 for (__node = &__head->node, __n = (__node ? __node->next : NULL); \
252 __node != NULL; \
253 __node = __n, __n = (__node ? __node->next : NULL))
254
d3bfcb24
MD
255#ifdef __cplusplus
256}
e9349020
MD
257
258/*
259 * In C++, implement static inline wrappers using function overloading
260 * to obtain an API similar to C.
261 */
262
3a602ac1 263static inline cds_lfs_stack_ptr_t cds_lfs_stack_cast(struct __cds_lfs_stack *s)
e9349020
MD
264{
265 cds_lfs_stack_ptr_t ret = {
266 ._s = s,
267 };
268 return ret;
269}
270
271static inline cds_lfs_stack_ptr_t cds_lfs_stack_cast(struct cds_lfs_stack *s)
272{
273 cds_lfs_stack_ptr_t ret = {
274 .s = s,
275 };
276 return ret;
277}
278
9298902c 279template<typename T> static inline bool cds_lfs_empty(T s)
e9349020 280{
3a602ac1 281 return cds_lfs_empty(cds_lfs_stack_cast(s));
e9349020
MD
282}
283
9298902c 284template<typename T> static inline bool cds_lfs_push(T s,
e9349020
MD
285 struct cds_lfs_node *node)
286{
287 return cds_lfs_push(cds_lfs_stack_cast(s), node);
288}
289
9298902c 290template<typename T> static inline struct cds_lfs_node *__cds_lfs_pop(T s)
e9349020 291{
3a602ac1 292 return __cds_lfs_pop(cds_lfs_stack_cast(s));
e9349020
MD
293}
294
9298902c 295template<typename T> static inline struct cds_lfs_head *__cds_lfs_pop_all(T s)
e9349020
MD
296{
297 return __cds_lfs_pop_all(cds_lfs_stack_cast(s));
298}
299
300#endif /* __cplusplus */
d3bfcb24
MD
301
302#endif /* _URCU_LFSTACK_H */
This page took 0.055672 seconds and 4 git commands to generate.