[urcu.git] / urcu / wfcqueue.h

#ifndef _URCU_WFCQUEUE_H
#define _URCU_WFCQUEUE_H

/*
 * urcu/wfcqueue.h
 *
 * Userspace RCU library - Concurrent Queue with Wait-Free Enqueue/Blocking Dequeue
 *
 * Copyright 2010-2012 - Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
 * Copyright 2011-2012 - Lai Jiangshan <laijs@cn.fujitsu.com>
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public
 * License as published by the Free Software Foundation; either
 * version 2.1 of the License, or (at your option) any later version.
 *
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public
 * License along with this library; if not, write to the Free Software
 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
 */

#include <pthread.h>
#include <assert.h>
#include <stdbool.h>
#include <urcu/compiler.h>
#include <urcu/arch.h>

#ifdef __cplusplus
extern "C" {
#endif

/*
 * Concurrent queue with wait-free enqueue/blocking dequeue.
 *
 * This queue has been designed and implemented collaboratively by
 * Mathieu Desnoyers and Lai Jiangshan. Inspired from
 * half-wait-free/half-blocking queue implementation done by Paul E.
 * McKenney.
 */

#define CDS_WFCQ_WOULDBLOCK	((void *) -1UL)

enum cds_wfcq_ret {
	CDS_WFCQ_RET_WOULDBLOCK = 	-1,
	CDS_WFCQ_RET_DEST_EMPTY =	0,
	CDS_WFCQ_RET_DEST_NON_EMPTY =	1,
	CDS_WFCQ_RET_SRC_EMPTY = 	2,
};

struct cds_wfcq_node {
	struct cds_wfcq_node *next;
};

/*
 * Do not put head and tail on the same cache-line if concurrent
 * enqueue/dequeue are expected from many CPUs. This eliminates
 * false-sharing between enqueue and dequeue.
 */
struct cds_wfcq_head {
	struct cds_wfcq_node node;
	pthread_mutex_t lock;
};

struct cds_wfcq_tail {
	struct cds_wfcq_node *p;
};

#ifdef _LGPL_SOURCE

#include <urcu/static/wfcqueue.h>

#define cds_wfcq_node_init		_cds_wfcq_node_init
#define cds_wfcq_init			_cds_wfcq_init
#define cds_wfcq_empty			_cds_wfcq_empty
#define cds_wfcq_enqueue		_cds_wfcq_enqueue

/* Dequeue locking */
#define cds_wfcq_dequeue_lock		_cds_wfcq_dequeue_lock
#define cds_wfcq_dequeue_unlock		_cds_wfcq_dequeue_unlock

/* Locking performed within cds_wfcq calls. */
#define cds_wfcq_dequeue_blocking	_cds_wfcq_dequeue_blocking
#define cds_wfcq_splice_blocking	_cds_wfcq_splice_blocking
#define cds_wfcq_first_blocking		_cds_wfcq_first_blocking
#define cds_wfcq_next_blocking		_cds_wfcq_next_blocking

/* Locking ensured by caller by holding cds_wfcq_dequeue_lock() */
#define __cds_wfcq_dequeue_blocking	___cds_wfcq_dequeue_blocking
#define __cds_wfcq_splice_blocking	___cds_wfcq_splice_blocking
#define __cds_wfcq_first_blocking	___cds_wfcq_first_blocking
#define __cds_wfcq_next_blocking	___cds_wfcq_next_blocking

/*
 * Locking ensured by caller by holding cds_wfcq_dequeue_lock().
 * Non-blocking: deque, first, next return CDS_WFCQ_WOULDBLOCK if they
 * need to block. splice returns nonzero if it needs to block.
 */
#define __cds_wfcq_dequeue_nonblocking	___cds_wfcq_dequeue_nonblocking
#define __cds_wfcq_splice_nonblocking	___cds_wfcq_splice_nonblocking
#define __cds_wfcq_first_nonblocking	___cds_wfcq_first_nonblocking
#define __cds_wfcq_next_nonblocking	___cds_wfcq_next_nonblocking

#else /* !_LGPL_SOURCE */

/*
 * Mutual exclusion of cds_wfcq_* / __cds_wfcq_* API
 *
 * Unless otherwise stated, the caller must ensure mutual exclusion of
 * queue update operations "dequeue" and "splice" (for source queue).
 * Queue read operations "first" and "next", which are used by
 * "for_each" iterations, need to be protected against concurrent
 * "dequeue" and "splice" (for source queue) by the caller.
 * "enqueue", "splice" (for destination queue), and "empty" are the only
 * operations that can be used without any mutual exclusion.
 * Mutual exclusion can be ensured by holding cds_wfcq_dequeue_lock().
 *
 * For convenience, cds_wfcq_dequeue_blocking() and
 * cds_wfcq_splice_blocking() hold the dequeue lock.
 *
 * Besides locking, mutual exclusion of dequeue, splice and iteration
 * can be ensured by performing all of those operations from a single
 * thread, without requiring any lock.
 */

/*
 * cds_wfcq_node_init: initialize wait-free queue node.
 */
extern void cds_wfcq_node_init(struct cds_wfcq_node *node);

/*
 * cds_wfcq_init: initialize wait-free queue.
 */
extern void cds_wfcq_init(struct cds_wfcq_head *head,
		struct cds_wfcq_tail *tail);

/*
 * cds_wfcq_empty: return whether wait-free queue is empty.
 *
 * No memory barrier is issued. No mutual exclusion is required.
 */
extern bool cds_wfcq_empty(struct cds_wfcq_head *head,
		struct cds_wfcq_tail *tail);

/*
 * cds_wfcq_dequeue_lock: take the dequeue mutual exclusion lock.
 */
extern void cds_wfcq_dequeue_lock(struct cds_wfcq_head *head,
		struct cds_wfcq_tail *tail);

/*
 * cds_wfcq_dequeue_unlock: release the dequeue mutual exclusion lock.
 */
extern void cds_wfcq_dequeue_unlock(struct cds_wfcq_head *head,
		struct cds_wfcq_tail *tail);

/*
 * cds_wfcq_enqueue: enqueue a node into a wait-free queue.
 *
 * Issues a full memory barrier before enqueue. No mutual exclusion is
 * required.
 *
 * Returns false if the queue was empty prior to adding the node.
 * Returns true otherwise.
 */
extern bool cds_wfcq_enqueue(struct cds_wfcq_head *head,
		struct cds_wfcq_tail *tail,
		struct cds_wfcq_node *node);

/*
 * cds_wfcq_dequeue_blocking: dequeue a node from a wait-free queue.
 *
 * Content written into the node before enqueue is guaranteed to be
 * consistent, but no other memory ordering is ensured.
 * It is valid to reuse and free a dequeued node immediately.
 * Mutual exlusion with cds_wfcq_dequeue_blocking and dequeue lock is
 * ensured.
 */
extern struct cds_wfcq_node *cds_wfcq_dequeue_blocking(
		struct cds_wfcq_head *head,
		struct cds_wfcq_tail *tail);

/*
 * cds_wfcq_splice_blocking: enqueue all src_q nodes at the end of dest_q.
 *
 * Dequeue all nodes from src_q.
 * dest_q must be already initialized.
 * Content written into the node before enqueue is guaranteed to be
 * consistent, but no other memory ordering is ensured.
 * Mutual exlusion with cds_wfcq_dequeue_blocking and dequeue lock is
 * ensured.
 *
 * Returns enum cds_wfcq_ret which indicates the state of the src or
 * dest queue. Cannot block.
 */
extern enum cds_wfcq_ret cds_wfcq_splice_blocking(
		struct cds_wfcq_head *dest_q_head,
		struct cds_wfcq_tail *dest_q_tail,
		struct cds_wfcq_head *src_q_head,
		struct cds_wfcq_tail *src_q_tail);

/*
 * __cds_wfcq_dequeue_blocking: dequeue a node from a wait-free queue.
 *
 * Content written into the node before enqueue is guaranteed to be
 * consistent, but no other memory ordering is ensured.
 * It is valid to reuse and free a dequeued node immediately.
 * Dequeue/splice/iteration mutual exclusion should be ensured by the
 * caller.
 */
extern struct cds_wfcq_node *__cds_wfcq_dequeue_blocking(
		struct cds_wfcq_head *head,
		struct cds_wfcq_tail *tail);

/*
 * __cds_wfcq_dequeue_nonblocking: dequeue a node from a wait-free queue.
 *
 * Same as __cds_wfcq_dequeue_blocking, but returns CDS_WFCQ_WOULDBLOCK
 * if it needs to block.
 */
extern struct cds_wfcq_node *__cds_wfcq_dequeue_nonblocking(
		struct cds_wfcq_head *head,
		struct cds_wfcq_tail *tail);

/*
 * __cds_wfcq_splice_blocking: enqueue all src_q nodes at the end of dest_q.
 *
 * Dequeue all nodes from src_q.
 * dest_q must be already initialized.
 * Content written into the node before enqueue is guaranteed to be
 * consistent, but no other memory ordering is ensured.
 * Dequeue/splice/iteration mutual exclusion for src_q should be ensured
 * by the caller.
 *
 * Returns enum cds_wfcq_ret which indicates the state of the src or
 * dest queue. Cannot block.
 */
extern enum cds_wfcq_ret __cds_wfcq_splice_blocking(
		struct cds_wfcq_head *dest_q_head,
		struct cds_wfcq_tail *dest_q_tail,
		struct cds_wfcq_head *src_q_head,
		struct cds_wfcq_tail *src_q_tail);

/*
 * __cds_wfcq_splice_nonblocking: enqueue all src_q nodes at the end of dest_q.
 *
 * Same as __cds_wfcq_splice_blocking, but returns
 * CDS_WFCQ_RET_WOULDBLOCK if it needs to block.
 */
extern enum cds_wfcq_ret __cds_wfcq_splice_nonblocking(
		struct cds_wfcq_head *dest_q_head,
		struct cds_wfcq_tail *dest_q_tail,
		struct cds_wfcq_head *src_q_head,
		struct cds_wfcq_tail *src_q_tail);

/*
 * __cds_wfcq_first_blocking: get first node of a queue, without dequeuing.
 *
 * Content written into the node before enqueue is guaranteed to be
 * consistent, but no other memory ordering is ensured.
 * Dequeue/splice/iteration mutual exclusion should be ensured by the
 * caller.
 *
 * Used by for-like iteration macros:
 * __cds_wfcq_for_each_blocking()
 * __cds_wfcq_for_each_blocking_safe()
 */
extern struct cds_wfcq_node *__cds_wfcq_first_blocking(
		struct cds_wfcq_head *head,
		struct cds_wfcq_tail *tail);

/*
 * __cds_wfcq_first_nonblocking: get first node of a queue, without dequeuing.
 *
 * Same as __cds_wfcq_first_blocking, but returns CDS_WFCQ_WOULDBLOCK if
 * it needs to block.
 */
extern struct cds_wfcq_node *__cds_wfcq_first_nonblocking(
		struct cds_wfcq_head *head,
		struct cds_wfcq_tail *tail);

/*
 * __cds_wfcq_next_blocking: get next node of a queue, without dequeuing.
 *
 * Content written into the node before enqueue is guaranteed to be
 * consistent, but no other memory ordering is ensured.
 * Dequeue/splice/iteration mutual exclusion should be ensured by the
 * caller.
 *
 * Used by for-like iteration macros:
 * __cds_wfcq_for_each_blocking()
 * __cds_wfcq_for_each_blocking_safe()
 */
extern struct cds_wfcq_node *__cds_wfcq_next_blocking(
		struct cds_wfcq_head *head,
		struct cds_wfcq_tail *tail,
		struct cds_wfcq_node *node);

/*
 * __cds_wfcq_next_blocking: get next node of a queue, without dequeuing.
 *
 * Same as __cds_wfcq_next_blocking, but returns CDS_WFCQ_WOULDBLOCK if
 * it needs to block.
 */
extern struct cds_wfcq_node *__cds_wfcq_next_nonblocking(
		struct cds_wfcq_head *head,
		struct cds_wfcq_tail *tail,
		struct cds_wfcq_node *node);

#endif /* !_LGPL_SOURCE */

/*
 * __cds_wfcq_for_each_blocking: Iterate over all nodes in a queue,
 * without dequeuing them.
 * @head: head of the queue (struct cds_wfcq_head pointer).
 * @tail: tail of the queue (struct cds_wfcq_tail pointer).
 * @node: iterator on the queue (struct cds_wfcq_node pointer).
 *
 * Content written into each node before enqueue is guaranteed to be
 * consistent, but no other memory ordering is ensured.
 * Dequeue/splice/iteration mutual exclusion should be ensured by the
 * caller.
 */
#define __cds_wfcq_for_each_blocking(head, tail, node)		\
	for (node = __cds_wfcq_first_blocking(head, tail);	\
		node != NULL;					\
		node = __cds_wfcq_next_blocking(head, tail, node))

/*
 * __cds_wfcq_for_each_blocking_safe: Iterate over all nodes in a queue,
 * without dequeuing them. Safe against deletion.
 * @head: head of the queue (struct cds_wfcq_head pointer).
 * @tail: tail of the queue (struct cds_wfcq_tail pointer).
 * @node: iterator on the queue (struct cds_wfcq_node pointer).
 * @n: struct cds_wfcq_node pointer holding the next pointer (used
 *     internally).
 *
 * Content written into each node before enqueue is guaranteed to be
 * consistent, but no other memory ordering is ensured.
 * Dequeue/splice/iteration mutual exclusion should be ensured by the
 * caller.
 */
#define __cds_wfcq_for_each_blocking_safe(head, tail, node, n)		       \
	for (node = __cds_wfcq_first_blocking(head, tail),		       \
			n = (node ? __cds_wfcq_next_blocking(head, tail, node) : NULL); \
		node != NULL;						       \
		node = n, n = (node ? __cds_wfcq_next_blocking(head, tail, node) : NULL))

#ifdef __cplusplus
}
#endif

