3 #ifndef __CDS_INTRUSIVE_CUCKOO_SET_H
4 #define __CDS_INTRUSIVE_CUCKOO_SET_H
9 #include <functional> // ref
10 #include <cds/intrusive/details/base.h>
11 #include <cds/opt/compare.h>
12 #include <cds/opt/hash.h>
13 #include <cds/lock/array.h>
14 #include <cds/os/thread.h>
15 #include <cds/lock/spinlock.h>
18 namespace cds { namespace intrusive {
20 /// CuckooSet-related definitions
23 /// Option to define probeset type
25 The option specifies probeset type for the CuckooSet.
27 - \p cds::intrusive::cuckoo::list - the probeset is a single-linked list.
28 The node contains pointer to next node in probeset.
29 - \p cds::intrusive::cuckoo::vector<Capacity> - the probeset is a vector
30 with constant-size \p Capacity where \p Capacity is an <tt>unsigned int</tt> constant.
31 The node does not contain any auxiliary data.
33 template <typename Type>
37 template <typename Base>
38 struct pack: public Base {
39 typedef Type probeset_type;
44 /// Option specifying whether to store hash values in the node
46 This option reserves additional space in the hook to store the hash value of the object once it's introduced in the container.
47 When this option is used, the unordered container will store the calculated hash value in the hook and rehashing operations won't need
48 to recalculate the hash of the value. This option will improve the performance of unordered containers
49 when rehashing is frequent or hashing the value is a slow operation
51 The \p Count template parameter defines the size of hash array. Remember that cuckoo hashing implies at least two
54 Possible values of \p Count:
55 - 0 - no hash storing in the node
56 - greater that 1 - store hash values.
58 Value 1 is deprecated.
60 template <unsigned int Count>
64 template <typename Base>
65 struct pack: public Base {
66 static unsigned int const store_hash = Count;
73 // Probeset type placeholders
74 struct list_probeset_class;
75 struct vector_probeset_class;
79 // Probeset type declarations.
81 template <unsigned int Capacity>
84 static unsigned int const c_nCapacity = Capacity;
91 - \p ProbesetType - type of probeset. Can be \p cds::intrusive::cuckoo::list
92 or \p cds::intrusive::cuckoo::vector<Capacity>.
93 - \p StoreHashCount - constant that defines whether to store node hash values.
94 See cuckoo::store_hash option for explanation
95 - Tag - a tag used to distinguish between different implementation when two or more
96 \p node is needed in single struct.
98 template <typename ProbesetType = cuckoo::list, unsigned int StoreHashCount = 0, typename Tag = opt::none>
100 #ifdef CDS_DOXYGEN_INVOKED
102 typedef ProbesetType probeset_type ; ///< Probeset type
103 typedef Tag tag ; ///< Tag
104 static unsigned int const hash_array_size = StoreHashCount ; ///< The size of hash array
110 template <typename Tag>
111 struct node< cuckoo::list, 0, Tag>
113 typedef list_probeset_class probeset_class;
114 typedef cuckoo::list probeset_type;
116 static unsigned int const hash_array_size = 0;
117 static unsigned int const probeset_size = 0;
121 CDS_CONSTEXPR node() CDS_NOEXCEPT
125 void store_hash( size_t * )
128 size_t * get_hash() const
130 // This node type does not store hash values!!!
141 template <unsigned int StoreHashCount, typename Tag>
142 struct node< cuckoo::list, StoreHashCount, Tag>
144 typedef list_probeset_class probeset_class;
145 typedef cuckoo::list probeset_type;
147 static unsigned int const hash_array_size = StoreHashCount;
148 static unsigned int const probeset_size = 0;
151 size_t m_arrHash[ hash_array_size ];
156 memset( m_arrHash, 0, sizeof(m_arrHash));
159 void store_hash( size_t * pHashes )
161 memcpy( m_arrHash, pHashes, hash_array_size );
164 size_t * get_hash() const
166 return const_cast<size_t *>( m_arrHash );
176 template <unsigned int VectorSize, typename Tag>
177 struct node< cuckoo::vector<VectorSize>, 0, Tag>
179 typedef vector_probeset_class probeset_class;
180 typedef cuckoo::vector<VectorSize> probeset_type;
182 static unsigned int const hash_array_size = 0;
183 static unsigned int const probeset_size = probeset_type::c_nCapacity;
188 void store_hash( size_t * )
191 size_t * get_hash() const
193 // This node type does not store hash values!!!
202 template <unsigned int VectorSize, unsigned int StoreHashCount, typename Tag>
203 struct node< cuckoo::vector<VectorSize>, StoreHashCount, Tag>
205 typedef vector_probeset_class probeset_class;
206 typedef cuckoo::vector<VectorSize> probeset_type;
208 static unsigned int const hash_array_size = StoreHashCount;
209 static unsigned int const probeset_size = probeset_type::c_nCapacity;
211 size_t m_arrHash[ hash_array_size ];
215 memset( m_arrHash, 0, sizeof(m_arrHash));
218 void store_hash( size_t * pHashes )
220 memcpy( m_arrHash, pHashes, hash_array_size );
223 size_t * get_hash() const
225 return const_cast<size_t *>( m_arrHash );
235 struct default_hook {
236 typedef cuckoo::list probeset_type;
237 static unsigned int const store_hash = 0;
238 typedef opt::none tag;
241 template < typename HookType, typename... Options>
244 typedef typename opt::make_options< default_hook, Options...>::type options;
246 typedef typename options::probeset_type probeset_type;
247 typedef typename options::tag tag;
248 static unsigned int const store_hash = options::store_hash;
250 typedef node<probeset_type, store_hash, tag> node_type;
252 typedef HookType hook_type;
259 - cuckoo::probeset_type - probeset type. Defaul is \p cuckoo::list
260 - cuckoo::store_hash - store hash values in the node or not. Default is 0 (no storing)
261 - opt::tag - tag to distinguish different nodes in one struct. Default is opt::none
263 template < typename... Options >
264 struct base_hook: public hook< opt::base_hook_tag, Options... >
269 \p MemberOffset defines offset in bytes of \ref node member into your structure.
270 Use \p offsetof macro to define \p MemberOffset
273 - cuckoo::probeset_type - probeset type. Defaul is \p cuckoo::list
274 - cuckoo::store_hash - store hash values in the node or not. Default is 0 (no storing)
275 - opt::tag - tag to distinguish different nodes in one struct. Default is opt::none
277 template < size_t MemberOffset, typename... Options >
278 struct member_hook: public hook< opt::member_hook_tag, Options... >
281 static const size_t c_nMemberOffset = MemberOffset;
287 \p NodeTraits defines type traits for node.
288 See \ref node_traits for \p NodeTraits interface description
291 - cuckoo::probeset_type - probeset type. Defaul is \p cuckoo::list
292 - cuckoo::store_hash - store hash values in the node or not. Default is 0 (no storing)
293 - opt::tag - tag to distinguish different nodes in one struct. Default is opt::none
295 template <typename NodeTraits, typename... Options >
296 struct traits_hook: public hook< opt::traits_hook_tag, Options... >
299 typedef NodeTraits node_traits;
303 /// Internal statistics for \ref striping mutex policy
304 struct striping_stat {
305 typedef cds::atomicity::event_counter counter_type; ///< Counter type
307 counter_type m_nCellLockCount ; ///< Count of obtaining cell lock
308 counter_type m_nCellTryLockCount ; ///< Count of cell \p try_lock attempts
309 counter_type m_nFullLockCount ; ///< Count of obtaining full lock
310 counter_type m_nResizeLockCount ; ///< Count of obtaining resize lock
311 counter_type m_nResizeCount ; ///< Count of resize event
314 void onCellLock() { ++m_nCellLockCount; }
315 void onCellTryLock() { ++m_nCellTryLockCount; }
316 void onFullLock() { ++m_nFullLockCount; }
317 void onResizeLock() { ++m_nResizeLockCount; }
318 void onResize() { ++m_nResizeCount; }
322 /// Dummy internal statistics for \ref striping mutex policy
323 struct empty_striping_stat {
325 void onCellLock() const {}
326 void onCellTryLock() const {}
327 void onFullLock() const {}
328 void onResizeLock() const {}
329 void onResize() const {}
333 /// Lock striping concurrent access policy
335 This is one of available opt::mutex_policy option type for CuckooSet
337 Lock striping is very simple technique.
338 The cuckoo set consists of the bucket tables and the array of locks.
339 There is single lock array for each bucket table, at least, the count of bucket table is 2.
340 Initially, the capacity of lock array and each bucket table is the same.
341 When set is resized, bucket table capacity will be doubled but lock array will not.
342 The lock \p i protects each bucket \p j, where <tt> j = i mod L </tt>,
343 where \p L - the size of lock array.
345 The policy contains an internal array of \p RecursiveLock locks.
348 - \p RecursiveLock - the type of recursive mutex. The default is \p std::recursive_mutex. The mutex type should be default-constructible.
349 Note that a recursive spin-lock is not suitable for lock striping for performance reason.
350 - \p Arity - unsigned int constant that specifies an arity. The arity is the count of hash functors, i.e., the
351 count of lock arrays. Default value is 2.
352 - \p Alloc - allocator type used for lock array memory allocation. Default is \p CDS_DEFAULT_ALLOCATOR.
353 - \p Stat - internal statistics type. Note that this template argument is automatically selected by \ref CuckooSet
354 class according to its \p opt::stat option.
357 class RecursiveLock = std::recursive_mutex,
358 unsigned int Arity = 2,
359 class Alloc = CDS_DEFAULT_ALLOCATOR,
360 class Stat = empty_striping_stat
365 typedef RecursiveLock lock_type ; ///< lock type
366 typedef Alloc allocator_type ; ///< allocator type
367 static unsigned int const c_nArity = Arity ; ///< the arity
368 typedef Stat statistics_type ; ///< Internal statistics type (\ref striping_stat or \ref empty_striping_stat)
371 typedef striping_stat real_stat;
372 typedef empty_striping_stat empty_stat;
374 template <typename Stat2>
375 struct rebind_statistics {
376 typedef striping<lock_type, c_nArity, allocator_type, Stat2> other;
380 typedef cds::lock::array< lock_type, cds::lock::pow2_select_policy, allocator_type > lock_array_type ; ///< lock array type
384 class lock_array: public lock_array_type
388 lock_array(): lock_array_type( typename lock_array_type::select_cell_policy(2) ) {}
391 lock_array( size_t nCapacity ): lock_array_type( nCapacity, typename lock_array_type::select_cell_policy(nCapacity) ) {}
394 class scoped_lock: public std::unique_lock< lock_array_type >
396 typedef std::unique_lock< lock_array_type > base_class;
398 scoped_lock( lock_array& arrLock, size_t nHash ): base_class( arrLock, nHash ) {}
404 lock_array m_Locks[c_nArity] ; ///< array of lock_array_type
405 statistics_type m_Stat ; ///< internal statistics
410 class scoped_cell_lock {
411 lock_type * m_guard[c_nArity];
414 scoped_cell_lock( striping& policy, size_t const* arrHash )
416 for ( unsigned int i = 0; i < c_nArity; ++i ) {
417 m_guard[i] = &( policy.m_Locks[i].at( policy.m_Locks[i].lock( arrHash[i] )));
419 policy.m_Stat.onCellLock();
424 for ( unsigned int i = 0; i < c_nArity; ++i )
425 m_guard[i]->unlock();
429 class scoped_cell_trylock
431 typedef typename lock_array_type::lock_type lock_type;
433 lock_type * m_guard[c_nArity];
437 scoped_cell_trylock( striping& policy, size_t const* arrHash )
439 size_t nCell = policy.m_Locks[0].try_lock( arrHash[0] );
440 m_bLocked = nCell != lock_array_type::c_nUnspecifiedCell;
442 m_guard[0] = &(policy.m_Locks[0].at(nCell));
443 for ( unsigned int i = 1; i < c_nArity; ++i ) {
444 m_guard[i] = &( policy.m_Locks[i].at( policy.m_Locks[i].lock( arrHash[i] )) );
448 std::fill( m_guard, m_guard + c_nArity, nullptr );
450 policy.m_Stat.onCellTryLock();
452 ~scoped_cell_trylock()
455 for ( unsigned int i = 0; i < c_nArity; ++i )
456 m_guard[i]->unlock();
466 class scoped_full_lock {
467 std::unique_lock< lock_array_type > m_guard;
469 scoped_full_lock( striping& policy )
470 : m_guard( policy.m_Locks[0] )
472 policy.m_Stat.onFullLock();
475 /// Ctor for scoped_resize_lock - no statistics is incremented
476 scoped_full_lock( striping& policy, bool )
477 : m_guard( policy.m_Locks[0] )
481 class scoped_resize_lock: public scoped_full_lock {
483 scoped_resize_lock( striping& policy )
484 : scoped_full_lock( policy, false )
486 policy.m_Stat.onResizeLock();
494 size_t nLockCount ///< The size of lock array. Must be power of two.
497 // Trick: initialize the array of locks
498 for ( unsigned int i = 0; i < c_nArity; ++i ) {
499 lock_array * pArr = m_Locks + i;
500 pArr->lock_array::~lock_array();
501 new ( pArr ) lock_array( nLockCount );
505 /// Returns lock array size
507 Lock array size is unchanged during \p striping object lifetime
509 size_t lock_count() const
511 return m_Locks[0].size();
515 void resize( size_t )
521 /// Returns the arity of striping mutex policy
522 CDS_CONSTEXPR unsigned int arity() const CDS_NOEXCEPT
527 /// Returns internal statistics
528 statistics_type const& statistics() const
534 /// Internal statistics for \ref refinable mutex policy
535 struct refinable_stat {
536 typedef cds::atomicity::event_counter counter_type ; ///< Counter type
538 counter_type m_nCellLockCount ; ///< Count of obtaining cell lock
539 counter_type m_nCellLockWaitResizing ; ///< Count of loop iteration to wait for resizing
540 counter_type m_nCellLockArrayChanged ; ///< Count of event "Lock array has been changed when obtaining cell lock"
541 counter_type m_nCellLockFailed ; ///< Count of event "Cell lock failed because of the array is owned by other thread"
543 counter_type m_nSecondCellLockCount ; ///< Count of obtaining cell lock when another cell is already locked
544 counter_type m_nSecondCellLockFailed ; ///< Count of unsuccess obtaining cell lock when another cell is already locked
546 counter_type m_nFullLockCount ; ///< Count of obtaining full lock
547 counter_type m_nFullLockIter ; ///< Count of unsuccessfull iteration to obtain full lock
549 counter_type m_nResizeLockCount ; ///< Count of obtaining resize lock
550 counter_type m_nResizeLockIter ; ///< Count of unsuccessfull iteration to obtain resize lock
551 counter_type m_nResizeLockArrayChanged; ///< Count of event "Lock array has been changed when obtaining resize lock"
552 counter_type m_nResizeCount ; ///< Count of resize event
555 void onCellLock() { ++m_nCellLockCount; }
556 void onCellWaitResizing() { ++m_nCellLockWaitResizing; }
557 void onCellArrayChanged() { ++m_nCellLockArrayChanged; }
558 void onCellLockFailed() { ++m_nCellLockFailed; }
559 void onSecondCellLock() { ++m_nSecondCellLockCount; }
560 void onSecondCellLockFailed() { ++m_nSecondCellLockFailed; }
561 void onFullLock() { ++m_nFullLockCount; }
562 void onFullLockIter() { ++m_nFullLockIter; }
563 void onResizeLock() { ++m_nResizeLockCount; }
564 void onResizeLockIter() { ++m_nResizeLockIter; }
565 void onResizeLockArrayChanged() { ++m_nResizeLockArrayChanged; }
566 void onResize() { ++m_nResizeCount; }
570 /// Dummy internal statistics for \ref refinable mutex policy
571 struct empty_refinable_stat {
573 void onCellLock() const {}
574 void onCellWaitResizing() const {}
575 void onCellArrayChanged() const {}
576 void onCellLockFailed() const {}
577 void onSecondCellLock() const {}
578 void onSecondCellLockFailed() const {}
579 void onFullLock() const {}
580 void onFullLockIter() const {}
581 void onResizeLock() const {}
582 void onResizeLockIter() const {}
583 void onResizeLockArrayChanged() const {}
584 void onResize() const {}
588 /// Refinable concurrent access policy
590 This is one of available opt::mutex_policy option type for CuckooSet
592 Refining is like a striping technique (see cuckoo::striping)
593 but it allows growing the size of lock array when resizing the hash table.
594 So, the sizes of hash table and lock array are equal.
597 - \p RecursiveLock - the type of mutex. Reentrant (recursive) mutex is required.
598 The default is \p std::recursive_mutex. The mutex type should be default-constructible.
599 - \p Arity - unsigned int constant that specifies an arity. The arity is the count of hash functors, i.e., the
600 count of lock arrays. Default value is 2.
601 - \p BackOff - back-off strategy. Default is cds::backoff::yield
602 - \p Alloc - allocator type used for lock array memory allocation. Default is \p CDS_DEFAULT_ALLOCATOR.
603 - \p Stat - internal statistics type. Note that this template argument is automatically selected by \ref CuckooSet
604 class according to its \p opt::stat option.
607 class RecursiveLock = std::recursive_mutex,
608 unsigned int Arity = 2,
609 typename BackOff = cds::backoff::yield,
610 class Alloc = CDS_DEFAULT_ALLOCATOR,
611 class Stat = empty_refinable_stat
616 typedef RecursiveLock lock_type ; ///< lock type
617 typedef Alloc allocator_type ; ///< allocator type
618 typedef BackOff back_off ; ///< back-off strategy
619 typedef Stat statistics_type ; ///< internal statistics type
620 static unsigned int const c_nArity = Arity; ///< the arity
623 typedef refinable_stat real_stat;
624 typedef empty_refinable_stat empty_stat;
626 template <typename Stat2>
627 struct rebind_statistics {
628 typedef refinable< lock_type, c_nArity, back_off, allocator_type, Stat2> other;
634 typedef cds::lock::trivial_select_policy lock_selection_policy;
636 class lock_array_type
637 : public cds::lock::array< lock_type, lock_selection_policy, allocator_type >
638 , public std::enable_shared_from_this< lock_array_type >
640 typedef cds::lock::array< lock_type, lock_selection_policy, allocator_type > lock_array_base;
642 lock_array_type( size_t nCapacity )
643 : lock_array_base( nCapacity )
646 typedef std::shared_ptr< lock_array_type > lock_array_ptr;
647 typedef cds::details::Allocator< lock_array_type, allocator_type > lock_array_allocator;
649 typedef unsigned long long owner_t;
650 typedef cds::OS::ThreadId threadId_t;
652 typedef cds::lock::Spin spinlock_type;
653 typedef std::unique_lock< spinlock_type > scoped_spinlock;
658 static owner_t const c_nOwnerMask = (((owner_t) 1) << (sizeof(owner_t) * 8 - 1)) - 1;
660 atomics::atomic< owner_t > m_Owner ; ///< owner mark (thread id + boolean flag)
661 atomics::atomic<size_t> m_nCapacity ; ///< lock array capacity
662 lock_array_ptr m_arrLocks[ c_nArity ] ; ///< Lock array. The capacity of array is specified in constructor.
663 spinlock_type m_access ; ///< access to m_arrLocks
664 statistics_type m_Stat ; ///< internal statistics
669 struct lock_array_disposer {
670 void operator()( lock_array_type * pArr )
672 lock_array_allocator().Delete( pArr );
676 lock_array_ptr create_lock_array( size_t nCapacity )
678 return lock_array_ptr( lock_array_allocator().New( nCapacity ), lock_array_disposer() );
681 void acquire( size_t const * arrHash, lock_array_ptr * pLockArr, lock_type ** parrLock )
683 owner_t me = (owner_t) cds::OS::getCurrentThreadId();
690 scoped_spinlock sl(m_access);
691 for ( unsigned int i = 0; i < c_nArity; ++i )
692 pLockArr[i] = m_arrLocks[i];
695 // wait while resizing
697 who = m_Owner.load( atomics::memory_order_acquire );
698 if ( !( who & 1 ) || (who >> 1) == (me & c_nOwnerMask) )
701 m_Stat.onCellWaitResizing();
704 if ( pLockArr[0] != m_arrLocks[0] ) {
705 m_Stat.onCellArrayChanged();
709 size_t const nMask = pLockArr[0]->size() - 1;
710 assert( cds::beans::is_power2( nMask + 1 ));
712 for ( unsigned int i = 0; i < c_nArity; ++i ) {
713 parrLock[i] = &( pLockArr[i]->at( arrHash[i] & nMask ));
717 who = m_Owner.load( atomics::memory_order_acquire );
718 if ( ( !(who & 1) || (who >> 1) == (me & c_nOwnerMask) ) && m_arrLocks[0] == pLockArr[0] ) {
723 for ( unsigned int i = 0; i < c_nArity; ++i ) {
724 parrLock[i]->unlock();
727 m_Stat.onCellLockFailed();
730 // clears pLockArr can lead to calling dtor for each item of pLockArr[i] that may be a heavy-weighted operation
731 // (each pLockArr[i] is a shared pointer to array of a ton of mutexes)
732 // It is better to do this before the next loop iteration where we will use spin-locked assignment to pLockArr
733 // Destructing a lot of mutexes under spin-lock is a bad solution
734 for ( unsigned int i = 0; i < c_nArity; ++i )
739 bool try_second_acquire( size_t const * arrHash, lock_type ** parrLock )
741 // It is assumed that the current thread already has a lock
742 // and requires a second lock for other hash
744 size_t const nMask = m_nCapacity.load(atomics::memory_order_acquire) - 1;
745 size_t nCell = m_arrLocks[0]->try_lock( arrHash[0] & nMask);
746 if ( nCell == lock_array_type::c_nUnspecifiedCell ) {
747 m_Stat.onSecondCellLockFailed();
750 parrLock[0] = &(m_arrLocks[0]->at(nCell));
752 for ( unsigned int i = 1; i < c_nArity; ++i ) {
753 parrLock[i] = &( m_arrLocks[i]->at( m_arrLocks[i]->lock( arrHash[i] & nMask)) );
756 m_Stat.onSecondCellLock();
762 owner_t me = (owner_t) cds::OS::getCurrentThreadId();
767 if ( m_Owner.compare_exchange_strong( ownNull, (me << 1) | 1, atomics::memory_order_acq_rel, atomics::memory_order_relaxed )) {
768 m_arrLocks[0]->lock_all();
774 m_Stat.onFullLockIter();
780 m_arrLocks[0]->unlock_all();
781 m_Owner.store( 0, atomics::memory_order_release );
784 void acquire_resize( lock_array_ptr * pOldLocks )
786 owner_t me = (owner_t) cds::OS::getCurrentThreadId();
790 scoped_spinlock sl(m_access);
791 for ( unsigned int i = 0; i < c_nArity; ++i )
792 pOldLocks[i] = m_arrLocks[i];
797 if ( m_Owner.compare_exchange_strong( ownNull, (me << 1) | 1, atomics::memory_order_acq_rel, atomics::memory_order_relaxed )) {
798 if ( pOldLocks[0] != m_arrLocks[0] ) {
799 m_Owner.store( 0, atomics::memory_order_release );
800 m_Stat.onResizeLockArrayChanged();
803 pOldLocks[0]->lock_all();
804 m_Stat.onResizeLock();
809 m_Stat.onResizeLockIter();
811 // clears pOldLocks can lead to calling dtor for each item of pOldLocks[i] that may be a heavy-weighted operation
812 // (each pOldLocks[i] is a shared pointer to array of a ton of mutexes)
813 // It is better to do this before the next loop iteration where we will use spin-locked assignment to pOldLocks
814 // Destructing a lot of mutexes under spin-lock is a bad solution
815 for ( unsigned int i = 0; i < c_nArity; ++i )
816 pOldLocks[i].reset();
820 void release_resize( lock_array_ptr * pOldLocks )
822 m_Owner.store( 0, atomics::memory_order_release );
823 pOldLocks[0]->unlock_all();
829 class scoped_cell_lock {
830 lock_type * m_arrLock[ c_nArity ];
831 lock_array_ptr m_arrLockArr[ c_nArity ];
834 scoped_cell_lock( refinable& policy, size_t const* arrHash )
836 policy.acquire( arrHash, m_arrLockArr, m_arrLock );
841 for ( unsigned int i = 0; i < c_nArity; ++i )
842 m_arrLock[i]->unlock();
846 class scoped_cell_trylock {
847 lock_type * m_arrLock[ c_nArity ];
851 scoped_cell_trylock( refinable& policy, size_t const* arrHash )
853 m_bLocked = policy.try_second_acquire( arrHash, m_arrLock );
856 ~scoped_cell_trylock()
859 for ( unsigned int i = 0; i < c_nArity; ++i )
860 m_arrLock[i]->unlock();
870 class scoped_full_lock {
873 scoped_full_lock( refinable& policy )
876 policy.acquire_all();
880 m_policy.release_all();
884 class scoped_resize_lock
887 lock_array_ptr m_arrLocks[ c_nArity ];
889 scoped_resize_lock( refinable& policy )
892 policy.acquire_resize( m_arrLocks );
894 ~scoped_resize_lock()
896 m_policy.release_resize( m_arrLocks );
904 size_t nLockCount ///< The size of lock array. Must be power of two.
906 , m_nCapacity( nLockCount )
908 assert( cds::beans::is_power2( nLockCount ));
909 for ( unsigned int i = 0; i < c_nArity; ++i )
910 m_arrLocks[i] = create_lock_array( nLockCount );
914 void resize( size_t nCapacity )
916 lock_array_ptr pNew[ c_nArity ];
917 for ( unsigned int i = 0; i < c_nArity; ++i )
918 pNew[i] = create_lock_array( nCapacity );
921 // Assignment m_arrLocks[i] = pNew[i] may call heavy-weighted dtor for each item of m_arrLocks
922 // that is unacceptable under spin-lock
923 // So, we store copy of m_arrLocks in pOld
924 lock_array_ptr pOld[ c_nArity ];
925 for ( unsigned int i = 0; i < c_nArity; ++i )
926 pOld[i] = m_arrLocks[i];
928 // m_arrLocks assignment will not lead to calling dtor of each item of m_arrLocks
929 // since copy of m_arrLocks locates in pOld and assignment will not be too painful for spin-lock
933 scoped_spinlock sl(m_access);
934 for ( unsigned int i = 0; i < c_nArity; ++i )
935 m_arrLocks[i] = pNew[i];
937 m_nCapacity.store( nCapacity, atomics::memory_order_release );
943 /// Returns lock array size
945 Lock array size is not a constant for \p refinable policy and can be changed when the set is resized.
947 size_t lock_count() const
949 return m_nCapacity.load(atomics::memory_order_relaxed);
952 /// Returns the arity of \p refinable mutex policy
953 CDS_CONSTEXPR unsigned int arity() const CDS_NOEXCEPT
958 /// Returns internal statistics
959 statistics_type const& statistics() const
965 /// CuckooSet internal statistics
967 typedef cds::atomicity::event_counter counter_type ; ///< Counter type
969 counter_type m_nRelocateCallCount ; ///< Count of \p relocate function call
970 counter_type m_nRelocateRoundCount ; ///< Count of attempts to relocate items
971 counter_type m_nFalseRelocateCount ; ///< Count of unneeded attempts of \p relocate call
972 counter_type m_nSuccessRelocateCount ; ///< Count of successfull item relocating
973 counter_type m_nRelocateAboveThresholdCount; ///< Count of item relocating above probeset threshold
974 counter_type m_nFailedRelocateCount ; ///< Count of failed relocation attemp (when all probeset is full)
976 counter_type m_nResizeCallCount ; ///< Count of \p resize function call
977 counter_type m_nFalseResizeCount ; ///< Count of false \p resize function call (when other thread has been resized the set)
978 counter_type m_nResizeSuccessNodeMove; ///< Count of successfull node moving when resizing
979 counter_type m_nResizeRelocateCall ; ///< Count of \p relocate function call from \p resize function
981 counter_type m_nInsertSuccess ; ///< Count of successfull \p insert function call
982 counter_type m_nInsertFailed ; ///< Count of failed \p insert function call
983 counter_type m_nInsertResizeCount ; ///< Count of \p resize function call from \p insert
984 counter_type m_nInsertRelocateCount ; ///< Count of \p relocate function call from \p insert
985 counter_type m_nInsertRelocateFault ; ///< Count of failed \p relocate function call from \p insert
987 counter_type m_nEnsureExistCount ; ///< Count of call \p ensure function for existing node
988 counter_type m_nEnsureSuccessCount ; ///< Count of successfull \p insert function call for new node
989 counter_type m_nEnsureResizeCount ; ///< Count of \p resize function call from \p ensure
990 counter_type m_nEnsureRelocateCount ; ///< Count of \p relocate function call from \p ensure
991 counter_type m_nEnsureRelocateFault ; ///< Count of failed \p relocate function call from \p ensure
993 counter_type m_nUnlinkSuccess ; ///< Count of success \p unlink function call
994 counter_type m_nUnlinkFailed ; ///< Count of failed \p unlink function call
996 counter_type m_nEraseSuccess ; ///< Count of success \p erase function call
997 counter_type m_nEraseFailed ; ///< Count of failed \p erase function call
999 counter_type m_nFindSuccess ; ///< Count of success \p find function call
1000 counter_type m_nFindFailed ; ///< Count of failed \p find function call
1002 counter_type m_nFindEqualSuccess ; ///< Count of success \p find_equal function call
1003 counter_type m_nFindEqualFailed ; ///< Count of failed \p find_equal function call
1005 counter_type m_nFindWithSuccess ; ///< Count of success \p find_with function call
1006 counter_type m_nFindWithFailed ; ///< Count of failed \p find_with function call
1009 void onRelocateCall() { ++m_nRelocateCallCount; }
1010 void onRelocateRound() { ++m_nRelocateRoundCount; }
1011 void onFalseRelocateRound() { ++m_nFalseRelocateCount; }
1012 void onSuccessRelocateRound(){ ++m_nSuccessRelocateCount; }
1013 void onRelocateAboveThresholdRound() { ++m_nRelocateAboveThresholdCount; }
1014 void onFailedRelocate() { ++m_nFailedRelocateCount; }
1016 void onResizeCall() { ++m_nResizeCallCount; }
1017 void onFalseResizeCall() { ++m_nFalseResizeCount; }
1018 void onResizeSuccessMove() { ++m_nResizeSuccessNodeMove; }
1019 void onResizeRelocateCall() { ++m_nResizeRelocateCall; }
1021 void onInsertSuccess() { ++m_nInsertSuccess; }
1022 void onInsertFailed() { ++m_nInsertFailed; }
1023 void onInsertResize() { ++m_nInsertResizeCount; }
1024 void onInsertRelocate() { ++m_nInsertRelocateCount; }
1025 void onInsertRelocateFault() { ++m_nInsertRelocateFault; }
1027 void onEnsureExist() { ++m_nEnsureExistCount; }
1028 void onEnsureSuccess() { ++m_nEnsureSuccessCount; }
1029 void onEnsureResize() { ++m_nEnsureResizeCount; }
1030 void onEnsureRelocate() { ++m_nEnsureRelocateCount; }
1031 void onEnsureRelocateFault() { ++m_nEnsureRelocateFault; }
1033 void onUnlinkSuccess() { ++m_nUnlinkSuccess; }
1034 void onUnlinkFailed() { ++m_nUnlinkFailed; }
1036 void onEraseSuccess() { ++m_nEraseSuccess; }
1037 void onEraseFailed() { ++m_nEraseFailed; }
1039 void onFindSuccess() { ++m_nFindSuccess; }
1040 void onFindFailed() { ++m_nFindFailed; }
1042 void onFindWithSuccess() { ++m_nFindWithSuccess; }
1043 void onFindWithFailed() { ++m_nFindWithFailed; }
1047 /// CuckooSet empty internal statistics
1050 void onRelocateCall() const {}
1051 void onRelocateRound() const {}
1052 void onFalseRelocateRound() const {}
1053 void onSuccessRelocateRound()const {}
1054 void onRelocateAboveThresholdRound() const {}
1055 void onFailedRelocate() const {}
1057 void onResizeCall() const {}
1058 void onFalseResizeCall() const {}
1059 void onResizeSuccessMove() const {}
1060 void onResizeRelocateCall() const {}
1062 void onInsertSuccess() const {}
1063 void onInsertFailed() const {}
1064 void onInsertResize() const {}
1065 void onInsertRelocate() const {}
1066 void onInsertRelocateFault() const {}
1068 void onEnsureExist() const {}
1069 void onEnsureSuccess() const {}
1070 void onEnsureResize() const {}
1071 void onEnsureRelocate() const {}
1072 void onEnsureRelocateFault() const {}
1074 void onUnlinkSuccess() const {}
1075 void onUnlinkFailed() const {}
1077 void onEraseSuccess() const {}
1078 void onEraseFailed() const {}
1080 void onFindSuccess() const {}
1081 void onFindFailed() const {}
1083 void onFindWithSuccess() const {}
1084 void onFindWithFailed() const {}
1088 /// Type traits for CuckooSet class
1093 Possible values are: cuckoo::base_hook, cuckoo::member_hook, cuckoo::traits_hook.
1095 typedef base_hook<> hook;
1097 /// Hash functors tuple
1099 This is mandatory type and has no predefined one.
1101 At least, two hash functors should be provided. All hash functor
1102 should be orthogonal (different): for each <tt> i,j: i != j => h[i](x) != h[j](x) </tt>.
1103 The hash functors are defined as <tt> std::tuple< H1, H2, ... Hn > </tt>:
1104 \@code cds::opt::hash< std::tuple< h1, h2 > > \@endcode
1105 The number of hash functors specifies the number \p k - the count of hash tables in cuckoo hashing.
1106 Up to 10 different hash functors are supported.
1108 typedef cds::opt::none hash;
1110 /// Concurrent access policy
1112 Available opt::mutex_policy types:
1113 - cuckoo::striping - simple, but the lock array is not resizable
1114 - cuckoo::refinable - resizable lock array, but more complex access to set data.
1116 Default is cuckoo::striping.
1118 typedef cuckoo::striping<> mutex_policy;
1120 /// Key equality functor
1122 Default is <tt>std::equal_to<T></tt>
1124 typedef opt::none equal_to;
1126 /// Key comparison functor
1128 No default functor is provided. If the option is not specified, the \p less is used.
1130 typedef opt::none compare;
1132 /// specifies binary predicate used for key comparison.
1134 Default is \p std::less<T>.
1136 typedef opt::none less;
1140 The type for item counting feature.
1141 Default is cds::atomicity::item_counter
1143 Only atomic item counter type is allowed.
1145 typedef atomicity::item_counter item_counter;
1149 The allocator type for allocating bucket tables.
1151 typedef CDS_DEFAULT_ALLOCATOR allocator;
1155 The disposer functor is used in CuckooSet::clear member function
1158 typedef intrusive::opt::v::empty_disposer disposer;
1160 /// Internal statistics. Available statistics: cuckoo::stat, cuckoo::empty_stat
1161 typedef empty_stat stat;
1164 /// Metafunction converting option list to CuckooSet traits
1166 This is a wrapper for <tt> cds::opt::make_options< type_traits, Options...> </tt>
1167 \p Options list see \ref CuckooSet.
1169 template <typename... Options>
1170 struct make_traits {
1171 typedef typename cds::opt::make_options<
1172 typename cds::opt::find_type_traits< cuckoo::type_traits, Options... >::type
1174 >::type type ; ///< Result of metafunction
1179 template <typename Node, typename Probeset>
1182 template <typename Node>
1183 class bucket_entry<Node, cuckoo::list>
1186 typedef Node node_type;
1187 typedef cuckoo::list_probeset_class probeset_class;
1188 typedef cuckoo::list probeset_type;
1198 friend class bucket_entry;
1204 iterator( node_type * p )
1207 iterator( iterator const& it)
1211 iterator& operator=( iterator const& it )
1217 iterator& operator=( node_type * p )
1223 node_type * operator->()
1227 node_type& operator*()
1229 assert( pNode != nullptr );
1234 iterator& operator ++()
1237 pNode = pNode->m_pNext;
1241 bool operator==(iterator const& it ) const
1243 return pNode == it.pNode;
1245 bool operator!=(iterator const& it ) const
1247 return !( *this == it );
1256 static_assert(( std::is_same<typename node_type::probeset_type, probeset_type>::value ), "Incompatible node type" );
1261 return iterator(pHead);
1268 void insert_after( iterator it, node_type * p )
1270 node_type * pPrev = it.pNode;
1272 p->m_pNext = pPrev->m_pNext;
1283 void remove( iterator itPrev, iterator itWhat )
1285 node_type * pPrev = itPrev.pNode;
1286 node_type * pWhat = itWhat.pNode;
1287 assert( (!pPrev && pWhat == pHead) || (pPrev && pPrev->m_pNext == pWhat) );
1290 pPrev->m_pNext = pWhat->m_pNext;
1292 assert( pWhat == pHead );
1293 pHead = pHead->m_pNext;
1302 for ( node_type * pNode = pHead; pNode; pNode = pNext ) {
1303 pNext = pNode->m_pNext;
1311 template <typename Disposer>
1312 void clear( Disposer disp )
1315 for ( node_type * pNode = pHead; pNode; pNode = pNext ) {
1316 pNext = pNode->m_pNext;
1325 unsigned int size() const
1331 template <typename Node, unsigned int Capacity>
1332 class bucket_entry<Node, cuckoo::vector<Capacity> >
1335 typedef Node node_type;
1336 typedef cuckoo::vector_probeset_class probeset_class;
1337 typedef cuckoo::vector<Capacity> probeset_type;
1339 static unsigned int const c_nCapacity = probeset_type::c_nCapacity;
1342 node_type * m_arrNode[c_nCapacity];
1343 unsigned int m_nSize;
1345 void shift_up( unsigned int nFrom )
1347 assert( m_nSize < c_nCapacity );
1350 if ( nFrom < m_nSize )
1351 std::copy_backward( m_arrNode + nFrom, m_arrNode + m_nSize, m_arrNode + m_nSize + 1 );
1353 // alternative: low-level byte copying
1354 //memmove( m_arrNode + nFrom + 1, m_arrNode + nFrom, (m_nSize - nFrom) * sizeof(m_arrNode[0]) );
1357 void shift_down( node_type ** pFrom )
1359 assert( m_arrNode <= pFrom && pFrom < m_arrNode + m_nSize);
1361 std::copy( pFrom + 1, m_arrNode + m_nSize, pFrom );
1363 // alternative: low-level byte copying
1364 //memmove( pFrom + 1, pFrom, (m_nSize - nFrom - 1) * sizeof(m_arrNode[0]));
1370 friend class bucket_entry;
1376 iterator( node_type ** p )
1379 iterator( iterator const& it)
1383 iterator& operator=( iterator const& it )
1389 node_type * operator->()
1391 assert( pArr != nullptr );
1394 node_type& operator*()
1396 assert( pArr != nullptr );
1397 assert( *pArr != nullptr );
1402 iterator& operator ++()
1408 bool operator==(iterator const& it ) const
1410 return pArr == it.pArr;
1412 bool operator!=(iterator const& it ) const
1414 return !( *this == it );
1422 memset( m_arrNode, 0, sizeof(m_arrNode));
1423 static_assert(( std::is_same<typename node_type::probeset_type, probeset_type>::value ), "Incompatible node type" );
1428 return iterator(m_arrNode);
1432 return iterator(m_arrNode + size());
1435 void insert_after( iterator it, node_type * p )
1437 assert( m_nSize < c_nCapacity );
1438 assert( !it.pArr || (m_arrNode <= it.pArr && it.pArr <= m_arrNode + m_nSize));
1441 shift_up( (unsigned int)(it.pArr - m_arrNode) + 1 );
1451 void remove( iterator /*itPrev*/, iterator itWhat )
1454 shift_down( itWhat.pArr );
1463 template <typename Disposer>
1464 void clear( Disposer disp )
1466 for ( unsigned int i = 0; i < m_nSize; ++i ) {
1467 disp( m_arrNode[i] );
1472 unsigned int size() const
1478 template <typename Node, unsigned int ArraySize>
1480 static void store( Node * pNode, size_t * pHashes )
1482 memcpy( pNode->m_arrHash, pHashes, sizeof(size_t) * ArraySize );
1484 static bool equal_to( Node& node, unsigned int nTable, size_t nHash )
1486 return node.m_arrHash[nTable] == nHash;
1489 template <typename Node>
1490 struct hash_ops<Node, 0>
1492 static void store( Node * /*pNode*/, size_t * /*pHashes*/ )
1494 static bool equal_to( Node& /*node*/, unsigned int /*nTable*/, size_t /*nHash*/ )
1500 template <typename NodeTraits, bool Ordered>
1503 template <typename NodeTraits>
1504 struct contains<NodeTraits, true>
1506 template <typename BucketEntry, typename Position, typename Q, typename Compare>
1507 static bool find( BucketEntry& probeset, Position& pos, unsigned int nTable, size_t nHash, Q const& val, Compare cmp )
1510 typedef typename BucketEntry::iterator bucket_iterator;
1512 bucket_iterator itPrev;
1514 for ( bucket_iterator it = probeset.begin(), itEnd = probeset.end(); it != itEnd; ++it ) {
1515 int cmpRes = cmp( *NodeTraits::to_value_ptr(*it), val );
1516 if ( cmpRes >= 0 ) {
1518 pos.itPrev = itPrev;
1525 pos.itPrev = itPrev;
1526 pos.itFound = probeset.end();
1531 template <typename NodeTraits>
1532 struct contains<NodeTraits, false>
1534 template <typename BucketEntry, typename Position, typename Q, typename EqualTo>
1535 static bool find( BucketEntry& probeset, Position& pos, unsigned int nTable, size_t nHash, Q const& val, EqualTo eq )
1537 // Unordered version
1538 typedef typename BucketEntry::iterator bucket_iterator;
1539 typedef typename BucketEntry::node_type node_type;
1541 bucket_iterator itPrev;
1543 for ( bucket_iterator it = probeset.begin(), itEnd = probeset.end(); it != itEnd; ++it ) {
1544 if ( hash_ops<node_type, node_type::hash_array_size>::equal_to( *it, nTable, nHash ) && eq( *NodeTraits::to_value_ptr(*it), val )) {
1546 pos.itPrev = itPrev;
1552 pos.itPrev = itPrev;
1553 pos.itFound = probeset.end();
1558 } // namespace details
1561 } // namespace cuckoo
1564 /** @ingroup cds_intrusive_map
1567 - [2007] M.Herlihy, N.Shavit, M.Tzafrir "Concurrent Cuckoo Hashing. Technical report"
1568 - [2008] Maurice Herlihy, Nir Shavit "The Art of Multiprocessor Programming"
1570 <b>About Cuckoo hashing</b>
1572 [From <i>"The Art of Multiprocessor Programming"</i>]
1573 Cuckoo hashing is a hashing algorithm in which a newly added item displaces any earlier item
1574 occupying the same slot. For brevity, a table is a k-entry array of items. For a hash set f size
1575 N = 2k we use a two-entry array of tables, and two independent hash functions,
1576 <tt> h0, h1: KeyRange -> 0,...,k-1</tt>
1577 mapping the set of possible keys to entries in he array. To test whether a value \p x is in the set,
1578 <tt>find(x)</tt> tests whether either <tt>table[0][h0(x)]</tt> or <tt>table[1][h1(x)]</tt> is
1579 equal to \p x. Similarly, <tt>erase(x)</tt>checks whether \p x is in either <tt>table[0][h0(x)]</tt>
1580 or <tt>table[1][h1(x)]</tt>, ad removes it if found.
1582 The <tt>insert(x)</tt> successively "kicks out" conflicting items until every key has a slot.
1583 To add \p x, the method swaps \p x with \p y, the current occupant of <tt>table[0][h0(x)]</tt>.
1584 If the prior value was \p nullptr, it is done. Otherwise, it swaps the newly nest-less value \p y
1585 for the current occupant of <tt>table[1][h1(y)]</tt> in the same way. As before, if the prior value
1586 was \p nullptr, it is done. Otherwise, the method continues swapping entries (alternating tables)
1587 until it finds an empty slot. We might not find an empty slot, either because the table is full,
1588 or because the sequence of displacement forms a cycle. We therefore need an upper limit on the
1589 number of successive displacements we are willing to undertake. When this limit is exceeded,
1590 we resize the hash table, choose new hash functions and start over.
1592 For concurrent cuckoo hashing, rather than organizing the set as a two-dimensional table of
1593 items, we use two-dimensional table of probe sets, where a probe set is a constant-sized set
1594 of items with the same hash code. Each probe set holds at most \p PROBE_SIZE items, but the algorithm
1595 tries to ensure that when the set is quiescent (i.e no method call in progress) each probe set
1596 holds no more than <tt>THRESHOLD < PROBE_SET</tt> items. While method calls are in-flight, a probe
1597 set may temporarily hold more than \p THRESHOLD but never more than \p PROBE_SET items.
1599 In current implementation, a probe set can be defined either as a (single-linked) list
1600 or as a fixed-sized vector, optionally ordered.
1602 In description above two-table cuckoo hashing (<tt>k = 2</tt>) has been considered.
1603 We can generalize this approach for <tt>k >= 2</tt> when we have \p k hash functions
1604 <tt>h[0], ... h[k-1]</tt> and \p k tables <tt>table[0], ... table[k-1]</tt>.
1606 The search in probe set is linear, the complexity is <tt> O(PROBE_SET) </tt>.
1607 The probe set may be ordered or not. Ordered probe set can be more efficient since
1608 the average search complexity is <tt>O(PROBE_SET/2)</tt>.
1609 However, the overhead of sorting can eliminate a gain of ordered search.
1611 The probe set is ordered if opt::compare or opt::less is specified in \p Traits template
1612 parameter. Otherwise, the probe set is unordered and \p Traits must contain
1613 opt::equal_to option.
1615 The cds::intrusive::cuckoo namespace contains \p %CuckooSet-related declarations.
1618 - \p T - the type stored in the set. The type must be based on cuckoo::node (for cuckoo::base_hook)
1619 or it must have a member of type %cuckoo::node (for cuckoo::member_hook),
1620 or it must be convertible to \p %cuckoo::node (for cuckoo::traits_hook)
1621 - \p Traits - type traits. See cuckoo::type_traits for explanation. It is possible to declare option-based
1622 set with cuckoo::make_traits metafunction result as \p Traits template argument.
1624 Template argument list \p Options... of cuckoo::make_traits metafunction are:
1625 - intrusive::opt::hook - hook used. Possible values are: cuckoo::base_hook, cuckoo::member_hook, cuckoo::traits_hook.
1626 If the option is not specified, <tt>%cuckoo::base_hook<></tt> is used.
1627 - opt::hash - hash functor tuple, mandatory option. At least, two hash functors should be provided. All hash functor
1628 should be orthogonal (different): for each <tt> i,j: i != j => h[i](x) != h[j](x) </tt>.
1629 The hash functors are passed as <tt> std::tuple< H1, H2, ... Hn > </tt>. The number of hash functors specifies
1630 the number \p k - the count of hash tables in cuckoo hashing. If the compiler supports variadic templates
1631 then k is unlimited, otherwise up to 10 different hash functors are supported.
1632 - opt::mutex_policy - concurrent access policy.
1633 Available policies: cuckoo::striping, cuckoo::refinable.
1634 Default is cuckoo::striping.
1635 - opt::equal_to - key equality functor like \p std::equal_to.
1636 If this functor is defined then the probe-set will be unordered.
1637 If opt::compare or opt::less option is specified too, then the probe-set will be ordered
1638 and opt::equal_to will be ignored.
1639 - opt::compare - key comparison functor. No default functor is provided.
1640 If the option is not specified, the opt::less is used.
1641 If opt::compare or opt::less option is specified, then the probe-set will be ordered.
1642 - opt::less - specifies binary predicate used for key comparison. Default is \p std::less<T>.
1643 If opt::compare or opt::less option is specified, then the probe-set will be ordered.
1644 - opt::item_counter - the type of item counting feature. Default is \ref atomicity::item_counter
1645 The item counter should be atomic.
1646 - opt::allocator - the allocator type using for allocating bucket tables.
1647 Default is \p CDS_DEFAULT_ALLOCATOR
1648 - intrusive::opt::disposer - the disposer type used in \ref clear() member function for
1649 freeing nodes. Default is intrusive::opt::v::empty_disposer
1650 - opt::stat - internal statistics. Possibly types: cuckoo::stat, cuckoo::empty_stat.
1651 Default is cuckoo::empty_stat
1653 The probe set options cuckoo::probeset_type and cuckoo::store_hash are taken from \p node type
1654 specified by \p opt::hook option.
1658 You should incorporate cuckoo::node into your struct \p T and provide
1659 appropriate cuckoo::type_traits::hook in your \p Traits template parameters. Usually, for \p Traits you
1660 define a struct based on cuckoo::type_traits.
1662 Example for base hook and list-based probe-set:
1664 #include <cds/intrusive/cuckoo_set.h>
1666 // Data stored in cuckoo set
1667 // We use list as probe-set container and store hash values in the node
1668 // (since we use two hash functions we should store 2 hash values per node)
1669 struct my_data: public cds::intrusive::cuckoo::node< cds::intrusive::cuckoo::list, 2 >
1678 // Provide equal_to functor for my_data since we will use unordered probe-set
1679 struct my_data_equal_to {
1680 bool operator()( const my_data& d1, const my_data& d2 ) const
1682 return d1.strKey.compare( d2.strKey ) == 0;
1685 bool operator()( const my_data& d, const std::string& s ) const
1687 return d.strKey.compare(s) == 0;
1690 bool operator()( const std::string& s, const my_data& d ) const
1692 return s.compare( d.strKey ) == 0;
1696 // Provide two hash functor for my_data
1698 size_t operator()(std::string const& s) const
1700 return cds::opt::v::hash<std::string>( s );
1702 size_t operator()( my_data const& d ) const
1704 return (*this)( d.strKey );
1708 struct hash2: private hash1 {
1709 size_t operator()(std::string const& s) const
1711 size_t h = ~( hash1::operator()(s));
1712 return ~h + 0x9e3779b9 + (h << 6) + (h >> 2);
1714 size_t operator()( my_data const& d ) const
1716 return (*this)( d.strKey );
1720 // Declare type traits
1721 struct my_traits: public cds::intrusive::cuckoo::type_traits
1723 typedef cds::intrusive::cuckoo::base_hook<
1724 cds::intrusive::cuckoo::probeset_type< my_data::probeset_type >
1725 ,cds::intrusive::cuckoo::store_hash< my_data::hash_array_size >
1727 typedef my_data_equa_to equal_to;
1728 typedef std::tuple< hash1, hash2 > hash;
1731 // Declare CuckooSet type
1732 typedef cds::intrusive::CuckooSet< my_data, my_traits > my_cuckoo_set;
1734 // Equal option-based declaration
1735 typedef cds::intrusive::CuckooSet< my_data,
1736 cds::intrusive::cuckoo::make_traits<
1737 cds::intrusive::opt::hook< cds::intrusive::cuckoo::base_hook<
1738 cds::intrusive::cuckoo::probeset_type< my_data::probeset_type >
1739 ,cds::intrusive::cuckoo::store_hash< my_data::hash_array_size >
1741 ,cds::opt::hash< std::tuple< hash1, hash2 > >
1742 ,cds::opt::equal_to< my_data_equal_to >
1747 If we provide \p compare function instead of \p equal_to for \p my_data
1748 we get as a result a cuckoo set with ordered probe set that may improve
1750 Example for base hook and ordered vector-based probe-set:
1753 #include <cds/intrusive/cuckoo_set.h>
1755 // Data stored in cuckoo set
1756 // We use a vector of capacity 4 as probe-set container and store hash values in the node
1757 // (since we use two hash functions we should store 2 hash values per node)
1758 struct my_data: public cds::intrusive::cuckoo::node< cds::intrusive::cuckoo::vector<4>, 2 >
1767 // Provide compare functor for my_data since we want to use ordered probe-set
1768 struct my_data_compare {
1769 int operator()( const my_data& d1, const my_data& d2 ) const
1771 return d1.strKey.compare( d2.strKey );
1774 int operator()( const my_data& d, const std::string& s ) const
1776 return d.strKey.compare(s);
1779 int operator()( const std::string& s, const my_data& d ) const
1781 return s.compare( d.strKey );
1785 // Provide two hash functor for my_data
1787 size_t operator()(std::string const& s) const
1789 return cds::opt::v::hash<std::string>( s );
1791 size_t operator()( my_data const& d ) const
1793 return (*this)( d.strKey );
1797 struct hash2: private hash1 {
1798 size_t operator()(std::string const& s) const
1800 size_t h = ~( hash1::operator()(s));
1801 return ~h + 0x9e3779b9 + (h << 6) + (h >> 2);
1803 size_t operator()( my_data const& d ) const
1805 return (*this)( d.strKey );
1809 // Declare type traits
1810 struct my_traits: public cds::intrusive::cuckoo::type_traits
1812 typedef cds::intrusive::cuckoo::base_hook<
1813 cds::intrusive::cuckoo::probeset_type< my_data::probeset_type >
1814 ,cds::intrusive::cuckoo::store_hash< my_data::hash_array_size >
1816 typedef my_data_compare compare;
1817 typedef std::tuple< hash1, hash2 > hash;
1820 // Declare CuckooSet type
1821 typedef cds::intrusive::CuckooSet< my_data, my_traits > my_cuckoo_set;
1823 // Equal option-based declaration
1824 typedef cds::intrusive::CuckooSet< my_data,
1825 cds::intrusive::cuckoo::make_traits<
1826 cds::intrusive::opt::hook< cds::intrusive::cuckoo::base_hook<
1827 cds::intrusive::cuckoo::probeset_type< my_data::probeset_type >
1828 ,cds::intrusive::cuckoo::store_hash< my_data::hash_array_size >
1830 ,cds::opt::hash< std::tuple< hash1, hash2 > >
1831 ,cds::opt::compare< my_data_compare >
1837 template <typename T, typename Traits = cuckoo::type_traits>
1841 typedef T value_type ; ///< The value type stored in the set
1842 typedef Traits options ; ///< Set traits
1844 typedef typename options::hook hook ; ///< hook type
1845 typedef typename hook::node_type node_type ; ///< node type
1846 typedef typename get_node_traits< value_type, node_type, hook>::type node_traits ; ///< node traits
1848 typedef typename options::hash hash ; ///< hash functor tuple wrapped for internal use
1849 typedef typename hash::hash_tuple_type hash_tuple_type ; ///< Type of hash tuple
1851 typedef typename options::stat stat ; ///< internal statistics type
1853 typedef typename options::mutex_policy original_mutex_policy ; ///< Concurrent access policy, see cuckoo::type_traits::mutex_policy
1855 /// Actual mutex policy
1857 Actual mutex policy is built from mutex policy type provided by \p Traits template argument (see cuckoo::type_traits::mutex_policy)
1858 but mutex policy internal statistics is conformed with cukoo::type_traits::stat type provided by \p Traits:
1859 - if \p %cuckoo::type_traits::stat is cuckoo::empty_stat then mutex policy statistics is already empty one
1860 - otherwise real mutex policy statistics is used
1862 typedef typename original_mutex_policy::template rebind_statistics<
1863 typename std::conditional<
1864 std::is_same< stat, cuckoo::empty_stat >::value
1865 ,typename original_mutex_policy::empty_stat
1866 ,typename original_mutex_policy::real_stat
1868 >::other mutex_policy;
1870 static bool const c_isSorted = !( std::is_same< typename options::compare, opt::none >::value
1871 && std::is_same< typename options::less, opt::none >::value ) ; ///< whether the probe set should be ordered
1872 static size_t const c_nArity = hash::size ; ///< the arity of cuckoo hashing: the number of hash functors provided; minimum 2.
1874 /// Key equality functor; used only for unordered probe-set
1875 typedef typename opt::details::make_equal_to< value_type, options, !c_isSorted>::type key_equal_to;
1877 /// key comparing functor based on opt::compare and opt::less option setter. Used only for ordered probe set
1878 typedef typename opt::details::make_comparator< value_type, options >::type key_comparator;
1881 typedef typename options::allocator allocator;
1883 /// item counter type
1884 typedef typename options::item_counter item_counter;
1887 typedef typename options::disposer disposer;
1891 typedef typename node_type::probeset_class probeset_class;
1892 typedef typename node_type::probeset_type probeset_type;
1893 static unsigned int const c_nNodeHashArraySize = node_type::hash_array_size;
1895 typedef typename mutex_policy::scoped_cell_lock scoped_cell_lock;
1896 typedef typename mutex_policy::scoped_cell_trylock scoped_cell_trylock;
1897 typedef typename mutex_policy::scoped_full_lock scoped_full_lock;
1898 typedef typename mutex_policy::scoped_resize_lock scoped_resize_lock;
1900 typedef cuckoo::details::bucket_entry< node_type, probeset_type > bucket_entry;
1901 typedef typename bucket_entry::iterator bucket_iterator;
1902 typedef cds::details::Allocator< bucket_entry, allocator > bucket_table_allocator;
1904 typedef size_t hash_array[c_nArity] ; ///< hash array
1907 bucket_iterator itPrev;
1908 bucket_iterator itFound;
1911 typedef typename std::conditional< c_isSorted
1912 , cuckoo::details::contains< node_traits, true >
1913 , cuckoo::details::contains< node_traits, false >
1914 >::type contains_action;
1916 template <typename Predicate>
1917 struct predicate_wrapper {
1918 typedef typename std::conditional< c_isSorted, cds::opt::details::make_comparator_from_less<Predicate>, Predicate>::type type;
1921 typedef typename std::conditional< c_isSorted, key_comparator, key_equal_to >::type key_predicate;
1925 static unsigned int const c_nDefaultProbesetSize = 4 ; ///< default probeset size
1926 static size_t const c_nDefaultInitialSize = 16 ; ///< default initial size
1927 static unsigned int const c_nRelocateLimit = c_nArity * 2 - 1 ; ///< Count of attempts to relocate before giving up
1930 bucket_entry * m_BucketTable[ c_nArity ] ; ///< Bucket tables
1932 size_t m_nBucketMask ; ///< Hash bitmask; bucket table size minus 1.
1933 unsigned int const m_nProbesetSize ; ///< Probe set size
1934 unsigned int const m_nProbesetThreshold ; ///< Probe set threshold
1936 hash m_Hash ; ///< Hash functor tuple
1937 mutex_policy m_MutexPolicy ; ///< concurrent access policy
1938 item_counter m_ItemCounter ; ///< item counter
1939 mutable stat m_Stat ; ///< internal statistics
1943 static void check_common_constraints()
1945 static_assert( (c_nArity == mutex_policy::c_nArity), "The count of hash functors must be equal to mutex_policy arity" );
1948 void check_probeset_properties() const
1950 assert( m_nProbesetThreshold < m_nProbesetSize );
1952 // if probe set type is cuckoo::vector<N> then m_nProbesetSize == N
1953 assert( node_type::probeset_size == 0 || node_type::probeset_size == m_nProbesetSize );
1956 template <typename Q>
1957 void hashing( size_t * pHashes, Q const& v ) const
1959 m_Hash( pHashes, v );
1962 void copy_hash( size_t * pHashes, value_type const& v ) const
1964 if ( c_nNodeHashArraySize )
1965 memcpy( pHashes, node_traits::to_node_ptr( v )->get_hash(), sizeof(pHashes[0]) * c_nNodeHashArraySize );
1967 hashing( pHashes, v );
1970 bucket_entry& bucket( unsigned int nTable, size_t nHash )
1972 assert( nTable < c_nArity );
1973 return m_BucketTable[nTable][nHash & m_nBucketMask];
1976 static void store_hash( node_type * pNode, size_t * pHashes )
1978 cuckoo::details::hash_ops< node_type, c_nNodeHashArraySize >::store( pNode, pHashes );
1979 //memcpy( pNode->m_arrHash, pHashes, sizeof(size_t) * c_nArity );
1982 static bool equal_hash( node_type& node, unsigned int nTable, size_t nHash )
1984 return cuckoo::details::hash_ops< node_type, c_nNodeHashArraySize >::equal_to( node, nTable, nHash );
1987 void allocate_bucket_tables( size_t nSize )
1989 assert( cds::beans::is_power2( nSize ) );
1991 m_nBucketMask = nSize - 1;
1992 bucket_table_allocator alloc;
1993 for ( unsigned int i = 0; i < c_nArity; ++i )
1994 m_BucketTable[i] = alloc.NewArray( nSize );
1997 static void free_bucket_tables( bucket_entry ** pTable, size_t nCapacity )
1999 bucket_table_allocator alloc;
2000 for ( unsigned int i = 0; i < c_nArity; ++i ) {
2001 alloc.Delete( pTable[i], nCapacity );
2002 pTable[i] = nullptr;
2005 void free_bucket_tables()
2007 free_bucket_tables( m_BucketTable, m_nBucketMask + 1 );
2010 static unsigned int const c_nUndefTable = (unsigned int) -1;
2011 template <typename Q, typename Predicate >
2012 unsigned int contains( position * arrPos, size_t * arrHash, Q const& val, Predicate pred )
2014 // Buckets must be locked
2016 for ( unsigned int i = 0; i < c_nArity; ++i ) {
2017 bucket_entry& probeset = bucket( i, arrHash[i] );
2018 if ( contains_action::find( probeset, arrPos[i], i, arrHash[i], val, pred ))
2021 return c_nUndefTable;
2024 template <typename Q, typename Predicate, typename Func>
2025 value_type * erase_( Q const& val, Predicate pred, Func f )
2028 hashing( arrHash, val );
2029 position arrPos[ c_nArity ];
2032 scoped_cell_lock guard( m_MutexPolicy, arrHash );
2034 unsigned int nTable = contains( arrPos, arrHash, val, pred );
2035 if ( nTable != c_nUndefTable ) {
2036 node_type& node = *arrPos[nTable].itFound;
2037 f( *node_traits::to_value_ptr(node) );
2038 bucket( nTable, arrHash[nTable]).remove( arrPos[nTable].itPrev, arrPos[nTable].itFound );
2040 m_Stat.onEraseSuccess();
2041 return node_traits::to_value_ptr( node );
2045 m_Stat.onEraseFailed();
2049 template <typename Q, typename Predicate, typename Func>
2050 bool find_( Q& val, Predicate pred, Func f )
2053 position arrPos[ c_nArity ];
2054 hashing( arrHash, val );
2055 scoped_cell_lock sl( m_MutexPolicy, arrHash );
2057 unsigned int nTable = contains( arrPos, arrHash, val, pred );
2058 if ( nTable != c_nUndefTable ) {
2059 f( *node_traits::to_value_ptr( *arrPos[nTable].itFound ), val );
2060 m_Stat.onFindSuccess();
2064 m_Stat.onFindFailed();
2068 bool relocate( unsigned int nTable, size_t * arrGoalHash )
2070 // arrGoalHash contains hash values for relocating element
2071 // Relocating element is first one from bucket( nTable, arrGoalHash[nTable] ) probeset
2073 m_Stat.onRelocateCall();
2077 for ( unsigned int nRound = 0; nRound < c_nRelocateLimit; ++nRound ) {
2078 m_Stat.onRelocateRound();
2081 scoped_cell_lock guard( m_MutexPolicy, arrGoalHash );
2083 bucket_entry& refBucket = bucket( nTable, arrGoalHash[nTable] );
2084 if ( refBucket.size() < m_nProbesetThreshold ) {
2085 // probeset is not above the threshold
2086 m_Stat.onFalseRelocateRound();
2090 pVal = node_traits::to_value_ptr( *refBucket.begin() );
2091 copy_hash( arrHash, *pVal );
2093 scoped_cell_trylock guard2( m_MutexPolicy, arrHash );
2094 if ( !guard2.locked() )
2095 continue ; // try one more time
2097 refBucket.remove( typename bucket_entry::iterator(), refBucket.begin() );
2099 unsigned int i = (nTable + 1) % c_nArity;
2101 // try insert into free probeset
2102 while ( i != nTable ) {
2103 bucket_entry& bkt = bucket( i, arrHash[i] );
2104 if ( bkt.size() < m_nProbesetThreshold ) {
2106 contains_action::find( bkt, pos, i, arrHash[i], *pVal, key_predicate() ) ; // must return false!
2107 bkt.insert_after( pos.itPrev, node_traits::to_node_ptr( pVal ));
2108 m_Stat.onSuccessRelocateRound();
2111 i = ( i + 1 ) % c_nArity;
2114 // try insert into partial probeset
2115 i = (nTable + 1) % c_nArity;
2116 while ( i != nTable ) {
2117 bucket_entry& bkt = bucket( i, arrHash[i] );
2118 if ( bkt.size() < m_nProbesetSize ) {
2120 contains_action::find( bkt, pos, i, arrHash[i], *pVal, key_predicate() ) ; // must return false!
2121 bkt.insert_after( pos.itPrev, node_traits::to_node_ptr( pVal ));
2123 memcpy( arrGoalHash, arrHash, sizeof(arrHash));
2124 m_Stat.onRelocateAboveThresholdRound();
2125 goto next_iteration;
2127 i = (i + 1) % c_nArity;
2130 // all probeset is full, relocating fault
2131 refBucket.insert_after( typename bucket_entry::iterator(), node_traits::to_node_ptr( pVal ));
2132 m_Stat.onFailedRelocate();
2143 m_Stat.onResizeCall();
2145 size_t nOldCapacity = bucket_count();
2146 bucket_entry * pOldTable[ c_nArity ];
2148 scoped_resize_lock guard( m_MutexPolicy );
2150 if ( nOldCapacity != bucket_count() ) {
2151 m_Stat.onFalseResizeCall();
2155 size_t nCapacity = nOldCapacity * 2;
2157 m_MutexPolicy.resize( nCapacity );
2158 memcpy( pOldTable, m_BucketTable, sizeof(pOldTable));
2159 allocate_bucket_tables( nCapacity );
2161 typedef typename bucket_entry::iterator bucket_iterator;
2163 position arrPos[ c_nArity ];
2165 for ( unsigned int nTable = 0; nTable < c_nArity; ++nTable ) {
2166 bucket_entry * pTable = pOldTable[nTable];
2167 for ( size_t k = 0; k < nOldCapacity; ++k ) {
2168 bucket_iterator itNext;
2169 for ( bucket_iterator it = pTable[k].begin(), itEnd = pTable[k].end(); it != itEnd; it = itNext ) {
2173 value_type& val = *node_traits::to_value_ptr( *it );
2174 copy_hash( arrHash, val );
2175 contains( arrPos, arrHash, val, key_predicate() ) ; // must return c_nUndefTable
2177 for ( unsigned int i = 0; i < c_nArity; ++i ) {
2178 bucket_entry& refBucket = bucket( i, arrHash[i] );
2179 if ( refBucket.size() < m_nProbesetThreshold ) {
2180 refBucket.insert_after( arrPos[i].itPrev, &*it );
2181 m_Stat.onResizeSuccessMove();
2186 for ( unsigned int i = 0; i < c_nArity; ++i ) {
2187 bucket_entry& refBucket = bucket( i, arrHash[i] );
2188 if ( refBucket.size() < m_nProbesetSize ) {
2189 refBucket.insert_after( arrPos[i].itPrev, &*it );
2190 assert( refBucket.size() > 1 );
2191 copy_hash( arrHash, *node_traits::to_value_ptr( *refBucket.begin()) );
2192 m_Stat.onResizeRelocateCall();
2193 relocate( i, arrHash );
2202 free_bucket_tables( pOldTable, nOldCapacity );
2205 CDS_CONSTEXPR static unsigned int calc_probeset_size( unsigned int nProbesetSize ) CDS_NOEXCEPT
2207 return nProbesetSize
2209 : ( node_type::probeset_size ? node_type::probeset_size : c_nDefaultProbesetSize )
2215 /// Default constructor
2217 Initial size = \ref c_nDefaultInitialSize
2220 - \p c_nDefaultProbesetSize if \p probeset_type is \p cuckoo::list
2221 - \p Capacity if \p probeset_type is <tt> cuckoo::vector<Capacity> </tt>
2223 Probe set threshold = probe set size - 1
2226 : m_nProbesetSize( calc_probeset_size(0) )
2227 , m_nProbesetThreshold( m_nProbesetSize - 1 )
2228 , m_MutexPolicy( c_nDefaultInitialSize )
2230 check_common_constraints();
2231 check_probeset_properties();
2233 allocate_bucket_tables( c_nDefaultInitialSize );
2236 /// Constructs the set object with given probe set size and threshold
2238 If probe set type is <tt> cuckoo::vector<Capacity> </tt> vector
2239 then \p nProbesetSize should be equal to vector's \p Capacity.
2242 size_t nInitialSize ///< Initial set size; if 0 - use default initial size \ref c_nDefaultInitialSize
2243 , unsigned int nProbesetSize ///< probe set size
2244 , unsigned int nProbesetThreshold = 0 ///< probe set threshold, <tt>nProbesetThreshold < nProbesetSize</tt>. If 0, nProbesetThreshold = nProbesetSize - 1
2246 : m_nProbesetSize( calc_probeset_size(nProbesetSize) )
2247 , m_nProbesetThreshold( nProbesetThreshold ? nProbesetThreshold : m_nProbesetSize - 1 )
2248 , m_MutexPolicy( cds::beans::ceil2(nInitialSize ? nInitialSize : c_nDefaultInitialSize ))
2250 check_common_constraints();
2251 check_probeset_properties();
2253 allocate_bucket_tables( nInitialSize ? cds::beans::ceil2( nInitialSize ) : c_nDefaultInitialSize );
2256 /// Constructs the set object with given hash functor tuple
2258 The probe set size and threshold are set as default, see CuckooSet()
2261 hash_tuple_type const& h ///< hash functor tuple of type <tt>std::tuple<H1, H2, ... Hn></tt> where <tt> n == \ref c_nArity </tt>
2263 : m_nProbesetSize( calc_probeset_size(0) )
2264 , m_nProbesetThreshold( m_nProbesetSize -1 )
2266 , m_MutexPolicy( c_nDefaultInitialSize )
2268 check_common_constraints();
2269 check_probeset_properties();
2271 allocate_bucket_tables( c_nDefaultInitialSize );
2274 /// Constructs the set object with given probe set properties and hash functor tuple
2276 If probe set type is <tt> cuckoo::vector<Capacity> </tt> vector
2277 then \p nProbesetSize should be equal to vector's \p Capacity.
2280 size_t nInitialSize ///< Initial set size; if 0 - use default initial size \ref c_nDefaultInitialSize
2281 , unsigned int nProbesetSize ///< probe set size, positive integer
2282 , unsigned int nProbesetThreshold ///< probe set threshold, <tt>nProbesetThreshold < nProbesetSize</tt>. If 0, nProbesetThreshold = nProbesetSize - 1
2283 , hash_tuple_type const& h ///< hash functor tuple of type <tt>std::tuple<H1, H2, ... Hn></tt> where <tt> n == \ref c_nArity </tt>
2285 : m_nProbesetSize( calc_probeset_size(nProbesetSize) )
2286 , m_nProbesetThreshold( nProbesetThreshold ? nProbesetThreshold : m_nProbesetSize - 1)
2288 , m_MutexPolicy( cds::beans::ceil2(nInitialSize ? nInitialSize : c_nDefaultInitialSize ))
2290 check_common_constraints();
2291 check_probeset_properties();
2293 allocate_bucket_tables( nInitialSize ? cds::beans::ceil2( nInitialSize ) : c_nDefaultInitialSize );
2296 /// Constructs the set object with given hash functor tuple (move semantics)
2298 The probe set size and threshold are set as default, see CuckooSet()
2301 hash_tuple_type&& h ///< hash functor tuple of type <tt>std::tuple<H1, H2, ... Hn></tt> where <tt> n == \ref c_nArity </tt>
2303 : m_nProbesetSize( calc_probeset_size(0) )
2304 , m_nProbesetThreshold( m_nProbesetSize / 2 )
2305 , m_Hash( std::forward<hash_tuple_type>(h) )
2306 , m_MutexPolicy( c_nDefaultInitialSize )
2308 check_common_constraints();
2309 check_probeset_properties();
2311 allocate_bucket_tables( c_nDefaultInitialSize );
2314 /// Constructs the set object with given probe set properties and hash functor tuple (move semantics)
2316 If probe set type is <tt> cuckoo::vector<Capacity> </tt> vector
2317 then \p nProbesetSize should be equal to vector's \p Capacity.
2320 size_t nInitialSize ///< Initial set size; if 0 - use default initial size \ref c_nDefaultInitialSize
2321 , unsigned int nProbesetSize ///< probe set size, positive integer
2322 , unsigned int nProbesetThreshold ///< probe set threshold, <tt>nProbesetThreshold < nProbesetSize</tt>. If 0, nProbesetThreshold = nProbesetSize - 1
2323 , hash_tuple_type&& h ///< hash functor tuple of type <tt>std::tuple<H1, H2, ... Hn></tt> where <tt> n == \ref c_nArity </tt>
2325 : m_nProbesetSize( calc_probeset_size(nProbesetSize) )
2326 , m_nProbesetThreshold( nProbesetThreshold ? nProbesetThreshold : m_nProbesetSize - 1)
2327 , m_Hash( std::forward<hash_tuple_type>(h) )
2328 , m_MutexPolicy( cds::beans::ceil2(nInitialSize ? nInitialSize : c_nDefaultInitialSize ))
2330 check_common_constraints();
2331 check_probeset_properties();
2333 allocate_bucket_tables( nInitialSize ? cds::beans::ceil2( nInitialSize ) : c_nDefaultInitialSize );
2339 free_bucket_tables();
2343 /// Inserts new node
2345 The function inserts \p val in the set if it does not contain
2346 an item with key equal to \p val.
2348 Returns \p true if \p val is placed into the set, \p false otherwise.
2350 bool insert( value_type& val )
2352 return insert( val, []( value_type& ) {} );
2355 /// Inserts new node
2357 The function allows to split creating of new item into two part:
2358 - create item with key only
2359 - insert new item into the set
2360 - if inserting is success, calls \p f functor to initialize value-field of \p val.
2362 The functor signature is:
2364 void func( value_type& val );
2366 where \p val is the item inserted.
2368 The user-defined functor is called only if the inserting is success and can be passed by reference
2371 template <typename Func>
2372 bool insert( value_type& val, Func f )
2375 position arrPos[ c_nArity ];
2376 unsigned int nGoalTable;
2378 hashing( arrHash, val );
2379 node_type * pNode = node_traits::to_node_ptr( val );
2380 store_hash( pNode, arrHash );
2384 scoped_cell_lock guard( m_MutexPolicy, arrHash );
2386 if ( contains( arrPos, arrHash, val, key_predicate() ) != c_nUndefTable ) {
2387 m_Stat.onInsertFailed();
2391 for ( unsigned int i = 0; i < c_nArity; ++i ) {
2392 bucket_entry& refBucket = bucket( i, arrHash[i] );
2393 if ( refBucket.size() < m_nProbesetThreshold ) {
2394 refBucket.insert_after( arrPos[i].itPrev, pNode );
2397 m_Stat.onInsertSuccess();
2402 for ( unsigned int i = 0; i < c_nArity; ++i ) {
2403 bucket_entry& refBucket = bucket( i, arrHash[i] );
2404 if ( refBucket.size() < m_nProbesetSize ) {
2405 refBucket.insert_after( arrPos[i].itPrev, pNode );
2409 assert( refBucket.size() > 1 );
2410 copy_hash( arrHash, *node_traits::to_value_ptr( *refBucket.begin()) );
2416 m_Stat.onInsertResize();
2421 m_Stat.onInsertRelocate();
2422 if ( !relocate( nGoalTable, arrHash )) {
2423 m_Stat.onInsertRelocateFault();
2424 m_Stat.onInsertResize();
2428 m_Stat.onInsertSuccess();
2432 /// Ensures that the \p val exists in the set
2434 The operation performs inserting or changing data with lock-free manner.
2436 If the item \p val not found in the set, then \p val is inserted into the set.
2437 Otherwise, the functor \p func is called with item found.
2438 The functor signature is:
2440 void func( bool bNew, value_type& item, value_type& val );
2443 - \p bNew - \p true if the item has been inserted, \p false otherwise
2444 - \p item - item of the set
2445 - \p val - argument \p val passed into the \p ensure function
2446 If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
2447 refers to the same thing.
2449 The functor may change non-key fields of the \p item.
2451 You may pass \p func argument by reference using \p std::ref.
2453 Returns <tt> std::pair<bool, bool> </tt> where \p first is \p true if operation is successful,
2454 \p second is \p true if new item has been added or \p false if the item with \p key
2455 already is in the set.
2457 template <typename Func>
2458 std::pair<bool, bool> ensure( value_type& val, Func func )
2461 position arrPos[ c_nArity ];
2462 unsigned int nGoalTable;
2464 hashing( arrHash, val );
2465 node_type * pNode = node_traits::to_node_ptr( val );
2466 store_hash( pNode, arrHash );
2470 scoped_cell_lock guard( m_MutexPolicy, arrHash );
2472 unsigned int nTable = contains( arrPos, arrHash, val, key_predicate() );
2473 if ( nTable != c_nUndefTable ) {
2474 func( false, *node_traits::to_value_ptr( *arrPos[nTable].itFound ), val );
2475 m_Stat.onEnsureExist();
2476 return std::make_pair( true, false );
2479 node_type * pNode = node_traits::to_node_ptr( val );
2480 store_hash( pNode, arrHash );
2482 for ( unsigned int i = 0; i < c_nArity; ++i ) {
2483 bucket_entry& refBucket = bucket( i, arrHash[i] );
2484 if ( refBucket.size() < m_nProbesetThreshold ) {
2485 refBucket.insert_after( arrPos[i].itPrev, pNode );
2486 func( true, val, val );
2488 m_Stat.onEnsureSuccess();
2489 return std::make_pair( true, true );
2493 for ( unsigned int i = 0; i < c_nArity; ++i ) {
2494 bucket_entry& refBucket = bucket( i, arrHash[i] );
2495 if ( refBucket.size() < m_nProbesetSize ) {
2496 refBucket.insert_after( arrPos[i].itPrev, pNode );
2497 func( true, val, val );
2500 assert( refBucket.size() > 1 );
2501 copy_hash( arrHash, *node_traits::to_value_ptr( *refBucket.begin()) );
2507 m_Stat.onEnsureResize();
2512 m_Stat.onEnsureRelocate();
2513 if ( !relocate( nGoalTable, arrHash )) {
2514 m_Stat.onEnsureRelocateFault();
2515 m_Stat.onEnsureResize();
2519 m_Stat.onEnsureSuccess();
2520 return std::make_pair( true, true );
2523 /// Unlink the item \p val from the set
2525 The function searches the item \p val in the set and unlink it
2526 if it is found and is equal to \p val (here, the equality means that
2527 \p val belongs to the set: if \p item is an item found then
2528 unlink is successful iif <tt>&val == &item</tt>)
2530 The function returns \p true if success and \p false otherwise.
2532 bool unlink( value_type& val )
2535 hashing( arrHash, val );
2536 position arrPos[ c_nArity ];
2539 scoped_cell_lock guard( m_MutexPolicy, arrHash );
2541 unsigned int nTable = contains( arrPos, arrHash, val, key_predicate() );
2542 if ( nTable != c_nUndefTable && node_traits::to_value_ptr(*arrPos[nTable].itFound) == &val ) {
2543 bucket( nTable, arrHash[nTable]).remove( arrPos[nTable].itPrev, arrPos[nTable].itFound );
2545 m_Stat.onUnlinkSuccess();
2550 m_Stat.onUnlinkFailed();
2554 /// Deletes the item from the set
2555 /** \anchor cds_intrusive_CuckooSet_erase
2556 The function searches an item with key equal to \p val in the set,
2557 unlinks it from the set, and returns a pointer to unlinked item.
2559 If the item with key equal to \p val is not found the function return \p nullptr.
2561 Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
2563 template <typename Q>
2564 value_type * erase( Q const& val )
2566 return erase( val, [](value_type const&) {} );
2569 /// Deletes the item from the set using \p pred predicate for searching
2571 The function is an analog of \ref cds_intrusive_CuckooSet_erase "erase(Q const&)"
2572 but \p pred is used for key comparing.
2573 If cuckoo set is ordered, then \p Predicate should have the interface and semantics like \p std::less.
2574 If cuckoo set is unordered, then \p Predicate should have the interface and semantics like \p std::equal_to.
2575 \p Predicate must imply the same element order as the comparator used for building the set.
2577 template <typename Q, typename Predicate>
2578 value_type * erase_with( Q const& val, Predicate pred )
2580 return erase_( val, typename predicate_wrapper<Predicate>::type(), [](value_type const&) {} );
2583 /// Delete the item from the set
2584 /** \anchor cds_intrusive_CuckooSet_erase_func
2585 The function searches an item with key equal to \p val in the set,
2586 call \p f functor with item found, unlinks it from the set, and returns a pointer to unlinked item.
2588 The \p Func interface is
2591 void operator()( value_type const& item );
2594 The functor may be passed by reference with <tt>boost:ref</tt>
2596 If the item with key equal to \p val is not found the function return \p nullptr.
2598 Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
2600 template <typename Q, typename Func>
2601 value_type * erase( Q const& val, Func f )
2603 return erase_( val, key_predicate(), f );
2606 /// Deletes the item from the set using \p pred predicate for searching
2608 The function is an analog of \ref cds_intrusive_CuckooSet_erase_func "erase(Q const&, Func)"
2609 but \p pred is used for key comparing.
2610 If you use ordered cuckoo set, then \p Predicate should have the interface and semantics like \p std::less.
2611 If you use unordered cuckoo set, then \p Predicate should have the interface and semantics like \p std::equal_to.
2612 \p Predicate must imply the same element order as the comparator used for building the set.
2614 template <typename Q, typename Predicate, typename Func>
2615 value_type * erase_with( Q const& val, Predicate pred, Func f )
2617 return erase_( val, typename predicate_wrapper<Predicate>::type(), f );
2620 /// Find the key \p val
2621 /** \anchor cds_intrusive_CuckooSet_find_func
2622 The function searches the item with key equal to \p val and calls the functor \p f for item found.
2623 The interface of \p Func functor is:
2626 void operator()( value_type& item, Q& val );
2629 where \p item is the item found, \p val is the <tt>find</tt> function argument.
2631 You can pass \p f argument by reference using \p std::ref.
2633 The functor may change non-key fields of \p item.
2635 The \p val argument is non-const since it can be used as \p f functor destination i.e., the functor
2636 may modify both arguments.
2638 Note the hash functor specified for class \p Traits template parameter
2639 should accept a parameter of type \p Q that can be not the same as \p value_type.
2641 The function returns \p true if \p val is found, \p false otherwise.
2643 template <typename Q, typename Func>
2644 bool find( Q& val, Func f )
2646 return find_( val, key_predicate(), f );
2649 /// Find the key \p val using \p pred predicate for comparing
2651 The function is an analog of \ref cds_intrusive_CuckooSet_find_func "find(Q&, Func)"
2652 but \p pred is used for key comparison.
2653 If you use ordered cuckoo set, then \p Predicate should have the interface and semantics like \p std::less.
2654 If you use unordered cuckoo set, then \p Predicate should have the interface and semantics like \p std::equal_to.
2655 \p pred must imply the same element order as the comparator used for building the set.
2657 template <typename Q, typename Predicate, typename Func>
2658 bool find_with( Q& val, Predicate pred, Func f )
2660 return find_( val, typename predicate_wrapper<Predicate>::type(), f );
2663 /// Find the key \p val
2664 /** \anchor cds_intrusive_CuckooSet_find_cfunc
2665 The function searches the item with key equal to \p val and calls the functor \p f for item found.
2666 The interface of \p Func functor is:
2669 void operator()( value_type& item, Q const& val );
2672 where \p item is the item found, \p val is the <tt>find</tt> function argument.
2674 You can pass \p f argument by reference using \p std::ref.
2676 The functor may change non-key fields of \p item.
2678 The \p val argument is non-const since it can be used as \p f functor destination i.e., the functor
2679 may modify both arguments.
2681 The function returns \p true if \p val is found, \p false otherwise.
2683 template <typename Q, typename Func>
2684 bool find( Q const& val, Func f )
2686 return find_( val, key_predicate(), f );
2689 /// Find the key \p val using \p pred predicate for comparing
2691 The function is an analog of \ref cds_intrusive_CuckooSet_find_cfunc "find(Q const&, Func)"
2692 but \p pred is used for key comparison.
2693 If you use ordered cuckoo set, then \p Predicate should have the interface and semantics like \p std::less.
2694 If you use unordered cuckoo set, then \p Predicate should have the interface and semantics like \p std::equal_to.
2695 \p pred must imply the same element order as the comparator used for building the set.
2697 template <typename Q, typename Predicate, typename Func>
2698 bool find_with( Q const& val, Predicate pred, Func f )
2700 return find_( val, typename predicate_wrapper<Predicate>::type(), f );
2703 /// Find the key \p val
2704 /** \anchor cds_intrusive_CuckooSet_find_val
2705 The function searches the item with key equal to \p val
2706 and returns \p true if it is found, and \p false otherwise.
2708 Note the hash functor specified for class \p Traits template parameter
2709 should accept a parameter of type \p Q that can be not the same as \p value_type.
2711 template <typename Q>
2712 bool find( Q const& val )
2714 return find( val, [](value_type&, Q const& ) {} );
2717 /// Find the key \p val using \p pred predicate for comparing
2719 The function is an analog of \ref cds_intrusive_CuckooSet_find_val "find(Q const&)"
2720 but \p pred is used for key comparison.
2721 If you use ordered cuckoo set, then \p Predicate should have the interface and semantics like \p std::less.
2722 If you use unordered cuckoo set, then \p Predicate should have the interface and semantics like \p std::equal_to.
2723 \p pred must imply the same element order as the comparator used for building the set.
2725 template <typename Q, typename Predicate>
2726 bool find_with( Q const& val, Predicate pred )
2728 return find_with( val, typename predicate_wrapper<Predicate>::type(), [](value_type& , Q const& ) {} );
2733 The function unlinks all items from the set.
2734 For any item \ref disposer is called
2738 clear_and_dispose( disposer() );
2741 /// Clears the set and calls \p disposer for each item
2743 The function unlinks all items from the set calling \p disposer for each item.
2744 \p Disposer functor interface is:
2747 void operator()( value_type * p );
2751 The \ref disposer specified in \p Traits options is not called.
2753 template <typename Disposer>
2754 void clear_and_dispose( Disposer oDisposer )
2756 // locks entire array
2757 scoped_full_lock sl( m_MutexPolicy );
2759 for ( unsigned int i = 0; i < c_nArity; ++i ) {
2760 bucket_entry * pEntry = m_BucketTable[i];
2761 bucket_entry * pEnd = pEntry + m_nBucketMask + 1;
2762 for ( ; pEntry != pEnd ; ++pEntry ) {
2763 pEntry->clear( [&oDisposer]( node_type * pNode ){ oDisposer( node_traits::to_value_ptr( pNode )) ; } );
2766 m_ItemCounter.reset();
2769 /// Checks if the set is empty
2771 Emptiness is checked by item counting: if item count is zero then the set is empty.
2778 /// Returns item count in the set
2781 return m_ItemCounter;
2784 /// Returns the size of hash table
2786 The hash table size is non-constant and can be increased via resizing.
2788 size_t bucket_count() const
2790 return m_nBucketMask + 1;
2793 /// Returns lock array size
2794 size_t lock_count() const
2796 return m_MutexPolicy.lock_count();
2799 /// Returns const reference to internal statistics
2800 stat const& statistics() const
2805 /// Returns const reference to mutex policy internal statistics
2806 typename mutex_policy::statistics_type const& mutex_policy_statistics() const
2808 return m_MutexPolicy.statistics();
2811 }} // namespace cds::intrusive
2813 #endif // #ifndef __CDS_INTRUSIVE_CUCKOO_SET_H