Index: uspace/lib/cpp/include/internal/rbtree_policies.hpp
===================================================================
--- uspace/lib/cpp/include/internal/rbtree_policies.hpp	(revision 49fbfb594483ab34c974b754eb90f7df9e0ef10c)
+++ uspace/lib/cpp/include/internal/rbtree_policies.hpp	(revision f8bbaa083cba7c3130b4f8c68cf7327222ae3a88)
@@ -44,22 +44,133 @@
 
         template<class Tree, class Key>
-        static pair<
-            typename Tree::node_type*,
-            typename Tree::node_type*
-        > erase(const Tree& tree, const Key& key)
-        {
-            // TODO:
-        }
-
-        template<class Tree, class Key>
-        static typename Tree::iterator lower_bound(const Tree& tree, const Key& key)
-        {
-            // TODO:
-        }
-
-        template<class Tree, class Key>
-        static typename Tree::iterator upper_bound(const Tree& tree, const Key& key)
-        {
-            // TODO:
+        static typename Tree::size_type erase(Tree& tree, const Key& key)
+        {
+            using size_type = typename Tree::size_type;
+
+            auto it = tree.find(key);
+            if (it == tree.end())
+                return size_type{};
+            else
+                tree.delete_node(it.node());
+            return size_type{1};
+
+            // This is the multi version -.-
+            /* size_type res{}; */
+            /* while (tree.keys_equal(tree.get_key(*it), key)) */
+            /* { */
+            /*     auto node = it.node(); */
+            /*     ++it; */
+
+            /*     tree->delete_node(node); */
+            /*     ++res; */
+            /* } */
+
+            /* return res; */
+        }
+
+        template<class Tree, class Key>
+        static typename Tree::iterator lower_bound(Tree& tree, const Key& key)
+        {
+            using iterator = typename Tree::iterator;
+
+            auto node = tree.find_parent_for_insertion(key);
+            iterator it{node, false};
+            auto beg = tree.begin();
+            auto end = tree.end();
+
+            if (tree.key_compare_(tree.get_key(*it), key))
+            {
+                // Predecessor.
+                if (it != end)
+                    return ++it;
+                else
+                    return it;
+            }
+            else if (tree.key_compare_(key, tree.get_key(*it)))
+            {
+                // Successor.
+                if (it != beg)
+                    return --it;
+                else
+                    return it;
+            }
+            else // Perfect match.
+                return it;
+
+            return it;
+        }
+
+        template<class Tree, class Key>
+        static typename Tree::const_iterator lower_bound_const(const Tree& tree, const Key& key)
+        {
+            using const_iterator = typename Tree::const_iterator;
+
+            auto node = tree.find_parent_for_insertion(key);
+            const_iterator it{node, false};
+            auto beg = tree.begin();
+            auto end = tree.end();
+
+            if (tree.key_compare_(tree.get_key(*it), key))
+            {
+                // Predecessor.
+                if (it != end)
+                    return ++it;
+                else
+                    return it;
+            }
+            else if (tree.key_compare_(key, tree.get_key(*it)))
+            {
+                // Successor.
+                if (it != beg)
+                    return --it;
+                else
+                    return it;
+            }
+            else // Perfect match.
+                return it;
+
+            return it;
+        }
+
+        template<class Tree, class Key>
+        static typename Tree::iterator upper_bound(Tree& tree, const Key& key)
+        {
+            /**
+             * If key isn't in the tree, we get it's
+             * successor or tree.end(). If key is
+             * in the tree, we get it.
+             * In the first case, the successor is also
+             * the upper bound, so we just return it,
+             * otherwise (as long as it != end()) we
+             * increment.
+             */
+            auto it = lower_bound(tree, key);
+            if (it == tree.end())
+                return it;
+            else if (tree.keys_equal(key, *it))
+                return ++it;
+            else
+                return it;
+        }
+
+        template<class Tree, class Key>
+        static typename Tree::const_iterator upper_bound_const(const Tree& tree, const Key& key)
+        {
+            /**
+             * If key isn't in the tree, we get it's
+             * successor or tree.end(). If key is
+             * in the tree, we get it.
+             * In the first case, the successor is also
+             * the upper bound, so we just return it,
+             * otherwise (as long as it != end()) we
+             * increment.
+             */
+            auto it = lower_bound_const(tree, key);
+            if (it == tree.end())
+                return it;
+            else if (tree.keys_equal(key, *it))
+                return ++it;
+            else
+                return it;
         }
 
@@ -68,7 +179,10 @@
             typename Tree::iterator,
             typename Tree::iterator
-        > equal_range(const Tree& tree, const Key& key)
-        {
-            // TODO:
+        > equal_range(Tree& tree, const Key& key)
+        {
+            return make_pair(
+                lower_bound(tree, key),
+                upper_bound(tree, key)
+            );
         }
 
@@ -79,5 +193,8 @@
         > equal_range_const(const Tree& tree, const Key& key)
         {
-            // TODO:
+            return make_pair(
+                lower_bound_const(tree, key),
+                upper_bound_const(tree, key)
+            );
         }
 
@@ -107,5 +224,5 @@
             }
 
-            if (tree.get_key(parent->value) == tree.get_key(val))
+            if (tree.keys_equal(tree.get_key(parent->value), tree.get_key(val)))
                 return make_pair(iterator{parent}, false);
 
@@ -135,5 +252,5 @@
             }
 
-            if (tree.get_key(parent->value) == tree.get_key(val))
+            if (tree.keys_equal(tree.get_key(parent->value), tree.get_key(val)))
                 return make_pair(iterator{parent}, false);
 
@@ -163,5 +280,5 @@
             }
 
-            if (tree.get_key(parent->value) == tree.get_key(val))
+            if (tree.keys_equal(tree.get_key(parent->value), tree.get_key(val)))
                 return make_pair(iterator{parent}, false);