X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=cds%2Fintrusive%2Flazy_list_nogc.h;h=01fc656e4528ce6a6827a844e32a8d1f95fa086d;hb=056d289619d45ccf1055c18d63cb3bad072a71a0;hp=255cab87190eec8932e9354b5f72e5f0babf39b3;hpb=7edbe8f8507709bbc68f468612abc6dcae71b505;p=libcds.git diff --git a/cds/intrusive/lazy_list_nogc.h b/cds/intrusive/lazy_list_nogc.h index 255cab87..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,25 +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. - typedef implementation_defined equal_to_comparator; - typedef implementation_defined predicate_type; + /// 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 opt::details::make_equal_to< value_type, traits >::type equal_to_comparator; - typedef typename std::conditional< traits::sort, key_comparator, equal_to_comparator >::type predicate_type; + 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 { @@ -94,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: @@ -103,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 @@ -163,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 ); @@ -289,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; } @@ -302,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() { @@ -333,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 @@ -348,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 @@ -386,62 +449,116 @@ namespace cds { namespace intrusive { template bool find( Q& key, Func f ) { - return find_at( &m_Head, key, predicate_type(), f ); + return find_at( &m_Head, key, key_comparator(), f ); } //@cond template bool find( Q const& key, Func f ) { - return find_at( &m_Head, key, predicate_type(), f ); + return find_at( &m_Head, key, key_comparator(), f ); } //@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 - typename std::enable_if::type 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 + 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, predicate_type() ); + return contains( key ); } + //@endcond - /// Finds the key \p key using \p pred predicate for searching. Disabled for unordered lists. + /// 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 - typename std::enable_if::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 /** @@ -458,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; } } @@ -468,7 +586,7 @@ namespace cds { namespace intrusive { */ void clear() { - clear( disposer() ); + clear( disposer()); } /// Checks if the list is empty @@ -490,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 @@ -507,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; - predicate_type pred; + key_comparator pred; while ( true ) { search( pHead, val, pos, pred ); { auto_lock_position alp( pos ); if ( validate( pos.pPred, pos.pCur )) { - if ( pos.pCur != &m_Tail && equal( *node_traits::to_value_ptr( *pos.pCur ), val, pred ) ) { + 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 ) @@ -544,40 +673,49 @@ 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; - predicate_type pred; + key_comparator pred; while ( true ) { search( pHead, val, pos, pred ); { auto_lock_position alp( pos ); if ( validate( pos.pPred, pos.pCur )) { - if ( pos.pCur != &m_Tail && equal( *node_traits::to_value_ptr( *pos.pCur ), val, pred ) ) { + 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 ); } @@ -589,12 +727,15 @@ namespace cds { namespace intrusive { search( pHead, val, pos, pred ); if ( pos.pCur != &m_Tail ) { std::unique_lock< typename node_type::lock_type> al( pos.pCur->m_Lock ); - if ( equal( *node_traits::to_value_ptr( *pos.pCur ), val, pred ) ) + 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; } @@ -602,7 +743,7 @@ namespace cds { namespace intrusive { value_type * find_at( node_type * pHead, Q& val, Pred pred) { iterator it = find_at_( pHead, val, pred ); - if ( it != end() ) + if ( it != end()) return &*it; return nullptr; } @@ -614,9 +755,13 @@ namespace cds { namespace intrusive { search( pHead, val, pos, pred ); if ( pos.pCur != &m_Tail ) { - if ( equal( *node_traits::to_value_ptr( *pos.pCur ), val, pred ) ) + if ( equal( *node_traits::to_value_ptr( *pos.pCur ), val, pred )) { + m_Stat.onFindSuccess(); return iterator( pos.pCur ); + } } + + m_Stat.onFindFailed(); return end(); } @@ -624,7 +769,7 @@ namespace cds { namespace intrusive { protected: //@cond - template + template typename std::enable_if::type search( node_type * pHead, const Q& key, position& pos, Equal eq ) { const node_type * pTail = &m_Tail; @@ -632,7 +777,7 @@ namespace cds { namespace intrusive { node_type * pCur = pHead; node_type * pPrev = pHead; - while ( pCur != pTail && ( pCur == pHead || !equal( *node_traits::to_value_ptr( *pCur ), key, eq ) )) { + 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); } @@ -641,7 +786,7 @@ namespace cds { namespace intrusive { pos.pPred = pPrev; } - template + template typename std::enable_if::type search( node_type * pHead, const Q& key, position& pos, Compare cmp ) { const node_type * pTail = &m_Tail; @@ -658,23 +803,48 @@ namespace cds { namespace intrusive { pos.pPred = pPrev; } - template + template static typename std::enable_if::type equal( L const& l, R const& r, Equal eq ) { return eq(l, r); } - template + template static typename std::enable_if::type equal( L const& l, R const& r, Compare cmp ) { return cmp(l, r) == 0; } - static bool validate( node_type * pPred, node_type * pCur ) + bool validate( node_type * pPred, node_type * pCur ) { - return pPred->m_pNext.load(memory_model::memory_order_acquire) == 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 };