#include <sharded_unordered_map.hpp>

Public Types
using	iterator = basic_iterator< false >

using	const_iterator = basic_iterator< true >

Public Member Functions
range< iterator >	range_exclusive ()

range< const_iterator >	range_exclusive () const

std::size_t	estimate_size () const

std::size_t	size_exclusive () const

	conc_sharded_unordered_map (std::size_t shard_count=std::thread::hardware_concurrency() *2, Alloc const &alloc=Alloc())

	conc_sharded_unordered_map (conc_sharded_unordered_map const &)=delete

conc_sharded_unordered_map &	operator= (conc_sharded_unordered_map const &)=delete

	conc_sharded_unordered_map (conc_sharded_unordered_map &&)=delete

conc_sharded_unordered_map &	operator= (conc_sharded_unordered_map &&)=delete

	~conc_sharded_unordered_map ()=default

void	put (Key const &key, Value value)

template<typename Func>
void	put_exec (Key const &key, Func func)

template<typename Func>
bool	try_put_exec (Key const &key, Func func)

template<typename Func>
Value &	get_or_create (Key const &key, Func func)

template<typename Func>
Value &	get_or_init (Key const &key, Func func)

template<typename Func>
Value &	get_or_init_iter (Key const &key, Func func)

bool	try_put (Key const &key, Value value)

Value	get (Key const &key)

void	erase (Key const &key)

Detailed Description

template<typename Key, typename Value, typename Hash = std::hash< Key >, typename KeyEqual = std::equal_to< Key >, typename Alloc = std::allocator< std::pair< const Key, Value > >>
class rpnx::conc_sharded_unordered_map< Key, Value, Hash, KeyEqual, Alloc >

A sharded unordered map that serializes operations per shard.

Template Parameters

Key	The key type used to index values.
Value	The mapped value type.
Hash	The hash functor used to choose shards and hash keys inside each shard.
KeyEqual	The key equality predicate used inside each shard.
Alloc	The allocator used by the shard maps and rebound for shard storage.

Operations that access the container structure lock the affected shard. Methods that return a reference release that lock before returning; the caller is responsible for ensuring the referenced element is not erased, replaced, or otherwise concurrently modified while the reference is being used.

References to existing elements are not invalidated by inserting other elements into the map, including insertions that rehash the underlying std::unordered_map. They are invalidated by erasing the referenced element and by destroying the map.

Member Typedef Documentation

◆ const_iterator

template<typename Key, typename Value, typename Hash = std::hash< Key >, typename KeyEqual = std::equal_to< Key >, typename Alloc = std::allocator< std::pair< const Key, Value > >>

using rpnx::conc_sharded_unordered_map< Key, Value, Hash, KeyEqual, Alloc >::const_iterator = basic_iterator< true >

Const forward iterator type for exclusive whole-map iteration.

Note: Iterators are only safe to use with the range returned by range_exclusive() while no other thread is mutating the map.

◆ iterator

template<typename Key, typename Value, typename Hash = std::hash< Key >, typename KeyEqual = std::equal_to< Key >, typename Alloc = std::allocator< std::pair< const Key, Value > >>

using rpnx::conc_sharded_unordered_map< Key, Value, Hash, KeyEqual, Alloc >::iterator = basic_iterator< false >

Mutable forward iterator type for exclusive whole-map iteration.

Note: Iterators are only safe to use with the range returned by range_exclusive() while no other thread is mutating the map.

Constructor & Destructor Documentation

◆ conc_sharded_unordered_map() [1/3]

template<typename Key, typename Value, typename Hash = std::hash< Key >, typename KeyEqual = std::equal_to< Key >, typename Alloc = std::allocator< std::pair< const Key, Value > >>

rpnx::conc_sharded_unordered_map< Key, Value, Hash, KeyEqual, Alloc >::conc_sharded_unordered_map	(	std::size_t	shard_count = std::thread::hardware_concurrency() * 2,
		Alloc const &	alloc = Alloc() )

inlineexplicit

Constructs a sharded map.

Parameters

shard_count	Requested number of shards. If zero or not a power of two, it is rounded up to the next power of two so shard selection can use a mask.
alloc	Allocator used for the underlying unordered maps and rebound for shard storage.

◆ conc_sharded_unordered_map() [2/3]

template<typename Key, typename Value, typename Hash = std::hash< Key >, typename KeyEqual = std::equal_to< Key >, typename Alloc = std::allocator< std::pair< const Key, Value > >>