#endif /* _URCU_WFCQUEUE_H */
Commit	Line	Data
8ad4ce58 MD	1	#ifndef _URCU_WFCQUEUE_H
	2	#define _URCU_WFCQUEUE_H
	3
	4	/*
47215721	5	* urcu/wfcqueue.h
8ad4ce58 MD	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	*
ebfd2673 MD	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.
8ad4ce58 MD	44	*/
8ad4ce58 MD	45
47215721 MD	46	#define CDS_WFCQ_WOULDBLOCK ((void *) -1UL)
47215721 MD	47
23773356 MD	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
8ad4ce58 MD	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
47215721 MD	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
8ad4ce58 MD	108	#else /* !_LGPL_SOURCE */
	109
	110	/*
	111	* Mutual exclusion of cds_wfcq_* / __cds_wfcq_* API
	112	*
	113	* Unless otherwise stated, the caller must ensure mutual exclusion of
	114	* queue update operations "dequeue" and "splice" (for source queue).
f94061a3 MD	115	* Queue read operations "first" and "next", which are used by
	116	* "for_each" iterations, need to be protected against concurrent
	117	* "dequeue" and "splice" (for source queue) by the caller.
8ad4ce58 MD	118	* "enqueue", "splice" (for destination queue), and "empty" are the only
	119	* operations that can be used without any mutual exclusion.
	120	* Mutual exclusion can be ensured by holding cds_wfcq_dequeue_lock().
	121	*
	122	* For convenience, cds_wfcq_dequeue_blocking() and
	123	* cds_wfcq_splice_blocking() hold the dequeue lock.
1fe734e1 MD	124	*
	125	* Besides locking, mutual exclusion of dequeue, splice and iteration
	126	* can be ensured by performing all of those operations from a single
	127	* thread, without requiring any lock.
8ad4ce58 MD	128	*/
	129
	130	/*
	131	* cds_wfcq_node_init: initialize wait-free queue node.
	132	*/
	133	extern void cds_wfcq_node_init(struct cds_wfcq_node *node);
	134
	135	/*
	136	* cds_wfcq_init: initialize wait-free queue.
	137	*/
	138	extern void cds_wfcq_init(struct cds_wfcq_head *head,
	139	struct cds_wfcq_tail *tail);
	140
	141	/*
	142	* cds_wfcq_empty: return whether wait-free queue is empty.
	143	*
	144	* No memory barrier is issued. No mutual exclusion is required.
	145	*/
	146	extern bool cds_wfcq_empty(struct cds_wfcq_head *head,
	147	struct cds_wfcq_tail *tail);
	148
	149	/*
	150	* cds_wfcq_dequeue_lock: take the dequeue mutual exclusion lock.
	151	*/
	152	extern void cds_wfcq_dequeue_lock(struct cds_wfcq_head *head,
	153	struct cds_wfcq_tail *tail);
	154
	155	/*
	156	* cds_wfcq_dequeue_unlock: release the dequeue mutual exclusion lock.
	157	*/
	158	extern void cds_wfcq_dequeue_unlock(struct cds_wfcq_head *head,
	159	struct cds_wfcq_tail *tail);
	160
	161	/*
	162	* cds_wfcq_enqueue: enqueue a node into a wait-free queue.
	163	*
	164	* Issues a full memory barrier before enqueue. No mutual exclusion is
	165	* required.
23773356 MD	166	*
	167	* Returns false if the queue was empty prior to adding the node.
	168	* Returns true otherwise.
8ad4ce58	169	*/
23773356	170	extern bool cds_wfcq_enqueue(struct cds_wfcq_head *head,
8ad4ce58 MD	171	struct cds_wfcq_tail *tail,
	172	struct cds_wfcq_node *node);
	173
	174	/*
	175	* cds_wfcq_dequeue_blocking: dequeue a node from a wait-free queue.
	176	*
	177	* Content written into the node before enqueue is guaranteed to be
	178	* consistent, but no other memory ordering is ensured.
	179	* It is valid to reuse and free a dequeued node immediately.
1fe734e1 MD	180	* Mutual exlusion with cds_wfcq_dequeue_blocking and dequeue lock is
1fe734e1 MD	181	* ensured.
8ad4ce58 MD	182	*/
	183	extern struct cds_wfcq_node *cds_wfcq_dequeue_blocking(
	184	struct cds_wfcq_head *head,
	185	struct cds_wfcq_tail *tail);
	186
	187	/*
	188	* cds_wfcq_splice_blocking: enqueue all src_q nodes at the end of dest_q.
	189	*
	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.
1fe734e1 MD	194	* Mutual exlusion with cds_wfcq_dequeue_blocking and dequeue lock is
1fe734e1 MD	195	* ensured.
23773356 MD	196	*
	197	* Returns enum cds_wfcq_ret which indicates the state of the src or
	198	* dest queue. Cannot block.
8ad4ce58	199	*/
23773356	200	extern enum cds_wfcq_ret cds_wfcq_splice_blocking(
8ad4ce58 MD	201	struct cds_wfcq_head *dest_q_head,
	202	struct cds_wfcq_tail *dest_q_tail,
	203	struct cds_wfcq_head *src_q_head,
	204	struct cds_wfcq_tail *src_q_tail);
	205
	206	/*
47215721	207	* __cds_wfcq_dequeue_blocking: dequeue a node from a wait-free queue.
8ad4ce58 MD	208	*
	209	* Content written into the node before enqueue is guaranteed to be
	210	* consistent, but no other memory ordering is ensured.
	211	* It is valid to reuse and free a dequeued node immediately.
1fe734e1 MD	212	* Dequeue/splice/iteration mutual exclusion should be ensured by the
1fe734e1 MD	213	* caller.
8ad4ce58 MD	214	*/
	215	extern struct cds_wfcq_node *__cds_wfcq_dequeue_blocking(
	216	struct cds_wfcq_head *head,
	217	struct cds_wfcq_tail *tail);
	218
