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 if ( !pos.splitter.eos() ) {
644 // the slot must be expanded
645 base_class::expand_slot( pos, slot );
651 // the slot is empty, try to insert data node
653 if ( pos.pArr->nodes[pos.nSlot].compare_exchange_strong( pNull, node_ptr( &val ), memory_model::memory_order_release, atomics::memory_order_relaxed ))
655 // the new data node has been inserted
658 stats().onInsertSuccess();
659 stats().height( pos.nHeight );
663 // insert failed - slot has been changed by another thread
665 stats().onInsertRetry();
672 Performs inserting or updating the item with hash value equal to \p val.
673 - If hash value is found then existing item is replaced with \p val, old item is disposed
674 with \p Traits::disposer. Note that the disposer is called by \p GC asynchronously.
675 The function returns <tt> std::pair<true, false> </tt>
676 - If hash value is not found and \p bInsert is \p true then \p val is inserted,
677 the function returns <tt> std::pair<true, true> </tt>
678 - If hash value is not found and \p bInsert is \p false then the set is unchanged,
679 the function returns <tt> std::pair<false, false> </tt>
681 Returns <tt> std::pair<bool, bool> </tt> where \p first is \p true if operation is successful
682 (i.e. the item has been inserted or updated),
683 \p second is \p true if new item has been added or \p false if the set contains that hash.
685 std::pair<bool, bool> update( value_type& val, bool bInsert = true )
687 return do_update( val, []( value_type&, value_type* ) {}, bInsert );
690 /// Unlinks the item \p val from the set
692 The function searches the item \p val in the set and unlink it
693 if it is found and its address is equal to <tt>&val</tt>.
695 The function returns \p true if success and \p false otherwise.
697 bool unlink( value_type const& val )
699 typename gc::Guard guard;
700 auto pred = [&val]( value_type const& item ) -> bool { return &item == &val; };
701 value_type * p = do_erase( hash_accessor()( val ), guard, std::ref( pred ));
705 /// Deletes the item from the set
707 The function searches \p hash in the set,
708 unlinks the item found, and returns \p true.
709 If that item is not found the function returns \p false.
711 The \ref disposer specified in \p Traits is called by garbage collector \p GC asynchronously.
713 bool erase( hash_type const& hash )
715 return erase( hash, []( value_type const& ) {} );
718 /// Deletes the item from the set
720 The function searches \p hash in the set,
721 call \p f functor with item found, and unlinks it from the set.
722 The \ref disposer specified in \p Traits is called
723 by garbage collector \p GC asynchronously.
725 The \p Func interface is
728 void operator()( value_type& item );
732 If \p hash is not found the function returns \p false.
734 template <typename Func>
735 bool erase( hash_type const& hash, Func f )
737 typename gc::Guard guard;
738 value_type * p = do_erase( hash, guard, []( value_type const&) -> bool {return true; } );
740 // p is guarded by HP
748 /// Deletes the item pointed by iterator \p iter
750 Returns \p true if the operation is successful, \p false otherwise.
752 The function does not invalidate the iterator, it remains valid and can be used for further traversing.
754 bool erase_at( iterator const& iter )
756 return do_erase_at( iter );
759 bool erase_at( reverse_iterator const& iter )
761 return do_erase_at( iter );
765 /// Extracts the item with specified \p hash
767 The function searches \p hash in the set,
768 unlinks it from the set, and returns an guarded pointer to the item extracted.
769 If \p hash is not found the function returns an empty guarded pointer.
771 The \p disposer specified in \p Traits class' template parameter is called automatically
772 by garbage collector \p GC when returned \ref guarded_ptr object to be destroyed or released.
773 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
777 typedef cds::intrusive::FeldmanHashSet< your_template_args > my_set;
781 my_set::guarded_ptr gp( theSet.extract( 5 ));
786 // Destructor of gp releases internal HP guard
790 guarded_ptr extract( hash_type const& hash )
792 typename gc::Guard guard;
793 if ( do_erase( hash, guard, []( value_type const&) -> bool {return true;} ))
794 return guarded_ptr( std::move( guard ));
795 return guarded_ptr();
798 /// Finds an item by it's \p hash
800 The function searches the item by \p hash and calls the functor \p f for item found.
801 The interface of \p Func functor is:
804 void operator()( value_type& item );
807 where \p item is the item found.
809 The functor may change non-key fields of \p item. Note that the functor is only guarantee
810 that \p item cannot be disposed during the functor is executing.
811 The functor does not serialize simultaneous access to the set's \p item. If such access is
812 possible you must provide your own synchronization schema on item level to prevent unsafe item modifications.
814 The function returns \p true if \p hash is found, \p false otherwise.
816 template <typename Func>
817 bool find( hash_type const& hash, Func f )
819 typename gc::Guard guard;
820 value_type * p = search( hash, guard );
822 // p is guarded by HP
830 /// Checks whether the set contains \p hash
832 The function searches the item by its \p hash
833 and returns \p true if it is found, or \p false otherwise.
835 bool contains( hash_type const& hash )
837 return find( hash, []( value_type& ) {} );
840 /// Finds an item by it's \p hash and returns the item found
842 The function searches the item by its \p hash
843 and returns the guarded pointer to the item found.
844 If \p hash is not found the function returns an empty \p guarded_ptr.
846 @note Each \p guarded_ptr object uses one GC's guard which can be limited resource.
850 typedef cds::intrusive::FeldmanHashSet< your_template_params > my_set;
854 my_set::guarded_ptr gp( theSet.get( 5 ));
855 if ( theSet.get( 5 )) {
859 // Destructor of guarded_ptr releases internal HP guard
863 guarded_ptr get( hash_type const& hash )
865 typename gc::Guard guard;
866 if ( search( hash, guard ))
867 return guarded_ptr( std::move( guard ));
868 return guarded_ptr();
871 /// Clears the set (non-atomic)
873 The function unlink all data node from the set.
874 The function is not atomic but is thread-safe.
875 After \p %clear() the set may not be empty because another threads may insert items.
877 For each item the \p disposer is called after unlinking.
881 clear_array( head(), head_size());
884 /// Checks if the set is empty
886 Emptiness is checked by item counting: if item count is zero then the set is empty.
887 Thus, the correct item counting feature is an important part of the set implementation.
894 /// Returns item count in the set
897 return m_ItemCounter;
900 /// Returns const reference to internal statistics
901 stat const& statistics() const
906 /// Returns the size of head node
907 using base_class::head_size;
909 /// Returns the size of the array node
910 using base_class::array_node_size;
912 /// Collects tree level statistics into \p stat
914 The function traverses the set and collects statistics for each level of the tree
915 into \p feldman_hashset::level_statistics struct. The element of \p stat[i]
916 represents statistics for level \p i, level 0 is head array.
917 The function is thread-safe and may be called in multi-threaded environment.
919 Result can be useful for estimating efficiency of hash functor you use.
921 void get_level_statistics( std::vector< feldman_hashset::level_statistics>& stat ) const
923 base_class::get_level_statistics( stat );
927 ///@name Thread-safe iterators
928 /** @anchor cds_intrusive_FeldmanHashSet_iterators
929 The set supports thread-safe iterators: you may iterate over the set in multi-threaded environment.
930 It is guaranteed that the iterators will remain valid even if another thread deletes the node the iterator points to:
931 Hazard Pointer embedded into the iterator object protects the node from physical reclamation.
933 @note Since the iterator object contains hazard pointer that is a thread-local resource,
934 the iterator should not be passed to another thread.
936 Each iterator object supports the common interface:
937 - dereference operators:
939 value_type [const] * operator ->() noexcept
940 value_type [const] & operator *() noexcept
942 - pre-increment and pre-decrement. Post-operators is not supported
943 - equality operators <tt>==</tt> and <tt>!=</tt>.
944 Iterators are equal iff they point to the same cell of the same array node.
945 Note that for two iterators \p it1 and \p it2, the conditon <tt> it1 == it2 </tt>
946 does not entail <tt> &(*it1) == &(*it2) </tt>: welcome to concurrent containers
947 - helper member function \p release() that clears internal hazard pointer.
948 After \p release() the iterator points to \p nullptr but it still remain valid: further iterating is possible.
950 During iteration you may safely erase any item from the set;
951 @ref erase_at() function call doesn't invalidate any iterator.
952 If some iterator points to the item to be erased, that item is not deleted immediately
953 but only after that iterator will be advanced forward or backward.
955 @note It is possible the item can be iterated more that once, for example, if an iterator points to the item
956 in array node that is being splitted.
960 /// Returns an iterator to the beginning of the set
963 return iterator( *this, head(), size_t(0) - 1 );
966 /// Returns an const iterator to the beginning of the set
967 const_iterator begin() const
969 return const_iterator( *this, head(), size_t(0) - 1 );
972 /// Returns an const iterator to the beginning of the set
973 const_iterator cbegin()
975 return const_iterator( *this, head(), size_t(0) - 1 );
978 /// 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.
981 return iterator( *this, head(), head_size(), false );
984 /// 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.
985 const_iterator end() const
987 return const_iterator( *this, head(), head_size(), false );
990 /// 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.
991 const_iterator cend()
993 return const_iterator( *this, head(), head_size(), false );
996 /// Returns a reverse iterator to the first element of the reversed set
997 reverse_iterator rbegin()
999 return reverse_iterator( *this, head(), head_size());
1002 /// Returns a const reverse iterator to the first element of the reversed set
1003 const_reverse_iterator rbegin() const
1005 return const_reverse_iterator( *this, head(), head_size());
1008 /// Returns a const reverse iterator to the first element of the reversed set
1009 const_reverse_iterator crbegin()
1011 return const_reverse_iterator( *this, head(), head_size());
1014 /// Returns a reverse iterator to the element following the last element of the reversed set
1016 It corresponds to the element preceding the first element of the non-reversed container.
1017 This element acts as a placeholder, attempting to access it results in undefined behavior.
1019 reverse_iterator rend()
1021 return reverse_iterator( *this, head(), size_t(0) - 1, false );
1024 /// Returns a const reverse iterator to the element following the last element of the reversed set
1026 It corresponds to the element preceding the first element of the non-reversed container.
1027 This element acts as a placeholder, attempting to access it results in undefined behavior.
1029 const_reverse_iterator rend() const
1031 return const_reverse_iterator( *this, head(), size_t(0) - 1, false );
1034 /// Returns a const reverse iterator to the element following the last element of the reversed set
1036 It corresponds to the element preceding the first element of the non-reversed container.
1037 This element acts as a placeholder, attempting to access it results in undefined behavior.
1039 const_reverse_iterator crend()
1041 return const_reverse_iterator( *this, head(), size_t(0) - 1, false );
1047 void clear_array( array_node * pArrNode, size_t nSize )
1051 for ( atomic_node_ptr * pArr = pArrNode->nodes, *pLast = pArr + nSize; pArr != pLast; ++pArr ) {
1053 node_ptr slot = pArr->load( memory_model::memory_order_acquire );
1054 if ( slot.bits() == base_class::flag_array_node ) {
1055 // array node, go down the tree
1056 assert( slot.ptr() != nullptr );
1057 clear_array( to_array( slot.ptr()), array_node_size());
1060 else if ( slot.bits() == base_class::flag_array_converting ) {
1061 // the slot is converting to array node right now
1062 while (( slot = pArr->load( memory_model::memory_order_acquire )).bits() == base_class::flag_array_converting ) {
1064 stats().onSlotConverting();
1068 assert( slot.ptr() != nullptr );
1069 assert( slot.bits() == base_class::flag_array_node );
1070 clear_array( to_array( slot.ptr()), array_node_size());
1075 if ( pArr->compare_exchange_strong( slot, node_ptr(), memory_model::memory_order_acquire, atomics::memory_order_relaxed )) {
1077 gc::template retire<disposer>( slot.ptr());
1079 stats().onEraseSuccess();
1091 value_type * search( hash_type const& hash, typename gc::Guard& guard )
1093 traverse_data pos( hash, *this );
1094 hash_comparator cmp;
1097 node_ptr slot = base_class::traverse( pos );
1098 assert( slot.bits() == 0 );
1100 // protect data node by hazard pointer
1101 if ( guard.protect( pos.pArr->nodes[pos.nSlot], []( node_ptr p ) -> value_type* { return p.ptr(); }) != slot) {
1102 // slot value has been changed - retry
1103 stats().onSlotChanged();
1106 else if ( slot.ptr() && cmp( hash, hash_accessor()( *slot.ptr())) == 0 ) {
1108 stats().onFindSuccess();
1111 stats().onFindFailed();
1116 template <typename Predicate>
1117 value_type * do_erase( hash_type const& hash, typename gc::Guard& guard, Predicate pred )
1119 traverse_data pos( hash, *this );
1120 hash_comparator cmp;
1122 node_ptr slot = base_class::traverse( pos );
1123 assert( slot.bits() == 0 );
1125 // protect data node by hazard pointer
1126 if ( guard.protect( pos.pArr->nodes[pos.nSlot], []( node_ptr p ) -> value_type* { return p.ptr(); }) != slot ) {
1127 // slot value has been changed - retry
1128 stats().onSlotChanged();
1130 else if ( slot.ptr()) {
1131 if ( cmp( hash, hash_accessor()( *slot.ptr())) == 0 && pred( *slot.ptr())) {
1132 // item found - replace it with nullptr
1133 if ( pos.pArr->nodes[pos.nSlot].compare_exchange_strong( slot, node_ptr( nullptr ), memory_model::memory_order_acquire, atomics::memory_order_relaxed)) {
1134 // slot is guarded by HP
1135 gc::template retire<disposer>( slot.ptr());
1137 stats().onEraseSuccess();
1141 stats().onEraseRetry();
1144 stats().onEraseFailed();
1148 // the slot is empty
1149 stats().onEraseFailed();
1155 bool do_erase_at( iterator_base const& iter )
1157 if ( iter.m_set != this )
1159 if ( iter.m_pNode == head()) {
1160 if ( iter.m_idx >= head_size())
1163 else if ( iter.m_idx >= array_node_size())
1167 node_ptr slot = iter.m_pNode->nodes[iter.m_idx].load( memory_model::memory_order_acquire );
1168 if ( slot.bits() == 0 && slot.ptr() == iter.pointer()) {
1169 if ( iter.m_pNode->nodes[iter.m_idx].compare_exchange_strong( slot, node_ptr( nullptr ), memory_model::memory_order_acquire, atomics::memory_order_relaxed )) {
1170 // the item is guarded by iterator, so we may retire it safely
1171 gc::template retire<disposer>( slot.ptr());
1173 stats().onEraseSuccess();
1182 template <typename Func>
1183 std::pair<bool, bool> do_update( value_type& val, Func f, bool bInsert = true )
1185 hash_type const& hash = hash_accessor()( val );
1186 traverse_data pos( hash, *this );
1187 hash_comparator cmp;
1188 typename gc::template GuardArray<2> guards;
1190 guards.assign( 1, &val );
1192 node_ptr slot = base_class::traverse( pos );
1193 assert( slot.bits() == 0 );
1195 // protect data node by hazard pointer
1196 if ( guards.protect( 0, pos.pArr->nodes[pos.nSlot], []( node_ptr p ) -> value_type* { return p.ptr(); }) != slot ) {
1197 // slot value has been changed - retry
1198 stats().onSlotChanged();
1200 else if ( slot.ptr()) {
1201 if ( cmp( hash, hash_accessor()( *slot.ptr())) == 0 ) {
1202 // the item with that hash value already exists
1203 // Replace it with val
1204 if ( slot.ptr() == &val ) {
1205 stats().onUpdateExisting();
1206 return std::make_pair( true, false );
1209 if ( pos.pArr->nodes[pos.nSlot].compare_exchange_strong( slot, node_ptr( &val ), memory_model::memory_order_release, atomics::memory_order_relaxed )) {
1210 // slot can be disposed
1211 f( val, slot.ptr());
1212 gc::template retire<disposer>( slot.ptr());
1213 stats().onUpdateExisting();
1214 return std::make_pair( true, false );
1217 stats().onUpdateRetry();
1222 if ( !pos.splitter.eos() ) {
1223 // the slot must be expanded
1224 base_class::expand_slot( pos, slot );
1227 return std::make_pair( false, false );
1230 stats().onUpdateFailed();
1231 return std::make_pair( false, false );
1235 // the slot is empty, try to insert data node
1238 if ( pos.pArr->nodes[pos.nSlot].compare_exchange_strong( pNull, node_ptr( &val ), memory_model::memory_order_release, atomics::memory_order_relaxed ))
1240 // the new data node has been inserted
1243 stats().onUpdateNew();
1244 stats().height( pos.nHeight );
1245 return std::make_pair( true, true );
1249 stats().onUpdateFailed();
1250 return std::make_pair( false, false );
1253 // insert failed - slot has been changed by another thread
1255 stats().onUpdateRetry();
1261 }} // namespace cds::intrusive
1263 #endif // #ifndef CDSLIB_INTRUSIVE_IMPL_FELDMAN_HASHSET_H