3 #ifndef CDSLIB_INTRUSIVE_CUCKOO_SET_H
4 #define CDSLIB_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/sync/lock_array.h>
14 #include <cds/os/thread.h>
15 #include <cds/sync/spinlock.h>
18 namespace cds { namespace intrusive {
20 /// CuckooSet-related definitions
22 /// Option to define probeset type
24 The option specifies probeset type for the CuckooSet.
26 - \p cds::intrusive::cuckoo::list - the probeset is a single-linked list.
27 The node contains pointer to next node in probeset.
28 - \p cds::intrusive::cuckoo::vector<Capacity> - the probeset is a vector
29 with constant-size \p Capacity where \p Capacity is an <tt>unsigned int</tt> constant.
30 The node does not contain any auxiliary data.
32 template <typename Type>
36 template <typename Base>
37 struct pack: public Base {
38 typedef Type probeset_type;
43 /// Option specifying whether to store hash values in the node
45 This option reserves additional space in the hook to store the hash value of the object once it's introduced in the container.
46 When this option is used, the unordered container will store the calculated hash value in the hook and rehashing operations won't need
47 to recalculate the hash of the value. This option will improve the performance of unordered containers
48 when rehashing is frequent or hashing the value is a slow operation
50 The \p Count template parameter defines the size of hash array. Remember that cuckoo hashing implies at least two
53 Possible values of \p Count:
54 - 0 - no hash storing in the node
55 - greater that 1 - store hash values.
57 Value 1 is deprecated.
59 template <unsigned int Count>
63 template <typename Base>
64 struct pack: public Base {
65 static unsigned int const store_hash = Count;
72 // Probeset type placeholders
73 struct list_probeset_class;
74 struct vector_probeset_class;
78 /// List probeset type
82 /// Vector probeset type
83 template <unsigned int Capacity>
87 static unsigned int const c_nCapacity = Capacity;
93 - \p ProbesetType - type of probeset. Can be \p cds::intrusive::cuckoo::list
94 or \p cds::intrusive::cuckoo::vector<Capacity>.
95 - \p StoreHashCount - constant that defines whether to store node hash values.
96 See cuckoo::store_hash option for explanation
97 - \p Tag - a \ref cds_intrusive_hook_tag "tag"
99 template <typename ProbesetType = cuckoo::list, unsigned int StoreHashCount = 0, typename Tag = opt::none>
101 #ifdef CDS_DOXYGEN_INVOKED
103 typedef ProbesetType probeset_type ; ///< Probeset type
104 typedef Tag tag ; ///< Tag
105 static unsigned int const hash_array_size = StoreHashCount ; ///< The size of hash array
111 template <typename Tag>
112 struct node< cuckoo::list, 0, Tag>
114 typedef list_probeset_class probeset_class;
115 typedef cuckoo::list probeset_type;
117 static unsigned int const hash_array_size = 0;
118 static unsigned int const probeset_size = 0;
122 CDS_CONSTEXPR node() CDS_NOEXCEPT
126 void store_hash( size_t * )
129 size_t * get_hash() const
131 // This node type does not store hash values!!!
142 template <unsigned int StoreHashCount, typename Tag>
143 struct node< cuckoo::list, StoreHashCount, Tag>
145 typedef list_probeset_class probeset_class;
146 typedef cuckoo::list probeset_type;
148 static unsigned int const hash_array_size = StoreHashCount;
149 static unsigned int const probeset_size = 0;
152 size_t m_arrHash[ hash_array_size ];
157 memset( m_arrHash, 0, sizeof(m_arrHash));
160 void store_hash( size_t * pHashes )
162 memcpy( m_arrHash, pHashes, hash_array_size );
165 size_t * get_hash() const
167 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 traits;
246 typedef typename traits::probeset_type probeset_type;
247 typedef typename traits::tag tag;
248 static unsigned int const store_hash = traits::store_hash;
250 typedef node<probeset_type, store_hash, tag> node_type;
252 typedef HookType hook_type;
259 - \p cuckoo::probeset_type - probeset type. Defaul is \p cuckoo::list
260 - \p cuckoo::store_hash - store hash values in the node or not. Default is 0 (no storing)
261 - \p opt::tag - a \ref cds_intrusive_hook_tag "tag"
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 - \p cuckoo::probeset_type - probeset type. Defaul is \p cuckoo::list
274 - \p cuckoo::store_hash - store hash values in the node or not. Default is 0 (no storing)
275 - \p opt::tag - a \ref cds_intrusive_hook_tag "tag"
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 - \p cuckoo::probeset_type - probeset type. Defaul is \p cuckoo::list
292 - \p cuckoo::store_hash - store hash values in the node or not. Default is 0 (no storing)
293 - \p opt::tag - a \ref cds_intrusive_hook_tag "tag"
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::sync::lock_array< lock_type, cds::sync::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::sync::trivial_select_policy lock_selection_policy;
636 class lock_array_type
637 : public cds::sync::lock_array< lock_type, lock_selection_policy, allocator_type >
638 , public std::enable_shared_from_this< lock_array_type >
640 typedef cds::sync::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::sync::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::get_current_thread_id();
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::get_current_thread_id();
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::get_current_thread_id();
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_nUpdateExistCount ; ///< Count of call \p update() function for existing node
988 counter_type m_nUpdateSuccessCount ; ///< Count of successfull \p insert function call for new node
989 counter_type m_nUpdateResizeCount ; ///< Count of \p resize function call from \p update()
990 counter_type m_nUpdateRelocateCount ; ///< Count of \p relocate function call from \p update()
991 counter_type m_nUpdateRelocateFault ; ///< Count of failed \p relocate function call from \p update()
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 onUpdateExist() { ++m_nUpdateExistCount; }
1028 void onUpdateSuccess() { ++m_nUpdateSuccessCount; }
1029 void onUpdateResize() { ++m_nUpdateResizeCount; }
1030 void onUpdateRelocate() { ++m_nUpdateRelocateCount; }
1031 void onUpdateRelocateFault() { ++m_nUpdateRelocateFault; }
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 onUpdateExist() const {}
1069 void onUpdateSuccess() const {}
1070 void onUpdateResize() const {}
1071 void onUpdateRelocate() const {}
1072 void onUpdateRelocateFault() 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.
1107 To specify hash tuple in traits you should use \p cds::opt::hash_tuple:
1109 struct my_traits: public cds::intrusive::cuckoo::traits {
1110 typedef cds::opt::hash_tuple< hash1, hash2 > hash;
1114 typedef cds::opt::none hash;
1116 /// Concurrent access policy
1118 Available opt::mutex_policy types:
1119 - \p cuckoo::striping - simple, but the lock array is not resizable
1120 - \p cuckoo::refinable - resizable lock array, but more complex access to set data.
1122 Default is \p cuckoo::striping.
1124 typedef cuckoo::striping<> mutex_policy;
1126 /// Key equality functor
1128 Default is <tt>std::equal_to<T></tt>
1130 typedef opt::none equal_to;
1132 /// Key comparing functor
1134 No default functor is provided. If the option is not specified, the \p less is used.
1136 typedef opt::none compare;
1138 /// specifies binary predicate used for key comparison.
1140 Default is \p std::less<T>.
1142 typedef opt::none less;
1146 The type for item counting feature.
1147 Default is \p cds::atomicity::item_counter
1149 Only atomic item counter type is allowed.
1151 typedef atomicity::item_counter item_counter;
1155 The allocator type for allocating bucket tables.
1157 typedef CDS_DEFAULT_ALLOCATOR allocator;
1161 The disposer functor is used in \p CuckooSet::clear() member function
1164 typedef intrusive::opt::v::empty_disposer disposer;
1166 /// Internal statistics. Available statistics: \p cuckoo::stat, \p cuckoo::empty_stat
1167 typedef empty_stat stat;
1170 /// Metafunction converting option list to \p CuckooSet traits
1172 Template argument list \p Options... are:
1173 - \p intrusive::opt::hook - hook used. Possible values are: \p cuckoo::base_hook, \p cuckoo::member_hook,
1174 \p cuckoo::traits_hook.
1175 If the option is not specified, <tt>%cuckoo::base_hook<></tt> is used.
1176 - \p opt::hash - hash functor tuple, mandatory option. At least, two hash functors should be provided. All hash functor
1177 should be orthogonal (different): for each <tt> i,j: i != j => h[i](x) != h[j](x) </tt>.
1178 The hash functors are passed as <tt> std::tuple< H1, H2, ... Hn > </tt>. The number of hash functors specifies
1179 the number \p k - the count of hash tables in cuckoo hashing.
1180 - \p opt::mutex_policy - concurrent access policy.
1181 Available policies: \p cuckoo::striping, \p cuckoo::refinable.
1182 Default is \p %cuckoo::striping.
1183 - \p opt::equal_to - key equality functor like \p std::equal_to.
1184 If this functor is defined then the probe-set will be unordered.
1185 If \p %opt::compare or \p %opt::less option is specified too, then the probe-set will be ordered
1186 and \p %opt::equal_to will be ignored.
1187 - \p opt::compare - key comparison functor. No default functor is provided.
1188 If the option is not specified, the \p %opt::less is used.
1189 If \p %opt::compare or \p %opt::less option is specified, then the probe-set will be ordered.
1190 - \p opt::less - specifies binary predicate used for key comparison. Default is \p std::less<T>.
1191 If \p %opt::compare or \p %opt::less option is specified, then the probe-set will be ordered.
1192 - \p opt::item_counter - the type of item counting feature. Default is \p atomicity::item_counter
1193 The item counter should be atomic.
1194 - \p opt::allocator - the allocator type using for allocating bucket tables.
1195 Default is \ref CDS_DEFAULT_ALLOCATOR
1196 - \p intrusive::opt::disposer - the disposer type used in \p clear() member function for
1197 freeing nodes. Default is \p intrusive::opt::v::empty_disposer
1198 - \p opt::stat - internal statistics. Possibly types: \p cuckoo::stat, \p cuckoo::empty_stat.
1199 Default is \p %cuckoo::empty_stat
1201 The probe set traits \p cuckoo::probeset_type and \p cuckoo::store_hash are taken from \p node type
1202 specified by \p opt::hook option.
1204 template <typename... Options>
1205 struct make_traits {
1206 typedef typename cds::opt::make_options<
1207 typename cds::opt::find_type_traits< cuckoo::traits, Options... >::type
1209 >::type type ; ///< Result of metafunction
1214 template <typename Node, typename Probeset>
1217 template <typename Node>
1218 class bucket_entry<Node, cuckoo::list>
1221 typedef Node node_type;
1222 typedef cuckoo::list_probeset_class probeset_class;
1223 typedef cuckoo::list probeset_type;
1233 friend class bucket_entry;
1239 iterator( node_type * p )
1242 iterator( iterator const& it)
1246 iterator& operator=( iterator const& it )
1252 iterator& operator=( node_type * p )
1258 node_type * operator->()
1262 node_type& operator*()
1264 assert( pNode != nullptr );
1269 iterator& operator ++()
1272 pNode = pNode->m_pNext;
1276 bool operator==(iterator const& it ) const
1278 return pNode == it.pNode;
1280 bool operator!=(iterator const& it ) const
1282 return !( *this == it );
1291 static_assert(( std::is_same<typename node_type::probeset_type, probeset_type>::value ), "Incompatible node type" );
1296 return iterator(pHead);
1303 void insert_after( iterator it, node_type * p )
1305 node_type * pPrev = it.pNode;
1307 p->m_pNext = pPrev->m_pNext;
1318 void remove( iterator itPrev, iterator itWhat )
1320 node_type * pPrev = itPrev.pNode;
1321 node_type * pWhat = itWhat.pNode;
1322 assert( (!pPrev && pWhat == pHead) || (pPrev && pPrev->m_pNext == pWhat) );
1325 pPrev->m_pNext = pWhat->m_pNext;
1327 assert( pWhat == pHead );
1328 pHead = pHead->m_pNext;
1337 for ( node_type * pNode = pHead; pNode; pNode = pNext ) {
1338 pNext = pNode->m_pNext;
1346 template <typename Disposer>
1347 void clear( Disposer disp )
1350 for ( node_type * pNode = pHead; pNode; pNode = pNext ) {
1351 pNext = pNode->m_pNext;
1360 unsigned int size() const
1366 template <typename Node, unsigned int Capacity>
1367 class bucket_entry<Node, cuckoo::vector<Capacity> >
1370 typedef Node node_type;
1371 typedef cuckoo::vector_probeset_class probeset_class;
1372 typedef cuckoo::vector<Capacity> probeset_type;
1374 static unsigned int const c_nCapacity = probeset_type::c_nCapacity;
1377 node_type * m_arrNode[c_nCapacity];
1378 unsigned int m_nSize;
1380 void shift_up( unsigned int nFrom )
1382 assert( m_nSize < c_nCapacity );
1385 if ( nFrom < m_nSize )
1386 std::copy_backward( m_arrNode + nFrom, m_arrNode + m_nSize, m_arrNode + m_nSize + 1 );
1388 // alternative: low-level byte copying
1389 //memmove( m_arrNode + nFrom + 1, m_arrNode + nFrom, (m_nSize - nFrom) * sizeof(m_arrNode[0]) );
1392 void shift_down( node_type ** pFrom )
1394 assert( m_arrNode <= pFrom && pFrom < m_arrNode + m_nSize);
1396 std::copy( pFrom + 1, m_arrNode + m_nSize, pFrom );
1398 // alternative: low-level byte copying
1399 //memmove( pFrom + 1, pFrom, (m_nSize - nFrom - 1) * sizeof(m_arrNode[0]));
1405 friend class bucket_entry;
1411 iterator( node_type ** p )
1414 iterator( iterator const& it)
1418 iterator& operator=( iterator const& it )
1424 node_type * operator->()
1426 assert( pArr != nullptr );
1429 node_type& operator*()
1431 assert( pArr != nullptr );
1432 assert( *pArr != nullptr );
1437 iterator& operator ++()
1443 bool operator==(iterator const& it ) const
1445 return pArr == it.pArr;
1447 bool operator!=(iterator const& it ) const
1449 return !( *this == it );
1457 memset( m_arrNode, 0, sizeof(m_arrNode));
1458 static_assert(( std::is_same<typename node_type::probeset_type, probeset_type>::value ), "Incompatible node type" );
1463 return iterator(m_arrNode);
1467 return iterator(m_arrNode + size());
1470 void insert_after( iterator it, node_type * p )
1472 assert( m_nSize < c_nCapacity );
1473 assert( !it.pArr || (m_arrNode <= it.pArr && it.pArr <= m_arrNode + m_nSize));
1476 shift_up( (unsigned int)(it.pArr - m_arrNode) + 1 );
1486 void remove( iterator /*itPrev*/, iterator itWhat )
1489 shift_down( itWhat.pArr );
1498 template <typename Disposer>
1499 void clear( Disposer disp )
1501 for ( unsigned int i = 0; i < m_nSize; ++i ) {
1502 disp( m_arrNode[i] );
1507 unsigned int size() const
1513 template <typename Node, unsigned int ArraySize>
1515 static void store( Node * pNode, size_t * pHashes )
1517 memcpy( pNode->m_arrHash, pHashes, sizeof(size_t) * ArraySize );
1519 static bool equal_to( Node& node, unsigned int nTable, size_t nHash )
1521 return node.m_arrHash[nTable] == nHash;
1524 template <typename Node>
1525 struct hash_ops<Node, 0>
1527 static void store( Node * /*pNode*/, size_t * /*pHashes*/ )
1529 static bool equal_to( Node& /*node*/, unsigned int /*nTable*/, size_t /*nHash*/ )
1535 template <typename NodeTraits, bool Ordered>
1538 template <typename NodeTraits>
1539 struct contains<NodeTraits, true>
1541 template <typename BucketEntry, typename Position, typename Q, typename Compare>
1542 static bool find( BucketEntry& probeset, Position& pos, unsigned int /*nTable*/, size_t /*nHash*/, Q const& val, Compare cmp )
1545 typedef typename BucketEntry::iterator bucket_iterator;
1547 bucket_iterator itPrev;
1549 for ( bucket_iterator it = probeset.begin(), itEnd = probeset.end(); it != itEnd; ++it ) {
1550 int cmpRes = cmp( *NodeTraits::to_value_ptr(*it), val );
1551 if ( cmpRes >= 0 ) {
1553 pos.itPrev = itPrev;
1560 pos.itPrev = itPrev;
1561 pos.itFound = probeset.end();
1566 template <typename NodeTraits>
1567 struct contains<NodeTraits, false>
1569 template <typename BucketEntry, typename Position, typename Q, typename EqualTo>
1570 static bool find( BucketEntry& probeset, Position& pos, unsigned int nTable, size_t nHash, Q const& val, EqualTo eq )
1572 // Unordered version
1573 typedef typename BucketEntry::iterator bucket_iterator;
1574 typedef typename BucketEntry::node_type node_type;
1576 bucket_iterator itPrev;
1578 for ( bucket_iterator it = probeset.begin(), itEnd = probeset.end(); it != itEnd; ++it ) {
1579 if ( hash_ops<node_type, node_type::hash_array_size>::equal_to( *it, nTable, nHash ) && eq( *NodeTraits::to_value_ptr(*it), val )) {
1581 pos.itPrev = itPrev;
1587 pos.itPrev = itPrev;
1588 pos.itFound = probeset.end();
1593 } // namespace details
1596 } // namespace cuckoo
1599 /** @ingroup cds_intrusive_map
1602 - [2007] M.Herlihy, N.Shavit, M.Tzafrir "Concurrent Cuckoo Hashing. Technical report"
1603 - [2008] Maurice Herlihy, Nir Shavit "The Art of Multiprocessor Programming"
1605 <b>About Cuckoo hashing</b>
1607 [From <i>"The Art of Multiprocessor Programming"</i>]
1608 Cuckoo hashing is a hashing algorithm in which a newly added item displaces any earlier item
1609 occupying the same slot. For brevity, a table is a k-entry array of items. For a hash set f size
1610 N = 2k we use a two-entry array of tables, and two independent hash functions,
1611 <tt> h0, h1: KeyRange -> 0,...,k-1</tt>
1612 mapping the set of possible keys to entries in he array. To test whether a value \p x is in the set,
1613 <tt>find(x)</tt> tests whether either <tt>table[0][h0(x)]</tt> or <tt>table[1][h1(x)]</tt> is
1614 equal to \p x. Similarly, <tt>erase(x)</tt>checks whether \p x is in either <tt>table[0][h0(x)]</tt>
1615 or <tt>table[1][h1(x)]</tt>, ad removes it if found.
1617 The <tt>insert(x)</tt> successively "kicks out" conflicting items until every key has a slot.
1618 To add \p x, the method swaps \p x with \p y, the current occupant of <tt>table[0][h0(x)]</tt>.
1619 If the prior value was \p nullptr, it is done. Otherwise, it swaps the newly nest-less value \p y
1620 for the current occupant of <tt>table[1][h1(y)]</tt> in the same way. As before, if the prior value
1621 was \p nullptr, it is done. Otherwise, the method continues swapping entries (alternating tables)
1622 until it finds an empty slot. We might not find an empty slot, either because the table is full,
1623 or because the sequence of displacement forms a cycle. We therefore need an upper limit on the
1624 number of successive displacements we are willing to undertake. When this limit is exceeded,
1625 we resize the hash table, choose new hash functions and start over.
1627 For concurrent cuckoo hashing, rather than organizing the set as a two-dimensional table of
1628 items, we use two-dimensional table of probe sets, where a probe set is a constant-sized set
1629 of items with the same hash code. Each probe set holds at most \p PROBE_SIZE items, but the algorithm
1630 tries to ensure that when the set is quiescent (i.e no method call in progress) each probe set
1631 holds no more than <tt>THRESHOLD < PROBE_SET</tt> items. While method calls are in-flight, a probe
1632 set may temporarily hold more than \p THRESHOLD but never more than \p PROBE_SET items.
1634 In current implementation, a probe set can be defined either as a (single-linked) list
1635 or as a fixed-sized vector, optionally ordered.
1637 In description above two-table cuckoo hashing (<tt>k = 2</tt>) has been considered.
1638 We can generalize this approach for <tt>k >= 2</tt> when we have \p k hash functions
1639 <tt>h[0], ... h[k-1]</tt> and \p k tables <tt>table[0], ... table[k-1]</tt>.
1641 The search in probe set is linear, the complexity is <tt> O(PROBE_SET) </tt>.
1642 The probe set may be ordered or not. Ordered probe set can be more efficient since
1643 the average search complexity is <tt>O(PROBE_SET/2)</tt>.
1644 However, the overhead of sorting can eliminate a gain of ordered search.
1646 The probe set is ordered if opt::compare or opt::less is specified in \p Traits template
1647 parameter. Otherwise, the probe set is unordered and \p Traits must contain
1648 opt::equal_to option.
1650 The cds::intrusive::cuckoo namespace contains \p %CuckooSet-related declarations.
1653 - \p T - the type stored in the set. The type must be based on cuckoo::node (for cuckoo::base_hook)
1654 or it must have a member of type %cuckoo::node (for cuckoo::member_hook),
1655 or it must be convertible to \p %cuckoo::node (for cuckoo::traits_hook)
1656 - \p Traits - type traits, default is cuckoo::traits. It is possible to declare option-based
1657 set with \p cuckoo::make_traits metafunction result as \p Traits template argument.
1661 You should incorporate \p cuckoo::node into your struct \p T and provide
1662 appropriate \p cuckoo::traits::hook in your \p Traits template parameters.
1663 Usually, for \p Traits you define a struct based on \p cuckoo::traits.
1665 Example for base hook and list-based probe-set:
1667 #include <cds/intrusive/cuckoo_set.h>
1669 // Data stored in cuckoo set
1670 // We use list as probe-set container and store hash values in the node
1671 // (since we use two hash functions we should store 2 hash values per node)
1672 struct my_data: public cds::intrusive::cuckoo::node< cds::intrusive::cuckoo::list, 2 >
1681 // Provide equal_to functor for my_data since we will use unordered probe-set
1682 struct my_data_equal_to {
1683 bool operator()( const my_data& d1, const my_data& d2 ) const
1685 return d1.strKey.compare( d2.strKey ) == 0;
1688 bool operator()( const my_data& d, const std::string& s ) const
1690 return d.strKey.compare(s) == 0;
1693 bool operator()( const std::string& s, const my_data& d ) const
1695 return s.compare( d.strKey ) == 0;
1699 // Provide two hash functor for my_data
1701 size_t operator()(std::string const& s) const
1703 return cds::opt::v::hash<std::string>( s );
1705 size_t operator()( my_data const& d ) const
1707 return (*this)( d.strKey );
1711 struct hash2: private hash1 {
1712 size_t operator()(std::string const& s) const
1714 size_t h = ~( hash1::operator()(s));
1715 return ~h + 0x9e3779b9 + (h << 6) + (h >> 2);
1717 size_t operator()( my_data const& d ) const
1719 return (*this)( d.strKey );
1723 // Declare type traits
1724 struct my_traits: public cds::intrusive::cuckoo::traits
1726 typedef cds::intrusive::cuckoo::base_hook<
1727 cds::intrusive::cuckoo::probeset_type< my_data::probeset_type >
1728 ,cds::intrusive::cuckoo::store_hash< my_data::hash_array_size >
1730 typedef my_data_equa_to equal_to;
1731 typedef cds::opt::hash_tuple< hash1, hash2 > hash;
1734 // Declare CuckooSet type
1735 typedef cds::intrusive::CuckooSet< my_data, my_traits > my_cuckoo_set;
1737 // Equal option-based declaration
1738 typedef cds::intrusive::CuckooSet< my_data,
1739 cds::intrusive::cuckoo::make_traits<
1740 cds::intrusive::opt::hook< cds::intrusive::cuckoo::base_hook<
1741 cds::intrusive::cuckoo::probeset_type< my_data::probeset_type >
1742 ,cds::intrusive::cuckoo::store_hash< my_data::hash_array_size >
1744 ,cds::opt::hash< std::tuple< hash1, hash2 > >
1745 ,cds::opt::equal_to< my_data_equal_to >
1750 If we provide \p compare function instead of \p equal_to for \p my_data
1751 we get as a result a cuckoo set with ordered probe set that may improve
1753 Example for base hook and ordered vector-based probe-set:
1756 #include <cds/intrusive/cuckoo_set.h>
1758 // Data stored in cuckoo set
1759 // We use a vector of capacity 4 as probe-set container and store hash values in the node
1760 // (since we use two hash functions we should store 2 hash values per node)
1761 struct my_data: public cds::intrusive::cuckoo::node< cds::intrusive::cuckoo::vector<4>, 2 >
1770 // Provide compare functor for my_data since we want to use ordered probe-set
1771 struct my_data_compare {
1772 int operator()( const my_data& d1, const my_data& d2 ) const
1774 return d1.strKey.compare( d2.strKey );
1777 int operator()( const my_data& d, const std::string& s ) const
1779 return d.strKey.compare(s);
1782 int operator()( const std::string& s, const my_data& d ) const
1784 return s.compare( d.strKey );
1788 // Provide two hash functor for my_data
1790 size_t operator()(std::string const& s) const
1792 return cds::opt::v::hash<std::string>( s );
1794 size_t operator()( my_data const& d ) const
1796 return (*this)( d.strKey );
1800 struct hash2: private hash1 {
1801 size_t operator()(std::string const& s) const
1803 size_t h = ~( hash1::operator()(s));
1804 return ~h + 0x9e3779b9 + (h << 6) + (h >> 2);
1806 size_t operator()( my_data const& d ) const
1808 return (*this)( d.strKey );
1812 // Declare type traits
1813 struct my_traits: public cds::intrusive::cuckoo::traits
1815 typedef cds::intrusive::cuckoo::base_hook<
1816 cds::intrusive::cuckoo::probeset_type< my_data::probeset_type >
1817 ,cds::intrusive::cuckoo::store_hash< my_data::hash_array_size >
1819 typedef my_data_compare compare;
1820 typedef cds::opt::hash_tuple< hash1, hash2 > hash;
1823 // Declare CuckooSet type
1824 typedef cds::intrusive::CuckooSet< my_data, my_traits > my_cuckoo_set;
1826 // Equal option-based declaration
1827 typedef cds::intrusive::CuckooSet< my_data,
1828 cds::intrusive::cuckoo::make_traits<
1829 cds::intrusive::opt::hook< cds::intrusive::cuckoo::base_hook<
1830 cds::intrusive::cuckoo::probeset_type< my_data::probeset_type >
1831 ,cds::intrusive::cuckoo::store_hash< my_data::hash_array_size >
1833 ,cds::opt::hash< std::tuple< hash1, hash2 > >
1834 ,cds::opt::compare< my_data_compare >
1840 template <typename T, typename Traits = cuckoo::traits>
1844 typedef T value_type; ///< The value type stored in the set
1845 typedef Traits traits; ///< Set traits
1847 typedef typename traits::hook hook; ///< hook type
1848 typedef typename hook::node_type node_type; ///< node type
1849 typedef typename get_node_traits< value_type, node_type, hook>::type node_traits; ///< node traits
1851 typedef typename traits::hash hash; ///< hash functor tuple wrapped for internal use
1852 typedef typename hash::hash_tuple_type hash_tuple_type; ///< Type of hash tuple
1854 typedef typename traits::stat stat; ///< internal statistics type
1856 typedef typename traits::mutex_policy original_mutex_policy; ///< Concurrent access policy, see \p cuckoo::traits::mutex_policy
1858 /// Actual mutex policy
1860 Actual mutex policy is built from mutex policy type provided by \p Traits template argument (see \p cuckoo::traits::mutex_policy)
1861 but mutex policy internal statistics is conformed with \p cukoo::traits::stat type provided by \p Traits:
1862 - if \p %cuckoo::traits::stat is \p cuckoo::empty_stat then mutex policy statistics is already empty
1863 - otherwise real mutex policy statistics is used
1865 typedef typename original_mutex_policy::template rebind_statistics<
1866 typename std::conditional<
1867 std::is_same< stat, cuckoo::empty_stat >::value
1868 ,typename original_mutex_policy::empty_stat
1869 ,typename original_mutex_policy::real_stat
1871 >::other mutex_policy;
1873 static bool const c_isSorted = !( std::is_same< typename traits::compare, opt::none >::value
1874 && std::is_same< typename traits::less, opt::none >::value ) ; ///< whether the probe set should be ordered
1875 static size_t const c_nArity = hash::size ; ///< the arity of cuckoo hashing: the number of hash functors provided; minimum 2.
1877 /// Key equality functor; used only for unordered probe-set
1878 typedef typename opt::details::make_equal_to< value_type, traits, !c_isSorted>::type key_equal_to;
1880 /// key comparing functor based on opt::compare and opt::less option setter. Used only for ordered probe set
1881 typedef typename opt::details::make_comparator< value_type, traits >::type key_comparator;
1884 typedef typename traits::allocator allocator;
1886 /// item counter type
1887 typedef typename traits::item_counter item_counter;
1890 typedef typename traits::disposer disposer;
1894 typedef typename node_type::probeset_class probeset_class;
1895 typedef typename node_type::probeset_type probeset_type;
1896 static unsigned int const c_nNodeHashArraySize = node_type::hash_array_size;
1898 typedef typename mutex_policy::scoped_cell_lock scoped_cell_lock;
1899 typedef typename mutex_policy::scoped_cell_trylock scoped_cell_trylock;
1900 typedef typename mutex_policy::scoped_full_lock scoped_full_lock;
1901 typedef typename mutex_policy::scoped_resize_lock scoped_resize_lock;
1903 typedef cuckoo::details::bucket_entry< node_type, probeset_type > bucket_entry;
1904 typedef typename bucket_entry::iterator bucket_iterator;
1905 typedef cds::details::Allocator< bucket_entry, allocator > bucket_table_allocator;
1907 typedef size_t hash_array[c_nArity] ; ///< hash array
1910 bucket_iterator itPrev;
1911 bucket_iterator itFound;
1914 typedef typename std::conditional< c_isSorted
1915 , cuckoo::details::contains< node_traits, true >
1916 , cuckoo::details::contains< node_traits, false >
1917 >::type contains_action;
1919 template <typename Predicate>
1920 struct predicate_wrapper {
1921 typedef typename std::conditional< c_isSorted, cds::opt::details::make_comparator_from_less<Predicate>, Predicate>::type type;
1924 typedef typename std::conditional< c_isSorted, key_comparator, key_equal_to >::type key_predicate;
1928 static unsigned int const c_nDefaultProbesetSize = 4; ///< default probeset size
1929 static size_t const c_nDefaultInitialSize = 16; ///< default initial size
1930 static unsigned int const c_nRelocateLimit = c_nArity * 2 - 1; ///< Count of attempts to relocate before giving up
1933 bucket_entry * m_BucketTable[ c_nArity ] ; ///< Bucket tables
1935 size_t m_nBucketMask ; ///< Hash bitmask; bucket table size minus 1.
1936 unsigned int const m_nProbesetSize ; ///< Probe set size
1937 unsigned int const m_nProbesetThreshold ; ///< Probe set threshold
1939 hash m_Hash ; ///< Hash functor tuple
1940 mutex_policy m_MutexPolicy ; ///< concurrent access policy
1941 item_counter m_ItemCounter ; ///< item counter
1942 mutable stat m_Stat ; ///< internal statistics
1946 static void check_common_constraints()
1948 static_assert( (c_nArity == mutex_policy::c_nArity), "The count of hash functors must be equal to mutex_policy arity" );
1951 void check_probeset_properties() const
1953 assert( m_nProbesetThreshold < m_nProbesetSize );
1955 // if probe set type is cuckoo::vector<N> then m_nProbesetSize == N
1956 assert( node_type::probeset_size == 0 || node_type::probeset_size == m_nProbesetSize );
1959 template <typename Q>
1960 void hashing( size_t * pHashes, Q const& v ) const
1962 m_Hash( pHashes, v );
1965 void copy_hash( size_t * pHashes, value_type const& v ) const
1967 if ( c_nNodeHashArraySize )
1968 memcpy( pHashes, node_traits::to_node_ptr( v )->get_hash(), sizeof(pHashes[0]) * c_nNodeHashArraySize );
1970 hashing( pHashes, v );
1973 bucket_entry& bucket( unsigned int nTable, size_t nHash )
1975 assert( nTable < c_nArity );
1976 return m_BucketTable[nTable][nHash & m_nBucketMask];
1979 static void store_hash( node_type * pNode, size_t * pHashes )
1981 cuckoo::details::hash_ops< node_type, c_nNodeHashArraySize >::store( pNode, pHashes );
1984 static bool equal_hash( node_type& node, unsigned int nTable, size_t nHash )
1986 return cuckoo::details::hash_ops< node_type, c_nNodeHashArraySize >::equal_to( node, nTable, nHash );
1989 void allocate_bucket_tables( size_t nSize )
1991 assert( cds::beans::is_power2( nSize ) );
1993 m_nBucketMask = nSize - 1;
1994 bucket_table_allocator alloc;
1995 for ( unsigned int i = 0; i < c_nArity; ++i )
1996 m_BucketTable[i] = alloc.NewArray( nSize );
1999 static void free_bucket_tables( bucket_entry ** pTable, size_t nCapacity )
2001 bucket_table_allocator alloc;
2002 for ( unsigned int i = 0; i < c_nArity; ++i ) {
2003 alloc.Delete( pTable[i], nCapacity );
2004 pTable[i] = nullptr;
2007 void free_bucket_tables()
2009 free_bucket_tables( m_BucketTable, m_nBucketMask + 1 );
2012 static CDS_CONSTEXPR unsigned int const c_nUndefTable = (unsigned int) -1;
2013 template <typename Q, typename Predicate >
2014 unsigned int contains( position * arrPos, size_t * arrHash, Q const& val, Predicate pred )
2016 // Buckets must be locked
2018 for ( unsigned int i = 0; i < c_nArity; ++i ) {
2019 bucket_entry& probeset = bucket( i, arrHash[i] );
2020 if ( contains_action::find( probeset, arrPos[i], i, arrHash[i], val, pred ))
2023 return c_nUndefTable;
2026 template <typename Q, typename Predicate, typename Func>
2027 value_type * erase_( Q const& val, Predicate pred, Func f )
2030 hashing( arrHash, val );
2031 position arrPos[ c_nArity ];
2034 scoped_cell_lock guard( m_MutexPolicy, arrHash );
2036 unsigned int nTable = contains( arrPos, arrHash, val, pred );
2037 if ( nTable != c_nUndefTable ) {
2038 node_type& node = *arrPos[nTable].itFound;
2039 f( *node_traits::to_value_ptr(node) );
2040 bucket( nTable, arrHash[nTable]).remove( arrPos[nTable].itPrev, arrPos[nTable].itFound );
2042 m_Stat.onEraseSuccess();
2043 return node_traits::to_value_ptr( node );
2047 m_Stat.onEraseFailed();
2051 template <typename Q, typename Predicate, typename Func>
2052 bool find_( Q& val, Predicate pred, Func f )
2055 position arrPos[ c_nArity ];
2056 hashing( arrHash, val );
2057 scoped_cell_lock sl( m_MutexPolicy, arrHash );
2059 unsigned int nTable = contains( arrPos, arrHash, val, pred );
2060 if ( nTable != c_nUndefTable ) {
2061 f( *node_traits::to_value_ptr( *arrPos[nTable].itFound ), val );
2062 m_Stat.onFindSuccess();
2066 m_Stat.onFindFailed();
2070 bool relocate( unsigned int nTable, size_t * arrGoalHash )
2072 // arrGoalHash contains hash values for relocating element
2073 // Relocating element is first one from bucket( nTable, arrGoalHash[nTable] ) probeset
2075 m_Stat.onRelocateCall();
2079 for ( unsigned int nRound = 0; nRound < c_nRelocateLimit; ++nRound ) {
2080 m_Stat.onRelocateRound();
2083 scoped_cell_lock guard( m_MutexPolicy, arrGoalHash );
2085 bucket_entry& refBucket = bucket( nTable, arrGoalHash[nTable] );
2086 if ( refBucket.size() < m_nProbesetThreshold ) {
2087 // probeset is not above the threshold
2088 m_Stat.onFalseRelocateRound();
2092 pVal = node_traits::to_value_ptr( *refBucket.begin() );
2093 copy_hash( arrHash, *pVal );
2095 scoped_cell_trylock guard2( m_MutexPolicy, arrHash );
2096 if ( !guard2.locked() )
2097 continue ; // try one more time
2099 refBucket.remove( typename bucket_entry::iterator(), refBucket.begin() );
2101 unsigned int i = (nTable + 1) % c_nArity;
2103 // try insert into free probeset
2104 while ( i != nTable ) {
2105 bucket_entry& bkt = bucket( i, arrHash[i] );
2106 if ( bkt.size() < m_nProbesetThreshold ) {
2108 contains_action::find( bkt, pos, i, arrHash[i], *pVal, key_predicate() ) ; // must return false!
2109 bkt.insert_after( pos.itPrev, node_traits::to_node_ptr( pVal ));
2110 m_Stat.onSuccessRelocateRound();
2113 i = ( i + 1 ) % c_nArity;
2116 // try insert into partial probeset
2117 i = (nTable + 1) % c_nArity;
2118 while ( i != nTable ) {
2119 bucket_entry& bkt = bucket( i, arrHash[i] );
2120 if ( bkt.size() < m_nProbesetSize ) {
2122 contains_action::find( bkt, pos, i, arrHash[i], *pVal, key_predicate() ) ; // must return false!
2123 bkt.insert_after( pos.itPrev, node_traits::to_node_ptr( pVal ));
2125 memcpy( arrGoalHash, arrHash, sizeof(arrHash));
2126 m_Stat.onRelocateAboveThresholdRound();
2127 goto next_iteration;
2129 i = (i + 1) % c_nArity;
2132 // all probeset is full, relocating fault
2133 refBucket.insert_after( typename bucket_entry::iterator(), node_traits::to_node_ptr( pVal ));
2134 m_Stat.onFailedRelocate();
2145 m_Stat.onResizeCall();
2147 size_t nOldCapacity = bucket_count();
2148 bucket_entry * pOldTable[ c_nArity ];
2150 scoped_resize_lock guard( m_MutexPolicy );
2152 if ( nOldCapacity != bucket_count() ) {
2153 m_Stat.onFalseResizeCall();
2157 size_t nCapacity = nOldCapacity * 2;
2159 m_MutexPolicy.resize( nCapacity );
2160 memcpy( pOldTable, m_BucketTable, sizeof(pOldTable));
2161 allocate_bucket_tables( nCapacity );
2163 typedef typename bucket_entry::iterator bucket_iterator;
2165 position arrPos[ c_nArity ];
2167 for ( unsigned int nTable = 0; nTable < c_nArity; ++nTable ) {
2168 bucket_entry * pTable = pOldTable[nTable];
2169 for ( size_t k = 0; k < nOldCapacity; ++k ) {
2170 bucket_iterator itNext;
2171 for ( bucket_iterator it = pTable[k].begin(), itEnd = pTable[k].end(); it != itEnd; it = itNext ) {
2175 value_type& val = *node_traits::to_value_ptr( *it );
2176 copy_hash( arrHash, val );
2177 contains( arrPos, arrHash, val, key_predicate() ) ; // must return c_nUndefTable
2179 for ( unsigned int i = 0; i < c_nArity; ++i ) {
2180 bucket_entry& refBucket = bucket( i, arrHash[i] );
2181 if ( refBucket.size() < m_nProbesetThreshold ) {
2182 refBucket.insert_after( arrPos[i].itPrev, &*it );
2183 m_Stat.onResizeSuccessMove();
2188 for ( unsigned int i = 0; i < c_nArity; ++i ) {
2189 bucket_entry& refBucket = bucket( i, arrHash[i] );
2190 if ( refBucket.size() < m_nProbesetSize ) {
2191 refBucket.insert_after( arrPos[i].itPrev, &*it );
2192 assert( refBucket.size() > 1 );
2193 copy_hash( arrHash, *node_traits::to_value_ptr( *refBucket.begin()) );
2194 m_Stat.onResizeRelocateCall();
2195 relocate( i, arrHash );
2204 free_bucket_tables( pOldTable, nOldCapacity );
2207 CDS_CONSTEXPR static unsigned int calc_probeset_size( unsigned int nProbesetSize ) CDS_NOEXCEPT
2209 return nProbesetSize
2211 : ( node_type::probeset_size ? node_type::probeset_size : c_nDefaultProbesetSize )
2217 /// Default constructor
2219 Initial size = \ref c_nDefaultInitialSize
2222 - \p c_nDefaultProbesetSize if \p probeset_type is \p cuckoo::list
2223 - \p Capacity if \p probeset_type is <tt> cuckoo::vector<Capacity> </tt>
2225 Probe set threshold = probe set size - 1
2228 : m_nProbesetSize( calc_probeset_size(0) )
2229 , m_nProbesetThreshold( m_nProbesetSize - 1 )
2230 , m_MutexPolicy( c_nDefaultInitialSize )
2232 check_common_constraints();
2233 check_probeset_properties();
2235 allocate_bucket_tables( c_nDefaultInitialSize );
2238 /// Constructs the set object with given probe set size and threshold
2240 If probe set type is <tt> cuckoo::vector<Capacity> </tt> vector
2241 then \p nProbesetSize should be equal to vector's \p Capacity.
2244 size_t nInitialSize ///< Initial set size; if 0 - use default initial size \ref c_nDefaultInitialSize
2245 , unsigned int nProbesetSize ///< probe set size
2246 , unsigned int nProbesetThreshold = 0 ///< probe set threshold, <tt>nProbesetThreshold < nProbesetSize</tt>. If 0, nProbesetThreshold = nProbesetSize - 1
2248 : m_nProbesetSize( calc_probeset_size(nProbesetSize) )
2249 , m_nProbesetThreshold( nProbesetThreshold ? nProbesetThreshold : m_nProbesetSize - 1 )
2250 , m_MutexPolicy( cds::beans::ceil2(nInitialSize ? nInitialSize : c_nDefaultInitialSize ))
2252 check_common_constraints();
2253 check_probeset_properties();
2255 allocate_bucket_tables( nInitialSize ? cds::beans::ceil2( nInitialSize ) : c_nDefaultInitialSize );
2258 /// Constructs the set object with given hash functor tuple
2260 The probe set size and threshold are set as default, see CuckooSet()
2263 hash_tuple_type const& h ///< hash functor tuple of type <tt>std::tuple<H1, H2, ... Hn></tt> where <tt> n == \ref c_nArity </tt>
2265 : m_nProbesetSize( calc_probeset_size(0) )
2266 , m_nProbesetThreshold( m_nProbesetSize -1 )
2268 , m_MutexPolicy( c_nDefaultInitialSize )
2270 check_common_constraints();
2271 check_probeset_properties();
2273 allocate_bucket_tables( c_nDefaultInitialSize );
2276 /// Constructs the set object with given probe set properties and hash functor tuple
2278 If probe set type is <tt> cuckoo::vector<Capacity> </tt> vector
2279 then \p nProbesetSize should be equal to vector's \p Capacity.
2282 size_t nInitialSize ///< Initial set size; if 0 - use default initial size \ref c_nDefaultInitialSize
2283 , unsigned int nProbesetSize ///< probe set size, positive integer
2284 , unsigned int nProbesetThreshold ///< probe set threshold, <tt>nProbesetThreshold < nProbesetSize</tt>. If 0, nProbesetThreshold = nProbesetSize - 1
2285 , hash_tuple_type const& h ///< hash functor tuple of type <tt>std::tuple<H1, H2, ... Hn></tt> where <tt> n == \ref c_nArity </tt>
2287 : m_nProbesetSize( calc_probeset_size(nProbesetSize) )
2288 , m_nProbesetThreshold( nProbesetThreshold ? nProbesetThreshold : m_nProbesetSize - 1)
2290 , m_MutexPolicy( cds::beans::ceil2(nInitialSize ? nInitialSize : c_nDefaultInitialSize ))
2292 check_common_constraints();
2293 check_probeset_properties();
2295 allocate_bucket_tables( nInitialSize ? cds::beans::ceil2( nInitialSize ) : c_nDefaultInitialSize );
2298 /// Constructs the set object with given hash functor tuple (move semantics)
2300 The probe set size and threshold are set as default, see CuckooSet()
2303 hash_tuple_type&& h ///< hash functor tuple of type <tt>std::tuple<H1, H2, ... Hn></tt> where <tt> n == \ref c_nArity </tt>
2305 : m_nProbesetSize( calc_probeset_size(0) )
2306 , m_nProbesetThreshold( m_nProbesetSize / 2 )
2307 , m_Hash( std::forward<hash_tuple_type>(h) )
2308 , m_MutexPolicy( c_nDefaultInitialSize )
2310 check_common_constraints();
2311 check_probeset_properties();
2313 allocate_bucket_tables( c_nDefaultInitialSize );
2316 /// Constructs the set object with given probe set properties and hash functor tuple (move semantics)
2318 If probe set type is <tt> cuckoo::vector<Capacity> </tt> vector
2319 then \p nProbesetSize should be equal to vector's \p Capacity.
2322 size_t nInitialSize ///< Initial set size; if 0 - use default initial size \ref c_nDefaultInitialSize
2323 , unsigned int nProbesetSize ///< probe set size, positive integer
2324 , unsigned int nProbesetThreshold ///< probe set threshold, <tt>nProbesetThreshold < nProbesetSize</tt>. If 0, nProbesetThreshold = nProbesetSize - 1
2325 , hash_tuple_type&& h ///< hash functor tuple of type <tt>std::tuple<H1, H2, ... Hn></tt> where <tt> n == \ref c_nArity </tt>
2327 : m_nProbesetSize( calc_probeset_size(nProbesetSize) )
2328 , m_nProbesetThreshold( nProbesetThreshold ? nProbesetThreshold : m_nProbesetSize - 1)
2329 , m_Hash( std::forward<hash_tuple_type>(h) )
2330 , m_MutexPolicy( cds::beans::ceil2(nInitialSize ? nInitialSize : c_nDefaultInitialSize ))
2332 check_common_constraints();
2333 check_probeset_properties();
2335 allocate_bucket_tables( nInitialSize ? cds::beans::ceil2( nInitialSize ) : c_nDefaultInitialSize );
2341 free_bucket_tables();
2345 /// Inserts new node
2347 The function inserts \p val in the set if it does not contain
2348 an item with key equal to \p val.
2350 Returns \p true if \p val is placed into the set, \p false otherwise.
2352 bool insert( value_type& val )
2354 return insert( val, []( value_type& ) {} );
2357 /// Inserts new node
2359 The function allows to split creating of new item into two part:
2360 - create item with key only
2361 - insert new item into the set
2362 - if inserting is success, calls \p f functor to initialize value-field of \p val.
2364 The functor signature is:
2366 void func( value_type& val );
2368 where \p val is the item inserted.
2370 The user-defined functor is called only if the inserting is success.
2372 template <typename Func>
2373 bool insert( value_type& val, Func f )
2376 position arrPos[ c_nArity ];
2377 unsigned int nGoalTable;
2379 hashing( arrHash, val );
2380 node_type * pNode = node_traits::to_node_ptr( val );
2381 store_hash( pNode, arrHash );
2385 scoped_cell_lock guard( m_MutexPolicy, arrHash );
2387 if ( contains( arrPos, arrHash, val, key_predicate() ) != c_nUndefTable ) {
2388 m_Stat.onInsertFailed();
2392 for ( unsigned int i = 0; i < c_nArity; ++i ) {
2393 bucket_entry& refBucket = bucket( i, arrHash[i] );
2394 if ( refBucket.size() < m_nProbesetThreshold ) {
2395 refBucket.insert_after( arrPos[i].itPrev, pNode );
2398 m_Stat.onInsertSuccess();
2403 for ( unsigned int i = 0; i < c_nArity; ++i ) {
2404 bucket_entry& refBucket = bucket( i, arrHash[i] );
2405 if ( refBucket.size() < m_nProbesetSize ) {
2406 refBucket.insert_after( arrPos[i].itPrev, pNode );
2410 assert( refBucket.size() > 1 );
2411 copy_hash( arrHash, *node_traits::to_value_ptr( *refBucket.begin()) );
2417 m_Stat.onInsertResize();
2422 m_Stat.onInsertRelocate();
2423 if ( !relocate( nGoalTable, arrHash )) {
2424 m_Stat.onInsertRelocateFault();
2425 m_Stat.onInsertResize();
2429 m_Stat.onInsertSuccess();
2433 /// Updates the node
2435 The operation performs inserting or changing data with lock-free manner.
2437 If the item \p val is not found in the set, then \p val is inserted into the set
2438 iff \p bAllowInsert is \p true.
2439 Otherwise, the functor \p func is called with item found.
2440 The functor \p func signature is:
2442 void func( bool bNew, value_type& item, value_type& val );
2445 - \p bNew - \p true if the item has been inserted, \p false otherwise
2446 - \p item - item of the set
2447 - \p val - argument \p val passed into the \p %update() function
2448 If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
2449 refer to the same thing.
2451 The functor may change non-key fields of the \p item.
2453 Returns std::pair<bool, bool> where \p first is \p true if operation is successfull,
2454 i.e. the node has been inserted or updated,
2455 \p second is \p true if new item has been added or \p false if the item with \p key
2458 template <typename Func>
2459 std::pair<bool, bool> update( value_type& val, Func func, bool bAllowInsert = true )
2462 position arrPos[ c_nArity ];
2463 unsigned int nGoalTable;
2465 hashing( arrHash, val );
2466 node_type * pNode = node_traits::to_node_ptr( val );
2467 store_hash( pNode, arrHash );
2471 scoped_cell_lock guard( m_MutexPolicy, arrHash );
2473 unsigned int nTable = contains( arrPos, arrHash, val, key_predicate() );
2474 if ( nTable != c_nUndefTable ) {
2475 func( false, *node_traits::to_value_ptr( *arrPos[nTable].itFound ), val );
2476 m_Stat.onUpdateExist();
2477 return std::make_pair( true, false );
2480 if ( !bAllowInsert )
2481 return std::make_pair( false, false );
2483 //node_type * pNode = node_traits::to_node_ptr( val );
2484 //store_hash( pNode, arrHash );
2486 for ( unsigned int i = 0; i < c_nArity; ++i ) {
2487 bucket_entry& refBucket = bucket( i, arrHash[i] );
2488 if ( refBucket.size() < m_nProbesetThreshold ) {
2489 refBucket.insert_after( arrPos[i].itPrev, pNode );
2490 func( true, val, val );
2492 m_Stat.onUpdateSuccess();
2493 return std::make_pair( true, true );
2497 for ( unsigned int i = 0; i < c_nArity; ++i ) {
2498 bucket_entry& refBucket = bucket( i, arrHash[i] );
2499 if ( refBucket.size() < m_nProbesetSize ) {
2500 refBucket.insert_after( arrPos[i].itPrev, pNode );
2501 func( true, val, val );
2504 assert( refBucket.size() > 1 );
2505 copy_hash( arrHash, *node_traits::to_value_ptr( *refBucket.begin()) );
2511 m_Stat.onUpdateResize();
2516 m_Stat.onUpdateRelocate();
2517 if ( !relocate( nGoalTable, arrHash )) {
2518 m_Stat.onUpdateRelocateFault();
2519 m_Stat.onUpdateResize();
2523 m_Stat.onUpdateSuccess();
2524 return std::make_pair( true, true );
2527 // Deprecated, use update()
2528 template <typename Func>
2529 std::pair<bool, bool> ensure( value_type& val, Func func )
2531 return update( val, func, true );
2535 /// Unlink the item \p val from the set
2537 The function searches the item \p val in the set and unlink it
2538 if it is found and is equal to \p val (here, the equality means that
2539 \p val belongs to the set: if \p item is an item found then
2540 unlink is successful iif <tt>&val == &item</tt>)
2542 The function returns \p true if success and \p false otherwise.
2544 bool unlink( value_type& val )
2547 hashing( arrHash, val );
2548 position arrPos[ c_nArity ];
2551 scoped_cell_lock guard( m_MutexPolicy, arrHash );
2553 unsigned int nTable = contains( arrPos, arrHash, val, key_predicate() );
2554 if ( nTable != c_nUndefTable && node_traits::to_value_ptr(*arrPos[nTable].itFound) == &val ) {
2555 bucket( nTable, arrHash[nTable]).remove( arrPos[nTable].itPrev, arrPos[nTable].itFound );
2557 m_Stat.onUnlinkSuccess();
2562 m_Stat.onUnlinkFailed();
2566 /// Deletes the item from the set
2567 /** \anchor cds_intrusive_CuckooSet_erase
2568 The function searches an item with key equal to \p val in the set,
2569 unlinks it from the set, and returns a pointer to unlinked item.
2571 If the item with key equal to \p val is not found the function return \p nullptr.
2573 Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
2575 template <typename Q>
2576 value_type * erase( Q const& val )
2578 return erase( val, [](value_type const&) {} );
2581 /// Deletes the item from the set using \p pred predicate for searching
2583 The function is an analog of \ref cds_intrusive_CuckooSet_erase "erase(Q const&)"
2584 but \p pred is used for key comparing.
2585 If cuckoo set is ordered, then \p Predicate should have the interface and semantics like \p std::less.
2586 If cuckoo set is unordered, then \p Predicate should have the interface and semantics like \p std::equal_to.
2587 \p Predicate must imply the same element order as the comparator used for building the set.
2589 template <typename Q, typename Predicate>
2590 value_type * erase_with( Q const& val, Predicate pred )
2593 return erase_( val, typename predicate_wrapper<Predicate>::type(), [](value_type const&) {} );
2596 /// Delete the item from the set
2597 /** \anchor cds_intrusive_CuckooSet_erase_func
2598 The function searches an item with key equal to \p val in the set,
2599 call \p f functor with item found, unlinks it from the set, and returns a pointer to unlinked item.
2601 The \p Func interface is
2604 void operator()( value_type const& item );
2608 If the item with key equal to \p val is not found the function return \p nullptr.
2610 Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
2612 template <typename Q, typename Func>
2613 value_type * erase( Q const& val, Func f )
2615 return erase_( val, key_predicate(), f );
2618 /// Deletes the item from the set using \p pred predicate for searching
2620 The function is an analog of \ref cds_intrusive_CuckooSet_erase_func "erase(Q const&, Func)"
2621 but \p pred is used for key comparing.
2622 If you use ordered cuckoo set, then \p Predicate should have the interface and semantics like \p std::less.
2623 If you use unordered cuckoo set, then \p Predicate should have the interface and semantics like \p std::equal_to.
2624 \p Predicate must imply the same element order as the comparator used for building the set.
2626 template <typename Q, typename Predicate, typename Func>
2627 value_type * erase_with( Q const& val, Predicate pred, Func f )
2630 return erase_( val, typename predicate_wrapper<Predicate>::type(), f );
2633 /// Find the key \p val
2634 /** \anchor cds_intrusive_CuckooSet_find_func
2635 The function searches the item with key equal to \p val and calls the functor \p f for item found.
2636 The interface of \p Func functor is:
2639 void operator()( value_type& item, Q& val );
2642 where \p item is the item found, \p val is the <tt>find</tt> function argument.
2644 The functor may change non-key fields of \p item.
2646 The \p val argument is non-const since it can be used as \p f functor destination i.e., the functor
2647 may modify both arguments.
2649 Note the hash functor specified for class \p Traits template parameter
2650 should accept a parameter of type \p Q that can be not the same as \p value_type.
2652 The function returns \p true if \p val is found, \p false otherwise.
2654 template <typename Q, typename Func>
2655 bool find( Q& val, Func f )
2657 return find_( val, key_predicate(), f );
2660 template <typename Q, typename Func>
2661 bool find( Q const& val, Func f )
2663 return find_( val, key_predicate(), f );
2667 /// Find the key \p val using \p pred predicate for comparing
2669 The function is an analog of \ref cds_intrusive_CuckooSet_find_func "find(Q&, Func)"
2670 but \p pred is used for key comparison.
2671 If you use ordered cuckoo set, then \p Predicate should have the interface and semantics like \p std::less.
2672 If you use unordered cuckoo set, then \p Predicate should have the interface and semantics like \p std::equal_to.
2673 \p pred must imply the same element order as the comparator used for building the set.
2675 template <typename Q, typename Predicate, typename Func>
2676 bool find_with( Q& val, Predicate pred, Func f )
2679 return find_( val, typename predicate_wrapper<Predicate>::type(), f );
2682 template <typename Q, typename Predicate, typename Func>
2683 bool find_with( Q const& val, Predicate pred, Func f )
2686 return find_( val, typename predicate_wrapper<Predicate>::type(), f );
2690 /// Checks whether the set contains \p key
2692 The function searches the item with key equal to \p key
2693 and returns \p true if it is found, and \p false otherwise.
2695 template <typename Q>
2696 bool contains( Q const& key )
2698 return find( key, [](value_type&, Q const& ) {} );
2701 // Deprecated, use contains()
2702 template <typename Q>
2703 bool find( Q const& key )
2705 return contains( key );
2709 /// Checks whether the set contains \p key using \p pred predicate for searching
2711 The function is similar to <tt>contains( key )</tt> but \p pred is used for key comparing.
2712 \p Less functor has the interface like \p std::less.
2713 \p Less must imply the same element order as the comparator used for building the set.
2715 template <typename Q, typename Predicate>
2716 bool contains( Q const& key, Predicate pred )
2719 return find_with( key, typename predicate_wrapper<Predicate>::type(), [](value_type& , Q const& ) {} );
2722 // Deprecated,use contains()
2723 template <typename Q, typename Predicate>
2724 bool find_with( Q const& key, Predicate pred )
2726 return contains( key, pred );
2732 The function unlinks all items from the set.
2733 For any item \ref disposer is called
2737 clear_and_dispose( disposer() );
2740 /// Clears the set and calls \p disposer for each item
2742 The function unlinks all items from the set calling \p disposer for each item.
2743 \p Disposer functor interface is:
2746 void operator()( value_type * p );
2750 The \ref disposer specified in \p Traits traits is not called.
2752 template <typename Disposer>
2753 void clear_and_dispose( Disposer oDisposer )
2755 // locks entire array
2756 scoped_full_lock sl( m_MutexPolicy );
2758 for ( unsigned int i = 0; i < c_nArity; ++i ) {
2759 bucket_entry * pEntry = m_BucketTable[i];
2760 bucket_entry * pEnd = pEntry + m_nBucketMask + 1;
2761 for ( ; pEntry != pEnd ; ++pEntry ) {
2762 pEntry->clear( [&oDisposer]( node_type * pNode ){ oDisposer( node_traits::to_value_ptr( pNode )) ; } );
2765 m_ItemCounter.reset();
2768 /// Checks if the set is empty
2770 Emptiness is checked by item counting: if item count is zero then the set is empty.
2777 /// Returns item count in the set
2780 return m_ItemCounter;
2783 /// Returns the size of hash table
2785 The hash table size is non-constant and can be increased via resizing.
2787 size_t bucket_count() const
2789 return m_nBucketMask + 1;
2792 /// Returns lock array size
2793 size_t lock_count() const
2795 return m_MutexPolicy.lock_count();
2798 /// Returns const reference to internal statistics
2799 stat const& statistics() const
2804 /// Returns const reference to mutex policy internal statistics
2805 typename mutex_policy::statistics_type const& mutex_policy_statistics() const
2807 return m_MutexPolicy.statistics();
2810 }} // namespace cds::intrusive
2812 #endif // #ifndef CDSLIB_INTRUSIVE_CUCKOO_SET_H