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;
412 } // namespace details
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
420 /// Apply padding only for tiny data of size less than required padding
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.
425 This flag is applyed for padding value:
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 >;
431 padding_tiny_data_only = 0x80000000,
434 padding_flags = padding_tiny_data_only
438 /// [value-option] Padding option setter
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.
444 template <unsigned int Value>
447 template <typename Base> struct pack: public Base
449 enum { padding = Value };
456 enum padding_vs_datasize {
457 padding_datasize_less,
458 padding_datasize_equal,
459 padding_datasize_greater
462 template < typename T, unsigned int Padding, bool NoPadding, padding_vs_datasize Relation, bool TinyOnly >
463 struct apply_padding_helper;
465 template <typename T, padding_vs_datasize Relation, bool TinyOnly >
466 struct apply_padding_helper < T, 0, true, Relation, TinyOnly >
473 template <typename T, unsigned int Padding, bool TinyOnly >
474 struct apply_padding_helper < T, Padding, false, padding_datasize_equal, TinyOnly >
481 template <typename T, unsigned int Padding, bool TinyOnly >
482 struct apply_padding_helper < T, Padding, false, padding_datasize_less, TinyOnly >
486 uint8_t pad_[Padding - sizeof( T )];
490 template <typename T, unsigned int Padding >
491 struct apply_padding_helper < T, Padding, false, padding_datasize_greater, false >
495 uint8_t pad_[Padding - sizeof( T ) % Padding];
499 template <typename T, unsigned int Padding >
500 struct apply_padding_helper < T, Padding, false, padding_datasize_greater, true >
507 template <typename T, unsigned int Padding >
511 enum { padding = Padding & ~padding_flags };
514 static CDS_CONSTEXPR const size_t c_nPadding =
515 static_cast<unsigned int>(padding) == static_cast<unsigned int>(cache_line_padding) ? cds::c_nCacheLineSize :
516 static_cast<unsigned int>(padding) == static_cast<unsigned int>(no_special_padding) ? 0 : padding;
518 static_assert( (c_nPadding & (c_nPadding - 1)) == 0, "Padding must be a power-of-two number" );
520 typedef typename apply_padding_helper< T,
523 sizeof( T ) < c_nPadding ? padding_datasize_less : sizeof( T ) == c_nPadding ? padding_datasize_equal : padding_datasize_greater,
524 (Padding & padding_tiny_data_only) != 0
528 } // namespace details
532 /// [type-option] Generic option setter for statisitcs
534 This option sets a type to gather statistics.
535 The option is generic - no predefined type(s) is provided.
536 The particular \p Type of statistics depends on internal structure of the object.
538 template <typename Type>
541 template <typename Base> struct pack: public Base
548 /// [type-option] Option setter for C++ memory model
550 The <b>cds</b> library supports following memory ordering constraints for atomic operations in container implementation:
551 - \p v::relaxed_ordering - relaxed C++ memory model. This mode supports full set of memory ordering constraints:
552 \p memory_order_relaxed, \p memory_order_acquire, \p memory_order_release and so on.
553 - \p v::sequential_consistent - sequentially consistent C++ memory model (default memory ordering for C++). In
554 this mode any memory ordering constraint maps to \p memory_order_seq_cst.
556 The \p Type template parameter can be \p v::relaxed_ordering or \p v::sequential_consistent.
558 You may mix different memory ordering options for different containers: one declare as sequentially consistent,
559 another declare as relaxed.
560 Usually, \p v::relaxed_ordering is the default memory ordering for <b>libcds</b> containers.
562 template <typename Type>
563 struct memory_model {
565 template <typename Base> struct pack: public Base
567 typedef Type memory_model;
573 /// Relaxed memory ordering model
575 In this memory model the memory constraints are defined according to C++ Memory Model specification:
576 each constraint is mapped to \p std::memory_order constraints one-to-one
578 See \p opt::memory_model for explanations
580 struct relaxed_ordering {
582 static const atomics::memory_order memory_order_relaxed = atomics::memory_order_relaxed;
583 static const atomics::memory_order memory_order_consume = atomics::memory_order_consume;
584 static const atomics::memory_order memory_order_acquire = atomics::memory_order_acquire;
585 static const atomics::memory_order memory_order_release = atomics::memory_order_release;
586 static const atomics::memory_order memory_order_acq_rel = atomics::memory_order_acq_rel;
587 static const atomics::memory_order memory_order_seq_cst = atomics::memory_order_seq_cst;
591 /// Sequential consistent memory ordering model
593 In this memory model any memory constraint is equivalent to \p memory_order_seq_cst.
595 See \p opt::memory_model for explanations
597 struct sequential_consistent {
599 static const atomics::memory_order memory_order_relaxed = atomics::memory_order_seq_cst;
600 static const atomics::memory_order memory_order_consume = atomics::memory_order_seq_cst;
601 static const atomics::memory_order memory_order_acquire = atomics::memory_order_seq_cst;
602 static const atomics::memory_order memory_order_release = atomics::memory_order_seq_cst;
603 static const atomics::memory_order memory_order_acq_rel = atomics::memory_order_seq_cst;
604 static const atomics::memory_order memory_order_seq_cst = atomics::memory_order_seq_cst;
608 /// Totally relaxed memory ordering model (do not use!)
610 In this memory model any memory constraint is equivalent to \p memory_order_relaxed.
611 @warning Do not use this model! It intended for testing purposes only
612 to verify debugging instruments like Thread Sanitizer.
614 See \p opt::memory_model for explanations
616 struct total_relaxed_ordering {
618 static const atomics::memory_order memory_order_relaxed = atomics::memory_order_relaxed;
619 static const atomics::memory_order memory_order_consume = atomics::memory_order_relaxed;
620 static const atomics::memory_order memory_order_acquire = atomics::memory_order_relaxed;
621 static const atomics::memory_order memory_order_release = atomics::memory_order_relaxed;
622 static const atomics::memory_order memory_order_acq_rel = atomics::memory_order_relaxed;
623 static const atomics::memory_order memory_order_seq_cst = atomics::memory_order_relaxed;
628 /// [type-option] Base type traits option setter
630 This option setter is intended generally for internal use for type rebinding.
632 template <typename Type>
635 template <typename Base> struct pack: public Base
637 typedef Type type_traits;
642 /// Resizing policy option
644 This option specifies the resizing policy that decides when to resize a container.
645 Used in some containers, for example, in container::StripedHashSet, intrusive::StripedHashSet.
647 The real resizing policy specified by \p Type does strongly depend on a container
648 that supports this option, see container documentation about possibly \p Type values.
650 template <typename Type>
651 struct resizing_policy {
653 template <typename Base> struct pack: public Base
655 typedef Type resizing_policy;
660 /// Copy policy option
662 The copy policy defines an item copying algorithm which is used, for example, when a container is resized.
663 It is very specific algorithm depending on type of the container.
665 template <typename Type>
668 template <typename Base> struct pack: public Base
670 typedef Type copy_policy;
675 /// Swap policy option
677 The swap policy specifies an algorithm for swapping two objects.
678 Usually, the default policy is \p std::swap (see opt::v::default_swap_policy):
682 template <typename T>
683 void operator ()( T& v1, T& v2 )
690 template <typename Type>
693 template <typename Base> struct pack: public Base
695 typedef Type swap_policy;
702 /// Default swap policy (see opt::swap_policy option)
704 The default swap policy is wrappr around \p std::swap algorithm.
706 struct default_swap_policy {
707 /// Performs swapping of \p v1 and \p v2 using \p std::swap algo
708 template <typename T>
709 void operator()( T& v1, T& v2 ) const
716 /// Move policy option
718 The move policy specifies an algorithm for moving object content.
719 In trivial case, it can be simple assignment.
721 The move interface is:
723 template <typename T>
725 void operator()( T& dest, T& src );
729 Note that in move algorithm the \p src source argument can be changed too.
730 So you can use move semantics.
732 Usually, the default move policy is opt::v::assignment_move_policy
734 template <typename Type>
737 template <typename Base> struct pack: public Base
739 typedef Type move_policy;
745 /// \ref opt::move_policy "Move policy" based on assignment operator
746 struct assignment_move_policy
748 /// <tt> dest = src </tt>
749 template <typename T>
750 void operator()( T& dest, T const& src ) const
757 /// [value-option] Enable sorting
759 This option enables (<tt>Enable = true</tt>) or disables (<tt>Enable == false</tt>)
760 sorting of a container.
762 template <bool Enable>
765 template <typename Base> struct pack: public Base
767 static bool const sort = Enable;
772 /// [type-option] Concurrent access policy
774 This option specifies synchronization strategy for fine-grained lock-based containers.
775 The option has no predefined \p Policy type.
776 For each container that accepts this option the range of available \p Policy types
779 template <typename Policy>
780 struct mutex_policy {
782 template <typename Base> struct pack: public Base
784 typedef Policy mutex_policy;
790 /// [type-option] Random number generator
792 The option specifies a random number generator.
793 \p Random can be any STL random number generator producing
794 unsigned integer: \p std::linear_congruential_engine,
795 \p std::mersenne_twister_engine, \p std::subtract_with_carry_engine
796 and so on, or opt::v::c_rand.
799 template <typename Random>
800 struct random_engine {
802 template <typename Base> struct pack: public Base
804 typedef Random random_engine;
810 /// \p rand() -base random number generator
812 This generator returns a pseudorandom integer in the range 0 to \p RAND_MAX (32767).
815 typedef unsigned int result_type; ///< Result type
817 /// Constructor initializes object calling \p srand()
823 /// Returns next random number calling \p rand()
824 result_type operator()()
826 return (result_type) rand();
833 template <typename Accessor>
834 struct key_accessor {
835 template <typename Base> struct pack: public Base
837 typedef Accessor key_accessor;
841 template <typename Traits, typename ReplaceWith, typename WhatReplace = none >
842 struct replace_key_accessor {
843 typedef typename std::conditional<
844 std::is_same< typename Traits::key_accessor, WhatReplace >::value,
845 typename opt::key_accessor< ReplaceWith >::template pack< Traits >,
851 }} // namespace cds::opt
853 #include <cds/opt/make_options_var.h>
855 #endif // #ifndef CDSLIB_OPT_OPTIONS_H