2 This file is a part of libcds - Concurrent Data Structures library
4 (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2017
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;
148 /// The size of hash_type in bytes, see \p feldman_hashset::traits::hash_size for explanation
149 static CDS_CONSTEXPR size_t const c_hash_size = base_class::c_hash_size;
152 typedef feldman_hashset::level_statistics level_statistics;
156 typedef typename base_class::node_ptr node_ptr;
157 typedef typename base_class::atomic_node_ptr atomic_node_ptr;
158 typedef typename base_class::array_node array_node;
159 typedef typename base_class::traverse_data traverse_data;
161 using base_class::to_array;
162 using base_class::to_node;
163 using base_class::stats;
164 using base_class::head;
165 using base_class::metrics;
172 friend class FeldmanHashSet;
175 array_node * m_pNode; ///< current array node
176 size_t m_idx; ///< current position in m_pNode
177 typename gc::Guard m_guard; ///< HP guard
178 FeldmanHashSet const* m_set; ///< Hash set
181 iterator_base() CDS_NOEXCEPT
187 iterator_base( iterator_base const& rhs ) CDS_NOEXCEPT
188 : m_pNode( rhs.m_pNode )
192 m_guard.copy( rhs.m_guard );
195 iterator_base& operator=( iterator_base const& rhs ) CDS_NOEXCEPT
197 m_pNode = rhs.m_pNode;
200 m_guard.copy( rhs.m_guard );
204 iterator_base& operator++()
210 iterator_base& operator--()
221 bool operator ==( iterator_base const& rhs ) const CDS_NOEXCEPT
223 return m_pNode == rhs.m_pNode && m_idx == rhs.m_idx && m_set == rhs.m_set;
226 bool operator !=( iterator_base const& rhs ) const CDS_NOEXCEPT
228 return !( *this == rhs );
232 iterator_base( FeldmanHashSet const& set, array_node * pNode, size_t idx, bool )
238 iterator_base( FeldmanHashSet const& set, array_node * pNode, size_t idx )
246 value_type * pointer() const CDS_NOEXCEPT
248 return m_guard.template get<value_type>();
253 assert( m_set != nullptr );
254 assert( m_pNode != nullptr );
256 size_t const arrayNodeSize = m_set->array_node_size();
257 size_t const headSize = m_set->head_size();
258 array_node * pNode = m_pNode;
259 size_t idx = m_idx + 1;
260 size_t nodeSize = m_pNode->pParent? arrayNodeSize : headSize;
263 if ( idx < nodeSize ) {
264 node_ptr slot = pNode->nodes[idx].load( memory_model::memory_order_acquire );
265 if ( slot.bits() == base_class::flag_array_node ) {
266 // array node, go down the tree
267 assert( slot.ptr() != nullptr );
268 pNode = to_array( slot.ptr());
270 nodeSize = arrayNodeSize;
272 else if ( slot.bits() == base_class::flag_array_converting ) {
273 // the slot is converting to array node right now - skip the node
279 if ( m_guard.protect( pNode->nodes[idx], []( node_ptr p ) -> value_type* { return p.ptr(); }) == slot ) {
290 if ( pNode->pParent ) {
291 idx = pNode->idxParent + 1;
292 pNode = pNode->pParent;
293 nodeSize = pNode->pParent ? arrayNodeSize : headSize;
297 assert( pNode == m_set->head());
298 assert( idx == headSize );
309 assert( m_set != nullptr );
310 assert( m_pNode != nullptr );
312 size_t const arrayNodeSize = m_set->array_node_size();
313 size_t const headSize = m_set->head_size();
314 size_t const endIdx = size_t(0) - 1;
316 array_node * pNode = m_pNode;
317 size_t idx = m_idx - 1;
318 size_t nodeSize = m_pNode->pParent? arrayNodeSize : headSize;
321 if ( idx != endIdx ) {
322 node_ptr slot = pNode->nodes[idx].load( memory_model::memory_order_acquire );
323 if ( slot.bits() == base_class::flag_array_node ) {
324 // array node, go down the tree
325 assert( slot.ptr() != nullptr );
326 pNode = to_array( slot.ptr());
327 nodeSize = arrayNodeSize;
330 else if ( slot.bits() == base_class::flag_array_converting ) {
331 // the slot is converting to array node right now - skip the node
337 if ( m_guard.protect( pNode->nodes[idx], []( node_ptr p ) -> value_type* { return p.ptr(); }) == slot ) {
348 if ( pNode->pParent ) {
349 idx = pNode->idxParent - 1;
350 pNode = pNode->pParent;
351 nodeSize = pNode->pParent ? arrayNodeSize : headSize;
355 assert( pNode == m_set->head());
356 assert( idx == endIdx );
366 template <class Iterator>
367 Iterator init_begin() const
369 return Iterator( *this, head(), size_t(0) - 1 );
372 template <class Iterator>
373 Iterator init_end() const
375 return Iterator( *this, head(), head_size(), false );
378 template <class Iterator>
379 Iterator init_rbegin() const
381 return Iterator( *this, head(), head_size());
384 template <class Iterator>
385 Iterator init_rend() const
387 return Iterator( *this, head(), size_t(0) - 1, false );
390 /// Bidirectional iterator class
391 template <bool IsConst>
392 class bidirectional_iterator: protected iterator_base
394 friend class FeldmanHashSet;
397 static CDS_CONSTEXPR bool const c_bConstantIterator = IsConst;
400 typedef typename std::conditional< IsConst, value_type const*, value_type*>::type value_ptr; ///< Value pointer
401 typedef typename std::conditional< IsConst, value_type const&, value_type&>::type value_ref; ///< Value reference
404 bidirectional_iterator() CDS_NOEXCEPT
407 bidirectional_iterator( bidirectional_iterator const& rhs ) CDS_NOEXCEPT
408 : iterator_base( rhs )
411 bidirectional_iterator& operator=( bidirectional_iterator const& rhs ) CDS_NOEXCEPT
413 iterator_base::operator=( rhs );
417 bidirectional_iterator& operator++()
419 iterator_base::operator++();
423 bidirectional_iterator& operator--()
425 iterator_base::operator--();
429 value_ptr operator ->() const CDS_NOEXCEPT
431 return iterator_base::pointer();
434 value_ref operator *() const CDS_NOEXCEPT
436 value_ptr p = iterator_base::pointer();
443 iterator_base::release();
446 template <bool IsConst2>
447 bool operator ==( bidirectional_iterator<IsConst2> const& rhs ) const CDS_NOEXCEPT
449 return iterator_base::operator==( rhs );
452 template <bool IsConst2>
453 bool operator !=( bidirectional_iterator<IsConst2> const& rhs ) const CDS_NOEXCEPT
455 return !( *this == rhs );
459 bidirectional_iterator( FeldmanHashSet& set, array_node * pNode, size_t idx, bool )
460 : iterator_base( set, pNode, idx, false )
463 bidirectional_iterator( FeldmanHashSet& set, array_node * pNode, size_t idx )
464 : iterator_base( set, pNode, idx )
468 /// Reverse bidirectional iterator
469 template <bool IsConst>
470 class reverse_bidirectional_iterator : public iterator_base
472 friend class FeldmanHashSet;
475 typedef typename std::conditional< IsConst, value_type const*, value_type*>::type value_ptr; ///< Value pointer
476 typedef typename std::conditional< IsConst, value_type const&, value_type&>::type value_ref; ///< Value reference
479 reverse_bidirectional_iterator() CDS_NOEXCEPT
483 reverse_bidirectional_iterator( reverse_bidirectional_iterator const& rhs ) CDS_NOEXCEPT
484 : iterator_base( rhs )
487 reverse_bidirectional_iterator& operator=( reverse_bidirectional_iterator const& rhs) CDS_NOEXCEPT
489 iterator_base::operator=( rhs );
493 reverse_bidirectional_iterator& operator++()
495 iterator_base::operator--();
499 reverse_bidirectional_iterator& operator--()
501 iterator_base::operator++();
505 value_ptr operator ->() const CDS_NOEXCEPT
507 return iterator_base::pointer();
510 value_ref operator *() const CDS_NOEXCEPT
512 value_ptr p = iterator_base::pointer();
519 iterator_base::release();
522 template <bool IsConst2>
523 bool operator ==( reverse_bidirectional_iterator<IsConst2> const& rhs ) const
525 return iterator_base::operator==( rhs );
528 template <bool IsConst2>
529 bool operator !=( reverse_bidirectional_iterator<IsConst2> const& rhs )
531 return !( *this == rhs );
535 reverse_bidirectional_iterator( FeldmanHashSet& set, array_node * pNode, size_t idx, bool )
536 : iterator_base( set, pNode, idx, false )
539 reverse_bidirectional_iterator( FeldmanHashSet& set, array_node * pNode, size_t idx )
540 : iterator_base( set, pNode, idx, false )
542 iterator_base::backward();
548 #ifdef CDS_DOXYGEN_INVOKED
549 typedef implementation_defined iterator; ///< @ref cds_intrusive_FeldmanHashSet_iterators "bidirectional iterator" type
550 typedef implementation_defined const_iterator; ///< @ref cds_intrusive_FeldmanHashSet_iterators "bidirectional const iterator" type
551 typedef implementation_defined reverse_iterator; ///< @ref cds_intrusive_FeldmanHashSet_iterators "bidirectional reverse iterator" type
552 typedef implementation_defined const_reverse_iterator; ///< @ref cds_intrusive_FeldmanHashSet_iterators "bidirectional reverse const iterator" type
554 typedef bidirectional_iterator<false> iterator;
555 typedef bidirectional_iterator<true> const_iterator;
556 typedef reverse_bidirectional_iterator<false> reverse_iterator;
557 typedef reverse_bidirectional_iterator<true> const_reverse_iterator;
562 item_counter m_ItemCounter; ///< Item counter
566 /// Creates empty set
568 @param head_bits: 2<sup>head_bits</sup> specifies the size of head array, minimum is 4.
569 @param array_bits: 2<sup>array_bits</sup> specifies the size of array node, minimum is 2.
571 Equation for \p head_bits and \p array_bits:
573 sizeof( hash_type ) * 8 == head_bits + N * array_bits
575 where \p N is multi-level array depth.
577 FeldmanHashSet( size_t head_bits = 8, size_t array_bits = 4 )
578 : base_class( head_bits, array_bits )
581 /// Destructs the set and frees all data
589 The function inserts \p val in the set if it does not contain
590 an item with that hash.
592 Returns \p true if \p val is placed into the set, \p false otherwise.
594 bool insert( value_type& val )
596 return insert( val, []( value_type& ) {} );
601 This function is intended for derived non-intrusive containers.
603 The function allows to split creating of new item into two part:
604 - create item with key only
605 - insert new item into the set
606 - if inserting is success, calls \p f functor to initialize \p val.
608 The functor signature is:
610 void func( value_type& val );
612 where \p val is the item inserted.
614 The user-defined functor is called only if the inserting is success.
616 @warning See \ref cds_intrusive_item_creating "insert item troubleshooting".
618 template <typename Func>
619 bool insert( value_type& val, Func f )
621 hash_type const& hash = hash_accessor()( val );
622 traverse_data pos( hash, *this );
624 typename gc::template GuardArray<2> guards;
626 guards.assign( 1, &val );
628 node_ptr slot = base_class::traverse( pos );
629 assert( slot.bits() == 0 );
631 // protect data node by hazard pointer
632 if ( guards.protect( 0, pos.pArr->nodes[pos.nSlot], []( node_ptr p ) -> value_type* { return p.ptr(); }) != slot ) {
633 // slot value has been changed - retry
634 stats().onSlotChanged();
636 else if ( slot.ptr()) {
637 if ( cmp( hash, hash_accessor()( *slot.ptr())) == 0 ) {
638 // the item with that hash value already exists
639 stats().onInsertFailed();
643 // the slot must be expanded
644 base_class::expand_slot( pos, slot );
647 // the slot is empty, try to insert data node
649 if ( pos.pArr->nodes[pos.nSlot].compare_exchange_strong( pNull, node_ptr( &val ), memory_model::memory_order_release, atomics::memory_order_relaxed ))
651 // the new data node has been inserted
654 stats().onInsertSuccess();
655 stats().height( pos.nHeight );
659 // insert failed - slot has been changed by another thread
661 stats().onInsertRetry();
668 Performs inserting or updating the item with hash value equal to \p val.
669 - If hash value is found then existing item is replaced with \p val, old item is disposed
670 with \p Traits::disposer. Note that the disposer is called by \p GC asynchronously.
671 The function returns <tt> std::pair<true, false> </tt>
672 - If hash value is not found and \p bInsert is \p true then \p val is inserted,
673 the function returns <tt> std::pair<true, true> </tt>
674 - If hash value is not found and \p bInsert is \p false then the set is unchanged,
675 the function returns <tt> std::pair<false, false> </tt>
677 Returns <tt> std::pair<bool, bool> </tt> where \p first is \p true if operation is successful
678 (i.e. the item has been inserted or updated),
679 \p second is \p true if new item has been added or \p false if the set contains that hash.
681 std::pair<bool, bool> update( value_type& val, bool bInsert = true )
683 return do_update( val, []( value_type&, value_type* ) {}, bInsert );
686 /// Unlinks the item \p val from the set
688 The function searches the item \p val in the set and unlink it
689 if it is found and its address is equal to <tt>&val</tt>.
691 The function returns \p true if success and \p false otherwise.
693 bool unlink( value_type const& val )
695 typename gc::Guard guard;
696 auto pred = [&val]( value_type const& item ) -> bool { return &item == &val; };
697 value_type * p = do_erase( hash_accessor()( val ), guard, std::ref( pred ));
701 /// Deletes the item from the set
703 The function searches \p hash in the set,
704 unlinks the item found, and returns \p true.
705 If that item is not found the function returns \p false.
707 The \ref disposer specified in \p Traits is called by garbage collector \p GC asynchronously.
709 bool erase( hash_type const& hash )
711 return erase( hash, []( value_type const& ) {} );
714 /// Deletes the item from the set
716 The function searches \p hash in the set,
717 call \p f functor with item found, and unlinks it from the set.
718 The \ref disposer specified in \p Traits is called
719 by garbage collector \p GC asynchronously.
721 The \p Func interface is
724 void operator()( value_type& item );
728 If \p hash is not found the function returns \p false.
730 template <typename Func>
731 bool erase( hash_type const& hash, Func f )
733 typename gc::Guard guard;
734 value_type * p = do_erase( hash, guard, []( value_type const&) -> bool {return true; } );
736 // p is guarded by HP
744 /// Deletes the item pointed by iterator \p iter
746 Returns \p true if the operation is successful, \p false otherwise.
748 The function does not invalidate the iterator, it remains valid and can be used for further traversing.
750 bool erase_at( iterator const& iter )
752 return do_erase_at( iter );
755 bool erase_at( reverse_iterator const& iter )
757 return do_erase_at( iter );
761 /// Extracts the item with specified \p hash
763 The function searches \p hash in the set,
764 unlinks it from the set, and returns an guarded pointer to the item extracted.
765 If \p hash is not found the function returns an empty guarded pointer.
767 The \p disposer specified in \p Traits class' template parameter is called automatically
768 by garbage collector \p GC when returned \ref guarded_ptr object to be destroyed or released.
769 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
773 typedef cds::intrusive::FeldmanHashSet< your_template_args > my_set;
777 my_set::guarded_ptr gp( theSet.extract( 5 ));
782 // Destructor of gp releases internal HP guard
786 guarded_ptr extract( hash_type const& hash )
788 typename gc::Guard guard;
789 if ( do_erase( hash, guard, []( value_type const&) -> bool {return true;} ))
790 return guarded_ptr( std::move( guard ));
791 return guarded_ptr();
794 /// Finds an item by it's \p hash
796 The function searches the item by \p hash and calls the functor \p f for item found.
797 The interface of \p Func functor is:
800 void operator()( value_type& item );
803 where \p item is the item found.
805 The functor may change non-key fields of \p item. Note that the functor is only guarantee
806 that \p item cannot be disposed during the functor is executing.
807 The functor does not serialize simultaneous access to the set's \p item. If such access is
808 possible you must provide your own synchronization schema on item level to prevent unsafe item modifications.
810 The function returns \p true if \p hash is found, \p false otherwise.
812 template <typename Func>
813 bool find( hash_type const& hash, Func f )
815 typename gc::Guard guard;
816 value_type * p = search( hash, guard );
818 // p is guarded by HP
826 /// Checks whether the set contains \p hash
828 The function searches the item by its \p hash
829 and returns \p true if it is found, or \p false otherwise.
831 bool contains( hash_type const& hash )
833 return find( hash, []( value_type& ) {} );
836 /// Finds an item by it's \p hash and returns the item found
838 The function searches the item by its \p hash
839 and returns the guarded pointer to the item found.
840 If \p hash is not found the function returns an empty \p guarded_ptr.
842 @note Each \p guarded_ptr object uses one GC's guard which can be limited resource.
846 typedef cds::intrusive::FeldmanHashSet< your_template_params > my_set;
850 my_set::guarded_ptr gp( theSet.get( 5 ));
851 if ( theSet.get( 5 )) {
855 // Destructor of guarded_ptr releases internal HP guard
859 guarded_ptr get( hash_type const& hash )
861 typename gc::Guard guard;
862 if ( search( hash, guard ))
863 return guarded_ptr( std::move( guard ));
864 return guarded_ptr();
867 /// Clears the set (non-atomic)
869 The function unlink all data node from the set.
870 The function is not atomic but is thread-safe.
871 After \p %clear() the set may not be empty because another threads may insert items.
873 For each item the \p disposer is called after unlinking.
877 clear_array( head(), head_size());
880 /// Checks if the set is empty
882 Emptiness is checked by item counting: if item count is zero then the set is empty.
883 Thus, the correct item counting feature is an important part of the set implementation.
890 /// Returns item count in the set
893 return m_ItemCounter;
896 /// Returns const reference to internal statistics
897 stat const& statistics() const
902 /// Returns the size of head node
903 using base_class::head_size;
905 /// Returns the size of the array node
906 using base_class::array_node_size;
908 /// Collects tree level statistics into \p stat
910 The function traverses the set and collects statistics for each level of the tree
911 into \p feldman_hashset::level_statistics struct. The element of \p stat[i]
912 represents statistics for level \p i, level 0 is head array.
913 The function is thread-safe and may be called in multi-threaded environment.
915 Result can be useful for estimating efficiency of hash functor you use.
917 void get_level_statistics( std::vector< feldman_hashset::level_statistics>& stat ) const
919 base_class::get_level_statistics( stat );
923 ///@name Thread-safe iterators
924 /** @anchor cds_intrusive_FeldmanHashSet_iterators
925 The set supports thread-safe iterators: you may iterate over the set in multi-threaded environment.
926 It is guaranteed that the iterators will remain valid even if another thread deletes the node the iterator points to:
927 Hazard Pointer embedded into the iterator object protects the node from physical reclamation.
929 @note Since the iterator object contains hazard pointer that is a thread-local resource,
930 the iterator should not be passed to another thread.
932 Each iterator object supports the common interface:
933 - dereference operators:
935 value_type [const] * operator ->() noexcept
936 value_type [const] & operator *() noexcept
938 - pre-increment and pre-decrement. Post-operators is not supported
939 - equality operators <tt>==</tt> and <tt>!=</tt>.
940 Iterators are equal iff they point to the same cell of the same array node.
941 Note that for two iterators \p it1 and \p it2, the conditon <tt> it1 == it2 </tt>
942 does not entail <tt> &(*it1) == &(*it2) </tt>: welcome to concurrent containers
943 - helper member function \p release() that clears internal hazard pointer.
944 After \p release() the iterator points to \p nullptr but it still remain valid: further iterating is possible.
946 During iteration you may safely erase any item from the set;
947 @ref erase_at() function call doesn't invalidate any iterator.
948 If some iterator points to the item to be erased, that item is not deleted immediately
949 but only after that iterator will be advanced forward or backward.
951 @note It is possible the item can be iterated more that once, for example, if an iterator points to the item
952 in array node that is being splitted.
956 /// Returns an iterator to the beginning of the set
959 return iterator( *this, head(), size_t(0) - 1 );
962 /// Returns an const iterator to the beginning of the set
963 const_iterator begin() const
965 return const_iterator( *this, head(), size_t(0) - 1 );
968 /// Returns an const iterator to the beginning of the set
969 const_iterator cbegin()
971 return const_iterator( *this, head(), size_t(0) - 1 );
974 /// 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.
977 return iterator( *this, head(), head_size(), false );
980 /// 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.
981 const_iterator end() const
983 return const_iterator( *this, head(), head_size(), false );
986 /// 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.
987 const_iterator cend()
989 return const_iterator( *this, head(), head_size(), false );
992 /// Returns a reverse iterator to the first element of the reversed set
993 reverse_iterator rbegin()
995 return reverse_iterator( *this, head(), head_size());
998 /// Returns a const reverse iterator to the first element of the reversed set
999 const_reverse_iterator rbegin() const
1001 return const_reverse_iterator( *this, head(), head_size());
1004 /// Returns a const reverse iterator to the first element of the reversed set
1005 const_reverse_iterator crbegin()
1007 return const_reverse_iterator( *this, head(), head_size());
1010 /// Returns a reverse iterator to the element following the last element of the reversed set
1012 It corresponds to the element preceding the first element of the non-reversed container.
1013 This element acts as a placeholder, attempting to access it results in undefined behavior.
1015 reverse_iterator rend()
1017 return reverse_iterator( *this, head(), size_t(0) - 1, false );
1020 /// Returns a const reverse iterator to the element following the last element of the reversed set
1022 It corresponds to the element preceding the first element of the non-reversed container.
1023 This element acts as a placeholder, attempting to access it results in undefined behavior.
1025 const_reverse_iterator rend() const
1027 return const_reverse_iterator( *this, head(), size_t(0) - 1, false );
1030 /// Returns a const reverse iterator to the element following the last element of the reversed set
1032 It corresponds to the element preceding the first element of the non-reversed container.
1033 This element acts as a placeholder, attempting to access it results in undefined behavior.
1035 const_reverse_iterator crend()
1037 return const_reverse_iterator( *this, head(), size_t(0) - 1, false );
1043 void clear_array( array_node * pArrNode, size_t nSize )
1047 for ( atomic_node_ptr * pArr = pArrNode->nodes, *pLast = pArr + nSize; pArr != pLast; ++pArr ) {
1049 node_ptr slot = pArr->load( memory_model::memory_order_acquire );
1050 if ( slot.bits() == base_class::flag_array_node ) {
1051 // array node, go down the tree
1052 assert( slot.ptr() != nullptr );
1053 clear_array( to_array( slot.ptr()), array_node_size());
1056 else if ( slot.bits() == base_class::flag_array_converting ) {
1057 // the slot is converting to array node right now
1058 while (( slot = pArr->load( memory_model::memory_order_acquire )).bits() == base_class::flag_array_converting ) {
1060 stats().onSlotConverting();
1064 assert( slot.ptr() != nullptr );
1065 assert( slot.bits() == base_class::flag_array_node );
1066 clear_array( to_array( slot.ptr()), array_node_size());
1071 if ( pArr->compare_exchange_strong( slot, node_ptr(), memory_model::memory_order_acquire, atomics::memory_order_relaxed )) {
1073 gc::template retire<disposer>( slot.ptr());
1075 stats().onEraseSuccess();
1087 value_type * search( hash_type const& hash, typename gc::Guard& guard )
1089 traverse_data pos( hash, *this );
1090 hash_comparator cmp;
1093 node_ptr slot = base_class::traverse( pos );
1094 assert( slot.bits() == 0 );
1096 // protect data node by hazard pointer
1097 if ( guard.protect( pos.pArr->nodes[pos.nSlot], []( node_ptr p ) -> value_type* { return p.ptr(); }) != slot) {
1098 // slot value has been changed - retry
1099 stats().onSlotChanged();
1102 else if ( slot.ptr() && cmp( hash, hash_accessor()( *slot.ptr())) == 0 ) {
1104 stats().onFindSuccess();
1107 stats().onFindFailed();
1112 template <typename Predicate>
1113 value_type * do_erase( hash_type const& hash, typename gc::Guard& guard, Predicate pred )
1115 traverse_data pos( hash, *this );
1116 hash_comparator cmp;
1118 node_ptr slot = base_class::traverse( pos );
1119 assert( slot.bits() == 0 );
1121 // protect data node by hazard pointer
1122 if ( guard.protect( pos.pArr->nodes[pos.nSlot], []( node_ptr p ) -> value_type* { return p.ptr(); }) != slot ) {
1123 // slot value has been changed - retry
1124 stats().onSlotChanged();
1126 else if ( slot.ptr()) {
1127 if ( cmp( hash, hash_accessor()( *slot.ptr())) == 0 && pred( *slot.ptr())) {
1128 // item found - replace it with nullptr
1129 if ( pos.pArr->nodes[pos.nSlot].compare_exchange_strong( slot, node_ptr( nullptr ), memory_model::memory_order_acquire, atomics::memory_order_relaxed)) {
1130 // slot is guarded by HP
1131 gc::template retire<disposer>( slot.ptr());
1133 stats().onEraseSuccess();
1137 stats().onEraseRetry();
1140 stats().onEraseFailed();
1144 // the slot is empty
1145 stats().onEraseFailed();
1151 bool do_erase_at( iterator_base const& iter )
1153 if ( iter.m_set != this )
1155 if ( iter.m_pNode == head()) {
1156 if ( iter.m_idx >= head_size())
1159 else if ( iter.m_idx >= array_node_size())
1163 node_ptr slot = iter.m_pNode->nodes[iter.m_idx].load( memory_model::memory_order_acquire );
1164 if ( slot.bits() == 0 && slot.ptr() == iter.pointer()) {
1165 if ( iter.m_pNode->nodes[iter.m_idx].compare_exchange_strong( slot, node_ptr( nullptr ), memory_model::memory_order_acquire, atomics::memory_order_relaxed )) {
1166 // the item is guarded by iterator, so we may retire it safely
1167 gc::template retire<disposer>( slot.ptr());
1169 stats().onEraseSuccess();
1178 template <typename Func>
1179 std::pair<bool, bool> do_update( value_type& val, Func f, bool bInsert = true )
1181 hash_type const& hash = hash_accessor()( val );
1182 traverse_data pos( hash, *this );
1183 hash_comparator cmp;
1184 typename gc::template GuardArray<2> guards;
1186 guards.assign( 1, &val );
1188 node_ptr slot = base_class::traverse( pos );
1189 assert( slot.bits() == 0 );
1191 // protect data node by hazard pointer
1192 if ( guards.protect( 0, pos.pArr->nodes[pos.nSlot], []( node_ptr p ) -> value_type* { return p.ptr(); }) != slot ) {
1193 // slot value has been changed - retry
1194 stats().onSlotChanged();
1196 else if ( slot.ptr()) {
1197 if ( cmp( hash, hash_accessor()( *slot.ptr())) == 0 ) {
1198 // the item with that hash value already exists
1199 // Replace it with val
1200 if ( slot.ptr() == &val ) {
1201 stats().onUpdateExisting();
1202 return std::make_pair( true, false );
1205 if ( pos.pArr->nodes[pos.nSlot].compare_exchange_strong( slot, node_ptr( &val ), memory_model::memory_order_release, atomics::memory_order_relaxed )) {
1206 // slot can be disposed
1207 f( val, slot.ptr());
1208 gc::template retire<disposer>( slot.ptr());
1209 stats().onUpdateExisting();
1210 return std::make_pair( true, false );
1213 stats().onUpdateRetry();
1218 // the slot must be expanded
1219 base_class::expand_slot( pos, slot );
1222 stats().onUpdateFailed();
1223 return std::make_pair( false, false );
1227 // the slot is empty, try to insert data node
1230 if ( pos.pArr->nodes[pos.nSlot].compare_exchange_strong( pNull, node_ptr( &val ), memory_model::memory_order_release, atomics::memory_order_relaxed ))
1232 // the new data node has been inserted
1235 stats().onUpdateNew();
1236 stats().height( pos.nHeight );
1237 return std::make_pair( true, true );
1241 stats().onUpdateFailed();
1242 return std::make_pair( false, false );
1245 // insert failed - slot has been changed by another thread
1247 stats().onUpdateRetry();
1253 }} // namespace cds::intrusive
1255 #endif // #ifndef CDSLIB_INTRUSIVE_IMPL_FELDMAN_HASHSET_H