3 #ifndef __CDS_OPT_OPTIONS_H
4 #define __CDS_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::lock::Spin
54 typedef typename cds::opt::select_default< cds::opt::none, cds::lock::Spin >::type default_spin;
56 // spin_32bit is cds::lock::Spin32
57 typedef typename cds::opt::select_default< cds::lock::Spin32, cds::lock::Spin >::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] Back-off strategy option setter
182 Back-off strategy used in some algorithm.
183 See cds::backoff namespace for back-off explanation and supported interface.
185 template <typename Type>
188 template <class Base> struct pack: public Base
190 typedef Type back_off;
195 /// [type-option] Option setter for garbage collecting schema used
197 Possible values of \p GC template parameter are:
198 - cds::gc::HP - Hazard Pointer garbage collector
199 - cds::gc::DHP - Dynamic Hazard Pointer garbage collector
200 - cds::gc::none::GC - No garbage collector (not supported for some containers)
202 template <typename GC>
205 template <class Base> struct pack: public Base
212 /// [type-option] Option setter for an allocator
214 \p Type is allocator with \p std::allocator interface. Default is value of macro CDS_DEFAULT_ALLOCATOR
215 that, in turn, is \p std::allocator.
217 The \p libcds containers actively use rebinding to convert an allocator of one type to another. Thus,
218 you may specify any valid type as std::allocator's template parameter.
220 See also opt::node_allocator
222 template <typename Type>
225 template <typename Base> struct pack: public Base
227 typedef Type allocator;
232 /// [type-option] Option setter for node allocator
234 \p Type is allocator with \p std::allocator interface. Default is value of macro CDS_DEFAULT_ALLOCATOR
235 that, in turn, is \p std::allocator.
237 Many node-base containers require an allocator for maintaining data (container's node) and for internal use.
238 Sometimes, this types of allocator should be different for performance reason.
239 For example, we should like to allocate the node from a pool of preallocated nodes.
240 Such pool can be seen as the node allocator.
242 Usually, if a container supports \p opt::allocator and \p %opt::node_allocator options
243 and \p opt::node_allocator is not specified the \p %opt::allocator option is used for maintaining the nodes.
245 The \p libcds containers actively use rebinding to convert an allocator of one type to another. Thus,
246 you may specify any valid type as std::allocator's template parameter.
248 template <typename Type>
249 struct node_allocator {
251 template <typename Base> struct pack: public Base
253 typedef Type node_allocator;
258 /// [type-option] Option setter for item counting
260 Some data structure (for example, queues) has additional feature for item counting.
261 This option allows to set up appropriate item counting policy for that data structure.
263 Predefined option \p Type:
264 - atomicity::empty_item_counter - no item counting performed. It is default policy for many
266 - atomicity::item_counter - the class that provides atomically item counting
267 - opt::v::sequential_item_counter - simple non-atomic item counter. This item counter is not intended for
268 concurrent containers and may be used only if it is explicitly noted.
270 You may provide other implementation of atomicity::item_counter interface for your needs.
272 Note, the item counting in lock-free containers cannot be exact; for example, if
273 item counter for a container returns zero it is not mean that the container is empty.
274 Thus, item counter may be used for statistical purposes only.
276 template <typename Type>
277 struct item_counter {
279 template <typename Base> struct pack: public Base
281 typedef Type item_counter;
287 /// Sequential non-atomic item counter
289 This type of item counter is not intended for concurrent containers
290 and may be used only if it is explicitly noted.
292 class sequential_item_counter
295 typedef size_t counter_type ; ///< Counter type
297 counter_type m_nCounter ; ///< Counter
300 sequential_item_counter()
304 /// Returns current value of the counter
305 counter_type value() const
310 /// Same as \ref value() with relaxed memory ordering
311 operator counter_type() const
316 /// Increments the counter. Semantics: postincrement
322 /// Decrements the counter. Semantics: postdecrement
329 counter_type operator ++()
334 counter_type operator ++(int)
340 counter_type operator --()
345 counter_type operator --(int)
350 /// Resets count to 0
358 /// Special alignment constants for \ref cds::opt::alignment option
359 enum special_alignment {
360 no_special_alignment = 0, ///< no special alignment
361 cache_line_alignment = 1 ///< use cache line size defined in cds/user_setup/cache_line.h
364 /// [value-option] Alignment option setter
366 Alignment for some internal data of containers. May be useful to solve false sharing problem.
367 \p Value defines desired alignment and it may be power of two integer or predefined values from
368 \ref special_alignment enum.
370 template <unsigned int Value>
373 template <typename Base> struct pack: public Base
375 enum { alignment = Value };
382 template <typename Type, unsigned int Alignment>
383 struct alignment_setter {
384 typedef typename cds::details::aligned_type< Type, Alignment >::type type;
387 template <typename Type>
388 struct alignment_setter<Type, no_special_alignment> {
392 template <typename Type>
393 struct alignment_setter<Type, cache_line_alignment> {
394 typedef typename cds::details::aligned_type< Type, c_nCacheLineSize >::type type;
397 } // namespace details
400 /// Special padding constants for \p cds::opt::padding option
401 enum special_padding {
402 no_special_padding = 0, ///< no special padding
403 cache_line_padding = 1, ///< use cache line size defined in cds/user_setup/cache_line.h
405 /// Apply padding only for tiny data of size less than required padding
407 The flag means that if your data size is less than the casheline size, the padding is applyed.
408 Otherwise no padding will be applyed.
410 This flag is applyed for padding value:
412 cds::opt::padding< cds::opt::cache_line_padding | cds::opt::padding_tiny_data_only >;
413 cds::opt::padding< 256 | cds::opt::padding_tiny_data_only >;
416 padding_tiny_data_only = 0x80000000,
419 padding_flags = padding_tiny_data_only
423 /// [value-option] Padding option setter
425 The padding for the internal data of some containers. May be useful to solve false sharing problem.
426 \p Value defines desired padding and it may be power of two integer or predefined values from
427 \p special_padding enum.
429 template <unsigned int Value>
432 template <typename Base> struct pack: public Base
434 enum { padding = Value };
441 enum padding_vs_datasize {
442 padding_datasize_less,
443 padding_datasize_equal,
444 padding_datasize_greater
447 template < typename T, unsigned int Padding, bool NoPadding, padding_vs_datasize Relation, bool TinyOnly >
448 struct apply_padding_helper;
450 template <typename T, padding_vs_datasize Relation, bool TinyOnly >
451 struct apply_padding_helper < T, 0, true, Relation, TinyOnly >
458 template <typename T, unsigned int Padding, bool TinyOnly >
459 struct apply_padding_helper < T, Padding, false, padding_datasize_equal, TinyOnly >
466 template <typename T, unsigned int Padding, bool TinyOnly >
467 struct apply_padding_helper < T, Padding, false, padding_datasize_less, TinyOnly >
471 uint8_t pad_[Padding - sizeof( T )];
475 template <typename T, unsigned int Padding >
476 struct apply_padding_helper < T, Padding, false, padding_datasize_greater, false >
480 uint8_t pad_[Padding - sizeof( T ) % Padding];
484 template <typename T, unsigned int Padding >
485 struct apply_padding_helper < T, Padding, false, padding_datasize_greater, true >
492 template <typename T, unsigned int Padding >
496 enum { padding = Padding & ~padding_flags };
499 static CDS_CONSTEXPR const size_t c_nPadding =
500 static_cast<unsigned int>(padding) == static_cast<unsigned int>(cache_line_padding) ? cds::c_nCacheLineSize :
501 static_cast<unsigned int>(padding) == static_cast<unsigned int>(no_special_padding) ? 0 : padding;
503 static_assert( (c_nPadding & (c_nPadding - 1)) == 0, "Padding must be a power-of-two number" );
505 typedef typename apply_padding_helper< T,
508 sizeof( T ) < c_nPadding ? padding_datasize_less : sizeof( T ) == c_nPadding ? padding_datasize_equal : padding_datasize_greater,
509 (Padding & padding_tiny_data_only) != 0
513 } // namespace details
517 /// [type-option] Generic option setter for statisitcs
519 This option sets a type to gather statistics.
520 The option is generic - no predefined type(s) is provided.
521 The particular \p Type of statistics depends on internal structure of the object.
523 template <typename Type>
526 template <typename Base> struct pack: public Base
533 /// [type-option] Option setter for C++ memory model
535 The <b>cds</b> library supports following memory ordering constraints for atomic operations in container implementation:
536 - v::relaxed_ordering - relaxed C++ memory model. This mode supports full set of memory ordering constraints:
537 \p memory_order_relaxed, \p memory_order_acquire, \p memory_order_release and so on.
538 - v::sequential_consistent - sequentially consistent C++ memory model (default memory ordering for C++). In
539 this mode any memory ordering constraint maps to \p memory_order_seq_cst.
541 The \p Type template parameter can be v::relaxed_ordering or v::sequential_consistent.
543 You may mix different memory ordering options for different containers: one declare as sequentially consistent,
544 another declare as relaxed.
545 Usually, v::relaxed_ordering is the default memory ordering for <b>cds</b> containers.
547 template <typename Type>
548 struct memory_model {
550 template <typename Base> struct pack: public Base
552 typedef Type memory_model;
558 /// Relaxed memory ordering model
560 In this memory model the memory constraints are defined according to C++ Memory Model specification.
562 See opt::memory_model for explanations
564 struct relaxed_ordering {
567 // For new C++11 (cds-1.1.0)
568 static const atomics::memory_order memory_order_relaxed = atomics::memory_order_relaxed;
569 static const atomics::memory_order memory_order_consume = atomics::memory_order_consume;
570 static const atomics::memory_order memory_order_acquire = atomics::memory_order_acquire;
571 static const atomics::memory_order memory_order_release = atomics::memory_order_release;
572 static const atomics::memory_order memory_order_acq_rel = atomics::memory_order_acq_rel;
573 static const atomics::memory_order memory_order_seq_cst = atomics::memory_order_seq_cst;
577 /// Sequential consistent memory ordering model
579 In this memory model any memory constraint is equivalent to \p memory_order_seq_cst.
581 See opt::memory_model for explanations
583 struct sequential_consistent {
586 // For new C++11 (cds-1.1.0)
587 static const atomics::memory_order memory_order_relaxed = atomics::memory_order_seq_cst;
588 static const atomics::memory_order memory_order_consume = atomics::memory_order_seq_cst;
589 static const atomics::memory_order memory_order_acquire = atomics::memory_order_seq_cst;
590 static const atomics::memory_order memory_order_release = atomics::memory_order_seq_cst;
591 static const atomics::memory_order memory_order_acq_rel = atomics::memory_order_seq_cst;
592 static const atomics::memory_order memory_order_seq_cst = atomics::memory_order_seq_cst;
597 /// [type-option] Base type traits option setter
599 This option setter is intended generally for internal use for type rebinding.
601 template <typename Type>
604 template <typename Base> struct pack: public Base
606 typedef Type type_traits;
611 /// Resizing policy option
613 This option specifies the resizing policy that decides when to resize a container.
614 Used in some containers, for example, in container::StripedHashSet, intrusive::StripedHashSet.
616 The real resizing policy specified by \p Type does strongly depend on a container
617 that supports this option, see container documentation about possibly \p Type values.
619 template <typename Type>
620 struct resizing_policy {
622 template <typename Base> struct pack: public Base
624 typedef Type resizing_policy;
629 /// Copy policy option
631 The copy policy defines an item copying algorithm which is used, for example, when a container is resized.
632 It is very specific algorithm depending on type of the container.
634 template <typename Type>
637 template <typename Base> struct pack: public Base
639 typedef Type copy_policy;
644 /// Swap policy option
646 The swap policy specifies an algorithm for swapping two objects.
647 Usually, the default policy is \p std::swap (see opt::v::default_swap_policy):
651 template <typename T>
652 void operator ()( T& v1, T& v2 )
659 template <typename Type>
662 template <typename Base> struct pack: public Base
664 typedef Type swap_policy;
671 /// Default swap policy (see opt::swap_policy option)
673 The default swap policy is wrappr around \p std::swap algorithm.
675 struct default_swap_policy {
676 /// Performs swapping of \p v1 and \p v2 using \p std::swap algo
677 template <typename T>
678 void operator()( T& v1, T& v2 ) const
685 /// Move policy option
687 The move policy specifies an algorithm for moving object content.
688 In trivial case, it can be simple assignment.
690 The move interface is:
692 template <typename T>
694 void operator()( T& dest, T& src );
698 Note that in move algorithm the \p src source argument can be changed too.
699 So you can use move semantics.
701 Usually, the default move policy is opt::v::assignment_move_policy
703 template <typename Type>
706 template <typename Base> struct pack: public Base
708 typedef Type move_policy;
714 /// \ref opt::move_policy "Move policy" based on assignment operator
715 struct assignment_move_policy
717 /// <tt> dest = src </tt>
718 template <typename T>
719 void operator()( T& dest, T const& src ) const
726 /// [value-option] Enable sorting
728 This option enables (<tt>Enable = true</tt>) or disables (<tt>Enable == false</tt>)
729 sorting of a container.
731 template <bool Enable>
734 template <typename Base> struct pack: public Base
736 static bool const sort = Enable;
741 /// [type-option] Concurrent access policy
743 This option specifies synchronization strategy for fine-grained lock-based containers.
744 The option has no predefined \p Policy type.
745 For each container that accepts this option the range of available \p Policy types
748 template <typename Policy>
749 struct mutex_policy {
751 template <typename Base> struct pack: public Base
753 typedef Policy mutex_policy;
759 /// [type-option] Random number generator
761 The option specifies a random number generator.
762 \p Random can be any STL random number generator producing
763 unsigned integer: \p std::linear_congruential_engine,
764 \p std::mersenne_twister_engine, \p std::subtract_with_carry_engine
765 and so on, or opt::v::c_rand.
768 template <typename Random>
769 struct random_engine {
771 template <typename Base> struct pack: public Base
773 typedef Random random_engine;
779 /// \p rand() -base random number generator
781 This generator returns a pseudorandom integer in the range 0 to \p RAND_MAX (32767).
784 typedef unsigned int result_type; ///< Result type
786 /// Constructor initializes object calling \p srand()
792 /// Returns next random number calling \p rand()
793 result_type operator()()
795 return (result_type) rand();
802 template <typename Accessor>
803 struct key_accessor {
804 template <typename Base> struct pack: public Base
806 typedef Accessor key_accessor;
810 template <typename Traits, typename ReplaceWith, typename WhatReplace = none >
811 struct replace_key_accessor {
812 typedef typename std::conditional<
813 std::is_same< typename Traits::key_accessor, WhatReplace >::value,
814 typename opt::key_accessor< ReplaceWith >::template pack< Traits >,
820 }} // namespace cds::opt
822 #include <cds/opt/make_options_var.h>
824 #endif // #ifndef __CDS_OPT_OPTIONS_H