[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
 */

#ifdef __cplusplus
extern "C" {
#endif

#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 or modifying the rcu_lfs_node structure.
 * 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;
		}
	}
}

#ifdef __cplusplus
}
#endif

#endif /* _URCU_RCULFSTACK_H */
Commit	Line	Data
c3f74cb2 MD	1	#ifndef _URCU_RCULFSTACK_H
	2	#define _URCU_RCULFSTACK_H
	3
453629a9 MD	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
0e2e9380 MD	26	#ifdef __cplusplus
	27	extern "C" {
	28	#endif
	29
453629a9 MD	30	#if (!defined(_GNU_SOURCE) && !defined(_LGPL_SOURCE))
	31	#error "Dynamic loader LGPL wrappers not implemented yet"
	32	#endif
	33
	34	struct rcu_lfs_node {
	35	struct rcu_lfs_node *next;
	36	};
	37
	38	struct rcu_lfs_stack {
	39	struct rcu_lfs_node *head;
	40	};
	41
	42	void rcu_lfs_node_init(struct rcu_lfs_node *node)
	43	{
	44	}
	45
	46	void rcu_lfs_init(struct rcu_lfs_stack *s)
	47	{
	48	s->head = NULL;
	49	}
	50
	51	void rcu_lfs_push(struct rcu_lfs_stack s, struct rcu_lfs_node node)
	52	{
453629a9	53	for (;;) {
2e6c6432	54	struct rcu_lfs_node *head;
453629a9	55
2e6c6432 MD	56	rcu_read_lock();
2e6c6432 MD	57	head = rcu_dereference(s->head);
453629a9 MD	58	node->next = head;
	59	/*
	60	* uatomic_cmpxchg() implicit memory barrier orders earlier
	61	* stores to node before publication.
	62	*/
	63	if (uatomic_cmpxchg(&s->head, head, node) == head) {
	64	rcu_read_unlock();
	65	return;
	66	} else {
	67	/* Failure to prepend. Retry. */
2e6c6432	68	rcu_read_unlock();
453629a9 MD	69	continue;
	70	}
	71	}
	72	}
	73
1c1e940e MD	74	/*
1c1e940e MD	75	* The caller must wait for a grace period to pass before freeing the returned
c97740a3	76	* node or modifying the rcu_lfs_node structure.
1c1e940e MD	77	* Returns NULL if stack is empty.
1c1e940e MD	78	*/
453629a9 MD	79	struct rcu_lfs_node *
	80	rcu_lfs_pop(struct rcu_lfs_stack *s)
	81	{
453629a9	82	for (;;) {
2e6c6432	83	struct rcu_lfs_node *head;
453629a9	84
2e6c6432 MD	85	rcu_read_lock();
2e6c6432 MD	86	head = rcu_dereference(s->head);
453629a9 MD	87	if (head) {
	88	struct rcu_lfs_node *next = rcu_dereference(head->next);
	89
	90	if (uatomic_cmpxchg(&s->head, head, next) == head) {
	91	rcu_read_unlock();
	92	return head;
	93	} else {
	94	/* Concurrent modification. Retry. */
2e6c6432	95	rcu_read_unlock();
453629a9 MD	96	continue;
	97	}
	98	} else {
	99	/* Empty stack */
	100	rcu_read_unlock();
	101	return NULL;
	102	}
	103	}
	104	}
c3f74cb2	105
0e2e9380 MD	106	#ifdef __cplusplus
	107	}
	108	#endif
	109
c3f74cb2	110	#endif /* _URCU_RCULFSTACK_H */