3 #ifndef __CDS_INTRUSIVE_DETAILS_SKIP_LIST_BASE_H
4 #define __CDS_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
18 /// The maximum possible height of any skip-list
19 static unsigned int const c_nHeightLimit = 32;
24 - \p GC - garbage collector
25 - \p Tag - a \ref cds_intrusive_hook_tag "tag"
27 template <class GC, typename Tag = opt::none>
31 typedef GC gc; ///< Garbage collector
32 typedef Tag tag; ///< tag
34 typedef cds::details::marked_ptr<node, 1> marked_ptr; ///< marked pointer
35 typedef typename gc::template atomic_marked_ptr< marked_ptr> atomic_marked_ptr; ///< atomic marked pointer specific for GC
37 typedef atomic_marked_ptr tower_item_type;
41 atomic_marked_ptr m_pNext; ///< Next item in bottom-list (list at level 0)
42 unsigned int m_nHeight; ///< Node height (size of m_arrNext array). For node at level 0 the height is 1.
43 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
46 /// Constructs a node of height 1 (a bottom-list node)
50 , m_arrNext( nullptr )
53 /// Constructs a node of height \p nHeight
54 void make_tower( unsigned int nHeight, atomic_marked_ptr * nextTower )
56 assert( nHeight > 0 );
57 assert( (nHeight == 1 && nextTower == nullptr) // bottom-list node
58 || (nHeight > 1 && nextTower != nullptr) // node at level of more than 0
61 m_arrNext = nextTower;
66 atomic_marked_ptr * release_tower()
68 atomic_marked_ptr * pTower = m_arrNext;
74 atomic_marked_ptr * get_tower() const
80 /// Access to element of next pointer array
81 atomic_marked_ptr& next( unsigned int nLevel )
83 assert( nLevel < height() );
84 assert( nLevel == 0 || (nLevel > 0 && m_arrNext != nullptr) );
86 return nLevel ? m_arrNext[ nLevel - 1] : m_pNext;
89 /// Access to element of next pointer array (const version)
90 atomic_marked_ptr const& next( unsigned int nLevel ) const
92 assert( nLevel < height() );
93 assert( nLevel == 0 || nLevel > 0 && m_arrNext != nullptr );
95 return nLevel ? m_arrNext[ nLevel - 1] : m_pNext;
98 /// Access to element of next pointer array (same as \ref next function)
99 atomic_marked_ptr& operator[]( unsigned int nLevel )
101 return next( nLevel );
104 /// Access to element of next pointer array (same as \ref next function)
105 atomic_marked_ptr const& operator[]( unsigned int nLevel ) const
107 return next( nLevel );
110 /// Height of the node
111 unsigned int height() const
116 /// Clears internal links
119 assert( m_arrNext == nullptr );
120 m_pNext.store( marked_ptr(), atomics::memory_order_release );
124 bool is_cleared() const
126 return m_pNext == atomic_marked_ptr()
127 && m_arrNext == nullptr
135 struct default_hook {
136 typedef undefined_gc gc;
137 typedef opt::none tag;
142 template < typename HookType, typename... Options>
145 typedef typename opt::make_options< default_hook, Options...>::type options;
146 typedef typename options::gc gc;
147 typedef typename options::tag tag;
148 typedef node<gc, tag> node_type;
149 typedef HookType hook_type;
156 - \p opt::gc - garbage collector
157 - \p opt::tag - a \ref cds_intrusive_hook_tag "tag"
159 template < typename... Options >
160 struct base_hook: public hook< opt::base_hook_tag, Options... >
165 \p MemberOffset defines offset in bytes of \ref node member into your structure.
166 Use \p offsetof macro to define \p MemberOffset
169 - \p opt::gc - garbage collector
170 - \p opt::tag - a \ref cds_intrusive_hook_tag "tag"
172 template < size_t MemberOffset, typename... Options >
173 struct member_hook: public hook< opt::member_hook_tag, Options... >
176 static const size_t c_nMemberOffset = MemberOffset;
182 \p NodeTraits defines type traits for node.
183 See \ref node_traits for \p NodeTraits interface description
186 - \p opt::gc - garbage collector
187 - \p opt::tag - a \ref cds_intrusive_hook_tag "tag"
189 template <typename NodeTraits, typename... Options >
190 struct traits_hook: public hook< opt::traits_hook_tag, Options... >
193 typedef NodeTraits node_traits;
197 /// Option specifying random level generator
199 The random level generator is an important part of skip-list algorithm.
200 The node height in the skip-list have a probabilistic distribution
201 where half of the nodes that have level \p i pointers also have level <tt>i+1</tt> pointers
203 The random level generator should provide such distribution.
205 The \p Type functor interface is:
207 struct random_generator {
208 static unsigned int const c_nUpperBound = 32;
210 unsigned int operator()();
215 - \p c_nUpperBound - constant that specifies the upper bound of random number generated.
216 The generator produces a number from range <tt>[0 .. c_nUpperBound)</tt> (upper bound excluded).
217 \p c_nUpperBound must be no more than 32.
218 - <tt>random_generator()</tt> - the constructor of generator object initialises the generator instance (its internal state).
219 - <tt>unsigned int operator()()</tt> - the main generating function. Returns random level from range 0..31.
221 Stateful generators are supported.
223 Available \p Type implementations:
224 - \p skip_list::xorshift
225 - \p skip_list::turbo_pascal
227 template <typename Type>
228 struct random_level_generator {
230 template <typename Base>
231 struct pack: public Base
233 typedef Type random_level_generator;
238 /// Xor-shift random level generator
240 The simplest of the generators described in George
241 Marsaglia's "Xorshift RNGs" paper. This is not a high-quality
242 generator but is acceptable for skip-list.
244 The random generator should return numbers from range [0..31].
246 From Doug Lea's ConcurrentSkipListMap.java.
250 atomics::atomic<unsigned int> m_nSeed;
253 /// The upper bound of generator's return value. The generator produces random number in range <tt>[0..c_nUpperBound)</tt>
254 static unsigned int const c_nUpperBound = c_nHeightLimit;
256 /// Initializes the generator instance
259 m_nSeed.store( (unsigned int) cds::OS::Timer::random_seed(), atomics::memory_order_relaxed );
262 /// Main generator function
263 unsigned int operator()()
265 /* ConcurrentSkipListMap.java
266 private int randomLevel() {
270 randomSeed = x ^= x << 5;
271 if ((x & 0x80000001) != 0) // test highest and lowest bits
274 while (((x >>>= 1) & 1) != 0) ++level;
278 unsigned int x = m_nSeed.load( atomics::memory_order_relaxed );
282 m_nSeed.store( x, atomics::memory_order_relaxed );
283 unsigned int nLevel = ((x & 0x00000001) != 0) ? 0 : cds::bitop::LSB( (~(x >> 1)) & 0x7FFFFFFF );
284 assert( nLevel < c_nUpperBound );
289 /// Turbo-pascal random level generator
291 This uses a cheap pseudo-random function that was used in Turbo Pascal.
293 The random generator should return numbers from range [0..31].
295 From Doug Lea's ConcurrentSkipListMap.java.
300 atomics::atomic<unsigned int> m_nSeed;
303 /// The upper bound of generator's return value. The generator produces random number in range <tt>[0..c_nUpperBound)</tt>
304 static unsigned int const c_nUpperBound = c_nHeightLimit;
306 /// Initializes the generator instance
309 m_nSeed.store( (unsigned int) cds::OS::Timer::random_seed(), atomics::memory_order_relaxed );
312 /// Main generator function
313 unsigned int operator()()
316 private int randomLevel() {
319 randomSeed = r * 134775813 + 1;
321 while ((r <<= 1) > 0)
328 The low bits are apparently not very random (the original used only
329 upper 16 bits) so we traverse from highest bit down (i.e., test
330 sign), thus hardly ever use lower bits.
332 unsigned int x = m_nSeed.load( atomics::memory_order_relaxed ) * 134775813 + 1;
333 m_nSeed.store( x, atomics::memory_order_relaxed );
334 unsigned int nLevel = ( x & 0x80000000 ) ? (31 - cds::bitop::MSBnz( (x & 0x7FFFFFFF) | 1 )) : 0;
335 assert( nLevel < c_nUpperBound );
340 /// \p SkipListSet internal statistics
341 template <typename EventCounter = cds::atomicity::event_counter>
343 typedef EventCounter event_counter ; ///< Event counter type
345 event_counter m_nNodeHeightAdd[c_nHeightLimit] ; ///< Count of added node of each height
346 event_counter m_nNodeHeightDel[c_nHeightLimit] ; ///< Count of deleted node of each height
347 event_counter m_nInsertSuccess ; ///< Count of success insertion
348 event_counter m_nInsertFailed ; ///< Count of failed insertion
349 event_counter m_nInsertRetries ; ///< Count of unsuccessful retries of insertion
350 event_counter m_nEnsureExist ; ///< Count of \p ensure call for existed node
351 event_counter m_nEnsureNew ; ///< Count of \p ensure call for new node
352 event_counter m_nUnlinkSuccess ; ///< Count of successful call of \p unlink
353 event_counter m_nUnlinkFailed ; ///< Count of failed call of \p unlink
354 event_counter m_nEraseSuccess ; ///< Count of successful call of \p erase
355 event_counter m_nEraseFailed ; ///< Count of failed call of \p erase
356 event_counter m_nFindFastSuccess ; ///< Count of successful call of \p find and all derivatives (via fast-path)
357 event_counter m_nFindFastFailed ; ///< Count of failed call of \p find and all derivatives (via fast-path)
358 event_counter m_nFindSlowSuccess ; ///< Count of successful call of \p find and all derivatives (via slow-path)
359 event_counter m_nFindSlowFailed ; ///< Count of failed call of \p find and all derivatives (via slow-path)
360 event_counter m_nRenewInsertPosition ; ///< Count of renewing position events while inserting
361 event_counter m_nLogicDeleteWhileInsert ; ///< Count of events "The node has been logically deleted while inserting"
362 event_counter m_nNotFoundWhileInsert ; ///< Count of events "Inserting node is not found"
363 event_counter m_nFastErase ; ///< Fast erase event counter
364 event_counter m_nFastExtract ; ///< Fast extract event counter
365 event_counter m_nSlowErase ; ///< Slow erase event counter
366 event_counter m_nSlowExtract ; ///< Slow extract event counter
367 event_counter m_nExtractSuccess ; ///< Count of successful call of \p extract
368 event_counter m_nExtractFailed ; ///< Count of failed call of \p extract
369 event_counter m_nExtractRetries ; ///< Count of retries of \p extract call
370 event_counter m_nExtractMinSuccess ; ///< Count of successful call of \p extract_min
371 event_counter m_nExtractMinFailed ; ///< Count of failed call of \p extract_min
372 event_counter m_nExtractMinRetries ; ///< Count of retries of \p extract_min call
373 event_counter m_nExtractMaxSuccess ; ///< Count of successful call of \p extract_max
374 event_counter m_nExtractMaxFailed ; ///< Count of failed call of \p extract_max
375 event_counter m_nExtractMaxRetries ; ///< Count of retries of \p extract_max call
376 event_counter m_nEraseWhileFind ; ///< Count of erased item while searching
377 event_counter m_nExtractWhileFind ; ///< Count of extracted item while searching (RCU only)
380 void onAddNode( unsigned int nHeight )
382 assert( nHeight > 0 && nHeight <= sizeof(m_nNodeHeightAdd) / sizeof(m_nNodeHeightAdd[0]));
383 ++m_nNodeHeightAdd[nHeight - 1];
385 void onRemoveNode( unsigned int nHeight )
387 assert( nHeight > 0 && nHeight <= sizeof(m_nNodeHeightDel) / sizeof(m_nNodeHeightDel[0]));
388 ++m_nNodeHeightDel[nHeight - 1];
391 void onInsertSuccess() { ++m_nInsertSuccess ; }
392 void onInsertFailed() { ++m_nInsertFailed ; }
393 void onInsertRetry() { ++m_nInsertRetries ; }
394 void onEnsureExist() { ++m_nEnsureExist ; }
395 void onEnsureNew() { ++m_nEnsureNew ; }
396 void onUnlinkSuccess() { ++m_nUnlinkSuccess ; }
397 void onUnlinkFailed() { ++m_nUnlinkFailed ; }
398 void onEraseSuccess() { ++m_nEraseSuccess ; }
399 void onEraseFailed() { ++m_nEraseFailed ; }
400 void onFindFastSuccess() { ++m_nFindFastSuccess ; }
401 void onFindFastFailed() { ++m_nFindFastFailed ; }
402 void onFindSlowSuccess() { ++m_nFindSlowSuccess ; }
403 void onFindSlowFailed() { ++m_nFindSlowFailed ; }
404 void onEraseWhileFind() { ++m_nEraseWhileFind ; }
405 void onExtractWhileFind() { ++m_nExtractWhileFind ; }
406 void onRenewInsertPosition() { ++m_nRenewInsertPosition; }
407 void onLogicDeleteWhileInsert() { ++m_nLogicDeleteWhileInsert; }
408 void onNotFoundWhileInsert() { ++m_nNotFoundWhileInsert; }
409 void onFastErase() { ++m_nFastErase; }
410 void onFastExtract() { ++m_nFastExtract; }
411 void onSlowErase() { ++m_nSlowErase; }
412 void onSlowExtract() { ++m_nSlowExtract; }
413 void onExtractSuccess() { ++m_nExtractSuccess; }
414 void onExtractFailed() { ++m_nExtractFailed; }
415 void onExtractRetry() { ++m_nExtractRetries; }
416 void onExtractMinSuccess() { ++m_nExtractMinSuccess; }
417 void onExtractMinFailed() { ++m_nExtractMinFailed; }
418 void onExtractMinRetry() { ++m_nExtractMinRetries; }
419 void onExtractMaxSuccess() { ++m_nExtractMaxSuccess; }
420 void onExtractMaxFailed() { ++m_nExtractMaxFailed; }
421 void onExtractMaxRetry() { ++m_nExtractMaxRetries; }
426 /// \p SkipListSet empty internal statistics
429 void onAddNode( unsigned int /*nHeight*/ ) const {}
430 void onRemoveNode( unsigned int /*nHeight*/ ) const {}
431 void onInsertSuccess() const {}
432 void onInsertFailed() const {}
433 void onInsertRetry() const {}
434 void onEnsureExist() const {}
435 void onEnsureNew() const {}
436 void onUnlinkSuccess() const {}
437 void onUnlinkFailed() const {}
438 void onEraseSuccess() const {}
439 void onEraseFailed() const {}
440 void onFindFastSuccess() const {}
441 void onFindFastFailed() const {}
442 void onFindSlowSuccess() const {}
443 void onFindSlowFailed() const {}
444 void onEraseWhileFind() const {}
445 void onExtractWhileFind() const {}
446 void onRenewInsertPosition() const {}
447 void onLogicDeleteWhileInsert() const {}
448 void onNotFoundWhileInsert() const {}
449 void onFastErase() const {}
450 void onFastExtract() const {}
451 void onSlowErase() const {}
452 void onSlowExtract() const {}
453 void onExtractSuccess() const {}
454 void onExtractFailed() const {}
455 void onExtractRetry() const {}
456 void onExtractMinSuccess() const {}
457 void onExtractMinFailed() const {}
458 void onExtractMinRetry() const {}
459 void onExtractMaxSuccess() const {}
460 void onExtractMaxFailed() const {}
461 void onExtractMaxRetry() const {}
467 // For internal use only!!!
468 template <typename Type>
469 struct internal_node_builder {
470 template <typename Base>
471 struct pack: public Base
473 typedef Type internal_node_builder;
478 /// \p SkipListSet traits
483 Possible values are: \p skip_list::base_hook, \p skip_list::member_hook, \p skip_list::traits_hook.
485 typedef base_hook<> hook;
487 /// Key comparison functor
489 No default functor is provided. If the option is not specified, the \p less is used.
491 typedef opt::none compare;
493 /// specifies binary predicate used for key compare.
495 Default is \p std::less<T>.
497 typedef opt::none less;
501 The functor used for dispose removed items. Default is \p opt::v::empty_disposer.
503 typedef opt::v::empty_disposer disposer;
507 The type for item counting feature.
508 By default, item counting is disabled (\p atomicity::empty_item_counter)
509 \p atomicity::item_counter enables it.
511 typedef atomicity::empty_item_counter item_counter;
513 /// C++ memory ordering model
515 List of available memory ordering see \p opt::memory_model
517 typedef opt::v::relaxed_ordering memory_model;
519 /// Random level generator
521 The random level generator is an important part of skip-list algorithm.
522 The node height in the skip-list have a probabilistic distribution
523 where half of the nodes that have level \p i pointers also have level <tt>i+1</tt> pointers
524 (i = 0..30). So, the height of a node is in range [0..31].
526 See \p skip_list::random_level_generator option setter.
528 typedef turbo_pascal random_level_generator;
532 Although the skip-list is an intrusive container,
533 an allocator should be provided to maintain variable randomly-calculated height of the node
534 since the node can contain up to 32 next pointers.
535 The allocator specified is used to allocate an array of next pointers
536 for nodes which height is more than 1.
538 typedef CDS_DEFAULT_ALLOCATOR allocator;
540 /// back-off strategy
542 If the option is not specified, the \p cds::backoff::Default is used.
544 typedef cds::backoff::Default back_off;
546 /// Internal statistics
548 By default, internal statistics is disabled (\p skip_list::empty_stat).
549 Use \p skip_list::stat to enable it.
551 typedef empty_stat stat;
553 /// RCU deadlock checking policy (only for \ref cds_intrusive_SkipListSet_rcu "RCU-based SkipListSet")
555 List of available options see \p opt::rcu_check_deadlock
557 typedef opt::v::rcu_throw_deadlock rcu_check_deadlock;
560 // For internal use only!!!
561 typedef opt::none internal_node_builder;
565 /// Metafunction converting option list to \p SkipListSet traits
568 - \p opt::hook - hook used. Possible values are: \p skip_list::base_hook, \p skip_list::member_hook, \p skip_list::traits_hook.
569 If the option is not specified, <tt>skip_list::base_hook<></tt> and \p gc::HP is used.
570 - \p opt::compare - key comparison functor. No default functor is provided.
571 If the option is not specified, the \p opt::less is used.
572 - \p opt::less - specifies binary predicate used for key comparison. Default is \p std::less<T>.
573 - \p opt::disposer - the functor used for dispose removed items. Default is \p opt::v::empty_disposer. Due the nature
574 of GC schema the disposer may be called asynchronously.
575 - \p opt::item_counter - the type of item counting feature. Default is disabled, i.e. \p atomicity::empty_item_counter.
576 To enable it use \p atomicity::item_counter
577 - \p opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
578 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
579 - \p skip_list::random_level_generator - random level generator. Can be \p skip_list::xorshift,
580 \p skip_list::turbo_pascal (the default) or
581 user-provided one. See \p skip_list::random_level_generator option description for explanation.
582 - \p opt::allocator - although the skip-list is an intrusive container,
583 an allocator should be provided to maintain variable randomly-calculated height of the node
584 since the node can contain up to 32 next pointers. The allocator option is used to allocate an array of next pointers
585 for nodes which height is more than 1. Default is \ref CDS_DEFAULT_ALLOCATOR.
586 - \p opt::back_off - back-off strategy, default is \รง cds::backoff::Default.
587 - \p opt::stat - internal statistics. By default, it is disabled (\p skip_list::empty_stat).
588 To enable it use \p skip_list::stat
590 template <typename... Options>
592 # ifdef CDS_DOXYGEN_INVOKED
593 typedef implementation_defined type ; ///< Metafunction result
595 typedef typename cds::opt::make_options<
596 typename cds::opt::find_type_traits< traits, Options... >::type
604 template <typename Node>
605 class head_node: public Node
607 typedef Node node_type;
608 typename node_type::atomic_marked_ptr m_Tower[skip_list::c_nHeightLimit];
611 head_node( unsigned int nHeight )
613 for ( size_t i = 0; i < sizeof(m_Tower) / sizeof(m_Tower[0]); ++i )
614 m_Tower[i].store( typename node_type::marked_ptr(), atomics::memory_order_relaxed );
616 node_type::make_tower( nHeight, m_Tower );
619 node_type * head() const
621 return const_cast<node_type *>( static_cast<node_type const *>(this));
625 template <typename NodeType, typename AtomicNodePtr, typename Alloc>
626 struct intrusive_node_builder
628 typedef NodeType node_type;
629 typedef AtomicNodePtr atomic_node_ptr;
630 typedef Alloc allocator_type;
632 typedef cds::details::Allocator< atomic_node_ptr, allocator_type > tower_allocator;
634 template <typename RandomGen>
635 static node_type * make_tower( node_type * pNode, RandomGen& gen )
637 return make_tower( pNode, gen() + 1 );
640 static node_type * make_tower( node_type * pNode, unsigned int nHeight )
643 pNode->make_tower( nHeight, tower_allocator().NewArray( nHeight - 1, nullptr ) );
647 static void dispose_tower( node_type * pNode )
649 unsigned int nHeight = pNode->height();
651 tower_allocator().Delete( pNode->release_tower(), nHeight );
654 struct node_disposer {
655 void operator()( node_type * pNode )
657 dispose_tower( pNode );
662 // Forward declaration
663 template <class GC, typename NodeTraits, typename BackOff, bool IsConst>
666 } // namespace details
669 } // namespace skip_list
671 // Forward declaration
672 template <class GC, typename T, typename Traits = skip_list::traits >
675 }} // namespace cds::intrusive
677 #endif // #ifndef __CDS_INTRUSIVE_DETAILS_SKIP_LIST_BASE_H