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
41 with that key; it is a simple struct holding two variables. A \p dataNode in the multi-level array could be marked.
42 A \p markedDataNode refers to a pointer to a \p dataNode that has been bitmarked at the least significant bit (LSB)
43 of the pointer to the node. This signifies that this \p dataNode is contended. An expansion must occur at this node;
44 any thread that sees this \p markedDataNode will try to replace it with an \p arrayNode; which is a position that holds
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
46 on the second-least significant bit.
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
49 called \p head. The length of the \p head memory array is unique, whereas every other \p arrayNode has a uniform length;
50 a normal \p arrayNode has a fixed power-of-two length equal to the binary logarithm of a variable called \p arrayLength.
51 The maximum depth of the tree, \p maxDepth, is the maximum number of pointers that must be followed to reach any node.
52 We define \p currentDepth as the number of memory arrays that we need to traverse to reach the \p arrayNode on which
53 we need to operate; this is initially one, because of \p head.
55 That approach to the structure of the hash set uses an extensible hashing scheme; <b> the hash value is treated as a bit
56 string</b> and rehash incrementally.
58 @note Two important things you should keep in mind when you're using \p %MultiLevelHashSet:
59 - all keys must be fixed-size. It means that you cannot use \p std::string as a key for \p %MultiLevelHashSet.
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>,
61 <a href="https://en.wikipedia.org/wiki/MurmurHash">MurmurHash</a>, <a href="https://en.wikipedia.org/wiki/CityHash">CityHash</a>
62 or its successor <a href="https://code.google.com/p/farmhash/">FarmHash</a> and so on, which
63 converts variable-length strings to fixed-length bit-strings, and use that hash as a key in \p %MultiLevelHashSet.
64 - \p %MultiLevelHashSet uses a perfect hashing. It means that if two different keys, for example, of type \p std::string,
65 have identical hash then you cannot insert both that keys in the set. \p %MultiLevelHashSet does not maintain the key,
66 it maintains its fixed-size hash value.
68 The set supports @ref cds_intrusive_MultilevelHashSet_iterators "bidirectional thread-safe iterators".
71 - \p GC - safe memory reclamation schema. Can be \p gc::HP, \p gc::DHP or one of \ref cds_urcu_type "RCU type"
72 - \p T - a value type to be stored in the set
73 - \p Traits - type traits, the structure based on \p multilevel_hashset::traits or result of \p multilevel_hashset::make_traits metafunction.
74 \p Traits is the mandatory argument because it has one mandatory type - an @ref multilevel_hashset::traits::hash_accessor "accessor"
75 to hash value of \p T. The set algorithm does not calculate that hash value.
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;
170 friend class MultiLevelHashSet;
173 array_node * m_pNode; ///< current array node
174 size_t m_idx; ///< current position in m_pNode
175 typename gc::Guard m_guard; ///< HP guard
176 MultiLevelHashSet const* m_set; ///< Hash set
179 iterator_base() CDS_NOEXCEPT
185 iterator_base( iterator_base const& rhs ) CDS_NOEXCEPT
186 : m_pNode( rhs.m_pNode )
190 m_guard.copy( rhs.m_guard );
193 iterator_base& operator=(iterator_base const& rhs) CDS_NOEXCEPT
195 m_pNode = rhs.m_pNode;
198 m_guard.copy( rhs.m_guard );
202 iterator_base& operator++()
208 iterator_base& operator--()
219 bool operator ==(iterator_base const& rhs) const CDS_NOEXCEPT
221 return m_pNode == rhs.m_pNode && m_idx == rhs.m_idx && m_set == rhs.m_set;
224 bool operator !=(iterator_base const& rhs) const CDS_NOEXCEPT
226 return !( *this == rhs );
230 iterator_base( MultiLevelHashSet const& set, array_node * pNode, size_t idx, bool )
236 iterator_base( MultiLevelHashSet const& set, array_node * pNode, size_t idx )
244 value_type * pointer() const CDS_NOEXCEPT
246 return m_guard.template get<value_type>();
251 assert( m_set != nullptr );
252 assert( m_pNode != nullptr );
254 size_t const arrayNodeSize = m_set->array_node_size();
255 size_t const headSize = m_set->head_size();
256 array_node * pNode = m_pNode;
257 size_t idx = m_idx + 1;
258 size_t nodeSize = m_pNode->pParent? arrayNodeSize : headSize;
261 if ( idx < nodeSize ) {
262 node_ptr slot = pNode->nodes[idx].load( memory_model::memory_order_acquire );
263 if ( slot.bits() == flag_array_node ) {
264 // array node, go down the tree
265 assert( slot.ptr() != nullptr );
266 pNode = to_array( slot.ptr() );
268 nodeSize = arrayNodeSize;
270 else if ( slot.bits() == flag_array_converting ) {
271 // the slot is converting to array node right now - skip the node
277 if ( m_guard.protect( pNode->nodes[idx], [](node_ptr p) -> value_type * { return p.ptr(); }) == slot ) {
288 if ( pNode->pParent ) {
289 idx = pNode->idxParent + 1;
290 pNode = pNode->pParent;
291 nodeSize = pNode->pParent ? arrayNodeSize : headSize;
295 assert( pNode == m_set->m_Head );
296 assert( idx == headSize );
307 assert( m_set != nullptr );
308 assert( m_pNode != nullptr );
310 size_t const arrayNodeSize = m_set->array_node_size();
311 size_t const headSize = m_set->head_size();
312 size_t const endIdx = size_t(0) - 1;
314 array_node * pNode = m_pNode;
315 size_t idx = m_idx - 1;
316 size_t nodeSize = m_pNode->pParent? arrayNodeSize : headSize;
319 if ( idx != endIdx ) {
320 node_ptr slot = pNode->nodes[idx].load( memory_model::memory_order_acquire );
321 if ( slot.bits() == flag_array_node ) {
322 // array node, go down the tree
323 assert( slot.ptr() != nullptr );
324 pNode = to_array( slot.ptr() );
325 nodeSize = arrayNodeSize;
328 else if ( slot.bits() == flag_array_converting ) {
329 // the slot is converting to array node right now - skip the node
335 if ( m_guard.protect( pNode->nodes[idx], [](node_ptr p) -> value_type * { return p.ptr(); }) == slot ) {
346 if ( pNode->pParent ) {
347 idx = pNode->idxParent - 1;
348 pNode = pNode->pParent;
349 nodeSize = pNode->pParent ? arrayNodeSize : headSize;
353 assert( pNode == m_set->m_Head );
354 assert( idx == endIdx );
364 template <class Iterator>
365 Iterator init_begin() const
367 return Iterator( *this, m_Head, size_t(0) - 1 );
370 template <class Iterator>
371 Iterator init_end() const
373 return Iterator( *this, m_Head, head_size(), false );
376 template <class Iterator>
377 Iterator init_rbegin() const
379 return Iterator( *this, m_Head, head_size() );
382 template <class Iterator>
383 Iterator init_rend() const
385 return Iterator( *this, m_Head, size_t(0) - 1, false );
388 /// Bidirectional iterator class
389 template <bool IsConst>
390 class bidirectional_iterator: protected iterator_base
392 friend class MultiLevelHashSet;
395 static CDS_CONSTEXPR bool const c_bConstantIterator = IsConst;
398 typedef typename std::conditional< IsConst, value_type const*, value_type*>::type value_ptr; ///< Value pointer
399 typedef typename std::conditional< IsConst, value_type const&, value_type&>::type value_ref; ///< Value reference
402 bidirectional_iterator() CDS_NOEXCEPT
405 bidirectional_iterator( bidirectional_iterator const& rhs ) CDS_NOEXCEPT
406 : iterator_base( rhs )
409 bidirectional_iterator& operator=(bidirectional_iterator const& rhs) CDS_NOEXCEPT
411 iterator_base::operator=( rhs );
415 bidirectional_iterator& operator++()
417 iterator_base::operator++();
421 bidirectional_iterator& operator--()
423 iterator_base::operator--();
427 value_ptr operator ->() const CDS_NOEXCEPT
429 return iterator_base::pointer();
432 value_ref operator *() const CDS_NOEXCEPT
434 value_ptr p = iterator_base::pointer();
441 iterator_base::release();
444 template <bool IsConst2>
445 bool operator ==(bidirectional_iterator<IsConst2> const& rhs) const CDS_NOEXCEPT
447 return iterator_base::operator==( rhs );
450 template <bool IsConst2>
451 bool operator !=(bidirectional_iterator<IsConst2> const& rhs) const CDS_NOEXCEPT
453 return !( *this == rhs );
457 bidirectional_iterator( MultiLevelHashSet& set, array_node * pNode, size_t idx, bool )
458 : iterator_base( set, pNode, idx, false )
461 bidirectional_iterator( MultiLevelHashSet& set, array_node * pNode, size_t idx )
462 : iterator_base( set, pNode, idx )
466 /// Reverse bidirectional iterator
467 template <bool IsConst>
468 class reverse_bidirectional_iterator : public iterator_base
470 friend class MultiLevelHashSet;
473 typedef typename std::conditional< IsConst, value_type const*, value_type*>::type value_ptr; ///< Value pointer
474 typedef typename std::conditional< IsConst, value_type const&, value_type&>::type value_ref; ///< Value reference
477 reverse_bidirectional_iterator() CDS_NOEXCEPT
481 reverse_bidirectional_iterator( reverse_bidirectional_iterator const& rhs ) CDS_NOEXCEPT
482 : iterator_base( rhs )
485 reverse_bidirectional_iterator& operator=( reverse_bidirectional_iterator const& rhs) CDS_NOEXCEPT
487 iterator_base::operator=( rhs );
491 reverse_bidirectional_iterator& operator++()
493 iterator_base::operator--();
497 reverse_bidirectional_iterator& operator--()
499 iterator_base::operator++();
503 value_ptr operator ->() const CDS_NOEXCEPT
505 return iterator_base::pointer();
508 value_ref operator *() const CDS_NOEXCEPT
510 value_ptr p = iterator_base::pointer();
517 iterator_base::release();
520 template <bool IsConst2>
521 bool operator ==(reverse_bidirectional_iterator<IsConst2> const& rhs) const
523 return iterator_base::operator==( rhs );
526 template <bool IsConst2>
527 bool operator !=(reverse_bidirectional_iterator<IsConst2> const& rhs)
529 return !( *this == rhs );
533 reverse_bidirectional_iterator( MultiLevelHashSet& set, array_node * pNode, size_t idx, bool )
534 : iterator_base( set, pNode, idx, false )
537 reverse_bidirectional_iterator( MultiLevelHashSet& set, array_node * pNode, size_t idx )
538 : iterator_base( set, pNode, idx, false )
540 iterator_base::backward();
546 #ifdef CDS_DOXYGEN_INVOKED
547 typedef implementation_defined iterator; ///< @ref cds_intrusive_MultilevelHashSet_iterators "bidirectional iterator" type
548 typedef implementation_defined const_iterator; ///< @ref cds_intrusive_MultilevelHashSet_iterators "bidirectional const iterator" type
549 typedef implementation_defined reverse_iterator; ///< @ref cds_intrusive_MultilevelHashSet_iterators "bidirectional reverse iterator" type
550 typedef implementation_defined const_reverse_iterator; ///< @ref cds_intrusive_MultilevelHashSet_iterators "bidirectional reverse const iterator" type
552 typedef bidirectional_iterator<false> iterator;
553 typedef bidirectional_iterator<true> const_iterator;
554 typedef reverse_bidirectional_iterator<false> reverse_iterator;
555 typedef reverse_bidirectional_iterator<true> const_reverse_iterator;
560 multilevel_hashset::details::metrics const m_Metrics; ///< Metrics
561 array_node * m_Head; ///< Head array
562 item_counter m_ItemCounter; ///< Item counter
563 stat m_Stat; ///< Internal statistics
567 /// Creates empty set
569 @param head_bits: 2<sup>head_bits</sup> specifies the size of head array, minimum is 4.
570 @param array_bits: 2<sup>array_bits</sup> specifies the size of array node, minimum is 2.
572 Equation for \p head_bits and \p array_bits:
574 sizeof(hash_type) * 8 == head_bits + N * array_bits
576 where \p N is multi-level array depth.
578 MultiLevelHashSet( size_t head_bits = 8, size_t array_bits = 4 )
579 : m_Metrics( multilevel_hashset::details::metrics::make( head_bits, array_bits, sizeof(hash_type)))
580 , m_Head( alloc_head_node())
583 /// Destructs the set and frees all data
587 free_array_node( m_Head );
592 The function inserts \p val in the set if it does not contain
593 an item with that hash.
595 Returns \p true if \p val is placed into the set, \p false otherwise.
597 bool insert( value_type& val )
599 return insert( val, [](value_type&) {} );
604 This function is intended for derived non-intrusive containers.
606 The function allows to split creating of new item into two part:
607 - create item with key only
608 - insert new item into the set
609 - if inserting is success, calls \p f functor to initialize \p val.
611 The functor signature is:
613 void func( value_type& val );
615 where \p val is the item inserted.
617 The user-defined functor is called only if the inserting is success.
619 @warning See \ref cds_intrusive_item_creating "insert item troubleshooting".
621 template <typename Func>
622 bool insert( value_type& val, Func f )
624 hash_type const& hash = hash_accessor()( val );
625 hash_splitter splitter( hash );
627 typename gc::Guard guard;
630 size_t nOffset = m_Metrics.head_node_size_log;
631 array_node * pArr = m_Head;
632 size_t nSlot = splitter.cut( m_Metrics.head_node_size_log );
633 assert( nSlot < m_Metrics.head_node_size );
637 node_ptr slot = pArr->nodes[nSlot].load( memory_model::memory_order_acquire );
638 if ( slot.bits() == flag_array_node ) {
639 // array node, go down the tree
640 assert( slot.ptr() != nullptr );
641 nSlot = splitter.cut( m_Metrics.array_node_size_log );
642 assert( nSlot < m_Metrics.array_node_size );
643 pArr = to_array( slot.ptr() );
644 nOffset += m_Metrics.array_node_size_log;
647 else if ( slot.bits() == flag_array_converting ) {
648 // the slot is converting to array node right now
650 m_Stat.onSlotConverting();
654 assert(slot.bits() == 0 );
656 // protect data node by hazard pointer
657 if ( guard.protect( pArr->nodes[nSlot], [](node_ptr p) -> value_type * { return p.ptr(); }) != slot ) {
658 // slot value has been changed - retry
659 m_Stat.onSlotChanged();
661 else if ( slot.ptr() ) {
662 if ( cmp( hash, hash_accessor()( *slot.ptr() )) == 0 ) {
663 // the item with that hash value already exists
664 m_Stat.onInsertFailed();
668 // the slot must be expanded
669 expand_slot( pArr, nSlot, slot, nOffset );
672 // the slot is empty, try to insert data node
674 if ( pArr->nodes[nSlot].compare_exchange_strong( pNull, node_ptr( &val ), memory_model::memory_order_release, atomics::memory_order_relaxed ))
676 // the new data node has been inserted
679 m_Stat.onInsertSuccess();
680 m_Stat.height( nHeight );
684 // insert failed - slot has been changed by another thread
686 m_Stat.onInsertRetry();
694 Performs inserting or updating the item with hash value equal to \p val.
695 - If hash value is found then existing item is replaced with \p val, old item is disposed
696 with \p Traits::disposer. Note that the disposer is called by \p GC asynchronously.
697 The function returns <tt> std::pair<true, false> </tt>
698 - If hash value is not found and \p bInsert is \p true then \p val is inserted,
699 the function returns <tt> std::pair<true, true> </tt>
700 - If hash value is not found and \p bInsert is \p false then the set is unchanged,
701 the function returns <tt> std::pair<false, false> </tt>
703 Returns <tt> std::pair<bool, bool> </tt> where \p first is \p true if operation is successfull
704 (i.e. the item has been inserted or updated),
705 \p second is \p true if new item has been added or \p false if the set contains that hash.
707 std::pair<bool, bool> update( value_type& val, bool bInsert = true )
709 return do_update(val, [](value_type&, value_type *) {}, bInsert );
712 /// Unlinks the item \p val from the set
714 The function searches the item \p val in the set and unlink it
715 if it is found and its address is equal to <tt>&val</tt>.
717 The function returns \p true if success and \p false otherwise.
719 bool unlink( value_type const& val )
721 typename gc::Guard guard;
722 auto pred = [&val](value_type const& item) -> bool { return &item == &val; };
723 value_type * p = do_erase( hash_accessor()( val ), guard, std::ref( pred ));
727 /// Deletes the item from the set
729 The function searches \p hash in the set,
730 unlinks the item found, and returns \p true.
731 If that item is not found the function returns \p false.
733 The \ref disposer specified in \p Traits is called by garbage collector \p GC asynchronously.
735 bool erase( hash_type const& hash )
737 return erase(hash, [](value_type const&) {} );
740 /// Deletes the item from the set
742 The function searches \p hash in the set,
743 call \p f functor with item found, and unlinks it from the set.
744 The \ref disposer specified in \p Traits is called
745 by garbage collector \p GC asynchronously.
747 The \p Func interface is
750 void operator()( value_type& item );
754 If \p hash is not found the function returns \p false.
756 template <typename Func>
757 bool erase( hash_type const& hash, Func f )
759 typename gc::Guard guard;
760 value_type * p = do_erase( hash, guard, []( value_type const&) -> bool {return true; } );
762 // p is guarded by HP
770 /// Deletes the item pointed by iterator \p iter
772 Returns \p true if the operation is successful, \p false otherwise.
774 The function does not invalidate the iterator, it remains valid and can be used for further traversing.
776 bool erase_at( iterator const& iter )
778 return do_erase_at( iter );
781 bool erase_at( reverse_iterator const& iter )
783 return do_erase_at( iter );
787 /// Extracts the item with specified \p hash
789 The function searches \p hash in the set,
790 unlinks it from the set, and returns an guarded pointer to the item extracted.
791 If \p hash is not found the function returns an empty guarded pointer.
793 The \p disposer specified in \p Traits class' template parameter is called automatically
794 by garbage collector \p GC when returned \ref guarded_ptr object to be destroyed or released.
795 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
799 typedef cds::intrusive::MultiLevelHashSet< your_template_args > my_set;
803 my_set::guarded_ptr gp( theSet.extract( 5 ));
808 // Destructor of gp releases internal HP guard
812 guarded_ptr extract( hash_type const& hash )
816 typename gc::Guard guard;
817 value_type * p = do_erase( hash, guard, []( value_type const&) -> bool {return true;} );
819 // p is guarded by HP
826 /// Finds an item by it's \p hash
828 The function searches the item by \p hash and calls the functor \p f for item found.
829 The interface of \p Func functor is:
832 void operator()( value_type& item );
835 where \p item is the item found.
837 The functor may change non-key fields of \p item. Note that the functor is only guarantee
838 that \p item cannot be disposed during the functor is executing.
839 The functor does not serialize simultaneous access to the set's \p item. If such access is
840 possible you must provide your own synchronization schema on item level to prevent unsafe item modifications.
842 The function returns \p true if \p hash is found, \p false otherwise.
844 template <typename Func>
845 bool find( hash_type const& hash, Func f )
847 typename gc::Guard guard;
848 value_type * p = search( hash, guard );
850 // p is guarded by HP
858 /// Checks whether the set contains \p hash
860 The function searches the item by its \p hash
861 and returns \p true if it is found, or \p false otherwise.
863 bool contains( hash_type const& hash )
865 return find( hash, [](value_type&) {} );
868 /// Finds an item by it's \p hash and returns the item found
870 The function searches the item by its \p hash
871 and returns the guarded pointer to the item found.
872 If \p hash is not found the function returns an empty \p guarded_ptr.
874 @note Each \p guarded_ptr object uses one GC's guard which can be limited resource.
878 typedef cds::intrusive::MultiLevelHashSet< your_template_params > my_set;
882 my_set::guarded_ptr gp( theSet.get( 5 ));
883 if ( theSet.get( 5 )) {
887 // Destructor of guarded_ptr releases internal HP guard
891 guarded_ptr get( hash_type const& hash )
895 typename gc::Guard guard;
896 gp.reset( search( hash, guard ));
901 /// Clears the set (non-atomic)
903 The function unlink all data node from the set.
904 The function is not atomic but is thread-safe.
905 After \p %clear() the set may not be empty because another threads may insert items.
907 For each item the \p disposer is called after unlinking.
911 clear_array( m_Head, head_size() );
914 /// Checks if the set is empty
916 Emptiness is checked by item counting: if item count is zero then the set is empty.
917 Thus, the correct item counting feature is an important part of the set implementation.
924 /// Returns item count in the set
927 return m_ItemCounter;
930 /// Returns const reference to internal statistics
931 stat const& statistics() const
936 /// Returns the size of head node
937 size_t head_size() const
939 return m_Metrics.head_node_size;
942 /// Returns the size of the array node
943 size_t array_node_size() const
945 return m_Metrics.array_node_size;
949 ///@name Thread-safe iterators
950 /** @anchor cds_intrusive_MultilevelHashSet_iterators
951 The set supports thread-safe iterators: you may iterate over the set in multi-threaded environment.
952 It is guaranteed that the iterators will remain valid even if another thread deletes the node the iterator points to:
953 Hazard Pointer embedded into the iterator object protects the node from physical reclamation.
955 @note Since the iterator object contains hazard pointer that is a thread-local resource,
956 the iterator should not be passed to another thread.
958 Each iterator object supports the common interface:
959 - dereference operators:
961 value_type [const] * operator ->() noexcept
962 value_type [const] & operator *() noexcept
964 - pre-increment and pre-decrement. Post-operators is not supported
965 - equality operators <tt>==</tt> and <tt>!=</tt>.
966 Iterators are equal iff they point to the same cell of the same array node.
967 Note that for two iterators \p it1 and \p it2, the conditon <tt> it1 == it2 </tt>
968 does not entail <tt> &(*it1) == &(*it2) </tt>: welcome to concurrent containers
969 - helper member function \p release() that clears internal hazard pointer.
970 After \p release() the iterator points to \p nullptr but it still remain valid: further iterating is possible.
972 During iteration you may safely erase any item from the set;
973 @ref erase_at() function call doesn't invalidate any iterator.
974 If some iterator points to the item to be erased, that item is not deleted immediately
975 but only after that iterator will be advanced forward or backward.
977 @note It is possible the item can be iterated more that once, for example, if an iterator points to the item
978 in array node that is being splitted.
982 /// Returns an iterator to the beginning of the set
985 return iterator( *this, m_Head, size_t(0) - 1 );
988 /// Returns an const iterator to the beginning of the set
989 const_iterator begin() const
991 return const_iterator( *this, m_Head, size_t(0) - 1 );
994 /// Returns an const iterator to the beginning of the set
995 const_iterator cbegin()
997 return const_iterator( *this, m_Head, size_t(0) - 1 );
1000 /// 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.
1003 return iterator( *this, m_Head, head_size(), false );
1006 /// 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.
1007 const_iterator end() const
1009 return const_iterator( *this, m_Head, head_size(), false );
1012 /// 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.
1013 const_iterator cend()
1015 return const_iterator( *this, m_Head, head_size(), false );
1018 /// Returns a reverse iterator to the first element of the reversed set
1019 reverse_iterator rbegin()
1021 return reverse_iterator( *this, m_Head, head_size() );
1024 /// Returns a const reverse iterator to the first element of the reversed set
1025 const_reverse_iterator rbegin() const
1027 return const_reverse_iterator( *this, m_Head, head_size() );
1030 /// Returns a const reverse iterator to the first element of the reversed set
1031 const_reverse_iterator crbegin()
1033 return const_reverse_iterator( *this, m_Head, head_size() );
1036 /// Returns a reverse iterator to the element following the last element of the reversed set
1038 It corresponds to the element preceding the first element of the non-reversed container.
1039 This element acts as a placeholder, attempting to access it results in undefined behavior.
1041 reverse_iterator rend()
1043 return reverse_iterator( *this, m_Head, size_t(0) - 1, false );
1046 /// Returns a const reverse iterator to the element following the last element of the reversed set
1048 It corresponds to the element preceding the first element of the non-reversed container.
1049 This element acts as a placeholder, attempting to access it results in undefined behavior.
1051 const_reverse_iterator rend() const
1053 return const_reverse_iterator( *this, m_Head, size_t(0) - 1, false );
1056 /// Returns a const reverse iterator to the element following the last element of the reversed set
1058 It corresponds to the element preceding the first element of the non-reversed container.
1059 This element acts as a placeholder, attempting to access it results in undefined behavior.
1061 const_reverse_iterator crend()
1063 return const_reverse_iterator( *this, m_Head, size_t(0) - 1, false );
1070 array_node * alloc_head_node() const
1072 return alloc_array_node( head_size(), nullptr, 0 );
1075 array_node * alloc_array_node( array_node * pParent, size_t idxParent ) const
1077 return alloc_array_node( array_node_size(), pParent, idxParent );
1080 static array_node * alloc_array_node( size_t nSize, array_node * pParent, size_t idxParent )
1082 array_node * pNode = cxx_array_node_allocator().NewBlock( sizeof(array_node) + sizeof(atomic_node_ptr) * (nSize - 1), pParent, idxParent );
1083 for ( atomic_node_ptr * p = pNode->nodes, *pEnd = pNode->nodes + nSize; p < pEnd; ++p )
1084 p->store( node_ptr(), memory_model::memory_order_release );
1088 static void free_array_node( array_node * parr )
1090 cxx_array_node_allocator().Delete( parr );
1095 // The function is not thread-safe. For use in dtor only
1099 // Destroy all array nodes
1100 destroy_array_nodes( m_Head, head_size());
1103 void destroy_array_nodes( array_node * pArr, size_t nSize )
1105 for ( atomic_node_ptr * p = pArr->nodes, *pLast = pArr->nodes + nSize; p != pLast; ++p ) {
1106 node_ptr slot = p->load( memory_model::memory_order_acquire );
1107 if ( slot.bits() == flag_array_node ) {
1108 destroy_array_nodes(to_array(slot.ptr()), array_node_size());
1109 free_array_node( to_array(slot.ptr()));
1110 p->store(node_ptr(), memory_model::memory_order_relaxed );
1115 void clear_array( array_node * pArrNode, size_t nSize )
1120 for ( atomic_node_ptr * pArr = pArrNode->nodes, *pLast = pArr + nSize; pArr != pLast; ++pArr ) {
1122 node_ptr slot = pArr->load( memory_model::memory_order_acquire );
1123 if ( slot.bits() == flag_array_node ) {
1124 // array node, go down the tree
1125 assert( slot.ptr() != nullptr );
1126 clear_array( to_array( slot.ptr()), array_node_size() );
1129 else if ( slot.bits() == flag_array_converting ) {
1130 // the slot is converting to array node right now
1131 while ( (slot = pArr->load(memory_model::memory_order_acquire)).bits() == flag_array_converting ) {
1133 m_Stat.onSlotConverting();
1137 assert( slot.ptr() != nullptr );
1138 assert(slot.bits() == flag_array_node );
1139 clear_array( to_array( slot.ptr()), array_node_size() );
1144 if ( pArr->compare_exchange_strong( slot, node_ptr(), memory_model::memory_order_acquire, atomics::memory_order_relaxed )) {
1146 gc::template retire<disposer>( slot.ptr() );
1148 m_Stat.onEraseSuccess();
1161 converter( value_type * p )
1165 converter( array_node * p )
1170 static array_node * to_array( value_type * p )
1172 return converter( p ).pArr;
1174 static value_type * to_node( array_node * p )
1176 return converter( p ).pData;
1179 bool expand_slot( array_node * pParent, size_t idxParent, node_ptr current, size_t nOffset )
1181 assert( current.bits() == 0 );
1182 assert( current.ptr() );
1184 size_t idx = hash_splitter(hash_accessor()(*current.ptr()), nOffset).cut( m_Metrics.array_node_size_log );
1185 array_node * pArr = alloc_array_node( pParent, idxParent );
1187 node_ptr cur(current.ptr());
1188 atomic_node_ptr& slot = pParent->nodes[idxParent];
1189 if ( !slot.compare_exchange_strong( cur, cur | flag_array_converting, memory_model::memory_order_release, atomics::memory_order_relaxed ))
1191 m_Stat.onExpandNodeFailed();
1192 free_array_node( pArr );
1196 pArr->nodes[idx].store( current, memory_model::memory_order_release );
1198 cur = cur | flag_array_converting;
1200 slot.compare_exchange_strong( cur, node_ptr( to_node( pArr ), flag_array_node ), memory_model::memory_order_release, atomics::memory_order_relaxed )
1203 m_Stat.onExpandNodeSuccess();
1204 m_Stat.onArrayNodeCreated();
1211 value_type * search( hash_type const& hash, typename gc::Guard& guard )
1213 hash_splitter splitter( hash );
1214 hash_comparator cmp;
1217 array_node * pArr = m_Head;
1218 size_t nSlot = splitter.cut( m_Metrics.head_node_size_log );
1219 assert( nSlot < m_Metrics.head_node_size );
1222 node_ptr slot = pArr->nodes[nSlot].load( memory_model::memory_order_acquire );
1223 if ( slot.bits() == flag_array_node ) {
1224 // array node, go down the tree
1225 assert( slot.ptr() != nullptr );
1226 nSlot = splitter.cut( m_Metrics.array_node_size_log );
1227 assert( nSlot < m_Metrics.array_node_size );
1228 pArr = to_array( slot.ptr() );
1230 else if ( slot.bits() == flag_array_converting ) {
1231 // the slot is converting to array node right now
1233 m_Stat.onSlotConverting();
1237 assert(slot.bits() == 0 );
1239 // protect data node by hazard pointer
1240 if ( guard.protect( pArr->nodes[nSlot], [](node_ptr p) -> value_type * { return p.ptr(); }) != slot ) {
1241 // slot value has been changed - retry
1242 m_Stat.onSlotChanged();
1244 else if ( slot.ptr() && cmp( hash, hash_accessor()( *slot.ptr() )) == 0 ) {
1246 m_Stat.onFindSuccess();
1249 m_Stat.onFindFailed();
1255 template <typename Predicate>
1256 value_type * do_erase( hash_type const& hash, typename gc::Guard& guard, Predicate pred )
1258 hash_splitter splitter( hash );
1259 hash_comparator cmp;
1262 array_node * pArr = m_Head;
1263 size_t nSlot = splitter.cut( m_Metrics.head_node_size_log );
1264 assert( nSlot < m_Metrics.head_node_size );
1267 node_ptr slot = pArr->nodes[nSlot].load( memory_model::memory_order_acquire );
1268 if ( slot.bits() == flag_array_node ) {
1269 // array node, go down the tree
1270 assert( slot.ptr() != nullptr );
1271 nSlot = splitter.cut( m_Metrics.array_node_size_log );
1272 assert( nSlot < m_Metrics.array_node_size );
1273 pArr = to_array( slot.ptr() );
1275 else if ( slot.bits() == flag_array_converting ) {
1276 // the slot is converting to array node right now
1278 m_Stat.onSlotConverting();
1282 assert(slot.bits() == 0 );
1284 // protect data node by hazard pointer
1285 if ( guard.protect( pArr->nodes[nSlot], [](node_ptr p) -> value_type * { return p.ptr(); }) != slot ) {
1286 // slot value has been changed - retry
1287 m_Stat.onSlotChanged();
1289 else if ( slot.ptr() ) {
1290 if ( cmp( hash, hash_accessor()( *slot.ptr() )) == 0 && pred( *slot.ptr() )) {
1291 // item found - replace it with nullptr
1292 if ( pArr->nodes[nSlot].compare_exchange_strong(slot, node_ptr(nullptr), memory_model::memory_order_acquire, atomics::memory_order_relaxed) ) {
1293 // slot is guarded by HP
1294 gc::template retire<disposer>( slot.ptr() );
1296 m_Stat.onEraseSuccess();
1300 m_Stat.onEraseRetry();
1303 m_Stat.onEraseFailed();
1307 // the slot is empty
1308 m_Stat.onEraseFailed();
1315 bool do_erase_at( iterator_base const& iter )
1317 if ( iter.m_set != this )
1319 if ( iter.m_pNode == m_Head && iter.m_idx >= head_size())
1321 if ( iter.m_idx >= array_node_size() )
1325 node_ptr slot = iter.m_pNode->nodes[iter.m_idx].load( memory_model::memory_order_acquire );
1326 if ( slot.bits() == 0 && slot.ptr() == iter.pointer() ) {
1327 if ( iter.m_pNode->nodes[iter.m_idx].compare_exchange_strong(slot, node_ptr(nullptr), memory_model::memory_order_acquire, atomics::memory_order_relaxed) ) {
1328 // the item is guarded by iterator, so we may retire it safely
1329 gc::template retire<disposer>( slot.ptr() );
1331 m_Stat.onEraseSuccess();
1340 template <typename Func>
1341 std::pair<bool, bool> do_update( value_type& val, Func f, bool bInsert = true )
1343 hash_type const& hash = hash_accessor()( val );
1344 hash_splitter splitter( hash );
1345 hash_comparator cmp;
1346 typename gc::template GuardArray<2> guards;
1349 array_node * pArr = m_Head;
1350 size_t nSlot = splitter.cut( m_Metrics.head_node_size_log );
1351 assert( nSlot < m_Metrics.head_node_size );
1352 size_t nOffset = m_Metrics.head_node_size_log;
1355 guards.assign( 1, &val );
1358 node_ptr slot = pArr->nodes[nSlot].load( memory_model::memory_order_acquire );
1359 if ( slot.bits() == flag_array_node ) {
1360 // array node, go down the tree
1361 assert( slot.ptr() != nullptr );
1362 nSlot = splitter.cut( m_Metrics.array_node_size_log );
1363 assert( nSlot < m_Metrics.array_node_size );
1364 pArr = to_array( slot.ptr() );
1365 nOffset += m_Metrics.array_node_size_log;
1368 else if ( slot.bits() == flag_array_converting ) {
1369 // the slot is converting to array node right now
1371 m_Stat.onSlotConverting();
1375 assert(slot.bits() == 0 );
1377 // protect data node by hazard pointer
1378 if ( guards.protect( 0, pArr->nodes[nSlot], [](node_ptr p) -> value_type * { return p.ptr(); }) != slot ) {
1379 // slot value has been changed - retry
1380 m_Stat.onSlotChanged();
1382 else if ( slot.ptr() ) {
1383 if ( cmp( hash, hash_accessor()( *slot.ptr() )) == 0 ) {
1384 // the item with that hash value already exists
1385 // Replace it with val
1386 if ( slot.ptr() == &val ) {
1387 m_Stat.onUpdateExisting();
1388 return std::make_pair( true, false );
1391 if ( pArr->nodes[nSlot].compare_exchange_strong( slot, node_ptr( &val ), memory_model::memory_order_release, atomics::memory_order_relaxed )) {
1392 // slot can be disposed
1393 f( val, slot.ptr() );
1394 gc::template retire<disposer>( slot.ptr() );
1395 m_Stat.onUpdateExisting();
1396 return std::make_pair( true, false );
1399 m_Stat.onUpdateRetry();
1403 // the slot must be expanded
1404 expand_slot( pArr, nSlot, slot, nOffset );
1407 // the slot is empty, try to insert data node
1410 if ( pArr->nodes[nSlot].compare_exchange_strong( pNull, node_ptr( &val ), memory_model::memory_order_release, atomics::memory_order_relaxed ))
1412 // the new data node has been inserted
1415 m_Stat.onUpdateNew();
1416 m_Stat.height( nHeight );
1417 return std::make_pair( true, true );
1421 m_Stat.onUpdateFailed();
1422 return std::make_pair( false, false );
1425 // insert failed - slot has been changed by another thread
1427 m_Stat.onUpdateRetry();
1434 }} // namespace cds::intrusive
1439 template <class GC, typename T, typename Traits>
1440 struct iterator_traits< typename cds::intrusive::MultiLevelHashSet< GC, T, Traits >::iterator >
1442 typedef typename cds::intrusive::MultiLevelHashSet< GC, T, Traits >::iterator iterator_class;
1444 // difference_type is not applicable for that iterator
1445 // typedef ??? difference_type
1446 typedef T value_type;
1447 typedef typename iterator_class::value_ptr pointer;
1448 typedef typename iterator_class::value_ref reference;
1449 typedef bidirectional_iterator_tag iterator_category;
1452 template <class GC, typename T, typename Traits>
1453 struct iterator_traits< typename cds::intrusive::MultiLevelHashSet< GC, T, Traits >::const_iterator >
1455 typedef typename cds::intrusive::MultiLevelHashSet< GC, T, Traits >::const_iterator iterator_class;
1457 // difference_type is not applicable for that iterator
1458 // typedef ??? difference_type
1459 typedef T value_type;
1460 typedef typename iterator_class::value_ptr pointer;
1461 typedef typename iterator_class::value_ref reference;
1462 typedef bidirectional_iterator_tag iterator_category;
1468 #endif // #ifndef CDSLIB_INTRUSIVE_IMPL_MULTILEVEL_HASHSET_H