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 <cds/details/void_selector.h>
18 #include <stdlib.h> // rand, srand
22 /// Framework to define template options
24 There are two kind of options:
25 - \p type-option - option that determines a data type. The template argument \p Type of the option is a type.
26 - \p value-option - option that determines a value. The template argument \p Value of the option is a value.
30 /// Predefined options value (generally, for the options that determine the data types)
33 /// Type indicates that an option is not specified and the default one should be used
37 template <class Base> struct pack: public Base
42 /// Metafunction for selecting default option value
45 - \p Option - option value
46 - \p Default - default option value
47 - \p Value - option value if \p Option is not opt::none
49 If \p Option is opt::none, the metafunction result is \p Default, otherwise
50 the result is \p Value.
54 // default_spin is cds::lock::Spin
55 typedef typename cds::opt::select_default< cds::opt::none, cds::lock::Spin >::type default_spin;
57 // spin_32bit is cds::lock::Spin32
58 typedef typename cds::opt::select_default< cds::lock::Spin32, cds::lock::Spin >::type spin_32bit;
61 template <typename Option, typename Default, typename Value = Option>
64 typedef Value type ; ///< metafunction result
67 template <typename Default>
68 struct select_default< none, Default >
74 /// Metafunction to select option value
76 This metafunction is intended for extracting the value of the \p Option option.
79 #include <cds/opt/options.h>
80 #include <type_traits> // only for testing purpose (static_assert)
85 typedef cds::opt::tag< tag_a > tag_option;
87 // What is the value of the tag_option?
88 // How we can extract tag_a from tag_option?
89 // Here is a solution:
90 typedef cds::opt::value< tag_option >::tag tag_option_value;
92 // tag_option_value is the same as tag_a
93 static_assert( std::is_same< tag_option_value, tag_a >::value, "Error: tag_option_value != tag_a" );
97 template <typename Option>
98 struct value: public Option::template pack<none>
102 /// [type-option] Option setter specifies a tag
104 Suppose, you have a struct
109 and you want that your class \p X would be derived from several \p Feature:
111 class X: public Feature, public Feature
115 How can you distinguish one \p Feature from another?
116 You may use a tag option:
118 template <typename Tag>
124 class X: public Feature< tag_a >, public Feature< tag_b >
127 Now you can distinguish one \p Feature from another:
130 Feature<tag_a>& fa = static_cast< Feature<tag_a> >( x );
131 Feature<tag_b>& fb = static_cast< Feature<tag_b> >( x );
134 \p tag option setter allows you to do things like this for an option-centric approach:
136 template <typename ...Options>
142 class X: public Feature< tag<tag_a> >, public Feature< tag<tag_b> >
146 This option setter is widely used in cds::intrusive containers to distinguish
147 between different intrusive part of container's node.
149 An incomplete type can serve as a \p Tag.
151 template <typename Tag>
154 template<class Base> struct pack: public Base
161 /// [type-option] Option setter specifies lock class
163 Specification of the \p Type class is:
171 template <typename Type>
174 template<class Base> struct pack: public Base
176 typedef Type lock_type;
181 /// [type-option] Back-off strategy option setter
183 Back-off strategy used in some algorithm.
184 See cds::backoff namespace for back-off explanation and supported interface.
186 template <typename Type>
189 template <class Base> struct pack: public Base
191 typedef Type back_off;
196 /// [type-option] Option setter for garbage collecting schema used
198 Possible values of \p GC template parameter are:
199 - cds::gc::HP - Hazard Pointer garbage collector
200 - cds::gc::HRC - Gidenstam's garbage collector
201 - cds::gc::PTB - Pass-the-Buck garbage collector
202 - cds::gc::none::GC - No garbage collector (not supported for some containers)
204 template <typename GC>
207 template <class Base> struct pack: public Base
214 /// [type-option] Option setter for an allocator
216 \p Type is allocator with \p std::allocator interface. Default is value of macro CDS_DEFAULT_ALLOCATOR
217 that, in turn, is \p std::allocator.
219 The \p libcds containers actively use rebinding to convert an allocator of one type to another. Thus,
220 you may specify any valid type as std::allocator's template parameter.
222 See also opt::node_allocator
224 template <typename Type>
227 template <typename Base> struct pack: public Base
229 typedef Type allocator;
234 /// [type-option] Option setter for node allocator
236 \p Type is allocator with \p std::allocator interface. Default is value of macro CDS_DEFAULT_ALLOCATOR
237 that, in turn, is \p std::allocator.
239 Many node-base containers require an allocator for maintaining data (container's node) and for internal use.
240 Sometimes, this types of allocator should be different for performance reason.
241 For example, we should like to allocate the node from a pool of preallocated nodes.
242 Such pool can be seen as the node allocator.
244 Usually, if a container supports \p opt::allocator and \p %opt::node_allocator options
245 and \p opt::node_allocator is not specified the \p %opt::allocator option is used for maintaining the nodes.
247 The \p libcds containers actively use rebinding to convert an allocator of one type to another. Thus,
248 you may specify any valid type as std::allocator's template parameter.
250 template <typename Type>
251 struct node_allocator {
253 template <typename Base> struct pack: public Base
255 typedef Type node_allocator;
260 /// [type-option] Option setter for item counting
262 Some data structure (for example, queues) has additional feature for item counting.
263 This option allows to set up appropriate item counting policy for that data structure.
265 Predefined option \p Type:
266 - atomicity::empty_item_counter - no item counting performed. It is default policy for many
268 - atomicity::item_counter - the class that provides atomically item counting
269 - opt::v::sequential_item_counter - simple non-atomic item counter. This item counter is not intended for
270 concurrent containers and may be used only if it is explicitly noted.
272 You may provide other implementation of atomicity::item_counter interface for your needs.
274 Note, the item counting in lock-free containers cannot be exact; for example, if
275 item counter for a container returns zero it is not mean that the container is empty.
276 Thus, item counter may be used for statistical purposes only.
278 template <typename Type>
279 struct item_counter {
281 template <typename Base> struct pack: public Base
283 typedef Type item_counter;
289 /// Sequential non-atomic item counter
291 This type of item counter is not intended for concurrent containers
292 and may be used only if it is explicitly noted.
294 class sequential_item_counter
297 typedef size_t counter_type ; ///< Counter type
299 counter_type m_nCounter ; ///< Counter
302 sequential_item_counter()
306 /// Returns current value of the counter
307 counter_type value() const
312 /// Same as \ref value() with relaxed memory ordering
313 operator counter_type() const
318 /// Increments the counter. Semantics: postincrement
324 /// Decrements the counter. Semantics: postdecrement
331 counter_type operator ++()
336 counter_type operator ++(int)
342 counter_type operator --()
347 counter_type operator --(int)
352 /// Resets count to 0
360 /// Special alignment constants for \ref cds::opt::alignment option
361 enum special_alignment {
362 no_special_alignment = 0, ///< no special alignment
363 cache_line_alignment = 1 ///< use cache line size defined in cds/user_setup/cache_line.h
366 /// [value-option] Alignment option setter
368 Alignment for some internal data of containers. May be useful to solve false sharing problem.
369 \p Value defines desired alignment and it may be power of two integer or predefined values from
370 \ref special_alignment enum.
372 template <unsigned int Value>
375 template <typename Base> struct pack: public Base
377 enum { alignment = Value };
384 template <typename Type, unsigned int Alignment>
385 struct alignment_setter {
386 typedef typename cds::details::aligned_type< Type, Alignment >::type type;
389 template <typename Type>
390 struct alignment_setter<Type, no_special_alignment> {
394 template <typename Type>
395 struct alignment_setter<Type, cache_line_alignment> {
396 typedef typename cds::details::aligned_type< Type, c_nCacheLineSize >::type type;
399 } // namespace details
402 /// [type-option] Generic option setter for statisitcs
404 This option sets a type to gather statistics.
405 The option is generic - no predefined type(s) is provided.
406 The particular \p Type of statistics depends on internal structure of the object.
408 template <typename Type>
411 template <typename Base> struct pack: public Base
418 /// [type-option] Option setter for C++ memory model
420 The <b>cds</b> library supports following memory ordering constraints for atomic operations in container implementation:
421 - v::relaxed_ordering - relaxed C++ memory model. This mode supports full set of memory ordering constraints:
422 \p memory_order_relaxed, \p memory_order_acquire, \p memory_order_release and so on.
423 - v::sequential_consistent - sequentially consistent C++ memory model (default memory ordering for C++). In
424 this mode any memory ordering constraint maps to \p memory_order_seq_cst.
426 The \p Type template parameter can be v::relaxed_ordering or v::sequential_consistent.
428 You may mix different memory ordering options for different containers: one declare as sequentially consistent,
429 another declare as relaxed.
430 Usually, v::relaxed_ordering is the default memory ordering for <b>cds</b> containers.
432 template <typename Type>
433 struct memory_model {
435 template <typename Base> struct pack: public Base
437 typedef Type memory_model;
443 /// Relaxed memory ordering model
445 In this memory model the memory constraints are defined according to C++ Memory Model specification.
447 See opt::memory_model for explanations
449 struct relaxed_ordering {
452 // For new C++11 (cds-1.1.0)
453 static const atomics::memory_order memory_order_relaxed = atomics::memory_order_relaxed;
454 static const atomics::memory_order memory_order_consume = atomics::memory_order_consume;
455 static const atomics::memory_order memory_order_acquire = atomics::memory_order_acquire;
456 static const atomics::memory_order memory_order_release = atomics::memory_order_release;
457 static const atomics::memory_order memory_order_acq_rel = atomics::memory_order_acq_rel;
458 static const atomics::memory_order memory_order_seq_cst = atomics::memory_order_seq_cst;
462 /// Sequential consistent memory ordering model
464 In this memory model any memory constraint is equivalent to \p memory_order_seq_cst.
466 See opt::memory_model for explanations
468 struct sequential_consistent {
471 // For new C++11 (cds-1.1.0)
472 static const atomics::memory_order memory_order_relaxed = atomics::memory_order_seq_cst;
473 static const atomics::memory_order memory_order_consume = atomics::memory_order_seq_cst;
474 static const atomics::memory_order memory_order_acquire = atomics::memory_order_seq_cst;
475 static const atomics::memory_order memory_order_release = atomics::memory_order_seq_cst;
476 static const atomics::memory_order memory_order_acq_rel = atomics::memory_order_seq_cst;
477 static const atomics::memory_order memory_order_seq_cst = atomics::memory_order_seq_cst;
482 /// [type-option] Base type traits option setter
484 This option setter is intended generally for internal use for type rebinding.
486 template <typename Type>
489 template <typename Base> struct pack: public Base
491 typedef Type type_traits;
496 /// Resizing policy option
498 This option specifies the resizing policy that decides when to resize a container.
499 Used in some containers, for example, in container::StripedHashSet, intrusive::StripedHashSet.
501 The real resizing policy specified by \p Type does strongly depend on a container
502 that supports this option, see container documentation about possibly \p Type values.
504 template <typename Type>
505 struct resizing_policy {
507 template <typename Base> struct pack: public Base
509 typedef Type resizing_policy;
514 /// Copy policy option
516 The copy policy defines an item copying algorithm which is used, for example, when a container is resized.
517 It is very specific algorithm depending on type of the container.
519 template <typename Type>
522 template <typename Base> struct pack: public Base
524 typedef Type copy_policy;
529 /// Swap policy option
531 The swap policy specifies an algorithm for swapping two objects.
532 Usually, the default policy is \p std::swap (see opt::v::default_swap_policy):
536 template <typename T>
537 void operator ()( T& v1, T& v2 )
544 template <typename Type>
547 template <typename Base> struct pack: public Base
549 typedef Type swap_policy;
556 /// Default swap policy (see opt::swap_policy option)
558 The default swap policy is wrappr around \p std::swap algorithm.
560 struct default_swap_policy {
561 /// Performs swapping of \p v1 and \p v2 using \p std::swap algo
562 template <typename T>
563 void operator()( T& v1, T& v2 ) const
570 /// Move policy option
572 The move policy specifies an algorithm for moving object content.
573 In trivial case, it can be simple assignment.
575 The move interface is:
577 template <typename T>
579 void operator()( T& dest, T& src );
583 Note that in move algorithm the \p src source argument can be changed too.
584 So you can use move semantics.
586 Usually, the default move policy is opt::v::assignment_move_policy
588 template <typename Type>
591 template <typename Base> struct pack: public Base
593 typedef Type move_policy;
599 /// \ref opt::move_policy "Move policy" based on assignment operator
600 struct assignment_move_policy
602 /// <tt> dest = src </tt>
603 template <typename T>
604 void operator()( T& dest, T const& src ) const
611 /// [value-option] Enable sorting
613 This option enables (<tt>Enable = true</tt>) or disables (<tt>Enable == false</tt>)
614 sorting of a container.
616 template <bool Enable>
619 template <typename Base> struct pack: public Base
621 static bool const sort = Enable;
626 /// [type-option] Concurrent access policy
628 This option specifies synchronization strategy for fine-grained lock-based containers.
629 The option has no predefined \p Policy type.
630 For each container that accepts this option the range of available \p Policy types
633 template <typename Policy>
634 struct mutex_policy {
636 template <typename Base> struct pack: public Base
638 typedef Policy mutex_policy;
644 /// [type-option] Random number generator
646 The option specifies a random number generator.
647 \p Random can be any STL random number generator producing
648 unsigned integer: \p std::linear_congruential_engine,
649 \p std::mersenne_twister_engine, \p std::subtract_with_carry_engine
650 and so on, or opt::v::c_rand.
653 template <typename Random>
654 struct random_engine {
656 template <typename Base> struct pack: public Base
658 typedef Random random_engine;
664 /// \p rand() -base random number generator
666 This generator returns a pseudorandom integer in the range 0 to \p RAND_MAX (32767).
669 typedef unsigned int result_type; ///< Result type
671 /// Constructor initializes object calling \p srand()
677 /// Returns next random number calling \p rand()
678 result_type operator()()
680 return (result_type) rand();
687 template <typename Accessor>
688 struct key_accessor {
689 template <typename Base> struct pack: public Base
691 typedef Accessor key_accessor;
695 template <typename Traits, typename ReplaceWith, typename WhatReplace = none >
696 struct replace_key_accessor {
697 typedef typename std::conditional<
698 std::is_same< typename Traits::key_accessor, WhatReplace >::value,
699 typename opt::key_accessor< ReplaceWith >::template pack< Traits >,
705 }} // namespace cds::opt
707 #include <cds/opt/make_options_var.h>
709 #endif // #ifndef __CDS_OPT_OPTIONS_H