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             /// Back-off strategy
 184             typedef cds::backoff::empty             back_off;
 185
 186             /// RCU deadlock checking policy (only for RCU-based EllenBinTree<i>XXX</i> classes)
 187             /**
 188                 List of available options see \p opt::rcu_check_deadlock
 189             */
 190             typedef cds::opt::v::rcu_throw_deadlock      rcu_check_deadlock;
 191
 192             /// Key copy policy (for \p EllenBinTreeMap)
 193             /**
 194                 The key copy policy defines a functor to copy leaf node's key to internal node.
 195                 This policy is used only in \p EllenBinTreeMap.
 196                 By default, assignment operator is used.
 197
 198                 The copy functor interface is:
 199                 \code
 200                 struct copy_functor {
 201                     void operator()( Key& dest, Key const& src );
 202                 };
 203                 \endcode
 204             */
 205             typedef opt::none                           copy_policy;
 206         };
 207
 208
 209         /// Metafunction converting option list to \p EllenBinTreeSet traits
 210         /**
 211             \p Options are:
 212             - \p ellen_bintree::key_extractor - key extracting functor, mandatory option. The functor has the following prototype:
 213                 \code
 214                     struct key_extractor {
 215                         void operator ()( Key& dest, T const& src );
 216                     };
 217                 \endcode
 218                 It should initialize \p dest key from \p src data. The functor is used to initialize internal nodes.
 219             - \p opt::compare - key compare functor. No default functor is provided.
 220                 If the option is not specified, \p %opt::less is used.
 221             - \p opt::less - specifies binary predicate used for key compare. At least \p %opt::compare or \p %opt::less should be defined.
 222             - \p opt::item_counter - the type of item counter, default is disabled (\p atomicity::empty_item_counter).
 223                 To enable it use \p atomicity::item_counter
 224             - \p opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
 225                 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
 226             - \p opt::allocator - the allocator for \ref ellen_bintree::node "leaf nodes" which contains data.
 227                 Default is \ref CDS_DEFAULT_ALLOCATOR.
 228             - \p opt::node_allocator - the allocator for internal nodes. Default is \ref CDS_DEFAULT_ALLOCATOR.
 229             - \p ellen_bintree::update_desc_allocator - an allocator of \ref ellen_bintree::update_desc "update descriptors",
 230                 default is \ref CDS_DEFAULT_ALLOCATOR.
 231                 Note that update descriptor is helping data structure with short lifetime and it is good candidate for pooling.
 232                 The number of simultaneously existing descriptors is a relatively small number limited the number of threads
 233                 working with the tree and RCU buffer size.
 234                 Therefore, a bounded lock-free container like \p cds::container::VyukovMPMCCycleQueue is good choice for the free-list
 235                 of update descriptors, see \p cds::memory::vyukov_queue_pool free-list implementation.
 236                 Also notice that size of update descriptor is not dependent on the type of data
 237                 stored in the tree so single free-list object can be used for several EllenBinTree-based object.
 238             - \p opt::stat - internal statistics, by default disabled (\p ellen_bintree::empty_stat). To enable
 239                 it use \p ellen_bintree::stat.
 240             - \p opt::backoff - back-off strategy, by default no strategy is used (\p cds::backoff::empty)
 241             - \p opt::rcu_check_deadlock - a deadlock checking policy, only for RCU-based tree.
 242                 Default is \p opt::v::rcu_throw_deadlock.
 243         */
 244         template <typename... Options>
 245         struct make_set_traits {
 246 #   ifdef CDS_DOXYGEN_INVOKED
 247             typedef implementation_defined type ;   ///< Metafunction result
 248 #   else
 249             typedef typename cds::opt::make_options<
 250                 typename cds::opt::find_type_traits< traits, Options... >::type
 251                 ,Options...
 252             >::type   type;
 253 #   endif
 254         };
 255
 256         /// Metafunction converting option list to \p EllenBinTreeMap traits
 257         /**
 258             \p Options are:
 259             - \p opt::compare - key compare functor. No default functor is provided.
 260                 If the option is not specified, \p %opt::less is used.
 261             - \p opt::less - specifies binary predicate used for key compare. At least \p %opt::compare or \p %opt::less should be defined.
 262             - \p opt::item_counter - the type of item counter, default is disabled (\p atomicity::empty_item_counter).
 263                 To enable it use \p atomicity::item_counter
 264             - opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
 265                 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
 266             - \p opt::allocator - the allocator used for \ref ellen_bintree::map_node "leaf nodes" which contains data.
 267                 Default is \ref CDS_DEFAULT_ALLOCATOR.
 268             - \p opt::node_allocator - the allocator used for \ref ellen_bintree::internal_node "internal nodes".
 269                 Default is \ref CDS_DEFAULT_ALLOCATOR.
 270             - \p ellen_bintree::update_desc_allocator - an allocator of \ref ellen_bintree::update_desc "update descriptors",
 271                 default is \ref CDS_DEFAULT_ALLOCATOR.
 272                 Note that update descriptor is helping data structure with short lifetime and it is good candidate for pooling.
 273                 The number of simultaneously existing descriptors is a relatively small number limited the number of threads
 274                 working with the tree and RCU buffer size.
 275                 Therefore, a bounded lock-free container like \p cds::container::VyukovMPMCCycleQueue is good choice for the free-list
 276                 of update descriptors, see \p cds::memory::vyukov_queue_pool free-list implementation.
 277                 Also notice that size of update descriptor is not dependent on the type of data
 278                 stored in the tree so single free-list object can be used for several EllenBinTree-based object.
 279             - \p opt::stat - internal statistics, by default disabled (\p ellen_bintree::empty_stat). To enable
 280                 it use \p ellen_bintree::stat.
 281             - \p opt::backoff - back-off strategy, by default no strategy is used (\p cds::backoff::empty)
 282             - \p opt::rcu_check_deadlock - a deadlock checking policy, only for RCU-based tree. Default is \p opt::v::rcu_throw_deadlock
 283             - opt::copy_policy - key copying policy defines a functor to copy leaf node's key to internal node.
 284                 By default, assignment operator is used.
 285                 The copy functor interface is:
 286                 \code
 287                 struct copy_functor {
 288                     void operator()( Key& dest, Key const& src );
 289                 };
 290                 \endcode
 291         */
 292         template <typename... Options>
 293         struct make_map_traits {
 294 #   ifdef CDS_DOXYGEN_INVOKED
 295             typedef implementation_defined type ;   ///< Metafunction result
 296 #   else
 297             typedef typename cds::opt::make_options<
 298                 typename cds::opt::find_type_traits< traits, Options... >::type
 299                 ,Options...
 300             >::type   type;
 301 #   endif
 302         };
 303
 304         //@cond
 305         namespace details {
 306
 307             template < class GC, typename Key, typename T, class Traits>
 308             struct make_ellen_bintree_set
 309             {
 310                 typedef GC      gc;
 311                 typedef Key     key_type;
 312                 typedef T       value_type;
 313                 typedef Traits  original_traits;
 314
 315                 typedef node< gc, value_type >  leaf_node;
 316
 317                 struct intrusive_key_extractor
 318                 {
 319                     void operator()( key_type& dest, leaf_node const& src ) const
 320                     {
 321                         typename original_traits::key_extractor()( dest, src.m_Value );
 322                     }
 323                 };
 324
 325                 struct value_accessor
 326                 {
 327                     value_type const& operator()( leaf_node const& node ) const
 328                     {
 329                         return node.m_Value;
 330                     }
 331                 };
 332
 333                 typedef typename cds::opt::details::make_comparator< value_type, original_traits, false >::type key_comparator;
 334
 335                 typedef cds::details::Allocator< leaf_node, typename original_traits::allocator>  cxx_leaf_node_allocator;
 336                 struct leaf_deallocator
 337                 {
 338                     void operator()( leaf_node * p ) const
 339                     {
 340                         cxx_leaf_node_allocator().Delete( p );
 341                     }
 342                 };
 343
 344                 struct intrusive_traits: public original_traits
 345                 {
 346                     typedef cds::intrusive::ellen_bintree::base_hook< cds::opt::gc< gc > >  hook;
 347                     typedef intrusive_key_extractor key_extractor;
 348                     typedef leaf_deallocator        disposer;
 349                     typedef cds::details::compare_wrapper< leaf_node, key_comparator, value_accessor > compare;
 350                 };
 351
 352                 // Metafunction result
 353                 typedef cds::intrusive::EllenBinTree< gc, key_type, leaf_node, intrusive_traits >    type;
 354             };
 355
 356             template < class GC, typename Key, typename T, class Traits>
 357             struct make_ellen_bintree_map
 358             {
 359                 typedef GC      gc;
 360                 typedef Key     key_type;
 361                 typedef T       mapped_type;
 362                 typedef map_node< gc, key_type, mapped_type >   leaf_node;
 363                 typedef typename leaf_node::value_type          value_type;
 364
 365                 typedef Traits  original_traits;
 366
 367                 struct assignment_copy_policy {
 368                     void operator()( key_type& dest, key_type const& src )
 369                     {
 370                         dest = src;
 371                     }
 372                 };
 373                 typedef typename std::conditional<
 374                     std::is_same< typename original_traits::copy_policy, opt::none >::value,
 375                     assignment_copy_policy,
 376                     typename original_traits::copy_policy
 377                 >::type copy_policy;
 378
 379                 struct intrusive_key_extractor
 380                 {
 381                     void operator()( key_type& dest, leaf_node const& src ) const
 382                     {
 383                         copy_policy()( dest, src.m_Value.first );
 384                     }
 385                 };
 386
 387                 struct key_accessor
 388                 {
 389                     key_type const& operator()( leaf_node const& node ) const
 390                     {
 391                         return node.m_Value.first;
 392                     }
 393                 };
 394
 395                 typedef typename cds::opt::details::make_comparator< key_type, original_traits, false >::type key_comparator;
 396
 397                 typedef cds::details::Allocator< leaf_node, typename original_traits::allocator>    cxx_leaf_node_allocator;
 398                 struct leaf_deallocator
 399                 {
 400                     void operator()( leaf_node * p ) const
 401                     {
 402                         cxx_leaf_node_allocator().Delete( p );
 403                     }
 404                 };
 405
 406                 struct intrusive_traits: public original_traits
 407                 {
 408                     typedef cds::intrusive::ellen_bintree::base_hook< cds::opt::gc< gc > >  hook;
 409                     typedef intrusive_key_extractor key_extractor;
 410                     typedef leaf_deallocator        disposer;
 411                     typedef cds::details::compare_wrapper< leaf_node, key_comparator, key_accessor >    compare;
 412                 };
 413
 414                 // Metafunction result
 415                 typedef cds::intrusive::EllenBinTree< gc, key_type, leaf_node, intrusive_traits >    type;
 416             };
 417
 418         } // namespace details
 419         //@endcond
 420     } // namespace ellen_bintree
 421
 422     // Forward declarations
 423     //@cond
 424     template < class GC, typename Key, typename T, class Traits = ellen_bintree::traits >
 425     class EllenBinTreeSet;
 426
 427     template < class GC, typename Key, typename T, class Traits = ellen_bintree::traits >
 428     class EllenBinTreeMap;
 429     //@endcond
 430
 431 }} // namespace cds::container
 432
 433 #endif // #ifndef __CDS_CONTAINER_DETAILS_ELLEN_BINTREE_BASE_H