47215721 MD	219	/*
	220	* __cds_wfcq_dequeue_nonblocking: dequeue a node from a wait-free queue.
	221	*
	222	* Same as __cds_wfcq_dequeue_blocking, but returns CDS_WFCQ_WOULDBLOCK
	223	* if it needs to block.
	224	*/
	225	extern struct cds_wfcq_node *__cds_wfcq_dequeue_nonblocking(
	226	struct cds_wfcq_head *head,
	227	struct cds_wfcq_tail *tail);
	228
8ad4ce58 MD	229	/*
	230	* __cds_wfcq_splice_blocking: enqueue all src_q nodes at the end of dest_q.
	231	*
	232	* Dequeue all nodes from src_q.
	233	* dest_q must be already initialized.
	234	* Content written into the node before enqueue is guaranteed to be
	235	* consistent, but no other memory ordering is ensured.
1fe734e1 MD	236	* Dequeue/splice/iteration mutual exclusion for src_q should be ensured
1fe734e1 MD	237	* by the caller.
23773356 MD	238	*
	239	* Returns enum cds_wfcq_ret which indicates the state of the src or
	240	* dest queue. Cannot block.
8ad4ce58	241	*/
23773356	242	extern enum cds_wfcq_ret __cds_wfcq_splice_blocking(
8ad4ce58 MD	243	struct cds_wfcq_head *dest_q_head,
	244	struct cds_wfcq_tail *dest_q_tail,
	245	struct cds_wfcq_head *src_q_head,
	246	struct cds_wfcq_tail *src_q_tail);
	247
