cds/container/details/ellen_bintree_base.h

   1 //$$CDS-header$$
   2
   3 #ifndef __CDS_CONTAINER_DETAILS_ELLEN_BINTREE_BASE_H
   4 #define __CDS_CONTAINER_DETAILS_ELLEN_BINTREE_BASE_H
   5
   6 #include <cds/intrusive/details/ellen_bintree_base.h>
   7 #include <cds/container/details/base.h>
   8 #include <cds/opt/compare.h>
   9 #include <cds/details/binary_functor_wrapper.h>
  10
  11
  12 namespace cds { namespace container {
  13     /// EllenBinTree related definitions
  14     /** @ingroup cds_nonintrusive_helper
  15     */
  16     namespace ellen_bintree {
  17
  18 #ifdef CDS_DOXYGEN_INVOKED
  19         /// Typedef for \p cds::intrusive::ellen_bintree::update_desc
  20         typedef cds::intrusive::ellen_bintree::update_desc update_desc;
  21
  22         /// Typedef for \p cds::intrusive::ellen_bintree::internal_node
  23         typedef cds::intrusive::ellen_bintree::internal_node internal_node;
  24
  25         /// Typedef for \p cds::intrusive::ellen_bintree::key_extractor
  26         typedef cds::intrusive::ellen_bintree::key_extractor key_extractor;
  27
  28         /// Typedef for \p cds::intrusive::ellen_bintree::update_desc_allocator
  29         typedef cds::intrusive::ellen_bintree::update_desc_allocator update_desc_allocator;
  30 #else
  31         using cds::intrusive::ellen_bintree::update_desc;
  32         using cds::intrusive::ellen_bintree::internal_node;
  33         using cds::intrusive::ellen_bintree::key_extractor;
  34         using cds::intrusive::ellen_bintree::update_desc_allocator;
  35         using cds::intrusive::ellen_bintree::node_types;
  36 #endif
  37         /// EllenBinTree internal statistics
  38         template <typename Counter = cds::intrusive::ellen_bintree::stat<>::event_counter >
  39         using stat = cds::intrusive::ellen_bintree::stat< Counter >;
  40
  41         /// EllenBinTree empty internal statistics
  42         typedef cds::intrusive::ellen_bintree::empty_stat empty_stat;
  43
  44         /// EllenBinTree leaf node
  45         template <typename GC, typename T>
  46         struct node: public cds::intrusive::ellen_bintree::node<GC>
  47         {
  48             typedef T   value_type  ;   ///< Value type
  49
  50             T   m_Value ;   ///< Value
  51
  52             /// Default ctor
  53             node()
  54             {}
  55
  56             /// Initializing ctor
  57             template <typename Q>
  58             node(Q const& v)
  59                 : m_Value(v)
  60             {}
  61
  62             /// Copy constructor
  63             template <typename... Args>
  64             node( Args const&... args)
  65                 : m_Value( args... )
  66             {}
  67
  68             /// Move constructor
  69             template <typename... Args>
  70             node( Args&&... args)
  71                 : m_Value( std::forward<Args>(args)... )
  72             {}
  73         };
  74
  75         /// EllenBinTreeMap leaf node
  76         template <typename GC, typename Key, typename T>
  77         struct map_node: public cds::intrusive::ellen_bintree::node< GC >
  78         {
  79             typedef Key     key_type    ;   ///< key type
  80             typedef T       mapped_type ;   ///< value type
  81             typedef std::pair<key_type const, mapped_type> value_type  ;   ///< key-value pair stored in the map
  82
  83             value_type  m_Value     ;   ///< Key-value pair stored in map leaf node
  84
  85             /// Initializes key field, value if default-constructed
  86             template <typename K>
  87             map_node( K const& key )
  88                 : m_Value( std::make_pair( key_type(key), mapped_type() ))
  89             {}
  90
  91             /// Initializes key and value fields
  92             template <typename K, typename Q>
  93             map_node( K const& key, Q const& v )
  94                 : m_Value( std::make_pair(key_type(key), mapped_type(v) ))
  95             {}
  96         };
  97
  98         /// Type traits for EllenBinTreeSet and EllenBinTreeMap
  99         struct traits
 100         {
 101             /// Key extracting functor (only for \p EllenBinTreeSet)
 102             /**
 103                 You should explicit define a valid functor.
 104                 The functor has the following prototype:
 105                 \code
 106                 struct key_extractor {
 107                     void operator ()( Key& dest, T const& src );
 108                 };
 109                 \endcode
 110                 It should initialize \p dest key from \p src data.
 111                 The functor is used to initialize internal nodes of \p EllenBinTreeSet
 112             */
 113             typedef opt::none           key_extractor;
 114
 115             /// Key comparison functor
 116             /**
 117                 No default functor is provided. If the option is not specified, the \p less is used.
 118
 119                 See \p cds::opt::compare option description for functor interface.
 120
 121                 You should provide \p compare or \p less functor.
 122                 See \ref cds_container_EllenBinTreeSet_rcu_less "predicate requirements".
 123             */
 124             typedef opt::none                       compare;
 125
 126             /// Specifies binary predicate used for key compare.
 127             /**
 128                 See \p cds::opt::less option description.
 129
 130                 You should provide \p compare or \p less functor.
 131                 See \ref cds_container_EllenBinTreeSet_rcu_less "predicate requirements".
 132             */
 133             typedef opt::none                       less;
 134
 135             /// Item counter
 136             /**
 137                 The type for item counter, by default it is disabled (\p atomicity::empty_item_counter).
 138                 To enable it use \p atomicity::item_counter
 139             */
 140             typedef atomicity::empty_item_counter     item_counter;
 141
 142             /// C++ memory ordering model
 143             /**
 144                 List of available memory ordering see \p opt::memory_model
 145             */
 146             typedef opt::v::relaxed_ordering        memory_model;
 147
 148             /// Allocator for update descriptors
 149             /**
 150                 The allocator type is used for \p ellen_bintree::update_desc.
 151
 152                 Update descriptor is helping data structure with short lifetime and it is good candidate
 153                 for pooling. The number of simultaneously existing descriptors is a small number
 154                 limited the number of threads working with the tree.
 155                 Therefore, a bounded lock-free container like \p cds::container::VyukovMPMCCycleQueue
 156                 is good choice for the free-list of update descriptors,
 157                 see \p cds::memory::vyukov_queue_pool free-list implementation.
 158
 159                 Also notice that size of update descriptor is not dependent on the type of data
 160                 stored in the tree so single free-list object can be used for several \p EllenBinTree object.
 161             */
 162             typedef CDS_DEFAULT_ALLOCATOR           update_desc_allocator;
 163
 164             /// Allocator for internal nodes
 165             /**
 166                 The allocator type is used for \p ellen_bintree::internal_node.
 167             */
 168             typedef CDS_DEFAULT_ALLOCATOR           node_allocator;
 169
 170             /// Allocator for leaf nodes
 171             /**
 172                 Each leaf node contains data stored in the container.
 173             */
 174             typedef CDS_DEFAULT_ALLOCATOR           allocator;
 175
 176             /// Internal statistics
 177             /**
 178                 By default, internal statistics is disabled (\p ellen_bintree::empty_stat).
 179                 To enable it use \p ellen_bintree::stat.
 180             */
 181             typedef empty_stat                      stat;
 182
 183             /// RCU deadlock checking policy (only for RCU-based EllenBinTree<i>XXX</i> classes)
 184             /**
 185                 List of available options see \p opt::rcu_check_deadlock
 186             */
 187             typedef cds::opt::v::rcu_throw_deadlock      rcu_check_deadlock;
 188
 189             /// Key copy policy (for \p EllenBinTreeMap)
 190             /**
 191                 The key copy policy defines a functor to copy leaf node's key to internal node.
 192                 This policy is used only in \p EllenBinTreeMap.
 193                 By default, assignment operator is used.
 194
 195                 The copy functor interface is:
 196                 \code
 197                 struct copy_functor {
 198                     void operator()( Key& dest, Key const& src );
 199                 };
 200                 \endcode
 201             */
 202             typedef opt::none                           copy_policy;
 203         };
 204
 205
 206         /// Metafunction converting option list to \p EllenBinTreeSet traits
 207         /**
 208             \p Options are:
 209             - \p ellen_bintree::key_extractor - key extracting functor, mandatory option. The functor has the following prototype:
 210                 \code
 211                     struct key_extractor {
 212                         void operator ()( Key& dest, T const& src );
 213                     };
 214                 \endcode
 215                 It should initialize \p dest key from \p src data. The functor is used to initialize internal nodes.
 216             - \p opt::compare - key compare functor. No default functor is provided.
 217                 If the option is not specified, \p %opt::less is used.
 218             - \p opt::less - specifies binary predicate used for key compare. At least \p %opt::compare or \p %opt::less should be defined.
 219             - \p opt::item_counter - the type of item counter, default is disabled (\p atomicity::empty_item_counter).
 220                 To enable it use \p atomicity::item_counter
 221             - \p opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
 222                 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
 223             - \p opt::allocator - the allocator for \ref ellen_bintree::node "leaf nodes" which contains data.
 224                 Default is \ref CDS_DEFAULT_ALLOCATOR.
 225             - \p opt::node_allocator - the allocator for internal nodes. Default is \ref CDS_DEFAULT_ALLOCATOR.
 226             - \p ellen_bintree::update_desc_allocator - an allocator of \ref ellen_bintree::update_desc "update descriptors",
 227                 default is \ref CDS_DEFAULT_ALLOCATOR.
 228                 Note that update descriptor is helping data structure with short lifetime and it is good candidate for pooling.
 229                 The number of simultaneously existing descriptors is a relatively small number limited the number of threads
 230                 working with the tree and RCU buffer size.
 231                 Therefore, a bounded lock-free container like \p cds::container::VyukovMPMCCycleQueue is good choice for the free-list
 232                 of update descriptors, see \p cds::memory::vyukov_queue_pool free-list implementation.
 233                 Also notice that size of update descriptor is not dependent on the type of data
 234                 stored in the tree so single free-list object can be used for several EllenBinTree-based object.
 235             - \p opt::stat - internal statistics, by default disabled (\p ellen_bintree::empty_stat). To enable
 236                 it use \p ellen_bintree::stat.
 237             - \p opt::rcu_check_deadlock - a deadlock checking policy, only for RCU-based tree.
 238                 Default is \p opt::v::rcu_throw_deadlock.
 239         */
 240         template <typename... Options>
 241         struct make_set_traits {
 242 #   ifdef CDS_DOXYGEN_INVOKED
 243             typedef implementation_defined type ;   ///< Metafunction result
 244 #   else
 245             typedef typename cds::opt::make_options<
 246                 typename cds::opt::find_type_traits< traits, Options... >::type
 247                 ,Options...
 248             >::type   type;
 249 #   endif
 250         };
 251
 252         /// Metafunction converting option list to \p EllenBinTreeMap traits
 253         /**
 254             \p Options are:
 255             - \p opt::compare - key compare functor. No default functor is provided.
 256                 If the option is not specified, \p %opt::less is used.
 257             - \p opt::less - specifies binary predicate used for key compare. At least \p %opt::compare or \p %opt::less should be defined.
 258             - \p opt::item_counter - the type of item counter, default is disabled (\p atomicity::empty_item_counter).
 259                 To enable it use \p atomicity::item_counter
 260             - opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
 261                 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
 262             - \p opt::allocator - the allocator used for \ref ellen_bintree::map_node "leaf nodes" which contains data.
 263                 Default is \ref CDS_DEFAULT_ALLOCATOR.
 264             - \p opt::node_allocator - the allocator used for \ref ellen_bintree::internal_node "internal nodes".
 265                 Default is \ref CDS_DEFAULT_ALLOCATOR.
 266             - \p ellen_bintree::update_desc_allocator - an allocator of \ref ellen_bintree::update_desc "update descriptors",
 267                 default is \ref CDS_DEFAULT_ALLOCATOR.
 268                 Note that update descriptor is helping data structure with short lifetime and it is good candidate for pooling.
 269                 The number of simultaneously existing descriptors is a relatively small number limited the number of threads
 270                 working with the tree and RCU buffer size.
 271                 Therefore, a bounded lock-free container like \p cds::container::VyukovMPMCCycleQueue is good choice for the free-list
 272                 of update descriptors, see \p cds::memory::vyukov_queue_pool free-list implementation.
 273                 Also notice that size of update descriptor is not dependent on the type of data
 274                 stored in the tree so single free-list object can be used for several EllenBinTree-based object.
 275             - \p opt::stat - internal statistics, by default disabled (\p ellen_bintree::empty_stat). To enable
 276                 it use \p ellen_bintree::stat.
 277             - \p opt::rcu_check_deadlock - a deadlock checking policy, only for RCU-based tree. Default is \p opt::v::rcu_throw_deadlock
 278             - opt::copy_policy - key copying policy defines a functor to copy leaf node's key to internal node.
 279                 By default, assignment operator is used.
 280                 The copy functor interface is:
 281                 \code
 282                 struct copy_functor {
 283                     void operator()( Key& dest, Key const& src );
 284                 };
 285                 \endcode
 286         */
 287         template <typename... Options>
 288         struct make_map_traits {
 289 #   ifdef CDS_DOXYGEN_INVOKED
 290             typedef implementation_defined type ;   ///< Metafunction result
 291 #   else
 292             typedef typename cds::opt::make_options<
 293                 typename cds::opt::find_type_traits< traits, Options... >::type
 294                 ,Options...
 295             >::type   type;
 296 #   endif
 297         };
 298
 299         //@cond
 300         namespace details {
 301
 302             template < class GC, typename Key, typename T, class Traits>
 303             struct make_ellen_bintree_set
 304             {
 305                 typedef GC      gc;
 306                 typedef Key     key_type;
 307                 typedef T       value_type;
 308                 typedef Traits  original_traits;
 309
 310                 typedef node< gc, value_type >  leaf_node;
 311
 312                 struct intrusive_key_extractor
 313                 {
 314                     void operator()( key_type& dest, leaf_node const& src ) const
 315                     {
 316                         typename original_traits::key_extractor()( dest, src.m_Value );
 317                     }
 318                 };
 319
 320                 struct value_accessor
 321                 {
 322                     value_type const& operator()( leaf_node const& node ) const
 323                     {
 324                         return node.m_Value;
 325                     }
 326                 };
 327
 328                 typedef typename cds::opt::details::make_comparator< value_type, original_traits, false >::type key_comparator;
 329
 330                 typedef cds::details::Allocator< leaf_node, typename original_traits::allocator>  cxx_leaf_node_allocator;
 331                 struct leaf_deallocator
 332                 {
 333                     void operator()( leaf_node * p ) const
 334                     {
 335                         cxx_leaf_node_allocator().Delete( p );
 336                     }
 337                 };
 338
 339                 struct intrusive_traits: public original_traits
 340                 {
 341                     typedef cds::intrusive::ellen_bintree::base_hook< cds::opt::gc< gc > >  hook;
 342                     typedef intrusive_key_extractor key_extractor;
 343                     typedef leaf_deallocator        disposer;
 344                     typedef cds::details::compare_wrapper< leaf_node, key_comparator, value_accessor > compare;
 345                 };
 346
 347                 // Metafunction result
 348                 typedef cds::intrusive::EllenBinTree< gc, key_type, leaf_node, intrusive_traits >    type;
 349             };
 350
 351             template < class GC, typename Key, typename T, class Traits>
 352             struct make_ellen_bintree_map
 353             {
 354                 typedef GC      gc;
 355                 typedef Key     key_type;
 356                 typedef T       mapped_type;
 357                 typedef map_node< gc, key_type, mapped_type >   leaf_node;
 358                 typedef typename leaf_node::value_type          value_type;
 359
 360                 typedef Traits  original_traits;
 361
 362                 struct assignment_copy_policy {
 363                     void operator()( key_type& dest, key_type const& src )
 364                     {
 365                         dest = src;
 366                     }
 367                 };
 368                 typedef typename std::conditional<
 369                     std::is_same< typename original_traits::copy_policy, opt::none >::value,
 370                     assignment_copy_policy,
 371                     typename original_traits::copy_policy
 372                 >::type copy_policy;
 373
 374                 struct intrusive_key_extractor
 375                 {
 376                     void operator()( key_type& dest, leaf_node const& src ) const
 377                     {
 378                         copy_policy()( dest, src.m_Value.first );
 379                     }
 380                 };
 381
 382                 struct key_accessor
 383                 {
 384                     key_type const& operator()( leaf_node const& node ) const
 385                     {
 386                         return node.m_Value.first;
 387                     }
 388                 };
 389
 390                 typedef typename cds::opt::details::make_comparator< key_type, original_traits, false >::type key_comparator;
 391
 392                 typedef cds::details::Allocator< leaf_node, typename original_traits::allocator>    cxx_leaf_node_allocator;
 393                 struct leaf_deallocator
 394                 {
 395                     void operator()( leaf_node * p ) const
 396                     {
 397                         cxx_leaf_node_allocator().Delete( p );
 398                     }
 399                 };
 400
 401                 struct intrusive_traits: public original_traits
 402                 {
 403                     typedef cds::intrusive::ellen_bintree::base_hook< cds::opt::gc< gc > >  hook;
 404                     typedef intrusive_key_extractor key_extractor;
 405                     typedef leaf_deallocator        disposer;
 406                     typedef cds::details::compare_wrapper< leaf_node, key_comparator, key_accessor >    compare;
 407                 };
 408
 409                 // Metafunction result
 410                 typedef cds::intrusive::EllenBinTree< gc, key_type, leaf_node, intrusive_traits >    type;
 411             };
 412
 413         } // namespace details
 414         //@endcond
 415     } // namespace ellen_bintree
 416
 417     // Forward declarations
 418     //@cond
 419     template < class GC, typename Key, typename T, class Traits = ellen_bintree::traits >
 420     class EllenBinTreeSet;
 421
 422     template < class GC, typename Key, typename T, class Traits = ellen_bintree::traits >
 423     class EllenBinTreeMap;
 424     //@endcond
 425
 426 }} // namespace cds::container
 427
 428 #endif // #ifndef __CDS_CONTAINER_DETAILS_ELLEN_BINTREE_BASE_H