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_LAZY_LIST_BASE_H
32 #define CDSLIB_INTRUSIVE_DETAILS_LAZY_LIST_BASE_H
34 #include <cds/intrusive/details/base.h>
35 #include <cds/opt/compare.h>
36 #include <cds/details/marked_ptr.h>
37 #include <cds/details/make_const_type.h>
38 #include <cds/sync/spinlock.h>
39 #include <cds/urcu/options.h>
41 namespace cds { namespace intrusive {
43 /// LazyList ordered list related definitions
44 /** @ingroup cds_intrusive_helper
50 - GC - garbage collector
51 - Lock - lock type. Default is \p cds::sync::spin
52 - Tag - a \ref cds_intrusive_hook_tag "tag"
56 ,typename Lock = cds::sync::spin
57 ,typename Tag = opt::none
61 typedef GC gc ; ///< Garbage collector
62 typedef Lock lock_type ; ///< Lock type
63 typedef Tag tag ; ///< tag
65 typedef cds::details::marked_ptr<node, 1> marked_ptr ; ///< marked pointer
66 typedef typename gc::template atomic_marked_ptr< marked_ptr> atomic_marked_ptr ; ///< atomic marked pointer specific for GC
68 atomic_marked_ptr m_pNext; ///< pointer to the next node in the list + logical deletion mark
69 mutable lock_type m_Lock; ///< Node lock
71 /// Checks if node is marked
72 bool is_marked() const
74 return m_pNext.load(atomics::memory_order_relaxed).bits() != 0;
84 template <typename GC, typename Node, typename MemoryModel>
86 void operator()( Node * p )
88 typedef typename Node::marked_ptr marked_ptr;
89 p->m_pNext.store( marked_ptr(), MemoryModel::memory_order_release );
97 typedef undefined_gc gc;
98 typedef opt::none tag;
99 typedef sync::spin lock_type;
104 template < typename HookType, typename... Options>
107 typedef typename opt::make_options< default_hook, Options...>::type options;
108 typedef typename options::gc gc;
109 typedef typename options::tag tag;
110 typedef typename options::lock_type lock_type;
111 typedef node<gc, lock_type, tag> node_type;
112 typedef HookType hook_type;
119 - opt::gc - garbage collector
120 - opt::lock_type - lock type used for node locking. Default is sync::spin
121 - opt::tag - a \ref cds_intrusive_hook_tag "tag"
123 template < typename... Options >
124 struct base_hook: public hook< opt::base_hook_tag, Options... >
129 \p MemberOffset defines offset in bytes of \ref node member into your structure.
130 Use \p offsetof macro to define \p MemberOffset
133 - opt::gc - garbage collector
134 - opt::lock_type - lock type used for node locking. Default is sync::spin
135 - opt::tag - a \ref cds_intrusive_hook_tag "tag"
137 template < size_t MemberOffset, typename... Options >
138 struct member_hook: public hook< opt::member_hook_tag, Options... >
141 static const size_t c_nMemberOffset = MemberOffset;
147 \p NodeTraits defines type traits for node.
148 See \ref node_traits for \p NodeTraits interface description
151 - opt::gc - garbage collector used.
152 - opt::lock_type - lock type used for node locking. Default is sync::spin
153 - opt::tag - a \ref cds_intrusive_hook_tag "tag"
155 template <typename NodeTraits, typename... Options >
156 struct traits_hook: public hook< opt::traits_hook_tag, Options... >
159 typedef NodeTraits node_traits;
164 template <typename Node>
168 typedef Node node_type;
171 /// Checks if the link field of node \p pNode is \p nullptr
173 An asserting is generated if \p pNode link field is not \p nullptr
175 static void is_empty( node_type const * pNode )
177 assert( pNode->m_pNext.load( atomics::memory_order_relaxed ) == nullptr );
183 template <class GC, typename Node, opt::link_check_type LinkType >
184 struct link_checker_selector;
186 template <typename GC, typename Node>
187 struct link_checker_selector< GC, Node, opt::never_check_link >
189 typedef intrusive::opt::v::empty_link_checker<Node> type;
192 template <typename GC, typename Node>
193 struct link_checker_selector< GC, Node, opt::debug_check_link >
196 typedef link_checker<Node> type;
198 typedef intrusive::opt::v::empty_link_checker<Node> type;
202 template <typename GC, typename Node>
203 struct link_checker_selector< GC, Node, opt::always_check_link >
205 typedef link_checker<Node> type;
209 /// Metafunction for selecting appropriate link checking policy
210 template < typename Node, opt::link_check_type LinkType >
211 struct get_link_checker
214 typedef typename link_checker_selector< typename Node::gc, Node, LinkType>::type type;
218 /// \p LazyList internal statistics
219 template <typename EventCounter = cds::atomicity::event_counter>
221 typedef EventCounter event_counter; ///< Event counter type
223 event_counter m_nInsertSuccess; ///< Number of success \p insert() operations
224 event_counter m_nInsertFailed; ///< Number of failed \p insert() operations
225 event_counter m_nInsertRetry; ///< Number of attempts to insert new item
226 event_counter m_nUpdateNew; ///< Number of new item inserted for \p update()
227 event_counter m_nUpdateExisting; ///< Number of existing item updates
228 event_counter m_nUpdateFailed; ///< Number of failed \p update() call
229 event_counter m_nUpdateRetry; ///< Number of attempts to \p update() the item
230 event_counter m_nUpdateMarked; ///< Number of attempts to \p update() logically deleted (marked) items
231 event_counter m_nEraseSuccess; ///< Number of successful \p erase(), \p unlink(), \p extract() operations
232 event_counter m_nEraseFailed; ///< Number of failed \p erase(), \p unlink(), \p extract() operations
233 event_counter m_nEraseRetry; ///< Number of attempts to \p erase() an item
234 event_counter m_nFindSuccess; ///< Number of successful \p find() and \p get() operations
235 event_counter m_nFindFailed; ///< Number of failed \p find() and \p get() operations
237 event_counter m_nValidationSuccess; ///< Number of successful validating of search result
238 event_counter m_nValidationFailed; ///< Number of failed validating of search result
241 void onInsertSuccess() { ++m_nInsertSuccess; }
242 void onInsertFailed() { ++m_nInsertFailed; }
243 void onInsertRetry() { ++m_nInsertRetry; }
244 void onUpdateNew() { ++m_nUpdateNew; }
245 void onUpdateExisting() { ++m_nUpdateExisting; }
246 void onUpdateFailed() { ++m_nUpdateFailed; }
247 void onUpdateRetry() { ++m_nUpdateRetry; }
248 void onUpdateMarked() { ++m_nUpdateMarked; }
249 void onEraseSuccess() { ++m_nEraseSuccess; }
250 void onEraseFailed() { ++m_nEraseFailed; }
251 void onEraseRetry() { ++m_nEraseRetry; }
252 void onFindSuccess() { ++m_nFindSuccess; }
253 void onFindFailed() { ++m_nFindFailed; }
255 void onValidationSuccess() { ++m_nValidationSuccess; }
256 void onValidationFailed() { ++m_nValidationFailed; }
260 /// \p LazyList empty internal statistics
263 void onInsertSuccess() const {}
264 void onInsertFailed() const {}
265 void onInsertRetry() const {}
266 void onUpdateNew() const {}
267 void onUpdateExisting() const {}
268 void onUpdateFailed() const {}
269 void onUpdateRetry() const {}
270 void onUpdateMarked() const {}
271 void onEraseSuccess() const {}
272 void onEraseFailed() const {}
273 void onEraseRetry() const {}
274 void onFindSuccess() const {}
275 void onFindFailed() const {}
277 void onValidationSuccess() const {}
278 void onValidationFailed() const {}
283 template <typename Stat = lazy_list::stat<>>
284 struct wrapped_stat {
285 typedef Stat stat_type;
287 wrapped_stat( stat_type& st )
291 void onInsertSuccess() { m_stat.onInsertSuccess(); }
292 void onInsertFailed() { m_stat.onInsertFailed(); }
293 void onInsertRetry() { m_stat.onInsertRetry(); }
294 void onUpdateNew() { m_stat.onUpdateNew(); }
295 void onUpdateExisting() { m_stat.onUpdateExisting(); }
296 void onUpdateFailed() { m_stat.onUpdateFailed(); }
297 void onUpdateRetry() { m_stat.onUpdateRetry(); }
298 void onUpdateMarked() { m_stat.onUpdateMarked(); }
299 void onEraseSuccess() { m_stat.onEraseSuccess(); }
300 void onEraseFailed() { m_stat.onEraseFailed(); }
301 void onEraseRetry() { m_stat.onEraseRetry(); }
302 void onFindSuccess() { m_stat.onFindSuccess(); }
303 void onFindFailed() { m_stat.onFindFailed(); }
305 void onValidationSuccess() { m_stat.onValidationSuccess(); }
306 void onValidationFailed() { m_stat.onValidationFailed(); }
318 Possible values are: \p lazy_list::base_hook, \p lazy_list::member_hook, \p lazy_list::traits_hook.
320 typedef base_hook<> hook;
322 /// Key comparing functor
324 No default functor is provided. If the functor is not specified, the \p less is used.
326 typedef opt::none compare;
328 /// Specifies binary predicate used for comparing keys
330 Default is \p std::less<T>.
332 typedef opt::none less;
334 /// Specifies binary functor used for comparing keys for equality (for unordered list only)
336 If \p equal_to option is not specified, \p compare is used, if \p compare is not specified, \p less is used,
337 if \p less is not specified, then \p std::equal_to<T> is used.
339 typedef opt::none equal_to;
341 /// Specifies list ordering policy
343 If \p sort is \p true, than list maintains items in sorted order, otherwise the list is unordered.
345 Note that if \p sort is \p false, than lookup operations scan entire list.
347 static const bool sort = true;
349 /// Back-off strategy
350 typedef cds::backoff::Default back_off;
352 /// Disposer for removing items
353 typedef opt::v::empty_disposer disposer;
355 /// Item counting feature; by default, disabled. Use \p cds::atomicity::item_counter or \p atomicity::cache_friendly_item_counter to enable item counting
356 typedef atomicity::empty_item_counter item_counter;
358 /// Internal statistics
360 By default, internal statistics is disabled (\p lazy_list::empty_stat).
361 Use \p lazy_list::stat to enable it.
363 typedef empty_stat stat;
365 /// Link fields checking feature
367 Default is \p opt::debug_check_link
369 static const opt::link_check_type link_checker = opt::debug_check_link;
371 /// C++ memory ordering model
373 Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
374 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
376 typedef opt::v::relaxed_ordering memory_model;
378 /// RCU deadlock checking policy (only for \ref cds_intrusive_LazyList_rcu "RCU-based LazyList")
380 List of available options see \p opt::rcu_check_deadlock
382 typedef opt::v::rcu_throw_deadlock rcu_check_deadlock;
385 /// Metafunction converting option list to \p lazy_list::traits
387 Supported \p Options are:
388 - \p opt::hook - hook used. Possible values are: \p lazy_list::base_hook, \p lazy_list::member_hook, \p lazy_list::traits_hook.
389 If the option is not specified, \p %lazy_list::base_hook and \p gc::HP is used.
390 - \p opt::compare - key comparison functor. No default functor is provided.
391 If the option is not specified, the \p opt::less is used.
392 - \p opt::less - specifies binary predicate used for key comparison. Default is \p std::less<T>.
393 - \p opt::equal_to - specifies binary functor for comparing keys for equality. This option is applicable only for unordered list.
394 If \p equal_to is not specified, \p compare is used, \p compare is not specified, \p less is used.
395 - \p opt::sort - specifies ordering policy. Default value is \p true, i.e. the list is ordered.
396 Note: unordering feature is not fully supported yet.
397 - \p opt::back_off - back-off strategy used. If the option is not specified, the \p cds::backoff::Default is used.
398 - \p opt::disposer - the functor used for dispose removed items. Default is \p opt::v::empty_disposer. Due the nature
399 of GC schema the disposer may be called asynchronously.
400 - \p opt::link_checker - the type of node's link fields checking. Default is \p opt::debug_check_link
401 - \p opt::item_counter - the type of item counting feature. Default is disabled (\p atomicity::empty_item_counter).
402 To enable item counting use \p atomicity::item_counter or \p atomicity::cache_friendly_item_counter
403 - \p opt::stat - internal statistics. By default, it is disabled (\p lazy_list::empty_stat).
404 To enable it use \p lazy_list::stat
405 - \p opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
406 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
407 - \p opt::rcu_check_deadlock - a deadlock checking policy for \ref cds_intrusive_MichaelList_rcu "RCU-based MichaelList"
408 Default is \p opt::v::rcu_throw_deadlock
410 template <typename... Options>
412 # ifdef CDS_DOXYGEN_INVOKED
413 typedef implementation_defined type ; ///< Metafunction result
415 typedef typename cds::opt::make_options<
416 typename cds::opt::find_type_traits< traits, Options... >::type
423 template <typename Stat>
424 struct select_stat_wrapper
427 typedef lazy_list::wrapped_stat<Stat> wrapped_stat;
434 struct select_stat_wrapper< empty_stat >
436 typedef empty_stat stat;
437 typedef empty_stat wrapped_stat;
443 template <typename Stat>
444 struct select_stat_wrapper< lazy_list::wrapped_stat<Stat>>: public select_stat_wrapper< Stat >
448 } // namespace lazy_list
451 // Forward declaration
452 template < class GC, typename T, class Traits = lazy_list::traits >
457 template <typename List>
458 struct is_lazy_list {
464 template <typename GC, typename T, typename Traits>
465 struct is_lazy_list< LazyList< GC, T, Traits >> {
472 }} // namespace cds::intrusive
474 #endif // #ifndef CDSLIB_INTRUSIVE_DETAILS_LAZY_LIST_BASE_H