rbtree test: show tree

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

diff --git a/urcu-rbtree.h b/urcu-rbtree.h
index 8125170df9d31ce05a0a5748a9f9a8a07d3d6a76..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,6 +61,7 @@ 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. */
@@ -84,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,
@@ -96,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);