cds/opt/options.h

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