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 \p 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 scoped_spinlock sl(m_access);
922 for ( unsigned int i = 0; i < c_nArity; ++i )
923 m_arrLocks[i] = pNew[i];
925 m_nCapacity.store( nCapacity, atomics::memory_order_release );
931 /// Returns lock array size
933 Lock array size is not a constant for \p refinable policy and can be changed when the set is resized.
935 size_t lock_count() const
937 return m_nCapacity.load(atomics::memory_order_relaxed);
940 /// Returns the arity of \p refinable mutex policy
941 CDS_CONSTEXPR unsigned int arity() const CDS_NOEXCEPT
946 /// Returns internal statistics
947 statistics_type const& statistics() const
953 /// CuckooSet internal statistics
955 typedef cds::atomicity::event_counter counter_type ; ///< Counter type
957 counter_type m_nRelocateCallCount ; ///< Count of \p relocate function call
958 counter_type m_nRelocateRoundCount ; ///< Count of attempts to relocate items
959 counter_type m_nFalseRelocateCount ; ///< Count of unneeded attempts of \p relocate call
960 counter_type m_nSuccessRelocateCount ; ///< Count of successfull item relocating
961 counter_type m_nRelocateAboveThresholdCount; ///< Count of item relocating above probeset threshold
962 counter_type m_nFailedRelocateCount ; ///< Count of failed relocation attemp (when all probeset is full)
964 counter_type m_nResizeCallCount ; ///< Count of \p resize function call
965 counter_type m_nFalseResizeCount ; ///< Count of false \p resize function call (when other thread has been resized the set)
966 counter_type m_nResizeSuccessNodeMove; ///< Count of successfull node moving when resizing
967 counter_type m_nResizeRelocateCall ; ///< Count of \p relocate function call from \p resize function
969 counter_type m_nInsertSuccess ; ///< Count of successfull \p insert function call
970 counter_type m_nInsertFailed ; ///< Count of failed \p insert function call
971 counter_type m_nInsertResizeCount ; ///< Count of \p resize function call from \p insert
972 counter_type m_nInsertRelocateCount ; ///< Count of \p relocate function call from \p insert
973 counter_type m_nInsertRelocateFault ; ///< Count of failed \p relocate function call from \p insert
975 counter_type m_nUpdateExistCount ; ///< Count of call \p update() function for existing node
976 counter_type m_nUpdateSuccessCount ; ///< Count of successfull \p insert function call for new node
977 counter_type m_nUpdateResizeCount ; ///< Count of \p resize function call from \p update()
978 counter_type m_nUpdateRelocateCount ; ///< Count of \p relocate function call from \p update()
979 counter_type m_nUpdateRelocateFault ; ///< Count of failed \p relocate function call from \p update()
981 counter_type m_nUnlinkSuccess ; ///< Count of success \p unlink function call
982 counter_type m_nUnlinkFailed ; ///< Count of failed \p unlink function call
984 counter_type m_nEraseSuccess ; ///< Count of success \p erase function call
985 counter_type m_nEraseFailed ; ///< Count of failed \p erase function call
987 counter_type m_nFindSuccess ; ///< Count of success \p find function call
988 counter_type m_nFindFailed ; ///< Count of failed \p find function call
990 counter_type m_nFindEqualSuccess ; ///< Count of success \p find_equal function call
991 counter_type m_nFindEqualFailed ; ///< Count of failed \p find_equal function call
993 counter_type m_nFindWithSuccess ; ///< Count of success \p find_with function call
994 counter_type m_nFindWithFailed ; ///< Count of failed \p find_with function call
997 void onRelocateCall() { ++m_nRelocateCallCount; }
998 void onRelocateRound() { ++m_nRelocateRoundCount; }
999 void onFalseRelocateRound() { ++m_nFalseRelocateCount; }
1000 void onSuccessRelocateRound(){ ++m_nSuccessRelocateCount; }
1001 void onRelocateAboveThresholdRound() { ++m_nRelocateAboveThresholdCount; }
1002 void onFailedRelocate() { ++m_nFailedRelocateCount; }
1004 void onResizeCall() { ++m_nResizeCallCount; }
1005 void onFalseResizeCall() { ++m_nFalseResizeCount; }
1006 void onResizeSuccessMove() { ++m_nResizeSuccessNodeMove; }
1007 void onResizeRelocateCall() { ++m_nResizeRelocateCall; }
1009 void onInsertSuccess() { ++m_nInsertSuccess; }
1010 void onInsertFailed() { ++m_nInsertFailed; }
1011 void onInsertResize() { ++m_nInsertResizeCount; }
1012 void onInsertRelocate() { ++m_nInsertRelocateCount; }
1013 void onInsertRelocateFault() { ++m_nInsertRelocateFault; }
1015 void onUpdateExist() { ++m_nUpdateExistCount; }
1016 void onUpdateSuccess() { ++m_nUpdateSuccessCount; }
1017 void onUpdateResize() { ++m_nUpdateResizeCount; }
1018 void onUpdateRelocate() { ++m_nUpdateRelocateCount; }
1019 void onUpdateRelocateFault() { ++m_nUpdateRelocateFault; }
1021 void onUnlinkSuccess() { ++m_nUnlinkSuccess; }
1022 void onUnlinkFailed() { ++m_nUnlinkFailed; }
1024 void onEraseSuccess() { ++m_nEraseSuccess; }
1025 void onEraseFailed() { ++m_nEraseFailed; }
1027 void onFindSuccess() { ++m_nFindSuccess; }
1028 void onFindFailed() { ++m_nFindFailed; }
1030 void onFindWithSuccess() { ++m_nFindWithSuccess; }
1031 void onFindWithFailed() { ++m_nFindWithFailed; }
1035 /// CuckooSet empty internal statistics
1038 void onRelocateCall() const {}
1039 void onRelocateRound() const {}
1040 void onFalseRelocateRound() const {}
1041 void onSuccessRelocateRound()const {}
1042 void onRelocateAboveThresholdRound() const {}
1043 void onFailedRelocate() const {}
1045 void onResizeCall() const {}
1046 void onFalseResizeCall() const {}
1047 void onResizeSuccessMove() const {}
1048 void onResizeRelocateCall() const {}
1050 void onInsertSuccess() const {}
1051 void onInsertFailed() const {}
1052 void onInsertResize() const {}
1053 void onInsertRelocate() const {}
1054 void onInsertRelocateFault() const {}
1056 void onUpdateExist() const {}
1057 void onUpdateSuccess() const {}
1058 void onUpdateResize() const {}
1059 void onUpdateRelocate() const {}
1060 void onUpdateRelocateFault() const {}
1062 void onUnlinkSuccess() const {}
1063 void onUnlinkFailed() const {}
1065 void onEraseSuccess() const {}
1066 void onEraseFailed() const {}
1068 void onFindSuccess() const {}
1069 void onFindFailed() const {}
1071 void onFindWithSuccess() const {}
1072 void onFindWithFailed() const {}
1076 /// Type traits for CuckooSet class
1081 Possible values are: cuckoo::base_hook, cuckoo::member_hook, cuckoo::traits_hook.
1083 typedef base_hook<> hook;
1085 /// Hash functors tuple
1087 This is mandatory type and has no predefined one.
1089 At least, two hash functors should be provided. All hash functor
1090 should be orthogonal (different): for each <tt> i,j: i != j => h[i](x) != h[j](x) </tt>.
1091 The hash functors are defined as <tt> std::tuple< H1, H2, ... Hn > </tt>:
1092 \@code cds::opt::hash< std::tuple< h1, h2 > > \@endcode
1093 The number of hash functors specifies the number \p k - the count of hash tables in cuckoo hashing.
1095 To specify hash tuple in traits you should use \p cds::opt::hash_tuple:
1097 struct my_traits: public cds::intrusive::cuckoo::traits {
1098 typedef cds::opt::hash_tuple< hash1, hash2 > hash;
1102 typedef cds::opt::none hash;
1104 /// Concurrent access policy
1106 Available opt::mutex_policy types:
1107 - \p cuckoo::striping - simple, but the lock array is not resizable
1108 - \p cuckoo::refinable - resizable lock array, but more complex access to set data.
1110 Default is \p cuckoo::striping.
1112 typedef cuckoo::striping<> mutex_policy;
1114 /// Key equality functor
1116 Default is <tt>std::equal_to<T></tt>
1118 typedef opt::none equal_to;
1120 /// Key comparing functor
1122 No default functor is provided. If the option is not specified, the \p less is used.
1124 typedef opt::none compare;
1126 /// specifies binary predicate used for key comparison.
1128 Default is \p std::less<T>.
1130 typedef opt::none less;
1134 The type for item counting feature.
1135 Default is \p cds::atomicity::item_counter
1137 Only atomic item counter type is allowed.
1139 typedef atomicity::item_counter item_counter;
1143 The allocator type for allocating bucket tables.
1145 typedef CDS_DEFAULT_ALLOCATOR allocator;
1149 The disposer functor is used in \p CuckooSet::clear() member function
1152 typedef intrusive::opt::v::empty_disposer disposer;
1154 /// Internal statistics. Available statistics: \p cuckoo::stat, \p cuckoo::empty_stat
1155 typedef empty_stat stat;
1158 /// Metafunction converting option list to \p CuckooSet traits
1160 Template argument list \p Options... are:
1161 - \p intrusive::opt::hook - hook used. Possible values are: \p cuckoo::base_hook, \p cuckoo::member_hook,
1162 \p cuckoo::traits_hook.
1163 If the option is not specified, <tt>%cuckoo::base_hook<></tt> is used.
1164 - \p opt::hash - hash functor tuple, mandatory option. At least, two hash functors should be provided. All hash functor
1165 should be orthogonal (different): for each <tt> i,j: i != j => h[i](x) != h[j](x) </tt>.
1166 The hash functors are passed as <tt> std::tuple< H1, H2, ... Hn > </tt>. The number of hash functors specifies
1167 the number \p k - the count of hash tables in cuckoo hashing.
1168 - \p opt::mutex_policy - concurrent access policy.
1169 Available policies: \p cuckoo::striping, \p cuckoo::refinable.
1170 Default is \p %cuckoo::striping.
1171 - \p opt::equal_to - key equality functor like \p std::equal_to.
1172 If this functor is defined then the probe-set will be unordered.
1173 If \p %opt::compare or \p %opt::less option is specified too, then the probe-set will be ordered
1174 and \p %opt::equal_to will be ignored.
1175 - \p opt::compare - key comparison functor. No default functor is provided.
1176 If the option is not specified, the \p %opt::less is used.
1177 If \p %opt::compare or \p %opt::less option is specified, then the probe-set will be ordered.
1178 - \p opt::less - specifies binary predicate used for key comparison. Default is \p std::less<T>.
1179 If \p %opt::compare or \p %opt::less option is specified, then the probe-set will be ordered.
1180 - \p opt::item_counter - the type of item counting feature. Default is \p atomicity::item_counter
1181 The item counter should be atomic.
1182 - \p opt::allocator - the allocator type using for allocating bucket tables.
1183 Default is \ref CDS_DEFAULT_ALLOCATOR
1184 - \p intrusive::opt::disposer - the disposer type used in \p clear() member function for
1185 freeing nodes. Default is \p intrusive::opt::v::empty_disposer
1186 - \p opt::stat - internal statistics. Possibly types: \p cuckoo::stat, \p cuckoo::empty_stat.
1187 Default is \p %cuckoo::empty_stat
1189 The probe set traits \p cuckoo::probeset_type and \p cuckoo::store_hash are taken from \p node type
1190 specified by \p opt::hook option.
1192 template <typename... Options>
1193 struct make_traits {
1194 typedef typename cds::opt::make_options<
1195 typename cds::opt::find_type_traits< cuckoo::traits, Options... >::type
1197 >::type type ; ///< Result of metafunction
1202 template <typename Node, typename Probeset>
1205 template <typename Node>
1206 class bucket_entry<Node, cuckoo::list>
1209 typedef Node node_type;
1210 typedef cuckoo::list_probeset_class probeset_class;
1211 typedef cuckoo::list probeset_type;
1221 friend class bucket_entry;
1227 iterator( node_type * p )
1230 iterator( iterator const& it)
1234 iterator& operator=( iterator const& it )
1240 iterator& operator=( node_type * p )
1246 node_type * operator->()
1250 node_type& operator*()
1252 assert( pNode != nullptr );
1257 iterator& operator ++()
1260 pNode = pNode->m_pNext;
1264 bool operator==(iterator const& it ) const
1266 return pNode == it.pNode;
1268 bool operator!=(iterator const& it ) const
1270 return !( *this == it );
1279 static_assert(( std::is_same<typename node_type::probeset_type, probeset_type>::value ), "Incompatible node type" );
1284 return iterator(pHead);
1291 void insert_after( iterator it, node_type * p )
1293 node_type * pPrev = it.pNode;
1295 p->m_pNext = pPrev->m_pNext;
1306 void remove( iterator itPrev, iterator itWhat )
1308 node_type * pPrev = itPrev.pNode;
1309 node_type * pWhat = itWhat.pNode;
1310 assert( (!pPrev && pWhat == pHead) || (pPrev && pPrev->m_pNext == pWhat) );
1313 pPrev->m_pNext = pWhat->m_pNext;
1315 assert( pWhat == pHead );
1316 pHead = pHead->m_pNext;
1325 for ( node_type * pNode = pHead; pNode; pNode = pNext ) {
1326 pNext = pNode->m_pNext;
1334 template <typename Disposer>
1335 void clear( Disposer disp )
1338 for ( node_type * pNode = pHead; pNode; pNode = pNext ) {
1339 pNext = pNode->m_pNext;
1348 unsigned int size() const
1354 template <typename Node, unsigned int Capacity>
1355 class bucket_entry<Node, cuckoo::vector<Capacity>>
1358 typedef Node node_type;
1359 typedef cuckoo::vector_probeset_class probeset_class;
1360 typedef cuckoo::vector<Capacity> probeset_type;
1362 static unsigned int const c_nCapacity = probeset_type::c_nCapacity;
1365 node_type * m_arrNode[c_nCapacity];
1366 unsigned int m_nSize;
1368 void shift_up( unsigned int nFrom )
1370 assert( m_nSize < c_nCapacity );
1372 if ( nFrom < m_nSize )
1373 std::copy_backward( m_arrNode + nFrom, m_arrNode + m_nSize, m_arrNode + m_nSize + 1 );
1376 void shift_down( node_type ** pFrom )
1378 assert( m_arrNode <= pFrom && pFrom < m_arrNode + m_nSize);
1379 std::copy( pFrom + 1, m_arrNode + m_nSize, pFrom );
1385 friend class bucket_entry;
1391 iterator( node_type ** p )
1394 iterator( iterator const& it)
1398 iterator& operator=( iterator const& it )
1404 node_type * operator->()
1406 assert( pArr != nullptr );
1409 node_type& operator*()
1411 assert( pArr != nullptr );
1412 assert( *pArr != nullptr );
1417 iterator& operator ++()
1423 bool operator==(iterator const& it ) const
1425 return pArr == it.pArr;
1427 bool operator!=(iterator const& it ) const
1429 return !( *this == it );
1437 memset( m_arrNode, 0, sizeof(m_arrNode));
1438 static_assert(( std::is_same<typename node_type::probeset_type, probeset_type>::value ), "Incompatible node type" );
1443 return iterator(m_arrNode);
1447 return iterator(m_arrNode + size());
1450 void insert_after( iterator it, node_type * p )
1452 assert( m_nSize < c_nCapacity );
1453 assert( !it.pArr || (m_arrNode <= it.pArr && it.pArr <= m_arrNode + m_nSize));
1456 shift_up( static_cast<unsigned int>(it.pArr - m_arrNode) + 1 );
1466 void remove( iterator /*itPrev*/, iterator itWhat )
1469 shift_down( itWhat.pArr );
1478 template <typename Disposer>
1479 void clear( Disposer disp )
1481 for ( unsigned int i = 0; i < m_nSize; ++i ) {
1482 disp( m_arrNode[i] );
1487 unsigned int size() const
1493 template <typename Node, unsigned int ArraySize>
1495 static void store( Node * pNode, size_t * pHashes )
1497 memcpy( pNode->m_arrHash, pHashes, sizeof(pHashes[0]) * ArraySize );
1499 static bool equal_to( Node& node, unsigned int nTable, size_t nHash )
1501 return node.m_arrHash[nTable] == nHash;
1504 template <typename Node>
1505 struct hash_ops<Node, 0>
1507 static void store( Node * /*pNode*/, size_t * /*pHashes*/ )
1509 static bool equal_to( Node& /*node*/, unsigned int /*nTable*/, size_t /*nHash*/ )
1515 template <typename NodeTraits, bool Ordered>
1518 template <typename NodeTraits>
1519 struct contains<NodeTraits, true>
1521 template <typename BucketEntry, typename Position, typename Q, typename Compare>
1522 static bool find( BucketEntry& probeset, Position& pos, unsigned int /*nTable*/, size_t /*nHash*/, Q const& val, Compare cmp )
1525 typedef typename BucketEntry::iterator bucket_iterator;
1527 bucket_iterator itPrev;
1529 for ( bucket_iterator it = probeset.begin(), itEnd = probeset.end(); it != itEnd; ++it ) {
1530 int cmpRes = cmp( *NodeTraits::to_value_ptr(*it), val );
1531 if ( cmpRes >= 0 ) {
1533 pos.itPrev = itPrev;
1540 pos.itPrev = itPrev;
1541 pos.itFound = probeset.end();
1546 template <typename NodeTraits>
1547 struct contains<NodeTraits, false>
1549 template <typename BucketEntry, typename Position, typename Q, typename EqualTo>
1550 static bool find( BucketEntry& probeset, Position& pos, unsigned int nTable, size_t nHash, Q const& val, EqualTo eq )
1552 // Unordered version
1553 typedef typename BucketEntry::iterator bucket_iterator;
1554 typedef typename BucketEntry::node_type node_type;
1556 bucket_iterator itPrev;
1558 for ( bucket_iterator it = probeset.begin(), itEnd = probeset.end(); it != itEnd; ++it ) {
1559 if ( hash_ops<node_type, node_type::hash_array_size>::equal_to( *it, nTable, nHash ) && eq( *NodeTraits::to_value_ptr(*it), val )) {
1561 pos.itPrev = itPrev;
1567 pos.itPrev = itPrev;
1568 pos.itFound = probeset.end();
1573 } // namespace details
1576 } // namespace cuckoo
1579 /** @ingroup cds_intrusive_map
1582 - [2007] M.Herlihy, N.Shavit, M.Tzafrir "Concurrent Cuckoo Hashing. Technical report"
1583 - [2008] Maurice Herlihy, Nir Shavit "The Art of Multiprocessor Programming"
1585 <b>About Cuckoo hashing</b>
1587 [From <i>"The Art of Multiprocessor Programming"</i>]
1588 Cuckoo hashing is a hashing algorithm in which a newly added item displaces any earlier item
1589 occupying the same slot. For brevity, a table is a k-entry array of items. For a hash set f size
1590 N = 2k we use a two-entry array of tables, and two independent hash functions,
1591 <tt> h0, h1: KeyRange -> 0,...,k-1</tt>
1592 mapping the set of possible keys to entries in he array. To test whether a value \p x is in the set,
1593 <tt>find(x)</tt> tests whether either <tt>table[0][h0(x)]</tt> or <tt>table[1][h1(x)]</tt> is
1594 equal to \p x. Similarly, <tt>erase(x)</tt>checks whether \p x is in either <tt>table[0][h0(x)]</tt>
1595 or <tt>table[1][h1(x)]</tt>, ad removes it if found.
1597 The <tt>insert(x)</tt> successively "kicks out" conflicting items until every key has a slot.
1598 To add \p x, the method swaps \p x with \p y, the current occupant of <tt>table[0][h0(x)]</tt>.
1599 If the prior value was \p nullptr, it is done. Otherwise, it swaps the newly nest-less value \p y
1600 for the current occupant of <tt>table[1][h1(y)]</tt> in the same way. As before, if the prior value
1601 was \p nullptr, it is done. Otherwise, the method continues swapping entries (alternating tables)
1602 until it finds an empty slot. We might not find an empty slot, either because the table is full,
1603 or because the sequence of displacement forms a cycle. We therefore need an upper limit on the
1604 number of successive displacements we are willing to undertake. When this limit is exceeded,
1605 we resize the hash table, choose new hash functions and start over.
1607 For concurrent cuckoo hashing, rather than organizing the set as a two-dimensional table of
1608 items, we use two-dimensional table of probe sets, where a probe set is a constant-sized set
1609 of items with the same hash code. Each probe set holds at most \p PROBE_SIZE items, but the algorithm
1610 tries to ensure that when the set is quiescent (i.e no method call in progress) each probe set
1611 holds no more than <tt>THRESHOLD < PROBE_SET</tt> items. While method calls are in-flight, a probe
1612 set may temporarily hold more than \p THRESHOLD but never more than \p PROBE_SET items.
1614 In current implementation, a probe set can be defined either as a (single-linked) list
1615 or as a fixed-sized vector, optionally ordered.
1617 In description above two-table cuckoo hashing (<tt>k = 2</tt>) has been considered.
1618 We can generalize this approach for <tt>k >= 2</tt> when we have \p k hash functions
1619 <tt>h[0], ... h[k-1]</tt> and \p k tables <tt>table[0], ... table[k-1]</tt>.
1621 The search in probe set is linear, the complexity is <tt> O(PROBE_SET) </tt>.
1622 The probe set may be ordered or not. Ordered probe set can be more efficient since
1623 the average search complexity is <tt>O(PROBE_SET/2)</tt>.
1624 However, the overhead of sorting can eliminate a gain of ordered search.
1626 The probe set is ordered if opt::compare or opt::less is specified in \p Traits template
1627 parameter. Otherwise, the probe set is unordered and \p Traits must contain
1628 opt::equal_to option.
1630 The cds::intrusive::cuckoo namespace contains \p %CuckooSet-related declarations.
1633 - \p T - the type stored in the set. The type must be based on cuckoo::node (for cuckoo::base_hook)
1634 or it must have a member of type %cuckoo::node (for cuckoo::member_hook),
1635 or it must be convertible to \p %cuckoo::node (for cuckoo::traits_hook)
1636 - \p Traits - type traits, default is cuckoo::traits. It is possible to declare option-based
1637 set with \p cuckoo::make_traits metafunction result as \p Traits template argument.
1641 You should incorporate \p cuckoo::node into your struct \p T and provide
1642 appropriate \p cuckoo::traits::hook in your \p Traits template parameters.
1643 Usually, for \p Traits you define a struct based on \p cuckoo::traits.
1645 Example for base hook and list-based probe-set:
1647 #include <cds/intrusive/cuckoo_set.h>
1649 // Data stored in cuckoo set
1650 // We use list as probe-set container and store hash values in the node
1651 // (since we use two hash functions we should store 2 hash values per node)
1652 struct my_data: public cds::intrusive::cuckoo::node< cds::intrusive::cuckoo::list, 2 >
1661 // Provide equal_to functor for my_data since we will use unordered probe-set
1662 struct my_data_equal_to {
1663 bool operator()( const my_data& d1, const my_data& d2 ) const
1665 return d1.strKey.compare( d2.strKey ) == 0;
1668 bool operator()( const my_data& d, const std::string& s ) const
1670 return d.strKey.compare(s) == 0;
1673 bool operator()( const std::string& s, const my_data& d ) const
1675 return s.compare( d.strKey ) == 0;
1679 // Provide two hash functor for my_data
1681 size_t operator()(std::string const& s) const
1683 return cds::opt::v::hash<std::string>( s );
1685 size_t operator()( my_data const& d ) const
1687 return (*this)( d.strKey );
1691 struct hash2: private hash1 {
1692 size_t operator()(std::string const& s) const
1694 size_t h = ~( hash1::operator()(s));
1695 return ~h + 0x9e3779b9 + (h << 6) + (h >> 2);
1697 size_t operator()( my_data const& d ) const
1699 return (*this)( d.strKey );
1703 // Declare type traits
1704 struct my_traits: public cds::intrusive::cuckoo::traits
1706 typedef cds::intrusive::cuckoo::base_hook<
1707 cds::intrusive::cuckoo::probeset_type< my_data::probeset_type >
1708 ,cds::intrusive::cuckoo::store_hash< my_data::hash_array_size >
1710 typedef my_data_equa_to equal_to;
1711 typedef cds::opt::hash_tuple< hash1, hash2 > hash;
1714 // Declare CuckooSet type
1715 typedef cds::intrusive::CuckooSet< my_data, my_traits > my_cuckoo_set;
1717 // Equal option-based declaration
1718 typedef cds::intrusive::CuckooSet< my_data,
1719 cds::intrusive::cuckoo::make_traits<
1720 cds::intrusive::opt::hook< cds::intrusive::cuckoo::base_hook<
1721 cds::intrusive::cuckoo::probeset_type< my_data::probeset_type >
1722 ,cds::intrusive::cuckoo::store_hash< my_data::hash_array_size >
1724 ,cds::opt::hash< std::tuple< hash1, hash2 > >
1725 ,cds::opt::equal_to< my_data_equal_to >
1730 If we provide \p compare function instead of \p equal_to for \p my_data
1731 we get as a result a cuckoo set with ordered probe set that may improve
1733 Example for base hook and ordered vector-based probe-set:
1736 #include <cds/intrusive/cuckoo_set.h>
1738 // Data stored in cuckoo set
1739 // We use a vector of capacity 4 as probe-set container and store hash values in the node
1740 // (since we use two hash functions we should store 2 hash values per node)
1741 struct my_data: public cds::intrusive::cuckoo::node< cds::intrusive::cuckoo::vector<4>, 2 >
1750 // Provide compare functor for my_data since we want to use ordered probe-set
1751 struct my_data_compare {
1752 int operator()( const my_data& d1, const my_data& d2 ) const
1754 return d1.strKey.compare( d2.strKey );
1757 int operator()( const my_data& d, const std::string& s ) const
1759 return d.strKey.compare(s);
1762 int operator()( const std::string& s, const my_data& d ) const
1764 return s.compare( d.strKey );
1768 // Provide two hash functor for my_data
1770 size_t operator()(std::string const& s) const
1772 return cds::opt::v::hash<std::string>( s );
1774 size_t operator()( my_data const& d ) const
1776 return (*this)( d.strKey );
1780 struct hash2: private hash1 {
1781 size_t operator()(std::string const& s) const
1783 size_t h = ~( hash1::operator()(s));
1784 return ~h + 0x9e3779b9 + (h << 6) + (h >> 2);
1786 size_t operator()( my_data const& d ) const
1788 return (*this)( d.strKey );
1792 // Declare type traits
1793 struct my_traits: public cds::intrusive::cuckoo::traits
1795 typedef cds::intrusive::cuckoo::base_hook<
1796 cds::intrusive::cuckoo::probeset_type< my_data::probeset_type >
1797 ,cds::intrusive::cuckoo::store_hash< my_data::hash_array_size >
1799 typedef my_data_compare compare;
1800 typedef cds::opt::hash_tuple< hash1, hash2 > hash;
1803 // Declare CuckooSet type
1804 typedef cds::intrusive::CuckooSet< my_data, my_traits > my_cuckoo_set;
1806 // Equal option-based declaration
1807 typedef cds::intrusive::CuckooSet< my_data,
1808 cds::intrusive::cuckoo::make_traits<
1809 cds::intrusive::opt::hook< cds::intrusive::cuckoo::base_hook<
1810 cds::intrusive::cuckoo::probeset_type< my_data::probeset_type >
1811 ,cds::intrusive::cuckoo::store_hash< my_data::hash_array_size >
1813 ,cds::opt::hash< std::tuple< hash1, hash2 > >
1814 ,cds::opt::compare< my_data_compare >
1820 template <typename T, typename Traits = cuckoo::traits>
1824 typedef T value_type; ///< The value type stored in the set
1825 typedef Traits traits; ///< Set traits
1827 typedef typename traits::hook hook; ///< hook type
1828 typedef typename hook::node_type node_type; ///< node type
1829 typedef typename get_node_traits< value_type, node_type, hook>::type node_traits; ///< node traits
1831 typedef typename traits::hash hash; ///< hash functor tuple wrapped for internal use
1832 typedef typename hash::hash_tuple_type hash_tuple_type; ///< Type of hash tuple
1834 typedef typename traits::stat stat; ///< internal statistics type
1836 typedef typename traits::mutex_policy original_mutex_policy; ///< Concurrent access policy, see \p cuckoo::traits::mutex_policy
1838 /// Actual mutex policy
1840 Actual mutex policy is built from mutex policy type provided by \p Traits template argument (see \p cuckoo::traits::mutex_policy)
1841 but mutex policy internal statistics is conformed with \p cukoo::traits::stat type provided by \p Traits:
1842 - if \p %cuckoo::traits::stat is \p cuckoo::empty_stat then mutex policy statistics is already empty
1843 - otherwise real mutex policy statistics is used
1845 typedef typename original_mutex_policy::template rebind_statistics<
1846 typename std::conditional<
1847 std::is_same< stat, cuckoo::empty_stat >::value
1848 ,typename original_mutex_policy::empty_stat
1849 ,typename original_mutex_policy::real_stat
1851 >::other mutex_policy;
1853 static bool const c_isSorted = !( std::is_same< typename traits::compare, opt::none >::value
1854 && std::is_same< typename traits::less, opt::none >::value ) ; ///< whether the probe set should be ordered
1855 static size_t const c_nArity = hash::size ; ///< the arity of cuckoo hashing: the number of hash functors provided; minimum 2.
1857 /// Key equality functor; used only for unordered probe-set
1858 typedef typename opt::details::make_equal_to< value_type, traits, !c_isSorted>::type key_equal_to;
1860 /// key comparing functor based on opt::compare and opt::less option setter. Used only for ordered probe set
1861 typedef typename opt::details::make_comparator< value_type, traits >::type key_comparator;
1864 typedef typename traits::allocator allocator;
1866 /// item counter type
1867 typedef typename traits::item_counter item_counter;
1870 typedef typename traits::disposer disposer;
1874 typedef typename node_type::probeset_class probeset_class;
1875 typedef typename node_type::probeset_type probeset_type;
1876 static unsigned int const c_nNodeHashArraySize = node_type::hash_array_size;
1878 typedef typename mutex_policy::scoped_cell_lock scoped_cell_lock;
1879 typedef typename mutex_policy::scoped_cell_trylock scoped_cell_trylock;
1880 typedef typename mutex_policy::scoped_full_lock scoped_full_lock;
1881 typedef typename mutex_policy::scoped_resize_lock scoped_resize_lock;
1883 typedef cuckoo::details::bucket_entry< node_type, probeset_type > bucket_entry;
1884 typedef typename bucket_entry::iterator bucket_iterator;
1885 typedef cds::details::Allocator< bucket_entry, allocator > bucket_table_allocator;
1887 typedef size_t hash_array[c_nArity] ; ///< hash array
1890 bucket_iterator itPrev;
1891 bucket_iterator itFound;
1894 typedef cuckoo::details::contains< node_traits, c_isSorted > contains_action;
1896 template <typename Predicate>
1897 struct predicate_wrapper {
1898 typedef typename std::conditional< c_isSorted, cds::opt::details::make_comparator_from_less<Predicate>, Predicate>::type type;
1901 typedef typename std::conditional< c_isSorted, key_comparator, key_equal_to >::type key_predicate;
1905 static unsigned int const c_nDefaultProbesetSize = 4; ///< default probeset size
1906 static size_t const c_nDefaultInitialSize = 16; ///< default initial size
1907 static unsigned int const c_nRelocateLimit = c_nArity * 2 - 1; ///< Count of attempts to relocate before giving up
1910 bucket_entry * m_BucketTable[ c_nArity ] ; ///< Bucket tables
1912 size_t m_nBucketMask ; ///< Hash bitmask; bucket table size minus 1.
1913 unsigned int const m_nProbesetSize ; ///< Probe set size
1914 unsigned int const m_nProbesetThreshold ; ///< Probe set threshold
1916 hash m_Hash ; ///< Hash functor tuple
1917 mutex_policy m_MutexPolicy ; ///< concurrent access policy
1918 item_counter m_ItemCounter ; ///< item counter
1919 mutable stat m_Stat ; ///< internal statistics
1923 static void check_common_constraints()
1925 static_assert( (c_nArity == mutex_policy::c_nArity), "The count of hash functors must be equal to mutex_policy arity" );
1928 void check_probeset_properties() const
1930 assert( m_nProbesetThreshold < m_nProbesetSize );
1932 // if probe set type is cuckoo::vector<N> then m_nProbesetSize == N
1933 assert( node_type::probeset_size == 0 || node_type::probeset_size == m_nProbesetSize );
1936 template <typename Q>
1937 void hashing( size_t * pHashes, Q const& v ) const
1939 m_Hash( pHashes, v );
1942 void copy_hash( size_t * pHashes, value_type const& v ) const
1944 if ( c_nNodeHashArraySize )
1945 memcpy( pHashes, node_traits::to_node_ptr( v )->get_hash(), sizeof(pHashes[0]) * c_nNodeHashArraySize );
1947 hashing( pHashes, v );
1950 bucket_entry& bucket( unsigned int nTable, size_t nHash )
1952 assert( nTable < c_nArity );
1953 return m_BucketTable[nTable][nHash & m_nBucketMask];
1956 static void store_hash( node_type * pNode, size_t * pHashes )
1958 cuckoo::details::hash_ops< node_type, c_nNodeHashArraySize >::store( pNode, pHashes );
1961 static bool equal_hash( node_type& node, unsigned int nTable, size_t nHash )
1963 return cuckoo::details::hash_ops< node_type, c_nNodeHashArraySize >::equal_to( node, nTable, nHash );
1966 void allocate_bucket_tables( size_t nSize )
1968 assert( cds::beans::is_power2( nSize ) );
1970 m_nBucketMask = nSize - 1;
1971 bucket_table_allocator alloc;
1972 for ( unsigned int i = 0; i < c_nArity; ++i )
1973 m_BucketTable[i] = alloc.NewArray( nSize );
1976 static void free_bucket_tables( bucket_entry ** pTable, size_t nCapacity )
1978 bucket_table_allocator alloc;
1979 for ( unsigned int i = 0; i < c_nArity; ++i ) {
1980 alloc.Delete( pTable[i], nCapacity );
1981 pTable[i] = nullptr;
1984 void free_bucket_tables()
1986 free_bucket_tables( m_BucketTable, m_nBucketMask + 1 );
1989 static CDS_CONSTEXPR unsigned int const c_nUndefTable = (unsigned int) -1;
1990 template <typename Q, typename Predicate >
1991 unsigned int contains( position * arrPos, size_t * arrHash, Q const& val, Predicate pred )
1993 // Buckets must be locked
1995 for ( unsigned int i = 0; i < c_nArity; ++i ) {
1996 bucket_entry& probeset = bucket( i, arrHash[i] );
1997 if ( contains_action::find( probeset, arrPos[i], i, arrHash[i], val, pred ))
2000 return c_nUndefTable;
2003 template <typename Q, typename Predicate, typename Func>
2004 value_type * erase_( Q const& val, Predicate pred, Func f )
2007 hashing( arrHash, val );
2008 position arrPos[ c_nArity ];
2011 scoped_cell_lock guard( m_MutexPolicy, arrHash );
2013 unsigned int nTable = contains( arrPos, arrHash, val, pred );
2014 if ( nTable != c_nUndefTable ) {
2015 node_type& node = *arrPos[nTable].itFound;
2016 f( *node_traits::to_value_ptr(node) );
2017 bucket( nTable, arrHash[nTable]).remove( arrPos[nTable].itPrev, arrPos[nTable].itFound );
2019 m_Stat.onEraseSuccess();
2020 return node_traits::to_value_ptr( node );
2024 m_Stat.onEraseFailed();
2028 template <typename Q, typename Predicate, typename Func>
2029 bool find_( Q& val, Predicate pred, Func f )
2032 position arrPos[ c_nArity ];
2033 hashing( arrHash, val );
2034 scoped_cell_lock sl( m_MutexPolicy, arrHash );
2036 unsigned int nTable = contains( arrPos, arrHash, val, pred );
2037 if ( nTable != c_nUndefTable ) {
2038 f( *node_traits::to_value_ptr( *arrPos[nTable].itFound ), val );
2039 m_Stat.onFindSuccess();
2043 m_Stat.onFindFailed();
2047 bool relocate( unsigned int nTable, size_t * arrGoalHash )
2049 // arrGoalHash contains hash values for relocating element
2050 // Relocating element is first one from bucket( nTable, arrGoalHash[nTable] ) probeset
2052 m_Stat.onRelocateCall();
2056 for ( unsigned int nRound = 0; nRound < c_nRelocateLimit; ++nRound ) {
2057 m_Stat.onRelocateRound();
2060 scoped_cell_lock guard( m_MutexPolicy, arrGoalHash );
2062 bucket_entry& refBucket = bucket( nTable, arrGoalHash[nTable] );
2063 if ( refBucket.size() < m_nProbesetThreshold ) {
2064 // probeset is not above the threshold
2065 m_Stat.onFalseRelocateRound();
2069 pVal = node_traits::to_value_ptr( *refBucket.begin() );
2070 copy_hash( arrHash, *pVal );
2072 scoped_cell_trylock guard2( m_MutexPolicy, arrHash );
2073 if ( !guard2.locked() )
2074 continue ; // try one more time
2076 refBucket.remove( typename bucket_entry::iterator(), refBucket.begin() );
2078 unsigned int i = (nTable + 1) % c_nArity;
2080 // try insert into free probeset
2081 while ( i != nTable ) {
2082 bucket_entry& bkt = bucket( i, arrHash[i] );
2083 if ( bkt.size() < m_nProbesetThreshold ) {
2085 contains_action::find( bkt, pos, i, arrHash[i], *pVal, key_predicate() ) ; // must return false!
2086 bkt.insert_after( pos.itPrev, node_traits::to_node_ptr( pVal ));
2087 m_Stat.onSuccessRelocateRound();
2090 i = ( i + 1 ) % c_nArity;
2093 // try insert into partial probeset
2094 i = (nTable + 1) % c_nArity;
2095 while ( i != nTable ) {
2096 bucket_entry& bkt = bucket( i, arrHash[i] );
2097 if ( bkt.size() < m_nProbesetSize ) {
2099 contains_action::find( bkt, pos, i, arrHash[i], *pVal, key_predicate() ) ; // must return false!
2100 bkt.insert_after( pos.itPrev, node_traits::to_node_ptr( pVal ));
2102 memcpy( arrGoalHash, arrHash, sizeof(arrHash));
2103 m_Stat.onRelocateAboveThresholdRound();
2104 goto next_iteration;
2106 i = (i + 1) % c_nArity;
2109 // all probeset is full, relocating fault
2110 refBucket.insert_after( typename bucket_entry::iterator(), node_traits::to_node_ptr( pVal ));
2111 m_Stat.onFailedRelocate();
2122 m_Stat.onResizeCall();
2124 size_t nOldCapacity = bucket_count();
2125 bucket_entry * pOldTable[ c_nArity ];
2127 scoped_resize_lock guard( m_MutexPolicy );
2129 if ( nOldCapacity != bucket_count() ) {
2130 m_Stat.onFalseResizeCall();
2134 size_t nCapacity = nOldCapacity * 2;
2136 m_MutexPolicy.resize( nCapacity );
2137 memcpy( pOldTable, m_BucketTable, sizeof(pOldTable));
2138 allocate_bucket_tables( nCapacity );
2140 typedef typename bucket_entry::iterator bucket_iterator;
2142 position arrPos[ c_nArity ];
2144 for ( unsigned int nTable = 0; nTable < c_nArity; ++nTable ) {
2145 bucket_entry * pTable = pOldTable[nTable];
2146 for ( size_t k = 0; k < nOldCapacity; ++k ) {
2147 bucket_iterator itNext;
2148 for ( bucket_iterator it = pTable[k].begin(), itEnd = pTable[k].end(); it != itEnd; it = itNext ) {
2152 value_type& val = *node_traits::to_value_ptr( *it );
2153 copy_hash( arrHash, val );
2154 contains( arrPos, arrHash, val, key_predicate() ) ; // must return c_nUndefTable
2156 for ( unsigned int i = 0; i < c_nArity; ++i ) {
2157 bucket_entry& refBucket = bucket( i, arrHash[i] );
2158 if ( refBucket.size() < m_nProbesetThreshold ) {
2159 refBucket.insert_after( arrPos[i].itPrev, &*it );
2160 m_Stat.onResizeSuccessMove();
2165 for ( unsigned int i = 0; i < c_nArity; ++i ) {
2166 bucket_entry& refBucket = bucket( i, arrHash[i] );
2167 if ( refBucket.size() < m_nProbesetSize ) {
2168 refBucket.insert_after( arrPos[i].itPrev, &*it );
2169 assert( refBucket.size() > 1 );
2170 copy_hash( arrHash, *node_traits::to_value_ptr( *refBucket.begin()) );
2171 m_Stat.onResizeRelocateCall();
2172 relocate( i, arrHash );
2181 free_bucket_tables( pOldTable, nOldCapacity );
2184 CDS_CONSTEXPR static unsigned int calc_probeset_size( unsigned int nProbesetSize ) CDS_NOEXCEPT
2186 return std::is_same< probeset_class, cuckoo::vector_probeset_class >::value
2187 ? node_type::probeset_size
2190 : ( node_type::probeset_size ? node_type::probeset_size : c_nDefaultProbesetSize ));
2195 /// Default constructor
2197 Initial size = \ref c_nDefaultInitialSize
2200 - \p c_nDefaultProbesetSize if \p probeset_type is \p cuckoo::list
2201 - \p Capacity if \p probeset_type is <tt> cuckoo::vector<Capacity> </tt>
2203 Probe set threshold = probe set size - 1
2206 : m_nProbesetSize( calc_probeset_size(0) )
2207 , m_nProbesetThreshold( m_nProbesetSize - 1 )
2208 , m_MutexPolicy( c_nDefaultInitialSize )
2210 check_common_constraints();
2211 check_probeset_properties();
2213 allocate_bucket_tables( c_nDefaultInitialSize );
2216 /// Constructs the set object with given probe set size and threshold
2218 If probe set type is <tt> cuckoo::vector<Capacity> </tt> vector
2219 then \p nProbesetSize is ignored since it should be equal to vector's \p Capacity.
2222 size_t nInitialSize ///< Initial set size; if 0 - use default initial size \ref c_nDefaultInitialSize
2223 , unsigned int nProbesetSize ///< probe set size
2224 , unsigned int nProbesetThreshold = 0 ///< probe set threshold, <tt>nProbesetThreshold < nProbesetSize</tt>. If 0, nProbesetThreshold = nProbesetSize - 1
2226 : m_nProbesetSize( calc_probeset_size(nProbesetSize) )
2227 , m_nProbesetThreshold( nProbesetThreshold ? nProbesetThreshold : m_nProbesetSize - 1 )
2228 , m_MutexPolicy( cds::beans::ceil2(nInitialSize ? nInitialSize : c_nDefaultInitialSize ))
2230 check_common_constraints();
2231 check_probeset_properties();
2233 allocate_bucket_tables( nInitialSize ? cds::beans::ceil2( nInitialSize ) : c_nDefaultInitialSize );
2236 /// Constructs the set object with given hash functor tuple
2238 The probe set size and threshold are set as default, see CuckooSet()
2241 hash_tuple_type const& h ///< hash functor tuple of type <tt>std::tuple<H1, H2, ... Hn></tt> where <tt> n == \ref c_nArity </tt>
2243 : m_nProbesetSize( calc_probeset_size(0) )
2244 , m_nProbesetThreshold( m_nProbesetSize -1 )
2246 , m_MutexPolicy( c_nDefaultInitialSize )
2248 check_common_constraints();
2249 check_probeset_properties();
2251 allocate_bucket_tables( c_nDefaultInitialSize );
2254 /// Constructs the set object with given probe set properties and hash functor tuple
2256 If probe set type is <tt> cuckoo::vector<Capacity> </tt> vector
2257 then \p nProbesetSize should be equal to vector's \p Capacity.
2260 size_t nInitialSize ///< Initial set size; if 0 - use default initial size \ref c_nDefaultInitialSize
2261 , unsigned int nProbesetSize ///< probe set size, positive integer
2262 , unsigned int nProbesetThreshold ///< probe set threshold, <tt>nProbesetThreshold < nProbesetSize</tt>. If 0, nProbesetThreshold = nProbesetSize - 1
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(nProbesetSize) )
2266 , m_nProbesetThreshold( nProbesetThreshold ? nProbesetThreshold : m_nProbesetSize - 1)
2268 , m_MutexPolicy( cds::beans::ceil2(nInitialSize ? nInitialSize : c_nDefaultInitialSize ))
2270 check_common_constraints();
2271 check_probeset_properties();
2273 allocate_bucket_tables( nInitialSize ? cds::beans::ceil2( nInitialSize ) : c_nDefaultInitialSize );
2276 /// Constructs the set object with given hash functor tuple (move semantics)
2278 The probe set size and threshold are set as default, see CuckooSet()
2281 hash_tuple_type&& h ///< hash functor tuple of type <tt>std::tuple<H1, H2, ... Hn></tt> where <tt> n == \ref c_nArity </tt>
2283 : m_nProbesetSize( calc_probeset_size(0) )
2284 , m_nProbesetThreshold( m_nProbesetSize / 2 )
2285 , m_Hash( std::forward<hash_tuple_type>(h) )
2286 , m_MutexPolicy( c_nDefaultInitialSize )
2288 check_common_constraints();
2289 check_probeset_properties();
2291 allocate_bucket_tables( c_nDefaultInitialSize );
2294 /// Constructs the set object with given probe set properties and hash functor tuple (move semantics)
2296 If probe set type is <tt> cuckoo::vector<Capacity> </tt> vector
2297 then \p nProbesetSize should be equal to vector's \p Capacity.
2300 size_t nInitialSize ///< Initial set size; if 0 - use default initial size \ref c_nDefaultInitialSize
2301 , unsigned int nProbesetSize ///< probe set size, positive integer
2302 , unsigned int nProbesetThreshold ///< probe set threshold, <tt>nProbesetThreshold < nProbesetSize</tt>. If 0, nProbesetThreshold = nProbesetSize - 1
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(nProbesetSize) )
2306 , m_nProbesetThreshold( nProbesetThreshold ? nProbesetThreshold : m_nProbesetSize - 1)
2307 , m_Hash( std::forward<hash_tuple_type>(h) )
2308 , m_MutexPolicy( cds::beans::ceil2(nInitialSize ? nInitialSize : c_nDefaultInitialSize ))
2310 check_common_constraints();
2311 check_probeset_properties();
2313 allocate_bucket_tables( nInitialSize ? cds::beans::ceil2( nInitialSize ) : c_nDefaultInitialSize );
2319 free_bucket_tables();
2323 /// Inserts new node
2325 The function inserts \p val in the set if it does not contain
2326 an item with key equal to \p val.
2328 Returns \p true if \p val is placed into the set, \p false otherwise.
2330 bool insert( value_type& val )
2332 return insert( val, []( value_type& ) {} );
2335 /// Inserts new node
2337 The function allows to split creating of new item into two part:
2338 - create item with key only
2339 - insert new item into the set
2340 - if inserting is success, calls \p f functor to initialize value-field of \p val.
2342 The functor signature is:
2344 void func( value_type& val );
2346 where \p val is the item inserted.
2348 The user-defined functor is called only if the inserting is success.
2350 template <typename Func>
2351 bool insert( value_type& val, Func f )
2354 position arrPos[ c_nArity ];
2355 unsigned int nGoalTable;
2357 hashing( arrHash, val );
2358 node_type * pNode = node_traits::to_node_ptr( val );
2359 store_hash( pNode, arrHash );
2363 scoped_cell_lock guard( m_MutexPolicy, arrHash );
2365 if ( contains( arrPos, arrHash, val, key_predicate() ) != c_nUndefTable ) {
2366 m_Stat.onInsertFailed();
2370 for ( unsigned int i = 0; i < c_nArity; ++i ) {
2371 bucket_entry& refBucket = bucket( i, arrHash[i] );
2372 if ( refBucket.size() < m_nProbesetThreshold ) {
2373 refBucket.insert_after( arrPos[i].itPrev, pNode );
2376 m_Stat.onInsertSuccess();
2381 for ( unsigned int i = 0; i < c_nArity; ++i ) {
2382 bucket_entry& refBucket = bucket( i, arrHash[i] );
2383 if ( refBucket.size() < m_nProbesetSize ) {
2384 refBucket.insert_after( arrPos[i].itPrev, pNode );
2388 assert( refBucket.size() > 1 );
2389 copy_hash( arrHash, *node_traits::to_value_ptr( *refBucket.begin()) );
2395 m_Stat.onInsertResize();
2400 m_Stat.onInsertRelocate();
2401 if ( !relocate( nGoalTable, arrHash )) {
2402 m_Stat.onInsertRelocateFault();
2403 m_Stat.onInsertResize();
2407 m_Stat.onInsertSuccess();
2411 /// Updates the node
2413 The operation performs inserting or changing data with lock-free manner.
2415 If the item \p val is not found in the set, then \p val is inserted into the set
2416 iff \p bAllowInsert is \p true.
2417 Otherwise, the functor \p func is called with item found.
2418 The functor \p func signature is:
2420 void func( bool bNew, value_type& item, value_type& val );
2423 - \p bNew - \p true if the item has been inserted, \p false otherwise
2424 - \p item - item of the set
2425 - \p val - argument \p val passed into the \p %update() function
2426 If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
2427 refer to the same thing.
2429 The functor may change non-key fields of the \p item.
2431 Returns std::pair<bool, bool> where \p first is \p true if operation is successfull,
2432 i.e. the node has been inserted or updated,
2433 \p second is \p true if new item has been added or \p false if the item with \p key
2436 template <typename Func>
2437 std::pair<bool, bool> update( value_type& val, Func func, bool bAllowInsert = true )
2440 position arrPos[ c_nArity ];
2441 unsigned int nGoalTable;
2443 hashing( arrHash, val );
2444 node_type * pNode = node_traits::to_node_ptr( val );
2445 store_hash( pNode, arrHash );
2449 scoped_cell_lock guard( m_MutexPolicy, arrHash );
2451 unsigned int nTable = contains( arrPos, arrHash, val, key_predicate() );
2452 if ( nTable != c_nUndefTable ) {
2453 func( false, *node_traits::to_value_ptr( *arrPos[nTable].itFound ), val );
2454 m_Stat.onUpdateExist();
2455 return std::make_pair( true, false );
2458 if ( !bAllowInsert )
2459 return std::make_pair( false, false );
2461 //node_type * pNode = node_traits::to_node_ptr( val );
2462 //store_hash( pNode, arrHash );
2464 for ( unsigned int i = 0; i < c_nArity; ++i ) {
2465 bucket_entry& refBucket = bucket( i, arrHash[i] );
2466 if ( refBucket.size() < m_nProbesetThreshold ) {
2467 refBucket.insert_after( arrPos[i].itPrev, pNode );
2468 func( true, val, val );
2470 m_Stat.onUpdateSuccess();
2471 return std::make_pair( true, true );
2475 for ( unsigned int i = 0; i < c_nArity; ++i ) {
2476 bucket_entry& refBucket = bucket( i, arrHash[i] );
2477 if ( refBucket.size() < m_nProbesetSize ) {
2478 refBucket.insert_after( arrPos[i].itPrev, pNode );
2479 func( true, val, val );
2482 assert( refBucket.size() > 1 );
2483 copy_hash( arrHash, *node_traits::to_value_ptr( *refBucket.begin()) );
2489 m_Stat.onUpdateResize();
2494 m_Stat.onUpdateRelocate();
2495 if ( !relocate( nGoalTable, arrHash )) {
2496 m_Stat.onUpdateRelocateFault();
2497 m_Stat.onUpdateResize();
2501 m_Stat.onUpdateSuccess();
2502 return std::make_pair( true, true );
2505 template <typename Func>
2506 CDS_DEPRECATED("ensure() is deprecated, use update()")
2507 std::pair<bool, bool> ensure( value_type& val, Func func )
2509 return update( val, func, true );
2513 /// Unlink the item \p val from the set
2515 The function searches the item \p val in the set and unlink it
2516 if it is found and is equal to \p val (here, the equality means that
2517 \p val belongs to the set: if \p item is an item found then
2518 unlink is successful iif <tt>&val == &item</tt>)
2520 The function returns \p true if success and \p false otherwise.
2522 bool unlink( value_type& val )
2525 hashing( arrHash, val );
2526 position arrPos[ c_nArity ];
2529 scoped_cell_lock guard( m_MutexPolicy, arrHash );
2531 unsigned int nTable = contains( arrPos, arrHash, val, key_predicate() );
2532 if ( nTable != c_nUndefTable && node_traits::to_value_ptr(*arrPos[nTable].itFound) == &val ) {
2533 bucket( nTable, arrHash[nTable]).remove( arrPos[nTable].itPrev, arrPos[nTable].itFound );
2535 m_Stat.onUnlinkSuccess();
2540 m_Stat.onUnlinkFailed();
2544 /// Deletes the item from the set
2545 /** \anchor cds_intrusive_CuckooSet_erase
2546 The function searches an item with key equal to \p val in the set,
2547 unlinks it from the set, and returns a pointer to unlinked item.
2549 If the item with key equal to \p val is not found the function return \p nullptr.
2551 Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
2553 template <typename Q>
2554 value_type * erase( Q const& val )
2556 return erase( val, [](value_type const&) {} );
2559 /// Deletes the item from the set using \p pred predicate for searching
2561 The function is an analog of \ref cds_intrusive_CuckooSet_erase "erase(Q const&)"
2562 but \p pred is used for key comparing.
2563 If cuckoo set is ordered, then \p Predicate should have the interface and semantics like \p std::less.
2564 If cuckoo set is unordered, then \p Predicate should have the interface and semantics like \p std::equal_to.
2565 \p Predicate must imply the same element order as the comparator used for building the set.
2567 template <typename Q, typename Predicate>
2568 value_type * erase_with( Q const& val, Predicate pred )
2571 return erase_( val, typename predicate_wrapper<Predicate>::type(), [](value_type const&) {} );
2574 /// Delete the item from the set
2575 /** \anchor cds_intrusive_CuckooSet_erase_func
2576 The function searches an item with key equal to \p val in the set,
2577 call \p f functor with item found, unlinks it from the set, and returns a pointer to unlinked item.
2579 The \p Func interface is
2582 void operator()( value_type const& item );
2586 If the item with key equal to \p val is not found the function return \p nullptr.
2588 Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
2590 template <typename Q, typename Func>
2591 value_type * erase( Q const& val, Func f )
2593 return erase_( val, key_predicate(), f );
2596 /// Deletes the item from the set using \p pred predicate for searching
2598 The function is an analog of \ref cds_intrusive_CuckooSet_erase_func "erase(Q const&, Func)"
2599 but \p pred is used for key comparing.
2600 If you use ordered cuckoo set, then \p Predicate should have the interface and semantics like \p std::less.
2601 If you use unordered cuckoo set, then \p Predicate should have the interface and semantics like \p std::equal_to.
2602 \p Predicate must imply the same element order as the comparator used for building the set.
2604 template <typename Q, typename Predicate, typename Func>
2605 value_type * erase_with( Q const& val, Predicate pred, Func f )
2608 return erase_( val, typename predicate_wrapper<Predicate>::type(), f );
2611 /// Find the key \p val
2612 /** \anchor cds_intrusive_CuckooSet_find_func
2613 The function searches the item with key equal to \p val and calls the functor \p f for item found.
2614 The interface of \p Func functor is:
2617 void operator()( value_type& item, Q& val );
2620 where \p item is the item found, \p val is the <tt>find</tt> function argument.
2622 The functor may change non-key fields of \p item.
2624 The \p val argument is non-const since it can be used as \p f functor destination i.e., the functor
2625 may modify both arguments.
2627 Note the hash functor specified for class \p Traits template parameter
2628 should accept a parameter of type \p Q that can be not the same as \p value_type.
2630 The function returns \p true if \p val is found, \p false otherwise.
2632 template <typename Q, typename Func>
2633 bool find( Q& val, Func f )
2635 return find_( val, key_predicate(), f );
2638 template <typename Q, typename Func>
2639 bool find( Q const& val, Func f )
2641 return find_( val, key_predicate(), f );
2645 /// Find the key \p val using \p pred predicate for comparing
2647 The function is an analog of \ref cds_intrusive_CuckooSet_find_func "find(Q&, Func)"
2648 but \p pred is used for key comparison.
2649 If you use ordered cuckoo set, then \p Predicate should have the interface and semantics like \p std::less.
2650 If you use unordered cuckoo set, then \p Predicate should have the interface and semantics like \p std::equal_to.
2651 \p pred must imply the same element order as the comparator used for building the set.
2653 template <typename Q, typename Predicate, typename Func>
2654 bool find_with( Q& val, Predicate pred, Func f )
2657 return find_( val, typename predicate_wrapper<Predicate>::type(), f );
2660 template <typename Q, typename Predicate, typename Func>
2661 bool find_with( Q const& val, Predicate pred, Func f )
2664 return find_( val, typename predicate_wrapper<Predicate>::type(), f );
2668 /// Checks whether the set contains \p key
2670 The function searches the item with key equal to \p key
2671 and returns \p true if it is found, and \p false otherwise.
2673 template <typename Q>
2674 bool contains( Q const& key )
2676 return find( key, [](value_type&, Q const& ) {} );
2679 template <typename Q>
2680 CDS_DEPRECATED("deprecated, use contains()")
2681 bool find( Q const& key )
2683 return contains( key );
2687 /// Checks whether the set contains \p key using \p pred predicate for searching
2689 The function is similar to <tt>contains( key )</tt> but \p pred is used for key comparing.
2690 \p Less functor has the interface like \p std::less.
2691 \p Less must imply the same element order as the comparator used for building the set.
2693 template <typename Q, typename Predicate>
2694 bool contains( Q const& key, Predicate pred )
2697 return find_with( key, typename predicate_wrapper<Predicate>::type(), [](value_type& , Q const& ) {} );
2700 template <typename Q, typename Predicate>
2701 CDS_DEPRECATED("deprecated, use contains()")
2702 bool find_with( Q const& key, Predicate pred )
2704 return contains( key, pred );
2710 The function unlinks all items from the set.
2711 For any item \ref disposer is called
2715 clear_and_dispose( disposer() );
2718 /// Clears the set and calls \p disposer for each item
2720 The function unlinks all items from the set calling \p disposer for each item.
2721 \p Disposer functor interface is:
2724 void operator()( value_type * p );
2728 The \ref disposer specified in \p Traits traits is not called.
2730 template <typename Disposer>
2731 void clear_and_dispose( Disposer oDisposer )
2733 // locks entire array
2734 scoped_full_lock sl( m_MutexPolicy );
2736 for ( unsigned int i = 0; i < c_nArity; ++i ) {
2737 bucket_entry * pEntry = m_BucketTable[i];
2738 bucket_entry * pEnd = pEntry + m_nBucketMask + 1;
2739 for ( ; pEntry != pEnd ; ++pEntry ) {
2740 pEntry->clear( [&oDisposer]( node_type * pNode ){ oDisposer( node_traits::to_value_ptr( pNode )) ; } );
2743 m_ItemCounter.reset();
2746 /// Checks if the set is empty
2748 Emptiness is checked by item counting: if item count is zero then the set is empty.
2755 /// Returns item count in the set
2758 return m_ItemCounter;
2761 /// Returns the size of hash table
2763 The hash table size is non-constant and can be increased via resizing.
2765 size_t bucket_count() const
2767 return m_nBucketMask + 1;
2770 /// Returns lock array size
2771 size_t lock_count() const
2773 return m_MutexPolicy.lock_count();
2776 /// Returns const reference to internal statistics
2777 stat const& statistics() const
2782 /// Returns const reference to mutex policy internal statistics
2783 typename mutex_policy::statistics_type const& mutex_policy_statistics() const
2785 return m_MutexPolicy.statistics();
2788 }} // namespace cds::intrusive
2790 #endif // #ifndef CDSLIB_INTRUSIVE_CUCKOO_SET_H