From d1d4662c752ec69b80a8f856183acdc27e3ebdb7 Mon Sep 17 00:00:00 2001 From: khizmax Date: Tue, 1 Nov 2016 20:30:06 +0300 Subject: [PATCH] Removed TsigasCycleQueue (undecidable ABA problem) --- cds/container/tsigas_cycle_queue.h | 432 ----------------- cds/details/bounded_container.h | 2 +- cds/intrusive/tsigas_cycle_queue.h | 457 ------------------ change.log | 1 + projects/Win/vc14/cds.vcxproj | 2 - projects/Win/vc14/cds.vcxproj.filters | 6 - projects/Win/vc14/gtest-queue.vcxproj | 2 - projects/Win/vc14/gtest-queue.vcxproj.filters | 6 - test/stress/queue/bounded_queue_fulness.cpp | 1 - test/stress/queue/intrusive_push_pop.cpp | 2 - test/stress/queue/intrusive_queue_type.h | 57 --- test/stress/queue/pop.cpp | 1 - test/stress/queue/push.cpp | 1 - test/stress/queue/push_pop.cpp | 1 - test/stress/queue/queue_type.h | 92 ---- test/stress/queue/random.cpp | 1 - test/unit/queue/CMakeLists.txt | 2 - test/unit/queue/intrusive_tsigas_queue.cpp | 112 ----- test/unit/queue/tsigas_queue.cpp | 134 ----- 19 files changed, 2 insertions(+), 1310 deletions(-) delete mode 100644 cds/container/tsigas_cycle_queue.h delete mode 100644 cds/intrusive/tsigas_cycle_queue.h delete mode 100644 test/unit/queue/intrusive_tsigas_queue.cpp delete mode 100644 test/unit/queue/tsigas_queue.cpp diff --git a/cds/container/tsigas_cycle_queue.h b/cds/container/tsigas_cycle_queue.h deleted file mode 100644 index 741b31ba..00000000 --- a/cds/container/tsigas_cycle_queue.h +++ /dev/null @@ -1,432 +0,0 @@ -/* - This file is a part of libcds - Concurrent Data Structures library - - (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016 - - 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_CONTAINER_TSIGAS_CYCLE_QUEUE_H -#define CDSLIB_CONTAINER_TSIGAS_CYCLE_QUEUE_H - -#include -#include -#include - -namespace cds { namespace container { - - /// TsigasCycleQueue related definitions - /** @ingroup cds_nonintrusive_helper - */ - namespace tsigas_queue { - - /// TsigasCycleQueue default traits - struct traits - { - /// Buffer type for cyclic array - /* - The type of element for the buffer is not important: the queue rebinds - buffer for required type via \p rebind metafunction. - - For \p TsigasCycleQueue queue the buffer size should have power-of-2 size. - - You should use any initialized buffer type, see \p opt::buffer. - */ - typedef cds::opt::v::initialized_dynamic_buffer< void * > buffer; - - /// Node allocator - typedef CDS_DEFAULT_ALLOCATOR allocator; - - /// Back-off strategy - typedef cds::backoff::empty back_off; - - /// Item counting feature; by default, disabled. Use \p cds::atomicity::item_counter to enable item counting - typedef atomicity::empty_item_counter item_counter; - - /// C++ memory ordering model - /** - Can be \p opt::v::relaxed_ordering (relaxed memory model, the default) - or \p opt::v::sequential_consistent (sequentially consisnent memory model). - */ - typedef opt::v::relaxed_ordering memory_model; - - /// Padding for internal critical atomic data. Default is \p opt::cache_line_padding - enum { padding = opt::cache_line_padding }; - }; - - /// Metafunction converting option list to \p tsigas_queue::traits - /** - Supported \p Options are: - - \p opt::buffer - the buffer type for internal cyclic array. Possible types are: - \p opt::v::initialized_dynamic_buffer (the default), \p opt::v::initialized_static_buffer. The type of - element in the buffer is not important: it will be changed via \p rebind metafunction. - - \p opt::allocator - allocator (like \p std::allocator) used for allocating queue items. Default is \ref CDS_DEFAULT_ALLOCATOR - - \p opt::back_off - back-off strategy used, default is \p cds::backoff::empty. - - \p opt::item_counter - the type of item counting feature. Default is \p cds::atomicity::empty_item_counter (item counting disabled) - To enable item counting use \p cds::atomicity::item_counter - - \p opt::padding - padding for internal critical atomic data. Default is \p opt::cache_line_padding - - \p opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default) - or \p opt::v::sequential_consistent (sequentially consisnent memory model). - - Example: declare \p %TsigasCycleQueue with item counting and static iternal buffer of size 1024: - \code - typedef cds::container::TsigasCycleQueue< Foo, - typename cds::container::tsigas_queue::make_traits< - cds::opt::buffer< cds::opt::v::initialized_static_buffer< void *, 1024 >, - cds::opt::item_counter< cds::atomicity::item_counter > - >::type - > myQueue; - \endcode - */ - template - struct make_traits { -# ifdef CDS_DOXYGEN_INVOKED - typedef implementation_defined type; ///< Metafunction result -# else - typedef typename cds::opt::make_options< - typename cds::opt::find_type_traits< traits, Options... >::type - , Options... - >::type type; -# endif - }; - - } // namespace tsigas_queue - - //@cond - namespace details { - template - struct make_tsigas_cycle_queue - { - typedef T value_type; - typedef Traits traits; - - typedef typename traits::allocator::template rebind::other allocator_type; - typedef cds::details::Allocator< value_type, allocator_type > cxx_allocator; - - struct node_deallocator - { - void operator ()( value_type * pNode ) - { - cxx_allocator().Delete( pNode ); - } - }; - typedef node_deallocator node_disposer; - - struct intrusive_traits: public traits - { - typedef node_deallocator disposer; - }; - - typedef intrusive::TsigasCycleQueue< value_type, intrusive_traits > type; - }; - } // namespace - //@endcond - - /// Non-blocking cyclic bounded queue - /** @ingroup cds_nonintrusive_queue - It is non-intrusive implementation of Tsigas & Zhang cyclic queue based on \p intrusive::TsigasCycleQueue. - - Source: - - [2000] Philippas Tsigas, Yi Zhang "A Simple, Fast and Scalable Non-Blocking Concurrent FIFO Queue - for Shared Memory Multiprocessor Systems" - - Template arguments: - - \p T is a type stored in the queue. - - \p Traits - queue traits, default is \p tsigas_queue::traits. You can use \p tsigas_queue::make_traits - metafunction to make your traits or just derive your traits from \p %tsigas_queue::traits: - \code - struct myTraits: public cds::container::tsigas_queue::traits { - typedef cds::atomicity::item_counter item_counter; - }; - typedef cds::container::TsigasCycleQueue< Foo, myTraits > myQueue; - - // Equivalent make_traits example: - typedef cds::container::TsigasCycleQueue< cds::gc::HP, Foo, - typename cds::container::tsigas_queue::make_traits< - cds::opt::item_counter< cds::atomicity::item_counter > - >::type - > myQueue; - \endcode - - \par Examples: - \code - #include - - struct Foo { - ... - }; - - // Queue of Foo, capacity is 1024, statically allocated buffer: - typedef cds::container::TsigasCycleQueue< Foo, - typename cds::container::tsigas_queue::make_traits< - cds::opt::buffer< cds::opt::v::initialized_static_buffer< Foo, 1024 > > - >::type - > static_queue; - static_queue stQueue; - - // Queue of Foo, capacity is 1024, dynamically allocated buffer: - typedef cds::container::TsigasCycleQueue< Foo - typename cds::container::tsigas_queue::make_traits< - cds::opt::buffer< cds::opt::v::initialized_dynamic_buffer< Foo > > - >::type - > dynamic_queue; - dynamic_queue dynQueue( 1024 ); - \endcode - */ - template - class TsigasCycleQueue: -#ifdef CDS_DOXYGEN_INVOKED - intrusive::TsigasCycleQueue< T, Traits > -#else - details::make_tsigas_cycle_queue< T, Traits >::type -#endif - { - //@cond - typedef details::make_tsigas_cycle_queue< T, Traits > maker; - typedef typename maker::type base_class; - //@endcond - public: - typedef T value_type ; ///< Value type stored in the stack - typedef Traits traits; ///< Queue traits - - typedef typename traits::back_off back_off; ///< Back-off strategy used - typedef typename maker::allocator_type allocator_type; ///< Allocator type used for allocate/deallocate the items - typedef typename traits::item_counter item_counter; ///< Item counting policy used - typedef typename traits::memory_model memory_model; ///< Memory ordering. See \p cds::opt::memory_model option - - /// Rebind template arguments - template - struct rebind { - typedef TsigasCycleQueue< T2, Traits2> other ; ///< Rebinding result - }; - - protected: - //@cond - typedef typename maker::cxx_allocator cxx_allocator; - typedef typename maker::node_deallocator node_deallocator; // deallocate node - typedef typename maker::node_disposer node_disposer; - //@endcond - - protected: - ///@cond - static value_type * alloc_node() - { - return cxx_allocator().New(); - } - static value_type * alloc_node( const value_type& val ) - { - return cxx_allocator().New( val ); - } - template - static value_type * alloc_node_move( Args&&... args ) - { - return cxx_allocator().MoveNew( std::forward( args )... ); - } - static void free_node( value_type * p ) - { - node_deallocator()( p ); - } - - struct node_disposer2 { - void operator()( value_type * pNode ) - { - free_node( pNode ); - } - }; - typedef std::unique_ptr< value_type, node_disposer2 > scoped_node_ptr; - //@endcond - - public: - /// Initialize empty queue of capacity \p nCapacity - /** - If internal buffer type is \p cds::opt::v::initialized_static_buffer, the \p nCapacity parameter is ignored. - - Note, the real capacity of queue is \p nCapacity - 2. - */ - TsigasCycleQueue( size_t nCapacity = 0 ) - : base_class( nCapacity ) - {} - - /// Enqueues \p val value into the queue. - /** - The function makes queue node in dynamic memory calling copy constructor for \p val - and then it calls \p intrusive::TsigasCycleQueue::enqueue. - - Returns \p true if success, \p false if the queue is full. - */ - bool enqueue( value_type const& val ) - { - scoped_node_ptr p( alloc_node(val)); - if ( base_class::enqueue( *p )) { - p.release(); - return true; - } - return false; - } - - /// Enqueues \p val value into the queue, move semantics - bool enqueue( value_type&& val ) - { - scoped_node_ptr p( alloc_node_move( std::move( val ))); - if ( base_class::enqueue( *p )) { - p.release(); - return true; - } - return false; - } - - /// Enqueues data to the queue using a functor - /** - \p Func is a functor called to create node. - The functor \p f takes one argument - a reference to a new node of type \ref value_type : - \code - cds::container::TsigasCysleQueue< Foo > myQueue; - Bar bar; - myQueue.enqueue_with( [&bar]( Foo& dest ) { dest = bar; } ); - \endcode - */ - template - bool enqueue_with( Func f ) - { - scoped_node_ptr p( alloc_node()); - f( *p ); - if ( base_class::enqueue( *p )) { - p.release(); - return true; - } - return false; - } - - /// Enqueues data of type \ref value_type constructed with std::forward(args)... - template - bool emplace( Args&&... args ) - { - scoped_node_ptr p ( alloc_node_move( std::forward(args)...)); - if ( base_class::enqueue( *p)) { - p.release(); - return true; - } - return false; - } - - /// Synonym for \p enqueue( value_type const& ) - bool push( value_type const& data ) - { - return enqueue( data ); - } - - /// Synonym for \p enqueue( value_type&& ) - bool push( value_type&& data ) - { - return enqueue( std::move( data )); - } - - /// Synonym for \p enqueue_with() function - template - bool push_with( Func f ) - { - return enqueue_with( f ); - } - - /// Dequeues a value using a functor - /** - \p Func is a functor called to copy dequeued value. - The functor takes one argument - a reference to removed node: - \code - cds:container::TsigasCycleQueue< Foo > myQueue; - Bar bar; - myQueue.dequeue_with( [&bar]( Foo& src ) { bar = std::move( src );}); - \endcode - The functor is called only if the queue is not empty. - */ - template - bool dequeue_with( Func f ) - { - value_type * p = base_class::dequeue(); - if ( p ) { - f( *p ); - free_node( p ); - return true; - } - return false; - } - - /// 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. - 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 = std::move( src );}); - } - - /// Synonym for \p dequeue() function - bool pop( value_type& dest ) - { - return dequeue( dest ); - } - - /// Synonym for \p dequeue_with() function - template - bool pop_with( Func f ) - { - return dequeue_with( f ); - } - - /// Checks if the queue is empty - bool empty() const - { - return base_class::empty(); - } - - /// Clear the queue - /** - The function repeatedly calls \p dequeue() until it returns \p nullptr. - */ - void clear() - { - base_class::clear(); - } - - /// Returns queue's item count - /** \copydetails cds::intrusive::TsigasCycleQueue::size() - */ - size_t size() const - { - return base_class::size(); - } - - /// Returns capacity of cyclic buffer - size_t capacity() const - { - return base_class::capacity(); - } - }; - -}} // namespace cds::intrusive - -#endif // #ifndef CDSLIB_CONTAINER_TSIGAS_CYCLE_QUEUE_H diff --git a/cds/details/bounded_container.h b/cds/details/bounded_container.h index 390be48e..755d4b06 100644 --- a/cds/details/bounded_container.h +++ b/cds/details/bounded_container.h @@ -35,7 +35,7 @@ namespace cds { /// Bounded container /** If a container has upper limit of item then it should be based on bounded_container class. - Example of those containers: cyclic queue (cds::container::TsigasCycleQueue) + Example of those containers: cyclic queue (\p cds::container::VyukovMPMCCycleQueue) */ struct bounded_container {}; } // namespace cds diff --git a/cds/intrusive/tsigas_cycle_queue.h b/cds/intrusive/tsigas_cycle_queue.h deleted file mode 100644 index 55076276..00000000 --- a/cds/intrusive/tsigas_cycle_queue.h +++ /dev/null @@ -1,457 +0,0 @@ -/* - This file is a part of libcds - Concurrent Data Structures library - - (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016 - - 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_TSIGAS_CYCLE_QUEUE_H -#define CDSLIB_INTRUSIVE_TSIGAS_CYCLE_QUEUE_H - -#include -#include -#include -#include - -namespace cds { namespace intrusive { - - /// TsigasCycleQueue related definitions - /** @ingroup cds_intrusive_helper - */ - namespace tsigas_queue { - - /// TsigasCycleQueue default traits - struct traits - { - /// Buffer type for cyclic array - /* - The type of element for the buffer is not important: the queue rebinds - buffer for required type via \p rebind metafunction. - - For \p TsigasCycleQueue queue the buffer size should have power-of-2 size. - - You should use any initialized buffer type, see \p opt::buffer. - */ - typedef cds::opt::v::initialized_dynamic_buffer< void * > buffer; - - /// Back-off strategy - typedef cds::backoff::empty back_off; - - /// The functor used for dispose removed items. Default is \p opt::v::empty_disposer. This option is used for dequeuing - typedef opt::v::empty_disposer disposer; - - /// Item counting feature; by default, disabled. Use \p cds::atomicity::item_counter to enable item counting - typedef atomicity::empty_item_counter item_counter; - - /// C++ memory ordering model - /** - Can be \p opt::v::relaxed_ordering (relaxed memory model, the default) - or \p opt::v::sequential_consistent (sequentially consisnent memory model). - */ - typedef opt::v::relaxed_ordering memory_model; - - /// Padding for internal critical atomic data. Default is \p opt::cache_line_padding - enum { padding = opt::cache_line_padding }; - }; - - /// Metafunction converting option list to \p tsigas_queue::traits - /** - Supported \p Options are: - - \p opt::buffer - the buffer type for internal cyclic array. Possible types are: - \p opt::v::initialized_dynamic_buffer (the default), \p opt::v::initialized_static_buffer. The type of - element in the buffer is not important: it will be changed via \p rebind metafunction. - - \p opt::back_off - back-off strategy used, default is \p cds::backoff::empty. - - \p opt::disposer - the functor used for dispose removed items. Default is \p opt::v::empty_disposer. This option is used - when dequeuing. - - \p opt::item_counter - the type of item counting feature. Default is \p cds::atomicity::empty_item_counter (item counting disabled) - To enable item counting use \p cds::atomicity::item_counter - - \p opt::padding - padding for internal critical atomic data. Default is \p opt::cache_line_padding - - \p opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default) - or \p opt::v::sequential_consistent (sequentially consisnent memory model). - - Example: declare \p %TsigasCycleQueue with item counting and static iternal buffer of size 1024: - \code - typedef cds::intrusive::TsigasCycleQueue< Foo, - typename cds::intrusive::tsigas_queue::make_traits< - cds::opt::buffer< cds::opt::v::initialized_static_buffer< void *, 1024 >, - cds::opt::item_counte< cds::atomicity::item_counter > - >::type - > myQueue; - \endcode - */ - template - struct make_traits { -# ifdef CDS_DOXYGEN_INVOKED - typedef implementation_defined type; ///< Metafunction result -# else - typedef typename cds::opt::make_options< - typename cds::opt::find_type_traits< traits, Options... >::type - , Options... - >::type type; -# endif - }; - - - } //namespace tsigas_queue - - /// Non-blocking cyclic queue discovered by Philippas Tsigas and Yi Zhang - /** @ingroup cds_intrusive_queue - - Source: - \li [2000] Philippas Tsigas, Yi Zhang "A Simple, Fast and Scalable Non-Blocking Concurrent FIFO Queue - for Shared Memory Multiprocessor Systems" - - Template arguments: - - \p T - value type to be stored in queue. The queue stores pointers to passed data of type \p T. - Restriction: the queue can manage at least two-byte aligned data: the least significant bit (LSB) - of any pointer stored in the queue must be zero since the algorithm may use LSB - as a flag that marks the free cell. - - \p Traits - queue traits, default is \p tsigas_queue::traits. You can use \p tsigas_queue::make_traits - metafunction to make your traits or just derive your traits from \p %tsigas_queue::traits: - \code - struct myTraits: public cds::intrusive::tsigas_queue::traits { - typedef cds::atomicity::item_counter item_counter; - }; - typedef cds::intrusive::TsigasCycleQueue< Foo, myTraits > myQueue; - - // Equivalent make_traits example: - typedef cds::intrusive::TsigasCycleQueue< Foo, - typename cds::intrusive::tsigas_queue::make_traits< - cds::opt::item_counter< cds::atomicity::item_counter > - >::type - > myQueue; - \endcode - - This queue algorithm does not require any garbage collector. - - \par Examples: - \code - #include - - struct Foo { - ... - }; - - // Queue of Foo pointers, capacity is 1024, statically allocated buffer: - struct queue_traits: public cds::intrusive::tsigas_queue::traits - { - typedef cds::opt::v::initialized_static_buffer< Foo, 1024 > buffer; - }; - typedef cds::intrusive::TsigasCycleQueue< Foo, queue_traits > static_queue; - static_queue stQueue; - - // Queue of Foo pointers, capacity is 1024, dynamically allocated buffer, with item counting: - typedef cds::intrusive::TsigasCycleQueue< Foo, - typename cds::intrusive::tsigas_queue::make_traits< - cds::opt::buffer< cds::opt::v::initialized_dynamic_buffer< Foo > >, - cds::opt::item_counter< cds::atomicity::item_counter > - >::type - > dynamic_queue; - dynamic_queue dynQueue( 1024 ); - \endcode - */ - template - class TsigasCycleQueue: public cds::bounded_container - { - public: - /// Rebind template arguments - template - struct rebind { - typedef TsigasCycleQueue< T2, Traits2 > other ; ///< Rebinding result - }; - - public: - typedef T value_type; ///< type of value to be stored in the queue - typedef Traits traits; ///< Queue traits - typedef typename traits::item_counter item_counter; ///< Item counter type - typedef typename traits::disposer disposer; ///< Item disposer - typedef typename traits::back_off back_off; ///< back-off strategy used - typedef typename traits::memory_model memory_model; ///< Memory ordering. See cds::opt::memory_model option - typedef typename traits::buffer::template rebind< atomics::atomic >::other buffer; ///< Internal buffer - - protected: - //@cond - typedef size_t index_type; - //@endcond - - protected: - //@cond - buffer m_buffer ; ///< array of pointer T *, array size is equal to m_nCapacity+1 - typename opt::details::apply_padding< index_type, traits::padding >::padding_type pad1_; - atomics::atomic m_nHead ; ///< index of queue's head - typename opt::details::apply_padding< index_type, traits::padding >::padding_type pad2_; - atomics::atomic m_nTail ; ///< index of queue's tail - typename opt::details::apply_padding< index_type, traits::padding >::padding_type pad3_; - item_counter m_ItemCounter; ///< item counter - //@endcond - - protected: - //@cond - static CDS_CONSTEXPR intptr_t const free0 = 0; - static CDS_CONSTEXPR intptr_t const free1 = 1; - - static bool is_free( const value_type * p ) CDS_NOEXCEPT - { - return (reinterpret_cast(p) & ~intptr_t(1)) == 0; - } - - size_t CDS_CONSTEXPR buffer_capacity() const CDS_NOEXCEPT - { - return m_buffer.capacity(); - } - - index_type CDS_CONSTEXPR modulo() const CDS_NOEXCEPT - { - return buffer_capacity() - 1; - } - //@endcond - - public: - /// Initialize empty queue of capacity \p nCapacity - /** - If internal buffer type is \p cds::opt::v::initialized_static_buffer, the \p nCapacity parameter is ignored. - - Note that the real capacity of queue is \p nCapacity - 2. - */ - TsigasCycleQueue( size_t nCapacity = 0 ) - : m_buffer( nCapacity ) - , m_nHead(0) - , m_nTail(1) - { - m_buffer.zeroize(); - } - - /// Clears the queue - ~TsigasCycleQueue() - { - clear(); - } - - /// Enqueues an item to the queue - /** @anchor cds_intrusive_TsigasQueue_enqueue - Returns \p true if success, \p false if queue is full - */ - bool enqueue( value_type& data ) - { - value_type * pNewNode = &data; - assert( (reinterpret_cast(pNewNode) & 1) == 0 ); - back_off bkoff; - - const index_type nModulo = modulo(); - - do { - index_type te = m_nTail.load(memory_model::memory_order_acquire); - index_type ate = te; - value_type * tt = m_buffer[ ate ].load(memory_model::memory_order_relaxed); - index_type temp = ( ate + 1 ) & nModulo ; // next item after tail - - // Looking for actual tail - while ( !is_free( tt )) { - if ( te != m_nTail.load(memory_model::memory_order_relaxed)) // check the tail consistency - goto TryAgain; - if ( temp == m_nHead.load(memory_model::memory_order_acquire)) // queue full? - break; - tt = m_buffer[ temp ].load(memory_model::memory_order_relaxed); - ate = temp; - temp = (temp + 1) & nModulo; - } - - if ( te != m_nTail.load(memory_model::memory_order_acquire)) - continue; - - // Check whether queue is full - if ( temp == m_nHead.load(memory_model::memory_order_acquire)) { - ate = ( temp + 1 ) & nModulo; - tt = m_buffer[ ate ].load(memory_model::memory_order_relaxed); - if ( !is_free( tt )) { - return false; // Queue is full - } - - // help the dequeue to update head - m_nHead.compare_exchange_strong( temp, ate, memory_model::memory_order_release, atomics::memory_order_relaxed ); - continue; - } - - if ( tt == reinterpret_cast(free1)) - pNewNode = reinterpret_cast(reinterpret_cast( pNewNode ) | 1); - if ( te != m_nTail.load(memory_model::memory_order_acquire)) - continue; - - // get actual tail and try to enqueue new node - if ( m_buffer[ate].compare_exchange_strong( tt, pNewNode, memory_model::memory_order_release, atomics::memory_order_relaxed )) { - if ( temp % 2 == 0 ) - m_nTail.compare_exchange_strong( te, temp, memory_model::memory_order_release, atomics::memory_order_relaxed ); - ++m_ItemCounter; - return true; - } - TryAgain:; - } while ( bkoff(), true ); - - // No control path reaches this line! - return false; - } - - /// Dequeues item from the queue - /** @anchor cds_intrusive_TsigasQueue_dequeue - If the queue is empty the function returns \p nullptr - - Dequeue does not call value disposer. You may manually dispose returned value if it is needed. - */ - value_type * dequeue() - { - back_off bkoff; - - const index_type nModulo = modulo(); - do { - index_type th = m_nHead.load(memory_model::memory_order_acquire); - index_type temp = ( th + 1 ) & nModulo; - value_type * tt = m_buffer[ temp ].load(memory_model::memory_order_relaxed); - value_type * pNull; - - // find the actual head after this loop - while ( is_free( tt )) { - if ( th != m_nHead.load(memory_model::memory_order_relaxed)) - goto TryAgain; - - // two consecutive nullptr means the queue is empty - if ( temp == m_nTail.load(memory_model::memory_order_acquire)) - return nullptr; - - temp = ( temp + 1 ) & nModulo; - tt = m_buffer[ temp ].load(memory_model::memory_order_relaxed); - } - - if ( th != m_nHead.load(memory_model::memory_order_relaxed)) - continue; - - // check whether the queue is empty - if ( temp == m_nTail.load(memory_model::memory_order_acquire)) { - // help the enqueue to update end - m_nTail.compare_exchange_weak( temp, (temp + 1) & nModulo, memory_model::memory_order_release, atomics::memory_order_relaxed ); - continue; - } - - pNull = reinterpret_cast((reinterpret_cast(tt) & 1) ? free0 : free1); - - if ( th != m_nHead.load(memory_model::memory_order_relaxed)) - continue; - - // Get the actual head, null means empty - if ( m_buffer[temp].compare_exchange_weak( tt, pNull, memory_model::memory_order_acquire, atomics::memory_order_relaxed )) { - if ( temp % 2 == 0 ) - m_nHead.compare_exchange_weak( th, temp, memory_model::memory_order_release, atomics::memory_order_relaxed ); - --m_ItemCounter; - return reinterpret_cast(reinterpret_cast( tt ) & ~intptr_t(1)); - } - - TryAgain:; - } while ( bkoff(), true ); - - // No control path reaches this line! - return nullptr; - } - - /// Synonym for \p enqueue() - bool push( value_type& data ) - { - return enqueue( data ); - } - - /// Synonym for \p dequeue() - value_type * pop() - { - return dequeue(); - } - - /// Checks if the queue is empty - bool empty() const - { - const index_type nModulo = modulo(); - - TryAgain: - index_type th = m_nHead.load(memory_model::memory_order_relaxed); - index_type temp = ( th + 1 ) & nModulo; - const value_type * tt = m_buffer[ temp ].load(memory_model::memory_order_relaxed); - - // find the actual head after this loop - while ( is_free( tt )) { - if ( th != m_nHead.load(memory_model::memory_order_relaxed)) - goto TryAgain; - // two consecutive nullptr means queue empty - if ( temp == m_nTail.load(memory_model::memory_order_relaxed)) - return true; - temp = ( temp + 1 ) & nModulo; - tt = m_buffer[ temp ].load(memory_model::memory_order_relaxed); - } - return false; - } - - /// Clears queue in lock-free manner. - /** - \p f parameter is a functor to dispose removed items: - \code - myQueue.clear( []( value_type * p ) { delete p; } ); - \endcode - */ - template - void clear( Disposer f ) - { - value_type * pv; - while ( (pv = pop()) != nullptr ) { - f( pv ); - } - } - - /// Clears the queue - /** - This function uses the disposer that is specified in \p Traits, - see \p tsigas_queue::traits::disposer. - */ - void clear() - { - clear( disposer()); - } - - /// Returns queue's item count - /** - The value returned depends on \p tsigas_queue::traits::item_counter. - For \p atomicity::empty_item_counter, the function always returns 0. - */ - size_t size() const CDS_NOEXCEPT - { - return m_ItemCounter.value(); - } - - /// Returns capacity of internal cyclic buffer - size_t CDS_CONSTEXPR capacity() const CDS_NOEXCEPT - { - return buffer_capacity() - 2; - } - }; - -}} // namespace cds::intrusive - -#endif // #ifndef CDSLIB_INTRUSIVE_TSIGAS_CYCLE_QUEUE_H diff --git a/change.log b/change.log index 7488246f..88be5d79 100644 --- a/change.log +++ b/change.log @@ -21,6 +21,7 @@ and uninitialized (cds::opt::v::uninitialized_dynamic_buffer, cds::opt::v::uninitialized_static_buffer) ones. The old cds::opt::v::dynamic_buffer and cds::opt::v::static_buffer classes are removed. + - Removed: TsigasCysleQueue (due undecidable ABA-problem) - Fixed: use-after-free bug in VyukovMPMCCycleQueue internal buffer. To prevent this bug the queue uses an uninitialized buffer now. - Fixed: rare priority inversion bug in MSPriorityQueue diff --git a/projects/Win/vc14/cds.vcxproj b/projects/Win/vc14/cds.vcxproj index 6454034d..99241488 100644 --- a/projects/Win/vc14/cds.vcxproj +++ b/projects/Win/vc14/cds.vcxproj @@ -713,7 +713,6 @@ - @@ -741,7 +740,6 @@ - diff --git a/projects/Win/vc14/cds.vcxproj.filters b/projects/Win/vc14/cds.vcxproj.filters index 66c75e1e..b03ac73f 100644 --- a/projects/Win/vc14/cds.vcxproj.filters +++ b/projects/Win/vc14/cds.vcxproj.filters @@ -505,9 +505,6 @@ Header Files\cds\intrusive - - Header Files\cds\intrusive - Header Files\cds\intrusive @@ -589,9 +586,6 @@ Header Files\cds\container - - Header Files\cds\container - Header Files\cds\container diff --git a/projects/Win/vc14/gtest-queue.vcxproj b/projects/Win/vc14/gtest-queue.vcxproj index 93db0c90..b6f03324 100644 --- a/projects/Win/vc14/gtest-queue.vcxproj +++ b/projects/Win/vc14/gtest-queue.vcxproj @@ -42,7 +42,6 @@ - @@ -55,7 +54,6 @@ false - diff --git a/projects/Win/vc14/gtest-queue.vcxproj.filters b/projects/Win/vc14/gtest-queue.vcxproj.filters index 386c2fe0..953b381d 100644 --- a/projects/Win/vc14/gtest-queue.vcxproj.filters +++ b/projects/Win/vc14/gtest-queue.vcxproj.filters @@ -53,9 +53,6 @@ Source Files - - Source Files - Source Files @@ -92,9 +89,6 @@ Source Files - - Source Files - diff --git a/test/stress/queue/bounded_queue_fulness.cpp b/test/stress/queue/bounded_queue_fulness.cpp index d133fa06..70f33e65 100644 --- a/test/stress/queue/bounded_queue_fulness.cpp +++ b/test/stress/queue/bounded_queue_fulness.cpp @@ -155,7 +155,6 @@ namespace { test( queue ); \ } - CDSSTRESS_TsigasQueue( bounded_queue_fulness ) CDSSTRESS_VyukovQueue( bounded_queue_fulness ) #undef CDSSTRESS_Queue_F diff --git a/test/stress/queue/intrusive_push_pop.cpp b/test/stress/queue/intrusive_push_pop.cpp index 8c8c743c..22b2b352 100644 --- a/test/stress/queue/intrusive_push_pop.cpp +++ b/test/stress/queue/intrusive_push_pop.cpp @@ -437,8 +437,6 @@ namespace { test( q, arrValue, 0, 0 ); \ } - CDSSTRESS_QUEUE_F( TsigasCycleQueue_dyn ) - CDSSTRESS_QUEUE_F( TsigasCycleQueue_dyn_ic ) CDSSTRESS_QUEUE_F( VyukovMPMCCycleQueue_dyn ) CDSSTRESS_QUEUE_F( VyukovMPMCCycleQueue_dyn_ic ) #undef CDSSTRESS_QUEUE_F diff --git a/test/stress/queue/intrusive_queue_type.h b/test/stress/queue/intrusive_queue_type.h index 4a88e80a..c03056f9 100644 --- a/test/stress/queue/intrusive_queue_type.h +++ b/test/stress/queue/intrusive_queue_type.h @@ -34,7 +34,6 @@ #include #include #include -#include #include #include #include @@ -244,62 +243,6 @@ namespace queue { {}; typedef cds::intrusive::OptimisticQueue< cds::gc::DHP, T, traits_OptimisticQueue_DHP_stat > OptimisticQueue_DHP_stat; - // TsigasCycleQueue - class TsigasCycleQueue_dyn - : public cds::intrusive::TsigasCycleQueue< T, - typename cds::intrusive::tsigas_queue::make_traits< - cds::opt::buffer< cds::opt::v::initialized_dynamic_buffer< int > > - >::type - > - { - typedef cds::intrusive::TsigasCycleQueue< T, - typename cds::intrusive::tsigas_queue::make_traits< - cds::opt::buffer< cds::opt::v::initialized_dynamic_buffer< int > > - >::type - > base_class; - public: - TsigasCycleQueue_dyn() - : base_class( 1024 * 64 ) - {} - - TsigasCycleQueue_dyn( size_t nCapacity ) - : base_class( nCapacity ) - {} - - cds::opt::none statistics() const - { - return cds::opt::none(); - } - }; - - class TsigasCycleQueue_dyn_ic - : public cds::intrusive::TsigasCycleQueue< T, - typename cds::intrusive::tsigas_queue::make_traits< - cds::opt::buffer< cds::opt::v::initialized_dynamic_buffer< int > > - ,cds::opt::item_counter< cds::atomicity::item_counter > - >::type - > - { - typedef cds::intrusive::TsigasCycleQueue< T, - typename cds::intrusive::tsigas_queue::make_traits< - cds::opt::buffer< cds::opt::v::initialized_dynamic_buffer< int > > - ,cds::opt::item_counter< cds::atomicity::item_counter > - >::type - > base_class; - public: - TsigasCycleQueue_dyn_ic() - : base_class( 1024 * 64 ) - {} - TsigasCycleQueue_dyn_ic( size_t nCapacity ) - : base_class( nCapacity ) - {} - - cds::opt::none statistics() const - { - return cds::opt::none(); - } - }; - // VyukovMPMCCycleQueue struct traits_VyukovMPMCCycleQueue_dyn : public cds::intrusive::vyukov_queue::traits { diff --git a/test/stress/queue/pop.cpp b/test/stress/queue/pop.cpp index 2747d125..b9ba753c 100644 --- a/test/stress/queue/pop.cpp +++ b/test/stress/queue/pop.cpp @@ -185,7 +185,6 @@ namespace { test( queue ); \ } - CDSSTRESS_TsigasQueue( queue_pop ) CDSSTRESS_VyukovQueue( queue_pop ) #undef CDSSTRESS_Queue_F diff --git a/test/stress/queue/push.cpp b/test/stress/queue/push.cpp index 0be51017..cc043ba7 100644 --- a/test/stress/queue/push.cpp +++ b/test/stress/queue/push.cpp @@ -188,7 +188,6 @@ namespace { test( queue ); \ } - CDSSTRESS_TsigasQueue( queue_push ) CDSSTRESS_VyukovQueue( queue_push ) #undef CDSSTRESS_Queue_F diff --git a/test/stress/queue/push_pop.cpp b/test/stress/queue/push_pop.cpp index 927712d0..6db97a62 100644 --- a/test/stress/queue/push_pop.cpp +++ b/test/stress/queue/push_pop.cpp @@ -337,7 +337,6 @@ namespace { test( queue ); \ } - CDSSTRESS_TsigasQueue( queue_push_pop ) CDSSTRESS_VyukovQueue( queue_push_pop ) #undef CDSSTRESS_Queue_F diff --git a/test/stress/queue/queue_type.h b/test/stress/queue/queue_type.h index 92a35fe3..a5453787 100644 --- a/test/stress/queue/queue_type.h +++ b/test/stress/queue/queue_type.h @@ -35,7 +35,6 @@ #include #include #include -#include #include #include #include @@ -213,92 +212,6 @@ namespace queue { typedef cds::container::OptimisticQueue< cds::gc::DHP, Value, traits_OptimisticQueue_stat > OptimisticQueue_DHP_stat; - // TsigasCycleQueue - - class TsigasCycleQueue_dyn - : public cds::container::TsigasCycleQueue< Value, - typename cds::container::tsigas_queue::make_traits< - cds::opt::buffer< cds::opt::v::initialized_dynamic_buffer< int > > - >::type - > - { - typedef cds::container::TsigasCycleQueue< Value, - typename cds::container::tsigas_queue::make_traits< - cds::opt::buffer< cds::opt::v::initialized_dynamic_buffer< int > > - >::type - > base_class; - public: - TsigasCycleQueue_dyn() - : base_class( 1024 * 64 ) - {} - - TsigasCycleQueue_dyn( size_t nCapacity ) - : base_class( nCapacity ) - {} - - cds::opt::none statistics() const - { - return cds::opt::none(); - } - }; - - class TsigasCycleQueue_dyn_michaelAlloc - : public cds::container::TsigasCycleQueue< Value, - typename cds::container::tsigas_queue::make_traits< - cds::opt::buffer< cds::opt::v::initialized_dynamic_buffer< int > > - ,cds::opt::allocator< memory::MichaelAllocator > - >::type - > - { - typedef cds::container::TsigasCycleQueue< Value, - typename cds::container::tsigas_queue::make_traits< - cds::opt::buffer< cds::opt::v::initialized_dynamic_buffer< int > > - , cds::opt::allocator< memory::MichaelAllocator > - >::type - > base_class; - public: - TsigasCycleQueue_dyn_michaelAlloc() - : base_class( 1024 * 64 ) - {} - - TsigasCycleQueue_dyn_michaelAlloc( size_t nCapacity ) - : base_class( nCapacity ) - {} - - cds::opt::none statistics() const - { - return cds::opt::none(); - } - }; - - class TsigasCycleQueue_dyn_ic - : public cds::container::TsigasCycleQueue< Value, - typename cds::container::tsigas_queue::make_traits< - cds::opt::buffer< cds::opt::v::initialized_dynamic_buffer< int > > - ,cds::opt::item_counter< cds::atomicity::item_counter > - >::type - > - { - typedef cds::container::TsigasCycleQueue< Value, - typename cds::container::tsigas_queue::make_traits< - cds::opt::buffer< cds::opt::v::initialized_dynamic_buffer< int > > - ,cds::opt::item_counter< cds::atomicity::item_counter > - >::type - > base_class; - public: - TsigasCycleQueue_dyn_ic() - : base_class( 1024 * 64 ) - {} - TsigasCycleQueue_dyn_ic( size_t nCapacity ) - : base_class( nCapacity ) - {} - - cds::opt::none statistics() const - { - return cds::opt::none(); - } - }; - // VyukovMPMCCycleQueue struct traits_VyukovMPMCCycleQueue_dyn : public cds::container::vyukov_queue::traits { @@ -801,11 +714,6 @@ namespace cds_test { CDSSTRESS_Queue_F( test_fixture, SegmentedQueue_DHP_mutex_stat, 0 ) -#define CDSSTRESS_TsigasQueue( test_fixture ) \ - CDSSTRESS_Queue_F( test_fixture, TsigasCycleQueue_dyn, 0 ) \ - CDSSTRESS_Queue_F( test_fixture, TsigasCycleQueue_dyn_michaelAlloc, 0 ) \ - CDSSTRESS_Queue_F( test_fixture, TsigasCycleQueue_dyn_ic, 1 ) - #define CDSSTRESS_VyukovQueue( test_fixture ) \ CDSSTRESS_Queue_F( test_fixture, VyukovMPMCCycleQueue_dyn, 0 ) \ CDSSTRESS_Queue_F( test_fixture, VyukovMPMCCycleQueue_dyn_michaelAlloc, 0 ) \ diff --git a/test/stress/queue/random.cpp b/test/stress/queue/random.cpp index 2e7cbe1b..2a970dc1 100644 --- a/test/stress/queue/random.cpp +++ b/test/stress/queue/random.cpp @@ -252,7 +252,6 @@ namespace { test( queue ); \ } - CDSSTRESS_TsigasQueue( queue_random ) CDSSTRESS_VyukovQueue( queue_random ) #undef CDSSTRESS_Queue_F diff --git a/test/unit/queue/CMakeLists.txt b/test/unit/queue/CMakeLists.txt index 00310999..1c5ece95 100644 --- a/test/unit/queue/CMakeLists.txt +++ b/test/unit/queue/CMakeLists.txt @@ -14,7 +14,6 @@ set(CDSGTEST_QUEUE_SOURCES rwqueue.cpp segmented_queue_hp.cpp segmented_queue_dhp.cpp - tsigas_queue.cpp vyukov_mpmc_queue.cpp intrusive_basket_queue_hp.cpp intrusive_basket_queue_dhp.cpp @@ -27,7 +26,6 @@ set(CDSGTEST_QUEUE_SOURCES intrusive_optqueue_dhp.cpp intrusive_segmented_queue_hp.cpp intrusive_segmented_queue_dhp.cpp - intrusive_tsigas_queue.cpp intrusive_vyukov_queue.cpp ) diff --git a/test/unit/queue/intrusive_tsigas_queue.cpp b/test/unit/queue/intrusive_tsigas_queue.cpp deleted file mode 100644 index 0e29e9f1..00000000 --- a/test/unit/queue/intrusive_tsigas_queue.cpp +++ /dev/null @@ -1,112 +0,0 @@ -/* - This file is a part of libcds - Concurrent Data Structures library - - (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016 - - 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. -*/ - -#include -#include "test_intrusive_bounded_queue.h" - -namespace { - - class IntrusiveTsigasQueue : public cds_test::intrusive_bounded_queue - { - public: - struct disposer { - void operator()( item * p ) - { - ++p->nDisposeCount; - } - }; - }; - - static const size_t c_Capacity = 64; - static const size_t c_RealCapacity = c_Capacity - 2; - - TEST_F( IntrusiveTsigasQueue, defaulted ) - { - cds::intrusive::TsigasCycleQueue< item > q( c_Capacity ); - ASSERT_EQ( q.capacity(), c_RealCapacity ); - test( q ); - } - - TEST_F( IntrusiveTsigasQueue, disposer ) - { - struct traits : public cds::intrusive::tsigas_queue::traits - { - typedef IntrusiveTsigasQueue::disposer disposer; - typedef cds::atomicity::item_counter item_counter; - }; - - cds::intrusive::TsigasCycleQueue< item, traits > q( c_Capacity ); - ASSERT_EQ( q.capacity(), c_RealCapacity ); - test( q ); - } - - TEST_F( IntrusiveTsigasQueue, static_buffer ) - { - struct traits : public cds::intrusive::tsigas_queue::traits - { - typedef cds::opt::v::initialized_static_buffer< int, c_Capacity > buffer; - typedef IntrusiveTsigasQueue::disposer disposer; - }; - - cds::intrusive::TsigasCycleQueue< item, traits > q; - ASSERT_EQ( q.capacity(), c_RealCapacity ); - test( q ); - } - - TEST_F( IntrusiveTsigasQueue, dynamic_buffer ) - { - typedef typename cds::intrusive::tsigas_queue::make_traits< - cds::opt::buffer< cds::opt::v::initialized_dynamic_buffer< int >> - ,cds::opt::item_counter< cds::atomicity::item_counter > - ,cds::opt::back_off< cds::backoff::pause > - ,cds::intrusive::opt::disposer< disposer > - >::type traits; - - cds::intrusive::TsigasCycleQueue< item, traits > q( c_Capacity ); - ASSERT_EQ( q.capacity(), c_RealCapacity ); - test( q ); - } - - TEST_F( IntrusiveTsigasQueue, padding ) - { - struct traits : public cds::intrusive::tsigas_queue::traits - { - typedef cds::opt::v::initialized_static_buffer< int, c_Capacity > buffer; - typedef IntrusiveTsigasQueue::disposer disposer; - enum { padding = 16 | cds::opt::padding_tiny_data_only }; - }; - - cds::intrusive::TsigasCycleQueue< item, traits > q; - ASSERT_EQ( q.capacity(), c_RealCapacity ); - test( q ); - } - - -} // namespace diff --git a/test/unit/queue/tsigas_queue.cpp b/test/unit/queue/tsigas_queue.cpp deleted file mode 100644 index f6609575..00000000 --- a/test/unit/queue/tsigas_queue.cpp +++ /dev/null @@ -1,134 +0,0 @@ -/* - This file is a part of libcds - Concurrent Data Structures library - - (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016 - - 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. -*/ - -#include "test_bounded_queue.h" - -#include - -namespace { - namespace cc = cds::container; - - class TsigasCycleQueue: public cds_test::bounded_queue - {}; - - TEST_F( TsigasCycleQueue, defaulted ) - { - typedef cds::container::TsigasCycleQueue< int > test_queue; - - test_queue q( 128 ); - test(q); - } - - TEST_F( TsigasCycleQueue, stat ) - { - struct traits: public cds::container::tsigas_queue::traits - { - typedef cds::opt::v::initialized_static_buffer buffer; - }; - typedef cds::container::TsigasCycleQueue< int, traits > test_queue; - - test_queue q; - test( q ); - } - - TEST_F( TsigasCycleQueue, stat_item_counting ) - { - - typedef cds::container::TsigasCycleQueue< int, - cds::container::tsigas_queue::make_traits< - cds::opt::buffer< cds::opt::v::initialized_static_buffer> - , cds::opt::item_counter< cds::atomicity::item_counter> - >::type - > test_queue; - - test_queue q; - test( q ); - } - - TEST_F( TsigasCycleQueue, dynamic ) - { - struct traits : public cds::container::tsigas_queue::traits - { - typedef cds::opt::v::initialized_dynamic_buffer buffer; - }; - typedef cds::container::TsigasCycleQueue< int, traits > test_queue; - - test_queue q( 128 ); - test( q ); - } - - TEST_F( TsigasCycleQueue, dynamic_item_counting ) - { - typedef cds::container::TsigasCycleQueue< int, - cds::container::tsigas_queue::make_traits< - cds::opt::buffer< cds::opt::v::initialized_dynamic_buffer> - , cds::opt::item_counter< cds::atomicity::item_counter> - >::type - > test_queue; - - test_queue q( 128 ); - test( q ); - } - - TEST_F( TsigasCycleQueue, dynamic_padding ) - { - struct traits : public cds::container::tsigas_queue::traits - { - typedef cds::opt::v::initialized_dynamic_buffer buffer; - enum { padding = 16 }; - }; - typedef cds::container::TsigasCycleQueue< int, traits > test_queue; - - test_queue q( 128 ); - test( q ); - } - - TEST_F( TsigasCycleQueue, move ) - { - typedef cds::container::TsigasCycleQueue< std::string > test_queue; - - test_queue q( 128 ); - test_string( q ); - } - - TEST_F( TsigasCycleQueue, move_item_counting ) - { - struct traits : public cds::container::tsigas_queue::traits - { - typedef cds::atomicity::item_counter item_counter; - }; - typedef cds::container::TsigasCycleQueue< std::string, traits > test_queue; - - test_queue q( 128 ); - test_string( q ); - } - -} // namespace - -- 2.34.1