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>
13 namespace cds { namespace intrusive {
14 /// SkipListSet related definitions
15 /** @ingroup cds_intrusive_helper
19 /// The maximum possible height of any skip-list
20 static unsigned int const c_nHeightLimit = 32;
25 - GC - garbage collector
26 - Tag - a tag used to distinguish between different implementation. An incomplete type may be used as a tag.
28 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
136 struct default_hook {
137 typedef undefined_gc gc;
138 typedef opt::none tag;
143 template < typename HookType, typename... Options>
146 typedef typename opt::make_options< default_hook, Options...>::type options;
147 typedef typename options::gc gc;
148 typedef typename options::tag tag;
149 typedef node<gc, tag> node_type;
150 typedef HookType hook_type;
157 - opt::gc - garbage collector used.
160 template < typename... Options >
161 struct base_hook: public hook< opt::base_hook_tag, Options... >
166 \p MemberOffset defines offset in bytes of \ref node member into your structure.
167 Use \p offsetof macro to define \p MemberOffset
170 - opt::gc - garbage collector used.
173 template < size_t MemberOffset, typename... Options >
174 struct member_hook: public hook< opt::member_hook_tag, Options... >
177 static const size_t c_nMemberOffset = MemberOffset;
183 \p NodeTraits defines type traits for node.
184 See \ref node_traits for \p NodeTraits interface description
187 - opt::gc - garbage collector used.
190 template <typename NodeTraits, typename... Options >
191 struct traits_hook: public hook< opt::traits_hook_tag, Options... >
194 typedef NodeTraits node_traits;
198 /// Option specifying random level generator
200 The random level generator is an important part of skip-list algorithm.
201 The node height in the skip-list have a probabilistic distribution
202 where half of the nodes that have level \p i pointers also have level <tt>i+1</tt> pointers
204 The random level generator should provide such distribution.
206 The \p Type functor interface is:
208 struct random_generator {
209 static unsigned int const c_nUpperBound = 32;
211 unsigned int operator()();
216 - \p c_nUpperBound - constant that specifies the upper bound of random number generated.
217 The generator produces a number from range <tt>[0 .. c_nUpperBound)</tt> (upper bound excluded).
218 \p c_nUpperBound must be no more than 32.
219 - <tt>random_generator()</tt> - the constructor of generator object initialises the generator instance (its internal state).
220 - <tt>unsigned int operator()()</tt> - the main generating function. Returns random level from range 0..31.
222 Stateful generators are supported.
224 Available \p Type implementations:
228 template <typename Type>
229 struct random_level_generator {
231 template <typename Base>
232 struct pack: public Base
234 typedef Type random_level_generator;
239 /// Xor-shift random level generator
241 The simplest of the generators described in George
242 Marsaglia's "Xorshift RNGs" paper. This is not a high-quality
243 generator but is acceptable for skip-list.
245 The random generator should return numbers from range [0..31].
247 From Doug Lea's ConcurrentSkipListMap.java.
251 atomics::atomic<unsigned int> m_nSeed;
254 /// The upper bound of generator's return value. The generator produces random number in range <tt>[0..c_nUpperBound)</tt>
255 static unsigned int const c_nUpperBound = c_nHeightLimit;
257 /// Initializes the generator instance
260 m_nSeed.store( (unsigned int) cds::OS::Timer::random_seed(), atomics::memory_order_relaxed );
263 /// Main generator function
264 unsigned int operator()()
266 /* ConcurrentSkipListMap.java
267 private int randomLevel() {
271 randomSeed = x ^= x << 5;
272 if ((x & 0x80000001) != 0) // test highest and lowest bits
275 while (((x >>>= 1) & 1) != 0) ++level;
279 unsigned int x = m_nSeed.load( atomics::memory_order_relaxed );
283 m_nSeed.store( x, atomics::memory_order_relaxed );
284 unsigned int nLevel = ((x & 0x00000001) != 0) ? 0 : cds::bitop::LSB( (~(x >> 1)) & 0x7FFFFFFF );
285 assert( nLevel < c_nUpperBound );
290 /// Turbo-pascal random level generator
292 This uses a cheap pseudo-random function that was used in Turbo Pascal.
294 The random generator should return numbers from range [0..31].
296 From Doug Lea's ConcurrentSkipListMap.java.
301 atomics::atomic<unsigned int> m_nSeed;
304 /// The upper bound of generator's return value. The generator produces random number in range <tt>[0..c_nUpperBound)</tt>
305 static unsigned int const c_nUpperBound = c_nHeightLimit;
307 /// Initializes the generator instance
310 m_nSeed.store( (unsigned int) cds::OS::Timer::random_seed(), atomics::memory_order_relaxed );
313 /// Main generator function
314 unsigned int operator()()
317 private int randomLevel() {
320 randomSeed = r * 134775813 + 1;
322 while ((r <<= 1) > 0)
329 The low bits are apparently not very random (the original used only
330 upper 16 bits) so we traverse from highest bit down (i.e., test
331 sign), thus hardly ever use lower bits.
333 unsigned int x = m_nSeed.load( atomics::memory_order_relaxed ) * 134775813 + 1;
334 m_nSeed.store( x, atomics::memory_order_relaxed );
335 unsigned int nLevel = ( x & 0x80000000 ) ? (31 - cds::bitop::MSBnz( (x & 0x7FFFFFFF) | 1 )) : 0;
336 assert( nLevel < c_nUpperBound );
341 /// SkipListSet internal statistics
342 template <typename EventCounter = cds::atomicity::event_counter>
344 typedef EventCounter event_counter ; ///< Event counter type
346 event_counter m_nNodeHeightAdd[c_nHeightLimit] ; ///< Count of added node of each height
347 event_counter m_nNodeHeightDel[c_nHeightLimit] ; ///< Count of deleted node of each height
348 event_counter m_nInsertSuccess ; ///< Count of success insertion
349 event_counter m_nInsertFailed ; ///< Count of failed insertion
350 event_counter m_nInsertRetries ; ///< Count of unsuccessful retries of insertion
351 event_counter m_nEnsureExist ; ///< Count of \p ensure call for existed node
352 event_counter m_nEnsureNew ; ///< Count of \p ensure call for new node
353 event_counter m_nUnlinkSuccess ; ///< Count of successful call of \p unlink
354 event_counter m_nUnlinkFailed ; ///< Count of failed call of \p unlink
355 event_counter m_nEraseSuccess ; ///< Count of successful call of \p erase
356 event_counter m_nEraseFailed ; ///< Count of failed call of \p erase
357 event_counter m_nFindFastSuccess ; ///< Count of successful call of \p find and all derivatives (via fast-path)
358 event_counter m_nFindFastFailed ; ///< Count of failed call of \p find and all derivatives (via fast-path)
359 event_counter m_nFindSlowSuccess ; ///< Count of successful call of \p find and all derivatives (via slow-path)
360 event_counter m_nFindSlowFailed ; ///< Count of failed call of \p find and all derivatives (via slow-path)
361 event_counter m_nRenewInsertPosition ; ///< Count of renewing position events while inserting
362 event_counter m_nLogicDeleteWhileInsert ; ///< Count of events "The node has been logically deleted while inserting"
363 event_counter m_nNotFoundWhileInsert ; ///< Count of events "Inserting node is not found"
364 event_counter m_nFastErase ; ///< Fast erase event counter
365 event_counter m_nFastExtract ; ///< Fast extract event counter
366 event_counter m_nSlowErase ; ///< Slow erase event counter
367 event_counter m_nSlowExtract ; ///< Slow extract event counter
368 event_counter m_nExtractSuccess ; ///< Count of successful call of \p extract
369 event_counter m_nExtractFailed ; ///< Count of failed call of \p extract
370 event_counter m_nExtractRetries ; ///< Count of retries of \p extract call
371 event_counter m_nExtractMinSuccess ; ///< Count of successful call of \p extract_min
372 event_counter m_nExtractMinFailed ; ///< Count of failed call of \p extract_min
373 event_counter m_nExtractMinRetries ; ///< Count of retries of \p extract_min call
374 event_counter m_nExtractMaxSuccess ; ///< Count of successful call of \p extract_max
375 event_counter m_nExtractMaxFailed ; ///< Count of failed call of \p extract_max
376 event_counter m_nExtractMaxRetries ; ///< Count of retries of \p extract_max call
377 event_counter m_nEraseWhileFind ; ///< Count of erased item while searching
378 event_counter m_nExtractWhileFind ; ///< Count of extracted item while searching (RCU only)
381 void onAddNode( unsigned int nHeight )
383 assert( nHeight > 0 && nHeight <= sizeof(m_nNodeHeightAdd) / sizeof(m_nNodeHeightAdd[0]));
384 ++m_nNodeHeightAdd[nHeight - 1];
386 void onRemoveNode( unsigned int nHeight )
388 assert( nHeight > 0 && nHeight <= sizeof(m_nNodeHeightDel) / sizeof(m_nNodeHeightDel[0]));
389 ++m_nNodeHeightDel[nHeight - 1];
392 void onInsertSuccess() { ++m_nInsertSuccess ; }
393 void onInsertFailed() { ++m_nInsertFailed ; }
394 void onInsertRetry() { ++m_nInsertRetries ; }
395 void onEnsureExist() { ++m_nEnsureExist ; }
396 void onEnsureNew() { ++m_nEnsureNew ; }
397 void onUnlinkSuccess() { ++m_nUnlinkSuccess ; }
398 void onUnlinkFailed() { ++m_nUnlinkFailed ; }
399 void onEraseSuccess() { ++m_nEraseSuccess ; }
400 void onEraseFailed() { ++m_nEraseFailed ; }
401 void onFindFastSuccess() { ++m_nFindFastSuccess ; }
402 void onFindFastFailed() { ++m_nFindFastFailed ; }
403 void onFindSlowSuccess() { ++m_nFindSlowSuccess ; }
404 void onFindSlowFailed() { ++m_nFindSlowFailed ; }
405 void onEraseWhileFind() { ++m_nEraseWhileFind ; }
406 void onExtractWhileFind() { ++m_nExtractWhileFind ; }
407 void onRenewInsertPosition() { ++m_nRenewInsertPosition; }
408 void onLogicDeleteWhileInsert() { ++m_nLogicDeleteWhileInsert; }
409 void onNotFoundWhileInsert() { ++m_nNotFoundWhileInsert; }
410 void onFastErase() { ++m_nFastErase; }
411 void onFastExtract() { ++m_nFastExtract; }
412 void onSlowErase() { ++m_nSlowErase; }
413 void onSlowExtract() { ++m_nSlowExtract; }
414 void onExtractSuccess() { ++m_nExtractSuccess; }
415 void onExtractFailed() { ++m_nExtractFailed; }
416 void onExtractRetry() { ++m_nExtractRetries; }
417 void onExtractMinSuccess() { ++m_nExtractMinSuccess; }
418 void onExtractMinFailed() { ++m_nExtractMinFailed; }
419 void onExtractMinRetry() { ++m_nExtractMinRetries; }
420 void onExtractMaxSuccess() { ++m_nExtractMaxSuccess; }
421 void onExtractMaxFailed() { ++m_nExtractMaxFailed; }
422 void onExtractMaxRetry() { ++m_nExtractMaxRetries; }
427 /// SkipListSet empty internal statistics
430 void onAddNode( unsigned int nHeight ) const {}
431 void onRemoveNode( unsigned int nHeight ) const {}
432 void onInsertSuccess() const {}
433 void onInsertFailed() const {}
434 void onInsertRetry() const {}
435 void onEnsureExist() const {}
436 void onEnsureNew() const {}
437 void onUnlinkSuccess() const {}
438 void onUnlinkFailed() const {}
439 void onEraseSuccess() const {}
440 void onEraseFailed() const {}
441 void onFindFastSuccess() const {}
442 void onFindFastFailed() const {}
443 void onFindSlowSuccess() const {}
444 void onFindSlowFailed() const {}
445 void onEraseWhileFind() const {}
446 void onExtractWhileFind() const {}
447 void onRenewInsertPosition() const {}
448 void onLogicDeleteWhileInsert() const {}
449 void onNotFoundWhileInsert() const {}
450 void onFastErase() const {}
451 void onFastExtract() const {}
452 void onSlowErase() const {}
453 void onSlowExtract() const {}
454 void onExtractSuccess() const {}
455 void onExtractFailed() const {}
456 void onExtractRetry() const {}
457 void onExtractMinSuccess() const {}
458 void onExtractMinFailed() const {}
459 void onExtractMinRetry() const {}
460 void onExtractMaxSuccess() const {}
461 void onExtractMaxFailed() const {}
462 void onExtractMaxRetry() const {}
468 // For internal use only!!!
469 template <typename Type>
470 struct internal_node_builder {
471 template <typename Base>
472 struct pack: public Base
474 typedef Type internal_node_builder;
479 /// Type traits for SkipListSet class
484 Possible values are: skip_list::base_hook, skip_list::member_hook, skip_list::traits_hook.
486 typedef base_hook<> hook;
488 /// Key comparison functor
490 No default functor is provided. If the option is not specified, the \p less is used.
492 typedef opt::none compare;
494 /// specifies binary predicate used for key compare.
496 Default is \p std::less<T>.
498 typedef opt::none less;
502 The functor used for dispose removed items. Default is opt::v::empty_disposer.
504 typedef opt::v::empty_disposer disposer;
508 The type for item counting feature.
509 Default is no item counter (\ref atomicity::empty_item_counter)
511 typedef atomicity::empty_item_counter item_counter;
513 /// C++ memory ordering model
515 List of available memory ordering see 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 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 used
542 If the option is not specified, the cds::backoff::Default is used.
544 typedef cds::backoff::Default back_off;
546 /// Internal statistics
547 typedef empty_stat stat;
549 /// RCU deadlock checking policy (only for \ref cds_intrusive_SkipListSet_rcu "RCU-based SkipListSet")
551 List of available options see opt::rcu_check_deadlock
553 typedef opt::v::rcu_throw_deadlock rcu_check_deadlock;
556 // For internal use only!!!
557 typedef opt::none internal_node_builder;
561 /// Metafunction converting option list to SkipListSet traits
563 This is a wrapper for <tt> cds::opt::make_options< type_traits, Options...> </tt>
564 \p Options list see \ref SkipListSet.
566 template <typename... Options>
568 # ifdef CDS_DOXYGEN_INVOKED
569 typedef implementation_defined type ; ///< Metafunction result
571 typedef typename cds::opt::make_options<
572 typename cds::opt::find_type_traits< type_traits, Options... >::type
580 template <typename Node>
581 class head_node: public Node
583 typedef Node node_type;
585 typename node_type::atomic_marked_ptr m_Tower[skip_list::c_nHeightLimit];
588 head_node( unsigned int nHeight )
590 for ( size_t i = 0; i < sizeof(m_Tower) / sizeof(m_Tower[0]); ++i )
591 m_Tower[i].store( typename node_type::marked_ptr(), atomics::memory_order_relaxed );
593 node_type::make_tower( nHeight, m_Tower );
596 node_type * head() const
598 return const_cast<node_type *>( static_cast<node_type const *>(this));
602 template <typename NodeType, typename AtomicNodePtr, typename Alloc>
603 struct intrusive_node_builder
605 typedef NodeType node_type;
606 typedef AtomicNodePtr atomic_node_ptr;
607 typedef Alloc allocator_type;
609 typedef cds::details::Allocator< atomic_node_ptr, allocator_type > tower_allocator;
611 template <typename RandomGen>
612 static node_type * make_tower( node_type * pNode, RandomGen& gen )
614 return make_tower( pNode, gen() + 1 );
617 static node_type * make_tower( node_type * pNode, unsigned int nHeight )
620 pNode->make_tower( nHeight, tower_allocator().NewArray( nHeight - 1, nullptr ) );
624 static void dispose_tower( node_type * pNode )
626 unsigned int nHeight = pNode->height();
628 tower_allocator().Delete( pNode->release_tower(), nHeight );
631 struct node_disposer {
632 void operator()( node_type * pNode )
634 dispose_tower( pNode );
639 // Forward declaration
640 template <class GC, typename NodeTraits, typename BackOff, bool IsConst>
643 } // namespace details
646 } // namespace skip_list
648 // Forward declaration
649 template <class GC, typename T, typename Traits = skip_list::type_traits >
652 }} // namespace cds::intrusive
654 #endif // #ifndef __CDS_INTRUSIVE_DETAILS_SKIP_LIST_BASE_H