From 97f90e05d05de3e7772b950b7f4caadff5cdea7c Mon Sep 17 00:00:00 2001 From: khizmax Date: Sat, 19 Mar 2016 12:02:29 +0300 Subject: [PATCH] Fixed constness, improved doc --- cds/container/impl/skip_list_set.h | 48 +++++++++++++++++++++++++++++- cds/container/skip_list_set_nogc.h | 17 +++++++---- cds/container/skip_list_set_rcu.h | 23 ++++++++++---- 3 files changed, 76 insertions(+), 12 deletions(-) diff --git a/cds/container/impl/skip_list_set.h b/cds/container/impl/skip_list_set.h index 4b76d9cf..5534c7c5 100644 --- a/cds/container/impl/skip_list_set.h +++ b/cds/container/impl/skip_list_set.h @@ -152,6 +152,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; @@ -183,7 +185,50 @@ namespace cds { namespace container { {} public: + ///@name Forward iterators (only for debugging purpose) + //@{ /// Iterator type + /** + The forward iterator has some features: + - 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. + + 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 @@ -224,6 +269,7 @@ namespace cds { namespace container { { return const_iterator( base_class::cend() ); } + //@} public: /// Inserts new node @@ -578,7 +624,7 @@ namespace cds { namespace container { { CDS_UNUSED( pred ); return base_class::find_with( key, cds::details::predicate_wrapper< node_type, Less, typename maker::value_accessor >(), - [&f]( node_type& node, Q& v ) { f( node.m_Value, v ); } ); + [&f]( node_type& node, Q const& v ) { f( node.m_Value, v ); } ); } //@endcond diff --git a/cds/container/skip_list_set_nogc.h b/cds/container/skip_list_set_nogc.h index ca866b41..b337b12a 100644 --- a/cds/container/skip_list_set_nogc.h +++ b/cds/container/skip_list_set_nogc.h @@ -199,7 +199,14 @@ namespace cds { namespace container { //@endcond public: - /// Iterator type + ///@name Forward iterators + //@{ + /// Forward iterator + /** + 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 skip_list::details::iterator< typename base_class::iterator > iterator; /// Const iterator type @@ -212,16 +219,16 @@ namespace cds { namespace container { } /// Returns a forward const iterator addressing the first element in a set - //@{ const_iterator begin() const { return const_iterator( base_class::begin() ); } + + /// Returns a forward const iterator addressing the first element in a set const_iterator cbegin() const { return const_iterator( base_class::cbegin() ); } - //@} /// Returns a forward iterator that addresses the location succeeding the last element in a set. iterator end() @@ -230,16 +237,16 @@ namespace cds { namespace container { } /// Returns a forward const iterator that addresses the location succeeding the last element in a set. - //@{ const_iterator end() const { return const_iterator( base_class::end() ); } + /// Returns a forward const iterator that addresses the location succeeding the last element in a set. const_iterator cend() const { return const_iterator( base_class::cend() ); } - //@} + //@} protected: //@cond diff --git a/cds/container/skip_list_set_rcu.h b/cds/container/skip_list_set_rcu.h index 29fbb5ee..f3770e1e 100644 --- a/cds/container/skip_list_set_rcu.h +++ b/cds/container/skip_list_set_rcu.h @@ -259,7 +259,17 @@ namespace cds { namespace container { {} public: - /// Iterator type + ///@name Forward 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 @@ -272,16 +282,16 @@ namespace cds { namespace container { } /// Returns a forward const iterator addressing the first element in a set - //@{ const_iterator begin() const { return const_iterator( base_class::begin() ); } + + /// Returns a forward const iterator addressing the first element in a set const_iterator cbegin() const { return const_iterator( base_class::cbegin() ); } - //@} /// Returns a forward iterator that addresses the location succeeding the last element in a set. iterator end() @@ -290,16 +300,17 @@ namespace cds { namespace container { } /// Returns a forward const iterator that addresses the location succeeding the last element in a set. - //@{ const_iterator end() const { return const_iterator( base_class::end() ); } + + /// Returns a forward const iterator that addresses the location succeeding the last element in a set. const_iterator cend() const { return const_iterator( base_class::cend() ); } - //@} + //@} public: /// Inserts new node @@ -621,7 +632,7 @@ namespace cds { namespace container { { CDS_UNUSED( pred ); return base_class::find_with( val, cds::details::predicate_wrapper< node_type, Less, typename maker::value_accessor >(), - [&f]( node_type& node, Q& v ) { f( node.m_Value, v ); } ); + [&f]( node_type& node, Q const& v ) { f( node.m_Value, v ); } ); } //@endcond -- 2.34.1