[urcu.git] / urcu / rculfstack.h

#ifndef _URCU_RCULFSTACK_H
#define _URCU_RCULFSTACK_H

/*
 * rculfstack.h
 *
 * Userspace RCU library - Lock-Free RCU Stack
 *
 * Copyright 2010 - Mathieu Desnoyers <mathieu.desnoyers@efficios.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
 */

#if (!defined(_GNU_SOURCE) && !defined(_LGPL_SOURCE))
#error "Dynamic loader LGPL wrappers not implemented yet"
#endif

struct rcu_lfs_node {
	struct rcu_lfs_node *next;
};

struct rcu_lfs_stack {
	struct rcu_lfs_node *head;
};

void rcu_lfs_node_init(struct rcu_lfs_node *node)
{
}

void rcu_lfs_init(struct rcu_lfs_stack *s)
{
	s->head = NULL;
}

void rcu_lfs_push(struct rcu_lfs_stack *s, struct rcu_lfs_node *node)
{
	for (;;) {
		struct rcu_lfs_node *head;

		rcu_read_lock();
		head = rcu_dereference(s->head);
		node->next = head;
		/*
		 * uatomic_cmpxchg() implicit memory barrier orders earlier
		 * stores to node before publication.
		 */
		if (uatomic_cmpxchg(&s->head, head, node) == head) {
			rcu_read_unlock();
			return;
		} else {
			/* Failure to prepend. Retry. */
			rcu_read_unlock();
			continue;
		}
	}
}

/*
 * The caller must wait for a grace period to pass before freeing the returned
 * node.
 * Returns NULL if stack is empty.
 */
struct rcu_lfs_node *
rcu_lfs_pop(struct rcu_lfs_stack *s)
{
	for (;;) {
		struct rcu_lfs_node *head;

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

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

#endif /* _URCU_RCULFSTACK_H */
Commit	Line	Data
	1	#ifndef _URCU_RCULFSTACK_H
	2	#define _URCU_RCULFSTACK_H
	3
	4	/*
	5	* rculfstack.h
	6	*
	7	* Userspace RCU library - Lock-Free RCU Stack
	8	*
	9	* Copyright 2010 - Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
	10	*
	11	* This library is free software; you can redistribute it and/or
	12	* modify it under the terms of the GNU Lesser General Public
	13	* License as published by the Free Software Foundation; either
	14	* version 2.1 of the License, or (at your option) any later version.
	15	*
	16	* This library is distributed in the hope that it will be useful,
	17	* but WITHOUT ANY WARRANTY; without even the implied warranty of
	18	* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
	19	* Lesser General Public License for more details.
	20	*
	21	* You should have received a copy of the GNU Lesser General Public
	22	* License along with this library; if not, write to the Free Software
	23	* Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
	24	*/
	25
	26	#if (!defined(_GNU_SOURCE) && !defined(_LGPL_SOURCE))
	27	#error "Dynamic loader LGPL wrappers not implemented yet"
	28	#endif
	29
	30	struct rcu_lfs_node {
	31	struct rcu_lfs_node *next;
	32	};
	33
	34	struct rcu_lfs_stack {
	35	struct rcu_lfs_node *head;
	36	};
	37
	38	void rcu_lfs_node_init(struct rcu_lfs_node *node)
	39	{
	40	}
	41
	42	void rcu_lfs_init(struct rcu_lfs_stack *s)
	43	{
	44	s->head = NULL;
	45	}
	46
	47	void rcu_lfs_push(struct rcu_lfs_stack s, struct rcu_lfs_node node)
	48	{
	49	for (;;) {
	50	struct rcu_lfs_node *head;
	51
	52	rcu_read_lock();
	53	head = rcu_dereference(s->head);
	54	node->next = head;
	55	/*
	56	* uatomic_cmpxchg() implicit memory barrier orders earlier
	57	* stores to node before publication.
	58	*/
	59	if (uatomic_cmpxchg(&s->head, head, node) == head) {
	60	rcu_read_unlock();
	61	return;
	62	} else {
	63	/* Failure to prepend. Retry. */
	64	rcu_read_unlock();
	65	continue;
	66	}
	67	}
	68	}
	69
	70	/*
	71	* The caller must wait for a grace period to pass before freeing the returned
	72	* node.
	73	* Returns NULL if stack is empty.
	74	*/
	75	struct rcu_lfs_node *
	76	rcu_lfs_pop(struct rcu_lfs_stack *s)
	77	{
	78	for (;;) {
	79	struct rcu_lfs_node *head;
	80
	81	rcu_read_lock();
	82	head = rcu_dereference(s->head);
	83	if (head) {
	84	struct rcu_lfs_node *next = rcu_dereference(head->next);
	85
	86	if (uatomic_cmpxchg(&s->head, head, next) == head) {
	87	rcu_read_unlock();
	88	return head;
	89	} else {
	90	/* Concurrent modification. Retry. */
	91	rcu_read_unlock();
	92	continue;
	93	}
	94	} else {
	95	/* Empty stack */
	96	rcu_read_unlock();
	97	return NULL;
	98	}
	99	}
	100	}
	101
	102	#endif /* _URCU_RCULFSTACK_H */