3 #ifndef CDSLIB_INTRUSIVE_IMPL_FELDMAN_HASHSET_H
4 #define CDSLIB_INTRUSIVE_IMPL_FELDMAN_HASHSET_H
6 #include <functional> // std::ref
7 #include <iterator> // std::iterator_traits
9 #include <cds/intrusive/details/feldman_hashset_base.h>
10 #include <cds/details/allocator.h>
12 namespace cds { namespace intrusive {
13 /// Intrusive hash set based on multi-level array
14 /** @ingroup cds_intrusive_map
15 @anchor cds_intrusive_FeldmanHashSet_hp
18 - [2013] Steven Feldman, Pierre LaBorde, Damian Dechev "Concurrent Multi-level Arrays:
19 Wait-free Extensible Hash Maps"
21 [From the paper] The hardest problem encountered while developing a parallel hash map is how to perform
22 a global resize, the process of redistributing the elements in a hash map that occurs when adding new
23 buckets. The negative impact of blocking synchronization is multiplied during a global resize, because all
24 threads will be forced to wait on the thread that is performing the involved process of resizing the hash map
25 and redistributing the elements. \p %FeldmanHashSet implementation avoids global resizes through new array
26 allocation. By allowing concurrent expansion this structure is free from the overhead of an explicit resize,
27 which facilitates concurrent operations.
29 The presented design includes dynamic hashing, the use of sub-arrays within the hash map data structure;
30 which, in combination with <b>perfect hashing</b>, means that each element has a unique final, as well as current, position.
31 It is important to note that the perfect hash function required by our hash map is trivial to realize as
32 any hash function that permutes the bits of the key is suitable. This is possible because of our approach
33 to the hash function; we require that it produces hash values that are equal in size to that of the key.
34 We know that if we expand the hash map a fixed number of times there can be no collision as duplicate keys
35 are not provided for in the standard semantics of a hash map.
37 \p %FeldmanHashSet is a multi-level array which has a structure similar to a tree:
38 @image html feldman_hashset.png
39 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.
40 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
41 with that key; it is a simple struct holding two variables. A \p dataNode in the multi-level array could be marked.
42 A \p markedDataNode refers to a pointer to a \p dataNode that has been bitmarked at the least significant bit (LSB)
43 of the pointer to the node. This signifies that this \p dataNode is contended. An expansion must occur at this node;
44 any thread that sees this \p markedDataNode will try to replace it with an \p arrayNode; which is a position that holds
45 an array of nodes. The pointer to an \p arrayNode is differentiated from that of a pointer to a \p dataNode by a bitmark
46 on the second-least significant bit.
48 \p %FeldmanHashSet multi-level array is similar to a tree in that we keep a pointer to the root, which is a memory array
49 called \p head. The length of the \p head memory array is unique, whereas every other \p arrayNode has a uniform length;
50 a normal \p arrayNode has a fixed power-of-two length equal to the binary logarithm of a variable called \p arrayLength.
51 The maximum depth of the tree, \p maxDepth, is the maximum number of pointers that must be followed to reach any node.
52 We define \p currentDepth as the number of memory arrays that we need to traverse to reach the \p arrayNode on which
53 we need to operate; this is initially one, because of \p head.
55 That approach to the structure of the hash set uses an extensible hashing scheme; <b> the hash value is treated as a bit
56 string</b> and rehash incrementally.
58 @note Two important things you should keep in mind when you're using \p %FeldmanHashSet:
59 - all keys must be fixed-size. It means that you cannot use \p std::string as a key for \p %FeldmanHashSet.
60 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>,
61 <a href="https://en.wikipedia.org/wiki/MurmurHash">MurmurHash</a>, <a href="https://en.wikipedia.org/wiki/CityHash">CityHash</a>
62 or its successor <a href="https://code.google.com/p/farmhash/">FarmHash</a> and so on, which
63 converts variable-length strings to fixed-length bit-strings, and use that hash as a key in \p %FeldmanHashSet.
64 - \p %FeldmanHashSet uses a perfect hashing. It means that if two different keys, for example, of type \p std::string,
65 have identical hash then you cannot insert both that keys in the set. \p %FeldmanHashSet does not maintain the key,
66 it maintains its fixed-size hash value.
68 The set supports @ref cds_intrusive_FeldmanHashSet_iterators "bidirectional thread-safe iterators".
71 - \p GC - safe memory reclamation schema. Can be \p gc::HP, \p gc::DHP or one of \ref cds_urcu_type "RCU type"
72 - \p T - a value type to be stored in the set
73 - \p Traits - type traits, the structure based on \p feldman_hashset::traits or result of \p feldman_hashset::make_traits metafunction.
74 \p Traits is the mandatory argument because it has one mandatory type - an @ref feldman_hashset::traits::hash_accessor "accessor"
75 to hash value of \p T. The set algorithm does not calculate that hash value.
77 There are several specializations of \p %FeldmanHashSet for each \p GC. You should include:
78 - <tt><cds/intrusive/feldman_hashset_hp.h></tt> for \p gc::HP garbage collector
79 - <tt><cds/intrusive/feldman_hashset_dhp.h></tt> for \p gc::DHP garbage collector
80 - <tt><cds/intrusive/feldman_hashset_rcu.h></tt> for \ref cds_intrusive_FeldmanHashSet_rcu "RCU type". RCU specialization
81 has a slightly different interface.
86 #ifdef CDS_DOXYGEN_INVOKED
87 ,typename Traits = feldman_hashset::traits
95 typedef GC gc; ///< Garbage collector
96 typedef T value_type; ///< type of value stored in the set
97 typedef Traits traits; ///< Traits template parameter, see \p feldman_hashset::traits
99 typedef typename traits::hash_accessor hash_accessor; ///< Hash accessor functor
100 static_assert(!std::is_same< hash_accessor, cds::opt::none >::value, "hash_accessor functor must be specified" );
102 /// Hash type deduced from \p hash_accessor return type
103 typedef typename std::decay<
104 typename std::remove_reference<
105 decltype( hash_accessor()( std::declval<T>()) )
108 //typedef typename std::result_of< hash_accessor( std::declval<T>()) >::type hash_type;
109 static_assert( !std::is_pointer<hash_type>::value, "hash_accessor should return a reference to hash value" );
111 typedef typename traits::disposer disposer; ///< data node disposer
113 # ifdef CDS_DOXYGEN_INVOKED
114 typedef implementation_defined hash_comparator ; ///< hash compare functor based on opt::compare and opt::less option setter
116 typedef typename cds::opt::details::make_comparator_from<
119 feldman_hashset::bitwise_compare< hash_type >
120 >::type hash_comparator;
123 typedef typename traits::item_counter item_counter; ///< Item counter type
124 typedef typename traits::node_allocator node_allocator; ///< Array node allocator
125 typedef typename traits::memory_model memory_model; ///< Memory model
126 typedef typename traits::back_off back_off; ///< Backoff strategy
127 typedef typename traits::stat stat; ///< Internal statistics type
129 typedef typename gc::template guarded_ptr< value_type > guarded_ptr; ///< Guarded pointer
131 /// Count of hazard pointers required
132 static CDS_CONSTEXPR size_t const c_nHazardPtrCount = 2;
134 /// Node marked poiter
135 typedef cds::details::marked_ptr< value_type, 3 > node_ptr;
136 /// Array node element
137 typedef atomics::atomic< node_ptr > atomic_node_ptr;
142 flag_array_converting = 1, ///< the cell is converting from data node to an array node
143 flag_array_node = 2 ///< the cell is a pointer to an array node
147 array_node * const pParent; ///< parent array node
148 size_t const idxParent; ///< index in parent array node
149 atomic_node_ptr nodes[1]; ///< node array
151 array_node( array_node * parent, size_t idx )
156 array_node() = delete;
157 array_node( array_node const&) = delete;
158 array_node( array_node&& ) = delete;
161 typedef cds::details::Allocator< array_node, node_allocator > cxx_array_node_allocator;
163 typedef feldman_hashset::details::hash_splitter< hash_type > hash_splitter;
170 friend class FeldmanHashSet;
173 array_node * m_pNode; ///< current array node
174 size_t m_idx; ///< current position in m_pNode
175 typename gc::Guard m_guard; ///< HP guard
176 FeldmanHashSet const* m_set; ///< Hash set
179 iterator_base() CDS_NOEXCEPT
185 iterator_base( iterator_base const& rhs ) CDS_NOEXCEPT
186 : m_pNode( rhs.m_pNode )
190 m_guard.copy( rhs.m_guard );
193 iterator_base& operator=(iterator_base const& rhs) CDS_NOEXCEPT
195 m_pNode = rhs.m_pNode;
198 m_guard.copy( rhs.m_guard );
202 iterator_base& operator++()
208 iterator_base& operator--()
219 bool operator ==(iterator_base const& rhs) const CDS_NOEXCEPT
221 return m_pNode == rhs.m_pNode && m_idx == rhs.m_idx && m_set == rhs.m_set;
224 bool operator !=(iterator_base const& rhs) const CDS_NOEXCEPT
226 return !( *this == rhs );
230 iterator_base( FeldmanHashSet const& set, array_node * pNode, size_t idx, bool )
236 iterator_base( FeldmanHashSet const& set, array_node * pNode, size_t idx )
244 value_type * pointer() const CDS_NOEXCEPT
246 return m_guard.template get<value_type>();
251 assert( m_set != nullptr );
252 assert( m_pNode != nullptr );
254 size_t const arrayNodeSize = m_set->array_node_size();
255 size_t const headSize = m_set->head_size();
256 array_node * pNode = m_pNode;
257 size_t idx = m_idx + 1;
258 size_t nodeSize = m_pNode->pParent? arrayNodeSize : headSize;
261 if ( idx < nodeSize ) {
262 node_ptr slot = pNode->nodes[idx].load( memory_model::memory_order_acquire );
263 if ( slot.bits() == flag_array_node ) {
264 // array node, go down the tree
265 assert( slot.ptr() != nullptr );
266 pNode = to_array( slot.ptr() );
268 nodeSize = arrayNodeSize;
270 else if ( slot.bits() == flag_array_converting ) {
271 // the slot is converting to array node right now - skip the node
277 if ( m_guard.protect( pNode->nodes[idx], [](node_ptr p) -> value_type * { return p.ptr(); }) == slot ) {
288 if ( pNode->pParent ) {
289 idx = pNode->idxParent + 1;
290 pNode = pNode->pParent;
291 nodeSize = pNode->pParent ? arrayNodeSize : headSize;
295 assert( pNode == m_set->m_Head );
296 assert( idx == headSize );
307 assert( m_set != nullptr );
308 assert( m_pNode != nullptr );
310 size_t const arrayNodeSize = m_set->array_node_size();
311 size_t const headSize = m_set->head_size();
312 size_t const endIdx = size_t(0) - 1;
314 array_node * pNode = m_pNode;
315 size_t idx = m_idx - 1;
316 size_t nodeSize = m_pNode->pParent? arrayNodeSize : headSize;
319 if ( idx != endIdx ) {
320 node_ptr slot = pNode->nodes[idx].load( memory_model::memory_order_acquire );
321 if ( slot.bits() == flag_array_node ) {
322 // array node, go down the tree
323 assert( slot.ptr() != nullptr );
324 pNode = to_array( slot.ptr() );
325 nodeSize = arrayNodeSize;
328 else if ( slot.bits() == flag_array_converting ) {
329 // the slot is converting to array node right now - skip the node
335 if ( m_guard.protect( pNode->nodes[idx], [](node_ptr p) -> value_type * { return p.ptr(); }) == slot ) {
346 if ( pNode->pParent ) {
347 idx = pNode->idxParent - 1;
348 pNode = pNode->pParent;
349 nodeSize = pNode->pParent ? arrayNodeSize : headSize;
353 assert( pNode == m_set->m_Head );
354 assert( idx == endIdx );
364 template <class Iterator>
365 Iterator init_begin() const
367 return Iterator( *this, m_Head, size_t(0) - 1 );
370 template <class Iterator>
371 Iterator init_end() const
373 return Iterator( *this, m_Head, head_size(), false );
376 template <class Iterator>
377 Iterator init_rbegin() const
379 return Iterator( *this, m_Head, head_size() );
382 template <class Iterator>
383 Iterator init_rend() const
385 return Iterator( *this, m_Head, size_t(0) - 1, false );
388 /// Bidirectional iterator class
389 template <bool IsConst>
390 class bidirectional_iterator: protected iterator_base
392 friend class FeldmanHashSet;
395 static CDS_CONSTEXPR bool const c_bConstantIterator = IsConst;
398 typedef typename std::conditional< IsConst, value_type const*, value_type*>::type value_ptr; ///< Value pointer
399 typedef typename std::conditional< IsConst, value_type const&, value_type&>::type value_ref; ///< Value reference
402 bidirectional_iterator() CDS_NOEXCEPT
405 bidirectional_iterator( bidirectional_iterator const& rhs ) CDS_NOEXCEPT
406 : iterator_base( rhs )
409 bidirectional_iterator& operator=(bidirectional_iterator const& rhs) CDS_NOEXCEPT
411 iterator_base::operator=( rhs );
415 bidirectional_iterator& operator++()
417 iterator_base::operator++();
421 bidirectional_iterator& operator--()
423 iterator_base::operator--();
427 value_ptr operator ->() const CDS_NOEXCEPT
429 return iterator_base::pointer();
432 value_ref operator *() const CDS_NOEXCEPT
434 value_ptr p = iterator_base::pointer();
441 iterator_base::release();
444 template <bool IsConst2>
445 bool operator ==(bidirectional_iterator<IsConst2> const& rhs) const CDS_NOEXCEPT
447 return iterator_base::operator==( rhs );
450 template <bool IsConst2>
451 bool operator !=(bidirectional_iterator<IsConst2> const& rhs) const CDS_NOEXCEPT
453 return !( *this == rhs );
457 bidirectional_iterator( FeldmanHashSet& set, array_node * pNode, size_t idx, bool )
458 : iterator_base( set, pNode, idx, false )
461 bidirectional_iterator( FeldmanHashSet& set, array_node * pNode, size_t idx )
462 : iterator_base( set, pNode, idx )
466 /// Reverse bidirectional iterator
467 template <bool IsConst>
468 class reverse_bidirectional_iterator : public iterator_base
470 friend class FeldmanHashSet;
473 typedef typename std::conditional< IsConst, value_type const*, value_type*>::type value_ptr; ///< Value pointer
474 typedef typename std::conditional< IsConst, value_type const&, value_type&>::type value_ref; ///< Value reference
477 reverse_bidirectional_iterator() CDS_NOEXCEPT
481 reverse_bidirectional_iterator( reverse_bidirectional_iterator const& rhs ) CDS_NOEXCEPT
482 : iterator_base( rhs )
485 reverse_bidirectional_iterator& operator=( reverse_bidirectional_iterator const& rhs) CDS_NOEXCEPT
487 iterator_base::operator=( rhs );
491 reverse_bidirectional_iterator& operator++()
493 iterator_base::operator--();
497 reverse_bidirectional_iterator& operator--()
499 iterator_base::operator++();
503 value_ptr operator ->() const CDS_NOEXCEPT
505 return iterator_base::pointer();
508 value_ref operator *() const CDS_NOEXCEPT
510 value_ptr p = iterator_base::pointer();
517 iterator_base::release();
520 template <bool IsConst2>
521 bool operator ==(reverse_bidirectional_iterator<IsConst2> const& rhs) const
523 return iterator_base::operator==( rhs );
526 template <bool IsConst2>
527 bool operator !=(reverse_bidirectional_iterator<IsConst2> const& rhs)
529 return !( *this == rhs );
533 reverse_bidirectional_iterator( FeldmanHashSet& set, array_node * pNode, size_t idx, bool )
534 : iterator_base( set, pNode, idx, false )
537 reverse_bidirectional_iterator( FeldmanHashSet& set, array_node * pNode, size_t idx )
538 : iterator_base( set, pNode, idx, false )
540 iterator_base::backward();
546 #ifdef CDS_DOXYGEN_INVOKED
547 typedef implementation_defined iterator; ///< @ref cds_intrusive_FeldmanHashSet_iterators "bidirectional iterator" type
548 typedef implementation_defined const_iterator; ///< @ref cds_intrusive_FeldmanHashSet_iterators "bidirectional const iterator" type
549 typedef implementation_defined reverse_iterator; ///< @ref cds_intrusive_FeldmanHashSet_iterators "bidirectional reverse iterator" type
550 typedef implementation_defined const_reverse_iterator; ///< @ref cds_intrusive_FeldmanHashSet_iterators "bidirectional reverse const iterator" type
552 typedef bidirectional_iterator<false> iterator;
553 typedef bidirectional_iterator<true> const_iterator;
554 typedef reverse_bidirectional_iterator<false> reverse_iterator;
555 typedef reverse_bidirectional_iterator<true> const_reverse_iterator;
560 feldman_hashset::details::metrics const m_Metrics; ///< Metrics
561 array_node * m_Head; ///< Head array
562 item_counter m_ItemCounter; ///< Item counter
563 stat m_Stat; ///< Internal statistics
567 /// Creates empty set
569 @param head_bits: 2<sup>head_bits</sup> specifies the size of head array, minimum is 4.
570 @param array_bits: 2<sup>array_bits</sup> specifies the size of array node, minimum is 2.
572 Equation for \p head_bits and \p array_bits:
574 sizeof(hash_type) * 8 == head_bits + N * array_bits
576 where \p N is multi-level array depth.
578 FeldmanHashSet( size_t head_bits = 8, size_t array_bits = 4 )
579 : m_Metrics( feldman_hashset::details::metrics::make( head_bits, array_bits, sizeof(hash_type)))
580 , m_Head( alloc_head_node())
583 /// Destructs the set and frees all data
587 free_array_node( m_Head );
592 The function inserts \p val in the set if it does not contain
593 an item with that hash.
595 Returns \p true if \p val is placed into the set, \p false otherwise.
597 bool insert( value_type& val )
599 return insert( val, [](value_type&) {} );
604 This function is intended for derived non-intrusive containers.
606 The function allows to split creating of new item into two part:
607 - create item with key only
608 - insert new item into the set
609 - if inserting is success, calls \p f functor to initialize \p val.
611 The functor signature is:
613 void func( value_type& val );
615 where \p val is the item inserted.
617 The user-defined functor is called only if the inserting is success.
619 @warning See \ref cds_intrusive_item_creating "insert item troubleshooting".
621 template <typename Func>
622 bool insert( value_type& val, Func f )
624 hash_type const& hash = hash_accessor()( val );
625 hash_splitter splitter( hash );
627 typename gc::Guard guard;
630 size_t nOffset = m_Metrics.head_node_size_log;
631 array_node * pArr = m_Head;
632 size_t nSlot = splitter.cut( m_Metrics.head_node_size_log );
633 assert( nSlot < m_Metrics.head_node_size );
637 node_ptr slot = pArr->nodes[nSlot].load( memory_model::memory_order_acquire );
638 if ( slot.bits() == flag_array_node ) {
639 // array node, go down the tree
640 assert( slot.ptr() != nullptr );
641 nSlot = splitter.cut( m_Metrics.array_node_size_log );
642 assert( nSlot < m_Metrics.array_node_size );
643 pArr = to_array( slot.ptr() );
644 nOffset += m_Metrics.array_node_size_log;
647 else if ( slot.bits() == flag_array_converting ) {
648 // the slot is converting to array node right now
650 m_Stat.onSlotConverting();
654 assert(slot.bits() == 0 );
656 // protect data node by hazard pointer
657 if ( guard.protect( pArr->nodes[nSlot], [](node_ptr p) -> value_type * { return p.ptr(); }) != slot ) {
658 // slot value has been changed - retry
659 m_Stat.onSlotChanged();
661 else if ( slot.ptr() ) {
662 if ( cmp( hash, hash_accessor()( *slot.ptr() )) == 0 ) {
663 // the item with that hash value already exists
664 m_Stat.onInsertFailed();
668 // the slot must be expanded
669 expand_slot( pArr, nSlot, slot, nOffset );
672 // the slot is empty, try to insert data node
674 if ( pArr->nodes[nSlot].compare_exchange_strong( pNull, node_ptr( &val ), memory_model::memory_order_release, atomics::memory_order_relaxed ))
676 // the new data node has been inserted
679 m_Stat.onInsertSuccess();
680 m_Stat.height( nHeight );
684 // insert failed - slot has been changed by another thread
686 m_Stat.onInsertRetry();
694 Performs inserting or updating the item with hash value equal to \p val.
695 - If hash value is found then existing item is replaced with \p val, old item is disposed
696 with \p Traits::disposer. Note that the disposer is called by \p GC asynchronously.
697 The function returns <tt> std::pair<true, false> </tt>
698 - If hash value is not found and \p bInsert is \p true then \p val is inserted,
699 the function returns <tt> std::pair<true, true> </tt>
700 - If hash value is not found and \p bInsert is \p false then the set is unchanged,
701 the function returns <tt> std::pair<false, false> </tt>
703 Returns <tt> std::pair<bool, bool> </tt> where \p first is \p true if operation is successfull
704 (i.e. the item has been inserted or updated),
705 \p second is \p true if new item has been added or \p false if the set contains that hash.
707 std::pair<bool, bool> update( value_type& val, bool bInsert = true )
709 return do_update(val, [](value_type&, value_type *) {}, bInsert );
712 /// Unlinks the item \p val from the set
714 The function searches the item \p val in the set and unlink it
715 if it is found and its address is equal to <tt>&val</tt>.
717 The function returns \p true if success and \p false otherwise.
719 bool unlink( value_type const& val )
721 typename gc::Guard guard;
722 auto pred = [&val](value_type const& item) -> bool { return &item == &val; };
723 value_type * p = do_erase( hash_accessor()( val ), guard, std::ref( pred ));
727 /// Deletes the item from the set
729 The function searches \p hash in the set,
730 unlinks the item found, and returns \p true.
731 If that item is not found the function returns \p false.
733 The \ref disposer specified in \p Traits is called by garbage collector \p GC asynchronously.
735 bool erase( hash_type const& hash )
737 return erase(hash, [](value_type const&) {} );
740 /// Deletes the item from the set
742 The function searches \p hash in the set,
743 call \p f functor with item found, and unlinks it from the set.
744 The \ref disposer specified in \p Traits is called
745 by garbage collector \p GC asynchronously.
747 The \p Func interface is
750 void operator()( value_type& item );
754 If \p hash is not found the function returns \p false.
756 template <typename Func>
757 bool erase( hash_type const& hash, Func f )
759 typename gc::Guard guard;
760 value_type * p = do_erase( hash, guard, []( value_type const&) -> bool {return true; } );
762 // p is guarded by HP
770 /// Deletes the item pointed by iterator \p iter
772 Returns \p true if the operation is successful, \p false otherwise.
774 The function does not invalidate the iterator, it remains valid and can be used for further traversing.
776 bool erase_at( iterator const& iter )
778 return do_erase_at( iter );
781 bool erase_at( reverse_iterator const& iter )
783 return do_erase_at( iter );
787 /// Extracts the item with specified \p hash
789 The function searches \p hash in the set,
790 unlinks it from the set, and returns an guarded pointer to the item extracted.
791 If \p hash is not found the function returns an empty guarded pointer.
793 The \p disposer specified in \p Traits class' template parameter is called automatically
794 by garbage collector \p GC when returned \ref guarded_ptr object to be destroyed or released.
795 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
799 typedef cds::intrusive::FeldmanHashSet< your_template_args > my_set;
803 my_set::guarded_ptr gp( theSet.extract( 5 ));
808 // Destructor of gp releases internal HP guard
812 guarded_ptr extract( hash_type const& hash )
816 typename gc::Guard guard;
817 value_type * p = do_erase( hash, guard, []( value_type const&) -> bool {return true;} );
819 // p is guarded by HP
826 /// Finds an item by it's \p hash
828 The function searches the item by \p hash and calls the functor \p f for item found.
829 The interface of \p Func functor is:
832 void operator()( value_type& item );
835 where \p item is the item found.
837 The functor may change non-key fields of \p item. Note that the functor is only guarantee
838 that \p item cannot be disposed during the functor is executing.
839 The functor does not serialize simultaneous access to the set's \p item. If such access is
840 possible you must provide your own synchronization schema on item level to prevent unsafe item modifications.
842 The function returns \p true if \p hash is found, \p false otherwise.
844 template <typename Func>
845 bool find( hash_type const& hash, Func f )
847 typename gc::Guard guard;
848 value_type * p = search( hash, guard );
850 // p is guarded by HP
858 /// Checks whether the set contains \p hash
860 The function searches the item by its \p hash
861 and returns \p true if it is found, or \p false otherwise.
863 bool contains( hash_type const& hash )
865 return find( hash, [](value_type&) {} );
868 /// Finds an item by it's \p hash and returns the item found
870 The function searches the item by its \p hash
871 and returns the guarded pointer to the item found.
872 If \p hash is not found the function returns an empty \p guarded_ptr.
874 @note Each \p guarded_ptr object uses one GC's guard which can be limited resource.
878 typedef cds::intrusive::FeldmanHashSet< your_template_params > my_set;
882 my_set::guarded_ptr gp( theSet.get( 5 ));
883 if ( theSet.get( 5 )) {
887 // Destructor of guarded_ptr releases internal HP guard
891 guarded_ptr get( hash_type const& hash )
895 typename gc::Guard guard;
896 gp.reset( search( hash, guard ));
901 /// Clears the set (non-atomic)
903 The function unlink all data node from the set.
904 The function is not atomic but is thread-safe.
905 After \p %clear() the set may not be empty because another threads may insert items.
907 For each item the \p disposer is called after unlinking.
911 clear_array( m_Head, head_size() );
914 /// Checks if the set is empty
916 Emptiness is checked by item counting: if item count is zero then the set is empty.
917 Thus, the correct item counting feature is an important part of the set implementation.
924 /// Returns item count in the set
927 return m_ItemCounter;
930 /// Returns const reference to internal statistics
931 stat const& statistics() const
936 /// Returns the size of head node
937 size_t head_size() const
939 return m_Metrics.head_node_size;
942 /// Returns the size of the array node
943 size_t array_node_size() const
945 return m_Metrics.array_node_size;
949 ///@name Thread-safe iterators
950 /** @anchor cds_intrusive_FeldmanHashSet_iterators
951 The set supports thread-safe iterators: you may iterate over the set in multi-threaded environment.
952 It is guaranteed that the iterators will remain valid even if another thread deletes the node the iterator points to:
953 Hazard Pointer embedded into the iterator object protects the node from physical reclamation.
955 @note Since the iterator object contains hazard pointer that is a thread-local resource,
956 the iterator should not be passed to another thread.
958 Each iterator object supports the common interface:
959 - dereference operators:
961 value_type [const] * operator ->() noexcept
962 value_type [const] & operator *() noexcept
964 - pre-increment and pre-decrement. Post-operators is not supported
965 - equality operators <tt>==</tt> and <tt>!=</tt>.
966 Iterators are equal iff they point to the same cell of the same array node.
967 Note that for two iterators \p it1 and \p it2, the conditon <tt> it1 == it2 </tt>
968 does not entail <tt> &(*it1) == &(*it2) </tt>: welcome to concurrent containers
969 - helper member function \p release() that clears internal hazard pointer.
970 After \p release() the iterator points to \p nullptr but it still remain valid: further iterating is possible.
972 During iteration you may safely erase any item from the set;
973 @ref erase_at() function call doesn't invalidate any iterator.
974 If some iterator points to the item to be erased, that item is not deleted immediately
975 but only after that iterator will be advanced forward or backward.
977 @note It is possible the item can be iterated more that once, for example, if an iterator points to the item
978 in array node that is being splitted.
982 /// Returns an iterator to the beginning of the set
985 return iterator( *this, m_Head, size_t(0) - 1 );
988 /// Returns an const iterator to the beginning of the set
989 const_iterator begin() const
991 return const_iterator( *this, m_Head, size_t(0) - 1 );
994 /// Returns an const iterator to the beginning of the set
995 const_iterator cbegin()
997 return const_iterator( *this, m_Head, size_t(0) - 1 );
1000 /// 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.
1003 return iterator( *this, m_Head, head_size(), false );
1006 /// 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.
1007 const_iterator end() const
1009 return const_iterator( *this, m_Head, head_size(), false );
1012 /// 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.
1013 const_iterator cend()
1015 return const_iterator( *this, m_Head, head_size(), false );
1018 /// Returns a reverse iterator to the first element of the reversed set
1019 reverse_iterator rbegin()
1021 return reverse_iterator( *this, m_Head, head_size() );
1024 /// Returns a const reverse iterator to the first element of the reversed set
1025 const_reverse_iterator rbegin() const
1027 return const_reverse_iterator( *this, m_Head, head_size() );
1030 /// Returns a const reverse iterator to the first element of the reversed set
1031 const_reverse_iterator crbegin()
1033 return const_reverse_iterator( *this, m_Head, head_size() );
1036 /// Returns a 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 reverse_iterator rend()
1043 return reverse_iterator( *this, m_Head, size_t(0) - 1, false );
1046 /// Returns a const reverse iterator to the element following the last element of the reversed set
1048 It corresponds to the element preceding the first element of the non-reversed container.
1049 This element acts as a placeholder, attempting to access it results in undefined behavior.
1051 const_reverse_iterator rend() const
1053 return const_reverse_iterator( *this, m_Head, size_t(0) - 1, false );
1056 /// Returns a const reverse iterator to the element following the last element of the reversed set
1058 It corresponds to the element preceding the first element of the non-reversed container.
1059 This element acts as a placeholder, attempting to access it results in undefined behavior.
1061 const_reverse_iterator crend()
1063 return const_reverse_iterator( *this, m_Head, size_t(0) - 1, false );
1070 array_node * alloc_head_node() const
1072 return alloc_array_node( head_size(), nullptr, 0 );
1075 array_node * alloc_array_node( array_node * pParent, size_t idxParent ) const
1077 return alloc_array_node( array_node_size(), pParent, idxParent );
1080 static array_node * alloc_array_node( size_t nSize, array_node * pParent, size_t idxParent )
1082 array_node * pNode = cxx_array_node_allocator().NewBlock( sizeof(array_node) + sizeof(atomic_node_ptr) * (nSize - 1), pParent, idxParent );
1083 new ( pNode->nodes ) atomic_node_ptr[ nSize ];
1087 static void free_array_node( array_node * parr )
1089 cxx_array_node_allocator().Delete( parr );
1094 // The function is not thread-safe. For use in dtor only
1098 // Destroy all array nodes
1099 destroy_array_nodes( m_Head, head_size());
1102 void destroy_array_nodes( array_node * pArr, size_t nSize )
1104 for ( atomic_node_ptr * p = pArr->nodes, *pLast = pArr->nodes + nSize; p != pLast; ++p ) {
1105 node_ptr slot = p->load( memory_model::memory_order_acquire );
1106 if ( slot.bits() == flag_array_node ) {
1107 destroy_array_nodes(to_array(slot.ptr()), array_node_size());
1108 free_array_node( to_array(slot.ptr()));
1109 p->store(node_ptr(), memory_model::memory_order_relaxed );
1114 void clear_array( array_node * pArrNode, size_t nSize )
1119 for ( atomic_node_ptr * pArr = pArrNode->nodes, *pLast = pArr + nSize; pArr != pLast; ++pArr ) {
1121 node_ptr slot = pArr->load( memory_model::memory_order_acquire );
1122 if ( slot.bits() == flag_array_node ) {
1123 // array node, go down the tree
1124 assert( slot.ptr() != nullptr );
1125 clear_array( to_array( slot.ptr()), array_node_size() );
1128 else if ( slot.bits() == flag_array_converting ) {
1129 // the slot is converting to array node right now
1130 while ( (slot = pArr->load(memory_model::memory_order_acquire)).bits() == flag_array_converting ) {
1132 m_Stat.onSlotConverting();
1136 assert( slot.ptr() != nullptr );
1137 assert(slot.bits() == flag_array_node );
1138 clear_array( to_array( slot.ptr()), array_node_size() );
1143 if ( pArr->compare_exchange_strong( slot, node_ptr(), memory_model::memory_order_acquire, atomics::memory_order_relaxed )) {
1145 gc::template retire<disposer>( slot.ptr() );
1147 m_Stat.onEraseSuccess();
1160 converter( value_type * p )
1164 converter( array_node * p )
1169 static array_node * to_array( value_type * p )
1171 return converter( p ).pArr;
1173 static value_type * to_node( array_node * p )
1175 return converter( p ).pData;
1178 bool expand_slot( array_node * pParent, size_t idxParent, node_ptr current, size_t nOffset )
1180 assert( current.bits() == 0 );
1181 assert( current.ptr() );
1183 size_t idx = hash_splitter(hash_accessor()(*current.ptr()), nOffset).cut( m_Metrics.array_node_size_log );
1184 array_node * pArr = alloc_array_node( pParent, idxParent );
1186 node_ptr cur(current.ptr());
1187 atomic_node_ptr& slot = pParent->nodes[idxParent];
1188 if ( !slot.compare_exchange_strong( cur, cur | flag_array_converting, memory_model::memory_order_release, atomics::memory_order_relaxed ))
1190 m_Stat.onExpandNodeFailed();
1191 free_array_node( pArr );
1195 pArr->nodes[idx].store( current, memory_model::memory_order_release );
1197 cur = cur | flag_array_converting;
1199 slot.compare_exchange_strong( cur, node_ptr( to_node( pArr ), flag_array_node ), memory_model::memory_order_release, atomics::memory_order_relaxed )
1202 m_Stat.onExpandNodeSuccess();
1203 m_Stat.onArrayNodeCreated();
1210 value_type * search( hash_type const& hash, typename gc::Guard& guard )
1212 hash_splitter splitter( hash );
1213 hash_comparator cmp;
1216 array_node * pArr = m_Head;
1217 size_t nSlot = splitter.cut( m_Metrics.head_node_size_log );
1218 assert( nSlot < m_Metrics.head_node_size );
1221 node_ptr slot = pArr->nodes[nSlot].load( memory_model::memory_order_acquire );
1222 if ( slot.bits() == flag_array_node ) {
1223 // array node, go down the tree
1224 assert( slot.ptr() != nullptr );
1225 nSlot = splitter.cut( m_Metrics.array_node_size_log );
1226 assert( nSlot < m_Metrics.array_node_size );
1227 pArr = to_array( slot.ptr() );
1229 else if ( slot.bits() == flag_array_converting ) {
1230 // the slot is converting to array node right now
1232 m_Stat.onSlotConverting();
1236 assert(slot.bits() == 0 );
1238 // protect data node by hazard pointer
1239 if ( guard.protect( pArr->nodes[nSlot], [](node_ptr p) -> value_type * { return p.ptr(); }) != slot ) {
1240 // slot value has been changed - retry
1241 m_Stat.onSlotChanged();
1243 else if ( slot.ptr() && cmp( hash, hash_accessor()( *slot.ptr() )) == 0 ) {
1245 m_Stat.onFindSuccess();
1248 m_Stat.onFindFailed();
1254 template <typename Predicate>
1255 value_type * do_erase( hash_type const& hash, typename gc::Guard& guard, Predicate pred )
1257 hash_splitter splitter( hash );
1258 hash_comparator cmp;
1261 array_node * pArr = m_Head;
1262 size_t nSlot = splitter.cut( m_Metrics.head_node_size_log );
1263 assert( nSlot < m_Metrics.head_node_size );
1266 node_ptr slot = pArr->nodes[nSlot].load( memory_model::memory_order_acquire );
1267 if ( slot.bits() == flag_array_node ) {
1268 // array node, go down the tree
1269 assert( slot.ptr() != nullptr );
1270 nSlot = splitter.cut( m_Metrics.array_node_size_log );
1271 assert( nSlot < m_Metrics.array_node_size );
1272 pArr = to_array( slot.ptr() );
1274 else if ( slot.bits() == flag_array_converting ) {
1275 // the slot is converting to array node right now
1277 m_Stat.onSlotConverting();
1281 assert(slot.bits() == 0 );
1283 // protect data node by hazard pointer
1284 if ( guard.protect( pArr->nodes[nSlot], [](node_ptr p) -> value_type * { return p.ptr(); }) != slot ) {
1285 // slot value has been changed - retry
1286 m_Stat.onSlotChanged();
1288 else if ( slot.ptr() ) {
1289 if ( cmp( hash, hash_accessor()( *slot.ptr() )) == 0 && pred( *slot.ptr() )) {
1290 // item found - replace it with nullptr
1291 if ( pArr->nodes[nSlot].compare_exchange_strong(slot, node_ptr(nullptr), memory_model::memory_order_acquire, atomics::memory_order_relaxed) ) {
1292 // slot is guarded by HP
1293 gc::template retire<disposer>( slot.ptr() );
1295 m_Stat.onEraseSuccess();
1299 m_Stat.onEraseRetry();
1302 m_Stat.onEraseFailed();
1306 // the slot is empty
1307 m_Stat.onEraseFailed();
1314 bool do_erase_at( iterator_base const& iter )
1316 if ( iter.m_set != this )
1318 if ( iter.m_pNode == m_Head && iter.m_idx >= head_size())
1320 if ( iter.m_idx >= array_node_size() )
1324 node_ptr slot = iter.m_pNode->nodes[iter.m_idx].load( memory_model::memory_order_acquire );
1325 if ( slot.bits() == 0 && slot.ptr() == iter.pointer() ) {
1326 if ( iter.m_pNode->nodes[iter.m_idx].compare_exchange_strong(slot, node_ptr(nullptr), memory_model::memory_order_acquire, atomics::memory_order_relaxed) ) {
1327 // the item is guarded by iterator, so we may retire it safely
1328 gc::template retire<disposer>( slot.ptr() );
1330 m_Stat.onEraseSuccess();
1339 template <typename Func>
1340 std::pair<bool, bool> do_update( value_type& val, Func f, bool bInsert = true )
1342 hash_type const& hash = hash_accessor()( val );
1343 hash_splitter splitter( hash );
1344 hash_comparator cmp;
1345 typename gc::template GuardArray<2> guards;
1348 array_node * pArr = m_Head;
1349 size_t nSlot = splitter.cut( m_Metrics.head_node_size_log );
1350 assert( nSlot < m_Metrics.head_node_size );
1351 size_t nOffset = m_Metrics.head_node_size_log;
1354 guards.assign( 1, &val );
1357 node_ptr slot = pArr->nodes[nSlot].load( memory_model::memory_order_acquire );
1358 if ( slot.bits() == flag_array_node ) {
1359 // array node, go down the tree
1360 assert( slot.ptr() != nullptr );
1361 nSlot = splitter.cut( m_Metrics.array_node_size_log );
1362 assert( nSlot < m_Metrics.array_node_size );
1363 pArr = to_array( slot.ptr() );
1364 nOffset += m_Metrics.array_node_size_log;
1367 else if ( slot.bits() == flag_array_converting ) {
1368 // the slot is converting to array node right now
1370 m_Stat.onSlotConverting();
1374 assert(slot.bits() == 0 );
1376 // protect data node by hazard pointer
1377 if ( guards.protect( 0, pArr->nodes[nSlot], [](node_ptr p) -> value_type * { return p.ptr(); }) != slot ) {
1378 // slot value has been changed - retry
1379 m_Stat.onSlotChanged();
1381 else if ( slot.ptr() ) {
1382 if ( cmp( hash, hash_accessor()( *slot.ptr() )) == 0 ) {
1383 // the item with that hash value already exists
1384 // Replace it with val
1385 if ( slot.ptr() == &val ) {
1386 m_Stat.onUpdateExisting();
1387 return std::make_pair( true, false );
1390 if ( pArr->nodes[nSlot].compare_exchange_strong( slot, node_ptr( &val ), memory_model::memory_order_release, atomics::memory_order_relaxed )) {
1391 // slot can be disposed
1392 f( val, slot.ptr() );
1393 gc::template retire<disposer>( slot.ptr() );
1394 m_Stat.onUpdateExisting();
1395 return std::make_pair( true, false );
1398 m_Stat.onUpdateRetry();
1402 // the slot must be expanded
1403 expand_slot( pArr, nSlot, slot, nOffset );
1406 // the slot is empty, try to insert data node
1409 if ( pArr->nodes[nSlot].compare_exchange_strong( pNull, node_ptr( &val ), memory_model::memory_order_release, atomics::memory_order_relaxed ))
1411 // the new data node has been inserted
1414 m_Stat.onUpdateNew();
1415 m_Stat.height( nHeight );
1416 return std::make_pair( true, true );
1420 m_Stat.onUpdateFailed();
1421 return std::make_pair( false, false );
1424 // insert failed - slot has been changed by another thread
1426 m_Stat.onUpdateRetry();
1433 }} // namespace cds::intrusive
1438 template <class GC, typename T, typename Traits>
1439 struct iterator_traits< typename cds::intrusive::FeldmanHashSet< GC, T, Traits >::iterator >
1441 typedef typename cds::intrusive::FeldmanHashSet< GC, T, Traits >::iterator iterator_class;
1443 // difference_type is not applicable for that iterator
1444 // typedef ??? difference_type
1445 typedef T value_type;
1446 typedef typename iterator_class::value_ptr pointer;
1447 typedef typename iterator_class::value_ref reference;
1448 typedef bidirectional_iterator_tag iterator_category;
1451 template <class GC, typename T, typename Traits>
1452 struct iterator_traits< typename cds::intrusive::FeldmanHashSet< GC, T, Traits >::const_iterator >
1454 typedef typename cds::intrusive::FeldmanHashSet< GC, T, Traits >::const_iterator iterator_class;
1456 // difference_type is not applicable for that iterator
1457 // typedef ??? difference_type
1458 typedef T value_type;
1459 typedef typename iterator_class::value_ptr pointer;
1460 typedef typename iterator_class::value_ref reference;
1461 typedef bidirectional_iterator_tag iterator_category;
1467 #endif // #ifndef CDSLIB_INTRUSIVE_IMPL_FELDMAN_HASHSET_H