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 // Probeset type declarations.
84 template <unsigned int Capacity>
87 static unsigned int const c_nCapacity = Capacity;
94 - \p ProbesetType - type of probeset. Can be \p cds::intrusive::cuckoo::list
95 or \p cds::intrusive::cuckoo::vector<Capacity>.
96 - \p StoreHashCount - constant that defines whether to store node hash values.
97 See cuckoo::store_hash option for explanation
98 - \p Tag - a \ref cds_intrusive_hook_tag "tag"
100 template <typename ProbesetType = cuckoo::list, unsigned int StoreHashCount = 0, typename Tag = opt::none>
102 #ifdef CDS_DOXYGEN_INVOKED
104 typedef ProbesetType probeset_type ; ///< Probeset type
105 typedef Tag tag ; ///< Tag
106 static unsigned int const hash_array_size = StoreHashCount ; ///< The size of hash array
112 template <typename Tag>
113 struct node< cuckoo::list, 0, Tag>
115 typedef list_probeset_class probeset_class;
116 typedef cuckoo::list probeset_type;
118 static unsigned int const hash_array_size = 0;
119 static unsigned int const probeset_size = 0;
123 CDS_CONSTEXPR node() CDS_NOEXCEPT
127 void store_hash( size_t * )
130 size_t * get_hash() const
132 // This node type does not store hash values!!!
143 template <unsigned int StoreHashCount, typename Tag>
144 struct node< cuckoo::list, StoreHashCount, Tag>
146 typedef list_probeset_class probeset_class;
147 typedef cuckoo::list probeset_type;
149 static unsigned int const hash_array_size = StoreHashCount;
150 static unsigned int const probeset_size = 0;
153 size_t m_arrHash[ hash_array_size ];
158 memset( m_arrHash, 0, sizeof(m_arrHash));
161 void store_hash( size_t * pHashes )
163 memcpy( m_arrHash, pHashes, hash_array_size );
166 size_t * get_hash() const
168 return const_cast<size_t *>( m_arrHash );
178 template <unsigned int VectorSize, typename Tag>
179 struct node< cuckoo::vector<VectorSize>, 0, Tag>
181 typedef vector_probeset_class probeset_class;
182 typedef cuckoo::vector<VectorSize> probeset_type;
184 static unsigned int const hash_array_size = 0;
185 static unsigned int const probeset_size = probeset_type::c_nCapacity;
190 void store_hash( size_t * )
193 size_t * get_hash() const
195 // This node type does not store hash values!!!
204 template <unsigned int VectorSize, unsigned int StoreHashCount, typename Tag>
205 struct node< cuckoo::vector<VectorSize>, StoreHashCount, Tag>
207 typedef vector_probeset_class probeset_class;
208 typedef cuckoo::vector<VectorSize> probeset_type;
210 static unsigned int const hash_array_size = StoreHashCount;
211 static unsigned int const probeset_size = probeset_type::c_nCapacity;
213 size_t m_arrHash[ hash_array_size ];
217 memset( m_arrHash, 0, sizeof(m_arrHash));
220 void store_hash( size_t * pHashes )
222 memcpy( m_arrHash, pHashes, hash_array_size );
225 size_t * get_hash() const
227 return const_cast<size_t *>( m_arrHash );
237 struct default_hook {
238 typedef cuckoo::list probeset_type;
239 static unsigned int const store_hash = 0;
240 typedef opt::none tag;
243 template < typename HookType, typename... Options>
246 typedef typename opt::make_options< default_hook, Options...>::type traits;
248 typedef typename traits::probeset_type probeset_type;
249 typedef typename traits::tag tag;
250 static unsigned int const store_hash = traits::store_hash;
252 typedef node<probeset_type, store_hash, tag> node_type;
254 typedef HookType hook_type;
261 - \p cuckoo::probeset_type - probeset type. Defaul is \p cuckoo::list
262 - \p cuckoo::store_hash - store hash values in the node or not. Default is 0 (no storing)
263 - \p opt::tag - a \ref cds_intrusive_hook_tag "tag"
265 template < typename... Options >
266 struct base_hook: public hook< opt::base_hook_tag, Options... >
271 \p MemberOffset defines offset in bytes of \ref node member into your structure.
272 Use \p offsetof macro to define \p MemberOffset
275 - \p cuckoo::probeset_type - probeset type. Defaul is \p cuckoo::list
276 - \p cuckoo::store_hash - store hash values in the node or not. Default is 0 (no storing)
277 - \p opt::tag - a \ref cds_intrusive_hook_tag "tag"
279 template < size_t MemberOffset, typename... Options >
280 struct member_hook: public hook< opt::member_hook_tag, Options... >
283 static const size_t c_nMemberOffset = MemberOffset;
289 \p NodeTraits defines type traits for node.
290 See \ref node_traits for \p NodeTraits interface description
293 - \p cuckoo::probeset_type - probeset type. Defaul is \p cuckoo::list
294 - \p cuckoo::store_hash - store hash values in the node or not. Default is 0 (no storing)
295 - \p opt::tag - a \ref cds_intrusive_hook_tag "tag"
297 template <typename NodeTraits, typename... Options >
298 struct traits_hook: public hook< opt::traits_hook_tag, Options... >
301 typedef NodeTraits node_traits;
305 /// Internal statistics for \ref striping mutex policy
306 struct striping_stat {
307 typedef cds::atomicity::event_counter counter_type; ///< Counter type
309 counter_type m_nCellLockCount ; ///< Count of obtaining cell lock
310 counter_type m_nCellTryLockCount ; ///< Count of cell \p try_lock attempts
311 counter_type m_nFullLockCount ; ///< Count of obtaining full lock
312 counter_type m_nResizeLockCount ; ///< Count of obtaining resize lock
313 counter_type m_nResizeCount ; ///< Count of resize event
316 void onCellLock() { ++m_nCellLockCount; }
317 void onCellTryLock() { ++m_nCellTryLockCount; }
318 void onFullLock() { ++m_nFullLockCount; }
319 void onResizeLock() { ++m_nResizeLockCount; }
320 void onResize() { ++m_nResizeCount; }
324 /// Dummy internal statistics for \ref striping mutex policy
325 struct empty_striping_stat {
327 void onCellLock() const {}
328 void onCellTryLock() const {}
329 void onFullLock() const {}
330 void onResizeLock() const {}
331 void onResize() const {}
335 /// Lock striping concurrent access policy
337 This is one of available opt::mutex_policy option type for CuckooSet
339 Lock striping is very simple technique.
340 The cuckoo set consists of the bucket tables and the array of locks.
341 There is single lock array for each bucket table, at least, the count of bucket table is 2.
342 Initially, the capacity of lock array and each bucket table is the same.
343 When set is resized, bucket table capacity will be doubled but lock array will not.
344 The lock \p i protects each bucket \p j, where <tt> j = i mod L </tt>,
345 where \p L - the size of lock array.
347 The policy contains an internal array of \p RecursiveLock locks.
350 - \p RecursiveLock - the type of recursive mutex. The default is \p std::recursive_mutex. The mutex type should be default-constructible.
351 Note that a recursive spin-lock is not suitable for lock striping for performance reason.
352 - \p Arity - unsigned int constant that specifies an arity. The arity is the count of hash functors, i.e., the
353 count of lock arrays. Default value is 2.
354 - \p Alloc - allocator type used for lock array memory allocation. Default is \p CDS_DEFAULT_ALLOCATOR.
355 - \p Stat - internal statistics type. Note that this template argument is automatically selected by \ref CuckooSet
356 class according to its \p opt::stat option.
359 class RecursiveLock = std::recursive_mutex,
360 unsigned int Arity = 2,
361 class Alloc = CDS_DEFAULT_ALLOCATOR,
362 class Stat = empty_striping_stat
367 typedef RecursiveLock lock_type ; ///< lock type
368 typedef Alloc allocator_type ; ///< allocator type
369 static unsigned int const c_nArity = Arity ; ///< the arity
370 typedef Stat statistics_type ; ///< Internal statistics type (\ref striping_stat or \ref empty_striping_stat)
373 typedef striping_stat real_stat;
374 typedef empty_striping_stat empty_stat;
376 template <typename Stat2>
377 struct rebind_statistics {
378 typedef striping<lock_type, c_nArity, allocator_type, Stat2> other;
382 typedef cds::sync::lock_array< lock_type, cds::sync::pow2_select_policy, allocator_type > lock_array_type ; ///< lock array type
386 class lock_array: public lock_array_type
390 lock_array(): lock_array_type( typename lock_array_type::select_cell_policy(2) ) {}
393 lock_array( size_t nCapacity ): lock_array_type( nCapacity, typename lock_array_type::select_cell_policy(nCapacity) ) {}
396 class scoped_lock: public std::unique_lock< lock_array_type >
398 typedef std::unique_lock< lock_array_type > base_class;
400 scoped_lock( lock_array& arrLock, size_t nHash ): base_class( arrLock, nHash ) {}
406 lock_array m_Locks[c_nArity] ; ///< array of lock_array_type
407 statistics_type m_Stat ; ///< internal statistics
412 class scoped_cell_lock {
413 lock_type * m_guard[c_nArity];
416 scoped_cell_lock( striping& policy, size_t const* arrHash )
418 for ( unsigned int i = 0; i < c_nArity; ++i ) {
419 m_guard[i] = &( policy.m_Locks[i].at( policy.m_Locks[i].lock( arrHash[i] )));
421 policy.m_Stat.onCellLock();
426 for ( unsigned int i = 0; i < c_nArity; ++i )
427 m_guard[i]->unlock();
431 class scoped_cell_trylock
433 typedef typename lock_array_type::lock_type lock_type;
435 lock_type * m_guard[c_nArity];
439 scoped_cell_trylock( striping& policy, size_t const* arrHash )
441 size_t nCell = policy.m_Locks[0].try_lock( arrHash[0] );
442 m_bLocked = nCell != lock_array_type::c_nUnspecifiedCell;
444 m_guard[0] = &(policy.m_Locks[0].at(nCell));
445 for ( unsigned int i = 1; i < c_nArity; ++i ) {
446 m_guard[i] = &( policy.m_Locks[i].at( policy.m_Locks[i].lock( arrHash[i] )) );
450 std::fill( m_guard, m_guard + c_nArity, nullptr );
452 policy.m_Stat.onCellTryLock();
454 ~scoped_cell_trylock()
457 for ( unsigned int i = 0; i < c_nArity; ++i )
458 m_guard[i]->unlock();
468 class scoped_full_lock {
469 std::unique_lock< lock_array_type > m_guard;
471 scoped_full_lock( striping& policy )
472 : m_guard( policy.m_Locks[0] )
474 policy.m_Stat.onFullLock();
477 /// Ctor for scoped_resize_lock - no statistics is incremented
478 scoped_full_lock( striping& policy, bool )
479 : m_guard( policy.m_Locks[0] )
483 class scoped_resize_lock: public scoped_full_lock {
485 scoped_resize_lock( striping& policy )
486 : scoped_full_lock( policy, false )
488 policy.m_Stat.onResizeLock();
496 size_t nLockCount ///< The size of lock array. Must be power of two.
499 // Trick: initialize the array of locks
500 for ( unsigned int i = 0; i < c_nArity; ++i ) {
501 lock_array * pArr = m_Locks + i;
502 pArr->lock_array::~lock_array();
503 new ( pArr ) lock_array( nLockCount );
507 /// Returns lock array size
509 Lock array size is unchanged during \p striping object lifetime
511 size_t lock_count() const
513 return m_Locks[0].size();
517 void resize( size_t )
523 /// Returns the arity of striping mutex policy
524 CDS_CONSTEXPR unsigned int arity() const CDS_NOEXCEPT
529 /// Returns internal statistics
530 statistics_type const& statistics() const
536 /// Internal statistics for \ref refinable mutex policy
537 struct refinable_stat {
538 typedef cds::atomicity::event_counter counter_type ; ///< Counter type
540 counter_type m_nCellLockCount ; ///< Count of obtaining cell lock
541 counter_type m_nCellLockWaitResizing ; ///< Count of loop iteration to wait for resizing
542 counter_type m_nCellLockArrayChanged ; ///< Count of event "Lock array has been changed when obtaining cell lock"
543 counter_type m_nCellLockFailed ; ///< Count of event "Cell lock failed because of the array is owned by other thread"
545 counter_type m_nSecondCellLockCount ; ///< Count of obtaining cell lock when another cell is already locked
546 counter_type m_nSecondCellLockFailed ; ///< Count of unsuccess obtaining cell lock when another cell is already locked
548 counter_type m_nFullLockCount ; ///< Count of obtaining full lock
549 counter_type m_nFullLockIter ; ///< Count of unsuccessfull iteration to obtain full lock
551 counter_type m_nResizeLockCount ; ///< Count of obtaining resize lock
552 counter_type m_nResizeLockIter ; ///< Count of unsuccessfull iteration to obtain resize lock
553 counter_type m_nResizeLockArrayChanged; ///< Count of event "Lock array has been changed when obtaining resize lock"
554 counter_type m_nResizeCount ; ///< Count of resize event
557 void onCellLock() { ++m_nCellLockCount; }
558 void onCellWaitResizing() { ++m_nCellLockWaitResizing; }
559 void onCellArrayChanged() { ++m_nCellLockArrayChanged; }
560 void onCellLockFailed() { ++m_nCellLockFailed; }
561 void onSecondCellLock() { ++m_nSecondCellLockCount; }
562 void onSecondCellLockFailed() { ++m_nSecondCellLockFailed; }
563 void onFullLock() { ++m_nFullLockCount; }
564 void onFullLockIter() { ++m_nFullLockIter; }
565 void onResizeLock() { ++m_nResizeLockCount; }
566 void onResizeLockIter() { ++m_nResizeLockIter; }
567 void onResizeLockArrayChanged() { ++m_nResizeLockArrayChanged; }
568 void onResize() { ++m_nResizeCount; }
572 /// Dummy internal statistics for \ref refinable mutex policy
573 struct empty_refinable_stat {
575 void onCellLock() const {}
576 void onCellWaitResizing() const {}
577 void onCellArrayChanged() const {}
578 void onCellLockFailed() const {}
579 void onSecondCellLock() const {}
580 void onSecondCellLockFailed() const {}
581 void onFullLock() const {}
582 void onFullLockIter() const {}
583 void onResizeLock() const {}
584 void onResizeLockIter() const {}
585 void onResizeLockArrayChanged() const {}
586 void onResize() const {}
590 /// Refinable concurrent access policy
592 This is one of available opt::mutex_policy option type for CuckooSet
594 Refining is like a striping technique (see cuckoo::striping)
595 but it allows growing the size of lock array when resizing the hash table.
596 So, the sizes of hash table and lock array are equal.
599 - \p RecursiveLock - the type of mutex. Reentrant (recursive) mutex is required.
600 The default is \p std::recursive_mutex. The mutex type should be default-constructible.
601 - \p Arity - unsigned int constant that specifies an arity. The arity is the count of hash functors, i.e., the
602 count of lock arrays. Default value is 2.
603 - \p BackOff - back-off strategy. Default is cds::backoff::yield
604 - \p Alloc - allocator type used for lock array memory allocation. Default is \p CDS_DEFAULT_ALLOCATOR.
605 - \p Stat - internal statistics type. Note that this template argument is automatically selected by \ref CuckooSet
606 class according to its \p opt::stat option.
609 class RecursiveLock = std::recursive_mutex,
610 unsigned int Arity = 2,
611 typename BackOff = cds::backoff::yield,
612 class Alloc = CDS_DEFAULT_ALLOCATOR,
613 class Stat = empty_refinable_stat
618 typedef RecursiveLock lock_type ; ///< lock type
619 typedef Alloc allocator_type ; ///< allocator type
620 typedef BackOff back_off ; ///< back-off strategy
621 typedef Stat statistics_type ; ///< internal statistics type
622 static unsigned int const c_nArity = Arity; ///< the arity
625 typedef refinable_stat real_stat;
626 typedef empty_refinable_stat empty_stat;
628 template <typename Stat2>
629 struct rebind_statistics {
630 typedef refinable< lock_type, c_nArity, back_off, allocator_type, Stat2> other;
636 typedef cds::sync::trivial_select_policy lock_selection_policy;
638 class lock_array_type
639 : public cds::sync::lock_array< lock_type, lock_selection_policy, allocator_type >
640 , public std::enable_shared_from_this< lock_array_type >
642 typedef cds::sync::lock_array< lock_type, lock_selection_policy, allocator_type > lock_array_base;
644 lock_array_type( size_t nCapacity )
645 : lock_array_base( nCapacity )
648 typedef std::shared_ptr< lock_array_type > lock_array_ptr;
649 typedef cds::details::Allocator< lock_array_type, allocator_type > lock_array_allocator;
651 typedef unsigned long long owner_t;
652 typedef cds::OS::ThreadId threadId_t;
654 typedef cds::sync::spin spinlock_type;
655 typedef std::unique_lock< spinlock_type > scoped_spinlock;
660 static owner_t const c_nOwnerMask = (((owner_t) 1) << (sizeof(owner_t) * 8 - 1)) - 1;
662 atomics::atomic< owner_t > m_Owner ; ///< owner mark (thread id + boolean flag)
663 atomics::atomic<size_t> m_nCapacity ; ///< lock array capacity
664 lock_array_ptr m_arrLocks[ c_nArity ] ; ///< Lock array. The capacity of array is specified in constructor.
665 spinlock_type m_access ; ///< access to m_arrLocks
666 statistics_type m_Stat ; ///< internal statistics
671 struct lock_array_disposer {
672 void operator()( lock_array_type * pArr )
674 lock_array_allocator().Delete( pArr );
678 lock_array_ptr create_lock_array( size_t nCapacity )
680 return lock_array_ptr( lock_array_allocator().New( nCapacity ), lock_array_disposer() );
683 void acquire( size_t const * arrHash, lock_array_ptr * pLockArr, lock_type ** parrLock )
685 owner_t me = (owner_t) cds::OS::get_current_thread_id();
692 scoped_spinlock sl(m_access);
693 for ( unsigned int i = 0; i < c_nArity; ++i )
694 pLockArr[i] = m_arrLocks[i];
697 // wait while resizing
699 who = m_Owner.load( atomics::memory_order_acquire );
700 if ( !( who & 1 ) || (who >> 1) == (me & c_nOwnerMask) )
703 m_Stat.onCellWaitResizing();
706 if ( pLockArr[0] != m_arrLocks[0] ) {
707 m_Stat.onCellArrayChanged();
711 size_t const nMask = pLockArr[0]->size() - 1;
712 assert( cds::beans::is_power2( nMask + 1 ));
714 for ( unsigned int i = 0; i < c_nArity; ++i ) {
715 parrLock[i] = &( pLockArr[i]->at( arrHash[i] & nMask ));
719 who = m_Owner.load( atomics::memory_order_acquire );
720 if ( ( !(who & 1) || (who >> 1) == (me & c_nOwnerMask) ) && m_arrLocks[0] == pLockArr[0] ) {
725 for ( unsigned int i = 0; i < c_nArity; ++i ) {
726 parrLock[i]->unlock();
729 m_Stat.onCellLockFailed();
732 // clears pLockArr can lead to calling dtor for each item of pLockArr[i] that may be a heavy-weighted operation
733 // (each pLockArr[i] is a shared pointer to array of a ton of mutexes)
734 // It is better to do this before the next loop iteration where we will use spin-locked assignment to pLockArr
735 // Destructing a lot of mutexes under spin-lock is a bad solution
736 for ( unsigned int i = 0; i < c_nArity; ++i )
741 bool try_second_acquire( size_t const * arrHash, lock_type ** parrLock )
743 // It is assumed that the current thread already has a lock
744 // and requires a second lock for other hash
746 size_t const nMask = m_nCapacity.load(atomics::memory_order_acquire) - 1;
747 size_t nCell = m_arrLocks[0]->try_lock( arrHash[0] & nMask);
748 if ( nCell == lock_array_type::c_nUnspecifiedCell ) {
749 m_Stat.onSecondCellLockFailed();
752 parrLock[0] = &(m_arrLocks[0]->at(nCell));
754 for ( unsigned int i = 1; i < c_nArity; ++i ) {
755 parrLock[i] = &( m_arrLocks[i]->at( m_arrLocks[i]->lock( arrHash[i] & nMask)) );
758 m_Stat.onSecondCellLock();
764 owner_t me = (owner_t) cds::OS::get_current_thread_id();
769 if ( m_Owner.compare_exchange_strong( ownNull, (me << 1) | 1, atomics::memory_order_acq_rel, atomics::memory_order_relaxed )) {
770 m_arrLocks[0]->lock_all();
776 m_Stat.onFullLockIter();
782 m_arrLocks[0]->unlock_all();
783 m_Owner.store( 0, atomics::memory_order_release );
786 void acquire_resize( lock_array_ptr * pOldLocks )
788 owner_t me = (owner_t) cds::OS::get_current_thread_id();
792 scoped_spinlock sl(m_access);
793 for ( unsigned int i = 0; i < c_nArity; ++i )
794 pOldLocks[i] = m_arrLocks[i];
799 if ( m_Owner.compare_exchange_strong( ownNull, (me << 1) | 1, atomics::memory_order_acq_rel, atomics::memory_order_relaxed )) {
800 if ( pOldLocks[0] != m_arrLocks[0] ) {
801 m_Owner.store( 0, atomics::memory_order_release );
802 m_Stat.onResizeLockArrayChanged();
805 pOldLocks[0]->lock_all();
806 m_Stat.onResizeLock();
811 m_Stat.onResizeLockIter();
813 // clears pOldLocks can lead to calling dtor for each item of pOldLocks[i] that may be a heavy-weighted operation
814 // (each pOldLocks[i] is a shared pointer to array of a ton of mutexes)
815 // It is better to do this before the next loop iteration where we will use spin-locked assignment to pOldLocks
816 // Destructing a lot of mutexes under spin-lock is a bad solution
817 for ( unsigned int i = 0; i < c_nArity; ++i )
818 pOldLocks[i].reset();
822 void release_resize( lock_array_ptr * pOldLocks )
824 m_Owner.store( 0, atomics::memory_order_release );
825 pOldLocks[0]->unlock_all();
831 class scoped_cell_lock {
832 lock_type * m_arrLock[ c_nArity ];
833 lock_array_ptr m_arrLockArr[ c_nArity ];
836 scoped_cell_lock( refinable& policy, size_t const* arrHash )
838 policy.acquire( arrHash, m_arrLockArr, m_arrLock );
843 for ( unsigned int i = 0; i < c_nArity; ++i )
844 m_arrLock[i]->unlock();
848 class scoped_cell_trylock {
849 lock_type * m_arrLock[ c_nArity ];
853 scoped_cell_trylock( refinable& policy, size_t const* arrHash )
855 m_bLocked = policy.try_second_acquire( arrHash, m_arrLock );
858 ~scoped_cell_trylock()
861 for ( unsigned int i = 0; i < c_nArity; ++i )
862 m_arrLock[i]->unlock();
872 class scoped_full_lock {
875 scoped_full_lock( refinable& policy )
878 policy.acquire_all();
882 m_policy.release_all();
886 class scoped_resize_lock
889 lock_array_ptr m_arrLocks[ c_nArity ];
891 scoped_resize_lock( refinable& policy )
894 policy.acquire_resize( m_arrLocks );
896 ~scoped_resize_lock()
898 m_policy.release_resize( m_arrLocks );
906 size_t nLockCount ///< The size of lock array. Must be power of two.
908 , m_nCapacity( nLockCount )
910 assert( cds::beans::is_power2( nLockCount ));
911 for ( unsigned int i = 0; i < c_nArity; ++i )
912 m_arrLocks[i] = create_lock_array( nLockCount );
916 void resize( size_t nCapacity )
918 lock_array_ptr pNew[ c_nArity ];
919 for ( unsigned int i = 0; i < c_nArity; ++i )
920 pNew[i] = create_lock_array( nCapacity );
923 // Assignment m_arrLocks[i] = pNew[i] may call heavy-weighted dtor for each item of m_arrLocks
924 // that is unacceptable under spin-lock
925 // So, we store copy of m_arrLocks in pOld
926 lock_array_ptr pOld[ c_nArity ];
927 for ( unsigned int i = 0; i < c_nArity; ++i )
928 pOld[i] = m_arrLocks[i];
930 // m_arrLocks assignment will not lead to calling dtor of each item of m_arrLocks
931 // since copy of m_arrLocks locates in pOld and assignment will not be too painful for spin-lock
935 scoped_spinlock sl(m_access);
936 for ( unsigned int i = 0; i < c_nArity; ++i )
937 m_arrLocks[i] = pNew[i];
939 m_nCapacity.store( nCapacity, atomics::memory_order_release );
945 /// Returns lock array size
947 Lock array size is not a constant for \p refinable policy and can be changed when the set is resized.
949 size_t lock_count() const
951 return m_nCapacity.load(atomics::memory_order_relaxed);
954 /// Returns the arity of \p refinable mutex policy
955 CDS_CONSTEXPR unsigned int arity() const CDS_NOEXCEPT
960 /// Returns internal statistics
961 statistics_type const& statistics() const
967 /// CuckooSet internal statistics
969 typedef cds::atomicity::event_counter counter_type ; ///< Counter type
971 counter_type m_nRelocateCallCount ; ///< Count of \p relocate function call
972 counter_type m_nRelocateRoundCount ; ///< Count of attempts to relocate items
973 counter_type m_nFalseRelocateCount ; ///< Count of unneeded attempts of \p relocate call
974 counter_type m_nSuccessRelocateCount ; ///< Count of successfull item relocating
975 counter_type m_nRelocateAboveThresholdCount; ///< Count of item relocating above probeset threshold
976 counter_type m_nFailedRelocateCount ; ///< Count of failed relocation attemp (when all probeset is full)
978 counter_type m_nResizeCallCount ; ///< Count of \p resize function call
979 counter_type m_nFalseResizeCount ; ///< Count of false \p resize function call (when other thread has been resized the set)
980 counter_type m_nResizeSuccessNodeMove; ///< Count of successfull node moving when resizing
981 counter_type m_nResizeRelocateCall ; ///< Count of \p relocate function call from \p resize function
983 counter_type m_nInsertSuccess ; ///< Count of successfull \p insert function call
984 counter_type m_nInsertFailed ; ///< Count of failed \p insert function call
985 counter_type m_nInsertResizeCount ; ///< Count of \p resize function call from \p insert
986 counter_type m_nInsertRelocateCount ; ///< Count of \p relocate function call from \p insert
987 counter_type m_nInsertRelocateFault ; ///< Count of failed \p relocate function call from \p insert
989 counter_type m_nEnsureExistCount ; ///< Count of call \p ensure function for existing node
990 counter_type m_nEnsureSuccessCount ; ///< Count of successfull \p insert function call for new node
991 counter_type m_nEnsureResizeCount ; ///< Count of \p resize function call from \p ensure
992 counter_type m_nEnsureRelocateCount ; ///< Count of \p relocate function call from \p ensure
993 counter_type m_nEnsureRelocateFault ; ///< Count of failed \p relocate function call from \p ensure
995 counter_type m_nUnlinkSuccess ; ///< Count of success \p unlink function call
996 counter_type m_nUnlinkFailed ; ///< Count of failed \p unlink function call
998 counter_type m_nEraseSuccess ; ///< Count of success \p erase function call
999 counter_type m_nEraseFailed ; ///< Count of failed \p erase function call
1001 counter_type m_nFindSuccess ; ///< Count of success \p find function call
1002 counter_type m_nFindFailed ; ///< Count of failed \p find function call
1004 counter_type m_nFindEqualSuccess ; ///< Count of success \p find_equal function call
1005 counter_type m_nFindEqualFailed ; ///< Count of failed \p find_equal function call
1007 counter_type m_nFindWithSuccess ; ///< Count of success \p find_with function call
1008 counter_type m_nFindWithFailed ; ///< Count of failed \p find_with function call
1011 void onRelocateCall() { ++m_nRelocateCallCount; }
1012 void onRelocateRound() { ++m_nRelocateRoundCount; }
1013 void onFalseRelocateRound() { ++m_nFalseRelocateCount; }
1014 void onSuccessRelocateRound(){ ++m_nSuccessRelocateCount; }
1015 void onRelocateAboveThresholdRound() { ++m_nRelocateAboveThresholdCount; }
1016 void onFailedRelocate() { ++m_nFailedRelocateCount; }
1018 void onResizeCall() { ++m_nResizeCallCount; }
1019 void onFalseResizeCall() { ++m_nFalseResizeCount; }
1020 void onResizeSuccessMove() { ++m_nResizeSuccessNodeMove; }
1021 void onResizeRelocateCall() { ++m_nResizeRelocateCall; }
1023 void onInsertSuccess() { ++m_nInsertSuccess; }
1024 void onInsertFailed() { ++m_nInsertFailed; }
1025 void onInsertResize() { ++m_nInsertResizeCount; }
1026 void onInsertRelocate() { ++m_nInsertRelocateCount; }
1027 void onInsertRelocateFault() { ++m_nInsertRelocateFault; }
1029 void onEnsureExist() { ++m_nEnsureExistCount; }
1030 void onEnsureSuccess() { ++m_nEnsureSuccessCount; }
1031 void onEnsureResize() { ++m_nEnsureResizeCount; }
1032 void onEnsureRelocate() { ++m_nEnsureRelocateCount; }
1033 void onEnsureRelocateFault() { ++m_nEnsureRelocateFault; }
1035 void onUnlinkSuccess() { ++m_nUnlinkSuccess; }
1036 void onUnlinkFailed() { ++m_nUnlinkFailed; }
1038 void onEraseSuccess() { ++m_nEraseSuccess; }
1039 void onEraseFailed() { ++m_nEraseFailed; }
1041 void onFindSuccess() { ++m_nFindSuccess; }
1042 void onFindFailed() { ++m_nFindFailed; }
1044 void onFindWithSuccess() { ++m_nFindWithSuccess; }
1045 void onFindWithFailed() { ++m_nFindWithFailed; }
1049 /// CuckooSet empty internal statistics
1052 void onRelocateCall() const {}
1053 void onRelocateRound() const {}
1054 void onFalseRelocateRound() const {}
1055 void onSuccessRelocateRound()const {}
1056 void onRelocateAboveThresholdRound() const {}
1057 void onFailedRelocate() const {}
1059 void onResizeCall() const {}
1060 void onFalseResizeCall() const {}
1061 void onResizeSuccessMove() const {}
1062 void onResizeRelocateCall() const {}
1064 void onInsertSuccess() const {}
1065 void onInsertFailed() const {}
1066 void onInsertResize() const {}
1067 void onInsertRelocate() const {}
1068 void onInsertRelocateFault() const {}
1070 void onEnsureExist() const {}
1071 void onEnsureSuccess() const {}
1072 void onEnsureResize() const {}
1073 void onEnsureRelocate() const {}
1074 void onEnsureRelocateFault() const {}
1076 void onUnlinkSuccess() const {}
1077 void onUnlinkFailed() const {}
1079 void onEraseSuccess() const {}
1080 void onEraseFailed() const {}
1082 void onFindSuccess() const {}
1083 void onFindFailed() const {}
1085 void onFindWithSuccess() const {}
1086 void onFindWithFailed() const {}
1090 /// Type traits for CuckooSet class
1095 Possible values are: cuckoo::base_hook, cuckoo::member_hook, cuckoo::traits_hook.
1097 typedef base_hook<> hook;
1099 /// Hash functors tuple
1101 This is mandatory type and has no predefined one.
1103 At least, two hash functors should be provided. All hash functor
1104 should be orthogonal (different): for each <tt> i,j: i != j => h[i](x) != h[j](x) </tt>.
1105 The hash functors are defined as <tt> std::tuple< H1, H2, ... Hn > </tt>:
1106 \@code cds::opt::hash< std::tuple< h1, h2 > > \@endcode
1107 The number of hash functors specifies the number \p k - the count of hash tables in cuckoo hashing.
1109 To specify hash tuple in traits you should use \p cds::opt::hash_tuple:
1111 struct my_traits: public cds::intrusive::cuckoo::traits {
1112 typedef cds::opt::hash_tuple< hash1, hash2 > hash;
1116 typedef cds::opt::none hash;
1118 /// Concurrent access policy
1120 Available opt::mutex_policy types:
1121 - \p cuckoo::striping - simple, but the lock array is not resizable
1122 - \p cuckoo::refinable - resizable lock array, but more complex access to set data.
1124 Default is \p cuckoo::striping.
1126 typedef cuckoo::striping<> mutex_policy;
1128 /// Key equality functor
1130 Default is <tt>std::equal_to<T></tt>
1132 typedef opt::none equal_to;
1134 /// Key comparing functor
1136 No default functor is provided. If the option is not specified, the \p less is used.
1138 typedef opt::none compare;
1140 /// specifies binary predicate used for key comparison.
1142 Default is \p std::less<T>.
1144 typedef opt::none less;
1148 The type for item counting feature.
1149 Default is \p cds::atomicity::item_counter
1151 Only atomic item counter type is allowed.
1153 typedef atomicity::item_counter item_counter;
1157 The allocator type for allocating bucket tables.
1159 typedef CDS_DEFAULT_ALLOCATOR allocator;
1163 The disposer functor is used in \p CuckooSet::clear() member function
1166 typedef intrusive::opt::v::empty_disposer disposer;
1168 /// Internal statistics. Available statistics: \p cuckoo::stat, \p cuckoo::empty_stat
1169 typedef empty_stat stat;
1172 /// Metafunction converting option list to \p CuckooSet traits
1174 Template argument list \p Options... are:
1175 - \p intrusive::opt::hook - hook used. Possible values are: \p cuckoo::base_hook, \p cuckoo::member_hook,
1176 \p cuckoo::traits_hook.
1177 If the option is not specified, <tt>%cuckoo::base_hook<></tt> is used.
1178 - \p opt::hash - hash functor tuple, mandatory option. At least, two hash functors should be provided. All hash functor
1179 should be orthogonal (different): for each <tt> i,j: i != j => h[i](x) != h[j](x) </tt>.
1180 The hash functors are passed as <tt> std::tuple< H1, H2, ... Hn > </tt>. The number of hash functors specifies
1181 the number \p k - the count of hash tables in cuckoo hashing.
1182 - \p opt::mutex_policy - concurrent access policy.
1183 Available policies: \p cuckoo::striping, \p cuckoo::refinable.
1184 Default is \p %cuckoo::striping.
1185 - \p opt::equal_to - key equality functor like \p std::equal_to.
1186 If this functor is defined then the probe-set will be unordered.
1187 If \p %opt::compare or \p %opt::less option is specified too, then the probe-set will be ordered
1188 and \p %opt::equal_to will be ignored.
1189 - \p opt::compare - key comparison functor. No default functor is provided.
1190 If the option is not specified, the \p %opt::less is used.
1191 If \p %opt::compare or \p %opt::less option is specified, then the probe-set will be ordered.
1192 - \p opt::less - specifies binary predicate used for key comparison. Default is \p std::less<T>.
1193 If \p %opt::compare or \p %opt::less option is specified, then the probe-set will be ordered.
1194 - \p opt::item_counter - the type of item counting feature. Default is \p atomicity::item_counter
1195 The item counter should be atomic.
1196 - \p opt::allocator - the allocator type using for allocating bucket tables.
1197 Default is \ref CDS_DEFAULT_ALLOCATOR
1198 - \p intrusive::opt::disposer - the disposer type used in \p clear() member function for
1199 freeing nodes. Default is \p intrusive::opt::v::empty_disposer
1200 - \p opt::stat - internal statistics. Possibly types: \p cuckoo::stat, \p cuckoo::empty_stat.
1201 Default is \p %cuckoo::empty_stat
1203 The probe set traits \p cuckoo::probeset_type and \p cuckoo::store_hash are taken from \p node type
1204 specified by \p opt::hook option.
1206 template <typename... Options>
1207 struct make_traits {
1208 typedef typename cds::opt::make_options<
1209 typename cds::opt::find_type_traits< cuckoo::traits, Options... >::type
1211 >::type type ; ///< Result of metafunction
1216 template <typename Node, typename Probeset>
1219 template <typename Node>
1220 class bucket_entry<Node, cuckoo::list>
1223 typedef Node node_type;
1224 typedef cuckoo::list_probeset_class probeset_class;
1225 typedef cuckoo::list probeset_type;
1235 friend class bucket_entry;
1241 iterator( node_type * p )
1244 iterator( iterator const& it)
1248 iterator& operator=( iterator const& it )
1254 iterator& operator=( node_type * p )
1260 node_type * operator->()
1264 node_type& operator*()
1266 assert( pNode != nullptr );
1271 iterator& operator ++()
1274 pNode = pNode->m_pNext;
1278 bool operator==(iterator const& it ) const
1280 return pNode == it.pNode;
1282 bool operator!=(iterator const& it ) const
1284 return !( *this == it );
1293 static_assert(( std::is_same<typename node_type::probeset_type, probeset_type>::value ), "Incompatible node type" );
1298 return iterator(pHead);
1305 void insert_after( iterator it, node_type * p )
1307 node_type * pPrev = it.pNode;
1309 p->m_pNext = pPrev->m_pNext;
1320 void remove( iterator itPrev, iterator itWhat )
1322 node_type * pPrev = itPrev.pNode;
1323 node_type * pWhat = itWhat.pNode;
1324 assert( (!pPrev && pWhat == pHead) || (pPrev && pPrev->m_pNext == pWhat) );
1327 pPrev->m_pNext = pWhat->m_pNext;
1329 assert( pWhat == pHead );
1330 pHead = pHead->m_pNext;
1339 for ( node_type * pNode = pHead; pNode; pNode = pNext ) {
1340 pNext = pNode->m_pNext;
1348 template <typename Disposer>
1349 void clear( Disposer disp )
1352 for ( node_type * pNode = pHead; pNode; pNode = pNext ) {
1353 pNext = pNode->m_pNext;
1362 unsigned int size() const
1368 template <typename Node, unsigned int Capacity>
1369 class bucket_entry<Node, cuckoo::vector<Capacity> >
1372 typedef Node node_type;
1373 typedef cuckoo::vector_probeset_class probeset_class;
1374 typedef cuckoo::vector<Capacity> probeset_type;
1376 static unsigned int const c_nCapacity = probeset_type::c_nCapacity;
1379 node_type * m_arrNode[c_nCapacity];
1380 unsigned int m_nSize;
1382 void shift_up( unsigned int nFrom )
1384 assert( m_nSize < c_nCapacity );
1387 if ( nFrom < m_nSize )
1388 std::copy_backward( m_arrNode + nFrom, m_arrNode + m_nSize, m_arrNode + m_nSize + 1 );
1390 // alternative: low-level byte copying
1391 //memmove( m_arrNode + nFrom + 1, m_arrNode + nFrom, (m_nSize - nFrom) * sizeof(m_arrNode[0]) );
1394 void shift_down( node_type ** pFrom )
1396 assert( m_arrNode <= pFrom && pFrom < m_arrNode + m_nSize);
1398 std::copy( pFrom + 1, m_arrNode + m_nSize, pFrom );
1400 // alternative: low-level byte copying
1401 //memmove( pFrom + 1, pFrom, (m_nSize - nFrom - 1) * sizeof(m_arrNode[0]));
1407 friend class bucket_entry;
1413 iterator( node_type ** p )
1416 iterator( iterator const& it)
1420 iterator& operator=( iterator const& it )
1426 node_type * operator->()
1428 assert( pArr != nullptr );
1431 node_type& operator*()
1433 assert( pArr != nullptr );
1434 assert( *pArr != nullptr );
1439 iterator& operator ++()
1445 bool operator==(iterator const& it ) const
1447 return pArr == it.pArr;
1449 bool operator!=(iterator const& it ) const
1451 return !( *this == it );
1459 memset( m_arrNode, 0, sizeof(m_arrNode));
1460 static_assert(( std::is_same<typename node_type::probeset_type, probeset_type>::value ), "Incompatible node type" );
1465 return iterator(m_arrNode);
1469 return iterator(m_arrNode + size());
1472 void insert_after( iterator it, node_type * p )
1474 assert( m_nSize < c_nCapacity );
1475 assert( !it.pArr || (m_arrNode <= it.pArr && it.pArr <= m_arrNode + m_nSize));
1478 shift_up( (unsigned int)(it.pArr - m_arrNode) + 1 );
1488 void remove( iterator /*itPrev*/, iterator itWhat )
1491 shift_down( itWhat.pArr );
1500 template <typename Disposer>
1501 void clear( Disposer disp )
1503 for ( unsigned int i = 0; i < m_nSize; ++i ) {
1504 disp( m_arrNode[i] );
1509 unsigned int size() const
1515 template <typename Node, unsigned int ArraySize>
1517 static void store( Node * pNode, size_t * pHashes )
1519 memcpy( pNode->m_arrHash, pHashes, sizeof(size_t) * ArraySize );
1521 static bool equal_to( Node& node, unsigned int nTable, size_t nHash )
1523 return node.m_arrHash[nTable] == nHash;
1526 template <typename Node>
1527 struct hash_ops<Node, 0>
1529 static void store( Node * /*pNode*/, size_t * /*pHashes*/ )
1531 static bool equal_to( Node& /*node*/, unsigned int /*nTable*/, size_t /*nHash*/ )
1537 template <typename NodeTraits, bool Ordered>
1540 template <typename NodeTraits>
1541 struct contains<NodeTraits, true>
1543 template <typename BucketEntry, typename Position, typename Q, typename Compare>
1544 static bool find( BucketEntry& probeset, Position& pos, unsigned int /*nTable*/, size_t /*nHash*/, Q const& val, Compare cmp )
1547 typedef typename BucketEntry::iterator bucket_iterator;
1549 bucket_iterator itPrev;
1551 for ( bucket_iterator it = probeset.begin(), itEnd = probeset.end(); it != itEnd; ++it ) {
1552 int cmpRes = cmp( *NodeTraits::to_value_ptr(*it), val );
1553 if ( cmpRes >= 0 ) {
1555 pos.itPrev = itPrev;
1562 pos.itPrev = itPrev;
1563 pos.itFound = probeset.end();
1568 template <typename NodeTraits>
1569 struct contains<NodeTraits, false>
1571 template <typename BucketEntry, typename Position, typename Q, typename EqualTo>
1572 static bool find( BucketEntry& probeset, Position& pos, unsigned int nTable, size_t nHash, Q const& val, EqualTo eq )
1574 // Unordered version
1575 typedef typename BucketEntry::iterator bucket_iterator;
1576 typedef typename BucketEntry::node_type node_type;
1578 bucket_iterator itPrev;
1580 for ( bucket_iterator it = probeset.begin(), itEnd = probeset.end(); it != itEnd; ++it ) {
1581 if ( hash_ops<node_type, node_type::hash_array_size>::equal_to( *it, nTable, nHash ) && eq( *NodeTraits::to_value_ptr(*it), val )) {
1583 pos.itPrev = itPrev;
1589 pos.itPrev = itPrev;
1590 pos.itFound = probeset.end();
1595 } // namespace details
1598 } // namespace cuckoo
1601 /** @ingroup cds_intrusive_map
1604 - [2007] M.Herlihy, N.Shavit, M.Tzafrir "Concurrent Cuckoo Hashing. Technical report"
1605 - [2008] Maurice Herlihy, Nir Shavit "The Art of Multiprocessor Programming"
1607 <b>About Cuckoo hashing</b>
1609 [From <i>"The Art of Multiprocessor Programming"</i>]
1610 Cuckoo hashing is a hashing algorithm in which a newly added item displaces any earlier item
1611 occupying the same slot. For brevity, a table is a k-entry array of items. For a hash set f size
1612 N = 2k we use a two-entry array of tables, and two independent hash functions,
1613 <tt> h0, h1: KeyRange -> 0,...,k-1</tt>
1614 mapping the set of possible keys to entries in he array. To test whether a value \p x is in the set,
1615 <tt>find(x)</tt> tests whether either <tt>table[0][h0(x)]</tt> or <tt>table[1][h1(x)]</tt> is
1616 equal to \p x. Similarly, <tt>erase(x)</tt>checks whether \p x is in either <tt>table[0][h0(x)]</tt>
1617 or <tt>table[1][h1(x)]</tt>, ad removes it if found.
1619 The <tt>insert(x)</tt> successively "kicks out" conflicting items until every key has a slot.
1620 To add \p x, the method swaps \p x with \p y, the current occupant of <tt>table[0][h0(x)]</tt>.
1621 If the prior value was \p nullptr, it is done. Otherwise, it swaps the newly nest-less value \p y
1622 for the current occupant of <tt>table[1][h1(y)]</tt> in the same way. As before, if the prior value
1623 was \p nullptr, it is done. Otherwise, the method continues swapping entries (alternating tables)
1624 until it finds an empty slot. We might not find an empty slot, either because the table is full,
1625 or because the sequence of displacement forms a cycle. We therefore need an upper limit on the
1626 number of successive displacements we are willing to undertake. When this limit is exceeded,
1627 we resize the hash table, choose new hash functions and start over.
1629 For concurrent cuckoo hashing, rather than organizing the set as a two-dimensional table of
1630 items, we use two-dimensional table of probe sets, where a probe set is a constant-sized set
1631 of items with the same hash code. Each probe set holds at most \p PROBE_SIZE items, but the algorithm
1632 tries to ensure that when the set is quiescent (i.e no method call in progress) each probe set
1633 holds no more than <tt>THRESHOLD < PROBE_SET</tt> items. While method calls are in-flight, a probe
1634 set may temporarily hold more than \p THRESHOLD but never more than \p PROBE_SET items.
1636 In current implementation, a probe set can be defined either as a (single-linked) list
1637 or as a fixed-sized vector, optionally ordered.
1639 In description above two-table cuckoo hashing (<tt>k = 2</tt>) has been considered.
1640 We can generalize this approach for <tt>k >= 2</tt> when we have \p k hash functions
1641 <tt>h[0], ... h[k-1]</tt> and \p k tables <tt>table[0], ... table[k-1]</tt>.
1643 The search in probe set is linear, the complexity is <tt> O(PROBE_SET) </tt>.
1644 The probe set may be ordered or not. Ordered probe set can be more efficient since
1645 the average search complexity is <tt>O(PROBE_SET/2)</tt>.
1646 However, the overhead of sorting can eliminate a gain of ordered search.
1648 The probe set is ordered if opt::compare or opt::less is specified in \p Traits template
1649 parameter. Otherwise, the probe set is unordered and \p Traits must contain
1650 opt::equal_to option.
1652 The cds::intrusive::cuckoo namespace contains \p %CuckooSet-related declarations.
1655 - \p T - the type stored in the set. The type must be based on cuckoo::node (for cuckoo::base_hook)
1656 or it must have a member of type %cuckoo::node (for cuckoo::member_hook),
1657 or it must be convertible to \p %cuckoo::node (for cuckoo::traits_hook)
1658 - \p Traits - type traits, default is cuckoo::traits. It is possible to declare option-based
1659 set with \p cuckoo::make_traits metafunction result as \p Traits template argument.
1663 You should incorporate \p cuckoo::node into your struct \p T and provide
1664 appropriate \p cuckoo::traits::hook in your \p Traits template parameters.
1665 Usually, for \p Traits you define a struct based on \p cuckoo::traits.
1667 Example for base hook and list-based probe-set:
1669 #include <cds/intrusive/cuckoo_set.h>
1671 // Data stored in cuckoo set
1672 // We use list as probe-set container and store hash values in the node
1673 // (since we use two hash functions we should store 2 hash values per node)
1674 struct my_data: public cds::intrusive::cuckoo::node< cds::intrusive::cuckoo::list, 2 >
1683 // Provide equal_to functor for my_data since we will use unordered probe-set
1684 struct my_data_equal_to {
1685 bool operator()( const my_data& d1, const my_data& d2 ) const
1687 return d1.strKey.compare( d2.strKey ) == 0;
1690 bool operator()( const my_data& d, const std::string& s ) const
1692 return d.strKey.compare(s) == 0;
1695 bool operator()( const std::string& s, const my_data& d ) const
1697 return s.compare( d.strKey ) == 0;
1701 // Provide two hash functor for my_data
1703 size_t operator()(std::string const& s) const
1705 return cds::opt::v::hash<std::string>( s );
1707 size_t operator()( my_data const& d ) const
1709 return (*this)( d.strKey );
1713 struct hash2: private hash1 {
1714 size_t operator()(std::string const& s) const
1716 size_t h = ~( hash1::operator()(s));
1717 return ~h + 0x9e3779b9 + (h << 6) + (h >> 2);
1719 size_t operator()( my_data const& d ) const
1721 return (*this)( d.strKey );
1725 // Declare type traits
1726 struct my_traits: public cds::intrusive::cuckoo::traits
1728 typedef cds::intrusive::cuckoo::base_hook<
1729 cds::intrusive::cuckoo::probeset_type< my_data::probeset_type >
1730 ,cds::intrusive::cuckoo::store_hash< my_data::hash_array_size >
1732 typedef my_data_equa_to equal_to;
1733 typedef cds::opt::hash_tuple< hash1, hash2 > hash;
1736 // Declare CuckooSet type
1737 typedef cds::intrusive::CuckooSet< my_data, my_traits > my_cuckoo_set;
1739 // Equal option-based declaration
1740 typedef cds::intrusive::CuckooSet< my_data,
1741 cds::intrusive::cuckoo::make_traits<
1742 cds::intrusive::opt::hook< cds::intrusive::cuckoo::base_hook<
1743 cds::intrusive::cuckoo::probeset_type< my_data::probeset_type >
1744 ,cds::intrusive::cuckoo::store_hash< my_data::hash_array_size >
1746 ,cds::opt::hash< std::tuple< hash1, hash2 > >
1747 ,cds::opt::equal_to< my_data_equal_to >
1752 If we provide \p compare function instead of \p equal_to for \p my_data
1753 we get as a result a cuckoo set with ordered probe set that may improve
1755 Example for base hook and ordered vector-based probe-set:
1758 #include <cds/intrusive/cuckoo_set.h>
1760 // Data stored in cuckoo set
1761 // We use a vector of capacity 4 as probe-set container and store hash values in the node
1762 // (since we use two hash functions we should store 2 hash values per node)
1763 struct my_data: public cds::intrusive::cuckoo::node< cds::intrusive::cuckoo::vector<4>, 2 >
1772 // Provide compare functor for my_data since we want to use ordered probe-set
1773 struct my_data_compare {
1774 int operator()( const my_data& d1, const my_data& d2 ) const
1776 return d1.strKey.compare( d2.strKey );
1779 int operator()( const my_data& d, const std::string& s ) const
1781 return d.strKey.compare(s);
1784 int operator()( const std::string& s, const my_data& d ) const
1786 return s.compare( d.strKey );
1790 // Provide two hash functor for my_data
1792 size_t operator()(std::string const& s) const
1794 return cds::opt::v::hash<std::string>( s );
1796 size_t operator()( my_data const& d ) const
1798 return (*this)( d.strKey );
1802 struct hash2: private hash1 {
1803 size_t operator()(std::string const& s) const
1805 size_t h = ~( hash1::operator()(s));
1806 return ~h + 0x9e3779b9 + (h << 6) + (h >> 2);
1808 size_t operator()( my_data const& d ) const
1810 return (*this)( d.strKey );
1814 // Declare type traits
1815 struct my_traits: public cds::intrusive::cuckoo::traits
1817 typedef cds::intrusive::cuckoo::base_hook<
1818 cds::intrusive::cuckoo::probeset_type< my_data::probeset_type >
1819 ,cds::intrusive::cuckoo::store_hash< my_data::hash_array_size >
1821 typedef my_data_compare compare;
1822 typedef cds::opt::hash_tuple< hash1, hash2 > hash;
1825 // Declare CuckooSet type
1826 typedef cds::intrusive::CuckooSet< my_data, my_traits > my_cuckoo_set;
1828 // Equal option-based declaration
1829 typedef cds::intrusive::CuckooSet< my_data,
1830 cds::intrusive::cuckoo::make_traits<
1831 cds::intrusive::opt::hook< cds::intrusive::cuckoo::base_hook<
1832 cds::intrusive::cuckoo::probeset_type< my_data::probeset_type >
1833 ,cds::intrusive::cuckoo::store_hash< my_data::hash_array_size >
1835 ,cds::opt::hash< std::tuple< hash1, hash2 > >
1836 ,cds::opt::compare< my_data_compare >
1842 template <typename T, typename Traits = cuckoo::traits>
1846 typedef T value_type; ///< The value type stored in the set
1847 typedef Traits traits; ///< Set traits
1849 typedef typename traits::hook hook; ///< hook type
1850 typedef typename hook::node_type node_type; ///< node type
1851 typedef typename get_node_traits< value_type, node_type, hook>::type node_traits; ///< node traits
1853 typedef typename traits::hash hash; ///< hash functor tuple wrapped for internal use
1854 typedef typename hash::hash_tuple_type hash_tuple_type; ///< Type of hash tuple
1856 typedef typename traits::stat stat; ///< internal statistics type
1858 typedef typename traits::mutex_policy original_mutex_policy; ///< Concurrent access policy, see \p cuckoo::traits::mutex_policy
1860 /// Actual mutex policy
1862 Actual mutex policy is built from mutex policy type provided by \p Traits template argument (see \p cuckoo::traits::mutex_policy)
1863 but mutex policy internal statistics is conformed with \p cukoo::traits::stat type provided by \p Traits:
1864 - if \p %cuckoo::traits::stat is \p cuckoo::empty_stat then mutex policy statistics is already empty
1865 - otherwise real mutex policy statistics is used
1867 typedef typename original_mutex_policy::template rebind_statistics<
1868 typename std::conditional<
1869 std::is_same< stat, cuckoo::empty_stat >::value
1870 ,typename original_mutex_policy::empty_stat
1871 ,typename original_mutex_policy::real_stat
1873 >::other mutex_policy;
1875 static bool const c_isSorted = !( std::is_same< typename traits::compare, opt::none >::value
1876 && std::is_same< typename traits::less, opt::none >::value ) ; ///< whether the probe set should be ordered
1877 static size_t const c_nArity = hash::size ; ///< the arity of cuckoo hashing: the number of hash functors provided; minimum 2.
1879 /// Key equality functor; used only for unordered probe-set
1880 typedef typename opt::details::make_equal_to< value_type, traits, !c_isSorted>::type key_equal_to;
1882 /// key comparing functor based on opt::compare and opt::less option setter. Used only for ordered probe set
1883 typedef typename opt::details::make_comparator< value_type, traits >::type key_comparator;
1886 typedef typename traits::allocator allocator;
1888 /// item counter type
1889 typedef typename traits::item_counter item_counter;
1892 typedef typename traits::disposer disposer;
1895 typedef cds::intrusive::cuckoo::implementation_tag implementation_tag;
1899 typedef typename node_type::probeset_class probeset_class;
1900 typedef typename node_type::probeset_type probeset_type;
1901 static unsigned int const c_nNodeHashArraySize = node_type::hash_array_size;
1903 typedef typename mutex_policy::scoped_cell_lock scoped_cell_lock;
1904 typedef typename mutex_policy::scoped_cell_trylock scoped_cell_trylock;
1905 typedef typename mutex_policy::scoped_full_lock scoped_full_lock;
1906 typedef typename mutex_policy::scoped_resize_lock scoped_resize_lock;
1908 typedef cuckoo::details::bucket_entry< node_type, probeset_type > bucket_entry;
1909 typedef typename bucket_entry::iterator bucket_iterator;
1910 typedef cds::details::Allocator< bucket_entry, allocator > bucket_table_allocator;
1912 typedef size_t hash_array[c_nArity] ; ///< hash array
1915 bucket_iterator itPrev;
1916 bucket_iterator itFound;
1919 typedef typename std::conditional< c_isSorted
1920 , cuckoo::details::contains< node_traits, true >
1921 , cuckoo::details::contains< node_traits, false >
1922 >::type contains_action;
1924 template <typename Predicate>
1925 struct predicate_wrapper {
1926 typedef typename std::conditional< c_isSorted, cds::opt::details::make_comparator_from_less<Predicate>, Predicate>::type type;
1929 typedef typename std::conditional< c_isSorted, key_comparator, key_equal_to >::type key_predicate;
1933 static unsigned int const c_nDefaultProbesetSize = 4; ///< default probeset size
1934 static size_t const c_nDefaultInitialSize = 16; ///< default initial size
1935 static unsigned int const c_nRelocateLimit = c_nArity * 2 - 1; ///< Count of attempts to relocate before giving up
1938 bucket_entry * m_BucketTable[ c_nArity ] ; ///< Bucket tables
1940 size_t m_nBucketMask ; ///< Hash bitmask; bucket table size minus 1.
1941 unsigned int const m_nProbesetSize ; ///< Probe set size
1942 unsigned int const m_nProbesetThreshold ; ///< Probe set threshold
1944 hash m_Hash ; ///< Hash functor tuple
1945 mutex_policy m_MutexPolicy ; ///< concurrent access policy
1946 item_counter m_ItemCounter ; ///< item counter
1947 mutable stat m_Stat ; ///< internal statistics
1951 static void check_common_constraints()
1953 static_assert( (c_nArity == mutex_policy::c_nArity), "The count of hash functors must be equal to mutex_policy arity" );
1956 void check_probeset_properties() const
1958 assert( m_nProbesetThreshold < m_nProbesetSize );
1960 // if probe set type is cuckoo::vector<N> then m_nProbesetSize == N
1961 assert( node_type::probeset_size == 0 || node_type::probeset_size == m_nProbesetSize );
1964 template <typename Q>
1965 void hashing( size_t * pHashes, Q const& v ) const
1967 m_Hash( pHashes, v );
1970 void copy_hash( size_t * pHashes, value_type const& v ) const
1972 if ( c_nNodeHashArraySize )
1973 memcpy( pHashes, node_traits::to_node_ptr( v )->get_hash(), sizeof(pHashes[0]) * c_nNodeHashArraySize );
1975 hashing( pHashes, v );
1978 bucket_entry& bucket( unsigned int nTable, size_t nHash )
1980 assert( nTable < c_nArity );
1981 return m_BucketTable[nTable][nHash & m_nBucketMask];
1984 static void store_hash( node_type * pNode, size_t * pHashes )
1986 cuckoo::details::hash_ops< node_type, c_nNodeHashArraySize >::store( pNode, pHashes );
1987 //memcpy( pNode->m_arrHash, pHashes, sizeof(size_t) * c_nArity );
1990 static bool equal_hash( node_type& node, unsigned int nTable, size_t nHash )
1992 return cuckoo::details::hash_ops< node_type, c_nNodeHashArraySize >::equal_to( node, nTable, nHash );
1995 void allocate_bucket_tables( size_t nSize )
1997 assert( cds::beans::is_power2( nSize ) );
1999 m_nBucketMask = nSize - 1;
2000 bucket_table_allocator alloc;
2001 for ( unsigned int i = 0; i < c_nArity; ++i )
2002 m_BucketTable[i] = alloc.NewArray( nSize );
2005 static void free_bucket_tables( bucket_entry ** pTable, size_t nCapacity )
2007 bucket_table_allocator alloc;
2008 for ( unsigned int i = 0; i < c_nArity; ++i ) {
2009 alloc.Delete( pTable[i], nCapacity );
2010 pTable[i] = nullptr;
2013 void free_bucket_tables()
2015 free_bucket_tables( m_BucketTable, m_nBucketMask + 1 );
2018 static unsigned int const c_nUndefTable = (unsigned int) -1;
2019 template <typename Q, typename Predicate >
2020 unsigned int contains( position * arrPos, size_t * arrHash, Q const& val, Predicate pred )
2022 // Buckets must be locked
2024 for ( unsigned int i = 0; i < c_nArity; ++i ) {
2025 bucket_entry& probeset = bucket( i, arrHash[i] );
2026 if ( contains_action::find( probeset, arrPos[i], i, arrHash[i], val, pred ))
2029 return c_nUndefTable;
2032 template <typename Q, typename Predicate, typename Func>
2033 value_type * erase_( Q const& val, Predicate pred, Func f )
2036 hashing( arrHash, val );
2037 position arrPos[ c_nArity ];
2040 scoped_cell_lock guard( m_MutexPolicy, arrHash );
2042 unsigned int nTable = contains( arrPos, arrHash, val, pred );
2043 if ( nTable != c_nUndefTable ) {
2044 node_type& node = *arrPos[nTable].itFound;
2045 f( *node_traits::to_value_ptr(node) );
2046 bucket( nTable, arrHash[nTable]).remove( arrPos[nTable].itPrev, arrPos[nTable].itFound );
2048 m_Stat.onEraseSuccess();
2049 return node_traits::to_value_ptr( node );
2053 m_Stat.onEraseFailed();
2057 template <typename Q, typename Predicate, typename Func>
2058 bool find_( Q& val, Predicate pred, Func f )
2061 position arrPos[ c_nArity ];
2062 hashing( arrHash, val );
2063 scoped_cell_lock sl( m_MutexPolicy, arrHash );
2065 unsigned int nTable = contains( arrPos, arrHash, val, pred );
2066 if ( nTable != c_nUndefTable ) {
2067 f( *node_traits::to_value_ptr( *arrPos[nTable].itFound ), val );
2068 m_Stat.onFindSuccess();
2072 m_Stat.onFindFailed();
2076 bool relocate( unsigned int nTable, size_t * arrGoalHash )
2078 // arrGoalHash contains hash values for relocating element
2079 // Relocating element is first one from bucket( nTable, arrGoalHash[nTable] ) probeset
2081 m_Stat.onRelocateCall();
2085 for ( unsigned int nRound = 0; nRound < c_nRelocateLimit; ++nRound ) {
2086 m_Stat.onRelocateRound();
2089 scoped_cell_lock guard( m_MutexPolicy, arrGoalHash );
2091 bucket_entry& refBucket = bucket( nTable, arrGoalHash[nTable] );
2092 if ( refBucket.size() < m_nProbesetThreshold ) {
2093 // probeset is not above the threshold
2094 m_Stat.onFalseRelocateRound();
2098 pVal = node_traits::to_value_ptr( *refBucket.begin() );
2099 copy_hash( arrHash, *pVal );
2101 scoped_cell_trylock guard2( m_MutexPolicy, arrHash );
2102 if ( !guard2.locked() )
2103 continue ; // try one more time
2105 refBucket.remove( typename bucket_entry::iterator(), refBucket.begin() );
2107 unsigned int i = (nTable + 1) % c_nArity;
2109 // try insert into free probeset
2110 while ( i != nTable ) {
2111 bucket_entry& bkt = bucket( i, arrHash[i] );
2112 if ( bkt.size() < m_nProbesetThreshold ) {
2114 contains_action::find( bkt, pos, i, arrHash[i], *pVal, key_predicate() ) ; // must return false!
2115 bkt.insert_after( pos.itPrev, node_traits::to_node_ptr( pVal ));
2116 m_Stat.onSuccessRelocateRound();
2119 i = ( i + 1 ) % c_nArity;
2122 // try insert into partial probeset
2123 i = (nTable + 1) % c_nArity;
2124 while ( i != nTable ) {
2125 bucket_entry& bkt = bucket( i, arrHash[i] );
2126 if ( bkt.size() < m_nProbesetSize ) {
2128 contains_action::find( bkt, pos, i, arrHash[i], *pVal, key_predicate() ) ; // must return false!
2129 bkt.insert_after( pos.itPrev, node_traits::to_node_ptr( pVal ));
2131 memcpy( arrGoalHash, arrHash, sizeof(arrHash));
2132 m_Stat.onRelocateAboveThresholdRound();
2133 goto next_iteration;
2135 i = (i + 1) % c_nArity;
2138 // all probeset is full, relocating fault
2139 refBucket.insert_after( typename bucket_entry::iterator(), node_traits::to_node_ptr( pVal ));
2140 m_Stat.onFailedRelocate();
2151 m_Stat.onResizeCall();
2153 size_t nOldCapacity = bucket_count();
2154 bucket_entry * pOldTable[ c_nArity ];
2156 scoped_resize_lock guard( m_MutexPolicy );
2158 if ( nOldCapacity != bucket_count() ) {
2159 m_Stat.onFalseResizeCall();
2163 size_t nCapacity = nOldCapacity * 2;
2165 m_MutexPolicy.resize( nCapacity );
2166 memcpy( pOldTable, m_BucketTable, sizeof(pOldTable));
2167 allocate_bucket_tables( nCapacity );
2169 typedef typename bucket_entry::iterator bucket_iterator;
2171 position arrPos[ c_nArity ];
2173 for ( unsigned int nTable = 0; nTable < c_nArity; ++nTable ) {
2174 bucket_entry * pTable = pOldTable[nTable];
2175 for ( size_t k = 0; k < nOldCapacity; ++k ) {
2176 bucket_iterator itNext;
2177 for ( bucket_iterator it = pTable[k].begin(), itEnd = pTable[k].end(); it != itEnd; it = itNext ) {
2181 value_type& val = *node_traits::to_value_ptr( *it );
2182 copy_hash( arrHash, val );
2183 contains( arrPos, arrHash, val, key_predicate() ) ; // must return c_nUndefTable
2185 for ( unsigned int i = 0; i < c_nArity; ++i ) {
2186 bucket_entry& refBucket = bucket( i, arrHash[i] );
2187 if ( refBucket.size() < m_nProbesetThreshold ) {
2188 refBucket.insert_after( arrPos[i].itPrev, &*it );
2189 m_Stat.onResizeSuccessMove();
2194 for ( unsigned int i = 0; i < c_nArity; ++i ) {
2195 bucket_entry& refBucket = bucket( i, arrHash[i] );
2196 if ( refBucket.size() < m_nProbesetSize ) {
2197 refBucket.insert_after( arrPos[i].itPrev, &*it );
2198 assert( refBucket.size() > 1 );
2199 copy_hash( arrHash, *node_traits::to_value_ptr( *refBucket.begin()) );
2200 m_Stat.onResizeRelocateCall();
2201 relocate( i, arrHash );
2210 free_bucket_tables( pOldTable, nOldCapacity );
2213 CDS_CONSTEXPR static unsigned int calc_probeset_size( unsigned int nProbesetSize ) CDS_NOEXCEPT
2215 return nProbesetSize
2217 : ( node_type::probeset_size ? node_type::probeset_size : c_nDefaultProbesetSize )
2223 /// Default constructor
2225 Initial size = \ref c_nDefaultInitialSize
2228 - \p c_nDefaultProbesetSize if \p probeset_type is \p cuckoo::list
2229 - \p Capacity if \p probeset_type is <tt> cuckoo::vector<Capacity> </tt>
2231 Probe set threshold = probe set size - 1
2234 : m_nProbesetSize( calc_probeset_size(0) )
2235 , m_nProbesetThreshold( m_nProbesetSize - 1 )
2236 , m_MutexPolicy( c_nDefaultInitialSize )
2238 check_common_constraints();
2239 check_probeset_properties();
2241 allocate_bucket_tables( c_nDefaultInitialSize );
2244 /// Constructs the set object with given probe set size and threshold
2246 If probe set type is <tt> cuckoo::vector<Capacity> </tt> vector
2247 then \p nProbesetSize should be equal to vector's \p Capacity.
2250 size_t nInitialSize ///< Initial set size; if 0 - use default initial size \ref c_nDefaultInitialSize
2251 , unsigned int nProbesetSize ///< probe set size
2252 , unsigned int nProbesetThreshold = 0 ///< probe set threshold, <tt>nProbesetThreshold < nProbesetSize</tt>. If 0, nProbesetThreshold = nProbesetSize - 1
2254 : m_nProbesetSize( calc_probeset_size(nProbesetSize) )
2255 , m_nProbesetThreshold( nProbesetThreshold ? nProbesetThreshold : m_nProbesetSize - 1 )
2256 , m_MutexPolicy( cds::beans::ceil2(nInitialSize ? nInitialSize : c_nDefaultInitialSize ))
2258 check_common_constraints();
2259 check_probeset_properties();
2261 allocate_bucket_tables( nInitialSize ? cds::beans::ceil2( nInitialSize ) : c_nDefaultInitialSize );
2264 /// Constructs the set object with given hash functor tuple
2266 The probe set size and threshold are set as default, see CuckooSet()
2269 hash_tuple_type const& h ///< hash functor tuple of type <tt>std::tuple<H1, H2, ... Hn></tt> where <tt> n == \ref c_nArity </tt>
2271 : m_nProbesetSize( calc_probeset_size(0) )
2272 , m_nProbesetThreshold( m_nProbesetSize -1 )
2274 , m_MutexPolicy( c_nDefaultInitialSize )
2276 check_common_constraints();
2277 check_probeset_properties();
2279 allocate_bucket_tables( c_nDefaultInitialSize );
2282 /// Constructs the set object with given probe set properties and hash functor tuple
2284 If probe set type is <tt> cuckoo::vector<Capacity> </tt> vector
2285 then \p nProbesetSize should be equal to vector's \p Capacity.
2288 size_t nInitialSize ///< Initial set size; if 0 - use default initial size \ref c_nDefaultInitialSize
2289 , unsigned int nProbesetSize ///< probe set size, positive integer
2290 , unsigned int nProbesetThreshold ///< probe set threshold, <tt>nProbesetThreshold < nProbesetSize</tt>. If 0, nProbesetThreshold = nProbesetSize - 1
2291 , hash_tuple_type const& h ///< hash functor tuple of type <tt>std::tuple<H1, H2, ... Hn></tt> where <tt> n == \ref c_nArity </tt>
2293 : m_nProbesetSize( calc_probeset_size(nProbesetSize) )
2294 , m_nProbesetThreshold( nProbesetThreshold ? nProbesetThreshold : m_nProbesetSize - 1)
2296 , m_MutexPolicy( cds::beans::ceil2(nInitialSize ? nInitialSize : c_nDefaultInitialSize ))
2298 check_common_constraints();
2299 check_probeset_properties();
2301 allocate_bucket_tables( nInitialSize ? cds::beans::ceil2( nInitialSize ) : c_nDefaultInitialSize );
2304 /// Constructs the set object with given hash functor tuple (move semantics)
2306 The probe set size and threshold are set as default, see CuckooSet()
2309 hash_tuple_type&& h ///< hash functor tuple of type <tt>std::tuple<H1, H2, ... Hn></tt> where <tt> n == \ref c_nArity </tt>
2311 : m_nProbesetSize( calc_probeset_size(0) )
2312 , m_nProbesetThreshold( m_nProbesetSize / 2 )
2313 , m_Hash( std::forward<hash_tuple_type>(h) )
2314 , m_MutexPolicy( c_nDefaultInitialSize )
2316 check_common_constraints();
2317 check_probeset_properties();
2319 allocate_bucket_tables( c_nDefaultInitialSize );
2322 /// Constructs the set object with given probe set properties and hash functor tuple (move semantics)
2324 If probe set type is <tt> cuckoo::vector<Capacity> </tt> vector
2325 then \p nProbesetSize should be equal to vector's \p Capacity.
2328 size_t nInitialSize ///< Initial set size; if 0 - use default initial size \ref c_nDefaultInitialSize
2329 , unsigned int nProbesetSize ///< probe set size, positive integer
2330 , unsigned int nProbesetThreshold ///< probe set threshold, <tt>nProbesetThreshold < nProbesetSize</tt>. If 0, nProbesetThreshold = nProbesetSize - 1
2331 , hash_tuple_type&& h ///< hash functor tuple of type <tt>std::tuple<H1, H2, ... Hn></tt> where <tt> n == \ref c_nArity </tt>
2333 : m_nProbesetSize( calc_probeset_size(nProbesetSize) )
2334 , m_nProbesetThreshold( nProbesetThreshold ? nProbesetThreshold : m_nProbesetSize - 1)
2335 , m_Hash( std::forward<hash_tuple_type>(h) )
2336 , m_MutexPolicy( cds::beans::ceil2(nInitialSize ? nInitialSize : c_nDefaultInitialSize ))
2338 check_common_constraints();
2339 check_probeset_properties();
2341 allocate_bucket_tables( nInitialSize ? cds::beans::ceil2( nInitialSize ) : c_nDefaultInitialSize );
2347 free_bucket_tables();
2351 /// Inserts new node
2353 The function inserts \p val in the set if it does not contain
2354 an item with key equal to \p val.
2356 Returns \p true if \p val is placed into the set, \p false otherwise.
2358 bool insert( value_type& val )
2360 return insert( val, []( value_type& ) {} );
2363 /// Inserts new node
2365 The function allows to split creating of new item into two part:
2366 - create item with key only
2367 - insert new item into the set
2368 - if inserting is success, calls \p f functor to initialize value-field of \p val.
2370 The functor signature is:
2372 void func( value_type& val );
2374 where \p val is the item inserted.
2376 The user-defined functor is called only if the inserting is success.
2378 template <typename Func>
2379 bool insert( value_type& val, Func f )
2382 position arrPos[ c_nArity ];
2383 unsigned int nGoalTable;
2385 hashing( arrHash, val );
2386 node_type * pNode = node_traits::to_node_ptr( val );
2387 store_hash( pNode, arrHash );
2391 scoped_cell_lock guard( m_MutexPolicy, arrHash );
2393 if ( contains( arrPos, arrHash, val, key_predicate() ) != c_nUndefTable ) {
2394 m_Stat.onInsertFailed();
2398 for ( unsigned int i = 0; i < c_nArity; ++i ) {
2399 bucket_entry& refBucket = bucket( i, arrHash[i] );
2400 if ( refBucket.size() < m_nProbesetThreshold ) {
2401 refBucket.insert_after( arrPos[i].itPrev, pNode );
2404 m_Stat.onInsertSuccess();
2409 for ( unsigned int i = 0; i < c_nArity; ++i ) {
2410 bucket_entry& refBucket = bucket( i, arrHash[i] );
2411 if ( refBucket.size() < m_nProbesetSize ) {
2412 refBucket.insert_after( arrPos[i].itPrev, pNode );
2416 assert( refBucket.size() > 1 );
2417 copy_hash( arrHash, *node_traits::to_value_ptr( *refBucket.begin()) );
2423 m_Stat.onInsertResize();
2428 m_Stat.onInsertRelocate();
2429 if ( !relocate( nGoalTable, arrHash )) {
2430 m_Stat.onInsertRelocateFault();
2431 m_Stat.onInsertResize();
2435 m_Stat.onInsertSuccess();
2439 /// Ensures that the \p val exists in the set
2441 The operation performs inserting or changing data with lock-free manner.
2443 If the item \p val not found in the set, then \p val is inserted into the set.
2444 Otherwise, the functor \p func is called with item found.
2445 The functor signature is:
2447 void func( bool bNew, value_type& item, value_type& val );
2450 - \p bNew - \p true if the item has been inserted, \p false otherwise
2451 - \p item - item of the set
2452 - \p val - argument \p val passed into the \p ensure function
2453 If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
2454 refers to the same thing.
2456 The functor may change non-key fields of the \p item.
2458 Returns <tt> std::pair<bool, bool> </tt> where \p first is \p true if operation is successful,
2459 \p second is \p true if new item has been added or \p false if the item with \p key
2460 already is in the set.
2462 template <typename Func>
2463 std::pair<bool, bool> ensure( value_type& val, Func func )
2466 position arrPos[ c_nArity ];
2467 unsigned int nGoalTable;
2469 hashing( arrHash, val );
2470 node_type * pNode = node_traits::to_node_ptr( val );
2471 store_hash( pNode, arrHash );
2475 scoped_cell_lock guard( m_MutexPolicy, arrHash );
2477 unsigned int nTable = contains( arrPos, arrHash, val, key_predicate() );
2478 if ( nTable != c_nUndefTable ) {
2479 func( false, *node_traits::to_value_ptr( *arrPos[nTable].itFound ), val );
2480 m_Stat.onEnsureExist();
2481 return std::make_pair( true, false );
2484 node_type * pNode = node_traits::to_node_ptr( val );
2485 store_hash( pNode, arrHash );
2487 for ( unsigned int i = 0; i < c_nArity; ++i ) {
2488 bucket_entry& refBucket = bucket( i, arrHash[i] );
2489 if ( refBucket.size() < m_nProbesetThreshold ) {
2490 refBucket.insert_after( arrPos[i].itPrev, pNode );
2491 func( true, val, val );
2493 m_Stat.onEnsureSuccess();
2494 return std::make_pair( true, true );
2498 for ( unsigned int i = 0; i < c_nArity; ++i ) {
2499 bucket_entry& refBucket = bucket( i, arrHash[i] );
2500 if ( refBucket.size() < m_nProbesetSize ) {
2501 refBucket.insert_after( arrPos[i].itPrev, pNode );
2502 func( true, val, val );
2505 assert( refBucket.size() > 1 );
2506 copy_hash( arrHash, *node_traits::to_value_ptr( *refBucket.begin()) );
2512 m_Stat.onEnsureResize();
2517 m_Stat.onEnsureRelocate();
2518 if ( !relocate( nGoalTable, arrHash )) {
2519 m_Stat.onEnsureRelocateFault();
2520 m_Stat.onEnsureResize();
2524 m_Stat.onEnsureSuccess();
2525 return std::make_pair( true, true );
2528 /// Unlink the item \p val from the set
2530 The function searches the item \p val in the set and unlink it
2531 if it is found and is equal to \p val (here, the equality means that
2532 \p val belongs to the set: if \p item is an item found then
2533 unlink is successful iif <tt>&val == &item</tt>)
2535 The function returns \p true if success and \p false otherwise.
2537 bool unlink( value_type& val )
2540 hashing( arrHash, val );
2541 position arrPos[ c_nArity ];
2544 scoped_cell_lock guard( m_MutexPolicy, arrHash );
2546 unsigned int nTable = contains( arrPos, arrHash, val, key_predicate() );
2547 if ( nTable != c_nUndefTable && node_traits::to_value_ptr(*arrPos[nTable].itFound) == &val ) {
2548 bucket( nTable, arrHash[nTable]).remove( arrPos[nTable].itPrev, arrPos[nTable].itFound );
2550 m_Stat.onUnlinkSuccess();
2555 m_Stat.onUnlinkFailed();
2559 /// Deletes the item from the set
2560 /** \anchor cds_intrusive_CuckooSet_erase
2561 The function searches an item with key equal to \p val in the set,
2562 unlinks it from the set, and returns a pointer to unlinked item.
2564 If the item with key equal to \p val is not found the function return \p nullptr.
2566 Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
2568 template <typename Q>
2569 value_type * erase( Q const& val )
2571 return erase( val, [](value_type const&) {} );
2574 /// Deletes the item from the set using \p pred predicate for searching
2576 The function is an analog of \ref cds_intrusive_CuckooSet_erase "erase(Q const&)"
2577 but \p pred is used for key comparing.
2578 If cuckoo set is ordered, then \p Predicate should have the interface and semantics like \p std::less.
2579 If cuckoo set is unordered, then \p Predicate should have the interface and semantics like \p std::equal_to.
2580 \p Predicate must imply the same element order as the comparator used for building the set.
2582 template <typename Q, typename Predicate>
2583 value_type * erase_with( Q const& val, Predicate pred )
2586 return erase_( val, typename predicate_wrapper<Predicate>::type(), [](value_type const&) {} );
2589 /// Delete the item from the set
2590 /** \anchor cds_intrusive_CuckooSet_erase_func
2591 The function searches an item with key equal to \p val in the set,
2592 call \p f functor with item found, unlinks it from the set, and returns a pointer to unlinked item.
2594 The \p Func interface is
2597 void operator()( value_type const& item );
2601 If the item with key equal to \p val is not found the function return \p nullptr.
2603 Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
2605 template <typename Q, typename Func>
2606 value_type * erase( Q const& val, Func f )
2608 return erase_( val, key_predicate(), f );
2611 /// Deletes the item from the set using \p pred predicate for searching
2613 The function is an analog of \ref cds_intrusive_CuckooSet_erase_func "erase(Q const&, Func)"
2614 but \p pred is used for key comparing.
2615 If you use ordered cuckoo set, then \p Predicate should have the interface and semantics like \p std::less.
2616 If you use unordered cuckoo set, then \p Predicate should have the interface and semantics like \p std::equal_to.
2617 \p Predicate must imply the same element order as the comparator used for building the set.
2619 template <typename Q, typename Predicate, typename Func>
2620 value_type * erase_with( Q const& val, Predicate pred, Func f )
2623 return erase_( val, typename predicate_wrapper<Predicate>::type(), f );
2626 /// Find the key \p val
2627 /** \anchor cds_intrusive_CuckooSet_find_func
2628 The function searches the item with key equal to \p val and calls the functor \p f for item found.
2629 The interface of \p Func functor is:
2632 void operator()( value_type& item, Q& val );
2635 where \p item is the item found, \p val is the <tt>find</tt> function argument.
2637 The functor may change non-key fields of \p item.
2639 The \p val argument is non-const since it can be used as \p f functor destination i.e., the functor
2640 may modify both arguments.
2642 Note the hash functor specified for class \p Traits template parameter
2643 should accept a parameter of type \p Q that can be not the same as \p value_type.
2645 The function returns \p true if \p val is found, \p false otherwise.
2647 template <typename Q, typename Func>
2648 bool find( Q& val, Func f )
2650 return find_( val, key_predicate(), f );
2653 /// Find the key \p val using \p pred predicate for comparing
2655 The function is an analog of \ref cds_intrusive_CuckooSet_find_func "find(Q&, Func)"
2656 but \p pred is used for key comparison.
2657 If you use ordered cuckoo set, then \p Predicate should have the interface and semantics like \p std::less.
2658 If you use unordered cuckoo set, then \p Predicate should have the interface and semantics like \p std::equal_to.
2659 \p pred must imply the same element order as the comparator used for building the set.
2661 template <typename Q, typename Predicate, typename Func>
2662 bool find_with( Q& val, Predicate pred, Func f )
2665 return find_( val, typename predicate_wrapper<Predicate>::type(), f );
2668 /// Find the key \p val
2669 /** \anchor cds_intrusive_CuckooSet_find_cfunc
2670 The function searches the item with key equal to \p val and calls the functor \p f for item found.
2671 The interface of \p Func functor is:
2674 void operator()( value_type& item, Q const& val );
2677 where \p item is the item found, \p val is the <tt>find</tt> function argument.
2679 The functor may change non-key fields of \p item.
2681 The \p val argument is non-const since it can be used as \p f functor destination i.e., the functor
2682 may modify both arguments.
2684 The function returns \p true if \p val is found, \p false otherwise.
2686 template <typename Q, typename Func>
2687 bool find( Q const& val, Func f )
2689 return find_( val, key_predicate(), f );
2692 /// Find the key \p val using \p pred predicate for comparing
2694 The function is an analog of \ref cds_intrusive_CuckooSet_find_cfunc "find(Q const&, Func)"
2695 but \p pred is used for key comparison.
2696 If you use ordered cuckoo set, then \p Predicate should have the interface and semantics like \p std::less.
2697 If you use unordered cuckoo set, then \p Predicate should have the interface and semantics like \p std::equal_to.
2698 \p pred must imply the same element order as the comparator used for building the set.
2700 template <typename Q, typename Predicate, typename Func>
2701 bool find_with( Q const& val, Predicate pred, Func f )
2704 return find_( val, typename predicate_wrapper<Predicate>::type(), f );
2707 /// Find the key \p val
2708 /** \anchor cds_intrusive_CuckooSet_find_val
2709 The function searches the item with key equal to \p val
2710 and returns \p true if it is found, and \p false otherwise.
2712 Note the hash functor specified for class \p Traits template parameter
2713 should accept a parameter of type \p Q that can be not the same as \p value_type.
2715 template <typename Q>
2716 bool find( Q const& val )
2718 return find( val, [](value_type&, Q const& ) {} );
2721 /// Find the key \p val using \p pred predicate for comparing
2723 The function is an analog of \ref cds_intrusive_CuckooSet_find_val "find(Q const&)"
2724 but \p pred is used for key comparison.
2725 If you use ordered cuckoo set, then \p Predicate should have the interface and semantics like \p std::less.
2726 If you use unordered cuckoo set, then \p Predicate should have the interface and semantics like \p std::equal_to.
2727 \p pred must imply the same element order as the comparator used for building the set.
2729 template <typename Q, typename Predicate>
2730 bool find_with( Q const& val, Predicate pred )
2733 return find_with( val, typename predicate_wrapper<Predicate>::type(), [](value_type& , Q const& ) {} );
2738 The function unlinks all items from the set.
2739 For any item \ref disposer is called
2743 clear_and_dispose( disposer() );
2746 /// Clears the set and calls \p disposer for each item
2748 The function unlinks all items from the set calling \p disposer for each item.
2749 \p Disposer functor interface is:
2752 void operator()( value_type * p );
2756 The \ref disposer specified in \p Traits traits is not called.
2758 template <typename Disposer>
2759 void clear_and_dispose( Disposer oDisposer )
2761 // locks entire array
2762 scoped_full_lock sl( m_MutexPolicy );
2764 for ( unsigned int i = 0; i < c_nArity; ++i ) {
2765 bucket_entry * pEntry = m_BucketTable[i];
2766 bucket_entry * pEnd = pEntry + m_nBucketMask + 1;
2767 for ( ; pEntry != pEnd ; ++pEntry ) {
2768 pEntry->clear( [&oDisposer]( node_type * pNode ){ oDisposer( node_traits::to_value_ptr( pNode )) ; } );
2771 m_ItemCounter.reset();
2774 /// Checks if the set is empty
2776 Emptiness is checked by item counting: if item count is zero then the set is empty.
2783 /// Returns item count in the set
2786 return m_ItemCounter;
2789 /// Returns the size of hash table
2791 The hash table size is non-constant and can be increased via resizing.
2793 size_t bucket_count() const
2795 return m_nBucketMask + 1;
2798 /// Returns lock array size
2799 size_t lock_count() const
2801 return m_MutexPolicy.lock_count();
2804 /// Returns const reference to internal statistics
2805 stat const& statistics() const
2810 /// Returns const reference to mutex policy internal statistics
2811 typename mutex_policy::statistics_type const& mutex_policy_statistics() const
2813 return m_MutexPolicy.statistics();
2816 }} // namespace cds::intrusive
2818 #endif // #ifndef CDSLIB_INTRUSIVE_CUCKOO_SET_H