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 lock_array_allocator().Delete( pArr );
704 lock_array_ptr create_lock_array( size_t nCapacity )
706 return lock_array_ptr( lock_array_allocator().New( nCapacity ), lock_array_disposer());
709 void acquire( size_t const * arrHash, lock_array_ptr * pLockArr, lock_type ** parrLock )
711 owner_t me = (owner_t) cds::OS::get_current_thread_id();
719 scoped_spinlock sl(m_access);
720 for ( unsigned int i = 0; i < c_nArity; ++i )
721 pLockArr[i] = m_arrLocks[i];
722 cur_capacity = m_nCapacity.load( atomics::memory_order_acquire );
725 // wait while resizing
727 who = m_Owner.load( atomics::memory_order_acquire );
728 if ( !( who & 1 ) || (who >> 1) == (me & c_nOwnerMask))
731 m_Stat.onCellWaitResizing();
734 if ( cur_capacity == m_nCapacity.load( atomics::memory_order_acquire )) {
736 size_t const nMask = pLockArr[0]->size() - 1;
737 assert( cds::beans::is_power2( nMask + 1 ));
739 for ( unsigned int i = 0; i < c_nArity; ++i ) {
740 parrLock[i] = &( pLockArr[i]->at( arrHash[i] & nMask ));
744 who = m_Owner.load( atomics::memory_order_acquire );
745 if ( ( !(who & 1) || (who >> 1) == (me & c_nOwnerMask)) && cur_capacity == m_nCapacity.load( atomics::memory_order_acquire )) {
750 for ( unsigned int i = 0; i < c_nArity; ++i )
751 parrLock[i]->unlock();
753 m_Stat.onCellLockFailed();
756 m_Stat.onCellArrayChanged();
758 // clears pLockArr can lead to calling dtor for each item of pLockArr[i] that may be a heavy-weighted operation
759 // (each pLockArr[i] is a shared pointer to array of a ton of mutexes)
760 // It is better to do this before the next loop iteration where we will use spin-locked assignment to pLockArr
761 // However, destructing a lot of mutexes under spin-lock is a bad solution
762 for ( unsigned int i = 0; i < c_nArity; ++i )
767 bool try_second_acquire( size_t const * arrHash, lock_type ** parrLock )
769 // It is assumed that the current thread already has a lock
770 // and requires a second lock for other hash
772 size_t const nMask = m_nCapacity.load(atomics::memory_order_acquire) - 1;
773 size_t nCell = m_arrLocks[0]->try_lock( arrHash[0] & nMask);
774 if ( nCell == lock_array_type::c_nUnspecifiedCell ) {
775 m_Stat.onSecondCellLockFailed();
778 parrLock[0] = &(m_arrLocks[0]->at(nCell));
780 for ( unsigned int i = 1; i < c_nArity; ++i ) {
781 parrLock[i] = &( m_arrLocks[i]->at( m_arrLocks[i]->lock( arrHash[i] & nMask)));
784 m_Stat.onSecondCellLock();
790 owner_t me = (owner_t) cds::OS::get_current_thread_id();
795 if ( m_Owner.compare_exchange_strong( ownNull, (me << 1) | 1, atomics::memory_order_acq_rel, atomics::memory_order_relaxed )) {
796 m_arrLocks[0]->lock_all();
802 m_Stat.onFullLockIter();
808 m_arrLocks[0]->unlock_all();
809 m_Owner.store( 0, atomics::memory_order_release );
812 void acquire_resize( lock_array_ptr * pOldLocks )
814 owner_t me = (owner_t) cds::OS::get_current_thread_id();
819 scoped_spinlock sl(m_access);
820 for ( unsigned int i = 0; i < c_nArity; ++i )
821 pOldLocks[i] = m_arrLocks[i];
822 cur_capacity = m_nCapacity.load( atomics::memory_order_acquire );
827 if ( m_Owner.compare_exchange_strong( ownNull, (me << 1) | 1, atomics::memory_order_acq_rel, atomics::memory_order_relaxed )) {
828 if ( cur_capacity == m_nCapacity.load( atomics::memory_order_acquire )) {
829 pOldLocks[0]->lock_all();
830 m_Stat.onResizeLock();
834 m_Owner.store( 0, atomics::memory_order_release );
835 m_Stat.onResizeLockArrayChanged();
838 m_Stat.onResizeLockIter();
840 // clears pOldLocks can lead to calling dtor for each item of pOldLocks[i] that may be a heavy-weighted operation
841 // (each pOldLocks[i] is a shared pointer to array of a ton of mutexes)
842 // It is better to do this before the next loop iteration where we will use spin-locked assignment to pOldLocks
843 // However, destructing a lot of mutexes under spin-lock is a bad solution
844 for ( unsigned int i = 0; i < c_nArity; ++i )
845 pOldLocks[i].reset();
849 void release_resize( lock_array_ptr * pOldLocks )
851 m_Owner.store( 0, atomics::memory_order_release );
852 pOldLocks[0]->unlock_all();
858 class scoped_cell_lock {
859 lock_type * m_arrLock[ c_nArity ];
860 lock_array_ptr m_arrLockArr[ c_nArity ];
863 scoped_cell_lock( refinable& policy, size_t const* arrHash )
865 policy.acquire( arrHash, m_arrLockArr, m_arrLock );
870 for ( unsigned int i = 0; i < c_nArity; ++i )
871 m_arrLock[i]->unlock();
875 class scoped_cell_trylock {
876 lock_type * m_arrLock[ c_nArity ];
880 scoped_cell_trylock( refinable& policy, size_t const* arrHash )
882 m_bLocked = policy.try_second_acquire( arrHash, m_arrLock );
885 ~scoped_cell_trylock()
888 for ( unsigned int i = 0; i < c_nArity; ++i )
889 m_arrLock[i]->unlock();
899 class scoped_full_lock {
902 scoped_full_lock( refinable& policy )
905 policy.acquire_all();
909 m_policy.release_all();
913 class scoped_resize_lock
916 lock_array_ptr m_arrLocks[ c_nArity ];
918 scoped_resize_lock( refinable& policy )
921 policy.acquire_resize( m_arrLocks );
923 ~scoped_resize_lock()
925 m_policy.release_resize( m_arrLocks );
933 size_t nLockCount ///< The size of lock array. Must be power of two.
935 , m_nCapacity( nLockCount )
937 assert( cds::beans::is_power2( nLockCount ));
938 for ( unsigned int i = 0; i < c_nArity; ++i )
939 m_arrLocks[i] = create_lock_array( nLockCount );
943 void resize( size_t nCapacity )
945 lock_array_ptr pNew[ c_nArity ];
946 for ( unsigned int i = 0; i < c_nArity; ++i )
947 pNew[i] = create_lock_array( nCapacity );
950 scoped_spinlock sl(m_access);
951 m_nCapacity.store( nCapacity, atomics::memory_order_release );
952 for ( unsigned int i = 0; i < c_nArity; ++i )
953 m_arrLocks[i] = pNew[i];
960 /// Returns lock array size
962 Lock array size is not a constant for \p refinable policy and can be changed when the set is resized.
964 size_t lock_count() const
966 return m_nCapacity.load(atomics::memory_order_relaxed);
969 /// Returns the arity of \p refinable mutex policy
970 CDS_CONSTEXPR unsigned int arity() const CDS_NOEXCEPT
975 /// Returns internal statistics
976 statistics_type const& statistics() const
982 /// \p CuckooSet internal statistics
984 typedef cds::atomicity::event_counter counter_type ; ///< Counter type
986 counter_type m_nRelocateCallCount ; ///< Count of \p relocate() function call
987 counter_type m_nRelocateRoundCount ; ///< Count of attempts to relocate items
988 counter_type m_nFalseRelocateCount ; ///< Count of unneeded attempts of \p relocate call
989 counter_type m_nSuccessRelocateCount ; ///< Count of successful item relocating
990 counter_type m_nRelocateAboveThresholdCount; ///< Count of item relocating above probeset threshold
991 counter_type m_nFailedRelocateCount ; ///< Count of failed relocation attemp (when all probeset is full)
993 counter_type m_nResizeCallCount ; ///< Count of \p resize() function call
994 counter_type m_nFalseResizeCount ; ///< Count of false \p resize() function call (when other thread has been resized the set)
995 counter_type m_nResizeSuccessNodeMove; ///< Count of successful node moving when resizing
996 counter_type m_nResizeRelocateCall ; ///< Count of \p relocate() function call from \p resize function
998 counter_type m_nInsertSuccess ; ///< Count of successful \p insert() function call
999 counter_type m_nInsertFailed ; ///< Count of failed \p insert() function call
1000 counter_type m_nInsertResizeCount ; ///< Count of \p resize() function call from \p insert()
1001 counter_type m_nInsertRelocateCount ; ///< Count of \p relocate() function call from \p insert()
1002 counter_type m_nInsertRelocateFault ; ///< Count of failed \p relocate() function call from \p insert()
1004 counter_type m_nUpdateExistCount ; ///< Count of call \p update() function for existing node
1005 counter_type m_nUpdateSuccessCount ; ///< Count of successful \p insert() function call for new node
1006 counter_type m_nUpdateResizeCount ; ///< Count of \p resize() function call from \p update()
1007 counter_type m_nUpdateRelocateCount ; ///< Count of \p relocate() function call from \p update()
1008 counter_type m_nUpdateRelocateFault ; ///< Count of failed \p relocate() function call from \p update()
1010 counter_type m_nUnlinkSuccess ; ///< Count of success \p unlink() function call
1011 counter_type m_nUnlinkFailed ; ///< Count of failed \p unlink() function call
1013 counter_type m_nEraseSuccess ; ///< Count of success \p erase() function call
1014 counter_type m_nEraseFailed ; ///< Count of failed \p erase() function call
1016 counter_type m_nFindSuccess ; ///< Count of success \p find() function call
1017 counter_type m_nFindFailed ; ///< Count of failed \p find() function call
1019 counter_type m_nFindEqualSuccess ; ///< Count of success \p find_equal() function call
1020 counter_type m_nFindEqualFailed ; ///< Count of failed \p find_equal() function call
1022 counter_type m_nFindWithSuccess ; ///< Count of success \p find_with() function call
1023 counter_type m_nFindWithFailed ; ///< Count of failed \p find_with() function call
1026 void onRelocateCall() { ++m_nRelocateCallCount; }
1027 void onRelocateRound() { ++m_nRelocateRoundCount; }
1028 void onFalseRelocateRound() { ++m_nFalseRelocateCount; }
1029 void onSuccessRelocateRound(){ ++m_nSuccessRelocateCount; }
1030 void onRelocateAboveThresholdRound() { ++m_nRelocateAboveThresholdCount; }
1031 void onFailedRelocate() { ++m_nFailedRelocateCount; }
1033 void onResizeCall() { ++m_nResizeCallCount; }
1034 void onFalseResizeCall() { ++m_nFalseResizeCount; }
1035 void onResizeSuccessMove() { ++m_nResizeSuccessNodeMove; }
1036 void onResizeRelocateCall() { ++m_nResizeRelocateCall; }
1038 void onInsertSuccess() { ++m_nInsertSuccess; }
1039 void onInsertFailed() { ++m_nInsertFailed; }
1040 void onInsertResize() { ++m_nInsertResizeCount; }
1041 void onInsertRelocate() { ++m_nInsertRelocateCount; }
1042 void onInsertRelocateFault() { ++m_nInsertRelocateFault; }
1044 void onUpdateExist() { ++m_nUpdateExistCount; }
1045 void onUpdateSuccess() { ++m_nUpdateSuccessCount; }
1046 void onUpdateResize() { ++m_nUpdateResizeCount; }
1047 void onUpdateRelocate() { ++m_nUpdateRelocateCount; }
1048 void onUpdateRelocateFault() { ++m_nUpdateRelocateFault; }
1050 void onUnlinkSuccess() { ++m_nUnlinkSuccess; }
1051 void onUnlinkFailed() { ++m_nUnlinkFailed; }
1053 void onEraseSuccess() { ++m_nEraseSuccess; }
1054 void onEraseFailed() { ++m_nEraseFailed; }
1056 void onFindSuccess() { ++m_nFindSuccess; }
1057 void onFindFailed() { ++m_nFindFailed; }
1059 void onFindWithSuccess() { ++m_nFindWithSuccess; }
1060 void onFindWithFailed() { ++m_nFindWithFailed; }
1064 /// CuckooSet empty internal statistics
1067 void onRelocateCall() const {}
1068 void onRelocateRound() const {}
1069 void onFalseRelocateRound() const {}
1070 void onSuccessRelocateRound()const {}
1071 void onRelocateAboveThresholdRound() const {}
1072 void onFailedRelocate() const {}
1074 void onResizeCall() const {}
1075 void onFalseResizeCall() const {}
1076 void onResizeSuccessMove() const {}
1077 void onResizeRelocateCall() const {}
1079 void onInsertSuccess() const {}
1080 void onInsertFailed() const {}
1081 void onInsertResize() const {}
1082 void onInsertRelocate() const {}
1083 void onInsertRelocateFault() const {}
1085 void onUpdateExist() const {}
1086 void onUpdateSuccess() const {}
1087 void onUpdateResize() const {}
1088 void onUpdateRelocate() const {}
1089 void onUpdateRelocateFault() const {}
1091 void onUnlinkSuccess() const {}
1092 void onUnlinkFailed() const {}
1094 void onEraseSuccess() const {}
1095 void onEraseFailed() const {}
1097 void onFindSuccess() const {}
1098 void onFindFailed() const {}
1100 void onFindWithSuccess() const {}
1101 void onFindWithFailed() const {}
1105 /// Type traits for CuckooSet class
1110 Possible values are: cuckoo::base_hook, cuckoo::member_hook, cuckoo::traits_hook.
1112 typedef base_hook<> hook;
1114 /// Hash functors tuple
1116 This is mandatory type and has no predefined one.
1118 At least, two hash functors should be provided. All hash functor
1119 should be orthogonal (different): for each <tt> i,j: i != j => h[i](x) != h[j](x) </tt>.
1120 The hash functors are defined as <tt> std::tuple< H1, H2, ... Hn > </tt>:
1121 \@code cds::opt::hash< std::tuple< h1, h2 > > \@endcode
1122 The number of hash functors specifies the number \p k - the count of hash tables in cuckoo hashing.
1124 To specify hash tuple in traits you should use \p cds::opt::hash_tuple:
1126 struct my_traits: public cds::intrusive::cuckoo::traits {
1127 typedef cds::opt::hash_tuple< hash1, hash2 > hash;
1131 typedef cds::opt::none hash;
1133 /// Concurrent access policy
1135 Available opt::mutex_policy types:
1136 - \p cuckoo::striping - simple, but the lock array is not resizable
1137 - \p cuckoo::refinable - resizable lock array, but more complex access to set data.
1139 Default is \p cuckoo::striping.
1141 typedef cuckoo::striping<> mutex_policy;
1143 /// Key equality functor
1145 Default is <tt>std::equal_to<T></tt>
1147 typedef opt::none equal_to;
1149 /// Key comparing functor
1151 No default functor is provided. If the option is not specified, the \p less is used.
1153 typedef opt::none compare;
1155 /// specifies binary predicate used for key comparison.
1157 Default is \p std::less<T>.
1159 typedef opt::none less;
1163 The type for item counting feature.
1164 Default is \p cds::atomicity::item_counter
1166 Only atomic item counter type is allowed.
1168 typedef atomicity::item_counter item_counter;
1172 The allocator type for allocating bucket tables.
1174 typedef CDS_DEFAULT_ALLOCATOR allocator;
1178 The disposer functor is used in \p CuckooSet::clear() member function
1181 typedef intrusive::opt::v::empty_disposer disposer;
1183 /// Internal statistics. Available statistics: \p cuckoo::stat, \p cuckoo::empty_stat
1184 typedef empty_stat stat;
1187 /// Metafunction converting option list to \p CuckooSet traits
1189 Template argument list \p Options... are:
1190 - \p intrusive::opt::hook - hook used. Possible values are: \p cuckoo::base_hook, \p cuckoo::member_hook,
1191 \p cuckoo::traits_hook.
1192 If the option is not specified, <tt>%cuckoo::base_hook<></tt> is used.
1193 - \p opt::hash - hash functor tuple, mandatory option. At least, two hash functors should be provided. All hash functor
1194 should be orthogonal (different): for each <tt> i,j: i != j => h[i](x) != h[j](x) </tt>.
1195 The hash functors are passed as <tt> std::tuple< H1, H2, ... Hn > </tt>. The number of hash functors specifies
1196 the number \p k - the count of hash tables in cuckoo hashing.
1197 - \p opt::mutex_policy - concurrent access policy.
1198 Available policies: \p cuckoo::striping, \p cuckoo::refinable.
1199 Default is \p %cuckoo::striping.
1200 - \p opt::equal_to - key equality functor like \p std::equal_to.
1201 If this functor is defined then the probe-set will be unordered.
1202 If \p %opt::compare or \p %opt::less option is specified too, then the probe-set will be ordered
1203 and \p %opt::equal_to will be ignored.
1204 - \p opt::compare - key comparison functor. No default functor is provided.
1205 If the option is not specified, the \p %opt::less is used.
1206 If \p %opt::compare or \p %opt::less option is specified, then the probe-set will be ordered.
1207 - \p opt::less - specifies binary predicate used for key comparison. Default is \p std::less<T>.
1208 If \p %opt::compare or \p %opt::less option is specified, then the probe-set will be ordered.
1209 - \p opt::item_counter - the type of item counting feature. Default is \p atomicity::item_counter
1210 The item counter should be atomic.
1211 - \p opt::allocator - the allocator type using for allocating bucket tables.
1212 Default is \ref CDS_DEFAULT_ALLOCATOR
1213 - \p intrusive::opt::disposer - the disposer type used in \p clear() member function for
1214 freeing nodes. Default is \p intrusive::opt::v::empty_disposer
1215 - \p opt::stat - internal statistics. Possibly types: \p cuckoo::stat, \p cuckoo::empty_stat.
1216 Default is \p %cuckoo::empty_stat
1218 The probe set traits \p cuckoo::probeset_type and \p cuckoo::store_hash are taken from \p node type
1219 specified by \p opt::hook option.
1221 template <typename... Options>
1222 struct make_traits {
1223 typedef typename cds::opt::make_options<
1224 typename cds::opt::find_type_traits< cuckoo::traits, Options... >::type
1226 >::type type ; ///< Result of metafunction
1231 template <typename Node, typename Probeset>
1234 template <typename Node>
1235 class bucket_entry<Node, cuckoo::list>
1238 typedef Node node_type;
1239 typedef cuckoo::list_probeset_class probeset_class;
1240 typedef cuckoo::list probeset_type;
1250 friend class bucket_entry;
1256 iterator( node_type * p )
1259 iterator( iterator const& it)
1263 iterator& operator=( iterator const& it )
1269 iterator& operator=( node_type * p )
1275 node_type * operator->()
1279 node_type& operator*()
1281 assert( pNode != nullptr );
1286 iterator& operator ++()
1289 pNode = pNode->m_pNext;
1293 bool operator==(iterator const& it ) const
1295 return pNode == it.pNode;
1297 bool operator!=(iterator const& it ) const
1299 return !( *this == it );
1308 static_assert(( std::is_same<typename node_type::probeset_type, probeset_type>::value ), "Incompatible node type" );
1313 return iterator(pHead);
1320 void insert_after( iterator it, node_type * p )
1322 node_type * pPrev = it.pNode;
1324 p->m_pNext = pPrev->m_pNext;
1335 void remove( iterator itPrev, iterator itWhat )
1337 node_type * pPrev = itPrev.pNode;
1338 node_type * pWhat = itWhat.pNode;
1339 assert( (!pPrev && pWhat == pHead) || (pPrev && pPrev->m_pNext == pWhat));
1342 pPrev->m_pNext = pWhat->m_pNext;
1344 assert( pWhat == pHead );
1345 pHead = pHead->m_pNext;
1354 for ( node_type * pNode = pHead; pNode; pNode = pNext ) {
1355 pNext = pNode->m_pNext;
1363 template <typename Disposer>
1364 void clear( Disposer disp )
1367 for ( node_type * pNode = pHead; pNode; pNode = pNext ) {
1368 pNext = pNode->m_pNext;
1377 unsigned int size() const
1383 template <typename Node, unsigned int Capacity>
1384 class bucket_entry<Node, cuckoo::vector<Capacity>>
1387 typedef Node node_type;
1388 typedef cuckoo::vector_probeset_class probeset_class;
1389 typedef cuckoo::vector<Capacity> probeset_type;
1391 static unsigned int const c_nCapacity = probeset_type::c_nCapacity;
1394 node_type * m_arrNode[c_nCapacity];
1395 unsigned int m_nSize;
1397 void shift_up( unsigned int nFrom )
1399 assert( m_nSize < c_nCapacity );
1401 if ( nFrom < m_nSize )
1402 std::copy_backward( m_arrNode + nFrom, m_arrNode + m_nSize, m_arrNode + m_nSize + 1 );
1405 void shift_down( node_type ** pFrom )
1407 assert( m_arrNode <= pFrom && pFrom < m_arrNode + m_nSize);
1408 std::copy( pFrom + 1, m_arrNode + m_nSize, pFrom );
1414 friend class bucket_entry;
1420 iterator( node_type ** p )
1423 iterator( iterator const& it)
1427 iterator& operator=( iterator const& it )
1433 node_type * operator->()
1435 assert( pArr != nullptr );
1438 node_type& operator*()
1440 assert( pArr != nullptr );
1441 assert( *pArr != nullptr );
1446 iterator& operator ++()
1452 bool operator==(iterator const& it ) const
1454 return pArr == it.pArr;
1456 bool operator!=(iterator const& it ) const
1458 return !( *this == it );
1466 memset( m_arrNode, 0, sizeof(m_arrNode));
1467 static_assert(( std::is_same<typename node_type::probeset_type, probeset_type>::value ), "Incompatible node type" );
1472 return iterator(m_arrNode);
1476 return iterator(m_arrNode + size());
1479 void insert_after( iterator it, node_type * p )
1481 assert( m_nSize < c_nCapacity );
1482 assert( !it.pArr || (m_arrNode <= it.pArr && it.pArr <= m_arrNode + m_nSize));
1485 shift_up( static_cast<unsigned int>(it.pArr - m_arrNode) + 1 );
1495 void remove( iterator /*itPrev*/, iterator itWhat )
1498 shift_down( itWhat.pArr );
1507 template <typename Disposer>
1508 void clear( Disposer disp )
1510 for ( unsigned int i = 0; i < m_nSize; ++i ) {
1511 disp( m_arrNode[i] );
1516 unsigned int size() const
1522 template <typename Node, unsigned int ArraySize>
1524 static void store( Node * pNode, size_t * pHashes )
1526 memcpy( pNode->m_arrHash, pHashes, sizeof(pHashes[0]) * ArraySize );
1528 static bool equal_to( Node& node, unsigned int nTable, size_t nHash )
1530 return node.m_arrHash[nTable] == nHash;
1533 template <typename Node>
1534 struct hash_ops<Node, 0>
1536 static void store( Node * /*pNode*/, size_t * /*pHashes*/ )
1538 static bool equal_to( Node& /*node*/, unsigned int /*nTable*/, size_t /*nHash*/ )
1544 template <typename NodeTraits, bool Ordered>
1547 template <typename NodeTraits>
1548 struct contains<NodeTraits, true>
1550 template <typename BucketEntry, typename Position, typename Q, typename Compare>
1551 static bool find( BucketEntry& probeset, Position& pos, unsigned int /*nTable*/, size_t /*nHash*/, Q const& val, Compare cmp )
1554 typedef typename BucketEntry::iterator bucket_iterator;
1556 bucket_iterator itPrev;
1558 for ( bucket_iterator it = probeset.begin(), itEnd = probeset.end(); it != itEnd; ++it ) {
1559 int cmpRes = cmp( *NodeTraits::to_value_ptr(*it), val );
1560 if ( cmpRes >= 0 ) {
1562 pos.itPrev = itPrev;
1569 pos.itPrev = itPrev;
1570 pos.itFound = probeset.end();
1575 template <typename NodeTraits>
1576 struct contains<NodeTraits, false>
1578 template <typename BucketEntry, typename Position, typename Q, typename EqualTo>
1579 static bool find( BucketEntry& probeset, Position& pos, unsigned int nTable, size_t nHash, Q const& val, EqualTo eq )
1581 // Unordered version
1582 typedef typename BucketEntry::iterator bucket_iterator;
1583 typedef typename BucketEntry::node_type node_type;
1585 bucket_iterator itPrev;
1587 for ( bucket_iterator it = probeset.begin(), itEnd = probeset.end(); it != itEnd; ++it ) {
1588 if ( hash_ops<node_type, node_type::hash_array_size>::equal_to( *it, nTable, nHash ) && eq( *NodeTraits::to_value_ptr(*it), val )) {
1590 pos.itPrev = itPrev;
1596 pos.itPrev = itPrev;
1597 pos.itFound = probeset.end();
1602 } // namespace details
1605 } // namespace cuckoo
1608 /** @ingroup cds_intrusive_map
1611 - [2007] M.Herlihy, N.Shavit, M.Tzafrir "Concurrent Cuckoo Hashing. Technical report"
1612 - [2008] Maurice Herlihy, Nir Shavit "The Art of Multiprocessor Programming"
1614 <b>About Cuckoo hashing</b>
1616 [From <i>"The Art of Multiprocessor Programming"</i>]
1617 <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
1618 occupying the same slot. For brevity, a table is a k-entry array of items. For a hash set of size
1619 N = 2k we use a two-entry array of tables, and two independent hash functions,
1620 <tt> h0, h1: KeyRange -> 0,...,k-1</tt>
1621 mapping the set of possible keys to entries in he array. To test whether a value \p x is in the set,
1622 <tt>find(x)</tt> tests whether either <tt>table[0][h0(x)]</tt> or <tt>table[1][h1(x)]</tt> is
1623 equal to \p x. Similarly, <tt>erase(x)</tt>checks whether \p x is in either <tt>table[0][h0(x)]</tt>
1624 or <tt>table[1][h1(x)]</tt>, ad removes it if found.
1626 The <tt>insert(x)</tt> successively "kicks out" conflicting items until every key has a slot.
1627 To add \p x, the method swaps \p x with \p y, the current occupant of <tt>table[0][h0(x)]</tt>.
1628 If the prior value was \p nullptr, it is done. Otherwise, it swaps the newly nest-less value \p y
1629 for the current occupant of <tt>table[1][h1(y)]</tt> in the same way. As before, if the prior value
1630 was \p nullptr, it is done. Otherwise, the method continues swapping entries (alternating tables)
1631 until it finds an empty slot. We might not find an empty slot, either because the table is full,
1632 or because the sequence of displacement forms a cycle. We therefore need an upper limit on the
1633 number of successive displacements we are willing to undertake. When this limit is exceeded,
1634 we resize the hash table, choose new hash functions and start over.
1636 For concurrent cuckoo hashing, rather than organizing the set as a two-dimensional table of
1637 items, we use two-dimensional table of probe sets, where a probe set is a constant-sized set
1638 of items with the same hash code. Each probe set holds at most \p PROBE_SIZE items, but the algorithm
1639 tries to ensure that when the set is quiescent (i.e no method call in progress) each probe set
1640 holds no more than <tt>THRESHOLD < PROBE_SET</tt> items. While method calls are in-flight, a probe
1641 set may temporarily hold more than \p THRESHOLD but never more than \p PROBE_SET items.
1643 In current implementation, a probe set can be defined either as a (single-linked) list
1644 or as a fixed-sized vector, optionally ordered.
1646 In description above two-table cuckoo hashing (<tt>k = 2</tt>) has been considered.
1647 We can generalize this approach for <tt>k >= 2</tt> when we have \p k hash functions
1648 <tt>h[0], ... h[k-1]</tt> and \p k tables <tt>table[0], ... table[k-1]</tt>.
1650 The search in probe set is linear, the complexity is <tt> O(PROBE_SET) </tt>.
1651 The probe set may be ordered or not. Ordered probe set can be more efficient since
1652 the average search complexity is <tt>O(PROBE_SET/2)</tt>.
1653 However, the overhead of sorting can eliminate a gain of ordered search.
1655 The probe set is ordered if \p compare or \p less is specified in \p Traits template
1656 parameter. Otherwise, the probe set is unordered and \p Traits should provide
1657 \p equal_to predicate.
1659 The \p cds::intrusive::cuckoo namespace contains \p %CuckooSet-related declarations.
1662 - \p T - the type stored in the set. The type must be based on \p cuckoo::node (for \p cuckoo::base_hook)
1663 or it must have a member of type %cuckoo::node (for \p cuckoo::member_hook),
1664 or it must be convertible to \p %cuckoo::node (for \p cuckoo::traits_hook)
1665 - \p Traits - type traits, default is \p cuckoo::traits. It is possible to declare option-based
1666 set with \p cuckoo::make_traits metafunction result as \p Traits template argument.
1670 You should incorporate \p cuckoo::node into your struct \p T and provide
1671 appropriate \p cuckoo::traits::hook in your \p Traits template parameters.
1672 Usually, for \p Traits you define a struct based on \p cuckoo::traits.
1674 Example for base hook and list-based probe-set:
1676 #include <cds/intrusive/cuckoo_set.h>
1678 // Data stored in cuckoo set
1679 // We use list as probe-set container and store hash values in the node
1680 // (since we use two hash functions we should store 2 hash values per node)
1681 struct my_data: public cds::intrusive::cuckoo::node< cds::intrusive::cuckoo::list, 2 >
1690 // Provide equal_to functor for my_data since we will use unordered probe-set
1691 struct my_data_equal_to {
1692 bool operator()( const my_data& d1, const my_data& d2 ) const
1694 return d1.strKey.compare( d2.strKey ) == 0;
1697 bool operator()( const my_data& d, const std::string& s ) const
1699 return d.strKey.compare(s) == 0;
1702 bool operator()( const std::string& s, const my_data& d ) const
1704 return s.compare( d.strKey ) == 0;
1708 // Provide two hash functor for my_data
1710 size_t operator()(std::string const& s) const
1712 return cds::opt::v::hash<std::string>( s );
1714 size_t operator()( my_data const& d ) const
1716 return (*this)( d.strKey );
1720 struct hash2: private hash1 {
1721 size_t operator()(std::string const& s) const
1723 size_t h = ~( hash1::operator()(s));
1724 return ~h + 0x9e3779b9 + (h << 6) + (h >> 2);
1726 size_t operator()( my_data const& d ) const
1728 return (*this)( d.strKey );
1732 // Declare type traits
1733 struct my_traits: public cds::intrusive::cuckoo::traits
1735 typedef cds::intrusive::cuckoo::base_hook<
1736 cds::intrusive::cuckoo::probeset_type< my_data::probeset_type >
1737 ,cds::intrusive::cuckoo::store_hash< my_data::hash_array_size >
1739 typedef my_data_equa_to equal_to;
1740 typedef cds::opt::hash_tuple< hash1, hash2 > hash;
1743 // Declare CuckooSet type
1744 typedef cds::intrusive::CuckooSet< my_data, my_traits > my_cuckoo_set;
1746 // Equal option-based declaration
1747 typedef cds::intrusive::CuckooSet< my_data,
1748 cds::intrusive::cuckoo::make_traits<
1749 cds::intrusive::opt::hook< cds::intrusive::cuckoo::base_hook<
1750 cds::intrusive::cuckoo::probeset_type< my_data::probeset_type >
1751 ,cds::intrusive::cuckoo::store_hash< my_data::hash_array_size >
1753 ,cds::opt::hash< std::tuple< hash1, hash2 > >
1754 ,cds::opt::equal_to< my_data_equal_to >
1759 If we provide \p compare function instead of \p equal_to for \p my_data
1760 we get as a result a cuckoo set with ordered probe set that may improve
1762 Example for base hook and ordered vector-based probe-set:
1765 #include <cds/intrusive/cuckoo_set.h>
1767 // Data stored in cuckoo set
1768 // We use a vector of capacity 4 as probe-set container and store hash values in the node
1769 // (since we use two hash functions we should store 2 hash values per node)
1770 struct my_data: public cds::intrusive::cuckoo::node< cds::intrusive::cuckoo::vector<4>, 2 >
1779 // Provide compare functor for my_data since we want to use ordered probe-set
1780 struct my_data_compare {
1781 int operator()( const my_data& d1, const my_data& d2 ) const
1783 return d1.strKey.compare( d2.strKey );
1786 int operator()( const my_data& d, const std::string& s ) const
1788 return d.strKey.compare(s);
1791 int operator()( const std::string& s, const my_data& d ) const
1793 return s.compare( d.strKey );
1797 // Provide two hash functor for my_data
1799 size_t operator()(std::string const& s) const
1801 return cds::opt::v::hash<std::string>( s );
1803 size_t operator()( my_data const& d ) const
1805 return (*this)( d.strKey );
1809 struct hash2: private hash1 {
1810 size_t operator()(std::string const& s) const
1812 size_t h = ~( hash1::operator()(s));
1813 return ~h + 0x9e3779b9 + (h << 6) + (h >> 2);
1815 size_t operator()( my_data const& d ) const
1817 return (*this)( d.strKey );
1821 // Declare type traits
1822 struct my_traits: public cds::intrusive::cuckoo::traits
1824 typedef cds::intrusive::cuckoo::base_hook<
1825 cds::intrusive::cuckoo::probeset_type< my_data::probeset_type >
1826 ,cds::intrusive::cuckoo::store_hash< my_data::hash_array_size >
1828 typedef my_data_compare compare;
1829 typedef cds::opt::hash_tuple< hash1, hash2 > hash;
1832 // Declare CuckooSet type
1833 typedef cds::intrusive::CuckooSet< my_data, my_traits > my_cuckoo_set;
1835 // Equal option-based declaration
1836 typedef cds::intrusive::CuckooSet< my_data,
1837 cds::intrusive::cuckoo::make_traits<
1838 cds::intrusive::opt::hook< cds::intrusive::cuckoo::base_hook<
1839 cds::intrusive::cuckoo::probeset_type< my_data::probeset_type >
1840 ,cds::intrusive::cuckoo::store_hash< my_data::hash_array_size >
1842 ,cds::opt::hash< std::tuple< hash1, hash2 > >
1843 ,cds::opt::compare< my_data_compare >
1849 template <typename T, typename Traits = cuckoo::traits>
1853 typedef T value_type; ///< The value type stored in the set
1854 typedef Traits traits; ///< Set traits
1856 typedef typename traits::hook hook; ///< hook type
1857 typedef typename hook::node_type node_type; ///< node type
1858 typedef typename get_node_traits< value_type, node_type, hook>::type node_traits; ///< node traits
1860 typedef typename traits::hash hash; ///< hash functor tuple wrapped for internal use
1861 typedef typename hash::hash_tuple_type hash_tuple_type; ///< Type of hash tuple
1863 typedef typename traits::stat stat; ///< internal statistics type
1865 typedef typename traits::mutex_policy original_mutex_policy; ///< Concurrent access policy, see \p cuckoo::traits::mutex_policy
1868 typedef typename original_mutex_policy::template rebind_statistics<
1869 typename std::conditional<
1870 std::is_same< stat, cuckoo::empty_stat >::value
1871 ,typename original_mutex_policy::empty_stat
1872 ,typename original_mutex_policy::real_stat
1874 >::other mutex_policy;
1877 /// Probe set should be ordered or not
1879 If \p Traits specifies \p cmpare or \p less functor then the set is ordered.
1880 Otherwise, it is unordered and \p Traits should provide \p equal_to functor.
1882 static bool const c_isSorted = !( std::is_same< typename traits::compare, opt::none >::value
1883 && std::is_same< typename traits::less, opt::none >::value );
1884 static size_t const c_nArity = hash::size ; ///< the arity of cuckoo hashing: the number of hash functors provided; minimum 2.
1886 /// Key equality functor; used only for unordered probe-set
1887 typedef typename opt::details::make_equal_to< value_type, traits, !c_isSorted>::type key_equal_to;
1889 /// key comparing functor based on \p opt::compare and \p opt::less option setter. Used only for ordered probe set
1890 typedef typename opt::details::make_comparator< value_type, traits >::type key_comparator;
1893 typedef typename traits::allocator allocator;
1895 /// item counter type
1896 typedef typename traits::item_counter item_counter;
1899 typedef typename traits::disposer disposer;
1903 typedef typename node_type::probeset_class probeset_class;
1904 typedef typename node_type::probeset_type probeset_type;
1905 static unsigned int const c_nNodeHashArraySize = node_type::hash_array_size;
1907 typedef typename mutex_policy::scoped_cell_lock scoped_cell_lock;
1908 typedef typename mutex_policy::scoped_cell_trylock scoped_cell_trylock;
1909 typedef typename mutex_policy::scoped_full_lock scoped_full_lock;
1910 typedef typename mutex_policy::scoped_resize_lock scoped_resize_lock;
1912 typedef cuckoo::details::bucket_entry< node_type, probeset_type > bucket_entry;
1913 typedef typename bucket_entry::iterator bucket_iterator;
1914 typedef cds::details::Allocator< bucket_entry, allocator > bucket_table_allocator;
1916 typedef size_t hash_array[c_nArity] ; ///< hash array
1919 bucket_iterator itPrev;
1920 bucket_iterator itFound;
1923 typedef cuckoo::details::contains< node_traits, c_isSorted > contains_action;
1925 template <typename Predicate>
1926 struct predicate_wrapper {
1927 typedef typename std::conditional< c_isSorted, cds::opt::details::make_comparator_from_less<Predicate>, Predicate>::type type;
1930 typedef typename std::conditional< c_isSorted, key_comparator, key_equal_to >::type key_predicate;
1934 static unsigned int const c_nDefaultProbesetSize = 4; ///< default probeset size
1935 static size_t const c_nDefaultInitialSize = 16; ///< default initial size
1936 static unsigned int const c_nRelocateLimit = c_nArity * 2 - 1; ///< Count of attempts to relocate before giving up
1939 bucket_entry * m_BucketTable[ c_nArity ] ; ///< Bucket tables
1941 size_t m_nBucketMask ; ///< Hash bitmask; bucket table size minus 1.
1942 unsigned int const m_nProbesetSize ; ///< Probe set size
1943 unsigned int const m_nProbesetThreshold ; ///< Probe set threshold
1945 hash m_Hash ; ///< Hash functor tuple
1946 mutex_policy m_MutexPolicy ; ///< concurrent access policy
1947 item_counter m_ItemCounter ; ///< item counter
1948 mutable stat m_Stat ; ///< internal statistics
1952 static void check_common_constraints()
1954 static_assert( (c_nArity == mutex_policy::c_nArity), "The count of hash functors must be equal to mutex_policy arity" );
1957 void check_probeset_properties() const
1959 assert( m_nProbesetThreshold < m_nProbesetSize );
1961 // if probe set type is cuckoo::vector<N> then m_nProbesetSize == N
1962 assert( node_type::probeset_size == 0 || node_type::probeset_size == m_nProbesetSize );
1965 template <typename Q>
1966 void hashing( size_t * pHashes, Q const& v ) const
1968 m_Hash( pHashes, v );
1971 void copy_hash( size_t * pHashes, value_type const& v ) const
1973 if ( c_nNodeHashArraySize )
1974 memcpy( pHashes, node_traits::to_node_ptr( v )->get_hash(), sizeof(pHashes[0]) * c_nNodeHashArraySize );
1976 hashing( pHashes, v );
1979 bucket_entry& bucket( unsigned int nTable, size_t nHash )
1981 assert( nTable < c_nArity );
1982 return m_BucketTable[nTable][nHash & m_nBucketMask];
1985 static void store_hash( node_type * pNode, size_t * pHashes )
1987 cuckoo::details::hash_ops< node_type, c_nNodeHashArraySize >::store( pNode, pHashes );
1990 static bool equal_hash( node_type& node, unsigned int nTable, size_t nHash )
1992 return cuckoo::details::hash_ops< node_type, c_nNodeHashArraySize >::equal_to( node, nTable, nHash );
1995 void allocate_bucket_tables( size_t nSize )
1997 assert( cds::beans::is_power2( nSize ));
1999 m_nBucketMask = nSize - 1;
2000 bucket_table_allocator alloc;
2001 for ( unsigned int i = 0; i < c_nArity; ++i )
2002 m_BucketTable[i] = alloc.NewArray( nSize );
2005 static void free_bucket_tables( bucket_entry ** pTable, size_t nCapacity )
2007 bucket_table_allocator alloc;
2008 for ( unsigned int i = 0; i < c_nArity; ++i ) {
2009 alloc.Delete( pTable[i], nCapacity );
2010 pTable[i] = nullptr;
2013 void free_bucket_tables()
2015 free_bucket_tables( m_BucketTable, m_nBucketMask + 1 );
2018 static CDS_CONSTEXPR unsigned int const c_nUndefTable = (unsigned int) -1;
2019 template <typename Q, typename Predicate >
2020 unsigned int contains( position * arrPos, size_t * arrHash, Q const& val, Predicate pred )
2022 // Buckets must be locked
2024 for ( unsigned int i = 0; i < c_nArity; ++i ) {
2025 bucket_entry& probeset = bucket( i, arrHash[i] );
2026 if ( contains_action::find( probeset, arrPos[i], i, arrHash[i], val, pred ))
2029 return c_nUndefTable;
2032 template <typename Q, typename Predicate, typename Func>
2033 value_type * erase_( Q const& val, Predicate pred, Func f )
2036 hashing( arrHash, val );
2037 position arrPos[ c_nArity ];
2040 scoped_cell_lock guard( m_MutexPolicy, arrHash );
2042 unsigned int nTable = contains( arrPos, arrHash, val, pred );
2043 if ( nTable != c_nUndefTable ) {
2044 node_type& node = *arrPos[nTable].itFound;
2045 f( *node_traits::to_value_ptr(node));
2046 bucket( nTable, arrHash[nTable]).remove( arrPos[nTable].itPrev, arrPos[nTable].itFound );
2048 m_Stat.onEraseSuccess();
2049 return node_traits::to_value_ptr( node );
2053 m_Stat.onEraseFailed();
2057 template <typename Q, typename Predicate, typename Func>
2058 bool find_( Q& val, Predicate pred, Func f )
2061 position arrPos[ c_nArity ];
2062 hashing( arrHash, val );
2063 scoped_cell_lock sl( m_MutexPolicy, arrHash );
2065 unsigned int nTable = contains( arrPos, arrHash, val, pred );
2066 if ( nTable != c_nUndefTable ) {
2067 f( *node_traits::to_value_ptr( *arrPos[nTable].itFound ), val );
2068 m_Stat.onFindSuccess();
2072 m_Stat.onFindFailed();
2076 bool relocate( unsigned int nTable, size_t * arrGoalHash )
2078 // arrGoalHash contains hash values for relocating element
2079 // Relocating element is first one from bucket( nTable, arrGoalHash[nTable] ) probeset
2081 m_Stat.onRelocateCall();
2085 for ( unsigned int nRound = 0; nRound < c_nRelocateLimit; ++nRound ) {
2086 m_Stat.onRelocateRound();
2089 scoped_cell_lock guard( m_MutexPolicy, arrGoalHash );
2091 bucket_entry& refBucket = bucket( nTable, arrGoalHash[nTable] );
2092 if ( refBucket.size() < m_nProbesetThreshold ) {
2093 // probeset is not above the threshold
2094 m_Stat.onFalseRelocateRound();
2098 pVal = node_traits::to_value_ptr( *refBucket.begin());
2099 copy_hash( arrHash, *pVal );
2101 scoped_cell_trylock guard2( m_MutexPolicy, arrHash );
2102 if ( !guard2.locked())
2103 continue ; // try one more time
2105 refBucket.remove( typename bucket_entry::iterator(), refBucket.begin());
2107 unsigned int i = (nTable + 1) % c_nArity;
2109 // try insert into free probeset
2110 while ( i != nTable ) {
2111 bucket_entry& bkt = bucket( i, arrHash[i] );
2112 if ( bkt.size() < m_nProbesetThreshold ) {
2114 contains_action::find( bkt, pos, i, arrHash[i], *pVal, key_predicate()) ; // must return false!
2115 bkt.insert_after( pos.itPrev, node_traits::to_node_ptr( pVal ));
2116 m_Stat.onSuccessRelocateRound();
2119 i = ( i + 1 ) % c_nArity;
2122 // try insert into partial probeset
2123 i = (nTable + 1) % c_nArity;
2124 while ( i != nTable ) {
2125 bucket_entry& bkt = bucket( i, arrHash[i] );
2126 if ( bkt.size() < m_nProbesetSize ) {
2128 contains_action::find( bkt, pos, i, arrHash[i], *pVal, key_predicate()) ; // must return false!
2129 bkt.insert_after( pos.itPrev, node_traits::to_node_ptr( pVal ));
2131 memcpy( arrGoalHash, arrHash, sizeof(arrHash));
2132 m_Stat.onRelocateAboveThresholdRound();
2133 goto next_iteration;
2135 i = (i + 1) % c_nArity;
2138 // all probeset is full, relocating fault
2139 refBucket.insert_after( typename bucket_entry::iterator(), node_traits::to_node_ptr( pVal ));
2140 m_Stat.onFailedRelocate();
2151 m_Stat.onResizeCall();
2153 size_t nOldCapacity = bucket_count();
2154 bucket_entry * pOldTable[ c_nArity ];
2156 scoped_resize_lock guard( m_MutexPolicy );
2158 if ( nOldCapacity != bucket_count()) {
2159 m_Stat.onFalseResizeCall();
2163 size_t nCapacity = nOldCapacity * 2;
2165 m_MutexPolicy.resize( nCapacity );
2166 memcpy( pOldTable, m_BucketTable, sizeof(pOldTable));
2167 allocate_bucket_tables( nCapacity );
2169 typedef typename bucket_entry::iterator bucket_iterator;
2171 position arrPos[ c_nArity ];
2173 for ( unsigned int nTable = 0; nTable < c_nArity; ++nTable ) {
2174 bucket_entry * pTable = pOldTable[nTable];
2175 for ( size_t k = 0; k < nOldCapacity; ++k ) {
2176 bucket_iterator itNext;
2177 for ( bucket_iterator it = pTable[k].begin(), itEnd = pTable[k].end(); it != itEnd; it = itNext ) {
2181 value_type& val = *node_traits::to_value_ptr( *it );
2182 copy_hash( arrHash, val );
2183 contains( arrPos, arrHash, val, key_predicate()) ; // must return c_nUndefTable
2185 for ( unsigned int i = 0; i < c_nArity; ++i ) {
2186 bucket_entry& refBucket = bucket( i, arrHash[i] );
2187 if ( refBucket.size() < m_nProbesetThreshold ) {
2188 refBucket.insert_after( arrPos[i].itPrev, &*it );
2189 m_Stat.onResizeSuccessMove();
2194 for ( unsigned int i = 0; i < c_nArity; ++i ) {
2195 bucket_entry& refBucket = bucket( i, arrHash[i] );
2196 if ( refBucket.size() < m_nProbesetSize ) {
2197 refBucket.insert_after( arrPos[i].itPrev, &*it );
2198 assert( refBucket.size() > 1 );
2199 copy_hash( arrHash, *node_traits::to_value_ptr( *refBucket.begin()));
2200 m_Stat.onResizeRelocateCall();
2201 relocate( i, arrHash );
2210 free_bucket_tables( pOldTable, nOldCapacity );
2213 CDS_CONSTEXPR static unsigned int calc_probeset_size( unsigned int nProbesetSize ) CDS_NOEXCEPT
2215 return std::is_same< probeset_class, cuckoo::vector_probeset_class >::value
2216 ? node_type::probeset_size
2219 : ( node_type::probeset_size ? node_type::probeset_size : c_nDefaultProbesetSize ));
2224 /// Default constructor
2226 Initial size = \ref c_nDefaultInitialSize
2229 - \p c_nDefaultProbesetSize if \p probeset_type is \p cuckoo::list
2230 - \p Capacity if \p probeset_type is <tt> cuckoo::vector<Capacity> </tt>
2232 Probe set threshold = probe set size - 1
2235 : m_nProbesetSize( calc_probeset_size(0))
2236 , m_nProbesetThreshold( m_nProbesetSize - 1 )
2237 , m_MutexPolicy( c_nDefaultInitialSize )
2239 check_common_constraints();
2240 check_probeset_properties();
2242 allocate_bucket_tables( c_nDefaultInitialSize );
2245 /// Constructs the set object with given probe set size and threshold
2247 If probe set type is <tt> cuckoo::vector<Capacity> </tt> vector
2248 then \p nProbesetSize is ignored since it should be equal to vector's \p Capacity.
2251 size_t nInitialSize ///< Initial set size; if 0 - use default initial size \p c_nDefaultInitialSize
2252 , unsigned int nProbesetSize ///< probe set size
2253 , unsigned int nProbesetThreshold = 0 ///< probe set threshold, <tt>nProbesetThreshold < nProbesetSize</tt>. If 0, <tt>nProbesetThreshold = nProbesetSize - 1</tt>
2255 : m_nProbesetSize( calc_probeset_size(nProbesetSize))
2256 , m_nProbesetThreshold( nProbesetThreshold ? nProbesetThreshold : m_nProbesetSize - 1 )
2257 , m_MutexPolicy( cds::beans::ceil2(nInitialSize ? nInitialSize : c_nDefaultInitialSize ))
2259 check_common_constraints();
2260 check_probeset_properties();
2262 allocate_bucket_tables( nInitialSize ? cds::beans::ceil2( nInitialSize ) : c_nDefaultInitialSize );
2265 /// Constructs the set object with given hash functor tuple
2267 The probe set size and threshold are set as default, see \p CuckooSet()
2270 hash_tuple_type const& h ///< hash functor tuple of type <tt>std::tuple<H1, H2, ... Hn></tt> where <tt> n == \ref c_nArity </tt>
2272 : m_nProbesetSize( calc_probeset_size(0))
2273 , m_nProbesetThreshold( m_nProbesetSize -1 )
2275 , m_MutexPolicy( c_nDefaultInitialSize )
2277 check_common_constraints();
2278 check_probeset_properties();
2280 allocate_bucket_tables( c_nDefaultInitialSize );
2283 /// Constructs the set object with given probe set properties and hash functor tuple
2285 If probe set type is <tt> cuckoo::vector<Capacity> </tt> vector
2286 then \p nProbesetSize should be equal to vector's \p Capacity.
2289 size_t nInitialSize ///< Initial set size; if 0 - use default initial size \p c_nDefaultInitialSize
2290 , unsigned int nProbesetSize ///< probe set size, positive integer
2291 , unsigned int nProbesetThreshold ///< probe set threshold, <tt>nProbesetThreshold < nProbesetSize</tt>. If 0, <tt>nProbesetThreshold = nProbesetSize - 1</tt>
2292 , hash_tuple_type const& h ///< hash functor tuple of type <tt>std::tuple<H1, H2, ... Hn></tt> where <tt> n == \ref c_nArity </tt>
2294 : m_nProbesetSize( calc_probeset_size(nProbesetSize))
2295 , m_nProbesetThreshold( nProbesetThreshold ? nProbesetThreshold : m_nProbesetSize - 1)
2297 , m_MutexPolicy( cds::beans::ceil2(nInitialSize ? nInitialSize : c_nDefaultInitialSize ))
2299 check_common_constraints();
2300 check_probeset_properties();
2302 allocate_bucket_tables( nInitialSize ? cds::beans::ceil2( nInitialSize ) : c_nDefaultInitialSize );
2305 /// Constructs the set object with given hash functor tuple (move semantics)
2307 The probe set size and threshold are set as default, see \p CuckooSet()
2310 hash_tuple_type&& h ///< hash functor tuple of type <tt>std::tuple<H1, H2, ... Hn></tt> where <tt> n == \ref c_nArity </tt>
2312 : m_nProbesetSize( calc_probeset_size(0))
2313 , m_nProbesetThreshold( m_nProbesetSize / 2 )
2314 , m_Hash( std::forward<hash_tuple_type>(h))
2315 , m_MutexPolicy( c_nDefaultInitialSize )
2317 check_common_constraints();
2318 check_probeset_properties();
2320 allocate_bucket_tables( c_nDefaultInitialSize );
2323 /// Constructs the set object with given probe set properties and hash functor tuple (move semantics)
2325 If probe set type is <tt> cuckoo::vector<Capacity> </tt> vector
2326 then \p nProbesetSize should be equal to vector's \p Capacity.
2329 size_t nInitialSize ///< Initial set size; if 0 - use default initial size \p c_nDefaultInitialSize
2330 , unsigned int nProbesetSize ///< probe set size, positive integer
2331 , unsigned int nProbesetThreshold ///< probe set threshold, <tt>nProbesetThreshold < nProbesetSize</tt>. If 0, <tt>nProbesetThreshold = nProbesetSize - 1</tt>
2332 , hash_tuple_type&& h ///< hash functor tuple of type <tt>std::tuple<H1, H2, ... Hn></tt> where <tt> n == \ref c_nArity </tt>
2334 : m_nProbesetSize( calc_probeset_size(nProbesetSize))
2335 , m_nProbesetThreshold( nProbesetThreshold ? nProbesetThreshold : m_nProbesetSize - 1)
2336 , m_Hash( std::forward<hash_tuple_type>(h))
2337 , m_MutexPolicy( cds::beans::ceil2(nInitialSize ? nInitialSize : c_nDefaultInitialSize ))
2339 check_common_constraints();
2340 check_probeset_properties();
2342 allocate_bucket_tables( nInitialSize ? cds::beans::ceil2( nInitialSize ) : c_nDefaultInitialSize );
2348 free_bucket_tables();
2352 /// Inserts new node
2354 The function inserts \p val in the set if it does not contain an item with key equal to \p val.
2356 Returns \p true if \p val is inserted into the set, \p false otherwise.
2358 bool insert( value_type& val )
2360 return insert( val, []( value_type& ) {} );
2363 /// Inserts new node
2365 The function allows to split creating of new item into two part:
2366 - create item with key only
2367 - insert new item into the set
2368 - if inserting is success, calls \p f functor to initialize value-field of \p val.
2370 The functor signature is:
2372 void func( value_type& val );
2374 where \p val is the item inserted.
2376 The user-defined functor is called only if the inserting is success.
2378 template <typename Func>
2379 bool insert( value_type& val, Func f )
2382 position arrPos[ c_nArity ];
2383 unsigned int nGoalTable;
2385 hashing( arrHash, val );
2386 node_type * pNode = node_traits::to_node_ptr( val );
2387 store_hash( pNode, arrHash );
2391 scoped_cell_lock guard( m_MutexPolicy, arrHash );
2393 if ( contains( arrPos, arrHash, val, key_predicate()) != c_nUndefTable ) {
2394 m_Stat.onInsertFailed();
2398 for ( unsigned int i = 0; i < c_nArity; ++i ) {
2399 bucket_entry& refBucket = bucket( i, arrHash[i] );
2400 if ( refBucket.size() < m_nProbesetThreshold ) {
2401 refBucket.insert_after( arrPos[i].itPrev, pNode );
2404 m_Stat.onInsertSuccess();
2409 for ( unsigned int i = 0; i < c_nArity; ++i ) {
2410 bucket_entry& refBucket = bucket( i, arrHash[i] );
2411 if ( refBucket.size() < m_nProbesetSize ) {
2412 refBucket.insert_after( arrPos[i].itPrev, pNode );
2416 assert( refBucket.size() > 1 );
2417 copy_hash( arrHash, *node_traits::to_value_ptr( *refBucket.begin()));
2423 m_Stat.onInsertResize();
2428 m_Stat.onInsertRelocate();
2429 if ( !relocate( nGoalTable, arrHash )) {
2430 m_Stat.onInsertRelocateFault();
2431 m_Stat.onInsertResize();
2435 m_Stat.onInsertSuccess();
2439 /// Updates the node
2441 The operation performs inserting or changing data with lock-free manner.
2443 If the item \p val is not found in the set, then \p val is inserted into the set
2444 iff \p bAllowInsert is \p true.
2445 Otherwise, the functor \p func is called with item found.
2446 The functor \p func signature is:
2448 void func( bool bNew, value_type& item, value_type& val );
2451 - \p bNew - \p true if the item has been inserted, \p false otherwise
2452 - \p item - item of the set
2453 - \p val - argument \p val passed into the \p %update() function
2454 If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
2455 refer to the same thing.
2457 The functor may change non-key fields of the \p item.
2459 Returns std::pair<bool, bool> where \p first is \p true if operation is successful,
2460 i.e. the node has been inserted or updated,
2461 \p second is \p true if new item has been added or \p false if the item with \p key
2464 template <typename Func>
2465 std::pair<bool, bool> update( value_type& val, Func func, bool bAllowInsert = true )
2468 position arrPos[ c_nArity ];
2469 unsigned int nGoalTable;
2471 hashing( arrHash, val );
2472 node_type * pNode = node_traits::to_node_ptr( val );
2473 store_hash( pNode, arrHash );
2477 scoped_cell_lock guard( m_MutexPolicy, arrHash );
2479 unsigned int nTable = contains( arrPos, arrHash, val, key_predicate());
2480 if ( nTable != c_nUndefTable ) {
2481 func( false, *node_traits::to_value_ptr( *arrPos[nTable].itFound ), val );
2482 m_Stat.onUpdateExist();
2483 return std::make_pair( true, false );
2486 if ( !bAllowInsert )
2487 return std::make_pair( false, false );
2489 //node_type * pNode = node_traits::to_node_ptr( val );
2490 //store_hash( pNode, arrHash );
2492 for ( unsigned int i = 0; i < c_nArity; ++i ) {
2493 bucket_entry& refBucket = bucket( i, arrHash[i] );
2494 if ( refBucket.size() < m_nProbesetThreshold ) {
2495 refBucket.insert_after( arrPos[i].itPrev, pNode );
2496 func( true, val, val );
2498 m_Stat.onUpdateSuccess();
2499 return std::make_pair( true, true );
2503 for ( unsigned int i = 0; i < c_nArity; ++i ) {
2504 bucket_entry& refBucket = bucket( i, arrHash[i] );
2505 if ( refBucket.size() < m_nProbesetSize ) {
2506 refBucket.insert_after( arrPos[i].itPrev, pNode );
2507 func( true, val, val );
2510 assert( refBucket.size() > 1 );
2511 copy_hash( arrHash, *node_traits::to_value_ptr( *refBucket.begin()));
2517 m_Stat.onUpdateResize();
2522 m_Stat.onUpdateRelocate();
2523 if ( !relocate( nGoalTable, arrHash )) {
2524 m_Stat.onUpdateRelocateFault();
2525 m_Stat.onUpdateResize();
2529 m_Stat.onUpdateSuccess();
2530 return std::make_pair( true, true );
2533 template <typename Func>
2534 CDS_DEPRECATED("ensure() is deprecated, use update()")
2535 std::pair<bool, bool> ensure( value_type& val, Func func )
2537 return update( val, func, true );
2541 /// Unlink the item \p val from the set
2543 The function searches the item \p val in the set and unlink it
2544 if it is found and is equal to \p val (here, the equality means that
2545 \p val belongs to the set: if \p item is an item found then
2546 unlink is successful iif <tt>&val == &item</tt>)
2548 The function returns \p true if success and \p false otherwise.
2550 bool unlink( value_type& val )
2553 hashing( arrHash, val );
2554 position arrPos[ c_nArity ];
2557 scoped_cell_lock guard( m_MutexPolicy, arrHash );
2559 unsigned int nTable = contains( arrPos, arrHash, val, key_predicate());
2560 if ( nTable != c_nUndefTable && node_traits::to_value_ptr(*arrPos[nTable].itFound) == &val ) {
2561 bucket( nTable, arrHash[nTable]).remove( arrPos[nTable].itPrev, arrPos[nTable].itFound );
2563 m_Stat.onUnlinkSuccess();
2568 m_Stat.onUnlinkFailed();
2572 /// Deletes the item from the set
2573 /** \anchor cds_intrusive_CuckooSet_erase
2574 The function searches an item with key equal to \p val in the set,
2575 unlinks it from the set, and returns a pointer to unlinked item.
2577 If the item with key equal to \p val is not found the function return \p nullptr.
2579 Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
2581 template <typename Q>
2582 value_type * erase( Q const& val )
2584 return erase( val, [](value_type const&) {} );
2587 /// Deletes the item from the set using \p pred predicate for searching
2589 The function is an analog of \ref cds_intrusive_CuckooSet_erase "erase(Q const&)"
2590 but \p pred is used for key comparing.
2591 If cuckoo set is ordered, then \p Predicate should have the interface and semantics like \p std::less.
2592 If cuckoo set is unordered, then \p Predicate should have the interface and semantics like \p std::equal_to.
2593 \p Predicate must imply the same element order as the comparator used for building the set.
2595 template <typename Q, typename Predicate>
2596 value_type * erase_with( Q const& val, Predicate pred )
2599 return erase_( val, typename predicate_wrapper<Predicate>::type(), [](value_type const&) {} );
2602 /// Delete the item from the set
2603 /** \anchor cds_intrusive_CuckooSet_erase_func
2604 The function searches an item with key equal to \p val in the set,
2605 call \p f functor with item found, unlinks it from the set, and returns a pointer to unlinked item.
2607 The \p Func interface is
2610 void operator()( value_type const& item );
2614 If the item with key equal to \p val is not found the function return \p nullptr.
2616 Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
2618 template <typename Q, typename Func>
2619 value_type * erase( Q const& val, Func f )
2621 return erase_( val, key_predicate(), f );
2624 /// Deletes the item from the set using \p pred predicate for searching
2626 The function is an analog of \ref cds_intrusive_CuckooSet_erase_func "erase(Q const&, Func)"
2627 but \p pred is used for key comparing.
2628 If you use ordered cuckoo set, then \p Predicate should have the interface and semantics like \p std::less.
2629 If you use unordered cuckoo set, then \p Predicate should have the interface and semantics like \p std::equal_to.
2630 \p Predicate must imply the same element order as the comparator used for building the set.
2632 template <typename Q, typename Predicate, typename Func>
2633 value_type * erase_with( Q const& val, Predicate pred, Func f )
2636 return erase_( val, typename predicate_wrapper<Predicate>::type(), f );
2639 /// Find the key \p val
2640 /** \anchor cds_intrusive_CuckooSet_find_func
2641 The function searches the item with key equal to \p val and calls the functor \p f for item found.
2642 The interface of \p Func functor is:
2645 void operator()( value_type& item, Q& val );
2648 where \p item is the item found, \p val is the <tt>find</tt> function argument.
2650 The functor may change non-key fields of \p item.
2652 The \p val argument is non-const since it can be used as \p f functor destination i.e., the functor
2653 may modify both arguments.
2655 Note the hash functor specified for class \p Traits template parameter
2656 should accept a parameter of type \p Q that can be not the same as \p value_type.
2658 The function returns \p true if \p val is found, \p false otherwise.
2660 template <typename Q, typename Func>
2661 bool find( Q& val, Func f )
2663 return find_( val, key_predicate(), f );
2666 template <typename Q, typename Func>
2667 bool find( Q const& val, Func f )
2669 return find_( val, key_predicate(), f );
2673 /// Find the key \p val using \p pred predicate for comparing
2675 The function is an analog of \ref cds_intrusive_CuckooSet_find_func "find(Q&, Func)"
2676 but \p pred is used for key comparison.
2677 If you use ordered cuckoo set, then \p Predicate should have the interface and semantics like \p std::less.
2678 If you use unordered cuckoo set, then \p Predicate should have the interface and semantics like \p std::equal_to.
2679 \p pred must imply the same element order as the comparator used for building the set.
2681 template <typename Q, typename Predicate, typename Func>
2682 bool find_with( Q& val, Predicate pred, Func f )
2685 return find_( val, typename predicate_wrapper<Predicate>::type(), f );
2688 template <typename Q, typename Predicate, typename Func>
2689 bool find_with( Q const& val, Predicate pred, Func f )
2692 return find_( val, typename predicate_wrapper<Predicate>::type(), f );
2696 /// Checks whether the set contains \p key
2698 The function searches the item with key equal to \p key
2699 and returns \p true if it is found, and \p false otherwise.
2701 template <typename Q>
2702 bool contains( Q const& key )
2704 return find( key, [](value_type&, Q const& ) {} );
2707 template <typename Q>
2708 CDS_DEPRECATED("deprecated, use contains()")
2709 bool find( Q const& key )
2711 return contains( key );
2715 /// Checks whether the set contains \p key using \p pred predicate for searching
2717 The function is similar to <tt>contains( key )</tt> but \p pred is used for key comparing.
2718 If the set is unordered, \p Predicate has semantics like \p std::equal_to.
2719 For ordered set \p Predicate has \p std::less semantics. In that case \p pred
2720 must imply the same element order as the comparator used for building the set.
2722 template <typename Q, typename Predicate>
2723 bool contains( Q const& key, Predicate pred )
2726 return find_with( key, typename predicate_wrapper<Predicate>::type(), [](value_type& , Q const& ) {} );
2729 template <typename Q, typename Predicate>
2730 CDS_DEPRECATED("deprecated, use contains()")
2731 bool find_with( Q const& key, Predicate pred )
2733 return contains( key, pred );
2739 The function unlinks all items from the set.
2740 For any item \p Traits::disposer is called
2744 clear_and_dispose( disposer());
2747 /// Clears the set and calls \p disposer for each item
2749 The function unlinks all items from the set calling \p oDisposer for each item.
2750 \p Disposer functor interface is:
2753 void operator()( value_type * p );
2757 The \p Traits::disposer is not called.
2759 template <typename Disposer>
2760 void clear_and_dispose( Disposer oDisposer )
2762 // locks entire array
2763 scoped_full_lock sl( m_MutexPolicy );
2765 for ( unsigned int i = 0; i < c_nArity; ++i ) {
2766 bucket_entry * pEntry = m_BucketTable[i];
2767 bucket_entry * pEnd = pEntry + m_nBucketMask + 1;
2768 for ( ; pEntry != pEnd ; ++pEntry ) {
2769 pEntry->clear( [&oDisposer]( node_type * pNode ){ oDisposer( node_traits::to_value_ptr( pNode )) ; } );
2772 m_ItemCounter.reset();
2775 /// Checks if the set is empty
2777 Emptiness is checked by item counting: if item count is zero then the set is empty.
2784 /// Returns item count in the set
2787 return m_ItemCounter;
2790 /// Returns the size of hash table
2792 The hash table size is non-constant and can be increased via resizing.
2794 size_t bucket_count() const
2796 return m_nBucketMask + 1;
2799 /// Returns lock array size
2800 size_t lock_count() const
2802 return m_MutexPolicy.lock_count();
2805 /// Returns const reference to internal statistics
2806 stat const& statistics() const
2811 /// Returns const reference to mutex policy internal statistics
2812 typename mutex_policy::statistics_type const& mutex_policy_statistics() const
2814 return m_MutexPolicy.statistics();
2817 }} // namespace cds::intrusive
2819 #endif // #ifndef CDSLIB_INTRUSIVE_CUCKOO_SET_H