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;
67 clean, // initial state
68 removed, // final state
69 hand_off // temp state
75 atomic_marked_ptr m_pNext{ nullptr }; ///< Next item in bottom-list (list at level 0)
76 unsigned int m_nHeight{ 1 }; ///< Node height (size of \p m_arrNext array). For node at level 0 the height is 1.
77 atomic_marked_ptr * m_arrNext{ nullptr }; ///< Array of next items for levels 1 .. m_nHeight - 1. For node at level 0 \p m_arrNext is \p nullptr
78 atomics::atomic< state > m_state{ clean };
82 /// Constructs a node's tower of height \p nHeight
83 void make_tower( unsigned int nHeight, atomic_marked_ptr * nextTower )
85 assert( nHeight > 0 );
86 assert( (nHeight == 1 && nextTower == nullptr) // bottom-list node
87 || (nHeight > 1 && nextTower != nullptr) // node at level of more than 0
90 m_arrNext = nextTower;
92 atomics::atomic_thread_fence( atomics::memory_order_release );
96 atomic_marked_ptr * release_tower()
98 atomic_marked_ptr * pTower = m_arrNext;
104 atomic_marked_ptr * get_tower() const
109 bool has_tower() const
111 return m_nHeight > 1;
115 /// Access to element of next pointer array
116 atomic_marked_ptr& next( unsigned int nLevel )
118 assert( nLevel < height());
119 assert( nLevel == 0 || (nLevel > 0 && m_arrNext != nullptr));
121 return nLevel ? m_arrNext[ nLevel - 1] : m_pNext;
124 /// Access to element of next pointer array (const version)
125 atomic_marked_ptr const& next( unsigned int nLevel ) const
127 assert( nLevel < height());
128 assert( nLevel == 0 || nLevel > 0 && m_arrNext != nullptr );
130 return nLevel ? m_arrNext[ nLevel - 1] : m_pNext;
133 /// Access to element of next pointer array (synonym for \p next() function)
134 atomic_marked_ptr& operator[]( unsigned int nLevel )
136 return next( nLevel );
139 /// Access to element of next pointer array (synonym for \p next() function)
140 atomic_marked_ptr const& operator[]( unsigned int nLevel ) const
142 return next( nLevel );
145 /// Height of the node
146 unsigned int height() const
151 /// Clears internal links
154 assert( m_arrNext == nullptr );
155 m_pNext.store( marked_ptr(), atomics::memory_order_release );
159 bool is_cleared() const
161 return m_pNext == atomic_marked_ptr()
162 && m_arrNext == nullptr
166 bool set_state( state& cur_state, state new_state, atomics::memory_order order )
168 return m_state.compare_exchange_strong( cur_state, new_state, order, atomics::memory_order_relaxed );
171 void clear_state( atomics::memory_order order )
173 m_state.store( clean, order );
180 struct default_hook {
181 typedef undefined_gc gc;
182 typedef opt::none tag;
187 template < typename HookType, typename... Options>
190 typedef typename opt::make_options< default_hook, Options...>::type options;
191 typedef typename options::gc gc;
192 typedef typename options::tag tag;
193 typedef node<gc, tag> node_type;
194 typedef HookType hook_type;
201 - \p opt::gc - garbage collector
202 - \p opt::tag - a \ref cds_intrusive_hook_tag "tag"
204 template < typename... Options >
205 struct base_hook: public hook< opt::base_hook_tag, Options... >
210 \p MemberOffset defines offset in bytes of \ref node member into your structure.
211 Use \p offsetof macro to define \p MemberOffset
214 - \p opt::gc - garbage collector
215 - \p opt::tag - a \ref cds_intrusive_hook_tag "tag"
217 template < size_t MemberOffset, typename... Options >
218 struct member_hook: public hook< opt::member_hook_tag, Options... >
221 static const size_t c_nMemberOffset = MemberOffset;
227 \p NodeTraits defines type traits for node.
228 See \ref node_traits for \p NodeTraits interface description
231 - \p opt::gc - garbage collector
232 - \p opt::tag - a \ref cds_intrusive_hook_tag "tag"
234 template <typename NodeTraits, typename... Options >
235 struct traits_hook: public hook< opt::traits_hook_tag, Options... >
238 typedef NodeTraits node_traits;
242 /// Option specifying random level generator
244 The random level generator is an important part of skip-list algorithm.
245 The node height in the skip-list have a probabilistic distribution
246 where half of the nodes that have level \p i pointers also have level <tt>i+1</tt> pointers
248 The random level generator should provide such distribution.
250 The \p Type functor interface is:
252 struct random_generator {
253 static unsigned int const c_nUpperBound = 32;
255 unsigned int operator()();
260 - \p c_nUpperBound - constant that specifies the upper bound of random number generated.
261 The generator produces a number from range <tt>[0 .. c_nUpperBound)</tt> (upper bound excluded).
262 \p c_nUpperBound must be no more than 32.
263 - <tt>random_generator()</tt> - the constructor of generator object initialises the generator instance (its internal state).
264 - <tt>unsigned int operator()()</tt> - the main generating function. Returns random level from range 0..31.
266 Stateful generators are supported.
268 Available \p Type implementations:
269 - \p skip_list::xorshift
270 - \p skip_list::turbo_pascal
272 template <typename Type>
273 struct random_level_generator {
275 template <typename Base>
276 struct pack: public Base
278 typedef Type random_level_generator;
283 /// Xor-shift random level generator
285 The simplest of the generators described in George
286 Marsaglia's "Xorshift RNGs" paper. This is not a high-quality
287 generator but is acceptable for skip-list.
289 The random generator should return numbers from range [0..31].
291 From Doug Lea's ConcurrentSkipListMap.java.
295 atomics::atomic<unsigned int> m_nSeed;
298 /// The upper bound of generator's return value. The generator produces random number in range <tt>[0..c_nUpperBound)</tt>
299 static unsigned int const c_nUpperBound = c_nHeightLimit;
301 /// Initializes the generator instance
304 m_nSeed.store( (unsigned int) cds::OS::Timer::random_seed(), atomics::memory_order_relaxed );
307 /// Main generator function
308 unsigned int operator()()
310 /* ConcurrentSkipListMap.java
311 private int randomLevel() {
315 randomSeed = x ^= x << 5;
316 if ((x & 0x80000001) != 0) // test highest and lowest bits
319 while (((x >>>= 1) & 1) != 0) ++level;
323 unsigned int x = m_nSeed.load( atomics::memory_order_relaxed );
327 m_nSeed.store( x, atomics::memory_order_relaxed );
328 unsigned int nLevel = ((x & 0x00000001) != 0) ? 0 : cds::bitop::LSB( (~(x >> 1)) & 0x7FFFFFFF );
329 assert( nLevel < c_nUpperBound );
334 /// Turbo-pascal random level generator
336 This uses a cheap pseudo-random function that was used in Turbo Pascal.
338 The random generator should return numbers from range [0..31].
340 From Doug Lea's ConcurrentSkipListMap.java.
345 atomics::atomic<unsigned int> m_nSeed;
348 /// The upper bound of generator's return value. The generator produces random number in range <tt>[0..c_nUpperBound)</tt>
349 static unsigned int const c_nUpperBound = c_nHeightLimit;
351 /// Initializes the generator instance
354 m_nSeed.store( (unsigned int) cds::OS::Timer::random_seed(), atomics::memory_order_relaxed );
357 /// Main generator function
358 unsigned int operator()()
361 private int randomLevel() {
364 randomSeed = r * 134775813 + 1;
366 while ((r <<= 1) > 0)
373 The low bits are apparently not very random (the original used only
374 upper 16 bits) so we traverse from highest bit down (i.e., test
375 sign), thus hardly ever use lower bits.
377 unsigned int x = m_nSeed.load( atomics::memory_order_relaxed ) * 134775813 + 1;
378 m_nSeed.store( x, atomics::memory_order_relaxed );
379 unsigned int nLevel = ( x & 0x80000000 ) ? (31 - cds::bitop::MSBnz( (x & 0x7FFFFFFF) | 1 )) : 0;
380 assert( nLevel < c_nUpperBound );
385 /// \p SkipListSet internal statistics
386 template <typename EventCounter = cds::atomicity::event_counter>
388 typedef EventCounter event_counter ; ///< Event counter type
390 event_counter m_nNodeHeightAdd[c_nHeightLimit] ; ///< Count of added node of each height
391 event_counter m_nNodeHeightDel[c_nHeightLimit] ; ///< Count of deleted node of each height
392 event_counter m_nInsertSuccess ; ///< Count of success insertion
393 event_counter m_nInsertFailed ; ///< Count of failed insertion
394 event_counter m_nInsertRetries ; ///< Count of unsuccessful retries of insertion
395 event_counter m_nUpdateExist ; ///< Count of \p update() call for existed node
396 event_counter m_nUpdateNew ; ///< Count of \p update() call for new node
397 event_counter m_nUnlinkSuccess ; ///< Count of successful call of \p unlink
398 event_counter m_nUnlinkFailed ; ///< Count of failed call of \p unlink
399 event_counter m_nEraseSuccess ; ///< Count of successful call of \p erase
400 event_counter m_nEraseFailed ; ///< Count of failed call of \p erase
401 event_counter m_nEraseRetry ; ///< Count of retries while erasing node
402 event_counter m_nFindFastSuccess ; ///< Count of successful call of \p find and all derivatives (via fast-path)
403 event_counter m_nFindFastFailed ; ///< Count of failed call of \p find and all derivatives (via fast-path)
404 event_counter m_nFindSlowSuccess ; ///< Count of successful call of \p find and all derivatives (via slow-path)
405 event_counter m_nFindSlowFailed ; ///< Count of failed call of \p find and all derivatives (via slow-path)
406 event_counter m_nRenewInsertPosition ; ///< Count of renewing position events while inserting
407 event_counter m_nLogicDeleteWhileInsert ; ///< Count of events "The node has been logically deleted while inserting"
408 event_counter m_nNotFoundWhileInsert ; ///< Count of events "Inserting node is not found"
409 event_counter m_nFastErase ; ///< Fast erase event counter
410 event_counter m_nFastExtract ; ///< Fast extract event counter
411 event_counter m_nSlowErase ; ///< Slow erase event counter
412 event_counter m_nSlowExtract ; ///< Slow extract event counter
413 event_counter m_nExtractSuccess ; ///< Count of successful call of \p extract
414 event_counter m_nExtractFailed ; ///< Count of failed call of \p extract
415 event_counter m_nExtractRetries ; ///< Count of retries of \p extract call
416 event_counter m_nExtractMinSuccess ; ///< Count of successful call of \p extract_min
417 event_counter m_nExtractMinFailed ; ///< Count of failed call of \p extract_min
418 event_counter m_nExtractMinRetries ; ///< Count of retries of \p extract_min call
419 event_counter m_nExtractMaxSuccess ; ///< Count of successful call of \p extract_max
420 event_counter m_nExtractMaxFailed ; ///< Count of failed call of \p extract_max
421 event_counter m_nExtractMaxRetries ; ///< Count of retries of \p extract_max call
422 event_counter m_nEraseWhileFind ; ///< Count of erased item while searching
423 event_counter m_nExtractWhileFind ; ///< Count of extracted item while searching (RCU only)
424 event_counter m_nNodeHandOffFailed ; ///< Cannot set "hand-off" node state
427 void onAddNode( unsigned int nHeight )
429 assert( nHeight > 0 && nHeight <= sizeof(m_nNodeHeightAdd) / sizeof(m_nNodeHeightAdd[0]));
430 ++m_nNodeHeightAdd[nHeight - 1];
432 void onRemoveNode( unsigned int nHeight )
434 assert( nHeight > 0 && nHeight <= sizeof(m_nNodeHeightDel) / sizeof(m_nNodeHeightDel[0]));
435 ++m_nNodeHeightDel[nHeight - 1];
438 void onInsertSuccess() { ++m_nInsertSuccess ; }
439 void onInsertFailed() { ++m_nInsertFailed ; }
440 void onInsertRetry() { ++m_nInsertRetries ; }
441 void onUpdateExist() { ++m_nUpdateExist ; }
442 void onUpdateNew() { ++m_nUpdateNew ; }
443 void onUnlinkSuccess() { ++m_nUnlinkSuccess ; }
444 void onUnlinkFailed() { ++m_nUnlinkFailed ; }
445 void onEraseSuccess() { ++m_nEraseSuccess ; }
446 void onEraseFailed() { ++m_nEraseFailed ; }
447 void onEraseRetry() { ++m_nEraseRetry; }
448 void onFindFastSuccess() { ++m_nFindFastSuccess ; }
449 void onFindFastFailed() { ++m_nFindFastFailed ; }
450 void onFindSlowSuccess() { ++m_nFindSlowSuccess ; }
451 void onFindSlowFailed() { ++m_nFindSlowFailed ; }
452 void onEraseWhileFind() { ++m_nEraseWhileFind ; }
453 void onExtractWhileFind() { ++m_nExtractWhileFind ; }
454 void onRenewInsertPosition() { ++m_nRenewInsertPosition; }
455 void onLogicDeleteWhileInsert() { ++m_nLogicDeleteWhileInsert; }
456 void onNotFoundWhileInsert() { ++m_nNotFoundWhileInsert; }
457 void onFastErase() { ++m_nFastErase; }
458 void onFastExtract() { ++m_nFastExtract; }
459 void onSlowErase() { ++m_nSlowErase; }
460 void onSlowExtract() { ++m_nSlowExtract; }
461 void onExtractSuccess() { ++m_nExtractSuccess; }
462 void onExtractFailed() { ++m_nExtractFailed; }
463 void onExtractRetry() { ++m_nExtractRetries; }
464 void onExtractMinSuccess() { ++m_nExtractMinSuccess; }
465 void onExtractMinFailed() { ++m_nExtractMinFailed; }
466 void onExtractMinRetry() { ++m_nExtractMinRetries; }
467 void onExtractMaxSuccess() { ++m_nExtractMaxSuccess; }
468 void onExtractMaxFailed() { ++m_nExtractMaxFailed; }
469 void onExtractMaxRetry() { ++m_nExtractMaxRetries; }
470 void onNodeHandOffFailed() { ++m_nNodeHandOffFailed; }
475 /// \p SkipListSet empty internal statistics
478 void onAddNode( unsigned int /*nHeight*/ ) const {}
479 void onRemoveNode( unsigned int /*nHeight*/ ) const {}
480 void onInsertSuccess() const {}
481 void onInsertFailed() const {}
482 void onInsertRetry() const {}
483 void onUpdateExist() const {}
484 void onUpdateNew() const {}
485 void onUnlinkSuccess() const {}
486 void onUnlinkFailed() const {}
487 void onEraseSuccess() const {}
488 void onEraseFailed() const {}
489 void onEraseRetry() const {}
490 void onFindFastSuccess() const {}
491 void onFindFastFailed() const {}
492 void onFindSlowSuccess() const {}
493 void onFindSlowFailed() const {}
494 void onEraseWhileFind() const {}
495 void onExtractWhileFind() const {}
496 void onRenewInsertPosition() const {}
497 void onLogicDeleteWhileInsert() const {}
498 void onNotFoundWhileInsert() const {}
499 void onFastErase() const {}
500 void onFastExtract() const {}
501 void onSlowErase() const {}
502 void onSlowExtract() const {}
503 void onExtractSuccess() const {}
504 void onExtractFailed() const {}
505 void onExtractRetry() const {}
506 void onExtractMinSuccess() const {}
507 void onExtractMinFailed() const {}
508 void onExtractMinRetry() const {}
509 void onExtractMaxSuccess() const {}
510 void onExtractMaxFailed() const {}
511 void onExtractMaxRetry() const {}
512 void onNodeHandOffFailed() const {}
517 // For internal use only!!!
518 template <typename Type>
519 struct internal_node_builder {
520 template <typename Base>
521 struct pack: public Base
523 typedef Type internal_node_builder;
528 /// \p SkipListSet traits
533 Possible values are: \p skip_list::base_hook, \p skip_list::member_hook, \p skip_list::traits_hook.
535 typedef base_hook<> hook;
537 /// Key comparison functor
539 No default functor is provided. If the option is not specified, the \p less is used.
541 typedef opt::none compare;
543 /// specifies binary predicate used for key compare.
545 Default is \p std::less<T>.
547 typedef opt::none less;
551 The functor used for dispose removed items. Default is \p opt::v::empty_disposer.
553 typedef opt::v::empty_disposer disposer;
557 The type for item counting feature.
558 By default, item counting is disabled (\p atomicity::empty_item_counter),
559 \p atomicity::item_counter enables it.
561 typedef atomicity::empty_item_counter item_counter;
563 /// C++ memory ordering model
565 List of available memory ordering see \p opt::memory_model
567 typedef opt::v::relaxed_ordering memory_model;
569 /// Random level generator
571 The random level generator is an important part of skip-list algorithm.
572 The node height in the skip-list have a probabilistic distribution
573 where half of the nodes that have level \p i pointers also have level <tt>i+1</tt> pointers
574 (i = 0..30). So, the height of a node is in range [0..31].
576 See \p skip_list::random_level_generator option setter.
578 typedef turbo_pascal random_level_generator;
582 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.
585 The allocator specified is used to allocate an array of next pointers
586 for nodes which height is more than 1.
588 typedef CDS_DEFAULT_ALLOCATOR allocator;
590 /// back-off strategy
592 If the option is not specified, the \p cds::backoff::Default is used.
594 typedef cds::backoff::Default back_off;
596 /// Internal statistics
598 By default, internal statistics is disabled (\p skip_list::empty_stat).
599 Use \p skip_list::stat to enable it.
601 typedef empty_stat stat;
603 /// RCU deadlock checking policy (only for \ref cds_intrusive_SkipListSet_rcu "RCU-based SkipListSet")
605 List of available options see \p opt::rcu_check_deadlock
607 typedef opt::v::rcu_throw_deadlock rcu_check_deadlock;
610 // For internal use only!!!
611 typedef opt::none internal_node_builder;
615 /// Metafunction converting option list to \p SkipListSet traits
618 - \p opt::hook - hook used. Possible values are: \p skip_list::base_hook, \p skip_list::member_hook, \p skip_list::traits_hook.
619 If the option is not specified, <tt>skip_list::base_hook<></tt> and \p gc::HP is used.
620 - \p opt::compare - key comparison functor. No default functor is provided.
621 If the option is not specified, the \p opt::less is used.
622 - \p opt::less - specifies binary predicate used for key comparison. Default is \p std::less<T>.
623 - \p opt::disposer - the functor used for dispose removed items. Default is \p opt::v::empty_disposer. Due the nature
624 of GC schema the disposer may be called asynchronously.
625 - \p opt::item_counter - the type of item counting feature. Default is disabled, i.e. \p atomicity::empty_item_counter.
626 To enable it use \p atomicity::item_counter
627 - \p opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
628 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
629 - \p skip_list::random_level_generator - random level generator. Can be \p skip_list::xorshift,
630 \p skip_list::turbo_pascal (the default) or
631 user-provided one. See \p skip_list::random_level_generator option description for explanation.
632 - \p opt::allocator - although the skip-list is an intrusive container,
633 an allocator should be provided to maintain variable randomly-calculated height of the node
634 since the node can contain up to 32 next pointers. The allocator option is used to allocate an array of next pointers
635 for nodes which height is more than 1. Default is \ref CDS_DEFAULT_ALLOCATOR.
636 - \p opt::back_off - back-off strategy, default is \p cds::backoff::Default.
637 - \p opt::stat - internal statistics. By default, it is disabled (\p skip_list::empty_stat).
638 To enable it use \p skip_list::stat
640 template <typename... Options>
642 # ifdef CDS_DOXYGEN_INVOKED
643 typedef implementation_defined type ; ///< Metafunction result
645 typedef typename cds::opt::make_options<
646 typename cds::opt::find_type_traits< traits, Options... >::type
654 template <typename Node>
655 class head_node: public Node
657 typedef Node node_type;
658 typename node_type::atomic_marked_ptr m_Tower[skip_list::c_nHeightLimit];
661 head_node( unsigned int nHeight )
663 for ( size_t i = 0; i < sizeof(m_Tower) / sizeof(m_Tower[0]); ++i )
664 m_Tower[i].store( typename node_type::marked_ptr(), atomics::memory_order_relaxed );
666 node_type::make_tower( nHeight, m_Tower );
669 node_type * head() const
671 return const_cast<node_type *>( static_cast<node_type const *>(this));
675 template <typename NodeType, typename AtomicNodePtr, typename Alloc>
676 struct intrusive_node_builder
678 typedef NodeType node_type;
679 typedef AtomicNodePtr atomic_node_ptr;
680 typedef Alloc allocator_type;
682 typedef cds::details::Allocator< atomic_node_ptr, allocator_type > tower_allocator;
684 template <typename RandomGen>
685 static node_type * make_tower( node_type * pNode, RandomGen& gen )
687 return make_tower( pNode, gen() + 1 );
690 static node_type * make_tower( node_type * pNode, unsigned int nHeight )
693 pNode->make_tower( nHeight, tower_allocator().NewArray( nHeight - 1, nullptr ));
697 static void dispose_tower( node_type * pNode )
699 unsigned int nHeight = pNode->height();
701 tower_allocator().Delete( pNode->release_tower(), nHeight );
704 struct node_disposer {
705 void operator()( node_type * pNode )
707 dispose_tower( pNode );
712 // Forward declaration
713 template <class GC, typename NodeTraits, typename BackOff, bool IsConst>
716 } // namespace details
719 } // namespace skip_list
721 // Forward declaration
722 template <class GC, typename T, typename Traits = skip_list::traits >
725 }} // namespace cds::intrusive
727 #endif // #ifndef CDSLIB_INTRUSIVE_DETAILS_SKIP_LIST_BASE_H