From 7a70599883226459c97174848a1f53b307631eb7 Mon Sep 17 00:00:00 2001 From: khizmax Date: Sat, 20 Aug 2016 23:13:56 +0300 Subject: [PATCH] HP refactoring: - added move semantics support to guards for reducing HP count - added move semantics for container's method returning guarded_ptr - fixed some minor bugs --- cds/algo/split_bitstring.h | 4 +- cds/container/impl/ellen_bintree_map.h | 30 +- cds/container/impl/ellen_bintree_set.h | 26 +- cds/container/impl/feldman_hashmap.h | 18 +- cds/container/impl/feldman_hashset.h | 2 +- cds/container/impl/iterable_kvlist.h | 8 +- cds/container/impl/iterable_list.h | 24 +- cds/container/impl/lazy_kvlist.h | 24 +- cds/container/impl/lazy_list.h | 24 +- cds/container/impl/michael_kvlist.h | 24 +- cds/container/impl/michael_list.h | 24 +- cds/container/impl/skip_list_map.h | 26 +- cds/container/impl/skip_list_set.h | 26 +- cds/container/split_list_map.h | 18 +- cds/container/split_list_set.h | 26 +- cds/gc/details/dhp.h | 308 ++++-------------- cds/gc/details/hp.h | 112 +------ cds/gc/details/hp_alloc.h | 192 ++++++----- cds/gc/details/hp_type.h | 2 +- cds/gc/hp.h | 2 +- cds/gc/impl/dhp_decl.h | 271 ++++++++++----- cds/gc/impl/dhp_impl.h | 64 ++-- cds/gc/impl/hp_decl.h | 265 ++++++++++----- cds/gc/impl/hp_impl.h | 95 +++--- cds/intrusive/details/feldman_hashset_base.h | 6 +- cds/intrusive/ellen_bintree_dhp.h | 2 +- cds/intrusive/ellen_bintree_hp.h | 2 +- cds/intrusive/impl/ellen_bintree.h | 132 +++++--- cds/intrusive/impl/feldman_hashset.h | 26 +- cds/intrusive/impl/iterable_list.h | 33 +- cds/intrusive/impl/lazy_list.h | 33 +- cds/intrusive/impl/michael_list.h | 30 +- cds/intrusive/impl/skip_list.h | 66 ++-- cds/intrusive/split_list.h | 57 ++-- .../Win/vc14/stress-set-insdelfind.vcxproj | 12 +- src/dhp_gc.cpp | 96 +++--- src/hp_const.h | 7 +- src/hp_gc.cpp | 6 +- test/unit/list/test_intrusive_iterable_list.h | 3 + test/unit/set/test_feldman_hashset.h | 2 +- test/unit/set/test_feldman_hashset_hp.h | 2 +- 41 files changed, 1033 insertions(+), 1097 deletions(-) diff --git a/cds/algo/split_bitstring.h b/cds/algo/split_bitstring.h index 54407c90..2d499681 100644 --- a/cds/algo/split_bitstring.h +++ b/cds/algo/split_bitstring.h @@ -25,7 +25,7 @@ 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. + OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. */ #ifndef CDSLIB_ALGO_SPLIT_BITSTRING_H @@ -44,7 +44,7 @@ namespace cds { namespace algo { The splitter stores a const reference to bit-string, not a copy. The maximum count of bits that can be cut in a single call is sizeof(UInt) * 8 */ - template + template ::type > class split_bitstring { public: diff --git a/cds/container/impl/ellen_bintree_map.h b/cds/container/impl/ellen_bintree_map.h index a5b9855b..5c2d5b62 100644 --- a/cds/container/impl/ellen_bintree_map.h +++ b/cds/container/impl/ellen_bintree_map.h @@ -25,7 +25,7 @@ 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. + OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. */ #ifndef CDSLIB_CONTAINER_IMPL_ELLEN_BINTREE_MAP_H @@ -370,9 +370,7 @@ namespace cds { namespace container { */ guarded_ptr extract_min() { - guarded_ptr gp; - base_class::extract_min_( gp.guard() ); - return gp; + return guarded_ptr( base_class::extract_min_()); } /// Extracts an item with maximal key from the map @@ -391,9 +389,7 @@ namespace cds { namespace container { */ guarded_ptr extract_max() { - guarded_ptr gp; - base_class::extract_max_( gp.guard() ); - return gp; + return guarded_ptr( base_class::extract_max_()); } /// Extracts an item from the tree @@ -409,9 +405,7 @@ namespace cds { namespace container { template guarded_ptr extract( Q const& key ) { - guarded_ptr gp; - base_class::extract_( gp.guard(), key ); - return gp; + return guarded_ptr( base_class::extract_( key )); } /// Extracts an item from the map using \p pred for searching @@ -425,10 +419,8 @@ namespace cds { namespace container { guarded_ptr extract_with( Q const& key, Less pred ) { CDS_UNUSED( pred ); - guarded_ptr gp; - base_class::extract_with_( gp.guard(), key, - cds::details::predicate_wrapper< leaf_node, Less, typename maker::key_accessor >()); - return gp; + return guarded_ptr( base_class::extract_with_( key, + cds::details::predicate_wrapper< leaf_node, Less, typename maker::key_accessor >())); } /// Find the key \p key @@ -520,9 +512,7 @@ namespace cds { namespace container { template guarded_ptr get( Q const& key ) { - guarded_ptr gp; - base_class::get_( gp.guard(), key ); - return gp; + return guarded_ptr( base_class::get_( key )); } /// Finds \p key with predicate \p pred and returns the item found @@ -536,10 +526,8 @@ namespace cds { namespace container { guarded_ptr get_with( Q const& key, Less pred ) { CDS_UNUSED( pred ); - guarded_ptr gp; - base_class::get_with_( gp.guard(), key, - cds::details::predicate_wrapper< leaf_node, Less, typename maker::key_accessor >() ); - return gp; + return guarded_ptr( base_class::get_with_( key, + cds::details::predicate_wrapper< leaf_node, Less, typename maker::key_accessor >() )); } /// Clears the map (not atomic) diff --git a/cds/container/impl/ellen_bintree_set.h b/cds/container/impl/ellen_bintree_set.h index 2e00f54d..a8631e8d 100644 --- a/cds/container/impl/ellen_bintree_set.h +++ b/cds/container/impl/ellen_bintree_set.h @@ -25,7 +25,7 @@ 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. + OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. */ #ifndef CDSLIB_CONTAINER_IMPL_ELLEN_BINTREE_SET_H @@ -383,9 +383,7 @@ namespace cds { namespace container { */ guarded_ptr extract_min() { - guarded_ptr gp; - base_class::extract_min_( gp.guard() ); - return gp; + return guarded_ptr( base_class::extract_min_()); } /// Extracts an item with maximal key from the set @@ -404,9 +402,7 @@ namespace cds { namespace container { */ guarded_ptr extract_max() { - guarded_ptr gp; - base_class::extract_max_( gp.guard() ); - return gp; + return guarded_ptr( base_class::extract_max_()); } /// Extracts an item from the tree @@ -422,9 +418,7 @@ namespace cds { namespace container { template guarded_ptr extract( Q const& key ) { - guarded_ptr gp; - base_class::extract_( gp.guard(), key ); - return gp; + return base_class::extract_( key ); } /// Extracts an item from the set using \p pred for searching @@ -438,10 +432,8 @@ namespace cds { namespace container { guarded_ptr extract_with( Q const& key, Less pred ) { CDS_UNUSED( pred ); - guarded_ptr gp; - base_class::extract_with_( gp.guard(), key, + return base_class::extract_with_( key, cds::details::predicate_wrapper< leaf_node, Less, typename maker::value_accessor >()); - return gp; } /// Find the key \p key @@ -559,9 +551,7 @@ namespace cds { namespace container { template guarded_ptr get( Q const& key ) { - guarded_ptr gp; - base_class::get_( gp.guard(), key ); - return gp; + return base_class::get_( key ); } /// Finds \p key with predicate \p pred and returns the item found @@ -575,10 +565,8 @@ namespace cds { namespace container { guarded_ptr get_with( Q const& key, Less pred ) { CDS_UNUSED(pred); - guarded_ptr gp; - base_class::get_with_( gp.guard(), key, + return base_class::get_with_( key, cds::details::predicate_wrapper< leaf_node, Less, typename maker::value_accessor >() ); - return gp; } /// Clears the set (not atomic) diff --git a/cds/container/impl/feldman_hashmap.h b/cds/container/impl/feldman_hashmap.h index 60d73cf2..9c90e89b 100644 --- a/cds/container/impl/feldman_hashmap.h +++ b/cds/container/impl/feldman_hashmap.h @@ -25,7 +25,7 @@ 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. + OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. */ #ifndef CDSLIB_CONTAINER_IMPL_FELDMAN_HASHMAP_H @@ -592,14 +592,7 @@ namespace cds { namespace container { template guarded_ptr extract( K const& key ) { - guarded_ptr gp; - typename gc::Guard guard; - node_type * p = base_class::do_erase( m_Hasher( key_type( key )), guard, []( node_type const&) -> bool {return true;} ); - - // p is guarded by HP - if ( p ) - gp.reset( p ); - return gp; + return base_class::extract( m_Hasher( key_type( key ))); } /// Checks whether the map contains \p key @@ -665,12 +658,7 @@ namespace cds { namespace container { template guarded_ptr get( K const& key ) { - guarded_ptr gp; - { - typename gc::Guard guard; - gp.reset( base_class::search( m_Hasher( key_type( key )), guard )); - } - return gp; + return base_class::get( m_Hasher( key_type( key ))); } /// Clears the map (non-atomic) diff --git a/cds/container/impl/feldman_hashset.h b/cds/container/impl/feldman_hashset.h index ee48d472..d90a6a34 100644 --- a/cds/container/impl/feldman_hashset.h +++ b/cds/container/impl/feldman_hashset.h @@ -25,7 +25,7 @@ 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. + OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. */ #ifndef CDSLIB_CONTAINER_IMPL_FELDMAN_HASHSET_H diff --git a/cds/container/impl/iterable_kvlist.h b/cds/container/impl/iterable_kvlist.h index 55cc3583..92ec7728 100644 --- a/cds/container/impl/iterable_kvlist.h +++ b/cds/container/impl/iterable_kvlist.h @@ -691,9 +691,9 @@ namespace cds { namespace container { 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 ) + guarded_ptr extract_at( head_type& refHead, K const& key, Compare cmp ) { - return base_class::extract_at( refHead, guard, key, cmp ); + return base_class::extract_at( refHead, key, cmp ); } template @@ -709,9 +709,9 @@ namespace cds { namespace container { } template - bool get_at( head_type& refHead, typename guarded_ptr::native_guard& guard, K const& key, Compare cmp ) + guarded_ptr get_at( head_type& refHead, K const& key, Compare cmp ) { - return base_class::get_at( refHead, guard, key, cmp ); + return base_class::get_at( refHead, key, cmp ); } //@endcond diff --git a/cds/container/impl/iterable_list.h b/cds/container/impl/iterable_list.h index 228e96ac..e32f8945 100644 --- a/cds/container/impl/iterable_list.h +++ b/cds/container/impl/iterable_list.h @@ -556,9 +556,7 @@ namespace cds { namespace container { template guarded_ptr extract( Q const& key ) { - guarded_ptr gp; - extract_at( head(), gp.guard(), key, key_comparator() ); - return gp; + return extract_at( head(), key, key_comparator() ); } /// Extracts the item from the list with comparing functor \p pred @@ -573,9 +571,7 @@ namespace cds { namespace container { 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; + return extract_at( head(), key, typename maker::template less_wrapper::type() ); } /// Checks whether the list contains \p key @@ -708,9 +704,7 @@ namespace cds { namespace container { template guarded_ptr get( Q const& key ) const { - guarded_ptr gp; - get_at( head(), gp.guard(), key, key_comparator() ); - return gp; + return get_at( head(), key, key_comparator() ); } /// Finds \p key and return the item found @@ -726,9 +720,7 @@ namespace cds { namespace container { 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; + return get_at( head(), key, typename maker::template less_wrapper::type() ); } /// Checks if the list is empty @@ -852,9 +844,9 @@ namespace cds { namespace container { } template - bool extract_at( head_type& refHead, typename guarded_ptr::native_guard& guard, Q const& key, Compare cmp ) + guarded_ptr extract_at( head_type& refHead, Q const& key, Compare cmp ) { - return base_class::extract_at( refHead, guard, key, cmp ); + return base_class::extract_at( refHead, key, cmp ); } template @@ -876,9 +868,9 @@ namespace cds { namespace container { } template - bool get_at( head_type const& refHead, typename guarded_ptr::native_guard& guard, Q const& key, Compare cmp ) const + guarded_ptr get_at( head_type const& refHead, Q const& key, Compare cmp ) const { - return base_class::get_at( refHead, guard, key, cmp ); + return base_class::get_at( refHead, key, cmp ); } //@endcond diff --git a/cds/container/impl/lazy_kvlist.h b/cds/container/impl/lazy_kvlist.h index 59947bb9..5b6599c3 100644 --- a/cds/container/impl/lazy_kvlist.h +++ b/cds/container/impl/lazy_kvlist.h @@ -589,9 +589,7 @@ namespace cds { namespace container { template guarded_ptr extract( K const& key ) { - guarded_ptr gp; - extract_at( head(), gp.guard(), key, intrusive_key_comparator() ); - return gp; + return extract_at( head(), key, intrusive_key_comparator() ); } /// Extracts the item from the list with comparing functor \p pred @@ -607,9 +605,7 @@ namespace cds { namespace container { guarded_ptr extract_with( K const& key, Less pred ) { CDS_UNUSED( pred ); - guarded_ptr gp; - extract_at( head(), gp.guard(), key, typename maker::template less_wrapper::type() ); - return gp; + return extract_at( head(), key, typename maker::template less_wrapper::type() ); } /// Checks whether the list contains \p key @@ -719,9 +715,7 @@ namespace cds { namespace container { template guarded_ptr get( K const& key ) { - guarded_ptr gp; - get_at( head(), gp.guard(), key, intrusive_key_comparator() ); - return gp; + return get_at( head(), key, intrusive_key_comparator() ); } /// Finds the key \p val and return the item found @@ -737,9 +731,7 @@ namespace cds { namespace container { guarded_ptr get_with( K const& key, Less pred ) { CDS_UNUSED( pred ); - guarded_ptr gp; - get_at( head(), gp.guard(), key, typename maker::template less_wrapper::type() ); - return gp; + return get_at( head(), key, typename maker::template less_wrapper::type() ); } /// Checks if the list is empty @@ -831,9 +823,9 @@ namespace cds { namespace container { } template - bool extract_at( head_type& refHead, typename guarded_ptr::native_guard& guard, K const& key, Compare cmp ) + guarded_ptr extract_at( head_type& refHead, K const& key, Compare cmp ) { - return base_class::extract_at( &refHead, guard, key, cmp ); + return base_class::extract_at( &refHead, key, cmp ); } template @@ -863,9 +855,9 @@ namespace cds { namespace container { } template - bool get_at( head_type& refHead, typename guarded_ptr::native_guard& guard, K const& key, Compare cmp ) + guarded_ptr get_at( head_type& refHead, K const& key, Compare cmp ) { - return base_class::get_at( &refHead, guard, key, cmp ); + return base_class::get_at( &refHead, key, cmp ); } //@endcond diff --git a/cds/container/impl/lazy_list.h b/cds/container/impl/lazy_list.h index 496f1b56..0a1615ec 100644 --- a/cds/container/impl/lazy_list.h +++ b/cds/container/impl/lazy_list.h @@ -532,9 +532,7 @@ namespace cds { namespace container { template guarded_ptr extract( Q const& key ) { - guarded_ptr gp; - extract_at( head(), gp.guard(), key, intrusive_key_comparator() ); - return gp; + return extract_at( head(), key, intrusive_key_comparator() ); } /// Extracts the item from the list with comparing functor \p pred @@ -550,9 +548,7 @@ namespace cds { namespace container { 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; + return extract_at( head(), key, typename maker::template less_wrapper::type() ); } /// Checks whether the list contains \p key @@ -679,9 +675,7 @@ namespace cds { namespace container { template guarded_ptr get( Q const& key ) { - guarded_ptr gp; - get_at( head(), gp.guard(), key, intrusive_key_comparator() ); - return gp; + return get_at( head(), key, intrusive_key_comparator() ); } /// Finds the key \p key and return the item found @@ -697,9 +691,7 @@ namespace cds { namespace container { guarded_ptr get_with( Q const& key, Less pred ) { CDS_UNUSED( pred ); - guarded_ptr gp; - get_at( head(), gp.guard(), key, typename maker::template less_wrapper::type() ); - return gp; + return get_at( head(), key, typename maker::template less_wrapper::type() ); } /// Checks whether the list is empty @@ -831,9 +823,9 @@ namespace cds { namespace container { } template - bool extract_at( head_type& refHead, typename guarded_ptr::native_guard& guard, Q const& key, Compare cmp ) + guarded_ptr extract_at( head_type& refHead, Q const& key, Compare cmp ) { - return base_class::extract_at( &refHead, guard, key, cmp ); + return base_class::extract_at( &refHead, key, cmp ); } template @@ -863,9 +855,9 @@ namespace cds { namespace container { } template - bool get_at( head_type& refHead, typename guarded_ptr::native_guard& guard, Q const& key, Compare cmp ) + guarded_ptr get_at( head_type& refHead, Q const& key, Compare cmp ) { - return base_class::get_at( &refHead, guard, key, cmp ); + return base_class::get_at( &refHead, key, cmp ); } //@endcond diff --git a/cds/container/impl/michael_kvlist.h b/cds/container/impl/michael_kvlist.h index 4a5ba37c..12a23426 100644 --- a/cds/container/impl/michael_kvlist.h +++ b/cds/container/impl/michael_kvlist.h @@ -592,9 +592,7 @@ namespace cds { namespace container { template guarded_ptr extract( K const& key ) { - guarded_ptr gp; - extract_at( head(), gp.guard(), key, intrusive_key_comparator() ); - return gp; + return extract_at( head(), key, intrusive_key_comparator() ); } /// Extracts the item from the list with comparing functor \p pred @@ -610,9 +608,7 @@ namespace cds { namespace container { guarded_ptr extract_with( K const& key, Less pred ) { CDS_UNUSED( pred ); - guarded_ptr gp; - extract_at( head(), gp.guard(), key, typename maker::template less_wrapper::type() ); - return gp; + return extract_at( head(), key, typename maker::template less_wrapper::type() ); } /// Checks whether the list contains \p key @@ -723,9 +719,7 @@ namespace cds { namespace container { template guarded_ptr get( K const& key ) { - guarded_ptr gp; - get_at( head(), gp.guard(), key, intrusive_key_comparator() ); - return gp; + return get_at( head(), key, intrusive_key_comparator() ); } /// Finds the \p key and return the item found @@ -741,9 +735,7 @@ namespace cds { namespace container { guarded_ptr get_with( K const& key, Less pred ) { CDS_UNUSED( pred ); - guarded_ptr gp; - get_at( head(), gp.guard(), key, typename maker::template less_wrapper::type() ); - return gp; + return get_at( head(), key, typename maker::template less_wrapper::type() ); } /// Checks if the list is empty @@ -846,9 +838,9 @@ namespace cds { namespace container { return base_class::erase_at( refHead, key, cmp, [&f]( node_type const & node ){ f( const_cast(node.m_Data)); }); } template - bool extract_at( head_type& refHead, typename guarded_ptr::native_guard& guard, K const& key, Compare cmp ) + guarded_ptr extract_at( head_type& refHead, K const& key, Compare cmp ) { - return base_class::extract_at( refHead, guard, key, cmp ); + return base_class::extract_at( refHead, key, cmp ); } template @@ -864,9 +856,9 @@ namespace cds { namespace container { } template - bool get_at( head_type& refHead, typename guarded_ptr::native_guard& guard, K const& key, Compare cmp ) + guarded_ptr get_at( head_type& refHead, K const& key, Compare cmp ) { - return base_class::get_at( refHead, guard, key, cmp ); + return base_class::get_at( refHead, key, cmp ); } //@endcond diff --git a/cds/container/impl/michael_list.h b/cds/container/impl/michael_list.h index 97e438a5..d631e2de 100644 --- a/cds/container/impl/michael_list.h +++ b/cds/container/impl/michael_list.h @@ -525,9 +525,7 @@ namespace cds { namespace container { template guarded_ptr extract( Q const& key ) { - guarded_ptr gp; - extract_at( head(), gp.guard(), key, intrusive_key_comparator() ); - return gp; + return extract_at( head(), key, intrusive_key_comparator() ); } /// Extracts the item from the list with comparing functor \p pred @@ -543,9 +541,7 @@ namespace cds { namespace container { 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; + return extract_at( head(), key, typename maker::template less_wrapper::type() ); } /// Checks whether the list contains \p key @@ -670,9 +666,7 @@ namespace cds { namespace container { template guarded_ptr get( Q const& key ) { - guarded_ptr gp; - get_at( head(), gp.guard(), key, intrusive_key_comparator() ); - return gp; + return get_at( head(), key, intrusive_key_comparator() ); } /// Finds \p key and return the item found @@ -688,9 +682,7 @@ namespace cds { namespace container { guarded_ptr get_with( Q const& key, Less pred ) { CDS_UNUSED( pred ); - guarded_ptr gp; - get_at( head(), gp.guard(), key, typename maker::template less_wrapper::type() ); - return gp; + return get_at( head(), key, typename maker::template less_wrapper::type() ); } /// Check if the list is empty @@ -810,9 +802,9 @@ namespace cds { namespace container { } template - bool extract_at( head_type& refHead, typename guarded_ptr::native_guard& guard, Q const& key, Compare cmp ) + guarded_ptr extract_at( head_type& refHead, Q const& key, Compare cmp ) { - return base_class::extract_at( refHead, guard, key, cmp ); + return base_class::extract_at( refHead, key, cmp ); } template @@ -842,9 +834,9 @@ namespace cds { namespace container { } template - bool get_at( head_type& refHead, typename guarded_ptr::native_guard& guard, Q const& key, Compare cmp ) + guarded_ptr get_at( head_type& refHead, Q const& key, Compare cmp ) { - return base_class::get_at( refHead, guard, key, cmp ); + return base_class::get_at( refHead, key, cmp ); } //@endcond diff --git a/cds/container/impl/skip_list_map.h b/cds/container/impl/skip_list_map.h index aedf7213..74b98e4a 100644 --- a/cds/container/impl/skip_list_map.h +++ b/cds/container/impl/skip_list_map.h @@ -25,7 +25,7 @@ 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. + OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. */ #ifndef CDSLIB_CONTAINER_IMPL_SKIP_LIST_MAP_H @@ -466,9 +466,7 @@ namespace cds { namespace container { template guarded_ptr extract( K const& key ) { - guarded_ptr gp; - base_class::extract_( gp.guard(), key, typename base_class::key_comparator() ); - return gp; + return base_class::extract_( key, typename base_class::key_comparator() ); } /// Extracts the item from the map with comparing functor \p pred @@ -485,9 +483,7 @@ namespace cds { namespace container { { CDS_UNUSED( pred ); typedef cds::details::predicate_wrapper< node_type, Less, typename maker::key_accessor > wrapped_less; - guarded_ptr gp; - base_class::extract_( gp.guard(), key, cds::opt::details::make_comparator_from_less() ); - return gp; + return base_class::extract_( key, cds::opt::details::make_comparator_from_less() ); } /// Extracts an item with minimal key from the map @@ -516,9 +512,7 @@ namespace cds { namespace container { */ guarded_ptr extract_min() { - guarded_ptr gp; - base_class::extract_min_( gp.guard() ); - return gp; + return base_class::extract_min_(); } /// Extracts an item with maximal key from the map @@ -547,9 +541,7 @@ namespace cds { namespace container { */ guarded_ptr extract_max() { - guarded_ptr gp; - base_class::extract_max_( gp.guard() ); - return gp; + return base_class::extract_max_(); } /// Find the key \p key @@ -662,9 +654,7 @@ namespace cds { namespace container { template guarded_ptr get( K const& key ) { - guarded_ptr gp; - base_class::get_with_( gp.guard(), key, typename base_class::key_comparator() ); - return gp; + return base_class::get_with_( key, typename base_class::key_comparator() ); } /// Finds the key \p key and return the item found @@ -681,9 +671,7 @@ namespace cds { namespace container { { CDS_UNUSED( pred ); typedef cds::details::predicate_wrapper< node_type, Less, typename maker::key_accessor > wrapped_less; - guarded_ptr gp; - base_class::get_with_( gp.guard(), key, cds::opt::details::make_comparator_from_less< wrapped_less >()); - return gp; + return base_class::get_with_( key, cds::opt::details::make_comparator_from_less< wrapped_less >()); } /// Clears the map diff --git a/cds/container/impl/skip_list_set.h b/cds/container/impl/skip_list_set.h index ae20895b..4221124f 100644 --- a/cds/container/impl/skip_list_set.h +++ b/cds/container/impl/skip_list_set.h @@ -25,7 +25,7 @@ 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. + OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. */ #ifndef CDSLIB_CONTAINER_IMPL_SKIP_LIST_SET_H @@ -483,9 +483,7 @@ namespace cds { namespace container { template guarded_ptr extract( Q const& key ) { - guarded_ptr gp; - base_class::extract_( gp.guard(), key, typename base_class::key_comparator() ); - return gp; + return base_class::extract_( key, typename base_class::key_comparator() ); } /// Extracts the item from the set with comparing functor \p pred @@ -502,9 +500,7 @@ namespace cds { namespace container { { CDS_UNUSED( pred ); typedef cds::details::predicate_wrapper< node_type, Less, typename maker::value_accessor > wrapped_less; - guarded_ptr gp; - base_class::extract_( gp.guard(), key, cds::opt::details::make_comparator_from_less() ); - return gp; + return base_class::extract_( key, cds::opt::details::make_comparator_from_less() ); } /// Extracts an item with minimal key from the set @@ -533,9 +529,7 @@ namespace cds { namespace container { */ guarded_ptr extract_min() { - guarded_ptr gp; - base_class::extract_min_( gp.guard() ); - return gp; + return base_class::extract_min_(); } /// Extracts an item with maximal key from the set @@ -564,9 +558,7 @@ namespace cds { namespace container { */ guarded_ptr extract_max() { - guarded_ptr gp; - base_class::extract_max_( gp.guard() ); - return gp; + return base_class::extract_max_(); } /// Find the \p key @@ -700,9 +692,7 @@ namespace cds { namespace container { template guarded_ptr get( Q const& key ) { - guarded_ptr gp; - base_class::get_with_( gp.guard(), key, typename base_class::key_comparator() ); - return gp; + return base_class::get_with_( key, typename base_class::key_comparator() ); } /// Finds \p key and return the item found @@ -719,9 +709,7 @@ namespace cds { namespace container { { CDS_UNUSED( pred ); typedef cds::details::predicate_wrapper< node_type, Less, typename maker::value_accessor > wrapped_less; - guarded_ptr gp; - base_class::get_with_( gp.guard(), key, cds::opt::details::make_comparator_from_less< wrapped_less >()); - return gp; + return base_class::get_with_( key, cds::opt::details::make_comparator_from_less< wrapped_less >()); } /// Clears the set (not atomic). diff --git a/cds/container/split_list_map.h b/cds/container/split_list_map.h index 57c460dd..29cd7fc8 100644 --- a/cds/container/split_list_map.h +++ b/cds/container/split_list_map.h @@ -25,7 +25,7 @@ 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. + OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. */ #ifndef CDSLIB_CONTAINER_SPLIT_LIST_MAP_H @@ -511,9 +511,7 @@ namespace cds { namespace container { template guarded_ptr extract( K const& key ) { - guarded_ptr gp; - base_class::extract_( gp.guard(), key ); - return gp; + return base_class::extract_( key ); } /// Extracts the item using compare functor \p pred @@ -529,9 +527,7 @@ namespace cds { namespace container { guarded_ptr extract_with( K const& key, Less pred ) { CDS_UNUSED( pred ); - guarded_ptr gp; - base_class::extract_with_( gp.guard(), key, cds::details::predicate_wrapper()); - return gp; + return base_class::extract_with_( key, cds::details::predicate_wrapper()); } /// Finds the key \p key @@ -648,9 +644,7 @@ namespace cds { namespace container { template guarded_ptr get( K const& key ) { - guarded_ptr gp; - base_class::get_( gp.guard(), key ); - return gp; + return base_class::get_( key ); } /// Finds \p key and return the item found @@ -666,9 +660,7 @@ namespace cds { namespace container { guarded_ptr get_with( K const& key, Less pred ) { CDS_UNUSED( pred ); - guarded_ptr gp; - base_class::get_with_( gp.guard(), key, cds::details::predicate_wrapper()); - return gp; + return base_class::get_with_( key, cds::details::predicate_wrapper()); } /// Clears the map (not atomic) diff --git a/cds/container/split_list_set.h b/cds/container/split_list_set.h index e9d44e32..4c48a5d4 100644 --- a/cds/container/split_list_set.h +++ b/cds/container/split_list_set.h @@ -25,7 +25,7 @@ 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. + OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. */ #ifndef CDSLIB_CONTAINER_SPLIT_LIST_SET_H @@ -638,9 +638,7 @@ namespace cds { namespace container { template guarded_ptr extract( Q const& key ) { - guarded_ptr gp; - extract_( gp.guard(), key ); - return gp; + return extract_( key ); } /// Extracts the item using compare functor \p pred @@ -655,9 +653,7 @@ namespace cds { namespace container { template guarded_ptr extract_with( Q const& key, Less pred ) { - guarded_ptr gp; - extract_with_( gp.guard(), key, pred ); - return gp; + return extract_with_( key, pred ); } /// Finds the key \p key @@ -791,9 +787,7 @@ namespace cds { namespace container { template guarded_ptr get( Q const& key ) { - guarded_ptr gp; - get_( gp.guard(), key ); - return gp; + return get_( key ); } /// Finds \p key and return the item found @@ -808,9 +802,7 @@ namespace cds { namespace container { template guarded_ptr get_with( Q const& key, Less pred ) { - guarded_ptr gp; - get_with_( gp.guard(), key, pred ); - return gp; + return get_with_( key, pred ); } /// Clears the set (not atomic) @@ -847,17 +839,17 @@ namespace cds { namespace container { using base_class::get_; template - bool extract_with_( typename guarded_ptr::native_guard& guard, Q const& key, Less pred ) + guarded_ptr extract_with_( Q const& key, Less pred ) { CDS_UNUSED( pred ); - return base_class::extract_with_( guard, key, typename maker::template predicate_wrapper::type()); + return base_class::extract_with_( key, typename maker::template predicate_wrapper::type()); } template - bool get_with_( typename guarded_ptr::native_guard& guard, Q const& key, Less pred ) + guarded_ptr get_with_( Q const& key, Less pred ) { CDS_UNUSED( pred ); - return base_class::get_with_( guard, key, typename maker::template predicate_wrapper::type()); + return base_class::get_with_( key, typename maker::template predicate_wrapper::type()); } //@endcond diff --git a/cds/gc/details/dhp.h b/cds/gc/details/dhp.h index 68a3659b..f459c218 100644 --- a/cds/gc/details/dhp.h +++ b/cds/gc/details/dhp.h @@ -25,7 +25,7 @@ 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. + OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. */ #ifndef CDSLIB_GC_DETAILS_DHP_H @@ -117,13 +117,23 @@ namespace cds { namespace gc { { return pPost.load( atomics::memory_order_acquire ) == nullptr; } + + guarded_ptr get( atomics::memory_order order = atomics::memory_order_acquire ) + { + return pPost.load( order ); + } + + void set( guarded_ptr p, atomics::memory_order order = atomics::memory_order_release ) + { + pPost.store( p, order ); + } }; /// Guard allocator template class guard_allocator { - cds::details::Allocator m_GuardAllocator ; ///< guard allocator + cds::details::Allocator m_GuardAllocator; ///< guard allocator atomics::atomic m_GuardList; ///< Head of allocated guard list (linked by guard_data::pGlobalNext field) atomics::atomic m_FreeGuardList; ///< Head of free guard list (linked by guard_data::pNextFree field) @@ -174,7 +184,7 @@ namespace cds { namespace gc { } /// Allocates a guard from free list or from heap if free list is empty - guard_data * alloc() + guard_data* alloc() { // Try to pop a guard from free-list details::guard_data * pGuard; @@ -196,7 +206,7 @@ namespace cds { namespace gc { /** The function places the guard \p pGuard into free-list */ - void free( guard_data * pGuard ) CDS_NOEXCEPT + void free( guard_data* pGuard ) CDS_NOEXCEPT { pGuard->pPost.store( nullptr, atomics::memory_order_relaxed ); @@ -329,9 +339,7 @@ namespace cds { namespace gc { // Item counter is needed only as a threshold for \p scan() function // So, we may clear the item counter without synchronization with m_pHead res.second = m_nItemCount.exchange( 0, atomics::memory_order_relaxed ); - res.first = m_pHead.exchange( nullptr, atomics::memory_order_acq_rel ); - return res; } @@ -509,208 +517,8 @@ namespace cds { namespace gc { } while ( !m_pEpochFree[nEpoch].compare_exchange_weak( pCurHead, pHead, atomics::memory_order_release, atomics::memory_order_relaxed )); } }; - - /// Uninitialized guard - class guard - { - friend class dhp::ThreadGC; - protected: - details::guard_data * m_pGuard ; ///< Pointer to guard data - - public: - /// Initialize empty guard. - CDS_CONSTEXPR guard() CDS_NOEXCEPT - : m_pGuard( nullptr ) - {} - - /// Copy-ctor is disabled - guard( guard const& ) = delete; - - /// Move-ctor is disabled - guard( guard&& ) = delete; - - /// Object destructor, does nothing - ~guard() CDS_NOEXCEPT - {} - - /// Get current guarded pointer - void * get( atomics::memory_order order = atomics::memory_order_acquire ) const CDS_NOEXCEPT - { - assert( m_pGuard != nullptr ); - return m_pGuard->pPost.load( order ); - } - - /// Guards pointer \p p - void set( void * p, atomics::memory_order order = atomics::memory_order_release ) CDS_NOEXCEPT - { - assert( m_pGuard != nullptr ); - m_pGuard->pPost.store( p, order ); - } - - /// Clears the guard - void clear( atomics::memory_order order = atomics::memory_order_relaxed ) CDS_NOEXCEPT - { - assert( m_pGuard != nullptr ); - m_pGuard->pPost.store( nullptr, order ); - } - - /// Guards pointer \p p - template - T * operator =(T * p) CDS_NOEXCEPT - { - set( reinterpret_cast( const_cast(p) )); - return p; - } - - std::nullptr_t operator=(std::nullptr_t) CDS_NOEXCEPT - { - clear(); - return nullptr; - } - - public: // for ThreadGC. - /* - GCC cannot compile code for template versions of ThreadGC::allocGuard/freeGuard, - the compiler produces error: 'cds::gc::dhp::details::guard_data* cds::gc::dhp::details::guard::m_pGuard' is protected - despite the fact that ThreadGC is declared as friend for guard class. - Therefore, we have to add set_guard/get_guard public functions - */ - /// Set guard data - void set_guard( details::guard_data * pGuard ) CDS_NOEXCEPT - { - assert( m_pGuard == nullptr ); - m_pGuard = pGuard; - } - - /// Get current guard data - details::guard_data * get_guard() CDS_NOEXCEPT - { - return m_pGuard; - } - /// Get current guard data - details::guard_data * get_guard() const CDS_NOEXCEPT - { - return m_pGuard; - } - - details::guard_data * release_guard() CDS_NOEXCEPT - { - details::guard_data * p = m_pGuard; - m_pGuard = nullptr; - return p; - } - - bool is_initialized() const - { - return m_pGuard != nullptr; - } - }; - } // namespace details - /// Guard - /** - This class represents auto guard: ctor allocates a guard from guard pool, - dtor returns the guard back to the pool of free guard. - */ - class Guard: public details::guard - { - typedef details::guard base_class; - friend class ThreadGC; - public: - /// Allocates a guard from \p gc GC. \p gc must be ThreadGC object of current thread - Guard(); // inline in dhp_impl.h - - /// Returns guard allocated back to pool of free guards - ~Guard(); // inline in dhp_impl.h - - /// Guards pointer \p p - template - T * operator =(T * p) CDS_NOEXCEPT - { - return base_class::operator =( p ); - } - - std::nullptr_t operator=(std::nullptr_t) CDS_NOEXCEPT - { - return base_class::operator =(nullptr); - } - }; - - /// Array of guards - /** - This class represents array of auto guards: ctor allocates \p Count guards from guard pool, - dtor returns the guards allocated back to the pool. - */ - template - class GuardArray - { - details::guard m_arr[Count] ; ///< array of guard - const static size_t c_nCapacity = Count ; ///< Array capacity (equal to \p Count template parameter) - - public: - /// Rebind array for other size \p OtherCount - template - struct rebind { - typedef GuardArray other ; ///< rebinding result - }; - - public: - /// Allocates array of guards from \p gc which must be the ThreadGC object of current thread - GuardArray(); // inline in dhp_impl.h - - /// The object is not copy-constructible - GuardArray( GuardArray const& ) = delete; - - /// The object is not move-constructible - GuardArray( GuardArray&& ) = delete; - - /// Returns guards allocated back to pool - ~GuardArray(); // inline in dh_impl.h - - /// Returns the capacity of array - CDS_CONSTEXPR size_t capacity() const CDS_NOEXCEPT - { - return c_nCapacity; - } - - /// Returns reference to the guard of index \p nIndex (0 <= \p nIndex < \p Count) - details::guard& operator []( size_t nIndex ) CDS_NOEXCEPT - { - assert( nIndex < capacity() ); - return m_arr[nIndex]; - } - - /// Returns reference to the guard of index \p nIndex (0 <= \p nIndex < \p Count) [const version] - const details::guard& operator []( size_t nIndex ) const CDS_NOEXCEPT - { - assert( nIndex < capacity() ); - return m_arr[nIndex]; - } - - /// Set the guard \p nIndex. 0 <= \p nIndex < \p Count - template - void set( size_t nIndex, T * p ) CDS_NOEXCEPT - { - assert( nIndex < capacity() ); - m_arr[nIndex].set( p ); - } - - /// Clears (sets to \p nullptr) the guard \p nIndex - void clear( size_t nIndex ) CDS_NOEXCEPT - { - assert( nIndex < capacity() ); - m_arr[nIndex].clear(); - } - - /// Clears all guards in the array - void clearAll() CDS_NOEXCEPT - { - for ( size_t i = 0; i < capacity(); ++i ) - clear(i); - } - }; - /// Memory manager (Garbage collector) class CDS_EXPORT_API GarbageCollector { @@ -845,7 +653,7 @@ namespace cds { namespace gc { } /// Allocates guard list for a thread. - details::guard_data * allocGuardList( size_t nCount ) + details::guard_data* allocGuardList( size_t nCount ) { return m_GuardPool.allocList( nCount ); } @@ -921,9 +729,9 @@ namespace cds { namespace gc { */ class ThreadGC { - GarbageCollector& m_gc ; ///< reference to GC singleton - details::guard_data * m_pList ; ///< Local list of guards owned by the thread - details::guard_data * m_pFree ; ///< The list of free guard from m_pList + GarbageCollector& m_gc; ///< reference to GC singleton + details::guard_data * m_pList; ///< Local list of guards owned by the thread + details::guard_data * m_pFree; ///< The list of free guard from m_pList public: /// Default constructor @@ -962,72 +770,84 @@ namespace cds { namespace gc { } public: - /// Initializes guard \p g - void allocGuard( dhp::details::guard& g ) + /// Allocates new guard + dhp::details::guard_data* allocGuard() { assert( m_pList != nullptr ); - if ( !g.m_pGuard ) { - if ( m_pFree ) { - g.m_pGuard = m_pFree; - m_pFree = m_pFree->pNextFree.load( atomics::memory_order_relaxed ); - } - else { - g.m_pGuard = m_gc.allocGuard(); - g.m_pGuard->pThreadNext = m_pList; - m_pList = g.m_pGuard; - } + + dhp::details::guard_data* ret; + if ( cds_likely( m_pFree )) { + ret = m_pFree; + m_pFree = m_pFree->pNextFree.load( atomics::memory_order_relaxed ); + } + else { + ret = m_gc.allocGuard(); + ret->pThreadNext = m_pList; + m_pList = ret; } + return ret; } /// Frees guard \p g - void freeGuard( dhp::details::guard& g ) + void freeGuard( dhp::details::guard_data* g ) { assert( m_pList != nullptr ); - if ( g.m_pGuard ) { - g.m_pGuard->pPost.store( nullptr, atomics::memory_order_relaxed ); - g.m_pGuard->pNextFree.store( m_pFree, atomics::memory_order_relaxed ); - m_pFree = g.m_pGuard; - g.m_pGuard = nullptr; + if ( cds_likely( g )) { + g->pPost.store( nullptr, atomics::memory_order_relaxed ); + g->pNextFree.store( m_pFree, atomics::memory_order_relaxed ); + m_pFree = g; } } + /// Guard array + template + using guard_array = dhp::details::guard_data* [Count]; + /// Initializes guard array \p arr template - void allocGuard( GuardArray& arr ) + void allocGuard( guard_array& arr ) { assert( m_pList != nullptr ); size_t nCount = 0; while ( m_pFree && nCount < Count ) { - arr[nCount].set_guard( m_pFree ); + arr[nCount] = m_pFree; m_pFree = m_pFree->pNextFree.load(atomics::memory_order_relaxed); ++nCount; } while ( nCount < Count ) { - details::guard& g = arr[nCount++]; - g.set_guard( m_gc.allocGuard() ); - g.get_guard()->pThreadNext = m_pList; - m_pList = g.get_guard(); + dhp::details::guard_data*& g = arr[nCount]; + g = m_gc.allocGuard(); + g->pThreadNext = m_pList; + m_pList = g; + ++nCount; } } /// Frees guard array \p arr template - void freeGuard( GuardArray& arr ) + void freeGuard( guard_array& arr ) { assert( m_pList != nullptr ); - details::guard_data * pGuard; - for ( size_t i = 0; i < Count - 1; ++i ) { - pGuard = arr[i].get_guard(); - pGuard->pPost.store( nullptr, atomics::memory_order_relaxed ); - pGuard->pNextFree.store( arr[i+1].get_guard(), atomics::memory_order_relaxed ); + details::guard_data* first = nullptr; + details::guard_data* last; + for ( size_t i = 0; i < Count; ++i ) { + details::guard_data* guard = arr[i]; + if ( cds_likely( guard )) { + guard->pPost.store( nullptr, atomics::memory_order_relaxed ); + if ( first ) + last->pNextFree.store( guard, atomics::memory_order_relaxed ); + else + first = guard; + last = guard; + } + } + if ( first ) { + last->pNextFree.store( m_pFree, atomics::memory_order_relaxed ); + m_pFree = first; } - pGuard = arr[Count-1].get_guard(); - pGuard->pPost.store( nullptr, atomics::memory_order_relaxed ); - pGuard->pNextFree.store( m_pFree, atomics::memory_order_relaxed ); - m_pFree = arr[0].get_guard(); } /// Places retired pointer \p and its deleter \p pFunc into list of retired pointer for deferred reclamation diff --git a/cds/gc/details/hp.h b/cds/gc/details/hp.h index ffc57441..1bcfd43b 100644 --- a/cds/gc/details/hp.h +++ b/cds/gc/details/hp.h @@ -25,7 +25,7 @@ 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. + OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. */ #ifndef CDSLIB_GC_DETAILS_HP_H @@ -182,9 +182,10 @@ namespace cds { char padding[cds::c_nCacheLineSize]; atomics::atomic m_nSync; ///< dummy var to introduce synchronizes-with relationship between threads + char padding2[cds::c_nCacheLineSize]; /// Ctor - hp_record( const cds::gc::hp::GarbageCollector& HzpMgr ); // inline + hp_record( const cds::gc::hp::GarbageCollector& HzpMgr ); // inline ~hp_record() {} @@ -261,13 +262,13 @@ namespace cds { //@endcond }; - /// Not enough required Hazard Pointer count + /// Not enough Hazard Pointer class too_many_hazard_ptr : public std::length_error { public: //@cond too_many_hazard_ptr() - : std::length_error( "Not enough required Hazard Pointer count" ) + : std::length_error( "Not enough Hazard Pointer" ) {} //@endcond }; @@ -461,10 +462,10 @@ namespace cds { public: // Internals for threads /// Allocates Hazard Pointer GC record. For internal use only - details::hp_record * alloc_hp_record(); + details::hp_record* alloc_hp_record(); /// Free HP record. For internal use only - void free_hp_record( details::hp_record * pRec ); + void free_hp_record( details::hp_record* pRec ); /// The main garbage collecting function /** @@ -546,8 +547,8 @@ namespace cds { */ class ThreadGC { - GarbageCollector& m_HzpManager; ///< Hazard Pointer GC singleton - details::hp_record * m_pHzpRec; ///< Pointer to thread's HZP record + GarbageCollector& m_HzpManager; ///< Hazard Pointer GC singleton + details::hp_record* m_pHzpRec; ///< Pointer to thread's HZP record public: /// Default constructor @@ -565,7 +566,7 @@ namespace cds { } /// Checks if thread GC is initialized - bool isInitialized() const { return m_pHzpRec != nullptr; } + bool isInitialized() const { return m_pHzpRec != nullptr; } /// Initialization. Repeat call is available void init() @@ -578,21 +579,21 @@ namespace cds { void fini() { if ( m_pHzpRec ) { - details::hp_record * pRec = m_pHzpRec; + details::hp_record* pRec = m_pHzpRec; m_pHzpRec = nullptr; m_HzpManager.free_hp_record( pRec ); } } /// Initializes HP guard \p guard - details::hp_guard& allocGuard() + details::hp_guard* allocGuard() { assert( m_pHzpRec ); return m_pHzpRec->m_hzp.alloc(); } /// Frees HP guard \p guard - void freeGuard( details::hp_guard& guard ) + void freeGuard( details::hp_guard* guard ) { assert( m_pHzpRec ); m_pHzpRec->m_hzp.free( guard ); @@ -600,10 +601,10 @@ namespace cds { /// Initializes HP guard array \p arr template - void allocGuard( details::hp_array& arr ) + size_t allocGuard( details::hp_array& arr ) { assert( m_pHzpRec ); - m_pHzpRec->m_hzp.alloc( arr ); + return m_pHzpRec->m_hzp.alloc( arr ); } /// Frees HP guard array \p arr @@ -618,21 +619,6 @@ namespace cds { template void retirePtr( T * p, void (* pFunc)(T *) ) { - /* - union { - T * p; - hazard_pointer hp; - } cast_ptr; - cast_ptr.p = p; - - union{ - void( *pFunc )(T *); - free_retired_ptr_func hpFunc; - } cast_func; - cast_func.pFunc = pFunc; - - retirePtr( details::retired_ptr( cast_ptr.hp, cast_func.hpFunc ) ); - */ retirePtr( details::retired_ptr( reinterpret_cast( p ), reinterpret_cast( pFunc ))); } @@ -661,74 +647,6 @@ namespace cds { } }; - /// Auto hp_guard. - /** - This class encapsulates Hazard Pointer guard to protect a pointer against deletion. - It allocates one HP from thread's HP array in constructor and free the hazard pointer allocated - in destructor. - */ - class guard - { - details::hp_guard& m_hp ; ///< Hazard pointer guarded - - public: - typedef details::hp_guard::hazard_ptr hazard_ptr ; ///< Hazard pointer type - - public: - /// Allocates HP guard - guard(); // inline in hp_impl.h - - /// Allocates HP guard from \p gc and protects the pointer \p p of type \p T - template - explicit guard( T * p ); // inline in hp_impl.h - - /// Frees HP guard. The pointer guarded may be deleted after this. - ~guard(); // inline in hp_impl.h - - /// Protects the pointer \p p against reclamation (guards the pointer). - template - T * operator =( T * p ) - { - return m_hp = p; - } - - //@cond - std::nullptr_t operator =(std::nullptr_t) - { - return m_hp = nullptr; - } - //@endcond - - /// Get raw guarded pointer - hazard_ptr get() const - { - return m_hp; - } - }; - - /// Auto-managed array of hazard pointers - /** - This class is wrapper around cds::gc::hp::details::hp_array class. - \p Count is the size of HP array - */ - template - class array : public details::hp_array - { - public: - /// Rebind array for other size \p COUNT2 - template - struct rebind { - typedef array other; ///< rebinding result - }; - - public: - /// Allocates array of HP guard - array(); // inline in hp_impl.h - - /// Frees array of HP guard - ~array(); //inline in hp_impl.h - }; - } // namespace hp }} // namespace cds::gc //@endcond diff --git a/cds/gc/details/hp_alloc.h b/cds/gc/details/hp_alloc.h index 5da30526..d6d42a57 100644 --- a/cds/gc/details/hp_alloc.h +++ b/cds/gc/details/hp_alloc.h @@ -25,7 +25,7 @@ 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. + OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. */ #ifndef CDSLIB_GC_DETAILS_HP_ALLOC_H @@ -52,18 +52,23 @@ namespace cds { */ class hp_guard : protected atomics::atomic < hazard_pointer > { + template friend class hp_allocator; + public: - typedef hazard_pointer hazard_ptr; ///< Hazard pointer type + typedef hazard_pointer hazard_ptr;///< Hazard pointer type + private: - typedef atomics::atomic base_class; + typedef atomics::atomic atomic_hazard_ptr; - protected: - template friend class hp_allocator; + atomic_hazard_ptr m_hp; + hp_guard* m_next; // next free guard public: hp_guard() CDS_NOEXCEPT - : base_class( nullptr ) + : m_hp( nullptr ) + , m_next( nullptr ) {} + ~hp_guard() CDS_NOEXCEPT {} @@ -85,28 +90,19 @@ namespace cds { return nullptr; } - /// Returns current value of hazard pointer - /** - Loading has acquire semantics - */ - operator hazard_ptr() const CDS_NOEXCEPT - { - return get(); - } - /// Returns current value of hazard pointer /** Loading has acquire semantics */ hazard_ptr get( atomics::memory_order order = atomics::memory_order_acquire ) const CDS_NOEXCEPT { - return base_class::load( order ); + return m_hp.load( order ); } template void set( T * p, atomics::memory_order order = atomics::memory_order_release ) CDS_NOEXCEPT { - base_class::store( reinterpret_cast(p), order ); + m_hp.store( reinterpret_cast(p), order ); } /// Clears HP @@ -116,7 +112,7 @@ namespace cds { void clear( atomics::memory_order order = atomics::memory_order_release ) CDS_NOEXCEPT { // memory order is not necessary here - base_class::store( nullptr, order ); + m_hp.store( nullptr, order ); } }; @@ -137,24 +133,22 @@ namespace cds { Template parameter: \li Count - capacity of array - */ template class hp_array { + template friend class hp_allocator; + public: - typedef hazard_pointer hazard_ptr_type; ///< Hazard pointer type - typedef hp_guard atomic_hazard_ptr; ///< Element type of the array + typedef hazard_pointer hazard_ptr; ///< Hazard pointer type static CDS_CONSTEXPR const size_t c_nCapacity = Count ; ///< Capacity of the array - private: - atomic_hazard_ptr * m_arr ; ///< Hazard pointer array of size = \p Count - template friend class hp_allocator; - public: /// Constructs uninitialized array. hp_array() CDS_NOEXCEPT - {} + { + memset( m_arr, 0, sizeof( m_arr )); + } /// Destructs object ~hp_array() CDS_NOEXCEPT @@ -167,32 +161,49 @@ namespace cds { } /// Set hazard pointer \p nIndex. 0 <= \p nIndex < \p Count - void set( size_t nIndex, hazard_ptr_type hzPtr ) CDS_NOEXCEPT + void set( size_t nIndex, hazard_ptr hptr ) CDS_NOEXCEPT { - assert( nIndex < capacity() ); - m_arr[nIndex] = hzPtr; + assert( nIndex < capacity()); + assert( m_arr[nIndex] != nullptr ); + + *m_arr[nIndex] = hptr; } - /// Returns reference to hazard pointer of index \p nIndex (0 <= \p nIndex < \p Count) - atomic_hazard_ptr& operator []( size_t nIndex ) CDS_NOEXCEPT + /// Returns pointer to hazard pointer of index \p nIndex (0 <= \p nIndex < \p Count) + hp_guard* operator []( size_t nIndex ) CDS_NOEXCEPT { - assert( nIndex < capacity() ); + assert( nIndex < capacity()); return m_arr[nIndex]; } - /// Returns reference to hazard pointer of index \p nIndex (0 <= \p nIndex < \p Count) [const version] - atomic_hazard_ptr& operator []( size_t nIndex ) const CDS_NOEXCEPT + /// Returns pointer to hazard pointer of index \p nIndex (0 <= \p nIndex < \p Count) [const version] + hp_guard* operator []( size_t nIndex ) const CDS_NOEXCEPT { - assert( nIndex < capacity() ); + assert( nIndex < capacity()); return m_arr[nIndex]; } /// Clears (sets to \p nullptr) hazard pointer \p nIndex void clear( size_t nIndex ) CDS_NOEXCEPT + { + assert( nIndex < capacity()); + assert( m_arr[nIndex] != nullptr ); + + m_arr[ nIndex ]->clear(); + } + + hp_guard* release( size_t nIndex ) CDS_NOEXCEPT { assert( nIndex < capacity() ); - m_arr[ nIndex ].clear(); + + hp_guard* p = m_arr[ nIndex ]; + m_arr[ nIndex ] = nullptr; + return p; } + + + private: + hp_guard* m_arr[c_nCapacity]; ///< Hazard pointer array of size = \p Count }; /// Allocator of hazard pointers for the thread @@ -212,26 +223,26 @@ namespace cds { class hp_allocator { public: - typedef hazard_pointer hazard_ptr_type; ///< type of hazard pointer - typedef hp_guard atomic_hazard_ptr; ///< Atomic hazard pointer type - typedef Allocator allocator_type; ///< allocator type + typedef hazard_pointer hazard_ptr; ///< type of hazard pointer + typedef Allocator allocator_type; ///< allocator type private: - typedef cds::details::Allocator< atomic_hazard_ptr, allocator_type > allocator_impl; + typedef cds::details::Allocator< hp_guard, allocator_type > allocator_impl; - atomic_hazard_ptr * m_arrHazardPtr ; ///< Array of hazard pointers - size_t m_nTop ; ///< The top of stack - const size_t m_nCapacity ; ///< Array capacity + hp_guard* m_arrHazardPtr; ///< Array of hazard pointers + hp_guard* m_FreeListHead; ///< List of free hp guards + size_t const m_nCapacity; ///< Array capacity public: /// Default ctor explicit hp_allocator( - size_t nCapacity ///< max count of hazard pointer per thread - ) - : m_arrHazardPtr( alloc_array( nCapacity ) ) - , m_nCapacity( nCapacity ) + size_t nCapacity ///< max count of hazard pointer per thread + ) + : m_arrHazardPtr( alloc_array( nCapacity )) + , m_FreeListHead( m_arrHazardPtr ) + , m_nCapacity( nCapacity ) { - make_free(); + build_free_list(); } /// Dtor @@ -253,38 +264,52 @@ namespace cds { } /// Checks if all items are allocated - bool isFull() const CDS_NOEXCEPT + bool full() const CDS_NOEXCEPT { - return m_nTop == 0; + return m_FreeListHead == nullptr; } /// Allocates hazard pointer - atomic_hazard_ptr& alloc() + hp_guard* alloc() { - assert( m_nTop > 0 ); - --m_nTop; - return m_arrHazardPtr[m_nTop]; + assert( !full()); + + hp_guard* p = m_FreeListHead; + m_FreeListHead = m_FreeListHead->m_next; + return p; } /// Frees previously allocated hazard pointer - void free( atomic_hazard_ptr& hp ) CDS_NOEXCEPT + void free( hp_guard* hp ) CDS_NOEXCEPT { - assert( m_nTop < capacity() ); - hp.clear(); - ++m_nTop; + if ( hp ) { + hp->clear(); + hp->m_next = m_FreeListHead; + m_FreeListHead = hp; + } } /// Allocates hazard pointers array /** Allocates \p Count hazard pointers from array \p m_arrHazardPtr - Returns initialized object \p arr + Initializes \p arr with hazard pointers. + + @return actual size of allocated array. */ template - void alloc( hp_array& arr ) + size_t alloc( hp_array& arr ) { - assert( m_nTop >= Count ); - m_nTop -= Count; - arr.m_arr = m_arrHazardPtr + m_nTop; + size_t i; + hp_guard* p = m_FreeListHead; + for ( i = 0; i < Count && p; ++i ) { + arr.m_arr[i] = p; + p = p->m_next; + } + size_t ret = i; + for ( ; i < Count; ++i ) + arr.m_arr[i] = nullptr; + m_FreeListHead = p; + return ret; } /// Frees hazard pointer array @@ -294,38 +319,49 @@ namespace cds { template void free( hp_array const& arr ) CDS_NOEXCEPT { - CDS_UNUSED( arr ); - - assert( m_nTop + Count <= capacity()); - for ( size_t i = m_nTop; i < m_nTop + Count; ++i ) - m_arrHazardPtr[i].clear(); - m_nTop += Count; + hp_guard* pList = m_FreeListHead; + for ( size_t i = 0; i < Count; ++i ) { + hp_guard* p = arr[i]; + if ( p ) { + p->clear(); + p->m_next = pList; + pList = p; + } + } + m_FreeListHead = pList; } /// Makes all HP free void clear() CDS_NOEXCEPT { - make_free(); + for ( size_t i = 0; i < capacity(); ++i ) + m_arrHazardPtr[i].clear(); } - /// Returns to i-th hazard pointer - atomic_hazard_ptr& operator []( size_t i ) CDS_NOEXCEPT + /// Returns i-th hazard pointer + hp_guard& operator []( size_t i ) CDS_NOEXCEPT { assert( i < capacity() ); return m_arrHazardPtr[i]; } private: - void make_free() CDS_NOEXCEPT + hp_guard* alloc_array( size_t nCapacity ) { - for ( size_t i = 0; i < capacity(); ++i ) - m_arrHazardPtr[i].clear(); - m_nTop = capacity(); + return allocator_impl().NewArray( nCapacity ); } - atomic_hazard_ptr * alloc_array( size_t nCapacity ) + void build_free_list() { - return allocator_impl().NewArray( nCapacity ); + hp_guard* first = m_arrHazardPtr; + hp_guard* last = m_arrHazardPtr + capacity(); + hp_guard* prev = first; + for ( ++first; first < last; ++first ) { + prev->m_next = first; + prev = first; + } + prev->m_next = nullptr; + m_FreeListHead = m_arrHazardPtr; } }; diff --git a/cds/gc/details/hp_type.h b/cds/gc/details/hp_type.h index a3a41dd5..21c31157 100644 --- a/cds/gc/details/hp_type.h +++ b/cds/gc/details/hp_type.h @@ -25,7 +25,7 @@ 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. + OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. */ #ifndef CDSLIB_GC_DETAILS_HP_TYPE_H diff --git a/cds/gc/hp.h b/cds/gc/hp.h index 901cf220..bcbc3a7a 100644 --- a/cds/gc/hp.h +++ b/cds/gc/hp.h @@ -25,7 +25,7 @@ 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. + OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. */ #ifndef CDSLIB_GC_HP_H diff --git a/cds/gc/impl/dhp_decl.h b/cds/gc/impl/dhp_decl.h index b2b6e77a..128c8845 100644 --- a/cds/gc/impl/dhp_decl.h +++ b/cds/gc/impl/dhp_decl.h @@ -25,7 +25,7 @@ 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. + OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. */ #ifndef CDSLIB_GC_IMPL_DHP_DECL_H @@ -119,8 +119,8 @@ namespace cds { namespace gc { public: // for internal use only!!! //@cond - static void alloc_guard( cds::gc::dhp::details::guard& g ); // inline in dhp_impl.h - static void free_guard( cds::gc::dhp::details::guard& g ); // inline in dhp_impl.h + static dhp::details::guard_data* alloc_guard(); // inline in dhp_impl.h + static void free_guard( dhp::details::guard_data* g ); // inline in dhp_impl.h //@endcond }; @@ -132,31 +132,80 @@ namespace cds { namespace gc { A guard is the hazard pointer. Additionally, the \p %Guard class manages allocation and deallocation of the hazard pointer - A \p %Guard object is not copy- and move-constructible - and not copy- and move-assignable. - */ - class Guard: public dhp::Guard - { - //@cond - typedef dhp::Guard base_class; - //@endcond + \p %Guard object is movable but not copyable. - public: // for internal use only - //@cond - typedef cds::gc::dhp::details::guard native_guard; - //@endcond + The guard object can be in two states: + - unlinked - the guard is not linked with any internal hazard pointer. + In this state no operation except \p link() and move assignment is supported. + - linked (default) - the guard allocates an internal hazard pointer and fully operable. + Due to performance reason the implementation does not check state of the guard in runtime. + + @warning Move assignment can transfer the guard in unlinked state, use with care. + */ + class Guard + { public: - // Default ctor - Guard() + /// Default ctor allocates a guard (hazard pointer) from thread-private storage + Guard() CDS_NOEXCEPT + : m_guard( thread_gc::alloc_guard()) {} - //@cond + /// Initilalizes an unlinked guard i.e. the guard contains no hazard pointer. Used for move semantics support + explicit Guard( std::nullptr_t ) CDS_NOEXCEPT + : m_guard( nullptr ) + {} + + /// Move ctor - \p src guard becomes unlinked (transfer internal guard ownership) + Guard( Guard&& src ) CDS_NOEXCEPT + : m_guard( src.m_guard ) + { + src.m_guard = nullptr; + } + + /// Move assignment: the internal guards are swapped between \p src and \p this + /** + @warning \p src will become in unlinked state if \p this was unlinked on entry. + */ + Guard& operator=( Guard&& src ) CDS_NOEXCEPT + { + std::swap( m_guard, src.m_guard ); + return *this; + } + + /// Copy ctor is prohibited - the guard is not copyable Guard( Guard const& ) = delete; - Guard( Guard&& s ) = delete; - Guard& operator=(Guard const&) = delete; - Guard& operator=(Guard&&) = delete; - //@endcond + + /// Copy assignment is prohibited + Guard& operator=( Guard const& ) = delete; + + ~Guard() + { + if ( m_guard ) + thread_gc::free_guard( m_guard ); + } + + /// Checks if the guard object linked with any internal hazard pointer + bool is_linked() const + { + return m_guard != nullptr; + } + + /// Links the guard with internal hazard pointer if the guard is in unlinked state + void link() + { + if ( !m_guard ) + m_guard = thread_gc::alloc_guard(); + } + + /// Unlinks the guard from internal hazard pointer; the guard becomes in unlinked state + void unlink() + { + if ( m_guard ) { + thread_gc::free_guard( m_guard ); + m_guard = nullptr; + } + } /// Protects a pointer of type atomic /** @@ -214,15 +263,18 @@ namespace cds { namespace gc { or for already guarded pointer. */ template - T * assign( T * p ) + T* assign( T* p ) { - return base_class::operator =(p); + assert( m_guard != nullptr ); + m_guard->pPost.store( p, atomics::memory_order_release ); + return p; } //@cond std::nullptr_t assign( std::nullptr_t ) { - return base_class::operator =(nullptr); + clear(); + return nullptr; } //@endcond @@ -233,9 +285,9 @@ namespace cds { namespace gc { or for already guarded pointer. */ template - T * assign( cds::details::marked_ptr p ) + T* assign( cds::details::marked_ptr p ) { - return base_class::operator =( p.ptr() ); + return assign( p.ptr() ); } /// Copy from \p src guard to \p this guard @@ -247,7 +299,8 @@ namespace cds { namespace gc { /// Clears value of the guard void clear() { - base_class::clear(); + assert( m_guard != nullptr ); + m_guard->pPost.store( nullptr, atomics::memory_order_release ); } /// Gets the value currently protected (relaxed read) @@ -258,10 +311,25 @@ namespace cds { namespace gc { } /// Gets native guarded pointer stored - guarded_pointer get_native() const + void* get_native() const { - return base_class::get_guard()->pPost.load(atomics::memory_order_relaxed); + assert( m_guard != nullptr ); + return m_guard->pPost.load( atomics::memory_order_acquire ); } + + //@cond + dhp::details::guard_data* release() + { + dhp::details::guard_data* g = m_guard; + m_guard = nullptr; + return g; + } + //@endcond + + private: + //@cond + dhp::details::guard_data* m_guard; + //@endcond }; /// Array of Dynamic Hazard Pointer guards @@ -274,11 +342,8 @@ namespace cds { namespace gc { and not copy- and move-assignable. */ template - class GuardArray: public dhp::GuardArray + class GuardArray { - //@cond - typedef dhp::GuardArray base_class; - //@endcond public: /// Rebind array for other size \p OtherCount template @@ -286,17 +351,27 @@ namespace cds { namespace gc { typedef GuardArray other ; ///< rebinding result }; + /// Array capacity + static CDS_CONSTEXPR const size_t c_nCapacity = Count; + public: - // Default ctor - GuardArray() - {} + /// Default ctor allocates \p Count hazard pointers + GuardArray(); // inline in dhp_impl.h - //@cond - GuardArray( GuardArray const& ) = delete; + /// Move ctor is prohibited GuardArray( GuardArray&& ) = delete; - GuardArray& operator=(GuardArray const&) = delete; - GuardArray& operator-(GuardArray&&) = delete; - //@endcond + + /// Move assignment is prohibited + GuardArray& operator=( GuardArray&& ) = delete; + + /// Copy ctor is prohibited + GuardArray( GuardArray const& ) = delete; + + /// Copy assignment is prohibited + GuardArray& operator=( GuardArray const& ) = delete; + + /// Frees allocated hazard pointers + ~GuardArray(); // inline in dhp_impl.h /// Protects a pointer of type \p atomic /** @@ -351,7 +426,10 @@ namespace cds { namespace gc { template T * assign( size_t nIndex, T * p ) { - base_class::set(nIndex, p); + assert( nIndex < capacity()); + assert( m_arr[nIndex] != nullptr ); + + m_arr[nIndex]->pPost.store( p, atomics::memory_order_release ); return p; } @@ -382,7 +460,10 @@ namespace cds { namespace gc { /// Clear value of the slot \p nIndex void clear( size_t nIndex ) { - base_class::clear( nIndex ); + assert( nIndex < capacity() ); + assert( m_arr[nIndex] != nullptr ); + + m_arr[nIndex]->pPost.store( nullptr, atomics::memory_order_release ); } /// Get current value of slot \p nIndex @@ -395,14 +476,33 @@ namespace cds { namespace gc { /// Get native guarded pointer stored guarded_pointer get_native( size_t nIndex ) const { - return base_class::operator[](nIndex).get_guard()->pPost.load(atomics::memory_order_relaxed); + assert( nIndex < capacity() ); + assert( m_arr[nIndex] != nullptr ); + + return m_arr[nIndex]->pPost.load( atomics::memory_order_acquire ); } + //@cond + dhp::details::guard_data* release( size_t nIndex ) CDS_NOEXCEPT + { + assert( nIndex < capacity() ); + + dhp::details::guard_data* ret = m_arr[ nIndex ]; + m_arr[nIndex] = nullptr; + return ret; + } + //@endcond + /// Capacity of the guard array static CDS_CONSTEXPR size_t capacity() { return Count; } + + private: + //@cond + dhp::details::guard_data* m_arr[c_nCapacity]; + //@endcond }; /// Guarded pointer @@ -455,6 +555,8 @@ namespace cds { namespace gc { return p; } }; + + template friend class guarded_ptr; //@endcond public: @@ -464,38 +566,47 @@ namespace cds { namespace gc { /// Functor for casting \p guarded_type to \p value_type typedef typename std::conditional< std::is_same::value, trivial_cast, Cast >::type value_cast; - //@cond - typedef cds::gc::dhp::details::guard native_guard; - //@endcond - - private: - //@cond - native_guard m_guard; - //@endcond - public: /// Creates empty guarded pointer guarded_ptr() CDS_NOEXCEPT + : m_guard( nullptr ) {} //@cond + explicit guarded_ptr( dhp::details::guard_data* g ) CDS_NOEXCEPT + : m_guard( g ) + {} + /// Initializes guarded pointer with \p p explicit guarded_ptr( guarded_type * p ) CDS_NOEXCEPT { - alloc_guard(); - assert( m_guard.is_initialized() ); - m_guard.set( p ); + reset( p ); } explicit guarded_ptr( std::nullptr_t ) CDS_NOEXCEPT + : m_guard( nullptr ) {} //@endcond /// Move ctor guarded_ptr( guarded_ptr&& gp ) CDS_NOEXCEPT + : m_guard( gp.m_guard ) { - m_guard.set_guard( gp.m_guard.release_guard() ); + gp.m_guard = nullptr; } + /// Move ctor + template + guarded_ptr( guarded_ptr&& gp ) CDS_NOEXCEPT + : m_guard( gp.m_guard ) + { + gp.m_guard = nullptr; + } + + /// Ctor from \p Guard + explicit guarded_ptr( Guard&& g ) CDS_NOEXCEPT + : m_guard( g.release() ) + {} + /// The guarded pointer is not copy-constructible guarded_ptr( guarded_ptr const& gp ) = delete; @@ -505,14 +616,20 @@ namespace cds { namespace gc { */ ~guarded_ptr() CDS_NOEXCEPT { - free_guard(); + release(); } /// Move-assignment operator guarded_ptr& operator=( guarded_ptr&& gp ) CDS_NOEXCEPT { - free_guard(); - m_guard.set_guard( gp.m_guard.release_guard() ); + std::swap( m_guard, gp.m_guard ); + return *this; + } + + /// Move-assignment from \p Guard + guarded_ptr& operator=( Guard&& g ) CDS_NOEXCEPT + { + std::swap( m_guard, g.m_guard ); return *this; } @@ -523,27 +640,27 @@ namespace cds { namespace gc { value_type * operator ->() const CDS_NOEXCEPT { assert( !empty() ); - return value_cast()( reinterpret_cast(m_guard.get())); + return value_cast()( reinterpret_cast(m_guard->get())); } /// Returns a reference to guarded value value_type& operator *() CDS_NOEXCEPT { assert( !empty()); - return *value_cast()(reinterpret_cast(m_guard.get())); + return *value_cast()(reinterpret_cast(m_guard->get())); } /// Returns const reference to guarded value value_type const& operator *() const CDS_NOEXCEPT { assert( !empty() ); - return *value_cast()(reinterpret_cast(m_guard.get())); + return *value_cast()(reinterpret_cast(m_guard->get())); } /// Checks if the guarded pointer is \p nullptr bool empty() const CDS_NOEXCEPT { - return !m_guard.is_initialized() || m_guard.get( atomics::memory_order_relaxed ) == nullptr; + return m_guard == nullptr || m_guard->get( atomics::memory_order_relaxed ) == nullptr; } /// \p bool operator returns !empty() @@ -564,18 +681,11 @@ namespace cds { namespace gc { //@cond // For internal use only!!! - native_guard& guard() CDS_NOEXCEPT - { - alloc_guard(); - assert( m_guard.is_initialized() ); - return m_guard; - } - void reset(guarded_type * p) CDS_NOEXCEPT { alloc_guard(); - assert( m_guard.is_initialized() ); - m_guard.set(p); + assert( m_guard ); + m_guard->set( p ); } //@endcond @@ -584,16 +694,23 @@ namespace cds { namespace gc { //@cond void alloc_guard() { - if ( !m_guard.is_initialized() ) - thread_gc::alloc_guard( m_guard ); + if ( !m_guard ) + m_guard = thread_gc::alloc_guard(); } void free_guard() { - if ( m_guard.is_initialized() ) + if ( m_guard ) { thread_gc::free_guard( m_guard ); + m_guard = nullptr; + } } //@endcond + + private: + //@cond + dhp::details::guard_data* m_guard; + //@endcond }; public: diff --git a/cds/gc/impl/dhp_impl.h b/cds/gc/impl/dhp_impl.h index a051e869..f22d74d6 100644 --- a/cds/gc/impl/dhp_impl.h +++ b/cds/gc/impl/dhp_impl.h @@ -25,7 +25,7 @@ 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. + OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. */ #ifndef CDSLIB_GC_IMPL_DHP_IMPL_H @@ -38,27 +38,32 @@ namespace cds { namespace gc { namespace dhp { - inline Guard::Guard() + static inline ThreadGC& get_thread_gc() { - cds::threading::getGC().allocGuard( *this ); + return cds::threading::getGC(); } - inline Guard::~Guard() - { - cds::threading::getGC().freeGuard( *this ); - } - - template - inline GuardArray::GuardArray() - { - cds::threading::getGC().allocGuard( *this ); - } - - template - inline GuardArray::~GuardArray() - { - cds::threading::getGC().freeGuard( *this ); - } + //inline Guard::Guard() + //{ + // cds::threading::getGC().allocGuard( *this ); + //} + + //inline Guard::~Guard() + //{ + // cds::threading::getGC().freeGuard( *this ); + //} + + //template + //inline GuardArray::GuardArray() + //{ + // cds::threading::getGC().allocGuard( *this ); + //} + + //template + //inline GuardArray::~GuardArray() + //{ + // cds::threading::getGC().freeGuard( *this ); + //} } // namespace dhp @@ -77,13 +82,26 @@ namespace cds { namespace gc { cds::threading::Manager::detachThread(); } - inline /*static*/ void DHP::thread_gc::alloc_guard( cds::gc::dhp::details::guard& g ) + inline /*static*/ dhp::details::guard_data* DHP::thread_gc::alloc_guard() + { + return dhp::get_thread_gc().allocGuard(); + } + inline /*static*/ void DHP::thread_gc::free_guard( dhp::details::guard_data* g ) { - return cds::threading::getGC().allocGuard(g); + if ( g ) + dhp::get_thread_gc().freeGuard( g ); } - inline /*static*/ void DHP::thread_gc::free_guard( cds::gc::dhp::details::guard& g ) + + template + inline DHP::GuardArray::GuardArray() + { + dhp::get_thread_gc().allocGuard( m_arr ); + } + + template + inline DHP::GuardArray::~GuardArray() { - cds::threading::getGC().freeGuard(g); + dhp::get_thread_gc().freeGuard( m_arr ); } inline void DHP::scan() diff --git a/cds/gc/impl/hp_decl.h b/cds/gc/impl/hp_decl.h index 64f3cdef..354ac6a8 100644 --- a/cds/gc/impl/hp_decl.h +++ b/cds/gc/impl/hp_decl.h @@ -25,7 +25,7 @@ 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. + OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. */ #ifndef CDSLIB_GC_IMPL_HP_DECL_H @@ -87,6 +87,9 @@ namespace cds { namespace gc { */ typedef hp::ThreadGC thread_gc_impl; + /// Exception "Too many Hazard Pointer" + typedef hp::GarbageCollector::too_many_hazard_ptr too_many_hazard_ptr_exception; + /// Wrapper for hp::ThreadGC class /** @headerfile cds/gc/hp.h @@ -121,8 +124,8 @@ namespace cds { namespace gc { public: // for internal use only!!! //@cond - static cds::gc::hp::details::hp_guard& alloc_guard(); // inline in hp_impl.h - static void free_guard( cds::gc::hp::details::hp_guard& g ); // inline in hp_impl.h + static cds::gc::hp::details::hp_guard* alloc_guard(); // inline in hp_impl.h + static void free_guard( cds::gc::hp::details::hp_guard* g ); // inline in hp_impl.h //@endcond }; @@ -130,29 +133,77 @@ namespace cds { namespace gc { /** @headerfile cds/gc/hp.h - A guard is the hazard pointer. - Additionally, the \p %Guard class manages allocation and deallocation of the hazard pointer + A guard is a hazard pointer. + Additionally, the \p %Guard class manages allocation and deallocation of the hazard pointer. + + \p %Guard object is movable but not copyable. + + The guard object can be in two states: + - unlinked - the guard is not linked with any internal hazard pointer. + In this state no operation except \p link() and move assignment is supported. + - linked (default) - the guard allocates an internal hazard pointer and fully operable. + + Due to performance reason the implementation does not check state of the guard in runtime. - A \p %Guard object is not copy- and move-constructible - and not copy- and move-assignable. + @warning Move assignment can transfer the guard in unlinked state, use with care. */ - class Guard : public hp::guard + class Guard { - //@cond - typedef hp::guard base_class; - //@endcond - public: - /// Default ctor - Guard() + /// Default ctor allocates a guard (hazard pointer) from thread-private storage + /** + @warning Can throw \p too_many_hazard_ptr_exception if internal hazard pointer objects are exhausted. + */ + Guard(); // inline in hp_impl.h + + /// Initilalizes an unlinked guard i.e. the guard contains no hazard pointer. Used for move semantics support + explicit Guard( std::nullptr_t ) CDS_NOEXCEPT + : m_guard( nullptr ) {} - //@cond + /// Move ctor - \p src guard becomes unlinked (transfer internal guard ownership) + Guard( Guard&& src ) CDS_NOEXCEPT + : m_guard( src.m_guard ) + { + src.m_guard = nullptr; + } + + /// Move assignment: the internal guards are swapped between \p src and \p this + /** + @warning \p src will become in unlinked state if \p this was unlinked on entry. + */ + Guard& operator=( Guard&& src ) CDS_NOEXCEPT + { + std::swap( m_guard, src.m_guard ); + return *this; + } + + /// Copy ctor is prohibited - the guard is not copyable Guard( Guard const& ) = delete; - Guard( Guard&& s ) = delete; - Guard& operator=(Guard const&) = delete; - Guard& operator=(Guard&&) = delete; - //@endcond + + /// Copy assignment is prohibited + Guard& operator=( Guard const& ) = delete; + + /// Frees the internal hazard pointer if the guard is in linked state + ~Guard() + { + unlink(); + } + + /// Checks if the guard object linked with any internal hazard pointer + bool is_linked() const + { + return m_guard != nullptr; + } + + /// Links the guard with internal hazard pointer if the guard is in unlinked state + /** + @warning Can throw \p too_many_hazard_ptr_exception if internal hazard pointer objects are exhausted. + */ + void link(); // inline in hp_impl.h + + /// Unlinks the guard from internal hazard pointer; the guard becomes in unlinked state + void unlink(); // inline in hp_impl.h /// Protects a pointer of type \p atomic /** @@ -160,10 +211,14 @@ namespace cds { namespace gc { The function tries to load \p toGuard and to store it to the HP slot repeatedly until the guard's value equals \p toGuard + + @warning The guad object should be in linked state, otherwise the result is undefined */ template T protect( atomics::atomic const& toGuard ) { + assert( m_guard != nullptr ); + T pCur = toGuard.load(atomics::memory_order_acquire); T pRet; do { @@ -188,11 +243,15 @@ namespace cds { namespace gc { value_type * operator()( T * p ); }; \endcode - Really, the result of f( toGuard.load() ) is assigned to the hazard pointer. + Actually, the result of f( toGuard.load() ) is assigned to the hazard pointer. + + @warning The guad object should be in linked state, otherwise the result is undefined */ template T protect( atomics::atomic const& toGuard, Func f ) { + assert( m_guard != nullptr ); + T pCur = toGuard.load(atomics::memory_order_acquire); T pRet; do { @@ -207,18 +266,21 @@ namespace cds { namespace gc { /** The function equals to a simple assignment the value \p p to guard, no loop is performed. Can be used for a pointer that cannot be changed concurrently + + @warning The guad object should be in linked state, otherwise the result is undefined */ template - T * assign( T * p ); // inline in hp_impl.h + T * assign( T* p ); // inline in hp_impl.h //@cond std::nullptr_t assign( std::nullptr_t ) { - return base_class::operator =(nullptr); + assert(m_guard != nullptr ); + return *m_guard = nullptr; } //@endcond - /// Copy from \p src guard to \p this guard + /// Copy a value guarded from \p src guard to \p this guard (valid only in linked state) void copy( Guard const& src ) { assign( src.get_native() ); @@ -228,31 +290,48 @@ namespace cds { namespace gc { /** The function equals to a simple assignment of p.ptr(), no loop is performed. Can be used for a marked pointer that cannot be changed concurrently. + + @warning The guad object should be in linked state, otherwise the result is undefined */ template T * assign( cds::details::marked_ptr p ) { - return base_class::operator =( p.ptr() ); + return assign( p.ptr()); } - /// Clear value of the guard + /// Clear value of the guard (valid only in linked state) void clear() { assign( nullptr ); } - /// Get the value currently protected + /// Get the value currently protected (valid only in linked state) template T * get() const { return reinterpret_cast( get_native() ); } - /// Get native hazard pointer stored + /// Get native hazard pointer stored (valid only in linked state) guarded_pointer get_native() const { - return base_class::get(); + assert( m_guard != nullptr ); + return m_guard->get(); } + + //@cond + hp::details::hp_guard* release() + { + hp::details::hp_guard* g = m_guard; + m_guard = nullptr; + return g; + } + //@endcond + + private: + //@cond + hp::details::hp_guard* m_guard; + //@endcond }; /// Array of Hazard Pointer guards @@ -261,33 +340,38 @@ namespace cds { namespace gc { The class is intended for allocating an array of hazard pointer guards. Template parameter \p Count defines the size of the array. - A \p %GuardArray object is not copy- and move-constructible - and not copy- and move-assignable. */ template - class GuardArray : public hp::array + class GuardArray { - //@cond - typedef hp::array base_class; - //@endcond public: /// Rebind array for other size \p Count2 template struct rebind { - typedef GuardArray other ; ///< rebinding result + typedef GuardArray other; ///< rebinding result }; + /// Array capacity + static CDS_CONSTEXPR const size_t c_nCapacity = Count; + public: - /// Default ctor - GuardArray() - {} + /// Default ctor allocates \p Count hazard pointers + GuardArray(); // inline in hp_impl.h - //@cond - GuardArray( GuardArray const& ) = delete; + /// Move ctor is prohibited GuardArray( GuardArray&& ) = delete; - GuardArray& operator=(GuardArray const&) = delete; - GuardArray& operator=(GuardArray&&) = delete; - //@endcond + + /// Move assignment is prohibited + GuardArray& operator=( GuardArray&& ) = delete; + + /// Copy ctor is prohibited + GuardArray( GuardArray const& ) = delete; + + /// Copy assignment is prohibited + GuardArray& operator=( GuardArray const& ) = delete; + + /// Frees allocated hazard pointers + ~GuardArray(); // inline in hp_impl.h /// Protects a pointer of type \p atomic /** @@ -299,6 +383,8 @@ namespace cds { namespace gc { template T protect( size_t nIndex, atomics::atomic const& toGuard ) { + assert( nIndex < capacity()); + T pRet; do { pRet = assign( nIndex, toGuard.load(atomics::memory_order_acquire) ); @@ -327,6 +413,8 @@ namespace cds { namespace gc { template T protect( size_t nIndex, atomics::atomic const& toGuard, Func f ) { + assert( nIndex < capacity() ); + T pRet; do { assign( nIndex, f( pRet = toGuard.load(atomics::memory_order_acquire) )); @@ -368,7 +456,7 @@ namespace cds { namespace gc { /// Clear value of the slot \p nIndex void clear( size_t nIndex ) { - base_class::clear( nIndex ); + m_arr.clear( nIndex ); } /// Get current value of slot \p nIndex @@ -381,14 +469,27 @@ namespace cds { namespace gc { /// Get native hazard pointer stored guarded_pointer get_native( size_t nIndex ) const { - return base_class::operator[](nIndex).get(); + assert( nIndex < capacity() ); + return m_arr[nIndex]->get(); } + //@cond + hp::details::hp_guard* release( size_t nIndex ) CDS_NOEXCEPT + { + return m_arr.release( nIndex ); + } + //@endcond + /// Capacity of the guard array static CDS_CONSTEXPR size_t capacity() { - return Count; + return c_nCapacity; } + + private: + //@cond + hp::details::hp_array m_arr; + //@endcond }; /// Guarded pointer @@ -441,6 +542,8 @@ namespace cds { namespace gc { return p; } }; + + template friend class guarded_ptr; //@endcond public: @@ -450,26 +553,19 @@ namespace cds { namespace gc { /// Functor for casting \p guarded_type to \p value_type typedef typename std::conditional< std::is_same::value, trivial_cast, Cast >::type value_cast; - //@cond - typedef cds::gc::hp::details::hp_guard native_guard; - //@endcond - - private: - //@cond - native_guard * m_pGuard; - //@endcond - public: /// Creates empty guarded pointer guarded_ptr() CDS_NOEXCEPT : m_pGuard(nullptr) - { - alloc_guard(); - } + {} //@cond + explicit guarded_ptr( hp::details::hp_guard* g ) CDS_NOEXCEPT + : m_pGuard( g ) + {} + /// Initializes guarded pointer with \p p - explicit guarded_ptr( guarded_type * p ) CDS_NOEXCEPT + explicit guarded_ptr( guarded_type* p ) CDS_NOEXCEPT : m_pGuard( nullptr ) { reset(p); @@ -486,31 +582,42 @@ namespace cds { namespace gc { gp.m_pGuard = nullptr; } + /// Move ctor + template + guarded_ptr( guarded_ptr&& gp ) CDS_NOEXCEPT + : m_pGuard( gp.m_pGuard ) + { + gp.m_pGuard = nullptr; + } + + /// Ctor from \p Guard + explicit guarded_ptr( Guard&& g ) CDS_NOEXCEPT + : m_pGuard( g.release() ) + {} + /// The guarded pointer is not copy-constructible guarded_ptr( guarded_ptr const& gp ) = delete; /// Clears the guarded pointer /** - \ref release is called if guarded pointer is not \ref empty + \ref release() is called if guarded pointer is not \ref empty() */ ~guarded_ptr() CDS_NOEXCEPT { - free_guard(); + release(); } /// Move-assignment operator guarded_ptr& operator=( guarded_ptr&& gp ) CDS_NOEXCEPT { - // Hazard Pointer array is organized as a stack - if ( m_pGuard && m_pGuard > gp.m_pGuard ) { - m_pGuard->set( gp.m_pGuard->get(atomics::memory_order_relaxed) ); - gp.free_guard(); - } - else { - free_guard(); - m_pGuard = gp.m_pGuard; - gp.m_pGuard = nullptr; - } + std::swap( m_pGuard, gp.m_pGuard ); + return *this; + } + + /// Move-assignment from \p Guard + guarded_ptr& operator=( Guard&& g ) CDS_NOEXCEPT + { + std::swap( m_pGuard, g.m_guard ); return *this; } @@ -562,13 +669,6 @@ namespace cds { namespace gc { //@cond // For internal use only!!! - native_guard& guard() CDS_NOEXCEPT - { - alloc_guard(); - assert( m_pGuard ); - return *m_pGuard; - } - void reset(guarded_type * p) CDS_NOEXCEPT { alloc_guard(); @@ -582,17 +682,22 @@ namespace cds { namespace gc { void alloc_guard() { if ( !m_pGuard ) - m_pGuard = &thread_gc::alloc_guard(); + m_pGuard = thread_gc::alloc_guard(); } void free_guard() { if ( m_pGuard ) { - thread_gc::free_guard( *m_pGuard ); + thread_gc::free_guard( m_pGuard ); m_pGuard = nullptr; } } //@endcond + + private: + //@cond + hp::details::hp_guard* m_pGuard; + //@endcond }; public: diff --git a/cds/gc/impl/hp_impl.h b/cds/gc/impl/hp_impl.h index 63d9ddea..92bf7493 100644 --- a/cds/gc/impl/hp_impl.h +++ b/cds/gc/impl/hp_impl.h @@ -25,7 +25,7 @@ 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. + OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. */ #ifndef CDSLIB_GC_IMPL_HP_IMPL_H @@ -38,36 +38,10 @@ namespace cds { namespace gc { namespace hp { - inline guard::guard() - : m_hp( cds::threading::getGC().allocGuard() ) - {} - - template - inline guard::guard( T * p ) - : m_hp( cds::threading::getGC().allocGuard() ) + static inline ThreadGC& get_thread_gc() { - m_hp = p; + return cds::threading::getGC(); } - - inline guard::~guard() - { - cds::threading::getGC().freeGuard( m_hp ); - } - - template - inline array::array() - { - cds::threading::getGC().allocGuard( *this ); - } - - template - inline array::~array() - { - cds::threading::getGC().freeGuard( *this ); - } - - - } // namespace hp inline HP::thread_gc::thread_gc( @@ -85,30 +59,71 @@ namespace cds { namespace gc { cds::threading::Manager::detachThread(); } - inline /*static*/ cds::gc::hp::details::hp_guard& HP::thread_gc::alloc_guard() + inline /*static*/ cds::gc::hp::details::hp_guard* HP::thread_gc::alloc_guard() { - return cds::threading::getGC().allocGuard(); + return hp::get_thread_gc().allocGuard(); } - inline /*static*/ void HP::thread_gc::free_guard( cds::gc::hp::details::hp_guard& g ) + inline /*static*/ void HP::thread_gc::free_guard( cds::gc::hp::details::hp_guard* g ) { - cds::threading::getGC().freeGuard( g ); + hp::get_thread_gc().freeGuard( g ); + } + + inline HP::Guard::Guard() + : m_guard( hp::get_thread_gc().allocGuard()) + { + if ( !m_guard ) + throw too_many_hazard_ptr_exception(); } template inline T * HP::Guard::assign( T * p ) { - T * pp = base_class::operator =(p); - cds::threading::getGC().sync(); + assert( m_guard != nullptr ); + + T * pp = ( *m_guard = p ); + hp::get_thread_gc().sync(); return pp; } + inline void HP::Guard::link() + { + if ( !m_guard ) { + m_guard = hp::get_thread_gc().allocGuard(); + if ( !m_guard ) + throw too_many_hazard_ptr_exception(); + } + } + + inline void HP::Guard::unlink() + { + if ( m_guard ) { + hp::get_thread_gc().freeGuard( m_guard ); + m_guard = nullptr; + } + } + + template + inline HP::GuardArray::GuardArray() + { + if ( hp::get_thread_gc().allocGuard( m_arr ) != Count ) + throw too_many_hazard_ptr_exception(); + } + + template + inline HP::GuardArray::~GuardArray() + { + hp::get_thread_gc().freeGuard( m_arr ); + } + template template - inline T * HP::GuardArray::assign( size_t nIndex, T * p ) + inline T * HP::GuardArray::assign( size_t nIndex, T* p ) { - base_class::set(nIndex, p); - cds::threading::getGC().sync(); + assert( nIndex < capacity() ); + + m_arr.set(nIndex, p); + hp::get_thread_gc().sync(); return p; } @@ -121,12 +136,12 @@ namespace cds { namespace gc { template inline void HP::retire( T * p ) { - cds::threading::getGC().retirePtr( p, cds::details::static_functor::call ); + hp::get_thread_gc().retirePtr( p, cds::details::static_functor::call ); } inline void HP::scan() { - cds::threading::getGC().scan(); + hp::get_thread_gc().scan(); } }} // namespace cds::gc diff --git a/cds/intrusive/details/feldman_hashset_base.h b/cds/intrusive/details/feldman_hashset_base.h index 0ac96f12..792dc018 100644 --- a/cds/intrusive/details/feldman_hashset_base.h +++ b/cds/intrusive/details/feldman_hashset_base.h @@ -25,7 +25,7 @@ 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. + OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. */ #ifndef CDSLIB_INTRUSIVE_DETAILS_FELDMAN_HASHSET_BASE_H @@ -300,8 +300,8 @@ namespace cds { namespace intrusive { //@cond namespace details { - template - using hash_splitter = cds::algo::split_bitstring< HashType, UInt >; + template + using hash_splitter = cds::algo::split_bitstring< HashType >; struct metrics { size_t head_node_size; // power-of-two diff --git a/cds/intrusive/ellen_bintree_dhp.h b/cds/intrusive/ellen_bintree_dhp.h index c36729c8..db0ce4d2 100644 --- a/cds/intrusive/ellen_bintree_dhp.h +++ b/cds/intrusive/ellen_bintree_dhp.h @@ -25,7 +25,7 @@ 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. + OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. */ #ifndef CDSLIB_INTRUSIVE_ELLEN_BINTREE_DHP_H diff --git a/cds/intrusive/ellen_bintree_hp.h b/cds/intrusive/ellen_bintree_hp.h index 0f94eb56..1af9a480 100644 --- a/cds/intrusive/ellen_bintree_hp.h +++ b/cds/intrusive/ellen_bintree_hp.h @@ -25,7 +25,7 @@ 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. + OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. */ #ifndef CDSLIB_INTRUSIVE_ELLEN_BINTREE_HP_H diff --git a/cds/intrusive/impl/ellen_bintree.h b/cds/intrusive/impl/ellen_bintree.h index f8f08633..be8f88b0 100644 --- a/cds/intrusive/impl/ellen_bintree.h +++ b/cds/intrusive/impl/ellen_bintree.h @@ -25,7 +25,7 @@ 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. + OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. */ #ifndef CDSLIB_INTRUSIVE_IMPL_ELLEN_BINTREE_H @@ -601,9 +601,7 @@ namespace cds { namespace intrusive { */ guarded_ptr extract_min() { - guarded_ptr gp; - extract_min_( gp.guard() ); - return gp; + return extract_min_(); } /// Extracts an item with maximal key from the tree @@ -622,9 +620,7 @@ namespace cds { namespace intrusive { */ guarded_ptr extract_max() { - guarded_ptr gp; - extract_max_( gp.guard()); - return gp; + return extract_max_(); } /// Extracts an item from the tree @@ -640,9 +636,7 @@ namespace cds { namespace intrusive { template guarded_ptr extract( Q const& key ) { - guarded_ptr gp; - extract_( gp.guard(), key ); - return gp; + return extract_( key ); } /// Extracts an item from the tree using \p pred for searching @@ -656,9 +650,7 @@ namespace cds { namespace intrusive { template guarded_ptr extract_with( Q const& key, Less pred ) { - guarded_ptr gp; - extract_with_( gp.guard(), key, pred ); - return gp; + return extract_with_( key, pred ); } /// Checks whether the set contains \p key @@ -785,9 +777,7 @@ namespace cds { namespace intrusive { template guarded_ptr get( Q const& key ) const { - guarded_ptr gp; - get_( gp.guard(), key ); - return gp; + return get_( key ); } /// Finds \p key with predicate \p pred and returns the item found @@ -801,9 +791,7 @@ namespace cds { namespace intrusive { template guarded_ptr get_with( Q const& key, Less pred ) const { - guarded_ptr gp; - get_with_( gp.guard(), key, pred ); - return gp; + return get_with_( key, pred ); } /// Checks if the tree is empty @@ -1359,16 +1347,62 @@ namespace cds { namespace intrusive { return true; } + template + guarded_ptr extract_item( Q const& key, Compare cmp ) + { + update_desc * pOp = nullptr; + search_result res; + back_off bkoff; + + for ( ;; ) { + if ( !search( res, key, cmp )) { + if ( pOp ) + retire_update_desc( pOp ); + m_Stat.onEraseFailed(); + return guarded_ptr(); + } + + if ( res.updGrandParent.bits() == update_desc::Clean && res.updParent.bits() == update_desc::Clean ) { + if ( !pOp ) + pOp = alloc_update_desc(); + if ( check_delete_precondition( res ) ) { + typename gc::Guard guard; + guard.assign( pOp ); + + pOp->dInfo.pGrandParent = res.pGrandParent; + pOp->dInfo.pParent = res.pParent; + pOp->dInfo.pLeaf = res.pLeaf; + pOp->dInfo.pUpdateParent = res.updParent.ptr(); + pOp->dInfo.bRightParent = res.bRightParent; + pOp->dInfo.bRightLeaf = res.bRightLeaf; + + update_ptr updGP( res.updGrandParent.ptr() ); + if ( res.pGrandParent->m_pUpdate.compare_exchange_strong( updGP, update_ptr( pOp, update_desc::DFlag ), + memory_model::memory_order_acquire, atomics::memory_order_relaxed ) ) { + if ( help_delete( pOp )) + break; + pOp = nullptr; + } + } + } + + bkoff(); + m_Stat.onEraseRetry(); + } + + --m_ItemCounter; + m_Stat.onEraseSuccess(); + return guarded_ptr( res.guards.release( search_result::Guard_Leaf )); + } + template - bool extract_( typename guarded_ptr::native_guard& guard, Q const& key ) + guarded_ptr extract_( Q const& key ) { - return erase_( key, node_compare(), - []( Q const&, leaf_node const& ) -> bool { return true; }, - [&guard]( value_type& found ) { guard.set( &found ); } ); + return extract_item( key, node_compare()); } template - bool extract_with_( typename guarded_ptr::native_guard& guard, Q const& key, Less /*pred*/ ) + guarded_ptr extract_with_( Q const& key, Less /*pred*/ ) { typedef ellen_bintree::details::compare< key_type, @@ -1377,12 +1411,10 @@ namespace cds { namespace intrusive { node_traits > compare_functor; - return erase_( key, compare_functor(), - []( Q const&, leaf_node const& ) -> bool { return true; }, - [&guard]( value_type& found ) { guard.set( &found ); } ); + return extract_item( key, compare_functor()); } - bool extract_max_( typename guarded_ptr::native_guard& gp ) + guarded_ptr extract_max_() { update_desc * pOp = nullptr; search_result res; @@ -1394,7 +1426,7 @@ namespace cds { namespace intrusive { if ( pOp ) retire_update_desc( pOp ); m_Stat.onExtractMaxFailed(); - return false; + return guarded_ptr(); } if ( res.updGrandParent.bits() == update_desc::Clean && res.updParent.bits() == update_desc::Clean ) { @@ -1428,11 +1460,10 @@ namespace cds { namespace intrusive { --m_ItemCounter; m_Stat.onExtractMaxSuccess(); - gp.set( node_traits::to_value_ptr( res.pLeaf )); - return true; + return guarded_ptr( res.guards.release( search_result::Guard_Leaf )); } - bool extract_min_( typename guarded_ptr::native_guard& gp ) + guarded_ptr extract_min_() { update_desc * pOp = nullptr; search_result res; @@ -1444,7 +1475,7 @@ namespace cds { namespace intrusive { if ( pOp ) retire_update_desc( pOp ); m_Stat.onExtractMinFailed(); - return false; + return guarded_ptr(); } if ( res.updGrandParent.bits() == update_desc::Clean && res.updParent.bits() == update_desc::Clean ) { @@ -1478,8 +1509,7 @@ namespace cds { namespace intrusive { --m_ItemCounter; m_Stat.onExtractMinSuccess(); - gp.set( node_traits::to_value_ptr( res.pLeaf )); - return true; + return guarded_ptr( res.guards.release( search_result::Guard_Leaf )); } template @@ -1522,15 +1552,39 @@ namespace cds { namespace intrusive { } template - bool get_( typename guarded_ptr::native_guard& guard, Q const& val ) const + guarded_ptr get_( Q const& val ) const { - return find_( val, [&guard]( value_type& found, Q const& ) { guard.set( &found ); } ); + search_result res; + if ( search( res, val, node_compare() ) ) { + assert( res.pLeaf ); + m_Stat.onFindSuccess(); + return guarded_ptr( res.guards.release( search_result::Guard_Leaf )); + } + + m_Stat.onFindFailed(); + return guarded_ptr(); } template - bool get_with_( typename guarded_ptr::native_guard& guard, Q const& val, Less pred ) const + guarded_ptr get_with_( Q const& val, Less pred ) const { - return find_with_( val, pred, [&guard]( value_type& found, Q const& ) { guard.set( &found ); } ); + typedef ellen_bintree::details::compare< + key_type, + value_type, + opt::details::make_comparator_from_less, + node_traits + > compare_functor; + + search_result res; + if ( search( res, val, compare_functor() ) ) { + assert( res.pLeaf ); + m_Stat.onFindSuccess(); + return guarded_ptr( res.guards.release( search_result::Guard_Leaf )); + } + + m_Stat.onFindFailed(); + return guarded_ptr(); + } //@endcond diff --git a/cds/intrusive/impl/feldman_hashset.h b/cds/intrusive/impl/feldman_hashset.h index 33828773..4078fcf8 100644 --- a/cds/intrusive/impl/feldman_hashset.h +++ b/cds/intrusive/impl/feldman_hashset.h @@ -25,7 +25,7 @@ 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. + OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. */ #ifndef CDSLIB_INTRUSIVE_IMPL_FELDMAN_HASHSET_H @@ -782,16 +782,10 @@ namespace cds { namespace intrusive { */ guarded_ptr extract( hash_type const& hash ) { - guarded_ptr gp; - { - typename gc::Guard guard; - value_type * p = do_erase( hash, guard, []( value_type const&) -> bool {return true;} ); - - // p is guarded by HP - if ( p ) - gp.reset( p ); - } - return gp; + typename gc::Guard guard; + if ( do_erase( hash, guard, []( value_type const&) -> bool {return true;} )) + return guarded_ptr( std::move( guard )); + return guarded_ptr(); } /// Finds an item by it's \p hash @@ -861,12 +855,10 @@ namespace cds { namespace intrusive { */ guarded_ptr get( hash_type const& hash ) { - guarded_ptr gp; - { - typename gc::Guard guard; - gp.reset( search( hash, guard )); - } - return gp; + typename gc::Guard guard; + if ( search( hash, guard )) + return guarded_ptr( std::move( guard )); + return guarded_ptr(); } /// Clears the set (non-atomic) diff --git a/cds/intrusive/impl/iterable_list.h b/cds/intrusive/impl/iterable_list.h index 603d3015..ea051c88 100644 --- a/cds/intrusive/impl/iterable_list.h +++ b/cds/intrusive/impl/iterable_list.h @@ -585,7 +585,7 @@ namespace cds { namespace intrusive { ord_list theList; // ... { - ord_list::guarded_ptr gp(theList.extract( 5 )); + ord_list::guarded_ptr gp( theList.extract( 5 )); if ( gp ) { // Deal with gp // ... @@ -597,9 +597,7 @@ namespace cds { namespace intrusive { template guarded_ptr extract( Q const& key ) { - guarded_ptr gp; - extract_at( m_pHead, gp.guard(), key, key_comparator()); - return gp; + return extract_at( m_pHead, key, key_comparator()); } /// Extracts the item using compare functor \p pred @@ -615,9 +613,7 @@ namespace cds { namespace intrusive { guarded_ptr extract_with( Q const& key, Less pred ) { CDS_UNUSED( pred ); - guarded_ptr gp; - extract_at( m_pHead, gp.guard(), key, cds::opt::details::make_comparator_from_less()); - return gp; + return extract_at( m_pHead, key, cds::opt::details::make_comparator_from_less()); } /// Finds \p key in the list @@ -754,9 +750,7 @@ namespace cds { namespace intrusive { template guarded_ptr get( Q const& key ) const { - guarded_ptr gp; - get_at( m_pHead, gp.guard(), key, key_comparator()); - return gp; + return get_at( m_pHead, key, key_comparator()); } /// Finds the \p key and return the item found @@ -772,9 +766,7 @@ namespace cds { namespace intrusive { guarded_ptr get_with( Q const& key, Less pred ) const { CDS_UNUSED( pred ); - guarded_ptr gp; - get_at( m_pHead, gp.guard(), key, cds::opt::details::make_comparator_from_less()); - return gp; + return get_at( m_pHead, key, cds::opt::details::make_comparator_from_less()); } /// Clears the list (thread safe, not atomic) @@ -989,16 +981,16 @@ namespace cds { namespace intrusive { } template - bool extract_at( atomic_node_ptr& refHead, typename guarded_ptr::native_guard& dest, Q const& val, Compare cmp ) + guarded_ptr extract_at( atomic_node_ptr& refHead, Q const& val, Compare cmp ) { position pos; back_off bkoff; while ( search( refHead, val, pos, cmp )) { if ( unlink_node( pos )) { - dest.set( pos.pFound ); --m_ItemCounter; m_Stat.onEraseSuccess(); - return true; + assert( pos.pFound != nullptr ); + return guarded_ptr( std::move( pos.guard )); } else bkoff(); @@ -1007,7 +999,7 @@ namespace cds { namespace intrusive { } m_Stat.onEraseFailed(); - return false; + return guarded_ptr(); } template @@ -1054,17 +1046,16 @@ namespace cds { namespace intrusive { } template - bool get_at( atomic_node_ptr const& refHead, typename guarded_ptr::native_guard& guard, Q const& val, Compare cmp ) const + guarded_ptr get_at( atomic_node_ptr const& refHead, Q const& val, Compare cmp ) const { position pos; if ( search( refHead, val, pos, cmp )) { - guard.set( pos.pFound ); m_Stat.onFindSuccess(); - return true; + return guarded_ptr( std::move( pos.guard )); } m_Stat.onFindFailed(); - return false; + return guarded_ptr(); } //@endcond diff --git a/cds/intrusive/impl/lazy_list.h b/cds/intrusive/impl/lazy_list.h index 845362ae..13fa9b92 100644 --- a/cds/intrusive/impl/lazy_list.h +++ b/cds/intrusive/impl/lazy_list.h @@ -721,9 +721,7 @@ namespace cds { namespace intrusive { template guarded_ptr extract( Q const& key ) { - guarded_ptr gp; - extract_at( &m_Head, gp.guard(), key, key_comparator()); - return gp; + return extract_at( &m_Head, key, key_comparator()); } /// Extracts the item from the list with comparing functor \p pred @@ -739,9 +737,7 @@ namespace cds { namespace intrusive { guarded_ptr extract_with( Q const& key, Less pred ) { CDS_UNUSED( pred ); - guarded_ptr gp; - extract_at( &m_Head, gp.guard(), key, cds::opt::details::make_comparator_from_less()); - return gp; + return extract_at( &m_Head, key, cds::opt::details::make_comparator_from_less()); } /// Finds the key \p key @@ -867,9 +863,7 @@ namespace cds { namespace intrusive { template guarded_ptr get( Q const& key ) { - guarded_ptr gp; - get_at( &m_Head, gp.guard(), key, key_comparator()); - return gp; + return get_at( &m_Head, key, key_comparator()); } /// Finds \p key and return the item found @@ -885,9 +879,7 @@ namespace cds { namespace intrusive { guarded_ptr get_with( Q const& key, Less pred ) { CDS_UNUSED( pred ); - guarded_ptr gp; - get_at( &m_Head, gp.guard(), key, cds::opt::details::make_comparator_from_less()); - return gp; + return get_at( &m_Head, key, cds::opt::details::make_comparator_from_less()); } /// Clears the list @@ -1154,14 +1146,12 @@ namespace cds { namespace intrusive { } template - bool extract_at( node_type * pHead, typename guarded_ptr::native_guard& gp, const Q& val, Compare cmp ) + guarded_ptr extract_at( node_type * pHead, const Q& val, Compare cmp ) { position pos; - if ( erase_at( pHead, val, cmp, [](value_type const &){}, pos )) { - gp.set( pos.guards.template get(position::guard_current_item)); - return true; - } - return false; + if ( erase_at( pHead, val, cmp, [](value_type const &){}, pos )) + return guarded_ptr( pos.guards.release( position::guard_current_item )); + return guarded_ptr(); } template @@ -1201,7 +1191,7 @@ namespace cds { namespace intrusive { } template - bool get_at( node_type * pHead, typename guarded_ptr::native_guard& gp, Q const& val, Compare cmp ) + guarded_ptr get_at( node_type * pHead, Q const& val, Compare cmp ) { position pos; @@ -1210,13 +1200,12 @@ namespace cds { namespace intrusive { && !pos.pCur->is_marked() && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) { - gp.set( pos.guards.template get( position::guard_current_item )); m_Stat.onFindSuccess(); - return true; + return guarded_ptr( pos.guards.release( position::guard_current_item )); } m_Stat.onFindFailed(); - return false; + return guarded_ptr(); } //@endcond diff --git a/cds/intrusive/impl/michael_list.h b/cds/intrusive/impl/michael_list.h index 8e58bf4a..d279a21b 100644 --- a/cds/intrusive/impl/michael_list.h +++ b/cds/intrusive/impl/michael_list.h @@ -732,9 +732,7 @@ namespace cds { namespace intrusive { template guarded_ptr extract( Q const& key ) { - guarded_ptr gp; - extract_at( m_pHead, gp.guard(), key, key_comparator()); - return gp; + return extract_at( m_pHead, key, key_comparator()); } /// Extracts the item using compare functor \p pred @@ -750,9 +748,7 @@ namespace cds { namespace intrusive { guarded_ptr extract_with( Q const& key, Less pred ) { CDS_UNUSED( pred ); - guarded_ptr gp; - extract_at( m_pHead, gp.guard(), key, cds::opt::details::make_comparator_from_less()); - return gp; + return extract_at( m_pHead, key, cds::opt::details::make_comparator_from_less()); } /// Finds \p key in the list @@ -883,9 +879,7 @@ namespace cds { namespace intrusive { template guarded_ptr get( Q const& key ) { - guarded_ptr gp; - get_at( m_pHead, gp.guard(), key, key_comparator()); - return gp; + return get_at( m_pHead, key, key_comparator()); } /// Finds the \p key and return the item found @@ -901,9 +895,7 @@ namespace cds { namespace intrusive { guarded_ptr get_with( Q const& key, Less pred ) { CDS_UNUSED( pred ); - guarded_ptr gp; - get_at( m_pHead, gp.guard(), key, cds::opt::details::make_comparator_from_less()); - return gp; + return get_at( m_pHead, key, cds::opt::details::make_comparator_from_less()); } /// Clears the list @@ -1119,16 +1111,15 @@ namespace cds { namespace intrusive { } template - bool extract_at( atomic_node_ptr& refHead, typename guarded_ptr::native_guard& dest, Q const& val, Compare cmp ) + guarded_ptr extract_at( atomic_node_ptr& refHead, Q const& val, Compare cmp ) { position pos; back_off bkoff; while ( search( refHead, val, pos, cmp )) { if ( unlink_node( pos )) { - dest.set( pos.guards.template get( position::guard_current_item )); --m_ItemCounter; m_Stat.onEraseSuccess(); - return true; + return guarded_ptr( pos.guards.release( position::guard_current_item )); } else bkoff(); @@ -1136,7 +1127,7 @@ namespace cds { namespace intrusive { } m_Stat.onEraseFailed(); - return false; + return guarded_ptr(); } template @@ -1167,17 +1158,16 @@ namespace cds { namespace intrusive { } template - bool get_at( atomic_node_ptr& refHead, typename guarded_ptr::native_guard& guard, Q const& val, Compare cmp ) + guarded_ptr get_at( atomic_node_ptr& refHead, Q const& val, Compare cmp ) { position pos; if ( search( refHead, val, pos, cmp )) { - guard.set( pos.guards.template get( position::guard_current_item )); m_Stat.onFindSuccess(); - return true; + return guarded_ptr( pos.guards.release( position::guard_current_item )); } m_Stat.onFindFailed(); - return false; + return guarded_ptr(); } //@endcond diff --git a/cds/intrusive/impl/skip_list.h b/cds/intrusive/impl/skip_list.h index 57b1037a..8b2f0eae 100644 --- a/cds/intrusive/impl/skip_list.h +++ b/cds/intrusive/impl/skip_list.h @@ -25,7 +25,7 @@ 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. + OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. */ #ifndef CDSLIB_INTRUSIVE_IMPL_SKIP_LIST_H @@ -843,9 +843,12 @@ namespace cds { namespace intrusive { } template - bool get_with_( typename guarded_ptr::native_guard& guard, Q const& val, Compare cmp ) + guarded_ptr get_with_( Q const& val, Compare cmp ) { - return find_with_( val, cmp, [&guard](value_type& found, Q const& ) { guard.set(&found); } ); + guarded_ptr gp; + if ( find_with_( val, cmp, [&gp](value_type& found, Q const& ) { gp.reset(&found); } )) + return gp; + return guarded_ptr(); } template @@ -876,19 +879,19 @@ namespace cds { namespace intrusive { } template - bool extract_( typename guarded_ptr::native_guard& guard, Q const& val, Compare cmp ) + guarded_ptr extract_( Q const& val, Compare cmp ) { position pos; + guarded_ptr gp; for (;;) { if ( !find_position( val, pos, cmp, false ) ) { m_Stat.onExtractFailed(); - guard.clear(); - return false; + return guarded_ptr(); } node_type * pDel = pos.pCur; - guard.set( node_traits::to_value_ptr(pDel)); + gp.reset( node_traits::to_value_ptr( pDel )); assert( cmp( *node_traits::to_value_ptr( pDel ), val ) == 0 ); unsigned int nHeight = pDel->height(); @@ -896,62 +899,62 @@ namespace cds { namespace intrusive { --m_ItemCounter; m_Stat.onRemoveNode( nHeight ); m_Stat.onExtractSuccess(); - return true; + return gp; } m_Stat.onExtractRetry(); } } - bool extract_min_( typename guarded_ptr::native_guard& gDel ) + guarded_ptr extract_min_() { position pos; + guarded_ptr gp; for (;;) { if ( !find_min_position( pos ) ) { // The list is empty m_Stat.onExtractMinFailed(); - gDel.clear(); - return false; + return guarded_ptr(); } node_type * pDel = pos.pCur; unsigned int nHeight = pDel->height(); - gDel.set( node_traits::to_value_ptr(pDel) ); + gp.reset( node_traits::to_value_ptr(pDel) ); if ( try_remove_at( pDel, pos, [](value_type const&) {} )) { --m_ItemCounter; m_Stat.onRemoveNode( nHeight ); m_Stat.onExtractMinSuccess(); - return true; + return gp; } m_Stat.onExtractMinRetry(); } } - bool extract_max_( typename guarded_ptr::native_guard& gDel ) + guarded_ptr extract_max_() { position pos; + guarded_ptr gp; for (;;) { if ( !find_max_position( pos ) ) { // The list is empty m_Stat.onExtractMaxFailed(); - gDel.clear(); - return false; + return guarded_ptr(); } node_type * pDel = pos.pCur; unsigned int nHeight = pDel->height(); - gDel.set( node_traits::to_value_ptr(pDel) ); + gp.reset( node_traits::to_value_ptr(pDel) ); if ( try_remove_at( pDel, pos, [](value_type const&) {} )) { --m_ItemCounter; m_Stat.onRemoveNode( nHeight ); m_Stat.onExtractMaxSuccess(); - return true; + return gp; } m_Stat.onExtractMaxRetry(); @@ -1308,9 +1311,7 @@ namespace cds { namespace intrusive { template guarded_ptr extract( Q const& key ) { - guarded_ptr gp; - extract_( gp.guard(), key, key_comparator() ); - return gp; + return extract_( key, key_comparator() ); } /// Extracts the item from the set with comparing functor \p pred @@ -1326,9 +1327,7 @@ namespace cds { namespace intrusive { guarded_ptr extract_with( Q const& key, Less pred ) { CDS_UNUSED( pred ); - guarded_ptr gp; - extract_( gp.guard(), key, cds::opt::details::make_comparator_from_less() ); - return gp; + return extract_( key, cds::opt::details::make_comparator_from_less() ); } /// Extracts an item with minimal key from the list @@ -1363,9 +1362,7 @@ namespace cds { namespace intrusive { */ guarded_ptr extract_min() { - guarded_ptr gp; - extract_min_( gp.guard() ); - return gp; + return extract_min_(); } /// Extracts an item with maximal key from the list @@ -1401,9 +1398,7 @@ namespace cds { namespace intrusive { */ guarded_ptr extract_max() { - guarded_ptr gp; - extract_max_( gp.guard() ); - return gp; + return extract_max_(); } /// Deletes the item from the set @@ -1606,9 +1601,7 @@ namespace cds { namespace intrusive { template guarded_ptr get( Q const& key ) { - guarded_ptr gp; - get_with_( gp.guard(), key, key_comparator() ); - return gp; + return get_with_( key, key_comparator() ); } /// Finds \p key and return the item found @@ -1624,9 +1617,7 @@ namespace cds { namespace intrusive { guarded_ptr get_with( Q const& key, Less pred ) { CDS_UNUSED( pred ); - guarded_ptr gp; - get_with_( gp.guard(), key, cds::opt::details::make_comparator_from_less() ); - return gp; + return get_with_( key, cds::opt::details::make_comparator_from_less() ); } /// Returns item count in the set @@ -1662,8 +1653,7 @@ namespace cds { namespace intrusive { */ void clear() { - guarded_ptr gp; - while ( extract_min_( gp.guard() )); + while ( extract_min_()); } /// Returns maximum height of skip-list. The max height is a constant for each object and does not exceed 32. diff --git a/cds/intrusive/split_list.h b/cds/intrusive/split_list.h index ad45c064..f4fce634 100644 --- a/cds/intrusive/split_list.h +++ b/cds/intrusive/split_list.h @@ -330,11 +330,11 @@ namespace cds { namespace intrusive { } template - bool extract_at( dummy_node_type * pHead, typename guarded_ptr::native_guard& guard, split_list::details::search_value_type const& val, Compare cmp ) + guarded_ptr extract_at( dummy_node_type * pHead, split_list::details::search_value_type const& val, Compare cmp ) { assert( pHead != nullptr ); bucket_head_type h(pHead); - return base_class::extract_at( h, guard, val, cmp ); + return base_class::extract_at( h, val, cmp ); } template @@ -354,11 +354,11 @@ namespace cds { namespace intrusive { } template - bool get_at( dummy_node_type * pHead, typename guarded_ptr::native_guard& guard, split_list::details::search_value_type const& val, Compare cmp ) + guarded_ptr get_at( dummy_node_type * pHead, split_list::details::search_value_type const& val, Compare cmp ) { assert( pHead != nullptr ); bucket_head_type h(pHead); - return base_class::get_at( h, guard, val, cmp ); + return base_class::get_at( h, val, cmp ); } bool insert_aux_node( dummy_node_type * pNode ) @@ -539,26 +539,28 @@ namespace cds { namespace intrusive { } template - bool get_( typename guarded_ptr::native_guard& guard, Q const& val, Compare cmp ) + guarded_ptr get_( Q const& val, Compare cmp ) { size_t nHash = hash_value( val ); split_list::details::search_value_type sv( val, split_list::regular_hash( nHash )); dummy_node_type * pHead = get_bucket( nHash ); assert( pHead != nullptr ); - return m_Stat.onFind( m_List.get_at( pHead, guard, sv, cmp )); + guarded_ptr gp = m_List.get_at( pHead, sv, cmp ); + m_Stat.onFind( !gp.empty() ); + return gp; } template - bool get_( typename guarded_ptr::native_guard& guard, Q const& key ) + guarded_ptr get_( Q const& key ) { - return get_( guard, key, key_comparator()); + return get_( key, key_comparator()); } template - bool get_with_( typename guarded_ptr::native_guard& guard, Q const& key, Less ) + guarded_ptr get_with_( Q const& key, Less ) { - return get_( guard, key, typename wrapped_ordered_list::template make_compare_from_less()); + return get_( key, typename wrapped_ordered_list::template make_compare_from_less()); } template @@ -596,32 +598,33 @@ namespace cds { namespace intrusive { } template - bool extract_( typename guarded_ptr::native_guard& guard, Q const& val, Compare cmp ) + guarded_ptr extract_( Q const& val, Compare cmp ) { size_t nHash = hash_value( val ); split_list::details::search_value_type sv( val, split_list::regular_hash( nHash )); dummy_node_type * pHead = get_bucket( nHash ); assert( pHead != nullptr ); - if ( m_List.extract_at( pHead, guard, sv, cmp )) { + guarded_ptr gp = m_List.extract_at( pHead, sv, cmp ); + if ( gp ) { --m_ItemCounter; m_Stat.onExtractSuccess(); - return true; } - m_Stat.onExtractFailed(); - return false; + else + m_Stat.onExtractFailed(); + return gp; } template - bool extract_( typename guarded_ptr::native_guard& guard, Q const& key ) + guarded_ptr extract_( Q const& key ) { - return extract_( guard, key, key_comparator()); + return extract_( key, key_comparator()); } template - bool extract_with_( typename guarded_ptr::native_guard& guard, Q const& key, Less ) + guarded_ptr extract_with_( Q const& key, Less ) { - return extract_( guard, key, typename wrapped_ordered_list::template make_compare_from_less()); + return extract_( key, typename wrapped_ordered_list::template make_compare_from_less()); } //@endcond @@ -898,9 +901,7 @@ namespace cds { namespace intrusive { template guarded_ptr extract( Q const& key ) { - guarded_ptr gp; - extract_( gp.guard(), key ); - return gp; + return extract_( key ); } /// Extracts the item using compare functor \p pred @@ -915,9 +916,7 @@ namespace cds { namespace intrusive { template guarded_ptr extract_with( Q const& key, Less pred ) { - guarded_ptr gp; - extract_with_( gp.guard(), key, pred ); - return gp; + return extract_with_( key, pred ); } /// Finds the key \p key @@ -1052,9 +1051,7 @@ namespace cds { namespace intrusive { template guarded_ptr get( Q const& key ) { - guarded_ptr gp; - get_( gp.guard(), key ); - return gp; + return get_( key ); } /// Finds the key \p key and return the item found @@ -1069,9 +1066,7 @@ namespace cds { namespace intrusive { template guarded_ptr get_with( Q const& key, Less pred ) { - guarded_ptr gp; - get_with_( gp.guard(), key, pred ); - return gp; + return get_with_( key, pred ); } /// Returns item count in the set diff --git a/projects/Win/vc14/stress-set-insdelfind.vcxproj b/projects/Win/vc14/stress-set-insdelfind.vcxproj index c760a82e..e7cb6e8f 100644 --- a/projects/Win/vc14/stress-set-insdelfind.vcxproj +++ b/projects/Win/vc14/stress-set-insdelfind.vcxproj @@ -163,7 +163,7 @@ NotUsing Level3 Disabled - _ENABLE_ATOMIC_ALIGNMENT_FIX;CDSUNIT_USE_URCU;WIN32;_DEBUG;_CONSOLE;%(PreprocessorDefinitions) + _ENABLE_ATOMIC_ALIGNMENT_FIX;CDSUNIT_USE_URCU;_SCL_SECURE_NO_WARNINGS;WIN32;_DEBUG;_CONSOLE;%(PreprocessorDefinitions) $(SolutionDir)..\..\..;$(GTEST_ROOT)/include;$(SolutionDir)..\..\..\test\include;$(SolutionDir)..\..\..\test\stress\set;$(SolutionDir)..\..\..\test\stress\;$(BOOST_PATH);%(AdditionalIncludeDirectories) /bigobj %(AdditionalOptions) @@ -179,7 +179,7 @@ NotUsing Level3 Disabled - _ENABLE_ATOMIC_ALIGNMENT_FIX;CDSUNIT_USE_URCU;WIN32;_DEBUG;_CONSOLE;%(PreprocessorDefinitions) + _ENABLE_ATOMIC_ALIGNMENT_FIX;CDSUNIT_USE_URCU;_SCL_SECURE_NO_WARNINGS;WIN32;_DEBUG;_CONSOLE;%(PreprocessorDefinitions) $(SolutionDir)..\..\..;$(GTEST_ROOT)/include;$(SolutionDir)..\..\..\test\include;$(SolutionDir)..\..\..\test\stress\set;$(SolutionDir)..\..\..\test\stress\;$(BOOST_PATH);%(AdditionalIncludeDirectories) /bigobj %(AdditionalOptions) @@ -195,7 +195,7 @@ NotUsing Level3 Disabled - _ENABLE_ATOMIC_ALIGNMENT_FIX;CDSUNIT_USE_URCU;_DEBUG;_CONSOLE;%(PreprocessorDefinitions) + _ENABLE_ATOMIC_ALIGNMENT_FIX;CDSUNIT_USE_URCU;_SCL_SECURE_NO_WARNINGS;_DEBUG;_CONSOLE;%(PreprocessorDefinitions) $(SolutionDir)..\..\..;$(GTEST_ROOT)/include;$(SolutionDir)..\..\..\test\include;$(SolutionDir)..\..\..\test\stress\set;$(SolutionDir)..\..\..\test\stress\;$(BOOST_PATH);%(AdditionalIncludeDirectories) /bigobj %(AdditionalOptions) @@ -211,7 +211,7 @@ NotUsing Level3 Disabled - _ENABLE_ATOMIC_ALIGNMENT_FIX;CDSUNIT_USE_URCU;_DEBUG;_CONSOLE;%(PreprocessorDefinitions) + _ENABLE_ATOMIC_ALIGNMENT_FIX;CDSUNIT_USE_URCU;_SCL_SECURE_NO_WARNINGS;_DEBUG;_CONSOLE;%(PreprocessorDefinitions) $(SolutionDir)..\..\..;$(GTEST_ROOT)/include;$(SolutionDir)..\..\..\test\include;$(SolutionDir)..\..\..\test\stress\set;$(SolutionDir)..\..\..\test\stress\;$(BOOST_PATH);%(AdditionalIncludeDirectories) /bigobj %(AdditionalOptions) @@ -229,7 +229,7 @@ MaxSpeed true true - _ENABLE_ATOMIC_ALIGNMENT_FIX;CDSUNIT_USE_URCU;WIN32;NDEBUG;_CONSOLE;%(PreprocessorDefinitions) + _ENABLE_ATOMIC_ALIGNMENT_FIX;CDSUNIT_USE_URCU;_SCL_SECURE_NO_WARNINGS;WIN32;NDEBUG;_CONSOLE;%(PreprocessorDefinitions) $(SolutionDir)..\..\..;$(GTEST_ROOT)/include;$(SolutionDir)..\..\..\test\include;$(SolutionDir)..\..\..\test\stress\set;$(SolutionDir)..\..\..\test\stress\;$(BOOST_PATH);%(AdditionalIncludeDirectories) /bigobj %(AdditionalOptions) @@ -249,7 +249,7 @@ MaxSpeed true true - _ENABLE_ATOMIC_ALIGNMENT_FIX;CDSUNIT_USE_URCU;NDEBUG;_CONSOLE;%(PreprocessorDefinitions) + _ENABLE_ATOMIC_ALIGNMENT_FIX;CDSUNIT_USE_URCU;_SCL_SECURE_NO_WARNINGS;NDEBUG;_CONSOLE;%(PreprocessorDefinitions) $(SolutionDir)..\..\..;$(GTEST_ROOT)/include;$(SolutionDir)..\..\..\test\include;$(SolutionDir)..\..\..\test\stress\set;$(SolutionDir)..\..\..\test\stress\;$(BOOST_PATH);%(AdditionalIncludeDirectories) /bigobj %(AdditionalOptions) diff --git a/src/dhp_gc.cpp b/src/dhp_gc.cpp index 665ea996..28f809e7 100644 --- a/src/dhp_gc.cpp +++ b/src/dhp_gc.cpp @@ -25,7 +25,7 @@ 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. + OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. */ // Dynamic Hazard Pointer memory manager implementation @@ -79,42 +79,69 @@ namespace cds { namespace gc { namespace dhp { item_type& refBucket = bucket( node ); if ( refBucket ) { item_type p = refBucket; + item_type prev = nullptr; do { - if ( p->m_ptr.m_p == node.m_ptr.m_p ) { - assert( node.m_pNextFree.load( atomics::memory_order_relaxed ) == nullptr ); - - node.m_pNextFree.store( p->m_pNextFree.load( atomics::memory_order_relaxed ), atomics::memory_order_relaxed ); - p->m_pNextFree.store( &node, atomics::memory_order_relaxed ); + if ( p->m_ptr.m_p >= node.m_ptr.m_p ) { + node.m_pNext.store( p, atomics::memory_order_relaxed ); + if ( prev ) + prev->m_pNext.store( &node, atomics::memory_order_relaxed ); + else + refBucket = &node; return; } + prev = p; p = p->m_pNext.load(atomics::memory_order_relaxed); } while ( p ); - node.m_pNext.store( refBucket, atomics::memory_order_relaxed ); + assert( prev != nullptr ); + prev->m_pNext.store( &node, atomics::memory_order_relaxed ); } - refBucket = &node; + else + refBucket = &node; } - item_type erase( guard_data::guarded_ptr ptr ) + struct erase_result + { + item_type head; + item_type tail; + size_t size; + + erase_result() + : head( nullptr ) + , tail( nullptr ) + , size(0) + {} + }; + + erase_result erase( guard_data::guarded_ptr ptr ) { item_type& refBucket = bucket( ptr ); item_type p = refBucket; item_type pPrev = nullptr; - while ( p ) { + erase_result ret; + while ( p && p->m_ptr.m_p <= ptr ) { if ( p->m_ptr.m_p == ptr ) { if ( pPrev ) pPrev->m_pNext.store( p->m_pNext.load(atomics::memory_order_relaxed ), atomics::memory_order_relaxed ); else refBucket = p->m_pNext.load(atomics::memory_order_relaxed); - p->m_pNext.store( nullptr, atomics::memory_order_relaxed ); - return p; + + if ( ret.head ) + ret.tail->m_pNext.store( p, atomics::memory_order_relaxed ); + else + ret.head = p; + ret.tail = p; + ++ret.size; } - pPrev = p; + else + pPrev = p; p = p->m_pNext.load( atomics::memory_order_relaxed ); } - return nullptr; + if ( ret.tail ) + ret.tail->m_pNext.store( nullptr, atomics::memory_order_relaxed ); + return ret; } typedef std::pair list_range; @@ -128,10 +155,10 @@ namespace cds { namespace gc { namespace dhp { for ( item_type * ppBucket = m_Buckets; ppBucket < pEndBucket; ++ppBucket ) { item_type pBucket = *ppBucket; if ( pBucket ) { - if ( !ret.first ) - ret.first = pBucket; - else + if ( ret.first ) pTail->m_pNextFree.store( pBucket, atomics::memory_order_relaxed ); + else + ret.first = pBucket; pTail = pBucket; for (;;) { @@ -139,11 +166,13 @@ namespace cds { namespace gc { namespace dhp { pTail->m_ptr.free(); pTail->m_pNext.store( nullptr, atomics::memory_order_relaxed ); + /* while ( pTail->m_pNextFree.load( atomics::memory_order_relaxed )) { pTail = pTail->m_pNextFree.load( atomics::memory_order_relaxed ); pTail->m_ptr.free(); pTail->m_pNext.store( nullptr, atomics::memory_order_relaxed ); } + */ if ( pNext ) { pTail->m_pNextFree.store( pNext, atomics::memory_order_relaxed ); @@ -215,8 +244,9 @@ namespace cds { namespace gc { namespace dhp { // Liberate cycle - details::retired_ptr_node * pBusyFirst = nullptr; - details::retired_ptr_node * pBusyLast = nullptr; + details::retired_ptr_node dummy; + dummy.m_pNext.store( nullptr, atomics::memory_order_relaxed ); + details::retired_ptr_node * pBusyLast = &dummy; size_t nBusyCount = 0; for ( details::guard_data * pGuard = m_GuardPool.begin(); pGuard; pGuard = pGuard->pGlobalNext.load(atomics::memory_order_acquire) ) @@ -225,31 +255,21 @@ namespace cds { namespace gc { namespace dhp { details::guard_data::guarded_ptr valGuarded = pGuard->pPost.load(atomics::memory_order_acquire); if ( valGuarded ) { - details::retired_ptr_node * pRetired = set.erase( valGuarded ); - if ( pRetired ) { + auto retired = set.erase( valGuarded ); + if ( retired.head ) { // Retired pointer is being guarded - // pRetired is the head of retired pointers list for which the m_ptr.m_p field is equal - // List is linked on m_pNextFree field + // [retired.head, retired.tail] is the list linked by m_pNext field - if ( pBusyLast ) - pBusyLast->m_pNext.store( pRetired, atomics::memory_order_relaxed ); - else - pBusyFirst = pRetired; - pBusyLast = pRetired; - ++nBusyCount; - details::retired_ptr_node * p = pBusyLast->m_pNextFree.load(atomics::memory_order_relaxed); - while ( p != nullptr ) { - pBusyLast->m_pNext.store( p, atomics::memory_order_relaxed ); - pBusyLast = p; - ++nBusyCount; - } + pBusyLast->m_pNext.store( retired.head, atomics::memory_order_relaxed ); + pBusyLast = retired.tail; + nBusyCount += retired.size; } } } - // Place [pBusyList, pBusyLast] back to m_RetiredBuffer - if ( pBusyFirst ) - m_RetiredBuffer.push_list( pBusyFirst, pBusyLast, nBusyCount ); + // Place [dummy.m_pNext, pBusyLast] back to m_RetiredBuffer + if ( nBusyCount ) + m_RetiredBuffer.push_list( dummy.m_pNext.load(atomics::memory_order_relaxed), pBusyLast, nBusyCount ); // Free all retired pointers details::liberate_set::list_range range = set.free_all(); diff --git a/src/hp_const.h b/src/hp_const.h index 5d65d6a0..48a9150b 100644 --- a/src/hp_const.h +++ b/src/hp_const.h @@ -25,7 +25,7 @@ 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. + OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. */ #ifndef CDSIMPL_HP_CONST_H @@ -35,7 +35,6 @@ File: hp_const.h Michael's Hazard Pointer reclamation schema global constants - Gidenstam's reclamation schema global constants Editions: 2008.03.10 Maxim.Khiszinsky Created @@ -47,10 +46,10 @@ namespace cds { namespace gc { // Hazard Pointers reclamation schema constants namespace hp { // Max number of threads expected - static const size_t c_nMaxThreadCount = 100; + static CDS_CONSTEXPR const size_t c_nMaxThreadCount = 100; // Number of Hazard Pointers per thread - static const size_t c_nHazardPointerPerThread = 8; + static CDS_CONSTEXPR const size_t c_nHazardPointerPerThread = 8; } // namespace hp } /* namespace gc */ } /* namespace cds */ diff --git a/src/hp_gc.cpp b/src/hp_gc.cpp index 99214444..a525c1cf 100644 --- a/src/hp_gc.cpp +++ b/src/hp_gc.cpp @@ -25,7 +25,7 @@ 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. + OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. */ /* @@ -195,7 +195,7 @@ namespace cds { namespace gc { while ( pNode ) { for ( size_t i = 0; i < m_nHazardPointerCount; ++i ) { pRec->sync(); - void * hptr = pNode->m_hzp[i]; + void * hptr = pNode->m_hzp[i].get(); if ( hptr ) plist.push_back( hptr ); } @@ -277,7 +277,7 @@ namespace cds { namespace gc { if ( !pNode->m_bFree.load( atomics::memory_order_acquire ) ) { for ( size_t i = 0; i < m_nHazardPointerCount; ++i ) { pRec->sync(); - void * hptr = pNode->m_hzp[i]; + void * hptr = pNode->m_hzp[i].get(); if ( hptr ) { dummyRetired.m_p = hptr; details::retired_vector::iterator it = std::lower_bound( itRetired, itRetiredEnd, dummyRetired, cds::gc::details::retired_ptr::less ); diff --git a/test/unit/list/test_intrusive_iterable_list.h b/test/unit/list/test_intrusive_iterable_list.h index 8416a4c4..1db06f9c 100644 --- a/test/unit/list/test_intrusive_iterable_list.h +++ b/test/unit/list/test_intrusive_iterable_list.h @@ -357,6 +357,9 @@ namespace cds_test { EXPECT_EQ( i.s.nUpdateExistsCall, 1 ); } + // Apply retired pointer to clean links + List::gc::force_dispose(); + for ( auto& i : arr ) { EXPECT_EQ( i.s.nUpdateExistsCall, 0 ); std::pair ret = l.update( i, []( value_type& i, value_type * old ) { diff --git a/test/unit/set/test_feldman_hashset.h b/test/unit/set/test_feldman_hashset.h index 1bfbe3a0..b1c76b07 100644 --- a/test/unit/set/test_feldman_hashset.h +++ b/test/unit/set/test_feldman_hashset.h @@ -25,7 +25,7 @@ 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. + OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. */ #ifndef CDSUNIT_SET_TEST_FELDMAN_HASHSET_H diff --git a/test/unit/set/test_feldman_hashset_hp.h b/test/unit/set/test_feldman_hashset_hp.h index aa06b343..ecc13827 100644 --- a/test/unit/set/test_feldman_hashset_hp.h +++ b/test/unit/set/test_feldman_hashset_hp.h @@ -25,7 +25,7 @@ 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. + OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. */ #ifndef CDSUNIT_SET_TEST_FELDMAN_HASHSET_HP_H -- 2.34.1