3 #ifndef __CDS_INTRUSIVE_CUCKOO_SET_H
4 #define __CDS_INTRUSIVE_CUCKOO_SET_H
9 #include <cds/intrusive/base.h>
10 #include <cds/opt/compare.h>
11 #include <cds/opt/hash.h>
12 #include <cds/lock/array.h>
14 #include <cds/os/thread.h>
15 #include <cds/details/functor_wrapper.h>
16 #include <cds/lock/spinlock.h>
19 namespace cds { namespace intrusive {
21 /// CuckooSet-related definitions
24 /// Option to define probeset type
26 The option specifies probeset type for the CuckooSet.
28 - \p cds::intrusive::cuckoo::list - the probeset is a single-linked list.
29 The node contains pointer to next node in probeset.
30 - \p cds::intrusive::cuckoo::vector<Capacity> - the probeset is a vector
31 with constant-size \p Capacity where \p Capacity is an <tt>unsigned int</tt> constant.
32 The node does not contain any auxiliary data.
34 template <typename Type>
38 template <typename Base>
39 struct pack: public Base {
40 typedef Type probeset_type;
45 /// Option specifying whether to store hash values in the node
47 This option reserves additional space in the hook to store the hash value of the object once it's introduced in the container.
48 When this option is used, the unordered container will store the calculated hash value in the hook and rehashing operations won't need
49 to recalculate the hash of the value. This option will improve the performance of unordered containers
50 when rehashing is frequent or hashing the value is a slow operation
52 The \p Count template parameter defines the size of hash array. Remember that cuckoo hashing implies at least two
55 Possible values of \p Count:
56 - 0 - no hash storing in the node
57 - greater that 1 - store hash values.
59 Value 1 is deprecated.
61 template <unsigned int Count>
65 template <typename Base>
66 struct pack: public Base {
67 static unsigned int const store_hash = Count;
74 // Probeset type placeholders
75 struct list_probeset_class;
76 struct vector_probeset_class;
80 // Probeset type declarations.
82 template <unsigned int Capacity>
85 static unsigned int const c_nCapacity = Capacity;
92 - \p ProbesetType - type of probeset. Can be \p cds::intrusive::cuckoo::list
93 or \p cds::intrusive::cuckoo::vector<Capacity>.
94 - \p StoreHashCount - constant that defines whether to store node hash values.
95 See cuckoo::store_hash option for explanation
96 - Tag - a tag used to distinguish between different implementation when two or more
97 \p node is needed in single struct.
99 template <typename ProbesetType = cuckoo::list, unsigned int StoreHashCount = 0, typename Tag = opt::none>
101 #ifdef CDS_DOXYGEN_INVOKED
103 typedef ProbesetType probeset_type ; ///< Probeset type
104 typedef Tag tag ; ///< Tag
105 static unsigned int const hash_array_size = StoreHashCount ; ///< The size of hash array
111 template <typename Tag>
112 struct node< cuckoo::list, 0, Tag>
114 typedef list_probeset_class probeset_class;
115 typedef cuckoo::list probeset_type;
117 static unsigned int const hash_array_size = 0;
118 static unsigned int const probeset_size = 0;
122 CDS_CONSTEXPR node() CDS_NOEXCEPT
126 void store_hash( size_t * )
129 size_t * get_hash() const
131 // This node type does not store hash values!!!
142 template <unsigned int StoreHashCount, typename Tag>
143 struct node< cuckoo::list, StoreHashCount, Tag>
145 typedef list_probeset_class probeset_class;
146 typedef cuckoo::list probeset_type;
148 static unsigned int const hash_array_size = StoreHashCount;
149 static unsigned int const probeset_size = 0;
152 size_t m_arrHash[ hash_array_size ];
157 memset( m_arrHash, 0, sizeof(m_arrHash));
160 void store_hash( size_t * pHashes )
162 memcpy( m_arrHash, pHashes, hash_array_size );
165 size_t * get_hash() const
167 return const_cast<size_t *>( m_arrHash );
177 template <unsigned int VectorSize, typename Tag>
178 struct node< cuckoo::vector<VectorSize>, 0, Tag>
180 typedef vector_probeset_class probeset_class;
181 typedef cuckoo::vector<VectorSize> probeset_type;
183 static unsigned int const hash_array_size = 0;
184 static unsigned int const probeset_size = probeset_type::c_nCapacity;
189 void store_hash( size_t * )
192 size_t * get_hash() const
194 // This node type does not store hash values!!!
203 template <unsigned int VectorSize, unsigned int StoreHashCount, typename Tag>
204 struct node< cuckoo::vector<VectorSize>, StoreHashCount, Tag>
206 typedef vector_probeset_class probeset_class;
207 typedef cuckoo::vector<VectorSize> probeset_type;
209 static unsigned int const hash_array_size = StoreHashCount;
210 static unsigned int const probeset_size = probeset_type::c_nCapacity;
212 size_t m_arrHash[ hash_array_size ];
216 memset( m_arrHash, 0, sizeof(m_arrHash));
219 void store_hash( size_t * pHashes )
221 memcpy( m_arrHash, pHashes, hash_array_size );
224 size_t * get_hash() const
226 return const_cast<size_t *>( m_arrHash );
236 struct default_hook {
237 typedef cuckoo::list probeset_type;
238 static unsigned int const store_hash = 0;
239 typedef opt::none tag;
242 template < typename HookType, CDS_DECL_OPTIONS3>
245 typedef typename opt::make_options< default_hook, CDS_OPTIONS3>::type options;
247 typedef typename options::probeset_type probeset_type;
248 typedef typename options::tag tag;
249 static unsigned int const store_hash = options::store_hash;
251 typedef node<probeset_type, store_hash, tag> node_type;
253 typedef HookType hook_type;
260 - cuckoo::probeset_type - probeset type. Defaul is \p cuckoo::list
261 - cuckoo::store_hash - store hash values in the node or not. Default is 0 (no storing)
262 - opt::tag - tag to distinguish different nodes in one struct. Default is opt::none
264 template < CDS_DECL_OPTIONS3 >
265 struct base_hook: public hook< opt::base_hook_tag, CDS_OPTIONS3 >
270 \p MemberOffset defines offset in bytes of \ref node member into your structure.
271 Use \p offsetof macro to define \p MemberOffset
274 - cuckoo::probeset_type - probeset type. Defaul is \p cuckoo::list
275 - cuckoo::store_hash - store hash values in the node or not. Default is 0 (no storing)
276 - opt::tag - tag to distinguish different nodes in one struct. Default is opt::none
278 template < size_t MemberOffset, CDS_DECL_OPTIONS3 >
279 struct member_hook: public hook< opt::member_hook_tag, CDS_OPTIONS3 >
282 static const size_t c_nMemberOffset = MemberOffset;
288 \p NodeTraits defines type traits for node.
289 See \ref node_traits for \p NodeTraits interface description
292 - cuckoo::probeset_type - probeset type. Defaul is \p cuckoo::list
293 - cuckoo::store_hash - store hash values in the node or not. Default is 0 (no storing)
294 - opt::tag - tag to distinguish different nodes in one struct. Default is opt::none
296 template <typename NodeTraits, CDS_DECL_OPTIONS3 >
297 struct traits_hook: public hook< opt::traits_hook_tag, CDS_OPTIONS3 >
300 typedef NodeTraits node_traits;
304 /// Internal statistics for \ref striping mutex policy
305 struct striping_stat {
306 typedef cds::atomicity::event_counter counter_type; ///< Counter type
308 counter_type m_nCellLockCount ; ///< Count of obtaining cell lock
309 counter_type m_nCellTryLockCount ; ///< Count of cell \p try_lock attempts
310 counter_type m_nFullLockCount ; ///< Count of obtaining full lock
311 counter_type m_nResizeLockCount ; ///< Count of obtaining resize lock
312 counter_type m_nResizeCount ; ///< Count of resize event
315 void onCellLock() { ++m_nCellLockCount; }
316 void onCellTryLock() { ++m_nCellTryLockCount; }
317 void onFullLock() { ++m_nFullLockCount; }
318 void onResizeLock() { ++m_nResizeLockCount; }
319 void onResize() { ++m_nResizeCount; }
323 /// Dummy internal statistics for \ref striping mutex policy
324 struct empty_striping_stat {
326 void onCellLock() const {}
327 void onCellTryLock() const {}
328 void onFullLock() const {}
329 void onResizeLock() const {}
330 void onResize() const {}
334 /// Lock striping concurrent access policy
336 This is one of available opt::mutex_policy option type for CuckooSet
338 Lock striping is very simple technique.
339 The cuckoo set consists of the bucket tables and the array of locks.
340 There is single lock array for each bucket table, at least, the count of bucket table is 2.
341 Initially, the capacity of lock array and each bucket table is the same.
342 When set is resized, bucket table capacity will be doubled but lock array will not.
343 The lock \p i protects each bucket \p j, where <tt> j = i mod L </tt>,
344 where \p L - the size of lock array.
346 The policy contains an internal array of \p RecursiveLock locks.
349 - \p RecursiveLock - the type of recursive mutex. The default is \p std::recursive_mutex. The mutex type should be default-constructible.
350 Note that a recursive spin-lock is not suitable for lock striping for performance reason.
351 - \p Arity - unsigned int constant that specifies an arity. The arity is the count of hash functors, i.e., the
352 count of lock arrays. Default value is 2.
353 - \p Alloc - allocator type used for lock array memory allocation. Default is \p CDS_DEFAULT_ALLOCATOR.
354 - \p Stat - internal statistics type. Note that this template argument is automatically selected by \ref CuckooSet
355 class according to its \p opt::stat option.
358 class RecursiveLock = std::recursive_mutex,
359 unsigned int Arity = 2,
360 class Alloc = CDS_DEFAULT_ALLOCATOR,
361 class Stat = empty_striping_stat
366 typedef RecursiveLock lock_type ; ///< lock type
367 typedef Alloc allocator_type ; ///< allocator type
368 static unsigned int const c_nArity = Arity ; ///< the arity
369 typedef Stat statistics_type ; ///< Internal statistics type (\ref striping_stat or \ref empty_striping_stat)
372 typedef striping_stat real_stat;
373 typedef empty_striping_stat empty_stat;
375 template <typename Stat2>
376 struct rebind_statistics {
377 typedef striping<lock_type, c_nArity, allocator_type, Stat2> other;
381 typedef cds::lock::array< lock_type, cds::lock::pow2_select_policy, allocator_type > lock_array_type ; ///< lock array type
385 class lock_array: public lock_array_type
389 lock_array(): lock_array_type( typename lock_array_type::select_cell_policy(2) ) {}
392 lock_array( size_t nCapacity ): lock_array_type( nCapacity, typename lock_array_type::select_cell_policy(nCapacity) ) {}
395 class scoped_lock: public cds::lock::scoped_lock< lock_array_type >
397 typedef cds::lock::scoped_lock< lock_array_type > base_class;
399 scoped_lock( lock_array& arrLock, size_t nHash ): base_class( arrLock, nHash ) {}
405 lock_array m_Locks[c_nArity] ; ///< array of lock_array_type
406 statistics_type m_Stat ; ///< internal statistics
411 class scoped_cell_lock {
412 lock_type * m_guard[c_nArity];
415 scoped_cell_lock( striping& policy, size_t const* arrHash )
417 for ( unsigned int i = 0; i < c_nArity; ++i ) {
418 m_guard[i] = &( policy.m_Locks[i].at( policy.m_Locks[i].lock( arrHash[i] )));
420 policy.m_Stat.onCellLock();
425 for ( unsigned int i = 0; i < c_nArity; ++i )
426 m_guard[i]->unlock();
430 class scoped_cell_trylock
432 typedef typename lock_array_type::lock_type lock_type;
434 lock_type * m_guard[c_nArity];
438 scoped_cell_trylock( striping& policy, size_t const* arrHash )
440 size_t nCell = policy.m_Locks[0].try_lock( arrHash[0] );
441 m_bLocked = nCell != lock_array_type::c_nUnspecifiedCell;
443 m_guard[0] = &(policy.m_Locks[0].at(nCell));
444 for ( unsigned int i = 1; i < c_nArity; ++i ) {
445 m_guard[i] = &( policy.m_Locks[i].at( policy.m_Locks[i].lock( arrHash[i] )) );
449 std::fill( m_guard, m_guard + c_nArity, nullptr );
451 policy.m_Stat.onCellTryLock();
453 ~scoped_cell_trylock()
456 for ( unsigned int i = 0; i < c_nArity; ++i )
457 m_guard[i]->unlock();
467 class scoped_full_lock {
468 cds::lock::scoped_lock< lock_array_type > m_guard;
470 scoped_full_lock( striping& policy )
471 : m_guard( policy.m_Locks[0] )
473 policy.m_Stat.onFullLock();
476 /// Ctor for scoped_resize_lock - no statistics is incremented
477 scoped_full_lock( striping& policy, bool )
478 : m_guard( policy.m_Locks[0] )
482 class scoped_resize_lock: public scoped_full_lock {
484 scoped_resize_lock( striping& policy )
485 : scoped_full_lock( policy, false )
487 policy.m_Stat.onResizeLock();
495 size_t nLockCount ///< The size of lock array. Must be power of two.
498 // Trick: initialize the array of locks
499 for ( unsigned int i = 0; i < c_nArity; ++i ) {
500 lock_array * pArr = m_Locks + i;
501 pArr->lock_array::~lock_array();
502 new ( pArr ) lock_array( nLockCount );
506 /// Returns lock array size
508 Lock array size is unchanged during \p striping object lifetime
510 size_t lock_count() const
512 return m_Locks[0].size();
516 void resize( size_t )
522 /// Returns the arity of striping mutex policy
523 CDS_CONSTEXPR unsigned int arity() const CDS_NOEXCEPT
528 /// Returns internal statistics
529 statistics_type const& statistics() const
535 /// Internal statistics for \ref refinable mutex policy
536 struct refinable_stat {
537 typedef cds::atomicity::event_counter counter_type ; ///< Counter type
539 counter_type m_nCellLockCount ; ///< Count of obtaining cell lock
540 counter_type m_nCellLockWaitResizing ; ///< Count of loop iteration to wait for resizing
541 counter_type m_nCellLockArrayChanged ; ///< Count of event "Lock array has been changed when obtaining cell lock"
542 counter_type m_nCellLockFailed ; ///< Count of event "Cell lock failed because of the array is owned by other thread"
544 counter_type m_nSecondCellLockCount ; ///< Count of obtaining cell lock when another cell is already locked
545 counter_type m_nSecondCellLockFailed ; ///< Count of unsuccess obtaining cell lock when another cell is already locked
547 counter_type m_nFullLockCount ; ///< Count of obtaining full lock
548 counter_type m_nFullLockIter ; ///< Count of unsuccessfull iteration to obtain full lock
550 counter_type m_nResizeLockCount ; ///< Count of obtaining resize lock
551 counter_type m_nResizeLockIter ; ///< Count of unsuccessfull iteration to obtain resize lock
552 counter_type m_nResizeLockArrayChanged; ///< Count of event "Lock array has been changed when obtaining resize lock"
553 counter_type m_nResizeCount ; ///< Count of resize event
556 void onCellLock() { ++m_nCellLockCount; }
557 void onCellWaitResizing() { ++m_nCellLockWaitResizing; }
558 void onCellArrayChanged() { ++m_nCellLockArrayChanged; }
559 void onCellLockFailed() { ++m_nCellLockFailed; }
560 void onSecondCellLock() { ++m_nSecondCellLockCount; }
561 void onSecondCellLockFailed() { ++m_nSecondCellLockFailed; }
562 void onFullLock() { ++m_nFullLockCount; }
563 void onFullLockIter() { ++m_nFullLockIter; }
564 void onResizeLock() { ++m_nResizeLockCount; }
565 void onResizeLockIter() { ++m_nResizeLockIter; }
566 void onResizeLockArrayChanged() { ++m_nResizeLockArrayChanged; }
567 void onResize() { ++m_nResizeCount; }
571 /// Dummy internal statistics for \ref refinable mutex policy
572 struct empty_refinable_stat {
574 void onCellLock() const {}
575 void onCellWaitResizing() const {}
576 void onCellArrayChanged() const {}
577 void onCellLockFailed() const {}
578 void onSecondCellLock() const {}
579 void onSecondCellLockFailed() const {}
580 void onFullLock() const {}
581 void onFullLockIter() const {}
582 void onResizeLock() const {}
583 void onResizeLockIter() const {}
584 void onResizeLockArrayChanged() const {}
585 void onResize() const {}
589 /// Refinable concurrent access policy
591 This is one of available opt::mutex_policy option type for CuckooSet
593 Refining is like a striping technique (see cuckoo::striping)
594 but it allows growing the size of lock array when resizing the hash table.
595 So, the sizes of hash table and lock array are equal.
598 - \p RecursiveLock - the type of mutex. Reentrant (recursive) mutex is required.
599 The default is \p std::recursive_mutex. The mutex type should be default-constructible.
600 - \p Arity - unsigned int constant that specifies an arity. The arity is the count of hash functors, i.e., the
601 count of lock arrays. Default value is 2.
602 - \p BackOff - back-off strategy. Default is cds::backoff::yield
603 - \p Alloc - allocator type used for lock array memory allocation. Default is \p CDS_DEFAULT_ALLOCATOR.
604 - \p Stat - internal statistics type. Note that this template argument is automatically selected by \ref CuckooSet
605 class according to its \p opt::stat option.
608 class RecursiveLock = std::recursive_mutex,
609 unsigned int Arity = 2,
610 typename BackOff = cds::backoff::yield,
611 class Alloc = CDS_DEFAULT_ALLOCATOR,
612 class Stat = empty_refinable_stat
617 typedef RecursiveLock lock_type ; ///< lock type
618 typedef Alloc allocator_type ; ///< allocator type
619 typedef BackOff back_off ; ///< back-off strategy
620 typedef Stat statistics_type ; ///< internal statistics type
621 static unsigned int const c_nArity = Arity; ///< the arity
624 typedef refinable_stat real_stat;
625 typedef empty_refinable_stat empty_stat;
627 template <typename Stat2>
628 struct rebind_statistics {
629 typedef refinable< lock_type, c_nArity, back_off, allocator_type, Stat2> other;
635 typedef cds::lock::trivial_select_policy lock_selection_policy;
637 class lock_array_type
638 : public cds::lock::array< lock_type, lock_selection_policy, allocator_type >
639 , public std::enable_shared_from_this< lock_array_type >
641 typedef cds::lock::array< lock_type, lock_selection_policy, allocator_type > lock_array_base;
643 lock_array_type( size_t nCapacity )
644 : lock_array_base( nCapacity )
647 typedef std::shared_ptr< lock_array_type > lock_array_ptr;
648 typedef cds::details::Allocator< lock_array_type, allocator_type > lock_array_allocator;
650 typedef unsigned long long owner_t;
651 typedef cds::OS::ThreadId threadId_t;
653 typedef cds::lock::Spin spinlock_type;
654 typedef cds::lock::scoped_lock< spinlock_type > scoped_spinlock;
659 static owner_t const c_nOwnerMask = (((owner_t) 1) << (sizeof(owner_t) * 8 - 1)) - 1;
661 CDS_ATOMIC::atomic< owner_t > m_Owner ; ///< owner mark (thread id + boolean flag)
662 CDS_ATOMIC::atomic<size_t> m_nCapacity ; ///< lock array capacity
663 lock_array_ptr m_arrLocks[ c_nArity ] ; ///< Lock array. The capacity of array is specified in constructor.
664 spinlock_type m_access ; ///< access to m_arrLocks
665 statistics_type m_Stat ; ///< internal statistics
670 struct lock_array_disposer {
671 void operator()( lock_array_type * pArr )
673 lock_array_allocator().Delete( pArr );
677 lock_array_ptr create_lock_array( size_t nCapacity )
679 return lock_array_ptr( lock_array_allocator().New( nCapacity ), lock_array_disposer() );
682 void acquire( size_t const * arrHash, lock_array_ptr * pLockArr, lock_type ** parrLock )
684 owner_t me = (owner_t) cds::OS::getCurrentThreadId();
691 scoped_spinlock sl(m_access);
692 for ( unsigned int i = 0; i < c_nArity; ++i )
693 pLockArr[i] = m_arrLocks[i];
696 // wait while resizing
698 who = m_Owner.load( CDS_ATOMIC::memory_order_acquire );
699 if ( !( who & 1 ) || (who >> 1) == (me & c_nOwnerMask) )
702 m_Stat.onCellWaitResizing();
705 if ( pLockArr[0] != m_arrLocks[0] ) {
706 m_Stat.onCellArrayChanged();
710 size_t const nMask = pLockArr[0]->size() - 1;
711 assert( cds::beans::is_power2( nMask + 1 ));
713 for ( unsigned int i = 0; i < c_nArity; ++i ) {
714 parrLock[i] = &( pLockArr[i]->at( arrHash[i] & nMask ));
718 who = m_Owner.load( CDS_ATOMIC::memory_order_acquire );
719 if ( ( !(who & 1) || (who >> 1) == (me & c_nOwnerMask) ) && m_arrLocks[0] == pLockArr[0] ) {
724 for ( unsigned int i = 0; i < c_nArity; ++i ) {
725 parrLock[i]->unlock();
728 m_Stat.onCellLockFailed();
731 // clears pLockArr can lead to calling dtor for each item of pLockArr[i] that may be a heavy-weighted operation
732 // (each pLockArr[i] is a shared pointer to array of a ton of mutexes)
733 // It is better to do this before the next loop iteration where we will use spin-locked assignment to pLockArr
734 // Destructing a lot of mutexes under spin-lock is a bad solution
735 for ( unsigned int i = 0; i < c_nArity; ++i )
740 bool try_second_acquire( size_t const * arrHash, lock_type ** parrLock )
742 // It is assumed that the current thread already has a lock
743 // and requires a second lock for other hash
745 size_t const nMask = m_nCapacity.load(CDS_ATOMIC::memory_order_acquire) - 1;
746 size_t nCell = m_arrLocks[0]->try_lock( arrHash[0] & nMask);
747 if ( nCell == lock_array_type::c_nUnspecifiedCell ) {
748 m_Stat.onSecondCellLockFailed();
751 parrLock[0] = &(m_arrLocks[0]->at(nCell));
753 for ( unsigned int i = 1; i < c_nArity; ++i ) {
754 parrLock[i] = &( m_arrLocks[i]->at( m_arrLocks[i]->lock( arrHash[i] & nMask)) );
757 m_Stat.onSecondCellLock();
763 owner_t me = (owner_t) cds::OS::getCurrentThreadId();
768 if ( m_Owner.compare_exchange_strong( ownNull, (me << 1) | 1, CDS_ATOMIC::memory_order_acq_rel, CDS_ATOMIC::memory_order_relaxed )) {
769 m_arrLocks[0]->lock_all();
775 m_Stat.onFullLockIter();
781 m_arrLocks[0]->unlock_all();
782 m_Owner.store( 0, CDS_ATOMIC::memory_order_release );
785 void acquire_resize( lock_array_ptr * pOldLocks )
787 owner_t me = (owner_t) cds::OS::getCurrentThreadId();
791 scoped_spinlock sl(m_access);
792 for ( unsigned int i = 0; i < c_nArity; ++i )
793 pOldLocks[i] = m_arrLocks[i];
798 if ( m_Owner.compare_exchange_strong( ownNull, (me << 1) | 1, CDS_ATOMIC::memory_order_acq_rel, CDS_ATOMIC::memory_order_relaxed )) {
799 if ( pOldLocks[0] != m_arrLocks[0] ) {
800 m_Owner.store( 0, CDS_ATOMIC::memory_order_release );
801 m_Stat.onResizeLockArrayChanged();
804 pOldLocks[0]->lock_all();
805 m_Stat.onResizeLock();
810 m_Stat.onResizeLockIter();
812 // clears pOldLocks can lead to calling dtor for each item of pOldLocks[i] that may be a heavy-weighted operation
813 // (each pOldLocks[i] is a shared pointer to array of a ton of mutexes)
814 // It is better to do this before the next loop iteration where we will use spin-locked assignment to pOldLocks
815 // Destructing a lot of mutexes under spin-lock is a bad solution
816 for ( unsigned int i = 0; i < c_nArity; ++i )
817 pOldLocks[i].reset();
821 void release_resize( lock_array_ptr * pOldLocks )
823 m_Owner.store( 0, CDS_ATOMIC::memory_order_release );
824 pOldLocks[0]->unlock_all();
830 class scoped_cell_lock {
831 lock_type * m_arrLock[ c_nArity ];
832 lock_array_ptr m_arrLockArr[ c_nArity ];
835 scoped_cell_lock( refinable& policy, size_t const* arrHash )
837 policy.acquire( arrHash, m_arrLockArr, m_arrLock );
842 for ( unsigned int i = 0; i < c_nArity; ++i )
843 m_arrLock[i]->unlock();
847 class scoped_cell_trylock {
848 lock_type * m_arrLock[ c_nArity ];
852 scoped_cell_trylock( refinable& policy, size_t const* arrHash )
854 m_bLocked = policy.try_second_acquire( arrHash, m_arrLock );
857 ~scoped_cell_trylock()
860 for ( unsigned int i = 0; i < c_nArity; ++i )
861 m_arrLock[i]->unlock();
871 class scoped_full_lock {
874 scoped_full_lock( refinable& policy )
877 policy.acquire_all();
881 m_policy.release_all();
885 class scoped_resize_lock
888 lock_array_ptr m_arrLocks[ c_nArity ];
890 scoped_resize_lock( refinable& policy )
893 policy.acquire_resize( m_arrLocks );
895 ~scoped_resize_lock()
897 m_policy.release_resize( m_arrLocks );
905 size_t nLockCount ///< The size of lock array. Must be power of two.
907 , m_nCapacity( nLockCount )
909 assert( cds::beans::is_power2( nLockCount ));
910 for ( unsigned int i = 0; i < c_nArity; ++i )
911 m_arrLocks[i] = create_lock_array( nLockCount );
915 void resize( size_t nCapacity )
917 lock_array_ptr pNew[ c_nArity ];
918 for ( unsigned int i = 0; i < c_nArity; ++i )
919 pNew[i] = create_lock_array( nCapacity );
922 // Assignment m_arrLocks[i] = pNew[i] may call heavy-weighted dtor for each item of m_arrLocks
923 // that is unacceptable under spin-lock
924 // So, we store copy of m_arrLocks in pOld
925 lock_array_ptr pOld[ c_nArity ];
926 for ( unsigned int i = 0; i < c_nArity; ++i )
927 pOld[i] = m_arrLocks[i];
929 // m_arrLocks assignment will not lead to calling dtor of each item of m_arrLocks
930 // since copy of m_arrLocks locates in pOld and assignment will not be too painful for spin-lock
934 scoped_spinlock sl(m_access);
935 for ( unsigned int i = 0; i < c_nArity; ++i )
936 m_arrLocks[i] = pNew[i];
938 m_nCapacity.store( nCapacity, CDS_ATOMIC::memory_order_release );
944 /// Returns lock array size
946 Lock array size is not a constant for \p refinable policy and can be changed when the set is resized.
948 size_t lock_count() const
950 return m_nCapacity.load(CDS_ATOMIC::memory_order_relaxed);
953 /// Returns the arity of \p refinable mutex policy
954 CDS_CONSTEXPR unsigned int arity() const CDS_NOEXCEPT
959 /// Returns internal statistics
960 statistics_type const& statistics() const
966 /// CuckooSet internal statistics
968 typedef cds::atomicity::event_counter counter_type ; ///< Counter type
970 counter_type m_nRelocateCallCount ; ///< Count of \p relocate function call
971 counter_type m_nRelocateRoundCount ; ///< Count of attempts to relocate items
972 counter_type m_nFalseRelocateCount ; ///< Count of unneeded attempts of \p relocate call
973 counter_type m_nSuccessRelocateCount ; ///< Count of successfull item relocating
974 counter_type m_nRelocateAboveThresholdCount; ///< Count of item relocating above probeset threshold
975 counter_type m_nFailedRelocateCount ; ///< Count of failed relocation attemp (when all probeset is full)
977 counter_type m_nResizeCallCount ; ///< Count of \p resize function call
978 counter_type m_nFalseResizeCount ; ///< Count of false \p resize function call (when other thread has been resized the set)
979 counter_type m_nResizeSuccessNodeMove; ///< Count of successfull node moving when resizing
980 counter_type m_nResizeRelocateCall ; ///< Count of \p relocate function call from \p resize function
982 counter_type m_nInsertSuccess ; ///< Count of successfull \p insert function call
983 counter_type m_nInsertFailed ; ///< Count of failed \p insert function call
984 counter_type m_nInsertResizeCount ; ///< Count of \p resize function call from \p insert
985 counter_type m_nInsertRelocateCount ; ///< Count of \p relocate function call from \p insert
986 counter_type m_nInsertRelocateFault ; ///< Count of failed \p relocate function call from \p insert
988 counter_type m_nEnsureExistCount ; ///< Count of call \p ensure function for existing node
989 counter_type m_nEnsureSuccessCount ; ///< Count of successfull \p insert function call for new node
990 counter_type m_nEnsureResizeCount ; ///< Count of \p resize function call from \p ensure
991 counter_type m_nEnsureRelocateCount ; ///< Count of \p relocate function call from \p ensure
992 counter_type m_nEnsureRelocateFault ; ///< Count of failed \p relocate function call from \p ensure
994 counter_type m_nUnlinkSuccess ; ///< Count of success \p unlink function call
995 counter_type m_nUnlinkFailed ; ///< Count of failed \p unlink function call
997 counter_type m_nEraseSuccess ; ///< Count of success \p erase function call
998 counter_type m_nEraseFailed ; ///< Count of failed \p erase function call
1000 counter_type m_nFindSuccess ; ///< Count of success \p find function call
1001 counter_type m_nFindFailed ; ///< Count of failed \p find function call
1003 counter_type m_nFindEqualSuccess ; ///< Count of success \p find_equal function call
1004 counter_type m_nFindEqualFailed ; ///< Count of failed \p find_equal function call
1006 counter_type m_nFindWithSuccess ; ///< Count of success \p find_with function call
1007 counter_type m_nFindWithFailed ; ///< Count of failed \p find_with function call
1010 void onRelocateCall() { ++m_nRelocateCallCount; }
1011 void onRelocateRound() { ++m_nRelocateRoundCount; }
1012 void onFalseRelocateRound() { ++m_nFalseRelocateCount; }
1013 void onSuccessRelocateRound(){ ++m_nSuccessRelocateCount; }
1014 void onRelocateAboveThresholdRound() { ++m_nRelocateAboveThresholdCount; }
1015 void onFailedRelocate() { ++m_nFailedRelocateCount; }
1017 void onResizeCall() { ++m_nResizeCallCount; }
1018 void onFalseResizeCall() { ++m_nFalseResizeCount; }
1019 void onResizeSuccessMove() { ++m_nResizeSuccessNodeMove; }
1020 void onResizeRelocateCall() { ++m_nResizeRelocateCall; }
1022 void onInsertSuccess() { ++m_nInsertSuccess; }
1023 void onInsertFailed() { ++m_nInsertFailed; }
1024 void onInsertResize() { ++m_nInsertResizeCount; }
1025 void onInsertRelocate() { ++m_nInsertRelocateCount; }
1026 void onInsertRelocateFault() { ++m_nInsertRelocateFault; }
1028 void onEnsureExist() { ++m_nEnsureExistCount; }
1029 void onEnsureSuccess() { ++m_nEnsureSuccessCount; }
1030 void onEnsureResize() { ++m_nEnsureResizeCount; }
1031 void onEnsureRelocate() { ++m_nEnsureRelocateCount; }
1032 void onEnsureRelocateFault() { ++m_nEnsureRelocateFault; }
1034 void onUnlinkSuccess() { ++m_nUnlinkSuccess; }
1035 void onUnlinkFailed() { ++m_nUnlinkFailed; }
1037 void onEraseSuccess() { ++m_nEraseSuccess; }
1038 void onEraseFailed() { ++m_nEraseFailed; }
1040 void onFindSuccess() { ++m_nFindSuccess; }
1041 void onFindFailed() { ++m_nFindFailed; }
1043 void onFindWithSuccess() { ++m_nFindWithSuccess; }
1044 void onFindWithFailed() { ++m_nFindWithFailed; }
1048 /// CuckooSet empty internal statistics
1051 void onRelocateCall() const {}
1052 void onRelocateRound() const {}
1053 void onFalseRelocateRound() const {}
1054 void onSuccessRelocateRound()const {}
1055 void onRelocateAboveThresholdRound() const {}
1056 void onFailedRelocate() const {}
1058 void onResizeCall() const {}
1059 void onFalseResizeCall() const {}
1060 void onResizeSuccessMove() const {}
1061 void onResizeRelocateCall() const {}
1063 void onInsertSuccess() const {}
1064 void onInsertFailed() const {}
1065 void onInsertResize() const {}
1066 void onInsertRelocate() const {}
1067 void onInsertRelocateFault() const {}
1069 void onEnsureExist() const {}
1070 void onEnsureSuccess() const {}
1071 void onEnsureResize() const {}
1072 void onEnsureRelocate() const {}
1073 void onEnsureRelocateFault() const {}
1075 void onUnlinkSuccess() const {}
1076 void onUnlinkFailed() const {}
1078 void onEraseSuccess() const {}
1079 void onEraseFailed() const {}
1081 void onFindSuccess() const {}
1082 void onFindFailed() const {}
1084 void onFindWithSuccess() const {}
1085 void onFindWithFailed() const {}
1089 /// Type traits for CuckooSet class
1094 Possible values are: cuckoo::base_hook, cuckoo::member_hook, cuckoo::traits_hook.
1096 typedef base_hook<> hook;
1098 /// Hash functors tuple
1100 This is mandatory type and has no predefined one.
1102 At least, two hash functors should be provided. All hash functor
1103 should be orthogonal (different): for each <tt> i,j: i != j => h[i](x) != h[j](x) </tt>.
1104 The hash functors are defined as <tt> std::tuple< H1, H2, ... Hn > </tt>:
1105 \@code cds::opt::hash< std::tuple< h1, h2 > > \@endcode
1106 The number of hash functors specifies the number \p k - the count of hash tables in cuckoo hashing.
1107 Up to 10 different hash functors are supported.
1109 typedef cds::opt::none hash;
1111 /// Concurrent access policy
1113 Available opt::mutex_policy types:
1114 - cuckoo::striping - simple, but the lock array is not resizable
1115 - cuckoo::refinable - resizable lock array, but more complex access to set data.
1117 Default is cuckoo::striping.
1119 typedef cuckoo::striping<> mutex_policy;
1121 /// Key equality functor
1123 Default is <tt>std::equal_to<T></tt>
1125 typedef opt::none equal_to;
1127 /// Key comparison functor
1129 No default functor is provided. If the option is not specified, the \p less is used.
1131 typedef opt::none compare;
1133 /// specifies binary predicate used for key comparison.
1135 Default is \p std::less<T>.
1137 typedef opt::none less;
1141 The type for item counting feature.
1142 Default is cds::atomicity::item_counter
1144 Only atomic item counter type is allowed.
1146 typedef atomicity::item_counter item_counter;
1150 The allocator type for allocating bucket tables.
1152 typedef CDS_DEFAULT_ALLOCATOR allocator;
1156 The disposer functor is used in CuckooSet::clear member function
1159 typedef intrusive::opt::v::empty_disposer disposer;
1161 /// Internal statistics. Available statistics: cuckoo::stat, cuckoo::empty_stat
1162 typedef empty_stat stat;
1165 /// Metafunction converting option list to CuckooSet traits
1167 This is a wrapper for <tt> cds::opt::make_options< type_traits, Options...> </tt>
1168 \p Options list see \ref CuckooSet.
1170 template <CDS_DECL_OPTIONS11>
1171 struct make_traits {
1172 typedef typename cds::opt::make_options<
1173 typename cds::opt::find_type_traits< cuckoo::type_traits, CDS_OPTIONS10 >::type
1175 >::type type ; ///< Result of metafunction
1180 template <typename Node, typename Probeset>
1183 template <typename Node>
1184 class bucket_entry<Node, cuckoo::list>
1187 typedef Node node_type;
1188 typedef cuckoo::list_probeset_class probeset_class;
1189 typedef cuckoo::list probeset_type;
1199 friend class bucket_entry;
1205 iterator( node_type * p )
1208 iterator( iterator const& it)
1212 iterator& operator=( iterator const& it )
1218 iterator& operator=( node_type * p )
1224 node_type * operator->()
1228 node_type& operator*()
1230 assert( pNode != nullptr );
1235 iterator& operator ++()
1238 pNode = pNode->m_pNext;
1242 bool operator==(iterator const& it ) const
1244 return pNode == it.pNode;
1246 bool operator!=(iterator const& it ) const
1248 return !( *this == it );
1257 static_assert(( std::is_same<typename node_type::probeset_type, probeset_type>::value ), "Incompatible node type" );
1262 return iterator(pHead);
1269 void insert_after( iterator it, node_type * p )
1271 node_type * pPrev = it.pNode;
1273 p->m_pNext = pPrev->m_pNext;
1284 void remove( iterator itPrev, iterator itWhat )
1286 node_type * pPrev = itPrev.pNode;
1287 node_type * pWhat = itWhat.pNode;
1288 assert( (!pPrev && pWhat == pHead) || (pPrev && pPrev->m_pNext == pWhat) );
1291 pPrev->m_pNext = pWhat->m_pNext;
1293 assert( pWhat == pHead );
1294 pHead = pHead->m_pNext;
1303 for ( node_type * pNode = pHead; pNode; pNode = pNext ) {
1304 pNext = pNode->m_pNext;
1312 template <typename Disposer>
1313 void clear( Disposer disp )
1316 for ( node_type * pNode = pHead; pNode; pNode = pNext ) {
1317 pNext = pNode->m_pNext;
1319 cds::unref(disp)( pNode );
1326 unsigned int size() const
1332 template <typename Node, unsigned int Capacity>
1333 class bucket_entry<Node, cuckoo::vector<Capacity> >
1336 typedef Node node_type;
1337 typedef cuckoo::vector_probeset_class probeset_class;
1338 typedef cuckoo::vector<Capacity> probeset_type;
1340 static unsigned int const c_nCapacity = probeset_type::c_nCapacity;
1343 node_type * m_arrNode[c_nCapacity];
1344 unsigned int m_nSize;
1346 void shift_up( unsigned int nFrom )
1348 assert( m_nSize < c_nCapacity );
1351 if ( nFrom < m_nSize )
1352 std::copy_backward( m_arrNode + nFrom, m_arrNode + m_nSize, m_arrNode + m_nSize + 1 );
1354 // alternative: low-level byte copying
1355 //memmove( m_arrNode + nFrom + 1, m_arrNode + nFrom, (m_nSize - nFrom) * sizeof(m_arrNode[0]) );
1358 void shift_down( node_type ** pFrom )
1360 assert( m_arrNode <= pFrom && pFrom < m_arrNode + m_nSize);
1362 std::copy( pFrom + 1, m_arrNode + m_nSize, pFrom );
1364 // alternative: low-level byte copying
1365 //memmove( pFrom + 1, pFrom, (m_nSize - nFrom - 1) * sizeof(m_arrNode[0]));
1371 friend class bucket_entry;
1377 iterator( node_type ** p )
1380 iterator( iterator const& it)
1384 iterator& operator=( iterator const& it )
1390 node_type * operator->()
1392 assert( pArr != nullptr );
1395 node_type& operator*()
1397 assert( pArr != nullptr );
1398 assert( *pArr != nullptr );
1403 iterator& operator ++()
1409 bool operator==(iterator const& it ) const
1411 return pArr == it.pArr;
1413 bool operator!=(iterator const& it ) const
1415 return !( *this == it );
1423 memset( m_arrNode, 0, sizeof(m_arrNode));
1424 static_assert(( std::is_same<typename node_type::probeset_type, probeset_type>::value ), "Incompatible node type" );
1429 return iterator(m_arrNode);
1433 return iterator(m_arrNode + size());
1436 void insert_after( iterator it, node_type * p )
1438 assert( m_nSize < c_nCapacity );
1439 assert( !it.pArr || (m_arrNode <= it.pArr && it.pArr <= m_arrNode + m_nSize));
1442 shift_up( (unsigned int)(it.pArr - m_arrNode) + 1 );
1452 void remove( iterator /*itPrev*/, iterator itWhat )
1455 shift_down( itWhat.pArr );
1464 template <typename Disposer>
1465 void clear( Disposer disp )
1467 for ( unsigned int i = 0; i < m_nSize; ++i ) {
1468 cds::unref(disp)( m_arrNode[i] );
1473 unsigned int size() const
1479 template <typename Node, unsigned int ArraySize>
1481 static void store( Node * pNode, size_t * pHashes )
1483 memcpy( pNode->m_arrHash, pHashes, sizeof(size_t) * ArraySize );
1485 static bool equal_to( Node& node, unsigned int nTable, size_t nHash )
1487 return node.m_arrHash[nTable] == nHash;
1490 template <typename Node>
1491 struct hash_ops<Node, 0>
1493 static void store( Node * /*pNode*/, size_t * /*pHashes*/ )
1495 static bool equal_to( Node& /*node*/, unsigned int /*nTable*/, size_t /*nHash*/ )
1501 template <typename NodeTraits, bool Ordered>
1504 template <typename NodeTraits>
1505 struct contains<NodeTraits, true>
1507 template <typename BucketEntry, typename Position, typename Q, typename Compare>
1508 static bool find( BucketEntry& probeset, Position& pos, unsigned int nTable, size_t nHash, Q const& val, Compare cmp )
1511 typedef typename BucketEntry::iterator bucket_iterator;
1513 bucket_iterator itPrev;
1515 for ( bucket_iterator it = probeset.begin(), itEnd = probeset.end(); it != itEnd; ++it ) {
1516 int cmpRes = cmp( *NodeTraits::to_value_ptr(*it), val );
1517 if ( cmpRes >= 0 ) {
1519 pos.itPrev = itPrev;
1526 pos.itPrev = itPrev;
1527 pos.itFound = probeset.end();
1532 template <typename NodeTraits>
1533 struct contains<NodeTraits, false>
1535 template <typename BucketEntry, typename Position, typename Q, typename EqualTo>
1536 static bool find( BucketEntry& probeset, Position& pos, unsigned int nTable, size_t nHash, Q const& val, EqualTo eq )
1538 // Unordered version
1539 typedef typename BucketEntry::iterator bucket_iterator;
1540 typedef typename BucketEntry::node_type node_type;
1542 bucket_iterator itPrev;
1544 for ( bucket_iterator it = probeset.begin(), itEnd = probeset.end(); it != itEnd; ++it ) {
1545 if ( hash_ops<node_type, node_type::hash_array_size>::equal_to( *it, nTable, nHash ) && eq( *NodeTraits::to_value_ptr(*it), val )) {
1547 pos.itPrev = itPrev;
1553 pos.itPrev = itPrev;
1554 pos.itFound = probeset.end();
1559 } // namespace details
1562 } // namespace cuckoo
1565 /** @ingroup cds_intrusive_map
1568 - [2007] M.Herlihy, N.Shavit, M.Tzafrir "Concurrent Cuckoo Hashing. Technical report"
1569 - [2008] Maurice Herlihy, Nir Shavit "The Art of Multiprocessor Programming"
1571 <b>About Cuckoo hashing</b>
1573 [From <i>"The Art of Multiprocessor Programming"</i>]
1574 Cuckoo hashing is a hashing algorithm in which a newly added item displaces any earlier item
1575 occupying the same slot. For brevity, a table is a k-entry array of items. For a hash set f size
1576 N = 2k we use a two-entry array of tables, and two independent hash functions,
1577 <tt> h0, h1: KeyRange -> 0,...,k-1</tt>
1578 mapping the set of possible keys to entries in he array. To test whether a value \p x is in the set,
1579 <tt>find(x)</tt> tests whether either <tt>table[0][h0(x)]</tt> or <tt>table[1][h1(x)]</tt> is
1580 equal to \p x. Similarly, <tt>erase(x)</tt>checks whether \p x is in either <tt>table[0][h0(x)]</tt>
1581 or <tt>table[1][h1(x)]</tt>, ad removes it if found.
1583 The <tt>insert(x)</tt> successively "kicks out" conflicting items until every key has a slot.
1584 To add \p x, the method swaps \p x with \p y, the current occupant of <tt>table[0][h0(x)]</tt>.
1585 If the prior value was \p nullptr, it is done. Otherwise, it swaps the newly nest-less value \p y
1586 for the current occupant of <tt>table[1][h1(y)]</tt> in the same way. As before, if the prior value
1587 was \p nullptr, it is done. Otherwise, the method continues swapping entries (alternating tables)
1588 until it finds an empty slot. We might not find an empty slot, either because the table is full,
1589 or because the sequence of displacement forms a cycle. We therefore need an upper limit on the
1590 number of successive displacements we are willing to undertake. When this limit is exceeded,
1591 we resize the hash table, choose new hash functions and start over.
1593 For concurrent cuckoo hashing, rather than organizing the set as a two-dimensional table of
1594 items, we use two-dimensional table of probe sets, where a probe set is a constant-sized set
1595 of items with the same hash code. Each probe set holds at most \p PROBE_SIZE items, but the algorithm
1596 tries to ensure that when the set is quiescent (i.e no method call in progress) each probe set
1597 holds no more than <tt>THRESHOLD < PROBE_SET</tt> items. While method calls are in-flight, a probe
1598 set may temporarily hold more than \p THRESHOLD but never more than \p PROBE_SET items.
1600 In current implementation, a probe set can be defined either as a (single-linked) list
1601 or as a fixed-sized vector, optionally ordered.
1603 In description above two-table cuckoo hashing (<tt>k = 2</tt>) has been considered.
1604 We can generalize this approach for <tt>k >= 2</tt> when we have \p k hash functions
1605 <tt>h[0], ... h[k-1]</tt> and \p k tables <tt>table[0], ... table[k-1]</tt>.
1607 The search in probe set is linear, the complexity is <tt> O(PROBE_SET) </tt>.
1608 The probe set may be ordered or not. Ordered probe set can be more efficient since
1609 the average search complexity is <tt>O(PROBE_SET/2)</tt>.
1610 However, the overhead of sorting can eliminate a gain of ordered search.
1612 The probe set is ordered if opt::compare or opt::less is specified in \p Traits template
1613 parameter. Otherwise, the probe set is unordered and \p Traits must contain
1614 opt::equal_to option.
1616 The cds::intrusive::cuckoo namespace contains \p %CuckooSet-related declarations.
1619 - \p T - the type stored in the set. The type must be based on cuckoo::node (for cuckoo::base_hook)
1620 or it must have a member of type %cuckoo::node (for cuckoo::member_hook),
1621 or it must be convertible to \p %cuckoo::node (for cuckoo::traits_hook)
1622 - \p Traits - type traits. See cuckoo::type_traits for explanation. It is possible to declare option-based
1623 set with cuckoo::make_traits metafunction result as \p Traits template argument.
1625 Template argument list \p Options... of cuckoo::make_traits metafunction are:
1626 - intrusive::opt::hook - hook used. Possible values are: cuckoo::base_hook, cuckoo::member_hook, cuckoo::traits_hook.
1627 If the option is not specified, <tt>%cuckoo::base_hook<></tt> is used.
1628 - opt::hash - hash functor tuple, mandatory option. At least, two hash functors should be provided. All hash functor
1629 should be orthogonal (different): for each <tt> i,j: i != j => h[i](x) != h[j](x) </tt>.
1630 The hash functors are passed as <tt> std::tuple< H1, H2, ... Hn > </tt>. The number of hash functors specifies
1631 the number \p k - the count of hash tables in cuckoo hashing. If the compiler supports variadic templates
1632 then k is unlimited, otherwise up to 10 different hash functors are supported.
1633 - opt::mutex_policy - concurrent access policy.
1634 Available policies: cuckoo::striping, cuckoo::refinable.
1635 Default is cuckoo::striping.
1636 - opt::equal_to - key equality functor like \p std::equal_to.
1637 If this functor is defined then the probe-set will be unordered.
1638 If opt::compare or opt::less option is specified too, then the probe-set will be ordered
1639 and opt::equal_to will be ignored.
1640 - opt::compare - key comparison functor. No default functor is provided.
1641 If the option is not specified, the opt::less is used.
1642 If opt::compare or opt::less option is specified, then the probe-set will be ordered.
1643 - opt::less - specifies binary predicate used for key comparison. Default is \p std::less<T>.
1644 If opt::compare or opt::less option is specified, then the probe-set will be ordered.
1645 - opt::item_counter - the type of item counting feature. Default is \ref atomicity::item_counter
1646 The item counter should be atomic.
1647 - opt::allocator - the allocator type using for allocating bucket tables.
1648 Default is \p CDS_DEFAULT_ALLOCATOR
1649 - intrusive::opt::disposer - the disposer type used in \ref clear() member function for
1650 freeing nodes. Default is intrusive::opt::v::empty_disposer
1651 - opt::stat - internal statistics. Possibly types: cuckoo::stat, cuckoo::empty_stat.
1652 Default is cuckoo::empty_stat
1654 The probe set options cuckoo::probeset_type and cuckoo::store_hash are taken from \p node type
1655 specified by \p opt::hook option.
1659 You should incorporate cuckoo::node into your struct \p T and provide
1660 appropriate cuckoo::type_traits::hook in your \p Traits template parameters. Usually, for \p Traits you
1661 define a struct based on cuckoo::type_traits.
1663 Example for base hook and list-based probe-set:
1665 #include <cds/intrusive/cuckoo_set.h>
1667 // Data stored in cuckoo set
1668 // We use list as probe-set container and store hash values in the node
1669 // (since we use two hash functions we should store 2 hash values per node)
1670 struct my_data: public cds::intrusive::cuckoo::node< cds::intrusive::cuckoo::list, 2 >
1679 // Provide equal_to functor for my_data since we will use unordered probe-set
1680 struct my_data_equal_to {
1681 bool operator()( const my_data& d1, const my_data& d2 ) const
1683 return d1.strKey.compare( d2.strKey ) == 0;
1686 bool operator()( const my_data& d, const std::string& s ) const
1688 return d.strKey.compare(s) == 0;
1691 bool operator()( const std::string& s, const my_data& d ) const
1693 return s.compare( d.strKey ) == 0;
1697 // Provide two hash functor for my_data
1699 size_t operator()(std::string const& s) const
1701 return cds::opt::v::hash<std::string>( s );
1703 size_t operator()( my_data const& d ) const
1705 return (*this)( d.strKey );
1709 struct hash2: private hash1 {
1710 size_t operator()(std::string const& s) const
1712 size_t h = ~( hash1::operator()(s));
1713 return ~h + 0x9e3779b9 + (h << 6) + (h >> 2);
1715 size_t operator()( my_data const& d ) const
1717 return (*this)( d.strKey );
1721 // Declare type traits
1722 struct my_traits: public cds::intrusive::cuckoo::type_traits
1724 typedef cds::intrusive::cuckoo::base_hook<
1725 cds::intrusive::cuckoo::probeset_type< my_data::probeset_type >
1726 ,cds::intrusive::cuckoo::store_hash< my_data::hash_array_size >
1728 typedef my_data_equa_to equal_to;
1729 typedef std::tuple< hash1, hash2 > hash;
1732 // Declare CuckooSet type
1733 typedef cds::intrusive::CuckooSet< my_data, my_traits > my_cuckoo_set;
1735 // Equal option-based declaration
1736 typedef cds::intrusive::CuckooSet< my_data,
1737 cds::intrusive::cuckoo::make_traits<
1738 cds::intrusive::opt::hook< cds::intrusive::cuckoo::base_hook<
1739 cds::intrusive::cuckoo::probeset_type< my_data::probeset_type >
1740 ,cds::intrusive::cuckoo::store_hash< my_data::hash_array_size >
1742 ,cds::opt::hash< std::tuple< hash1, hash2 > >
1743 ,cds::opt::equal_to< my_data_equal_to >
1748 If we provide \p compare function instead of \p equal_to for \p my_data
1749 we get as a result a cuckoo set with ordered probe set that may improve
1751 Example for base hook and ordered vector-based probe-set:
1754 #include <cds/intrusive/cuckoo_set.h>
1756 // Data stored in cuckoo set
1757 // We use a vector of capacity 4 as probe-set container and store hash values in the node
1758 // (since we use two hash functions we should store 2 hash values per node)
1759 struct my_data: public cds::intrusive::cuckoo::node< cds::intrusive::cuckoo::vector<4>, 2 >
1768 // Provide compare functor for my_data since we want to use ordered probe-set
1769 struct my_data_compare {
1770 int operator()( const my_data& d1, const my_data& d2 ) const
1772 return d1.strKey.compare( d2.strKey );
1775 int operator()( const my_data& d, const std::string& s ) const
1777 return d.strKey.compare(s);
1780 int operator()( const std::string& s, const my_data& d ) const
1782 return s.compare( d.strKey );
1786 // Provide two hash functor for my_data
1788 size_t operator()(std::string const& s) const
1790 return cds::opt::v::hash<std::string>( s );
1792 size_t operator()( my_data const& d ) const
1794 return (*this)( d.strKey );
1798 struct hash2: private hash1 {
1799 size_t operator()(std::string const& s) const
1801 size_t h = ~( hash1::operator()(s));
1802 return ~h + 0x9e3779b9 + (h << 6) + (h >> 2);
1804 size_t operator()( my_data const& d ) const
1806 return (*this)( d.strKey );
1810 // Declare type traits
1811 struct my_traits: public cds::intrusive::cuckoo::type_traits
1813 typedef cds::intrusive::cuckoo::base_hook<
1814 cds::intrusive::cuckoo::probeset_type< my_data::probeset_type >
1815 ,cds::intrusive::cuckoo::store_hash< my_data::hash_array_size >
1817 typedef my_data_compare compare;
1818 typedef std::tuple< hash1, hash2 > hash;
1821 // Declare CuckooSet type
1822 typedef cds::intrusive::CuckooSet< my_data, my_traits > my_cuckoo_set;
1824 // Equal option-based declaration
1825 typedef cds::intrusive::CuckooSet< my_data,
1826 cds::intrusive::cuckoo::make_traits<
1827 cds::intrusive::opt::hook< cds::intrusive::cuckoo::base_hook<
1828 cds::intrusive::cuckoo::probeset_type< my_data::probeset_type >
1829 ,cds::intrusive::cuckoo::store_hash< my_data::hash_array_size >
1831 ,cds::opt::hash< std::tuple< hash1, hash2 > >
1832 ,cds::opt::compare< my_data_compare >
1838 template <typename T, typename Traits = cuckoo::type_traits>
1842 typedef T value_type ; ///< The value type stored in the set
1843 typedef Traits options ; ///< Set traits
1845 typedef typename options::hook hook ; ///< hook type
1846 typedef typename hook::node_type node_type ; ///< node type
1847 typedef typename get_node_traits< value_type, node_type, hook>::type node_traits ; ///< node traits
1849 typedef typename options::hash hash ; ///< hash functor tuple wrapped for internal use
1850 typedef typename hash::hash_tuple_type hash_tuple_type ; ///< Type of hash tuple
1852 typedef typename options::stat stat ; ///< internal statistics type
1854 typedef typename options::mutex_policy original_mutex_policy ; ///< Concurrent access policy, see cuckoo::type_traits::mutex_policy
1856 /// Actual mutex policy
1858 Actual mutex policy is built from mutex policy type provided by \p Traits template argument (see cuckoo::type_traits::mutex_policy)
1859 but mutex policy internal statistics is conformed with cukoo::type_traits::stat type provided by \p Traits:
1860 - if \p %cuckoo::type_traits::stat is cuckoo::empty_stat then mutex policy statistics is already empty one
1861 - otherwise real mutex policy statistics is used
1863 typedef typename original_mutex_policy::template rebind_statistics<
1864 typename std::conditional<
1865 std::is_same< stat, cuckoo::empty_stat >::value
1866 ,typename original_mutex_policy::empty_stat
1867 ,typename original_mutex_policy::real_stat
1869 >::other mutex_policy;
1871 static bool const c_isSorted = !( std::is_same< typename options::compare, opt::none >::value
1872 && std::is_same< typename options::less, opt::none >::value ) ; ///< whether the probe set should be ordered
1873 static size_t const c_nArity = hash::size ; ///< the arity of cuckoo hashing: the number of hash functors provided; minimum 2.
1875 /// Key equality functor; used only for unordered probe-set
1876 typedef typename opt::details::make_equal_to< value_type, options, !c_isSorted>::type key_equal_to;
1878 /// key comparing functor based on opt::compare and opt::less option setter. Used only for ordered probe set
1879 typedef typename opt::details::make_comparator< value_type, options >::type key_comparator;
1882 typedef typename options::allocator allocator;
1884 /// item counter type
1885 typedef typename options::item_counter item_counter;
1888 typedef typename options::disposer disposer;
1892 typedef typename node_type::probeset_class probeset_class;
1893 typedef typename node_type::probeset_type probeset_type;
1894 static unsigned int const c_nNodeHashArraySize = node_type::hash_array_size;
1896 typedef typename mutex_policy::scoped_cell_lock scoped_cell_lock;
1897 typedef typename mutex_policy::scoped_cell_trylock scoped_cell_trylock;
1898 typedef typename mutex_policy::scoped_full_lock scoped_full_lock;
1899 typedef typename mutex_policy::scoped_resize_lock scoped_resize_lock;
1901 typedef cuckoo::details::bucket_entry< node_type, probeset_type > bucket_entry;
1902 typedef typename bucket_entry::iterator bucket_iterator;
1903 typedef cds::details::Allocator< bucket_entry, allocator > bucket_table_allocator;
1905 typedef size_t hash_array[c_nArity] ; ///< hash array
1907 # ifndef CDS_CXX11_LAMBDA_SUPPORT
1908 struct empty_insert_functor {
1909 void operator()( value_type& )
1913 struct empty_erase_functor {
1914 void operator()( value_type const& )
1918 struct empty_find_functor {
1919 template <typename Q>
1920 void operator()( value_type& item, Q& val )
1925 # if !defined(CDS_CXX11_LAMBDA_SUPPORT) || ((CDS_COMPILER == CDS_COMPILER_MSVC || CDS_COMPILER == CDS_COMPILER_INTEL ) && _MSC_VER == 1600)
1926 template <typename Disposer>
1927 class disposer_wrapper: protected cds::details::functor_wrapper<Disposer>
1929 typedef cds::details::functor_wrapper<Disposer> base_class;
1931 disposer_wrapper( Disposer d): base_class(d) {}
1933 void operator()( node_type * pNode )
1935 base_class::get()( node_traits::to_value_ptr( pNode ));
1941 bucket_iterator itPrev;
1942 bucket_iterator itFound;
1945 typedef typename std::conditional< c_isSorted
1946 , cuckoo::details::contains< node_traits, true >
1947 , cuckoo::details::contains< node_traits, false >
1948 >::type contains_action;
1950 template <typename Predicate>
1951 struct predicate_wrapper {
1952 typedef typename std::conditional< c_isSorted, cds::opt::details::make_comparator_from_less<Predicate>, Predicate>::type type;
1955 typedef typename std::conditional< c_isSorted, key_comparator, key_equal_to >::type key_predicate;
1959 static unsigned int const c_nDefaultProbesetSize = 4 ; ///< default probeset size
1960 static size_t const c_nDefaultInitialSize = 16 ; ///< default initial size
1961 static unsigned int const c_nRelocateLimit = c_nArity * 2 - 1 ; ///< Count of attempts to relocate before giving up
1964 bucket_entry * m_BucketTable[ c_nArity ] ; ///< Bucket tables
1966 size_t m_nBucketMask ; ///< Hash bitmask; bucket table size minus 1.
1967 unsigned int const m_nProbesetSize ; ///< Probe set size
1968 unsigned int const m_nProbesetThreshold ; ///< Probe set threshold
1970 hash m_Hash ; ///< Hash functor tuple
1971 mutex_policy m_MutexPolicy ; ///< concurrent access policy
1972 item_counter m_ItemCounter ; ///< item counter
1973 mutable stat m_Stat ; ///< internal statistics
1977 static void check_common_constraints()
1979 static_assert( (c_nArity == mutex_policy::c_nArity), "The count of hash functors must be equal to mutex_policy arity" );
1982 void check_probeset_properties() const
1984 assert( m_nProbesetThreshold < m_nProbesetSize );
1986 // if probe set type is cuckoo::vector<N> then m_nProbesetSize == N
1987 assert( node_type::probeset_size == 0 || node_type::probeset_size == m_nProbesetSize );
1990 template <typename Q>
1991 void hashing( size_t * pHashes, Q const& v ) const
1993 m_Hash( pHashes, v );
1996 void copy_hash( size_t * pHashes, value_type const& v ) const
1998 if ( c_nNodeHashArraySize )
1999 memcpy( pHashes, node_traits::to_node_ptr( v )->get_hash(), sizeof(pHashes[0]) * c_nNodeHashArraySize );
2001 hashing( pHashes, v );
2004 bucket_entry& bucket( unsigned int nTable, size_t nHash )
2006 assert( nTable < c_nArity );
2007 return m_BucketTable[nTable][nHash & m_nBucketMask];
2010 static void store_hash( node_type * pNode, size_t * pHashes )
2012 cuckoo::details::hash_ops< node_type, c_nNodeHashArraySize >::store( pNode, pHashes );
2013 //memcpy( pNode->m_arrHash, pHashes, sizeof(size_t) * c_nArity );
2016 static bool equal_hash( node_type& node, unsigned int nTable, size_t nHash )
2018 return cuckoo::details::hash_ops< node_type, c_nNodeHashArraySize >::equal_to( node, nTable, nHash );
2021 void allocate_bucket_tables( size_t nSize )
2023 assert( cds::beans::is_power2( nSize ) );
2025 m_nBucketMask = nSize - 1;
2026 bucket_table_allocator alloc;
2027 for ( unsigned int i = 0; i < c_nArity; ++i )
2028 m_BucketTable[i] = alloc.NewArray( nSize );
2031 static void free_bucket_tables( bucket_entry ** pTable, size_t nCapacity )
2033 bucket_table_allocator alloc;
2034 for ( unsigned int i = 0; i < c_nArity; ++i ) {
2035 alloc.Delete( pTable[i], nCapacity );
2036 pTable[i] = nullptr;
2039 void free_bucket_tables()
2041 free_bucket_tables( m_BucketTable, m_nBucketMask + 1 );
2044 static unsigned int const c_nUndefTable = (unsigned int) -1;
2045 template <typename Q, typename Predicate >
2046 unsigned int contains( position * arrPos, size_t * arrHash, Q const& val, Predicate pred )
2048 // Buckets must be locked
2050 for ( unsigned int i = 0; i < c_nArity; ++i ) {
2051 bucket_entry& probeset = bucket( i, arrHash[i] );
2052 if ( contains_action::find( probeset, arrPos[i], i, arrHash[i], val, pred ))
2055 return c_nUndefTable;
2058 template <typename Q, typename Predicate, typename Func>
2059 value_type * erase_( Q const& val, Predicate pred, Func f )
2062 hashing( arrHash, val );
2063 position arrPos[ c_nArity ];
2066 scoped_cell_lock guard( m_MutexPolicy, arrHash );
2068 unsigned int nTable = contains( arrPos, arrHash, val, pred );
2069 if ( nTable != c_nUndefTable ) {
2070 node_type& node = *arrPos[nTable].itFound;
2071 cds::unref(f)( *node_traits::to_value_ptr(node) );
2072 bucket( nTable, arrHash[nTable]).remove( arrPos[nTable].itPrev, arrPos[nTable].itFound );
2074 m_Stat.onEraseSuccess();
2075 return node_traits::to_value_ptr( node );
2079 m_Stat.onEraseFailed();
2083 template <typename Q, typename Predicate, typename Func>
2084 bool find_( Q& val, Predicate pred, Func f )
2087 position arrPos[ c_nArity ];
2088 hashing( arrHash, val );
2089 scoped_cell_lock sl( m_MutexPolicy, arrHash );
2091 unsigned int nTable = contains( arrPos, arrHash, val, pred );
2092 if ( nTable != c_nUndefTable ) {
2093 cds::unref(f)( *node_traits::to_value_ptr( *arrPos[nTable].itFound ), val );
2094 m_Stat.onFindSuccess();
2098 m_Stat.onFindFailed();
2102 bool relocate( unsigned int nTable, size_t * arrGoalHash )
2104 // arrGoalHash contains hash values for relocating element
2105 // Relocating element is first one from bucket( nTable, arrGoalHash[nTable] ) probeset
2107 m_Stat.onRelocateCall();
2111 for ( unsigned int nRound = 0; nRound < c_nRelocateLimit; ++nRound ) {
2112 m_Stat.onRelocateRound();
2115 scoped_cell_lock guard( m_MutexPolicy, arrGoalHash );
2117 bucket_entry& refBucket = bucket( nTable, arrGoalHash[nTable] );
2118 if ( refBucket.size() < m_nProbesetThreshold ) {
2119 // probeset is not above the threshold
2120 m_Stat.onFalseRelocateRound();
2124 pVal = node_traits::to_value_ptr( *refBucket.begin() );
2125 copy_hash( arrHash, *pVal );
2127 scoped_cell_trylock guard2( m_MutexPolicy, arrHash );
2128 if ( !guard2.locked() )
2129 continue ; // try one more time
2131 refBucket.remove( typename bucket_entry::iterator(), refBucket.begin() );
2133 unsigned int i = (nTable + 1) % c_nArity;
2135 // try insert into free probeset
2136 while ( i != nTable ) {
2137 bucket_entry& bkt = bucket( i, arrHash[i] );
2138 if ( bkt.size() < m_nProbesetThreshold ) {
2140 contains_action::find( bkt, pos, i, arrHash[i], *pVal, key_predicate() ) ; // must return false!
2141 bkt.insert_after( pos.itPrev, node_traits::to_node_ptr( pVal ));
2142 m_Stat.onSuccessRelocateRound();
2145 i = ( i + 1 ) % c_nArity;
2148 // try insert into partial probeset
2149 i = (nTable + 1) % c_nArity;
2150 while ( i != nTable ) {
2151 bucket_entry& bkt = bucket( i, arrHash[i] );
2152 if ( bkt.size() < m_nProbesetSize ) {
2154 contains_action::find( bkt, pos, i, arrHash[i], *pVal, key_predicate() ) ; // must return false!
2155 bkt.insert_after( pos.itPrev, node_traits::to_node_ptr( pVal ));
2157 memcpy( arrGoalHash, arrHash, sizeof(arrHash));
2158 m_Stat.onRelocateAboveThresholdRound();
2159 goto next_iteration;
2161 i = (i + 1) % c_nArity;
2164 // all probeset is full, relocating fault
2165 refBucket.insert_after( typename bucket_entry::iterator(), node_traits::to_node_ptr( pVal ));
2166 m_Stat.onFailedRelocate();
2177 m_Stat.onResizeCall();
2179 size_t nOldCapacity = bucket_count();
2180 bucket_entry * pOldTable[ c_nArity ];
2182 scoped_resize_lock guard( m_MutexPolicy );
2184 if ( nOldCapacity != bucket_count() ) {
2185 m_Stat.onFalseResizeCall();
2189 size_t nCapacity = nOldCapacity * 2;
2191 m_MutexPolicy.resize( nCapacity );
2192 memcpy( pOldTable, m_BucketTable, sizeof(pOldTable));
2193 allocate_bucket_tables( nCapacity );
2195 typedef typename bucket_entry::iterator bucket_iterator;
2197 position arrPos[ c_nArity ];
2199 for ( unsigned int nTable = 0; nTable < c_nArity; ++nTable ) {
2200 bucket_entry * pTable = pOldTable[nTable];
2201 for ( size_t k = 0; k < nOldCapacity; ++k ) {
2202 bucket_iterator itNext;
2203 for ( bucket_iterator it = pTable[k].begin(), itEnd = pTable[k].end(); it != itEnd; it = itNext ) {
2207 value_type& val = *node_traits::to_value_ptr( *it );
2208 copy_hash( arrHash, val );
2209 contains( arrPos, arrHash, val, key_predicate() ) ; // must return c_nUndefTable
2211 for ( unsigned int i = 0; i < c_nArity; ++i ) {
2212 bucket_entry& refBucket = bucket( i, arrHash[i] );
2213 if ( refBucket.size() < m_nProbesetThreshold ) {
2214 refBucket.insert_after( arrPos[i].itPrev, &*it );
2215 m_Stat.onResizeSuccessMove();
2220 for ( unsigned int i = 0; i < c_nArity; ++i ) {
2221 bucket_entry& refBucket = bucket( i, arrHash[i] );
2222 if ( refBucket.size() < m_nProbesetSize ) {
2223 refBucket.insert_after( arrPos[i].itPrev, &*it );
2224 assert( refBucket.size() > 1 );
2225 copy_hash( arrHash, *node_traits::to_value_ptr( *refBucket.begin()) );
2226 m_Stat.onResizeRelocateCall();
2227 relocate( i, arrHash );
2236 free_bucket_tables( pOldTable, nOldCapacity );
2239 CDS_CONSTEXPR static unsigned int calc_probeset_size( unsigned int nProbesetSize ) CDS_NOEXCEPT
2241 return nProbesetSize
2243 : ( node_type::probeset_size ? node_type::probeset_size : c_nDefaultProbesetSize )
2249 /// Default constructor
2251 Initial size = \ref c_nDefaultInitialSize
2254 - \p c_nDefaultProbesetSize if \p probeset_type is \p cuckoo::list
2255 - \p Capacity if \p probeset_type is <tt> cuckoo::vector<Capacity> </tt>
2257 Probe set threshold = probe set size - 1
2260 : m_nProbesetSize( calc_probeset_size(0) )
2261 , m_nProbesetThreshold( m_nProbesetSize - 1 )
2262 , m_MutexPolicy( c_nDefaultInitialSize )
2264 check_common_constraints();
2265 check_probeset_properties();
2267 allocate_bucket_tables( c_nDefaultInitialSize );
2270 /// Constructs the set object with given probe set size and threshold
2272 If probe set type is <tt> cuckoo::vector<Capacity> </tt> vector
2273 then \p nProbesetSize should be equal to vector's \p Capacity.
2276 size_t nInitialSize ///< Initial set size; if 0 - use default initial size \ref c_nDefaultInitialSize
2277 , unsigned int nProbesetSize ///< probe set size
2278 , unsigned int nProbesetThreshold = 0 ///< probe set threshold, <tt>nProbesetThreshold < nProbesetSize</tt>. If 0, nProbesetThreshold = nProbesetSize - 1
2280 : m_nProbesetSize( calc_probeset_size(nProbesetSize) )
2281 , m_nProbesetThreshold( nProbesetThreshold ? nProbesetThreshold : m_nProbesetSize - 1 )
2282 , m_MutexPolicy( cds::beans::ceil2(nInitialSize ? nInitialSize : c_nDefaultInitialSize ))
2284 check_common_constraints();
2285 check_probeset_properties();
2287 allocate_bucket_tables( nInitialSize ? cds::beans::ceil2( nInitialSize ) : c_nDefaultInitialSize );
2290 /// Constructs the set object with given hash functor tuple
2292 The probe set size and threshold are set as default, see CuckooSet()
2295 hash_tuple_type const& h ///< hash functor tuple of type <tt>std::tuple<H1, H2, ... Hn></tt> where <tt> n == \ref c_nArity </tt>
2297 : m_nProbesetSize( calc_probeset_size(0) )
2298 , m_nProbesetThreshold( m_nProbesetSize -1 )
2300 , m_MutexPolicy( c_nDefaultInitialSize )
2302 check_common_constraints();
2303 check_probeset_properties();
2305 allocate_bucket_tables( c_nDefaultInitialSize );
2308 /// Constructs the set object with given probe set properties and hash functor tuple
2310 If probe set type is <tt> cuckoo::vector<Capacity> </tt> vector
2311 then \p nProbesetSize should be equal to vector's \p Capacity.
2314 size_t nInitialSize ///< Initial set size; if 0 - use default initial size \ref c_nDefaultInitialSize
2315 , unsigned int nProbesetSize ///< probe set size, positive integer
2316 , unsigned int nProbesetThreshold ///< probe set threshold, <tt>nProbesetThreshold < nProbesetSize</tt>. If 0, nProbesetThreshold = nProbesetSize - 1
2317 , hash_tuple_type const& h ///< hash functor tuple of type <tt>std::tuple<H1, H2, ... Hn></tt> where <tt> n == \ref c_nArity </tt>
2319 : m_nProbesetSize( calc_probeset_size(nProbesetSize) )
2320 , m_nProbesetThreshold( nProbesetThreshold ? nProbesetThreshold : m_nProbesetSize - 1)
2322 , m_MutexPolicy( cds::beans::ceil2(nInitialSize ? nInitialSize : c_nDefaultInitialSize ))
2324 check_common_constraints();
2325 check_probeset_properties();
2327 allocate_bucket_tables( nInitialSize ? cds::beans::ceil2( nInitialSize ) : c_nDefaultInitialSize );
2330 # ifdef CDS_MOVE_SEMANTICS_SUPPORT
2331 /// Constructs the set object with given hash functor tuple (move semantics)
2333 The probe set size and threshold are set as default, see CuckooSet()
2336 hash_tuple_type&& h ///< hash functor tuple of type <tt>std::tuple<H1, H2, ... Hn></tt> where <tt> n == \ref c_nArity </tt>
2338 : m_nProbesetSize( calc_probeset_size(0) )
2339 , m_nProbesetThreshold( m_nProbesetSize / 2 )
2340 , m_Hash( std::forward<hash_tuple_type>(h) )
2341 , m_MutexPolicy( c_nDefaultInitialSize )
2343 check_common_constraints();
2344 check_probeset_properties();
2346 allocate_bucket_tables( c_nDefaultInitialSize );
2349 /// Constructs the set object with given probe set properties and hash functor tuple (move semantics)
2351 If probe set type is <tt> cuckoo::vector<Capacity> </tt> vector
2352 then \p nProbesetSize should be equal to vector's \p Capacity.
2355 size_t nInitialSize ///< Initial set size; if 0 - use default initial size \ref c_nDefaultInitialSize
2356 , unsigned int nProbesetSize ///< probe set size, positive integer
2357 , unsigned int nProbesetThreshold ///< probe set threshold, <tt>nProbesetThreshold < nProbesetSize</tt>. If 0, nProbesetThreshold = nProbesetSize - 1
2358 , hash_tuple_type&& h ///< hash functor tuple of type <tt>std::tuple<H1, H2, ... Hn></tt> where <tt> n == \ref c_nArity </tt>
2360 : m_nProbesetSize( calc_probeset_size(nProbesetSize) )
2361 , m_nProbesetThreshold( nProbesetThreshold ? nProbesetThreshold : m_nProbesetSize - 1)
2362 , m_Hash( std::forward<hash_tuple_type>(h) )
2363 , m_MutexPolicy( cds::beans::ceil2(nInitialSize ? nInitialSize : c_nDefaultInitialSize ))
2365 check_common_constraints();
2366 check_probeset_properties();
2368 allocate_bucket_tables( nInitialSize ? cds::beans::ceil2( nInitialSize ) : c_nDefaultInitialSize );
2370 # endif // ifdef CDS_MOVE_SEMANTICS_SUPPORT
2375 free_bucket_tables();
2379 /// Inserts new node
2381 The function inserts \p val in the set if it does not contain
2382 an item with key equal to \p val.
2384 Returns \p true if \p val is placed into the set, \p false otherwise.
2386 bool insert( value_type& val )
2388 # ifdef CDS_CXX11_LAMBDA_SUPPORT
2389 return insert( val, []( value_type& ) {} );
2391 return insert( val, empty_insert_functor() );
2395 /// Inserts new node
2397 The function allows to split creating of new item into two part:
2398 - create item with key only
2399 - insert new item into the set
2400 - if inserting is success, calls \p f functor to initialize value-field of \p val.
2402 The functor signature is:
2404 void func( value_type& val );
2406 where \p val is the item inserted.
2408 The user-defined functor is called only if the inserting is success and can be passed by reference
2409 using <tt>boost::ref</tt>
2411 template <typename Func>
2412 bool insert( value_type& val, Func f )
2415 position arrPos[ c_nArity ];
2416 unsigned int nGoalTable;
2418 hashing( arrHash, val );
2419 node_type * pNode = node_traits::to_node_ptr( val );
2420 store_hash( pNode, arrHash );
2424 scoped_cell_lock guard( m_MutexPolicy, arrHash );
2426 if ( contains( arrPos, arrHash, val, key_predicate() ) != c_nUndefTable ) {
2427 m_Stat.onInsertFailed();
2431 for ( unsigned int i = 0; i < c_nArity; ++i ) {
2432 bucket_entry& refBucket = bucket( i, arrHash[i] );
2433 if ( refBucket.size() < m_nProbesetThreshold ) {
2434 refBucket.insert_after( arrPos[i].itPrev, pNode );
2435 cds::unref(f)( val );
2437 m_Stat.onInsertSuccess();
2442 for ( unsigned int i = 0; i < c_nArity; ++i ) {
2443 bucket_entry& refBucket = bucket( i, arrHash[i] );
2444 if ( refBucket.size() < m_nProbesetSize ) {
2445 refBucket.insert_after( arrPos[i].itPrev, pNode );
2446 cds::unref(f)( val );
2449 assert( refBucket.size() > 1 );
2450 copy_hash( arrHash, *node_traits::to_value_ptr( *refBucket.begin()) );
2456 m_Stat.onInsertResize();
2461 m_Stat.onInsertRelocate();
2462 if ( !relocate( nGoalTable, arrHash )) {
2463 m_Stat.onInsertRelocateFault();
2464 m_Stat.onInsertResize();
2468 m_Stat.onInsertSuccess();
2472 /// Ensures that the \p val exists in the set
2474 The operation performs inserting or changing data with lock-free manner.
2476 If the item \p val not found in the set, then \p val is inserted into the set.
2477 Otherwise, the functor \p func is called with item found.
2478 The functor signature is:
2480 void func( bool bNew, value_type& item, value_type& val );
2483 - \p bNew - \p true if the item has been inserted, \p false otherwise
2484 - \p item - item of the set
2485 - \p val - argument \p val passed into the \p ensure function
2486 If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
2487 refers to the same thing.
2489 The functor may change non-key fields of the \p item.
2491 You may pass \p func argument by reference using <tt>boost::ref</tt> or cds::ref.
2493 Returns <tt> std::pair<bool, bool> </tt> where \p first is \p true if operation is successful,
2494 \p second is \p true if new item has been added or \p false if the item with \p key
2495 already is in the set.
2497 template <typename Func>
2498 std::pair<bool, bool> ensure( value_type& val, Func func )
2501 position arrPos[ c_nArity ];
2502 unsigned int nGoalTable;
2504 hashing( arrHash, val );
2505 node_type * pNode = node_traits::to_node_ptr( val );
2506 store_hash( pNode, arrHash );
2510 scoped_cell_lock guard( m_MutexPolicy, arrHash );
2512 unsigned int nTable = contains( arrPos, arrHash, val, key_predicate() );
2513 if ( nTable != c_nUndefTable ) {
2514 cds::unref(func)( false, *node_traits::to_value_ptr( *arrPos[nTable].itFound ), val );
2515 m_Stat.onEnsureExist();
2516 return std::make_pair( true, false );
2519 node_type * pNode = node_traits::to_node_ptr( val );
2520 store_hash( pNode, arrHash );
2522 for ( unsigned int i = 0; i < c_nArity; ++i ) {
2523 bucket_entry& refBucket = bucket( i, arrHash[i] );
2524 if ( refBucket.size() < m_nProbesetThreshold ) {
2525 refBucket.insert_after( arrPos[i].itPrev, pNode );
2526 cds::unref(func)( true, val, val );
2528 m_Stat.onEnsureSuccess();
2529 return std::make_pair( true, true );
2533 for ( unsigned int i = 0; i < c_nArity; ++i ) {
2534 bucket_entry& refBucket = bucket( i, arrHash[i] );
2535 if ( refBucket.size() < m_nProbesetSize ) {
2536 refBucket.insert_after( arrPos[i].itPrev, pNode );
2537 cds::unref(func)( true, val, val );
2540 assert( refBucket.size() > 1 );
2541 copy_hash( arrHash, *node_traits::to_value_ptr( *refBucket.begin()) );
2547 m_Stat.onEnsureResize();
2552 m_Stat.onEnsureRelocate();
2553 if ( !relocate( nGoalTable, arrHash )) {
2554 m_Stat.onEnsureRelocateFault();
2555 m_Stat.onEnsureResize();
2559 m_Stat.onEnsureSuccess();
2560 return std::make_pair( true, true );
2563 /// Unlink the item \p val from the set
2565 The function searches the item \p val in the set and unlink it
2566 if it is found and is equal to \p val (here, the equality means that
2567 \p val belongs to the set: if \p item is an item found then
2568 unlink is successful iif <tt>&val == &item</tt>)
2570 The function returns \p true if success and \p false otherwise.
2572 bool unlink( value_type& val )
2575 hashing( arrHash, val );
2576 position arrPos[ c_nArity ];
2579 scoped_cell_lock guard( m_MutexPolicy, arrHash );
2581 unsigned int nTable = contains( arrPos, arrHash, val, key_predicate() );
2582 if ( nTable != c_nUndefTable && node_traits::to_value_ptr(*arrPos[nTable].itFound) == &val ) {
2583 bucket( nTable, arrHash[nTable]).remove( arrPos[nTable].itPrev, arrPos[nTable].itFound );
2585 m_Stat.onUnlinkSuccess();
2590 m_Stat.onUnlinkFailed();
2594 /// Deletes the item from the set
2595 /** \anchor cds_intrusive_CuckooSet_erase
2596 The function searches an item with key equal to \p val in the set,
2597 unlinks it from the set, and returns a pointer to unlinked item.
2599 If the item with key equal to \p val is not found the function return \p nullptr.
2601 Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
2603 template <typename Q>
2604 value_type * erase( Q const& val )
2606 # ifdef CDS_CXX11_LAMBDA_SUPPORT
2607 return erase( val, [](value_type const&) {} );
2609 return erase( val, empty_erase_functor() );
2613 /// Deletes the item from the set using \p pred predicate for searching
2615 The function is an analog of \ref cds_intrusive_CuckooSet_erase "erase(Q const&)"
2616 but \p pred is used for key comparing.
2617 If cuckoo set is ordered, then \p Predicate should have the interface and semantics like \p std::less.
2618 If cuckoo set is unordered, then \p Predicate should have the interface and semantics like \p std::equal_to.
2619 \p Predicate must imply the same element order as the comparator used for building the set.
2621 template <typename Q, typename Predicate>
2622 value_type * erase_with( Q const& val, Predicate pred )
2624 # ifdef CDS_CXX11_LAMBDA_SUPPORT
2625 return erase_( val, typename predicate_wrapper<Predicate>::type(), [](value_type const&) {} );
2627 return erase_( val, typename predicate_wrapper<Predicate>::type(), empty_erase_functor() );
2631 /// Delete the item from the set
2632 /** \anchor cds_intrusive_CuckooSet_erase_func
2633 The function searches an item with key equal to \p val in the set,
2634 call \p f functor with item found, unlinks it from the set, and returns a pointer to unlinked item.
2636 The \p Func interface is
2639 void operator()( value_type const& item );
2642 The functor may be passed by reference with <tt>boost:ref</tt>
2644 If the item with key equal to \p val is not found the function return \p nullptr.
2646 Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
2648 template <typename Q, typename Func>
2649 value_type * erase( Q const& val, Func f )
2651 return erase_( val, key_predicate(), f );
2654 /// Deletes the item from the set using \p pred predicate for searching
2656 The function is an analog of \ref cds_intrusive_CuckooSet_erase_func "erase(Q const&, Func)"
2657 but \p pred is used for key comparing.
2658 If you use ordered cuckoo set, then \p Predicate should have the interface and semantics like \p std::less.
2659 If you use unordered cuckoo set, then \p Predicate should have the interface and semantics like \p std::equal_to.
2660 \p Predicate must imply the same element order as the comparator used for building the set.
2662 template <typename Q, typename Predicate, typename Func>
2663 value_type * erase_with( Q const& val, Predicate pred, Func f )
2665 return erase_( val, typename predicate_wrapper<Predicate>::type(), f );
2668 /// Find the key \p val
2669 /** \anchor cds_intrusive_CuckooSet_find_func
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& val );
2677 where \p item is the item found, \p val is the <tt>find</tt> function argument.
2679 You can pass \p f argument by reference using <tt>boost::ref</tt> or cds::ref.
2681 The functor may change non-key fields of \p item.
2683 The \p val argument is non-const since it can be used as \p f functor destination i.e., the functor
2684 may modify both arguments.
2686 Note the hash functor specified for class \p Traits template parameter
2687 should accept a parameter of type \p Q that can be not the same as \p value_type.
2689 The function returns \p true if \p val is found, \p false otherwise.
2691 template <typename Q, typename Func>
2692 bool find( Q& val, Func f )
2694 return find_( val, key_predicate(), f );
2697 /// Find the key \p val using \p pred predicate for comparing
2699 The function is an analog of \ref cds_intrusive_CuckooSet_find_func "find(Q&, Func)"
2700 but \p pred is used for key comparison.
2701 If you use ordered cuckoo set, then \p Predicate should have the interface and semantics like \p std::less.
2702 If you use unordered cuckoo set, then \p Predicate should have the interface and semantics like \p std::equal_to.
2703 \p pred must imply the same element order as the comparator used for building the set.
2705 template <typename Q, typename Predicate, typename Func>
2706 bool find_with( Q& val, Predicate pred, Func f )
2708 return find_( val, typename predicate_wrapper<Predicate>::type(), f );
2711 /// Find the key \p val
2712 /** \anchor cds_intrusive_CuckooSet_find_cfunc
2713 The function searches the item with key equal to \p val and calls the functor \p f for item found.
2714 The interface of \p Func functor is:
2717 void operator()( value_type& item, Q const& val );
2720 where \p item is the item found, \p val is the <tt>find</tt> function argument.
2722 You can pass \p f argument by reference using <tt>boost::ref</tt> or cds::ref.
2724 The functor may change non-key fields of \p item.
2726 The \p val argument is non-const since it can be used as \p f functor destination i.e., the functor
2727 may modify both arguments.
2729 The function returns \p true if \p val is found, \p false otherwise.
2731 template <typename Q, typename Func>
2732 bool find( Q const& val, Func f )
2734 return find_( val, key_predicate(), f );
2737 /// Find the key \p val using \p pred predicate for comparing
2739 The function is an analog of \ref cds_intrusive_CuckooSet_find_cfunc "find(Q const&, Func)"
2740 but \p pred is used for key comparison.
2741 If you use ordered cuckoo set, then \p Predicate should have the interface and semantics like \p std::less.
2742 If you use unordered cuckoo set, then \p Predicate should have the interface and semantics like \p std::equal_to.
2743 \p pred must imply the same element order as the comparator used for building the set.
2745 template <typename Q, typename Predicate, typename Func>
2746 bool find_with( Q const& val, Predicate pred, Func f )
2748 return find_( val, typename predicate_wrapper<Predicate>::type(), f );
2751 /// Find the key \p val
2752 /** \anchor cds_intrusive_CuckooSet_find_val
2753 The function searches the item with key equal to \p val
2754 and returns \p true if it is found, and \p false otherwise.
2756 Note the hash functor specified for class \p Traits template parameter
2757 should accept a parameter of type \p Q that can be not the same as \p value_type.
2759 template <typename Q>
2760 bool find( Q const& val )
2762 # ifdef CDS_CXX11_LAMBDA_SUPPORT
2763 return find( val, [](value_type&, Q const& ) {} );
2765 return find( val, empty_find_functor() );
2769 /// Find the key \p val using \p pred predicate for comparing
2771 The function is an analog of \ref cds_intrusive_CuckooSet_find_val "find(Q const&)"
2772 but \p pred is used for key comparison.
2773 If you use ordered cuckoo set, then \p Predicate should have the interface and semantics like \p std::less.
2774 If you use unordered cuckoo set, then \p Predicate should have the interface and semantics like \p std::equal_to.
2775 \p pred must imply the same element order as the comparator used for building the set.
2777 template <typename Q, typename Predicate>
2778 bool find_with( Q const& val, Predicate pred )
2780 # ifdef CDS_CXX11_LAMBDA_SUPPORT
2781 return find_with( val, typename predicate_wrapper<Predicate>::type(), [](value_type& , Q const& ) {} );
2783 return find_with( val, typename predicate_wrapper<Predicate>::type(), empty_find_functor() );
2789 The function unlinks all items from the set.
2790 For any item \ref disposer is called
2794 clear_and_dispose( disposer() );
2797 /// Clears the set and calls \p disposer for each item
2799 The function unlinks all items from the set calling \p disposer for each item.
2800 \p Disposer functor interface is:
2803 void operator()( value_type * p );
2807 The \ref disposer specified in \p Traits options is not called.
2809 template <typename Disposer>
2810 void clear_and_dispose( Disposer oDisposer )
2812 // locks entire array
2813 scoped_full_lock sl( m_MutexPolicy );
2815 # if !defined(CDS_CXX11_LAMBDA_SUPPORT) || ((CDS_COMPILER == CDS_COMPILER_MSVC || CDS_COMPILER == CDS_COMPILER_INTEL ) && _MSC_VER == 1600)
2816 disposer_wrapper<Disposer> disp( oDisposer );
2818 for ( unsigned int i = 0; i < c_nArity; ++i ) {
2819 bucket_entry * pEntry = m_BucketTable[i];
2820 bucket_entry * pEnd = pEntry + m_nBucketMask + 1;
2821 for ( ; pEntry != pEnd ; ++pEntry ) {
2822 # if defined(CDS_CXX11_LAMBDA_SUPPORT) && !((CDS_COMPILER == CDS_COMPILER_MSVC || CDS_COMPILER == CDS_COMPILER_INTEL) && _MSC_VER == 1600)
2823 // MSVC 10: error to call nested typedefs node_traits from lambda
2824 pEntry->clear( [&oDisposer]( node_type * pNode ){ oDisposer( node_traits::to_value_ptr( pNode )) ; } );
2826 pEntry->clear( cds::ref(disp) );
2830 m_ItemCounter.reset();
2833 /// Checks if the set is empty
2835 Emptiness is checked by item counting: if item count is zero then the set is empty.
2842 /// Returns item count in the set
2845 return m_ItemCounter;
2848 /// Returns the size of hash table
2850 The hash table size is non-constant and can be increased via resizing.
2852 size_t bucket_count() const
2854 return m_nBucketMask + 1;
2857 /// Returns lock array size
2858 size_t lock_count() const
2860 return m_MutexPolicy.lock_count();
2863 /// Returns const reference to internal statistics
2864 stat const& statistics() const
2869 /// Returns const reference to mutex policy internal statistics
2870 typename mutex_policy::statistics_type const& mutex_policy_statistics() const
2872 return m_MutexPolicy.statistics();
2875 }} // namespace cds::intrusive
2877 #endif // #ifndef __CDS_INTRUSIVE_CUCKOO_SET_H