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