gdax-orderbook-hpp/demo/dependencies/libcds-2.3.2/cds/container/details/ellen_bintree_base.h

   1 /*
   2     This file is a part of libcds - Concurrent Data Structures library
   3
   4     (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2017
   5
   6     Source code repo: http://github.com/khizmax/libcds/
   7     Download: http://sourceforge.net/projects/libcds/files/
   8
   9     Redistribution and use in source and binary forms, with or without
  10     modification, are permitted provided that the following conditions are met:
  11
  12     * Redistributions of source code must retain the above copyright notice, this
  13       list of conditions and the following disclaimer.
  14
  15     * Redistributions in binary form must reproduce the above copyright notice,
  16       this list of conditions and the following disclaimer in the documentation
  17       and/or other materials provided with the distribution.
  18
  19     THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
  20     AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  21     IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  22     DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
  23     FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  24     DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
  25     SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
  26     CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
  27     OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  28     OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  29 */
  30
  31 #ifndef CDSLIB_CONTAINER_DETAILS_ELLEN_BINTREE_BASE_H
  32 #define CDSLIB_CONTAINER_DETAILS_ELLEN_BINTREE_BASE_H
  33
  34 #include <cds/intrusive/details/ellen_bintree_base.h>
  35 #include <cds/container/details/base.h>
  36 #include <cds/opt/compare.h>
  37 #include <cds/details/binary_functor_wrapper.h>
  38
  39
  40 namespace cds { namespace container {
  41     /// EllenBinTree related definitions
  42     /** @ingroup cds_nonintrusive_helper
  43     */
  44     namespace ellen_bintree {
  45 #ifdef CDS_DOXYGEN_INVOKED
  46         /// Typedef for \p cds::intrusive::ellen_bintree::update_desc
  47         typedef cds::intrusive::ellen_bintree::update_desc update_desc;
  48
  49         /// Typedef for \p cds::intrusive::ellen_bintree::internal_node
  50         typedef cds::intrusive::ellen_bintree::internal_node internal_node;
  51
  52         /// Typedef for \p cds::intrusive::ellen_bintree::key_extractor
  53         typedef cds::intrusive::ellen_bintree::key_extractor key_extractor;
  54
  55         /// Typedef for \p cds::intrusive::ellen_bintree::update_desc_allocator
  56         typedef cds::intrusive::ellen_bintree::update_desc_allocator update_desc_allocator;
  57 #else
  58         using cds::intrusive::ellen_bintree::update_desc;
  59         using cds::intrusive::ellen_bintree::internal_node;
  60         using cds::intrusive::ellen_bintree::key_extractor;
  61         using cds::intrusive::ellen_bintree::update_desc_allocator;
  62         using cds::intrusive::ellen_bintree::node_types;
  63 #endif
  64         /// EllenBinTree internal statistics
  65         template <typename Counter = cds::intrusive::ellen_bintree::stat<>::event_counter >
  66         using stat = cds::intrusive::ellen_bintree::stat< Counter >;
  67
  68         /// EllenBinTree empty internal statistics
  69         typedef cds::intrusive::ellen_bintree::empty_stat empty_stat;
  70
  71         /// EllenBinTree leaf node
  72         template <typename GC, typename T>
  73         struct node: public cds::intrusive::ellen_bintree::node<GC>
  74         {
  75             typedef T   value_type  ;   ///< Value type
  76
  77             T   m_Value ;   ///< Value
  78
  79             /// Default ctor
  80             node()
  81             {}
  82
  83             /// Initializing ctor
  84             template <typename Q>
  85             node(Q const& v)
  86                 : m_Value(v)
  87             {}
  88
  89             /// Copy constructor
  90             template <typename... Args>
  91             node( Args const&... args )
  92                 : m_Value( args... )
  93             {}
  94
  95             /// Move constructor
  96             template <typename... Args>
  97             node( Args&&... args )
  98                 : m_Value( std::forward<Args>( args )... )
  99             {}
 100         };
 101
 102         /// EllenBinTreeMap leaf node
 103         template <typename GC, typename Key, typename T>
 104         struct map_node: public cds::intrusive::ellen_bintree::node< GC >
 105         {
 106             typedef Key     key_type    ;   ///< key type
 107             typedef T       mapped_type ;   ///< value type
 108             typedef std::pair<key_type const, mapped_type> value_type  ;   ///< key-value pair stored in the map
 109
 110             value_type  m_Value     ;   ///< Key-value pair stored in map leaf node
 111
 112             /// Initializes key field, value if default-constructed
 113             template <typename K>
 114             map_node( K const& key )
 115                 : m_Value( std::make_pair( key_type(key), mapped_type()))
 116             {}
 117
 118             /// Initializes key and value fields
 119             template <typename K, typename Q>
 120             map_node( K const& key, Q const& v )
 121                 : m_Value( std::make_pair(key_type(key), mapped_type(v)))
 122             {}
 123         };
 124
 125         /// Type traits for \p EllenBinTreeSet and \p EllenBinTreeMap
 126         struct traits
 127         {
 128             /// Key extracting functor (only for \p EllenBinTreeSet)
 129             /**
 130                 This is mandatory functor for \p %EllenBinTreeSet.
 131                 It has the following prototype:
 132                 \code
 133                 struct key_extractor {
 134                     void operator ()( Key& dest, T const& src );
 135                 };
 136                 \endcode
 137                 It should initialize \p dest key from \p src data.
 138                 The functor is used to initialize internal nodes of \p %EllenBinTreeSet
 139             */
 140             typedef opt::none           key_extractor;
 141
 142             /// Key comparison functor
 143             /**
 144                 No default functor is provided. If the option is not specified, the \p less is used.
 145
 146                 See \p cds::opt::compare option description for functor interface.
 147
 148                 You should provide \p compare or \p less functor.
 149                 See \ref cds_container_EllenBinTreeSet_rcu_less "predicate requirements".
 150             */
 151             typedef opt::none                       compare;
 152
 153             /// Specifies binary predicate used for key compare.
 154             /**
 155                 See \p cds::opt::less option description.
 156
 157                 You should provide \p compare or \p less functor.
 158                 See \ref cds_container_EllenBinTreeSet_rcu_less "predicate requirements".
 159             */
 160             typedef opt::none                       less;
 161
 162             /// Item counter
 163             /**
 164                 The type for item counter, by default it is disabled (\p atomicity::empty_item_counter).
 165                 To enable it use \p atomicity::item_counter or \p atomicity::cache_friendly_item_counter
 166             */
 167             typedef atomicity::empty_item_counter     item_counter;
 168
 169             /// C++ memory ordering model
 170             /**
 171                 List of available memory ordering see \p opt::memory_model
 172             */
 173             typedef opt::v::relaxed_ordering        memory_model;
 174
 175             /// Allocator for update descriptors
 176             /**
 177                 The allocator type is used for \p ellen_bintree::update_desc.
 178
 179                 Update descriptor is helping data structure with short lifetime and it is good candidate
 180                 for pooling. The number of simultaneously existing descriptors is a small number
 181                 limited the number of threads working with the tree.
 182                 Therefore, a bounded lock-free container like \p cds::container::VyukovMPMCCycleQueue
 183                 is good choice for the free-list of update descriptors,
 184                 see \p cds::memory::vyukov_queue_pool free-list implementation.
 185
 186                 Also notice that size of update descriptor is not dependent on the type of data
 187                 stored in the tree so single free-list object can be used for several \p EllenBinTree object.
 188             */
 189             typedef CDS_DEFAULT_ALLOCATOR           update_desc_allocator;
 190
 191             /// Allocator for internal nodes
 192             /**
 193                 The allocator type is used for \p ellen_bintree::internal_node.
 194             */
 195             typedef CDS_DEFAULT_ALLOCATOR           node_allocator;
 196
 197             /// Allocator for leaf nodes
 198             /**
 199                 Each leaf node contains data stored in the container.
 200             */
 201             typedef CDS_DEFAULT_ALLOCATOR           allocator;
 202
 203             /// Internal statistics
 204             /**
 205                 By default, internal statistics is disabled (\p ellen_bintree::empty_stat).
 206                 To enable it use \p ellen_bintree::stat.
 207             */
 208             typedef empty_stat                      stat;
 209
 210             /// Back-off strategy
 211             typedef cds::backoff::empty             back_off;
 212
 213             /// RCU deadlock checking policy (only for RCU-based EllenBinTree<i>XXX</i> classes)
 214             /**
 215                 List of available options see \p opt::rcu_check_deadlock
 216             */
 217             typedef cds::opt::v::rcu_throw_deadlock      rcu_check_deadlock;
 218
 219             /// Key copy policy (for \p EllenBinTreeMap)
 220             /**
 221                 The key copy policy defines a functor to copy leaf node's key to internal node.
 222                 This policy is used only in \p EllenBinTreeMap.
 223                 By default, assignment operator is used.
 224
 225                 The copy functor interface is:
 226                 \code
 227                 struct copy_functor {
 228                     void operator()( Key& dest, Key const& src );
 229                 };
 230                 \endcode
 231             */
 232             typedef opt::none                           copy_policy;
 233         };
 234
 235
 236         /// Metafunction converting option list to \p EllenBinTreeSet traits
 237         /**
 238             \p Options are:
 239             - \p ellen_bintree::key_extractor - key extracting functor, mandatory option. The functor has the following prototype:
 240                 \code
 241                     struct key_extractor {
 242                         void operator ()( Key& dest, T const& src );
 243                     };
 244                 \endcode
 245                 It should initialize \p dest key from \p src data. The functor is used to initialize internal nodes.
 246             - \p opt::compare - key compare functor. No default functor is provided.
 247                 If the option is not specified, \p %opt::less is used.
 248             - \p opt::less - specifies binary predicate used for key compare. At least \p %opt::compare or \p %opt::less should be defined.
 249             - \p opt::item_counter - the type of item counter, default is disabled (\p atomicity::empty_item_counter).
 250                 To enable it use \p atomicity::item_counter or \p atomicity::cache_friendly_item_counter
 251             - \p opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
 252                 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
 253             - \p opt::allocator - the allocator for \ref ellen_bintree::node "leaf nodes" which contains data.
 254                 Default is \ref CDS_DEFAULT_ALLOCATOR.
 255             - \p opt::node_allocator - the allocator for internal nodes. Default is \ref CDS_DEFAULT_ALLOCATOR.
 256             - \p ellen_bintree::update_desc_allocator - an allocator of \ref ellen_bintree::update_desc "update descriptors",
 257                 default is \ref CDS_DEFAULT_ALLOCATOR.
 258                 Note that update descriptor is helping data structure with short lifetime and it is good candidate for pooling.
 259                 The number of simultaneously existing descriptors is a relatively small number limited the number of threads
 260                 working with the tree and RCU buffer size.
 261                 Therefore, a bounded lock-free container like \p cds::container::VyukovMPMCCycleQueue is good choice for the free-list
 262                 of update descriptors, see \p cds::memory::vyukov_queue_pool free-list implementation.
 263                 Also notice that size of update descriptor is not dependent on the type of data
 264                 stored in the tree so single free-list object can be used for several EllenBinTree-based object.
 265             - \p opt::stat - internal statistics, by default disabled (\p ellen_bintree::empty_stat). To enable
 266                 it use \p ellen_bintree::stat.
 267             - \p opt::backoff - back-off strategy, by default no strategy is used (\p cds::backoff::empty)
 268             - \p opt::rcu_check_deadlock - a deadlock checking policy, only for RCU-based tree.
 269                 Default is \p opt::v::rcu_throw_deadlock.
 270         */
 271         template <typename... Options>
 272         struct make_set_traits {
 273 #   ifdef CDS_DOXYGEN_INVOKED
 274             typedef implementation_defined type ;   ///< Metafunction result
 275 #   else
 276             typedef typename cds::opt::make_options<
 277                 typename cds::opt::find_type_traits< traits, Options... >::type
 278                 ,Options...
 279             >::type   type;
 280 #   endif
 281         };
 282
 283         /// Metafunction converting option list to \p EllenBinTreeMap traits
 284         /**
 285             \p Options are:
 286             - \p opt::compare - key compare functor. No default functor is provided.
 287                 If the option is not specified, \p %opt::less is used.
 288             - \p opt::less - specifies binary predicate used for key compare. At least \p %opt::compare or \p %opt::less should be defined.
 289             - \p opt::item_counter - the type of item counter, default is disabled (\p atomicity::empty_item_counter).
 290                 To enable it use \p atomicity::item_counter or \p atomicity::cache_friendly_item_counter
 291             - opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
 292                 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
 293             - \p opt::allocator - the allocator used for \ref ellen_bintree::map_node "leaf nodes" which contains data.
 294                 Default is \ref CDS_DEFAULT_ALLOCATOR.
 295             - \p opt::node_allocator - the allocator used for \ref ellen_bintree::internal_node "internal nodes".
 296                 Default is \ref CDS_DEFAULT_ALLOCATOR.
 297             - \p ellen_bintree::update_desc_allocator - an allocator of \ref ellen_bintree::update_desc "update descriptors",
 298                 default is \ref CDS_DEFAULT_ALLOCATOR.
 299                 Note that update descriptor is helping data structure with short lifetime and it is good candidate for pooling.
 300                 The number of simultaneously existing descriptors is a relatively small number limited the number of threads
 301                 working with the tree and RCU buffer size.
 302                 Therefore, a bounded lock-free container like \p cds::container::VyukovMPMCCycleQueue is good choice for the free-list
 303                 of update descriptors, see \p cds::memory::vyukov_queue_pool free-list implementation.
 304                 Also notice that size of update descriptor is not dependent on the type of data
 305                 stored in the tree so single free-list object can be used for several EllenBinTree-based object.
 306             - \p opt::stat - internal statistics, by default disabled (\p ellen_bintree::empty_stat). To enable
 307                 it use \p ellen_bintree::stat.
 308             - \p opt::backoff - back-off strategy, by default no strategy is used (\p cds::backoff::empty)
 309             - \p opt::rcu_check_deadlock - a deadlock checking policy, only for RCU-based tree. Default is \p opt::v::rcu_throw_deadlock
 310             - opt::copy_policy - key copying policy defines a functor to copy leaf node's key to internal node.
 311                 By default, assignment operator is used.
 312                 The copy functor interface is:
 313                 \code
 314                 struct copy_functor {
 315                     void operator()( Key& dest, Key const& src );
 316                 };
 317                 \endcode
 318         */
 319         template <typename... Options>
 320         struct make_map_traits {
 321 #   ifdef CDS_DOXYGEN_INVOKED
 322             typedef implementation_defined type ;   ///< Metafunction result
 323 #   else
 324             typedef typename cds::opt::make_options<
 325                 typename cds::opt::find_type_traits< traits, Options... >::type
 326                 ,Options...
 327             >::type   type;
 328 #   endif
 329         };
 330
 331         //@cond
 332         namespace details {
 333
 334             template < class GC, typename Key, typename T, class Traits>
 335             struct make_ellen_bintree_set
 336             {
 337                 typedef GC      gc;
 338                 typedef Key     key_type;
 339                 typedef T       value_type;
 340                 typedef Traits  original_traits;
 341
 342                 typedef node< gc, value_type >  leaf_node;
 343
 344                 struct intrusive_key_extractor
 345                 {
 346                     void operator()( key_type& dest, leaf_node const& src ) const
 347                     {
 348                         typename original_traits::key_extractor()( dest, src.m_Value );
 349                     }
 350                 };
 351
 352                 struct value_accessor
 353                 {
 354                     value_type const& operator()( leaf_node const& node ) const
 355                     {
 356                         return node.m_Value;
 357                     }
 358                 };
 359
 360                 typedef typename cds::opt::details::make_comparator< value_type, original_traits, false >::type key_comparator;
 361
 362                 typedef cds::details::Allocator< leaf_node, typename original_traits::allocator> cxx_leaf_node_allocator;
 363                 struct leaf_deallocator
 364                 {
 365                     void operator()( leaf_node * p ) const
 366                     {
 367                         cxx_leaf_node_allocator().Delete( p );
 368                     }
 369                 };
 370
 371                 struct intrusive_traits: public original_traits
 372                 {
 373                     typedef cds::intrusive::ellen_bintree::base_hook< cds::opt::gc< gc >> hook;
 374                     typedef intrusive_key_extractor key_extractor;
 375                     typedef leaf_deallocator        disposer;
 376                     typedef cds::details::compare_wrapper< leaf_node, key_comparator, value_accessor > compare;
 377                 };
 378
 379                 // Metafunction result
 380                 typedef cds::intrusive::EllenBinTree< gc, key_type, leaf_node, intrusive_traits > type;
 381             };
 382
 383             template < class GC, typename Key, typename T, class Traits>
 384             struct make_ellen_bintree_map
 385             {
 386                 typedef GC      gc;
 387                 typedef Key     key_type;
 388                 typedef T       mapped_type;
 389                 typedef map_node< gc, key_type, mapped_type >   leaf_node;
 390                 typedef typename leaf_node::value_type          value_type;
 391
 392                 typedef Traits  original_traits;
 393
 394                 struct assignment_copy_policy {
 395                     void operator()( key_type& dest, key_type const& src )
 396                     {
 397                         dest = src;
 398                     }
 399                 };
 400                 typedef typename std::conditional<
 401                     std::is_same< typename original_traits::copy_policy, opt::none >::value,
 402                     assignment_copy_policy,
 403                     typename original_traits::copy_policy
 404                 >::type copy_policy;
 405
 406                 struct intrusive_key_extractor
 407                 {
 408                     void operator()( key_type& dest, leaf_node const& src ) const
 409                     {
 410                         copy_policy()( dest, src.m_Value.first );
 411                     }
 412                 };
 413
 414                 struct key_accessor
 415                 {
 416                     key_type const& operator()( leaf_node const& node ) const
 417                     {
 418                         return node.m_Value.first;
 419                     }
 420                 };
 421
 422                 typedef typename cds::opt::details::make_comparator< key_type, original_traits, false >::type key_comparator;
 423
 424                 typedef cds::details::Allocator< leaf_node, typename original_traits::allocator>    cxx_leaf_node_allocator;
 425                 struct leaf_deallocator
 426                 {
 427                     void operator()( leaf_node * p ) const
 428                     {
 429                         cxx_leaf_node_allocator().Delete( p );
 430                     }
 431                 };
 432
 433                 struct intrusive_traits: public original_traits
 434                 {
 435                     typedef cds::intrusive::ellen_bintree::base_hook< cds::opt::gc< gc > >  hook;
 436                     typedef intrusive_key_extractor key_extractor;
 437                     typedef leaf_deallocator        disposer;
 438                     typedef cds::details::compare_wrapper< leaf_node, key_comparator, key_accessor >    compare;
 439                 };
 440
 441                 // Metafunction result
 442                 typedef cds::intrusive::EllenBinTree< gc, key_type, leaf_node, intrusive_traits >    type;
 443             };
 444
 445         } // namespace details
 446         //@endcond
 447     } // namespace ellen_bintree
 448
 449     // Forward declarations
 450     //@cond
 451     template < class GC, typename Key, typename T, class Traits = ellen_bintree::traits >
 452     class EllenBinTreeSet;
 453
 454     template < class GC, typename Key, typename T, class Traits = ellen_bintree::traits >
 455     class EllenBinTreeMap;
 456     //@endcond
 457
 458 }} // namespace cds::container
 459
 460 #endif // #ifndef CDSLIB_CONTAINER_DETAILS_ELLEN_BINTREE_BASE_H