-//$$CDS-header$$
-
-#ifndef __CDS_CONTAINER_STRIPED_SET_H
-#define __CDS_CONTAINER_STRIPED_SET_H
+/*
+ This file is a part of libcds - Concurrent Data Structures library
+
+ (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016
+
+ Source code repo: http://github.com/khizmax/libcds/
+ Download: http://sourceforge.net/projects/libcds/files/
+
+ Redistribution and use in source and binary forms, with or without
+ modification, are permitted provided that the following conditions are met:
+
+ * Redistributions of source code must retain the above copyright notice, this
+ list of conditions and the following disclaimer.
+
+ * Redistributions in binary form must reproduce the above copyright notice,
+ this list of conditions and the following disclaimer in the documentation
+ and/or other materials provided with the distribution.
+
+ THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+ DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
+ FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
+ CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
+ OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+*/
+
+#ifndef CDSLIB_CONTAINER_STRIPED_SET_H
+#define CDSLIB_CONTAINER_STRIPED_SET_H
#include <cds/intrusive/striped_set.h>
#include <cds/container/striped_set/adapter.h>
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>
typedef typename base_class::scoped_resize_lock scoped_resize_lock;
//@endcond
- protected:
- //@cond
-# ifndef CDS_CXX11_LAMBDA_SUPPORT
- struct empty_insert_functor {
- void operator()( value_type& )
- {}
- };
-
- struct empty_erase_functor {
- void operator()( value_type const& )
- {}
- };
-
- struct empty_find_functor {
- template <typename Q>
- void operator()( value_type& item, Q& val )
- {}
- };
-# endif
- //@endcond
-
public:
/// Default ctor. The initial capacity is 16.
StripedSet()
- : base_class()
+ : base_class()
{}
/// Ctor with initial capacity specified
StripedSet(
size_t nCapacity ///< Initial size of bucket table and lock array. Must be power of two, the minimum is 16.
- ) : base_class( nCapacity )
+ )
+
+ : base_class( nCapacity )
{}
/// Ctor with resizing policy (copy semantics)
StripedSet(
size_t nCapacity ///< Initial size of bucket table and lock array. Must be power of two, the minimum is 16.
,resizing_policy const& resizingPolicy ///< Resizing policy
- ) : base_class( nCapacity, resizingPolicy )
+ )
+
+ : base_class( nCapacity, resizingPolicy )
{}
/// Ctor with resizing policy (move semantics)
StripedSet(
size_t nCapacity ///< Initial size of bucket table and lock array. Must be power of two, the minimum is 16.
,resizing_policy&& resizingPolicy ///< Resizing policy
- ) : base_class( nCapacity, std::forward<resizing_policy>(resizingPolicy) )
+ )
+
+ : base_class( nCapacity, std::forward<resizing_policy>(resizingPolicy) )
{}
/// Destructor destroys internal data
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.
*/
template <typename Q>
bool insert( Q const& val )
{
-# ifdef CDS_CXX11_LAMBDA_SUPPORT
return insert( val, []( value_type& ) {} );
-# else
- return insert( val, empty_insert_functor() );
-# endif
}
/// Inserts new node
\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. It can be passed by reference
- using <tt>boost::ref</tt>
+ The user-defined functor is called only if the inserting is success.
*/
template <typename Q, typename Func>
bool insert( Q const& val, Func f )
{
bool bOk;
bool bResize;
- size_t nHash = base_class::hashing( value_type( std::forward<Args>(args)...));
+ value_type val( std::forward<Args>( args )... );
+ size_t nHash = base_class::hashing( val );
bucket_type * pBucket;
{
scoped_cell_lock sl( base_class::m_MutexPolicy, nHash );
pBucket = base_class::bucket( nHash );
- bOk = pBucket->emplace( std::forward<Args>(args)...);
+ bOk = pBucket->emplace( std::move( val ));
bResize = bOk && base_class::m_ResizingPolicy( ++base_class::m_ItemCounter, *this, *pBucket );
}
return bOk;
}
- /// Ensures that the \p val exists in the set
+ /// Updates the node
/**
- The operation performs inserting or changing data.
+ The operation performs inserting or changing data with lock-free manner.
- If the \p val key not found in the set, then the new item created from \p val
- is inserted into the set. Otherwise, the functor \p func is called with the item found.
- The functor \p Func should be a function with signature:
- \code
- void func( bool bNew, value_type& item, const Q& val );
- \endcode
- or a functor:
+ If \p key is not found in the set, then \p key is inserted iff \p bAllowInsert is \p true.
+ Otherwise, the functor \p func is called with item found.
+
+ The functor signature is:
\code
struct my_functor {
void operator()( bool bNew, value_type& item, const Q& val );
};
\endcode
-
with arguments:
- \p bNew - \p true if the item has been inserted, \p false otherwise
- - \p item - item of the list
- - \p val - argument \p val passed into the \p ensure function
+ - \p item - item of the set
+ - \p val - argument \p val passed into the \p %update() function
- The functor can change non-key fields of the \p item.
+ The functor may change non-key fields of the \p item.
- You can pass \p func argument by value or by reference using <tt>boost::ref</tt>.
-
- 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 val key
- already exists.
+ Returns <tt> std::pair<bool, bool> </tt> where \p first is true if operation is successful,
+ \p second is true if new item has been added or \p false if the item with \p key
+ already is in the map.
*/
template <typename Q, typename Func>
- std::pair<bool, bool> ensure( Q const& val, Func func )
+ std::pair<bool, bool> update( Q const& val, Func func, bool bAllowInsert = true )
{
std::pair<bool, bool> result;
- bool bResize;
+ bool bResize = false;
size_t nHash = base_class::hashing( val );
bucket_type * pBucket;
{
scoped_cell_lock sl( base_class::m_MutexPolicy, nHash );
pBucket = base_class::bucket( nHash );
- result = pBucket->ensure( val, func );
- bResize = result.first && result.second && base_class::m_ResizingPolicy( ++base_class::m_ItemCounter, *this, *pBucket );
+ result = pBucket->update( val, func, bAllowInsert );
+ if ( result.first && result.second )
+ bResize = base_class::m_ResizingPolicy( ++base_class::m_ItemCounter, *this, *pBucket );
}
if ( bResize )
base_class::resize();
return result;
}
+ //@cond
+ template <typename Q, typename Func>
+ CDS_DEPRECATED("ensure() is deprecated, use update()")
+ std::pair<bool, bool> ensure( Q const& val, Func func )
+ {
+ return update( val, func, true );
+ }
+ //@endcond
/// Delete \p key from the set
/** \anchor cds_nonintrusive_StripedSet_erase
template <typename Q>
bool erase( Q const& key )
{
-# ifdef CDS_CXX11_LAMBDA_SUPPORT
return erase( key, [](value_type const&) {} );
-# else
- return erase( key, empty_erase_functor() );
-# endif
}
/// Deletes the item from the set using \p pred predicate for searching
,typename Bucket = bucket_type, typename = typename std::enable_if< Bucket::has_erase_with >::type >
bool erase_with( Q const& key, Less pred )
{
-# ifdef CDS_CXX11_LAMBDA_SUPPORT
return erase_with( key, pred, [](value_type const&) {} );
-# else
- return erase_with( key, pred, empty_erase_functor() );
-# endif
}
/// Delete \p key from the set
void operator()(value_type const& val);
};
\endcode
- The functor can be passed by value or by reference using <tt>boost:ref</tt>
Return \p true if key is found and deleted, \p false otherwise
*/
\endcode
where \p item is the item found, \p val is the <tt>find</tt> function argument.
- You can pass \p f argument by value or by reference using <tt>boost::ref</tt> or cds::ref.
-
The functor can change non-key fields of \p item.
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.
\endcode
where \p item is the item found, \p val is the <tt>find</tt> function argument.
- You can pass \p f argument by value or by reference using <tt>boost::ref</tt> or cds::ref.
-
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.
return base_class::find_with( val, pred, f );
}
- /// Find the key \p val
- /** \anchor cds_nonintrusive_StripedSet_find_val
-
- The function searches the item with key equal to \p val
+ /// Checks whether the set contains \p key
+ /**
+ The function searches the item with key equal to \p key
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.
+ Otherwise, you may use \p contains( Q const&, Less pred ) functions with explicit predicate for key comparing.
*/
template <typename Q>
- bool find( Q const& val )
+ bool contains( Q const& key )
+ {
+ return base_class::contains( key );
+ }
+ //@cond
+ template <typename Q>
+ CDS_DEPRECATED("use contains()")
+ bool find( Q const& key )
{
- return base_class::find( val );
+ return contains( key );
}
+ //@endcond
- /// Find the key \p val using \p pred predicate
+ /// Checks whether the map contains \p key using \p pred predicate for searching
/**
- The function is an analog of \ref cds_nonintrusive_StripedSet_find_val "find(Q const&)"
- but \p pred is used for key comparing
- \p Less has the interface like \p std::less.
- \p pred must imply the same element order as the comparator used for building the set.
-
- @note This function is enabled if the compiler supports C++11
- default template arguments for function template <b>and</b> the underlying container
- supports \p %find_with feature.
+ The function is similar to <tt>contains( key )</tt> but \p pred is used for key comparing.
+ \p Less functor has the interface like \p std::less.
+ \p Less must imply the same element order as the comparator used for building the map.
*/
template <typename Q, typename Less
, typename Bucket = bucket_type, typename = typename std::enable_if< Bucket::has_find_with >::type >
+ bool contains( Q const& key, Less pred )
+ {
+ return base_class::contains( key, pred );
+ }
+ //@cond
+ template <typename Q, typename Less
+ , typename Bucket = bucket_type, typename = typename std::enable_if< Bucket::has_find_with >::type >
+ CDS_DEPRECATED("use contains()")
bool find_with( Q const& val, Less pred )
{
- return base_class::find_with( val, pred );
+ return contains( val, pred );
}
+ //@endcond
/// Clears the set
/**
}} // namespace cds::container
-#endif // #ifndef __CDS_CONTAINER_STRIPED_SET_H
+#endif // #ifndef CDSLIB_CONTAINER_STRIPED_SET_H
projects / libcds.git / blobdiff