#include <userver/rcu/rcu_map.hpp>

Detailed Description

template<typename Key, typename Value, typename RcuMapTraits>
class rcu::RcuMap< Key, Value, RcuMapTraits >

Map-like structure allowing RCU keyset updates.

Only keyset changes are thread-safe in scope of this class. Values are stored in std::shared_ptrs and are not copied during keyset change. The map itself is implemented as rcu::Variable, so every keyset change (e.g. insert or erase) triggers the whole map copying.

Warning: Inserting N elements one by one requires O(N^2) operations because each insertion copies the whole map.

Writer access is protected by RcuMapTraits::MutexType. The default rcu::DefaultRcuMapTraits selects engine::Mutex. With it and other regular mutex types, concurrent keyset changes are serialized for the whole map. Read-modify-write operations first acquire the mutex and then copy the latest committed map snapshot, so they include changes made by preceding writers. The mutex is held until the new snapshot is committed or discarded, while readers continue using an older snapshot without waiting. This guarantee concerns copying the map snapshot; preparation of a candidate Value is documented by each insertion method separately.

Note: No synchronization is provided for value access, it must be implemented by Value when necessary.

Example usage:

    struct Data {
        // Access to RcuMap content must be synchronized via std::atomic
        // or other synchronization primitives
        std::atomic<int> x{0};
        std::atomic<bool> flag{false};
    };
    rcu::RcuMap<std::string, Data> map;
 
    // If the key is not in the dictionary,
    // then a default object will be created
    map["123"]->x++;
    map["other_data"]->flag = true;
    ASSERT_EQ(map["123"]->x.load(), 1);
    ASSERT_EQ(map["123"]->flag.load(), false);
    ASSERT_EQ(map["other_data"]->x.load(), 0);
    ASSERT_EQ(map["other_data"]->flag.load(), true);

See also: Synchronization Primitives

Definition at line 124 of file rcu_map.hpp.

Classes
struct	InsertReturnTypeImpl

Public Types
using	Hash = typename RcuMapTraits::Hash
using	KeyEqual = typename RcuMapTraits::KeyEqual
using	MutexType = typename RcuMapTraits::MutexType
using	ValuePtr = std::shared_ptr<Value>
using	Iterator = RcuMapIterator<Key, Value, Value, RcuMapTraits>
using	ConstValuePtr = std::shared_ptr<const Value>
using	ConstIterator = RcuMapIterator<Key, Value, const Value, RcuMapTraits>
using	RawMap = std::unordered_map<Key, ValuePtr, Hash, KeyEqual>
using	Snapshot = std::unordered_map<Key, ConstValuePtr, Hash, KeyEqual>
using	InsertReturnType = InsertReturnTypeImpl<ValuePtr>

Public Member Functions
	RcuMap (const RcuMap &)=delete
	RcuMap (RcuMap &&)=delete
RcuMap &	operator= (const RcuMap &)=delete
RcuMap &	operator= (RcuMap &&)=delete
std::size_t	SizeApprox () const
	Returns an estimated size of the map at some point in time.
const utils::NotNull< ConstValuePtr >	operator[] (const Key &) const
	Returns a readonly value pointer by its key if exists.
const utils::NotNull< ValuePtr >	operator[] (const Key &)
	Returns a modifiable value pointer by key if exists or default-creates one.
InsertReturnType	Insert (const Key &key, ValuePtr value)
	Inserts a new element into the container if there is no element with the key in the container. Returns a pair consisting of a pointer to the inserted element, or the already-existing element if no insertion happened, and a bool denoting whether the insertion took place.
template<typename... Args>
InsertReturnType	Emplace (const Key &key, Args &&... args)
	Inserts a new element into the container constructed in-place with the given args if there is no element with the key in the container. Returns a pair consisting of a pointer to the inserted element, or the already-existing element if no insertion happened, and a bool denoting whether the insertion took place.
template<typename... Args>
InsertReturnType	TryEmplace (const Key &key, Args &&... args)
	If a key equivalent to key already exists in the container, does nothing. Otherwise, constructs a Value from the given args and inserts it into the map. Returns a pair consisting of a pointer to the inserted element, or the already-existing element if no insertion happened, and a bool denoting whether the insertion took place.
template<typename RawKey>
void	InsertOrAssign (RawKey &&key, ValuePtr value)
	If a key equivalent to key already exists in the container, replaces the associated value. Otherwise, inserts a new pair into the map.
template<typename CompatibleKey = Key>
const ConstValuePtr	Get (const CompatibleKey &key) const
	Returns a readonly value pointer by its key; nullptr (a default constructed ConstValuePtr) if no such key Supports heterogeneous lookup when RcuMapTraits provide transparent Hash and KeyEqual.
