From 686510ecc01f1c07fa168b35a5d255fb8304dab6 Mon Sep 17 00:00:00 2001 From: khizmax Date: Tue, 19 Jul 2016 23:16:48 +0300 Subject: [PATCH] Added intrusive IterableList --- cds/intrusive/details/iterable_list_base.h | 151 +++ cds/intrusive/impl/iterable_list.h | 1136 +++++++++++++++++ cds/intrusive/impl/michael_list.h | 4 +- cds/intrusive/iterable_list_dhp.h | 37 + cds/intrusive/iterable_list_hp.h | 37 + projects/Win/vc14/cds.vcxproj | 4 + projects/Win/vc14/cds.vcxproj.filters | 278 ++-- projects/Win/vc14/gtest-list.vcxproj | 4 + projects/Win/vc14/gtest-list.vcxproj.filters | 12 + test/unit/list/CMakeLists.txt | 2 + test/unit/list/intrusive_iterable_dhp.cpp | 139 ++ test/unit/list/intrusive_iterable_hp.cpp | 140 ++ test/unit/list/test_intrusive_iterable_list.h | 540 ++++++++ .../list/test_intrusive_iterable_list_hp.h | 110 ++ 14 files changed, 2459 insertions(+), 135 deletions(-) create mode 100644 cds/intrusive/details/iterable_list_base.h create mode 100644 cds/intrusive/impl/iterable_list.h create mode 100644 cds/intrusive/iterable_list_dhp.h create mode 100644 cds/intrusive/iterable_list_hp.h create mode 100644 test/unit/list/intrusive_iterable_dhp.cpp create mode 100644 test/unit/list/intrusive_iterable_hp.cpp create mode 100644 test/unit/list/test_intrusive_iterable_list.h create mode 100644 test/unit/list/test_intrusive_iterable_list_hp.h diff --git a/cds/intrusive/details/iterable_list_base.h b/cds/intrusive/details/iterable_list_base.h new file mode 100644 index 00000000..2953a791 --- /dev/null +++ b/cds/intrusive/details/iterable_list_base.h @@ -0,0 +1,151 @@ +/* + 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 CDSLIB_INTRUSIVE_DETAILS_ITERABLE_LIST_BASE_H +#define CDSLIB_INTRUSIVE_DETAILS_ITERABLE_LIST_BASE_H + +#include +#include +#include +#include +#include +#include + +namespace cds { namespace intrusive { + + /// \p IterableList ordered list related definitions + /** @ingroup cds_intrusive_helper + */ + namespace iterable_list { + + /// Node type + template + struct node + { + typedef T value_type; ///< Value type + + atomics::atomic< node* > next; ///< pointer to next node in the list + atomics::atomic< value_type* > data; ///< pointer to user data, \p nullptr if the node is free + + //@cond + node() + : next( nullptr ) + , data( nullptr ) + {} + + node( value_type * pVal ) + : next( nullptr ) + , data( pVal ) + {} + //@endcond + }; + + /// \p IterableList traits + struct traits + { + /// Key comparison functor + /** + No default functor is provided. If the option is not specified, the \p less is used. + */ + typedef opt::none compare; + + /// Specifies binary predicate used for key compare. + /** + Default is \p std::less + */ + typedef opt::none less; + + /// Node allocator + typedef CDS_DEFAULT_ALLOCATOR node_allocator; + + /// Back-off strategy + typedef cds::backoff::Default back_off; + + /// Disposer for removing items + typedef opt::v::empty_disposer disposer; + + /// Item counting feature; by default, disabled. Use \p cds::atomicity::item_counter to enable item counting + typedef atomicity::empty_item_counter item_counter; + + /// C++ memory ordering model + /** + Can be \p opt::v::relaxed_ordering (relaxed memory model, the default) + or \p opt::v::sequential_consistent (sequentially consisnent memory model). + */ + typedef opt::v::relaxed_ordering memory_model; + + /// RCU deadlock checking policy (only for \ref cds_intrusive_IterableList_rcu "RCU-based IterableList") + /** + List of available policy see \p opt::rcu_check_deadlock + */ + typedef opt::v::rcu_throw_deadlock rcu_check_deadlock; + }; + + /// Metafunction converting option list to \p iterable_list::traits + /** + Supported \p Options are: + - \p opt::compare - key comparison functor. No default functor is provided. + If the option is not specified, the \p opt::less is used. + - \p opt::less - specifies binary predicate used for key comparison. Default is \p std::less. + - \p opt::node_allocator - node allocator, default is \p std::allocator. + - \p opt::back_off - back-off strategy used. If the option is not specified, the \p cds::backoff::Default is used. + - \p opt::disposer - the functor used for disposing removed items. Default is \p opt::v::empty_disposer. Due the nature + of GC schema the disposer may be called asynchronously. + - \p opt::item_counter - the type of item counting feature. Default is disabled (\p atomicity::empty_item_counter). + To enable item counting use \p atomicity::item_counter. + - \p opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default) + or \p opt::v::sequential_consistent (sequentially consistent memory model). + - \p opt::rcu_check_deadlock - a deadlock checking policy for \ref cds_intrusive_IterableList_rcu "RCU-based IterableList" + Default is \p opt::v::rcu_throw_deadlock + */ + template + struct make_traits { +# ifdef CDS_DOXYGEN_INVOKED + typedef implementation_defined type ; ///< Metafunction result +# else + typedef typename cds::opt::make_options< + typename cds::opt::find_type_traits< traits, Options... >::type + ,Options... + >::type type; +# endif + }; + + } // namespace iterable_list + + //@cond + // Forward declaration + template < class GC, typename T, class Traits = iterable_list::traits > + class IterableList; + //@endcond + + +}} // namespace cds::intrusive + +#endif // #ifndef CDSLIB_INTRUSIVE_DETAILS_ITERABLE_LIST_BASE_H diff --git a/cds/intrusive/impl/iterable_list.h b/cds/intrusive/impl/iterable_list.h new file mode 100644 index 00000000..a1a8d1d6 --- /dev/null +++ b/cds/intrusive/impl/iterable_list.h @@ -0,0 +1,1136 @@ +/* + 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 CDSLIB_INTRUSIVE_IMPL_ITERABLE_LIST_H +#define CDSLIB_INTRUSIVE_IMPL_ITERABLE_LIST_H + +#include +#include + +namespace cds { namespace intrusive { + + /// Iterable lock-free ordered single-linked list + /** @ingroup cds_intrusive_list + \anchor cds_intrusive_IterableList_hp + + This lock-free list implementation supports thread-safe iterators. + Unlike \p cds::intrusive::MichaelList the iterable list does not require + any hook in \p T to be stored in the list. + + Usually, ordered single-linked list is used as a building block for the hash table implementation. + The complexity of searching is O(N). + + Template arguments: + - \p GC - Garbage collector used. + - \p T - type to be stored in the list. + - \p Traits - type traits, default is \p iterable_list::traits. It is possible to declare option-based + list with \p cds::intrusive::iterable_list::make_traits metafunction: + For example, the following traits-based declaration of \p gc::HP iterable list + \code + #include + // Declare item stored in your list + struct foo + { + int nKey; + // .... other data + }; + + // Declare comparator for the item + struct my_compare { + int operator()( foo const& i1, foo const& i2 ) const + { + return i1.nKey - i2.nKey; + } + }; + + // Declare traits + struct my_traits: public cds::intrusive::iterable_list::traits + { + typedef my_compare compare; + }; + + // Declare list + typedef cds::intrusive::IterableList< cds::gc::HP, foo, my_traits > list_type; + \endcode + is equivalent for the following option-based list + \code + #include + + // foo struct and my_compare are the same + + // Declare option-based list + typedef cds::intrusive::IterableList< cds::gc::HP, foo, + typename cds::intrusive::iterable_list::make_traits< + cds::intrusive::opt::compare< my_compare > // item comparator option + >::type + > option_list_type; + \endcode + + \par Usage + There are different specializations of this template for each garbage collecting schema. + You should select GC you want and include appropriate .h-file: + - for \p gc::HP: + - for \p gc::DHP: + - for \ref cds_urcu_gc "RCU type" - see \ref cds_intrusive_IterableList_rcu "RCU-based IterableList" + */ + template < + class GC + ,typename T +#ifdef CDS_DOXYGEN_INVOKED + ,class Traits = iterable_list::traits +#else + ,class Traits +#endif + > + class IterableList + { + public: + typedef T value_type; ///< type of value stored in the list + typedef Traits traits; ///< Traits template parameter + + typedef iterable_list::node< value_type > node_type; ///< node type + +# ifdef CDS_DOXYGEN_INVOKED + typedef implementation_defined key_comparator ; ///< key comparison functor based on opt::compare and opt::less option setter. +# else + typedef typename opt::details::make_comparator< value_type, traits >::type key_comparator; +# endif + + typedef typename traits::disposer disposer; ///< disposer for \p value_type + + typedef GC gc; ///< Garbage collector + typedef typename traits::back_off back_off; ///< back-off strategy + typedef typename traits::item_counter item_counter; ///< Item counting policy used + typedef typename traits::memory_model memory_model; ///< Memory ordering. See \p cds::opt::memory_model option + typedef typename traits::node_allocator node_allocator; ///< Node allocator + + typedef typename gc::template guarded_ptr< value_type > guarded_ptr; ///< Guarded pointer + + static CDS_CONSTEXPR const size_t c_nHazardPtrCount = 2; ///< 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; + }; + //@endcond + + protected: + typedef atomics::atomic< node_type* > atomic_node_ptr; ///< Atomic node pointer + typedef atomic_node_ptr auxiliary_head; ///< Auxiliary head type (for split-list support) + + atomic_node_ptr m_pHead; ///< Head pointer + item_counter m_ItemCounter; ///< Item counter + + //@cond + typedef cds::details::Allocator< node_type, node_allocator > cxx_node_allocator; + + /// Position pointer for item search + struct position { + atomic_node_ptr * pHead; ///< Previous node (pointer to pPrev->next or to m_pHead) + node_type * pPrev; ///< Previous node + node_type * pCur; ///< Current node + + value_type * pFound; ///< Value of \p pCur->data, valid only if data found + typename gc::Guard guard; ///< guard for \p pFound + }; + //@endcond + + protected: + //@cond + template + class iterator_type + { + friend class IterableList; + + protected: + node_type* m_pNode; + value_type* m_pVal; + typename gc::Guard m_Guard; // for m_pVal + + void next() + { + while ( m_pNode ) { + m_pNode = m_pNode->next.load( memory_model::memory_order_relaxed ); + if ( !m_pNode ) + break; + m_pVal = m_Guard.protect( m_pNode->data ); + if ( m_pVal ) + break; + } + } + + explicit iterator_type( atomic_node_ptr const& pNode ) + : m_pNode( pNode.load( memory_model::memory_order_relaxed )) + , m_pVal( nullptr ) + { + if ( m_pNode ) { + m_pVal = m_Guard.protect( m_pNode->data ); + if ( !m_pVal ) + next(); + } + } + + iterator_type( node_type* pNode, value_type* pVal ) + : m_pNode( pNode ) + , m_pVal( pVal ) + { + if ( m_pNode ) { + assert( pVal != nullptr ); + m_Guard.assign( pVal ); + } + } + + public: + typedef typename cds::details::make_const_type::pointer value_ptr; + typedef typename cds::details::make_const_type::reference value_ref; + + iterator_type() + : m_pNode( nullptr ) + , m_pVal( nullptr ) + {} + + iterator_type( iterator_type const& src ) + : m_pNode( src.m_pNode ) + , m_pVal( src.m_pVal ) + { + m_Guard.assign( m_pVal ); + } + + value_ptr operator ->() const + { + return m_pVal; + } + + value_ref operator *() const + { + assert( m_pVal != nullptr ); + return *m_pVal; + } + + /// Pre-increment + iterator_type& operator ++() + { + next(); + return *this; + } + + iterator_type& operator = (iterator_type const& src) + { + m_pNode = src.m_pNode; + m_pVal = src.m_pVal; + m_Guard.assign( m_pVal ); + return *this; + } + + template + bool operator ==(iterator_type const& i ) const + { + return m_pNode == i.m_pNode; + } + template + bool operator !=(iterator_type const& i ) const + { + return m_pNode != i.m_pNode; + } + }; + //@endcond + + public: + ///@name Thread-safe forward iterators + //@{ + /// Forward iterator + /** + The forward iterator for iterable list has some features: + - it has no post-increment operator + - to protect the value, the iterator contains a GC-specific guard. + 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 since it contains thread-private GC's guard. + - Iterator is thread-safe: event if the element the iterator points to is removed, the iterator stays valid because + it contains the guard keeping the value from to be recycled. + + The iterator interface: + \code + class iterator { + public: + // Default constructor + iterator(); + + // Copy construtor + iterator( iterator const& src ); + + // Dereference operator + value_type * operator ->() const; + + // Dereference operator + value_type& operator *() const; + + // Preincrement operator + iterator& operator ++(); + + // Assignment operator + iterator& operator = (iterator const& src); + + // Equality operators + bool operator ==(iterator const& i ) const; + bool operator !=(iterator const& i ) const; + }; + \endcode + + @note For two iterators pointed to the same element the value can be different; + this code + \code + if ( it1 == it2 ) + assert( &(*it1) == &(*it2) ); + \endcode + can throw assertion. The point is that the iterator stores the value of element which can be modified later by other thread. + The guard inside the iterator prevents recycling that value so the iterator's value remains valid even after such changing. + Other iterator can observe modified value of the element. + */ + typedef iterator_type iterator; + /// Const forward iterator + /** + For iterator's features and requirements see \ref iterator + */ + typedef iterator_type const_iterator; + + /// Returns a forward iterator addressing the first element in a list + /** + For empty list \code begin() == end() \endcode + */ + iterator begin() + { + return iterator( m_pHead ); + } + + /// Returns an iterator that addresses the location succeeding the last element in a list + /** + Do not use the value returned by end function to access any item. + Internally, end returning value equals to \p nullptr. + + The returned value can be used only to control reaching the end of the list. + For empty list begin() == end() + */ + iterator end() + { + return iterator(); + } + + /// Returns a forward const iterator addressing the first element in a list + const_iterator cbegin() const + { + return const_iterator( m_pHead ); + } + + /// Returns a forward const iterator addressing the first element in a list + const_iterator begin() const + { + return const_iterator( m_pHead ); + } + + /// Returns an const iterator that addresses the location succeeding the last element in a list + const_iterator end() const + { + return const_iterator(); + } + + /// Returns an const iterator that addresses the location succeeding the last element in a list + const_iterator cend() const + { + return const_iterator(); + } + //@} + + public: + /// Default constructor initializes empty list + IterableList() + : m_pHead( nullptr ) + {} + + /// Destroys the list object + ~IterableList() + { + destroy(); + } + + /// Inserts new node + /** + The function inserts \p val into the list if the list does not contain + an item with key equal to \p val. + + Returns \p true if \p val has been linked to the list, \p false otherwise. + */ + bool insert( value_type& val ) + { + return insert_at( m_pHead, val ); + } + + /// Inserts new node + /** + This function is intended for derived non-intrusive containers. + + The function allows to split new item creating into two part: + - create item with key only + - insert new item into the list + - if inserting is success, calls \p f functor to initialize value-field of \p val. + + The functor signature is: + \code + void func( value_type& val ); + \endcode + where \p val is the item inserted. User-defined functor \p f should guarantee that during changing + \p val no any other changes could be made on this list's item by concurrent threads. + The user-defined functor is called only if the inserting is success. + + @warning See \ref cds_intrusive_item_creating "insert item troubleshooting" + */ + template + bool insert( value_type& val, Func f ) + { + return insert_at( m_pHead, val, f ); + } + + /// Updates the node + /** + The operation performs inserting or changing data with lock-free manner. + + If the item \p val is not found in the list, then \p val is inserted + iff \p bInsert is \p true. + Otherwise, the current element is changed to \p val, the element will be retired later + by call \p Traits::disposer. + The functor \p func is called after inserting or replacing, it signature is: + \code + void func( value_type& val, value_type * old ); + \endcode + where + - \p val - argument \p val passed into the \p %update() function + - \p old - old value that will be retired. If new item has been inserted then \p old is \p nullptr. + + 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 list. + */ + template + std::pair update( value_type& val, Func func, bool bInsert = true ) + { + return update_at( m_pHead, val, func, bInsert ); + } + + /// Updates the node + /** + The operation performs inserting or changing data with lock-free manner. + + If the item \p val is not found in the list, then \p val is inserted + iff \p bInsert is \p true. + Otherwise, the current element is changed to \p val, the 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 list. + */ + std::pair update( value_type& val, bool bInsert = true ) + { + return update_at( m_pHead, val, []( value_type&, value_type* ) {}, bINsert ); + } + + /// Unlinks the item \p val from the list + /** + The function searches the item \p val in the list and unlinks it from the list + if it is found and it is equal to \p val. + + Difference between \p erase() and \p %unlink(): \p %erase() finds a key + and deletes the item found. \p %unlink() finds an item by key and deletes it + only if \p val is an item of the list, i.e. the pointer to item found + is equal to &val . + + \p disposer specified in \p Traits is called for deleted item. + + The function returns \p true if success and \p false otherwise. + */ + bool unlink( value_type& val ) + { + return unlink_at( m_pHead, val ); + } + + /// Deletes the item from the list + /** \anchor cds_intrusive_IterableList_hp_erase_val + The function searches an item with key equal to \p key in the list, + unlinks it from the list, and returns \p true. + If \p key is not found the function return \p false. + + \p disposer specified in \p Traits is called for deleted item. + */ + template + bool erase( Q const& key ) + { + return erase_at( m_pHead, key, key_comparator()); + } + + /// Deletes the item from the list using \p pred predicate for searching + /** + The function is an analog of \ref cds_intrusive_IterableList_hp_erase_val "erase(Q const&)" + 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 list. + + \p disposer specified in \p Traits is called for deleted item. + */ + template + bool erase_with( Q const& key, Less pred ) + { + CDS_UNUSED( pred ); + return erase_at( m_pHead, key, cds::opt::details::make_comparator_from_less()); + } + + /// Deletes the item from the list + /** \anchor cds_intrusive_IterableList_hp_erase_func + The function searches an item with key equal to \p key in the list, + call \p func functor with item found, unlinks it from the list, and returns \p true. + The \p Func interface is + \code + struct functor { + void operator()( value_type const& item ); + }; + \endcode + If \p key is not found the function return \p false, \p func is not called. + + \p disposer specified in \p Traits is called for deleted item. + */ + template + bool erase( Q const& key, Func func ) + { + return erase_at( m_pHead, key, key_comparator(), func ); + } + + /// Deletes the item from the list using \p pred predicate for searching + /** + The function is an analog of \ref cds_intrusive_IterableList_hp_erase_func "erase(Q const&, Func)" + 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 list. + + \p disposer specified in \p Traits is called for deleted item. + */ + template + bool erase_with( Q const& key, Less pred, Func f ) + { + CDS_UNUSED( pred ); + return erase_at( m_pHead, key, cds::opt::details::make_comparator_from_less(), f ); + } + + /// Extracts the item from the list with specified \p key + /** \anchor cds_intrusive_IterableList_hp_extract + The function searches an item with key equal to \p key, + unlinks it from the list, and returns it as \p guarded_ptr. + If \p key is not found returns an empty guarded pointer. + + Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type. + + The \ref disposer specified in \p Traits class template parameter is called automatically + by garbage collector \p GC when returned \ref guarded_ptr object will be destroyed or released. + @note Each \p guarded_ptr object uses the GC's guard that can be limited resource. + + Usage: + \code + typedef cds::intrusive::IterableList< cds::gc::HP, foo, my_traits > ord_list; + ord_list theList; + // ... + { + ord_list::guarded_ptr gp(theList.extract( 5 )); + if ( gp ) { + // Deal with gp + // ... + } + // Destructor of gp releases internal HP guard + } + \endcode + */ + template + guarded_ptr extract( Q const& key ) + { + guarded_ptr gp; + extract_at( m_pHead, gp.guard(), key, key_comparator()); + return gp; + } + + /// Extracts the item using compare functor \p pred + /** + The function is an analog of \ref cds_intrusive_IterableList_hp_extract "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 pred must imply the same element order as the comparator used for building the list. + */ + template + guarded_ptr extract_with( Q const& key, Less pred ) + { + CDS_UNUSED( pred ); + guarded_ptr gp; + extract_at( m_pHead, gp.guard(), key, cds::opt::details::make_comparator_from_less()); + return gp; + } + + /// Finds \p key in the list + /** \anchor cds_intrusive_IterableList_hp_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 + struct functor { + void operator()( value_type& item, Q& key ); + }; + \endcode + where \p item is the item found, \p key is the \p %find() function argument. + + The functor may change non-key fields of \p item. Note that the function is only guarantee + that \p item cannot be disposed during functor is executing. + The function does not serialize simultaneous access to the \p item. If such access is + possible you must provide your own synchronization schema to keep out unsafe item modifications. + + The function returns \p true if \p val is found, \p false otherwise. + */ + template + bool find( Q& key, Func f ) const + { + return find_at( m_pHead, key, key_comparator(), f ); + } + //@cond + template + bool find( Q const& key, Func f ) const + { + return find_at( m_pHead, key, key_comparator(), f ); + } + //@endcond + + /// Finds \p key in the list and returns iterator pointed to the item found + /** + If \p key is not found the function returns \p end(). + */ + template + iterator find( Q& key ) const + { + return find_iterator_at( m_pHead, key, key_comparator()); + } + //@cond + template + iterator find( Q const& key ) const + { + return find_iterator_at( m_pHead, key, key_comparator() ); + } + //@endcond + + /// Finds the \p key using \p pred predicate for searching + /** + The function is an analog of \ref cds_intrusive_IterableList_hp_find_func "find(Q&, Func)" + 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 list. + */ + template + bool find_with( Q& key, Less pred, Func f ) const + { + CDS_UNUSED( pred ); + return find_at( m_pHead, key, cds::opt::details::make_comparator_from_less(), f ); + } + //@cond + template + bool find_with( Q const& key, Less pred, Func f ) const + { + CDS_UNUSED( pred ); + return find_at( m_pHead, key, cds::opt::details::make_comparator_from_less(), f ); + } + //@endcond + + /// Finds \p key in the list using \p pred predicate for searching and returns iterator pointed to the item found + /** + 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 list. + + If \p key is not found the function returns \p end(). + */ + template + iterator find_with( Q& key, Less pred ) const + { + CDS_UNUSED( pred ); + return find_iterator_at( m_pHead, key, cds::opt::details::make_comparator_from_less()); + } + //@cond + template + iterator find_with( Q const& key, Less pred ) const + { + CDS_UNUSED( pred ); + return find_iterator_at( m_pHead, key, cds::opt::details::make_comparator_from_less()); + } + //@endcond + + /// Checks whether the list contains \p key + /** + The function searches the item with key equal to \p key + and returns \p true if it is found, and \p false otherwise. + */ + template + bool contains( Q const& key ) const + { + return find_at( m_pHead, key, key_comparator()); + } + + /// Checks whether the list contains \p key using \p pred predicate for searching + /** + The function is an analog of contains( key ) 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 list. + */ + template + bool contains( Q const& key, Less pred ) const + { + CDS_UNUSED( pred ); + return find_at( m_pHead, key, cds::opt::details::make_comparator_from_less()); + } + + /// Finds the \p key and return the item found + /** \anchor cds_intrusive_IterableList_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. + + The \ref disposer specified in \p Traits class template parameter is called + by garbage collector \p GC automatically when returned \ref guarded_ptr object + will be destroyed or released. + @note Each \p guarded_ptr object uses one GC's guard which can be limited resource. + + Usage: + \code + typedef cds::intrusive::IterableList< cds::gc::HP, foo, my_traits > ord_list; + ord_list theList; + // ... + { + ord_list::guarded_ptr gp(theList.get( 5 )); + if ( gp ) { + // Deal with gp + //... + } + // Destructor of guarded_ptr releases internal HP guard + } + \endcode + + Note the compare functor specified for \p Traits template parameter + should accept a parameter of type \p Q that can be not the same as \p value_type. + */ + template + guarded_ptr get( Q const& key ) const + { + guarded_ptr gp; + get_at( m_pHead, gp.guard(), key, key_comparator()); + return gp; + } + + /// Finds the \p key and return the item found + /** + The function is an analog of \ref cds_intrusive_IterableList_hp_get "get( Q const&)" + but \p pred is used for comparing the keys. + + \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 pred must imply the same element order as the comparator used for building the list. + */ + template + guarded_ptr get_with( Q const& key, Less pred ) const + { + CDS_UNUSED( pred ); + guarded_ptr gp; + get_at( m_pHead, gp.guard(), key, cds::opt::details::make_comparator_from_less()); + return gp; + } + + /// Clears the list (thread safe, not atomic) + void clear() + { + position pos; + for ( pos.pCur = m_pHead.load( memory_model::memory_order_relaxed ); pos.pCur; pos.pCur = pos.pCur->next.load( memory_model::memory_order_relaxed )) { + while ( true ) { + pos.pFound = pos.guard.protect( pos.pCur->data ); + if ( !pos.pFound ) + break; + if ( cds_likely( unlink_node( pos ))) { + --m_ItemCounter; + break; + } + } + } + } + + /// Checks if the list is empty + /** + Emptiness is checked by item counting: if item count is zero then the set is empty. + Thus, if you need to use \p %empty() you should provide appropriate (non-empty) \p iterable_list::traits::item_counter + feature. + */ + bool empty() const + { + return size() == 0; + } + + /// Returns list's item count + /** + The value returned depends on item counter provided by \p iterable_list::traits::item_counter. For \p atomicity::empty_item_counter, + this function always returns 0. + */ + size_t size() const + { + return m_ItemCounter.value(); + } + + protected: + //@cond +#if 0 + // split-list support + bool insert_aux_node( node_type * pNode ) + { + return insert_aux_node( m_pHead, pNode ); + } + + // split-list support + bool insert_aux_node( atomic_node_ptr& refHead, node_type * pNode ) + { + assert( pNode != nullptr ); + + // Hack: convert node_type to value_type. + // In principle, auxiliary node can be non-reducible to value_type + // We assume that comparator can correctly distinguish aux and regular node. + return insert_at( refHead, *node_traits::to_value_ptr( pNode ) ); + } +#endif + + bool insert_at( atomic_node_ptr& refHead, value_type& val ) + { + position pos; + + while ( true ) { + if ( search( refHead, val, pos, key_comparator() ) ) + return false; + + if ( link_node( &val, pos ) ) { + ++m_ItemCounter; + return true; + } + } + } + + template + bool insert_at( atomic_node_ptr& refHead, value_type& val, Func f ) + { + position pos; + + typename gc::Guard guard; + guard.assign( &val ); + + while ( true ) { + if ( search( refHead, val, pos, key_comparator() ) ) + return false; + + if ( link_node( &val, pos ) ) { + f( val ); + ++m_ItemCounter; + return true; + } + } + } + + template + std::pair update_at( atomic_node_ptr& refHead, value_type& val, Func func, bool bInsert ) + { + position pos; + + typename gc::Guard guard; + guard.assign( &val ); + + while ( true ) { + if ( search( refHead, val, pos, key_comparator() ) ) { + // try to replace pCur->data with val + assert( pos.pFound != nullptr ); + assert( key_comparator()(*pos.pFound, val) == 0 ); + + if ( cds_likely( pos.pCur->data.compare_exchange_strong( pos.pFound, &val, memory_model::memory_order_release, atomics::memory_order_relaxed ))) { + if ( pos.pFound != &val ) { + retire_data( pos.pFound ); + func( val, pos.pFound ); + } + return std::make_pair( true, false ); + } + } + else { + if ( !bInsert ) + return std::make_pair( false, false ); + + if ( link_node( &val, pos ) ) { + func( val, static_cast( nullptr )); + ++m_ItemCounter; + return std::make_pair( true, true ); + } + } + } + } + + bool unlink_at( atomic_node_ptr& refHead, value_type& val ) + { + position pos; + + back_off bkoff; + while ( search( refHead, val, pos, key_comparator())) { + if ( pos.pFound == &val ) { + if ( unlink_node( pos )) { + --m_ItemCounter; + return true; + } + else + bkoff(); + } + else + break; + } + return false; + } + + template + bool erase_at( atomic_node_ptr& refHead, const Q& val, Compare cmp, Func f, position& pos ) + { + back_off bkoff; + while ( search( refHead, val, pos, cmp )) { + if ( unlink_node( pos )) { + f( *pos.pFound ); + --m_ItemCounter; + return true; + } + else + bkoff(); + } + return false; + } + + template + bool erase_at( atomic_node_ptr& refHead, const Q& val, Compare cmp, Func f ) + { + position pos; + return erase_at( refHead, val, cmp, f, pos ); + } + + template + bool erase_at( atomic_node_ptr& refHead, Q const& val, Compare cmp ) + { + position pos; + return erase_at( refHead, val, cmp, [](value_type const&){}, pos ); + } + + template + bool extract_at( atomic_node_ptr& refHead, typename guarded_ptr::native_guard& dest, Q const& val, Compare cmp ) + { + position pos; + back_off bkoff; + while ( search( refHead, val, pos, cmp )) { + if ( unlink_node( pos )) { + dest.set( pos.pFound ); + --m_ItemCounter; + return true; + } + else + bkoff(); + } + return false; + } + + template + bool find_at( atomic_node_ptr const& refHead, Q const& val, Compare cmp ) const + { + position pos; + return search( refHead, val, pos, cmp ); + } + + template + bool find_at( atomic_node_ptr const& refHead, Q& val, Compare cmp, Func f ) const + { + position pos; + if ( search( refHead, val, pos, cmp )) { + assert( pos.pFound != nullptr ); + f( *pos.pFound, val ); + return true; + } + return false; + } + + template + iterator find_iterator_at( atomic_node_ptr const& refHead, Q const& val, Compare cmp ) const + { + position pos; + if ( search( refHead, val, pos, cmp )) { + assert( pos.pCur != nullptr ); + assert( pos.pFound != nullptr ); + return iterator( pos.pCur, pos.pFound ); + } + return iterator{}; + } + + template + bool get_at( atomic_node_ptr const& refHead, typename guarded_ptr::native_guard& guard, Q const& val, Compare cmp ) const + { + position pos; + if ( search( refHead, val, pos, cmp )) { + guard.set( pos.pFound ); + return true; + } + return false; + } + //@endcond + + protected: + + //@cond + template + bool search( atomic_node_ptr const& refHead, const Q& val, position& pos, Compare cmp ) const + { + atomic_node_ptr* pHead = const_cast( &refHead ); + node_type * pPrev = nullptr; + + while ( true ) { + node_type * pCur = pHead->load( memory_model::memory_order_relaxed ); + + if ( pCur == nullptr ) { + // end-of-list + pos.pHead = pHead; + pos.pPrev = pPrev; + pos.pCur = nullptr; + pos.pFound = nullptr; + return false; + } + + value_type * pVal = pos.guard.protect( pCur->data ); + + if ( pVal ) { + int nCmp = cmp( *pVal, val ); + if ( nCmp >= 0 ) { + pos.pHead = pHead; + pos.pPrev = pPrev; + pos.pCur = pCur; + pos.pFound = pVal; + return nCmp == 0; + } + } + + pPrev = pCur; + pHead = &( pCur->next ); + } + } + //@endcond + + private: + //@cond + static node_type * alloc_node( value_type * pVal ) + { + return cxx_node_allocator().New( pVal ); + } + + static void delete_node( node_type * pNode ) + { + cxx_node_allocator().Delete( pNode ); + } + + static void retire_data( value_type * pVal ) + { + assert( pVal != nullptr ); + gc::template retire( pVal ); + } + + void destroy() + { + node_type * pNode = m_pHead.load( memory_model::memory_order_relaxed ); + while ( pNode ) { + value_type * pVal = pNode->data.load( memory_model::memory_order_relaxed ); + if ( pVal ) + retire_data( pVal ); + node_type * pNext = pNode->next.load( memory_model::memory_order_relaxed ); + delete_node( pNode ); + pNode = pNext; + } + } + + static bool link_node( value_type * pVal, position& pos ) + { + if ( pos.pPrev ) { + if ( pos.pPrev->data.load( memory_model::memory_order_relaxed ) == nullptr ) { + // reuse pPrev + value_type * p = nullptr; + return pos.pPrev->data.compare_exchange_strong( p, pVal, memory_model::memory_order_release, atomics::memory_order_relaxed ); + } + else { + // insert new node between pos.pPrev and pos.pCur + node_type * pNode = alloc_node( pVal ); + pNode->next.store( pos.pCur, memory_model::memory_order_relaxed ); + + if ( cds_likely( pos.pPrev->next.compare_exchange_strong( pos.pCur, pNode, memory_model::memory_order_release, atomics::memory_order_relaxed ))) + return true; + + delete_node( pNode ); + } + } + else { + node_type * pNode = alloc_node( pVal ); + pNode->next.store( pos.pCur, memory_model::memory_order_relaxed ); + if ( cds_likely( pos.pHead->compare_exchange_strong( pos.pCur, pNode, memory_model::memory_order_release, atomics::memory_order_relaxed ) ) ) + return true; + + delete_node( pNode ); + } + return false; + } + + static bool unlink_node( position& pos ) + { + assert( pos.pCur != nullptr ); + assert( pos.pFound != nullptr ); + + if ( pos.pCur->data.compare_exchange_strong( pos.pFound, nullptr, memory_model::memory_order_acquire, atomics::memory_order_relaxed ) ) { + retire_data( pos.pFound ); + return true; + } + return false; + } + + //@endcond + }; +}} // namespace cds::intrusive + +#endif // #ifndef CDSLIB_INTRUSIVE_IMPL_ITERABLE_LIST_H diff --git a/cds/intrusive/impl/michael_list.h b/cds/intrusive/impl/michael_list.h index 37be7ebb..55c778e0 100644 --- a/cds/intrusive/impl/michael_list.h +++ b/cds/intrusive/impl/michael_list.h @@ -583,8 +583,8 @@ namespace cds { namespace intrusive { that during changing no any other modifications could be made on this item by concurrent threads. Returns 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 list. + \p second is \p true if new item has been added or \p false if the item with that key + already in the list. @warning See \ref cds_intrusive_item_creating "insert item troubleshooting" */ diff --git a/cds/intrusive/iterable_list_dhp.h b/cds/intrusive/iterable_list_dhp.h new file mode 100644 index 00000000..5685f1d7 --- /dev/null +++ b/cds/intrusive/iterable_list_dhp.h @@ -0,0 +1,37 @@ +/* + 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 CDSLIB_INTRUSIVE_ITERABLE_LIST_DHP_H +#define CDSLIB_INTRUSIVE_ITERABLE_LIST_DHP_H + +#include +#include + +#endif // #ifndef CDSLIB_INTRUSIVE_ITERABLE_LIST_DHP_H diff --git a/cds/intrusive/iterable_list_hp.h b/cds/intrusive/iterable_list_hp.h new file mode 100644 index 00000000..c2718b38 --- /dev/null +++ b/cds/intrusive/iterable_list_hp.h @@ -0,0 +1,37 @@ +/* + 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 CDSLIB_INTRUSIVE_ITERABLE_LIST_HP_H +#define CDSLIB_INTRUSIVE_ITERABLE_LIST_HP_H + +#include +#include + +#endif // #ifndef CDSLIB_INTRUSIVE_ITERABLE_LIST_HP_H diff --git a/projects/Win/vc14/cds.vcxproj b/projects/Win/vc14/cds.vcxproj index 9694c1e0..e994ff6e 100644 --- a/projects/Win/vc14/cds.vcxproj +++ b/projects/Win/vc14/cds.vcxproj @@ -509,6 +509,7 @@ + @@ -524,10 +525,13 @@ + + + diff --git a/projects/Win/vc14/cds.vcxproj.filters b/projects/Win/vc14/cds.vcxproj.filters index b9a9ef05..14525378 100644 --- a/projects/Win/vc14/cds.vcxproj.filters +++ b/projects/Win/vc14/cds.vcxproj.filters @@ -102,12 +102,6 @@ {7226715d-6777-4c01-8e66-83b3885c00c1} - - {84ca9e83-f6c9-4503-a45f-14f08317fd70} - - - {4b79fe31-4f6c-4e05-8910-1151a26d51f3} - {67DA6AB6-F800-4c08-8B7A-83BB121AAD01} rc;ico;cur;bmp;dlg;rc2;rct;bin;rgs;gif;jpg;jpeg;jpe;resx @@ -118,12 +112,6 @@ {560b4d4c-71e1-443c-942e-dcc5a275c7c2} - - {6530b757-5bb7-4de0-b1c9-019acc8183ba} - - - {d3f68c37-8c36-448e-9d4c-cd89a940d275} - {32754dfc-727a-42ff-b243-9a8510bf5c4e} @@ -145,9 +133,6 @@ {00a14aa8-3035-4b56-bc86-442ca9bf8f44} - - {0a2328b4-ff6f-4afb-8de0-9884ae172fa9} - {3195cce2-1710-4b79-a1cf-6c7cea085fa3} @@ -157,6 +142,21 @@ {fe703227-44ad-4ad6-bae4-b6c9f5c65355} + + {84ca9e83-f6c9-4503-a45f-14f08317fd70} + + + {4b79fe31-4f6c-4e05-8910-1151a26d51f3} + + + {6530b757-5bb7-4de0-b1c9-019acc8183ba} + + + {d3f68c37-8c36-448e-9d4c-cd89a940d275} + + + {0a2328b4-ff6f-4afb-8de0-9884ae172fa9} + @@ -516,103 +516,103 @@ Header Files\cds\intrusive - Header Files\cds\container + Header Files\cds\gc\container - Header Files\cds\container + Header Files\cds\gc\container - Header Files\cds\container + Header Files\cds\gc\container - Header Files\cds\container + Header Files\cds\gc\container - Header Files\cds\container + Header Files\cds\gc\container - Header Files\cds\container + Header Files\cds\gc\container - Header Files\cds\container + Header Files\cds\gc\container - Header Files\cds\container + Header Files\cds\gc\container - Header Files\cds\container + Header Files\cds\gc\container - Header Files\cds\container + Header Files\cds\gc\container - Header Files\cds\container + Header Files\cds\gc\container - Header Files\cds\container + Header Files\cds\gc\container - Header Files\cds\container + Header Files\cds\gc\container - Header Files\cds\container + Header Files\cds\gc\container - Header Files\cds\container + Header Files\cds\gc\container - Header Files\cds\container + Header Files\cds\gc\container - Header Files\cds\container + Header Files\cds\gc\container - Header Files\cds\container + Header Files\cds\gc\container - Header Files\cds\container + Header Files\cds\gc\container - Header Files\cds\container + Header Files\cds\gc\container - Header Files\cds\container + Header Files\cds\gc\container - Header Files\cds\container + Header Files\cds\gc\container - Header Files\cds\container + Header Files\cds\gc\container - Header Files\cds\container + Header Files\cds\gc\container - Header Files\cds\container + Header Files\cds\gc\container - Header Files\cds\container + Header Files\cds\gc\container - Header Files\cds\container + Header Files\cds\gc\container - Header Files\cds\container + Header Files\cds\gc\container - Header Files\cds\container\details + Header Files\cds\gc\container\details - Header Files\cds\container\details + Header Files\cds\gc\container\details - Header Files\cds\container\details + Header Files\cds\gc\container\details - Header Files\cds\container\details + Header Files\cds\gc\container\details - Header Files\cds\container\details + Header Files\cds\gc\container\details Header Files\cds\compiler @@ -645,7 +645,7 @@ Header Files\cds\intrusive - Header Files\cds\container + Header Files\cds\gc\container Header Files\cds\intrusive @@ -687,91 +687,91 @@ Header Files\cds\intrusive\striped_set - Header Files\cds\container\striped_set + Header Files\cds\gc\container\striped_set - Header Files\cds\container\striped_set + Header Files\cds\gc\container\striped_set - Header Files\cds\container\striped_set + Header Files\cds\gc\container\striped_set - Header Files\cds\container\striped_set + Header Files\cds\gc\container\striped_set - Header Files\cds\container\striped_set + Header Files\cds\gc\container\striped_set - Header Files\cds\container\striped_set + Header Files\cds\gc\container\striped_set - Header Files\cds\container\striped_set + Header Files\cds\gc\container\striped_set - Header Files\cds\container\striped_set + Header Files\cds\gc\container\striped_set - Header Files\cds\container\striped_set + Header Files\cds\gc\container\striped_set - Header Files\cds\container\striped_set + Header Files\cds\gc\container\striped_set - Header Files\cds\container\striped_set + Header Files\cds\gc\container\striped_set - Header Files\cds\container\striped_set + Header Files\cds\gc\container\striped_set - Header Files\cds\container\striped_map + Header Files\cds\gc\container\striped_map - Header Files\cds\container\striped_map + Header Files\cds\gc\container\striped_map - Header Files\cds\container\striped_map + Header Files\cds\gc\container\striped_map - Header Files\cds\container\striped_map + Header Files\cds\gc\container\striped_map - Header Files\cds\container\striped_map + Header Files\cds\gc\container\striped_map - Header Files\cds\container\striped_map + Header Files\cds\gc\container\striped_map - Header Files\cds\container\striped_map + Header Files\cds\gc\container\striped_map - Header Files\cds\container\striped_map + Header Files\cds\gc\container\striped_map - Header Files\cds\container + Header Files\cds\gc\container - Header Files\cds\container + Header Files\cds\gc\container - Header Files\cds\container + Header Files\cds\gc\container - Header Files\cds\container + Header Files\cds\gc\container Header Files\cds\intrusive - Header Files\cds\container + Header Files\cds\gc\container - Header Files\cds\container\details + Header Files\cds\gc\container\details - Header Files\cds\container + Header Files\cds\gc\container - Header Files\cds\container\details + Header Files\cds\gc\container\details Header Files\cds\details @@ -825,40 +825,40 @@ Header Files\cds\intrusive - Header Files\cds\container + Header Files\cds\gc\container - Header Files\cds\container + Header Files\cds\gc\container - Header Files\cds\container + Header Files\cds\gc\container - Header Files\cds\container + Header Files\cds\gc\container Header Files\cds\intrusive - Header Files\cds\container + Header Files\cds\gc\container - Header Files\cds\container + Header Files\cds\gc\container - Header Files\cds\container + Header Files\cds\gc\container - Header Files\cds\container + Header Files\cds\gc\container Header Files\cds\intrusive - Header Files\cds\container + Header Files\cds\gc\container - Header Files\cds\container + Header Files\cds\gc\container Header Files\cds\intrusive @@ -870,10 +870,10 @@ Header Files\cds\threading - Header Files\cds\container + Header Files\cds\gc\container - Header Files\cds\container + Header Files\cds\gc\container Header Files\cds\details @@ -909,7 +909,7 @@ Header Files\cds\intrusive - Header Files\cds\container + Header Files\cds\gc\container Header Files\cds\memory @@ -918,13 +918,13 @@ Header Files\cds\memory - Header Files\cds\container + Header Files\cds\gc\container Header Files\cds\details - Header Files\cds\container + Header Files\cds\gc\container Header Files\cds\compiler\icl @@ -936,10 +936,10 @@ Header Files\cds\details - Header Files\cds\container + Header Files\cds\gc\container - Header Files\cds\container + Header Files\cds\gc\container Header Files\cds\intrusive @@ -987,7 +987,7 @@ Header Files\cds\lock - Header Files\cds\container\details + Header Files\cds\gc\container\details Header Files\cds\compiler\gcc\x86 @@ -1029,91 +1029,91 @@ Header Files\cds\intrusive\details - Header Files\cds\container\details + Header Files\cds\gc\container\details - Header Files\cds\container\details + Header Files\cds\gc\container\details - Header Files\cds\container\details + Header Files\cds\gc\container\details - Header Files\cds\container\impl + Header Files\cds\gc\container\impl - Header Files\cds\container\impl + Header Files\cds\gc\container\impl - Header Files\cds\container\impl + Header Files\cds\gc\container\impl - Header Files\cds\container\details + Header Files\cds\gc\container\details - Header Files\cds\container\impl + Header Files\cds\gc\container\impl - Header Files\cds\container\impl + Header Files\cds\gc\container\impl - Header Files\cds\container\details + Header Files\cds\gc\container\details - Header Files\cds\container\impl + Header Files\cds\gc\container\impl - Header Files\cds\container\details + Header Files\cds\gc\container\details - Header Files\cds\container\details + Header Files\cds\gc\container\details - Header Files\cds\container\details + Header Files\cds\gc\container\details - Header Files\cds\container\impl + Header Files\cds\gc\container\impl - Header Files\cds\container\impl + Header Files\cds\gc\container\impl - Header Files\cds\container\details + Header Files\cds\gc\container\details - Header Files\cds\container + Header Files\cds\gc\container Header Files\cds\intrusive - Header Files\cds\container + Header Files\cds\gc\container Header Files\cds\intrusive - Header Files\cds\container + Header Files\cds\gc\container - Header Files\cds\container + Header Files\cds\gc\container Header Files\cds\intrusive - Header Files\cds\container + Header Files\cds\gc\container - Header Files\cds\container + Header Files\cds\gc\container Header Files\cds\intrusive - Header Files\cds\container + Header Files\cds\gc\container - Header Files\cds\container + Header Files\cds\gc\container Header Files\cds\gc @@ -1149,13 +1149,13 @@ Header Files\cds\algo - Header Files\cds\container\details + Header Files\cds\gc\container\details - Header Files\cds\container\impl + Header Files\cds\gc\container\impl - Header Files\cds\container + Header Files\cds\gc\container Header Files\cds\sync @@ -1197,37 +1197,37 @@ Header Files\cds\algo - Header Files\cds\container\details + Header Files\cds\gc\container\details - Header Files\cds\container\impl + Header Files\cds\gc\container\impl - Header Files\cds\container + Header Files\cds\gc\container - Header Files\cds\container + Header Files\cds\gc\container - Header Files\cds\container\details + Header Files\cds\gc\container\details - Header Files\cds\container\impl + Header Files\cds\gc\container\impl - Header Files\cds\container + Header Files\cds\gc\container - Header Files\cds\container + Header Files\cds\gc\container Header Files\cds\intrusive - Header Files\cds\container + Header Files\cds\gc\container - Header Files\cds\container + Header Files\cds\gc\container Header Files\cds\intrusive @@ -1244,5 +1244,17 @@ Header Files\cds\algo\flat_combining + + Header Files\cds\intrusive\details + + + Header Files\cds\intrusive\impl + + + Header Files\cds\intrusive + + + Header Files\cds\intrusive + \ No newline at end of file diff --git a/projects/Win/vc14/gtest-list.vcxproj b/projects/Win/vc14/gtest-list.vcxproj index 767fc125..bbd7b1c5 100644 --- a/projects/Win/vc14/gtest-list.vcxproj +++ b/projects/Win/vc14/gtest-list.vcxproj @@ -27,6 +27,8 @@ + + @@ -47,6 +49,8 @@ + + diff --git a/projects/Win/vc14/gtest-list.vcxproj.filters b/projects/Win/vc14/gtest-list.vcxproj.filters index 2fe3b715..2b38fd61 100644 --- a/projects/Win/vc14/gtest-list.vcxproj.filters +++ b/projects/Win/vc14/gtest-list.vcxproj.filters @@ -69,6 +69,12 @@ Header Files + + Header Files + + + Header Files + @@ -218,5 +224,11 @@ Source Files + + Source Files + + + Source Files + \ No newline at end of file diff --git a/test/unit/list/CMakeLists.txt b/test/unit/list/CMakeLists.txt index 8ecf2d4a..407dd510 100644 --- a/test/unit/list/CMakeLists.txt +++ b/test/unit/list/CMakeLists.txt @@ -2,6 +2,8 @@ set(PACKAGE_NAME unit-list) set(CDSGTEST_LIST_SOURCES ../main.cpp + intrusive_iterable_dhp.cpp + intrusive_iterable_hp.cpp intrusive_lazy_hp.cpp intrusive_lazy_dhp.cpp intrusive_lazy_nogc.cpp diff --git a/test/unit/list/intrusive_iterable_dhp.cpp b/test/unit/list/intrusive_iterable_dhp.cpp new file mode 100644 index 00000000..efa335a6 --- /dev/null +++ b/test/unit/list/intrusive_iterable_dhp.cpp @@ -0,0 +1,139 @@ +/* + 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_intrusive_iterable_list_hp.h" +#include + +namespace { + namespace ci = cds::intrusive; + typedef cds::gc::DHP gc_type; + + class IntrusiveIterableList_DHP : public cds_test::intrusive_iterable_list_hp + { + protected: + void SetUp() + { + typedef ci::IterableList< gc_type, item_type > list_type; + + // +1 - for guarded_ptr + // +3 - for iterator test + cds::gc::dhp::GarbageCollector::Construct( 16, list_type::c_nHazardPtrCount ); + cds::threading::Manager::attachThread(); + } + + void TearDown() + { + cds::threading::Manager::detachThread(); + cds::gc::dhp::GarbageCollector::Destruct(); + } + }; + + TEST_F( IntrusiveIterableList_DHP, less ) + { + typedef ci::IterableList< gc_type, item_type, + typename ci::iterable_list::make_traits< + ci::opt::disposer< mock_disposer > + ,cds::opt::less< less< item_type >> + , cds::opt::item_counter< cds::atomicity::item_counter > + >::type + > list_type; + + list_type l; + test_common( l ); + test_ordered_iterator( l ); + test_hp( l ); + } + + TEST_F( IntrusiveIterableList_DHP, compare ) + { + typedef ci::IterableList< gc_type, item_type, + typename ci::iterable_list::make_traits< + ci::opt::disposer< mock_disposer > + , cds::opt::compare< cmp< item_type >> + , cds::opt::item_counter< cds::atomicity::item_counter > + >::type + > list_type; + + list_type l; + test_common( l ); + test_ordered_iterator( l ); + test_hp( l ); + } + + TEST_F( IntrusiveIterableList_DHP, item_counting ) + { + struct traits : public ci::iterable_list::traits { + typedef mock_disposer disposer; + typedef cmp< item_type > compare; + typedef intrusive_iterable_list::less< item_type > less; + typedef cds::atomicity::item_counter item_counter; + }; + typedef ci::IterableList< gc_type, item_type, traits > list_type; + + list_type l; + test_common( l ); + test_ordered_iterator( l ); + test_hp( l ); + } + + TEST_F( IntrusiveIterableList_DHP, backoff ) + { + struct traits : public ci::iterable_list::traits { + typedef mock_disposer disposer; + typedef cmp< item_type > compare; + typedef intrusive_iterable_list::less< item_type > less; + typedef cds::atomicity::item_counter item_counter; + typedef cds::backoff::pause back_off; + }; + typedef ci::IterableList< gc_type, item_type, traits > list_type; + + list_type l; + test_common( l ); + test_ordered_iterator( l ); + test_hp( l ); + } + + TEST_F( IntrusiveIterableList_DHP, seqcst ) + { + struct traits : public ci::iterable_list::traits { + typedef mock_disposer disposer; + typedef intrusive_iterable_list::less< item_type > less; + typedef cds::atomicity::item_counter item_counter; + typedef cds::opt::v::sequential_consistent memory_model; + }; + typedef ci::IterableList< gc_type, item_type, traits > list_type; + + list_type l; + test_common( l ); + test_ordered_iterator( l ); + test_hp( l ); + } + +} // namespace diff --git a/test/unit/list/intrusive_iterable_hp.cpp b/test/unit/list/intrusive_iterable_hp.cpp new file mode 100644 index 00000000..cc4c6972 --- /dev/null +++ b/test/unit/list/intrusive_iterable_hp.cpp @@ -0,0 +1,140 @@ +/* + 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_intrusive_iterable_list_hp.h" +#include + +namespace { + namespace ci = cds::intrusive; + typedef cds::gc::HP gc_type; + + class IntrusiveIterableList_HP : public cds_test::intrusive_iterable_list_hp + { + protected: + void SetUp() + { + typedef ci::IterableList< gc_type, item_type > list_type; + + // +1 - for guarded_ptr + // +3 - for iterator test + cds::gc::hp::GarbageCollector::Construct( list_type::c_nHazardPtrCount + 3, 1, 16 ); + cds::threading::Manager::attachThread(); + } + + void TearDown() + { + cds::threading::Manager::detachThread(); + cds::gc::hp::GarbageCollector::Destruct( true ); + } + }; + + TEST_F( IntrusiveIterableList_HP, less ) + { + typedef ci::IterableList< gc_type, item_type, + typename ci::iterable_list::make_traits< + ci::opt::disposer< mock_disposer > + ,cds::opt::less< less< item_type >> + ,cds::opt::item_counter< cds::atomicity::item_counter > + + >::type + > list_type; + + list_type l; + test_common( l ); + test_ordered_iterator( l ); + test_hp( l ); + } + + TEST_F( IntrusiveIterableList_HP, compare ) + { + typedef ci::IterableList< gc_type, item_type, + typename ci::iterable_list::make_traits< + ci::opt::disposer< mock_disposer > + , cds::opt::compare< cmp< item_type >> + , cds::opt::item_counter< cds::atomicity::item_counter > + >::type + > list_type; + + list_type l; + test_common( l ); + test_ordered_iterator( l ); + test_hp( l ); + } + + TEST_F( IntrusiveIterableList_HP, item_counting ) + { + struct traits : public ci::iterable_list::traits { + typedef mock_disposer disposer; + typedef cmp< item_type > compare; + typedef intrusive_iterable_list::less< item_type > less; + typedef cds::atomicity::item_counter item_counter; + }; + typedef ci::IterableList< gc_type, item_type, traits > list_type; + + list_type l; + test_common( l ); + test_ordered_iterator( l ); + test_hp( l ); + } + + TEST_F( IntrusiveIterableList_HP, backoff ) + { + struct traits : public ci::iterable_list::traits { + typedef mock_disposer disposer; + typedef cmp< item_type > compare; + typedef intrusive_iterable_list::less< item_type > less; + typedef cds::atomicity::item_counter item_counter; + typedef cds::backoff::pause back_off; + }; + typedef ci::IterableList< gc_type, item_type, traits > list_type; + + list_type l; + test_common( l ); + test_ordered_iterator( l ); + test_hp( l ); + } + + TEST_F( IntrusiveIterableList_HP, seqcst ) + { + struct traits : public ci::iterable_list::traits { + typedef mock_disposer disposer; + typedef intrusive_iterable_list::less< item_type > less; + typedef cds::atomicity::item_counter item_counter; + typedef cds::opt::v::sequential_consistent memory_model; + }; + typedef ci::IterableList< gc_type, item_type, traits > list_type; + + list_type l; + test_common( l ); + test_ordered_iterator( l ); + test_hp( l ); + } + +} // namespace diff --git a/test/unit/list/test_intrusive_iterable_list.h b/test/unit/list/test_intrusive_iterable_list.h new file mode 100644 index 00000000..00c5c983 --- /dev/null +++ b/test/unit/list/test_intrusive_iterable_list.h @@ -0,0 +1,540 @@ +/* + 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_LIST_TEST_INTRUSIVE_ITERABLE_LIST_H +#define CDSUNIT_LIST_TEST_INTRUSIVE_ITERABLE_LIST_H + +#include +#include + +namespace cds_test { + + class intrusive_iterable_list : public fixture + { + public: + struct stat { + int nDisposeCount; + int nUpdateExistsCall; + int nUpdateNewCall; + int nFindCall; + int nEraseCall; + int nInsertCall; + + stat() + : nDisposeCount( 0 ) + , nUpdateExistsCall( 0 ) + , nUpdateNewCall( 0 ) + , nFindCall( 0 ) + , nEraseCall( 0 ) + , nInsertCall( 0 ) + {} + + stat( const stat& s ) + { + *this = s; + } + + stat& operator =( const stat& s ) + { + memcpy( this, &s, sizeof( s ) ); + return *this; + } + }; + + struct item_type + { + int nKey; + int nVal; + + mutable stat s; + + item_type() + {} + + item_type( int key, int val ) + : nKey( key ) + , nVal( val ) + , s() + {} + + item_type( const item_type& v ) + : nKey( v.nKey ) + , nVal( v.nVal ) + , s() + {} + + const int& key() const + { + return nKey; + } + + item_type& operator=( item_type const& src ) + { + nKey = src.nKey; + nVal = src.nVal; + return *this; + } + + item_type& operator=( item_type&& src ) + { + nKey = src.nKey; + nVal = src.nVal; + return *this; + } + }; + + template + struct less + { + bool operator ()( const T& v1, const T& v2 ) const + { + return v1.key() < v2.key(); + } + + template + bool operator ()( const T& v1, const Q& v2 ) const + { + return v1.key() < v2; + } + + template + bool operator ()( const Q& v1, const T& v2 ) const + { + return v1 < v2.key(); + } + }; + + struct other_item { + int nKey; + + other_item( int n ) + : nKey( n ) + {} + }; + + struct other_less { + template + bool operator()( T const& i1, Q const& i2 ) const + { + return i1.nKey < i2.nKey; + } + }; + + template + struct cmp { + int operator ()( const T& v1, const T& v2 ) const + { + if ( v1.key() < v2.key() ) + return -1; + return v1.key() > v2.key() ? 1 : 0; + } + + template + int operator ()( const T& v1, const Q& v2 ) const + { + if ( v1.key() < v2 ) + return -1; + return v1.key() > v2 ? 1 : 0; + } + + template + int operator ()( const Q& v1, const T& v2 ) const + { + if ( v1 < v2.key() ) + return -1; + return v1 > v2.key() ? 1 : 0; + } + }; + + struct mock_disposer + { + template + void operator ()( T * p ) + { + ++p->s.nDisposeCount; + } + }; + + struct update_functor + { + template + void operator()( T& item, T * old ) + { + if ( !old ) + ++item.s.nUpdateNewCall; + else + ++item.s.nUpdateExistsCall; + } + }; + + struct find_functor + { + template + void operator ()( T& item, Q& /*val*/ ) + { + ++item.s.nFindCall; + } + }; + + struct erase_functor + { + template + void operator()( T const& item ) + { + item.s.nEraseCall++; + } + }; + + protected: + template + void test_common( List& l ) + { + // Precondition: list is empty + // Postcondition: list is empty + + static const size_t nSize = 20; + typedef typename List::value_type value_type; + value_type arr[ nSize ]; + value_type arr2[ nSize ]; + + for ( size_t i = 0; i < nSize; ++i ) { + arr[i].nKey = static_cast( i ); + arr[i].nVal = arr[i].nKey * 10; + + arr2[i] = arr[i]; + } + shuffle( arr, arr + nSize ); + shuffle( arr2, arr2 + nSize ); + + ASSERT_TRUE( l.empty() ); + ASSERT_CONTAINER_SIZE( l, 0 ); + + typedef typename List::iterator iterator; + + // insert / find + for ( auto& i : arr ) { + EXPECT_FALSE( l.contains( i.nKey )); + EXPECT_FALSE( l.contains( other_item( i.nKey ), other_less())); + EXPECT_FALSE( l.find( i.nKey, []( value_type& item, int ) { ++item.s.nFindCall; } )); + EXPECT_EQ( i.s.nFindCall, 0 ); + EXPECT_FALSE( l.find_with( other_item( i.nKey ), other_less(), []( value_type& item, other_item const& ) { ++item.s.nFindCall; } )); + EXPECT_EQ( i.s.nFindCall, 0 ); + + switch ( i.nKey % 3 ) { + case 0: + EXPECT_TRUE( l.insert( i )); + break; + case 1: + EXPECT_EQ( i.s.nInsertCall, 0 ); + EXPECT_TRUE( l.insert( i, []( value_type& i ) { ++i.s.nInsertCall; } )); + EXPECT_EQ( i.s.nInsertCall, 1 ); + break; + case 2: + { + std::pair ret = l.update( i, []( value_type& i, value_type * old ) { + EXPECT_TRUE( old == nullptr ); + EXPECT_EQ( i.s.nUpdateNewCall, 0 ); + ++i.s.nUpdateNewCall; + }, false ); + EXPECT_EQ( i.s.nUpdateNewCall, 0 ); + EXPECT_EQ( ret.first, false ); + EXPECT_EQ( ret.second, false ); + + ret = l.update( i, []( value_type& i, value_type * old ) { + EXPECT_TRUE( old == nullptr ); + EXPECT_EQ( i.s.nUpdateNewCall, 0 ); + ++i.s.nUpdateNewCall; + }, true ); + EXPECT_EQ( i.s.nUpdateNewCall, 1 ); + EXPECT_EQ( ret.first, true ); + EXPECT_EQ( ret.second, true ); + } + break; + } + + EXPECT_TRUE( l.contains( i.nKey )); + EXPECT_TRUE( l.contains( i )); + EXPECT_TRUE( l.contains( other_item( i.nKey ), other_less())); + EXPECT_TRUE( l.find( i.nKey, []( value_type& item, int ) { ++item.s.nFindCall; } )); + EXPECT_EQ( i.s.nFindCall, 1 ); + EXPECT_TRUE( l.find( i, []( value_type& item, value_type const& ) { ++item.s.nFindCall; } )); + EXPECT_EQ( i.s.nFindCall, 2 ); + EXPECT_TRUE( l.find_with( other_item( i.nKey ), other_less(), []( value_type& item, other_item const& ) { ++item.s.nFindCall; } )); + EXPECT_EQ( i.s.nFindCall, 3 ); + + EXPECT_FALSE( l.insert( i ) ); + ASSERT_FALSE( l.empty() ); + + int const ckey = i.nKey; + iterator it = l.find( ckey ); + ASSERT_FALSE( it == l.end() ); + EXPECT_EQ( it->nKey, i.nKey ); + EXPECT_EQ( (*it).nVal, i.nVal ); + check_ordered( it, l.end() ); + + it = l.find( i.nKey ); + ASSERT_FALSE( it == l.end() ); + EXPECT_EQ( it->nKey, i.nKey ); + EXPECT_EQ( (*it).nVal, i.nVal ); + check_ordered( it, l.end() ); + + it = l.find_with( other_item( i.nKey ), other_less() ); + ASSERT_FALSE( it == l.end() ); + EXPECT_EQ( it->nKey, i.nKey ); + EXPECT_EQ( it->nVal, i.nVal ); + check_ordered( it, l.end() ); + + } + ASSERT_CONTAINER_SIZE( l, nSize ); + + // check all items + for ( auto const& i : arr ) { + EXPECT_TRUE( l.contains( i.nKey )); + EXPECT_TRUE( l.contains( i )); + EXPECT_TRUE( l.contains( other_item( i.nKey ), other_less())); + EXPECT_TRUE( l.find( i.nKey, []( value_type& item, int ) { ++item.s.nFindCall; } )); + EXPECT_EQ( i.s.nFindCall, 4 ); + EXPECT_TRUE( l.find( i, []( value_type& item, value_type const& ) { ++item.s.nFindCall; } )); + EXPECT_EQ( i.s.nFindCall, 5 ); + EXPECT_TRUE( l.find_with( other_item( i.nKey ), other_less(), []( value_type& item, other_item const& ) { ++item.s.nFindCall; } )); + EXPECT_EQ( i.s.nFindCall, 6 ); + } + ASSERT_FALSE( l.empty() ); + ASSERT_CONTAINER_SIZE( l, nSize ); + + // update existing test + for ( auto& i : arr2 ) { + EXPECT_EQ( i.s.nUpdateExistsCall, 0 ); + std::pair ret = l.update( i, update_functor() ); + EXPECT_TRUE( ret.first ); + EXPECT_FALSE( ret.second ); + EXPECT_EQ( i.s.nUpdateExistsCall, 1 ); + } + + // update with the same value must be empty - no functor is called + for ( auto& i : arr2 ) { + EXPECT_EQ( i.s.nUpdateExistsCall, 1 ); + std::pair ret = l.update( i, update_functor() ); + EXPECT_TRUE( ret.first ); + EXPECT_FALSE( ret.second ); + EXPECT_EQ( i.s.nUpdateExistsCall, 1 ); + } + + for ( auto& i : arr ) { + EXPECT_EQ( i.s.nUpdateExistsCall, 0 ); + std::pair ret = l.update( i, []( value_type& i, value_type * old ) { + EXPECT_FALSE( old == nullptr ); + EXPECT_EQ( i.s.nUpdateExistsCall, 0 ); + ++i.s.nUpdateExistsCall; + }); + EXPECT_TRUE( ret.first ); + EXPECT_FALSE( ret.second ); + EXPECT_EQ( i.s.nUpdateExistsCall, 1 ); + } + + // erase test + for ( auto const& i : arr ) { + if ( i.nKey & 1 ) + EXPECT_TRUE( l.erase( i.nKey )); + else + EXPECT_TRUE( l.erase_with( other_item( i.nKey ), other_less() )); + + EXPECT_FALSE( l.contains( i )); + } + EXPECT_TRUE( l.empty() ); + EXPECT_CONTAINER_SIZE( l, 0 ); + + // Apply retired pointer to clean links + List::gc::force_dispose(); + + for ( auto const& i : arr ) + EXPECT_EQ( i.s.nDisposeCount, 2 ); + for ( auto const& i : arr2 ) + EXPECT_EQ( i.s.nDisposeCount, 1 ); + + // erase with functor + for ( auto& i : arr ) { + int const updateNewCall = i.s.nUpdateNewCall; + std::pair ret = l.update( i, update_functor(), false ); + EXPECT_FALSE( ret.first ); + EXPECT_FALSE( ret.second ); + EXPECT_EQ( i.s.nUpdateNewCall, updateNewCall ); + + ret = l.update( i, update_functor(), true ); + EXPECT_TRUE( ret.first ); + EXPECT_TRUE( ret.second ); + EXPECT_EQ( i.s.nUpdateNewCall, updateNewCall + 1 ); + } + EXPECT_FALSE( l.empty() ); + EXPECT_CONTAINER_SIZE( l, nSize ); + + for ( auto const& i : arr ) { + EXPECT_EQ( i.s.nEraseCall, 0 ); + if ( i.nKey & 1 ) { + EXPECT_TRUE( l.erase_with( other_item( i.nKey ), other_less(), erase_functor())); + EXPECT_FALSE( l.erase_with( other_item( i.nKey ), other_less(), erase_functor())); + } + else { + EXPECT_TRUE( l.erase( i.nKey, []( value_type& item) { ++item.s.nEraseCall; } )); + EXPECT_FALSE( l.erase( i.nKey, []( value_type& item) { ++item.s.nEraseCall; } )); + } + EXPECT_EQ( i.s.nEraseCall, 1 ); + EXPECT_FALSE( l.contains( i.nKey )); + } + EXPECT_TRUE( l.empty() ); + EXPECT_CONTAINER_SIZE( l, 0 ); + + // Apply retired pointer to clean links + List::gc::force_dispose(); + + for ( auto const& i : arr ) + EXPECT_EQ( i.s.nDisposeCount, 3 ); + + // clear test + for ( auto& i : arr ) + EXPECT_TRUE( l.insert( i )); + + EXPECT_FALSE( l.empty() ); + EXPECT_CONTAINER_SIZE( l, nSize ); + + l.clear(); + + EXPECT_TRUE( l.empty() ); + EXPECT_CONTAINER_SIZE( l, 0 ); + + // Apply retired pointer to clean links + List::gc::force_dispose(); + for ( auto const& i : arr ) { + EXPECT_EQ( i.s.nDisposeCount, 4 ); + EXPECT_FALSE( l.contains( i )); + } + + // unlink test + for ( auto& i : arr ) + EXPECT_TRUE( l.insert( i ) ); + for ( auto& i : arr ) { + value_type val( i ); + EXPECT_TRUE( l.contains( val )); + EXPECT_FALSE( l.unlink( val )); + EXPECT_TRUE( l.contains( val ) ); + EXPECT_TRUE( l.unlink( i )); + EXPECT_FALSE( l.unlink( i )); + EXPECT_FALSE( l.contains( i ) ); + } + EXPECT_TRUE( l.empty() ); + EXPECT_CONTAINER_SIZE( l, 0 ); + + // Apply retired pointer to clean links + List::gc::force_dispose(); + for ( auto const& i : arr ) { + EXPECT_EQ( i.s.nDisposeCount, 5 ); + EXPECT_FALSE( l.contains( i ) ); + } + + // Iterators on empty list + { + auto it = l.begin(); + auto itEnd = l.end(); + auto cit = l.cbegin(); + auto citEnd = l.cend(); + + EXPECT_TRUE( it == itEnd ); + EXPECT_TRUE( it == cit ); + EXPECT_TRUE( cit == citEnd ); + + ++it; + ++cit; + + EXPECT_TRUE( it == itEnd ); + EXPECT_TRUE( it == cit ); + EXPECT_TRUE( cit == citEnd ); + } + } + + template + void test_ordered_iterator( List& l ) + { + // Precondition: list is empty + // Postcondition: list is empty + + static const size_t nSize = 20; + typedef typename List::value_type value_type; + value_type arr[nSize]; + + for ( size_t i = 0; i < nSize; ++i ) { + arr[i].nKey = static_cast(i); + arr[i].nVal = arr[i].nKey * 10; + } + shuffle( arr, arr + nSize ); + + ASSERT_TRUE( l.empty() ); + ASSERT_CONTAINER_SIZE( l, 0 ); + + for ( auto& i : arr ) + EXPECT_TRUE( l.insert( i ) ); + + int key = 0; + for ( auto it = l.begin(); it != l.end(); ++it ) { + EXPECT_EQ( it->nKey, key ); + EXPECT_EQ( (*it).nKey, key ); + ++key; + } + + key = 0; + for ( auto it = l.cbegin(); it != l.cend(); ++it ) { + EXPECT_EQ( it->nKey, key ); + EXPECT_EQ( (*it).nKey, key ); + ++key; + } + + l.clear(); + List::gc::force_dispose(); + for ( auto const& i : arr ) { + EXPECT_EQ( i.s.nDisposeCount, 1 ); + EXPECT_FALSE( l.contains( i ) ); + } + } + + template + void check_ordered( Iterator first, Iterator last ) + { + while ( first != last ) { + Iterator it = first; + if ( ++it != last ) { + EXPECT_LT( first->nKey, it->nKey ); + } + first = it; + } + } + + }; + +} // namespace cds_test + +#endif // CDSUNIT_LIST_TEST_INTRUSIVE_ITERABLE_LIST_H diff --git a/test/unit/list/test_intrusive_iterable_list_hp.h b/test/unit/list/test_intrusive_iterable_list_hp.h new file mode 100644 index 00000000..4fbb63db --- /dev/null +++ b/test/unit/list/test_intrusive_iterable_list_hp.h @@ -0,0 +1,110 @@ +/* + 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_LIST_TEST_INTRUSIVE_ITERABLE_LIST_HP_H +#define CDSUNIT_LIST_TEST_INTRUSIVE_ITERABLE_LIST_HP_H + +#include "test_intrusive_iterable_list.h" + +namespace cds_test { + + class intrusive_iterable_list_hp : public intrusive_iterable_list + { + protected: + template + void test_hp( List& l ) + { + // Precondition: list is empty + // Postcondition: list is empty + + static const size_t nSize = 20; + typedef typename List::value_type value_type; + value_type arr[nSize]; + + for ( size_t i = 0; i < nSize; ++i ) { + arr[i].nKey = static_cast(i); + arr[i].nVal = arr[i].nKey * 10; + } + shuffle( arr, arr + nSize ); + + typedef typename List::guarded_ptr guarded_ptr; + + ASSERT_TRUE( l.empty() ); + ASSERT_CONTAINER_SIZE( l, 0 ); + + guarded_ptr gp; + + // get() test + for ( auto& i : arr ) { + gp = l.get( i.nKey ); + EXPECT_TRUE( !gp ); + gp = l.get_with( other_item( i.nKey ), other_less() ); + EXPECT_TRUE( !gp ); + + EXPECT_TRUE( l.insert( i ) ); + + gp = l.get( i.nKey ); + ASSERT_FALSE( !gp ); + EXPECT_EQ( gp->nKey, i.nKey ); + EXPECT_EQ( gp->nVal, i.nVal ); + gp = l.get_with( other_item( i.nKey ), other_less() ); + ASSERT_FALSE( !gp ); + EXPECT_EQ( gp->nKey, i.nKey ); + EXPECT_EQ( gp->nVal, i.nVal ); + } + + // extract() test + for ( int i = 0; i < static_cast(nSize); ++i ) { + if ( i & 1 ) + gp = l.extract( i ); + else + gp = l.extract_with( other_item( i ), other_less() ); + ASSERT_FALSE( !gp ); + EXPECT_EQ( gp->nKey, i ); + + gp = l.extract( i ); + EXPECT_TRUE( !gp ); + gp = l.extract_with( other_item( i ), other_less() ); + EXPECT_TRUE( !gp ); + } + + ASSERT_TRUE( l.empty() ); + ASSERT_CONTAINER_SIZE( l, 0 ); + + List::gc::force_dispose(); + for ( auto const& i : arr ) { + EXPECT_EQ( i.s.nDisposeCount, 1 ); + EXPECT_FALSE( l.contains( i ) ); + } + } + }; + +} // namespace cds_test + +#endif // CDSUNIT_LIST_TEST_INTRUSIVE_ITERABLE_LIST_HP_H -- 2.34.1