X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=cds%2Fintrusive%2Fcuckoo_set.h;h=9e7d794e7b1b22850a4d1a80c251497e600aebce;hb=5fc87a172bd82f8a7040b8b83f32ce0e635e82ea;hp=89a9fd167bd3718143bfe679197d05001d427f94;hpb=785a8577b9d9ad4988c494055a9a95f1cbf62d65;p=libcds.git diff --git a/cds/intrusive/cuckoo_set.h b/cds/intrusive/cuckoo_set.h index 89a9fd16..9e7d794e 100644 --- a/cds/intrusive/cuckoo_set.h +++ b/cds/intrusive/cuckoo_set.h @@ -1,26 +1,52 @@ -//$$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-2017 + + Source code repo: http://github.com/khizmax/libcds/ + Download: http://sourceforge.net/projects/libcds/files/ + + Redistribution and use in source and binary forms, with or without + modification, are permitted provided that the following conditions are met: + + * Redistributions of source code must retain the above copyright notice, this + list of conditions and the following disclaimer. + + * Redistributions in binary form must reproduce the above copyright notice, + this list of conditions and the following disclaimer in the documentation + and/or other materials provided with the distribution. + + THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" + AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE + FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR + SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER + CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, + OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. +*/ + +#ifndef CDSLIB_INTRUSIVE_CUCKOO_SET_H +#define CDSLIB_INTRUSIVE_CUCKOO_SET_H #include #include #include -#include +#include // ref +#include #include #include -#include -#include +#include #include -#include -#include +#include namespace cds { namespace intrusive { /// CuckooSet-related definitions namespace cuckoo { - /// Option to define probeset type /** The option specifies probeset type for the CuckooSet. @@ -77,14 +103,17 @@ namespace cds { namespace intrusive { //@endcond //@cond - // Probeset type declarations. + /// List probeset type struct list; + //@endcond + + /// Vector probeset type template struct vector { + /// Vector capacity static unsigned int const c_nCapacity = Capacity; }; - //@endcond /// CuckooSet node /** @@ -93,8 +122,7 @@ namespace cds { namespace intrusive { or \p cds::intrusive::cuckoo::vector. - \p StoreHashCount - constant that defines whether to store node hash values. See cuckoo::store_hash option for explanation - - Tag - a tag used to distinguish between different implementation when two or more - \p node is needed in single struct. + - \p Tag - a \ref cds_intrusive_hook_tag "tag" */ template struct node @@ -171,7 +199,6 @@ namespace cds { namespace intrusive { { m_pNext = nullptr; } - }; template @@ -239,14 +266,14 @@ namespace cds { namespace intrusive { typedef opt::none tag; }; - template < typename HookType, CDS_DECL_OPTIONS3> + template < typename HookType, typename... Options> struct hook { - typedef typename opt::make_options< default_hook, CDS_OPTIONS3>::type options; + typedef typename opt::make_options< default_hook, Options...>::type traits; - typedef typename options::probeset_type probeset_type; - typedef typename options::tag tag; - static unsigned int const store_hash = options::store_hash; + typedef typename traits::probeset_type probeset_type; + typedef typename traits::tag tag; + static unsigned int const store_hash = traits::store_hash; typedef node node_type; @@ -257,12 +284,12 @@ namespace cds { namespace intrusive { /// Base hook /** \p Options are: - - cuckoo::probeset_type - probeset type. Defaul is \p cuckoo::list - - cuckoo::store_hash - store hash values in the node or not. Default is 0 (no storing) - - opt::tag - tag to distinguish different nodes in one struct. Default is opt::none + - \p cuckoo::probeset_type - probeset type. Defaul is \p cuckoo::list + - \p cuckoo::store_hash - store hash values in the node or not. Default is 0 (no storing) + - \p opt::tag - a \ref cds_intrusive_hook_tag "tag" */ - template < CDS_DECL_OPTIONS3 > - struct base_hook: public hook< opt::base_hook_tag, CDS_OPTIONS3 > + template < typename... Options > + struct base_hook: public hook< opt::base_hook_tag, Options... > {}; /// Member hook @@ -271,12 +298,12 @@ namespace cds { namespace intrusive { Use \p offsetof macro to define \p MemberOffset \p Options are: - - cuckoo::probeset_type - probeset type. Defaul is \p cuckoo::list - - cuckoo::store_hash - store hash values in the node or not. Default is 0 (no storing) - - opt::tag - tag to distinguish different nodes in one struct. Default is opt::none + - \p cuckoo::probeset_type - probeset type. Defaul is \p cuckoo::list + - \p cuckoo::store_hash - store hash values in the node or not. Default is 0 (no storing) + - \p opt::tag - a \ref cds_intrusive_hook_tag "tag" */ - template < size_t MemberOffset, CDS_DECL_OPTIONS3 > - struct member_hook: public hook< opt::member_hook_tag, CDS_OPTIONS3 > + template < size_t MemberOffset, typename... Options > + struct member_hook: public hook< opt::member_hook_tag, Options... > { //@cond static const size_t c_nMemberOffset = MemberOffset; @@ -289,12 +316,12 @@ namespace cds { namespace intrusive { See \ref node_traits for \p NodeTraits interface description \p Options are: - - cuckoo::probeset_type - probeset type. Defaul is \p cuckoo::list - - cuckoo::store_hash - store hash values in the node or not. Default is 0 (no storing) - - opt::tag - tag to distinguish different nodes in one struct. Default is opt::none + - \p cuckoo::probeset_type - probeset type. Defaul is \p cuckoo::list + - \p cuckoo::store_hash - store hash values in the node or not. Default is 0 (no storing) + - \p opt::tag - a \ref cds_intrusive_hook_tag "tag" */ - template - struct traits_hook: public hook< opt::traits_hook_tag, CDS_OPTIONS3 > + template + struct traits_hook: public hook< opt::traits_hook_tag, Options... > { //@cond typedef NodeTraits node_traits; @@ -378,7 +405,7 @@ namespace cds { namespace intrusive { }; //@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 @@ -386,15 +413,15 @@ namespace cds { namespace intrusive { { public: // placeholder ctor - lock_array(): lock_array_type( typename lock_array_type::select_cell_policy(2) ) {} + lock_array(): lock_array_type( typename lock_array_type::select_cell_policy(2)) {} // real ctor - lock_array( size_t nCapacity ): lock_array_type( nCapacity, typename lock_array_type::select_cell_policy(nCapacity) ) {} + lock_array( size_t nCapacity ): lock_array_type( nCapacity, typename lock_array_type::select_cell_policy(nCapacity)) {} }; - class scoped_lock: public cds::lock::scoped_lock< lock_array_type > + class scoped_lock: public std::unique_lock< lock_array_type > { - typedef cds::lock::scoped_lock< lock_array_type > base_class; + typedef std::unique_lock< lock_array_type > base_class; public: scoped_lock( lock_array& arrLock, size_t nHash ): base_class( arrLock, nHash ) {} }; @@ -402,7 +429,7 @@ namespace cds { namespace intrusive { 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 @@ -442,7 +469,7 @@ namespace cds { namespace intrusive { if ( m_bLocked ) { m_guard[0] = &(policy.m_Locks[0].at(nCell)); for ( unsigned int i = 1; i < c_nArity; ++i ) { - m_guard[i] = &( policy.m_Locks[i].at( policy.m_Locks[i].lock( arrHash[i] )) ); + m_guard[i] = &( policy.m_Locks[i].at( policy.m_Locks[i].lock( arrHash[i] ))); } } else { @@ -465,7 +492,7 @@ namespace cds { namespace intrusive { }; class scoped_full_lock { - cds::lock::scoped_lock< lock_array_type > m_guard; + std::unique_lock< lock_array_type > m_guard; public: scoped_full_lock( striping& policy ) : m_guard( policy.m_Locks[0] ) @@ -588,9 +615,9 @@ namespace cds { namespace intrusive { /// Refinable concurrent access policy /** - This is one of available opt::mutex_policy option type for CuckooSet + This is one of available \p opt::mutex_policy option type for \p CuckooSet - Refining is like a striping technique (see cuckoo::striping) + Refining is like a striping technique (see \p cuckoo::striping) but it allows growing the size of lock array when resizing the hash table. So, the sizes of hash table and lock array are equal. @@ -599,7 +626,7 @@ namespace cds { namespace intrusive { The default is \p std::recursive_mutex. The mutex type should be default-constructible. - \p Arity - unsigned int constant that specifies an arity. The arity is the count of hash functors, i.e., the count of lock arrays. Default value is 2. - - \p BackOff - back-off strategy. Default is cds::backoff::yield + - \p BackOff - back-off strategy. Default is \p cds::backoff::Default - \p Alloc - allocator type used for lock array memory allocation. Default is \p CDS_DEFAULT_ALLOCATOR. - \p Stat - internal statistics type. Note that this template argument is automatically selected by \ref CuckooSet class according to its \p opt::stat option. @@ -607,7 +634,7 @@ namespace cds { namespace intrusive { template < class RecursiveLock = std::recursive_mutex, unsigned int Arity = 2, - typename BackOff = cds::backoff::yield, + typename BackOff = cds::backoff::Default, class Alloc = CDS_DEFAULT_ALLOCATOR, class Stat = empty_refinable_stat > @@ -632,13 +659,13 @@ namespace cds { namespace intrusive { 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 ) @@ -650,8 +677,8 @@ namespace cds { namespace intrusive { typedef unsigned long long owner_t; typedef cds::OS::ThreadId threadId_t; - typedef cds::lock::Spin spinlock_type; - typedef cds::lock::scoped_lock< spinlock_type > scoped_spinlock; + typedef cds::sync::spin spinlock_type; + typedef std::unique_lock< spinlock_type > scoped_spinlock; //@endcond protected: @@ -660,9 +687,9 @@ namespace cds { namespace intrusive { atomics::atomic< owner_t > m_Owner ; ///< owner mark (thread id + boolean flag) atomics::atomic m_nCapacity ; ///< lock array capacity - lock_array_ptr m_arrLocks[ c_nArity ] ; ///< Lock array. The capacity of array is specified in constructor. - spinlock_type m_access ; ///< access to m_arrLocks - statistics_type m_Stat ; ///< internal statistics + lock_array_ptr m_arrLocks[ c_nArity ] ; ///< Lock array. The capacity of array is specified in constructor. + spinlock_type m_access ; ///< access to m_arrLocks + statistics_type m_Stat ; ///< internal statistics //@endcond protected: @@ -670,19 +697,25 @@ namespace cds { namespace intrusive { struct lock_array_disposer { void operator()( lock_array_type * pArr ) { + // Seems, there is a false positive in std::shared_ptr deallocation in uninstrumented libc++ + // see, for example, https://groups.google.com/forum/#!topic/thread-sanitizer/eHu4dE_z7Cc + // https://reviews.llvm.org/D21609 + CDS_TSAN_ANNOTATE_IGNORE_WRITES_BEGIN; lock_array_allocator().Delete( pArr ); + CDS_TSAN_ANNOTATE_IGNORE_WRITES_END; } }; lock_array_ptr create_lock_array( size_t nCapacity ) { - return lock_array_ptr( lock_array_allocator().New( nCapacity ), lock_array_disposer() ); + return lock_array_ptr( lock_array_allocator().New( nCapacity ), lock_array_disposer()); } void acquire( size_t const * arrHash, lock_array_ptr * pLockArr, lock_type ** parrLock ) { - owner_t me = (owner_t) cds::OS::getCurrentThreadId(); + owner_t me = (owner_t) cds::OS::get_current_thread_id(); owner_t who; + size_t cur_capacity; back_off bkoff; while ( true ) { @@ -691,21 +724,19 @@ namespace cds { namespace intrusive { scoped_spinlock sl(m_access); for ( unsigned int i = 0; i < c_nArity; ++i ) pLockArr[i] = m_arrLocks[i]; + cur_capacity = m_nCapacity.load( atomics::memory_order_acquire ); } // wait while resizing while ( true ) { who = m_Owner.load( atomics::memory_order_acquire ); - if ( !( who & 1 ) || (who >> 1) == (me & c_nOwnerMask) ) + if ( !( who & 1 ) || (who >> 1) == (me & c_nOwnerMask)) break; bkoff(); m_Stat.onCellWaitResizing(); } - if ( pLockArr[0] != m_arrLocks[0] ) { - m_Stat.onCellArrayChanged(); - } - else { + if ( cur_capacity == m_nCapacity.load( atomics::memory_order_acquire )) { size_t const nMask = pLockArr[0]->size() - 1; assert( cds::beans::is_power2( nMask + 1 )); @@ -716,22 +747,23 @@ namespace cds { namespace intrusive { } who = m_Owner.load( atomics::memory_order_acquire ); - if ( ( !(who & 1) || (who >> 1) == (me & c_nOwnerMask) ) && m_arrLocks[0] == pLockArr[0] ) { + if ( ( !(who & 1) || (who >> 1) == (me & c_nOwnerMask)) && cur_capacity == m_nCapacity.load( atomics::memory_order_acquire )) { m_Stat.onCellLock(); return; } - for ( unsigned int i = 0; i < c_nArity; ++i ) { + for ( unsigned int i = 0; i < c_nArity; ++i ) parrLock[i]->unlock(); - } m_Stat.onCellLockFailed(); } + else + m_Stat.onCellArrayChanged(); // clears pLockArr can lead to calling dtor for each item of pLockArr[i] that may be a heavy-weighted operation // (each pLockArr[i] is a shared pointer to array of a ton of mutexes) // It is better to do this before the next loop iteration where we will use spin-locked assignment to pLockArr - // Destructing a lot of mutexes under spin-lock is a bad solution + // However, destructing a lot of mutexes under spin-lock is a bad solution for ( unsigned int i = 0; i < c_nArity; ++i ) pLockArr[i].reset(); } @@ -751,7 +783,7 @@ namespace cds { namespace intrusive { parrLock[0] = &(m_arrLocks[0]->at(nCell)); for ( unsigned int i = 1; i < c_nArity; ++i ) { - parrLock[i] = &( m_arrLocks[i]->at( m_arrLocks[i]->lock( arrHash[i] & nMask)) ); + parrLock[i] = &( m_arrLocks[i]->at( m_arrLocks[i]->lock( arrHash[i] & nMask))); } m_Stat.onSecondCellLock(); @@ -760,7 +792,7 @@ namespace cds { namespace intrusive { void acquire_all() { - owner_t me = (owner_t) cds::OS::getCurrentThreadId(); + owner_t me = (owner_t) cds::OS::get_current_thread_id(); back_off bkoff; while ( true ) { @@ -784,27 +816,28 @@ namespace cds { namespace intrusive { void acquire_resize( lock_array_ptr * pOldLocks ) { - owner_t me = (owner_t) cds::OS::getCurrentThreadId(); + owner_t me = (owner_t) cds::OS::get_current_thread_id(); + size_t cur_capacity; while ( true ) { { scoped_spinlock sl(m_access); for ( unsigned int i = 0; i < c_nArity; ++i ) pOldLocks[i] = m_arrLocks[i]; + cur_capacity = m_nCapacity.load( atomics::memory_order_acquire ); } // global lock owner_t ownNull = 0; if ( m_Owner.compare_exchange_strong( ownNull, (me << 1) | 1, atomics::memory_order_acq_rel, atomics::memory_order_relaxed )) { - if ( pOldLocks[0] != m_arrLocks[0] ) { - m_Owner.store( 0, atomics::memory_order_release ); - m_Stat.onResizeLockArrayChanged(); - } - else { + if ( cur_capacity == m_nCapacity.load( atomics::memory_order_acquire )) { pOldLocks[0]->lock_all(); m_Stat.onResizeLock(); return; } + + m_Owner.store( 0, atomics::memory_order_release ); + m_Stat.onResizeLockArrayChanged(); } else m_Stat.onResizeLockIter(); @@ -812,7 +845,7 @@ namespace cds { namespace intrusive { // clears pOldLocks can lead to calling dtor for each item of pOldLocks[i] that may be a heavy-weighted operation // (each pOldLocks[i] is a shared pointer to array of a ton of mutexes) // It is better to do this before the next loop iteration where we will use spin-locked assignment to pOldLocks - // Destructing a lot of mutexes under spin-lock is a bad solution + // However, destructing a lot of mutexes under spin-lock is a bad solution for ( unsigned int i = 0; i < c_nArity; ++i ) pOldLocks[i].reset(); } @@ -918,24 +951,12 @@ namespace cds { namespace intrusive { 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); + m_nCapacity.store( nCapacity, atomics::memory_order_release ); for ( unsigned int i = 0; i < c_nArity; ++i ) m_arrLocks[i] = pNew[i]; } - m_nCapacity.store( nCapacity, atomics::memory_order_release ); m_Stat.onResize(); } @@ -963,48 +984,48 @@ namespace cds { namespace intrusive { } }; - /// 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; } @@ -1025,11 +1046,11 @@ namespace cds { namespace intrusive { 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; } @@ -1066,11 +1087,11 @@ namespace cds { namespace intrusive { 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 {} @@ -1087,7 +1108,7 @@ namespace cds { namespace intrusive { }; /// Type traits for CuckooSet class - struct type_traits + struct traits { /// Hook used /** @@ -1104,17 +1125,23 @@ namespace cds { namespace intrusive { The hash functors are defined as std::tuple< H1, H2, ... Hn > : \@code cds::opt::hash< std::tuple< h1, h2 > > \@endcode The number of hash functors specifies the number \p k - the count of hash tables in cuckoo hashing. - Up to 10 different hash functors are supported. + + To specify hash tuple in traits you should use \p cds::opt::hash_tuple: + \code + struct my_traits: public cds::intrusive::cuckoo::traits { + typedef cds::opt::hash_tuple< hash1, hash2 > hash; + }; + \endcode */ typedef cds::opt::none hash; /// Concurrent access policy /** Available opt::mutex_policy types: - - cuckoo::striping - simple, but the lock array is not resizable - - cuckoo::refinable - resizable lock array, but more complex access to set data. + - \p cuckoo::striping - simple, but the lock array is not resizable + - \p cuckoo::refinable - resizable lock array, but more complex access to set data. - Default is cuckoo::striping. + Default is \p cuckoo::striping. */ typedef cuckoo::striping<> mutex_policy; @@ -1124,7 +1151,7 @@ namespace cds { namespace intrusive { */ typedef opt::none equal_to; - /// Key comparison functor + /// Key comparing functor /** No default functor is provided. If the option is not specified, the \p less is used. */ @@ -1139,7 +1166,7 @@ namespace cds { namespace intrusive { /// Item counter /** The type for item counting feature. - Default is cds::atomicity::item_counter + Default is \p cds::atomicity::item_counter Only atomic item counter type is allowed. */ @@ -1153,25 +1180,54 @@ namespace cds { namespace intrusive { /// Disposer /** - The disposer functor is used in CuckooSet::clear member function + The disposer functor is used in \p CuckooSet::clear() member function to free set's node. */ typedef intrusive::opt::v::empty_disposer disposer; - /// Internal statistics. Available statistics: cuckoo::stat, cuckoo::empty_stat + /// Internal statistics. Available statistics: \p cuckoo::stat, \p cuckoo::empty_stat typedef empty_stat stat; }; - /// Metafunction converting option list to CuckooSet traits + /// Metafunction converting option list to \p CuckooSet traits /** - This is a wrapper for cds::opt::make_options< type_traits, Options...> - \p Options list see \ref CuckooSet. + Template argument list \p Options... are: + - \p intrusive::opt::hook - hook used. Possible values are: \p cuckoo::base_hook, \p cuckoo::member_hook, + \p cuckoo::traits_hook. + If the option is not specified, %cuckoo::base_hook<> is used. + - \p opt::hash - hash functor tuple, mandatory option. At least, two hash functors should be provided. All hash functor + should be orthogonal (different): for each i,j: i != j => h[i](x) != h[j](x) . + The hash functors are passed as std::tuple< H1, H2, ... Hn > . The number of hash functors specifies + the number \p k - the count of hash tables in cuckoo hashing. + - \p opt::mutex_policy - concurrent access policy. + Available policies: \p cuckoo::striping, \p cuckoo::refinable. + Default is \p %cuckoo::striping. + - \p opt::equal_to - key equality functor like \p std::equal_to. + If this functor is defined then the probe-set will be unordered. + If \p %opt::compare or \p %opt::less option is specified too, then the probe-set will be ordered + and \p %opt::equal_to will be ignored. + - \p opt::compare - key comparison functor. No default functor is provided. + If the option is not specified, the \p %opt::less is used. + If \p %opt::compare or \p %opt::less option is specified, then the probe-set will be ordered. + - \p opt::less - specifies binary predicate used for key comparison. Default is \p std::less. + If \p %opt::compare or \p %opt::less option is specified, then the probe-set will be ordered. + - \p opt::item_counter - the type of item counting feature. Default is \p atomicity::item_counter + The item counter should be atomic. + - \p opt::allocator - the allocator type using for allocating bucket tables. + Default is \ref CDS_DEFAULT_ALLOCATOR + - \p intrusive::opt::disposer - the disposer type used in \p clear() member function for + freeing nodes. Default is \p intrusive::opt::v::empty_disposer + - \p opt::stat - internal statistics. Possibly types: \p cuckoo::stat, \p cuckoo::empty_stat. + Default is \p %cuckoo::empty_stat + + The probe set traits \p cuckoo::probeset_type and \p cuckoo::store_hash are taken from \p node type + specified by \p opt::hook option. */ - template + template struct make_traits { typedef typename cds::opt::make_options< - typename cds::opt::find_type_traits< cuckoo::type_traits, CDS_OPTIONS10 >::type - ,CDS_OPTIONS11 + typename cds::opt::find_type_traits< cuckoo::traits, Options... >::type + ,Options... >::type type ; ///< Result of metafunction }; @@ -1285,7 +1341,7 @@ namespace cds { namespace intrusive { { node_type * pPrev = itPrev.pNode; node_type * pWhat = itWhat.pNode; - assert( (!pPrev && pWhat == pHead) || (pPrev && pPrev->m_pNext == pWhat) ); + assert( (!pPrev && pWhat == pHead) || (pPrev && pPrev->m_pNext == pWhat)); if ( pPrev ) pPrev->m_pNext = pWhat->m_pNext; @@ -1316,7 +1372,7 @@ namespace cds { namespace intrusive { for ( node_type * pNode = pHead; pNode; pNode = pNext ) { pNext = pNode->m_pNext; pNode->clear(); - cds::unref(disp)( pNode ); + disp( pNode ); } nSize = 0; @@ -1330,7 +1386,7 @@ namespace cds { namespace intrusive { }; template - class bucket_entry > + class bucket_entry> { public: typedef Node node_type; @@ -1347,22 +1403,14 @@ namespace cds { namespace intrusive { { 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 @@ -1439,8 +1487,8 @@ namespace cds { namespace intrusive { 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(it.pArr - m_arrNode) + 1 ); + it.pArr[1] = p; } else { shift_up(0); @@ -1465,7 +1513,7 @@ namespace cds { namespace intrusive { void clear( Disposer disp ) { for ( unsigned int i = 0; i < m_nSize; ++i ) { - cds::unref(disp)( m_arrNode[i] ); + disp( m_arrNode[i] ); } m_nSize = 0; } @@ -1480,7 +1528,7 @@ namespace cds { namespace intrusive { 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 ) { @@ -1505,7 +1553,7 @@ namespace cds { namespace intrusive { struct contains { template - static bool find( BucketEntry& probeset, Position& pos, unsigned int nTable, size_t nHash, Q const& val, Compare cmp ) + static bool find( BucketEntry& probeset, Position& pos, unsigned int /*nTable*/, size_t /*nHash*/, Q const& val, Compare cmp ) { // Ordered version typedef typename BucketEntry::iterator bucket_iterator; @@ -1571,8 +1619,8 @@ namespace cds { namespace intrusive { About Cuckoo hashing [From "The Art of Multiprocessor Programming"] - Cuckoo hashing 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 + Cuckoo hashing 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 of size N = 2k we use a two-entry array of tables, and two independent hash functions, h0, h1: KeyRange -> 0,...,k-1 mapping the set of possible keys to entries in he array. To test whether a value \p x is in the set, @@ -1609,56 +1657,24 @@ namespace cds { namespace intrusive { the average search complexity is O(PROBE_SET/2). 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. See cuckoo::type_traits for explanation. It is possible to declare option-based - set with cuckoo::make_traits metafunction result as \p Traits template argument. - - Template argument list \p Options... of cuckoo::make_traits metafunction are: - - intrusive::opt::hook - hook used. Possible values are: cuckoo::base_hook, cuckoo::member_hook, cuckoo::traits_hook. - If the option is not specified, %cuckoo::base_hook<> is used. - - opt::hash - hash functor tuple, mandatory option. At least, two hash functors should be provided. All hash functor - should be orthogonal (different): for each i,j: i != j => h[i](x) != h[j](x) . - The hash functors are passed as std::tuple< H1, H2, ... Hn > . The number of hash functors specifies - the number \p k - the count of hash tables in cuckoo hashing. If the compiler supports variadic templates - then k is unlimited, otherwise up to 10 different hash functors are supported. - - opt::mutex_policy - concurrent access policy. - Available policies: cuckoo::striping, cuckoo::refinable. - Default is cuckoo::striping. - - opt::equal_to - key equality functor like \p std::equal_to. - If this functor is defined then the probe-set will be unordered. - If opt::compare or opt::less option is specified too, then the probe-set will be ordered - and opt::equal_to will be ignored. - - opt::compare - key comparison functor. No default functor is provided. - If the option is not specified, the opt::less is used. - If opt::compare or opt::less option is specified, then the probe-set will be ordered. - - opt::less - specifies binary predicate used for key comparison. Default is \p std::less. - If opt::compare or opt::less option is specified, then the probe-set will be ordered. - - opt::item_counter - the type of item counting feature. Default is \ref atomicity::item_counter - The item counter should be atomic. - - opt::allocator - the allocator type using for allocating bucket tables. - Default is \p CDS_DEFAULT_ALLOCATOR - - intrusive::opt::disposer - the disposer type used in \ref clear() member function for - freeing nodes. Default is intrusive::opt::v::empty_disposer - - opt::stat - internal statistics. Possibly types: cuckoo::stat, cuckoo::empty_stat. - Default is cuckoo::empty_stat - - The probe set options cuckoo::probeset_type and cuckoo::store_hash are taken from \p node type - specified by \p opt::hook option. + - \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. How to use - You should incorporate cuckoo::node into your struct \p T and provide - appropriate cuckoo::type_traits::hook in your \p Traits template parameters. Usually, for \p Traits you - define a struct based on cuckoo::type_traits. + You should incorporate \p cuckoo::node into your struct \p T and provide + appropriate \p cuckoo::traits::hook in your \p Traits template parameters. + Usually, for \p Traits you define a struct based on \p cuckoo::traits. Example for base hook and list-based probe-set: \code @@ -1719,14 +1735,14 @@ namespace cds { namespace intrusive { }; // Declare type traits - struct my_traits: public cds::intrusive::cuckoo::type_traits + struct my_traits: public cds::intrusive::cuckoo::traits { typedef cds::intrusive::cuckoo::base_hook< cds::intrusive::cuckoo::probeset_type< my_data::probeset_type > ,cds::intrusive::cuckoo::store_hash< my_data::hash_array_size > > hook; typedef my_data_equa_to equal_to; - typedef std::tuple< hash1, hash2 > hash; + typedef cds::opt::hash_tuple< hash1, hash2 > hash; }; // Declare CuckooSet type @@ -1808,14 +1824,14 @@ namespace cds { namespace intrusive { }; // Declare type traits - struct my_traits: public cds::intrusive::cuckoo::type_traits + struct my_traits: public cds::intrusive::cuckoo::traits { typedef cds::intrusive::cuckoo::base_hook< cds::intrusive::cuckoo::probeset_type< my_data::probeset_type > ,cds::intrusive::cuckoo::store_hash< my_data::hash_array_size > > hook; typedef my_data_compare compare; - typedef std::tuple< hash1, hash2 > hash; + typedef cds::opt::hash_tuple< hash1, hash2 > hash; }; // Declare CuckooSet type @@ -1835,31 +1851,25 @@ namespace cds { namespace intrusive { \endcode */ - template + template class CuckooSet { public: - typedef T value_type ; ///< The value type stored in the set - typedef Traits options ; ///< Set traits + typedef T value_type; ///< The value type stored in the set + typedef Traits traits; ///< Set traits - typedef typename options::hook hook ; ///< hook type - typedef typename hook::node_type node_type ; ///< node type - typedef typename get_node_traits< value_type, node_type, hook>::type node_traits ; ///< node traits + typedef typename traits::hook hook; ///< hook type + typedef typename hook::node_type node_type; ///< node type + typedef typename get_node_traits< value_type, node_type, hook>::type node_traits; ///< node traits - typedef typename options::hash hash ; ///< hash functor tuple wrapped for internal use - typedef typename hash::hash_tuple_type hash_tuple_type ; ///< Type of hash tuple + typedef typename traits::hash hash; ///< hash functor tuple wrapped for internal use + typedef typename hash::hash_tuple_type hash_tuple_type; ///< Type of hash tuple - typedef typename options::stat stat ; ///< internal statistics type + typedef typename traits::stat stat; ///< internal statistics type - typedef typename options::mutex_policy original_mutex_policy ; ///< Concurrent access policy, see cuckoo::type_traits::mutex_policy + 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 cuckoo::type_traits::mutex_policy) - but mutex policy internal statistics is conformed with cukoo::type_traits::stat type provided by \p Traits: - - if \p %cuckoo::type_traits::stat is cuckoo::empty_stat then mutex policy statistics is already empty one - - 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 @@ -1867,25 +1877,31 @@ namespace cds { namespace intrusive { ,typename original_mutex_policy::real_stat >::type >::other mutex_policy; + //@endcond - static bool const c_isSorted = !( std::is_same< typename options::compare, opt::none >::value - && std::is_same< typename options::less, opt::none >::value ) ; ///< whether the probe set should be ordered + /// 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 ); 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, options, !c_isSorted>::type key_equal_to; + 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 - typedef typename opt::details::make_comparator< value_type, options >::type key_comparator; + /// 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 - typedef typename options::allocator allocator; + typedef typename traits::allocator allocator; /// item counter type - typedef typename options::item_counter item_counter; + typedef typename traits::item_counter item_counter; /// node disposer - typedef typename options::disposer disposer; + typedef typename traits::disposer disposer; protected: //@cond @@ -1904,48 +1920,12 @@ namespace cds { namespace intrusive { typedef size_t hash_array[c_nArity] ; ///< hash array -# 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 - void operator()( value_type& item, Q& val ) - {} - }; -# endif - -# if !defined(CDS_CXX11_LAMBDA_SUPPORT) || ((CDS_COMPILER == CDS_COMPILER_MSVC || CDS_COMPILER == CDS_COMPILER_INTEL ) && _MSC_VER == 1600) - template - class disposer_wrapper: protected cds::details::functor_wrapper - { - typedef cds::details::functor_wrapper base_class; - public: - disposer_wrapper( Disposer d): base_class(d) {} - - void operator()( node_type * pNode ) - { - base_class::get()( node_traits::to_value_ptr( pNode )); - } - }; -# endif - struct position { bucket_iterator itPrev; 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 struct predicate_wrapper { @@ -1956,16 +1936,16 @@ namespace cds { namespace intrusive { //@endcond public: - static unsigned int const c_nDefaultProbesetSize = 4 ; ///< default probeset size - static size_t const c_nDefaultInitialSize = 16 ; ///< default initial size - static unsigned int const c_nRelocateLimit = c_nArity * 2 - 1 ; ///< Count of attempts to relocate before giving up + static unsigned int const c_nDefaultProbesetSize = 4; ///< default probeset size + static size_t const c_nDefaultInitialSize = 16; ///< default initial size + static unsigned int const c_nRelocateLimit = c_nArity * 2 - 1; ///< Count of attempts to relocate before giving up protected: bucket_entry * m_BucketTable[ c_nArity ] ; ///< Bucket tables - size_t m_nBucketMask ; ///< Hash bitmask; bucket table size minus 1. - unsigned int const m_nProbesetSize ; ///< Probe set size - unsigned int const m_nProbesetThreshold ; ///< Probe set threshold + atomics::atomic m_nBucketMask ; ///< Hash bitmask; bucket table size minus 1. + unsigned int const m_nProbesetSize ; ///< Probe set size + unsigned int const m_nProbesetThreshold ; ///< Probe set threshold hash m_Hash ; ///< Hash functor tuple mutex_policy m_MutexPolicy ; ///< concurrent access policy @@ -2004,13 +1984,12 @@ namespace cds { namespace intrusive { bucket_entry& bucket( unsigned int nTable, size_t nHash ) { assert( nTable < c_nArity ); - return m_BucketTable[nTable][nHash & m_nBucketMask]; + return m_BucketTable[nTable][nHash & m_nBucketMask.load( atomics::memory_order_relaxed ) ]; } 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 ) @@ -2020,9 +1999,9 @@ namespace cds { namespace intrusive { void allocate_bucket_tables( size_t nSize ) { - assert( cds::beans::is_power2( nSize ) ); + assert( cds::beans::is_power2( nSize )); - m_nBucketMask = nSize - 1; + m_nBucketMask.store( nSize - 1, atomics::memory_order_release ); bucket_table_allocator alloc; for ( unsigned int i = 0; i < c_nArity; ++i ) m_BucketTable[i] = alloc.NewArray( nSize ); @@ -2038,10 +2017,10 @@ namespace cds { namespace intrusive { } void free_bucket_tables() { - free_bucket_tables( m_BucketTable, m_nBucketMask + 1 ); + free_bucket_tables( m_BucketTable, m_nBucketMask.load( atomics::memory_order_relaxed ) + 1 ); } - static unsigned int const c_nUndefTable = (unsigned int) -1; + static CDS_CONSTEXPR unsigned int const c_nUndefTable = (unsigned int) -1; template unsigned int contains( position * arrPos, size_t * arrHash, Q const& val, Predicate pred ) { @@ -2068,7 +2047,7 @@ namespace cds { namespace intrusive { unsigned int nTable = contains( arrPos, arrHash, val, pred ); if ( nTable != c_nUndefTable ) { node_type& node = *arrPos[nTable].itFound; - cds::unref(f)( *node_traits::to_value_ptr(node) ); + f( *node_traits::to_value_ptr(node)); bucket( nTable, arrHash[nTable]).remove( arrPos[nTable].itPrev, arrPos[nTable].itFound ); --m_ItemCounter; m_Stat.onEraseSuccess(); @@ -2090,7 +2069,7 @@ namespace cds { namespace intrusive { unsigned int nTable = contains( arrPos, arrHash, val, pred ); if ( nTable != c_nUndefTable ) { - cds::unref(f)( *node_traits::to_value_ptr( *arrPos[nTable].itFound ), val ); + f( *node_traits::to_value_ptr( *arrPos[nTable].itFound ), val ); m_Stat.onFindSuccess(); return true; } @@ -2121,14 +2100,14 @@ namespace cds { namespace intrusive { return true; } - pVal = node_traits::to_value_ptr( *refBucket.begin() ); + pVal = node_traits::to_value_ptr( *refBucket.begin()); copy_hash( arrHash, *pVal ); scoped_cell_trylock guard2( m_MutexPolicy, arrHash ); - if ( !guard2.locked() ) + if ( !guard2.locked()) continue ; // try one more time - refBucket.remove( typename bucket_entry::iterator(), refBucket.begin() ); + refBucket.remove( typename bucket_entry::iterator(), refBucket.begin()); unsigned int i = (nTable + 1) % c_nArity; @@ -2137,7 +2116,7 @@ namespace cds { namespace intrusive { bucket_entry& bkt = bucket( i, arrHash[i] ); if ( bkt.size() < m_nProbesetThreshold ) { position pos; - contains_action::find( bkt, pos, i, arrHash[i], *pVal, key_predicate() ) ; // must return false! + contains_action::find( bkt, pos, i, arrHash[i], *pVal, key_predicate()) ; // must return false! bkt.insert_after( pos.itPrev, node_traits::to_node_ptr( pVal )); m_Stat.onSuccessRelocateRound(); return true; @@ -2151,7 +2130,7 @@ namespace cds { namespace intrusive { bucket_entry& bkt = bucket( i, arrHash[i] ); if ( bkt.size() < m_nProbesetSize ) { position pos; - contains_action::find( bkt, pos, i, arrHash[i], *pVal, key_predicate() ) ; // must return false! + contains_action::find( bkt, pos, i, arrHash[i], *pVal, key_predicate()) ; // must return false! bkt.insert_after( pos.itPrev, node_traits::to_node_ptr( pVal )); nTable = i; memcpy( arrGoalHash, arrHash, sizeof(arrHash)); @@ -2176,12 +2155,12 @@ namespace cds { namespace intrusive { { m_Stat.onResizeCall(); - size_t nOldCapacity = bucket_count(); + size_t nOldCapacity = bucket_count( atomics::memory_order_acquire ); bucket_entry * pOldTable[ c_nArity ]; { scoped_resize_lock guard( m_MutexPolicy ); - if ( nOldCapacity != bucket_count() ) { + if ( nOldCapacity != bucket_count()) { m_Stat.onFalseResizeCall(); return; } @@ -2192,7 +2171,6 @@ namespace cds { namespace intrusive { memcpy( pOldTable, m_BucketTable, sizeof(pOldTable)); allocate_bucket_tables( nCapacity ); - typedef typename bucket_entry::iterator bucket_iterator; hash_array arrHash; position arrPos[ c_nArity ]; @@ -2206,7 +2184,7 @@ namespace cds { namespace intrusive { value_type& val = *node_traits::to_value_ptr( *it ); copy_hash( arrHash, val ); - contains( arrPos, arrHash, val, key_predicate() ) ; // must return c_nUndefTable + CDS_VERIFY_EQ( contains( arrPos, arrHash, val, key_predicate()), c_nUndefTable ); for ( unsigned int i = 0; i < c_nArity; ++i ) { bucket_entry& refBucket = bucket( i, arrHash[i] ); @@ -2222,7 +2200,7 @@ namespace cds { namespace intrusive { if ( refBucket.size() < m_nProbesetSize ) { refBucket.insert_after( arrPos[i].itPrev, &*it ); assert( refBucket.size() > 1 ); - copy_hash( arrHash, *node_traits::to_value_ptr( *refBucket.begin()) ); + copy_hash( arrHash, *node_traits::to_value_ptr( *refBucket.begin())); m_Stat.onResizeRelocateCall(); relocate( i, arrHash ); break; @@ -2238,10 +2216,11 @@ namespace cds { namespace intrusive { 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 @@ -2257,7 +2236,7 @@ namespace cds { namespace intrusive { Probe set threshold = probe set size - 1 */ CuckooSet() - : m_nProbesetSize( calc_probeset_size(0) ) + : m_nProbesetSize( calc_probeset_size(0)) , m_nProbesetThreshold( m_nProbesetSize - 1 ) , m_MutexPolicy( c_nDefaultInitialSize ) { @@ -2270,14 +2249,14 @@ namespace cds { namespace intrusive { /// Constructs the set object with given probe set size and threshold /** If probe set type is cuckoo::vector 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, nProbesetThreshold < nProbesetSize. If 0, nProbesetThreshold = nProbesetSize - 1 + , unsigned int nProbesetThreshold = 0 ///< probe set threshold, nProbesetThreshold < nProbesetSize. If 0, nProbesetThreshold = nProbesetSize - 1 ) - : m_nProbesetSize( calc_probeset_size(nProbesetSize) ) + : m_nProbesetSize( calc_probeset_size(nProbesetSize)) , m_nProbesetThreshold( nProbesetThreshold ? nProbesetThreshold : m_nProbesetSize - 1 ) , m_MutexPolicy( cds::beans::ceil2(nInitialSize ? nInitialSize : c_nDefaultInitialSize )) { @@ -2289,12 +2268,12 @@ namespace cds { namespace intrusive { /// 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 std::tuple where n == \ref c_nArity ) - : m_nProbesetSize( calc_probeset_size(0) ) + : m_nProbesetSize( calc_probeset_size(0)) , m_nProbesetThreshold( m_nProbesetSize -1 ) , m_Hash( h ) , m_MutexPolicy( c_nDefaultInitialSize ) @@ -2311,12 +2290,12 @@ namespace cds { namespace intrusive { 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, nProbesetThreshold < nProbesetSize. If 0, nProbesetThreshold = nProbesetSize - 1 + , unsigned int nProbesetThreshold ///< probe set threshold, nProbesetThreshold < nProbesetSize. If 0, nProbesetThreshold = nProbesetSize - 1 , hash_tuple_type const& h ///< hash functor tuple of type std::tuple where n == \ref c_nArity ) - : m_nProbesetSize( calc_probeset_size(nProbesetSize) ) + : m_nProbesetSize( calc_probeset_size(nProbesetSize)) , m_nProbesetThreshold( nProbesetThreshold ? nProbesetThreshold : m_nProbesetSize - 1) , m_Hash( h ) , m_MutexPolicy( cds::beans::ceil2(nInitialSize ? nInitialSize : c_nDefaultInitialSize )) @@ -2327,17 +2306,16 @@ namespace cds { namespace intrusive { allocate_bucket_tables( nInitialSize ? cds::beans::ceil2( nInitialSize ) : c_nDefaultInitialSize ); } -# ifdef CDS_MOVE_SEMANTICS_SUPPORT /// 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 std::tuple where n == \ref c_nArity ) - : m_nProbesetSize( calc_probeset_size(0) ) + : m_nProbesetSize( calc_probeset_size(0)) , m_nProbesetThreshold( m_nProbesetSize / 2 ) - , m_Hash( std::forward(h) ) + , m_Hash( std::forward(h)) , m_MutexPolicy( c_nDefaultInitialSize ) { check_common_constraints(); @@ -2352,14 +2330,14 @@ namespace cds { namespace intrusive { 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, nProbesetThreshold < nProbesetSize. If 0, nProbesetThreshold = nProbesetSize - 1 + , unsigned int nProbesetThreshold ///< probe set threshold, nProbesetThreshold < nProbesetSize. If 0, nProbesetThreshold = nProbesetSize - 1 , hash_tuple_type&& h ///< hash functor tuple of type std::tuple where n == \ref c_nArity ) - : m_nProbesetSize( calc_probeset_size(nProbesetSize) ) + : m_nProbesetSize( calc_probeset_size(nProbesetSize)) , m_nProbesetThreshold( nProbesetThreshold ? nProbesetThreshold : m_nProbesetSize - 1) - , m_Hash( std::forward(h) ) + , m_Hash( std::forward(h)) , m_MutexPolicy( cds::beans::ceil2(nInitialSize ? nInitialSize : c_nDefaultInitialSize )) { check_common_constraints(); @@ -2367,7 +2345,6 @@ namespace cds { namespace intrusive { allocate_bucket_tables( nInitialSize ? cds::beans::ceil2( nInitialSize ) : c_nDefaultInitialSize ); } -# endif // ifdef CDS_MOVE_SEMANTICS_SUPPORT /// Destructor ~CuckooSet() @@ -2378,18 +2355,13 @@ namespace cds { namespace intrusive { 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 ) { -# ifdef CDS_CXX11_LAMBDA_SUPPORT return insert( val, []( value_type& ) {} ); -# else - return insert( val, empty_insert_functor() ); -# endif } /// Inserts new node @@ -2405,8 +2377,7 @@ namespace cds { namespace intrusive { \endcode where \p val is the item inserted. - The user-defined functor is called only if the inserting is success and can be passed by reference - using boost::ref + The user-defined functor is called only if the inserting is success. */ template bool insert( value_type& val, Func f ) @@ -2423,7 +2394,7 @@ namespace cds { namespace intrusive { { scoped_cell_lock guard( m_MutexPolicy, arrHash ); - if ( contains( arrPos, arrHash, val, key_predicate() ) != c_nUndefTable ) { + if ( contains( arrPos, arrHash, val, key_predicate()) != c_nUndefTable ) { m_Stat.onInsertFailed(); return false; } @@ -2432,7 +2403,7 @@ namespace cds { namespace intrusive { bucket_entry& refBucket = bucket( i, arrHash[i] ); if ( refBucket.size() < m_nProbesetThreshold ) { refBucket.insert_after( arrPos[i].itPrev, pNode ); - cds::unref(f)( val ); + f( val ); ++m_ItemCounter; m_Stat.onInsertSuccess(); return true; @@ -2443,11 +2414,11 @@ namespace cds { namespace intrusive { bucket_entry& refBucket = bucket( i, arrHash[i] ); if ( refBucket.size() < m_nProbesetSize ) { refBucket.insert_after( arrPos[i].itPrev, pNode ); - cds::unref(f)( val ); + f( val ); ++m_ItemCounter; nGoalTable = i; assert( refBucket.size() > 1 ); - copy_hash( arrHash, *node_traits::to_value_ptr( *refBucket.begin()) ); + copy_hash( arrHash, *node_traits::to_value_ptr( *refBucket.begin())); goto do_relocate; } } @@ -2469,33 +2440,33 @@ namespace cds { namespace intrusive { 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. - You may pass \p func argument by reference using boost::ref or cds::ref. - - Returns std::pair where \p first is \p true if operation is successful, + Returns std::pair 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 - std::pair ensure( value_type& val, Func func ) + std::pair update( value_type& val, Func func, bool bAllowInsert = true ) { hash_array arrHash; position arrPos[ c_nArity ]; @@ -2509,23 +2480,26 @@ namespace cds { namespace intrusive { { scoped_cell_lock guard( m_MutexPolicy, arrHash ); - unsigned int nTable = contains( arrPos, arrHash, val, key_predicate() ); + unsigned int nTable = contains( arrPos, arrHash, val, key_predicate()); if ( nTable != c_nUndefTable ) { - cds::unref(func)( false, *node_traits::to_value_ptr( *arrPos[nTable].itFound ), val ); - m_Stat.onEnsureExist(); + func( false, *node_traits::to_value_ptr( *arrPos[nTable].itFound ), val ); + 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] ); if ( refBucket.size() < m_nProbesetThreshold ) { refBucket.insert_after( arrPos[i].itPrev, pNode ); - cds::unref(func)( true, val, val ); + func( true, val, val ); ++m_ItemCounter; - m_Stat.onEnsureSuccess(); + m_Stat.onUpdateSuccess(); return std::make_pair( true, true ); } } @@ -2534,31 +2508,39 @@ namespace cds { namespace intrusive { bucket_entry& refBucket = bucket( i, arrHash[i] ); if ( refBucket.size() < m_nProbesetSize ) { refBucket.insert_after( arrPos[i].itPrev, pNode ); - cds::unref(func)( true, val, val ); + func( true, val, val ); ++m_ItemCounter; nGoalTable = i; assert( refBucket.size() > 1 ); - copy_hash( arrHash, *node_traits::to_value_ptr( *refBucket.begin()) ); + copy_hash( arrHash, *node_traits::to_value_ptr( *refBucket.begin())); goto do_relocate; } } } - 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 + CDS_DEPRECATED("ensure() is deprecated, use update()") + std::pair ensure( value_type& val, Func func ) + { + return update( val, func, true ); + } + //@endcond /// Unlink the item \p val from the set /** @@ -2578,7 +2560,7 @@ namespace cds { namespace intrusive { { scoped_cell_lock guard( m_MutexPolicy, arrHash ); - unsigned int nTable = contains( arrPos, arrHash, val, key_predicate() ); + unsigned int nTable = contains( arrPos, arrHash, val, key_predicate()); if ( nTable != c_nUndefTable && node_traits::to_value_ptr(*arrPos[nTable].itFound) == &val ) { bucket( nTable, arrHash[nTable]).remove( arrPos[nTable].itPrev, arrPos[nTable].itFound ); --m_ItemCounter; @@ -2603,11 +2585,7 @@ namespace cds { namespace intrusive { template value_type * erase( Q const& val ) { -# ifdef CDS_CXX11_LAMBDA_SUPPORT return erase( val, [](value_type const&) {} ); -# else - return erase( val, empty_erase_functor() ); -# endif } /// Deletes the item from the set using \p pred predicate for searching @@ -2621,11 +2599,8 @@ namespace cds { namespace intrusive { template value_type * erase_with( Q const& val, Predicate pred ) { -# ifdef CDS_CXX11_LAMBDA_SUPPORT + CDS_UNUSED( pred ); return erase_( val, typename predicate_wrapper::type(), [](value_type const&) {} ); -# else - return erase_( val, typename predicate_wrapper::type(), empty_erase_functor() ); -# endif } /// Delete the item from the set @@ -2639,7 +2614,6 @@ namespace cds { namespace intrusive { void operator()( value_type const& item ); }; \endcode - The functor may be passed by reference with boost:ref If the item with key equal to \p val is not found the function return \p nullptr. @@ -2662,6 +2636,7 @@ namespace cds { namespace intrusive { template value_type * erase_with( Q const& val, Predicate pred, Func f ) { + CDS_UNUSED( pred ); return erase_( val, typename predicate_wrapper::type(), f ); } @@ -2676,8 +2651,6 @@ namespace cds { namespace intrusive { \endcode where \p item is the item found, \p val is the find function argument. - You can pass \p f argument by reference using boost::ref or cds::ref. - 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 @@ -2693,6 +2666,13 @@ namespace cds { namespace intrusive { { return find_( val, key_predicate(), f ); } + //@cond + template + 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 /** @@ -2705,98 +2685,72 @@ namespace cds { namespace intrusive { template bool find_with( Q& val, Predicate pred, Func f ) { + CDS_UNUSED( pred ); return find_( val, typename predicate_wrapper::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 find function argument. - - You can pass \p f argument by reference using boost::ref or cds::ref. - - 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 - 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 bool find_with( Q const& val, Predicate pred, Func f ) { + CDS_UNUSED( pred ); return find_( val, typename predicate_wrapper::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 - bool find( Q const& val ) + bool contains( Q const& key ) + { + return find( key, [](value_type&, Q const& ) {} ); + } + //@cond + template + CDS_DEPRECATED("deprecated, use contains()") + bool find( Q const& key ) { -# ifdef CDS_CXX11_LAMBDA_SUPPORT - return find( val, [](value_type&, Q const& ) {} ); -# else - return find( val, empty_find_functor() ); -# endif + 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 contains( key ) 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 - bool find_with( Q const& val, Predicate pred ) + bool contains( Q const& key, Predicate pred ) + { + CDS_UNUSED( pred ); + return find_with( key, typename predicate_wrapper::type(), [](value_type& , Q const& ) {} ); + } + //@cond + template + CDS_DEPRECATED("deprecated, use contains()") + bool find_with( Q const& key, Predicate pred ) { -# ifdef CDS_CXX11_LAMBDA_SUPPORT - return find_with( val, typename predicate_wrapper::type(), [](value_type& , Q const& ) {} ); -# else - return find_with( val, typename predicate_wrapper::type(), empty_find_functor() ); -# endif + 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 \p Traits::disposer is called */ void clear() { - clear_and_dispose( disposer() ); + clear_and_dispose( disposer()); } /// 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{ @@ -2804,7 +2758,7 @@ namespace cds { namespace intrusive { }; \endcode - The \ref disposer specified in \p Traits options is not called. + The \p Traits::disposer is not called. */ template void clear_and_dispose( Disposer oDisposer ) @@ -2812,19 +2766,11 @@ namespace cds { namespace intrusive { // locks entire array scoped_full_lock sl( m_MutexPolicy ); -# if !defined(CDS_CXX11_LAMBDA_SUPPORT) || ((CDS_COMPILER == CDS_COMPILER_MSVC || CDS_COMPILER == CDS_COMPILER_INTEL ) && _MSC_VER == 1600) - disposer_wrapper disp( oDisposer ); -# endif for ( unsigned int i = 0; i < c_nArity; ++i ) { bucket_entry * pEntry = m_BucketTable[i]; - bucket_entry * pEnd = pEntry + m_nBucketMask + 1; + bucket_entry * pEnd = pEntry + m_nBucketMask.load( atomics::memory_order_relaxed ) + 1; for ( ; pEntry != pEnd ; ++pEntry ) { -# if defined(CDS_CXX11_LAMBDA_SUPPORT) && !((CDS_COMPILER == CDS_COMPILER_MSVC || CDS_COMPILER == CDS_COMPILER_INTEL) && _MSC_VER == 1600) - // MSVC 10: error to call nested typedefs node_traits from lambda pEntry->clear( [&oDisposer]( node_type * pNode ){ oDisposer( node_traits::to_value_ptr( pNode )) ; } ); -# else - pEntry->clear( cds::ref(disp) ); -# endif } } m_ItemCounter.reset(); @@ -2851,8 +2797,14 @@ namespace cds { namespace intrusive { */ size_t bucket_count() const { - return m_nBucketMask + 1; + return m_nBucketMask.load( atomics::memory_order_relaxed ) + 1; } + //@cond + size_t bucket_count( atomics::memory_order load_mo ) const + { + return m_nBucketMask.load( load_mo ) + 1; + } + //@endcond /// Returns lock array size size_t lock_count() const @@ -2874,4 +2826,4 @@ namespace cds { namespace intrusive { }; }} // namespace cds::intrusive -#endif // #ifndef __CDS_INTRUSIVE_CUCKOO_SET_H +#endif // #ifndef CDSLIB_INTRUSIVE_CUCKOO_SET_H