-//$$CDS-header$$
+/*
+ This file is a part of libcds - Concurrent Data Structures library
-#ifndef __CDS_INTRUSIVE_CUCKOO_SET_H
-#define __CDS_INTRUSIVE_CUCKOO_SET_H
+ (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_INTRUSIVE_CUCKOO_SET_H
+#define CDSLIB_INTRUSIVE_CUCKOO_SET_H
#include <memory>
#include <type_traits>
#include <cds/intrusive/details/base.h>
#include <cds/opt/compare.h>
#include <cds/opt/hash.h>
-#include <cds/lock/array.h>
+#include <cds/sync/lock_array.h>
#include <cds/os/thread.h>
-#include <cds/lock/spinlock.h>
+#include <cds/sync/spinlock.h>
namespace cds { namespace intrusive {
/// CuckooSet-related definitions
namespace cuckoo {
-
/// Option to define probeset type
/**
The option specifies probeset type for the CuckooSet.
//@endcond
//@cond
- // Probeset type declarations.
+ /// List probeset type
struct list;
+ //@endcond
+
+ /// Vector probeset type
template <unsigned int Capacity>
struct vector
{
+ /// Vector capacity
static unsigned int const c_nCapacity = Capacity;
};
- //@endcond
/// CuckooSet node
/**
{
m_pNext = nullptr;
}
-
};
template <unsigned int VectorSize, typename Tag>
};
//@endcond
- typedef cds::lock::array< lock_type, cds::lock::pow2_select_policy, allocator_type > lock_array_type ; ///< lock array type
+ typedef cds::sync::lock_array< lock_type, cds::sync::pow2_select_policy, allocator_type > lock_array_type ; ///< lock array type
protected:
//@cond
protected:
//@cond
- lock_array m_Locks[c_nArity] ; ///< array of lock_array_type
+ lock_array m_Locks[c_nArity] ; ///< array of \p lock_array_type
statistics_type m_Stat ; ///< internal statistics
//@endcond
protected:
//@cond
- typedef cds::lock::trivial_select_policy lock_selection_policy;
+ typedef cds::sync::trivial_select_policy lock_selection_policy;
class lock_array_type
- : public cds::lock::array< lock_type, lock_selection_policy, allocator_type >
+ : public cds::sync::lock_array< lock_type, lock_selection_policy, allocator_type >
, public std::enable_shared_from_this< lock_array_type >
{
- typedef cds::lock::array< lock_type, lock_selection_policy, allocator_type > lock_array_base;
+ typedef cds::sync::lock_array< lock_type, lock_selection_policy, allocator_type > lock_array_base;
public:
lock_array_type( size_t nCapacity )
: lock_array_base( nCapacity )
typedef unsigned long long owner_t;
typedef cds::OS::ThreadId threadId_t;
- typedef cds::lock::Spin spinlock_type;
+ typedef cds::sync::spin spinlock_type;
typedef std::unique_lock< spinlock_type > scoped_spinlock;
//@endcond
for ( unsigned int i = 0; i < c_nArity; ++i )
pNew[i] = create_lock_array( nCapacity );
- /*
- // Assignment m_arrLocks[i] = pNew[i] may call heavy-weighted dtor for each item of m_arrLocks
- // that is unacceptable under spin-lock
- // So, we store copy of m_arrLocks in pOld
- lock_array_ptr pOld[ c_nArity ];
- for ( unsigned int i = 0; i < c_nArity; ++i )
- pOld[i] = m_arrLocks[i];
-
- // m_arrLocks assignment will not lead to calling dtor of each item of m_arrLocks
- // since copy of m_arrLocks locates in pOld and assignment will not be too painful for spin-lock
- */
-
{
scoped_spinlock sl(m_access);
for ( unsigned int i = 0; i < c_nArity; ++i )
}
};
- /// CuckooSet internal statistics
+ /// \p CuckooSet internal statistics
struct stat {
typedef cds::atomicity::event_counter counter_type ; ///< Counter type
- counter_type m_nRelocateCallCount ; ///< Count of \p relocate function call
+ counter_type m_nRelocateCallCount ; ///< Count of \p relocate() function call
counter_type m_nRelocateRoundCount ; ///< Count of attempts to relocate items
counter_type m_nFalseRelocateCount ; ///< Count of unneeded attempts of \p relocate call
- counter_type m_nSuccessRelocateCount ; ///< Count of successfull item relocating
+ counter_type m_nSuccessRelocateCount ; ///< Count of successful item relocating
counter_type m_nRelocateAboveThresholdCount; ///< Count of item relocating above probeset threshold
counter_type m_nFailedRelocateCount ; ///< Count of failed relocation attemp (when all probeset is full)
- counter_type m_nResizeCallCount ; ///< Count of \p resize function call
- counter_type m_nFalseResizeCount ; ///< Count of false \p resize function call (when other thread has been resized the set)
- counter_type m_nResizeSuccessNodeMove; ///< Count of successfull node moving when resizing
- counter_type m_nResizeRelocateCall ; ///< Count of \p relocate function call from \p resize function
+ counter_type m_nResizeCallCount ; ///< Count of \p resize() function call
+ counter_type m_nFalseResizeCount ; ///< Count of false \p resize() function call (when other thread has been resized the set)
+ counter_type m_nResizeSuccessNodeMove; ///< Count of successful node moving when resizing
+ counter_type m_nResizeRelocateCall ; ///< Count of \p relocate() function call from \p resize function
- counter_type m_nInsertSuccess ; ///< Count of successfull \p insert function call
- counter_type m_nInsertFailed ; ///< Count of failed \p insert function call
- counter_type m_nInsertResizeCount ; ///< Count of \p resize function call from \p insert
- counter_type m_nInsertRelocateCount ; ///< Count of \p relocate function call from \p insert
- counter_type m_nInsertRelocateFault ; ///< Count of failed \p relocate function call from \p insert
+ counter_type m_nInsertSuccess ; ///< Count of successful \p insert() function call
+ counter_type m_nInsertFailed ; ///< Count of failed \p insert() function call
+ counter_type m_nInsertResizeCount ; ///< Count of \p resize() function call from \p insert()
+ counter_type m_nInsertRelocateCount ; ///< Count of \p relocate() function call from \p insert()
+ counter_type m_nInsertRelocateFault ; ///< Count of failed \p relocate() function call from \p insert()
- counter_type m_nEnsureExistCount ; ///< Count of call \p ensure function for existing node
- counter_type m_nEnsureSuccessCount ; ///< Count of successfull \p insert function call for new node
- counter_type m_nEnsureResizeCount ; ///< Count of \p resize function call from \p ensure
- counter_type m_nEnsureRelocateCount ; ///< Count of \p relocate function call from \p ensure
- counter_type m_nEnsureRelocateFault ; ///< Count of failed \p relocate function call from \p ensure
+ counter_type m_nUpdateExistCount ; ///< Count of call \p update() function for existing node
+ counter_type m_nUpdateSuccessCount ; ///< Count of successful \p insert() function call for new node
+ counter_type m_nUpdateResizeCount ; ///< Count of \p resize() function call from \p update()
+ counter_type m_nUpdateRelocateCount ; ///< Count of \p relocate() function call from \p update()
+ counter_type m_nUpdateRelocateFault ; ///< Count of failed \p relocate() function call from \p update()
- counter_type m_nUnlinkSuccess ; ///< Count of success \p unlink function call
- counter_type m_nUnlinkFailed ; ///< Count of failed \p unlink function call
+ counter_type m_nUnlinkSuccess ; ///< Count of success \p unlink() function call
+ counter_type m_nUnlinkFailed ; ///< Count of failed \p unlink() function call
- counter_type m_nEraseSuccess ; ///< Count of success \p erase function call
- counter_type m_nEraseFailed ; ///< Count of failed \p erase function call
+ counter_type m_nEraseSuccess ; ///< Count of success \p erase() function call
+ counter_type m_nEraseFailed ; ///< Count of failed \p erase() function call
- counter_type m_nFindSuccess ; ///< Count of success \p find function call
- counter_type m_nFindFailed ; ///< Count of failed \p find function call
+ counter_type m_nFindSuccess ; ///< Count of success \p find() function call
+ counter_type m_nFindFailed ; ///< Count of failed \p find() function call
- counter_type m_nFindEqualSuccess ; ///< Count of success \p find_equal function call
- counter_type m_nFindEqualFailed ; ///< Count of failed \p find_equal function call
+ counter_type m_nFindEqualSuccess ; ///< Count of success \p find_equal() function call
+ counter_type m_nFindEqualFailed ; ///< Count of failed \p find_equal() function call
- counter_type m_nFindWithSuccess ; ///< Count of success \p find_with function call
- counter_type m_nFindWithFailed ; ///< Count of failed \p find_with function call
+ counter_type m_nFindWithSuccess ; ///< Count of success \p find_with() function call
+ counter_type m_nFindWithFailed ; ///< Count of failed \p find_with() function call
//@cond
void onRelocateCall() { ++m_nRelocateCallCount; }
void onInsertRelocate() { ++m_nInsertRelocateCount; }
void onInsertRelocateFault() { ++m_nInsertRelocateFault; }
- void onEnsureExist() { ++m_nEnsureExistCount; }
- void onEnsureSuccess() { ++m_nEnsureSuccessCount; }
- void onEnsureResize() { ++m_nEnsureResizeCount; }
- void onEnsureRelocate() { ++m_nEnsureRelocateCount; }
- void onEnsureRelocateFault() { ++m_nEnsureRelocateFault; }
+ void onUpdateExist() { ++m_nUpdateExistCount; }
+ void onUpdateSuccess() { ++m_nUpdateSuccessCount; }
+ void onUpdateResize() { ++m_nUpdateResizeCount; }
+ void onUpdateRelocate() { ++m_nUpdateRelocateCount; }
+ void onUpdateRelocateFault() { ++m_nUpdateRelocateFault; }
void onUnlinkSuccess() { ++m_nUnlinkSuccess; }
void onUnlinkFailed() { ++m_nUnlinkFailed; }
void onInsertRelocate() const {}
void onInsertRelocateFault() const {}
- void onEnsureExist() const {}
- void onEnsureSuccess() const {}
- void onEnsureResize() const {}
- void onEnsureRelocate() const {}
- void onEnsureRelocateFault() const {}
+ void onUpdateExist() const {}
+ void onUpdateSuccess() const {}
+ void onUpdateResize() const {}
+ void onUpdateRelocate() const {}
+ void onUpdateRelocateFault() const {}
void onUnlinkSuccess() const {}
void onUnlinkFailed() const {}
};
template <typename Node, unsigned int Capacity>
- class bucket_entry<Node, cuckoo::vector<Capacity> >
+ class bucket_entry<Node, cuckoo::vector<Capacity>>
{
public:
typedef Node node_type;
{
assert( m_nSize < c_nCapacity );
- // std alorithm
if ( nFrom < m_nSize )
std::copy_backward( m_arrNode + nFrom, m_arrNode + m_nSize, m_arrNode + m_nSize + 1 );
-
- // alternative: low-level byte copying
- //memmove( m_arrNode + nFrom + 1, m_arrNode + nFrom, (m_nSize - nFrom) * sizeof(m_arrNode[0]) );
}
void shift_down( node_type ** pFrom )
{
assert( m_arrNode <= pFrom && pFrom < m_arrNode + m_nSize);
- // std algo
- std::copy( pFrom + 1, m_arrNode + m_nSize, pFrom );
-
- // alternative: low-level byte copying
- //memmove( pFrom + 1, pFrom, (m_nSize - nFrom - 1) * sizeof(m_arrNode[0]));
+ std::copy( pFrom + 1, m_arrNode + m_nSize, pFrom );
}
public:
class iterator
assert( !it.pArr || (m_arrNode <= it.pArr && it.pArr <= m_arrNode + m_nSize));
if ( it.pArr ) {
- shift_up( (unsigned int)(it.pArr - m_arrNode) + 1 );
- *(it.pArr + 1) = p;
+ shift_up( static_cast<unsigned int>(it.pArr - m_arrNode) + 1 );
+ it.pArr[1] = p;
}
else {
shift_up(0);
struct hash_ops {
static void store( Node * pNode, size_t * pHashes )
{
- memcpy( pNode->m_arrHash, pHashes, sizeof(size_t) * ArraySize );
+ memcpy( pNode->m_arrHash, pHashes, sizeof(pHashes[0]) * ArraySize );
}
static bool equal_to( Node& node, unsigned int nTable, size_t nHash )
{
<b>About Cuckoo hashing</b>
[From <i>"The Art of Multiprocessor Programming"</i>]
- Cuckoo hashing is a hashing algorithm in which a newly added item displaces any earlier item
+ <a href="https://en.wikipedia.org/wiki/Cuckoo_hashing">Cuckoo hashing</a> is a hashing algorithm in which a newly added item displaces any earlier item
occupying the same slot. For brevity, a table is a k-entry array of items. For a hash set f size
N = 2k we use a two-entry array of tables, and two independent hash functions,
<tt> h0, h1: KeyRange -> 0,...,k-1</tt>
the average search complexity is <tt>O(PROBE_SET/2)</tt>.
However, the overhead of sorting can eliminate a gain of ordered search.
- The probe set is ordered if opt::compare or opt::less is specified in \p Traits template
- parameter. Otherwise, the probe set is unordered and \p Traits must contain
- opt::equal_to option.
+ The probe set is ordered if \p compare or \p less is specified in \p Traits template
+ parameter. Otherwise, the probe set is unordered and \p Traits should provide
+ \p equal_to predicate.
- The cds::intrusive::cuckoo namespace contains \p %CuckooSet-related declarations.
+ The \p cds::intrusive::cuckoo namespace contains \p %CuckooSet-related declarations.
Template arguments:
- - \p T - the type stored in the set. The type must be based on cuckoo::node (for cuckoo::base_hook)
- or it must have a member of type %cuckoo::node (for cuckoo::member_hook),
- or it must be convertible to \p %cuckoo::node (for cuckoo::traits_hook)
- - \p Traits - type traits, default is cuckoo::traits. It is possible to declare option-based
+ - \p T - the type stored in the set. The type must be based on \p cuckoo::node (for \p cuckoo::base_hook)
+ or it must have a member of type %cuckoo::node (for \p cuckoo::member_hook),
+ or it must be convertible to \p %cuckoo::node (for \p cuckoo::traits_hook)
+ - \p Traits - type traits, default is \p cuckoo::traits. It is possible to declare option-based
set with \p cuckoo::make_traits metafunction result as \p Traits template argument.
<b>How to use</b>
typedef typename traits::mutex_policy original_mutex_policy; ///< Concurrent access policy, see \p cuckoo::traits::mutex_policy
- /// Actual mutex policy
- /**
- Actual mutex policy is built from mutex policy type provided by \p Traits template argument (see \p cuckoo::traits::mutex_policy)
- but mutex policy internal statistics is conformed with \p cukoo::traits::stat type provided by \p Traits:
- - if \p %cuckoo::traits::stat is \p cuckoo::empty_stat then mutex policy statistics is already empty
- - otherwise real mutex policy statistics is used
- */
+ //@cond
typedef typename original_mutex_policy::template rebind_statistics<
typename std::conditional<
std::is_same< stat, cuckoo::empty_stat >::value
,typename original_mutex_policy::real_stat
>::type
>::other mutex_policy;
+ //@endcond
+ /// Probe set should be ordered or not
+ /**
+ If \p Traits specifies \p cmpare or \p less functor then the set is ordered.
+ Otherwise, it is unordered and \p Traits should provide \p equal_to functor.
+ */
static bool const c_isSorted = !( std::is_same< typename traits::compare, opt::none >::value
- && std::is_same< typename traits::less, opt::none >::value ) ; ///< whether the probe set should be ordered
+ && std::is_same< typename traits::less, opt::none >::value );
static size_t const c_nArity = hash::size ; ///< the arity of cuckoo hashing: the number of hash functors provided; minimum 2.
/// Key equality functor; used only for unordered probe-set
typedef typename opt::details::make_equal_to< value_type, traits, !c_isSorted>::type key_equal_to;
- /// key comparing functor based on opt::compare and opt::less option setter. Used only for ordered probe set
+ /// key comparing functor based on \p opt::compare and \p opt::less option setter. Used only for ordered probe set
typedef typename opt::details::make_comparator< value_type, traits >::type key_comparator;
/// allocator type
bucket_iterator itFound;
};
- typedef typename std::conditional< c_isSorted
- , cuckoo::details::contains< node_traits, true >
- , cuckoo::details::contains< node_traits, false >
- >::type contains_action;
+ typedef cuckoo::details::contains< node_traits, c_isSorted > contains_action;
template <typename Predicate>
struct predicate_wrapper {
static void store_hash( node_type * pNode, size_t * pHashes )
{
cuckoo::details::hash_ops< node_type, c_nNodeHashArraySize >::store( pNode, pHashes );
- //memcpy( pNode->m_arrHash, pHashes, sizeof(size_t) * c_nArity );
}
static bool equal_hash( node_type& node, unsigned int nTable, size_t nHash )
free_bucket_tables( m_BucketTable, m_nBucketMask + 1 );
}
- static unsigned int const c_nUndefTable = (unsigned int) -1;
+ static CDS_CONSTEXPR unsigned int const c_nUndefTable = (unsigned int) -1;
template <typename Q, typename Predicate >
unsigned int contains( position * arrPos, size_t * arrHash, Q const& val, Predicate pred )
{
CDS_CONSTEXPR static unsigned int calc_probeset_size( unsigned int nProbesetSize ) CDS_NOEXCEPT
{
- return nProbesetSize
- ? nProbesetSize
- : ( node_type::probeset_size ? node_type::probeset_size : c_nDefaultProbesetSize )
-;
+ return std::is_same< probeset_class, cuckoo::vector_probeset_class >::value
+ ? node_type::probeset_size
+ : (nProbesetSize
+ ? nProbesetSize
+ : ( node_type::probeset_size ? node_type::probeset_size : c_nDefaultProbesetSize ));
}
//@endcond
/// Constructs the set object with given probe set size and threshold
/**
If probe set type is <tt> cuckoo::vector<Capacity> </tt> vector
- then \p nProbesetSize should be equal to vector's \p Capacity.
+ then \p nProbesetSize is ignored since it should be equal to vector's \p Capacity.
*/
CuckooSet(
- size_t nInitialSize ///< Initial set size; if 0 - use default initial size \ref c_nDefaultInitialSize
+ size_t nInitialSize ///< Initial set size; if 0 - use default initial size \p c_nDefaultInitialSize
, unsigned int nProbesetSize ///< probe set size
- , unsigned int nProbesetThreshold = 0 ///< probe set threshold, <tt>nProbesetThreshold < nProbesetSize</tt>. If 0, nProbesetThreshold = nProbesetSize - 1
+ , unsigned int nProbesetThreshold = 0 ///< probe set threshold, <tt>nProbesetThreshold < nProbesetSize</tt>. If 0, <tt>nProbesetThreshold = nProbesetSize - 1</tt>
)
: m_nProbesetSize( calc_probeset_size(nProbesetSize) )
, m_nProbesetThreshold( nProbesetThreshold ? nProbesetThreshold : m_nProbesetSize - 1 )
/// Constructs the set object with given hash functor tuple
/**
- The probe set size and threshold are set as default, see CuckooSet()
+ The probe set size and threshold are set as default, see \p CuckooSet()
*/
CuckooSet(
hash_tuple_type const& h ///< hash functor tuple of type <tt>std::tuple<H1, H2, ... Hn></tt> where <tt> n == \ref c_nArity </tt>
then \p nProbesetSize should be equal to vector's \p Capacity.
*/
CuckooSet(
- size_t nInitialSize ///< Initial set size; if 0 - use default initial size \ref c_nDefaultInitialSize
+ size_t nInitialSize ///< Initial set size; if 0 - use default initial size \p c_nDefaultInitialSize
, unsigned int nProbesetSize ///< probe set size, positive integer
- , unsigned int nProbesetThreshold ///< probe set threshold, <tt>nProbesetThreshold < nProbesetSize</tt>. If 0, nProbesetThreshold = nProbesetSize - 1
+ , unsigned int nProbesetThreshold ///< probe set threshold, <tt>nProbesetThreshold < nProbesetSize</tt>. If 0, <tt>nProbesetThreshold = nProbesetSize - 1</tt>
, hash_tuple_type const& h ///< hash functor tuple of type <tt>std::tuple<H1, H2, ... Hn></tt> where <tt> n == \ref c_nArity </tt>
)
: m_nProbesetSize( calc_probeset_size(nProbesetSize) )
/// Constructs the set object with given hash functor tuple (move semantics)
/**
- The probe set size and threshold are set as default, see CuckooSet()
+ The probe set size and threshold are set as default, see \p CuckooSet()
*/
CuckooSet(
hash_tuple_type&& h ///< hash functor tuple of type <tt>std::tuple<H1, H2, ... Hn></tt> where <tt> n == \ref c_nArity </tt>
then \p nProbesetSize should be equal to vector's \p Capacity.
*/
CuckooSet(
- size_t nInitialSize ///< Initial set size; if 0 - use default initial size \ref c_nDefaultInitialSize
+ size_t nInitialSize ///< Initial set size; if 0 - use default initial size \p c_nDefaultInitialSize
, unsigned int nProbesetSize ///< probe set size, positive integer
- , unsigned int nProbesetThreshold ///< probe set threshold, <tt>nProbesetThreshold < nProbesetSize</tt>. If 0, nProbesetThreshold = nProbesetSize - 1
+ , unsigned int nProbesetThreshold ///< probe set threshold, <tt>nProbesetThreshold < nProbesetSize</tt>. If 0, <tt>nProbesetThreshold = nProbesetSize - 1</tt>
, hash_tuple_type&& h ///< hash functor tuple of type <tt>std::tuple<H1, H2, ... Hn></tt> where <tt> n == \ref c_nArity </tt>
)
: m_nProbesetSize( calc_probeset_size(nProbesetSize) )
public:
/// Inserts new node
/**
- The function inserts \p val in the set if it does not contain
- an item with key equal to \p val.
+ The function inserts \p val in the set if it does not contain an item with key equal to \p val.
- Returns \p true if \p val is placed into the set, \p false otherwise.
+ Returns \p true if \p val is inserted into the set, \p false otherwise.
*/
bool insert( value_type& val )
{
return true;
}
- /// Ensures that the \p val exists in the set
+ /// Updates the node
/**
The operation performs inserting or changing data with lock-free manner.
- If the item \p val not found in the set, then \p val is inserted into the set.
+ If the item \p val is not found in the set, then \p val is inserted into the set
+ iff \p bAllowInsert is \p true.
Otherwise, the functor \p func is called with item found.
- The functor signature is:
+ The functor \p func signature is:
\code
void func( bool bNew, value_type& item, value_type& val );
\endcode
with arguments:
- \p bNew - \p true if the item has been inserted, \p false otherwise
- \p item - item of the set
- - \p val - argument \p val passed into the \p ensure function
+ - \p val - argument \p val passed into the \p %update() function
If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
- refers to the same thing.
+ refer to the same thing.
The functor may change non-key fields of the \p item.
- Returns <tt> std::pair<bool, bool> </tt> where \p first is \p true if operation is successful,
+ Returns std::pair<bool, bool> where \p first is \p true if operation is successful,
+ i.e. the node has been inserted or updated,
\p second is \p true if new item has been added or \p false if the item with \p key
- already is in the set.
+ already exists.
*/
template <typename Func>
- std::pair<bool, bool> ensure( value_type& val, Func func )
+ std::pair<bool, bool> update( value_type& val, Func func, bool bAllowInsert = true )
{
hash_array arrHash;
position arrPos[ c_nArity ];
unsigned int nTable = contains( arrPos, arrHash, val, key_predicate() );
if ( nTable != c_nUndefTable ) {
func( false, *node_traits::to_value_ptr( *arrPos[nTable].itFound ), val );
- m_Stat.onEnsureExist();
+ m_Stat.onUpdateExist();
return std::make_pair( true, false );
}
- node_type * pNode = node_traits::to_node_ptr( val );
- store_hash( pNode, arrHash );
+ if ( !bAllowInsert )
+ return std::make_pair( false, false );
+
+ //node_type * pNode = node_traits::to_node_ptr( val );
+ //store_hash( pNode, arrHash );
for ( unsigned int i = 0; i < c_nArity; ++i ) {
bucket_entry& refBucket = bucket( i, arrHash[i] );
refBucket.insert_after( arrPos[i].itPrev, pNode );
func( true, val, val );
++m_ItemCounter;
- m_Stat.onEnsureSuccess();
+ m_Stat.onUpdateSuccess();
return std::make_pair( true, true );
}
}
}
}
- m_Stat.onEnsureResize();
+ m_Stat.onUpdateResize();
resize();
}
do_relocate:
- m_Stat.onEnsureRelocate();
+ m_Stat.onUpdateRelocate();
if ( !relocate( nGoalTable, arrHash )) {
- m_Stat.onEnsureRelocateFault();
- m_Stat.onEnsureResize();
+ m_Stat.onUpdateRelocateFault();
+ m_Stat.onUpdateResize();
resize();
}
- m_Stat.onEnsureSuccess();
+ m_Stat.onUpdateSuccess();
return std::make_pair( true, true );
}
+ //@cond
+ template <typename Func>
+ CDS_DEPRECATED("ensure() is deprecated, use update()")
+ std::pair<bool, bool> ensure( value_type& val, Func func )
+ {
+ return update( val, func, true );
+ }
+ //@endcond
/// Unlink the item \p val from the set
/**
{
return find_( val, key_predicate(), f );
}
+ //@cond
+ template <typename Q, typename Func>
+ bool find( Q const& val, Func f )
+ {
+ return find_( val, key_predicate(), f );
+ }
+ //@endcond
/// Find the key \p val using \p pred predicate for comparing
/**
CDS_UNUSED( pred );
return find_( val, typename predicate_wrapper<Predicate>::type(), f );
}
-
- /// Find the key \p val
- /** \anchor cds_intrusive_CuckooSet_find_cfunc
- The function searches the item with key equal to \p val and calls the functor \p f for item found.
- The interface of \p Func functor is:
- \code
- struct functor {
- void operator()( value_type& item, Q const& val );
- };
- \endcode
- where \p item is the item found, \p val is the <tt>find</tt> function argument.
-
- The functor may 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
- may modify both arguments.
-
- The function returns \p true if \p val is found, \p false otherwise.
- */
- template <typename Q, typename Func>
- bool find( Q const& val, Func f )
- {
- return find_( val, key_predicate(), f );
- }
-
- /// Find the key \p val using \p pred predicate for comparing
- /**
- The function is an analog of \ref cds_intrusive_CuckooSet_find_cfunc "find(Q const&, Func)"
- but \p pred is used for key comparison.
- If you use ordered cuckoo set, then \p Predicate should have the interface and semantics like \p std::less.
- If you use unordered cuckoo set, then \p Predicate should have the interface and semantics like \p std::equal_to.
- \p pred must imply the same element order as the comparator used for building the set.
- */
+ //@cond
template <typename Q, typename Predicate, typename Func>
bool find_with( Q const& val, Predicate pred, Func f )
{
CDS_UNUSED( pred );
return find_( val, typename predicate_wrapper<Predicate>::type(), f );
}
+ //@endcond
- /// Find the key \p val
- /** \anchor cds_intrusive_CuckooSet_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 \p value_type.
*/
template <typename Q>
- bool find( Q const& val )
+ bool contains( Q const& key )
+ {
+ return find( key, [](value_type&, Q const& ) {} );
+ }
+ //@cond
+ template <typename Q>
+ CDS_DEPRECATED("deprecated, use contains()")
+ bool find( Q const& key )
{
- return find( val, [](value_type&, Q const& ) {} );
+ return contains( key );
}
+ //@endcond
- /// Find the key \p val using \p pred predicate for comparing
+ /// Checks whether the set contains \p key using \p pred predicate for searching
/**
- The function is an analog of \ref cds_intrusive_CuckooSet_find_val "find(Q const&)"
- but \p pred is used for key comparison.
- If you use ordered cuckoo set, then \p Predicate should have the interface and semantics like \p std::less.
- If you use unordered cuckoo set, then \p Predicate should have the interface and semantics like \p std::equal_to.
- \p pred must imply the same element order as the comparator used for building the set.
+ The function is similar to <tt>contains( key )</tt> but \p pred is used for key comparing.
+ If the set is unordered, \p Predicate has semantics like \p std::equal_to.
+ For ordered set \p Predicate has \p std::less semantics. In that case \p pred
+ must imply the same element order as the comparator used for building the set.
*/
template <typename Q, typename Predicate>
- bool find_with( Q const& val, Predicate pred )
+ bool contains( Q const& key, Predicate pred )
{
CDS_UNUSED( pred );
- return find_with( val, typename predicate_wrapper<Predicate>::type(), [](value_type& , Q const& ) {} );
+ return find_with( key, typename predicate_wrapper<Predicate>::type(), [](value_type& , Q const& ) {} );
}
+ //@cond
+ template <typename Q, typename Predicate>
+ CDS_DEPRECATED("deprecated, use contains()")
+ bool find_with( Q const& key, Predicate pred )
+ {
+ return contains( key, pred );
+ }
+ //@endcond
/// Clears the set
/**
The function unlinks all items from the set.
- For any item \ref disposer is called
+ For any item <tt> @ref disposer</tt> is called
*/
void clear()
{
/// Clears the set and calls \p disposer for each item
/**
- The function unlinks all items from the set calling \p disposer for each item.
+ The function unlinks all items from the set calling \p oDisposer for each item.
\p Disposer functor interface is:
\code
struct Disposer{
};
\endcode
- The \ref disposer specified in \p Traits traits is not called.
+ The <tt> @ref disposer</tt> specified in \p Traits is not called.
*/
template <typename Disposer>
void clear_and_dispose( Disposer oDisposer )
};
}} // namespace cds::intrusive
-#endif // #ifndef __CDS_INTRUSIVE_CUCKOO_SET_H
+#endif // #ifndef CDSLIB_INTRUSIVE_CUCKOO_SET_H