ifdef C, wait-free stack adaptative pop wait
[urcu.git] / urcu / rculfstack.h
CommitLineData
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
27extern "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
34struct rcu_lfs_node {
35 struct rcu_lfs_node *next;
36};
37
38struct rcu_lfs_stack {
39 struct rcu_lfs_node *head;
40};
41
42void rcu_lfs_node_init(struct rcu_lfs_node *node)
43{
44}
45
46void rcu_lfs_init(struct rcu_lfs_stack *s)
47{
48 s->head = NULL;
49}
50
51void 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();
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/*
75 * The caller must wait for a grace period to pass before freeing the returned
76 * node.
77 * Returns NULL if stack is empty.
78 */
453629a9
MD
79struct rcu_lfs_node *
80rcu_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();
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 */
This page took 0.029176 seconds and 4 git commands to generate.