3 #ifndef __CDS_INTRUSIVE_SKIP_LIST_HRC_H
4 #define __CDS_INTRUSIVE_SKIP_LIST_HRC_H
6 #include <cds/intrusive/skip_list_impl.h>
7 #include <cds/gc/hrc.h>
10 namespace cds { namespace intrusive { namespace skip_list {
11 // Specialization for HRC GC
12 template <typename Tag>
13 class node< cds::gc::HRC, Tag>: public cds::gc::HRC::container_node
16 typedef gc::HRC gc ; ///< Garbage collector
17 typedef Tag tag ; ///< tag
19 typedef cds::details::marked_ptr<node, 1> marked_ptr ; ///< marked pointer
20 typedef typename gc::template atomic_marked_ptr< marked_ptr> atomic_marked_ptr ; ///< atomic marked pointer specific for GC
21 typedef atomic_marked_ptr tower_item_type;
24 atomic_marked_ptr m_pNext ; ///< Next item in bottom-list (list at level 0)
25 unsigned int m_nHeight ; ///< Node height (size of m_arrNext array). For node at level 0 the height is 1.
26 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 NULL
32 /// Constructs a node of height 1 (a bottom-list node)
34 : m_pNext( null_ptr<node *>())
36 , m_arrNext( null_ptr<atomic_marked_ptr *>())
43 m_pNext.store( marked_ptr(), CDS_ATOMIC::memory_order_relaxed );
46 /// Constructs a node of height \p nHeight
47 void make_tower( unsigned int nHeight, atomic_marked_ptr * nextTower )
49 assert( nHeight > 0 );
50 assert( ( nHeight == 1 && nextTower == null_ptr<atomic_marked_ptr *>() ) // bottom-list node
51 || ( nHeight > 1 && nextTower != null_ptr<atomic_marked_ptr *>() ) // node at level of more than 0
54 m_arrNext = nextTower;
58 atomic_marked_ptr * release_tower()
60 unsigned int nHeight = m_nHeight - 1;
61 atomic_marked_ptr * pTower = m_arrNext;
63 m_arrNext = null_ptr<atomic_marked_ptr *>();
65 for ( unsigned int i = 0; i < nHeight; ++i )
66 pTower[i].store( marked_ptr(), CDS_ATOMIC::memory_order_release );
71 atomic_marked_ptr * get_tower() const
76 /// Access to element of next pointer array
77 atomic_marked_ptr& next( unsigned int nLevel )
79 assert( nLevel < height() );
80 assert( nLevel == 0 || (nLevel > 0 && m_arrNext != null_ptr<atomic_marked_ptr *>() ));
82 return nLevel ? m_arrNext[ nLevel - 1] : m_pNext;
85 /// Access to element of next pointer array (const version)
86 atomic_marked_ptr const& next( unsigned int nLevel ) const
88 assert( nLevel < height() );
89 assert( nLevel == 0 || (nLevel > 0 && m_arrNext != null_ptr<atomic_marked_ptr *>()) );
91 return nLevel ? m_arrNext[ nLevel - 1] : m_pNext;
94 /// Access to element of next pointer array (same as \ref next function)
95 atomic_marked_ptr& operator[]( unsigned int nLevel )
97 return next( nLevel );
100 /// Access to element of next pointer array (same as \ref next function)
101 atomic_marked_ptr const& operator[]( unsigned int nLevel ) const
103 return next( nLevel );
106 /// Height of the node
107 unsigned int height() const
113 virtual void cleanUp( cds::gc::hrc::ThreadGC * pGC )
115 assert( pGC != NULL );
116 typename gc::GuardArray<2> aGuards( *pGC );
118 unsigned int const nHeight = height();
119 for (unsigned int i = 0; i < nHeight; ++i ) {
121 marked_ptr pNextMarked( aGuards.protect( 0, next(i) ));
122 node * pNext = pNextMarked.ptr();
123 if ( pNext && pNext->m_bDeleted.load(CDS_ATOMIC::memory_order_acquire) ) {
124 marked_ptr p = aGuards.protect( 1, pNext->next(i) );
125 next(i).compare_exchange_strong( pNextMarked, p, CDS_ATOMIC::memory_order_acquire, CDS_ATOMIC::memory_order_relaxed );
135 virtual void terminate( cds::gc::hrc::ThreadGC * pGC, bool bConcurrent )
137 unsigned int const nHeight = height();
139 for (unsigned int i = 0; i < nHeight; ++i ) {
140 marked_ptr pNext = next(i).load(CDS_ATOMIC::memory_order_relaxed);
141 while ( !next(i).compare_exchange_weak( pNext, marked_ptr(), CDS_ATOMIC::memory_order_release, CDS_ATOMIC::memory_order_relaxed ) );
145 for (unsigned int i = 0; i < nHeight; ++i )
146 next(i).store( marked_ptr(), CDS_ATOMIC::memory_order_relaxed );
153 template <typename Tag>
154 class head_node< node< cds::gc::HRC, Tag > >
156 typedef node< cds::gc::HRC, Tag > node_type;
158 struct head_tower: public node_type
160 typename node_type::atomic_marked_ptr m_Tower[skip_list::c_nHeightLimit];
163 head_tower * m_pHead;
165 struct head_disposer {
166 void operator()( head_tower * p )
172 head_node( unsigned int nHeight )
173 : m_pHead( new head_tower() )
175 for ( size_t i = 0; i < sizeof(m_pHead->m_Tower) / sizeof(m_pHead->m_Tower[0]); ++i )
176 m_pHead->m_Tower[i].store( typename node_type::marked_ptr(), CDS_ATOMIC::memory_order_relaxed );
178 m_pHead->make_tower( nHeight, m_pHead->m_Tower );
183 cds::gc::HRC::template retire<head_disposer>( m_pHead );
188 return static_cast<node_type *>( m_pHead );
190 node_type const * head() const
192 return static_cast<node_type const *>( m_pHead );
196 } // namespace details
198 }}} // namespace cds::intrusive::skip_list