[urcu.git] / urcu / rculfstack-static.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_arch.h>
/* A urcu implementation header should be already included. */

#ifdef __cplusplus
extern "C" {
#endif

void _cds_lfs_node_init_rcu(struct cds_lfs_node_rcu *node)
{
}

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

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.
 */
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
	29	#include <urcu/uatomic_arch.h>
	30	/* A urcu implementation header should be already included. */
	31
	32	#ifdef __cplusplus
	33	extern "C" {
	34	#endif
	35
16aa9ee8	36	void _cds_lfs_node_init_rcu(struct cds_lfs_node_rcu *node)
b6a37eac MD	37	{
	38	}
	39
16aa9ee8	40	void _cds_lfs_init_rcu(struct cds_lfs_stack_rcu *s)
b6a37eac MD	41	{
	42	s->head = NULL;
	43	}
	44
16aa9ee8	45	void _cds_lfs_push_rcu(struct cds_lfs_stack_rcu s, struct cds_lfs_node_rcu node)
b6a37eac	46	{
16aa9ee8	47	struct cds_lfs_node_rcu *head = NULL;
75202035	48
b6a37eac	49	for (;;) {
16aa9ee8	50	struct cds_lfs_node_rcu *old_head = head;
b6a37eac	51
b6a37eac MD	52	node->next = head;
	53	/*
	54	* uatomic_cmpxchg() implicit memory barrier orders earlier
	55	* stores to node before publication.
	56	*/
75202035 MD	57	head = uatomic_cmpxchg(&s->head, old_head, node);
	58	if (old_head == head)
	59	break;
b6a37eac MD	60	}
	61	}
	62
	63	/*
d9b52143 MD	64	* Should be called under rcu read-side lock.
d9b52143 MD	65	*
b6a37eac	66	* The caller must wait for a grace period to pass before freeing the returned
16aa9ee8	67	* node or modifying the cds_lfs_node_rcu structure.
b6a37eac MD	68	* Returns NULL if stack is empty.
b6a37eac MD	69	*/
16aa9ee8 DG	70	struct cds_lfs_node_rcu *
16aa9ee8 DG	71	_cds_lfs_pop_rcu(struct cds_lfs_stack_rcu *s)
b6a37eac MD	72	{
b6a37eac MD	73	for (;;) {
16aa9ee8	74	struct cds_lfs_node_rcu *head;
b6a37eac	75
4fc06b7f MD	76	head = rcu_dereference(s->head);
4fc06b7f MD	77	if (head) {
16aa9ee8	78	struct cds_lfs_node_rcu *next = rcu_dereference(head->next);
b6a37eac	79
4fc06b7f	80	if (uatomic_cmpxchg(&s->head, head, next) == head) {
4fc06b7f MD	81	return head;
	82	} else {
	83	/* Concurrent modification. Retry. */
4fc06b7f MD	84	continue;
	85	}
	86	} else {
	87	/* Empty stack */
4fc06b7f MD	88	return NULL;
4fc06b7f MD	89	}
b6a37eac MD	90	}
	91	}
	92
	93	#ifdef __cplusplus
	94	}
	95	#endif
	96
	97	#endif /* _URCU_RCULFSTACK_STATIC_H */