Index: uspace/lib/cpp/include/internal/hash_table.hpp
===================================================================
--- uspace/lib/cpp/include/internal/hash_table.hpp	(revision b22ccaa60d7166c5ab9c53efecda53f5c976ea39)
+++ uspace/lib/cpp/include/internal/hash_table.hpp	(revision 6b18e43969229aee425dc9cc96cc33dfed7e42f7)
@@ -32,4 +32,7 @@
 #include <cstdlib>
 #include <internal/list.hpp>
+#include <internal/key_extractors.hpp>
+#include <internal/hash_table_iterators.hpp>
+#include <internal/hash_table_policies.hpp>
 #include <iterator>
 #include <limits>
@@ -47,903 +50,9 @@
      * and two proxies that either use plain Key type or a pair
      * of a key and a value.
+     * Additionally, we will use policies to represent both single
+     * and multi variants of these containers at once.
      * Note: I am aware the naming is very unimaginative here,
      *       not my strong side :)
      */
-
-    template<class Key, class Value>
-    struct key_value_key_extractor
-    {
-        const Key& operator()(const pair<const Key, Value>& p) const noexcept
-        {
-            return p.first;
-        }
-    };
-
-    template<class Key>
-    struct key_no_value_key_extractor
-    {
-        Key& operator()(Key& k) const noexcept
-        {
-            return k;
-        }
-
-        const Key& operator()(const Key& k) const noexcept
-        {
-            return k;
-        }
-    };
-
-    template<class Value, class Size>
-    struct hash_table_bucket
-    {
-        /**
-         * Note: We use a doubly linked list because
-         *       we need to use hints, which point to the
-         *       element after the hinted spot.
-         */
-
-        list_node<Value>* head;
-
-        hash_table_bucket()
-            : head{}
-        { /* DUMMY BODY */ }
-
-        Size size() const noexcept
-        {
-            auto current = head;
-            Size res{};
-
-            do
-            {
-                ++res;
-                current = current->next;
-            }
-            while (current != head);
-
-            return res;
-        }
-
-        void append(list_node<Value>* node)
-        {
-            if (!head)
-                head = node;
-            else
-                head->append(node);
-        }
-
-        void prepend(list_node<Value>* node)
-        {
-            if (!head)
-                head = node;
-            else
-                head->prepend(node);
-        }
-
-        void clear()
-        {
-            if (!head)
-                return;
-
-            auto current = head;
-            do
-            {
-                auto tmp = current;
-                current = current->next;
-                delete tmp;
-            }
-            while (current != head);
-
-            head = nullptr;
-        }
-
-        ~hash_table_bucket()
-        {
-            clear();
-        }
-    };
-
-    struct hash_single_policy
-    {
-        template<class Table, class Key>
-        static typename Table::size_type count(const Table& table, const Key& key)
-        {
-            return table.find(key) == table.end() ? 0 : 1;
-        }
-
-        template<class Table, class Key>
-        static typename Table::place_type find_insertion_spot(const Table& table, const Key& key)
-        {
-            auto idx = table.get_bucket_idx_(key);
-            return make_tuple(
-                &table.table_[idx],
-                table.table_[idx].head,
-                idx
-            );
-        }
-
-        template<class Table, class Key>
-        static typename Table::size_type erase(Table& table, const Key& key)
-        {
-            auto idx = table.get_bucket_idx_(key);
-            auto head = table.table_[idx].head;
-            auto current = head;
-
-            do
-            {
-                if (table.keys_equal(key, current->value))
-                {
-                    --table.size_;
-
-                    if (current == head)
-                    {
-                        if (current->next != head)
-                            table.table_[idx].head = current->next;
-                        else
-                            table.table_[idx].head = nullptr;
-                    }
-
-                    current->unlink();
-                    delete current;
-
-                    return 1;
-                }
-                else
-                    current = current->next;
-            }
-            while (current != head);
-
-            return 0;
-        }
-
-        template<class Table, class Key>
-        static pair<
-            typename Table::iterator,
-            typename Table::iterator
-        > equal_range(Table& table, const Key& key)
-        {
-            auto it = table.find(key);
-            return make_pair(it, ++it);
-        }
-
-        template<class Table, class Key>
-        static pair<
-            typename Table::const_iterator,
-            typename Table::const_iterator
-        > equal_range_const(const Table& table, const Key& key)
-        { // Note: We cannot overload by return type, so we use a different name.
-            auto it = table.find(key);
-            return make_pair(it, ++it);
-        }
-
-        /**
-         * Note: We have to duplicate code for emplace, insert(const&)
-         *       and insert(&&) here, because the node (which makes distinction
-         *       between the arguments) is only created if the value isn't
-         *       in the table already.
-         */
-
-        template<class Table, class... Args>
-        static pair<
-            typename Table::iterator, bool
-        > emplace(Table& table, Args&&... args)
-        {
-            using value_type = typename Table::value_type;
-            using node_type  = typename Table::node_type;
-            using iterator   = typename Table::iterator;
-
-            table.increment_size();
-
-            auto val = value_type{forward<Args>(args)...};
-            const auto& key = table.get_key(val);
-            auto [bucket, target, idx] = table.find_insertion_spot(key);
-
-            if (!bucket)
-                return make_pair(table.end(), false);
-
-            if (target && table.keys_equal(key, target->value))
-            {
-                table.decrement_size();
-
-                return make_pair(
-                    iterator{
-                        table.table(), idx, table.bucket_count(),
-                        target
-                    },
-                    false
-                );
-            }
-            else
-            {
-                auto node = new node_type{move(val)};
-                bucket->prepend(node);
-
-                return make_pair(iterator{
-                    table.table(), idx,
-                    table.bucket_count(),
-                    node
-                }, true);
-            }
-        }
-
-        template<class Table, class Value>
-        static pair<
-            typename Table::iterator, bool
-        > insert(Table& table, const Value& val)
-        {
-            using node_type  = typename Table::node_type;
-            using iterator   = typename Table::iterator;
-
-            table.increment_size();
-
-            const auto& key = table.get_key(val);
-            auto [bucket, target, idx] = table.find_insertion_spot(key);
-
-            if (!bucket)
-                return make_pair(table.end(), false);
-
-            if (target && table.keys_equal(key, target->value))
-            {
-                table.decrement_size();
-
-                return make_pair(
-                    iterator{
-                        table.table(), idx, table.bucket_count(),
-                        target
-                    },
-                    false
-                );
-            }
-            else
-            {
-                auto node = new node_type{val};
-                bucket->prepend(node);
-
-                return make_pair(iterator{
-                    table.table(), idx,
-                    table.bucket_count(),
-                    node
-                }, true);
-            }
-        }
-
-        template<class Table, class Value>
-        static pair<
-            typename Table::iterator, bool
-        > insert(Table& table, Value&& val)
-        {
-            using value_type = typename Table::value_type;
-            using node_type  = typename Table::node_type;
-            using iterator   = typename Table::iterator;
-
-            table.increment_size();
-
-            const auto& key = table.get_key(val);
-            auto [bucket, target, idx] = table.find_insertion_spot(key);
-
-            if (!bucket)
-                return make_pair(table.end(), false);
-
-            if (target && table.keys_equal(key, target->value))
-            {
-                table.decrement_size();
-
-                return make_pair(
-                    iterator{
-                        table.table(), idx, table.bucket_count(),
-                        target
-                    },
-                    false
-                );
-            }
-            else
-            {
-                auto node = new node_type{forward<value_type>(val)};
-                bucket->prepend(node);
-
-                return make_pair(iterator{
-                    table.table(), idx,
-                    table.bucket_count(),
-                    node
-                }, true);
-            }
-        }
-    };
-
-    struct hash_multi_policy
-    {
-        template<class Table, class Key>
-        static typename Table::size_type count(const Table& table, const Key& key)
-        {
-            auto head = table.table_[get_bucket_idx_(key)].head;
-            if (!head)
-                return 0;
-
-            auto current = head;
-            typename Table::size_type res = 0;
-            do
-            {
-                if (table.keys_equal(key, current->value))
-                    ++res;
-
-                current = current->next;
-            }
-            while (current != head);
-
-            return res;
-        }
-
-        template<class Table, class Key>
-        static typename Table::place_type find_insertion_spot(const Table& table, const Key& key)
-        {
-            auto idx = table.get_bucket_idx_(key);
-            auto head = table.table_[idx].head;
-
-            if (head)
-            {
-                auto current = head;
-                do
-                {
-                    if (table.keys_equal(key, current->value))
-                    {
-                        return make_tuple(
-                            &table.table_[idx],
-                            current,
-                            idx
-                        );
-                    }
-
-                    current = current->next;
-                } while (current != head);
-            }
-
-            return make_tuple(
-                &table.table_[idx],
-                table.table_[idx].head,
-                idx
-            );
-        }
-
-        template<class Table, class Key>
-        static typename Table::size_type erase(Table& table, const Key& key)
-        {
-            auto idx = table.get_bucket_idx_(key);
-            auto it = table.begin(it);
-            typename Table::size_type res{};
-
-            while (it != table.end(it))
-            {
-                if (table.keys_equal(key, *it))
-                {
-                    while (table.keys_equal(key, *it))
-                    {
-                        auto node = it.node();
-                        ++it;
-                        ++res;
-
-                        node.unlink();
-                        delete node;
-                        --table.size_;
-                    }
-
-                    // Elements with equal keys are next to each other.
-                    return res;
-                }
-
-                ++it;
-            }
-
-            return res;
-        }
-
-        template<class Table, class Key>
-        static pair<
-            typename Table::iterator,
-            typename Table::iterator
-        > equal_range(Table& table, const Key& key)
-        {
-            auto first = table.find(key);
-            if (first == table.end())
-                return make_pair(table.end(), table.end());
-
-            auto last = first;
-            do
-            {
-                ++last;
-            } while (table.keys_equal(key, *last));
-
-            return make_pair(first, last);
-        }
-
-        template<class Table, class Key>
-        static pair<
-            typename Table::const_iterator,
-            typename Table::const_iterator
-        > equal_range_const(const Table& table, const Key& key)
-        {
-            auto first = table.find(key);
-            if (first == table.end())
-                return make_pair(table.end(), table.end());
-
-            auto last = first;
-            do
-            {
-                ++last;
-            } while (table.keys_equal(key, *last));
-
-            return make_pair(first, last);
-        }
-
-        template<class Table, class... Args>
-        static pair<
-            typename Table::iterator, bool
-        > emplace(Table& table, Args&&... args)
-        {
-            using node_type  = typename Table::node_type;
-
-            auto node = new node_type{forward<Args>(args)...};
-
-            return insert(table, node);
-        }
-
-        template<class Table, class Value>
-        static pair<
-            typename Table::iterator, bool
-        > insert(Table& table, const Value& val)
-        {
-            using node_type  = typename Table::node_type;
-
-            auto node = new node_type{val};
-
-            return insert(table, node);
-        }
-
-        template<class Table, class Value>
-        static pair<
-            typename Table::iterator, bool
-        > insert(Table& table, Value&& val)
-        {
-            using value_type = typename Table::value_type;
-            using node_type  = typename Table::node_type;
-
-            auto node = new node_type{forward<value_type>(val)};
-
-            return insert(table, node);
-        }
-
-        template<class Table>
-        static pair<
-            typename Table::iterator, bool
-        > insert(Table& table, typename Table::node_type* node)
-        {
-            using iterator   = typename Table::iterator;
-
-            table.increment_size();
-
-            const auto& key = table.get_key(node->value);
-            auto [bucket, target, idx] = table.find_insertion_spot(key);
-
-            if (!bucket)
-                return make_pair(table.end(), false);
-
-            if (target && table.keys_equal(key, target->value))
-                target->append(node);
-            else
-                bucket->prepend(node);
-
-            return make_pair(iterator{
-                table.table(), idx,
-                table.bucket_count(),
-                node
-            }, true);
-        }
-    };
-
-    template<class Value, class ConstReference, class ConstPointer, class Size>
-    class hash_table_const_iterator
-    {
-        public:
-            using value_type      = Value;
-            using size_type       = Size;
-            using const_reference = ConstReference;
-            using const_pointer   = ConstPointer;
-            using difference_type = ptrdiff_t;
-
-            using iterator_category = forward_iterator_tag;
-
-            hash_table_const_iterator(const hash_table_bucket<value_type, size_type>* table = nullptr,
-                                      size_type idx = size_type{}, size_type max_idx = size_type{},
-                                      const list_node<value_type>* current = nullptr)
-                : table_{table}, idx_{idx}, max_idx_{max_idx}, current_{current}
-            { /* DUMMY BODY */ }
-
-            hash_table_const_iterator(const hash_table_const_iterator&) = default;
-            hash_table_const_iterator& operator=(const hash_table_const_iterator&) = default;
-
-            const_reference operator*() const
-            {
-                return current_->value;
-            }
-
-            const_pointer operator->() const
-            {
-                return &current_->value;
-            }
-
-            hash_table_const_iterator& operator++()
-            {
-                current_ = current_->next;
-                if (current_ == table_[idx_].head)
-                {
-                    if (idx_ < max_idx_)
-                    {
-                        while (!table_[++idx_].head && idx_ < max_idx_)
-                        { /* DUMMY BODY */ }
-
-                        if (idx_ < max_idx_)
-                            current_ = table_[idx_].head;
-                        else
-                            current_ = nullptr;
-                    }
-                    else
-                        current_ = nullptr;
-                }
-
-                return *this;
-            }
-
-            hash_table_const_iterator operator++(int)
-            {
-                auto tmp_current = current_;
-                auto tmp_idx = idx_;
-
-                current_ = current_->next;
-                if (current_ == table_[idx_].head)
-                {
-                    if (idx_ < max_idx_)
-                    {
-                        while (!table_[++idx_].head && idx_ < max_idx_)
-                        { /* DUMMY BODY */ }
-
-                        if (idx_ < max_idx_)
-                            current_ = table_[idx_].head;
-                        else
-                            current_ = nullptr;
-                    }
-                    else
-                        current_ = nullptr;
-                }
-
-                return hash_table_const_iterator{
-                    table_, tmp_idx, max_idx_, tmp_current
-                };
-            }
-
-            list_node<value_type>* node()
-            {
-                return const_cast<list_node<value_type>*>(current_);
-            }
-
-            const list_node<value_type>* node() const
-            {
-                return current_;
-            }
-
-            size_type idx() const
-            {
-                return idx_;
-            }
-
-        private:
-            const hash_table_bucket<value_type, size_type>* table_;
-            size_type idx_;
-            size_type max_idx_;
-            const list_node<value_type>* current_;
-    };
-
-    template<class Value, class ConstRef, class ConstPtr, class Size>
-    bool operator==(const hash_table_const_iterator<Value, ConstRef, ConstPtr, Size>& lhs,
-                    const hash_table_const_iterator<Value, ConstRef, ConstPtr, Size>& rhs)
-    {
-        return lhs.node() == rhs.node();
-    }
-
-    template<class Value, class ConstRef, class ConstPtr, class Size>
-    bool operator!=(const hash_table_const_iterator<Value, ConstRef, ConstPtr, Size>& lhs,
-                    const hash_table_const_iterator<Value, ConstRef, ConstPtr, Size>& rhs)
-    {
-        return !(lhs == rhs);
-    }
-
-    template<class Value, class Reference, class Pointer, class Size>
-    class hash_table_iterator
-    {
-        public:
-            using value_type      = Value;
-            using size_type       = Size;
-            using reference       = Reference;
-            using pointer         = Pointer;
-            using difference_type = ptrdiff_t;
-
-            using iterator_category = forward_iterator_tag;
-
-            hash_table_iterator(hash_table_bucket<value_type, size_type>* table = nullptr,
-                                size_type idx = size_type{}, size_type max_idx = size_type{},
-                                list_node<value_type>* current = nullptr)
-                : table_{table}, idx_{idx}, max_idx_{max_idx}, current_{current}
-            { /* DUMMY BODY */ }
-
-            hash_table_iterator(const hash_table_iterator&) = default;
-            hash_table_iterator& operator=(const hash_table_iterator&) = default;
-
-            reference operator*()
-            {
-                return current_->value;
-            }
-
-            pointer operator->()
-            {
-                return &current_->value;
-            }
-
-            hash_table_iterator& operator++()
-            {
-                current_ = current_->next;
-                if (current_ == table_[idx_].head)
-                {
-                    if (idx_ < max_idx_)
-                    {
-                        while (!table_[++idx_].head && idx_ < max_idx_)
-                        { /* DUMMY BODY */ }
-
-                        if (idx_ < max_idx_)
-                            current_ = table_[idx_].head;
-                        else
-                            current_ = nullptr;
-                    }
-                    else
-                        current_ = nullptr;
-                }
-
-                return *this;
-            }
-
-            hash_table_iterator operator++(int)
-            {
-                auto tmp_current = current_;
-                auto tmp_idx = idx_;
-
-                current_ = current_->next;
-                if (current_ == table_[idx_].head)
-                {
-                    if (idx_ < max_idx_)
-                    {
-                        while (!table_[++idx_].head && idx_ < max_idx_)
-                        { /* DUMMY BODY */ }
-
-                        if (idx_ < max_idx_)
-                            current_ = table_[idx_].head;
-                        else
-                            current_ = nullptr;
-                    }
-                    else
-                        current_ = nullptr;
-                }
-
-                return hash_table_iterator{
-                    table_, tmp_idx, max_idx_, tmp_current
-                };
-            }
-
-            list_node<value_type>* node()
-            {
-                return current_;
-            }
-
-            const list_node<value_type>* node() const
-            {
-                return current_;
-            }
-
-            size_type idx() const
-            {
-                return idx_;
-            }
-
-            template<class ConstRef, class ConstPtr>
-            operator hash_table_const_iterator<
-                Value, ConstRef, ConstPtr, Size
-            >() const
-            {
-                return hash_table_const_iterator<value_type, ConstRef, ConstPtr, size_type>{
-                    table_, idx_, max_idx_, current_
-                };
-            }
-
-        private:
-            hash_table_bucket<value_type, size_type>* table_;
-            size_type idx_;
-            size_type max_idx_;
-            list_node<value_type>* current_;
-    };
-
-    template<class Value, class Ref, class Ptr, class Size>
-    bool operator==(const hash_table_iterator<Value, Ref, Ptr, Size>& lhs,
-                    const hash_table_iterator<Value, Ref, Ptr, Size>& rhs)
-    {
-        return lhs.node() == rhs.node();
-    }
-
-    template<class Value, class Ref, class Ptr, class Size>
-    bool operator!=(const hash_table_iterator<Value, Ref, Ptr, Size>& lhs,
-                    const hash_table_iterator<Value, Ref, Ptr, Size>& rhs)
-    {
-        return !(lhs == rhs);
-    }
-
-    template<class Value, class ConstReference, class ConstPointer>
-    class hash_table_const_local_iterator
-    {
-        public:
-            using value_type      = Value;
-            using const_reference = ConstReference;
-            using const_pointer   = ConstPointer;
-            using difference_type = ptrdiff_t;
-
-            using iterator_category = forward_iterator_tag;
-
-            // TODO: requirement for forward iterator is default constructibility, fix others!
-            hash_table_const_local_iterator(const list_node<value_type>* head = nullptr,
-                                            const list_node<value_type>* current = nullptr)
-                : head_{head}, current_{current}
-            { /* DUMMY BODY */ }
-
-            hash_table_const_local_iterator(const hash_table_const_local_iterator&) = default;
-            hash_table_const_local_iterator& operator=(const hash_table_const_local_iterator&) = default;
-
-            const_reference operator*() const
-            {
-                return current_->value;
-            }
-
-            const_pointer operator->() const
-            {
-                return &current_->value;
-            }
-
-            hash_table_const_local_iterator& operator++()
-            {
-                current_ = current_->next;
-                if (current_ == head_)
-                    current_ = nullptr;
-
-                return *this;
-            }
-
-            hash_table_const_local_iterator operator++(int)
-            {
-                auto tmp = current_;
-                current_ = current_->next;
-                if (current_ == head_)
-                    current_ = nullptr;
-
-                return hash_table_const_local_iterator{head_, tmp};
-            }
-
-
-            list_node<value_type>* node()
-            {
-                return const_cast<list_node<value_type>*>(current_);
-            }
-
-            const list_node<value_type>* node() const
-            {
-                return current_;
-            }
-
-        private:
-            const list_node<value_type>* head_;
-            const list_node<value_type>* current_;
-    };
-
-    template<class Value, class ConstRef, class ConstPtr>
-    bool operator==(const hash_table_const_local_iterator<Value, ConstRef, ConstPtr>& lhs,
-                    const hash_table_const_local_iterator<Value, ConstRef, ConstPtr>& rhs)
-    {
-        return lhs.node() == rhs.node();
-    }
-
-    template<class Value, class ConstRef, class ConstPtr>
-    bool operator!=(const hash_table_const_local_iterator<Value, ConstRef, ConstPtr>& lhs,
-                    const hash_table_const_local_iterator<Value, ConstRef, ConstPtr>& rhs)
-    {
-        return !(lhs == rhs);
-    }
-
-    template<class Value, class Reference, class Pointer>
-    class hash_table_local_iterator
-    {
-        public:
-            using value_type      = Value;
-            using reference       = Reference;
-            using pointer         = Pointer;
-            using difference_type = ptrdiff_t;
-
-            using iterator_category = forward_iterator_tag;
-
-            hash_table_local_iterator(list_node<value_type>* head = nullptr,
-                                      list_node<value_type>* current = nullptr)
-                : head_{head}, current_{current}
-            { /* DUMMY BODY */ }
-
-            hash_table_local_iterator(const hash_table_local_iterator&) = default;
-            hash_table_local_iterator& operator=(const hash_table_local_iterator&) = default;
-
-            reference operator*()
-            {
-                return current_->value;
-            }
-
-            pointer operator->()
-            {
-                return &current_->value;
-            }
-
-            hash_table_local_iterator& operator++()
-            {
-                current_ = current_->next;
-                if (current_ == head_)
-                    current_ = nullptr;
-
-                return *this;
-            }
-
-            hash_table_local_iterator operator++(int)
-            {
-                auto tmp = current_;
-                current_ = current_->next;
-                if (current_ == head_)
-                    current_ = nullptr;
-
-                return hash_table_local_iterator{head_, tmp};
-            }
-
-            list_node<value_type>* node()
-            {
-                return current_;
-            }
-
-            const list_node<value_type>* node() const
-            {
-                return current_;
-            }
-
-            template<class ConstRef, class ConstPtr>
-            operator hash_table_const_local_iterator<
-                Value, ConstRef, ConstPtr
-            >() const
-            {
-                return hash_table_const_local_iterator<
-                    value_type, ConstRef, ConstPtr
-                >{head_, current_};
-            }
-
-        private:
-            list_node<value_type>* head_;
-            list_node<value_type>* current_;
-    };
-
-    template<class Value, class Ref, class Ptr>
-    bool operator==(const hash_table_local_iterator<Value, Ref, Ptr>& lhs,
-                    const hash_table_local_iterator<Value, Ref, Ptr>& rhs)
-    {
-        return lhs.node() == rhs.node();
-    }
-
-    template<class Value, class Ref, class Ptr>
-    bool operator!=(const hash_table_local_iterator<Value, Ref, Ptr>& lhs,
-                    const hash_table_local_iterator<Value, Ref, Ptr>& rhs)
-    {
-        return !(lhs == rhs);
-    }
 
     template<
