3 #ifndef CDSLIB_CONTAINER_FELDMAN_HASHSET_RCU_H
4 #define CDSLIB_CONTAINER_FELDMAN_HASHSET_RCU_H
6 #include <cds/intrusive/feldman_hashset_rcu.h>
7 #include <cds/container/details/feldman_hashset_base.h>
9 namespace cds { namespace container {
11 /// Hash set based on multi-level array, \ref cds_urcu_desc "RCU" specialization
12 /** @ingroup cds_nonintrusive_set
13 @anchor cds_container_FeldmanHashSet_rcu
16 - [2013] Steven Feldman, Pierre LaBorde, Damian Dechev "Concurrent Multi-level Arrays:
17 Wait-free Extensible Hash Maps"
19 See algorithm short description @ref cds_intrusive_FeldmanHashSet_hp "here"
21 @note Two important things you should keep in mind when you're using \p %FeldmanHashSet:
22 - all keys must be fixed-size. It means that you cannot use \p std::string as a key for \p %FeldmanHashSet.
23 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>,
24 <a href="https://en.wikipedia.org/wiki/MurmurHash">MurmurHash</a>, <a href="https://en.wikipedia.org/wiki/CityHash">CityHash</a>
25 or its successor <a href="https://code.google.com/p/farmhash/">FarmHash</a> and so on, which
26 converts variable-length strings to fixed-length bit-strings, and use that hash as a key in \p %FeldmanHashSet.
27 - \p %FeldmanHashSet uses a perfect hashing. It means that if two different keys, for example, of type \p std::string,
28 have identical hash then you cannot insert both that keys in the set. \p %FeldmanHashSet does not maintain the key,
29 it maintains its fixed-size hash value.
31 The set supports @ref cds_container_FeldmanHashSet_iterators "bidirectional thread-safe iterators".
34 - \p RCU - one of \ref cds_urcu_gc "RCU type"
35 - \p T - a value type to be stored in the set
36 - \p Traits - type traits, the structure based on \p feldman_hashset::traits or result of \p feldman_hashset::make_traits metafunction.
37 \p Traits is the mandatory argument because it has one mandatory type - an @ref feldman_hashset::traits::hash_accessor "accessor"
38 to hash value of \p T. The set algorithm does not calculate that hash value.
40 @note Before including <tt><cds/intrusive/feldman_hashset_rcu.h></tt> you should include appropriate RCU header file,
41 see \ref cds_urcu_gc "RCU type" for list of existing RCU class and corresponding header files.
43 The set supports @ref cds_container_FeldmanHashSet_rcu_iterators "bidirectional thread-safe iterators"
44 with some restrictions.
49 #ifdef CDS_DOXYGEN_INVOKED
50 , class Traits = feldman_hashset::traits
55 class FeldmanHashSet< cds::urcu::gc< RCU >, T, Traits >
56 #ifdef CDS_DOXYGEN_INVOKED
57 : protected cds::intrusive::FeldmanHashSet< cds::urcu::gc< RCU >, T, Traits >
59 : protected cds::container::details::make_feldman_hashset< cds::urcu::gc< RCU >, T, Traits >::type
63 typedef cds::container::details::make_feldman_hashset< cds::urcu::gc< RCU >, T, Traits > maker;
64 typedef typename maker::type base_class;
68 typedef cds::urcu::gc< RCU > gc; ///< RCU garbage collector
69 typedef T value_type; ///< type of value stored in the set
70 typedef Traits traits; ///< Traits template parameter, see \p feldman_hashset::traits
72 typedef typename base_class::hash_accessor hash_accessor; ///< Hash accessor functor
73 typedef typename base_class::hash_type hash_type; ///< Hash type deduced from \p hash_accessor return type
74 typedef typename base_class::hash_comparator hash_comparator; ///< hash compare functor based on \p opt::compare and \p opt::less option setter
76 typedef typename traits::item_counter item_counter; ///< Item counter type
77 typedef typename traits::allocator allocator; ///< Element allocator
78 typedef typename traits::node_allocator node_allocator; ///< Array node allocator
79 typedef typename traits::memory_model memory_model; ///< Memory model
80 typedef typename traits::back_off back_off; ///< Backoff strategy
81 typedef typename traits::stat stat; ///< Internal statistics type
82 typedef typename traits::rcu_check_deadlock rcu_check_deadlock; ///< Deadlock checking policy
83 typedef typename gc::scoped_lock rcu_lock; ///< RCU scoped lock
84 static CDS_CONSTEXPR const bool c_bExtractLockExternal = false; ///< Group of \p extract_xxx functions does not require external locking
85 typedef typename base_class::exempt_ptr exempt_ptr; ///< pointer to extracted node
87 typedef typename base_class::iterator iterator; ///< @ref cds_container_FeldmanHashSet_rcu_iterators "bidirectional iterator" type
88 typedef typename base_class::const_iterator const_iterator; ///< @ref cds_container_FeldmanHashSet_rcu_iterators "bidirectional const iterator" type
89 typedef typename base_class::reverse_iterator reverse_iterator; ///< @ref cds_container_FeldmanHashSet_rcu_iterators "bidirectional reverse iterator" type
90 typedef typename base_class::const_reverse_iterator const_reverse_iterator; ///< @ref cds_container_FeldmanHashSet_rcu_iterators "bidirectional reverse const iterator" type
94 typedef typename maker::cxx_node_allocator cxx_node_allocator;
95 typedef std::unique_ptr< value_type, typename maker::node_disposer > scoped_node_ptr;
101 @param head_bits: 2<sup>head_bits</sup> specifies the size of head array, minimum is 4.
102 @param array_bits: 2<sup>array_bits</sup> specifies the size of array node, minimum is 2.
104 Equation for \p head_bits and \p array_bits:
106 sizeof(hash_type) * 8 == head_bits + N * array_bits
108 where \p N is multi-level array depth.
110 FeldmanHashSet( size_t head_bits = 8, size_t array_bits = 4 )
111 : base_class( head_bits, array_bits )
114 /// Destructs the set and frees all data
118 /// Inserts new element
120 The function creates an element with copy of \p val value and then inserts it into the set.
122 The type \p Q should contain as minimum the complete hash for the element.
123 The object of \ref value_type should be constructible from a value of type \p Q.
124 In trivial case, \p Q is equal to \ref value_type.
126 Returns \p true if \p val is inserted into the set, \p false otherwise.
128 The function locks RCU internally.
130 template <typename Q>
131 bool insert( Q const& val )
133 scoped_node_ptr sp( cxx_node_allocator().New( val ));
134 if ( base_class::insert( *sp )) {
141 /// Inserts new element
143 The function allows to split creating of new item into two part:
144 - create item with key only
145 - insert new item into the set
146 - if inserting is success, calls \p f functor to initialize value-fields of \p val.
148 The functor signature is:
150 void func( value_type& val );
152 where \p val is the item inserted. User-defined functor \p f should guarantee that during changing
153 \p val no any other changes could be made on this set's item by concurrent threads.
154 The user-defined functor is called only if the inserting is success.
156 The function locks RCU internally.
158 template <typename Q, typename Func>
159 bool insert( Q const& val, Func f )
161 scoped_node_ptr sp( cxx_node_allocator().New( val ));
162 if ( base_class::insert( *sp, f )) {
169 /// Updates the element
171 The operation performs inserting or replacing with lock-free manner.
173 If the \p val key not found in the set, then the new item created from \p val
174 will be inserted into the set iff \p bInsert is \p true.
175 Otherwise, if \p val is found, it is replaced with new item created from \p val
176 and previous item is disposed.
177 In both cases \p func functor is called.
179 The functor \p Func signature:
182 void operator()( value_type& cur, value_type * prev );
186 - \p cur - current element
187 - \p prev - pointer to previous element with such hash. \p prev is \p nullptr
188 if \p cur was just inserted.
190 The functor may change non-key fields of the \p item; however, \p func must guarantee
191 that during changing no any other modifications could be made on this item by concurrent threads.
193 Returns <tt> std::pair<bool, bool> </tt> where \p first is \p true if operation is successfull,
194 i.e. the item has been inserted or updated,
195 \p second is \p true if the new item has been added or \p false if the item with key equal to \p val
198 template <typename Q, typename Func>
199 std::pair<bool, bool> update( Q const& val, Func func, bool bInsert = true )
201 scoped_node_ptr sp( cxx_node_allocator().New( val ));
202 std::pair<bool, bool> bRes = base_class::do_update( *sp, func, bInsert );
208 /// Inserts data of type \p value_type created in-place from <tt>std::forward<Args>(args)...</tt>
210 Returns \p true if inserting successful, \p false otherwise.
212 template <typename... Args>
213 bool emplace( Args&&... args )
215 scoped_node_ptr sp( cxx_node_allocator().New( std::forward<Args>(args)... ));
216 if ( base_class::insert( *sp )) {
223 /// Deletes the item from the set
225 The function searches \p hash in the set,
226 deletes the item found, and returns \p true.
227 If that item is not found the function returns \p false.
229 RCU should not be locked. The function locks RCU internally.
231 bool erase( hash_type const& hash )
233 return base_class::erase( hash );
236 /// Deletes the item from the set
238 The function searches \p hash in the set,
239 call \p f functor with item found, and deltes the element from the set.
241 The \p Func interface is
244 void operator()( value_type& item );
248 If \p hash is not found the function returns \p false.
250 RCU should not be locked. The function locks RCU internally.
252 template <typename Func>
253 bool erase( hash_type const& hash, Func f )
255 return base_class::erase( hash, f );
258 /// Extracts the item with specified \p hash
260 The function searches \p hash in the set,
261 unlinks it from the set, and returns \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to the item found.
262 If the item with key equal to \p key is not found the function returns an empty \p exempt_ptr.
264 RCU \p synchronize method can be called. RCU should NOT be locked.
265 The function does not call the disposer for the item found.
266 The disposer will be implicitly invoked when the returned object is destroyed or when
267 its \p release() member function is called.
270 typedef cds::container::FeldmanHashSet< cds::urcu::gc< cds::urcu::general_buffered<> >, foo, my_traits > set_type;
274 typename set_type::exempt_ptr ep( theSet.extract( 5 ));
279 // Dispose returned item.
284 exempt_ptr extract( hash_type const& hash )
286 return base_class::extract( hash );
289 /// Finds an item by it's \p hash
291 The function searches the item by \p hash and calls the functor \p f for item found.
292 The interface of \p Func functor is:
295 void operator()( value_type& item );
298 where \p item is the item found.
300 The functor may change non-key fields of \p item. Note that the functor is only guarantee
301 that \p item cannot be disposed during the functor is executing.
302 The functor does not serialize simultaneous access to the set's \p item. If such access is
303 possible you must provide your own synchronization schema on item level to prevent unsafe item modifications.
305 The function returns \p true if \p hash is found, \p false otherwise.
307 template <typename Func>
308 bool find( hash_type const& hash, Func f )
310 return base_class::find( hash, f );
313 /// Checks whether the set contains \p hash
315 The function searches the item by its \p hash
316 and returns \p true if it is found, or \p false otherwise.
318 bool contains( hash_type const& hash )
320 return base_class::contains( hash );
323 /// Finds an item by it's \p hash and returns the item found
325 The function searches the item by its \p hash
326 and returns the pointer to the item found.
327 If \p hash is not found the function returns \p nullptr.
329 RCU should be locked before the function invocation.
330 Returned pointer is valid only while RCU is locked.
334 typedef cds::container::FeldmanHashSet< your_template_params > my_set;
341 foo * p = theSet.get( 5 );
349 value_type * get( hash_type const& hash )
351 return base_class::get( hash );
354 /// Clears the set (non-atomic)
356 The function unlink all data node from the set.
357 The function is not atomic but is thread-safe.
358 After \p %clear() the set may not be empty because another threads may insert items.
365 /// Checks if the set is empty
367 Emptiness is checked by item counting: if item count is zero then the set is empty.
368 Thus, the correct item counting feature is an important part of the set implementation.
372 return base_class::empty();
375 /// Returns item count in the set
378 return base_class::size();
381 /// Returns const reference to internal statistics
382 stat const& statistics() const
384 return base_class::statistics();
387 /// Returns the size of head node
388 size_t head_size() const
390 return base_class::head_size();
393 /// Returns the size of the array node
394 size_t array_node_size() const
396 return base_class::array_node_size();
399 /// Collects tree level statistics into \p stat
400 /** @copydetails cds::intrusive::FeldmanHashSet::get_level_statistics
402 void get_level_statistics(std::vector< feldman_hashset::level_statistics>& stat) const
404 base_class::get_level_statistics(stat);
408 ///@name Thread-safe iterators
409 /** @anchor cds_container_FeldmanHashSet_rcu_iterators
410 The set supports thread-safe iterators: you may iterate over the set in multi-threaded environment
411 under explicit RCU lock.
412 RCU lock requirement means that inserting or searching is allowed but you must not erase the items from the set
413 since erasing under RCU lock can lead to a deadlock. However, another thread can call \p erase() safely
414 while your thread is iterating.
416 A typical example is:
421 uint32_t payload; // only for example
423 struct set_traits: cds::container::feldman_hashset::traits
425 struct hash_accessor {
426 uint32_t operator()( foo const& src ) const
433 typedef cds::urcu::gc< cds::urcu::general_buffered<>> rcu;
434 typedef cds::container::FeldmanHashSet< rcu, foo, set_traits > set_type;
440 // iterate over the set
443 typename set_type::rcu_lock l; // scoped RCU lock
446 for ( auto i = s.begin(); i != s.end(); ++i ) {
447 // deal with i. Remember, erasing is prohibited here!
450 } // at this point RCU lock is released
453 Each iterator object supports the common interface:
454 - dereference operators:
456 value_type [const] * operator ->() noexcept
457 value_type [const] & operator *() noexcept
459 - pre-increment and pre-decrement. Post-operators is not supported
460 - equality operators <tt>==</tt> and <tt>!=</tt>.
461 Iterators are equal iff they point to the same cell of the same array node.
462 Note that for two iterators \p it1 and \p it2 the condition <tt> it1 == it2 </tt>
463 does not entail <tt> &(*it1) == &(*it2) </tt>: welcome to concurrent containers
465 @note It is possible the item can be iterated more that once, for example, if an iterator points to the item
466 in an array node that is being splitted.
470 /// Returns an iterator to the beginning of the set
473 return base_class::begin();
476 /// Returns an const iterator to the beginning of the set
477 const_iterator begin() const
479 return base_class::begin();
482 /// Returns an const iterator to the beginning of the set
483 const_iterator cbegin()
485 return base_class::cbegin();
488 /// 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.
491 return base_class::end();
494 /// 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.
495 const_iterator end() const
497 return base_class::end();
500 /// 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.
501 const_iterator cend()
503 return base_class::cend();
506 /// Returns a reverse iterator to the first element of the reversed set
507 reverse_iterator rbegin()
509 return base_class::rbegin();
512 /// Returns a const reverse iterator to the first element of the reversed set
513 const_reverse_iterator rbegin() const
515 return base_class::rbegin();
518 /// Returns a const reverse iterator to the first element of the reversed set
519 const_reverse_iterator crbegin()
521 return base_class::crbegin();
524 /// Returns a reverse iterator to the element following the last element of the reversed set
526 It corresponds to the element preceding the first element of the non-reversed container.
527 This element acts as a placeholder, attempting to access it results in undefined behavior.
529 reverse_iterator rend()
531 return base_class::rend();
534 /// Returns a const reverse iterator to the element following the last element of the reversed set
536 It corresponds to the element preceding the first element of the non-reversed container.
537 This element acts as a placeholder, attempting to access it results in undefined behavior.
539 const_reverse_iterator rend() const
541 return base_class::rend();
544 /// Returns a const reverse iterator to the element following the last element of the reversed set
546 It corresponds to the element preceding the first element of the non-reversed container.
547 This element acts as a placeholder, attempting to access it results in undefined behavior.
549 const_reverse_iterator crend()
551 return base_class::crend();
556 }} // namespace cds::container
558 #endif // #ifndef CDSLIB_CONTAINER_FELDMAN_HASHSET_RCU_H