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