2 This file is a part of libcds - Concurrent Data Structures library
4 (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2017
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
115 /// The size of hash_type in bytes, see \p feldman_hashset::traits::hash_size for explanation
116 static CDS_CONSTEXPR size_t const c_hash_size = base_class::c_hash_size;
119 typedef feldman_hashset::level_statistics level_statistics;
123 typedef typename maker::cxx_node_allocator cxx_node_allocator;
124 typedef std::unique_ptr< value_type, typename maker::node_disposer > scoped_node_ptr;
128 /// Creates empty set
130 @param head_bits - 2<sup>head_bits</sup> specifies the size of head array, minimum is 4.
131 @param array_bits - 2<sup>array_bits</sup> specifies the size of array node, minimum is 2.
133 Equation for \p head_bits and \p array_bits:
135 sizeof(hash_type) * 8 == head_bits + N * array_bits
137 where \p N is multi-level array depth.
139 FeldmanHashSet( size_t head_bits = 8, size_t array_bits = 4 )
140 : base_class( head_bits, array_bits )
143 /// Destructs the set and frees all data
147 /// Inserts new element
149 The function creates an element with copy of \p val value and then inserts it into the set.
151 The type \p Q should contain as minimum the complete hash for the element.
152 The object of \ref value_type should be constructible from a value of type \p Q.
153 In trivial case, \p Q is equal to \ref value_type.
155 Returns \p true if \p val is inserted into the set, \p false otherwise.
157 The function locks RCU internally.
159 template <typename Q>
160 bool insert( Q const& val )
162 scoped_node_ptr sp( cxx_node_allocator().New( val ));
163 if ( base_class::insert( *sp )) {
170 /// Inserts new element
172 The function allows to split creating of new item into two part:
173 - create item with key only
174 - insert new item into the set
175 - if inserting is success, calls \p f functor to initialize value-fields of \p val.
177 The functor signature is:
179 void func( value_type& val );
181 where \p val is the item inserted. User-defined functor \p f should guarantee that during changing
182 \p val no any other changes could be made on this set's item by concurrent threads.
183 The user-defined functor is called only if the inserting is success.
185 The function locks RCU internally.
187 template <typename Q, typename Func>
188 bool insert( Q const& val, Func f )
190 scoped_node_ptr sp( cxx_node_allocator().New( val ));
191 if ( base_class::insert( *sp, f )) {
198 /// Updates the element
200 The operation performs inserting or replacing with lock-free manner.
202 If the \p val key not found in the set, then the new item created from \p val
203 will be inserted into the set iff \p bInsert is \p true.
204 Otherwise, if \p val is found, it is replaced with new item created from \p val
205 and previous item is disposed.
206 In both cases \p func functor is called.
208 The functor \p Func signature:
211 void operator()( value_type& cur, value_type * prev );
215 - \p cur - current element
216 - \p prev - pointer to previous element with such hash. \p prev is \p nullptr
217 if \p cur was just inserted.
219 The functor may change non-key fields of the \p item; however, \p func must guarantee
220 that during changing no any other modifications could be made on this item by concurrent threads.
222 Returns <tt> std::pair<bool, bool> </tt> where \p first is \p true if operation is successful,
223 i.e. the item has been inserted or updated,
224 \p second is \p true if the new item has been added or \p false if the item with key equal to \p val
227 template <typename Q, typename Func>
228 std::pair<bool, bool> update( Q const& val, Func func, bool bInsert = true )
230 scoped_node_ptr sp( cxx_node_allocator().New( val ));
231 std::pair<bool, bool> bRes = base_class::do_update( *sp, func, bInsert );
237 /// Inserts data of type \p value_type created in-place from <tt>std::forward<Args>(args)...</tt>
239 Returns \p true if inserting successful, \p false otherwise.
241 template <typename... Args>
242 bool emplace( Args&&... args )
244 scoped_node_ptr sp( cxx_node_allocator().MoveNew( std::forward<Args>(args)... ));
245 if ( base_class::insert( *sp )) {
252 /// Deletes the item from the set
254 The function searches \p hash in the set,
255 deletes the item found, and returns \p true.
256 If that item is not found the function returns \p false.
258 RCU should not be locked. The function locks RCU internally.
260 bool erase( hash_type const& hash )
262 return base_class::erase( hash );
265 /// Deletes the item from the set
267 The function searches \p hash in the set,
268 call \p f functor with item found, and deltes the element from the set.
270 The \p Func interface is
273 void operator()( value_type& item );
277 If \p hash is not found the function returns \p false.
279 RCU should not be locked. The function locks RCU internally.
281 template <typename Func>
282 bool erase( hash_type const& hash, Func f )
284 return base_class::erase( hash, f );
287 /// Extracts the item with specified \p hash
289 The function searches \p hash in the set,
290 unlinks it from the set, and returns \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to the item found.
291 If the item with key equal to \p key is not found the function returns an empty \p exempt_ptr.
293 RCU \p synchronize method can be called. RCU should NOT be locked.
294 The function does not call the disposer for the item found.
295 The disposer will be implicitly invoked when the returned object is destroyed or when
296 its \p release() member function is called.
299 typedef cds::container::FeldmanHashSet< cds::urcu::gc< cds::urcu::general_buffered<> >, foo, my_traits > set_type;
303 typename set_type::exempt_ptr ep( theSet.extract( 5 ));
308 // Dispose returned item.
313 exempt_ptr extract( hash_type const& hash )
315 return base_class::extract( hash );
318 /// Finds an item by it's \p hash
320 The function searches the item by \p hash and calls the functor \p f for item found.
321 The interface of \p Func functor is:
324 void operator()( value_type& item );
327 where \p item is the item found.
329 The functor may change non-key fields of \p item. Note that the functor is only guarantee
330 that \p item cannot be disposed during the functor is executing.
331 The functor does not serialize simultaneous access to the set's \p item. If such access is
332 possible you must provide your own synchronization schema on item level to prevent unsafe item modifications.
334 The function returns \p true if \p hash is found, \p false otherwise.
336 template <typename Func>
337 bool find( hash_type const& hash, Func f )
339 return base_class::find( hash, f );
342 /// Checks whether the set contains \p hash
344 The function searches the item by its \p hash
345 and returns \p true if it is found, or \p false otherwise.
347 bool contains( hash_type const& hash )
349 return base_class::contains( hash );
352 /// Finds an item by it's \p hash and returns the item found
354 The function searches the item by its \p hash
355 and returns the pointer to the item found.
356 If \p hash is not found the function returns \p nullptr.
358 RCU should be locked before the function invocation.
359 Returned pointer is valid only while RCU is locked.
363 typedef cds::container::FeldmanHashSet< your_template_params > my_set;
368 my_set::rcu_lock lock;
370 foo * p = theSet.get( 5 );
378 value_type * get( hash_type const& hash )
380 return base_class::get( hash );
383 /// Clears the set (non-atomic)
385 The function unlink all data node from the set.
386 The function is not atomic but is thread-safe.
387 After \p %clear() the set may not be empty because another threads may insert items.
394 /// Checks if the set is empty
396 Emptiness is checked by item counting: if item count is zero then the set is empty.
397 Thus, the correct item counting feature is an important part of the set implementation.
401 return base_class::empty();
404 /// Returns item count in the set
407 return base_class::size();
410 /// Returns const reference to internal statistics
411 stat const& statistics() const
413 return base_class::statistics();
416 /// Returns the size of head node
417 size_t head_size() const
419 return base_class::head_size();
422 /// Returns the size of the array node
423 size_t array_node_size() const
425 return base_class::array_node_size();
428 /// Collects tree level statistics into \p stat
430 The function traverses the set and collects statistics for each level of the tree
431 into \p feldman_hashset::level_statistics struct. The element of \p stat[i]
432 represents statistics for level \p i, level 0 is head array.
433 The function is thread-safe and may be called in multi-threaded environment.
435 Result can be useful for estimating efficiency of hash functor you use.
437 void get_level_statistics(std::vector< feldman_hashset::level_statistics>& stat) const
439 base_class::get_level_statistics(stat);
443 ///@name Thread-safe iterators
445 /// Bidirectional iterator
446 /** @anchor cds_container_FeldmanHashSet_rcu_iterators
447 The set supports thread-safe iterators: you may iterate over the set in multi-threaded environment
448 under explicit RCU lock.
449 RCU lock requirement means that inserting or searching is allowed but you must not erase the items from the set
450 since erasing under RCU lock can lead to a deadlock. However, another thread can call \p erase() safely
451 while your thread is iterating.
453 A typical example is:
458 uint32_t payload; // only for example
460 struct set_traits: cds::container::feldman_hashset::traits
462 struct hash_accessor {
463 uint32_t operator()( foo const& src ) const
470 typedef cds::urcu::gc< cds::urcu::general_buffered<>> rcu;
471 typedef cds::container::FeldmanHashSet< rcu, foo, set_traits > set_type;
477 // iterate over the set
480 typename set_type::rcu_lock l; // scoped RCU lock
483 for ( auto i = s.begin(); i != s.end(); ++i ) {
484 // deal with i. Remember, erasing is prohibited here!
487 } // at this point RCU lock is released
490 Each iterator object supports the common interface:
491 - dereference operators:
493 value_type [const] * operator ->() noexcept
494 value_type [const] & operator *() noexcept
496 - pre-increment and pre-decrement. Post-operators is not supported
497 - equality operators <tt>==</tt> and <tt>!=</tt>.
498 Iterators are equal iff they point to the same cell of the same array node.
499 Note that for two iterators \p it1 and \p it2 the condition <tt> it1 == it2 </tt>
500 does not entail <tt> &(*it1) == &(*it2) </tt>: welcome to concurrent containers
502 @note It is possible the item can be iterated more that once, for example, if an iterator points to the item
503 in an array node that is being splitted.
505 typedef typename base_class::iterator iterator;
506 typedef typename base_class::const_iterator const_iterator; ///< @ref cds_container_FeldmanHashSet_rcu_iterators "bidirectional const iterator" type
507 typedef typename base_class::reverse_iterator reverse_iterator; ///< @ref cds_container_FeldmanHashSet_rcu_iterators "bidirectional reverse iterator" type
508 typedef typename base_class::const_reverse_iterator const_reverse_iterator; ///< @ref cds_container_FeldmanHashSet_rcu_iterators "bidirectional reverse const iterator" type
510 /// Returns an iterator to the beginning of the set
513 return base_class::begin();
516 /// Returns an const iterator to the beginning of the set
517 const_iterator begin() const
519 return base_class::begin();
522 /// Returns an const iterator to the beginning of the set
523 const_iterator cbegin()
525 return base_class::cbegin();
528 /// 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.
531 return base_class::end();
534 /// 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.
535 const_iterator end() const
537 return base_class::end();
540 /// 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.
541 const_iterator cend()
543 return base_class::cend();
546 /// Returns a reverse iterator to the first element of the reversed set
547 reverse_iterator rbegin()
549 return base_class::rbegin();
552 /// Returns a const reverse iterator to the first element of the reversed set
553 const_reverse_iterator rbegin() const
555 return base_class::rbegin();
558 /// Returns a const reverse iterator to the first element of the reversed set
559 const_reverse_iterator crbegin()
561 return base_class::crbegin();
564 /// Returns a reverse iterator to the element following the last element of the reversed set
566 It corresponds to the element preceding the first element of the non-reversed container.
567 This element acts as a placeholder, attempting to access it results in undefined behavior.
569 reverse_iterator rend()
571 return base_class::rend();
574 /// Returns a const reverse iterator to the element following the last element of the reversed set
576 It corresponds to the element preceding the first element of the non-reversed container.
577 This element acts as a placeholder, attempting to access it results in undefined behavior.
579 const_reverse_iterator rend() const
581 return base_class::rend();
584 /// Returns a const reverse iterator to the element following the last element of the reversed set
586 It corresponds to the element preceding the first element of the non-reversed container.
587 This element acts as a placeholder, attempting to access it results in undefined behavior.
589 const_reverse_iterator crend()
591 return base_class::crend();
596 }} // namespace cds::container
598 #endif // #ifndef CDSLIB_CONTAINER_FELDMAN_HASHSET_RCU_H