template<typename CompatibleKey = Key>
const ValuePtr	Get (const CompatibleKey &key)
	Returns a modifiable value pointer by key; nullptr (a default constructed ValuePtr) if no such key.
bool	Erase (const Key &)
	Removes a key from the map.
ValuePtr	Pop (const Key &)
	Removes a key from the map returning its value.
void	Clear ()
	Resets the map to an empty state.
void	Assign (RawMap new_map)
	Replace current data by data from new_map.
rcu::WritablePtr< RawMap, RcuTraits >	StartWrite ()
	Starts a transaction, used to perform a series of arbitrary changes to the map.
Snapshot	GetSnapshot () const
	Returns a readonly copy of the map.
template<typename... Args>
RcuMap< K, V, RcuMapTraits >::InsertReturnType	Emplace (const K &key, Args &&... args)
template<typename... Args>
RcuMap< K, V, RcuMapTraits >::InsertReturnType	TryEmplace (const K &key, Args &&... args)
Iteration support
Keyset is fixed at the start of the iteration and is not affected by concurrent changes.
ConstIterator	begin () const
ConstIterator	end () const
Iterator	begin ()
Iterator	end ()

Member Typedef Documentation

◆ ConstIterator

template<typename Key, typename Value, typename RcuMapTraits>

using rcu::RcuMap< Key, Value, RcuMapTraits >::ConstIterator = RcuMapIterator<Key, Value, const Value, RcuMapTraits>

Definition at line 141 of file rcu_map.hpp.

◆ ConstValuePtr

template<typename Key, typename Value, typename RcuMapTraits>

using rcu::RcuMap< Key, Value, RcuMapTraits >::ConstValuePtr = std::shared_ptr<const Value>

Definition at line 140 of file rcu_map.hpp.

◆ Hash

template<typename Key, typename Value, typename RcuMapTraits>

using rcu::RcuMap< Key, Value, RcuMapTraits >::Hash = typename RcuMapTraits::Hash

Definition at line 135 of file rcu_map.hpp.

◆ InsertReturnType

template<typename Key, typename Value, typename RcuMapTraits>

using rcu::RcuMap< Key, Value, RcuMapTraits >::InsertReturnType = InsertReturnTypeImpl<ValuePtr>

Definition at line 144 of file rcu_map.hpp.

◆ Iterator

template<typename Key, typename Value, typename RcuMapTraits>

using rcu::RcuMap< Key, Value, RcuMapTraits >::Iterator = RcuMapIterator<Key, Value, Value, RcuMapTraits>

Definition at line 139 of file rcu_map.hpp.

◆ KeyEqual

template<typename Key, typename Value, typename RcuMapTraits>

using rcu::RcuMap< Key, Value, RcuMapTraits >::KeyEqual = typename RcuMapTraits::KeyEqual

Definition at line 136 of file rcu_map.hpp.

◆ MutexType

template<typename Key, typename Value, typename RcuMapTraits>

using rcu::RcuMap< Key, Value, RcuMapTraits >::MutexType = typename RcuMapTraits::MutexType

Definition at line 137 of file rcu_map.hpp.

◆ RawMap

template<typename Key, typename Value, typename RcuMapTraits>

using rcu::RcuMap< Key, Value, RcuMapTraits >::RawMap = std::unordered_map<Key, ValuePtr, Hash, KeyEqual>

Definition at line 142 of file rcu_map.hpp.

◆ Snapshot

template<typename Key, typename Value, typename RcuMapTraits>

using rcu::RcuMap< Key, Value, RcuMapTraits >::Snapshot = std::unordered_map<Key, ConstValuePtr, Hash, KeyEqual>

Definition at line 143 of file rcu_map.hpp.

◆ ValuePtr

template<typename Key, typename Value, typename RcuMapTraits>

using rcu::RcuMap< Key, Value, RcuMapTraits >::ValuePtr = std::shared_ptr<Value>

Definition at line 138 of file rcu_map.hpp.

Member Function Documentation

◆ Assign()

template<typename K, typename V, typename RcuMapTraits>

void rcu::RcuMap< K, V, RcuMapTraits >::Assign ( RawMap new_map )

Replace current data by data from new_map.

Definition at line 458 of file rcu_map.hpp.

◆ begin() [1/2]

template<typename K, typename V, typename RcuMapTraits>

RcuMap< K, V, RcuMapTraits >::Iterator rcu::RcuMap< K, V, RcuMapTraits >::begin ( )

Definition at line 285 of file rcu_map.hpp.

◆ begin() [2/2]

template<typename K, typename V, typename RcuMapTraits>

RcuMap< K, V, RcuMapTraits >::ConstIterator rcu::RcuMap< K, V, RcuMapTraits >::begin ( ) const

Definition at line 271 of file rcu_map.hpp.

◆ Clear()

