[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	((struct cds_wfcq_node *) -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,
};

enum cds_wfcq_state {
	CDS_WFCQ_STATE_LAST =		(1U << 0),
};

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;
};

struct cds_wfcq_head {
	struct cds_wfcq_node node;
	pthread_mutex_t lock;
};

#ifndef __cplusplus
/*
 * The transparent union allows calling functions that work on both
 * struct cds_wfcq_head and struct __cds_wfcq_head on any of those two
 * types.
 */
typedef union {
	struct __cds_wfcq_head *_h;
	struct cds_wfcq_head *h;
} __attribute__((__transparent_union__)) cds_wfcq_head_ptr_t;

/*
 * This static inline is only present for compatibility with C++. It is
 * effect-less in C.
 */
static inline struct __cds_wfcq_head *__cds_wfcq_head_cast(struct __cds_wfcq_head *head)
{
	return head;
}

/*
 * This static inline is only present for compatibility with C++. It is
 * effect-less in C.
 */
static inline struct cds_wfcq_head *cds_wfcq_head_cast(struct cds_wfcq_head *head)
{
	return head;
}
#else /* #ifndef __cplusplus */

/* C++ ignores transparent union. */
typedef union {
	struct __cds_wfcq_head *_h;
	struct cds_wfcq_head *h;
} cds_wfcq_head_ptr_t;

