[urcu.git] / include / 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_init			___cds_wfcq_init
#define cds_wfcq_destroy		_cds_wfcq_destroy
#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. Pair with
 * cds_wfcq_destroy().
 */
extern void cds_wfcq_init(struct cds_wfcq_head *head,
		struct cds_wfcq_tail *tail);

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

/*
 * __cds_wfcq_init: initialize wait-free queue (without lock). Don't
 * pair with any destroy function.
 */
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
b4edfa81	137	#define __cds_wfcq_init ___cds_wfcq_init
200d100e	138	#define cds_wfcq_destroy _cds_wfcq_destroy
8ad4ce58 MD	139	#define cds_wfcq_empty _cds_wfcq_empty
	140	#define cds_wfcq_enqueue _cds_wfcq_enqueue
	141
	142	/* Dequeue locking */
	143	#define cds_wfcq_dequeue_lock _cds_wfcq_dequeue_lock
	144	#define cds_wfcq_dequeue_unlock _cds_wfcq_dequeue_unlock
	145
	146	/* Locking performed within cds_wfcq calls. */
	147	#define cds_wfcq_dequeue_blocking _cds_wfcq_dequeue_blocking
eec791af MD	148	#define cds_wfcq_dequeue_with_state_blocking \
eec791af MD	149	_cds_wfcq_dequeue_with_state_blocking
8ad4ce58 MD	150	#define cds_wfcq_splice_blocking _cds_wfcq_splice_blocking
	151	#define cds_wfcq_first_blocking _cds_wfcq_first_blocking
	152	#define cds_wfcq_next_blocking _cds_wfcq_next_blocking
	153
	154	/* Locking ensured by caller by holding cds_wfcq_dequeue_lock() */
	155	#define __cds_wfcq_dequeue_blocking ___cds_wfcq_dequeue_blocking
eec791af MD	156	#define __cds_wfcq_dequeue_with_state_blocking \
eec791af MD	157	___cds_wfcq_dequeue_with_state_blocking
8ad4ce58 MD	158	#define __cds_wfcq_splice_blocking ___cds_wfcq_splice_blocking
	159	#define __cds_wfcq_first_blocking ___cds_wfcq_first_blocking
	160	#define __cds_wfcq_next_blocking ___cds_wfcq_next_blocking
	161
47215721 MD	162	/*
	163	* Locking ensured by caller by holding cds_wfcq_dequeue_lock().
	164	* Non-blocking: deque, first, next return CDS_WFCQ_WOULDBLOCK if they
	165	* need to block. splice returns nonzero if it needs to block.
	166	*/
	167	#define __cds_wfcq_dequeue_nonblocking ___cds_wfcq_dequeue_nonblocking
eec791af MD	168	#define __cds_wfcq_dequeue_with_state_nonblocking \
eec791af MD	169	___cds_wfcq_dequeue_with_state_nonblocking
47215721 MD	170	#define __cds_wfcq_splice_nonblocking ___cds_wfcq_splice_nonblocking
	171	#define __cds_wfcq_first_nonblocking ___cds_wfcq_first_nonblocking
	172	#define __cds_wfcq_next_nonblocking ___cds_wfcq_next_nonblocking
	173
