3 #ifndef CDSLIB_OPT_OPTIONS_H
4 #define CDSLIB_OPT_OPTIONS_H
7 Framework to define template options
10 2011.01.23 khizmax Created
13 #include <cds/details/aligned_type.h>
14 #include <cds/user_setup/allocator.h>
15 #include <cds/user_setup/cache_line.h>
16 #include <cds/algo/atomic.h>
17 #include <stdlib.h> // rand, srand
21 /// Framework to define template options
23 There are two kind of options:
24 - \p type-option - option that determines a data type. The template argument \p Type of the option is a type.
25 - \p value-option - option that determines a value. The template argument \p Value of the option is a value.
29 /// Predefined options value (generally, for the options that determine the data types)
32 /// Type indicates that an option is not specified and the default one should be used
36 template <class Base> struct pack: public Base
41 /// Metafunction for selecting default option value
44 - \p Option - option value
45 - \p Default - default option value
46 - \p Value - option value if \p Option is not opt::none
48 If \p Option is opt::none, the metafunction result is \p Default, otherwise
49 the result is \p Value.
53 // default_spin is cds::sync::spin
54 typedef typename cds::opt::select_default< cds::opt::none, cds::sync::spin >::type default_spin;
56 // spin_32bit is cds::sync::reentrant_spin32
57 typedef typename cds::opt::select_default< cds::opt::none, cds::sync::reentrant_spin32 >::type spin_32bit;
60 template <typename Option, typename Default, typename Value = Option>
63 typedef Value type ; ///< metafunction result
66 template <typename Default>
67 struct select_default< none, Default >
73 /// Metafunction to select option value
75 This metafunction is intended for extracting the value of the \p Option option.
78 #include <cds/opt/options.h>
79 #include <type_traits> // only for testing purpose (static_assert)
84 typedef cds::opt::tag< tag_a > tag_option;
86 // What is the value of the tag_option?
87 // How we can extract tag_a from tag_option?
88 // Here is a solution:
89 typedef cds::opt::value< tag_option >::tag tag_option_value;
91 // tag_option_value is the same as tag_a
92 static_assert( std::is_same< tag_option_value, tag_a >::value, "Error: tag_option_value != tag_a" );
96 template <typename Option>
97 struct value: public Option::template pack<none>
101 /// [type-option] Option setter specifies a tag
103 Suppose, you have a struct
108 and you want that your class \p X would be derived from several \p Feature:
110 class X: public Feature, public Feature
114 How can you distinguish one \p Feature from another?
115 You may use a tag option:
117 template <typename Tag>
123 class X: public Feature< tag_a >, public Feature< tag_b >
126 Now you can distinguish one \p Feature from another:
129 Feature<tag_a>& fa = static_cast< Feature<tag_a> >( x );
130 Feature<tag_b>& fb = static_cast< Feature<tag_b> >( x );
133 \p tag option setter allows you to do things like this for an option-centric approach:
135 template <typename ...Options>
141 class X: public Feature< tag<tag_a> >, public Feature< tag<tag_b> >
145 This option setter is widely used in cds::intrusive containers to distinguish
146 between different intrusive part of container's node.
148 An incomplete type can serve as a \p Tag.
150 template <typename Tag>
153 template<class Base> struct pack: public Base
160 /// [type-option] Option setter specifies lock class
162 Specification of the \p Type class is:
170 template <typename Type>
173 template<class Base> struct pack: public Base
175 typedef Type lock_type;
180 /// [type-option] @ref cds_sync_monitor "Monitor" type setter
182 This option setter specifyes @ref cds_sync_monitor "synchronization monitor"
183 for blocking container.
185 template <typename Type>
186 struct sync_monitor {
188 template <class Base> struct pack : public Base
190 typedef Type sync_monitor;
195 /// [type-option] Back-off strategy option setter
197 Back-off strategy used in some algorithm.
198 See cds::backoff namespace for back-off explanation and supported interface.
200 template <typename Type>
203 template <class Base> struct pack: public Base
205 typedef Type back_off;
210 /// [type-option] Option setter for garbage collecting schema used
212 Possible values of \p GC template parameter are:
213 - cds::gc::HP - Hazard Pointer garbage collector
214 - cds::gc::DHP - Dynamic Hazard Pointer garbage collector
215 - cds::gc::none::GC - No garbage collector (not supported for some containers)
217 template <typename GC>
220 template <class Base> struct pack: public Base
227 /// [type-option] Option setter for an allocator
229 \p Type is allocator with \p std::allocator interface. Default is value of macro CDS_DEFAULT_ALLOCATOR
230 that, in turn, is \p std::allocator.
232 The \p libcds containers actively use rebinding to convert an allocator of one type to another. Thus,
233 you may specify any valid type as std::allocator's template parameter.
235 See also opt::node_allocator
237 template <typename Type>
240 template <typename Base> struct pack: public Base
242 typedef Type allocator;
247 /// [type-option] Option setter for node allocator
249 \p Type is allocator with \p std::allocator interface. Default is value of macro CDS_DEFAULT_ALLOCATOR
250 that, in turn, is \p std::allocator.
252 Many node-base containers require an allocator for maintaining data (container's node) and for internal use.
253 Sometimes, this types of allocator should be different for performance reason.
254 For example, we should like to allocate the node from a pool of preallocated nodes.
255 Such pool can be seen as the node allocator.
257 Usually, if a container supports \p opt::allocator and \p %opt::node_allocator options
258 and \p opt::node_allocator is not specified the \p %opt::allocator option is used for maintaining the nodes.
260 The \p libcds containers actively use rebinding to convert an allocator of one type to another. Thus,
261 you may specify any valid type as std::allocator's template parameter.
263 template <typename Type>
264 struct node_allocator {
266 template <typename Base> struct pack: public Base
268 typedef Type node_allocator;
273 /// [type-option] Option setter for item counting
275 Some data structure (for example, queues) has additional feature for item counting.
276 This option allows to set up appropriate item counting policy for that data structure.
278 Predefined option \p Type:
279 - atomicity::empty_item_counter - no item counting performed. It is default policy for many
281 - atomicity::item_counter - the class that provides atomically item counting
282 - opt::v::sequential_item_counter - simple non-atomic item counter. This item counter is not intended for
283 concurrent containers and may be used only if it is explicitly noted.
285 You may provide other implementation of atomicity::item_counter interface for your needs.
287 Note, the item counting in lock-free containers cannot be exact; for example, if
288 item counter for a container returns zero it is not mean that the container is empty.
289 Thus, item counter may be used for statistical purposes only.
291 template <typename Type>
292 struct item_counter {
294 template <typename Base> struct pack: public Base
296 typedef Type item_counter;
302 /// Sequential non-atomic item counter
304 This type of item counter is not intended for concurrent containers
305 and may be used only if it is explicitly noted.
307 class sequential_item_counter
310 typedef size_t counter_type ; ///< Counter type
312 counter_type m_nCounter ; ///< Counter
315 sequential_item_counter()
319 /// Returns current value of the counter
320 counter_type value() const
325 /// Same as \ref value() with relaxed memory ordering
326 operator counter_type() const
331 /// Increments the counter. Semantics: postincrement
337 /// Decrements the counter. Semantics: postdecrement
344 counter_type operator ++()
349 counter_type operator ++(int)
355 counter_type operator --()
360 counter_type operator --(int)
365 /// Resets count to 0
373 /// Special alignment constants for \ref cds::opt::alignment option
374 enum special_alignment {
375 no_special_alignment = 0, ///< no special alignment
376 cache_line_alignment = 1 ///< use cache line size defined in cds/user_setup/cache_line.h
379 /// [value-option] Alignment option setter
381 Alignment for some internal data of containers. May be useful to solve false sharing problem.
382 \p Value defines desired alignment and it may be power of two integer or predefined values from
383 \ref special_alignment enum.
385 template <unsigned int Value>
388 template <typename Base> struct pack: public Base
390 enum { alignment = Value };
397 template <typename Type, unsigned int Alignment>
398 struct alignment_setter {
399 typedef typename cds::details::aligned_type< Type, Alignment >::type type;
402 template <typename Type>
403 struct alignment_setter<Type, no_special_alignment> {
407 template <typename Type>
408 struct alignment_setter<Type, cache_line_alignment> {
409 typedef typename cds::details::aligned_type< Type, c_nCacheLineSize >::type type;
411 } // namespace details
414 /// Special padding constants for \p cds::opt::padding option
415 enum special_padding {
416 no_special_padding = 0, ///< no special padding
417 cache_line_padding = 1, ///< use cache line size defined in cds/user_setup/cache_line.h
419 /// Apply padding only for tiny data of size less than required padding
421 The flag means that if your data size is less than the casheline size, the padding is applyed.
422 Otherwise no padding will be applyed.
424 This flag is applyed for padding value:
426 cds::opt::padding< cds::opt::cache_line_padding | cds::opt::padding_tiny_data_only >;
427 cds::opt::padding< 256 | cds::opt::padding_tiny_data_only >;
430 padding_tiny_data_only = 0x80000000,
433 padding_flags = padding_tiny_data_only
437 /// [value-option] Padding option setter
439 The padding for the internal data of some containers. May be useful to solve false sharing problem.
440 \p Value defines desired padding and it may be power of two integer or predefined values from
441 \p special_padding enum.
443 template <unsigned int Value>
446 template <typename Base> struct pack: public Base
448 enum { padding = Value };
455 enum padding_vs_datasize {
456 padding_datasize_less,
457 padding_datasize_equal,
458 padding_datasize_greater
461 template < typename T, unsigned int Padding, bool NoPadding, padding_vs_datasize Relation, bool TinyOnly >
462 struct apply_padding_helper;
464 template <typename T, padding_vs_datasize Relation, bool TinyOnly >
465 struct apply_padding_helper < T, 0, true, Relation, TinyOnly >
470 typedef void padding_type;
473 template <typename T, unsigned int Padding, bool TinyOnly >
474 struct apply_padding_helper < T, Padding, false, padding_datasize_equal, TinyOnly >
479 typedef void padding_type;
482 template <typename T, unsigned int Padding, bool TinyOnly >
483 struct apply_padding_helper < T, Padding, false, padding_datasize_less, TinyOnly >
485 typedef uint8_t padding_type[Padding - sizeof( T )];
493 template <typename T, unsigned int Padding >
494 struct apply_padding_helper < T, Padding, false, padding_datasize_greater, false >
496 typedef uint8_t padding_type[Padding - sizeof( T ) % Padding];
503 template <typename T, unsigned int Padding >
504 struct apply_padding_helper < T, Padding, false, padding_datasize_greater, true >
509 typedef void padding_type;
512 template <typename T, unsigned int Padding >
516 enum { padding = Padding & ~padding_flags };
519 static CDS_CONSTEXPR const size_t c_nPadding =
520 static_cast<unsigned int>(padding) == static_cast<unsigned int>(cache_line_padding) ? cds::c_nCacheLineSize :
521 static_cast<unsigned int>(padding) == static_cast<unsigned int>(no_special_padding) ? 0 : padding;
523 static_assert( (c_nPadding & (c_nPadding - 1)) == 0, "Padding must be a power-of-two number" );
525 typedef apply_padding_helper< T,
528 sizeof( T ) < c_nPadding ? padding_datasize_less : sizeof( T ) == c_nPadding ? padding_datasize_equal : padding_datasize_greater,
529 (Padding & padding_tiny_data_only) != 0
532 typedef typename result::type type;
534 typedef typename std::conditional<
535 std::is_same< typename result::padding_type, void >::value,
537 typename result::padding_type
538 >::type padding_type;
541 } // namespace details
545 /// [type-option] Generic option setter for statisitcs
547 This option sets a type to gather statistics.
548 The option is generic - no predefined type(s) is provided.
549 The particular \p Type of statistics depends on internal structure of the object.
551 template <typename Type>
554 template <typename Base> struct pack: public Base
561 /// [type-option] Option setter for C++ memory model
563 The <b>cds</b> library supports following memory ordering constraints for atomic operations in container implementation:
564 - \p v::relaxed_ordering - relaxed C++ memory model. This mode supports full set of memory ordering constraints:
565 \p memory_order_relaxed, \p memory_order_acquire, \p memory_order_release and so on.
566 - \p v::sequential_consistent - sequentially consistent C++ memory model (default memory ordering for C++). In
567 this mode any memory ordering constraint maps to \p memory_order_seq_cst.
569 The \p Type template parameter can be \p v::relaxed_ordering or \p v::sequential_consistent.
571 You may mix different memory ordering options for different containers: one declare as sequentially consistent,
572 another declare as relaxed.
573 Usually, \p v::relaxed_ordering is the default memory ordering for <b>libcds</b> containers.
575 template <typename Type>
576 struct memory_model {
578 template <typename Base> struct pack: public Base
580 typedef Type memory_model;
586 /// Relaxed memory ordering model
588 In this memory model the memory constraints are defined according to C++ Memory Model specification:
589 each constraint is mapped to \p std::memory_order constraints one-to-one
591 See \p opt::memory_model for explanations
593 struct relaxed_ordering {
595 static const atomics::memory_order memory_order_relaxed = atomics::memory_order_relaxed;
596 static const atomics::memory_order memory_order_consume = atomics::memory_order_consume;
597 static const atomics::memory_order memory_order_acquire = atomics::memory_order_acquire;
598 static const atomics::memory_order memory_order_release = atomics::memory_order_release;
599 static const atomics::memory_order memory_order_acq_rel = atomics::memory_order_acq_rel;
600 static const atomics::memory_order memory_order_seq_cst = atomics::memory_order_seq_cst;
604 /// Sequential consistent memory ordering model
606 In this memory model any memory constraint is equivalent to \p memory_order_seq_cst.
608 See \p opt::memory_model for explanations
610 struct sequential_consistent {
612 static const atomics::memory_order memory_order_relaxed = atomics::memory_order_seq_cst;
613 static const atomics::memory_order memory_order_consume = atomics::memory_order_seq_cst;
614 static const atomics::memory_order memory_order_acquire = atomics::memory_order_seq_cst;
615 static const atomics::memory_order memory_order_release = atomics::memory_order_seq_cst;
616 static const atomics::memory_order memory_order_acq_rel = atomics::memory_order_seq_cst;
617 static const atomics::memory_order memory_order_seq_cst = atomics::memory_order_seq_cst;
622 /// Totally relaxed memory ordering model (do not use!)
624 In this memory model any memory constraint is equivalent to \p memory_order_relaxed.
625 @warning Do not use this model! It intended for testing purposes only
626 to verify debugging instruments like Thread Sanitizer.
628 See \p opt::memory_model for explanations
630 struct total_relaxed_ordering {
631 static const atomics::memory_order memory_order_relaxed = atomics::memory_order_relaxed;
632 static const atomics::memory_order memory_order_consume = atomics::memory_order_relaxed;
633 static const atomics::memory_order memory_order_acquire = atomics::memory_order_relaxed;
634 static const atomics::memory_order memory_order_release = atomics::memory_order_relaxed;
635 static const atomics::memory_order memory_order_acq_rel = atomics::memory_order_relaxed;
636 static const atomics::memory_order memory_order_seq_cst = atomics::memory_order_relaxed;
641 /// [type-option] Base type traits option setter
643 This option setter is intended generally for internal use for type rebinding.
645 template <typename Type>
648 template <typename Base> struct pack: public Base
650 typedef Type type_traits;
655 /// Resizing policy option
657 This option specifies the resizing policy that decides when to resize a container.
658 Used in some containers, for example, in container::StripedHashSet, intrusive::StripedHashSet.
660 The real resizing policy specified by \p Type does strongly depend on a container
661 that supports this option, see container documentation about possibly \p Type values.
663 template <typename Type>
664 struct resizing_policy {
666 template <typename Base> struct pack: public Base
668 typedef Type resizing_policy;
673 /// Copy policy option
675 The copy policy defines an item copying algorithm which is used, for example, when a container is resized.
676 It is very specific algorithm depending on type of the container.
678 template <typename Type>
681 template <typename Base> struct pack: public Base
683 typedef Type copy_policy;
688 /// Swap policy option
690 The swap policy specifies an algorithm for swapping two objects.
691 Usually, the default policy is \p std::swap (see opt::v::default_swap_policy):
695 template <typename T>
696 void operator ()( T& v1, T& v2 )
703 template <typename Type>
706 template <typename Base> struct pack: public Base
708 typedef Type swap_policy;
715 /// Default swap policy (see opt::swap_policy option)
717 The default swap policy is wrappr around \p std::swap algorithm.
719 struct default_swap_policy {
720 /// Performs swapping of \p v1 and \p v2 using \p std::swap algo
721 template <typename T>
722 void operator()( T& v1, T& v2 ) const
729 /// Move policy option
731 The move policy specifies an algorithm for moving object content.
732 In trivial case, it can be simple assignment.
734 The move interface is:
736 template <typename T>
738 void operator()( T& dest, T& src );
742 Note that in move algorithm the \p src source argument can be changed too.
743 So you can use move semantics.
745 Usually, the default move policy is opt::v::assignment_move_policy
747 template <typename Type>
750 template <typename Base> struct pack: public Base
752 typedef Type move_policy;
758 /// \ref opt::move_policy "Move policy" based on assignment operator
759 struct assignment_move_policy
761 /// <tt> dest = src </tt>
762 template <typename T>
763 void operator()( T& dest, T const& src ) const
770 /// [value-option] Enable sorting
772 This option enables (<tt>Enable = true</tt>) or disables (<tt>Enable == false</tt>)
773 sorting of a container.
775 template <bool Enable>
778 template <typename Base> struct pack: public Base
780 static bool const sort = Enable;
785 /// [type-option] Concurrent access policy
787 This option specifies synchronization strategy for fine-grained lock-based containers.
788 The option has no predefined \p Policy type.
789 For each container that accepts this option the range of available \p Policy types
792 template <typename Policy>
793 struct mutex_policy {
795 template <typename Base> struct pack: public Base
797 typedef Policy mutex_policy;
803 /// [type-option] Random number generator
805 The option specifies a random number generator.
806 \p Random can be any STL random number generator producing
807 unsigned integer: \p std::linear_congruential_engine,
808 \p std::mersenne_twister_engine, \p std::subtract_with_carry_engine
809 and so on, or opt::v::c_rand.
812 template <typename Random>
813 struct random_engine {
815 template <typename Base> struct pack: public Base
817 typedef Random random_engine;
823 /// \p rand() -base random number generator
825 This generator returns a pseudorandom integer in the range 0 to \p RAND_MAX (32767).
828 typedef unsigned int result_type; ///< Result type
830 /// Constructor initializes object calling \p srand()
836 /// Returns next random number calling \p rand()
837 result_type operator()()
839 return (result_type) rand();
846 template <typename Accessor>
847 struct key_accessor {
848 template <typename Base> struct pack: public Base
850 typedef Accessor key_accessor;
854 template <typename Traits, typename ReplaceWith, typename WhatReplace = none >
855 struct replace_key_accessor {
856 typedef typename std::conditional<
857 std::is_same< typename Traits::key_accessor, WhatReplace >::value,
858 typename opt::key_accessor< ReplaceWith >::template pack< Traits >,
864 }} // namespace cds::opt
866 #include <cds/opt/make_options_var.h>
868 #endif // #ifndef CDSLIB_OPT_OPTIONS_H