X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=cds%2Fintrusive%2Fcuckoo_set.h;h=9508c24ae861125e95c812d87663d10fcbccd293;hb=7dfac7ccae1aa24f28655e3380293dc1f67ea7b2;hp=0fc53d7bc4d6366e891368f60c05d7d03fd925cd;hpb=36347e82740e7f7c35d198b20b470a85216a4264;p=libcds.git diff --git a/cds/intrusive/cuckoo_set.h b/cds/intrusive/cuckoo_set.h index 0fc53d7b..9508c24a 100644 --- a/cds/intrusive/cuckoo_set.h +++ b/cds/intrusive/cuckoo_set.h @@ -1,4 +1,32 @@ -//$$CDS-header$$ +/* + This file is a part of libcds - Concurrent Data Structures library + + (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 @@ -19,7 +47,6 @@ namespace cds { namespace intrusive { /// CuckooSet-related definitions namespace cuckoo { - /// Option to define probeset type /** The option specifies probeset type for the CuckooSet. @@ -76,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 /** @@ -169,7 +199,6 @@ namespace cds { namespace intrusive { { m_pNext = nullptr; } - }; template @@ -384,10 +413,10 @@ 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 std::unique_lock< lock_array_type > @@ -400,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 @@ -440,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 { @@ -586,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. @@ -597,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. @@ -605,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 > @@ -658,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: @@ -668,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::get_current_thread_id(); owner_t who; + size_t cur_capacity; back_off bkoff; while ( true ) { @@ -689,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 )); @@ -714,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(); } @@ -749,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(); @@ -783,26 +817,27 @@ namespace cds { namespace intrusive { void acquire_resize( lock_array_ptr * pOldLocks ) { 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(); @@ -810,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(); } @@ -916,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(); } @@ -961,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; } @@ -1023,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; } @@ -1064,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 {} @@ -1318,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; @@ -1363,7 +1386,7 @@ namespace cds { namespace intrusive { }; template - class bucket_entry > + class bucket_entry> { public: typedef Node node_type; @@ -1380,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 @@ -1472,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); @@ -1513,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 ) { @@ -1604,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, @@ -1642,17 +1657,17 @@ 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, 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. How to use @@ -1854,13 +1869,7 @@ namespace cds { namespace intrusive { 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 @@ -1868,15 +1877,21 @@ namespace cds { namespace intrusive { ,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 @@ -1910,10 +1925,7 @@ namespace cds { namespace intrusive { 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 { @@ -1931,9 +1943,9 @@ namespace cds { namespace intrusive { 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 @@ -1972,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 ) @@ -1988,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 ); @@ -2006,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 ) { @@ -2036,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; - 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(); @@ -2089,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; @@ -2105,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; @@ -2119,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)); @@ -2144,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; } @@ -2160,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 ]; @@ -2174,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 + contains( arrPos, arrHash, val, key_predicate()) ; // must return c_nUndefTable for ( unsigned int i = 0; i < c_nArity; ++i ) { bucket_entry& refBucket = bucket( i, arrHash[i] ); @@ -2190,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; @@ -2206,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 @@ -2225,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 ) { @@ -2238,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 )) { @@ -2257,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 ) @@ -2279,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 )) @@ -2297,14 +2308,14 @@ namespace cds { namespace intrusive { /// 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(); @@ -2319,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(); @@ -2344,10 +2355,9 @@ 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 ) { @@ -2384,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; } @@ -2408,7 +2418,7 @@ namespace cds { namespace intrusive { ++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; } } @@ -2430,31 +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. - 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 ]; @@ -2468,15 +2480,18 @@ 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 ) { 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] ); @@ -2484,7 +2499,7 @@ namespace cds { namespace intrusive { 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 ); } } @@ -2497,27 +2512,35 @@ namespace cds { namespace intrusive { ++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 /** @@ -2537,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; @@ -2643,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 /** @@ -2658,88 +2688,69 @@ namespace cds { namespace intrusive { 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. - - 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( val, [](value_type&, Q const& ) {} ); + return find( key, [](value_type&, Q const& ) {} ); } + //@cond + template + CDS_DEPRECATED("deprecated, use contains()") + bool find( Q const& key ) + { + 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( val, typename predicate_wrapper::type(), [](value_type& , Q const& ) {} ); + 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 ) + { + 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{ @@ -2747,7 +2758,7 @@ namespace cds { namespace intrusive { }; \endcode - The \ref disposer specified in \p Traits traits is not called. + The \p Traits::disposer is not called. */ template void clear_and_dispose( Disposer oDisposer ) @@ -2757,7 +2768,7 @@ namespace cds { namespace intrusive { 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 ) { pEntry->clear( [&oDisposer]( node_type * pNode ){ oDisposer( node_traits::to_value_ptr( pNode )) ; } ); } @@ -2786,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