3 #ifndef CDSLIB_INTRUSIVE_DETAILS_SKIP_LIST_BASE_H
4 #define CDSLIB_INTRUSIVE_DETAILS_SKIP_LIST_BASE_H
6 #include <cds/intrusive/details/base.h>
7 #include <cds/details/marked_ptr.h>
8 #include <cds/algo/bitop.h>
9 #include <cds/os/timer.h>
10 #include <cds/urcu/options.h>
12 namespace cds { namespace intrusive {
13 /// SkipListSet related definitions
14 /** @ingroup cds_intrusive_helper
17 /// The maximum possible height of any skip-list
18 static unsigned int const c_nHeightLimit = 32;
23 - \p GC - garbage collector
24 - \p Tag - a \ref cds_intrusive_hook_tag "tag"
26 template <class GC, typename Tag = opt::none>
30 typedef GC gc; ///< Garbage collector
31 typedef Tag tag; ///< tag
33 typedef cds::details::marked_ptr<node, 1> marked_ptr; ///< marked pointer
34 typedef typename gc::template atomic_marked_ptr< marked_ptr> atomic_marked_ptr; ///< atomic marked pointer specific for GC
36 typedef atomic_marked_ptr tower_item_type;
40 atomic_marked_ptr m_pNext; ///< Next item in bottom-list (list at level 0)
41 unsigned int m_nHeight; ///< Node height (size of m_arrNext array). For node at level 0 the height is 1.
42 atomic_marked_ptr * m_arrNext; ///< Array of next items for levels 1 .. m_nHeight - 1. For node at level 0 \p m_arrNext is \p nullptr
45 /// Constructs a node of height 1 (a bottom-list node)
49 , m_arrNext( nullptr )
52 /// Constructs a node of height \p nHeight
53 void make_tower( unsigned int nHeight, atomic_marked_ptr * nextTower )
55 assert( nHeight > 0 );
56 assert( (nHeight == 1 && nextTower == nullptr) // bottom-list node
57 || (nHeight > 1 && nextTower != nullptr) // node at level of more than 0
60 m_arrNext = nextTower;
65 atomic_marked_ptr * release_tower()
67 atomic_marked_ptr * pTower = m_arrNext;
73 atomic_marked_ptr * get_tower() const
79 /// Access to element of next pointer array
80 atomic_marked_ptr& next( unsigned int nLevel )
82 assert( nLevel < height() );
83 assert( nLevel == 0 || (nLevel > 0 && m_arrNext != nullptr) );
85 # ifdef CDS_THREAD_SANITIZER_ENABLED
86 // TSan false positive: m_arrNext is read-only array
87 CDS_TSAN_ANNOTATE_IGNORE_READS_BEGIN;
88 atomic_marked_ptr& r = nLevel ? m_arrNext[ nLevel - 1] : m_pNext;
89 CDS_TSAN_ANNOTATE_IGNORE_READS_END;
92 return nLevel ? m_arrNext[ nLevel - 1] : m_pNext;
96 /// Access to element of next pointer array (const version)
97 atomic_marked_ptr const& next( unsigned int nLevel ) const
99 assert( nLevel < height() );
100 assert( nLevel == 0 || nLevel > 0 && m_arrNext != nullptr );
102 # ifdef CDS_THREAD_SANITIZER_ENABLED
103 // TSan false positive: m_arrNext is read-only array
104 CDS_TSAN_ANNOTATE_IGNORE_READS_BEGIN;
105 atomic_marked_ptr const& r = nLevel ? m_arrNext[ nLevel - 1] : m_pNext;
106 CDS_TSAN_ANNOTATE_IGNORE_READS_END;
109 return nLevel ? m_arrNext[ nLevel - 1] : m_pNext;
113 /// Access to element of next pointer array (same as \ref next function)
114 atomic_marked_ptr& operator[]( unsigned int nLevel )
116 return next( nLevel );
119 /// Access to element of next pointer array (same as \ref next function)
120 atomic_marked_ptr const& operator[]( unsigned int nLevel ) const
122 return next( nLevel );
125 /// Height of the node
126 unsigned int height() const
131 /// Clears internal links
134 assert( m_arrNext == nullptr );
135 m_pNext.store( marked_ptr(), atomics::memory_order_release );
139 bool is_cleared() const
141 return m_pNext == atomic_marked_ptr()
142 && m_arrNext == nullptr
150 struct default_hook {
151 typedef undefined_gc gc;
152 typedef opt::none tag;
157 template < typename HookType, typename... Options>
160 typedef typename opt::make_options< default_hook, Options...>::type options;
161 typedef typename options::gc gc;
162 typedef typename options::tag tag;
163 typedef node<gc, tag> node_type;
164 typedef HookType hook_type;
171 - \p opt::gc - garbage collector
172 - \p opt::tag - a \ref cds_intrusive_hook_tag "tag"
174 template < typename... Options >
175 struct base_hook: public hook< opt::base_hook_tag, Options... >
180 \p MemberOffset defines offset in bytes of \ref node member into your structure.
181 Use \p offsetof macro to define \p MemberOffset
184 - \p opt::gc - garbage collector
185 - \p opt::tag - a \ref cds_intrusive_hook_tag "tag"
187 template < size_t MemberOffset, typename... Options >
188 struct member_hook: public hook< opt::member_hook_tag, Options... >
191 static const size_t c_nMemberOffset = MemberOffset;
197 \p NodeTraits defines type traits for node.
198 See \ref node_traits for \p NodeTraits interface description
201 - \p opt::gc - garbage collector
202 - \p opt::tag - a \ref cds_intrusive_hook_tag "tag"
204 template <typename NodeTraits, typename... Options >
205 struct traits_hook: public hook< opt::traits_hook_tag, Options... >
208 typedef NodeTraits node_traits;
212 /// Option specifying random level generator
214 The random level generator is an important part of skip-list algorithm.
215 The node height in the skip-list have a probabilistic distribution
216 where half of the nodes that have level \p i pointers also have level <tt>i+1</tt> pointers
218 The random level generator should provide such distribution.
220 The \p Type functor interface is:
222 struct random_generator {
223 static unsigned int const c_nUpperBound = 32;
225 unsigned int operator()();
230 - \p c_nUpperBound - constant that specifies the upper bound of random number generated.
231 The generator produces a number from range <tt>[0 .. c_nUpperBound)</tt> (upper bound excluded).
232 \p c_nUpperBound must be no more than 32.
233 - <tt>random_generator()</tt> - the constructor of generator object initialises the generator instance (its internal state).
234 - <tt>unsigned int operator()()</tt> - the main generating function. Returns random level from range 0..31.
236 Stateful generators are supported.
238 Available \p Type implementations:
239 - \p skip_list::xorshift
240 - \p skip_list::turbo_pascal
242 template <typename Type>
243 struct random_level_generator {
245 template <typename Base>
246 struct pack: public Base
248 typedef Type random_level_generator;
253 /// Xor-shift random level generator
255 The simplest of the generators described in George
256 Marsaglia's "Xorshift RNGs" paper. This is not a high-quality
257 generator but is acceptable for skip-list.
259 The random generator should return numbers from range [0..31].
261 From Doug Lea's ConcurrentSkipListMap.java.
265 atomics::atomic<unsigned int> m_nSeed;
268 /// The upper bound of generator's return value. The generator produces random number in range <tt>[0..c_nUpperBound)</tt>
269 static unsigned int const c_nUpperBound = c_nHeightLimit;
271 /// Initializes the generator instance
274 m_nSeed.store( (unsigned int) cds::OS::Timer::random_seed(), atomics::memory_order_relaxed );
277 /// Main generator function
278 unsigned int operator()()
280 /* ConcurrentSkipListMap.java
281 private int randomLevel() {
285 randomSeed = x ^= x << 5;
286 if ((x & 0x80000001) != 0) // test highest and lowest bits
289 while (((x >>>= 1) & 1) != 0) ++level;
293 unsigned int x = m_nSeed.load( atomics::memory_order_relaxed );
297 m_nSeed.store( x, atomics::memory_order_relaxed );
298 unsigned int nLevel = ((x & 0x00000001) != 0) ? 0 : cds::bitop::LSB( (~(x >> 1)) & 0x7FFFFFFF );
299 assert( nLevel < c_nUpperBound );
304 /// Turbo-pascal random level generator
306 This uses a cheap pseudo-random function that was used in Turbo Pascal.
308 The random generator should return numbers from range [0..31].
310 From Doug Lea's ConcurrentSkipListMap.java.
315 atomics::atomic<unsigned int> m_nSeed;
318 /// The upper bound of generator's return value. The generator produces random number in range <tt>[0..c_nUpperBound)</tt>
319 static unsigned int const c_nUpperBound = c_nHeightLimit;
321 /// Initializes the generator instance
324 m_nSeed.store( (unsigned int) cds::OS::Timer::random_seed(), atomics::memory_order_relaxed );
327 /// Main generator function
328 unsigned int operator()()
331 private int randomLevel() {
334 randomSeed = r * 134775813 + 1;
336 while ((r <<= 1) > 0)
343 The low bits are apparently not very random (the original used only
344 upper 16 bits) so we traverse from highest bit down (i.e., test
345 sign), thus hardly ever use lower bits.
347 unsigned int x = m_nSeed.load( atomics::memory_order_relaxed ) * 134775813 + 1;
348 m_nSeed.store( x, atomics::memory_order_relaxed );
349 unsigned int nLevel = ( x & 0x80000000 ) ? (31 - cds::bitop::MSBnz( (x & 0x7FFFFFFF) | 1 )) : 0;
350 assert( nLevel < c_nUpperBound );
355 /// \p SkipListSet internal statistics
356 template <typename EventCounter = cds::atomicity::event_counter>
358 typedef EventCounter event_counter ; ///< Event counter type
360 event_counter m_nNodeHeightAdd[c_nHeightLimit] ; ///< Count of added node of each height
361 event_counter m_nNodeHeightDel[c_nHeightLimit] ; ///< Count of deleted node of each height
362 event_counter m_nInsertSuccess ; ///< Count of success insertion
363 event_counter m_nInsertFailed ; ///< Count of failed insertion
364 event_counter m_nInsertRetries ; ///< Count of unsuccessful retries of insertion
365 event_counter m_nUpdateExist ; ///< Count of \p update() call for existed node
366 event_counter m_nUpdateNew ; ///< Count of \p update() call for new node
367 event_counter m_nUnlinkSuccess ; ///< Count of successful call of \p unlink
368 event_counter m_nUnlinkFailed ; ///< Count of failed call of \p unlink
369 event_counter m_nEraseSuccess ; ///< Count of successful call of \p erase
370 event_counter m_nEraseFailed ; ///< Count of failed call of \p erase
371 event_counter m_nEraseRetry ; ///< Count of retries while erasing node
372 event_counter m_nFindFastSuccess ; ///< Count of successful call of \p find and all derivatives (via fast-path)
373 event_counter m_nFindFastFailed ; ///< Count of failed call of \p find and all derivatives (via fast-path)
374 event_counter m_nFindSlowSuccess ; ///< Count of successful call of \p find and all derivatives (via slow-path)
375 event_counter m_nFindSlowFailed ; ///< Count of failed call of \p find and all derivatives (via slow-path)
376 event_counter m_nRenewInsertPosition ; ///< Count of renewing position events while inserting
377 event_counter m_nLogicDeleteWhileInsert ; ///< Count of events "The node has been logically deleted while inserting"
378 event_counter m_nNotFoundWhileInsert ; ///< Count of events "Inserting node is not found"
379 event_counter m_nFastErase ; ///< Fast erase event counter
380 event_counter m_nFastExtract ; ///< Fast extract event counter
381 event_counter m_nSlowErase ; ///< Slow erase event counter
382 event_counter m_nSlowExtract ; ///< Slow extract event counter
383 event_counter m_nExtractSuccess ; ///< Count of successful call of \p extract
384 event_counter m_nExtractFailed ; ///< Count of failed call of \p extract
385 event_counter m_nExtractRetries ; ///< Count of retries of \p extract call
386 event_counter m_nExtractMinSuccess ; ///< Count of successful call of \p extract_min
387 event_counter m_nExtractMinFailed ; ///< Count of failed call of \p extract_min
388 event_counter m_nExtractMinRetries ; ///< Count of retries of \p extract_min call
389 event_counter m_nExtractMaxSuccess ; ///< Count of successful call of \p extract_max
390 event_counter m_nExtractMaxFailed ; ///< Count of failed call of \p extract_max
391 event_counter m_nExtractMaxRetries ; ///< Count of retries of \p extract_max call
392 event_counter m_nEraseWhileFind ; ///< Count of erased item while searching
393 event_counter m_nExtractWhileFind ; ///< Count of extracted item while searching (RCU only)
396 void onAddNode( unsigned int nHeight )
398 assert( nHeight > 0 && nHeight <= sizeof(m_nNodeHeightAdd) / sizeof(m_nNodeHeightAdd[0]));
399 ++m_nNodeHeightAdd[nHeight - 1];
401 void onRemoveNode( unsigned int nHeight )
403 assert( nHeight > 0 && nHeight <= sizeof(m_nNodeHeightDel) / sizeof(m_nNodeHeightDel[0]));
404 ++m_nNodeHeightDel[nHeight - 1];
407 void onInsertSuccess() { ++m_nInsertSuccess ; }
408 void onInsertFailed() { ++m_nInsertFailed ; }
409 void onInsertRetry() { ++m_nInsertRetries ; }
410 void onUpdateExist() { ++m_nUpdateExist ; }
411 void onUpdateNew() { ++m_nUpdateNew ; }
412 void onUnlinkSuccess() { ++m_nUnlinkSuccess ; }
413 void onUnlinkFailed() { ++m_nUnlinkFailed ; }
414 void onEraseSuccess() { ++m_nEraseSuccess ; }
415 void onEraseFailed() { ++m_nEraseFailed ; }
416 void onEraseRetry() { ++m_nEraseRetry; }
417 void onFindFastSuccess() { ++m_nFindFastSuccess ; }
418 void onFindFastFailed() { ++m_nFindFastFailed ; }
419 void onFindSlowSuccess() { ++m_nFindSlowSuccess ; }
420 void onFindSlowFailed() { ++m_nFindSlowFailed ; }
421 void onEraseWhileFind() { ++m_nEraseWhileFind ; }
422 void onExtractWhileFind() { ++m_nExtractWhileFind ; }
423 void onRenewInsertPosition() { ++m_nRenewInsertPosition; }
424 void onLogicDeleteWhileInsert() { ++m_nLogicDeleteWhileInsert; }
425 void onNotFoundWhileInsert() { ++m_nNotFoundWhileInsert; }
426 void onFastErase() { ++m_nFastErase; }
427 void onFastExtract() { ++m_nFastExtract; }
428 void onSlowErase() { ++m_nSlowErase; }
429 void onSlowExtract() { ++m_nSlowExtract; }
430 void onExtractSuccess() { ++m_nExtractSuccess; }
431 void onExtractFailed() { ++m_nExtractFailed; }
432 void onExtractRetry() { ++m_nExtractRetries; }
433 void onExtractMinSuccess() { ++m_nExtractMinSuccess; }
434 void onExtractMinFailed() { ++m_nExtractMinFailed; }
435 void onExtractMinRetry() { ++m_nExtractMinRetries; }
436 void onExtractMaxSuccess() { ++m_nExtractMaxSuccess; }
437 void onExtractMaxFailed() { ++m_nExtractMaxFailed; }
438 void onExtractMaxRetry() { ++m_nExtractMaxRetries; }
443 /// \p SkipListSet empty internal statistics
446 void onAddNode( unsigned int /*nHeight*/ ) const {}
447 void onRemoveNode( unsigned int /*nHeight*/ ) const {}
448 void onInsertSuccess() const {}
449 void onInsertFailed() const {}
450 void onInsertRetry() const {}
451 void onUpdateExist() const {}
452 void onUpdateNew() const {}
453 void onUnlinkSuccess() const {}
454 void onUnlinkFailed() const {}
455 void onEraseSuccess() const {}
456 void onEraseFailed() const {}
457 void onEraseRetry() const {}
458 void onFindFastSuccess() const {}
459 void onFindFastFailed() const {}
460 void onFindSlowSuccess() const {}
461 void onFindSlowFailed() const {}
462 void onEraseWhileFind() const {}
463 void onExtractWhileFind() const {}
464 void onRenewInsertPosition() const {}
465 void onLogicDeleteWhileInsert() const {}
466 void onNotFoundWhileInsert() const {}
467 void onFastErase() const {}
468 void onFastExtract() const {}
469 void onSlowErase() const {}
470 void onSlowExtract() const {}
471 void onExtractSuccess() const {}
472 void onExtractFailed() const {}
473 void onExtractRetry() const {}
474 void onExtractMinSuccess() const {}
475 void onExtractMinFailed() const {}
476 void onExtractMinRetry() const {}
477 void onExtractMaxSuccess() const {}
478 void onExtractMaxFailed() const {}
479 void onExtractMaxRetry() const {}
485 // For internal use only!!!
486 template <typename Type>
487 struct internal_node_builder {
488 template <typename Base>
489 struct pack: public Base
491 typedef Type internal_node_builder;
496 /// \p SkipListSet traits
501 Possible values are: \p skip_list::base_hook, \p skip_list::member_hook, \p skip_list::traits_hook.
503 typedef base_hook<> hook;
505 /// Key comparison functor
507 No default functor is provided. If the option is not specified, the \p less is used.
509 typedef opt::none compare;
511 /// specifies binary predicate used for key compare.
513 Default is \p std::less<T>.
515 typedef opt::none less;
519 The functor used for dispose removed items. Default is \p opt::v::empty_disposer.
521 typedef opt::v::empty_disposer disposer;
525 The type for item counting feature.
526 By default, item counting is disabled (\p atomicity::empty_item_counter)
527 \p atomicity::item_counter enables it.
529 typedef atomicity::empty_item_counter item_counter;
531 /// C++ memory ordering model
533 List of available memory ordering see \p opt::memory_model
535 typedef opt::v::relaxed_ordering memory_model;
537 /// Random level generator
539 The random level generator is an important part of skip-list algorithm.
540 The node height in the skip-list have a probabilistic distribution
541 where half of the nodes that have level \p i pointers also have level <tt>i+1</tt> pointers
542 (i = 0..30). So, the height of a node is in range [0..31].
544 See \p skip_list::random_level_generator option setter.
546 typedef turbo_pascal random_level_generator;
550 Although the skip-list is an intrusive container,
551 an allocator should be provided to maintain variable randomly-calculated height of the node
552 since the node can contain up to 32 next pointers.
553 The allocator specified is used to allocate an array of next pointers
554 for nodes which height is more than 1.
556 typedef CDS_DEFAULT_ALLOCATOR allocator;
558 /// back-off strategy
560 If the option is not specified, the \p cds::backoff::Default is used.
562 typedef cds::backoff::Default back_off;
564 /// Internal statistics
566 By default, internal statistics is disabled (\p skip_list::empty_stat).
567 Use \p skip_list::stat to enable it.
569 typedef empty_stat stat;
571 /// RCU deadlock checking policy (only for \ref cds_intrusive_SkipListSet_rcu "RCU-based SkipListSet")
573 List of available options see \p opt::rcu_check_deadlock
575 typedef opt::v::rcu_throw_deadlock rcu_check_deadlock;
578 // For internal use only!!!
579 typedef opt::none internal_node_builder;
583 /// Metafunction converting option list to \p SkipListSet traits
586 - \p opt::hook - hook used. Possible values are: \p skip_list::base_hook, \p skip_list::member_hook, \p skip_list::traits_hook.
587 If the option is not specified, <tt>skip_list::base_hook<></tt> and \p gc::HP is used.
588 - \p opt::compare - key comparison functor. No default functor is provided.
589 If the option is not specified, the \p opt::less is used.
590 - \p opt::less - specifies binary predicate used for key comparison. Default is \p std::less<T>.
591 - \p opt::disposer - the functor used for dispose removed items. Default is \p opt::v::empty_disposer. Due the nature
592 of GC schema the disposer may be called asynchronously.
593 - \p opt::item_counter - the type of item counting feature. Default is disabled, i.e. \p atomicity::empty_item_counter.
594 To enable it use \p atomicity::item_counter
595 - \p opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
596 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
597 - \p skip_list::random_level_generator - random level generator. Can be \p skip_list::xorshift,
598 \p skip_list::turbo_pascal (the default) or
599 user-provided one. See \p skip_list::random_level_generator option description for explanation.
600 - \p opt::allocator - although the skip-list is an intrusive container,
601 an allocator should be provided to maintain variable randomly-calculated height of the node
602 since the node can contain up to 32 next pointers. The allocator option is used to allocate an array of next pointers
603 for nodes which height is more than 1. Default is \ref CDS_DEFAULT_ALLOCATOR.
604 - \p opt::back_off - back-off strategy, default is \รง cds::backoff::Default.
605 - \p opt::stat - internal statistics. By default, it is disabled (\p skip_list::empty_stat).
606 To enable it use \p skip_list::stat
608 template <typename... Options>
610 # ifdef CDS_DOXYGEN_INVOKED
611 typedef implementation_defined type ; ///< Metafunction result
613 typedef typename cds::opt::make_options<
614 typename cds::opt::find_type_traits< traits, Options... >::type
622 template <typename Node>
623 class head_node: public Node
625 typedef Node node_type;
626 typename node_type::atomic_marked_ptr m_Tower[skip_list::c_nHeightLimit];
629 head_node( unsigned int nHeight )
631 for ( size_t i = 0; i < sizeof(m_Tower) / sizeof(m_Tower[0]); ++i )
632 m_Tower[i].store( typename node_type::marked_ptr(), atomics::memory_order_relaxed );
634 node_type::make_tower( nHeight, m_Tower );
637 node_type * head() const
639 return const_cast<node_type *>( static_cast<node_type const *>(this));
643 template <typename NodeType, typename AtomicNodePtr, typename Alloc>
644 struct intrusive_node_builder
646 typedef NodeType node_type;
647 typedef AtomicNodePtr atomic_node_ptr;
648 typedef Alloc allocator_type;
650 typedef cds::details::Allocator< atomic_node_ptr, allocator_type > tower_allocator;
652 template <typename RandomGen>
653 static node_type * make_tower( node_type * pNode, RandomGen& gen )
655 return make_tower( pNode, gen() + 1 );
658 static node_type * make_tower( node_type * pNode, unsigned int nHeight )
661 pNode->make_tower( nHeight, tower_allocator().NewArray( nHeight - 1, nullptr ) );
665 static void dispose_tower( node_type * pNode )
667 unsigned int nHeight = pNode->height();
669 tower_allocator().Delete( pNode->release_tower(), nHeight );
672 struct node_disposer {
673 void operator()( node_type * pNode )
675 dispose_tower( pNode );
680 // Forward declaration
681 template <class GC, typename NodeTraits, typename BackOff, bool IsConst>
684 } // namespace details
687 } // namespace skip_list
689 // Forward declaration
690 template <class GC, typename T, typename Traits = skip_list::traits >
693 }} // namespace cds::intrusive
695 #endif // #ifndef CDSLIB_INTRUSIVE_DETAILS_SKIP_LIST_BASE_H