#include <unordered_map_concurrent.h>

Classes
class	iterator

Public Types
typedef BINMAP	BinMap_t

typedef BINMAP::iterator	BinMap_iterator_t

using	key_type = KEY

Public Member Functions
	unordered_map_concurrent ()

	~unordered_map_concurrent ()

iterator	begin ()
	Return an interator pointing to the first entry in the map. More...

iterator	end ()

iterator	find (const KEY &key, bool do_lock=true)

std::pair< iterator, bool >	find_or_insert (const KEY &key, const VALUE &value, bool do_lock=true)

bool	retrieve (const KEY &key, VALUE &value, bool do_lock=true)

bool	insert_retrieve (const KEY &key, VALUE &value, VALUE &mapvalue, bool do_lock=true)

bool	insert (const KEY &key, const VALUE &value, bool do_lock=true)

void	erase (const KEY &key, bool do_lock=true)

bool	empty ()
	Return true if the entire map is empty. More...

size_t	size ()
	Return the total number of entries in the map. More...

size_t	lock_bin (const KEY &key)

void	unlock_bin (size_t bin)

Static Public Member Functions
static constexpr size_t	nobin_mask ()

Detailed Description

template<class KEY, class VALUE, class HASH = std::hash<KEY>, class PRED = std::equal_to<KEY>, size_t BINS = 16, class BINMAP = std::unordered_map<KEY, VALUE, HASH, PRED>>
class unordered_map_concurrent< KEY, VALUE, HASH, PRED, BINS, BINMAP >

unordered_map_concurrent provides an unordered_map replacement that is optimized for concurrent access. Its principle of operation is similar to Java's ConcurrentHashMap.

With naive use of an unordered_map, multiple threads would have to lock a mutex of some kind to control access to the map, either with a unique full lock, or with a reader/writer lock. But as the number of threads contending for this shared resource rises, they end up locking each other out and the map becomes a thread bottleneck.

unordered_map_concurrent solves this problem by internally splitting the hash map into several disjoint bins, each of which is a standard unordered_map. For any given map item, the hash of its key determines both the bin as well as its hashing within the bin (i.e., we break a big hash map into lots of little hash maps, deterministically determined by the key). Thus, we should expect map entries to be spread more or less evenly among the bins. There is no mutex that locks the map as a whole; instead, each bin is locked individually. If the number of bins is larger than the typical number of threads, most of the time two (or more) threads accessing the map simultaneously will not be accessing the same bin, and therefore will not be contending for the same lock.

unordered_map_concurrent provides an iterator which points to an entry in the map and also knows which bin it is in and implicitly holds a lock on the bin. When the iterator is destroyed, the lock on that bin is released. When the iterator is incremented in such a way that it transitions from the last entry of its current bin to the first entry of the next bin, it will also release its current lock and obtain a lock on the next bin.

Definition at line 98 of file unordered_map_concurrent.h.