/*
    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_IMPL_ELLEN_BINTREE_H
#define CDSLIB_INTRUSIVE_IMPL_ELLEN_BINTREE_H

#include <memory>
#include <cds/intrusive/details/ellen_bintree_base.h>
#include <cds/opt/compare.h>
#include <cds/details/binary_functor_wrapper.h>
#include <cds/urcu/details/check_deadlock.h>

namespace cds { namespace intrusive {

    /// Ellen's et al binary search tree
    /** @ingroup cds_intrusive_map
        @ingroup cds_intrusive_tree
        @anchor cds_intrusive_EllenBinTree

        Source:
            - [2010] F.Ellen, P.Fatourou, E.Ruppert, F.van Breugel "Non-blocking Binary Search Tree"

        %EllenBinTree is an <i>unbalanced</i> leaf-oriented binary search tree that implements the <i>set</i>
        abstract data type. Nodes maintains child pointers but not parent pointers.
        Every internal node has exactly two children, and all data of type \p T currently in
        the tree are stored in the leaves. Internal nodes of the tree are used to direct \p find()
        operation along the path to the correct leaf. The keys (of \p Key type) stored in internal nodes
        may or may not be in the set. \p Key type is a subset of \p T type.
        There should be exactly defined a key extracting functor for converting object of type \p T to
        object of type \p Key.

        Due to \p extract_min() and \p extract_max() member functions the \p %EllenBinTree can act as
        a <i>priority queue</i>. In this case you should provide unique compound key, for example,
        the priority value plus some uniformly distributed random value.

        @note In the current implementation we do not use helping technique described in the original paper.
        In Hazard Pointer schema the helping is too complicated and does not give any observable benefits.
        Instead of helping, when a thread encounters a concurrent operation it just spins waiting for
        the operation done. Such solution allows greatly simplify implementation of the tree.

        @attention Recall the tree is <b>unbalanced</b>. The complexity of operations is <tt>O(log N)</tt>
        for uniformly distributed random keys, but in the worst case the complexity is <tt>O(N)</tt>.

        @note Do not include <tt><cds/intrusive/impl/ellen_bintree.h></tt> header file explicitly.
        There are header file for each GC type:
        - <tt><cds/intrusive/ellen_bintree_hp.h></tt> - for Hazard Pointer GC \p cds::gc::HP
        - <tt><cds/intrusive/ellen_bintree_dhp.h></tt> - for Dynamic Hazard Pointer GC \p cds::gc::DHP
        - <tt><cds/intrusive/ellen_bintree_rcu.h></tt> - for RCU (see \ref cds_intrusive_EllenBinTree_rcu "RCU-based EllenBinTree")

        <b>Template arguments</b> :
        - \p GC - garbage collector, possible types are cds::gc::HP, cds::gc::DHP.
        - \p Key - key type, a subset of \p T
        - \p T - type to be stored in tree's leaf nodes. The type must be based on \p ellen_bintree::node
            (for \p ellen_bintree::base_hook) or it must have a member of type \p ellen_bintree::node
            (for \p ellen_bintree::member_hook).
        - \p Traits - tree traits, default is \p ellen_bintree::traits
            It is possible to declare option-based tree with \p ellen_bintree::make_traits metafunction
            instead of \p Traits template argument.

        @anchor cds_intrusive_EllenBinTree_less
        <b>Predicate requirements</b>

        \p Traits::less, \p Traits::compare and other predicates using with member fuctions should accept at least parameters
        of type \p T and \p Key in any combination.
        For example, for \p Foo struct with \p std::string key field the appropiate \p less functor is:
        \code
        struct Foo: public cds::intrusive::ellen_bintree::node< ... >
        {
            std::string m_strKey;
            ...
        };

        struct less {
            bool operator()( Foo const& v1, Foo const& v2 ) const
            { return v1.m_strKey < v2.m_strKey ; }

            bool operator()( Foo const& v, std::string const& s ) const
            { return v.m_strKey < s ; }

            bool operator()( std::string const& s, Foo const& v ) const
            { return s < v.m_strKey ; }

            // Support comparing std::string and char const *
            bool operator()( std::string const& s, char const * p ) const
            { return s.compare(p) < 0 ; }

            bool operator()( Foo const& v, char const * p ) const
            { return v.m_strKey.compare(p) < 0 ; }

            bool operator()( char const * p, std::string const& s ) const
            { return s.compare(p) > 0; }

            bool operator()( char const * p, Foo const& v ) const
            { return v.m_strKey.compare(p) > 0; }
        };
        \endcode

        Usage examples see \ref cds_intrusive_EllenBinTree_usage "here"
    */
    template < class GC,
        typename Key,
        typename T,
#ifdef CDS_DOXYGEN_INVOKED
        class Traits = ellen_bintree::traits
#else
        class Traits