8ad4ce58 MD	174	#else /* !_LGPL_SOURCE */
	175
	176	/*
	177	* Mutual exclusion of cds_wfcq_* / __cds_wfcq_* API
	178	*
f878b49e MD	179	* Synchronization table:
	180	*
	181	* External synchronization techniques described in the API below is
	182	* required between pairs marked with "X". No external synchronization
	183	* required between pairs marked with "-".
	184	*
	185	* Legend:
	186	* [1] cds_wfcq_enqueue
	187	* [2] __cds_wfcq_splice (destination queue)
	188	* [3] __cds_wfcq_dequeue
	189	* [4] __cds_wfcq_splice (source queue)
	190	* [5] __cds_wfcq_first
	191	* [6] __cds_wfcq_next
	192	*
	193	* [1] [2] [3] [4] [5] [6]
	194	* [1] - - - - - -
	195	* [2] - - - - - -
	196	* [3] - - X X X X
	197	* [4] - - X - X X
	198	* [5] - - X X - -
	199	* [6] - - X X - -
	200	*
8ad4ce58 MD	201	* Mutual exclusion can be ensured by holding cds_wfcq_dequeue_lock().
	202	*
	203	* For convenience, cds_wfcq_dequeue_blocking() and
	204	* cds_wfcq_splice_blocking() hold the dequeue lock.
1fe734e1 MD	205	*
	206	* Besides locking, mutual exclusion of dequeue, splice and iteration
	207	* can be ensured by performing all of those operations from a single
	208	* thread, without requiring any lock.
8ad4ce58 MD	209	*/
	210
	211	/*
	212	* cds_wfcq_node_init: initialize wait-free queue node.
	213	*/
	214	extern void cds_wfcq_node_init(struct cds_wfcq_node *node);
	215
	216	/*
200d100e MD	217	* cds_wfcq_init: initialize wait-free queue. Pair with
200d100e MD	218	* cds_wfcq_destroy().
8ad4ce58 MD	219	*/
	220	extern void cds_wfcq_init(struct cds_wfcq_head *head,
	221	struct cds_wfcq_tail *tail);
	222
f637f191	223	/*
200d100e MD	224	* cds_wfcq_destroy: destroy wait-free queue. Pair with
	225	* cds_wfcq_init().
	226	*/
	227	extern void cds_wfcq_destroy(struct cds_wfcq_head *head,
	228	struct cds_wfcq_tail *tail);
	229
	230	/*
	231	* __cds_wfcq_init: initialize wait-free queue (without lock). Don't
	232	* pair with any destroy function.
f637f191 MD	233	*/
	234	extern void __cds_wfcq_init(struct __cds_wfcq_head *head,
	235	struct cds_wfcq_tail *tail);
	236
8ad4ce58 MD	237	/*
	238	* cds_wfcq_empty: return whether wait-free queue is empty.
	239	*
	240	* No memory barrier is issued. No mutual exclusion is required.
	241	*/
f637f191	242	extern bool cds_wfcq_empty(cds_wfcq_head_ptr_t head,
8ad4ce58 MD	243	struct cds_wfcq_tail *tail);
	244
	245	/*
	246	* cds_wfcq_dequeue_lock: take the dequeue mutual exclusion lock.
	247	*/
	248	extern void cds_wfcq_dequeue_lock(struct cds_wfcq_head *head,
	249	struct cds_wfcq_tail *tail);
	250
	251	/*
	252	* cds_wfcq_dequeue_unlock: release the dequeue mutual exclusion lock.
	253	*/
	254	extern void cds_wfcq_dequeue_unlock(struct cds_wfcq_head *head,
	255	struct cds_wfcq_tail *tail);
	256
	257	/*
	258	* cds_wfcq_enqueue: enqueue a node into a wait-free queue.
	259	*
	260	* Issues a full memory barrier before enqueue. No mutual exclusion is
	261	* required.
23773356 MD	262	*
	263	* Returns false if the queue was empty prior to adding the node.
	264	* Returns true otherwise.
8ad4ce58	265	*/
f637f191	266	extern bool cds_wfcq_enqueue(cds_wfcq_head_ptr_t head,
8ad4ce58 MD	267	struct cds_wfcq_tail *tail,
	268	struct cds_wfcq_node *node);
	269
	270	/*
	271	* cds_wfcq_dequeue_blocking: dequeue a node from a wait-free queue.
	272	*
	273	* Content written into the node before enqueue is guaranteed to be
	274	* consistent, but no other memory ordering is ensured.
	275	* It is valid to reuse and free a dequeued node immediately.
ffa11a18	276	* Mutual exclusion with cds_wfcq_dequeue_blocking and dequeue lock is
1fe734e1	277	* ensured.
8ad4ce58 MD	278	*/
	279	extern struct cds_wfcq_node *cds_wfcq_dequeue_blocking(
	280	struct cds_wfcq_head *head,
	281	struct cds_wfcq_tail *tail);
	282
