1 // SPDX-FileCopyrightText: 2010-2012 Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
3 // SPDX-License-Identifier: LGPL-2.1-or-later
5 #ifndef _URCU_LFSTACK_H
6 #define _URCU_LFSTACK_H
9 * Userspace RCU library - Lock-Free Stack
22 * Stack implementing push, pop, pop_all operations, as well as iterator
23 * on the stack head returned by pop_all.
25 * Synchronization table:
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 "-".
31 * cds_lfs_push __cds_lfs_pop __cds_lfs_pop_all
34 * __cds_lfs_pop_all - X -
36 * cds_lfs_pop_blocking and cds_lfs_pop_all_blocking use an internal
37 * mutex to provide synchronization.
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.
46 struct cds_lfs_node
*next
;
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
56 struct cds_lfs_node node
;
59 struct __cds_lfs_stack
{
60 struct cds_lfs_head
*head
;
63 struct cds_lfs_stack
{
64 struct cds_lfs_head
*head
;
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
73 * In C++, implement static inline wrappers using function overloading
74 * to obtain an API similar to C.
76 * Avoid complaints from clang++ not knowing the transparent union
79 #if defined(__clang__)
80 #pragma clang diagnostic push
81 #pragma clang diagnostic ignored "-Wignored-attributes"
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
93 #include <urcu/static/lfstack.h>
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
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
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
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
114 #else /* !_LGPL_SOURCE */
117 * cds_lfs_node_init: initialize lock-free stack node.
119 extern void cds_lfs_node_init(struct cds_lfs_node
*node
);
122 * cds_lfs_init: initialize lock-free stack (with locking). Pair with
125 extern void cds_lfs_init(struct cds_lfs_stack
*s
);
128 * cds_lfs_destroy: destroy lock-free stack (with lock). Pair with
131 extern void cds_lfs_destroy(struct cds_lfs_stack
*s
);
134 * __cds_lfs_init: initialize lock-free stack (without lock).
135 * Don't pair with any destroy function.
137 extern void __cds_lfs_init(struct __cds_lfs_stack
*s
);
140 * cds_lfs_empty: return whether lock-free stack is empty.
142 * No memory barrier is issued. No mutual exclusion is required.
144 extern bool cds_lfs_empty(cds_lfs_stack_ptr_t s
);
147 * cds_lfs_push: push a node into the stack.
149 * Does not require any synchronization with other push nor pop.
151 * Returns 0 if the stack was empty prior to adding the node.
152 * Returns non-zero otherwise.
154 extern bool cds_lfs_push(cds_lfs_stack_ptr_t s
,
155 struct cds_lfs_node
*node
);
158 * cds_lfs_pop_blocking: pop a node from the stack.
160 * Calls __cds_lfs_pop with an internal pop mutex held.
162 extern struct cds_lfs_node
*cds_lfs_pop_blocking(struct cds_lfs_stack
*s
);
165 * cds_lfs_pop_all_blocking: pop all nodes from a stack.
167 * Calls __cds_lfs_pop_all with an internal pop mutex held.
169 extern struct cds_lfs_head
*cds_lfs_pop_all_blocking(struct cds_lfs_stack
*s
);
172 * cds_lfs_pop_lock: lock stack pop-protection mutex.
174 extern void cds_lfs_pop_lock(struct cds_lfs_stack
*s
);
177 * cds_lfs_pop_unlock: unlock stack pop-protection mutex.
179 extern void cds_lfs_pop_unlock(struct cds_lfs_stack
*s
);
182 * __cds_lfs_pop: pop a node from the stack.
184 * Returns NULL if stack is empty.
186 * __cds_lfs_pop needs to be synchronized using one of the following
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
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).
200 extern struct cds_lfs_node
*__cds_lfs_pop(cds_lfs_stack_ptr_t s
);
203 * __cds_lfs_pop_all: pop all nodes from a stack.
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:
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).
221 extern struct cds_lfs_head
*__cds_lfs_pop_all(cds_lfs_stack_ptr_t s
);
223 #endif /* !_LGPL_SOURCE */
226 * cds_lfs_for_each: Iterate over all nodes returned by
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).
231 * Content written into each node before push is guaranteed to be
232 * consistent, but no other memory ordering is ensured.
234 #define cds_lfs_for_each(__head, __node) \
235 for (__node = &__head->node; \
237 __node = __node->next)
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
247 * Content written into each node before push is guaranteed to be
248 * consistent, but no other memory ordering is ensured.
250 #define cds_lfs_for_each_safe(__head, __node, __n) \
251 for (__node = &__head->node, __n = (__node ? __node->next : NULL); \
253 __node = __n, __n = (__node ? __node->next : NULL))
259 * In C++, implement static inline wrappers using function overloading
260 * to obtain an API similar to C.
263 static inline cds_lfs_stack_ptr_t
cds_lfs_stack_cast(struct __cds_lfs_stack
*s
)
265 cds_lfs_stack_ptr_t ret
= {
271 static inline cds_lfs_stack_ptr_t
cds_lfs_stack_cast(struct cds_lfs_stack
*s
)
273 cds_lfs_stack_ptr_t ret
= {
279 template<typename T
> static inline bool cds_lfs_empty(T s
)
281 return cds_lfs_empty(cds_lfs_stack_cast(s
));
284 template<typename T
> static inline bool cds_lfs_push(T s
,
285 struct cds_lfs_node
*node
)
287 return cds_lfs_push(cds_lfs_stack_cast(s
), node
);
290 template<typename T
> static inline struct cds_lfs_node
*__cds_lfs_pop(T s
)
292 return __cds_lfs_pop(cds_lfs_stack_cast(s
));
295 template<typename T
> static inline struct cds_lfs_head
*__cds_lfs_pop_all(T s
)
297 return __cds_lfs_pop_all(cds_lfs_stack_cast(s
));
300 #endif /* __cplusplus */
302 #endif /* _URCU_LFSTACK_H */
This page took 0.043185 seconds and 4 git commands to generate.