init_tower( nHeight, pTower );
}
- private:
- node_type() ; // no default ctor
+ node_type() = delete;
+ private:
void init_tower( unsigned int nHeight, atomic_marked_ptr * pTower )
{
if ( nHeight > 1 ) {
--- /dev/null
+//$$CDS-header$$
+
+#ifndef CDSLIB_CONTAINER_DETAILS_MULTILEVEL_HASHMAP_BASE_H
+#define CDSLIB_CONTAINER_DETAILS_MULTILEVEL_HASHMAP_BASE_H
+
+#include <cds/intrusive/details/multilevel_hashset_base.h>
+#include <cds/container/details/base.h>
+#include <cds/opt/hash.h>
+
+namespace cds { namespace container {
+ /// \p MultiLevelHashMap related definitions
+ /** @ingroup cds_nonintrusive_helper
+ */
+ namespace multilevel_hashmap {
+
+ /// \p MultiLevelHashMap internal statistics, see cds::intrusive::multilevel_hashset::stat
+ template <typename EventCounter = cds::atomicity::event_counter>
+ using stat = cds::intrusive::multilevel_hashset::stat< EventCounter >;
+
+ /// \p MultiLevelHashMap empty internal statistics
+ typedef cds::intrusive::multilevel_hashset::empty_stat empty_stat;
+
+ /// Bit-wise memcmp-based comparator for hash value \p T
+ template <typename T>
+ using bitwise_compare = cds::intrusive::multilevel_hashset::bitwise_compare< T >;
+
+ /// \p MultiLevelHashMap traits
+ struct traits
+ {
+ /// Hash functor, default is \p std::hash
+ /**
+ \p MultiLevelHashMap may use any hash functor converting key to
+ fixed-sized bit-string, for example, <a href="https://en.wikipedia.org/wiki/Secure_Hash_Algorithm">SHA1, SHA2</a>,\r
+ <a href="https://en.wikipedia.org/wiki/MurmurHash">MurmurHash</a>,\r
+ <a href="https://en.wikipedia.org/wiki/CityHash">CityHash</a>\r
+ or its successor <a href="https://code.google.com/p/farmhash/">FarmHash</a>.
+ */
+ typedef opt::none hash;
+
+ /// Hash comparing functor
+ /**
+ @copydetails cds::intrusive::multilevel_hashset::traits::compare
+ */
+ typedef cds::opt::none compare;
+
+ /// Specifies binary predicate used for hash compare.
+ /**
+ @copydetails cds::intrusive::multilevel_hashset::traits::less
+ */
+ typedef cds::opt::none less;
+
+ /// Item counter
+ /**
+ @copydetails cds::intrusive::multilevel_hashset::traits::item_counter
+ */
+ typedef cds::atomicity::item_counter item_counter;
+
+ /// Item allocator
+ /**
+ Default is \ref CDS_DEFAULT_ALLOCATOR
+ */
+ typedef CDS_DEFAULT_ALLOCATOR allocator;
+
+ /// Array node allocator
+ /**
+ @copydetails cds::intrusive::multilevel_hashset::traits::node_allocator
+ */
+ typedef CDS_DEFAULT_ALLOCATOR node_allocator;
+
+ /// C++ memory ordering model
+ /**
+ @copydetails cds::intrusive::multilevel_hashset::traits::memory_model
+ */
+ typedef cds::opt::v::relaxed_ordering memory_model;
+
+ /// Back-off strategy
+ typedef cds::backoff::Default back_off;
+
+ /// Internal statistics
+ /**
+ @copydetails cds::intrusive::multilevel_hashset::traits::stat
+ */
+ typedef empty_stat stat;
+
+ /// RCU deadlock checking policy (only for \ref cds_container_MultilevelHashSet_rcu "RCU-based MultilevelHashSet")
+ /**
+ @copydetails cds::intrusive::multilevel_hashset::traits::rcu_check_deadlock
+ */
+ typedef cds::opt::v::rcu_throw_deadlock rcu_check_deadlock;
+ };
+
+ /// Metafunction converting option list to \p multilevel_hashmap::traits
+ /**
+ Supported \p Options are:
+ - \p opt::hash - a hash functor, default is \p std::hash
+ @copydetails traits::hash
+ - \p opt::allocator - item allocator
+ @copydetails traits::allocator
+ - \p opt::node_allocator - array node allocator.
+ @copydetails traits::node_allocator
+ - \p opt::compare - hash comparison functor. No default functor is provided.
+ If the option is not specified, the \p opt::less is used.
+ - \p opt::less - specifies binary predicate used for hash comparison.
+ @copydetails cds::container::multilevel_hashmap::traits::less
+ - \p opt::back_off - back-off strategy used. If the option is not specified, the \p cds::backoff::Default is used.
+ - \p opt::item_counter - the type of item counting feature.
+ @copydetails cds::intrusive::multilevel_hashmap::traits::item_counter
+ - \p opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
+ or \p opt::v::sequential_consistent (sequentially consisnent memory model).
+ - \p opt::stat - internal statistics. By default, it is disabled (\p multilevel_hashmap::empty_stat).
+ To enable it use \p multilevel_hashmap::stat
+ - \p opt::rcu_check_deadlock - a deadlock checking policy for \ref cds_intrusive_MultilevelHashSet_rcu "RCU-based MultilevelHashSet"
+ Default is \p opt::v::rcu_throw_deadlock
+ */
+ template <typename... Options>
+ struct make_traits
+ {
+# ifdef CDS_DOXYGEN_INVOKED
+ typedef implementation_defined type ; ///< Metafunction result
+# else
+ typedef typename cds::opt::make_options<
+ typename cds::opt::find_type_traits< traits, Options... >::type
+ ,Options...
+ >::type type;
+# endif
+ };
+ } // namespace multilevel_hashmap
+
+ //@cond
+ // Forward declaration
+ template < class GC, typename Key, typename T, class Traits = multilevel_hashmap::traits >
+ class MultiLevelHashMap;
+ //@endcond
+
+ //@cond
+ namespace details {
+
+ template <typename GC, typename Key, typename T, typename Traits>
+ struct make_multilevel_hashmap
+ {
+ typedef GC gc;
+ typedef Key key_type;
+ typedef T mapped_type;
+ typedef Traits original_traits;
+ typedef typename cds::opt::v::hash_selector< typename original_traits::hash >::type hasher;
+
+ typedef typename std::decay<
+ typename std::remove_reference<
+ decltype( hasher()( std::declval<key_type>()) )
+ >::type
+ >::type hash_type;
+ //typedef typename std::result_of< hasher( std::declval<key_type>()) >::type hash_type;
+ static_assert( !std::is_pointer<hash_type>::value, "hash functor should return a reference to hash value" );
+
+ struct node_type
+ {
+ std::pair< key_type const, mapped_type> m_Value;
+ hash_type const m_hash;
+
+ node_type() = delete;
+ node_type( node_type const& ) = delete;
+
+ template <typename Q>
+ node_type( hasher& h, Q const& key )
+ : m_Value( std::make_pair( key, mapped_type()))
+ , m_hash( h( m_Value.first ))
+ {}
+
+ template <typename Q, typename U >
+ node_type( hasher& h, Q const& key, U const& val )
+ : m_Value( std::make_pair( key, val ))
+ , m_hash( h( m_Value.first ))
+ {}
+
+ template <typename Q, typename... Args>
+ node_type( hasher& h, Q&& key, Args&&... args )
+ : m_Value( std::forward<Q>(key), std::move( mapped_type( std::forward<Args>(args)... )))
+ , m_hash( h( m_Value.first ))
+ {}
+ };
+
+ typedef cds::details::Allocator< node_type, typename original_traits::allocator > cxx_node_allocator;
+
+ struct node_disposer
+ {
+ void operator()( node_type * p ) const
+ {
+ cxx_node_allocator().Delete( p );
+ }
+ };
+
+ struct get_node_hash
+ {
+ hash_type const& operator()( node_type const& n )
+ {
+ return n.m_hash;
+ }
+ };
+
+ struct intrusive_traits: public original_traits
+ {
+ typedef get_node_hash hash_accesor;
+ typedef node_disposer disposer;
+ };
+
+ // Metafunction result
+ typedef cds::intrusive::MultiLevelHashSet< GC, node_type, intrusive_traits > type;
+ };
+ } // namespace details
+ //@endcond
+
+}} // namespace cds::container
+
+#endif // #ifndef CDSLIB_CONTAINER_DETAILS_MULTILEVEL_HASHMAP_BASE_H
#include <cds/container/details/base.h>
namespace cds { namespace container {
- /// MultiLevelHashSet related definitions
+ /// \p MultiLevelHashSet related definitions
/** @ingroup cds_nonintrusive_helper
*/
namespace multilevel_hashset {
--- /dev/null
+//$$CDS-header$$
+
+#ifndef CDSLIB_CONTAINER_IMPL_MULTILEVEL_HASHMAP_H
+#define CDSLIB_CONTAINER_IMPL_MULTILEVEL_HASHMAP_H
+
+#include <cds/intrusive/impl/multilevel_hashset.h>
+#include <cds/container/details/multilevel_hashmap_base.h>
+
+namespace cds { namespace container {
+
+ /// Hash map based on multi-level array
+ /** @ingroup cds_nonintrusive_map
+ @anchor cds_container_MultilevelHashMap_hp
+
+ Source:
+ - [2013] Steven Feldman, Pierre LaBorde, Damian Dechev "Concurrent Multi-level Arrays:
+ Wait-free Extensible Hash Maps"
+
+ [From the paper] The hardest problem encountered while developing a parallel hash map is how to perform
+ a global resize, the process of redistributing the elements in a hash map that occurs when adding new
+ buckets. The negative impact of blocking synchronization is multiplied during a global resize, because all
+ threads will be forced to wait on the thread that is performing the involved process of resizing the hash map
+ and redistributing the elements. \p %MultilevelHashSet implementation avoids global resizes through new array
+ allocation. By allowing concurrent expansion this structure is free from the overhead of an explicit resize,
+ which facilitates concurrent operations.
+
+ The presented design includes dynamic hashing, the use of sub-arrays within the hash map data structure;
+ which, in combination with <b>perfect hashing</b>, means that each element has a unique final, as well as current, position.
+ It is important to note that the perfect hash function required by our hash map is trivial to realize as
+ any hash function that permutes the bits of the key is suitable. This is possible because of our approach
+ to the hash function; we require that it produces hash values that are equal in size to that of the key.
+ We know that if we expand the hash map a fixed number of times there can be no collision as duplicate keys
+ are not provided for in the standard semantics of a hash map.
+
+ \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 set 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 set. \p %MultiLevelHashMap does not maintain the key,\r
+ it maintains its fixed-size hash value.\r
+\r
+ The set 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
+ 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_MultiLevelHashSet_rcu "RCU type". RCU specialization
+ has a slightly different interface.
+ */
+ template <
+ class GC
+ ,typename Key
+ ,typename T
+#ifdef CDS_DOXYGEN_INVOKED
+ ,class Traits = multilevel_hashmap::traits
+#else
+ ,class Traits
+#endif
+ >
+ class MultiLevelHashMap
+#ifdef CDS_DOXYGEN_INVOKED
+ : protected cds::intrusive::MultiLevelHashSet< GC, std::pair<Key const, T>, Traits >
+#else
+ : protected cds::container::details::make_multilevel_hashmap< GC, Key, T, Hasher, Traits >::type
+#endif
+ {
+ //@cond
+ typedef cds::container::details::make_multilevel_hashmap< GC, Key, T, Hasher, Traits > maker;
+ typedef typename maker::type base_class;
+ //@endcond
+ public:
+ typedef GC gc; ///< Garbage collector
+ typedef Key key_type; ///< Key type
+ typedef T mapped_type; ///< Mapped type
+ typedef std::pair< key_type const, mapped_type> value_type; ///< Key-value pair to be stored in the map
+ typedef Traits traits; ///< Map traits
+#ifdef CDS_DOXYGEN_INVOKED
+ typedef typename traits::hash hasher; ///< Hash functor, see \p multilevel_hashmap::traits::hash
+#else
+ typedef typename maker::hasher hasher;
+#endif
+
+ typedef typename maker::hash_type hash_type; ///< Hash type deduced from \p hasher return type
+ typedef typename base_class::hash_comparator hash_comparator; ///< hash compare functor based on \p Traits::compare and \p Traits::less
+
+ typedef typename traits::item_counter item_counter; ///< Item counter type
+ typedef typename traits::allocator allocator; ///< Element allocator
+ typedef typename traits::node_allocator node_allocator; ///< Array node allocator
+ typedef typename traits::memory_model memory_model; ///< Memory model
+ typedef typename traits::back_off back_off; ///< Backoff strategy
+ typedef typename traits::stat stat; ///< Internal statistics type
+
+ typedef typename gc::template guarded_ptr< value_type > guarded_ptr; ///< Guarded pointer
+
+ /// Count of hazard pointers required
+ static CDS_CONSTEXPR size_t const c_nHazardPtrCount = base_class::c_nHazardPtrCount;
+
+ protected:
+ //@cond
+ typedef typename maker::node_type node_type;
+ typedef typename maker::cxx_node_allocator cxx_node_allocator;
+ typedef std::unique_ptr< node_type, typename maker::node_disposer > scoped_node_ptr;
+ //@endcond
+
+ protected:
+ //@cond
+ hasher m_Hasher;
+ //@endcond
+
+ public:
+ /// Creates empty map
+ /**
+ @param head_bits: 2<sup>head_bits</sup> specifies the size of head array, minimum is 4.
+ @param array_bits: 2<sup>array_bits</sup> specifies the size of array node, minimum is 2.
+
+ Equation for \p head_bits and \p array_bits:
+ \code
+ sizeof(hash_type) * 8 == head_bits + N * array_bits
+ \endcode
+ where \p N is multi-level array depth.
+ */
+ MultiLevelHashMap( size_t head_bits = 8, size_t array_bits = 4 )
+ : base_class( head_bits, array_bits )
+ {}
+
+ /// Destructs the map and frees all data
+ ~MultiLevelHashMap()
+ {}
+
+ /// Inserts new element with key and default value
+ /**
+ The function creates an element with \p key and default value, and then inserts the node created into the map.
+
+ Preconditions:
+ - The \p key_type should be constructible from a value of type \p K.
+ In trivial case, \p K is equal to \p key_type.
+ - The \p mapped_type should be default-constructible.
+
+ Returns \p true if inserting successful, \p false otherwise.
+ */
+ template <typename K>
+ bool insert( K const& key )
+ {
+ scoped_node_ptr sp( cxx_node_allocator().New( m_Hasher, key ));
+ if ( base_class::insert( *sp )) {
+ sp.release();
+ return true;
+ }
+ return false;
+ }
+
+ /// Inserts new element
+ /**
+ The function creates a node with copy of \p val value
+ and then inserts the node created into the map.
+
+ Preconditions:
+ - The \p key_type should be constructible from \p key of type \p K.
+ - The \p value_type should be constructible from \p val of type \p V.
+
+ Returns \p true if \p val is inserted into the set, \p false otherwise.
+ */
+ template <typename K, typename V>
+ bool insert( K const& key, V const& val )
+ {
+ scoped_node_ptr sp( cxx_node_allocator().New( m_Hasher, key, val ));
+ if ( base_class::insert( *sp )) {
+ sp.release();
+ return true;
+ }
+ return false;
+ }
+
+ /// Inserts new element and initialize it by a functor
+ /**
+ This function inserts new element with key \p key and if inserting is successful then it calls
+ \p func functor with signature
+ \code
+ struct functor {
+ void operator()( value_type& item );
+ };
+ \endcode
+
+ The argument \p item of user-defined functor \p func is the reference
+ to the map's item inserted:
+ - <tt>item.first</tt> is a const reference to item's key that cannot be changed.
+ - <tt>item.second</tt> is a reference to item's value that may be changed.
+
+ \p key_type should be constructible from value of type \p K.
+
+ The function allows to split creating of new item into two part:
+ - create item from \p key;
+ - insert new item into the map;
+ - if inserting is successful, initialize the value of item by calling \p func functor
+
+ This can be useful if complete initialization of object of \p value_type is heavyweight and
+ it is preferable that the initialization should be completed only if inserting is successful.
+ */
+ template <typename K, typename Func>
+ bool insert_with( K const& key, Func func )
+ {
+ scoped_node_ptr sp( cxx_node_allocator().New( m_Hasher, key ));
+ if ( base_class::insert( *sp, [&func]( node_type& item ) { func( item.m_Value ); } )) {
+ sp.release();
+ return true;
+ }
+ return false;
+ }
+
+ /// For key \p key inserts data of type \p value_type created in-place from <tt>std::forward<Args>(args)...</tt>
+ /**
+ Returns \p true if inserting successful, \p false otherwise.
+ */
+ template <typename K, typename... Args>
+ bool emplace( K&& key, Args&&... args )
+ {
+ scoped_node_ptr sp( cxx_node_allocator().New( m_Hasher, std::forward<K>(key), std::forward<Args>(args)... ));
+ if ( base_class::insert( *sp )) {
+ sp.release();
+ return true;
+ }
+ return false;
+ }
+
+ /// Updates data by \p key
+ /**
+ The operation performs inserting or changing data with lock-free manner.
+
+ If the \p key not found in the map, then the new item created from \p key
+ will be inserted into the map iff \p bInsert is \p true
+ (note that in this case the \ref key_type should be constructible from type \p K).
+ Otherwise, if \p key is found, the functor \p func is called with item found.
+ The functor \p Func signature:
+ \code
+ struct my_functor {
+ void operator()( bool bNew, value_type& item );
+ };
+ \endcode
+ where:
+ - \p bNew - \p true if the item has been inserted, \p false otherwise
+ - \p item - item of the map
+
+ The functor may change any fields of the \p item.second that is \ref value_type.
+
+ Returns <tt> std::pair<bool, bool> </tt> where \p first is \p true if operation is successfull,
+ \p second is \p true if new item has been added or \p false if \p key already exists.
+
+ @warning See \ref cds_intrusive_item_creating "insert item troubleshooting"
+ */
+ template <typename K, typename Func>
+ std::pair<bool, bool> update( K const& key, Func func, bool bInsert = true )
+ {
+ scoped_node_ptr sp( cxx_node_allocator().New( m_Hasher, key ));
+ std::pair<bool, bool> result = base_class::do_update( *sp, [&func]( bool bNew, node_type& node ) { func( bNew, node.m_Value );}, bInsert );
+ if ( !result.first )
+ sp.release();
+ return result;
+ }
+
+ /// Delete \p key from the map
+ /**
+ \p key_type must be constructible from value of type \p K.
+
+ Return \p true if \p key is found and deleted, \p false otherwise.
+ */
+ template <typename K>
+ bool erase( K const& key )
+ {
+ hash_type h = m_Hasher( key_type( key ));
+ return base_class::erase( h );
+ }
+
+ /// Delete \p key from the map
+ /**
+ The function searches an item with key \p key, calls \p f functor
+ and deletes the item. If \p key is not found, the functor is not called.
+
+ The functor \p Func interface:
+ \code
+ struct extractor {
+ void operator()(value_type& item) { ... }
+ };
+ \endcode
+ \p key_type must be constructible from value of type \p K.
+
+ Return \p true if key is found and deleted, \p false otherwise
+ */
+ template <typename K, typename Func>
+ bool erase( K const& key, Func f )
+ {
+ hash_type h = m_Hasher( key_type( key ));
+ return base_class::erase( h, [&f]( node_type& node) { f( node.m_Value ); } );
+ }
+
+ /// Deletes the element pointed by iterator \p iter
+ /**
+ Returns \p true if the operation is successful, \p false otherwise.
+
+ The function does not invalidate the iterator, it remains valid and can be used for further traversing.
+ */
+ bool erase_at( iterator const& iter )
+ {
+ //TODO
+ }
+
+
+ };
+
+}} // namespace cds::container
+
+#endif // #ifndef CDSLIB_CONTAINER_IMPL_MULTILEVEL_HASHMAP_H
typedef T mapped_type; ///< Mapped type
typedef Traits traits; ///< Map traits
# ifdef CDS_DOXYGEN_INVOKED
- typedef std::pair< K const, T> value_type; ///< Key-value pair to be stored in the map
+ typedef std::pair< Key const, T> value_type; ///< Key-value pair to be stored in the map
# else
typedef typename maker::value_type value_type;
# endif
it is preferable that the initialization should be completed only if inserting is successful.
*/
template <typename K, typename Func>
- bool insert_with( const K& key, Func func )
+ bool insert_with( K const& key, Func func )
{
scoped_node_ptr pNode( node_allocator().New( random_level(), key ));
if ( base_class::insert( *pNode, [&func]( node_type& item ) { func( item.m_Value ); } )) {
--- /dev/null
+//$$CDS-header$$
+
+#ifndef CDSLIB_CONTAINER_MULTILEVEL_HASHMAP_DHP_H
+#define CDSLIB_CONTAINER_MULTILEVEL_HASHMAP_DHP_H
+
+#include <cds/container/impl/multilevel_hashmap.h>
+#include <cds/gc/dhp.h>
+
+#endif // #ifndef CDSLIB_CONTAINER_MULTILEVEL_HASHMAP_DHP_H
--- /dev/null
+//$$CDS-header$$
+
+#ifndef CDSLIB_CONTAINER_MULTILEVEL_HASHMAP_HP_H
+#define CDSLIB_CONTAINER_MULTILEVEL_HASHMAP_HP_H
+
+#include <cds/container/impl/multilevel_hashmap.h>
+#include <cds/gc/hp.h>
+
+#endif // #ifndef CDSLIB_CONTAINER_MULTILEVEL_HASHMAP_HP_H
*/
std::pair<bool, bool> update( value_type& val, bool bInsert = true )
{
- hash_type const& hash = hash_accessor()( val );
- hash_splitter splitter( hash );
- hash_comparator cmp;
- typename gc::Guard guard;
- back_off bkoff;
-
- array_node * pArr = m_Head;
- size_t nSlot = splitter.cut( m_Metrics.head_node_size_log );
- assert( nSlot < m_Metrics.head_node_size );
- size_t nOffset = m_Metrics.head_node_size_log;
-
- while ( true ) {
- node_ptr slot = pArr->nodes[nSlot].load( memory_model::memory_order_acquire );
- if ( slot.bits() == flag_array_node ) {
- // array node, go down the tree
- assert( slot.ptr() != nullptr );
- nSlot = splitter.cut( m_Metrics.array_node_size_log );
- assert( nSlot < m_Metrics.array_node_size );
- pArr = to_array( slot.ptr() );
- nOffset += m_Metrics.array_node_size_log;
- }
- else if ( slot.bits() == flag_array_converting ) {
- // the slot is converting to array node right now
- bkoff();
- m_Stat.onSlotConverting();
- }
- else {
- // data node
- assert(slot.bits() == 0 );
-
- // protect data node by hazard pointer
- if ( guard.protect( pArr->nodes[nSlot], [](node_ptr p) -> value_type * { return p.ptr(); }) != slot ) {
- // slot value has been changed - retry
- m_Stat.onSlotChanged();
- }
- else if ( slot.ptr() ) {
- if ( cmp( hash, hash_accessor()( *slot.ptr() )) == 0 ) {
- // the item with that hash value already exists
- // Replace it with val
- if ( slot.ptr() == &val ) {
- m_Stat.onUpdateExisting();
- return std::make_pair( true, false );
- }
-
- if ( pArr->nodes[nSlot].compare_exchange_strong( slot, node_ptr( &val ), memory_model::memory_order_release, atomics::memory_order_relaxed )) {
- // slot can be disposed
- gc::template retire<disposer>( slot.ptr() );
- m_Stat.onUpdateExisting();
- return std::make_pair( true, false );
- }
-
- m_Stat.onUpdateRetry();
- continue;
- }
-
- // the slot must be expanded
- expand_slot( pArr, nSlot, slot, nOffset );
- }
- else {
- // the slot is empty, try to insert data node
- if ( bInsert ) {
- node_ptr pNull;
- if ( pArr->nodes[nSlot].compare_exchange_strong( pNull, node_ptr( &val ), memory_model::memory_order_release, atomics::memory_order_relaxed ))
- {
- // the new data node has been inserted
- ++m_ItemCounter;
- m_Stat.onUpdateNew();
- return std::make_pair( true, true );
- }
- }
- else {
- m_Stat.onUpdateFailed();
- return std::make_pair( false, false );
- }
-
- // insert failed - slot has been changed by another thread
- // retry updating
- m_Stat.onUpdateRetry();
- }
- }
- } // while
+ return do_update(val, [](bool, value_type&) {}, bInsert );
}
/// Unlinks the item \p val from the set
return false;
}
- /// Deletes the item pointed by iterator \p it
+ /// Deletes the item pointed by iterator \p iter
/**
Returns \p true if the operation is successful, \p false otherwise.
The function does not invalidate the iterator, it remains valid and can be used for further traversing.
*/
- bool erase_at( iterator const& it )
+ bool erase_at( iterator const& iter )
{
- if ( it.m_set != this )
+ if ( iter.m_set != this )
return false;
- if ( it.m_pNode == m_Head && it.m_idx >= head_size())
+ if ( iter.m_pNode == m_Head && iter.m_idx >= head_size())
return false;
- if ( it.m_idx >= array_node_size() )
+ if ( iter.m_idx >= array_node_size() )
return false;
for (;;) {
- node_ptr slot = it.m_pNode->nodes[it.m_idx].load( memory_model::memory_order_acquire );
- if ( slot.bits() == 0 && slot.ptr() == it.pointer() ) {
- if ( it.m_pNode->nodes[it.m_idx].compare_exchange_strong(slot, node_ptr(nullptr), memory_model::memory_order_acquire, atomics::memory_order_relaxed) ) {
+ node_ptr slot = iter.m_pNode->nodes[iter.m_idx].load( memory_model::memory_order_acquire );
+ if ( slot.bits() == 0 && slot.ptr() == iter.pointer() ) {
+ if ( iter.m_pNode->nodes[iter.m_idx].compare_exchange_strong(slot, node_ptr(nullptr), memory_model::memory_order_acquire, atomics::memory_order_relaxed) ) {
// the item is guarded by iterator, so we may retire it safely
gc::template retire<disposer>( slot.ptr() );
--m_ItemCounter;
m_Stat.onArrayNodeCreated();
return true;
}
+ //@endcond
+ protected:
+ //@cond
value_type * search( hash_type const& hash, typename gc::Guard& guard )
{
hash_splitter splitter( hash );
} // while
}
+ template <typename Func>
+ std::pair<bool, bool> do_update( value_type& val, Func f, bool bInsert = true )
+ {
+ hash_type const& hash = hash_accessor()( val );
+ hash_splitter splitter( hash );
+ hash_comparator cmp;
+ typename gc::Guard guard;
+ back_off bkoff;
+
+ array_node * pArr = m_Head;
+ size_t nSlot = splitter.cut( m_Metrics.head_node_size_log );
+ assert( nSlot < m_Metrics.head_node_size );
+ size_t nOffset = m_Metrics.head_node_size_log;
+
+ while ( true ) {
+ node_ptr slot = pArr->nodes[nSlot].load( memory_model::memory_order_acquire );
+ if ( slot.bits() == flag_array_node ) {
+ // array node, go down the tree
+ assert( slot.ptr() != nullptr );
+ nSlot = splitter.cut( m_Metrics.array_node_size_log );
+ assert( nSlot < m_Metrics.array_node_size );
+ pArr = to_array( slot.ptr() );
+ nOffset += m_Metrics.array_node_size_log;
+ }
+ else if ( slot.bits() == flag_array_converting ) {
+ // the slot is converting to array node right now
+ bkoff();
+ m_Stat.onSlotConverting();
+ }
+ else {
+ // data node
+ assert(slot.bits() == 0 );
+
+ // protect data node by hazard pointer
+ if ( guard.protect( pArr->nodes[nSlot], [](node_ptr p) -> value_type * { return p.ptr(); }) != slot ) {
+ // slot value has been changed - retry
+ m_Stat.onSlotChanged();
+ }
+ else if ( slot.ptr() ) {
+ if ( cmp( hash, hash_accessor()( *slot.ptr() )) == 0 ) {
+ // the item with that hash value already exists
+ // Replace it with val
+ if ( slot.ptr() == &val ) {
+ m_Stat.onUpdateExisting();
+ return std::make_pair( true, false );
+ }
+
+ if ( pArr->nodes[nSlot].compare_exchange_strong( slot, node_ptr( &val ), memory_model::memory_order_release, atomics::memory_order_relaxed )) {
+ // slot can be disposed
+ f( false, val );
+ gc::template retire<disposer>( slot.ptr() );
+ m_Stat.onUpdateExisting();
+ return std::make_pair( true, false );
+ }
+
+ m_Stat.onUpdateRetry();
+ continue;
+ }
+
+ // the slot must be expanded
+ expand_slot( pArr, nSlot, slot, nOffset );
+ }
+ else {
+ // the slot is empty, try to insert data node
+ if ( bInsert ) {
+ node_ptr pNull;
+ if ( pArr->nodes[nSlot].compare_exchange_strong( pNull, node_ptr( &val ), memory_model::memory_order_release, atomics::memory_order_relaxed ))
+ {
+ // the new data node has been inserted
+ f( true, val );
+ ++m_ItemCounter;
+ m_Stat.onUpdateNew();
+ return std::make_pair( true, true );
+ }
+ }
+ else {
+ m_Stat.onUpdateFailed();
+ return std::make_pair( false, false );
+ }
+
+ // insert failed - slot has been changed by another thread
+ // retry updating
+ m_Stat.onUpdateRetry();
+ }
+ }
+ } // while
+ }
//@endcond
};
}} // namespace cds::intrusive
<ClInclude Include="..\..\..\cds\container\details\michael_list_base.h" />\r
<ClInclude Include="..\..\..\cds\container\details\michael_map_base.h" />\r
<ClInclude Include="..\..\..\cds\container\details\michael_set_base.h" />\r
+ <ClInclude Include="..\..\..\cds\container\details\multilevel_hashmap_base.h" />\r
<ClInclude Include="..\..\..\cds\container\details\multilevel_hashset_base.h" />\r
<ClInclude Include="..\..\..\cds\container\details\skip_list_base.h" />\r
<ClInclude Include="..\..\..\cds\container\details\split_list_base.h" />\r
<ClInclude Include="..\..\..\cds\container\impl\lazy_list.h" />\r
<ClInclude Include="..\..\..\cds\container\impl\michael_kvlist.h" />\r
<ClInclude Include="..\..\..\cds\container\impl\michael_list.h" />\r
+ <ClInclude Include="..\..\..\cds\container\impl\multilevel_hashmap.h" />\r
<ClInclude Include="..\..\..\cds\container\impl\multilevel_hashset.h" />\r
<ClInclude Include="..\..\..\cds\container\impl\skip_list_map.h" />\r
<ClInclude Include="..\..\..\cds\container\impl\skip_list_set.h" />\r
<ClInclude Include="..\..\..\cds\container\michael_map_rcu.h" />\r
<ClInclude Include="..\..\..\cds\container\michael_set_rcu.h" />\r
<ClInclude Include="..\..\..\cds\container\mspriority_queue.h" />\r
+ <ClInclude Include="..\..\..\cds\container\multilevel_hashmap_dhp.h" />\r
+ <ClInclude Include="..\..\..\cds\container\multilevel_hashmap_hp.h" />\r
<ClInclude Include="..\..\..\cds\container\multilevel_hashset_dhp.h" />\r
<ClInclude Include="..\..\..\cds\container\multilevel_hashset_hp.h" />\r
<ClInclude Include="..\..\..\cds\container\skip_list_map_dhp.h" />\r
<ClInclude Include="..\..\..\cds\container\multilevel_hashset_dhp.h">\r
<Filter>Header Files\cds\container</Filter>\r
</ClInclude>\r
+ <ClInclude Include="..\..\..\cds\container\details\multilevel_hashmap_base.h">\r
+ <Filter>Header Files\cds\container\details</Filter>\r
+ </ClInclude>\r
+ <ClInclude Include="..\..\..\cds\container\impl\multilevel_hashmap.h">\r
+ <Filter>Header Files\cds\container\impl</Filter>\r
+ </ClInclude>\r
+ <ClInclude Include="..\..\..\cds\container\multilevel_hashmap_dhp.h">\r
+ <Filter>Header Files\cds\container</Filter>\r
+ </ClInclude>\r
+ <ClInclude Include="..\..\..\cds\container\multilevel_hashmap_hp.h">\r
+ <Filter>Header Files\cds\container</Filter>\r
+ </ClInclude>\r
</ItemGroup>\r
</Project>
\ No newline at end of file
projects / libcds.git / commitdiff