eec791af MD	283	/*
	284	* cds_wfcq_dequeue_with_state_blocking: dequeue with state.
	285	*
	286	* Same as cds_wfcq_dequeue_blocking, but saves whether dequeueing the
	287	* last node of the queue into state (CDS_WFCQ_STATE_LAST).
	288	*/
	289	extern struct cds_wfcq_node *cds_wfcq_dequeue_with_state_blocking(
	290	struct cds_wfcq_head *head,
	291	struct cds_wfcq_tail *tail,
	292	int *state);
	293
8ad4ce58 MD	294	/*
	295	* cds_wfcq_splice_blocking: enqueue all src_q nodes at the end of dest_q.
	296	*
	297	* Dequeue all nodes from src_q.
	298	* dest_q must be already initialized.
	299	* Content written into the node before enqueue is guaranteed to be
	300	* consistent, but no other memory ordering is ensured.
ffa11a18	301	* Mutual exclusion with cds_wfcq_dequeue_blocking and dequeue lock is
1fe734e1	302	* ensured.
23773356 MD	303	*
23773356 MD	304	* Returns enum cds_wfcq_ret which indicates the state of the src or
b94aaf6f	305	* dest queue.
8ad4ce58	306	*/
23773356	307	extern enum cds_wfcq_ret cds_wfcq_splice_blocking(
8ad4ce58 MD	308	struct cds_wfcq_head *dest_q_head,
	309	struct cds_wfcq_tail *dest_q_tail,
	310	struct cds_wfcq_head *src_q_head,
	311	struct cds_wfcq_tail *src_q_tail);
	312
	313	/*
47215721	314	* __cds_wfcq_dequeue_blocking: dequeue a node from a wait-free queue.
8ad4ce58 MD	315	*
	316	* Content written into the node before enqueue is guaranteed to be
	317	* consistent, but no other memory ordering is ensured.
	318	* It is valid to reuse and free a dequeued node immediately.
1fe734e1 MD	319	* Dequeue/splice/iteration mutual exclusion should be ensured by the
1fe734e1 MD	320	* caller.
8ad4ce58 MD	321	*/
8ad4ce58 MD	322	extern struct cds_wfcq_node *__cds_wfcq_dequeue_blocking(
f637f191	323	cds_wfcq_head_ptr_t head,
8ad4ce58 MD	324	struct cds_wfcq_tail *tail);
8ad4ce58 MD	325
eec791af MD	326	/*
	327	* __cds_wfcq_dequeue_with_state_blocking: dequeue with state.
	328	*
	329	* Same as __cds_wfcq_dequeue_blocking, but saves whether dequeueing the
	330	* last node of the queue into state (CDS_WFCQ_STATE_LAST).
	331	*/
	332	extern struct cds_wfcq_node *__cds_wfcq_dequeue_with_state_blocking(
f637f191	333	cds_wfcq_head_ptr_t head,
eec791af MD	334	struct cds_wfcq_tail *tail,
	335	int *state);
	336
47215721 MD	337	/*
	338	* __cds_wfcq_dequeue_nonblocking: dequeue a node from a wait-free queue.
	339	*
	340	* Same as __cds_wfcq_dequeue_blocking, but returns CDS_WFCQ_WOULDBLOCK
	341	* if it needs to block.
	342	*/
	343	extern struct cds_wfcq_node *__cds_wfcq_dequeue_nonblocking(
f637f191	344	cds_wfcq_head_ptr_t head,
47215721 MD	345	struct cds_wfcq_tail *tail);
47215721 MD	346
eec791af MD	347	/*
	348	* __cds_wfcq_dequeue_with_state_blocking: dequeue with state.
	349	*
	350	* Same as __cds_wfcq_dequeue_nonblocking, but saves whether dequeueing
	351	* the last node of the queue into state (CDS_WFCQ_STATE_LAST).
	352	*/
	353	extern struct cds_wfcq_node *__cds_wfcq_dequeue_with_state_nonblocking(
f637f191	354	cds_wfcq_head_ptr_t head,
eec791af MD	355	struct cds_wfcq_tail *tail,
	356	int *state);
	357
