From 59af4764fbbd1b89e6c5ee268afc71d6f8fe1aa0 Mon Sep 17 00:00:00 2001 From: khizmax Date: Sun, 23 Aug 2015 13:40:43 +0300 Subject: [PATCH] - Refactored MultiLevelHashSet iterators - Added MultiLevelHashMap unit tests --- .../details/multilevel_hashmap_base.h | 10 +- cds/container/impl/multilevel_hashmap.h | 230 ++++++---- cds/intrusive/impl/multilevel_hashset.h | 246 +++++++---- projects/Win/vc12/hdr-test-map.vcxproj | 3 + .../Win/vc12/hdr-test-map.vcxproj.filters | 12 + projects/source.test-hdr.mk | 2 + tests/test-hdr/CMakeLists.txt | 2 + tests/test-hdr/map/hdr_multilevel_hashmap.h | 404 ++++++++++++++++++ .../map/hdr_multilevel_hashmap_dhp.cpp | 140 ++++++ .../map/hdr_multilevel_hashmap_hp.cpp | 140 ++++++ tests/test-hdr/set/hdr_multilevel_hashset.h | 8 - 11 files changed, 1022 insertions(+), 175 deletions(-) create mode 100644 tests/test-hdr/map/hdr_multilevel_hashmap.h create mode 100644 tests/test-hdr/map/hdr_multilevel_hashmap_dhp.cpp create mode 100644 tests/test-hdr/map/hdr_multilevel_hashmap_hp.cpp diff --git a/cds/container/details/multilevel_hashmap_base.h b/cds/container/details/multilevel_hashmap_base.h index ee24dfdb..aac4dce1 100644 --- a/cds/container/details/multilevel_hashmap_base.h +++ b/cds/container/details/multilevel_hashmap_base.h @@ -29,7 +29,7 @@ namespace cds { namespace container { { /// Hash functor, default is \p std::hash /** - \p MultiLevelHashMap may use any hash functor converting key to + \p MultiLevelHashMap may use any hash functor converting a key to fixed-sized bit-string, for example, SHA1, SHA2, MurmurHash, CityHash @@ -162,19 +162,19 @@ namespace cds { namespace container { template node_type( hasher& h, Q const& key ) - : m_Value( std::make_pair( key, mapped_type())) + : m_Value( std::move( std::make_pair( key, mapped_type()))) , m_hash( h( m_Value.first )) {} template node_type( hasher& h, Q const& key, U const& val ) - : m_Value( std::make_pair( key, val )) + : m_Value( std::move( std::make_pair( key, mapped_type(val)))) , m_hash( h( m_Value.first )) {} template node_type( hasher& h, Q&& key, Args&&... args ) - : m_Value( std::forward(key), std::move( mapped_type( std::forward(args)... ))) + : m_Value( std::move( std::make_pair( std::forward(key), std::move( mapped_type( std::forward(args)... ))))) , m_hash( h( m_Value.first )) {} }; @@ -199,7 +199,7 @@ namespace cds { namespace container { struct intrusive_traits: public original_traits { - typedef get_node_hash hash_accesor; + typedef get_node_hash hash_accessor; typedef node_disposer disposer; }; diff --git a/cds/container/impl/multilevel_hashmap.h b/cds/container/impl/multilevel_hashmap.h index 2ba9e363..4704240f 100644 --- a/cds/container/impl/multilevel_hashmap.h +++ b/cds/container/impl/multilevel_hashmap.h @@ -77,7 +77,7 @@ namespace cds { namespace container { There are several specializations of \p %MultiLevelHashMap for each \p GC. You should include: - for \p gc::HP garbage collector - for \p gc::DHP garbage collector - - for \ref cds_intrusive_MultiLevelHashSet_rcu "RCU type". RCU specialization + - for \ref cds_intrusive_MultiLevelHashMap_rcu "RCU type". RCU specialization has a slightly different interface. */ template < @@ -94,11 +94,11 @@ namespace cds { namespace container { #ifdef CDS_DOXYGEN_INVOKED : protected cds::intrusive::MultiLevelHashSet< GC, std::pair, Traits > #else - : protected cds::container::details::make_multilevel_hashmap< GC, Key, T, Hasher, Traits >::type + : protected cds::container::details::make_multilevel_hashmap< GC, Key, T, Traits >::type #endif { //@cond - typedef cds::container::details::make_multilevel_hashmap< GC, Key, T, Hasher, Traits > maker; + typedef cds::container::details::make_multilevel_hashmap< GC, Key, T, Traits > maker; typedef typename maker::type base_class; //@endcond public: @@ -132,88 +132,167 @@ namespace cds { namespace container { typedef typename maker::cxx_node_allocator cxx_node_allocator; typedef std::unique_ptr< node_type, typename maker::node_disposer > scoped_node_ptr; - template - class bidirectional_iterator : protected Iterator + template + class bidirectional_iterator: public base_class::iterator_base { friend class MultiLevelHashMap; - typedef Iterator base_class; + friend typename base_class; + typedef typename base_class::iterator_base iterator_base; + + protected: + static CDS_CONSTEXPR bool const c_bConstantIterator = IsConst; public: - typedef typename std::conditional< base_class::c_bConstantIterator, value_type const*, value_type*>::type value_ptr; ///< Value pointer - typedef typename std::conditional< base_class::c_bConstantIterator, value_type const&, value_type&>::type value_ref; ///< Value reference + typedef typename std::conditional< IsConst, value_type const*, value_type*>::type value_ptr; ///< Value pointer + typedef typename std::conditional< IsConst, value_type const&, value_type&>::type value_ref; ///< Value reference public: bidirectional_iterator() CDS_NOEXCEPT - : base_class() {} bidirectional_iterator( bidirectional_iterator const& rhs ) CDS_NOEXCEPT - : base_class( rhs ) + : iterator_base( rhs ) {} bidirectional_iterator& operator=(bidirectional_iterator const& rhs) CDS_NOEXCEPT { - base_class::operator=( rhs ); + iterator_base::operator=( rhs ); return *this; } bidirectional_iterator& operator++() { - base_class::operator++(); + iterator_base::operator++(); return *this; } bidirectional_iterator& operator--() { - base_class::operator--(); + iterator_base::operator--(); return *this; } value_ptr operator ->() const CDS_NOEXCEPT { - return pointer(); + node_type * p = iterator_base::pointer(); + return p ? &p->m_Value : nullptr; } value_ref operator *() const CDS_NOEXCEPT { - value_ptr p = pointer(); + node_type * p = iterator_base::pointer(); assert( p ); - return *p; + return p->m_Value; } void release() { - base_class::release(); + iterator_base::release(); } - template - bool operator ==(It const& rhs) const CDS_NOEXCEPT + template + bool operator ==(bidirectional_iterator const& rhs) const CDS_NOEXCEPT { - return base_class::operator==( rhs ); + return iterator_base::operator==( rhs ); } - template - bool operator !=(It const& rhs) const CDS_NOEXCEPT + template + bool operator !=(bidirectional_iterator const& rhs) const CDS_NOEXCEPT { return !( *this == rhs ); } protected: - bidirectional_iterator( base_class&& it ) CDS_NOEXCEPT - : base_class( it ) + bidirectional_iterator( base_class const& set, typename base_class::array_node * pNode, size_t idx, bool ) + : iterator_base( set, pNode, idx, false ) + {} + + bidirectional_iterator( base_class const& set, typename base_class::array_node * pNode, size_t idx ) + : iterator_base( set, pNode, idx ) + {} + }; + + /// Reverse bidirectional iterator + template + class reverse_bidirectional_iterator : public base_class::iterator_base + { + friend class MultiLevelHashMap; + friend typename base_class; + typedef typename base_class::iterator_base iterator_base; + + public: + typedef typename std::conditional< IsConst, value_type const*, value_type*>::type value_ptr; ///< Value pointer + typedef typename std::conditional< IsConst, value_type const&, value_type&>::type value_ref; ///< Value reference + + public: + reverse_bidirectional_iterator() CDS_NOEXCEPT + : iterator_base() + {} + + reverse_bidirectional_iterator( reverse_bidirectional_iterator const& rhs ) CDS_NOEXCEPT + : iterator_base( rhs ) {} - value_ptr pointer() const CDS_NOEXCEPT + reverse_bidirectional_iterator& operator=( reverse_bidirectional_iterator const& rhs) CDS_NOEXCEPT { - typename base_class::value_ptr p = base_class::pointer(); + iterator_base::operator=( rhs ); + return *this; + } + + reverse_bidirectional_iterator& operator++() + { + iterator_base::operator--(); + return *this; + } + + reverse_bidirectional_iterator& operator--() + { + iterator_base::operator++(); + return *this; + } + + value_ptr operator ->() const CDS_NOEXCEPT + { + node_type * p = iterator_base::pointer(); return p ? &p->m_Value : nullptr; } - - node_type * node_pointer() const CDS_NOEXCEPT + + value_ref operator *() const CDS_NOEXCEPT { - return base_class::pointer(); + node_type * p = iterator_base::pointer(); + assert( p ); + return p->m_Value; + } + + void release() + { + iterator_base::release(); + } + + template + bool operator ==(reverse_bidirectional_iterator const& rhs) const + { + return iterator_base::operator==( rhs ); + } + + template + bool operator !=(reverse_bidirectional_iterator const& rhs) + { + return !( *this == rhs ); + } + + protected: + reverse_bidirectional_iterator( base_class const& set, typename base_class::array_node * pNode, size_t idx, bool ) + : iterator_base( set, pNode, idx, false ) + {} + + reverse_bidirectional_iterator( base_class const& set, typename base_class::array_node * pNode, size_t idx ) + : iterator_base( set, pNode, idx, false ) + { + iterator_base::backward(); } }; + //@endcond public: @@ -221,7 +300,7 @@ namespace cds { namespace container { /// Guarded pointer typedef typename gc::template guarded_ptr< value_type > guarded_ptr; #else - typedef typename gc::template guarded_ptr< node_type, value_type, cds::details::guarded_ptr_cast_set > guarded_ptr; + typedef typename gc::template guarded_ptr< node_type, value_type, cds::container::details::guarded_ptr_cast_set > guarded_ptr; #endif #ifdef CDS_DOXYGEN_INVOKED @@ -230,10 +309,10 @@ namespace cds { namespace container { typedef implementation_defined reverse_iterator; ///< @ref cds_container_MultilevelHashMap_iterators "bidirectional reverse iterator" type typedef implementation_defined const_reverse_iterator; ///< @ref cds_container_MultilevelHashMap_iterators "bidirectional reverse const iterator" type #else - typedef bidirectional_iterator iterator; - typedef bidirectional_iterator const_iterator; - typedef bidirectional_iterator reverse_iterator; - typedef bidirectional_iterator const_reverse_iterator; + typedef bidirectional_iterator iterator; + typedef bidirectional_iterator const_iterator; + typedef reverse_bidirectional_iterator reverse_iterator; + typedef reverse_bidirectional_iterator const_reverse_iterator; #endif protected: @@ -273,9 +352,9 @@ namespace cds { namespace container { Returns \p true if inserting successful, \p false otherwise. */ template - bool insert( K const& key ) + bool insert( K&& key ) { - scoped_node_ptr sp( cxx_node_allocator().New( m_Hasher, key )); + scoped_node_ptr sp( cxx_node_allocator().MoveNew( m_Hasher, std::forward(key) )); if ( base_class::insert( *sp )) { sp.release(); return true; @@ -295,9 +374,9 @@ namespace cds { namespace container { Returns \p true if \p val is inserted into the map, \p false otherwise. */ template - bool insert( K const& key, V const& val ) + bool insert( K&& key, V&& val ) { - scoped_node_ptr sp( cxx_node_allocator().New( m_Hasher, key, val )); + scoped_node_ptr sp( cxx_node_allocator().MoveNew( m_Hasher, std::forward(key), std::forward(val))); if ( base_class::insert( *sp )) { sp.release(); return true; @@ -331,9 +410,9 @@ namespace cds { namespace container { it is preferable that the initialization should be completed only if inserting is successful. */ template - bool insert_with( K const& key, Func func ) + bool insert_with( K&& key, Func func ) { - scoped_node_ptr sp( cxx_node_allocator().New( m_Hasher, key )); + scoped_node_ptr sp( cxx_node_allocator().MoveNew( m_Hasher, std::forward(key))); if ( base_class::insert( *sp, [&func]( node_type& item ) { func( item.m_Value ); } )) { sp.release(); return true; @@ -348,7 +427,7 @@ namespace cds { namespace container { template bool emplace( K&& key, Args&&... args ) { - scoped_node_ptr sp( cxx_node_allocator().New( m_Hasher, std::forward(key), std::forward(args)... )); + scoped_node_ptr sp( cxx_node_allocator().MoveNew( m_Hasher, std::forward(key), std::forward(args)... )); if ( base_class::insert( *sp )) { sp.release(); return true; @@ -358,23 +437,24 @@ namespace cds { namespace container { /// Updates data by \p key /** - The operation performs inserting or changing data with lock-free manner. + The operation performs inserting or replacing the element 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. + Otherwise, if \p key is found, it is replaced with a new item created from + \p key. The functor \p Func signature: \code struct my_functor { - void operator()( bool bNew, value_type& item ); + void operator()( value_type& item, value_type * old ); }; \endcode where: - - \p bNew - \p true if the item has been inserted, \p false otherwise - \p item - item of the map + - \p old - old item of the map, if \p nullptr - the new item was inserted - The functor may change any fields of the \p item.second that is \ref value_type. + The functor may change any fields of the \p item.second. Returns std::pair 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. @@ -382,11 +462,13 @@ namespace cds { namespace container { @warning See \ref cds_intrusive_item_creating "insert item troubleshooting" */ template - std::pair update( K const& key, Func func, bool bInsert = true ) + std::pair update( K&& key, Func func, bool bInsert = true ) { - scoped_node_ptr sp( cxx_node_allocator().New( m_Hasher, key )); - std::pair result = base_class::do_update( *sp, [&func]( bool bNew, node_type& node ) { func( bNew, node.m_Value );}, bInsert ); - if ( !result.first ) + scoped_node_ptr sp( cxx_node_allocator().MoveNew( m_Hasher, std::forward(key))); + std::pair 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(); return result; } @@ -437,12 +519,12 @@ namespace cds { namespace container { */ bool erase_at( iterator const& iter ) { - return base_class::erase_at( static_cast( iter )); + return base_class::do_erase_at( iter ); } //@cond bool erase_at( reverse_iterator const& iter ) { - return base_class::erase_at( static_cast( iter )); + return base_class::do_erase_at( iter ); } //@endcond @@ -484,26 +566,6 @@ namespace cds { namespace container { return gp; } - /// Extracts the item pointed by the iterator \p iter - /** - The item extracted is freed automatically by garbage collector \p GC - when returned \p guarded_ptr object will be destroyed or released. - - @note Each \p guarded_ptr object uses the GC's guard that can be limited resource. - - Due to concurrent nature of the map the returned guarded pointer may be empty. - Check it before dereferencing. - */ - guarded_ptr extract_at( iterator const& iter ) - { - guarded_ptr gp; - if ( base_class::erase_at( iter )) { - // The element erased is guarded by iter so it is still alive - gp.reset( iter.node_pointer()); - } - return gp; - } - /// Checks whether the map contains \p key /** The function searches the item by its hash that is equal to hash( key_type( key )) @@ -648,55 +710,55 @@ namespace cds { namespace container { /// Returns an iterator to the beginning of the map iterator begin() { - return iterator( base_class::begin() ); + return base_class::template init_begin(); } /// Returns an const iterator to the beginning of the map const_iterator begin() const { - return const_iterator( base_class::begin()); + return base_class::template init_begin(); } /// Returns an const iterator to the beginning of the map const_iterator cbegin() { - return const_iterator( base_class::cbegin()); + return base_class::template init_begin(); } /// 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 iterator( base_class::end()); + return base_class::template init_end(); } /// 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 const_iterator( base_class::end()); + return base_class::template init_end(); } /// 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 const_iterator( base_class::cend()); + return base_class::template init_end(); } /// Returns a reverse iterator to the first element of the reversed map reverse_iterator rbegin() { - return reverse_iterator( base_class::rbegin()); + return base_class::template init_rbegin(); } /// Returns a const reverse iterator to the first element of the reversed map const_reverse_iterator rbegin() const { - return const_reverse_iterator( base_class::rbegin()); + return base_class::template init_rbegin(); } /// Returns a const reverse iterator to the first element of the reversed map const_reverse_iterator crbegin() { - return const_reverse_iterator( base_class::crbegin()); + return base_class::template init_rbegin(); } /// Returns a reverse iterator to the element following the last element of the reversed map @@ -706,7 +768,7 @@ namespace cds { namespace container { */ reverse_iterator rend() { - return reverse_iterator( base_class::rend()); + return base_class::template init_rend(); } /// Returns a const reverse iterator to the element following the last element of the reversed map @@ -716,7 +778,7 @@ namespace cds { namespace container { */ const_reverse_iterator rend() const { - return const_reverse_iterator( base_class::rend()); + return base_class::template init_rend(); } /// Returns a const reverse iterator to the element following the last element of the reversed map @@ -726,7 +788,7 @@ namespace cds { namespace container { */ const_reverse_iterator crend() { - return const_reverse_iterator( base_class::crend()); + return base_class::template init_rend(); } ///@} }; diff --git a/cds/intrusive/impl/multilevel_hashset.h b/cds/intrusive/impl/multilevel_hashset.h index 86ce7439..4b22a47b 100644 --- a/cds/intrusive/impl/multilevel_hashset.h +++ b/cds/intrusive/impl/multilevel_hashset.h @@ -172,32 +172,24 @@ namespace cds { namespace intrusive { protected: //@cond - /// Bidirectional iterator class - template - class bidirectional_iterator + class iterator_base { friend class MultiLevelHashSet; + protected: array_node * m_pNode; ///< current array node size_t m_idx; ///< current position in m_pNode typename gc::Guard m_guard; ///< HP guard MultiLevelHashSet const* m_set; ///< Hash set - - protected: - static CDS_CONSTEXPR bool const c_bConstantIterator = IsConst; - - public: - typedef typename std::conditional< IsConst, value_type const*, value_type*>::type value_ptr; ///< Value pointer - typedef typename std::conditional< IsConst, value_type const&, value_type&>::type value_ref; ///< Value reference - + public: - bidirectional_iterator() CDS_NOEXCEPT + iterator_base() CDS_NOEXCEPT : m_pNode( nullptr ) , m_idx( 0 ) , m_set( nullptr ) {} - bidirectional_iterator( bidirectional_iterator const& rhs ) CDS_NOEXCEPT + iterator_base( iterator_base const& rhs ) CDS_NOEXCEPT : m_pNode( rhs.m_pNode ) , m_idx( rhs.m_idx ) , m_set( rhs.m_set ) @@ -205,7 +197,7 @@ namespace cds { namespace intrusive { m_guard.copy( rhs.m_guard ); } - bidirectional_iterator& operator=(bidirectional_iterator const& rhs) CDS_NOEXCEPT + iterator_base& operator=(iterator_base const& rhs) CDS_NOEXCEPT { m_pNode = rhs.m_pNode; m_idx = rhs.m_idx; @@ -214,55 +206,41 @@ namespace cds { namespace intrusive { return *this; } - bidirectional_iterator& operator++() + iterator_base& operator++() { forward(); return *this; } - bidirectional_iterator& operator--() + iterator_base& operator--() { backward(); return *this; } - value_ptr operator ->() const CDS_NOEXCEPT - { - return pointer(); - } - - value_ref operator *() const CDS_NOEXCEPT - { - value_ptr p = pointer(); - assert( p ); - return *p; - } - void release() { m_guard.clear(); } - template - bool operator ==(bidirectional_iterator const& rhs) const CDS_NOEXCEPT + bool operator ==(iterator_base const& rhs) const CDS_NOEXCEPT { return m_pNode == rhs.m_pNode && m_idx == rhs.m_idx && m_set == rhs.m_set; } - template - bool operator !=(bidirectional_iterator const& rhs) const CDS_NOEXCEPT + bool operator !=(iterator_base const& rhs) const CDS_NOEXCEPT { return !( *this == rhs ); } protected: - bidirectional_iterator( MultiLevelHashSet& set, array_node * pNode, size_t idx, bool ) + iterator_base( MultiLevelHashSet const& set, array_node * pNode, size_t idx, bool ) : m_pNode( pNode ) , m_idx( idx ) , m_set( &set ) {} - bidirectional_iterator( MultiLevelHashSet& set, array_node * pNode, size_t idx ) + iterator_base( MultiLevelHashSet const& set, array_node * pNode, size_t idx ) : m_pNode( pNode ) , m_idx( idx ) , m_set( &set ) @@ -270,7 +248,7 @@ namespace cds { namespace intrusive { forward(); } - value_ptr pointer() const CDS_NOEXCEPT + value_type * pointer() const CDS_NOEXCEPT { return m_guard.template get(); } @@ -390,63 +368,166 @@ namespace cds { namespace intrusive { } }; + template + Iterator init_begin() const + { + return Iterator( *this, m_Head, size_t(0) - 1 ); + } + + template + Iterator init_end() const + { + return Iterator( *this, m_Head, head_size(), false ); + } + + template + Iterator init_rbegin() const + { + return Iterator( *this, m_Head, head_size() ); + } + + template + Iterator init_rend() const + { + return Iterator( *this, m_Head, size_t(0) - 1, false ); + } + + /// Bidirectional iterator class + template + class bidirectional_iterator: protected iterator_base + { + friend class MultiLevelHashSet; + + protected: + static CDS_CONSTEXPR bool const c_bConstantIterator = IsConst; + + public: + typedef typename std::conditional< IsConst, value_type const*, value_type*>::type value_ptr; ///< Value pointer + typedef typename std::conditional< IsConst, value_type const&, value_type&>::type value_ref; ///< Value reference + + public: + bidirectional_iterator() CDS_NOEXCEPT + {} + + bidirectional_iterator( bidirectional_iterator const& rhs ) CDS_NOEXCEPT + : iterator_base( rhs ) + {} + + bidirectional_iterator& operator=(bidirectional_iterator const& rhs) CDS_NOEXCEPT + { + iterator_base::operator=( rhs ); + return *this; + } + + bidirectional_iterator& operator++() + { + iterator_base::operator++(); + return *this; + } + + bidirectional_iterator& operator--() + { + iterator_base::operator--(); + return *this; + } + + value_ptr operator ->() const CDS_NOEXCEPT + { + return iterator_base::pointer(); + } + + value_ref operator *() const CDS_NOEXCEPT + { + value_ptr p = iterator_base::pointer(); + assert( p ); + return *p; + } + + void release() + { + iterator_base::release(); + } + + template + bool operator ==(bidirectional_iterator const& rhs) const CDS_NOEXCEPT + { + return iterator_base::operator==( rhs ); + } + + template + bool operator !=(bidirectional_iterator const& rhs) const CDS_NOEXCEPT + { + return !( *this == rhs ); + } + + protected: + bidirectional_iterator( MultiLevelHashSet& set, array_node * pNode, size_t idx, bool ) + : iterator_base( set, pNode, idx, false ) + {} + + bidirectional_iterator( MultiLevelHashSet& set, array_node * pNode, size_t idx ) + : iterator_base( set, pNode, idx ) + {} + }; + /// Reverse bidirectional iterator template - class reverse_bidirectional_iterator : protected bidirectional_iterator + class reverse_bidirectional_iterator : public iterator_base { - typedef bidirectional_iterator base_class; friend class MultiLevelHashSet; public: - typedef typename base_class::value_ptr value_ptr; - typedef typename base_class::value_ref value_ref; + typedef typename std::conditional< IsConst, value_type const*, value_type*>::type value_ptr; ///< Value pointer + typedef typename std::conditional< IsConst, value_type const&, value_type&>::type value_ref; ///< Value reference public: reverse_bidirectional_iterator() CDS_NOEXCEPT - : base_class() + : iterator_base() {} reverse_bidirectional_iterator( reverse_bidirectional_iterator const& rhs ) CDS_NOEXCEPT - : base_class( rhs ) + : iterator_base( rhs ) {} reverse_bidirectional_iterator& operator=( reverse_bidirectional_iterator const& rhs) CDS_NOEXCEPT { - base_class::operator=( rhs ); + iterator_base::operator=( rhs ); return *this; } reverse_bidirectional_iterator& operator++() { - base_class::backward(); + iterator_base::operator--(); return *this; } reverse_bidirectional_iterator& operator--() { - base_class::forward(); + iterator_base::operator++(); return *this; } value_ptr operator ->() const CDS_NOEXCEPT { - return base_class::operator->(); + return iterator_base::pointer(); } value_ref operator *() const CDS_NOEXCEPT { - return base_class::operator*(); + value_ptr p = iterator_base::pointer(); + assert( p ); + return *p; } void release() { - base_class::release(); + iterator_base::release(); } template bool operator ==(reverse_bidirectional_iterator const& rhs) const { - return base_class::operator==( rhs ); + return iterator_base::operator==( rhs ); } template @@ -456,10 +537,14 @@ namespace cds { namespace intrusive { } private: + reverse_bidirectional_iterator( MultiLevelHashSet& set, array_node * pNode, size_t idx, bool ) + : iterator_base( set, pNode, idx, false ) + {} + reverse_bidirectional_iterator( MultiLevelHashSet& set, array_node * pNode, size_t idx ) - : base_class( set, pNode, idx, false ) + : iterator_base( set, pNode, idx, false ) { - base_class::backward(); + iterator_base::backward(); } }; //@endcond @@ -694,32 +779,12 @@ namespace cds { namespace intrusive { */ bool erase_at( iterator const& iter ) { - if ( iter.m_set != this ) - return false; - if ( iter.m_pNode == m_Head && iter.m_idx >= head_size()) - return false; - if ( iter.m_idx >= array_node_size() ) - return false; - - for (;;) { - 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( slot.ptr() ); - --m_ItemCounter; - m_Stat.onEraseSuccess(); - return true; - } - } - else - return false; - } + return do_erase_at( iter ); } //@cond bool erase_at( reverse_iterator const& iter ) { - return erase_at(static_cast( iter )); + return do_erase_at( iter ); } //@endcond @@ -931,19 +996,19 @@ namespace cds { namespace intrusive { /// Returns an iterator to the element following the last element of the set. This element acts as a placeholder; attempting to access it results in undefined behavior. iterator end() { - return iterator( *this, m_Head, head_size() - 1 ); + return iterator( *this, m_Head, head_size(), false ); } /// Returns a const iterator to the element following the last element of the set. This element acts as a placeholder; attempting to access it results in undefined behavior. const_iterator end() const { - return const_iterator( *this, m_Head, head_size() - 1 ); + return const_iterator( *this, m_Head, head_size(), false ); } /// Returns a const iterator to the element following the last element of the set. This element acts as a placeholder; attempting to access it results in undefined behavior. const_iterator cend() { - return const_iterator( *this, m_Head, head_size() - 1 ); + return const_iterator( *this, m_Head, head_size(), false ); } /// Returns a reverse iterator to the first element of the reversed set @@ -971,7 +1036,7 @@ namespace cds { namespace intrusive { */ reverse_iterator rend() { - return reverse_iterator( *this, m_Head, 0 ); + return reverse_iterator( *this, m_Head, size_t(0) - 1, false ); } /// Returns a const reverse iterator to the element following the last element of the reversed set @@ -981,7 +1046,7 @@ namespace cds { namespace intrusive { */ const_reverse_iterator rend() const { - return const_reverse_iterator( *this, m_Head, 0 ); + return const_reverse_iterator( *this, m_Head, size_t(0) - 1, false ); } /// Returns a const reverse iterator to the element following the last element of the reversed set @@ -991,7 +1056,7 @@ namespace cds { namespace intrusive { */ const_reverse_iterator crend() { - return const_reverse_iterator( *this, m_Head, 0 ); + return const_reverse_iterator( *this, m_Head, size_t(0) - 1, false ); } ///@} @@ -1264,6 +1329,31 @@ namespace cds { namespace intrusive { } // while } + bool do_erase_at( iterator_base const& iter ) + { + if ( iter.m_set != this ) + return false; + if ( iter.m_pNode == m_Head && iter.m_idx >= head_size()) + return false; + if ( iter.m_idx >= array_node_size() ) + return false; + + for (;;) { + 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( slot.ptr() ); + --m_ItemCounter; + m_Stat.onEraseSuccess(); + return true; + } + } + else + return false; + } + } + template std::pair do_update( value_type& val, Func f, bool bInsert = true ) { diff --git a/projects/Win/vc12/hdr-test-map.vcxproj b/projects/Win/vc12/hdr-test-map.vcxproj index 9b26328d..a298e9a4 100644 --- a/projects/Win/vc12/hdr-test-map.vcxproj +++ b/projects/Win/vc12/hdr-test-map.vcxproj @@ -546,6 +546,7 @@ + @@ -566,6 +567,8 @@ + + diff --git a/projects/Win/vc12/hdr-test-map.vcxproj.filters b/projects/Win/vc12/hdr-test-map.vcxproj.filters index 066cf2a4..22112b2f 100644 --- a/projects/Win/vc12/hdr-test-map.vcxproj.filters +++ b/projects/Win/vc12/hdr-test-map.vcxproj.filters @@ -175,6 +175,12 @@ skip_list + + multilvel_hashmap + + + multilvel_hashmap + @@ -191,6 +197,9 @@ cuckoo + + multilvel_hashmap + @@ -208,5 +217,8 @@ {9318c3c0-92a3-4a5a-be2b-a47411a3e4c4} + + {cf81877d-3069-48a6-a143-2281963e9c4f} + \ No newline at end of file diff --git a/projects/source.test-hdr.mk b/projects/source.test-hdr.mk index efaab042..868da4e7 100644 --- a/projects/source.test-hdr.mk +++ b/projects/source.test-hdr.mk @@ -15,6 +15,8 @@ CDS_TESTHDR_MAP := \ tests/test-hdr/map/hdr_michael_map_lazy_rcu_shb.cpp \ tests/test-hdr/map/hdr_michael_map_lazy_rcu_sht.cpp \ tests/test-hdr/map/hdr_michael_map_lazy_nogc.cpp \ + tests/test-hdr/map/hdr_multilevel_hashmap_hp.cpp \ + tests/test-hdr/map/hdr_multilevel_hashmap_dhp.cpp \ tests/test-hdr/map/hdr_refinable_hashmap_hashmap_std.cpp \ tests/test-hdr/map/hdr_refinable_hashmap_boost_list.cpp \ tests/test-hdr/map/hdr_refinable_hashmap_list.cpp \ diff --git a/tests/test-hdr/CMakeLists.txt b/tests/test-hdr/CMakeLists.txt index f84173f5..f68211e3 100644 --- a/tests/test-hdr/CMakeLists.txt +++ b/tests/test-hdr/CMakeLists.txt @@ -17,6 +17,8 @@ set(CDS_TESTHDR_MAP map/hdr_michael_map_lazy_rcu_shb.cpp map/hdr_michael_map_lazy_rcu_sht.cpp map/hdr_michael_map_lazy_nogc.cpp + map/hdr_multilevel_hashmap_hp.cpp + map/hdr_multilevel_hashmap_dhp.cpp map/hdr_refinable_hashmap_hashmap_std.cpp map/hdr_refinable_hashmap_boost_list.cpp map/hdr_refinable_hashmap_list.cpp diff --git a/tests/test-hdr/map/hdr_multilevel_hashmap.h b/tests/test-hdr/map/hdr_multilevel_hashmap.h new file mode 100644 index 00000000..e5a7b71e --- /dev/null +++ b/tests/test-hdr/map/hdr_multilevel_hashmap.h @@ -0,0 +1,404 @@ +//$$CDS-header$$ + +#ifndef CDSTEST_HDR_MULTILEVEL_HASHMAP_H +#define CDSTEST_HDR_MULTILEVEL_HASHMAP_H + +#include "cppunit/cppunit_proxy.h" + +// forward declaration +namespace cds { + namespace container {} + namespace opt {} +} + +namespace map { + namespace cc = cds::container; + namespace co = cds::opt; + + class MultiLevelHashMapHdrTest : public CppUnitMini::TestCase + { + struct Item + { + unsigned int nInsertCall; + unsigned int nFindCall; + unsigned int nEraseCall; + mutable unsigned int nIteratorCall; + + Item() + : nInsertCall(0) + , nFindCall(0) + , nEraseCall(0) + , nIteratorCall(0) + {} + + explicit Item( unsigned int n ) + : nInsertCall(n) + , nFindCall(0) + , nEraseCall(0) + , nIteratorCall(0) + {} + }; + + struct hash128 + { + size_t lo; + size_t hi; + + hash128() {} + hash128(size_t l, size_t h) : lo(l), hi(h) {} + hash128( hash128 const& h) : lo(h.lo), hi(h.hi) {} + + struct make { + hash128 operator()( size_t n ) const + { + return hash128( std::hash()( n ), std::hash()( ~n )); + } + hash128 operator()( hash128 const& n ) const + { + return hash128( std::hash()( n.lo ), std::hash()( ~n.hi )); + } + }; + + struct less { + bool operator()( hash128 const& lhs, hash128 const& rhs ) const + { + if ( lhs.hi != rhs.hi ) + return lhs.hi < rhs.hi; + return lhs.lo < rhs.lo; + } + }; + + struct cmp { + int operator()( hash128 const& lhs, hash128 const& rhs ) const + { + if ( lhs.hi != rhs.hi ) + return lhs.hi < rhs.hi ? -1 : 1; + return lhs.lo < rhs.lo ? -1 : lhs.lo == rhs.lo ? 0 : 1; + } + }; + + friend bool operator==( hash128 const& lhs, hash128 const& rhs ) + { + return cmp()( lhs, rhs ) == 0; + } + friend bool operator!=(hash128 const& lhs, hash128 const& rhs) + { + return !( lhs == rhs ); + } + }; + + template + void test_hp( size_t nHeadBits, size_t nArrayBits ) + { + typedef typename Map::hash_type hash_type; + typedef typename Map::key_type key_type; + typedef typename Map::mapped_type mapped_type; + typedef typename Map::value_type value_type; + typedef typename Map::guarded_ptr guarded_ptr; + + size_t const capacity = 1000; + + Map m; + CPPUNIT_MSG("Array size: head=" << m.head_size() << ", array_node=" << m.array_node_size()); + //CPPUNIT_ASSERT(m.head_size() >= (size_t(1) << nHeadBits)); + //CPPUNIT_ASSERT(m.array_node_size() == (size_t(1) << nArrayBits)); + + CPPUNIT_ASSERT(m.empty()); + CPPUNIT_ASSERT(m.size() == 0); + + // insert( key )/update()/get()/find() + for ( size_t i = 0; i < capacity; ++i ) { + size_t key = i * 57; + CPPUNIT_ASSERT(!m.contains( key )) + CPPUNIT_ASSERT(m.insert( key )); + CPPUNIT_ASSERT(m.contains( key )); + CPPUNIT_ASSERT(m.size() == i + 1); + + auto ret = m.update(key, [] ( value_type& v, value_type * old ) { + CPPUNIT_ASSERT_CURRENT( old != nullptr ); + ++v.second.nInsertCall; + }, false ); + CPPUNIT_ASSERT( ret.first ); + CPPUNIT_ASSERT( !ret.second ); + + CPPUNIT_ASSERT(m.find(key, [](value_type& v) { ++v.second.nFindCall;} )); + + guarded_ptr gp{ m.get( key ) }; + CPPUNIT_ASSERT( gp ); + CPPUNIT_ASSERT( gp->first == key ); + CPPUNIT_ASSERT( gp->second.nInsertCall == 1 ); + CPPUNIT_ASSERT( gp->second.nFindCall == 1 ); + } + CPPUNIT_ASSERT(!m.empty()); + CPPUNIT_ASSERT(m.size() == capacity); + + // iterator test + size_t nCount = 0; + for ( auto it = m.begin(), itEnd = m.end(); it != itEnd; ++it ) { + CPPUNIT_ASSERT( it->second.nIteratorCall == 0 ); + CPPUNIT_ASSERT( it->second.nInsertCall == 1 ); + CPPUNIT_ASSERT( (*it).second.nFindCall == 1 ); + it->second.nIteratorCall += 1; + ++nCount; + } + CPPUNIT_ASSERT( nCount == capacity ); + + nCount = 0; + for ( auto it = m.rbegin(), itEnd = m.rend(); it != itEnd; ++it ) { + CPPUNIT_ASSERT( it->second.nInsertCall == 1 ); + CPPUNIT_ASSERT( (*it).second.nFindCall == 1 ); + CPPUNIT_ASSERT( it->second.nIteratorCall == 1 ); + (*it).second.nIteratorCall += 1; + ++nCount; + } + CPPUNIT_ASSERT( nCount == capacity ); + + nCount = 0; + for ( auto it = m.cbegin(), itEnd = m.cend(); it != itEnd; ++it ) { + CPPUNIT_ASSERT( it->second.nInsertCall == 1 ); + CPPUNIT_ASSERT( (*it).second.nFindCall == 1 ); + CPPUNIT_ASSERT( it->second.nIteratorCall == 2 ); + (*it).second.nIteratorCall += 1; + ++nCount; + } + CPPUNIT_ASSERT( nCount == capacity ); + + nCount = 0; + for ( auto it = m.crbegin(), itEnd = m.crend(); it != itEnd; ++it ) { + CPPUNIT_ASSERT( it->second.nInsertCall == 1 ); + CPPUNIT_ASSERT( (*it).second.nFindCall == 1 ); + CPPUNIT_ASSERT( it->second.nIteratorCall == 3 ); + (*it).second.nIteratorCall += 1; + ++nCount; + } + CPPUNIT_ASSERT( nCount == capacity ); + + // find + for ( size_t i = 0; i < capacity; i++ ) { + size_t key = i * 57; + CPPUNIT_ASSERT( m.find( key, [key]( value_type& v ) { + CPPUNIT_ASSERT_CURRENT( v.first == key ); + CPPUNIT_ASSERT_CURRENT( v.second.nInsertCall == 1 ); + CPPUNIT_ASSERT_CURRENT( v.second.nFindCall == 1 ); + CPPUNIT_ASSERT_CURRENT( v.second.nIteratorCall == 4 ); + })); + } + + // erase + for ( size_t i = capacity; i > 0; --i ) { + size_t key = (i -1) * 57; + guarded_ptr gp = m.get( key ); + CPPUNIT_ASSERT( gp ); + CPPUNIT_ASSERT( gp->first == key ); + CPPUNIT_ASSERT( gp->second.nInsertCall == 1 ); + CPPUNIT_ASSERT( gp->second.nFindCall == 1 ); + CPPUNIT_ASSERT( (*gp).second.nIteratorCall == 4 ); + + CPPUNIT_ASSERT(m.erase( key )); + + gp = m.get( key ); + CPPUNIT_ASSERT( !gp ); + CPPUNIT_ASSERT(!m.contains( key )); + } + CPPUNIT_ASSERT( m.empty()); + CPPUNIT_ASSERT(m.size() == 0); + + // Iterators on empty map + CPPUNIT_ASSERT(m.begin() == m.end()); + CPPUNIT_ASSERT(m.cbegin() == m.cend()); + CPPUNIT_ASSERT(m.rbegin() == m.rend()); + CPPUNIT_ASSERT(m.crbegin() == m.crend()); + + // insert( key, val ) + for ( size_t i = 0; i < capacity; ++i ) { + CPPUNIT_ASSERT(!m.contains(i)); + CPPUNIT_ASSERT(m.insert( i, (unsigned int) i * 100)); + CPPUNIT_ASSERT( m.contains(i)); + CPPUNIT_ASSERT( m.find( i, [i]( value_type& v ) { + CPPUNIT_ASSERT_CURRENT( v.first == i ); + CPPUNIT_ASSERT_CURRENT( v.second.nInsertCall == i * 100 ); + })); + } + CPPUNIT_ASSERT( !m.empty()); + CPPUNIT_ASSERT(m.size() == capacity); + + // erase( key, func ) + for ( size_t i = 0; i < capacity; ++i ) { + CPPUNIT_ASSERT( m.contains(i)); + CPPUNIT_ASSERT( m.erase( i, [i]( value_type& v ) { + CPPUNIT_ASSERT_CURRENT( v.first == i ); + CPPUNIT_ASSERT_CURRENT( v.second.nInsertCall == i * 100 ); + v.second.nInsertCall = 0; + })); + } + CPPUNIT_ASSERT( m.empty()); + CPPUNIT_ASSERT(m.size() == 0 ); + + // insert_with + for ( size_t i = 0; i < capacity; ++i ) { + size_t key = i * 121; + CPPUNIT_ASSERT(!m.contains(key)); + CPPUNIT_ASSERT( m.insert_with( key, [key]( value_type& v ) { + CPPUNIT_ASSERT_CURRENT( v.first == key ); + CPPUNIT_ASSERT_CURRENT( v.second.nInsertCall == 0 ); + v.second.nInsertCall = decltype(v.second.nInsertCall)( key ); + })); + CPPUNIT_ASSERT(m.find(key, [key] (value_type& v ) { + CPPUNIT_ASSERT_CURRENT( v.first == key ); + CPPUNIT_ASSERT_CURRENT( v.second.nInsertCall == key ); + })); + CPPUNIT_ASSERT(m.size() == i + 1); + } + CPPUNIT_ASSERT( !m.empty()); + CPPUNIT_ASSERT(m.size() == capacity); + + nCount = 0; + for ( auto it = m.begin(), itEnd = m.end(); it != itEnd; ++it ) { + CPPUNIT_ASSERT( it->first == it->second.nInsertCall ); + CPPUNIT_ASSERT( it->second.nIteratorCall == 0 ); + it->second.nIteratorCall += 1; + ++nCount; + } + CPPUNIT_ASSERT( nCount == capacity ); + + nCount = 0; + for ( auto it = m.rbegin(), itEnd = m.rend(); it != itEnd; ++it ) { + CPPUNIT_ASSERT( it->first == it->second.nInsertCall ); + CPPUNIT_ASSERT( it->second.nIteratorCall == 1 ); + it->second.nIteratorCall += 1; + ++nCount; + } + CPPUNIT_ASSERT( nCount == capacity ); + + // erase_at( iterator ) + nCount = 0; + for ( auto it = m.begin(), itEnd = m.end(); it != itEnd; ++it ) { + CPPUNIT_ASSERT( it->first == it->second.nInsertCall ); + CPPUNIT_ASSERT( it->second.nIteratorCall == 2 ); + CPPUNIT_ASSERT(m.erase_at( it )); + ++nCount; + CPPUNIT_ASSERT(!m.contains( it->first )); + } + CPPUNIT_ASSERT( nCount == capacity ); + CPPUNIT_ASSERT( m.empty()); + CPPUNIT_ASSERT(m.size() == 0 ); + + // emplace + for ( size_t i = 0; i < capacity; ++i ) { + size_t key = i * 1023; + CPPUNIT_ASSERT(!m.contains(key)); + CPPUNIT_ASSERT( m.emplace( key, (unsigned int) i )); + CPPUNIT_ASSERT(m.find(key, [key] (value_type& v ) { + CPPUNIT_ASSERT_CURRENT( v.first == key ); + CPPUNIT_ASSERT_CURRENT( v.second.nInsertCall * 1023 == key ); + })); + CPPUNIT_ASSERT(m.size() == i + 1); + } + CPPUNIT_ASSERT( !m.empty()); + CPPUNIT_ASSERT(m.size() == capacity); + + // erase_at( reverse_iterator ) + nCount = 0; + for ( auto it = m.rbegin(), itEnd = m.rend(); it != itEnd; ++it ) { + CPPUNIT_ASSERT( it->first == it->second.nInsertCall * 1023 ); + CPPUNIT_ASSERT(m.erase_at( it )); + ++nCount; + CPPUNIT_ASSERT(!m.contains( it->first )); + } + CPPUNIT_ASSERT( nCount == capacity ); + CPPUNIT_ASSERT( m.empty()); + CPPUNIT_ASSERT(m.size() == 0 ); + + + // extract + for ( size_t i = 0; i < capacity; ++i ) { + size_t key = i * 711; + CPPUNIT_ASSERT(!m.contains(key)); + auto ret = m.update( key, [i]( value_type& v, value_type * old ) { + CPPUNIT_ASSERT_CURRENT( old == nullptr ); + v.second.nInsertCall = (unsigned int) i; + }); + CPPUNIT_ASSERT( ret.first ); + CPPUNIT_ASSERT( ret.second ); + CPPUNIT_ASSERT(m.find(key, [i, key] (value_type& v ) { + CPPUNIT_ASSERT_CURRENT( v.first == key ); + CPPUNIT_ASSERT_CURRENT( v.second.nInsertCall == i ); + })); + CPPUNIT_ASSERT(m.size() == i + 1); + } + CPPUNIT_ASSERT( !m.empty()); + CPPUNIT_ASSERT(m.size() == capacity); + + for ( size_t i = capacity; i > 0; --i ) { + size_t key = (i-1) * 711; + guarded_ptr gp{ m.extract(key) }; + CPPUNIT_ASSERT( gp ); + CPPUNIT_ASSERT( gp->first == key ); + CPPUNIT_ASSERT((*gp).second.nInsertCall == i - 1 ); + gp = m.extract(key); + CPPUNIT_ASSERT( !gp ); + } + CPPUNIT_ASSERT( m.empty()); + CPPUNIT_ASSERT(m.size() == 0 ); + + // clear + for ( size_t i = 0; i < capacity; ++i ) { + CPPUNIT_ASSERT(!m.contains( i )) + CPPUNIT_ASSERT(m.insert( i )); + CPPUNIT_ASSERT(m.contains( i )); + CPPUNIT_ASSERT(m.size() == i + 1); + } + CPPUNIT_ASSERT( !m.empty()); + CPPUNIT_ASSERT(m.size() == capacity ); + + m.clear(); + CPPUNIT_ASSERT( m.empty()); + CPPUNIT_ASSERT(m.size() == 0 ); + + + CPPUNIT_MSG( m.statistics() ); + } + + void hp_stdhash(); + void hp_stdhash_stat(); + void hp_stdhash_5_3(); + void hp_stdhash_5_3_stat(); + void hp_hash128(); + void hp_hash128_stat(); + void hp_hash128_4_3(); + void hp_hash128_4_3_stat(); + + void dhp_stdhash(); + void dhp_stdhash_stat(); + void dhp_stdhash_5_3(); + void dhp_stdhash_5_3_stat(); + void dhp_hash128(); + void dhp_hash128_stat(); + void dhp_hash128_4_3(); + void dhp_hash128_4_3_stat(); + + CPPUNIT_TEST_SUITE(MultiLevelHashMapHdrTest) + CPPUNIT_TEST(hp_stdhash) + CPPUNIT_TEST(hp_stdhash_stat) + CPPUNIT_TEST(hp_stdhash_5_3) + CPPUNIT_TEST(hp_stdhash_5_3_stat) + CPPUNIT_TEST(hp_hash128) + CPPUNIT_TEST(hp_hash128_stat) + CPPUNIT_TEST(hp_hash128_4_3) + CPPUNIT_TEST(hp_hash128_4_3_stat) + + CPPUNIT_TEST(dhp_stdhash) + CPPUNIT_TEST(dhp_stdhash_stat) + CPPUNIT_TEST(dhp_stdhash_5_3) + CPPUNIT_TEST(dhp_stdhash_5_3_stat) + CPPUNIT_TEST(dhp_hash128) + CPPUNIT_TEST(dhp_hash128_stat) + CPPUNIT_TEST(dhp_hash128_4_3) + CPPUNIT_TEST(dhp_hash128_4_3_stat) + CPPUNIT_TEST_SUITE_END() + + }; + +} // namespace map + +#endif //#ifndef CDSTEST_HDR_MULTILEVEL_HASHMAP_H diff --git a/tests/test-hdr/map/hdr_multilevel_hashmap_dhp.cpp b/tests/test-hdr/map/hdr_multilevel_hashmap_dhp.cpp new file mode 100644 index 00000000..a01fc0fe --- /dev/null +++ b/tests/test-hdr/map/hdr_multilevel_hashmap_dhp.cpp @@ -0,0 +1,140 @@ +//$$CDS-header$$ + +#include "map/hdr_multilevel_hashmap.h" +#include +#include "unit/print_multilevel_hashset_stat.h" + +namespace map { + namespace { + typedef cds::gc::DHP gc_type; + } // namespace + + void MultiLevelHashMapHdrTest::dhp_stdhash() + { + typedef cc::MultiLevelHashMap< gc_type, size_t, Item > map_type; + + test_hp(4, 2); + } + + void MultiLevelHashMapHdrTest::dhp_hash128() + { + struct traits : public cc::multilevel_hashmap::traits { + typedef hash128::make hash; + typedef hash128::less less; + }; + typedef cc::MultiLevelHashMap< gc_type, size_t, Item, traits > map_type; + test_hp(4, 2); + + typedef cc::MultiLevelHashMap< gc_type, size_t, Item, + typename cc::multilevel_hashmap::make_traits< + co::hash< hash128::make > + , co::less< hash128::less > + >::type + > map_type2; + test_hp(4, 2); + } + + void MultiLevelHashMapHdrTest::dhp_stdhash_stat() + { + struct traits : public cc::multilevel_hashmap::traits { + typedef cc::multilevel_hashmap::stat<> stat; + }; + typedef cc::MultiLevelHashMap< gc_type, size_t, Item, traits > map_type; + test_hp(4, 2); + + typedef cc::MultiLevelHashMap< gc_type, size_t, Item, + typename cc::multilevel_hashmap::make_traits< + co::stat< cc::multilevel_hashmap::stat<>> + >::type + > map_type2; + test_hp(4, 2); + } + + void MultiLevelHashMapHdrTest::dhp_hash128_stat() + { + struct traits : public cc::multilevel_hashmap::traits { + typedef cc::multilevel_hashmap::stat<> stat; + typedef hash128::make hash; + typedef hash128::cmp compare; + }; + typedef cc::MultiLevelHashMap< gc_type, size_t, Item, traits > map_type; + test_hp(4, 2); + + typedef cc::MultiLevelHashMap< gc_type, size_t, Item, + typename cc::multilevel_hashmap::make_traits< + co::stat< cc::multilevel_hashmap::stat<>> + , co::hash< hash128::make > + , co::compare< hash128::cmp > + >::type + > map_type2; + test_hp(4, 2); + } + + void MultiLevelHashMapHdrTest::dhp_stdhash_5_3() + { + typedef cc::MultiLevelHashMap< gc_type, size_t, Item > map_type; + + test_hp(5, 3); + } + + void MultiLevelHashMapHdrTest::dhp_stdhash_5_3_stat() + { + struct traits : public cc::multilevel_hashmap::traits { + typedef cc::multilevel_hashmap::stat<> stat; + typedef cds::backoff::empty back_off; + }; + typedef cc::MultiLevelHashMap< gc_type, size_t, Item, traits > map_type; + test_hp(5, 3); + + typedef cc::MultiLevelHashMap< gc_type, size_t, Item, + typename cc::multilevel_hashmap::make_traits< + co::stat< cc::multilevel_hashmap::stat<>> + ,co::back_off< cds::backoff::empty > + >::type + > map_type2; + test_hp(5, 3); + } + + void MultiLevelHashMapHdrTest::dhp_hash128_4_3() + { + struct traits : public cc::multilevel_hashmap::traits { + typedef hash128::make hash; + typedef hash128::less less; + }; + typedef cc::MultiLevelHashMap< gc_type, size_t, Item, traits > map_type; + test_hp(4, 3); + + typedef cc::MultiLevelHashMap< gc_type, size_t, Item, + typename cc::multilevel_hashmap::make_traits< + co::hash< hash128::make > + , co::less< hash128::less > + >::type + > map_type2; + test_hp(4, 3); + } + + void MultiLevelHashMapHdrTest::dhp_hash128_4_3_stat() + { + struct traits : public cc::multilevel_hashmap::traits { + typedef hash128::make hash; + typedef hash128::less less; + typedef cc::multilevel_hashmap::stat<> stat; + typedef co::v::sequential_consistent memory_model; + }; + typedef cc::MultiLevelHashMap< gc_type, size_t, Item, traits > map_type; + test_hp(4, 3); + + typedef cc::MultiLevelHashMap< gc_type, size_t, Item, + typename cc::multilevel_hashmap::make_traits< + co::hash< hash128::make > + , co::less< hash128::less > + , co::stat< cc::multilevel_hashmap::stat<>> + , co::memory_model< co::v::sequential_consistent > + >::type + > map_type2; + test_hp(4, 3); + } + +} // namespace map + +CPPUNIT_TEST_SUITE_REGISTRATION(map::MultiLevelHashMapHdrTest); diff --git a/tests/test-hdr/map/hdr_multilevel_hashmap_hp.cpp b/tests/test-hdr/map/hdr_multilevel_hashmap_hp.cpp new file mode 100644 index 00000000..40c3e378 --- /dev/null +++ b/tests/test-hdr/map/hdr_multilevel_hashmap_hp.cpp @@ -0,0 +1,140 @@ +//$$CDS-header$$ + +#include "map/hdr_multilevel_hashmap.h" +#include +#include "unit/print_multilevel_hashset_stat.h" + +namespace map { + namespace { + typedef cds::gc::HP gc_type; + } // namespace + + void MultiLevelHashMapHdrTest::hp_stdhash() + { + typedef cc::MultiLevelHashMap< gc_type, size_t, Item > map_type; + + test_hp(4, 2); + } + + void MultiLevelHashMapHdrTest::hp_hash128() + { + struct traits : public cc::multilevel_hashmap::traits { + typedef hash128::make hash; + typedef hash128::less less; + }; + typedef cc::MultiLevelHashMap< gc_type, size_t, Item, traits > map_type; + test_hp(4, 2); + + typedef cc::MultiLevelHashMap< gc_type, size_t, Item, + typename cc::multilevel_hashmap::make_traits< + co::hash< hash128::make > + , co::less< hash128::less > + >::type + > map_type2; + test_hp(4, 2); + } + + void MultiLevelHashMapHdrTest::hp_stdhash_stat() + { + struct traits : public cc::multilevel_hashmap::traits { + typedef cc::multilevel_hashmap::stat<> stat; + }; + typedef cc::MultiLevelHashMap< gc_type, size_t, Item, traits > map_type; + test_hp(4, 2); + + typedef cc::MultiLevelHashMap< gc_type, size_t, Item, + typename cc::multilevel_hashmap::make_traits< + co::stat< cc::multilevel_hashmap::stat<>> + >::type + > map_type2; + test_hp(4, 2); + } + + void MultiLevelHashMapHdrTest::hp_hash128_stat() + { + struct traits : public cc::multilevel_hashmap::traits { + typedef cc::multilevel_hashmap::stat<> stat; + typedef hash128::make hash; + typedef hash128::cmp compare; + }; + typedef cc::MultiLevelHashMap< gc_type, size_t, Item, traits > map_type; + test_hp(4, 2); + + typedef cc::MultiLevelHashMap< gc_type, size_t, Item, + typename cc::multilevel_hashmap::make_traits< + co::stat< cc::multilevel_hashmap::stat<>> + , co::hash< hash128::make > + , co::compare< hash128::cmp > + >::type + > map_type2; + test_hp(4, 2); + } + + void MultiLevelHashMapHdrTest::hp_stdhash_5_3() + { + typedef cc::MultiLevelHashMap< gc_type, size_t, Item > map_type; + + test_hp(5, 3); + } + + void MultiLevelHashMapHdrTest::hp_stdhash_5_3_stat() + { + struct traits : public cc::multilevel_hashmap::traits { + typedef cc::multilevel_hashmap::stat<> stat; + typedef cds::backoff::empty back_off; + }; + typedef cc::MultiLevelHashMap< gc_type, size_t, Item, traits > map_type; + test_hp(5, 3); + + typedef cc::MultiLevelHashMap< gc_type, size_t, Item, + typename cc::multilevel_hashmap::make_traits< + co::stat< cc::multilevel_hashmap::stat<>> + ,co::back_off< cds::backoff::empty > + >::type + > map_type2; + test_hp(5, 3); + } + + void MultiLevelHashMapHdrTest::hp_hash128_4_3() + { + struct traits : public cc::multilevel_hashmap::traits { + typedef hash128::make hash; + typedef hash128::less less; + }; + typedef cc::MultiLevelHashMap< gc_type, size_t, Item, traits > map_type; + test_hp(4, 3); + + typedef cc::MultiLevelHashMap< gc_type, size_t, Item, + typename cc::multilevel_hashmap::make_traits< + co::hash< hash128::make > + , co::less< hash128::less > + >::type + > map_type2; + test_hp(4, 3); + } + + void MultiLevelHashMapHdrTest::hp_hash128_4_3_stat() + { + struct traits : public cc::multilevel_hashmap::traits { + typedef hash128::make hash; + typedef hash128::less less; + typedef cc::multilevel_hashmap::stat<> stat; + typedef co::v::sequential_consistent memory_model; + }; + typedef cc::MultiLevelHashMap< gc_type, size_t, Item, traits > map_type; + test_hp(4, 3); + + typedef cc::MultiLevelHashMap< gc_type, size_t, Item, + typename cc::multilevel_hashmap::make_traits< + co::hash< hash128::make > + , co::less< hash128::less > + , co::stat< cc::multilevel_hashmap::stat<>> + , co::memory_model< co::v::sequential_consistent > + >::type + > map_type2; + test_hp(4, 3); + } + +} // namespace map + +CPPUNIT_TEST_SUITE_REGISTRATION(map::MultiLevelHashMapHdrTest); diff --git a/tests/test-hdr/set/hdr_multilevel_hashset.h b/tests/test-hdr/set/hdr_multilevel_hashset.h index 8c7526cd..b34a4504 100644 --- a/tests/test-hdr/set/hdr_multilevel_hashset.h +++ b/tests/test-hdr/set/hdr_multilevel_hashset.h @@ -76,14 +76,6 @@ namespace set { } }; - struct item_disposer { - template - void operator()( Item * p ) - { - ++p->nDisposeCount; - } - }; - struct hash128 { size_t lo; -- 2.34.1