Cleanup: fix cppcheck errors
[urcu.git] / urcu / wfcqueue.h
1 #ifndef _URCU_WFCQUEUE_H
2 #define _URCU_WFCQUEUE_H
3
4 /*
5 * wfcqueue.h
6 *
7 * Userspace RCU library - Concurrent Queue with Wait-Free Enqueue/Blocking Dequeue
8 *
9 * Copyright 2010-2012 - Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
10 * Copyright 2011-2012 - Lai Jiangshan <laijs@cn.fujitsu.com>
11 *
12 * This library is free software; you can redistribute it and/or
13 * modify it under the terms of the GNU Lesser General Public
14 * License as published by the Free Software Foundation; either
15 * version 2.1 of the License, or (at your option) any later version.
16 *
17 * This library is distributed in the hope that it will be useful,
18 * but WITHOUT ANY WARRANTY; without even the implied warranty of
19 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
20 * Lesser General Public License for more details.
21 *
22 * You should have received a copy of the GNU Lesser General Public
23 * License along with this library; if not, write to the Free Software
24 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
25 */
26
27 #include <pthread.h>
28 #include <assert.h>
29 #include <stdbool.h>
30 #include <urcu/compiler.h>
31 #include <urcu/arch.h>
32
33 #ifdef __cplusplus
34 extern "C" {
35 #endif
36
37 /*
38 * Concurrent queue with wait-free enqueue/blocking dequeue.
39 *
40 * This queue has been designed and implemented collaboratively by
41 * Mathieu Desnoyers and Lai Jiangshan. Inspired from
42 * half-wait-free/half-blocking queue implementation done by Paul E.
43 * McKenney.
44 */
45
46 struct cds_wfcq_node {
47 struct cds_wfcq_node *next;
48 };
49
50 /*
51 * Do not put head and tail on the same cache-line if concurrent
52 * enqueue/dequeue are expected from many CPUs. This eliminates
53 * false-sharing between enqueue and dequeue.
54 */
55 struct cds_wfcq_head {
56 struct cds_wfcq_node node;
57 pthread_mutex_t lock;
58 };
59
60 struct cds_wfcq_tail {
61 struct cds_wfcq_node *p;
62 };
63
64 #ifdef _LGPL_SOURCE
65
66 #include <urcu/static/wfcqueue.h>
67
68 #define cds_wfcq_node_init _cds_wfcq_node_init
69 #define cds_wfcq_init _cds_wfcq_init
70 #define cds_wfcq_empty _cds_wfcq_empty
71 #define cds_wfcq_enqueue _cds_wfcq_enqueue
72
73 /* Dequeue locking */
74 #define cds_wfcq_dequeue_lock _cds_wfcq_dequeue_lock
75 #define cds_wfcq_dequeue_unlock _cds_wfcq_dequeue_unlock
76
77 /* Locking performed within cds_wfcq calls. */
78 #define cds_wfcq_dequeue_blocking _cds_wfcq_dequeue_blocking
79 #define cds_wfcq_splice_blocking _cds_wfcq_splice_blocking
80 #define cds_wfcq_first_blocking _cds_wfcq_first_blocking
81 #define cds_wfcq_next_blocking _cds_wfcq_next_blocking
82
83 /* Locking ensured by caller by holding cds_wfcq_dequeue_lock() */
84 #define __cds_wfcq_dequeue_blocking ___cds_wfcq_dequeue_blocking
85 #define __cds_wfcq_splice_blocking ___cds_wfcq_splice_blocking
86 #define __cds_wfcq_first_blocking ___cds_wfcq_first_blocking
87 #define __cds_wfcq_next_blocking ___cds_wfcq_next_blocking
88
89 #else /* !_LGPL_SOURCE */
90
91 /*
92 * Mutual exclusion of cds_wfcq_* / __cds_wfcq_* API
93 *
94 * Unless otherwise stated, the caller must ensure mutual exclusion of
95 * queue update operations "dequeue" and "splice" (for source queue).
96 * Queue read operations "first" and "next", which are used by
97 * "for_each" iterations, need to be protected against concurrent
98 * "dequeue" and "splice" (for source queue) by the caller.
99 * "enqueue", "splice" (for destination queue), and "empty" are the only
100 * operations that can be used without any mutual exclusion.
101 * Mutual exclusion can be ensured by holding cds_wfcq_dequeue_lock().
102 *
103 * For convenience, cds_wfcq_dequeue_blocking() and
104 * cds_wfcq_splice_blocking() hold the dequeue lock.
105 *
106 * Besides locking, mutual exclusion of dequeue, splice and iteration
107 * can be ensured by performing all of those operations from a single
108 * thread, without requiring any lock.
109 */
110
111 /*
112 * cds_wfcq_node_init: initialize wait-free queue node.
113 */
114 extern void cds_wfcq_node_init(struct cds_wfcq_node *node);
115
116 /*
117 * cds_wfcq_init: initialize wait-free queue.
118 */
119 extern void cds_wfcq_init(struct cds_wfcq_head *head,
120 struct cds_wfcq_tail *tail);
121
122 /*
123 * cds_wfcq_empty: return whether wait-free queue is empty.
124 *
125 * No memory barrier is issued. No mutual exclusion is required.
126 */
127 extern bool cds_wfcq_empty(struct cds_wfcq_head *head,
128 struct cds_wfcq_tail *tail);
129
130 /*
131 * cds_wfcq_dequeue_lock: take the dequeue mutual exclusion lock.
132 */
133 extern void cds_wfcq_dequeue_lock(struct cds_wfcq_head *head,
134 struct cds_wfcq_tail *tail);
135
136 /*
137 * cds_wfcq_dequeue_unlock: release the dequeue mutual exclusion lock.
138 */
139 extern void cds_wfcq_dequeue_unlock(struct cds_wfcq_head *head,
140 struct cds_wfcq_tail *tail);
141
142 /*
143 * cds_wfcq_enqueue: enqueue a node into a wait-free queue.
144 *
145 * Issues a full memory barrier before enqueue. No mutual exclusion is
146 * required.
147 */
148 extern void cds_wfcq_enqueue(struct cds_wfcq_head *head,
149 struct cds_wfcq_tail *tail,
150 struct cds_wfcq_node *node);
151
152 /*
153 * cds_wfcq_dequeue_blocking: dequeue a node from a wait-free queue.
154 *
155 * Content written into the node before enqueue is guaranteed to be
156 * consistent, but no other memory ordering is ensured.
157 * It is valid to reuse and free a dequeued node immediately.
158 * Mutual exlusion with cds_wfcq_dequeue_blocking and dequeue lock is
159 * ensured.
160 */
161 extern struct cds_wfcq_node *cds_wfcq_dequeue_blocking(
162 struct cds_wfcq_head *head,
163 struct cds_wfcq_tail *tail);
164
165 /*
166 * cds_wfcq_splice_blocking: enqueue all src_q nodes at the end of dest_q.
167 *
168 * Dequeue all nodes from src_q.
169 * dest_q must be already initialized.
170 * Content written into the node before enqueue is guaranteed to be
171 * consistent, but no other memory ordering is ensured.
172 * Mutual exlusion with cds_wfcq_dequeue_blocking and dequeue lock is
173 * ensured.
174 */
175 extern void cds_wfcq_splice_blocking(
176 struct cds_wfcq_head *dest_q_head,
177 struct cds_wfcq_tail *dest_q_tail,
178 struct cds_wfcq_head *src_q_head,
179 struct cds_wfcq_tail *src_q_tail);
180
181 /*
182 * __cds_wfcq_dequeue_blocking:
183 *
184 * Content written into the node before enqueue is guaranteed to be
185 * consistent, but no other memory ordering is ensured.
186 * It is valid to reuse and free a dequeued node immediately.
187 * Dequeue/splice/iteration mutual exclusion should be ensured by the
188 * caller.
189 */
190 extern struct cds_wfcq_node *__cds_wfcq_dequeue_blocking(
191 struct cds_wfcq_head *head,
192 struct cds_wfcq_tail *tail);
193
194 /*
195 * __cds_wfcq_splice_blocking: enqueue all src_q nodes at the end of dest_q.
196 *
197 * Dequeue all nodes from src_q.
198 * dest_q must be already initialized.
199 * Content written into the node before enqueue is guaranteed to be
200 * consistent, but no other memory ordering is ensured.
201 * Dequeue/splice/iteration mutual exclusion for src_q should be ensured
202 * by the caller.
203 */
204 extern void __cds_wfcq_splice_blocking(
205 struct cds_wfcq_head *dest_q_head,
206 struct cds_wfcq_tail *dest_q_tail,
207 struct cds_wfcq_head *src_q_head,
208 struct cds_wfcq_tail *src_q_tail);
209
210 /*
211 * __cds_wfcq_first_blocking: get first node of a queue, without dequeuing.
212 *
213 * Content written into the node before enqueue is guaranteed to be
214 * consistent, but no other memory ordering is ensured.
215 * Dequeue/splice/iteration mutual exclusion should be ensured by the
216 * caller.
217 *
218 * Used by for-like iteration macros:
219 * __cds_wfcq_for_each_blocking()
220 * __cds_wfcq_for_each_blocking_safe()
221 */
222 extern struct cds_wfcq_node *__cds_wfcq_first_blocking(
223 struct cds_wfcq_head *head,
224 struct cds_wfcq_tail *tail);
225
226 /*
227 * __cds_wfcq_next_blocking: get next node of a queue, without dequeuing.
228 *
229 * Content written into the node before enqueue is guaranteed to be
230 * consistent, but no other memory ordering is ensured.
231 * Dequeue/splice/iteration mutual exclusion should be ensured by the
232 * caller.
233 *
234 * Used by for-like iteration macros:
235 * __cds_wfcq_for_each_blocking()
236 * __cds_wfcq_for_each_blocking_safe()
237 */
238 extern struct cds_wfcq_node *__cds_wfcq_next_blocking(
239 struct cds_wfcq_head *head,
240 struct cds_wfcq_tail *tail,
241 struct cds_wfcq_node *node);
242
243 #endif /* !_LGPL_SOURCE */
244
245 /*
246 * __cds_wfcq_for_each_blocking: Iterate over all nodes in a queue,
247 * without dequeuing them.
248 * @head: head of the queue (struct cds_wfcq_head pointer).
249 * @tail: tail of the queue (struct cds_wfcq_tail pointer).
250 * @node: iterator on the queue (struct cds_wfcq_node pointer).
251 *
252 * Content written into each node before enqueue is guaranteed to be
253 * consistent, but no other memory ordering is ensured.
254 * Dequeue/splice/iteration mutual exclusion should be ensured by the
255 * caller.
256 */
257 #define __cds_wfcq_for_each_blocking(head, tail, node) \
258 for (node = __cds_wfcq_first_blocking(head, tail); \
259 node != NULL; \
260 node = __cds_wfcq_next_blocking(head, tail, node))
261
262 /*
263 * __cds_wfcq_for_each_blocking_safe: Iterate over all nodes in a queue,
264 * without dequeuing them. Safe against deletion.
265 * @head: head of the queue (struct cds_wfcq_head pointer).
266 * @tail: tail of the queue (struct cds_wfcq_tail pointer).
267 * @node: iterator on the queue (struct cds_wfcq_node pointer).
268 * @n: struct cds_wfcq_node pointer holding the next pointer (used
269 * internally).
270 *
271 * Content written into each node before enqueue is guaranteed to be
272 * consistent, but no other memory ordering is ensured.
273 * Dequeue/splice/iteration mutual exclusion should be ensured by the
274 * caller.
275 */
276 #define __cds_wfcq_for_each_blocking_safe(head, tail, node, n) \
277 for (node = __cds_wfcq_first_blocking(head, tail), \
278 n = (node ? __cds_wfcq_next_blocking(head, tail, node) : NULL); \
279 node != NULL; \
280 node = n, n = (node ? __cds_wfcq_next_blocking(head, tail, node) : NULL))
281
282 #ifdef __cplusplus
283 }
284 #endif
285
286 #endif /* _URCU_WFCQUEUE_H */
This page took 0.037059 seconds and 4 git commands to generate.