3 #ifndef CDSLIB_INTRUSIVE_IMPL_FELDMAN_HASHSET_H
4 #define CDSLIB_INTRUSIVE_IMPL_FELDMAN_HASHSET_H
6 #include <functional> // std::ref
7 #include <iterator> // std::iterator_traits
10 #include <cds/intrusive/details/feldman_hashset_base.h>
11 #include <cds/details/allocator.h>
13 namespace cds { namespace intrusive {
14 /// Intrusive hash set based on multi-level array
15 /** @ingroup cds_intrusive_map
16 @anchor cds_intrusive_FeldmanHashSet_hp
19 - [2013] Steven Feldman, Pierre LaBorde, Damian Dechev "Concurrent Multi-level Arrays:
20 Wait-free Extensible Hash Maps"
22 [From the paper] The hardest problem encountered while developing a parallel hash map is how to perform
23 a global resize, the process of redistributing the elements in a hash map that occurs when adding new
24 buckets. The negative impact of blocking synchronization is multiplied during a global resize, because all
25 threads will be forced to wait on the thread that is performing the involved process of resizing the hash map
26 and redistributing the elements. \p %FeldmanHashSet implementation avoids global resizes through new array
27 allocation. By allowing concurrent expansion this structure is free from the overhead of an explicit resize,
28 which facilitates concurrent operations.
30 The presented design includes dynamic hashing, the use of sub-arrays within the hash map data structure;
31 which, in combination with <b>perfect hashing</b>, means that each element has a unique final, as well as current, position.
32 It is important to note that the perfect hash function required by our hash map is trivial to realize as
33 any hash function that permutes the bits of the key is suitable. This is possible because of our approach
34 to the hash function; we require that it produces hash values that are equal in size to that of the key.
35 We know that if we expand the hash map a fixed number of times there can be no collision as duplicate keys
36 are not provided for in the standard semantics of a hash map.
38 \p %FeldmanHashSet is a multi-level array which has a structure similar to a tree:
39 @image html feldman_hashset.png
40 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.
41 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
42 with that key; it is a simple struct holding two variables. A \p dataNode in the multi-level array could be marked.
43 A \p markedDataNode refers to a pointer to a \p dataNode that has been bitmarked at the least significant bit (LSB)
44 of the pointer to the node. This signifies that this \p dataNode is contended. An expansion must occur at this node;
45 any thread that sees this \p markedDataNode will try to replace it with an \p arrayNode; which is a position that holds
46 an array of nodes. The pointer to an \p arrayNode is differentiated from that of a pointer to a \p dataNode by a bitmark
47 on the second-least significant bit.
49 \p %FeldmanHashSet multi-level array is similar to a tree in that we keep a pointer to the root, which is a memory array
50 called \p head. The length of the \p head memory array is unique, whereas every other \p arrayNode has a uniform length;
51 a normal \p arrayNode has a fixed power-of-two length equal to the binary logarithm of a variable called \p arrayLength.
52 The maximum depth of the tree, \p maxDepth, is the maximum number of pointers that must be followed to reach any node.
53 We define \p currentDepth as the number of memory arrays that we need to traverse to reach the \p arrayNode on which
54 we need to operate; this is initially one, because of \p head.
56 That approach to the structure of the hash set uses an extensible hashing scheme; <b> the hash value is treated as a bit
57 string</b> and rehash incrementally.
59 @note Two important things you should keep in mind when you're using \p %FeldmanHashSet:
60 - all keys must be fixed-size. It means that you cannot use \p std::string as a key for \p %FeldmanHashSet.
61 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>,
62 <a href="https://en.wikipedia.org/wiki/MurmurHash">MurmurHash</a>, <a href="https://en.wikipedia.org/wiki/CityHash">CityHash</a>
63 or its successor <a href="https://code.google.com/p/farmhash/">FarmHash</a> and so on, which
64 converts variable-length strings to fixed-length bit-strings, and use that hash as a key in \p %FeldmanHashSet.
65 - \p %FeldmanHashSet uses a perfect hashing. It means that if two different keys, for example, of type \p std::string,
66 have identical hash then you cannot insert both that keys in the set. \p %FeldmanHashSet does not maintain the key,
67 it maintains its fixed-size hash value.
69 The set supports @ref cds_intrusive_FeldmanHashSet_iterators "bidirectional thread-safe iterators".
72 - \p GC - safe memory reclamation schema. Can be \p gc::HP, \p gc::DHP or one of \ref cds_urcu_type "RCU type"
73 - \p T - a value type to be stored in the set
74 - \p Traits - type traits, the structure based on \p feldman_hashset::traits or result of \p feldman_hashset::make_traits metafunction.
75 \p Traits is the mandatory argument because it has one mandatory type - an @ref feldman_hashset::traits::hash_accessor "accessor"
76 to hash value of \p T. The set algorithm does not calculate that hash value.
78 There are several specializations of \p %FeldmanHashSet for each \p GC. You should include:
79 - <tt><cds/intrusive/feldman_hashset_hp.h></tt> for \p gc::HP garbage collector
80 - <tt><cds/intrusive/feldman_hashset_dhp.h></tt> for \p gc::DHP garbage collector
81 - <tt><cds/intrusive/feldman_hashset_rcu.h></tt> for \ref cds_intrusive_FeldmanHashSet_rcu "RCU type". RCU specialization
82 has a slightly different interface.
87 #ifdef CDS_DOXYGEN_INVOKED
88 ,typename Traits = feldman_hashset::traits
93 class FeldmanHashSet: protected feldman_hashset::multilevel_array<T, Traits>
95 typedef feldman_hashset::multilevel_array<T, Traits> base_class;
98 typedef GC gc; ///< Garbage collector
99 typedef T value_type; ///< type of value stored in the set
100 typedef Traits traits; ///< Traits template parameter, see \p feldman_hashset::traits
102 typedef typename traits::hash_accessor hash_accessor; ///< Hash accessor functor
103 typedef typename base_class::hash_type hash_type; ///< Hash type deduced from \p hash_accessor return type
104 typedef typename traits::disposer disposer; ///< data node disposer
105 typedef typename base_class::hash_comparator hash_comparator; ///< hash compare functor based on \p traits::compare and \p traits::less options
107 typedef typename traits::item_counter item_counter; ///< Item counter type
108 typedef typename traits::node_allocator node_allocator; ///< Array node allocator
109 typedef typename traits::memory_model memory_model; ///< Memory model
110 typedef typename traits::back_off back_off; ///< Backoff strategy
111 typedef typename traits::stat stat; ///< Internal statistics type
113 typedef typename gc::template guarded_ptr< value_type > guarded_ptr; ///< Guarded pointer
115 /// Count of hazard pointers required
116 static CDS_CONSTEXPR size_t const c_nHazardPtrCount = 2;
120 typedef typename base_class::node_ptr node_ptr;
121 typedef typename base_class::atomic_node_ptr atomic_node_ptr;
122 typedef typename base_class::array_node array_node;
123 typedef typename base_class::traverse_data traverse_data;
125 using base_class::to_array;
126 using base_class::to_node;
127 using base_class::stats;
128 using base_class::head;
129 using base_class::metrics;
136 friend class FeldmanHashSet;
139 array_node * m_pNode; ///< current array node
140 size_t m_idx; ///< current position in m_pNode
141 typename gc::Guard m_guard; ///< HP guard
142 FeldmanHashSet const* m_set; ///< Hash set
145 iterator_base() CDS_NOEXCEPT
151 iterator_base( iterator_base const& rhs ) CDS_NOEXCEPT
152 : m_pNode( rhs.m_pNode )
156 m_guard.copy( rhs.m_guard );
159 iterator_base& operator=(iterator_base const& rhs) CDS_NOEXCEPT
161 m_pNode = rhs.m_pNode;
164 m_guard.copy( rhs.m_guard );
168 iterator_base& operator++()
174 iterator_base& operator--()
185 bool operator ==(iterator_base const& rhs) const CDS_NOEXCEPT
187 return m_pNode == rhs.m_pNode && m_idx == rhs.m_idx && m_set == rhs.m_set;
190 bool operator !=(iterator_base const& rhs) const CDS_NOEXCEPT
192 return !( *this == rhs );
196 iterator_base( FeldmanHashSet const& set, array_node * pNode, size_t idx, bool )
202 iterator_base( FeldmanHashSet const& set, array_node * pNode, size_t idx )
210 value_type * pointer() const CDS_NOEXCEPT
212 return m_guard.template get<value_type>();
217 assert( m_set != nullptr );
218 assert( m_pNode != nullptr );
220 size_t const arrayNodeSize = m_set->array_node_size();
221 size_t const headSize = m_set->head_size();
222 array_node * pNode = m_pNode;
223 size_t idx = m_idx + 1;
224 size_t nodeSize = m_pNode->pParent? arrayNodeSize : headSize;
227 if ( idx < nodeSize ) {
228 node_ptr slot = pNode->nodes[idx].load( memory_model::memory_order_acquire );
229 if ( slot.bits() == base_class::flag_array_node ) {
230 // array node, go down the tree
231 assert( slot.ptr() != nullptr );
232 pNode = to_array( slot.ptr() );
234 nodeSize = arrayNodeSize;
236 else if ( slot.bits() == base_class::flag_array_converting ) {
237 // the slot is converting to array node right now - skip the node
243 if ( m_guard.protect( pNode->nodes[idx], [](node_ptr p) -> value_type * { return p.ptr(); }) == slot ) {
254 if ( pNode->pParent ) {
255 idx = pNode->idxParent + 1;
256 pNode = pNode->pParent;
257 nodeSize = pNode->pParent ? arrayNodeSize : headSize;
261 assert( pNode == m_set->head() );
262 assert( idx == headSize );
273 assert( m_set != nullptr );
274 assert( m_pNode != nullptr );
276 size_t const arrayNodeSize = m_set->array_node_size();
277 size_t const headSize = m_set->head_size();
278 size_t const endIdx = size_t(0) - 1;
280 array_node * pNode = m_pNode;
281 size_t idx = m_idx - 1;
282 size_t nodeSize = m_pNode->pParent? arrayNodeSize : headSize;
285 if ( idx != endIdx ) {
286 node_ptr slot = pNode->nodes[idx].load( memory_model::memory_order_acquire );
287 if ( slot.bits() == base_class::flag_array_node ) {
288 // array node, go down the tree
289 assert( slot.ptr() != nullptr );
290 pNode = to_array( slot.ptr() );
291 nodeSize = arrayNodeSize;
294 else if ( slot.bits() == base_class::flag_array_converting ) {
295 // the slot is converting to array node right now - skip the node
301 if ( m_guard.protect( pNode->nodes[idx], [](node_ptr p) -> value_type * { return p.ptr(); }) == slot ) {
312 if ( pNode->pParent ) {
313 idx = pNode->idxParent - 1;
314 pNode = pNode->pParent;
315 nodeSize = pNode->pParent ? arrayNodeSize : headSize;
319 assert( pNode == m_set->head() );
320 assert( idx == endIdx );
330 template <class Iterator>
331 Iterator init_begin() const
333 return Iterator( *this, head(), size_t(0) - 1 );
336 template <class Iterator>
337 Iterator init_end() const
339 return Iterator( *this, head(), head_size(), false );
342 template <class Iterator>
343 Iterator init_rbegin() const
345 return Iterator( *this, head(), head_size() );
348 template <class Iterator>
349 Iterator init_rend() const
351 return Iterator( *this, head(), size_t(0) - 1, false );
354 /// Bidirectional iterator class
355 template <bool IsConst>
356 class bidirectional_iterator: protected iterator_base
358 friend class FeldmanHashSet;
361 static CDS_CONSTEXPR bool const c_bConstantIterator = IsConst;
364 typedef typename std::conditional< IsConst, value_type const*, value_type*>::type value_ptr; ///< Value pointer
365 typedef typename std::conditional< IsConst, value_type const&, value_type&>::type value_ref; ///< Value reference
368 bidirectional_iterator() CDS_NOEXCEPT
371 bidirectional_iterator( bidirectional_iterator const& rhs ) CDS_NOEXCEPT
372 : iterator_base( rhs )
375 bidirectional_iterator& operator=(bidirectional_iterator const& rhs) CDS_NOEXCEPT
377 iterator_base::operator=( rhs );
381 bidirectional_iterator& operator++()
383 iterator_base::operator++();
387 bidirectional_iterator& operator--()
389 iterator_base::operator--();
393 value_ptr operator ->() const CDS_NOEXCEPT
395 return iterator_base::pointer();
398 value_ref operator *() const CDS_NOEXCEPT
400 value_ptr p = iterator_base::pointer();
407 iterator_base::release();
410 template <bool IsConst2>
411 bool operator ==(bidirectional_iterator<IsConst2> const& rhs) const CDS_NOEXCEPT
413 return iterator_base::operator==( rhs );
416 template <bool IsConst2>
417 bool operator !=(bidirectional_iterator<IsConst2> const& rhs) const CDS_NOEXCEPT
419 return !( *this == rhs );
423 bidirectional_iterator( FeldmanHashSet& set, array_node * pNode, size_t idx, bool )
424 : iterator_base( set, pNode, idx, false )
427 bidirectional_iterator( FeldmanHashSet& set, array_node * pNode, size_t idx )
428 : iterator_base( set, pNode, idx )
432 /// Reverse bidirectional iterator
433 template <bool IsConst>
434 class reverse_bidirectional_iterator : public iterator_base
436 friend class FeldmanHashSet;
439 typedef typename std::conditional< IsConst, value_type const*, value_type*>::type value_ptr; ///< Value pointer
440 typedef typename std::conditional< IsConst, value_type const&, value_type&>::type value_ref; ///< Value reference
443 reverse_bidirectional_iterator() CDS_NOEXCEPT
447 reverse_bidirectional_iterator( reverse_bidirectional_iterator const& rhs ) CDS_NOEXCEPT
448 : iterator_base( rhs )
451 reverse_bidirectional_iterator& operator=( reverse_bidirectional_iterator const& rhs) CDS_NOEXCEPT
453 iterator_base::operator=( rhs );
457 reverse_bidirectional_iterator& operator++()
459 iterator_base::operator--();
463 reverse_bidirectional_iterator& operator--()
465 iterator_base::operator++();
469 value_ptr operator ->() const CDS_NOEXCEPT
471 return iterator_base::pointer();
474 value_ref operator *() const CDS_NOEXCEPT
476 value_ptr p = iterator_base::pointer();
483 iterator_base::release();
486 template <bool IsConst2>
487 bool operator ==(reverse_bidirectional_iterator<IsConst2> const& rhs) const
489 return iterator_base::operator==( rhs );
492 template <bool IsConst2>
493 bool operator !=(reverse_bidirectional_iterator<IsConst2> const& rhs)
495 return !( *this == rhs );
499 reverse_bidirectional_iterator( FeldmanHashSet& set, array_node * pNode, size_t idx, bool )
500 : iterator_base( set, pNode, idx, false )
503 reverse_bidirectional_iterator( FeldmanHashSet& set, array_node * pNode, size_t idx )
504 : iterator_base( set, pNode, idx, false )
506 iterator_base::backward();
512 #ifdef CDS_DOXYGEN_INVOKED
513 typedef implementation_defined iterator; ///< @ref cds_intrusive_FeldmanHashSet_iterators "bidirectional iterator" type
514 typedef implementation_defined const_iterator; ///< @ref cds_intrusive_FeldmanHashSet_iterators "bidirectional const iterator" type
515 typedef implementation_defined reverse_iterator; ///< @ref cds_intrusive_FeldmanHashSet_iterators "bidirectional reverse iterator" type
516 typedef implementation_defined const_reverse_iterator; ///< @ref cds_intrusive_FeldmanHashSet_iterators "bidirectional reverse const iterator" type
518 typedef bidirectional_iterator<false> iterator;
519 typedef bidirectional_iterator<true> const_iterator;
520 typedef reverse_bidirectional_iterator<false> reverse_iterator;
521 typedef reverse_bidirectional_iterator<true> const_reverse_iterator;
526 item_counter m_ItemCounter; ///< Item counter
530 /// Creates empty set
532 @param head_bits: 2<sup>head_bits</sup> specifies the size of head array, minimum is 4.
533 @param array_bits: 2<sup>array_bits</sup> specifies the size of array node, minimum is 2.
535 Equation for \p head_bits and \p array_bits:
537 sizeof(hash_type) * 8 == head_bits + N * array_bits
539 where \p N is multi-level array depth.
541 FeldmanHashSet( size_t head_bits = 8, size_t array_bits = 4 )
542 : base_class( head_bits, array_bits )
545 /// Destructs the set and frees all data
553 The function inserts \p val in the set if it does not contain
554 an item with that hash.
556 Returns \p true if \p val is placed into the set, \p false otherwise.
558 bool insert( value_type& val )
560 return insert( val, [](value_type&) {} );
565 This function is intended for derived non-intrusive containers.
567 The function allows to split creating of new item into two part:
568 - create item with key only
569 - insert new item into the set
570 - if inserting is success, calls \p f functor to initialize \p val.
572 The functor signature is:
574 void func( value_type& val );
576 where \p val is the item inserted.
578 The user-defined functor is called only if the inserting is success.
580 @warning See \ref cds_intrusive_item_creating "insert item troubleshooting".
582 template <typename Func>
583 bool insert( value_type& val, Func f )
585 hash_type const& hash = hash_accessor()(val);
586 traverse_data pos( hash, *this );
588 typename gc::Guard guard;
591 node_ptr slot = base_class::traverse( pos );
592 assert( slot.bits() == 0 );
594 // protect data node by hazard pointer
595 if (guard.protect(pos.pArr->nodes[pos.nSlot], [](node_ptr p) -> value_type * { return p.ptr(); }) != slot) {
596 // slot value has been changed - retry
597 stats().onSlotChanged();
601 if ( cmp( hash, hash_accessor()(*slot.ptr())) == 0 ) {
602 // the item with that hash value already exists
603 stats().onInsertFailed();
607 // the slot must be expanded
608 base_class::expand_slot( pos, slot );
611 // the slot is empty, try to insert data node
613 if ( pos.pArr->nodes[pos.nSlot].compare_exchange_strong(pNull, node_ptr(&val), memory_model::memory_order_release, atomics::memory_order_relaxed))
615 // the new data node has been inserted
618 stats().onInsertSuccess();
619 stats().height(pos.nHeight);
623 // insert failed - slot has been changed by another thread
625 stats().onInsertRetry();
632 Performs inserting or updating the item with hash value equal to \p val.
633 - If hash value is found then existing item is replaced with \p val, old item is disposed
634 with \p Traits::disposer. Note that the disposer is called by \p GC asynchronously.
635 The function returns <tt> std::pair<true, false> </tt>
636 - If hash value is not found and \p bInsert is \p true then \p val is inserted,
637 the function returns <tt> std::pair<true, true> </tt>
638 - If hash value is not found and \p bInsert is \p false then the set is unchanged,
639 the function returns <tt> std::pair<false, false> </tt>
641 Returns <tt> std::pair<bool, bool> </tt> where \p first is \p true if operation is successfull
642 (i.e. the item has been inserted or updated),
643 \p second is \p true if new item has been added or \p false if the set contains that hash.
645 std::pair<bool, bool> update( value_type& val, bool bInsert = true )
647 return do_update(val, [](value_type&, value_type *) {}, bInsert );
650 /// Unlinks the item \p val from the set
652 The function searches the item \p val in the set and unlink it
653 if it is found and its address is equal to <tt>&val</tt>.
655 The function returns \p true if success and \p false otherwise.
657 bool unlink( value_type const& val )
659 typename gc::Guard guard;
660 auto pred = [&val](value_type const& item) -> bool { return &item == &val; };
661 value_type * p = do_erase( hash_accessor()( val ), guard, std::ref( pred ));
665 /// Deletes the item from the set
667 The function searches \p hash in the set,
668 unlinks the item found, and returns \p true.
669 If that item is not found the function returns \p false.
671 The \ref disposer specified in \p Traits is called by garbage collector \p GC asynchronously.
673 bool erase( hash_type const& hash )
675 return erase(hash, [](value_type const&) {} );
678 /// Deletes the item from the set
680 The function searches \p hash in the set,
681 call \p f functor with item found, and unlinks it from the set.
682 The \ref disposer specified in \p Traits is called
683 by garbage collector \p GC asynchronously.
685 The \p Func interface is
688 void operator()( value_type& item );
692 If \p hash is not found the function returns \p false.
694 template <typename Func>
695 bool erase( hash_type const& hash, Func f )
697 typename gc::Guard guard;
698 value_type * p = do_erase( hash, guard, []( value_type const&) -> bool {return true; } );
700 // p is guarded by HP
708 /// Deletes the item pointed by iterator \p iter
710 Returns \p true if the operation is successful, \p false otherwise.
712 The function does not invalidate the iterator, it remains valid and can be used for further traversing.
714 bool erase_at( iterator const& iter )
716 return do_erase_at( iter );
719 bool erase_at( reverse_iterator const& iter )
721 return do_erase_at( iter );
725 /// Extracts the item with specified \p hash
727 The function searches \p hash in the set,
728 unlinks it from the set, and returns an guarded pointer to the item extracted.
729 If \p hash is not found the function returns an empty guarded pointer.
731 The \p disposer specified in \p Traits class' template parameter is called automatically
732 by garbage collector \p GC when returned \ref guarded_ptr object to be destroyed or released.
733 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
737 typedef cds::intrusive::FeldmanHashSet< your_template_args > my_set;
741 my_set::guarded_ptr gp( theSet.extract( 5 ));
746 // Destructor of gp releases internal HP guard
750 guarded_ptr extract( hash_type const& hash )
754 typename gc::Guard guard;
755 value_type * p = do_erase( hash, guard, []( value_type const&) -> bool {return true;} );
757 // p is guarded by HP
764 /// Finds an item by it's \p hash
766 The function searches the item by \p hash and calls the functor \p f for item found.
767 The interface of \p Func functor is:
770 void operator()( value_type& item );
773 where \p item is the item found.
775 The functor may change non-key fields of \p item. Note that the functor is only guarantee
776 that \p item cannot be disposed during the functor is executing.
777 The functor does not serialize simultaneous access to the set's \p item. If such access is
778 possible you must provide your own synchronization schema on item level to prevent unsafe item modifications.
780 The function returns \p true if \p hash is found, \p false otherwise.
782 template <typename Func>
783 bool find( hash_type const& hash, Func f )
785 typename gc::Guard guard;
786 value_type * p = search( hash, guard );
788 // p is guarded by HP
796 /// Checks whether the set contains \p hash
798 The function searches the item by its \p hash
799 and returns \p true if it is found, or \p false otherwise.
801 bool contains( hash_type const& hash )
803 return find( hash, [](value_type&) {} );
806 /// Finds an item by it's \p hash and returns the item found
808 The function searches the item by its \p hash
809 and returns the guarded pointer to the item found.
810 If \p hash is not found the function returns an empty \p guarded_ptr.
812 @note Each \p guarded_ptr object uses one GC's guard which can be limited resource.
816 typedef cds::intrusive::FeldmanHashSet< your_template_params > my_set;
820 my_set::guarded_ptr gp( theSet.get( 5 ));
821 if ( theSet.get( 5 )) {
825 // Destructor of guarded_ptr releases internal HP guard
829 guarded_ptr get( hash_type const& hash )
833 typename gc::Guard guard;
834 gp.reset( search( hash, guard ));
839 /// Clears the set (non-atomic)
841 The function unlink all data node from the set.
842 The function is not atomic but is thread-safe.
843 After \p %clear() the set may not be empty because another threads may insert items.
845 For each item the \p disposer is called after unlinking.
849 clear_array( head(), head_size() );
852 /// Checks if the set is empty
854 Emptiness is checked by item counting: if item count is zero then the set is empty.
855 Thus, the correct item counting feature is an important part of the set implementation.
862 /// Returns item count in the set
865 return m_ItemCounter;
868 /// Returns const reference to internal statistics
869 stat const& statistics() const
874 /// Returns the size of head node
875 using base_class::head_size;
877 /// Returns the size of the array node
878 using base_class::array_node_size;
880 /// Collects tree level statistics into \p stat
881 /** @anchor cds_intrusive_FeldmanHashSet_hp_get_level_statistics
882 The function traverses the set and collects staistics for each level of the tree
883 into \p feldman_hashset::level_statistics struct. The element of \p stat[i]
884 represents statistics for level \p i, level 0 is head array.
885 The function is thread-safe and may be called in multi-threaded environment.
887 Result can be useful for estimating efficiency of hash functor you use.
889 void get_level_statistics(std::vector< feldman_hashset::level_statistics>& stat) const
891 base_class::get_level_statistics( stat );
895 ///@name Thread-safe iterators
896 /** @anchor cds_intrusive_FeldmanHashSet_iterators
897 The set supports thread-safe iterators: you may iterate over the set in multi-threaded environment.
898 It is guaranteed that the iterators will remain valid even if another thread deletes the node the iterator points to:
899 Hazard Pointer embedded into the iterator object protects the node from physical reclamation.
901 @note Since the iterator object contains hazard pointer that is a thread-local resource,
902 the iterator should not be passed to another thread.
904 Each iterator object supports the common interface:
905 - dereference operators:
907 value_type [const] * operator ->() noexcept
908 value_type [const] & operator *() noexcept
910 - pre-increment and pre-decrement. Post-operators is not supported
911 - equality operators <tt>==</tt> and <tt>!=</tt>.
912 Iterators are equal iff they point to the same cell of the same array node.
913 Note that for two iterators \p it1 and \p it2, the conditon <tt> it1 == it2 </tt>
914 does not entail <tt> &(*it1) == &(*it2) </tt>: welcome to concurrent containers
915 - helper member function \p release() that clears internal hazard pointer.
916 After \p release() the iterator points to \p nullptr but it still remain valid: further iterating is possible.
918 During iteration you may safely erase any item from the set;
919 @ref erase_at() function call doesn't invalidate any iterator.
920 If some iterator points to the item to be erased, that item is not deleted immediately
921 but only after that iterator will be advanced forward or backward.
923 @note It is possible the item can be iterated more that once, for example, if an iterator points to the item
924 in array node that is being splitted.
928 /// Returns an iterator to the beginning of the set
931 return iterator( *this, head(), size_t(0) - 1 );
934 /// Returns an const iterator to the beginning of the set
935 const_iterator begin() const
937 return const_iterator( *this, head(), size_t(0) - 1 );
940 /// Returns an const iterator to the beginning of the set
941 const_iterator cbegin()
943 return const_iterator( *this, head(), size_t(0) - 1 );
946 /// 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.
949 return iterator( *this, head(), head_size(), false );
952 /// 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.
953 const_iterator end() const
955 return const_iterator( *this, head(), head_size(), false );
958 /// 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.
959 const_iterator cend()
961 return const_iterator( *this, head(), head_size(), false );
964 /// Returns a reverse iterator to the first element of the reversed set
965 reverse_iterator rbegin()
967 return reverse_iterator( *this, head(), head_size() );
970 /// Returns a const reverse iterator to the first element of the reversed set
971 const_reverse_iterator rbegin() const
973 return const_reverse_iterator( *this, head(), head_size() );
976 /// Returns a const reverse iterator to the first element of the reversed set
977 const_reverse_iterator crbegin()
979 return const_reverse_iterator( *this, head(), head_size() );
982 /// Returns a reverse iterator to the element following the last element of the reversed set
984 It corresponds to the element preceding the first element of the non-reversed container.
985 This element acts as a placeholder, attempting to access it results in undefined behavior.
987 reverse_iterator rend()
989 return reverse_iterator( *this, head(), size_t(0) - 1, false );
992 /// Returns a const reverse iterator to the element following the last element of the reversed set
994 It corresponds to the element preceding the first element of the non-reversed container.
995 This element acts as a placeholder, attempting to access it results in undefined behavior.
997 const_reverse_iterator rend() const
999 return const_reverse_iterator( *this, head(), size_t(0) - 1, false );
1002 /// Returns a const reverse iterator to the element following the last element of the reversed set
1004 It corresponds to the element preceding the first element of the non-reversed container.
1005 This element acts as a placeholder, attempting to access it results in undefined behavior.
1007 const_reverse_iterator crend()
1009 return const_reverse_iterator( *this, head(), size_t(0) - 1, false );
1015 void clear_array( array_node * pArrNode, size_t nSize )
1019 for ( atomic_node_ptr * pArr = pArrNode->nodes, *pLast = pArr + nSize; pArr != pLast; ++pArr ) {
1021 node_ptr slot = pArr->load( memory_model::memory_order_acquire );
1022 if ( slot.bits() == base_class::flag_array_node ) {
1023 // array node, go down the tree
1024 assert( slot.ptr() != nullptr );
1025 clear_array( to_array( slot.ptr()), array_node_size() );
1028 else if ( slot.bits() == base_class::flag_array_converting ) {
1029 // the slot is converting to array node right now
1030 while ( (slot = pArr->load(memory_model::memory_order_acquire)).bits() == base_class::flag_array_converting ) {
1032 stats().onSlotConverting();
1036 assert( slot.ptr() != nullptr );
1037 assert( slot.bits() == base_class::flag_array_node );
1038 clear_array( to_array( slot.ptr()), array_node_size() );
1043 if ( pArr->compare_exchange_strong( slot, node_ptr(), memory_model::memory_order_acquire, atomics::memory_order_relaxed )) {
1045 gc::template retire<disposer>( slot.ptr() );
1047 stats().onEraseSuccess();
1059 value_type * search( hash_type const& hash, typename gc::Guard& guard )
1061 traverse_data pos( hash, *this );
1062 hash_comparator cmp;
1065 node_ptr slot = base_class::traverse( pos );
1066 assert(slot.bits() == 0);
1068 // protect data node by hazard pointer
1069 if (guard.protect( pos.pArr->nodes[pos.nSlot], [](node_ptr p) -> value_type * { return p.ptr(); }) != slot) {
1070 // slot value has been changed - retry
1071 stats().onSlotChanged();
1073 else if (slot.ptr() && cmp(hash, hash_accessor()(*slot.ptr())) == 0) {
1075 stats().onFindSuccess();
1078 stats().onFindFailed();
1083 template <typename Predicate>
1084 value_type * do_erase( hash_type const& hash, typename gc::Guard& guard, Predicate pred )
1086 traverse_data pos( hash, *this );
1087 hash_comparator cmp;
1089 node_ptr slot = base_class::traverse( pos );
1090 assert(slot.bits() == 0);
1092 // protect data node by hazard pointer
1093 if (guard.protect( pos.pArr->nodes[pos.nSlot], [](node_ptr p) -> value_type * { return p.ptr(); }) != slot) {
1094 // slot value has been changed - retry
1095 stats().onSlotChanged();
1097 else if (slot.ptr()) {
1098 if (cmp(hash, hash_accessor()(*slot.ptr())) == 0 && pred(*slot.ptr())) {
1099 // item found - replace it with nullptr
1100 if ( pos.pArr->nodes[pos.nSlot].compare_exchange_strong(slot, node_ptr(nullptr), memory_model::memory_order_acquire, atomics::memory_order_relaxed)) {
1101 // slot is guarded by HP
1102 gc::template retire<disposer>(slot.ptr());
1104 stats().onEraseSuccess();
1108 stats().onEraseRetry();
1111 stats().onEraseFailed();
1115 // the slot is empty
1116 stats().onEraseFailed();
1122 bool do_erase_at( iterator_base const& iter )
1124 if ( iter.m_set != this )
1126 if ( iter.m_pNode == head() && iter.m_idx >= head_size())
1128 if ( iter.m_idx >= array_node_size() )
1132 node_ptr slot = iter.m_pNode->nodes[iter.m_idx].load( memory_model::memory_order_acquire );
1133 if ( slot.bits() == 0 && slot.ptr() == iter.pointer() ) {
1134 if ( iter.m_pNode->nodes[iter.m_idx].compare_exchange_strong(slot, node_ptr(nullptr), memory_model::memory_order_acquire, atomics::memory_order_relaxed) ) {
1135 // the item is guarded by iterator, so we may retire it safely
1136 gc::template retire<disposer>( slot.ptr() );
1138 stats().onEraseSuccess();
1147 template <typename Func>
1148 std::pair<bool, bool> do_update( value_type& val, Func f, bool bInsert = true )
1150 hash_type const& hash = hash_accessor()( val );
1151 traverse_data pos( hash, *this );
1152 hash_comparator cmp;
1153 typename gc::template GuardArray<2> guards;
1156 node_ptr slot = base_class::traverse( pos );
1157 assert(slot.bits() == 0);
1159 // protect data node by hazard pointer
1160 if (guards.protect(0, pos.pArr->nodes[pos.nSlot], [](node_ptr p) -> value_type * { return p.ptr(); }) != slot) {
1161 // slot value has been changed - retry
1162 stats().onSlotChanged();
1164 else if (slot.ptr()) {
1165 if (cmp(hash, hash_accessor()(*slot.ptr())) == 0) {
1166 // the item with that hash value already exists
1167 // Replace it with val
1168 if (slot.ptr() == &val) {
1169 stats().onUpdateExisting();
1170 return std::make_pair(true, false);
1173 if ( pos.pArr->nodes[pos.nSlot].compare_exchange_strong(slot, node_ptr(&val), memory_model::memory_order_release, atomics::memory_order_relaxed)) {
1174 // slot can be disposed
1176 gc::template retire<disposer>(slot.ptr());
1177 stats().onUpdateExisting();
1178 return std::make_pair(true, false);
1181 stats().onUpdateRetry();
1186 // the slot must be expanded
1187 base_class::expand_slot( pos, slot );
1190 stats().onUpdateFailed();
1191 return std::make_pair(false, false);
1195 // the slot is empty, try to insert data node
1198 if ( pos.pArr->nodes[pos.nSlot].compare_exchange_strong(pNull, node_ptr(&val), memory_model::memory_order_release, atomics::memory_order_relaxed))
1200 // the new data node has been inserted
1203 stats().onUpdateNew();
1204 stats().height( pos.nHeight );
1205 return std::make_pair(true, true);
1209 stats().onUpdateFailed();
1210 return std::make_pair(false, false);
1213 // insert failed - slot has been changed by another thread
1215 stats().onUpdateRetry();
1221 }} // namespace cds::intrusive
1223 #endif // #ifndef CDSLIB_INTRUSIVE_IMPL_FELDMAN_HASHSET_H