From c61e9202490df1b91fedd51205ff05fe6449b401 Mon Sep 17 00:00:00 2001 From: khizmax Date: Mon, 1 Aug 2016 23:56:30 +0300 Subject: [PATCH] Added container::IterableKVList --- cds/container/details/make_iterable_kvlist.h | 51 +- cds/container/impl/iterable_kvlist.h | 746 +++++++++++++++++++ cds/container/impl/iterable_list.h | 15 +- cds/container/iterable_kvlist_dhp.h | 39 + cds/container/iterable_kvlist_hp.h | 39 + projects/Win/vc14/cds.vcxproj | 3 + projects/Win/vc14/cds.vcxproj.filters | 9 + projects/Win/vc14/gtest-list.vcxproj | 3 + projects/Win/vc14/gtest-list.vcxproj.filters | 9 + test/unit/list/CMakeLists.txt | 2 + test/unit/list/kv_iterable_hp.cpp | 180 +++++ test/unit/list/test_kv_iterable_list.h | 450 +++++++++++ test/unit/list/test_kv_iterable_list_hp.h | 138 ++++ 13 files changed, 1655 insertions(+), 29 deletions(-) create mode 100644 cds/container/impl/iterable_kvlist.h create mode 100644 cds/container/iterable_kvlist_dhp.h create mode 100644 cds/container/iterable_kvlist_hp.h create mode 100644 test/unit/list/kv_iterable_hp.cpp create mode 100644 test/unit/list/test_kv_iterable_list.h create mode 100644 test/unit/list/test_kv_iterable_list_hp.h diff --git a/cds/container/details/make_iterable_kvlist.h b/cds/container/details/make_iterable_kvlist.h index 811b917c..8ae93400 100644 --- a/cds/container/details/make_iterable_kvlist.h +++ b/cds/container/details/make_iterable_kvlist.h @@ -32,6 +32,7 @@ #define CDSLIB_CONTAINER_DETAILS_MAKE_ITERABLE_KVLIST_H #include +#include namespace cds { namespace container { @@ -45,48 +46,54 @@ namespace cds { namespace container { typedef GC gc; typedef K key_type; - typedef T value_type; - typedef std::pair pair_type; + typedef T mapped_type; + typedef std::pair value_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::allocator::template rebind::other data_allocator_type; + typedef cds::details::Allocator< value_type, data_allocator_type > cxx_data_allocator; typedef typename original_type_traits::memory_model memory_model; - struct node_disposer + struct data_disposer { - void operator ()( node_type * pNode ) + void operator ()( value_type * pData ) { - cxx_data_allocator().Delete( pNode->data.load( memory_model::memory_order_relaxed ) ); + cxx_data_allocator().Delete( pData ); } }; struct key_field_accessor { - key_type const& operator()( node_type const& node ) + key_type const& operator()( value_type const& data ) { - pair_type const* p = node.data.load( memory_model::memory_order_relaxed ); - assert( p != nullptr ) - return p->first; + return data.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 less_wrapper + { + template + bool operator()( value_type const& lhs, Q const& rhs ) const + { + return Less()( lhs.first, rhs ); + } + + template + bool operator()( Q const& lhs, value_type const& rhs ) const + { + return Less()( lhs, rhs.first ); + } }; - struct intrusive_traits: public original_type_traits + typedef typename opt::details::make_comparator< key_type, original_type_traits >::type key_comparator; + + struct base_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 data_disposer disposer; + typedef cds::details::compare_wrapper< value_type, key_comparator, key_field_accessor > compare; }; - typedef intrusive::IterableList type; + typedef container::IterableList type; }; } // namespace details //@endcond diff --git a/cds/container/impl/iterable_kvlist.h b/cds/container/impl/iterable_kvlist.h new file mode 100644 index 00000000..0cac4538 --- /dev/null +++ b/cds/container/impl/iterable_kvlist.h @@ -0,0 +1,746 @@ +/* + 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_KVLIST_H +#define CDSLIB_CONTAINER_IMPL_ITERABLE_KVLIST_H + +#include +#include + +namespace cds { namespace container { + + /// Iterable ordered list for key-value pair + /** @ingroup cds_nonintrusive_list + \anchor cds_nonintrusive_IterableKVList_gc + + This is key-value variation of non-intrusive \p IterableList. + Like standard container, this implementation split a value stored into two part - + constant key and alterable value. + + 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 Key - key type of an item stored in the list. It should be copy-constructible + - \p Value - value type stored in a list + - \p Traits - type traits, default is \p iterable_list::traits + + It is possible to declare option-based list with \p cds::container::iterable_list::make_traits metafunction instead of \p Traits template + argument. For example, the following traits-based declaration of \p 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::IterableKVList< cds::gc::HP, int, 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::IterableKVList< cds::gc::HP, int, 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 Key, + typename Value, +#ifdef CDS_DOXYGEN_INVOKED + typename Traits = iterable_list::traits +#else + typename Traits +#endif + > + class IterableKVList: +#ifdef CDS_DOXYGEN_INVOKED + protected container::IterableList< GC, std::pair, Traits > +#else + protected details::make_iterable_kvlist< GC, Key, Value, Traits >::type +#endif + { + //@cond + typedef details::make_iterable_kvlist< GC, Key, Value, Traits > maker; + typedef typename maker::type base_class; + //@endcond + + public: +#ifdef CDS_DOXYGEN_INVOKED + typedef Key key_type ; ///< Key type + typedef Value mapped_type ; ///< Type of value stored in the list + typedef std::pair value_type ; ///< key/value pair stored in the list +#else + typedef typename maker::key_type key_type; + typedef typename maker::mapped_type mapped_type; + typedef typename maker::value_type value_type; +#endif + + 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 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 + + /// Guarded pointer + typedef typename base_class::guarded_ptr guarded_ptr; + + protected: + //@cond + typedef typename base_class::head_type head_type; + typedef typename maker::cxx_data_allocator cxx_data_allocator; + + template + using less_wrapper = typename maker::less_wrapper< Less >; + + template + using iterator_type = typename base_class::template iterator_type; + //@endcond + + public: + /// 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 constructor + 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. + */ + using typename base_class::iterator; + using typename base_class::const_iterator; + using base_class::begin; + using base_class::end; + using base_class::cbegin; + using base_class::cend; + + public: + /// Default constructor + /** + Initializes empty list + */ + IterableKVList() + {} + + //@cond + template >::value >> + explicit IterableKVList( Stat& st ) + : base_class( st ) + {} + //@endcond + + /// List destructor + /** + Clears the list + */ + ~IterableKVList() + {} + + /// Inserts new node with key and default value + /** + The function creates a node with \p key and default value, and then inserts the node created into the list. + + Preconditions: + - The \p key_type should be constructible from value of type \p K. In trivial case, \p K is equal to \p key_type. + - The \p mapped_type should be default-constructible. + + Returns \p true if inserting successful, \p false otherwise. + + @note The function is supported only if \ref mapped_type is default constructible + */ + template +#ifdef CDS_DOXYGEN_INVOKED + bool +#else + typename std::enable_if< + std::is_same::value && std::is_default_constructible< mapped_type >::value, + bool + >::type +#endif + insert( K const& key ) + { + return base_class::emplace( key, mapped_type()); + } + + /// Inserts new node with a key and a value + /** + The function creates a node with \p key and value \p val, and then inserts the node created into the list. + + Preconditions: + - The \p key_type should be constructible from \p key of type \p K. + - The \p mapped_type should be constructible from \p val of type \p V. + + Returns \p true if inserting successful, \p false otherwise. + */ + template + bool insert( K const& key, V const& val ) + { + return base_class::emplace( key, val ); + } + + /// Inserts new node and initialize it by a functor + /** + This function inserts new node with key \p key and if inserting is successful then it calls + \p func functor with signature + \code + struct functor { + void operator()( value_type& item ); + }; + \endcode + + The argument \p item of user-defined functor \p func is the reference + to the item inserted. item.second is a reference to item's value that may be changed. + 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 successful. + + The \p key_type should be constructible from value of type \p K. + + The function allows to split creating of new item into two part: + - create a new item from \p key; + - insert the new item into the list; + - if inserting is successful, initialize the value of item by calling \p func functor + + This can be useful if complete initialization of object of \p mapped_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" + + @note The function is supported only if \ref mapped_type is default constructible + */ + template +#ifdef CDS_DOXYGEN_INVOKED + bool +#else + typename std::enable_if< + std::is_same::value && std::is_default_constructible< mapped_type >::value, + bool + >::type +#endif + insert_with( K const& key, Func func ) + { + return base_class::insert( value_type( key, mapped_type()), 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. + (note that in this case the \ref key_type should be constructible from type \p K). + Otherwise, if \p key is found, the functor \p func is called with item found. + + The functor \p func 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" + + @note The function is supported only if \ref mapped_type is default constructible + */ + template +#ifdef CDS_DOXYGEN_INVOKED + std::pair +#else + typename std::enable_if< + std::is_same::value && std::is_default_constructible< mapped_type >::value, + std::pair + >::type +#endif + update( K const& key, Func f, bool bAllowInsert = true ) + { + return base_class::update( key, f, bAllowInsert ); + } + + /// Insert or update + /** + The operation performs inserting or updating data with lock-free manner. + + If the item \p key is not found in the list, then \p key is inserted + iff \p bInsert is \p true. + Otherwise, the current element is changed to value_type( key, 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 key has been added or \p false if the item with that key + already in the list. + */ + template + std::pair upsert( Q&& key, V&& val, bool bInsert = true ) + { + return base_class::upsert( value_type( std::forward( key ), std::forward( val )), bInsert ); + } + + /// Inserts a new node using move semantics + /** + \p key_type field of new item is constructed from \p key argument, + \p mapped_type field is done from \p args. + + Returns \p true if inserting successful, \p false otherwise. + */ + template + bool emplace( K&& key, Args&&... args ) + { + return base_class::emplace( std::forward( key ), std::forward( args )... ); + } + + /// Deletes \p key from the list + /** + + Returns \p true if \p key is found and has been deleted, \p false otherwise + */ + template + bool erase( K const& key ) + { + return base_class::erase( key ); + } + + /// Deletes the item from the list using \p pred predicate for searching + /** + The function is an analog of \p erase(K 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( K const& key, Less pred ) + { + CDS_UNUSED( pred ); + return base_class::erase_with( key, less_wrapper() ); + } + + /// Deletes \p key from the list + /** + The function searches an item with key \p key, calls \p f functor + and deletes the item. If \p key is not found, the functor is not called. + + The functor \p Func interface: + \code + struct extractor { + void operator()(value_type& val) { ... } + }; + \endcode + + Return \p true if key is found and deleted, \p false otherwise + */ + template + bool erase( K const& key, Func f ) + { + return base_class::erase( key, f ); + } + + /// Deletes the item from the list using \p pred predicate for searching + /** + The function is an analog of \p erase(K 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( K const& key, Less pred, Func f ) + { + CDS_UNUSED( pred ); + return base_class::erase_with( key, less_wrapper(), 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 K that can be not the same as \p key_type. + + The \p disposer specified in \p Traits class template parameter is called automatically + by garbage collector \p GC specified in class' template parameters when returned \p guarded_ptr object + will be destroyed or released. + @note Each \p guarded_ptr object uses the GC's guard that can be limited resource. + + Usage: + \code + typedef cds::container::IterableKVList< cds::gc::HP, int, 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( K const& key ) + { + return base_class::extract( key ); + } + + /// Extracts the item from the list with comparing functor \p pred + /** + The function is an analog of \p extract(K 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 key_type and \p K + in any order. + \p pred must imply the same element order as the comparator used for building the list. + */ + template + guarded_ptr extract_with( K const& key, Less pred ) + { + CDS_UNUSED( pred ); + return base_class::extract_with( key, less_wrapper() ); + } + + /// 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 base_class::contains( key ); + } + + /// Checks whether the map 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 base_class::contains( key, less_wrapper() ); + } + + /// Finds the key \p key and performs 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 ); + }; + \endcode + where \p item is the item found. + + The functor may change item.second that is reference to value of node. + 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 const& key, Func f ) const + { + return base_class::find( key, [&f]( value_type& v, Q const& ) { f( v ); } ); + } + + /// 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 const& key ) const + { + return base_class::find( key ); + } + + /// Finds the key \p val 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 const& key, Less pred, Func f ) const + { + CDS_UNUSED( pred ); + return base_class::find_with( key, less_wrapper(), [&f]( value_type& v, Q const& ) { f( v ); } ); + } + + /// 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 base_class::find_with( key, less_wrapper()); + } + + /// Finds the \p key and return the item found + /** + 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::IterableKVList< cds::gc::HP, int, 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 class \p Traits template parameter + should accept a parameter of type \p K that can be not the same as \p key_type. + */ + template + guarded_ptr get( K const& key ) const + { + return base_class::get( key ); + } + + /// Finds the \p key and return the item found + /** + The function is an analog of \p get( guarded_ptr& ptr, K 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 key_type and \p K + in any order. + \p pred must imply the same element order as the comparator used for building the list. + */ + template + guarded_ptr get_with( K const& key, Less pred ) const + { + CDS_UNUSED( pred ); + return base_class::get_with( key, less_wrapper() ); + } + + /// 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 + void clear() + { + base_class::clear(); + } + + /// Returns const reference to internal statistics + stat const& statistics() const + { + return base_class::statistics(); + } + + protected: + //@cond + // Split-list support + + template + bool insert_at( head_type& refHead, const K& key ) + { + return base_class::insert_at( refHead, value_type( key, mapped_type() )); + } + + template + bool insert_at( head_type& refHead, const K& key, const V& val ) + { + return base_class::insert_at( refHead, value_type( key, val )); + } + + template + bool insert_with_at( head_type& refHead, const K& key, Func f ) + { + return base_class::insert_at( refHead, value_type( key, mapped_type()), f ); + } + + template + bool emplace_at( head_type& refHead, K&& key, Args&&... args ) + { + return base_class::emplace_at( refHead, std::forward(key), std::forward(args)... ); + } + + template + std::pair update_at( head_type& refHead, const K& key, Func f, bool bAllowInsert ) + { + return base_class::update_at( refHead, value_type( key, mapped_type()), f, bAllowInsert ); + } + + template + bool erase_at( head_type& refHead, K const& key, Compare cmp ) + { + return base_class::erase_at( refHead, key, cmp ); + } + + template + bool erase_at( head_type& refHead, K 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, K const& key, Compare cmp ) + { + return base_class::extract_at( refHead, guard, key, cmp ); + } + + template + bool find_at( head_type& refHead, K const& key, Compare cmp ) + { + return base_class::find_at( refHead, key, cmp ); + } + + template + bool find_at( head_type& refHead, K& key, Compare cmp, Func f ) + { + return base_class::find_at( refHead, key, cmp, f ); + } + + template + bool get_at( head_type& refHead, typename guarded_ptr::native_guard& guard, K const& key, Compare cmp ) + { + return base_class::get_at( refHead, guard, key, cmp ); + } + + //@endcond + }; + +}} // namespace cds::container + +#endif // #ifndef CDSLIB_CONTAINER_IMPL_ITERABLE_KVLIST_H diff --git a/cds/container/impl/iterable_list.h b/cds/container/impl/iterable_list.h index 2d38c7fe..83a02219 100644 --- a/cds/container/impl/iterable_list.h +++ b/cds/container/impl/iterable_list.h @@ -141,7 +141,6 @@ namespace cds { namespace container { 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; @@ -229,7 +228,7 @@ namespace cds { namespace container { // Default constructor iterator(); - // Copy construtor + // Copy constructor iterator( iterator const& src ); // Dereference operator @@ -421,18 +420,20 @@ namespace cds { namespace container { /** 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 + If the item \p key is not found in the list, then \p key is inserted iff \p bInsert is \p true. - Otherwise, the current element is changed to \p val, the old element will be retired later. + Otherwise, the current element is changed to \p key, the old element will be retired later. + + \p value_type should be constructible from \p key. 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 + \p second is \p true if \p key 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 ) + std::pair upsert( Q&& key, bool bInsert = true ) { - return update_at( head(), key, []( value_type&, value_type* ) {}, bInsert ); + return update_at( head(), std::forward( key ), []( value_type&, value_type* ) {}, bInsert ); } /// Inserts data of type \p value_type constructed with std::forward(args)... diff --git a/cds/container/iterable_kvlist_dhp.h b/cds/container/iterable_kvlist_dhp.h new file mode 100644 index 00000000..ce85a552 --- /dev/null +++ b/cds/container/iterable_kvlist_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_KVLIST_DHP_H +#define CDSLIB_CONTAINER_ITERABLE_KVLIST_DHP_H + +#include +#include +#include +#include + +#endif // #ifndef CDSLIB_CONTAINER_ITERABLE_KVLIST_DHP_H diff --git a/cds/container/iterable_kvlist_hp.h b/cds/container/iterable_kvlist_hp.h new file mode 100644 index 00000000..58ad3174 --- /dev/null +++ b/cds/container/iterable_kvlist_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_KVLIST_HP_H +#define CDSLIB_CONTAINER_ITERABLE_KVLIST_HP_H + +#include +#include +#include +#include + +#endif // #ifndef CDSLIB_CONTAINER_ITERABLE_KVLIST_HP_H diff --git a/projects/Win/vc14/cds.vcxproj b/projects/Win/vc14/cds.vcxproj index 9b417352..5fe27e3b 100644 --- a/projects/Win/vc14/cds.vcxproj +++ b/projects/Win/vc14/cds.vcxproj @@ -437,6 +437,7 @@ + @@ -446,6 +447,8 @@ + + diff --git a/projects/Win/vc14/cds.vcxproj.filters b/projects/Win/vc14/cds.vcxproj.filters index 411ea7a1..3ad7fee3 100644 --- a/projects/Win/vc14/cds.vcxproj.filters +++ b/projects/Win/vc14/cds.vcxproj.filters @@ -1274,5 +1274,14 @@ Header Files\cds\container + + 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 72ff8080..ab0dc161 100644 --- a/projects/Win/vc14/gtest-list.vcxproj +++ b/projects/Win/vc14/gtest-list.vcxproj @@ -37,6 +37,8 @@ + + @@ -99,6 +101,7 @@ + diff --git a/projects/Win/vc14/gtest-list.vcxproj.filters b/projects/Win/vc14/gtest-list.vcxproj.filters index de917e28..f9a551b6 100644 --- a/projects/Win/vc14/gtest-list.vcxproj.filters +++ b/projects/Win/vc14/gtest-list.vcxproj.filters @@ -90,6 +90,12 @@ Header Files + + Header Files + + + Header Files + @@ -251,5 +257,8 @@ 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 3f82d497..36d8dc53 100644 --- a/test/unit/list/CMakeLists.txt +++ b/test/unit/list/CMakeLists.txt @@ -22,6 +22,8 @@ set(CDSGTEST_LIST_SOURCES intrusive_michael_rcu_sht.cpp iterable_hp.cpp iterable_dhp.cpp + kv_iterable_hp.cpp + kv_iterable_dhp.cpp kv_lazy_hp.cpp kv_lazy_dhp.cpp kv_lazy_nogc.cpp diff --git a/test/unit/list/kv_iterable_hp.cpp b/test/unit/list/kv_iterable_hp.cpp new file mode 100644 index 00000000..cca1577f --- /dev/null +++ b/test/unit/list/kv_iterable_hp.cpp @@ -0,0 +1,180 @@ +/* + 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_kv_iterable_list_hp.h" +#include + +namespace { + namespace cc = cds::container; + typedef cds::gc::HP gc_type; + + class IterableKVList_HP : public cds_test::kv_iterable_list_hp + { + protected: + void SetUp() + { + typedef cc::IterableKVList< gc_type, key_type, value_type > 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( IterableKVList_HP, less_ordered ) + { + typedef cc::IterableKVList< gc_type, key_type, value_type, + typename cc::iterable_list::make_traits< + cds::opt::less< lt > + >::type + > list_type; + + list_type l; + test_common( l ); + test_ordered_iterator( l ); + test_hp( l ); + } + + TEST_F( IterableKVList_HP, compare_ordered ) + { + typedef cc::IterableKVList< gc_type, key_type, value_type, + typename cc::iterable_list::make_traits< + cds::opt::compare< cmp > + >::type + > list_type; + + list_type l; + test_common( l ); + test_ordered_iterator( l ); + test_hp( l ); + } + + TEST_F( IterableKVList_HP, mix_ordered ) + { + typedef cc::IterableKVList< gc_type, key_type, value_type, + typename cc::iterable_list::make_traits< + cds::opt::compare< cmp > + ,cds::opt::less< lt > + >::type + > list_type; + + list_type l; + test_common( l ); + test_ordered_iterator( l ); + test_hp( l ); + } + + TEST_F( IterableKVList_HP, item_counting ) + { + struct traits : public cc::iterable_list::traits + { + typedef lt less; + typedef cds::atomicity::item_counter item_counter; + }; + typedef cc::IterableKVList list_type; + + list_type l; + test_common( l ); + test_ordered_iterator( l ); + test_hp( l ); + } + + TEST_F( IterableKVList_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::IterableKVList list_type; + + list_type l; + test_common( l ); + test_ordered_iterator( l ); + test_hp( l ); + } + + TEST_F( IterableKVList_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::IterableKVList list_type; + + list_type l; + test_common( l ); + test_ordered_iterator( l ); + test_hp( l ); + } + + TEST_F( IterableKVList_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::IterableKVList list_type; + + list_type l; + test_common( l ); + test_ordered_iterator( l ); + test_hp( l ); + } + + TEST_F( IterableKVList_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::IterableKVList 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_kv_iterable_list.h b/test/unit/list/test_kv_iterable_list.h new file mode 100644 index 00000000..4bb57696 --- /dev/null +++ b/test/unit/list/test_kv_iterable_list.h @@ -0,0 +1,450 @@ +/* + 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_KV_ITERABLE_LIST_H +#define CDSUNIT_LIST_TEST_KV_ITERABLE_LIST_H + +#include +#include + +namespace cds_test { + + class kv_iterable_list : public fixture + { + public: + struct key_type { + int nKey; + + key_type() = delete; + explicit key_type( int n ) + : nKey( n ) + {} + + key_type( key_type const& s ) + : nKey( s.nKey ) + {} + + key_type( key_type&& s ) + : nKey( s.nKey ) + { + s.nKey = 0; + } + + int key() const + { + return nKey; + } + }; + + struct value_type { + int val; + + value_type() + : val( 0 ) + {} + + explicit value_type( int n ) + : val( n ) + {} + }; + + struct lt + { + bool operator()( key_type const& lhs, key_type const& rhs ) const + { + return lhs.key() < rhs.key(); + } + + bool operator()( key_type const& lhs, int rhs ) const + { + return lhs.key() < rhs; + } + + bool operator()( int lhs, key_type const& rhs ) const + { + return lhs < rhs.key(); + } + + template + bool operator ()( T const& v1, T const& v2 ) const + { + return v1.key() < v2.key(); + } + }; + + struct cmp + { + int operator()( key_type const& lhs, key_type const& rhs ) const + { + return lhs.key() - rhs.key(); + } + + int operator()( key_type const& lhs, int rhs ) const + { + return lhs.key() - rhs; + } + + int operator()( int lhs, key_type const& rhs ) const + { + return lhs - rhs.key(); + } + + template + int operator ()( T const& lhs, T const& rhs ) const + { + return lhs.key() - rhs.key(); + } + }; + + struct other_key + { + int nKey; + + other_key() + {} + + other_key( int n ) + : nKey( n ) + {} + + int key() const + { + return nKey; + } + }; + + struct other_less + { + template + bool operator()( T1 const& t1, T2 const& t2 ) const + { + return t1.key() < t2.key(); + } + }; + + protected: + template + void test_common( List& l ) + { + // Precondition: list is empty + // Postcondition: list is empty + + static const size_t nSize = 20; + typedef typename List::key_type list_key_type; + typedef typename List::mapped_type list_mapped_type; + typedef typename List::value_type list_value_type; + struct key_val { + int key; + int val; + }; + key_val arr[nSize]; + + for ( size_t i = 0; i < nSize; ++i ) { + arr[i].key = static_cast(i) + 1; + arr[i].val = arr[i].key * 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.key )); + EXPECT_FALSE( l.contains( key_type( i.key ))); + EXPECT_FALSE( l.contains( other_key( i.key ), other_less())); + EXPECT_FALSE( l.find( i.key, []( list_value_type& ) {} )); + EXPECT_FALSE( l.find( key_type( i.key ), []( list_value_type& ) {} )); + EXPECT_FALSE( l.find_with( other_key( i.key ), other_less(), []( list_value_type& ) {} )); + EXPECT_TRUE( l.find( i.key ) == l.end() ); + EXPECT_TRUE( l.find_with( other_key( i.key ), other_less()) == l.end()); + + switch ( i.key % 6 ) { + case 0: + EXPECT_TRUE( l.insert( i.key )); + EXPECT_TRUE( l.find( i.key, []( list_value_type& n ) { + EXPECT_EQ( n.second.val, 0 ); + } )); + EXPECT_FALSE( l.insert( i.key )); + break; + + case 1: + EXPECT_TRUE( l.insert( i.key, i.val )); + EXPECT_TRUE( l.find( key_type(i.key), []( list_value_type& n ) { + EXPECT_EQ( n.second.val, n.first.nKey * 10 ); + } )); + EXPECT_FALSE( l.insert( key_type( i.key ))); + break; + + case 2: + EXPECT_TRUE( l.insert_with( i.key, []( list_value_type& n ) { + n.second.val = n.first.nKey * 2; + })); + EXPECT_TRUE( l.find( i.key, []( list_value_type& n ) { + EXPECT_EQ( n.second.val, n.first.key() * 2 ); + } )); + EXPECT_FALSE( l.insert_with( i.key, []( list_value_type& n ) { + n.second.val = n.first.nKey * 3; + } )); + EXPECT_TRUE( l.find( i.key, []( list_value_type& n ) { + EXPECT_EQ( n.second.val, n.first.key() * 2 ); + } )); + break; + + case 3: + { + key_type k( i.key ); + EXPECT_TRUE( l.emplace( std::move(k), i.key * 100 )); + EXPECT_EQ( k.key(), 0 ); + EXPECT_TRUE( l.find( i.key, []( list_value_type& n ) { + EXPECT_EQ( n.second.val, n.first.nKey * 100 ); + } )); + k.nKey = i.key; + EXPECT_FALSE( l.emplace( std::move( k ), i.key )); + //EXPECT_EQ( k.key(), i.key ); // ??? + EXPECT_TRUE( l.find( i.key, []( list_value_type& n ) { + EXPECT_EQ( n.second.val, n.first.nKey * 100 ); + } )); + } + break; + + case 4: + { + auto pair = l.update( i.key, []( list_value_type& n, list_value_type* old ) { + ASSERT_TRUE( false ); + }, false ); + EXPECT_FALSE( pair.first ); + EXPECT_FALSE( pair.second ); + + pair = l.update( list_key_type(i.key), []( list_value_type& n, list_value_type* old ) { + EXPECT_TRUE( old == nullptr ); + n.second.val = n.first.nKey * 3; + }); + EXPECT_TRUE( pair.first ); + EXPECT_TRUE( pair.second ); + + EXPECT_TRUE( l.find( i.key, []( list_value_type& n ) { + EXPECT_EQ( n.second.val, n.first.key() * 3 ); + } )); + + pair = l.update( list_key_type(i.key), []( list_value_type& n, list_value_type* old ) { + EXPECT_FALSE( old == nullptr ); + n.second.val = n.first.nKey * 5; + }); + EXPECT_TRUE( pair.first ); + EXPECT_FALSE( pair.second ); + + EXPECT_TRUE( l.find( i.key, []( list_value_type& n ) { + EXPECT_EQ( n.second.val, n.first.key() * 5 ); + } )); + } + break; + case 5: + { + auto ret = l.upsert( i.key, i.val, false ); + EXPECT_FALSE( ret.first ); + EXPECT_FALSE( ret.second ); + EXPECT_FALSE( l.contains( i.key )); + + ret = l.upsert( i.key, i.val ); + EXPECT_TRUE( ret.first ); + EXPECT_TRUE( ret.second ); + EXPECT_TRUE( l.contains( i.key ) ); + + ret = l.upsert( i.key, i.val * 12 ); + EXPECT_TRUE( ret.first ); + EXPECT_FALSE( ret.second ); + EXPECT_TRUE( l.find( i.key, []( list_value_type& n ) { + EXPECT_EQ( n.second.val, n.first.key() * 12 ); + })); + } + break; + } + + EXPECT_TRUE( l.contains( i.key )); + EXPECT_TRUE( l.contains( list_key_type(i.key))); + EXPECT_TRUE( l.contains( other_key( i.key ), other_less())); + EXPECT_TRUE( l.find( i.key, []( list_value_type& n ) { + n.second.val = n.first.nKey; + } )); + EXPECT_TRUE( l.find( i.key, []( list_value_type& n ) { + EXPECT_EQ( n.first.nKey, n.second.val ); + n.second.val = n.first.nKey * 5; + } )); + EXPECT_TRUE( l.find_with( other_key( i.key ), other_less(), []( list_value_type& n ) { + EXPECT_EQ( n.first.nKey * 5, n.second.val ); + } )); + + auto pair = l.update( i.key, []( list_value_type& n, list_value_type* old ) { + EXPECT_FALSE( old == nullptr ); + EXPECT_EQ( n.first.nKey * 5, n.second.val ); + n.second.val = n.first.nKey * 3; + }, false ); + EXPECT_TRUE( pair.first ); + EXPECT_FALSE( pair.second ); + + EXPECT_FALSE( l.find( i.key ) == l.end() ); + EXPECT_EQ( l.find( i.key )->first.nKey, i.key ); + EXPECT_EQ( l.find( i.key )->second.val, i.key * 3 ); + EXPECT_FALSE( l.find_with( other_key( i.key ), other_less() ) == l.end() ); + EXPECT_EQ( l.find_with( other_key( i.key ), other_less())->first.nKey, i.key ); + EXPECT_EQ( l.find_with( other_key( i.key ), other_less())->second.val, i.key * 3 ); + + EXPECT_FALSE( l.empty() ); + } + + ASSERT_FALSE( l.empty() ); + EXPECT_CONTAINER_SIZE( l, nSize ); + + // erase + for ( auto const&i : arr ) { + switch ( i.key % 4 ) { + case 0: + EXPECT_TRUE( l.erase( i.key )); + break; + case 1: + EXPECT_TRUE( l.erase_with( other_key( i.key ), other_less())); + break; + case 2: + EXPECT_TRUE( l.erase( i.key, [ &i ]( list_value_type const& n ) { + EXPECT_EQ( n.first.nKey, i.key ); + EXPECT_EQ( n.first.nKey * 3, n.second.val ); + })); + break; + case 3: + EXPECT_TRUE( l.erase_with( other_key( i.key ), other_less(), [ &i ]( list_value_type const& n) { + EXPECT_EQ( n.first.nKey, i.key ); + EXPECT_EQ( n.first.nKey * 3, n.second.val ); + } )); + } + + EXPECT_FALSE( l.contains( i.key )); + EXPECT_FALSE( l.contains( key_type( i.key ))); + EXPECT_FALSE( l.contains( other_key( i.key ), other_less())); + EXPECT_FALSE( l.find( key_type( i.key ), []( list_value_type& ) {} )); + EXPECT_FALSE( l.find( i.key, []( list_value_type& ) {} )); + EXPECT_FALSE( l.find_with( other_key( i.key ), other_less(), []( list_value_type& ) {} )); + } + + ASSERT_TRUE( l.empty() ); + EXPECT_CONTAINER_SIZE( l, 0 ); + + // clear test + for ( auto& i : arr ) + EXPECT_TRUE( l.insert( i.key, i.val )); + + 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; + struct key_val { + int key; + int val; + }; + key_val arr[nSize]; + + for ( size_t i = 0; i < nSize; ++i ) { + arr[i].key = static_cast(i); + arr[i].val = arr[i].key; + } + shuffle( arr, arr + nSize ); + + ASSERT_TRUE( l.empty() ); + ASSERT_CONTAINER_SIZE( l, 0 ); + + for ( auto& i : arr ) + EXPECT_TRUE( l.insert( i.key, i.val )); + + int key = 0; + for ( auto& it : l ) { + EXPECT_EQ( key, it.first.key() ); + EXPECT_EQ( it.second.val, it.first.key() ); + it.second.val = it.first.key() * 10; + ++key; + } + EXPECT_EQ( static_cast(key), nSize ); + + key = 0; + for ( auto it = l.cbegin(); it != l.cend(); ++it ) { + EXPECT_EQ( key, it->first.key() ); + EXPECT_EQ( it->first.key() * 10, it->second.val ); + ++key; + } + EXPECT_EQ( static_cast(key), nSize ); + + key = 0; + for ( auto it = l.begin(); it != l.end(); ++it ) { + EXPECT_EQ( key, it->first.key() ); + EXPECT_EQ( it->first.key() * 10, it->second.val ); + it->second.val = it->first.key() * 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->first.nKey ); + EXPECT_EQ( it->first.nKey * 2, it->second.val ); + ++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_KV_ITERABLE_LIST_H diff --git a/test/unit/list/test_kv_iterable_list_hp.h b/test/unit/list/test_kv_iterable_list_hp.h new file mode 100644 index 00000000..e7a6b57f --- /dev/null +++ b/test/unit/list/test_kv_iterable_list_hp.h @@ -0,0 +1,138 @@ +/* + 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_KV_ITERABLE_LIST_HP_H +#define CDSUNIT_LIST_TEST_KV_ITERABLE_LIST_HP_H + +#include "test_kv_iterable_list.h" + +namespace cds_test { + + class kv_iterable_list_hp : public kv_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::key_type list_key_type; + typedef typename List::mapped_type list_mapped_type; + typedef typename List::value_type list_value_type; + typedef typename List::guarded_ptr guarded_ptr; + + struct key_val { + int key; + int val; + }; + key_val arr[nSize]; + + for ( size_t i = 0; i < nSize; ++i ) { + arr[i].key = static_cast(i); + arr[i].val = arr[i].key * 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.key ); + EXPECT_TRUE( !gp ); + gp = l.get_with( other_key( i.key ), other_less()); + EXPECT_TRUE( !gp ); + + EXPECT_TRUE( l.insert( i.key, i.val )); + + gp = l.get( i.key ); + ASSERT_FALSE( !gp ); + EXPECT_EQ( gp->first.nKey, i.key ); + EXPECT_EQ( gp->second.val, gp->first.nKey * 10 ); + gp->second.val = gp->first.nKey * 5; + + gp = l.get_with( other_key( i.key ), other_less()); + ASSERT_FALSE( !gp ); + EXPECT_EQ( gp->first.nKey, i.key ); + EXPECT_EQ( gp->second.val, gp->first.nKey * 5 ); + gp->second.val = gp->first.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.key ); + ASSERT_FALSE( !gp ); + EXPECT_EQ( gp->first.nKey, i.key ); + + switch ( i.key & 1 ) { + case 0: + gp = l.extract( i.key ); + break; + case 1: + gp = l.extract_with( other_key( i.key ), other_less()); + break; + } + ASSERT_FALSE( !gp ); + EXPECT_EQ( gp->first.nKey, i.key ); + EXPECT_EQ( gp->second.val, gp->first.nKey * 10 ); + + gp = l.get( i.key ); + EXPECT_FALSE( gp ); + + gp = l.extract( i.key ); + EXPECT_FALSE( gp ); + gp = l.extract_with( other_key( i.key ), other_less()); + EXPECT_FALSE( gp ); + } + + ASSERT_TRUE( l.empty() ); + ASSERT_CONTAINER_SIZE( l, 0 ); + } + }; + +} // namespace cds_list + +#endif // CDSUNIT_LIST_TEST_KV_ITERABLE_LIST_HP_H -- 2.34.1