3 #ifndef __CDS_INTRUSIVE_CUCKOO_SET_H
4 #define __CDS_INTRUSIVE_CUCKOO_SET_H
7 #include <cds/intrusive/base.h>
8 #include <cds/opt/compare.h>
9 #include <cds/opt/hash.h>
10 #include <cds/lock/array.h>
12 #include <cds/os/thread.h>
13 #include <cds/details/std/memory.h>
14 #include <cds/details/functor_wrapper.h>
15 #include <cds/lock/spinlock.h>
17 #include <cds/details/std/mutex.h>
18 //#include <boost/thread/recursive_mutex.hpp>
20 namespace cds { namespace intrusive {
22 /// CuckooSet-related definitions
25 /// Option to define probeset type
27 The option specifies probeset type for the CuckooSet.
29 - \p cds::intrusive::cuckoo::list - the probeset is a single-linked list.
30 The node contains pointer to next node in probeset.
31 - \p cds::intrusive::cuckoo::vector<Capacity> - the probeset is a vector
32 with constant-size \p Capacity where \p Capacity is an <tt>unsigned int</tt> constant.
33 The node does not contain any auxiliary data.
35 template <typename Type>
39 template <typename Base>
40 struct pack: public Base {
41 typedef Type probeset_type;
46 /// Option specifying whether to store hash values in the node
48 This option reserves additional space in the hook to store the hash value of the object once it's introduced in the container.
49 When this option is used, the unordered container will store the calculated hash value in the hook and rehashing operations won't need
50 to recalculate the hash of the value. This option will improve the performance of unordered containers
51 when rehashing is frequent or hashing the value is a slow operation
53 The \p Count template parameter defines the size of hash array. Remember that cuckoo hashing implies at least two
56 Possible values of \p Count:
57 - 0 - no hash storing in the node
58 - greater that 1 - store hash values.
60 Value 1 is deprecated.
62 template <unsigned int Count>
66 template <typename Base>
67 struct pack: public Base {
68 static unsigned int const store_hash = Count;
75 // Probeset type placeholders
76 struct list_probeset_class;
77 struct vector_probeset_class;
81 // Probeset type declarations.
83 template <unsigned int Capacity>
86 static unsigned int const c_nCapacity = Capacity;
93 - \p ProbesetType - type of probeset. Can be \p cds::intrusive::cuckoo::list
94 or \p cds::intrusive::cuckoo::vector<Capacity>.
95 - \p StoreHashCount - constant that defines whether to store node hash values.
96 See cuckoo::store_hash option for explanation
97 - Tag - a tag used to distinguish between different implementation when two or more
98 \p node is needed in single struct.
100 template <typename ProbesetType = cuckoo::list, unsigned int StoreHashCount = 0, typename Tag = opt::none>
102 #ifdef CDS_DOXYGEN_INVOKED
104 typedef ProbesetType probeset_type ; ///< Probeset type
105 typedef Tag tag ; ///< Tag
106 static unsigned int const hash_array_size = StoreHashCount ; ///< The size of hash array
112 template <typename Tag>
113 struct node< cuckoo::list, 0, Tag>
115 typedef list_probeset_class probeset_class;
116 typedef cuckoo::list probeset_type;
118 static unsigned int const hash_array_size = 0;
119 static unsigned int const probeset_size = 0;
123 CDS_CONSTEXPR node() CDS_NOEXCEPT
127 void store_hash( size_t * )
130 size_t * get_hash() const
132 // This node type does not store hash values!!!
143 template <unsigned int StoreHashCount, typename Tag>
144 struct node< cuckoo::list, StoreHashCount, Tag>
146 typedef list_probeset_class probeset_class;
147 typedef cuckoo::list probeset_type;
149 static unsigned int const hash_array_size = StoreHashCount;
150 static unsigned int const probeset_size = 0;
153 size_t m_arrHash[ hash_array_size ];
158 memset( m_arrHash, 0, sizeof(m_arrHash));
161 void store_hash( size_t * pHashes )
163 memcpy( m_arrHash, pHashes, hash_array_size );
166 size_t * get_hash() const
168 return const_cast<size_t *>( m_arrHash );
178 template <unsigned int VectorSize, typename Tag>
179 struct node< cuckoo::vector<VectorSize>, 0, Tag>
181 typedef vector_probeset_class probeset_class;
182 typedef cuckoo::vector<VectorSize> probeset_type;
184 static unsigned int const hash_array_size = 0;
185 static unsigned int const probeset_size = probeset_type::c_nCapacity;
190 void store_hash( size_t * )
193 size_t * get_hash() const
195 // This node type does not store hash values!!!
204 template <unsigned int VectorSize, unsigned int StoreHashCount, typename Tag>
205 struct node< cuckoo::vector<VectorSize>, StoreHashCount, Tag>
207 typedef vector_probeset_class probeset_class;
208 typedef cuckoo::vector<VectorSize> probeset_type;
210 static unsigned int const hash_array_size = StoreHashCount;
211 static unsigned int const probeset_size = probeset_type::c_nCapacity;
213 size_t m_arrHash[ hash_array_size ];
217 memset( m_arrHash, 0, sizeof(m_arrHash));
220 void store_hash( size_t * pHashes )
222 memcpy( m_arrHash, pHashes, hash_array_size );
225 size_t * get_hash() const
227 return const_cast<size_t *>( m_arrHash );
237 struct default_hook {
238 typedef cuckoo::list probeset_type;
239 static unsigned int const store_hash = 0;
240 typedef opt::none tag;
243 template < typename HookType, CDS_DECL_OPTIONS3>
246 typedef typename opt::make_options< default_hook, CDS_OPTIONS3>::type options;
248 typedef typename options::probeset_type probeset_type;
249 typedef typename options::tag tag;
250 static unsigned int const store_hash = options::store_hash;
252 typedef node<probeset_type, store_hash, tag> node_type;
254 typedef HookType hook_type;
261 - cuckoo::probeset_type - probeset type. Defaul is \p cuckoo::list
262 - cuckoo::store_hash - store hash values in the node or not. Default is 0 (no storing)
263 - opt::tag - tag to distinguish different nodes in one struct. Default is opt::none
265 template < CDS_DECL_OPTIONS3 >
266 struct base_hook: public hook< opt::base_hook_tag, CDS_OPTIONS3 >
271 \p MemberOffset defines offset in bytes of \ref node member into your structure.
272 Use \p offsetof macro to define \p MemberOffset
275 - cuckoo::probeset_type - probeset type. Defaul is \p cuckoo::list
276 - cuckoo::store_hash - store hash values in the node or not. Default is 0 (no storing)
277 - opt::tag - tag to distinguish different nodes in one struct. Default is opt::none
279 template < size_t MemberOffset, CDS_DECL_OPTIONS3 >
280 struct member_hook: public hook< opt::member_hook_tag, CDS_OPTIONS3 >
283 static const size_t c_nMemberOffset = MemberOffset;
289 \p NodeTraits defines type traits for node.
290 See \ref node_traits for \p NodeTraits interface description
293 - cuckoo::probeset_type - probeset type. Defaul is \p cuckoo::list
294 - cuckoo::store_hash - store hash values in the node or not. Default is 0 (no storing)
295 - opt::tag - tag to distinguish different nodes in one struct. Default is opt::none
297 template <typename NodeTraits, CDS_DECL_OPTIONS3 >
298 struct traits_hook: public hook< opt::traits_hook_tag, CDS_OPTIONS3 >
301 typedef NodeTraits node_traits;
305 /// Internal statistics for \ref striping mutex policy
306 struct striping_stat {
307 typedef cds::atomicity::event_counter counter_type; ///< Counter type
309 counter_type m_nCellLockCount ; ///< Count of obtaining cell lock
310 counter_type m_nCellTryLockCount ; ///< Count of cell \p try_lock attempts
311 counter_type m_nFullLockCount ; ///< Count of obtaining full lock
312 counter_type m_nResizeLockCount ; ///< Count of obtaining resize lock
313 counter_type m_nResizeCount ; ///< Count of resize event
316 void onCellLock() { ++m_nCellLockCount; }
317 void onCellTryLock() { ++m_nCellTryLockCount; }
318 void onFullLock() { ++m_nFullLockCount; }
319 void onResizeLock() { ++m_nResizeLockCount; }
320 void onResize() { ++m_nResizeCount; }
324 /// Dummy internal statistics for \ref striping mutex policy
325 struct empty_striping_stat {
327 void onCellLock() const {}
328 void onCellTryLock() const {}
329 void onFullLock() const {}
330 void onResizeLock() const {}
331 void onResize() const {}
335 /// Lock striping concurrent access policy
337 This is one of available opt::mutex_policy option type for CuckooSet
339 Lock striping is very simple technique.
340 The cuckoo set consists of the bucket tables and the array of locks.
341 There is single lock array for each bucket table, at least, the count of bucket table is 2.
342 Initially, the capacity of lock array and each bucket table is the same.
343 When set is resized, bucket table capacity will be doubled but lock array will not.
344 The lock \p i protects each bucket \p j, where <tt> j = i mod L </tt>,
345 where \p L - the size of lock array.
347 The policy contains an internal array of \p RecursiveLock locks.
350 - \p RecursiveLock - the type of recursive mutex. The default is \p cds_std::recursive_mutex. The mutex type should be default-constructible.
351 Note that a recursive spin-lock is not suitable for lock striping for performance reason.
352 - \p Arity - unsigned int constant that specifies an arity. The arity is the count of hash functors, i.e., the
353 count of lock arrays. Default value is 2.
354 - \p Alloc - allocator type used for lock array memory allocation. Default is \p CDS_DEFAULT_ALLOCATOR.
355 - \p Stat - internal statistics type. Note that this template argument is automatically selected by \ref CuckooSet
356 class according to its \p opt::stat option.
359 class RecursiveLock = cds_std::recursive_mutex,
360 unsigned int Arity = 2,
361 class Alloc = CDS_DEFAULT_ALLOCATOR,
362 class Stat = empty_striping_stat
367 typedef RecursiveLock lock_type ; ///< lock type
368 typedef Alloc allocator_type ; ///< allocator type
369 static unsigned int const c_nArity = Arity ; ///< the arity
370 typedef Stat statistics_type ; ///< Internal statistics type (\ref striping_stat or \ref empty_striping_stat)
373 typedef striping_stat real_stat;
374 typedef empty_striping_stat empty_stat;
376 template <typename Stat2>
377 struct rebind_statistics {
378 typedef striping<lock_type, c_nArity, allocator_type, Stat2> other;
382 typedef cds::lock::array< lock_type, cds::lock::pow2_select_policy, allocator_type > lock_array_type ; ///< lock array type
386 class lock_array: public lock_array_type
390 lock_array(): lock_array_type( typename lock_array_type::select_cell_policy(2) ) {}
393 lock_array( size_t nCapacity ): lock_array_type( nCapacity, typename lock_array_type::select_cell_policy(nCapacity) ) {}
396 class scoped_lock: public cds::lock::scoped_lock< lock_array_type >
398 typedef cds::lock::scoped_lock< lock_array_type > base_class;
400 scoped_lock( lock_array& arrLock, size_t nHash ): base_class( arrLock, nHash ) {}
406 lock_array m_Locks[c_nArity] ; ///< array of lock_array_type
407 statistics_type m_Stat ; ///< internal statistics
412 class scoped_cell_lock {
413 lock_type * m_guard[c_nArity];
416 scoped_cell_lock( striping& policy, size_t const* arrHash )
418 for ( unsigned int i = 0; i < c_nArity; ++i ) {
419 m_guard[i] = &( policy.m_Locks[i].at( policy.m_Locks[i].lock( arrHash[i] )));
421 policy.m_Stat.onCellLock();
426 for ( unsigned int i = 0; i < c_nArity; ++i )
427 m_guard[i]->unlock();
431 class scoped_cell_trylock
433 typedef typename lock_array_type::lock_type lock_type;
435 lock_type * m_guard[c_nArity];
439 scoped_cell_trylock( striping& policy, size_t const* arrHash )
441 size_t nCell = policy.m_Locks[0].try_lock( arrHash[0] );
442 m_bLocked = nCell != lock_array_type::c_nUnspecifiedCell;
444 m_guard[0] = &(policy.m_Locks[0].at(nCell));
445 for ( unsigned int i = 1; i < c_nArity; ++i ) {
446 m_guard[i] = &( policy.m_Locks[i].at( policy.m_Locks[i].lock( arrHash[i] )) );
450 std::fill( m_guard, m_guard + c_nArity, nullptr );
452 policy.m_Stat.onCellTryLock();
454 ~scoped_cell_trylock()
457 for ( unsigned int i = 0; i < c_nArity; ++i )
458 m_guard[i]->unlock();
468 class scoped_full_lock {
469 cds::lock::scoped_lock< lock_array_type > m_guard;
471 scoped_full_lock( striping& policy )
472 : m_guard( policy.m_Locks[0] )
474 policy.m_Stat.onFullLock();
477 /// Ctor for scoped_resize_lock - no statistics is incremented
478 scoped_full_lock( striping& policy, bool )
479 : m_guard( policy.m_Locks[0] )
483 class scoped_resize_lock: public scoped_full_lock {
485 scoped_resize_lock( striping& policy )
486 : scoped_full_lock( policy, false )
488 policy.m_Stat.onResizeLock();
496 size_t nLockCount ///< The size of lock array. Must be power of two.
499 // Trick: initialize the array of locks
500 for ( unsigned int i = 0; i < c_nArity; ++i ) {
501 lock_array * pArr = m_Locks + i;
502 pArr->lock_array::~lock_array();
503 new ( pArr ) lock_array( nLockCount );
507 /// Returns lock array size
509 Lock array size is unchanged during \p striping object lifetime
511 size_t lock_count() const
513 return m_Locks[0].size();
517 void resize( size_t )
523 /// Returns the arity of striping mutex policy
524 CDS_CONSTEXPR unsigned int arity() const CDS_NOEXCEPT
529 /// Returns internal statistics
530 statistics_type const& statistics() const
536 /// Internal statistics for \ref refinable mutex policy
537 struct refinable_stat {
538 typedef cds::atomicity::event_counter counter_type ; ///< Counter type
540 counter_type m_nCellLockCount ; ///< Count of obtaining cell lock
541 counter_type m_nCellLockWaitResizing ; ///< Count of loop iteration to wait for resizing
542 counter_type m_nCellLockArrayChanged ; ///< Count of event "Lock array has been changed when obtaining cell lock"
543 counter_type m_nCellLockFailed ; ///< Count of event "Cell lock failed because of the array is owned by other thread"
545 counter_type m_nSecondCellLockCount ; ///< Count of obtaining cell lock when another cell is already locked
546 counter_type m_nSecondCellLockFailed ; ///< Count of unsuccess obtaining cell lock when another cell is already locked
548 counter_type m_nFullLockCount ; ///< Count of obtaining full lock
549 counter_type m_nFullLockIter ; ///< Count of unsuccessfull iteration to obtain full lock
551 counter_type m_nResizeLockCount ; ///< Count of obtaining resize lock
552 counter_type m_nResizeLockIter ; ///< Count of unsuccessfull iteration to obtain resize lock
553 counter_type m_nResizeLockArrayChanged; ///< Count of event "Lock array has been changed when obtaining resize lock"
554 counter_type m_nResizeCount ; ///< Count of resize event
557 void onCellLock() { ++m_nCellLockCount; }
558 void onCellWaitResizing() { ++m_nCellLockWaitResizing; }
559 void onCellArrayChanged() { ++m_nCellLockArrayChanged; }
560 void onCellLockFailed() { ++m_nCellLockFailed; }
561 void onSecondCellLock() { ++m_nSecondCellLockCount; }
562 void onSecondCellLockFailed() { ++m_nSecondCellLockFailed; }
563 void onFullLock() { ++m_nFullLockCount; }
564 void onFullLockIter() { ++m_nFullLockIter; }
565 void onResizeLock() { ++m_nResizeLockCount; }
566 void onResizeLockIter() { ++m_nResizeLockIter; }
567 void onResizeLockArrayChanged() { ++m_nResizeLockArrayChanged; }
568 void onResize() { ++m_nResizeCount; }
572 /// Dummy internal statistics for \ref refinable mutex policy
573 struct empty_refinable_stat {
575 void onCellLock() const {}
576 void onCellWaitResizing() const {}
577 void onCellArrayChanged() const {}
578 void onCellLockFailed() const {}
579 void onSecondCellLock() const {}
580 void onSecondCellLockFailed() const {}
581 void onFullLock() const {}
582 void onFullLockIter() const {}
583 void onResizeLock() const {}
584 void onResizeLockIter() const {}
585 void onResizeLockArrayChanged() const {}
586 void onResize() const {}
590 /// Refinable concurrent access policy
592 This is one of available opt::mutex_policy option type for CuckooSet
594 Refining is like a striping technique (see cuckoo::striping)
595 but it allows growing the size of lock array when resizing the hash table.
596 So, the sizes of hash table and lock array are equal.
599 - \p RecursiveLock - the type of mutex. Reentrant (recursive) mutex is required.
600 The default is \p cds_std::recursive_mutex. The mutex type should be default-constructible.
601 - \p Arity - unsigned int constant that specifies an arity. The arity is the count of hash functors, i.e., the
602 count of lock arrays. Default value is 2.
603 - \p BackOff - back-off strategy. Default is cds::backoff::yield
604 - \p Alloc - allocator type used for lock array memory allocation. Default is \p CDS_DEFAULT_ALLOCATOR.
605 - \p Stat - internal statistics type. Note that this template argument is automatically selected by \ref CuckooSet
606 class according to its \p opt::stat option.
609 class RecursiveLock = cds_std::recursive_mutex,
610 unsigned int Arity = 2,
611 typename BackOff = cds::backoff::yield,
612 class Alloc = CDS_DEFAULT_ALLOCATOR,
613 class Stat = empty_refinable_stat
618 typedef RecursiveLock lock_type ; ///< lock type
619 typedef Alloc allocator_type ; ///< allocator type
620 typedef BackOff back_off ; ///< back-off strategy
621 typedef Stat statistics_type ; ///< internal statistics type
622 static unsigned int const c_nArity = Arity; ///< the arity
625 typedef refinable_stat real_stat;
626 typedef empty_refinable_stat empty_stat;
628 template <typename Stat2>
629 struct rebind_statistics {
630 typedef refinable< lock_type, c_nArity, back_off, allocator_type, Stat2> other;
636 typedef cds::lock::trivial_select_policy lock_selection_policy;
638 class lock_array_type
639 : public cds::lock::array< lock_type, lock_selection_policy, allocator_type >
640 , public std::enable_shared_from_this< lock_array_type >
642 typedef cds::lock::array< lock_type, lock_selection_policy, allocator_type > lock_array_base;
644 lock_array_type( size_t nCapacity )
645 : lock_array_base( nCapacity )
648 typedef std::shared_ptr< lock_array_type > lock_array_ptr;
649 typedef cds::details::Allocator< lock_array_type, allocator_type > lock_array_allocator;
651 typedef unsigned long long owner_t;
652 typedef cds::OS::ThreadId threadId_t;
654 typedef cds::lock::Spin spinlock_type;
655 typedef cds::lock::scoped_lock< spinlock_type > scoped_spinlock;
660 static owner_t const c_nOwnerMask = (((owner_t) 1) << (sizeof(owner_t) * 8 - 1)) - 1;
662 CDS_ATOMIC::atomic< owner_t > m_Owner ; ///< owner mark (thread id + boolean flag)
663 CDS_ATOMIC::atomic<size_t> m_nCapacity ; ///< lock array capacity
664 lock_array_ptr m_arrLocks[ c_nArity ] ; ///< Lock array. The capacity of array is specified in constructor.
665 spinlock_type m_access ; ///< access to m_arrLocks
666 statistics_type m_Stat ; ///< internal statistics
671 struct lock_array_disposer {
672 void operator()( lock_array_type * pArr )
674 lock_array_allocator().Delete( pArr );
678 lock_array_ptr create_lock_array( size_t nCapacity )
680 return lock_array_ptr( lock_array_allocator().New( nCapacity ), lock_array_disposer() );
683 void acquire( size_t const * arrHash, lock_array_ptr * pLockArr, lock_type ** parrLock )
685 owner_t me = (owner_t) cds::OS::getCurrentThreadId();
692 scoped_spinlock sl(m_access);
693 for ( unsigned int i = 0; i < c_nArity; ++i )
694 pLockArr[i] = m_arrLocks[i];
697 // wait while resizing
699 who = m_Owner.load( CDS_ATOMIC::memory_order_acquire );
700 if ( !( who & 1 ) || (who >> 1) == (me & c_nOwnerMask) )
703 m_Stat.onCellWaitResizing();
706 if ( pLockArr[0] != m_arrLocks[0] ) {
707 m_Stat.onCellArrayChanged();
711 size_t const nMask = pLockArr[0]->size() - 1;
712 assert( cds::beans::is_power2( nMask + 1 ));
714 for ( unsigned int i = 0; i < c_nArity; ++i ) {
715 parrLock[i] = &( pLockArr[i]->at( arrHash[i] & nMask ));
719 who = m_Owner.load( CDS_ATOMIC::memory_order_acquire );
720 if ( ( !(who & 1) || (who >> 1) == (me & c_nOwnerMask) ) && m_arrLocks[0] == pLockArr[0] ) {
725 for ( unsigned int i = 0; i < c_nArity; ++i ) {
726 parrLock[i]->unlock();
729 m_Stat.onCellLockFailed();
732 // clears pLockArr can lead to calling dtor for each item of pLockArr[i] that may be a heavy-weighted operation
733 // (each pLockArr[i] is a shared pointer to array of a ton of mutexes)
734 // It is better to do this before the next loop iteration where we will use spin-locked assignment to pLockArr
735 // Destructing a lot of mutexes under spin-lock is a bad solution
736 for ( unsigned int i = 0; i < c_nArity; ++i )
741 bool try_second_acquire( size_t const * arrHash, lock_type ** parrLock )
743 // It is assumed that the current thread already has a lock
744 // and requires a second lock for other hash
746 size_t const nMask = m_nCapacity.load(CDS_ATOMIC::memory_order_acquire) - 1;
747 size_t nCell = m_arrLocks[0]->try_lock( arrHash[0] & nMask);
748 if ( nCell == lock_array_type::c_nUnspecifiedCell ) {
749 m_Stat.onSecondCellLockFailed();
752 parrLock[0] = &(m_arrLocks[0]->at(nCell));
754 for ( unsigned int i = 1; i < c_nArity; ++i ) {
755 parrLock[i] = &( m_arrLocks[i]->at( m_arrLocks[i]->lock( arrHash[i] & nMask)) );
758 m_Stat.onSecondCellLock();
764 owner_t me = (owner_t) cds::OS::getCurrentThreadId();
769 if ( m_Owner.compare_exchange_strong( ownNull, (me << 1) | 1, CDS_ATOMIC::memory_order_acq_rel, CDS_ATOMIC::memory_order_relaxed )) {
770 m_arrLocks[0]->lock_all();
776 m_Stat.onFullLockIter();
782 m_arrLocks[0]->unlock_all();
783 m_Owner.store( 0, CDS_ATOMIC::memory_order_release );
786 void acquire_resize( lock_array_ptr * pOldLocks )
788 owner_t me = (owner_t) cds::OS::getCurrentThreadId();
792 scoped_spinlock sl(m_access);
793 for ( unsigned int i = 0; i < c_nArity; ++i )
794 pOldLocks[i] = m_arrLocks[i];
799 if ( m_Owner.compare_exchange_strong( ownNull, (me << 1) | 1, CDS_ATOMIC::memory_order_acq_rel, CDS_ATOMIC::memory_order_relaxed )) {
800 if ( pOldLocks[0] != m_arrLocks[0] ) {
801 m_Owner.store( 0, CDS_ATOMIC::memory_order_release );
802 m_Stat.onResizeLockArrayChanged();
805 pOldLocks[0]->lock_all();
806 m_Stat.onResizeLock();
811 m_Stat.onResizeLockIter();
813 // clears pOldLocks can lead to calling dtor for each item of pOldLocks[i] that may be a heavy-weighted operation
814 // (each pOldLocks[i] is a shared pointer to array of a ton of mutexes)
815 // It is better to do this before the next loop iteration where we will use spin-locked assignment to pOldLocks
816 // Destructing a lot of mutexes under spin-lock is a bad solution
817 for ( unsigned int i = 0; i < c_nArity; ++i )
818 pOldLocks[i].reset();
822 void release_resize( lock_array_ptr * pOldLocks )
824 m_Owner.store( 0, CDS_ATOMIC::memory_order_release );
825 pOldLocks[0]->unlock_all();
831 class scoped_cell_lock {
832 lock_type * m_arrLock[ c_nArity ];
833 lock_array_ptr m_arrLockArr[ c_nArity ];
836 scoped_cell_lock( refinable& policy, size_t const* arrHash )
838 policy.acquire( arrHash, m_arrLockArr, m_arrLock );
843 for ( unsigned int i = 0; i < c_nArity; ++i )
844 m_arrLock[i]->unlock();
848 class scoped_cell_trylock {
849 lock_type * m_arrLock[ c_nArity ];
853 scoped_cell_trylock( refinable& policy, size_t const* arrHash )
855 m_bLocked = policy.try_second_acquire( arrHash, m_arrLock );
858 ~scoped_cell_trylock()
861 for ( unsigned int i = 0; i < c_nArity; ++i )
862 m_arrLock[i]->unlock();
872 class scoped_full_lock {
875 scoped_full_lock( refinable& policy )
878 policy.acquire_all();
882 m_policy.release_all();
886 class scoped_resize_lock
889 lock_array_ptr m_arrLocks[ c_nArity ];
891 scoped_resize_lock( refinable& policy )
894 policy.acquire_resize( m_arrLocks );
896 ~scoped_resize_lock()
898 m_policy.release_resize( m_arrLocks );
906 size_t nLockCount ///< The size of lock array. Must be power of two.
908 , m_nCapacity( nLockCount )
910 assert( cds::beans::is_power2( nLockCount ));
911 for ( unsigned int i = 0; i < c_nArity; ++i )
912 m_arrLocks[i] = create_lock_array( nLockCount );
916 void resize( size_t nCapacity )
918 lock_array_ptr pNew[ c_nArity ];
919 for ( unsigned int i = 0; i < c_nArity; ++i )
920 pNew[i] = create_lock_array( nCapacity );
923 // Assignment m_arrLocks[i] = pNew[i] may call heavy-weighted dtor for each item of m_arrLocks
924 // that is unacceptable under spin-lock
925 // So, we store copy of m_arrLocks in pOld
926 lock_array_ptr pOld[ c_nArity ];
927 for ( unsigned int i = 0; i < c_nArity; ++i )
928 pOld[i] = m_arrLocks[i];
930 // m_arrLocks assignment will not lead to calling dtor of each item of m_arrLocks
931 // since copy of m_arrLocks locates in pOld and assignment will not be too painful for spin-lock
935 scoped_spinlock sl(m_access);
936 for ( unsigned int i = 0; i < c_nArity; ++i )
937 m_arrLocks[i] = pNew[i];
939 m_nCapacity.store( nCapacity, CDS_ATOMIC::memory_order_release );
945 /// Returns lock array size
947 Lock array size is not a constant for \p refinable policy and can be changed when the set is resized.
949 size_t lock_count() const
951 return m_nCapacity.load(CDS_ATOMIC::memory_order_relaxed);
954 /// Returns the arity of \p refinable mutex policy
955 CDS_CONSTEXPR unsigned int arity() const CDS_NOEXCEPT
960 /// Returns internal statistics
961 statistics_type const& statistics() const
967 /// CuckooSet internal statistics
969 typedef cds::atomicity::event_counter counter_type ; ///< Counter type
971 counter_type m_nRelocateCallCount ; ///< Count of \p relocate function call
972 counter_type m_nRelocateRoundCount ; ///< Count of attempts to relocate items
973 counter_type m_nFalseRelocateCount ; ///< Count of unneeded attempts of \p relocate call
974 counter_type m_nSuccessRelocateCount ; ///< Count of successfull item relocating
975 counter_type m_nRelocateAboveThresholdCount; ///< Count of item relocating above probeset threshold
976 counter_type m_nFailedRelocateCount ; ///< Count of failed relocation attemp (when all probeset is full)
978 counter_type m_nResizeCallCount ; ///< Count of \p resize function call
979 counter_type m_nFalseResizeCount ; ///< Count of false \p resize function call (when other thread has been resized the set)
980 counter_type m_nResizeSuccessNodeMove; ///< Count of successfull node moving when resizing
981 counter_type m_nResizeRelocateCall ; ///< Count of \p relocate function call from \p resize function
983 counter_type m_nInsertSuccess ; ///< Count of successfull \p insert function call
984 counter_type m_nInsertFailed ; ///< Count of failed \p insert function call
985 counter_type m_nInsertResizeCount ; ///< Count of \p resize function call from \p insert
986 counter_type m_nInsertRelocateCount ; ///< Count of \p relocate function call from \p insert
987 counter_type m_nInsertRelocateFault ; ///< Count of failed \p relocate function call from \p insert
989 counter_type m_nEnsureExistCount ; ///< Count of call \p ensure function for existing node
990 counter_type m_nEnsureSuccessCount ; ///< Count of successfull \p insert function call for new node
991 counter_type m_nEnsureResizeCount ; ///< Count of \p resize function call from \p ensure
992 counter_type m_nEnsureRelocateCount ; ///< Count of \p relocate function call from \p ensure
993 counter_type m_nEnsureRelocateFault ; ///< Count of failed \p relocate function call from \p ensure
995 counter_type m_nUnlinkSuccess ; ///< Count of success \p unlink function call
996 counter_type m_nUnlinkFailed ; ///< Count of failed \p unlink function call
998 counter_type m_nEraseSuccess ; ///< Count of success \p erase function call
999 counter_type m_nEraseFailed ; ///< Count of failed \p erase function call
1001 counter_type m_nFindSuccess ; ///< Count of success \p find function call
1002 counter_type m_nFindFailed ; ///< Count of failed \p find function call
1004 counter_type m_nFindEqualSuccess ; ///< Count of success \p find_equal function call
1005 counter_type m_nFindEqualFailed ; ///< Count of failed \p find_equal function call
1007 counter_type m_nFindWithSuccess ; ///< Count of success \p find_with function call
1008 counter_type m_nFindWithFailed ; ///< Count of failed \p find_with function call
1011 void onRelocateCall() { ++m_nRelocateCallCount; }
1012 void onRelocateRound() { ++m_nRelocateRoundCount; }
1013 void onFalseRelocateRound() { ++m_nFalseRelocateCount; }
1014 void onSuccessRelocateRound(){ ++m_nSuccessRelocateCount; }
1015 void onRelocateAboveThresholdRound() { ++m_nRelocateAboveThresholdCount; }
1016 void onFailedRelocate() { ++m_nFailedRelocateCount; }
1018 void onResizeCall() { ++m_nResizeCallCount; }
1019 void onFalseResizeCall() { ++m_nFalseResizeCount; }
1020 void onResizeSuccessMove() { ++m_nResizeSuccessNodeMove; }
1021 void onResizeRelocateCall() { ++m_nResizeRelocateCall; }
1023 void onInsertSuccess() { ++m_nInsertSuccess; }
1024 void onInsertFailed() { ++m_nInsertFailed; }
1025 void onInsertResize() { ++m_nInsertResizeCount; }
1026 void onInsertRelocate() { ++m_nInsertRelocateCount; }
1027 void onInsertRelocateFault() { ++m_nInsertRelocateFault; }
1029 void onEnsureExist() { ++m_nEnsureExistCount; }
1030 void onEnsureSuccess() { ++m_nEnsureSuccessCount; }
1031 void onEnsureResize() { ++m_nEnsureResizeCount; }
1032 void onEnsureRelocate() { ++m_nEnsureRelocateCount; }
1033 void onEnsureRelocateFault() { ++m_nEnsureRelocateFault; }
1035 void onUnlinkSuccess() { ++m_nUnlinkSuccess; }
1036 void onUnlinkFailed() { ++m_nUnlinkFailed; }
1038 void onEraseSuccess() { ++m_nEraseSuccess; }
1039 void onEraseFailed() { ++m_nEraseFailed; }
1041 void onFindSuccess() { ++m_nFindSuccess; }
1042 void onFindFailed() { ++m_nFindFailed; }
1044 void onFindWithSuccess() { ++m_nFindWithSuccess; }
1045 void onFindWithFailed() { ++m_nFindWithFailed; }
1049 /// CuckooSet empty internal statistics
1052 void onRelocateCall() const {}
1053 void onRelocateRound() const {}
1054 void onFalseRelocateRound() const {}
1055 void onSuccessRelocateRound()const {}
1056 void onRelocateAboveThresholdRound() const {}
1057 void onFailedRelocate() const {}
1059 void onResizeCall() const {}
1060 void onFalseResizeCall() const {}
1061 void onResizeSuccessMove() const {}
1062 void onResizeRelocateCall() const {}
1064 void onInsertSuccess() const {}
1065 void onInsertFailed() const {}
1066 void onInsertResize() const {}
1067 void onInsertRelocate() const {}
1068 void onInsertRelocateFault() const {}
1070 void onEnsureExist() const {}
1071 void onEnsureSuccess() const {}
1072 void onEnsureResize() const {}
1073 void onEnsureRelocate() const {}
1074 void onEnsureRelocateFault() const {}
1076 void onUnlinkSuccess() const {}
1077 void onUnlinkFailed() const {}
1079 void onEraseSuccess() const {}
1080 void onEraseFailed() const {}
1082 void onFindSuccess() const {}
1083 void onFindFailed() const {}
1085 void onFindWithSuccess() const {}
1086 void onFindWithFailed() const {}
1090 /// Type traits for CuckooSet class
1095 Possible values are: cuckoo::base_hook, cuckoo::member_hook, cuckoo::traits_hook.
1097 typedef base_hook<> hook;
1099 /// Hash functors tuple
1101 This is mandatory type and has no predefined one.
1103 At least, two hash functors should be provided. All hash functor
1104 should be orthogonal (different): for each <tt> i,j: i != j => h[i](x) != h[j](x) </tt>.
1105 The hash functors are defined as <tt> std::tuple< H1, H2, ... Hn > </tt>:
1106 \@code cds::opt::hash< std::tuple< h1, h2 > > \@endcode
1107 The number of hash functors specifies the number \p k - the count of hash tables in cuckoo hashing.
1108 Up to 10 different hash functors are supported.
1110 typedef cds::opt::none hash;
1112 /// Concurrent access policy
1114 Available opt::mutex_policy types:
1115 - cuckoo::striping - simple, but the lock array is not resizable
1116 - cuckoo::refinable - resizable lock array, but more complex access to set data.
1118 Default is cuckoo::striping.
1120 typedef cuckoo::striping<> mutex_policy;
1122 /// Key equality functor
1124 Default is <tt>std::equal_to<T></tt>
1126 typedef opt::none equal_to;
1128 /// Key comparison functor
1130 No default functor is provided. If the option is not specified, the \p less is used.
1132 typedef opt::none compare;
1134 /// specifies binary predicate used for key comparison.
1136 Default is \p std::less<T>.
1138 typedef opt::none less;
1142 The type for item counting feature.
1143 Default is cds::atomicity::item_counter
1145 Only atomic item counter type is allowed.
1147 typedef atomicity::item_counter item_counter;
1151 The allocator type for allocating bucket tables.
1153 typedef CDS_DEFAULT_ALLOCATOR allocator;
1157 The disposer functor is used in CuckooSet::clear member function
1160 typedef intrusive::opt::v::empty_disposer disposer;
1162 /// Internal statistics. Available statistics: cuckoo::stat, cuckoo::empty_stat
1163 typedef empty_stat stat;
1166 /// Metafunction converting option list to CuckooSet traits
1168 This is a wrapper for <tt> cds::opt::make_options< type_traits, Options...> </tt>
1169 \p Options list see \ref CuckooSet.
1171 template <CDS_DECL_OPTIONS11>
1172 struct make_traits {
1173 typedef typename cds::opt::make_options<
1174 typename cds::opt::find_type_traits< cuckoo::type_traits, CDS_OPTIONS10 >::type
1176 >::type type ; ///< Result of metafunction
1181 template <typename Node, typename Probeset>
1184 template <typename Node>
1185 class bucket_entry<Node, cuckoo::list>
1188 typedef Node node_type;
1189 typedef cuckoo::list_probeset_class probeset_class;
1190 typedef cuckoo::list probeset_type;
1200 friend class bucket_entry;
1206 iterator( node_type * p )
1209 iterator( iterator const& it)
1213 iterator& operator=( iterator const& it )
1219 iterator& operator=( node_type * p )
1225 node_type * operator->()
1229 node_type& operator*()
1231 assert( pNode != nullptr );
1236 iterator& operator ++()
1239 pNode = pNode->m_pNext;
1243 bool operator==(iterator const& it ) const
1245 return pNode == it.pNode;
1247 bool operator!=(iterator const& it ) const
1249 return !( *this == it );
1258 static_assert(( std::is_same<typename node_type::probeset_type, probeset_type>::value ), "Incompatible node type" );
1263 return iterator(pHead);
1270 void insert_after( iterator it, node_type * p )
1272 node_type * pPrev = it.pNode;
1274 p->m_pNext = pPrev->m_pNext;
1285 void remove( iterator itPrev, iterator itWhat )
1287 node_type * pPrev = itPrev.pNode;
1288 node_type * pWhat = itWhat.pNode;
1289 assert( (!pPrev && pWhat == pHead) || (pPrev && pPrev->m_pNext == pWhat) );
1292 pPrev->m_pNext = pWhat->m_pNext;
1294 assert( pWhat == pHead );
1295 pHead = pHead->m_pNext;
1304 for ( node_type * pNode = pHead; pNode; pNode = pNext ) {
1305 pNext = pNode->m_pNext;
1313 template <typename Disposer>
1314 void clear( Disposer disp )
1317 for ( node_type * pNode = pHead; pNode; pNode = pNext ) {
1318 pNext = pNode->m_pNext;
1320 cds::unref(disp)( pNode );
1327 unsigned int size() const
1333 template <typename Node, unsigned int Capacity>
1334 class bucket_entry<Node, cuckoo::vector<Capacity> >
1337 typedef Node node_type;
1338 typedef cuckoo::vector_probeset_class probeset_class;
1339 typedef cuckoo::vector<Capacity> probeset_type;
1341 static unsigned int const c_nCapacity = probeset_type::c_nCapacity;
1344 node_type * m_arrNode[c_nCapacity];
1345 unsigned int m_nSize;
1347 void shift_up( unsigned int nFrom )
1349 assert( m_nSize < c_nCapacity );
1352 if ( nFrom < m_nSize )
1353 std::copy_backward( m_arrNode + nFrom, m_arrNode + m_nSize, m_arrNode + m_nSize + 1 );
1355 // alternative: low-level byte copying
1356 //memmove( m_arrNode + nFrom + 1, m_arrNode + nFrom, (m_nSize - nFrom) * sizeof(m_arrNode[0]) );
1359 void shift_down( node_type ** pFrom )
1361 assert( m_arrNode <= pFrom && pFrom < m_arrNode + m_nSize);
1363 std::copy( pFrom + 1, m_arrNode + m_nSize, pFrom );
1365 // alternative: low-level byte copying
1366 //memmove( pFrom + 1, pFrom, (m_nSize - nFrom - 1) * sizeof(m_arrNode[0]));
1372 friend class bucket_entry;
1378 iterator( node_type ** p )
1381 iterator( iterator const& it)
1385 iterator& operator=( iterator const& it )
1391 node_type * operator->()
1393 assert( pArr != nullptr );
1396 node_type& operator*()
1398 assert( pArr != nullptr );
1399 assert( *pArr != nullptr );
1404 iterator& operator ++()
1410 bool operator==(iterator const& it ) const
1412 return pArr == it.pArr;
1414 bool operator!=(iterator const& it ) const
1416 return !( *this == it );
1424 memset( m_arrNode, 0, sizeof(m_arrNode));
1425 static_assert(( std::is_same<typename node_type::probeset_type, probeset_type>::value ), "Incompatible node type" );
1430 return iterator(m_arrNode);
1434 return iterator(m_arrNode + size());
1437 void insert_after( iterator it, node_type * p )
1439 assert( m_nSize < c_nCapacity );
1440 assert( !it.pArr || (m_arrNode <= it.pArr && it.pArr <= m_arrNode + m_nSize));
1443 shift_up( (unsigned int)(it.pArr - m_arrNode) + 1 );
1453 void remove( iterator /*itPrev*/, iterator itWhat )
1456 shift_down( itWhat.pArr );
1465 template <typename Disposer>
1466 void clear( Disposer disp )
1468 for ( unsigned int i = 0; i < m_nSize; ++i ) {
1469 cds::unref(disp)( m_arrNode[i] );
1474 unsigned int size() const
1480 template <typename Node, unsigned int ArraySize>
1482 static void store( Node * pNode, size_t * pHashes )
1484 memcpy( pNode->m_arrHash, pHashes, sizeof(size_t) * ArraySize );
1486 static bool equal_to( Node& node, unsigned int nTable, size_t nHash )
1488 return node.m_arrHash[nTable] == nHash;
1491 template <typename Node>
1492 struct hash_ops<Node, 0>
1494 static void store( Node * /*pNode*/, size_t * /*pHashes*/ )
1496 static bool equal_to( Node& /*node*/, unsigned int /*nTable*/, size_t /*nHash*/ )
1502 template <typename NodeTraits, bool Ordered>
1505 template <typename NodeTraits>
1506 struct contains<NodeTraits, true>
1508 template <typename BucketEntry, typename Position, typename Q, typename Compare>
1509 static bool find( BucketEntry& probeset, Position& pos, unsigned int nTable, size_t nHash, Q const& val, Compare cmp )
1512 typedef typename BucketEntry::iterator bucket_iterator;
1514 bucket_iterator itPrev;
1516 for ( bucket_iterator it = probeset.begin(), itEnd = probeset.end(); it != itEnd; ++it ) {
1517 int cmpRes = cmp( *NodeTraits::to_value_ptr(*it), val );
1518 if ( cmpRes >= 0 ) {
1520 pos.itPrev = itPrev;
1527 pos.itPrev = itPrev;
1528 pos.itFound = probeset.end();
1533 template <typename NodeTraits>
1534 struct contains<NodeTraits, false>
1536 template <typename BucketEntry, typename Position, typename Q, typename EqualTo>
1537 static bool find( BucketEntry& probeset, Position& pos, unsigned int nTable, size_t nHash, Q const& val, EqualTo eq )
1539 // Unordered version
1540 typedef typename BucketEntry::iterator bucket_iterator;
1541 typedef typename BucketEntry::node_type node_type;
1543 bucket_iterator itPrev;
1545 for ( bucket_iterator it = probeset.begin(), itEnd = probeset.end(); it != itEnd; ++it ) {
1546 if ( hash_ops<node_type, node_type::hash_array_size>::equal_to( *it, nTable, nHash ) && eq( *NodeTraits::to_value_ptr(*it), val )) {
1548 pos.itPrev = itPrev;
1554 pos.itPrev = itPrev;
1555 pos.itFound = probeset.end();
1560 } // namespace details
1563 } // namespace cuckoo
1566 /** @ingroup cds_intrusive_map
1569 - [2007] M.Herlihy, N.Shavit, M.Tzafrir "Concurrent Cuckoo Hashing. Technical report"
1570 - [2008] Maurice Herlihy, Nir Shavit "The Art of Multiprocessor Programming"
1572 <b>About Cuckoo hashing</b>
1574 [From <i>"The Art of Multiprocessor Programming"</i>]
1575 Cuckoo hashing is a hashing algorithm in which a newly added item displaces any earlier item
1576 occupying the same slot. For brevity, a table is a k-entry array of items. For a hash set f size
1577 N = 2k we use a two-entry array of tables, and two independent hash functions,
1578 <tt> h0, h1: KeyRange -> 0,...,k-1</tt>
1579 mapping the set of possible keys to entries in he array. To test whether a value \p x is in the set,
1580 <tt>find(x)</tt> tests whether either <tt>table[0][h0(x)]</tt> or <tt>table[1][h1(x)]</tt> is
1581 equal to \p x. Similarly, <tt>erase(x)</tt>checks whether \p x is in either <tt>table[0][h0(x)]</tt>
1582 or <tt>table[1][h1(x)]</tt>, ad removes it if found.
1584 The <tt>insert(x)</tt> successively "kicks out" conflicting items until every key has a slot.
1585 To add \p x, the method swaps \p x with \p y, the current occupant of <tt>table[0][h0(x)]</tt>.
1586 If the prior value was \p NULL, it is done. Otherwise, it swaps the newly nest-less value \p y
1587 for the current occupant of <tt>table[1][h1(y)]</tt> in the same way. As before, if the prior value
1588 was \p NULL, it is done. Otherwise, the method continues swapping entries (alternating tables)
1589 until it finds an empty slot. We might not find an empty slot, either because the table is full,
1590 or because the sequence of displacement forms a cycle. We therefore need an upper limit on the
1591 number of successive displacements we are willing to undertake. When this limit is exceeded,
1592 we resize the hash table, choose new hash functions and start over.
1594 For concurrent cuckoo hashing, rather than organizing the set as a two-dimensional table of
1595 items, we use two-dimensional table of probe sets, where a probe set is a constant-sized set
1596 of items with the same hash code. Each probe set holds at most \p PROBE_SIZE items, but the algorithm
1597 tries to ensure that when the set is quiescent (i.e no method call in progress) each probe set
1598 holds no more than <tt>THRESHOLD < PROBE_SET</tt> items. While method calls are in-flight, a probe
1599 set may temporarily hold more than \p THRESHOLD but never more than \p PROBE_SET items.
1601 In current implementation, a probe set can be defined either as a (single-linked) list
1602 or as a fixed-sized vector, optionally ordered.
1604 In description above two-table cuckoo hashing (<tt>k = 2</tt>) has been considered.
1605 We can generalize this approach for <tt>k >= 2</tt> when we have \p k hash functions
1606 <tt>h[0], ... h[k-1]</tt> and \p k tables <tt>table[0], ... table[k-1]</tt>.
1608 The search in probe set is linear, the complexity is <tt> O(PROBE_SET) </tt>.
1609 The probe set may be ordered or not. Ordered probe set can be more efficient since
1610 the average search complexity is <tt>O(PROBE_SET/2)</tt>.
1611 However, the overhead of sorting can eliminate a gain of ordered search.
1613 The probe set is ordered if opt::compare or opt::less is specified in \p Traits template
1614 parameter. Otherwise, the probe set is unordered and \p Traits must contain
1615 opt::equal_to option.
1617 The cds::intrusive::cuckoo namespace contains \p %CuckooSet-related declarations.
1620 - \p T - the type stored in the set. The type must be based on cuckoo::node (for cuckoo::base_hook)
1621 or it must have a member of type %cuckoo::node (for cuckoo::member_hook),
1622 or it must be convertible to \p %cuckoo::node (for cuckoo::traits_hook)
1623 - \p Traits - type traits. See cuckoo::type_traits for explanation. It is possible to declare option-based
1624 set with cuckoo::make_traits metafunction result as \p Traits template argument.
1626 Template argument list \p Options... of cuckoo::make_traits metafunction are:
1627 - intrusive::opt::hook - hook used. Possible values are: cuckoo::base_hook, cuckoo::member_hook, cuckoo::traits_hook.
1628 If the option is not specified, <tt>%cuckoo::base_hook<></tt> is used.
1629 - opt::hash - hash functor tuple, mandatory option. At least, two hash functors should be provided. All hash functor
1630 should be orthogonal (different): for each <tt> i,j: i != j => h[i](x) != h[j](x) </tt>.
1631 The hash functors are passed as <tt> std::tuple< H1, H2, ... Hn > </tt>. The number of hash functors specifies
1632 the number \p k - the count of hash tables in cuckoo hashing. If the compiler supports variadic templates
1633 then k is unlimited, otherwise up to 10 different hash functors are supported.
1634 - opt::mutex_policy - concurrent access policy.
1635 Available policies: cuckoo::striping, cuckoo::refinable.
1636 Default is cuckoo::striping.
1637 - opt::equal_to - key equality functor like \p std::equal_to.
1638 If this functor is defined then the probe-set will be unordered.
1639 If opt::compare or opt::less option is specified too, then the probe-set will be ordered
1640 and opt::equal_to will be ignored.
1641 - opt::compare - key comparison functor. No default functor is provided.
1642 If the option is not specified, the opt::less is used.
1643 If opt::compare or opt::less option is specified, then the probe-set will be ordered.
1644 - opt::less - specifies binary predicate used for key comparison. Default is \p std::less<T>.
1645 If opt::compare or opt::less option is specified, then the probe-set will be ordered.
1646 - opt::item_counter - the type of item counting feature. Default is \ref atomicity::item_counter
1647 The item counter should be atomic.
1648 - opt::allocator - the allocator type using for allocating bucket tables.
1649 Default is \p CDS_DEFAULT_ALLOCATOR
1650 - intrusive::opt::disposer - the disposer type used in \ref clear() member function for
1651 freeing nodes. Default is intrusive::opt::v::empty_disposer
1652 - opt::stat - internal statistics. Possibly types: cuckoo::stat, cuckoo::empty_stat.
1653 Default is cuckoo::empty_stat
1655 The probe set options cuckoo::probeset_type and cuckoo::store_hash are taken from \p node type
1656 specified by \p opt::hook option.
1660 You should incorporate cuckoo::node into your struct \p T and provide
1661 appropriate cuckoo::type_traits::hook in your \p Traits template parameters. Usually, for \p Traits you
1662 define a struct based on cuckoo::type_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::type_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 std::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::type_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 std::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::type_traits>
1843 typedef T value_type ; ///< The value type stored in the set
1844 typedef Traits options ; ///< Set traits
1846 typedef typename options::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 options::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 options::stat stat ; ///< internal statistics type
1855 typedef typename options::mutex_policy original_mutex_policy ; ///< Concurrent access policy, see cuckoo::type_traits::mutex_policy
1857 /// Actual mutex policy
1859 Actual mutex policy is built from mutex policy type provided by \p Traits template argument (see cuckoo::type_traits::mutex_policy)
1860 but mutex policy internal statistics is conformed with cukoo::type_traits::stat type provided by \p Traits:
1861 - if \p %cuckoo::type_traits::stat is cuckoo::empty_stat then mutex policy statistics is already empty one
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 options::compare, opt::none >::value
1873 && std::is_same< typename options::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, options, !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, options >::type key_comparator;
1883 typedef typename options::allocator allocator;
1885 /// item counter type
1886 typedef typename options::item_counter item_counter;
1889 typedef typename options::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
1908 # ifndef CDS_CXX11_LAMBDA_SUPPORT
1909 struct empty_insert_functor {
1910 void operator()( value_type& )
1914 struct empty_erase_functor {
1915 void operator()( value_type const& )
1919 struct empty_find_functor {
1920 template <typename Q>
1921 void operator()( value_type& item, Q& val )
1926 # if !defined(CDS_CXX11_LAMBDA_SUPPORT) || ((CDS_COMPILER == CDS_COMPILER_MSVC || CDS_COMPILER == CDS_COMPILER_INTEL ) && _MSC_VER == 1600)
1927 template <typename Disposer>
1928 class disposer_wrapper: protected cds::details::functor_wrapper<Disposer>
1930 typedef cds::details::functor_wrapper<Disposer> base_class;
1932 disposer_wrapper( Disposer d): base_class(d) {}
1934 void operator()( node_type * pNode )
1936 base_class::get()( node_traits::to_value_ptr( pNode ));
1942 bucket_iterator itPrev;
1943 bucket_iterator itFound;
1946 typedef typename std::conditional< c_isSorted
1947 , cuckoo::details::contains< node_traits, true >
1948 , cuckoo::details::contains< node_traits, false >
1949 >::type contains_action;
1951 template <typename Predicate>
1952 struct predicate_wrapper {
1953 typedef typename std::conditional< c_isSorted, cds::opt::details::make_comparator_from_less<Predicate>, Predicate>::type type;
1956 typedef typename std::conditional< c_isSorted, key_comparator, key_equal_to >::type key_predicate;
1960 static unsigned int const c_nDefaultProbesetSize = 4 ; ///< default probeset size
1961 static size_t const c_nDefaultInitialSize = 16 ; ///< default initial size
1962 static unsigned int const c_nRelocateLimit = c_nArity * 2 - 1 ; ///< Count of attempts to relocate before giving up
1965 bucket_entry * m_BucketTable[ c_nArity ] ; ///< Bucket tables
1967 size_t m_nBucketMask ; ///< Hash bitmask; bucket table size minus 1.
1968 unsigned int const m_nProbesetSize ; ///< Probe set size
1969 unsigned int const m_nProbesetThreshold ; ///< Probe set threshold
1971 hash m_Hash ; ///< Hash functor tuple
1972 mutex_policy m_MutexPolicy ; ///< concurrent access policy
1973 item_counter m_ItemCounter ; ///< item counter
1974 mutable stat m_Stat ; ///< internal statistics
1978 static void check_common_constraints()
1980 static_assert( (c_nArity == mutex_policy::c_nArity), "The count of hash functors must be equal to mutex_policy arity" );
1983 void check_probeset_properties() const
1985 assert( m_nProbesetThreshold < m_nProbesetSize );
1987 // if probe set type is cuckoo::vector<N> then m_nProbesetSize == N
1988 assert( node_type::probeset_size == 0 || node_type::probeset_size == m_nProbesetSize );
1991 template <typename Q>
1992 void hashing( size_t * pHashes, Q const& v ) const
1994 m_Hash( pHashes, v );
1997 void copy_hash( size_t * pHashes, value_type const& v ) const
1999 if ( c_nNodeHashArraySize )
2000 memcpy( pHashes, node_traits::to_node_ptr( v )->get_hash(), sizeof(pHashes[0]) * c_nNodeHashArraySize );
2002 hashing( pHashes, v );
2005 bucket_entry& bucket( unsigned int nTable, size_t nHash )
2007 assert( nTable < c_nArity );
2008 return m_BucketTable[nTable][nHash & m_nBucketMask];
2011 static void store_hash( node_type * pNode, size_t * pHashes )
2013 cuckoo::details::hash_ops< node_type, c_nNodeHashArraySize >::store( pNode, pHashes );
2014 //memcpy( pNode->m_arrHash, pHashes, sizeof(size_t) * c_nArity );
2017 static bool equal_hash( node_type& node, unsigned int nTable, size_t nHash )
2019 return cuckoo::details::hash_ops< node_type, c_nNodeHashArraySize >::equal_to( node, nTable, nHash );
2022 void allocate_bucket_tables( size_t nSize )
2024 assert( cds::beans::is_power2( nSize ) );
2026 m_nBucketMask = nSize - 1;
2027 bucket_table_allocator alloc;
2028 for ( unsigned int i = 0; i < c_nArity; ++i )
2029 m_BucketTable[i] = alloc.NewArray( nSize );
2032 static void free_bucket_tables( bucket_entry ** pTable, size_t nCapacity )
2034 bucket_table_allocator alloc;
2035 for ( unsigned int i = 0; i < c_nArity; ++i ) {
2036 alloc.Delete( pTable[i], nCapacity );
2037 pTable[i] = nullptr;
2040 void free_bucket_tables()
2042 free_bucket_tables( m_BucketTable, m_nBucketMask + 1 );
2045 static unsigned int const c_nUndefTable = (unsigned int) -1;
2046 template <typename Q, typename Predicate >
2047 unsigned int contains( position * arrPos, size_t * arrHash, Q const& val, Predicate pred )
2049 // Buckets must be locked
2051 for ( unsigned int i = 0; i < c_nArity; ++i ) {
2052 bucket_entry& probeset = bucket( i, arrHash[i] );
2053 if ( contains_action::find( probeset, arrPos[i], i, arrHash[i], val, pred ))
2056 return c_nUndefTable;
2059 template <typename Q, typename Predicate, typename Func>
2060 value_type * erase_( Q const& val, Predicate pred, Func f )
2063 hashing( arrHash, val );
2064 position arrPos[ c_nArity ];
2067 scoped_cell_lock guard( m_MutexPolicy, arrHash );
2069 unsigned int nTable = contains( arrPos, arrHash, val, pred );
2070 if ( nTable != c_nUndefTable ) {
2071 node_type& node = *arrPos[nTable].itFound;
2072 cds::unref(f)( *node_traits::to_value_ptr(node) );
2073 bucket( nTable, arrHash[nTable]).remove( arrPos[nTable].itPrev, arrPos[nTable].itFound );
2075 m_Stat.onEraseSuccess();
2076 return node_traits::to_value_ptr( node );
2080 m_Stat.onEraseFailed();
2084 template <typename Q, typename Predicate, typename Func>
2085 bool find_( Q& val, Predicate pred, Func f )
2088 position arrPos[ c_nArity ];
2089 hashing( arrHash, val );
2090 scoped_cell_lock sl( m_MutexPolicy, arrHash );
2092 unsigned int nTable = contains( arrPos, arrHash, val, pred );
2093 if ( nTable != c_nUndefTable ) {
2094 cds::unref(f)( *node_traits::to_value_ptr( *arrPos[nTable].itFound ), val );
2095 m_Stat.onFindSuccess();
2099 m_Stat.onFindFailed();
2103 bool relocate( unsigned int nTable, size_t * arrGoalHash )
2105 // arrGoalHash contains hash values for relocating element
2106 // Relocating element is first one from bucket( nTable, arrGoalHash[nTable] ) probeset
2108 m_Stat.onRelocateCall();
2112 for ( unsigned int nRound = 0; nRound < c_nRelocateLimit; ++nRound ) {
2113 m_Stat.onRelocateRound();
2116 scoped_cell_lock guard( m_MutexPolicy, arrGoalHash );
2118 bucket_entry& refBucket = bucket( nTable, arrGoalHash[nTable] );
2119 if ( refBucket.size() < m_nProbesetThreshold ) {
2120 // probeset is not above the threshold
2121 m_Stat.onFalseRelocateRound();
2125 pVal = node_traits::to_value_ptr( *refBucket.begin() );
2126 copy_hash( arrHash, *pVal );
2128 scoped_cell_trylock guard2( m_MutexPolicy, arrHash );
2129 if ( !guard2.locked() )
2130 continue ; // try one more time
2132 refBucket.remove( typename bucket_entry::iterator(), refBucket.begin() );
2134 unsigned int i = (nTable + 1) % c_nArity;
2136 // try insert into free probeset
2137 while ( i != nTable ) {
2138 bucket_entry& bkt = bucket( i, arrHash[i] );
2139 if ( bkt.size() < m_nProbesetThreshold ) {
2141 contains_action::find( bkt, pos, i, arrHash[i], *pVal, key_predicate() ) ; // must return false!
2142 bkt.insert_after( pos.itPrev, node_traits::to_node_ptr( pVal ));
2143 m_Stat.onSuccessRelocateRound();
2146 i = ( i + 1 ) % c_nArity;
2149 // try insert into partial probeset
2150 i = (nTable + 1) % c_nArity;
2151 while ( i != nTable ) {
2152 bucket_entry& bkt = bucket( i, arrHash[i] );
2153 if ( bkt.size() < m_nProbesetSize ) {
2155 contains_action::find( bkt, pos, i, arrHash[i], *pVal, key_predicate() ) ; // must return false!
2156 bkt.insert_after( pos.itPrev, node_traits::to_node_ptr( pVal ));
2158 memcpy( arrGoalHash, arrHash, sizeof(arrHash));
2159 m_Stat.onRelocateAboveThresholdRound();
2160 goto next_iteration;
2162 i = (i + 1) % c_nArity;
2165 // all probeset is full, relocating fault
2166 refBucket.insert_after( typename bucket_entry::iterator(), node_traits::to_node_ptr( pVal ));
2167 m_Stat.onFailedRelocate();
2178 m_Stat.onResizeCall();
2180 size_t nOldCapacity = bucket_count();
2181 bucket_entry * pOldTable[ c_nArity ];
2183 scoped_resize_lock guard( m_MutexPolicy );
2185 if ( nOldCapacity != bucket_count() ) {
2186 m_Stat.onFalseResizeCall();
2190 size_t nCapacity = nOldCapacity * 2;
2192 m_MutexPolicy.resize( nCapacity );
2193 memcpy( pOldTable, m_BucketTable, sizeof(pOldTable));
2194 allocate_bucket_tables( nCapacity );
2196 typedef typename bucket_entry::iterator bucket_iterator;
2198 position arrPos[ c_nArity ];
2200 for ( unsigned int nTable = 0; nTable < c_nArity; ++nTable ) {
2201 bucket_entry * pTable = pOldTable[nTable];
2202 for ( size_t k = 0; k < nOldCapacity; ++k ) {
2203 bucket_iterator itNext;
2204 for ( bucket_iterator it = pTable[k].begin(), itEnd = pTable[k].end(); it != itEnd; it = itNext ) {
2208 value_type& val = *node_traits::to_value_ptr( *it );
2209 copy_hash( arrHash, val );
2210 contains( arrPos, arrHash, val, key_predicate() ) ; // must return c_nUndefTable
2212 for ( unsigned int i = 0; i < c_nArity; ++i ) {
2213 bucket_entry& refBucket = bucket( i, arrHash[i] );
2214 if ( refBucket.size() < m_nProbesetThreshold ) {
2215 refBucket.insert_after( arrPos[i].itPrev, &*it );
2216 m_Stat.onResizeSuccessMove();
2221 for ( unsigned int i = 0; i < c_nArity; ++i ) {
2222 bucket_entry& refBucket = bucket( i, arrHash[i] );
2223 if ( refBucket.size() < m_nProbesetSize ) {
2224 refBucket.insert_after( arrPos[i].itPrev, &*it );
2225 assert( refBucket.size() > 1 );
2226 copy_hash( arrHash, *node_traits::to_value_ptr( *refBucket.begin()) );
2227 m_Stat.onResizeRelocateCall();
2228 relocate( i, arrHash );
2237 free_bucket_tables( pOldTable, nOldCapacity );
2240 CDS_CONSTEXPR static unsigned int calc_probeset_size( unsigned int nProbesetSize ) CDS_NOEXCEPT
2242 return nProbesetSize
2244 : ( node_type::probeset_size ? node_type::probeset_size : c_nDefaultProbesetSize )
2250 /// Default constructor
2252 Initial size = \ref c_nDefaultInitialSize
2255 - \p c_nDefaultProbesetSize if \p probeset_type is \p cuckoo::list
2256 - \p Capacity if \p probeset_type is <tt> cuckoo::vector<Capacity> </tt>
2258 Probe set threshold = probe set size - 1
2261 : m_nProbesetSize( calc_probeset_size(0) )
2262 , m_nProbesetThreshold( m_nProbesetSize - 1 )
2263 , m_MutexPolicy( c_nDefaultInitialSize )
2265 check_common_constraints();
2266 check_probeset_properties();
2268 allocate_bucket_tables( c_nDefaultInitialSize );
2271 /// Constructs the set object with given probe set size and threshold
2273 If probe set type is <tt> cuckoo::vector<Capacity> </tt> vector
2274 then \p nProbesetSize should be equal to vector's \p Capacity.
2277 size_t nInitialSize ///< Initial set size; if 0 - use default initial size \ref c_nDefaultInitialSize
2278 , unsigned int nProbesetSize ///< probe set size
2279 , unsigned int nProbesetThreshold = 0 ///< probe set threshold, <tt>nProbesetThreshold < nProbesetSize</tt>. If 0, nProbesetThreshold = nProbesetSize - 1
2281 : m_nProbesetSize( calc_probeset_size(nProbesetSize) )
2282 , m_nProbesetThreshold( nProbesetThreshold ? nProbesetThreshold : m_nProbesetSize - 1 )
2283 , m_MutexPolicy( cds::beans::ceil2(nInitialSize ? nInitialSize : c_nDefaultInitialSize ))
2285 check_common_constraints();
2286 check_probeset_properties();
2288 allocate_bucket_tables( nInitialSize ? cds::beans::ceil2( nInitialSize ) : c_nDefaultInitialSize );
2291 /// Constructs the set object with given hash functor tuple
2293 The probe set size and threshold are set as default, see CuckooSet()
2296 hash_tuple_type const& h ///< hash functor tuple of type <tt>std::tuple<H1, H2, ... Hn></tt> where <tt> n == \ref c_nArity </tt>
2298 : m_nProbesetSize( calc_probeset_size(0) )
2299 , m_nProbesetThreshold( m_nProbesetSize -1 )
2301 , m_MutexPolicy( c_nDefaultInitialSize )
2303 check_common_constraints();
2304 check_probeset_properties();
2306 allocate_bucket_tables( c_nDefaultInitialSize );
2309 /// Constructs the set object with given probe set properties and hash functor tuple
2311 If probe set type is <tt> cuckoo::vector<Capacity> </tt> vector
2312 then \p nProbesetSize should be equal to vector's \p Capacity.
2315 size_t nInitialSize ///< Initial set size; if 0 - use default initial size \ref c_nDefaultInitialSize
2316 , unsigned int nProbesetSize ///< probe set size, positive integer
2317 , unsigned int nProbesetThreshold ///< probe set threshold, <tt>nProbesetThreshold < nProbesetSize</tt>. If 0, nProbesetThreshold = nProbesetSize - 1
2318 , hash_tuple_type const& h ///< hash functor tuple of type <tt>std::tuple<H1, H2, ... Hn></tt> where <tt> n == \ref c_nArity </tt>
2320 : m_nProbesetSize( calc_probeset_size(nProbesetSize) )
2321 , m_nProbesetThreshold( nProbesetThreshold ? nProbesetThreshold : m_nProbesetSize - 1)
2323 , m_MutexPolicy( cds::beans::ceil2(nInitialSize ? nInitialSize : c_nDefaultInitialSize ))
2325 check_common_constraints();
2326 check_probeset_properties();
2328 allocate_bucket_tables( nInitialSize ? cds::beans::ceil2( nInitialSize ) : c_nDefaultInitialSize );
2331 # ifdef CDS_MOVE_SEMANTICS_SUPPORT
2332 /// Constructs the set object with given hash functor tuple (move semantics)
2334 The probe set size and threshold are set as default, see CuckooSet()
2337 hash_tuple_type&& h ///< hash functor tuple of type <tt>std::tuple<H1, H2, ... Hn></tt> where <tt> n == \ref c_nArity </tt>
2339 : m_nProbesetSize( calc_probeset_size(0) )
2340 , m_nProbesetThreshold( m_nProbesetSize / 2 )
2341 , m_Hash( std::forward<hash_tuple_type>(h) )
2342 , m_MutexPolicy( c_nDefaultInitialSize )
2344 check_common_constraints();
2345 check_probeset_properties();
2347 allocate_bucket_tables( c_nDefaultInitialSize );
2350 /// Constructs the set object with given probe set properties and hash functor tuple (move semantics)
2352 If probe set type is <tt> cuckoo::vector<Capacity> </tt> vector
2353 then \p nProbesetSize should be equal to vector's \p Capacity.
2356 size_t nInitialSize ///< Initial set size; if 0 - use default initial size \ref c_nDefaultInitialSize
2357 , unsigned int nProbesetSize ///< probe set size, positive integer
2358 , unsigned int nProbesetThreshold ///< probe set threshold, <tt>nProbesetThreshold < nProbesetSize</tt>. If 0, nProbesetThreshold = nProbesetSize - 1
2359 , hash_tuple_type&& h ///< hash functor tuple of type <tt>std::tuple<H1, H2, ... Hn></tt> where <tt> n == \ref c_nArity </tt>
2361 : m_nProbesetSize( calc_probeset_size(nProbesetSize) )
2362 , m_nProbesetThreshold( nProbesetThreshold ? nProbesetThreshold : m_nProbesetSize - 1)
2363 , m_Hash( std::forward<hash_tuple_type>(h) )
2364 , m_MutexPolicy( cds::beans::ceil2(nInitialSize ? nInitialSize : c_nDefaultInitialSize ))
2366 check_common_constraints();
2367 check_probeset_properties();
2369 allocate_bucket_tables( nInitialSize ? cds::beans::ceil2( nInitialSize ) : c_nDefaultInitialSize );
2371 # endif // ifdef CDS_MOVE_SEMANTICS_SUPPORT
2376 free_bucket_tables();
2380 /// Inserts new node
2382 The function inserts \p val in the set if it does not contain
2383 an item with key equal to \p val.
2385 Returns \p true if \p val is placed into the set, \p false otherwise.
2387 bool insert( value_type& val )
2389 # ifdef CDS_CXX11_LAMBDA_SUPPORT
2390 return insert( val, []( value_type& ) {} );
2392 return insert( val, empty_insert_functor() );
2396 /// Inserts new node
2398 The function allows to split creating of new item into two part:
2399 - create item with key only
2400 - insert new item into the set
2401 - if inserting is success, calls \p f functor to initialize value-field of \p val.
2403 The functor signature is:
2405 void func( value_type& val );
2407 where \p val is the item inserted.
2409 The user-defined functor is called only if the inserting is success and can be passed by reference
2410 using <tt>boost::ref</tt>
2412 template <typename Func>
2413 bool insert( value_type& val, Func f )
2416 position arrPos[ c_nArity ];
2417 unsigned int nGoalTable;
2419 hashing( arrHash, val );
2420 node_type * pNode = node_traits::to_node_ptr( val );
2421 store_hash( pNode, arrHash );
2425 scoped_cell_lock guard( m_MutexPolicy, arrHash );
2427 if ( contains( arrPos, arrHash, val, key_predicate() ) != c_nUndefTable ) {
2428 m_Stat.onInsertFailed();
2432 for ( unsigned int i = 0; i < c_nArity; ++i ) {
2433 bucket_entry& refBucket = bucket( i, arrHash[i] );
2434 if ( refBucket.size() < m_nProbesetThreshold ) {
2435 refBucket.insert_after( arrPos[i].itPrev, pNode );
2436 cds::unref(f)( val );
2438 m_Stat.onInsertSuccess();
2443 for ( unsigned int i = 0; i < c_nArity; ++i ) {
2444 bucket_entry& refBucket = bucket( i, arrHash[i] );
2445 if ( refBucket.size() < m_nProbesetSize ) {
2446 refBucket.insert_after( arrPos[i].itPrev, pNode );
2447 cds::unref(f)( val );
2450 assert( refBucket.size() > 1 );
2451 copy_hash( arrHash, *node_traits::to_value_ptr( *refBucket.begin()) );
2457 m_Stat.onInsertResize();
2462 m_Stat.onInsertRelocate();
2463 if ( !relocate( nGoalTable, arrHash )) {
2464 m_Stat.onInsertRelocateFault();
2465 m_Stat.onInsertResize();
2469 m_Stat.onInsertSuccess();
2473 /// Ensures that the \p val exists in the set
2475 The operation performs inserting or changing data with lock-free manner.
2477 If the item \p val not found in the set, then \p val is inserted into the set.
2478 Otherwise, the functor \p func is called with item found.
2479 The functor signature is:
2481 void func( bool bNew, value_type& item, value_type& val );
2484 - \p bNew - \p true if the item has been inserted, \p false otherwise
2485 - \p item - item of the set
2486 - \p val - argument \p val passed into the \p ensure function
2487 If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
2488 refers to the same thing.
2490 The functor may change non-key fields of the \p item.
2492 You may pass \p func argument by reference using <tt>boost::ref</tt> or cds::ref.
2494 Returns <tt> std::pair<bool, bool> </tt> where \p first is \p true if operation is successful,
2495 \p second is \p true if new item has been added or \p false if the item with \p key
2496 already is in the set.
2498 template <typename Func>
2499 std::pair<bool, bool> ensure( value_type& val, Func func )
2502 position arrPos[ c_nArity ];
2503 unsigned int nGoalTable;
2505 hashing( arrHash, val );
2506 node_type * pNode = node_traits::to_node_ptr( val );
2507 store_hash( pNode, arrHash );
2511 scoped_cell_lock guard( m_MutexPolicy, arrHash );
2513 unsigned int nTable = contains( arrPos, arrHash, val, key_predicate() );
2514 if ( nTable != c_nUndefTable ) {
2515 cds::unref(func)( false, *node_traits::to_value_ptr( *arrPos[nTable].itFound ), val );
2516 m_Stat.onEnsureExist();
2517 return std::make_pair( true, false );
2520 node_type * pNode = node_traits::to_node_ptr( val );
2521 store_hash( pNode, arrHash );
2523 for ( unsigned int i = 0; i < c_nArity; ++i ) {
2524 bucket_entry& refBucket = bucket( i, arrHash[i] );
2525 if ( refBucket.size() < m_nProbesetThreshold ) {
2526 refBucket.insert_after( arrPos[i].itPrev, pNode );
2527 cds::unref(func)( true, val, val );
2529 m_Stat.onEnsureSuccess();
2530 return std::make_pair( true, true );
2534 for ( unsigned int i = 0; i < c_nArity; ++i ) {
2535 bucket_entry& refBucket = bucket( i, arrHash[i] );
2536 if ( refBucket.size() < m_nProbesetSize ) {
2537 refBucket.insert_after( arrPos[i].itPrev, pNode );
2538 cds::unref(func)( true, val, val );
2541 assert( refBucket.size() > 1 );
2542 copy_hash( arrHash, *node_traits::to_value_ptr( *refBucket.begin()) );
2548 m_Stat.onEnsureResize();
2553 m_Stat.onEnsureRelocate();
2554 if ( !relocate( nGoalTable, arrHash )) {
2555 m_Stat.onEnsureRelocateFault();
2556 m_Stat.onEnsureResize();
2560 m_Stat.onEnsureSuccess();
2561 return std::make_pair( true, true );
2564 /// Unlink the item \p val from the set
2566 The function searches the item \p val in the set and unlink it
2567 if it is found and is equal to \p val (here, the equality means that
2568 \p val belongs to the set: if \p item is an item found then
2569 unlink is successful iif <tt>&val == &item</tt>)
2571 The function returns \p true if success and \p false otherwise.
2573 bool unlink( value_type& val )
2576 hashing( arrHash, val );
2577 position arrPos[ c_nArity ];
2580 scoped_cell_lock guard( m_MutexPolicy, arrHash );
2582 unsigned int nTable = contains( arrPos, arrHash, val, key_predicate() );
2583 if ( nTable != c_nUndefTable && node_traits::to_value_ptr(*arrPos[nTable].itFound) == &val ) {
2584 bucket( nTable, arrHash[nTable]).remove( arrPos[nTable].itPrev, arrPos[nTable].itFound );
2586 m_Stat.onUnlinkSuccess();
2591 m_Stat.onUnlinkFailed();
2595 /// Deletes the item from the set
2596 /** \anchor cds_intrusive_CuckooSet_erase
2597 The function searches an item with key equal to \p val in the set,
2598 unlinks it from the set, and returns a pointer to unlinked item.
2600 If the item with key equal to \p val is not found the function return \p NULL.
2602 Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
2604 template <typename Q>
2605 value_type * erase( Q const& val )
2607 # ifdef CDS_CXX11_LAMBDA_SUPPORT
2608 return erase( val, [](value_type const&) {} );
2610 return erase( val, empty_erase_functor() );
2614 /// Deletes the item from the set using \p pred predicate for searching
2616 The function is an analog of \ref cds_intrusive_CuckooSet_erase "erase(Q const&)"
2617 but \p pred is used for key comparing.
2618 If cuckoo set is ordered, then \p Predicate should have the interface and semantics like \p std::less.
2619 If cuckoo set is unordered, then \p Predicate should have the interface and semantics like \p std::equal_to.
2620 \p Predicate must imply the same element order as the comparator used for building the set.
2622 template <typename Q, typename Predicate>
2623 value_type * erase_with( Q const& val, Predicate pred )
2625 # ifdef CDS_CXX11_LAMBDA_SUPPORT
2626 return erase_( val, typename predicate_wrapper<Predicate>::type(), [](value_type const&) {} );
2628 return erase_( val, typename predicate_wrapper<Predicate>::type(), empty_erase_functor() );
2632 /// Delete the item from the set
2633 /** \anchor cds_intrusive_CuckooSet_erase_func
2634 The function searches an item with key equal to \p val in the set,
2635 call \p f functor with item found, unlinks it from the set, and returns a pointer to unlinked item.
2637 The \p Func interface is
2640 void operator()( value_type const& item );
2643 The functor may be passed by reference with <tt>boost:ref</tt>
2645 If the item with key equal to \p val is not found the function return \p NULL.
2647 Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
2649 template <typename Q, typename Func>
2650 value_type * erase( Q const& val, Func f )
2652 return erase_( val, key_predicate(), f );
2655 /// Deletes the item from the set using \p pred predicate for searching
2657 The function is an analog of \ref cds_intrusive_CuckooSet_erase_func "erase(Q const&, Func)"
2658 but \p pred is used for key comparing.
2659 If you use ordered cuckoo set, then \p Predicate should have the interface and semantics like \p std::less.
2660 If you use unordered cuckoo set, then \p Predicate should have the interface and semantics like \p std::equal_to.
2661 \p Predicate must imply the same element order as the comparator used for building the set.
2663 template <typename Q, typename Predicate, typename Func>
2664 value_type * erase_with( Q const& val, Predicate pred, Func f )
2666 return erase_( val, typename predicate_wrapper<Predicate>::type(), f );
2669 /// Find the key \p val
2670 /** \anchor cds_intrusive_CuckooSet_find_func
2671 The function searches the item with key equal to \p val and calls the functor \p f for item found.
2672 The interface of \p Func functor is:
2675 void operator()( value_type& item, Q& val );
2678 where \p item is the item found, \p val is the <tt>find</tt> function argument.
2680 You can pass \p f argument by reference using <tt>boost::ref</tt> or cds::ref.
2682 The functor may change non-key fields of \p item.
2684 The \p val argument is non-const since it can be used as \p f functor destination i.e., the functor
2685 may modify both arguments.
2687 Note the hash functor specified for class \p Traits template parameter
2688 should accept a parameter of type \p Q that can be not the same as \p value_type.
2690 The function returns \p true if \p val is found, \p false otherwise.
2692 template <typename Q, typename Func>
2693 bool find( Q& val, Func f )
2695 return find_( val, key_predicate(), f );
2698 /// Find the key \p val using \p pred predicate for comparing
2700 The function is an analog of \ref cds_intrusive_CuckooSet_find_func "find(Q&, Func)"
2701 but \p pred is used for key comparison.
2702 If you use ordered cuckoo set, then \p Predicate should have the interface and semantics like \p std::less.
2703 If you use unordered cuckoo set, then \p Predicate should have the interface and semantics like \p std::equal_to.
2704 \p pred must imply the same element order as the comparator used for building the set.
2706 template <typename Q, typename Predicate, typename Func>
2707 bool find_with( Q& val, Predicate pred, Func f )
2709 return find_( val, typename predicate_wrapper<Predicate>::type(), f );
2712 /// Find the key \p val
2713 /** \anchor cds_intrusive_CuckooSet_find_cfunc
2714 The function searches the item with key equal to \p val and calls the functor \p f for item found.
2715 The interface of \p Func functor is:
2718 void operator()( value_type& item, Q const& val );
2721 where \p item is the item found, \p val is the <tt>find</tt> function argument.
2723 You can pass \p f argument by reference using <tt>boost::ref</tt> or cds::ref.
2725 The functor may change non-key fields of \p item.
2727 The \p val argument is non-const since it can be used as \p f functor destination i.e., the functor
2728 may modify both arguments.
2730 The function returns \p true if \p val is found, \p false otherwise.
2732 template <typename Q, typename Func>
2733 bool find( Q const& val, Func f )
2735 return find_( val, key_predicate(), f );
2738 /// Find the key \p val using \p pred predicate for comparing
2740 The function is an analog of \ref cds_intrusive_CuckooSet_find_cfunc "find(Q const&, Func)"
2741 but \p pred is used for key comparison.
2742 If you use ordered cuckoo set, then \p Predicate should have the interface and semantics like \p std::less.
2743 If you use unordered cuckoo set, then \p Predicate should have the interface and semantics like \p std::equal_to.
2744 \p pred must imply the same element order as the comparator used for building the set.
2746 template <typename Q, typename Predicate, typename Func>
2747 bool find_with( Q const& val, Predicate pred, Func f )
2749 return find_( val, typename predicate_wrapper<Predicate>::type(), f );
2752 /// Find the key \p val
2753 /** \anchor cds_intrusive_CuckooSet_find_val
2754 The function searches the item with key equal to \p val
2755 and returns \p true if it is found, and \p false otherwise.
2757 Note the hash functor specified for class \p Traits template parameter
2758 should accept a parameter of type \p Q that can be not the same as \p value_type.
2760 template <typename Q>
2761 bool find( Q const& val )
2763 # ifdef CDS_CXX11_LAMBDA_SUPPORT
2764 return find( val, [](value_type&, Q const& ) {} );
2766 return find( val, empty_find_functor() );
2770 /// Find the key \p val using \p pred predicate for comparing
2772 The function is an analog of \ref cds_intrusive_CuckooSet_find_val "find(Q const&)"
2773 but \p pred is used for key comparison.
2774 If you use ordered cuckoo set, then \p Predicate should have the interface and semantics like \p std::less.
2775 If you use unordered cuckoo set, then \p Predicate should have the interface and semantics like \p std::equal_to.
2776 \p pred must imply the same element order as the comparator used for building the set.
2778 template <typename Q, typename Predicate>
2779 bool find_with( Q const& val, Predicate pred )
2781 # ifdef CDS_CXX11_LAMBDA_SUPPORT
2782 return find_with( val, typename predicate_wrapper<Predicate>::type(), [](value_type& , Q const& ) {} );
2784 return find_with( val, typename predicate_wrapper<Predicate>::type(), empty_find_functor() );
2790 The function unlinks all items from the set.
2791 For any item \ref disposer is called
2795 clear_and_dispose( disposer() );
2798 /// Clears the set and calls \p disposer for each item
2800 The function unlinks all items from the set calling \p disposer for each item.
2801 \p Disposer functor interface is:
2804 void operator()( value_type * p );
2808 The \ref disposer specified in \p Traits options is not called.
2810 template <typename Disposer>
2811 void clear_and_dispose( Disposer oDisposer )
2813 // locks entire array
2814 scoped_full_lock sl( m_MutexPolicy );
2816 # if !defined(CDS_CXX11_LAMBDA_SUPPORT) || ((CDS_COMPILER == CDS_COMPILER_MSVC || CDS_COMPILER == CDS_COMPILER_INTEL ) && _MSC_VER == 1600)
2817 disposer_wrapper<Disposer> disp( oDisposer );
2819 for ( unsigned int i = 0; i < c_nArity; ++i ) {
2820 bucket_entry * pEntry = m_BucketTable[i];
2821 bucket_entry * pEnd = pEntry + m_nBucketMask + 1;
2822 for ( ; pEntry != pEnd ; ++pEntry ) {
2823 # if defined(CDS_CXX11_LAMBDA_SUPPORT) && !((CDS_COMPILER == CDS_COMPILER_MSVC || CDS_COMPILER == CDS_COMPILER_INTEL) && _MSC_VER == 1600)
2824 // MSVC 10: error to call nested typedefs node_traits from lambda
2825 pEntry->clear( [&oDisposer]( node_type * pNode ){ oDisposer( node_traits::to_value_ptr( pNode )) ; } );
2827 pEntry->clear( cds::ref(disp) );
2831 m_ItemCounter.reset();
2834 /// Checks if the set is empty
2836 Emptiness is checked by item counting: if item count is zero then the set is empty.
2843 /// Returns item count in the set
2846 return m_ItemCounter;
2849 /// Returns the size of hash table
2851 The hash table size is non-constant and can be increased via resizing.
2853 size_t bucket_count() const
2855 return m_nBucketMask + 1;
2858 /// Returns lock array size
2859 size_t lock_count() const
2861 return m_MutexPolicy.lock_count();
2864 /// Returns const reference to internal statistics
2865 stat const& statistics() const
2870 /// Returns const reference to mutex policy internal statistics
2871 typename mutex_policy::statistics_type const& mutex_policy_statistics() const
2873 return m_MutexPolicy.statistics();
2876 }} // namespace cds::intrusive
2878 #endif // #ifndef __CDS_INTRUSIVE_CUCKOO_SET_H