/*
    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_URCU_DETAILS_GPT_H
#define CDSLIB_URCU_DETAILS_GPT_H

#include <mutex>    //unique_lock
#include <limits>
#include <cds/urcu/details/gp.h>
#include <cds/urcu/dispose_thread.h>
#include <cds/algo/backoff_strategy.h>
#include <cds/container/vyukov_mpmc_cycle_queue.h>

namespace cds { namespace urcu {

    /// User-space general-purpose RCU with deferred threaded reclamation
    /**
        @headerfile cds/urcu/general_threaded.h

        This implementation is similar to \ref general_buffered but separate thread is created
        for deleting the retired objects. Like \p %general_buffered, the class contains an internal buffer
        where retired objects are accumulated. When the buffer becomes full,
        the RCU \p synchronize() function is called that waits until all reader/updater threads end up their read-side critical sections,
        i.e. until the RCU quiescent state will come. After that the "work ready" message is sent to reclamation thread.
        The reclamation thread frees the buffer.
        This synchronization cycle may be called in any thread that calls \p retire_ptr() function.

        There is a wrapper \ref cds_urcu_general_threaded_gc "gc<general_threaded>" for \p %general_threaded class
        that provides unified RCU interface. You should use this wrapper class instead \p %general_threaded

        The \p Buffer contains items of \ref cds_urcu_retired_ptr "epoch_retired_ptr" type

        and it should support a multiple producer/single consumer queue with the following interface:
        - <tt> bool push( epoch_retired_ptr& p ) </tt> - places the retired pointer \p p into queue. If the function
        returns \p false it means that the buffer is full and RCU synchronization cycle must be processed.
        - <tt>epoch_retired_ptr * front() </tt> - returns a pointer to the top element or \p nullptr if the buffer is empty.
        - <tt>bool pop_front() </tt> - pops the top element; returns \p false if the buffer is empty.
        - <tt>size_t size()</tt> - returns queue's item count.

        The buffer is considered as full if \p push() returns \p false or the buffer size reaches the RCU threshold.

        Template arguments:
        - \p Buffer - MPSC (muliple producer/single consumer) buffer type with FIFO semantics.

            Default is \p cds::container::VyukovMPSCCycleQueue. The buffer contains the objects of \ref epoch_retired_ptr
            type that contains additional \p m_nEpoch field. This field specifies an epoch when the object
            has been placed into the buffer. The \p %general_threaded object has a global epoch counter
            that is incremented on each \p synchronize() call. The epoch is used internally to prevent early deletion.
        - \p Lock - mutex type, default is \p std::mutex
        - \p DisposerThread - the reclamation thread class. Default is \ref cds::urcu::dispose_thread,
            see the description of this class for required interface.
        - \p Backoff - back-off schema, default is cds::backoff::Default
    */
    template <
        class Buffer = cds::container::VyukovMPSCCycleQueue< epoch_retired_ptr >
        ,class Lock = std::mutex
        ,class DisposerThread = dispose_thread<Buffer>
        ,class Backoff = cds::backoff::Default
    >
    class general_threaded: public details::gp_singleton< general_threaded_tag >
    {
        //@cond
        typedef details::gp_singleton< general_threaded_tag > base_class;
        //@endcond
    public:
        typedef Buffer          buffer_type ;   ///< Buffer type
        typedef Lock            lock_type   ;   ///< Lock type
        typedef Backoff         back_off    ;   ///< Back-off scheme
        typedef DisposerThread  disposer_thread ;   ///< Disposer thread type

        typedef general_threaded_tag    rcu_tag ;       ///< Thread-side RCU part
        typedef base_class::thread_gc   thread_gc ;     ///< Access lock class
        typedef typename thread_gc::scoped_lock scoped_lock ; ///< Access lock class

        static bool const c_bBuffered = true ; ///< This RCU buffers disposed elements

    protected:
        //@cond
        typedef details::gp_singleton_instance< rcu_tag >    singleton_ptr;

        struct scoped_disposer {
            void operator ()( general_threaded * p )
            {
                delete p;
            }
        };
        //@endcond

    protected:
        //@cond
        buffer_type               m_Buffer;
        atomics::atomic<uint64_t> m_nCurEpoch;
        lock_type                 m_Lock;
        size_t const              m_nCapacity;
        disposer_thread           m_DisposerThread;
        //@endcond

    public:
        /// Returns singleton instance
        static general_threaded * instance()
        {
            return static_cast<general_threaded *>( base_class::instance() );
        }
        /// Checks if the singleton is created and ready to use
        static bool isUsed()
        {
            return singleton_ptr::s_pRCU != nullptr;
        }

    protected:
        //@cond
        general_threaded( size_t nBufferCapacity )
            : m_Buffer( nBufferCapacity )
            , m_nCurEpoch( 1 )
            , m_nCapacity( nBufferCapacity )
        {}

        void flip_and_wait()
        {
            back_off bkoff;
            base_class::flip_and_wait( bkoff );
        }

        // Return: true - synchronize has been called, false - otherwise
        bool push_buffer( epoch_retired_ptr&& p )
        {
            bool bPushed = m_Buffer.push( p );
            if ( !bPushed || m_Buffer.size() >= capacity() ) {
                synchronize();
                if ( !bPushed )
                    p.free();
                return true;
            }
            return false;
        }

        //@endcond

    public:
        //@cond
        ~general_threaded()
        {}
        //@endcond

        /// Creates singleton object and starts reclamation thread
        /**
            The \p nBufferCapacity parameter defines RCU threshold.
        */
        static void Construct( size_t nBufferCapacity = 256 )
        {
            if ( !singleton_ptr::s_pRCU ) {
                std::unique_ptr< general_threaded, scoped_disposer > pRCU( new general_threaded( nBufferCapacity ) );
                pRCU->m_DisposerThread.start();

                singleton_ptr::s_pRCU = pRCU.release();
            }
        }

        /// Destroys singleton object and terminates internal reclamation thread
        static void Destruct( bool bDetachAll = false )
        {
            if ( isUsed() ) {
                general_threaded * pThis = instance();
                if ( bDetachAll )
                    pThis->m_ThreadList.detach_all();

                pThis->m_DisposerThread.stop( pThis->m_Buffer, std::numeric_limits< uint64_t >::max());

                delete pThis;
                singleton_ptr::s_pRCU = nullptr;
            }
        }

    public:
        /// Retires \p p pointer
        /**
            The method pushes \p p pointer to internal buffer.
            When the buffer becomes full \ref synchronize function is called
            to wait for the end of grace period and then
            a message is sent to the reclamation thread.
        */
        virtual void retire_ptr( retired_ptr& p )
        {
            if ( p.m_p )
                push_buffer( epoch_retired_ptr( p, m_nCurEpoch.load( atomics::memory_order_acquire )));
        }

        /// Retires the pointer chain [\p itFirst, \p itLast)
        template <typename ForwardIterator>
        void batch_retire( ForwardIterator itFirst, ForwardIterator itLast )
        {
            uint64_t nEpoch = m_nCurEpoch.load( atomics::memory_order_acquire );
            while ( itFirst != itLast ) {
                epoch_retired_ptr ep( *itFirst, nEpoch );
                ++itFirst;
                push_buffer( std::move(ep));
            }
        }

        /// Retires the pointer chain until \p Func returns \p nullptr retired pointer
        template <typename Func>
        void batch_retire( Func e )
        {
            uint64_t nEpoch = m_nCurEpoch.load( atomics::memory_order_acquire );
            for ( retired_ptr p{ e() }; p.m_p; ) {
                epoch_retired_ptr ep( p, nEpoch );
                p = e();
                push_buffer( std::move(ep));
            }
        }

        /// Waits to finish a grace period and calls disposing thread
        void synchronize()
        {
            synchronize( false );
        }

        //@cond
        void synchronize( bool bSync )
        {
            uint64_t nPrevEpoch = m_nCurEpoch.fetch_add( 1, atomics::memory_order_release );
            {
                std::unique_lock<lock_type> sl( m_Lock );
                flip_and_wait();
                flip_and_wait();
            }
            m_DisposerThread.dispose( m_Buffer, nPrevEpoch, bSync );
        }
        void force_dispose()
        {
            synchronize( true );
        }
        //@endcond

        /// Returns the threshold of internal buffer
        size_t capacity() const
        {
            return m_nCapacity;
        }
    };

    /// User-space general-purpose RCU with deferred threaded reclamation (stripped version)
    /**
        @headerfile cds/urcu/general_threaded.h

        This short version of \p general_threaded is intended for stripping debug info.
        If you use \p %general_threaded with default template arguments you may use
        this stripped version. All functionality of both classes are identical.
    */
    class general_threaded_stripped: public general_threaded<>
    {};

}} // namespace cds::urcu

#endif // #ifndef CDSLIB_URCU_DETAILS_GPT_H
