From: khizmax Date: Thu, 4 Aug 2016 21:04:19 +0000 (+0300) Subject: Added IterableList support to MichaelSet X-Git-Tag: v2.2.0~150 X-Git-Url: http://plrg.eecs.uci.edu/git/?p=libcds.git;a=commitdiff_plain;h=977a7c10110c2ce47531719035172ec18c25fe84 Added IterableList support to MichaelSet --- diff --git a/cds/container/details/iterable_list_base.h b/cds/container/details/iterable_list_base.h index 2adc1aa8..2d6e9fb5 100644 --- a/cds/container/details/iterable_list_base.h +++ b/cds/container/details/iterable_list_base.h @@ -158,6 +158,31 @@ namespace cds { namespace container { struct iterable_list_tag {}; + //@cond + template + struct is_iterable_list { + enum { + value = false + }; + }; + + template + struct is_iterable_list< IterableList> + { + enum { + value = true + }; + }; + + template + struct is_iterable_list< IterableKVList> + { + enum { + value = true + }; + }; + //@endcond + }} // namespace cds::container diff --git a/cds/container/details/michael_set_base.h b/cds/container/details/michael_set_base.h index 0db930cb..bd7543f8 100644 --- a/cds/container/details/michael_set_base.h +++ b/cds/container/details/michael_set_base.h @@ -25,7 +25,7 @@ SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE - OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. */ #ifndef CDSLIB_CONTAINER_DETAILS_MICHAEL_SET_BASE_H diff --git a/cds/container/impl/iterable_list.h b/cds/container/impl/iterable_list.h index cac200e4..228e96ac 100644 --- a/cds/container/impl/iterable_list.h +++ b/cds/container/impl/iterable_list.h @@ -139,6 +139,22 @@ namespace cds { namespace container { static CDS_CONSTEXPR const size_t c_nHazardPtrCount = base_class::c_nHazardPtrCount; ///< Count of hazard pointer required for the algorithm + //@cond + // Rebind traits (split-list support) + template + struct rebind_traits { + typedef IterableList< + gc + , value_type + , typename cds::opt::make_options< traits, Options...>::type + > type; + }; + + // Stat selector + template + using select_stat_wrapper = typename base_class::template select_stat_wrapper< Stat >; + //@endcond + protected: //@cond typedef typename maker::cxx_data_allocator cxx_data_allocator; @@ -750,12 +766,6 @@ namespace cds { namespace container { protected: //@cond - //template - //static value_type* alloc_data( Q const& v ) - //{ - // return cxx_data_allocator().New( v ); - //} - template static value_type* alloc_data( Args&&... args ) { diff --git a/cds/container/impl/lazy_list.h b/cds/container/impl/lazy_list.h index 6b7efb57..496f1b56 100644 --- a/cds/container/impl/lazy_list.h +++ b/cds/container/impl/lazy_list.h @@ -144,6 +144,22 @@ namespace cds { namespace container { static CDS_CONSTEXPR const size_t c_nHazardPtrCount = base_class::c_nHazardPtrCount; ///< Count of hazard pointer required for the algorithm + //@cond + // Rebind traits (split-list support) + template + struct rebind_traits { + typedef LazyList< + gc + , value_type + , typename cds::opt::make_options< traits, Options...>::type + > type; + }; + + // Stat selector + template + using select_stat_wrapper = typename base_class::template select_stat_wrapper< Stat >; + //@endcond + protected: //@cond typedef typename base_class::value_type node_type; @@ -152,40 +168,6 @@ namespace cds { namespace container { typedef typename maker::intrusive_traits::compare intrusive_key_comparator; typedef typename base_class::node_type head_type; - //@endcond - - public: - /// Guarded pointer - typedef typename gc::template guarded_ptr< node_type, value_type, details::guarded_ptr_cast_set > guarded_ptr; - - protected: - //@cond - static value_type& node_to_value( node_type& n ) - { - return n.m_Value; - } - - static value_type const& node_to_value( node_type const& n ) - { - return n.m_Value; - } - - template - static node_type * alloc_node( Q const& v ) - { - return cxx_allocator().New( v ); - } - - template - static node_type * alloc_node( Args&&... args ) - { - return cxx_allocator().MoveNew( std::forward(args)... ); - } - - static void free_node( node_type * pNode ) - { - cxx_allocator().Delete( pNode ); - } struct node_disposer { void operator()( node_type * pNode ) @@ -193,35 +175,20 @@ namespace cds { namespace container { free_node( pNode ); } }; - typedef std::unique_ptr< node_type, node_disposer > scoped_node_ptr; + typedef std::unique_ptr< node_type, node_disposer > scoped_node_ptr; - head_type& head() - { - return base_class::m_Head; - } - - head_type const& head() const - { - return base_class::m_Head; - } - - head_type& tail() - { - return base_class::m_Tail; - } - - head_type const& tail() const - { - return base_class::m_Tail; - } //@endcond + public: + /// Guarded pointer + typedef typename gc::template guarded_ptr< node_type, value_type, details::guarded_ptr_cast_set > guarded_ptr; + protected: - //@cond + //@cond template class iterator_type: protected base_class::template iterator_type { - typedef typename base_class::template iterator_type iterator_base; + typedef typename base_class::template iterator_type iterator_base; iterator_type( head_type const& pNode ) : iterator_base( const_cast( &pNode )) @@ -240,7 +207,7 @@ namespace cds { namespace container { iterator_type() {} - iterator_type( const iterator_type& src ) + iterator_type( iterator_type const& src ) : iterator_base( src ) {} @@ -382,9 +349,9 @@ namespace cds { namespace container { Returns \p true if inserting successful, \p false otherwise. */ template - bool insert( Q const& val ) + bool insert( Q&& val ) { - return insert_at( head(), val ); + return insert_at( head(), std::forward( val )); } /// Inserts new node @@ -410,9 +377,9 @@ namespace cds { namespace container { it is preferable that the initialization should be completed only if inserting is successful. */ template - bool insert( Q const& key, Func func ) + bool insert( Q&& key, Func func ) { - return insert_at( head(), key, func ); + return insert_at( head(), std::forward( key ), func ); } /// Inserts data of type \p value_type constructed from \p args @@ -436,14 +403,14 @@ namespace cds { namespace container { The functor \p Func signature is: \code struct my_functor { - void operator()( bool bNew, value_type& item, Q const& val ); + void operator()( bool bNew, value_type& item, Q const& key ); }; \endcode with arguments: - \p bNew - \p true if the item has been inserted, \p false otherwise - \p item - item of the list - - \p val - argument \p key passed into the \p %update() function + - \p key - argument \p key passed into the \p %update() function The functor may change non-key fields of the \p item; during \p func call \p item is locked so it is safe to modify the item in @@ -768,6 +735,53 @@ namespace cds { namespace container { protected: //@cond + static value_type& node_to_value( node_type& n ) + { + return n.m_Value; + } + + static value_type const& node_to_value( node_type const& n ) + { + return n.m_Value; + } + + template + static node_type * alloc_node( Q const& v ) + { + return cxx_allocator().New( v ); + } + + template + static node_type * alloc_node( Args&&... args ) + { + return cxx_allocator().MoveNew( std::forward( args )... ); + } + + static void free_node( node_type * pNode ) + { + cxx_allocator().Delete( pNode ); + } + + head_type& head() + { + return base_class::m_Head; + } + + head_type const& head() const + { + return base_class::m_Head; + } + + head_type& tail() + { + return base_class::m_Tail; + } + + head_type const& tail() const + { + return base_class::m_Tail; + } + bool insert_node( node_type * pNode ) { return insert_node_at( head(), pNode ); @@ -787,9 +801,9 @@ namespace cds { namespace container { } template - bool insert_at( head_type& refHead, const Q& val ) + bool insert_at( head_type& refHead, Q&& val ) { - return insert_node_at( refHead, alloc_node( val )); + return insert_node_at( refHead, alloc_node( std::forward( val ))); } template @@ -799,9 +813,9 @@ namespace cds { namespace container { } template - bool insert_at( head_type& refHead, const Q& key, Func f ) + bool insert_at( head_type& refHead, Q&& key, Func f ) { - scoped_node_ptr pNode( alloc_node( key )); + scoped_node_ptr pNode( alloc_node( std::forward( key ))); if ( base_class::insert_at( &refHead, *pNode, [&f](node_type& node){ f( node_to_value(node) ); } )) { pNode.release(); @@ -811,7 +825,7 @@ namespace cds { namespace container { } template - bool erase_at( head_type& refHead, const Q& key, Compare cmp, Func f ) + bool erase_at( head_type& refHead, Q const& key, Compare cmp, Func f ) { return base_class::erase_at( &refHead, key, cmp, [&f](node_type const& node){ f( node_to_value(node) ); } ); } @@ -823,12 +837,12 @@ namespace cds { namespace container { } template - std::pair update_at( head_type& refHead, const Q& key, Func f, bool bAllowInsert ) + std::pair update_at( head_type& refHead, Q const& key, Func f, bool bAllowInsert ) { scoped_node_ptr pNode( alloc_node( key )); std::pair ret = base_class::update_at( &refHead, *pNode, - [&f, &key](bool bNew, node_type& node, node_type&){f( bNew, node_to_value(node), key );}, + [&f, &key](bool bNew, node_type& node, node_type&) { f( bNew, node_to_value(node), key );}, bAllowInsert ); if ( ret.first && ret.second ) pNode.release(); diff --git a/cds/container/impl/michael_list.h b/cds/container/impl/michael_list.h index 27c87b90..97e438a5 100644 --- a/cds/container/impl/michael_list.h +++ b/cds/container/impl/michael_list.h @@ -140,6 +140,22 @@ namespace cds { namespace container { static CDS_CONSTEXPR const size_t c_nHazardPtrCount = base_class::c_nHazardPtrCount; ///< Count of hazard pointer required for the algorithm + //@cond + // Rebind traits (split-list support) + template + struct rebind_traits { + typedef MichaelList< + gc + , value_type + , typename cds::opt::make_options< traits, Options...>::type + > type; + }; + + // Stat selector + template + using select_stat_wrapper = typename base_class::template select_stat_wrapper< Stat >; + //@endcond + protected: //@cond typedef typename base_class::value_type node_type; @@ -148,39 +164,6 @@ namespace cds { namespace container { typedef typename maker::intrusive_traits::compare intrusive_key_comparator; typedef typename base_class::atomic_node_ptr head_type; - //@endcond - - public: - /// Guarded pointer - typedef typename gc::template guarded_ptr< node_type, value_type, details::guarded_ptr_cast_set > guarded_ptr; - - protected: - //@cond - static value_type& node_to_value( node_type& n ) - { - return n.m_Value; - } - static value_type const& node_to_value( node_type const& n ) - { - return n.m_Value; - } - - template - static node_type * alloc_node( Q const& v ) - { - return cxx_allocator().New( v ); - } - - template - static node_type * alloc_node( Args&&... args ) - { - return cxx_allocator().MoveNew( std::forward(args)... ); - } - - static void free_node( node_type * pNode ) - { - cxx_allocator().Delete( pNode ); - } struct node_disposer { void operator()( node_type * pNode ) @@ -189,18 +172,12 @@ namespace cds { namespace container { } }; typedef std::unique_ptr< node_type, node_disposer > scoped_node_ptr; - - head_type& head() - { - return base_class::m_pHead; - } - - head_type const& head() const - { - return base_class::m_pHead; - } //@endcond + public: + /// Guarded pointer + typedef typename gc::template guarded_ptr< node_type, value_type, details::guarded_ptr_cast_set > guarded_ptr; + protected: //@cond template @@ -364,9 +341,9 @@ namespace cds { namespace container { Returns \p true if inserting successful, \p false otherwise. */ template - bool insert( Q const& val ) + bool insert( Q&& val ) { - return insert_at( head(), val ); + return insert_at( head(), std::forward( val )); } /// Inserts new node @@ -394,9 +371,9 @@ namespace cds { namespace container { @warning See \ref cds_intrusive_item_creating "insert item troubleshooting" */ template - bool insert( Q const& key, Func func ) + bool insert( Q&& key, Func func ) { - return insert_at( head(), key, func ); + return insert_at( head(), std::forward(key), func ); } /// Updates data by \p key @@ -410,14 +387,14 @@ namespace cds { namespace container { The functor \p Func signature is: \code struct my_functor { - void operator()( bool bNew, value_type& item, Q const& val ); + void operator()( bool bNew, value_type& item, Q const& key ); }; \endcode with arguments: - \p bNew - \p true if the item has been inserted, \p false otherwise - \p item - item of the list - - \p val - argument \p key passed into the \p %update() function + - \p key - argument \p key passed into the \p %update() function The functor may change non-key fields of the \p item; however, \p func must guarantee that during changing no any other modifications could be made on this item by concurrent threads. @@ -665,7 +642,7 @@ namespace cds { namespace container { //@endcond /// Finds \p key and return the item found - /** \anchor cds_nonintrusive_MichaelList_hp_get + /** The function searches the item with key equal to \p key and returns it as \p guarded_ptr. If \p key is not found the function returns an empty guarded pointer. @@ -700,7 +677,7 @@ namespace cds { namespace container { /// Finds \p key and return the item found /** - The function is an analog of \ref cds_nonintrusive_MichaelList_hp_get "get( Q const&)" + The function is an analog of \p get( Q const&) but \p pred is used for comparing the keys. \p Less functor has the semantics like \p std::less but should accept arguments of type \p value_type and \p Q @@ -749,6 +726,42 @@ namespace cds { namespace container { protected: //@cond + static value_type& node_to_value( node_type& n ) + { + return n.m_Value; + } + static value_type const& node_to_value( node_type const& n ) + { + return n.m_Value; + } + + template + static node_type * alloc_node( Q const& v ) + { + return cxx_allocator().New( v ); + } + + template + static node_type * alloc_node( Args&&... args ) + { + return cxx_allocator().MoveNew( std::forward( args )... ); + } + + static void free_node( node_type * pNode ) + { + cxx_allocator().Delete( pNode ); + } + + head_type& head() + { + return base_class::m_pHead; + } + + head_type const& head() const + { + return base_class::m_pHead; + } + bool insert_node( node_type * pNode ) { return insert_node_at( head(), pNode ); @@ -767,15 +780,15 @@ namespace cds { namespace container { } template - bool insert_at( head_type& refHead, Q const& val ) + bool insert_at( head_type& refHead, Q&& val ) { - return insert_node_at( refHead, alloc_node( val )); + return insert_node_at( refHead, alloc_node( std::forward(val))); } template - bool insert_at( head_type& refHead, Q const& key, Func f ) + bool insert_at( head_type& refHead, Q&& key, Func f ) { - scoped_node_ptr pNode( alloc_node( key )); + scoped_node_ptr pNode( alloc_node( std::forward( key ))); if ( base_class::insert_at( refHead, *pNode, [&f]( node_type& node ) { f( node_to_value(node) ); } )) { pNode.release(); diff --git a/cds/container/lazy_list_nogc.h b/cds/container/lazy_list_nogc.h index 4227d8b3..5655b801 100644 --- a/cds/container/lazy_list_nogc.h +++ b/cds/container/lazy_list_nogc.h @@ -86,6 +86,22 @@ namespace cds { namespace container { static CDS_CONSTEXPR bool const c_bSort = base_class::c_bSort; ///< List type: ordered (\p true) or unordered (\p false) + //@cond + // Rebind traits (split-list support) + template + struct rebind_traits { + typedef LazyList< + gc + , value_type + , typename cds::opt::make_options< traits, Options...>::type + > type; + }; + + // Stat selector + template + using select_stat_wrapper = typename base_class::template select_stat_wrapper< Stat >; + //@endcond + protected: //@cond typedef typename base_class::value_type node_type; @@ -94,35 +110,6 @@ namespace cds { namespace container { typedef typename base_class::key_comparator intrusive_key_comparator; typedef typename base_class::node_type head_type; - //@endcond - - protected: - //@cond - static value_type& node_to_value( node_type& n ) - { - return n.m_Value; - } - - static node_type * alloc_node() - { - return cxx_allocator().New(); - } - - static node_type * alloc_node( value_type const& v ) - { - return cxx_allocator().New( v ); - } - - template - static node_type * alloc_node( Args&&... args ) - { - return cxx_allocator().MoveNew( std::forward(args)... ); - } - - static void free_node( node_type * pNode ) - { - cxx_allocator().Delete( pNode ); - } struct node_disposer { void operator()( node_type * pNode ) @@ -131,26 +118,6 @@ namespace cds { namespace container { } }; typedef std::unique_ptr< node_type, node_disposer > scoped_node_ptr; - - head_type& head() - { - return base_class::m_Head; - } - - head_type const& head() const - { - return base_class::m_Head; - } - - head_type& tail() - { - return base_class::m_Tail; - } - - head_type const& tail() const - { - return base_class::m_Tail; - } //@endcond protected: @@ -290,16 +257,6 @@ namespace cds { namespace container { } //@} - protected: - //@cond - iterator node_to_iterator( node_type * pNode ) - { - if ( pNode ) - return iterator( *pNode ); - return end(); - } - //@endcond - public: /// Default constructor LazyList() @@ -326,9 +283,9 @@ namespace cds { namespace container { Return an iterator pointing to inserted item if success \ref end() otherwise */ template - iterator insert( Q const& val ) + iterator insert( Q&& val ) { - return node_to_iterator( insert_at( head(), val ) ); + return node_to_iterator( insert_at( head(), std::forward( val )) ); } /// Inserts data of type \p value_type created from \p args @@ -344,7 +301,6 @@ namespace cds { namespace container { /// Updates the item /** If \p key is not in the list and \p bAllowInsert is \p true, - the function inserts a new item. Otherwise, the function returns an iterator pointing to the item found. @@ -353,9 +309,9 @@ namespace cds { namespace container { already is in the list. */ template - std::pair update( Q const& val, bool bAllowInsert = true ) + std::pair update( Q&& val, bool bAllowInsert = true ) { - std::pair< node_type *, bool > ret = update_at( head(), val, bAllowInsert ); + std::pair< node_type *, bool > ret = update_at( head(), std::forward( val ), bAllowInsert ); return std::make_pair( node_to_iterator( ret.first ), ret.second ); } //@cond @@ -461,6 +417,59 @@ namespace cds { namespace container { protected: //@cond + static value_type& node_to_value( node_type& n ) + { + return n.m_Value; + } + + static node_type * alloc_node() + { + return cxx_allocator().New(); + } + + static node_type * alloc_node( value_type const& v ) + { + return cxx_allocator().New( v ); + } + + template + static node_type * alloc_node( Args&&... args ) + { + return cxx_allocator().MoveNew( std::forward( args )... ); + } + + static void free_node( node_type * pNode ) + { + cxx_allocator().Delete( pNode ); + } + + head_type& head() + { + return base_class::m_Head; + } + + head_type const& head() const + { + return base_class::m_Head; + } + + head_type& tail() + { + return base_class::m_Tail; + } + + head_type const& tail() const + { + return base_class::m_Tail; + } + + iterator node_to_iterator( node_type * pNode ) + { + if ( pNode ) + return iterator( *pNode ); + return end(); + } + iterator insert_node( node_type * pNode ) { return node_to_iterator( insert_node_at( head(), pNode )); @@ -477,9 +486,9 @@ namespace cds { namespace container { } template - node_type * insert_at( head_type& refHead, Q const& val ) + node_type * insert_at( head_type& refHead, Q&& val ) { - return insert_node_at( refHead, alloc_node( val )); + return insert_node_at( refHead, alloc_node( std::forward( val ))); } template @@ -489,13 +498,13 @@ namespace cds { namespace container { } template - std::pair< node_type *, bool > update_at( head_type& refHead, Q const& val, bool bAllowInsert ) + std::pair< node_type *, bool > update_at( head_type& refHead, Q&& val, bool bAllowInsert ) { - scoped_node_ptr pNode( alloc_node( val )); + scoped_node_ptr pNode( alloc_node( std::forward( val ))); node_type * pItemFound = nullptr; std::pair ret = base_class::update_at( &refHead, *pNode, - [&pItemFound](bool, node_type& item, node_type&){ pItemFound = &item; }, + [&pItemFound](bool, node_type& item, node_type&) { pItemFound = &item; }, bAllowInsert ); if ( ret.second ) diff --git a/cds/container/michael_list_nogc.h b/cds/container/michael_list_nogc.h index 1bf897c7..42523607 100644 --- a/cds/container/michael_list_nogc.h +++ b/cds/container/michael_list_nogc.h @@ -100,6 +100,22 @@ namespace cds { namespace container { typedef typename base_class::memory_model memory_model; ///< Memory ordering. See cds::opt::memory_model option typedef typename base_class::stat stat; ///< Internal statistics + //@cond + // Rebind traits (split-list support) + template + struct rebind_traits { + typedef MichaelList< + gc + , value_type + , typename cds::opt::make_options< traits, Options...>::type + > type; + }; + + // Stat selector + template + using select_stat_wrapper = typename base_class::template select_stat_wrapper< Stat >; + //@endcond + protected: //@cond typedef typename base_class::value_type node_type; @@ -108,30 +124,6 @@ namespace cds { namespace container { typedef typename maker::intrusive_traits::compare intrusive_key_comparator; typedef typename base_class::atomic_node_ptr head_type; - //@endcond - - protected: - //@cond - static node_type * alloc_node() - { - return cxx_allocator().New(); - } - - static node_type * alloc_node( value_type const& v ) - { - return cxx_allocator().New( v ); - } - - template - static node_type * alloc_node( Args&&... args ) - { - return cxx_allocator().MoveNew( std::forward(args)... ); - } - - static void free_node( node_type * pNode ) - { - cxx_allocator().Delete( pNode ); - } struct node_disposer { void operator()( node_type * pNode ) @@ -139,17 +131,8 @@ namespace cds { namespace container { free_node( pNode ); } }; - typedef std::unique_ptr< node_type, node_disposer > scoped_node_ptr; - - head_type& head() - { - return base_class::m_pHead; - } - head_type const& head() const - { - return base_class::m_pHead; - } + typedef std::unique_ptr< node_type, node_disposer > scoped_node_ptr; //@endcond protected: @@ -284,16 +267,6 @@ namespace cds { namespace container { } //@} - protected: - //@cond - iterator node_to_iterator( node_type * pNode ) - { - if ( pNode ) - return iterator( *pNode ); - return end(); - } - //@endcond - public: /// Default constructor /** @@ -326,9 +299,9 @@ namespace cds { namespace container { Return an iterator pointing to inserted item if success \ref end() otherwise */ template - iterator insert( const Q& val ) + iterator insert( Q&& val ) { - return node_to_iterator( insert_at( head(), val ) ); + return node_to_iterator( insert_at( head(), std::forward( val )) ); } /// Updates the item @@ -342,9 +315,9 @@ namespace cds { namespace container { already is in the list. */ template - std::pair update( const Q& key, bool bAllowInsert = true ) + std::pair update( Q&& key, bool bAllowInsert = true ) { - std::pair< node_type *, bool > ret = update_at( head(), key, bAllowInsert ); + std::pair< node_type *, bool > ret = update_at( head(), std::forward( key ), bAllowInsert ); return std::make_pair( node_to_iterator( ret.first ), ret.second ); } //@cond @@ -445,6 +418,44 @@ namespace cds { namespace container { return n.m_Value; } + static node_type * alloc_node() + { + return cxx_allocator().New(); + } + + static node_type * alloc_node( value_type const& v ) + { + return cxx_allocator().New( v ); + } + + template + static node_type * alloc_node( Args&&... args ) + { + return cxx_allocator().MoveNew( std::forward( args )... ); + } + + static void free_node( node_type * pNode ) + { + cxx_allocator().Delete( pNode ); + } + + head_type& head() + { + return base_class::m_pHead; + } + + head_type const& head() const + { + return base_class::m_pHead; + } + + iterator node_to_iterator( node_type * pNode ) + { + if ( pNode ) + return iterator( *pNode ); + return end(); + } + iterator insert_node( node_type * pNode ) { return node_to_iterator( insert_node_at( head(), pNode )); @@ -461,15 +472,15 @@ namespace cds { namespace container { } template - node_type * insert_at( head_type& refHead, const Q& val ) + node_type * insert_at( head_type& refHead, Q&& val ) { - return insert_node_at( refHead, alloc_node( val )); + return insert_node_at( refHead, alloc_node( std::forward( val ))); } template - std::pair< node_type *, bool > update_at( head_type& refHead, const Q& val, bool bAllowInsert ) + std::pair< node_type *, bool > update_at( head_type& refHead, Q&& val, bool bAllowInsert ) { - scoped_node_ptr pNode( alloc_node( val )); + scoped_node_ptr pNode( alloc_node( std::forward( val ))); node_type * pItemFound = nullptr; std::pair ret = base_class::update_at( refHead, *pNode, @@ -492,7 +503,6 @@ namespace cds { namespace container { { return base_class::find_at( refHead, key, cmp ); } - //@endcond }; }} // namespace cds::container diff --git a/cds/container/michael_set.h b/cds/container/michael_set.h index b3819f69..bff19031 100644 --- a/cds/container/michael_set.h +++ b/cds/container/michael_set.h @@ -25,13 +25,14 @@ SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE - OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. */ #ifndef CDSLIB_CONTAINER_MICHAEL_SET_H #define CDSLIB_CONTAINER_MICHAEL_SET_H #include +#include #include namespace cds { namespace container { @@ -52,7 +53,8 @@ namespace cds { namespace container { - \p GC - Garbage collector used. You may use any \ref cds_garbage_collector "Garbage collector" from the \p libcds library. Note the \p GC must be the same as the \p GC used for \p OrderedList - - \p OrderedList - ordered list implementation used as bucket for hash set, for example, \p MichaelList. + - \p OrderedList - ordered list implementation used as bucket for hash set, possible implementations: + \p MichaelList, \p LazyList, \p IterableList. The ordered list implementation specifies the type \p T to be stored in the hash-set, the comparing functor for the type \p T and other features specific for the ordered list. - \p Traits - set traits, default is \p michael_set::traits. @@ -75,7 +77,7 @@ namespace cds { namespace container { \code // Our node type struct Foo { - std::string key_ ; // key field + std::string key_; // key field // ... other fields }; @@ -98,8 +100,8 @@ namespace cds { namespace container { Suppose, we have the following type \p Foo that we want to store in our \p %MichaelHashSet: \code struct Foo { - int nKey ; // key field - int nVal ; // value field + int nKey; // key field + int nVal; // value field }; \endcode @@ -166,67 +168,64 @@ namespace cds { namespace container { class MichaelHashSet { public: - typedef GC gc; ///< Garbage collector - typedef OrderedList bucket_type; ///< type of ordered list used as a bucket implementation - typedef Traits traits; ///< Set traits + typedef GC gc; ///< Garbage collector + typedef OrderedList ordered_list; ///< type of ordered list used as a bucket implementation + typedef Traits traits; ///< Set traits - typedef typename bucket_type::value_type value_type; ///< type of value to be stored in the list - typedef typename bucket_type::key_comparator key_comparator; ///< key comparison functor + typedef typename ordered_list::value_type value_type; ///< type of value to be stored in the list + typedef typename ordered_list::key_comparator key_comparator; ///< key comparison functor + typedef typename ordered_list::stat stat; ///< Internal statistics /// Hash functor for \ref value_type and all its derivatives that you use typedef typename cds::opt::v::hash_selector< typename traits::hash >::type hash; typedef typename traits::item_counter item_counter; ///< Item counter type + typedef typename traits::allocator allocator; ///< Bucket table allocator - typedef typename bucket_type::guarded_ptr guarded_ptr; ///< Guarded pointer - static CDS_CONSTEXPR const size_t c_nHazardPtrCount = bucket_type::c_nHazardPtrCount; ///< Count of hazard pointer required + static CDS_CONSTEXPR const size_t c_nHazardPtrCount = ordered_list::c_nHazardPtrCount; ///< Count of hazard pointer required - protected: - //@cond - class internal_bucket_type: public bucket_type - { - typedef bucket_type base_class; - public: - using base_class::node_type; - using base_class::alloc_node; - using base_class::insert_node; - using base_class::node_to_value; - }; + // GC and OrderedList::gc must be the same + static_assert( std::is_same::value, "GC and OrderedList::gc must be the same"); - /// Bucket table allocator - typedef cds::details::Allocator< internal_bucket_type, typename traits::allocator > bucket_table_allocator; - //@endcond + // atomicity::empty_item_counter is not allowed as a item counter + static_assert( !std::is_same::value, + "cds::atomicity::empty_item_counter is not allowed as a item counter"); - protected: - //@cond - item_counter m_ItemCounter; ///< Item counter - hash m_HashFunctor; ///< Hash functor - internal_bucket_type * m_Buckets; ///< bucket table - //@endcond +#ifdef CDS_DOXYGEN_INVOKED + /// Wrapped internal statistics for \p ordered_list + typedef implementatin_specific bucket_stat; +#else + typedef typename ordered_list::template select_stat_wrapper< typename ordered_list::stat > bucket_stat; +#endif + +#ifdef CDS_DOXYGEN_INVOKED + /// Internal bucket type - rebind \p ordered_list with empty item counter and wrapped internal statistics + typedef modified_ordered_list internal_bucket_type; +#else + typedef typename ordered_list::template rebind_traits< + cds::opt::item_counter< cds::atomicity::empty_item_counter > + , cds::opt::stat< typename bucket_stat::wrapped_stat > + >::type internal_bucket_type; +#endif + + /// Guarded pointer - a result of \p get() and \p extract() functions + typedef typename internal_bucket_type::guarded_ptr guarded_ptr; - private: //@cond - const size_t m_nHashBitmask; + /// Bucket table allocator + typedef typename allocator::template rebind< internal_bucket_type >::other bucket_table_allocator; //@endcond protected: //@cond - /// Calculates hash value of \p key - template - size_t hash_value( Q const& key ) const - { - return m_HashFunctor( key ) & m_nHashBitmask; - } - - /// Returns the bucket (ordered list) for \p key - template - internal_bucket_type& bucket( Q const& key ) - { - return m_Buckets[ hash_value( key ) ]; - } + size_t const m_nHashBitmask; + internal_bucket_type * m_Buckets; ///< bucket table + item_counter m_ItemCounter; ///< Item counter + hash m_HashFunctor; ///< Hash functor + typename bucket_stat::stat m_Stat; ///< Internal statistics //@endcond public: - ///@name Forward iterators (only for debugging purpose) + ///@name Forward iterators //@{ /// Forward iterator /** @@ -236,11 +235,14 @@ namespace cds { namespace container { For some GC (like as \p gc::HP), a guard is a limited resource per thread, so an exception (or assertion) "no free guard" may be thrown if the limit of guard count per thread is exceeded. - The iterator cannot be moved across thread boundary because it contains thread-private GC's guard. - - Iterator ensures thread-safety even if you delete the item the iterator points to. However, in case of concurrent - deleting operations there is no guarantee that you iterate all item in the set. - Moreover, a crash is possible when you try to iterate the next element that has been deleted by concurrent thread. - @warning Use this iterator on the concurrent container for debugging purpose only. + Iterator thread safety depends on type of \p OrderedList: + - for \p MichaelList and \p LazyList: iterator guarantees safety even if you delete the item that iterator points to + because that item is guarded by hazard pointer. + However, in case of concurrent deleting operations it is no guarantee that you iterate all item in the set. + Moreover, a crash is possible when you try to iterate the next element that has been deleted by concurrent thread. + Use this iterator on the concurrent container for debugging purpose only. + - for \p IterableList: iterator is thread-safe. You may use it freely in concurrent environment. The iterator interface: \code @@ -272,10 +274,10 @@ namespace cds { namespace container { */ /// Forward iterator - typedef michael_set::details::iterator< bucket_type, false > iterator; + typedef michael_set::details::iterator< internal_bucket_type, false > iterator; /// Const forward iterator - typedef michael_set::details::iterator< bucket_type, true > const_iterator; + typedef michael_set::details::iterator< internal_bucket_type, true > const_iterator; /// Returns a forward iterator addressing the first element in a set /** @@ -283,7 +285,7 @@ namespace cds { namespace container { */ iterator begin() { - return iterator( m_Buckets[0].begin(), m_Buckets, m_Buckets + bucket_count() ); + return iterator( bucket_begin()->begin(), bucket_begin(), bucket_end()); } /// Returns an iterator that addresses the location succeeding the last element in a set @@ -294,7 +296,7 @@ namespace cds { namespace container { */ iterator end() { - return iterator( m_Buckets[bucket_count() - 1].end(), m_Buckets + bucket_count() - 1, m_Buckets + bucket_count() ); + return iterator( bucket_end()[-1].end(), bucket_end() - 1, bucket_end()); } /// Returns a forward const iterator addressing the first element in a set @@ -322,21 +324,9 @@ namespace cds { namespace container { } //@} - private: - //@cond - const_iterator get_const_begin() const - { - return const_iterator( const_cast(m_Buckets[0]).begin(), m_Buckets, m_Buckets + bucket_count() ); - } - const_iterator get_const_end() const - { - return const_iterator( const_cast(m_Buckets[bucket_count() - 1]).end(), m_Buckets + bucket_count() - 1, m_Buckets + bucket_count() ); - } - //@endcond - public: /// Initialize hash set - /** @anchor cds_nonintrusive_MichaelHashSet_hp_ctor + /** The Michael's hash set is non-expandable container. You should point the average count of items \p nMaxItemCount when you create an object. \p nLoadFactor parameter defines average count of items per bucket and it should be small number between 1 and 10. @@ -348,22 +338,20 @@ namespace cds { namespace container { size_t nMaxItemCount, ///< estimation of max item count in the hash set size_t nLoadFactor ///< load factor: estimation of max number of items in the bucket ) : m_nHashBitmask( michael_set::details::init_hash_bitmask( nMaxItemCount, nLoadFactor )) + , m_Buckets( bucket_table_allocator().allocate( bucket_count() ) ) { - // GC and OrderedList::gc must be the same - static_assert( std::is_same::value, "GC and OrderedList::gc must be the same"); - - // atomicity::empty_item_counter is not allowed as a item counter - static_assert( !std::is_same::value, - "cds::atomicity::empty_item_counter is not allowed as a item counter"); - - m_Buckets = bucket_table_allocator().NewArray( bucket_count() ); + for ( auto it = m_Buckets, itEnd = m_Buckets + bucket_count(); it != itEnd; ++it ) + construct_bucket( it ); } /// Clears hash set and destroys it ~MichaelHashSet() { clear(); - bucket_table_allocator().Delete( m_Buckets, bucket_count() ); + + for ( auto it = m_Buckets, itEnd = m_Buckets + bucket_count(); it != itEnd; ++it ) + it->~internal_bucket_type(); + bucket_table_allocator().deallocate( m_Buckets, bucket_count() ); } /// Inserts new node @@ -378,9 +366,9 @@ namespace cds { namespace container { Returns \p true if \p val is inserted into the set, \p false otherwise. */ template - bool insert( Q const& val ) + bool insert( Q&& val ) { - const bool bRet = bucket( val ).insert( val ); + const bool bRet = bucket( val ).insert( std::forward( val )); if ( bRet ) ++m_ItemCounter; return bRet; @@ -400,14 +388,15 @@ namespace cds { namespace container { where \p val is the item inserted. The user-defined functor is called only if the inserting is success. - @warning For \ref cds_nonintrusive_MichaelList_gc "MichaelList" as the bucket see \ref cds_intrusive_item_creating "insert item troubleshooting". + @warning For \ref cds_nonintrusive_MichaelList_gc "MichaelList" and \ref cds_nonintrusive_IterableList_gc "IterableList" + as the bucket see \ref cds_intrusive_item_creating "insert item troubleshooting". @ref cds_nonintrusive_LazyList_gc "LazyList" provides exclusive access to inserted item and does not require any node-level synchronization. */ template - bool insert( Q const& val, Func f ) + bool insert( Q&& val, Func f ) { - const bool bRet = bucket( val ).insert( val, f ); + const bool bRet = bucket( val ).insert( std::forward( val ), f ); if ( bRet ) ++m_ItemCounter; return bRet; @@ -419,7 +408,10 @@ namespace cds { namespace container { If the item \p val not found in the set, then \p val is inserted iff \p bAllowInsert is \p true. Otherwise, the functor \p func is called with item found. - The functor signature is: + + The functor \p func signature depends of \p OrderedList: + + for \p MichaelList, \p LazyList \code struct functor { void operator()( bool bNew, value_type& item, Q const& val ); @@ -432,18 +424,27 @@ namespace cds { namespace container { The functor may change non-key fields of the \p item. - Returns std::pair where \p first is \p true if operation is successful, + for \p IterableList + \code + void func( value_type& val, value_type * old ); + \endcode + where + - \p val - a new data constructed from \p key + - \p old - old value that will be retired. If new item has been inserted then \p old is \p nullptr. + + @return std::pair where \p first is \p true if operation is successful, \p second is \p true if new item has been added or \p false if the item with \p key already is in the set. - @warning For \ref cds_intrusive_MichaelList_hp "MichaelList" as the bucket see \ref cds_intrusive_item_creating "insert item troubleshooting". + @warning For \ref cds_intrusive_MichaelList_hp "MichaelList" and \ref cds_nonintrusive_IterableList_gc "IterableList" + as the bucket see \ref cds_intrusive_item_creating "insert item troubleshooting". \ref cds_intrusive_LazyList_hp "LazyList" provides exclusive access to inserted item and does not require any node-level synchronization. */ template - std::pair update( const Q& val, Func func, bool bAllowUpdate = true ) + std::pair update( Q&& val, Func func, bool bAllowUpdate = true ) { - std::pair bRet = bucket( val ).update( val, func, bAllowUpdate ); + std::pair bRet = bucket( val ).update( std::forward( val ), func, bAllowUpdate ); if ( bRet.second ) ++m_ItemCounter; return bRet; @@ -457,6 +458,35 @@ namespace cds { namespace container { } //@endcond + /// Inserts or updates the node (only for \p IterableList) + /** + The operation performs inserting or changing data with lock-free manner. + + If the item \p val is not found in the set, then \p val is inserted iff \p bAllowInsert is \p true. + Otherwise, the current element is changed to \p val, the old element will be retired later + by call \p Traits::disposer. + + Returns std::pair where \p first is \p true if operation is successful, + \p second is \p true if \p val has been added or \p false if the item with that key + already in the set. + */ + template +#ifdef CDS_DOXYGEN_INVOKED + std::pair +#else + typename std::enable_if< + std::is_same< Q, Q>::value && is_iterable_list< ordered_list >::value, + std::pair + >::type +#endif + upsert( Q&& val, bool bAllowInsert = true ) + { + std::pair bRet = bucket( val ).upsert( std::forward( val ), bAllowInsert ); + if ( bRet.second ) + ++m_ItemCounter; + return bRet; + } + /// Inserts data of type \p value_type constructed from \p args /** Returns \p true if inserting successful, \p false otherwise. @@ -464,22 +494,20 @@ namespace cds { namespace container { template bool emplace( Args&&... args ) { - typename internal_bucket_type::node_type * pNode = internal_bucket_type::alloc_node( std::forward( args )... ); - bool bRet = bucket( internal_bucket_type::node_to_value( *pNode )).insert_node( pNode ); + bool bRet = bucket_emplace( std::forward(args)... ); if ( bRet ) ++m_ItemCounter; return bRet; } /// Deletes \p key from the set - /** \anchor cds_nonintrusive_MichaelSet_erase_val - - Since the key of MichaelHashSet's item type \ref value_type is not explicitly specified, + /** + Since the key of MichaelHashSet's item type \p value_type is not explicitly specified, template parameter \p Q defines the key type searching in the list. The set item comparator should be able to compare the type \p value_type and the type \p Q. - Return \p true if key is found and deleted, \p false otherwise + Return \p true if key is found and deleted, \p false otherwise. */ template bool erase( Q const& key ) @@ -492,8 +520,7 @@ namespace cds { namespace container { /// Deletes the item from the set using \p pred predicate for searching /** - The function is an analog of \ref cds_nonintrusive_MichaelSet_erase_val "erase(Q const&)" - but \p pred is used for key comparing. + The function is an analog of \p erase(Q const&) but \p pred is used for key comparing. \p Less functor has the interface like \p std::less. \p Less must imply the same element order as the comparator used for building the set. */ @@ -507,8 +534,7 @@ namespace cds { namespace container { } /// Deletes \p key from the set - /** \anchor cds_nonintrusive_MichaelSet_erase_func - + /** 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. @@ -538,8 +564,7 @@ namespace cds { namespace container { /// Deletes the item from the set using \p pred predicate for searching /** - The function is an analog of \ref cds_nonintrusive_MichaelSet_erase_func "erase(Q const&, Func)" - but \p pred is used for key comparing. + The function is an analog of \p erase(Q const&, Func) but \p pred is used for key comparing. \p Less functor has the interface like \p std::less. \p Less must imply the same element order as the comparator used for building the set. */ @@ -569,7 +594,7 @@ namespace cds { namespace container { michael_set theSet; // ... { - michael_set::guarded_ptr gp( theSet.extract( 5 )); + typename michael_set::guarded_ptr gp( theSet.extract( 5 )); if ( gp ) { // Deal with gp // ... @@ -589,11 +614,11 @@ namespace cds { namespace container { /// Extracts the item using compare functor \p pred /** - The function is an analog of \ref cds_nonintrusive_MichaelHashSet_hp_extract "extract(Q const&)" + The function is an analog of \p extract(Q const&) but \p pred predicate is used for key comparing. - \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q - in any order. + \p Less functor has the semantics like \p std::less but should take arguments + of type \p value_type and \p Q in any order. \p pred must imply the same element order as the comparator used for building the set. */ template @@ -606,8 +631,7 @@ namespace cds { namespace container { } /// Finds the key \p key - /** \anchor cds_nonintrusive_MichaelSet_find_func - + /** The function searches the item with key equal to \p key and calls the functor \p f for item found. The interface of \p Func functor is: \code @@ -643,10 +667,42 @@ namespace cds { namespace container { } //@endcond + /// Finds \p key and returns iterator pointed to the item found (only for \p IterableList) + /** + If \p key is not found the function returns \p end(). + + @note This function is supported only for the set based on \p IterableList + */ + template +#ifdef CDS_DOXYGEN_INVOKED + iterator +#else + typename std::enable_if< std::is_same::value && is_iterable_list< ordered_list >::value, iterator >::type +#endif + find( Q& key ) + { + internal_bucket_type& b = bucket( key ); + typename internal_bucket_type::iterator it = b.find( key ); + if ( it == b.end() ) + return end(); + return iterator( it, &b, bucket_end()); + } + //@cond + template + typename std::enable_if< std::is_same::value && is_iterable_list< ordered_list >::value, iterator >::type + find( Q const& key ) + { + internal_bucket_type& b = bucket( key ); + typename internal_bucket_type::iterator it = b.find( key ); + if ( it == b.end() ) + return end(); + return iterator( it, &b, bucket_end() ); + } + //@endcond + /// Finds the key \p key using \p pred predicate for searching /** - The function is an analog of \ref cds_nonintrusive_MichaelSet_find_func "find(Q&, Func)" - but \p pred is used for key comparing. + The function is an analog of \p find(Q&, Func) but \p pred is used for key comparing. \p Less functor has the interface like \p std::less. \p Less must imply the same element order as the comparator used for building the set. */ @@ -663,9 +719,45 @@ namespace cds { namespace container { } //@endcond - /// Checks whether the set contains \p key + /// Finds \p key using \p pred predicate and returns iterator pointed to the item found (only for \p IterableList) /** + The function is an analog of \p find(Q&) but \p pred is used for key comparing. + \p Less functor has the interface like \p std::less. + \p pred must imply the same element order as the comparator used for building the set. + + If \p key is not found the function returns \p end(). + @note This function is supported only for the set based on \p IterableList + */ + template +#ifdef CDS_DOXYGEN_INVOKED + iterator +#else + typename std::enable_if< std::is_same::value && is_iterable_list< ordered_list >::value, iterator >::type +#endif + find_with( Q& key, Less pred ) + { + internal_bucket_type& b = bucket( key ); + typename internal_bucket_type::iterator it = b.find_with( key, pred ); + if ( it == b.end() ) + return end(); + return iterator( it, &b, bucket_end() ); + } + //@cond + template + typename std::enable_if< std::is_same::value && is_iterable_list< ordered_list >::value, iterator >::type + find_with( Q const& key, Less pred ) + { + internal_bucket_type& b = bucket( key ); + typename internal_bucket_type::iterator it = b.find_with( key, pred ); + if ( it == b.end() ) + return end(); + return iterator( it, &b, bucket_end() ); + } + //@endcond + + /// Checks whether the set contains \p key + /** The function searches the item with key equal to \p key and returns \p true if the key is found, and \p false otherwise. @@ -677,14 +769,6 @@ namespace cds { namespace container { { return bucket( key ).contains( key ); } - //@cond - template - CDS_DEPRECATED("use contains()") - bool find( Q const& key ) - { - return contains( key ); - } - //@endcond /// Checks whether the set contains \p key using \p pred predicate for searching /** @@ -697,14 +781,6 @@ namespace cds { namespace container { { return bucket( key ).contains( key, pred ); } - //@cond - template - CDS_DEPRECATED("use contains()") - bool find_with( Q const& key, Less pred ) - { - return contains( key, pred ); - } - //@endcond /// Finds the key \p key and return the item found /** \anchor cds_nonintrusive_MichaelHashSet_hp_get @@ -720,7 +796,7 @@ namespace cds { namespace container { michael_set theSet; // ... { - michael_set::guarded_ptr gp( theSet.get( 5 )); + typename michael_set::guarded_ptr gp( theSet.get( 5 )); if ( gp ) { // Deal with gp //... @@ -785,6 +861,12 @@ namespace cds { namespace container { return m_ItemCounter; } + /// Returns const reference to internal statistics + stat const& statistics() const + { + return m_Stat; + } + /// Returns the size of hash table /** Since MichaelHashSet cannot dynamically extend the hash table size, @@ -795,6 +877,95 @@ namespace cds { namespace container { { return m_nHashBitmask + 1; } + + protected: + //@cond + /// Calculates hash value of \p key + template + size_t hash_value( Q const& key ) const + { + return m_HashFunctor( key ) & m_nHashBitmask; + } + + /// Returns the bucket (ordered list) for \p key + template + internal_bucket_type& bucket( Q const& key ) + { + return m_Buckets[ hash_value( key ) ]; + } + template + internal_bucket_type const& bucket( Q const& key ) const + { + return m_Buckets[hash_value( key )]; + } + //@endcond + + private: + //@cond + internal_bucket_type* bucket_begin() const + { + return m_Buckets; + } + + internal_bucket_type* bucket_end() const + { + return m_Buckets + bucket_count(); + } + + const_iterator get_const_begin() const + { + return const_iterator( bucket_begin()->cbegin(), bucket_begin(), bucket_end() ); + } + const_iterator get_const_end() const + { + return const_iterator(( bucket_end() -1 )->cend(), bucket_end() - 1, bucket_end() ); + } + + template + typename std::enable_if< Stat::empty >::type construct_bucket( internal_bucket_type* bucket ) + { + new (bucket) internal_bucket_type; + } + + template + typename std::enable_if< !Stat::empty >::type construct_bucket( internal_bucket_type* bucket ) + { + new (bucket) internal_bucket_type( m_Stat ); + } + + template + typename std::enable_if< !is_iterable_list::value, bool>::type + bucket_emplace( Args&&... args ) + { + class list_accessor: public List + { + public: + using List::alloc_node; + using List::node_to_value; + using List::insert_node; + }; + + auto pNode = list_accessor::alloc_node( std::forward( args )... ); + assert( pNode != nullptr ); + return static_cast( bucket( list_accessor::node_to_value( *pNode ))).insert_node( pNode ); + } + + template + typename std::enable_if< is_iterable_list::value, bool>::type + bucket_emplace( Args&&... args ) + { + class list_accessor: public List + { + public: + using List::alloc_data; + using List::insert_node; + }; + + auto pData = list_accessor::alloc_data( std::forward( args )... ); + assert( pData != nullptr ); + return static_cast( bucket( *pData )).insert_node( pData ); + } + //@endcond }; }} // namespace cds::container diff --git a/cds/container/michael_set_nogc.h b/cds/container/michael_set_nogc.h index b3e7db4b..aaa7ee5b 100644 --- a/cds/container/michael_set_nogc.h +++ b/cds/container/michael_set_nogc.h @@ -33,7 +33,6 @@ #include #include -#include namespace cds { namespace container { @@ -59,23 +58,40 @@ namespace cds { namespace container { class MichaelHashSet< cds::gc::nogc, OrderedList, Traits > { public: - typedef cds::gc::nogc gc; ///< Garbage collector - typedef OrderedList bucket_type; ///< type of ordered list to be used as a bucket implementation - typedef Traits traits; ///< Set traits + typedef cds::gc::nogc gc; ///< Garbage collector + typedef OrderedList ordered_list; ///< type of ordered list to be used as a bucket implementation + typedef Traits traits; ///< Set traits - typedef typename bucket_type::value_type value_type; ///< type of value stored in the list - typedef typename bucket_type::key_comparator key_comparator; ///< key comparison functor + typedef typename ordered_list::value_type value_type; ///< type of value stored in the list + typedef typename ordered_list::key_comparator key_comparator; ///< key comparison functor + typedef typename ordered_list::stat stat; ///< Internal statistics /// Hash functor for \ref value_type and all its derivatives that you use typedef typename cds::opt::v::hash_selector< typename traits::hash >::type hash; - typedef typename traits::item_counter item_counter; ///< Item counter type + typedef typename traits::item_counter item_counter; ///< Item counter type + typedef typename traits::allocator allocator; ///< Bucket table allocator + + // GC and OrderedList::gc must be the same + static_assert(std::is_same::value, "GC and OrderedList::gc must be the same"); + + // atomicity::empty_item_counter is not allowed as a item counter + static_assert(!std::is_same::value, + "cds::atomicity::empty_item_counter is not allowed as a item counter"); protected: //@cond - class internal_bucket_type: public bucket_type + typedef typename ordered_list::template select_stat_wrapper< typename ordered_list::stat > bucket_stat; + + typedef typename ordered_list::template rebind_traits< + cds::opt::item_counter< cds::atomicity::empty_item_counter > + , cds::opt::stat< typename bucket_stat::wrapped_stat > + >::type internal_bucket_type_; + + class internal_bucket_type: public internal_bucket_type_ { - typedef bucket_type base_class; + typedef internal_bucket_type_ base_class; public: + using base_class::base_class; using base_class::node_type; using base_class::alloc_node; using base_class::insert_node; @@ -83,39 +99,19 @@ namespace cds { namespace container { }; /// Bucket table allocator - typedef cds::details::Allocator< internal_bucket_type, typename traits::allocator > bucket_table_allocator; + typedef typename allocator::template rebind< internal_bucket_type >::other bucket_table_allocator; - typedef typename bucket_type::iterator bucket_iterator; - typedef typename bucket_type::const_iterator bucket_const_iterator; + typedef typename internal_bucket_type::iterator bucket_iterator; + typedef typename internal_bucket_type::const_iterator bucket_const_iterator; //@endcond protected: - //@cond - item_counter m_ItemCounter; ///< Item counter - hash m_HashFunctor; ///< Hash functor - internal_bucket_type * m_Buckets; ///< bucket table - //@endcond - - private: //@cond const size_t m_nHashBitmask; - //@endcond - - protected: - //@cond - /// Calculates hash value of \p key - template - size_t hash_value( const Q& key ) const - { - return m_HashFunctor( key ) & m_nHashBitmask; - } - - /// Returns the bucket (ordered list) for \p key - template - internal_bucket_type& bucket( const Q& key ) - { - return m_Buckets[ hash_value( key ) ]; - } + item_counter m_ItemCounter; ///< Item counter + hash m_HashFunctor; ///< Hash functor + internal_bucket_type* m_Buckets; ///< bucket table + typename bucket_stat::stat m_Stat; ///< Internal statistics //@endcond public: @@ -155,13 +151,13 @@ namespace cds { namespace container { }; \endcode */ - typedef michael_set::details::iterator< bucket_type, false > iterator; + typedef michael_set::details::iterator< internal_bucket_type, false > iterator; /// Const forward iterator /** For iterator's features and requirements see \ref iterator */ - typedef michael_set::details::iterator< bucket_type, true > const_iterator; + typedef michael_set::details::iterator< internal_bucket_type, true > const_iterator; /// Returns a forward iterator addressing the first element in a set /** @@ -208,18 +204,6 @@ namespace cds { namespace container { } //@} - private: - //@cond - const_iterator get_const_begin() const - { - return const_iterator( const_cast(m_Buckets[0]).begin(), m_Buckets, m_Buckets + bucket_count() ); - } - const_iterator get_const_end() const - { - return const_iterator( const_cast(m_Buckets[bucket_count() - 1]).end(), m_Buckets + bucket_count() - 1, m_Buckets + bucket_count() ); - } - //@endcond - public: /// Initialize hash set /** @@ -234,22 +218,19 @@ namespace cds { namespace container { size_t nMaxItemCount, ///< estimation of max item count in the hash set size_t nLoadFactor ///< load factor: estimation of max number of items in the bucket ) : m_nHashBitmask( michael_set::details::init_hash_bitmask( nMaxItemCount, nLoadFactor )) + , m_Buckets( bucket_table_allocator().allocate( bucket_count() ) ) { - // GC and OrderedList::gc must be the same - static_assert( std::is_same::value, "GC and OrderedList::gc must be the same"); - - // atomicity::empty_item_counter is not allowed as a item counter - static_assert( !std::is_same::value, - "cds::atomicity::empty_item_counter is not allowed as a item counter"); - - m_Buckets = bucket_table_allocator().NewArray( bucket_count() ); + for ( auto it = m_Buckets, itEnd = m_Buckets + bucket_count(); it != itEnd; ++it ) + construct_bucket( it ); } /// Clears hash set and destroys it ~MichaelHashSet() { clear(); - bucket_table_allocator().Delete( m_Buckets, bucket_count() ); + for ( auto it = m_Buckets, itEnd = m_Buckets + bucket_count(); it != itEnd; ++it ) + it->~internal_bucket_type(); + bucket_table_allocator().deallocate( m_Buckets, bucket_count() ); } /// Inserts new node @@ -405,6 +386,12 @@ namespace cds { namespace container { return m_ItemCounter; } + /// Returns const reference to internal statistics + stat const& statistics() const + { + return m_Stat; + } + /// Returns the size of hash table /** Since \p %MichaelHashSet cannot dynamically extend the hash table size, @@ -415,6 +402,47 @@ namespace cds { namespace container { { return m_nHashBitmask + 1; } + + protected: + //@cond + /// Calculates hash value of \p key + template + size_t hash_value( const Q& key ) const + { + return m_HashFunctor( key ) & m_nHashBitmask; + } + + /// Returns the bucket (ordered list) for \p key + template + internal_bucket_type& bucket( const Q& key ) + { + return m_Buckets[hash_value( key )]; + } + //@endcond + + private: + //@cond + template + typename std::enable_if< Stat::empty >::type construct_bucket( internal_bucket_type* bucket ) + { + new (bucket) internal_bucket_type; + } + + template + typename std::enable_if< !Stat::empty >::type construct_bucket( internal_bucket_type* bucket ) + { + new (bucket) internal_bucket_type( m_Stat ); + } + + const_iterator get_const_begin() const + { + return const_iterator( const_cast(m_Buckets[0]).begin(), m_Buckets, m_Buckets + bucket_count() ); + } + const_iterator get_const_end() const + { + return const_iterator( const_cast(m_Buckets[bucket_count() - 1]).end(), m_Buckets + bucket_count() - 1, m_Buckets + bucket_count() ); + } + //@endcond }; }} // cds::container diff --git a/cds/intrusive/michael_set.h b/cds/intrusive/michael_set.h index b264bb1f..8cc7fe9a 100644 --- a/cds/intrusive/michael_set.h +++ b/cds/intrusive/michael_set.h @@ -50,7 +50,8 @@ namespace cds { namespace intrusive { Template parameters are: - \p GC - Garbage collector used. Note the \p GC must be the same as the GC used for \p OrderedList - - \p OrderedList - ordered list implementation used as bucket for hash set, for example, \p MichaelList, \p LazyList, \p IterableList. + - \p OrderedList - ordered list implementation used as bucket for hash set, possible implementations: + \p MichaelList, \p LazyList, \p IterableList. The intrusive ordered list implementation specifies the type \p T stored in the hash-set, the reclamation schema \p GC used by hash-set, the comparison functor for the type \p T and other features specific for the ordered list. @@ -364,7 +365,7 @@ namespace cds { namespace intrusive { public: /// Initializes hash set - /** @anchor cds_intrusive_MichaelHashSet_hp_ctor + /** The Michael's hash set is an unbounded container, but its hash table is non-expandable. At construction time you should pass estimated maximum item count and a load factor. The load factor is average size of one bucket - a small number between 1 and 10. diff --git a/projects/Win/vc14/gtest-set.vcxproj b/projects/Win/vc14/gtest-set.vcxproj index a8763524..d67504e4 100644 --- a/projects/Win/vc14/gtest-set.vcxproj +++ b/projects/Win/vc14/gtest-set.vcxproj @@ -35,6 +35,8 @@ + + 4503 4503 @@ -206,10 +208,13 @@ + + + diff --git a/projects/Win/vc14/gtest-set.vcxproj.filters b/projects/Win/vc14/gtest-set.vcxproj.filters index 80a2f7e6..4fe9b8d8 100644 --- a/projects/Win/vc14/gtest-set.vcxproj.filters +++ b/projects/Win/vc14/gtest-set.vcxproj.filters @@ -171,6 +171,12 @@ Source Files\FeldmanHashSet + + Source Files\MichaelSet + + + Source Files\MichaelSet + @@ -212,5 +218,14 @@ Header Files + + Header Files + + + Header Files + + + Header Files + \ No newline at end of file diff --git a/test/unit/set/CMakeLists.txt b/test/unit/set/CMakeLists.txt index dcd684a1..8178121d 100644 --- a/test/unit/set/CMakeLists.txt +++ b/test/unit/set/CMakeLists.txt @@ -9,6 +9,8 @@ set(CDSGTEST_SET_SOURCES feldman_hashset_rcu_gpt.cpp feldman_hashset_rcu_shb.cpp feldman_hashset_rcu_sht.cpp + michael_iterable_hp.cpp + michael_iterable_dhp.cpp michael_lazy_hp.cpp michael_lazy_dhp.cpp michael_lazy_nogc.cpp diff --git a/test/unit/set/michael_iterable_dhp.cpp b/test/unit/set/michael_iterable_dhp.cpp new file mode 100644 index 00000000..0ff99a88 --- /dev/null +++ b/test/unit/set/michael_iterable_dhp.cpp @@ -0,0 +1,218 @@ +/* + This file is a part of libcds - Concurrent Data Structures library + + (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016 + + Source code repo: http://github.com/khizmax/libcds/ + Download: http://sourceforge.net/projects/libcds/files/ + + Redistribution and use in source and binary forms, with or without + modification, are permitted provided that the following conditions are met: + + * Redistributions of source code must retain the above copyright notice, this + list of conditions and the following disclaimer. + + * Redistributions in binary form must reproduce the above copyright notice, + this list of conditions and the following disclaimer in the documentation + and/or other materials provided with the distribution. + + THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" + AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE + FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR + SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER + CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, + OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. +*/ + +#include "test_michael_iterable_hp.h" + +#include +#include + +namespace { + namespace cc = cds::container; + typedef cds::gc::DHP gc_type; + + class MichaelIterableSet_DHP : public cds_test::michael_iterable_set_hp + { + protected: + typedef cds_test::michael_iterable_set_hp base_class; + + void SetUp() + { + typedef cc::IterableList< gc_type, int_item > list_type; + typedef cc::MichaelHashSet< gc_type, list_type > set_type; + + cds::gc::dhp::GarbageCollector::Construct( 16, set_type::c_nHazardPtrCount ); + cds::threading::Manager::attachThread(); + } + + void TearDown() + { + cds::threading::Manager::detachThread(); + cds::gc::dhp::GarbageCollector::Destruct(); + } + }; + + TEST_F( MichaelIterableSet_DHP, compare ) + { + typedef cc::IterableList< gc_type, int_item, + typename cc::iterable_list::make_traits< + cds::opt::compare< cmp > + >::type + > list_type; + + typedef cc::MichaelHashSet< gc_type, list_type, + typename cc::michael_set::make_traits< + cds::opt::hash< hash_int > + >::type + > set_type; + + set_type s( kSize, 2 ); + test( s ); + } + + TEST_F( MichaelIterableSet_DHP, less ) + { + typedef cc::IterableList< gc_type, int_item, + typename cc::iterable_list::make_traits< + cds::opt::less< base_class::less > + >::type + > list_type; + + typedef cc::MichaelHashSet< gc_type, list_type, + typename cc::michael_set::make_traits< + cds::opt::hash< hash_int > + >::type + > set_type; + + set_type s( kSize, 2 ); + test( s ); + } + + TEST_F( MichaelIterableSet_DHP, cmpmix ) + { + struct list_traits : public cc::iterable_list::traits + { + typedef base_class::less less; + typedef cmp compare; + }; + typedef cc::IterableList< gc_type, int_item, list_traits > list_type; + + typedef cc::MichaelHashSet< gc_type, list_type, + typename cc::michael_set::make_traits< + cds::opt::hash< hash_int > + >::type + > set_type; + + set_type s( kSize, 2 ); + test( s ); + } + + TEST_F( MichaelIterableSet_DHP, item_counting ) + { + struct list_traits : public cc::iterable_list::traits + { + typedef cmp compare; + }; + typedef cc::IterableList< gc_type, int_item, list_traits > list_type; + + struct set_traits: public cc::michael_set::traits + { + typedef hash_int hash; + typedef simple_item_counter item_counter; + }; + typedef cc::MichaelHashSet< gc_type, list_type, set_traits > set_type; + + set_type s( kSize, 3 ); + test( s ); + } + + TEST_F( MichaelIterableSet_DHP, backoff ) + { + struct list_traits : public cc::iterable_list::traits + { + typedef cmp compare; + typedef cds::backoff::exponential back_off; + }; + typedef cc::IterableList< gc_type, int_item, list_traits > list_type; + + struct set_traits : public cc::michael_set::traits + { + typedef hash_int hash; + typedef cds::atomicity::item_counter item_counter; + }; + typedef cc::MichaelHashSet< gc_type, list_type, set_traits > set_type; + + set_type s( kSize, 4 ); + test( s ); + } + + TEST_F( MichaelIterableSet_DHP, seq_cst ) + { + struct list_traits : public cc::iterable_list::traits + { + typedef base_class::less less; + typedef cds::backoff::pause back_off; + typedef cds::opt::v::sequential_consistent memory_model; + }; + typedef cc::IterableList< gc_type, int_item, list_traits > list_type; + + struct set_traits : public cc::michael_set::traits + { + typedef hash_int hash; + typedef cds::atomicity::item_counter item_counter; + }; + typedef cc::MichaelHashSet< gc_type, list_type, set_traits > set_type; + + set_type s( kSize, 4 ); + test( s ); + } + + TEST_F( MichaelIterableSet_DHP, stat ) + { + struct list_traits: public cc::iterable_list::traits + { + typedef base_class::less less; + typedef cds::backoff::pause back_off; + typedef cc::iterable_list::stat<> stat; + }; + typedef cc::IterableList< gc_type, int_item, list_traits > list_type; + + struct set_traits: public cc::michael_set::traits + { + typedef hash_int hash; + typedef cds::atomicity::item_counter item_counter; + }; + typedef cc::MichaelHashSet< gc_type, list_type, set_traits > set_type; + + set_type s( kSize, 4 ); + test( s ); + } + + TEST_F( MichaelIterableSet_DHP, wrapped_stat ) + { + struct list_traits: public cc::iterable_list::traits + { + typedef base_class::less less; + typedef cds::backoff::pause back_off; + typedef cc::iterable_list::wrapped_stat<> stat; + }; + typedef cc::IterableList< gc_type, int_item, list_traits > list_type; + + struct set_traits: public cc::michael_set::traits + { + typedef hash_int hash; + typedef cds::atomicity::item_counter item_counter; + }; + typedef cc::MichaelHashSet< gc_type, list_type, set_traits > set_type; + + set_type s( kSize, 4 ); + test( s ); + } + +} // namespace diff --git a/test/unit/set/michael_iterable_hp.cpp b/test/unit/set/michael_iterable_hp.cpp new file mode 100644 index 00000000..b3313e75 --- /dev/null +++ b/test/unit/set/michael_iterable_hp.cpp @@ -0,0 +1,219 @@ +/* + This file is a part of libcds - Concurrent Data Structures library + + (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016 + + Source code repo: http://github.com/khizmax/libcds/ + Download: http://sourceforge.net/projects/libcds/files/ + + Redistribution and use in source and binary forms, with or without + modification, are permitted provided that the following conditions are met: + + * Redistributions of source code must retain the above copyright notice, this + list of conditions and the following disclaimer. + + * Redistributions in binary form must reproduce the above copyright notice, + this list of conditions and the following disclaimer in the documentation + and/or other materials provided with the distribution. + + THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" + AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE + FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR + SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER + CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, + OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. +*/ + +#include "test_michael_iterable_hp.h" + +#include +#include + +namespace { + namespace cc = cds::container; + typedef cds::gc::HP gc_type; + + class MichaelIterableSet_HP : public cds_test::michael_iterable_set_hp + { + protected: + typedef cds_test::michael_iterable_set_hp base_class; + + void SetUp() + { + typedef cc::IterableList< gc_type, int_item > list_type; + typedef cc::MichaelHashSet< gc_type, list_type > set_type; + + // +3 - for guarded_ptr, iterators + cds::gc::hp::GarbageCollector::Construct( set_type::c_nHazardPtrCount + 3, 1, 16 ); + cds::threading::Manager::attachThread(); + } + + void TearDown() + { + cds::threading::Manager::detachThread(); + cds::gc::hp::GarbageCollector::Destruct( true ); + } + }; + + TEST_F( MichaelIterableSet_HP, compare ) + { + typedef cc::IterableList< gc_type, int_item, + typename cc::iterable_list::make_traits< + cds::opt::compare< cmp > + >::type + > list_type; + + typedef cc::MichaelHashSet< gc_type, list_type, + typename cc::michael_set::make_traits< + cds::opt::hash< hash_int > + >::type + > set_type; + + set_type s( kSize, 2 ); + test( s ); + } + + TEST_F( MichaelIterableSet_HP, less ) + { + typedef cc::IterableList< gc_type, int_item, + typename cc::iterable_list::make_traits< + cds::opt::less< base_class::less > + >::type + > list_type; + + typedef cc::MichaelHashSet< gc_type, list_type, + typename cc::michael_set::make_traits< + cds::opt::hash< hash_int > + >::type + > set_type; + + set_type s( kSize, 2 ); + test( s ); + } + + TEST_F( MichaelIterableSet_HP, cmpmix ) + { + struct list_traits : public cc::iterable_list::traits + { + typedef base_class::less less; + typedef cmp compare; + }; + typedef cc::IterableList< gc_type, int_item, list_traits > list_type; + + typedef cc::MichaelHashSet< gc_type, list_type, + typename cc::michael_set::make_traits< + cds::opt::hash< hash_int > + >::type + > set_type; + + set_type s( kSize, 2 ); + test( s ); + } + + TEST_F( MichaelIterableSet_HP, item_counting ) + { + struct list_traits : public cc::iterable_list::traits + { + typedef cmp compare; + }; + typedef cc::IterableList< gc_type, int_item, list_traits > list_type; + + struct set_traits: public cc::michael_set::traits + { + typedef hash_int hash; + typedef simple_item_counter item_counter; + }; + typedef cc::MichaelHashSet< gc_type, list_type, set_traits > set_type; + + set_type s( kSize, 3 ); + test( s ); + } + + TEST_F( MichaelIterableSet_HP, backoff ) + { + struct list_traits : public cc::iterable_list::traits + { + typedef cmp compare; + typedef cds::backoff::exponential back_off; + }; + typedef cc::IterableList< gc_type, int_item, list_traits > list_type; + + struct set_traits : public cc::michael_set::traits + { + typedef hash_int hash; + typedef cds::atomicity::item_counter item_counter; + }; + typedef cc::MichaelHashSet< gc_type, list_type, set_traits > set_type; + + set_type s( kSize, 4 ); + test( s ); + } + + TEST_F( MichaelIterableSet_HP, seq_cst ) + { + struct list_traits : public cc::iterable_list::traits + { + typedef base_class::less less; + typedef cds::backoff::pause back_off; + typedef cds::opt::v::sequential_consistent memory_model; + }; + typedef cc::IterableList< gc_type, int_item, list_traits > list_type; + + struct set_traits : public cc::michael_set::traits + { + typedef hash_int hash; + typedef cds::atomicity::item_counter item_counter; + }; + typedef cc::MichaelHashSet< gc_type, list_type, set_traits > set_type; + + set_type s( kSize, 4 ); + test( s ); + } + + TEST_F( MichaelIterableSet_HP, stat ) + { + struct list_traits: public cc::iterable_list::traits + { + typedef base_class::less less; + typedef cds::backoff::pause back_off; + typedef cc::iterable_list::stat<> stat; + }; + typedef cc::IterableList< gc_type, int_item, list_traits > list_type; + + struct set_traits: public cc::michael_set::traits + { + typedef hash_int hash; + typedef cds::atomicity::item_counter item_counter; + }; + typedef cc::MichaelHashSet< gc_type, list_type, set_traits > set_type; + + set_type s( kSize, 4 ); + test( s ); + } + + TEST_F( MichaelIterableSet_HP, wrapped_stat ) + { + struct list_traits: public cc::iterable_list::traits + { + typedef base_class::less less; + typedef cds::backoff::pause back_off; + typedef cc::iterable_list::wrapped_stat<> stat; + }; + typedef cc::IterableList< gc_type, int_item, list_traits > list_type; + + struct set_traits: public cc::michael_set::traits + { + typedef hash_int hash; + typedef cds::atomicity::item_counter item_counter; + }; + typedef cc::MichaelHashSet< gc_type, list_type, set_traits > set_type; + + set_type s( kSize, 4 ); + test( s ); + } + +} // namespace diff --git a/test/unit/set/michael_lazy_dhp.cpp b/test/unit/set/michael_lazy_dhp.cpp index 1ec2a93d..be57e996 100644 --- a/test/unit/set/michael_lazy_dhp.cpp +++ b/test/unit/set/michael_lazy_dhp.cpp @@ -25,7 +25,7 @@ SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE - OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. */ #include "test_set_hp.h" @@ -194,4 +194,46 @@ namespace { test( s ); } + TEST_F( MichaelLazySet_DHP, stat ) + { + struct list_traits: public cc::lazy_list::traits + { + typedef base_class::less less; + typedef cds::backoff::pause back_off; + typedef cc::lazy_list::stat<> stat; + }; + typedef cc::LazyList< gc_type, int_item, list_traits > list_type; + + struct set_traits: public cc::michael_set::traits + { + typedef hash_int hash; + typedef cds::atomicity::item_counter item_counter; + }; + typedef cc::MichaelHashSet< gc_type, list_type, set_traits >set_type; + + set_type s( kSize, 4 ); + test( s ); + } + + TEST_F( MichaelLazySet_DHP, wrapped_stat ) + { + struct list_traits: public cc::lazy_list::traits + { + typedef base_class::less less; + typedef cds::backoff::pause back_off; + typedef cc::lazy_list::wrapped_stat<> stat; + }; + typedef cc::LazyList< gc_type, int_item, list_traits > list_type; + + struct set_traits: public cc::michael_set::traits + { + typedef hash_int hash; + typedef cds::atomicity::item_counter item_counter; + }; + typedef cc::MichaelHashSet< gc_type, list_type, set_traits >set_type; + + set_type s( kSize, 4 ); + test( s ); + } + } // namespace diff --git a/test/unit/set/michael_lazy_hp.cpp b/test/unit/set/michael_lazy_hp.cpp index af163397..8e3cee2a 100644 --- a/test/unit/set/michael_lazy_hp.cpp +++ b/test/unit/set/michael_lazy_hp.cpp @@ -25,7 +25,7 @@ SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE - OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. */ #include "test_set_hp.h" @@ -195,4 +195,46 @@ namespace { test( s ); } + TEST_F( MichaelLazySet_HP, stat ) + { + struct list_traits: public cc::lazy_list::traits + { + typedef base_class::less less; + typedef cds::backoff::pause back_off; + typedef cc::lazy_list::stat<> stat; + }; + typedef cc::LazyList< gc_type, int_item, list_traits > list_type; + + struct set_traits: public cc::michael_set::traits + { + typedef hash_int hash; + typedef cds::atomicity::item_counter item_counter; + }; + typedef cc::MichaelHashSet< gc_type, list_type, set_traits >set_type; + + set_type s( kSize, 4 ); + test( s ); + } + + TEST_F( MichaelLazySet_HP, wrapped_stat ) + { + struct list_traits: public cc::lazy_list::traits + { + typedef base_class::less less; + typedef cds::backoff::pause back_off; + typedef cc::lazy_list::wrapped_stat<> stat; + }; + typedef cc::LazyList< gc_type, int_item, list_traits > list_type; + + struct set_traits: public cc::michael_set::traits + { + typedef hash_int hash; + typedef cds::atomicity::item_counter item_counter; + }; + typedef cc::MichaelHashSet< gc_type, list_type, set_traits >set_type; + + set_type s( kSize, 4 ); + test( s ); + } + } // namespace diff --git a/test/unit/set/michael_lazy_nogc.cpp b/test/unit/set/michael_lazy_nogc.cpp index 0a7751ce..76b9cb18 100644 --- a/test/unit/set/michael_lazy_nogc.cpp +++ b/test/unit/set/michael_lazy_nogc.cpp @@ -25,7 +25,7 @@ SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE - OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. */ #include "test_set_nogc.h" @@ -185,4 +185,46 @@ namespace { test( s ); } + TEST_F( MichaelLazySet_NoGC, stat ) + { + struct list_traits: public cc::lazy_list::traits + { + typedef base_class::less less; + typedef cds::backoff::pause back_off; + typedef cc::lazy_list::stat<> stat; + }; + typedef cc::LazyList< gc_type, int_item, list_traits > list_type; + + struct set_traits: public cc::michael_set::traits + { + typedef hash_int hash; + typedef cds::atomicity::item_counter item_counter; + }; + typedef cc::MichaelHashSet< gc_type, list_type, set_traits >set_type; + + set_type s( kSize, 4 ); + test( s ); + } + + TEST_F( MichaelLazySet_NoGC, wrapped_stat ) + { + struct list_traits: public cc::lazy_list::traits + { + typedef base_class::less less; + typedef cds::backoff::pause back_off; + typedef cc::lazy_list::wrapped_stat<> stat; + }; + typedef cc::LazyList< gc_type, int_item, list_traits > list_type; + + struct set_traits: public cc::michael_set::traits + { + typedef hash_int hash; + typedef cds::atomicity::item_counter item_counter; + }; + typedef cc::MichaelHashSet< gc_type, list_type, set_traits >set_type; + + set_type s( kSize, 4 ); + test( s ); + } + } // namespace diff --git a/test/unit/set/michael_michael_dhp.cpp b/test/unit/set/michael_michael_dhp.cpp index 73f8b1f6..046e0c21 100644 --- a/test/unit/set/michael_michael_dhp.cpp +++ b/test/unit/set/michael_michael_dhp.cpp @@ -25,7 +25,7 @@ SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE - OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. */ #include "test_set_hp.h" @@ -173,4 +173,46 @@ namespace { test( s ); } + TEST_F( MichaelSet_DHP, stat ) + { + struct list_traits: public cc::michael_list::traits + { + typedef base_class::less less; + typedef cds::backoff::pause back_off; + typedef cc::michael_list::stat<> stat; + }; + typedef cc::MichaelList< gc_type, int_item, list_traits > list_type; + + struct set_traits: public cc::michael_set::traits + { + typedef hash_int hash; + typedef cds::atomicity::item_counter item_counter; + }; + typedef cc::MichaelHashSet< gc_type, list_type, set_traits >set_type; + + set_type s( kSize, 4 ); + test( s ); + } + + TEST_F( MichaelSet_DHP, wrapped_stat ) + { + struct list_traits: public cc::michael_list::traits + { + typedef base_class::less less; + typedef cds::backoff::pause back_off; + typedef cc::michael_list::wrapped_stat<> stat; + }; + typedef cc::MichaelList< gc_type, int_item, list_traits > list_type; + + struct set_traits: public cc::michael_set::traits + { + typedef hash_int hash; + typedef cds::atomicity::item_counter item_counter; + }; + typedef cc::MichaelHashSet< gc_type, list_type, set_traits >set_type; + + set_type s( kSize, 4 ); + test( s ); + } + } // namespace diff --git a/test/unit/set/michael_michael_hp.cpp b/test/unit/set/michael_michael_hp.cpp index 29107d44..dc85ec73 100644 --- a/test/unit/set/michael_michael_hp.cpp +++ b/test/unit/set/michael_michael_hp.cpp @@ -25,7 +25,7 @@ SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE - OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. */ #include "test_set_hp.h" @@ -174,4 +174,46 @@ namespace { test( s ); } + TEST_F( MichaelSet_HP, stat ) + { + struct list_traits: public cc::michael_list::traits + { + typedef base_class::less less; + typedef cds::backoff::pause back_off; + typedef cc::michael_list::stat<> stat; + }; + typedef cc::MichaelList< gc_type, int_item, list_traits > list_type; + + struct set_traits: public cc::michael_set::traits + { + typedef hash_int hash; + typedef cds::atomicity::item_counter item_counter; + }; + typedef cc::MichaelHashSet< gc_type, list_type, set_traits > set_type; + + set_type s( kSize, 4 ); + test( s ); + } + + TEST_F( MichaelSet_HP, wrapped_stat ) + { + struct list_traits: public cc::michael_list::traits + { + typedef base_class::less less; + typedef cds::backoff::pause back_off; + typedef cc::michael_list::wrapped_stat<> stat; + }; + typedef cc::MichaelList< gc_type, int_item, list_traits > list_type; + + struct set_traits: public cc::michael_set::traits + { + typedef hash_int hash; + typedef cds::atomicity::item_counter item_counter; + }; + typedef cc::MichaelHashSet< gc_type, list_type, set_traits > set_type; + + set_type s( kSize, 4 ); + test( s ); + } + } // namespace diff --git a/test/unit/set/michael_michael_nogc.cpp b/test/unit/set/michael_michael_nogc.cpp index 0f493ff0..5dda78bb 100644 --- a/test/unit/set/michael_michael_nogc.cpp +++ b/test/unit/set/michael_michael_nogc.cpp @@ -25,7 +25,7 @@ SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE - OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. */ #include "test_set_nogc.h" @@ -164,4 +164,46 @@ namespace { test( s ); } + TEST_F( MichaelSet_NoGC, stat ) + { + struct list_traits: public cc::michael_list::traits + { + typedef base_class::less less; + typedef cds::backoff::pause back_off; + typedef cc::michael_list::stat<> stat; + }; + typedef cc::MichaelList< gc_type, int_item, list_traits > list_type; + + struct set_traits: public cc::michael_set::traits + { + typedef hash_int hash; + typedef cds::atomicity::item_counter item_counter; + }; + typedef cc::MichaelHashSet< gc_type, list_type, set_traits >set_type; + + set_type s( kSize, 4 ); + test( s ); + } + + TEST_F( MichaelSet_NoGC, wrapped_stat ) + { + struct list_traits: public cc::michael_list::traits + { + typedef base_class::less less; + typedef cds::backoff::pause back_off; + typedef cc::michael_list::wrapped_stat<> stat; + }; + typedef cc::MichaelList< gc_type, int_item, list_traits > list_type; + + struct set_traits: public cc::michael_set::traits + { + typedef hash_int hash; + typedef cds::atomicity::item_counter item_counter; + }; + typedef cc::MichaelHashSet< gc_type, list_type, set_traits >set_type; + + set_type s( kSize, 4 ); + test( s ); + } + } // namespace diff --git a/test/unit/set/test_michael_iterable.h b/test/unit/set/test_michael_iterable.h new file mode 100644 index 00000000..9742a1cb --- /dev/null +++ b/test/unit/set/test_michael_iterable.h @@ -0,0 +1,379 @@ +/* + This file is a part of libcds - Concurrent Data Structures library + + (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016 + + Source code repo: http://github.com/khizmax/libcds/ + Download: http://sourceforge.net/projects/libcds/files/ + + Redistribution and use in source and binary forms, with or without + modification, are permitted provided that the following conditions are met: + + * Redistributions of source code must retain the above copyright notice, this + list of conditions and the following disclaimer. + + * Redistributions in binary form must reproduce the above copyright notice, + this list of conditions and the following disclaimer in the documentation + and/or other materials provided with the distribution. + + THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" + AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE + FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR + SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER + CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, + OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. +*/ + +#ifndef CDSUNIT_SET_TEST_MICHAEL_ITERABLE_H +#define CDSUNIT_SET_TEST_MICHAEL_ITERABLE_H + +#include "test_set_data.h" + +namespace cds_test { + + class michael_iterable_set: public container_set_data + { + protected: + template + void test( Set& s ) + { + // Precondition: set is empty + // Postcondition: set is empty + + EXPECT_TRUE( s.empty() ); + EXPECT_CONTAINER_SIZE( s, 0 ); + size_t const nSetSize = kSize; + + typedef typename Set::value_type value_type; + + std::vector< value_type > data; + std::vector< size_t> indices; + data.reserve( kSize ); + indices.reserve( kSize ); + for ( size_t key = 0; key < kSize; ++key ) { + data.push_back( value_type( static_cast(key) ) ); + indices.push_back( key ); + } + shuffle( indices.begin(), indices.end() ); + + // insert/find + for ( auto idx : indices ) { + auto& i = data[idx]; + + EXPECT_FALSE( s.contains( i.nKey ) ); + EXPECT_FALSE( s.contains( i ) ); + EXPECT_FALSE( s.contains( other_item( i.key() ), other_less())); + EXPECT_FALSE( s.find( i.nKey, []( value_type&, int ) {} )); + EXPECT_FALSE( s.find( i, []( value_type&, value_type const& ) {} )); + EXPECT_FALSE( s.find_with( other_item( i.key()), other_less(), []( value_type&, other_item const& ) {} )); + EXPECT_TRUE( s.find( i ) == s.end()); + EXPECT_TRUE( s.find( i.nKey ) == s.end() ); + EXPECT_TRUE( s.find_with( other_item( i.key()), other_less()) == s.end() ); + + std::pair updResult; + + std::string str; + updResult = s.update( i.key(), []( value_type&, value_type* old ) + { + EXPECT_TRUE( old == nullptr ); + }, false ); + EXPECT_FALSE( updResult.first ); + EXPECT_FALSE( updResult.second ); + + switch ( idx % 11 ) { + case 0: + EXPECT_TRUE( s.insert( i )); + EXPECT_FALSE( s.insert( i )); + updResult = s.update( i, []( value_type& val, value_type* old) + { + ASSERT_FALSE( old == nullptr ); + EXPECT_EQ( val.key(), old->key() ); + }, false ); + EXPECT_TRUE( updResult.first ); + EXPECT_FALSE( updResult.second ); + break; + case 1: + EXPECT_TRUE( s.insert( i.key() )); + EXPECT_FALSE( s.insert( i.key() )); + updResult = s.update( i.key(), []( value_type& val, value_type* old) + { + ASSERT_FALSE( old == nullptr ); + EXPECT_EQ( val.key(), old->key() ); + }, false ); + EXPECT_TRUE( updResult.first ); + EXPECT_FALSE( updResult.second ); + break; + case 2: + EXPECT_TRUE( s.insert( i, []( value_type& v ) { ++v.nFindCount; } )); + EXPECT_FALSE( s.insert( i, []( value_type& v ) { ++v.nFindCount; } )); + EXPECT_TRUE( s.find( i.nKey, []( value_type const& v, int key ) + { + EXPECT_EQ( v.key(), key ); + EXPECT_EQ( v.nFindCount, 1 ); + })); + break; + case 3: + EXPECT_TRUE( s.insert( i.key(), []( value_type& v ) { ++v.nFindCount; } )); + EXPECT_FALSE( s.insert( i.key(), []( value_type& v ) { ++v.nFindCount; } )); + EXPECT_TRUE( s.find( i.nKey, []( value_type const& v, int key ) + { + EXPECT_EQ( v.key(), key ); + EXPECT_EQ( v.nFindCount, 1 ); + })); + break; + case 4: + updResult = s.update( i, [&i]( value_type& v, value_type* old ) + { + EXPECT_TRUE( old == nullptr ); + EXPECT_EQ( v.key(), i.key() ); + ++v.nUpdateNewCount; + }); + EXPECT_TRUE( updResult.first ); + EXPECT_TRUE( updResult.second ); + + updResult = s.update( i, []( value_type& v, value_type* old ) + { + ASSERT_FALSE( old == nullptr ); + EXPECT_EQ( v.key(), old->key() ); + EXPECT_EQ( old->nUpdateNewCount, 1 ); + v.nUpdateNewCount = old->nUpdateNewCount; + ++v.nUpdateCount; + }, false ); + EXPECT_TRUE( updResult.first ); + EXPECT_FALSE( updResult.second ); + + EXPECT_TRUE( s.find( i.nKey, []( value_type const& v, int key ) + { + EXPECT_EQ( v.key(), key ); + EXPECT_EQ( v.nUpdateNewCount, 1 ); + EXPECT_EQ( v.nUpdateCount, 1 ); + })); + break; + case 5: + updResult = s.update( i.key(), [&i]( value_type& v, value_type* old ) + { + EXPECT_TRUE( old == nullptr ); + EXPECT_EQ( v.key(), i.key() ); + ++v.nUpdateNewCount; + }); + EXPECT_TRUE( updResult.first ); + EXPECT_TRUE( updResult.second ); + + updResult = s.update( i.key(), []( value_type& v, value_type* old ) + { + EXPECT_FALSE( old == nullptr ); + EXPECT_EQ( v.key(), old->key() ); + EXPECT_EQ( old->nUpdateNewCount, 1 ); + v.nUpdateNewCount = old->nUpdateNewCount; + ++v.nUpdateCount; + }, false ); + EXPECT_TRUE( updResult.first ); + EXPECT_FALSE( updResult.second ); + + EXPECT_TRUE( s.find( i, []( value_type const& v, value_type const& arg ) + { + EXPECT_EQ( v.key(), arg.key() ); + EXPECT_EQ( v.nUpdateNewCount, 1 ); + EXPECT_EQ( v.nUpdateCount, 1 ); + })); + break; + case 6: + EXPECT_TRUE( s.emplace( i.key())); + EXPECT_TRUE( s.find( i, []( value_type const& v, value_type const& arg ) + { + EXPECT_EQ( v.key(), arg.key() ); + EXPECT_EQ( v.nVal, arg.nVal ); + })); + break; + case 7: + str = "Hello!"; + EXPECT_TRUE( s.emplace( i.key(), std::move( str ))); + EXPECT_TRUE( str.empty()); + EXPECT_TRUE( s.find( i, []( value_type const& v, value_type const& arg ) + { + EXPECT_EQ( v.key(), arg.key() ); + EXPECT_EQ( v.nVal, arg.nVal ); + EXPECT_EQ( v.strVal, std::string( "Hello!" )); + } )); + break; + case 8: + str = "Hello!"; + EXPECT_TRUE( s.insert( value_type( i.key(), std::move( str ))) ); + EXPECT_TRUE( str.empty() ); + EXPECT_TRUE( s.find( i, []( value_type const& v, value_type const& arg ) + { + EXPECT_EQ( v.key(), arg.key() ); + EXPECT_EQ( v.nVal, arg.nVal ); + EXPECT_EQ( v.strVal, std::string( "Hello!" ) ); + } ) ); + break; + case 9: + updResult = s.upsert( i.key(), false ); + EXPECT_FALSE( updResult.first ); + EXPECT_FALSE( updResult.second ); + + updResult = s.upsert( i.key()); + EXPECT_TRUE( updResult.first ); + EXPECT_TRUE( updResult.second ); + + updResult = s.upsert( i.key(), false ); + EXPECT_TRUE( updResult.first ); + EXPECT_FALSE( updResult.second ); + + EXPECT_TRUE( s.find( i, []( value_type const& v, value_type const& arg ) + { + EXPECT_EQ( v.key(), arg.key() ); + } ) ); + break; + case 10: + updResult = s.upsert( i, false ); + EXPECT_FALSE( updResult.first ); + EXPECT_FALSE( updResult.second ); + + updResult = s.upsert( i ); + EXPECT_TRUE( updResult.first ); + EXPECT_TRUE( updResult.second ); + + updResult = s.upsert( i, false ); + EXPECT_TRUE( updResult.first ); + EXPECT_FALSE( updResult.second ); + + EXPECT_TRUE( s.find( i, []( value_type const& v, value_type const& arg ) + { + EXPECT_EQ( v.key(), arg.key() ); + } ) ); + break; + default: + // forgot anything?.. + EXPECT_TRUE( false ); + } + + EXPECT_TRUE( s.contains( i.nKey ) ); + EXPECT_TRUE( s.contains( i ) ); + EXPECT_TRUE( s.contains( other_item( i.key() ), other_less() ) ); + EXPECT_TRUE( s.find( i.nKey, []( value_type&, int ) {} ) ); + EXPECT_TRUE( s.find( i, []( value_type&, value_type const& ) {} ) ); + EXPECT_TRUE( s.find_with( other_item( i.key() ), other_less(), []( value_type&, other_item const& ) {} ) ); + EXPECT_FALSE( s.find( i.nKey ) == s.end()); + EXPECT_FALSE( s.find( i ) == s.end() ); + EXPECT_FALSE( s.find_with( other_item( i.key() ), other_less()) == s.end() ); + } + + EXPECT_FALSE( s.empty() ); + EXPECT_CONTAINER_SIZE( s, nSetSize ); + + // erase + shuffle( indices.begin(), indices.end() ); + for ( auto idx : indices ) { + auto& i = data[idx]; + + EXPECT_TRUE( s.contains( i.nKey ) ); + EXPECT_TRUE( s.contains( i ) ); + EXPECT_TRUE( s.contains( other_item( i.key() ), other_less() ) ); + EXPECT_TRUE( s.find( i.nKey, []( value_type& v, int ) + { + v.nFindCount = 1; + })); + EXPECT_TRUE( s.find( i, []( value_type& v, value_type const& ) + { + EXPECT_EQ( ++v.nFindCount, 2 ); + })); + EXPECT_TRUE( s.find_with( other_item( i.key() ), other_less(), []( value_type& v, other_item const& ) + { + EXPECT_EQ( ++v.nFindCount, 3 ); + })); + + int nKey = i.key() - 1; + switch ( idx % 6 ) { + case 0: + EXPECT_TRUE( s.erase( i.key())); + EXPECT_FALSE( s.erase( i.key())); + break; + case 1: + EXPECT_TRUE( s.erase( i )); + EXPECT_FALSE( s.erase( i )); + break; + case 2: + EXPECT_TRUE( s.erase_with( other_item( i.key()), other_less())); + EXPECT_FALSE( s.erase_with( other_item( i.key() ), other_less() ) ); + break; + case 3: + EXPECT_TRUE( s.erase( i.key(), [&nKey]( value_type const& v ) + { + nKey = v.key(); + } )); + EXPECT_EQ( i.key(), nKey ); + + nKey = i.key() - 1; + EXPECT_FALSE( s.erase( i.key(), [&nKey]( value_type const& v ) + { + nKey = v.key(); + } )); + EXPECT_EQ( i.key(), nKey + 1 ); + break; + case 4: + EXPECT_TRUE( s.erase( i, [&nKey]( value_type const& v ) + { + nKey = v.key(); + } )); + EXPECT_EQ( i.key(), nKey ); + + nKey = i.key() - 1; + EXPECT_FALSE( s.erase( i, [&nKey]( value_type const& v ) + { + nKey = v.key(); + } )); + EXPECT_EQ( i.key(), nKey + 1 ); + break; + case 5: + EXPECT_TRUE( s.erase_with( other_item( i.key()), other_less(), [&nKey]( value_type const& v ) + { + nKey = v.key(); + } )); + EXPECT_EQ( i.key(), nKey ); + + nKey = i.key() - 1; + EXPECT_FALSE( s.erase_with( other_item( i.key()), other_less(), [&nKey]( value_type const& v ) + { + nKey = v.key(); + } )); + EXPECT_EQ( i.key(), nKey + 1 ); + break; + } + + EXPECT_FALSE( s.contains( i.nKey ) ); + EXPECT_FALSE( s.contains( i ) ); + EXPECT_FALSE( s.contains( other_item( i.key() ), other_less())); + EXPECT_FALSE( s.find( i.nKey, []( value_type&, int ) {} )); + EXPECT_FALSE( s.find( i, []( value_type&, value_type const& ) {} )); + EXPECT_FALSE( s.find_with( other_item( i.key()), other_less(), []( value_type&, other_item const& ) {} )); + } + EXPECT_TRUE( s.empty() ); + EXPECT_CONTAINER_SIZE( s, 0 ); + + + // clear + for ( auto& i : data ) { + EXPECT_TRUE( s.insert( i ) ); + } + + EXPECT_FALSE( s.empty() ); + EXPECT_CONTAINER_SIZE( s, nSetSize ); + + s.clear(); + + EXPECT_TRUE( s.empty() ); + EXPECT_CONTAINER_SIZE( s, 0 ); + + EXPECT_TRUE( s.begin() == s.end() ); + EXPECT_TRUE( s.cbegin() == s.cend() ); + } + }; + +} // namespace cds_test + +#endif // CDSUNIT_SET_TEST_MICHAEL_ITERABLE_H diff --git a/test/unit/set/test_michael_iterable_hp.h b/test/unit/set/test_michael_iterable_hp.h new file mode 100644 index 00000000..1a867678 --- /dev/null +++ b/test/unit/set/test_michael_iterable_hp.h @@ -0,0 +1,153 @@ +/* + This file is a part of libcds - Concurrent Data Structures library + + (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016 + + Source code repo: http://github.com/khizmax/libcds/ + Download: http://sourceforge.net/projects/libcds/files/ + + Redistribution and use in source and binary forms, with or without + modification, are permitted provided that the following conditions are met: + + * Redistributions of source code must retain the above copyright notice, this + list of conditions and the following disclaimer. + + * Redistributions in binary form must reproduce the above copyright notice, + this list of conditions and the following disclaimer in the documentation + and/or other materials provided with the distribution. + + THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" + AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE + FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR + SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER + CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, + OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. +*/ + +#ifndef CDSUNIT_SET_TEST_SET_HP_H +#define CDSUNIT_SET_TEST_SET_HP_H + +#include "test_michael_iterable.h" + +namespace cds_test { + + class michael_iterable_set_hp: public michael_iterable_set + { + typedef michael_iterable_set base_class; + + protected: + template + void test( Set& s ) + { + // Precondition: set is empty + // Postcondition: set is empty + + EXPECT_TRUE( s.empty() ); + EXPECT_CONTAINER_SIZE( s, 0 ); + + base_class::test( s ); + + typedef typename Set::value_type value_type; + + size_t const nSetSize = kSize; + std::vector< value_type > data; + std::vector< size_t> indices; + data.reserve( kSize ); + indices.reserve( kSize ); + for ( size_t key = 0; key < kSize; ++key ) { + data.push_back( value_type( static_cast(key) ) ); + indices.push_back( key ); + } + shuffle( indices.begin(), indices.end() ); + + for ( auto& i : data ) { + EXPECT_TRUE( s.insert( i ) ); + } + EXPECT_FALSE( s.empty() ); + EXPECT_CONTAINER_SIZE( s, nSetSize ); + + // iterator test + for ( auto it = s.begin(); it != s.end(); ++it ) { + it->nFindCount = it->key() * 3; + } + + for ( auto it = s.cbegin(); it != s.cend(); ++it ) { + EXPECT_EQ( it->nFindCount, it->key() * 3 ); + } + + typedef typename Set::guarded_ptr guarded_ptr; + guarded_ptr gp; + + // get() + for ( auto idx : indices ) { + auto& i = data[idx]; + + EXPECT_TRUE( !gp ); + switch ( idx % 3 ) { + case 0: + gp = s.get( i.key() ); + ASSERT_FALSE( !gp ); + break; + case 1: + gp = s.get( i ); + ASSERT_FALSE( !gp ); + break; + case 2: + gp = s.get_with( other_item( i.key() ), other_less() ); + ASSERT_FALSE( !gp ); + } + EXPECT_EQ( gp->key(), i.key() ); + EXPECT_EQ( gp->nFindCount, i.key() * 3 ); + gp->nFindCount *= 2; + + gp.release(); + } + + // extract() + for ( auto idx : indices ) { + auto& i = data[idx]; + + EXPECT_TRUE( !gp ); + switch ( idx % 3 ) { + case 0: + gp = s.extract( i.key() ); + ASSERT_FALSE( !gp ); + break; + case 1: + gp = s.extract( i ); + ASSERT_FALSE( !gp ); + break; + case 2: + gp = s.extract_with( other_item( i.key() ), other_less() ); + ASSERT_FALSE( !gp ); + break; + } + EXPECT_EQ( gp->key(), i.key() ); + EXPECT_EQ( gp->nFindCount, i.key() * 6 ); + + switch ( idx % 3 ) { + case 0: + gp = s.extract( i.key() ); + break; + case 1: + gp = s.extract( i ); + break; + case 2: + gp = s.extract_with( other_item( i.key() ), other_less() ); + break; + } + EXPECT_TRUE( !gp ); + } + + EXPECT_TRUE( s.empty() ); + EXPECT_CONTAINER_SIZE( s, 0 ); + } + + }; +} // namespace cds_test + +#endif // CDSUNIT_SET_TEST_SET_HP_H diff --git a/test/unit/set/test_set.h b/test/unit/set/test_set.h index d3a7a908..fd3957a7 100644 --- a/test/unit/set/test_set.h +++ b/test/unit/set/test_set.h @@ -31,199 +31,14 @@ #ifndef CDSUNIT_SET_TEST_SET_H #define CDSUNIT_SET_TEST_SET_H -#include -#include +#include "test_set_data.h" #include -#include // ref - -// forward declaration -namespace cds { namespace container {}} namespace cds_test { - namespace co = cds::opt; - class container_set : public fixture + class container_set : public container_set_data { - public: - static size_t const kSize = 1000; - - struct stat - { - unsigned int nFindCount; - unsigned int nUpdateNewCount; - unsigned int nUpdateCount; - mutable unsigned int nEraseCount; - - stat() - { - clear_stat(); - } - - void clear_stat() - { - memset( this, 0, sizeof( *this ) ); - } - }; - - struct other_item { - int nKey; - - explicit other_item( int k ) - : nKey( k ) - {} - - int key() const - { - return nKey; - } - }; - - struct int_item: public stat - { - int nKey; - int nVal; - std::string strVal; - - int_item() - : nKey( 0 ) - , nVal( 0 ) - {} - - explicit int_item( int k ) - : nKey( k ) - , nVal( k * 2 ) - {} - - template - explicit int_item( Q const& src ) - : nKey( src.key() ) - , nVal( 0 ) - {} - - int_item( int_item const& src ) - : nKey( src.nKey ) - , nVal( src.nVal ) - , strVal( src.strVal ) - {} - - int_item( int_item&& src ) - : nKey( src.nKey ) - , nVal( src.nVal ) - , strVal( std::move( src.strVal ) ) - {} - - int_item( int k, std::string&& s ) - : nKey( k ) - , nVal( k * 2 ) - , strVal( std::move( s ) ) - {} - - explicit int_item( other_item const& s ) - : nKey( s.key() ) - , nVal( s.key() * 2 ) - {} - - int key() const - { - return nKey; - } - }; - - struct hash_int { - size_t operator()( int i ) const - { - return co::v::hash()(i); - } - template - size_t operator()( const Item& i ) const - { - return (*this)(i.key()); - } - }; - - struct simple_item_counter { - size_t m_nCount; - - simple_item_counter() - : m_nCount( 0 ) - {} - - size_t operator ++() - { - return ++m_nCount; - } - - size_t operator --() - { - return --m_nCount; - } - - void reset() - { - m_nCount = 0; - } - - operator size_t() const - { - return m_nCount; - } - - }; - - struct less - { - bool operator ()( int_item const& v1, int_item const& v2 ) const - { - return v1.key() < v2.key(); - } - - template - bool operator ()( int_item const& v1, const Q& v2 ) const - { - return v1.key() < v2; - } - - template - bool operator ()( const Q& v1, int_item const& v2 ) const - { - return v1 < v2.key(); - } - }; - - struct cmp { - int operator ()( int_item const& v1, int_item const& v2 ) const - { - if ( v1.key() < v2.key() ) - return -1; - return v1.key() > v2.key() ? 1 : 0; - } - - template - int operator ()( T const& v1, int v2 ) const - { - if ( v1.key() < v2 ) - return -1; - return v1.key() > v2 ? 1 : 0; - } - - template - int operator ()( int v1, T const& v2 ) const - { - if ( v1 < v2.key() ) - return -1; - return v1 > v2.key() ? 1 : 0; - } - }; - - struct other_less { - template - bool operator()( Q const& lhs, T const& rhs ) const - { - return lhs.key() < rhs.key(); - } - }; - protected: template void test( Set& s ) diff --git a/test/unit/set/test_set_data.h b/test/unit/set/test_set_data.h new file mode 100644 index 00000000..2242fdf6 --- /dev/null +++ b/test/unit/set/test_set_data.h @@ -0,0 +1,229 @@ +/* + This file is a part of libcds - Concurrent Data Structures library + + (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016 + + Source code repo: http://github.com/khizmax/libcds/ + Download: http://sourceforge.net/projects/libcds/files/ + + Redistribution and use in source and binary forms, with or without + modification, are permitted provided that the following conditions are met: + + * Redistributions of source code must retain the above copyright notice, this + list of conditions and the following disclaimer. + + * Redistributions in binary form must reproduce the above copyright notice, + this list of conditions and the following disclaimer in the documentation + and/or other materials provided with the distribution. + + THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" + AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE + FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR + SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER + CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, + OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. +*/ + +#ifndef CDSUNIT_SET_TEST_SET_DATA_H +#define CDSUNIT_SET_TEST_SET_DATA_H + +#include +#include + +#include + +// forward declaration +namespace cds { namespace container {}} + +namespace cds_test { + namespace co = cds::opt; + + class container_set_data : public fixture + { + public: + static size_t const kSize = 1000; + + struct stat + { + unsigned int nFindCount; + unsigned int nUpdateNewCount; + unsigned int nUpdateCount; + mutable unsigned int nEraseCount; + + stat() + { + clear_stat(); + } + + void clear_stat() + { + memset( this, 0, sizeof( *this ) ); + } + }; + + struct other_item { + int nKey; + + explicit other_item( int k ) + : nKey( k ) + {} + + int key() const + { + return nKey; + } + }; + + struct int_item: public stat + { + int nKey; + int nVal; + std::string strVal; + + int_item() + : nKey( 0 ) + , nVal( 0 ) + {} + + explicit int_item( int k ) + : nKey( k ) + , nVal( k * 2 ) + {} + + template + explicit int_item( Q const& src ) + : nKey( src.key() ) + , nVal( 0 ) + {} + + int_item( int_item const& src ) + : nKey( src.nKey ) + , nVal( src.nVal ) + , strVal( src.strVal ) + {} + + int_item( int_item&& src ) + : nKey( src.nKey ) + , nVal( src.nVal ) + , strVal( std::move( src.strVal ) ) + {} + + int_item( int k, std::string&& s ) + : nKey( k ) + , nVal( k * 2 ) + , strVal( std::move( s ) ) + {} + + explicit int_item( other_item const& s ) + : nKey( s.key() ) + , nVal( s.key() * 2 ) + {} + + int key() const + { + return nKey; + } + }; + + struct hash_int { + size_t operator()( int i ) const + { + return co::v::hash()(i); + } + template + size_t operator()( const Item& i ) const + { + return (*this)(i.key()); + } + }; + + struct simple_item_counter { + size_t m_nCount; + + simple_item_counter() + : m_nCount( 0 ) + {} + + size_t operator ++() + { + return ++m_nCount; + } + + size_t operator --() + { + return --m_nCount; + } + + void reset() + { + m_nCount = 0; + } + + operator size_t() const + { + return m_nCount; + } + + }; + + struct less + { + bool operator ()( int_item const& v1, int_item const& v2 ) const + { + return v1.key() < v2.key(); + } + + template + bool operator ()( int_item const& v1, const Q& v2 ) const + { + return v1.key() < v2; + } + + template + bool operator ()( const Q& v1, int_item const& v2 ) const + { + return v1 < v2.key(); + } + }; + + struct cmp { + int operator ()( int_item const& v1, int_item const& v2 ) const + { + if ( v1.key() < v2.key() ) + return -1; + return v1.key() > v2.key() ? 1 : 0; + } + + template + int operator ()( T const& v1, int v2 ) const + { + if ( v1.key() < v2 ) + return -1; + return v1.key() > v2 ? 1 : 0; + } + + template + int operator ()( int v1, T const& v2 ) const + { + if ( v1 < v2.key() ) + return -1; + return v1 > v2.key() ? 1 : 0; + } + }; + + struct other_less { + template + bool operator()( Q const& lhs, T const& rhs ) const + { + return lhs.key() < rhs.key(); + } + }; + }; + +} // namespace cds_test + +#endif // CDSUNIT_SET_TEST_SET_DATA_H