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