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/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 /// Option to define probeset type
25 The option specifies probeset type for the CuckooSet.
27 - \p cds::intrusive::cuckoo::list - the probeset is a single-linked list.
28 The node contains pointer to next node in probeset.
29 - \p cds::intrusive::cuckoo::vector<Capacity> - the probeset is a vector
30 with constant-size \p Capacity where \p Capacity is an <tt>unsigned int</tt> constant.
31 The node does not contain any auxiliary data.
33 template <typename Type>
37 template <typename Base>
38 struct pack: public Base {
39 typedef Type probeset_type;
44 /// Option specifying whether to store hash values in the node
46 This option reserves additional space in the hook to store the hash value of the object once it's introduced in the container.
47 When this option is used, the unordered container will store the calculated hash value in the hook and rehashing operations won't need
48 to recalculate the hash of the value. This option will improve the performance of unordered containers
49 when rehashing is frequent or hashing the value is a slow operation
51 The \p Count template parameter defines the size of hash array. Remember that cuckoo hashing implies at least two
54 Possible values of \p Count:
55 - 0 - no hash storing in the node
56 - greater that 1 - store hash values.
58 Value 1 is deprecated.
60 template <unsigned int Count>
64 template <typename Base>
65 struct pack: public Base {
66 static unsigned int const store_hash = Count;
73 // Probeset type placeholders
74 struct list_probeset_class;
75 struct vector_probeset_class;
79 // Probeset type declarations.
81 template <unsigned int Capacity>
84 static unsigned int const c_nCapacity = Capacity;
91 - \p ProbesetType - type of probeset. Can be \p cds::intrusive::cuckoo::list
92 or \p cds::intrusive::cuckoo::vector<Capacity>.
93 - \p StoreHashCount - constant that defines whether to store node hash values.
94 See cuckoo::store_hash option for explanation
95 - \p Tag - a \ref cds_intrusive_hook_tag "tag"
97 template <typename ProbesetType = cuckoo::list, unsigned int StoreHashCount = 0, typename Tag = opt::none>
99 #ifdef CDS_DOXYGEN_INVOKED
101 typedef ProbesetType probeset_type ; ///< Probeset type
102 typedef Tag tag ; ///< Tag
103 static unsigned int const hash_array_size = StoreHashCount ; ///< The size of hash array
109 template <typename Tag>
110 struct node< cuckoo::list, 0, Tag>
112 typedef list_probeset_class probeset_class;
113 typedef cuckoo::list probeset_type;
115 static unsigned int const hash_array_size = 0;
116 static unsigned int const probeset_size = 0;
120 CDS_CONSTEXPR node() CDS_NOEXCEPT
124 void store_hash( size_t * )
127 size_t * get_hash() const
129 // This node type does not store hash values!!!
140 template <unsigned int StoreHashCount, typename Tag>
141 struct node< cuckoo::list, StoreHashCount, Tag>
143 typedef list_probeset_class probeset_class;
144 typedef cuckoo::list probeset_type;
146 static unsigned int const hash_array_size = StoreHashCount;
147 static unsigned int const probeset_size = 0;
150 size_t m_arrHash[ hash_array_size ];
155 memset( m_arrHash, 0, sizeof(m_arrHash));
158 void store_hash( size_t * pHashes )
160 memcpy( m_arrHash, pHashes, hash_array_size );
163 size_t * get_hash() const
165 return const_cast<size_t *>( m_arrHash );
175 template <unsigned int VectorSize, typename Tag>
176 struct node< cuckoo::vector<VectorSize>, 0, Tag>
178 typedef vector_probeset_class probeset_class;
179 typedef cuckoo::vector<VectorSize> probeset_type;
181 static unsigned int const hash_array_size = 0;
182 static unsigned int const probeset_size = probeset_type::c_nCapacity;
187 void store_hash( size_t * )
190 size_t * get_hash() const
192 // This node type does not store hash values!!!
201 template <unsigned int VectorSize, unsigned int StoreHashCount, typename Tag>
202 struct node< cuckoo::vector<VectorSize>, StoreHashCount, Tag>
204 typedef vector_probeset_class probeset_class;
205 typedef cuckoo::vector<VectorSize> probeset_type;
207 static unsigned int const hash_array_size = StoreHashCount;
208 static unsigned int const probeset_size = probeset_type::c_nCapacity;
210 size_t m_arrHash[ hash_array_size ];
214 memset( m_arrHash, 0, sizeof(m_arrHash));
217 void store_hash( size_t * pHashes )
219 memcpy( m_arrHash, pHashes, hash_array_size );
222 size_t * get_hash() const
224 return const_cast<size_t *>( m_arrHash );
234 struct default_hook {
235 typedef cuckoo::list probeset_type;
236 static unsigned int const store_hash = 0;
237 typedef opt::none tag;
240 template < typename HookType, typename... Options>
243 typedef typename opt::make_options< default_hook, Options...>::type traits;
245 typedef typename traits::probeset_type probeset_type;
246 typedef typename traits::tag tag;
247 static unsigned int const store_hash = traits::store_hash;
249 typedef node<probeset_type, store_hash, tag> node_type;
251 typedef HookType hook_type;
258 - \p cuckoo::probeset_type - probeset type. Defaul is \p cuckoo::list
259 - \p cuckoo::store_hash - store hash values in the node or not. Default is 0 (no storing)
260 - \p opt::tag - a \ref cds_intrusive_hook_tag "tag"
262 template < typename... Options >
263 struct base_hook: public hook< opt::base_hook_tag, Options... >
268 \p MemberOffset defines offset in bytes of \ref node member into your structure.
269 Use \p offsetof macro to define \p MemberOffset
272 - \p cuckoo::probeset_type - probeset type. Defaul is \p cuckoo::list
273 - \p cuckoo::store_hash - store hash values in the node or not. Default is 0 (no storing)
274 - \p opt::tag - a \ref cds_intrusive_hook_tag "tag"
276 template < size_t MemberOffset, typename... Options >
277 struct member_hook: public hook< opt::member_hook_tag, Options... >
280 static const size_t c_nMemberOffset = MemberOffset;
286 \p NodeTraits defines type traits for node.
287 See \ref node_traits for \p NodeTraits interface description
290 - \p cuckoo::probeset_type - probeset type. Defaul is \p cuckoo::list
291 - \p cuckoo::store_hash - store hash values in the node or not. Default is 0 (no storing)
292 - \p opt::tag - a \ref cds_intrusive_hook_tag "tag"
294 template <typename NodeTraits, typename... Options >
295 struct traits_hook: public hook< opt::traits_hook_tag, Options... >
298 typedef NodeTraits node_traits;
302 /// Internal statistics for \ref striping mutex policy
303 struct striping_stat {
304 typedef cds::atomicity::event_counter counter_type; ///< Counter type
306 counter_type m_nCellLockCount ; ///< Count of obtaining cell lock
307 counter_type m_nCellTryLockCount ; ///< Count of cell \p try_lock attempts
308 counter_type m_nFullLockCount ; ///< Count of obtaining full lock
309 counter_type m_nResizeLockCount ; ///< Count of obtaining resize lock
310 counter_type m_nResizeCount ; ///< Count of resize event
313 void onCellLock() { ++m_nCellLockCount; }
314 void onCellTryLock() { ++m_nCellTryLockCount; }
315 void onFullLock() { ++m_nFullLockCount; }
316 void onResizeLock() { ++m_nResizeLockCount; }
317 void onResize() { ++m_nResizeCount; }
321 /// Dummy internal statistics for \ref striping mutex policy
322 struct empty_striping_stat {
324 void onCellLock() const {}
325 void onCellTryLock() const {}
326 void onFullLock() const {}
327 void onResizeLock() const {}
328 void onResize() const {}
332 /// Lock striping concurrent access policy
334 This is one of available opt::mutex_policy option type for CuckooSet
336 Lock striping is very simple technique.
337 The cuckoo set consists of the bucket tables and the array of locks.
338 There is single lock array for each bucket table, at least, the count of bucket table is 2.
339 Initially, the capacity of lock array and each bucket table is the same.
340 When set is resized, bucket table capacity will be doubled but lock array will not.
341 The lock \p i protects each bucket \p j, where <tt> j = i mod L </tt>,
342 where \p L - the size of lock array.
344 The policy contains an internal array of \p RecursiveLock locks.
347 - \p RecursiveLock - the type of recursive mutex. The default is \p std::recursive_mutex. The mutex type should be default-constructible.
348 Note that a recursive spin-lock is not suitable for lock striping for performance reason.
349 - \p Arity - unsigned int constant that specifies an arity. The arity is the count of hash functors, i.e., the
350 count of lock arrays. Default value is 2.
351 - \p Alloc - allocator type used for lock array memory allocation. Default is \p CDS_DEFAULT_ALLOCATOR.
352 - \p Stat - internal statistics type. Note that this template argument is automatically selected by \ref CuckooSet
353 class according to its \p opt::stat option.
356 class RecursiveLock = std::recursive_mutex,
357 unsigned int Arity = 2,
358 class Alloc = CDS_DEFAULT_ALLOCATOR,
359 class Stat = empty_striping_stat
364 typedef RecursiveLock lock_type ; ///< lock type
365 typedef Alloc allocator_type ; ///< allocator type
366 static unsigned int const c_nArity = Arity ; ///< the arity
367 typedef Stat statistics_type ; ///< Internal statistics type (\ref striping_stat or \ref empty_striping_stat)
370 typedef striping_stat real_stat;
371 typedef empty_striping_stat empty_stat;
373 template <typename Stat2>
374 struct rebind_statistics {
375 typedef striping<lock_type, c_nArity, allocator_type, Stat2> other;
379 typedef cds::lock::array< lock_type, cds::lock::pow2_select_policy, allocator_type > lock_array_type ; ///< lock array type
383 class lock_array: public lock_array_type
387 lock_array(): lock_array_type( typename lock_array_type::select_cell_policy(2) ) {}
390 lock_array( size_t nCapacity ): lock_array_type( nCapacity, typename lock_array_type::select_cell_policy(nCapacity) ) {}
393 class scoped_lock: public std::unique_lock< lock_array_type >
395 typedef std::unique_lock< lock_array_type > base_class;
397 scoped_lock( lock_array& arrLock, size_t nHash ): base_class( arrLock, nHash ) {}
403 lock_array m_Locks[c_nArity] ; ///< array of lock_array_type
404 statistics_type m_Stat ; ///< internal statistics
409 class scoped_cell_lock {
410 lock_type * m_guard[c_nArity];
413 scoped_cell_lock( striping& policy, size_t const* arrHash )
415 for ( unsigned int i = 0; i < c_nArity; ++i ) {
416 m_guard[i] = &( policy.m_Locks[i].at( policy.m_Locks[i].lock( arrHash[i] )));
418 policy.m_Stat.onCellLock();
423 for ( unsigned int i = 0; i < c_nArity; ++i )
424 m_guard[i]->unlock();
428 class scoped_cell_trylock
430 typedef typename lock_array_type::lock_type lock_type;
432 lock_type * m_guard[c_nArity];
436 scoped_cell_trylock( striping& policy, size_t const* arrHash )
438 size_t nCell = policy.m_Locks[0].try_lock( arrHash[0] );
439 m_bLocked = nCell != lock_array_type::c_nUnspecifiedCell;
441 m_guard[0] = &(policy.m_Locks[0].at(nCell));
442 for ( unsigned int i = 1; i < c_nArity; ++i ) {
443 m_guard[i] = &( policy.m_Locks[i].at( policy.m_Locks[i].lock( arrHash[i] )) );
447 std::fill( m_guard, m_guard + c_nArity, nullptr );
449 policy.m_Stat.onCellTryLock();
451 ~scoped_cell_trylock()
454 for ( unsigned int i = 0; i < c_nArity; ++i )
455 m_guard[i]->unlock();
465 class scoped_full_lock {
466 std::unique_lock< lock_array_type > m_guard;
468 scoped_full_lock( striping& policy )
469 : m_guard( policy.m_Locks[0] )
471 policy.m_Stat.onFullLock();
474 /// Ctor for scoped_resize_lock - no statistics is incremented
475 scoped_full_lock( striping& policy, bool )
476 : m_guard( policy.m_Locks[0] )
480 class scoped_resize_lock: public scoped_full_lock {
482 scoped_resize_lock( striping& policy )
483 : scoped_full_lock( policy, false )
485 policy.m_Stat.onResizeLock();
493 size_t nLockCount ///< The size of lock array. Must be power of two.
496 // Trick: initialize the array of locks
497 for ( unsigned int i = 0; i < c_nArity; ++i ) {
498 lock_array * pArr = m_Locks + i;
499 pArr->lock_array::~lock_array();
500 new ( pArr ) lock_array( nLockCount );
504 /// Returns lock array size
506 Lock array size is unchanged during \p striping object lifetime
508 size_t lock_count() const
510 return m_Locks[0].size();
514 void resize( size_t )
520 /// Returns the arity of striping mutex policy
521 CDS_CONSTEXPR unsigned int arity() const CDS_NOEXCEPT
526 /// Returns internal statistics
527 statistics_type const& statistics() const
533 /// Internal statistics for \ref refinable mutex policy
534 struct refinable_stat {
535 typedef cds::atomicity::event_counter counter_type ; ///< Counter type
537 counter_type m_nCellLockCount ; ///< Count of obtaining cell lock
538 counter_type m_nCellLockWaitResizing ; ///< Count of loop iteration to wait for resizing
539 counter_type m_nCellLockArrayChanged ; ///< Count of event "Lock array has been changed when obtaining cell lock"
540 counter_type m_nCellLockFailed ; ///< Count of event "Cell lock failed because of the array is owned by other thread"
542 counter_type m_nSecondCellLockCount ; ///< Count of obtaining cell lock when another cell is already locked
543 counter_type m_nSecondCellLockFailed ; ///< Count of unsuccess obtaining cell lock when another cell is already locked
545 counter_type m_nFullLockCount ; ///< Count of obtaining full lock
546 counter_type m_nFullLockIter ; ///< Count of unsuccessfull iteration to obtain full lock
548 counter_type m_nResizeLockCount ; ///< Count of obtaining resize lock
549 counter_type m_nResizeLockIter ; ///< Count of unsuccessfull iteration to obtain resize lock
550 counter_type m_nResizeLockArrayChanged; ///< Count of event "Lock array has been changed when obtaining resize lock"
551 counter_type m_nResizeCount ; ///< Count of resize event
554 void onCellLock() { ++m_nCellLockCount; }
555 void onCellWaitResizing() { ++m_nCellLockWaitResizing; }
556 void onCellArrayChanged() { ++m_nCellLockArrayChanged; }
557 void onCellLockFailed() { ++m_nCellLockFailed; }
558 void onSecondCellLock() { ++m_nSecondCellLockCount; }
559 void onSecondCellLockFailed() { ++m_nSecondCellLockFailed; }
560 void onFullLock() { ++m_nFullLockCount; }
561 void onFullLockIter() { ++m_nFullLockIter; }
562 void onResizeLock() { ++m_nResizeLockCount; }
563 void onResizeLockIter() { ++m_nResizeLockIter; }
564 void onResizeLockArrayChanged() { ++m_nResizeLockArrayChanged; }
565 void onResize() { ++m_nResizeCount; }
569 /// Dummy internal statistics for \ref refinable mutex policy
570 struct empty_refinable_stat {
572 void onCellLock() const {}
573 void onCellWaitResizing() const {}
574 void onCellArrayChanged() const {}
575 void onCellLockFailed() const {}
576 void onSecondCellLock() const {}
577 void onSecondCellLockFailed() const {}
578 void onFullLock() const {}
579 void onFullLockIter() const {}
580 void onResizeLock() const {}
581 void onResizeLockIter() const {}
582 void onResizeLockArrayChanged() const {}
583 void onResize() const {}
587 /// Refinable concurrent access policy
589 This is one of available opt::mutex_policy option type for CuckooSet
591 Refining is like a striping technique (see cuckoo::striping)
592 but it allows growing the size of lock array when resizing the hash table.
593 So, the sizes of hash table and lock array are equal.
596 - \p RecursiveLock - the type of mutex. Reentrant (recursive) mutex is required.
597 The default is \p std::recursive_mutex. The mutex type should be default-constructible.
598 - \p Arity - unsigned int constant that specifies an arity. The arity is the count of hash functors, i.e., the
599 count of lock arrays. Default value is 2.
600 - \p BackOff - back-off strategy. Default is cds::backoff::yield
601 - \p Alloc - allocator type used for lock array memory allocation. Default is \p CDS_DEFAULT_ALLOCATOR.
602 - \p Stat - internal statistics type. Note that this template argument is automatically selected by \ref CuckooSet
603 class according to its \p opt::stat option.
606 class RecursiveLock = std::recursive_mutex,
607 unsigned int Arity = 2,
608 typename BackOff = cds::backoff::yield,
609 class Alloc = CDS_DEFAULT_ALLOCATOR,
610 class Stat = empty_refinable_stat
615 typedef RecursiveLock lock_type ; ///< lock type
616 typedef Alloc allocator_type ; ///< allocator type
617 typedef BackOff back_off ; ///< back-off strategy
618 typedef Stat statistics_type ; ///< internal statistics type
619 static unsigned int const c_nArity = Arity; ///< the arity
622 typedef refinable_stat real_stat;
623 typedef empty_refinable_stat empty_stat;
625 template <typename Stat2>
626 struct rebind_statistics {
627 typedef refinable< lock_type, c_nArity, back_off, allocator_type, Stat2> other;
633 typedef cds::lock::trivial_select_policy lock_selection_policy;
635 class lock_array_type
636 : public cds::lock::array< lock_type, lock_selection_policy, allocator_type >
637 , public std::enable_shared_from_this< lock_array_type >
639 typedef cds::lock::array< lock_type, lock_selection_policy, allocator_type > lock_array_base;
641 lock_array_type( size_t nCapacity )
642 : lock_array_base( nCapacity )
645 typedef std::shared_ptr< lock_array_type > lock_array_ptr;
646 typedef cds::details::Allocator< lock_array_type, allocator_type > lock_array_allocator;
648 typedef unsigned long long owner_t;
649 typedef cds::OS::ThreadId threadId_t;
651 typedef cds::sync::spin spinlock_type;
652 typedef std::unique_lock< spinlock_type > scoped_spinlock;
657 static owner_t const c_nOwnerMask = (((owner_t) 1) << (sizeof(owner_t) * 8 - 1)) - 1;
659 atomics::atomic< owner_t > m_Owner ; ///< owner mark (thread id + boolean flag)
660 atomics::atomic<size_t> m_nCapacity ; ///< lock array capacity
661 lock_array_ptr m_arrLocks[ c_nArity ] ; ///< Lock array. The capacity of array is specified in constructor.
662 spinlock_type m_access ; ///< access to m_arrLocks
663 statistics_type m_Stat ; ///< internal statistics
668 struct lock_array_disposer {
669 void operator()( lock_array_type * pArr )
671 lock_array_allocator().Delete( pArr );
675 lock_array_ptr create_lock_array( size_t nCapacity )
677 return lock_array_ptr( lock_array_allocator().New( nCapacity ), lock_array_disposer() );
680 void acquire( size_t const * arrHash, lock_array_ptr * pLockArr, lock_type ** parrLock )
682 owner_t me = (owner_t) cds::OS::get_current_thread_id();
689 scoped_spinlock sl(m_access);
690 for ( unsigned int i = 0; i < c_nArity; ++i )
691 pLockArr[i] = m_arrLocks[i];
694 // wait while resizing
696 who = m_Owner.load( atomics::memory_order_acquire );
697 if ( !( who & 1 ) || (who >> 1) == (me & c_nOwnerMask) )
700 m_Stat.onCellWaitResizing();
703 if ( pLockArr[0] != m_arrLocks[0] ) {
704 m_Stat.onCellArrayChanged();
708 size_t const nMask = pLockArr[0]->size() - 1;
709 assert( cds::beans::is_power2( nMask + 1 ));
711 for ( unsigned int i = 0; i < c_nArity; ++i ) {
712 parrLock[i] = &( pLockArr[i]->at( arrHash[i] & nMask ));
716 who = m_Owner.load( atomics::memory_order_acquire );
717 if ( ( !(who & 1) || (who >> 1) == (me & c_nOwnerMask) ) && m_arrLocks[0] == pLockArr[0] ) {
722 for ( unsigned int i = 0; i < c_nArity; ++i ) {
723 parrLock[i]->unlock();
726 m_Stat.onCellLockFailed();
729 // clears pLockArr can lead to calling dtor for each item of pLockArr[i] that may be a heavy-weighted operation
730 // (each pLockArr[i] is a shared pointer to array of a ton of mutexes)
731 // It is better to do this before the next loop iteration where we will use spin-locked assignment to pLockArr
732 // Destructing a lot of mutexes under spin-lock is a bad solution
733 for ( unsigned int i = 0; i < c_nArity; ++i )
738 bool try_second_acquire( size_t const * arrHash, lock_type ** parrLock )
740 // It is assumed that the current thread already has a lock
741 // and requires a second lock for other hash
743 size_t const nMask = m_nCapacity.load(atomics::memory_order_acquire) - 1;
744 size_t nCell = m_arrLocks[0]->try_lock( arrHash[0] & nMask);
745 if ( nCell == lock_array_type::c_nUnspecifiedCell ) {
746 m_Stat.onSecondCellLockFailed();
749 parrLock[0] = &(m_arrLocks[0]->at(nCell));
751 for ( unsigned int i = 1; i < c_nArity; ++i ) {
752 parrLock[i] = &( m_arrLocks[i]->at( m_arrLocks[i]->lock( arrHash[i] & nMask)) );
755 m_Stat.onSecondCellLock();
761 owner_t me = (owner_t) cds::OS::get_current_thread_id();
766 if ( m_Owner.compare_exchange_strong( ownNull, (me << 1) | 1, atomics::memory_order_acq_rel, atomics::memory_order_relaxed )) {
767 m_arrLocks[0]->lock_all();
773 m_Stat.onFullLockIter();
779 m_arrLocks[0]->unlock_all();
780 m_Owner.store( 0, atomics::memory_order_release );
783 void acquire_resize( lock_array_ptr * pOldLocks )
785 owner_t me = (owner_t) cds::OS::get_current_thread_id();
789 scoped_spinlock sl(m_access);
790 for ( unsigned int i = 0; i < c_nArity; ++i )
791 pOldLocks[i] = m_arrLocks[i];
796 if ( m_Owner.compare_exchange_strong( ownNull, (me << 1) | 1, atomics::memory_order_acq_rel, atomics::memory_order_relaxed )) {
797 if ( pOldLocks[0] != m_arrLocks[0] ) {
798 m_Owner.store( 0, atomics::memory_order_release );
799 m_Stat.onResizeLockArrayChanged();
802 pOldLocks[0]->lock_all();
803 m_Stat.onResizeLock();
808 m_Stat.onResizeLockIter();
810 // clears pOldLocks can lead to calling dtor for each item of pOldLocks[i] that may be a heavy-weighted operation
811 // (each pOldLocks[i] is a shared pointer to array of a ton of mutexes)
812 // It is better to do this before the next loop iteration where we will use spin-locked assignment to pOldLocks
813 // Destructing a lot of mutexes under spin-lock is a bad solution
814 for ( unsigned int i = 0; i < c_nArity; ++i )
815 pOldLocks[i].reset();
819 void release_resize( lock_array_ptr * pOldLocks )
821 m_Owner.store( 0, atomics::memory_order_release );
822 pOldLocks[0]->unlock_all();
828 class scoped_cell_lock {
829 lock_type * m_arrLock[ c_nArity ];
830 lock_array_ptr m_arrLockArr[ c_nArity ];
833 scoped_cell_lock( refinable& policy, size_t const* arrHash )
835 policy.acquire( arrHash, m_arrLockArr, m_arrLock );
840 for ( unsigned int i = 0; i < c_nArity; ++i )
841 m_arrLock[i]->unlock();
845 class scoped_cell_trylock {
846 lock_type * m_arrLock[ c_nArity ];
850 scoped_cell_trylock( refinable& policy, size_t const* arrHash )
852 m_bLocked = policy.try_second_acquire( arrHash, m_arrLock );
855 ~scoped_cell_trylock()
858 for ( unsigned int i = 0; i < c_nArity; ++i )
859 m_arrLock[i]->unlock();
869 class scoped_full_lock {
872 scoped_full_lock( refinable& policy )
875 policy.acquire_all();
879 m_policy.release_all();
883 class scoped_resize_lock
886 lock_array_ptr m_arrLocks[ c_nArity ];
888 scoped_resize_lock( refinable& policy )
891 policy.acquire_resize( m_arrLocks );
893 ~scoped_resize_lock()
895 m_policy.release_resize( m_arrLocks );
903 size_t nLockCount ///< The size of lock array. Must be power of two.
905 , m_nCapacity( nLockCount )
907 assert( cds::beans::is_power2( nLockCount ));
908 for ( unsigned int i = 0; i < c_nArity; ++i )
909 m_arrLocks[i] = create_lock_array( nLockCount );
913 void resize( size_t nCapacity )
915 lock_array_ptr pNew[ c_nArity ];
916 for ( unsigned int i = 0; i < c_nArity; ++i )
917 pNew[i] = create_lock_array( nCapacity );
920 // Assignment m_arrLocks[i] = pNew[i] may call heavy-weighted dtor for each item of m_arrLocks
921 // that is unacceptable under spin-lock
922 // So, we store copy of m_arrLocks in pOld
923 lock_array_ptr pOld[ c_nArity ];
924 for ( unsigned int i = 0; i < c_nArity; ++i )
925 pOld[i] = m_arrLocks[i];
927 // m_arrLocks assignment will not lead to calling dtor of each item of m_arrLocks
928 // since copy of m_arrLocks locates in pOld and assignment will not be too painful for spin-lock
932 scoped_spinlock sl(m_access);
933 for ( unsigned int i = 0; i < c_nArity; ++i )
934 m_arrLocks[i] = pNew[i];
936 m_nCapacity.store( nCapacity, atomics::memory_order_release );
942 /// Returns lock array size
944 Lock array size is not a constant for \p refinable policy and can be changed when the set is resized.
946 size_t lock_count() const
948 return m_nCapacity.load(atomics::memory_order_relaxed);
951 /// Returns the arity of \p refinable mutex policy
952 CDS_CONSTEXPR unsigned int arity() const CDS_NOEXCEPT
957 /// Returns internal statistics
958 statistics_type const& statistics() const
964 /// CuckooSet internal statistics
966 typedef cds::atomicity::event_counter counter_type ; ///< Counter type
968 counter_type m_nRelocateCallCount ; ///< Count of \p relocate function call
969 counter_type m_nRelocateRoundCount ; ///< Count of attempts to relocate items
970 counter_type m_nFalseRelocateCount ; ///< Count of unneeded attempts of \p relocate call
971 counter_type m_nSuccessRelocateCount ; ///< Count of successfull item relocating
972 counter_type m_nRelocateAboveThresholdCount; ///< Count of item relocating above probeset threshold
973 counter_type m_nFailedRelocateCount ; ///< Count of failed relocation attemp (when all probeset is full)
975 counter_type m_nResizeCallCount ; ///< Count of \p resize function call
976 counter_type m_nFalseResizeCount ; ///< Count of false \p resize function call (when other thread has been resized the set)
977 counter_type m_nResizeSuccessNodeMove; ///< Count of successfull node moving when resizing
978 counter_type m_nResizeRelocateCall ; ///< Count of \p relocate function call from \p resize function
980 counter_type m_nInsertSuccess ; ///< Count of successfull \p insert function call
981 counter_type m_nInsertFailed ; ///< Count of failed \p insert function call
982 counter_type m_nInsertResizeCount ; ///< Count of \p resize function call from \p insert
983 counter_type m_nInsertRelocateCount ; ///< Count of \p relocate function call from \p insert
984 counter_type m_nInsertRelocateFault ; ///< Count of failed \p relocate function call from \p insert
986 counter_type m_nEnsureExistCount ; ///< Count of call \p ensure function for existing node
987 counter_type m_nEnsureSuccessCount ; ///< Count of successfull \p insert function call for new node
988 counter_type m_nEnsureResizeCount ; ///< Count of \p resize function call from \p ensure
989 counter_type m_nEnsureRelocateCount ; ///< Count of \p relocate function call from \p ensure
990 counter_type m_nEnsureRelocateFault ; ///< Count of failed \p relocate function call from \p ensure
992 counter_type m_nUnlinkSuccess ; ///< Count of success \p unlink function call
993 counter_type m_nUnlinkFailed ; ///< Count of failed \p unlink function call
995 counter_type m_nEraseSuccess ; ///< Count of success \p erase function call
996 counter_type m_nEraseFailed ; ///< Count of failed \p erase function call
998 counter_type m_nFindSuccess ; ///< Count of success \p find function call
999 counter_type m_nFindFailed ; ///< Count of failed \p find function call
1001 counter_type m_nFindEqualSuccess ; ///< Count of success \p find_equal function call
1002 counter_type m_nFindEqualFailed ; ///< Count of failed \p find_equal function call
1004 counter_type m_nFindWithSuccess ; ///< Count of success \p find_with function call
1005 counter_type m_nFindWithFailed ; ///< Count of failed \p find_with function call
1008 void onRelocateCall() { ++m_nRelocateCallCount; }
1009 void onRelocateRound() { ++m_nRelocateRoundCount; }
1010 void onFalseRelocateRound() { ++m_nFalseRelocateCount; }
1011 void onSuccessRelocateRound(){ ++m_nSuccessRelocateCount; }
1012 void onRelocateAboveThresholdRound() { ++m_nRelocateAboveThresholdCount; }
1013 void onFailedRelocate() { ++m_nFailedRelocateCount; }
1015 void onResizeCall() { ++m_nResizeCallCount; }
1016 void onFalseResizeCall() { ++m_nFalseResizeCount; }
1017 void onResizeSuccessMove() { ++m_nResizeSuccessNodeMove; }
1018 void onResizeRelocateCall() { ++m_nResizeRelocateCall; }
1020 void onInsertSuccess() { ++m_nInsertSuccess; }
1021 void onInsertFailed() { ++m_nInsertFailed; }
1022 void onInsertResize() { ++m_nInsertResizeCount; }
1023 void onInsertRelocate() { ++m_nInsertRelocateCount; }
1024 void onInsertRelocateFault() { ++m_nInsertRelocateFault; }
1026 void onEnsureExist() { ++m_nEnsureExistCount; }
1027 void onEnsureSuccess() { ++m_nEnsureSuccessCount; }
1028 void onEnsureResize() { ++m_nEnsureResizeCount; }
1029 void onEnsureRelocate() { ++m_nEnsureRelocateCount; }
1030 void onEnsureRelocateFault() { ++m_nEnsureRelocateFault; }
1032 void onUnlinkSuccess() { ++m_nUnlinkSuccess; }
1033 void onUnlinkFailed() { ++m_nUnlinkFailed; }
1035 void onEraseSuccess() { ++m_nEraseSuccess; }
1036 void onEraseFailed() { ++m_nEraseFailed; }
1038 void onFindSuccess() { ++m_nFindSuccess; }
1039 void onFindFailed() { ++m_nFindFailed; }
1041 void onFindWithSuccess() { ++m_nFindWithSuccess; }
1042 void onFindWithFailed() { ++m_nFindWithFailed; }
1046 /// CuckooSet empty internal statistics
1049 void onRelocateCall() const {}
1050 void onRelocateRound() const {}
1051 void onFalseRelocateRound() const {}
1052 void onSuccessRelocateRound()const {}
1053 void onRelocateAboveThresholdRound() const {}
1054 void onFailedRelocate() const {}
1056 void onResizeCall() const {}
1057 void onFalseResizeCall() const {}
1058 void onResizeSuccessMove() const {}
1059 void onResizeRelocateCall() const {}
1061 void onInsertSuccess() const {}
1062 void onInsertFailed() const {}
1063 void onInsertResize() const {}
1064 void onInsertRelocate() const {}
1065 void onInsertRelocateFault() const {}
1067 void onEnsureExist() const {}
1068 void onEnsureSuccess() const {}
1069 void onEnsureResize() const {}
1070 void onEnsureRelocate() const {}
1071 void onEnsureRelocateFault() const {}
1073 void onUnlinkSuccess() const {}
1074 void onUnlinkFailed() const {}
1076 void onEraseSuccess() const {}
1077 void onEraseFailed() const {}
1079 void onFindSuccess() const {}
1080 void onFindFailed() const {}
1082 void onFindWithSuccess() const {}
1083 void onFindWithFailed() const {}
1087 /// Type traits for CuckooSet class
1092 Possible values are: cuckoo::base_hook, cuckoo::member_hook, cuckoo::traits_hook.
1094 typedef base_hook<> hook;
1096 /// Hash functors tuple
1098 This is mandatory type and has no predefined one.
1100 At least, two hash functors should be provided. All hash functor
1101 should be orthogonal (different): for each <tt> i,j: i != j => h[i](x) != h[j](x) </tt>.
1102 The hash functors are defined as <tt> std::tuple< H1, H2, ... Hn > </tt>:
1103 \@code cds::opt::hash< std::tuple< h1, h2 > > \@endcode
1104 The number of hash functors specifies the number \p k - the count of hash tables in cuckoo hashing.
1106 To specify hash tuple in traits you should use \p cds::opt::hash_tuple:
1108 struct my_traits: public cds::intrusive::cuckoo::traits {
1109 typedef cds::opt::hash_tuple< hash1, hash2 > hash;
1113 typedef cds::opt::none hash;
1115 /// Concurrent access policy
1117 Available opt::mutex_policy types:
1118 - \p cuckoo::striping - simple, but the lock array is not resizable
1119 - \p cuckoo::refinable - resizable lock array, but more complex access to set data.
1121 Default is \p cuckoo::striping.
1123 typedef cuckoo::striping<> mutex_policy;
1125 /// Key equality functor
1127 Default is <tt>std::equal_to<T></tt>
1129 typedef opt::none equal_to;
1131 /// Key comparing functor
1133 No default functor is provided. If the option is not specified, the \p less is used.
1135 typedef opt::none compare;
1137 /// specifies binary predicate used for key comparison.
1139 Default is \p std::less<T>.
1141 typedef opt::none less;
1145 The type for item counting feature.
1146 Default is \p cds::atomicity::item_counter
1148 Only atomic item counter type is allowed.
1150 typedef atomicity::item_counter item_counter;
1154 The allocator type for allocating bucket tables.
1156 typedef CDS_DEFAULT_ALLOCATOR allocator;
1160 The disposer functor is used in \p CuckooSet::clear() member function
1163 typedef intrusive::opt::v::empty_disposer disposer;
1165 /// Internal statistics. Available statistics: \p cuckoo::stat, \p cuckoo::empty_stat
1166 typedef empty_stat stat;
1169 /// Metafunction converting option list to \p CuckooSet traits
1171 Template argument list \p Options... are:
1172 - \p intrusive::opt::hook - hook used. Possible values are: \p cuckoo::base_hook, \p cuckoo::member_hook,
1173 \p cuckoo::traits_hook.
1174 If the option is not specified, <tt>%cuckoo::base_hook<></tt> is used.
1175 - \p opt::hash - hash functor tuple, mandatory option. At least, two hash functors should be provided. All hash functor
1176 should be orthogonal (different): for each <tt> i,j: i != j => h[i](x) != h[j](x) </tt>.
1177 The hash functors are passed as <tt> std::tuple< H1, H2, ... Hn > </tt>. The number of hash functors specifies
1178 the number \p k - the count of hash tables in cuckoo hashing.
1179 - \p opt::mutex_policy - concurrent access policy.
1180 Available policies: \p cuckoo::striping, \p cuckoo::refinable.
1181 Default is \p %cuckoo::striping.
1182 - \p opt::equal_to - key equality functor like \p std::equal_to.
1183 If this functor is defined then the probe-set will be unordered.
1184 If \p %opt::compare or \p %opt::less option is specified too, then the probe-set will be ordered
1185 and \p %opt::equal_to will be ignored.
1186 - \p opt::compare - key comparison functor. No default functor is provided.
1187 If the option is not specified, the \p %opt::less is used.
1188 If \p %opt::compare or \p %opt::less option is specified, then the probe-set will be ordered.
1189 - \p opt::less - specifies binary predicate used for key comparison. Default is \p std::less<T>.
1190 If \p %opt::compare or \p %opt::less option is specified, then the probe-set will be ordered.
1191 - \p opt::item_counter - the type of item counting feature. Default is \p atomicity::item_counter
1192 The item counter should be atomic.
1193 - \p opt::allocator - the allocator type using for allocating bucket tables.
1194 Default is \ref CDS_DEFAULT_ALLOCATOR
1195 - \p intrusive::opt::disposer - the disposer type used in \p clear() member function for
1196 freeing nodes. Default is \p intrusive::opt::v::empty_disposer
1197 - \p opt::stat - internal statistics. Possibly types: \p cuckoo::stat, \p cuckoo::empty_stat.
1198 Default is \p %cuckoo::empty_stat
1200 The probe set traits \p cuckoo::probeset_type and \p cuckoo::store_hash are taken from \p node type
1201 specified by \p opt::hook option.
1203 template <typename... Options>
1204 struct make_traits {
1205 typedef typename cds::opt::make_options<
1206 typename cds::opt::find_type_traits< cuckoo::traits, Options... >::type
1208 >::type type ; ///< Result of metafunction
1213 template <typename Node, typename Probeset>
1216 template <typename Node>
1217 class bucket_entry<Node, cuckoo::list>
1220 typedef Node node_type;
1221 typedef cuckoo::list_probeset_class probeset_class;
1222 typedef cuckoo::list probeset_type;
1232 friend class bucket_entry;
1238 iterator( node_type * p )
1241 iterator( iterator const& it)
1245 iterator& operator=( iterator const& it )
1251 iterator& operator=( node_type * p )
1257 node_type * operator->()
1261 node_type& operator*()
1263 assert( pNode != nullptr );
1268 iterator& operator ++()
1271 pNode = pNode->m_pNext;
1275 bool operator==(iterator const& it ) const
1277 return pNode == it.pNode;
1279 bool operator!=(iterator const& it ) const
1281 return !( *this == it );
1290 static_assert(( std::is_same<typename node_type::probeset_type, probeset_type>::value ), "Incompatible node type" );
1295 return iterator(pHead);
1302 void insert_after( iterator it, node_type * p )
1304 node_type * pPrev = it.pNode;
1306 p->m_pNext = pPrev->m_pNext;
1317 void remove( iterator itPrev, iterator itWhat )
1319 node_type * pPrev = itPrev.pNode;
1320 node_type * pWhat = itWhat.pNode;
1321 assert( (!pPrev && pWhat == pHead) || (pPrev && pPrev->m_pNext == pWhat) );
1324 pPrev->m_pNext = pWhat->m_pNext;
1326 assert( pWhat == pHead );
1327 pHead = pHead->m_pNext;
1336 for ( node_type * pNode = pHead; pNode; pNode = pNext ) {
1337 pNext = pNode->m_pNext;
1345 template <typename Disposer>
1346 void clear( Disposer disp )
1349 for ( node_type * pNode = pHead; pNode; pNode = pNext ) {
1350 pNext = pNode->m_pNext;
1359 unsigned int size() const
1365 template <typename Node, unsigned int Capacity>
1366 class bucket_entry<Node, cuckoo::vector<Capacity> >
1369 typedef Node node_type;
1370 typedef cuckoo::vector_probeset_class probeset_class;
1371 typedef cuckoo::vector<Capacity> probeset_type;
1373 static unsigned int const c_nCapacity = probeset_type::c_nCapacity;
1376 node_type * m_arrNode[c_nCapacity];
1377 unsigned int m_nSize;
1379 void shift_up( unsigned int nFrom )
1381 assert( m_nSize < c_nCapacity );
1384 if ( nFrom < m_nSize )
1385 std::copy_backward( m_arrNode + nFrom, m_arrNode + m_nSize, m_arrNode + m_nSize + 1 );
1387 // alternative: low-level byte copying
1388 //memmove( m_arrNode + nFrom + 1, m_arrNode + nFrom, (m_nSize - nFrom) * sizeof(m_arrNode[0]) );
1391 void shift_down( node_type ** pFrom )
1393 assert( m_arrNode <= pFrom && pFrom < m_arrNode + m_nSize);
1395 std::copy( pFrom + 1, m_arrNode + m_nSize, pFrom );
1397 // alternative: low-level byte copying
1398 //memmove( pFrom + 1, pFrom, (m_nSize - nFrom - 1) * sizeof(m_arrNode[0]));
1404 friend class bucket_entry;
1410 iterator( node_type ** p )
1413 iterator( iterator const& it)
1417 iterator& operator=( iterator const& it )
1423 node_type * operator->()
1425 assert( pArr != nullptr );
1428 node_type& operator*()
1430 assert( pArr != nullptr );
1431 assert( *pArr != nullptr );
1436 iterator& operator ++()
1442 bool operator==(iterator const& it ) const
1444 return pArr == it.pArr;
1446 bool operator!=(iterator const& it ) const
1448 return !( *this == it );
1456 memset( m_arrNode, 0, sizeof(m_arrNode));
1457 static_assert(( std::is_same<typename node_type::probeset_type, probeset_type>::value ), "Incompatible node type" );
1462 return iterator(m_arrNode);
1466 return iterator(m_arrNode + size());
1469 void insert_after( iterator it, node_type * p )
1471 assert( m_nSize < c_nCapacity );
1472 assert( !it.pArr || (m_arrNode <= it.pArr && it.pArr <= m_arrNode + m_nSize));
1475 shift_up( (unsigned int)(it.pArr - m_arrNode) + 1 );
1485 void remove( iterator /*itPrev*/, iterator itWhat )
1488 shift_down( itWhat.pArr );
1497 template <typename Disposer>
1498 void clear( Disposer disp )
1500 for ( unsigned int i = 0; i < m_nSize; ++i ) {
1501 disp( m_arrNode[i] );
1506 unsigned int size() const
1512 template <typename Node, unsigned int ArraySize>
1514 static void store( Node * pNode, size_t * pHashes )
1516 memcpy( pNode->m_arrHash, pHashes, sizeof(size_t) * ArraySize );
1518 static bool equal_to( Node& node, unsigned int nTable, size_t nHash )
1520 return node.m_arrHash[nTable] == nHash;
1523 template <typename Node>
1524 struct hash_ops<Node, 0>
1526 static void store( Node * /*pNode*/, size_t * /*pHashes*/ )
1528 static bool equal_to( Node& /*node*/, unsigned int /*nTable*/, size_t /*nHash*/ )
1534 template <typename NodeTraits, bool Ordered>
1537 template <typename NodeTraits>
1538 struct contains<NodeTraits, true>
1540 template <typename BucketEntry, typename Position, typename Q, typename Compare>
1541 static bool find( BucketEntry& probeset, Position& pos, unsigned int /*nTable*/, size_t /*nHash*/, Q const& val, Compare cmp )
1544 typedef typename BucketEntry::iterator bucket_iterator;
1546 bucket_iterator itPrev;
1548 for ( bucket_iterator it = probeset.begin(), itEnd = probeset.end(); it != itEnd; ++it ) {
1549 int cmpRes = cmp( *NodeTraits::to_value_ptr(*it), val );
1550 if ( cmpRes >= 0 ) {
1552 pos.itPrev = itPrev;
1559 pos.itPrev = itPrev;
1560 pos.itFound = probeset.end();
1565 template <typename NodeTraits>
1566 struct contains<NodeTraits, false>
1568 template <typename BucketEntry, typename Position, typename Q, typename EqualTo>
1569 static bool find( BucketEntry& probeset, Position& pos, unsigned int nTable, size_t nHash, Q const& val, EqualTo eq )
1571 // Unordered version
1572 typedef typename BucketEntry::iterator bucket_iterator;
1573 typedef typename BucketEntry::node_type node_type;
1575 bucket_iterator itPrev;
1577 for ( bucket_iterator it = probeset.begin(), itEnd = probeset.end(); it != itEnd; ++it ) {
1578 if ( hash_ops<node_type, node_type::hash_array_size>::equal_to( *it, nTable, nHash ) && eq( *NodeTraits::to_value_ptr(*it), val )) {
1580 pos.itPrev = itPrev;
1586 pos.itPrev = itPrev;
1587 pos.itFound = probeset.end();
1592 } // namespace details
1595 } // namespace cuckoo
1598 /** @ingroup cds_intrusive_map
1601 - [2007] M.Herlihy, N.Shavit, M.Tzafrir "Concurrent Cuckoo Hashing. Technical report"
1602 - [2008] Maurice Herlihy, Nir Shavit "The Art of Multiprocessor Programming"
1604 <b>About Cuckoo hashing</b>
1606 [From <i>"The Art of Multiprocessor Programming"</i>]
1607 Cuckoo hashing is a hashing algorithm in which a newly added item displaces any earlier item
1608 occupying the same slot. For brevity, a table is a k-entry array of items. For a hash set f size
1609 N = 2k we use a two-entry array of tables, and two independent hash functions,
1610 <tt> h0, h1: KeyRange -> 0,...,k-1</tt>
1611 mapping the set of possible keys to entries in he array. To test whether a value \p x is in the set,
1612 <tt>find(x)</tt> tests whether either <tt>table[0][h0(x)]</tt> or <tt>table[1][h1(x)]</tt> is
1613 equal to \p x. Similarly, <tt>erase(x)</tt>checks whether \p x is in either <tt>table[0][h0(x)]</tt>
1614 or <tt>table[1][h1(x)]</tt>, ad removes it if found.
1616 The <tt>insert(x)</tt> successively "kicks out" conflicting items until every key has a slot.
1617 To add \p x, the method swaps \p x with \p y, the current occupant of <tt>table[0][h0(x)]</tt>.
1618 If the prior value was \p nullptr, it is done. Otherwise, it swaps the newly nest-less value \p y
1619 for the current occupant of <tt>table[1][h1(y)]</tt> in the same way. As before, if the prior value
1620 was \p nullptr, it is done. Otherwise, the method continues swapping entries (alternating tables)
1621 until it finds an empty slot. We might not find an empty slot, either because the table is full,
1622 or because the sequence of displacement forms a cycle. We therefore need an upper limit on the
1623 number of successive displacements we are willing to undertake. When this limit is exceeded,
1624 we resize the hash table, choose new hash functions and start over.
1626 For concurrent cuckoo hashing, rather than organizing the set as a two-dimensional table of
1627 items, we use two-dimensional table of probe sets, where a probe set is a constant-sized set
1628 of items with the same hash code. Each probe set holds at most \p PROBE_SIZE items, but the algorithm
1629 tries to ensure that when the set is quiescent (i.e no method call in progress) each probe set
1630 holds no more than <tt>THRESHOLD < PROBE_SET</tt> items. While method calls are in-flight, a probe
1631 set may temporarily hold more than \p THRESHOLD but never more than \p PROBE_SET items.
1633 In current implementation, a probe set can be defined either as a (single-linked) list
1634 or as a fixed-sized vector, optionally ordered.
1636 In description above two-table cuckoo hashing (<tt>k = 2</tt>) has been considered.
1637 We can generalize this approach for <tt>k >= 2</tt> when we have \p k hash functions
1638 <tt>h[0], ... h[k-1]</tt> and \p k tables <tt>table[0], ... table[k-1]</tt>.
1640 The search in probe set is linear, the complexity is <tt> O(PROBE_SET) </tt>.
1641 The probe set may be ordered or not. Ordered probe set can be more efficient since
1642 the average search complexity is <tt>O(PROBE_SET/2)</tt>.
1643 However, the overhead of sorting can eliminate a gain of ordered search.
1645 The probe set is ordered if opt::compare or opt::less is specified in \p Traits template
1646 parameter. Otherwise, the probe set is unordered and \p Traits must contain
1647 opt::equal_to option.
1649 The cds::intrusive::cuckoo namespace contains \p %CuckooSet-related declarations.
1652 - \p T - the type stored in the set. The type must be based on cuckoo::node (for cuckoo::base_hook)
1653 or it must have a member of type %cuckoo::node (for cuckoo::member_hook),
1654 or it must be convertible to \p %cuckoo::node (for cuckoo::traits_hook)
1655 - \p Traits - type traits, default is cuckoo::traits. It is possible to declare option-based
1656 set with \p cuckoo::make_traits metafunction result as \p Traits template argument.
1660 You should incorporate \p cuckoo::node into your struct \p T and provide
1661 appropriate \p cuckoo::traits::hook in your \p Traits template parameters.
1662 Usually, for \p Traits you define a struct based on \p cuckoo::traits.
1664 Example for base hook and list-based probe-set:
1666 #include <cds/intrusive/cuckoo_set.h>
1668 // Data stored in cuckoo set
1669 // We use list as probe-set container and store hash values in the node
1670 // (since we use two hash functions we should store 2 hash values per node)
1671 struct my_data: public cds::intrusive::cuckoo::node< cds::intrusive::cuckoo::list, 2 >
1680 // Provide equal_to functor for my_data since we will use unordered probe-set
1681 struct my_data_equal_to {
1682 bool operator()( const my_data& d1, const my_data& d2 ) const
1684 return d1.strKey.compare( d2.strKey ) == 0;
1687 bool operator()( const my_data& d, const std::string& s ) const
1689 return d.strKey.compare(s) == 0;
1692 bool operator()( const std::string& s, const my_data& d ) const
1694 return s.compare( d.strKey ) == 0;
1698 // Provide two hash functor for my_data
1700 size_t operator()(std::string const& s) const
1702 return cds::opt::v::hash<std::string>( s );
1704 size_t operator()( my_data const& d ) const
1706 return (*this)( d.strKey );
1710 struct hash2: private hash1 {
1711 size_t operator()(std::string const& s) const
1713 size_t h = ~( hash1::operator()(s));
1714 return ~h + 0x9e3779b9 + (h << 6) + (h >> 2);
1716 size_t operator()( my_data const& d ) const
1718 return (*this)( d.strKey );
1722 // Declare type traits
1723 struct my_traits: public cds::intrusive::cuckoo::traits
1725 typedef cds::intrusive::cuckoo::base_hook<
1726 cds::intrusive::cuckoo::probeset_type< my_data::probeset_type >
1727 ,cds::intrusive::cuckoo::store_hash< my_data::hash_array_size >
1729 typedef my_data_equa_to equal_to;
1730 typedef cds::opt::hash_tuple< hash1, hash2 > hash;
1733 // Declare CuckooSet type
1734 typedef cds::intrusive::CuckooSet< my_data, my_traits > my_cuckoo_set;
1736 // Equal option-based declaration
1737 typedef cds::intrusive::CuckooSet< my_data,
1738 cds::intrusive::cuckoo::make_traits<
1739 cds::intrusive::opt::hook< cds::intrusive::cuckoo::base_hook<
1740 cds::intrusive::cuckoo::probeset_type< my_data::probeset_type >
1741 ,cds::intrusive::cuckoo::store_hash< my_data::hash_array_size >
1743 ,cds::opt::hash< std::tuple< hash1, hash2 > >
1744 ,cds::opt::equal_to< my_data_equal_to >
1749 If we provide \p compare function instead of \p equal_to for \p my_data
1750 we get as a result a cuckoo set with ordered probe set that may improve
1752 Example for base hook and ordered vector-based probe-set:
1755 #include <cds/intrusive/cuckoo_set.h>
1757 // Data stored in cuckoo set
1758 // We use a vector of capacity 4 as probe-set container and store hash values in the node
1759 // (since we use two hash functions we should store 2 hash values per node)
1760 struct my_data: public cds::intrusive::cuckoo::node< cds::intrusive::cuckoo::vector<4>, 2 >
1769 // Provide compare functor for my_data since we want to use ordered probe-set
1770 struct my_data_compare {
1771 int operator()( const my_data& d1, const my_data& d2 ) const
1773 return d1.strKey.compare( d2.strKey );
1776 int operator()( const my_data& d, const std::string& s ) const
1778 return d.strKey.compare(s);
1781 int operator()( const std::string& s, const my_data& d ) const
1783 return s.compare( d.strKey );
1787 // Provide two hash functor for my_data
1789 size_t operator()(std::string const& s) const
1791 return cds::opt::v::hash<std::string>( s );
1793 size_t operator()( my_data const& d ) const
1795 return (*this)( d.strKey );
1799 struct hash2: private hash1 {
1800 size_t operator()(std::string const& s) const
1802 size_t h = ~( hash1::operator()(s));
1803 return ~h + 0x9e3779b9 + (h << 6) + (h >> 2);
1805 size_t operator()( my_data const& d ) const
1807 return (*this)( d.strKey );
1811 // Declare type traits
1812 struct my_traits: public cds::intrusive::cuckoo::traits
1814 typedef cds::intrusive::cuckoo::base_hook<
1815 cds::intrusive::cuckoo::probeset_type< my_data::probeset_type >
1816 ,cds::intrusive::cuckoo::store_hash< my_data::hash_array_size >
1818 typedef my_data_compare compare;
1819 typedef cds::opt::hash_tuple< hash1, hash2 > hash;
1822 // Declare CuckooSet type
1823 typedef cds::intrusive::CuckooSet< my_data, my_traits > my_cuckoo_set;
1825 // Equal option-based declaration
1826 typedef cds::intrusive::CuckooSet< my_data,
1827 cds::intrusive::cuckoo::make_traits<
1828 cds::intrusive::opt::hook< cds::intrusive::cuckoo::base_hook<
1829 cds::intrusive::cuckoo::probeset_type< my_data::probeset_type >
1830 ,cds::intrusive::cuckoo::store_hash< my_data::hash_array_size >
1832 ,cds::opt::hash< std::tuple< hash1, hash2 > >
1833 ,cds::opt::compare< my_data_compare >
1839 template <typename T, typename Traits = cuckoo::traits>
1843 typedef T value_type; ///< The value type stored in the set
1844 typedef Traits traits; ///< Set traits
1846 typedef typename traits::hook hook; ///< hook type
1847 typedef typename hook::node_type node_type; ///< node type
1848 typedef typename get_node_traits< value_type, node_type, hook>::type node_traits; ///< node traits
1850 typedef typename traits::hash hash; ///< hash functor tuple wrapped for internal use
1851 typedef typename hash::hash_tuple_type hash_tuple_type; ///< Type of hash tuple
1853 typedef typename traits::stat stat; ///< internal statistics type
1855 typedef typename traits::mutex_policy original_mutex_policy; ///< Concurrent access policy, see \p cuckoo::traits::mutex_policy
1857 /// Actual mutex policy
1859 Actual mutex policy is built from mutex policy type provided by \p Traits template argument (see \p cuckoo::traits::mutex_policy)
1860 but mutex policy internal statistics is conformed with \p cukoo::traits::stat type provided by \p Traits:
1861 - if \p %cuckoo::traits::stat is \p cuckoo::empty_stat then mutex policy statistics is already empty
1862 - otherwise real mutex policy statistics is used
1864 typedef typename original_mutex_policy::template rebind_statistics<
1865 typename std::conditional<
1866 std::is_same< stat, cuckoo::empty_stat >::value
1867 ,typename original_mutex_policy::empty_stat
1868 ,typename original_mutex_policy::real_stat
1870 >::other mutex_policy;
1872 static bool const c_isSorted = !( std::is_same< typename traits::compare, opt::none >::value
1873 && std::is_same< typename traits::less, opt::none >::value ) ; ///< whether the probe set should be ordered
1874 static size_t const c_nArity = hash::size ; ///< the arity of cuckoo hashing: the number of hash functors provided; minimum 2.
1876 /// Key equality functor; used only for unordered probe-set
1877 typedef typename opt::details::make_equal_to< value_type, traits, !c_isSorted>::type key_equal_to;
1879 /// key comparing functor based on opt::compare and opt::less option setter. Used only for ordered probe set
1880 typedef typename opt::details::make_comparator< value_type, traits >::type key_comparator;
1883 typedef typename traits::allocator allocator;
1885 /// item counter type
1886 typedef typename traits::item_counter item_counter;
1889 typedef typename traits::disposer disposer;
1893 typedef typename node_type::probeset_class probeset_class;
1894 typedef typename node_type::probeset_type probeset_type;
1895 static unsigned int const c_nNodeHashArraySize = node_type::hash_array_size;
1897 typedef typename mutex_policy::scoped_cell_lock scoped_cell_lock;
1898 typedef typename mutex_policy::scoped_cell_trylock scoped_cell_trylock;
1899 typedef typename mutex_policy::scoped_full_lock scoped_full_lock;
1900 typedef typename mutex_policy::scoped_resize_lock scoped_resize_lock;
1902 typedef cuckoo::details::bucket_entry< node_type, probeset_type > bucket_entry;
1903 typedef typename bucket_entry::iterator bucket_iterator;
1904 typedef cds::details::Allocator< bucket_entry, allocator > bucket_table_allocator;
1906 typedef size_t hash_array[c_nArity] ; ///< hash array
1909 bucket_iterator itPrev;
1910 bucket_iterator itFound;
1913 typedef typename std::conditional< c_isSorted
1914 , cuckoo::details::contains< node_traits, true >
1915 , cuckoo::details::contains< node_traits, false >
1916 >::type contains_action;
1918 template <typename Predicate>
1919 struct predicate_wrapper {
1920 typedef typename std::conditional< c_isSorted, cds::opt::details::make_comparator_from_less<Predicate>, Predicate>::type type;
1923 typedef typename std::conditional< c_isSorted, key_comparator, key_equal_to >::type key_predicate;
1927 static unsigned int const c_nDefaultProbesetSize = 4; ///< default probeset size
1928 static size_t const c_nDefaultInitialSize = 16; ///< default initial size
1929 static unsigned int const c_nRelocateLimit = c_nArity * 2 - 1; ///< Count of attempts to relocate before giving up
1932 bucket_entry * m_BucketTable[ c_nArity ] ; ///< Bucket tables
1934 size_t m_nBucketMask ; ///< Hash bitmask; bucket table size minus 1.
1935 unsigned int const m_nProbesetSize ; ///< Probe set size
1936 unsigned int const m_nProbesetThreshold ; ///< Probe set threshold
1938 hash m_Hash ; ///< Hash functor tuple
1939 mutex_policy m_MutexPolicy ; ///< concurrent access policy
1940 item_counter m_ItemCounter ; ///< item counter
1941 mutable stat m_Stat ; ///< internal statistics
1945 static void check_common_constraints()
1947 static_assert( (c_nArity == mutex_policy::c_nArity), "The count of hash functors must be equal to mutex_policy arity" );
1950 void check_probeset_properties() const
1952 assert( m_nProbesetThreshold < m_nProbesetSize );
1954 // if probe set type is cuckoo::vector<N> then m_nProbesetSize == N
1955 assert( node_type::probeset_size == 0 || node_type::probeset_size == m_nProbesetSize );
1958 template <typename Q>
1959 void hashing( size_t * pHashes, Q const& v ) const
1961 m_Hash( pHashes, v );
1964 void copy_hash( size_t * pHashes, value_type const& v ) const
1966 if ( c_nNodeHashArraySize )
1967 memcpy( pHashes, node_traits::to_node_ptr( v )->get_hash(), sizeof(pHashes[0]) * c_nNodeHashArraySize );
1969 hashing( pHashes, v );
1972 bucket_entry& bucket( unsigned int nTable, size_t nHash )
1974 assert( nTable < c_nArity );
1975 return m_BucketTable[nTable][nHash & m_nBucketMask];
1978 static void store_hash( node_type * pNode, size_t * pHashes )
1980 cuckoo::details::hash_ops< node_type, c_nNodeHashArraySize >::store( pNode, pHashes );
1981 //memcpy( pNode->m_arrHash, pHashes, sizeof(size_t) * c_nArity );
1984 static bool equal_hash( node_type& node, unsigned int nTable, size_t nHash )
1986 return cuckoo::details::hash_ops< node_type, c_nNodeHashArraySize >::equal_to( node, nTable, nHash );
1989 void allocate_bucket_tables( size_t nSize )
1991 assert( cds::beans::is_power2( nSize ) );
1993 m_nBucketMask = nSize - 1;
1994 bucket_table_allocator alloc;
1995 for ( unsigned int i = 0; i < c_nArity; ++i )
1996 m_BucketTable[i] = alloc.NewArray( nSize );
1999 static void free_bucket_tables( bucket_entry ** pTable, size_t nCapacity )
2001 bucket_table_allocator alloc;
2002 for ( unsigned int i = 0; i < c_nArity; ++i ) {
2003 alloc.Delete( pTable[i], nCapacity );
2004 pTable[i] = nullptr;
2007 void free_bucket_tables()
2009 free_bucket_tables( m_BucketTable, m_nBucketMask + 1 );
2012 static unsigned int const c_nUndefTable = (unsigned int) -1;
2013 template <typename Q, typename Predicate >
2014 unsigned int contains( position * arrPos, size_t * arrHash, Q const& val, Predicate pred )
2016 // Buckets must be locked
2018 for ( unsigned int i = 0; i < c_nArity; ++i ) {
2019 bucket_entry& probeset = bucket( i, arrHash[i] );
2020 if ( contains_action::find( probeset, arrPos[i], i, arrHash[i], val, pred ))
2023 return c_nUndefTable;
2026 template <typename Q, typename Predicate, typename Func>
2027 value_type * erase_( Q const& val, Predicate pred, Func f )
2030 hashing( arrHash, val );
2031 position arrPos[ c_nArity ];
2034 scoped_cell_lock guard( m_MutexPolicy, arrHash );
2036 unsigned int nTable = contains( arrPos, arrHash, val, pred );
2037 if ( nTable != c_nUndefTable ) {
2038 node_type& node = *arrPos[nTable].itFound;
2039 f( *node_traits::to_value_ptr(node) );
2040 bucket( nTable, arrHash[nTable]).remove( arrPos[nTable].itPrev, arrPos[nTable].itFound );
2042 m_Stat.onEraseSuccess();
2043 return node_traits::to_value_ptr( node );
2047 m_Stat.onEraseFailed();
2051 template <typename Q, typename Predicate, typename Func>
2052 bool find_( Q& val, Predicate pred, Func f )
2055 position arrPos[ c_nArity ];
2056 hashing( arrHash, val );
2057 scoped_cell_lock sl( m_MutexPolicy, arrHash );
2059 unsigned int nTable = contains( arrPos, arrHash, val, pred );
2060 if ( nTable != c_nUndefTable ) {
2061 f( *node_traits::to_value_ptr( *arrPos[nTable].itFound ), val );
2062 m_Stat.onFindSuccess();
2066 m_Stat.onFindFailed();
2070 bool relocate( unsigned int nTable, size_t * arrGoalHash )
2072 // arrGoalHash contains hash values for relocating element
2073 // Relocating element is first one from bucket( nTable, arrGoalHash[nTable] ) probeset
2075 m_Stat.onRelocateCall();
2079 for ( unsigned int nRound = 0; nRound < c_nRelocateLimit; ++nRound ) {
2080 m_Stat.onRelocateRound();
2083 scoped_cell_lock guard( m_MutexPolicy, arrGoalHash );
2085 bucket_entry& refBucket = bucket( nTable, arrGoalHash[nTable] );
2086 if ( refBucket.size() < m_nProbesetThreshold ) {
2087 // probeset is not above the threshold
2088 m_Stat.onFalseRelocateRound();
2092 pVal = node_traits::to_value_ptr( *refBucket.begin() );
2093 copy_hash( arrHash, *pVal );
2095 scoped_cell_trylock guard2( m_MutexPolicy, arrHash );
2096 if ( !guard2.locked() )
2097 continue ; // try one more time
2099 refBucket.remove( typename bucket_entry::iterator(), refBucket.begin() );
2101 unsigned int i = (nTable + 1) % c_nArity;
2103 // try insert into free probeset
2104 while ( i != nTable ) {
2105 bucket_entry& bkt = bucket( i, arrHash[i] );
2106 if ( bkt.size() < m_nProbesetThreshold ) {
2108 contains_action::find( bkt, pos, i, arrHash[i], *pVal, key_predicate() ) ; // must return false!
2109 bkt.insert_after( pos.itPrev, node_traits::to_node_ptr( pVal ));
2110 m_Stat.onSuccessRelocateRound();
2113 i = ( i + 1 ) % c_nArity;
2116 // try insert into partial probeset
2117 i = (nTable + 1) % c_nArity;
2118 while ( i != nTable ) {
2119 bucket_entry& bkt = bucket( i, arrHash[i] );
2120 if ( bkt.size() < m_nProbesetSize ) {
2122 contains_action::find( bkt, pos, i, arrHash[i], *pVal, key_predicate() ) ; // must return false!
2123 bkt.insert_after( pos.itPrev, node_traits::to_node_ptr( pVal ));
2125 memcpy( arrGoalHash, arrHash, sizeof(arrHash));
2126 m_Stat.onRelocateAboveThresholdRound();
2127 goto next_iteration;
2129 i = (i + 1) % c_nArity;
2132 // all probeset is full, relocating fault
2133 refBucket.insert_after( typename bucket_entry::iterator(), node_traits::to_node_ptr( pVal ));
2134 m_Stat.onFailedRelocate();
2145 m_Stat.onResizeCall();
2147 size_t nOldCapacity = bucket_count();
2148 bucket_entry * pOldTable[ c_nArity ];
2150 scoped_resize_lock guard( m_MutexPolicy );
2152 if ( nOldCapacity != bucket_count() ) {
2153 m_Stat.onFalseResizeCall();
2157 size_t nCapacity = nOldCapacity * 2;
2159 m_MutexPolicy.resize( nCapacity );
2160 memcpy( pOldTable, m_BucketTable, sizeof(pOldTable));
2161 allocate_bucket_tables( nCapacity );
2163 typedef typename bucket_entry::iterator bucket_iterator;
2165 position arrPos[ c_nArity ];
2167 for ( unsigned int nTable = 0; nTable < c_nArity; ++nTable ) {
2168 bucket_entry * pTable = pOldTable[nTable];
2169 for ( size_t k = 0; k < nOldCapacity; ++k ) {
2170 bucket_iterator itNext;
2171 for ( bucket_iterator it = pTable[k].begin(), itEnd = pTable[k].end(); it != itEnd; it = itNext ) {
2175 value_type& val = *node_traits::to_value_ptr( *it );
2176 copy_hash( arrHash, val );
2177 contains( arrPos, arrHash, val, key_predicate() ) ; // must return c_nUndefTable
2179 for ( unsigned int i = 0; i < c_nArity; ++i ) {
2180 bucket_entry& refBucket = bucket( i, arrHash[i] );
2181 if ( refBucket.size() < m_nProbesetThreshold ) {
2182 refBucket.insert_after( arrPos[i].itPrev, &*it );
2183 m_Stat.onResizeSuccessMove();
2188 for ( unsigned int i = 0; i < c_nArity; ++i ) {
2189 bucket_entry& refBucket = bucket( i, arrHash[i] );
2190 if ( refBucket.size() < m_nProbesetSize ) {
2191 refBucket.insert_after( arrPos[i].itPrev, &*it );
2192 assert( refBucket.size() > 1 );
2193 copy_hash( arrHash, *node_traits::to_value_ptr( *refBucket.begin()) );
2194 m_Stat.onResizeRelocateCall();
2195 relocate( i, arrHash );
2204 free_bucket_tables( pOldTable, nOldCapacity );
2207 CDS_CONSTEXPR static unsigned int calc_probeset_size( unsigned int nProbesetSize ) CDS_NOEXCEPT
2209 return nProbesetSize
2211 : ( node_type::probeset_size ? node_type::probeset_size : c_nDefaultProbesetSize )
2217 /// Default constructor
2219 Initial size = \ref c_nDefaultInitialSize
2222 - \p c_nDefaultProbesetSize if \p probeset_type is \p cuckoo::list
2223 - \p Capacity if \p probeset_type is <tt> cuckoo::vector<Capacity> </tt>
2225 Probe set threshold = probe set size - 1
2228 : m_nProbesetSize( calc_probeset_size(0) )
2229 , m_nProbesetThreshold( m_nProbesetSize - 1 )
2230 , m_MutexPolicy( c_nDefaultInitialSize )
2232 check_common_constraints();
2233 check_probeset_properties();
2235 allocate_bucket_tables( c_nDefaultInitialSize );
2238 /// Constructs the set object with given probe set size and threshold
2240 If probe set type is <tt> cuckoo::vector<Capacity> </tt> vector
2241 then \p nProbesetSize should be equal to vector's \p Capacity.
2244 size_t nInitialSize ///< Initial set size; if 0 - use default initial size \ref c_nDefaultInitialSize
2245 , unsigned int nProbesetSize ///< probe set size
2246 , unsigned int nProbesetThreshold = 0 ///< probe set threshold, <tt>nProbesetThreshold < nProbesetSize</tt>. If 0, nProbesetThreshold = nProbesetSize - 1
2248 : m_nProbesetSize( calc_probeset_size(nProbesetSize) )
2249 , m_nProbesetThreshold( nProbesetThreshold ? nProbesetThreshold : m_nProbesetSize - 1 )
2250 , m_MutexPolicy( cds::beans::ceil2(nInitialSize ? nInitialSize : c_nDefaultInitialSize ))
2252 check_common_constraints();
2253 check_probeset_properties();
2255 allocate_bucket_tables( nInitialSize ? cds::beans::ceil2( nInitialSize ) : c_nDefaultInitialSize );
2258 /// Constructs the set object with given hash functor tuple
2260 The probe set size and threshold are set as default, see CuckooSet()
2263 hash_tuple_type const& h ///< hash functor tuple of type <tt>std::tuple<H1, H2, ... Hn></tt> where <tt> n == \ref c_nArity </tt>
2265 : m_nProbesetSize( calc_probeset_size(0) )
2266 , m_nProbesetThreshold( m_nProbesetSize -1 )
2268 , m_MutexPolicy( c_nDefaultInitialSize )
2270 check_common_constraints();
2271 check_probeset_properties();
2273 allocate_bucket_tables( c_nDefaultInitialSize );
2276 /// Constructs the set object with given probe set properties and hash functor tuple
2278 If probe set type is <tt> cuckoo::vector<Capacity> </tt> vector
2279 then \p nProbesetSize should be equal to vector's \p Capacity.
2282 size_t nInitialSize ///< Initial set size; if 0 - use default initial size \ref c_nDefaultInitialSize
2283 , unsigned int nProbesetSize ///< probe set size, positive integer
2284 , unsigned int nProbesetThreshold ///< probe set threshold, <tt>nProbesetThreshold < nProbesetSize</tt>. If 0, nProbesetThreshold = nProbesetSize - 1
2285 , hash_tuple_type const& h ///< hash functor tuple of type <tt>std::tuple<H1, H2, ... Hn></tt> where <tt> n == \ref c_nArity </tt>
2287 : m_nProbesetSize( calc_probeset_size(nProbesetSize) )
2288 , m_nProbesetThreshold( nProbesetThreshold ? nProbesetThreshold : m_nProbesetSize - 1)
2290 , m_MutexPolicy( cds::beans::ceil2(nInitialSize ? nInitialSize : c_nDefaultInitialSize ))
2292 check_common_constraints();
2293 check_probeset_properties();
2295 allocate_bucket_tables( nInitialSize ? cds::beans::ceil2( nInitialSize ) : c_nDefaultInitialSize );
2298 /// Constructs the set object with given hash functor tuple (move semantics)
2300 The probe set size and threshold are set as default, see CuckooSet()
2303 hash_tuple_type&& h ///< hash functor tuple of type <tt>std::tuple<H1, H2, ... Hn></tt> where <tt> n == \ref c_nArity </tt>
2305 : m_nProbesetSize( calc_probeset_size(0) )
2306 , m_nProbesetThreshold( m_nProbesetSize / 2 )
2307 , m_Hash( std::forward<hash_tuple_type>(h) )
2308 , m_MutexPolicy( c_nDefaultInitialSize )
2310 check_common_constraints();
2311 check_probeset_properties();
2313 allocate_bucket_tables( c_nDefaultInitialSize );
2316 /// Constructs the set object with given probe set properties and hash functor tuple (move semantics)
2318 If probe set type is <tt> cuckoo::vector<Capacity> </tt> vector
2319 then \p nProbesetSize should be equal to vector's \p Capacity.
2322 size_t nInitialSize ///< Initial set size; if 0 - use default initial size \ref c_nDefaultInitialSize
2323 , unsigned int nProbesetSize ///< probe set size, positive integer
2324 , unsigned int nProbesetThreshold ///< probe set threshold, <tt>nProbesetThreshold < nProbesetSize</tt>. If 0, nProbesetThreshold = nProbesetSize - 1
2325 , hash_tuple_type&& h ///< hash functor tuple of type <tt>std::tuple<H1, H2, ... Hn></tt> where <tt> n == \ref c_nArity </tt>
2327 : m_nProbesetSize( calc_probeset_size(nProbesetSize) )
2328 , m_nProbesetThreshold( nProbesetThreshold ? nProbesetThreshold : m_nProbesetSize - 1)
2329 , m_Hash( std::forward<hash_tuple_type>(h) )
2330 , m_MutexPolicy( cds::beans::ceil2(nInitialSize ? nInitialSize : c_nDefaultInitialSize ))
2332 check_common_constraints();
2333 check_probeset_properties();
2335 allocate_bucket_tables( nInitialSize ? cds::beans::ceil2( nInitialSize ) : c_nDefaultInitialSize );
2341 free_bucket_tables();
2345 /// Inserts new node
2347 The function inserts \p val in the set if it does not contain
2348 an item with key equal to \p val.
2350 Returns \p true if \p val is placed into the set, \p false otherwise.
2352 bool insert( value_type& val )
2354 return insert( val, []( value_type& ) {} );
2357 /// Inserts new node
2359 The function allows to split creating of new item into two part:
2360 - create item with key only
2361 - insert new item into the set
2362 - if inserting is success, calls \p f functor to initialize value-field of \p val.
2364 The functor signature is:
2366 void func( value_type& val );
2368 where \p val is the item inserted.
2370 The user-defined functor is called only if the inserting is success.
2372 template <typename Func>
2373 bool insert( value_type& val, Func f )
2376 position arrPos[ c_nArity ];
2377 unsigned int nGoalTable;
2379 hashing( arrHash, val );
2380 node_type * pNode = node_traits::to_node_ptr( val );
2381 store_hash( pNode, arrHash );
2385 scoped_cell_lock guard( m_MutexPolicy, arrHash );
2387 if ( contains( arrPos, arrHash, val, key_predicate() ) != c_nUndefTable ) {
2388 m_Stat.onInsertFailed();
2392 for ( unsigned int i = 0; i < c_nArity; ++i ) {
2393 bucket_entry& refBucket = bucket( i, arrHash[i] );
2394 if ( refBucket.size() < m_nProbesetThreshold ) {
2395 refBucket.insert_after( arrPos[i].itPrev, pNode );
2398 m_Stat.onInsertSuccess();
2403 for ( unsigned int i = 0; i < c_nArity; ++i ) {
2404 bucket_entry& refBucket = bucket( i, arrHash[i] );
2405 if ( refBucket.size() < m_nProbesetSize ) {
2406 refBucket.insert_after( arrPos[i].itPrev, pNode );
2410 assert( refBucket.size() > 1 );
2411 copy_hash( arrHash, *node_traits::to_value_ptr( *refBucket.begin()) );
2417 m_Stat.onInsertResize();
2422 m_Stat.onInsertRelocate();
2423 if ( !relocate( nGoalTable, arrHash )) {
2424 m_Stat.onInsertRelocateFault();
2425 m_Stat.onInsertResize();
2429 m_Stat.onInsertSuccess();
2433 /// Ensures that the \p val exists in the set
2435 The operation performs inserting or changing data with lock-free manner.
2437 If the item \p val not found in the set, then \p val is inserted into the set.
2438 Otherwise, the functor \p func is called with item found.
2439 The functor signature is:
2441 void func( bool bNew, value_type& item, value_type& val );
2444 - \p bNew - \p true if the item has been inserted, \p false otherwise
2445 - \p item - item of the set
2446 - \p val - argument \p val passed into the \p ensure function
2447 If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
2448 refers to the same thing.
2450 The functor may change non-key fields of the \p item.
2452 Returns <tt> std::pair<bool, bool> </tt> where \p first is \p true if operation is successful,
2453 \p second is \p true if new item has been added or \p false if the item with \p key
2454 already is in the set.
2456 template <typename Func>
2457 std::pair<bool, bool> ensure( value_type& val, Func func )
2460 position arrPos[ c_nArity ];
2461 unsigned int nGoalTable;
2463 hashing( arrHash, val );
2464 node_type * pNode = node_traits::to_node_ptr( val );
2465 store_hash( pNode, arrHash );
2469 scoped_cell_lock guard( m_MutexPolicy, arrHash );
2471 unsigned int nTable = contains( arrPos, arrHash, val, key_predicate() );
2472 if ( nTable != c_nUndefTable ) {
2473 func( false, *node_traits::to_value_ptr( *arrPos[nTable].itFound ), val );
2474 m_Stat.onEnsureExist();
2475 return std::make_pair( true, false );
2478 node_type * pNode = node_traits::to_node_ptr( val );
2479 store_hash( pNode, arrHash );
2481 for ( unsigned int i = 0; i < c_nArity; ++i ) {
2482 bucket_entry& refBucket = bucket( i, arrHash[i] );
2483 if ( refBucket.size() < m_nProbesetThreshold ) {
2484 refBucket.insert_after( arrPos[i].itPrev, pNode );
2485 func( true, val, val );
2487 m_Stat.onEnsureSuccess();
2488 return std::make_pair( true, true );
2492 for ( unsigned int i = 0; i < c_nArity; ++i ) {
2493 bucket_entry& refBucket = bucket( i, arrHash[i] );
2494 if ( refBucket.size() < m_nProbesetSize ) {
2495 refBucket.insert_after( arrPos[i].itPrev, pNode );
2496 func( true, val, val );
2499 assert( refBucket.size() > 1 );
2500 copy_hash( arrHash, *node_traits::to_value_ptr( *refBucket.begin()) );
2506 m_Stat.onEnsureResize();
2511 m_Stat.onEnsureRelocate();
2512 if ( !relocate( nGoalTable, arrHash )) {
2513 m_Stat.onEnsureRelocateFault();
2514 m_Stat.onEnsureResize();
2518 m_Stat.onEnsureSuccess();
2519 return std::make_pair( true, true );
2522 /// Unlink the item \p val from the set
2524 The function searches the item \p val in the set and unlink it
2525 if it is found and is equal to \p val (here, the equality means that
2526 \p val belongs to the set: if \p item is an item found then
2527 unlink is successful iif <tt>&val == &item</tt>)
2529 The function returns \p true if success and \p false otherwise.
2531 bool unlink( value_type& val )
2534 hashing( arrHash, val );
2535 position arrPos[ c_nArity ];
2538 scoped_cell_lock guard( m_MutexPolicy, arrHash );
2540 unsigned int nTable = contains( arrPos, arrHash, val, key_predicate() );
2541 if ( nTable != c_nUndefTable && node_traits::to_value_ptr(*arrPos[nTable].itFound) == &val ) {
2542 bucket( nTable, arrHash[nTable]).remove( arrPos[nTable].itPrev, arrPos[nTable].itFound );
2544 m_Stat.onUnlinkSuccess();
2549 m_Stat.onUnlinkFailed();
2553 /// Deletes the item from the set
2554 /** \anchor cds_intrusive_CuckooSet_erase
2555 The function searches an item with key equal to \p val in the set,
2556 unlinks it from the set, and returns a pointer to unlinked item.
2558 If the item with key equal to \p val is not found the function return \p nullptr.
2560 Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
2562 template <typename Q>
2563 value_type * erase( Q const& val )
2565 return erase( val, [](value_type const&) {} );
2568 /// Deletes the item from the set using \p pred predicate for searching
2570 The function is an analog of \ref cds_intrusive_CuckooSet_erase "erase(Q const&)"
2571 but \p pred is used for key comparing.
2572 If cuckoo set is ordered, then \p Predicate should have the interface and semantics like \p std::less.
2573 If cuckoo set is unordered, then \p Predicate should have the interface and semantics like \p std::equal_to.
2574 \p Predicate must imply the same element order as the comparator used for building the set.
2576 template <typename Q, typename Predicate>
2577 value_type * erase_with( Q const& val, Predicate pred )
2580 return erase_( val, typename predicate_wrapper<Predicate>::type(), [](value_type const&) {} );
2583 /// Delete the item from the set
2584 /** \anchor cds_intrusive_CuckooSet_erase_func
2585 The function searches an item with key equal to \p val in the set,
2586 call \p f functor with item found, unlinks it from the set, and returns a pointer to unlinked item.
2588 The \p Func interface is
2591 void operator()( value_type const& item );
2595 If the item with key equal to \p val is not found the function return \p nullptr.
2597 Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
2599 template <typename Q, typename Func>
2600 value_type * erase( Q const& val, Func f )
2602 return erase_( val, key_predicate(), f );
2605 /// Deletes the item from the set using \p pred predicate for searching
2607 The function is an analog of \ref cds_intrusive_CuckooSet_erase_func "erase(Q const&, Func)"
2608 but \p pred is used for key comparing.
2609 If you use ordered cuckoo set, then \p Predicate should have the interface and semantics like \p std::less.
2610 If you use unordered cuckoo set, then \p Predicate should have the interface and semantics like \p std::equal_to.
2611 \p Predicate must imply the same element order as the comparator used for building the set.
2613 template <typename Q, typename Predicate, typename Func>
2614 value_type * erase_with( Q const& val, Predicate pred, Func f )
2617 return erase_( val, typename predicate_wrapper<Predicate>::type(), f );
2620 /// Find the key \p val
2621 /** \anchor cds_intrusive_CuckooSet_find_func
2622 The function searches the item with key equal to \p val and calls the functor \p f for item found.
2623 The interface of \p Func functor is:
2626 void operator()( value_type& item, Q& val );
2629 where \p item is the item found, \p val is the <tt>find</tt> function argument.
2631 The functor may change non-key fields of \p item.
2633 The \p val argument is non-const since it can be used as \p f functor destination i.e., the functor
2634 may modify both arguments.
2636 Note the hash functor specified for class \p Traits template parameter
2637 should accept a parameter of type \p Q that can be not the same as \p value_type.
2639 The function returns \p true if \p val is found, \p false otherwise.
2641 template <typename Q, typename Func>
2642 bool find( Q& val, Func f )
2644 return find_( val, key_predicate(), f );
2647 /// Find the key \p val using \p pred predicate for comparing
2649 The function is an analog of \ref cds_intrusive_CuckooSet_find_func "find(Q&, Func)"
2650 but \p pred is used for key comparison.
2651 If you use ordered cuckoo set, then \p Predicate should have the interface and semantics like \p std::less.
2652 If you use unordered cuckoo set, then \p Predicate should have the interface and semantics like \p std::equal_to.
2653 \p pred must imply the same element order as the comparator used for building the set.
2655 template <typename Q, typename Predicate, typename Func>
2656 bool find_with( Q& val, Predicate pred, Func f )
2659 return find_( val, typename predicate_wrapper<Predicate>::type(), f );
2662 /// Find the key \p val
2663 /** \anchor cds_intrusive_CuckooSet_find_cfunc
2664 The function searches the item with key equal to \p val and calls the functor \p f for item found.
2665 The interface of \p Func functor is:
2668 void operator()( value_type& item, Q const& val );
2671 where \p item is the item found, \p val is the <tt>find</tt> function argument.
2673 The functor may change non-key fields of \p item.
2675 The \p val argument is non-const since it can be used as \p f functor destination i.e., the functor
2676 may modify both arguments.
2678 The function returns \p true if \p val is found, \p false otherwise.
2680 template <typename Q, typename Func>
2681 bool find( Q const& val, Func f )
2683 return find_( val, key_predicate(), f );
2686 /// Find the key \p val using \p pred predicate for comparing
2688 The function is an analog of \ref cds_intrusive_CuckooSet_find_cfunc "find(Q const&, Func)"
2689 but \p pred is used for key comparison.
2690 If you use ordered cuckoo set, then \p Predicate should have the interface and semantics like \p std::less.
2691 If you use unordered cuckoo set, then \p Predicate should have the interface and semantics like \p std::equal_to.
2692 \p pred must imply the same element order as the comparator used for building the set.
2694 template <typename Q, typename Predicate, typename Func>
2695 bool find_with( Q const& val, Predicate pred, Func f )
2698 return find_( val, typename predicate_wrapper<Predicate>::type(), f );
2701 /// Find the key \p val
2702 /** \anchor cds_intrusive_CuckooSet_find_val
2703 The function searches the item with key equal to \p val
2704 and returns \p true if it is found, and \p false otherwise.
2706 Note the hash functor specified for class \p Traits template parameter
2707 should accept a parameter of type \p Q that can be not the same as \p value_type.
2709 template <typename Q>
2710 bool find( Q const& val )
2712 return find( val, [](value_type&, Q const& ) {} );
2715 /// Find the key \p val using \p pred predicate for comparing
2717 The function is an analog of \ref cds_intrusive_CuckooSet_find_val "find(Q const&)"
2718 but \p pred is used for key comparison.
2719 If you use ordered cuckoo set, then \p Predicate should have the interface and semantics like \p std::less.
2720 If you use unordered cuckoo set, then \p Predicate should have the interface and semantics like \p std::equal_to.
2721 \p pred must imply the same element order as the comparator used for building the set.
2723 template <typename Q, typename Predicate>
2724 bool find_with( Q const& val, Predicate pred )
2727 return find_with( val, typename predicate_wrapper<Predicate>::type(), [](value_type& , Q const& ) {} );
2732 The function unlinks all items from the set.
2733 For any item \ref disposer is called
2737 clear_and_dispose( disposer() );
2740 /// Clears the set and calls \p disposer for each item
2742 The function unlinks all items from the set calling \p disposer for each item.
2743 \p Disposer functor interface is:
2746 void operator()( value_type * p );
2750 The \ref disposer specified in \p Traits traits is not called.
2752 template <typename Disposer>
2753 void clear_and_dispose( Disposer oDisposer )
2755 // locks entire array
2756 scoped_full_lock sl( m_MutexPolicy );
2758 for ( unsigned int i = 0; i < c_nArity; ++i ) {
2759 bucket_entry * pEntry = m_BucketTable[i];
2760 bucket_entry * pEnd = pEntry + m_nBucketMask + 1;
2761 for ( ; pEntry != pEnd ; ++pEntry ) {
2762 pEntry->clear( [&oDisposer]( node_type * pNode ){ oDisposer( node_traits::to_value_ptr( pNode )) ; } );
2765 m_ItemCounter.reset();
2768 /// Checks if the set is empty
2770 Emptiness is checked by item counting: if item count is zero then the set is empty.
2777 /// Returns item count in the set
2780 return m_ItemCounter;
2783 /// Returns the size of hash table
2785 The hash table size is non-constant and can be increased via resizing.
2787 size_t bucket_count() const
2789 return m_nBucketMask + 1;
2792 /// Returns lock array size
2793 size_t lock_count() const
2795 return m_MutexPolicy.lock_count();
2798 /// Returns const reference to internal statistics
2799 stat const& statistics() const
2804 /// Returns const reference to mutex policy internal statistics
2805 typename mutex_policy::statistics_type const& mutex_policy_statistics() const
2807 return m_MutexPolicy.statistics();
2810 }} // namespace cds::intrusive
2812 #endif // #ifndef CDSLIB_INTRUSIVE_CUCKOO_SET_H