cds/container/details/ellen_bintree_base.h

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