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_CONTAINER_FELDMAN_HASHSET_RCU_H
32 #define CDSLIB_CONTAINER_FELDMAN_HASHSET_RCU_H
34 #include <cds/intrusive/feldman_hashset_rcu.h>
35 #include <cds/container/details/feldman_hashset_base.h>
37 namespace cds { namespace container {
39 /// Hash set based on multi-level array, \ref cds_urcu_desc "RCU" specialization
40 /** @ingroup cds_nonintrusive_set
41 @anchor cds_container_FeldmanHashSet_rcu
44 - [2013] Steven Feldman, Pierre LaBorde, Damian Dechev "Concurrent Multi-level Arrays:
45 Wait-free Extensible Hash Maps"
47 See algorithm short description @ref cds_intrusive_FeldmanHashSet_hp "here"
49 @note Two important things you should keep in mind when you're using \p %FeldmanHashSet:
50 - all keys must be fixed-size. It means that you cannot use \p std::string as a key for \p %FeldmanHashSet.
51 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>,
52 <a href="https://en.wikipedia.org/wiki/MurmurHash">MurmurHash</a>, <a href="https://en.wikipedia.org/wiki/CityHash">CityHash</a>
53 or its successor <a href="https://code.google.com/p/farmhash/">FarmHash</a> and so on, which
54 converts variable-length strings to fixed-length bit-strings, and use that hash as a key in \p %FeldmanHashSet.
55 - \p %FeldmanHashSet uses a perfect hashing. It means that if two different keys, for example, of type \p std::string,
56 have identical hash then you cannot insert both that keys in the set. \p %FeldmanHashSet does not maintain the key,
57 it maintains its fixed-size hash value.
59 The set supports @ref cds_container_FeldmanHashSet_iterators "bidirectional thread-safe iterators".
62 - \p RCU - one of \ref cds_urcu_gc "RCU type"
63 - \p T - a value type to be stored in the set
64 - \p Traits - type traits, the structure based on \p feldman_hashset::traits or result of \p feldman_hashset::make_traits metafunction.
65 \p Traits is the mandatory argument because it has one mandatory type - an @ref feldman_hashset::traits::hash_accessor "accessor"
66 to hash value of \p T. The set algorithm does not calculate that hash value.
68 @note Before including <tt><cds/intrusive/feldman_hashset_rcu.h></tt> you should include appropriate RCU header file,
69 see \ref cds_urcu_gc "RCU type" for list of existing RCU class and corresponding header files.
71 The set supports @ref cds_container_FeldmanHashSet_rcu_iterators "bidirectional thread-safe iterators"
72 with some restrictions.
77 #ifdef CDS_DOXYGEN_INVOKED
78 , class Traits = feldman_hashset::traits
83 class FeldmanHashSet< cds::urcu::gc< RCU >, T, Traits >
84 #ifdef CDS_DOXYGEN_INVOKED
85 : protected cds::intrusive::FeldmanHashSet< cds::urcu::gc< RCU >, T, Traits >
87 : protected cds::container::details::make_feldman_hashset< cds::urcu::gc< RCU >, T, Traits >::type
91 typedef cds::container::details::make_feldman_hashset< cds::urcu::gc< RCU >, T, Traits > maker;
92 typedef typename maker::type base_class;
96 typedef cds::urcu::gc< RCU > gc; ///< RCU garbage collector
97 typedef T value_type; ///< type of value stored in the set
98 typedef Traits traits; ///< Traits template parameter, see \p feldman_hashset::traits
100 typedef typename base_class::hash_accessor hash_accessor; ///< Hash accessor functor
101 typedef typename base_class::hash_type hash_type; ///< Hash type deduced from \p hash_accessor return type
102 typedef typename base_class::hash_comparator hash_comparator; ///< hash compare functor based on \p opt::compare and \p opt::less option setter
104 typedef typename traits::item_counter item_counter; ///< Item counter type
105 typedef typename traits::allocator allocator; ///< Element allocator
106 typedef typename traits::node_allocator node_allocator; ///< Array node allocator
107 typedef typename traits::memory_model memory_model; ///< Memory model
108 typedef typename traits::back_off back_off; ///< Backoff strategy
109 typedef typename traits::stat stat; ///< Internal statistics type
110 typedef typename traits::rcu_check_deadlock rcu_check_deadlock; ///< Deadlock checking policy
111 typedef typename gc::scoped_lock rcu_lock; ///< RCU scoped lock
112 static CDS_CONSTEXPR const bool c_bExtractLockExternal = false; ///< Group of \p extract_xxx functions does not require external locking
113 typedef typename base_class::exempt_ptr exempt_ptr; ///< pointer to extracted node
116 typedef feldman_hashset::level_statistics level_statistics;
120 typedef typename maker::cxx_node_allocator cxx_node_allocator;
121 typedef std::unique_ptr< value_type, typename maker::node_disposer > scoped_node_ptr;
125 /// Creates empty set
127 @param head_bits: 2<sup>head_bits</sup> specifies the size of head array, minimum is 4.
128 @param array_bits: 2<sup>array_bits</sup> specifies the size of array node, minimum is 2.
130 Equation for \p head_bits and \p array_bits:
132 sizeof(hash_type) * 8 == head_bits + N * array_bits
134 where \p N is multi-level array depth.
136 FeldmanHashSet( size_t head_bits = 8, size_t array_bits = 4 )
137 : base_class( head_bits, array_bits )
140 /// Destructs the set and frees all data
144 /// Inserts new element
146 The function creates an element with copy of \p val value and then inserts it into the set.
148 The type \p Q should contain as minimum the complete hash for the element.
149 The object of \ref value_type should be constructible from a value of type \p Q.
150 In trivial case, \p Q is equal to \ref value_type.
152 Returns \p true if \p val is inserted into the set, \p false otherwise.
154 The function locks RCU internally.
156 template <typename Q>
157 bool insert( Q const& val )
159 scoped_node_ptr sp( cxx_node_allocator().New( val ));
160 if ( base_class::insert( *sp )) {
167 /// Inserts new element
169 The function allows to split creating of new item into two part:
170 - create item with key only
171 - insert new item into the set
172 - if inserting is success, calls \p f functor to initialize value-fields of \p val.
174 The functor signature is:
176 void func( value_type& val );
178 where \p val is the item inserted. User-defined functor \p f should guarantee that during changing
179 \p val no any other changes could be made on this set's item by concurrent threads.
180 The user-defined functor is called only if the inserting is success.
182 The function locks RCU internally.
184 template <typename Q, typename Func>
185 bool insert( Q const& val, Func f )
187 scoped_node_ptr sp( cxx_node_allocator().New( val ));
188 if ( base_class::insert( *sp, f )) {
195 /// Updates the element
197 The operation performs inserting or replacing with lock-free manner.
199 If the \p val key not found in the set, then the new item created from \p val
200 will be inserted into the set iff \p bInsert is \p true.
201 Otherwise, if \p val is found, it is replaced with new item created from \p val
202 and previous item is disposed.
203 In both cases \p func functor is called.
205 The functor \p Func signature:
208 void operator()( value_type& cur, value_type * prev );
212 - \p cur - current element
213 - \p prev - pointer to previous element with such hash. \p prev is \p nullptr
214 if \p cur was just inserted.
216 The functor may change non-key fields of the \p item; however, \p func must guarantee
217 that during changing no any other modifications could be made on this item by concurrent threads.
219 Returns <tt> std::pair<bool, bool> </tt> where \p first is \p true if operation is successful,
220 i.e. the item has been inserted or updated,
221 \p second is \p true if the new item has been added or \p false if the item with key equal to \p val
224 template <typename Q, typename Func>
225 std::pair<bool, bool> update( Q const& val, Func func, bool bInsert = true )
227 scoped_node_ptr sp( cxx_node_allocator().New( val ));
228 std::pair<bool, bool> bRes = base_class::do_update( *sp, func, bInsert );
234 /// Inserts data of type \p value_type created in-place from <tt>std::forward<Args>(args)...</tt>
236 Returns \p true if inserting successful, \p false otherwise.
238 template <typename... Args>
239 bool emplace( Args&&... args )
241 scoped_node_ptr sp( cxx_node_allocator().MoveNew( std::forward<Args>(args)... ));
242 if ( base_class::insert( *sp )) {
249 /// Deletes the item from the set
251 The function searches \p hash in the set,
252 deletes the item found, and returns \p true.
253 If that item is not found the function returns \p false.
255 RCU should not be locked. The function locks RCU internally.
257 bool erase( hash_type const& hash )
259 return base_class::erase( hash );
262 /// Deletes the item from the set
264 The function searches \p hash in the set,
265 call \p f functor with item found, and deltes the element from the set.
267 The \p Func interface is
270 void operator()( value_type& item );
274 If \p hash is not found the function returns \p false.
276 RCU should not be locked. The function locks RCU internally.
278 template <typename Func>
279 bool erase( hash_type const& hash, Func f )
281 return base_class::erase( hash, f );
284 /// Extracts the item with specified \p hash
286 The function searches \p hash in the set,
287 unlinks it from the set, and returns \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to the item found.
288 If the item with key equal to \p key is not found the function returns an empty \p exempt_ptr.
290 RCU \p synchronize method can be called. RCU should NOT be locked.
291 The function does not call the disposer for the item found.
292 The disposer will be implicitly invoked when the returned object is destroyed or when
293 its \p release() member function is called.
296 typedef cds::container::FeldmanHashSet< cds::urcu::gc< cds::urcu::general_buffered<> >, foo, my_traits > set_type;
300 typename set_type::exempt_ptr ep( theSet.extract( 5 ));
305 // Dispose returned item.
310 exempt_ptr extract( hash_type const& hash )
312 return base_class::extract( hash );
315 /// Finds an item by it's \p hash
317 The function searches the item by \p hash and calls the functor \p f for item found.
318 The interface of \p Func functor is:
321 void operator()( value_type& item );
324 where \p item is the item found.
326 The functor may change non-key fields of \p item. Note that the functor is only guarantee
327 that \p item cannot be disposed during the functor is executing.
328 The functor does not serialize simultaneous access to the set's \p item. If such access is
329 possible you must provide your own synchronization schema on item level to prevent unsafe item modifications.
331 The function returns \p true if \p hash is found, \p false otherwise.
333 template <typename Func>
334 bool find( hash_type const& hash, Func f )
336 return base_class::find( hash, f );
339 /// Checks whether the set contains \p hash
341 The function searches the item by its \p hash
342 and returns \p true if it is found, or \p false otherwise.
344 bool contains( hash_type const& hash )
346 return base_class::contains( hash );
349 /// Finds an item by it's \p hash and returns the item found
351 The function searches the item by its \p hash
352 and returns the pointer to the item found.
353 If \p hash is not found the function returns \p nullptr.
355 RCU should be locked before the function invocation.
356 Returned pointer is valid only while RCU is locked.
360 typedef cds::container::FeldmanHashSet< your_template_params > my_set;
365 my_set::rcu_lock lock;
367 foo * p = theSet.get( 5 );
375 value_type * get( hash_type const& hash )
377 return base_class::get( hash );
380 /// Clears the set (non-atomic)
382 The function unlink all data node from the set.
383 The function is not atomic but is thread-safe.
384 After \p %clear() the set may not be empty because another threads may insert items.
391 /// Checks if the set is empty
393 Emptiness is checked by item counting: if item count is zero then the set is empty.
394 Thus, the correct item counting feature is an important part of the set implementation.
398 return base_class::empty();
401 /// Returns item count in the set
404 return base_class::size();
407 /// Returns const reference to internal statistics
408 stat const& statistics() const
410 return base_class::statistics();
413 /// Returns the size of head node
414 size_t head_size() const
416 return base_class::head_size();
419 /// Returns the size of the array node
420 size_t array_node_size() const
422 return base_class::array_node_size();
425 /// Collects tree level statistics into \p stat
427 The function traverses the set and collects statistics for each level of the tree
428 into \p feldman_hashset::level_statistics struct. The element of \p stat[i]
429 represents statistics for level \p i, level 0 is head array.
430 The function is thread-safe and may be called in multi-threaded environment.
432 Result can be useful for estimating efficiency of hash functor you use.
434 void get_level_statistics(std::vector< feldman_hashset::level_statistics>& stat) const
436 base_class::get_level_statistics(stat);
440 ///@name Thread-safe iterators
442 /// Bidirectional iterator
443 /** @anchor cds_container_FeldmanHashSet_rcu_iterators
444 The set supports thread-safe iterators: you may iterate over the set in multi-threaded environment
445 under explicit RCU lock.
446 RCU lock requirement means that inserting or searching is allowed but you must not erase the items from the set
447 since erasing under RCU lock can lead to a deadlock. However, another thread can call \p erase() safely
448 while your thread is iterating.
450 A typical example is:
455 uint32_t payload; // only for example
457 struct set_traits: cds::container::feldman_hashset::traits
459 struct hash_accessor {
460 uint32_t operator()( foo const& src ) const
467 typedef cds::urcu::gc< cds::urcu::general_buffered<>> rcu;
468 typedef cds::container::FeldmanHashSet< rcu, foo, set_traits > set_type;
474 // iterate over the set
477 typename set_type::rcu_lock l; // scoped RCU lock
480 for ( auto i = s.begin(); i != s.end(); ++i ) {
481 // deal with i. Remember, erasing is prohibited here!
484 } // at this point RCU lock is released
487 Each iterator object supports the common interface:
488 - dereference operators:
490 value_type [const] * operator ->() noexcept
491 value_type [const] & operator *() noexcept
493 - pre-increment and pre-decrement. Post-operators is not supported
494 - equality operators <tt>==</tt> and <tt>!=</tt>.
495 Iterators are equal iff they point to the same cell of the same array node.
496 Note that for two iterators \p it1 and \p it2 the condition <tt> it1 == it2 </tt>
497 does not entail <tt> &(*it1) == &(*it2) </tt>: welcome to concurrent containers
499 @note It is possible the item can be iterated more that once, for example, if an iterator points to the item
500 in an array node that is being splitted.
502 typedef typename base_class::iterator iterator;
503 typedef typename base_class::const_iterator const_iterator; ///< @ref cds_container_FeldmanHashSet_rcu_iterators "bidirectional const iterator" type
504 typedef typename base_class::reverse_iterator reverse_iterator; ///< @ref cds_container_FeldmanHashSet_rcu_iterators "bidirectional reverse iterator" type
505 typedef typename base_class::const_reverse_iterator const_reverse_iterator; ///< @ref cds_container_FeldmanHashSet_rcu_iterators "bidirectional reverse const iterator" type
507 /// Returns an iterator to the beginning of the set
510 return base_class::begin();
513 /// Returns an const iterator to the beginning of the set
514 const_iterator begin() const
516 return base_class::begin();
519 /// Returns an const iterator to the beginning of the set
520 const_iterator cbegin()
522 return base_class::cbegin();
525 /// 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.
528 return base_class::end();
531 /// 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.
532 const_iterator end() const
534 return base_class::end();
537 /// 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.
538 const_iterator cend()
540 return base_class::cend();
543 /// Returns a reverse iterator to the first element of the reversed set
544 reverse_iterator rbegin()
546 return base_class::rbegin();
549 /// Returns a const reverse iterator to the first element of the reversed set
550 const_reverse_iterator rbegin() const
552 return base_class::rbegin();
555 /// Returns a const reverse iterator to the first element of the reversed set
556 const_reverse_iterator crbegin()
558 return base_class::crbegin();
561 /// Returns a reverse iterator to the element following the last element of the reversed set
563 It corresponds to the element preceding the first element of the non-reversed container.
564 This element acts as a placeholder, attempting to access it results in undefined behavior.
566 reverse_iterator rend()
568 return base_class::rend();
571 /// Returns a const reverse iterator to the element following the last element of the reversed set
573 It corresponds to the element preceding the first element of the non-reversed container.
574 This element acts as a placeholder, attempting to access it results in undefined behavior.
576 const_reverse_iterator rend() const
578 return base_class::rend();
581 /// Returns a const reverse iterator to the element following the last element of the reversed set
583 It corresponds to the element preceding the first element of the non-reversed container.
584 This element acts as a placeholder, attempting to access it results in undefined behavior.
586 const_reverse_iterator crend()
588 return base_class::crend();
593 }} // namespace cds::container
595 #endif // #ifndef CDSLIB_CONTAINER_FELDMAN_HASHSET_RCU_H