2 This file is a part of libcds - Concurrent Data Structures library
4 (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016
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_SKIP_LIST_BASE_H
32 #define CDSLIB_INTRUSIVE_DETAILS_SKIP_LIST_BASE_H
34 #include <cds/intrusive/details/base.h>
35 #include <cds/details/marked_ptr.h>
36 #include <cds/algo/bitop.h>
37 #include <cds/os/timer.h>
38 #include <cds/urcu/options.h>
40 namespace cds { namespace intrusive {
41 /// SkipListSet related definitions
42 /** @ingroup cds_intrusive_helper
45 /// The maximum possible height of any skip-list
46 static unsigned int const c_nHeightLimit = 32;
51 - \p GC - garbage collector
52 - \p Tag - a \ref cds_intrusive_hook_tag "tag"
54 template <class GC, typename Tag = opt::none>
58 typedef GC gc; ///< Garbage collector
59 typedef Tag tag; ///< tag
61 typedef cds::details::marked_ptr<node, 1> marked_ptr; ///< marked pointer
62 typedef typename gc::template atomic_marked_ptr< marked_ptr> atomic_marked_ptr; ///< atomic marked pointer specific for GC
64 typedef atomic_marked_ptr tower_item_type;
68 atomic_marked_ptr m_pNext; ///< Next item in bottom-list (list at level 0)
69 unsigned int m_nHeight; ///< Node height (size of m_arrNext array). For node at level 0 the height is 1.
70 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
73 /// Constructs a node of height 1 (a bottom-list node)
77 , m_arrNext( nullptr )
80 /// Constructs a node of height \p nHeight
81 void make_tower( unsigned int nHeight, atomic_marked_ptr * nextTower )
83 assert( nHeight > 0 );
84 assert( (nHeight == 1 && nextTower == nullptr) // bottom-list node
85 || (nHeight > 1 && nextTower != nullptr) // node at level of more than 0
88 m_arrNext = nextTower;
90 atomics::atomic_thread_fence( atomics::memory_order_release );
94 atomic_marked_ptr * release_tower()
96 atomic_marked_ptr * pTower = m_arrNext;
102 atomic_marked_ptr * get_tower() const
107 bool has_tower() const
109 return m_nHeight > 1;
113 /// Access to element of next pointer array
114 atomic_marked_ptr& next( unsigned int nLevel )
116 assert( nLevel < height());
117 assert( nLevel == 0 || (nLevel > 0 && m_arrNext != nullptr));
119 return nLevel ? m_arrNext[ nLevel - 1] : m_pNext;
122 /// Access to element of next pointer array (const version)
123 atomic_marked_ptr const& next( unsigned int nLevel ) const
125 assert( nLevel < height());
126 assert( nLevel == 0 || nLevel > 0 && m_arrNext != nullptr );
128 return nLevel ? m_arrNext[ nLevel - 1] : m_pNext;
131 /// Access to element of next pointer array (synonym for \p next() function)
132 atomic_marked_ptr& operator[]( unsigned int nLevel )
134 return next( nLevel );
137 /// Access to element of next pointer array (synonym for \p next() function)
138 atomic_marked_ptr const& operator[]( unsigned int nLevel ) const
140 return next( nLevel );
143 /// Height of the node
144 unsigned int height() const
149 /// Clears internal links
152 assert( m_arrNext == nullptr );
153 m_pNext.store( marked_ptr(), atomics::memory_order_release );
157 bool is_cleared() const
159 return m_pNext == atomic_marked_ptr()
160 && m_arrNext == nullptr
168 struct default_hook {
169 typedef undefined_gc gc;
170 typedef opt::none tag;
175 template < typename HookType, typename... Options>
178 typedef typename opt::make_options< default_hook, Options...>::type options;
179 typedef typename options::gc gc;
180 typedef typename options::tag tag;
181 typedef node<gc, tag> node_type;
182 typedef HookType hook_type;
189 - \p opt::gc - garbage collector
190 - \p opt::tag - a \ref cds_intrusive_hook_tag "tag"
192 template < typename... Options >
193 struct base_hook: public hook< opt::base_hook_tag, Options... >
198 \p MemberOffset defines offset in bytes of \ref node member into your structure.
199 Use \p offsetof macro to define \p MemberOffset
202 - \p opt::gc - garbage collector
203 - \p opt::tag - a \ref cds_intrusive_hook_tag "tag"
205 template < size_t MemberOffset, typename... Options >
206 struct member_hook: public hook< opt::member_hook_tag, Options... >
209 static const size_t c_nMemberOffset = MemberOffset;
215 \p NodeTraits defines type traits for node.
216 See \ref node_traits for \p NodeTraits interface description
219 - \p opt::gc - garbage collector
220 - \p opt::tag - a \ref cds_intrusive_hook_tag "tag"
222 template <typename NodeTraits, typename... Options >
223 struct traits_hook: public hook< opt::traits_hook_tag, Options... >
226 typedef NodeTraits node_traits;
230 /// Option specifying random level generator
232 The random level generator is an important part of skip-list algorithm.
233 The node height in the skip-list have a probabilistic distribution
234 where half of the nodes that have level \p i pointers also have level <tt>i+1</tt> pointers
236 The random level generator should provide such distribution.
238 The \p Type functor interface is:
240 struct random_generator {
241 static unsigned int const c_nUpperBound = 32;
243 unsigned int operator()();
248 - \p c_nUpperBound - constant that specifies the upper bound of random number generated.
249 The generator produces a number from range <tt>[0 .. c_nUpperBound)</tt> (upper bound excluded).
250 \p c_nUpperBound must be no more than 32.
251 - <tt>random_generator()</tt> - the constructor of generator object initialises the generator instance (its internal state).
252 - <tt>unsigned int operator()()</tt> - the main generating function. Returns random level from range 0..31.
254 Stateful generators are supported.
256 Available \p Type implementations:
257 - \p skip_list::xorshift
258 - \p skip_list::turbo_pascal
260 template <typename Type>
261 struct random_level_generator {
263 template <typename Base>
264 struct pack: public Base
266 typedef Type random_level_generator;
271 /// Xor-shift random level generator
273 The simplest of the generators described in George
274 Marsaglia's "Xorshift RNGs" paper. This is not a high-quality
275 generator but is acceptable for skip-list.
277 The random generator should return numbers from range [0..31].
279 From Doug Lea's ConcurrentSkipListMap.java.
283 atomics::atomic<unsigned int> m_nSeed;
286 /// The upper bound of generator's return value. The generator produces random number in range <tt>[0..c_nUpperBound)</tt>
287 static unsigned int const c_nUpperBound = c_nHeightLimit;
289 /// Initializes the generator instance
292 m_nSeed.store( (unsigned int) cds::OS::Timer::random_seed(), atomics::memory_order_relaxed );
295 /// Main generator function
296 unsigned int operator()()
298 /* ConcurrentSkipListMap.java
299 private int randomLevel() {
303 randomSeed = x ^= x << 5;
304 if ((x & 0x80000001) != 0) // test highest and lowest bits
307 while (((x >>>= 1) & 1) != 0) ++level;
311 unsigned int x = m_nSeed.load( atomics::memory_order_relaxed );
315 m_nSeed.store( x, atomics::memory_order_relaxed );
316 unsigned int nLevel = ((x & 0x00000001) != 0) ? 0 : cds::bitop::LSB( (~(x >> 1)) & 0x7FFFFFFF );
317 assert( nLevel < c_nUpperBound );
322 /// Turbo-pascal random level generator
324 This uses a cheap pseudo-random function that was used in Turbo Pascal.
326 The random generator should return numbers from range [0..31].
328 From Doug Lea's ConcurrentSkipListMap.java.
333 atomics::atomic<unsigned int> m_nSeed;
336 /// The upper bound of generator's return value. The generator produces random number in range <tt>[0..c_nUpperBound)</tt>
337 static unsigned int const c_nUpperBound = c_nHeightLimit;
339 /// Initializes the generator instance
342 m_nSeed.store( (unsigned int) cds::OS::Timer::random_seed(), atomics::memory_order_relaxed );
345 /// Main generator function
346 unsigned int operator()()
349 private int randomLevel() {
352 randomSeed = r * 134775813 + 1;
354 while ((r <<= 1) > 0)
361 The low bits are apparently not very random (the original used only
362 upper 16 bits) so we traverse from highest bit down (i.e., test
363 sign), thus hardly ever use lower bits.
365 unsigned int x = m_nSeed.load( atomics::memory_order_relaxed ) * 134775813 + 1;
366 m_nSeed.store( x, atomics::memory_order_relaxed );
367 unsigned int nLevel = ( x & 0x80000000 ) ? (31 - cds::bitop::MSBnz( (x & 0x7FFFFFFF) | 1 )) : 0;
368 assert( nLevel < c_nUpperBound );
373 /// \p SkipListSet internal statistics
374 template <typename EventCounter = cds::atomicity::event_counter>
376 typedef EventCounter event_counter ; ///< Event counter type
378 event_counter m_nNodeHeightAdd[c_nHeightLimit] ; ///< Count of added node of each height
379 event_counter m_nNodeHeightDel[c_nHeightLimit] ; ///< Count of deleted node of each height
380 event_counter m_nInsertSuccess ; ///< Count of success insertion
381 event_counter m_nInsertFailed ; ///< Count of failed insertion
382 event_counter m_nInsertRetries ; ///< Count of unsuccessful retries of insertion
383 event_counter m_nUpdateExist ; ///< Count of \p update() call for existed node
384 event_counter m_nUpdateNew ; ///< Count of \p update() call for new node
385 event_counter m_nUnlinkSuccess ; ///< Count of successful call of \p unlink
386 event_counter m_nUnlinkFailed ; ///< Count of failed call of \p unlink
387 event_counter m_nEraseSuccess ; ///< Count of successful call of \p erase
388 event_counter m_nEraseFailed ; ///< Count of failed call of \p erase
389 event_counter m_nEraseRetry ; ///< Count of retries while erasing node
390 event_counter m_nFindFastSuccess ; ///< Count of successful call of \p find and all derivatives (via fast-path)
391 event_counter m_nFindFastFailed ; ///< Count of failed call of \p find and all derivatives (via fast-path)
392 event_counter m_nFindSlowSuccess ; ///< Count of successful call of \p find and all derivatives (via slow-path)
393 event_counter m_nFindSlowFailed ; ///< Count of failed call of \p find and all derivatives (via slow-path)
394 event_counter m_nRenewInsertPosition ; ///< Count of renewing position events while inserting
395 event_counter m_nLogicDeleteWhileInsert ; ///< Count of events "The node has been logically deleted while inserting"
396 event_counter m_nNotFoundWhileInsert ; ///< Count of events "Inserting node is not found"
397 event_counter m_nFastErase ; ///< Fast erase event counter
398 event_counter m_nFastExtract ; ///< Fast extract event counter
399 event_counter m_nSlowErase ; ///< Slow erase event counter
400 event_counter m_nSlowExtract ; ///< Slow extract event counter
401 event_counter m_nExtractSuccess ; ///< Count of successful call of \p extract
402 event_counter m_nExtractFailed ; ///< Count of failed call of \p extract
403 event_counter m_nExtractRetries ; ///< Count of retries of \p extract call
404 event_counter m_nExtractMinSuccess ; ///< Count of successful call of \p extract_min
405 event_counter m_nExtractMinFailed ; ///< Count of failed call of \p extract_min
406 event_counter m_nExtractMinRetries ; ///< Count of retries of \p extract_min call
407 event_counter m_nExtractMaxSuccess ; ///< Count of successful call of \p extract_max
408 event_counter m_nExtractMaxFailed ; ///< Count of failed call of \p extract_max
409 event_counter m_nExtractMaxRetries ; ///< Count of retries of \p extract_max call
410 event_counter m_nEraseWhileFind ; ///< Count of erased item while searching
411 event_counter m_nExtractWhileFind ; ///< Count of extracted item while searching (RCU only)
414 void onAddNode( unsigned int nHeight )
416 assert( nHeight > 0 && nHeight <= sizeof(m_nNodeHeightAdd) / sizeof(m_nNodeHeightAdd[0]));
417 ++m_nNodeHeightAdd[nHeight - 1];
419 void onRemoveNode( unsigned int nHeight )
421 assert( nHeight > 0 && nHeight <= sizeof(m_nNodeHeightDel) / sizeof(m_nNodeHeightDel[0]));
422 ++m_nNodeHeightDel[nHeight - 1];
425 void onInsertSuccess() { ++m_nInsertSuccess ; }
426 void onInsertFailed() { ++m_nInsertFailed ; }
427 void onInsertRetry() { ++m_nInsertRetries ; }
428 void onUpdateExist() { ++m_nUpdateExist ; }
429 void onUpdateNew() { ++m_nUpdateNew ; }
430 void onUnlinkSuccess() { ++m_nUnlinkSuccess ; }
431 void onUnlinkFailed() { ++m_nUnlinkFailed ; }
432 void onEraseSuccess() { ++m_nEraseSuccess ; }
433 void onEraseFailed() { ++m_nEraseFailed ; }
434 void onEraseRetry() { ++m_nEraseRetry; }
435 void onFindFastSuccess() { ++m_nFindFastSuccess ; }
436 void onFindFastFailed() { ++m_nFindFastFailed ; }
437 void onFindSlowSuccess() { ++m_nFindSlowSuccess ; }
438 void onFindSlowFailed() { ++m_nFindSlowFailed ; }
439 void onEraseWhileFind() { ++m_nEraseWhileFind ; }
440 void onExtractWhileFind() { ++m_nExtractWhileFind ; }
441 void onRenewInsertPosition() { ++m_nRenewInsertPosition; }
442 void onLogicDeleteWhileInsert() { ++m_nLogicDeleteWhileInsert; }
443 void onNotFoundWhileInsert() { ++m_nNotFoundWhileInsert; }
444 void onFastErase() { ++m_nFastErase; }
445 void onFastExtract() { ++m_nFastExtract; }
446 void onSlowErase() { ++m_nSlowErase; }
447 void onSlowExtract() { ++m_nSlowExtract; }
448 void onExtractSuccess() { ++m_nExtractSuccess; }
449 void onExtractFailed() { ++m_nExtractFailed; }
450 void onExtractRetry() { ++m_nExtractRetries; }
451 void onExtractMinSuccess() { ++m_nExtractMinSuccess; }
452 void onExtractMinFailed() { ++m_nExtractMinFailed; }
453 void onExtractMinRetry() { ++m_nExtractMinRetries; }
454 void onExtractMaxSuccess() { ++m_nExtractMaxSuccess; }
455 void onExtractMaxFailed() { ++m_nExtractMaxFailed; }
456 void onExtractMaxRetry() { ++m_nExtractMaxRetries; }
461 /// \p SkipListSet empty internal statistics
464 void onAddNode( unsigned int /*nHeight*/ ) const {}
465 void onRemoveNode( unsigned int /*nHeight*/ ) const {}
466 void onInsertSuccess() const {}
467 void onInsertFailed() const {}
468 void onInsertRetry() const {}
469 void onUpdateExist() const {}
470 void onUpdateNew() const {}
471 void onUnlinkSuccess() const {}
472 void onUnlinkFailed() const {}
473 void onEraseSuccess() const {}
474 void onEraseFailed() const {}
475 void onEraseRetry() const {}
476 void onFindFastSuccess() const {}
477 void onFindFastFailed() const {}
478 void onFindSlowSuccess() const {}
479 void onFindSlowFailed() const {}
480 void onEraseWhileFind() const {}
481 void onExtractWhileFind() const {}
482 void onRenewInsertPosition() const {}
483 void onLogicDeleteWhileInsert() const {}
484 void onNotFoundWhileInsert() const {}
485 void onFastErase() const {}
486 void onFastExtract() const {}
487 void onSlowErase() const {}
488 void onSlowExtract() const {}
489 void onExtractSuccess() const {}
490 void onExtractFailed() const {}
491 void onExtractRetry() const {}
492 void onExtractMinSuccess() const {}
493 void onExtractMinFailed() const {}
494 void onExtractMinRetry() const {}
495 void onExtractMaxSuccess() const {}
496 void onExtractMaxFailed() const {}
497 void onExtractMaxRetry() const {}
503 // For internal use only!!!
504 template <typename Type>
505 struct internal_node_builder {
506 template <typename Base>
507 struct pack: public Base
509 typedef Type internal_node_builder;
514 /// \p SkipListSet traits
519 Possible values are: \p skip_list::base_hook, \p skip_list::member_hook, \p skip_list::traits_hook.
521 typedef base_hook<> hook;
523 /// Key comparison functor
525 No default functor is provided. If the option is not specified, the \p less is used.
527 typedef opt::none compare;
529 /// specifies binary predicate used for key compare.
531 Default is \p std::less<T>.
533 typedef opt::none less;
537 The functor used for dispose removed items. Default is \p opt::v::empty_disposer.
539 typedef opt::v::empty_disposer disposer;
543 The type for item counting feature.
544 By default, item counting is disabled (\p atomicity::empty_item_counter),
545 \p atomicity::item_counter enables it.
547 typedef atomicity::empty_item_counter item_counter;
549 /// C++ memory ordering model
551 List of available memory ordering see \p opt::memory_model
553 typedef opt::v::relaxed_ordering memory_model;
555 /// Random level generator
557 The random level generator is an important part of skip-list algorithm.
558 The node height in the skip-list have a probabilistic distribution
559 where half of the nodes that have level \p i pointers also have level <tt>i+1</tt> pointers
560 (i = 0..30). So, the height of a node is in range [0..31].
562 See \p skip_list::random_level_generator option setter.
564 typedef turbo_pascal random_level_generator;
568 Although the skip-list is an intrusive container,
569 an allocator should be provided to maintain variable randomly-calculated height of the node
570 since the node can contain up to 32 next pointers.
571 The allocator specified is used to allocate an array of next pointers
572 for nodes which height is more than 1.
574 typedef CDS_DEFAULT_ALLOCATOR allocator;
576 /// back-off strategy
578 If the option is not specified, the \p cds::backoff::Default is used.
580 typedef cds::backoff::Default back_off;
582 /// Internal statistics
584 By default, internal statistics is disabled (\p skip_list::empty_stat).
585 Use \p skip_list::stat to enable it.
587 typedef empty_stat stat;
589 /// RCU deadlock checking policy (only for \ref cds_intrusive_SkipListSet_rcu "RCU-based SkipListSet")
591 List of available options see \p opt::rcu_check_deadlock
593 typedef opt::v::rcu_throw_deadlock rcu_check_deadlock;
596 // For internal use only!!!
597 typedef opt::none internal_node_builder;
601 /// Metafunction converting option list to \p SkipListSet traits
604 - \p opt::hook - hook used. Possible values are: \p skip_list::base_hook, \p skip_list::member_hook, \p skip_list::traits_hook.
605 If the option is not specified, <tt>skip_list::base_hook<></tt> and \p gc::HP is used.
606 - \p opt::compare - key comparison functor. No default functor is provided.
607 If the option is not specified, the \p opt::less is used.
608 - \p opt::less - specifies binary predicate used for key comparison. Default is \p std::less<T>.
609 - \p opt::disposer - the functor used for dispose removed items. Default is \p opt::v::empty_disposer. Due the nature
610 of GC schema the disposer may be called asynchronously.
611 - \p opt::item_counter - the type of item counting feature. Default is disabled, i.e. \p atomicity::empty_item_counter.
612 To enable it use \p atomicity::item_counter
613 - \p opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
614 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
615 - \p skip_list::random_level_generator - random level generator. Can be \p skip_list::xorshift,
616 \p skip_list::turbo_pascal (the default) or
617 user-provided one. See \p skip_list::random_level_generator option description for explanation.
618 - \p opt::allocator - although the skip-list is an intrusive container,
619 an allocator should be provided to maintain variable randomly-calculated height of the node
620 since the node can contain up to 32 next pointers. The allocator option is used to allocate an array of next pointers
621 for nodes which height is more than 1. Default is \ref CDS_DEFAULT_ALLOCATOR.
622 - \p opt::back_off - back-off strategy, default is \p cds::backoff::Default.
623 - \p opt::stat - internal statistics. By default, it is disabled (\p skip_list::empty_stat).
624 To enable it use \p skip_list::stat
626 template <typename... Options>
628 # ifdef CDS_DOXYGEN_INVOKED
629 typedef implementation_defined type ; ///< Metafunction result
631 typedef typename cds::opt::make_options<
632 typename cds::opt::find_type_traits< traits, Options... >::type
640 template <typename Node>
641 class head_node: public Node
643 typedef Node node_type;
644 typename node_type::atomic_marked_ptr m_Tower[skip_list::c_nHeightLimit];
647 head_node( unsigned int nHeight )
649 for ( size_t i = 0; i < sizeof(m_Tower) / sizeof(m_Tower[0]); ++i )
650 m_Tower[i].store( typename node_type::marked_ptr(), atomics::memory_order_relaxed );
652 node_type::make_tower( nHeight, m_Tower );
655 node_type * head() const
657 return const_cast<node_type *>( static_cast<node_type const *>(this));
661 template <typename NodeType, typename AtomicNodePtr, typename Alloc>
662 struct intrusive_node_builder
664 typedef NodeType node_type;
665 typedef AtomicNodePtr atomic_node_ptr;
666 typedef Alloc allocator_type;
668 typedef cds::details::Allocator< atomic_node_ptr, allocator_type > tower_allocator;
670 template <typename RandomGen>
671 static node_type * make_tower( node_type * pNode, RandomGen& gen )
673 return make_tower( pNode, gen() + 1 );
676 static node_type * make_tower( node_type * pNode, unsigned int nHeight )
679 pNode->make_tower( nHeight, tower_allocator().NewArray( nHeight - 1, nullptr ));
683 static void dispose_tower( node_type * pNode )
685 unsigned int nHeight = pNode->height();
687 tower_allocator().Delete( pNode->release_tower(), nHeight );
690 struct node_disposer {
691 void operator()( node_type * pNode )
693 dispose_tower( pNode );
698 // Forward declaration
699 template <class GC, typename NodeTraits, typename BackOff, bool IsConst>
702 } // namespace details
705 } // namespace skip_list
707 // Forward declaration
708 template <class GC, typename T, typename Traits = skip_list::traits >
711 }} // namespace cds::intrusive
713 #endif // #ifndef CDSLIB_INTRUSIVE_DETAILS_SKIP_LIST_BASE_H