cds/intrusive/skip_list_hrc.h

   1 //$$CDS-header$$
   2
   3 #ifndef __CDS_INTRUSIVE_SKIP_LIST_HRC_H
   4 #define __CDS_INTRUSIVE_SKIP_LIST_HRC_H
   5
   6 #include <cds/intrusive/skip_list_impl.h>
   7 #include <cds/gc/hrc.h>
   8
   9 //@cond
  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
  14     {
  15     public:
  16         typedef gc::HRC gc          ;   ///< Garbage collector
  17         typedef Tag     tag         ;   ///< tag
  18
  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;
  22
  23     protected:
  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
  27
  28     public:
  29         bool                    m_bDel;
  30
  31     public:
  32         /// Constructs a node of height 1 (a bottom-list node)
  33         node()
  34             : m_pNext( null_ptr<node *>())
  35             , m_nHeight(1)
  36             , m_arrNext( null_ptr<atomic_marked_ptr *>())
  37             , m_bDel( false )
  38         {}
  39
  40         ~node()
  41         {
  42             release_tower();
  43             m_pNext.store( marked_ptr(), CDS_ATOMIC::memory_order_relaxed );
  44         }
  45
  46         /// Constructs a node of height \p nHeight
  47         void make_tower( unsigned int nHeight, atomic_marked_ptr * nextTower )
  48         {
  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
  52                 );
  53
  54             m_arrNext = nextTower;
  55             m_nHeight = nHeight;
  56         }
  57
  58         atomic_marked_ptr * release_tower()
  59         {
  60             unsigned int nHeight = m_nHeight - 1;
  61             atomic_marked_ptr * pTower = m_arrNext;
  62             if ( pTower ) {
  63                 m_arrNext = null_ptr<atomic_marked_ptr *>();
  64                 m_nHeight = 1;
  65                 for ( unsigned int i = 0; i < nHeight; ++i )
  66                     pTower[i].store( marked_ptr(), CDS_ATOMIC::memory_order_release );
  67             }
  68             return pTower;
  69         }
  70
  71         atomic_marked_ptr * get_tower() const
  72         {
  73             return m_arrNext;
  74         }
  75
  76         /// Access to element of next pointer array
  77         atomic_marked_ptr& next( unsigned int nLevel )
  78         {
  79             assert( nLevel < height() );
  80             assert( nLevel == 0 || (nLevel > 0 && m_arrNext != null_ptr<atomic_marked_ptr *>() ));
  81
  82             return nLevel ? m_arrNext[ nLevel - 1] : m_pNext;
  83         }
  84
  85         /// Access to element of next pointer array (const version)
  86         atomic_marked_ptr const& next( unsigned int nLevel ) const
  87         {
  88             assert( nLevel < height() );
  89             assert( nLevel == 0 || (nLevel > 0 && m_arrNext != null_ptr<atomic_marked_ptr *>()) );
  90
  91             return nLevel ? m_arrNext[ nLevel - 1] : m_pNext;
  92         }
  93
  94         /// Access to element of next pointer array (same as \ref next function)
  95         atomic_marked_ptr& operator[]( unsigned int nLevel )
  96         {
  97             return next( nLevel );
  98         }
  99
 100         /// Access to element of next pointer array (same as \ref next function)
 101         atomic_marked_ptr const& operator[]( unsigned int nLevel ) const
 102         {
 103             return next( nLevel );
 104         }
 105
 106         /// Height of the node
 107         unsigned int height() const
 108         {
 109             return m_nHeight;
 110         }
 111
 112     protected:
 113         virtual void cleanUp( cds::gc::hrc::ThreadGC * pGC )
 114         {
 115             assert( pGC != NULL );
 116             typename gc::GuardArray<2> aGuards( *pGC );
 117
 118             unsigned int const nHeight = height();
 119             for (unsigned int i = 0; i < nHeight; ++i ) {
 120                 while ( true ) {
 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 );
 126                         continue;
 127                     }
 128                     else {
 129                         break;
 130                     }
 131                 }
 132             }
 133         }
 134
 135         virtual void terminate( cds::gc::hrc::ThreadGC * pGC, bool bConcurrent )
 136         {
 137             unsigned int const nHeight = height();
 138             if ( bConcurrent ) {
 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 ) );
 142                 }
 143             }
 144             else {
 145                 for (unsigned int i = 0; i < nHeight; ++i )
 146                     next(i).store( marked_ptr(), CDS_ATOMIC::memory_order_relaxed );
 147             }
 148         }
 149     };
 150
 151     namespace details {
 152
 153         template <typename Tag>
 154         class head_node< node< cds::gc::HRC, Tag > >
 155         {
 156             typedef node< cds::gc::HRC, Tag > node_type;
 157
 158             struct head_tower: public node_type
 159             {
 160                 typename node_type::atomic_marked_ptr   m_Tower[skip_list::c_nHeightLimit];
 161             };
 162
 163             head_tower * m_pHead;
 164
 165             struct head_disposer {
 166                 void operator()( head_tower * p )
 167                 {
 168                     delete p;
 169                 }
 170             };
 171         public:
 172             head_node( unsigned int nHeight )
 173                 : m_pHead( new head_tower() )
 174             {
 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 );
 177
 178                 m_pHead->make_tower( nHeight, m_pHead->m_Tower );
 179             }
 180
 181             ~head_node()
 182             {
 183                 cds::gc::HRC::template retire<head_disposer>( m_pHead );
 184             }
 185
 186             node_type * head()
 187             {
 188                 return static_cast<node_type *>( m_pHead );
 189             }
 190             node_type const * head() const
 191             {
 192                 return static_cast<node_type const *>( m_pHead );
 193             }
 194
 195         };
 196     } // namespace details
 197
 198 }}} // namespace cds::intrusive::skip_list
 199 //@endcond
 200
 201 #endif