2 This file is a part of libcds - Concurrent Data Structures library
4 (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016
6 Source code repo: http://github.com/khizmax/libcds/
7 Download: http://sourceforge.net/projects/libcds/files/
9 Redistribution and use in source and binary forms, with or without
10 modification, are permitted provided that the following conditions are met:
12 * Redistributions of source code must retain the above copyright notice, this
13 list of conditions and the following disclaimer.
15 * Redistributions in binary form must reproduce the above copyright notice,
16 this list of conditions and the following disclaimer in the documentation
17 and/or other materials provided with the distribution.
19 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
20 AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
21 IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
22 DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
23 FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
24 DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
25 SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
26 CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
27 OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
28 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
31 #ifndef CDSLIB_INTRUSIVE_IMPL_FELDMAN_HASHSET_H
32 #define CDSLIB_INTRUSIVE_IMPL_FELDMAN_HASHSET_H
34 #include <functional> // std::ref
35 #include <iterator> // std::iterator_traits
38 #include <cds/intrusive/details/feldman_hashset_base.h>
39 #include <cds/details/allocator.h>
41 namespace cds { namespace intrusive {
42 /// Intrusive hash set based on multi-level array
43 /** @ingroup cds_intrusive_map
44 @anchor cds_intrusive_FeldmanHashSet_hp
47 - [2013] Steven Feldman, Pierre LaBorde, Damian Dechev "Concurrent Multi-level Arrays:
48 Wait-free Extensible Hash Maps"
50 [From the paper] The hardest problem encountered while developing a parallel hash map is how to perform
51 a global resize, the process of redistributing the elements in a hash map that occurs when adding new
52 buckets. The negative impact of blocking synchronization is multiplied during a global resize, because all
53 threads will be forced to wait on the thread that is performing the involved process of resizing the hash map
54 and redistributing the elements. \p %FeldmanHashSet implementation avoids global resizes through new array
55 allocation. By allowing concurrent expansion this structure is free from the overhead of an explicit resize,
56 which facilitates concurrent operations.
58 The presented design includes dynamic hashing, the use of sub-arrays within the hash map data structure;
59 which, in combination with <b>perfect hashing</b>, means that each element has a unique final, as well as current, position.
60 It is important to note that the perfect hash function required by our hash map is trivial to realize as
61 any hash function that permutes the bits of the key is suitable. This is possible because of our approach
62 to the hash function; we require that it produces hash values that are equal in size to that of the key.
63 We know that if we expand the hash map a fixed number of times there can be no collision as duplicate keys
64 are not provided for in the standard semantics of a hash map.
66 \p %FeldmanHashSet is a multi-level array which has a structure similar to a tree:
67 @image html feldman_hashset.png
68 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.
69 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
70 with that key; it is a simple struct holding two variables. A \p dataNode in the multi-level array could be marked.
71 A \p markedDataNode refers to a pointer to a \p dataNode that has been bitmarked at the least significant bit (LSB)
72 of the pointer to the node. This signifies that this \p dataNode is contended. An expansion must occur at this node;
73 any thread that sees this \p markedDataNode will try to replace it with an \p arrayNode; which is a position that holds
74 an array of nodes. The pointer to an \p arrayNode is differentiated from that of a pointer to a \p dataNode by a bitmark
75 on the second-least significant bit.
77 \p %FeldmanHashSet multi-level array is similar to a tree in that we keep a pointer to the root, which is a memory array
78 called \p head. The length of the \p head memory array is unique, whereas every other \p arrayNode has a uniform length;
79 a normal \p arrayNode has a fixed power-of-two length equal to the binary logarithm of a variable called \p arrayLength.
80 The maximum depth of the tree, \p maxDepth, is the maximum number of pointers that must be followed to reach any node.
81 We define \p currentDepth as the number of memory arrays that we need to traverse to reach the \p arrayNode on which
82 we need to operate; this is initially one, because of \p head.
84 That approach to the structure of the hash set uses an extensible hashing scheme; <b> the hash value is treated as a bit
85 string</b> and rehash incrementally.
87 @note Two important things you should keep in mind when you're using \p %FeldmanHashSet:
88 - all keys must be fixed-size. It means that you cannot use \p std::string as a key for \p %FeldmanHashSet.
89 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>,
90 <a href="https://en.wikipedia.org/wiki/MurmurHash">MurmurHash</a>, <a href="https://en.wikipedia.org/wiki/CityHash">CityHash</a>
91 or its successor <a href="https://code.google.com/p/farmhash/">FarmHash</a> and so on, which
92 converts variable-length strings to fixed-length bit-strings, and use that hash as a key in \p %FeldmanHashSet.
93 - \p %FeldmanHashSet uses a perfect hashing. It means that if two different keys, for example, of type \p std::string,
94 have identical hash then you cannot insert both that keys in the set. \p %FeldmanHashSet does not maintain the key,
95 it maintains its fixed-size hash value.
97 The set supports @ref cds_intrusive_FeldmanHashSet_iterators "bidirectional thread-safe iterators".
100 - \p GC - safe memory reclamation schema. Can be \p gc::HP, \p gc::DHP or one of \ref cds_urcu_type "RCU type"
101 - \p T - a value type to be stored in the set
102 - \p Traits - type traits, the structure based on \p feldman_hashset::traits or result of \p feldman_hashset::make_traits metafunction.
103 \p Traits is the mandatory argument because it has one mandatory type - an @ref feldman_hashset::traits::hash_accessor "accessor"
104 to hash value of \p T. The set algorithm does not calculate that hash value.
106 There are several specializations of \p %FeldmanHashSet for each \p GC. You should include:
107 - <tt><cds/intrusive/feldman_hashset_hp.h></tt> for \p gc::HP garbage collector
108 - <tt><cds/intrusive/feldman_hashset_dhp.h></tt> for \p gc::DHP garbage collector
109 - <tt><cds/intrusive/feldman_hashset_rcu.h></tt> for \ref cds_intrusive_FeldmanHashSet_rcu "RCU type". RCU specialization
110 has a slightly different interface.
115 #ifdef CDS_DOXYGEN_INVOKED
116 ,typename Traits = feldman_hashset::traits
121 class FeldmanHashSet: protected feldman_hashset::multilevel_array<T, Traits>
124 typedef feldman_hashset::multilevel_array<T, Traits> base_class;
128 typedef GC gc; ///< Garbage collector
129 typedef T value_type; ///< type of value stored in the set
130 typedef Traits traits; ///< Traits template parameter, see \p feldman_hashset::traits
132 typedef typename traits::hash_accessor hash_accessor; ///< Hash accessor functor
133 typedef typename base_class::hash_type hash_type; ///< Hash type deduced from \p hash_accessor return type
134 typedef typename traits::disposer disposer; ///< data node disposer
135 typedef typename base_class::hash_comparator hash_comparator; ///< hash compare functor based on \p traits::compare and \p traits::less options
137 typedef typename traits::item_counter item_counter; ///< Item counter type
138 typedef typename traits::node_allocator node_allocator; ///< Array node allocator
139 typedef typename traits::memory_model memory_model; ///< Memory model
140 typedef typename traits::back_off back_off; ///< Backoff strategy
141 typedef typename traits::stat stat; ///< Internal statistics type
143 typedef typename gc::template guarded_ptr< value_type > guarded_ptr; ///< Guarded pointer
145 /// Count of hazard pointers required
146 static CDS_CONSTEXPR size_t const c_nHazardPtrCount = 2;
149 typedef feldman_hashset::level_statistics level_statistics;
153 typedef typename base_class::node_ptr node_ptr;
154 typedef typename base_class::atomic_node_ptr atomic_node_ptr;
155 typedef typename base_class::array_node array_node;
156 typedef typename base_class::traverse_data traverse_data;
158 using base_class::to_array;
159 using base_class::to_node;
160 using base_class::stats;
161 using base_class::head;
162 using base_class::metrics;
169 friend class FeldmanHashSet;
172 array_node * m_pNode; ///< current array node
173 size_t m_idx; ///< current position in m_pNode
174 typename gc::Guard m_guard; ///< HP guard
175 FeldmanHashSet const* m_set; ///< Hash set
178 iterator_base() CDS_NOEXCEPT
184 iterator_base( iterator_base const& rhs ) CDS_NOEXCEPT
185 : m_pNode( rhs.m_pNode )
189 m_guard.copy( rhs.m_guard );
192 iterator_base& operator=( iterator_base const& rhs ) CDS_NOEXCEPT
194 m_pNode = rhs.m_pNode;
197 m_guard.copy( rhs.m_guard );
201 iterator_base& operator++()
207 iterator_base& operator--()
218 bool operator ==( iterator_base const& rhs ) const CDS_NOEXCEPT
220 return m_pNode == rhs.m_pNode && m_idx == rhs.m_idx && m_set == rhs.m_set;
223 bool operator !=( iterator_base const& rhs ) const CDS_NOEXCEPT
225 return !( *this == rhs );
229 iterator_base( FeldmanHashSet const& set, array_node * pNode, size_t idx, bool )
235 iterator_base( FeldmanHashSet const& set, array_node * pNode, size_t idx )
243 value_type * pointer() const CDS_NOEXCEPT
245 return m_guard.template get<value_type>();
250 assert( m_set != nullptr );
251 assert( m_pNode != nullptr );
253 size_t const arrayNodeSize = m_set->array_node_size();
254 size_t const headSize = m_set->head_size();
255 array_node * pNode = m_pNode;
256 size_t idx = m_idx + 1;
257 size_t nodeSize = m_pNode->pParent? arrayNodeSize : headSize;
260 if ( idx < nodeSize ) {
261 node_ptr slot = pNode->nodes[idx].load( memory_model::memory_order_acquire );
262 if ( slot.bits() == base_class::flag_array_node ) {
263 // array node, go down the tree
264 assert( slot.ptr() != nullptr );
265 pNode = to_array( slot.ptr());
267 nodeSize = arrayNodeSize;
269 else if ( slot.bits() == base_class::flag_array_converting ) {
270 // the slot is converting to array node right now - skip the node
276 if ( m_guard.protect( pNode->nodes[idx], []( node_ptr p ) -> value_type* { return p.ptr(); }) == slot ) {
287 if ( pNode->pParent ) {
288 idx = pNode->idxParent + 1;
289 pNode = pNode->pParent;
290 nodeSize = pNode->pParent ? arrayNodeSize : headSize;
294 assert( pNode == m_set->head());
295 assert( idx == headSize );
306 assert( m_set != nullptr );
307 assert( m_pNode != nullptr );
309 size_t const arrayNodeSize = m_set->array_node_size();
310 size_t const headSize = m_set->head_size();
311 size_t const endIdx = size_t(0) - 1;
313 array_node * pNode = m_pNode;
314 size_t idx = m_idx - 1;
315 size_t nodeSize = m_pNode->pParent? arrayNodeSize : headSize;
318 if ( idx != endIdx ) {
319 node_ptr slot = pNode->nodes[idx].load( memory_model::memory_order_acquire );
320 if ( slot.bits() == base_class::flag_array_node ) {
321 // array node, go down the tree
322 assert( slot.ptr() != nullptr );
323 pNode = to_array( slot.ptr());
324 nodeSize = arrayNodeSize;
327 else if ( slot.bits() == base_class::flag_array_converting ) {
328 // the slot is converting to array node right now - skip the node
334 if ( m_guard.protect( pNode->nodes[idx], []( node_ptr p ) -> value_type* { return p.ptr(); }) == slot ) {
345 if ( pNode->pParent ) {
346 idx = pNode->idxParent - 1;
347 pNode = pNode->pParent;
348 nodeSize = pNode->pParent ? arrayNodeSize : headSize;
352 assert( pNode == m_set->head());
353 assert( idx == endIdx );
363 template <class Iterator>
364 Iterator init_begin() const
366 return Iterator( *this, head(), size_t(0) - 1 );
369 template <class Iterator>
370 Iterator init_end() const
372 return Iterator( *this, head(), head_size(), false );
375 template <class Iterator>
376 Iterator init_rbegin() const
378 return Iterator( *this, head(), head_size());
381 template <class Iterator>
382 Iterator init_rend() const
384 return Iterator( *this, head(), size_t(0) - 1, false );
387 /// Bidirectional iterator class
388 template <bool IsConst>
389 class bidirectional_iterator: protected iterator_base
391 friend class FeldmanHashSet;
394 static CDS_CONSTEXPR bool const c_bConstantIterator = IsConst;
397 typedef typename std::conditional< IsConst, value_type const*, value_type*>::type value_ptr; ///< Value pointer
398 typedef typename std::conditional< IsConst, value_type const&, value_type&>::type value_ref; ///< Value reference
401 bidirectional_iterator() CDS_NOEXCEPT
404 bidirectional_iterator( bidirectional_iterator const& rhs ) CDS_NOEXCEPT
405 : iterator_base( rhs )
408 bidirectional_iterator& operator=( bidirectional_iterator const& rhs ) CDS_NOEXCEPT
410 iterator_base::operator=( rhs );
414 bidirectional_iterator& operator++()
416 iterator_base::operator++();
420 bidirectional_iterator& operator--()
422 iterator_base::operator--();
426 value_ptr operator ->() const CDS_NOEXCEPT
428 return iterator_base::pointer();
431 value_ref operator *() const CDS_NOEXCEPT
433 value_ptr p = iterator_base::pointer();
440 iterator_base::release();
443 template <bool IsConst2>
444 bool operator ==( bidirectional_iterator<IsConst2> const& rhs ) const CDS_NOEXCEPT
446 return iterator_base::operator==( rhs );
449 template <bool IsConst2>
450 bool operator !=( bidirectional_iterator<IsConst2> const& rhs ) const CDS_NOEXCEPT
452 return !( *this == rhs );
456 bidirectional_iterator( FeldmanHashSet& set, array_node * pNode, size_t idx, bool )
457 : iterator_base( set, pNode, idx, false )
460 bidirectional_iterator( FeldmanHashSet& set, array_node * pNode, size_t idx )
461 : iterator_base( set, pNode, idx )
465 /// Reverse bidirectional iterator
466 template <bool IsConst>
467 class reverse_bidirectional_iterator : public iterator_base
469 friend class FeldmanHashSet;
472 typedef typename std::conditional< IsConst, value_type const*, value_type*>::type value_ptr; ///< Value pointer
473 typedef typename std::conditional< IsConst, value_type const&, value_type&>::type value_ref; ///< Value reference
476 reverse_bidirectional_iterator() CDS_NOEXCEPT
480 reverse_bidirectional_iterator( reverse_bidirectional_iterator const& rhs ) CDS_NOEXCEPT
481 : iterator_base( rhs )
484 reverse_bidirectional_iterator& operator=( reverse_bidirectional_iterator const& rhs) CDS_NOEXCEPT
486 iterator_base::operator=( rhs );
490 reverse_bidirectional_iterator& operator++()
492 iterator_base::operator--();
496 reverse_bidirectional_iterator& operator--()
498 iterator_base::operator++();
502 value_ptr operator ->() const CDS_NOEXCEPT
504 return iterator_base::pointer();
507 value_ref operator *() const CDS_NOEXCEPT
509 value_ptr p = iterator_base::pointer();
516 iterator_base::release();
519 template <bool IsConst2>
520 bool operator ==( reverse_bidirectional_iterator<IsConst2> const& rhs ) const
522 return iterator_base::operator==( rhs );
525 template <bool IsConst2>
526 bool operator !=( reverse_bidirectional_iterator<IsConst2> const& rhs )
528 return !( *this == rhs );
532 reverse_bidirectional_iterator( FeldmanHashSet& set, array_node * pNode, size_t idx, bool )
533 : iterator_base( set, pNode, idx, false )
536 reverse_bidirectional_iterator( FeldmanHashSet& set, array_node * pNode, size_t idx )
537 : iterator_base( set, pNode, idx, false )
539 iterator_base::backward();
545 #ifdef CDS_DOXYGEN_INVOKED
546 typedef implementation_defined iterator; ///< @ref cds_intrusive_FeldmanHashSet_iterators "bidirectional iterator" type
547 typedef implementation_defined const_iterator; ///< @ref cds_intrusive_FeldmanHashSet_iterators "bidirectional const iterator" type
548 typedef implementation_defined reverse_iterator; ///< @ref cds_intrusive_FeldmanHashSet_iterators "bidirectional reverse iterator" type
549 typedef implementation_defined const_reverse_iterator; ///< @ref cds_intrusive_FeldmanHashSet_iterators "bidirectional reverse const iterator" type
551 typedef bidirectional_iterator<false> iterator;
552 typedef bidirectional_iterator<true> const_iterator;
553 typedef reverse_bidirectional_iterator<false> reverse_iterator;
554 typedef reverse_bidirectional_iterator<true> const_reverse_iterator;
559 item_counter m_ItemCounter; ///< Item counter
563 /// Creates empty set
565 @param head_bits: 2<sup>head_bits</sup> specifies the size of head array, minimum is 4.
566 @param array_bits: 2<sup>array_bits</sup> specifies the size of array node, minimum is 2.
568 Equation for \p head_bits and \p array_bits:
570 sizeof( hash_type ) * 8 == head_bits + N * array_bits
572 where \p N is multi-level array depth.
574 FeldmanHashSet( size_t head_bits = 8, size_t array_bits = 4 )
575 : base_class( head_bits, array_bits )
578 /// Destructs the set and frees all data
586 The function inserts \p val in the set if it does not contain
587 an item with that hash.
589 Returns \p true if \p val is placed into the set, \p false otherwise.
591 bool insert( value_type& val )
593 return insert( val, []( value_type& ) {} );
598 This function is intended for derived non-intrusive containers.
600 The function allows to split creating of new item into two part:
601 - create item with key only
602 - insert new item into the set
603 - if inserting is success, calls \p f functor to initialize \p val.
605 The functor signature is:
607 void func( value_type& val );
609 where \p val is the item inserted.
611 The user-defined functor is called only if the inserting is success.
613 @warning See \ref cds_intrusive_item_creating "insert item troubleshooting".
615 template <typename Func>
616 bool insert( value_type& val, Func f )
618 hash_type const& hash = hash_accessor()( val );
619 traverse_data pos( hash, *this );
621 typename gc::template GuardArray<2> guards;
623 guards.assign( 1, &val );
625 node_ptr slot = base_class::traverse( pos );
626 assert( slot.bits() == 0 );
628 // protect data node by hazard pointer
629 if ( guards.protect( 0, pos.pArr->nodes[pos.nSlot], []( node_ptr p ) -> value_type* { return p.ptr(); }) != slot ) {
630 // slot value has been changed - retry
631 stats().onSlotChanged();
633 else if ( slot.ptr()) {
634 if ( cmp( hash, hash_accessor()( *slot.ptr())) == 0 ) {
635 // the item with that hash value already exists
636 stats().onInsertFailed();
640 // the slot must be expanded
641 base_class::expand_slot( pos, slot );
644 // the slot is empty, try to insert data node
646 if ( pos.pArr->nodes[pos.nSlot].compare_exchange_strong( pNull, node_ptr( &val ), memory_model::memory_order_release, atomics::memory_order_relaxed ))
648 // the new data node has been inserted
651 stats().onInsertSuccess();
652 stats().height( pos.nHeight );
656 // insert failed - slot has been changed by another thread
658 stats().onInsertRetry();
665 Performs inserting or updating the item with hash value equal to \p val.
666 - If hash value is found then existing item is replaced with \p val, old item is disposed
667 with \p Traits::disposer. Note that the disposer is called by \p GC asynchronously.
668 The function returns <tt> std::pair<true, false> </tt>
669 - If hash value is not found and \p bInsert is \p true then \p val is inserted,
670 the function returns <tt> std::pair<true, true> </tt>
671 - If hash value is not found and \p bInsert is \p false then the set is unchanged,
672 the function returns <tt> std::pair<false, false> </tt>
674 Returns <tt> std::pair<bool, bool> </tt> where \p first is \p true if operation is successful
675 (i.e. the item has been inserted or updated),
676 \p second is \p true if new item has been added or \p false if the set contains that hash.
678 std::pair<bool, bool> update( value_type& val, bool bInsert = true )
680 return do_update( val, []( value_type&, value_type* ) {}, bInsert );
683 /// Unlinks the item \p val from the set
685 The function searches the item \p val in the set and unlink it
686 if it is found and its address is equal to <tt>&val</tt>.
688 The function returns \p true if success and \p false otherwise.
690 bool unlink( value_type const& val )
692 typename gc::Guard guard;
693 auto pred = [&val]( value_type const& item ) -> bool { return &item == &val; };
694 value_type * p = do_erase( hash_accessor()( val ), guard, std::ref( pred ));
698 /// Deletes the item from the set
700 The function searches \p hash in the set,
701 unlinks the item found, and returns \p true.
702 If that item is not found the function returns \p false.
704 The \ref disposer specified in \p Traits is called by garbage collector \p GC asynchronously.
706 bool erase( hash_type const& hash )
708 return erase( hash, []( value_type const& ) {} );
711 /// Deletes the item from the set
713 The function searches \p hash in the set,
714 call \p f functor with item found, and unlinks it from the set.
715 The \ref disposer specified in \p Traits is called
716 by garbage collector \p GC asynchronously.
718 The \p Func interface is
721 void operator()( value_type& item );
725 If \p hash is not found the function returns \p false.
727 template <typename Func>
728 bool erase( hash_type const& hash, Func f )
730 typename gc::Guard guard;
731 value_type * p = do_erase( hash, guard, []( value_type const&) -> bool {return true; } );
733 // p is guarded by HP
741 /// Deletes the item pointed by iterator \p iter
743 Returns \p true if the operation is successful, \p false otherwise.
745 The function does not invalidate the iterator, it remains valid and can be used for further traversing.
747 bool erase_at( iterator const& iter )
749 return do_erase_at( iter );
752 bool erase_at( reverse_iterator const& iter )
754 return do_erase_at( iter );
758 /// Extracts the item with specified \p hash
760 The function searches \p hash in the set,
761 unlinks it from the set, and returns an guarded pointer to the item extracted.
762 If \p hash is not found the function returns an empty guarded pointer.
764 The \p disposer specified in \p Traits class' template parameter is called automatically
765 by garbage collector \p GC when returned \ref guarded_ptr object to be destroyed or released.
766 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
770 typedef cds::intrusive::FeldmanHashSet< your_template_args > my_set;
774 my_set::guarded_ptr gp( theSet.extract( 5 ));
779 // Destructor of gp releases internal HP guard
783 guarded_ptr extract( hash_type const& hash )
785 typename gc::Guard guard;
786 if ( do_erase( hash, guard, []( value_type const&) -> bool {return true;} ))
787 return guarded_ptr( std::move( guard ));
788 return guarded_ptr();
791 /// Finds an item by it's \p hash
793 The function searches the item by \p hash and calls the functor \p f for item found.
794 The interface of \p Func functor is:
797 void operator()( value_type& item );
800 where \p item is the item found.
802 The functor may change non-key fields of \p item. Note that the functor is only guarantee
803 that \p item cannot be disposed during the functor is executing.
804 The functor does not serialize simultaneous access to the set's \p item. If such access is
805 possible you must provide your own synchronization schema on item level to prevent unsafe item modifications.
807 The function returns \p true if \p hash is found, \p false otherwise.
809 template <typename Func>
810 bool find( hash_type const& hash, Func f )
812 typename gc::Guard guard;
813 value_type * p = search( hash, guard );
815 // p is guarded by HP
823 /// Checks whether the set contains \p hash
825 The function searches the item by its \p hash
826 and returns \p true if it is found, or \p false otherwise.
828 bool contains( hash_type const& hash )
830 return find( hash, []( value_type& ) {} );
833 /// Finds an item by it's \p hash and returns the item found
835 The function searches the item by its \p hash
836 and returns the guarded pointer to the item found.
837 If \p hash is not found the function returns an empty \p guarded_ptr.
839 @note Each \p guarded_ptr object uses one GC's guard which can be limited resource.
843 typedef cds::intrusive::FeldmanHashSet< your_template_params > my_set;
847 my_set::guarded_ptr gp( theSet.get( 5 ));
848 if ( theSet.get( 5 )) {
852 // Destructor of guarded_ptr releases internal HP guard
856 guarded_ptr get( hash_type const& hash )
858 typename gc::Guard guard;
859 if ( search( hash, guard ))
860 return guarded_ptr( std::move( guard ));
861 return guarded_ptr();
864 /// Clears the set (non-atomic)
866 The function unlink all data node from the set.
867 The function is not atomic but is thread-safe.
868 After \p %clear() the set may not be empty because another threads may insert items.
870 For each item the \p disposer is called after unlinking.
874 clear_array( head(), head_size());
877 /// Checks if the set is empty
879 Emptiness is checked by item counting: if item count is zero then the set is empty.
880 Thus, the correct item counting feature is an important part of the set implementation.
887 /// Returns item count in the set
890 return m_ItemCounter;
893 /// Returns const reference to internal statistics
894 stat const& statistics() const
899 /// Returns the size of head node
900 using base_class::head_size;
902 /// Returns the size of the array node
903 using base_class::array_node_size;
905 /// Collects tree level statistics into \p stat
907 The function traverses the set and collects statistics for each level of the tree
908 into \p feldman_hashset::level_statistics struct. The element of \p stat[i]
909 represents statistics for level \p i, level 0 is head array.
910 The function is thread-safe and may be called in multi-threaded environment.
912 Result can be useful for estimating efficiency of hash functor you use.
914 void get_level_statistics( std::vector< feldman_hashset::level_statistics>& stat ) const
916 base_class::get_level_statistics( stat );
920 ///@name Thread-safe iterators
921 /** @anchor cds_intrusive_FeldmanHashSet_iterators
922 The set supports thread-safe iterators: you may iterate over the set in multi-threaded environment.
923 It is guaranteed that the iterators will remain valid even if another thread deletes the node the iterator points to:
924 Hazard Pointer embedded into the iterator object protects the node from physical reclamation.
926 @note Since the iterator object contains hazard pointer that is a thread-local resource,
927 the iterator should not be passed to another thread.
929 Each iterator object supports the common interface:
930 - dereference operators:
932 value_type [const] * operator ->() noexcept
933 value_type [const] & operator *() noexcept
935 - pre-increment and pre-decrement. Post-operators is not supported
936 - equality operators <tt>==</tt> and <tt>!=</tt>.
937 Iterators are equal iff they point to the same cell of the same array node.
938 Note that for two iterators \p it1 and \p it2, the conditon <tt> it1 == it2 </tt>
939 does not entail <tt> &(*it1) == &(*it2) </tt>: welcome to concurrent containers
940 - helper member function \p release() that clears internal hazard pointer.
941 After \p release() the iterator points to \p nullptr but it still remain valid: further iterating is possible.
943 During iteration you may safely erase any item from the set;
944 @ref erase_at() function call doesn't invalidate any iterator.
945 If some iterator points to the item to be erased, that item is not deleted immediately
946 but only after that iterator will be advanced forward or backward.
948 @note It is possible the item can be iterated more that once, for example, if an iterator points to the item
949 in array node that is being splitted.
953 /// Returns an iterator to the beginning of the set
956 return iterator( *this, head(), size_t(0) - 1 );
959 /// Returns an const iterator to the beginning of the set
960 const_iterator begin() const
962 return const_iterator( *this, head(), size_t(0) - 1 );
965 /// Returns an const iterator to the beginning of the set
966 const_iterator cbegin()
968 return const_iterator( *this, head(), size_t(0) - 1 );
971 /// 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.
974 return iterator( *this, head(), head_size(), false );
977 /// 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.
978 const_iterator end() const
980 return const_iterator( *this, head(), head_size(), false );
983 /// 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.
984 const_iterator cend()
986 return const_iterator( *this, head(), head_size(), false );
989 /// Returns a reverse iterator to the first element of the reversed set
990 reverse_iterator rbegin()
992 return reverse_iterator( *this, head(), head_size());
995 /// Returns a const reverse iterator to the first element of the reversed set
996 const_reverse_iterator rbegin() const
998 return const_reverse_iterator( *this, head(), head_size());
1001 /// Returns a const reverse iterator to the first element of the reversed set
1002 const_reverse_iterator crbegin()
1004 return const_reverse_iterator( *this, head(), head_size());
1007 /// Returns a reverse iterator to the element following the last element of the reversed set
1009 It corresponds to the element preceding the first element of the non-reversed container.
1010 This element acts as a placeholder, attempting to access it results in undefined behavior.
1012 reverse_iterator rend()
1014 return reverse_iterator( *this, head(), size_t(0) - 1, false );
1017 /// Returns a const reverse iterator to the element following the last element of the reversed set
1019 It corresponds to the element preceding the first element of the non-reversed container.
1020 This element acts as a placeholder, attempting to access it results in undefined behavior.
1022 const_reverse_iterator rend() const
1024 return const_reverse_iterator( *this, head(), size_t(0) - 1, false );
1027 /// Returns a const reverse iterator to the element following the last element of the reversed set
1029 It corresponds to the element preceding the first element of the non-reversed container.
1030 This element acts as a placeholder, attempting to access it results in undefined behavior.
1032 const_reverse_iterator crend()
1034 return const_reverse_iterator( *this, head(), size_t(0) - 1, false );
1040 void clear_array( array_node * pArrNode, size_t nSize )
1044 for ( atomic_node_ptr * pArr = pArrNode->nodes, *pLast = pArr + nSize; pArr != pLast; ++pArr ) {
1046 node_ptr slot = pArr->load( memory_model::memory_order_acquire );
1047 if ( slot.bits() == base_class::flag_array_node ) {
1048 // array node, go down the tree
1049 assert( slot.ptr() != nullptr );
1050 clear_array( to_array( slot.ptr()), array_node_size());
1053 else if ( slot.bits() == base_class::flag_array_converting ) {
1054 // the slot is converting to array node right now
1055 while (( slot = pArr->load( memory_model::memory_order_acquire )).bits() == base_class::flag_array_converting ) {
1057 stats().onSlotConverting();
1061 assert( slot.ptr() != nullptr );
1062 assert( slot.bits() == base_class::flag_array_node );
1063 clear_array( to_array( slot.ptr()), array_node_size());
1068 if ( pArr->compare_exchange_strong( slot, node_ptr(), memory_model::memory_order_acquire, atomics::memory_order_relaxed )) {
1070 gc::template retire<disposer>( slot.ptr());
1072 stats().onEraseSuccess();
1084 value_type * search( hash_type const& hash, typename gc::Guard& guard )
1086 traverse_data pos( hash, *this );
1087 hash_comparator cmp;
1090 node_ptr slot = base_class::traverse( pos );
1091 assert( slot.bits() == 0 );
1093 // protect data node by hazard pointer
1094 if ( guard.protect( pos.pArr->nodes[pos.nSlot], []( node_ptr p ) -> value_type* { return p.ptr(); }) != slot) {
1095 // slot value has been changed - retry
1096 stats().onSlotChanged();
1099 else if ( slot.ptr() && cmp( hash, hash_accessor()( *slot.ptr())) == 0 ) {
1101 stats().onFindSuccess();
1104 stats().onFindFailed();
1109 template <typename Predicate>
1110 value_type * do_erase( hash_type const& hash, typename gc::Guard& guard, Predicate pred )
1112 traverse_data pos( hash, *this );
1113 hash_comparator cmp;
1115 node_ptr slot = base_class::traverse( pos );
1116 assert( slot.bits() == 0 );
1118 // protect data node by hazard pointer
1119 if ( guard.protect( pos.pArr->nodes[pos.nSlot], []( node_ptr p ) -> value_type* { return p.ptr(); }) != slot ) {
1120 // slot value has been changed - retry
1121 stats().onSlotChanged();
1123 else if ( slot.ptr()) {
1124 if ( cmp( hash, hash_accessor()( *slot.ptr())) == 0 && pred( *slot.ptr())) {
1125 // item found - replace it with nullptr
1126 if ( pos.pArr->nodes[pos.nSlot].compare_exchange_strong( slot, node_ptr( nullptr ), memory_model::memory_order_acquire, atomics::memory_order_relaxed)) {
1127 // slot is guarded by HP
1128 gc::template retire<disposer>( slot.ptr());
1130 stats().onEraseSuccess();
1134 stats().onEraseRetry();
1137 stats().onEraseFailed();
1141 // the slot is empty
1142 stats().onEraseFailed();
1148 bool do_erase_at( iterator_base const& iter )
1150 if ( iter.m_set != this )
1152 if ( iter.m_pNode == head()) {
1153 if ( iter.m_idx >= head_size())
1156 else if ( iter.m_idx >= array_node_size())
1160 node_ptr slot = iter.m_pNode->nodes[iter.m_idx].load( memory_model::memory_order_acquire );
1161 if ( slot.bits() == 0 && slot.ptr() == iter.pointer()) {
1162 if ( iter.m_pNode->nodes[iter.m_idx].compare_exchange_strong( slot, node_ptr( nullptr ), memory_model::memory_order_acquire, atomics::memory_order_relaxed )) {
1163 // the item is guarded by iterator, so we may retire it safely
1164 gc::template retire<disposer>( slot.ptr());
1166 stats().onEraseSuccess();
1175 template <typename Func>
1176 std::pair<bool, bool> do_update( value_type& val, Func f, bool bInsert = true )
1178 hash_type const& hash = hash_accessor()( val );
1179 traverse_data pos( hash, *this );
1180 hash_comparator cmp;
1181 typename gc::template GuardArray<2> guards;
1183 guards.assign( 1, &val );
1185 node_ptr slot = base_class::traverse( pos );
1186 assert( slot.bits() == 0 );
1188 // protect data node by hazard pointer
1189 if ( guards.protect( 0, pos.pArr->nodes[pos.nSlot], []( node_ptr p ) -> value_type* { return p.ptr(); }) != slot ) {
1190 // slot value has been changed - retry
1191 stats().onSlotChanged();
1193 else if ( slot.ptr()) {
1194 if ( cmp( hash, hash_accessor()( *slot.ptr())) == 0 ) {
1195 // the item with that hash value already exists
1196 // Replace it with val
1197 if ( slot.ptr() == &val ) {
1198 stats().onUpdateExisting();
1199 return std::make_pair( true, false );
1202 if ( pos.pArr->nodes[pos.nSlot].compare_exchange_strong( slot, node_ptr( &val ), memory_model::memory_order_release, atomics::memory_order_relaxed )) {
1203 // slot can be disposed
1204 f( val, slot.ptr());
1205 gc::template retire<disposer>( slot.ptr());
1206 stats().onUpdateExisting();
1207 return std::make_pair( true, false );
1210 stats().onUpdateRetry();
1215 // the slot must be expanded
1216 base_class::expand_slot( pos, slot );
1219 stats().onUpdateFailed();
1220 return std::make_pair( false, false );
1224 // the slot is empty, try to insert data node
1227 if ( pos.pArr->nodes[pos.nSlot].compare_exchange_strong( pNull, node_ptr( &val ), memory_model::memory_order_release, atomics::memory_order_relaxed ))
1229 // the new data node has been inserted
1232 stats().onUpdateNew();
1233 stats().height( pos.nHeight );
1234 return std::make_pair( true, true );
1238 stats().onUpdateFailed();
1239 return std::make_pair( false, false );
1242 // insert failed - slot has been changed by another thread
1244 stats().onUpdateRetry();
1250 }} // namespace cds::intrusive
1252 #endif // #ifndef CDSLIB_INTRUSIVE_IMPL_FELDMAN_HASHSET_H