#endif
    >
    class EllenBinTree
    {
    public:
        typedef GC      gc;         ///< Garbage collector
        typedef Key     key_type;   ///< type of a key to be stored in internal nodes; key is a part of \p value_type
        typedef T       value_type; ///< type of value stored in the binary tree
        typedef Traits  traits;     ///< Traits template parameter

        typedef typename traits::hook      hook;        ///< hook type
        typedef typename hook::node_type   node_type;   ///< node type
        typedef typename traits::disposer  disposer;    ///< leaf node disposer
        typedef typename traits::back_off  back_off;    ///< back-off strategy

        typedef typename gc::template guarded_ptr< value_type > guarded_ptr; ///< Guarded pointer

    protected:
        //@cond
        typedef ellen_bintree::base_node< gc >            tree_node; ///< Base type of tree node
        typedef node_type                                 leaf_node; ///< Leaf node type
        typedef ellen_bintree::node_types< gc, key_type, typename leaf_node::tag > node_factory;
        typedef typename node_factory::internal_node_type internal_node; ///< Internal node type
        typedef typename node_factory::update_desc_type   update_desc;   ///< Update descriptor
        typedef typename update_desc::update_ptr          update_ptr;    ///< Marked pointer to update descriptor
        //@endcond

    public:
#   ifdef CDS_DOXYGEN_INVOKED
        typedef implementation_defined key_comparator;    ///< key compare functor based on \p Traits::compare and \p Traits::less
        typedef typename get_node_traits< value_type, node_type, hook>::type node_traits; ///< Node traits
#   else
        typedef typename opt::details::make_comparator< value_type, traits >::type key_comparator;
        struct node_traits: public get_node_traits< value_type, node_type, hook>::type
        {
            static internal_node const& to_internal_node( tree_node const& n )
            {
                assert( n.is_internal() );
                return static_cast<internal_node const&>( n );
            }

            static leaf_node const& to_leaf_node( tree_node const& n )
            {
                assert( n.is_leaf() );
                return static_cast<leaf_node const&>( n );
            }
        };
#   endif

        typedef typename traits::item_counter  item_counter;   ///< Item counting policy
        typedef typename traits::memory_model  memory_model;   ///< Memory ordering, see \p cds::opt::memory_model
        typedef typename traits::stat          stat;           ///< internal statistics type
        typedef typename traits::key_extractor key_extractor;  ///< key extracting functor

        typedef typename traits::node_allocator        node_allocator;        ///< Allocator for internal node
        typedef typename traits::update_desc_allocator update_desc_allocator; ///< Update descriptor allocator

        static CDS_CONSTEXPR const size_t c_nHazardPtrCount = 9; ///< Count of hazard pointer required for the algorithm

    protected:
        //@cond
        typedef ellen_bintree::details::compare< key_type, value_type, key_comparator, node_traits > node_compare;

        typedef cds::details::Allocator< internal_node, node_allocator >        cxx_node_allocator;
        typedef cds::details::Allocator< update_desc, update_desc_allocator >   cxx_update_desc_allocator;

        struct search_result {
            enum guard_index {
                Guard_GrandParent,
                Guard_Parent,
                Guard_Leaf,
                Guard_updGrandParent,
                Guard_updParent,
                Guard_temporary,

                // end of guard indices
                guard_count
            };

            typedef typename gc::template GuardArray< guard_count > guard_array;
            guard_array guards;

            internal_node *     pGrandParent;
            internal_node *     pParent;
            leaf_node *         pLeaf;
            update_ptr          updParent;
            update_ptr          updGrandParent;
            bool                bRightLeaf;   // true if pLeaf is right child of pParent, false otherwise
            bool                bRightParent; // true if pParent is right child of pGrandParent, false otherwise

            search_result()
                :pGrandParent( nullptr )
                ,pParent( nullptr )
                ,pLeaf( nullptr )
                ,bRightLeaf( false )
                ,bRightParent( false )
            {}
        };
        //@endcond

    protected:
        //@cond
        internal_node       m_Root;     ///< Tree root node (key= Infinite2)
        leaf_node           m_LeafInf1; ///< Infinite leaf 1 (key= Infinite1)
        leaf_node           m_LeafInf2; ///< Infinite leaf 2 (key= Infinite2)
        //@endcond

        item_counter        m_ItemCounter;  ///< item counter
        mutable stat        m_Stat;         ///< internal statistics

    protected:
        //@cond
        static void free_leaf_node( value_type * p )
        {
            disposer()( p );
        }

        internal_node * alloc_internal_node() const
        {
            m_Stat.onInternalNodeCreated();
            internal_node * pNode = cxx_node_allocator().New();
            return pNode;
        }

        static void free_internal_node( internal_node * pNode )
        {
            cxx_node_allocator().Delete( pNode );
        }

        struct internal_node_deleter {
            void operator()( internal_node * p) const
            {
                free_internal_node( p );
            }
        };

        typedef std::unique_ptr< internal_node, internal_node_deleter>  unique_internal_node_ptr;

        update_desc * alloc_update_desc() const
        {
            m_Stat.onUpdateDescCreated();
            return cxx_update_desc_allocator().New();
        }

        static void free_update_desc( update_desc * pDesc )
        {
            cxx_update_desc_allocator().Delete( pDesc );
        }

        void retire_node( tree_node * pNode ) const
        {
            if ( pNode->is_leaf() ) {
                assert( static_cast<leaf_node *>( pNode ) != &m_LeafInf1 );
                assert( static_cast<leaf_node *>( pNode ) != &m_LeafInf2 );

                gc::template retire( node_traits::to_value_ptr( static_cast<leaf_node *>( pNode )), free_leaf_node );
            }
            else {
                assert( static_cast<internal_node *>( pNode ) != &m_Root );
                m_Stat.onInternalNodeDeleted();

                gc::template retire( static_cast<internal_node *>( pNode ), free_internal_node );
            }
        }

        void retire_update_desc( update_desc * p ) const
        {
            m_Stat.onUpdateDescDeleted();
            gc::template retire( p, free_update_desc );
        }

        void make_empty_tree()
        {
            m_Root.infinite_key( 2 );
            m_LeafInf1.infinite_key( 1 );
            m_LeafInf2.infinite_key( 2 );
            m_Root.m_pLeft.store( &m_LeafInf1, memory_model::memory_order_relaxed );
            m_Root.m_pRight.store( &m_LeafInf2, memory_model::memory_order_release );
        }
        //@endcond

    public:
        /// Default constructor
        EllenBinTree()
        {
            static_assert( !std::is_same< key_extractor, opt::none >::value, "The key extractor option must be specified" );
            make_empty_tree();
        }

        /// Clears the tree
        ~EllenBinTree()
        {
            unsafe_clear();
        }

        /// Inserts new node
        /**
            The function inserts \p val in the tree if it does not contain
            an item with key equal to \p val.

            Returns \p true if \p val is placed into the tree, \p false otherwise.
        */
        bool insert( value_type& val )
        {
            return insert( val, []( value_type& ) {} );
        }

        /// Inserts new node
        /**
            This function is intended for derived non-intrusive containers.

            The function allows to split creating of new item into two part:
            - create item with key only
            - insert new item into the tree
            - if inserting is success, calls  \p f functor to initialize value-field of \p val.

            The functor signature is:
            \code
                void func( value_type& val );
            \endcode
            where \p val is the item inserted. User-defined functor \p f should guarantee that during changing
            \p val no any other changes could be made on this tree's item by concurrent threads.
            The user-defined functor is called only if the inserting is success.
        */
        template <typename Func>
        bool insert( value_type& val, Func f )
        {
            typename gc::Guard guardInsert;
            guardInsert.assign( &val );

            unique_internal_node_ptr pNewInternal;
            search_result res;
            back_off bkoff;

            for ( ;; ) {
                if ( search( res, val, node_compare() )) {
                    if ( pNewInternal.get() )
                        m_Stat.onInternalNodeDeleted() ;    // unique_internal_node_ptr deletes internal node
                    m_Stat.onInsertFailed();
                    return false;
                }

                if ( res.updGrandParent.bits() == update_desc::Clean && res.updParent.bits() == update_desc::Clean ) {

                    if ( !pNewInternal.get() )
                        pNewInternal.reset( alloc_internal_node() );

                    if ( try_insert( val, pNewInternal.get(), res )) {
                        f( val );
                        pNewInternal.release(); // internal node is linked into the tree and should not be deleted
                        break;
                    }
                }

                bkoff();
                m_Stat.onInsertRetry();
            }

            ++m_ItemCounter;
            m_Stat.onInsertSuccess();
            return true;
        }

        /// Updates the node
        /**
            The operation performs inserting or changing data with lock-free manner.

            If the item \p val is not found in the set, then \p val is inserted into the set
            iff \p bAllowInsert is \p true.
            Otherwise, the functor \p func is called with item found.
            The functor \p func signature is:
            \code
                void func( bool bNew, value_type& item, value_type& val );
            \endcode
            with arguments:
            - \p bNew - \p true if the item has been inserted, \p false otherwise
            - \p item - item of the set
            - \p val - argument \p val passed into the \p %update() function
            If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
            refer to the same thing.

            The functor can change non-key fields of the \p item; however, \p func must guarantee
            that during changing no any other modifications could be made on this item by concurrent threads.

            Returns std::pair<bool, bool> where \p first is \p true if operation is successfull,
            i.e. the node has been inserted or updated,
            \p second is \p true if new item has been added or \p false if the item with \p key
            already exists.

            @warning See \ref cds_intrusive_item_creating "insert item troubleshooting"
        */
        template <typename Func>
        std::pair<bool, bool> update( value_type& val, Func func, bool bAllowInsert = true )
        {
            typename gc::Guard guardInsert;
            guardInsert.assign( &val );

            unique_internal_node_ptr pNewInternal;
            search_result res;
            back_off bkoff;

            for ( ;; ) {
                if ( search( res, val, node_compare() )) {
                    func( false, *node_traits::to_value_ptr( res.pLeaf ), val );
                    if ( pNewInternal.get() )
                        m_Stat.onInternalNodeDeleted() ;    // unique_internal_node_ptr deletes internal node
                    m_Stat.onUpdateExist();
                    return std::make_pair( true, false );
                }

                if ( res.updGrandParent.bits() == update_desc::Clean && res.updParent.bits() == update_desc::Clean )  {
                    if ( !bAllowInsert )
                        return std::make_pair( false, false );

                    if ( !pNewInternal.get() )
                        pNewInternal.reset( alloc_internal_node() );

                    if ( try_insert( val, pNewInternal.get(), res )) {
                        func( true, val, val );
                        pNewInternal.release()  ;   // internal node has been linked into the tree and should not be deleted
                        break;
                    }
                }

                bkoff();
                m_Stat.onUpdateRetry();
            }

            ++m_ItemCounter;
            m_Stat.onUpdateNew();
            return std::make_pair( true, true );
        }
        //@cond
        template <typename Func>
        CDS_DEPRECATED("ensure() is deprecated, use update()")
        std::pair<bool, bool> ensure( value_type& val, Func func )
        {
            return update( val, func, true );
        }
        //@endcond

        /// Unlinks the item \p val from the tree
        /**
            The function searches the item \p val in the tree and unlink it from the tree
            if it is found and is equal to \p val.

            Difference between \ref erase and \p unlink functions: \p erase finds <i>a key</i>
            and deletes the item found. \p unlink finds an item by key and deletes it
            only if \p val is a node, i.e. the pointer to item found is equal to <tt> &val </tt>.

            The \p disposer specified in \p Traits class template parameter is called
            by garbage collector \p GC asynchronously.

            The function returns \p true if success and \p false otherwise.
        */
        bool unlink( value_type& val )
        {
            return erase_( val, node_compare(),
                []( value_type const& v, leaf_node const& n ) -> bool { return &v == node_traits::to_value_ptr( n ); },
                [](value_type const&) {} );
        }

        /// Deletes the item from the tree
        /** \anchor cds_intrusive_EllenBinTree_erase
            The function searches an item with key equal to \p key in the tree,
            unlinks it from the tree, and returns \p true.
            If the item with key equal to \p key is not found the function return \p false.

            Note the \p Traits::less and/or \p Traits::compare predicate should accept a parameter of type \p Q 
            that can be not the same as \p value_type.
        */
        template <typename Q>
        bool erase( const Q& key )
        {
            return erase_( key, node_compare(),
                []( Q const&, leaf_node const& ) -> bool { return true; },
                [](value_type const&) {} );
        }

        /// Delete the item from the tree with comparing functor \p pred
        /**
            The function is an analog of \ref cds_intrusive_EllenBinTree_erase "erase(Q const&)"
            but \p pred predicate is used for key comparing.
            \p Less has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_less
            "Predicate requirements".
            \p pred must imply the same element order as the comparator used for building the tree.
        */
        template <typename Q, typename Less>
        bool erase_with( const Q& key, Less pred )
        {
            CDS_UNUSED( pred );
            typedef ellen_bintree::details::compare<
                key_type,
                value_type,
                opt::details::make_comparator_from_less<Less>,
                node_traits
            > compare_functor;

            return erase_( key, compare_functor(),
                []( Q const&, leaf_node const& ) -> bool { return true; },
                [](value_type const&) {} );
        }

        /// Deletes the item from the tree
        /** \anchor cds_intrusive_EllenBinTree_erase_func
            The function searches an item with key equal to \p key in the tree,
            call \p f functor with item found, unlinks it from the tree, and returns \p true.
            The \ref disposer specified in \p Traits class template parameter is called
            by garbage collector \p GC asynchronously.

            The \p Func interface is
            \code
            struct functor {
                void operator()( value_type const& item );
            };
            \endcode

            If the item with key equal to \p key is not found the function return \p false.

            Note the \p Traits::less and/or \p Traits::compare predicate should accept a parameter of type \p Q 
            that can be not the same as \p value_type.
        */
        template <typename Q, typename Func>
        bool erase( Q const& key, Func f )
        {
            return erase_( key, node_compare(),
                []( Q const&, leaf_node const& ) -> bool { return true; },
                f );
        }

        /// Delete the item from the tree with comparing functor \p pred
        /**
            The function is an analog of \ref cds_intrusive_EllenBinTree_erase_func "erase(Q const&, Func)"
            but \p pred predicate is used for key comparing.
            \p Less has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_less
            "Predicate requirements".
            \p pred must imply the same element order as the comparator used for building the tree.
        */
        template <typename Q, typename Less, typename Func>
        bool erase_with( Q const& key, Less pred, Func f )
        {
            CDS_UNUSED( pred );
            typedef ellen_bintree::details::compare<
                key_type,
                value_type,
                opt::details::make_comparator_from_less<Less>,
                node_traits
            > compare_functor;

            return erase_( key, compare_functor(),
                []( Q const&, leaf_node const& ) -> bool { return true; },
                f );
        }

        /// Extracts an item with minimal key from the tree
        /**
            The function searches an item with minimal key, unlinks it, and returns a guarded pointer to an item found.
            If the tree is empty the function returns an empty guarded pointer.

            @note Due the concurrent nature of the tree, the function extracts <i>nearly</i> minimum key.
            It means that the function gets leftmost leaf of the tree and tries to unlink it.
            During unlinking, a concurrent thread may insert an item with key less than leftmost item's key.
            So, the function returns the item with minimum key at the moment of tree traversing.

            The returned \p guarded_ptr prevents disposer invocation for returned item,
            see \p cds::gc::guarded_ptr for explanation.
            @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
        */
        guarded_ptr extract_min()
        {
            guarded_ptr gp;
            extract_min_( gp.guard() );
            return gp;
        }

        /// Extracts an item with maximal key from the tree
        /**
            The function searches an item with maximal key, unlinks it, and returns a guarded pointer to an item found.
            If the tree is empty the function returns an empty \p guarded_ptr.

            @note Due the concurrent nature of the tree, the function extracts <i>nearly</i> maximal key.
            It means that the function gets rightmost leaf of the tree and tries to unlink it.
            During unlinking, a concurrent thread may insert an item with key great than rightmost item's key.
            So, the function returns the item with maximal key at the moment of tree traversing.

            The returned \p guarded_ptr prevents disposer invocation for returned item,
            see cds::gc::guarded_ptr for explanation.
            @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
        */
        guarded_ptr extract_max()
        {
            guarded_ptr gp;
            extract_max_( gp.guard());
            return gp;
        }

        /// Extracts an item from the tree
        /** \anchor cds_intrusive_EllenBinTree_extract
            The function searches an item with key equal to \p key in the tree,
            unlinks it, and returns a guarded pointer to an item found.
            If the item  is not found the function returns an empty \p guarded_ptr.

            \p guarded_ptr prevents disposer invocation for returned item,
            see cds::gc::guarded_ptr for explanation.
            @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
        */
        template <typename Q>
        guarded_ptr extract( Q const& key )
        {
            guarded_ptr gp;
            extract_( gp.guard(), key );
            return gp;
        }

        /// Extracts an item from the tree using \p pred for searching
        /**
            The function is an analog of \ref cds_intrusive_EllenBinTree_extract "extract(Q const&)"
            but \p pred is used for key compare.
            \p Less has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_less
            "Predicate requirements".
            \p pred must imply the same element order as the comparator used for building the tree.
        */
        template <typename Q, typename Less>
        guarded_ptr extract_with( Q const& key, Less pred )
        {
            guarded_ptr gp;
            extract_with_( gp.guard(), key, pred );
            return gp;
        }

        /// Checks whether the set contains \p key
        /**
            The function searches the item with key equal to \p key
            and returns \p true if it is found, and \p false otherwise.
        */
        template <typename Q>
        bool contains( Q const& key ) const
        {
            search_result    res;
            if ( search( res, key, node_compare() )) {
                m_Stat.onFindSuccess();
                return true;
            }

            m_Stat.onFindFailed();
            return false;
        }
        //@cond
        template <typename Q>
        CDS_DEPRECATED("deprecated, use contains()")
        bool find( Q const& key ) const
        {
            return contains( key );
        }
        //@endcond

        /// Checks whether the set contains \p key using \p pred predicate for searching
        /**
            The function is similar to <tt>contains( key )</tt> but \p pred is used for key comparing.
            \p Less functor has the interface like \p std::less.
            \p Less must imply the same element order as the comparator used for building the set.
        */
        template <typename Q, typename Less>
        bool contains( Q const& key, Less pred ) const
        {
            CDS_UNUSED( pred );
            typedef ellen_bintree::details::compare<
                key_type,
                value_type,
                opt::details::make_comparator_from_less<Less>,
                node_traits
            > compare_functor;

            search_result    res;
            if ( search( res, key, compare_functor() )) {
                m_Stat.onFindSuccess();
                return true;
            }
            m_Stat.onFindFailed();
            return false;
        }
        //@cond
        template <typename Q, typename Less>
        CDS_DEPRECATED("deprecated, use contains()")
        bool find_with( Q const& key, Less pred ) const
        {
            return contains( key, pred );
        }
        //@endcond

        /// Finds the key \p key
        /** @anchor cds_intrusive_EllenBinTree_find_func
            The function searches the item with key equal to \p key and calls the functor \p f for item found.
            The interface of \p Func functor is:
            \code
            struct functor {
                void operator()( value_type& item, Q& key );
            };
            \endcode
            where \p item is the item found, \p key is the <tt>find</tt> function argument.

            The functor can change non-key fields of \p item. Note that the functor is only guarantee
            that \p item cannot be disposed during functor is executing.
            The functor does not serialize simultaneous access to the tree \p item. If such access is
            possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.

            The function returns \p true if \p key is found, \p false otherwise.
        */
        template <typename Q, typename Func>
        bool find( Q& key, Func f ) const
        {
            return find_( key, f );
        }
        //@cond
        template <typename Q, typename Func>
        bool find( Q const& key, Func f ) const
        {
            return find_( key, f );
        }
        //@endcond

        /// Finds the key \p key with comparing functor \p pred
        /**
            The function is an analog of \ref cds_intrusive_EllenBinTree_find_func "find(Q&, Func)"
            but \p pred is used for key comparison.
            \p Less functor has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_less
            "Predicate requirements".
            \p pred must imply the same element order as the comparator used for building the tree.
        */
        template <typename Q, typename Less, typename Func>
        bool find_with( Q& key, Less pred, Func f ) const
        {
            return find_with_( key, pred, f );
        }
        //@cond
        template <typename Q, typename Less, typename Func>
        bool find_with( Q const& key, Less pred, Func f ) const
        {
            return find_with_( key, pred, f );
        }
        //@endcond

        /// Finds \p key and returns the item found
        /** @anchor cds_intrusive_EllenBinTree_get
            The function searches the item with key equal to \p key and returns the item found as \p guarded_ptr object.
            The function returns an empty guarded pointer is \p key is not found.

            \p guarded_ptr prevents disposer invocation for returned item,
            see \p cds::gc::guarded_ptr for explanation.
            @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
        */
        template <typename Q>
        guarded_ptr get( Q const& key ) const
        {
            guarded_ptr gp;
            get_( gp.guard(), key );
            return gp;
        }

        /// Finds \p key with predicate \p pred and returns the item found
        /**
            The function is an analog of \ref cds_intrusive_EllenBinTree_get "get(Q const&)"
            but \p pred is used for key comparing.
            \p Less functor has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_less
            "Predicate requirements".
            \p pred must imply the same element order as the comparator used for building the tree.
        */
        template <typename Q, typename Less>
        guarded_ptr get_with( Q const& key, Less pred ) const
        {
            guarded_ptr gp;
            get_with_( gp.guard(), key, pred );
            return gp;
        }

        /// Checks if the tree is empty
        bool empty() const
        {
            return m_Root.m_pLeft.load( memory_model::memory_order_relaxed )->is_leaf();
        }

        /// Clears the tree (thread safe, not atomic)
        /**
            The function unlink all items from the tree.
            The function is thread safe but not atomic: in multi-threaded environment with parallel insertions
            this sequence
            \code
            tree.clear();
            assert( tree.empty() );
            \endcode
            the assertion could be raised.

            For each leaf the \p disposer will be called after unlinking.
        */
        void clear()
        {
            guarded_ptr gp;
            do {
                gp = extract_min();
            }  while ( gp );
        }

        /// Clears the tree (not thread safe)
        /**
            This function is not thread safe and may be called only when no other thread deals with the tree.
            The function is used in the tree destructor.
        */
        void unsafe_clear()
        {
            while ( true ) {
                internal_node * pParent = nullptr;
                internal_node * pGrandParent = nullptr;
                tree_node *     pLeaf = const_cast<internal_node *>( &m_Root );

                // Get leftmost leaf
                while ( pLeaf->is_internal() ) {
                    pGrandParent = pParent;
                    pParent = static_cast<internal_node *>( pLeaf );
                    pLeaf = pParent->m_pLeft.load( memory_model::memory_order_relaxed );
                }

                if ( pLeaf->infinite_key()) {
                    // The tree is empty
                    return;
                }

                // Remove leftmost leaf and its parent node
                assert( pGrandParent );
                assert( pParent );
                assert( pLeaf->is_leaf() );

                pGrandParent->m_pLeft.store( pParent->m_pRight.load( memory_model::memory_order_relaxed ), memory_model::memory_order_relaxed );
                free_leaf_node( node_traits::to_value_ptr( static_cast<leaf_node *>( pLeaf ) ) );
                free_internal_node( pParent );
            }
        }

        /// Returns item count in the tree
        /**
            Only leaf nodes containing user data are counted.

            The value returned depends on item counter type provided by \p Traits template parameter.
            If it is \p atomicity::empty_item_counter this function always returns 0.
            The function is not suitable for checking the tree emptiness, use \p empty()
            member function for this purpose.
        */
        size_t size() const
        {
            return m_ItemCounter;
        }

        /// Returns const reference to internal statistics
        stat const& statistics() const
        {
            return m_Stat;
        }

        /// Checks internal consistency (not atomic, not thread-safe)
        /**
            The debugging function to check internal consistency of the tree.
        */
        bool check_consistency() const
        {
            return check_consistency( &m_Root );
        }

    protected:
        //@cond

        bool check_consistency( internal_node const * pRoot ) const
        {
            tree_node * pLeft  = pRoot->m_pLeft.load( atomics::memory_order_relaxed );
            tree_node * pRight = pRoot->m_pRight.load( atomics::memory_order_relaxed );
            assert( pLeft );
            assert( pRight );

            if ( node_compare()( *pLeft, *pRoot ) < 0
                && node_compare()( *pRoot, *pRight ) <= 0
                && node_compare()( *pLeft, *pRight ) < 0 )
            {
                bool bRet = true;
                if ( pLeft->is_internal() )
                    bRet = check_consistency( static_cast<internal_node *>( pLeft ) );
                assert( bRet );

                if ( bRet && pRight->is_internal() )
                    bRet = bRet && check_consistency( static_cast<internal_node *>( pRight ));
                assert( bRet );

                return bRet;
            }
            return false;
        }

        tree_node * protect_child_node( search_result& res, internal_node * pParent, bool bRight, update_ptr updParent ) const
        {
        retry:
            tree_node * p = bRight
                ? res.guards.protect( search_result::Guard_Leaf, pParent->m_pRight,
                    []( tree_node * p ) -> internal_node* { return static_cast<internal_node *>(p);})
                : res.guards.protect( search_result::Guard_Leaf, pParent->m_pLeft,
                    []( tree_node * p ) -> internal_node* { return static_cast<internal_node *>(p);});

            // If we use member hook, data node pointer != internal node pointer
            // So, we need protect the child twice: as internal node and as data node
            // and then analyze what kind of node we have
            tree_node * pVal = bRight
                ? res.guards.protect( search_result::Guard_temporary, pParent->m_pRight,
                    []( tree_node * p ) -> value_type* { return node_traits::to_value_ptr( static_cast<leaf_node *>(p));} )
                : res.guards.protect( search_result::Guard_temporary, pParent->m_pLeft,
                    []( tree_node * p ) -> value_type* { return node_traits::to_value_ptr( static_cast<leaf_node *>(p));} );

            // child node is guarded
            // See whether pParent->m_pUpdate has not been changed
            if ( pParent->m_pUpdate.load( memory_model::memory_order_acquire ) != updParent ) {
                // update has been changed - returns nullptr as a flag to search retry
                return nullptr;
            }

            if ( p != pVal )
                goto retry;

            if ( p && p->is_leaf())
                res.guards.assign( search_result::Guard_Leaf, node_traits::to_value_ptr( static_cast<leaf_node *>( p )));

            res.guards.clear( search_result::Guard_temporary );

            return p;
        }

        static update_ptr search_protect_update( search_result& res, atomics::atomic<update_ptr> const& src )
        {
            return res.guards.protect( search_result::Guard_updParent, src, [](update_ptr p) -> update_desc* { return p.ptr(); });
        }

        template <typename KeyValue, typename Compare>
        bool search( search_result& res, KeyValue const& key, Compare cmp ) const
        {
            internal_node * pParent;
            internal_node * pGrandParent = nullptr;
            update_ptr      updParent;
            update_ptr      updGrandParent;
            bool bRightLeaf;
            bool bRightParent = false;

            int nCmp = 0;

        retry:
            pParent = nullptr;
            //pGrandParent = nullptr;
            updParent = nullptr;
            bRightLeaf = false;
            tree_node * pLeaf = const_cast<internal_node *>( &m_Root );
            while ( pLeaf->is_internal() ) {
                res.guards.copy( search_result::Guard_GrandParent, search_result::Guard_Parent );
                pGrandParent = pParent;
                res.guards.copy( search_result::Guard_Parent, search_result::Guard_Leaf );
                pParent = static_cast<internal_node *>( pLeaf );
                bRightParent = bRightLeaf;
                res.guards.copy( search_result::Guard_updGrandParent, search_result::Guard_updParent );
                updGrandParent = updParent;

                updParent = search_protect_update( res, pParent->m_pUpdate );

                switch ( updParent.bits() ) {
                    case update_desc::DFlag:
                    case update_desc::Mark:
                        m_Stat.onSearchRetry();
                        goto retry;
                }

                nCmp = cmp( key, *pParent );
                bRightLeaf = nCmp >= 0;

                pLeaf = protect_child_node( res, pParent, bRightLeaf, updParent );
                if ( !pLeaf ) {
                    m_Stat.onSearchRetry();
                    goto retry;
                }
            }

            assert( pLeaf->is_leaf() );
            nCmp = cmp( key, *static_cast<leaf_node *>(pLeaf) );

            res.pGrandParent    = pGrandParent;
            res.pParent         = pParent;
            res.pLeaf           = static_cast<leaf_node *>( pLeaf );
            res.updParent       = updParent;
            res.updGrandParent  = updGrandParent;
            res.bRightParent    = bRightParent;
            res.bRightLeaf      = bRightLeaf;

            return nCmp == 0;
        }

        bool search_min( search_result& res ) const
        {
            internal_node * pParent;
            internal_node * pGrandParent;
            update_ptr      updParent;
            update_ptr      updGrandParent;

        retry:
            pParent = nullptr;
            pGrandParent = nullptr;
            updParent = nullptr;
            tree_node *     pLeaf = const_cast<internal_node *>( &m_Root );
            while ( pLeaf->is_internal() ) {
                res.guards.copy( search_result::Guard_GrandParent, search_result::Guard_Parent );
                pGrandParent = pParent;
                res.guards.copy( search_result::Guard_Parent, search_result::Guard_Leaf );
                pParent = static_cast<internal_node *>( pLeaf );
                res.guards.copy( search_result::Guard_updGrandParent, search_result::Guard_updParent );
                updGrandParent = updParent;

                updParent = search_protect_update( res, pParent->m_pUpdate );

                switch ( updParent.bits() ) {
                    case update_desc::DFlag:
                    case update_desc::Mark:
                        m_Stat.onSearchRetry();
                        goto retry;
                }

                pLeaf = protect_child_node( res, pParent, false, updParent );
                if ( !pLeaf ) {
                    m_Stat.onSearchRetry();
                    goto retry;
                }
            }

            if ( pLeaf->infinite_key())
                return false;

            res.pGrandParent    = pGrandParent;
            res.pParent         = pParent;
            assert( pLeaf->is_leaf() );
            res.pLeaf           = static_cast<leaf_node *>( pLeaf );
            res.updParent       = updParent;
            res.updGrandParent  = updGrandParent;
            res.bRightParent    = false;
            res.bRightLeaf      = false;

            return true;
        }

        bool search_max( search_result& res ) const
        {
            internal_node * pParent;
            internal_node * pGrandParent;
            update_ptr      updParent;
            update_ptr      updGrandParent;
            bool bRightLeaf;
            bool bRightParent = false;

        retry:
            pParent = nullptr;
            pGrandParent = nullptr;
            updParent = nullptr;
            bRightLeaf = false;
            tree_node * pLeaf = const_cast<internal_node *>( &m_Root );
            while ( pLeaf->is_internal() ) {
                res.guards.copy( search_result::Guard_GrandParent, search_result::Guard_Parent );
                pGrandParent = pParent;
                res.guards.copy( search_result::Guard_Parent, search_result::Guard_Leaf );
                pParent = static_cast<internal_node *>( pLeaf );
                bRightParent = bRightLeaf;
                res.guards.copy( search_result::Guard_updGrandParent, search_result::Guard_updParent );
                updGrandParent = updParent;

                updParent = search_protect_update( res, pParent->m_pUpdate );

                switch ( updParent.bits() ) {
                    case update_desc::DFlag:
                    case update_desc::Mark:
                        m_Stat.onSearchRetry();
                        goto retry;
                }

                bRightLeaf = !pParent->infinite_key();
                pLeaf = protect_child_node( res, pParent, bRightLeaf, updParent );
                if ( !pLeaf ) {
                    m_Stat.onSearchRetry();
                    goto retry;
                }
            }

            if ( pLeaf->infinite_key())
                return false;

            res.pGrandParent    = pGrandParent;
            res.pParent         = pParent;
            assert( pLeaf->is_leaf() );
            res.pLeaf           = static_cast<leaf_node *>( pLeaf );
            res.updParent       = updParent;
            res.updGrandParent  = updGrandParent;
            res.bRightParent    = bRightParent;
            res.bRightLeaf      = bRightLeaf;

            return true;
        }

        /*
        void help( update_ptr pUpdate )
        {
            // pUpdate must be guarded!
            switch ( pUpdate.bits() ) {
                case update_desc::IFlag:
                    help_insert( pUpdate.ptr() );
                    m_Stat.onHelpInsert();
                    break;
                case update_desc::DFlag:
                    help_delete( pUpdate.ptr() );
                    m_Stat.onHelpDelete();
                    break;
                case update_desc::Mark:
                    //m_Stat.onHelpMark();
                    //help_marked( pUpdate.ptr() );
                    break;
            }
        }
        */

        void help_insert( update_desc * pOp )
        {
            // pOp must be guarded

            tree_node * pLeaf = static_cast<tree_node *>( pOp->iInfo.pLeaf );
            if ( pOp->iInfo.bRightLeaf ) {
                CDS_VERIFY( pOp->iInfo.pParent->m_pRight.compare_exchange_strong( pLeaf, static_cast<tree_node *>( pOp->iInfo.pNew ),
                    memory_model::memory_order_relaxed, atomics::memory_order_relaxed ));
            }
            else {
                CDS_VERIFY( pOp->iInfo.pParent->m_pLeft.compare_exchange_strong( pLeaf, static_cast<tree_node *>( pOp->iInfo.pNew ),
                    memory_model::memory_order_relaxed, atomics::memory_order_relaxed ));
            }

            // Unflag parent
            update_ptr cur( pOp, update_desc::IFlag );
            CDS_VERIFY( pOp->iInfo.pParent->m_pUpdate.compare_exchange_strong( cur, pOp->iInfo.pParent->null_update_desc(),
                memory_model::memory_order_release, atomics::memory_order_relaxed ));
        }

        bool check_delete_precondition( search_result& res ) const
        {
            // precondition: all member of res must be guarded

            assert( res.pGrandParent != nullptr );

            return static_cast<internal_node *>(res.pGrandParent->get_child( res.bRightParent, memory_model::memory_order_relaxed )) == res.pParent
                && static_cast<leaf_node *>( res.pParent->get_child( res.bRightLeaf, memory_model::memory_order_relaxed )) == res.pLeaf;
        }

        bool help_delete( update_desc * pOp )
        {
            // precondition: pOp must be guarded

            update_ptr pUpdate( pOp->dInfo.pUpdateParent );
            update_ptr pMark( pOp, update_desc::Mark );
            if ( pOp->dInfo.pParent->m_pUpdate.compare_exchange_strong( pUpdate, pMark, // *
                memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
            {
                help_marked( pOp );

                retire_node( pOp->dInfo.pParent );
                retire_node( pOp->dInfo.pLeaf );
                retire_update_desc( pOp );
                return true;
            }
            else if ( pUpdate == pMark ) {
                // some other thread is processing help_marked()
                help_marked( pOp );
                m_Stat.onHelpMark();
                return true;
            }
            else {
                // Undo grandparent dInfo
                update_ptr pDel( pOp, update_desc::DFlag );
                if ( pOp->dInfo.pGrandParent->m_pUpdate.compare_exchange_strong( pDel, pOp->dInfo.pGrandParent->null_update_desc(),
                    memory_model::memory_order_release, atomics::memory_order_relaxed ))
                {
                    retire_update_desc( pOp );
                }
                return false;
            }
        }

        static tree_node * protect_sibling( typename gc::Guard& guard, atomics::atomic<tree_node *>& sibling )
        {
            tree_node * pSibling = guard.protect( sibling, [](tree_node * p) -> internal_node* { return static_cast<internal_node *>(p); } );
            if ( pSibling->is_leaf() )
                guard.assign( node_traits::to_value_ptr( static_cast<leaf_node *>( pSibling )));
            return pSibling;
        }

        void help_marked( update_desc * pOp )
        {
            // precondition: pOp must be guarded

            tree_node * pParent = pOp->dInfo.pParent;

            typename gc::Guard guard;
            tree_node * pOpposite = protect_sibling( guard, pOp->dInfo.bRightLeaf ? pOp->dInfo.pParent->m_pLeft : pOp->dInfo.pParent->m_pRight );

            if ( pOp->dInfo.bRightParent ) {
                CDS_VERIFY( pOp->dInfo.pGrandParent->m_pRight.compare_exchange_strong( pParent, pOpposite,
                    memory_model::memory_order_release, atomics::memory_order_relaxed ));
            }
            else {
                CDS_VERIFY( pOp->dInfo.pGrandParent->m_pLeft.compare_exchange_strong( pParent, pOpposite,
                    memory_model::memory_order_release, atomics::memory_order_relaxed ));
            }

            update_ptr upd( pOp, update_desc::DFlag );
            CDS_VERIFY( pOp->dInfo.pGrandParent->m_pUpdate.compare_exchange_strong( upd, pOp->dInfo.pGrandParent->null_update_desc(),
                memory_model::memory_order_release, atomics::memory_order_relaxed ));
        }

        bool try_insert( value_type& val, internal_node * pNewInternal, search_result& res )
        {
            assert( res.updParent.bits() == update_desc::Clean );
            assert( res.pLeaf->is_leaf() );

            // check search result
            if ( res.pParent->get_child( res.bRightLeaf, memory_model::memory_order_acquire ) == res.pLeaf ) {
                leaf_node * pNewLeaf = node_traits::to_node_ptr( val );

                int nCmp = node_compare()(val, *res.pLeaf);
                if ( nCmp < 0 ) {
                    if ( res.pGrandParent ) {
                        assert( !res.pLeaf->infinite_key() );
                        pNewInternal->infinite_key( 0 );
                        key_extractor()(pNewInternal->m_Key, *node_traits::to_value_ptr( res.pLeaf ));
                    }
                    else {
                        assert( res.pLeaf->infinite_key() == tree_node::key_infinite1 );
                        pNewInternal->infinite_key( 1 );
                    }
                    pNewInternal->m_pLeft.store( static_cast<tree_node *>(pNewLeaf), memory_model::memory_order_relaxed );
                    pNewInternal->m_pRight.store( static_cast<tree_node *>(res.pLeaf), memory_model::memory_order_release );
                }
                else {
                    assert( !res.pLeaf->is_internal() );

                    pNewInternal->infinite_key( 0 );
                    key_extractor()(pNewInternal->m_Key, val);
                    pNewInternal->m_pLeft.store( static_cast<tree_node *>(res.pLeaf), memory_model::memory_order_relaxed );
                    pNewInternal->m_pRight.store( static_cast<tree_node *>(pNewLeaf), memory_model::memory_order_release );
                    assert( !res.pLeaf->infinite_key() );
                }

                typename gc::Guard guard;
                update_desc * pOp = alloc_update_desc();
                guard.assign( pOp );

                pOp->iInfo.pParent = res.pParent;
                pOp->iInfo.pNew = pNewInternal;
                pOp->iInfo.pLeaf = res.pLeaf;
                pOp->iInfo.bRightLeaf = res.bRightLeaf;

                update_ptr updCur( res.updParent.ptr() );
                if ( res.pParent->m_pUpdate.compare_exchange_strong( updCur, update_ptr( pOp, update_desc::IFlag ),
                    memory_model::memory_order_acquire, atomics::memory_order_relaxed ) ) {
                    // do insert
                    help_insert( pOp );
                    retire_update_desc( pOp );
                    return true;
                }
                else {
                    m_Stat.onUpdateDescDeleted();
                    free_update_desc( pOp );
                }
            }

            return false;
        }

        template <typename Q, typename Compare, typename Equal, typename Func>
        bool erase_( Q const& val, Compare cmp, Equal eq, Func f )
        {
            update_desc * pOp = nullptr;
            search_result res;
            back_off bkoff;

            for ( ;; ) {
                if ( !search( res, val, cmp ) || !eq( val, *res.pLeaf ) ) {
                    if ( pOp )
                        retire_update_desc( pOp );
                    m_Stat.onEraseFailed();
                    return false;
                }

                if ( res.updGrandParent.bits() == update_desc::Clean && res.updParent.bits() == update_desc::Clean ) {
                    if ( !pOp )
                        pOp = alloc_update_desc();
                    if ( check_delete_precondition( res ) ) {
                        typename gc::Guard guard;
                        guard.assign( pOp );

                        pOp->dInfo.pGrandParent = res.pGrandParent;
                        pOp->dInfo.pParent = res.pParent;
                        pOp->dInfo.pLeaf = res.pLeaf;
                        pOp->dInfo.pUpdateParent = res.updParent.ptr();
                        pOp->dInfo.bRightParent = res.bRightParent;
                        pOp->dInfo.bRightLeaf = res.bRightLeaf;

                        update_ptr updGP( res.updGrandParent.ptr() );
                        if ( res.pGrandParent->m_pUpdate.compare_exchange_strong( updGP, update_ptr( pOp, update_desc::DFlag ),
                            memory_model::memory_order_acquire, atomics::memory_order_relaxed ) ) {
                            if ( help_delete( pOp ) ) {
                                // res.pLeaf is not deleted yet since it is guarded
                                f( *node_traits::to_value_ptr( res.pLeaf ) );
                                break;
                            }
                            pOp = nullptr;
                        }
                    }
                }

                bkoff();
                m_Stat.onEraseRetry();
            }

            --m_ItemCounter;
            m_Stat.onEraseSuccess();
            return true;
        }

        template <typename Q>
        bool extract_( typename guarded_ptr::native_guard& guard, Q const& key )
        {
            return erase_( key, node_compare(),
                []( Q const&, leaf_node const& ) -> bool { return true; },
                [&guard]( value_type& found ) { guard.set( &found ); } );
        }

        template <typename Q, typename Less>
        bool extract_with_( typename guarded_ptr::native_guard& guard, Q const& key, Less /*pred*/ )
        {
            typedef ellen_bintree::details::compare<
                key_type,
                value_type,
                opt::details::make_comparator_from_less<Less>,
                node_traits
            > compare_functor;

            return erase_( key, compare_functor(),
                []( Q const&, leaf_node const& ) -> bool { return true; },
                [&guard]( value_type& found ) { guard.set( &found ); } );
        }

        bool extract_max_( typename guarded_ptr::native_guard& gp )
        {
            update_desc * pOp = nullptr;
            search_result res;
            back_off bkoff;

            for ( ;; ) {
                if ( !search_max( res )) {
                    // Tree is empty
                    if ( pOp )
                        retire_update_desc( pOp );
                    m_Stat.onExtractMaxFailed();
                    return false;
                }

                if ( res.updGrandParent.bits() == update_desc::Clean && res.updParent.bits() == update_desc::Clean ) {
                    if ( !pOp )
                        pOp = alloc_update_desc();
                    if ( check_delete_precondition( res ) ) {
                        typename gc::Guard guard;
                        guard.assign( pOp );

                        pOp->dInfo.pGrandParent = res.pGrandParent;
                        pOp->dInfo.pParent = res.pParent;
                        pOp->dInfo.pLeaf = res.pLeaf;
                        pOp->dInfo.pUpdateParent = res.updParent.ptr();
                        pOp->dInfo.bRightParent = res.bRightParent;
                        pOp->dInfo.bRightLeaf = res.bRightLeaf;

                        update_ptr updGP( res.updGrandParent.ptr() );
                        if ( res.pGrandParent->m_pUpdate.compare_exchange_strong( updGP, update_ptr( pOp, update_desc::DFlag ),
                                memory_model::memory_order_acquire, atomics::memory_order_relaxed ) )
                        {
                            if ( help_delete( pOp ) )
                                break;
                            pOp = nullptr;
                        }
                    }
                }

                bkoff();
                m_Stat.onExtractMaxRetry();
            }

            --m_ItemCounter;
            m_Stat.onExtractMaxSuccess();
            gp.set( node_traits::to_value_ptr( res.pLeaf ));
            return true;
        }

        bool extract_min_( typename guarded_ptr::native_guard& gp )
        {
            update_desc * pOp = nullptr;
            search_result res;
            back_off bkoff;

            for ( ;; ) {
                if ( !search_min( res )) {
                    // Tree is empty
                    if ( pOp )
                        retire_update_desc( pOp );
                    m_Stat.onExtractMinFailed();
                    return false;
                }

                if ( res.updGrandParent.bits() == update_desc::Clean && res.updParent.bits() == update_desc::Clean ) {
                    if ( !pOp )
                        pOp = alloc_update_desc();
                    if ( check_delete_precondition( res ) ) {
                        typename gc::Guard guard;
                        guard.assign( pOp );

                        pOp->dInfo.pGrandParent = res.pGrandParent;
                        pOp->dInfo.pParent = res.pParent;
                        pOp->dInfo.pLeaf = res.pLeaf;
                        pOp->dInfo.pUpdateParent = res.updParent.ptr();
                        pOp->dInfo.bRightParent = res.bRightParent;
                        pOp->dInfo.bRightLeaf = res.bRightLeaf;

                        update_ptr updGP( res.updGrandParent.ptr() );
                        if ( res.pGrandParent->m_pUpdate.compare_exchange_strong( updGP, update_ptr( pOp, update_desc::DFlag ),
                            memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
                        {
                            if ( help_delete( pOp ))
                                break;
                            pOp = nullptr;
                        }
                    }
                }

                bkoff();
                m_Stat.onExtractMinRetry();
            }

            --m_ItemCounter;
            m_Stat.onExtractMinSuccess();
            gp.set( node_traits::to_value_ptr( res.pLeaf ));
            return true;
        }

        template <typename Q, typename Func>
        bool find_( Q& val, Func f ) const
        {
            search_result    res;
            if ( search( res, val, node_compare() )) {
                assert( res.pLeaf );
                f( *node_traits::to_value_ptr( res.pLeaf ), val );

                m_Stat.onFindSuccess();
                return true;
            }

            m_Stat.onFindFailed();
            return false;
        }

        template <typename Q, typename Less, typename Func>
        bool find_with_( Q& val, Less /*pred*/, Func f ) const
        {
            typedef ellen_bintree::details::compare<
                key_type,
                value_type,
                opt::details::make_comparator_from_less<Less>,
                node_traits
            > compare_functor;

            search_result    res;
            if ( search( res, val, compare_functor() )) {
                assert( res.pLeaf );
                f( *node_traits::to_value_ptr( res.pLeaf ), val );

                m_Stat.onFindSuccess();
                return true;
            }

            m_Stat.onFindFailed();
            return false;
        }

        template <typename Q>
        bool get_( typename guarded_ptr::native_guard& guard, Q const& val ) const
        {
            return find_( val, [&guard]( value_type& found, Q const& ) { guard.set( &found ); } );
        }

        template <typename Q, typename Less>
        bool get_with_( typename guarded_ptr::native_guard& guard, Q const& val, Less pred ) const
        {
            return find_with_( val, pred, [&guard]( value_type& found, Q const& ) { guard.set( &found ); } );
        }

        //@endcond
    };

}} // namespace cds::intrusive

#endif // #ifndef CDSLIB_INTRUSIVE_IMPL_ELLEN_BINTREE_H
