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