template<typename K, typename V, typename RcuMapTraits>

void rcu::RcuMap< K, V, RcuMapTraits >::Clear ( )

Resets the map to an empty state.

Definition at line 453 of file rcu_map.hpp.

◆ Emplace() [1/2]

template<typename Key, typename Value, typename RcuMapTraits>

template<typename... Args>

RcuMap< K, V, RcuMapTraits >::InsertReturnType rcu::RcuMap< Key, Value, RcuMapTraits >::Emplace	(	const K &	key,
		Args &&...	args )

Definition at line 376 of file rcu_map.hpp.

◆ Emplace() [2/2]

template<typename Key, typename Value, typename RcuMapTraits>

template<typename... Args>

InsertReturnType rcu::RcuMap< Key, Value, RcuMapTraits >::Emplace	(	const Key &	key,
		Args &&...	args )

Inserts a new element into the container constructed in-place with the given args if there is no element with the key in the container. Returns a pair consisting of a pointer to the inserted element, or the already-existing element if no insertion happened, and a bool denoting whether the insertion took place.

Note: Copies the whole map if the key doesn't exist.; The Value candidate is constructed before acquiring the writer mutex and may be discarded if another writer inserts an equivalent key first. rcu::RcuMap::TryEmplace avoids this extra construction.; The decisive presence check and insertion are serialized with other writers. Concurrent calls for equivalent keys don't overwrite each other: at most one can return inserted == true while the key remains present.

◆ end() [1/2]

template<typename K, typename V, typename RcuMapTraits>

RcuMap< K, V, RcuMapTraits >::Iterator rcu::RcuMap< K, V, RcuMapTraits >::end ( )

Definition at line 292 of file rcu_map.hpp.

◆ end() [2/2]

template<typename K, typename V, typename RcuMapTraits>

RcuMap< K, V, RcuMapTraits >::ConstIterator rcu::RcuMap< K, V, RcuMapTraits >::end ( ) const

Definition at line 278 of file rcu_map.hpp.

◆ Erase()

template<typename Key, typename Value, typename RcuMapTraits>

bool rcu::RcuMap< K, V, RcuMapTraits >::Erase ( const Key & )

Removes a key from the map.

Returns: whether the key was present

Note: Copies the whole map, might be slow for large maps.

Definition at line 429 of file rcu_map.hpp.

◆ Get() [1/2]

template<typename K, typename V, typename RcuMapTraits>

template<typename CompatibleKey>

const RcuMap< K, V, RcuMapTraits >::ValuePtr rcu::RcuMap< K, V, RcuMapTraits >::Get ( const CompatibleKey & key )

Returns a modifiable value pointer by key; nullptr (a default constructed ValuePtr) if no such key.

Definition at line 331 of file rcu_map.hpp.

◆ Get() [2/2]

template<typename K, typename V, typename RcuMapTraits>

template<typename CompatibleKey>

const RcuMap< K, V, RcuMapTraits >::ConstValuePtr rcu::RcuMap< K, V, RcuMapTraits >::Get ( const CompatibleKey & key ) const

Returns a readonly value pointer by its key; nullptr (a default constructed ConstValuePtr) if no such key Supports heterogeneous lookup when RcuMapTraits provide transparent Hash and KeyEqual.

Definition at line 321 of file rcu_map.hpp.

◆ GetSnapshot()

template<typename K, typename V, typename RcuMapTraits>

RcuMap< K, V, RcuMapTraits >::Snapshot rcu::RcuMap< K, V, RcuMapTraits >::GetSnapshot ( ) const

Returns a readonly copy of the map.

Note: Equivalent to {begin(), end()} construct, preferable for long-running operations.

Definition at line 468 of file rcu_map.hpp.

◆ Insert()

template<typename Key, typename Value, typename RcuMapTraits>

RcuMap< K, V, RcuMapTraits >::InsertReturnType rcu::RcuMap< K, V, RcuMapTraits >::Insert	(	const Key &	key,
		ValuePtr	value )

Inserts a new element into the container if there is no element with the key in the container. Returns a pair consisting of a pointer to the inserted element, or the already-existing element if no insertion happened, and a bool denoting whether the insertion took place.

Note: Copies the whole map if the key doesn't exist.; The supplied Value pointer may be discarded if another writer inserts an equivalent key before this operation acquires the writer mutex.; The decisive presence check and insertion are serialized with other writers. Concurrent calls for equivalent keys don't overwrite each other: at most one can return inserted == true while the key remains present.

Definition at line 362 of file rcu_map.hpp.

◆ InsertOrAssign()

template<typename Key, typename Value, typename RcuMapTraits>

template<typename RawKey>

void rcu::RcuMap< Key, Value, RcuMapTraits >::InsertOrAssign	(	RawKey &&	key,
		RcuMap< Key, Value, RcuMapTraits >::ValuePtr	value )

