cds/container/ellen_bintree_base.h

   1 //$$CDS-header$$
   2
   3 #ifndef __CDS_CONTAINER_ELLEN_BINTREE_BASE_H
   4 #define __CDS_CONTAINER_ELLEN_BINTREE_BASE_H
   5
   6 #include <cds/intrusive/details/ellen_bintree_base.h>
   7 #include <cds/container/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 cds::intrusive::ellen_bintree::update_desc
  20         typedef cds::intrusive::ellen_bintree::update_desc update_desc;
  21
  22         /// Typedef for cds::intrusive::ellen_bintree::internal_node
  23         typedef cds::intrusive::ellen_bintree::internal_node internal_node;
  24
  25         /// Typedef for cds::intrusive::ellen_bintree::key_extractor
  26         typedef cds::intrusive::ellen_bintree::key_extractor key_extractor;
  27
  28         /// Typedef for cds::intrusive::ellen_bintree::update_desc_allocator
  29         typedef cds::intrusive::ellen_bintree::update_desc_allocator update_desc_allocator;
  30
  31         /// Typedef for cds::intrusive::ellen_bintree::stat
  32         typedef cds::intrusive::ellen_bintree::stat stat;
  33
  34         /// Typedef for cds::intrusive::ellen_bintree::empty_stat
  35         typedef cds::intrusive::ellen_bintree::empty_stat empty_stat;
  36 #else
  37         using cds::intrusive::ellen_bintree::update_desc;
  38         using cds::intrusive::ellen_bintree::internal_node;
  39         using cds::intrusive::ellen_bintree::key_extractor;
  40         using cds::intrusive::ellen_bintree::update_desc_allocator;
  41         using cds::intrusive::ellen_bintree::stat;
  42         using cds::intrusive::ellen_bintree::empty_stat;
  43         using cds::intrusive::ellen_bintree::node_types;
  44 #endif
  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 #ifdef CDS_RVALUE_SUPPORT
  71             /// Move constructor
  72             template <typename... Args>
  73             node( Args&&... args)
  74                 : m_Value( std::forward<Args>(args)... )
  75             {}
  76 #endif  // CDS_RVALUE_SUPPORT
  77         };
  78
  79         /// EllenBinTreeMap leaf node
  80         template <typename GC, typename Key, typename T>
  81         struct map_node: public cds::intrusive::ellen_bintree::node< GC >
  82         {
  83             typedef Key     key_type    ;   ///< key type
  84             typedef T       mapped_type ;   ///< value type
  85             typedef std::pair<key_type const, mapped_type> value_type  ;   ///< key-value pair stored in the map
  86
  87             value_type  m_Value     ;   ///< Key-value pair stored in map leaf node
  88
  89             /// Initializes key field, value if default-constructed
  90             template <typename K>
  91             map_node( K const& key )
  92                 : m_Value( std::make_pair( key_type(key), mapped_type() ))
  93             {}
  94
  95             /// Initializes key and value fields
  96             template <typename K, typename Q>
  97             map_node( K const& key, Q const& v )
  98                 : m_Value( std::make_pair(key_type(key), mapped_type(v) ))
  99             {}
 100         };
 101
 102         /// Type traits for EllenBinTreeSet, EllenBinTreeMap and EllenBinTreePriorityQueue
 103         struct type_traits
 104         {
 105             /// Key extracting functor (only for EllenBinTreeSet)
 106             /**
 107                 You should explicit define a valid functor.
 108                 The functor has the following prototype:
 109                 \code
 110                 struct key_extractor {
 111                     void operator ()( Key& dest, T const& src );
 112                 };
 113                 \endcode
 114                 It should initialize \p dest key from \p src data.
 115                 The functor is used to initialize internal nodes.
 116             */
 117             typedef opt::none           key_extractor;
 118
 119             /// Key comparison functor
 120             /**
 121                 No default functor is provided. If the option is not specified, the \p less is used.
 122
 123                 See cds::opt::compare option description for functor interface.
 124
 125                 You should provide \p compare or \p less functor.
 126                 See \ref cds_container_EllenBinTreeSet_rcu_less "predicate requirements".
 127             */
 128             typedef opt::none                       compare;
 129
 130             /// Specifies binary predicate used for key compare.
 131             /**
 132                 See cds::opt::less option description for predicate interface.
 133
 134                 You should provide \p compare or \p less functor.
 135                 See \ref cds_container_EllenBinTreeSet_rcu_less "predicate requirements".
 136             */
 137             typedef opt::none                       less;
 138
 139             /// Item counter
 140             /**
 141                 The type for item counting feature (see cds::opt::item_counter).
 142                 Default is no item counter (\ref atomicity::empty_item_counter)
 143             */
 144             typedef atomicity::empty_item_counter     item_counter;
 145
 146             /// C++ memory ordering model
 147             /**
 148                 List of available memory ordering see opt::memory_model
 149             */
 150             typedef opt::v::relaxed_ordering        memory_model;
 151
 152             /// Allocator for update descriptors
 153             /**
 154                 The allocator type is used for \ref update_desc.
 155
 156                 Update descriptor is helping data structure with short lifetime and it is good candidate
 157                 for pooling. The number of simultaneously existing descriptors is a small number
 158                 limited the number of threads working with the tree.
 159                 Therefore, a bounded lock-free container like \p cds::container::VyukovMPMCCycleQueue
 160                 is good choice for the free-list of update descriptors,
 161                 see cds::memory::vyukov_queue_pool free-list implementation.
 162
 163                 Also notice that size of update descriptor is not dependent on the type of data
 164                 stored in the tree so single free-list object can be used for several \p EllenBinTree object.
 165             */
 166             typedef CDS_DEFAULT_ALLOCATOR           update_desc_allocator;
 167
 168             /// Allocator for internal nodes
 169             /**
 170                 The allocator type is used for \ref internal_node.
 171             */
 172             typedef CDS_DEFAULT_ALLOCATOR           node_allocator;
 173
 174             /// Allocator for leaf nodes
 175             /**
 176                 Each leaf node contains data stored in the container.
 177             */
 178             typedef CDS_DEFAULT_ALLOCATOR           allocator;
 179
 180             /// Internal statistics
 181             /**
 182                 Possible types: ellen_bintree::empty_stat (the default), ellen_bintree::stat or any
 183                 other with interface like \p %stat.
 184             */
 185             typedef empty_stat                      stat;
 186
 187             /// RCU deadlock checking policy (only for RCU-based EllenBinTree<i>XXX</i> classes)
 188             /**
 189                 List of available options see opt::rcu_check_deadlock
 190             */
 191             typedef cds::opt::v::rcu_throw_deadlock      rcu_check_deadlock;
 192
 193             /// Key copy policy (for EllenBinTreeMap)
 194             /**
 195                 The key copy policy defines a functor to copy leaf node's key to internal node.
 196                 This policy is used only in EllenBinTreeMap. 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 EllenBinTreeSet traits
 210         /**
 211             This is a wrapper for <tt> cds::opt::make_options< type_traits, Options...> </tt>
 212             \p Options list see \ref cds_container_EllenBinTreeSet "EllenBinTreeSet".
 213         */
 214         template <CDS_DECL_OPTIONS11>
 215         struct make_set_traits {
 216 #   ifdef CDS_DOXYGEN_INVOKED
 217             typedef implementation_defined type ;   ///< Metafunction result
 218 #   else
 219             typedef typename cds::opt::make_options<
 220                 typename cds::opt::find_type_traits< type_traits, CDS_OPTIONS11 >::type
 221                 ,CDS_OPTIONS11
 222             >::type   type;
 223 #   endif
 224         };
 225
 226         /// Metafunction converting option list to EllenBinTreeMap traits
 227         /**
 228             This is a wrapper for <tt> cds::opt::make_options< type_traits, Options...> </tt>
 229             \p Options list see \ref cds_container_EllenBinTreeMap "EllenBinTreeMap".
 230         */
 231         template <CDS_DECL_OPTIONS11>
 232         struct make_map_traits {
 233 #   ifdef CDS_DOXYGEN_INVOKED
 234             typedef implementation_defined type ;   ///< Metafunction result
 235 #   else
 236             typedef typename cds::opt::make_options<
 237                 typename cds::opt::find_type_traits< type_traits, CDS_OPTIONS11 >::type
 238                 ,CDS_OPTIONS11
 239             >::type   type;
 240 #   endif
 241         };
 242
 243         //@cond
 244         namespace details {
 245
 246             template < class GC, typename Key, typename T, class Traits>
 247             struct make_ellen_bintree_set
 248             {
 249                 typedef GC      gc;
 250                 typedef Key     key_type;
 251                 typedef T       value_type;
 252                 typedef Traits  original_type_traits;
 253
 254                 typedef node< gc, value_type >  leaf_node;
 255
 256                 struct intrusive_key_extractor
 257                 {
 258                     void operator()( key_type& dest, leaf_node const& src ) const
 259                     {
 260                         typename original_type_traits::key_extractor()( dest, src.m_Value );
 261                     }
 262                 };
 263
 264                 struct value_accessor
 265                 {
 266                     value_type const& operator()( leaf_node const& node ) const
 267                     {
 268                         return node.m_Value;
 269                     }
 270                 };
 271
 272                 typedef typename cds::opt::details::make_comparator< value_type, original_type_traits, false >::type key_comparator;
 273
 274                 typedef cds::details::Allocator< leaf_node, typename original_type_traits::allocator>    cxx_leaf_node_allocator;
 275                 struct leaf_deallocator
 276                 {
 277                     void operator()( leaf_node * p ) const
 278                     {
 279                         cxx_leaf_node_allocator().Delete( p );
 280                     }
 281                 };
 282
 283                 struct intrusive_type_traits: public original_type_traits
 284                 {
 285                     typedef cds::intrusive::ellen_bintree::base_hook< cds::opt::gc< gc > >  hook;
 286                     typedef intrusive_key_extractor key_extractor;
 287                     typedef leaf_deallocator        disposer;
 288                     typedef cds::details::compare_wrapper< leaf_node, key_comparator, value_accessor > compare;
 289                 };
 290
 291                 // Metafunction result
 292                 typedef cds::intrusive::EllenBinTree< gc, key_type, leaf_node, intrusive_type_traits >    type;
 293             };
 294
 295             template < class GC, typename Key, typename T, class Traits>
 296             struct make_ellen_bintree_map
 297             {
 298                 typedef GC      gc;
 299                 typedef Key     key_type;
 300                 typedef T       mapped_type;
 301                 typedef map_node< gc, key_type, mapped_type >   leaf_node;
 302                 typedef typename leaf_node::value_type          value_type;
 303
 304                 typedef Traits  original_type_traits;
 305
 306                 struct assignment_copy_policy {
 307                     void operator()( key_type& dest, key_type const& src )
 308                     {
 309                         dest = src;
 310                     }
 311                 };
 312                 typedef typename std::conditional<
 313                     std::is_same< typename original_type_traits::copy_policy, opt::none >::value,
 314                     assignment_copy_policy,
 315                     typename original_type_traits::copy_policy
 316                 >::type copy_policy;
 317
 318                 struct intrusive_key_extractor
 319                 {
 320                     void operator()( key_type& dest, leaf_node const& src ) const
 321                     {
 322                         copy_policy()( dest, src.m_Value.first );
 323                     }
 324                 };
 325
 326                 struct key_accessor
 327                 {
 328                     key_type const& operator()( leaf_node const& node ) const
 329                     {
 330                         return node.m_Value.first;
 331                     }
 332                 };
 333
 334                 typedef typename cds::opt::details::make_comparator< key_type, original_type_traits, false >::type key_comparator;
 335
 336                 typedef cds::details::Allocator< leaf_node, typename original_type_traits::allocator>    cxx_leaf_node_allocator;
 337                 struct leaf_deallocator
 338                 {
 339                     void operator()( leaf_node * p ) const
 340                     {
 341                         cxx_leaf_node_allocator().Delete( p );
 342                     }
 343                 };
 344
 345                 struct intrusive_type_traits: public original_type_traits
 346                 {
 347                     typedef cds::intrusive::ellen_bintree::base_hook< cds::opt::gc< gc > >  hook;
 348                     typedef intrusive_key_extractor key_extractor;
 349                     typedef leaf_deallocator        disposer;
 350                     typedef cds::details::compare_wrapper< leaf_node, key_comparator, key_accessor >    compare;
 351                 };
 352
 353                 // Metafunction result
 354                 typedef cds::intrusive::EllenBinTree< gc, key_type, leaf_node, intrusive_type_traits >    type;
 355             };
 356
 357         } // namespace details
 358         //@endcond
 359     } // namespace ellen_bintree
 360
 361     // Forward declarations
 362     //@cond
 363     template < class GC, typename Key, typename T, class Traits = ellen_bintree::type_traits >
 364     class EllenBinTreeSet;
 365
 366     template < class GC, typename Key, typename T, class Traits = ellen_bintree::type_traits >
 367     class EllenBinTreeMap;
 368     //@endcond
 369
 370 }} // namespace cds::container
 371
 372 #endif // #ifndef __CDS_CONTAINER_ELLEN_BINTREE_BASE_H