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/sync/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::sync::spin
24 - Tag - a \ref cds_intrusive_hook_tag "tag"
28 ,typename Lock = cds::sync::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 sync::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 sync::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 sync::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 sync::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 /// Specifies binary functor used for comparing keys for equality (for unordered list only)
213 If \p equal_to option is not specified, \p compare is used, if \p compare is not specified, \p less is used,
214 if \p less is not specified, then \p std::equal_to<T> is used.
216 typedef opt::none equal_to;
218 /// Specifies list ordering policy
220 If \p sort is \p true, than list maintains items in sorted order, otherwise the list is unordered.
222 Note that if \p sort is \p false, than lookup operations scan entire list.
224 static const bool sort = true;
226 /// Back-off strategy
227 typedef cds::backoff::Default back_off;
229 /// Disposer for removing items
230 typedef opt::v::empty_disposer disposer;
232 /// Item counting feature; by default, disabled. Use \p cds::atomicity::item_counter to enable item counting
233 typedef atomicity::empty_item_counter item_counter;
235 /// Link fields checking feature
237 Default is \p opt::debug_check_link
239 static const opt::link_check_type link_checker = opt::debug_check_link;
241 /// C++ memory ordering model
243 Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
244 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
246 typedef opt::v::relaxed_ordering memory_model;
248 /// RCU deadlock checking policy (only for \ref cds_intrusive_LazyList_rcu "RCU-based LazyList")
250 List of available options see \p opt::rcu_check_deadlock
252 typedef opt::v::rcu_throw_deadlock rcu_check_deadlock;
255 /// Metafunction converting option list to \p lazy_list::traits
257 Supported \p Options are:
258 - \p opt::hook - hook used. Possible values are: \p lazy_list::base_hook, \p lazy_list::member_hook, \p lazy_list::traits_hook.
259 If the option is not specified, \p %lazy_list::base_hook and \p gc::HP is used.
260 - \p opt::compare - key comparison functor. No default functor is provided.
261 If the option is not specified, the \p opt::less is used.
262 - \p opt::less - specifies binary predicate used for key comparison. Default is \p std::less<T>.
263 - \p opt::equal_to - specifies binary functor for comparing keys for equality. If \p equal_to is not specified, \p compare is
264 used, \p compare is not specified, \p less is used.
265 - \p opt::sort - specifies ordering policy. Default value is \p true.
266 - \p opt::back_off - back-off strategy used. If the option is not specified, the \p cds::backoff::Default is used.
267 - \p opt::disposer - the functor used for dispose removed items. Default is \p opt::v::empty_disposer. Due the nature
268 of GC schema the disposer may be called asynchronously.
269 - \p opt::link_checker - the type of node's link fields checking. Default is \p opt::debug_check_link
270 - \p opt::item_counter - the type of item counting feature. Default is disabled (\p atomicity::empty_item_counter).
271 To enable item counting use \p atomicity::item_counter.
272 - \p opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
273 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
274 - \p opt::rcu_check_deadlock - a deadlock checking policy for \ref cds_intrusive_MichaelList_rcu "RCU-based MichaelList"
275 Default is \p opt::v::rcu_throw_deadlock
277 template <typename... Options>
279 # ifdef CDS_DOXYGEN_INVOKED
280 typedef implementation_defined type ; ///< Metafunction result
282 typedef typename cds::opt::make_options<
283 typename cds::opt::find_type_traits< traits, Options... >::type
289 } // namespace lazy_list
292 // Forward declaration
293 template < class GC, typename T, class Traits = lazy_list::traits >
297 }} // namespace cds::intrusive
299 #endif // #ifndef CDSLIB_INTRUSIVE_DETAILS_LAZY_LIST_BASE_H