just::thread Complete C++ Standard Thread Library by Just Software Solutions

jss::concurrent_map<> provides a lock-free hash map designed for concurrent access. All operations except construction and destruction are safe for concurrent access by up to 200 concurrent accessors (each thread calling a member function of concurrent_map, and each active iterator into the map counts as one accessor).

If the DataType is either an instantiation of std::atomic<> or jss::synchronized_value<>, or jss::has_synchronized_modifiers<DataType>::value is true then the mapped_type is DataType, consequently allowing concurrent modification of the value through an iterator. Otherwise, mapped_type is const DataType, thus preventing concurrent modification. Of course, values can still be replaced by calling insert_or_replace().

iterator is a Forward Iterator, with two additional operations: anchor() and is_deleted_node().

Calling anchor() guarantees that this iterator can be used as the end of a range, without danger of problems due to concurrent calls to insert_or_replace() or erase() on the map. If anchor() has not been called for a given iterator, then comparisons of that iterator with another will throw jss::concurrent_modification if the node referenced by that iterator has been deleted from the map. This is of specialized use: since the map is unordered, iteration across subranges is tricky, as the order of elements is not guaranteed. The iterator returned from end() is always an anchor.

is_deleted_node() can be used to check if the node referenced by the iterator is still part of the map, or has been deleted by a call to insert_or_replace() or erase(). If the return value is false then it cannot be relied upon to remain false if other threads may be erasing elements concurrently. A deleted node may still be accessed through an iterator that refers to it, but it is not reachable from any operation on the map.

namespace jss
{
    template<
        typename KeyType,typename DataType,typename Hasher=std::hash<_KeyType>,
        typename KeyEquals=std::equal_to<_KeyType> >
    class concurrent_map
    {
    public:
        concurrent_map(concurrent_map const&) = delete;
        concurrent_map& operator=(concurrent_map const&) = delete;

        typedef KeyType key_type;
        typedef possibly-const DataType mapped_type;
        typedef std::pair<const KeyType,mapped_type> value_type;
        typedef Hasher hasher;
        typedef KeyEquals key_equals;

        class iterator;

        explicit concurrent_map(
            Hasher const& hasher=Hasher(),
            KeyEquals const& equals=KeyEquals());

        ~concurrent_map();

        hasher hash_function() const;
        key_equals key_eq() const;

        unsigned size() const;
        bool empty() const;

        DataType at(KeyType const& key);
        DataType operator[](KeyType const& key);
        iterator find(KeyType const& key);

        template<typename KT,typename DT>
        std::pair<iterator,bool> emplace(KT && key,DT && data);
        std::pair<iterator,bool> insert(value_type const& val);

        template<typename KT,typename DT>
        void insert_or_replace(KT && key,DT && data);

        iterator erase(iterator const& it);
        iterator erase(iterator&& it);
        void erase(KeyType const& key);

        iterator begin();
        iterator end();
    };
}

Header

#include <jss/concurrent_map.hpp>

See Also