cds/opt/options.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-2016
   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_OPT_OPTIONS_H
  32 #define CDSLIB_OPT_OPTIONS_H
  33
  34 /*
  35     Framework to define template options
  36
  37     Editions:
  38         2011.01.23 khizmax  Created
  39 */
  40
  41 #include <cstdlib> // rand, srand
  42
  43 #include <cds/details/aligned_type.h>
  44 #include <cds/user_setup/allocator.h>
  45 #include <cds/user_setup/cache_line.h>
  46 #include <cds/algo/atomic.h>
  47
  48 namespace cds {
  49
  50 /// Framework to define template options
  51 /**
  52     There are two kind of options:
  53     - \p type-option - option that determines a data type. The template argument \p Type of the option is a type.
  54     - \p value-option - option that determines a value. The template argument \p Value of the option is a value.
  55 */
  56 namespace opt {
  57
  58     /// Type indicates that an option is not specified and the default one should be used
  59     struct none
  60     {
  61         //@cond
  62         template <class Base> struct pack: public Base
  63         {};
  64         //@endcond
  65     };
  66
  67     /// Metafunction for selecting default option value
  68     /**
  69         Template parameters:
  70         - \p Option - option value
  71         - \p Default - default option value
  72         - \p Value - option value if \p Option is not opt::none
  73
  74         If \p Option is opt::none, the metafunction result is \p Default, otherwise
  75         the result is \p Value.
  76
  77         Examples:
  78         \code
  79         // default_spin is cds::sync::spin
  80         typedef typename cds::opt::select_default< cds::opt::none, cds::sync::spin >::type  default_spin;
  81
  82         // spin_32bit is cds::sync::reentrant_spin32
  83         typedef typename cds::opt::select_default< cds::opt::none, cds::sync::reentrant_spin32 >::type  spin_32bit;
  84         \endcode
  85     */
  86     template <typename Option, typename Default, typename Value = Option>
  87     struct select_default
  88     {
  89         typedef Value type ;   ///< metafunction result
  90     };
  91     //@cond
  92     template <typename Default>
  93     struct select_default< none, Default >
  94     {
  95         typedef Default type;
  96     };
  97     //@endcond
  98
  99     /// Metafunction to select option value
 100     /**
 101         This metafunction is intended for extracting the value of the \p Option option.
 102         For example,
 103         \code
 104         #include <cds/opt/options.h>
 105         #include <type_traits> // only for testing purpose (static_assert)
 106
 107         struct tag_a;
 108
 109         // Define option
 110         typedef cds::opt::tag< tag_a >  tag_option;
 111
 112         // What is the value of the tag_option?
 113         // How we can extract tag_a from tag_option?
 114         // Here is a solution:
 115         typedef cds::opt::value< tag_option >::tag  tag_option_value;
 116
 117         // tag_option_value is the same as tag_a
 118         static_assert( std::is_same< tag_option_value, tag_a >::value, "Error: tag_option_value != tag_a" );
 119
 120         \endcode
 121     */
 122     template <typename Option>
 123     struct value: public Option::template pack<none>
 124     {};
 125
 126
 127     /// [type-option] Option setter specifies a tag
 128     /**
 129         Suppose, you have a struct
 130         \code
 131         struct Feature
 132         {  .... };
 133         \endcode
 134         and you want that your class \p X would be derived from several \p Feature:
 135         \code
 136             class X: public Feature, public Feature
 137             { .... };
 138         \endcode
 139
 140         How can you distinguish one \p Feature from another?
 141         You may use a tag option:
 142         \code
 143             template <typename Tag>
 144             struct Feature
 145             { .... };
 146
 147             class tag_a;
 148             class tag_b;
 149             class X: public Feature< tag_a >, public Feature< tag_b >
 150             { .... };
 151         \endcode
 152         Now you can distinguish one \p Feature from another:
 153         \code
 154             X x;
 155             Feature<tag_a>& fa = static_cast< Feature<tag_a> >( x );
 156             Feature<tag_b>& fb = static_cast< Feature<tag_b> >( x );
 157         \endcode
 158
 159         \p tag option setter allows you to do things like this for an option-centric approach:
 160         \code
 161         template <typename ...Options>
 162         struct Feature
 163         { .... };
 164
 165         class tag_a;
 166         class tag_b;
 167         class X: public Feature< tag<tag_a> >, public Feature< tag<tag_b> >
 168         { .... };
 169         \endcode
 170
 171         This option setter is widely used in cds::intrusive containers to distinguish
 172         between different intrusive part of container's node.
 173
 174         An incomplete type can serve as a \p Tag.
 175     */
 176     template <typename Tag>
 177     struct tag {
 178         //@cond
 179         template<class Base> struct pack: public Base
 180         {
 181             typedef Tag tag;
 182         };
 183         //@endcond
 184     };
 185
 186     /// [type-option] Option setter specifies lock class
 187     /**
 188         Specification of the \p Type class is:
 189         \code
 190         struct Lock {
 191             void lock();
 192             void unlock();
 193         };
 194         \endcode
 195     */
 196     template <typename Type>
 197     struct lock_type {
 198         //@cond
 199         template<class Base> struct pack: public Base
 200         {
 201             typedef Type lock_type;
 202         };
 203         //@endcond
 204     };
 205
 206     /// [type-option] @ref cds_sync_monitor "Monitor" type setter
 207     /**
 208         This option setter specifyes @ref cds_sync_monitor "synchronization monitor"
 209         for blocking container.
 210     */
 211     template <typename Type>
 212     struct sync_monitor {
 213         //@cond
 214         template <class Base> struct pack : public Base
 215         {
 216             typedef Type sync_monitor;
 217         };
 218         //@endcond
 219     };
 220
 221     /// [type-option] Back-off strategy option setter
 222     /**
 223         Back-off strategy used in some algorithm.
 224         See cds::backoff namespace for back-off explanation and supported interface.
 225     */
 226     template <typename Type>
 227     struct back_off {
 228         //@cond
 229         template <class Base> struct pack: public Base
 230         {
 231             typedef Type back_off;
 232         };
 233         //@endcond
 234     };
 235
 236     /// [type-option] Option setter for garbage collecting schema used
 237     /**
 238         Possible values of \p GC template parameter are:
 239         - cds::gc::HP - Hazard Pointer garbage collector
 240         - cds::gc::DHP - Dynamic Hazard Pointer garbage collector
 241         - cds::gc::none::GC - No garbage collector (not supported for some containers)
 242     */
 243     template <typename GC>
 244     struct gc {
 245         //@cond
 246         template <class Base> struct pack: public Base
 247         {
 248             typedef GC gc;
 249         };
 250         //@endcond
 251     };
 252
 253     /// [type-option] Option setter for an allocator
 254     /**
 255         \p Type is allocator with \p std::allocator interface. Default is value of macro CDS_DEFAULT_ALLOCATOR
 256         that, in turn, is \p std::allocator.
 257
 258         The \p libcds containers actively use rebinding to convert an allocator of one type to another. Thus,
 259         you may specify any valid type as std::allocator's template parameter.
 260
 261         See also opt::node_allocator
 262     */
 263     template <typename Type>
 264     struct allocator {
 265         //@cond
 266         template <typename Base> struct pack: public Base
 267         {
 268             typedef Type allocator;
 269         };
 270         //@endcond
 271     };
 272
 273     /// [type-option] Option setter for node allocator
 274     /**
 275         \p Type is allocator with \p std::allocator interface. Default is value of macro CDS_DEFAULT_ALLOCATOR
 276         that, in turn, is \p std::allocator.
 277
 278         Many node-base containers require an allocator for maintaining data (container's node) and for internal use.
 279         Sometimes, this types of allocator should be different for performance reason.
 280         For example, we should like to allocate the node from a pool of preallocated nodes.
 281         Such pool can be seen as the node allocator.
 282
 283         Usually, if a container supports \p opt::allocator and \p %opt::node_allocator options
 284         and \p opt::node_allocator is not specified the \p %opt::allocator option is used for maintaining the nodes.
 285
 286         The \p libcds containers actively use rebinding to convert an allocator of one type to another. Thus,
 287         you may specify any valid type as std::allocator's template parameter.
 288     */
 289     template <typename Type>
 290     struct node_allocator {
 291         //@cond
 292             template <typename Base> struct pack: public Base
 293             {
 294                 typedef Type node_allocator;
 295             };
 296         //@endcond
 297     };
 298
 299     /// [type-option] Option setter for item counting
 300     /**
 301         Some data structure (for example, queues) has additional feature for item counting.
 302         This option allows to set up appropriate item counting policy for that data structure.
 303
 304         Predefined option \p Type:
 305         - \p atomicity::empty_item_counter - no item counting performed. It is default policy for many
 306             containers
 307         - \p atomicity::item_counter - the class that provides atomically item counting
 308         - \p opt::v::sequential_item_counter - simple non-atomic item counter. This item counter is not intended for
 309             concurrent containers and may be used only if it is explicitly noted.
 310
 311         You may provide other implementation of \p atomicity::item_counter interface for your needs.
 312
 313         Note, the item counting in lock-free containers cannot be exact; for example, if
 314         item counter for a container returns zero it is not mean that the container is empty.
 315         Thus, the item counter may be used for statistical purposes only.
 316     */
 317     template <typename Type>
 318     struct item_counter {
 319         //@cond
 320         template <typename Base> struct pack: public Base
 321         {
 322             typedef Type item_counter;
 323         };
 324         //@endcond
 325     };
 326
 327     /// Special alignment constants for \ref cds::opt::alignment option
 328     enum special_alignment {
 329         no_special_alignment = 0,   ///< no special alignment
 330         cache_line_alignment = 1    ///< use cache line size defined in cds/user_setup/cache_line.h
 331     };
 332
 333     /// [value-option] Alignment option setter
 334     /**
 335         Alignment for some internal data of containers. May be useful to solve false sharing problem.
 336         \p Value defines desired alignment and it may be power of two integer or predefined values from
 337         \ref special_alignment enum.
 338     */
 339     template <unsigned int Value>
 340     struct alignment {
 341         //@cond
 342         template <typename Base> struct pack: public Base
 343         {
 344             enum { alignment = Value };
 345         };
 346         //@endcond
 347     };
 348
 349     //@cond
 350     namespace details {
 351         template <typename Type, unsigned int Alignment>
 352         struct alignment_setter {
 353             typedef typename cds::details::aligned_type< Type, Alignment >::type  type;
 354         };
 355
 356         template <typename Type>
 357         struct alignment_setter<Type, no_special_alignment> {
 358             typedef Type type;
 359         };
 360
 361         template <typename Type>
 362         struct alignment_setter<Type, cache_line_alignment> {
 363             typedef typename cds::details::aligned_type< Type, c_nCacheLineSize >::type  type;
 364         };
 365     } // namespace details
 366     //@endcond
 367
 368     /// Special padding constants for \p cds::opt::padding option
 369     enum special_padding {
 370         no_special_padding = 0,   ///< no special padding
 371         cache_line_padding = 1,   ///< use cache line size defined in cds/user_setup/cache_line.h
 372
 373         /// Apply padding only for tiny data when data size is less than required padding
 374         /**
 375             The flag means that if your data size is less than the casheline size, the padding is applyed.
 376             Otherwise no padding will be applyed.
 377
 378             This flag is applyed for padding value:
 379             \code
 380             cds::opt::padding< cds::opt::cache_line_padding | cds::opt::padding_tiny_data_only >;
 381             cds::opt::padding< 256 | cds::opt::padding_tiny_data_only >;
 382             \endcode
 383         */
 384         padding_tiny_data_only = 0x80000000,
 385
 386         //@cond
 387         padding_flags = padding_tiny_data_only
 388         //@endcond
 389     };
 390
 391     /// [value-option] Padding option setter
 392     /**
 393         The padding for the internal data of some containers. May be useful to solve false sharing problem.
 394         \p Value defines desired padding and it may be power of two integer or predefined values from
 395         \p special_padding enum.
 396     */
 397     template <unsigned int Value>
 398     struct padding {
 399         //@cond
 400         template <typename Base> struct pack: public Base
 401         {
 402             enum { padding = Value };
 403         };
 404         //@endcond
 405     };
 406
 407     //@cond
 408     namespace details {
 409         enum padding_vs_datasize {
 410             padding_datasize_less,
 411             padding_datasize_equal,
 412             padding_datasize_greater
 413         };
 414
 415         template < typename T, unsigned int Padding, bool NoPadding, padding_vs_datasize Relation, bool TinyOnly >
 416         struct apply_padding_helper;
 417
 418         template <typename T, padding_vs_datasize Relation, bool TinyOnly >
 419         struct apply_padding_helper < T, 0, true, Relation, TinyOnly >
 420         {
 421             struct type {
 422                 T   data;
 423             };
 424             typedef void padding_type;
 425         };
 426
 427         template <typename T, unsigned int Padding, bool TinyOnly >
 428         struct apply_padding_helper < T, Padding, false, padding_datasize_equal, TinyOnly >
 429         {
 430             struct type {
 431                 T   data;
 432             };
 433             typedef void padding_type;
 434         };
 435
 436         template <typename T, unsigned int Padding, bool TinyOnly >
 437         struct apply_padding_helper < T, Padding, false, padding_datasize_less, TinyOnly >
 438         {
 439             typedef uint8_t padding_type[Padding - sizeof( T )];
 440             struct type {
 441                 T data;
 442                 padding_type pad_;
 443             };
 444
 445         };
 446
 447         template <typename T, unsigned int Padding >
 448         struct apply_padding_helper < T, Padding, false, padding_datasize_greater, false >
 449         {
 450             typedef uint8_t padding_type[Padding - sizeof( T ) % Padding];
 451             struct type {
 452                 T data;
 453                 padding_type pad_;
 454             };
 455         };
 456
 457         template <typename T, unsigned int Padding >
 458         struct apply_padding_helper < T, Padding, false, padding_datasize_greater, true >
 459         {
 460             struct type {
 461                 T data;
 462             };
 463             typedef void padding_type;
 464         };
 465
 466         template <typename T, unsigned int Padding >
 467         struct apply_padding
 468         {
 469         private:
 470             enum { padding = Padding & ~padding_flags };
 471
 472         public:
 473             static CDS_CONSTEXPR const size_t c_nPadding =
 474                 static_cast<unsigned int>(padding) == static_cast<unsigned int>(cache_line_padding) ? cds::c_nCacheLineSize :
 475                 static_cast<unsigned int>(padding) == static_cast<unsigned int>(no_special_padding) ? 0 : padding;
 476
 477             static_assert( (c_nPadding & (c_nPadding - 1)) == 0, "Padding must be a power-of-two number" );
 478
 479             typedef apply_padding_helper< T,
 480                 c_nPadding,
 481                 c_nPadding == 0,
 482                 sizeof( T ) < c_nPadding ? padding_datasize_less : sizeof( T ) == c_nPadding ? padding_datasize_equal : padding_datasize_greater,
 483                 (Padding & padding_tiny_data_only) != 0
 484             > result;
 485
 486             typedef typename result::type type;
 487
 488             typedef typename std::conditional<
 489                 std::is_same< typename result::padding_type, void >::value,
 490                 unsigned int,
 491                 typename result::padding_type
 492             >::type padding_type;
 493         };
 494
 495     } // namespace details
 496     //@endcond
 497
 498
 499     /// [type-option] Generic option setter for statisitcs
 500     /**
 501         This option sets a type to gather statistics.
 502         The option is generic - no predefined type(s) is provided.
 503         The particular \p Type of statistics depends on internal structure of the object.
 504     */
 505     template <typename Type>
 506     struct stat {
 507         //@cond
 508         template <typename Base> struct pack: public Base
 509         {
 510             typedef Type stat;
 511         };
 512         //@endcond
 513     };
 514
 515     /// [type-option] Option setter for C++ memory model
 516     /**
 517         The <b>cds</b> library supports following memory ordering constraints for atomic operations in container implementation:
 518         - \p v::relaxed_ordering - relaxed C++ memory model. This mode supports full set of memory ordering constraints:
 519             \p memory_order_relaxed, \p memory_order_acquire, \p memory_order_release and so on.
 520         - \p v::sequential_consistent - sequentially consistent C++ memory model (default memory ordering for C++). In
 521             this mode any memory ordering constraint maps to \p memory_order_seq_cst.
 522
 523         The \p Type template parameter can be \p v::relaxed_ordering or \p v::sequential_consistent.
 524
 525         You may mix different memory ordering options for different containers: one declare as sequentially consistent,
 526         another declare as relaxed.
 527         Usually, \p v::relaxed_ordering is the default memory ordering for <b>libcds</b> containers.
 528     */
 529     template <typename Type>
 530     struct memory_model {
 531         //@cond
 532         template <typename Base> struct pack: public Base
 533         {
 534             typedef Type memory_model;
 535         };
 536         //@endcond
 537     };
 538
 539     /// [type-option] Base type traits option setter
 540     /**
 541         This option setter is intended generally for internal use for type rebinding.
 542     */
 543     template <typename Type>
 544     struct type_traits {
 545         //@cond
 546         template <typename Base> struct pack: public Base
 547         {
 548             typedef Type type_traits;
 549         };
 550         //@endcond
 551     };
 552
 553     /// Resizing policy option
 554     /**
 555         This option specifies the resizing policy that decides when to resize a container.
 556         Used in some containers, for example, in container::StripedHashSet, intrusive::StripedHashSet.
 557
 558         The real resizing policy specified by \p Type does strongly depend on a container
 559         that supports this option, see container documentation about possibly \p Type values.
 560     */
 561     template <typename Type>
 562     struct resizing_policy {
 563         //@cond
 564         template <typename Base> struct pack: public Base
 565         {
 566             typedef Type resizing_policy;
 567         };
 568         //@endcond
 569     };
 570
 571     /// Copy policy option
 572     /**
 573         The copy policy defines an item copying algorithm which is used, for example, when a container is resized.
 574         It is very specific algorithm depending on type of the container.
 575     */
 576     template <typename Type>
 577     struct copy_policy {
 578         //@cond
 579         template <typename Base> struct pack: public Base
 580         {
 581             typedef Type copy_policy;
 582         };
 583         //@endcond
 584     };
 585
 586     /// Swap policy option
 587     /**
 588         The swap policy specifies an algorithm for swapping two objects.
 589         Usually, the default policy is \p std::swap (see opt::v::default_swap_policy):
 590
 591         @code
 592         struct std_swap {
 593             template <typename T>
 594             void operator ()( T& v1, T& v2 )
 595             {
 596                 std::swap( v1, v2 );
 597             }
 598         };
 599         @endcode
 600     */
 601     template <typename Type>
 602     struct swap_policy {
 603         //@cond
 604         template <typename Base> struct pack: public Base
 605         {
 606             typedef Type swap_policy;
 607         };
 608         //@endcond
 609     };
 610
 611     /// Move policy option
 612     /**
 613         The move policy specifies an algorithm for moving object content.
 614         In trivial case, it can be simple assignment.
 615
 616         The move interface is:
 617         \code
 618         template <typename T>
 619         struct move_policy {
 620             void operator()( T& dest, T& src );
 621         };
 622         \endcode
 623
 624         Note that in move algorithm the \p src source argument can be changed too.
 625         So you can use move semantics.
 626
 627         Usually, the default move policy is opt::v::assignment_move_policy
 628     */
 629     template <typename Type>
 630     struct move_policy {
 631         //@cond
 632         template <typename Base> struct pack: public Base
 633         {
 634             typedef Type move_policy;
 635         };
 636         //@endcond
 637     };
 638
 639     /// [value-option] Enable sorting
 640     /**
 641         This option enables (<tt>Enable = true</tt>) or disables (<tt>Enable == false</tt>)
 642         sorting of a container.
 643     */
 644     template <bool Enable>
 645     struct sort {
 646         //@cond
 647         template <typename Base> struct pack: public Base
 648         {
 649             static bool const sort = Enable;
 650         };
 651         //@endcond
 652     };
 653
 654     /// [type-option] Concurrent access policy
 655     /**
 656         This option specifies synchronization strategy for fine-grained lock-based containers.
 657         The option has no predefined \p Policy type.
 658         For each container that accepts this option the range of available \p Policy types
 659         is unique.
 660     */
 661     template <typename Policy>
 662     struct mutex_policy {
 663         //@cond
 664         template <typename Base> struct pack: public Base
 665         {
 666             typedef Policy mutex_policy;
 667         };
 668         //@endcond
 669     };
 670
 671
 672     /// [type-option] Random number generator
 673     /**
 674         The option specifies a random number generator.
 675         \p Random can be any STL random number generator producing
 676         unsigned integer: \p std::linear_congruential_engine,
 677         \p std::mersenne_twister_engine, \p std::subtract_with_carry_engine
 678         and so on, or \p opt::v::c_rand.
 679
 680     */
 681     template <typename Random>
 682     struct random_engine {
 683         //@cond
 684         template <typename Base> struct pack: public Base
 685         {
 686             typedef Random random_engine;
 687         };
 688         //@endcond
 689     };
 690
 691     /// [type-option] Free-list implementation
 692     /**
 693         See \p cds::intrusive::FreeList for free-list interface
 694     */
 695     template <typename FreeList>
 696     struct free_list {
 697         //@cond
 698         template <typename Base> struct pack: public Base
 699         {
 700             typedef FreeList free_list;
 701         };
 702         //@endcond
 703     };
 704
 705     //@cond
 706     // For internal use
 707     template <typename Accessor>
 708     struct key_accessor {
 709         template <typename Base> struct pack: public Base
 710         {
 711             typedef Accessor key_accessor;
 712         };
 713     };
 714
 715     template <typename Traits, typename ReplaceWith, typename WhatReplace = none >
 716     struct replace_key_accessor {
 717         typedef typename std::conditional<
 718             std::is_same< typename Traits::key_accessor, WhatReplace >::value,
 719             typename opt::key_accessor< ReplaceWith >::template pack< Traits >,
 720             Traits
 721         >::type type;
 722     };
 723     //@endcond
 724
 725 }}  // namespace cds::opt
 726
 727
 728 // ****************************************************
 729 // Options predefined types and values
 730
 731 namespace cds { namespace opt {
 732
 733     /// Predefined options value
 734     namespace v {
 735
 736         /// Sequential non-atomic item counter
 737         /**
 738             This type of \p opt::item_counter option is not intended for concurrent containers
 739             and may be used only if it is explicitly noted.
 740         */
 741         class sequential_item_counter
 742         {
 743         public:
 744             typedef size_t counter_type    ;  ///< Counter type
 745         protected:
 746             counter_type  m_nCounter ;      ///< Counter
 747
 748         public:
 749             sequential_item_counter()
 750                 : m_nCounter(0)
 751             {}
 752
 753             /// Returns current value of the counter
 754             counter_type    value() const
 755             {
 756                 return m_nCounter;
 757             }
 758
 759             /// Same as \ref value() with relaxed memory ordering
 760             operator counter_type() const
 761             {
 762                 return value();
 763             }
 764
 765             /// Increments the counter. Semantics: postincrement
 766             counter_type inc()
 767             {
 768                 return m_nCounter++;
 769             }
 770
 771             /// Decrements the counter. Semantics: postdecrement
 772             counter_type dec()
 773             {
 774                 return m_nCounter--;
 775             }
 776
 777             /// Preincrement
 778             counter_type operator ++()
 779             {
 780                 return inc() + 1;
 781             }
 782             /// Postincrement
 783             counter_type operator ++(int)
 784             {
 785                 return inc();
 786             }
 787
 788             /// Predecrement
 789             counter_type operator --()
 790             {
 791                 return dec() - 1;
 792             }
 793             /// Postdecrement
 794             counter_type operator --(int)
 795             {
 796                 return dec();
 797             }
 798
 799             /// Resets count to 0
 800             void reset()
 801             {
 802                 m_nCounter = 0;
 803             }
 804         };
 805
 806         /// Relaxed memory ordering \p opt::memory_model
 807         /**
 808             In this ordering the memory constraints are defined according to C++ Memory Model specification:
 809             each constraint is mapped to \p std::memory_order constraints one-to-one
 810         */
 811         struct relaxed_ordering {
 812             //@cond
 813             static const atomics::memory_order memory_order_relaxed    = atomics::memory_order_relaxed;
 814             static const atomics::memory_order memory_order_consume    = atomics::memory_order_consume;
 815             static const atomics::memory_order memory_order_acquire    = atomics::memory_order_acquire;
 816             static const atomics::memory_order memory_order_release    = atomics::memory_order_release;
 817             static const atomics::memory_order memory_order_acq_rel    = atomics::memory_order_acq_rel;
 818             static const atomics::memory_order memory_order_seq_cst    = atomics::memory_order_seq_cst;
 819             //@endcond
 820         };
 821
 822         /// Sequential consistent \p opt::memory_memory ordering
 823         /**
 824             In this memory model any memory constraint is equivalent to \p std::memory_order_seq_cst.
 825         */
 826         struct sequential_consistent {
 827             //@cond
 828             static const atomics::memory_order memory_order_relaxed    = atomics::memory_order_seq_cst;
 829             static const atomics::memory_order memory_order_consume    = atomics::memory_order_seq_cst;
 830             static const atomics::memory_order memory_order_acquire    = atomics::memory_order_seq_cst;
 831             static const atomics::memory_order memory_order_release    = atomics::memory_order_seq_cst;
 832             static const atomics::memory_order memory_order_acq_rel    = atomics::memory_order_seq_cst;
 833             static const atomics::memory_order memory_order_seq_cst    = atomics::memory_order_seq_cst;
 834             //@endcond
 835         };
 836
 837         //@cond
 838         /// Totally relaxed \p opt::memory_model ordering (do not use!)
 839         /**
 840             In this memory model any memory constraint is equivalent to \p std::memory_order_relaxed.
 841             @warning Do not use this model! It intended for testing purposes only
 842             to verify debugging instruments like Thread Sanitizer.
 843         */
 844         struct total_relaxed_ordering {
 845             static const atomics::memory_order memory_order_relaxed    = atomics::memory_order_relaxed;
 846             static const atomics::memory_order memory_order_consume    = atomics::memory_order_relaxed;
 847             static const atomics::memory_order memory_order_acquire    = atomics::memory_order_relaxed;
 848             static const atomics::memory_order memory_order_release    = atomics::memory_order_relaxed;
 849             static const atomics::memory_order memory_order_acq_rel    = atomics::memory_order_relaxed;
 850             static const atomics::memory_order memory_order_seq_cst    = atomics::memory_order_relaxed;
 851         };
 852         //@endcond
 853
 854
 855         /// Default swap policy for \p opt::swap_policy option
 856         /**
 857             The default swap policy is wrappr around \p std::swap algorithm.
 858         */
 859         struct default_swap_policy {
 860             /// Performs swapping of \p v1 and \p v2 using \p std::swap algo
 861             template <typename T>
 862             void operator()( T& v1, T& v2 ) const
 863             {
 864                 std::swap( v1, v2 );
 865             }
 866         };
 867
 868         /// \p opt::move_policy based on move-assignment operator
 869         struct assignment_move_policy
 870         {
 871             /// <tt> dest = std::move( src ) </tt>
 872             template <typename T>
 873             void operator()( T& dest, T&& src ) const
 874             {
 875                 dest = std::move( src );
 876             }
 877         };
 878
 879         /// \p rand() -base random number generator for \p opt::random_engine
 880         /**
 881             This generator returns a pseudorandom integer in the range 0 to \p RAND_MAX (32767).
 882         */
 883         struct c_rand {
 884             typedef unsigned int result_type; ///< Result type
 885
 886             /// Constructor initializes object calling \p std::srand()
 887             c_rand()
 888             {
 889                 std::srand(1);
 890             }
 891
 892             /// Returns next random number calling \p std::rand()
 893             result_type operator()()
 894             {
 895                 return (result_type) std::rand();
 896             }
 897         };
 898     } // namespace v
 899
 900 }} // namespace cds::opt
 901
 902
 903 // ****************************************************
 904 // Options metafunctions
 905
 906 namespace cds { namespace opt {
 907
 908     //@cond
 909     namespace details {
 910         template <typename OptionList, typename Option>
 911         struct do_pack
 912         {
 913             // Use "pack" member template to pack options
 914             typedef typename Option::template pack<OptionList> type;
 915         };
 916
 917         template <typename ...T> class typelist;
 918
 919         template <typename Typelist> struct typelist_head;
 920         template <typename Head, typename ...Tail>
 921         struct typelist_head< typelist<Head, Tail...> > {
 922             typedef Head type;
 923         };
 924         template <typename Head>
 925         struct typelist_head< typelist<Head> > {
 926             typedef Head type;
 927         };
 928
 929         template <typename Typelist> struct typelist_tail;
 930         template <typename Head, typename ...Tail>
 931         struct typelist_tail< typelist<Head, Tail...> > {
 932             typedef typelist<Tail...> type;
 933         };
 934         template <typename Head>
 935         struct typelist_tail< typelist<Head> > {
 936             typedef typelist<> type;
 937         };
 938
 939         template <typename OptionList, typename Typelist>
 940         struct make_options_impl {
 941             typedef typename make_options_impl<
 942                 typename do_pack<
 943                     OptionList,
 944                     typename typelist_head< Typelist >::type
 945                 >::type,
 946                 typename typelist_tail<Typelist>::type
 947             >::type type;
 948         };
 949
 950         template <typename OptionList>
 951         struct make_options_impl<OptionList, typelist<> > {
 952             typedef OptionList type;
 953         };
 954     }   // namespace details
 955     //@endcond
 956
 957     /// make_options metafunction
 958     /** @headerfile cds/opt/options.h
 959
 960         The metafunction converts option list \p Options to traits structure.
 961         The result of metafunction is \p type.
 962
 963         Template parameter \p OptionList is default option set (default traits).
 964         \p Options is option list.
 965     */
 966     template <typename OptionList, typename... Options>
 967     struct make_options {
 968 #ifdef CDS_DOXYGEN_INVOKED
 969         typedef implementation_defined type ;   ///< Result of the metafunction
 970 #else
 971         typedef typename details::make_options_impl< OptionList, details::typelist<Options...> >::type type;
 972 #endif
 973     };
 974
 975
 976     // *****************************************************************
 977     // find_type_traits metafunction
 978     // *****************************************************************
 979
 980     //@cond
 981     namespace details {
 982         template <typename... Options>
 983         struct find_type_traits_option;
 984
 985         template <>
 986         struct find_type_traits_option<> {
 987             typedef cds::opt::none  type;
 988         };
 989
 990         template <typename Any>
 991         struct find_type_traits_option< Any > {
 992             typedef cds::opt::none type;
 993         };
 994
 995         template <typename Any>
 996         struct find_type_traits_option< cds::opt::type_traits< Any > > {
 997             typedef Any type;
 998         };
 999
1000         template <typename Any, typename... Options>
1001         struct find_type_traits_option< cds::opt::type_traits< Any >, Options... > {
1002             typedef Any type;
1003         };
1004
1005         template <typename Any, typename... Options>
1006         struct find_type_traits_option< Any, Options... > {
1007             typedef typename find_type_traits_option< Options... >::type type;
1008         };
1009     } // namespace details
1010     //@endcond
1011
1012     /// Metafunction to find opt::type_traits option in \p Options list
1013     /** @headerfile cds/opt/options.h
1014
1015         If \p Options contains \p opt::type_traits option then it is the metafunction result.
1016         Otherwise the result is \p DefaultOptons.
1017     */
1018     template <typename DefaultOptions, typename... Options>
1019     struct find_type_traits {
1020         typedef typename select_default< typename details::find_type_traits_option<Options...>::type, DefaultOptions>::type type ;  ///< Metafunction result
1021     };
1022
1023
1024     // *****************************************************************
1025     // find_option metafunction
1026     // *****************************************************************
1027
1028     //@cond
1029     namespace details {
1030         template <typename What, typename... Options>
1031         struct find_option;
1032
1033         struct compare_ok;
1034         struct compare_fail;
1035
1036         template <typename A, typename B>
1037         struct compare_option
1038         {
1039             typedef compare_fail type;
1040         };
1041
1042         template <template <typename> class Opt, typename A, typename B>
1043         struct compare_option< Opt<A>, Opt<B> >
1044         {
1045             typedef compare_ok   type;
1046         };
1047
1048         // Specializations for integral type of option
1049 #define CDS_FIND_OPTION_INTEGRAL_SPECIALIZATION_( _type ) template <template <_type> class What, _type A, _type B> \
1050         struct compare_option< What<A>, What<B> > { typedef compare_ok type ; };
1051
1052         // For user-defined enum types
1053 #define CDS_DECLARE_FIND_OPTION_INTEGRAL_SPECIALIZATION( _type ) namespace cds { namespace opt { namespace details { CDS_FIND_OPTION_INTEGRAL_SPECIALIZATION_(_type ) }}}
1054
1055         CDS_FIND_OPTION_INTEGRAL_SPECIALIZATION_(bool)
1056         CDS_FIND_OPTION_INTEGRAL_SPECIALIZATION_(char)
1057         CDS_FIND_OPTION_INTEGRAL_SPECIALIZATION_(unsigned char)
1058         CDS_FIND_OPTION_INTEGRAL_SPECIALIZATION_(signed char)
1059         CDS_FIND_OPTION_INTEGRAL_SPECIALIZATION_(short int)
1060         CDS_FIND_OPTION_INTEGRAL_SPECIALIZATION_(unsigned short int)
1061         CDS_FIND_OPTION_INTEGRAL_SPECIALIZATION_(int)
1062         CDS_FIND_OPTION_INTEGRAL_SPECIALIZATION_(unsigned int)
1063         CDS_FIND_OPTION_INTEGRAL_SPECIALIZATION_(long)
1064         CDS_FIND_OPTION_INTEGRAL_SPECIALIZATION_(unsigned long)
1065         CDS_FIND_OPTION_INTEGRAL_SPECIALIZATION_(long long)
1066         CDS_FIND_OPTION_INTEGRAL_SPECIALIZATION_(unsigned long long)
1067
1068
1069         template <typename CompResult, typename Ok, typename Fail>
1070         struct select_option
1071         {
1072             typedef Fail    type;
1073         };
1074
1075         template <typename Ok, typename Fail>
1076         struct select_option< compare_ok, Ok, Fail >
1077         {
1078             typedef Ok      type;
1079         };
1080
1081         template <typename What>
1082         struct find_option< What > {
1083             typedef What    type;
1084         };
1085
1086         template <typename What, typename Opt>
1087         struct find_option< What, Opt > {
1088             typedef typename select_option<
1089                 typename compare_option< What, Opt >::type
1090                 ,Opt
1091                 ,What
1092             >::type type;
1093         };
1094
1095         template <typename What, typename Opt, typename... Options>
1096         struct find_option< What, Opt, Options... > {
1097             typedef typename select_option<
1098                 typename compare_option< What, Opt >::type
1099                 ,Opt
1100                 ,typename find_option< What, Options... >::type
1101             >::type type;
1102         };
1103     } // namespace details
1104     //@endcond
1105
1106     /// Metafunction to find \p What option in \p Options list
1107     /** @headerfile cds/opt/options.h
1108
1109         If \p Options contains \p What< Val > option for any \p Val then the result is \p What< Val >
1110         Otherwise the result is \p What.
1111
1112         Example:
1113         \code
1114         #include <cds/opt/options.h>
1115         namespace co = cds::opt;
1116
1117         struct default_tag;
1118         struct tag_a;
1119         struct tag_b;
1120
1121         // Find option co::tag.
1122
1123         // res1 is co::tag< tag_a >
1124         typedef co::find_option< co::tag< default_tag >, co::gc< cds::gc::HP >, co::tag< tag_a > >::type res1;
1125
1126         // res2 is default co::tag< default_tag >
1127         typedef co::find_option< co::tag< default_tag >, co::less< x >, co::hash< H > >::type res2;
1128
1129         // Multiple option co::tag. The first option is selected
1130         // res3 is default co::tag< tag_a >
1131         typedef co::find_option< co::tag< default_tag >, co::tag< tag_a >, co::tag< tag_b > >::type res3;
1132
1133         \endcode
1134     */
1135     template <typename What, typename... Options>
1136     struct find_option {
1137         typedef typename details::find_option<What, Options...>::type   type ;  ///< Metafunction result
1138     };
1139
1140
1141     // *****************************************************************
1142     // select metafunction
1143     // *****************************************************************
1144
1145     //@cond
1146     namespace details {
1147
1148         template <typename What, typename... Pairs>
1149         struct select;
1150
1151         template <typename What, typename Value>
1152         struct select< What, What, Value>
1153         {
1154             typedef Value   type;
1155         };
1156
1157         template <typename What, typename Tag, typename Value>
1158         struct select<What, Tag, Value>
1159         {
1160             typedef What    type;
1161         };
1162
1163         template <typename What, typename Value, typename... Pairs>
1164         struct select< What, What, Value, Pairs...>
1165         {
1166             typedef Value   type;
1167         };
1168
1169         template <typename What, typename Tag, typename Value, typename... Pairs>
1170         struct select< What, Tag, Value, Pairs...>
1171         {
1172             typedef typename select<What, Pairs...>::type   type;
1173         };
1174     }   // namespace details
1175     //@endcond
1176
1177     /// Select option metafunction
1178     /** @headerfile cds/opt/options.h
1179
1180         Pseudocode:
1181         \code
1182         select <What, T1, R1, T2, R2, ... Tn, Rn> ::=
1183             if What == T1 then return R1
1184             if What == T2 then return R2
1185             ...
1186             if What == Tn then return Rn
1187             else return What
1188         \endcode
1189     */
1190     template <typename What, typename... Pairs>
1191     struct select {
1192         typedef typename details::select< What, Pairs...>::type  type    ;   ///< Metafunction result
1193     };
1194
1195 }}  // namespace cds::opt
1196
1197
1198 #endif  // #ifndef CDSLIB_OPT_OPTIONS_H