rpnx::conc_sharded_unordered_map< Key, Value, Hash, KeyEqual, Alloc >::conc_sharded_unordered_map ( conc_sharded_unordered_map< Key, Value, Hash, KeyEqual, Alloc > const & )

delete

Copy construction is disabled because shards contain mutexes and define synchronization ownership.

◆ conc_sharded_unordered_map() [3/3]

template<typename Key, typename Value, typename Hash = std::hash< Key >, typename KeyEqual = std::equal_to< Key >, typename Alloc = std::allocator< std::pair< const Key, Value > >>

rpnx::conc_sharded_unordered_map< Key, Value, Hash, KeyEqual, Alloc >::conc_sharded_unordered_map ( conc_sharded_unordered_map< Key, Value, Hash, KeyEqual, Alloc > && )

delete

Move construction is disabled so references and shard synchronization state cannot be relocated.

◆ ~conc_sharded_unordered_map()

template<typename Key, typename Value, typename Hash = std::hash< Key >, typename KeyEqual = std::equal_to< Key >, typename Alloc = std::allocator< std::pair< const Key, Value > >>

rpnx::conc_sharded_unordered_map< Key, Value, Hash, KeyEqual, Alloc >::~conc_sharded_unordered_map ( )

default

Destroys the map and all stored elements.

Precondition: No other thread may access the map or any reference obtained from it during destruction.

Member Function Documentation

◆ erase()

template<typename Key, typename Value, typename Hash = std::hash< Key >, typename KeyEqual = std::equal_to< Key >, typename Alloc = std::allocator< std::pair< const Key, Value > >>

void rpnx::conc_sharded_unordered_map< Key, Value, Hash, KeyEqual, Alloc >::erase ( Key const & key )

inline

Erases a key from the map.

Parameters

key	Key to erase if present.

Note: Any reference, pointer, or iterator to the erased element is invalidated. Callers must ensure no other thread is still using a reference returned by get_or_create(), get_or_init(), or get_or_init_iter() for this key.

◆ estimate_size()

template<typename Key, typename Value, typename Hash = std::hash< Key >, typename KeyEqual = std::equal_to< Key >, typename Alloc = std::allocator< std::pair< const Key, Value > >>

std::size_t rpnx::conc_sharded_unordered_map< Key, Value, Hash, KeyEqual, Alloc >::estimate_size ( ) const

inlinenodiscard

Estimates the number of elements in the map while locking each shard independently.

Returns: The sum of the shard sizes observed during the call.

Note: If no other threads are concurrently modifying the map, this method will always return the correct size.; This operation is thread-safe, but non-atomic. Because it works by non-atomically adding counts from each shard, the returned value may be sequentially inconsistent if other threads are concurrently modifying the map. For example, if a thread removes an element from shard 0 and then adds one to shard 5, the estimate_size() function may observe shard 0 before the removal and shard 5 after the insertion, resulting in an estimated size that is larger than the actual size was at any point in time.

◆ get()

template<typename Key, typename Value, typename Hash = std::hash< Key >, typename KeyEqual = std::equal_to< Key >, typename Alloc = std::allocator< std::pair< const Key, Value > >>

Value rpnx::conc_sharded_unordered_map< Key, Value, Hash, KeyEqual, Alloc >::get ( Key const & key )

inline

Returns a copy of the value for a key.

Parameters

key	Key to look up.

Returns: A copy of the stored value.

Exceptions

std::out_of_range if the key is absent.

Note: This operation locks only the shard selected by the key. The returned copy is independent of subsequent map operations.

◆ get_or_create()

template<typename Key, typename Value, typename Hash = std::hash< Key >, typename KeyEqual = std::equal_to< Key >, typename Alloc = std::allocator< std::pair< const Key, Value > >>

template<typename Func>

Value & rpnx::conc_sharded_unordered_map< Key, Value, Hash, KeyEqual, Alloc >::get_or_create	(	Key const &	key,
		Func	func )

inline

Returns the value for a key, creating it if missing.

Template Parameters

Func	Nullary callable type used to create the value when the key is absent.

Parameters

key	Key to look up or insert.
func	Callable invoked while the target shard is locked if the key is absent.

Returns: A reference to the stored value.

Note: The callable must not call back into this map for a key in the same shard, otherwise it may deadlock.; The shard lock is released before this function returns. Concurrent insertions of other keys do not invalidate the returned reference, but erasing this key, destroying the map, or concurrently modifying the same value while the reference is in use is not allowed unless Value provides its own synchronization.