/* C++ ignores transparent union. Requires an explicit conversion. */
static inline cds_wfcq_head_ptr_t __cds_wfcq_head_cast(struct __cds_wfcq_head *head)
{
	cds_wfcq_head_ptr_t ret = { ._h = head };
	return ret;
}
/* C++ ignores transparent union. Requires an explicit conversion. */
static inline cds_wfcq_head_ptr_t cds_wfcq_head_cast(struct cds_wfcq_head *head)
{
	cds_wfcq_head_ptr_t ret = { .h = head };
	return ret;
}
#endif /* #else #ifndef __cplusplus */

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_dequeue_with_state_blocking	\
					_cds_wfcq_dequeue_with_state_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_dequeue_with_state_blocking	\
					___cds_wfcq_dequeue_with_state_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_dequeue_with_state_nonblocking	\
				___cds_wfcq_dequeue_with_state_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
 *
 * Synchronization table:
 *
 * External synchronization techniques described in the API below is
 * required between pairs marked with "X". No external synchronization
 * required between pairs marked with "-".
 *
 * Legend:
 * [1] cds_wfcq_enqueue
 * [2] __cds_wfcq_splice (destination queue)
 * [3] __cds_wfcq_dequeue
 * [4] __cds_wfcq_splice (source queue)
 * [5] __cds_wfcq_first
 * [6] __cds_wfcq_next
 *
 *     [1] [2] [3] [4] [5] [6]
 * [1]  -   -   -   -   -   -
 * [2]  -   -   -   -   -   -
 * [3]  -   -   X   X   X   X
 * [4]  -   -   X   -   X   X
 * [5]  -   -   X   X   -   -
 * [6]  -   -   X   X   -   -
 *
 * 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_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(cds_wfcq_head_ptr_t 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(cds_wfcq_head_ptr_t 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 exclusion 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_dequeue_with_state_blocking: dequeue with state.
 *
 * Same as cds_wfcq_dequeue_blocking, but saves whether dequeueing the
 * last node of the queue into state (CDS_WFCQ_STATE_LAST).
 */
extern struct cds_wfcq_node *cds_wfcq_dequeue_with_state_blocking(
		struct cds_wfcq_head *head,
		struct cds_wfcq_tail *tail,
		int *state);

/*
 * 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 exclusion 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.
 */
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(
		cds_wfcq_head_ptr_t head,
		struct cds_wfcq_tail *tail);

/*
 * __cds_wfcq_dequeue_with_state_blocking: dequeue with state.
 *
 * Same as __cds_wfcq_dequeue_blocking, but saves whether dequeueing the
 * last node of the queue into state (CDS_WFCQ_STATE_LAST).
 */
extern struct cds_wfcq_node *__cds_wfcq_dequeue_with_state_blocking(
		cds_wfcq_head_ptr_t head,
		struct cds_wfcq_tail *tail,
		int *state);

/*
 * __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(
		cds_wfcq_head_ptr_t head,
		struct cds_wfcq_tail *tail);

/*
 * __cds_wfcq_dequeue_with_state_blocking: dequeue with state.
 *
 * Same as __cds_wfcq_dequeue_nonblocking, but saves whether dequeueing
 * the last node of the queue into state (CDS_WFCQ_STATE_LAST).
 */
extern struct cds_wfcq_node *__cds_wfcq_dequeue_with_state_nonblocking(
		cds_wfcq_head_ptr_t head,
		struct cds_wfcq_tail *tail,
		int *state);

/*
 * __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.
 * Mutual exclusion for src_q should be ensured by the caller as
 * specified in the "Synchronisation table".
 * Returns enum cds_wfcq_ret which indicates the state of the src or
 * dest queue. Never returns CDS_WFCQ_RET_WOULDBLOCK.
 */
extern enum cds_wfcq_ret __cds_wfcq_splice_blocking(
		cds_wfcq_head_ptr_t dest_q_head,
		struct cds_wfcq_tail *dest_q_tail,
		cds_wfcq_head_ptr_t 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(
		cds_wfcq_head_ptr_t dest_q_head,
		struct cds_wfcq_tail *dest_q_tail,
		cds_wfcq_head_ptr_t 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()
 *
 * Returns NULL if queue is empty, first node otherwise.
 */
extern struct cds_wfcq_node *__cds_wfcq_first_blocking(
		cds_wfcq_head_ptr_t 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(
		cds_wfcq_head_ptr_t 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()
 *
 * Returns NULL if reached end of queue, non-NULL next queue node
 * otherwise.
 */
extern struct cds_wfcq_node *__cds_wfcq_next_blocking(
		cds_wfcq_head_ptr_t 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(
		cds_wfcq_head_ptr_t 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 or __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 or __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
0b73c819	46	#define CDS_WFCQ_WOULDBLOCK ((struct cds_wfcq_node *) -1UL)
47215721	47
23773356	48	enum cds_wfcq_ret {
f878b49e	49	CDS_WFCQ_RET_WOULDBLOCK = -1,
23773356 MD	50	CDS_WFCQ_RET_DEST_EMPTY = 0,
	51	CDS_WFCQ_RET_DEST_NON_EMPTY = 1,
	52	CDS_WFCQ_RET_SRC_EMPTY = 2,
	53	};
	54
eec791af MD	55	enum cds_wfcq_state {
	56	CDS_WFCQ_STATE_LAST = (1U << 0),
	57	};
	58
8ad4ce58 MD	59	struct cds_wfcq_node {
	60	struct cds_wfcq_node *next;
	61	};
	62
	63	/*
	64	* Do not put head and tail on the same cache-line if concurrent
	65	* enqueue/dequeue are expected from many CPUs. This eliminates
	66	* false-sharing between enqueue and dequeue.
	67	*/
f637f191 MD	68	struct __cds_wfcq_head {
	69	struct cds_wfcq_node node;
	70	};
	71
8ad4ce58 MD	72	struct cds_wfcq_head {
	73	struct cds_wfcq_node node;
	74	pthread_mutex_t lock;
	75	};
	76
4d0d7cbc	77	#ifndef __cplusplus
f637f191 MD	78	/*
	79	* The transparent union allows calling functions that work on both
	80	* struct cds_wfcq_head and struct __cds_wfcq_head on any of those two
	81	* types.
	82	*/
5135c0fd	83	typedef union {
f637f191 MD	84	struct __cds_wfcq_head *_h;
f637f191 MD	85	struct cds_wfcq_head *h;
5135c0fd	86	} __attribute__((__transparent_union__)) cds_wfcq_head_ptr_t;
f637f191	87
4d0d7cbc MD	88	/*
	89	* This static inline is only present for compatibility with C++. It is
	90	* effect-less in C.
	91	*/
	92	static inline struct __cds_wfcq_head __cds_wfcq_head_cast(struct __cds_wfcq_head head)
	93	{
	94	return head;
	95	}
	96
	97	/*
	98	* This static inline is only present for compatibility with C++. It is
	99	* effect-less in C.
	100	*/
	101	static inline struct cds_wfcq_head cds_wfcq_head_cast(struct cds_wfcq_head head)
	102	{
	103	return head;
	104	}
	105	#else /* #ifndef __cplusplus */
	106
	107	/* C++ ignores transparent union. */
	108	typedef union {
	109	struct __cds_wfcq_head *_h;
	110	struct cds_wfcq_head *h;
	111	} cds_wfcq_head_ptr_t;
	112
	113	/* C++ ignores transparent union. Requires an explicit conversion. */
	114	static inline cds_wfcq_head_ptr_t __cds_wfcq_head_cast(struct __cds_wfcq_head *head)
	115	{
	116	cds_wfcq_head_ptr_t ret = { ._h = head };
	117	return ret;
	118	}
	119	/* C++ ignores transparent union. Requires an explicit conversion. */
	120	static inline cds_wfcq_head_ptr_t cds_wfcq_head_cast(struct cds_wfcq_head *head)
	121	{
	122	cds_wfcq_head_ptr_t ret = { .h = head };
	123	return ret;
	124	}
	125	#endif /* #else #ifndef __cplusplus */
	126
8ad4ce58 MD	127	struct cds_wfcq_tail {
	128	struct cds_wfcq_node *p;
	129	};
	130
	131	#ifdef _LGPL_SOURCE
	132
	133	#include <urcu/static/wfcqueue.h>
	134
	135	#define cds_wfcq_node_init _cds_wfcq_node_init
	136	#define cds_wfcq_init _cds_wfcq_init
	137	#define cds_wfcq_empty _cds_wfcq_empty
	138	#define cds_wfcq_enqueue _cds_wfcq_enqueue
	139
	140	/* Dequeue locking */
	141	#define cds_wfcq_dequeue_lock _cds_wfcq_dequeue_lock
	142	#define cds_wfcq_dequeue_unlock _cds_wfcq_dequeue_unlock
	143
	144	/* Locking performed within cds_wfcq calls. */
	145	#define cds_wfcq_dequeue_blocking _cds_wfcq_dequeue_blocking
eec791af MD	146	#define cds_wfcq_dequeue_with_state_blocking \
eec791af MD	147	_cds_wfcq_dequeue_with_state_blocking
8ad4ce58 MD	148	#define cds_wfcq_splice_blocking _cds_wfcq_splice_blocking
	149	#define cds_wfcq_first_blocking _cds_wfcq_first_blocking
	150	#define cds_wfcq_next_blocking _cds_wfcq_next_blocking
	151
	152	/* Locking ensured by caller by holding cds_wfcq_dequeue_lock() */
	153	#define __cds_wfcq_dequeue_blocking ___cds_wfcq_dequeue_blocking
eec791af MD	154	#define __cds_wfcq_dequeue_with_state_blocking \
eec791af MD	155	___cds_wfcq_dequeue_with_state_blocking
8ad4ce58 MD	156	#define __cds_wfcq_splice_blocking ___cds_wfcq_splice_blocking
	157	#define __cds_wfcq_first_blocking ___cds_wfcq_first_blocking
	158	#define __cds_wfcq_next_blocking ___cds_wfcq_next_blocking
	159
47215721 MD	160	/*
	161	* Locking ensured by caller by holding cds_wfcq_dequeue_lock().
	162	* Non-blocking: deque, first, next return CDS_WFCQ_WOULDBLOCK if they
	163	* need to block. splice returns nonzero if it needs to block.
	164	*/
	165	#define __cds_wfcq_dequeue_nonblocking ___cds_wfcq_dequeue_nonblocking
eec791af MD	166	#define __cds_wfcq_dequeue_with_state_nonblocking \
eec791af MD	167	___cds_wfcq_dequeue_with_state_nonblocking
47215721 MD	168	#define __cds_wfcq_splice_nonblocking ___cds_wfcq_splice_nonblocking
	169	#define __cds_wfcq_first_nonblocking ___cds_wfcq_first_nonblocking
	170	#define __cds_wfcq_next_nonblocking ___cds_wfcq_next_nonblocking
	171
8ad4ce58 MD	172	#else /* !_LGPL_SOURCE */
	173
	174	/*
	175	* Mutual exclusion of cds_wfcq_* / __cds_wfcq_* API
	176	*
f878b49e MD	177	* Synchronization table:
	178	*
	179	* External synchronization techniques described in the API below is
	180	* required between pairs marked with "X". No external synchronization
	181	* required between pairs marked with "-".
	182	*
	183	* Legend:
	184	* [1] cds_wfcq_enqueue
	185	* [2] __cds_wfcq_splice (destination queue)
	186	* [3] __cds_wfcq_dequeue
	187	* [4] __cds_wfcq_splice (source queue)
	188	* [5] __cds_wfcq_first
	189	* [6] __cds_wfcq_next
	190	*
	191	* [1] [2] [3] [4] [5] [6]
	192	* [1] - - - - - -
	193	* [2] - - - - - -
	194	* [3] - - X X X X
	195	* [4] - - X - X X
	196	* [5] - - X X - -
	197	* [6] - - X X - -
	198	*
8ad4ce58 MD	199	* Mutual exclusion can be ensured by holding cds_wfcq_dequeue_lock().
	200	*
	201	* For convenience, cds_wfcq_dequeue_blocking() and
	202	* cds_wfcq_splice_blocking() hold the dequeue lock.
1fe734e1 MD	203	*
	204	* Besides locking, mutual exclusion of dequeue, splice and iteration
	205	* can be ensured by performing all of those operations from a single
	206	* thread, without requiring any lock.
8ad4ce58 MD	207	*/
	208
	209	/*
	210	* cds_wfcq_node_init: initialize wait-free queue node.
	211	*/
	212	extern void cds_wfcq_node_init(struct cds_wfcq_node *node);
	213
	214	/*
	215	* cds_wfcq_init: initialize wait-free queue.
	216	*/
	217	extern void cds_wfcq_init(struct cds_wfcq_head *head,
	218	struct cds_wfcq_tail *tail);
	219
f637f191 MD	220	/*
	221	* __cds_wfcq_init: initialize wait-free queue.
	222	*/
	223	extern void __cds_wfcq_init(struct __cds_wfcq_head *head,
	224	struct cds_wfcq_tail *tail);
	225
8ad4ce58 MD	226	/*
	227	* cds_wfcq_empty: return whether wait-free queue is empty.
	228	*
	229	* No memory barrier is issued. No mutual exclusion is required.
	230	*/
f637f191	231	extern bool cds_wfcq_empty(cds_wfcq_head_ptr_t head,
8ad4ce58 MD	232	struct cds_wfcq_tail *tail);
	233
	234	/*
	235	* cds_wfcq_dequeue_lock: take the dequeue mutual exclusion lock.
	236	*/
	237	extern void cds_wfcq_dequeue_lock(struct cds_wfcq_head *head,
	238	struct cds_wfcq_tail *tail);
	239
	240	/*
	241	* cds_wfcq_dequeue_unlock: release the dequeue mutual exclusion lock.
	242	*/
	243	extern void cds_wfcq_dequeue_unlock(struct cds_wfcq_head *head,
	244	struct cds_wfcq_tail *tail);
	245
	246	/*
	247	* cds_wfcq_enqueue: enqueue a node into a wait-free queue.
	248	*
	249	* Issues a full memory barrier before enqueue. No mutual exclusion is
	250	* required.
23773356 MD	251	*
	252	* Returns false if the queue was empty prior to adding the node.
	253	* Returns true otherwise.
8ad4ce58	254	*/
f637f191	255	extern bool cds_wfcq_enqueue(cds_wfcq_head_ptr_t head,
8ad4ce58 MD	256	struct cds_wfcq_tail *tail,
	257	struct cds_wfcq_node *node);
	258
	259	/*
	260	* cds_wfcq_dequeue_blocking: dequeue a node from a wait-free queue.
	261	*
	262	* Content written into the node before enqueue is guaranteed to be
	263	* consistent, but no other memory ordering is ensured.
	264	* It is valid to reuse and free a dequeued node immediately.
ffa11a18	265	* Mutual exclusion with cds_wfcq_dequeue_blocking and dequeue lock is
1fe734e1	266	* ensured.
8ad4ce58 MD	267	*/
	268	extern struct cds_wfcq_node *cds_wfcq_dequeue_blocking(
	269	struct cds_wfcq_head *head,
	270	struct cds_wfcq_tail *tail);
	271
eec791af MD	272	/*
	273	* cds_wfcq_dequeue_with_state_blocking: dequeue with state.
	274	*
	275	* Same as cds_wfcq_dequeue_blocking, but saves whether dequeueing the
	276	* last node of the queue into state (CDS_WFCQ_STATE_LAST).
	277	*/
	278	extern struct cds_wfcq_node *cds_wfcq_dequeue_with_state_blocking(
	279	struct cds_wfcq_head *head,
	280	struct cds_wfcq_tail *tail,
	281	int *state);
	282
8ad4ce58 MD	283	/*
	284	* cds_wfcq_splice_blocking: enqueue all src_q nodes at the end of dest_q.
	285	*
	286	* Dequeue all nodes from src_q.
	287	* dest_q must be already initialized.
	288	* Content written into the node before enqueue is guaranteed to be
	289	* consistent, but no other memory ordering is ensured.
ffa11a18	290	* Mutual exclusion with cds_wfcq_dequeue_blocking and dequeue lock is
1fe734e1	291	* ensured.
23773356 MD	292	*
23773356 MD	293	* Returns enum cds_wfcq_ret which indicates the state of the src or
b94aaf6f	294	* dest queue.
8ad4ce58	295	*/
23773356	296	extern enum cds_wfcq_ret cds_wfcq_splice_blocking(
8ad4ce58 MD	297	struct cds_wfcq_head *dest_q_head,
	298	struct cds_wfcq_tail *dest_q_tail,
	299	struct cds_wfcq_head *src_q_head,
	300	struct cds_wfcq_tail *src_q_tail);
	301
	302	/*
47215721	303	* __cds_wfcq_dequeue_blocking: dequeue a node from a wait-free queue.
8ad4ce58 MD	304	*
	305	* Content written into the node before enqueue is guaranteed to be
	306	* consistent, but no other memory ordering is ensured.
	307	* It is valid to reuse and free a dequeued node immediately.
1fe734e1 MD	308	* Dequeue/splice/iteration mutual exclusion should be ensured by the
1fe734e1 MD	309	* caller.
8ad4ce58 MD	310	*/
8ad4ce58 MD	311	extern struct cds_wfcq_node *__cds_wfcq_dequeue_blocking(
f637f191	312	cds_wfcq_head_ptr_t head,
8ad4ce58 MD	313	struct cds_wfcq_tail *tail);
8ad4ce58 MD	314
eec791af MD	315	/*
	316	* __cds_wfcq_dequeue_with_state_blocking: dequeue with state.
	317	*
	318	* Same as __cds_wfcq_dequeue_blocking, but saves whether dequeueing the
	319	* last node of the queue into state (CDS_WFCQ_STATE_LAST).
	320	*/
	321	extern struct cds_wfcq_node *__cds_wfcq_dequeue_with_state_blocking(
f637f191	322	cds_wfcq_head_ptr_t head,
eec791af MD	323	struct cds_wfcq_tail *tail,
	324	int *state);
	325
47215721 MD	326	/*
	327	* __cds_wfcq_dequeue_nonblocking: dequeue a node from a wait-free queue.
	328	*
	329	* Same as __cds_wfcq_dequeue_blocking, but returns CDS_WFCQ_WOULDBLOCK
	330	* if it needs to block.
	331	*/
	332	extern struct cds_wfcq_node *__cds_wfcq_dequeue_nonblocking(
f637f191	333	cds_wfcq_head_ptr_t head,
47215721 MD	334	struct cds_wfcq_tail *tail);
47215721 MD	335
eec791af MD	336	/*
	337	* __cds_wfcq_dequeue_with_state_blocking: dequeue with state.
	338	*
	339	* Same as __cds_wfcq_dequeue_nonblocking, but saves whether dequeueing
	340	* the last node of the queue into state (CDS_WFCQ_STATE_LAST).
	341	*/
	342	extern struct cds_wfcq_node *__cds_wfcq_dequeue_with_state_nonblocking(
f637f191	343	cds_wfcq_head_ptr_t head,
eec791af MD	344	struct cds_wfcq_tail *tail,
	345	int *state);
	346
8ad4ce58 MD	347	/*
	348	* __cds_wfcq_splice_blocking: enqueue all src_q nodes at the end of dest_q.
	349	*
	350	* Dequeue all nodes from src_q.
	351	* dest_q must be already initialized.
f878b49e MD	352	* Mutual exclusion for src_q should be ensured by the caller as
f878b49e MD	353	* specified in the "Synchronisation table".
23773356	354	* Returns enum cds_wfcq_ret which indicates the state of the src or
f878b49e	355	* dest queue. Never returns CDS_WFCQ_RET_WOULDBLOCK.
8ad4ce58	356	*/
23773356	357	extern enum cds_wfcq_ret __cds_wfcq_splice_blocking(
f637f191	358	cds_wfcq_head_ptr_t dest_q_head,
8ad4ce58	359	struct cds_wfcq_tail *dest_q_tail,
f637f191	360	cds_wfcq_head_ptr_t src_q_head,
8ad4ce58 MD	361	struct cds_wfcq_tail *src_q_tail);
8ad4ce58 MD	362
47215721 MD	363	/*
	364	* __cds_wfcq_splice_nonblocking: enqueue all src_q nodes at the end of dest_q.
	365	*
23773356 MD	366	* Same as __cds_wfcq_splice_blocking, but returns
23773356 MD	367	* CDS_WFCQ_RET_WOULDBLOCK if it needs to block.
47215721	368	*/
23773356	369	extern enum cds_wfcq_ret __cds_wfcq_splice_nonblocking(
f637f191	370	cds_wfcq_head_ptr_t dest_q_head,
47215721	371	struct cds_wfcq_tail *dest_q_tail,
f637f191	372	cds_wfcq_head_ptr_t src_q_head,
47215721 MD	373	struct cds_wfcq_tail *src_q_tail);
47215721 MD	374
8ad4ce58 MD	375	/*
	376	* __cds_wfcq_first_blocking: get first node of a queue, without dequeuing.
	377	*
	378	* Content written into the node before enqueue is guaranteed to be
	379	* consistent, but no other memory ordering is ensured.
1fe734e1 MD	380	* Dequeue/splice/iteration mutual exclusion should be ensured by the
1fe734e1 MD	381	* caller.
f94061a3 MD	382	*
	383	* Used by for-like iteration macros:
	384	* __cds_wfcq_for_each_blocking()
	385	* __cds_wfcq_for_each_blocking_safe()
131a29a6 MD	386	*
131a29a6 MD	387	* Returns NULL if queue is empty, first node otherwise.
8ad4ce58 MD	388	*/
8ad4ce58 MD	389	extern struct cds_wfcq_node *__cds_wfcq_first_blocking(
f637f191	390	cds_wfcq_head_ptr_t head,
8ad4ce58 MD	391	struct cds_wfcq_tail *tail);
8ad4ce58 MD	392
47215721 MD	393	/*
	394	* __cds_wfcq_first_nonblocking: get first node of a queue, without dequeuing.
	395	*
	396	* Same as __cds_wfcq_first_blocking, but returns CDS_WFCQ_WOULDBLOCK if
	397	* it needs to block.
	398	*/
	399	extern struct cds_wfcq_node *__cds_wfcq_first_nonblocking(
f637f191	400	cds_wfcq_head_ptr_t head,
47215721 MD	401	struct cds_wfcq_tail *tail);
47215721 MD	402
8ad4ce58 MD	403	/*
	404	* __cds_wfcq_next_blocking: get next node of a queue, without dequeuing.
	405	*
	406	* Content written into the node before enqueue is guaranteed to be
	407	* consistent, but no other memory ordering is ensured.
1fe734e1 MD	408	* Dequeue/splice/iteration mutual exclusion should be ensured by the
1fe734e1 MD	409	* caller.
f94061a3 MD	410	*
	411	* Used by for-like iteration macros:
	412	* __cds_wfcq_for_each_blocking()
	413	* __cds_wfcq_for_each_blocking_safe()
131a29a6 MD	414	*
	415	* Returns NULL if reached end of queue, non-NULL next queue node
	416	* otherwise.
8ad4ce58 MD	417	*/
8ad4ce58 MD	418	extern struct cds_wfcq_node *__cds_wfcq_next_blocking(
f637f191	419	cds_wfcq_head_ptr_t head,
8ad4ce58 MD	420	struct cds_wfcq_tail *tail,
	421	struct cds_wfcq_node *node);
	422
47215721 MD	423	/*
	424	* __cds_wfcq_next_blocking: get next node of a queue, without dequeuing.
	425	*
	426	* Same as __cds_wfcq_next_blocking, but returns CDS_WFCQ_WOULDBLOCK if
	427	* it needs to block.
	428	*/
	429	extern struct cds_wfcq_node *__cds_wfcq_next_nonblocking(
f637f191	430	cds_wfcq_head_ptr_t head,
47215721 MD	431	struct cds_wfcq_tail *tail,
	432	struct cds_wfcq_node *node);
	433
8ad4ce58 MD	434	#endif /* !_LGPL_SOURCE */
	435
	436	/*
	437	* __cds_wfcq_for_each_blocking: Iterate over all nodes in a queue,
	438	* without dequeuing them.
f637f191	439	* @head: head of the queue (struct cds_wfcq_head or __cds_wfcq_head pointer).
8ad4ce58 MD	440	* @tail: tail of the queue (struct cds_wfcq_tail pointer).
	441	* @node: iterator on the queue (struct cds_wfcq_node pointer).
	442	*
	443	* Content written into each node before enqueue is guaranteed to be
	444	* consistent, but no other memory ordering is ensured.
1fe734e1 MD	445	* Dequeue/splice/iteration mutual exclusion should be ensured by the
1fe734e1 MD	446	* caller.
8ad4ce58 MD	447	*/
	448	#define __cds_wfcq_for_each_blocking(head, tail, node) \
	449	for (node = __cds_wfcq_first_blocking(head, tail); \
	450	node != NULL; \
	451	node = __cds_wfcq_next_blocking(head, tail, node))
	452
	453	/*
	454	* __cds_wfcq_for_each_blocking_safe: Iterate over all nodes in a queue,
	455	* without dequeuing them. Safe against deletion.
f637f191	456	* @head: head of the queue (struct cds_wfcq_head or __cds_wfcq_head pointer).
8ad4ce58 MD	457	* @tail: tail of the queue (struct cds_wfcq_tail pointer).
	458	* @node: iterator on the queue (struct cds_wfcq_node pointer).
	459	* @n: struct cds_wfcq_node pointer holding the next pointer (used
	460	* internally).
	461	*
	462	* Content written into each node before enqueue is guaranteed to be
	463	* consistent, but no other memory ordering is ensured.
1fe734e1 MD	464	* Dequeue/splice/iteration mutual exclusion should be ensured by the
1fe734e1 MD	465	* caller.
8ad4ce58 MD	466	*/
	467	#define __cds_wfcq_for_each_blocking_safe(head, tail, node, n) \
	468	for (node = __cds_wfcq_first_blocking(head, tail), \
	469	n = (node ? __cds_wfcq_next_blocking(head, tail, node) : NULL); \
	470	node != NULL; \
	471	node = n, n = (node ? __cds_wfcq_next_blocking(head, tail, node) : NULL))
	472
	473	#ifdef __cplusplus
	474	}
	475	#endif
	476
	477	#endif /* _URCU_WFCQUEUE_H */