Removed TsigasCycleQueue (undecidable ABA problem)
authorkhizmax <libcds.dev@gmail.com>
Tue, 1 Nov 2016 17:30:06 +0000 (20:30 +0300)
committerkhizmax <libcds.dev@gmail.com>
Tue, 1 Nov 2016 17:30:06 +0000 (20:30 +0300)
19 files changed:
cds/container/tsigas_cycle_queue.h [deleted file]
cds/details/bounded_container.h
cds/intrusive/tsigas_cycle_queue.h [deleted file]
change.log
projects/Win/vc14/cds.vcxproj
projects/Win/vc14/cds.vcxproj.filters
projects/Win/vc14/gtest-queue.vcxproj
projects/Win/vc14/gtest-queue.vcxproj.filters
test/stress/queue/bounded_queue_fulness.cpp
test/stress/queue/intrusive_push_pop.cpp
test/stress/queue/intrusive_queue_type.h
test/stress/queue/pop.cpp
test/stress/queue/push.cpp
test/stress/queue/push_pop.cpp
test/stress/queue/queue_type.h
test/stress/queue/random.cpp
test/unit/queue/CMakeLists.txt
test/unit/queue/intrusive_tsigas_queue.cpp [deleted file]
test/unit/queue/tsigas_queue.cpp [deleted file]

