From: khizmax Date: Tue, 11 Nov 2014 10:17:59 +0000 (+0300) Subject: improve docs and fix typo X-Git-Tag: v2.0.0~115 X-Git-Url: http://plrg.eecs.uci.edu/git/?p=libcds.git;a=commitdiff_plain;h=ab7af122c1440e755bcab9192ad3394332c8eec1 improve docs and fix typo --- diff --git a/cds/container/details/make_skip_list_map.h b/cds/container/details/make_skip_list_map.h index ae87e8a3..e0cb9757 100644 --- a/cds/container/details/make_skip_list_map.h +++ b/cds/container/details/make_skip_list_map.h @@ -16,7 +16,7 @@ namespace cds { namespace container { namespace details { typedef K key_type; typedef T mapped_type; typedef std::pair< key_type const, mapped_type> value_type; - typedef Traits type_traits; + typedef Traits traits; typedef cds::intrusive::skip_list::node< gc > intrusive_node_type; struct node_type: public intrusive_node_type @@ -61,9 +61,9 @@ namespace cds { namespace container { namespace details { } }; - class node_allocator: public skip_list::details::node_allocator< node_type, type_traits> + class node_allocator : public skip_list::details::node_allocator< node_type, traits> { - typedef skip_list::details::node_allocator< node_type, type_traits> base_class; + typedef skip_list::details::node_allocator< node_type, traits> base_class; public: template node_type * New( unsigned int nHeight, Q const& key ) @@ -108,10 +108,10 @@ namespace cds { namespace container { namespace details { return node.m_Value.first; } }; - typedef typename opt::details::make_comparator< key_type, type_traits >::type key_comparator; + typedef typename opt::details::make_comparator< key_type, traits >::type key_comparator; class intrusive_type_traits: public cds::intrusive::skip_list::make_traits< - cds::opt::type_traits< type_traits > + cds::opt::type_traits< traits > ,cds::intrusive::opt::hook< intrusive::skip_list::base_hook< cds::opt::gc< gc > > > ,cds::intrusive::opt::disposer< node_deallocator > ,cds::intrusive::skip_list::internal_node_builder< dummy_node_builder > diff --git a/cds/container/details/michael_list_base.h b/cds/container/details/michael_list_base.h index a88eb485..c38be462 100644 --- a/cds/container/details/michael_list_base.h +++ b/cds/container/details/michael_list_base.h @@ -86,7 +86,7 @@ namespace cds { namespace container { This struct is empty and it is used only as a tag for selecting MichaelList as ordered list implementation in declaration of some classes. - See split_list::type_traits::ordered_list as an example. + See split_list::traits::ordered_list as an example. */ struct michael_list_tag {}; diff --git a/cds/container/details/skip_list_base.h b/cds/container/details/skip_list_base.h index a5258968..5381b3b8 100644 --- a/cds/container/details/skip_list_base.h +++ b/cds/container/details/skip_list_base.h @@ -96,7 +96,7 @@ namespace cds { namespace container { - \p opt::compare - key comparison functor. No default functor is provided. If the option is not specified, the \p opt::less is used. - \p opt::less - specifies binary predicate used for key comparison. Default is \p std::less. - - \p opt::item_counter - the type of item counting feature. Default is \pf atomicity::empty_item_counter that is no item counting. + - \p opt::item_counter - the type of item counting feature. Default is \p atomicity::empty_item_counter that is no item counting. - \p opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default) or \p opt::v::sequential_consistent (sequentially consisnent memory model). - \p skip_list::random_level_generator - random level generator. Can be \p skip_list::xorshift, \p skip_list::turbo_pascal or diff --git a/cds/container/impl/lazy_list.h b/cds/container/impl/lazy_list.h index 6605dbfa..54ac49ce 100644 --- a/cds/container/impl/lazy_list.h +++ b/cds/container/impl/lazy_list.h @@ -42,7 +42,7 @@ namespace cds { namespace container { } }; - // Declare type_traits + // Declare traits struct my_traits: public cds::container::lazy_list::traits { typedef my_compare compare; diff --git a/cds/container/segmented_queue.h b/cds/container/segmented_queue.h index 59104fa9..ea4cd957 100644 --- a/cds/container/segmented_queue.h +++ b/cds/container/segmented_queue.h @@ -169,7 +169,7 @@ namespace cds { namespace container { Template parameters: - \p GC - a garbage collector, possible types are cds::gc::HP, cds::gc::PTB - \p T - the type of values stored in the queue - - \p Traits - queue type traits, default is \p segmented_queue::type_traits. + - \p Traits - queue type traits, default is \p segmented_queue::traits. \p segmented_queue::make_traits metafunction can be used to construct your type traits. */ diff --git a/cds/container/skip_list_set_nogc.h b/cds/container/skip_list_set_nogc.h index 9427f5b2..d930dbb5 100644 --- a/cds/container/skip_list_set_nogc.h +++ b/cds/container/skip_list_set_nogc.h @@ -28,7 +28,7 @@ namespace cds { namespace container { { typedef cds::gc::nogc gc; typedef T value_type; - typedef Traits type_traits; + typedef Traits traits; typedef cds::intrusive::skip_list::node< gc > intrusive_node_type; struct node_type: public intrusive_node_type @@ -64,7 +64,7 @@ namespace cds { namespace container { node_type() = delete; // no default ctor }; - typedef skip_list::details::node_allocator< node_type, type_traits> node_allocator; + typedef skip_list::details::node_allocator< node_type, traits> node_allocator; struct node_deallocator { void operator ()( node_type * pNode ) @@ -75,8 +75,8 @@ namespace cds { namespace container { typedef skip_list::details::dummy_node_builder dummy_node_builder; - typedef typename type_traits::key_accessor key_accessor; - typedef typename opt::details::make_comparator< value_type, type_traits >::type key_comparator; + typedef typename traits::key_accessor key_accessor; + typedef typename opt::details::make_comparator< value_type, traits >::type key_comparator; /* template @@ -86,7 +86,7 @@ namespace cds { namespace container { */ typedef typename cds::intrusive::skip_list::make_traits< - cds::opt::type_traits< type_traits > + cds::opt::type_traits< traits > ,cds::intrusive::opt::hook< intrusive::skip_list::base_hook< cds::opt::gc< gc > > > ,cds::intrusive::opt::disposer< node_deallocator > ,cds::intrusive::skip_list::internal_node_builder< dummy_node_builder > @@ -108,7 +108,7 @@ namespace cds { namespace container { Template arguments: - \p T - type to be stored in the list. - - \p Traits - type traits. See skip_list::type_traits for explanation. + - \p Traits - type traits. See skip_list::traits for explanation. It is possible to declare option-based list with cds::container::skip_list::make_traits metafunction istead of \p Traits template argument. \p Options template arguments of cds::container::skip_list::make_traits metafunction are: @@ -128,7 +128,7 @@ namespace cds { namespace container { template < typename T, #ifdef CDS_DOXYGEN_INVOKED - class Traits = skip_list::type_traits + class Traits = skip_list::traits #else class Traits #endif diff --git a/cds/container/skip_list_set_rcu.h b/cds/container/skip_list_set_rcu.h index b7cdfbc9..82b7b838 100644 --- a/cds/container/skip_list_set_rcu.h +++ b/cds/container/skip_list_set_rcu.h @@ -35,7 +35,7 @@ namespace cds { namespace container { Template arguments: - \p RCU - one of \ref cds_urcu_gc "RCU type". - \p T - type to be stored in the list. - - \p Traits - type traits. See skip_list::type_traits for explanation. + - \p Traits - set traits, default is skip_list::traits for explanation. It is possible to declare option-based list with cds::container::skip_list::make_traits metafunction istead of \p Traits template argument. @@ -85,7 +85,7 @@ namespace cds { namespace container { // Traits for your skip-list. // At least, you should define cds::opt::less or cds::opt::compare for Foo struct - struct my_traits: public cds::continer::skip_list::type_traits + struct my_traits: public cds::continer::skip_list::traits { // ... }; @@ -141,7 +141,7 @@ namespace cds { namespace container { typename RCU, typename T, #ifdef CDS_DOXYGEN_INVOKED - typename Traits = skip_list::type_traits + typename Traits = skip_list::traits #else typename Traits #endif @@ -160,16 +160,16 @@ namespace cds { namespace container { public: typedef typename base_class::gc gc ; ///< Garbage collector used typedef T value_type ; ///< Value type stored in the set - typedef Traits options ; ///< Options specified + typedef Traits traits ; ///< Options specified typedef typename base_class::back_off back_off ; ///< Back-off strategy used - typedef typename options::allocator allocator_type ; ///< Allocator type used for allocate/deallocate the skip-list nodes + typedef typename traits::allocator allocator_type ; ///< Allocator type used for allocate/deallocate the skip-list nodes typedef typename base_class::item_counter item_counter ; ///< Item counting policy used typedef typename maker::key_comparator key_comparator ; ///< key compare functor typedef typename base_class::memory_model memory_model ; ///< Memory ordering. See cds::opt::memory_model option - typedef typename options::random_level_generator random_level_generator ; ///< random level generator - typedef typename options::stat stat ; ///< internal statistics type - typedef typename options::rcu_check_deadlock rcu_check_deadlock ; ///< Deadlock checking policy + typedef typename traits::random_level_generator random_level_generator ; ///< random level generator + typedef typename traits::stat stat ; ///< internal statistics type + typedef typename traits::rcu_check_deadlock rcu_check_deadlock ; ///< Deadlock checking policy protected: //@cond diff --git a/cds/container/striped_map.h b/cds/container/striped_map.h index 3c23860e..cc05e3e0 100644 --- a/cds/container/striped_map.h +++ b/cds/container/striped_map.h @@ -68,33 +68,33 @@ namespace cds { namespace container { among \p Options template arguments. The \p Options are: - - opt::mutex_policy - concurrent access policy. - Available policies: intrusive::striped_set::striping, intrusive::striped_set::refinable. + - \p opt::mutex_policy - concurrent access policy. + Available policies: \p intrusive::striped_set::striping, \p intrusive::striped_set::refinable. Default is %striped_set::striping. - - opt::hash - hash functor. Default option value see opt::v::hash_selector which selects default hash functor for - your compiler. - - opt::compare - key comparison functor. No default functor is provided. - If the option is not specified, the opt::less is used. - - opt::less - specifies binary predicate used for key comparison. Default is \p std::less. - - opt::item_counter - item counter type. Default is \p atomicity::item_counter since some operation on the counter is performed - without locks. Note that item counting is an essential part of the map algorithm, so dummy type like atomicity::empty_item_counter - is not suitable. - - opt::allocator - the allocator type using for memory allocation of bucket table and lock array. Default is CDS_DEFAULT_ALLOCATOR. - - opt::resizing_policy - the resizing policy that is a functor that decides when to resize the hash map. + - \p opt::hash - hash functor. Default option value see opt::v::hash_selector + which selects default hash functor for your compiler. + - \p opt::compare - key comparison functor. No default functor is provided. + If the option is not specified, the \p %opt::less is used. + - \p opt::less - specifies binary predicate used for key comparison. Default is \p std::less. + - \p opt::item_counter - item counter type. Default is \p atomicity::item_counter since some operation on the counter is performed + without locks. Note that item counting is an essential part of the map algorithm, so dummy counter + like as \p atomicity::empty_item_counter is not suitable. + - \p opt::allocator - the allocator type using for memory allocation of bucket table and lock array. Default is \ref CDS_DEFAULT_ALLOCATOR. + - \p opt::resizing_policy - the resizing policy that is a functor that decides when to resize the hash map. Default option value depends on bucket container type: - for sequential containers like \p std::list, \p std::vector the resizing policy is hash_set::load_factor_resizing<4>; - for other type of containers like \p std::map, \p std::unordered_map the resizing policy is hash_set::no_resizing. - See \ref intrusive::striped_set namespace for list of all possible types of the option. + for sequential containers like \p std::list, \p std::vector the resizing policy is striped_set::load_factor_resizing<4> ; + for other type of containers like \p std::map, \p std::unordered_map the resizing policy is \p striped_set::no_resizing. + See \ref cds_striped_resizing_policy "available resizing policy". Note that the choose of resizing policy depends of \p Container type: for sequential containers like \p std::list, \p std::vector and so on, right choosing of the policy can significantly improve performance. For other, non-sequential types of \p Container (like a \p std::map) the resizing policy is not so important. - - opt::copy_policy - the copy policy which is used to copy items from the old map to the new one when resizing. + - \p opt::copy_policy - the copy policy which is used to copy items from the old map to the new one when resizing. The policy can be optionally used in adapted bucket container for performance reasons of resizing. The detail of copy algorithm depends on type of bucket container and explains below. - \p opt::compare or \p opt::less options are used only in some \p Container class for searching an item. + \p %opt::compare or \p %opt::less options are used only in some \p Container class for searching an item. \p %opt::compare option has the highest priority: if \p %opt::compare is specified, \p %opt::less is not used. You can pass other option that would be passed to adapt metafunction, see below. @@ -102,14 +102,14 @@ namespace cds { namespace container { Internal details The \p %StripedMap class cannot utilize the \p Container container specified directly, but only its adapted variant which - supports an unified interface. Internally, the adaptation is made via hash_set::adapt metafunction that wraps bucket container + supports an unified interface. Internally, the adaptation is made via \p striped_set::adapt metafunction that wraps bucket container and provides the unified bucket interface suitable for \p %StripedMap. Such adaptation is completely transparent for you - you don't need to call \p adapt metafunction directly, \p %StripedMap class's internal machinery itself invokes appropriate \p adapt metafunction to adjust your \p Container container class to \p %StripedMap bucket's internal interface. All you need is to include a right header before striped_hash_map.h. - By default, intrusive::striped_set::adapt metafunction does not make any wrapping to \p AnyContainer, - so, the result %intrusive::striped_set::adapt::type is the same as \p AnyContainer. + By default, striped_set::adapt metafunction does not make any wrapping to \p AnyContainer, + so, the result striped_set::adapt::type is the same as \p AnyContainer. However, there are a lot of specializations of \p adapt for well-known containers, see table below. Any of this specialization wraps corresponding container making it suitable for the map's bucket. Remember, you should include the proper header file for \p adapt before striped_map.h. @@ -135,7 +135,7 @@ namespace cds { namespace container { The type of values stored in the \p std::list must be std::pair< const Key, V > , where \p Key - key type, and \p V - value type The list is ordered by key \p Key. - Template argument pack \p Options must contain cds::opt::less or cds::opt::compare for type \p Key stored in the list. + Template argument pack \p Options must contain \p cds::opt::less or \p cds::opt::compare for type \p Key stored in the list. @@ -172,27 +172,6 @@ namespace cds { namespace container { For the best result, \p h1 and \p h2 must be orthogonal i.e. h1(X) != h2(X) for any value \p X of type \p Key. - - \p stdext::hash_map (only for MS VC++ 2008) - - \code - #include - #include - typedef cds::container::StripedMap< - stdext::hash_map< Key, T, - stdext::hash_compare< - Key, - std::less - > - > - > striped_map; - \endcode - - - You should provide two different hash function \p h1 and \p h2 - one for stdext::hash_map and other for \p %StripedMap. - For the best result, \p h1 and \p h2 must be orthogonal i.e. h1(X) != h2(X) for any value \p X of type \p Key. - - \p boost::container::slist @@ -207,7 +186,7 @@ namespace cds { namespace container { The type of values stored in the \p boost::container::slist must be std::pair< const Key, T > , where \p Key - key type, and \p T - value type. The list is ordered. - \p Options must contain cds::opt::less or cds::opt::compare. + \p Options must contain \p cds::opt::less or \p cds::opt::compare. @@ -224,7 +203,7 @@ namespace cds { namespace container { The type of values stored in the \p boost::container::list must be std::pair< const Key, T > , where \p Key - key type, and \p T - value type. The list is ordered. - \p Options must contain cds::opt::less or cds::opt::compare. + \p Options must contain \p cds::opt::less or \p cds::opt::compare. @@ -278,26 +257,26 @@ namespace cds { namespace container { Suppose, you have a container class \p MyBestContainer and you want to integrate it with \p %StripedMap as bucket type. There are two possibility: - either your \p MyBestContainer class has native support of bucket's interface; - in this case, you can use default hash_set::adapt metafunction; + in this case, you can use default striped_set::adapt metafunction; - or your \p MyBestContainer class does not support bucket's interface, which means, that you should develop a specialization - cds::container::hash_set::adapt metafunction providing necessary interface. + cds::container::striped_set::adapt metafunction providing necessary interface. - The hash_set::adapt< Container, Options... > metafunction has two template argument: + The striped_set::adapt< Container, Options... > metafunction has two template argument: - \p Container is the class that should be used as the bucket, for example, std::list< std::pair< Key, T > >. - \p Options pack is the options from \p %StripedMap declaration. The \p adapt metafunction can use any option from \p Options for its internal use. For example, a \p compare option can be passed to \p adapt metafunction via \p Options argument of \p %StripedMap declaration. - See hash_set::adapt metafunction for the description of interface that the bucket container must provide + See striped_set::adapt metafunction for the description of interface that the bucket container must provide to be \p %StripedMap compatible. Copy policy There are three predefined copy policy: - - \p cds::container::hash_set::copy_item - copy item from old bucket to new one when resizing using copy ctor. It is default policy for + - \p cds::container::striped_set::copy_item - copy item from old bucket to new one when resizing using copy ctor. It is default policy for any compiler that do not support move semantics - - \p cds::container::hash_set::move_item - move item from old bucket to new one when resizing using move semantics. It is default policy for + - \p cds::container::striped_set::move_item - move item from old bucket to new one when resizing using move semantics. It is default policy for any compiler that support move semantics. If compiler does not support move semantics, the move policy is the same as \p copy_item - - \p cds::container::hash_set::swap_item - copy item from old bucket to new one when resizing using \p std::swap. Not all containers support + - \p cds::container::striped_set::swap_item - copy item from old bucket to new one when resizing using \p std::swap. Not all containers support this copy policy, see details in table below. You can define your own copy policy specifically for your case. @@ -353,7 +332,6 @@ namespace cds { namespace container { - \p std::map - \p std::unordered_map - - \p stdext::hash_map (only for MS VC++ 2008) - \p boost::container::map - \p boost::container::flat_map - \p boost::unordered_map @@ -429,7 +407,7 @@ namespace cds { namespace container { Advanced functions - libcds provides some advanced functions like \p erase_with, \p find_with, + The library provides some advanced functions like \p erase_with(), \p find_with(), that cannot be supported by all underlying containers. The table below shows whether underlying container supports those functions (the sign "+" means "container supports the function"): @@ -455,11 +433,6 @@ namespace cds { namespace container { - - - - \p stdext::hash_map (only for MS VC++ 2008) - - - - - \p boost::container::slist + @@ -578,9 +551,9 @@ template The function creates a node with \p key and default value, and then inserts the node created into the map. Preconditions: - - The \ref key_type should be constructible from a value of type \p K. - In trivial case, \p K is equal to \ref key_type. - - The \ref mapped_type should be default-constructible. + - The \p key_type should be constructible from a value of type \p K. + In trivial case, \p K is equal to \p key_type. + - The \p mapped_type should be default-constructible. Returns \p true if inserting successful, \p false otherwise. */ @@ -596,8 +569,8 @@ template and then inserts the node created into the map. Preconditions: - - The \ref key_type should be constructible from \p key of type \p K. - - The \ref mapped_type should be constructible from \p val of type \p V. + - The \p key_type should be constructible from \p key of type \p K. + - The \p mapped_type should be constructible from \p val of type \p V. Returns \p true if \p val is inserted into the set, \p false otherwise. */ @@ -638,7 +611,7 @@ template return base_class::insert( key, func ); } - /// For key \p key inserts data of type \ref mapped_type constructed with std::forward(args)... + /// For key \p key inserts data of type \p mapped_type created in-place from \p args /** Returns \p true if inserting successful, \p false otherwise. */ @@ -668,7 +641,7 @@ template The operation performs inserting or changing data with lock-free manner. If the \p key not found in the map, then the new item created from \p key - is inserted into the map (note that in this case the \ref key_type should be + is inserted into the map (note that in this case the \p key_type should be constructible from type \p K). Otherwise, the functor \p func is called with item found. The functor \p Func may be a function with signature: @@ -686,7 +659,7 @@ template - \p bNew - \p true if the item has been inserted, \p false otherwise - \p item - item of the list - The functor may change any fields of the \p item.second that is \ref mapped_type. + The functor may change any fields of the \p item.second that is \p mapped_type. Returns std::pair where \p first is true if operation is successfull, \p second is true if new item has been added or \p false if the item with \p key @@ -755,8 +728,6 @@ template \endcode Return \p true if key is found and deleted, \p false otherwise - - See also: \ref erase */ template bool erase( K const& key, Func f ) diff --git a/cds/container/striped_set.h b/cds/container/striped_set.h index 720a1b5d..1eae6b91 100644 --- a/cds/container/striped_set.h +++ b/cds/container/striped_set.h @@ -33,34 +33,33 @@ namespace cds { namespace container { among \p Options template arguments. The \p Options are: - - opt::mutex_policy - concurrent access policy. - Available policies: intrusive::striped_set::striping, intrusive::striped_set::refinable. - Default is %striped_set::striping. - - opt::hash - hash functor. Default option value see opt::v::hash_selector which selects default hash functor for - your compiler. - - opt::compare - key comparison functor. No default functor is provided. - If the option is not specified, the opt::less is used. - - opt::less - specifies binary predicate used for key comparison. Default is \p std::less. - - opt::item_counter - item counter type. Default is \p atomicity::item_counter since some operation on the counter is performed - without locks. Note that item counting is an essential part of the set algorithm, so dummy type like atomicity::empty_item_counter - is not suitable. - - opt::allocator - the allocator type using for memory allocation of bucket table and lock array. Default is CDS_DEFAULT_ALLOCATOR. - - opt::resizing_policy - the resizing policy that is a functor that decides when to resize the hash set. + - \p opt::mutex_policy - concurrent access policy. + Available policies: \p intrusive::striped_set::striping, \p intrusive::striped_set::refinable. + Default is \p %striped_set::striping. + - \p opt::hash - hash functor. Default option value see opt::v::hash_selector + which selects default hash functor for your compiler. + - \p opt::compare - key comparison functor. No default functor is provided. + If the option is not specified, the \p %opt::less is used. + - \p opt::less - specifies binary predicate used for key comparison. Default is \p std::less. + - \p opt::item_counter - item counter type. Default is \p atomicity::item_counter since some operation on the counter is performed + without locks. Note that item counting is an essential part of the set algorithm, so dummy counter + like as \p atomicity::empty_item_counter is not suitable. + - \p opt::allocator - the allocator type using for memory allocation of bucket table and lock array. Default is \ref CDS_DEFAULT_ALLOCATOR. + - \p opt::resizing_policy - the resizing policy that is a functor that decides when to resize the hash set. Default option value depends on bucket container type: - for sequential containers like \p std::list, \p std::vector the resizing policy is striped_set::load_factor_resizing<4>; - for other type of containers like \p std::set, \p std::unordered_set the resizing policy is striped_set::no_resizing. - See \ref striped_set namespace for list of all possible types of the option. + for sequential containers like \p std::list, \p std::vector the resizing policy is striped_set::load_factor_resizing<4> ; + for other type of containers like \p std::set, \p std::unordered_set the resizing policy is \p striped_set::no_resizing. + See \ref cds_striped_resizing_policy "available resizing policy". Note that the choose of resizing policy depends of \p Container type: for sequential containers like \p std::list, \p std::vector and so on, right choosing of the policy can significantly improve performance. - For other, non-sequential types of \p Container (like a \p std::set) - the resizing policy is not so important. - - opt::copy_policy - the copy policy which is used to copy items from the old set to the new one when resizing. + For other, non-sequential types of \p Container (like a \p std::set) the resizing policy is not so important. + - \p opt::copy_policy - the copy policy which is used to copy items from the old set to the new one when resizing. The policy can be optionally used in adapted bucket container for performance reasons of resizing. The detail of copy algorithm depends on type of bucket container and explains below. - opt::compare or opt::less options are used in some \p Container class for searching an item. - opt::compare option has the highest priority: if opt::compare is specified, opt::less is not used. + \p %opt::compare or \p %opt::less options are used in some \p Container class for searching an item. + \p %opt::compare option has the highest priority: if \p %opt::compare is specified, \p %opt::less is not used. You can pass other option that would be passed to adapt metafunction, see below. @@ -74,7 +73,7 @@ namespace cds { namespace container { All you need is to include a right header before striped_hash_set.h. By default, striped_set::adapt metafunction does not make any wrapping to \p AnyContainer, - so, the result %striped_set::adapt::type is the same as \p AnyContainer. + so, the result striped_set::adapt::type is the same as \p AnyContainer. However, there are a lot of specializations of striped_set::adapt for well-known containers, see table below. Any of this specialization wraps corresponding container making it suitable for the set's bucket. Remember, you should include the proper header file for \p adapt before including striped_hash_set.h. @@ -116,7 +115,7 @@ namespace cds { namespace container { The vector is ordered. - Template argument pack \p Options must contain cds::opt::less or cds::opt::compare for type \p T stored in the list + Template argument pack \p Options must contain \p cds::opt::less or \p cds::opt::compare for type \p T stored in the list @@ -149,28 +148,7 @@ namespace cds { namespace container { \endcode - You should provide two different hash function \p h1 and \p h2 - one for std::unordered_set and other for \p %StripedSet. - For the best result, \p h1 and \p h2 must be orthogonal i.e. h1(X) != h2(X) for any value \p X. - - - - \p stdext::hash_set (only for MS VC++ 2008) - - \code - #include - #include - typedef cds::container::StripedSet< - stdext::hash_set< T, - stdext::hash_compare< - T, - std::less - > - > - > striped_set; - \endcode - - - You should provide two different hash function \p h1 and \p h2 - one for stdext::hash_set and other for \p %StripedSet. + You should provide two different hash function \p h1 and \p h2 - one for \p std::unordered_set and other for \p %StripedSet. For the best result, \p h1 and \p h2 must be orthogonal i.e. h1(X) != h2(X) for any value \p X. @@ -187,7 +165,7 @@ namespace cds { namespace container { The list is ordered. - \p Options must contain cds::opt::less or cds::opt::compare. + \p Options must contain \p cds::opt::less or \p cds::opt::compare. @@ -203,7 +181,7 @@ namespace cds { namespace container { The list is ordered. - \p Options must contain cds::opt::less or cds::opt::compare. + \p Options must contain \p cds::opt::less or \p cds::opt::compare. @@ -220,7 +198,7 @@ namespace cds { namespace container { The vector is ordered. - Template argument pack \p Options must contain cds::opt::less or cds::opt::compare for type \p T stored in the list + Template argument pack \p Options must contain \p cds::opt::less or \p cds::opt::compare for type \p T stored in the vector @@ -237,7 +215,7 @@ namespace cds { namespace container { The vector is ordered. - Template argument pack \p Options must contain cds::opt::less or cds::opt::compare for type \p T stored in the list + Template argument pack \p Options must contain \p cds::opt::less or \p cds::opt::compare for type \p T stored in the vector @@ -284,7 +262,7 @@ namespace cds { namespace container { \endcode - You should provide two different hash function \p h1 and \p h2 - one for boost::unordered_set and other for \p %StripedSet. + You should provide two different hash function \p h1 and \p h2 - one for \p boost::unordered_set and other for \p %StripedSet. For the best result, \p h1 and \p h2 must be orthogonal i.e. h1(X) != h2(X) for any value \p X. @@ -362,7 +340,6 @@ namespace cds { namespace container { - \p std::set - \p std::unordered_set - - \p stdext::hash_set (only for MS VC++ 2008) \code struct copy_item { @@ -415,7 +392,7 @@ namespace cds { namespace container { Advanced functions - libcds provides some advanced functions like \p erase_with, \p find_with, + libcds provides some advanced functions like \p erase_with(), \p find_with(), that cannot be supported by all underlying containers. The table below shows whether underlying container supports those functions (the sign "+" means "container supports the function"): @@ -446,11 +423,6 @@ namespace cds { namespace container { - - - - \p stdext::hash_set (only for MS VC++ 2008) - - - - - \p boost::container::slist + @@ -561,8 +533,8 @@ namespace cds { namespace container { and then inserts the node created into the set. The type \p Q should contain as minimum the complete key for the node. - The object of \ref value_type should be constructible from a value of type \p Q. - In trivial case, \p Q is equal to \ref value_type. + The object of \p value_type should be constructible from a value of type \p Q. + In trivial case, \p Q is equal to \p value_type. Returns \p true if \p val is inserted into the set, \p false otherwise. */ @@ -585,7 +557,7 @@ namespace cds { namespace container { \endcode where \p item is the item inserted. - The type \p Q can differ from \ref value_type of items storing in the set. + The type \p Q can differ from \p value_type of items storing in the set. Therefore, the \p value_type should be constructible from type \p Q. The user-defined functor is called only if the inserting is success. @@ -788,7 +760,7 @@ namespace cds { namespace container { The \p val argument is non-const since it can be used as \p f functor destination i.e., the functor can modify both arguments. - The type \p Q can differ from \ref value_type of items storing in the container. + The type \p Q can differ from \p value_type of items storing in the container. Therefore, the \p value_type should be comparable with type \p Q. The function returns \p true if \p val is found, \p false otherwise. @@ -831,7 +803,7 @@ namespace cds { namespace container { The functor can change non-key fields of \p item. - The type \p Q can differ from \ref value_type of items storing in the container. + The type \p Q can differ from \p value_type of items storing in the container. Therefore, the \p value_type should be comparable with type \p Q. The function returns \p true if \p val is found, \p false otherwise. @@ -867,7 +839,7 @@ namespace cds { namespace container { and returns \p true if it is found, and \p false otherwise. Note the hash functor specified for class \p Traits template parameter - should accept a parameter of type \p Q that can be not the same as \ref value_type. + should accept a parameter of type \p Q that can be not the same as \p value_type. */ template bool find( Q const& val ) diff --git a/cds/container/treiber_stack.h b/cds/container/treiber_stack.h index cb6777a8..d79e1f5b 100644 --- a/cds/container/treiber_stack.h +++ b/cds/container/treiber_stack.h @@ -77,7 +77,6 @@ namespace cds { namespace container { /// Metafunction converting option list to \p TreiberStack traits /** - This is a wrapper for cds::opt::make_options< type_traits, Options...> Supported \p Options are: - opt::allocator - allocator (like \p std::allocator) used for allocating stack nodes. Default is \ref CDS_DEFAULT_ALLOCATOR - opt::back_off - back-off strategy used. If the option is not specified, the \p cds::backoff::Default is used. diff --git a/cds/intrusive/skip_list_rcu.h b/cds/intrusive/skip_list_rcu.h index 5569052a..3b9bb82d 100644 --- a/cds/intrusive/skip_list_rcu.h +++ b/cds/intrusive/skip_list_rcu.h @@ -317,7 +317,7 @@ namespace cds { namespace intrusive { - \p RCU - one of \ref cds_urcu_gc "RCU type" - \p T - type to be stored in the list. The type must be based on \p skip_list::node (for \p skip_list::base_hook) or it must have a member of type \p skip_list::node (for \p skip_list::member_hook). - - \p Traits - set traits, default is \p skip_list::type_traits + - \p Traits - set traits, default is \p skip_list::traits It is possible to declare option-based list with \p cds::intrusive::skip_list::make_traits metafunction instead of \p Traits template argument. diff --git a/cds/intrusive/striped_set.h b/cds/intrusive/striped_set.h index f9990d1f..a5f7cd06 100644 --- a/cds/intrusive/striped_set.h +++ b/cds/intrusive/striped_set.h @@ -10,6 +10,12 @@ namespace cds { namespace intrusive { /// StripedSet related definitions namespace striped_set { + + /** @defgroup cds_striped_resizing_policy Resizing policy for striped/refinable set/map + + Resizing policy for \p intrusive::StripedSet, \p container::StripedSet and \p container::StripedMap. + */ + } // namespace striped_set /// Striped hash set @@ -28,47 +34,48 @@ namespace cds { namespace intrusive { Template arguments: - \p Container - the container class that is used as bucket table entry. The \p Container class should support an uniform interface described below. - - \p Options - options + - \p Options - options The \p %StripedSet class does not exactly dictate the type of container that should be used as a \p Container bucket. - Instead, the class supports different intrusive container type for the bucket, for exampe, \p boost::intrusive::list, \p boost::intrusive::set and others. + Instead, the class supports different intrusive container type for the bucket, for exampe, + \p boost::intrusive::list, \p boost::intrusive::set and others. Remember that \p %StripedSet class algorithm ensures sequential blocking access to its bucket through the mutex type you specify among \p Options template arguments. The \p Options are: - - opt::mutex_policy - concurrent access policy. - Available policies: striped_set::striping, striped_set::refinable. - Default is striped_set::striping. - - cds::opt::hash - hash functor. Default option value see opt::v::hash_selector which selects default hash functor for - your compiler. - - cds::opt::compare - key comparison functor. No default functor is provided. - If the option is not specified, the opt::less is used. - - cds::opt::less - specifies binary predicate used for key comparison. Default is \p std::less. - - cds::opt::item_counter - item counter type. Default is \p atomicity::item_counter since some operation on the counter is performed - without locks. Note that item counting is an essential part of the set algorithm, so dummy type like atomicity::empty_item_counter + - \p opt::mutex_policy - concurrent access policy. + Available policies: \p striped_set::striping, \p striped_set::refinable. + Default is \p %striped_set::striping. + - \p cds::opt::hash - hash functor. Default option value see opt::v::hash_selector + which selects default hash functor for your compiler. + - \p cds::opt::compare - key comparison functor. No default functor is provided. + If the option is not specified, the \p opt::less is used. + - \p cds::opt::less - specifies binary predicate used for key comparison. Default is \p std::less. + - \p cds::opt::item_counter - item counter type. Default is \p atomicity::item_counter since some operation on the counter is performed + without locks. Note that item counting is an essential part of the set algorithm, so dummy counter like \p atomicity::empty_item_counter is not suitable. - - cds::opt::allocator - the allocator type using for memory allocation of bucket table and lock array. Default is CDS_DEFAULT_ALLOCATOR. - - cds::opt::resizing_policy - the resizing policy that is a functor that decides when to resize the hash set. + - \p cds::opt::allocator - the allocator type using for memory allocation of bucket table and lock array. Default is \ref CDS_DEFAULT_ALLOCATOR. + - \p cds::opt::resizing_policy - the resizing policy - a functor that decides when to resize the hash set. Default option value depends on bucket container type: - for sequential containers like \p boost::intrusive::list the resizing policy is cds::container::striped_set::load_factor_resizing <4>; - for other type of containers like \p boost::intrusive::set the resizing policy is cds::container::striped_set::no_resizing. - See cds::container::striped_set namespace for list of all possible types of the option. + for sequential containers like \p boost::intrusive::list the resizing policy is cds::container::striped_set::load_factor_resizing<4> ; + for other type of containers like \p boost::intrusive::set the resizing policy is cds::container::striped_set::no_resizing. + See \ref cds_striped_resizing_policy "available resizing policy". Note that the choose of resizing policy depends of \p Container type: - for sequential containers like \p boost::intrusive::list right choosing of the policy can significantly improve performance. + for sequential containers like \p boost::intrusive::list the right policy can significantly improve performance. For other, non-sequential types of \p Container (like a \p boost::intrusive::set) the resizing policy is not so important. - - cds::opt::buffer - a buffer type used only for boost::intrusive::unordered_set. - Default is cds::opt::v::static_buffer< cds::any_type, 256 >. + - \p cds::opt::buffer - a buffer type used only for \p boost::intrusive::unordered_set. + Default is cds::opt::v::static_buffer< cds::any_type, 256 > . - opt::compare or opt::less options are used in some \p Container class for ordering. - opt::compare option has the highest priority: if opt::compare is specified, opt::less is not used. + \p opt::compare or \p opt::less options are used in some \p Container class for ordering. + \p %opt::compare option has the highest priority: if \p %opt::compare is specified, \p %opt::less is not used. - You can pass other option that would be passed to adapt metafunction, see below. + You can pass other option that would be passed to \p adapt metafunction, see below. Internal details - The \p %StripedSet class cannot utilize the \p Container container specified directly, but only its adapted variant which - supports an unified interface. Internally, the adaptation is made via intrusive::striped_set::adapt metafunction that wraps bucket container + The \p %StripedSet class cannot utilize the \p Container specified directly, but only its adapted variant which + supports an unified interface. Internally, the adaptation is made via \p intrusive::striped_set::adapt metafunction that wraps bucket container and provides the unified bucket interface suitable for \p %StripedSet. Such adaptation is completely transparent for you - you don't need to call \p adapt metafunction directly, \p %StripedSet class's internal machinery itself invokes appropriate \p adapt metafunction specialization to adjust your \p Container container class to \p %StripedSet bucket's internal interface. @@ -122,7 +129,7 @@ namespace cds { namespace intrusive { The list is ordered. - Template argument pack \p Options must contain cds::opt::less or cds::opt::compare for type \p T stored in the list + Template argument pack \p Options must contain \p cds::opt::less or \p cds::opt::compare for type \p T stored in the list @@ -139,7 +146,7 @@ namespace cds { namespace intrusive { Note that \p boost::intrusive::compare option using in \p boost::intrusive::set should support \p T type stored in the set and any type \p Q that you can use - in \p erase and \p find member functions. + in \p erase() and \p find() member functions. @@ -157,12 +164,12 @@ namespace cds { namespace intrusive { \endcode - You should provide two different hash function h1 and h2 - one for boost::intrusive::unordered_set - and other for %StripedSet. For the best result, h1 and h2 must be orthogonal i.e. h1(X) != h2(X) for any value X + You should provide two different hash function \p h1 and \p h2 - one for \p boost::intrusive::unordered_set + and other for \p %StripedSet. For the best result, \p h1 and \p h2 must be orthogonal i.e. h1(X) != h2(X) for any value \p X - The option opt::buffer is used for boost::intrusive::bucket_traits. Default is cds::opt::v::static_buffer< cds::any_type, 256 >. + The option \p opt::buffer is used for \p boost::intrusive::bucket_traits. Default is cds::opt::v::static_buffer< cds::any_type, 256 > . The resizing policy should correlate with the buffer capacity. - The default resizing policy is cds::container::striped_set::load_factor_resizing<256> what gives load factor 1 for + The default resizing policy is cds::container::striped_set::load_factor_resizing<256> what gives load factor 1 for default bucket buffer that is the best for \p boost::intrusive::unordered_set. @@ -180,7 +187,7 @@ namespace cds { namespace intrusive { Note that \p boost::intrusive::compare option using in \p boost::intrusive::avl_set should support \p T type stored in the set and any type \p Q that you can use - in \p erase and \p find member functions. + in \p erase() and \p find() member functions. @@ -197,7 +204,7 @@ namespace cds { namespace intrusive { Note that \p boost::intrusive::compare option using in \p boost::intrusive::sg_set should support \p T type stored in the set and any type \p Q that you can use - in \p erase and \p find member functions. + in \p erase() and \p find() member functions. @@ -214,7 +221,7 @@ namespace cds { namespace intrusive { Note that \p boost::intrusive::compare option using in \p boost::intrusive::splay_set should support \p T type stored in the set and any type \p Q that you can use - in \p erase and \p find member functions. + in \p erase() and \p find() member functions. @@ -231,7 +238,7 @@ namespace cds { namespace intrusive { Note that \p boost::intrusive::compare option using in \p boost::intrusive::treap_set should support \p T type stored in the set and any type \p Q that you can use - in \p erase and \p find member functions. + in \p erase() and \p find() member functions. @@ -241,7 +248,7 @@ namespace cds { namespace intrusive { There are two possibility: - either your \p MyBestContainer class has native support of bucket's interface; in this case, you can use default \p intrusive::striped_set::adapt metafunction; - - or your \p MyBestContainer class does not support bucket's interface, which means, that you should develop a specialization + - or your \p MyBestContainer class does not support bucket's interface, which means, that you should create a specialization of cds::intrusive::striped_set::adapt metafunction providing necessary interface. The intrusive::striped_set::adapt< Container, OptionPack > metafunction has two template argument: @@ -250,7 +257,7 @@ namespace cds { namespace intrusive { any option from \p OptionPack for its internal use. For example, a \p compare option can be passed to \p adapt metafunction via \p OptionPack argument of \p %StripedSet declaration. - See intrusive::striped_set::adapt metafunction for the description of interface that the bucket container must provide + See \p intrusive::striped_set::adapt metafunction for the description of interface that the bucket container must provide to be \p %StripedSet compatible. */ template diff --git a/cds/intrusive/striped_set/adapter.h b/cds/intrusive/striped_set/adapter.h index 7811ba88..99eaa64c 100644 --- a/cds/intrusive/striped_set/adapter.h +++ b/cds/intrusive/striped_set/adapter.h @@ -3,7 +3,6 @@ #ifndef __CDS_INTRUSIVE_STRIPED_SET_ADAPTER_H #define __CDS_INTRUSIVE_STRIPED_SET_ADAPTER_H -#include // ref #include #include #include @@ -19,8 +18,8 @@ namespace cds { namespace intrusive { By default, the metafunction does not make any transformation for container type \p Container. \p Container should provide interface suitable for the hash set. - The \p SetOptions template argument contains option pack - that has been passed to cds::intrusive::StripedSet. + The \p Options template argument contains option pack + that will be passed to \p cds::intrusive::StripedSet. Bucket interface diff --git a/cds/intrusive/striped_set/resizing_policy.h b/cds/intrusive/striped_set/resizing_policy.h index a82632e2..54513e2f 100644 --- a/cds/intrusive/striped_set/resizing_policy.h +++ b/cds/intrusive/striped_set/resizing_policy.h @@ -8,7 +8,7 @@ namespace cds { namespace intrusive { namespace striped_set { /// Load factor based resizing policy - /** + /** @ingroup cds_striped_resizing_policy When total item count in a container exceeds container.bucket_count() * LoadFactor then resizing is needed. @@ -38,7 +38,7 @@ namespace cds { namespace intrusive { namespace striped_set { }; /// Load factor based resizing policy, stateful specialization - /** + /** @ingroup cds_striped_resizing_policy This specialization allows to specify a load factor at runtime. */ template <> @@ -86,7 +86,7 @@ namespace cds { namespace intrusive { namespace striped_set { /// Single bucket threshold resizing policy - /** + /** @ingroup cds_striped_resizing_policy If any single bucket size exceeds the global \p Threshold then resizing is needed. This policy is stateless. @@ -112,7 +112,7 @@ namespace cds { namespace intrusive { namespace striped_set { /// Single bucket threshold resizing policy, stateful specialization - /** + /** @ingroup cds_striped_resizing_policy This specialization allows to specify and modify a threshold at runtime. */ template <> @@ -157,7 +157,7 @@ namespace cds { namespace intrusive { namespace striped_set { }; /// Dummy resizing policy - /** + /** @ingroup cds_striped_resizing_policy This policy is dummy and always returns \p false that means no resizing is needed. This policy is stateless. diff --git a/cds/intrusive/treiber_stack.h b/cds/intrusive/treiber_stack.h index 89bc36d0..99c22cb2 100644 --- a/cds/intrusive/treiber_stack.h +++ b/cds/intrusive/treiber_stack.h @@ -207,9 +207,7 @@ namespace cds { namespace intrusive { /// Metafunction converting option list to \p treiber_stack::traits /** - This is a wrapper for cds::opt::make_options< type_traits, Options...> Supported \p Options are: - - opt::hook - hook used. Possible hooks are: \p treiber_stack::base_hook, \p treiber_stack::member_hook, \p treiber_stack::traits_hook. If the option is not specified, \p %treiber_stack::base_hook<> is used. - opt::back_off - back-off strategy used. If the option is not specified, the \p cds::backoff::Default is used. diff --git a/change.log b/change.log index 0fda6337..8bf8422c 100644 --- a/change.log +++ b/change.log @@ -3,6 +3,11 @@ - switch to C++11 standard - Removed: MichaelDeque, reason: the implementation is heavy-weighted, inefficient, and, seems, unstable. + - Removed: cds::gc::HRC garbage collector, reason: the implementation is inefficient + and unstable. + - Changed: all container's declaration except StripedSet has been unified to the + following traits-based form: + class Container< GC, T, Traits > - Added: new member function pop_with(Func) to cds::container::TreiberStack - Added: new member functions enqueue_with(Func), dequeue_with(Func) to cds::container::MSQueue