Spelling cleanups within comments and documentation
[urcu.git] / urcu / wfcqueue.h
1 #ifndef _URCU_WFCQUEUE_H
2 #define _URCU_WFCQUEUE_H
3
4 /*
5 * urcu/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 #define CDS_WFCQ_WOULDBLOCK ((void *) -1UL)
47
48 enum cds_wfcq_ret {
49 CDS_WFCQ_RET_WOULDBLOCK = -1,
50 CDS_WFCQ_RET_DEST_EMPTY = 0,
51 CDS_WFCQ_RET_DEST_NON_EMPTY = 1,
52 CDS_WFCQ_RET_SRC_EMPTY = 2,
53 };
54
55 struct cds_wfcq_node {
56 struct cds_wfcq_node *next;
57 };
58
59 /*
60 * Do not put head and tail on the same cache-line if concurrent
61 * enqueue/dequeue are expected from many CPUs. This eliminates
62 * false-sharing between enqueue and dequeue.
63 */
64 struct cds_wfcq_head {
65 struct cds_wfcq_node node;
66 pthread_mutex_t lock;
67 };
68
69 struct cds_wfcq_tail {
70 struct cds_wfcq_node *p;
71 };
72
73 #ifdef _LGPL_SOURCE
74
75 #include <urcu/static/wfcqueue.h>
76
77 #define cds_wfcq_node_init _cds_wfcq_node_init
78 #define cds_wfcq_init _cds_wfcq_init
79 #define cds_wfcq_empty _cds_wfcq_empty
80 #define cds_wfcq_enqueue _cds_wfcq_enqueue
81
82 /* Dequeue locking */
83 #define cds_wfcq_dequeue_lock _cds_wfcq_dequeue_lock
84 #define cds_wfcq_dequeue_unlock _cds_wfcq_dequeue_unlock
85
86 /* Locking performed within cds_wfcq calls. */
87 #define cds_wfcq_dequeue_blocking _cds_wfcq_dequeue_blocking
88 #define cds_wfcq_splice_blocking _cds_wfcq_splice_blocking
89 #define cds_wfcq_first_blocking _cds_wfcq_first_blocking
90 #define cds_wfcq_next_blocking _cds_wfcq_next_blocking
91
92 /* Locking ensured by caller by holding cds_wfcq_dequeue_lock() */
93 #define __cds_wfcq_dequeue_blocking ___cds_wfcq_dequeue_blocking
94 #define __cds_wfcq_splice_blocking ___cds_wfcq_splice_blocking
95 #define __cds_wfcq_first_blocking ___cds_wfcq_first_blocking
96 #define __cds_wfcq_next_blocking ___cds_wfcq_next_blocking
97
98 /*
99 * Locking ensured by caller by holding cds_wfcq_dequeue_lock().
100 * Non-blocking: deque, first, next return CDS_WFCQ_WOULDBLOCK if they
101 * need to block. splice returns nonzero if it needs to block.
102 */
103 #define __cds_wfcq_dequeue_nonblocking ___cds_wfcq_dequeue_nonblocking
104 #define __cds_wfcq_splice_nonblocking ___cds_wfcq_splice_nonblocking
105 #define __cds_wfcq_first_nonblocking ___cds_wfcq_first_nonblocking
106 #define __cds_wfcq_next_nonblocking ___cds_wfcq_next_nonblocking
107
108 #else /* !_LGPL_SOURCE */
109
110 /*
111 * Mutual exclusion of cds_wfcq_* / __cds_wfcq_* API
112 *
113 * Synchronization table:
114 *
115 * External synchronization techniques described in the API below is
116 * required between pairs marked with "X". No external synchronization
117 * required between pairs marked with "-".
118 *
119 * Legend:
120 * [1] cds_wfcq_enqueue
121 * [2] __cds_wfcq_splice (destination queue)
122 * [3] __cds_wfcq_dequeue
123 * [4] __cds_wfcq_splice (source queue)
124 * [5] __cds_wfcq_first
125 * [6] __cds_wfcq_next
126 *
127 * [1] [2] [3] [4] [5] [6]
128 * [1] - - - - - -
129 * [2] - - - - - -
130 * [3] - - X X X X
131 * [4] - - X - X X
132 * [5] - - X X - -
133 * [6] - - X X - -
134 *
135 * Mutual exclusion can be ensured by holding cds_wfcq_dequeue_lock().
136 *
137 * For convenience, cds_wfcq_dequeue_blocking() and
138 * cds_wfcq_splice_blocking() hold the dequeue lock.
139 *
140 * Besides locking, mutual exclusion of dequeue, splice and iteration
141 * can be ensured by performing all of those operations from a single
142 * thread, without requiring any lock.
143 */
144
145 /*
146 * cds_wfcq_node_init: initialize wait-free queue node.
147 */
148 extern void cds_wfcq_node_init(struct cds_wfcq_node *node);
149
150 /*
151 * cds_wfcq_init: initialize wait-free queue.
152 */
153 extern void cds_wfcq_init(struct cds_wfcq_head *head,
154 struct cds_wfcq_tail *tail);
155
156 /*
157 * cds_wfcq_empty: return whether wait-free queue is empty.
158 *
159 * No memory barrier is issued. No mutual exclusion is required.
160 */
161 extern bool cds_wfcq_empty(struct cds_wfcq_head *head,
162 struct cds_wfcq_tail *tail);
163
164 /*
165 * cds_wfcq_dequeue_lock: take the dequeue mutual exclusion lock.
166 */
167 extern void cds_wfcq_dequeue_lock(struct cds_wfcq_head *head,
168 struct cds_wfcq_tail *tail);
169
170 /*
171 * cds_wfcq_dequeue_unlock: release the dequeue mutual exclusion lock.
172 */
173 extern void cds_wfcq_dequeue_unlock(struct cds_wfcq_head *head,
174 struct cds_wfcq_tail *tail);
175
176 /*
177 * cds_wfcq_enqueue: enqueue a node into a wait-free queue.
178 *
179 * Issues a full memory barrier before enqueue. No mutual exclusion is
180 * required.
181 *
182 * Returns false if the queue was empty prior to adding the node.
183 * Returns true otherwise.
184 */
185 extern bool cds_wfcq_enqueue(struct cds_wfcq_head *head,
186 struct cds_wfcq_tail *tail,
187 struct cds_wfcq_node *node);
188
189 /*
190 * cds_wfcq_dequeue_blocking: dequeue a node from a wait-free queue.
191 *
192 * Content written into the node before enqueue is guaranteed to be
193 * consistent, but no other memory ordering is ensured.
194 * It is valid to reuse and free a dequeued node immediately.
195 * Mutual exclusion with cds_wfcq_dequeue_blocking and dequeue lock is
196 * ensured.
197 */
198 extern struct cds_wfcq_node *cds_wfcq_dequeue_blocking(
199 struct cds_wfcq_head *head,
200 struct cds_wfcq_tail *tail);
201
202 /*
203 * cds_wfcq_splice_blocking: enqueue all src_q nodes at the end of dest_q.
204 *
205 * Dequeue all nodes from src_q.
206 * dest_q must be already initialized.
207 * Content written into the node before enqueue is guaranteed to be
208 * consistent, but no other memory ordering is ensured.
209 * Mutual exclusion with cds_wfcq_dequeue_blocking and dequeue lock is
210 * ensured.
211 *
212 * Returns enum cds_wfcq_ret which indicates the state of the src or
213 * dest queue. Cannot block.
214 */
215 extern enum cds_wfcq_ret cds_wfcq_splice_blocking(
216 struct cds_wfcq_head *dest_q_head,
217 struct cds_wfcq_tail *dest_q_tail,
218 struct cds_wfcq_head *src_q_head,
219 struct cds_wfcq_tail *src_q_tail);
220
221 /*
222 * __cds_wfcq_dequeue_blocking: dequeue a node from a wait-free queue.
223 *
224 * Content written into the node before enqueue is guaranteed to be
225 * consistent, but no other memory ordering is ensured.
226 * It is valid to reuse and free a dequeued node immediately.
227 * Dequeue/splice/iteration mutual exclusion should be ensured by the
228 * caller.
229 */
230 extern struct cds_wfcq_node *__cds_wfcq_dequeue_blocking(
231 struct cds_wfcq_head *head,
232 struct cds_wfcq_tail *tail);
233
234 /*
235 * __cds_wfcq_dequeue_nonblocking: dequeue a node from a wait-free queue.
236 *
237 * Same as __cds_wfcq_dequeue_blocking, but returns CDS_WFCQ_WOULDBLOCK
238 * if it needs to block.
239 */
240 extern struct cds_wfcq_node *__cds_wfcq_dequeue_nonblocking(
241 struct cds_wfcq_head *head,
242 struct cds_wfcq_tail *tail);
243
244 /*
245 * __cds_wfcq_splice_blocking: enqueue all src_q nodes at the end of dest_q.
246 *
247 * Dequeue all nodes from src_q.
248 * dest_q must be already initialized.
249 * Mutual exclusion for src_q should be ensured by the caller as
250 * specified in the "Synchronisation table".
251 * Returns enum cds_wfcq_ret which indicates the state of the src or
252 * dest queue. Never returns CDS_WFCQ_RET_WOULDBLOCK.
253 */
254 extern enum cds_wfcq_ret __cds_wfcq_splice_blocking(
255 struct cds_wfcq_head *dest_q_head,
256 struct cds_wfcq_tail *dest_q_tail,
257 struct cds_wfcq_head *src_q_head,
258 struct cds_wfcq_tail *src_q_tail);
259
260 /*
261 * __cds_wfcq_splice_nonblocking: enqueue all src_q nodes at the end of dest_q.
262 *
263 * Same as __cds_wfcq_splice_blocking, but returns
264 * CDS_WFCQ_RET_WOULDBLOCK if it needs to block.
265 */
266 extern enum cds_wfcq_ret __cds_wfcq_splice_nonblocking(
267 struct cds_wfcq_head *dest_q_head,
268 struct cds_wfcq_tail *dest_q_tail,
269 struct cds_wfcq_head *src_q_head,
270 struct cds_wfcq_tail *src_q_tail);
271
272 /*
273 * __cds_wfcq_first_blocking: get first node of a queue, without dequeuing.
274 *
275 * Content written into the node before enqueue is guaranteed to be
276 * consistent, but no other memory ordering is ensured.
277 * Dequeue/splice/iteration mutual exclusion should be ensured by the
278 * caller.
279 *
280 * Used by for-like iteration macros:
281 * __cds_wfcq_for_each_blocking()
282 * __cds_wfcq_for_each_blocking_safe()
283 *
284 * Returns NULL if queue is empty, first node otherwise.
285 */
286 extern struct cds_wfcq_node *__cds_wfcq_first_blocking(
287 struct cds_wfcq_head *head,
288 struct cds_wfcq_tail *tail);
289
290 /*
291 * __cds_wfcq_first_nonblocking: get first node of a queue, without dequeuing.
292 *
293 * Same as __cds_wfcq_first_blocking, but returns CDS_WFCQ_WOULDBLOCK if
294 * it needs to block.
295 */
296 extern struct cds_wfcq_node *__cds_wfcq_first_nonblocking(
297 struct cds_wfcq_head *head,
298 struct cds_wfcq_tail *tail);
299
300 /*
301 * __cds_wfcq_next_blocking: get next node of a queue, without dequeuing.
302 *
303 * Content written into the node before enqueue is guaranteed to be
304 * consistent, but no other memory ordering is ensured.
305 * Dequeue/splice/iteration mutual exclusion should be ensured by the
306 * caller.
307 *
308 * Used by for-like iteration macros:
309 * __cds_wfcq_for_each_blocking()
310 * __cds_wfcq_for_each_blocking_safe()
311 *
312 * Returns NULL if reached end of queue, non-NULL next queue node
313 * otherwise.
314 */
315 extern struct cds_wfcq_node *__cds_wfcq_next_blocking(
316 struct cds_wfcq_head *head,
317 struct cds_wfcq_tail *tail,
318 struct cds_wfcq_node *node);
319
320 /*
321 * __cds_wfcq_next_blocking: get next node of a queue, without dequeuing.
322 *
323 * Same as __cds_wfcq_next_blocking, but returns CDS_WFCQ_WOULDBLOCK if
324 * it needs to block.
325 */
326 extern struct cds_wfcq_node *__cds_wfcq_next_nonblocking(
327 struct cds_wfcq_head *head,
328 struct cds_wfcq_tail *tail,
329 struct cds_wfcq_node *node);
330
331 #endif /* !_LGPL_SOURCE */
332
333 /*
334 * __cds_wfcq_for_each_blocking: Iterate over all nodes in a queue,
335 * without dequeuing them.
336 * @head: head of the queue (struct cds_wfcq_head pointer).
337 * @tail: tail of the queue (struct cds_wfcq_tail pointer).
338 * @node: iterator on the queue (struct cds_wfcq_node pointer).
339 *
340 * Content written into each node before enqueue is guaranteed to be
341 * consistent, but no other memory ordering is ensured.
342 * Dequeue/splice/iteration mutual exclusion should be ensured by the
343 * caller.
344 */
345 #define __cds_wfcq_for_each_blocking(head, tail, node) \
346 for (node = __cds_wfcq_first_blocking(head, tail); \
347 node != NULL; \
348 node = __cds_wfcq_next_blocking(head, tail, node))
349
350 /*
351 * __cds_wfcq_for_each_blocking_safe: Iterate over all nodes in a queue,
352 * without dequeuing them. Safe against deletion.
353 * @head: head of the queue (struct cds_wfcq_head pointer).
354 * @tail: tail of the queue (struct cds_wfcq_tail pointer).
355 * @node: iterator on the queue (struct cds_wfcq_node pointer).
356 * @n: struct cds_wfcq_node pointer holding the next pointer (used
357 * internally).
358 *
359 * Content written into each node before enqueue is guaranteed to be
360 * consistent, but no other memory ordering is ensured.
361 * Dequeue/splice/iteration mutual exclusion should be ensured by the
362 * caller.
363 */
364 #define __cds_wfcq_for_each_blocking_safe(head, tail, node, n) \
365 for (node = __cds_wfcq_first_blocking(head, tail), \
366 n = (node ? __cds_wfcq_next_blocking(head, tail, node) : NULL); \
367 node != NULL; \
368 node = n, n = (node ? __cds_wfcq_next_blocking(head, tail, node) : NULL))
369
370 #ifdef __cplusplus
371 }
372 #endif
373
374 #endif /* _URCU_WFCQUEUE_H */
This page took 0.063293 seconds and 4 git commands to generate.