ppc.h: use mftb on ppc
[urcu.git] / include / urcu / lfstack.h
1 // SPDX-FileCopyrightText: 2010-2012 Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
2 //
3 // SPDX-License-Identifier: LGPL-2.1-or-later
4
5 #ifndef _URCU_LFSTACK_H
6 #define _URCU_LFSTACK_H
7
8 /*
9 * Userspace RCU library - Lock-Free Stack
10 */
11
12 #ifdef __cplusplus
13 extern "C" {
14 #endif
15
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 */
45 struct cds_lfs_node {
46 struct cds_lfs_node *next;
47 };
48
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 */
55 struct cds_lfs_head {
56 struct cds_lfs_node node;
57 };
58
59 struct __cds_lfs_stack {
60 struct cds_lfs_head *head;
61 };
62
63 struct cds_lfs_stack {
64 struct cds_lfs_head *head;
65 pthread_mutex_t lock;
66 };
67
68 /*
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.
72 *
73 * In C++, implement static inline wrappers using function overloading
74 * to obtain an API similar to C.
75 *
76 * Avoid complaints from clang++ not knowing the transparent union
77 * attribute.
78 */
79 #if defined(__clang__)
80 #pragma clang diagnostic push
81 #pragma clang diagnostic ignored "-Wignored-attributes"
82 #endif
83 typedef union {
84 struct __cds_lfs_stack *_s;
85 struct cds_lfs_stack *s;
86 } __attribute__((__transparent_union__)) cds_lfs_stack_ptr_t;
87 #if defined(__clang__)
88 #pragma clang diagnostic pop
89 #endif
90
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
97 #define cds_lfs_destroy _cds_lfs_destroy
98 #define __cds_lfs_init ___cds_lfs_init
99 #define cds_lfs_empty _cds_lfs_empty
100 #define cds_lfs_push _cds_lfs_push
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
113
114 #else /* !_LGPL_SOURCE */
115
116 /*
117 * cds_lfs_node_init: initialize lock-free stack node.
118 */
119 extern void cds_lfs_node_init(struct cds_lfs_node *node);
120
121 /*
122 * cds_lfs_init: initialize lock-free stack (with locking). Pair with
123 * cds_lfs_destroy().
124 */
125 extern void cds_lfs_init(struct cds_lfs_stack *s);
126
127 /*
128 * cds_lfs_destroy: destroy lock-free stack (with lock). Pair with
129 * cds_lfs_init().
130 */
131 extern 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.
136 */
137 extern void __cds_lfs_init(struct __cds_lfs_stack *s);
138
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 */
144 extern bool cds_lfs_empty(cds_lfs_stack_ptr_t s);
145
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 */
154 extern bool cds_lfs_push(cds_lfs_stack_ptr_t s,
155 struct cds_lfs_node *node);
156
157 /*
158 * cds_lfs_pop_blocking: pop a node from the stack.
159 *
160 * Calls __cds_lfs_pop with an internal pop mutex held.
161 */
162 extern 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 */
169 extern 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 */
174 extern void cds_lfs_pop_lock(struct cds_lfs_stack *s);
175
176 /*
177 * cds_lfs_pop_unlock: unlock stack pop-protection mutex.
178 */
179 extern void cds_lfs_pop_unlock(struct cds_lfs_stack *s);
180
181 /*
182 * __cds_lfs_pop: pop a node from the stack.
183 *
184 * Returns NULL if stack is empty.
185 *
186 * __cds_lfs_pop needs to be synchronized using one of the following
187 * techniques:
188 *
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.
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).
199 */
200 extern struct cds_lfs_node *__cds_lfs_pop(cds_lfs_stack_ptr_t s);
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,
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.
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 */
221 extern struct cds_lfs_head *__cds_lfs_pop_all(cds_lfs_stack_ptr_t s);
222
223 #endif /* !_LGPL_SOURCE */
224
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
255 #ifdef __cplusplus
256 }
257
258 /*
259 * In C++, implement static inline wrappers using function overloading
260 * to obtain an API similar to C.
261 */
262
263 static inline cds_lfs_stack_ptr_t cds_lfs_stack_cast(struct __cds_lfs_stack *s)
264 {
265 cds_lfs_stack_ptr_t ret = {
266 ._s = s,
267 };
268 return ret;
269 }
270
271 static 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
279 template<typename T> static inline bool cds_lfs_empty(T s)
280 {
281 return cds_lfs_empty(cds_lfs_stack_cast(s));
282 }
283
284 template<typename T> static inline bool cds_lfs_push(T s,
285 struct cds_lfs_node *node)
286 {
287 return cds_lfs_push(cds_lfs_stack_cast(s), node);
288 }
289
290 template<typename T> static inline struct cds_lfs_node *__cds_lfs_pop(T s)
291 {
292 return __cds_lfs_pop(cds_lfs_stack_cast(s));
293 }
294
295 template<typename T> static inline struct cds_lfs_head *__cds_lfs_pop_all(T s)
296 {
297 return __cds_lfs_pop_all(cds_lfs_stack_cast(s));
298 }
299
300 #endif /* __cplusplus */
301
302 #endif /* _URCU_LFSTACK_H */
This page took 0.042443 seconds and 4 git commands to generate.