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();
635 if ( cmp( hash, hash_accessor()(*slot.ptr())) == 0 ) {
636 // the item with that hash value already exists
637 stats().onInsertFailed();
641 // the slot must be expanded
642 base_class::expand_slot( pos, slot );
645 // the slot is empty, try to insert data node
647 if ( pos.pArr->nodes[pos.nSlot].compare_exchange_strong( pNull, node_ptr(&val), memory_model::memory_order_release, atomics::memory_order_relaxed ))
649 // the new data node has been inserted
652 stats().onInsertSuccess();
653 stats().height(pos.nHeight);
657 // insert failed - slot has been changed by another thread
659 stats().onInsertRetry();
666 Performs inserting or updating the item with hash value equal to \p val.
667 - If hash value is found then existing item is replaced with \p val, old item is disposed
668 with \p Traits::disposer. Note that the disposer is called by \p GC asynchronously.
669 The function returns <tt> std::pair<true, false> </tt>
670 - If hash value is not found and \p bInsert is \p true then \p val is inserted,
671 the function returns <tt> std::pair<true, true> </tt>
672 - If hash value is not found and \p bInsert is \p false then the set is unchanged,
673 the function returns <tt> std::pair<false, false> </tt>
675 Returns <tt> std::pair<bool, bool> </tt> where \p first is \p true if operation is successfull
676 (i.e. the item has been inserted or updated),
677 \p second is \p true if new item has been added or \p false if the set contains that hash.
679 std::pair<bool, bool> update( value_type& val, bool bInsert = true )
681 return do_update(val, [](value_type&, value_type *) {}, bInsert );
684 /// Unlinks the item \p val from the set
686 The function searches the item \p val in the set and unlink it
687 if it is found and its address is equal to <tt>&val</tt>.
689 The function returns \p true if success and \p false otherwise.
691 bool unlink( value_type const& val )
693 typename gc::Guard guard;
694 auto pred = [&val](value_type const& item) -> bool { return &item == &val; };
695 value_type * p = do_erase( hash_accessor()( val ), guard, std::ref( pred ));
699 /// Deletes the item from the set
701 The function searches \p hash in the set,
702 unlinks the item found, and returns \p true.
703 If that item is not found the function returns \p false.
705 The \ref disposer specified in \p Traits is called by garbage collector \p GC asynchronously.
707 bool erase( hash_type const& hash )
709 return erase(hash, [](value_type const&) {} );
712 /// Deletes the item from the set
714 The function searches \p hash in the set,
715 call \p f functor with item found, and unlinks it from the set.
716 The \ref disposer specified in \p Traits is called
717 by garbage collector \p GC asynchronously.
719 The \p Func interface is
722 void operator()( value_type& item );
726 If \p hash is not found the function returns \p false.
728 template <typename Func>
729 bool erase( hash_type const& hash, Func f )
731 typename gc::Guard guard;
732 value_type * p = do_erase( hash, guard, []( value_type const&) -> bool {return true; } );
734 // p is guarded by HP
742 /// Deletes the item pointed by iterator \p iter
744 Returns \p true if the operation is successful, \p false otherwise.
746 The function does not invalidate the iterator, it remains valid and can be used for further traversing.
748 bool erase_at( iterator const& iter )
750 return do_erase_at( iter );
753 bool erase_at( reverse_iterator const& iter )
755 return do_erase_at( iter );
759 /// Extracts the item with specified \p hash
761 The function searches \p hash in the set,
762 unlinks it from the set, and returns an guarded pointer to the item extracted.
763 If \p hash is not found the function returns an empty guarded pointer.
765 The \p disposer specified in \p Traits class' template parameter is called automatically
766 by garbage collector \p GC when returned \ref guarded_ptr object to be destroyed or released.
767 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
771 typedef cds::intrusive::FeldmanHashSet< your_template_args > my_set;
775 my_set::guarded_ptr gp( theSet.extract( 5 ));
780 // Destructor of gp releases internal HP guard
784 guarded_ptr extract( hash_type const& hash )
788 typename gc::Guard guard;
789 value_type * p = do_erase( hash, guard, []( value_type const&) -> bool {return true;} );
791 // p is guarded by HP
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 )
867 typename gc::Guard guard;
868 gp.reset( search( hash, guard ));
873 /// Clears the set (non-atomic)
875 The function unlink all data node from the set.
876 The function is not atomic but is thread-safe.
877 After \p %clear() the set may not be empty because another threads may insert items.
879 For each item the \p disposer is called after unlinking.
883 clear_array( head(), head_size());
886 /// Checks if the set is empty
888 Emptiness is checked by item counting: if item count is zero then the set is empty.
889 Thus, the correct item counting feature is an important part of the set implementation.
896 /// Returns item count in the set
899 return m_ItemCounter;
902 /// Returns const reference to internal statistics
903 stat const& statistics() const
908 /// Returns the size of head node
909 using base_class::head_size;
911 /// Returns the size of the array node
912 using base_class::array_node_size;
914 /// Collects tree level statistics into \p stat
916 The function traverses the set and collects statistics for each level of the tree
917 into \p feldman_hashset::level_statistics struct. The element of \p stat[i]
918 represents statistics for level \p i, level 0 is head array.
919 The function is thread-safe and may be called in multi-threaded environment.
921 Result can be useful for estimating efficiency of hash functor you use.
923 void get_level_statistics(std::vector< feldman_hashset::level_statistics>& stat) const
925 base_class::get_level_statistics( stat );
929 ///@name Thread-safe iterators
930 /** @anchor cds_intrusive_FeldmanHashSet_iterators
931 The set supports thread-safe iterators: you may iterate over the set in multi-threaded environment.
932 It is guaranteed that the iterators will remain valid even if another thread deletes the node the iterator points to:
933 Hazard Pointer embedded into the iterator object protects the node from physical reclamation.
935 @note Since the iterator object contains hazard pointer that is a thread-local resource,
936 the iterator should not be passed to another thread.
938 Each iterator object supports the common interface:
939 - dereference operators:
941 value_type [const] * operator ->() noexcept
942 value_type [const] & operator *() noexcept
944 - pre-increment and pre-decrement. Post-operators is not supported
945 - equality operators <tt>==</tt> and <tt>!=</tt>.
946 Iterators are equal iff they point to the same cell of the same array node.
947 Note that for two iterators \p it1 and \p it2, the conditon <tt> it1 == it2 </tt>
948 does not entail <tt> &(*it1) == &(*it2) </tt>: welcome to concurrent containers
949 - helper member function \p release() that clears internal hazard pointer.
950 After \p release() the iterator points to \p nullptr but it still remain valid: further iterating is possible.
952 During iteration you may safely erase any item from the set;
953 @ref erase_at() function call doesn't invalidate any iterator.
954 If some iterator points to the item to be erased, that item is not deleted immediately
955 but only after that iterator will be advanced forward or backward.
957 @note It is possible the item can be iterated more that once, for example, if an iterator points to the item
958 in array node that is being splitted.
962 /// Returns an iterator to the beginning of the set
965 return iterator( *this, head(), size_t(0) - 1 );
968 /// Returns an const iterator to the beginning of the set
969 const_iterator begin() const
971 return const_iterator( *this, head(), size_t(0) - 1 );
974 /// Returns an const iterator to the beginning of the set
975 const_iterator cbegin()
977 return const_iterator( *this, head(), size_t(0) - 1 );
980 /// 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.
983 return 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 end() const
989 return const_iterator( *this, head(), head_size(), false );
992 /// 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.
993 const_iterator cend()
995 return const_iterator( *this, head(), head_size(), false );
998 /// Returns a reverse iterator to the first element of the reversed set
999 reverse_iterator rbegin()
1001 return reverse_iterator( *this, head(), head_size());
1004 /// Returns a const reverse iterator to the first element of the reversed set
1005 const_reverse_iterator rbegin() const
1007 return const_reverse_iterator( *this, head(), head_size());
1010 /// Returns a const reverse iterator to the first element of the reversed set
1011 const_reverse_iterator crbegin()
1013 return const_reverse_iterator( *this, head(), head_size());
1016 /// Returns a reverse iterator to the element following the last element of the reversed set
1018 It corresponds to the element preceding the first element of the non-reversed container.
1019 This element acts as a placeholder, attempting to access it results in undefined behavior.
1021 reverse_iterator rend()
1023 return reverse_iterator( *this, head(), size_t(0) - 1, false );
1026 /// Returns a const reverse iterator to the element following the last element of the reversed set
1028 It corresponds to the element preceding the first element of the non-reversed container.
1029 This element acts as a placeholder, attempting to access it results in undefined behavior.
1031 const_reverse_iterator rend() const
1033 return const_reverse_iterator( *this, head(), size_t(0) - 1, false );
1036 /// Returns a const reverse iterator to the element following the last element of the reversed set
1038 It corresponds to the element preceding the first element of the non-reversed container.
1039 This element acts as a placeholder, attempting to access it results in undefined behavior.
1041 const_reverse_iterator crend()
1043 return const_reverse_iterator( *this, head(), size_t(0) - 1, false );
1049 void clear_array( array_node * pArrNode, size_t nSize )
1053 for ( atomic_node_ptr * pArr = pArrNode->nodes, *pLast = pArr + nSize; pArr != pLast; ++pArr ) {
1055 node_ptr slot = pArr->load( memory_model::memory_order_acquire );
1056 if ( slot.bits() == base_class::flag_array_node ) {
1057 // array node, go down the tree
1058 assert( slot.ptr() != nullptr );
1059 clear_array( to_array( slot.ptr()), array_node_size());
1062 else if ( slot.bits() == base_class::flag_array_converting ) {
1063 // the slot is converting to array node right now
1064 while ( (slot = pArr->load(memory_model::memory_order_acquire)).bits() == base_class::flag_array_converting ) {
1066 stats().onSlotConverting();
1070 assert( slot.ptr() != nullptr );
1071 assert( slot.bits() == base_class::flag_array_node );
1072 clear_array( to_array( slot.ptr()), array_node_size());
1077 if ( pArr->compare_exchange_strong( slot, node_ptr(), memory_model::memory_order_acquire, atomics::memory_order_relaxed )) {
1079 gc::template retire<disposer>( slot.ptr());
1081 stats().onEraseSuccess();
1093 value_type * search( hash_type const& hash, typename gc::Guard& guard )
1095 traverse_data pos( hash, *this );
1096 hash_comparator cmp;
1099 node_ptr slot = base_class::traverse( pos );
1100 assert(slot.bits() == 0);
1102 // protect data node by hazard pointer
1103 if (guard.protect( pos.pArr->nodes[pos.nSlot], [](node_ptr p) -> value_type * { return p.ptr(); }) != slot) {
1104 // slot value has been changed - retry
1105 stats().onSlotChanged();
1108 else if (slot.ptr() && cmp(hash, hash_accessor()(*slot.ptr())) == 0) {
1110 stats().onFindSuccess();
1113 stats().onFindFailed();
1118 template <typename Predicate>
1119 value_type * do_erase( hash_type const& hash, typename gc::Guard& guard, Predicate pred )
1121 traverse_data pos( hash, *this );
1122 hash_comparator cmp;
1124 node_ptr slot = base_class::traverse( pos );
1125 assert(slot.bits() == 0);
1127 // protect data node by hazard pointer
1128 if (guard.protect( pos.pArr->nodes[pos.nSlot], [](node_ptr p) -> value_type * { return p.ptr(); }) != slot) {
1129 // slot value has been changed - retry
1130 stats().onSlotChanged();
1132 else if (slot.ptr()) {
1133 if ( cmp(hash, hash_accessor()(*slot.ptr())) == 0 && pred(*slot.ptr())) {
1134 // item found - replace it with nullptr
1135 if ( pos.pArr->nodes[pos.nSlot].compare_exchange_strong(slot, node_ptr(nullptr), memory_model::memory_order_acquire, atomics::memory_order_relaxed)) {
1136 // slot is guarded by HP
1137 gc::template retire<disposer>(slot.ptr());
1139 stats().onEraseSuccess();
1143 stats().onEraseRetry();
1146 stats().onEraseFailed();
1150 // the slot is empty
1151 stats().onEraseFailed();
1157 bool do_erase_at( iterator_base const& iter )
1159 if ( iter.m_set != this )
1161 if ( iter.m_pNode == head()) {
1162 if ( iter.m_idx >= head_size())
1165 else if ( iter.m_idx >= array_node_size())
1169 node_ptr slot = iter.m_pNode->nodes[iter.m_idx].load( memory_model::memory_order_acquire );
1170 if ( slot.bits() == 0 && slot.ptr() == iter.pointer()) {
1171 if ( iter.m_pNode->nodes[iter.m_idx].compare_exchange_strong(slot, node_ptr(nullptr), memory_model::memory_order_acquire, atomics::memory_order_relaxed)) {
1172 // the item is guarded by iterator, so we may retire it safely
1173 gc::template retire<disposer>( slot.ptr());
1175 stats().onEraseSuccess();
1184 template <typename Func>
1185 std::pair<bool, bool> do_update( value_type& val, Func f, bool bInsert = true )
1187 hash_type const& hash = hash_accessor()( val );
1188 traverse_data pos( hash, *this );
1189 hash_comparator cmp;
1190 typename gc::template GuardArray<2> guards;
1192 guards.assign( 1, &val );
1194 node_ptr slot = base_class::traverse( pos );
1195 assert(slot.bits() == 0);
1197 // protect data node by hazard pointer
1198 if ( guards.protect( 0, pos.pArr->nodes[pos.nSlot], [](node_ptr p) -> value_type * { return p.ptr(); }) != slot ) {
1199 // slot value has been changed - retry
1200 stats().onSlotChanged();
1202 else if ( slot.ptr()) {
1203 if ( cmp( hash, hash_accessor()(*slot.ptr())) == 0 ) {
1204 // the item with that hash value already exists
1205 // Replace it with val
1206 if ( slot.ptr() == &val ) {
1207 stats().onUpdateExisting();
1208 return std::make_pair(true, false);
1211 if ( pos.pArr->nodes[pos.nSlot].compare_exchange_strong(slot, node_ptr(&val), memory_model::memory_order_release, atomics::memory_order_relaxed)) {
1212 // slot can be disposed
1213 f( val, slot.ptr());
1214 gc::template retire<disposer>( slot.ptr());
1215 stats().onUpdateExisting();
1216 return std::make_pair(true, false);
1219 stats().onUpdateRetry();
1224 // the slot must be expanded
1225 base_class::expand_slot( pos, slot );
1228 stats().onUpdateFailed();
1229 return std::make_pair(false, false);
1233 // the slot is empty, try to insert data node
1236 if ( pos.pArr->nodes[pos.nSlot].compare_exchange_strong(pNull, node_ptr(&val), memory_model::memory_order_release, atomics::memory_order_relaxed))
1238 // the new data node has been inserted
1241 stats().onUpdateNew();
1242 stats().height( pos.nHeight );
1243 return std::make_pair(true, true);
1247 stats().onUpdateFailed();
1248 return std::make_pair(false, false);
1251 // insert failed - slot has been changed by another thread
1253 stats().onUpdateRetry();
1259 }} // namespace cds::intrusive
1261 #endif // #ifndef CDSLIB_INTRUSIVE_IMPL_FELDMAN_HASHSET_H