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 )
85 /// Constructs a node's tower of height \p nHeight
86 void make_tower( unsigned int nHeight, atomic_marked_ptr * nextTower )
88 assert( nHeight > 0 );
89 assert( (nHeight == 1 && nextTower == nullptr) // bottom-list node
90 || (nHeight > 1 && nextTower != nullptr) // node at level of more than 0
93 m_arrNext = nextTower;
95 m_nUnlink.store( nHeight, atomics::memory_order_relaxed );
99 atomic_marked_ptr * release_tower()
101 atomic_marked_ptr * pTower = m_arrNext;
107 atomic_marked_ptr * get_tower() const
112 bool has_tower() const
114 return m_nHeight > 1;
118 /// Access to element of next pointer array
119 atomic_marked_ptr& next( unsigned int nLevel )
121 assert( nLevel < height());
122 assert( nLevel == 0 || (nLevel > 0 && m_arrNext != nullptr));
124 return nLevel ? m_arrNext[ nLevel - 1] : m_pNext;
127 /// Access to element of next pointer array (const version)
128 atomic_marked_ptr const& next( unsigned int nLevel ) const
130 assert( nLevel < height());
131 assert( nLevel == 0 || nLevel > 0 && m_arrNext != nullptr );
133 return nLevel ? m_arrNext[ nLevel - 1] : m_pNext;
136 /// Access to element of next pointer array (synonym for \p next() function)
137 atomic_marked_ptr& operator[]( unsigned int nLevel )
139 return next( nLevel );
142 /// Access to element of next pointer array (synonym for \p next() function)
143 atomic_marked_ptr const& operator[]( unsigned int nLevel ) const
145 return next( nLevel );
148 /// Height of the node
149 unsigned int height() const
154 /// Clears internal links
157 assert( m_arrNext == nullptr );
158 m_pNext.store( marked_ptr(), atomics::memory_order_release );
162 bool is_cleared() const
164 return m_pNext == atomic_marked_ptr()
165 && m_arrNext == nullptr
169 bool level_unlinked( unsigned nCount = 1 )
171 return m_nUnlink.fetch_sub( nCount, atomics::memory_order_relaxed ) == 1;
174 bool is_upper_level( unsigned nLevel ) const
176 return m_nUnlink.load( atomics::memory_order_relaxed ) == nLevel + 1;
183 struct default_hook {
184 typedef undefined_gc gc;
185 typedef opt::none tag;
190 template < typename HookType, typename... Options>
193 typedef typename opt::make_options< default_hook, Options...>::type options;
194 typedef typename options::gc gc;
195 typedef typename options::tag tag;
196 typedef node<gc, tag> node_type;
197 typedef HookType hook_type;
204 - \p opt::gc - garbage collector
205 - \p opt::tag - a \ref cds_intrusive_hook_tag "tag"
207 template < typename... Options >
208 struct base_hook: public hook< opt::base_hook_tag, Options... >
213 \p MemberOffset defines offset in bytes of \ref node member into your structure.
214 Use \p offsetof macro to define \p MemberOffset
217 - \p opt::gc - garbage collector
218 - \p opt::tag - a \ref cds_intrusive_hook_tag "tag"
220 template < size_t MemberOffset, typename... Options >
221 struct member_hook: public hook< opt::member_hook_tag, Options... >
224 static const size_t c_nMemberOffset = MemberOffset;
230 \p NodeTraits defines type traits for node.
231 See \ref node_traits for \p NodeTraits interface description
234 - \p opt::gc - garbage collector
235 - \p opt::tag - a \ref cds_intrusive_hook_tag "tag"
237 template <typename NodeTraits, typename... Options >
238 struct traits_hook: public hook< opt::traits_hook_tag, Options... >
241 typedef NodeTraits node_traits;
245 /// Option specifying random level generator
247 The random level generator is an important part of skip-list algorithm.
248 The node height in the skip-list have a probabilistic distribution
249 where half of the nodes that have level \p i pointers also have level <tt>i+1</tt> pointers
251 The random level generator should provide such distribution.
253 The \p Type functor interface is:
255 struct random_generator {
256 static unsigned int const c_nUpperBound = 32;
258 unsigned int operator()();
263 - \p c_nUpperBound - constant that specifies the upper bound of random number generated.
264 The generator produces a number from range <tt>[0 .. c_nUpperBound)</tt> (upper bound excluded).
265 \p c_nUpperBound must be no more than 32.
266 - <tt>random_generator()</tt> - the constructor of generator object initialises the generator instance (its internal state).
267 - <tt>unsigned int operator()()</tt> - the main generating function. Returns random level from range 0..31.
269 Stateful generators are supported.
271 Available \p Type implementations:
272 - \p skip_list::xorshift
273 - \p skip_list::turbo_pascal
275 template <typename Type>
276 struct random_level_generator {
278 template <typename Base>
279 struct pack: public Base
281 typedef Type random_level_generator;
286 /// Xor-shift random level generator
288 The simplest of the generators described in George
289 Marsaglia's "Xorshift RNGs" paper. This is not a high-quality
290 generator but is acceptable for skip-list.
292 The random generator should return numbers from range [0..31].
294 From Doug Lea's ConcurrentSkipListMap.java.
298 atomics::atomic<unsigned int> m_nSeed;
301 /// The upper bound of generator's return value. The generator produces random number in range <tt>[0..c_nUpperBound)</tt>
302 static unsigned int const c_nUpperBound = c_nHeightLimit;
304 /// Initializes the generator instance
307 m_nSeed.store( (unsigned int) cds::OS::Timer::random_seed(), atomics::memory_order_relaxed );
310 /// Main generator function
311 unsigned int operator()()
313 /* ConcurrentSkipListMap.java
314 private int randomLevel() {
318 randomSeed = x ^= x << 5;
319 if ((x & 0x80000001) != 0) // test highest and lowest bits
322 while (((x >>>= 1) & 1) != 0) ++level;
326 unsigned int x = m_nSeed.load( atomics::memory_order_relaxed );
330 m_nSeed.store( x, atomics::memory_order_relaxed );
331 unsigned int nLevel = ((x & 0x00000001) != 0) ? 0 : cds::bitop::LSB( (~(x >> 1)) & 0x7FFFFFFF );
332 assert( nLevel < c_nUpperBound );
337 /// Turbo-pascal random level generator
339 This uses a cheap pseudo-random function that was used in Turbo Pascal.
341 The random generator should return numbers from range [0..31].
343 From Doug Lea's ConcurrentSkipListMap.java.
348 atomics::atomic<unsigned int> m_nSeed;
351 /// The upper bound of generator's return value. The generator produces random number in range <tt>[0..c_nUpperBound)</tt>
352 static unsigned int const c_nUpperBound = c_nHeightLimit;
354 /// Initializes the generator instance
357 m_nSeed.store( (unsigned int) cds::OS::Timer::random_seed(), atomics::memory_order_relaxed );
360 /// Main generator function
361 unsigned int operator()()
364 private int randomLevel() {
367 randomSeed = r * 134775813 + 1;
369 while ((r <<= 1) > 0)
376 The low bits are apparently not very random (the original used only
377 upper 16 bits) so we traverse from highest bit down (i.e., test
378 sign), thus hardly ever use lower bits.
380 unsigned int x = m_nSeed.load( atomics::memory_order_relaxed ) * 134775813 + 1;
381 m_nSeed.store( x, atomics::memory_order_relaxed );
382 unsigned int nLevel = ( x & 0x80000000 ) ? (31 - cds::bitop::MSBnz( (x & 0x7FFFFFFF) | 1 )) : 0;
383 assert( nLevel < c_nUpperBound );
388 /// \p SkipListSet internal statistics
389 template <typename EventCounter = cds::atomicity::event_counter>
391 typedef EventCounter event_counter ; ///< Event counter type
393 event_counter m_nNodeHeightAdd[c_nHeightLimit] ; ///< Count of added node of each height
394 event_counter m_nNodeHeightDel[c_nHeightLimit] ; ///< Count of deleted node of each height
395 event_counter m_nInsertSuccess ; ///< Count of success insertion
396 event_counter m_nInsertFailed ; ///< Count of failed insertion
397 event_counter m_nInsertRetries ; ///< Count of unsuccessful retries of insertion
398 event_counter m_nUpdateExist ; ///< Count of \p update() call for existed node
399 event_counter m_nUpdateNew ; ///< Count of \p update() call for new node
400 event_counter m_nUnlinkSuccess ; ///< Count of successful call of \p unlink
401 event_counter m_nUnlinkFailed ; ///< Count of failed call of \p unlink
402 event_counter m_nEraseSuccess ; ///< Count of successful call of \p erase
403 event_counter m_nEraseFailed ; ///< Count of failed call of \p erase
404 event_counter m_nEraseRetry ; ///< Count of retries while erasing node
405 event_counter m_nFindFastSuccess ; ///< Count of successful call of \p find and all derivatives (via fast-path)
406 event_counter m_nFindFastFailed ; ///< Count of failed call of \p find and all derivatives (via fast-path)
407 event_counter m_nFindSlowSuccess ; ///< Count of successful call of \p find and all derivatives (via slow-path)
408 event_counter m_nFindSlowFailed ; ///< Count of failed call of \p find and all derivatives (via slow-path)
409 event_counter m_nRenewInsertPosition ; ///< Count of renewing position events while inserting
410 event_counter m_nLogicDeleteWhileInsert; ///< Count of events "The node has been logically deleted while inserting"
411 event_counter m_nNotFoundWhileInsert ; ///< Count of events "Inserting node is not found"
412 event_counter m_nFastErase ; ///< Fast erase event counter
413 event_counter m_nFastExtract ; ///< Fast extract event counter
414 event_counter m_nSlowErase ; ///< Slow erase event counter
415 event_counter m_nSlowExtract ; ///< Slow extract event counter
416 event_counter m_nExtractSuccess ; ///< Count of successful call of \p extract
417 event_counter m_nExtractFailed ; ///< Count of failed call of \p extract
418 event_counter m_nExtractRetries ; ///< Count of retries of \p extract call
419 event_counter m_nExtractMinSuccess ; ///< Count of successful call of \p extract_min
420 event_counter m_nExtractMinFailed ; ///< Count of failed call of \p extract_min
421 event_counter m_nExtractMinRetries ; ///< Count of retries of \p extract_min call
422 event_counter m_nExtractMaxSuccess ; ///< Count of successful call of \p extract_max
423 event_counter m_nExtractMaxFailed ; ///< Count of failed call of \p extract_max
424 event_counter m_nExtractMaxRetries ; ///< Count of retries of \p extract_max call
425 event_counter m_nEraseWhileFind ; ///< Count of erased item while searching
426 event_counter m_nExtractWhileFind ; ///< Count of extracted item while searching (RCU only)
427 event_counter m_nMarkFailed ; ///< Count of failed node marking (logical deletion mark)
428 event_counter m_nEraseContention ; ///< Count of key erasing contention encountered
431 void onAddNode( unsigned int nHeight )
433 assert( nHeight > 0 && nHeight <= sizeof(m_nNodeHeightAdd) / sizeof(m_nNodeHeightAdd[0]));
434 ++m_nNodeHeightAdd[nHeight - 1];
436 void onRemoveNode( unsigned int nHeight )
438 assert( nHeight > 0 && nHeight <= sizeof(m_nNodeHeightDel) / sizeof(m_nNodeHeightDel[0]));
439 ++m_nNodeHeightDel[nHeight - 1];
442 void onInsertSuccess() { ++m_nInsertSuccess ; }
443 void onInsertFailed() { ++m_nInsertFailed ; }
444 void onInsertRetry() { ++m_nInsertRetries ; }
445 void onUpdateExist() { ++m_nUpdateExist ; }
446 void onUpdateNew() { ++m_nUpdateNew ; }
447 void onUnlinkSuccess() { ++m_nUnlinkSuccess ; }
448 void onUnlinkFailed() { ++m_nUnlinkFailed ; }
449 void onEraseSuccess() { ++m_nEraseSuccess ; }
450 void onEraseFailed() { ++m_nEraseFailed ; }
451 void onEraseRetry() { ++m_nEraseRetry; }
452 void onFindFastSuccess() { ++m_nFindFastSuccess ; }
453 void onFindFastFailed() { ++m_nFindFastFailed ; }
454 void onFindSlowSuccess() { ++m_nFindSlowSuccess ; }
455 void onFindSlowFailed() { ++m_nFindSlowFailed ; }
456 void onEraseWhileFind() { ++m_nEraseWhileFind ; }
457 void onExtractWhileFind() { ++m_nExtractWhileFind ; }
458 void onRenewInsertPosition() { ++m_nRenewInsertPosition; }
459 void onLogicDeleteWhileInsert() { ++m_nLogicDeleteWhileInsert; }
460 void onNotFoundWhileInsert() { ++m_nNotFoundWhileInsert; }
461 void onFastErase() { ++m_nFastErase; }
462 void onFastExtract() { ++m_nFastExtract; }
463 void onSlowErase() { ++m_nSlowErase; }
464 void onSlowExtract() { ++m_nSlowExtract; }
465 void onExtractSuccess() { ++m_nExtractSuccess; }
466 void onExtractFailed() { ++m_nExtractFailed; }
467 void onExtractRetry() { ++m_nExtractRetries; }
468 void onExtractMinSuccess() { ++m_nExtractMinSuccess; }
469 void onExtractMinFailed() { ++m_nExtractMinFailed; }
470 void onExtractMinRetry() { ++m_nExtractMinRetries; }
471 void onExtractMaxSuccess() { ++m_nExtractMaxSuccess; }
472 void onExtractMaxFailed() { ++m_nExtractMaxFailed; }
473 void onExtractMaxRetry() { ++m_nExtractMaxRetries; }
474 void onMarkFailed() { ++m_nMarkFailed; }
475 void onEraseContention() { ++m_nEraseContention; }
479 /// \p SkipListSet empty internal statistics
482 void onAddNode( unsigned int /*nHeight*/ ) const {}
483 void onRemoveNode( unsigned int /*nHeight*/ ) const {}
484 void onInsertSuccess() const {}
485 void onInsertFailed() const {}
486 void onInsertRetry() const {}
487 void onUpdateExist() const {}
488 void onUpdateNew() const {}
489 void onUnlinkSuccess() const {}
490 void onUnlinkFailed() const {}
491 void onEraseSuccess() const {}
492 void onEraseFailed() const {}
493 void onEraseRetry() const {}
494 void onFindFastSuccess() const {}
495 void onFindFastFailed() const {}
496 void onFindSlowSuccess() const {}
497 void onFindSlowFailed() const {}
498 void onEraseWhileFind() const {}
499 void onExtractWhileFind() const {}
500 void onRenewInsertPosition() const {}
501 void onLogicDeleteWhileInsert() const {}
502 void onNotFoundWhileInsert() const {}
503 void onFastErase() const {}
504 void onFastExtract() const {}
505 void onSlowErase() const {}
506 void onSlowExtract() const {}
507 void onExtractSuccess() const {}
508 void onExtractFailed() const {}
509 void onExtractRetry() const {}
510 void onExtractMinSuccess() const {}
511 void onExtractMinFailed() const {}
512 void onExtractMinRetry() const {}
513 void onExtractMaxSuccess() const {}
514 void onExtractMaxFailed() const {}
515 void onExtractMaxRetry() const {}
516 void onMarkFailed() const {}
517 void onEraseContention() const {}
522 // For internal use only!!!
523 template <typename Type>
524 struct internal_node_builder {
525 template <typename Base>
526 struct pack: public Base
528 typedef Type internal_node_builder;
533 /// \p SkipListSet traits
538 Possible values are: \p skip_list::base_hook, \p skip_list::member_hook, \p skip_list::traits_hook.
540 typedef base_hook<> hook;
542 /// Key comparison functor
544 No default functor is provided. If the option is not specified, the \p less is used.
546 typedef opt::none compare;
548 /// specifies binary predicate used for key compare.
550 Default is \p std::less<T>.
552 typedef opt::none less;
556 The functor used for dispose removed items. Default is \p opt::v::empty_disposer.
558 typedef opt::v::empty_disposer disposer;
562 The type for item counting feature.
563 By default, item counting is disabled (\p atomicity::empty_item_counter),
564 \p atomicity::item_counter enables it.
566 typedef atomicity::empty_item_counter item_counter;
568 /// C++ memory ordering model
570 List of available memory ordering see \p opt::memory_model
572 typedef opt::v::relaxed_ordering memory_model;
574 /// Random level generator
576 The random level generator is an important part of skip-list algorithm.
577 The node height in the skip-list have a probabilistic distribution
578 where half of the nodes that have level \p i pointers also have level <tt>i+1</tt> pointers
579 (i = 0..30). So, the height of a node is in range [0..31].
581 See \p skip_list::random_level_generator option setter.
583 typedef turbo_pascal random_level_generator;
587 Although the skip-list is an intrusive container,
588 an allocator should be provided to maintain variable randomly-calculated height of the node
589 since the node can contain up to 32 next pointers.
590 The allocator specified is used to allocate an array of next pointers
591 for nodes which height is more than 1.
593 typedef CDS_DEFAULT_ALLOCATOR allocator;
595 /// back-off strategy
597 If the option is not specified, the \p cds::backoff::Default is used.
599 typedef cds::backoff::Default back_off;
601 /// Internal statistics
603 By default, internal statistics is disabled (\p skip_list::empty_stat).
604 Use \p skip_list::stat to enable it.
606 typedef empty_stat stat;
608 /// RCU deadlock checking policy (only for \ref cds_intrusive_SkipListSet_rcu "RCU-based SkipListSet")
610 List of available options see \p opt::rcu_check_deadlock
612 typedef opt::v::rcu_throw_deadlock rcu_check_deadlock;
615 // For internal use only!!!
616 typedef opt::none internal_node_builder;
620 /// Metafunction converting option list to \p SkipListSet traits
623 - \p opt::hook - hook used. Possible values are: \p skip_list::base_hook, \p skip_list::member_hook, \p skip_list::traits_hook.
624 If the option is not specified, <tt>skip_list::base_hook<></tt> and \p gc::HP is used.
625 - \p opt::compare - key comparison functor. No default functor is provided.
626 If the option is not specified, the \p opt::less is used.
627 - \p opt::less - specifies binary predicate used for key comparison. Default is \p std::less<T>.
628 - \p opt::disposer - the functor used for dispose removed items. Default is \p opt::v::empty_disposer. Due the nature
629 of GC schema the disposer may be called asynchronously.
630 - \p opt::item_counter - the type of item counting feature. Default is disabled, i.e. \p atomicity::empty_item_counter.
631 To enable it use \p atomicity::item_counter
632 - \p opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
633 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
634 - \p skip_list::random_level_generator - random level generator. Can be \p skip_list::xorshift,
635 \p skip_list::turbo_pascal (the default) or
636 user-provided one. See \p skip_list::random_level_generator option description for explanation.
637 - \p opt::allocator - although the skip-list is an intrusive container,
638 an allocator should be provided to maintain variable randomly-calculated height of the node
639 since the node can contain up to 32 next pointers. The allocator option is used to allocate an array of next pointers
640 for nodes which height is more than 1. Default is \ref CDS_DEFAULT_ALLOCATOR.
641 - \p opt::back_off - back-off strategy, default is \p cds::backoff::Default.
642 - \p opt::stat - internal statistics. By default, it is disabled (\p skip_list::empty_stat).
643 To enable it use \p skip_list::stat
645 template <typename... Options>
647 # ifdef CDS_DOXYGEN_INVOKED
648 typedef implementation_defined type ; ///< Metafunction result
650 typedef typename cds::opt::make_options<
651 typename cds::opt::find_type_traits< traits, Options... >::type
659 template <typename Node>
660 class head_node: public Node
662 typedef Node node_type;
663 typename node_type::atomic_marked_ptr m_Tower[skip_list::c_nHeightLimit];
666 head_node( unsigned int nHeight )
668 for ( size_t i = 0; i < sizeof(m_Tower) / sizeof(m_Tower[0]); ++i )
669 m_Tower[i].store( typename node_type::marked_ptr(), atomics::memory_order_relaxed );
671 node_type::make_tower( nHeight, m_Tower );
674 node_type * head() const
676 return const_cast<node_type *>( static_cast<node_type const *>(this));
680 template <typename NodeType, typename AtomicNodePtr, typename Alloc>
681 struct intrusive_node_builder
683 typedef NodeType node_type;
684 typedef AtomicNodePtr atomic_node_ptr;
685 typedef Alloc allocator_type;
687 typedef cds::details::Allocator< atomic_node_ptr, allocator_type > tower_allocator;
689 template <typename RandomGen>
690 static node_type * make_tower( node_type * pNode, RandomGen& gen )
692 return make_tower( pNode, gen() + 1 );
695 static node_type * make_tower( node_type * pNode, unsigned int nHeight )
698 pNode->make_tower( nHeight, tower_allocator().NewArray( nHeight - 1, nullptr ));
702 static void dispose_tower( node_type * pNode )
704 unsigned int nHeight = pNode->height();
706 tower_allocator().Delete( pNode->release_tower(), nHeight );
709 struct node_disposer {
710 void operator()( node_type * pNode )
712 dispose_tower( pNode );
717 // Forward declaration
718 template <class GC, typename NodeTraits, typename BackOff, bool IsConst>
721 } // namespace details
724 } // namespace skip_list
726 // Forward declaration
727 template <class GC, typename T, typename Traits = skip_list::traits >
730 }} // namespace cds::intrusive
732 #endif // #ifndef CDSLIB_INTRUSIVE_DETAILS_SKIP_LIST_BASE_H