If a key equivalent to key already exists in the container, replaces the associated value. Otherwise, inserts a new pair into the map.

Note: Serialized with other write operations by the writer mutex. Concurrent assignments are applied one by one; the last committed assignment determines the value.

Definition at line 422 of file rcu_map.hpp.

◆ operator[]() [1/2]

template<typename Key, typename Value, typename RcuMapTraits>

const utils::NotNull< ValuePtr > rcu::RcuMap< Key, Value, RcuMapTraits >::operator[] ( const Key & )

Returns a modifiable value pointer by key if exists or default-creates one.

Note: Copies the whole map if the key doesn't exist.; The decisive presence check and insertion are serialized with other writers. Concurrent calls for the same missing key don't overwrite each other and return pointers to the same published value, unless another writer removes or replaces the key in between.

◆ operator[]() [2/2]

template<typename Key, typename Value, typename RcuMapTraits>

const utils::NotNull< ConstValuePtr > rcu::RcuMap< Key, Value, RcuMapTraits >::operator[] ( const Key & ) const

Returns a readonly value pointer by its key if exists.

Exceptions

MissingKeyException if the key is not present

◆ Pop()

template<typename Key, typename Value, typename RcuMapTraits>

RcuMap< K, V, RcuMapTraits >::ValuePtr rcu::RcuMap< K, V, RcuMapTraits >::Pop ( const Key & )

Removes a key from the map returning its value.

Returns: a value if the key was present, empty pointer otherwise

Note: Copies the whole map, might be slow for large maps.

Definition at line 441 of file rcu_map.hpp.

◆ SizeApprox()

template<typename K, typename V, typename RcuMapTraits>

std::size_t rcu::RcuMap< K, V, RcuMapTraits >::SizeApprox ( ) const

Returns an estimated size of the map at some point in time.

Definition at line 299 of file rcu_map.hpp.

◆ StartWrite()

template<typename K, typename V, typename RcuMapTraits>

auto rcu::RcuMap< K, V, RcuMapTraits >::StartWrite ( )

Starts a transaction, used to perform a series of arbitrary changes to the map.

Acquires the same writer mutex as all other map writes, then copies the latest committed map. The returned transaction owns the mutex until Commit or destruction, so concurrent write transactions proceed one by one. Readers don't wait for the transaction. Don't forget to Commit to apply the changes.

Definition at line 463 of file rcu_map.hpp.

◆ TryEmplace() [1/2]

template<typename Key, typename Value, typename RcuMapTraits>

template<typename... Args>

RcuMap< K, V, RcuMapTraits >::InsertReturnType rcu::RcuMap< Key, Value, RcuMapTraits >::TryEmplace	(	const K &	key,
		Args &&...	args )

Definition at line 404 of file rcu_map.hpp.

◆ TryEmplace() [2/2]

template<typename Key, typename Value, typename RcuMapTraits>

template<typename... Args>

InsertReturnType rcu::RcuMap< Key, Value, RcuMapTraits >::TryEmplace	(	const Key &	key,
		Args &&...	args )

If a key equivalent to key already exists in the container, does nothing. Otherwise, constructs a Value from the given args and inserts it into the map. Returns a pair consisting of a pointer to the inserted element, or the already-existing element if no insertion happened, and a bool denoting whether the insertion took place.

Note: After acquiring the writer mutex, the final presence check uses the latest committed map snapshot. Value construction happens only if this check succeeds, although function arguments are evaluated before the call. For concurrent calls with equivalent keys, at most one call can commit the insertion and return inserted == true; once it commits, the other calls return its value with inserted == false, unless another writer removes or replaces the key.

The documentation for this class was generated from the following files:

userver/rcu/fwd.hpp
userver/rcu/rcu_map.hpp

Detailed Description

Example usage:

Classes

Public Types

Public Member Functions

Member Typedef Documentation

◆ ConstIterator

◆ ConstValuePtr

◆ Hash

◆ InsertReturnType

◆ Iterator

◆ KeyEqual

◆ MutexType

◆ RawMap

◆ Snapshot

◆ ValuePtr

Member Function Documentation

◆ Assign()

◆ begin() [1/2]

◆ begin() [2/2]

◆ Clear()

◆ Emplace() [1/2]

◆ Emplace() [2/2]

◆ end() [1/2]

◆ end() [2/2]

◆ Erase()

◆ Get() [1/2]

◆ Get() [2/2]

◆ GetSnapshot()

◆ Insert()

◆ InsertOrAssign()

◆ operator[]() [1/2]

◆ operator[]() [2/2]

◆ Pop()

◆ SizeApprox()

◆ StartWrite()

◆ TryEmplace() [1/2]

◆ TryEmplace() [2/2]