From 994743d48f3b6bc593944c1998f6109339aa135c Mon Sep 17 00:00:00 2001 From: khizmax Date: Mon, 1 Aug 2016 18:30:04 +0300 Subject: [PATCH] Added container::IterableList --- cds/container/details/iterable_list_base.h | 164 ++++ cds/container/details/make_iterable_kvlist.h | 96 ++ cds/container/details/make_iterable_list.h | 82 ++ cds/container/impl/iterable_list.h | 893 +++++++++++++++++++ cds/container/iterable_list_dhp.h | 39 + cds/container/iterable_list_hp.h | 39 + cds/intrusive/impl/iterable_list.h | 2 +- projects/Win/vc14/cds.vcxproj | 6 + projects/Win/vc14/cds.vcxproj.filters | 18 + projects/Win/vc14/gtest-list.vcxproj | 4 + projects/Win/vc14/gtest-list.vcxproj.filters | 213 +++-- test/unit/list/CMakeLists.txt | 2 + test/unit/list/iterable_dhp.cpp | 170 ++++ test/unit/list/iterable_hp.cpp | 170 ++++ test/unit/list/test_iterable_list.h | 405 +++++++++ test/unit/list/test_iterable_list_hp.h | 136 +++ 16 files changed, 2342 insertions(+), 97 deletions(-) create mode 100644 cds/container/details/iterable_list_base.h create mode 100644 cds/container/details/make_iterable_kvlist.h create mode 100644 cds/container/details/make_iterable_list.h create mode 100644 cds/container/impl/iterable_list.h create mode 100644 cds/container/iterable_list_dhp.h create mode 100644 cds/container/iterable_list_hp.h create mode 100644 test/unit/list/iterable_dhp.cpp create mode 100644 test/unit/list/iterable_hp.cpp create mode 100644 test/unit/list/test_iterable_list.h create mode 100644 test/unit/list/test_iterable_list_hp.h diff --git a/cds/container/details/iterable_list_base.h b/cds/container/details/iterable_list_base.h new file mode 100644 index 00000000..2adc1aa8 --- /dev/null +++ b/cds/container/details/iterable_list_base.h @@ -0,0 +1,164 @@ +/* + 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_CONTAINER_DETAILS_ITERABLE_LIST_BASE_H +#define CDSLIB_CONTAINER_DETAILS_ITERABLE_LIST_BASE_H + +#include +#include +#include + +namespace cds { namespace container { + + /// \p IterableList ordered list related definitions + /** @ingroup cds_nonintrusive_helper + */ + namespace iterable_list { + + /// \p IterableList internal statistics, see \p cds::intrusive::iterable_list::stat + template ::event_counter > + using stat = cds::intrusive::iterable_list::stat< EventCounter >; + + /// \p IterableList empty internal statistics, see \p cds::intrusive::iterable_list::empty_stat + typedef cds::intrusive::iterable_list::empty_stat empty_stat; + + //@cond + template ::stat_type > + using wrapped_stat = cds::intrusive::iterable_list::wrapped_stat< Stat >; + //@endif + + /// \p IterableList traits + struct traits + { + /// Allocator used to allocate new data + typedef CDS_DEFAULT_ALLOCATOR allocator; + + /// Node allocator + typedef intrusive::iterable_list::traits::node_allocator node_allocator; + + /// 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 comparison. + /** + Default is \p std::less. + */ + typedef opt::none less; + + /// Back-off strategy + typedef intrusive::iterable_list::traits::back_off back_off; + + /// Item counting feature; by default, disabled. Use \p cds::atomicity::item_counter to enable item counting + typedef intrusive::iterable_list::traits::item_counter item_counter; + + /// Internal statistics + /** + By default, internal statistics is disabled (\p iterable_list::empty_stat). + Use \p iterable_list::stat to enable it. + */ + typedef intrusive::iterable_list::traits::stat stat; + + /// 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_MichaelList_rcu "RCU-based MichaelList") + /** + List of available options see opt::rcu_check_deadlock + */ + typedef opt::v::rcu_throw_deadlock rcu_check_deadlock; + + //@cond + // IterableKVList: supporting for split-ordered list + // key accessor (opt::none = internal key type is equal to user key type) + typedef opt::none key_accessor; + //@endcond + }; + + /// 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::allocator - an allocator for data, default is \p CDS_DEFAULT_ALLOCATOR + - \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::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::stat - internal statistics. By default, it is disabled (\p iterable_list::empty_stat). + To enable it use \p iterable_list::stat + - \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 + + // Forward declarations + template + class IterableList; + + template + class IterableKVList; + + // Tag for selecting iterable list implementation + /** + This struct is empty and it is used only as a tag for selecting \p IterableList + as ordered list implementation in declaration of some classes. + + See split_list::traits::ordered_list as an example. + */ + struct iterable_list_tag + {}; + +}} // namespace cds::container + + +#endif // #ifndef CDSLIB_CONTAINER_DETAILS_ITERABLE_LIST_BASE_H diff --git a/cds/container/details/make_iterable_kvlist.h b/cds/container/details/make_iterable_kvlist.h new file mode 100644 index 00000000..811b917c --- /dev/null +++ b/cds/container/details/make_iterable_kvlist.h @@ -0,0 +1,96 @@ +/* + 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_CONTAINER_DETAILS_MAKE_ITERABLE_KVLIST_H +#define CDSLIB_CONTAINER_DETAILS_MAKE_ITERABLE_KVLIST_H + +#include + +namespace cds { namespace container { + + //@cond + namespace details { + + template + struct make_iterable_kvlist + { + typedef Traits original_type_traits; + + typedef GC gc; + typedef K key_type; + typedef T value_type; + typedef std::pair pair_type; + + typedef intrusive::iterable_list::node< pair_type > node_type; + + typedef typename original_type_traits::allocator::template rebind::other data_allocator_type; + typedef cds::details::Allocator< pair_type, allocator_type > cxx_data_allocator; + + typedef typename original_type_traits::memory_model memory_model; + + struct node_disposer + { + void operator ()( node_type * pNode ) + { + cxx_data_allocator().Delete( pNode->data.load( memory_model::memory_order_relaxed ) ); + } + }; + + struct key_field_accessor { + key_type const& operator()( node_type const& node ) + { + pair_type const* p = node.data.load( memory_model::memory_order_relaxed ); + assert( p != nullptr ) + return p->first; + } + }; + + typedef typename opt::details::make_comparator< key_type, original_type_traits >::type key_comparator; + + template + struct less_wrapper { + typedef cds::details::compare_wrapper< node_type, cds::opt::details::make_comparator_from_less, key_field_accessor > type; + }; + + struct intrusive_traits: public original_type_traits + { + typedef node_disposer disposer; + typedef cds::details::compare_wrapper< node_type, key_comparator, key_field_accessor > compare; + static const opt::link_check_type link_checker = intrusive::iterable_list::traits::link_checker; + }; + + typedef intrusive::IterableList type; + }; + } // namespace details + //@endcond + +}} // namespace cds::container + +#endif // #ifndef CDSLIB_CONTAINER_DETAILS_MAKE_ITERABLE_KVLIST_H diff --git a/cds/container/details/make_iterable_list.h b/cds/container/details/make_iterable_list.h new file mode 100644 index 00000000..f6df9f58 --- /dev/null +++ b/cds/container/details/make_iterable_list.h @@ -0,0 +1,82 @@ +/* + 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_CONTAINER_DETAILS_MAKE_ITERABLE_LIST_H +#define CDSLIB_CONTAINER_DETAILS_MAKE_ITERABLE_LIST_H + +#include +#include + +namespace cds { namespace container { + + //@cond + namespace details { + + template + struct make_iterable_list + { + typedef GC gc; + typedef T value_type; + + typedef Traits original_traits; + + typedef typename original_traits::allocator::template rebind::other data_allocator_type; + typedef cds::details::Allocator< value_type, data_allocator_type > cxx_data_allocator; + + typedef typename original_traits::memory_model memory_model; + + struct data_disposer + { + void operator ()( value_type* data ) + { + cxx_data_allocator().Delete( data ); + } + }; + + template + struct less_wrapper { + typedef cds::opt::details::make_comparator_from_less type; + }; + + struct intrusive_traits: public original_traits + { + typedef data_disposer disposer; + }; + + typedef intrusive::IterableList type; + + typedef typename type::key_comparator key_comparator; + }; + } // namespace details + //@endcond + +}} // namespace cds::container + +#endif // #ifndef CDSLIB_CONTAINER_DETAILS_MAKE_ITERABLE_LIST_H diff --git a/cds/container/impl/iterable_list.h b/cds/container/impl/iterable_list.h new file mode 100644 index 00000000..2d38c7fe --- /dev/null +++ b/cds/container/impl/iterable_list.h @@ -0,0 +1,893 @@ +/* + 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_CONTAINER_IMPL_ITERABLE_LIST_H +#define CDSLIB_CONTAINER_IMPL_ITERABLE_LIST_H + +#include +#include + +namespace cds { namespace container { + + /// Iterable ordered list + /** @ingroup cds_nonintrusive_list + \anchor cds_nonintrusive_IterableList_gc + + This lock-free list implementation supports thread-safe iterators. + + Usually, ordered single-linked list is used as a building block for the hash table implementation. + Iterable list is suitable for almost append-only hash table because the list doesn't delete + its internal node when erasing a key but it is marked them as empty to be reused in the future. + However, plenty of empty nodes degrades performance. + + 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. + + Unlike standard container, this implementation does not divide type \p T into key and value part and + may be used as a main building block for hash set algorithms. + The key is a function (or a part) of type \p T, and this function is specified by Traits::compare functor + or Traits::less predicate. + + \p IterableKVList is a key-value version of iterable non-intrusive list that is closer to the C++ std library approach. + + It is possible to declare option-based list with cds::container::iterable_list::make_traits metafunction istead of \p Traits template + argument. For example, the following traits-based declaration of gc::HP iterable list + \code + #include + // Declare comparator for the item + struct my_compare { + int operator ()( int i1, int i2 ) + { + return i1 - i2; + } + }; + + // Declare traits + struct my_traits: public cds::container::iterable_list::traits + { + typedef my_compare compare; + }; + + // Declare traits-based list + typedef cds::container::IterableList< cds::gc::HP, int, my_traits > traits_based_list; + \endcode + + is equivalent for the following option-based list + \code + #include + + // my_compare is the same + + // Declare option-based list + typedef cds::container::IterableList< cds::gc::HP, int, + typename cds::container::iterable_list::make_traits< + cds::container::opt::compare< my_compare > // item comparator option + >::type + > option_based_list; + \endcode + + \par Usage + There are different specializations of this template for each garbage collecting schema used. + You should include appropriate .h-file depending on GC you are using: + - for gc::HP: \code #include \endcode + - for gc::DHP: \code #include \endcode + - for \ref cds_urcu_desc "RCU": \code #include \endcode + */ + template < + typename GC, + typename T, +#ifdef CDS_DOXYGEN_INVOKED + typename Traits = iterable_list::traits +#else + typename Traits +#endif + > + class IterableList: +#ifdef CDS_DOXYGEN_INVOKED + protected intrusive::IterableList< GC, T, Traits > +#else + protected details::make_iterable_list< GC, T, Traits >::type +#endif + { + //@cond + typedef details::make_iterable_list< GC, T, Traits > maker; + typedef typename maker::type base_class; + //@endcond + + public: + typedef T value_type; ///< Type of value stored in the list + typedef Traits traits; ///< List traits + + typedef typename base_class::gc gc; ///< Garbage collector used + typedef typename base_class::back_off back_off; ///< Back-off strategy used + typedef typename maker::data_allocator_type allocator_type; ///< Allocator type used for allocate/deallocate data + typedef typename base_class::item_counter item_counter; ///< Item counting policy used + typedef typename maker::key_comparator key_comparator; ///< key comparison functor + typedef typename base_class::memory_model memory_model; ///< Memory ordering. See \p cds::opt::memory_model option + typedef typename base_class::stat stat; ///< Internal statistics + + static CDS_CONSTEXPR const size_t c_nHazardPtrCount = base_class::c_nHazardPtrCount; ///< Count of hazard pointer required for the algorithm + + protected: + //@cond + typedef typename base_class::value_type node_type; + typedef typename maker::cxx_data_allocator cxx_data_allocator; + typedef typename maker::data_disposer data_disposer; + typedef typename base_class::atomic_node_ptr head_type; + //@endcond + + public: + /// Guarded pointer + typedef typename base_class::guarded_ptr guarded_ptr; + + protected: + //@cond + template + class iterator_type: protected base_class::template iterator_type + { + typedef typename base_class::template iterator_type iterator_base; + friend class IterableList; + + iterator_type( head_type const& pNode ) + : iterator_base( pNode ) + {} + + iterator_type( iterator_base it ) + : iterator_base( it ) + {} + + public: + typedef typename iterator_base::value_ptr value_ptr; + typedef typename iterator_base::value_ref value_ref; + + iterator_type() + {} + + iterator_type( iterator_type const& src ) + : iterator_base( src ) + {} + + value_ptr operator ->() const + { + return iterator_base::operator ->(); + } + + value_ref operator *() const + { + return iterator_base::operator *(); + } + + /// Pre-increment + iterator_type& operator ++() + { + iterator_base::operator ++(); + return *this; + } + + template + bool operator ==(iterator_type const& i ) const + { + return iterator_base::operator ==(i); + } + template + bool operator !=(iterator_type const& i ) const + { + return iterator_base::operator !=(i); + } + }; + //@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: even if an 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( head() ); + } + + /// 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 \code begin() == end() \endcode + */ + iterator end() + { + return iterator(); + } + + /// Returns a forward const iterator addressing the first element in a list + const_iterator begin() const + { + return const_iterator( head() ); + } + + /// Returns a forward const iterator addressing the first element in a list + const_iterator cbegin() const + { + return const_iterator( head() ); + } + + /// 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 + /** + Initialize empty list + */ + IterableList() + {} + + //@cond + template >::value >> + explicit IterableList( Stat& st ) + : base_class( st ) + {} + //@endcond + + /// List destructor + /** + Clears the list + */ + ~IterableList() + {} + + /// Inserts new node + /** + The function creates a node with copy of \p val value + and then inserts the node created into the list. + + The type \p Q should contain least the complete key of the node. + The object of \ref value_type should be constructible from \p val of type \p Q. + In trivial case, \p Q is equal to \ref value_type. + + Returns \p true if inserting successful, \p false otherwise. + */ + template + bool insert( Q const& val ) + { + return insert_at( head(), val ); + } + + /// Inserts new node + /** + This function inserts new node with default-constructed value and then it calls + \p func functor with signature + \code + void func( value_type& data ); + \endcode + + The argument \p data of user-defined functor \p func is the reference + to the list's item inserted. User-defined functor \p func should guarantee that during changing + item's value no any other changes could be made on this list's item by concurrent threads. + The user-defined functor is called only if inserting is success. + + The type \p Q should contain the complete key of the node. + The object of \p value_type should be constructible from \p key of type \p Q. + + The function allows to split creating of new item into two part: + - create item from \p key with initializing key-fields only; + - insert new item into the list; + - if inserting is successful, initialize non-key fields of item by calling \p func functor + + The method can be useful if complete initialization of object of \p value_type is heavyweight and + it is preferable that the initialization should be completed only if inserting is successful. + + @warning See \ref cds_intrusive_item_creating "insert item troubleshooting" + */ + template + bool insert( Q const& key, Func func ) + { + return insert_at( head(), key, func ); + } + + /// Updates data by \p key + /** + The operation performs inserting or replacing the element with lock-free manner. + + If the \p key not found in the list, then the new item created from \p key + will be inserted iff \p bAllowInsert is \p true. + Otherwise, if \p key is found, the functor \p func is called with item found. + + 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 - 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. + + The functor may change non-key fields of \p val; however, \p func must guarantee + that during changing no any other modifications could be made on this item by concurrent threads. + + Returns std::pair where \p first is true if operation is successful, + \p second is true if new item has been added or \p false if the item with such \p key + already exists. + + @warning See \ref cds_intrusive_item_creating "insert item troubleshooting" + */ + template + std::pair update( Q const& key, Func func, bool bAllowInsert = true ) + { + return update_at( head(), key, func, bAllowInsert ); + } + + /// Insert or update + /** + The operation performs inserting or updating 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 old element will be retired later. + + 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 upsert( Q const& key, bool bInsert = true ) + { + return update_at( head(), key, []( value_type&, value_type* ) {}, bInsert ); + } + + /// Inserts data of type \p value_type constructed with std::forward(args)... + /** + Returns \p true if inserting successful, \p false otherwise. + */ + template + bool emplace( Args&&... args ) + { + return emplace_at( head(), std::forward(args)... ); + } + + /// Delete \p key from the list + /** + Since the key of IterableList's item type \p value_type is not explicitly specified, + template parameter \p Q sould contain the complete key to search in the list. + The list 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 + */ + template + bool erase( Q const& key ) + { + return erase_at( head(), key, key_comparator(), [](value_type const&){} ); + } + + /// Deletes the item from the list using \p pred predicate for searching + /** + 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 pred must imply the same element order as the comparator used for building the list. + */ + template + bool erase_with( Q const& key, Less pred ) + { + CDS_UNUSED( pred ); + return erase_at( head(), key, typename maker::template less_wrapper::type(), [](value_type const&){} ); + } + + /// Deletes \p key from the list + /** + The function searches an item with key \p key, calls \p f functor with item found + and deletes it. If \p key is not found, the functor is not called. + + The functor \p Func interface: + \code + struct extractor { + void operator()(const value_type& val) { ... } + }; + \endcode + + Since the key of IterableList's item type \p value_type is not explicitly specified, + template parameter \p Q should contain the complete key to search in the list. + The list item comparator should be able to compare the type \p value_type of list item + and the type \p Q. + + Return \p true if key is found and deleted, \p false otherwise + */ + template + bool erase( Q const& key, Func f ) + { + return erase_at( head(), key, key_comparator(), f ); + } + + /// Deletes the item from the list using \p pred predicate for searching + /** + 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 pred must imply the same element order as the comparator used for building the list. + */ + template + bool erase_with( Q const& key, Less pred, Func f ) + { + CDS_UNUSED( pred ); + return erase_at( head(), key, typename maker::template less_wrapper::type(), f ); + } + + /// Extracts the item from the list with specified \p key + /** + 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 the function 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. + + @note Each \p guarded_ptr object uses the GC's guard that can be limited resource. + + Usage: + \code + typedef cds::container::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 and frees the item + } + \endcode + */ + template + guarded_ptr extract( Q const& key ) + { + guarded_ptr gp; + extract_at( head(), gp.guard(), key, key_comparator() ); + return gp; + } + + /// Extracts the item from the list with comparing functor \p pred + /** + 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 it should accept 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 list. + */ + template + guarded_ptr extract_with( Q const& key, Less pred ) + { + CDS_UNUSED( pred ); + guarded_ptr gp; + extract_at( head(), gp.guard(), key, typename maker::template less_wrapper::type() ); + return gp; + } + + /// 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( head(), 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 pred 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( head(), key, typename maker::template less_wrapper::type() ); + } + + /// Finds \p key and perform an action with it + /** + The function searches an item with key equal to \p key and calls the functor \p f for the 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 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 deleted during functor is executing. + The function does not serialize simultaneous access to the list \p item. If such access is + possible you must provide your own synchronization schema to exclude unsafe item modifications. + + The function returns \p true if \p key is found, \p false otherwise. + */ + template + bool find( Q& key, Func f ) const + { + return find_at( head(), key, key_comparator(), f ); + } + //@cond + template + bool find( Q const& key, Func f ) const + { + return find_at( head(), 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( head(), key, key_comparator()); + } + //@cond + template + iterator find( Q const& key ) const + { + return find_iterator_at( head(), key, key_comparator() ); + } + //@endcond + + /// Finds \p key using \p pred predicate for searching + /** + 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 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( head(), key, typename maker::template less_wrapper::type(), f ); + } + //@cond + template + bool find_with( Q const& key, Less pred, Func f ) const + { + CDS_UNUSED( pred ); + return find_at( head(), key, typename maker::template less_wrapper::type(), 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( head(), 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( head(), key, cds::opt::details::make_comparator_from_less()); + } + //@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. + + @note Each \p guarded_ptr object uses one GC's guard which can be limited resource. + + Usage: + \code + typedef cds::container::MichaelList< 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 and frees the item + } + \endcode + + Note the compare functor specified for class \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( head(), gp.guard(), key, key_comparator() ); + return gp; + } + + /// Finds \p key and return the item found + /** + The function is an analog of \ref cds_nonintrusive_MichaelList_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 accept 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 list. + */ + template + guarded_ptr get_with( Q const& key, Less pred ) const + { + CDS_UNUSED( pred ); + guarded_ptr gp; + get_at( head(), gp.guard(), key, typename maker::template less_wrapper::type() ); + return gp; + } + + /// 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 base_class::empty(); + } + + /// Returns list's item count + /** + The value returned depends on item counter provided by \p Traits. For \p atomicity::empty_item_counter, + this function always returns 0. + */ + size_t size() const + { + return base_class::size(); + } + + /// Clears the list (thread safe, not atomic) + void clear() + { + base_class::clear(); + } + + /// Returns const reference to internal statistics + stat const& statistics() const + { + return base_class::statistics(); + } + + 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 ) + { + return cxx_data_allocator().MoveNew( std::forward(args)... ); + } + + static void free_data( value_type* pData ) + { + cxx_data_allocator().Delete( pData ); + } + + typedef std::unique_ptr< value_type, data_disposer > scoped_data_ptr; + + head_type& head() + { + return base_class::m_pHead; + } + + head_type const& head() const + { + return base_class::m_pHead; + } + //@endcond + + protected: + //@cond + bool insert_node( value_type * pData ) + { + return insert_node_at( head(), pData ); + } + + bool insert_node_at( head_type& refHead, value_type* pData ) + { + assert( pData ); + scoped_data_ptr p( pData ); + if ( base_class::insert_at( refHead, *pData )) { + p.release(); + return true; + } + + return false; + } + + template + bool insert_at( head_type& refHead, Q const& val ) + { + return insert_node_at( refHead, alloc_data( val )); + } + + template + bool insert_at( head_type& refHead, Q const& key, Func f ) + { + scoped_data_ptr pNode( alloc_data( key )); + + if ( base_class::insert_at( refHead, *pNode, f )) { + pNode.release(); + return true; + } + return false; + } + + template + bool emplace_at( head_type& refHead, Args&&... args ) + { + return insert_node_at( refHead, alloc_data( std::forward(args) ... )); + } + + template + std::pair update_at( head_type& refHead, Q const& key, Func f, bool bAllowInsert ) + { + scoped_data_ptr pData( alloc_data( key ) ); + + std::pair ret = base_class::update_at( refHead, *pData, f, bAllowInsert ); + if ( ret.first ) + pData.release(); + + return ret; + } + + template + bool erase_at( head_type& refHead, Q const& key, Compare cmp, Func f ) + { + return base_class::erase_at( refHead, key, cmp, f ); + } + + template + bool extract_at( head_type& refHead, typename guarded_ptr::native_guard& guard, Q const& key, Compare cmp ) + { + return base_class::extract_at( refHead, guard, key, cmp ); + } + + template + bool find_at( head_type const& refHead, Q const& key, Compare cmp ) const + { + return base_class::find_at( refHead, key, cmp ); + } + + template + bool find_at( head_type const& refHead, Q& val, Compare cmp, Func f ) const + { + return base_class::find_at( refHead, val, cmp, f ); + } + + template + iterator find_iterator_at( head_type const& refHead, Q const& key, Compare cmp ) const + { + return iterator( base_class::find_iterator_at( refHead, key, cmp )); + } + + template + bool get_at( head_type const& refHead, typename guarded_ptr::native_guard& guard, Q const& key, Compare cmp ) const + { + return base_class::get_at( refHead, guard, key, cmp ); + } + + //@endcond + }; + +}} // namespace cds::container + +#endif // #ifndef CDSLIB_CONTAINER_IMPL_ITERABLE_LIST_H diff --git a/cds/container/iterable_list_dhp.h b/cds/container/iterable_list_dhp.h new file mode 100644 index 00000000..134b665f --- /dev/null +++ b/cds/container/iterable_list_dhp.h @@ -0,0 +1,39 @@ +/* + 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_CONTAINER_ITERABLE_LIST_DHP_H +#define CDSLIB_CONTAINER_ITERABLE_LIST_DHP_H + +#include +#include +#include +#include + +#endif // #ifndef CDSLIB_CONTAINER_ITERABLE_LIST_DHP_H diff --git a/cds/container/iterable_list_hp.h b/cds/container/iterable_list_hp.h new file mode 100644 index 00000000..8912df34 --- /dev/null +++ b/cds/container/iterable_list_hp.h @@ -0,0 +1,39 @@ +/* + 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_CONTAINER_ITERABLE_LIST_HP_H +#define CDSLIB_CONTAINER_ITERABLE_LIST_HP_H + +#include +#include +#include +#include + +#endif // #ifndef CDSLIB_CONTAINER_ITERABLE_LIST_HP_H diff --git a/cds/intrusive/impl/iterable_list.h b/cds/intrusive/impl/iterable_list.h index 723b6b25..169496df 100644 --- a/cds/intrusive/impl/iterable_list.h +++ b/cds/intrusive/impl/iterable_list.h @@ -292,7 +292,7 @@ namespace cds { namespace intrusive { 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 + - Iterator is thread-safe: even 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: diff --git a/projects/Win/vc14/cds.vcxproj b/projects/Win/vc14/cds.vcxproj index e994ff6e..9b417352 100644 --- a/projects/Win/vc14/cds.vcxproj +++ b/projects/Win/vc14/cds.vcxproj @@ -414,7 +414,10 @@ + + + @@ -434,6 +437,7 @@ + @@ -442,6 +446,8 @@ + + diff --git a/projects/Win/vc14/cds.vcxproj.filters b/projects/Win/vc14/cds.vcxproj.filters index 73584fa3..411ea7a1 100644 --- a/projects/Win/vc14/cds.vcxproj.filters +++ b/projects/Win/vc14/cds.vcxproj.filters @@ -1256,5 +1256,23 @@ Header Files\cds\intrusive + + Header Files\cds\container\details + + + Header Files\cds\container\details + + + Header Files\cds\container\details + + + Header Files\cds\container\impl + + + Header Files\cds\container + + + Header Files\cds\container + \ No newline at end of file diff --git a/projects/Win/vc14/gtest-list.vcxproj b/projects/Win/vc14/gtest-list.vcxproj index bbd7b1c5..72ff8080 100644 --- a/projects/Win/vc14/gtest-list.vcxproj +++ b/projects/Win/vc14/gtest-list.vcxproj @@ -35,6 +35,8 @@ + + @@ -95,6 +97,8 @@ + + diff --git a/projects/Win/vc14/gtest-list.vcxproj.filters b/projects/Win/vc14/gtest-list.vcxproj.filters index 2b38fd61..de917e28 100644 --- a/projects/Win/vc14/gtest-list.vcxproj.filters +++ b/projects/Win/vc14/gtest-list.vcxproj.filters @@ -13,6 +13,15 @@ {67DA6AB6-F800-4c08-8B7A-83BB121AAD01} rc;ico;cur;bmp;dlg;rc2;rct;bin;rgs;gif;jpg;jpeg;jpe;resx;tiff;tif;png;wav;mfcribbon-ms + + {f6bc2494-0971-483b-98b2-7675d2aee7c9} + + + {b975977c-e055-46d0-95ea-bc94c66c6d50} + + + {edd852ff-4431-4c46-9592-dbbba4d9846e} + @@ -75,160 +84,172 @@ Header Files + + Header Files + + + Header Files + - - Source Files - Source Files - - Source Files + + Source Files\iterable_list - - Source Files + + Source Files\iterable_list - Source Files - - - Source Files - - - Source Files - - - Source Files - - - Source Files + Source Files\lazy_list - - Source Files - - - Source Files + + Source Files\lazy_list - - Source Files + + Source Files\lazy_list - Source Files + Source Files\lazy_list - Source Files + Source Files\lazy_list - Source Files + Source Files\lazy_list - Source Files + Source Files\lazy_list - Source Files + Source Files\lazy_list - - Source Files - - - Source Files + + Source Files\michael_list - - Source Files + + Source Files\michael_list - - Source Files + + Source Files\michael_list - - Source Files + + Source Files\michael_list - - Source Files + + Source Files\michael_list - - Source Files + + Source Files\michael_list - - Source Files + + Source Files\michael_list - - Source Files + + Source Files\michael_list - - Source Files + + Source Files\lazy_list - - Source Files + + Source Files\lazy_list - - Source Files + + Source Files\lazy_list - - Source Files + + Source Files\lazy_list - - Source Files + + Source Files\lazy_list - - Source Files + + Source Files\lazy_list - - Source Files + + Source Files\lazy_list - - Source Files + + Source Files\lazy_list - Source Files + Source Files\michael_list - - Source Files - - - Source Files + + Source Files\michael_list - Source Files - - - Source Files + Source Files\michael_list - Source Files + Source Files\michael_list - Source Files + Source Files\michael_list - Source Files + Source Files\michael_list - Source Files + Source Files\michael_list - Source Files + Source Files\michael_list - - Source Files + + Source Files\lazy_list - - Source Files + + Source Files\lazy_list - - Source Files + + Source Files\lazy_list - - Source Files + + Source Files\lazy_list - - Source Files + + Source Files\lazy_list - - Source Files + + Source Files\lazy_list - - Source Files + + Source Files\lazy_list + + + Source Files\lazy_list + + + Source Files\michael_list + + + Source Files\michael_list + + + Source Files\michael_list + + + Source Files\michael_list + + + Source Files\michael_list + + + Source Files\michael_list + + + Source Files\michael_list + + + Source Files\michael_list + + + Source Files\iterable_list + + + Source Files\iterable_list \ No newline at end of file diff --git a/test/unit/list/CMakeLists.txt b/test/unit/list/CMakeLists.txt index 407dd510..3f82d497 100644 --- a/test/unit/list/CMakeLists.txt +++ b/test/unit/list/CMakeLists.txt @@ -20,6 +20,8 @@ set(CDSGTEST_LIST_SOURCES intrusive_michael_rcu_gpt.cpp intrusive_michael_rcu_shb.cpp intrusive_michael_rcu_sht.cpp + iterable_hp.cpp + iterable_dhp.cpp kv_lazy_hp.cpp kv_lazy_dhp.cpp kv_lazy_nogc.cpp diff --git a/test/unit/list/iterable_dhp.cpp b/test/unit/list/iterable_dhp.cpp new file mode 100644 index 00000000..b008e92c --- /dev/null +++ b/test/unit/list/iterable_dhp.cpp @@ -0,0 +1,170 @@ +/* + 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_iterable_list_hp.h" +#include + +namespace { + namespace cc = cds::container; + typedef cds::gc::DHP gc_type; + + class IterableList_DHP : public cds_test::iterable_list_hp + { + protected: + void SetUp() + { + typedef cc::IterableList< gc_type, item > list_type; + + // +3 - for guarded_ptr, iterators + 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( IterableList_DHP, less_ordered ) + { + typedef cc::IterableList< gc_type, item, + typename cc::iterable_list::make_traits< + cds::opt::less< lt > + ,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( IterableList_DHP, compare_ordered ) + { + typedef cc::IterableList< gc_type, item, + typename cc::iterable_list::make_traits< + cds::opt::compare< cmp > + , 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( IterableList_DHP, mix_ordered ) + { + typedef cc::IterableList< gc_type, item, + typename cc::iterable_list::make_traits< + cds::opt::compare< cmp > + ,cds::opt::less< lt > + , 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( IterableList_DHP, backoff ) + { + struct traits : public cc::iterable_list::traits + { + typedef lt less; + typedef cds::atomicity::item_counter item_counter; + typedef cds::backoff::empty back_off; + }; + typedef cc::IterableList list_type; + + list_type l; + test_common( l ); + test_ordered_iterator( l ); + test_hp( l ); + } + + TEST_F( IterableList_DHP, seq_cst ) + { + struct traits : public cc::iterable_list::traits + { + typedef lt less; + typedef cds::atomicity::item_counter item_counter; + typedef cds::opt::v::sequential_consistent memory_model; + }; + typedef cc::IterableList list_type; + + list_type l; + test_common( l ); + test_ordered_iterator( l ); + test_hp( l ); + } + + TEST_F( IterableList_DHP, stat ) + { + struct traits: public cc::iterable_list::traits + { + typedef lt less; + typedef cds::atomicity::item_counter item_counter; + typedef cds::container::iterable_list::stat<> stat; + + }; + typedef cc::IterableList list_type; + + list_type l; + test_common( l ); + test_ordered_iterator( l ); + test_hp( l ); + } + + TEST_F( IterableList_DHP, wrapped_stat ) + { + struct traits: public cc::iterable_list::traits + { + typedef lt less; + typedef cds::atomicity::item_counter item_counter; + typedef cds::container::iterable_list::wrapped_stat<> stat; + + }; + typedef cc::IterableList list_type; + + cds::container::iterable_list::stat<> st; + list_type l( st ); + test_common( l ); + test_ordered_iterator( l ); + test_hp( l ); + } + +} // namespace diff --git a/test/unit/list/iterable_hp.cpp b/test/unit/list/iterable_hp.cpp new file mode 100644 index 00000000..b590344c --- /dev/null +++ b/test/unit/list/iterable_hp.cpp @@ -0,0 +1,170 @@ +/* + 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_iterable_list_hp.h" +#include + +namespace { + namespace cc = cds::container; + typedef cds::gc::HP gc_type; + + class IterableList_HP : public cds_test::iterable_list_hp + { + protected: + void SetUp() + { + typedef cc::IterableList< gc_type, item > list_type; + + // +3 - for guarded_ptr, iterators + 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( IterableList_HP, less_ordered ) + { + typedef cc::IterableList< gc_type, item, + typename cc::iterable_list::make_traits< + cds::opt::less< lt > + ,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( IterableList_HP, compare_ordered ) + { + typedef cc::IterableList< gc_type, item, + typename cc::iterable_list::make_traits< + cds::opt::compare< cmp > + , 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( IterableList_HP, mix_ordered ) + { + typedef cc::IterableList< gc_type, item, + typename cc::iterable_list::make_traits< + cds::opt::compare< cmp > + ,cds::opt::less< lt > + , 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( IterableList_HP, backoff ) + { + struct traits : public cc::iterable_list::traits + { + typedef lt less; + typedef cds::atomicity::item_counter item_counter; + typedef cds::backoff::empty back_off; + }; + typedef cc::IterableList list_type; + + list_type l; + test_common( l ); + test_ordered_iterator( l ); + test_hp( l ); + } + + TEST_F( IterableList_HP, seq_cst ) + { + struct traits : public cc::iterable_list::traits + { + typedef lt less; + typedef cds::atomicity::item_counter item_counter; + typedef cds::opt::v::sequential_consistent memory_model; + }; + typedef cc::IterableList list_type; + + list_type l; + test_common( l ); + test_ordered_iterator( l ); + test_hp( l ); + } + + TEST_F( IterableList_HP, stat ) + { + struct traits: public cc::iterable_list::traits + { + typedef lt less; + typedef cds::atomicity::item_counter item_counter; + typedef cds::container::iterable_list::stat<> stat; + + }; + typedef cc::IterableList list_type; + + list_type l; + test_common( l ); + test_ordered_iterator( l ); + test_hp( l ); + } + + TEST_F( IterableList_HP, wrapped_stat ) + { + struct traits: public cc::iterable_list::traits + { + typedef lt less; + typedef cds::atomicity::item_counter item_counter; + typedef cds::container::iterable_list::wrapped_stat<> stat; + + }; + typedef cc::IterableList list_type; + + cds::container::iterable_list::stat<> st; + list_type l( st ); + test_common( l ); + test_ordered_iterator( l ); + test_hp( l ); + } + +} // namespace diff --git a/test/unit/list/test_iterable_list.h b/test/unit/list/test_iterable_list.h new file mode 100644 index 00000000..40dbfe99 --- /dev/null +++ b/test/unit/list/test_iterable_list.h @@ -0,0 +1,405 @@ +/* + 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_ITERABLE_LIST_H +#define CDSUNIT_LIST_TEST_ITERABLE_LIST_H + +#include +#include + +namespace cds_test { + + class iterable_list_test : public fixture + { + public: + struct item { + int nKey; + int nVal; + + item() + {} + + item( int key ) + : nKey( key ) + , nVal( key * 2 ) + {} + + item( int key, int val ) + : nKey( key ) + , nVal( val ) + {} + + item( const item& v ) + : nKey( v.nKey ) + , nVal( v.nVal ) + {} + + int key() const + { + return nKey; + } + }; + + template + struct lt + { + 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(); + } + }; + + 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 other_item + { + int nKey; + + other_item() + {} + + other_item( int n ) + : nKey( n ) + {} + }; + + struct other_less + { + template + bool operator()( T1 const& t1, T2 const& t2 ) const + { + return t1.nKey < t2.nKey; + } + }; + + 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]; + + 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 ); + + // insert/find + for ( auto const& i : arr ) { + EXPECT_FALSE( l.contains( i )); + EXPECT_FALSE( l.contains( i.nKey )); + EXPECT_FALSE( l.contains( other_item( i.nKey ), other_less())); + EXPECT_TRUE( l.find( i ) == l.end()); + EXPECT_FALSE( l.find( i, []( value_type&, value_type const&) {} )); + EXPECT_FALSE( l.find( i.nKey, []( value_type&, int ) {} )); + EXPECT_FALSE( l.find_with( other_item( i.nKey ), other_less(), []( value_type&, other_item const& ) {} )); + EXPECT_TRUE( l.find_with( other_item( i.nKey ), other_less()) == l.end()); + + switch ( i.nKey % 5 ) { + case 0: + EXPECT_TRUE( l.insert( i.nKey )); + EXPECT_TRUE( l.find( i.nKey, []( value_type& n, int key ) { + EXPECT_EQ( n.nVal, key * 2 ); + } )); + EXPECT_FALSE( l.insert( i.nKey )); + break; + case 1: + EXPECT_TRUE( l.insert( i, []( value_type& n ) { + n.nVal = n.nKey * 3; + })); + EXPECT_TRUE( l.find( i.nKey, []( value_type& n, int key ) { + EXPECT_EQ( n.nVal, key * 3 ); + } )); + EXPECT_FALSE( l.insert( i )); + break; + case 2: + EXPECT_TRUE( l.emplace( i.nKey, i.nKey * 100 )); + EXPECT_TRUE( l.find( i.nKey, []( value_type& n, int key ) { + EXPECT_EQ( n.nVal, key * 100 ); + } )); + EXPECT_FALSE( l.insert( i )); + break; + case 3: + { + auto pair = l.update( i.nKey, []( value_type& n, value_type* old) { + EXPECT_TRUE( old == nullptr ); + n.nVal = n.nKey * 3; + }, false ); + EXPECT_FALSE( pair.first ); + EXPECT_FALSE( pair.second ); + + pair = l.update( i.nKey, []( value_type& n, value_type* old ) { + EXPECT_TRUE( old == nullptr ); + n.nVal = n.nKey * 3; + }); + EXPECT_TRUE( pair.first ); + EXPECT_TRUE( pair.second ); + + EXPECT_TRUE( l.find( i.nKey, []( value_type& n, int key ) { + EXPECT_EQ( n.nVal, key * 3 ); + } )); + EXPECT_FALSE( l.insert( i )); + } + break; + case 4: + { + auto pair = l.upsert( i.nKey, false ); + EXPECT_FALSE( pair.first ); + EXPECT_FALSE( pair.second ); + + pair = l.upsert( i.nKey ); + EXPECT_TRUE( pair.first ); + EXPECT_TRUE( pair.second ); + + EXPECT_TRUE( l.find( i.nKey, []( value_type& n, int key ) { + EXPECT_EQ( n.nVal, key * 2 ); + } )); + EXPECT_FALSE( l.insert( i )); + } + break; + } + + EXPECT_TRUE( l.contains( i )); + EXPECT_TRUE( l.contains( i.nKey )); + EXPECT_TRUE( l.contains( other_item( i.nKey ), other_less())); + EXPECT_TRUE( l.find( i, []( value_type& n, value_type const& arg ) { + EXPECT_EQ( arg.nKey, n.nKey ); + n.nVal = n.nKey; + } )); + EXPECT_TRUE( l.find( i.nKey, []( value_type& n, int key ) { + EXPECT_EQ( key, n.nKey ); + EXPECT_EQ( n.nKey, n.nVal ); + n.nVal = key * 5; + } )); + EXPECT_TRUE( l.find_with( other_item( i.nKey ), other_less(), []( value_type& n, other_item const& key ) { + EXPECT_EQ( key.nKey, n.nKey ); + EXPECT_EQ( n.nKey * 5, n.nVal ); + } )); + ASSERT_FALSE( l.find( i ) == l.end() ); + EXPECT_EQ( l.find( i.nKey )->nKey, i.nKey ); + ASSERT_FALSE( l.find_with( other_item( i.nKey ), other_less() ) == l.end() ); + EXPECT_EQ( l.find_with( other_item( i.nKey ), other_less() )->nKey, i.nKey ); + + auto pair = l.upsert( i.nKey, false ); + EXPECT_TRUE( pair.first ); + EXPECT_FALSE( pair.second ); + + pair = l.update( i.nKey, []( value_type& n, value_type* old ) { + ASSERT_FALSE( old == nullptr ); + EXPECT_EQ( old->nKey, n.nKey ); + EXPECT_EQ( old->nKey * 2, n.nVal ); + n.nVal = old->nKey * 3; + }, false ); + EXPECT_TRUE( pair.first ); + EXPECT_FALSE( pair.second ); + + EXPECT_FALSE( l.empty() ); + } + + ASSERT_FALSE( l.empty() ); + EXPECT_CONTAINER_SIZE( l, nSize ); + + // erase + for ( auto const&i : arr ) { + ASSERT_FALSE( l.find( i.nKey ) == l.end() ); + EXPECT_EQ( l.find( i.nKey )->nKey, i.nKey ); + ASSERT_FALSE( l.find_with( other_item( i.nKey ), other_less() ) == l.end() ); + EXPECT_EQ( l.find_with( other_item( i.nKey ), other_less() )->nKey, i.nKey ); + + switch ( i.nKey % 4 ) { + case 0: + EXPECT_TRUE( l.erase( i.nKey )); + break; + case 1: + EXPECT_TRUE( l.erase_with( other_item( i.nKey ), other_less())); + break; + case 2: + EXPECT_TRUE( l.erase( i, [ &i ]( value_type const& n ) { + EXPECT_EQ( n.nKey, i.nKey ); + EXPECT_EQ( n.nKey * 3, n.nVal ); + })); + break; + case 3: + EXPECT_TRUE( l.erase_with( other_item( i.nKey ), other_less(), [ &i ]( value_type const& n) { + EXPECT_EQ( n.nKey, i.nKey ); + EXPECT_EQ( n.nKey * 3, n.nVal ); + } )); + } + + EXPECT_FALSE( l.contains( i )); + EXPECT_FALSE( l.contains( i.nKey )); + EXPECT_FALSE( l.contains( other_item( i.nKey ), other_less())); + EXPECT_FALSE( l.find( i, []( value_type&, value_type const&) {} )); + EXPECT_FALSE( l.find( i.nKey, []( value_type&, int ) {} )); + EXPECT_FALSE( l.find_with( other_item( i.nKey ), other_less(), []( value_type&, other_item const& ) {} )); + EXPECT_TRUE( l.find( i ) == l.end() ); + EXPECT_TRUE( l.find( i.nKey ) == l.end() ); + EXPECT_TRUE( l.find_with( other_item( i.nKey ), other_less() ) == l.end() ); + } + + ASSERT_TRUE( l.empty() ); + EXPECT_CONTAINER_SIZE( l, 0 ); + + // clear test + for ( auto& i : arr ) + EXPECT_TRUE( l.insert( i )); + + ASSERT_FALSE( l.empty() ); + EXPECT_CONTAINER_SIZE( l, nSize ); + + l.clear(); + + ASSERT_TRUE( l.empty() ); + EXPECT_CONTAINER_SIZE( l, 0 ); + + // empty list iterator test + { + List const& cl = l; + EXPECT_TRUE( l.begin() == l.end()); + EXPECT_TRUE( l.cbegin() == l.cend()); + EXPECT_TRUE( cl.begin() == cl.end()); + EXPECT_TRUE( l.begin() == l.cend()); + EXPECT_TRUE( cl.begin() == l.end()); + } + } + + 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; + } + 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 ) { + EXPECT_EQ( key, it.nKey ); + EXPECT_EQ( it.nVal, it.nKey ); + it.nVal = it.nKey * 10; + ++key; + } + EXPECT_EQ( static_cast(key), nSize ); + + key = 0; + for ( auto it = l.cbegin(); it != l.cend(); ++it ) { + EXPECT_EQ( key, it->nKey ); + EXPECT_EQ( key, (*it).nKey ); + EXPECT_EQ( it->nKey * 10, it->nVal ); + ++key; + } + EXPECT_EQ( static_cast(key), nSize ); + + key = 0; + for ( auto it = l.begin(); it != l.end(); ++it ) { + EXPECT_EQ( key, it->nKey ); + EXPECT_EQ( key, (*it).nKey ); + EXPECT_EQ( it->nKey * 10, it->nVal ); + it->nVal = it->nKey * 2; + ++key; + } + EXPECT_EQ( static_cast(key), nSize ); + + List const& cl = l; + key = 0; + for ( auto it = cl.begin(); it != cl.end(); ++it ) { + EXPECT_EQ( key, it->nKey ); + EXPECT_EQ( key, (*it).nKey ); + EXPECT_EQ( it->nKey * 2, it->nVal ); + ++key; + } + EXPECT_EQ( static_cast(key), nSize ); + + l.clear(); + ASSERT_TRUE( l.empty() ); + EXPECT_CONTAINER_SIZE( l, 0 ); + } + }; + +} // namespace cds_test + +#endif // CDSUNIT_LIST_TEST_ITERABLE_LIST_H diff --git a/test/unit/list/test_iterable_list_hp.h b/test/unit/list/test_iterable_list_hp.h new file mode 100644 index 00000000..16451e3c --- /dev/null +++ b/test/unit/list/test_iterable_list_hp.h @@ -0,0 +1,136 @@ +/* + 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_ITERABLE_LIST_HP_H +#define CDSUNIT_LIST_TEST_ITERABLE_LIST_HP_H + +#include "test_iterable_list.h" + +namespace cds_test { + + class iterable_list_hp : public iterable_list_test + { + 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; + typedef typename List::guarded_ptr guarded_ptr; + 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 ); + + guarded_ptr gp; + size_t nCount = 0; + + // 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 ); + ASSERT_FALSE( !gp ); + EXPECT_EQ( gp->nKey, i.nKey ); + EXPECT_EQ( gp->nVal, gp->nKey * 10 ); + gp->nVal = gp->nKey * 5; + + gp = l.get_with( other_item( i.nKey ), other_less()); + ASSERT_FALSE( !gp ); + EXPECT_EQ( gp->nKey, i.nKey ); + EXPECT_EQ( gp->nVal, gp->nKey * 5 ); + gp->nVal = gp->nKey * 10; + + ++nCount; + ASSERT_FALSE( l.empty() ); + ASSERT_CONTAINER_SIZE( l, nCount ); + } + + ASSERT_FALSE( l.empty() ); + ASSERT_CONTAINER_SIZE( l, nSize ); + + // extract() test + for ( auto const& i : arr ) { + ASSERT_FALSE( l.empty() ); + ASSERT_CONTAINER_SIZE( l, nCount ); + --nCount; + + gp = l.get( i ); + ASSERT_FALSE( !gp ); + EXPECT_EQ( gp->nKey, i.nKey ); + + switch ( i.nKey & 3 ) { + case 0: + gp = l.extract( i ); + break; + case 1: + gp = l.extract_with( other_item( i.nKey ), other_less()); + break; + default: + gp = l.extract( i.nKey ); + break; + } + ASSERT_FALSE( !gp ); + EXPECT_EQ( gp->nKey, i.nKey ); + EXPECT_EQ( gp->nVal, gp->nKey * 10 ); + + gp = l.get( i.nKey ); + EXPECT_FALSE( gp ); + + gp = l.extract( i ); + EXPECT_FALSE( gp ); + gp = l.extract_with( other_item( i.nKey ), other_less()); + EXPECT_FALSE( gp ); + gp = l.extract( i.nKey ); + EXPECT_FALSE( gp ); + } + + ASSERT_TRUE( l.empty() ); + ASSERT_CONTAINER_SIZE( l, 0 ); + } + }; + +} // namespace cds_list + +#endif // CDSUNIT_LIST_TEST_ITERABLE_LIST_HP_H -- 2.34.1