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             /// 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, EllenBinTreeMap and EllenBinTreePriorityQueue
 101         struct type_traits
 102         {
 103             /// Key extracting functor (only for 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.
 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 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 cds::opt::less option description for predicate interface.
 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 counting feature (see cds::opt::item_counter).
 140                 Default is no item counter (\ref atomicity::empty_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 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 \ref 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 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 \ref 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                 Possible types: ellen_bintree::empty_stat (the default), ellen_bintree::stat or any
 181                 other with interface like \p %stat.
 182             */
 183             typedef empty_stat                      stat;
 184
 185             /// RCU deadlock checking policy (only for RCU-based EllenBinTree<i>XXX</i> classes)
 186             /**
 187                 List of available options see opt::rcu_check_deadlock
 188             */
 189             typedef cds::opt::v::rcu_throw_deadlock      rcu_check_deadlock;
 190
 191             /// Key copy policy (for 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 EllenBinTreeMap. By default, assignment operator is used.
 195
 196                 The copy functor interface is:
 197                 \code
 198                 struct copy_functor {
 199                     void operator()( Key& dest, Key const& src );
 200                 };
 201                 \endcode
 202             */
 203             typedef opt::none                           copy_policy;
 204         };
 205
 206
 207         /// Metafunction converting option list to EllenBinTreeSet traits
 208         /**
 209             This is a wrapper for <tt> cds::opt::make_options< type_traits, Options...> </tt>
 210             \p Options list see \ref cds_container_EllenBinTreeSet "EllenBinTreeSet".
 211         */
 212         template <CDS_DECL_OPTIONS11>
 213         struct make_set_traits {
 214 #   ifdef CDS_DOXYGEN_INVOKED
 215             typedef implementation_defined type ;   ///< Metafunction result
 216 #   else
 217             typedef typename cds::opt::make_options<
 218                 typename cds::opt::find_type_traits< type_traits, CDS_OPTIONS11 >::type
 219                 ,CDS_OPTIONS11
 220             >::type   type;
 221 #   endif
 222         };
 223
 224         /// Metafunction converting option list to EllenBinTreeMap traits
 225         /**
 226             This is a wrapper for <tt> cds::opt::make_options< type_traits, Options...> </tt>
 227             \p Options list see \ref cds_container_EllenBinTreeMap "EllenBinTreeMap".
 228         */
 229         template <CDS_DECL_OPTIONS11>
 230         struct make_map_traits {
 231 #   ifdef CDS_DOXYGEN_INVOKED
 232             typedef implementation_defined type ;   ///< Metafunction result
 233 #   else
 234             typedef typename cds::opt::make_options<
 235                 typename cds::opt::find_type_traits< type_traits, CDS_OPTIONS11 >::type
 236                 ,CDS_OPTIONS11
 237             >::type   type;
 238 #   endif
 239         };
 240
 241         //@cond
 242         namespace details {
 243
 244             template < class GC, typename Key, typename T, class Traits>
 245             struct make_ellen_bintree_set
 246             {
 247                 typedef GC      gc;
 248                 typedef Key     key_type;
 249                 typedef T       value_type;
 250                 typedef Traits  original_type_traits;
 251
 252                 typedef node< gc, value_type >  leaf_node;
 253
 254                 struct intrusive_key_extractor
 255                 {
 256                     void operator()( key_type& dest, leaf_node const& src ) const
 257                     {
 258                         typename original_type_traits::key_extractor()( dest, src.m_Value );
 259                     }
 260                 };
 261
 262                 struct value_accessor
 263                 {
 264                     value_type const& operator()( leaf_node const& node ) const
 265                     {
 266                         return node.m_Value;
 267                     }
 268                 };
 269
 270                 typedef typename cds::opt::details::make_comparator< value_type, original_type_traits, false >::type key_comparator;
 271
 272                 typedef cds::details::Allocator< leaf_node, typename original_type_traits::allocator>    cxx_leaf_node_allocator;
 273                 struct leaf_deallocator
 274                 {
 275                     void operator()( leaf_node * p ) const
 276                     {
 277                         cxx_leaf_node_allocator().Delete( p );
 278                     }
 279                 };
 280
 281                 struct intrusive_type_traits: public original_type_traits
 282                 {
 283                     typedef cds::intrusive::ellen_bintree::base_hook< cds::opt::gc< gc > >  hook;
 284                     typedef intrusive_key_extractor key_extractor;
 285                     typedef leaf_deallocator        disposer;
 286                     typedef cds::details::compare_wrapper< leaf_node, key_comparator, value_accessor > compare;
 287                 };
 288
 289                 // Metafunction result
 290                 typedef cds::intrusive::EllenBinTree< gc, key_type, leaf_node, intrusive_type_traits >    type;
 291             };
 292
 293             template < class GC, typename Key, typename T, class Traits>
 294             struct make_ellen_bintree_map
 295             {
 296                 typedef GC      gc;
 297                 typedef Key     key_type;
 298                 typedef T       mapped_type;
 299                 typedef map_node< gc, key_type, mapped_type >   leaf_node;
 300                 typedef typename leaf_node::value_type          value_type;
 301
 302                 typedef Traits  original_type_traits;
 303
 304                 struct assignment_copy_policy {
 305                     void operator()( key_type& dest, key_type const& src )
 306                     {
 307                         dest = src;
 308                     }
 309                 };
 310                 typedef typename std::conditional<
 311                     std::is_same< typename original_type_traits::copy_policy, opt::none >::value,
 312                     assignment_copy_policy,
 313                     typename original_type_traits::copy_policy
 314                 >::type copy_policy;
 315
 316                 struct intrusive_key_extractor
 317                 {
 318                     void operator()( key_type& dest, leaf_node const& src ) const
 319                     {
 320                         copy_policy()( dest, src.m_Value.first );
 321                     }
 322                 };
 323
 324                 struct key_accessor
 325                 {
 326                     key_type const& operator()( leaf_node const& node ) const
 327                     {
 328                         return node.m_Value.first;
 329                     }
 330                 };
 331
 332                 typedef typename cds::opt::details::make_comparator< key_type, original_type_traits, false >::type key_comparator;
 333
 334                 typedef cds::details::Allocator< leaf_node, typename original_type_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_type_traits: public original_type_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, key_accessor >    compare;
 349                 };
 350
 351                 // Metafunction result
 352                 typedef cds::intrusive::EllenBinTree< gc, key_type, leaf_node, intrusive_type_traits >    type;
 353             };
 354
 355         } // namespace details
 356         //@endcond
 357     } // namespace ellen_bintree
 358
 359     // Forward declarations
 360     //@cond
 361     template < class GC, typename Key, typename T, class Traits = ellen_bintree::type_traits >
 362     class EllenBinTreeSet;
 363
 364     template < class GC, typename Key, typename T, class Traits = ellen_bintree::type_traits >
 365     class EllenBinTreeMap;
 366     //@endcond
 367
 368 }} // namespace cds::container
 369
 370 #endif // #ifndef __CDS_CONTAINER_ELLEN_BINTREE_BASE_H