From 2c6a986edea7ad68bedad91f3678c3f76302a5e5 Mon Sep 17 00:00:00 2001 From: khizmax Date: Fri, 7 Nov 2014 13:47:17 +0300 Subject: [PATCH] intrusive::ellen_bintree refactoring --- cds/intrusive/details/ellen_bintree_base.h | 116 +++++--- cds/intrusive/details/michael_list_base.h | 4 +- cds/intrusive/ellen_bintree_dhp.h | 9 + cds/intrusive/ellen_bintree_ptb.h | 9 - cds/intrusive/ellen_bintree_rcu.h | 254 ++++++------------ cds/intrusive/impl/ellen_bintree.h | 252 ++++++----------- projects/Win/vc12/cds.vcxproj | 2 +- projects/Win/vc12/cds.vcxproj.filters | 6 +- .../hdr_intrusive_ellen_bintree_pool_ptb.h | 2 +- .../tree/hdr_intrusive_ellen_bintree_ptb.cpp | 2 +- ...hdr_intrusive_ellen_bintree_ptb_member.cpp | 2 +- 11 files changed, 269 insertions(+), 389 deletions(-) create mode 100644 cds/intrusive/ellen_bintree_dhp.h delete mode 100644 cds/intrusive/ellen_bintree_ptb.h diff --git a/cds/intrusive/details/ellen_bintree_base.h b/cds/intrusive/details/ellen_bintree_base.h index 644c5b76..2c32d9ab 100644 --- a/cds/intrusive/details/ellen_bintree_base.h +++ b/cds/intrusive/details/ellen_bintree_base.h @@ -151,7 +151,7 @@ namespace cds { namespace intrusive { /** 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 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() @@ -194,17 +194,17 @@ namespace cds { namespace intrusive { typedef base_node 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 - atomics::atomic m_pLeft ; ///< Left subtree - atomics::atomic m_pRight ; ///< Right subtree - atomics::atomic m_pUpdate ; ///< Update descriptor + key_type m_Key; ///< Regular key + atomics::atomic m_pLeft; ///< Left subtree + atomics::atomic m_pRight; ///< Right subtree + atomics::atomic 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 @@ -228,13 +228,18 @@ namespace cds { namespace intrusive { /** 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 struct node_types { - typedef node leaf_node_type ; ///< Leaf node type - typedef internal_node internal_node_type ; ///< Internal node type - typedef update_desc update_desc_type ; ///< Update descriptor type + typedef node leaf_node_type; ///< Leaf node type + typedef internal_node internal_node_type; ///< Internal node type + typedef update_desc update_desc_type; ///< Update descriptor type }; //@cond @@ -260,8 +265,8 @@ namespace cds { namespace intrusive { /// 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 < typename... Options > struct base_hook: public hook< opt::base_hook_tag, Options... > @@ -273,8 +278,8 @@ namespace cds { namespace intrusive { 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, typename... Options > struct member_hook: public hook< opt::member_hook_tag, Options... > @@ -290,8 +295,8 @@ namespace cds { namespace intrusive { 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 struct traits_hook: public hook< opt::traits_hook_tag, Options... > @@ -422,12 +427,12 @@ namespace cds { namespace intrusive { //@endcond }; - /// Type traits for EllenBinTree class - struct type_traits + /// EllenBinTree traits + struct traits { /// Hook used /** - 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; @@ -449,7 +454,7 @@ namespace cds { namespace intrusive { /** 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". @@ -458,7 +463,7 @@ namespace cds { namespace intrusive { /// 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". @@ -467,33 +472,33 @@ namespace cds { namespace intrusive { /// 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; /// 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; /// 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; /// 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. @@ -502,28 +507,58 @@ namespace cds { namespace intrusive { /// 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; /// 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; /// 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; }; /// Metafunction converting option list to EllenBinTree traits /** - This is a wrapper for cds::opt::make_options< type_traits, Options...> - \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, ellen_bintree::base_hook<> 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 defaulr 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::rcu_check_deadlock - a deadlock checking policy for RCU-based tree, default is \p opt::v::rcu_throw_deadlock */ template struct make_traits { @@ -531,7 +566,7 @@ namespace cds { namespace intrusive { typedef implementation_defined type ; ///< Metafunction result # else typedef typename cds::opt::make_options< - typename cds::opt::find_type_traits< type_traits, Options... >::type + typename cds::opt::find_type_traits< traits, Options... >::type ,Options... >::type type; # endif @@ -676,11 +711,10 @@ namespace cds { namespace intrusive { } // 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 diff --git a/cds/intrusive/details/michael_list_base.h b/cds/intrusive/details/michael_list_base.h index 8972be10..a3f79441 100644 --- a/cds/intrusive/details/michael_list_base.h +++ b/cds/intrusive/details/michael_list_base.h @@ -19,8 +19,8 @@ namespace cds { namespace intrusive { /// Michael's list node /** Template parameters: - - GC - garbage collector - - Tag - a \ref cds_intrusive_hook_tag "tag" + - \p GC - garbage collector + - \p Tag - a \ref cds_intrusive_hook_tag "tag" */ template struct node diff --git a/cds/intrusive/ellen_bintree_dhp.h b/cds/intrusive/ellen_bintree_dhp.h new file mode 100644 index 00000000..51547be3 --- /dev/null +++ b/cds/intrusive/ellen_bintree_dhp.h @@ -0,0 +1,9 @@ +//$$CDS-header$$ + +#ifndef __CDS_INTRUSIVE_ELLEN_BINTREE_DHP_H +#define __CDS_INTRUSIVE_ELLEN_BINTREE_DHP_H + +#include +#include + +#endif // #ifndef __CDS_INTRUSIVE_ELLEN_BINTREE_DHP_H diff --git a/cds/intrusive/ellen_bintree_ptb.h b/cds/intrusive/ellen_bintree_ptb.h deleted file mode 100644 index 88f7393d..00000000 --- a/cds/intrusive/ellen_bintree_ptb.h +++ /dev/null @@ -1,9 +0,0 @@ -//$$CDS-header$$ - -#ifndef __CDS_INTRUSIVE_ELLEN_BINTREE_PTB_H -#define __CDS_INTRUSIVE_ELLEN_BINTREE_PTB_H - -#include -#include - -#endif // #ifndef __CDS_INTRUSIVE_ELLEN_BINTREE_PTB_H diff --git a/cds/intrusive/ellen_bintree_rcu.h b/cds/intrusive/ellen_bintree_rcu.h index 328394be..31611fb4 100644 --- a/cds/intrusive/ellen_bintree_rcu.h +++ b/cds/intrusive/ellen_bintree_rcu.h @@ -4,7 +4,6 @@ #define __CDS_INTRUSIVE_ELLEN_BINTREE_RCU_H #include -#include // ref #include #include #include @@ -65,48 +64,17 @@ namespace cds { namespace intrusive { Template arguments : - \p RCU - one of \ref cds_urcu_gc "RCU type" - \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 ellen_bintree::node - (for ellen_bintree::base_hook) or it must have a member of type ellen_bintree::node - (for ellen_bintree::member_hook). - - \p Traits - type traits. See ellen_bintree::type_traits for explanation. - - It is possible to declare option-based tree with cds::intrusive::ellen_bintree::make_traits metafunction - instead of \p Traits template argument. - Template argument list \p Options of cds::intrusive::ellen_bintree::make_traits metafunction are: - - opt::hook - hook used. Possible values are: ellen_bintree::base_hook, ellen_bintree::member_hook, ellen_bintree::traits_hook. - If the option is not specified, ellen_bintree::base_hook<> is used. - - 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. - - opt::compare - key compare functor. No default functor is provided. - If the option is not specified, \p %opt::less is used. - - opt::less - specifies binary predicate used for key compare. At least \p %opt::compare or \p %opt::less should be defined. - - opt::disposer - the functor used for dispose removed nodes. Default is opt::v::empty_disposer. Due the nature - of GC schema the disposer may be called asynchronously. The disposer is used only for leaf nodes. - - opt::item_counter - the type of item counting feature. Default is \ref atomicity::empty_item_counter that is no item counting. - - opt::memory_model - C++ memory ordering model. Can be opt::v::relaxed_ordering (relaxed memory model, the default) - or opt::v::sequential_consistent (sequentially consisnent memory model). - - ellen_bintree::update_desc_allocator - an allocator of \ref ellen_bintree::update_desc "update descriptors", - default is 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 RCU buffer size (if RCU is buffered). - Therefore, 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. - - opt::node_allocator - the allocator used for internal nodes. Default is \ref CDS_DEFAULT_ALLOCATOR. - - opt::stat - internal statistics. Available types: ellen_bintree::stat, ellen_bintree::empty_stat (the default) - - opt::rcu_check_deadlock - a deadlock checking policy. Default is opt::v::rcu_throw_deadlock + - \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_rcu_less Predicate requirements - opt::less, opt::compare and other predicates using with member fuctions should accept at least parameters + \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 @@ -144,6 +112,7 @@ namespace cds { namespace intrusive { @note Before including you should include appropriate RCU header file, see \ref cds_urcu_gc "RCU type" for list of existing RCU class and corresponding header files. + @anchor cds_intrusive_EllenBinTree_usage Usage Suppose we have the following Foo struct with string key type: @@ -176,7 +145,7 @@ namespace cds { namespace intrusive { Such functor is necessary because the tree internal nodes store the keys. - \p less predicate. We want our set should accept \p std::string and char const * parameters for searching, so our \p less - predicate should be non-trivial, see below. + predicate will not be trivial, see below. - item counting feature: we want our set's \p size() member function returns actual item count. @@ -215,10 +184,10 @@ namespace cds { namespace intrusive { { return v.m_strKey.compare(p) > 0; } }; - // Type traits for our set + // Tree traits for our set // It is necessary to specify only those typedefs that differ from - // cds::intrusive::ellen_bintree::type_traits defaults. - struct set_traits: public cds::intrusive::ellen_bintree::type_traits + // cds::intrusive::ellen_bintree::traits defaults. + struct set_traits: public cds::intrusive::ellen_bintree::traits { typedef cds::intrusive::ellen_bintree::base_hook< cds::opt::gc > > hook; typedef my_key_extractor key_extractor; @@ -235,8 +204,8 @@ namespace cds { namespace intrusive { // ... \endcode - Instead of declaring \p set_traits type traits we can use option-based syntax with \p %make_traits metafunction, - for example: + Instead of declaring \p set_traits type traits we can use option-based syntax with + \p ellen_bintree::make_traits metafunction, for example: \code typedef cds::intrusive::EllenBinTree< gpb_rcu, std::string, Foo, typename cds::intrusive::ellen_bintree::make_traits< @@ -271,7 +240,7 @@ namespace cds { namespace intrusive { struct MyFoo { Foo m_foo; - cds::intrusive:ellen_bintree::node< gpb_rcu > set_hook ; // member hook + cds::intrusive:ellen_bintree::node< gpb_rcu > set_hook; // member hook }; // Key extractor functor @@ -308,8 +277,8 @@ namespace cds { namespace intrusive { { return v.m_foo.m_strKey.compare(p) > 0; } }; - // Type traits for our member-based set - struct member_set_traits: public cds::intrusive::ellen_bintree::type_traits + // Tree traits for our member-based set + struct member_set_traits: public cds::intrusive::ellen_bintree::traits { cds::intrusive::ellen_bintree::member_hook< offsetof(MyFoo, set_hook), cds::opt::gc > > hook; typedef member_key_extractor key_extractor; @@ -346,7 +315,7 @@ namespace cds { namespace intrusive { typedef cds::urcu::gc< cds::urcu::general_buffered<> > gpb_rcu; // Declare tag structs - struct int_tag ; // in key tag + struct int_tag ; // int key tag struct string_tag ; // string key tag // Foo struct is derived from two ellen_bintree::node class @@ -416,7 +385,7 @@ namespace cds { namespace intrusive { }; // Type traits for string-indexed set - struct string_set_traits: public cds::intrusive::ellen_bintree::type_traits + struct string_set_traits: public cds::intrusive::ellen_bintree::traits { typedef cds::intrusive::ellen_bintree::base_hook< cds::opt::gc >, cds::opt::tag< string_tag > > hook; typedef string_key_extractor key_extractor; @@ -425,7 +394,7 @@ namespace cds { namespace intrusive { }; // Type traits for int-indexed set - struct int_set_traits: public cds::intrusive::ellen_bintree::type_traits + struct int_set_traits: public cds::intrusive::ellen_bintree::traits { typedef cds::intrusive::ellen_bintree::base_hook< cds::opt::gc >, cds::opt::tag< int_tag > > hook; typedef int_key_extractor key_extractor; @@ -449,7 +418,7 @@ namespace cds { namespace intrusive { typename Key, typename T, #ifdef CDS_DOXYGEN_INVOKED - class Traits = ellen_bintree::type_traits + class Traits = ellen_bintree::traits #else class Traits #endif @@ -457,34 +426,34 @@ namespace cds { namespace intrusive { class EllenBinTree< cds::urcu::gc, Key, T, Traits > { public: - typedef cds::urcu::gc gc ; ///< RCU Garbage collector - typedef Key key_type ; ///< type of a key 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 options ; ///< Traits template parameter + typedef cds::urcu::gc gc; ///< RCU Garbage collector + typedef Key key_type; ///< type of a key 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 options::hook hook ; ///< hook type - typedef typename hook::node_type node_type ; ///< node type + typedef typename traits::hook hook; ///< hook type + typedef typename hook::node_type node_type; ///< node type - typedef typename options::disposer disposer ; ///< leaf node disposer + typedef typename traits::disposer disposer; ///< leaf node disposer 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::internal_node< key_type, leaf_node > internal_node ; ///< Internal node type - typedef ellen_bintree::update_desc< leaf_node, internal_node> update_desc ; ///< Update descriptor - typedef typename update_desc::update_ptr update_ptr ; ///< Marked pointer to update descriptor + typedef ellen_bintree::base_node< gc > tree_node; ///< Base type of tree node + typedef node_type leaf_node; ///< Leaf node type + typedef ellen_bintree::internal_node< key_type, leaf_node > internal_node; ///< Internal node type + typedef ellen_bintree::update_desc< leaf_node, internal_node> update_desc; ///< Update descriptor + typedef typename update_desc::update_ptr update_ptr; ///< Marked pointer to update descriptor //@endcond public: - typedef cds::urcu::exempt_ptr< gc, value_type, value_type, disposer, void > exempt_ptr ; ///< pointer to extracted node + typedef cds::urcu::exempt_ptr< gc, value_type, value_type, disposer, void > exempt_ptr; ///< pointer to extracted node public: # ifdef CDS_DOXYGEN_INVOKED - typedef implementation_defined key_comparator ; ///< key compare functor based on opt::compare and opt::less option setter. - typedef typename get_node_traits< value_type, node_type, hook>::type node_traits ; ///< Node traits + 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, options >::type key_comparator; + 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 ) @@ -501,14 +470,14 @@ namespace cds { namespace intrusive { }; # endif - typedef typename options::item_counter item_counter; ///< Item counting policy used - typedef typename options::memory_model memory_model; ///< Memory ordering. See cds::opt::memory_model option - typedef typename options::stat stat ; ///< internal statistics type - typedef typename options::rcu_check_deadlock rcu_check_deadlock ; ///< Deadlock checking policy - typedef typename options::key_extractor key_extractor ; ///< key extracting functor + typedef typename traits::item_counter item_counter; ///< Item counting policy used + typedef typename traits::memory_model memory_model; ///< Memory ordering. See cds::opt::memory_model option + typedef typename traits::stat stat; ///< internal statistics type + typedef typename traits::rcu_check_deadlock rcu_check_deadlock; ///< Deadlock checking policy + typedef typename traits::key_extractor key_extractor; ///< key extracting functor - typedef typename options::node_allocator node_allocator ; ///< Internal node allocator - typedef typename options::update_desc_allocator update_desc_allocator ; ///< Update descriptor allocator + typedef typename traits::node_allocator node_allocator; ///< Internal node allocator + typedef typename traits::update_desc_allocator update_desc_allocator; ///< Update descriptor allocator typedef typename gc::scoped_lock rcu_lock; ///< RCU scoped lock @@ -544,13 +513,13 @@ namespace cds { namespace intrusive { protected: //@cond - internal_node m_Root ; ///< Tree root node (key= Infinite2) + internal_node m_Root; ///< Tree root node (key= Infinite2) leaf_node m_LeafInf1; leaf_node m_LeafInf2; //@endcond - item_counter m_ItemCounter ; ///< item counter - mutable stat m_Stat ; ///< internal statistics + item_counter m_ItemCounter; ///< item counter + mutable stat m_Stat; ///< internal statistics protected: //@cond @@ -714,7 +683,7 @@ namespace cds { namespace intrusive { /// Default constructor EllenBinTree() { - static_assert( (!std::is_same< key_extractor, opt::none >::value), "The key extractor option must be specified" ); + static_assert( !std::is_same< key_extractor, opt::none >::value, "The key extractor option must be specified" ); make_empty_tree(); } @@ -753,8 +722,7 @@ namespace cds { namespace intrusive { \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 and may be passed by reference - using \p std::ref + The user-defined functor is called only if the inserting is success. RCU \p synchronize method can be called. RCU should not be locked. */ @@ -821,13 +789,13 @@ namespace cds { namespace intrusive { 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. - You can pass \p func argument by value or by reference using \p std::ref. - RCU \p synchronize method can be called. RCU should not be locked. - Returns std::pair where \p first is \p true if operation is successfull, + Returns std::pair where \p first is \p true if operation is successfull, \p second is \p true if new item has been added or \p false if the item with \p key already is in the tree. + + @warning See \ref cds_intrusive_item_creating "insert item troubleshooting" */ template std::pair ensure( value_type& val, Func func ) @@ -898,18 +866,18 @@ namespace cds { namespace intrusive { /// Deletes the item from the tree /** \anchor cds_intrusive_EllenBinTree_rcu_erase - The function searches an item with key equal to \p val in the tree, + 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 val is not found the function return \p false. + If the item with key equal to \p key is not found the function return \p false. Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type. RCU \p synchronize method can be called. RCU should not be locked. */ template - bool erase( const Q& val ) + bool erase( const Q& key ) { - return erase_( val, node_compare(), + return erase_( key, node_compare(), []( Q const&, leaf_node const& ) -> bool { return true; }, [](value_type const&) {} ); } @@ -923,7 +891,7 @@ namespace cds { namespace intrusive { \p pred must imply the same element order as the comparator used for building the tree. */ template - bool erase_with( const Q& val, Less pred ) + bool erase_with( const Q& key, Less pred ) { typedef ellen_bintree::details::compare< key_type, @@ -932,14 +900,14 @@ namespace cds { namespace intrusive { node_traits > compare_functor; - return erase_( val, 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_rcu_erase_func - The function searches an item with key equal to \p val in the tree, + 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. @@ -952,16 +920,16 @@ namespace cds { namespace intrusive { \endcode The functor can be passed by reference with boost:ref - If the item with key equal to \p val is not found the function return \p false. + If the item with key equal to \p key is not found the function return \p false. Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type. RCU \p synchronize method can be called. RCU should not be locked. */ template - bool erase( Q const& val, Func f ) + bool erase( Q const& key, Func f ) { - return erase_( val, node_compare(), + return erase_( key, node_compare(), []( Q const&, leaf_node const& ) -> bool { return true; }, f ); } @@ -975,7 +943,7 @@ namespace cds { namespace intrusive { \p pred must imply the same element order as the comparator used for building the tree. */ template - bool erase_with( Q const& val, Less pred, Func f ) + bool erase_with( Q const& key, Less pred, Func f ) { typedef ellen_bintree::details::compare< key_type, @@ -984,7 +952,7 @@ namespace cds { namespace intrusive { node_traits > compare_functor; - return erase_( val, compare_functor(), + return erase_( key, compare_functor(), []( Q const&, leaf_node const& ) -> bool { return true; }, f ); } @@ -1058,14 +1026,14 @@ namespace cds { namespace intrusive { \p pred must imply the same element order as the comparator used for building the tree. */ template - bool extract_with( exempt_ptr& dest, Q const& val, Less pred ) + bool extract_with( exempt_ptr& dest, Q const& key, Less pred ) { - return extract_with_( dest, val, pred ); + return extract_with_( dest, key, pred ); } - /// Finds the key \p val + /// Finds the key \p key /** @anchor cds_intrusive_EllenBinTree_rcu_find_val - The function searches the item with key equal to \p val + The function searches the item with key equal to \p key and returns \p true if it is found, and \p false otherwise. Note the hash functor specified for class \p Traits template parameter @@ -1074,11 +1042,11 @@ namespace cds { namespace intrusive { The function applies RCU lock internally. */ template - bool find( Q const& val ) const + bool find( Q const& key ) const { rcu_lock l; search_result res; - if ( search( res, val, node_compare() )) { + if ( search( res, key, node_compare() )) { m_Stat.onFindSuccess(); return true; } @@ -1087,7 +1055,7 @@ namespace cds { namespace intrusive { return false; } - /// Finds the key \p val with comparing functor \p pred + /// Finds the key \p key with comparing functor \p pred /** The function is an analog of \ref cds_intrusive_EllenBinTree_rcu_find_val "find(Q const&)" but \p pred is used for key compare. @@ -1097,7 +1065,7 @@ namespace cds { namespace intrusive { \p pred should accept arguments of type \p Q, \p key_type, \p value_type in any combination. */ template - bool find_with( Q const& val, Less pred ) const + bool find_with( Q const& key, Less pred ) const { typedef ellen_bintree::details::compare< key_type, @@ -1108,7 +1076,7 @@ namespace cds { namespace intrusive { rcu_lock l; search_result res; - if ( search( res, val, compare_functor() )) { + if ( search( res, key, compare_functor() )) { m_Stat.onFindSuccess(); return true; } @@ -1116,38 +1084,33 @@ namespace cds { namespace intrusive { return false; } - /// Finds the key \p val + /// Finds the key \p key /** @anchor cds_intrusive_EllenBinTree_rcu_find_func - The function searches the item with key equal to \p val and calls the functor \p f for item found. + 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& val ); + void operator()( value_type& item, Q& key ); }; \endcode - where \p item is the item found, \p val is the find function argument. - - You can pass \p f argument by value or by reference using \p std::ref. + where \p item is the item found, \p key is the find 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 \p val argument is non-const since it can be used as \p f functor destination i.e., the functor - can modify both arguments. - The function applies RCU lock internally. - The function returns \p true if \p val is found, \p false otherwise. + The function returns \p true if \p key is found, \p false otherwise. */ template - bool find( Q& val, Func f ) const + bool find( Q& key, Func f ) const { - return find_( val, f ); + return find_( key, f ); } - /// Finds the key \p val with comparing functor \p pred + /// Finds the key \p key with comparing functor \p pred /** The function is an analog of \ref cds_intrusive_EllenBinTree_rcu_find_func "find(Q&, Func)" but \p pred is used for key comparison. @@ -1156,51 +1119,9 @@ namespace cds { namespace intrusive { \p pred must imply the same element order as the comparator used for building the tree. */ template - bool find_with( Q& val, Less pred, Func f ) const - { - return find_with_( val, pred, f ); - } - - /// Finds the key \p val - /** @anchor cds_intrusive_EllenBinTree_rcu_find_cfunc - The function searches the item with key equal to \p val 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 const& val ); - }; - \endcode - where \p item is the item found, \p val is the find function argument. - - You can pass \p f argument by value or by reference using \p std::ref. - - 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 applies RCU lock internally. - - The function returns \p true if \p val is found, \p false otherwise. - */ - template - bool find( Q const& val, Func f ) const - { - return find_( val, f ); - } - - /// Finds the key \p val with comparing functor \p pred - /** - The function is an analog of \ref cds_intrusive_EllenBinTree_rcu_find_cfunc "find(Q const&, Func)" - but \p pred is used for key compare. - \p Less functor has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_rcu_less - "Predicate requirements". - \p pred must imply the same element order as the comparator used for building the tree. - */ - template - bool find_with( Q const& val, Less pred, Func f ) const + bool find_with( Q& key, Less pred, Func f ) const { - return find_with_( val, pred, f ); + return find_with_( key, pred, f ); } /// Finds \p key and return the item found @@ -1245,7 +1166,7 @@ namespace cds { namespace intrusive { return m_Root.m_pLeft.load( memory_model::memory_order_relaxed )->is_leaf(); } - /// Clears the tree (thread safe, non-atomic) + /// 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 @@ -1309,9 +1230,10 @@ namespace cds { namespace intrusive { 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 atomicity::empty_item_counter this function always returns 0. - Therefore, the function is not suitable for checking the tree emptiness, use \ref empty - member function for this purpose. + 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 that. */ size_t size() const { diff --git a/cds/intrusive/impl/ellen_bintree.h b/cds/intrusive/impl/ellen_bintree.h index 407b2e18..577f6c86 100644 --- a/cds/intrusive/impl/ellen_bintree.h +++ b/cds/intrusive/impl/ellen_bintree.h @@ -4,7 +4,6 @@ #define __CDS_INTRUSIVE_IMPL_ELLEN_BINTREE_H #include -#include // ref #include #include #include @@ -21,16 +20,16 @@ namespace cds { namespace intrusive { Source: - [2010] F.Ellen, P.Fatourou, E.Ruppert, F.van Breugel "Non-blocking Binary Search Tree" - %EllenBinTree is an unbalanced leaf-oriented binary search tree that implements the set + %EllenBinTree is an unbalanced leaf-oriented binary search tree that implements the set 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 + 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 + Due to \p extract_min() and \p extract_max() member functions the \p %EllenBinTree can act as a priority queue. In this case you should provide unique compound key, for example, the priority value plus some uniformly distributed random value. @@ -44,56 +43,24 @@ namespace cds { namespace intrusive { @note Do not include header file explicitly. There are header file for each GC type: - - - for Hazard Pointer GC cds::gc::HP - - - for Pass-the-Buck GC cds::gc::PTB - - - for RCU GC - (see \ref cds_intrusive_EllenBinTree_rcu "RCU-based EllenBinTree") + - - for Hazard Pointer GC \p cds::gc::HP + - - for Pass-the-Buck GC \p cds::gc::DHP + - - for RCU (see \ref cds_intrusive_EllenBinTree_rcu "RCU-based EllenBinTree") Template arguments : - - \p GC - garbage collector used, possible types are cds::gc::HP, cds::gc::PTB. - Note that cds::gc::HRC is not supported. + - \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 ellen_bintree::node - (for ellen_bintree::base_hook) or it must have a member of type ellen_bintree::node - (for ellen_bintree::member_hook). - - \p Traits - type traits. See ellen_bintree::type_traits for explanation. - - It is possible to declare option-based tree with cds::intrusive::ellen_bintree::make_traits metafunction - instead of \p Traits template argument. - Template argument list \p Options of cds::intrusive::ellen_bintree::make_traits metafunction are: - - opt::hook - hook used. Possible values are: ellen_bintree::base_hook, ellen_bintree::member_hook, ellen_bintree::traits_hook. - If the option is not specified, ellen_bintree::base_hook<> is used. - - 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. - - opt::compare - key compare functor. No default functor is provided. - If the option is not specified, \p %opt::less is used. - - opt::less - specifies binary predicate used for key compare. At least \p %opt::compare or \p %opt::less should be defined. - - opt::disposer - the functor used for dispose removed nodes. Default is opt::v::empty_disposer. Due the nature - of GC schema the disposer may be called asynchronously. The disposer is used only for leaf nodes. - - opt::item_counter - the type of item counting feature. Default is \ref atomicity::empty_item_counter that means no item counting. - - opt::memory_model - C++ memory ordering model. Can be opt::v::relaxed_ordering (relaxed memory model, the default) - or opt::v::sequential_consistent (sequentially consisnent memory model). - - ellen_bintree::update_desc_allocator - an allocator of \ref ellen_bintree::update_desc "update descriptors", - default is 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. - - opt::node_allocator - the allocator used for internal nodes. Default is \ref CDS_DEFAULT_ALLOCATOR. - - opt::stat - internal statistics. Available types: ellen_bintree::stat, ellen_bintree::empty_stat (the default) + - \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 Predicate requirements - opt::less, opt::compare and other predicates using with member fuctions should accept at least parameters + \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 @@ -127,12 +94,14 @@ namespace cds { namespace intrusive { { 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::type_traits + class Traits = ellen_bintree::traits #else class Traits #endif @@ -140,33 +109,33 @@ namespace cds { namespace intrusive { class EllenBinTree { public: - typedef GC gc ; ///< Garbage collector used - typedef Key key_type ; ///< type of a key 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 options ; ///< Traits template parameter + 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 options::hook hook ; ///< hook type - typedef typename hook::node_type node_type ; ///< node type - typedef typename options::disposer disposer ; ///< leaf node disposer + 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 cds::gc::guarded_ptr< gc, 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::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 + 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 opt::compare and opt::less option setter. - typedef typename get_node_traits< value_type, node_type, hook>::type node_traits ; ///< Node traits + 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, options >::type key_comparator; + 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 ) @@ -183,13 +152,13 @@ namespace cds { namespace intrusive { }; # endif - typedef typename options::item_counter item_counter; ///< Item counting policy used - typedef typename options::memory_model memory_model; ///< Memory ordering. See cds::opt::memory_model option - typedef typename options::stat stat ; ///< internal statistics type - typedef typename options::key_extractor key_extractor ; ///< key extracting functor + 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 options::node_allocator node_allocator ; ///< Internal node allocator - typedef typename options::update_desc_allocator update_desc_allocator ; ///< Update descriptor allocator + typedef typename traits::node_allocator node_allocator; ///< Allocator for internal node + typedef typename traits::update_desc_allocator update_desc_allocator; ///< Update descriptor allocator protected: //@cond @@ -221,13 +190,13 @@ namespace cds { namespace intrusive { 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 + 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 ) + ,pParent( nullptr ) + ,pLeaf( nullptr ) ,bRightLeaf( false ) ,bRightParent( false ) {} @@ -241,13 +210,13 @@ namespace cds { namespace intrusive { 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) + 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 + item_counter m_ItemCounter; ///< item counter + mutable stat m_Stat; ///< internal statistics protected: //@cond @@ -324,7 +293,7 @@ namespace cds { namespace intrusive { /// Default constructor EllenBinTree() { - static_assert( (!std::is_same< key_extractor, opt::none >::value), "The key extractor option must be specified" ); + static_assert( !std::is_same< key_extractor, opt::none >::value, "The key extractor option must be specified" ); make_empty_tree(); } @@ -361,8 +330,7 @@ namespace cds { namespace intrusive { \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 and may be passed by reference - using \p std::ref + The user-defined functor is called only if the inserting is success. */ template bool insert( value_type& val, Func f ) @@ -413,19 +381,19 @@ namespace cds { namespace intrusive { \endcode with arguments: - \p bNew - \p true if the item has been inserted, \p false otherwise - - \p item - item of the tree - - \p val - argument \p val passed into the \p ensure function + - \p item - an item of the tree + - \p val - the argument \p val passed to the \p ensure 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. - You can pass \p func argument by value or by reference using \p std::ref. - Returns std::pair where \p first is \p true if operation is successfull, \p second is \p true if new item has been added or \p false if the item with \p key already is in the tree. + + @warning See \ref cds_intrusive_item_creating "insert item troubleshooting" */ template std::pair ensure( value_type& val, Func func ) @@ -471,10 +439,9 @@ namespace cds { namespace intrusive { Difference between \ref erase and \p unlink functions: \p erase finds a key and deletes the item found. \p unlink finds an item by key and deletes it - only if \p val is an item of the tree, i.e. the pointer to item found - is equal to &val . + only if \p val is a node, i.e. the pointer to item found is equal to &val . - The \ref disposer specified in \p Traits class template parameter is called + 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. @@ -488,16 +455,16 @@ namespace cds { namespace intrusive { /// Deletes the item from the tree /** \anchor cds_intrusive_EllenBinTree_erase - The function searches an item with key equal to \p val in the tree, + 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 val is not found the function return \p false. + If the item with key equal to \p key is not found the function return \p false. Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type. */ template - bool erase( const Q& val ) + bool erase( const Q& key ) { - return erase_( val, node_compare(), + return erase_( key, node_compare(), []( Q const&, leaf_node const& ) -> bool { return true; }, [](value_type const&) {} ); } @@ -511,7 +478,7 @@ namespace cds { namespace intrusive { \p pred must imply the same element order as the comparator used for building the tree. */ template - bool erase_with( const Q& val, Less pred ) + bool erase_with( const Q& key, Less pred ) { typedef ellen_bintree::details::compare< key_type, @@ -520,14 +487,14 @@ namespace cds { namespace intrusive { node_traits > compare_functor; - return erase_( val, 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 val in the tree, + 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. @@ -540,14 +507,14 @@ namespace cds { namespace intrusive { \endcode The functor can be passed by reference with boost:ref - If the item with key equal to \p val is not found the function return \p false. + If the item with key equal to \p key is not found the function return \p false. Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type. */ template - bool erase( Q const& val, Func f ) + bool erase( Q const& key, Func f ) { - return erase_( val, node_compare(), + return erase_( key, node_compare(), []( Q const&, leaf_node const& ) -> bool { return true; }, f ); } @@ -561,7 +528,7 @@ namespace cds { namespace intrusive { \p pred must imply the same element order as the comparator used for building the tree. */ template - bool erase_with( Q const& val, Less pred, Func f ) + bool erase_with( Q const& key, Less pred, Func f ) { typedef ellen_bintree::details::compare< key_type, @@ -570,7 +537,7 @@ namespace cds { namespace intrusive { node_traits > compare_functor; - return erase_( val, compare_functor(), + return erase_( key, compare_functor(), []( Q const&, leaf_node const& ) -> bool { return true; }, f ); } @@ -643,19 +610,19 @@ namespace cds { namespace intrusive { return extract_with_( dest.guard(), key, pred ); } - /// Finds the key \p val + /// Finds the key \p key /** @anchor cds_intrusive_EllenBinTree_find_val - The function searches the item with key equal to \p val + The function searches the item with key equal to \p key and returns \p true if it is found, and \p false otherwise. Note the hash functor specified for class \p Traits template parameter should accept a parameter of type \p Q that can be not the same as \p value_type. */ template - bool find( Q const& val ) const + bool find( Q const& key ) const { search_result res; - if ( search( res, val, node_compare() )) { + if ( search( res, key, node_compare() )) { m_Stat.onFindSuccess(); return true; } @@ -664,7 +631,7 @@ namespace cds { namespace intrusive { return false; } - /// Finds the key \p val with comparing functor \p pred + /// Finds the key \p key with comparing functor \p pred /** The function is an analog of \ref cds_intrusive_EllenBinTree_find_val "find(Q const&)" but \p pred is used for key compare. @@ -674,7 +641,7 @@ namespace cds { namespace intrusive { \p pred should accept arguments of type \p Q, \p key_type, \p value_type in any combination. */ template - bool find_with( Q const& val, Less pred ) const + bool find_with( Q const& key, Less pred ) const { typedef ellen_bintree::details::compare< key_type, @@ -684,7 +651,7 @@ namespace cds { namespace intrusive { > compare_functor; search_result res; - if ( search( res, val, compare_functor() )) { + if ( search( res, key, compare_functor() )) { m_Stat.onFindSuccess(); return true; } @@ -692,16 +659,16 @@ namespace cds { namespace intrusive { return false; } - /// Finds the key \p val + /// Finds the key \p key /** @anchor cds_intrusive_EllenBinTree_find_func - The function searches the item with key equal to \p val and calls the functor \p f for item found. + 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& val ); + void operator()( value_type& item, Q& key ); }; \endcode - where \p item is the item found, \p val is the find function argument. + where \p item is the item found, \p key is the find function argument. You can pass \p f argument by value or by reference using \p std::ref. @@ -710,18 +677,15 @@ namespace cds { namespace intrusive { 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 \p val argument is non-const since it can be used as \p f functor destination i.e., the functor - can modify both arguments. - - The function returns \p true if \p val is found, \p false otherwise. + The function returns \p true if \p key is found, \p false otherwise. */ template - bool find( Q& val, Func f ) const + bool find( Q& key, Func f ) const { - return find_( val, f ); + return find_( key, f ); } - /// Finds the key \p val with comparing functor \p pred + /// 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. @@ -730,49 +694,9 @@ namespace cds { namespace intrusive { \p pred must imply the same element order as the comparator used for building the tree. */ template - bool find_with( Q& val, Less pred, Func f ) const - { - return find_with_( val, pred, f ); - } - - /// Finds the key \p val - /** @anchor cds_intrusive_EllenBinTree_find_cfunc - The function searches the item with key equal to \p val 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 const& val ); - }; - \endcode - where \p item is the item found, \p val is the find function argument. - - You can pass \p f argument by value or by reference using \p std::ref. - - 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 val is found, \p false otherwise. - */ - template - bool find( Q const& val, Func f ) const - { - return find_( val, f ); - } - - /// Finds the key \p val with comparing functor \p pred - /** - The function is an analog of \ref cds_intrusive_EllenBinTree_find_cfunc "find(Q const&, Func)" - but \p pred is used for key compare. - \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 - bool find_with( Q const& val, Less pred, Func f ) const + bool find_with( Q& key, Less pred, Func f ) const { - return find_with_( val, pred, f ); + return find_with_( key, pred, f ); } /// Finds \p key and returns the item found @@ -810,7 +734,7 @@ namespace cds { namespace intrusive { return m_Root.m_pLeft.load( memory_model::memory_order_relaxed )->is_leaf(); } - /// Clears the tree (thread safe, non-atomic) + /// 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 @@ -821,7 +745,7 @@ namespace cds { namespace intrusive { \endcode the assertion could be raised. - For each leaf the \ref disposer will be called after unlinking. + For each leaf the \p disposer will be called after unlinking. */ void clear() { @@ -869,8 +793,8 @@ namespace cds { namespace intrusive { 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 atomicity::empty_item_counter this function always returns 0. - Therefore, the function is not suitable for checking the tree emptiness, use \ref empty + 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 diff --git a/projects/Win/vc12/cds.vcxproj b/projects/Win/vc12/cds.vcxproj index 391591e1..b1d4c659 100644 --- a/projects/Win/vc12/cds.vcxproj +++ b/projects/Win/vc12/cds.vcxproj @@ -757,8 +757,8 @@ + - diff --git a/projects/Win/vc12/cds.vcxproj.filters b/projects/Win/vc12/cds.vcxproj.filters index bed704df..9e873d16 100644 --- a/projects/Win/vc12/cds.vcxproj.filters +++ b/projects/Win/vc12/cds.vcxproj.filters @@ -1019,9 +1019,6 @@ Header Files\cds\intrusive - - Header Files\cds\intrusive - Header Files\cds\intrusive @@ -1232,5 +1229,8 @@ Header Files\cds\container + + Header Files\cds\intrusive + \ No newline at end of file diff --git a/tests/test-hdr/tree/hdr_intrusive_ellen_bintree_pool_ptb.h b/tests/test-hdr/tree/hdr_intrusive_ellen_bintree_pool_ptb.h index 05d2e9f6..17fb5c1c 100644 --- a/tests/test-hdr/tree/hdr_intrusive_ellen_bintree_pool_ptb.h +++ b/tests/test-hdr/tree/hdr_intrusive_ellen_bintree_pool_ptb.h @@ -4,7 +4,7 @@ #define CDSHDRTEST_INTRUSIVE_ELLEN_BINTREE_POOL_PTB_H #include "tree/hdr_intrusive_bintree.h" -#include +#include #include #include diff --git a/tests/test-hdr/tree/hdr_intrusive_ellen_bintree_ptb.cpp b/tests/test-hdr/tree/hdr_intrusive_ellen_bintree_ptb.cpp index f30e152e..3f95b5cc 100644 --- a/tests/test-hdr/tree/hdr_intrusive_ellen_bintree_ptb.cpp +++ b/tests/test-hdr/tree/hdr_intrusive_ellen_bintree_ptb.cpp @@ -1,7 +1,7 @@ //$$CDS-header$$ #include "tree/hdr_intrusive_bintree.h" -#include +#include #include "tree/hdr_intrusive_ellen_bintree_pool_ptb.h" #include "unit/print_ellenbintree_stat.h" diff --git a/tests/test-hdr/tree/hdr_intrusive_ellen_bintree_ptb_member.cpp b/tests/test-hdr/tree/hdr_intrusive_ellen_bintree_ptb_member.cpp index 0fd41f65..e0ac4f7f 100644 --- a/tests/test-hdr/tree/hdr_intrusive_ellen_bintree_ptb_member.cpp +++ b/tests/test-hdr/tree/hdr_intrusive_ellen_bintree_ptb_member.cpp @@ -1,7 +1,7 @@ //$$CDS-header$$ #include "tree/hdr_intrusive_bintree.h" -#include +#include #include "tree/hdr_intrusive_ellen_bintree_pool_ptb.h" #include "unit/print_ellenbintree_stat.h" -- 2.34.1