X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=cds%2Fcontainer%2Fimpl%2Fmichael_list.h;h=aa3a7c8dc53d8745149df98293f657e744dd0c51;hb=4701cf9c56d5553f21bafcf9c9f659a52d91a781;hp=17224e31d5d5a1488af0c568b4fc17d1844325d5;hpb=1c4e300439ce894a5a861c6db8ac04d6b1a90318;p=libcds.git diff --git a/cds/container/impl/michael_list.h b/cds/container/impl/michael_list.h index 17224e31..aa3a7c8d 100644 --- a/cds/container/impl/michael_list.h +++ b/cds/container/impl/michael_list.h @@ -1,7 +1,7 @@ //$$CDS-header$$ -#ifndef __CDS_CONTAINER_IMPL_MICHAEL_LIST_H -#define __CDS_CONTAINER_IMPL_MICHAEL_LIST_H +#ifndef CDSLIB_CONTAINER_IMPL_MICHAEL_LIST_H +#define CDSLIB_CONTAINER_IMPL_MICHAEL_LIST_H #include #include @@ -13,7 +13,7 @@ namespace cds { namespace container { \anchor cds_nonintrusive_MichaelList_gc Usually, ordered single-linked list is used as a building block for the hash table implementation. - The complexity of searching is O(N), where \p N is the item count in the list, not in the + The complexity of searching is O(N), where \p N is the item count in the list, not in the hash table. Source: @@ -121,7 +121,7 @@ namespace cds { namespace container { public: /// Guarded pointer - typedef cds::gc::guarded_ptr< gc, node_type, value_type, details::guarded_ptr_cast_set > guarded_ptr; + typedef typename gc::template guarded_ptr< node_type, value_type, details::guarded_ptr_cast_set > guarded_ptr; private: //@cond @@ -234,7 +234,7 @@ namespace cds { namespace container { The forward iterator for Michael's list has some features: - it has no post-increment operator - to protect the value, the iterator contains a GC-specific guard + another guard is required locally for increment operator. - For some GC (gc::HP, gc::HRC), a guard is limited resource per thread, so an exception (or assertion) "no free guard" + For some GC (\p gc::HP), a guard is limited resource per thread, so an exception (or assertion) "no free guard" may be thrown if a limit of guard count per thread is exceeded. - The iterator cannot be moved across thread boundary since it contains GC's guard that is thread-private GC data. - Iterator ensures thread-safety even if you delete the item that iterator points to. However, in case of concurrent @@ -279,7 +279,7 @@ namespace cds { namespace container { { return const_iterator( head() ); } - const_iterator cbegin() + const_iterator cbegin() const { return const_iterator( head() ); } @@ -291,7 +291,7 @@ namespace cds { namespace container { { return const_iterator(); } - const_iterator cend() + const_iterator cend() const { return const_iterator(); } @@ -433,6 +433,7 @@ namespace cds { namespace container { template bool erase_with( Q const& key, Less pred ) { + CDS_UNUSED( pred ); return erase_at( head(), key, typename maker::template less_wrapper::type(), [](value_type const&){} ); } @@ -447,7 +448,6 @@ namespace cds { namespace container { void operator()(const value_type& val) { ... } }; \endcode - The functor may be passed by reference with boost:ref Since the key of MichaelList's item type \p value_type is not explicitly specified, template parameter \p Q should contain the complete key to search in the list. @@ -472,14 +472,15 @@ namespace cds { namespace container { template bool erase_with( Q const& key, Less pred, Func f ) { + CDS_UNUSED( pred ); return erase_at( head(), key, typename maker::template less_wrapper::type(), f ); } /// Extracts the item from the list with specified \p key /** \anchor cds_nonintrusive_MichaelList_hp_extract The function searches an item with key equal to \p key, - unlinks it from the list, and returns it in \p dest parameter. - If the item with key equal to \p key is not found the function returns \p false. + unlinks it from the list, and returns it as \p guarded_ptr. + If \p key is not found the function returns an empty guarded pointer. Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type. @@ -491,24 +492,26 @@ namespace cds { namespace container { ord_list theList; // ... { - ord_list::guarded_ptr gp; - theList.extract( gp, 5 ); - // Deal with gp - // ... - + ord_list::guarded_ptr gp(theList.extract( 5 )); + if ( gp ) { + // Deal with gp + // ... + } // Destructor of gp releases internal HP guard and frees the item } \endcode */ template - bool extract( guarded_ptr& dest, Q const& key ) + guarded_ptr extract( Q const& key ) { - return extract_at( head(), dest.guard(), key, intrusive_key_comparator() ); + guarded_ptr gp; + extract_at( head(), gp.guard(), key, intrusive_key_comparator() ); + return gp; } /// Extracts the item from the list with comparing functor \p pred /** - The function is an analog of \ref cds_nonintrusive_MichaelList_hp_extract "extract(guarded_ptr&, Q const&)" + The function is an analog of \ref cds_nonintrusive_MichaelList_hp_extract "extract(Q const&)" but \p pred predicate is used for key comparing. \p Less functor has the semantics like \p std::less but it should accept arguments of type \p value_type and \p Q @@ -516,9 +519,12 @@ namespace cds { namespace container { \p pred must imply the same element order as the comparator used for building the list. */ template - bool extract_with( guarded_ptr& dest, Q const& key, Less pred ) + guarded_ptr extract_with( Q const& key, Less pred ) { - return extract_at( head(), dest.guard(), key, typename maker::template less_wrapper::type() ); + CDS_UNUSED( pred ); + guarded_ptr gp; + extract_at( head(), gp.guard(), key, typename maker::template less_wrapper::type() ); + return gp; } /// Finds \p key @@ -542,6 +548,7 @@ namespace cds { namespace container { template bool find_with( Q const& key, Less pred ) { + CDS_UNUSED( pred ); return find_at( head(), key, typename maker::template less_wrapper::type() ); } @@ -568,6 +575,13 @@ namespace cds { namespace container { { return find_at( head(), key, intrusive_key_comparator(), f ); } + //@cond + template + bool find( Q const& key, Func f ) + { + return find_at( head(), key, intrusive_key_comparator(), f ); + } + //@endcond /// Finds \p key using \p pred predicate for searching /** @@ -579,15 +593,23 @@ namespace cds { namespace container { template bool find_with( Q& key, Less pred, Func f ) { + CDS_UNUSED( pred ); return find_at( head(), key, typename maker::template less_wrapper::type(), f ); } + //@cond + template + bool find_with( Q const& key, Less pred, Func f ) + { + CDS_UNUSED( pred ); + return find_at( head(), key, typename maker::template less_wrapper::type(), f ); + } + //@endcond /// Finds \p key and return the item found /** \anchor cds_nonintrusive_MichaelList_hp_get The function searches the item with key equal to \p key - and assigns the item found to guarded pointer \p ptr. - The function returns \p true if \p key is found, and \p false otherwise. - If \p key is not found the \p ptr parameter is not changed. + and returns it as \p guarded_ptr. + If \p key is not found the function returns an empty guarded pointer. @note Each \p guarded_ptr object uses one GC's guard which can be limited resource. @@ -597,8 +619,8 @@ namespace cds { namespace container { ord_list theList; // ... { - ord_list::guarded_ptr gp; - if ( theList.get( gp, 5 )) { + ord_list::guarded_ptr gp(theList.get( 5 )); + if ( gp ) { // Deal with gp //... } @@ -610,14 +632,16 @@ namespace cds { namespace container { should accept a parameter of type \p Q that can be not the same as \p value_type. */ template - bool get( guarded_ptr& ptr, Q const& key ) + guarded_ptr get( Q const& key ) { - return get_at( head(), ptr.guard(), key, intrusive_key_comparator() ); + guarded_ptr gp; + get_at( head(), gp.guard(), key, intrusive_key_comparator() ); + return gp; } /// Finds \p key and return the item found /** - The function is an analog of \ref cds_nonintrusive_MichaelList_hp_get "get( guarded_ptr& ptr, Q const&)" + The function is an analog of \ref cds_nonintrusive_MichaelList_hp_get "get( Q const&)" but \p pred is used for comparing the keys. \p Less functor has the semantics like \p std::less but should accept arguments of type \p value_type and \p Q @@ -625,9 +649,12 @@ namespace cds { namespace container { \p pred must imply the same element order as the comparator used for building the list. */ template - bool get_with( guarded_ptr& ptr, Q const& key, Less pred ) + guarded_ptr get_with( Q const& key, Less pred ) { - return get_at( head(), ptr.guard(), key, typename maker::template less_wrapper::type() ); + CDS_UNUSED( pred ); + guarded_ptr gp; + get_at( head(), gp.guard(), key, typename maker::template less_wrapper::type() ); + return gp; } /// Check if the list is empty @@ -700,9 +727,9 @@ namespace cds { namespace container { } template - bool extract_at( head_type& refHead, typename gc::Guard& dest, Q const& key, Compare cmp ) + bool extract_at( head_type& refHead, typename guarded_ptr::native_guard& guard, Q const& key, Compare cmp ) { - return base_class::extract_at( refHead, dest, key, cmp ); + return base_class::extract_at( refHead, guard, key, cmp ); } template @@ -731,7 +758,7 @@ namespace cds { namespace container { } template - bool get_at( head_type& refHead, typename gc::Guard& guard, Q const& key, Compare cmp ) + bool get_at( head_type& refHead, typename guarded_ptr::native_guard& guard, Q const& key, Compare cmp ) { return base_class::get_at( refHead, guard, key, cmp ); } @@ -741,4 +768,4 @@ namespace cds { namespace container { }} // namespace cds::container -#endif // #ifndef __CDS_CONTAINER_IMPL_MICHAEL_LIST_H +#endif // #ifndef CDSLIB_CONTAINER_IMPL_MICHAEL_LIST_H