Index: uspace/lib/cpp/include/internal/rbtree_policies.hpp
===================================================================
--- uspace/lib/cpp/include/internal/rbtree_policies.hpp	(revision cacb5d0b0b55e670408f0c766d5b5a078ba11fd9)
+++ uspace/lib/cpp/include/internal/rbtree_policies.hpp	(revision 647b756ccd6a5c6ebdf8df6116ecbe4760f73368)
@@ -54,26 +54,23 @@
                 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)
+        }
+
+        template<class Tree, class Key>
+        static typename Tree::iterator lower_bound(const Tree& tree, const Key& key)
         {
             using iterator = typename Tree::iterator;
 
+            auto it = lower_bound_const(tree, key);
+
+            return iterator{it.node(), it.end()};
+        }
+
+        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);
-            iterator it{node, false};
+            const_iterator it{node, false};
             auto beg = tree.begin();
             auto end = tree.end();
@@ -102,54 +99,11 @@
 
         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;
+        static typename Tree::iterator upper_bound(const Tree& tree, const Key& key)
+        {
+            using iterator = typename Tree::iterator;
+
+            auto it = upper_bound_const(tree, key);
+
+            return iterator{it.node(), it.end()};
         }
 
@@ -220,10 +174,11 @@
             {
                 tree.root_ = new node_type{move(val)};
-
-                return make_pair(iterator{tree.root_}, true);
+                ++tree.size_;
+
+                return make_pair(iterator{tree.root_, false}, true);
             }
 
             if (tree.keys_equal(tree.get_key(parent->value), tree.get_key(val)))
-                return make_pair(iterator{parent}, false);
+                return make_pair(iterator{parent, false}, false);
 
             auto node = new node_type{move(val)};
@@ -233,5 +188,9 @@
                 parent->add_right_child(node);
 
-            return make_pair(iterator{node}, true);
+            ++tree.size_;
+            tree.repair_after_insert_(node);
+            tree.update_root_(node);
+
+            return make_pair(iterator{node, false}, true);
         }
 
@@ -248,4 +207,5 @@
             {
                 tree.root_ = new node_type{val};
+                ++tree.size_;
 
                 return make_pair(iterator{tree.root_}, true);
@@ -253,5 +213,5 @@
 
             if (tree.keys_equal(tree.get_key(parent->value), tree.get_key(val)))
-                return make_pair(iterator{parent}, false);
+                return make_pair(iterator{parent, false}, false);
 
             auto node = new node_type{val};
@@ -261,5 +221,9 @@
                 parent->add_right_child(node);
 
-            return make_pair(iterator{node}, true);
+            ++tree.size_;
+            tree.repair_after_insert_(node);
+            tree.update_root_(node);
+
+            return make_pair(iterator{node, false}, true);
         }
 
@@ -276,10 +240,11 @@
             {
                 tree.root_ = new node_type{forward<Value>(val)};
-
-                return make_pair(iterator{tree.root_}, true);
+                ++tree.size_;
+
+                return make_pair(iterator{tree.root_, false}, true);
             }
 
             if (tree.keys_equal(tree.get_key(parent->value), tree.get_key(val)))
-                return make_pair(iterator{parent}, false);
+                return make_pair(iterator{parent, false}, false);
 
             auto node = new node_type{forward<Value>(val)};
@@ -289,5 +254,9 @@
                 parent->add_right_child(node);
 
-            return make_pair(iterator{node}, true);
+            ++tree.size_;
+            tree.repair_after_insert_(node);
+            tree.update_root_(node);
+
+            return make_pair(iterator{node, false}, true);
         }
     };
