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_INTRUSIVE_DETAILS_FELDMAN_HASHSET_BASE_H
32 #define CDSLIB_INTRUSIVE_DETAILS_FELDMAN_HASHSET_BASE_H
34 #include <memory.h> // memcmp, memcpy
35 #include <type_traits>
37 #include <cds/intrusive/details/base.h>
38 #include <cds/opt/compare.h>
39 #include <cds/algo/atomic.h>
40 #include <cds/algo/split_bitstring.h>
41 #include <cds/details/marked_ptr.h>
42 #include <cds/urcu/options.h>
44 namespace cds { namespace intrusive {
46 /// FeldmanHashSet related definitions
47 /** @ingroup cds_intrusive_helper
49 namespace feldman_hashset {
50 /// Hash accessor option
52 @copydetails traits::hash_accessor
54 template <typename Accessor>
55 struct hash_accessor {
57 template <typename Base> struct pack: public Base
59 typedef Accessor hash_accessor;
66 @copydetails traits::hash_size
68 template <size_t Size>
71 template <typename Base> struct pack: public Base
80 /// Hash splitter option
82 @copydetails traits::hash_splitter
84 template <typename Splitter>
85 struct hash_splitter {
87 template <typename Base> struct pack: public Base
89 typedef Splitter hash_splitter;
95 /// \p FeldmanHashSet internal statistics
96 template <typename EventCounter = cds::atomicity::event_counter>
98 typedef EventCounter event_counter ; ///< Event counter type
100 event_counter m_nInsertSuccess; ///< Number of success \p insert() operations
101 event_counter m_nInsertFailed; ///< Number of failed \p insert() operations
102 event_counter m_nInsertRetry; ///< Number of attempts to insert new item
103 event_counter m_nUpdateNew; ///< Number of new item inserted for \p update()
104 event_counter m_nUpdateExisting; ///< Number of existing item updates
105 event_counter m_nUpdateFailed; ///< Number of failed \p update() call
106 event_counter m_nUpdateRetry; ///< Number of attempts to update the item
107 event_counter m_nEraseSuccess; ///< Number of successful \p erase(), \p unlink(), \p extract() operations
108 event_counter m_nEraseFailed; ///< Number of failed \p erase(), \p unlink(), \p extract() operations
109 event_counter m_nEraseRetry; ///< Number of attempts to \p erase() an item
110 event_counter m_nFindSuccess; ///< Number of successful \p find() and \p get() operations
111 event_counter m_nFindFailed; ///< Number of failed \p find() and \p get() operations
113 event_counter m_nExpandNodeSuccess; ///< Number of succeeded attempts converting data node to array node
114 event_counter m_nExpandNodeFailed; ///< Number of failed attempts converting data node to array node
115 event_counter m_nSlotChanged; ///< Number of array node slot changing by other thread during an operation
116 event_counter m_nSlotConverting; ///< Number of events when we encounter a slot while it is converting to array node
118 event_counter m_nArrayNodeCount; ///< Number of array nodes
119 event_counter m_nHeight; ///< Current height of the tree
122 void onInsertSuccess() { ++m_nInsertSuccess; }
123 void onInsertFailed() { ++m_nInsertFailed; }
124 void onInsertRetry() { ++m_nInsertRetry; }
125 void onUpdateNew() { ++m_nUpdateNew; }
126 void onUpdateExisting() { ++m_nUpdateExisting; }
127 void onUpdateFailed() { ++m_nUpdateFailed; }
128 void onUpdateRetry() { ++m_nUpdateRetry; }
129 void onEraseSuccess() { ++m_nEraseSuccess; }
130 void onEraseFailed() { ++m_nEraseFailed; }
131 void onEraseRetry() { ++m_nEraseRetry; }
132 void onFindSuccess() { ++m_nFindSuccess; }
133 void onFindFailed() { ++m_nFindFailed; }
135 void onExpandNodeSuccess() { ++m_nExpandNodeSuccess; }
136 void onExpandNodeFailed() { ++m_nExpandNodeFailed; }
137 void onSlotChanged() { ++m_nSlotChanged; }
138 void onSlotConverting() { ++m_nSlotConverting; }
139 void onArrayNodeCreated() { ++m_nArrayNodeCount; }
140 void height( size_t h ) { if (m_nHeight < h ) m_nHeight = h; }
144 /// \p FeldmanHashSet empty internal statistics
147 void onInsertSuccess() const {}
148 void onInsertFailed() const {}
149 void onInsertRetry() const {}
150 void onUpdateNew() const {}
151 void onUpdateExisting() const {}
152 void onUpdateFailed() const {}
153 void onUpdateRetry() const {}
154 void onEraseSuccess() const {}
155 void onEraseFailed() const {}
156 void onEraseRetry() const {}
157 void onFindSuccess() const {}
158 void onFindFailed() const {}
160 void onExpandNodeSuccess() const {}
161 void onExpandNodeFailed() const {}
162 void onSlotChanged() const {}
163 void onSlotConverting() const {}
164 void onArrayNodeCreated() const {}
165 void height(size_t) const {}
169 /// \p FeldmanHashSet traits
172 /// Mandatory functor to get hash value from data node
174 It is most-important feature of \p FeldmanHashSet.
175 That functor must return a reference to fixed-sized hash value of data node.
176 The return value of that functor specifies the type of hash value.
180 typedef uint8_t hash_type[32]; // 256-bit hash type
182 hash_type hash; // 256-bit hash value
187 struct foo_hash_accessor {
188 hash_type const& operator()( foo const& d ) const
195 typedef cds::opt::none hash_accessor;
197 /// The size of hash value in bytes
199 By default, the size of hash value is <tt>sizeof( hash_type )</tt>.
200 Sometimes it is not correct, for example, for that 6-byte struct \p static_assert will be thrown:
207 static_assert( sizeof( key_type ) == 6, "Key type size mismatch" );
209 For that case you can specify \p hash_size explicitly.
211 Value \p 0 means <tt>sizeof( hash_type )</tt>.
213 static CDS_CONSTEXPR size_t const hash_size = 0;
217 This trait specifies hash bit-string splitter algorithm.
218 By default, \p cds::algo::number_splitter is used if \p HashType is a number,
219 \p cds::algo::split_bitstring otherwise.
221 typedef cds::opt::none hash_splitter;
223 /// Disposer for removing data nodes
224 typedef cds::intrusive::opt::v::empty_disposer disposer;
226 /// Hash comparing functor
228 No default functor is provided.
229 If the option is not specified, the \p less option is used.
231 typedef cds::opt::none compare;
233 /// Specifies binary predicate used for hash compare.
235 If \p %less and \p %compare are not specified, \p memcmp() -like @ref bitwise_compare "bit-wise hash comparator" is used
236 because the hash value is treated as fixed-sized bit-string.
238 typedef cds::opt::none less;
242 The item counting is an important part of \p FeldmanHashSet algorithm:
243 the \p empty() member function depends on correct item counting.
244 Therefore, \p atomicity::empty_item_counter is not allowed as a type of the option.
246 Default is \p atomicity::item_counter. To avoid false sharing you can aldo use \p atomicity::cache_friendly_item_counter
248 typedef cds::atomicity::item_counter item_counter;
250 /// Array node allocator
252 Allocator for array nodes. The allocator is used for creating \p headNode and \p arrayNode when the set grows.
253 Default is \ref CDS_DEFAULT_ALLOCATOR
255 typedef CDS_DEFAULT_ALLOCATOR node_allocator;
257 /// C++ memory ordering model
259 Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
260 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
262 typedef cds::opt::v::relaxed_ordering memory_model;
264 /// Back-off strategy
265 typedef cds::backoff::Default back_off;
267 /// Internal statistics
269 By default, internal statistics is disabled (\p feldman_hashset::empty_stat).
270 Use \p feldman_hashset::stat to enable it.
272 typedef empty_stat stat;
274 /// RCU deadlock checking policy (only for \ref cds_intrusive_FeldmanHashSet_rcu "RCU-based FeldmanHashSet")
276 List of available policy see \p opt::rcu_check_deadlock
278 typedef cds::opt::v::rcu_throw_deadlock rcu_check_deadlock;
281 /// Metafunction converting option list to \p feldman_hashset::traits
283 Supported \p Options are:
284 - \p feldman_hashset::hash_accessor - mandatory option, hash accessor functor.
285 @copydetails traits::hash_accessor
286 - \p feldman_hashset::hash_size - the size of hash value in bytes.
287 @copydetails traits::hash_size
288 - \p feldman_hashset::hash_splitter - a hash splitter algorithm
289 @copydetails traits::hash_splitter
290 - \p opt::node_allocator - array node allocator.
291 @copydetails traits::node_allocator
292 - \p opt::compare - hash comparison functor. No default functor is provided.
293 If the option is not specified, the \p opt::less is used.
294 - \p opt::less - specifies binary predicate used for hash comparison.
295 If the option is not specified, \p memcmp() -like bit-wise hash comparator is used
296 because the hash value is treated as fixed-sized bit-string.
297 - \p opt::back_off - back-off strategy used. If the option is not specified, the \p cds::backoff::Default is used.
298 - \p opt::disposer - the functor used for disposing removed data node. Default is \p opt::v::empty_disposer. Due the nature
299 of GC schema the disposer may be called asynchronously.
300 - \p opt::item_counter - the type of item counting feature.
301 The item counting is an important part of \p FeldmanHashSet algorithm:
302 the \p empty() member function depends on correct item counting.
303 Therefore, \p atomicity::empty_item_counter is not allowed as a type of the option.
304 Default is \p atomicity::item_counter. To avoid false sharing you can use or \p atomicity::cache_friendly_item_counter
305 - \p opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
306 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
307 - \p opt::stat - internal statistics. By default, it is disabled (\p feldman_hashset::empty_stat).
308 To enable it use \p feldman_hashset::stat
309 - \p opt::rcu_check_deadlock - a deadlock checking policy for \ref cds_intrusive_FeldmanHashSet_rcu "RCU-based FeldmanHashSet"
310 Default is \p opt::v::rcu_throw_deadlock
312 template <typename... Options>
315 # ifdef CDS_DOXYGEN_INVOKED
316 typedef implementation_defined type ; ///< Metafunction result
318 typedef typename cds::opt::make_options<
319 typename cds::opt::find_type_traits< traits, Options... >::type
325 /// Bit-wise memcmp-based comparator for hash value \p T
326 template <typename T>
327 struct bitwise_compare
329 /// Compares \p lhs and \p rhs
332 - <tt> < 0</tt> if <tt>lhs < rhs</tt>
333 - <tt>0</tt> if <tt>lhs == rhs</tt>
334 - <tt> > 0</tt> if <tt>lhs > rhs</tt>
336 int operator()( T const& lhs, T const& rhs ) const
338 return memcmp( &lhs, &rhs, sizeof(T));
342 /// One-level statistics, see \p FeldmanHashSet::get_level_statistics
343 struct level_statistics
345 size_t array_node_count; ///< Count of array node at the level
346 size_t node_capacity; ///< Array capacity
348 size_t data_cell_count; ///< The number of data cells in all array node at this level
349 size_t array_cell_count; ///< The number of array cells in all array node at this level
350 size_t empty_cell_count; ///< The number of empty cells in all array node at this level
354 : array_node_count(0)
356 , array_cell_count(0)
357 , empty_cell_count(0)
364 template <typename HashType, size_t HashSize >
365 using hash_splitter = cds::algo::split_bitstring< HashType, HashSize >;
368 size_t head_node_size; // power-of-two
369 size_t head_node_size_log; // log2( head_node_size )
370 size_t array_node_size; // power-of-two
371 size_t array_node_size_log;// log2( array_node_size )
373 static metrics make(size_t head_bits, size_t array_bits, size_t hash_size )
375 size_t const hash_bits = hash_size * 8;
381 if (head_bits > hash_bits)
382 head_bits = hash_bits;
383 if ((hash_bits - head_bits) % array_bits != 0)
384 head_bits += (hash_bits - head_bits) % array_bits;
386 assert((hash_bits - head_bits) % array_bits == 0);
389 m.head_node_size_log = head_bits;
390 m.head_node_size = size_t(1) << head_bits;
391 m.array_node_size_log = array_bits;
392 m.array_node_size = size_t(1) << array_bits;
397 } // namespace details
401 template <typename T, typename Traits>
402 class multilevel_array
405 typedef T value_type;
406 typedef Traits traits;
407 typedef typename Traits::node_allocator node_allocator;
408 typedef typename traits::memory_model memory_model;
409 typedef typename traits::back_off back_off; ///< Backoff strategy
410 typedef typename traits::stat stat; ///< Internal statistics type
412 typedef typename traits::hash_accessor hash_accessor;
413 static_assert(!std::is_same< hash_accessor, cds::opt::none >::value, "hash_accessor functor must be specified");
415 /// Hash type deduced from \p hash_accessor return type
416 typedef typename std::decay<
417 typename std::remove_reference<
418 decltype(hash_accessor()(std::declval<value_type>()))
421 static_assert(!std::is_pointer<hash_type>::value, "hash_accessor should return a reference to hash value");
423 typedef typename cds::opt::details::make_comparator_from<
426 feldman_hashset::bitwise_compare< hash_type >
427 >::type hash_comparator;
429 /// The size of hash_type in bytes, see \p traits::hash_size for explanation
430 static CDS_CONSTEXPR size_t const c_hash_size = traits::hash_size == 0 ? sizeof( hash_type ) : static_cast<size_t>( traits::hash_size );
432 typedef typename std::conditional<
433 std::is_same< typename traits::hash_splitter, cds::opt::none >::value,
434 typename cds::algo::select_splitter< hash_type, c_hash_size >::type,
435 typename traits::hash_splitter
436 >::type hash_splitter;
439 flag_array_converting = 1, ///< the cell is converting from data node to an array node
440 flag_array_node = 2 ///< the cell is a pointer to an array node
445 typedef cds::details::marked_ptr< value_type, 3 > node_ptr;
446 typedef atomics::atomic< node_ptr > atomic_node_ptr;
449 array_node * const pParent; ///< parent array node
450 size_t const idxParent; ///< index in parent array node
451 atomic_node_ptr nodes[1]; ///< node array
453 array_node(array_node * parent, size_t idx)
458 array_node() = delete;
459 array_node(array_node const&) = delete;
460 array_node(array_node&&) = delete;
463 typedef cds::details::Allocator< array_node, node_allocator > cxx_array_node_allocator;
465 struct traverse_data {
466 hash_splitter splitter;
468 typename hash_splitter::uint_type nSlot;
471 traverse_data( hash_type const& hash, multilevel_array& arr )
477 void reset( multilevel_array& arr )
481 nSlot = splitter.cut( static_cast<unsigned>( arr.metrics().head_node_size_log ));
482 assert( static_cast<size_t>( nSlot ) < arr.metrics().head_node_size );
488 feldman_hashset::details::metrics const m_Metrics;
493 multilevel_array(size_t head_bits, size_t array_bits )
494 : m_Metrics(feldman_hashset::details::metrics::make( head_bits, array_bits, c_hash_size ))
495 , m_Head( alloc_head_node())
497 assert( hash_splitter::is_correct( static_cast<unsigned>( metrics().head_node_size_log )));
498 assert( hash_splitter::is_correct( static_cast<unsigned>( metrics().array_node_size_log )));
504 free_array_node( m_Head, head_size());
507 node_ptr traverse(traverse_data& pos)
511 node_ptr slot = pos.pArr->nodes[pos.nSlot].load(memory_model::memory_order_acquire);
512 if ( slot.bits() == flag_array_node ) {
513 // array node, go down the tree
514 assert(slot.ptr() != nullptr);
515 assert( !pos.splitter.eos());
516 pos.nSlot = pos.splitter.cut( static_cast<unsigned>( metrics().array_node_size_log ));
517 assert( static_cast<size_t>( pos.nSlot ) < metrics().array_node_size );
518 pos.pArr = to_array(slot.ptr());
521 else if (slot.bits() == flag_array_converting) {
522 // the slot is converting to array node right now
524 stats().onSlotConverting();
528 assert(slot.bits() == 0);
534 size_t head_size() const
536 return m_Metrics.head_node_size;
539 size_t array_node_size() const
541 return m_Metrics.array_node_size;
544 void get_level_statistics(std::vector< feldman_hashset::level_statistics>& stat) const
547 gather_level_statistics(stat, 0, m_Head, head_size());
551 array_node * head() const
561 feldman_hashset::details::metrics const& metrics() const
568 // The function is not thread-safe. For use in dtor only
569 // Destroy all array nodes
570 destroy_array_nodes(m_Head, head_size());
573 void destroy_array_nodes(array_node * pArr, size_t nSize)
575 for (atomic_node_ptr * p = pArr->nodes, *pLast = p + nSize; p != pLast; ++p) {
576 node_ptr slot = p->load(memory_model::memory_order_relaxed);
577 if (slot.bits() == flag_array_node) {
578 destroy_array_nodes( to_array(slot.ptr()), array_node_size());
579 free_array_node( to_array( slot.ptr()), array_node_size());
580 p->store(node_ptr(), memory_model::memory_order_relaxed);
585 static array_node * alloc_array_node(size_t nSize, array_node * pParent, size_t idxParent)
587 array_node * pNode = cxx_array_node_allocator().NewBlock(sizeof(array_node) + sizeof(atomic_node_ptr) * (nSize - 1), pParent, idxParent);
588 new (pNode->nodes) atomic_node_ptr[nSize];
592 array_node * alloc_head_node() const
594 return alloc_array_node(head_size(), nullptr, 0);
597 array_node * alloc_array_node(array_node * pParent, size_t idxParent) const
599 return alloc_array_node(array_node_size(), pParent, idxParent);
602 static void free_array_node( array_node * parr, size_t /*nSize*/ )
604 cxx_array_node_allocator().Delete( parr, 1 );
611 converter(value_type * p)
615 converter(array_node * p)
620 static array_node * to_array(value_type * p)
622 return converter(p).pArr;
624 static value_type * to_node(array_node * p)
626 return converter(p).pData;
629 void gather_level_statistics(std::vector<feldman_hashset::level_statistics>& stat, size_t nLevel, array_node * pArr, size_t nSize) const
631 if (stat.size() <= nLevel) {
632 stat.resize(nLevel + 1);
633 stat[nLevel].node_capacity = nSize;
636 ++stat[nLevel].array_node_count;
637 for (atomic_node_ptr * p = pArr->nodes, *pLast = p + nSize; p != pLast; ++p) {
638 node_ptr slot = p->load(memory_model::memory_order_relaxed);
640 ++stat[nLevel].array_cell_count;
641 if (slot.bits() == flag_array_node)
642 gather_level_statistics(stat, nLevel + 1, to_array(slot.ptr()), array_node_size());
645 ++stat[nLevel].data_cell_count;
647 ++stat[nLevel].empty_cell_count;
651 bool expand_slot( traverse_data& pos, node_ptr current)
653 assert( !pos.splitter.eos() );
654 return expand_slot( pos.pArr, pos.nSlot, current, pos.splitter.bit_offset());
658 bool expand_slot(array_node * pParent, size_t idxParent, node_ptr current, size_t nOffset)
660 assert(current.bits() == 0);
661 assert(current.ptr());
663 array_node * pArr = alloc_array_node(pParent, idxParent);
665 node_ptr cur(current.ptr());
666 atomic_node_ptr& slot = pParent->nodes[idxParent];
667 if (!slot.compare_exchange_strong(cur, cur | flag_array_converting, memory_model::memory_order_release, atomics::memory_order_relaxed))
669 stats().onExpandNodeFailed();
670 free_array_node( pArr, array_node_size());
674 typename hash_splitter::uint_type idx = hash_splitter( hash_accessor()(*current.ptr()), nOffset ).cut(
675 static_cast<unsigned>( m_Metrics.array_node_size_log ));
676 pArr->nodes[idx].store(current, memory_model::memory_order_release);
678 cur = cur | flag_array_converting;
680 slot.compare_exchange_strong(cur, node_ptr(to_node(pArr), flag_array_node), memory_model::memory_order_release, atomics::memory_order_relaxed)
683 stats().onExpandNodeSuccess();
684 stats().onArrayNodeCreated();
689 } // namespace feldman_hashset
692 // Forward declaration
693 template < class GC, typename T, class Traits = feldman_hashset::traits >
694 class FeldmanHashSet;
697 }} // namespace cds::intrusive
699 #endif // #ifndef CDSLIB_INTRUSIVE_DETAILS_FELDMAN_HASHSET_BASE_H