rbtree test: show tree

[userspace-rcu.git] / urcu-rbtree.h

diff --git a/urcu-rbtree.h b/urcu-rbtree.h
index b12a0e343b4d83d689c8b3943259a2842e417554..9670c346aff9759d23f51f86c4a2d558cdd4ccfa 100644 (file)
--- a/urcu-rbtree.h
+++ b/urcu-rbtree.h
@@ -35,6 +35,9 @@
 #define COLOR_BLACK    0
 #define COLOR_RED      1
 
+#define IS_LEFT                0
+#define IS_RIGHT       1
+
 /*
  * Node key comparison function.
  * < 0 : a lower than b.
@@ -58,8 +61,12 @@ struct rcu_rbtree_node {
        /* internally reserved */
        struct rcu_rbtree_node *p, *left, *right;
        unsigned int color:1;
+       unsigned int pos:1;
 };
 
+/* nil rbtree node. "root" must initially point to this node. */
+struct rcu_rbtree_node rcu_rbtree_nil;
+
 /*
  * Each of the search primitive and "prev"/"next" iteration must be called with
  * the RCU read-side lock held.
@@ -81,8 +88,13 @@ int rcu_rbtree_insert(struct rcu_rbtree_node **root,
 /*
  * Remove node from tree.
  * Must wait for a grace period after removal before performing deletion of the
- * node.
+ * node. Note: it is illegal to re-use the same node pointer passed to "insert"
+ * also to "remove", because it may have been copied and garbage-collected since
+ * the insertion. A "search" for the key in the tree should be done to get
+ * "node".
  * Returns 0 on success. May fail with -ENOMEM.
+ *
+ * The caller is responsible for freeing the node after a grace period.
  */
 int rcu_rbtree_remove(struct rcu_rbtree_node **root,
                      struct rcu_rbtree_node *node,
@@ -93,7 +105,7 @@ int rcu_rbtree_remove(struct rcu_rbtree_node **root,
 /* RCU read-side */
 
 /*
- * Search key starting from node x. Returns NULL if not found.
+ * Search key starting from node x. Returns &rcu_rbtree_nil if not found.
  */
 struct rcu_rbtree_node* rcu_rbtree_search(struct rcu_rbtree_node *x,
                                          void *key, rcu_rbtree_comp comp);