X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=cds%2Fintrusive%2Flazy_list_nogc.h;h=01fc656e4528ce6a6827a844e32a8d1f95fa086d;hb=056d289619d45ccf1055c18d63cb3bad072a71a0;hp=29412d552c96de03d153a6dd3d518113240f11d6;hpb=102daee36a830ed004c98fe863184ac7ce504069;p=libcds.git diff --git a/cds/intrusive/lazy_list_nogc.h b/cds/intrusive/lazy_list_nogc.h index 29412d55..01fc656e 100644 --- a/cds/intrusive/lazy_list_nogc.h +++ b/cds/intrusive/lazy_list_nogc.h @@ -1,4 +1,32 @@ -//$$CDS-header$$ +/* + This file is a part of libcds - Concurrent Data Structures library + + (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 @@ -40,13 +68,18 @@ namespace cds { namespace intrusive { } // namespace lazy_list - /// Lazy ordered single-linked list (template specialization for \p gc::nogc) + /// Lazy single-linked list (template specialization for \p gc::nogc) /** @ingroup cds_intrusive_list \anchor cds_intrusive_LazyList_nogc This specialization is append-only list when no item reclamation may be performed. The class does not support deleting of list item. + 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 < @@ -66,21 +99,33 @@ namespace cds { namespace intrusive { 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, traits >::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 traits::item_counter item_counter; ///< Item counting policy used - typedef typename traits::memory_model memory_model; ///< C++ memory ordering (see lazy_list::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 + 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_traits { @@ -90,6 +135,10 @@ namespace cds { namespace intrusive { , typename cds::opt::make_options< traits, Options...>::type > type; }; + + // Stat selector + template + using select_stat_wrapper = lazy_list::select_stat_wrapper< Stat >; //@endcond protected: @@ -99,6 +148,7 @@ namespace cds { namespace intrusive { 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 @@ -159,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 ); @@ -285,7 +336,7 @@ namespace cds { namespace intrusive { /// Returns a forward const iterator addressing the first element in a list const_iterator cbegin() const { - const_iterator it( const_cast(&m_Head) ); + const_iterator it( const_cast(&m_Head)); ++it; // skip dummy head return it; } @@ -298,17 +349,25 @@ namespace cds { namespace intrusive { /// 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) ); + 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() { @@ -329,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 @@ -344,23 +404,30 @@ 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. - 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 key /** \anchor cds_intrusive_LazyList_nogc_find_func @@ -392,52 +459,106 @@ namespace cds { namespace intrusive { } //@endcond - /// Finds the key \p key 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_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& key, Less pred, Func f ) + template + typename std::enable_if::type find_with( Q& key, Less less, Func f ) { - CDS_UNUSED( pred ); + CDS_UNUSED( less ); return find_at( &m_Head, key, cds::opt::details::make_comparator_from_less(), f ); } + + /// 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 equal is used for key comparing. + \p Equal functor has the interface like \p std::equal_to. + */ + template + typename std::enable_if::type find_with( Q& key, Equal equal, Func f ) + { + CDS_UNUSED( equal ); + return find_at( &m_Head, key, equal, f ); + } //@cond - template - bool find_with( Q const& key, Less pred, Func f ) + template + typename std::enable_if::type find_with( Q const& key, Less pred, Func f ) { CDS_UNUSED( pred ); return find_at( &m_Head, key, cds::opt::details::make_comparator_from_less(), f ); } + + template + typename std::enable_if::type find_with( Q const& key, Equal equal, Func f ) + { + CDS_UNUSED( equal ); + return find_at( &m_Head, key, equal, f ); + } //@endcond - /// Finds the key \p key - /** \anchor cds_intrusive_LazyList_nogc_find_val + /// Checks whether the list contains \p key + /** The function searches the item with key equal to \p key - and returns pointer to value found or \p nullptr. + and returns \p true if it is found, and \p false otherwise. */ template + 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, key, key_comparator() ); + return contains( key ); } + //@endcond - /// Finds the key \p key 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& key, 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() ); + 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 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 equal ) + { + return find_at( &m_Head, key, equal ); + } + //@cond + template + CDS_DEPRECATED("deprecated, use contains()") + typename std::enable_if::type find_with( Q const& key, Equal equal ) + { + return contains( key, equal ); + } + //@endcond /// Clears the list /** @@ -454,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; } } @@ -464,7 +586,7 @@ namespace cds { namespace intrusive { */ void clear() { - clear( disposer() ); + clear( disposer()); } /// Checks if the list is empty @@ -486,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 @@ -503,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 ) @@ -540,81 +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 ) { std::unique_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 )) { 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 ) { - 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(); } @@ -622,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; @@ -639,11 +803,48 @@ 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 eq(l, r); + } + + template + static typename std::enable_if::type equal( L const& l, R const& r, Compare cmp ) { - return pPred->m_pNext.load(memory_model::memory_order_acquire) == pCur; + 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 };