From 3d5cdd21e9cfd781f269ae3b47271b4cb08f39a3 Mon Sep 17 00:00:00 2001 From: khizmax Date: Sat, 2 Apr 2016 19:03:02 +0300 Subject: [PATCH] Fixed some bugs related to type conversion Docfix --- cds/container/details/make_skip_list_map.h | 4 +- cds/container/impl/skip_list_map.h | 99 ++++++++++++---------- cds/container/skip_list_map_nogc.h | 18 ++-- cds/container/skip_list_map_rcu.h | 13 ++- cds/container/skip_list_set_nogc.h | 2 +- cds/container/skip_list_set_rcu.h | 2 +- 6 files changed, 82 insertions(+), 56 deletions(-) diff --git a/cds/container/details/make_skip_list_map.h b/cds/container/details/make_skip_list_map.h index e6377e7a..a55de3b9 100644 --- a/cds/container/details/make_skip_list_map.h +++ b/cds/container/details/make_skip_list_map.h @@ -96,7 +96,7 @@ namespace cds { namespace container { namespace details { template node_type * New( unsigned int nHeight, Q const& key ) { - return base_class::New( nHeight, key ); + return base_class::New( nHeight, key_type( key )); } template node_type * New( unsigned int nHeight, Q const& key, U const& val ) @@ -105,7 +105,7 @@ namespace cds { namespace container { namespace details { return new( pMem ) node_type( nHeight, nHeight > 1 ? reinterpret_cast( pMem + base_class::c_nNodeSize ) : nullptr, - key, val + key_type( key ), mapped_type( val ) ); } template diff --git a/cds/container/impl/skip_list_map.h b/cds/container/impl/skip_list_map.h index 5e8653d5..b0fa8577 100644 --- a/cds/container/impl/skip_list_map.h +++ b/cds/container/impl/skip_list_map.h @@ -79,48 +79,6 @@ namespace cds { namespace container { - for \p gc::DHP garbage collector - for \ref cds_nonintrusive_SkipListMap_rcu "RCU type" - for \ref cds_nonintrusive_SkipListMap_nogc "non-deletable SkipListMap" - - Iterators - - The class supports a forward iterator (\ref iterator and \ref const_iterator). - The iteration is ordered. - The iterator object is thread-safe: the element pointed by the iterator object is guarded, - so, the element cannot be reclaimed while the iterator object is alive. - However, passing an iterator object between threads is dangerous. - - \warning Due to concurrent nature of skip-list map it is not guarantee that you can iterate - all elements in the map: any concurrent deletion can exclude the element - pointed by the iterator from the map, and your iteration can be terminated - before end of the map. Therefore, such iteration is more suitable for debugging purpose only - - Remember, each iterator object requires 2 additional hazard pointers, that may be - a limited resource for \p GC like \p gc::HP (for gc::DHP the count of - guards is unlimited). - - The iterator class supports the following minimalistic interface: - \code - struct iterator { - // Default ctor - iterator(); - - // Copy ctor - iterator( iterator const& s); - - value_type * operator ->() const; - value_type& operator *() const; - - // Pre-increment - iterator& operator ++(); - - // Copy assignment - iterator& operator = (const iterator& src); - - bool operator ==(iterator const& i ) const; - bool operator !=(iterator const& i ) const; - }; - \endcode - Note, the iterator object returned by \ref end, \ cend member functions points to \p nullptr and should not be dereferenced. - */ template < typename GC, @@ -162,6 +120,8 @@ namespace cds { namespace container { typedef typename traits::random_level_generator random_level_generator ; ///< random level generator typedef typename traits::stat stat; ///< internal statistics type + static size_t const c_nHazardPtrCount = base_class::c_nHazardPtrCount; ///< Count of hazard pointer required for the skip-list + protected: //@cond typedef typename maker::node_type node_type; @@ -193,11 +153,57 @@ namespace cds { namespace container { {} public: + ///@name Forward iterators (only for debugging purpose) + //@{ /// Iterator type + /** + The forward iterator has some features: + - it is ordered + - it has no post-increment operator + - to protect the value, the iterator contains a GC-specific guard + another guard is required locally for increment operator. + For some GC (like as \p gc::HP), a guard is a limited resource per thread, so an exception (or assertion) "no free guard" + may be thrown if the limit of guard count per thread is exceeded. + - The iterator cannot be moved across thread boundary because it contains thread-private GC's guard. + - Iterator ensures thread-safety even if you delete the item the iterator points to. However, in case of concurrent + deleting operations there is no guarantee that you iterate all item in the list. + Moreover, a crash is possible when you try to iterate the next element that has been deleted by concurrent thread. + + @warning Use this iterator on the concurrent container for debugging purpose only. + + @note \p end() and \p cend() are not dereferenceable. + + 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 + */ typedef skip_list::details::iterator< typename base_class::iterator > iterator; - /// Const iterator type - typedef skip_list::details::iterator< typename base_class::const_iterator > const_iterator; + /// Const forward iterator type + typedef skip_list::details::iterator< typename base_class::const_iterator > const_iterator; /// Returns a forward iterator addressing the first element in a map iterator begin() @@ -210,6 +216,7 @@ namespace cds { namespace container { { return cbegin(); } + /// Returns a forward const iterator addressing the first element in a map const_iterator cbegin() const { @@ -227,11 +234,13 @@ namespace cds { namespace container { { return cend(); } + /// Returns a forward const iterator that addresses the location succeeding the last element in a map. const_iterator cend() const { return const_iterator( base_class::cend() ); } + //@} public: /// Inserts new node with key and default value @@ -265,7 +274,7 @@ namespace cds { namespace container { template bool insert( K const& key, V const& val ) { - return insert_with( key, [&val](value_type& item) { item.second = val ; } ); + return insert_with( key, [&val]( value_type& item ) { item.second = val; } ); } /// Inserts new node and initialize it by a functor diff --git a/cds/container/skip_list_map_nogc.h b/cds/container/skip_list_map_nogc.h index df625a17..2171c650 100644 --- a/cds/container/skip_list_map_nogc.h +++ b/cds/container/skip_list_map_nogc.h @@ -122,10 +122,13 @@ namespace cds { namespace container { {} public: + ///@name Forward ordered iterators + //@{ /// Forward iterator /** - Remember, the iterator operator -> and operator * returns \ref value_type pointer and reference. - To access item key and value use it->first and it->second respectively. + The forward iterator for a split-list has some features: + - it has no post-increment operator + - it depends on iterator of underlying \p OrderedList */ typedef typename base_class::iterator iterator; @@ -157,6 +160,7 @@ namespace cds { namespace container { { return base_class::begin(); } + /// Returns a forward const iterator addressing the first element in a map const_iterator cbegin() const { @@ -168,11 +172,13 @@ namespace cds { namespace container { { return base_class::end(); } + /// Returns an const iterator that addresses the location succeeding the last element in a map const_iterator cend() const { return base_class::cend(); } + //@} public: /// Inserts new node with key and default value @@ -190,7 +196,7 @@ namespace cds { namespace container { iterator insert( K const& key ) { //TODO: pass arguments by reference (make_pair makes copy) - return base_class::insert( std::make_pair( key, mapped_type() ) ); + return base_class::insert( std::make_pair( key_type( key ), mapped_type() ) ); } /// Inserts new node @@ -208,7 +214,7 @@ namespace cds { namespace container { iterator insert( K const& key, V const& val ) { //TODO: pass arguments by reference (make_pair makes copy) - return base_class::insert( std::make_pair( key, val ) ); + return base_class::insert( std::make_pair( key_type( key ), mapped_type( val ))); } /// Inserts new node and initialize it by a functor @@ -256,7 +262,7 @@ namespace cds { namespace container { template iterator emplace( K&& key, Args&&... args ) { - return base_class::emplace( std::forward(key), std::move(mapped_type(std::forward(args)...))); + return base_class::emplace( key_type( std::forward( key )), mapped_type( std::forward(args)... )); } /// UPdates data by \p key @@ -272,7 +278,7 @@ namespace cds { namespace container { std::pair update( K const& key, bool bInsert = true ) { //TODO: pass arguments by reference (make_pair makes copy) - return base_class::update( std::make_pair( key, mapped_type() ), bInsert ); + return base_class::update( std::make_pair( key_type( key ), mapped_type() ), bInsert ); } //@cond template diff --git a/cds/container/skip_list_map_rcu.h b/cds/container/skip_list_map_rcu.h index 5bd9a8a0..64217a90 100644 --- a/cds/container/skip_list_map_rcu.h +++ b/cds/container/skip_list_map_rcu.h @@ -212,7 +212,17 @@ namespace cds { namespace container { {} public: - /// Iterator type + ///@name Forward ordered iterators (thread-safe under RCU lock) + //@{ + /// Forward iterator + /** + The forward iterator has some features: + - it has no post-increment operator + - it depends on iterator of underlying \p OrderedList + + You may safely use iterators in multi-threaded environment only under RCU lock. + Otherwise, a crash is possible if another thread deletes the element the iterator points to. + */ typedef skip_list::details::iterator< typename base_class::iterator > iterator; /// Const iterator type @@ -251,6 +261,7 @@ namespace cds { namespace container { { return const_iterator( base_class::cend() ); } + //@} public: /// Inserts new node with key and default value diff --git a/cds/container/skip_list_set_nogc.h b/cds/container/skip_list_set_nogc.h index b337b12a..4f89d653 100644 --- a/cds/container/skip_list_set_nogc.h +++ b/cds/container/skip_list_set_nogc.h @@ -201,7 +201,7 @@ namespace cds { namespace container { public: ///@name Forward iterators //@{ - /// Forward iterator + /// Forward ordered iterator /** The forward iterator for a split-list has some features: - it has no post-increment operator diff --git a/cds/container/skip_list_set_rcu.h b/cds/container/skip_list_set_rcu.h index f3770e1e..7d3f45ee 100644 --- a/cds/container/skip_list_set_rcu.h +++ b/cds/container/skip_list_set_rcu.h @@ -259,7 +259,7 @@ namespace cds { namespace container { {} public: - ///@name Forward iterators (thread-safe under RCU lock) + ///@name Forward ordered iterators (thread-safe under RCU lock) //@{ /// Forward iterator /** -- 2.34.1