3 #ifndef CDSLIB_INTRUSIVE_DETAILS_LAZY_LIST_BASE_H
4 #define CDSLIB_INTRUSIVE_DETAILS_LAZY_LIST_BASE_H
6 #include <cds/intrusive/details/base.h>
7 #include <cds/opt/compare.h>
8 #include <cds/details/marked_ptr.h>
9 #include <cds/details/make_const_type.h>
10 #include <cds/lock/spinlock.h>
11 #include <cds/urcu/options.h>
13 namespace cds { namespace intrusive {
15 /// LazyList ordered list related definitions
16 /** @ingroup cds_intrusive_helper
22 - GC - garbage collector
23 - Lock - lock type. Default is \p cds::lock::Spin
24 - Tag - a \ref cds_intrusive_hook_tag "tag"
28 ,typename Lock = cds::lock::Spin
29 ,typename Tag = opt::none
33 typedef GC gc ; ///< Garbage collector
34 typedef Lock lock_type ; ///< Lock type
35 typedef Tag tag ; ///< tag
37 typedef cds::details::marked_ptr<node, 1> marked_ptr ; ///< marked pointer
38 typedef typename gc::template atomic_marked_ptr< marked_ptr> atomic_marked_ptr ; ///< atomic marked pointer specific for GC
40 atomic_marked_ptr m_pNext; ///< pointer to the next node in the list + logical deletion mark
41 mutable lock_type m_Lock; ///< Node lock
43 /// Checks if node is marked
44 bool is_marked() const
46 return m_pNext.load(atomics::memory_order_relaxed).bits() != 0;
56 template <typename GC, typename Node, typename MemoryModel>
58 void operator()( Node * p )
60 typedef typename Node::marked_ptr marked_ptr;
61 p->m_pNext.store( marked_ptr(), MemoryModel::memory_order_release );
69 typedef undefined_gc gc;
70 typedef opt::none tag;
71 typedef lock::Spin lock_type;
76 template < typename HookType, typename... Options>
79 typedef typename opt::make_options< default_hook, Options...>::type options;
80 typedef typename options::gc gc;
81 typedef typename options::tag tag;
82 typedef typename options::lock_type lock_type;
83 typedef node<gc, lock_type, tag> node_type;
84 typedef HookType hook_type;
91 - opt::gc - garbage collector
92 - opt::lock_type - lock type used for node locking. Default is lock::Spin
93 - opt::tag - a \ref cds_intrusive_hook_tag "tag"
95 template < typename... Options >
96 struct base_hook: public hook< opt::base_hook_tag, Options... >
101 \p MemberOffset defines offset in bytes of \ref node member into your structure.
102 Use \p offsetof macro to define \p MemberOffset
105 - opt::gc - garbage collector
106 - opt::lock_type - lock type used for node locking. Default is lock::Spin
107 - opt::tag - a \ref cds_intrusive_hook_tag "tag"
109 template < size_t MemberOffset, typename... Options >
110 struct member_hook: public hook< opt::member_hook_tag, Options... >
113 static const size_t c_nMemberOffset = MemberOffset;
119 \p NodeTraits defines type traits for node.
120 See \ref node_traits for \p NodeTraits interface description
123 - opt::gc - garbage collector used.
124 - opt::lock_type - lock type used for node locking. Default is lock::Spin
125 - opt::tag - a \ref cds_intrusive_hook_tag "tag"
127 template <typename NodeTraits, typename... Options >
128 struct traits_hook: public hook< opt::traits_hook_tag, Options... >
131 typedef NodeTraits node_traits;
136 template <typename Node>
140 typedef Node node_type;
143 /// Checks if the link field of node \p pNode is \p nullptr
145 An asserting is generated if \p pNode link field is not \p nullptr
147 static void is_empty( node_type const * pNode )
149 assert( pNode->m_pNext.load( atomics::memory_order_relaxed ) == nullptr );
155 template <class GC, typename Node, opt::link_check_type LinkType >
156 struct link_checker_selector;
158 template <typename GC, typename Node>
159 struct link_checker_selector< GC, Node, opt::never_check_link >
161 typedef intrusive::opt::v::empty_link_checker<Node> type;
164 template <typename GC, typename Node>
165 struct link_checker_selector< GC, Node, opt::debug_check_link >
168 typedef link_checker<Node> type;
170 typedef intrusive::opt::v::empty_link_checker<Node> type;
174 template <typename GC, typename Node>
175 struct link_checker_selector< GC, Node, opt::always_check_link >
177 typedef link_checker<Node> type;
181 /// Metafunction for selecting appropriate link checking policy
182 template < typename Node, opt::link_check_type LinkType >
183 struct get_link_checker
186 typedef typename link_checker_selector< typename Node::gc, Node, LinkType>::type type;
195 Possible values are: \p lazy_list::base_hook, \p lazy_list::member_hook, \p lazy_list::traits_hook.
197 typedef base_hook<> hook;
199 /// Key comparing functor
201 No default functor is provided. If the functor is not specified, the \p less is used.
203 typedef opt::none compare;
205 /// Specifies binary predicate used for comparing keys
207 Default is \p std::less<T>.
209 typedef opt::none less;
211 /// Back-off strategy
212 typedef cds::backoff::Default back_off;
214 /// Disposer for removing items
215 typedef opt::v::empty_disposer disposer;
217 /// Item counting feature; by default, disabled. Use \p cds::atomicity::item_counter to enable item counting
218 typedef atomicity::empty_item_counter item_counter;
220 /// Link fields checking feature
222 Default is \p opt::debug_check_link
224 static const opt::link_check_type link_checker = opt::debug_check_link;
226 /// C++ memory ordering model
228 Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
229 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
231 typedef opt::v::relaxed_ordering memory_model;
233 /// RCU deadlock checking policy (only for \ref cds_intrusive_LazyList_rcu "RCU-based LazyList")
235 List of available options see \p opt::rcu_check_deadlock
237 typedef opt::v::rcu_throw_deadlock rcu_check_deadlock;
240 /// Metafunction converting option list to \p lazy_list::traits
242 Supported \p Options are:
243 - \p opt::hook - hook used. Possible values are: \p lazy_list::base_hook, \p lazy_list::member_hook, \p lazy_list::traits_hook.
244 If the option is not specified, \p %lazy_list::base_hook and \p gc::HP is used.
245 - \p opt::compare - key comparison functor. No default functor is provided.
246 If the option is not specified, the \p opt::less is used.
247 - \p opt::less - specifies binary predicate used for key comparison. Default is \p std::less<T>.
248 - \p opt::back_off - back-off strategy used. If the option is not specified, the \p cds::backoff::Default is used.
249 - \p opt::disposer - the functor used for dispose removed items. Default is \p opt::v::empty_disposer. Due the nature
250 of GC schema the disposer may be called asynchronously.
251 - \p opt::link_checker - the type of node's link fields checking. Default is \p opt::debug_check_link
252 - \p opt::item_counter - the type of item counting feature. Default is disabled (\p atomicity::empty_item_counter).
253 To enable item counting use \p atomicity::item_counter.
254 - \p opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
255 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
256 - \p opt::rcu_check_deadlock - a deadlock checking policy for \ref cds_intrusive_MichaelList_rcu "RCU-based MichaelList"
257 Default is \p opt::v::rcu_throw_deadlock
259 template <typename... Options>
261 # ifdef CDS_DOXYGEN_INVOKED
262 typedef implementation_defined type ; ///< Metafunction result
264 typedef typename cds::opt::make_options<
265 typename cds::opt::find_type_traits< traits, Options... >::type
271 } // namespace lazy_list
274 // Forward declaration
275 template < class GC, typename T, class Traits = lazy_list::traits >
279 }} // namespace cds::intrusive
281 #endif // #ifndef CDSLIB_INTRUSIVE_DETAILS_LAZY_LIST_BASE_H