linked_map.h

Go to the documentation of this file.

/*
Copyright (c) 2016 Alexei Novakov
https://github.com/novalexei

Distributed under the Boost Software License, Version 1.0.
http://boost.org/LICENSE_1_0.txt
*/
#ifndef SERVLET_LINKED_HASH_MAP_H
#define SERVLET_LINKED_HASH_MAP_H

#include <map>
#include <unordered_map>
#include <list>
#include <chrono>
#include <mutex>
#include <experimental/any>

#include <servlet/lib/optional.h>

namespace servlet
{

template<typename _Key, typename _Tp, typename _MT>
class linked_map
{
public:
    typedef _Key                        key_type;
    typedef _Tp                         mapped_type;
    typedef std::pair<const _Key&, _Tp> value_type;

    typedef linked_map<_Key, _Tp, _MT>  self_type;
    typedef std::list<value_type>       list_type;
    typedef _MT                         map_type;

    typedef typename map_type::allocator_type    allocator_type;
    typedef          value_type&                 reference;
    typedef          const value_type&           const_reference;
    typedef          value_type*                 pointer;
    typedef          const value_type*           const_pointer;
    typedef typename map_type::size_type         size_type;
    typedef typename map_type::difference_type   difference_type;

    typedef typename list_type::iterator               iterator;
    typedef typename list_type::const_iterator         const_iterator;
    typedef typename list_type::reverse_iterator       reverse_iterator;
    typedef typename list_type::const_reverse_iterator const_reverse_iterator;

    linked_map() = default;
    linked_map(const linked_map& m) = default;
    linked_map(linked_map&& m) = default;

    ~linked_map() = default;

    linked_map& operator=(const linked_map& m) = default;
    linked_map& operator=(linked_map&& m) = default;

    bool empty() const noexcept { return _map.empty(); }
    size_type size() const noexcept { return _map.size(); }

    template<typename KeyType>
    bool contains_key(const KeyType &key) const { return _map.find(key) != _map.end(); }

    void clear()
    {
        _map.clear();
        _list.clear();
    }

    template<typename KeyType>
    optional_ref<const mapped_type> get(const KeyType& key) const
    {
        auto it = _map.find(key);
        if (it == _map.end()) return optional_ref<const mapped_type>{};
        _list.splice(_list.cend(), _list, it->second);
        update(*it->second);
        return optional_ref<const mapped_type>{it->second->second};
    }
    template<typename KeyType>
    optional_ref<mapped_type> get(const KeyType& key)
    {
        auto it = _map.find(key);
        if (it == _map.end()) return optional_ref<mapped_type>{};
        _list.splice(_list.cend(), _list, it->second);
        update(*it->second);
        return optional_ref<mapped_type>{it->second->second};
    }

    template<class... Args>
    bool put(key_type&& key, Args &&... args)
    {
        auto it = _map.find(key);
        bool found = it != _map.end();
        if (found)
        {
            _list.splice(_list.cend(), _list, it->second);
            it->second->second = mapped_type{std::forward<Args>(args)...};
        }
        else
        {
            auto pr = _map.emplace(std::move(key), _list.begin());
            _list.emplace_back(std::piecewise_construct,
                               std::forward_as_tuple(pr.first->first),
                               std::forward_as_tuple(std::forward<Args>(args)...));
            pr.first->second = --_list.end();
        }
        purge();
        return found;
    }
    template<class... Args>
    bool put(const key_type& key, Args &&... args)
    {
        auto it = _map.find(key);
        bool found = it != _map.end();
        if (found)
        {
            _list.splice(_list.cend(), _list, it->second);
            it->second->second = mapped_type{std::forward<Args>(args)...};
        }
        else
        {
            auto pr = _map.emplace(key, _list.begin());
            _list.emplace_back(std::piecewise_construct,
                               std::forward_as_tuple(pr.first->first),
                               std::forward_as_tuple(std::forward<Args>(args)...));
            pr.first->second = --_list.end();
        }
        purge();
        return found;
    }

    template<class... Args>
    bool try_put(key_type&& key, Args &&... args)
    {
        auto it = _map.find(key);
        if (it != _map.end()) return false;
        auto pr = _map.emplace(std::move(key), _list.begin());
        _list.emplace_back(std::piecewise_construct,
                           std::forward_as_tuple(pr.first->first),
                           std::forward_as_tuple(std::forward<Args>(args)...));
        pr.first->second = --_list.end();
        purge();
        return true;
    }
    template<class... Args>
    bool try_put(const key_type& key, Args &&... args)
    {
        auto it = _map.find(key);
        if (it != _map.end()) return false;
        auto pr = _map.emplace(key, _list.begin());
        _list.emplace_back(std::piecewise_construct,
                           std::forward_as_tuple(pr.first->first),
                           std::forward_as_tuple(std::forward<Args>(args)...));
        pr.first->second = --_list.end();
        purge();
        return true;
    }

    template<typename KeyType>
    bool erase(const KeyType &key)
    {
        auto it = _map.find(key);
        if (it == _map.end()) return false;
        _list.erase(it->second);
        _map.erase(it);
        purge();
        return true;
    }

    iterator begin() noexcept { return _list.begin(); }
    iterator end() noexcept { return _list.end(); }
    const_iterator begin() const noexcept { return _list.begin(); }
    const_iterator end() const noexcept { return _list.end(); }

    const_iterator cbegin() const noexcept { return _list.cbegin(); }
    const_iterator cend() const noexcept { return _list.cend(); }

    reverse_iterator rbegin() noexcept { return _list.rbegin(); }
    reverse_iterator rend() noexcept { return _list.rend(); }
    const_reverse_iterator rbegin() const noexcept { return _list.rbegin(); }
    const_reverse_iterator rend() const noexcept { return _list.rend(); }

    const_reverse_iterator crbegin() const noexcept { return _list.crbegin(); }
    const_reverse_iterator crend() const noexcept { return _list.crend(); }

protected:
    virtual void update(value_type& val) const { }
    virtual void purge() {}

private:
    map_type _map;
    mutable list_type _list;
};

template <typename _Key, typename _Value, typename _Compare = std::less<>,
          typename _Alloc = std::allocator<std::pair<const _Key,
                                                     typename std::list<std::pair<const _Key&, _Value>>::iterator>>>
using linked_tree_map = linked_map<_Key, _Value,
                                   std::map<_Key, typename std::list<std::pair<const _Key&, _Value>>::iterator,
                                            _Compare, _Alloc>>;

template <typename _Key, typename _Value, typename _Hash = std::hash<_Key>,
          typename _Pred = std::equal_to<_Key>,
          typename _Alloc = std::allocator<std::pair<const _Key,
                                                     typename std::list<std::pair<const _Key&, _Value>>::iterator>>>
using linked_hash_map = linked_map<_Key, _Value,
                                   std::unordered_map<_Key, typename std::list<std::pair<const _Key&, _Value>>::iterator,
                                                      _Hash, _Pred, _Alloc>>;

} // end of servlet namespace

#endif // SERVLET_LINKED_HASH_MAP_H