1 #ifndef _URCU_WFCQUEUE_H
2 #define _URCU_WFCQUEUE_H
7 * Userspace RCU library - Concurrent Queue with Wait-Free Enqueue/Blocking Dequeue
9 * Copyright 2010-2012 - Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
10 * Copyright 2011-2012 - Lai Jiangshan <laijs@cn.fujitsu.com>
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.
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.
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
30 #include <urcu/compiler.h>
31 #include <urcu/arch.h>
38 * Concurrent queue with wait-free enqueue/blocking dequeue.
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.
46 struct cds_wfcq_node
{
47 struct cds_wfcq_node
*next
;
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.
55 struct cds_wfcq_head
{
56 struct cds_wfcq_node node
;
60 struct cds_wfcq_tail
{
61 struct cds_wfcq_node
*p
;
66 #include <urcu/static/wfcqueue.h>
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
74 #define cds_wfcq_dequeue_lock _cds_wfcq_dequeue_lock
75 #define cds_wfcq_dequeue_unlock _cds_wfcq_dequeue_unlock
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
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
89 #else /* !_LGPL_SOURCE */
92 * Mutual exclusion of cds_wfcq_* / __cds_wfcq_* API
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().
103 * For convenience, cds_wfcq_dequeue_blocking() and
104 * cds_wfcq_splice_blocking() hold the dequeue lock.
108 * cds_wfcq_node_init: initialize wait-free queue node.
110 extern void cds_wfcq_node_init(struct cds_wfcq_node
*node
);
113 * cds_wfcq_init: initialize wait-free queue.
115 extern void cds_wfcq_init(struct cds_wfcq_head
*head
,
116 struct cds_wfcq_tail
*tail
);
119 * cds_wfcq_empty: return whether wait-free queue is empty.
121 * No memory barrier is issued. No mutual exclusion is required.
123 extern bool cds_wfcq_empty(struct cds_wfcq_head
*head
,
124 struct cds_wfcq_tail
*tail
);
127 * cds_wfcq_dequeue_lock: take the dequeue mutual exclusion lock.
129 extern void cds_wfcq_dequeue_lock(struct cds_wfcq_head
*head
,
130 struct cds_wfcq_tail
*tail
);
133 * cds_wfcq_dequeue_unlock: release the dequeue mutual exclusion lock.
135 extern void cds_wfcq_dequeue_unlock(struct cds_wfcq_head
*head
,
136 struct cds_wfcq_tail
*tail
);
139 * cds_wfcq_enqueue: enqueue a node into a wait-free queue.
141 * Issues a full memory barrier before enqueue. No mutual exclusion is
144 extern void cds_wfcq_enqueue(struct cds_wfcq_head
*head
,
145 struct cds_wfcq_tail
*tail
,
146 struct cds_wfcq_node
*node
);
149 * cds_wfcq_dequeue_blocking: dequeue a node from a wait-free queue.
151 * Content written into the node before enqueue is guaranteed to be
152 * consistent, but no other memory ordering is ensured.
153 * It is valid to reuse and free a dequeued node immediately.
154 * Mutual exlusion with dequeuers is ensured internally.
156 extern struct cds_wfcq_node
*cds_wfcq_dequeue_blocking(
157 struct cds_wfcq_head
*head
,
158 struct cds_wfcq_tail
*tail
);
161 * cds_wfcq_splice_blocking: enqueue all src_q nodes at the end of dest_q.
163 * Dequeue all nodes from src_q.
164 * dest_q must be already initialized.
165 * Content written into the node before enqueue is guaranteed to be
166 * consistent, but no other memory ordering is ensured.
167 * Mutual exlusion with dequeuers is ensured internally.
169 extern void cds_wfcq_splice_blocking(
170 struct cds_wfcq_head
*dest_q_head
,
171 struct cds_wfcq_tail
*dest_q_tail
,
172 struct cds_wfcq_head
*src_q_head
,
173 struct cds_wfcq_tail
*src_q_tail
);
176 * __cds_wfcq_dequeue_blocking:
178 * Content written into the node before enqueue is guaranteed to be
179 * consistent, but no other memory ordering is ensured.
180 * It is valid to reuse and free a dequeued node immediately.
181 * Should be called with cds_wfcq_dequeue_lock() held.
183 extern struct cds_wfcq_node
*__cds_wfcq_dequeue_blocking(
184 struct cds_wfcq_head
*head
,
185 struct cds_wfcq_tail
*tail
);
188 * __cds_wfcq_splice_blocking: enqueue all src_q nodes at the end of dest_q.
190 * Dequeue all nodes from src_q.
191 * dest_q must be already initialized.
192 * Content written into the node before enqueue is guaranteed to be
193 * consistent, but no other memory ordering is ensured.
194 * Should be called with cds_wfcq_dequeue_lock() held.
196 extern void __cds_wfcq_splice_blocking(
197 struct cds_wfcq_head
*dest_q_head
,
198 struct cds_wfcq_tail
*dest_q_tail
,
199 struct cds_wfcq_head
*src_q_head
,
200 struct cds_wfcq_tail
*src_q_tail
);
203 * __cds_wfcq_first_blocking: get first node of a queue, without dequeuing.
205 * Content written into the node before enqueue is guaranteed to be
206 * consistent, but no other memory ordering is ensured.
207 * Should be called with cds_wfcq_dequeue_lock() held.
209 * Used by for-like iteration macros:
210 * __cds_wfcq_for_each_blocking()
211 * __cds_wfcq_for_each_blocking_safe()
213 extern struct cds_wfcq_node
*__cds_wfcq_first_blocking(
214 struct cds_wfcq_head
*head
,
215 struct cds_wfcq_tail
*tail
);
218 * __cds_wfcq_next_blocking: get next node of a queue, without dequeuing.
220 * Content written into the node before enqueue is guaranteed to be
221 * consistent, but no other memory ordering is ensured.
222 * Should be called with cds_wfcq_dequeue_lock() held.
224 * Used by for-like iteration macros:
225 * __cds_wfcq_for_each_blocking()
226 * __cds_wfcq_for_each_blocking_safe()
228 extern struct cds_wfcq_node
*__cds_wfcq_next_blocking(
229 struct cds_wfcq_head
*head
,
230 struct cds_wfcq_tail
*tail
,
231 struct cds_wfcq_node
*node
);
233 #endif /* !_LGPL_SOURCE */
236 * __cds_wfcq_for_each_blocking: Iterate over all nodes in a queue,
237 * without dequeuing them.
238 * @head: head of the queue (struct cds_wfcq_head pointer).
239 * @tail: tail of the queue (struct cds_wfcq_tail pointer).
240 * @node: iterator on the queue (struct cds_wfcq_node pointer).
242 * Content written into each node before enqueue is guaranteed to be
243 * consistent, but no other memory ordering is ensured.
244 * Should be called with cds_wfcq_dequeue_lock() held.
246 #define __cds_wfcq_for_each_blocking(head, tail, node) \
247 for (node = __cds_wfcq_first_blocking(head, tail); \
249 node = __cds_wfcq_next_blocking(head, tail, node))
252 * __cds_wfcq_for_each_blocking_safe: Iterate over all nodes in a queue,
253 * without dequeuing them. Safe against deletion.
254 * @head: head of the queue (struct cds_wfcq_head pointer).
255 * @tail: tail of the queue (struct cds_wfcq_tail pointer).
256 * @node: iterator on the queue (struct cds_wfcq_node pointer).
257 * @n: struct cds_wfcq_node pointer holding the next pointer (used
260 * Content written into each node before enqueue is guaranteed to be
261 * consistent, but no other memory ordering is ensured.
262 * Should be called with cds_wfcq_dequeue_lock() held.
264 #define __cds_wfcq_for_each_blocking_safe(head, tail, node, n) \
265 for (node = __cds_wfcq_first_blocking(head, tail), \
266 n = (node ? __cds_wfcq_next_blocking(head, tail, node) : NULL); \
268 node = n, n = (node ? __cds_wfcq_next_blocking(head, tail, node) : NULL))
274 #endif /* _URCU_WFCQUEUE_H */
This page took 0.036714 seconds and 4 git commands to generate.