[urcu.git] / urcu / static / rculfstack.h

#ifndef _URCU_RCULFSTACK_STATIC_H
#define _URCU_RCULFSTACK_STATIC_H

/*
 * rculfstack-static.h
 *
 * Userspace RCU library - Lock-Free RCU Stack
 *
 * Copyright 2010 - Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
 *
 * TO BE INCLUDED ONLY IN LGPL-COMPATIBLE CODE. See rculfstack.h for linking
 * dynamically with the userspace rcu library.
 *
 * 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 <urcu/uatomic.h>
/* A urcu implementation header should be already included. */

#ifdef __cplusplus
extern "C" {
#endif

static inline
void _cds_lfs_node_init_rcu(struct cds_lfs_node_rcu *node)
{
}

static inline
void _cds_lfs_init_rcu(struct cds_lfs_stack_rcu *s)
{
	s->head = NULL;
}

static inline
void _cds_lfs_push_rcu(struct cds_lfs_stack_rcu *s, struct cds_lfs_node_rcu *node)
{
	struct cds_lfs_node_rcu *head = NULL;

	for (;;) {
		struct cds_lfs_node_rcu *old_head = head;

		node->next = head;
		/*
		 * uatomic_cmpxchg() implicit memory barrier orders earlier
		 * stores to node before publication.
		 */
		head = uatomic_cmpxchg(&s->head, old_head, node);
		if (old_head == head)
			break;
	}
}

/*
 * Should be called under rcu read-side lock.
 *
 * The caller must wait for a grace period to pass before freeing the returned
 * node or modifying the cds_lfs_node_rcu structure.
 * Returns NULL if stack is empty.
 */
static inline
struct cds_lfs_node_rcu *
_cds_lfs_pop_rcu(struct cds_lfs_stack_rcu *s)
{
	for (;;) {
		struct cds_lfs_node_rcu *head;

		head = rcu_dereference(s->head);
		if (head) {
			struct cds_lfs_node_rcu *next = rcu_dereference(head->next);

			if (uatomic_cmpxchg(&s->head, head, next) == head) {
				return head;
			} else {
				/* Concurrent modification. Retry. */
				continue;
			}
		} else {
			/* Empty stack */
			return NULL;
		}
	}
}

#ifdef __cplusplus
}
#endif

#endif /* _URCU_RCULFSTACK_STATIC_H */
Commit	Line	Data
b6a37eac MD	1	#ifndef _URCU_RCULFSTACK_STATIC_H
	2	#define _URCU_RCULFSTACK_STATIC_H
	3
	4	/*
	5	* rculfstack-static.h
	6	*
	7	* Userspace RCU library - Lock-Free RCU Stack
	8	*
	9	* Copyright 2010 - Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
	10	*
	11	* TO BE INCLUDED ONLY IN LGPL-COMPATIBLE CODE. See rculfstack.h for linking
	12	* dynamically with the userspace rcu library.
	13	*
	14	* This library is free software; you can redistribute it and/or
	15	* modify it under the terms of the GNU Lesser General Public
	16	* License as published by the Free Software Foundation; either
	17	* version 2.1 of the License, or (at your option) any later version.
	18	*
	19	* This library is distributed in the hope that it will be useful,
	20	* but WITHOUT ANY WARRANTY; without even the implied warranty of
	21	* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
	22	* Lesser General Public License for more details.
	23	*
	24	* You should have received a copy of the GNU Lesser General Public
	25	* License along with this library; if not, write to the Free Software
	26	* Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
	27	*/
	28
a2e7bf9c	29	#include <urcu/uatomic.h>
b6a37eac MD	30	/* A urcu implementation header should be already included. */
	31
	32	#ifdef __cplusplus
	33	extern "C" {
	34	#endif
	35
c5f52d0c	36	static inline
16aa9ee8	37	void _cds_lfs_node_init_rcu(struct cds_lfs_node_rcu *node)
b6a37eac MD	38	{
	39	}
	40
c5f52d0c	41	static inline
16aa9ee8	42	void _cds_lfs_init_rcu(struct cds_lfs_stack_rcu *s)
b6a37eac MD	43	{
	44	s->head = NULL;
	45	}
	46
c5f52d0c	47	static inline
16aa9ee8	48	void _cds_lfs_push_rcu(struct cds_lfs_stack_rcu s, struct cds_lfs_node_rcu node)
b6a37eac	49	{
16aa9ee8	50	struct cds_lfs_node_rcu *head = NULL;
75202035	51
b6a37eac	52	for (;;) {
16aa9ee8	53	struct cds_lfs_node_rcu *old_head = head;
b6a37eac	54
b6a37eac MD	55	node->next = head;
	56	/*
	57	* uatomic_cmpxchg() implicit memory barrier orders earlier
	58	* stores to node before publication.
	59	*/
75202035 MD	60	head = uatomic_cmpxchg(&s->head, old_head, node);
	61	if (old_head == head)
	62	break;
b6a37eac MD	63	}
	64	}
	65
	66	/*
d9b52143 MD	67	* Should be called under rcu read-side lock.
d9b52143 MD	68	*
b6a37eac	69	* The caller must wait for a grace period to pass before freeing the returned
16aa9ee8	70	* node or modifying the cds_lfs_node_rcu structure.
b6a37eac MD	71	* Returns NULL if stack is empty.
b6a37eac MD	72	*/
c5f52d0c	73	static inline
16aa9ee8 DG	74	struct cds_lfs_node_rcu *
16aa9ee8 DG	75	_cds_lfs_pop_rcu(struct cds_lfs_stack_rcu *s)
b6a37eac MD	76	{
b6a37eac MD	77	for (;;) {
16aa9ee8	78	struct cds_lfs_node_rcu *head;
b6a37eac	79
4fc06b7f MD	80	head = rcu_dereference(s->head);
4fc06b7f MD	81	if (head) {
16aa9ee8	82	struct cds_lfs_node_rcu *next = rcu_dereference(head->next);
b6a37eac	83
4fc06b7f	84	if (uatomic_cmpxchg(&s->head, head, next) == head) {
4fc06b7f MD	85	return head;
	86	} else {
	87	/* Concurrent modification. Retry. */
4fc06b7f MD	88	continue;
	89	}
	90	} else {
	91	/* Empty stack */
4fc06b7f MD	92	return NULL;
4fc06b7f MD	93	}
b6a37eac MD	94	}
	95	}
	96
	97	#ifdef __cplusplus
	98	}
	99	#endif
	100
	101	#endif /* _URCU_RCULFSTACK_STATIC_H */