cds/intrusive/single_link_struct.h

   1 //$$CDS-header$$
   2
   3 #ifndef __CDS_INTRUSIVE_SINGLE_LINK_STRUCT_H
   4 #define __CDS_INTRUSIVE_SINGLE_LINK_STRUCT_H
   5
   6 #include <cds/intrusive/base.h>
   7 #include <cds/gc/default_gc.h>
   8 #include <cds/cxx11_atomic.h>
   9 #include <cds/gc/hrc.h>
  10
  11 namespace cds { namespace intrusive {
  12
  13     /// Definitions common for single-linked data structures
  14     /** @ingroup cds_intrusive_helper
  15     */
  16     namespace single_link {
  17
  18         /// Container's node
  19         /**
  20             Template parameters:
  21             - GC - garbage collector used
  22             - Tag - a tag used to distinguish between different implementation
  23         */
  24         template <class GC, typename Tag = opt::none>
  25         struct node: public GC::container_node
  26         {
  27             typedef GC              gc  ;   ///< Garbage collector
  28             typedef Tag             tag ;   ///< tag
  29
  30             typedef typename gc::template atomic_ref<node>    atomic_node_ptr    ;    ///< atomic pointer
  31
  32             /// Rebind node for other template parameters
  33             template <class GC2, typename Tag2 = tag>
  34             struct rebind {
  35                 typedef node<GC2, Tag2>  other ;    ///< Rebinding result
  36             };
  37
  38             atomic_node_ptr m_pNext ; ///< pointer to the next node in the container
  39
  40             node()
  41                 : m_pNext( nullptr )
  42             {}
  43         };
  44
  45         //@cond
  46         // Specialization for HRC GC
  47         template <typename Tag>
  48         struct node< gc::HRC, Tag>: public gc::HRC::container_node
  49         {
  50             typedef gc::HRC     gc  ;   ///< Garbage collector
  51             typedef Tag         tag ;   ///< tag
  52
  53             typedef gc::atomic_ref<node>    atomic_node_ptr    ;    ///< atomic pointer
  54             atomic_node_ptr m_pNext ; ///< pointer to the next node in the container
  55
  56             node()
  57                 : m_pNext( nullptr )
  58             {}
  59
  60         protected:
  61             virtual void cleanUp( cds::gc::hrc::ThreadGC * pGC )
  62             {
  63                 assert( pGC != nullptr );
  64                 typename gc::GuardArray<2> aGuards( *pGC );
  65
  66                 while ( true ) {
  67                     node * pNext = aGuards.protect( 0, m_pNext );
  68                     if ( pNext && pNext->m_bDeleted.load(CDS_ATOMIC::memory_order_acquire) ) {
  69                         node * p = aGuards.protect( 1, pNext->m_pNext );
  70                         m_pNext.compare_exchange_strong( pNext, p, CDS_ATOMIC::memory_order_acquire, CDS_ATOMIC::memory_order_relaxed );
  71                         continue;
  72                     }
  73                     else {
  74                         break;
  75                     }
  76                 }
  77             }
  78
  79             virtual void terminate( cds::gc::hrc::ThreadGC * pGC, bool bConcurrent )
  80             {
  81                 if ( bConcurrent ) {
  82                     node * pNext = m_pNext.load(CDS_ATOMIC::memory_order_relaxed);
  83                     do {} while ( !m_pNext.compare_exchange_weak( pNext, nullptr, CDS_ATOMIC::memory_order_release, CDS_ATOMIC::memory_order_relaxed ) );
  84                 }
  85                 else {
  86                     m_pNext.store( nullptr, CDS_ATOMIC::memory_order_relaxed );
  87                 }
  88             }
  89         };
  90         //@endcond
  91
  92         //@cond
  93         struct default_hook {
  94             typedef cds::gc::default_gc gc;
  95             typedef opt::none           tag;
  96         };
  97         //@endcond
  98
  99         //@cond
 100         template < typename HookType, CDS_DECL_OPTIONS2>
 101         struct hook
 102         {
 103             typedef typename opt::make_options< default_hook, CDS_OPTIONS2>::type  options;
 104             typedef typename options::gc    gc;
 105             typedef typename options::tag   tag;
 106             typedef node<gc, tag> node_type;
 107             typedef HookType     hook_type;
 108         };
 109         //@endcond
 110
 111
 112         /// Base hook
 113         /**
 114             \p Options are:
 115             - opt::gc - garbage collector used.
 116             - opt::tag - tag
 117         */
 118         template < CDS_DECL_OPTIONS2 >
 119         struct base_hook: public hook< opt::base_hook_tag, CDS_OPTIONS2 >
 120         {};
 121
 122         /// Member hook
 123         /**
 124             \p MemberOffset defines offset in bytes of \ref node member into your structure.
 125             Use \p offsetof macro to define \p MemberOffset
 126
 127             \p Options are:
 128             - opt::gc - garbage collector used.
 129             - opt::tag - tag
 130         */
 131         template < size_t MemberOffset, CDS_DECL_OPTIONS2 >
 132         struct member_hook: public hook< opt::member_hook_tag, CDS_OPTIONS2 >
 133         {
 134             //@cond
 135             static const size_t c_nMemberOffset = MemberOffset;
 136             //@endcond
 137         };
 138
 139         /// Traits hook
 140         /**
 141             \p NodeTraits defines type traits for node.
 142             See \ref node_traits for \p NodeTraits interface description
 143
 144             \p Options are:
 145             - opt::gc - garbage collector used.
 146             - opt::tag - tag
 147         */
 148         template <typename NodeTraits, CDS_DECL_OPTIONS2 >
 149         struct traits_hook: public hook< opt::traits_hook_tag, CDS_OPTIONS2 >
 150         {
 151             //@cond
 152             typedef NodeTraits node_traits;
 153             //@endcond
 154         };
 155
 156         /// Check link
 157         template <typename Node>
 158         struct link_checker {
 159             //@cond
 160             typedef Node node_type;
 161             //@endcond
 162
 163             /// Checks if the link field of node \p pNode is \p nullptr
 164             /**
 165                 An asserting is generated if \p pNode link field is not \p nullptr
 166             */
 167             static void is_empty( const node_type * pNode )
 168             {
 169                 assert( pNode->m_pNext.load( CDS_ATOMIC::memory_order_relaxed ) == nullptr );
 170             }
 171         };
 172
 173         //@cond
 174         template <class GC, typename Node, opt::link_check_type LinkType >
 175         struct link_checker_selector;
 176
 177         template <typename Node>
 178         struct link_checker_selector< gc::HRC, Node, opt::never_check_link >
 179         {
 180             typedef link_checker<Node>  type;
 181         };
 182
 183         template <typename Node>
 184         struct link_checker_selector< gc::HRC, Node, opt::debug_check_link >
 185         {
 186             typedef link_checker<Node>  type;
 187         };
 188
 189         template <typename GC, typename Node>
 190         struct link_checker_selector< GC, Node, opt::never_check_link >
 191         {
 192             typedef intrusive::opt::v::empty_link_checker<Node>  type;
 193         };
 194
 195         template <typename GC, typename Node>
 196         struct link_checker_selector< GC, Node, opt::debug_check_link >
 197         {
 198 #       ifdef _DEBUG
 199             typedef link_checker<Node>  type;
 200 #       else
 201             typedef intrusive::opt::v::empty_link_checker<Node>  type;
 202 #       endif
 203         };
 204
 205         template <typename GC, typename Node>
 206         struct link_checker_selector< GC, Node, opt::always_check_link >
 207         {
 208             typedef link_checker<Node>  type;
 209         };
 210         //@endcond
 211
 212         /// Metafunction for selecting appropriate link checking policy
 213         template < typename Node, opt::link_check_type LinkType >
 214         struct get_link_checker
 215         {
 216             //@cond
 217             typedef typename link_checker_selector< typename Node::gc, Node, LinkType>::type type;
 218             //@endcond
 219         };
 220
 221     }   // namespace single_link
 222
 223 }}  // namespace cds::intrusive
 224
 225
 226
 227 #endif // #ifndef __CDS_INTRUSIVE_SINGLE_LINK_STRUCT_H