HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
unordered_map_concurrent< KEY, VALUE, HASH, PRED, BINS, BINMAP > Class Template Reference

#include <unordered_map_concurrent.h>

Classes

class  iterator
 

Public Types

typedef BINMAP BinMap_t
 
typedef BINMAP::iterator BinMap_iterator_t
 

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)
 
bool retrieve (const KEY &key, VALUE &value, 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)
 

Detailed Description

template<class KEY, class VALUE, class HASH = std::hash<KEY>, class PRED = std::equal_to<KEY>, size_t BINS = 16, class BINMAP = 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 76 of file unordered_map_concurrent.h.

Member Typedef Documentation

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

Definition at line 79 of file unordered_map_concurrent.h.

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

Definition at line 78 of file unordered_map_concurrent.h.

Constructor & Destructor Documentation

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

Definition at line 82 of file unordered_map_concurrent.h.

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

Definition at line 84 of file unordered_map_concurrent.h.

Member Function Documentation

template<class KEY , class VALUE , class HASH = std::hash<KEY>, class PRED = std::equal_to<KEY>, size_t BINS = 16, class BINMAP = unordered_map<KEY, VALUE, HASH, PRED>>
iterator unordered_map_concurrent< KEY, VALUE, HASH, PRED, BINS, BINMAP >::begin ( void  )
inline

Return an interator pointing to the first entry in the map.

Definition at line 260 of file unordered_map_concurrent.h.

template<class KEY , class VALUE , class HASH = std::hash<KEY>, class PRED = std::equal_to<KEY>, size_t BINS = 16, class BINMAP = unordered_map<KEY, VALUE, HASH, PRED>>
bool unordered_map_concurrent< KEY, VALUE, HASH, PRED, BINS, BINMAP >::empty ( void  )
inline

Return true if the entire map is empty.

Definition at line 369 of file unordered_map_concurrent.h.

template<class KEY , class VALUE , class HASH = std::hash<KEY>, class PRED = std::equal_to<KEY>, size_t BINS = 16, class BINMAP = unordered_map<KEY, VALUE, HASH, PRED>>
iterator unordered_map_concurrent< KEY, VALUE, HASH, PRED, BINS, BINMAP >::end ( void  )
inline

Return an iterator signifying the end of the map (no valid entry pointed to).

Definition at line 277 of file unordered_map_concurrent.h.

template<class KEY , class VALUE , class HASH = std::hash<KEY>, class PRED = std::equal_to<KEY>, size_t BINS = 16, class BINMAP = unordered_map<KEY, VALUE, HASH, PRED>>
void unordered_map_concurrent< KEY, VALUE, HASH, PRED, BINS, BINMAP >::erase ( const KEY &  key,
bool  do_lock = true 
)
inline

If the key is in the map, safely erase it. If do_lock is true, lock the bin containing key while doing this operation; if do_lock is false, assume that the caller already has the bin locked, so do no locking or unlocking.

Definition at line 357 of file unordered_map_concurrent.h.

template<class KEY , class VALUE , class HASH = std::hash<KEY>, class PRED = std::equal_to<KEY>, size_t BINS = 16, class BINMAP = unordered_map<KEY, VALUE, HASH, PRED>>
iterator unordered_map_concurrent< KEY, VALUE, HASH, PRED, BINS, BINMAP >::find ( const KEY &  key,
bool  do_lock = true 
)
inline

Search for key. If found, return an iterator referring to the element, otherwise, return an iterator that is equivalent to this->end(). If do_lock is true, lock the bin that we're searching and return the iterator in a locked state, and unlock the bin again if not found; however, if do_lock is false, assume that the caller already has the bin locked, so do no locking or unlocking and return an iterator that is unaware that it holds a lock.

Definition at line 291 of file unordered_map_concurrent.h.

template<class KEY , class VALUE , class HASH = std::hash<KEY>, class PRED = std::equal_to<KEY>, size_t BINS = 16, class BINMAP = unordered_map<KEY, VALUE, HASH, PRED>>
bool unordered_map_concurrent< KEY, VALUE, HASH, PRED, BINS, BINMAP >::insert ( const KEY &  key,
const VALUE &  value,
bool  do_lock = true 
)
inline

Insert <key,value> into the hash map if it's not already there. Return true if added, false if it was already present. If do_lock is true, lock the bin containing key while doing this operation; if do_lock is false, assume that the caller already has the bin locked, so do no locking or unlocking.

Definition at line 337 of file unordered_map_concurrent.h.

template<class KEY , class VALUE , class HASH = std::hash<KEY>, class PRED = std::equal_to<KEY>, size_t BINS = 16, class BINMAP = unordered_map<KEY, VALUE, HASH, PRED>>
size_t unordered_map_concurrent< KEY, VALUE, HASH, PRED, BINS, BINMAP >::lock_bin ( const KEY &  key)
inline

Expliticly lock the bin that will contain the key (regardless of whether there is such an entry in the map), and return its bin number.

Definition at line 377 of file unordered_map_concurrent.h.

template<class KEY , class VALUE , class HASH = std::hash<KEY>, class PRED = std::equal_to<KEY>, size_t BINS = 16, class BINMAP = unordered_map<KEY, VALUE, HASH, PRED>>
bool unordered_map_concurrent< KEY, VALUE, HASH, PRED, BINS, BINMAP >::retrieve ( const KEY &  key,
VALUE &  value,
bool  do_lock = true 
)
inline

Search for key. If found, return true and store the value. If not found, return false and do not alter value. If do_lock is true, read-lock the bin while we're searching, and release it before returning; however, if do_lock is false, assume that the caller already has the bin locked, so do no locking or unlocking.

Definition at line 317 of file unordered_map_concurrent.h.

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

Return the total number of entries in the map.

Definition at line 372 of file unordered_map_concurrent.h.

template<class KEY , class VALUE , class HASH = std::hash<KEY>, class PRED = std::equal_to<KEY>, size_t BINS = 16, class BINMAP = unordered_map<KEY, VALUE, HASH, PRED>>
void unordered_map_concurrent< KEY, VALUE, HASH, PRED, BINS, BINMAP >::unlock_bin ( size_t  bin)
inline

Explicitly unlock the specified bin (this assumes that the caller holds the lock).

Definition at line 386 of file unordered_map_concurrent.h.


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