X-Git-Url: http://plrg.eecs.uci.edu/git/?p=libcds.git;a=blobdiff_plain;f=cds%2Fopt%2Foptions.h;h=70faba7178a6c1a36a4630730072d2cc666aeb31;hp=a14c7054ccd562c4d48c0871465e591c4583c9e6;hb=HEAD;hpb=1390299659f1a21330ada4d3de9dbdc484300e98 diff --git a/cds/opt/options.h b/cds/opt/options.h index a14c7054..70faba71 100644 --- a/cds/opt/options.h +++ b/cds/opt/options.h @@ -1,4 +1,32 @@ -//$$CDS-header$$ +/* + This file is a part of libcds - Concurrent Data Structures library + + (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2017 + + Source code repo: http://github.com/khizmax/libcds/ + Download: http://sourceforge.net/projects/libcds/files/ + + Redistribution and use in source and binary forms, with or without + modification, are permitted provided that the following conditions are met: + + * Redistributions of source code must retain the above copyright notice, this + list of conditions and the following disclaimer. + + * Redistributions in binary form must reproduce the above copyright notice, + this list of conditions and the following disclaimer in the documentation + and/or other materials provided with the distribution. + + THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" + AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE + FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR + SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER + CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, + OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. +*/ #ifndef CDSLIB_OPT_OPTIONS_H #define CDSLIB_OPT_OPTIONS_H @@ -10,11 +38,12 @@ 2011.01.23 khizmax Created */ +#include // rand, srand + #include #include #include #include -#include // rand, srand namespace cds { @@ -26,9 +55,6 @@ namespace cds { */ namespace opt { - /// Predefined options value (generally, for the options that determine the data types) - namespace v {} - /// Type indicates that an option is not specified and the default one should be used struct none { @@ -276,17 +302,18 @@ namespace opt { This option allows to set up appropriate item counting policy for that data structure. Predefined option \p Type: - - atomicity::empty_item_counter - no item counting performed. It is default policy for many + - \p atomicity::empty_item_counter - no item counting performed. It is default policy for many containers - - atomicity::item_counter - the class that provides atomically item counting - - opt::v::sequential_item_counter - simple non-atomic item counter. This item counter is not intended for + - \p atomicity::item_counter - the class that provides atomic item counting + - \p atomicity::cache_friendly_item_counter - cache-friendly atomic item counter + - \p opt::v::sequential_item_counter - simple non-atomic item counter. This counter is not intended for concurrent containers and may be used only if it is explicitly noted. - You may provide other implementation of atomicity::item_counter interface for your needs. + You may provide other implementation of \p atomicity::item_counter interface for your needs. Note, the item counting in lock-free containers cannot be exact; for example, if item counter for a container returns zero it is not mean that the container is empty. - Thus, item counter may be used for statistical purposes only. + So, the item counter may be used for statistical purposes only. */ template struct item_counter { @@ -298,78 +325,6 @@ namespace opt { //@endcond }; - namespace v { - /// Sequential non-atomic item counter - /** - This type of item counter is not intended for concurrent containers - and may be used only if it is explicitly noted. - */ - class sequential_item_counter - { - public: - typedef size_t counter_type ; ///< Counter type - protected: - counter_type m_nCounter ; ///< Counter - - public: - sequential_item_counter() - : m_nCounter(0) - {} - - /// Returns current value of the counter - counter_type value() const - { - return m_nCounter; - } - - /// Same as \ref value() with relaxed memory ordering - operator counter_type() const - { - return value(); - } - - /// Increments the counter. Semantics: postincrement - counter_type inc() - { - return m_nCounter++; - } - - /// Decrements the counter. Semantics: postdecrement - counter_type dec() - { - return m_nCounter--; - } - - /// Preincrement - counter_type operator ++() - { - return inc() + 1; - } - /// Postincrement - counter_type operator ++(int) - { - return inc(); - } - - /// Predecrement - counter_type operator --() - { - return dec() - 1; - } - /// Postdecrement - counter_type operator --(int) - { - return dec(); - } - - /// Resets count to 0 - void reset() - { - m_nCounter = 0; - } - }; - } // namespace v - /// Special alignment constants for \ref cds::opt::alignment option enum special_alignment { no_special_alignment = 0, ///< no special alignment @@ -408,7 +363,6 @@ namespace opt { struct alignment_setter { typedef typename cds::details::aligned_type< Type, c_nCacheLineSize >::type type; }; - } // namespace details //@endcond @@ -417,9 +371,9 @@ namespace opt { no_special_padding = 0, ///< no special padding cache_line_padding = 1, ///< use cache line size defined in cds/user_setup/cache_line.h - /// Apply padding only for tiny data of size less than required padding + /// Apply padding only for tiny data when data size is less than required padding /** - The flag means that if your data size is less than the casheline size, the padding is applyed. + The flag means that if your data size is less than the cacheline size, the padding is applyed. Otherwise no padding will be applyed. This flag is applyed for padding value: @@ -451,6 +405,26 @@ namespace opt { //@endcond }; + //@cond + template + struct actual_padding + { + enum { value = Padding & ~padding_flags }; + }; + + template <> + struct actual_padding + { + enum { value = cds::c_nCacheLineSize }; + }; + + template <> + struct actual_padding + { + enum { value = cds::c_nCacheLineSize }; + }; + //@endcond + //@cond namespace details { enum padding_vs_datasize { @@ -468,6 +442,7 @@ namespace opt { struct type { T data; }; + typedef void padding_type; }; template @@ -476,23 +451,27 @@ namespace opt { struct type { T data; }; + typedef void padding_type; }; template struct apply_padding_helper < T, Padding, false, padding_datasize_less, TinyOnly > { + typedef uint8_t padding_type[Padding - sizeof( T )]; struct type { T data; - uint8_t pad_[Padding - sizeof( T )]; + padding_type pad_; }; + }; template struct apply_padding_helper < T, Padding, false, padding_datasize_greater, false > { + typedef uint8_t padding_type[Padding - sizeof( T ) % Padding]; struct type { T data; - uint8_t pad_[Padding - sizeof( T ) % Padding]; + padding_type pad_; }; }; @@ -502,6 +481,7 @@ namespace opt { struct type { T data; }; + typedef void padding_type; }; template @@ -517,12 +497,20 @@ namespace opt { static_assert( (c_nPadding & (c_nPadding - 1)) == 0, "Padding must be a power-of-two number" ); - typedef typename apply_padding_helper< T, + typedef apply_padding_helper< T, c_nPadding, c_nPadding == 0, sizeof( T ) < c_nPadding ? padding_datasize_less : sizeof( T ) == c_nPadding ? padding_datasize_equal : padding_datasize_greater, (Padding & padding_tiny_data_only) != 0 - >::type type; + > result; + + typedef typename result::type type; + + typedef typename std::conditional< + std::is_same< typename result::padding_type, void >::value, + unsigned int, + typename result::padding_type + >::type padding_type; }; } // namespace details @@ -569,62 +557,6 @@ namespace opt { //@endcond }; - namespace v { - /// Relaxed memory ordering model - /** - In this memory model the memory constraints are defined according to C++ Memory Model specification: - each constraint is mapped to \p std::memory_order constraints one-to-one - - See \p opt::memory_model for explanations - */ - struct relaxed_ordering { - //@cond - static const atomics::memory_order memory_order_relaxed = atomics::memory_order_relaxed; - static const atomics::memory_order memory_order_consume = atomics::memory_order_consume; - static const atomics::memory_order memory_order_acquire = atomics::memory_order_acquire; - static const atomics::memory_order memory_order_release = atomics::memory_order_release; - static const atomics::memory_order memory_order_acq_rel = atomics::memory_order_acq_rel; - static const atomics::memory_order memory_order_seq_cst = atomics::memory_order_seq_cst; - //@endcond - }; - - /// Sequential consistent memory ordering model - /** - In this memory model any memory constraint is equivalent to \p memory_order_seq_cst. - - See \p opt::memory_model for explanations - */ - struct sequential_consistent { - //@cond - static const atomics::memory_order memory_order_relaxed = atomics::memory_order_seq_cst; - static const atomics::memory_order memory_order_consume = atomics::memory_order_seq_cst; - static const atomics::memory_order memory_order_acquire = atomics::memory_order_seq_cst; - static const atomics::memory_order memory_order_release = atomics::memory_order_seq_cst; - static const atomics::memory_order memory_order_acq_rel = atomics::memory_order_seq_cst; - static const atomics::memory_order memory_order_seq_cst = atomics::memory_order_seq_cst; - //@endcond - }; - - //@cond - /// Totally relaxed memory ordering model (do not use!) - /** - In this memory model any memory constraint is equivalent to \p memory_order_relaxed. - @warning Do not use this model! It intended for testing purposes only - to verify debugging instruments like Thread Sanitizer. - - See \p opt::memory_model for explanations - */ - struct total_relaxed_ordering { - static const atomics::memory_order memory_order_relaxed = atomics::memory_order_relaxed; - static const atomics::memory_order memory_order_consume = atomics::memory_order_relaxed; - static const atomics::memory_order memory_order_acquire = atomics::memory_order_relaxed; - static const atomics::memory_order memory_order_release = atomics::memory_order_relaxed; - static const atomics::memory_order memory_order_acq_rel = atomics::memory_order_relaxed; - static const atomics::memory_order memory_order_seq_cst = atomics::memory_order_relaxed; - }; - //@endcond - } // namespace v - /// [type-option] Base type traits option setter /** This option setter is intended generally for internal use for type rebinding. @@ -697,22 +629,6 @@ namespace opt { //@endcond }; - namespace v { - - /// Default swap policy (see opt::swap_policy option) - /** - The default swap policy is wrappr around \p std::swap algorithm. - */ - struct default_swap_policy { - /// Performs swapping of \p v1 and \p v2 using \p std::swap algo - template - void operator()( T& v1, T& v2 ) const - { - std::swap( v1, v2 ); - } - }; - } // namespace v - /// Move policy option /** The move policy specifies an algorithm for moving object content. @@ -741,19 +657,6 @@ namespace opt { //@endcond }; - namespace v { - /// \ref opt::move_policy "Move policy" based on assignment operator - struct assignment_move_policy - { - /// dest = src - template - void operator()( T& dest, T const& src ) const - { - dest = src; - } - }; - } // namespace v - /// [value-option] Enable sorting /** This option enables (Enable = true) or disables (Enable == false) @@ -793,7 +696,7 @@ namespace opt { \p Random can be any STL random number generator producing unsigned integer: \p std::linear_congruential_engine, \p std::mersenne_twister_engine, \p std::subtract_with_carry_engine - and so on, or opt::v::c_rand. + and so on, or \p opt::v::c_rand. */ template @@ -806,50 +709,511 @@ namespace opt { //@endcond }; + /// [type-option] Free-list implementation + /** + See \p cds::intrusive::FreeList for free-list interface + */ + template + struct free_list { + //@cond + template struct pack: public Base + { + typedef FreeList free_list; + }; + //@endcond + }; + + //@cond + // For internal use + template + struct key_accessor { + template struct pack: public Base + { + typedef Accessor key_accessor; + }; + }; + + template + struct replace_key_accessor { + typedef typename std::conditional< + std::is_same< typename Traits::key_accessor, WhatReplace >::value, + typename opt::key_accessor< ReplaceWith >::template pack< Traits >, + Traits + >::type type; + }; + //@endcond + +}} // namespace cds::opt + + +// **************************************************** +// Options predefined types and values + +namespace cds { namespace opt { + + /// Predefined options value namespace v { - /// \p rand() -base random number generator + + /// Sequential non-atomic item counter + /** + This type of \p opt::item_counter option is not intended for concurrent containers + and may be used only if it is explicitly noted. + */ + class sequential_item_counter + { + public: + typedef size_t counter_type ; ///< Counter type + protected: + counter_type m_nCounter ; ///< Counter + + public: + sequential_item_counter() + : m_nCounter(0) + {} + + /// Returns current value of the counter + counter_type value() const + { + return m_nCounter; + } + + /// Same as \ref value() with relaxed memory ordering + operator counter_type() const + { + return value(); + } + + /// Increments the counter. Semantics: postincrement + counter_type inc() + { + return m_nCounter++; + } + + /// Decrements the counter. Semantics: postdecrement + counter_type dec() + { + return m_nCounter--; + } + + /// Preincrement + counter_type operator ++() + { + return inc() + 1; + } + /// Postincrement + counter_type operator ++(int) + { + return inc(); + } + + /// Predecrement + counter_type operator --() + { + return dec() - 1; + } + /// Postdecrement + counter_type operator --(int) + { + return dec(); + } + + /// Resets count to 0 + void reset() + { + m_nCounter = 0; + } + }; + + /// Relaxed memory ordering \p opt::memory_model + /** + In this ordering the memory constraints are defined according to C++ Memory Model specification: + each constraint is mapped to \p std::memory_order constraints one-to-one + */ + struct relaxed_ordering { + //@cond + static const atomics::memory_order memory_order_relaxed = atomics::memory_order_relaxed; + static const atomics::memory_order memory_order_consume = atomics::memory_order_consume; + static const atomics::memory_order memory_order_acquire = atomics::memory_order_acquire; + static const atomics::memory_order memory_order_release = atomics::memory_order_release; + static const atomics::memory_order memory_order_acq_rel = atomics::memory_order_acq_rel; + static const atomics::memory_order memory_order_seq_cst = atomics::memory_order_seq_cst; + //@endcond + }; + + /// Sequential consistent \p opt::memory_memory ordering + /** + In this memory model any memory constraint is equivalent to \p std::memory_order_seq_cst. + */ + struct sequential_consistent { + //@cond + static const atomics::memory_order memory_order_relaxed = atomics::memory_order_seq_cst; + static const atomics::memory_order memory_order_consume = atomics::memory_order_seq_cst; + static const atomics::memory_order memory_order_acquire = atomics::memory_order_seq_cst; + static const atomics::memory_order memory_order_release = atomics::memory_order_seq_cst; + static const atomics::memory_order memory_order_acq_rel = atomics::memory_order_seq_cst; + static const atomics::memory_order memory_order_seq_cst = atomics::memory_order_seq_cst; + //@endcond + }; + + //@cond + /// Totally relaxed \p opt::memory_model ordering (do not use!) + /** + In this memory model any memory constraint is equivalent to \p std::memory_order_relaxed. + @warning Do not use this model! It intended for testing purposes only + to verify debugging instruments like Thread Sanitizer. + */ + struct total_relaxed_ordering { + static const atomics::memory_order memory_order_relaxed = atomics::memory_order_relaxed; + static const atomics::memory_order memory_order_consume = atomics::memory_order_relaxed; + static const atomics::memory_order memory_order_acquire = atomics::memory_order_relaxed; + static const atomics::memory_order memory_order_release = atomics::memory_order_relaxed; + static const atomics::memory_order memory_order_acq_rel = atomics::memory_order_relaxed; + static const atomics::memory_order memory_order_seq_cst = atomics::memory_order_relaxed; + }; + //@endcond + + + /// Default swap policy for \p opt::swap_policy option + /** + The default swap policy is wrappr around \p std::swap algorithm. + */ + struct default_swap_policy { + /// Performs swapping of \p v1 and \p v2 using \p std::swap algo + template + void operator()( T& v1, T& v2 ) const + { + std::swap( v1, v2 ); + } + }; + + /// \p opt::move_policy based on move-assignment operator + struct assignment_move_policy + { + /// dest = std::move( src ) + template + void operator()( T& dest, T&& src ) const + { + dest = std::move( src ); + } + }; + + /// \p rand() -base random number generator for \p opt::random_engine /** This generator returns a pseudorandom integer in the range 0 to \p RAND_MAX (32767). */ struct c_rand { typedef unsigned int result_type; ///< Result type - /// Constructor initializes object calling \p srand() + /// Constructor initializes object calling \p std::srand() c_rand() { - srand(1); + std::srand(1); } - /// Returns next random number calling \p rand() + /// Returns next random number calling \p std::rand() result_type operator()() { - return (result_type) rand(); + return (result_type) std::rand(); } }; } // namespace v +}} // namespace cds::opt + + +// **************************************************** +// Options metafunctions + +namespace cds { namespace opt { + //@cond - // For internal use - template - struct key_accessor { - template struct pack: public Base + namespace details { + template + struct do_pack { - typedef Accessor key_accessor; + // Use "pack" member template to pack options + typedef typename Option::template pack type; + }; + + template class typelist; + + template struct typelist_head; + template + struct typelist_head< typelist > { + typedef Head type; + }; + template + struct typelist_head< typelist > { + typedef Head type; + }; + + template struct typelist_tail; + template + struct typelist_tail< typelist > { + typedef typelist type; + }; + template + struct typelist_tail< typelist > { + typedef typelist<> type; + }; + + template + struct make_options_impl { + typedef typename make_options_impl< + typename do_pack< + OptionList, + typename typelist_head< Typelist >::type + >::type, + typename typelist_tail::type + >::type type; + }; + + template + struct make_options_impl > { + typedef OptionList type; }; + } // namespace details + //@endcond + + /// make_options metafunction + /** @headerfile cds/opt/options.h + + The metafunction converts option list \p Options to traits structure. + The result of metafunction is \p type. + + Template parameter \p OptionList is default option set (default traits). + \p Options is option list. + */ + template + struct make_options { +#ifdef CDS_DOXYGEN_INVOKED + typedef implementation_defined type ; ///< Result of the metafunction +#else + typedef typename details::make_options_impl< OptionList, details::typelist >::type type; +#endif }; - template - struct replace_key_accessor { - typedef typename std::conditional< - std::is_same< typename Traits::key_accessor, WhatReplace >::value, - typename opt::key_accessor< ReplaceWith >::template pack< Traits >, - Traits - >::type type; + + // ***************************************************************** + // find_type_traits metafunction + // ***************************************************************** + + //@cond + namespace details { + template + struct find_type_traits_option; + + template <> + struct find_type_traits_option<> { + typedef cds::opt::none type; + }; + + template + struct find_type_traits_option< Any > { + typedef cds::opt::none type; + }; + + template + struct find_type_traits_option< cds::opt::type_traits< Any > > { + typedef Any type; + }; + + template + struct find_type_traits_option< cds::opt::type_traits< Any >, Options... > { + typedef Any type; + }; + + template + struct find_type_traits_option< Any, Options... > { + typedef typename find_type_traits_option< Options... >::type type; + }; + } // namespace details + //@endcond + + /// Metafunction to find opt::type_traits option in \p Options list + /** @headerfile cds/opt/options.h + + If \p Options contains \p opt::type_traits option then it is the metafunction result. + Otherwise the result is \p DefaultOptons. + */ + template + struct find_type_traits { + typedef typename select_default< typename details::find_type_traits_option::type, DefaultOptions>::type type ; ///< Metafunction result }; + + + // ***************************************************************** + // find_option metafunction + // ***************************************************************** + + //@cond + namespace details { + template + struct find_option; + + struct compare_ok; + struct compare_fail; + + template + struct compare_option + { + typedef compare_fail type; + }; + + template