From ad62bc50a518a61b533a154bb1df71b794e91c4c Mon Sep 17 00:00:00 2001 From: khizmax Date: Tue, 12 Jan 2016 13:37:26 +0300 Subject: [PATCH] Issue #48: added std::move for pop() function of stack/queue/pqueue Fixed stack overflow case in pqueue unit tests --- cds/container/basket_queue.h | 4 +- cds/container/fcdeque.h | 107 +++++++++++++++--- cds/container/fcpriority_queue.h | 2 +- cds/container/fcqueue.h | 2 +- cds/container/fcstack.h | 2 +- cds/container/moir_queue.h | 2 +- cds/container/mspriority_queue.h | 2 +- cds/container/msqueue.h | 2 +- cds/container/optimistic_queue.h | 2 +- cds/container/rwqueue.h | 2 +- cds/container/segmented_queue.h | 2 +- cds/container/treiber_stack.h | 12 +- cds/container/tsigas_cycle_queue.h | 2 +- cds/container/vyukov_mpmc_cycle_queue.h | 4 +- cds/opt/options.h | 8 +- .../priority_queue/hdr_intrusive_pqueue.h | 4 +- tests/test-hdr/priority_queue/hdr_pqueue.h | 4 +- 17 files changed, 116 insertions(+), 47 deletions(-) diff --git a/cds/container/basket_queue.h b/cds/container/basket_queue.h index 53ef4bcf..1e443c12 100644 --- a/cds/container/basket_queue.h +++ b/cds/container/basket_queue.h @@ -373,12 +373,12 @@ namespace cds { namespace container { /// Dequeues a value from the queue /** If queue is not empty, the function returns \p true, \p dest contains copy of - dequeued value. The assignment operator for type \ref value_type is invoked. + dequeued value. The assignment operator for \p value_type is invoked. If queue is empty, the function returns \p false, \p dest is unchanged. */ bool dequeue( value_type& dest ) { - return dequeue_with( [&dest]( value_type& src ) { dest = src; } ); + return dequeue_with( [&dest]( value_type& src ) { dest = std::move( src );}); } /// Dequeues a value using a functor diff --git a/cds/container/fcdeque.h b/cds/container/fcdeque.h index d14328b6..7dccc157 100644 --- a/cds/container/fcdeque.h +++ b/cds/container/fcdeque.h @@ -417,7 +417,7 @@ namespace cds { namespace container { assert( pRec->pValPop ); pRec->bEmpty = m_Deque.empty(); if ( !pRec->bEmpty ) { - *(pRec->pValPop) = m_Deque.front(); + *(pRec->pValPop) = std::move( m_Deque.front()); m_Deque.pop_front(); } break; @@ -425,7 +425,7 @@ namespace cds { namespace container { assert( pRec->pValPop ); pRec->bEmpty = m_Deque.empty(); if ( !pRec->bEmpty ) { - *(pRec->pValPop) = m_Deque.back(); + *(pRec->pValPop) = std::move( m_Deque.back()); m_Deque.pop_back(); } break; @@ -454,20 +454,28 @@ namespace cds { namespace container { for ( fc_iterator it = itBegin, itPrev = itEnd; it != itEnd; ++it ) { switch ( it->op() ) { case op_push_front: + if ( itPrev != itEnd + && (itPrev->op() == op_pop_front || (m_Deque.empty() && itPrev->op() == op_pop_back)) ) + { + collide( *it, *itPrev ); + itPrev = itEnd; + } + else + itPrev = it; + break; case op_push_front_move: if ( itPrev != itEnd && (itPrev->op() == op_pop_front || ( m_Deque.empty() && itPrev->op() == op_pop_back ))) { - collide( *it, *itPrev ); + collide_move( *it, *itPrev ); itPrev = itEnd; } else itPrev = it; break; case op_push_back: - case op_push_back_move: if ( itPrev != itEnd - && (itPrev->op() == op_pop_back || ( m_Deque.empty() && itPrev->op() == op_pop_front ))) + && (itPrev->op() == op_pop_back || (m_Deque.empty() && itPrev->op() == op_pop_front)) ) { collide( *it, *itPrev ); itPrev = itEnd; @@ -475,24 +483,84 @@ namespace cds { namespace container { else itPrev = it; break; - case op_pop_front: + case op_push_back_move: if ( itPrev != itEnd - && ( itPrev->op() == op_push_front || itPrev->op() == op_push_front_move - || ( m_Deque.empty() && ( itPrev->op() == op_push_back || itPrev->op() == op_push_back_move )))) + && (itPrev->op() == op_pop_back || ( m_Deque.empty() && itPrev->op() == op_pop_front ))) { - collide( *itPrev, *it ); + collide_move( *it, *itPrev ); itPrev = itEnd; } else itPrev = it; break; + case op_pop_front: + if ( itPrev != itEnd ) { + if ( m_Deque.empty() ) { + switch ( itPrev->op() ) { + case op_push_back: + collide( *itPrev, *it ); + itPrev = itEnd; + break; + case op_push_back_move: + collide_move( *itPrev, *it ); + itPrev = itEnd; + break; + default: + itPrev = it; + break; + } + } + else { + switch ( itPrev->op() ) { + case op_push_front: + collide( *itPrev, *it ); + itPrev = itEnd; + break; + case op_push_front_move: + collide_move( *itPrev, *it ); + itPrev = itEnd; + break; + default: + itPrev = it; + break; + } + } + } + else + itPrev = it; + break; case op_pop_back: - if ( itPrev != itEnd - && ( itPrev->op() == op_push_back || itPrev->op() == op_push_back_move - || ( m_Deque.empty() && ( itPrev->op() == op_push_front || itPrev->op() == op_push_front_move )))) - { - collide( *itPrev, *it ); - itPrev = itEnd; + if ( itPrev != itEnd ) { + if ( m_Deque.empty() ) { + switch ( itPrev->op() ) { + case op_push_front: + collide( *itPrev, *it ); + itPrev = itEnd; + break; + case op_push_front_move: + collide_move( *itPrev, *it ); + itPrev = itEnd; + break; + default: + itPrev = it; + break; + } + } + else { + switch ( itPrev->op() ) { + case op_push_back: + collide( *itPrev, *it ); + itPrev = itEnd; + break; + case op_push_back_move: + collide_move( *itPrev, *it ); + itPrev = itEnd; + break; + default: + itPrev = it; + break; + } + } } else itPrev = it; @@ -513,6 +581,15 @@ namespace cds { namespace container { m_FlatCombining.operation_done( recPop ); m_FlatCombining.internal_statistics().onCollide(); } + + void collide_move( fc_record& recPush, fc_record& recPop ) + { + *(recPop.pValPop) = std::move( *(recPush.pValPush)); + recPop.bEmpty = false; + m_FlatCombining.operation_done( recPush ); + m_FlatCombining.operation_done( recPop ); + m_FlatCombining.internal_statistics().onCollide(); + } //@endcond }; diff --git a/cds/container/fcpriority_queue.h b/cds/container/fcpriority_queue.h index b8c38cda..779849b5 100644 --- a/cds/container/fcpriority_queue.h +++ b/cds/container/fcpriority_queue.h @@ -303,7 +303,7 @@ namespace cds { namespace container { assert( pRec->pValPop ); pRec->bEmpty = m_PQueue.empty(); if ( !pRec->bEmpty ) { - *(pRec->pValPop) = m_PQueue.top(); + *(pRec->pValPop) = std::move( m_PQueue.top()); m_PQueue.pop(); } break; diff --git a/cds/container/fcqueue.h b/cds/container/fcqueue.h index 8c58a45d..dff95ede 100644 --- a/cds/container/fcqueue.h +++ b/cds/container/fcqueue.h @@ -343,7 +343,7 @@ namespace cds { namespace container { assert( pRec->pValDeq ); pRec->bEmpty = m_Queue.empty(); if ( !pRec->bEmpty ) { - *(pRec->pValDeq) = m_Queue.front(); + *(pRec->pValDeq) = std::move( m_Queue.front()); m_Queue.pop(); } break; diff --git a/cds/container/fcstack.h b/cds/container/fcstack.h index 5fb24281..eb7c8de5 100644 --- a/cds/container/fcstack.h +++ b/cds/container/fcstack.h @@ -321,7 +321,7 @@ namespace cds { namespace container { assert( pRec->pValPop ); pRec->bEmpty = m_Stack.empty(); if ( !pRec->bEmpty ) { - *(pRec->pValPop) = m_Stack.top(); + *(pRec->pValPop) = std::move( m_Stack.top()); m_Stack.pop(); } break; diff --git a/cds/container/moir_queue.h b/cds/container/moir_queue.h index 7e903727..40acf9c6 100644 --- a/cds/container/moir_queue.h +++ b/cds/container/moir_queue.h @@ -221,7 +221,7 @@ namespace cds { namespace container { */ bool dequeue( value_type& dest ) { - return dequeue_with( [&dest]( value_type& src ) { dest = src; } ); + return dequeue_with( [&dest]( value_type& src ) { dest = std::move( src ); }); } /// Dequeues a value using a functor diff --git a/cds/container/mspriority_queue.h b/cds/container/mspriority_queue.h index b1321b5f..4b916f04 100644 --- a/cds/container/mspriority_queue.h +++ b/cds/container/mspriority_queue.h @@ -251,7 +251,7 @@ namespace cds { namespace container { */ bool pop( value_type& dest ) { - return pop_with( [&dest]( value_type& src ) { move_policy()(dest, src); } ); + return pop_with( [&dest]( value_type& src ) { move_policy()(dest, std::move(src)); }); } /// Extracts an item with high priority diff --git a/cds/container/msqueue.h b/cds/container/msqueue.h index f3d558f1..a26dff20 100644 --- a/cds/container/msqueue.h +++ b/cds/container/msqueue.h @@ -336,7 +336,7 @@ namespace cds { namespace container { */ bool dequeue( value_type& dest ) { - return dequeue_with( [&dest]( value_type& src ) { dest = src; } ); + return dequeue_with( [&dest]( value_type& src ) { dest = std::move( src );}); } /// Dequeues a value using a functor diff --git a/cds/container/optimistic_queue.h b/cds/container/optimistic_queue.h index b118dce2..0bb01cb4 100644 --- a/cds/container/optimistic_queue.h +++ b/cds/container/optimistic_queue.h @@ -339,7 +339,7 @@ namespace cds { namespace container { */ bool dequeue( value_type& dest ) { - return dequeue_with( [&dest]( value_type& src ) { dest = src; } ); + return dequeue_with( [&dest]( value_type& src ) { dest = std::move( src ); }); } /// Dequeues a value using a functor diff --git a/cds/container/rwqueue.h b/cds/container/rwqueue.h index ae52b9f0..de0c8e0c 100644 --- a/cds/container/rwqueue.h +++ b/cds/container/rwqueue.h @@ -306,7 +306,7 @@ namespace cds { namespace container { */ bool dequeue( value_type& dest ) { - return dequeue_with( [&dest]( value_type& src ) { dest = src; } ); + return dequeue_with( [&dest]( value_type& src ) { dest = std::move( src ); }); } /// Dequeues a value using a functor diff --git a/cds/container/segmented_queue.h b/cds/container/segmented_queue.h index d29d567a..fa981e26 100644 --- a/cds/container/segmented_queue.h +++ b/cds/container/segmented_queue.h @@ -337,7 +337,7 @@ namespace cds { namespace container { */ bool dequeue( value_type& dest ) { - return dequeue_with( [&dest]( value_type& src ) { dest = src; }); + return dequeue_with( [&dest]( value_type& src ) { dest = std::move( src );}); } /// Dequeues a value using a functor diff --git a/cds/container/treiber_stack.h b/cds/container/treiber_stack.h index ae9cb1f5..6c7f0702 100644 --- a/cds/container/treiber_stack.h +++ b/cds/container/treiber_stack.h @@ -347,25 +347,17 @@ namespace cds { namespace container { */ bool pop( value_type& val ) { - return pop_with( [&val]( value_type& src ) { val = src; } ); + return pop_with( [&val]( value_type& src ) { val = std::move(src); } ); } /// Pops an item from the stack with functor /** + \p Func can be used to copy/move popped item from the stack. \p Func interface is: \code void func( value_type& src ); \endcond where \p src - item popped. - - The \p %pop_with can be used to move item from the stack to user-provided storage: - \code - cds::container::TreiberStack myStack; - //... - - std::string dest; - myStack.pop_with( [&dest]( std::string& src ) { dest = std::move( src ); } ); - \endcode */ template bool pop_with( Func f ) diff --git a/cds/container/tsigas_cycle_queue.h b/cds/container/tsigas_cycle_queue.h index c4661898..f87da37c 100644 --- a/cds/container/tsigas_cycle_queue.h +++ b/cds/container/tsigas_cycle_queue.h @@ -362,7 +362,7 @@ namespace cds { namespace container { */ bool dequeue( value_type& dest ) { - return dequeue_with( [&dest]( value_type& src ) { dest = src; } ); + return dequeue_with( [&dest]( value_type& src ) { dest = std::move( src );}); } /// Synonym for \p dequeue() function diff --git a/cds/container/vyukov_mpmc_cycle_queue.h b/cds/container/vyukov_mpmc_cycle_queue.h index 29a126fa..783a912c 100644 --- a/cds/container/vyukov_mpmc_cycle_queue.h +++ b/cds/container/vyukov_mpmc_cycle_queue.h @@ -380,13 +380,13 @@ namespace cds { namespace container { /// Dequeues a value from the queue /** - If queue is not empty, the function returns \p true, \p dest contains copy of + If queue is not empty, the function returns \p true, \p dest contains a copy of dequeued value. The assignment operator for type \ref value_type is invoked. If queue is empty, the function returns \p false, \p dest is unchanged. */ bool dequeue(value_type & dest ) { - return dequeue_with( [&dest]( value_type& src ){ dest = src; } ); + return dequeue_with( [&dest]( value_type& src ){ dest = std::move( src );}); } /// Synonym for \p dequeue() diff --git a/cds/opt/options.h b/cds/opt/options.h index e78655bb..2b1c3ec6 100644 --- a/cds/opt/options.h +++ b/cds/opt/options.h @@ -851,14 +851,14 @@ namespace cds { namespace opt { } }; - /// \p opt::move_policy based on assignment operator + /// \p opt::move_policy based on move-assignment operator struct assignment_move_policy { - /// dest = src + /// dest = std::move( src ) template - void operator()( T& dest, T const& src ) const + void operator()( T& dest, T&& src ) const { - dest = src; + dest = std::move( src ); } }; diff --git a/tests/test-hdr/priority_queue/hdr_intrusive_pqueue.h b/tests/test-hdr/priority_queue/hdr_intrusive_pqueue.h index 3a917dc1..e038c8f9 100644 --- a/tests/test-hdr/priority_queue/hdr_intrusive_pqueue.h +++ b/tests/test-hdr/priority_queue/hdr_intrusive_pqueue.h @@ -201,8 +201,8 @@ namespace priority_queue { template void test_msq_stat() { - PQueue pq( 0 ); // argument should be ignored for static buffer - test_bounded_with( pq ); + std::unique_ptr< PQueue > pq( new PQueue(0)); // argument should be ignored for static buffer + test_bounded_with( *pq ); } template void test_msq_dyn() diff --git a/tests/test-hdr/priority_queue/hdr_pqueue.h b/tests/test-hdr/priority_queue/hdr_pqueue.h index 12eb4bb7..a9ef86c0 100644 --- a/tests/test-hdr/priority_queue/hdr_pqueue.h +++ b/tests/test-hdr/priority_queue/hdr_pqueue.h @@ -258,8 +258,8 @@ namespace priority_queue { template void test_msq_stat() { - PQueue pq( 0 ); // argument should be ignored for static buffer - test_bounded_with( pq ); + std::unique_ptr< PQueue > pq( new PQueue( 0 )); // argument should be ignored for static buffer + test_bounded_with( *pq ); } template void test_msq_dyn() -- 2.34.1