-//$$CDS-header$$
+/*
+ This file is a part of libcds - Concurrent Data Structures library
-#ifndef __CDS_INTRUSIVE_DETAILS_ELLEN_BINTREE_BASE_H
-#define __CDS_INTRUSIVE_DETAILS_ELLEN_BINTREE_BASE_H
+ (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016
-#include <cds/intrusive/base.h>
+ 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_DETAILS_ELLEN_BINTREE_BASE_H
+#define CDSLIB_INTRUSIVE_DETAILS_ELLEN_BINTREE_BASE_H
+
+#include <type_traits>
+#include <cds/intrusive/details/base.h>
#include <cds/opt/options.h>
#include <cds/urcu/options.h>
-#include <cds/details/std/type_traits.h>
#include <cds/details/marked_ptr.h>
-#include <cds/details/allocator.h>
namespace cds { namespace intrusive {
/// EllenBinTree related declarations
namespace ellen_bintree {
-
//Forwards
template <class GC> struct base_node;
template <class GC, typename Tag = opt::none> struct node;
delete_info dInfo;
};
- update_desc * pNextRetire ; // for local retired list (RCU)
+ update_desc * pNextRetire; // for local retired list (RCU)
update_desc()
: pNextRetire( nullptr )
key_infinite = key_infinite1 | key_infinite2 ///< Cumulative infinite flags
};
- unsigned int m_nFlags ; ///< Internal flags
+ atomics::atomic<unsigned int> m_nFlags; ///< Internal flags
/// Constructs leaf (bIntrenal == false) or internal (bInternal == true) node
explicit basic_node( bool bInternal )
/// Checks if the node is internal
bool is_internal() const
{
- return (m_nFlags & internal) != 0;
+ return (m_nFlags.load(atomics::memory_order_relaxed) & internal) != 0;
}
/// Returns infinite key, 0 if the node is not infinite
unsigned int infinite_key() const
{
- return m_nFlags & key_infinite;
+ return m_nFlags.load(atomics::memory_order_relaxed) & key_infinite;
}
/// Sets infinite key for the node (for internal use only!!!)
void infinite_key( int nInf )
{
- m_nFlags &= ~key_infinite;
+ unsigned int nFlags = m_nFlags.load(atomics::memory_order_relaxed);
+ nFlags &= ~key_infinite;
switch ( nInf ) {
case 1:
- m_nFlags |= key_infinite1;
+ nFlags |= key_infinite1;
break;
case 2:
- m_nFlags |= key_infinite2;
+ nFlags |= key_infinite2;
break;
case 0:
break;
assert( false );
break;
}
+ m_nFlags.store( nFlags, atomics::memory_order_relaxed );
}
};
/**
Template parameters:
- \p GC - one of \ref cds_garbage_collector "garbage collector type"
- - \p Tag - a tag used to distinguish between different implementation. An incomplete type may be used as a tag.
+ - \p Tag - a \ref cds_intrusive_hook_tag "tag"
*/
template <typename GC,
# ifdef CDS_DOXYGEN_INVOKED
typedef base_node< GC > base_class;
//@endcond
- typedef GC gc ; ///< Garbage collector type
- typedef Tag tag ; ///< Tag
+ typedef GC gc; ///< Garbage collector
+ typedef Tag tag; ///< Tag
/// Default ctor
node()
typedef base_node<typename LeafNode::gc> base_class;
//@endcond
- typedef Key key_type ; ///< key type
- typedef LeafNode leaf_node ; ///< type of leaf node
+ typedef Key key_type; ///< key type
+ typedef LeafNode leaf_node; ///< type of leaf node
typedef update_desc< leaf_node, internal_node > update_desc_type; ///< Update descriptor
- typedef typename update_desc_type::update_ptr update_ptr ; ///< Marked pointer to update descriptor
+ typedef typename update_desc_type::update_ptr update_ptr; ///< Marked pointer to update descriptor
- key_type m_Key ; ///< Regular key
- CDS_ATOMIC::atomic<base_class *> m_pLeft ; ///< Left subtree
- CDS_ATOMIC::atomic<base_class *> m_pRight ; ///< Right subtree
- CDS_ATOMIC::atomic<update_ptr> m_pUpdate ; ///< Update descriptor
+ key_type m_Key; ///< Regular key
+ atomics::atomic<base_class *> m_pLeft; ///< Left subtree
+ atomics::atomic<base_class *> m_pRight; ///< Right subtree
+ atomics::atomic<update_ptr> m_pUpdate; ///< Update descriptor
//@cond
- uintptr_t m_nEmptyUpdate; ///< ABA prevention for m_pUpdate, from 0..2^16 step 4
+ uintptr_t m_nEmptyUpdate; ///< ABA prevention for m_pUpdate, from 0..2^16 step 4
//@endcond
/// Default ctor
: base_class( true )
, m_pLeft( nullptr )
, m_pRight( nullptr )
- , m_pUpdate( update_ptr() )
+ , m_pUpdate( update_ptr())
, m_nEmptyUpdate(0)
{}
//@cond
update_ptr null_update_desc()
{
- return update_ptr( reinterpret_cast<update_desc_type *>( (++m_nEmptyUpdate << 2) & 0xFFFF ) );
+ return update_ptr( reinterpret_cast<update_desc_type *>( (++m_nEmptyUpdate << 2) & 0xFFFF ));
+ }
+
+ base_class * get_child( bool bRight, atomics::memory_order mo ) const
+ {
+ return bRight ? m_pRight.load( mo ) : m_pLeft.load( mo );
}
//@endcond
};
/**
This struct declares different \p %EllenBinTree node types.
It can be useful for simplifying \p %EllenBinTree node declaration in your application.
+
+ Template parameters:
+ - \p GC - one of \ref cds_garbage_collector "garbage collector type"
+ - \p Key - key type
+ - \p Tag - a \ref cds_intrusive_hook_tag "tag"
*/
template <typename GC, typename Key, typename Tag = opt::none>
struct node_types
{
- typedef node<GC, Tag> leaf_node_type ; ///< Leaf node type
- typedef internal_node<Key, leaf_node_type> internal_node_type ; ///< Internal node type
- typedef update_desc<leaf_node_type, internal_node_type> update_desc_type ; ///< Update descriptor type
+ typedef node<GC, Tag> leaf_node_type; ///< Leaf node type
+ typedef internal_node<Key, leaf_node_type> internal_node_type; ///< Internal node type
+ typedef update_desc<leaf_node_type, internal_node_type> update_desc_type; ///< Update descriptor type
};
//@cond
//@endcond
//@cond
- template < typename HookType, CDS_DECL_OPTIONS2>
+ template < typename HookType, typename... Options>
struct hook
{
- typedef typename opt::make_options< default_hook, CDS_OPTIONS2>::type options;
+ typedef typename opt::make_options< default_hook, Options...>::type options;
typedef typename options::gc gc;
typedef typename options::tag tag;
typedef node<gc, tag> node_type;
/// Base hook
/**
\p Options are:
- - opt::gc - garbage collector used.
- - opt::tag - a tag
+ - \p opt::gc - garbage collector
+ - \p opt::tag - a \ref cds_intrusive_hook_tag "tag"
*/
- template < CDS_DECL_OPTIONS2 >
- struct base_hook: public hook< opt::base_hook_tag, CDS_OPTIONS2 >
+ template < typename... Options >
+ struct base_hook: public hook< opt::base_hook_tag, Options... >
{};
/// Member hook
Use \p offsetof macro to define \p MemberOffset
\p Options are:
- - opt::gc - garbage collector used.
- - opt::tag - a tag
+ - \p opt::gc - garbage collector
+ - \p opt::tag - a \ref cds_intrusive_hook_tag "tag"
*/
- template < size_t MemberOffset, CDS_DECL_OPTIONS2 >
- struct member_hook: public hook< opt::member_hook_tag, CDS_OPTIONS2 >
+ template < size_t MemberOffset, typename... Options >
+ struct member_hook: public hook< opt::member_hook_tag, Options... >
{
//@cond
- static const size_t c_nMemberOffset = MemberOffset;
+ static CDS_CONSTEXPR const size_t c_nMemberOffset = MemberOffset;
//@endcond
};
See \ref node_traits for \p NodeTraits interface description
\p Options are:
- - opt::gc - garbage collector used.
- - opt::tag - a tag
+ - opt::gc - garbage collector
+ - \p opt::tag - a \ref cds_intrusive_hook_tag "tag"
*/
- template <typename NodeTraits, CDS_DECL_OPTIONS2 >
- struct traits_hook: public hook< opt::traits_hook_tag, CDS_OPTIONS2 >
+ template <typename NodeTraits, typename... Options >
+ struct traits_hook: public hook< opt::traits_hook_tag, Options... >
{
//@cond
typedef NodeTraits node_traits;
event_counter m_nInsertSuccess ; ///< Count of success insertion
event_counter m_nInsertFailed ; ///< Count of failed insertion
event_counter m_nInsertRetries ; ///< Count of unsuccessful retries of insertion
- event_counter m_nEnsureExist ; ///< Count of \p ensure call for existed node
- event_counter m_nEnsureNew ; ///< Count of \p ensure call for new node
- event_counter m_nEnsureRetries ; ///< Count of unsuccessful retries of ensuring
+ event_counter m_nUpdateExist ; ///< Count of \p update() call for existed node
+ event_counter m_nUpdateNew ; ///< Count of \p update() call for new node
+ event_counter m_nUpdateRetries ; ///< Count of unsuccessful retries of ensuring
event_counter m_nEraseSuccess ; ///< Count of successful call of \p erase and \p unlink
event_counter m_nEraseFailed ; ///< Count of failed call of \p erase and \p unlink
event_counter m_nEraseRetries ; ///< Count of unsuccessful retries inside erasing/unlinking
void onInsertSuccess() { ++m_nInsertSuccess ; }
void onInsertFailed() { ++m_nInsertFailed ; }
void onInsertRetry() { ++m_nInsertRetries ; }
- void onEnsureExist() { ++m_nEnsureExist ; }
- void onEnsureNew() { ++m_nEnsureNew ; }
- void onEnsureRetry() { ++m_nEnsureRetries ; }
+ void onUpdateExist() { ++m_nUpdateExist ; }
+ void onUpdateNew() { ++m_nUpdateNew ; }
+ void onUpdateRetry() { ++m_nUpdateRetries ; }
void onEraseSuccess() { ++m_nEraseSuccess ; }
void onEraseFailed() { ++m_nEraseFailed ; }
void onEraseRetry() { ++m_nEraseRetries ; }
/// EllenBinTree empty statistics
struct empty_stat {
//@cond
- void onInternalNodeCreated() {}
- void onInternalNodeDeleted() {}
- void onUpdateDescCreated() {}
- void onUpdateDescDeleted() {}
- void onInsertSuccess() {}
- void onInsertFailed() {}
- void onInsertRetry() {}
- void onEnsureExist() {}
- void onEnsureNew() {}
- void onEnsureRetry() {}
- void onEraseSuccess() {}
- void onEraseFailed() {}
- void onEraseRetry() {}
- void onExtractMinSuccess() {}
- void onExtractMinFailed() {}
- void onExtractMinRetry() {}
- void onExtractMaxSuccess() {}
- void onExtractMaxFailed() {}
- void onExtractMaxRetry() {}
- void onFindSuccess() {}
- void onFindFailed() {}
- void onSearchRetry() {}
- void onHelpInsert() {}
- void onHelpDelete() {}
- void onHelpMark() {}
- void onHelpGuardSuccess() {}
- void onHelpGuardFailed() {}
+ void onInternalNodeCreated() const {}
+ void onInternalNodeDeleted() const {}
+ void onUpdateDescCreated() const {}
+ void onUpdateDescDeleted() const {}
+ void onInsertSuccess() const {}
+ void onInsertFailed() const {}
+ void onInsertRetry() const {}
+ void onUpdateExist() const {}
+ void onUpdateNew() const {}
+ void onUpdateRetry() const {}
+ void onEraseSuccess() const {}
+ void onEraseFailed() const {}
+ void onEraseRetry() const {}
+ void onExtractMinSuccess() const {}
+ void onExtractMinFailed() const {}
+ void onExtractMinRetry() const {}
+ void onExtractMaxSuccess() const {}
+ void onExtractMaxFailed() const {}
+ void onExtractMaxRetry() const {}
+ void onFindSuccess() const {}
+ void onFindFailed() const {}
+ void onSearchRetry() const {}
+ void onHelpInsert() const {}
+ void onHelpDelete() const {}
+ void onHelpMark() const {}
+ void onHelpGuardSuccess() const {}
+ void onHelpGuardFailed() const {}
//@endcond
};
- /// Type traits for EllenBinTree class
- struct type_traits
+ /// EllenBinTree traits
+ struct traits
{
- /// Hook used
+ /// Hook used (mandatory)
/**
- Possible values are: ellen_bintree::base_hook, ellen_bintree::member_hook, ellen_bintree::traits_hook.
+ Possible values are: \p ellen_bintree::base_hook, \p ellen_bintree::member_hook, \p ellen_bintree::traits_hook.
*/
typedef base_hook<> hook;
- /// Key extracting functor
+ /// Key extracting functor (mandatory)
/**
You should explicit define a valid functor.
The functor has the following prototype:
It should initialize \p dest key from \p src data.
The functor is used to initialize internal nodes.
*/
- typedef opt::none key_extractor;
+ typedef opt::none key_extractor;
/// Key comparison functor
/**
No default functor is provided. If the option is not specified, the \p less is used.
- See cds::opt::compare option description for functor interface.
+ See \p cds::opt::compare option description for functor interface.
You should provide \p compare or \p less functor.
See \ref cds_intrusive_EllenBinTree_rcu_less "predicate requirements".
*/
- typedef opt::none compare;
+ typedef opt::none compare;
/// Specifies binary predicate used for key compare.
/**
- See cds::opt::less option description for predicate interface.
+ See \p cds::opt::less option description for predicate interface.
You should provide \p compare or \p less functor.
See \ref cds_intrusive_EllenBinTree_rcu_less "predicate requirements".
*/
- typedef opt::none less;
+ typedef opt::none less;
/// Disposer
/**
- The functor used for dispose removed items. Default is opt::v::empty_disposer.
+ The functor used for dispose removed items. Default is \p opt::v::empty_disposer.
*/
- typedef opt::v::empty_disposer disposer;
+ typedef opt::v::empty_disposer disposer;
/// Item counter
/**
- The type for item counting feature (see cds::opt::item_counter).
- Default is no item counter (\ref atomicity::empty_item_counter)
+ The type for item counter, by default it is disabled (\p atomicity::empty_item_counter).
+ To enable it use \p atomicity::item_counter
*/
- typedef atomicity::empty_item_counter item_counter;
+ typedef atomicity::empty_item_counter item_counter;
/// C++ memory ordering model
/**
- List of available memory ordering see opt::memory_model
+ List of available memory ordering see \p opt::memory_model
*/
- typedef opt::v::relaxed_ordering memory_model;
+ typedef opt::v::relaxed_ordering memory_model;
/// Allocator for update descriptors
/**
- The allocator type is used for \ref update_desc.
+ The allocator type is used for \p ellen_bintree::update_desc.
Update descriptor is helping data structure with short lifetime and it is good candidate
- for pooling. The number of simultaneously existing descriptors is bounded number
+ for pooling. The number of simultaneously existing descriptors is bounded and it is
limited the number of threads working with the tree.
Therefore, a bounded lock-free container like \p cds::container::VyukovMPMCCycleQueue
is good choice for the free-list of update descriptors,
- see cds::memory::vyukov_queue_pool free-list implementation.
+ see \p cds::memory::vyukov_queue_pool free-list implementation.
Also notice that size of update descriptor is constant and not dependent on the type of data
stored in the tree so single free-list object can be used for several \p EllenBinTree object.
*/
- typedef CDS_DEFAULT_ALLOCATOR update_desc_allocator;
+ typedef CDS_DEFAULT_ALLOCATOR update_desc_allocator;
/// Allocator for internal nodes
/**
- The allocator type is used for \ref internal_node.
+ The allocator type is used for \p ellen_bintree::internal_node.
*/
- typedef CDS_DEFAULT_ALLOCATOR node_allocator;
+ typedef CDS_DEFAULT_ALLOCATOR node_allocator;
/// Internal statistics
/**
- Possible types: \p ellen_bintree::empty_stat (the default), \p ellen_bintree::stat or any
- other with interface like \p %stat.
+ By default, internal statistics is disabled (\p ellen_bintree::empty_stat).
+ To enable it use \p ellen_bintree::stat.
*/
- typedef empty_stat stat;
+ typedef empty_stat stat;
+
+ /// Back-off strategy
+ typedef cds::backoff::empty back_off;
/// RCU deadlock checking policy (only for \ref cds_intrusive_EllenBinTree_rcu "RCU-based EllenBinTree")
/**
- List of available options see opt::rcu_check_deadlock
+ List of available options see \p opt::rcu_check_deadlock
*/
- typedef cds::opt::v::rcu_throw_deadlock rcu_check_deadlock;
+ typedef cds::opt::v::rcu_throw_deadlock rcu_check_deadlock;
};
/// Metafunction converting option list to EllenBinTree traits
/**
- This is a wrapper for <tt> cds::opt::make_options< type_traits, Options...> </tt>
- \p Options list see \ref EllenBinTree.
+ \p Options are:
+ - \p opt::hook - hook used. Possible values are: \p ellen_bintree::base_hook, \p ellen_bintree::member_hook, \p ellen_bintree::traits_hook.
+ If the option is not specified, <tt>ellen_bintree::base_hook<></tt> is used.
+ - \p ellen_bintree::key_extractor - key extracting functor, mandatory option. The functor has the following prototype:
+ \code
+ struct key_extractor {
+ void operator ()( Key& dest, T const& src );
+ };
+ \endcode
+ It should initialize \p dest key from \p src data. The functor is used to initialize internal nodes.
+ - \p opt::compare - key compare functor. No default functor is provided.
+ If the option is not specified, \p %opt::less is used.
+ - \p opt::less - specifies binary predicate used for key compare. At least \p %opt::compare or \p %opt::less should be defined.
+ - \p opt::disposer - the functor used for dispose removed nodes. Default is \p opt::v::empty_disposer. Due the nature
+ of GC schema the disposer may be called asynchronously. The disposer is used only for leaf nodes.
+ - \p opt::item_counter - the type of item counting feature, by default it is disabled (\p atomicity::empty_item_counter)
+ To enable it use \p atomicity::item_counter
+ - \p opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
+ or \p opt::v::sequential_consistent (sequentially consisnent memory model).
+ - \p ellen_bintree::update_desc_allocator - an allocator of \ref ellen_bintree::update_desc "update descriptors",
+ default is \ref CDS_DEFAULT_ALLOCATOR.
+ Note that update descriptor is helping data structure with short lifetime and it is good candidate for pooling.
+ The number of simultaneously existing descriptors is bounded and depends on the number of threads
+ working with the tree and GC internals.
+ A bounded lock-free container like \p cds::container::VyukovMPMCCycleQueue is good candidate
+ for the free-list of update descriptors, see cds::memory::vyukov_queue_pool free-list implementation.
+ Also notice that size of update descriptor is constant and not dependent on the type of data
+ stored in the tree so single free-list object can be used for all \p %EllenBinTree objects.
+ - \p opt::node_allocator - the allocator for internal nodes. Default is \ref CDS_DEFAULT_ALLOCATOR.
+ - \p opt::stat - internal statistics, by default it is disabled (\p ellen_bintree::empty_stat)
+ To enable statistics use \p \p ellen_bintree::stat
+ - \p opt::backoff - back-off strategy, by default no strategy is used (\p cds::backoff::empty)
+ - \p opt::rcu_check_deadlock - a deadlock checking policy for RCU-based tree, default is \p opt::v::rcu_throw_deadlock
*/
- template <CDS_DECL_OPTIONS12>
+ template <typename... Options>
struct make_traits {
# ifdef CDS_DOXYGEN_INVOKED
typedef implementation_defined type ; ///< Metafunction result
# else
typedef typename cds::opt::make_options<
- typename cds::opt::find_type_traits< type_traits, CDS_OPTIONS12 >::type
- ,CDS_OPTIONS12
+ typename cds::opt::find_type_traits< traits, Options... >::type
+ ,Options...
>::type type;
# endif
};
template <typename LeafNode>
int operator()( internal_node<key_type, LeafNode> const& n1, internal_node<key_type, LeafNode> const& n2 ) const
{
- if ( n1.infinite_key() )
+ if ( n1.infinite_key())
return n2.infinite_key() ? n1.infinite_key() - n2.infinite_key() : 1;
- else if ( n2.infinite_key() )
+ else if ( n2.infinite_key())
return -1;
return operator()( n1.m_Key, n2.m_Key );
}
template <typename LeafNode, typename Q>
int operator()( internal_node<key_type, LeafNode> const& n, Q const& v ) const
{
- if ( n.infinite_key() )
+ if ( n.infinite_key())
return 1;
return operator()( n.m_Key, v );
}
template <typename LeafNode, typename Q>
int operator()( Q const& v, internal_node<key_type, LeafNode> const& n ) const
{
- if ( n.infinite_key() )
+ if ( n.infinite_key())
return -1;
return operator()( v, n.m_Key );
}
template <typename GC, typename Tag>
int operator()( node<GC, Tag> const& n1, node<GC, Tag> const& n2 ) const
{
- if ( n1.infinite_key() != n2.infinite_key() )
+ if ( n1.infinite_key() != n2.infinite_key())
return n1.infinite_key() - n2.infinite_key();
return operator()( *node_traits::to_value_ptr( n1 ), *node_traits::to_value_ptr( n2 ));
}
template <typename GC, typename Tag, typename Q>
int operator()( node<GC, Tag> const& n, Q const& v ) const
{
- if ( n.infinite_key() )
+ if ( n.infinite_key())
return 1;
return operator()( *node_traits::to_value_ptr( n ), v );
}
template <typename GC, typename Tag, typename Q>
int operator()( Q const& v, node<GC, Tag> const& n ) const
{
- if ( n.infinite_key() )
+ if ( n.infinite_key())
return -1;
- return operator()( v, *node_traits::to_value_ptr( n ) );
+ return operator()( v, *node_traits::to_value_ptr( n ));
}
template <typename GC>
int operator()( base_node<GC> const& n1, base_node<GC> const& n2 ) const
{
- if ( n1.infinite_key() != n2.infinite_key() )
+ if ( n1.infinite_key() != n2.infinite_key())
return n1.infinite_key() - n2.infinite_key();
- if ( n1.is_leaf() ) {
- if ( n2.is_leaf() )
+ if ( n1.is_leaf()) {
+ if ( n2.is_leaf())
return operator()( node_traits::to_leaf_node( n1 ), node_traits::to_leaf_node( n2 ));
else
return operator()( node_traits::to_leaf_node( n1 ), node_traits::to_internal_node( n2 ));
}
- if ( n2.is_leaf() )
+ if ( n2.is_leaf())
return operator()( node_traits::to_internal_node( n1 ), node_traits::to_leaf_node( n2 ));
else
return operator()( node_traits::to_internal_node( n1 ), node_traits::to_internal_node( n2 ));
{
if ( n.infinite_key())
return 1;
- if ( n.is_leaf() )
+ if ( n.is_leaf())
return operator()( node_traits::to_leaf_node( n ), v );
return operator()( node_traits::to_internal_node( n ), v );
}
template <typename GC, typename LeafNode >
int operator()( base_node<GC> const& i, internal_node<key_type, LeafNode> const& n ) const
{
- if ( i.is_leaf() )
+ if ( i.is_leaf())
return operator()( static_cast<LeafNode const&>(i), n );
return operator()( static_cast<internal_node<key_type, LeafNode> const&>(i), n );
}
template <typename GC, typename Tag >
int operator()( node<GC, Tag> const& n, internal_node<key_type, node<GC, Tag> > const& i ) const
{
- if ( !n.infinite_key() ) {
- if ( i.infinite_key() )
+ if ( !n.infinite_key()) {
+ if ( i.infinite_key())
return -1;
return operator()( n, i.m_Key );
}
} // namespace details
//@endcond
-
} // namespace ellen_bintree
// Forwards
- template < class GC, typename Key, typename T, class Traits = ellen_bintree::type_traits >
+ template < class GC, typename Key, typename T, class Traits = ellen_bintree::traits >
class EllenBinTree;
}} // namespace cds::intrusive
-#endif // #ifndef __CDS_INTRUSIVE_DETAILS_ELLEN_BINTREE_BASE_H
+#endif // #ifndef CDSLIB_INTRUSIVE_DETAILS_ELLEN_BINTREE_BASE_H