3 #ifndef __CDS_INTRUSIVE_MICHAEL_LIST_BASE_H
4 #define __CDS_INTRUSIVE_MICHAEL_LIST_BASE_H
7 #include <cds/intrusive/base.h>
8 #include <cds/opt/compare.h>
9 #include <cds/cxx11_atomic.h>
10 #include <cds/details/marked_ptr.h>
12 #include <cds/details/make_const_type.h>
13 #include <cds/urcu/options.h>
15 namespace cds { namespace intrusive {
17 /// MichaelList ordered list related definitions
18 /** @ingroup cds_intrusive_helper
20 namespace michael_list {
21 /// Michael's list node
24 - GC - garbage collector
25 - Tag - a tag used to distinguish between different implementation
27 template <class GC, typename Tag = opt::none>
30 typedef GC gc ; ///< Garbage collector
31 typedef Tag tag ; ///< tag
33 typedef cds::details::marked_ptr<node, 1> marked_ptr ; ///< marked pointer
34 typedef typename gc::template atomic_marked_ptr< marked_ptr> atomic_marked_ptr ; ///< atomic marked pointer specific for GC
36 atomic_marked_ptr m_pNext ; ///< pointer to the next node in the container
38 CDS_CONSTEXPR node() CDS_NOEXCEPT
44 template <typename GC, typename Node, typename MemoryModel>
46 void operator()( Node * p )
48 typedef typename Node::marked_ptr marked_ptr;
49 p->m_pNext.store( marked_ptr(), MemoryModel::memory_order_release );
57 typedef undefined_gc gc;
58 typedef opt::none tag;
63 template < typename HookType, typename... Options>
66 typedef typename opt::make_options< default_hook, Options...>::type options;
67 typedef typename options::gc gc;
68 typedef typename options::tag tag;
69 typedef node<gc, tag> node_type;
70 typedef HookType hook_type;
77 - opt::gc - garbage collector used.
80 template < typename... Options >
81 struct base_hook: public hook< opt::base_hook_tag, Options... >
86 \p MemberOffset defines offset in bytes of \ref node member into your structure.
87 Use \p offsetof macro to define \p MemberOffset
90 - opt::gc - garbage collector used.
93 template < size_t MemberOffset, typename... Options >
94 struct member_hook: public hook< opt::member_hook_tag, Options... >
97 static const size_t c_nMemberOffset = MemberOffset;
103 \p NodeTraits defines type traits for node.
104 See \ref node_traits for \p NodeTraits interface description
107 - opt::gc - garbage collector used.
110 template <typename NodeTraits, typename... Options >
111 struct traits_hook: public hook< opt::traits_hook_tag, Options... >
114 typedef NodeTraits node_traits;
119 template <typename Node>
123 typedef Node node_type;
126 /// Checks if the link field of node \p pNode is \p nullptr
128 An asserting is generated if \p pNode link field is not \p nullptr
130 static void is_empty( const node_type * pNode )
132 assert( pNode->m_pNext.load( atomics::memory_order_relaxed ) == nullptr );
137 template <class GC, typename Node, opt::link_check_type LinkType >
138 struct link_checker_selector;
140 template <typename GC, typename Node>
141 struct link_checker_selector< GC, Node, opt::never_check_link >
143 typedef intrusive::opt::v::empty_link_checker<Node> type;
146 template <typename GC, typename Node>
147 struct link_checker_selector< GC, Node, opt::debug_check_link >
150 typedef link_checker<Node> type;
152 typedef intrusive::opt::v::empty_link_checker<Node> type;
156 template <typename GC, typename Node>
157 struct link_checker_selector< GC, Node, opt::always_check_link >
159 typedef link_checker<Node> type;
163 /// Metafunction for selecting appropriate link checking policy
164 template < typename Node, opt::link_check_type LinkType >
165 struct get_link_checker
168 typedef typename link_checker_selector< typename Node::gc, Node, LinkType>::type type;
172 /// Type traits for MichaelList class
177 Possible values are: michael_list::base_hook, michael_list::member_hook, michael_list::traits_hook.
179 typedef base_hook<> hook;
181 /// Key comparison functor
183 No default functor is provided. If the option is not specified, the \p less is used.
185 typedef opt::none compare;
187 /// specifies binary predicate used for key compare.
189 Default is \p std::less<T>.
191 typedef opt::none less;
193 /// back-off strategy used
195 If the option is not specified, the cds::backoff::Default is used.
197 typedef cds::backoff::Default back_off;
201 the functor used for dispose removed items. Default is opt::v::empty_disposer.
203 typedef opt::v::empty_disposer disposer;
207 The type for item counting feature.
208 Default is no item counter (\ref atomicity::empty_item_counter)
210 typedef atomicity::empty_item_counter item_counter;
212 /// Link fields checking feature
214 Default is \ref opt::debug_check_link
216 static const opt::link_check_type link_checker = opt::debug_check_link;
218 /// C++ memory ordering model
220 List of available memory ordering see opt::memory_model
222 typedef opt::v::relaxed_ordering memory_model;
224 /// RCU deadlock checking policy (only for \ref cds_intrusive_MichaelList_rcu "RCU-based MichaelList")
226 List of available options see opt::rcu_check_deadlock
228 typedef opt::v::rcu_throw_deadlock rcu_check_deadlock;
231 /// Metafunction converting option list to traits
233 This is a wrapper for <tt> cds::opt::make_options< type_traits, Options...> </tt>
234 \p Options list see \ref MichaelList.
236 template <typename... Options>
238 # ifdef CDS_DOXYGEN_INVOKED
239 typedef implementation_defined type ; ///< Metafunction result
241 typedef typename cds::opt::make_options<
242 typename cds::opt::find_type_traits< type_traits, Options... >::type
245 //typedef typename cds::opt::make_options< type_traits, Options...>::type type ; ///< Result of metafunction
249 } // namespace michael_list
252 // Forward declaration
253 template < class GC, typename T, class Traits = michael_list::type_traits >
258 /// Tag for selecting Michael list
259 //class michael_list_tag;
261 }} // namespace cds::intrusive
263 #endif // #ifndef __CDS_INTRUSIVE_MICHAEL_LIST_BASE_H