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 )
787 typename gc::Guard guard;
788 value_type * p = do_erase( hash, guard, []( value_type const&) -> bool {return true;} );
790 // p is guarded by HP
797 /// Finds an item by it's \p hash
799 The function searches the item by \p hash and calls the functor \p f for item found.
800 The interface of \p Func functor is:
803 void operator()( value_type& item );
806 where \p item is the item found.
808 The functor may change non-key fields of \p item. Note that the functor is only guarantee
809 that \p item cannot be disposed during the functor is executing.
810 The functor does not serialize simultaneous access to the set's \p item. If such access is
811 possible you must provide your own synchronization schema on item level to prevent unsafe item modifications.
813 The function returns \p true if \p hash is found, \p false otherwise.
815 template <typename Func>
816 bool find( hash_type const& hash, Func f )
818 typename gc::Guard guard;
819 value_type * p = search( hash, guard );
821 // p is guarded by HP
829 /// Checks whether the set contains \p hash
831 The function searches the item by its \p hash
832 and returns \p true if it is found, or \p false otherwise.
834 bool contains( hash_type const& hash )
836 return find( hash, []( value_type& ) {} );
839 /// Finds an item by it's \p hash and returns the item found
841 The function searches the item by its \p hash
842 and returns the guarded pointer to the item found.
843 If \p hash is not found the function returns an empty \p guarded_ptr.
845 @note Each \p guarded_ptr object uses one GC's guard which can be limited resource.
849 typedef cds::intrusive::FeldmanHashSet< your_template_params > my_set;
853 my_set::guarded_ptr gp( theSet.get( 5 ));
854 if ( theSet.get( 5 )) {
858 // Destructor of guarded_ptr releases internal HP guard
862 guarded_ptr get( hash_type const& hash )
866 typename gc::Guard guard;
867 gp.reset( search( hash, guard ));
872 /// Clears the set (non-atomic)
874 The function unlink all data node from the set.
875 The function is not atomic but is thread-safe.
876 After \p %clear() the set may not be empty because another threads may insert items.
878 For each item the \p disposer is called after unlinking.
882 clear_array( head(), head_size());
885 /// Checks if the set is empty
887 Emptiness is checked by item counting: if item count is zero then the set is empty.
888 Thus, the correct item counting feature is an important part of the set implementation.
895 /// Returns item count in the set
898 return m_ItemCounter;
901 /// Returns const reference to internal statistics
902 stat const& statistics() const
907 /// Returns the size of head node
908 using base_class::head_size;
910 /// Returns the size of the array node
911 using base_class::array_node_size;
913 /// Collects tree level statistics into \p stat
915 The function traverses the set and collects statistics for each level of the tree
916 into \p feldman_hashset::level_statistics struct. The element of \p stat[i]
917 represents statistics for level \p i, level 0 is head array.
918 The function is thread-safe and may be called in multi-threaded environment.
920 Result can be useful for estimating efficiency of hash functor you use.
922 void get_level_statistics( std::vector< feldman_hashset::level_statistics>& stat ) const
924 base_class::get_level_statistics( stat );
928 ///@name Thread-safe iterators
929 /** @anchor cds_intrusive_FeldmanHashSet_iterators
930 The set supports thread-safe iterators: you may iterate over the set in multi-threaded environment.
931 It is guaranteed that the iterators will remain valid even if another thread deletes the node the iterator points to:
932 Hazard Pointer embedded into the iterator object protects the node from physical reclamation.
934 @note Since the iterator object contains hazard pointer that is a thread-local resource,
935 the iterator should not be passed to another thread.
937 Each iterator object supports the common interface:
938 - dereference operators:
940 value_type [const] * operator ->() noexcept
941 value_type [const] & operator *() noexcept
943 - pre-increment and pre-decrement. Post-operators is not supported
944 - equality operators <tt>==</tt> and <tt>!=</tt>.
945 Iterators are equal iff they point to the same cell of the same array node.
946 Note that for two iterators \p it1 and \p it2, the conditon <tt> it1 == it2 </tt>
947 does not entail <tt> &(*it1) == &(*it2) </tt>: welcome to concurrent containers
948 - helper member function \p release() that clears internal hazard pointer.
949 After \p release() the iterator points to \p nullptr but it still remain valid: further iterating is possible.
951 During iteration you may safely erase any item from the set;
952 @ref erase_at() function call doesn't invalidate any iterator.
953 If some iterator points to the item to be erased, that item is not deleted immediately
954 but only after that iterator will be advanced forward or backward.
956 @note It is possible the item can be iterated more that once, for example, if an iterator points to the item
957 in array node that is being splitted.
961 /// Returns an iterator to the beginning of the set
964 return iterator( *this, head(), size_t(0) - 1 );
967 /// Returns an const iterator to the beginning of the set
968 const_iterator begin() const
970 return const_iterator( *this, head(), size_t(0) - 1 );
973 /// Returns an const iterator to the beginning of the set
974 const_iterator cbegin()
976 return const_iterator( *this, head(), size_t(0) - 1 );
979 /// 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.
982 return iterator( *this, head(), head_size(), false );
985 /// 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.
986 const_iterator end() const
988 return const_iterator( *this, head(), head_size(), false );
991 /// 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.
992 const_iterator cend()
994 return const_iterator( *this, head(), head_size(), false );
997 /// Returns a reverse iterator to the first element of the reversed set
998 reverse_iterator rbegin()
1000 return reverse_iterator( *this, head(), head_size());
1003 /// Returns a const reverse iterator to the first element of the reversed set
1004 const_reverse_iterator rbegin() const
1006 return const_reverse_iterator( *this, head(), head_size());
1009 /// Returns a const reverse iterator to the first element of the reversed set
1010 const_reverse_iterator crbegin()
1012 return const_reverse_iterator( *this, head(), head_size());
1015 /// Returns a reverse iterator to the element following the last element of the reversed set
1017 It corresponds to the element preceding the first element of the non-reversed container.
1018 This element acts as a placeholder, attempting to access it results in undefined behavior.
1020 reverse_iterator rend()
1022 return reverse_iterator( *this, head(), size_t(0) - 1, false );
1025 /// Returns a const reverse iterator to the element following the last element of the reversed set
1027 It corresponds to the element preceding the first element of the non-reversed container.
1028 This element acts as a placeholder, attempting to access it results in undefined behavior.
1030 const_reverse_iterator rend() const
1032 return const_reverse_iterator( *this, head(), size_t(0) - 1, false );
1035 /// Returns a const reverse iterator to the element following the last element of the reversed set
1037 It corresponds to the element preceding the first element of the non-reversed container.
1038 This element acts as a placeholder, attempting to access it results in undefined behavior.
1040 const_reverse_iterator crend()
1042 return const_reverse_iterator( *this, head(), size_t(0) - 1, false );
1048 void clear_array( array_node * pArrNode, size_t nSize )
1052 for ( atomic_node_ptr * pArr = pArrNode->nodes, *pLast = pArr + nSize; pArr != pLast; ++pArr ) {
1054 node_ptr slot = pArr->load( memory_model::memory_order_acquire );
1055 if ( slot.bits() == base_class::flag_array_node ) {
1056 // array node, go down the tree
1057 assert( slot.ptr() != nullptr );
1058 clear_array( to_array( slot.ptr()), array_node_size());
1061 else if ( slot.bits() == base_class::flag_array_converting ) {
1062 // the slot is converting to array node right now
1063 while (( slot = pArr->load( memory_model::memory_order_acquire )).bits() == base_class::flag_array_converting ) {
1065 stats().onSlotConverting();
1069 assert( slot.ptr() != nullptr );
1070 assert( slot.bits() == base_class::flag_array_node );
1071 clear_array( to_array( slot.ptr()), array_node_size());
1076 if ( pArr->compare_exchange_strong( slot, node_ptr(), memory_model::memory_order_acquire, atomics::memory_order_relaxed )) {
1078 gc::template retire<disposer>( slot.ptr());
1080 stats().onEraseSuccess();
1092 value_type * search( hash_type const& hash, typename gc::Guard& guard )
1094 traverse_data pos( hash, *this );
1095 hash_comparator cmp;
1098 node_ptr slot = base_class::traverse( pos );
1099 assert( slot.bits() == 0 );
1101 // protect data node by hazard pointer
1102 if ( guard.protect( pos.pArr->nodes[pos.nSlot], []( node_ptr p ) -> value_type* { return p.ptr(); }) != slot) {
1103 // slot value has been changed - retry
1104 stats().onSlotChanged();
1107 else if ( slot.ptr() && cmp( hash, hash_accessor()( *slot.ptr())) == 0 ) {
1109 stats().onFindSuccess();
1112 stats().onFindFailed();
1117 template <typename Predicate>
1118 value_type * do_erase( hash_type const& hash, typename gc::Guard& guard, Predicate pred )
1120 traverse_data pos( hash, *this );
1121 hash_comparator cmp;
1123 node_ptr slot = base_class::traverse( pos );
1124 assert( slot.bits() == 0 );
1126 // protect data node by hazard pointer
1127 if ( guard.protect( pos.pArr->nodes[pos.nSlot], []( node_ptr p ) -> value_type* { return p.ptr(); }) != slot ) {
1128 // slot value has been changed - retry
1129 stats().onSlotChanged();
1131 else if ( slot.ptr()) {
1132 if ( cmp( hash, hash_accessor()( *slot.ptr())) == 0 && pred( *slot.ptr())) {
1133 // item found - replace it with nullptr
1134 if ( pos.pArr->nodes[pos.nSlot].compare_exchange_strong( slot, node_ptr( nullptr ), memory_model::memory_order_acquire, atomics::memory_order_relaxed)) {
1135 // slot is guarded by HP
1136 gc::template retire<disposer>( slot.ptr());
1138 stats().onEraseSuccess();
1142 stats().onEraseRetry();
1145 stats().onEraseFailed();
1149 // the slot is empty
1150 stats().onEraseFailed();
1156 bool do_erase_at( iterator_base const& iter )
1158 if ( iter.m_set != this )
1160 if ( iter.m_pNode == head()) {
1161 if ( iter.m_idx >= head_size())
1164 else if ( iter.m_idx >= array_node_size())
1168 node_ptr slot = iter.m_pNode->nodes[iter.m_idx].load( memory_model::memory_order_acquire );
1169 if ( slot.bits() == 0 && slot.ptr() == iter.pointer()) {
1170 if ( iter.m_pNode->nodes[iter.m_idx].compare_exchange_strong( slot, node_ptr( nullptr ), memory_model::memory_order_acquire, atomics::memory_order_relaxed )) {
1171 // the item is guarded by iterator, so we may retire it safely
1172 gc::template retire<disposer>( slot.ptr());
1174 stats().onEraseSuccess();
1183 template <typename Func>
1184 std::pair<bool, bool> do_update( value_type& val, Func f, bool bInsert = true )
1186 hash_type const& hash = hash_accessor()( val );
1187 traverse_data pos( hash, *this );
1188 hash_comparator cmp;
1189 typename gc::template GuardArray<2> guards;
1191 guards.assign( 1, &val );
1193 node_ptr slot = base_class::traverse( pos );
1194 assert( slot.bits() == 0 );
1196 // protect data node by hazard pointer
1197 if ( guards.protect( 0, pos.pArr->nodes[pos.nSlot], []( node_ptr p ) -> value_type* { return p.ptr(); }) != slot ) {
1198 // slot value has been changed - retry
1199 stats().onSlotChanged();
1201 else if ( slot.ptr()) {
1202 if ( cmp( hash, hash_accessor()( *slot.ptr())) == 0 ) {
1203 // the item with that hash value already exists
1204 // Replace it with val
1205 if ( slot.ptr() == &val ) {
1206 stats().onUpdateExisting();
1207 return std::make_pair( true, false );
1210 if ( pos.pArr->nodes[pos.nSlot].compare_exchange_strong( slot, node_ptr( &val ), memory_model::memory_order_release, atomics::memory_order_relaxed )) {
1211 // slot can be disposed
1212 f( val, slot.ptr());
1213 gc::template retire<disposer>( slot.ptr());
1214 stats().onUpdateExisting();
1215 return std::make_pair( true, false );
1218 stats().onUpdateRetry();
1223 // the slot must be expanded
1224 base_class::expand_slot( pos, slot );
1227 stats().onUpdateFailed();
1228 return std::make_pair( false, false );
1232 // the slot is empty, try to insert data node
1235 if ( pos.pArr->nodes[pos.nSlot].compare_exchange_strong( pNull, node_ptr( &val ), memory_model::memory_order_release, atomics::memory_order_relaxed ))
1237 // the new data node has been inserted
1240 stats().onUpdateNew();
1241 stats().height( pos.nHeight );
1242 return std::make_pair( true, true );
1246 stats().onUpdateFailed();
1247 return std::make_pair( false, false );
1250 // insert failed - slot has been changed by another thread
1252 stats().onUpdateRetry();
1258 }} // namespace cds::intrusive
1260 #endif // #ifndef CDSLIB_INTRUSIVE_IMPL_FELDMAN_HASHSET_H