2 This file is a part of libcds - Concurrent Data Structures library
4 (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016
6 Source code repo: http://github.com/khizmax/libcds/
7 Download: http://sourceforge.net/projects/libcds/files/
9 Redistribution and use in source and binary forms, with or without
10 modification, are permitted provided that the following conditions are met:
12 * Redistributions of source code must retain the above copyright notice, this
13 list of conditions and the following disclaimer.
15 * Redistributions in binary form must reproduce the above copyright notice,
16 this list of conditions and the following disclaimer in the documentation
17 and/or other materials provided with the distribution.
19 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
20 AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
21 IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
22 DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
23 FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
24 DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
25 SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
26 CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
27 OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
28 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
31 #ifndef CDSLIB_INTRUSIVE_CUCKOO_SET_H
32 #define CDSLIB_INTRUSIVE_CUCKOO_SET_H
35 #include <type_traits>
37 #include <functional> // ref
38 #include <cds/intrusive/details/base.h>
39 #include <cds/opt/compare.h>
40 #include <cds/opt/hash.h>
41 #include <cds/sync/lock_array.h>
42 #include <cds/os/thread.h>
43 #include <cds/sync/spinlock.h>
46 namespace cds { namespace intrusive {
48 /// CuckooSet-related definitions
50 /// Option to define probeset type
52 The option specifies probeset type for the CuckooSet.
54 - \p cds::intrusive::cuckoo::list - the probeset is a single-linked list.
55 The node contains pointer to next node in probeset.
56 - \p cds::intrusive::cuckoo::vector<Capacity> - the probeset is a vector
57 with constant-size \p Capacity where \p Capacity is an <tt>unsigned int</tt> constant.
58 The node does not contain any auxiliary data.
60 template <typename Type>
64 template <typename Base>
65 struct pack: public Base {
66 typedef Type probeset_type;
71 /// Option specifying whether to store hash values in the node
73 This option reserves additional space in the hook to store the hash value of the object once it's introduced in the container.
74 When this option is used, the unordered container will store the calculated hash value in the hook and rehashing operations won't need
75 to recalculate the hash of the value. This option will improve the performance of unordered containers
76 when rehashing is frequent or hashing the value is a slow operation
78 The \p Count template parameter defines the size of hash array. Remember that cuckoo hashing implies at least two
81 Possible values of \p Count:
82 - 0 - no hash storing in the node
83 - greater that 1 - store hash values.
85 Value 1 is deprecated.
87 template <unsigned int Count>
91 template <typename Base>
92 struct pack: public Base {
93 static unsigned int const store_hash = Count;
100 // Probeset type placeholders
101 struct list_probeset_class;
102 struct vector_probeset_class;
106 /// List probeset type
110 /// Vector probeset type
111 template <unsigned int Capacity>
115 static unsigned int const c_nCapacity = Capacity;
121 - \p ProbesetType - type of probeset. Can be \p cds::intrusive::cuckoo::list
122 or \p cds::intrusive::cuckoo::vector<Capacity>.
123 - \p StoreHashCount - constant that defines whether to store node hash values.
124 See cuckoo::store_hash option for explanation
125 - \p Tag - a \ref cds_intrusive_hook_tag "tag"
127 template <typename ProbesetType = cuckoo::list, unsigned int StoreHashCount = 0, typename Tag = opt::none>
129 #ifdef CDS_DOXYGEN_INVOKED
131 typedef ProbesetType probeset_type ; ///< Probeset type
132 typedef Tag tag ; ///< Tag
133 static unsigned int const hash_array_size = StoreHashCount ; ///< The size of hash array
139 template <typename Tag>
140 struct node< cuckoo::list, 0, Tag>
142 typedef list_probeset_class probeset_class;
143 typedef cuckoo::list probeset_type;
145 static unsigned int const hash_array_size = 0;
146 static unsigned int const probeset_size = 0;
150 CDS_CONSTEXPR node() CDS_NOEXCEPT
154 void store_hash( size_t * )
157 size_t * get_hash() const
159 // This node type does not store hash values!!!
170 template <unsigned int StoreHashCount, typename Tag>
171 struct node< cuckoo::list, StoreHashCount, Tag>
173 typedef list_probeset_class probeset_class;
174 typedef cuckoo::list probeset_type;
176 static unsigned int const hash_array_size = StoreHashCount;
177 static unsigned int const probeset_size = 0;
180 size_t m_arrHash[ hash_array_size ];
185 memset( m_arrHash, 0, sizeof(m_arrHash));
188 void store_hash( size_t * pHashes )
190 memcpy( m_arrHash, pHashes, hash_array_size );
193 size_t * get_hash() const
195 return const_cast<size_t *>( m_arrHash );
204 template <unsigned int VectorSize, typename Tag>
205 struct node< cuckoo::vector<VectorSize>, 0, Tag>
207 typedef vector_probeset_class probeset_class;
208 typedef cuckoo::vector<VectorSize> probeset_type;
210 static unsigned int const hash_array_size = 0;
211 static unsigned int const probeset_size = probeset_type::c_nCapacity;
216 void store_hash( size_t * )
219 size_t * get_hash() const
221 // This node type does not store hash values!!!
230 template <unsigned int VectorSize, unsigned int StoreHashCount, typename Tag>
231 struct node< cuckoo::vector<VectorSize>, StoreHashCount, Tag>
233 typedef vector_probeset_class probeset_class;
234 typedef cuckoo::vector<VectorSize> probeset_type;
236 static unsigned int const hash_array_size = StoreHashCount;
237 static unsigned int const probeset_size = probeset_type::c_nCapacity;
239 size_t m_arrHash[ hash_array_size ];
243 memset( m_arrHash, 0, sizeof(m_arrHash));
246 void store_hash( size_t * pHashes )
248 memcpy( m_arrHash, pHashes, hash_array_size );
251 size_t * get_hash() const
253 return const_cast<size_t *>( m_arrHash );
263 struct default_hook {
264 typedef cuckoo::list probeset_type;
265 static unsigned int const store_hash = 0;
266 typedef opt::none tag;
269 template < typename HookType, typename... Options>
272 typedef typename opt::make_options< default_hook, Options...>::type traits;
274 typedef typename traits::probeset_type probeset_type;
275 typedef typename traits::tag tag;
276 static unsigned int const store_hash = traits::store_hash;
278 typedef node<probeset_type, store_hash, tag> node_type;
280 typedef HookType hook_type;
287 - \p cuckoo::probeset_type - probeset type. Defaul is \p cuckoo::list
288 - \p cuckoo::store_hash - store hash values in the node or not. Default is 0 (no storing)
289 - \p opt::tag - a \ref cds_intrusive_hook_tag "tag"
291 template < typename... Options >
292 struct base_hook: public hook< opt::base_hook_tag, Options... >
297 \p MemberOffset defines offset in bytes of \ref node member into your structure.
298 Use \p offsetof macro to define \p MemberOffset
301 - \p cuckoo::probeset_type - probeset type. Defaul is \p cuckoo::list
302 - \p cuckoo::store_hash - store hash values in the node or not. Default is 0 (no storing)
303 - \p opt::tag - a \ref cds_intrusive_hook_tag "tag"
305 template < size_t MemberOffset, typename... Options >
306 struct member_hook: public hook< opt::member_hook_tag, Options... >
309 static const size_t c_nMemberOffset = MemberOffset;
315 \p NodeTraits defines type traits for node.
316 See \ref node_traits for \p NodeTraits interface description
319 - \p cuckoo::probeset_type - probeset type. Defaul is \p cuckoo::list
320 - \p cuckoo::store_hash - store hash values in the node or not. Default is 0 (no storing)
321 - \p opt::tag - a \ref cds_intrusive_hook_tag "tag"
323 template <typename NodeTraits, typename... Options >
324 struct traits_hook: public hook< opt::traits_hook_tag, Options... >
327 typedef NodeTraits node_traits;
331 /// Internal statistics for \ref striping mutex policy
332 struct striping_stat {
333 typedef cds::atomicity::event_counter counter_type; ///< Counter type
335 counter_type m_nCellLockCount ; ///< Count of obtaining cell lock
336 counter_type m_nCellTryLockCount ; ///< Count of cell \p try_lock attempts
337 counter_type m_nFullLockCount ; ///< Count of obtaining full lock
338 counter_type m_nResizeLockCount ; ///< Count of obtaining resize lock
339 counter_type m_nResizeCount ; ///< Count of resize event
342 void onCellLock() { ++m_nCellLockCount; }
343 void onCellTryLock() { ++m_nCellTryLockCount; }
344 void onFullLock() { ++m_nFullLockCount; }
345 void onResizeLock() { ++m_nResizeLockCount; }
346 void onResize() { ++m_nResizeCount; }
350 /// Dummy internal statistics for \ref striping mutex policy
351 struct empty_striping_stat {
353 void onCellLock() const {}
354 void onCellTryLock() const {}
355 void onFullLock() const {}
356 void onResizeLock() const {}
357 void onResize() const {}
361 /// Lock striping concurrent access policy
363 This is one of available opt::mutex_policy option type for CuckooSet
365 Lock striping is very simple technique.
366 The cuckoo set consists of the bucket tables and the array of locks.
367 There is single lock array for each bucket table, at least, the count of bucket table is 2.
368 Initially, the capacity of lock array and each bucket table is the same.
369 When set is resized, bucket table capacity will be doubled but lock array will not.
370 The lock \p i protects each bucket \p j, where <tt> j = i mod L </tt>,
371 where \p L - the size of lock array.
373 The policy contains an internal array of \p RecursiveLock locks.
376 - \p RecursiveLock - the type of recursive mutex. The default is \p std::recursive_mutex. The mutex type should be default-constructible.
377 Note that a recursive spin-lock is not suitable for lock striping for performance reason.
378 - \p Arity - unsigned int constant that specifies an arity. The arity is the count of hash functors, i.e., the
379 count of lock arrays. Default value is 2.
380 - \p Alloc - allocator type used for lock array memory allocation. Default is \p CDS_DEFAULT_ALLOCATOR.
381 - \p Stat - internal statistics type. Note that this template argument is automatically selected by \ref CuckooSet
382 class according to its \p opt::stat option.
385 class RecursiveLock = std::recursive_mutex,
386 unsigned int Arity = 2,
387 class Alloc = CDS_DEFAULT_ALLOCATOR,
388 class Stat = empty_striping_stat
393 typedef RecursiveLock lock_type ; ///< lock type
394 typedef Alloc allocator_type ; ///< allocator type
395 static unsigned int const c_nArity = Arity ; ///< the arity
396 typedef Stat statistics_type ; ///< Internal statistics type (\ref striping_stat or \ref empty_striping_stat)
399 typedef striping_stat real_stat;
400 typedef empty_striping_stat empty_stat;
402 template <typename Stat2>
403 struct rebind_statistics {
404 typedef striping<lock_type, c_nArity, allocator_type, Stat2> other;
408 typedef cds::sync::lock_array< lock_type, cds::sync::pow2_select_policy, allocator_type > lock_array_type ; ///< lock array type
412 class lock_array: public lock_array_type
416 lock_array(): lock_array_type( typename lock_array_type::select_cell_policy(2)) {}
419 lock_array( size_t nCapacity ): lock_array_type( nCapacity, typename lock_array_type::select_cell_policy(nCapacity)) {}
422 class scoped_lock: public std::unique_lock< lock_array_type >
424 typedef std::unique_lock< lock_array_type > base_class;
426 scoped_lock( lock_array& arrLock, size_t nHash ): base_class( arrLock, nHash ) {}
432 lock_array m_Locks[c_nArity] ; ///< array of \p lock_array_type
433 statistics_type m_Stat ; ///< internal statistics
438 class scoped_cell_lock {
439 lock_type * m_guard[c_nArity];
442 scoped_cell_lock( striping& policy, size_t const* arrHash )
444 for ( unsigned int i = 0; i < c_nArity; ++i ) {
445 m_guard[i] = &( policy.m_Locks[i].at( policy.m_Locks[i].lock( arrHash[i] )));
447 policy.m_Stat.onCellLock();
452 for ( unsigned int i = 0; i < c_nArity; ++i )
453 m_guard[i]->unlock();
457 class scoped_cell_trylock
459 typedef typename lock_array_type::lock_type lock_type;
461 lock_type * m_guard[c_nArity];
465 scoped_cell_trylock( striping& policy, size_t const* arrHash )
467 size_t nCell = policy.m_Locks[0].try_lock( arrHash[0] );
468 m_bLocked = nCell != lock_array_type::c_nUnspecifiedCell;
470 m_guard[0] = &(policy.m_Locks[0].at(nCell));
471 for ( unsigned int i = 1; i < c_nArity; ++i ) {
472 m_guard[i] = &( policy.m_Locks[i].at( policy.m_Locks[i].lock( arrHash[i] )));
476 std::fill( m_guard, m_guard + c_nArity, nullptr );
478 policy.m_Stat.onCellTryLock();
480 ~scoped_cell_trylock()
483 for ( unsigned int i = 0; i < c_nArity; ++i )
484 m_guard[i]->unlock();
494 class scoped_full_lock {
495 std::unique_lock< lock_array_type > m_guard;
497 scoped_full_lock( striping& policy )
498 : m_guard( policy.m_Locks[0] )
500 policy.m_Stat.onFullLock();
503 /// Ctor for scoped_resize_lock - no statistics is incremented
504 scoped_full_lock( striping& policy, bool )
505 : m_guard( policy.m_Locks[0] )
509 class scoped_resize_lock: public scoped_full_lock {
511 scoped_resize_lock( striping& policy )
512 : scoped_full_lock( policy, false )
514 policy.m_Stat.onResizeLock();
522 size_t nLockCount ///< The size of lock array. Must be power of two.
525 // Trick: initialize the array of locks
526 for ( unsigned int i = 0; i < c_nArity; ++i ) {
527 lock_array * pArr = m_Locks + i;
528 pArr->lock_array::~lock_array();
529 new ( pArr ) lock_array( nLockCount );
533 /// Returns lock array size
535 Lock array size is unchanged during \p striping object lifetime
537 size_t lock_count() const
539 return m_Locks[0].size();
543 void resize( size_t )
549 /// Returns the arity of striping mutex policy
550 CDS_CONSTEXPR unsigned int arity() const CDS_NOEXCEPT
555 /// Returns internal statistics
556 statistics_type const& statistics() const
562 /// Internal statistics for \ref refinable mutex policy
563 struct refinable_stat {
564 typedef cds::atomicity::event_counter counter_type ; ///< Counter type
566 counter_type m_nCellLockCount ; ///< Count of obtaining cell lock
567 counter_type m_nCellLockWaitResizing ; ///< Count of loop iteration to wait for resizing
568 counter_type m_nCellLockArrayChanged ; ///< Count of event "Lock array has been changed when obtaining cell lock"
569 counter_type m_nCellLockFailed ; ///< Count of event "Cell lock failed because of the array is owned by other thread"
571 counter_type m_nSecondCellLockCount ; ///< Count of obtaining cell lock when another cell is already locked
572 counter_type m_nSecondCellLockFailed ; ///< Count of unsuccess obtaining cell lock when another cell is already locked
574 counter_type m_nFullLockCount ; ///< Count of obtaining full lock
575 counter_type m_nFullLockIter ; ///< Count of unsuccessfull iteration to obtain full lock
577 counter_type m_nResizeLockCount ; ///< Count of obtaining resize lock
578 counter_type m_nResizeLockIter ; ///< Count of unsuccessfull iteration to obtain resize lock
579 counter_type m_nResizeLockArrayChanged; ///< Count of event "Lock array has been changed when obtaining resize lock"
580 counter_type m_nResizeCount ; ///< Count of resize event
583 void onCellLock() { ++m_nCellLockCount; }
584 void onCellWaitResizing() { ++m_nCellLockWaitResizing; }
585 void onCellArrayChanged() { ++m_nCellLockArrayChanged; }
586 void onCellLockFailed() { ++m_nCellLockFailed; }
587 void onSecondCellLock() { ++m_nSecondCellLockCount; }
588 void onSecondCellLockFailed() { ++m_nSecondCellLockFailed; }
589 void onFullLock() { ++m_nFullLockCount; }
590 void onFullLockIter() { ++m_nFullLockIter; }
591 void onResizeLock() { ++m_nResizeLockCount; }
592 void onResizeLockIter() { ++m_nResizeLockIter; }
593 void onResizeLockArrayChanged() { ++m_nResizeLockArrayChanged; }
594 void onResize() { ++m_nResizeCount; }
598 /// Dummy internal statistics for \ref refinable mutex policy
599 struct empty_refinable_stat {
601 void onCellLock() const {}
602 void onCellWaitResizing() const {}
603 void onCellArrayChanged() const {}
604 void onCellLockFailed() const {}
605 void onSecondCellLock() const {}
606 void onSecondCellLockFailed() const {}
607 void onFullLock() const {}
608 void onFullLockIter() const {}
609 void onResizeLock() const {}
610 void onResizeLockIter() const {}
611 void onResizeLockArrayChanged() const {}
612 void onResize() const {}
616 /// Refinable concurrent access policy
618 This is one of available opt::mutex_policy option type for CuckooSet
620 Refining is like a striping technique (see cuckoo::striping)
621 but it allows growing the size of lock array when resizing the hash table.
622 So, the sizes of hash table and lock array are equal.
625 - \p RecursiveLock - the type of mutex. Reentrant (recursive) mutex is required.
626 The default is \p std::recursive_mutex. The mutex type should be default-constructible.
627 - \p Arity - unsigned int constant that specifies an arity. The arity is the count of hash functors, i.e., the
628 count of lock arrays. Default value is 2.
629 - \p BackOff - back-off strategy. Default is cds::backoff::yield
630 - \p Alloc - allocator type used for lock array memory allocation. Default is \p CDS_DEFAULT_ALLOCATOR.
631 - \p Stat - internal statistics type. Note that this template argument is automatically selected by \ref CuckooSet
632 class according to its \p opt::stat option.
635 class RecursiveLock = std::recursive_mutex,
636 unsigned int Arity = 2,
637 typename BackOff = cds::backoff::yield,
638 class Alloc = CDS_DEFAULT_ALLOCATOR,
639 class Stat = empty_refinable_stat
644 typedef RecursiveLock lock_type ; ///< lock type
645 typedef Alloc allocator_type ; ///< allocator type
646 typedef BackOff back_off ; ///< back-off strategy
647 typedef Stat statistics_type ; ///< internal statistics type
648 static unsigned int const c_nArity = Arity; ///< the arity
651 typedef refinable_stat real_stat;
652 typedef empty_refinable_stat empty_stat;
654 template <typename Stat2>
655 struct rebind_statistics {
656 typedef refinable< lock_type, c_nArity, back_off, allocator_type, Stat2> other;
662 typedef cds::sync::trivial_select_policy lock_selection_policy;
664 class lock_array_type
665 : public cds::sync::lock_array< lock_type, lock_selection_policy, allocator_type >
666 , public std::enable_shared_from_this< lock_array_type >
668 typedef cds::sync::lock_array< lock_type, lock_selection_policy, allocator_type > lock_array_base;
670 lock_array_type( size_t nCapacity )
671 : lock_array_base( nCapacity )
674 typedef std::shared_ptr< lock_array_type > lock_array_ptr;
675 typedef cds::details::Allocator< lock_array_type, allocator_type > lock_array_allocator;
677 typedef unsigned long long owner_t;
678 typedef cds::OS::ThreadId threadId_t;
680 typedef cds::sync::spin spinlock_type;
681 typedef std::unique_lock< spinlock_type > scoped_spinlock;
686 static owner_t const c_nOwnerMask = (((owner_t) 1) << (sizeof(owner_t) * 8 - 1)) - 1;
688 atomics::atomic< owner_t > m_Owner ; ///< owner mark (thread id + boolean flag)
689 atomics::atomic<size_t> m_nCapacity ; ///< lock array capacity
690 lock_array_ptr m_arrLocks[ c_nArity ] ; ///< Lock array. The capacity of array is specified in constructor.
691 spinlock_type m_access ; ///< access to m_arrLocks
692 statistics_type m_Stat ; ///< internal statistics
697 struct lock_array_disposer {
698 void operator()( lock_array_type * pArr )
700 lock_array_allocator().Delete( pArr );
704 lock_array_ptr create_lock_array( size_t nCapacity )
706 return lock_array_ptr( lock_array_allocator().New( nCapacity ), lock_array_disposer());
709 void acquire( size_t const * arrHash, lock_array_ptr * pLockArr, lock_type ** parrLock )
711 owner_t me = (owner_t) cds::OS::get_current_thread_id();
718 scoped_spinlock sl(m_access);
719 for ( unsigned int i = 0; i < c_nArity; ++i )
720 pLockArr[i] = m_arrLocks[i];
723 // wait while resizing
725 who = m_Owner.load( atomics::memory_order_acquire );
726 if ( !( who & 1 ) || (who >> 1) == (me & c_nOwnerMask))
729 m_Stat.onCellWaitResizing();
732 if ( pLockArr[0] != m_arrLocks[0] ) {
733 m_Stat.onCellArrayChanged();
737 size_t const nMask = pLockArr[0]->size() - 1;
738 assert( cds::beans::is_power2( nMask + 1 ));
740 for ( unsigned int i = 0; i < c_nArity; ++i ) {
741 parrLock[i] = &( pLockArr[i]->at( arrHash[i] & nMask ));
745 who = m_Owner.load( atomics::memory_order_acquire );
746 if ( ( !(who & 1) || (who >> 1) == (me & c_nOwnerMask)) && m_arrLocks[0] == pLockArr[0] ) {
751 for ( unsigned int i = 0; i < c_nArity; ++i ) {
752 parrLock[i]->unlock();
755 m_Stat.onCellLockFailed();
758 // clears pLockArr can lead to calling dtor for each item of pLockArr[i] that may be a heavy-weighted operation
759 // (each pLockArr[i] is a shared pointer to array of a ton of mutexes)
760 // It is better to do this before the next loop iteration where we will use spin-locked assignment to pLockArr
761 // Destructing a lot of mutexes under spin-lock is a bad solution
762 for ( unsigned int i = 0; i < c_nArity; ++i )
767 bool try_second_acquire( size_t const * arrHash, lock_type ** parrLock )
769 // It is assumed that the current thread already has a lock
770 // and requires a second lock for other hash
772 size_t const nMask = m_nCapacity.load(atomics::memory_order_acquire) - 1;
773 size_t nCell = m_arrLocks[0]->try_lock( arrHash[0] & nMask);
774 if ( nCell == lock_array_type::c_nUnspecifiedCell ) {
775 m_Stat.onSecondCellLockFailed();
778 parrLock[0] = &(m_arrLocks[0]->at(nCell));
780 for ( unsigned int i = 1; i < c_nArity; ++i ) {
781 parrLock[i] = &( m_arrLocks[i]->at( m_arrLocks[i]->lock( arrHash[i] & nMask)));
784 m_Stat.onSecondCellLock();
790 owner_t me = (owner_t) cds::OS::get_current_thread_id();
795 if ( m_Owner.compare_exchange_strong( ownNull, (me << 1) | 1, atomics::memory_order_acq_rel, atomics::memory_order_relaxed )) {
796 m_arrLocks[0]->lock_all();
802 m_Stat.onFullLockIter();
808 m_arrLocks[0]->unlock_all();
809 m_Owner.store( 0, atomics::memory_order_release );
812 void acquire_resize( lock_array_ptr * pOldLocks )
814 owner_t me = (owner_t) cds::OS::get_current_thread_id();
818 scoped_spinlock sl(m_access);
819 for ( unsigned int i = 0; i < c_nArity; ++i )
820 pOldLocks[i] = m_arrLocks[i];
825 if ( m_Owner.compare_exchange_strong( ownNull, (me << 1) | 1, atomics::memory_order_acq_rel, atomics::memory_order_relaxed )) {
826 if ( pOldLocks[0] != m_arrLocks[0] ) {
827 m_Owner.store( 0, atomics::memory_order_release );
828 m_Stat.onResizeLockArrayChanged();
831 pOldLocks[0]->lock_all();
832 m_Stat.onResizeLock();
837 m_Stat.onResizeLockIter();
839 // clears pOldLocks can lead to calling dtor for each item of pOldLocks[i] that may be a heavy-weighted operation
840 // (each pOldLocks[i] is a shared pointer to array of a ton of mutexes)
841 // It is better to do this before the next loop iteration where we will use spin-locked assignment to pOldLocks
842 // Destructing a lot of mutexes under spin-lock is a bad solution
843 for ( unsigned int i = 0; i < c_nArity; ++i )
844 pOldLocks[i].reset();
848 void release_resize( lock_array_ptr * pOldLocks )
850 m_Owner.store( 0, atomics::memory_order_release );
851 pOldLocks[0]->unlock_all();
857 class scoped_cell_lock {
858 lock_type * m_arrLock[ c_nArity ];
859 lock_array_ptr m_arrLockArr[ c_nArity ];
862 scoped_cell_lock( refinable& policy, size_t const* arrHash )
864 policy.acquire( arrHash, m_arrLockArr, m_arrLock );
869 for ( unsigned int i = 0; i < c_nArity; ++i )
870 m_arrLock[i]->unlock();
874 class scoped_cell_trylock {
875 lock_type * m_arrLock[ c_nArity ];
879 scoped_cell_trylock( refinable& policy, size_t const* arrHash )
881 m_bLocked = policy.try_second_acquire( arrHash, m_arrLock );
884 ~scoped_cell_trylock()
887 for ( unsigned int i = 0; i < c_nArity; ++i )
888 m_arrLock[i]->unlock();
898 class scoped_full_lock {
901 scoped_full_lock( refinable& policy )
904 policy.acquire_all();
908 m_policy.release_all();
912 class scoped_resize_lock
915 lock_array_ptr m_arrLocks[ c_nArity ];
917 scoped_resize_lock( refinable& policy )
920 policy.acquire_resize( m_arrLocks );
922 ~scoped_resize_lock()
924 m_policy.release_resize( m_arrLocks );
932 size_t nLockCount ///< The size of lock array. Must be power of two.
934 , m_nCapacity( nLockCount )
936 assert( cds::beans::is_power2( nLockCount ));
937 for ( unsigned int i = 0; i < c_nArity; ++i )
938 m_arrLocks[i] = create_lock_array( nLockCount );
942 void resize( size_t nCapacity )
944 lock_array_ptr pNew[ c_nArity ];
945 for ( unsigned int i = 0; i < c_nArity; ++i )
946 pNew[i] = create_lock_array( nCapacity );
949 scoped_spinlock sl(m_access);
950 for ( unsigned int i = 0; i < c_nArity; ++i )
951 m_arrLocks[i] = pNew[i];
953 m_nCapacity.store( nCapacity, atomics::memory_order_release );
959 /// Returns lock array size
961 Lock array size is not a constant for \p refinable policy and can be changed when the set is resized.
963 size_t lock_count() const
965 return m_nCapacity.load(atomics::memory_order_relaxed);
968 /// Returns the arity of \p refinable mutex policy
969 CDS_CONSTEXPR unsigned int arity() const CDS_NOEXCEPT
974 /// Returns internal statistics
975 statistics_type const& statistics() const
981 /// \p CuckooSet internal statistics
983 typedef cds::atomicity::event_counter counter_type ; ///< Counter type
985 counter_type m_nRelocateCallCount ; ///< Count of \p relocate() function call
986 counter_type m_nRelocateRoundCount ; ///< Count of attempts to relocate items
987 counter_type m_nFalseRelocateCount ; ///< Count of unneeded attempts of \p relocate call
988 counter_type m_nSuccessRelocateCount ; ///< Count of successful item relocating
989 counter_type m_nRelocateAboveThresholdCount; ///< Count of item relocating above probeset threshold
990 counter_type m_nFailedRelocateCount ; ///< Count of failed relocation attemp (when all probeset is full)
992 counter_type m_nResizeCallCount ; ///< Count of \p resize() function call
993 counter_type m_nFalseResizeCount ; ///< Count of false \p resize() function call (when other thread has been resized the set)
994 counter_type m_nResizeSuccessNodeMove; ///< Count of successful node moving when resizing
995 counter_type m_nResizeRelocateCall ; ///< Count of \p relocate() function call from \p resize function
997 counter_type m_nInsertSuccess ; ///< Count of successful \p insert() function call
998 counter_type m_nInsertFailed ; ///< Count of failed \p insert() function call
999 counter_type m_nInsertResizeCount ; ///< Count of \p resize() function call from \p insert()
1000 counter_type m_nInsertRelocateCount ; ///< Count of \p relocate() function call from \p insert()
1001 counter_type m_nInsertRelocateFault ; ///< Count of failed \p relocate() function call from \p insert()
1003 counter_type m_nUpdateExistCount ; ///< Count of call \p update() function for existing node
1004 counter_type m_nUpdateSuccessCount ; ///< Count of successful \p insert() function call for new node
1005 counter_type m_nUpdateResizeCount ; ///< Count of \p resize() function call from \p update()
1006 counter_type m_nUpdateRelocateCount ; ///< Count of \p relocate() function call from \p update()
1007 counter_type m_nUpdateRelocateFault ; ///< Count of failed \p relocate() function call from \p update()
1009 counter_type m_nUnlinkSuccess ; ///< Count of success \p unlink() function call
1010 counter_type m_nUnlinkFailed ; ///< Count of failed \p unlink() function call
1012 counter_type m_nEraseSuccess ; ///< Count of success \p erase() function call
1013 counter_type m_nEraseFailed ; ///< Count of failed \p erase() function call
1015 counter_type m_nFindSuccess ; ///< Count of success \p find() function call
1016 counter_type m_nFindFailed ; ///< Count of failed \p find() function call
1018 counter_type m_nFindEqualSuccess ; ///< Count of success \p find_equal() function call
1019 counter_type m_nFindEqualFailed ; ///< Count of failed \p find_equal() function call
1021 counter_type m_nFindWithSuccess ; ///< Count of success \p find_with() function call
1022 counter_type m_nFindWithFailed ; ///< Count of failed \p find_with() function call
1025 void onRelocateCall() { ++m_nRelocateCallCount; }
1026 void onRelocateRound() { ++m_nRelocateRoundCount; }
1027 void onFalseRelocateRound() { ++m_nFalseRelocateCount; }
1028 void onSuccessRelocateRound(){ ++m_nSuccessRelocateCount; }
1029 void onRelocateAboveThresholdRound() { ++m_nRelocateAboveThresholdCount; }
1030 void onFailedRelocate() { ++m_nFailedRelocateCount; }
1032 void onResizeCall() { ++m_nResizeCallCount; }
1033 void onFalseResizeCall() { ++m_nFalseResizeCount; }
1034 void onResizeSuccessMove() { ++m_nResizeSuccessNodeMove; }
1035 void onResizeRelocateCall() { ++m_nResizeRelocateCall; }
1037 void onInsertSuccess() { ++m_nInsertSuccess; }
1038 void onInsertFailed() { ++m_nInsertFailed; }
1039 void onInsertResize() { ++m_nInsertResizeCount; }
1040 void onInsertRelocate() { ++m_nInsertRelocateCount; }
1041 void onInsertRelocateFault() { ++m_nInsertRelocateFault; }
1043 void onUpdateExist() { ++m_nUpdateExistCount; }
1044 void onUpdateSuccess() { ++m_nUpdateSuccessCount; }
1045 void onUpdateResize() { ++m_nUpdateResizeCount; }
1046 void onUpdateRelocate() { ++m_nUpdateRelocateCount; }
1047 void onUpdateRelocateFault() { ++m_nUpdateRelocateFault; }
1049 void onUnlinkSuccess() { ++m_nUnlinkSuccess; }
1050 void onUnlinkFailed() { ++m_nUnlinkFailed; }
1052 void onEraseSuccess() { ++m_nEraseSuccess; }
1053 void onEraseFailed() { ++m_nEraseFailed; }
1055 void onFindSuccess() { ++m_nFindSuccess; }
1056 void onFindFailed() { ++m_nFindFailed; }
1058 void onFindWithSuccess() { ++m_nFindWithSuccess; }
1059 void onFindWithFailed() { ++m_nFindWithFailed; }
1063 /// CuckooSet empty internal statistics
1066 void onRelocateCall() const {}
1067 void onRelocateRound() const {}
1068 void onFalseRelocateRound() const {}
1069 void onSuccessRelocateRound()const {}
1070 void onRelocateAboveThresholdRound() const {}
1071 void onFailedRelocate() const {}
1073 void onResizeCall() const {}
1074 void onFalseResizeCall() const {}
1075 void onResizeSuccessMove() const {}
1076 void onResizeRelocateCall() const {}
1078 void onInsertSuccess() const {}
1079 void onInsertFailed() const {}
1080 void onInsertResize() const {}
1081 void onInsertRelocate() const {}
1082 void onInsertRelocateFault() const {}
1084 void onUpdateExist() const {}
1085 void onUpdateSuccess() const {}
1086 void onUpdateResize() const {}
1087 void onUpdateRelocate() const {}
1088 void onUpdateRelocateFault() const {}
1090 void onUnlinkSuccess() const {}
1091 void onUnlinkFailed() const {}
1093 void onEraseSuccess() const {}
1094 void onEraseFailed() const {}
1096 void onFindSuccess() const {}
1097 void onFindFailed() const {}
1099 void onFindWithSuccess() const {}
1100 void onFindWithFailed() const {}
1104 /// Type traits for CuckooSet class
1109 Possible values are: cuckoo::base_hook, cuckoo::member_hook, cuckoo::traits_hook.
1111 typedef base_hook<> hook;
1113 /// Hash functors tuple
1115 This is mandatory type and has no predefined one.
1117 At least, two hash functors should be provided. All hash functor
1118 should be orthogonal (different): for each <tt> i,j: i != j => h[i](x) != h[j](x) </tt>.
1119 The hash functors are defined as <tt> std::tuple< H1, H2, ... Hn > </tt>:
1120 \@code cds::opt::hash< std::tuple< h1, h2 > > \@endcode
1121 The number of hash functors specifies the number \p k - the count of hash tables in cuckoo hashing.
1123 To specify hash tuple in traits you should use \p cds::opt::hash_tuple:
1125 struct my_traits: public cds::intrusive::cuckoo::traits {
1126 typedef cds::opt::hash_tuple< hash1, hash2 > hash;
1130 typedef cds::opt::none hash;
1132 /// Concurrent access policy
1134 Available opt::mutex_policy types:
1135 - \p cuckoo::striping - simple, but the lock array is not resizable
1136 - \p cuckoo::refinable - resizable lock array, but more complex access to set data.
1138 Default is \p cuckoo::striping.
1140 typedef cuckoo::striping<> mutex_policy;
1142 /// Key equality functor
1144 Default is <tt>std::equal_to<T></tt>
1146 typedef opt::none equal_to;
1148 /// Key comparing functor
1150 No default functor is provided. If the option is not specified, the \p less is used.
1152 typedef opt::none compare;
1154 /// specifies binary predicate used for key comparison.
1156 Default is \p std::less<T>.
1158 typedef opt::none less;
1162 The type for item counting feature.
1163 Default is \p cds::atomicity::item_counter
1165 Only atomic item counter type is allowed.
1167 typedef atomicity::item_counter item_counter;
1171 The allocator type for allocating bucket tables.
1173 typedef CDS_DEFAULT_ALLOCATOR allocator;
1177 The disposer functor is used in \p CuckooSet::clear() member function
1180 typedef intrusive::opt::v::empty_disposer disposer;
1182 /// Internal statistics. Available statistics: \p cuckoo::stat, \p cuckoo::empty_stat
1183 typedef empty_stat stat;
1186 /// Metafunction converting option list to \p CuckooSet traits
1188 Template argument list \p Options... are:
1189 - \p intrusive::opt::hook - hook used. Possible values are: \p cuckoo::base_hook, \p cuckoo::member_hook,
1190 \p cuckoo::traits_hook.
1191 If the option is not specified, <tt>%cuckoo::base_hook<></tt> is used.
1192 - \p opt::hash - hash functor tuple, mandatory option. At least, two hash functors should be provided. All hash functor
1193 should be orthogonal (different): for each <tt> i,j: i != j => h[i](x) != h[j](x) </tt>.
1194 The hash functors are passed as <tt> std::tuple< H1, H2, ... Hn > </tt>. The number of hash functors specifies
1195 the number \p k - the count of hash tables in cuckoo hashing.
1196 - \p opt::mutex_policy - concurrent access policy.
1197 Available policies: \p cuckoo::striping, \p cuckoo::refinable.
1198 Default is \p %cuckoo::striping.
1199 - \p opt::equal_to - key equality functor like \p std::equal_to.
1200 If this functor is defined then the probe-set will be unordered.
1201 If \p %opt::compare or \p %opt::less option is specified too, then the probe-set will be ordered
1202 and \p %opt::equal_to will be ignored.
1203 - \p opt::compare - key comparison functor. No default functor is provided.
1204 If the option is not specified, the \p %opt::less is used.
1205 If \p %opt::compare or \p %opt::less option is specified, then the probe-set will be ordered.
1206 - \p opt::less - specifies binary predicate used for key comparison. Default is \p std::less<T>.
1207 If \p %opt::compare or \p %opt::less option is specified, then the probe-set will be ordered.
1208 - \p opt::item_counter - the type of item counting feature. Default is \p atomicity::item_counter
1209 The item counter should be atomic.
1210 - \p opt::allocator - the allocator type using for allocating bucket tables.
1211 Default is \ref CDS_DEFAULT_ALLOCATOR
1212 - \p intrusive::opt::disposer - the disposer type used in \p clear() member function for
1213 freeing nodes. Default is \p intrusive::opt::v::empty_disposer
1214 - \p opt::stat - internal statistics. Possibly types: \p cuckoo::stat, \p cuckoo::empty_stat.
1215 Default is \p %cuckoo::empty_stat
1217 The probe set traits \p cuckoo::probeset_type and \p cuckoo::store_hash are taken from \p node type
1218 specified by \p opt::hook option.
1220 template <typename... Options>
1221 struct make_traits {
1222 typedef typename cds::opt::make_options<
1223 typename cds::opt::find_type_traits< cuckoo::traits, Options... >::type
1225 >::type type ; ///< Result of metafunction
1230 template <typename Node, typename Probeset>
1233 template <typename Node>
1234 class bucket_entry<Node, cuckoo::list>
1237 typedef Node node_type;
1238 typedef cuckoo::list_probeset_class probeset_class;
1239 typedef cuckoo::list probeset_type;
1249 friend class bucket_entry;
1255 iterator( node_type * p )
1258 iterator( iterator const& it)
1262 iterator& operator=( iterator const& it )
1268 iterator& operator=( node_type * p )
1274 node_type * operator->()
1278 node_type& operator*()
1280 assert( pNode != nullptr );
1285 iterator& operator ++()
1288 pNode = pNode->m_pNext;
1292 bool operator==(iterator const& it ) const
1294 return pNode == it.pNode;
1296 bool operator!=(iterator const& it ) const
1298 return !( *this == it );
1307 static_assert(( std::is_same<typename node_type::probeset_type, probeset_type>::value ), "Incompatible node type" );
1312 return iterator(pHead);
1319 void insert_after( iterator it, node_type * p )
1321 node_type * pPrev = it.pNode;
1323 p->m_pNext = pPrev->m_pNext;
1334 void remove( iterator itPrev, iterator itWhat )
1336 node_type * pPrev = itPrev.pNode;
1337 node_type * pWhat = itWhat.pNode;
1338 assert( (!pPrev && pWhat == pHead) || (pPrev && pPrev->m_pNext == pWhat));
1341 pPrev->m_pNext = pWhat->m_pNext;
1343 assert( pWhat == pHead );
1344 pHead = pHead->m_pNext;
1353 for ( node_type * pNode = pHead; pNode; pNode = pNext ) {
1354 pNext = pNode->m_pNext;
1362 template <typename Disposer>
1363 void clear( Disposer disp )
1366 for ( node_type * pNode = pHead; pNode; pNode = pNext ) {
1367 pNext = pNode->m_pNext;
1376 unsigned int size() const
1382 template <typename Node, unsigned int Capacity>
1383 class bucket_entry<Node, cuckoo::vector<Capacity>>
1386 typedef Node node_type;
1387 typedef cuckoo::vector_probeset_class probeset_class;
1388 typedef cuckoo::vector<Capacity> probeset_type;
1390 static unsigned int const c_nCapacity = probeset_type::c_nCapacity;
1393 node_type * m_arrNode[c_nCapacity];
1394 unsigned int m_nSize;
1396 void shift_up( unsigned int nFrom )
1398 assert( m_nSize < c_nCapacity );
1400 if ( nFrom < m_nSize )
1401 std::copy_backward( m_arrNode + nFrom, m_arrNode + m_nSize, m_arrNode + m_nSize + 1 );
1404 void shift_down( node_type ** pFrom )
1406 assert( m_arrNode <= pFrom && pFrom < m_arrNode + m_nSize);
1407 std::copy( pFrom + 1, m_arrNode + m_nSize, pFrom );
1413 friend class bucket_entry;
1419 iterator( node_type ** p )
1422 iterator( iterator const& it)
1426 iterator& operator=( iterator const& it )
1432 node_type * operator->()
1434 assert( pArr != nullptr );
1437 node_type& operator*()
1439 assert( pArr != nullptr );
1440 assert( *pArr != nullptr );
1445 iterator& operator ++()
1451 bool operator==(iterator const& it ) const
1453 return pArr == it.pArr;
1455 bool operator!=(iterator const& it ) const
1457 return !( *this == it );
1465 memset( m_arrNode, 0, sizeof(m_arrNode));
1466 static_assert(( std::is_same<typename node_type::probeset_type, probeset_type>::value ), "Incompatible node type" );
1471 return iterator(m_arrNode);
1475 return iterator(m_arrNode + size());
1478 void insert_after( iterator it, node_type * p )
1480 assert( m_nSize < c_nCapacity );
1481 assert( !it.pArr || (m_arrNode <= it.pArr && it.pArr <= m_arrNode + m_nSize));
1484 shift_up( static_cast<unsigned int>(it.pArr - m_arrNode) + 1 );
1494 void remove( iterator /*itPrev*/, iterator itWhat )
1497 shift_down( itWhat.pArr );
1506 template <typename Disposer>
1507 void clear( Disposer disp )
1509 for ( unsigned int i = 0; i < m_nSize; ++i ) {
1510 disp( m_arrNode[i] );
1515 unsigned int size() const
1521 template <typename Node, unsigned int ArraySize>
1523 static void store( Node * pNode, size_t * pHashes )
1525 memcpy( pNode->m_arrHash, pHashes, sizeof(pHashes[0]) * ArraySize );
1527 static bool equal_to( Node& node, unsigned int nTable, size_t nHash )
1529 return node.m_arrHash[nTable] == nHash;
1532 template <typename Node>
1533 struct hash_ops<Node, 0>
1535 static void store( Node * /*pNode*/, size_t * /*pHashes*/ )
1537 static bool equal_to( Node& /*node*/, unsigned int /*nTable*/, size_t /*nHash*/ )
1543 template <typename NodeTraits, bool Ordered>
1546 template <typename NodeTraits>
1547 struct contains<NodeTraits, true>
1549 template <typename BucketEntry, typename Position, typename Q, typename Compare>
1550 static bool find( BucketEntry& probeset, Position& pos, unsigned int /*nTable*/, size_t /*nHash*/, Q const& val, Compare cmp )
1553 typedef typename BucketEntry::iterator bucket_iterator;
1555 bucket_iterator itPrev;
1557 for ( bucket_iterator it = probeset.begin(), itEnd = probeset.end(); it != itEnd; ++it ) {
1558 int cmpRes = cmp( *NodeTraits::to_value_ptr(*it), val );
1559 if ( cmpRes >= 0 ) {
1561 pos.itPrev = itPrev;
1568 pos.itPrev = itPrev;
1569 pos.itFound = probeset.end();
1574 template <typename NodeTraits>
1575 struct contains<NodeTraits, false>
1577 template <typename BucketEntry, typename Position, typename Q, typename EqualTo>
1578 static bool find( BucketEntry& probeset, Position& pos, unsigned int nTable, size_t nHash, Q const& val, EqualTo eq )
1580 // Unordered version
1581 typedef typename BucketEntry::iterator bucket_iterator;
1582 typedef typename BucketEntry::node_type node_type;
1584 bucket_iterator itPrev;
1586 for ( bucket_iterator it = probeset.begin(), itEnd = probeset.end(); it != itEnd; ++it ) {
1587 if ( hash_ops<node_type, node_type::hash_array_size>::equal_to( *it, nTable, nHash ) && eq( *NodeTraits::to_value_ptr(*it), val )) {
1589 pos.itPrev = itPrev;
1595 pos.itPrev = itPrev;
1596 pos.itFound = probeset.end();
1601 } // namespace details
1604 } // namespace cuckoo
1607 /** @ingroup cds_intrusive_map
1610 - [2007] M.Herlihy, N.Shavit, M.Tzafrir "Concurrent Cuckoo Hashing. Technical report"
1611 - [2008] Maurice Herlihy, Nir Shavit "The Art of Multiprocessor Programming"
1613 <b>About Cuckoo hashing</b>
1615 [From <i>"The Art of Multiprocessor Programming"</i>]
1616 <a href="https://en.wikipedia.org/wiki/Cuckoo_hashing">Cuckoo hashing</a> is a hashing algorithm in which a newly added item displaces any earlier item
1617 occupying the same slot. For brevity, a table is a k-entry array of items. For a hash set f size
1618 N = 2k we use a two-entry array of tables, and two independent hash functions,
1619 <tt> h0, h1: KeyRange -> 0,...,k-1</tt>
1620 mapping the set of possible keys to entries in he array. To test whether a value \p x is in the set,
1621 <tt>find(x)</tt> tests whether either <tt>table[0][h0(x)]</tt> or <tt>table[1][h1(x)]</tt> is
1622 equal to \p x. Similarly, <tt>erase(x)</tt>checks whether \p x is in either <tt>table[0][h0(x)]</tt>
1623 or <tt>table[1][h1(x)]</tt>, ad removes it if found.
1625 The <tt>insert(x)</tt> successively "kicks out" conflicting items until every key has a slot.
1626 To add \p x, the method swaps \p x with \p y, the current occupant of <tt>table[0][h0(x)]</tt>.
1627 If the prior value was \p nullptr, it is done. Otherwise, it swaps the newly nest-less value \p y
1628 for the current occupant of <tt>table[1][h1(y)]</tt> in the same way. As before, if the prior value
1629 was \p nullptr, it is done. Otherwise, the method continues swapping entries (alternating tables)
1630 until it finds an empty slot. We might not find an empty slot, either because the table is full,
1631 or because the sequence of displacement forms a cycle. We therefore need an upper limit on the
1632 number of successive displacements we are willing to undertake. When this limit is exceeded,
1633 we resize the hash table, choose new hash functions and start over.
1635 For concurrent cuckoo hashing, rather than organizing the set as a two-dimensional table of
1636 items, we use two-dimensional table of probe sets, where a probe set is a constant-sized set
1637 of items with the same hash code. Each probe set holds at most \p PROBE_SIZE items, but the algorithm
1638 tries to ensure that when the set is quiescent (i.e no method call in progress) each probe set
1639 holds no more than <tt>THRESHOLD < PROBE_SET</tt> items. While method calls are in-flight, a probe
1640 set may temporarily hold more than \p THRESHOLD but never more than \p PROBE_SET items.
1642 In current implementation, a probe set can be defined either as a (single-linked) list
1643 or as a fixed-sized vector, optionally ordered.
1645 In description above two-table cuckoo hashing (<tt>k = 2</tt>) has been considered.
1646 We can generalize this approach for <tt>k >= 2</tt> when we have \p k hash functions
1647 <tt>h[0], ... h[k-1]</tt> and \p k tables <tt>table[0], ... table[k-1]</tt>.
1649 The search in probe set is linear, the complexity is <tt> O(PROBE_SET) </tt>.
1650 The probe set may be ordered or not. Ordered probe set can be more efficient since
1651 the average search complexity is <tt>O(PROBE_SET/2)</tt>.
1652 However, the overhead of sorting can eliminate a gain of ordered search.
1654 The probe set is ordered if \p compare or \p less is specified in \p Traits template
1655 parameter. Otherwise, the probe set is unordered and \p Traits should provide
1656 \p equal_to predicate.
1658 The \p cds::intrusive::cuckoo namespace contains \p %CuckooSet-related declarations.
1661 - \p T - the type stored in the set. The type must be based on \p cuckoo::node (for \p cuckoo::base_hook)
1662 or it must have a member of type %cuckoo::node (for \p cuckoo::member_hook),
1663 or it must be convertible to \p %cuckoo::node (for \p cuckoo::traits_hook)
1664 - \p Traits - type traits, default is \p cuckoo::traits. It is possible to declare option-based
1665 set with \p cuckoo::make_traits metafunction result as \p Traits template argument.
1669 You should incorporate \p cuckoo::node into your struct \p T and provide
1670 appropriate \p cuckoo::traits::hook in your \p Traits template parameters.
1671 Usually, for \p Traits you define a struct based on \p cuckoo::traits.
1673 Example for base hook and list-based probe-set:
1675 #include <cds/intrusive/cuckoo_set.h>
1677 // Data stored in cuckoo set
1678 // We use list as probe-set container and store hash values in the node
1679 // (since we use two hash functions we should store 2 hash values per node)
1680 struct my_data: public cds::intrusive::cuckoo::node< cds::intrusive::cuckoo::list, 2 >
1689 // Provide equal_to functor for my_data since we will use unordered probe-set
1690 struct my_data_equal_to {
1691 bool operator()( const my_data& d1, const my_data& d2 ) const
1693 return d1.strKey.compare( d2.strKey ) == 0;
1696 bool operator()( const my_data& d, const std::string& s ) const
1698 return d.strKey.compare(s) == 0;
1701 bool operator()( const std::string& s, const my_data& d ) const
1703 return s.compare( d.strKey ) == 0;
1707 // Provide two hash functor for my_data
1709 size_t operator()(std::string const& s) const
1711 return cds::opt::v::hash<std::string>( s );
1713 size_t operator()( my_data const& d ) const
1715 return (*this)( d.strKey );
1719 struct hash2: private hash1 {
1720 size_t operator()(std::string const& s) const
1722 size_t h = ~( hash1::operator()(s));
1723 return ~h + 0x9e3779b9 + (h << 6) + (h >> 2);
1725 size_t operator()( my_data const& d ) const
1727 return (*this)( d.strKey );
1731 // Declare type traits
1732 struct my_traits: public cds::intrusive::cuckoo::traits
1734 typedef cds::intrusive::cuckoo::base_hook<
1735 cds::intrusive::cuckoo::probeset_type< my_data::probeset_type >
1736 ,cds::intrusive::cuckoo::store_hash< my_data::hash_array_size >
1738 typedef my_data_equa_to equal_to;
1739 typedef cds::opt::hash_tuple< hash1, hash2 > hash;
1742 // Declare CuckooSet type
1743 typedef cds::intrusive::CuckooSet< my_data, my_traits > my_cuckoo_set;
1745 // Equal option-based declaration
1746 typedef cds::intrusive::CuckooSet< my_data,
1747 cds::intrusive::cuckoo::make_traits<
1748 cds::intrusive::opt::hook< cds::intrusive::cuckoo::base_hook<
1749 cds::intrusive::cuckoo::probeset_type< my_data::probeset_type >
1750 ,cds::intrusive::cuckoo::store_hash< my_data::hash_array_size >
1752 ,cds::opt::hash< std::tuple< hash1, hash2 > >
1753 ,cds::opt::equal_to< my_data_equal_to >
1758 If we provide \p compare function instead of \p equal_to for \p my_data
1759 we get as a result a cuckoo set with ordered probe set that may improve
1761 Example for base hook and ordered vector-based probe-set:
1764 #include <cds/intrusive/cuckoo_set.h>
1766 // Data stored in cuckoo set
1767 // We use a vector of capacity 4 as probe-set container and store hash values in the node
1768 // (since we use two hash functions we should store 2 hash values per node)
1769 struct my_data: public cds::intrusive::cuckoo::node< cds::intrusive::cuckoo::vector<4>, 2 >
1778 // Provide compare functor for my_data since we want to use ordered probe-set
1779 struct my_data_compare {
1780 int operator()( const my_data& d1, const my_data& d2 ) const
1782 return d1.strKey.compare( d2.strKey );
1785 int operator()( const my_data& d, const std::string& s ) const
1787 return d.strKey.compare(s);
1790 int operator()( const std::string& s, const my_data& d ) const
1792 return s.compare( d.strKey );
1796 // Provide two hash functor for my_data
1798 size_t operator()(std::string const& s) const
1800 return cds::opt::v::hash<std::string>( s );
1802 size_t operator()( my_data const& d ) const
1804 return (*this)( d.strKey );
1808 struct hash2: private hash1 {
1809 size_t operator()(std::string const& s) const
1811 size_t h = ~( hash1::operator()(s));
1812 return ~h + 0x9e3779b9 + (h << 6) + (h >> 2);
1814 size_t operator()( my_data const& d ) const
1816 return (*this)( d.strKey );
1820 // Declare type traits
1821 struct my_traits: public cds::intrusive::cuckoo::traits
1823 typedef cds::intrusive::cuckoo::base_hook<
1824 cds::intrusive::cuckoo::probeset_type< my_data::probeset_type >
1825 ,cds::intrusive::cuckoo::store_hash< my_data::hash_array_size >
1827 typedef my_data_compare compare;
1828 typedef cds::opt::hash_tuple< hash1, hash2 > hash;
1831 // Declare CuckooSet type
1832 typedef cds::intrusive::CuckooSet< my_data, my_traits > my_cuckoo_set;
1834 // Equal option-based declaration
1835 typedef cds::intrusive::CuckooSet< my_data,
1836 cds::intrusive::cuckoo::make_traits<
1837 cds::intrusive::opt::hook< cds::intrusive::cuckoo::base_hook<
1838 cds::intrusive::cuckoo::probeset_type< my_data::probeset_type >
1839 ,cds::intrusive::cuckoo::store_hash< my_data::hash_array_size >
1841 ,cds::opt::hash< std::tuple< hash1, hash2 > >
1842 ,cds::opt::compare< my_data_compare >
1848 template <typename T, typename Traits = cuckoo::traits>
1852 typedef T value_type; ///< The value type stored in the set
1853 typedef Traits traits; ///< Set traits
1855 typedef typename traits::hook hook; ///< hook type
1856 typedef typename hook::node_type node_type; ///< node type
1857 typedef typename get_node_traits< value_type, node_type, hook>::type node_traits; ///< node traits
1859 typedef typename traits::hash hash; ///< hash functor tuple wrapped for internal use
1860 typedef typename hash::hash_tuple_type hash_tuple_type; ///< Type of hash tuple
1862 typedef typename traits::stat stat; ///< internal statistics type
1864 typedef typename traits::mutex_policy original_mutex_policy; ///< Concurrent access policy, see \p cuckoo::traits::mutex_policy
1867 typedef typename original_mutex_policy::template rebind_statistics<
1868 typename std::conditional<
1869 std::is_same< stat, cuckoo::empty_stat >::value
1870 ,typename original_mutex_policy::empty_stat
1871 ,typename original_mutex_policy::real_stat
1873 >::other mutex_policy;
1876 /// Probe set should be ordered or not
1878 If \p Traits specifies \p cmpare or \p less functor then the set is ordered.
1879 Otherwise, it is unordered and \p Traits should provide \p equal_to functor.
1881 static bool const c_isSorted = !( std::is_same< typename traits::compare, opt::none >::value
1882 && std::is_same< typename traits::less, opt::none >::value );
1883 static size_t const c_nArity = hash::size ; ///< the arity of cuckoo hashing: the number of hash functors provided; minimum 2.
1885 /// Key equality functor; used only for unordered probe-set
1886 typedef typename opt::details::make_equal_to< value_type, traits, !c_isSorted>::type key_equal_to;
1888 /// key comparing functor based on \p opt::compare and \p opt::less option setter. Used only for ordered probe set
1889 typedef typename opt::details::make_comparator< value_type, traits >::type key_comparator;
1892 typedef typename traits::allocator allocator;
1894 /// item counter type
1895 typedef typename traits::item_counter item_counter;
1898 typedef typename traits::disposer disposer;
1902 typedef typename node_type::probeset_class probeset_class;
1903 typedef typename node_type::probeset_type probeset_type;
1904 static unsigned int const c_nNodeHashArraySize = node_type::hash_array_size;
1906 typedef typename mutex_policy::scoped_cell_lock scoped_cell_lock;
1907 typedef typename mutex_policy::scoped_cell_trylock scoped_cell_trylock;
1908 typedef typename mutex_policy::scoped_full_lock scoped_full_lock;
1909 typedef typename mutex_policy::scoped_resize_lock scoped_resize_lock;
1911 typedef cuckoo::details::bucket_entry< node_type, probeset_type > bucket_entry;
1912 typedef typename bucket_entry::iterator bucket_iterator;
1913 typedef cds::details::Allocator< bucket_entry, allocator > bucket_table_allocator;
1915 typedef size_t hash_array[c_nArity] ; ///< hash array
1918 bucket_iterator itPrev;
1919 bucket_iterator itFound;
1922 typedef cuckoo::details::contains< node_traits, c_isSorted > contains_action;
1924 template <typename Predicate>
1925 struct predicate_wrapper {
1926 typedef typename std::conditional< c_isSorted, cds::opt::details::make_comparator_from_less<Predicate>, Predicate>::type type;
1929 typedef typename std::conditional< c_isSorted, key_comparator, key_equal_to >::type key_predicate;
1933 static unsigned int const c_nDefaultProbesetSize = 4; ///< default probeset size
1934 static size_t const c_nDefaultInitialSize = 16; ///< default initial size
1935 static unsigned int const c_nRelocateLimit = c_nArity * 2 - 1; ///< Count of attempts to relocate before giving up
1938 bucket_entry * m_BucketTable[ c_nArity ] ; ///< Bucket tables
1940 size_t m_nBucketMask ; ///< Hash bitmask; bucket table size minus 1.
1941 unsigned int const m_nProbesetSize ; ///< Probe set size
1942 unsigned int const m_nProbesetThreshold ; ///< Probe set threshold
1944 hash m_Hash ; ///< Hash functor tuple
1945 mutex_policy m_MutexPolicy ; ///< concurrent access policy
1946 item_counter m_ItemCounter ; ///< item counter
1947 mutable stat m_Stat ; ///< internal statistics
1951 static void check_common_constraints()
1953 static_assert( (c_nArity == mutex_policy::c_nArity), "The count of hash functors must be equal to mutex_policy arity" );
1956 void check_probeset_properties() const
1958 assert( m_nProbesetThreshold < m_nProbesetSize );
1960 // if probe set type is cuckoo::vector<N> then m_nProbesetSize == N
1961 assert( node_type::probeset_size == 0 || node_type::probeset_size == m_nProbesetSize );
1964 template <typename Q>
1965 void hashing( size_t * pHashes, Q const& v ) const
1967 m_Hash( pHashes, v );
1970 void copy_hash( size_t * pHashes, value_type const& v ) const
1972 if ( c_nNodeHashArraySize )
1973 memcpy( pHashes, node_traits::to_node_ptr( v )->get_hash(), sizeof(pHashes[0]) * c_nNodeHashArraySize );
1975 hashing( pHashes, v );
1978 bucket_entry& bucket( unsigned int nTable, size_t nHash )
1980 assert( nTable < c_nArity );
1981 return m_BucketTable[nTable][nHash & m_nBucketMask];
1984 static void store_hash( node_type * pNode, size_t * pHashes )
1986 cuckoo::details::hash_ops< node_type, c_nNodeHashArraySize >::store( pNode, pHashes );
1989 static bool equal_hash( node_type& node, unsigned int nTable, size_t nHash )
1991 return cuckoo::details::hash_ops< node_type, c_nNodeHashArraySize >::equal_to( node, nTable, nHash );
1994 void allocate_bucket_tables( size_t nSize )
1996 assert( cds::beans::is_power2( nSize ));
1998 m_nBucketMask = nSize - 1;
1999 bucket_table_allocator alloc;
2000 for ( unsigned int i = 0; i < c_nArity; ++i )
2001 m_BucketTable[i] = alloc.NewArray( nSize );
2004 static void free_bucket_tables( bucket_entry ** pTable, size_t nCapacity )
2006 bucket_table_allocator alloc;
2007 for ( unsigned int i = 0; i < c_nArity; ++i ) {
2008 alloc.Delete( pTable[i], nCapacity );
2009 pTable[i] = nullptr;
2012 void free_bucket_tables()
2014 free_bucket_tables( m_BucketTable, m_nBucketMask + 1 );
2017 static CDS_CONSTEXPR unsigned int const c_nUndefTable = (unsigned int) -1;
2018 template <typename Q, typename Predicate >
2019 unsigned int contains( position * arrPos, size_t * arrHash, Q const& val, Predicate pred )
2021 // Buckets must be locked
2023 for ( unsigned int i = 0; i < c_nArity; ++i ) {
2024 bucket_entry& probeset = bucket( i, arrHash[i] );
2025 if ( contains_action::find( probeset, arrPos[i], i, arrHash[i], val, pred ))
2028 return c_nUndefTable;
2031 template <typename Q, typename Predicate, typename Func>
2032 value_type * erase_( Q const& val, Predicate pred, Func f )
2035 hashing( arrHash, val );
2036 position arrPos[ c_nArity ];
2039 scoped_cell_lock guard( m_MutexPolicy, arrHash );
2041 unsigned int nTable = contains( arrPos, arrHash, val, pred );
2042 if ( nTable != c_nUndefTable ) {
2043 node_type& node = *arrPos[nTable].itFound;
2044 f( *node_traits::to_value_ptr(node));
2045 bucket( nTable, arrHash[nTable]).remove( arrPos[nTable].itPrev, arrPos[nTable].itFound );
2047 m_Stat.onEraseSuccess();
2048 return node_traits::to_value_ptr( node );
2052 m_Stat.onEraseFailed();
2056 template <typename Q, typename Predicate, typename Func>
2057 bool find_( Q& val, Predicate pred, Func f )
2060 position arrPos[ c_nArity ];
2061 hashing( arrHash, val );
2062 scoped_cell_lock sl( m_MutexPolicy, arrHash );
2064 unsigned int nTable = contains( arrPos, arrHash, val, pred );
2065 if ( nTable != c_nUndefTable ) {
2066 f( *node_traits::to_value_ptr( *arrPos[nTable].itFound ), val );
2067 m_Stat.onFindSuccess();
2071 m_Stat.onFindFailed();
2075 bool relocate( unsigned int nTable, size_t * arrGoalHash )
2077 // arrGoalHash contains hash values for relocating element
2078 // Relocating element is first one from bucket( nTable, arrGoalHash[nTable] ) probeset
2080 m_Stat.onRelocateCall();
2084 for ( unsigned int nRound = 0; nRound < c_nRelocateLimit; ++nRound ) {
2085 m_Stat.onRelocateRound();
2088 scoped_cell_lock guard( m_MutexPolicy, arrGoalHash );
2090 bucket_entry& refBucket = bucket( nTable, arrGoalHash[nTable] );
2091 if ( refBucket.size() < m_nProbesetThreshold ) {
2092 // probeset is not above the threshold
2093 m_Stat.onFalseRelocateRound();
2097 pVal = node_traits::to_value_ptr( *refBucket.begin());
2098 copy_hash( arrHash, *pVal );
2100 scoped_cell_trylock guard2( m_MutexPolicy, arrHash );
2101 if ( !guard2.locked())
2102 continue ; // try one more time
2104 refBucket.remove( typename bucket_entry::iterator(), refBucket.begin());
2106 unsigned int i = (nTable + 1) % c_nArity;
2108 // try insert into free probeset
2109 while ( i != nTable ) {
2110 bucket_entry& bkt = bucket( i, arrHash[i] );
2111 if ( bkt.size() < m_nProbesetThreshold ) {
2113 contains_action::find( bkt, pos, i, arrHash[i], *pVal, key_predicate()) ; // must return false!
2114 bkt.insert_after( pos.itPrev, node_traits::to_node_ptr( pVal ));
2115 m_Stat.onSuccessRelocateRound();
2118 i = ( i + 1 ) % c_nArity;
2121 // try insert into partial probeset
2122 i = (nTable + 1) % c_nArity;
2123 while ( i != nTable ) {
2124 bucket_entry& bkt = bucket( i, arrHash[i] );
2125 if ( bkt.size() < m_nProbesetSize ) {
2127 contains_action::find( bkt, pos, i, arrHash[i], *pVal, key_predicate()) ; // must return false!
2128 bkt.insert_after( pos.itPrev, node_traits::to_node_ptr( pVal ));
2130 memcpy( arrGoalHash, arrHash, sizeof(arrHash));
2131 m_Stat.onRelocateAboveThresholdRound();
2132 goto next_iteration;
2134 i = (i + 1) % c_nArity;
2137 // all probeset is full, relocating fault
2138 refBucket.insert_after( typename bucket_entry::iterator(), node_traits::to_node_ptr( pVal ));
2139 m_Stat.onFailedRelocate();
2150 m_Stat.onResizeCall();
2152 size_t nOldCapacity = bucket_count();
2153 bucket_entry * pOldTable[ c_nArity ];
2155 scoped_resize_lock guard( m_MutexPolicy );
2157 if ( nOldCapacity != bucket_count()) {
2158 m_Stat.onFalseResizeCall();
2162 size_t nCapacity = nOldCapacity * 2;
2164 m_MutexPolicy.resize( nCapacity );
2165 memcpy( pOldTable, m_BucketTable, sizeof(pOldTable));
2166 allocate_bucket_tables( nCapacity );
2168 typedef typename bucket_entry::iterator bucket_iterator;
2170 position arrPos[ c_nArity ];
2172 for ( unsigned int nTable = 0; nTable < c_nArity; ++nTable ) {
2173 bucket_entry * pTable = pOldTable[nTable];
2174 for ( size_t k = 0; k < nOldCapacity; ++k ) {
2175 bucket_iterator itNext;
2176 for ( bucket_iterator it = pTable[k].begin(), itEnd = pTable[k].end(); it != itEnd; it = itNext ) {
2180 value_type& val = *node_traits::to_value_ptr( *it );
2181 copy_hash( arrHash, val );
2182 contains( arrPos, arrHash, val, key_predicate()) ; // must return c_nUndefTable
2184 for ( unsigned int i = 0; i < c_nArity; ++i ) {
2185 bucket_entry& refBucket = bucket( i, arrHash[i] );
2186 if ( refBucket.size() < m_nProbesetThreshold ) {
2187 refBucket.insert_after( arrPos[i].itPrev, &*it );
2188 m_Stat.onResizeSuccessMove();
2193 for ( unsigned int i = 0; i < c_nArity; ++i ) {
2194 bucket_entry& refBucket = bucket( i, arrHash[i] );
2195 if ( refBucket.size() < m_nProbesetSize ) {
2196 refBucket.insert_after( arrPos[i].itPrev, &*it );
2197 assert( refBucket.size() > 1 );
2198 copy_hash( arrHash, *node_traits::to_value_ptr( *refBucket.begin()));
2199 m_Stat.onResizeRelocateCall();
2200 relocate( i, arrHash );
2209 free_bucket_tables( pOldTable, nOldCapacity );
2212 CDS_CONSTEXPR static unsigned int calc_probeset_size( unsigned int nProbesetSize ) CDS_NOEXCEPT
2214 return std::is_same< probeset_class, cuckoo::vector_probeset_class >::value
2215 ? node_type::probeset_size
2218 : ( node_type::probeset_size ? node_type::probeset_size : c_nDefaultProbesetSize ));
2223 /// Default constructor
2225 Initial size = \ref c_nDefaultInitialSize
2228 - \p c_nDefaultProbesetSize if \p probeset_type is \p cuckoo::list
2229 - \p Capacity if \p probeset_type is <tt> cuckoo::vector<Capacity> </tt>
2231 Probe set threshold = probe set size - 1
2234 : m_nProbesetSize( calc_probeset_size(0))
2235 , m_nProbesetThreshold( m_nProbesetSize - 1 )
2236 , m_MutexPolicy( c_nDefaultInitialSize )
2238 check_common_constraints();
2239 check_probeset_properties();
2241 allocate_bucket_tables( c_nDefaultInitialSize );
2244 /// Constructs the set object with given probe set size and threshold
2246 If probe set type is <tt> cuckoo::vector<Capacity> </tt> vector
2247 then \p nProbesetSize is ignored since it should be equal to vector's \p Capacity.
2250 size_t nInitialSize ///< Initial set size; if 0 - use default initial size \p c_nDefaultInitialSize
2251 , unsigned int nProbesetSize ///< probe set size
2252 , unsigned int nProbesetThreshold = 0 ///< probe set threshold, <tt>nProbesetThreshold < nProbesetSize</tt>. If 0, <tt>nProbesetThreshold = nProbesetSize - 1</tt>
2254 : m_nProbesetSize( calc_probeset_size(nProbesetSize))
2255 , m_nProbesetThreshold( nProbesetThreshold ? nProbesetThreshold : m_nProbesetSize - 1 )
2256 , m_MutexPolicy( cds::beans::ceil2(nInitialSize ? nInitialSize : c_nDefaultInitialSize ))
2258 check_common_constraints();
2259 check_probeset_properties();
2261 allocate_bucket_tables( nInitialSize ? cds::beans::ceil2( nInitialSize ) : c_nDefaultInitialSize );
2264 /// Constructs the set object with given hash functor tuple
2266 The probe set size and threshold are set as default, see \p CuckooSet()
2269 hash_tuple_type const& h ///< hash functor tuple of type <tt>std::tuple<H1, H2, ... Hn></tt> where <tt> n == \ref c_nArity </tt>
2271 : m_nProbesetSize( calc_probeset_size(0))
2272 , m_nProbesetThreshold( m_nProbesetSize -1 )
2274 , m_MutexPolicy( c_nDefaultInitialSize )
2276 check_common_constraints();
2277 check_probeset_properties();
2279 allocate_bucket_tables( c_nDefaultInitialSize );
2282 /// Constructs the set object with given probe set properties and hash functor tuple
2284 If probe set type is <tt> cuckoo::vector<Capacity> </tt> vector
2285 then \p nProbesetSize should be equal to vector's \p Capacity.
2288 size_t nInitialSize ///< Initial set size; if 0 - use default initial size \p c_nDefaultInitialSize
2289 , unsigned int nProbesetSize ///< probe set size, positive integer
2290 , unsigned int nProbesetThreshold ///< probe set threshold, <tt>nProbesetThreshold < nProbesetSize</tt>. If 0, <tt>nProbesetThreshold = nProbesetSize - 1</tt>
2291 , hash_tuple_type const& h ///< hash functor tuple of type <tt>std::tuple<H1, H2, ... Hn></tt> where <tt> n == \ref c_nArity </tt>
2293 : m_nProbesetSize( calc_probeset_size(nProbesetSize))
2294 , m_nProbesetThreshold( nProbesetThreshold ? nProbesetThreshold : m_nProbesetSize - 1)
2296 , m_MutexPolicy( cds::beans::ceil2(nInitialSize ? nInitialSize : c_nDefaultInitialSize ))
2298 check_common_constraints();
2299 check_probeset_properties();
2301 allocate_bucket_tables( nInitialSize ? cds::beans::ceil2( nInitialSize ) : c_nDefaultInitialSize );
2304 /// Constructs the set object with given hash functor tuple (move semantics)
2306 The probe set size and threshold are set as default, see \p CuckooSet()
2309 hash_tuple_type&& h ///< hash functor tuple of type <tt>std::tuple<H1, H2, ... Hn></tt> where <tt> n == \ref c_nArity </tt>
2311 : m_nProbesetSize( calc_probeset_size(0))
2312 , m_nProbesetThreshold( m_nProbesetSize / 2 )
2313 , m_Hash( std::forward<hash_tuple_type>(h))
2314 , m_MutexPolicy( c_nDefaultInitialSize )
2316 check_common_constraints();
2317 check_probeset_properties();
2319 allocate_bucket_tables( c_nDefaultInitialSize );
2322 /// Constructs the set object with given probe set properties and hash functor tuple (move semantics)
2324 If probe set type is <tt> cuckoo::vector<Capacity> </tt> vector
2325 then \p nProbesetSize should be equal to vector's \p Capacity.
2328 size_t nInitialSize ///< Initial set size; if 0 - use default initial size \p c_nDefaultInitialSize
2329 , unsigned int nProbesetSize ///< probe set size, positive integer
2330 , unsigned int nProbesetThreshold ///< probe set threshold, <tt>nProbesetThreshold < nProbesetSize</tt>. If 0, <tt>nProbesetThreshold = nProbesetSize - 1</tt>
2331 , hash_tuple_type&& h ///< hash functor tuple of type <tt>std::tuple<H1, H2, ... Hn></tt> where <tt> n == \ref c_nArity </tt>
2333 : m_nProbesetSize( calc_probeset_size(nProbesetSize))
2334 , m_nProbesetThreshold( nProbesetThreshold ? nProbesetThreshold : m_nProbesetSize - 1)
2335 , m_Hash( std::forward<hash_tuple_type>(h))
2336 , m_MutexPolicy( cds::beans::ceil2(nInitialSize ? nInitialSize : c_nDefaultInitialSize ))
2338 check_common_constraints();
2339 check_probeset_properties();
2341 allocate_bucket_tables( nInitialSize ? cds::beans::ceil2( nInitialSize ) : c_nDefaultInitialSize );
2347 free_bucket_tables();
2351 /// Inserts new node
2353 The function inserts \p val in the set if it does not contain an item with key equal to \p val.
2355 Returns \p true if \p val is inserted into the set, \p false otherwise.
2357 bool insert( value_type& val )
2359 return insert( val, []( value_type& ) {} );
2362 /// Inserts new node
2364 The function allows to split creating of new item into two part:
2365 - create item with key only
2366 - insert new item into the set
2367 - if inserting is success, calls \p f functor to initialize value-field of \p val.
2369 The functor signature is:
2371 void func( value_type& val );
2373 where \p val is the item inserted.
2375 The user-defined functor is called only if the inserting is success.
2377 template <typename Func>
2378 bool insert( value_type& val, Func f )
2381 position arrPos[ c_nArity ];
2382 unsigned int nGoalTable;
2384 hashing( arrHash, val );
2385 node_type * pNode = node_traits::to_node_ptr( val );
2386 store_hash( pNode, arrHash );
2390 scoped_cell_lock guard( m_MutexPolicy, arrHash );
2392 if ( contains( arrPos, arrHash, val, key_predicate()) != c_nUndefTable ) {
2393 m_Stat.onInsertFailed();
2397 for ( unsigned int i = 0; i < c_nArity; ++i ) {
2398 bucket_entry& refBucket = bucket( i, arrHash[i] );
2399 if ( refBucket.size() < m_nProbesetThreshold ) {
2400 refBucket.insert_after( arrPos[i].itPrev, pNode );
2403 m_Stat.onInsertSuccess();
2408 for ( unsigned int i = 0; i < c_nArity; ++i ) {
2409 bucket_entry& refBucket = bucket( i, arrHash[i] );
2410 if ( refBucket.size() < m_nProbesetSize ) {
2411 refBucket.insert_after( arrPos[i].itPrev, pNode );
2415 assert( refBucket.size() > 1 );
2416 copy_hash( arrHash, *node_traits::to_value_ptr( *refBucket.begin()));
2422 m_Stat.onInsertResize();
2427 m_Stat.onInsertRelocate();
2428 if ( !relocate( nGoalTable, arrHash )) {
2429 m_Stat.onInsertRelocateFault();
2430 m_Stat.onInsertResize();
2434 m_Stat.onInsertSuccess();
2438 /// Updates the node
2440 The operation performs inserting or changing data with lock-free manner.
2442 If the item \p val is not found in the set, then \p val is inserted into the set
2443 iff \p bAllowInsert is \p true.
2444 Otherwise, the functor \p func is called with item found.
2445 The functor \p func signature is:
2447 void func( bool bNew, value_type& item, value_type& val );
2450 - \p bNew - \p true if the item has been inserted, \p false otherwise
2451 - \p item - item of the set
2452 - \p val - argument \p val passed into the \p %update() function
2453 If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
2454 refer to the same thing.
2456 The functor may change non-key fields of the \p item.
2458 Returns std::pair<bool, bool> where \p first is \p true if operation is successful,
2459 i.e. the node has been inserted or updated,
2460 \p second is \p true if new item has been added or \p false if the item with \p key
2463 template <typename Func>
2464 std::pair<bool, bool> update( value_type& val, Func func, bool bAllowInsert = true )
2467 position arrPos[ c_nArity ];
2468 unsigned int nGoalTable;
2470 hashing( arrHash, val );
2471 node_type * pNode = node_traits::to_node_ptr( val );
2472 store_hash( pNode, arrHash );
2476 scoped_cell_lock guard( m_MutexPolicy, arrHash );
2478 unsigned int nTable = contains( arrPos, arrHash, val, key_predicate());
2479 if ( nTable != c_nUndefTable ) {
2480 func( false, *node_traits::to_value_ptr( *arrPos[nTable].itFound ), val );
2481 m_Stat.onUpdateExist();
2482 return std::make_pair( true, false );
2485 if ( !bAllowInsert )
2486 return std::make_pair( false, false );
2488 //node_type * pNode = node_traits::to_node_ptr( val );
2489 //store_hash( pNode, arrHash );
2491 for ( unsigned int i = 0; i < c_nArity; ++i ) {
2492 bucket_entry& refBucket = bucket( i, arrHash[i] );
2493 if ( refBucket.size() < m_nProbesetThreshold ) {
2494 refBucket.insert_after( arrPos[i].itPrev, pNode );
2495 func( true, val, val );
2497 m_Stat.onUpdateSuccess();
2498 return std::make_pair( true, true );
2502 for ( unsigned int i = 0; i < c_nArity; ++i ) {
2503 bucket_entry& refBucket = bucket( i, arrHash[i] );
2504 if ( refBucket.size() < m_nProbesetSize ) {
2505 refBucket.insert_after( arrPos[i].itPrev, pNode );
2506 func( true, val, val );
2509 assert( refBucket.size() > 1 );
2510 copy_hash( arrHash, *node_traits::to_value_ptr( *refBucket.begin()));
2516 m_Stat.onUpdateResize();
2521 m_Stat.onUpdateRelocate();
2522 if ( !relocate( nGoalTable, arrHash )) {
2523 m_Stat.onUpdateRelocateFault();
2524 m_Stat.onUpdateResize();
2528 m_Stat.onUpdateSuccess();
2529 return std::make_pair( true, true );
2532 template <typename Func>
2533 CDS_DEPRECATED("ensure() is deprecated, use update()")
2534 std::pair<bool, bool> ensure( value_type& val, Func func )
2536 return update( val, func, true );
2540 /// Unlink the item \p val from the set
2542 The function searches the item \p val in the set and unlink it
2543 if it is found and is equal to \p val (here, the equality means that
2544 \p val belongs to the set: if \p item is an item found then
2545 unlink is successful iif <tt>&val == &item</tt>)
2547 The function returns \p true if success and \p false otherwise.
2549 bool unlink( value_type& val )
2552 hashing( arrHash, val );
2553 position arrPos[ c_nArity ];
2556 scoped_cell_lock guard( m_MutexPolicy, arrHash );
2558 unsigned int nTable = contains( arrPos, arrHash, val, key_predicate());
2559 if ( nTable != c_nUndefTable && node_traits::to_value_ptr(*arrPos[nTable].itFound) == &val ) {
2560 bucket( nTable, arrHash[nTable]).remove( arrPos[nTable].itPrev, arrPos[nTable].itFound );
2562 m_Stat.onUnlinkSuccess();
2567 m_Stat.onUnlinkFailed();
2571 /// Deletes the item from the set
2572 /** \anchor cds_intrusive_CuckooSet_erase
2573 The function searches an item with key equal to \p val in the set,
2574 unlinks it from the set, and returns a pointer to unlinked item.
2576 If the item with key equal to \p val is not found the function return \p nullptr.
2578 Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
2580 template <typename Q>
2581 value_type * erase( Q const& val )
2583 return erase( val, [](value_type const&) {} );
2586 /// Deletes the item from the set using \p pred predicate for searching
2588 The function is an analog of \ref cds_intrusive_CuckooSet_erase "erase(Q const&)"
2589 but \p pred is used for key comparing.
2590 If cuckoo set is ordered, then \p Predicate should have the interface and semantics like \p std::less.
2591 If cuckoo set is unordered, then \p Predicate should have the interface and semantics like \p std::equal_to.
2592 \p Predicate must imply the same element order as the comparator used for building the set.
2594 template <typename Q, typename Predicate>
2595 value_type * erase_with( Q const& val, Predicate pred )
2598 return erase_( val, typename predicate_wrapper<Predicate>::type(), [](value_type const&) {} );
2601 /// Delete the item from the set
2602 /** \anchor cds_intrusive_CuckooSet_erase_func
2603 The function searches an item with key equal to \p val in the set,
2604 call \p f functor with item found, unlinks it from the set, and returns a pointer to unlinked item.
2606 The \p Func interface is
2609 void operator()( value_type const& item );
2613 If the item with key equal to \p val is not found the function return \p nullptr.
2615 Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
2617 template <typename Q, typename Func>
2618 value_type * erase( Q const& val, Func f )
2620 return erase_( val, key_predicate(), f );
2623 /// Deletes the item from the set using \p pred predicate for searching
2625 The function is an analog of \ref cds_intrusive_CuckooSet_erase_func "erase(Q const&, Func)"
2626 but \p pred is used for key comparing.
2627 If you use ordered cuckoo set, then \p Predicate should have the interface and semantics like \p std::less.
2628 If you use unordered cuckoo set, then \p Predicate should have the interface and semantics like \p std::equal_to.
2629 \p Predicate must imply the same element order as the comparator used for building the set.
2631 template <typename Q, typename Predicate, typename Func>
2632 value_type * erase_with( Q const& val, Predicate pred, Func f )
2635 return erase_( val, typename predicate_wrapper<Predicate>::type(), f );
2638 /// Find the key \p val
2639 /** \anchor cds_intrusive_CuckooSet_find_func
2640 The function searches the item with key equal to \p val and calls the functor \p f for item found.
2641 The interface of \p Func functor is:
2644 void operator()( value_type& item, Q& val );
2647 where \p item is the item found, \p val is the <tt>find</tt> function argument.
2649 The functor may change non-key fields of \p item.
2651 The \p val argument is non-const since it can be used as \p f functor destination i.e., the functor
2652 may modify both arguments.
2654 Note the hash functor specified for class \p Traits template parameter
2655 should accept a parameter of type \p Q that can be not the same as \p value_type.
2657 The function returns \p true if \p val is found, \p false otherwise.
2659 template <typename Q, typename Func>
2660 bool find( Q& val, Func f )
2662 return find_( val, key_predicate(), f );
2665 template <typename Q, typename Func>
2666 bool find( Q const& val, Func f )
2668 return find_( val, key_predicate(), f );
2672 /// Find the key \p val using \p pred predicate for comparing
2674 The function is an analog of \ref cds_intrusive_CuckooSet_find_func "find(Q&, Func)"
2675 but \p pred is used for key comparison.
2676 If you use ordered cuckoo set, then \p Predicate should have the interface and semantics like \p std::less.
2677 If you use unordered cuckoo set, then \p Predicate should have the interface and semantics like \p std::equal_to.
2678 \p pred must imply the same element order as the comparator used for building the set.
2680 template <typename Q, typename Predicate, typename Func>
2681 bool find_with( Q& val, Predicate pred, Func f )
2684 return find_( val, typename predicate_wrapper<Predicate>::type(), f );
2687 template <typename Q, typename Predicate, typename Func>
2688 bool find_with( Q const& val, Predicate pred, Func f )
2691 return find_( val, typename predicate_wrapper<Predicate>::type(), f );
2695 /// Checks whether the set contains \p key
2697 The function searches the item with key equal to \p key
2698 and returns \p true if it is found, and \p false otherwise.
2700 template <typename Q>
2701 bool contains( Q const& key )
2703 return find( key, [](value_type&, Q const& ) {} );
2706 template <typename Q>
2707 CDS_DEPRECATED("deprecated, use contains()")
2708 bool find( Q const& key )
2710 return contains( key );
2714 /// Checks whether the set contains \p key using \p pred predicate for searching
2716 The function is similar to <tt>contains( key )</tt> but \p pred is used for key comparing.
2717 If the set is unordered, \p Predicate has semantics like \p std::equal_to.
2718 For ordered set \p Predicate has \p std::less semantics. In that case \p pred
2719 must imply the same element order as the comparator used for building the set.
2721 template <typename Q, typename Predicate>
2722 bool contains( Q const& key, Predicate pred )
2725 return find_with( key, typename predicate_wrapper<Predicate>::type(), [](value_type& , Q const& ) {} );
2728 template <typename Q, typename Predicate>
2729 CDS_DEPRECATED("deprecated, use contains()")
2730 bool find_with( Q const& key, Predicate pred )
2732 return contains( key, pred );
2738 The function unlinks all items from the set.
2739 For any item <tt> @ref disposer</tt> is called
2743 clear_and_dispose( disposer());
2746 /// Clears the set and calls \p disposer for each item
2748 The function unlinks all items from the set calling \p oDisposer for each item.
2749 \p Disposer functor interface is:
2752 void operator()( value_type * p );
2756 The <tt> @ref disposer</tt> specified in \p Traits is not called.
2758 template <typename Disposer>
2759 void clear_and_dispose( Disposer oDisposer )
2761 // locks entire array
2762 scoped_full_lock sl( m_MutexPolicy );
2764 for ( unsigned int i = 0; i < c_nArity; ++i ) {
2765 bucket_entry * pEntry = m_BucketTable[i];
2766 bucket_entry * pEnd = pEntry + m_nBucketMask + 1;
2767 for ( ; pEntry != pEnd ; ++pEntry ) {
2768 pEntry->clear( [&oDisposer]( node_type * pNode ){ oDisposer( node_traits::to_value_ptr( pNode )) ; } );
2771 m_ItemCounter.reset();
2774 /// Checks if the set is empty
2776 Emptiness is checked by item counting: if item count is zero then the set is empty.
2783 /// Returns item count in the set
2786 return m_ItemCounter;
2789 /// Returns the size of hash table
2791 The hash table size is non-constant and can be increased via resizing.
2793 size_t bucket_count() const
2795 return m_nBucketMask + 1;
2798 /// Returns lock array size
2799 size_t lock_count() const
2801 return m_MutexPolicy.lock_count();
2804 /// Returns const reference to internal statistics
2805 stat const& statistics() const
2810 /// Returns const reference to mutex policy internal statistics
2811 typename mutex_policy::statistics_type const& mutex_policy_statistics() const
2813 return m_MutexPolicy.statistics();
2816 }} // namespace cds::intrusive
2818 #endif // #ifndef CDSLIB_INTRUSIVE_CUCKOO_SET_H