2 This file is a part of libcds - Concurrent Data Structures library
4 (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2017
6 Source code repo: http://github.com/khizmax/libcds/
7 Download: http://sourceforge.net/projects/libcds/files/
9 Redistribution and use in source and binary forms, with or without
10 modification, are permitted provided that the following conditions are met:
12 * Redistributions of source code must retain the above copyright notice, this
13 list of conditions and the following disclaimer.
15 * Redistributions in binary form must reproduce the above copyright notice,
16 this list of conditions and the following disclaimer in the documentation
17 and/or other materials provided with the distribution.
19 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
20 AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
21 IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
22 DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
23 FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
24 DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
25 SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
26 CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
27 OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
28 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
31 #ifndef CDSLIB_INTRUSIVE_DETAILS_MICHAEL_LIST_BASE_H
32 #define CDSLIB_INTRUSIVE_DETAILS_MICHAEL_LIST_BASE_H
34 #include <type_traits>
35 #include <cds/intrusive/details/base.h>
36 #include <cds/opt/compare.h>
37 #include <cds/algo/atomic.h>
38 #include <cds/details/marked_ptr.h>
39 #include <cds/urcu/options.h>
41 namespace cds { namespace intrusive {
43 /// MichaelList ordered list related definitions
44 /** @ingroup cds_intrusive_helper
46 namespace michael_list {
47 /// Michael's list node
50 - \p GC - garbage collector
51 - \p Tag - a \ref cds_intrusive_hook_tag "tag"
53 template <class GC, typename Tag = opt::none>
56 typedef GC gc ; ///< Garbage collector
57 typedef Tag tag ; ///< tag
59 typedef cds::details::marked_ptr<node, 1> marked_ptr; ///< marked pointer
60 typedef typename gc::template atomic_marked_ptr<marked_ptr> atomic_marked_ptr; ///< atomic marked pointer specific for GC
62 atomic_marked_ptr m_pNext ; ///< pointer to the next node in the container
64 constexpr node() noexcept
70 template <typename GC, typename Node, typename MemoryModel>
72 void operator()( Node * p )
74 typedef typename Node::marked_ptr marked_ptr;
75 p->m_pNext.store( marked_ptr(), MemoryModel::memory_order_release );
83 typedef undefined_gc gc;
84 typedef opt::none tag;
89 template < typename HookType, typename... Options>
92 typedef typename opt::make_options< default_hook, Options...>::type options;
93 typedef typename options::gc gc;
94 typedef typename options::tag tag;
95 typedef node<gc, tag> node_type;
96 typedef HookType hook_type;
103 - opt::gc - garbage collector used.
104 - opt::tag - a \ref cds_intrusive_hook_tag "tag"
106 template < typename... Options >
107 struct base_hook: public hook< opt::base_hook_tag, Options... >
112 \p MemberOffset defines offset in bytes of \ref node member into your structure.
113 Use \p offsetof macro to define \p MemberOffset
116 - opt::gc - garbage collector used.
117 - opt::tag - a \ref cds_intrusive_hook_tag "tag"
119 template < size_t MemberOffset, typename... Options >
120 struct member_hook: public hook< opt::member_hook_tag, Options... >
123 static const size_t c_nMemberOffset = MemberOffset;
129 \p NodeTraits defines type traits for node.
130 See \ref node_traits for \p NodeTraits interface description
133 - opt::gc - garbage collector used.
134 - opt::tag - a \ref cds_intrusive_hook_tag "tag"
136 template <typename NodeTraits, typename... Options >
137 struct traits_hook: public hook< opt::traits_hook_tag, Options... >
140 typedef NodeTraits node_traits;
145 template <typename Node>
149 typedef Node node_type;
152 /// Checks if the link field of node \p pNode is \p nullptr
154 An asserting is generated if \p pNode link field is not \p nullptr
156 static void is_empty( const node_type * pNode )
158 assert( pNode->m_pNext.load( atomics::memory_order_relaxed ) == nullptr );
164 template <class GC, typename Node, opt::link_check_type LinkType >
165 struct link_checker_selector;
167 template <typename GC, typename Node>
168 struct link_checker_selector< GC, Node, opt::never_check_link >
170 typedef intrusive::opt::v::empty_link_checker<Node> type;
173 template <typename GC, typename Node>
174 struct link_checker_selector< GC, Node, opt::debug_check_link >
177 typedef link_checker<Node> type;
179 typedef intrusive::opt::v::empty_link_checker<Node> type;
183 template <typename GC, typename Node>
184 struct link_checker_selector< GC, Node, opt::always_check_link >
186 typedef link_checker<Node> type;
190 /// Metafunction for selecting appropriate link checking policy
191 template < typename Node, opt::link_check_type LinkType >
192 struct get_link_checker
195 typedef typename link_checker_selector< typename Node::gc, Node, LinkType>::type type;
200 /// \p MichaelList internal statistics
201 template <typename EventCounter = cds::atomicity::event_counter>
203 typedef EventCounter event_counter; ///< Event counter type
205 event_counter m_nInsertSuccess; ///< Number of success \p insert() operations
206 event_counter m_nInsertFailed; ///< Number of failed \p insert() operations
207 event_counter m_nInsertRetry; ///< Number of attempts to insert new item
208 event_counter m_nUpdateNew; ///< Number of new item inserted for \p update()
209 event_counter m_nUpdateExisting; ///< Number of existing item updates
210 event_counter m_nUpdateFailed; ///< Number of failed \p update() call
211 event_counter m_nUpdateRetry; ///< Number of attempts to \p update() the item
212 event_counter m_nUpdateMarked; ///< Number of attempts to \p update() logically deleted (marked) items
213 event_counter m_nEraseSuccess; ///< Number of successful \p erase(), \p unlink(), \p extract() operations
214 event_counter m_nEraseFailed; ///< Number of failed \p erase(), \p unlink(), \p extract() operations
215 event_counter m_nEraseRetry; ///< Number of attempts to \p erase() an item
216 event_counter m_nFindSuccess; ///< Number of successful \p find() and \p get() operations
217 event_counter m_nFindFailed; ///< Number of failed \p find() and \p get() operations
219 event_counter m_nHelpingSuccess; ///< Number of successful help attempts to remove marked item during searching
220 event_counter m_nHelpingFailed; ///< Number if failed help attempts to remove marked item during searching
223 void onInsertSuccess() { ++m_nInsertSuccess; }
224 void onInsertFailed() { ++m_nInsertFailed; }
225 void onInsertRetry() { ++m_nInsertRetry; }
226 void onUpdateNew() { ++m_nUpdateNew; }
227 void onUpdateExisting() { ++m_nUpdateExisting; }
228 void onUpdateFailed() { ++m_nUpdateFailed; }
229 void onUpdateRetry() { ++m_nUpdateRetry; }
230 void onUpdateMarked() { ++m_nUpdateMarked; }
231 void onEraseSuccess() { ++m_nEraseSuccess; }
232 void onEraseFailed() { ++m_nEraseFailed; }
233 void onEraseRetry() { ++m_nEraseRetry; }
234 void onFindSuccess() { ++m_nFindSuccess; }
235 void onFindFailed() { ++m_nFindFailed; }
237 void onHelpingSuccess() { ++m_nHelpingSuccess; }
238 void onHelpingFailed() { ++m_nHelpingFailed; }
242 /// \p MichaelList empty internal statistics
245 void onInsertSuccess() const {}
246 void onInsertFailed() const {}
247 void onInsertRetry() const {}
248 void onUpdateNew() const {}
249 void onUpdateExisting() const {}
250 void onUpdateFailed() const {}
251 void onUpdateRetry() const {}
252 void onUpdateMarked() const {}
253 void onEraseSuccess() const {}
254 void onEraseFailed() const {}
255 void onEraseRetry() const {}
256 void onFindSuccess() const {}
257 void onFindFailed() const {}
259 void onHelpingSuccess() const {}
260 void onHelpingFailed() const {}
265 template <typename Stat = michael_list::stat<>>
266 struct wrapped_stat {
267 typedef Stat stat_type;
269 wrapped_stat( stat_type& st )
273 void onInsertSuccess() { m_stat.onInsertSuccess(); }
274 void onInsertFailed() { m_stat.onInsertFailed(); }
275 void onInsertRetry() { m_stat.onInsertRetry(); }
276 void onUpdateNew() { m_stat.onUpdateNew(); }
277 void onUpdateExisting() { m_stat.onUpdateExisting(); }
278 void onUpdateFailed() { m_stat.onUpdateFailed(); }
279 void onUpdateRetry() { m_stat.onUpdateRetry(); }
280 void onUpdateMarked() { m_stat.onUpdateMarked(); }
281 void onEraseSuccess() { m_stat.onEraseSuccess(); }
282 void onEraseFailed() { m_stat.onEraseFailed(); }
283 void onEraseRetry() { m_stat.onEraseRetry(); }
284 void onFindSuccess() { m_stat.onFindSuccess(); }
285 void onFindFailed() { m_stat.onFindFailed(); }
287 void onHelpingSuccess() { m_stat.onHelpingSuccess(); }
288 void onHelpingFailed() { m_stat.onHelpingFailed(); }
294 /// MichaelList traits
299 Possible values are: \p michael_list::base_hook, \p michael_list::member_hook, \p michael_list::traits_hook.
301 typedef base_hook<> hook;
303 /// Key comparison functor
305 No default functor is provided. If the option is not specified, the \p less is used.
307 typedef opt::none compare;
309 /// Specifies binary predicate used for key compare.
311 Default is \p std::less<T>.
313 typedef opt::none less;
315 /// Back-off strategy
316 typedef cds::backoff::Default back_off;
318 /// Disposer for removing items
319 typedef opt::v::empty_disposer disposer;
321 /// Item counting feature; by default, disabled. Use \p cds::atomicity::item_counter or \p atomicity::cache_friendly_item_counter to enable item counting
322 typedef atomicity::empty_item_counter item_counter;
324 /// Internal statistics
326 By default, internal statistics is disabled (\p michael_list::empty_stat).
327 Use \p michael_list::stat to enable it.
329 typedef empty_stat stat;
331 /// Link fields checking feature
333 Default is \p opt::debug_check_link
335 static const opt::link_check_type link_checker = opt::debug_check_link;
337 /// C++ memory ordering model
339 Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
340 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
342 typedef opt::v::relaxed_ordering memory_model;
344 /// RCU deadlock checking policy (only for \ref cds_intrusive_MichaelList_rcu "RCU-based MichaelList")
346 List of available policy see \p opt::rcu_check_deadlock
348 typedef opt::v::rcu_throw_deadlock rcu_check_deadlock;
351 /// Metafunction converting option list to \p michael_list::traits
353 Supported \p Options are:
354 - \p opt::hook - hook used. Possible values are: \p michael_list::base_hook, \p michael_list::member_hook, \p michael_list::traits_hook.
355 If the option is not specified, \p %michael_list::base_hook<> and \p gc::HP is used.
356 - \p opt::compare - key comparison functor. No default functor is provided.
357 If the option is not specified, the \p opt::less is used.
358 - \p opt::less - specifies binary predicate used for key comparison. Default is \p std::less<T>.
359 - \p opt::back_off - back-off strategy used. If the option is not specified, the \p cds::backoff::Default is used.
360 - \p opt::disposer - the functor used for disposing removed items. Default is \p opt::v::empty_disposer. Due the nature
361 of GC schema the disposer may be called asynchronously.
362 - \p opt::link_checker - the type of node's link fields checking. Default is \p opt::debug_check_link
363 - \p opt::item_counter - the type of item counting feature. Default is disabled (\p atomicity::empty_item_counter).
364 To enable item counting use \p atomicity::item_counter or \p atomicity::cache_friendly_item_counter
365 - \p opt::stat - internal statistics. By default, it is disabled (\p michael_list::empty_stat).
366 To enable it use \p michael_list::stat
367 - \p opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
368 or \p opt::v::sequential_consistent (sequentially consistent memory model).
369 - \p opt::rcu_check_deadlock - a deadlock checking policy for \ref cds_intrusive_MichaelList_rcu "RCU-based MichaelList"
370 Default is \p opt::v::rcu_throw_deadlock
372 template <typename... Options>
374 # ifdef CDS_DOXYGEN_INVOKED
375 typedef implementation_defined type ; ///< Metafunction result
377 typedef typename cds::opt::make_options<
378 typename cds::opt::find_type_traits< traits, Options... >::type
386 template <typename Stat>
387 struct select_stat_wrapper
390 typedef michael_list::wrapped_stat<Stat> wrapped_stat;
397 struct select_stat_wrapper< empty_stat >
399 typedef empty_stat stat;
400 typedef empty_stat wrapped_stat;
406 template <typename Stat>
407 struct select_stat_wrapper< michael_list::wrapped_stat<Stat>>: public select_stat_wrapper< Stat >
412 } // namespace michael_list
415 // Forward declaration
416 template < class GC, typename T, class Traits = michael_list::traits >
422 template <typename List>
423 struct is_michael_list {
429 template <typename GC, typename T, typename Traits>
430 struct is_michael_list< MichaelList< GC, T, Traits >> {
437 }} // namespace cds::intrusive
439 #endif // #ifndef CDSLIB_INTRUSIVE_DETAILS_MICHAEL_LIST_BASE_H