Index: uspace/lib/cpp/include/internal/rbtree.hpp
===================================================================
--- uspace/lib/cpp/include/internal/rbtree.hpp	(revision bb0212955007d8352e5478646fcff3db07313f52)
+++ uspace/lib/cpp/include/internal/rbtree.hpp	(revision 48f09f2fc1ca62fd13e779392828eb7b308c6c99)
@@ -313,5 +313,5 @@
             }
 
-            node_type* find_parent_for_insertion(const value_type& val) const
+            node_type* find_parent_for_insertion(const key_type& key) const
             {
                 auto current = root_;
@@ -321,5 +321,5 @@
                 {
                     parent = current;
-                    if (key_compare_(key_extractor_(val), key_extractor_(current->value)))
+                    if (key_compare_(key, key_extractor_(current->value)))
                         current = current->left;
                     else
Index: uspace/lib/cpp/include/internal/rbtree_policies.hpp
===================================================================
--- uspace/lib/cpp/include/internal/rbtree_policies.hpp	(revision bb0212955007d8352e5478646fcff3db07313f52)
+++ uspace/lib/cpp/include/internal/rbtree_policies.hpp	(revision 48f09f2fc1ca62fd13e779392828eb7b308c6c99)
@@ -170,5 +170,5 @@
 
             auto val = value_type{forward<Args>(args)...};
-            auto parent = tree.find_parent_for_insertion(val);
+            auto parent = tree.find_parent_for_insertion(tree.get_key(val));
 
             if (parent && tree.keys_equal(tree.get_key(parent->value), tree.get_key(val)))
@@ -189,5 +189,5 @@
             using node_type = typename Tree::node_type;
 
-            auto parent = tree.find_parent_for_insertion(val);
+            auto parent = tree.find_parent_for_insertion(tree.get_key(val));
             if (parent && tree.keys_equal(tree.get_key(parent->value), tree.get_key(val)))
                 return make_pair(iterator{parent, false}, false);
@@ -207,5 +207,5 @@
             using node_type = typename Tree::node_type;
 
-            auto parent = tree.find_parent_for_insertion(val);
+            auto parent = tree.find_parent_for_insertion(tree.get_key(val));
             if (parent && tree.keys_equal(tree.get_key(parent->value), tree.get_key(val)))
                 return make_pair(iterator{parent, false}, false);
@@ -388,5 +388,5 @@
             using iterator  = typename Tree::iterator;
 
-            auto parent = tree.find_parent_for_insertion(node->value);
+            auto parent = tree.find_parent_for_insertion(tree.get_key(node->value));
             tree.insert_node(node, parent);