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
}
};
- 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 <typename Q>
node_type * New( unsigned int nHeight, Q const& key )
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 >
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
{};
- \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<T>.
- - \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
}
};
- // Declare type_traits
+ // Declare traits
struct my_traits: public cds::container::lazy_list::traits
{
typedef my_compare compare;
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.
*/
{
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
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 )
typedef skip_list::details::dummy_node_builder<intrusive_node_type> 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 <typename Less>
*/
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 >
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:
template <
typename T,
#ifdef CDS_DOXYGEN_INVOKED
- class Traits = skip_list::type_traits
+ class Traits = skip_list::traits
#else
class Traits
#endif
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.
// 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
{
// ...
};
typename RCU,
typename T,
#ifdef CDS_DOXYGEN_INVOKED
- typename Traits = skip_list::type_traits
+ typename Traits = skip_list::traits
#else
typename Traits
#endif
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
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<opt::none> 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<T>.
- - 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 <tt>opt::v::hash_selector<opt::none> </tt>
+ 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<T>.
+ - \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 <tt>striped_set::load_factor_resizing<4> </tt>;
+ 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 <tt>adapt</tt> metafunction, see below.
<b>Internal details</b>
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 <tt>striped_hash_map.h</tt>.
- By default, <tt>
intrusive::striped_set::adapt<AnyContainer, Options...> </tt> metafunction does not make any wrapping to \p AnyContainer,
- so, the result <tt>
%intrusive::striped_set::adapt<AnyContainer, Options...>::type </tt> is the same as \p AnyContainer.
+ By default, <tt>striped_set::adapt<AnyContainer, Options...> </tt> metafunction does not make any wrapping to \p AnyContainer,
+ so, the result <tt>striped_set::adapt<AnyContainer, Options...>::type </tt> 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 <b>before</b> <tt>striped_map.h</tt>.
<td>
The type of values stored in the \p std::list must be <tt> std::pair< const Key, V > </tt>, where \p Key - key type, and \p V - value type
The list is ordered by key \p Key.
- Template argument pack \p Options <b>must</b> contain cds::opt::less or cds::opt::compare for type \p Key stored in the list.
+ Template argument pack \p Options <b>must</b> contain \p cds::opt::less or \p cds::opt::compare for type \p Key stored in the list.
</td>
</tr>
<tr>
For the best result, \p h1 and \p h2 must be orthogonal i.e. <tt> h1(X) != h2(X) </tt> for any value \p X of type \p Key.
</td>
</tr>
- <tr>
- <td>\p stdext::hash_map (only for MS VC++ 2008)</td>
- <td><tt><cds/container/striped_map/std_hash_map.h></tt></td>
- <td>\code
- #include <cds/container/striped_map/std_hash_map.h>
- #include <cds/container/striped_hash_map.h>
- typedef cds::container::StripedMap<
- stdext::hash_map< Key, T,
- stdext::hash_compare<
- Key,
- std::less<Key>
- >
- >
- > striped_map;
- \endcode
- </td>
- <td>
- 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. <tt> h1(X) != h2(X) </tt> for any value \p X of type \p Key.
- </td>
- </tr>
<tr>
<td> \p boost::container::slist</td>
<td><tt><cds/container/striped_map/boost_slist.h></tt></td>
<td>
The type of values stored in the \p boost::container::slist must be <tt> std::pair< const Key, T > </tt>,
where \p Key - key type, and \p T - value type. The list is ordered.
- \p Options <b>must</b> contain cds::opt::less or cds::opt::compare.
+ \p Options <b>must</b> contain \p cds::opt::less or \p cds::opt::compare.
</td>
</tr>
<tr>
<td>
The type of values stored in the \p boost::container::list must be <tt> std::pair< const Key, T > </tt>,
where \p Key - key type, and \p T - value type. The list is ordered.
- \p Options <b>must</b> contain cds::opt::less or cds::opt::compare.
+ \p Options <b>must</b> contain \p cds::opt::less or \p cds::opt::compare.
</td>
</tr>
<tr>
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 <tt>hash_set::adapt</tt> metafunction;
+ in this case, you can use default <tt>striped_set::adapt</tt> metafunction;
- or your \p MyBestContainer class does not support bucket's interface, which means, that you should develop a specialization
- <tt>cds::container::hash_set::adapt<MyBestContainer> </tt> metafunction providing necessary interface.
+ <tt>cds::container::striped_set::adapt<MyBestContainer> </tt> metafunction providing necessary interface.
- The <tt>hash_set::adapt< Container, Options... ></tt> metafunction has two template argument:
+ The <tt>striped_set::adapt< Container, Options... ></tt> metafunction has two template argument:
- \p Container is the class that should be used as the bucket, for example, <tt>std::list< std::pair< Key, T > ></tt>.
- \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.
<b>Copy policy</b>
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.
<td>
- \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
<b>Advanced functions</b>
- <b>libcds</b> 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"):
<td>-</td>
<td>-</td>
</tr>
- <tr>
- <td>\p stdext::hash_map (only for MS VC++ 2008)</td>
- <td>-</td>
- <td>-</td>
- </tr>
<tr>
<td> \p boost::container::slist</td>
<td>+</td>
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.
*/
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.
*/
return base_class::insert( key, func );
}
- /// For key \p key inserts data of type \ref mapped_type constructed with <tt>std::forward<Args>(args)...</tt>
+ /// 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.
*/
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:
- \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 <tt> std::pair<bool, bool> </tt> 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
\endcode
Return \p true if key is found and deleted, \p false otherwise
-
- See also: \ref erase
*/
template <typename K, typename Func>
bool erase( K const& key, Func f )
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<opt::none> 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<T>.
- - 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 <tt>opt::v::hash_selector<opt::none> </tt>
+ 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<T>.
+ - \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 <tt>striped_set::load_factor_resizing<4> </tt>;
+ 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 <tt>adapt</tt> metafunction, see below.
All you need is to include a right header before <tt>striped_hash_set.h</tt>.
By default, <tt>striped_set::adapt<AnyContainer, Options...> </tt> metafunction does not make any wrapping to \p AnyContainer,
- so, the result <tt>
%striped_set::adapt<AnyContainer, Options...>::type </tt> is the same as \p AnyContainer.
+ so, the result <tt>striped_set::adapt<AnyContainer, Options...>::type </tt> is the same as \p AnyContainer.
However, there are a lot of specializations of <tt>striped_set::adapt</tt> 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 <b>before</b> including <tt>striped_hash_set.h</tt>.
</td>
<td>
The vector is ordered.
- Template argument pack \p Options <b>must</b> contain cds::opt::less or cds::opt::compare for type \p T stored in the list
+ Template argument pack \p Options <b>must</b> contain \p cds::opt::less or \p cds::opt::compare for type \p T stored in the list
</td>
</tr>
<tr>
\endcode
</td>
<td>
- 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. <tt> h1(X) != h2(X) </tt> for any value \p X.
- </td>
- </tr>
- <tr>
- <td>\p stdext::hash_set (only for MS VC++ 2008)</td>
- <td><tt><cds/container/striped_set/std_hash_set.h></tt></td>
- <td>\code
- #include <cds/container/striped_set/std_hash_set.h>
- #include <cds/container/striped_hash_set.h>
- typedef cds::container::StripedSet<
- stdext::hash_set< T,
- stdext::hash_compare<
- T,
- std::less<T>
- >
- >
- > striped_set;
- \endcode
- </td>
- <td>
- 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. <tt> h1(X) != h2(X) </tt> for any value \p X.
</td>
</tr>
</td>
<td>
The list is ordered.
- \p Options <b>must</b> contain cds::opt::less or cds::opt::compare.
+ \p Options <b>must</b> contain \p cds::opt::less or \p cds::opt::compare.
</td>
</tr>
<tr>
</td>
<td>
The list is ordered.
- \p Options <b>must</b> contain cds::opt::less or cds::opt::compare.
+ \p Options <b>must</b> contain \p cds::opt::less or \p cds::opt::compare.
</td>
</tr>
<tr>
</td>
<td>
The vector is ordered.
- Template argument pack \p Options <b>must</b> contain cds::opt::less or cds::opt::compare for type \p T stored in the list
+ Template argument pack \p Options <b>must</b> contain \p cds::opt::less or \p cds::opt::compare for type \p T stored in the vector
</td>
</tr>
<tr>
</td>
<td>
The vector is ordered.
- Template argument pack \p Options <b>must</b> contain cds::opt::less or cds::opt::compare for type \p T stored in the list
+ Template argument pack \p Options <b>must</b> contain \p cds::opt::less or \p cds::opt::compare for type \p T stored in the vector
</td>
</tr>
<tr>
\endcode
</td>
<td>
- 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. <tt> h1(X) != h2(X) </tt> for any value \p X.
</td>
</tr>
<td>
- \p std::set
- \p std::unordered_set
- - \p stdext::hash_set (only for MS VC++ 2008)
</td>
<td>\code
struct copy_item {
<b>Advanced functions</b>
- <b>libcds</b> provides some advanced functions like \p erase_with, \p find_with,
+ <b>libcds</b> 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"):
<td>-</td>
<td>-</td>
</tr>
- <tr>
- <td>\p stdext::hash_set (only for MS VC++ 2008)</td>
- <td>-</td>
- <td>-</td>
- </tr>
<tr>
<td> \p boost::container::slist</td>
<td>+</td>
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.
*/
\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.
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.
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.
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 <typename Q>
bool find( Q const& val )
/// Metafunction converting option list to \p TreiberStack traits
/**
- This is a wrapper for <tt> cds::opt::make_options< type_traits, Options...> </tt>
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.
- \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.
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
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 <tt>opt::v::hash_selector <opt::none></tt> 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<T>.
- - 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 <tt>opt::v::hash_selector <opt::none></tt>
+ 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<T>.
+ - \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 <tt>cds::container::striped_set::load_factor_resizing <4></tt>;
- 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 <tt>cds::container::striped_set::load_factor_resizing<4> </tt>;
+ 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 <tt>cds::opt::v::static_buffer< cds::any_type, 256 > </tt>.
- 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 <tt>adapt</tt> metafunction, see below.
+ You can pass other option that would be passed to \p adapt metafunction, see below.
<b>Internal details</b>
- 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.
</td>
<td>
The list is ordered.
- Template argument pack \p Options <b>must</b> contain cds::opt::less or cds::opt::compare for type \p T stored in the list
+ Template argument pack \p Options <b>must</b> contain \p cds::opt::less or \p cds::opt::compare for type \p T stored in the list
</td>
</tr>
<tr>
<td>
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.
</td>
</tr>
<tr>
\endcode
</td>
<td>
- 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. <tt>h1(X) != h2(X)</tt> 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 <tt> cds::opt::v::static_buffer< cds::any_type, 256 > </tt>.
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 <tt>cds::container::striped_set::load_factor_resizing<256> </tt> what gives load factor 1 for
default bucket buffer that is the best for \p boost::intrusive::unordered_set.
</td>
</tr>
<td>
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.
</td>
</tr>
<tr>
<td>
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.
</td>
</tr>
<tr>
<td>
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.
</td>
</tr>
<tr>
<td>
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.
</td>
</tr>
</table>
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
<tt>cds::intrusive::striped_set::adapt<MyBestContainer> </tt> metafunction providing necessary interface.
The <tt>intrusive::striped_set::adapt< Container, OptionPack ></tt> metafunction has two template argument:
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 <class Container, typename... Options>
#ifndef __CDS_INTRUSIVE_STRIPED_SET_ADAPTER_H
#define __CDS_INTRUSIVE_STRIPED_SET_ADAPTER_H
-#include <functional> // ref
#include <cds/opt/options.h>
#include <cds/intrusive/striped_set/resizing_policy.h>
#include <cds/opt/hash.h>
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.
<b>Bucket interface</b>
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
<tt>container.bucket_count() * LoadFactor</tt>
then resizing is needed.
};
/// Load factor based resizing policy, stateful specialization
- /**
+ /** @ingroup cds_striped_resizing_policy
This specialization allows to specify a load factor at runtime.
*/
template <>
/// 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.
/// Single bucket threshold resizing policy, stateful specialization
- /**
+ /** @ingroup cds_striped_resizing_policy
This specialization allows to specify and modify a threshold at runtime.
*/
template <>
};
/// 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.
/// Metafunction converting option list to \p treiber_stack::traits
/**
- This is a wrapper for <tt> cds::opt::make_options< type_traits, Options...> </tt>
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.
- 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
projects / libcds.git / commitdiff