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/cxx11_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::HRC - Gidenstam's garbage collector
200 - cds::gc::PTB - Pass-the-Buck garbage collector
201 - cds::gc::none::GC - No garbage collector (not supported for some containers)
203 template <typename GC>
206 template <class Base> struct pack: public Base
213 /// [type-option] Option setter for an allocator
215 \p Type is allocator with \p std::allocator interface. Default is value of macro CDS_DEFAULT_ALLOCATOR
216 that, in turn, is \p std::allocator.
218 The \p libcds containers actively use rebinding to convert an allocator of one type to another. Thus,
219 you may specify any valid type as std::allocator's template parameter.
221 See also opt::node_allocator
223 template <typename Type>
226 template <typename Base> struct pack: public Base
228 typedef Type allocator;
233 /// [type-option] Option setter for node allocator
235 \p Type is allocator with \p std::allocator interface. Default is value of macro CDS_DEFAULT_ALLOCATOR
236 that, in turn, is \p std::allocator.
238 Many node-base containers require an allocator for maintaining data (container's node) and for internal use.
239 Sometimes, this types of allocator should be different for performance reason.
240 For example, we should like to allocate the node from a pool of preallocated nodes.
241 Such pool can be seen as the node allocator.
243 Usually, if a container supports \p opt::allocator and \p %opt::node_allocator options
244 and \p opt::node_allocator is not specified the \p %opt::allocator option is used for maintaining the nodes.
246 The \p libcds containers actively use rebinding to convert an allocator of one type to another. Thus,
247 you may specify any valid type as std::allocator's template parameter.
249 template <typename Type>
250 struct node_allocator {
252 template <typename Base> struct pack: public Base
254 typedef Type node_allocator;
259 /// [type-option] Option setter for item counting
261 Some data structure (for example, queues) has additional feature for item counting.
262 This option allows to set up appropriate item counting policy for that data structure.
264 Predefined option \p Type:
265 - atomicity::empty_item_counter - no item counting performed. It is default policy for many
267 - atomicity::item_counter - the class that provides atomically item counting
268 - opt::v::sequential_item_counter - simple non-atomic item counter. This item counter is not intended for
269 concurrent containers and may be used only if it is explicitly noted.
271 You may provide other implementation of atomicity::item_counter interface for your needs.
273 Note, the item counting in lock-free containers cannot be exact; for example, if
274 item counter for a container returns zero it is not mean that the container is empty.
275 Thus, item counter may be used for statistical purposes only.
277 template <typename Type>
278 struct item_counter {
280 template <typename Base> struct pack: public Base
282 typedef Type item_counter;
288 /// Sequential non-atomic item counter
290 This type of item counter is not intended for concurrent containers
291 and may be used only if it is explicitly noted.
293 class sequential_item_counter
296 typedef size_t counter_type ; ///< Counter type
298 counter_type m_nCounter ; ///< Counter
301 sequential_item_counter()
305 /// Returns current value of the counter
306 counter_type value() const
311 /// Same as \ref value() with relaxed memory ordering
312 operator counter_type() const
317 /// Increments the counter. Semantics: postincrement
323 /// Decrements the counter. Semantics: postdecrement
330 counter_type operator ++()
335 counter_type operator ++(int)
341 counter_type operator --()
346 counter_type operator --(int)
351 /// Resets count to 0
359 /// Special alignment constants for \ref cds::opt::alignment option
360 enum special_alignment {
361 no_special_alignment = 0, ///< no special alignment
362 cache_line_alignment = 1 ///< use cache line size defined in cds/user_setup/cache_line.h
365 /// [value-option] Alignment option setter
367 Alignment for some internal data of containers. May be useful to solve false sharing problem.
368 \p Value defines desired alignment and it may be power of two integer or predefined values from
369 \ref special_alignment enum.
371 template <unsigned int Value>
374 template <typename Base> struct pack: public Base
376 enum { alignment = Value };
383 template <typename Type, unsigned int Alignment>
384 struct alignment_setter {
385 typedef typename cds::details::aligned_type< Type, Alignment >::type type;
388 template <typename Type>
389 struct alignment_setter<Type, no_special_alignment> {
393 template <typename Type>
394 struct alignment_setter<Type, cache_line_alignment> {
395 typedef typename cds::details::aligned_type< Type, c_nCacheLineSize >::type type;
398 } // namespace details
401 /// Special padding constants for \p cds::opt::padding option
402 enum special_padding {
403 no_special_padding = 0, ///< no special padding
404 cache_line_padding = 1, ///< use cache line size defined in cds/user_setup/cache_line.h
406 /// Apply padding only for tiny data of size less than required padding
408 The flag means that if your data size is less than the casheline size, the padding is applyed.
409 Otherwise no padding will be applyed.
411 This flag is applyed for padding value:
413 cds::opt::padding< cds::opt::cache_line_padding | cds::opt::padding_tiny_data_only >;
414 cds::opt::padding< 256 | cds::opt::padding_tiny_data_only >;
417 padding_tiny_data_only = 0x80000000,
420 padding_flags = padding_tiny_data_only
424 /// [value-option] Padding option setter
426 The padding for the internal data of some containers. May be useful to solve false sharing problem.
427 \p Value defines desired padding and it may be power of two integer or predefined values from
428 \p special_padding enum.
430 template <unsigned int Value>
433 template <typename Base> struct pack: public Base
435 enum { padding = Value };
442 enum padding_vs_datasize {
443 padding_datasize_less,
444 padding_datasize_equal,
445 padding_datasize_greater
448 template < typename T, unsigned int Padding, bool NoPadding, padding_vs_datasize Relation, bool TinyOnly >
449 struct apply_padding_helper;
451 template <typename T, padding_vs_datasize Relation, bool TinyOnly >
452 struct apply_padding_helper < T, 0, true, Relation, TinyOnly >
459 template <typename T, unsigned int Padding, bool TinyOnly >
460 struct apply_padding_helper < T, Padding, false, padding_datasize_equal, TinyOnly >
467 template <typename T, unsigned int Padding, bool TinyOnly >
468 struct apply_padding_helper < T, Padding, false, padding_datasize_less, TinyOnly >
472 uint8_t pad_[Padding - sizeof( T )];
476 template <typename T, unsigned int Padding >
477 struct apply_padding_helper < T, Padding, false, padding_datasize_greater, false >
481 uint8_t pad_[Padding - sizeof( T ) % Padding];
485 template <typename T, unsigned int Padding >
486 struct apply_padding_helper < T, Padding, false, padding_datasize_greater, true >
493 template <typename T, unsigned int Padding >
497 enum { padding = Padding & ~padding_flags };
500 static CDS_CONSTEXPR const size_t c_nPadding =
501 static_cast<unsigned int>(padding) == static_cast<unsigned int>(cache_line_padding) ? cds::c_nCacheLineSize :
502 static_cast<unsigned int>(padding) == static_cast<unsigned int>(no_special_padding) ? 0 : padding;
504 static_assert( (c_nPadding & (c_nPadding - 1)) == 0, "Padding must be a power-of-two number" );
506 typedef typename apply_padding_helper< T,
509 sizeof( T ) < c_nPadding ? padding_datasize_less : sizeof( T ) == c_nPadding ? padding_datasize_equal : padding_datasize_greater,
510 (Padding & padding_tiny_data_only) != 0
514 } // namespace details
518 /// [type-option] Generic option setter for statisitcs
520 This option sets a type to gather statistics.
521 The option is generic - no predefined type(s) is provided.
522 The particular \p Type of statistics depends on internal structure of the object.
524 template <typename Type>
527 template <typename Base> struct pack: public Base
534 /// [type-option] Option setter for C++ memory model
536 The <b>cds</b> library supports following memory ordering constraints for atomic operations in container implementation:
537 - v::relaxed_ordering - relaxed C++ memory model. This mode supports full set of memory ordering constraints:
538 \p memory_order_relaxed, \p memory_order_acquire, \p memory_order_release and so on.
539 - v::sequential_consistent - sequentially consistent C++ memory model (default memory ordering for C++). In
540 this mode any memory ordering constraint maps to \p memory_order_seq_cst.
542 The \p Type template parameter can be v::relaxed_ordering or v::sequential_consistent.
544 You may mix different memory ordering options for different containers: one declare as sequentially consistent,
545 another declare as relaxed.
546 Usually, v::relaxed_ordering is the default memory ordering for <b>cds</b> containers.
548 template <typename Type>
549 struct memory_model {
551 template <typename Base> struct pack: public Base
553 typedef Type memory_model;
559 /// Relaxed memory ordering model
561 In this memory model the memory constraints are defined according to C++ Memory Model specification.
563 See opt::memory_model for explanations
565 struct relaxed_ordering {
568 // For new C++11 (cds-1.1.0)
569 static const atomics::memory_order memory_order_relaxed = atomics::memory_order_relaxed;
570 static const atomics::memory_order memory_order_consume = atomics::memory_order_consume;
571 static const atomics::memory_order memory_order_acquire = atomics::memory_order_acquire;
572 static const atomics::memory_order memory_order_release = atomics::memory_order_release;
573 static const atomics::memory_order memory_order_acq_rel = atomics::memory_order_acq_rel;
574 static const atomics::memory_order memory_order_seq_cst = atomics::memory_order_seq_cst;
578 /// Sequential consistent memory ordering model
580 In this memory model any memory constraint is equivalent to \p memory_order_seq_cst.
582 See opt::memory_model for explanations
584 struct sequential_consistent {
587 // For new C++11 (cds-1.1.0)
588 static const atomics::memory_order memory_order_relaxed = atomics::memory_order_seq_cst;
589 static const atomics::memory_order memory_order_consume = atomics::memory_order_seq_cst;
590 static const atomics::memory_order memory_order_acquire = atomics::memory_order_seq_cst;
591 static const atomics::memory_order memory_order_release = atomics::memory_order_seq_cst;
592 static const atomics::memory_order memory_order_acq_rel = atomics::memory_order_seq_cst;
593 static const atomics::memory_order memory_order_seq_cst = atomics::memory_order_seq_cst;
598 /// [type-option] Base type traits option setter
600 This option setter is intended generally for internal use for type rebinding.
602 template <typename Type>
605 template <typename Base> struct pack: public Base
607 typedef Type type_traits;
612 /// Resizing policy option
614 This option specifies the resizing policy that decides when to resize a container.
615 Used in some containers, for example, in container::StripedHashSet, intrusive::StripedHashSet.
617 The real resizing policy specified by \p Type does strongly depend on a container
618 that supports this option, see container documentation about possibly \p Type values.
620 template <typename Type>
621 struct resizing_policy {
623 template <typename Base> struct pack: public Base
625 typedef Type resizing_policy;
630 /// Copy policy option
632 The copy policy defines an item copying algorithm which is used, for example, when a container is resized.
633 It is very specific algorithm depending on type of the container.
635 template <typename Type>
638 template <typename Base> struct pack: public Base
640 typedef Type copy_policy;
645 /// Swap policy option
647 The swap policy specifies an algorithm for swapping two objects.
648 Usually, the default policy is \p std::swap (see opt::v::default_swap_policy):
652 template <typename T>
653 void operator ()( T& v1, T& v2 )
660 template <typename Type>
663 template <typename Base> struct pack: public Base
665 typedef Type swap_policy;
672 /// Default swap policy (see opt::swap_policy option)
674 The default swap policy is wrappr around \p std::swap algorithm.
676 struct default_swap_policy {
677 /// Performs swapping of \p v1 and \p v2 using \p std::swap algo
678 template <typename T>
679 void operator()( T& v1, T& v2 ) const
686 /// Move policy option
688 The move policy specifies an algorithm for moving object content.
689 In trivial case, it can be simple assignment.
691 The move interface is:
693 template <typename T>
695 void operator()( T& dest, T& src );
699 Note that in move algorithm the \p src source argument can be changed too.
700 So you can use move semantics.
702 Usually, the default move policy is opt::v::assignment_move_policy
704 template <typename Type>
707 template <typename Base> struct pack: public Base
709 typedef Type move_policy;
715 /// \ref opt::move_policy "Move policy" based on assignment operator
716 struct assignment_move_policy
718 /// <tt> dest = src </tt>
719 template <typename T>
720 void operator()( T& dest, T const& src ) const
727 /// [value-option] Enable sorting
729 This option enables (<tt>Enable = true</tt>) or disables (<tt>Enable == false</tt>)
730 sorting of a container.
732 template <bool Enable>
735 template <typename Base> struct pack: public Base
737 static bool const sort = Enable;
742 /// [type-option] Concurrent access policy
744 This option specifies synchronization strategy for fine-grained lock-based containers.
745 The option has no predefined \p Policy type.
746 For each container that accepts this option the range of available \p Policy types
749 template <typename Policy>
750 struct mutex_policy {
752 template <typename Base> struct pack: public Base
754 typedef Policy mutex_policy;
760 /// [type-option] Random number generator
762 The option specifies a random number generator.
763 \p Random can be any STL random number generator producing
764 unsigned integer: \p std::linear_congruential_engine,
765 \p std::mersenne_twister_engine, \p std::subtract_with_carry_engine
766 and so on, or opt::v::c_rand.
769 template <typename Random>
770 struct random_engine {
772 template <typename Base> struct pack: public Base
774 typedef Random random_engine;
780 /// \p rand() -base random number generator
782 This generator returns a pseudorandom integer in the range 0 to \p RAND_MAX (32767).
785 typedef unsigned int result_type; ///< Result type
787 /// Constructor initializes object calling \p srand()
793 /// Returns next random number calling \p rand()
794 result_type operator()()
796 return (result_type) rand();
803 template <typename Accessor>
804 struct key_accessor {
805 template <typename Base> struct pack: public Base
807 typedef Accessor key_accessor;
811 template <typename Traits, typename ReplaceWith, typename WhatReplace = none >
812 struct replace_key_accessor {
813 typedef typename std::conditional<
814 std::is_same< typename Traits::key_accessor, WhatReplace >::value,
815 typename opt::key_accessor< ReplaceWith >::template pack< Traits >,
821 }} // namespace cds::opt
823 #include <cds/opt/make_options_var.h>
825 #endif // #ifndef __CDS_OPT_OPTIONS_H