8ad4ce58 MD	358	/*
	359	* __cds_wfcq_splice_blocking: enqueue all src_q nodes at the end of dest_q.
	360	*
	361	* Dequeue all nodes from src_q.
	362	* dest_q must be already initialized.
f878b49e MD	363	* Mutual exclusion for src_q should be ensured by the caller as
f878b49e MD	364	* specified in the "Synchronisation table".
23773356	365	* Returns enum cds_wfcq_ret which indicates the state of the src or
f878b49e	366	* dest queue. Never returns CDS_WFCQ_RET_WOULDBLOCK.
8ad4ce58	367	*/
23773356	368	extern enum cds_wfcq_ret __cds_wfcq_splice_blocking(
f637f191	369	cds_wfcq_head_ptr_t dest_q_head,
8ad4ce58	370	struct cds_wfcq_tail *dest_q_tail,
f637f191	371	cds_wfcq_head_ptr_t src_q_head,
8ad4ce58 MD	372	struct cds_wfcq_tail *src_q_tail);
8ad4ce58 MD	373
47215721 MD	374	/*
	375	* __cds_wfcq_splice_nonblocking: enqueue all src_q nodes at the end of dest_q.
	376	*
23773356 MD	377	* Same as __cds_wfcq_splice_blocking, but returns
23773356 MD	378	* CDS_WFCQ_RET_WOULDBLOCK if it needs to block.
47215721	379	*/
23773356	380	extern enum cds_wfcq_ret __cds_wfcq_splice_nonblocking(
f637f191	381	cds_wfcq_head_ptr_t dest_q_head,
47215721	382	struct cds_wfcq_tail *dest_q_tail,
f637f191	383	cds_wfcq_head_ptr_t src_q_head,
47215721 MD	384	struct cds_wfcq_tail *src_q_tail);
47215721 MD	385
8ad4ce58 MD	386	/*
	387	* __cds_wfcq_first_blocking: get first node of a queue, without dequeuing.
	388	*
	389	* Content written into the node before enqueue is guaranteed to be
	390	* consistent, but no other memory ordering is ensured.
1fe734e1 MD	391	* Dequeue/splice/iteration mutual exclusion should be ensured by the
1fe734e1 MD	392	* caller.
f94061a3 MD	393	*
	394	* Used by for-like iteration macros:
	395	* __cds_wfcq_for_each_blocking()
	396	* __cds_wfcq_for_each_blocking_safe()
131a29a6 MD	397	*
131a29a6 MD	398	* Returns NULL if queue is empty, first node otherwise.
8ad4ce58 MD	399	*/
8ad4ce58 MD	400	extern struct cds_wfcq_node *__cds_wfcq_first_blocking(
f637f191	401	cds_wfcq_head_ptr_t head,
8ad4ce58 MD	402	struct cds_wfcq_tail *tail);
8ad4ce58 MD	403
47215721 MD	404	/*
	405	* __cds_wfcq_first_nonblocking: get first node of a queue, without dequeuing.
	406	*
	407	* Same as __cds_wfcq_first_blocking, but returns CDS_WFCQ_WOULDBLOCK if
	408	* it needs to block.
	409	*/
	410	extern struct cds_wfcq_node *__cds_wfcq_first_nonblocking(
f637f191	411	cds_wfcq_head_ptr_t head,
47215721 MD	412	struct cds_wfcq_tail *tail);
47215721 MD	413
8ad4ce58 MD	414	/*
	415	* __cds_wfcq_next_blocking: get next node of a queue, without dequeuing.
	416	*
	417	* Content written into the node before enqueue is guaranteed to be
	418	* consistent, but no other memory ordering is ensured.
1fe734e1 MD	419	* Dequeue/splice/iteration mutual exclusion should be ensured by the
1fe734e1 MD	420	* caller.
f94061a3 MD	421	*
	422	* Used by for-like iteration macros:
	423	* __cds_wfcq_for_each_blocking()
	424	* __cds_wfcq_for_each_blocking_safe()
131a29a6 MD	425	*
	426	* Returns NULL if reached end of queue, non-NULL next queue node
	427	* otherwise.
8ad4ce58 MD	428	*/
8ad4ce58 MD	429	extern struct cds_wfcq_node *__cds_wfcq_next_blocking(
f637f191	430	cds_wfcq_head_ptr_t head,
8ad4ce58 MD	431	struct cds_wfcq_tail *tail,
	432	struct cds_wfcq_node *node);
	433
