2 This file is a part of libcds - Concurrent Data Structures library
4 (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2017
6 Source code repo: http://github.com/khizmax/libcds/
7 Download: http://sourceforge.net/projects/libcds/files/
9 Redistribution and use in source and binary forms, with or without
10 modification, are permitted provided that the following conditions are met:
12 * Redistributions of source code must retain the above copyright notice, this
13 list of conditions and the following disclaimer.
15 * Redistributions in binary form must reproduce the above copyright notice,
16 this list of conditions and the following disclaimer in the documentation
17 and/or other materials provided with the distribution.
19 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
20 AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
21 IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
22 DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
23 FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
24 DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
25 SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
26 CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
27 OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
28 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
31 #ifndef CDSLIB_INTRUSIVE_CUCKOO_SET_H
32 #define CDSLIB_INTRUSIVE_CUCKOO_SET_H
35 #include <type_traits>
37 #include <functional> // ref
38 #include <cds/intrusive/details/base.h>
39 #include <cds/opt/compare.h>
40 #include <cds/opt/hash.h>
41 #include <cds/sync/lock_array.h>
42 #include <cds/os/thread.h>
43 #include <cds/sync/spinlock.h>
46 namespace cds { namespace intrusive {
48 /// CuckooSet-related definitions
50 /// Option to define probeset type
52 The option specifies probeset type for the CuckooSet.
54 - \p cds::intrusive::cuckoo::list - the probeset is a single-linked list.
55 The node contains pointer to next node in probeset.
56 - \p cds::intrusive::cuckoo::vector<Capacity> - the probeset is a vector
57 with constant-size \p Capacity where \p Capacity is an <tt>unsigned int</tt> constant.
58 The node does not contain any auxiliary data.
60 template <typename Type>
64 template <typename Base>
65 struct pack: public Base {
66 typedef Type probeset_type;
71 /// Option specifying whether to store hash values in the node
73 This option reserves additional space in the hook to store the hash value of the object once it's introduced in the container.
74 When this option is used, the unordered container will store the calculated hash value in the hook and rehashing operations won't need
75 to recalculate the hash of the value. This option will improve the performance of unordered containers
76 when rehashing is frequent or hashing the value is a slow operation
78 The \p Count template parameter defines the size of hash array. Remember that cuckoo hashing implies at least two
81 Possible values of \p Count:
82 - 0 - no hash storing in the node
83 - greater that 1 - store hash values.
85 Value 1 is deprecated.
87 template <unsigned int Count>
91 template <typename Base>
92 struct pack: public Base {
93 static unsigned int const store_hash = Count;
100 // Probeset type placeholders
101 struct list_probeset_class;
102 struct vector_probeset_class;
106 /// List probeset type
110 /// Vector probeset type
111 template <unsigned int Capacity>
115 static unsigned int const c_nCapacity = Capacity;
121 - \p ProbesetType - type of probeset. Can be \p cds::intrusive::cuckoo::list
122 or \p cds::intrusive::cuckoo::vector<Capacity>.
123 - \p StoreHashCount - constant that defines whether to store node hash values.
124 See cuckoo::store_hash option for explanation
125 - \p Tag - a \ref cds_intrusive_hook_tag "tag"
127 template <typename ProbesetType = cuckoo::list, unsigned int StoreHashCount = 0, typename Tag = opt::none>
129 #ifdef CDS_DOXYGEN_INVOKED
131 typedef ProbesetType probeset_type ; ///< Probeset type
132 typedef Tag tag ; ///< Tag
133 static unsigned int const hash_array_size = StoreHashCount ; ///< The size of hash array
139 template <typename Tag>
140 struct node< cuckoo::list, 0, Tag>
142 typedef list_probeset_class probeset_class;
143 typedef cuckoo::list probeset_type;
145 static unsigned int const hash_array_size = 0;
146 static unsigned int const probeset_size = 0;
150 CDS_CONSTEXPR node() CDS_NOEXCEPT
154 void store_hash( size_t * )
157 size_t * get_hash() const
159 // This node type does not store hash values!!!
170 template <unsigned int StoreHashCount, typename Tag>
171 struct node< cuckoo::list, StoreHashCount, Tag>
173 typedef list_probeset_class probeset_class;
174 typedef cuckoo::list probeset_type;
176 static unsigned int const hash_array_size = StoreHashCount;
177 static unsigned int const probeset_size = 0;
180 size_t m_arrHash[ hash_array_size ];
185 memset( m_arrHash, 0, sizeof(m_arrHash));
188 void store_hash( size_t * pHashes )
190 memcpy( m_arrHash, pHashes, hash_array_size );
193 size_t * get_hash() const
195 return const_cast<size_t *>( m_arrHash );
204 template <unsigned int VectorSize, typename Tag>
205 struct node< cuckoo::vector<VectorSize>, 0, Tag>
207 typedef vector_probeset_class probeset_class;
208 typedef cuckoo::vector<VectorSize> probeset_type;
210 static unsigned int const hash_array_size = 0;
211 static unsigned int const probeset_size = probeset_type::c_nCapacity;
216 void store_hash( size_t * )
219 size_t * get_hash() const
221 // This node type does not store hash values!!!
230 template <unsigned int VectorSize, unsigned int StoreHashCount, typename Tag>
231 struct node< cuckoo::vector<VectorSize>, StoreHashCount, Tag>
233 typedef vector_probeset_class probeset_class;
234 typedef cuckoo::vector<VectorSize> probeset_type;
236 static unsigned int const hash_array_size = StoreHashCount;
237 static unsigned int const probeset_size = probeset_type::c_nCapacity;
239 size_t m_arrHash[ hash_array_size ];
243 memset( m_arrHash, 0, sizeof(m_arrHash));
246 void store_hash( size_t * pHashes )
248 memcpy( m_arrHash, pHashes, hash_array_size );
251 size_t * get_hash() const
253 return const_cast<size_t *>( m_arrHash );
263 struct default_hook {
264 typedef cuckoo::list probeset_type;
265 static unsigned int const store_hash = 0;
266 typedef opt::none tag;
269 template < typename HookType, typename... Options>
272 typedef typename opt::make_options< default_hook, Options...>::type traits;
274 typedef typename traits::probeset_type probeset_type;
275 typedef typename traits::tag tag;
276 static unsigned int const store_hash = traits::store_hash;
278 typedef node<probeset_type, store_hash, tag> node_type;
280 typedef HookType hook_type;
287 - \p cuckoo::probeset_type - probeset type. Defaul is \p cuckoo::list
288 - \p cuckoo::store_hash - store hash values in the node or not. Default is 0 (no storing)
289 - \p opt::tag - a \ref cds_intrusive_hook_tag "tag"
291 template < typename... Options >
292 struct base_hook: public hook< opt::base_hook_tag, Options... >
297 \p MemberOffset defines offset in bytes of \ref node member into your structure.
298 Use \p offsetof macro to define \p MemberOffset
301 - \p cuckoo::probeset_type - probeset type. Defaul is \p cuckoo::list
302 - \p cuckoo::store_hash - store hash values in the node or not. Default is 0 (no storing)
303 - \p opt::tag - a \ref cds_intrusive_hook_tag "tag"
305 template < size_t MemberOffset, typename... Options >
306 struct member_hook: public hook< opt::member_hook_tag, Options... >
309 static const size_t c_nMemberOffset = MemberOffset;
315 \p NodeTraits defines type traits for node.
316 See \ref node_traits for \p NodeTraits interface description
319 - \p cuckoo::probeset_type - probeset type. Defaul is \p cuckoo::list
320 - \p cuckoo::store_hash - store hash values in the node or not. Default is 0 (no storing)
321 - \p opt::tag - a \ref cds_intrusive_hook_tag "tag"
323 template <typename NodeTraits, typename... Options >
324 struct traits_hook: public hook< opt::traits_hook_tag, Options... >
327 typedef NodeTraits node_traits;
331 /// Internal statistics for \ref striping mutex policy
332 struct striping_stat {
333 typedef cds::atomicity::event_counter counter_type; ///< Counter type
335 counter_type m_nCellLockCount ; ///< Count of obtaining cell lock
336 counter_type m_nCellTryLockCount ; ///< Count of cell \p try_lock attempts
337 counter_type m_nFullLockCount ; ///< Count of obtaining full lock
338 counter_type m_nResizeLockCount ; ///< Count of obtaining resize lock
339 counter_type m_nResizeCount ; ///< Count of resize event
342 void onCellLock() { ++m_nCellLockCount; }
343 void onCellTryLock() { ++m_nCellTryLockCount; }
344 void onFullLock() { ++m_nFullLockCount; }
345 void onResizeLock() { ++m_nResizeLockCount; }
346 void onResize() { ++m_nResizeCount; }
350 /// Dummy internal statistics for \ref striping mutex policy
351 struct empty_striping_stat {
353 void onCellLock() const {}
354 void onCellTryLock() const {}
355 void onFullLock() const {}
356 void onResizeLock() const {}
357 void onResize() const {}
361 /// Lock striping concurrent access policy
363 This is one of available opt::mutex_policy option type for CuckooSet
365 Lock striping is very simple technique.
366 The cuckoo set consists of the bucket tables and the array of locks.
367 There is single lock array for each bucket table, at least, the count of bucket table is 2.
368 Initially, the capacity of lock array and each bucket table is the same.
369 When set is resized, bucket table capacity will be doubled but lock array will not.
370 The lock \p i protects each bucket \p j, where <tt> j = i mod L </tt>,
371 where \p L - the size of lock array.
373 The policy contains an internal array of \p RecursiveLock locks.
376 - \p RecursiveLock - the type of recursive mutex. The default is \p std::recursive_mutex. The mutex type should be default-constructible.
377 Note that a recursive spin-lock is not suitable for lock striping for performance reason.
378 - \p Arity - unsigned int constant that specifies an arity. The arity is the count of hash functors, i.e., the
379 count of lock arrays. Default value is 2.
380 - \p Alloc - allocator type used for lock array memory allocation. Default is \p CDS_DEFAULT_ALLOCATOR.
381 - \p Stat - internal statistics type. Note that this template argument is automatically selected by \ref CuckooSet
382 class according to its \p opt::stat option.
385 class RecursiveLock = std::recursive_mutex,
386 unsigned int Arity = 2,
387 class Alloc = CDS_DEFAULT_ALLOCATOR,
388 class Stat = empty_striping_stat
393 typedef RecursiveLock lock_type ; ///< lock type
394 typedef Alloc allocator_type ; ///< allocator type
395 static unsigned int const c_nArity = Arity ; ///< the arity
396 typedef Stat statistics_type ; ///< Internal statistics type (\ref striping_stat or \ref empty_striping_stat)
399 typedef striping_stat real_stat;
400 typedef empty_striping_stat empty_stat;
402 template <typename Stat2>
403 struct rebind_statistics {
404 typedef striping<lock_type, c_nArity, allocator_type, Stat2> other;
408 typedef cds::sync::lock_array< lock_type, cds::sync::pow2_select_policy, allocator_type > lock_array_type ; ///< lock array type
412 class lock_array: public lock_array_type
416 lock_array(): lock_array_type( typename lock_array_type::select_cell_policy(2)) {}
419 lock_array( size_t nCapacity ): lock_array_type( nCapacity, typename lock_array_type::select_cell_policy(nCapacity)) {}
422 class scoped_lock: public std::unique_lock< lock_array_type >
424 typedef std::unique_lock< lock_array_type > base_class;
426 scoped_lock( lock_array& arrLock, size_t nHash ): base_class( arrLock, nHash ) {}
432 lock_array m_Locks[c_nArity] ; ///< array of \p lock_array_type
433 statistics_type m_Stat ; ///< internal statistics
438 class scoped_cell_lock {
439 lock_type * m_guard[c_nArity];
442 scoped_cell_lock( striping& policy, size_t const* arrHash )
444 for ( unsigned int i = 0; i < c_nArity; ++i ) {
445 m_guard[i] = &( policy.m_Locks[i].at( policy.m_Locks[i].lock( arrHash[i] )));
447 policy.m_Stat.onCellLock();
452 for ( unsigned int i = 0; i < c_nArity; ++i )
453 m_guard[i]->unlock();
457 class scoped_cell_trylock
459 typedef typename lock_array_type::lock_type lock_type;
461 lock_type * m_guard[c_nArity];
465 scoped_cell_trylock( striping& policy, size_t const* arrHash )
467 size_t nCell = policy.m_Locks[0].try_lock( arrHash[0] );
468 m_bLocked = nCell != lock_array_type::c_nUnspecifiedCell;
470 m_guard[0] = &(policy.m_Locks[0].at(nCell));
471 for ( unsigned int i = 1; i < c_nArity; ++i ) {
472 m_guard[i] = &( policy.m_Locks[i].at( policy.m_Locks[i].lock( arrHash[i] )));
476 std::fill( m_guard, m_guard + c_nArity, nullptr );
478 policy.m_Stat.onCellTryLock();
480 ~scoped_cell_trylock()
483 for ( unsigned int i = 0; i < c_nArity; ++i )
484 m_guard[i]->unlock();
494 class scoped_full_lock {
495 std::unique_lock< lock_array_type > m_guard;
497 scoped_full_lock( striping& policy )
498 : m_guard( policy.m_Locks[0] )
500 policy.m_Stat.onFullLock();
503 /// Ctor for scoped_resize_lock - no statistics is incremented
504 scoped_full_lock( striping& policy, bool )
505 : m_guard( policy.m_Locks[0] )
509 class scoped_resize_lock: public scoped_full_lock {
511 scoped_resize_lock( striping& policy )
512 : scoped_full_lock( policy, false )
514 policy.m_Stat.onResizeLock();
522 size_t nLockCount ///< The size of lock array. Must be power of two.
525 // Trick: initialize the array of locks
526 for ( unsigned int i = 0; i < c_nArity; ++i ) {
527 lock_array * pArr = m_Locks + i;
528 pArr->lock_array::~lock_array();
529 new ( pArr ) lock_array( nLockCount );
533 /// Returns lock array size
535 Lock array size is unchanged during \p striping object lifetime
537 size_t lock_count() const
539 return m_Locks[0].size();
543 void resize( size_t )
549 /// Returns the arity of striping mutex policy
550 CDS_CONSTEXPR unsigned int arity() const CDS_NOEXCEPT
555 /// Returns internal statistics
556 statistics_type const& statistics() const
562 /// Internal statistics for \ref refinable mutex policy
563 struct refinable_stat {
564 typedef cds::atomicity::event_counter counter_type ; ///< Counter type
566 counter_type m_nCellLockCount ; ///< Count of obtaining cell lock
567 counter_type m_nCellLockWaitResizing ; ///< Count of loop iteration to wait for resizing
568 counter_type m_nCellLockArrayChanged ; ///< Count of event "Lock array has been changed when obtaining cell lock"
569 counter_type m_nCellLockFailed ; ///< Count of event "Cell lock failed because of the array is owned by other thread"
571 counter_type m_nSecondCellLockCount ; ///< Count of obtaining cell lock when another cell is already locked
572 counter_type m_nSecondCellLockFailed ; ///< Count of unsuccess obtaining cell lock when another cell is already locked
574 counter_type m_nFullLockCount ; ///< Count of obtaining full lock
575 counter_type m_nFullLockIter ; ///< Count of unsuccessfull iteration to obtain full lock
577 counter_type m_nResizeLockCount ; ///< Count of obtaining resize lock
578 counter_type m_nResizeLockIter ; ///< Count of unsuccessfull iteration to obtain resize lock
579 counter_type m_nResizeLockArrayChanged; ///< Count of event "Lock array has been changed when obtaining resize lock"
580 counter_type m_nResizeCount ; ///< Count of resize event
583 void onCellLock() { ++m_nCellLockCount; }
584 void onCellWaitResizing() { ++m_nCellLockWaitResizing; }
585 void onCellArrayChanged() { ++m_nCellLockArrayChanged; }
586 void onCellLockFailed() { ++m_nCellLockFailed; }
587 void onSecondCellLock() { ++m_nSecondCellLockCount; }
588 void onSecondCellLockFailed() { ++m_nSecondCellLockFailed; }
589 void onFullLock() { ++m_nFullLockCount; }
590 void onFullLockIter() { ++m_nFullLockIter; }
591 void onResizeLock() { ++m_nResizeLockCount; }
592 void onResizeLockIter() { ++m_nResizeLockIter; }
593 void onResizeLockArrayChanged() { ++m_nResizeLockArrayChanged; }
594 void onResize() { ++m_nResizeCount; }
598 /// Dummy internal statistics for \ref refinable mutex policy
599 struct empty_refinable_stat {
601 void onCellLock() const {}
602 void onCellWaitResizing() const {}
603 void onCellArrayChanged() const {}
604 void onCellLockFailed() const {}
605 void onSecondCellLock() const {}
606 void onSecondCellLockFailed() const {}
607 void onFullLock() const {}
608 void onFullLockIter() const {}
609 void onResizeLock() const {}
610 void onResizeLockIter() const {}
611 void onResizeLockArrayChanged() const {}
612 void onResize() const {}
616 /// Refinable concurrent access policy
618 This is one of available \p opt::mutex_policy option type for \p CuckooSet
620 Refining is like a striping technique (see \p cuckoo::striping)
621 but it allows growing the size of lock array when resizing the hash table.
622 So, the sizes of hash table and lock array are equal.
625 - \p RecursiveLock - the type of mutex. Reentrant (recursive) mutex is required.
626 The default is \p std::recursive_mutex. The mutex type should be default-constructible.
627 - \p Arity - unsigned int constant that specifies an arity. The arity is the count of hash functors, i.e., the
628 count of lock arrays. Default value is 2.
629 - \p BackOff - back-off strategy. Default is \p cds::backoff::Default
630 - \p Alloc - allocator type used for lock array memory allocation. Default is \p CDS_DEFAULT_ALLOCATOR.
631 - \p Stat - internal statistics type. Note that this template argument is automatically selected by \ref CuckooSet
632 class according to its \p opt::stat option.
635 class RecursiveLock = std::recursive_mutex,
636 unsigned int Arity = 2,
637 typename BackOff = cds::backoff::Default,
638 class Alloc = CDS_DEFAULT_ALLOCATOR,
639 class Stat = empty_refinable_stat
644 typedef RecursiveLock lock_type ; ///< lock type
645 typedef Alloc allocator_type ; ///< allocator type
646 typedef BackOff back_off ; ///< back-off strategy
647 typedef Stat statistics_type ; ///< internal statistics type
648 static unsigned int const c_nArity = Arity; ///< the arity
651 typedef refinable_stat real_stat;
652 typedef empty_refinable_stat empty_stat;
654 template <typename Stat2>
655 struct rebind_statistics {
656 typedef refinable< lock_type, c_nArity, back_off, allocator_type, Stat2> other;
662 typedef cds::sync::trivial_select_policy lock_selection_policy;
664 class lock_array_type
665 : public cds::sync::lock_array< lock_type, lock_selection_policy, allocator_type >
666 , public std::enable_shared_from_this< lock_array_type >
668 typedef cds::sync::lock_array< lock_type, lock_selection_policy, allocator_type > lock_array_base;
670 lock_array_type( size_t nCapacity )
671 : lock_array_base( nCapacity )
674 typedef std::shared_ptr< lock_array_type > lock_array_ptr;
675 typedef cds::details::Allocator< lock_array_type, allocator_type > lock_array_allocator;
677 typedef unsigned long long owner_t;
678 typedef cds::OS::ThreadId threadId_t;
680 typedef cds::sync::spin spinlock_type;
681 typedef std::unique_lock< spinlock_type > scoped_spinlock;
686 static owner_t const c_nOwnerMask = (((owner_t) 1) << (sizeof(owner_t) * 8 - 1)) - 1;
688 atomics::atomic< owner_t > m_Owner ; ///< owner mark (thread id + boolean flag)
689 atomics::atomic<size_t> m_nCapacity ; ///< lock array capacity
690 lock_array_ptr m_arrLocks[ c_nArity ] ; ///< Lock array. The capacity of array is specified in constructor.
691 spinlock_type m_access ; ///< access to m_arrLocks
692 statistics_type m_Stat ; ///< internal statistics
697 struct lock_array_disposer {
698 void operator()( lock_array_type * pArr )
700 // Seems, there is a false positive in std::shared_ptr deallocation in uninstrumented libc++
701 // see, for example, https://groups.google.com/forum/#!topic/thread-sanitizer/eHu4dE_z7Cc
702 // https://reviews.llvm.org/D21609
703 CDS_TSAN_ANNOTATE_IGNORE_WRITES_BEGIN;
704 lock_array_allocator().Delete( pArr );
705 CDS_TSAN_ANNOTATE_IGNORE_WRITES_END;
709 lock_array_ptr create_lock_array( size_t nCapacity )
711 return lock_array_ptr( lock_array_allocator().New( nCapacity ), lock_array_disposer());
714 void acquire( size_t const * arrHash, lock_array_ptr * pLockArr, lock_type ** parrLock )
716 owner_t me = (owner_t) cds::OS::get_current_thread_id();
724 scoped_spinlock sl(m_access);
725 for ( unsigned int i = 0; i < c_nArity; ++i )
726 pLockArr[i] = m_arrLocks[i];
727 cur_capacity = m_nCapacity.load( atomics::memory_order_acquire );
730 // wait while resizing
732 who = m_Owner.load( atomics::memory_order_acquire );
733 if ( !( who & 1 ) || (who >> 1) == (me & c_nOwnerMask))
736 m_Stat.onCellWaitResizing();
739 if ( cur_capacity == m_nCapacity.load( atomics::memory_order_acquire )) {
741 size_t const nMask = pLockArr[0]->size() - 1;
742 assert( cds::beans::is_power2( nMask + 1 ));
744 for ( unsigned int i = 0; i < c_nArity; ++i ) {
745 parrLock[i] = &( pLockArr[i]->at( arrHash[i] & nMask ));
749 who = m_Owner.load( atomics::memory_order_acquire );
750 if ( ( !(who & 1) || (who >> 1) == (me & c_nOwnerMask)) && cur_capacity == m_nCapacity.load( atomics::memory_order_acquire )) {
755 for ( unsigned int i = 0; i < c_nArity; ++i )
756 parrLock[i]->unlock();
758 m_Stat.onCellLockFailed();
761 m_Stat.onCellArrayChanged();
763 // clears pLockArr can lead to calling dtor for each item of pLockArr[i] that may be a heavy-weighted operation
764 // (each pLockArr[i] is a shared pointer to array of a ton of mutexes)
765 // It is better to do this before the next loop iteration where we will use spin-locked assignment to pLockArr
766 // However, destructing a lot of mutexes under spin-lock is a bad solution
767 for ( unsigned int i = 0; i < c_nArity; ++i )
772 bool try_second_acquire( size_t const * arrHash, lock_type ** parrLock )
774 // It is assumed that the current thread already has a lock
775 // and requires a second lock for other hash
777 size_t const nMask = m_nCapacity.load(atomics::memory_order_acquire) - 1;
778 size_t nCell = m_arrLocks[0]->try_lock( arrHash[0] & nMask);
779 if ( nCell == lock_array_type::c_nUnspecifiedCell ) {
780 m_Stat.onSecondCellLockFailed();
783 parrLock[0] = &(m_arrLocks[0]->at(nCell));
785 for ( unsigned int i = 1; i < c_nArity; ++i ) {
786 parrLock[i] = &( m_arrLocks[i]->at( m_arrLocks[i]->lock( arrHash[i] & nMask)));
789 m_Stat.onSecondCellLock();
795 owner_t me = (owner_t) cds::OS::get_current_thread_id();
800 if ( m_Owner.compare_exchange_strong( ownNull, (me << 1) | 1, atomics::memory_order_acq_rel, atomics::memory_order_relaxed )) {
801 m_arrLocks[0]->lock_all();
807 m_Stat.onFullLockIter();
813 m_arrLocks[0]->unlock_all();
814 m_Owner.store( 0, atomics::memory_order_release );
817 void acquire_resize( lock_array_ptr * pOldLocks )
819 owner_t me = (owner_t) cds::OS::get_current_thread_id();
824 scoped_spinlock sl(m_access);
825 for ( unsigned int i = 0; i < c_nArity; ++i )
826 pOldLocks[i] = m_arrLocks[i];
827 cur_capacity = m_nCapacity.load( atomics::memory_order_acquire );
832 if ( m_Owner.compare_exchange_strong( ownNull, (me << 1) | 1, atomics::memory_order_acq_rel, atomics::memory_order_relaxed )) {
833 if ( cur_capacity == m_nCapacity.load( atomics::memory_order_acquire )) {
834 pOldLocks[0]->lock_all();
835 m_Stat.onResizeLock();
839 m_Owner.store( 0, atomics::memory_order_release );
840 m_Stat.onResizeLockArrayChanged();
843 m_Stat.onResizeLockIter();
845 // clears pOldLocks can lead to calling dtor for each item of pOldLocks[i] that may be a heavy-weighted operation
846 // (each pOldLocks[i] is a shared pointer to array of a ton of mutexes)
847 // It is better to do this before the next loop iteration where we will use spin-locked assignment to pOldLocks
848 // However, destructing a lot of mutexes under spin-lock is a bad solution
849 for ( unsigned int i = 0; i < c_nArity; ++i )
850 pOldLocks[i].reset();
854 void release_resize( lock_array_ptr * pOldLocks )
856 m_Owner.store( 0, atomics::memory_order_release );
857 pOldLocks[0]->unlock_all();
863 class scoped_cell_lock {
864 lock_type * m_arrLock[ c_nArity ];
865 lock_array_ptr m_arrLockArr[ c_nArity ];
868 scoped_cell_lock( refinable& policy, size_t const* arrHash )
870 policy.acquire( arrHash, m_arrLockArr, m_arrLock );
875 for ( unsigned int i = 0; i < c_nArity; ++i )
876 m_arrLock[i]->unlock();
880 class scoped_cell_trylock {
881 lock_type * m_arrLock[ c_nArity ];
885 scoped_cell_trylock( refinable& policy, size_t const* arrHash )
887 m_bLocked = policy.try_second_acquire( arrHash, m_arrLock );
890 ~scoped_cell_trylock()
893 for ( unsigned int i = 0; i < c_nArity; ++i )
894 m_arrLock[i]->unlock();
904 class scoped_full_lock {
907 scoped_full_lock( refinable& policy )
910 policy.acquire_all();
914 m_policy.release_all();
918 class scoped_resize_lock
921 lock_array_ptr m_arrLocks[ c_nArity ];
923 scoped_resize_lock( refinable& policy )
926 policy.acquire_resize( m_arrLocks );
928 ~scoped_resize_lock()
930 m_policy.release_resize( m_arrLocks );
938 size_t nLockCount ///< The size of lock array. Must be power of two.
940 , m_nCapacity( nLockCount )
942 assert( cds::beans::is_power2( nLockCount ));
943 for ( unsigned int i = 0; i < c_nArity; ++i )
944 m_arrLocks[i] = create_lock_array( nLockCount );
948 void resize( size_t nCapacity )
950 lock_array_ptr pNew[ c_nArity ];
951 for ( unsigned int i = 0; i < c_nArity; ++i )
952 pNew[i] = create_lock_array( nCapacity );
955 scoped_spinlock sl(m_access);
956 m_nCapacity.store( nCapacity, atomics::memory_order_release );
957 for ( unsigned int i = 0; i < c_nArity; ++i )
958 m_arrLocks[i] = pNew[i];
965 /// Returns lock array size
967 Lock array size is not a constant for \p refinable policy and can be changed when the set is resized.
969 size_t lock_count() const
971 return m_nCapacity.load(atomics::memory_order_relaxed);
974 /// Returns the arity of \p refinable mutex policy
975 CDS_CONSTEXPR unsigned int arity() const CDS_NOEXCEPT
980 /// Returns internal statistics
981 statistics_type const& statistics() const
987 /// \p CuckooSet internal statistics
989 typedef cds::atomicity::event_counter counter_type ; ///< Counter type
991 counter_type m_nRelocateCallCount ; ///< Count of \p relocate() function call
992 counter_type m_nRelocateRoundCount ; ///< Count of attempts to relocate items
993 counter_type m_nFalseRelocateCount ; ///< Count of unneeded attempts of \p relocate call
994 counter_type m_nSuccessRelocateCount ; ///< Count of successful item relocating
995 counter_type m_nRelocateAboveThresholdCount; ///< Count of item relocating above probeset threshold
996 counter_type m_nFailedRelocateCount ; ///< Count of failed relocation attemp (when all probeset is full)
998 counter_type m_nResizeCallCount ; ///< Count of \p resize() function call
999 counter_type m_nFalseResizeCount ; ///< Count of false \p resize() function call (when other thread has been resized the set)
1000 counter_type m_nResizeSuccessNodeMove; ///< Count of successful node moving when resizing
1001 counter_type m_nResizeRelocateCall ; ///< Count of \p relocate() function call from \p resize function
1003 counter_type m_nInsertSuccess ; ///< Count of successful \p insert() function call
1004 counter_type m_nInsertFailed ; ///< Count of failed \p insert() function call
1005 counter_type m_nInsertResizeCount ; ///< Count of \p resize() function call from \p insert()
1006 counter_type m_nInsertRelocateCount ; ///< Count of \p relocate() function call from \p insert()
1007 counter_type m_nInsertRelocateFault ; ///< Count of failed \p relocate() function call from \p insert()
1009 counter_type m_nUpdateExistCount ; ///< Count of call \p update() function for existing node
1010 counter_type m_nUpdateSuccessCount ; ///< Count of successful \p insert() function call for new node
1011 counter_type m_nUpdateResizeCount ; ///< Count of \p resize() function call from \p update()
1012 counter_type m_nUpdateRelocateCount ; ///< Count of \p relocate() function call from \p update()
1013 counter_type m_nUpdateRelocateFault ; ///< Count of failed \p relocate() function call from \p update()
1015 counter_type m_nUnlinkSuccess ; ///< Count of success \p unlink() function call
1016 counter_type m_nUnlinkFailed ; ///< Count of failed \p unlink() function call
1018 counter_type m_nEraseSuccess ; ///< Count of success \p erase() function call
1019 counter_type m_nEraseFailed ; ///< Count of failed \p erase() function call
1021 counter_type m_nFindSuccess ; ///< Count of success \p find() function call
1022 counter_type m_nFindFailed ; ///< Count of failed \p find() function call
1024 counter_type m_nFindEqualSuccess ; ///< Count of success \p find_equal() function call
1025 counter_type m_nFindEqualFailed ; ///< Count of failed \p find_equal() function call
1027 counter_type m_nFindWithSuccess ; ///< Count of success \p find_with() function call
1028 counter_type m_nFindWithFailed ; ///< Count of failed \p find_with() function call
1031 void onRelocateCall() { ++m_nRelocateCallCount; }
1032 void onRelocateRound() { ++m_nRelocateRoundCount; }
1033 void onFalseRelocateRound() { ++m_nFalseRelocateCount; }
1034 void onSuccessRelocateRound(){ ++m_nSuccessRelocateCount; }
1035 void onRelocateAboveThresholdRound() { ++m_nRelocateAboveThresholdCount; }
1036 void onFailedRelocate() { ++m_nFailedRelocateCount; }
1038 void onResizeCall() { ++m_nResizeCallCount; }
1039 void onFalseResizeCall() { ++m_nFalseResizeCount; }
1040 void onResizeSuccessMove() { ++m_nResizeSuccessNodeMove; }
1041 void onResizeRelocateCall() { ++m_nResizeRelocateCall; }
1043 void onInsertSuccess() { ++m_nInsertSuccess; }
1044 void onInsertFailed() { ++m_nInsertFailed; }
1045 void onInsertResize() { ++m_nInsertResizeCount; }
1046 void onInsertRelocate() { ++m_nInsertRelocateCount; }
1047 void onInsertRelocateFault() { ++m_nInsertRelocateFault; }
1049 void onUpdateExist() { ++m_nUpdateExistCount; }
1050 void onUpdateSuccess() { ++m_nUpdateSuccessCount; }
1051 void onUpdateResize() { ++m_nUpdateResizeCount; }
1052 void onUpdateRelocate() { ++m_nUpdateRelocateCount; }
1053 void onUpdateRelocateFault() { ++m_nUpdateRelocateFault; }
1055 void onUnlinkSuccess() { ++m_nUnlinkSuccess; }
1056 void onUnlinkFailed() { ++m_nUnlinkFailed; }
1058 void onEraseSuccess() { ++m_nEraseSuccess; }
1059 void onEraseFailed() { ++m_nEraseFailed; }
1061 void onFindSuccess() { ++m_nFindSuccess; }
1062 void onFindFailed() { ++m_nFindFailed; }
1064 void onFindWithSuccess() { ++m_nFindWithSuccess; }
1065 void onFindWithFailed() { ++m_nFindWithFailed; }
1069 /// CuckooSet empty internal statistics
1072 void onRelocateCall() const {}
1073 void onRelocateRound() const {}
1074 void onFalseRelocateRound() const {}
1075 void onSuccessRelocateRound()const {}
1076 void onRelocateAboveThresholdRound() const {}
1077 void onFailedRelocate() const {}
1079 void onResizeCall() const {}
1080 void onFalseResizeCall() const {}
1081 void onResizeSuccessMove() const {}
1082 void onResizeRelocateCall() const {}
1084 void onInsertSuccess() const {}
1085 void onInsertFailed() const {}
1086 void onInsertResize() const {}
1087 void onInsertRelocate() const {}
1088 void onInsertRelocateFault() const {}
1090 void onUpdateExist() const {}
1091 void onUpdateSuccess() const {}
1092 void onUpdateResize() const {}
1093 void onUpdateRelocate() const {}
1094 void onUpdateRelocateFault() const {}
1096 void onUnlinkSuccess() const {}
1097 void onUnlinkFailed() const {}
1099 void onEraseSuccess() const {}
1100 void onEraseFailed() const {}
1102 void onFindSuccess() const {}
1103 void onFindFailed() const {}
1105 void onFindWithSuccess() const {}
1106 void onFindWithFailed() const {}
1110 /// Type traits for CuckooSet class
1115 Possible values are: cuckoo::base_hook, cuckoo::member_hook, cuckoo::traits_hook.
1117 typedef base_hook<> hook;
1119 /// Hash functors tuple
1121 This is mandatory type and has no predefined one.
1123 At least, two hash functors should be provided. All hash functor
1124 should be orthogonal (different): for each <tt> i,j: i != j => h[i](x) != h[j](x) </tt>.
1125 The hash functors are defined as <tt> std::tuple< H1, H2, ... Hn > </tt>:
1126 \@code cds::opt::hash< std::tuple< h1, h2 > > \@endcode
1127 The number of hash functors specifies the number \p k - the count of hash tables in cuckoo hashing.
1129 To specify hash tuple in traits you should use \p cds::opt::hash_tuple:
1131 struct my_traits: public cds::intrusive::cuckoo::traits {
1132 typedef cds::opt::hash_tuple< hash1, hash2 > hash;
1136 typedef cds::opt::none hash;
1138 /// Concurrent access policy
1140 Available opt::mutex_policy types:
1141 - \p cuckoo::striping - simple, but the lock array is not resizable
1142 - \p cuckoo::refinable - resizable lock array, but more complex access to set data.
1144 Default is \p cuckoo::striping.
1146 typedef cuckoo::striping<> mutex_policy;
1148 /// Key equality functor
1150 Default is <tt>std::equal_to<T></tt>
1152 typedef opt::none equal_to;
1154 /// Key comparing functor
1156 No default functor is provided. If the option is not specified, the \p less is used.
1158 typedef opt::none compare;
1160 /// specifies binary predicate used for key comparison.
1162 Default is \p std::less<T>.
1164 typedef opt::none less;
1168 The type for item counting feature.
1169 Default is \p cds::atomicity::item_counter
1171 Only atomic item counter type is allowed.
1173 typedef atomicity::item_counter item_counter;
1177 The allocator type for allocating bucket tables.
1179 typedef CDS_DEFAULT_ALLOCATOR allocator;
1183 The disposer functor is used in \p CuckooSet::clear() member function
1186 typedef intrusive::opt::v::empty_disposer disposer;
1188 /// Internal statistics. Available statistics: \p cuckoo::stat, \p cuckoo::empty_stat
1189 typedef empty_stat stat;
1192 /// Metafunction converting option list to \p CuckooSet traits
1194 Template argument list \p Options... are:
1195 - \p intrusive::opt::hook - hook used. Possible values are: \p cuckoo::base_hook, \p cuckoo::member_hook,
1196 \p cuckoo::traits_hook.
1197 If the option is not specified, <tt>%cuckoo::base_hook<></tt> is used.
1198 - \p opt::hash - hash functor tuple, mandatory option. At least, two hash functors should be provided. All hash functor
1199 should be orthogonal (different): for each <tt> i,j: i != j => h[i](x) != h[j](x) </tt>.
1200 The hash functors are passed as <tt> std::tuple< H1, H2, ... Hn > </tt>. The number of hash functors specifies
1201 the number \p k - the count of hash tables in cuckoo hashing.
1202 - \p opt::mutex_policy - concurrent access policy.
1203 Available policies: \p cuckoo::striping, \p cuckoo::refinable.
1204 Default is \p %cuckoo::striping.
1205 - \p opt::equal_to - key equality functor like \p std::equal_to.
1206 If this functor is defined then the probe-set will be unordered.
1207 If \p %opt::compare or \p %opt::less option is specified too, then the probe-set will be ordered
1208 and \p %opt::equal_to will be ignored.
1209 - \p opt::compare - key comparison functor. No default functor is provided.
1210 If the option is not specified, the \p %opt::less is used.
1211 If \p %opt::compare or \p %opt::less option is specified, then the probe-set will be ordered.
1212 - \p opt::less - specifies binary predicate used for key comparison. Default is \p std::less<T>.
1213 If \p %opt::compare or \p %opt::less option is specified, then the probe-set will be ordered.
1214 - \p opt::item_counter - the type of item counting feature. Default is \p atomicity::item_counter
1215 The item counter should be atomic.
1216 - \p opt::allocator - the allocator type using for allocating bucket tables.
1217 Default is \ref CDS_DEFAULT_ALLOCATOR
1218 - \p intrusive::opt::disposer - the disposer type used in \p clear() member function for
1219 freeing nodes. Default is \p intrusive::opt::v::empty_disposer
1220 - \p opt::stat - internal statistics. Possibly types: \p cuckoo::stat, \p cuckoo::empty_stat.
1221 Default is \p %cuckoo::empty_stat
1223 The probe set traits \p cuckoo::probeset_type and \p cuckoo::store_hash are taken from \p node type
1224 specified by \p opt::hook option.
1226 template <typename... Options>
1227 struct make_traits {
1228 typedef typename cds::opt::make_options<
1229 typename cds::opt::find_type_traits< cuckoo::traits, Options... >::type
1231 >::type type ; ///< Result of metafunction
1236 template <typename Node, typename Probeset>
1239 template <typename Node>
1240 class bucket_entry<Node, cuckoo::list>
1243 typedef Node node_type;
1244 typedef cuckoo::list_probeset_class probeset_class;
1245 typedef cuckoo::list probeset_type;
1255 friend class bucket_entry;
1261 iterator( node_type * p )
1264 iterator( iterator const& it)
1268 iterator& operator=( iterator const& it )
1274 iterator& operator=( node_type * p )
1280 node_type * operator->()
1284 node_type& operator*()
1286 assert( pNode != nullptr );
1291 iterator& operator ++()
1294 pNode = pNode->m_pNext;
1298 bool operator==(iterator const& it ) const
1300 return pNode == it.pNode;
1302 bool operator!=(iterator const& it ) const
1304 return !( *this == it );
1313 static_assert(( std::is_same<typename node_type::probeset_type, probeset_type>::value ), "Incompatible node type" );
1318 return iterator(pHead);
1325 void insert_after( iterator it, node_type * p )
1327 node_type * pPrev = it.pNode;
1329 p->m_pNext = pPrev->m_pNext;
1340 void remove( iterator itPrev, iterator itWhat )
1342 node_type * pPrev = itPrev.pNode;
1343 node_type * pWhat = itWhat.pNode;
1344 assert( (!pPrev && pWhat == pHead) || (pPrev && pPrev->m_pNext == pWhat));
1347 pPrev->m_pNext = pWhat->m_pNext;
1349 assert( pWhat == pHead );
1350 pHead = pHead->m_pNext;
1359 for ( node_type * pNode = pHead; pNode; pNode = pNext ) {
1360 pNext = pNode->m_pNext;
1368 template <typename Disposer>
1369 void clear( Disposer disp )
1372 for ( node_type * pNode = pHead; pNode; pNode = pNext ) {
1373 pNext = pNode->m_pNext;
1382 unsigned int size() const
1388 template <typename Node, unsigned int Capacity>
1389 class bucket_entry<Node, cuckoo::vector<Capacity>>
1392 typedef Node node_type;
1393 typedef cuckoo::vector_probeset_class probeset_class;
1394 typedef cuckoo::vector<Capacity> probeset_type;
1396 static unsigned int const c_nCapacity = probeset_type::c_nCapacity;
1399 node_type * m_arrNode[c_nCapacity];
1400 unsigned int m_nSize;
1402 void shift_up( unsigned int nFrom )
1404 assert( m_nSize < c_nCapacity );
1406 if ( nFrom < m_nSize )
1407 std::copy_backward( m_arrNode + nFrom, m_arrNode + m_nSize, m_arrNode + m_nSize + 1 );
1410 void shift_down( node_type ** pFrom )
1412 assert( m_arrNode <= pFrom && pFrom < m_arrNode + m_nSize);
1413 std::copy( pFrom + 1, m_arrNode + m_nSize, pFrom );
1419 friend class bucket_entry;
1425 iterator( node_type ** p )
1428 iterator( iterator const& it)
1432 iterator& operator=( iterator const& it )
1438 node_type * operator->()
1440 assert( pArr != nullptr );
1443 node_type& operator*()
1445 assert( pArr != nullptr );
1446 assert( *pArr != nullptr );
1451 iterator& operator ++()
1457 bool operator==(iterator const& it ) const
1459 return pArr == it.pArr;
1461 bool operator!=(iterator const& it ) const
1463 return !( *this == it );
1471 memset( m_arrNode, 0, sizeof(m_arrNode));
1472 static_assert(( std::is_same<typename node_type::probeset_type, probeset_type>::value ), "Incompatible node type" );
1477 return iterator(m_arrNode);
1481 return iterator(m_arrNode + size());
1484 void insert_after( iterator it, node_type * p )
1486 assert( m_nSize < c_nCapacity );
1487 assert( !it.pArr || (m_arrNode <= it.pArr && it.pArr <= m_arrNode + m_nSize));
1490 shift_up( static_cast<unsigned int>(it.pArr - m_arrNode) + 1 );
1500 void remove( iterator /*itPrev*/, iterator itWhat )
1503 shift_down( itWhat.pArr );
1512 template <typename Disposer>
1513 void clear( Disposer disp )
1515 for ( unsigned int i = 0; i < m_nSize; ++i ) {
1516 disp( m_arrNode[i] );
1521 unsigned int size() const
1527 template <typename Node, unsigned int ArraySize>
1529 static void store( Node * pNode, size_t * pHashes )
1531 memcpy( pNode->m_arrHash, pHashes, sizeof(pHashes[0]) * ArraySize );
1533 static bool equal_to( Node& node, unsigned int nTable, size_t nHash )
1535 return node.m_arrHash[nTable] == nHash;
1538 template <typename Node>
1539 struct hash_ops<Node, 0>
1541 static void store( Node * /*pNode*/, size_t * /*pHashes*/ )
1543 static bool equal_to( Node& /*node*/, unsigned int /*nTable*/, size_t /*nHash*/ )
1549 template <typename NodeTraits, bool Ordered>
1552 template <typename NodeTraits>
1553 struct contains<NodeTraits, true>
1555 template <typename BucketEntry, typename Position, typename Q, typename Compare>
1556 static bool find( BucketEntry& probeset, Position& pos, unsigned int /*nTable*/, size_t /*nHash*/, Q const& val, Compare cmp )
1559 typedef typename BucketEntry::iterator bucket_iterator;
1561 bucket_iterator itPrev;
1563 for ( bucket_iterator it = probeset.begin(), itEnd = probeset.end(); it != itEnd; ++it ) {
1564 int cmpRes = cmp( *NodeTraits::to_value_ptr(*it), val );
1565 if ( cmpRes >= 0 ) {
1567 pos.itPrev = itPrev;
1574 pos.itPrev = itPrev;
1575 pos.itFound = probeset.end();
1580 template <typename NodeTraits>
1581 struct contains<NodeTraits, false>
1583 template <typename BucketEntry, typename Position, typename Q, typename EqualTo>
1584 static bool find( BucketEntry& probeset, Position& pos, unsigned int nTable, size_t nHash, Q const& val, EqualTo eq )
1586 // Unordered version
1587 typedef typename BucketEntry::iterator bucket_iterator;
1588 typedef typename BucketEntry::node_type node_type;
1590 bucket_iterator itPrev;
1592 for ( bucket_iterator it = probeset.begin(), itEnd = probeset.end(); it != itEnd; ++it ) {
1593 if ( hash_ops<node_type, node_type::hash_array_size>::equal_to( *it, nTable, nHash ) && eq( *NodeTraits::to_value_ptr(*it), val )) {
1595 pos.itPrev = itPrev;
1601 pos.itPrev = itPrev;
1602 pos.itFound = probeset.end();
1607 } // namespace details
1610 } // namespace cuckoo
1613 /** @ingroup cds_intrusive_map
1616 - [2007] M.Herlihy, N.Shavit, M.Tzafrir "Concurrent Cuckoo Hashing. Technical report"
1617 - [2008] Maurice Herlihy, Nir Shavit "The Art of Multiprocessor Programming"
1619 <b>About Cuckoo hashing</b>
1621 [From <i>"The Art of Multiprocessor Programming"</i>]
1622 <a href="https://en.wikipedia.org/wiki/Cuckoo_hashing">Cuckoo hashing</a> is a hashing algorithm in which a newly added item displaces any earlier item
1623 occupying the same slot. For brevity, a table is a k-entry array of items. For a hash set of size
1624 N = 2k we use a two-entry array of tables, and two independent hash functions,
1625 <tt> h0, h1: KeyRange -> 0,...,k-1</tt>
1626 mapping the set of possible keys to entries in he array. To test whether a value \p x is in the set,
1627 <tt>find(x)</tt> tests whether either <tt>table[0][h0(x)]</tt> or <tt>table[1][h1(x)]</tt> is
1628 equal to \p x. Similarly, <tt>erase(x)</tt>checks whether \p x is in either <tt>table[0][h0(x)]</tt>
1629 or <tt>table[1][h1(x)]</tt>, ad removes it if found.
1631 The <tt>insert(x)</tt> successively "kicks out" conflicting items until every key has a slot.
1632 To add \p x, the method swaps \p x with \p y, the current occupant of <tt>table[0][h0(x)]</tt>.
1633 If the prior value was \p nullptr, it is done. Otherwise, it swaps the newly nest-less value \p y
1634 for the current occupant of <tt>table[1][h1(y)]</tt> in the same way. As before, if the prior value
1635 was \p nullptr, it is done. Otherwise, the method continues swapping entries (alternating tables)
1636 until it finds an empty slot. We might not find an empty slot, either because the table is full,
1637 or because the sequence of displacement forms a cycle. We therefore need an upper limit on the
1638 number of successive displacements we are willing to undertake. When this limit is exceeded,
1639 we resize the hash table, choose new hash functions and start over.
1641 For concurrent cuckoo hashing, rather than organizing the set as a two-dimensional table of
1642 items, we use two-dimensional table of probe sets, where a probe set is a constant-sized set
1643 of items with the same hash code. Each probe set holds at most \p PROBE_SIZE items, but the algorithm
1644 tries to ensure that when the set is quiescent (i.e no method call in progress) each probe set
1645 holds no more than <tt>THRESHOLD < PROBE_SET</tt> items. While method calls are in-flight, a probe
1646 set may temporarily hold more than \p THRESHOLD but never more than \p PROBE_SET items.
1648 In current implementation, a probe set can be defined either as a (single-linked) list
1649 or as a fixed-sized vector, optionally ordered.
1651 In description above two-table cuckoo hashing (<tt>k = 2</tt>) has been considered.
1652 We can generalize this approach for <tt>k >= 2</tt> when we have \p k hash functions
1653 <tt>h[0], ... h[k-1]</tt> and \p k tables <tt>table[0], ... table[k-1]</tt>.
1655 The search in probe set is linear, the complexity is <tt> O(PROBE_SET) </tt>.
1656 The probe set may be ordered or not. Ordered probe set can be more efficient since
1657 the average search complexity is <tt>O(PROBE_SET/2)</tt>.
1658 However, the overhead of sorting can eliminate a gain of ordered search.
1660 The probe set is ordered if \p compare or \p less is specified in \p Traits template
1661 parameter. Otherwise, the probe set is unordered and \p Traits should provide
1662 \p equal_to predicate.
1664 The \p cds::intrusive::cuckoo namespace contains \p %CuckooSet-related declarations.
1667 - \p T - the type stored in the set. The type must be based on \p cuckoo::node (for \p cuckoo::base_hook)
1668 or it must have a member of type %cuckoo::node (for \p cuckoo::member_hook),
1669 or it must be convertible to \p %cuckoo::node (for \p cuckoo::traits_hook)
1670 - \p Traits - type traits, default is \p cuckoo::traits. It is possible to declare option-based
1671 set with \p cuckoo::make_traits metafunction result as \p Traits template argument.
1675 You should incorporate \p cuckoo::node into your struct \p T and provide
1676 appropriate \p cuckoo::traits::hook in your \p Traits template parameters.
1677 Usually, for \p Traits you define a struct based on \p cuckoo::traits.
1679 Example for base hook and list-based probe-set:
1681 #include <cds/intrusive/cuckoo_set.h>
1683 // Data stored in cuckoo set
1684 // We use list as probe-set container and store hash values in the node
1685 // (since we use two hash functions we should store 2 hash values per node)
1686 struct my_data: public cds::intrusive::cuckoo::node< cds::intrusive::cuckoo::list, 2 >
1695 // Provide equal_to functor for my_data since we will use unordered probe-set
1696 struct my_data_equal_to {
1697 bool operator()( const my_data& d1, const my_data& d2 ) const
1699 return d1.strKey.compare( d2.strKey ) == 0;
1702 bool operator()( const my_data& d, const std::string& s ) const
1704 return d.strKey.compare(s) == 0;
1707 bool operator()( const std::string& s, const my_data& d ) const
1709 return s.compare( d.strKey ) == 0;
1713 // Provide two hash functor for my_data
1715 size_t operator()(std::string const& s) const
1717 return cds::opt::v::hash<std::string>( s );
1719 size_t operator()( my_data const& d ) const
1721 return (*this)( d.strKey );
1725 struct hash2: private hash1 {
1726 size_t operator()(std::string const& s) const
1728 size_t h = ~( hash1::operator()(s));
1729 return ~h + 0x9e3779b9 + (h << 6) + (h >> 2);
1731 size_t operator()( my_data const& d ) const
1733 return (*this)( d.strKey );
1737 // Declare type traits
1738 struct my_traits: public cds::intrusive::cuckoo::traits
1740 typedef cds::intrusive::cuckoo::base_hook<
1741 cds::intrusive::cuckoo::probeset_type< my_data::probeset_type >
1742 ,cds::intrusive::cuckoo::store_hash< my_data::hash_array_size >
1744 typedef my_data_equa_to equal_to;
1745 typedef cds::opt::hash_tuple< hash1, hash2 > hash;
1748 // Declare CuckooSet type
1749 typedef cds::intrusive::CuckooSet< my_data, my_traits > my_cuckoo_set;
1751 // Equal option-based declaration
1752 typedef cds::intrusive::CuckooSet< my_data,
1753 cds::intrusive::cuckoo::make_traits<
1754 cds::intrusive::opt::hook< cds::intrusive::cuckoo::base_hook<
1755 cds::intrusive::cuckoo::probeset_type< my_data::probeset_type >
1756 ,cds::intrusive::cuckoo::store_hash< my_data::hash_array_size >
1758 ,cds::opt::hash< std::tuple< hash1, hash2 > >
1759 ,cds::opt::equal_to< my_data_equal_to >
1764 If we provide \p compare function instead of \p equal_to for \p my_data
1765 we get as a result a cuckoo set with ordered probe set that may improve
1767 Example for base hook and ordered vector-based probe-set:
1770 #include <cds/intrusive/cuckoo_set.h>
1772 // Data stored in cuckoo set
1773 // We use a vector of capacity 4 as probe-set container and store hash values in the node
1774 // (since we use two hash functions we should store 2 hash values per node)
1775 struct my_data: public cds::intrusive::cuckoo::node< cds::intrusive::cuckoo::vector<4>, 2 >
1784 // Provide compare functor for my_data since we want to use ordered probe-set
1785 struct my_data_compare {
1786 int operator()( const my_data& d1, const my_data& d2 ) const
1788 return d1.strKey.compare( d2.strKey );
1791 int operator()( const my_data& d, const std::string& s ) const
1793 return d.strKey.compare(s);
1796 int operator()( const std::string& s, const my_data& d ) const
1798 return s.compare( d.strKey );
1802 // Provide two hash functor for my_data
1804 size_t operator()(std::string const& s) const
1806 return cds::opt::v::hash<std::string>( s );
1808 size_t operator()( my_data const& d ) const
1810 return (*this)( d.strKey );
1814 struct hash2: private hash1 {
1815 size_t operator()(std::string const& s) const
1817 size_t h = ~( hash1::operator()(s));
1818 return ~h + 0x9e3779b9 + (h << 6) + (h >> 2);
1820 size_t operator()( my_data const& d ) const
1822 return (*this)( d.strKey );
1826 // Declare type traits
1827 struct my_traits: public cds::intrusive::cuckoo::traits
1829 typedef cds::intrusive::cuckoo::base_hook<
1830 cds::intrusive::cuckoo::probeset_type< my_data::probeset_type >
1831 ,cds::intrusive::cuckoo::store_hash< my_data::hash_array_size >
1833 typedef my_data_compare compare;
1834 typedef cds::opt::hash_tuple< hash1, hash2 > hash;
1837 // Declare CuckooSet type
1838 typedef cds::intrusive::CuckooSet< my_data, my_traits > my_cuckoo_set;
1840 // Equal option-based declaration
1841 typedef cds::intrusive::CuckooSet< my_data,
1842 cds::intrusive::cuckoo::make_traits<
1843 cds::intrusive::opt::hook< cds::intrusive::cuckoo::base_hook<
1844 cds::intrusive::cuckoo::probeset_type< my_data::probeset_type >
1845 ,cds::intrusive::cuckoo::store_hash< my_data::hash_array_size >
1847 ,cds::opt::hash< std::tuple< hash1, hash2 > >
1848 ,cds::opt::compare< my_data_compare >
1854 template <typename T, typename Traits = cuckoo::traits>
1858 typedef T value_type; ///< The value type stored in the set
1859 typedef Traits traits; ///< Set traits
1861 typedef typename traits::hook hook; ///< hook type
1862 typedef typename hook::node_type node_type; ///< node type
1863 typedef typename get_node_traits< value_type, node_type, hook>::type node_traits; ///< node traits
1865 typedef typename traits::hash hash; ///< hash functor tuple wrapped for internal use
1866 typedef typename hash::hash_tuple_type hash_tuple_type; ///< Type of hash tuple
1868 typedef typename traits::stat stat; ///< internal statistics type
1870 typedef typename traits::mutex_policy original_mutex_policy; ///< Concurrent access policy, see \p cuckoo::traits::mutex_policy
1873 typedef typename original_mutex_policy::template rebind_statistics<
1874 typename std::conditional<
1875 std::is_same< stat, cuckoo::empty_stat >::value
1876 ,typename original_mutex_policy::empty_stat
1877 ,typename original_mutex_policy::real_stat
1879 >::other mutex_policy;
1882 /// Probe set should be ordered or not
1884 If \p Traits specifies \p cmpare or \p less functor then the set is ordered.
1885 Otherwise, it is unordered and \p Traits should provide \p equal_to functor.
1887 static bool const c_isSorted = !( std::is_same< typename traits::compare, opt::none >::value
1888 && std::is_same< typename traits::less, opt::none >::value );
1889 static size_t const c_nArity = hash::size ; ///< the arity of cuckoo hashing: the number of hash functors provided; minimum 2.
1891 /// Key equality functor; used only for unordered probe-set
1892 typedef typename opt::details::make_equal_to< value_type, traits, !c_isSorted>::type key_equal_to;
1894 /// key comparing functor based on \p opt::compare and \p opt::less option setter. Used only for ordered probe set
1895 typedef typename opt::details::make_comparator< value_type, traits >::type key_comparator;
1898 typedef typename traits::allocator allocator;
1900 /// item counter type
1901 typedef typename traits::item_counter item_counter;
1904 typedef typename traits::disposer disposer;
1908 typedef typename node_type::probeset_class probeset_class;
1909 typedef typename node_type::probeset_type probeset_type;
1910 static unsigned int const c_nNodeHashArraySize = node_type::hash_array_size;
1912 typedef typename mutex_policy::scoped_cell_lock scoped_cell_lock;
1913 typedef typename mutex_policy::scoped_cell_trylock scoped_cell_trylock;
1914 typedef typename mutex_policy::scoped_full_lock scoped_full_lock;
1915 typedef typename mutex_policy::scoped_resize_lock scoped_resize_lock;
1917 typedef cuckoo::details::bucket_entry< node_type, probeset_type > bucket_entry;
1918 typedef typename bucket_entry::iterator bucket_iterator;
1919 typedef cds::details::Allocator< bucket_entry, allocator > bucket_table_allocator;
1921 typedef size_t hash_array[c_nArity] ; ///< hash array
1924 bucket_iterator itPrev;
1925 bucket_iterator itFound;
1928 typedef cuckoo::details::contains< node_traits, c_isSorted > contains_action;
1930 template <typename Predicate>
1931 struct predicate_wrapper {
1932 typedef typename std::conditional< c_isSorted, cds::opt::details::make_comparator_from_less<Predicate>, Predicate>::type type;
1935 typedef typename std::conditional< c_isSorted, key_comparator, key_equal_to >::type key_predicate;
1939 static unsigned int const c_nDefaultProbesetSize = 4; ///< default probeset size
1940 static size_t const c_nDefaultInitialSize = 16; ///< default initial size
1941 static unsigned int const c_nRelocateLimit = c_nArity * 2 - 1; ///< Count of attempts to relocate before giving up
1944 bucket_entry * m_BucketTable[ c_nArity ] ; ///< Bucket tables
1946 atomics::atomic<size_t> m_nBucketMask ; ///< Hash bitmask; bucket table size minus 1.
1947 unsigned int const m_nProbesetSize ; ///< Probe set size
1948 unsigned int const m_nProbesetThreshold ; ///< Probe set threshold
1950 hash m_Hash ; ///< Hash functor tuple
1951 mutex_policy m_MutexPolicy ; ///< concurrent access policy
1952 item_counter m_ItemCounter ; ///< item counter
1953 mutable stat m_Stat ; ///< internal statistics
1957 static void check_common_constraints()
1959 static_assert( (c_nArity == mutex_policy::c_nArity), "The count of hash functors must be equal to mutex_policy arity" );
1962 void check_probeset_properties() const
1964 assert( m_nProbesetThreshold < m_nProbesetSize );
1966 // if probe set type is cuckoo::vector<N> then m_nProbesetSize == N
1967 assert( node_type::probeset_size == 0 || node_type::probeset_size == m_nProbesetSize );
1970 template <typename Q>
1971 void hashing( size_t * pHashes, Q const& v ) const
1973 m_Hash( pHashes, v );
1976 void copy_hash( size_t * pHashes, value_type const& v ) const
1978 if ( c_nNodeHashArraySize )
1979 memcpy( pHashes, node_traits::to_node_ptr( v )->get_hash(), sizeof(pHashes[0]) * c_nNodeHashArraySize );
1981 hashing( pHashes, v );
1984 bucket_entry& bucket( unsigned int nTable, size_t nHash )
1986 assert( nTable < c_nArity );
1987 return m_BucketTable[nTable][nHash & m_nBucketMask.load( atomics::memory_order_relaxed ) ];
1990 static void store_hash( node_type * pNode, size_t * pHashes )
1992 cuckoo::details::hash_ops< node_type, c_nNodeHashArraySize >::store( pNode, pHashes );
1995 static bool equal_hash( node_type& node, unsigned int nTable, size_t nHash )
1997 return cuckoo::details::hash_ops< node_type, c_nNodeHashArraySize >::equal_to( node, nTable, nHash );
2000 void allocate_bucket_tables( size_t nSize )
2002 assert( cds::beans::is_power2( nSize ));
2004 m_nBucketMask.store( nSize - 1, atomics::memory_order_release );
2005 bucket_table_allocator alloc;
2006 for ( unsigned int i = 0; i < c_nArity; ++i )
2007 m_BucketTable[i] = alloc.NewArray( nSize );
2010 static void free_bucket_tables( bucket_entry ** pTable, size_t nCapacity )
2012 bucket_table_allocator alloc;
2013 for ( unsigned int i = 0; i < c_nArity; ++i ) {
2014 alloc.Delete( pTable[i], nCapacity );
2015 pTable[i] = nullptr;
2018 void free_bucket_tables()
2020 free_bucket_tables( m_BucketTable, m_nBucketMask.load( atomics::memory_order_relaxed ) + 1 );
2023 static CDS_CONSTEXPR unsigned int const c_nUndefTable = (unsigned int) -1;
2024 template <typename Q, typename Predicate >
2025 unsigned int contains( position * arrPos, size_t * arrHash, Q const& val, Predicate pred )
2027 // Buckets must be locked
2029 for ( unsigned int i = 0; i < c_nArity; ++i ) {
2030 bucket_entry& probeset = bucket( i, arrHash[i] );
2031 if ( contains_action::find( probeset, arrPos[i], i, arrHash[i], val, pred ))
2034 return c_nUndefTable;
2037 template <typename Q, typename Predicate, typename Func>
2038 value_type * erase_( Q const& val, Predicate pred, Func f )
2041 hashing( arrHash, val );
2042 position arrPos[ c_nArity ];
2045 scoped_cell_lock guard( m_MutexPolicy, arrHash );
2047 unsigned int nTable = contains( arrPos, arrHash, val, pred );
2048 if ( nTable != c_nUndefTable ) {
2049 node_type& node = *arrPos[nTable].itFound;
2050 f( *node_traits::to_value_ptr(node));
2051 bucket( nTable, arrHash[nTable]).remove( arrPos[nTable].itPrev, arrPos[nTable].itFound );
2053 m_Stat.onEraseSuccess();
2054 return node_traits::to_value_ptr( node );
2058 m_Stat.onEraseFailed();
2062 template <typename Q, typename Predicate, typename Func>
2063 bool find_( Q& val, Predicate pred, Func f )
2066 position arrPos[ c_nArity ];
2067 hashing( arrHash, val );
2068 scoped_cell_lock sl( m_MutexPolicy, arrHash );
2070 unsigned int nTable = contains( arrPos, arrHash, val, pred );
2071 if ( nTable != c_nUndefTable ) {
2072 f( *node_traits::to_value_ptr( *arrPos[nTable].itFound ), val );
2073 m_Stat.onFindSuccess();
2077 m_Stat.onFindFailed();
2081 bool relocate( unsigned int nTable, size_t * arrGoalHash )
2083 // arrGoalHash contains hash values for relocating element
2084 // Relocating element is first one from bucket( nTable, arrGoalHash[nTable] ) probeset
2086 m_Stat.onRelocateCall();
2090 for ( unsigned int nRound = 0; nRound < c_nRelocateLimit; ++nRound ) {
2091 m_Stat.onRelocateRound();
2094 scoped_cell_lock guard( m_MutexPolicy, arrGoalHash );
2096 bucket_entry& refBucket = bucket( nTable, arrGoalHash[nTable] );
2097 if ( refBucket.size() < m_nProbesetThreshold ) {
2098 // probeset is not above the threshold
2099 m_Stat.onFalseRelocateRound();
2103 pVal = node_traits::to_value_ptr( *refBucket.begin());
2104 copy_hash( arrHash, *pVal );
2106 scoped_cell_trylock guard2( m_MutexPolicy, arrHash );
2107 if ( !guard2.locked())
2108 continue ; // try one more time
2110 refBucket.remove( typename bucket_entry::iterator(), refBucket.begin());
2112 unsigned int i = (nTable + 1) % c_nArity;
2114 // try insert into free probeset
2115 while ( i != nTable ) {
2116 bucket_entry& bkt = bucket( i, arrHash[i] );
2117 if ( bkt.size() < m_nProbesetThreshold ) {
2119 contains_action::find( bkt, pos, i, arrHash[i], *pVal, key_predicate()) ; // must return false!
2120 bkt.insert_after( pos.itPrev, node_traits::to_node_ptr( pVal ));
2121 m_Stat.onSuccessRelocateRound();
2124 i = ( i + 1 ) % c_nArity;
2127 // try insert into partial probeset
2128 i = (nTable + 1) % c_nArity;
2129 while ( i != nTable ) {
2130 bucket_entry& bkt = bucket( i, arrHash[i] );
2131 if ( bkt.size() < m_nProbesetSize ) {
2133 contains_action::find( bkt, pos, i, arrHash[i], *pVal, key_predicate()) ; // must return false!
2134 bkt.insert_after( pos.itPrev, node_traits::to_node_ptr( pVal ));
2136 memcpy( arrGoalHash, arrHash, sizeof(arrHash));
2137 m_Stat.onRelocateAboveThresholdRound();
2138 goto next_iteration;
2140 i = (i + 1) % c_nArity;
2143 // all probeset is full, relocating fault
2144 refBucket.insert_after( typename bucket_entry::iterator(), node_traits::to_node_ptr( pVal ));
2145 m_Stat.onFailedRelocate();
2156 m_Stat.onResizeCall();
2158 size_t nOldCapacity = bucket_count( atomics::memory_order_acquire );
2159 bucket_entry * pOldTable[ c_nArity ];
2161 scoped_resize_lock guard( m_MutexPolicy );
2163 if ( nOldCapacity != bucket_count()) {
2164 m_Stat.onFalseResizeCall();
2168 size_t nCapacity = nOldCapacity * 2;
2170 m_MutexPolicy.resize( nCapacity );
2171 memcpy( pOldTable, m_BucketTable, sizeof(pOldTable));
2172 allocate_bucket_tables( nCapacity );
2175 position arrPos[ c_nArity ];
2177 for ( unsigned int nTable = 0; nTable < c_nArity; ++nTable ) {
2178 bucket_entry * pTable = pOldTable[nTable];
2179 for ( size_t k = 0; k < nOldCapacity; ++k ) {
2180 bucket_iterator itNext;
2181 for ( bucket_iterator it = pTable[k].begin(), itEnd = pTable[k].end(); it != itEnd; it = itNext ) {
2185 value_type& val = *node_traits::to_value_ptr( *it );
2186 copy_hash( arrHash, val );
2187 CDS_VERIFY_EQ( contains( arrPos, arrHash, val, key_predicate()), c_nUndefTable );
2189 for ( unsigned int i = 0; i < c_nArity; ++i ) {
2190 bucket_entry& refBucket = bucket( i, arrHash[i] );
2191 if ( refBucket.size() < m_nProbesetThreshold ) {
2192 refBucket.insert_after( arrPos[i].itPrev, &*it );
2193 m_Stat.onResizeSuccessMove();
2198 for ( unsigned int i = 0; i < c_nArity; ++i ) {
2199 bucket_entry& refBucket = bucket( i, arrHash[i] );
2200 if ( refBucket.size() < m_nProbesetSize ) {
2201 refBucket.insert_after( arrPos[i].itPrev, &*it );
2202 assert( refBucket.size() > 1 );
2203 copy_hash( arrHash, *node_traits::to_value_ptr( *refBucket.begin()));
2204 m_Stat.onResizeRelocateCall();
2205 relocate( i, arrHash );
2214 free_bucket_tables( pOldTable, nOldCapacity );
2217 CDS_CONSTEXPR static unsigned int calc_probeset_size( unsigned int nProbesetSize ) CDS_NOEXCEPT
2219 return std::is_same< probeset_class, cuckoo::vector_probeset_class >::value
2220 ? node_type::probeset_size
2223 : ( node_type::probeset_size ? node_type::probeset_size : c_nDefaultProbesetSize ));
2228 /// Default constructor
2230 Initial size = \ref c_nDefaultInitialSize
2233 - \p c_nDefaultProbesetSize if \p probeset_type is \p cuckoo::list
2234 - \p Capacity if \p probeset_type is <tt> cuckoo::vector<Capacity> </tt>
2236 Probe set threshold = probe set size - 1
2239 : m_nProbesetSize( calc_probeset_size(0))
2240 , m_nProbesetThreshold( m_nProbesetSize - 1 )
2241 , m_MutexPolicy( c_nDefaultInitialSize )
2243 check_common_constraints();
2244 check_probeset_properties();
2246 allocate_bucket_tables( c_nDefaultInitialSize );
2249 /// Constructs the set object with given probe set size and threshold
2251 If probe set type is <tt> cuckoo::vector<Capacity> </tt> vector
2252 then \p nProbesetSize is ignored since it should be equal to vector's \p Capacity.
2255 size_t nInitialSize ///< Initial set size; if 0 - use default initial size \p c_nDefaultInitialSize
2256 , unsigned int nProbesetSize ///< probe set size
2257 , unsigned int nProbesetThreshold = 0 ///< probe set threshold, <tt>nProbesetThreshold < nProbesetSize</tt>. If 0, <tt>nProbesetThreshold = nProbesetSize - 1</tt>
2259 : m_nProbesetSize( calc_probeset_size(nProbesetSize))
2260 , m_nProbesetThreshold( nProbesetThreshold ? nProbesetThreshold : m_nProbesetSize - 1 )
2261 , m_MutexPolicy( cds::beans::ceil2(nInitialSize ? nInitialSize : c_nDefaultInitialSize ))
2263 check_common_constraints();
2264 check_probeset_properties();
2266 allocate_bucket_tables( nInitialSize ? cds::beans::ceil2( nInitialSize ) : c_nDefaultInitialSize );
2269 /// Constructs the set object with given hash functor tuple
2271 The probe set size and threshold are set as default, see \p CuckooSet()
2274 hash_tuple_type const& h ///< hash functor tuple of type <tt>std::tuple<H1, H2, ... Hn></tt> where <tt> n == \ref c_nArity </tt>
2276 : m_nProbesetSize( calc_probeset_size(0))
2277 , m_nProbesetThreshold( m_nProbesetSize -1 )
2279 , m_MutexPolicy( c_nDefaultInitialSize )
2281 check_common_constraints();
2282 check_probeset_properties();
2284 allocate_bucket_tables( c_nDefaultInitialSize );
2287 /// Constructs the set object with given probe set properties and hash functor tuple
2289 If probe set type is <tt> cuckoo::vector<Capacity> </tt> vector
2290 then \p nProbesetSize should be equal to vector's \p Capacity.
2293 size_t nInitialSize ///< Initial set size; if 0 - use default initial size \p c_nDefaultInitialSize
2294 , unsigned int nProbesetSize ///< probe set size, positive integer
2295 , unsigned int nProbesetThreshold ///< probe set threshold, <tt>nProbesetThreshold < nProbesetSize</tt>. If 0, <tt>nProbesetThreshold = nProbesetSize - 1</tt>
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(nProbesetSize))
2299 , m_nProbesetThreshold( nProbesetThreshold ? nProbesetThreshold : m_nProbesetSize - 1)
2301 , m_MutexPolicy( cds::beans::ceil2(nInitialSize ? nInitialSize : c_nDefaultInitialSize ))
2303 check_common_constraints();
2304 check_probeset_properties();
2306 allocate_bucket_tables( nInitialSize ? cds::beans::ceil2( nInitialSize ) : c_nDefaultInitialSize );
2309 /// Constructs the set object with given hash functor tuple (move semantics)
2311 The probe set size and threshold are set as default, see \p CuckooSet()
2314 hash_tuple_type&& h ///< hash functor tuple of type <tt>std::tuple<H1, H2, ... Hn></tt> where <tt> n == \ref c_nArity </tt>
2316 : m_nProbesetSize( calc_probeset_size(0))
2317 , m_nProbesetThreshold( m_nProbesetSize / 2 )
2318 , m_Hash( std::forward<hash_tuple_type>(h))
2319 , m_MutexPolicy( c_nDefaultInitialSize )
2321 check_common_constraints();
2322 check_probeset_properties();
2324 allocate_bucket_tables( c_nDefaultInitialSize );
2327 /// Constructs the set object with given probe set properties and hash functor tuple (move semantics)
2329 If probe set type is <tt> cuckoo::vector<Capacity> </tt> vector
2330 then \p nProbesetSize should be equal to vector's \p Capacity.
2333 size_t nInitialSize ///< Initial set size; if 0 - use default initial size \p c_nDefaultInitialSize
2334 , unsigned int nProbesetSize ///< probe set size, positive integer
2335 , unsigned int nProbesetThreshold ///< probe set threshold, <tt>nProbesetThreshold < nProbesetSize</tt>. If 0, <tt>nProbesetThreshold = nProbesetSize - 1</tt>
2336 , hash_tuple_type&& h ///< hash functor tuple of type <tt>std::tuple<H1, H2, ... Hn></tt> where <tt> n == \ref c_nArity </tt>
2338 : m_nProbesetSize( calc_probeset_size(nProbesetSize))
2339 , m_nProbesetThreshold( nProbesetThreshold ? nProbesetThreshold : m_nProbesetSize - 1)
2340 , m_Hash( std::forward<hash_tuple_type>(h))
2341 , m_MutexPolicy( cds::beans::ceil2(nInitialSize ? nInitialSize : c_nDefaultInitialSize ))
2343 check_common_constraints();
2344 check_probeset_properties();
2346 allocate_bucket_tables( nInitialSize ? cds::beans::ceil2( nInitialSize ) : c_nDefaultInitialSize );
2352 free_bucket_tables();
2356 /// Inserts new node
2358 The function inserts \p val in the set if it does not contain an item with key equal to \p val.
2360 Returns \p true if \p val is inserted into the set, \p false otherwise.
2362 bool insert( value_type& val )
2364 return insert( val, []( value_type& ) {} );
2367 /// Inserts new node
2369 The function allows to split creating of new item into two part:
2370 - create item with key only
2371 - insert new item into the set
2372 - if inserting is success, calls \p f functor to initialize value-field of \p val.
2374 The functor signature is:
2376 void func( value_type& val );
2378 where \p val is the item inserted.
2380 The user-defined functor is called only if the inserting is success.
2382 template <typename Func>
2383 bool insert( value_type& val, Func f )
2386 position arrPos[ c_nArity ];
2387 unsigned int nGoalTable;
2389 hashing( arrHash, val );
2390 node_type * pNode = node_traits::to_node_ptr( val );
2391 store_hash( pNode, arrHash );
2395 scoped_cell_lock guard( m_MutexPolicy, arrHash );
2397 if ( contains( arrPos, arrHash, val, key_predicate()) != c_nUndefTable ) {
2398 m_Stat.onInsertFailed();
2402 for ( unsigned int i = 0; i < c_nArity; ++i ) {
2403 bucket_entry& refBucket = bucket( i, arrHash[i] );
2404 if ( refBucket.size() < m_nProbesetThreshold ) {
2405 refBucket.insert_after( arrPos[i].itPrev, pNode );
2408 m_Stat.onInsertSuccess();
2413 for ( unsigned int i = 0; i < c_nArity; ++i ) {
2414 bucket_entry& refBucket = bucket( i, arrHash[i] );
2415 if ( refBucket.size() < m_nProbesetSize ) {
2416 refBucket.insert_after( arrPos[i].itPrev, pNode );
2420 assert( refBucket.size() > 1 );
2421 copy_hash( arrHash, *node_traits::to_value_ptr( *refBucket.begin()));
2427 m_Stat.onInsertResize();
2432 m_Stat.onInsertRelocate();
2433 if ( !relocate( nGoalTable, arrHash )) {
2434 m_Stat.onInsertRelocateFault();
2435 m_Stat.onInsertResize();
2439 m_Stat.onInsertSuccess();
2443 /// Updates the node
2445 The operation performs inserting or changing data with lock-free manner.
2447 If the item \p val is not found in the set, then \p val is inserted into the set
2448 iff \p bAllowInsert is \p true.
2449 Otherwise, the functor \p func is called with item found.
2450 The functor \p func signature is:
2452 void func( bool bNew, value_type& item, value_type& val );
2455 - \p bNew - \p true if the item has been inserted, \p false otherwise
2456 - \p item - item of the set
2457 - \p val - argument \p val passed into the \p %update() function
2458 If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
2459 refer to the same thing.
2461 The functor may change non-key fields of the \p item.
2463 Returns std::pair<bool, bool> where \p first is \p true if operation is successful,
2464 i.e. the node has been inserted or updated,
2465 \p second is \p true if new item has been added or \p false if the item with \p key
2468 template <typename Func>
2469 std::pair<bool, bool> update( value_type& val, Func func, bool bAllowInsert = true )
2472 position arrPos[ c_nArity ];
2473 unsigned int nGoalTable;
2475 hashing( arrHash, val );
2476 node_type * pNode = node_traits::to_node_ptr( val );
2477 store_hash( pNode, arrHash );
2481 scoped_cell_lock guard( m_MutexPolicy, arrHash );
2483 unsigned int nTable = contains( arrPos, arrHash, val, key_predicate());
2484 if ( nTable != c_nUndefTable ) {
2485 func( false, *node_traits::to_value_ptr( *arrPos[nTable].itFound ), val );
2486 m_Stat.onUpdateExist();
2487 return std::make_pair( true, false );
2490 if ( !bAllowInsert )
2491 return std::make_pair( false, false );
2493 //node_type * pNode = node_traits::to_node_ptr( val );
2494 //store_hash( pNode, arrHash );
2496 for ( unsigned int i = 0; i < c_nArity; ++i ) {
2497 bucket_entry& refBucket = bucket( i, arrHash[i] );
2498 if ( refBucket.size() < m_nProbesetThreshold ) {
2499 refBucket.insert_after( arrPos[i].itPrev, pNode );
2500 func( true, val, val );
2502 m_Stat.onUpdateSuccess();
2503 return std::make_pair( true, true );
2507 for ( unsigned int i = 0; i < c_nArity; ++i ) {
2508 bucket_entry& refBucket = bucket( i, arrHash[i] );
2509 if ( refBucket.size() < m_nProbesetSize ) {
2510 refBucket.insert_after( arrPos[i].itPrev, pNode );
2511 func( true, val, val );
2514 assert( refBucket.size() > 1 );
2515 copy_hash( arrHash, *node_traits::to_value_ptr( *refBucket.begin()));
2521 m_Stat.onUpdateResize();
2526 m_Stat.onUpdateRelocate();
2527 if ( !relocate( nGoalTable, arrHash )) {
2528 m_Stat.onUpdateRelocateFault();
2529 m_Stat.onUpdateResize();
2533 m_Stat.onUpdateSuccess();
2534 return std::make_pair( true, true );
2537 template <typename Func>
2538 CDS_DEPRECATED("ensure() is deprecated, use update()")
2539 std::pair<bool, bool> ensure( value_type& val, Func func )
2541 return update( val, func, true );
2545 /// Unlink the item \p val from the set
2547 The function searches the item \p val in the set and unlink it
2548 if it is found and is equal to \p val (here, the equality means that
2549 \p val belongs to the set: if \p item is an item found then
2550 unlink is successful iif <tt>&val == &item</tt>)
2552 The function returns \p true if success and \p false otherwise.
2554 bool unlink( value_type& val )
2557 hashing( arrHash, val );
2558 position arrPos[ c_nArity ];
2561 scoped_cell_lock guard( m_MutexPolicy, arrHash );
2563 unsigned int nTable = contains( arrPos, arrHash, val, key_predicate());
2564 if ( nTable != c_nUndefTable && node_traits::to_value_ptr(*arrPos[nTable].itFound) == &val ) {
2565 bucket( nTable, arrHash[nTable]).remove( arrPos[nTable].itPrev, arrPos[nTable].itFound );
2567 m_Stat.onUnlinkSuccess();
2572 m_Stat.onUnlinkFailed();
2576 /// Deletes the item from the set
2577 /** \anchor cds_intrusive_CuckooSet_erase
2578 The function searches an item with key equal to \p val in the set,
2579 unlinks it from the set, and returns a pointer to unlinked item.
2581 If the item with key equal to \p val is not found the function return \p nullptr.
2583 Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
2585 template <typename Q>
2586 value_type * erase( Q const& val )
2588 return erase( val, [](value_type const&) {} );
2591 /// Deletes the item from the set using \p pred predicate for searching
2593 The function is an analog of \ref cds_intrusive_CuckooSet_erase "erase(Q const&)"
2594 but \p pred is used for key comparing.
2595 If cuckoo set is ordered, then \p Predicate should have the interface and semantics like \p std::less.
2596 If cuckoo set is unordered, then \p Predicate should have the interface and semantics like \p std::equal_to.
2597 \p Predicate must imply the same element order as the comparator used for building the set.
2599 template <typename Q, typename Predicate>
2600 value_type * erase_with( Q const& val, Predicate pred )
2603 return erase_( val, typename predicate_wrapper<Predicate>::type(), [](value_type const&) {} );
2606 /// Delete the item from the set
2607 /** \anchor cds_intrusive_CuckooSet_erase_func
2608 The function searches an item with key equal to \p val in the set,
2609 call \p f functor with item found, unlinks it from the set, and returns a pointer to unlinked item.
2611 The \p Func interface is
2614 void operator()( value_type const& item );
2618 If the item with key equal to \p val is not found the function return \p nullptr.
2620 Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
2622 template <typename Q, typename Func>
2623 value_type * erase( Q const& val, Func f )
2625 return erase_( val, key_predicate(), f );
2628 /// Deletes the item from the set using \p pred predicate for searching
2630 The function is an analog of \ref cds_intrusive_CuckooSet_erase_func "erase(Q const&, Func)"
2631 but \p pred is used for key comparing.
2632 If you use ordered cuckoo set, then \p Predicate should have the interface and semantics like \p std::less.
2633 If you use unordered cuckoo set, then \p Predicate should have the interface and semantics like \p std::equal_to.
2634 \p Predicate must imply the same element order as the comparator used for building the set.
2636 template <typename Q, typename Predicate, typename Func>
2637 value_type * erase_with( Q const& val, Predicate pred, Func f )
2640 return erase_( val, typename predicate_wrapper<Predicate>::type(), f );
2643 /// Find the key \p val
2644 /** \anchor cds_intrusive_CuckooSet_find_func
2645 The function searches the item with key equal to \p val and calls the functor \p f for item found.
2646 The interface of \p Func functor is:
2649 void operator()( value_type& item, Q& val );
2652 where \p item is the item found, \p val is the <tt>find</tt> function argument.
2654 The functor may change non-key fields of \p item.
2656 The \p val argument is non-const since it can be used as \p f functor destination i.e., the functor
2657 may modify both arguments.
2659 Note the hash functor specified for class \p Traits template parameter
2660 should accept a parameter of type \p Q that can be not the same as \p value_type.
2662 The function returns \p true if \p val is found, \p false otherwise.
2664 template <typename Q, typename Func>
2665 bool find( Q& val, Func f )
2667 return find_( val, key_predicate(), f );
2670 template <typename Q, typename Func>
2671 bool find( Q const& val, Func f )
2673 return find_( val, key_predicate(), f );
2677 /// Find the key \p val using \p pred predicate for comparing
2679 The function is an analog of \ref cds_intrusive_CuckooSet_find_func "find(Q&, Func)"
2680 but \p pred is used for key comparison.
2681 If you use ordered cuckoo set, then \p Predicate should have the interface and semantics like \p std::less.
2682 If you use unordered cuckoo set, then \p Predicate should have the interface and semantics like \p std::equal_to.
2683 \p pred must imply the same element order as the comparator used for building the set.
2685 template <typename Q, typename Predicate, typename Func>
2686 bool find_with( Q& val, Predicate pred, Func f )
2689 return find_( val, typename predicate_wrapper<Predicate>::type(), f );
2692 template <typename Q, typename Predicate, typename Func>
2693 bool find_with( Q const& val, Predicate pred, Func f )
2696 return find_( val, typename predicate_wrapper<Predicate>::type(), f );
2700 /// Checks whether the set contains \p key
2702 The function searches the item with key equal to \p key
2703 and returns \p true if it is found, and \p false otherwise.
2705 template <typename Q>
2706 bool contains( Q const& key )
2708 return find( key, [](value_type&, Q const& ) {} );
2711 template <typename Q>
2712 CDS_DEPRECATED("deprecated, use contains()")
2713 bool find( Q const& key )
2715 return contains( key );
2719 /// Checks whether the set contains \p key using \p pred predicate for searching
2721 The function is similar to <tt>contains( key )</tt> but \p pred is used for key comparing.
2722 If the set is unordered, \p Predicate has semantics like \p std::equal_to.
2723 For ordered set \p Predicate has \p std::less semantics. In that case \p pred
2724 must imply the same element order as the comparator used for building the set.
2726 template <typename Q, typename Predicate>
2727 bool contains( Q const& key, Predicate pred )
2730 return find_with( key, typename predicate_wrapper<Predicate>::type(), [](value_type& , Q const& ) {} );
2733 template <typename Q, typename Predicate>
2734 CDS_DEPRECATED("deprecated, use contains()")
2735 bool find_with( Q const& key, Predicate pred )
2737 return contains( key, pred );
2743 The function unlinks all items from the set.
2744 For any item \p Traits::disposer is called
2748 clear_and_dispose( disposer());
2751 /// Clears the set and calls \p disposer for each item
2753 The function unlinks all items from the set calling \p oDisposer for each item.
2754 \p Disposer functor interface is:
2757 void operator()( value_type * p );
2761 The \p Traits::disposer is not called.
2763 template <typename Disposer>
2764 void clear_and_dispose( Disposer oDisposer )
2766 // locks entire array
2767 scoped_full_lock sl( m_MutexPolicy );
2769 for ( unsigned int i = 0; i < c_nArity; ++i ) {
2770 bucket_entry * pEntry = m_BucketTable[i];
2771 bucket_entry * pEnd = pEntry + m_nBucketMask.load( atomics::memory_order_relaxed ) + 1;
2772 for ( ; pEntry != pEnd ; ++pEntry ) {
2773 pEntry->clear( [&oDisposer]( node_type * pNode ){ oDisposer( node_traits::to_value_ptr( pNode )) ; } );
2776 m_ItemCounter.reset();
2779 /// Checks if the set is empty
2781 Emptiness is checked by item counting: if item count is zero then the set is empty.
2788 /// Returns item count in the set
2791 return m_ItemCounter;
2794 /// Returns the size of hash table
2796 The hash table size is non-constant and can be increased via resizing.
2798 size_t bucket_count() const
2800 return m_nBucketMask.load( atomics::memory_order_relaxed ) + 1;
2803 size_t bucket_count( atomics::memory_order load_mo ) const
2805 return m_nBucketMask.load( load_mo ) + 1;
2809 /// Returns lock array size
2810 size_t lock_count() const
2812 return m_MutexPolicy.lock_count();
2815 /// Returns const reference to internal statistics
2816 stat const& statistics() const
2821 /// Returns const reference to mutex policy internal statistics
2822 typename mutex_policy::statistics_type const& mutex_policy_statistics() const
2824 return m_MutexPolicy.statistics();
2827 }} // namespace cds::intrusive
2829 #endif // #ifndef CDSLIB_INTRUSIVE_CUCKOO_SET_H