@@ -295,5 +264,186 @@
     struct rbtree_multi_policy
     {
-        // TODO:
+        template<class Tree, class Key>
+        static typename Tree::size_type count(const Tree& tree, const Key& key)
+        {
+            using size_type = typename Tree::size_type;
+
+            auto it = tree.find(key);
+            if (it == tree.end())
+                return size_type{};
+
+            size_type res{};
+            while (tree.keys_equal(tree.get_key(*it), key))
+            {
+                ++res;
+                ++it;
+            }
+
+            return res;
+        }
+
+        template<class Tree, class Key>
+        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{};
+
+            size_type res{};
+            while (tree.keys_equal(tree.get_key(*it), key))
+            {
+                ++res;
+                it = tree.erase(it);
+            }
+
+            return res;
+        }
+
+        template<class Tree, class Key>
+        static typename Tree::iterator lower_bound(const Tree& tree, const Key& key)
+        {
+            auto it = lower_bound_const(tree, key);
+
+            return typename Tree::iterator{it.node(), it.end()};
+        }
+
+        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.keys_comp(key, *it))
+                --it; // Incase we are on a successor.
+            while (tree.keys_equal(tree.get_key(*it), key) && it != beg)
+                --it; // Skip keys that are equal.
+            if (it != beg)
+                ++it; // If we moved all the way to the start, key is the smallest.
+
+            if (tree.key_compare_(tree.get_key(*it), key))
+            {
+                // Predecessor.
+                if (it != end)
+                    return ++it;
+                else
+                    return it;
+            }
+
+            return it;
+        }
+
+        template<class Tree, class Key>
+        static typename Tree::iterator upper_bound(const Tree& tree, const Key& key)
+        {
+            auto it = upper_bound_const(tree, key);
+
+            return typename Tree::iterator{it.node(), it.end()};
+        }
+
+        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(tree, key);
+            if (it == tree.end())
+                return it;
+            else if (tree.keys_equal(tree.get_key(*it), key))
+            {
+                while (tree.keys_equal(tree.get_key(*it), key))
+                    ++it;
+
+                return it;
+            }
+
+            return it;
+        }
+
+        template<class Tree, class Key>
+        static pair<
+            typename Tree::iterator,
+            typename Tree::iterator
+        > equal_range(const Tree& tree, const Key& key)
+        {
+            return make_pair(
+                lower_bound(tree, key),
+                upper_bound(tree, key)
+            );
+        }
+
+        template<class Tree, class Key>
+        static pair<
+            typename Tree::const_iterator,
+            typename Tree::const_iterator
+        > equal_range_const(const Tree& tree, const Key& key)
+        {
+            return make_pair(
+                lower_bound_const(tree, key),
+                upper_bound_const(tree, key)
+            );
+        }
+
+        template<class Tree, class... Args>
+        static typename Tree::iterator emplace(Tree& tree, Args&&... args)
+        {
+            using node_type  = typename Tree::node_type;
+
+            auto node = node_type{forward<Args>(args)...};
+
+            return insert(tree, node);
+        }
+
+        template<class Tree, class Value>
+        static typename Tree::iterator insert(Tree& tree, const Value& val)
+        {
+            using node_type = typename Tree::node_type;
+
+            auto node = new node_type{val};
+
+            return insert(tree, node);
+        }
+
+        template<class Tree, class Value>
+        static typename Tree::iterator insert(Tree& tree, Value&& val)
+        {
+            using node_type = typename Tree::node_type;
+
+            auto node = new node_type{forward<Value>(val)};
+
+            return insert(tree, node);
+        }
+
+        template<class Tree>
+        static typename Tree::iterator insert(Tree& tree, typename Tree::node_type* node)
+        {
+            using iterator  = typename Tree::iterator;
+
+            auto parent = tree.find_parent_for_insertion(node->value);
+            if (!parent)
+                tree.root_ = node;
+            else if (tree.keys_comp(tree.get_key(node->value), parent->value))
+                parent->add_left_child(node);
+            else
+                parent->add_right_child(node);
+
+            ++tree.size_;
+            tree.repair_after_insert_(node);
+            tree.update_root_(node);
+
+            return iterator{node, false};
+        }
     };
 }