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