+rb_node_index_t
+rb_tree_add_custom (rb_tree_t * rt, u32 key, uword opaque, rb_tree_lt_fn ltfn)
+{
+ rb_node_index_t yi = 0, xi = rt->root;
+ rb_node_t *z, *y, *x;
+
+ pool_get_zero (rt->nodes, z);
+ z->key = key;
+ z->color = RBTREE_RED;
+ z->opaque = opaque;
+
+ y = rb_node (rt, RBTREE_TNIL_INDEX);
+ while (xi != RBTREE_TNIL_INDEX)
+ {
+ x = rb_node (rt, xi);
+ y = x;
+ ASSERT (z->key != x->key);
+ if (ltfn (z->key, x->key))
+ xi = x->left;
+ else
+ xi = x->right;
+ }
+ yi = rb_node_index (rt, y);
+ z->parent = yi;
+ if (yi == RBTREE_TNIL_INDEX)
+ rt->root = rb_node_index (rt, z);
+ else if (ltfn (z->key, y->key))
+ y->left = rb_node_index (rt, z);
+ else
+ y->right = rb_node_index (rt, z);
+
+ rb_tree_fixup_inline (rt, y, z);
+
+ return rb_node_index (rt, z);
+}
+