From 7edbe8f8507709bbc68f468612abc6dcae71b505 Mon Sep 17 00:00:00 2001 From: Mike Krinkin Date: Sat, 28 Mar 2015 12:53:52 +0300 Subject: [PATCH] Implement unordered intrusive lazy list. Add implementation of unordered policy for intrusive lazy list. Implementation uses tratis::sort bool flag and std::enable_if to choose appropriate ordered/unordered implementation of search and equal functions. Also this fix disables find_with function for unordered list for simplicity. find_with is a part of public interface, so providing alternative implementation with same name and different semantic is arguable. --- cds/intrusive/lazy_list_nogc.h | 93 +++++++++++++++++++++++----------- 1 file changed, 63 insertions(+), 30 deletions(-) diff --git a/cds/intrusive/lazy_list_nogc.h b/cds/intrusive/lazy_list_nogc.h index ae950445..255cab87 100644 --- a/cds/intrusive/lazy_list_nogc.h +++ b/cds/intrusive/lazy_list_nogc.h @@ -69,8 +69,12 @@ namespace cds { namespace intrusive { # 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; # 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; # endif typedef typename traits::back_off back_off; ///< Back-off strategy typedef typename traits::disposer disposer; ///< disposer @@ -382,32 +386,32 @@ namespace cds { namespace intrusive { template bool find( Q& key, Func f ) { - return find_at( &m_Head, key, key_comparator(), f ); + return find_at( &m_Head, key, predicate_type(), f ); } //@cond template bool find( Q const& key, Func f ) { - return find_at( &m_Head, key, key_comparator(), f ); + return find_at( &m_Head, key, predicate_type(), f ); } //@endcond - /// Finds the key \p key using \p pred predicate for searching + /// Finds the key \p key using \p pred predicate for searching. /** 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 pred, Func f ) { CDS_UNUSED( pred ); return find_at( &m_Head, key, cds::opt::details::make_comparator_from_less(), 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 ); @@ -422,18 +426,18 @@ namespace cds { namespace intrusive { template value_type * find( Q const& key ) { - return find_at( &m_Head, key, key_comparator() ); + return find_at( &m_Head, key, predicate_type() ); } - /// Finds the key \p key using \p pred predicate for searching + /// Finds the key \p key using \p pred predicate for searching. Disabled for unordered lists. /** The function is an analog of \ref cds_intrusive_LazyList_nogc_find_val "find(Q const&)" 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 - value_type * find_with( Q const& key, Less pred ) + template + typename std::enable_if::type find_with( Q const& key, Less pred ) { CDS_UNUSED( pred ); return find_at( &m_Head, key, cds::opt::details::make_comparator_from_less() ); @@ -510,14 +514,14 @@ namespace cds { namespace intrusive { { link_checker::is_empty( node_traits::to_node_ptr( val ) ); position pos; - key_comparator cmp; + predicate_type 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 return false; } @@ -543,14 +547,14 @@ namespace cds { namespace intrusive { std::pair ensure_at_( node_type * pHead, value_type& val, Func func ) { position pos; - key_comparator cmp; + predicate_type 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 ); @@ -577,15 +581,15 @@ namespace cds { namespace intrusive { 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 ); return true; @@ -594,23 +598,23 @@ namespace cds { namespace intrusive { 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 ); + 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 ) ) return iterator( pos.pCur ); } return end(); @@ -620,8 +624,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; @@ -637,6 +658,18 @@ namespace cds { namespace intrusive { pos.pPred = pPrev; } + 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 cmp(l, r) == 0; + } + static bool validate( node_type * pPred, node_type * pCur ) { return pPred->m_pNext.load(memory_model::memory_order_acquire) == pCur; -- 2.34.1