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, typename... Options>
245 typedef typename opt::make_options< default_hook, Options...>::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 < typename... Options >
265 struct base_hook: public hook< opt::base_hook_tag, Options... >
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, typename... Options >
279 struct member_hook: public hook< opt::member_hook_tag, Options... >
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, typename... Options >
297 struct traits_hook: public hook< opt::traits_hook_tag, Options... >
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 atomics::atomic< owner_t > m_Owner ; ///< owner mark (thread id + boolean flag)
662 atomics::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( atomics::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( atomics::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(atomics::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, atomics::memory_order_acq_rel, atomics::memory_order_relaxed )) {
769 m_arrLocks[0]->lock_all();
775 m_Stat.onFullLockIter();
781 m_arrLocks[0]->unlock_all();
782 m_Owner.store( 0, atomics::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, atomics::memory_order_acq_rel, atomics::memory_order_relaxed )) {
799 if ( pOldLocks[0] != m_arrLocks[0] ) {
800 m_Owner.store( 0, atomics::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, atomics::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, atomics::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(atomics::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 <typename... Options>
1171 struct make_traits {
1172 typedef typename cds::opt::make_options<
1173 typename cds::opt::find_type_traits< cuckoo::type_traits, Options... >::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
1908 bucket_iterator itPrev;
1909 bucket_iterator itFound;
1912 typedef typename std::conditional< c_isSorted
1913 , cuckoo::details::contains< node_traits, true >
1914 , cuckoo::details::contains< node_traits, false >
1915 >::type contains_action;
1917 template <typename Predicate>
1918 struct predicate_wrapper {
1919 typedef typename std::conditional< c_isSorted, cds::opt::details::make_comparator_from_less<Predicate>, Predicate>::type type;
1922 typedef typename std::conditional< c_isSorted, key_comparator, key_equal_to >::type key_predicate;
1926 static unsigned int const c_nDefaultProbesetSize = 4 ; ///< default probeset size
1927 static size_t const c_nDefaultInitialSize = 16 ; ///< default initial size
1928 static unsigned int const c_nRelocateLimit = c_nArity * 2 - 1 ; ///< Count of attempts to relocate before giving up
1931 bucket_entry * m_BucketTable[ c_nArity ] ; ///< Bucket tables
1933 size_t m_nBucketMask ; ///< Hash bitmask; bucket table size minus 1.
1934 unsigned int const m_nProbesetSize ; ///< Probe set size
1935 unsigned int const m_nProbesetThreshold ; ///< Probe set threshold
1937 hash m_Hash ; ///< Hash functor tuple
1938 mutex_policy m_MutexPolicy ; ///< concurrent access policy
1939 item_counter m_ItemCounter ; ///< item counter
1940 mutable stat m_Stat ; ///< internal statistics
1944 static void check_common_constraints()
1946 static_assert( (c_nArity == mutex_policy::c_nArity), "The count of hash functors must be equal to mutex_policy arity" );
1949 void check_probeset_properties() const
1951 assert( m_nProbesetThreshold < m_nProbesetSize );
1953 // if probe set type is cuckoo::vector<N> then m_nProbesetSize == N
1954 assert( node_type::probeset_size == 0 || node_type::probeset_size == m_nProbesetSize );
1957 template <typename Q>
1958 void hashing( size_t * pHashes, Q const& v ) const
1960 m_Hash( pHashes, v );
1963 void copy_hash( size_t * pHashes, value_type const& v ) const
1965 if ( c_nNodeHashArraySize )
1966 memcpy( pHashes, node_traits::to_node_ptr( v )->get_hash(), sizeof(pHashes[0]) * c_nNodeHashArraySize );
1968 hashing( pHashes, v );
1971 bucket_entry& bucket( unsigned int nTable, size_t nHash )
1973 assert( nTable < c_nArity );
1974 return m_BucketTable[nTable][nHash & m_nBucketMask];
1977 static void store_hash( node_type * pNode, size_t * pHashes )
1979 cuckoo::details::hash_ops< node_type, c_nNodeHashArraySize >::store( pNode, pHashes );
1980 //memcpy( pNode->m_arrHash, pHashes, sizeof(size_t) * c_nArity );
1983 static bool equal_hash( node_type& node, unsigned int nTable, size_t nHash )
1985 return cuckoo::details::hash_ops< node_type, c_nNodeHashArraySize >::equal_to( node, nTable, nHash );
1988 void allocate_bucket_tables( size_t nSize )
1990 assert( cds::beans::is_power2( nSize ) );
1992 m_nBucketMask = nSize - 1;
1993 bucket_table_allocator alloc;
1994 for ( unsigned int i = 0; i < c_nArity; ++i )
1995 m_BucketTable[i] = alloc.NewArray( nSize );
1998 static void free_bucket_tables( bucket_entry ** pTable, size_t nCapacity )
2000 bucket_table_allocator alloc;
2001 for ( unsigned int i = 0; i < c_nArity; ++i ) {
2002 alloc.Delete( pTable[i], nCapacity );
2003 pTable[i] = nullptr;
2006 void free_bucket_tables()
2008 free_bucket_tables( m_BucketTable, m_nBucketMask + 1 );
2011 static unsigned int const c_nUndefTable = (unsigned int) -1;
2012 template <typename Q, typename Predicate >
2013 unsigned int contains( position * arrPos, size_t * arrHash, Q const& val, Predicate pred )
2015 // Buckets must be locked
2017 for ( unsigned int i = 0; i < c_nArity; ++i ) {
2018 bucket_entry& probeset = bucket( i, arrHash[i] );
2019 if ( contains_action::find( probeset, arrPos[i], i, arrHash[i], val, pred ))
2022 return c_nUndefTable;
2025 template <typename Q, typename Predicate, typename Func>
2026 value_type * erase_( Q const& val, Predicate pred, Func f )
2029 hashing( arrHash, val );
2030 position arrPos[ c_nArity ];
2033 scoped_cell_lock guard( m_MutexPolicy, arrHash );
2035 unsigned int nTable = contains( arrPos, arrHash, val, pred );
2036 if ( nTable != c_nUndefTable ) {
2037 node_type& node = *arrPos[nTable].itFound;
2038 cds::unref(f)( *node_traits::to_value_ptr(node) );
2039 bucket( nTable, arrHash[nTable]).remove( arrPos[nTable].itPrev, arrPos[nTable].itFound );
2041 m_Stat.onEraseSuccess();
2042 return node_traits::to_value_ptr( node );
2046 m_Stat.onEraseFailed();
2050 template <typename Q, typename Predicate, typename Func>
2051 bool find_( Q& val, Predicate pred, Func f )
2054 position arrPos[ c_nArity ];
2055 hashing( arrHash, val );
2056 scoped_cell_lock sl( m_MutexPolicy, arrHash );
2058 unsigned int nTable = contains( arrPos, arrHash, val, pred );
2059 if ( nTable != c_nUndefTable ) {
2060 cds::unref(f)( *node_traits::to_value_ptr( *arrPos[nTable].itFound ), val );
2061 m_Stat.onFindSuccess();
2065 m_Stat.onFindFailed();
2069 bool relocate( unsigned int nTable, size_t * arrGoalHash )
2071 // arrGoalHash contains hash values for relocating element
2072 // Relocating element is first one from bucket( nTable, arrGoalHash[nTable] ) probeset
2074 m_Stat.onRelocateCall();
2078 for ( unsigned int nRound = 0; nRound < c_nRelocateLimit; ++nRound ) {
2079 m_Stat.onRelocateRound();
2082 scoped_cell_lock guard( m_MutexPolicy, arrGoalHash );
2084 bucket_entry& refBucket = bucket( nTable, arrGoalHash[nTable] );
2085 if ( refBucket.size() < m_nProbesetThreshold ) {
2086 // probeset is not above the threshold
2087 m_Stat.onFalseRelocateRound();
2091 pVal = node_traits::to_value_ptr( *refBucket.begin() );
2092 copy_hash( arrHash, *pVal );
2094 scoped_cell_trylock guard2( m_MutexPolicy, arrHash );
2095 if ( !guard2.locked() )
2096 continue ; // try one more time
2098 refBucket.remove( typename bucket_entry::iterator(), refBucket.begin() );
2100 unsigned int i = (nTable + 1) % c_nArity;
2102 // try insert into free probeset
2103 while ( i != nTable ) {
2104 bucket_entry& bkt = bucket( i, arrHash[i] );
2105 if ( bkt.size() < m_nProbesetThreshold ) {
2107 contains_action::find( bkt, pos, i, arrHash[i], *pVal, key_predicate() ) ; // must return false!
2108 bkt.insert_after( pos.itPrev, node_traits::to_node_ptr( pVal ));
2109 m_Stat.onSuccessRelocateRound();
2112 i = ( i + 1 ) % c_nArity;
2115 // try insert into partial probeset
2116 i = (nTable + 1) % c_nArity;
2117 while ( i != nTable ) {
2118 bucket_entry& bkt = bucket( i, arrHash[i] );
2119 if ( bkt.size() < m_nProbesetSize ) {
2121 contains_action::find( bkt, pos, i, arrHash[i], *pVal, key_predicate() ) ; // must return false!
2122 bkt.insert_after( pos.itPrev, node_traits::to_node_ptr( pVal ));
2124 memcpy( arrGoalHash, arrHash, sizeof(arrHash));
2125 m_Stat.onRelocateAboveThresholdRound();
2126 goto next_iteration;
2128 i = (i + 1) % c_nArity;
2131 // all probeset is full, relocating fault
2132 refBucket.insert_after( typename bucket_entry::iterator(), node_traits::to_node_ptr( pVal ));
2133 m_Stat.onFailedRelocate();
2144 m_Stat.onResizeCall();
2146 size_t nOldCapacity = bucket_count();
2147 bucket_entry * pOldTable[ c_nArity ];
2149 scoped_resize_lock guard( m_MutexPolicy );
2151 if ( nOldCapacity != bucket_count() ) {
2152 m_Stat.onFalseResizeCall();
2156 size_t nCapacity = nOldCapacity * 2;
2158 m_MutexPolicy.resize( nCapacity );
2159 memcpy( pOldTable, m_BucketTable, sizeof(pOldTable));
2160 allocate_bucket_tables( nCapacity );
2162 typedef typename bucket_entry::iterator bucket_iterator;
2164 position arrPos[ c_nArity ];
2166 for ( unsigned int nTable = 0; nTable < c_nArity; ++nTable ) {
2167 bucket_entry * pTable = pOldTable[nTable];
2168 for ( size_t k = 0; k < nOldCapacity; ++k ) {
2169 bucket_iterator itNext;
2170 for ( bucket_iterator it = pTable[k].begin(), itEnd = pTable[k].end(); it != itEnd; it = itNext ) {
2174 value_type& val = *node_traits::to_value_ptr( *it );
2175 copy_hash( arrHash, val );
2176 contains( arrPos, arrHash, val, key_predicate() ) ; // must return c_nUndefTable
2178 for ( unsigned int i = 0; i < c_nArity; ++i ) {
2179 bucket_entry& refBucket = bucket( i, arrHash[i] );
2180 if ( refBucket.size() < m_nProbesetThreshold ) {
2181 refBucket.insert_after( arrPos[i].itPrev, &*it );
2182 m_Stat.onResizeSuccessMove();
2187 for ( unsigned int i = 0; i < c_nArity; ++i ) {
2188 bucket_entry& refBucket = bucket( i, arrHash[i] );
2189 if ( refBucket.size() < m_nProbesetSize ) {
2190 refBucket.insert_after( arrPos[i].itPrev, &*it );
2191 assert( refBucket.size() > 1 );
2192 copy_hash( arrHash, *node_traits::to_value_ptr( *refBucket.begin()) );
2193 m_Stat.onResizeRelocateCall();
2194 relocate( i, arrHash );
2203 free_bucket_tables( pOldTable, nOldCapacity );
2206 CDS_CONSTEXPR static unsigned int calc_probeset_size( unsigned int nProbesetSize ) CDS_NOEXCEPT
2208 return nProbesetSize
2210 : ( node_type::probeset_size ? node_type::probeset_size : c_nDefaultProbesetSize )
2216 /// Default constructor
2218 Initial size = \ref c_nDefaultInitialSize
2221 - \p c_nDefaultProbesetSize if \p probeset_type is \p cuckoo::list
2222 - \p Capacity if \p probeset_type is <tt> cuckoo::vector<Capacity> </tt>
2224 Probe set threshold = probe set size - 1
2227 : m_nProbesetSize( calc_probeset_size(0) )
2228 , m_nProbesetThreshold( m_nProbesetSize - 1 )
2229 , m_MutexPolicy( c_nDefaultInitialSize )
2231 check_common_constraints();
2232 check_probeset_properties();
2234 allocate_bucket_tables( c_nDefaultInitialSize );
2237 /// Constructs the set object with given probe set size and threshold
2239 If probe set type is <tt> cuckoo::vector<Capacity> </tt> vector
2240 then \p nProbesetSize should be equal to vector's \p Capacity.
2243 size_t nInitialSize ///< Initial set size; if 0 - use default initial size \ref c_nDefaultInitialSize
2244 , unsigned int nProbesetSize ///< probe set size
2245 , unsigned int nProbesetThreshold = 0 ///< probe set threshold, <tt>nProbesetThreshold < nProbesetSize</tt>. If 0, nProbesetThreshold = nProbesetSize - 1
2247 : m_nProbesetSize( calc_probeset_size(nProbesetSize) )
2248 , m_nProbesetThreshold( nProbesetThreshold ? nProbesetThreshold : m_nProbesetSize - 1 )
2249 , m_MutexPolicy( cds::beans::ceil2(nInitialSize ? nInitialSize : c_nDefaultInitialSize ))
2251 check_common_constraints();
2252 check_probeset_properties();
2254 allocate_bucket_tables( nInitialSize ? cds::beans::ceil2( nInitialSize ) : c_nDefaultInitialSize );
2257 /// Constructs the set object with given hash functor tuple
2259 The probe set size and threshold are set as default, see CuckooSet()
2262 hash_tuple_type const& h ///< hash functor tuple of type <tt>std::tuple<H1, H2, ... Hn></tt> where <tt> n == \ref c_nArity </tt>
2264 : m_nProbesetSize( calc_probeset_size(0) )
2265 , m_nProbesetThreshold( m_nProbesetSize -1 )
2267 , m_MutexPolicy( c_nDefaultInitialSize )
2269 check_common_constraints();
2270 check_probeset_properties();
2272 allocate_bucket_tables( c_nDefaultInitialSize );
2275 /// Constructs the set object with given probe set properties and hash functor tuple
2277 If probe set type is <tt> cuckoo::vector<Capacity> </tt> vector
2278 then \p nProbesetSize should be equal to vector's \p Capacity.
2281 size_t nInitialSize ///< Initial set size; if 0 - use default initial size \ref c_nDefaultInitialSize
2282 , unsigned int nProbesetSize ///< probe set size, positive integer
2283 , unsigned int nProbesetThreshold ///< probe set threshold, <tt>nProbesetThreshold < nProbesetSize</tt>. If 0, nProbesetThreshold = nProbesetSize - 1
2284 , hash_tuple_type const& h ///< hash functor tuple of type <tt>std::tuple<H1, H2, ... Hn></tt> where <tt> n == \ref c_nArity </tt>
2286 : m_nProbesetSize( calc_probeset_size(nProbesetSize) )
2287 , m_nProbesetThreshold( nProbesetThreshold ? nProbesetThreshold : m_nProbesetSize - 1)
2289 , m_MutexPolicy( cds::beans::ceil2(nInitialSize ? nInitialSize : c_nDefaultInitialSize ))
2291 check_common_constraints();
2292 check_probeset_properties();
2294 allocate_bucket_tables( nInitialSize ? cds::beans::ceil2( nInitialSize ) : c_nDefaultInitialSize );
2297 /// Constructs the set object with given hash functor tuple (move semantics)
2299 The probe set size and threshold are set as default, see CuckooSet()
2302 hash_tuple_type&& h ///< hash functor tuple of type <tt>std::tuple<H1, H2, ... Hn></tt> where <tt> n == \ref c_nArity </tt>
2304 : m_nProbesetSize( calc_probeset_size(0) )
2305 , m_nProbesetThreshold( m_nProbesetSize / 2 )
2306 , m_Hash( std::forward<hash_tuple_type>(h) )
2307 , m_MutexPolicy( c_nDefaultInitialSize )
2309 check_common_constraints();
2310 check_probeset_properties();
2312 allocate_bucket_tables( c_nDefaultInitialSize );
2315 /// Constructs the set object with given probe set properties and hash functor tuple (move semantics)
2317 If probe set type is <tt> cuckoo::vector<Capacity> </tt> vector
2318 then \p nProbesetSize should be equal to vector's \p Capacity.
2321 size_t nInitialSize ///< Initial set size; if 0 - use default initial size \ref c_nDefaultInitialSize
2322 , unsigned int nProbesetSize ///< probe set size, positive integer
2323 , unsigned int nProbesetThreshold ///< probe set threshold, <tt>nProbesetThreshold < nProbesetSize</tt>. If 0, nProbesetThreshold = nProbesetSize - 1
2324 , hash_tuple_type&& h ///< hash functor tuple of type <tt>std::tuple<H1, H2, ... Hn></tt> where <tt> n == \ref c_nArity </tt>
2326 : m_nProbesetSize( calc_probeset_size(nProbesetSize) )
2327 , m_nProbesetThreshold( nProbesetThreshold ? nProbesetThreshold : m_nProbesetSize - 1)
2328 , m_Hash( std::forward<hash_tuple_type>(h) )
2329 , m_MutexPolicy( cds::beans::ceil2(nInitialSize ? nInitialSize : c_nDefaultInitialSize ))
2331 check_common_constraints();
2332 check_probeset_properties();
2334 allocate_bucket_tables( nInitialSize ? cds::beans::ceil2( nInitialSize ) : c_nDefaultInitialSize );
2340 free_bucket_tables();
2344 /// Inserts new node
2346 The function inserts \p val in the set if it does not contain
2347 an item with key equal to \p val.
2349 Returns \p true if \p val is placed into the set, \p false otherwise.
2351 bool insert( value_type& val )
2353 return insert( val, []( value_type& ) {} );
2356 /// Inserts new node
2358 The function allows to split creating of new item into two part:
2359 - create item with key only
2360 - insert new item into the set
2361 - if inserting is success, calls \p f functor to initialize value-field of \p val.
2363 The functor signature is:
2365 void func( value_type& val );
2367 where \p val is the item inserted.
2369 The user-defined functor is called only if the inserting is success and can be passed by reference
2370 using <tt>boost::ref</tt>
2372 template <typename Func>
2373 bool insert( value_type& val, Func f )
2376 position arrPos[ c_nArity ];
2377 unsigned int nGoalTable;
2379 hashing( arrHash, val );
2380 node_type * pNode = node_traits::to_node_ptr( val );
2381 store_hash( pNode, arrHash );
2385 scoped_cell_lock guard( m_MutexPolicy, arrHash );
2387 if ( contains( arrPos, arrHash, val, key_predicate() ) != c_nUndefTable ) {
2388 m_Stat.onInsertFailed();
2392 for ( unsigned int i = 0; i < c_nArity; ++i ) {
2393 bucket_entry& refBucket = bucket( i, arrHash[i] );
2394 if ( refBucket.size() < m_nProbesetThreshold ) {
2395 refBucket.insert_after( arrPos[i].itPrev, pNode );
2396 cds::unref(f)( val );
2398 m_Stat.onInsertSuccess();
2403 for ( unsigned int i = 0; i < c_nArity; ++i ) {
2404 bucket_entry& refBucket = bucket( i, arrHash[i] );
2405 if ( refBucket.size() < m_nProbesetSize ) {
2406 refBucket.insert_after( arrPos[i].itPrev, pNode );
2407 cds::unref(f)( val );
2410 assert( refBucket.size() > 1 );
2411 copy_hash( arrHash, *node_traits::to_value_ptr( *refBucket.begin()) );
2417 m_Stat.onInsertResize();
2422 m_Stat.onInsertRelocate();
2423 if ( !relocate( nGoalTable, arrHash )) {
2424 m_Stat.onInsertRelocateFault();
2425 m_Stat.onInsertResize();
2429 m_Stat.onInsertSuccess();
2433 /// Ensures that the \p val exists in the set
2435 The operation performs inserting or changing data with lock-free manner.
2437 If the item \p val not found in the set, then \p val is inserted into the set.
2438 Otherwise, the functor \p func is called with item found.
2439 The functor signature is:
2441 void func( bool bNew, value_type& item, value_type& val );
2444 - \p bNew - \p true if the item has been inserted, \p false otherwise
2445 - \p item - item of the set
2446 - \p val - argument \p val passed into the \p ensure function
2447 If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
2448 refers to the same thing.
2450 The functor may change non-key fields of the \p item.
2452 You may pass \p func argument by reference using <tt>boost::ref</tt> or cds::ref.
2454 Returns <tt> std::pair<bool, bool> </tt> where \p first is \p true if operation is successful,
2455 \p second is \p true if new item has been added or \p false if the item with \p key
2456 already is in the set.
2458 template <typename Func>
2459 std::pair<bool, bool> ensure( value_type& val, Func func )
2462 position arrPos[ c_nArity ];
2463 unsigned int nGoalTable;
2465 hashing( arrHash, val );
2466 node_type * pNode = node_traits::to_node_ptr( val );
2467 store_hash( pNode, arrHash );
2471 scoped_cell_lock guard( m_MutexPolicy, arrHash );
2473 unsigned int nTable = contains( arrPos, arrHash, val, key_predicate() );
2474 if ( nTable != c_nUndefTable ) {
2475 cds::unref(func)( false, *node_traits::to_value_ptr( *arrPos[nTable].itFound ), val );
2476 m_Stat.onEnsureExist();
2477 return std::make_pair( true, false );
2480 node_type * pNode = node_traits::to_node_ptr( val );
2481 store_hash( pNode, arrHash );
2483 for ( unsigned int i = 0; i < c_nArity; ++i ) {
2484 bucket_entry& refBucket = bucket( i, arrHash[i] );
2485 if ( refBucket.size() < m_nProbesetThreshold ) {
2486 refBucket.insert_after( arrPos[i].itPrev, pNode );
2487 cds::unref(func)( true, val, val );
2489 m_Stat.onEnsureSuccess();
2490 return std::make_pair( true, true );
2494 for ( unsigned int i = 0; i < c_nArity; ++i ) {
2495 bucket_entry& refBucket = bucket( i, arrHash[i] );
2496 if ( refBucket.size() < m_nProbesetSize ) {
2497 refBucket.insert_after( arrPos[i].itPrev, pNode );
2498 cds::unref(func)( true, val, val );
2501 assert( refBucket.size() > 1 );
2502 copy_hash( arrHash, *node_traits::to_value_ptr( *refBucket.begin()) );
2508 m_Stat.onEnsureResize();
2513 m_Stat.onEnsureRelocate();
2514 if ( !relocate( nGoalTable, arrHash )) {
2515 m_Stat.onEnsureRelocateFault();
2516 m_Stat.onEnsureResize();
2520 m_Stat.onEnsureSuccess();
2521 return std::make_pair( true, true );
2524 /// Unlink the item \p val from the set
2526 The function searches the item \p val in the set and unlink it
2527 if it is found and is equal to \p val (here, the equality means that
2528 \p val belongs to the set: if \p item is an item found then
2529 unlink is successful iif <tt>&val == &item</tt>)
2531 The function returns \p true if success and \p false otherwise.
2533 bool unlink( value_type& val )
2536 hashing( arrHash, val );
2537 position arrPos[ c_nArity ];
2540 scoped_cell_lock guard( m_MutexPolicy, arrHash );
2542 unsigned int nTable = contains( arrPos, arrHash, val, key_predicate() );
2543 if ( nTable != c_nUndefTable && node_traits::to_value_ptr(*arrPos[nTable].itFound) == &val ) {
2544 bucket( nTable, arrHash[nTable]).remove( arrPos[nTable].itPrev, arrPos[nTable].itFound );
2546 m_Stat.onUnlinkSuccess();
2551 m_Stat.onUnlinkFailed();
2555 /// Deletes the item from the set
2556 /** \anchor cds_intrusive_CuckooSet_erase
2557 The function searches an item with key equal to \p val in the set,
2558 unlinks it from the set, and returns a pointer to unlinked item.
2560 If the item with key equal to \p val is not found the function return \p nullptr.
2562 Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
2564 template <typename Q>
2565 value_type * erase( Q const& val )
2567 return erase( val, [](value_type const&) {} );
2570 /// Deletes the item from the set using \p pred predicate for searching
2572 The function is an analog of \ref cds_intrusive_CuckooSet_erase "erase(Q const&)"
2573 but \p pred is used for key comparing.
2574 If cuckoo set is ordered, then \p Predicate should have the interface and semantics like \p std::less.
2575 If cuckoo set is unordered, then \p Predicate should have the interface and semantics like \p std::equal_to.
2576 \p Predicate must imply the same element order as the comparator used for building the set.
2578 template <typename Q, typename Predicate>
2579 value_type * erase_with( Q const& val, Predicate pred )
2581 return erase_( val, typename predicate_wrapper<Predicate>::type(), [](value_type const&) {} );
2584 /// Delete the item from the set
2585 /** \anchor cds_intrusive_CuckooSet_erase_func
2586 The function searches an item with key equal to \p val in the set,
2587 call \p f functor with item found, unlinks it from the set, and returns a pointer to unlinked item.
2589 The \p Func interface is
2592 void operator()( value_type const& item );
2595 The functor may be passed by reference with <tt>boost:ref</tt>
2597 If the item with key equal to \p val is not found the function return \p nullptr.
2599 Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
2601 template <typename Q, typename Func>
2602 value_type * erase( Q const& val, Func f )
2604 return erase_( val, key_predicate(), f );
2607 /// Deletes the item from the set using \p pred predicate for searching
2609 The function is an analog of \ref cds_intrusive_CuckooSet_erase_func "erase(Q const&, Func)"
2610 but \p pred is used for key comparing.
2611 If you use ordered cuckoo set, then \p Predicate should have the interface and semantics like \p std::less.
2612 If you use unordered cuckoo set, then \p Predicate should have the interface and semantics like \p std::equal_to.
2613 \p Predicate must imply the same element order as the comparator used for building the set.
2615 template <typename Q, typename Predicate, typename Func>
2616 value_type * erase_with( Q const& val, Predicate pred, Func f )
2618 return erase_( val, typename predicate_wrapper<Predicate>::type(), f );
2621 /// Find the key \p val
2622 /** \anchor cds_intrusive_CuckooSet_find_func
2623 The function searches the item with key equal to \p val and calls the functor \p f for item found.
2624 The interface of \p Func functor is:
2627 void operator()( value_type& item, Q& val );
2630 where \p item is the item found, \p val is the <tt>find</tt> function argument.
2632 You can pass \p f argument by reference using <tt>boost::ref</tt> or cds::ref.
2634 The functor may change non-key fields of \p item.
2636 The \p val argument is non-const since it can be used as \p f functor destination i.e., the functor
2637 may modify both arguments.
2639 Note the hash functor specified for class \p Traits template parameter
2640 should accept a parameter of type \p Q that can be not the same as \p value_type.
2642 The function returns \p true if \p val is found, \p false otherwise.
2644 template <typename Q, typename Func>
2645 bool find( Q& val, Func f )
2647 return find_( val, key_predicate(), f );
2650 /// Find the key \p val using \p pred predicate for comparing
2652 The function is an analog of \ref cds_intrusive_CuckooSet_find_func "find(Q&, Func)"
2653 but \p pred is used for key comparison.
2654 If you use ordered cuckoo set, then \p Predicate should have the interface and semantics like \p std::less.
2655 If you use unordered cuckoo set, then \p Predicate should have the interface and semantics like \p std::equal_to.
2656 \p pred must imply the same element order as the comparator used for building the set.
2658 template <typename Q, typename Predicate, typename Func>
2659 bool find_with( Q& val, Predicate pred, Func f )
2661 return find_( val, typename predicate_wrapper<Predicate>::type(), f );
2664 /// Find the key \p val
2665 /** \anchor cds_intrusive_CuckooSet_find_cfunc
2666 The function searches the item with key equal to \p val and calls the functor \p f for item found.
2667 The interface of \p Func functor is:
2670 void operator()( value_type& item, Q const& val );
2673 where \p item is the item found, \p val is the <tt>find</tt> function argument.
2675 You can pass \p f argument by reference using <tt>boost::ref</tt> or cds::ref.
2677 The functor may change non-key fields of \p item.
2679 The \p val argument is non-const since it can be used as \p f functor destination i.e., the functor
2680 may modify both arguments.
2682 The function returns \p true if \p val is found, \p false otherwise.
2684 template <typename Q, typename Func>
2685 bool find( Q const& val, Func f )
2687 return find_( val, key_predicate(), f );
2690 /// Find the key \p val using \p pred predicate for comparing
2692 The function is an analog of \ref cds_intrusive_CuckooSet_find_cfunc "find(Q const&, Func)"
2693 but \p pred is used for key comparison.
2694 If you use ordered cuckoo set, then \p Predicate should have the interface and semantics like \p std::less.
2695 If you use unordered cuckoo set, then \p Predicate should have the interface and semantics like \p std::equal_to.
2696 \p pred must imply the same element order as the comparator used for building the set.
2698 template <typename Q, typename Predicate, typename Func>
2699 bool find_with( Q const& val, Predicate pred, Func f )
2701 return find_( val, typename predicate_wrapper<Predicate>::type(), f );
2704 /// Find the key \p val
2705 /** \anchor cds_intrusive_CuckooSet_find_val
2706 The function searches the item with key equal to \p val
2707 and returns \p true if it is found, and \p false otherwise.
2709 Note the hash functor specified for class \p Traits template parameter
2710 should accept a parameter of type \p Q that can be not the same as \p value_type.
2712 template <typename Q>
2713 bool find( Q const& val )
2715 return find( val, [](value_type&, Q const& ) {} );
2718 /// Find the key \p val using \p pred predicate for comparing
2720 The function is an analog of \ref cds_intrusive_CuckooSet_find_val "find(Q const&)"
2721 but \p pred is used for key comparison.
2722 If you use ordered cuckoo set, then \p Predicate should have the interface and semantics like \p std::less.
2723 If you use unordered cuckoo set, then \p Predicate should have the interface and semantics like \p std::equal_to.
2724 \p pred must imply the same element order as the comparator used for building the set.
2726 template <typename Q, typename Predicate>
2727 bool find_with( Q const& val, Predicate pred )
2729 return find_with( val, typename predicate_wrapper<Predicate>::type(), [](value_type& , Q const& ) {} );
2734 The function unlinks all items from the set.
2735 For any item \ref disposer is called
2739 clear_and_dispose( disposer() );
2742 /// Clears the set and calls \p disposer for each item
2744 The function unlinks all items from the set calling \p disposer for each item.
2745 \p Disposer functor interface is:
2748 void operator()( value_type * p );
2752 The \ref disposer specified in \p Traits options is not called.
2754 template <typename Disposer>
2755 void clear_and_dispose( Disposer oDisposer )
2757 // locks entire array
2758 scoped_full_lock sl( m_MutexPolicy );
2760 for ( unsigned int i = 0; i < c_nArity; ++i ) {
2761 bucket_entry * pEntry = m_BucketTable[i];
2762 bucket_entry * pEnd = pEntry + m_nBucketMask + 1;
2763 for ( ; pEntry != pEnd ; ++pEntry ) {
2764 pEntry->clear( [&oDisposer]( node_type * pNode ){ oDisposer( node_traits::to_value_ptr( pNode )) ; } );
2767 m_ItemCounter.reset();
2770 /// Checks if the set is empty
2772 Emptiness is checked by item counting: if item count is zero then the set is empty.
2779 /// Returns item count in the set
2782 return m_ItemCounter;
2785 /// Returns the size of hash table
2787 The hash table size is non-constant and can be increased via resizing.
2789 size_t bucket_count() const
2791 return m_nBucketMask + 1;
2794 /// Returns lock array size
2795 size_t lock_count() const
2797 return m_MutexPolicy.lock_count();
2800 /// Returns const reference to internal statistics
2801 stat const& statistics() const
2806 /// Returns const reference to mutex policy internal statistics
2807 typename mutex_policy::statistics_type const& mutex_policy_statistics() const
2809 return m_MutexPolicy.statistics();
2812 }} // namespace cds::intrusive
2814 #endif // #ifndef __CDS_INTRUSIVE_CUCKOO_SET_H