7 * Userspace RCU library - Red-Black Tree
9 * Copyright (c) 2010 Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
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.
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.
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
25 * Implementation of RCU-adapted data structures and operations based on the RB
26 * tree algorithms found in chapter 12 of:
28 * Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and
29 * Clifford Stein. Introduction to Algorithms, Third Edition. The MIT
30 * Press, September 2009.
42 * Node key comparison function.
43 * < 0 : a lower than b.
44 * > 0 : a greater than b.
47 typedef int (*rcu_rbtree_comp
)(void *a
, void *b
);
50 * Node allocation and deletion functions.
52 typedef struct rcu_rbtree_node
*(*rcu_rbtree_alloc
)(void);
53 typedef void (*rcu_rbtree_free
)(struct rcu_rbtree_node
*node
);
55 struct rcu_rbtree_node
;
57 struct rcu_rbtree_node
{
58 /* must be set upon insertion */
61 /* internally reserved */
62 struct rcu_rbtree_node
*p
, *left
, *right
;
67 /* nil rbtree node. "root" must initially point to this node. */
68 struct rcu_rbtree_node rcu_rbtree_nil
;
71 * Each of the search primitive and "prev"/"next" iteration must be called with
72 * the RCU read-side lock held.
74 * Insertion and removal must be protected by a mutex. At the moment, insertion
75 * and removal use defer_rcu, so calling them with rcu read-lock held is
80 * Node insertion. Returns 0 on success. May fail with -ENOMEM.
82 int rcu_rbtree_insert(struct rcu_rbtree_node
**root
,
83 struct rcu_rbtree_node
*node
,
85 rcu_rbtree_alloc rballoc
,
86 rcu_rbtree_free rbfree
);
89 * Remove node from tree.
90 * Must wait for a grace period after removal before performing deletion of the
91 * node. Note: it is illegal to re-use the same node pointer passed to "insert"
92 * also to "remove", because it may have been copied and garbage-collected since
93 * the insertion. A "search" for the key in the tree should be done to get
95 * Returns 0 on success. May fail with -ENOMEM.
97 * The caller is responsible for freeing the node after a grace period.
99 int rcu_rbtree_remove(struct rcu_rbtree_node
**root
,
100 struct rcu_rbtree_node
*node
,
101 rcu_rbtree_comp comp
,
102 rcu_rbtree_alloc rballoc
,
103 rcu_rbtree_free rbfree
);
108 * Search key starting from node x. Returns &rcu_rbtree_nil if not found.
110 struct rcu_rbtree_node
* rcu_rbtree_search(struct rcu_rbtree_node
*x
,
111 void *key
, rcu_rbtree_comp comp
);
113 struct rcu_rbtree_node
*rcu_rbtree_min(struct rcu_rbtree_node
*x
,
114 rcu_rbtree_comp comp
);
116 struct rcu_rbtree_node
*rcu_rbtree_max(struct rcu_rbtree_node
*x
,
117 rcu_rbtree_comp comp
);
119 struct rcu_rbtree_node
*rcu_rbtree_next(struct rcu_rbtree_node
*x
,
120 rcu_rbtree_comp comp
);
122 struct rcu_rbtree_node
*rcu_rbtree_prev(struct rcu_rbtree_node
*x
,
123 rcu_rbtree_comp comp
);
125 #endif /* URCU_RBTREE_H */