#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.
/* 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. */
/*
* 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,
/* 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);