◆ get_or_init()

template<typename Key, typename Value, typename Hash = std::hash< Key >, typename KeyEqual = std::equal_to< Key >, typename Alloc = std::allocator< std::pair< const Key, Value > >>

template<typename Func>

Value & rpnx::conc_sharded_unordered_map< Key, Value, Hash, KeyEqual, Alloc >::get_or_init	(	Key const &	key,
		Func	func )

inline

Returns the value for a key, default-constructing and initializing it if missing.

Template Parameters

Func	Callable type invoked as func(Value&) when the key is absent.

Parameters

key	Key to look up or insert.
func	Callable invoked while the target shard is locked to initialize a new value.

Returns: A reference to the stored value.

Note: If func throws, the newly inserted value is erased before the exception is rethrown.; The callable must not call back into this map for a key in the same shard, otherwise it may deadlock.; The shard lock is released before this function returns. Concurrent insertions of other keys do not invalidate the returned reference, but erasing this key, destroying the map, or concurrently modifying the same value while the reference is in use is not allowed unless Value provides its own synchronization.

◆ get_or_init_iter()

template<typename Key, typename Value, typename Hash = std::hash< Key >, typename KeyEqual = std::equal_to< Key >, typename Alloc = std::allocator< std::pair< const Key, Value > >>

template<typename Func>

Value & rpnx::conc_sharded_unordered_map< Key, Value, Hash, KeyEqual, Alloc >::get_or_init_iter	(	Key const &	key,
		Func	func )

inline

Returns the value for a key, default-constructing and initializing it with key/value access if missing.

Template Parameters

Func	Callable type invoked as func(Key const&, Value&) when the key is absent.

Parameters

key	Key to look up or insert.
func	Callable invoked while the target shard is locked to initialize a new value.

Returns: A reference to the stored value.

Note: If func throws, the newly inserted value is erased before the exception is rethrown.; The callable must not call back into this map for a key in the same shard, otherwise it may deadlock.; The shard lock is released before this function returns. Concurrent insertions of other keys do not invalidate the returned reference, but erasing this key, destroying the map, or concurrently modifying the same value while the reference is in use is not allowed unless Value provides its own synchronization.

◆ operator=() [1/2]

template<typename Key, typename Value, typename Hash = std::hash< Key >, typename KeyEqual = std::equal_to< Key >, typename Alloc = std::allocator< std::pair< const Key, Value > >>

conc_sharded_unordered_map & rpnx::conc_sharded_unordered_map< Key, Value, Hash, KeyEqual, Alloc >::operator= ( conc_sharded_unordered_map< Key, Value, Hash, KeyEqual, Alloc > && )

delete

Move assignment is disabled so references and shard synchronization state cannot be relocated.

◆ operator=() [2/2]

template<typename Key, typename Value, typename Hash = std::hash< Key >, typename KeyEqual = std::equal_to< Key >, typename Alloc = std::allocator< std::pair< const Key, Value > >>

conc_sharded_unordered_map & rpnx::conc_sharded_unordered_map< Key, Value, Hash, KeyEqual, Alloc >::operator= ( conc_sharded_unordered_map< Key, Value, Hash, KeyEqual, Alloc > const & )

delete

Copy assignment is disabled because shards contain mutexes and define synchronization ownership.

◆ put()

template<typename Key, typename Value, typename Hash = std::hash< Key >, typename KeyEqual = std::equal_to< Key >, typename Alloc = std::allocator< std::pair< const Key, Value > >>

void rpnx::conc_sharded_unordered_map< Key, Value, Hash, KeyEqual, Alloc >::put	(	Key const &	key,
		Value	value )

inline

Inserts or replaces the value for a key.

Parameters

key	Key to update.
value	Value to store.

Note: This operation locks only the shard selected by the key.; Replacing an existing key modifies that key's stored Value. Other threads must not concurrently use a reference to that Value unless Value provides its own synchronization.

◆ put_exec()

template<typename Key, typename Value, typename Hash = std::hash< Key >, typename KeyEqual = std::equal_to< Key >, typename Alloc = std::allocator< std::pair< const Key, Value > >>

template<typename Func>

void rpnx::conc_sharded_unordered_map< Key, Value, Hash, KeyEqual, Alloc >::put_exec	(	Key const &	key,
		Func	func )

