X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=cds%2Fcontainer%2Fdetails%2Fellen_bintree_base.h;h=91e2e2b25e83f3dab55f4615f8b8b917ada8c359;hb=dd527e913731ce28ff1a6cea10bdabfd507ef856;hp=ca6d790817bc01987285442e2886496e7f7b3a12;hpb=bd75ca75fd01e1d37d315fd5d873b4c13b85f634;p=libcds.git diff --git a/cds/container/details/ellen_bintree_base.h b/cds/container/details/ellen_bintree_base.h index ca6d7908..91e2e2b2 100644 --- a/cds/container/details/ellen_bintree_base.h +++ b/cds/container/details/ellen_bintree_base.h @@ -1,7 +1,35 @@ -//$$CDS-header$$ +/* + This file is a part of libcds - Concurrent Data Structures library -#ifndef __CDS_CONTAINER_DETAILS_ELLEN_BINTREE_BASE_H -#define __CDS_CONTAINER_DETAILS_ELLEN_BINTREE_BASE_H + (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2017 + + Source code repo: http://github.com/khizmax/libcds/ + Download: http://sourceforge.net/projects/libcds/files/ + + Redistribution and use in source and binary forms, with or without + modification, are permitted provided that the following conditions are met: + + * Redistributions of source code must retain the above copyright notice, this + list of conditions and the following disclaimer. + + * Redistributions in binary form must reproduce the above copyright notice, + this list of conditions and the following disclaimer in the documentation + and/or other materials provided with the distribution. + + THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" + AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE + FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR + SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER + CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, + OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. +*/ + +#ifndef CDSLIB_CONTAINER_DETAILS_ELLEN_BINTREE_BASE_H +#define CDSLIB_CONTAINER_DETAILS_ELLEN_BINTREE_BASE_H #include #include @@ -14,34 +42,31 @@ namespace cds { namespace container { /** @ingroup cds_nonintrusive_helper */ namespace ellen_bintree { - #ifdef CDS_DOXYGEN_INVOKED - /// Typedef for cds::intrusive::ellen_bintree::update_desc + /// Typedef for \p cds::intrusive::ellen_bintree::update_desc typedef cds::intrusive::ellen_bintree::update_desc update_desc; - /// Typedef for cds::intrusive::ellen_bintree::internal_node + /// Typedef for \p cds::intrusive::ellen_bintree::internal_node typedef cds::intrusive::ellen_bintree::internal_node internal_node; - /// Typedef for cds::intrusive::ellen_bintree::key_extractor + /// Typedef for \p cds::intrusive::ellen_bintree::key_extractor typedef cds::intrusive::ellen_bintree::key_extractor key_extractor; - /// Typedef for cds::intrusive::ellen_bintree::update_desc_allocator + /// Typedef for \p cds::intrusive::ellen_bintree::update_desc_allocator typedef cds::intrusive::ellen_bintree::update_desc_allocator update_desc_allocator; - - /// Typedef for cds::intrusive::ellen_bintree::stat - typedef cds::intrusive::ellen_bintree::stat stat; - - /// Typedef for cds::intrusive::ellen_bintree::empty_stat - typedef cds::intrusive::ellen_bintree::empty_stat empty_stat; #else using cds::intrusive::ellen_bintree::update_desc; using cds::intrusive::ellen_bintree::internal_node; using cds::intrusive::ellen_bintree::key_extractor; using cds::intrusive::ellen_bintree::update_desc_allocator; - using cds::intrusive::ellen_bintree::stat; - using cds::intrusive::ellen_bintree::empty_stat; using cds::intrusive::ellen_bintree::node_types; #endif + /// EllenBinTree internal statistics + template ::event_counter > + using stat = cds::intrusive::ellen_bintree::stat< Counter >; + + /// EllenBinTree empty internal statistics + typedef cds::intrusive::ellen_bintree::empty_stat empty_stat; /// EllenBinTree leaf node template @@ -63,14 +88,14 @@ namespace cds { namespace container { /// Copy constructor template - node( Args const&... args) + node( Args const&... args ) : m_Value( args... ) {} /// Move constructor template - node( Args&&... args) - : m_Value( std::forward(args)... ) + node( Args&&... args ) + : m_Value( std::forward( args )... ) {} }; @@ -87,30 +112,30 @@ namespace cds { namespace container { /// Initializes key field, value if default-constructed template map_node( K const& key ) - : m_Value( std::make_pair( key_type(key), mapped_type() )) + : m_Value( std::make_pair( key_type(key), mapped_type())) {} /// Initializes key and value fields template map_node( K const& key, Q const& v ) - : m_Value( std::make_pair(key_type(key), mapped_type(v) )) + : m_Value( std::make_pair(key_type(key), mapped_type(v))) {} }; - /// Type traits for EllenBinTreeSet, EllenBinTreeMap and EllenBinTreePriorityQueue - struct type_traits + /// Type traits for \p EllenBinTreeSet and \p EllenBinTreeMap + struct traits { - /// Key extracting functor (only for EllenBinTreeSet) + /// Key extracting functor (only for \p EllenBinTreeSet) /** - You should explicit define a valid functor. - The functor has the following prototype: + This is mandatory functor for \p %EllenBinTreeSet. + It 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. + The functor is used to initialize internal nodes of \p %EllenBinTreeSet */ typedef opt::none key_extractor; @@ -118,7 +143,7 @@ namespace cds { namespace container { /** 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_container_EllenBinTreeSet_rcu_less "predicate requirements". @@ -127,7 +152,7 @@ namespace cds { namespace container { /// Specifies binary predicate used for key compare. /** - See cds::opt::less option description for predicate interface. + See \p cds::opt::less option description. You should provide \p compare or \p less functor. See \ref cds_container_EllenBinTreeSet_rcu_less "predicate requirements". @@ -136,27 +161,27 @@ namespace cds { namespace container { /// 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 a small number 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 not dependent on the type of data stored in the tree so single free-list object can be used for several \p EllenBinTree object. @@ -165,7 +190,7 @@ namespace cds { namespace container { /// 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; @@ -177,21 +202,25 @@ namespace cds { namespace container { /// Internal statistics /** - Possible types: ellen_bintree::empty_stat (the default), 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; + /// Back-off strategy + typedef cds::backoff::empty back_off; + /// RCU deadlock checking policy (only for RCU-based EllenBinTreeXXX classes) /** - 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; - /// Key copy policy (for EllenBinTreeMap) + /// Key copy policy (for \p EllenBinTreeMap) /** The key copy policy defines a functor to copy leaf node's key to internal node. - This policy is used only in EllenBinTreeMap. By default, assignment operator is used. + This policy is used only in \p EllenBinTreeMap. + By default, assignment operator is used. The copy functor interface is: \code @@ -204,10 +233,40 @@ namespace cds { namespace container { }; - /// Metafunction converting option list to EllenBinTreeSet traits + /// Metafunction converting option list to \p EllenBinTreeSet traits /** - This is a wrapper for cds::opt::make_options< type_traits, Options...> - \p Options list see \ref cds_container_EllenBinTreeSet "EllenBinTreeSet". + \p Options are: + - \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::item_counter - the type of item counter, default 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 opt::allocator - the allocator for \ref ellen_bintree::node "leaf nodes" which contains data. + Default is \ref CDS_DEFAULT_ALLOCATOR. + - \p opt::node_allocator - the allocator for internal nodes. Default is \ref CDS_DEFAULT_ALLOCATOR. + - \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 a relatively small number limited the number of threads + working with the tree and RCU buffer size. + Therefore, a bounded lock-free container like \p cds::container::VyukovMPMCCycleQueue is good choice for the free-list + of update descriptors, see \p cds::memory::vyukov_queue_pool free-list implementation. + Also notice that size of update descriptor is not dependent on the type of data + stored in the tree so single free-list object can be used for several EllenBinTree-based object. + - \p opt::stat - internal statistics, by default disabled (\p ellen_bintree::empty_stat). To enable + it use \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, only for RCU-based tree. + Default is \p opt::v::rcu_throw_deadlock. */ template struct make_set_traits { @@ -215,16 +274,47 @@ namespace cds { namespace container { 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 }; - /// Metafunction converting option list to EllenBinTreeMap traits + /// Metafunction converting option list to \p EllenBinTreeMap traits /** - This is a wrapper for cds::opt::make_options< type_traits, Options...> - \p Options list see \ref cds_container_EllenBinTreeMap "EllenBinTreeMap". + \p Options are: + - \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::item_counter - the type of item counter, default is disabled (\p atomicity::empty_item_counter). + To enable it use \p atomicity::item_counter + - 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 opt::allocator - the allocator used for \ref ellen_bintree::map_node "leaf nodes" which contains data. + Default is \ref CDS_DEFAULT_ALLOCATOR. + - \p opt::node_allocator - the allocator used for \ref ellen_bintree::internal_node "internal nodes". + Default is \ref CDS_DEFAULT_ALLOCATOR. + - \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 a relatively small number limited the number of threads + working with the tree and RCU buffer size. + Therefore, a bounded lock-free container like \p cds::container::VyukovMPMCCycleQueue is good choice for the free-list + of update descriptors, see \p cds::memory::vyukov_queue_pool free-list implementation. + Also notice that size of update descriptor is not dependent on the type of data + stored in the tree so single free-list object can be used for several EllenBinTree-based object. + - \p opt::stat - internal statistics, by default disabled (\p ellen_bintree::empty_stat). To enable + it use \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, only for RCU-based tree. Default is \p opt::v::rcu_throw_deadlock + - opt::copy_policy - key copying policy defines a functor to copy leaf node's key to internal node. + By default, assignment operator is used. + The copy functor interface is: + \code + struct copy_functor { + void operator()( Key& dest, Key const& src ); + }; + \endcode */ template struct make_map_traits { @@ -232,7 +322,7 @@ namespace cds { namespace container { 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 @@ -247,7 +337,7 @@ namespace cds { namespace container { typedef GC gc; typedef Key key_type; typedef T value_type; - typedef Traits original_type_traits; + typedef Traits original_traits; typedef node< gc, value_type > leaf_node; @@ -255,7 +345,7 @@ namespace cds { namespace container { { void operator()( key_type& dest, leaf_node const& src ) const { - typename original_type_traits::key_extractor()( dest, src.m_Value ); + typename original_traits::key_extractor()( dest, src.m_Value ); } }; @@ -267,9 +357,9 @@ namespace cds { namespace container { } }; - typedef typename cds::opt::details::make_comparator< value_type, original_type_traits, false >::type key_comparator; + typedef typename cds::opt::details::make_comparator< value_type, original_traits, false >::type key_comparator; - typedef cds::details::Allocator< leaf_node, typename original_type_traits::allocator> cxx_leaf_node_allocator; + typedef cds::details::Allocator< leaf_node, typename original_traits::allocator> cxx_leaf_node_allocator; struct leaf_deallocator { void operator()( leaf_node * p ) const @@ -278,16 +368,16 @@ namespace cds { namespace container { } }; - struct intrusive_type_traits: public original_type_traits + struct intrusive_traits: public original_traits { - typedef cds::intrusive::ellen_bintree::base_hook< cds::opt::gc< gc > > hook; + typedef cds::intrusive::ellen_bintree::base_hook< cds::opt::gc< gc >> hook; typedef intrusive_key_extractor key_extractor; typedef leaf_deallocator disposer; typedef cds::details::compare_wrapper< leaf_node, key_comparator, value_accessor > compare; }; // Metafunction result - typedef cds::intrusive::EllenBinTree< gc, key_type, leaf_node, intrusive_type_traits > type; + typedef cds::intrusive::EllenBinTree< gc, key_type, leaf_node, intrusive_traits > type; }; template < class GC, typename Key, typename T, class Traits> @@ -299,7 +389,7 @@ namespace cds { namespace container { typedef map_node< gc, key_type, mapped_type > leaf_node; typedef typename leaf_node::value_type value_type; - typedef Traits original_type_traits; + typedef Traits original_traits; struct assignment_copy_policy { void operator()( key_type& dest, key_type const& src ) @@ -308,9 +398,9 @@ namespace cds { namespace container { } }; typedef typename std::conditional< - std::is_same< typename original_type_traits::copy_policy, opt::none >::value, + std::is_same< typename original_traits::copy_policy, opt::none >::value, assignment_copy_policy, - typename original_type_traits::copy_policy + typename original_traits::copy_policy >::type copy_policy; struct intrusive_key_extractor @@ -329,9 +419,9 @@ namespace cds { namespace container { } }; - typedef typename cds::opt::details::make_comparator< key_type, original_type_traits, false >::type key_comparator; + typedef typename cds::opt::details::make_comparator< key_type, original_traits, false >::type key_comparator; - typedef cds::details::Allocator< leaf_node, typename original_type_traits::allocator> cxx_leaf_node_allocator; + typedef cds::details::Allocator< leaf_node, typename original_traits::allocator> cxx_leaf_node_allocator; struct leaf_deallocator { void operator()( leaf_node * p ) const @@ -340,7 +430,7 @@ namespace cds { namespace container { } }; - struct intrusive_type_traits: public original_type_traits + struct intrusive_traits: public original_traits { typedef cds::intrusive::ellen_bintree::base_hook< cds::opt::gc< gc > > hook; typedef intrusive_key_extractor key_extractor; @@ -349,7 +439,7 @@ namespace cds { namespace container { }; // Metafunction result - typedef cds::intrusive::EllenBinTree< gc, key_type, leaf_node, intrusive_type_traits > type; + typedef cds::intrusive::EllenBinTree< gc, key_type, leaf_node, intrusive_traits > type; }; } // namespace details @@ -358,13 +448,13 @@ namespace cds { namespace container { // Forward declarations //@cond - 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 EllenBinTreeSet; - 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 EllenBinTreeMap; //@endcond }} // namespace cds::container -#endif // #ifndef __CDS_CONTAINER_DETAILS_ELLEN_BINTREE_BASE_H +#endif // #ifndef CDSLIB_CONTAINER_DETAILS_ELLEN_BINTREE_BASE_H