3 #ifndef __CDS_INTRUSIVE_LAZY_LIST_BASE_H
4 #define __CDS_INTRUSIVE_LAZY_LIST_BASE_H
6 #include <cds/intrusive/base.h>
7 #include <cds/opt/compare.h>
8 #include <cds/details/marked_ptr.h>
10 #include <cds/details/make_const_type.h>
11 #include <boost/type_traits/is_same.hpp>
12 #include <cds/lock/spinlock.h>
13 #include <cds/urcu/options.h>
15 namespace cds { namespace intrusive {
17 /// LazyList ordered list related definitions
18 /** @ingroup cds_intrusive_helper
24 - GC - garbage collector
25 - Lock - lock type. Default is cds::lock::Spin
26 - Tag - a tag used to distinguish between different implementation. An incomplete type can be used as a tag.
30 ,typename Lock = lock::Spin
31 ,typename Tag = opt::none
35 typedef GC gc ; ///< Garbage collector
36 typedef Lock lock_type ; ///< Lock type
37 typedef Tag tag ; ///< tag
39 typedef cds::details::marked_ptr<node, 1> marked_ptr ; ///< marked pointer
40 typedef typename gc::template atomic_marked_ptr< marked_ptr> atomic_marked_ptr ; ///< atomic marked pointer specific for GC
42 atomic_marked_ptr m_pNext ; ///< pointer to the next node in the list + logical deletion mark
43 mutable lock_type m_Lock ; ///< Node lock
45 /// Checks if node is marked
46 bool is_marked() const
48 return m_pNext.load(CDS_ATOMIC::memory_order_relaxed).bits() != 0;
58 template <typename GC, typename NodeType, typename Alloc >
61 typedef NodeType node_type;
71 node_type const * head() const
79 node_type const * tail() const
87 template <typename GC, typename Node, typename MemoryModel>
89 void operator()( Node * p )
91 typedef typename Node::marked_ptr marked_ptr;
92 p->m_pNext.store( marked_ptr(), MemoryModel::memory_order_release );
100 typedef undefined_gc gc;
101 typedef opt::none tag;
102 typedef lock::Spin lock_type;
107 template < typename HookType, CDS_DECL_OPTIONS3>
110 typedef typename opt::make_options< default_hook, CDS_OPTIONS3>::type options;
111 typedef typename options::gc gc;
112 typedef typename options::tag tag;
113 typedef typename options::lock_type lock_type;
114 typedef node<gc, lock_type, tag> node_type;
115 typedef HookType hook_type;
122 - opt::gc - garbage collector used.
123 - opt::lock_type - lock type used for node locking. Default is lock::Spin
126 template < CDS_DECL_OPTIONS3 >
127 struct base_hook: public hook< opt::base_hook_tag, CDS_OPTIONS3 >
132 \p MemberOffset defines offset in bytes of \ref node member into your structure.
133 Use \p offsetof macro to define \p MemberOffset
136 - opt::gc - garbage collector used.
137 - opt::lock_type - lock type used for node locking. Default is lock::Spin
140 template < size_t MemberOffset, CDS_DECL_OPTIONS3 >
141 struct member_hook: public hook< opt::member_hook_tag, CDS_OPTIONS3 >
144 static const size_t c_nMemberOffset = MemberOffset;
150 \p NodeTraits defines type traits for node.
151 See \ref node_traits for \p NodeTraits interface description
154 - opt::gc - garbage collector used.
155 - opt::lock_type - lock type used for node locking. Default is lock::Spin
158 template <typename NodeTraits, CDS_DECL_OPTIONS3 >
159 struct traits_hook: public hook< opt::traits_hook_tag, CDS_OPTIONS3 >
162 typedef NodeTraits node_traits;
167 template <typename Node>
171 typedef Node node_type;
174 /// Checks if the link field of node \p pNode is NULL
176 An asserting is generated if \p pNode link field is not NULL
178 static void is_empty( node_type const * pNode )
180 assert( pNode->m_pNext.load( CDS_ATOMIC::memory_order_relaxed ) == nullptr );
185 template <class GC, typename Node, opt::link_check_type LinkType >
186 struct link_checker_selector;
188 template <typename GC, typename Node>
189 struct link_checker_selector< GC, Node, opt::never_check_link >
191 typedef intrusive::opt::v::empty_link_checker<Node> type;
194 template <typename GC, typename Node>
195 struct link_checker_selector< GC, Node, opt::debug_check_link >
198 typedef link_checker<Node> type;
200 typedef intrusive::opt::v::empty_link_checker<Node> type;
204 template <typename GC, typename Node>
205 struct link_checker_selector< GC, Node, opt::always_check_link >
207 typedef link_checker<Node> type;
211 /// Metafunction for selecting appropriate link checking policy
212 template < typename Node, opt::link_check_type LinkType >
213 struct get_link_checker
216 typedef typename link_checker_selector< typename Node::gc, Node, LinkType>::type type;
220 /// Type traits for LazyList class
225 Possible values are: lazy_list::base_hook, lazy_list::member_hook, lazy_list::traits_hook.
227 typedef base_hook<> hook;
229 /// Key comparison functor
231 No default functor is provided. If the option is not specified, the \p less is used.
233 typedef opt::none compare;
235 /// specifies binary predicate used for key comparison.
237 Default is \p std::less<T>.
239 typedef opt::none less;
241 /// back-off strategy used
243 If the option is not specified, the cds::backoff::Default is used.
245 typedef cds::backoff::Default back_off;
249 the functor used for dispose removed items. Default is opt::v::empty_disposer.
251 typedef opt::v::empty_disposer disposer;
255 The type for item counting feature.
256 Default is no item counter (\ref atomicity::empty_item_counter)
258 typedef atomicity::empty_item_counter item_counter;
260 /// Link fields checking feature
262 Default is \ref opt::debug_check_link
264 static const opt::link_check_type link_checker = opt::debug_check_link;
268 For intrusive lazy list an allocator is needed for dummy tail node allocation.
270 typedef CDS_DEFAULT_ALLOCATOR allocator;
272 /// C++ memory ordering model
274 List of available memory ordering see opt::memory_model
276 typedef opt::v::relaxed_ordering memory_model;
278 /// RCU deadlock checking policy (only for \ref cds_intrusive_LazyList_rcu "RCU-based LazyList")
280 List of available options see opt::rcu_check_deadlock
282 typedef opt::v::rcu_throw_deadlock rcu_check_deadlock;
285 // for internal use only!!!
286 typedef opt::none boundary_node_type;
290 /// Metafunction converting option list to traits
292 This is a wrapper for <tt> cds::opt::make_options< type_traits, Options...> </tt>
294 See \ref LazyList, \ref type_traits, \ref cds::opt::make_options.
297 template <CDS_DECL_OPTIONS11>
299 # ifdef CDS_DOXYGEN_INVOKED
300 typedef implementation_defined type ; ///< Metafunction result
302 typedef typename cds::opt::make_options<
303 typename cds::opt::find_type_traits< type_traits, CDS_OPTIONS11 >::type
309 } // namespace lazy_list
312 // Forward declaration
313 template < class GC, typename T, class Traits = lazy_list::type_traits >
318 }} // namespace cds::intrusive
320 #endif // #ifndef __CDS_INTRUSIVE_LAZY_LIST_BASE_H