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;
150 typedef typename base_class::node_ptr node_ptr;
151 typedef typename base_class::atomic_node_ptr atomic_node_ptr;
152 typedef typename base_class::array_node array_node;
153 typedef typename base_class::traverse_data traverse_data;
155 using base_class::to_array;
156 using base_class::to_node;
157 using base_class::stats;
158 using base_class::head;
159 using base_class::metrics;
166 friend class FeldmanHashSet;
169 array_node * m_pNode; ///< current array node
170 size_t m_idx; ///< current position in m_pNode
171 typename gc::Guard m_guard; ///< HP guard
172 FeldmanHashSet const* m_set; ///< Hash set
175 iterator_base() CDS_NOEXCEPT
181 iterator_base( iterator_base const& rhs ) CDS_NOEXCEPT
182 : m_pNode( rhs.m_pNode )
186 m_guard.copy( rhs.m_guard );
189 iterator_base& operator=(iterator_base const& rhs) CDS_NOEXCEPT
191 m_pNode = rhs.m_pNode;
194 m_guard.copy( rhs.m_guard );
198 iterator_base& operator++()
204 iterator_base& operator--()
215 bool operator ==(iterator_base const& rhs) const CDS_NOEXCEPT
217 return m_pNode == rhs.m_pNode && m_idx == rhs.m_idx && m_set == rhs.m_set;
220 bool operator !=(iterator_base const& rhs) const CDS_NOEXCEPT
222 return !( *this == rhs );
226 iterator_base( FeldmanHashSet const& set, array_node * pNode, size_t idx, bool )
232 iterator_base( FeldmanHashSet const& set, array_node * pNode, size_t idx )
240 value_type * pointer() const CDS_NOEXCEPT
242 return m_guard.template get<value_type>();
247 assert( m_set != nullptr );
248 assert( m_pNode != nullptr );
250 size_t const arrayNodeSize = m_set->array_node_size();
251 size_t const headSize = m_set->head_size();
252 array_node * pNode = m_pNode;
253 size_t idx = m_idx + 1;
254 size_t nodeSize = m_pNode->pParent? arrayNodeSize : headSize;
257 if ( idx < nodeSize ) {
258 node_ptr slot = pNode->nodes[idx].load( memory_model::memory_order_acquire );
259 if ( slot.bits() == base_class::flag_array_node ) {
260 // array node, go down the tree
261 assert( slot.ptr() != nullptr );
262 pNode = to_array( slot.ptr());
264 nodeSize = arrayNodeSize;
266 else if ( slot.bits() == base_class::flag_array_converting ) {
267 // the slot is converting to array node right now - skip the node
273 if ( m_guard.protect( pNode->nodes[idx], [](node_ptr p) -> value_type * { return p.ptr(); }) == slot ) {
284 if ( pNode->pParent ) {
285 idx = pNode->idxParent + 1;
286 pNode = pNode->pParent;
287 nodeSize = pNode->pParent ? arrayNodeSize : headSize;
291 assert( pNode == m_set->head());
292 assert( idx == headSize );
303 assert( m_set != nullptr );
304 assert( m_pNode != nullptr );
306 size_t const arrayNodeSize = m_set->array_node_size();
307 size_t const headSize = m_set->head_size();
308 size_t const endIdx = size_t(0) - 1;
310 array_node * pNode = m_pNode;
311 size_t idx = m_idx - 1;
312 size_t nodeSize = m_pNode->pParent? arrayNodeSize : headSize;
315 if ( idx != endIdx ) {
316 node_ptr slot = pNode->nodes[idx].load( memory_model::memory_order_acquire );
317 if ( slot.bits() == base_class::flag_array_node ) {
318 // array node, go down the tree
319 assert( slot.ptr() != nullptr );
320 pNode = to_array( slot.ptr());
321 nodeSize = arrayNodeSize;
324 else if ( slot.bits() == base_class::flag_array_converting ) {
325 // the slot is converting to array node right now - skip the node
331 if ( m_guard.protect( pNode->nodes[idx], [](node_ptr p) -> value_type * { return p.ptr(); }) == slot ) {
342 if ( pNode->pParent ) {
343 idx = pNode->idxParent - 1;
344 pNode = pNode->pParent;
345 nodeSize = pNode->pParent ? arrayNodeSize : headSize;
349 assert( pNode == m_set->head());
350 assert( idx == endIdx );
360 template <class Iterator>
361 Iterator init_begin() const
363 return Iterator( *this, head(), size_t(0) - 1 );
366 template <class Iterator>
367 Iterator init_end() const
369 return Iterator( *this, head(), head_size(), false );
372 template <class Iterator>
373 Iterator init_rbegin() const
375 return Iterator( *this, head(), head_size());
378 template <class Iterator>
379 Iterator init_rend() const
381 return Iterator( *this, head(), size_t(0) - 1, false );
384 /// Bidirectional iterator class
385 template <bool IsConst>
386 class bidirectional_iterator: protected iterator_base
388 friend class FeldmanHashSet;
391 static CDS_CONSTEXPR bool const c_bConstantIterator = IsConst;
394 typedef typename std::conditional< IsConst, value_type const*, value_type*>::type value_ptr; ///< Value pointer
395 typedef typename std::conditional< IsConst, value_type const&, value_type&>::type value_ref; ///< Value reference
398 bidirectional_iterator() CDS_NOEXCEPT
401 bidirectional_iterator( bidirectional_iterator const& rhs ) CDS_NOEXCEPT
402 : iterator_base( rhs )
405 bidirectional_iterator& operator=(bidirectional_iterator const& rhs) CDS_NOEXCEPT
407 iterator_base::operator=( rhs );
411 bidirectional_iterator& operator++()
413 iterator_base::operator++();
417 bidirectional_iterator& operator--()
419 iterator_base::operator--();
423 value_ptr operator ->() const CDS_NOEXCEPT
425 return iterator_base::pointer();
428 value_ref operator *() const CDS_NOEXCEPT
430 value_ptr p = iterator_base::pointer();
437 iterator_base::release();
440 template <bool IsConst2>
441 bool operator ==(bidirectional_iterator<IsConst2> const& rhs) const CDS_NOEXCEPT
443 return iterator_base::operator==( rhs );
446 template <bool IsConst2>
447 bool operator !=(bidirectional_iterator<IsConst2> const& rhs) const CDS_NOEXCEPT
449 return !( *this == rhs );
453 bidirectional_iterator( FeldmanHashSet& set, array_node * pNode, size_t idx, bool )
454 : iterator_base( set, pNode, idx, false )
457 bidirectional_iterator( FeldmanHashSet& set, array_node * pNode, size_t idx )
458 : iterator_base( set, pNode, idx )
462 /// Reverse bidirectional iterator
463 template <bool IsConst>
464 class reverse_bidirectional_iterator : public iterator_base
466 friend class FeldmanHashSet;
469 typedef typename std::conditional< IsConst, value_type const*, value_type*>::type value_ptr; ///< Value pointer
470 typedef typename std::conditional< IsConst, value_type const&, value_type&>::type value_ref; ///< Value reference
473 reverse_bidirectional_iterator() CDS_NOEXCEPT
477 reverse_bidirectional_iterator( reverse_bidirectional_iterator const& rhs ) CDS_NOEXCEPT
478 : iterator_base( rhs )
481 reverse_bidirectional_iterator& operator=( reverse_bidirectional_iterator const& rhs) CDS_NOEXCEPT
483 iterator_base::operator=( rhs );
487 reverse_bidirectional_iterator& operator++()
489 iterator_base::operator--();
493 reverse_bidirectional_iterator& operator--()
495 iterator_base::operator++();
499 value_ptr operator ->() const CDS_NOEXCEPT
501 return iterator_base::pointer();
504 value_ref operator *() const CDS_NOEXCEPT
506 value_ptr p = iterator_base::pointer();
513 iterator_base::release();
516 template <bool IsConst2>
517 bool operator ==(reverse_bidirectional_iterator<IsConst2> const& rhs) const
519 return iterator_base::operator==( rhs );
522 template <bool IsConst2>
523 bool operator !=(reverse_bidirectional_iterator<IsConst2> const& rhs)
525 return !( *this == rhs );
529 reverse_bidirectional_iterator( FeldmanHashSet& set, array_node * pNode, size_t idx, bool )
530 : iterator_base( set, pNode, idx, false )
533 reverse_bidirectional_iterator( FeldmanHashSet& set, array_node * pNode, size_t idx )
534 : iterator_base( set, pNode, idx, false )
536 iterator_base::backward();
542 #ifdef CDS_DOXYGEN_INVOKED
543 typedef implementation_defined iterator; ///< @ref cds_intrusive_FeldmanHashSet_iterators "bidirectional iterator" type
544 typedef implementation_defined const_iterator; ///< @ref cds_intrusive_FeldmanHashSet_iterators "bidirectional const iterator" type
545 typedef implementation_defined reverse_iterator; ///< @ref cds_intrusive_FeldmanHashSet_iterators "bidirectional reverse iterator" type
546 typedef implementation_defined const_reverse_iterator; ///< @ref cds_intrusive_FeldmanHashSet_iterators "bidirectional reverse const iterator" type
548 typedef bidirectional_iterator<false> iterator;
549 typedef bidirectional_iterator<true> const_iterator;
550 typedef reverse_bidirectional_iterator<false> reverse_iterator;
551 typedef reverse_bidirectional_iterator<true> const_reverse_iterator;
556 item_counter m_ItemCounter; ///< Item counter
560 /// Creates empty set
562 @param head_bits: 2<sup>head_bits</sup> specifies the size of head array, minimum is 4.
563 @param array_bits: 2<sup>array_bits</sup> specifies the size of array node, minimum is 2.
565 Equation for \p head_bits and \p array_bits:
567 sizeof(hash_type) * 8 == head_bits + N * array_bits
569 where \p N is multi-level array depth.
571 FeldmanHashSet( size_t head_bits = 8, size_t array_bits = 4 )
572 : base_class( head_bits, array_bits )
575 /// Destructs the set and frees all data
583 The function inserts \p val in the set if it does not contain
584 an item with that hash.
586 Returns \p true if \p val is placed into the set, \p false otherwise.
588 bool insert( value_type& val )
590 return insert( val, [](value_type&) {} );
595 This function is intended for derived non-intrusive containers.
597 The function allows to split creating of new item into two part:
598 - create item with key only
599 - insert new item into the set
600 - if inserting is success, calls \p f functor to initialize \p val.
602 The functor signature is:
604 void func( value_type& val );
606 where \p val is the item inserted.
608 The user-defined functor is called only if the inserting is success.
610 @warning See \ref cds_intrusive_item_creating "insert item troubleshooting".
612 template <typename Func>
613 bool insert( value_type& val, Func f )
615 hash_type const& hash = hash_accessor()(val);
616 traverse_data pos( hash, *this );
618 typename gc::template GuardArray<2> guards;
620 guards.assign( 1, &val );
622 node_ptr slot = base_class::traverse( pos );
623 assert( slot.bits() == 0 );
625 // protect data node by hazard pointer
626 if (guards.protect( 0, pos.pArr->nodes[pos.nSlot], [](node_ptr p) -> value_type * { return p.ptr(); }) != slot ) {
627 // slot value has been changed - retry
628 stats().onSlotChanged();
632 if ( cmp( hash, hash_accessor()(*slot.ptr())) == 0 ) {
633 // the item with that hash value already exists
634 stats().onInsertFailed();
638 // the slot must be expanded
639 base_class::expand_slot( pos, slot );
642 // the slot is empty, try to insert data node
644 if ( pos.pArr->nodes[pos.nSlot].compare_exchange_strong( pNull, node_ptr(&val), memory_model::memory_order_release, atomics::memory_order_relaxed ))
646 // the new data node has been inserted
649 stats().onInsertSuccess();
650 stats().height(pos.nHeight);
654 // insert failed - slot has been changed by another thread
656 stats().onInsertRetry();
663 Performs inserting or updating the item with hash value equal to \p val.
664 - If hash value is found then existing item is replaced with \p val, old item is disposed
665 with \p Traits::disposer. Note that the disposer is called by \p GC asynchronously.
666 The function returns <tt> std::pair<true, false> </tt>
667 - If hash value is not found and \p bInsert is \p true then \p val is inserted,
668 the function returns <tt> std::pair<true, true> </tt>
669 - If hash value is not found and \p bInsert is \p false then the set is unchanged,
670 the function returns <tt> std::pair<false, false> </tt>
672 Returns <tt> std::pair<bool, bool> </tt> where \p first is \p true if operation is successfull
673 (i.e. the item has been inserted or updated),
674 \p second is \p true if new item has been added or \p false if the set contains that hash.
676 std::pair<bool, bool> update( value_type& val, bool bInsert = true )
678 return do_update(val, [](value_type&, value_type *) {}, bInsert );
681 /// Unlinks the item \p val from the set
683 The function searches the item \p val in the set and unlink it
684 if it is found and its address is equal to <tt>&val</tt>.
686 The function returns \p true if success and \p false otherwise.
688 bool unlink( value_type const& val )
690 typename gc::Guard guard;
691 auto pred = [&val](value_type const& item) -> bool { return &item == &val; };
692 value_type * p = do_erase( hash_accessor()( val ), guard, std::ref( pred ));
696 /// Deletes the item from the set
698 The function searches \p hash in the set,
699 unlinks the item found, and returns \p true.
700 If that item is not found the function returns \p false.
702 The \ref disposer specified in \p Traits is called by garbage collector \p GC asynchronously.
704 bool erase( hash_type const& hash )
706 return erase(hash, [](value_type const&) {} );
709 /// Deletes the item from the set
711 The function searches \p hash in the set,
712 call \p f functor with item found, and unlinks it from the set.
713 The \ref disposer specified in \p Traits is called
714 by garbage collector \p GC asynchronously.
716 The \p Func interface is
719 void operator()( value_type& item );
723 If \p hash is not found the function returns \p false.
725 template <typename Func>
726 bool erase( hash_type const& hash, Func f )
728 typename gc::Guard guard;
729 value_type * p = do_erase( hash, guard, []( value_type const&) -> bool {return true; } );
731 // p is guarded by HP
739 /// Deletes the item pointed by iterator \p iter
741 Returns \p true if the operation is successful, \p false otherwise.
743 The function does not invalidate the iterator, it remains valid and can be used for further traversing.
745 bool erase_at( iterator const& iter )
747 return do_erase_at( iter );
750 bool erase_at( reverse_iterator const& iter )
752 return do_erase_at( iter );
756 /// Extracts the item with specified \p hash
758 The function searches \p hash in the set,
759 unlinks it from the set, and returns an guarded pointer to the item extracted.
760 If \p hash is not found the function returns an empty guarded pointer.
762 The \p disposer specified in \p Traits class' template parameter is called automatically
763 by garbage collector \p GC when returned \ref guarded_ptr object to be destroyed or released.
764 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
768 typedef cds::intrusive::FeldmanHashSet< your_template_args > my_set;
772 my_set::guarded_ptr gp( theSet.extract( 5 ));
777 // Destructor of gp releases internal HP guard
781 guarded_ptr extract( hash_type const& hash )
785 typename gc::Guard guard;
786 value_type * p = do_erase( hash, guard, []( value_type const&) -> bool {return true;} );
788 // p is guarded by HP
795 /// Finds an item by it's \p hash
797 The function searches the item by \p hash and calls the functor \p f for item found.
798 The interface of \p Func functor is:
801 void operator()( value_type& item );
804 where \p item is the item found.
806 The functor may change non-key fields of \p item. Note that the functor is only guarantee
807 that \p item cannot be disposed during the functor is executing.
808 The functor does not serialize simultaneous access to the set's \p item. If such access is
809 possible you must provide your own synchronization schema on item level to prevent unsafe item modifications.
811 The function returns \p true if \p hash is found, \p false otherwise.
813 template <typename Func>
814 bool find( hash_type const& hash, Func f )
816 typename gc::Guard guard;
817 value_type * p = search( hash, guard );
819 // p is guarded by HP
827 /// Checks whether the set contains \p hash
829 The function searches the item by its \p hash
830 and returns \p true if it is found, or \p false otherwise.
832 bool contains( hash_type const& hash )
834 return find( hash, [](value_type&) {} );
837 /// Finds an item by it's \p hash and returns the item found
839 The function searches the item by its \p hash
840 and returns the guarded pointer to the item found.
841 If \p hash is not found the function returns an empty \p guarded_ptr.
843 @note Each \p guarded_ptr object uses one GC's guard which can be limited resource.
847 typedef cds::intrusive::FeldmanHashSet< your_template_params > my_set;
851 my_set::guarded_ptr gp( theSet.get( 5 ));
852 if ( theSet.get( 5 )) {
856 // Destructor of guarded_ptr releases internal HP guard
860 guarded_ptr get( hash_type const& hash )
864 typename gc::Guard guard;
865 gp.reset( search( hash, guard ));
870 /// Clears the set (non-atomic)
872 The function unlink all data node from the set.
873 The function is not atomic but is thread-safe.
874 After \p %clear() the set may not be empty because another threads may insert items.
876 For each item the \p disposer is called after unlinking.
880 clear_array( head(), head_size());
883 /// Checks if the set is empty
885 Emptiness is checked by item counting: if item count is zero then the set is empty.
886 Thus, the correct item counting feature is an important part of the set implementation.
893 /// Returns item count in the set
896 return m_ItemCounter;
899 /// Returns const reference to internal statistics
900 stat const& statistics() const
905 /// Returns the size of head node
906 using base_class::head_size;
908 /// Returns the size of the array node
909 using base_class::array_node_size;
911 /// Collects tree level statistics into \p stat
913 The function traverses the set and collects statistics for each level of the tree
914 into \p feldman_hashset::level_statistics struct. The element of \p stat[i]
915 represents statistics for level \p i, level 0 is head array.
916 The function is thread-safe and may be called in multi-threaded environment.
918 Result can be useful for estimating efficiency of hash functor you use.
920 void get_level_statistics(std::vector< feldman_hashset::level_statistics>& stat) const
922 base_class::get_level_statistics( stat );
926 ///@name Thread-safe iterators
927 /** @anchor cds_intrusive_FeldmanHashSet_iterators
928 The set supports thread-safe iterators: you may iterate over the set in multi-threaded environment.
929 It is guaranteed that the iterators will remain valid even if another thread deletes the node the iterator points to:
930 Hazard Pointer embedded into the iterator object protects the node from physical reclamation.
932 @note Since the iterator object contains hazard pointer that is a thread-local resource,
933 the iterator should not be passed to another thread.
935 Each iterator object supports the common interface:
936 - dereference operators:
938 value_type [const] * operator ->() noexcept
939 value_type [const] & operator *() noexcept
941 - pre-increment and pre-decrement. Post-operators is not supported
942 - equality operators <tt>==</tt> and <tt>!=</tt>.
943 Iterators are equal iff they point to the same cell of the same array node.
944 Note that for two iterators \p it1 and \p it2, the conditon <tt> it1 == it2 </tt>
945 does not entail <tt> &(*it1) == &(*it2) </tt>: welcome to concurrent containers
946 - helper member function \p release() that clears internal hazard pointer.
947 After \p release() the iterator points to \p nullptr but it still remain valid: further iterating is possible.
949 During iteration you may safely erase any item from the set;
950 @ref erase_at() function call doesn't invalidate any iterator.
951 If some iterator points to the item to be erased, that item is not deleted immediately
952 but only after that iterator will be advanced forward or backward.
954 @note It is possible the item can be iterated more that once, for example, if an iterator points to the item
955 in array node that is being splitted.
959 /// Returns an iterator to the beginning of the set
962 return iterator( *this, head(), size_t(0) - 1 );
965 /// Returns an const iterator to the beginning of the set
966 const_iterator begin() const
968 return const_iterator( *this, head(), size_t(0) - 1 );
971 /// Returns an const iterator to the beginning of the set
972 const_iterator cbegin()
974 return const_iterator( *this, head(), size_t(0) - 1 );
977 /// 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.
980 return iterator( *this, head(), head_size(), false );
983 /// Returns a const iterator to the element following the last element of the set. This element acts as a placeholder; attempting to access it results in undefined behavior.
984 const_iterator end() const
986 return const_iterator( *this, head(), head_size(), false );
989 /// 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.
990 const_iterator cend()
992 return const_iterator( *this, head(), head_size(), false );
995 /// Returns a reverse iterator to the first element of the reversed set
996 reverse_iterator rbegin()
998 return reverse_iterator( *this, head(), head_size());
1001 /// Returns a const reverse iterator to the first element of the reversed set
1002 const_reverse_iterator rbegin() const
1004 return const_reverse_iterator( *this, head(), head_size());
1007 /// Returns a const reverse iterator to the first element of the reversed set
1008 const_reverse_iterator crbegin()
1010 return const_reverse_iterator( *this, head(), head_size());
1013 /// Returns a reverse iterator to the element following the last element of the reversed set
1015 It corresponds to the element preceding the first element of the non-reversed container.
1016 This element acts as a placeholder, attempting to access it results in undefined behavior.
1018 reverse_iterator rend()
1020 return reverse_iterator( *this, head(), size_t(0) - 1, false );
1023 /// Returns a const reverse iterator to the element following the last element of the reversed set
1025 It corresponds to the element preceding the first element of the non-reversed container.
1026 This element acts as a placeholder, attempting to access it results in undefined behavior.
1028 const_reverse_iterator rend() const
1030 return const_reverse_iterator( *this, head(), size_t(0) - 1, false );
1033 /// Returns a const reverse iterator to the element following the last element of the reversed set
1035 It corresponds to the element preceding the first element of the non-reversed container.
1036 This element acts as a placeholder, attempting to access it results in undefined behavior.
1038 const_reverse_iterator crend()
1040 return const_reverse_iterator( *this, head(), size_t(0) - 1, false );
1046 void clear_array( array_node * pArrNode, size_t nSize )
1050 for ( atomic_node_ptr * pArr = pArrNode->nodes, *pLast = pArr + nSize; pArr != pLast; ++pArr ) {
1052 node_ptr slot = pArr->load( memory_model::memory_order_acquire );
1053 if ( slot.bits() == base_class::flag_array_node ) {
1054 // array node, go down the tree
1055 assert( slot.ptr() != nullptr );
1056 clear_array( to_array( slot.ptr()), array_node_size());
1059 else if ( slot.bits() == base_class::flag_array_converting ) {
1060 // the slot is converting to array node right now
1061 while ( (slot = pArr->load(memory_model::memory_order_acquire)).bits() == base_class::flag_array_converting ) {
1063 stats().onSlotConverting();
1067 assert( slot.ptr() != nullptr );
1068 assert( slot.bits() == base_class::flag_array_node );
1069 clear_array( to_array( slot.ptr()), array_node_size());
1074 if ( pArr->compare_exchange_strong( slot, node_ptr(), memory_model::memory_order_acquire, atomics::memory_order_relaxed )) {
1076 gc::template retire<disposer>( slot.ptr());
1078 stats().onEraseSuccess();
1090 value_type * search( hash_type const& hash, typename gc::Guard& guard )
1092 traverse_data pos( hash, *this );
1093 hash_comparator cmp;
1096 node_ptr slot = base_class::traverse( pos );
1097 assert(slot.bits() == 0);
1099 // protect data node by hazard pointer
1100 if (guard.protect( pos.pArr->nodes[pos.nSlot], [](node_ptr p) -> value_type * { return p.ptr(); }) != slot) {
1101 // slot value has been changed - retry
1102 stats().onSlotChanged();
1105 else if (slot.ptr() && cmp(hash, hash_accessor()(*slot.ptr())) == 0) {
1107 stats().onFindSuccess();
1110 stats().onFindFailed();
1115 template <typename Predicate>
1116 value_type * do_erase( hash_type const& hash, typename gc::Guard& guard, Predicate pred )
1118 traverse_data pos( hash, *this );
1119 hash_comparator cmp;
1121 node_ptr slot = base_class::traverse( pos );
1122 assert(slot.bits() == 0);
1124 // protect data node by hazard pointer
1125 if (guard.protect( pos.pArr->nodes[pos.nSlot], [](node_ptr p) -> value_type * { return p.ptr(); }) != slot) {
1126 // slot value has been changed - retry
1127 stats().onSlotChanged();
1129 else if (slot.ptr()) {
1130 if ( cmp(hash, hash_accessor()(*slot.ptr())) == 0 && pred(*slot.ptr())) {
1131 // item found - replace it with nullptr
1132 if ( pos.pArr->nodes[pos.nSlot].compare_exchange_strong(slot, node_ptr(nullptr), memory_model::memory_order_acquire, atomics::memory_order_relaxed)) {
1133 // slot is guarded by HP
1134 gc::template retire<disposer>(slot.ptr());
1136 stats().onEraseSuccess();
1140 stats().onEraseRetry();
1143 stats().onEraseFailed();
1147 // the slot is empty
1148 stats().onEraseFailed();
1154 bool do_erase_at( iterator_base const& iter )
1156 if ( iter.m_set != this )
1158 if ( iter.m_pNode == head() && iter.m_idx >= head_size())
1160 if ( iter.m_idx >= array_node_size())
1164 node_ptr slot = iter.m_pNode->nodes[iter.m_idx].load( memory_model::memory_order_acquire );
1165 if ( slot.bits() == 0 && slot.ptr() == iter.pointer()) {
1166 if ( iter.m_pNode->nodes[iter.m_idx].compare_exchange_strong(slot, node_ptr(nullptr), memory_model::memory_order_acquire, atomics::memory_order_relaxed)) {
1167 // the item is guarded by iterator, so we may retire it safely
1168 gc::template retire<disposer>( slot.ptr());
1170 stats().onEraseSuccess();
1179 template <typename Func>
1180 std::pair<bool, bool> do_update( value_type& val, Func f, bool bInsert = true )
1182 hash_type const& hash = hash_accessor()( val );
1183 traverse_data pos( hash, *this );
1184 hash_comparator cmp;
1185 typename gc::template GuardArray<2> guards;
1187 guards.assign( 1, &val );
1189 node_ptr slot = base_class::traverse( pos );
1190 assert(slot.bits() == 0);
1192 // protect data node by hazard pointer
1193 if ( guards.protect( 0, pos.pArr->nodes[pos.nSlot], [](node_ptr p) -> value_type * { return p.ptr(); }) != slot ) {
1194 // slot value has been changed - retry
1195 stats().onSlotChanged();
1197 else if ( slot.ptr()) {
1198 if ( cmp( hash, hash_accessor()(*slot.ptr())) == 0 ) {
1199 // the item with that hash value already exists
1200 // Replace it with val
1201 if ( slot.ptr() == &val ) {
1202 stats().onUpdateExisting();
1203 return std::make_pair(true, false);
1206 if ( pos.pArr->nodes[pos.nSlot].compare_exchange_strong(slot, node_ptr(&val), memory_model::memory_order_release, atomics::memory_order_relaxed)) {
1207 // slot can be disposed
1208 f( val, slot.ptr());
1209 gc::template retire<disposer>( slot.ptr());
1210 stats().onUpdateExisting();
1211 return std::make_pair(true, false);
1214 stats().onUpdateRetry();
1219 // the slot must be expanded
1220 base_class::expand_slot( pos, slot );
1223 stats().onUpdateFailed();
1224 return std::make_pair(false, false);
1228 // the slot is empty, try to insert data node
1231 if ( pos.pArr->nodes[pos.nSlot].compare_exchange_strong(pNull, node_ptr(&val), memory_model::memory_order_release, atomics::memory_order_relaxed))
1233 // the new data node has been inserted
1236 stats().onUpdateNew();
1237 stats().height( pos.nHeight );
1238 return std::make_pair(true, true);
1242 stats().onUpdateFailed();
1243 return std::make_pair(false, false);
1246 // insert failed - slot has been changed by another thread
1248 stats().onUpdateRetry();
1254 }} // namespace cds::intrusive
1256 #endif // #ifndef CDSLIB_INTRUSIVE_IMPL_FELDMAN_HASHSET_H