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-2017
   5
   6     Source code repo: http://github.com/khizmax/libcds/
   7     Download: http://sourceforge.net/projects/libcds/files/
   8
   9     Redistribution and use in source and binary forms, with or without
  10     modification, are permitted provided that the following conditions are met:
  11
  12     * Redistributions of source code must retain the above copyright notice, this
  13       list of conditions and the following disclaimer.
  14
  15     * Redistributions in binary form must reproduce the above copyright notice,
  16       this list of conditions and the following disclaimer in the documentation
  17       and/or other materials provided with the distribution.
  18
  19     THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
  20     AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  21     IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  22     DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
  23     FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  24     DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
  25     SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
  26     CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
  27     OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  28     OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  29 */
  30
  31 #ifndef CDSLIB_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 cacheline 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     template <unsigned Padding>
 409     struct actual_padding
 410     {
 411         enum { value = Padding & ~padding_flags };
 412     };
 413
 414     template <>
 415     struct actual_padding<cache_line_padding>
 416     {
 417         enum { value = cds::c_nCacheLineSize };
 418     };
 419
 420     template <>
 421     struct actual_padding<cache_line_padding| padding_tiny_data_only>
 422     {
 423         enum { value = cds::c_nCacheLineSize };
 424     };
 425     //@endcond
 426
 427     //@cond
 428     namespace details {
 429         enum padding_vs_datasize {
 430             padding_datasize_less,
 431             padding_datasize_equal,
 432             padding_datasize_greater
 433         };
 434
 435         template < typename T, unsigned int Padding, bool NoPadding, padding_vs_datasize Relation, bool TinyOnly >
 436         struct apply_padding_helper;
 437
 438         template <typename T, padding_vs_datasize Relation, bool TinyOnly >
 439         struct apply_padding_helper < T, 0, true, Relation, TinyOnly >
 440         {
 441             struct type {
 442                 T   data;
 443             };
 444             typedef void padding_type;
 445         };
 446
 447         template <typename T, unsigned int Padding, bool TinyOnly >
 448         struct apply_padding_helper < T, Padding, false, padding_datasize_equal, TinyOnly >
 449         {
 450             struct type {
 451                 T   data;
 452             };
 453             typedef void padding_type;
 454         };
 455
 456         template <typename T, unsigned int Padding, bool TinyOnly >
 457         struct apply_padding_helper < T, Padding, false, padding_datasize_less, TinyOnly >
 458         {
 459             typedef uint8_t padding_type[Padding - sizeof( T )];
 460             struct type {
 461                 T data;
 462                 padding_type pad_;
 463             };
 464
 465         };
 466
 467         template <typename T, unsigned int Padding >
 468         struct apply_padding_helper < T, Padding, false, padding_datasize_greater, false >
 469         {
 470             typedef uint8_t padding_type[Padding - sizeof( T ) % Padding];
 471             struct type {
 472                 T data;
 473                 padding_type pad_;
 474             };
 475         };
 476
 477         template <typename T, unsigned int Padding >
 478         struct apply_padding_helper < T, Padding, false, padding_datasize_greater, true >
 479         {
 480             struct type {
 481                 T data;
 482             };
 483             typedef void padding_type;
 484         };
 485
 486         template <typename T, unsigned int Padding >
 487         struct apply_padding
 488         {
 489         private:
 490             enum { padding = Padding & ~padding_flags };
 491
 492         public:
 493             static CDS_CONSTEXPR const size_t c_nPadding =
 494                 static_cast<unsigned int>(padding) == static_cast<unsigned int>(cache_line_padding) ? cds::c_nCacheLineSize :
 495                 static_cast<unsigned int>(padding) == static_cast<unsigned int>(no_special_padding) ? 0 : padding;
 496
 497             static_assert( (c_nPadding & (c_nPadding - 1)) == 0, "Padding must be a power-of-two number" );
 498
 499             typedef apply_padding_helper< T,
 500                 c_nPadding,
 501                 c_nPadding == 0,
 502                 sizeof( T ) < c_nPadding ? padding_datasize_less : sizeof( T ) == c_nPadding ? padding_datasize_equal : padding_datasize_greater,
 503                 (Padding & padding_tiny_data_only) != 0
 504             > result;
 505
 506             typedef typename result::type type;
 507
 508             typedef typename std::conditional<
 509                 std::is_same< typename result::padding_type, void >::value,
 510                 unsigned int,
 511                 typename result::padding_type
 512             >::type padding_type;
 513         };
 514
 515     } // namespace details
 516     //@endcond
 517
 518
 519     /// [type-option] Generic option setter for statisitcs
 520     /**
 521         This option sets a type to gather statistics.
 522         The option is generic - no predefined type(s) is provided.
 523         The particular \p Type of statistics depends on internal structure of the object.
 524     */
 525     template <typename Type>
 526     struct stat {
 527         //@cond
 528         template <typename Base> struct pack: public Base
 529         {
 530             typedef Type stat;
 531         };
 532         //@endcond
 533     };
 534
 535     /// [type-option] Option setter for C++ memory model
 536     /**
 537         The <b>cds</b> library supports following memory ordering constraints for atomic operations in container implementation:
 538         - \p v::relaxed_ordering - relaxed C++ memory model. This mode supports full set of memory ordering constraints:
 539             \p memory_order_relaxed, \p memory_order_acquire, \p memory_order_release and so on.
 540         - \p v::sequential_consistent - sequentially consistent C++ memory model (default memory ordering for C++). In
 541             this mode any memory ordering constraint maps to \p memory_order_seq_cst.
 542
 543         The \p Type template parameter can be \p v::relaxed_ordering or \p v::sequential_consistent.
 544
 545         You may mix different memory ordering options for different containers: one declare as sequentially consistent,
 546         another declare as relaxed.
 547         Usually, \p v::relaxed_ordering is the default memory ordering for <b>libcds</b> containers.
 548     */
 549     template <typename Type>
 550     struct memory_model {
 551         //@cond
 552         template <typename Base> struct pack: public Base
 553         {
 554             typedef Type memory_model;
 555         };
 556         //@endcond
 557     };
 558
 559     /// [type-option] Base type traits option setter
 560     /**
 561         This option setter is intended generally for internal use for type rebinding.
 562     */
 563     template <typename Type>
 564     struct type_traits {
 565         //@cond
 566         template <typename Base> struct pack: public Base
 567         {
 568             typedef Type type_traits;
 569         };
 570         //@endcond
 571     };
 572
 573     /// Resizing policy option
 574     /**
 575         This option specifies the resizing policy that decides when to resize a container.
 576         Used in some containers, for example, in container::StripedHashSet, intrusive::StripedHashSet.
 577
 578         The real resizing policy specified by \p Type does strongly depend on a container
 579         that supports this option, see container documentation about possibly \p Type values.
 580     */
 581     template <typename Type>
 582     struct resizing_policy {
 583         //@cond
 584         template <typename Base> struct pack: public Base
 585         {
 586             typedef Type resizing_policy;
 587         };
 588         //@endcond
 589     };
 590
 591     /// Copy policy option
 592     /**
 593         The copy policy defines an item copying algorithm which is used, for example, when a container is resized.
 594         It is very specific algorithm depending on type of the container.
 595     */
 596     template <typename Type>
 597     struct copy_policy {
 598         //@cond
 599         template <typename Base> struct pack: public Base
 600         {
 601             typedef Type copy_policy;
 602         };
 603         //@endcond
 604     };
 605
 606     /// Swap policy option
 607     /**
 608         The swap policy specifies an algorithm for swapping two objects.
 609         Usually, the default policy is \p std::swap (see opt::v::default_swap_policy):
 610
 611         @code
 612         struct std_swap {
 613             template <typename T>
 614             void operator ()( T& v1, T& v2 )
 615             {
 616                 std::swap( v1, v2 );
 617             }
 618         };
 619         @endcode
 620     */
 621     template <typename Type>
 622     struct swap_policy {
 623         //@cond
 624         template <typename Base> struct pack: public Base
 625         {
 626             typedef Type swap_policy;
 627         };
 628         //@endcond
 629     };
 630
 631     /// Move policy option
 632     /**
 633         The move policy specifies an algorithm for moving object content.
 634         In trivial case, it can be simple assignment.
 635
 636         The move interface is:
 637         \code
 638         template <typename T>
 639         struct move_policy {
 640             void operator()( T& dest, T& src );
 641         };
 642         \endcode
 643
 644         Note that in move algorithm the \p src source argument can be changed too.
 645         So you can use move semantics.
 646
 647         Usually, the default move policy is opt::v::assignment_move_policy
 648     */
 649     template <typename Type>
 650     struct move_policy {
 651         //@cond
 652         template <typename Base> struct pack: public Base
 653         {
 654             typedef Type move_policy;
 655         };
 656         //@endcond
 657     };
 658
 659     /// [value-option] Enable sorting
 660     /**
 661         This option enables (<tt>Enable = true</tt>) or disables (<tt>Enable == false</tt>)
 662         sorting of a container.
 663     */
 664     template <bool Enable>
 665     struct sort {
 666         //@cond
 667         template <typename Base> struct pack: public Base
 668         {
 669             static bool const sort = Enable;
 670         };
 671         //@endcond
 672     };
 673
 674     /// [type-option] Concurrent access policy
 675     /**
 676         This option specifies synchronization strategy for fine-grained lock-based containers.
 677         The option has no predefined \p Policy type.
 678         For each container that accepts this option the range of available \p Policy types
 679         is unique.
 680     */
 681     template <typename Policy>
 682     struct mutex_policy {
 683         //@cond
 684         template <typename Base> struct pack: public Base
 685         {
 686             typedef Policy mutex_policy;
 687         };
 688         //@endcond
 689     };
 690
 691
 692     /// [type-option] Random number generator
 693     /**
 694         The option specifies a random number generator.
 695         \p Random can be any STL random number generator producing
 696         unsigned integer: \p std::linear_congruential_engine,
 697         \p std::mersenne_twister_engine, \p std::subtract_with_carry_engine
 698         and so on, or \p opt::v::c_rand.
 699
 700     */
 701     template <typename Random>
 702     struct random_engine {
 703         //@cond
 704         template <typename Base> struct pack: public Base
 705         {
 706             typedef Random random_engine;
 707         };
 708         //@endcond
 709     };
 710
 711     /// [type-option] Free-list implementation
 712     /**
 713         See \p cds::intrusive::FreeList for free-list interface
 714     */
 715     template <typename FreeList>
 716     struct free_list {
 717         //@cond
 718         template <typename Base> struct pack: public Base
 719         {
 720             typedef FreeList free_list;
 721         };
 722         //@endcond
 723     };
 724
 725     //@cond
 726     // For internal use
 727     template <typename Accessor>
 728     struct key_accessor {
 729         template <typename Base> struct pack: public Base
 730         {
 731             typedef Accessor key_accessor;
 732         };
 733     };
 734
 735     template <typename Traits, typename ReplaceWith, typename WhatReplace = none >
 736     struct replace_key_accessor {
 737         typedef typename std::conditional<
 738             std::is_same< typename Traits::key_accessor, WhatReplace >::value,
 739             typename opt::key_accessor< ReplaceWith >::template pack< Traits >,
 740             Traits
 741         >::type type;
 742     };
 743     //@endcond
 744
 745 }}  // namespace cds::opt
 746
 747
 748 // ****************************************************
 749 // Options predefined types and values
 750
 751 namespace cds { namespace opt {
 752
 753     /// Predefined options value
 754     namespace v {
 755
 756         /// Sequential non-atomic item counter
 757         /**
 758             This type of \p opt::item_counter option is not intended for concurrent containers
 759             and may be used only if it is explicitly noted.
 760         */
 761         class sequential_item_counter
 762         {
 763         public:
 764             typedef size_t counter_type    ;  ///< Counter type
 765         protected:
 766             counter_type  m_nCounter ;      ///< Counter
 767
 768         public:
 769             sequential_item_counter()
 770                 : m_nCounter(0)
 771             {}
 772
 773             /// Returns current value of the counter
 774             counter_type    value() const
 775             {
 776                 return m_nCounter;
 777             }
 778
 779             /// Same as \ref value() with relaxed memory ordering
 780             operator counter_type() const
 781             {
 782                 return value();
 783             }
 784
 785             /// Increments the counter. Semantics: postincrement
 786             counter_type inc()
 787             {
 788                 return m_nCounter++;
 789             }
 790
 791             /// Decrements the counter. Semantics: postdecrement
 792             counter_type dec()
 793             {
 794                 return m_nCounter--;
 795             }
 796
 797             /// Preincrement
 798             counter_type operator ++()
 799             {
 800                 return inc() + 1;
 801             }
 802             /// Postincrement
 803             counter_type operator ++(int)
 804             {
 805                 return inc();
 806             }
 807
 808             /// Predecrement
 809             counter_type operator --()
 810             {
 811                 return dec() - 1;
 812             }
 813             /// Postdecrement
 814             counter_type operator --(int)
 815             {
 816                 return dec();
 817             }
 818
 819             /// Resets count to 0
 820             void reset()
 821             {
 822                 m_nCounter = 0;
 823             }
 824         };
 825
 826         /// Relaxed memory ordering \p opt::memory_model
 827         /**
 828             In this ordering the memory constraints are defined according to C++ Memory Model specification:
 829             each constraint is mapped to \p std::memory_order constraints one-to-one
 830         */
 831         struct relaxed_ordering {
 832             //@cond
 833             static const atomics::memory_order memory_order_relaxed    = atomics::memory_order_relaxed;
 834             static const atomics::memory_order memory_order_consume    = atomics::memory_order_consume;
 835             static const atomics::memory_order memory_order_acquire    = atomics::memory_order_acquire;
 836             static const atomics::memory_order memory_order_release    = atomics::memory_order_release;
 837             static const atomics::memory_order memory_order_acq_rel    = atomics::memory_order_acq_rel;
 838             static const atomics::memory_order memory_order_seq_cst    = atomics::memory_order_seq_cst;
 839             //@endcond
 840         };
 841
 842         /// Sequential consistent \p opt::memory_memory ordering
 843         /**
 844             In this memory model any memory constraint is equivalent to \p std::memory_order_seq_cst.
 845         */
 846         struct sequential_consistent {
 847             //@cond
 848             static const atomics::memory_order memory_order_relaxed    = atomics::memory_order_seq_cst;
 849             static const atomics::memory_order memory_order_consume    = atomics::memory_order_seq_cst;
 850             static const atomics::memory_order memory_order_acquire    = atomics::memory_order_seq_cst;
 851             static const atomics::memory_order memory_order_release    = atomics::memory_order_seq_cst;
 852             static const atomics::memory_order memory_order_acq_rel    = atomics::memory_order_seq_cst;
 853             static const atomics::memory_order memory_order_seq_cst    = atomics::memory_order_seq_cst;
 854             //@endcond
 855         };
 856
 857         //@cond
 858         /// Totally relaxed \p opt::memory_model ordering (do not use!)
 859         /**
 860             In this memory model any memory constraint is equivalent to \p std::memory_order_relaxed.
 861             @warning Do not use this model! It intended for testing purposes only
 862             to verify debugging instruments like Thread Sanitizer.
 863         */
 864         struct total_relaxed_ordering {
 865             static const atomics::memory_order memory_order_relaxed    = atomics::memory_order_relaxed;
 866             static const atomics::memory_order memory_order_consume    = atomics::memory_order_relaxed;
 867             static const atomics::memory_order memory_order_acquire    = atomics::memory_order_relaxed;
 868             static const atomics::memory_order memory_order_release    = atomics::memory_order_relaxed;
 869             static const atomics::memory_order memory_order_acq_rel    = atomics::memory_order_relaxed;
 870             static const atomics::memory_order memory_order_seq_cst    = atomics::memory_order_relaxed;
 871         };
 872         //@endcond
 873
 874
 875         /// Default swap policy for \p opt::swap_policy option
 876         /**
 877             The default swap policy is wrappr around \p std::swap algorithm.
 878         */
 879         struct default_swap_policy {
 880             /// Performs swapping of \p v1 and \p v2 using \p std::swap algo
 881             template <typename T>
 882             void operator()( T& v1, T& v2 ) const
 883             {
 884                 std::swap( v1, v2 );
 885             }
 886         };
 887
 888         /// \p opt::move_policy based on move-assignment operator
 889         struct assignment_move_policy
 890         {
 891             /// <tt> dest = std::move( src ) </tt>
 892             template <typename T>
 893             void operator()( T& dest, T&& src ) const
 894             {
 895                 dest = std::move( src );
 896             }
 897         };
 898
 899         /// \p rand() -base random number generator for \p opt::random_engine
 900         /**
 901             This generator returns a pseudorandom integer in the range 0 to \p RAND_MAX (32767).
 902         */
 903         struct c_rand {
 904             typedef unsigned int result_type; ///< Result type
 905
 906             /// Constructor initializes object calling \p std::srand()
 907             c_rand()
 908             {
 909                 std::srand(1);
 910             }
 911
 912             /// Returns next random number calling \p std::rand()
 913             result_type operator()()
 914             {
 915                 return (result_type) std::rand();
 916             }
 917         };
 918     } // namespace v
 919
 920 }} // namespace cds::opt
 921
 922
 923 // ****************************************************
 924 // Options metafunctions
 925
 926 namespace cds { namespace opt {
 927
 928     //@cond
 929     namespace details {
 930         template <typename OptionList, typename Option>
 931         struct do_pack
 932         {
 933             // Use "pack" member template to pack options
 934             typedef typename Option::template pack<OptionList> type;
 935         };
 936
 937         template <typename ...T> class typelist;
 938
 939         template <typename Typelist> struct typelist_head;
 940         template <typename Head, typename ...Tail>
 941         struct typelist_head< typelist<Head, Tail...> > {
 942             typedef Head type;
 943         };
 944         template <typename Head>
 945         struct typelist_head< typelist<Head> > {
 946             typedef Head type;
 947         };
 948
 949         template <typename Typelist> struct typelist_tail;
 950         template <typename Head, typename ...Tail>
 951         struct typelist_tail< typelist<Head, Tail...> > {
 952             typedef typelist<Tail...> type;
 953         };
 954         template <typename Head>
 955         struct typelist_tail< typelist<Head> > {
 956             typedef typelist<> type;
 957         };
 958
 959         template <typename OptionList, typename Typelist>
 960         struct make_options_impl {
 961             typedef typename make_options_impl<
 962                 typename do_pack<
 963                     OptionList,
 964                     typename typelist_head< Typelist >::type
 965                 >::type,
 966                 typename typelist_tail<Typelist>::type
 967             >::type type;
 968         };
 969
 970         template <typename OptionList>
 971         struct make_options_impl<OptionList, typelist<> > {
 972             typedef OptionList type;
 973         };
 974     }   // namespace details
 975     //@endcond
 976
 977     /// make_options metafunction
 978     /** @headerfile cds/opt/options.h
 979
 980         The metafunction converts option list \p Options to traits structure.
 981         The result of metafunction is \p type.
 982
 983         Template parameter \p OptionList is default option set (default traits).
 984         \p Options is option list.
 985     */
 986     template <typename OptionList, typename... Options>
 987     struct make_options {
 988 #ifdef CDS_DOXYGEN_INVOKED
 989         typedef implementation_defined type ;   ///< Result of the metafunction
 990 #else
 991         typedef typename details::make_options_impl< OptionList, details::typelist<Options...> >::type type;
 992 #endif
 993     };
 994
 995
 996     // *****************************************************************
 997     // find_type_traits metafunction
 998     // *****************************************************************
 999
1000     //@cond
1001     namespace details {
1002         template <typename... Options>
1003         struct find_type_traits_option;
1004
1005         template <>
1006         struct find_type_traits_option<> {
1007             typedef cds::opt::none  type;
1008         };
1009
1010         template <typename Any>
1011         struct find_type_traits_option< Any > {
1012             typedef cds::opt::none type;
1013         };
1014
1015         template <typename Any>
1016         struct find_type_traits_option< cds::opt::type_traits< Any > > {
1017             typedef Any type;
1018         };
1019
1020         template <typename Any, typename... Options>
1021         struct find_type_traits_option< cds::opt::type_traits< Any >, Options... > {
1022             typedef Any type;
1023         };
1024
1025         template <typename Any, typename... Options>
1026         struct find_type_traits_option< Any, Options... > {
1027             typedef typename find_type_traits_option< Options... >::type type;
1028         };
1029     } // namespace details
1030     //@endcond
1031
1032     /// Metafunction to find opt::type_traits option in \p Options list
1033     /** @headerfile cds/opt/options.h
1034
1035         If \p Options contains \p opt::type_traits option then it is the metafunction result.
1036         Otherwise the result is \p DefaultOptons.
1037     */
1038     template <typename DefaultOptions, typename... Options>
1039     struct find_type_traits {
1040         typedef typename select_default< typename details::find_type_traits_option<Options...>::type, DefaultOptions>::type type ;  ///< Metafunction result
1041     };
1042
1043
1044     // *****************************************************************
1045     // find_option metafunction
1046     // *****************************************************************
1047
1048     //@cond
1049     namespace details {
1050         template <typename What, typename... Options>
1051         struct find_option;
1052
1053         struct compare_ok;
1054         struct compare_fail;
1055
1056         template <typename A, typename B>
1057         struct compare_option
1058         {
1059             typedef compare_fail type;
1060         };
1061
1062         template <template <typename> class Opt, typename A, typename B>
1063         struct compare_option< Opt<A>, Opt<B> >
1064         {
1065             typedef compare_ok   type;
1066         };
1067
1068         // Specializations for integral type of option
1069 #define CDS_FIND_OPTION_INTEGRAL_SPECIALIZATION_( _type ) template <template <_type> class What, _type A, _type B> \
1070         struct compare_option< What<A>, What<B> > { typedef compare_ok type ; };
1071
1072         // For user-defined enum types
1073 #define CDS_DECLARE_FIND_OPTION_INTEGRAL_SPECIALIZATION( _type ) namespace cds { namespace opt { namespace details { CDS_FIND_OPTION_INTEGRAL_SPECIALIZATION_(_type ) }}}
1074
1075         CDS_FIND_OPTION_INTEGRAL_SPECIALIZATION_(bool)
1076         CDS_FIND_OPTION_INTEGRAL_SPECIALIZATION_(char)
1077         CDS_FIND_OPTION_INTEGRAL_SPECIALIZATION_(unsigned char)
1078         CDS_FIND_OPTION_INTEGRAL_SPECIALIZATION_(signed char)
1079         CDS_FIND_OPTION_INTEGRAL_SPECIALIZATION_(short int)
1080         CDS_FIND_OPTION_INTEGRAL_SPECIALIZATION_(unsigned short int)
1081         CDS_FIND_OPTION_INTEGRAL_SPECIALIZATION_(int)
1082         CDS_FIND_OPTION_INTEGRAL_SPECIALIZATION_(unsigned int)
1083         CDS_FIND_OPTION_INTEGRAL_SPECIALIZATION_(long)
1084         CDS_FIND_OPTION_INTEGRAL_SPECIALIZATION_(unsigned long)
1085         CDS_FIND_OPTION_INTEGRAL_SPECIALIZATION_(long long)
1086         CDS_FIND_OPTION_INTEGRAL_SPECIALIZATION_(unsigned long long)
1087
1088
1089         template <typename CompResult, typename Ok, typename Fail>
1090         struct select_option
1091         {
1092             typedef Fail    type;
1093         };
1094
1095         template <typename Ok, typename Fail>
1096         struct select_option< compare_ok, Ok, Fail >
1097         {
1098             typedef Ok      type;
1099         };
1100
1101         template <typename What>
1102         struct find_option< What > {
1103             typedef What    type;
1104         };
1105
1106         template <typename What, typename Opt>
1107         struct find_option< What, Opt > {
1108             typedef typename select_option<
1109                 typename compare_option< What, Opt >::type
1110                 ,Opt
1111                 ,What
1112             >::type type;
1113         };
1114
1115         template <typename What, typename Opt, typename... Options>
1116         struct find_option< What, Opt, Options... > {
1117             typedef typename select_option<
1118                 typename compare_option< What, Opt >::type
1119                 ,Opt
1120                 ,typename find_option< What, Options... >::type
1121             >::type type;
1122         };
1123     } // namespace details
1124     //@endcond
1125
1126     /// Metafunction to find \p What option in \p Options list
1127     /** @headerfile cds/opt/options.h
1128
1129         If \p Options contains \p What< Val > option for any \p Val then the result is \p What< Val >
1130         Otherwise the result is \p What.
1131
1132         Example:
1133         \code
1134         #include <cds/opt/options.h>
1135         namespace co = cds::opt;
1136
1137         struct default_tag;
1138         struct tag_a;
1139         struct tag_b;
1140
1141         // Find option co::tag.
1142
1143         // res1 is co::tag< tag_a >
1144         typedef co::find_option< co::tag< default_tag >, co::gc< cds::gc::HP >, co::tag< tag_a > >::type res1;
1145
1146         // res2 is default co::tag< default_tag >
1147         typedef co::find_option< co::tag< default_tag >, co::less< x >, co::hash< H > >::type res2;
1148
1149         // Multiple option co::tag. The first option is selected
1150         // res3 is default co::tag< tag_a >
1151         typedef co::find_option< co::tag< default_tag >, co::tag< tag_a >, co::tag< tag_b > >::type res3;
1152
1153         \endcode
1154     */
1155     template <typename What, typename... Options>
1156     struct find_option {
1157         typedef typename details::find_option<What, Options...>::type   type ;  ///< Metafunction result
1158     };
1159
1160
1161     // *****************************************************************
1162     // select metafunction
1163     // *****************************************************************
1164
1165     //@cond
1166     namespace details {
1167
1168         template <typename What, typename... Pairs>
1169         struct select;
1170
1171         template <typename What, typename Value>
1172         struct select< What, What, Value>
1173         {
1174             typedef Value   type;
1175         };
1176
1177         template <typename What, typename Tag, typename Value>
1178         struct select<What, Tag, Value>
1179         {
1180             typedef What    type;
1181         };
1182
1183         template <typename What, typename Value, typename... Pairs>
1184         struct select< What, What, Value, Pairs...>
1185         {
1186             typedef Value   type;
1187         };
1188
1189         template <typename What, typename Tag, typename Value, typename... Pairs>
1190         struct select< What, Tag, Value, Pairs...>
1191         {
1192             typedef typename select<What, Pairs...>::type   type;
1193         };
1194     }   // namespace details
1195     //@endcond
1196
1197     /// Select option metafunction
1198     /** @headerfile cds/opt/options.h
1199
1200         Pseudocode:
1201         \code
1202         select <What, T1, R1, T2, R2, ... Tn, Rn> ::=
1203             if What == T1 then return R1
1204             if What == T2 then return R2
1205             ...
1206             if What == Tn then return Rn
1207             else return What
1208         \endcode
1209     */
1210     template <typename What, typename... Pairs>
1211     struct select {
1212         typedef typename details::select< What, Pairs...>::type  type    ;   ///< Metafunction result
1213     };
1214
1215 }}  // namespace cds::opt
1216
1217
1218 #endif  // #ifndef CDSLIB_OPT_OPTIONS_H