inline

Computes and stores a value for a key, replacing any existing value.

Template Parameters

Func	Nullary callable type used to create the value.

Parameters

key	Key to update.
func	Callable invoked while the target shard is locked.

Note: The callable must not call back into this map for a key in the same shard, otherwise it may deadlock.; Replacing an existing key modifies that key's stored Value. Other threads must not concurrently use a reference to that Value unless Value provides its own synchronization.

◆ range_exclusive() [1/2]

template<typename Key, typename Value, typename Hash = std::hash< Key >, typename KeyEqual = std::equal_to< Key >, typename Alloc = std::allocator< std::pair< const Key, Value > >>

range< iterator > rpnx::conc_sharded_unordered_map< Key, Value, Hash, KeyEqual, Alloc >::range_exclusive ( )

inlinenodiscard

Returns a mutable range over all shards without locking.

Returns: A range that iterates over every element in the map.

Precondition: No other thread may mutate the map while the returned range or its iterators are used.

Note: This method is intended for exclusive access phases such as setup, teardown, or single-threaded inspection.

◆ range_exclusive() [2/2]

template<typename Key, typename Value, typename Hash = std::hash< Key >, typename KeyEqual = std::equal_to< Key >, typename Alloc = std::allocator< std::pair< const Key, Value > >>

range< const_iterator > rpnx::conc_sharded_unordered_map< Key, Value, Hash, KeyEqual, Alloc >::range_exclusive ( ) const

inlinenodiscard

Returns a const range over all shards without locking.

Returns: A range that iterates over every element in the map.

Precondition: No other thread may mutate the map while the returned range or its iterators are used.

Note: This method is intended for exclusive access phases such as setup, teardown, or single-threaded inspection.

◆ size_exclusive()

template<typename Key, typename Value, typename Hash = std::hash< Key >, typename KeyEqual = std::equal_to< Key >, typename Alloc = std::allocator< std::pair< const Key, Value > >>

std::size_t rpnx::conc_sharded_unordered_map< Key, Value, Hash, KeyEqual, Alloc >::size_exclusive ( ) const

inlinenodiscard

Returns the number of elements in the map without locking.

Returns: The total number of elements.

Precondition: No other thread may mutate the map while this function runs.

Note: Use estimate_size() when concurrent mutation is possible.

◆ try_put()

template<typename Key, typename Value, typename Hash = std::hash< Key >, typename KeyEqual = std::equal_to< Key >, typename Alloc = std::allocator< std::pair< const Key, Value > >>

bool rpnx::conc_sharded_unordered_map< Key, Value, Hash, KeyEqual, Alloc >::try_put	(	Key const &	key,
		Value	value )

inline

Inserts a value only if the key is absent.

Parameters

key	Key to insert.
value	Value to store if the key is absent.

Returns: true if a new value was inserted, otherwise false.

Note: This operation locks only the shard selected by the key.

◆ try_put_exec()

template<typename Key, typename Value, typename Hash = std::hash< Key >, typename KeyEqual = std::equal_to< Key >, typename Alloc = std::allocator< std::pair< const Key, Value > >>

template<typename Func>

bool rpnx::conc_sharded_unordered_map< Key, Value, Hash, KeyEqual, Alloc >::try_put_exec	(	Key const &	key,
		Func	func )

inline

Computes and stores a value only if the key is absent.

Template Parameters

Func	Nullary callable type used to create the value.

Parameters

key	Key to insert.
func	Callable invoked while the target shard is locked if the key is absent.

Returns: true if a new value was inserted, otherwise false.

Note: The callable must not call back into this map for a key in the same shard, otherwise it may deadlock.

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

include/rpnx/sharded_unordered_map.hpp

Public Types

Public Member Functions

Detailed Description

Member Typedef Documentation

◆ const_iterator

◆ iterator

Constructor & Destructor Documentation

◆ conc_sharded_unordered_map() [1/3]

◆ conc_sharded_unordered_map() [2/3]

◆ conc_sharded_unordered_map() [3/3]

◆ ~conc_sharded_unordered_map()

Member Function Documentation

◆ erase()

◆ estimate_size()

◆ get()

◆ get_or_create()

◆ get_or_init()

◆ get_or_init_iter()

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ put()

◆ put_exec()

◆ range_exclusive() [1/2]

◆ range_exclusive() [2/2]

◆ size_exclusive()

◆ try_put()

◆ try_put_exec()