47215721 MD	248	/*
	249	* __cds_wfcq_splice_nonblocking: enqueue all src_q nodes at the end of dest_q.
	250	*
23773356 MD	251	* Same as __cds_wfcq_splice_blocking, but returns
23773356 MD	252	* CDS_WFCQ_RET_WOULDBLOCK if it needs to block.
47215721	253	*/
23773356	254	extern enum cds_wfcq_ret __cds_wfcq_splice_nonblocking(
47215721 MD	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
8ad4ce58 MD	260	/*
	261	* __cds_wfcq_first_blocking: get first node of a queue, without dequeuing.
	262	*
	263	* Content written into the node before enqueue is guaranteed to be
	264	* consistent, but no other memory ordering is ensured.
1fe734e1 MD	265	* Dequeue/splice/iteration mutual exclusion should be ensured by the
1fe734e1 MD	266	* caller.
f94061a3 MD	267	*
	268	* Used by for-like iteration macros:
	269	* __cds_wfcq_for_each_blocking()
	270	* __cds_wfcq_for_each_blocking_safe()
8ad4ce58 MD	271	*/
	272	extern struct cds_wfcq_node *__cds_wfcq_first_blocking(
	273	struct cds_wfcq_head *head,
	274	struct cds_wfcq_tail *tail);
	275
47215721 MD	276	/*
	277	* __cds_wfcq_first_nonblocking: get first node of a queue, without dequeuing.
	278	*
	279	* Same as __cds_wfcq_first_blocking, but returns CDS_WFCQ_WOULDBLOCK if
	280	* it needs to block.
	281	*/
	282	extern struct cds_wfcq_node *__cds_wfcq_first_nonblocking(
	283	struct cds_wfcq_head *head,
	284	struct cds_wfcq_tail *tail);
	285
8ad4ce58 MD	286	/*
	287	* __cds_wfcq_next_blocking: get next node of a queue, without dequeuing.
	288	*
	289	* Content written into the node before enqueue is guaranteed to be
	290	* consistent, but no other memory ordering is ensured.
1fe734e1 MD	291	* Dequeue/splice/iteration mutual exclusion should be ensured by the
1fe734e1 MD	292	* caller.
f94061a3 MD	293	*
	294	* Used by for-like iteration macros:
	295	* __cds_wfcq_for_each_blocking()
	296	* __cds_wfcq_for_each_blocking_safe()
8ad4ce58 MD	297	*/
	298	extern struct cds_wfcq_node *__cds_wfcq_next_blocking(
	299	struct cds_wfcq_head *head,
	300	struct cds_wfcq_tail *tail,
	301	struct cds_wfcq_node *node);
	302
47215721 MD	303	/*
	304	* __cds_wfcq_next_blocking: get next node of a queue, without dequeuing.
	305	*
	306	* Same as __cds_wfcq_next_blocking, but returns CDS_WFCQ_WOULDBLOCK if
	307	* it needs to block.
	308	*/
	309	extern struct cds_wfcq_node *__cds_wfcq_next_nonblocking(
	310	struct cds_wfcq_head *head,
	311	struct cds_wfcq_tail *tail,
	312	struct cds_wfcq_node *node);
	313
8ad4ce58 MD	314	#endif /* !_LGPL_SOURCE */
	315
	316	/*
	317	* __cds_wfcq_for_each_blocking: Iterate over all nodes in a queue,
	318	* without dequeuing them.
	319	* @head: head of the queue (struct cds_wfcq_head pointer).
	320	* @tail: tail of the queue (struct cds_wfcq_tail pointer).
	321	* @node: iterator on the queue (struct cds_wfcq_node pointer).
	322	*
	323	* Content written into each node before enqueue is guaranteed to be
	324	* consistent, but no other memory ordering is ensured.
1fe734e1 MD	325	* Dequeue/splice/iteration mutual exclusion should be ensured by the
1fe734e1 MD	326	* caller.
8ad4ce58 MD	327	*/
	328	#define __cds_wfcq_for_each_blocking(head, tail, node) \
	329	for (node = __cds_wfcq_first_blocking(head, tail); \
	330	node != NULL; \
	331	node = __cds_wfcq_next_blocking(head, tail, node))
	332
	333	/*
	334	* __cds_wfcq_for_each_blocking_safe: Iterate over all nodes in a queue,
	335	* without dequeuing them. Safe against deletion.
	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	* @n: struct cds_wfcq_node pointer holding the next pointer (used
	340	* internally).
	341	*
	342	* Content written into each node before enqueue is guaranteed to be
	343	* consistent, but no other memory ordering is ensured.
1fe734e1 MD	344	* Dequeue/splice/iteration mutual exclusion should be ensured by the
1fe734e1 MD	345	* caller.
8ad4ce58 MD	346	*/
	347	#define __cds_wfcq_for_each_blocking_safe(head, tail, node, n) \
	348	for (node = __cds_wfcq_first_blocking(head, tail), \
	349	n = (node ? __cds_wfcq_next_blocking(head, tail, node) : NULL); \
	350	node != NULL; \
	351	node = n, n = (node ? __cds_wfcq_next_blocking(head, tail, node) : NULL))
	352
	353	#ifdef __cplusplus
	354	}
	355	#endif
	356
	357	#endif /* _URCU_WFCQUEUE_H */