cds/opt/options.h

   1 //$$CDS-header$$
   2
   3 #ifndef __CDS_OPT_OPTIONS_H
   4 #define __CDS_OPT_OPTIONS_H
   5
   6 /*
   7     Framework to define template options
   8
   9     Editions:
  10         2011.01.23 khizmax  Created
  11 */
  12
  13 #include <cds/details/aligned_type.h>
  14 #include <cds/user_setup/allocator.h>
  15 #include <cds/user_setup/cache_line.h>
  16 #include <cds/cxx11_atomic.h>
  17 #include <stdlib.h> // rand, srand
  18
  19 namespace cds {
  20
  21 /// Framework to define template options
  22 /**
  23     There are two kind of options:
  24     - \p type-option - option that determines a data type. The template argument \p Type of the option is a type.
  25     - \p value-option - option that determines a value. The template argument \p Value of the option is a value.
  26 */
  27 namespace opt {
  28
  29     /// Predefined options value (generally, for the options that determine the data types)
  30     namespace v {}
  31
  32     /// Type indicates that an option is not specified and the default one should be used
  33     struct none
  34     {
  35         //@cond
  36         template <class Base> struct pack: public Base
  37         {};
  38         //@endcond
  39     };
  40
  41     /// Metafunction for selecting default option value
  42     /**
  43         Template parameters:
  44         - \p Option - option value
  45         - \p Default - default option value
  46         - \p Value - option value if \p Option is not opt::none
  47
  48         If \p Option is opt::none, the metafunction result is \p Default, otherwise
  49         the result is \p Value.
  50
  51         Examples:
  52         \code
  53         // default_spin is cds::lock::Spin
  54         typedef typename cds::opt::select_default< cds::opt::none, cds::lock::Spin >::type  default_spin;
  55
  56         // spin_32bit is cds::lock::Spin32
  57         typedef typename cds::opt::select_default< cds::lock::Spin32, cds::lock::Spin >::type  spin_32bit;
  58         \endcode
  59     */
  60     template <typename Option, typename Default, typename Value = Option>
  61     struct select_default
  62     {
  63         typedef Value type ;   ///< metafunction result
  64     };
  65     //@cond
  66     template <typename Default>
  67     struct select_default< none, Default >
  68     {
  69         typedef Default type;
  70     };
  71     //@endcond
  72
  73     /// Metafunction to select option value
  74     /**
  75         This metafunction is intended for extracting the value of the \p Option option.
  76         For example,
  77         \code
  78         #include <cds/opt/options.h>
  79         #include <type_traits> // only for testing purpose (static_assert)
  80
  81         struct tag_a;
  82
  83         // Define option
  84         typedef cds::opt::tag< tag_a >  tag_option;
  85
  86         // What is the value of the tag_option?
  87         // How we can extract tag_a from tag_option?
  88         // Here is a solution:
  89         typedef cds::opt::value< tag_option >::tag  tag_option_value;
  90
  91         // tag_option_value is the same as tag_a
  92         static_assert( std::is_same< tag_option_value, tag_a >::value, "Error: tag_option_value != tag_a" );
  93
  94         \endcode
  95     */
  96     template <typename Option>
  97     struct value: public Option::template pack<none>
  98     {};
  99
 100
 101     /// [type-option] Option setter specifies a tag
 102     /**
 103         Suppose, you have a struct
 104         \code
 105         struct Feature
 106         {  .... };
 107         \endcode
 108         and you want that your class \p X would be derived from several \p Feature:
 109         \code
 110             class X: public Feature, public Feature
 111             { .... };
 112         \endcode
 113
 114         How can you distinguish one \p Feature from another?
 115         You may use a tag option:
 116         \code
 117             template <typename Tag>
 118             struct Feature
 119             { .... };
 120
 121             class tag_a;
 122             class tag_b;
 123             class X: public Feature< tag_a >, public Feature< tag_b >
 124             { .... };
 125         \endcode
 126         Now you can distinguish one \p Feature from another:
 127         \code
 128             X x;
 129             Feature<tag_a>& fa = static_cast< Feature<tag_a> >( x );
 130             Feature<tag_b>& fb = static_cast< Feature<tag_b> >( x );
 131         \endcode
 132
 133         \p tag option setter allows you to do things like this for an option-centric approach:
 134         \code
 135         template <typename ...Options>
 136         struct Feature
 137         { .... };
 138
 139         class tag_a;
 140         class tag_b;
 141         class X: public Feature< tag<tag_a> >, public Feature< tag<tag_b> >
 142         { .... };
 143         \endcode
 144
 145         This option setter is widely used in cds::intrusive containers to distinguish
 146         between different intrusive part of container's node.
 147
 148         An incomplete type can serve as a \p Tag.
 149     */
 150     template <typename Tag>
 151     struct tag {
 152         //@cond
 153         template<class Base> struct pack: public Base
 154         {
 155             typedef Tag tag;
 156         };
 157         //@endcond
 158     };
 159
 160     /// [type-option] Option setter specifies lock class
 161     /**
 162         Specification of the \p Type class is:
 163         \code
 164         struct Lock {
 165             void lock();
 166             void unlock();
 167         };
 168         \endcode
 169     */
 170     template <typename Type>
 171     struct lock_type {
 172         //@cond
 173         template<class Base> struct pack: public Base
 174         {
 175             typedef Type lock_type;
 176         };
 177         //@endcond
 178     };
 179
 180     /// [type-option] Back-off strategy option setter
 181     /**
 182         Back-off strategy used in some algorithm.
 183         See cds::backoff namespace for back-off explanation and supported interface.
 184     */
 185     template <typename Type>
 186     struct back_off {
 187         //@cond
 188         template <class Base> struct pack: public Base
 189         {
 190             typedef Type back_off;
 191         };
 192         //@endcond
 193     };
 194
 195     /// [type-option] Option setter for garbage collecting schema used
 196     /**
 197         Possible values of \p GC template parameter are:
 198         - cds::gc::HP - Hazard Pointer garbage collector
 199         - cds::gc::HRC - Gidenstam's garbage collector
 200         - cds::gc::PTB - Pass-the-Buck garbage collector
 201         - cds::gc::none::GC - No garbage collector (not supported for some containers)
 202     */
 203     template <typename GC>
 204     struct gc {
 205         //@cond
 206         template <class Base> struct pack: public Base
 207         {
 208             typedef GC gc;
 209         };
 210         //@endcond
 211     };
 212
 213     /// [type-option] Option setter for an allocator
 214     /**
 215         \p Type is allocator with \p std::allocator interface. Default is value of macro CDS_DEFAULT_ALLOCATOR
 216         that, in turn, is \p std::allocator.
 217
 218         The \p libcds containers actively use rebinding to convert an allocator of one type to another. Thus,
 219         you may specify any valid type as std::allocator's template parameter.
 220
 221         See also opt::node_allocator
 222     */
 223     template <typename Type>
 224     struct allocator {
 225         //@cond
 226         template <typename Base> struct pack: public Base
 227         {
 228             typedef Type allocator;
 229         };
 230         //@endcond
 231     };
 232
 233     /// [type-option] Option setter for node allocator
 234     /**
 235         \p Type is allocator with \p std::allocator interface. Default is value of macro CDS_DEFAULT_ALLOCATOR
 236         that, in turn, is \p std::allocator.
 237
 238         Many node-base containers require an allocator for maintaining data (container's node) and for internal use.
 239         Sometimes, this types of allocator should be different for performance reason.
 240         For example, we should like to allocate the node from a pool of preallocated nodes.
 241         Such pool can be seen as the node allocator.
 242
 243         Usually, if a container supports \p opt::allocator and \p %opt::node_allocator options
 244         and \p opt::node_allocator is not specified the \p %opt::allocator option is used for maintaining the nodes.
 245
 246         The \p libcds containers actively use rebinding to convert an allocator of one type to another. Thus,
 247         you may specify any valid type as std::allocator's template parameter.
 248     */
 249     template <typename Type>
 250     struct node_allocator {
 251         //@cond
 252             template <typename Base> struct pack: public Base
 253             {
 254                 typedef Type node_allocator;
 255             };
 256         //@endcond
 257     };
 258
 259     /// [type-option] Option setter for item counting
 260     /**
 261         Some data structure (for example, queues) has additional feature for item counting.
 262         This option allows to set up appropriate item counting policy for that data structure.
 263
 264         Predefined option \p Type:
 265         - atomicity::empty_item_counter - no item counting performed. It is default policy for many
 266             containers
 267         - atomicity::item_counter - the class that provides atomically item counting
 268         - opt::v::sequential_item_counter - simple non-atomic item counter. This item counter is not intended for
 269             concurrent containers and may be used only if it is explicitly noted.
 270
 271         You may provide other implementation of atomicity::item_counter interface for your needs.
 272
 273         Note, the item counting in lock-free containers cannot be exact; for example, if
 274         item counter for a container returns zero it is not mean that the container is empty.
 275         Thus, item counter may be used for statistical purposes only.
 276     */
 277     template <typename Type>
 278     struct item_counter {
 279         //@cond
 280         template <typename Base> struct pack: public Base
 281         {
 282             typedef Type item_counter;
 283         };
 284         //@endcond
 285     };
 286
 287     namespace v {
 288         /// Sequential non-atomic item counter
 289         /**
 290             This type of item counter is not intended for concurrent containers
 291             and may be used only if it is explicitly noted.
 292         */
 293         class sequential_item_counter
 294         {
 295         public:
 296             typedef size_t counter_type    ;  ///< Counter type
 297         protected:
 298             counter_type  m_nCounter ;      ///< Counter
 299
 300         public:
 301             sequential_item_counter()
 302                 : m_nCounter(0)
 303             {}
 304
 305             /// Returns current value of the counter
 306             counter_type    value() const
 307             {
 308                 return m_nCounter;
 309             }
 310
 311             /// Same as \ref value() with relaxed memory ordering
 312             operator counter_type() const
 313             {
 314                 return value();
 315             }
 316
 317             /// Increments the counter. Semantics: postincrement
 318             counter_type inc()
 319             {
 320                 return m_nCounter++;
 321             }
 322
 323             /// Decrements the counter. Semantics: postdecrement
 324             counter_type dec()
 325             {
 326                 return m_nCounter--;
 327             }
 328
 329             /// Preincrement
 330             counter_type operator ++()
 331             {
 332                 return inc() + 1;
 333             }
 334             /// Postincrement
 335             counter_type operator ++(int)
 336             {
 337                 return inc();
 338             }
 339
 340             /// Predecrement
 341             counter_type operator --()
 342             {
 343                 return dec() - 1;
 344             }
 345             /// Postdecrement
 346             counter_type operator --(int)
 347             {
 348                 return dec();
 349             }
 350
 351             /// Resets count to 0
 352             void reset()
 353             {
 354                 m_nCounter = 0;
 355             }
 356         };
 357     } // namespace v
 358
 359     /// Special alignment constants for \ref cds::opt::alignment option
 360     enum special_alignment {
 361         no_special_alignment = 0,   ///< no special alignment
 362         cache_line_alignment = 1    ///< use cache line size defined in cds/user_setup/cache_line.h
 363     };
 364
 365     /// [value-option] Alignment option setter
 366     /**
 367         Alignment for some internal data of containers. May be useful to solve false sharing problem.
 368         \p Value defines desired alignment and it may be power of two integer or predefined values from
 369         \ref special_alignment enum.
 370     */
 371     template <unsigned int Value>
 372     struct alignment {
 373         //@cond
 374         template <typename Base> struct pack: public Base
 375         {
 376             enum { alignment = Value };
 377         };
 378         //@endcond
 379     };
 380
 381     //@cond
 382     namespace details {
 383         template <typename Type, unsigned int Alignment>
 384         struct alignment_setter {
 385             typedef typename cds::details::aligned_type< Type, Alignment >::type  type;
 386         };
 387
 388         template <typename Type>
 389         struct alignment_setter<Type, no_special_alignment> {
 390             typedef Type type;
 391         };
 392
 393         template <typename Type>
 394         struct alignment_setter<Type, cache_line_alignment> {
 395             typedef typename cds::details::aligned_type< Type, c_nCacheLineSize >::type  type;
 396         };
 397
 398     } // namespace details
 399     //@endcond
 400
 401     /// [type-option] Generic option setter for statisitcs
 402     /**
 403         This option sets a type to gather statistics.
 404         The option is generic - no predefined type(s) is provided.
 405         The particular \p Type of statistics depends on internal structure of the object.
 406     */
 407     template <typename Type>
 408     struct stat {
 409         //@cond
 410         template <typename Base> struct pack: public Base
 411         {
 412             typedef Type stat;
 413         };
 414         //@endcond
 415     };
 416
 417     /// [type-option] Option setter for C++ memory model
 418     /**
 419         The <b>cds</b> library supports following memory ordering constraints for atomic operations in container implementation:
 420         - v::relaxed_ordering - relaxed C++ memory model. This mode supports full set of memory ordering constraints:
 421             \p memory_order_relaxed, \p memory_order_acquire, \p memory_order_release and so on.
 422         - v::sequential_consistent - sequentially consistent C++ memory model (default memory ordering for C++). In
 423             this mode any memory ordering constraint maps to \p memory_order_seq_cst.
 424
 425         The \p Type template parameter can be v::relaxed_ordering or v::sequential_consistent.
 426
 427         You may mix different memory ordering options for different containers: one declare as sequentially consistent,
 428         another declare as relaxed.
 429         Usually, v::relaxed_ordering is the default memory ordering for <b>cds</b> containers.
 430     */
 431     template <typename Type>
 432     struct memory_model {
 433         //@cond
 434         template <typename Base> struct pack: public Base
 435         {
 436             typedef Type memory_model;
 437         };
 438         //@endcond
 439     };
 440
 441     namespace v {
 442         /// Relaxed memory ordering model
 443         /**
 444             In this memory model the memory constraints are defined according to C++ Memory Model specification.
 445
 446             See opt::memory_model for explanations
 447         */
 448         struct relaxed_ordering {
 449             //@cond
 450
 451             // For new C++11 (cds-1.1.0)
 452             static const atomics::memory_order memory_order_relaxed    = atomics::memory_order_relaxed;
 453             static const atomics::memory_order memory_order_consume    = atomics::memory_order_consume;
 454             static const atomics::memory_order memory_order_acquire    = atomics::memory_order_acquire;
 455             static const atomics::memory_order memory_order_release    = atomics::memory_order_release;
 456             static const atomics::memory_order memory_order_acq_rel    = atomics::memory_order_acq_rel;
 457             static const atomics::memory_order memory_order_seq_cst    = atomics::memory_order_seq_cst;
 458             //@endcond
 459         };
 460
 461         /// Sequential consistent memory ordering model
 462         /**
 463             In this memory model any memory constraint is equivalent to \p memory_order_seq_cst.
 464
 465             See opt::memory_model for explanations
 466         */
 467         struct sequential_consistent {
 468             //@cond
 469
 470             // For new C++11 (cds-1.1.0)
 471             static const atomics::memory_order memory_order_relaxed    = atomics::memory_order_seq_cst;
 472             static const atomics::memory_order memory_order_consume    = atomics::memory_order_seq_cst;
 473             static const atomics::memory_order memory_order_acquire    = atomics::memory_order_seq_cst;
 474             static const atomics::memory_order memory_order_release    = atomics::memory_order_seq_cst;
 475             static const atomics::memory_order memory_order_acq_rel    = atomics::memory_order_seq_cst;
 476             static const atomics::memory_order memory_order_seq_cst    = atomics::memory_order_seq_cst;
 477             //@endcond
 478         };
 479     } // namespace v
 480
 481     /// [type-option] Base type traits option setter
 482     /**
 483         This option setter is intended generally for internal use for type rebinding.
 484     */
 485     template <typename Type>
 486     struct type_traits {
 487         //@cond
 488         template <typename Base> struct pack: public Base
 489         {
 490             typedef Type type_traits;
 491         };
 492         //@endcond
 493     };
 494
 495     /// Resizing policy option
 496     /**
 497         This option specifies the resizing policy that decides when to resize a container.
 498         Used in some containers, for example, in container::StripedHashSet, intrusive::StripedHashSet.
 499
 500         The real resizing policy specified by \p Type does strongly depend on a container
 501         that supports this option, see container documentation about possibly \p Type values.
 502     */
 503     template <typename Type>
 504     struct resizing_policy {
 505         //@cond
 506         template <typename Base> struct pack: public Base
 507         {
 508             typedef Type resizing_policy;
 509         };
 510         //@endcond
 511     };
 512
 513     /// Copy policy option
 514     /**
 515         The copy policy defines an item copying algorithm which is used, for example, when a container is resized.
 516         It is very specific algorithm depending on type of the container.
 517     */
 518     template <typename Type>
 519     struct copy_policy {
 520         //@cond
 521         template <typename Base> struct pack: public Base
 522         {
 523             typedef Type copy_policy;
 524         };
 525         //@endcond
 526     };
 527
 528     /// Swap policy option
 529     /**
 530         The swap policy specifies an algorithm for swapping two objects.
 531         Usually, the default policy is \p std::swap (see opt::v::default_swap_policy):
 532
 533         @code
 534         struct std_swap {
 535             template <typename T>
 536             void operator ()( T& v1, T& v2 )
 537             {
 538                 std::swap( v1, v2 );
 539             }
 540         };
 541         @endcode
 542     */
 543     template <typename Type>
 544     struct swap_policy {
 545         //@cond
 546         template <typename Base> struct pack: public Base
 547         {
 548             typedef Type swap_policy;
 549         };
 550         //@endcond
 551     };
 552
 553     namespace v {
 554
 555         /// Default swap policy (see opt::swap_policy option)
 556         /**
 557             The default swap policy is wrappr around \p std::swap algorithm.
 558         */
 559         struct default_swap_policy {
 560             /// Performs swapping of \p v1 and \p v2 using \p std::swap algo
 561             template <typename T>
 562             void operator()( T& v1, T& v2 ) const
 563             {
 564                 std::swap( v1, v2 );
 565             }
 566         };
 567     } // namespace v
 568
 569     /// Move policy option
 570     /**
 571         The move policy specifies an algorithm for moving object content.
 572         In trivial case, it can be simple assignment.
 573
 574         The move interface is:
 575         \code
 576         template <typename T>
 577         struct move_policy {
 578             void operator()( T& dest, T& src );
 579         };
 580         \endcode
 581
 582         Note that in move algorithm the \p src source argument can be changed too.
 583         So you can use move semantics.
 584
 585         Usually, the default move policy is opt::v::assignment_move_policy
 586     */
 587     template <typename Type>
 588     struct move_policy {
 589         //@cond
 590         template <typename Base> struct pack: public Base
 591         {
 592             typedef Type move_policy;
 593         };
 594         //@endcond
 595     };
 596
 597     namespace v {
 598         /// \ref opt::move_policy "Move policy" based on assignment operator
 599         struct assignment_move_policy
 600         {
 601             /// <tt> dest = src </tt>
 602             template <typename T>
 603             void operator()( T& dest, T const& src ) const
 604             {
 605                 dest = src;
 606             }
 607         };
 608     } // namespace v
 609
 610     /// [value-option] Enable sorting
 611     /**
 612         This option enables (<tt>Enable = true</tt>) or disables (<tt>Enable == false</tt>)
 613         sorting of a container.
 614     */
 615     template <bool Enable>
 616     struct sort {
 617         //@cond
 618         template <typename Base> struct pack: public Base
 619         {
 620             static bool const sort = Enable;
 621         };
 622         //@endcond
 623     };
 624
 625     /// [type-option] Concurrent access policy
 626     /**
 627         This option specifies synchronization strategy for fine-grained lock-based containers.
 628         The option has no predefined \p Policy type.
 629         For each container that accepts this option the range of available \p Policy types
 630         is unique.
 631     */
 632     template <typename Policy>
 633     struct mutex_policy {
 634         //@cond
 635         template <typename Base> struct pack: public Base
 636         {
 637             typedef Policy mutex_policy;
 638         };
 639         //@endcond
 640     };
 641
 642
 643     /// [type-option] Random number generator
 644     /**
 645         The option specifies a random number generator.
 646         \p Random can be any STL random number generator producing
 647         unsigned integer: \p std::linear_congruential_engine,
 648         \p std::mersenne_twister_engine, \p std::subtract_with_carry_engine
 649         and so on, or opt::v::c_rand.
 650
 651     */
 652     template <typename Random>
 653     struct random_engine {
 654         //@cond
 655         template <typename Base> struct pack: public Base
 656         {
 657             typedef Random random_engine;
 658         };
 659         //@endcond
 660     };
 661
 662     namespace v {
 663         /// \p rand() -base random number generator
 664         /**
 665             This generator returns a pseudorandom integer in the range 0 to \p RAND_MAX (32767).
 666         */
 667         struct c_rand {
 668             typedef unsigned int result_type; ///< Result type
 669
 670             /// Constructor initializes object calling \p srand()
 671             c_rand()
 672             {
 673                 srand(1);
 674             }
 675
 676             /// Returns next random number calling \p rand()
 677             result_type operator()()
 678             {
 679                 return (result_type) rand();
 680             }
 681         };
 682     } // namespace v
 683
 684     //@cond
 685     // For internal use
 686     template <typename Accessor>
 687     struct key_accessor {
 688         template <typename Base> struct pack: public Base
 689         {
 690             typedef Accessor key_accessor;
 691         };
 692     };
 693
 694     template <typename Traits, typename ReplaceWith, typename WhatReplace = none >
 695     struct replace_key_accessor {
 696         typedef typename std::conditional<
 697             std::is_same< typename Traits::key_accessor, WhatReplace >::value,
 698             typename opt::key_accessor< ReplaceWith >::template pack< Traits >,
 699             Traits
 700         >::type type;
 701     };
 702     //@endcond
 703
 704 }}  // namespace cds::opt
 705
 706 #include <cds/opt/make_options_var.h>
 707
 708 #endif  // #ifndef __CDS_OPT_OPTIONS_H