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
23 struct implementation_tag;
26 /// Option to define probeset type
28 The option specifies probeset type for the CuckooSet.
30 - \p cds::intrusive::cuckoo::list - the probeset is a single-linked list.
31 The node contains pointer to next node in probeset.
32 - \p cds::intrusive::cuckoo::vector<Capacity> - the probeset is a vector
33 with constant-size \p Capacity where \p Capacity is an <tt>unsigned int</tt> constant.
34 The node does not contain any auxiliary data.
36 template <typename Type>
40 template <typename Base>
41 struct pack: public Base {
42 typedef Type probeset_type;
47 /// Option specifying whether to store hash values in the node
49 This option reserves additional space in the hook to store the hash value of the object once it's introduced in the container.
50 When this option is used, the unordered container will store the calculated hash value in the hook and rehashing operations won't need
51 to recalculate the hash of the value. This option will improve the performance of unordered containers
52 when rehashing is frequent or hashing the value is a slow operation
54 The \p Count template parameter defines the size of hash array. Remember that cuckoo hashing implies at least two
57 Possible values of \p Count:
58 - 0 - no hash storing in the node
59 - greater that 1 - store hash values.
61 Value 1 is deprecated.
63 template <unsigned int Count>
67 template <typename Base>
68 struct pack: public Base {
69 static unsigned int const store_hash = Count;
76 // Probeset type placeholders
77 struct list_probeset_class;
78 struct vector_probeset_class;
82 /// List probeset type
86 /// Vector probeset type
87 template <unsigned int Capacity>
91 static unsigned int const c_nCapacity = Capacity;
97 - \p ProbesetType - type of probeset. Can be \p cds::intrusive::cuckoo::list
98 or \p cds::intrusive::cuckoo::vector<Capacity>.
99 - \p StoreHashCount - constant that defines whether to store node hash values.
100 See cuckoo::store_hash option for explanation
101 - \p Tag - a \ref cds_intrusive_hook_tag "tag"
103 template <typename ProbesetType = cuckoo::list, unsigned int StoreHashCount = 0, typename Tag = opt::none>
105 #ifdef CDS_DOXYGEN_INVOKED
107 typedef ProbesetType probeset_type ; ///< Probeset type
108 typedef Tag tag ; ///< Tag
109 static unsigned int const hash_array_size = StoreHashCount ; ///< The size of hash array
115 template <typename Tag>
116 struct node< cuckoo::list, 0, Tag>
118 typedef list_probeset_class probeset_class;
119 typedef cuckoo::list probeset_type;
121 static unsigned int const hash_array_size = 0;
122 static unsigned int const probeset_size = 0;
126 CDS_CONSTEXPR node() CDS_NOEXCEPT
130 void store_hash( size_t * )
133 size_t * get_hash() const
135 // This node type does not store hash values!!!
146 template <unsigned int StoreHashCount, typename Tag>
147 struct node< cuckoo::list, StoreHashCount, Tag>
149 typedef list_probeset_class probeset_class;
150 typedef cuckoo::list probeset_type;
152 static unsigned int const hash_array_size = StoreHashCount;
153 static unsigned int const probeset_size = 0;
156 size_t m_arrHash[ hash_array_size ];
161 memset( m_arrHash, 0, sizeof(m_arrHash));
164 void store_hash( size_t * pHashes )
166 memcpy( m_arrHash, pHashes, hash_array_size );
169 size_t * get_hash() const
171 return const_cast<size_t *>( m_arrHash );
180 template <unsigned int VectorSize, typename Tag>
181 struct node< cuckoo::vector<VectorSize>, 0, Tag>
183 typedef vector_probeset_class probeset_class;
184 typedef cuckoo::vector<VectorSize> probeset_type;
186 static unsigned int const hash_array_size = 0;
187 static unsigned int const probeset_size = probeset_type::c_nCapacity;
192 void store_hash( size_t * )
195 size_t * get_hash() const
197 // This node type does not store hash values!!!
206 template <unsigned int VectorSize, unsigned int StoreHashCount, typename Tag>
207 struct node< cuckoo::vector<VectorSize>, StoreHashCount, Tag>
209 typedef vector_probeset_class probeset_class;
210 typedef cuckoo::vector<VectorSize> probeset_type;
212 static unsigned int const hash_array_size = StoreHashCount;
213 static unsigned int const probeset_size = probeset_type::c_nCapacity;
215 size_t m_arrHash[ hash_array_size ];
219 memset( m_arrHash, 0, sizeof(m_arrHash));
222 void store_hash( size_t * pHashes )
224 memcpy( m_arrHash, pHashes, hash_array_size );
227 size_t * get_hash() const
229 return const_cast<size_t *>( m_arrHash );
239 struct default_hook {
240 typedef cuckoo::list probeset_type;
241 static unsigned int const store_hash = 0;
242 typedef opt::none tag;
245 template < typename HookType, typename... Options>
248 typedef typename opt::make_options< default_hook, Options...>::type traits;
250 typedef typename traits::probeset_type probeset_type;
251 typedef typename traits::tag tag;
252 static unsigned int const store_hash = traits::store_hash;
254 typedef node<probeset_type, store_hash, tag> node_type;
256 typedef HookType hook_type;
263 - \p cuckoo::probeset_type - probeset type. Defaul is \p cuckoo::list
264 - \p cuckoo::store_hash - store hash values in the node or not. Default is 0 (no storing)
265 - \p opt::tag - a \ref cds_intrusive_hook_tag "tag"
267 template < typename... Options >
268 struct base_hook: public hook< opt::base_hook_tag, Options... >
273 \p MemberOffset defines offset in bytes of \ref node member into your structure.
274 Use \p offsetof macro to define \p MemberOffset
277 - \p cuckoo::probeset_type - probeset type. Defaul is \p cuckoo::list
278 - \p cuckoo::store_hash - store hash values in the node or not. Default is 0 (no storing)
279 - \p opt::tag - a \ref cds_intrusive_hook_tag "tag"
281 template < size_t MemberOffset, typename... Options >
282 struct member_hook: public hook< opt::member_hook_tag, Options... >
285 static const size_t c_nMemberOffset = MemberOffset;
291 \p NodeTraits defines type traits for node.
292 See \ref node_traits for \p NodeTraits interface description
295 - \p cuckoo::probeset_type - probeset type. Defaul is \p cuckoo::list
296 - \p cuckoo::store_hash - store hash values in the node or not. Default is 0 (no storing)
297 - \p opt::tag - a \ref cds_intrusive_hook_tag "tag"
299 template <typename NodeTraits, typename... Options >
300 struct traits_hook: public hook< opt::traits_hook_tag, Options... >
303 typedef NodeTraits node_traits;
307 /// Internal statistics for \ref striping mutex policy
308 struct striping_stat {
309 typedef cds::atomicity::event_counter counter_type; ///< Counter type
311 counter_type m_nCellLockCount ; ///< Count of obtaining cell lock
312 counter_type m_nCellTryLockCount ; ///< Count of cell \p try_lock attempts
313 counter_type m_nFullLockCount ; ///< Count of obtaining full lock
314 counter_type m_nResizeLockCount ; ///< Count of obtaining resize lock
315 counter_type m_nResizeCount ; ///< Count of resize event
318 void onCellLock() { ++m_nCellLockCount; }
319 void onCellTryLock() { ++m_nCellTryLockCount; }
320 void onFullLock() { ++m_nFullLockCount; }
321 void onResizeLock() { ++m_nResizeLockCount; }
322 void onResize() { ++m_nResizeCount; }
326 /// Dummy internal statistics for \ref striping mutex policy
327 struct empty_striping_stat {
329 void onCellLock() const {}
330 void onCellTryLock() const {}
331 void onFullLock() const {}
332 void onResizeLock() const {}
333 void onResize() const {}
337 /// Lock striping concurrent access policy
339 This is one of available opt::mutex_policy option type for CuckooSet
341 Lock striping is very simple technique.
342 The cuckoo set consists of the bucket tables and the array of locks.
343 There is single lock array for each bucket table, at least, the count of bucket table is 2.
344 Initially, the capacity of lock array and each bucket table is the same.
345 When set is resized, bucket table capacity will be doubled but lock array will not.
346 The lock \p i protects each bucket \p j, where <tt> j = i mod L </tt>,
347 where \p L - the size of lock array.
349 The policy contains an internal array of \p RecursiveLock locks.
352 - \p RecursiveLock - the type of recursive mutex. The default is \p std::recursive_mutex. The mutex type should be default-constructible.
353 Note that a recursive spin-lock is not suitable for lock striping for performance reason.
354 - \p Arity - unsigned int constant that specifies an arity. The arity is the count of hash functors, i.e., the
355 count of lock arrays. Default value is 2.
356 - \p Alloc - allocator type used for lock array memory allocation. Default is \p CDS_DEFAULT_ALLOCATOR.
357 - \p Stat - internal statistics type. Note that this template argument is automatically selected by \ref CuckooSet
358 class according to its \p opt::stat option.
361 class RecursiveLock = std::recursive_mutex,
362 unsigned int Arity = 2,
363 class Alloc = CDS_DEFAULT_ALLOCATOR,
364 class Stat = empty_striping_stat
369 typedef RecursiveLock lock_type ; ///< lock type
370 typedef Alloc allocator_type ; ///< allocator type
371 static unsigned int const c_nArity = Arity ; ///< the arity
372 typedef Stat statistics_type ; ///< Internal statistics type (\ref striping_stat or \ref empty_striping_stat)
375 typedef striping_stat real_stat;
376 typedef empty_striping_stat empty_stat;
378 template <typename Stat2>
379 struct rebind_statistics {
380 typedef striping<lock_type, c_nArity, allocator_type, Stat2> other;
384 typedef cds::sync::lock_array< lock_type, cds::sync::pow2_select_policy, allocator_type > lock_array_type ; ///< lock array type
388 class lock_array: public lock_array_type
392 lock_array(): lock_array_type( typename lock_array_type::select_cell_policy(2) ) {}
395 lock_array( size_t nCapacity ): lock_array_type( nCapacity, typename lock_array_type::select_cell_policy(nCapacity) ) {}
398 class scoped_lock: public std::unique_lock< lock_array_type >
400 typedef std::unique_lock< lock_array_type > base_class;
402 scoped_lock( lock_array& arrLock, size_t nHash ): base_class( arrLock, nHash ) {}
408 lock_array m_Locks[c_nArity] ; ///< array of lock_array_type
409 statistics_type m_Stat ; ///< internal statistics
414 class scoped_cell_lock {
415 lock_type * m_guard[c_nArity];
418 scoped_cell_lock( striping& policy, size_t const* arrHash )
420 for ( unsigned int i = 0; i < c_nArity; ++i ) {
421 m_guard[i] = &( policy.m_Locks[i].at( policy.m_Locks[i].lock( arrHash[i] )));
423 policy.m_Stat.onCellLock();
428 for ( unsigned int i = 0; i < c_nArity; ++i )
429 m_guard[i]->unlock();
433 class scoped_cell_trylock
435 typedef typename lock_array_type::lock_type lock_type;
437 lock_type * m_guard[c_nArity];
441 scoped_cell_trylock( striping& policy, size_t const* arrHash )
443 size_t nCell = policy.m_Locks[0].try_lock( arrHash[0] );
444 m_bLocked = nCell != lock_array_type::c_nUnspecifiedCell;
446 m_guard[0] = &(policy.m_Locks[0].at(nCell));
447 for ( unsigned int i = 1; i < c_nArity; ++i ) {
448 m_guard[i] = &( policy.m_Locks[i].at( policy.m_Locks[i].lock( arrHash[i] )) );
452 std::fill( m_guard, m_guard + c_nArity, nullptr );
454 policy.m_Stat.onCellTryLock();
456 ~scoped_cell_trylock()
459 for ( unsigned int i = 0; i < c_nArity; ++i )
460 m_guard[i]->unlock();
470 class scoped_full_lock {
471 std::unique_lock< lock_array_type > m_guard;
473 scoped_full_lock( striping& policy )
474 : m_guard( policy.m_Locks[0] )
476 policy.m_Stat.onFullLock();
479 /// Ctor for scoped_resize_lock - no statistics is incremented
480 scoped_full_lock( striping& policy, bool )
481 : m_guard( policy.m_Locks[0] )
485 class scoped_resize_lock: public scoped_full_lock {
487 scoped_resize_lock( striping& policy )
488 : scoped_full_lock( policy, false )
490 policy.m_Stat.onResizeLock();
498 size_t nLockCount ///< The size of lock array. Must be power of two.
501 // Trick: initialize the array of locks
502 for ( unsigned int i = 0; i < c_nArity; ++i ) {
503 lock_array * pArr = m_Locks + i;
504 pArr->lock_array::~lock_array();
505 new ( pArr ) lock_array( nLockCount );
509 /// Returns lock array size
511 Lock array size is unchanged during \p striping object lifetime
513 size_t lock_count() const
515 return m_Locks[0].size();
519 void resize( size_t )
525 /// Returns the arity of striping mutex policy
526 CDS_CONSTEXPR unsigned int arity() const CDS_NOEXCEPT
531 /// Returns internal statistics
532 statistics_type const& statistics() const
538 /// Internal statistics for \ref refinable mutex policy
539 struct refinable_stat {
540 typedef cds::atomicity::event_counter counter_type ; ///< Counter type
542 counter_type m_nCellLockCount ; ///< Count of obtaining cell lock
543 counter_type m_nCellLockWaitResizing ; ///< Count of loop iteration to wait for resizing
544 counter_type m_nCellLockArrayChanged ; ///< Count of event "Lock array has been changed when obtaining cell lock"
545 counter_type m_nCellLockFailed ; ///< Count of event "Cell lock failed because of the array is owned by other thread"
547 counter_type m_nSecondCellLockCount ; ///< Count of obtaining cell lock when another cell is already locked
548 counter_type m_nSecondCellLockFailed ; ///< Count of unsuccess obtaining cell lock when another cell is already locked
550 counter_type m_nFullLockCount ; ///< Count of obtaining full lock
551 counter_type m_nFullLockIter ; ///< Count of unsuccessfull iteration to obtain full lock
553 counter_type m_nResizeLockCount ; ///< Count of obtaining resize lock
554 counter_type m_nResizeLockIter ; ///< Count of unsuccessfull iteration to obtain resize lock
555 counter_type m_nResizeLockArrayChanged; ///< Count of event "Lock array has been changed when obtaining resize lock"
556 counter_type m_nResizeCount ; ///< Count of resize event
559 void onCellLock() { ++m_nCellLockCount; }
560 void onCellWaitResizing() { ++m_nCellLockWaitResizing; }
561 void onCellArrayChanged() { ++m_nCellLockArrayChanged; }
562 void onCellLockFailed() { ++m_nCellLockFailed; }
563 void onSecondCellLock() { ++m_nSecondCellLockCount; }
564 void onSecondCellLockFailed() { ++m_nSecondCellLockFailed; }
565 void onFullLock() { ++m_nFullLockCount; }
566 void onFullLockIter() { ++m_nFullLockIter; }
567 void onResizeLock() { ++m_nResizeLockCount; }
568 void onResizeLockIter() { ++m_nResizeLockIter; }
569 void onResizeLockArrayChanged() { ++m_nResizeLockArrayChanged; }
570 void onResize() { ++m_nResizeCount; }
574 /// Dummy internal statistics for \ref refinable mutex policy
575 struct empty_refinable_stat {
577 void onCellLock() const {}
578 void onCellWaitResizing() const {}
579 void onCellArrayChanged() const {}
580 void onCellLockFailed() const {}
581 void onSecondCellLock() const {}
582 void onSecondCellLockFailed() const {}
583 void onFullLock() const {}
584 void onFullLockIter() const {}
585 void onResizeLock() const {}
586 void onResizeLockIter() const {}
587 void onResizeLockArrayChanged() const {}
588 void onResize() const {}
592 /// Refinable concurrent access policy
594 This is one of available opt::mutex_policy option type for CuckooSet
596 Refining is like a striping technique (see cuckoo::striping)
597 but it allows growing the size of lock array when resizing the hash table.
598 So, the sizes of hash table and lock array are equal.
601 - \p RecursiveLock - the type of mutex. Reentrant (recursive) mutex is required.
602 The default is \p std::recursive_mutex. The mutex type should be default-constructible.
603 - \p Arity - unsigned int constant that specifies an arity. The arity is the count of hash functors, i.e., the
604 count of lock arrays. Default value is 2.
605 - \p BackOff - back-off strategy. Default is cds::backoff::yield
606 - \p Alloc - allocator type used for lock array memory allocation. Default is \p CDS_DEFAULT_ALLOCATOR.
607 - \p Stat - internal statistics type. Note that this template argument is automatically selected by \ref CuckooSet
608 class according to its \p opt::stat option.
611 class RecursiveLock = std::recursive_mutex,
612 unsigned int Arity = 2,
613 typename BackOff = cds::backoff::yield,
614 class Alloc = CDS_DEFAULT_ALLOCATOR,
615 class Stat = empty_refinable_stat
620 typedef RecursiveLock lock_type ; ///< lock type
621 typedef Alloc allocator_type ; ///< allocator type
622 typedef BackOff back_off ; ///< back-off strategy
623 typedef Stat statistics_type ; ///< internal statistics type
624 static unsigned int const c_nArity = Arity; ///< the arity
627 typedef refinable_stat real_stat;
628 typedef empty_refinable_stat empty_stat;
630 template <typename Stat2>
631 struct rebind_statistics {
632 typedef refinable< lock_type, c_nArity, back_off, allocator_type, Stat2> other;
638 typedef cds::sync::trivial_select_policy lock_selection_policy;
640 class lock_array_type
641 : public cds::sync::lock_array< lock_type, lock_selection_policy, allocator_type >
642 , public std::enable_shared_from_this< lock_array_type >
644 typedef cds::sync::lock_array< lock_type, lock_selection_policy, allocator_type > lock_array_base;
646 lock_array_type( size_t nCapacity )
647 : lock_array_base( nCapacity )
650 typedef std::shared_ptr< lock_array_type > lock_array_ptr;
651 typedef cds::details::Allocator< lock_array_type, allocator_type > lock_array_allocator;
653 typedef unsigned long long owner_t;
654 typedef cds::OS::ThreadId threadId_t;
656 typedef cds::sync::spin spinlock_type;
657 typedef std::unique_lock< spinlock_type > scoped_spinlock;
662 static owner_t const c_nOwnerMask = (((owner_t) 1) << (sizeof(owner_t) * 8 - 1)) - 1;
664 atomics::atomic< owner_t > m_Owner ; ///< owner mark (thread id + boolean flag)
665 atomics::atomic<size_t> m_nCapacity ; ///< lock array capacity
666 lock_array_ptr m_arrLocks[ c_nArity ] ; ///< Lock array. The capacity of array is specified in constructor.
667 spinlock_type m_access ; ///< access to m_arrLocks
668 statistics_type m_Stat ; ///< internal statistics
673 struct lock_array_disposer {
674 void operator()( lock_array_type * pArr )
676 lock_array_allocator().Delete( pArr );
680 lock_array_ptr create_lock_array( size_t nCapacity )
682 return lock_array_ptr( lock_array_allocator().New( nCapacity ), lock_array_disposer() );
685 void acquire( size_t const * arrHash, lock_array_ptr * pLockArr, lock_type ** parrLock )
687 owner_t me = (owner_t) cds::OS::get_current_thread_id();
694 scoped_spinlock sl(m_access);
695 for ( unsigned int i = 0; i < c_nArity; ++i )
696 pLockArr[i] = m_arrLocks[i];
699 // wait while resizing
701 who = m_Owner.load( atomics::memory_order_acquire );
702 if ( !( who & 1 ) || (who >> 1) == (me & c_nOwnerMask) )
705 m_Stat.onCellWaitResizing();
708 if ( pLockArr[0] != m_arrLocks[0] ) {
709 m_Stat.onCellArrayChanged();
713 size_t const nMask = pLockArr[0]->size() - 1;
714 assert( cds::beans::is_power2( nMask + 1 ));
716 for ( unsigned int i = 0; i < c_nArity; ++i ) {
717 parrLock[i] = &( pLockArr[i]->at( arrHash[i] & nMask ));
721 who = m_Owner.load( atomics::memory_order_acquire );
722 if ( ( !(who & 1) || (who >> 1) == (me & c_nOwnerMask) ) && m_arrLocks[0] == pLockArr[0] ) {
727 for ( unsigned int i = 0; i < c_nArity; ++i ) {
728 parrLock[i]->unlock();
731 m_Stat.onCellLockFailed();
734 // clears pLockArr can lead to calling dtor for each item of pLockArr[i] that may be a heavy-weighted operation
735 // (each pLockArr[i] is a shared pointer to array of a ton of mutexes)
736 // It is better to do this before the next loop iteration where we will use spin-locked assignment to pLockArr
737 // Destructing a lot of mutexes under spin-lock is a bad solution
738 for ( unsigned int i = 0; i < c_nArity; ++i )
743 bool try_second_acquire( size_t const * arrHash, lock_type ** parrLock )
745 // It is assumed that the current thread already has a lock
746 // and requires a second lock for other hash
748 size_t const nMask = m_nCapacity.load(atomics::memory_order_acquire) - 1;
749 size_t nCell = m_arrLocks[0]->try_lock( arrHash[0] & nMask);
750 if ( nCell == lock_array_type::c_nUnspecifiedCell ) {
751 m_Stat.onSecondCellLockFailed();
754 parrLock[0] = &(m_arrLocks[0]->at(nCell));
756 for ( unsigned int i = 1; i < c_nArity; ++i ) {
757 parrLock[i] = &( m_arrLocks[i]->at( m_arrLocks[i]->lock( arrHash[i] & nMask)) );
760 m_Stat.onSecondCellLock();
766 owner_t me = (owner_t) cds::OS::get_current_thread_id();
771 if ( m_Owner.compare_exchange_strong( ownNull, (me << 1) | 1, atomics::memory_order_acq_rel, atomics::memory_order_relaxed )) {
772 m_arrLocks[0]->lock_all();
778 m_Stat.onFullLockIter();
784 m_arrLocks[0]->unlock_all();
785 m_Owner.store( 0, atomics::memory_order_release );
788 void acquire_resize( lock_array_ptr * pOldLocks )
790 owner_t me = (owner_t) cds::OS::get_current_thread_id();
794 scoped_spinlock sl(m_access);
795 for ( unsigned int i = 0; i < c_nArity; ++i )
796 pOldLocks[i] = m_arrLocks[i];
801 if ( m_Owner.compare_exchange_strong( ownNull, (me << 1) | 1, atomics::memory_order_acq_rel, atomics::memory_order_relaxed )) {
802 if ( pOldLocks[0] != m_arrLocks[0] ) {
803 m_Owner.store( 0, atomics::memory_order_release );
804 m_Stat.onResizeLockArrayChanged();
807 pOldLocks[0]->lock_all();
808 m_Stat.onResizeLock();
813 m_Stat.onResizeLockIter();
815 // clears pOldLocks can lead to calling dtor for each item of pOldLocks[i] that may be a heavy-weighted operation
816 // (each pOldLocks[i] is a shared pointer to array of a ton of mutexes)
817 // It is better to do this before the next loop iteration where we will use spin-locked assignment to pOldLocks
818 // Destructing a lot of mutexes under spin-lock is a bad solution
819 for ( unsigned int i = 0; i < c_nArity; ++i )
820 pOldLocks[i].reset();
824 void release_resize( lock_array_ptr * pOldLocks )
826 m_Owner.store( 0, atomics::memory_order_release );
827 pOldLocks[0]->unlock_all();
833 class scoped_cell_lock {
834 lock_type * m_arrLock[ c_nArity ];
835 lock_array_ptr m_arrLockArr[ c_nArity ];
838 scoped_cell_lock( refinable& policy, size_t const* arrHash )
840 policy.acquire( arrHash, m_arrLockArr, m_arrLock );
845 for ( unsigned int i = 0; i < c_nArity; ++i )
846 m_arrLock[i]->unlock();
850 class scoped_cell_trylock {
851 lock_type * m_arrLock[ c_nArity ];
855 scoped_cell_trylock( refinable& policy, size_t const* arrHash )
857 m_bLocked = policy.try_second_acquire( arrHash, m_arrLock );
860 ~scoped_cell_trylock()
863 for ( unsigned int i = 0; i < c_nArity; ++i )
864 m_arrLock[i]->unlock();
874 class scoped_full_lock {
877 scoped_full_lock( refinable& policy )
880 policy.acquire_all();
884 m_policy.release_all();
888 class scoped_resize_lock
891 lock_array_ptr m_arrLocks[ c_nArity ];
893 scoped_resize_lock( refinable& policy )
896 policy.acquire_resize( m_arrLocks );
898 ~scoped_resize_lock()
900 m_policy.release_resize( m_arrLocks );
908 size_t nLockCount ///< The size of lock array. Must be power of two.
910 , m_nCapacity( nLockCount )
912 assert( cds::beans::is_power2( nLockCount ));
913 for ( unsigned int i = 0; i < c_nArity; ++i )
914 m_arrLocks[i] = create_lock_array( nLockCount );
918 void resize( size_t nCapacity )
920 lock_array_ptr pNew[ c_nArity ];
921 for ( unsigned int i = 0; i < c_nArity; ++i )
922 pNew[i] = create_lock_array( nCapacity );
925 // Assignment m_arrLocks[i] = pNew[i] may call heavy-weighted dtor for each item of m_arrLocks
926 // that is unacceptable under spin-lock
927 // So, we store copy of m_arrLocks in pOld
928 lock_array_ptr pOld[ c_nArity ];
929 for ( unsigned int i = 0; i < c_nArity; ++i )
930 pOld[i] = m_arrLocks[i];
932 // m_arrLocks assignment will not lead to calling dtor of each item of m_arrLocks
933 // since copy of m_arrLocks locates in pOld and assignment will not be too painful for spin-lock
937 scoped_spinlock sl(m_access);
938 for ( unsigned int i = 0; i < c_nArity; ++i )
939 m_arrLocks[i] = pNew[i];
941 m_nCapacity.store( nCapacity, atomics::memory_order_release );
947 /// Returns lock array size
949 Lock array size is not a constant for \p refinable policy and can be changed when the set is resized.
951 size_t lock_count() const
953 return m_nCapacity.load(atomics::memory_order_relaxed);
956 /// Returns the arity of \p refinable mutex policy
957 CDS_CONSTEXPR unsigned int arity() const CDS_NOEXCEPT
962 /// Returns internal statistics
963 statistics_type const& statistics() const
969 /// CuckooSet internal statistics
971 typedef cds::atomicity::event_counter counter_type ; ///< Counter type
973 counter_type m_nRelocateCallCount ; ///< Count of \p relocate function call
974 counter_type m_nRelocateRoundCount ; ///< Count of attempts to relocate items
975 counter_type m_nFalseRelocateCount ; ///< Count of unneeded attempts of \p relocate call
976 counter_type m_nSuccessRelocateCount ; ///< Count of successfull item relocating
977 counter_type m_nRelocateAboveThresholdCount; ///< Count of item relocating above probeset threshold
978 counter_type m_nFailedRelocateCount ; ///< Count of failed relocation attemp (when all probeset is full)
980 counter_type m_nResizeCallCount ; ///< Count of \p resize function call
981 counter_type m_nFalseResizeCount ; ///< Count of false \p resize function call (when other thread has been resized the set)
982 counter_type m_nResizeSuccessNodeMove; ///< Count of successfull node moving when resizing
983 counter_type m_nResizeRelocateCall ; ///< Count of \p relocate function call from \p resize function
985 counter_type m_nInsertSuccess ; ///< Count of successfull \p insert function call
986 counter_type m_nInsertFailed ; ///< Count of failed \p insert function call
987 counter_type m_nInsertResizeCount ; ///< Count of \p resize function call from \p insert
988 counter_type m_nInsertRelocateCount ; ///< Count of \p relocate function call from \p insert
989 counter_type m_nInsertRelocateFault ; ///< Count of failed \p relocate function call from \p insert
991 counter_type m_nUpdateExistCount ; ///< Count of call \p update() function for existing node
992 counter_type m_nUpdateSuccessCount ; ///< Count of successfull \p insert function call for new node
993 counter_type m_nUpdateResizeCount ; ///< Count of \p resize function call from \p update()
994 counter_type m_nUpdateRelocateCount ; ///< Count of \p relocate function call from \p update()
995 counter_type m_nUpdateRelocateFault ; ///< Count of failed \p relocate function call from \p update()
997 counter_type m_nUnlinkSuccess ; ///< Count of success \p unlink function call
998 counter_type m_nUnlinkFailed ; ///< Count of failed \p unlink function call
1000 counter_type m_nEraseSuccess ; ///< Count of success \p erase function call
1001 counter_type m_nEraseFailed ; ///< Count of failed \p erase function call
1003 counter_type m_nFindSuccess ; ///< Count of success \p find function call
1004 counter_type m_nFindFailed ; ///< Count of failed \p find function call
1006 counter_type m_nFindEqualSuccess ; ///< Count of success \p find_equal function call
1007 counter_type m_nFindEqualFailed ; ///< Count of failed \p find_equal function call
1009 counter_type m_nFindWithSuccess ; ///< Count of success \p find_with function call
1010 counter_type m_nFindWithFailed ; ///< Count of failed \p find_with function call
1013 void onRelocateCall() { ++m_nRelocateCallCount; }
1014 void onRelocateRound() { ++m_nRelocateRoundCount; }
1015 void onFalseRelocateRound() { ++m_nFalseRelocateCount; }
1016 void onSuccessRelocateRound(){ ++m_nSuccessRelocateCount; }
1017 void onRelocateAboveThresholdRound() { ++m_nRelocateAboveThresholdCount; }
1018 void onFailedRelocate() { ++m_nFailedRelocateCount; }
1020 void onResizeCall() { ++m_nResizeCallCount; }
1021 void onFalseResizeCall() { ++m_nFalseResizeCount; }
1022 void onResizeSuccessMove() { ++m_nResizeSuccessNodeMove; }
1023 void onResizeRelocateCall() { ++m_nResizeRelocateCall; }
1025 void onInsertSuccess() { ++m_nInsertSuccess; }
1026 void onInsertFailed() { ++m_nInsertFailed; }
1027 void onInsertResize() { ++m_nInsertResizeCount; }
1028 void onInsertRelocate() { ++m_nInsertRelocateCount; }
1029 void onInsertRelocateFault() { ++m_nInsertRelocateFault; }
1031 void onUpdateExist() { ++m_nUpdateExistCount; }
1032 void onUpdateSuccess() { ++m_nUpdateSuccessCount; }
1033 void onUpdateResize() { ++m_nUpdateResizeCount; }
1034 void onUpdateRelocate() { ++m_nUpdateRelocateCount; }
1035 void onUpdateRelocateFault() { ++m_nUpdateRelocateFault; }
1037 void onUnlinkSuccess() { ++m_nUnlinkSuccess; }
1038 void onUnlinkFailed() { ++m_nUnlinkFailed; }
1040 void onEraseSuccess() { ++m_nEraseSuccess; }
1041 void onEraseFailed() { ++m_nEraseFailed; }
1043 void onFindSuccess() { ++m_nFindSuccess; }
1044 void onFindFailed() { ++m_nFindFailed; }
1046 void onFindWithSuccess() { ++m_nFindWithSuccess; }
1047 void onFindWithFailed() { ++m_nFindWithFailed; }
1051 /// CuckooSet empty internal statistics
1054 void onRelocateCall() const {}
1055 void onRelocateRound() const {}
1056 void onFalseRelocateRound() const {}
1057 void onSuccessRelocateRound()const {}
1058 void onRelocateAboveThresholdRound() const {}
1059 void onFailedRelocate() const {}
1061 void onResizeCall() const {}
1062 void onFalseResizeCall() const {}
1063 void onResizeSuccessMove() const {}
1064 void onResizeRelocateCall() const {}
1066 void onInsertSuccess() const {}
1067 void onInsertFailed() const {}
1068 void onInsertResize() const {}
1069 void onInsertRelocate() const {}
1070 void onInsertRelocateFault() const {}
1072 void onUpdateExist() const {}
1073 void onUpdateSuccess() const {}
1074 void onUpdateResize() const {}
1075 void onUpdateRelocate() const {}
1076 void onUpdateRelocateFault() const {}
1078 void onUnlinkSuccess() const {}
1079 void onUnlinkFailed() const {}
1081 void onEraseSuccess() const {}
1082 void onEraseFailed() const {}
1084 void onFindSuccess() const {}
1085 void onFindFailed() const {}
1087 void onFindWithSuccess() const {}
1088 void onFindWithFailed() const {}
1092 /// Type traits for CuckooSet class
1097 Possible values are: cuckoo::base_hook, cuckoo::member_hook, cuckoo::traits_hook.
1099 typedef base_hook<> hook;
1101 /// Hash functors tuple
1103 This is mandatory type and has no predefined one.
1105 At least, two hash functors should be provided. All hash functor
1106 should be orthogonal (different): for each <tt> i,j: i != j => h[i](x) != h[j](x) </tt>.
1107 The hash functors are defined as <tt> std::tuple< H1, H2, ... Hn > </tt>:
1108 \@code cds::opt::hash< std::tuple< h1, h2 > > \@endcode
1109 The number of hash functors specifies the number \p k - the count of hash tables in cuckoo hashing.
1111 To specify hash tuple in traits you should use \p cds::opt::hash_tuple:
1113 struct my_traits: public cds::intrusive::cuckoo::traits {
1114 typedef cds::opt::hash_tuple< hash1, hash2 > hash;
1118 typedef cds::opt::none hash;
1120 /// Concurrent access policy
1122 Available opt::mutex_policy types:
1123 - \p cuckoo::striping - simple, but the lock array is not resizable
1124 - \p cuckoo::refinable - resizable lock array, but more complex access to set data.
1126 Default is \p cuckoo::striping.
1128 typedef cuckoo::striping<> mutex_policy;
1130 /// Key equality functor
1132 Default is <tt>std::equal_to<T></tt>
1134 typedef opt::none equal_to;
1136 /// Key comparing functor
1138 No default functor is provided. If the option is not specified, the \p less is used.
1140 typedef opt::none compare;
1142 /// specifies binary predicate used for key comparison.
1144 Default is \p std::less<T>.
1146 typedef opt::none less;
1150 The type for item counting feature.
1151 Default is \p cds::atomicity::item_counter
1153 Only atomic item counter type is allowed.
1155 typedef atomicity::item_counter item_counter;
1159 The allocator type for allocating bucket tables.
1161 typedef CDS_DEFAULT_ALLOCATOR allocator;
1165 The disposer functor is used in \p CuckooSet::clear() member function
1168 typedef intrusive::opt::v::empty_disposer disposer;
1170 /// Internal statistics. Available statistics: \p cuckoo::stat, \p cuckoo::empty_stat
1171 typedef empty_stat stat;
1174 /// Metafunction converting option list to \p CuckooSet traits
1176 Template argument list \p Options... are:
1177 - \p intrusive::opt::hook - hook used. Possible values are: \p cuckoo::base_hook, \p cuckoo::member_hook,
1178 \p cuckoo::traits_hook.
1179 If the option is not specified, <tt>%cuckoo::base_hook<></tt> is used.
1180 - \p opt::hash - hash functor tuple, mandatory option. At least, two hash functors should be provided. All hash functor
1181 should be orthogonal (different): for each <tt> i,j: i != j => h[i](x) != h[j](x) </tt>.
1182 The hash functors are passed as <tt> std::tuple< H1, H2, ... Hn > </tt>. The number of hash functors specifies
1183 the number \p k - the count of hash tables in cuckoo hashing.
1184 - \p opt::mutex_policy - concurrent access policy.
1185 Available policies: \p cuckoo::striping, \p cuckoo::refinable.
1186 Default is \p %cuckoo::striping.
1187 - \p opt::equal_to - key equality functor like \p std::equal_to.
1188 If this functor is defined then the probe-set will be unordered.
1189 If \p %opt::compare or \p %opt::less option is specified too, then the probe-set will be ordered
1190 and \p %opt::equal_to will be ignored.
1191 - \p opt::compare - key comparison functor. No default functor is provided.
1192 If the option is not specified, the \p %opt::less is used.
1193 If \p %opt::compare or \p %opt::less option is specified, then the probe-set will be ordered.
1194 - \p opt::less - specifies binary predicate used for key comparison. Default is \p std::less<T>.
1195 If \p %opt::compare or \p %opt::less option is specified, then the probe-set will be ordered.
1196 - \p opt::item_counter - the type of item counting feature. Default is \p atomicity::item_counter
1197 The item counter should be atomic.
1198 - \p opt::allocator - the allocator type using for allocating bucket tables.
1199 Default is \ref CDS_DEFAULT_ALLOCATOR
1200 - \p intrusive::opt::disposer - the disposer type used in \p clear() member function for
1201 freeing nodes. Default is \p intrusive::opt::v::empty_disposer
1202 - \p opt::stat - internal statistics. Possibly types: \p cuckoo::stat, \p cuckoo::empty_stat.
1203 Default is \p %cuckoo::empty_stat
1205 The probe set traits \p cuckoo::probeset_type and \p cuckoo::store_hash are taken from \p node type
1206 specified by \p opt::hook option.
1208 template <typename... Options>
1209 struct make_traits {
1210 typedef typename cds::opt::make_options<
1211 typename cds::opt::find_type_traits< cuckoo::traits, Options... >::type
1213 >::type type ; ///< Result of metafunction
1218 template <typename Node, typename Probeset>
1221 template <typename Node>
1222 class bucket_entry<Node, cuckoo::list>
1225 typedef Node node_type;
1226 typedef cuckoo::list_probeset_class probeset_class;
1227 typedef cuckoo::list probeset_type;
1237 friend class bucket_entry;
1243 iterator( node_type * p )
1246 iterator( iterator const& it)
1250 iterator& operator=( iterator const& it )
1256 iterator& operator=( node_type * p )
1262 node_type * operator->()
1266 node_type& operator*()
1268 assert( pNode != nullptr );
1273 iterator& operator ++()
1276 pNode = pNode->m_pNext;
1280 bool operator==(iterator const& it ) const
1282 return pNode == it.pNode;
1284 bool operator!=(iterator const& it ) const
1286 return !( *this == it );
1295 static_assert(( std::is_same<typename node_type::probeset_type, probeset_type>::value ), "Incompatible node type" );
1300 return iterator(pHead);
1307 void insert_after( iterator it, node_type * p )
1309 node_type * pPrev = it.pNode;
1311 p->m_pNext = pPrev->m_pNext;
1322 void remove( iterator itPrev, iterator itWhat )
1324 node_type * pPrev = itPrev.pNode;
1325 node_type * pWhat = itWhat.pNode;
1326 assert( (!pPrev && pWhat == pHead) || (pPrev && pPrev->m_pNext == pWhat) );
1329 pPrev->m_pNext = pWhat->m_pNext;
1331 assert( pWhat == pHead );
1332 pHead = pHead->m_pNext;
1341 for ( node_type * pNode = pHead; pNode; pNode = pNext ) {
1342 pNext = pNode->m_pNext;
1350 template <typename Disposer>
1351 void clear( Disposer disp )
1354 for ( node_type * pNode = pHead; pNode; pNode = pNext ) {
1355 pNext = pNode->m_pNext;
1364 unsigned int size() const
1370 template <typename Node, unsigned int Capacity>
1371 class bucket_entry<Node, cuckoo::vector<Capacity> >
1374 typedef Node node_type;
1375 typedef cuckoo::vector_probeset_class probeset_class;
1376 typedef cuckoo::vector<Capacity> probeset_type;
1378 static unsigned int const c_nCapacity = probeset_type::c_nCapacity;
1381 node_type * m_arrNode[c_nCapacity];
1382 unsigned int m_nSize;
1384 void shift_up( unsigned int nFrom )
1386 assert( m_nSize < c_nCapacity );
1389 if ( nFrom < m_nSize )
1390 std::copy_backward( m_arrNode + nFrom, m_arrNode + m_nSize, m_arrNode + m_nSize + 1 );
1392 // alternative: low-level byte copying
1393 //memmove( m_arrNode + nFrom + 1, m_arrNode + nFrom, (m_nSize - nFrom) * sizeof(m_arrNode[0]) );
1396 void shift_down( node_type ** pFrom )
1398 assert( m_arrNode <= pFrom && pFrom < m_arrNode + m_nSize);
1400 std::copy( pFrom + 1, m_arrNode + m_nSize, pFrom );
1402 // alternative: low-level byte copying
1403 //memmove( pFrom + 1, pFrom, (m_nSize - nFrom - 1) * sizeof(m_arrNode[0]));
1409 friend class bucket_entry;
1415 iterator( node_type ** p )
1418 iterator( iterator const& it)
1422 iterator& operator=( iterator const& it )
1428 node_type * operator->()
1430 assert( pArr != nullptr );
1433 node_type& operator*()
1435 assert( pArr != nullptr );
1436 assert( *pArr != nullptr );
1441 iterator& operator ++()
1447 bool operator==(iterator const& it ) const
1449 return pArr == it.pArr;
1451 bool operator!=(iterator const& it ) const
1453 return !( *this == it );
1461 memset( m_arrNode, 0, sizeof(m_arrNode));
1462 static_assert(( std::is_same<typename node_type::probeset_type, probeset_type>::value ), "Incompatible node type" );
1467 return iterator(m_arrNode);
1471 return iterator(m_arrNode + size());
1474 void insert_after( iterator it, node_type * p )
1476 assert( m_nSize < c_nCapacity );
1477 assert( !it.pArr || (m_arrNode <= it.pArr && it.pArr <= m_arrNode + m_nSize));
1480 shift_up( (unsigned int)(it.pArr - m_arrNode) + 1 );
1490 void remove( iterator /*itPrev*/, iterator itWhat )
1493 shift_down( itWhat.pArr );
1502 template <typename Disposer>
1503 void clear( Disposer disp )
1505 for ( unsigned int i = 0; i < m_nSize; ++i ) {
1506 disp( m_arrNode[i] );
1511 unsigned int size() const
1517 template <typename Node, unsigned int ArraySize>
1519 static void store( Node * pNode, size_t * pHashes )
1521 memcpy( pNode->m_arrHash, pHashes, sizeof(size_t) * ArraySize );
1523 static bool equal_to( Node& node, unsigned int nTable, size_t nHash )
1525 return node.m_arrHash[nTable] == nHash;
1528 template <typename Node>
1529 struct hash_ops<Node, 0>
1531 static void store( Node * /*pNode*/, size_t * /*pHashes*/ )
1533 static bool equal_to( Node& /*node*/, unsigned int /*nTable*/, size_t /*nHash*/ )
1539 template <typename NodeTraits, bool Ordered>
1542 template <typename NodeTraits>
1543 struct contains<NodeTraits, true>
1545 template <typename BucketEntry, typename Position, typename Q, typename Compare>
1546 static bool find( BucketEntry& probeset, Position& pos, unsigned int /*nTable*/, size_t /*nHash*/, Q const& val, Compare cmp )
1549 typedef typename BucketEntry::iterator bucket_iterator;
1551 bucket_iterator itPrev;
1553 for ( bucket_iterator it = probeset.begin(), itEnd = probeset.end(); it != itEnd; ++it ) {
1554 int cmpRes = cmp( *NodeTraits::to_value_ptr(*it), val );
1555 if ( cmpRes >= 0 ) {
1557 pos.itPrev = itPrev;
1564 pos.itPrev = itPrev;
1565 pos.itFound = probeset.end();
1570 template <typename NodeTraits>
1571 struct contains<NodeTraits, false>
1573 template <typename BucketEntry, typename Position, typename Q, typename EqualTo>
1574 static bool find( BucketEntry& probeset, Position& pos, unsigned int nTable, size_t nHash, Q const& val, EqualTo eq )
1576 // Unordered version
1577 typedef typename BucketEntry::iterator bucket_iterator;
1578 typedef typename BucketEntry::node_type node_type;
1580 bucket_iterator itPrev;
1582 for ( bucket_iterator it = probeset.begin(), itEnd = probeset.end(); it != itEnd; ++it ) {
1583 if ( hash_ops<node_type, node_type::hash_array_size>::equal_to( *it, nTable, nHash ) && eq( *NodeTraits::to_value_ptr(*it), val )) {
1585 pos.itPrev = itPrev;
1591 pos.itPrev = itPrev;
1592 pos.itFound = probeset.end();
1597 } // namespace details
1600 } // namespace cuckoo
1603 /** @ingroup cds_intrusive_map
1606 - [2007] M.Herlihy, N.Shavit, M.Tzafrir "Concurrent Cuckoo Hashing. Technical report"
1607 - [2008] Maurice Herlihy, Nir Shavit "The Art of Multiprocessor Programming"
1609 <b>About Cuckoo hashing</b>
1611 [From <i>"The Art of Multiprocessor Programming"</i>]
1612 Cuckoo hashing is a hashing algorithm in which a newly added item displaces any earlier item
1613 occupying the same slot. For brevity, a table is a k-entry array of items. For a hash set f size
1614 N = 2k we use a two-entry array of tables, and two independent hash functions,
1615 <tt> h0, h1: KeyRange -> 0,...,k-1</tt>
1616 mapping the set of possible keys to entries in he array. To test whether a value \p x is in the set,
1617 <tt>find(x)</tt> tests whether either <tt>table[0][h0(x)]</tt> or <tt>table[1][h1(x)]</tt> is
1618 equal to \p x. Similarly, <tt>erase(x)</tt>checks whether \p x is in either <tt>table[0][h0(x)]</tt>
1619 or <tt>table[1][h1(x)]</tt>, ad removes it if found.
1621 The <tt>insert(x)</tt> successively "kicks out" conflicting items until every key has a slot.
1622 To add \p x, the method swaps \p x with \p y, the current occupant of <tt>table[0][h0(x)]</tt>.
1623 If the prior value was \p nullptr, it is done. Otherwise, it swaps the newly nest-less value \p y
1624 for the current occupant of <tt>table[1][h1(y)]</tt> in the same way. As before, if the prior value
1625 was \p nullptr, it is done. Otherwise, the method continues swapping entries (alternating tables)
1626 until it finds an empty slot. We might not find an empty slot, either because the table is full,
1627 or because the sequence of displacement forms a cycle. We therefore need an upper limit on the
1628 number of successive displacements we are willing to undertake. When this limit is exceeded,
1629 we resize the hash table, choose new hash functions and start over.
1631 For concurrent cuckoo hashing, rather than organizing the set as a two-dimensional table of
1632 items, we use two-dimensional table of probe sets, where a probe set is a constant-sized set
1633 of items with the same hash code. Each probe set holds at most \p PROBE_SIZE items, but the algorithm
1634 tries to ensure that when the set is quiescent (i.e no method call in progress) each probe set
1635 holds no more than <tt>THRESHOLD < PROBE_SET</tt> items. While method calls are in-flight, a probe
1636 set may temporarily hold more than \p THRESHOLD but never more than \p PROBE_SET items.
1638 In current implementation, a probe set can be defined either as a (single-linked) list
1639 or as a fixed-sized vector, optionally ordered.
1641 In description above two-table cuckoo hashing (<tt>k = 2</tt>) has been considered.
1642 We can generalize this approach for <tt>k >= 2</tt> when we have \p k hash functions
1643 <tt>h[0], ... h[k-1]</tt> and \p k tables <tt>table[0], ... table[k-1]</tt>.
1645 The search in probe set is linear, the complexity is <tt> O(PROBE_SET) </tt>.
1646 The probe set may be ordered or not. Ordered probe set can be more efficient since
1647 the average search complexity is <tt>O(PROBE_SET/2)</tt>.
1648 However, the overhead of sorting can eliminate a gain of ordered search.
1650 The probe set is ordered if opt::compare or opt::less is specified in \p Traits template
1651 parameter. Otherwise, the probe set is unordered and \p Traits must contain
1652 opt::equal_to option.
1654 The cds::intrusive::cuckoo namespace contains \p %CuckooSet-related declarations.
1657 - \p T - the type stored in the set. The type must be based on cuckoo::node (for cuckoo::base_hook)
1658 or it must have a member of type %cuckoo::node (for cuckoo::member_hook),
1659 or it must be convertible to \p %cuckoo::node (for cuckoo::traits_hook)
1660 - \p Traits - type traits, default is cuckoo::traits. It is possible to declare option-based
1661 set with \p cuckoo::make_traits metafunction result as \p Traits template argument.
1665 You should incorporate \p cuckoo::node into your struct \p T and provide
1666 appropriate \p cuckoo::traits::hook in your \p Traits template parameters.
1667 Usually, for \p Traits you define a struct based on \p cuckoo::traits.
1669 Example for base hook and list-based probe-set:
1671 #include <cds/intrusive/cuckoo_set.h>
1673 // Data stored in cuckoo set
1674 // We use list as probe-set container and store hash values in the node
1675 // (since we use two hash functions we should store 2 hash values per node)
1676 struct my_data: public cds::intrusive::cuckoo::node< cds::intrusive::cuckoo::list, 2 >
1685 // Provide equal_to functor for my_data since we will use unordered probe-set
1686 struct my_data_equal_to {
1687 bool operator()( const my_data& d1, const my_data& d2 ) const
1689 return d1.strKey.compare( d2.strKey ) == 0;
1692 bool operator()( const my_data& d, const std::string& s ) const
1694 return d.strKey.compare(s) == 0;
1697 bool operator()( const std::string& s, const my_data& d ) const
1699 return s.compare( d.strKey ) == 0;
1703 // Provide two hash functor for my_data
1705 size_t operator()(std::string const& s) const
1707 return cds::opt::v::hash<std::string>( s );
1709 size_t operator()( my_data const& d ) const
1711 return (*this)( d.strKey );
1715 struct hash2: private hash1 {
1716 size_t operator()(std::string const& s) const
1718 size_t h = ~( hash1::operator()(s));
1719 return ~h + 0x9e3779b9 + (h << 6) + (h >> 2);
1721 size_t operator()( my_data const& d ) const
1723 return (*this)( d.strKey );
1727 // Declare type traits
1728 struct my_traits: public cds::intrusive::cuckoo::traits
1730 typedef cds::intrusive::cuckoo::base_hook<
1731 cds::intrusive::cuckoo::probeset_type< my_data::probeset_type >
1732 ,cds::intrusive::cuckoo::store_hash< my_data::hash_array_size >
1734 typedef my_data_equa_to equal_to;
1735 typedef cds::opt::hash_tuple< hash1, hash2 > hash;
1738 // Declare CuckooSet type
1739 typedef cds::intrusive::CuckooSet< my_data, my_traits > my_cuckoo_set;
1741 // Equal option-based declaration
1742 typedef cds::intrusive::CuckooSet< my_data,
1743 cds::intrusive::cuckoo::make_traits<
1744 cds::intrusive::opt::hook< cds::intrusive::cuckoo::base_hook<
1745 cds::intrusive::cuckoo::probeset_type< my_data::probeset_type >
1746 ,cds::intrusive::cuckoo::store_hash< my_data::hash_array_size >
1748 ,cds::opt::hash< std::tuple< hash1, hash2 > >
1749 ,cds::opt::equal_to< my_data_equal_to >
1754 If we provide \p compare function instead of \p equal_to for \p my_data
1755 we get as a result a cuckoo set with ordered probe set that may improve
1757 Example for base hook and ordered vector-based probe-set:
1760 #include <cds/intrusive/cuckoo_set.h>
1762 // Data stored in cuckoo set
1763 // We use a vector of capacity 4 as probe-set container and store hash values in the node
1764 // (since we use two hash functions we should store 2 hash values per node)
1765 struct my_data: public cds::intrusive::cuckoo::node< cds::intrusive::cuckoo::vector<4>, 2 >
1774 // Provide compare functor for my_data since we want to use ordered probe-set
1775 struct my_data_compare {
1776 int operator()( const my_data& d1, const my_data& d2 ) const
1778 return d1.strKey.compare( d2.strKey );
1781 int operator()( const my_data& d, const std::string& s ) const
1783 return d.strKey.compare(s);
1786 int operator()( const std::string& s, const my_data& d ) const
1788 return s.compare( d.strKey );
1792 // Provide two hash functor for my_data
1794 size_t operator()(std::string const& s) const
1796 return cds::opt::v::hash<std::string>( s );
1798 size_t operator()( my_data const& d ) const
1800 return (*this)( d.strKey );
1804 struct hash2: private hash1 {
1805 size_t operator()(std::string const& s) const
1807 size_t h = ~( hash1::operator()(s));
1808 return ~h + 0x9e3779b9 + (h << 6) + (h >> 2);
1810 size_t operator()( my_data const& d ) const
1812 return (*this)( d.strKey );
1816 // Declare type traits
1817 struct my_traits: public cds::intrusive::cuckoo::traits
1819 typedef cds::intrusive::cuckoo::base_hook<
1820 cds::intrusive::cuckoo::probeset_type< my_data::probeset_type >
1821 ,cds::intrusive::cuckoo::store_hash< my_data::hash_array_size >
1823 typedef my_data_compare compare;
1824 typedef cds::opt::hash_tuple< hash1, hash2 > hash;
1827 // Declare CuckooSet type
1828 typedef cds::intrusive::CuckooSet< my_data, my_traits > my_cuckoo_set;
1830 // Equal option-based declaration
1831 typedef cds::intrusive::CuckooSet< my_data,
1832 cds::intrusive::cuckoo::make_traits<
1833 cds::intrusive::opt::hook< cds::intrusive::cuckoo::base_hook<
1834 cds::intrusive::cuckoo::probeset_type< my_data::probeset_type >
1835 ,cds::intrusive::cuckoo::store_hash< my_data::hash_array_size >
1837 ,cds::opt::hash< std::tuple< hash1, hash2 > >
1838 ,cds::opt::compare< my_data_compare >
1844 template <typename T, typename Traits = cuckoo::traits>
1848 typedef T value_type; ///< The value type stored in the set
1849 typedef Traits traits; ///< Set traits
1851 typedef typename traits::hook hook; ///< hook type
1852 typedef typename hook::node_type node_type; ///< node type
1853 typedef typename get_node_traits< value_type, node_type, hook>::type node_traits; ///< node traits
1855 typedef typename traits::hash hash; ///< hash functor tuple wrapped for internal use
1856 typedef typename hash::hash_tuple_type hash_tuple_type; ///< Type of hash tuple
1858 typedef typename traits::stat stat; ///< internal statistics type
1860 typedef typename traits::mutex_policy original_mutex_policy; ///< Concurrent access policy, see \p cuckoo::traits::mutex_policy
1862 /// Actual mutex policy
1864 Actual mutex policy is built from mutex policy type provided by \p Traits template argument (see \p cuckoo::traits::mutex_policy)
1865 but mutex policy internal statistics is conformed with \p cukoo::traits::stat type provided by \p Traits:
1866 - if \p %cuckoo::traits::stat is \p cuckoo::empty_stat then mutex policy statistics is already empty
1867 - otherwise real mutex policy statistics is used
1869 typedef typename original_mutex_policy::template rebind_statistics<
1870 typename std::conditional<
1871 std::is_same< stat, cuckoo::empty_stat >::value
1872 ,typename original_mutex_policy::empty_stat
1873 ,typename original_mutex_policy::real_stat
1875 >::other mutex_policy;
1877 static bool const c_isSorted = !( std::is_same< typename traits::compare, opt::none >::value
1878 && std::is_same< typename traits::less, opt::none >::value ) ; ///< whether the probe set should be ordered
1879 static size_t const c_nArity = hash::size ; ///< the arity of cuckoo hashing: the number of hash functors provided; minimum 2.
1881 /// Key equality functor; used only for unordered probe-set
1882 typedef typename opt::details::make_equal_to< value_type, traits, !c_isSorted>::type key_equal_to;
1884 /// key comparing functor based on opt::compare and opt::less option setter. Used only for ordered probe set
1885 typedef typename opt::details::make_comparator< value_type, traits >::type key_comparator;
1888 typedef typename traits::allocator allocator;
1890 /// item counter type
1891 typedef typename traits::item_counter item_counter;
1894 typedef typename traits::disposer disposer;
1897 typedef cds::intrusive::cuckoo::implementation_tag implementation_tag;
1901 typedef typename node_type::probeset_class probeset_class;
1902 typedef typename node_type::probeset_type probeset_type;
1903 static unsigned int const c_nNodeHashArraySize = node_type::hash_array_size;
1905 typedef typename mutex_policy::scoped_cell_lock scoped_cell_lock;
1906 typedef typename mutex_policy::scoped_cell_trylock scoped_cell_trylock;
1907 typedef typename mutex_policy::scoped_full_lock scoped_full_lock;
1908 typedef typename mutex_policy::scoped_resize_lock scoped_resize_lock;
1910 typedef cuckoo::details::bucket_entry< node_type, probeset_type > bucket_entry;
1911 typedef typename bucket_entry::iterator bucket_iterator;
1912 typedef cds::details::Allocator< bucket_entry, allocator > bucket_table_allocator;
1914 typedef size_t hash_array[c_nArity] ; ///< hash array
1917 bucket_iterator itPrev;
1918 bucket_iterator itFound;
1921 typedef typename std::conditional< c_isSorted
1922 , cuckoo::details::contains< node_traits, true >
1923 , cuckoo::details::contains< node_traits, false >
1924 >::type contains_action;
1926 template <typename Predicate>
1927 struct predicate_wrapper {
1928 typedef typename std::conditional< c_isSorted, cds::opt::details::make_comparator_from_less<Predicate>, Predicate>::type type;
1931 typedef typename std::conditional< c_isSorted, key_comparator, key_equal_to >::type key_predicate;
1935 static unsigned int const c_nDefaultProbesetSize = 4; ///< default probeset size
1936 static size_t const c_nDefaultInitialSize = 16; ///< default initial size
1937 static unsigned int const c_nRelocateLimit = c_nArity * 2 - 1; ///< Count of attempts to relocate before giving up
1940 bucket_entry * m_BucketTable[ c_nArity ] ; ///< Bucket tables
1942 size_t m_nBucketMask ; ///< Hash bitmask; bucket table size minus 1.
1943 unsigned int const m_nProbesetSize ; ///< Probe set size
1944 unsigned int const m_nProbesetThreshold ; ///< Probe set threshold
1946 hash m_Hash ; ///< Hash functor tuple
1947 mutex_policy m_MutexPolicy ; ///< concurrent access policy
1948 item_counter m_ItemCounter ; ///< item counter
1949 mutable stat m_Stat ; ///< internal statistics
1953 static void check_common_constraints()
1955 static_assert( (c_nArity == mutex_policy::c_nArity), "The count of hash functors must be equal to mutex_policy arity" );
1958 void check_probeset_properties() const
1960 assert( m_nProbesetThreshold < m_nProbesetSize );
1962 // if probe set type is cuckoo::vector<N> then m_nProbesetSize == N
1963 assert( node_type::probeset_size == 0 || node_type::probeset_size == m_nProbesetSize );
1966 template <typename Q>
1967 void hashing( size_t * pHashes, Q const& v ) const
1969 m_Hash( pHashes, v );
1972 void copy_hash( size_t * pHashes, value_type const& v ) const
1974 if ( c_nNodeHashArraySize )
1975 memcpy( pHashes, node_traits::to_node_ptr( v )->get_hash(), sizeof(pHashes[0]) * c_nNodeHashArraySize );
1977 hashing( pHashes, v );
1980 bucket_entry& bucket( unsigned int nTable, size_t nHash )
1982 assert( nTable < c_nArity );
1983 return m_BucketTable[nTable][nHash & m_nBucketMask];
1986 static void store_hash( node_type * pNode, size_t * pHashes )
1988 cuckoo::details::hash_ops< node_type, c_nNodeHashArraySize >::store( pNode, pHashes );
1991 static bool equal_hash( node_type& node, unsigned int nTable, size_t nHash )
1993 return cuckoo::details::hash_ops< node_type, c_nNodeHashArraySize >::equal_to( node, nTable, nHash );
1996 void allocate_bucket_tables( size_t nSize )
1998 assert( cds::beans::is_power2( nSize ) );
2000 m_nBucketMask = nSize - 1;
2001 bucket_table_allocator alloc;
2002 for ( unsigned int i = 0; i < c_nArity; ++i )
2003 m_BucketTable[i] = alloc.NewArray( nSize );
2006 static void free_bucket_tables( bucket_entry ** pTable, size_t nCapacity )
2008 bucket_table_allocator alloc;
2009 for ( unsigned int i = 0; i < c_nArity; ++i ) {
2010 alloc.Delete( pTable[i], nCapacity );
2011 pTable[i] = nullptr;
2014 void free_bucket_tables()
2016 free_bucket_tables( m_BucketTable, m_nBucketMask + 1 );
2019 static CDS_CONSTEXPR unsigned int const c_nUndefTable = (unsigned int) -1;
2020 template <typename Q, typename Predicate >
2021 unsigned int contains( position * arrPos, size_t * arrHash, Q const& val, Predicate pred )
2023 // Buckets must be locked
2025 for ( unsigned int i = 0; i < c_nArity; ++i ) {
2026 bucket_entry& probeset = bucket( i, arrHash[i] );
2027 if ( contains_action::find( probeset, arrPos[i], i, arrHash[i], val, pred ))
2030 return c_nUndefTable;
2033 template <typename Q, typename Predicate, typename Func>
2034 value_type * erase_( Q const& val, Predicate pred, Func f )
2037 hashing( arrHash, val );
2038 position arrPos[ c_nArity ];
2041 scoped_cell_lock guard( m_MutexPolicy, arrHash );
2043 unsigned int nTable = contains( arrPos, arrHash, val, pred );
2044 if ( nTable != c_nUndefTable ) {
2045 node_type& node = *arrPos[nTable].itFound;
2046 f( *node_traits::to_value_ptr(node) );
2047 bucket( nTable, arrHash[nTable]).remove( arrPos[nTable].itPrev, arrPos[nTable].itFound );
2049 m_Stat.onEraseSuccess();
2050 return node_traits::to_value_ptr( node );
2054 m_Stat.onEraseFailed();
2058 template <typename Q, typename Predicate, typename Func>
2059 bool find_( Q& val, Predicate pred, Func f )
2062 position arrPos[ c_nArity ];
2063 hashing( arrHash, val );
2064 scoped_cell_lock sl( m_MutexPolicy, arrHash );
2066 unsigned int nTable = contains( arrPos, arrHash, val, pred );
2067 if ( nTable != c_nUndefTable ) {
2068 f( *node_traits::to_value_ptr( *arrPos[nTable].itFound ), val );
2069 m_Stat.onFindSuccess();
2073 m_Stat.onFindFailed();
2077 bool relocate( unsigned int nTable, size_t * arrGoalHash )
2079 // arrGoalHash contains hash values for relocating element
2080 // Relocating element is first one from bucket( nTable, arrGoalHash[nTable] ) probeset
2082 m_Stat.onRelocateCall();
2086 for ( unsigned int nRound = 0; nRound < c_nRelocateLimit; ++nRound ) {
2087 m_Stat.onRelocateRound();
2090 scoped_cell_lock guard( m_MutexPolicy, arrGoalHash );
2092 bucket_entry& refBucket = bucket( nTable, arrGoalHash[nTable] );
2093 if ( refBucket.size() < m_nProbesetThreshold ) {
2094 // probeset is not above the threshold
2095 m_Stat.onFalseRelocateRound();
2099 pVal = node_traits::to_value_ptr( *refBucket.begin() );
2100 copy_hash( arrHash, *pVal );
2102 scoped_cell_trylock guard2( m_MutexPolicy, arrHash );
2103 if ( !guard2.locked() )
2104 continue ; // try one more time
2106 refBucket.remove( typename bucket_entry::iterator(), refBucket.begin() );
2108 unsigned int i = (nTable + 1) % c_nArity;
2110 // try insert into free probeset
2111 while ( i != nTable ) {
2112 bucket_entry& bkt = bucket( i, arrHash[i] );
2113 if ( bkt.size() < m_nProbesetThreshold ) {
2115 contains_action::find( bkt, pos, i, arrHash[i], *pVal, key_predicate() ) ; // must return false!
2116 bkt.insert_after( pos.itPrev, node_traits::to_node_ptr( pVal ));
2117 m_Stat.onSuccessRelocateRound();
2120 i = ( i + 1 ) % c_nArity;
2123 // try insert into partial probeset
2124 i = (nTable + 1) % c_nArity;
2125 while ( i != nTable ) {
2126 bucket_entry& bkt = bucket( i, arrHash[i] );
2127 if ( bkt.size() < m_nProbesetSize ) {
2129 contains_action::find( bkt, pos, i, arrHash[i], *pVal, key_predicate() ) ; // must return false!
2130 bkt.insert_after( pos.itPrev, node_traits::to_node_ptr( pVal ));
2132 memcpy( arrGoalHash, arrHash, sizeof(arrHash));
2133 m_Stat.onRelocateAboveThresholdRound();
2134 goto next_iteration;
2136 i = (i + 1) % c_nArity;
2139 // all probeset is full, relocating fault
2140 refBucket.insert_after( typename bucket_entry::iterator(), node_traits::to_node_ptr( pVal ));
2141 m_Stat.onFailedRelocate();
2152 m_Stat.onResizeCall();
2154 size_t nOldCapacity = bucket_count();
2155 bucket_entry * pOldTable[ c_nArity ];
2157 scoped_resize_lock guard( m_MutexPolicy );
2159 if ( nOldCapacity != bucket_count() ) {
2160 m_Stat.onFalseResizeCall();
2164 size_t nCapacity = nOldCapacity * 2;
2166 m_MutexPolicy.resize( nCapacity );
2167 memcpy( pOldTable, m_BucketTable, sizeof(pOldTable));
2168 allocate_bucket_tables( nCapacity );
2170 typedef typename bucket_entry::iterator bucket_iterator;
2172 position arrPos[ c_nArity ];
2174 for ( unsigned int nTable = 0; nTable < c_nArity; ++nTable ) {
2175 bucket_entry * pTable = pOldTable[nTable];
2176 for ( size_t k = 0; k < nOldCapacity; ++k ) {
2177 bucket_iterator itNext;
2178 for ( bucket_iterator it = pTable[k].begin(), itEnd = pTable[k].end(); it != itEnd; it = itNext ) {
2182 value_type& val = *node_traits::to_value_ptr( *it );
2183 copy_hash( arrHash, val );
2184 contains( arrPos, arrHash, val, key_predicate() ) ; // must return c_nUndefTable
2186 for ( unsigned int i = 0; i < c_nArity; ++i ) {
2187 bucket_entry& refBucket = bucket( i, arrHash[i] );
2188 if ( refBucket.size() < m_nProbesetThreshold ) {
2189 refBucket.insert_after( arrPos[i].itPrev, &*it );
2190 m_Stat.onResizeSuccessMove();
2195 for ( unsigned int i = 0; i < c_nArity; ++i ) {
2196 bucket_entry& refBucket = bucket( i, arrHash[i] );
2197 if ( refBucket.size() < m_nProbesetSize ) {
2198 refBucket.insert_after( arrPos[i].itPrev, &*it );
2199 assert( refBucket.size() > 1 );
2200 copy_hash( arrHash, *node_traits::to_value_ptr( *refBucket.begin()) );
2201 m_Stat.onResizeRelocateCall();
2202 relocate( i, arrHash );
2211 free_bucket_tables( pOldTable, nOldCapacity );
2214 CDS_CONSTEXPR static unsigned int calc_probeset_size( unsigned int nProbesetSize ) CDS_NOEXCEPT
2216 return nProbesetSize
2218 : ( node_type::probeset_size ? node_type::probeset_size : c_nDefaultProbesetSize )
2224 /// Default constructor
2226 Initial size = \ref c_nDefaultInitialSize
2229 - \p c_nDefaultProbesetSize if \p probeset_type is \p cuckoo::list
2230 - \p Capacity if \p probeset_type is <tt> cuckoo::vector<Capacity> </tt>
2232 Probe set threshold = probe set size - 1
2235 : m_nProbesetSize( calc_probeset_size(0) )
2236 , m_nProbesetThreshold( m_nProbesetSize - 1 )
2237 , m_MutexPolicy( c_nDefaultInitialSize )
2239 check_common_constraints();
2240 check_probeset_properties();
2242 allocate_bucket_tables( c_nDefaultInitialSize );
2245 /// Constructs the set object with given probe set size and threshold
2247 If probe set type is <tt> cuckoo::vector<Capacity> </tt> vector
2248 then \p nProbesetSize should be equal to vector's \p Capacity.
2251 size_t nInitialSize ///< Initial set size; if 0 - use default initial size \ref c_nDefaultInitialSize
2252 , unsigned int nProbesetSize ///< probe set size
2253 , unsigned int nProbesetThreshold = 0 ///< probe set threshold, <tt>nProbesetThreshold < nProbesetSize</tt>. If 0, nProbesetThreshold = nProbesetSize - 1
2255 : m_nProbesetSize( calc_probeset_size(nProbesetSize) )
2256 , m_nProbesetThreshold( nProbesetThreshold ? nProbesetThreshold : m_nProbesetSize - 1 )
2257 , m_MutexPolicy( cds::beans::ceil2(nInitialSize ? nInitialSize : c_nDefaultInitialSize ))
2259 check_common_constraints();
2260 check_probeset_properties();
2262 allocate_bucket_tables( nInitialSize ? cds::beans::ceil2( nInitialSize ) : c_nDefaultInitialSize );
2265 /// Constructs the set object with given hash functor tuple
2267 The probe set size and threshold are set as default, see CuckooSet()
2270 hash_tuple_type const& h ///< hash functor tuple of type <tt>std::tuple<H1, H2, ... Hn></tt> where <tt> n == \ref c_nArity </tt>
2272 : m_nProbesetSize( calc_probeset_size(0) )
2273 , m_nProbesetThreshold( m_nProbesetSize -1 )
2275 , m_MutexPolicy( c_nDefaultInitialSize )
2277 check_common_constraints();
2278 check_probeset_properties();
2280 allocate_bucket_tables( c_nDefaultInitialSize );
2283 /// Constructs the set object with given probe set properties and hash functor tuple
2285 If probe set type is <tt> cuckoo::vector<Capacity> </tt> vector
2286 then \p nProbesetSize should be equal to vector's \p Capacity.
2289 size_t nInitialSize ///< Initial set size; if 0 - use default initial size \ref c_nDefaultInitialSize
2290 , unsigned int nProbesetSize ///< probe set size, positive integer
2291 , unsigned int nProbesetThreshold ///< probe set threshold, <tt>nProbesetThreshold < nProbesetSize</tt>. If 0, nProbesetThreshold = nProbesetSize - 1
2292 , hash_tuple_type const& h ///< hash functor tuple of type <tt>std::tuple<H1, H2, ... Hn></tt> where <tt> n == \ref c_nArity </tt>
2294 : m_nProbesetSize( calc_probeset_size(nProbesetSize) )
2295 , m_nProbesetThreshold( nProbesetThreshold ? nProbesetThreshold : m_nProbesetSize - 1)
2297 , m_MutexPolicy( cds::beans::ceil2(nInitialSize ? nInitialSize : c_nDefaultInitialSize ))
2299 check_common_constraints();
2300 check_probeset_properties();
2302 allocate_bucket_tables( nInitialSize ? cds::beans::ceil2( nInitialSize ) : c_nDefaultInitialSize );
2305 /// Constructs the set object with given hash functor tuple (move semantics)
2307 The probe set size and threshold are set as default, see CuckooSet()
2310 hash_tuple_type&& h ///< hash functor tuple of type <tt>std::tuple<H1, H2, ... Hn></tt> where <tt> n == \ref c_nArity </tt>
2312 : m_nProbesetSize( calc_probeset_size(0) )
2313 , m_nProbesetThreshold( m_nProbesetSize / 2 )
2314 , m_Hash( std::forward<hash_tuple_type>(h) )
2315 , m_MutexPolicy( c_nDefaultInitialSize )
2317 check_common_constraints();
2318 check_probeset_properties();
2320 allocate_bucket_tables( c_nDefaultInitialSize );
2323 /// Constructs the set object with given probe set properties and hash functor tuple (move semantics)
2325 If probe set type is <tt> cuckoo::vector<Capacity> </tt> vector
2326 then \p nProbesetSize should be equal to vector's \p Capacity.
2329 size_t nInitialSize ///< Initial set size; if 0 - use default initial size \ref c_nDefaultInitialSize
2330 , unsigned int nProbesetSize ///< probe set size, positive integer
2331 , unsigned int nProbesetThreshold ///< probe set threshold, <tt>nProbesetThreshold < nProbesetSize</tt>. If 0, nProbesetThreshold = nProbesetSize - 1
2332 , hash_tuple_type&& h ///< hash functor tuple of type <tt>std::tuple<H1, H2, ... Hn></tt> where <tt> n == \ref c_nArity </tt>
2334 : m_nProbesetSize( calc_probeset_size(nProbesetSize) )
2335 , m_nProbesetThreshold( nProbesetThreshold ? nProbesetThreshold : m_nProbesetSize - 1)
2336 , m_Hash( std::forward<hash_tuple_type>(h) )
2337 , m_MutexPolicy( cds::beans::ceil2(nInitialSize ? nInitialSize : c_nDefaultInitialSize ))
2339 check_common_constraints();
2340 check_probeset_properties();
2342 allocate_bucket_tables( nInitialSize ? cds::beans::ceil2( nInitialSize ) : c_nDefaultInitialSize );
2348 free_bucket_tables();
2352 /// Inserts new node
2354 The function inserts \p val in the set if it does not contain
2355 an item with key equal to \p val.
2357 Returns \p true if \p val is placed into the set, \p false otherwise.
2359 bool insert( value_type& val )
2361 return insert( val, []( value_type& ) {} );
2364 /// Inserts new node
2366 The function allows to split creating of new item into two part:
2367 - create item with key only
2368 - insert new item into the set
2369 - if inserting is success, calls \p f functor to initialize value-field of \p val.
2371 The functor signature is:
2373 void func( value_type& val );
2375 where \p val is the item inserted.
2377 The user-defined functor is called only if the inserting is success.
2379 template <typename Func>
2380 bool insert( value_type& val, Func f )
2383 position arrPos[ c_nArity ];
2384 unsigned int nGoalTable;
2386 hashing( arrHash, val );
2387 node_type * pNode = node_traits::to_node_ptr( val );
2388 store_hash( pNode, arrHash );
2392 scoped_cell_lock guard( m_MutexPolicy, arrHash );
2394 if ( contains( arrPos, arrHash, val, key_predicate() ) != c_nUndefTable ) {
2395 m_Stat.onInsertFailed();
2399 for ( unsigned int i = 0; i < c_nArity; ++i ) {
2400 bucket_entry& refBucket = bucket( i, arrHash[i] );
2401 if ( refBucket.size() < m_nProbesetThreshold ) {
2402 refBucket.insert_after( arrPos[i].itPrev, pNode );
2405 m_Stat.onInsertSuccess();
2410 for ( unsigned int i = 0; i < c_nArity; ++i ) {
2411 bucket_entry& refBucket = bucket( i, arrHash[i] );
2412 if ( refBucket.size() < m_nProbesetSize ) {
2413 refBucket.insert_after( arrPos[i].itPrev, pNode );
2417 assert( refBucket.size() > 1 );
2418 copy_hash( arrHash, *node_traits::to_value_ptr( *refBucket.begin()) );
2424 m_Stat.onInsertResize();
2429 m_Stat.onInsertRelocate();
2430 if ( !relocate( nGoalTable, arrHash )) {
2431 m_Stat.onInsertRelocateFault();
2432 m_Stat.onInsertResize();
2436 m_Stat.onInsertSuccess();
2440 /// Updates the node
2442 The operation performs inserting or changing data with lock-free manner.
2444 If the item \p val is not found in the set, then \p val is inserted into the set
2445 iff \p bAllowInsert is \p true.
2446 Otherwise, the functor \p func is called with item found.
2447 The functor \p func signature is:
2449 void func( bool bNew, value_type& item, value_type& val );
2452 - \p bNew - \p true if the item has been inserted, \p false otherwise
2453 - \p item - item of the set
2454 - \p val - argument \p val passed into the \p %update() function
2455 If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
2456 refer to the same thing.
2458 The functor may change non-key fields of the \p item.
2460 Returns std::pair<bool, bool> where \p first is \p true if operation is successfull,
2461 i.e. the node has been inserted or updated,
2462 \p second is \p true if new item has been added or \p false if the item with \p key
2465 template <typename Func>
2466 std::pair<bool, bool> update( value_type& val, Func func, bool bAllowInsert = true )
2469 position arrPos[ c_nArity ];
2470 unsigned int nGoalTable;
2472 hashing( arrHash, val );
2473 node_type * pNode = node_traits::to_node_ptr( val );
2474 store_hash( pNode, arrHash );
2478 scoped_cell_lock guard( m_MutexPolicy, arrHash );
2480 unsigned int nTable = contains( arrPos, arrHash, val, key_predicate() );
2481 if ( nTable != c_nUndefTable ) {
2482 func( false, *node_traits::to_value_ptr( *arrPos[nTable].itFound ), val );
2483 m_Stat.onUpdateExist();
2484 return std::make_pair( true, false );
2487 if ( !bAllowInsert )
2488 return std::make_pair( false, false );
2490 //node_type * pNode = node_traits::to_node_ptr( val );
2491 //store_hash( pNode, arrHash );
2493 for ( unsigned int i = 0; i < c_nArity; ++i ) {
2494 bucket_entry& refBucket = bucket( i, arrHash[i] );
2495 if ( refBucket.size() < m_nProbesetThreshold ) {
2496 refBucket.insert_after( arrPos[i].itPrev, pNode );
2497 func( true, val, val );
2499 m_Stat.onUpdateSuccess();
2500 return std::make_pair( true, true );
2504 for ( unsigned int i = 0; i < c_nArity; ++i ) {
2505 bucket_entry& refBucket = bucket( i, arrHash[i] );
2506 if ( refBucket.size() < m_nProbesetSize ) {
2507 refBucket.insert_after( arrPos[i].itPrev, pNode );
2508 func( true, val, val );
2511 assert( refBucket.size() > 1 );
2512 copy_hash( arrHash, *node_traits::to_value_ptr( *refBucket.begin()) );
2518 m_Stat.onUpdateResize();
2523 m_Stat.onUpdateRelocate();
2524 if ( !relocate( nGoalTable, arrHash )) {
2525 m_Stat.onUpdateRelocateFault();
2526 m_Stat.onUpdateResize();
2530 m_Stat.onUpdateSuccess();
2531 return std::make_pair( true, true );
2534 // Deprecated, use update()
2535 template <typename Func>
2536 std::pair<bool, bool> ensure( value_type& val, Func func )
2538 return update( val, func, true );
2542 /// Unlink the item \p val from the set
2544 The function searches the item \p val in the set and unlink it
2545 if it is found and is equal to \p val (here, the equality means that
2546 \p val belongs to the set: if \p item is an item found then
2547 unlink is successful iif <tt>&val == &item</tt>)
2549 The function returns \p true if success and \p false otherwise.
2551 bool unlink( value_type& val )
2554 hashing( arrHash, val );
2555 position arrPos[ c_nArity ];
2558 scoped_cell_lock guard( m_MutexPolicy, arrHash );
2560 unsigned int nTable = contains( arrPos, arrHash, val, key_predicate() );
2561 if ( nTable != c_nUndefTable && node_traits::to_value_ptr(*arrPos[nTable].itFound) == &val ) {
2562 bucket( nTable, arrHash[nTable]).remove( arrPos[nTable].itPrev, arrPos[nTable].itFound );
2564 m_Stat.onUnlinkSuccess();
2569 m_Stat.onUnlinkFailed();
2573 /// Deletes the item from the set
2574 /** \anchor cds_intrusive_CuckooSet_erase
2575 The function searches an item with key equal to \p val in the set,
2576 unlinks it from the set, and returns a pointer to unlinked item.
2578 If the item with key equal to \p val is not found the function return \p nullptr.
2580 Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
2582 template <typename Q>
2583 value_type * erase( Q const& val )
2585 return erase( val, [](value_type const&) {} );
2588 /// Deletes the item from the set using \p pred predicate for searching
2590 The function is an analog of \ref cds_intrusive_CuckooSet_erase "erase(Q const&)"
2591 but \p pred is used for key comparing.
2592 If cuckoo set is ordered, then \p Predicate should have the interface and semantics like \p std::less.
2593 If cuckoo set is unordered, then \p Predicate should have the interface and semantics like \p std::equal_to.
2594 \p Predicate must imply the same element order as the comparator used for building the set.
2596 template <typename Q, typename Predicate>
2597 value_type * erase_with( Q const& val, Predicate pred )
2600 return erase_( val, typename predicate_wrapper<Predicate>::type(), [](value_type const&) {} );
2603 /// Delete the item from the set
2604 /** \anchor cds_intrusive_CuckooSet_erase_func
2605 The function searches an item with key equal to \p val in the set,
2606 call \p f functor with item found, unlinks it from the set, and returns a pointer to unlinked item.
2608 The \p Func interface is
2611 void operator()( value_type const& item );
2615 If the item with key equal to \p val is not found the function return \p nullptr.
2617 Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
2619 template <typename Q, typename Func>
2620 value_type * erase( Q const& val, Func f )
2622 return erase_( val, key_predicate(), f );
2625 /// Deletes the item from the set using \p pred predicate for searching
2627 The function is an analog of \ref cds_intrusive_CuckooSet_erase_func "erase(Q const&, Func)"
2628 but \p pred is used for key comparing.
2629 If you use ordered cuckoo set, then \p Predicate should have the interface and semantics like \p std::less.
2630 If you use unordered cuckoo set, then \p Predicate should have the interface and semantics like \p std::equal_to.
2631 \p Predicate must imply the same element order as the comparator used for building the set.
2633 template <typename Q, typename Predicate, typename Func>
2634 value_type * erase_with( Q const& val, Predicate pred, Func f )
2637 return erase_( val, typename predicate_wrapper<Predicate>::type(), f );
2640 /// Find the key \p val
2641 /** \anchor cds_intrusive_CuckooSet_find_func
2642 The function searches the item with key equal to \p val and calls the functor \p f for item found.
2643 The interface of \p Func functor is:
2646 void operator()( value_type& item, Q& val );
2649 where \p item is the item found, \p val is the <tt>find</tt> function argument.
2651 The functor may change non-key fields of \p item.
2653 The \p val argument is non-const since it can be used as \p f functor destination i.e., the functor
2654 may modify both arguments.
2656 Note the hash functor specified for class \p Traits template parameter
2657 should accept a parameter of type \p Q that can be not the same as \p value_type.
2659 The function returns \p true if \p val is found, \p false otherwise.
2661 template <typename Q, typename Func>
2662 bool find( Q& val, Func f )
2664 return find_( val, key_predicate(), f );
2667 template <typename Q, typename Func>
2668 bool find( Q const& val, Func f )
2670 return find_( val, key_predicate(), f );
2674 /// Find the key \p val using \p pred predicate for comparing
2676 The function is an analog of \ref cds_intrusive_CuckooSet_find_func "find(Q&, Func)"
2677 but \p pred is used for key comparison.
2678 If you use ordered cuckoo set, then \p Predicate should have the interface and semantics like \p std::less.
2679 If you use unordered cuckoo set, then \p Predicate should have the interface and semantics like \p std::equal_to.
2680 \p pred must imply the same element order as the comparator used for building the set.
2682 template <typename Q, typename Predicate, typename Func>
2683 bool find_with( Q& val, Predicate pred, Func f )
2686 return find_( val, typename predicate_wrapper<Predicate>::type(), f );
2689 template <typename Q, typename Predicate, typename Func>
2690 bool find_with( Q const& val, Predicate pred, Func f )
2693 return find_( val, typename predicate_wrapper<Predicate>::type(), f );
2697 /// Checks whether the set contains \p key
2699 The function searches the item with key equal to \p key
2700 and returns \p true if it is found, and \p false otherwise.
2702 template <typename Q>
2703 bool contains( Q const& key )
2705 return find( key, [](value_type&, Q const& ) {} );
2708 // Deprecated, use contains()
2709 template <typename Q>
2710 bool find( Q const& key )
2712 return contains( key );
2716 /// Checks whether the set contains \p key using \p pred predicate for searching
2718 The function is similar to <tt>contains( key )</tt> but \p pred is used for key comparing.
2719 \p Less functor has the interface like \p std::less.
2720 \p Less must imply the same element order as the comparator used for building the set.
2722 template <typename Q, typename Predicate>
2723 bool contains( Q const& key, Predicate pred )
2726 return find_with( key, typename predicate_wrapper<Predicate>::type(), [](value_type& , Q const& ) {} );
2729 // Deprecated,use contains()
2730 template <typename Q, typename Predicate>
2731 bool find_with( Q const& key, Predicate pred )
2733 return contains( key, pred );
2739 The function unlinks all items from the set.
2740 For any item \ref disposer is called
2744 clear_and_dispose( disposer() );
2747 /// Clears the set and calls \p disposer for each item
2749 The function unlinks all items from the set calling \p disposer for each item.
2750 \p Disposer functor interface is:
2753 void operator()( value_type * p );
2757 The \ref disposer specified in \p Traits traits is not called.
2759 template <typename Disposer>
2760 void clear_and_dispose( Disposer oDisposer )
2762 // locks entire array
2763 scoped_full_lock sl( m_MutexPolicy );
2765 for ( unsigned int i = 0; i < c_nArity; ++i ) {
2766 bucket_entry * pEntry = m_BucketTable[i];
2767 bucket_entry * pEnd = pEntry + m_nBucketMask + 1;
2768 for ( ; pEntry != pEnd ; ++pEntry ) {
2769 pEntry->clear( [&oDisposer]( node_type * pNode ){ oDisposer( node_traits::to_value_ptr( pNode )) ; } );
2772 m_ItemCounter.reset();
2775 /// Checks if the set is empty
2777 Emptiness is checked by item counting: if item count is zero then the set is empty.
2784 /// Returns item count in the set
2787 return m_ItemCounter;
2790 /// Returns the size of hash table
2792 The hash table size is non-constant and can be increased via resizing.
2794 size_t bucket_count() const
2796 return m_nBucketMask + 1;
2799 /// Returns lock array size
2800 size_t lock_count() const
2802 return m_MutexPolicy.lock_count();
2805 /// Returns const reference to internal statistics
2806 stat const& statistics() const
2811 /// Returns const reference to mutex policy internal statistics
2812 typename mutex_policy::statistics_type const& mutex_policy_statistics() const
2814 return m_MutexPolicy.statistics();
2817 }} // namespace cds::intrusive
2819 #endif // #ifndef CDSLIB_INTRUSIVE_CUCKOO_SET_H