From 0cb65c4791436f8d395809ec641a7d90f22baec5 Mon Sep 17 00:00:00 2001 From: khizmax Date: Sun, 13 Mar 2016 11:01:36 +0300 Subject: [PATCH] Added clear() to SplitList Doc fixed --- cds/intrusive/details/split_list_base.h | 3 +-- cds/intrusive/lazy_list_nogc.h | 19 +++++++++++++++++++ cds/intrusive/michael_list_nogc.h | 19 +++++++++++++++++++ cds/intrusive/michael_set.h | 1 - cds/intrusive/michael_set_nogc.h | 4 ++-- cds/intrusive/split_list.h | 3 +++ cds/intrusive/split_list_nogc.h | 25 ++++++++++++++++++++++++- 7 files changed, 68 insertions(+), 6 deletions(-) diff --git a/cds/intrusive/details/split_list_base.h b/cds/intrusive/details/split_list_base.h index 2259fe76..40b5f102 100644 --- a/cds/intrusive/details/split_list_base.h +++ b/cds/intrusive/details/split_list_base.h @@ -781,7 +781,7 @@ namespace cds { namespace intrusive { opt::compare< key_compare > ,opt::disposer< wrapped_disposer > ,opt::boundary_node_type< splitlist_node_type > - >::type result; + >::type result; }; template @@ -836,7 +836,6 @@ namespace cds { namespace intrusive { ++m_itCur; } - value_ptr operator ->() const { return m_itCur.operator->(); diff --git a/cds/intrusive/lazy_list_nogc.h b/cds/intrusive/lazy_list_nogc.h index c2434d22..cd31be7b 100644 --- a/cds/intrusive/lazy_list_nogc.h +++ b/cds/intrusive/lazy_list_nogc.h @@ -777,6 +777,25 @@ namespace cds { namespace intrusive { return pPred->m_pNext.load(memory_model::memory_order_acquire) == pCur; } + // for split-list + template + void erase_for( Predicate pred ) + { + node_type * pPred = nullptr; + node_type * pHead = m_Head.m_pNext.load( memory_model::memory_order_relaxed ); + + while ( pHead != &m_Tail ) { + node_type * p = pHead->m_pNext.load( memory_model::memory_order_relaxed ); + if ( pred( *node_traits::to_value_ptr( pHead ))) { + assert( pPred != nullptr ); + pPred->m_pNext.store( p, memory_model::memory_order_relaxed ); + dispose_node( pHead, disposer() ); + } + else + pPred = pHead; + pHead = p; + } + } //@endcond }; diff --git a/cds/intrusive/michael_list_nogc.h b/cds/intrusive/michael_list_nogc.h index 9a539b51..de48a4bf 100644 --- a/cds/intrusive/michael_list_nogc.h +++ b/cds/intrusive/michael_list_nogc.h @@ -666,6 +666,25 @@ namespace cds { namespace intrusive { pCur = pNext; } } + + // for split-list + template + void erase_for( Predicate pred ) + { + node_type * pPred = nullptr; + node_type * pHead = m_pHead.load( memory_model::memory_order_relaxed ); + while ( pHead ) { + node_type * p = pHead->m_pNext.load( memory_model::memory_order_relaxed ); + if ( pred( *node_traits::to_value_ptr( pHead ))) { + assert( pPred != nullptr ); + pPred->m_pNext.store( p, memory_model::memory_order_relaxed ); + dispose_node( pHead, disposer()); + } + else + pPred = pHead; + pHead = p; + } + } //@endcond }; diff --git a/cds/intrusive/michael_set.h b/cds/intrusive/michael_set.h index c91202ea..16cac8f9 100644 --- a/cds/intrusive/michael_set.h +++ b/cds/intrusive/michael_set.h @@ -267,7 +267,6 @@ namespace cds { namespace intrusive { /// Count of hazard pointer required for the algorithm static CDS_CONSTEXPR const size_t c_nHazardPtrCount = ordered_list::c_nHazardPtrCount; - protected: item_counter m_ItemCounter; ///< Item counter hash m_HashFunctor; ///< Hash functor diff --git a/cds/intrusive/michael_set_nogc.h b/cds/intrusive/michael_set_nogc.h index 9de82aae..65cdd4f4 100644 --- a/cds/intrusive/michael_set_nogc.h +++ b/cds/intrusive/michael_set_nogc.h @@ -356,9 +356,9 @@ namespace cds { namespace intrusive { /** The function unlink all items from the set. The function is not atomic. It cleans up each bucket and then resets the item counter to zero. - If there are a thread that performs insertion while \p clear is working the result is undefined in general case: + If there are a thread that performs insertion while \p %clear() is working the result is undefined in general case: empty() may return \p true but the set may contain item(s). - Therefore, \p clear may be used only for debugging purposes. + Therefore, \p %clear() may be used only for debugging purposes. For each item the \p disposer is called after unlinking. */ diff --git a/cds/intrusive/split_list.h b/cds/intrusive/split_list.h index 1316360f..2e461795 100644 --- a/cds/intrusive/split_list.h +++ b/cds/intrusive/split_list.h @@ -248,6 +248,9 @@ namespace cds { namespace intrusive { typedef typename traits::stat stat; ///< Internal statistics, see \p spit_list::stat typedef typename ordered_list::guarded_ptr guarded_ptr; ///< Guarded pointer + /// Count of hazard pointer required + static CDS_CONSTEXPR const size_t c_nHazardPtrCount = ordered_list::c_nHazardPtrCount + 4; // +4 - for iterators + protected: typedef typename ordered_list::node_type list_node_type; ///< Node type as declared in ordered list typedef split_list::node node_type; ///< split-list node type diff --git a/cds/intrusive/split_list_nogc.h b/cds/intrusive/split_list_nogc.h index 3784d5a8..b93ce400 100644 --- a/cds/intrusive/split_list_nogc.h +++ b/cds/intrusive/split_list_nogc.h @@ -119,7 +119,7 @@ namespace cds { namespace intrusive { class ordered_list_wrapper: public ordered_list { typedef ordered_list base_class; - typedef typename base_class::auxiliary_head bucket_head_type; + typedef typename base_class::auxiliary_head bucket_head_type; public: list_iterator insert_at_( dummy_node_type * pHead, value_type& val ) @@ -162,6 +162,12 @@ namespace cds { namespace intrusive { bucket_head_type h(static_cast(pHead)); return base_class::insert_aux_node( h, pNode ); } + + template + void erase_for( Predicate pred ) + { + return base_class::erase_for( pred ); + } }; //@endcond @@ -495,6 +501,23 @@ namespace cds { namespace intrusive { } //@endcond + + /// Clears the set (non-atomic, not thread-safe) + /** + The function unlink all items from the set. + The function is not atomic. It cleans up each bucket and then resets the item counter to zero. + If there are a thread that performs insertion while \p %clear() is working the result is undefined in general case: + empty() may return \p true but the set may contain item(s). + Therefore, \p %clear() may be used only for debugging purposes. + + For each item the \p disposer is called after unlinking. + */ + void clear() + { + m_List.erase_for( []( value_type const& val ) -> bool { return !node_traits::to_node_ptr( val )->is_dummy(); } ); + m_ItemCounter.reset(); + } + /// Checks if the set is empty /** Emptiness is checked by item counting: if item count is zero then the set is empty. -- 2.34.1