diff --git a/cds/container/tsigas_cycle_queue.h b/cds/container/tsigas_cycle_queue.h
deleted file mode 100644 (file)
index 741b31b..0000000
+++ /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 <memory>
-#include <cds/intrusive/tsigas_cycle_queue.h>
-#include <cds/container/details/base.h>
-
-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 <typename... Options>
-        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 <typename T, typename Traits>
-        struct make_tsigas_cycle_queue
-        {
-            typedef T value_type;
-            typedef Traits traits;
-
-            typedef typename traits::allocator::template rebind<value_type>::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 <cds/container/tsigas_cycle_queue.h>
-
-        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 <typename T, typename Traits = tsigas_queue::traits>
-    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 <typename T2, typename Traits2>
-        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 <typename... Args>
-        static value_type * alloc_node_move( Args&&... args )
-        {
-            return cxx_allocator().MoveNew( std::forward<Args>( 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 <typename Func>
-        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 <tt>std::forward<Args>(args)...</tt>
-        template <typename... Args>
-        bool emplace( Args&&... args )
-        {
-            scoped_node_ptr p ( alloc_node_move( std::forward<Args>(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 <typename Func>
-        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 <typename Func>
-        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 <typename Func>
-        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
index 390be48..755d4b0 100644 (file)
@@ -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 (file)
index 5507627..0000000
+++ /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 <cds/intrusive/details/base.h>
-#include <cds/algo/atomic.h>
-#include <cds/details/bounded_container.h>
-#include <cds/opt/buffer.h>
-
-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 <typename... Options>
-        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.
-            <b>Restriction</b>: 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 <cds/intrusive/tsigas_cycle_queue.h>
-
-        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 <typename T, typename Traits = tsigas_queue::traits >
-    class TsigasCycleQueue: public cds::bounded_container
-    {
-    public:
-        /// Rebind template arguments
-        template <typename T2, typename Traits2>
-        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<value_type *> >::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<index_type>   m_nHead     ;   ///< index of queue's head
-        typename opt::details::apply_padding< index_type, traits::padding >::padding_type pad2_;
-        atomics::atomic<index_type>   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<intptr_t>(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<uintptr_t>(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<value_type *>(free1))
-                    pNewNode = reinterpret_cast<value_type *>(reinterpret_cast<intptr_t>( 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<value_type *>((reinterpret_cast<uintptr_t>(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<value_type *>(reinterpret_cast<intptr_t>( 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 <typename Disposer>
-        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
index 7488246..88be5d7 100644 (file)
@@ -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
index 6454034..9924148 100644 (file)
     <ClInclude Include="..\..\..\cds\intrusive\split_list.h" />\r
     <ClInclude Include="..\..\..\cds\intrusive\split_list_nogc.h" />\r
     <ClInclude Include="..\..\..\cds\intrusive\treiber_stack.h" />\r
-    <ClInclude Include="..\..\..\cds\intrusive\tsigas_cycle_queue.h" />\r
     <ClInclude Include="..\..\..\cds\intrusive\vyukov_mpmc_cycle_queue.h" />\r
     <ClInclude Include="..\..\..\cds\container\fcdeque.h" />\r
     <ClInclude Include="..\..\..\cds\container\fcpriority_queue.h" />\r
     <ClInclude Include="..\..\..\cds\container\split_list_set.h" />\r
     <ClInclude Include="..\..\..\cds\container\split_list_set_nogc.h" />\r
     <ClInclude Include="..\..\..\cds\container\treiber_stack.h" />\r
-    <ClInclude Include="..\..\..\cds\container\tsigas_cycle_queue.h" />\r
     <ClInclude Include="..\..\..\cds\container\vyukov_mpmc_cycle_queue.h" />\r
     <ClInclude Include="..\..\..\cds\container\details\make_lazy_kvlist.h" />\r
     <ClInclude Include="..\..\..\cds\container\details\make_lazy_list.h" />\r
index 66c75e1..b03ac73 100644 (file)
     <ClInclude Include="..\..\..\cds\intrusive\treiber_stack.h">\r
       <Filter>Header Files\cds\intrusive</Filter>\r
     </ClInclude>\r
-    <ClInclude Include="..\..\..\cds\intrusive\tsigas_cycle_queue.h">\r
-      <Filter>Header Files\cds\intrusive</Filter>\r
-    </ClInclude>\r
     <ClInclude Include="..\..\..\cds\intrusive\vyukov_mpmc_cycle_queue.h">\r
       <Filter>Header Files\cds\intrusive</Filter>\r
     </ClInclude>\r
     <ClInclude Include="..\..\..\cds\container\treiber_stack.h">\r
       <Filter>Header Files\cds\container</Filter>\r
     </ClInclude>\r
-    <ClInclude Include="..\..\..\cds\container\tsigas_cycle_queue.h">\r
-      <Filter>Header Files\cds\container</Filter>\r
-    </ClInclude>\r
     <ClInclude Include="..\..\..\cds\container\vyukov_mpmc_cycle_queue.h">\r
       <Filter>Header Files\cds\container</Filter>\r
     </ClInclude>\r
index 93db0c9..b6f0332 100644 (file)
@@ -42,7 +42,6 @@
     <ClCompile Include="..\..\..\test\unit\queue\intrusive_optqueue_hp.cpp" />\r
     <ClCompile Include="..\..\..\test\unit\queue\intrusive_segmented_queue_dhp.cpp" />\r
     <ClCompile Include="..\..\..\test\unit\queue\intrusive_segmented_queue_hp.cpp" />\r
-    <ClCompile Include="..\..\..\test\unit\queue\intrusive_tsigas_queue.cpp" />\r
     <ClCompile Include="..\..\..\test\unit\queue\intrusive_vyukov_queue.cpp" />\r
     <ClCompile Include="..\..\..\test\unit\queue\moirqueue_dhp.cpp" />\r
     <ClCompile Include="..\..\..\test\unit\queue\moirqueue_hp.cpp" />\r
@@ -55,7 +54,6 @@
       <ExcludedFromBuild Condition="'$(Configuration)|$(Platform)'=='Debug|x64'">false</ExcludedFromBuild>\r
     </ClCompile>\r
     <ClCompile Include="..\..\..\test\unit\queue\segmented_queue_hp.cpp" />\r
-    <ClCompile Include="..\..\..\test\unit\queue\tsigas_queue.cpp" />\r
     <ClCompile Include="..\..\..\test\unit\queue\vyukov_mpmc_queue.cpp" />\r
   </ItemGroup>\r
   <ItemGroup>\r
index 386c2fe..953b381 100644 (file)
@@ -53,9 +53,6 @@
     <ClCompile Include="..\..\..\test\unit\queue\vyukov_mpmc_queue.cpp">\r
       <Filter>Source Files</Filter>\r
     </ClCompile>\r
-    <ClCompile Include="..\..\..\test\unit\queue\tsigas_queue.cpp">\r
-      <Filter>Source Files</Filter>\r
-    </ClCompile>\r
     <ClCompile Include="..\..\..\test\unit\queue\intrusive_msqueue_hp.cpp">\r
       <Filter>Source Files</Filter>\r
     </ClCompile>\r
@@ -92,9 +89,6 @@
     <ClCompile Include="..\..\..\test\unit\queue\intrusive_vyukov_queue.cpp">\r
       <Filter>Source Files</Filter>\r
     </ClCompile>\r
-    <ClCompile Include="..\..\..\test\unit\queue\intrusive_tsigas_queue.cpp">\r
-      <Filter>Source Files</Filter>\r
-    </ClCompile>\r
   </ItemGroup>\r
   <ItemGroup>\r
     <ClInclude Include="..\..\..\test\unit\queue\test_generic_queue.h">\r
index d133fa0..70f33e6 100644 (file)
@@ -155,7 +155,6 @@ namespace {
         test( queue ); \
     }
 
-    CDSSTRESS_TsigasQueue( bounded_queue_fulness )
     CDSSTRESS_VyukovQueue( bounded_queue_fulness )
 
 #undef CDSSTRESS_Queue_F
index 8c8c743..22b2b35 100644 (file)
@@ -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
index 4a88e80..c03056f 100644 (file)
@@ -34,7 +34,6 @@
 #include <cds/intrusive/msqueue.h>
 #include <cds/intrusive/moir_queue.h>
 #include <cds/intrusive/optimistic_queue.h>
-#include <cds/intrusive/tsigas_cycle_queue.h>
 #include <cds/intrusive/vyukov_mpmc_cycle_queue.h>
 #include <cds/intrusive/basket_queue.h>
 #include <cds/intrusive/fcqueue.h>
@@ -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
         {
index 2747d12..b9ba753 100644 (file)
@@ -185,7 +185,6 @@ namespace {
         test( queue ); \
     }
 
-    CDSSTRESS_TsigasQueue( queue_pop )
     CDSSTRESS_VyukovQueue( queue_pop )
 
 #undef CDSSTRESS_Queue_F
index 0be5101..cc043ba 100644 (file)
@@ -188,7 +188,6 @@ namespace {
         test( queue ); \
     }
 
-    CDSSTRESS_TsigasQueue( queue_push )
     CDSSTRESS_VyukovQueue( queue_push )
 
 #undef CDSSTRESS_Queue_F
index 927712d..6db97a6 100644 (file)
@@ -337,7 +337,6 @@ namespace {
         test( queue ); \
     }
 
-    CDSSTRESS_TsigasQueue( queue_push_pop )
     CDSSTRESS_VyukovQueue( queue_push_pop )
 
 #undef CDSSTRESS_Queue_F
index 92a35fe..a545378 100644 (file)
@@ -35,7 +35,6 @@
 #include <cds/container/moir_queue.h>
 #include <cds/container/rwqueue.h>
 #include <cds/container/optimistic_queue.h>
-#include <cds/container/tsigas_cycle_queue.h>
 #include <cds/container/vyukov_mpmc_cycle_queue.h>
 #include <cds/container/basket_queue.h>
 #include <cds/container/fcqueue.h>
@@ -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<int> >
-                >::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<int> >
-                >::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 ) \
index 2e7cbe1..2a970dc 100644 (file)
@@ -252,7 +252,6 @@ namespace {
         test( queue ); \
     }
 
-    CDSSTRESS_TsigasQueue( queue_random )
     CDSSTRESS_VyukovQueue( queue_random )
 
 #undef CDSSTRESS_Queue_F
index 0031099..1c5ece9 100644 (file)
@@ -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 (file)
index 0e29e9f..0000000
+++ /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 <cds/intrusive/tsigas_cycle_queue.h>
-#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 (file)
index f660957..0000000
+++ /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 <cds/container/tsigas_cycle_queue.h>
-
-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<int, 128> 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<int, 128>>
-                , 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<int> 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<int>>
-                , 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<int> 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
-