3 #ifndef __CDS_INTRUSIVE_DETAILS_MICHAEL_LIST_BASE_H
4 #define __CDS_INTRUSIVE_DETAILS_MICHAEL_LIST_BASE_H
7 #include <cds/intrusive/details/base.h>
8 #include <cds/opt/compare.h>
9 #include <cds/algo/atomic.h>
10 #include <cds/details/marked_ptr.h>
11 #include <cds/urcu/options.h>
13 namespace cds { namespace intrusive {
15 /// MichaelList ordered list related definitions
16 /** @ingroup cds_intrusive_helper
18 namespace michael_list {
19 /// Michael's list node
22 - \p GC - garbage collector
23 - \p Tag - a \ref cds_intrusive_hook_tag "tag"
25 template <class GC, typename Tag = opt::none>
28 typedef GC gc ; ///< Garbage collector
29 typedef Tag tag ; ///< tag
31 typedef cds::details::marked_ptr<node, 1> marked_ptr ; ///< marked pointer
32 typedef typename gc::template atomic_marked_ptr< marked_ptr> atomic_marked_ptr ; ///< atomic marked pointer specific for GC
34 atomic_marked_ptr m_pNext ; ///< pointer to the next node in the container
36 CDS_CONSTEXPR node() CDS_NOEXCEPT
42 template <typename GC, typename Node, typename MemoryModel>
44 void operator()( Node * p )
46 typedef typename Node::marked_ptr marked_ptr;
47 p->m_pNext.store( marked_ptr(), MemoryModel::memory_order_release );
55 typedef undefined_gc gc;
56 typedef opt::none tag;
61 template < typename HookType, typename... Options>
64 typedef typename opt::make_options< default_hook, Options...>::type options;
65 typedef typename options::gc gc;
66 typedef typename options::tag tag;
67 typedef node<gc, tag> node_type;
68 typedef HookType hook_type;
75 - opt::gc - garbage collector used.
76 - opt::tag - a \ref cds_intrusive_hook_tag "tag"
78 template < typename... Options >
79 struct base_hook: public hook< opt::base_hook_tag, Options... >
84 \p MemberOffset defines offset in bytes of \ref node member into your structure.
85 Use \p offsetof macro to define \p MemberOffset
88 - opt::gc - garbage collector used.
89 - opt::tag - a \ref cds_intrusive_hook_tag "tag"
91 template < size_t MemberOffset, typename... Options >
92 struct member_hook: public hook< opt::member_hook_tag, Options... >
95 static const size_t c_nMemberOffset = MemberOffset;
101 \p NodeTraits defines type traits for node.
102 See \ref node_traits for \p NodeTraits interface description
105 - opt::gc - garbage collector used.
106 - opt::tag - a \ref cds_intrusive_hook_tag "tag"
108 template <typename NodeTraits, typename... Options >
109 struct traits_hook: public hook< opt::traits_hook_tag, Options... >
112 typedef NodeTraits node_traits;
117 template <typename Node>
121 typedef Node node_type;
124 /// Checks if the link field of node \p pNode is \p nullptr
126 An asserting is generated if \p pNode link field is not \p nullptr
128 static void is_empty( const node_type * pNode )
130 assert( pNode->m_pNext.load( atomics::memory_order_relaxed ) == nullptr );
136 template <class GC, typename Node, opt::link_check_type LinkType >
137 struct link_checker_selector;
139 template <typename GC, typename Node>
140 struct link_checker_selector< GC, Node, opt::never_check_link >
142 typedef intrusive::opt::v::empty_link_checker<Node> type;
145 template <typename GC, typename Node>
146 struct link_checker_selector< GC, Node, opt::debug_check_link >
149 typedef link_checker<Node> type;
151 typedef intrusive::opt::v::empty_link_checker<Node> type;
155 template <typename GC, typename Node>
156 struct link_checker_selector< GC, Node, opt::always_check_link >
158 typedef link_checker<Node> type;
162 /// Metafunction for selecting appropriate link checking policy
163 template < typename Node, opt::link_check_type LinkType >
164 struct get_link_checker
167 typedef typename link_checker_selector< typename Node::gc, Node, LinkType>::type type;
171 /// MichaelList traits
176 Possible values are: \p michael_list::base_hook, \p michael_list::member_hook, \p michael_list::traits_hook.
178 typedef base_hook<> hook;
180 /// Key comparison functor
182 No default functor is provided. If the option is not specified, the \p less is used.
184 typedef opt::none compare;
186 /// Specifies binary predicate used for key compare.
188 Default is \p std::less<T>.
190 typedef opt::none less;
192 /// Back-off strategy
193 typedef cds::backoff::Default back_off;
195 /// Disposer for removing items
196 typedef opt::v::empty_disposer disposer;
198 /// Item counting feature; by default, disabled. Use \p cds::atomicity::item_counter to enable item counting
199 typedef atomicity::empty_item_counter item_counter;
201 /// Link fields checking feature
203 Default is \p opt::debug_check_link
205 static const opt::link_check_type link_checker = opt::debug_check_link;
207 /// C++ memory ordering model
209 Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
210 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
212 typedef opt::v::relaxed_ordering memory_model;
214 /// RCU deadlock checking policy (only for \ref cds_intrusive_MichaelList_rcu "RCU-based MichaelList")
216 List of available policy see \p opt::rcu_check_deadlock
218 typedef opt::v::rcu_throw_deadlock rcu_check_deadlock;
221 /// Metafunction converting option list to \p michael_list::traits
223 Supported \p Options are:
224 - \p opt::hook - hook used. Possible values are: \p michael_list::base_hook, \p michael_list::member_hook, \p michael_list::traits_hook.
225 If the option is not specified, \p %michael_list::base_hook<> and \p gc::HP is used.
226 - \p opt::compare - key comparison functor. No default functor is provided.
227 If the option is not specified, the \p opt::less is used.
228 - \p opt::less - specifies binary predicate used for key comparison. Default is \p std::less<T>.
229 - \p opt::back_off - back-off strategy used. If the option is not specified, the \p cds::backoff::Default is used.
230 - \p opt::disposer - the functor used for disposing removed items. Default is \p opt::v::empty_disposer. Due the nature
231 of GC schema the disposer may be called asynchronously.
232 - \p opt::link_checker - the type of node's link fields checking. Default is \p opt::debug_check_link
233 - \p opt::item_counter - the type of item counting feature. Default is disabled (\p atomicity::empty_item_counter).
234 To enable item counting use \p atomicity::item_counter.
235 - \p opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
236 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
237 - \p opt::rcu_check_deadlock - a deadlock checking policy for \ref cds_intrusive_MichaelList_rcu "RCU-based MichaelList"
238 Default is \p opt::v::rcu_throw_deadlock
240 template <typename... Options>
242 # ifdef CDS_DOXYGEN_INVOKED
243 typedef implementation_defined type ; ///< Metafunction result
245 typedef typename cds::opt::make_options<
246 typename cds::opt::find_type_traits< traits, Options... >::type
252 } // namespace michael_list
255 // Forward declaration
256 template < class GC, typename T, class Traits = michael_list::traits >
261 /// Tag for selecting Michael list
262 //class michael_list_tag;
264 }} // namespace cds::intrusive
266 #endif // #ifndef __CDS_INTRUSIVE_DETAILS_MICHAEL_LIST_BASE_H