3 #ifndef CDSLIB_INTRUSIVE_IMPL_MULTILEVEL_HASHSET_H
4 #define CDSLIB_INTRUSIVE_IMPL_MULTILEVEL_HASHSET_H
6 #include <functional> // std::ref
7 #include <iterator> // std::iterator_traits
9 #include <cds/intrusive/details/multilevel_hashset_base.h>
10 #include <cds/details/allocator.h>
12 namespace cds { namespace intrusive {
13 /// Intrusive hash set based on multi-level array
14 /** @ingroup cds_intrusive_map
15 @anchor cds_intrusive_MultilevelHashSet_hp
18 - [2013] Steven Feldman, Pierre LaBorde, Damian Dechev "Concurrent Multi-level Arrays:
19 Wait-free Extensible Hash Maps"
21 [From the paper] The hardest problem encountered while developing a parallel hash map is how to perform
22 a global resize, the process of redistributing the elements in a hash map that occurs when adding new
23 buckets. The negative impact of blocking synchronization is multiplied during a global resize, because all
24 threads will be forced to wait on the thread that is performing the involved process of resizing the hash map
25 and redistributing the elements. \p %MultilevelHashSet implementation avoids global resizes through new array
26 allocation. By allowing concurrent expansion this structure is free from the overhead of an explicit resize,
27 which facilitates concurrent operations.
29 The presented design includes dynamic hashing, the use of sub-arrays within the hash map data structure;
30 which, in combination with <b>perfect hashing</b>, means that each element has a unique final, as well as current, position.
31 It is important to note that the perfect hash function required by our hash map is trivial to realize as
32 any hash function that permutes the bits of the key is suitable. This is possible because of our approach
33 to the hash function; we require that it produces hash values that are equal in size to that of the key.
34 We know that if we expand the hash map a fixed number of times there can be no collision as duplicate keys
35 are not provided for in the standard semantics of a hash map.
37 \p %MultiLevelHashSet is a multi-level array which has a structure similar to a tree:
38 @image html multilevel_hashset.png
39 The multi-level array differs from a tree in that each position on the tree could hold an array of nodes or a single node.
40 A position that holds a single node is a \p dataNode which holds the hash value of a key and the value that is associated
\r
41 with that key; it is a simple struct holding two variables. A \p dataNode in the multi-level array could be marked.
\r
42 A \p markedDataNode refers to a pointer to a \p dataNode that has been bitmarked at the least significant bit (LSB)
\r
43 of the pointer to the node. This signifies that this \p dataNode is contended. An expansion must occur at this node;
\r
44 any thread that sees this \p markedDataNode will try to replace it with an \p arrayNode; which is a position that holds
\r
45 an array of nodes. The pointer to an \p arrayNode is differentiated from that of a pointer to a \p dataNode by a bitmark
\r
46 on the second-least significant bit.
\r
48 \p %MultiLevelHashSet multi-level array is similar to a tree in that we keep a pointer to the root, which is a memory array
\r
49 called \p head. The length of the \p head memory array is unique, whereas every other \p arrayNode has a uniform length;
\r
50 a normal \p arrayNode has a fixed power-of-two length equal to the binary logarithm of a variable called \p arrayLength.
\r
51 The maximum depth of the tree, \p maxDepth, is the maximum number of pointers that must be followed to reach any node.
\r
52 We define \p currentDepth as the number of memory arrays that we need to traverse to reach the \p arrayNode on which
\r
53 we need to operate; this is initially one, because of \p head.
\r
55 That approach to the structure of the hash set uses an extensible hashing scheme; <b> the hash value is treated as a bit
\r
56 string</b> and rehash incrementally.
\r
58 @note Two important things you should keep in mind when you're using \p %MultiLevelHashSet:
\r
59 - all keys must be fixed-size. It means that you cannot use \p std::string as a key for \p %MultiLevelHashSet.
\r
60 Instead, for the strings you should use well-known hashing algorithms like <a href="https://en.wikipedia.org/wiki/Secure_Hash_Algorithm">SHA1, SHA2</a>,
\r
61 <a href="https://en.wikipedia.org/wiki/MurmurHash">MurmurHash</a>, <a href="https://en.wikipedia.org/wiki/CityHash">CityHash</a>
\r
62 or its successor <a href="https://code.google.com/p/farmhash/">FarmHash</a> and so on, which
\r
63 converts variable-length strings to fixed-length bit-strings, and use that hash as a key in \p %MultiLevelHashSet.
\r
64 - \p %MultiLevelHashSet uses a perfect hashing. It means that if two different keys, for example, of type \p std::string,
\r
65 have identical hash then you cannot insert both that keys in the set. \p %MultiLevelHashSet does not maintain the key,
\r
66 it maintains its fixed-size hash value.
\r
68 The set supports @ref cds_intrusive_MultilevelHashSet_iterators "bidirectional thread-safe iterators".
\r
70 Template parameters:
\r
71 - \p GC - safe memory reclamation schema. Can be \p gc::HP, \p gc::DHP or one of \ref cds_urcu_type "RCU type"
\r
72 - \p T - a value type to be stored in the set
\r
73 - \p Traits - type traits, the structure based on \p multilevel_hashset::traits or result of \p multilevel_hashset::make_traits metafunction.
\r
74 \p Traits is the mandatory argument because it has one mandatory type - an @ref multilevel_hashset::traits::hash_accessor "accessor"
\r
75 to hash value of \p T. The set algorithm does not calculate that hash value.
\r
77 There are several specializations of \p %MultiLevelHashSet for each \p GC. You should include:
78 - <tt><cds/intrusive/multilevel_hashset_hp.h></tt> for \p gc::HP garbage collector
79 - <tt><cds/intrusive/multilevel_hashset_dhp.h></tt> for \p gc::DHP garbage collector
80 - <tt><cds/intrusive/multilevel_hashset_rcu.h></tt> for \ref cds_intrusive_MultiLevelHashSet_rcu "RCU type". RCU specialization
81 has a slightly different interface.
86 #ifdef CDS_DOXYGEN_INVOKED
87 ,typename Traits = multilevel_hashset::traits
92 class MultiLevelHashSet
95 typedef GC gc; ///< Garbage collector
96 typedef T value_type; ///< type of value stored in the set
97 typedef Traits traits; ///< Traits template parameter, see \p multilevel_hashset::traits
99 typedef typename traits::hash_accessor hash_accessor; ///< Hash accessor functor
100 static_assert(!std::is_same< hash_accessor, cds::opt::none >::value, "hash_accessor functor must be specified" );
102 /// Hash type deduced from \p hash_accessor return type
103 typedef typename std::decay<
104 typename std::remove_reference<
105 decltype( hash_accessor()( std::declval<T>()) )
108 //typedef typename std::result_of< hash_accessor( std::declval<T>()) >::type hash_type;
109 static_assert( !std::is_pointer<hash_type>::value, "hash_accessor should return a reference to hash value" );
111 typedef typename traits::disposer disposer; ///< data node disposer
113 # ifdef CDS_DOXYGEN_INVOKED
114 typedef implementation_defined hash_comparator ; ///< hash compare functor based on opt::compare and opt::less option setter
116 typedef typename cds::opt::details::make_comparator_from<
119 multilevel_hashset::bitwise_compare< hash_type >
120 >::type hash_comparator;
123 typedef typename traits::item_counter item_counter; ///< Item counter type
124 typedef typename traits::node_allocator node_allocator; ///< Array node allocator
125 typedef typename traits::memory_model memory_model; ///< Memory model
126 typedef typename traits::back_off back_off; ///< Backoff strategy
127 typedef typename traits::stat stat; ///< Internal statistics type
129 typedef typename gc::template guarded_ptr< value_type > guarded_ptr; ///< Guarded pointer
131 /// Count of hazard pointers required
132 static CDS_CONSTEXPR size_t const c_nHazardPtrCount = 2;
134 /// Node marked poiter
135 typedef cds::details::marked_ptr< value_type, 3 > node_ptr;
136 /// Array node element
137 typedef atomics::atomic< node_ptr > atomic_node_ptr;
142 flag_array_converting = 1, ///< the cell is converting from data node to an array node
143 flag_array_node = 2 ///< the cell is a pointer to an array node
147 array_node * const pParent; ///< parent array node
148 size_t const idxParent; ///< index in parent array node
149 atomic_node_ptr nodes[1]; ///< node array
151 array_node( array_node * parent, size_t idx )
156 array_node() = delete;
157 array_node( array_node const&) = delete;
158 array_node( array_node&& ) = delete;
161 typedef cds::details::Allocator< array_node, node_allocator > cxx_array_node_allocator;
163 typedef multilevel_hashset::details::hash_splitter< hash_type > hash_splitter;
166 size_t head_node_size; // power-of-two
167 size_t head_node_size_log; // log2( head_node_size )
168 size_t array_node_size; // power-of-two
169 size_t array_node_size_log;// log2( array_node_size )
175 /// Bidirectional iterator class
176 template <bool IsConst>
177 class bidirectional_iterator
179 friend class MultiLevelHashSet;
181 array_node * m_pNode; ///< current array node
182 size_t m_idx; ///< current position in m_pNode
183 typename gc::Guard m_guard; ///< HP guard
184 MultiLevelHashSet const* m_set; ///< Hash set
187 static CDS_CONSTEXPR bool const c_bConstantIterator = IsConst;
190 typedef typename std::conditional< IsConst, value_type const*, value_type*>::type value_ptr; ///< Value pointer
191 typedef typename std::conditional< IsConst, value_type const&, value_type&>::type value_ref; ///< Value reference
194 bidirectional_iterator() CDS_NOEXCEPT
200 bidirectional_iterator( bidirectional_iterator const& rhs ) CDS_NOEXCEPT
201 : m_pNode( rhs.m_pNode )
205 m_guard.copy( rhs.m_guard );
208 bidirectional_iterator& operator=(bidirectional_iterator const& rhs) CDS_NOEXCEPT
210 m_pNode = rhs.m_pNode;
213 m_guard.copy( rhs.m_guard );
217 bidirectional_iterator& operator++()
223 bidirectional_iterator& operator--()
229 value_ptr operator ->() const CDS_NOEXCEPT
234 value_ref operator *() const CDS_NOEXCEPT
236 value_ptr p = pointer();
246 template <bool IsConst2>
247 bool operator ==(bidirectional_iterator<IsConst2> const& rhs) const CDS_NOEXCEPT
249 return m_pNode == rhs.m_pNode && m_idx == rhs.m_idx && m_set == rhs.m_set;
252 template <bool IsConst2>
253 bool operator !=(bidirectional_iterator<IsConst2> const& rhs) const CDS_NOEXCEPT
255 return !( *this == rhs );
259 bidirectional_iterator( MultiLevelHashSet& set, array_node * pNode, size_t idx, bool )
265 bidirectional_iterator( MultiLevelHashSet& set, array_node * pNode, size_t idx )
273 value_ptr pointer() const CDS_NOEXCEPT
275 return m_guard.template get<value_type>();
280 assert( m_set != nullptr );
281 assert( m_pNode != nullptr );
283 size_t const arrayNodeSize = m_set->array_node_size();
284 size_t const headSize = m_set->head_size();
285 array_node * pNode = m_pNode;
286 size_t idx = m_idx + 1;
287 size_t nodeSize = m_pNode->pParent? arrayNodeSize : headSize;
290 if ( idx < nodeSize ) {
291 node_ptr slot = pNode->nodes[idx].load( memory_model::memory_order_acquire );
292 if ( slot.bits() == flag_array_node ) {
293 // array node, go down the tree
294 assert( slot.ptr() != nullptr );
295 pNode = to_array( slot.ptr() );
297 nodeSize = arrayNodeSize;
299 else if ( slot.bits() == flag_array_converting ) {
300 // the slot is converting to array node right now - skip the node
306 if ( m_guard.protect( pNode->nodes[idx], [](node_ptr p) -> value_type * { return p.ptr(); }) == slot ) {
317 if ( pNode->pParent ) {
318 idx = pNode->idxParent + 1;
319 pNode = pNode->pParent;
320 nodeSize = pNode->pParent ? arrayNodeSize : headSize;
324 assert( pNode == m_set->m_Head );
325 assert( idx == headSize );
336 assert( m_set != nullptr );
337 assert( m_pNode != nullptr );
339 size_t const arrayNodeSize = m_set->array_node_size();
340 size_t const headSize = m_set->head_size();
341 size_t const endIdx = size_t(0) - 1;
343 array_node * pNode = m_pNode;
344 size_t idx = m_idx - 1;
345 size_t nodeSize = m_pNode->pParent? arrayNodeSize : headSize;
348 if ( idx != endIdx ) {
349 node_ptr slot = pNode->nodes[idx].load( memory_model::memory_order_acquire );
350 if ( slot.bits() == flag_array_node ) {
351 // array node, go down the tree
352 assert( slot.ptr() != nullptr );
353 pNode = to_array( slot.ptr() );
354 nodeSize = arrayNodeSize;
357 else if ( slot.bits() == flag_array_converting ) {
358 // the slot is converting to array node right now - skip the node
364 if ( m_guard.protect( pNode->nodes[idx], [](node_ptr p) -> value_type * { return p.ptr(); }) == slot ) {
375 if ( pNode->pParent ) {
376 idx = pNode->idxParent - 1;
377 pNode = pNode->pParent;
378 nodeSize = pNode->pParent ? arrayNodeSize : headSize;
382 assert( pNode == m_set->m_Head );
383 assert( idx == endIdx );
393 /// Reverse bidirectional iterator
394 template <bool IsConst>
395 class reverse_bidirectional_iterator : protected bidirectional_iterator<IsConst>
397 typedef bidirectional_iterator<IsConst> base_class;
398 friend class MultiLevelHashSet;
401 typedef typename base_class::value_ptr value_ptr;
402 typedef typename base_class::value_ref value_ref;
405 reverse_bidirectional_iterator() CDS_NOEXCEPT
409 reverse_bidirectional_iterator( reverse_bidirectional_iterator const& rhs ) CDS_NOEXCEPT
413 reverse_bidirectional_iterator& operator=( reverse_bidirectional_iterator const& rhs) CDS_NOEXCEPT
415 base_class::operator=( rhs );
419 reverse_bidirectional_iterator& operator++()
421 base_class::backward();
425 reverse_bidirectional_iterator& operator--()
427 base_class::forward();
431 value_ptr operator ->() const CDS_NOEXCEPT
433 return base_class::operator->();
436 value_ref operator *() const CDS_NOEXCEPT
438 return base_class::operator*();
443 base_class::release();
446 template <bool IsConst2>
447 bool operator ==(reverse_bidirectional_iterator<IsConst2> const& rhs) const
449 return base_class::operator==( rhs );
452 template <bool IsConst2>
453 bool operator !=(reverse_bidirectional_iterator<IsConst2> const& rhs)
455 return !( *this == rhs );
459 reverse_bidirectional_iterator( MultiLevelHashSet& set, array_node * pNode, size_t idx )
460 : base_class( set, pNode, idx, false )
462 base_class::backward();
468 #ifdef CDS_DOXYGEN_INVOKED
469 typedef implementation_defined iterator; ///< @ref cds_intrusive_MultilevelHashSet_iterators "bidirectional iterator" type
470 typedef implementation_defined const_iterator; ///< @ref cds_intrusive_MultilevelHashSet_iterators "bidirectional const iterator" type
471 typedef implementation_defined reverse_iterator; ///< @ref cds_intrusive_MultilevelHashSet_iterators "bidirectional reverse iterator" type
472 typedef implementation_defined const_reverse_iterator; ///< @ref cds_intrusive_MultilevelHashSet_iterators "bidirectional reverse const iterator" type
474 typedef bidirectional_iterator<false> iterator;
475 typedef bidirectional_iterator<true> const_iterator;
476 typedef reverse_bidirectional_iterator<false> reverse_iterator;
477 typedef reverse_bidirectional_iterator<true> const_reverse_iterator;
482 metrics const m_Metrics; ///< Metrics
483 array_node * m_Head; ///< Head array
484 item_counter m_ItemCounter; ///< Item counter
485 stat m_Stat; ///< Internal statistics
489 /// Creates empty set
491 @param head_bits: 2<sup>head_bits</sup> specifies the size of head array, minimum is 4.
492 @param array_bits: 2<sup>array_bits</sup> specifies the size of array node, minimum is 2.
494 Equation for \p head_bits and \p array_bits:
496 sizeof(hash_type) * 8 == head_bits + N * array_bits
498 where \p N is multi-level array depth.
500 MultiLevelHashSet( size_t head_bits = 8, size_t array_bits = 4 )
501 : m_Metrics(make_metrics( head_bits, array_bits ))
502 , m_Head( alloc_head_node())
505 /// Destructs the set and frees all data
509 free_array_node( m_Head );
514 The function inserts \p val in the set if it does not contain
515 an item with that hash.
517 Returns \p true if \p val is placed into the set, \p false otherwise.
519 bool insert( value_type& val )
521 return insert( val, [](value_type&) {} );
526 This function is intended for derived non-intrusive containers.
528 The function allows to split creating of new item into two part:
529 - create item with key only
530 - insert new item into the set
531 - if inserting is success, calls \p f functor to initialize \p val.
533 The functor signature is:
535 void func( value_type& val );
537 where \p val is the item inserted.
539 The user-defined functor is called only if the inserting is success.
541 @warning See \ref cds_intrusive_item_creating "insert item troubleshooting".
543 template <typename Func>
544 bool insert( value_type& val, Func f )
546 hash_type const& hash = hash_accessor()( val );
547 hash_splitter splitter( hash );
549 typename gc::Guard guard;
552 size_t nOffset = m_Metrics.head_node_size_log;
553 array_node * pArr = m_Head;
554 size_t nSlot = splitter.cut( m_Metrics.head_node_size_log );
555 assert( nSlot < m_Metrics.head_node_size );
558 node_ptr slot = pArr->nodes[nSlot].load( memory_model::memory_order_acquire );
559 if ( slot.bits() == flag_array_node ) {
560 // array node, go down the tree
561 assert( slot.ptr() != nullptr );
562 nSlot = splitter.cut( m_Metrics.array_node_size_log );
563 assert( nSlot < m_Metrics.array_node_size );
564 pArr = to_array( slot.ptr() );
565 nOffset += m_Metrics.array_node_size_log;
567 else if ( slot.bits() == flag_array_converting ) {
568 // the slot is converting to array node right now
570 m_Stat.onSlotConverting();
574 assert(slot.bits() == 0 );
576 // protect data node by hazard pointer
577 if ( guard.protect( pArr->nodes[nSlot], [](node_ptr p) -> value_type * { return p.ptr(); }) != slot ) {
578 // slot value has been changed - retry
579 m_Stat.onSlotChanged();
581 else if ( slot.ptr() ) {
582 if ( cmp( hash, hash_accessor()( *slot.ptr() )) == 0 ) {
583 // the item with that hash value already exists
584 m_Stat.onInsertFailed();
588 // the slot must be expanded
589 expand_slot( pArr, nSlot, slot, nOffset );
592 // the slot is empty, try to insert data node
594 if ( pArr->nodes[nSlot].compare_exchange_strong( pNull, node_ptr( &val ), memory_model::memory_order_release, atomics::memory_order_relaxed ))
596 // the new data node has been inserted
599 m_Stat.onInsertSuccess();
603 // insert failed - slot has been changed by another thread
605 m_Stat.onInsertRetry();
613 Performs inserting or updating the item with hash value equal to \p val.
614 - If hash value is found then existing item is replaced with \p val, old item is disposed
615 with \p Traits::disposer. Note that the disposer is called by \p GC asynchronously.
616 The function returns <tt> std::pair<true, false> </tt>
617 - If hash value is not found and \p bInsert is \p true then \p val is inserted,
618 the function returns <tt> std::pair<true, true> </tt>
619 - If hash value is not found and \p bInsert is \p false then the set is unchanged,
620 the function returns <tt> std::pair<false, false> </tt>
622 Returns <tt> std::pair<bool, bool> </tt> where \p first is \p true if operation is successfull
623 (i.e. the item has been inserted or updated),
624 \p second is \p true if new item has been added or \p false if the set contains that hash.
626 std::pair<bool, bool> update( value_type& val, bool bInsert = true )
628 return do_update(val, [](value_type&, value_type *) {}, bInsert );
631 /// Unlinks the item \p val from the set
633 The function searches the item \p val in the set and unlink it
634 if it is found and its address is equal to <tt>&val</tt>.
636 The function returns \p true if success and \p false otherwise.
638 bool unlink( value_type const& val )
640 typename gc::Guard guard;
641 auto pred = [&val](value_type const& item) -> bool { return &item == &val; };
642 value_type * p = do_erase( hash_accessor()( val ), guard, std::ref( pred ));
646 /// Deletes the item from the set
648 The function searches \p hash in the set,
649 unlinks the item found, and returns \p true.
650 If that item is not found the function returns \p false.
652 The \ref disposer specified in \p Traits is called by garbage collector \p GC asynchronously.
654 bool erase( hash_type const& hash )
656 return erase(hash, [](value_type const&) {} );
659 /// Deletes the item from the set
661 The function searches \p hash in the set,
662 call \p f functor with item found, and unlinks it from the set.
663 The \ref disposer specified in \p Traits is called
664 by garbage collector \p GC asynchronously.
666 The \p Func interface is
669 void operator()( value_type& item );
673 If \p hash is not found the function returns \p false.
675 template <typename Func>
676 bool erase( hash_type const& hash, Func f )
678 typename gc::Guard guard;
679 value_type * p = do_erase( hash, guard, []( value_type const&) -> bool {return true; } );
681 // p is guarded by HP
689 /// Deletes the item pointed by iterator \p iter
691 Returns \p true if the operation is successful, \p false otherwise.
693 The function does not invalidate the iterator, it remains valid and can be used for further traversing.
695 bool erase_at( iterator const& iter )
697 if ( iter.m_set != this )
699 if ( iter.m_pNode == m_Head && iter.m_idx >= head_size())
701 if ( iter.m_idx >= array_node_size() )
705 node_ptr slot = iter.m_pNode->nodes[iter.m_idx].load( memory_model::memory_order_acquire );
706 if ( slot.bits() == 0 && slot.ptr() == iter.pointer() ) {
707 if ( iter.m_pNode->nodes[iter.m_idx].compare_exchange_strong(slot, node_ptr(nullptr), memory_model::memory_order_acquire, atomics::memory_order_relaxed) ) {
708 // the item is guarded by iterator, so we may retire it safely
709 gc::template retire<disposer>( slot.ptr() );
711 m_Stat.onEraseSuccess();
720 bool erase_at( reverse_iterator const& iter )
722 return erase_at(static_cast<iterator const&>( iter ));
726 /// Extracts the item with specified \p hash
728 The function searches \p hash in the set,
729 unlinks it from the set, and returns an guarded pointer to the item extracted.
730 If \p hash is not found the function returns an empty guarded pointer.
732 The \p disposer specified in \p Traits class' template parameter is called automatically
733 by garbage collector \p GC when returned \ref guarded_ptr object to be destroyed or released.
734 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
738 typedef cds::intrusive::MultiLevelHashSet< your_template_args > my_set;
742 my_set::guarded_ptr gp( theSet.extract( 5 ));
747 // Destructor of gp releases internal HP guard
751 guarded_ptr extract( hash_type const& hash )
755 typename gc::Guard guard;
756 value_type * p = do_erase( hash, guard, []( value_type const&) -> bool {return true;} );
758 // p is guarded by HP
765 /// Finds an item by it's \p hash
767 The function searches the item by \p hash and calls the functor \p f for item found.
768 The interface of \p Func functor is:
771 void operator()( value_type& item );
774 where \p item is the item found.
776 The functor may change non-key fields of \p item. Note that the functor is only guarantee
777 that \p item cannot be disposed during the functor is executing.
778 The functor does not serialize simultaneous access to the set's \p item. If such access is
779 possible you must provide your own synchronization schema on item level to prevent unsafe item modifications.
781 The function returns \p true if \p hash is found, \p false otherwise.
783 template <typename Func>
784 bool find( hash_type const& hash, Func f )
786 typename gc::Guard guard;
787 value_type * p = search( hash, guard );
789 // p is guarded by HP
797 /// Checks whether the set contains \p hash
799 The function searches the item by its \p hash
800 and returns \p true if it is found, or \p false otherwise.
802 bool contains( hash_type const& hash )
804 return find( hash, [](value_type&) {} );
807 /// Finds an item by it's \p hash and returns the item found
809 The function searches the item by its \p hash
810 and returns the guarded pointer to the item found.
811 If \p hash is not found the function returns an empty \p guarded_ptr.
813 @note Each \p guarded_ptr object uses one GC's guard which can be limited resource.
817 typedef cds::intrusive::MultiLevelHashSet< your_template_params > my_set;
821 my_set::guarded_ptr gp( theSet.get( 5 ));
822 if ( theSet.get( 5 )) {
826 // Destructor of guarded_ptr releases internal HP guard
830 guarded_ptr get( hash_type const& hash )
834 typename gc::Guard guard;
835 gp.reset( search( hash, guard ));
840 /// Clears the set (non-atomic)
842 The function unlink all data node from the set.
843 The function is not atomic but is thread-safe.
844 After \p %clear() the set may not be empty because another threads may insert items.
846 For each item the \p disposer is called after unlinking.
850 clear_array( m_Head, head_size() );
853 /// Checks if the set is empty
855 Emptiness is checked by item counting: if item count is zero then the set is empty.
856 Thus, the correct item counting feature is an important part of the set implementation.
863 /// Returns item count in the set
866 return m_ItemCounter;
869 /// Returns const reference to internal statistics
870 stat const& statistics() const
875 /// Returns the size of head node
876 size_t head_size() const
878 return m_Metrics.head_node_size;
881 /// Returns the size of the array node
882 size_t array_node_size() const
884 return m_Metrics.array_node_size;
888 ///@name Thread-safe iterators
889 /** @anchor cds_intrusive_MultilevelHashSet_iterators
890 The set supports thread-safe iterators: you may iterate over the set in multi-threaded environment.
\r
891 It is guaranteed that the iterators will remain valid even if another thread deletes the node the iterator points to:
\r
892 Hazard Pointer embedded into the iterator object protects the node from physical reclamation.
\r
894 @note Since the iterator object contains hazard pointer that is a thread-local resource,
\r
895 the iterator should not be passed to another thread.
\r
897 Each iterator object supports the common interface:
\r
898 - dereference operators:
\r
900 value_type [const] * operator ->() noexcept
\r
901 value_type [const] & operator *() noexcept
\r
903 - pre-increment and pre-decrement. Post-operators is not supported
\r
904 - equality operators <tt>==</tt> and <tt>!=</tt>.
\r
905 Iterators are equal iff they point to the same cell of the same array node.
906 Note that for two iterators \p it1 and \p it2, the conditon <tt> it1 == it2 </tt>
907 does not entail <tt> &(*it1) == &(*it2) </tt>: welcome to concurrent containers
908 - helper member function \p release() that clears internal hazard pointer.
\r
909 After \p release() call the iterator points to \p nullptr but it still remain valid: further iterating is possible.
913 /// Returns an iterator to the beginning of the set
916 return iterator( *this, m_Head, size_t(0) - 1 );
919 /// Returns an const iterator to the beginning of the set
920 const_iterator begin() const
922 return const_iterator( *this, m_Head, size_t(0) - 1 );
925 /// Returns an const iterator to the beginning of the set
926 const_iterator cbegin()
928 return const_iterator( *this, m_Head, size_t(0) - 1 );
931 /// Returns an iterator to the element following the last element of the set. This element acts as a placeholder; attempting to access it results in undefined behavior.
934 return iterator( *this, m_Head, head_size() - 1 );
937 /// Returns a const iterator to the element following the last element of the set. This element acts as a placeholder; attempting to access it results in undefined behavior.
938 const_iterator end() const
940 return const_iterator( *this, m_Head, head_size() - 1 );
943 /// Returns a const iterator to the element following the last element of the set. This element acts as a placeholder; attempting to access it results in undefined behavior.
944 const_iterator cend()
946 return const_iterator( *this, m_Head, head_size() - 1 );
949 /// Returns a reverse iterator to the first element of the reversed set
950 reverse_iterator rbegin()
952 return reverse_iterator( *this, m_Head, head_size() );
955 /// Returns a const reverse iterator to the first element of the reversed set
956 const_reverse_iterator rbegin() const
958 return const_reverse_iterator( *this, m_Head, head_size() );
961 /// Returns a const reverse iterator to the first element of the reversed set
962 const_reverse_iterator crbegin()
964 return const_reverse_iterator( *this, m_Head, head_size() );
967 /// Returns a reverse iterator to the element following the last element of the reversed set
969 It corresponds to the element preceding the first element of the non-reversed container.
970 This element acts as a placeholder, attempting to access it results in undefined behavior.
972 reverse_iterator rend()
974 return reverse_iterator( *this, m_Head, 0 );
977 /// Returns a const reverse iterator to the element following the last element of the reversed set
979 It corresponds to the element preceding the first element of the non-reversed container.
980 This element acts as a placeholder, attempting to access it results in undefined behavior.
982 const_reverse_iterator rend() const
984 return const_reverse_iterator( *this, m_Head, 0 );
987 /// Returns a const reverse iterator to the element following the last element of the reversed set
989 It corresponds to the element preceding the first element of the non-reversed container.
990 This element acts as a placeholder, attempting to access it results in undefined behavior.
992 const_reverse_iterator crend()
994 return const_reverse_iterator( *this, m_Head, 0 );
1000 static metrics make_metrics( size_t head_bits, size_t array_bits )
1002 size_t const hash_bits = sizeof( hash_type ) * 8;
1004 if ( array_bits < 2 )
1006 if ( head_bits < 4 )
1008 if ( head_bits > hash_bits )
1009 head_bits = hash_bits;
1010 if ( (hash_bits - head_bits) % array_bits != 0 )
1011 head_bits += (hash_bits - head_bits) % array_bits;
1013 assert( (hash_bits - head_bits) % array_bits == 0 );
1016 m.head_node_size_log = head_bits;
1017 m.head_node_size = size_t(1) << head_bits;
1018 m.array_node_size_log = array_bits;
1019 m.array_node_size = size_t(1) << array_bits;
1023 array_node * alloc_head_node() const
1025 return alloc_array_node( head_size(), nullptr, 0 );
1028 array_node * alloc_array_node( array_node * pParent, size_t idxParent ) const
1030 return alloc_array_node( array_node_size(), pParent, idxParent );
1033 static array_node * alloc_array_node( size_t nSize, array_node * pParent, size_t idxParent )
1035 array_node * pNode = cxx_array_node_allocator().NewBlock( sizeof(array_node) + sizeof(atomic_node_ptr) * (nSize - 1), pParent, idxParent );
1036 for ( atomic_node_ptr * p = pNode->nodes, *pEnd = pNode->nodes + nSize; p < pEnd; ++p )
1037 p->store( node_ptr(), memory_model::memory_order_release );
1041 static void free_array_node( array_node * parr )
1043 cxx_array_node_allocator().Delete( parr );
1048 // The function is not thread-safe. For use in dtor only
1052 // Destroy all array nodes
1053 destroy_array_nodes( m_Head, head_size());
1056 void destroy_array_nodes( array_node * pArr, size_t nSize )
1058 for ( atomic_node_ptr * p = pArr->nodes, *pLast = pArr->nodes + nSize; p != pLast; ++p ) {
1059 node_ptr slot = p->load( memory_model::memory_order_acquire );
1060 if ( slot.bits() == flag_array_node ) {
1061 destroy_array_nodes(to_array(slot.ptr()), array_node_size());
1062 free_array_node( to_array(slot.ptr()));
1063 p->store(node_ptr(), memory_model::memory_order_relaxed );
1068 void clear_array( array_node * pArrNode, size_t nSize )
1073 for ( atomic_node_ptr * pArr = pArrNode->nodes, *pLast = pArr + nSize; pArr != pLast; ++pArr ) {
1075 node_ptr slot = pArr->load( memory_model::memory_order_acquire );
1076 if ( slot.bits() == flag_array_node ) {
1077 // array node, go down the tree
1078 assert( slot.ptr() != nullptr );
1079 clear_array( to_array( slot.ptr()), array_node_size() );
1082 else if ( slot.bits() == flag_array_converting ) {
1083 // the slot is converting to array node right now
1084 while ( (slot = pArr->load(memory_model::memory_order_acquire)).bits() == flag_array_converting ) {
1086 m_Stat.onSlotConverting();
1090 assert( slot.ptr() != nullptr );
1091 assert(slot.bits() == flag_array_node );
1092 clear_array( to_array( slot.ptr()), array_node_size() );
1097 if ( pArr->compare_exchange_strong( slot, node_ptr(), memory_model::memory_order_acquire, atomics::memory_order_relaxed )) {
1099 gc::template retire<disposer>( slot.ptr() );
1101 m_Stat.onEraseSuccess();
1114 converter( value_type * p )
1118 converter( array_node * p )
1123 static array_node * to_array( value_type * p )
1125 return converter( p ).pArr;
1127 static value_type * to_node( array_node * p )
1129 return converter( p ).pData;
1132 bool expand_slot( array_node * pParent, size_t idxParent, node_ptr current, size_t nOffset )
1134 assert( current.bits() == 0 );
1135 assert( current.ptr() );
1137 size_t idx = hash_splitter(hash_accessor()(*current.ptr()), nOffset).cut( m_Metrics.array_node_size_log );
1138 array_node * pArr = alloc_array_node( pParent, idxParent );
1140 node_ptr cur(current.ptr());
1141 atomic_node_ptr& slot = pParent->nodes[idxParent];
1142 if ( !slot.compare_exchange_strong( cur, cur | flag_array_converting, memory_model::memory_order_release, atomics::memory_order_relaxed ))
1144 m_Stat.onExpandNodeFailed();
1145 free_array_node( pArr );
1149 pArr->nodes[idx].store( current, memory_model::memory_order_release );
1151 cur = cur | flag_array_converting;
1153 slot.compare_exchange_strong( cur, node_ptr( to_node( pArr ), flag_array_node ), memory_model::memory_order_release, atomics::memory_order_relaxed )
1156 m_Stat.onArrayNodeCreated();
1163 value_type * search( hash_type const& hash, typename gc::Guard& guard )
1165 hash_splitter splitter( hash );
1166 hash_comparator cmp;
1169 array_node * pArr = m_Head;
1170 size_t nSlot = splitter.cut( m_Metrics.head_node_size_log );
1171 assert( nSlot < m_Metrics.head_node_size );
1174 node_ptr slot = pArr->nodes[nSlot].load( memory_model::memory_order_acquire );
1175 if ( slot.bits() == flag_array_node ) {
1176 // array node, go down the tree
1177 assert( slot.ptr() != nullptr );
1178 nSlot = splitter.cut( m_Metrics.array_node_size_log );
1179 assert( nSlot < m_Metrics.array_node_size );
1180 pArr = to_array( slot.ptr() );
1182 else if ( slot.bits() == flag_array_converting ) {
1183 // the slot is converting to array node right now
1185 m_Stat.onSlotConverting();
1189 assert(slot.bits() == 0 );
1191 // protect data node by hazard pointer
1192 if ( guard.protect( pArr->nodes[nSlot], [](node_ptr p) -> value_type * { return p.ptr(); }) != slot ) {
1193 // slot value has been changed - retry
1194 m_Stat.onSlotChanged();
1196 else if ( slot.ptr() && cmp( hash, hash_accessor()( *slot.ptr() )) == 0 ) {
1198 m_Stat.onFindSuccess();
1201 m_Stat.onFindFailed();
1207 template <typename Predicate>
1208 value_type * do_erase( hash_type const& hash, typename gc::Guard& guard, Predicate pred )
1210 hash_splitter splitter( hash );
1211 hash_comparator cmp;
1214 array_node * pArr = m_Head;
1215 size_t nSlot = splitter.cut( m_Metrics.head_node_size_log );
1216 assert( nSlot < m_Metrics.head_node_size );
1219 node_ptr slot = pArr->nodes[nSlot].load( memory_model::memory_order_acquire );
1220 if ( slot.bits() == flag_array_node ) {
1221 // array node, go down the tree
1222 assert( slot.ptr() != nullptr );
1223 nSlot = splitter.cut( m_Metrics.array_node_size_log );
1224 assert( nSlot < m_Metrics.array_node_size );
1225 pArr = to_array( slot.ptr() );
1227 else if ( slot.bits() == flag_array_converting ) {
1228 // the slot is converting to array node right now
1230 m_Stat.onSlotConverting();
1234 assert(slot.bits() == 0 );
1236 // protect data node by hazard pointer
1237 if ( guard.protect( pArr->nodes[nSlot], [](node_ptr p) -> value_type * { return p.ptr(); }) != slot ) {
1238 // slot value has been changed - retry
1239 m_Stat.onSlotChanged();
1241 else if ( slot.ptr() ) {
1242 if ( cmp( hash, hash_accessor()( *slot.ptr() )) == 0 && pred( *slot.ptr() )) {
1243 // item found - replace it with nullptr
1244 if ( pArr->nodes[nSlot].compare_exchange_strong(slot, node_ptr(nullptr), memory_model::memory_order_acquire, atomics::memory_order_relaxed) ) {
1245 // slot is guarded by HP
1246 gc::template retire<disposer>( slot.ptr() );
1248 m_Stat.onEraseSuccess();
1252 m_Stat.onEraseRetry();
1255 m_Stat.onEraseFailed();
1259 // the slot is empty
1260 m_Stat.onEraseFailed();
1267 template <typename Func>
1268 std::pair<bool, bool> do_update( value_type& val, Func f, bool bInsert = true )
1270 hash_type const& hash = hash_accessor()( val );
1271 hash_splitter splitter( hash );
1272 hash_comparator cmp;
1273 typename gc::GuardArray<2> guards;
1276 array_node * pArr = m_Head;
1277 size_t nSlot = splitter.cut( m_Metrics.head_node_size_log );
1278 assert( nSlot < m_Metrics.head_node_size );
1279 size_t nOffset = m_Metrics.head_node_size_log;
1281 guards.assign( 1, &val );
1284 node_ptr slot = pArr->nodes[nSlot].load( memory_model::memory_order_acquire );
1285 if ( slot.bits() == flag_array_node ) {
1286 // array node, go down the tree
1287 assert( slot.ptr() != nullptr );
1288 nSlot = splitter.cut( m_Metrics.array_node_size_log );
1289 assert( nSlot < m_Metrics.array_node_size );
1290 pArr = to_array( slot.ptr() );
1291 nOffset += m_Metrics.array_node_size_log;
1293 else if ( slot.bits() == flag_array_converting ) {
1294 // the slot is converting to array node right now
1296 m_Stat.onSlotConverting();
1300 assert(slot.bits() == 0 );
1302 // protect data node by hazard pointer
1303 if ( guards.protect( 0, pArr->nodes[nSlot], [](node_ptr p) -> value_type * { return p.ptr(); }) != slot ) {
1304 // slot value has been changed - retry
1305 m_Stat.onSlotChanged();
1307 else if ( slot.ptr() ) {
1308 if ( cmp( hash, hash_accessor()( *slot.ptr() )) == 0 ) {
1309 // the item with that hash value already exists
1310 // Replace it with val
1311 if ( slot.ptr() == &val ) {
1312 m_Stat.onUpdateExisting();
1313 return std::make_pair( true, false );
1316 if ( pArr->nodes[nSlot].compare_exchange_strong( slot, node_ptr( &val ), memory_model::memory_order_release, atomics::memory_order_relaxed )) {
1317 // slot can be disposed
1318 f( val, slot.ptr() );
1319 gc::template retire<disposer>( slot.ptr() );
1320 m_Stat.onUpdateExisting();
1321 return std::make_pair( true, false );
1324 m_Stat.onUpdateRetry();
1328 // the slot must be expanded
1329 expand_slot( pArr, nSlot, slot, nOffset );
1332 // the slot is empty, try to insert data node
1335 if ( pArr->nodes[nSlot].compare_exchange_strong( pNull, node_ptr( &val ), memory_model::memory_order_release, atomics::memory_order_relaxed ))
1337 // the new data node has been inserted
1340 m_Stat.onUpdateNew();
1341 return std::make_pair( true, true );
1345 m_Stat.onUpdateFailed();
1346 return std::make_pair( false, false );
1349 // insert failed - slot has been changed by another thread
1351 m_Stat.onUpdateRetry();
1358 }} // namespace cds::intrusive
1363 template <class GC, typename T, typename Traits>
1364 struct iterator_traits< typename cds::intrusive::MultiLevelHashSet< GC, T, Traits >::iterator >
1366 typedef typename cds::intrusive::MultiLevelHashSet< GC, T, Traits >::iterator iterator_class;
1368 // difference_type is not applicable for that iterator
1369 // typedef ??? difference_type
1370 typedef T value_type;
1371 typedef typename iterator_class::value_ptr pointer;
1372 typedef typename iterator_class::value_ref reference;
1373 typedef bidirectional_iterator_tag iterator_category;
1376 template <class GC, typename T, typename Traits>
1377 struct iterator_traits< typename cds::intrusive::MultiLevelHashSet< GC, T, Traits >::const_iterator >
1379 typedef typename cds::intrusive::MultiLevelHashSet< GC, T, Traits >::const_iterator iterator_class;
1381 // difference_type is not applicable for that iterator
1382 // typedef ??? difference_type
1383 typedef T value_type;
1384 typedef typename iterator_class::value_ptr pointer;
1385 typedef typename iterator_class::value_ref reference;
1386 typedef bidirectional_iterator_tag iterator_category;
1392 #endif // #ifndef CDSLIB_INTRUSIVE_IMPL_MULTILEVEL_HASHSET_H