47215721 MD	434	/*
	435	* __cds_wfcq_next_blocking: get next node of a queue, without dequeuing.
	436	*
	437	* Same as __cds_wfcq_next_blocking, but returns CDS_WFCQ_WOULDBLOCK if
	438	* it needs to block.
	439	*/
	440	extern struct cds_wfcq_node *__cds_wfcq_next_nonblocking(
f637f191	441	cds_wfcq_head_ptr_t head,
47215721 MD	442	struct cds_wfcq_tail *tail,
	443	struct cds_wfcq_node *node);
	444
8ad4ce58 MD	445	#endif /* !_LGPL_SOURCE */
	446
	447	/*
	448	* __cds_wfcq_for_each_blocking: Iterate over all nodes in a queue,
	449	* without dequeuing them.
f637f191	450	* @head: head of the queue (struct cds_wfcq_head or __cds_wfcq_head pointer).
8ad4ce58 MD	451	* @tail: tail of the queue (struct cds_wfcq_tail pointer).
	452	* @node: iterator on the queue (struct cds_wfcq_node pointer).
	453	*
	454	* Content written into each node before enqueue is guaranteed to be
	455	* consistent, but no other memory ordering is ensured.
1fe734e1 MD	456	* Dequeue/splice/iteration mutual exclusion should be ensured by the
1fe734e1 MD	457	* caller.
8ad4ce58 MD	458	*/
	459	#define __cds_wfcq_for_each_blocking(head, tail, node) \
	460	for (node = __cds_wfcq_first_blocking(head, tail); \
	461	node != NULL; \
	462	node = __cds_wfcq_next_blocking(head, tail, node))
	463
	464	/*
	465	* __cds_wfcq_for_each_blocking_safe: Iterate over all nodes in a queue,
	466	* without dequeuing them. Safe against deletion.
f637f191	467	* @head: head of the queue (struct cds_wfcq_head or __cds_wfcq_head pointer).
8ad4ce58 MD	468	* @tail: tail of the queue (struct cds_wfcq_tail pointer).
	469	* @node: iterator on the queue (struct cds_wfcq_node pointer).
	470	* @n: struct cds_wfcq_node pointer holding the next pointer (used
	471	* internally).
	472	*
	473	* Content written into each node before enqueue is guaranteed to be
	474	* consistent, but no other memory ordering is ensured.
1fe734e1 MD	475	* Dequeue/splice/iteration mutual exclusion should be ensured by the
1fe734e1 MD	476	* caller.
8ad4ce58 MD	477	*/
	478	#define __cds_wfcq_for_each_blocking_safe(head, tail, node, n) \
	479	for (node = __cds_wfcq_first_blocking(head, tail), \
	480	n = (node ? __cds_wfcq_next_blocking(head, tail, node) : NULL); \
	481	node != NULL; \
	482	node = n, n = (node ? __cds_wfcq_next_blocking(head, tail, node) : NULL))
	483
	484	#ifdef __cplusplus
	485	}
	486	#endif
	487
	488	#endif /* _URCU_WFCQUEUE_H */