issue #82: added doc about DCAS support

[libcds.git] / cds / gc / dhp.h

/*
    This file is a part of libcds - Concurrent Data Structures library

    (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2017

    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_GC_DHP_SMR_H
#define CDSLIB_GC_DHP_SMR_H

#include <exception>
#include <cds/gc/details/hp_common.h>
#include <cds/details/lib.h>
#include <cds/threading/model.h>
#include <cds/intrusive/free_list_selector.h>
#include <cds/details/throw_exception.h>
#include <cds/details/static_functor.h>
#include <cds/details/marked_ptr.h>
#include <cds/user_setup/cache_line.h>

namespace cds { namespace gc {

    /// Dynamic (adaptive) Hazard Pointer implementation details
    namespace dhp {
        using namespace cds::gc::hp::common;

        /// Exception "Dynamic Hazard Pointer SMR is not initialized"
        class not_initialized: public std::runtime_error
        {
        public:
            //@cond
            not_initialized()
                : std::runtime_error( "Global DHP SMR object is not initialized" )
            {}
            //@endcond
        };

        //@cond
        struct guard_block: public cds::intrusive::FreeListImpl::node
        {
            atomics::atomic<guard_block*>  next_block_;  // next block in the thread list

            guard_block()
                : next_block_( nullptr )
            {}

            guard* first()
            {
                return reinterpret_cast<guard*>( this + 1 );
            }
        };
        //@endcond

        //@cond
        /// \p guard_block allocator (global object)
        class hp_allocator
        {
            friend class smr;
        public:
            static hp_allocator& instance();

            CDS_EXPORT_API guard_block* alloc();
            void free( guard_block* block )
            {
                free_list_.put( block );
            }

        private:
            hp_allocator()
#ifdef CDS_ENABLE_HPSTAT
                : block_allocated_(0)
#endif
            {}
            CDS_EXPORT_API ~hp_allocator();

        private:
            cds::intrusive::FreeListImpl    free_list_; ///< list of free \p guard_block
#ifdef CDS_ENABLE_HPSTAT
        public:
            atomics::atomic<size_t>         block_allocated_;   ///< count of allocated blocks
#endif
        };
        //@endcond

        //@cond
        /// Per-thread hazard pointer storage
        class thread_hp_storage
        {
            friend class smr;
        public:
            thread_hp_storage( guard* arr, size_t nSize ) CDS_NOEXCEPT
                : free_head_( arr )
                , array_( arr )
                , initial_capacity_( nSize )
#       ifdef CDS_ENABLE_HPSTAT
                , alloc_guard_count_( 0 )
                , free_guard_count_( 0 )
                , extend_call_count_( 0 )
#       endif
            {
                // Initialize guards
                new( arr ) guard[nSize];
                extended_list_.store( nullptr, atomics::memory_order_release );
            }

            thread_hp_storage() = delete;
            thread_hp_storage( thread_hp_storage const& ) = delete;
            thread_hp_storage( thread_hp_storage&& ) = delete;

            ~thread_hp_storage()
            {
                clear();
            }

            guard* alloc()
            {
                if ( cds_unlikely( free_head_ == nullptr )) {
                    extend();
                    assert( free_head_ != nullptr );
                }

                guard* g = free_head_;
                free_head_ = g->next_;
                CDS_HPSTAT( ++alloc_guard_count_ );
                return g;
            }

            void free( guard* g ) CDS_NOEXCEPT
            {
                if ( g ) {
                    g->clear();
                    g->next_ = free_head_;
                    free_head_ = g;
                    CDS_HPSTAT( ++free_guard_count_ );
                }
            }

            template< size_t Capacity>
            size_t alloc( guard_array<Capacity>& arr )
            {
                for ( size_t i = 0; i < Capacity; ++i ) {
                    if ( cds_unlikely( free_head_ == nullptr ))
                        extend();
                    arr.reset( i, free_head_ );
                    free_head_ = free_head_->next_;
                }
                CDS_HPSTAT( alloc_guard_count_ += Capacity );
                return Capacity;
            }

            template <size_t Capacity>
            void free( guard_array<Capacity>& arr ) CDS_NOEXCEPT
            {
                guard* gList = free_head_;
                for ( size_t i = 0; i < Capacity; ++i ) {
                    guard* g = arr[i];
                    if ( g ) {
                        g->clear();
                        g->next_ = gList;
                        gList = g;
                        CDS_HPSTAT( ++free_guard_count_ );
                    }
                }
                free_head_ = gList;
            }

            void clear()
            {
                // clear array_
                for ( guard* cur = array_, *last = array_ + initial_capacity_; cur < last; ++cur )
                    cur->clear();

                // free all extended blocks
                hp_allocator& a = hp_allocator::instance();
                for ( guard_block* p = extended_list_.load( atomics::memory_order_relaxed ); p; ) {
                    guard_block* next = p->next_block_.load( atomics::memory_order_relaxed );
                    a.free( p );
                    p = next;
                }

                extended_list_.store( nullptr, atomics::memory_order_release );
            }

            void init()
            {
                assert( extended_list_.load(atomics::memory_order_relaxed) == nullptr );

                guard* p = array_;
                for ( guard* pEnd = p + initial_capacity_ - 1; p != pEnd; ++p )
                    p->next_ = p + 1;
                p->next_ = nullptr;
                free_head_ = array_;
            }

        private:
            void extend()
            {
                assert( free_head_ == nullptr );

                guard_block* block = hp_allocator::instance().alloc();
                block->next_block_.store( extended_list_.load( atomics::memory_order_relaxed ), atomics::memory_order_release );
                extended_list_.store( block, atomics::memory_order_release );
                free_head_ = block->first();
                CDS_HPSTAT( ++extend_call_count_ );
            }

        private:
            guard*          free_head_;        ///< Head of free guard list
            atomics::atomic<guard_block*> extended_list_;    ///< Head of extended guard blocks allocated for the thread
            guard* const    array_;            ///< initial HP array
            size_t const    initial_capacity_; ///< Capacity of \p array_
#       ifdef CDS_ENABLE_HPSTAT
        public:
            size_t          alloc_guard_count_;
            size_t          free_guard_count_;
            size_t          extend_call_count_;
#       endif
        };
        //@endcond

        //@cond
        struct retired_block: public cds::intrusive::FreeListImpl::node
        {
            retired_block*  next_;  ///< Next block in thread-private retired array

            static size_t const c_capacity = 256;

            retired_block()
                : next_( nullptr )
            {}

            retired_ptr* first() const
            {
                return reinterpret_cast<retired_ptr*>( const_cast<retired_block*>( this ) + 1 );
            }

            retired_ptr* last() const
            {
                return first() + c_capacity;
            }
        };
        //@endcond

        //@cond
        class retired_allocator
        {
            friend class smr;
        public:
            static retired_allocator& instance();

            CDS_EXPORT_API retired_block* alloc();
            void free( retired_block* block )
            {
                block->next_ = nullptr;
                free_list_.put( block );
            }

        private:
            retired_allocator()
#ifdef CDS_ENABLE_HPSTAT
                : block_allocated_(0)
#endif
            {}
            CDS_EXPORT_API ~retired_allocator();

        private:
            cds::intrusive::FreeListImpl    free_list_; ///< list of free \p guard_block
#ifdef CDS_ENABLE_HPSTAT
        public:
            atomics::atomic<size_t> block_allocated_; ///< Count of allocated blocks
#endif
        };
        //@endcond

        //@cond
        /// Per-thread retired array
        class retired_array
        {
            friend class smr;
        public:
            retired_array() CDS_NOEXCEPT
                : current_block_( nullptr )
                , current_cell_( nullptr )
                , list_head_( nullptr )
                , list_tail_( nullptr )
                , block_count_(0)
#       ifdef CDS_ENABLE_HPSTAT
                , retire_call_count_( 0 )
                , extend_call_count_( 0 )
#       endif
            {}

            retired_array( retired_array const& ) = delete;
            retired_array( retired_array&& ) = delete;

            ~retired_array()
            {
                assert( empty());
                fini();
            }

            bool push( retired_ptr const& p ) CDS_NOEXCEPT
            {
                assert( current_block_ != nullptr );
                assert( current_block_->first() <= current_cell_ );
                assert( current_cell_ < current_block_->last());
                //assert( &p != current_cell_ );

                *current_cell_ = p;
                CDS_HPSTAT( ++retire_call_count_ );

                if ( ++current_cell_ == current_block_->last()) {
                    // goto next block if exists
                    if ( current_block_->next_ ) {
                        current_block_ = current_block_->next_;
                        current_cell_ = current_block_->first();
                        return true;
                    }

                    // no free block
                    // smr::scan() extend retired_array if needed
                    return false;
                }

                return true;
            }

            bool repush( retired_ptr* p ) CDS_NOEXCEPT
            {
                bool ret = push( *p );
                CDS_HPSTAT( --retire_call_count_ );
                assert( ret );
                return ret;
            }

        private: // called by smr
            void init()
            {
                if ( list_head_ == nullptr ) {
                    retired_block* block = retired_allocator::instance().alloc();
                    assert( block->next_ == nullptr );

                    current_block_ =
                        list_head_ =
                        list_tail_ = block;
                    current_cell_ = block->first();

                    block_count_ = 1;
                }
            }

            void fini()
            {
                retired_allocator& alloc = retired_allocator::instance();
                for ( retired_block* p = list_head_; p; ) {
                    retired_block* next = p->next_;
                    alloc.free( p );
                    p = next;
                }

                current_block_ =
                    list_head_ =
                    list_tail_ = nullptr;
                current_cell_ = nullptr;

                block_count_ = 0;
            }

            void extend()
            {
                assert( list_head_ != nullptr );
                assert( current_block_ == list_tail_ );
                assert( current_cell_ == current_block_->last());

                retired_block* block = retired_allocator::instance().alloc();
                assert( block->next_ == nullptr );

                current_block_ = list_tail_ = list_tail_->next_ = block;
                current_cell_ = block->first();
                ++block_count_;
                CDS_HPSTAT( ++extend_call_count_ );
            }

            bool empty() const
            {
                return current_block_ == nullptr
                    || ( current_block_ == list_head_ && current_cell_ == current_block_->first());
            }

        private:
            retired_block*          current_block_;
            retired_ptr*            current_cell_;  // in current_block_

            retired_block*          list_head_;
            retired_block*          list_tail_;
            size_t                  block_count_;
#       ifdef CDS_ENABLE_HPSTAT
        public:
            size_t  retire_call_count_;
            size_t  extend_call_count_;
#       endif
        };
        //@endcond

        /// Internal statistics
        struct stat {
            size_t  guard_allocated;    ///< Count of allocated HP guards
            size_t  guard_freed;        ///< Count of freed HP guards
            size_t  retired_count;      ///< Count of retired pointers
            size_t  free_count;         ///< Count of free pointers
            size_t  scan_count;         ///< Count of \p scan() call
            size_t  help_scan_count;    ///< Count of \p help_scan() call

            size_t  thread_rec_count;   ///< Count of thread records

            size_t  hp_block_count;         ///< Count of extended HP blocks allocated
            size_t  retired_block_count;    ///< Count of retired blocks allocated
            size_t  hp_extend_count;        ///< Count of hp array \p extend() call
            size_t  retired_extend_count;   ///< Count of retired array \p extend() call

                                        /// Default ctor
            stat()
            {
                clear();
            }

            /// Clears all counters
            void clear()
            {
                guard_allocated =
                    guard_freed =
                    retired_count =
                    free_count =
                    scan_count =
                    help_scan_count =
                    thread_rec_count =
                    hp_block_count =
                    retired_block_count =
                    hp_extend_count =
                    retired_extend_count = 0;
            }
        };

        //@cond
        /// Per-thread data
        struct thread_data {
            thread_hp_storage   hazards_;   ///< Hazard pointers private to the thread
            retired_array       retired_;   ///< Retired data private to the thread

            char pad1_[cds::c_nCacheLineSize];
            atomics::atomic<unsigned int> sync_; ///< dummy var to introduce synchronizes-with relationship between threads
            char pad2_[cds::c_nCacheLineSize];

#       ifdef CDS_ENABLE_HPSTAT
            size_t              free_call_count_;
            size_t              scan_call_count_;
            size_t              help_scan_call_count_;
#       endif

            // CppCheck warn: pad1_ and pad2_ is uninitialized in ctor
            // cppcheck-suppress uninitMemberVar
            thread_data( guard* guards, size_t guard_count )
                : hazards_( guards, guard_count )
                , sync_( 0 )
#       ifdef CDS_ENABLE_HPSTAT
                , free_call_count_(0)
                , scan_call_count_(0)
                , help_scan_call_count_(0)
#       endif
            {}

            thread_data() = delete;
            thread_data( thread_data const& ) = delete;
            thread_data( thread_data&& ) = delete;

            void sync()
            {
                sync_.fetch_add( 1, atomics::memory_order_acq_rel );
            }
        };
        //@endcond

        //@cond
        // Dynamic (adaptive) Hazard Pointer SMR (Safe Memory Reclamation)
        class smr
        {
            struct thread_record;

        public:
            /// Returns the instance of Hazard Pointer \ref smr
            static smr& instance()
            {
#       ifdef CDS_DISABLE_SMR_EXCEPTION
                assert( instance_ != nullptr );
#       else
                if ( !instance_ )
                    CDS_THROW_EXCEPTION( not_initialized());
#       endif
                return *instance_;
            }

            /// Creates Dynamic Hazard Pointer SMR singleton
            /**
                Dynamic Hazard Pointer SMR is a singleton. If DHP instance is not initialized then the function creates the instance.
                Otherwise it does nothing.

                The Michael's HP reclamation schema depends of three parameters:
                - \p nHazardPtrCount - HP pointer count per thread. Usually it is small number (2-4) depending from
                the data structure algorithms. By default, if \p nHazardPtrCount = 0,
                the function uses maximum of HP count for CDS library
                - \p nMaxThreadCount - max count of thread with using HP GC in your application. Default is 100.
                - \p nMaxRetiredPtrCount - capacity of array of retired pointers for each thread. Must be greater than
                <tt> nHazardPtrCount * nMaxThreadCount </tt>
                Default is <tt>2 * nHazardPtrCount * nMaxThreadCount</tt>
            */
            static CDS_EXPORT_API void construct(
                size_t nInitialHazardPtrCount = 16  ///< Initial number of hazard pointer per thread
            );

            // for back-copatibility
            static void Construct(
                size_t nInitialHazardPtrCount = 16  ///< Initial number of hazard pointer per thread
            )
            {
                construct( nInitialHazardPtrCount );
            }

            /// Destroys global instance of \ref smr
            /**
                The parameter \p bDetachAll should be used carefully: if its value is \p true,
                then the object destroyed automatically detaches all attached threads. This feature
                can be useful when you have no control over the thread termination, for example,
                when \p libcds is injected into existing external thread.
            */
            static CDS_EXPORT_API void destruct(
                bool bDetachAll = false     ///< Detach all threads
            );

            // for back-compatibility
            static void Destruct(
                bool bDetachAll = false     ///< Detach all threads
            )
            {
                destruct( bDetachAll );
            }

            /// Checks if global SMR object is constructed and may be used
            static bool isUsed() CDS_NOEXCEPT
            {
                return instance_ != nullptr;
            }

            /// Set memory management functions
            /**
                @note This function may be called <b>BEFORE</b> creating an instance
                of Dynamic Hazard Pointer SMR

                SMR object allocates some memory for thread-specific data and for
                creating SMR object.
                By default, a standard \p new and \p delete operators are used for this.
            */
            static CDS_EXPORT_API void set_memory_allocator(
                void* ( *alloc_func )( size_t size ),
                void( *free_func )( void * p )
            );

            /// Returns thread-local data for the current thread
            static CDS_EXPORT_API thread_data* tls();

            static CDS_EXPORT_API void attach_thread();
            static CDS_EXPORT_API void detach_thread();

            /// Get internal statistics
            CDS_EXPORT_API void statistics( stat& st );

        public: // for internal use only
            /// The main garbage collecting function
            CDS_EXPORT_API void scan( thread_data* pRec );

            /// Helper scan routine
            /**
                The function guarantees that every node that is eligible for reuse is eventually freed, barring
                thread failures. To do so, after executing \p scan(), a thread executes a \p %help_scan(),
                where it checks every HP record. If an HP record is inactive, the thread moves all "lost" reclaimed pointers
                to thread's list of reclaimed pointers.

                The function is called internally by \p scan().
            */
            CDS_EXPORT_API void help_scan( thread_data* pThis );

            hp_allocator& get_hp_allocator()
            {
                return hp_allocator_;
            }

            retired_allocator& get_retired_allocator()
            {
                return retired_allocator_;
            }

        private:
            CDS_EXPORT_API explicit smr(
                size_t nInitialHazardPtrCount
            );

            CDS_EXPORT_API ~smr();

            CDS_EXPORT_API void detach_all_thread();

        private:
            CDS_EXPORT_API thread_record* create_thread_data();
            static CDS_EXPORT_API void destroy_thread_data( thread_record* pRec );

            /// Allocates Hazard Pointer SMR thread private data
            CDS_EXPORT_API thread_record* alloc_thread_data();

            /// Free HP SMR thread-private data
            CDS_EXPORT_API void free_thread_data( thread_record* pRec );

        private:
            static CDS_EXPORT_API smr* instance_;

            atomics::atomic< thread_record*>    thread_list_;   ///< Head of thread list
            size_t const        initial_hazard_count_;  ///< initial number of hazard pointers per thread
            hp_allocator        hp_allocator_;
            retired_allocator   retired_allocator_;

            // temporaries
            std::atomic<size_t> last_plist_size_;   ///< HP array size in last scan() call
        };
        //@endcond

        //@cond
        // for backward compatibility
        typedef smr GarbageCollector;


        // inlines
        inline hp_allocator& hp_allocator::instance()
        {
            return smr::instance().get_hp_allocator();
        }

        inline retired_allocator& retired_allocator::instance()
        {
            return smr::instance().get_retired_allocator();
        }
        //@endcond

    } // namespace dhp


    /// Dynamic (adaptie) Hazard Pointer SMR
    /**  @ingroup cds_garbage_collector

        Implementation of Dynamic (adaptive) Hazard Pointer SMR

        Sources:
            - [2002] Maged M.Michael "Safe memory reclamation for dynamic lock-freeobjects using atomic reads and writes"
            - [2003] Maged M.Michael "Hazard Pointers: Safe memory reclamation for lock-free objects"
            - [2004] Andrei Alexandrescy, Maged Michael "Lock-free Data Structures with Hazard Pointers"

        %DHP is an adaptive variant of classic \p cds::gc::HP, see @ref cds_garbage_collectors_comparison "Compare HP implementation"

        @note: Internally, %DHP depends on free-list implementation. There are
        DCAS-based free-list \p cds::intrusive::TaggedFreeList and more complicated CAS-based free-list
        \p cds::intrusive::FreeList. For x86 architecture and GCC/clang, libcds selects appropriate free-list 
        based on \p -mcx16 compiler flag. You may manually disable DCAS support specifying
        \p -DCDS_DISABLE_128BIT_ATOMIC for 64bit build or \p -DCDS_DISABLE_64BIT_ATOMIC for 32bit build
        in compiler command line. All your projects and libcds MUST be compiled with the same flags -
        either with DCAS support or without it.
        For MS VC++ compiler DCAS is not supported.

        See \ref cds_how_to_use "How to use" section for details how to apply SMR.
    */
    class DHP
    {
    public:
        /// Native guarded pointer type
        typedef void* guarded_pointer;

        /// Atomic reference
        template <typename T> using atomic_ref = atomics::atomic<T *>;

        /// Atomic type
        /**
            @headerfile cds/gc/dhp.h
        */
        template <typename T> using atomic_type = atomics::atomic<T>;

        /// Atomic marked pointer
        template <typename MarkedPtr> using atomic_marked_ptr = atomics::atomic<MarkedPtr>;

        /// Internal statistics
        typedef dhp::stat stat;

        /// Dynamic Hazard Pointer guard
        /**
            A guard is a hazard pointer.
            Additionally, the \p %Guard class manages allocation and deallocation of the hazard pointer

            \p %Guard object is movable but not copyable.

            The guard object can be in two states:
            - unlinked - the guard is not linked with any internal hazard pointer.
              In this state no operation except \p link() and move assignment is supported.
            - linked (default) - the guard allocates an internal hazard pointer and fully operable.

            Due to performance reason the implementation does not check state of the guard in runtime.

            @warning Move assignment can transfer the guard in unlinked state, use with care.
        */
        class Guard
        {
        public:
            /// Default ctor allocates a guard (hazard pointer) from thread-private storage
            Guard() CDS_NOEXCEPT
                : guard_( dhp::smr::tls()->hazards_.alloc())
            {}

            /// Initilalizes an unlinked guard i.e. the guard contains no hazard pointer. Used for move semantics support
            explicit Guard( std::nullptr_t ) CDS_NOEXCEPT
                : guard_( nullptr )
            {}

            /// Move ctor - \p src guard becomes unlinked (transfer internal guard ownership)
            Guard( Guard&& src ) CDS_NOEXCEPT
                : guard_( src.guard_ )
            {
                src.guard_ = nullptr;
            }

            /// Move assignment: the internal guards are swapped between \p src and \p this
            /**
                @warning \p src will become in unlinked state if \p this was unlinked on entry.
            */
            Guard& operator=( Guard&& src ) CDS_NOEXCEPT
            {
                std::swap( guard_, src.guard_ );
                return *this;
            }

            /// Copy ctor is prohibited - the guard is not copyable
            Guard( Guard const& ) = delete;

            /// Copy assignment is prohibited
            Guard& operator=( Guard const& ) = delete;

            /// Frees the internal hazard pointer if the guard is in linked state
            ~Guard()
            {
                unlink();
            }

            /// Checks if the guard object linked with any internal hazard pointer
            bool is_linked() const
            {
                return guard_ != nullptr;
            }

            /// Links the guard with internal hazard pointer if the guard is in unlinked state
            void link()
            {
                if ( !guard_ )
                    guard_ = dhp::smr::tls()->hazards_.alloc();
            }

            /// Unlinks the guard from internal hazard pointer; the guard becomes in unlinked state
            void unlink()
            {
                if ( guard_ ) {
                    dhp::smr::tls()->hazards_.free( guard_ );
                    guard_ = nullptr;
                }
            }

            /// Protects a pointer of type <tt> atomic<T*> </tt>
            /**
                Return the value of \p toGuard

                The function tries to load \p toGuard and to store it
                to the HP slot repeatedly until the guard's value equals \p toGuard
            */
            template <typename T>
            T protect( atomics::atomic<T> const& toGuard )
            {
                assert( guard_ != nullptr );

                T pCur = toGuard.load(atomics::memory_order_acquire);
                T pRet;
                do {
                    pRet = assign( pCur );
                    pCur = toGuard.load(atomics::memory_order_acquire);
                } while ( pRet != pCur );
                return pCur;
            }

            /// Protects a converted pointer of type <tt> atomic<T*> </tt>
            /**
                Return the value of \p toGuard

                The function tries to load \p toGuard and to store result of \p f functor
                to the HP slot repeatedly until the guard's value equals \p toGuard.

                The function is useful for intrusive containers when \p toGuard is a node pointer
                that should be converted to a pointer to the value type before guarding.
                The parameter \p f of type Func is a functor that makes this conversion:
                \code
                    struct functor {
                        value_type * operator()( T * p );
                    };
                \endcode
                Really, the result of <tt> f( toGuard.load()) </tt> is assigned to the hazard pointer.
            */
            template <typename T, class Func>
            T protect( atomics::atomic<T> const& toGuard, Func f )
            {
                assert( guard_ != nullptr );

                T pCur = toGuard.load(atomics::memory_order_acquire);
                T pRet;
                do {
                    pRet = pCur;
                    assign( f( pCur ));
                    pCur = toGuard.load(atomics::memory_order_acquire);
                } while ( pRet != pCur );
                return pCur;
            }

            /// Store \p p to the guard
            /**
                The function is just an assignment, no loop is performed.
                Can be used for a pointer that cannot be changed concurrently
                or for already guarded pointer.
            */
            template <typename T>
            T* assign( T* p )
            {
                assert( guard_ != nullptr );

                guard_->set( p );
                dhp::smr::tls()->sync();
                return p;
            }

            //@cond
            std::nullptr_t assign( std::nullptr_t )
            {
                assert( guard_ != nullptr );

                clear();
                return nullptr;
            }
            //@endcond

            /// Store marked pointer \p p to the guard
            /**
                The function is just an assignment of <tt>p.ptr()</tt>, no loop is performed.
                Can be used for a marked pointer that cannot be changed concurrently
                or for already guarded pointer.
            */
            template <typename T, int BITMASK>
            T* assign( cds::details::marked_ptr<T, BITMASK> p )
            {
                return assign( p.ptr());
            }

            /// Copy from \p src guard to \p this guard
            void copy( Guard const& src )
            {
                assign( src.get_native());
            }

            /// Clears value of the guard
            void clear()
            {
                assert( guard_ != nullptr );

                guard_->clear();
            }

            /// Gets the value currently protected (relaxed read)
            template <typename T>
            T * get() const
            {
                assert( guard_ != nullptr );
                return guard_->get_as<T>();
            }

            /// Gets native guarded pointer stored
            void* get_native() const
            {
                assert( guard_ != nullptr );
                return guard_->get();
            }

            //@cond
            dhp::guard* release()
            {
                dhp::guard* g = guard_;
                guard_ = nullptr;
                return g;
            }

            dhp::guard*& guard_ref()
            {
                return guard_;
            }
            //@endcond

        private:
            //@cond
            dhp::guard* guard_;
            //@endcond
        };

        /// Array of Dynamic Hazard Pointer guards
        /**
            The class is intended for allocating an array of hazard pointer guards.
            Template parameter \p Count defines the size of the array.

            A \p %GuardArray object is not copy- and move-constructible
            and not copy- and move-assignable.
        */
        template <size_t Count>
        class GuardArray
        {
        public:
            /// Rebind array for other size \p OtherCount
            template <size_t OtherCount>
            struct rebind {
                typedef GuardArray<OtherCount>  other   ;   ///< rebinding result
            };

            /// Array capacity
            static CDS_CONSTEXPR const size_t c_nCapacity = Count;

        public:
            /// Default ctor allocates \p Count hazard pointers
            GuardArray()
            {
                dhp::smr::tls()->hazards_.alloc( guards_ );
            }

            /// Move ctor is prohibited
            GuardArray( GuardArray&& ) = delete;

            /// Move assignment is prohibited
            GuardArray& operator=( GuardArray&& ) = delete;

            /// Copy ctor is prohibited
            GuardArray( GuardArray const& ) = delete;

            /// Copy assignment is prohibited
            GuardArray& operator=( GuardArray const& ) = delete;

            /// Frees allocated hazard pointers
            ~GuardArray()
            {
                dhp::smr::tls()->hazards_.free( guards_ );
            }

            /// Protects a pointer of type \p atomic<T*>
            /**
                Return the value of \p toGuard

                The function tries to load \p toGuard and to store it
                to the slot \p nIndex repeatedly until the guard's value equals \p toGuard
            */
            template <typename T>
            T protect( size_t nIndex, atomics::atomic<T> const& toGuard )
            {
                assert( nIndex < capacity());

                T pRet;
                do {
                    pRet = assign( nIndex, toGuard.load(atomics::memory_order_acquire));
                } while ( pRet != toGuard.load(atomics::memory_order_relaxed));

                return pRet;
            }

            /// Protects a pointer of type \p atomic<T*>
            /**
                Return the value of \p toGuard

                The function tries to load \p toGuard and to store it
                to the slot \p nIndex repeatedly until the guard's value equals \p toGuard

                The function is useful for intrusive containers when \p toGuard is a node pointer
                that should be converted to a pointer to the value type before guarding.
                The parameter \p f of type Func is a functor to make that conversion:
                \code
                    struct functor {
                        value_type * operator()( T * p );
                    };
                \endcode
                Actually, the result of <tt> f( toGuard.load()) </tt> is assigned to the hazard pointer.
            */
            template <typename T, class Func>
            T protect( size_t nIndex, atomics::atomic<T> const& toGuard, Func f )
            {
                assert( nIndex < capacity());

                T pRet;
                do {
                    assign( nIndex, f( pRet = toGuard.load(atomics::memory_order_acquire)));
                } while ( pRet != toGuard.load(atomics::memory_order_relaxed));

                return pRet;
            }

            /// Store \p p to the slot \p nIndex
            /**
                The function is just an assignment, no loop is performed.
            */
            template <typename T>
            T * assign( size_t nIndex, T * p )
            {
                assert( nIndex < capacity());

                guards_.set( nIndex, p );
                dhp::smr::tls()->sync();
                return p;
            }

            /// Store marked pointer \p p to the guard
            /**
                The function is just an assignment of <tt>p.ptr()</tt>, no loop is performed.
                Can be used for a marked pointer that cannot be changed concurrently
                or for already guarded pointer.
            */
            template <typename T, int Bitmask>
            T * assign( size_t nIndex, cds::details::marked_ptr<T, Bitmask> p )
            {
                return assign( nIndex, p.ptr());
            }

            /// Copy guarded value from \p src guard to slot at index \p nIndex
            void copy( size_t nIndex, Guard const& src )
            {
                assign( nIndex, src.get_native());
            }

            /// Copy guarded value from slot \p nSrcIndex to slot at index \p nDestIndex
            void copy( size_t nDestIndex, size_t nSrcIndex )
            {
                assign( nDestIndex, get_native( nSrcIndex ));
            }

            /// Clear value of the slot \p nIndex
            void clear( size_t nIndex )
            {
                guards_.clear( nIndex );
            }

            /// Get current value of slot \p nIndex
            template <typename T>
            T * get( size_t nIndex ) const
            {
                assert( nIndex < capacity());
                return guards_[nIndex]->template get_as<T>();
            }

            /// Get native guarded pointer stored
            guarded_pointer get_native( size_t nIndex ) const
            {
                assert( nIndex < capacity());
                return guards_[nIndex]->get();
            }

            //@cond
            dhp::guard* release( size_t nIndex ) CDS_NOEXCEPT
            {
                return guards_.release( nIndex );
            }
            //@endcond

            /// Capacity of the guard array
            static CDS_CONSTEXPR size_t capacity()
            {
                return Count;
            }

        private:
            //@cond
            dhp::guard_array<c_nCapacity> guards_;
            //@endcond
        };

        /// Guarded pointer
        /**
            A guarded pointer is a pair of a pointer and GC's guard.
            Usually, it is used for returning a pointer to the item from an lock-free container.
            The guard prevents the pointer to be early disposed (freed) by GC.
            After destructing \p %guarded_ptr object the pointer can be disposed (freed) automatically at any time.

            Template arguments:
            - \p GuardedType - a type which the guard stores
            - \p ValueType - a value type
            - \p Cast - a functor for converting <tt>GuardedType*</tt> to <tt>ValueType*</tt>. Default is \p void (no casting).

            For intrusive containers, \p GuardedType is the same as \p ValueType and no casting is needed.
            In such case the \p %guarded_ptr is:
            @code
            typedef cds::gc::DHP::guarded_ptr< foo > intrusive_guarded_ptr;
            @endcode

            For standard (non-intrusive) containers \p GuardedType is not the same as \p ValueType and casting is needed.
            For example:
            @code
            struct foo {
                int const   key;
                std::string value;
            };

            struct value_accessor {
                std::string* operator()( foo* pFoo ) const
                {
                    return &(pFoo->value);
                }
            };

            // Guarded ptr
            typedef cds::gc::DHP::guarded_ptr< Foo, std::string, value_accessor > nonintrusive_guarded_ptr;
            @endcode

            You don't need use this class directly.
            All set/map container classes from \p libcds declare the typedef for \p %guarded_ptr with appropriate casting functor.
        */
        template <typename GuardedType, typename ValueType=GuardedType, typename Cast=void >
        class guarded_ptr
        {
            //@cond
            struct trivial_cast {
                ValueType * operator()( GuardedType * p ) const
                {
                    return p;
                }
            };

            template <typename GT, typename VT, typename C> friend class guarded_ptr;
            //@endcond

        public:
            typedef GuardedType guarded_type; ///< Guarded type
            typedef ValueType   value_type;   ///< Value type

            /// Functor for casting \p guarded_type to \p value_type
            typedef typename std::conditional< std::is_same<Cast, void>::value, trivial_cast, Cast >::type value_cast;

        public:
            /// Creates empty guarded pointer
            guarded_ptr() CDS_NOEXCEPT
                : guard_( nullptr )
            {}

            //@cond
            explicit guarded_ptr( dhp::guard* g ) CDS_NOEXCEPT
                : guard_( g )
            {}

            /// Initializes guarded pointer with \p p
            explicit guarded_ptr( guarded_type * p ) CDS_NOEXCEPT
                : guard_( nullptr )
            {
                reset( p );
            }
            explicit guarded_ptr( std::nullptr_t ) CDS_NOEXCEPT
                : guard_( nullptr )
            {}
            //@endcond

            /// Move ctor
            guarded_ptr( guarded_ptr&& gp ) CDS_NOEXCEPT
                : guard_( gp.guard_ )
            {
                gp.guard_ = nullptr;
            }

            /// Move ctor
            template <typename GT, typename VT, typename C>
            guarded_ptr( guarded_ptr<GT, VT, C>&& gp ) CDS_NOEXCEPT
                : guard_( gp.guard_ )
            {
                gp.guard_ = nullptr;
            }

            /// Ctor from \p Guard
            explicit guarded_ptr( Guard&& g ) CDS_NOEXCEPT
                : guard_( g.release())
            {}

            /// The guarded pointer is not copy-constructible
            guarded_ptr( guarded_ptr const& gp ) = delete;

            /// Clears the guarded pointer
            /**
                \ref release is called if guarded pointer is not \ref empty
            */
            ~guarded_ptr() CDS_NOEXCEPT
            {
                release();
            }

            /// Move-assignment operator
            guarded_ptr& operator=( guarded_ptr&& gp ) CDS_NOEXCEPT
            {
                std::swap( guard_, gp.guard_ );
                return *this;
            }

            /// Move-assignment from \p Guard
            guarded_ptr& operator=( Guard&& g ) CDS_NOEXCEPT
            {
                std::swap( guard_, g.guard_ref());
                return *this;
            }

            /// The guarded pointer is not copy-assignable
            guarded_ptr& operator=(guarded_ptr const& gp) = delete;

            /// Returns a pointer to guarded value
            value_type * operator ->() const CDS_NOEXCEPT
            {
                assert( !empty());
                return value_cast()( guard_->get_as<guarded_type>());
            }

            /// Returns a reference to guarded value
            value_type& operator *() CDS_NOEXCEPT
            {
                assert( !empty());
                return *value_cast()( guard_->get_as<guarded_type>());
            }

            /// Returns const reference to guarded value
            value_type const& operator *() const CDS_NOEXCEPT
            {
                assert( !empty());
                return *value_cast()(reinterpret_cast<guarded_type *>(guard_->get()));
            }

            /// Checks if the guarded pointer is \p nullptr
            bool empty() const CDS_NOEXCEPT
            {
                return guard_ == nullptr || guard_->get( atomics::memory_order_relaxed ) == nullptr;
            }

            /// \p bool operator returns <tt>!empty()</tt>
            explicit operator bool() const CDS_NOEXCEPT
            {
                return !empty();
            }

            /// Clears guarded pointer
            /**
                If the guarded pointer has been released, the pointer can be disposed (freed) at any time.
                Dereferncing the guarded pointer after \p release() is dangerous.
            */
            void release() CDS_NOEXCEPT
            {
                free_guard();
            }

            //@cond
            // For internal use only!!!
            void reset(guarded_type * p) CDS_NOEXCEPT
            {
                alloc_guard();
                assert( guard_ );
                guard_->set( p );
            }

            //@endcond

        private:
            //@cond
            void alloc_guard()
            {
                if ( !guard_ )
                    guard_ = dhp::smr::tls()->hazards_.alloc();
            }

            void free_guard()
            {
                if ( guard_ ) {
                    dhp::smr::tls()->hazards_.free( guard_ );
                    guard_ = nullptr;
                }
            }
            //@endcond

        private:
            //@cond
            dhp::guard* guard_;
            //@endcond
        };

    public:
        /// Initializes %DHP memory manager singleton
        /**
            Constructor creates and initializes %DHP global object.
            %DHP object should be created before using CDS data structure based on \p %cds::gc::DHP. Usually,
            it is created in the beginning of \p main() function.
            After creating of global object you may use CDS data structures based on \p %cds::gc::DHP.

            \p nInitialThreadGuardCount - initial count of guard allocated for each thread.
                When a thread is initialized the GC allocates local guard pool for the thread from a common guard pool.
                By perforce the local thread's guard pool is grown automatically from common pool.
                When the thread terminated its guard pool is backed to common GC's pool.
        */
        explicit DHP(
            size_t nInitialHazardPtrCount = 16  ///< Initial number of hazard pointer per thread
        )
        {
            dhp::smr::construct( nInitialHazardPtrCount );
        }

        /// Destroys %DHP memory manager
        /**
            The destructor destroys %DHP global object. After calling of this function you may \b NOT
            use CDS data structures based on \p %cds::gc::DHP.
            Usually, %DHP object is destroyed at the end of your \p main().
        */
        ~DHP()
        {
            dhp::GarbageCollector::destruct( true );
        }

        /// Checks if count of hazard pointer is no less than \p nCountNeeded
        /**
            The function always returns \p true since the guard count is unlimited for
            \p %gc::DHP garbage collector.
        */
        static CDS_CONSTEXPR bool check_available_guards(
#ifdef CDS_DOXYGEN_INVOKED
            size_t nCountNeeded,
#else
            size_t
#endif
        )
        {
            return true;
        }

        /// Set memory management functions
        /**
            @note This function may be called <b>BEFORE</b> creating an instance
            of Dynamic Hazard Pointer SMR

            SMR object allocates some memory for thread-specific data and for creating SMR object.
            By default, a standard \p new and \p delete operators are used for this.
        */
        static void set_memory_allocator(
            void* ( *alloc_func )( size_t size ),   ///< \p malloc() function
            void( *free_func )( void * p )          ///< \p free() function
        )
        {
            dhp::smr::set_memory_allocator( alloc_func, free_func );
        }

        /// Retire pointer \p p with function \p pFunc
        /**
            The function places pointer \p p to array of pointers ready for removing.
            (so called retired pointer array). The pointer can be safely removed when no hazard pointer points to it.
            \p func is a disposer: when \p p can be safely removed, \p func is called.
        */
        template <typename T>
        static void retire( T * p, void (* func)(void *))
        {
            dhp::thread_data* rec = dhp::smr::tls();
            if ( !rec->retired_.push( dhp::retired_ptr( p, func )) )
                dhp::smr::instance().scan( rec );
        }

        /// Retire pointer \p p with functor of type \p Disposer
        /**
            The function places pointer \p p to array of pointers ready for removing.
            (so called retired pointer array). The pointer can be safely removed when no hazard pointer points to it.

            Deleting the pointer is an invocation of some object of type \p Disposer; the interface of \p Disposer is:
            \code
            template <typename T>
            struct disposer {
                void operator()( T * p )    ;   // disposing operator
            };
            \endcode
            Since the functor call can happen at any time after \p retire() call, additional restrictions are imposed to \p Disposer type:
            - it should be stateless functor
            - it should be default-constructible
            - the result of functor call with argument \p p should not depend on where the functor will be called.

            \par Examples:
            Operator \p delete functor:
            \code
            template <typename T>
            struct disposer {
                void operator ()( T * p ) {
                    delete p;
                }
            };

            // How to call HP::retire method
            int * p = new int;

            // ... use p in lock-free manner

            cds::gc::DHP::retire<disposer>( p ) ;   // place p to retired pointer array of DHP SMR
            \endcode

            Functor based on \p std::allocator :
            \code
            template <typename Alloc = std::allocator<int> >
            struct disposer {
                template <typename T>
                void operator()( T * p ) {
                    typedef typename Alloc::templare rebind<T>::other alloc_t;
                    alloc_t a;
                    a.destroy( p );
                    a.deallocate( p, 1 );
                }
            };
            \endcode
        */
        template <class Disposer, typename T>
        static void retire( T* p )
        {
            if ( !dhp::smr::tls()->retired_.push( dhp::retired_ptr( p, cds::details::static_functor<Disposer, T>::call )))
                scan();
        }

        /// Checks if Dynamic Hazard Pointer GC is constructed and may be used
        static bool isUsed()
        {
            return dhp::smr::isUsed();
        }

        /// Forced GC cycle call for current thread
        /**
            Usually, this function should not be called directly.
        */
        static void scan()
        {
            dhp::smr::instance().scan( dhp::smr::tls());
        }

        /// Synonym for \p scan()
        static void force_dispose()
        {
            scan();
        }

        /// Returns internal statistics
        /**
            The function clears \p st before gathering statistics.

            @note Internal statistics is available only if you compile
            \p libcds and your program with \p -DCDS_ENABLE_HPSTAT.
        */
        static void statistics( stat& st )
        {
            dhp::smr::instance().statistics( st );
        }

        /// Returns post-mortem statistics
        /**
            Post-mortem statistics is gathered in the \p %DHP object destructor
            and can be accessible after destructing the global \p %DHP object.

            @note Internal statistics is available only if you compile
            \p libcds and your program with \p -DCDS_ENABLE_HPSTAT.

            Usage:
            \code
            int main()
            {
                cds::Initialize();
                {
                    // Initialize DHP SMR
                    cds::gc::DHP dhp;

                    // deal with DHP-based data structured
                    // ...
                }

                // DHP object destroyed
                // Get total post-mortem statistics
                cds::gc::DHP::stat const& st = cds::gc::DHP::postmortem_statistics();

                printf( "DHP statistics:\n"
                    "  thread count           = %llu\n"
                    "  guard allocated        = %llu\n"
                    "  guard freed            = %llu\n"
                    "  retired data count     = %llu\n"
                    "  free data count        = %llu\n"
                    "  scan() call count      = %llu\n"
                    "  help_scan() call count = %llu\n",
                    st.thread_rec_count,
                    st.guard_allocated, st.guard_freed,
                    st.retired_count, st.free_count,
                    st.scan_count, st.help_scan_count
                );

                cds::Terminate();
            }
            \endcode
        */
        CDS_EXPORT_API static stat const& postmortem_statistics();
    };

}} // namespace cds::gc

#endif // #ifndef CDSLIB_GC_DHP_SMR_H