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_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;
70 atomic_marked_ptr m_pNext; ///< Next item in bottom-list (list at level 0)
71 unsigned int m_nHeight; ///< Node height (size of \p m_arrNext array). For node at level 0 the height is 1.
72 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 atomics::atomic<unsigned int> m_nUnlink; ///< Unlink helper
80 , m_arrNext( nullptr )
82 m_nUnlink.store( 1, atomics::memory_order_release );
86 /// Constructs a node's tower of height \p nHeight
87 void make_tower( unsigned int nHeight, atomic_marked_ptr * nextTower )
89 assert( nHeight > 0 );
90 assert( (nHeight == 1 && nextTower == nullptr) // bottom-list node
91 || (nHeight > 1 && nextTower != nullptr) // node at level of more than 0
94 m_arrNext = nextTower;
96 m_nUnlink.store( nHeight, atomics::memory_order_release );
100 atomic_marked_ptr * release_tower()
102 atomic_marked_ptr * pTower = m_arrNext;
108 atomic_marked_ptr * get_tower() const
113 bool has_tower() const
115 return m_nHeight > 1;
119 /// Access to element of next pointer array
120 atomic_marked_ptr& next( unsigned int nLevel )
122 assert( nLevel < height());
123 assert( nLevel == 0 || (nLevel > 0 && m_arrNext != nullptr));
126 // TSan: data race between m_arrNext[ nLevel - 1 ] and make_tower()
127 // In fact, m_arrNext is a const array that is never changed
128 CDS_TSAN_ANNOTATE_HAPPENS_BEFORE( &m_arrNext[ nLevel - 1 ] );
129 return m_arrNext[nLevel - 1];
134 /// Access to element of next pointer array (const version)
135 atomic_marked_ptr const& next( unsigned int nLevel ) const
137 assert( nLevel < height());
138 assert( nLevel == 0 || nLevel > 0 && m_arrNext != nullptr );
141 CDS_TSAN_ANNOTATE_HAPPENS_BEFORE( &m_arrNext[nLevel - 1] );
142 return m_arrNext[nLevel - 1];
147 /// Access to element of next pointer array (synonym for \p next() function)
148 atomic_marked_ptr& operator[]( unsigned int nLevel )
150 return next( nLevel );
153 /// Access to element of next pointer array (synonym for \p next() function)
154 atomic_marked_ptr const& operator[]( unsigned int nLevel ) const
156 return next( nLevel );
159 /// Height of the node
160 unsigned int height() const
165 /// Clears internal links
168 assert( m_arrNext == nullptr );
169 m_pNext.store( marked_ptr(), atomics::memory_order_release );
173 bool is_cleared() const
175 return m_pNext == atomic_marked_ptr()
176 && m_arrNext == nullptr
180 bool level_unlinked( unsigned nCount = 1 )
182 return m_nUnlink.fetch_sub( nCount, atomics::memory_order_relaxed ) == 1;
185 bool is_upper_level( unsigned nLevel ) const
187 return m_nUnlink.load( atomics::memory_order_relaxed ) == nLevel + 1;
194 struct default_hook {
195 typedef undefined_gc gc;
196 typedef opt::none tag;
201 template < typename HookType, typename... Options>
204 typedef typename opt::make_options< default_hook, Options...>::type options;
205 typedef typename options::gc gc;
206 typedef typename options::tag tag;
207 typedef node<gc, tag> node_type;
208 typedef HookType hook_type;
215 - \p opt::gc - garbage collector
216 - \p opt::tag - a \ref cds_intrusive_hook_tag "tag"
218 template < typename... Options >
219 struct base_hook: public hook< opt::base_hook_tag, Options... >
224 \p MemberOffset defines offset in bytes of \ref node member into your structure.
225 Use \p offsetof macro to define \p MemberOffset
228 - \p opt::gc - garbage collector
229 - \p opt::tag - a \ref cds_intrusive_hook_tag "tag"
231 template < size_t MemberOffset, typename... Options >
232 struct member_hook: public hook< opt::member_hook_tag, Options... >
235 static const size_t c_nMemberOffset = MemberOffset;
241 \p NodeTraits defines type traits for node.
242 See \ref node_traits for \p NodeTraits interface description
245 - \p opt::gc - garbage collector
246 - \p opt::tag - a \ref cds_intrusive_hook_tag "tag"
248 template <typename NodeTraits, typename... Options >
249 struct traits_hook: public hook< opt::traits_hook_tag, Options... >
252 typedef NodeTraits node_traits;
256 /// Option specifying random level generator
258 The random level generator is an important part of skip-list algorithm.
259 The node height in the skip-list have a probabilistic distribution
260 where half of the nodes that have level \p i pointers also have level <tt>i+1</tt> pointers
262 The random level generator should provide such distribution.
264 The \p Type functor interface is:
266 struct random_generator {
267 static unsigned int const c_nUpperBound = 32;
269 unsigned int operator()();
274 - \p c_nUpperBound - constant that specifies the upper bound of random number generated.
275 The generator produces a number from range <tt>[0 .. c_nUpperBound)</tt> (upper bound excluded).
276 \p c_nUpperBound must be no more than 32.
277 - <tt>random_generator()</tt> - the constructor of generator object initialises the generator instance (its internal state).
278 - <tt>unsigned int operator()()</tt> - the main generating function. Returns random level from range <tt>[0 .. c_nUpperBound - 1]</tt>
281 Stateful generators are supported.
283 Available \p Type implementations:
284 - \p skip_list::xor_shift
285 - \p skip_list::turbo
287 template <typename Type>
288 struct random_level_generator {
290 template <typename Base>
291 struct pack: public Base
293 typedef Type random_level_generator;
298 /// Xor-shift random level generator
300 The simplest of the generators described in George Marsaglia's "Xorshift RNGs" paper.
301 This is not a high-quality generator but is acceptable for skip-list.
303 The random generator should return numbers from range [0 .. MaxHeight - 1].
305 From Doug Lea's ConcurrentSkipListMap.java.
307 template <unsigned MaxHeight>
310 atomics::atomic<unsigned int> m_nSeed;
312 static_assert( MaxHeight > 1, "MaxHeight" );
313 static_assert( MaxHeight <= c_nHeightLimit, "MaxHeight is too large" );
314 static unsigned int const c_nBitMask = (1u << ( MaxHeight - 1 )) - 1;
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 = MaxHeight;
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()()
330 /* ConcurrentSkipListMap.java
331 private int randomLevel() {
335 randomSeed = x ^= x << 5;
336 if ((x & 0x80000001) != 0) // test highest and lowest bits
339 while (((x >>>= 1) & 1) != 0) ++level;
343 unsigned int x = m_nSeed.load( atomics::memory_order_relaxed );
347 m_nSeed.store( x, atomics::memory_order_relaxed );
348 unsigned int nLevel = ((x & 0x00000001) != 0) ? 0 : cds::bitop::LSB( (~(x >> 1)) & c_nBitMask );
350 assert( nLevel < c_nUpperBound );
355 /// Xor-shift random level generator, max height 32
356 typedef xor_shift<c_nHeightLimit> xorshift32;
359 // For backward compatibility
360 typedef xorshift32 xorshift;
363 /// \ref xor_shift generator, max height 24
364 typedef xor_shift< 24 > xorshift24;
366 /// \ref xor_shift generator, max height = 16
367 typedef xor_shift< 16 > xorshift16;
369 /// Turbo-pascal random level generator
371 This uses a cheap pseudo-random function that was used in Turbo Pascal.
373 The random generator should return numbers from range [0..31].
375 From Doug Lea's ConcurrentSkipListMap.java.
377 template <unsigned MaxHeight>
381 atomics::atomic<unsigned int> m_nSeed;
383 static_assert( MaxHeight > 1, "MaxHeight" );
384 static_assert( MaxHeight <= c_nHeightLimit, "MaxHeight is too large" );
385 static unsigned int const c_nBitMask = (1u << ( MaxHeight - 1 )) - 1;
388 /// The upper bound of generator's return value. The generator produces random number in range <tt>[0..c_nUpperBound)</tt>
389 static unsigned int const c_nUpperBound = MaxHeight;
391 /// Initializes the generator instance
394 m_nSeed.store( (unsigned int) cds::OS::Timer::random_seed(), atomics::memory_order_relaxed );
397 /// Main generator function
398 unsigned int operator()()
401 private int randomLevel() {
404 randomSeed = r * 134775813 + 1;
406 while ((r <<= 1) > 0)
413 The low bits are apparently not very random (the original used only
414 upper 16 bits) so we traverse from highest bit down (i.e., test
415 sign), thus hardly ever use lower bits.
417 unsigned int x = m_nSeed.load( atomics::memory_order_relaxed ) * 134775813 + 1;
418 m_nSeed.store( x, atomics::memory_order_relaxed );
419 unsigned int nLevel = ( x & 0x80000000 ) ? ( c_nUpperBound - 1 - cds::bitop::MSBnz( (x & c_nBitMask ) | 1 )) : 0;
421 assert( nLevel < c_nUpperBound );
426 /// Turbo-Pascal random level generator, max height 32
427 typedef turbo<c_nHeightLimit> turbo32;
430 // For backward compatibility
431 typedef turbo32 turbo_pascal;
434 /// Turbo-Pascal generator, max height 24
435 typedef turbo< 24 > turbo24;
437 /// Turbo-Pascal generator, max height 16
438 typedef turbo< 16 > turbo16;
440 /// \p SkipListSet internal statistics
441 template <typename EventCounter = cds::atomicity::event_counter>
443 typedef EventCounter event_counter ; ///< Event counter type
445 event_counter m_nNodeHeightAdd[c_nHeightLimit] ; ///< Count of added node of each height
446 event_counter m_nNodeHeightDel[c_nHeightLimit] ; ///< Count of deleted node of each height
447 event_counter m_nInsertSuccess ; ///< Count of success insertion
448 event_counter m_nInsertFailed ; ///< Count of failed insertion
449 event_counter m_nInsertRetries ; ///< Count of unsuccessful retries of insertion
450 event_counter m_nUpdateExist ; ///< Count of \p update() call for existed node
451 event_counter m_nUpdateNew ; ///< Count of \p update() call for new node
452 event_counter m_nUnlinkSuccess ; ///< Count of successful call of \p unlink
453 event_counter m_nUnlinkFailed ; ///< Count of failed call of \p unlink
454 event_counter m_nEraseSuccess ; ///< Count of successful call of \p erase
455 event_counter m_nEraseFailed ; ///< Count of failed call of \p erase
456 event_counter m_nEraseRetry ; ///< Count of retries while erasing node
457 event_counter m_nFindFastSuccess ; ///< Count of successful call of \p find and all derivatives (via fast-path)
458 event_counter m_nFindFastFailed ; ///< Count of failed call of \p find and all derivatives (via fast-path)
459 event_counter m_nFindSlowSuccess ; ///< Count of successful call of \p find and all derivatives (via slow-path)
460 event_counter m_nFindSlowFailed ; ///< Count of failed call of \p find and all derivatives (via slow-path)
461 event_counter m_nRenewInsertPosition ; ///< Count of renewing position events while inserting
462 event_counter m_nLogicDeleteWhileInsert; ///< Count of events "The node has been logically deleted while inserting"
463 event_counter m_nRemoveWhileInsert ; ///< Count of evnts "The node is removing while inserting"
464 event_counter m_nFastErase ; ///< Fast erase event counter
465 event_counter m_nFastExtract ; ///< Fast extract event counter
466 event_counter m_nSlowErase ; ///< Slow erase event counter
467 event_counter m_nSlowExtract ; ///< Slow extract event counter
468 event_counter m_nExtractSuccess ; ///< Count of successful call of \p extract
469 event_counter m_nExtractFailed ; ///< Count of failed call of \p extract
470 event_counter m_nExtractRetries ; ///< Count of retries of \p extract call
471 event_counter m_nExtractMinSuccess ; ///< Count of successful call of \p extract_min
472 event_counter m_nExtractMinFailed ; ///< Count of failed call of \p extract_min
473 event_counter m_nExtractMinRetries ; ///< Count of retries of \p extract_min call
474 event_counter m_nExtractMaxSuccess ; ///< Count of successful call of \p extract_max
475 event_counter m_nExtractMaxFailed ; ///< Count of failed call of \p extract_max
476 event_counter m_nExtractMaxRetries ; ///< Count of retries of \p extract_max call
477 event_counter m_nEraseWhileFind ; ///< Count of erased item while searching
478 event_counter m_nExtractWhileFind ; ///< Count of extracted item while searching (RCU only)
479 event_counter m_nMarkFailed ; ///< Count of failed node marking (logical deletion mark)
480 event_counter m_nEraseContention ; ///< Count of key erasing contention encountered
483 void onAddNode( unsigned int nHeight )
485 assert( nHeight > 0 && nHeight <= sizeof(m_nNodeHeightAdd) / sizeof(m_nNodeHeightAdd[0]));
486 ++m_nNodeHeightAdd[nHeight - 1];
488 void onRemoveNode( unsigned int nHeight )
490 assert( nHeight > 0 && nHeight <= sizeof(m_nNodeHeightDel) / sizeof(m_nNodeHeightDel[0]));
491 ++m_nNodeHeightDel[nHeight - 1];
494 void onInsertSuccess() { ++m_nInsertSuccess ; }
495 void onInsertFailed() { ++m_nInsertFailed ; }
496 void onInsertRetry() { ++m_nInsertRetries ; }
497 void onUpdateExist() { ++m_nUpdateExist ; }
498 void onUpdateNew() { ++m_nUpdateNew ; }
499 void onUnlinkSuccess() { ++m_nUnlinkSuccess ; }
500 void onUnlinkFailed() { ++m_nUnlinkFailed ; }
501 void onEraseSuccess() { ++m_nEraseSuccess ; }
502 void onEraseFailed() { ++m_nEraseFailed ; }
503 void onEraseRetry() { ++m_nEraseRetry; }
504 void onFindFastSuccess() { ++m_nFindFastSuccess ; }
505 void onFindFastFailed() { ++m_nFindFastFailed ; }
506 void onFindSlowSuccess() { ++m_nFindSlowSuccess ; }
507 void onFindSlowFailed() { ++m_nFindSlowFailed ; }
508 void onEraseWhileFind() { ++m_nEraseWhileFind ; }
509 void onExtractWhileFind() { ++m_nExtractWhileFind ; }
510 void onRenewInsertPosition() { ++m_nRenewInsertPosition; }
511 void onLogicDeleteWhileInsert() { ++m_nLogicDeleteWhileInsert; }
512 void onRemoveWhileInsert() { ++m_nRemoveWhileInsert; }
513 void onFastErase() { ++m_nFastErase; }
514 void onFastExtract() { ++m_nFastExtract; }
515 void onSlowErase() { ++m_nSlowErase; }
516 void onSlowExtract() { ++m_nSlowExtract; }
517 void onExtractSuccess() { ++m_nExtractSuccess; }
518 void onExtractFailed() { ++m_nExtractFailed; }
519 void onExtractRetry() { ++m_nExtractRetries; }
520 void onExtractMinSuccess() { ++m_nExtractMinSuccess; }
521 void onExtractMinFailed() { ++m_nExtractMinFailed; }
522 void onExtractMinRetry() { ++m_nExtractMinRetries; }
523 void onExtractMaxSuccess() { ++m_nExtractMaxSuccess; }
524 void onExtractMaxFailed() { ++m_nExtractMaxFailed; }
525 void onExtractMaxRetry() { ++m_nExtractMaxRetries; }
526 void onMarkFailed() { ++m_nMarkFailed; }
527 void onEraseContention() { ++m_nEraseContention; }
531 /// \p SkipListSet empty internal statistics
534 void onAddNode( unsigned int /*nHeight*/ ) const {}
535 void onRemoveNode( unsigned int /*nHeight*/ ) const {}
536 void onInsertSuccess() const {}
537 void onInsertFailed() const {}
538 void onInsertRetry() const {}
539 void onUpdateExist() const {}
540 void onUpdateNew() const {}
541 void onUnlinkSuccess() const {}
542 void onUnlinkFailed() const {}
543 void onEraseSuccess() const {}
544 void onEraseFailed() const {}
545 void onEraseRetry() const {}
546 void onFindFastSuccess() const {}
547 void onFindFastFailed() const {}
548 void onFindSlowSuccess() const {}
549 void onFindSlowFailed() const {}
550 void onEraseWhileFind() const {}
551 void onExtractWhileFind() const {}
552 void onRenewInsertPosition() const {}
553 void onLogicDeleteWhileInsert() const {}
554 void onRemoveWhileInsert() const {}
555 void onFastErase() const {}
556 void onFastExtract() const {}
557 void onSlowErase() const {}
558 void onSlowExtract() const {}
559 void onExtractSuccess() const {}
560 void onExtractFailed() const {}
561 void onExtractRetry() const {}
562 void onExtractMinSuccess() const {}
563 void onExtractMinFailed() const {}
564 void onExtractMinRetry() const {}
565 void onExtractMaxSuccess() const {}
566 void onExtractMaxFailed() const {}
567 void onExtractMaxRetry() const {}
568 void onMarkFailed() const {}
569 void onEraseContention() const {}
574 // For internal use only!!!
575 template <typename Type>
576 struct internal_node_builder {
577 template <typename Base>
578 struct pack: public Base
580 typedef Type internal_node_builder;
585 /// \p SkipListSet traits
590 Possible values are: \p skip_list::base_hook, \p skip_list::member_hook, \p skip_list::traits_hook.
592 typedef base_hook<> hook;
594 /// Key comparison functor
596 No default functor is provided. If the option is not specified, the \p less is used.
598 typedef opt::none compare;
600 /// specifies binary predicate used for key compare.
602 Default is \p std::less<T>.
604 typedef opt::none less;
608 The functor used for dispose removed items. Default is \p opt::v::empty_disposer.
610 typedef opt::v::empty_disposer disposer;
614 The type for item counting feature.
615 By default, item counting is disabled (\p atomicity::empty_item_counter),
616 \p atomicity::item_counter or \p atomicity::cache_friendly_item_counter enables it.
618 typedef atomicity::empty_item_counter item_counter;
620 /// C++ memory ordering model
622 List of available memory ordering see \p opt::memory_model
624 typedef opt::v::relaxed_ordering memory_model;
626 /// Random level generator
628 The random level generator is an important part of skip-list algorithm.
629 The node height in the skip-list have a probabilistic distribution
630 where half of the nodes that have level \p i pointers also have level <tt>i+1</tt> pointers
631 (i = 0..30). So, the height of a node is in range [0..31].
633 See \p skip_list::random_level_generator option setter.
635 typedef turbo32 random_level_generator;
639 Although the skip-list is an intrusive container,
640 an allocator should be provided to maintain variable randomly-calculated height of the node
641 since the node can contain up to 32 next pointers.
642 The allocator specified is used to allocate an array of next pointers
643 for nodes which height is more than 1.
645 typedef CDS_DEFAULT_ALLOCATOR allocator;
647 /// back-off strategy
649 If the option is not specified, the \p cds::backoff::Default is used.
651 typedef cds::backoff::Default back_off;
653 /// Internal statistics
655 By default, internal statistics is disabled (\p skip_list::empty_stat).
656 Use \p skip_list::stat to enable it.
658 typedef empty_stat stat;
660 /// RCU deadlock checking policy (only for \ref cds_intrusive_SkipListSet_rcu "RCU-based SkipListSet")
662 List of available options see \p opt::rcu_check_deadlock
664 typedef opt::v::rcu_throw_deadlock rcu_check_deadlock;
667 // For internal use only!!!
668 typedef opt::none internal_node_builder;
672 /// Metafunction converting option list to \p SkipListSet traits
675 - \p opt::hook - hook used. Possible values are: \p skip_list::base_hook, \p skip_list::member_hook, \p skip_list::traits_hook.
676 If the option is not specified, <tt>skip_list::base_hook<></tt> and \p gc::HP is used.
677 - \p opt::compare - key comparison functor. No default functor is provided.
678 If the option is not specified, the \p opt::less is used.
679 - \p opt::less - specifies binary predicate used for key comparison. Default is \p std::less<T>.
680 - \p opt::disposer - the functor used for dispose removed items. Default is \p opt::v::empty_disposer. Due the nature
681 of GC schema the disposer may be called asynchronously.
682 - \p opt::item_counter - the type of item counting feature. Default is disabled, i.e. \p atomicity::empty_item_counter.
683 To enable it use \p atomicity::item_counter or \p atomicity::cache_friendly_item_counter
684 - \p opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
685 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
686 - \p skip_list::random_level_generator - random level generator. Can be \p skip_list::xor_shift,
687 \p skip_list::turbo32 (the default) or user-provided one.
688 See \p skip_list::random_level_generator option description for explanation.
689 - \p opt::allocator - although the skip-list is an intrusive container,
690 an allocator should be provided to maintain variable randomly-calculated height of the node
691 since the node can contain up to 32 next pointers. The allocator option is used to allocate an array of next pointers
692 for nodes which height is more than 1. Default is \ref CDS_DEFAULT_ALLOCATOR.
693 - \p opt::back_off - back-off strategy, default is \p cds::backoff::Default.
694 - \p opt::stat - internal statistics. By default, it is disabled (\p skip_list::empty_stat).
695 To enable it use \p skip_list::stat
697 template <typename... Options>
699 # ifdef CDS_DOXYGEN_INVOKED
700 typedef implementation_defined type ; ///< Metafunction result
702 typedef typename cds::opt::make_options<
703 typename cds::opt::find_type_traits< traits, Options... >::type
711 template <typename Node>
712 class head_node: public Node
714 typedef Node node_type;
715 typename node_type::atomic_marked_ptr m_Tower[skip_list::c_nHeightLimit];
718 head_node( unsigned int nHeight )
720 for ( size_t i = 0; i < sizeof(m_Tower) / sizeof(m_Tower[0]); ++i )
721 m_Tower[i].store( typename node_type::marked_ptr(), atomics::memory_order_relaxed );
723 node_type::make_tower( nHeight, m_Tower );
726 node_type * head() const
728 return const_cast<node_type *>( static_cast<node_type const *>(this));
732 template <typename NodeType, typename AtomicNodePtr, typename Alloc>
733 struct intrusive_node_builder
735 typedef NodeType node_type;
736 typedef AtomicNodePtr atomic_node_ptr;
737 typedef Alloc allocator_type;
739 typedef cds::details::Allocator< atomic_node_ptr, allocator_type > tower_allocator;
741 template <typename RandomGen>
742 static node_type * make_tower( node_type * pNode, RandomGen& gen )
744 return make_tower( pNode, gen() + 1 );
747 static node_type * make_tower( node_type * pNode, unsigned int nHeight )
750 pNode->make_tower( nHeight, tower_allocator().NewArray( nHeight - 1, nullptr ));
754 static void dispose_tower( node_type * pNode )
756 unsigned int nHeight = pNode->height();
758 tower_allocator().Delete( pNode->release_tower(), nHeight );
761 struct node_disposer {
762 void operator()( node_type * pNode )
764 dispose_tower( pNode );
769 // Forward declaration
770 template <class GC, typename NodeTraits, typename BackOff, bool IsConst>
773 } // namespace details
776 } // namespace skip_list
778 // Forward declaration
779 template <class GC, typename T, typename Traits = skip_list::traits >
782 }} // namespace cds::intrusive
784 #endif // #ifndef CDSLIB_INTRUSIVE_DETAILS_SKIP_LIST_BASE_H