3 #ifndef __CDS_INTRUSIVE_DETAILS_SINGLE_LINK_STRUCT_H
4 #define __CDS_INTRUSIVE_DETAILS_SINGLE_LINK_STRUCT_H
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>
11 namespace cds { namespace intrusive {
13 /// Definitions common for single-linked data structures
14 /** @ingroup cds_intrusive_helper
16 namespace single_link {
21 - GC - garbage collector used
22 - Tag - a tag used to distinguish between different implementation
24 template <class GC, typename Tag = opt::none>
25 struct node: public GC::container_node
27 typedef GC gc ; ///< Garbage collector
28 typedef Tag tag ; ///< tag
30 typedef typename gc::template atomic_ref<node> atomic_node_ptr ; ///< atomic pointer
32 /// Rebind node for other template parameters
33 template <class GC2, typename Tag2 = tag>
35 typedef node<GC2, Tag2> other ; ///< Rebinding result
38 atomic_node_ptr m_pNext ; ///< pointer to the next node in the container
46 // Specialization for HRC GC
47 template <typename Tag>
48 struct node< gc::HRC, Tag>: public gc::HRC::container_node
50 typedef gc::HRC gc ; ///< Garbage collector
51 typedef Tag tag ; ///< tag
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
61 virtual void cleanUp( cds::gc::hrc::ThreadGC * pGC )
63 assert( pGC != nullptr );
64 typename gc::GuardArray<2> aGuards( *pGC );
67 node * pNext = aGuards.protect( 0, m_pNext );
68 if ( pNext && pNext->m_bDeleted.load(atomics::memory_order_acquire) ) {
69 node * p = aGuards.protect( 1, pNext->m_pNext );
70 m_pNext.compare_exchange_strong( pNext, p, atomics::memory_order_acquire, atomics::memory_order_relaxed );
79 virtual void terminate( cds::gc::hrc::ThreadGC * pGC, bool bConcurrent )
82 node * pNext = m_pNext.load(atomics::memory_order_relaxed);
83 do {} while ( !m_pNext.compare_exchange_weak( pNext, nullptr, atomics::memory_order_release, atomics::memory_order_relaxed ) );
86 m_pNext.store( nullptr, atomics::memory_order_relaxed );
94 typedef cds::gc::default_gc gc;
95 typedef opt::none tag;
100 template < typename HookType, typename... Options>
103 typedef typename opt::make_options< default_hook, Options...>::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;
115 - opt::gc - garbage collector used.
118 template < typename... Options >
119 struct base_hook: public hook< opt::base_hook_tag, Options... >
124 \p MemberOffset defines offset in bytes of \ref node member into your structure.
125 Use \p offsetof macro to define \p MemberOffset
128 - opt::gc - garbage collector used.
131 template < size_t MemberOffset, typename... Options >
132 struct member_hook: public hook< opt::member_hook_tag, Options... >
135 static const size_t c_nMemberOffset = MemberOffset;
141 \p NodeTraits defines type traits for node.
142 See \ref node_traits for \p NodeTraits interface description
145 - opt::gc - garbage collector used.
148 template <typename NodeTraits, typename... Options >
149 struct traits_hook: public hook< opt::traits_hook_tag, Options... >
152 typedef NodeTraits node_traits;
157 template <typename Node>
158 struct link_checker {
160 typedef Node node_type;
163 /// Checks if the link field of node \p pNode is \p nullptr
165 An asserting is generated if \p pNode link field is not \p nullptr
167 static void is_empty( const node_type * pNode )
169 assert( pNode->m_pNext.load( atomics::memory_order_relaxed ) == nullptr );
174 template <class GC, typename Node, opt::link_check_type LinkType >
175 struct link_checker_selector;
177 template <typename Node>
178 struct link_checker_selector< gc::HRC, Node, opt::never_check_link >
180 typedef link_checker<Node> type;
183 template <typename Node>
184 struct link_checker_selector< gc::HRC, Node, opt::debug_check_link >
186 typedef link_checker<Node> type;
189 template <typename GC, typename Node>
190 struct link_checker_selector< GC, Node, opt::never_check_link >
192 typedef intrusive::opt::v::empty_link_checker<Node> type;
195 template <typename GC, typename Node>
196 struct link_checker_selector< GC, Node, opt::debug_check_link >
199 typedef link_checker<Node> type;
201 typedef intrusive::opt::v::empty_link_checker<Node> type;
205 template <typename GC, typename Node>
206 struct link_checker_selector< GC, Node, opt::always_check_link >
208 typedef link_checker<Node> type;
212 /// Metafunction for selecting appropriate link checking policy
213 template < typename Node, opt::link_check_type LinkType >
214 struct get_link_checker
217 typedef typename link_checker_selector< typename Node::gc, Node, LinkType>::type type;
221 } // namespace single_link
223 }} // namespace cds::intrusive
227 #endif // #ifndef __CDS_INTRUSIVE_DETAILS_SINGLE_LINK_STRUCT_H