3 #ifndef CDSLIB_INTRUSIVE_SKIP_LIST_NOGC_H
4 #define CDSLIB_INTRUSIVE_SKIP_LIST_NOGC_H
8 #include <cds/gc/nogc.h>
9 #include <cds/intrusive/details/skip_list_base.h>
10 #include <cds/opt/compare.h>
11 #include <cds/details/binary_functor_wrapper.h>
13 namespace cds { namespace intrusive {
17 template <typename Tag>
18 class node< cds::gc::nogc, Tag >
21 typedef cds::gc::nogc gc; ///< Garbage collector
22 typedef Tag tag; ///< tag
24 typedef atomics::atomic<node * > atomic_ptr;
25 typedef atomic_ptr tower_item_type;
28 atomic_ptr m_pNext; ///< Next item in bottom-list (list at level 0)
29 unsigned int m_nHeight; ///< Node height (size of m_arrNext array). For node at level 0 the height is 1.
30 atomic_ptr * m_arrNext; ///< Array of next items for levels 1 .. m_nHeight - 1. For node at level 0 \p m_arrNext is \p nullptr
33 /// Constructs a node of height 1 (a bottom-list node)
37 , m_arrNext( nullptr )
40 /// Constructs a node of height \p nHeight
41 void make_tower( unsigned int nHeight, atomic_ptr * nextTower )
43 assert( nHeight > 0 );
44 assert( (nHeight == 1 && nextTower == nullptr) // bottom-list node
45 || (nHeight > 1 && nextTower != nullptr) // node at level of more than 0
48 m_arrNext = nextTower;
52 atomic_ptr * release_tower()
54 atomic_ptr * pTower = m_arrNext;
60 atomic_ptr * get_tower() const
65 /// Access to element of next pointer array
66 atomic_ptr& next( unsigned int nLevel )
68 assert( nLevel < height() );
69 assert( nLevel == 0 || (nLevel > 0 && m_arrNext != nullptr) );
71 return nLevel ? m_arrNext[ nLevel - 1] : m_pNext;
74 /// Access to element of next pointer array (const version)
75 atomic_ptr const& next( unsigned int nLevel ) const
77 assert( nLevel < height() );
78 assert( nLevel == 0 || nLevel > 0 && m_arrNext != nullptr );
80 return nLevel ? m_arrNext[ nLevel - 1] : m_pNext;
83 /// Access to element of next pointer array (same as \ref next function)
84 atomic_ptr& operator[]( unsigned int nLevel )
86 return next( nLevel );
89 /// Access to element of next pointer array (same as \ref next function)
90 atomic_ptr const& operator[]( unsigned int nLevel ) const
92 return next( nLevel );
95 /// Height of the node
96 unsigned int height() const
101 /// Clears internal links
104 assert( m_arrNext == nullptr );
105 m_pNext.store( nullptr, atomics::memory_order_release );
108 bool is_cleared() const
110 return m_pNext.load( atomics::memory_order_relaxed ) == nullptr
111 && m_arrNext == nullptr
116 } // namespace skip_list
118 namespace skip_list { namespace details {
120 template <typename NodeTraits, typename BackOff, bool IsConst>
121 class iterator< cds::gc::nogc, NodeTraits, BackOff, IsConst>
124 typedef cds::gc::nogc gc;
125 typedef NodeTraits node_traits;
126 typedef BackOff back_off;
127 typedef typename node_traits::node_type node_type;
128 typedef typename node_traits::value_type value_type;
129 static CDS_CONSTEXPR bool const c_isConst = IsConst;
131 typedef typename std::conditional< c_isConst, value_type const &, value_type &>::type value_ref;
132 friend class iterator< gc, node_traits, back_off, !c_isConst >;
135 typedef typename node_type::atomic_ptr atomic_ptr;
138 public: // for internal use only!!!
139 iterator( node_type& refHead )
140 : m_pNode( refHead[0].load( atomics::memory_order_relaxed ) )
143 static iterator from_node( node_type * pNode )
155 iterator( iterator const& s)
156 : m_pNode( s.m_pNode )
159 value_type * operator ->() const
161 assert( m_pNode != nullptr );
162 assert( node_traits::to_value_ptr( m_pNode ) != nullptr );
164 return node_traits::to_value_ptr( m_pNode );
167 value_ref operator *() const
169 assert( m_pNode != nullptr );
170 assert( node_traits::to_value_ptr( m_pNode ) != nullptr );
172 return *node_traits::to_value_ptr( m_pNode );
176 iterator& operator ++()
179 m_pNode = m_pNode->next(0).load( atomics::memory_order_relaxed );
183 iterator& operator =(const iterator& src)
185 m_pNode = src.m_pNode;
189 template <typename Bkoff, bool C>
190 bool operator ==(iterator<gc, node_traits, Bkoff, C> const& i ) const
192 return m_pNode == i.m_pNode;
194 template <typename Bkoff, bool C>
195 bool operator !=(iterator<gc, node_traits, Bkoff, C> const& i ) const
197 return !( *this == i );
200 }} // namespace skip_list::details
203 /// Lock-free skip-list set (template specialization for gc::nogc)
204 /** @ingroup cds_intrusive_map
205 @anchor cds_intrusive_SkipListSet_nogc
207 This specialization is so-called append-only when no item
208 reclamation may be performed. The class does not support deleting of list item.
210 See \ref cds_intrusive_SkipListSet_hp "SkipListSet" for description of skip-list.
212 <b>Template arguments</b> :
213 - \p T - type to be stored in the set. The type must be based on \p skip_list::node (for \p skip_list::base_hook)
214 or it must have a member of type \p skip_list::node (for \p skip_list::member_hook).
215 - \p Traits - type traits, default is \p skip_list::traits.
216 It is possible to declare option-based list with \p cds::intrusive::skip_list::make_traits metafunction
217 istead of \p Traits template argument.
221 The class supports a forward iterator (\ref iterator and \ref const_iterator).
222 The iteration is ordered.
224 The iterator class supports the following minimalistic interface:
231 iterator( iterator const& s);
233 value_type * operator ->() const;
234 value_type& operator *() const;
237 iterator& operator ++();
240 iterator& operator = (const iterator& src);
242 bool operator ==(iterator const& i ) const;
243 bool operator !=(iterator const& i ) const;
246 Note, the iterator object returned by \ref end, \p cend member functions points to \p nullptr and should not be dereferenced.
250 You should incorporate \p skip_list::node into your struct \p T and provide
251 appropriate \p skip_list::traits::hook in your \p Traits template parameters. Usually, for \p Traits you
252 define a struct based on \p skip_list::traits.
254 Example for base hook:
256 #include <cds/intrusive/skip_list_nogc.h>
258 // Data stored in skip list
259 struct my_data: public cds::intrusive::skip_list::node< cds::gc::nogc >
268 // my_data compare functor
270 int operator()( const my_data& d1, const my_data& d2 )
272 return d1.strKey.compare( d2.strKey );
275 int operator()( const my_data& d, const std::string& s )
277 return d.strKey.compare(s);
280 int operator()( const std::string& s, const my_data& d )
282 return s.compare( d.strKey );
288 struct my_traits: public cds::intrusive::skip_list::traits
290 typedef cds::intrusive::skip_list::base_hook< cds::opt::gc< cds::gc::nogc > > hook;
291 typedef my_data_cmp compare;
294 // Declare skip-list set type
295 typedef cds::intrusive::SkipListSet< cds::gc::nogc, my_data, my_traits > traits_based_set;
298 Equivalent option-based code:
300 // GC-related specialization
301 #include <cds/intrusive/skip_list_nogc.h>
310 // Declare option-based skip-list set
311 typedef cds::intrusive::SkipListSet< cds::gc::nogc
313 , typename cds::intrusive::skip_list::make_traits<
314 cds::intrusive::opt::hook< cds::intrusive::skip_list::base_hook< cds::opt::gc< cds::gc::nogc > > >
315 ,cds::intrusive::opt::compare< my_data_cmp >
322 #ifdef CDS_DOXYGEN_INVOKED
323 ,typename Traits = skip_list::traits
328 class SkipListSet< cds::gc::nogc, T, Traits >
331 typedef cds::gc::nogc gc; ///< No garbage collector is used
332 typedef T value_type; ///< type of value stored in the skip-list
333 typedef Traits traits; ///< Traits template parameter
335 typedef typename traits::hook hook; ///< hook type
336 typedef typename hook::node_type node_type; ///< node type
338 # ifdef CDS_DOXYGEN_INVOKED
339 typedef implementation_defined key_comparator; ///< key comparison functor based on \p Traits::compare and \p Traits::less
341 typedef typename opt::details::make_comparator< value_type, traits >::type key_comparator;
343 typedef typename get_node_traits< value_type, node_type, hook>::type node_traits; ///< node traits
345 typedef typename traits::item_counter item_counter; ///< Item counting policy
346 typedef typename traits::memory_model memory_model; ///< Memory ordering. See \p cds::opt::memory_model option
347 typedef typename traits::random_level_generator random_level_generator ; ///< random level generator
348 typedef typename traits::allocator allocator_type; ///< allocator for maintaining array of next pointers of the node
349 typedef typename traits::back_off back_off; ///< Back-off strategy
350 typedef typename traits::stat stat; ///< internal statistics type
351 typedef typename traits::disposer disposer; ///< disposer
353 /// Max node height. The actual node height should be in range <tt>[0 .. c_nMaxHeight)</tt>
355 The max height is specified by \ref skip_list::random_level_generator "random level generator" constant \p m_nUpperBound
356 but it should be no more than 32 (\p skip_list::c_nHeightLimit).
358 static unsigned int const c_nMaxHeight = std::conditional<
359 (random_level_generator::c_nUpperBound <= skip_list::c_nHeightLimit),
360 std::integral_constant< unsigned int, random_level_generator::c_nUpperBound >,
361 std::integral_constant< unsigned int, skip_list::c_nHeightLimit >
365 static unsigned int const c_nMinHeight = 3;
369 typedef typename node_type::atomic_ptr atomic_node_ptr; ///< Atomic node pointer
373 typedef skip_list::details::intrusive_node_builder< node_type, atomic_node_ptr, allocator_type > intrusive_node_builder;
375 typedef typename std::conditional<
376 std::is_same< typename traits::internal_node_builder, cds::opt::none >::value
377 ,intrusive_node_builder
378 ,typename traits::internal_node_builder
379 >::type node_builder;
381 typedef std::unique_ptr< node_type, typename node_builder::node_disposer > scoped_node_ptr;
384 node_type * pPrev[ c_nMaxHeight ];
385 node_type * pSucc[ c_nMaxHeight ];
390 class head_node: public node_type
392 typename node_type::atomic_ptr m_Tower[c_nMaxHeight];
395 head_node( unsigned int nHeight )
397 for ( size_t i = 0; i < sizeof(m_Tower) / sizeof(m_Tower[0]); ++i )
398 m_Tower[i].store( nullptr, atomics::memory_order_relaxed );
400 node_type::make_tower( nHeight, m_Tower );
403 node_type * head() const
405 return const_cast<node_type *>( static_cast<node_type const *>(this));
410 for (unsigned int i = 0; i < sizeof(m_Tower) / sizeof(m_Tower[0]); ++i )
411 m_Tower[i].store( nullptr, atomics::memory_order_relaxed );
412 node_type::m_pNext.store( nullptr, atomics::memory_order_relaxed );
418 head_node m_Head; ///< head tower (max height)
420 item_counter m_ItemCounter; ///< item counter
421 random_level_generator m_RandomLevelGen; ///< random level generator instance
422 atomics::atomic<unsigned int> m_nHeight; ///< estimated high level
423 mutable stat m_Stat; ///< internal statistics
427 unsigned int random_level()
429 // Random generator produces a number from range [0..31]
430 // We need a number from range [1..32]
431 return m_RandomLevelGen() + 1;
434 template <typename Q>
435 node_type * build_node( Q v )
437 return node_builder::make_tower( v, m_RandomLevelGen );
440 static void dispose_node( node_type * pNode )
442 assert( pNode != nullptr );
443 typename node_builder::node_disposer()( pNode );
444 disposer()( node_traits::to_value_ptr( pNode ));
447 template <typename Q, typename Compare >
448 bool find_position( Q const& val, position& pos, Compare cmp, bool bStopIfFound, bool bStrictSearch ) const
452 node_type * pCur = nullptr;
456 unsigned int nHeight = c_nMaxHeight;
458 if ( !bStrictSearch )
459 nHeight = m_nHeight.load( memory_model::memory_order_relaxed );
460 pPred = m_Head.head();
462 for ( int nLevel = (int) nHeight - 1; nLevel >= 0; --nLevel ) {
464 pCur = pPred->next( nLevel ).load( memory_model::memory_order_relaxed );
467 // end of the list at level nLevel - goto next level
471 pSucc = pCur->next( nLevel ).load( memory_model::memory_order_relaxed );
473 if ( pPred->next( nLevel ).load( memory_model::memory_order_acquire ) != pCur
474 || pCur->next( nLevel ).load( memory_model::memory_order_acquire ) != pSucc )
479 nCmp = cmp( *node_traits::to_value_ptr( pCur ), val );
482 else if ( nCmp == 0 && bStopIfFound )
488 pos.pPrev[ nLevel ] = pPred;
489 pos.pSucc[ nLevel ] = pCur;
497 return pCur && nCmp == 0;
500 template <typename Func>
501 bool insert_at_position( value_type& val, node_type * pNode, position& pos, Func f )
503 unsigned int nHeight = pNode->height();
505 for ( unsigned int nLevel = 1; nLevel < nHeight; ++nLevel )
506 pNode->next( nLevel ).store( nullptr, memory_model::memory_order_relaxed );
509 node_type * p = pos.pSucc[0];
510 pNode->next( 0 ).store( pos.pSucc[ 0 ], memory_model::memory_order_release );
511 if ( !pos.pPrev[0]->next(0).compare_exchange_strong( p, pNode, memory_model::memory_order_release, memory_model::memory_order_relaxed ) ) {
517 for ( unsigned int nLevel = 1; nLevel < nHeight; ++nLevel ) {
518 node_type * p = nullptr;
520 node_type * q = pos.pSucc[ nLevel ];
522 if ( pNode->next( nLevel ).compare_exchange_strong( p, q, memory_model::memory_order_release, memory_model::memory_order_relaxed )) {
524 if ( pos.pPrev[nLevel]->next(nLevel).compare_exchange_strong( q, pNode, memory_model::memory_order_release, memory_model::memory_order_relaxed ) )
528 // Renew insert position
529 find_position( val, pos, key_comparator(), false, true );
535 template <typename Q, typename Compare, typename Func>
536 node_type * find_with_( Q& val, Compare cmp, Func f ) const
539 if ( find_position( val, pos, cmp, true, false )) {
540 assert( cmp( *node_traits::to_value_ptr( pos.pCur ), val ) == 0 );
542 f( *node_traits::to_value_ptr( pos.pCur ), val );
544 m_Stat.onFindFastSuccess();
548 m_Stat.onFindFastFailed();
553 void increase_height( unsigned int nHeight )
555 unsigned int nCur = m_nHeight.load( memory_model::memory_order_relaxed );
556 while ( nCur < nHeight && !m_nHeight.compare_exchange_weak( nCur, nHeight, memory_model::memory_order_acquire, atomics::memory_order_relaxed ) );
561 /// Default constructor
563 The constructor checks whether the count of guards is enough
564 for skip-list and may raise an exception if not.
567 : m_Head( c_nMaxHeight )
568 , m_nHeight( c_nMinHeight )
570 static_assert( (std::is_same< gc, typename node_type::gc >::value), "GC and node_type::gc must be the same type" );
572 // Barrier for head node
573 atomics::atomic_thread_fence( memory_model::memory_order_release );
576 /// Clears and destructs the skip-list
584 typedef skip_list::details::iterator< gc, node_traits, back_off, false > iterator;
586 /// Const iterator type
587 typedef skip_list::details::iterator< gc, node_traits, back_off, true > const_iterator;
589 /// Returns a forward iterator addressing the first element in a set
592 return iterator( *m_Head.head() );
595 /// Returns a forward const iterator addressing the first element in a set
596 const_iterator begin() const
598 return const_iterator( *m_Head.head() );
600 /// Returns a forward const iterator addressing the first element in a set
601 const_iterator cbegin() const
603 return const_iterator( *m_Head.head() );
606 /// Returns a forward iterator that addresses the location succeeding the last element in a set.
612 /// Returns a forward const iterator that addresses the location succeeding the last element in a set.
613 const_iterator end() const
615 return const_iterator();
617 /// Returns a forward const iterator that addresses the location succeeding the last element in a set.
618 const_iterator cend() const
620 return const_iterator();
625 iterator nonconst_end() const
634 The function inserts \p val in the set if it does not contain
635 an item with key equal to \p val.
637 Returns \p true if \p val is placed into the set, \p false otherwise.
639 bool insert( value_type& val )
641 node_type * pNode = node_traits::to_node_ptr( val );
642 scoped_node_ptr scp( pNode );
643 unsigned int nHeight = pNode->height();
644 bool bTowerOk = nHeight > 1 && pNode->get_tower() != nullptr;
645 bool bTowerMade = false;
650 bool bFound = find_position( val, pos, key_comparator(), true, true );
652 // scoped_node_ptr deletes the node tower if we create it
656 m_Stat.onInsertFailed();
662 nHeight = pNode->height();
667 if ( !insert_at_position( val, pNode, pos, []( value_type& ) {} )) {
668 m_Stat.onInsertRetry();
672 increase_height( nHeight );
674 m_Stat.onAddNode( nHeight );
675 m_Stat.onInsertSuccess();
683 The operation performs inserting or changing data with lock-free manner.
685 If the item \p val is not found in the set, then \p val is inserted into the set
686 iff \p bInsert is \p true.
687 Otherwise, the functor \p func is called with item found.
688 The functor signature is:
690 void func( bool bNew, value_type& item, value_type& val );
693 - \p bNew - \p true if the item has been inserted, \p false otherwise
694 - \p item - item of the set
695 - \p val - argument \p val passed into the \p %update() function
696 If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
697 refer to the same thing.
699 The functor can change non-key fields of the \p item; however, \p func must guarantee
700 that during changing no any other modifications could be made on this item by concurrent threads.
702 Returns std::pair<bool, bool> where \p first is \p true if operation is successfull,
703 \p second is \p true if new item has been added or \p false if the item with \p key
704 already is in the set.
706 @warning See \ref cds_intrusive_item_creating "insert item troubleshooting"
708 template <typename Func>
709 std::pair<bool, bool> update( value_type& val, Func func, bool bInsert = true )
711 node_type * pNode = node_traits::to_node_ptr( val );
712 scoped_node_ptr scp( pNode );
713 unsigned int nHeight = pNode->height();
714 bool bTowerOk = nHeight > 1 && pNode->get_tower() != nullptr;
715 bool bTowerMade = false;
720 bool bFound = find_position( val, pos, key_comparator(), true, true );
722 // scoped_node_ptr deletes the node tower if we create it before
726 func( false, *node_traits::to_value_ptr(pos.pCur), val );
727 m_Stat.onUpdateExist();
728 return std::make_pair( true, false );
733 return std::make_pair( false, false );
738 nHeight = pNode->height();
743 if ( !insert_at_position( val, pNode, pos, [&func]( value_type& item ) { func( true, item, item ); })) {
744 m_Stat.onInsertRetry();
748 increase_height( nHeight );
751 m_Stat.onAddNode( nHeight );
752 m_Stat.onUpdateNew();
753 return std::make_pair( true, true );
757 template <typename Func>
758 CDS_DEPRECATED("ensure() is deprecated, use update()")
759 std::pair<bool, bool> ensure( value_type& val, Func func )
761 return update( val, func, true );
766 /** \anchor cds_intrusive_SkipListSet_nogc_find_func
767 The function searches the item with key equal to \p key and calls the functor \p f for item found.
768 The interface of \p Func functor is:
771 void operator()( value_type& item, Q& key );
774 where \p item is the item found, \p key is the <tt>find</tt> function argument.
776 The functor can change non-key fields of \p item. Note that the functor is only guarantee
777 that \p item cannot be disposed during functor is executing.
778 The functor does not serialize simultaneous access to the set \p item. If such access is
779 possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
781 The \p key argument is non-const since it can be used as \p f functor destination i.e., the functor
782 can modify both arguments.
784 Note the hash functor specified for class \p Traits template parameter
785 should accept a parameter of type \p Q that can be not the same as \p value_type.
787 The function returns \p true if \p key is found, \p false otherwise.
789 template <typename Q, typename Func>
790 bool find( Q& key, Func f ) const
792 return find_with_( key, key_comparator(), f ) != nullptr;
795 template <typename Q, typename Func>
796 bool find( Q const& key, Func f ) const
798 return find_with_( key, key_comparator(), f ) != nullptr;
802 /// Finds the key \p key using \p pred predicate for comparing
804 The function is an analog of \ref cds_intrusive_SkipListSet_nogc_find_func "find(Q&, Func)"
805 but \p pred predicate is used for key compare.
806 \p Less has the interface like \p std::less.
807 \p pred must imply the same element order as the comparator used for building the set.
809 template <typename Q, typename Less, typename Func>
810 bool find_with( Q& key, Less pred, Func f ) const
813 return find_with_( key, cds::opt::details::make_comparator_from_less<Less>(), f ) != nullptr;
816 template <typename Q, typename Less, typename Func>
817 bool find_with( Q const& key, Less pred, Func f ) const
820 return find_with_( key, cds::opt::details::make_comparator_from_less<Less>(), f ) != nullptr;
824 /// Checks whether the set contains \p key
826 The function searches the item with key equal to \p key
827 and returns pointer to item found or \p nullptr.
829 template <typename Q>
830 value_type * contains( Q const& key ) const
832 node_type * pNode = find_with_( key, key_comparator(), [](value_type& , Q const& ) {} );
834 return node_traits::to_value_ptr( pNode );
838 template <typename Q>
839 CDS_DEPRECATED("deprecated, use contains()")
840 value_type * find( Q const& key ) const
842 return contains( key );
846 /// Checks whether the set contains \p key using \p pred predicate for searching
848 The function is similar to <tt>contains( key )</tt> but \p pred is used for key comparing.
849 \p Less functor has the interface like \p std::less.
850 \p Less must imply the same element order as the comparator used for building the set.
852 template <typename Q, typename Less>
853 value_type * contains( Q const& key, Less pred ) const
856 node_type * pNode = find_with_( key, cds::opt::details::make_comparator_from_less<Less>(), [](value_type& , Q const& ) {} );
858 return node_traits::to_value_ptr( pNode );
862 template <typename Q, typename Less>
863 CDS_DEPRECATED("deprecated, use contains()")
864 value_type * find_with( Q const& key, Less pred ) const
866 return contains( key, pred );
870 /// Gets minimum key from the set
872 If the set is empty the function returns \p nullptr
874 value_type * get_min() const
876 return node_traits::to_value_ptr( m_Head.head()->next( 0 ));
879 /// Gets maximum key from the set
881 The function returns \p nullptr if the set is empty
883 value_type * get_max() const
887 unsigned int nHeight = m_nHeight.load( memory_model::memory_order_relaxed );
888 pPred = m_Head.head();
890 for ( int nLevel = (int) nHeight - 1; nLevel >= 0; --nLevel ) {
892 node_type * pCur = pPred->next( nLevel ).load( memory_model::memory_order_relaxed );
895 // end of the list at level nLevel - goto next level
901 return pPred && pPred != m_Head.head() ? node_traits::to_value_ptr( pPred ) : nullptr;
904 /// Clears the set (non-atomic)
906 The function is not atomic.
907 Finding and/or inserting is prohibited while clearing.
908 Otherwise an unpredictable result may be encountered.
909 Thus, \p clear() may be used only for debugging purposes.
913 node_type * pNode = m_Head.head()->next(0).load( memory_model::memory_order_relaxed );
915 m_ItemCounter.reset();
916 m_nHeight.store( c_nMinHeight, memory_model::memory_order_release );
919 node_type * pNext = pNode->next(0).load( memory_model::memory_order_relaxed );
920 dispose_node( pNode );
925 /// Returns item count in the set
927 The value returned depends on item counter type provided by \p Traits template parameter.
928 For \p atomicity::empty_item_counter the function always returns 0.
929 The function is not suitable for checking the set emptiness, use \p empty().
933 return m_ItemCounter;
936 /// Checks if the set is empty
939 return m_Head.head()->next( 0 ).load( memory_model::memory_order_relaxed ) == nullptr;
942 /// Returns maximum height of skip-list. The max height is a constant for each object and does not exceed 32.
943 static CDS_CONSTEXPR unsigned int max_height() CDS_NOEXCEPT
948 /// Returns const reference to internal statistics
949 stat const& statistics() const
955 }} // namespace cds::intrusive
958 #endif // #ifndef CDSLIB_INTRUSIVE_SKIP_LIST_IMPL_H