X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=cds%2Fintrusive%2Flazy_list_nogc.h;h=2c9761f54fb209b02a807badb233f6366b0fef74;hb=df4d0c52b3eff17a49505093870a37ea8c9d565d;hp=a50e742a5608b183505f1e6a761caf87c6c12b71;hpb=1503681e52c392bee2329cf66c910be0f8640105;p=libcds.git diff --git a/cds/intrusive/lazy_list_nogc.h b/cds/intrusive/lazy_list_nogc.h index a50e742a..2c9761f5 100644 --- a/cds/intrusive/lazy_list_nogc.h +++ b/cds/intrusive/lazy_list_nogc.h @@ -1,27 +1,65 @@ -//$$CDS-header$$ +/* + This file is a part of libcds - Concurrent Data Structures library -#ifndef __CDS_INTRUSIVE_LAZY_LIST_NOGC_H -#define __CDS_INTRUSIVE_LAZY_LIST_NOGC_H + (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2017 + Source code repo: http://github.com/khizmax/libcds/ + Download: http://sourceforge.net/projects/libcds/files/ + + Redistribution and use in source and binary forms, with or without + modification, are permitted provided that the following conditions are met: + + * Redistributions of source code must retain the above copyright notice, this + list of conditions and the following disclaimer. + + * Redistributions in binary form must reproduce the above copyright notice, + this list of conditions and the following disclaimer in the documentation + and/or other materials provided with the distribution. + + THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" + AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE + FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR + 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. +*/ + +#ifndef CDSLIB_INTRUSIVE_LAZY_LIST_NOGC_H +#define CDSLIB_INTRUSIVE_LAZY_LIST_NOGC_H + +#include // unique_lock #include #include namespace cds { namespace intrusive { namespace lazy_list { - /// Lazy list node for gc::nogc + /// Lazy list node for \p gc::nogc /** Template parameters: - - Tag - a tag used to distinguish between different implementation + - Lock - lock type. Default is \p cds::sync::spin + - Tag - a \ref cds_intrusive_hook_tag "tag" */ - template + template < +#ifdef CDS_DOXYGEN_INVOKED + typename Lock = cds::sync::spin, + typename Tag = opt::none +#else + typename Lock, + typename Tag +#endif + > struct node { - typedef gc::nogc gc ; ///< Garbage collector - typedef Lock lock_type ; ///< Lock type - typedef Tag tag ; ///< tag + typedef gc::nogc gc; ///< Garbage collector + typedef Lock lock_type; ///< Lock type + typedef Tag tag; ///< tag - atomics::atomic m_pNext ; ///< pointer to the next node in the list - mutable lock_type m_Lock ; ///< Node lock + atomics::atomic m_pNext; ///< pointer to the next node in the list + mutable lock_type m_Lock; ///< Node lock node() : m_pNext( nullptr ) @@ -30,39 +68,24 @@ namespace cds { namespace intrusive { } // namespace lazy_list - /// Lazy ordered single-linked list (template specialization for gc::nogc) + /// Lazy single-linked list (template specialization for \p gc::nogc) /** @ingroup cds_intrusive_list \anchor cds_intrusive_LazyList_nogc - This specialization is intended for so-called persistent usage when no item + This specialization is append-only list when no item reclamation may be performed. The class does not support deleting of list item. - See \ref cds_intrusive_LazyList_hp "LazyList" for description of template parameters. - - The interface of the specialization is a slightly different. - - The gc::nogc specialization of LazyList accepts following template argument list - \p Options of cds::intrusive::lazy_list::make_traits metafunction: - - opt::hook - hook used. Possible values are: lazy_list::base_hook, lazy_list::member_hook, lazy_list::traits_hook. - If the option is not specified, lazy_list::base_hook<> and gc::HP is used. - - opt::compare - key comparison functor. No default functor is provided. - If the option is not specified, the opt::less is used. - - opt::less - specifies binary predicate used for key comparison. Default is \p std::less. - - opt::back_off - back-off strategy used. If the option is not specified, the cds::backoff::empty is used. - - opt::disposer - the functor used for dispose removed items. Default is opt::v::empty_disposer. The disposer - provided is used only in \ref clear() function. - - opt::link_checker - the type of node's link fields checking. Default is \ref opt::debug_check_link - - opt::item_counter - the type of item counting feature. Default is \ref atomicity::empty_item_counter that is no item counting. - - opt::memory_model - C++ memory ordering model. Can be opt::v::relaxed_ordering (relaxed memory model, the default) - or opt::v::sequential_consistent (sequentially consisnent memory model). - - The opt::allocator and opt::back_off is not used for this specialization. + The list can be ordered if \p Traits::sort is \p true that is default + or unordered otherwise. Unordered list can be maintained by \p equal_to + relationship (\p Traits::equal_to), but for the ordered list \p less + or \p compare relations should be specified in \p Traits. + See \ref cds_intrusive_LazyList_hp "LazyList" for description of template parameters. */ template < typename T #ifdef CDS_DOXYGEN_INVOKED - ,class Traits = lazy_list::type_traits + ,class Traits = lazy_list::traits #else ,class Traits #endif @@ -70,46 +93,62 @@ namespace cds { namespace intrusive { class LazyList { public: - typedef T value_type ; ///< type of value stored in the list - typedef Traits options ; ///< Traits template parameter + typedef gc::nogc gc; ///< Garbage collector + typedef T value_type; ///< type of value stored in the list + typedef Traits traits; ///< Traits template parameter - typedef typename options::hook hook ; ///< hook type - typedef typename hook::node_type node_type ; ///< node type + typedef typename traits::hook hook; ///< hook type + typedef typename hook::node_type node_type; ///< node type + static CDS_CONSTEXPR bool const c_bSort = traits::sort; ///< List type: ordered (\p true) or unordered (\p false) # ifdef CDS_DOXYGEN_INVOKED - typedef implementation_defined key_comparator ; ///< key comparison functor based on opt::compare and opt::less option setter. + /// Key comparing functor + /** + - for ordered list, the functor is based on \p traits::compare or \p traits::less + - for unordered list, the functor is based on \p traits::equal_to, \p traits::compare or \p traits::less + */ + typedef implementation_defined key_comparator; # else - typedef typename opt::details::make_comparator< value_type, options >::type key_comparator; + typedef typename std::conditional< c_bSort, + typename opt::details::make_comparator< value_type, traits >::type, + typename opt::details::make_equal_to< value_type, traits >::type + >::type key_comparator; # endif + typedef typename traits::back_off back_off; ///< Back-off strategy + typedef typename traits::disposer disposer; ///< disposer + typedef typename get_node_traits< value_type, node_type, hook>::type node_traits; ///< node traits + typedef typename lazy_list::get_link_checker< node_type, traits::link_checker >::type link_checker; ///< link checker - typedef typename options::disposer disposer ; ///< disposer used - typedef typename get_node_traits< value_type, node_type, hook>::type node_traits ; ///< node traits - typedef typename lazy_list::get_link_checker< node_type, options::link_checker >::type link_checker ; ///< link checker - - typedef gc::nogc gc ; ///< Garbage collector - typedef typename options::back_off back_off ; ///< back-off strategy (not used) - typedef typename options::item_counter item_counter ; ///< Item counting policy used - typedef typename options::memory_model memory_model; ///< C++ memory ordering (see lazy_list::type_traits::memory_model) + typedef typename traits::item_counter item_counter; ///< Item counting policy used + typedef typename traits::memory_model memory_model; ///< C++ memory ordering (see \p lazy_list::traits::memory_model) + typedef typename traits::stat stat; ///< Internal statistics //@cond - // Rebind options (split-list support) + static_assert((std::is_same< gc, typename node_type::gc >::value), "GC and node_type::gc must be the same type"); + + // Rebind traits (split-list support) template - struct rebind_options { + struct rebind_traits { typedef LazyList< gc , value_type - , typename cds::opt::make_options< options, Options...>::type + , typename cds::opt::make_options< traits, Options...>::type > type; }; + + // Stat selector + template + using select_stat_wrapper = lazy_list::select_stat_wrapper< Stat >; //@endcond protected: typedef node_type * auxiliary_head ; ///< Auxiliary head type (for split-list support) protected: - node_type m_Head ; ///< List head (dummy node) - node_type m_Tail; ///< List tail (dummy node) - item_counter m_ItemCounter ; ///< Item counter + node_type m_Head; ///< List head (dummy node) + node_type m_Tail; ///< List tail (dummy node) + item_counter m_ItemCounter; ///< Item counter + mutable stat m_Stat; ///< Internal statistics //@cond @@ -170,6 +209,7 @@ namespace cds { namespace intrusive { void link_node( node_type * pNode, node_type * pPred, node_type * pCur ) { + link_checker::is_empty( pNode ); assert( pPred->m_pNext.load(memory_model::memory_order_relaxed) == pCur ); pNode->m_pNext.store( pCur, memory_model::memory_order_release ); @@ -291,31 +331,47 @@ namespace cds { namespace intrusive { /// Returns a forward const iterator addressing the first element in a list const_iterator begin() const { - const_iterator it( const_cast( &m_Head )); - ++it ; // skip dummy head + return cbegin(); + } + /// Returns a forward const iterator addressing the first element in a list + const_iterator cbegin() const + { + const_iterator it( const_cast(&m_Head)); + ++it; // skip dummy head return it; } /// Returns an const iterator that addresses the location succeeding the last element in a list const_iterator end() const { - return const_iterator( const_cast( &m_Tail )); + return cend(); + } + /// Returns an const iterator that addresses the location succeeding the last element in a list + const_iterator cend() const + { + return const_iterator( const_cast(&m_Tail)); } public: /// Default constructor initializes empty list LazyList() { - static_assert( (std::is_same< gc, typename node_type::gc >::value), "GC and node_type::gc must be the same type" ); + m_Head.m_pNext.store( &m_Tail, memory_model::memory_order_relaxed ); + } + //@cond + template >::value >> + explicit LazyList( Stat& st ) + : m_Stat( st ) + { m_Head.m_pNext.store( &m_Tail, memory_model::memory_order_relaxed ); } + //@endcond /// Destroys the list object ~LazyList() { clear(); - assert( m_Head.m_pNext.load(memory_model::memory_order_relaxed) == &m_Tail ); m_Head.m_pNext.store( nullptr, memory_model::memory_order_relaxed ); } @@ -332,11 +388,12 @@ namespace cds { namespace intrusive { return insert_at( &m_Head, val ); } - /// Ensures that the \p item exists in the list + /// Updates the item /** The operation performs inserting or changing data with lock-free manner. - If the item \p val not found in the list, then \p val is inserted into the list. + If the item \p val not found in the list, then \p val is inserted into the list + iff \p bAllowInsert is \p true. Otherwise, the functor \p func is called with item found. The functor signature is: \code @@ -347,125 +404,161 @@ namespace cds { namespace intrusive { with arguments: - \p bNew - \p true if the item has been inserted, \p false otherwise - \p item - item of the list - - \p val - argument \p val passed into the \p ensure function + - \p val - argument \p val passed into the \p update() function If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments - refers to the same thing. + refer to the same thing. The functor may change non-key fields of the \p item. While the functor \p f is calling the item \p item is locked. - You may pass \p func argument by reference using \p std::ref. - - Returns std::pair where \p first is true if operation is successfull, - \p second is true if new item has been added or \p false if the item with \p key + Returns std::pair where \p first is \p true if operation is successful, + \p second is \p true if new item has been added or \p false if the item with \p key already is in the list. */ - template + std::pair update( value_type& val, Func func, bool bAllowInsert = true ) + { + return update_at( &m_Head, val, func, bAllowInsert ); + } + //@cond + template + CDS_DEPRECATED("ensure() is deprecated, use update()") std::pair ensure( value_type& val, Func func ) { - return ensure_at( &m_Head, val, func ); + return update( val, func, true ); } + //@endcond - /// Finds the key \p val + /// Finds the key \p key /** \anchor cds_intrusive_LazyList_nogc_find_func - The function searches the item with key equal to \p val + The function searches the item with key equal to \p key and calls the functor \p f for item found. The interface of \p Func functor is: \code struct functor { - void operator()( value_type& item, Q& val ); + void operator()( value_type& item, Q& key ); }; \endcode - where \p item is the item found, \p val is the find function argument. - - You may pass \p f argument by reference using \p std::ref. + where \p item is the item found, \p key is the find function argument. The functor may change non-key fields of \p item. While the functor \p f is calling the item found \p item is locked. - The function returns \p true if \p val is found, \p false otherwise. + The function returns \p true if \p key is found, \p false otherwise. */ template - bool find( Q& val, Func f ) + bool find( Q& key, Func f ) { - return find_at( &m_Head, val, key_comparator(), f ); + return find_at( &m_Head, key, key_comparator(), f ); } - - /// Finds the key \p val - /** \anchor cds_intrusive_LazyList_nogc_find_cfunc - The function searches the item with key equal to \p val - and calls the functor \p f for item found. - The interface of \p Func functor is: - \code - struct functor { - void operator()( value_type& item, Q const& val ); - }; - \endcode - where \p item is the item found, \p val is the find function argument. - - You may pass \p f argument by reference using \p std::ref. - - The functor may change non-key fields of \p item. - While the functor \p f is calling the item found \p item is locked. - - The function returns \p true if \p val is found, \p false otherwise. - */ + //@cond template - bool find( Q const& val, Func f ) + bool find( Q const& key, Func f ) { - return find_at( &m_Head, val, key_comparator(), f ); + return find_at( &m_Head, key, key_comparator(), f ); } + //@endcond - /// Finds the key \p val using \p pred predicate for searching + /// Finds the key \p key using \p less predicate for searching. Disabled for unordered lists. /** - The function is an analog of \ref cds_intrusive_LazyList_nogc_find_cfunc "find(Q const&, Func)" + The function is an analog of \ref cds_intrusive_LazyList_nogc_find_func "find(Q&, Func)" but \p pred is used for key comparing. \p Less functor has the interface like \p std::less. \p pred must imply the same element order as the comparator used for building the list. */ - template - bool find_with( Q const& val, Less pred, Func f ) + template + typename std::enable_if::type find_with( Q& key, Less less, Func f ) { - return find_at( &m_Head, val, cds::opt::details::make_comparator_from_less(), f ); + CDS_UNUSED( less ); + return find_at( &m_Head, key, cds::opt::details::make_comparator_from_less(), f ); } - /// Finds the key \p val using \p pred predicate for searching + /// Finds the key \p key using \p equal predicate for searching. Disabled for ordered lists. /** The function is an analog of \ref cds_intrusive_LazyList_nogc_find_func "find(Q&, Func)" - but \p pred is used for key comparing. - \p Less functor has the interface like \p std::less. - \p pred must imply the same element order as the comparator used for building the list. + but \p equal is used for key comparing. + \p Equal functor has the interface like \p std::equal_to. */ - template - bool find_with( Q& val, Less pred, Func f ) + template + typename std::enable_if::type find_with( Q& key, Equal eq, Func f ) + { + //CDS_UNUSED( eq ); + return find_at( &m_Head, key, eq, f ); + } + //@cond + template + typename std::enable_if::type find_with( Q const& key, Less pred, Func f ) { - return find_at( &m_Head, val, cds::opt::details::make_comparator_from_less(), f ); + CDS_UNUSED( pred ); + return find_at( &m_Head, key, cds::opt::details::make_comparator_from_less(), f ); } - /// Finds the key \p val - /** \anchor cds_intrusive_LazyList_nogc_find_val - The function searches the item with key equal to \p val - and returns pointer to value found or \p nullptr. + template + typename std::enable_if::type find_with( Q const& key, Equal eq, Func f ) + { + //CDS_UNUSED( eq ); + return find_at( &m_Head, key, eq, f ); + } + //@endcond + + /// Checks whether the list contains \p key + /** + The function searches the item with key equal to \p key + and returns \p true if it is found, and \p false otherwise. */ template - value_type * find( Q const& val ) + value_type * contains( Q const& key ) + { + return find_at( &m_Head, key, key_comparator()); + } + //@cond + template + CDS_DEPRECATED("deprecated, use contains()") + value_type * find( Q const& key ) { - return find_at( &m_Head, val, key_comparator() ); + return contains( key ); } + //@endcond - /// Finds the key \p val using \p pred predicate for searching + /// Checks whether the map contains \p key using \p pred predicate for searching (ordered list version) /** - The function is an analog of \ref cds_intrusive_LazyList_nogc_find_val "find(Q const&)" - but \p pred is used for key comparing. + The function is an analog of contains( key ) but \p pred is used for key comparing. \p Less functor has the interface like \p std::less. - \p pred must imply the same element order as the comparator used for building the list. + \p Less must imply the same element order as the comparator used for building the list. */ - template - value_type * find_with( Q const & val, Less pred ) + template + typename std::enable_if::type contains( Q const& key, Less pred ) + { + CDS_UNUSED( pred ); + return find_at( &m_Head, key, cds::opt::details::make_comparator_from_less()); + } + //@cond + template + CDS_DEPRECATED("deprecated, use contains()") + typename std::enable_if::type find_with( Q const& key, Less pred ) { - return find_at( &m_Head, val, cds::opt::details::make_comparator_from_less() ); + return contains( key, pred ); } + //@endcond + + /// Checks whether the map contains \p key using \p equal predicate for searching (unordered list version) + /** + The function is an analog of contains( key ) but \p equal is used for key comparing. + \p Equal functor has the interface like \p std::equal_to. + */ + template + typename std::enable_if::type contains( Q const& key, Equal eq ) + { + return find_at( &m_Head, key, eq ); + } + //@cond + template + CDS_DEPRECATED("deprecated, use contains()") + typename std::enable_if::type find_with( Q const& key, Equal eq ) + { + return contains( key, eq ); + } + //@endcond /// Clears the list /** @@ -482,6 +575,7 @@ namespace cds { namespace intrusive { while ( pHead != &m_Tail ) { node_type * p = pHead->m_pNext.load(memory_model::memory_order_relaxed); dispose_node( pHead, disp ); + --m_ItemCounter; pHead = p; } } @@ -492,7 +586,7 @@ namespace cds { namespace intrusive { */ void clear() { - clear( disposer() ); + clear( disposer()); } /// Checks if the list is empty @@ -514,6 +608,12 @@ namespace cds { namespace intrusive { return m_ItemCounter.value(); } + /// Returns const reference to internal statistics + stat const& statistics() const + { + return m_Stat; + } + protected: //@cond // split-list support @@ -531,32 +631,37 @@ namespace cds { namespace intrusive { // Hack: convert node_type to value_type. // In principle, auxiliary node can be non-reducible to value_type // We assume that comparator can correctly distinguish aux and regular node. - return insert_at( pHead, *node_traits::to_value_ptr( pNode ) ); + return insert_at( pHead, *node_traits::to_value_ptr( pNode )); } bool insert_at( node_type * pHead, value_type& val ) { - link_checker::is_empty( node_traits::to_node_ptr( val ) ); position pos; - key_comparator cmp; + key_comparator pred; while ( true ) { - search( pHead, val, pos, key_comparator() ); + search( pHead, val, pos, pred ); { auto_lock_position alp( pos ); if ( validate( pos.pPred, pos.pCur )) { - if ( pos.pCur != &m_Tail && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) { + if ( pos.pCur != &m_Tail && equal( *node_traits::to_value_ptr( *pos.pCur ), val, pred )) { // failed: key already in list + m_Stat.onInsertFailed(); return false; } else { link_node( node_traits::to_node_ptr( val ), pos.pPred, pos.pCur ); - ++m_ItemCounter; - return true; + break; } } } + + m_Stat.onInsertRetry(); } + + ++m_ItemCounter; + m_Stat.onInsertSuccess(); + return true; } iterator insert_at_( node_type * pHead, value_type& val ) @@ -568,82 +673,95 @@ namespace cds { namespace intrusive { template - std::pair ensure_at_( node_type * pHead, value_type& val, Func func ) + std::pair update_at_( node_type * pHead, value_type& val, Func func, bool bAllowInsert ) { position pos; - key_comparator cmp; + key_comparator pred; while ( true ) { - search( pHead, val, pos, key_comparator() ); + search( pHead, val, pos, pred ); { auto_lock_position alp( pos ); if ( validate( pos.pPred, pos.pCur )) { - if ( pos.pCur != &m_Tail && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) { + if ( pos.pCur != &m_Tail && equal( *node_traits::to_value_ptr( *pos.pCur ), val, pred )) { // key already in the list func( false, *node_traits::to_value_ptr( *pos.pCur ) , val ); + m_Stat.onUpdateExisting(); return std::make_pair( iterator( pos.pCur ), false ); } else { // new key - link_checker::is_empty( node_traits::to_node_ptr( val ) ); + if ( !bAllowInsert ) { + m_Stat.onUpdateFailed(); + return std::make_pair( end(), false ); + } link_node( node_traits::to_node_ptr( val ), pos.pPred, pos.pCur ); func( true, val, val ); - ++m_ItemCounter; - return std::make_pair( iterator( node_traits::to_node_ptr( val )), true ); + break; } } + + m_Stat.onUpdateRetry(); } } + + ++m_ItemCounter; + m_Stat.onUpdateNew(); + return std::make_pair( iterator( node_traits::to_node_ptr( val )), true ); } template - std::pair ensure_at( node_type * pHead, value_type& val, Func func ) + std::pair update_at( node_type * pHead, value_type& val, Func func, bool bAllowInsert ) { - std::pair ret = ensure_at_( pHead, val, func ); + std::pair ret = update_at_( pHead, val, func, bAllowInsert ); return std::make_pair( ret.first != end(), ret.second ); } - template - bool find_at( node_type * pHead, Q& val, Compare cmp, Func f ) + template + bool find_at( node_type * pHead, Q& val, Pred pred, Func f ) { position pos; - search( pHead, val, pos, cmp ); + search( pHead, val, pos, pred ); if ( pos.pCur != &m_Tail ) { - cds::lock::scoped_lock< typename node_type::lock_type> al( pos.pCur->m_Lock ); - if ( cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) + std::unique_lock< typename node_type::lock_type> al( pos.pCur->m_Lock ); + if ( equal( *node_traits::to_value_ptr( *pos.pCur ), val, pred )) { f( *node_traits::to_value_ptr( *pos.pCur ), val ); + m_Stat.onFindSuccess(); return true; } } + + m_Stat.onFindFailed(); return false; } - template - value_type * find_at( node_type * pHead, Q& val, Compare cmp) + template + value_type * find_at( node_type * pHead, Q& val, Pred pred) { - iterator it = find_at_( pHead, val, cmp ); - if ( it != end() ) + iterator it = find_at_( pHead, val, pred ); + if ( it != end()) return &*it; return nullptr; } - template - iterator find_at_( node_type * pHead, Q& val, Compare cmp) + template + iterator find_at_( node_type * pHead, Q& val, Pred pred) { position pos; - search( pHead, val, pos, cmp ); + search( pHead, val, pos, pred ); if ( pos.pCur != &m_Tail ) { - cds::lock::scoped_lock< typename node_type::lock_type> al( pos.pCur->m_Lock ); - if ( cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) - { + if ( equal( *node_traits::to_value_ptr( *pos.pCur ), val, pred )) { + m_Stat.onFindSuccess(); return iterator( pos.pCur ); } } + + m_Stat.onFindFailed(); return end(); } @@ -651,8 +769,25 @@ namespace cds { namespace intrusive { protected: //@cond - template - void search( node_type * pHead, const Q& key, position& pos, Compare cmp ) + template + typename std::enable_if::type search( node_type * pHead, const Q& key, position& pos, Equal eq ) + { + const node_type * pTail = &m_Tail; + + node_type * pCur = pHead; + node_type * pPrev = pHead; + + while ( pCur != pTail && ( pCur == pHead || !equal( *node_traits::to_value_ptr( *pCur ), key, eq ))) { + pPrev = pCur; + pCur = pCur->m_pNext.load(memory_model::memory_order_acquire); + } + + pos.pCur = pCur; + pos.pPred = pPrev; + } + + template + typename std::enable_if::type search( node_type * pHead, const Q& key, position& pos, Compare cmp ) { const node_type * pTail = &m_Tail; @@ -668,14 +803,51 @@ namespace cds { namespace intrusive { pos.pPred = pPrev; } - static bool validate( node_type * pPred, node_type * pCur ) + template + static typename std::enable_if::type equal( L const& l, R const& r, Equal eq ) { - return pPred->m_pNext.load(memory_model::memory_order_acquire) == pCur; + return eq(l, r); } + template + static typename std::enable_if::type equal( L const& l, R const& r, Compare cmp ) + { + return cmp(l, r) == 0; + } + + bool validate( node_type * pPred, node_type * pCur ) + { + if ( pPred->m_pNext.load(memory_model::memory_order_acquire) == pCur ) { + m_Stat.onValidationSuccess(); + return true; + } + + m_Stat.onValidationFailed(); + return false; + } + + // for split-list + template + void erase_for( Predicate pred ) + { + node_type * pPred = nullptr; + node_type * pHead = m_Head.m_pNext.load( memory_model::memory_order_relaxed ); + + while ( pHead != &m_Tail ) { + node_type * p = pHead->m_pNext.load( memory_model::memory_order_relaxed ); + if ( pred( *node_traits::to_value_ptr( pHead ))) { + assert( pPred != nullptr ); + pPred->m_pNext.store( p, memory_model::memory_order_relaxed ); + dispose_node( pHead, disposer()); + } + else + pPred = pHead; + pHead = p; + } + } //@endcond }; }} // namespace cds::intrusive -#endif // #ifndef __CDS_INTRUSIVE_LAZY_LIST_NOGC_H +#endif // #ifndef CDSLIB_INTRUSIVE_LAZY_LIST_NOGC_H