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