\p %MultiLevelHashMap is a multi-level array which has an internal structure similar to a tree:
@image html multilevel_hashset.png
The multi-level array differs from a tree in that each position on the tree could hold an array of nodes or a single node.
- A position that holds a single node is a \p dataNode which holds the hash value of a key and the value that is associated\r
- with that key; it is a simple struct holding two variables. A \p dataNode in the multi-level array could be marked.\r
- A \p markedDataNode refers to a pointer to a \p dataNode that has been bitmarked at the least significant bit (LSB)\r
- of the pointer to the node. This signifies that this \p dataNode is contended. An expansion must occur at this node;\r
- any thread that sees this \p markedDataNode will try to replace it with an \p arrayNode; which is a position that holds\r
- an array of nodes. The pointer to an \p arrayNode is differentiated from that of a pointer to a \p dataNode by a bitmark\r
- on the second-least significant bit.\r
-\r
- \p %MultiLevelHashMap multi-level array is similar to a tree in that we keep a pointer to the root, which is a memory array\r
- called \p head. The length of the \p head memory array is unique, whereas every other \p arrayNode has a uniform length;\r
- a normal \p arrayNode has a fixed power-of-two length equal to the binary logarithm of a variable called \p arrayLength.\r
- The maximum depth of the tree, \p maxDepth, is the maximum number of pointers that must be followed to reach any node.\r
- We define \p currentDepth as the number of memory arrays that we need to traverse to reach the \p arrayNode on which\r
- we need to operate; this is initially one, because of \p head.\r
-\r
- That approach to the structure of the hash map uses an extensible hashing scheme; <b> the hash value is treated as a bit\r
- string</b> and rehash incrementally.\r
-\r
- @note Two important things you should keep in mind when you're using \p %MultiLevelHashMap:\r
- - all keys is converted to fixed-size bit-string by hash functor provided. \r
- You can use variable-length keys, for example, \p std::string as a key for \p %MultiLevelHashMap,\r
- but real key in the map will be fixed-ize hash values of your keys.\r
- For the strings you may use well-known hashing algorithms like <a href="https://en.wikipedia.org/wiki/Secure_Hash_Algorithm">SHA1, SHA2</a>,\r
- <a href="https://en.wikipedia.org/wiki/MurmurHash">MurmurHash</a>, <a href="https://en.wikipedia.org/wiki/CityHash">CityHash</a> \r
- or its successor <a href="https://code.google.com/p/farmhash/">FarmHash</a> and so on, which\r
- converts variable-length strings to fixed-length bit-strings, and such hash values will be the keys in \p %MultiLevelHashMap.\r
- - \p %MultiLevelHashMap uses a perfect hashing. It means that if two different keys, for example, of type \p std::string,\r
- have identical hash then you cannot insert both that keys in the map. \p %MultiLevelHashMap does not maintain the key,\r
- it maintains its fixed-size hash value.\r
-\r
- The map supports @ref cds_container_MultilevelHashMap_iterators "bidirectional thread-safe iterators".\r
-\r
- Template parameters:\r
- - \p GC - safe memory reclamation schema. Can be \p gc::HP, \p gc::DHP or one of \ref cds_urcu_type "RCU type"\r
- - \p Key - a key type to be stored in the map\r
- - \p T - a value type to be stored in the map\r
- - \p Traits - type traits, the structure based on \p multilevel_hashmap::traits or result of \p multilevel_hashmap::make_traits metafunction.\r
-\r
+ A position that holds a single node is a \p dataNode which holds the hash value of a key and the value that is associated
+ with that key; it is a simple struct holding two variables. A \p dataNode in the multi-level array could be marked.
+ A \p markedDataNode refers to a pointer to a \p dataNode that has been bitmarked at the least significant bit (LSB)
+ of the pointer to the node. This signifies that this \p dataNode is contended. An expansion must occur at this node;
+ any thread that sees this \p markedDataNode will try to replace it with an \p arrayNode; which is a position that holds
+ an array of nodes. The pointer to an \p arrayNode is differentiated from that of a pointer to a \p dataNode by a bitmark
+ on the second-least significant bit.
+
+ \p %MultiLevelHashMap multi-level array is similar to a tree in that we keep a pointer to the root, which is a memory array
+ called \p head. The length of the \p head memory array is unique, whereas every other \p arrayNode has a uniform length;
+ a normal \p arrayNode has a fixed power-of-two length equal to the binary logarithm of a variable called \p arrayLength.
+ The maximum depth of the tree, \p maxDepth, is the maximum number of pointers that must be followed to reach any node.
+ We define \p currentDepth as the number of memory arrays that we need to traverse to reach the \p arrayNode on which
+ we need to operate; this is initially one, because of \p head.
+
+ That approach to the structure of the hash map uses an extensible hashing scheme; <b> the hash value is treated as a bit
+ string</b> and rehash incrementally.
+
+ @note Two important things you should keep in mind when you're using \p %MultiLevelHashMap:
+ - all keys is converted to fixed-size bit-string by hash functor provided.
+ You can use variable-length keys, for example, \p std::string as a key for \p %MultiLevelHashMap,
+ but real key in the map will be fixed-ize hash values of your keys.
+ For the strings you may use well-known hashing algorithms like <a href="https://en.wikipedia.org/wiki/Secure_Hash_Algorithm">SHA1, SHA2</a>,
+ <a href="https://en.wikipedia.org/wiki/MurmurHash">MurmurHash</a>, <a href="https://en.wikipedia.org/wiki/CityHash">CityHash</a>
+ or its successor <a href="https://code.google.com/p/farmhash/">FarmHash</a> and so on, which
+ converts variable-length strings to fixed-length bit-strings, and such hash values will be the keys in \p %MultiLevelHashMap.
+ - \p %MultiLevelHashMap uses a perfect hashing. It means that if two different keys, for example, of type \p std::string,
+ have identical hash then you cannot insert both that keys in the map. \p %MultiLevelHashMap does not maintain the key,
+ it maintains its fixed-size hash value.
+
+ The map supports @ref cds_container_MultilevelHashMap_iterators "bidirectional thread-safe iterators".
+
+ Template parameters:
+ - \p GC - safe memory reclamation schema. Can be \p gc::HP, \p gc::DHP or one of \ref cds_urcu_type "RCU type"
+ - \p Key - a key type to be stored in the map
+ - \p T - a value type to be stored in the map
+ - \p Traits - type traits, the structure based on \p multilevel_hashmap::traits or result of \p multilevel_hashmap::make_traits metafunction.
+
There are several specializations of \p %MultiLevelHashMap for each \p GC. You should include:
- <tt><cds/container/multilevel_hashmap_hp.h></tt> for \p gc::HP garbage collector
- <tt><cds/container/multilevel_hashmap_dhp.h></tt> for \p gc::DHP garbage collector
- <tt><cds/container/multilevel_hashmap_rcu.h></tt> for \ref cds_intrusive_MultiLevelHashMap_rcu "RCU type". RCU specialization
has a slightly different interface.
*/
- template <
+ template <
class GC
,typename Key
,typename T
#ifdef CDS_DOXYGEN_INVOKED
- ,class Traits = multilevel_hashmap::traits
+ ,class Traits = multilevel_hashmap::traits
#else
,class Traits
#endif
std::pair<bool, bool> update( K&& key, Func func, bool bInsert = true )
{
scoped_node_ptr sp( cxx_node_allocator().MoveNew( m_Hasher, std::forward<K>(key)));
- std::pair<bool, bool> result = base_class::do_update( *sp,
- [&func]( node_type& node, node_type * old ) { func( node.m_Value, old ? &old->m_Value : nullptr );},
+ std::pair<bool, bool> result = base_class::do_update( *sp,
+ [&func]( node_type& node, node_type * old ) { func( node.m_Value, old ? &old->m_Value : nullptr );},
bInsert );
if ( result.first )
sp.release();
//@endcond
/// Extracts the item from the map with specified \p key
- /**
+ /**
The function searches an item with key equal to <tt>hash( key_type( key ))</tt> in the map,
unlinks it from the map, and returns a guarded pointer to the item found.
If \p key is not found the function returns an empty guarded pointer.
public:
///@name Thread-safe iterators
/** @anchor cds_container_MultilevelHashMap_iterators
- The map supports thread-safe iterators: you may iterate over the map in multi-threaded environment.\r
- It is guaranteed that the iterators will remain valid even if another thread deletes the node the iterator points to:\r
- Hazard Pointer embedded into the iterator object protects the node from physical reclamation.\r
-\r
- @note Since the iterator object contains hazard pointer that is a thread-local resource,\r
- the iterator should not be passed to another thread.\r
-\r
- Each iterator object supports the common interface:\r
- - dereference operators:\r
- @code\r
- value_type [const] * operator ->() noexcept\r
- value_type [const] & operator *() noexcept\r
- @endcode\r
- - pre-increment and pre-decrement. Post-operators is not supported\r
- - equality operators <tt>==</tt> and <tt>!=</tt>.\r
+ The map supports thread-safe iterators: you may iterate over the map in multi-threaded environment.
+ It is guaranteed that the iterators will remain valid even if another thread deletes the node the iterator points to:
+ Hazard Pointer embedded into the iterator object protects the node from physical reclamation.
+
+ @note Since the iterator object contains hazard pointer that is a thread-local resource,
+ the iterator should not be passed to another thread.
+
+ Each iterator object supports the common interface:
+ - dereference operators:
+ @code
+ value_type [const] * operator ->() noexcept
+ value_type [const] & operator *() noexcept
+ @endcode
+ - pre-increment and pre-decrement. Post-operators is not supported
+ - equality operators <tt>==</tt> and <tt>!=</tt>.
Iterators are equal iff they point to the same cell of the same array node.
- Note that for two iterators \p it1 and \p it2, the conditon <tt> it1 == it2 </tt>
+ Note that for two iterators \p it1 and \p it2, the conditon <tt> it1 == it2 </tt>
does not entail <tt> &(*it1) == &(*it2) </tt>
- - helper member function \p release() that clears internal hazard pointer.\r
+ - helper member function \p release() that clears internal hazard pointer.
After \p release() call the iterator points to \p nullptr but it still remain valid: further iterating is possible.
*/
///@{
return base_class::template init_begin<const_iterator>();
}
- /// Returns an iterator to the element following the last element of the map. This element acts as a placeholder; attempting to access it results in undefined behavior.
+ /// Returns an iterator to the element following the last element of the map. This element acts as a placeholder; attempting to access it results in undefined behavior.
iterator end()
{
return base_class::template init_end<iterator>();
}
- /// Returns a const iterator to the element following the last element of the map. This element acts as a placeholder; attempting to access it results in undefined behavior.
+ /// Returns a const iterator to the element following the last element of the map. This element acts as a placeholder; attempting to access it results in undefined behavior.
const_iterator end() const
{
return base_class::template init_end<const_iterator>();
}
- /// Returns a const iterator to the element following the last element of the map. This element acts as a placeholder; attempting to access it results in undefined behavior.
+ /// Returns a const iterator to the element following the last element of the map. This element acts as a placeholder; attempting to access it results in undefined behavior.
const_iterator cend()
{
return base_class::template init_end<const_iterator>();
projects / libcds.git / blobdiff