2 This file is a part of libcds - Concurrent Data Structures library
4 (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016
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_ITERABLE_LIST_BASE_H
32 #define CDSLIB_INTRUSIVE_DETAILS_ITERABLE_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 /// \p IterableList ordered list related definitions
44 /** @ingroup cds_intrusive_helper
46 namespace iterable_list {
52 typedef T value_type; ///< Value type
53 typedef cds::details::marked_ptr<T, 1> marked_data_ptr; ///< marked pointer to the value
55 atomics::atomic< node* > next; ///< pointer to next node in the list
56 atomics::atomic< marked_data_ptr > data; ///< pointer to user data, \p nullptr if the node is free
64 node( value_type * pVal )
71 /// \p IterableList internal statistics
72 template <typename EventCounter = cds::atomicity::event_counter>
74 typedef EventCounter event_counter; ///< Event counter type
76 event_counter m_nInsertSuccess; ///< Number of success \p insert() operations
77 event_counter m_nInsertFailed; ///< Number of failed \p insert() operations
78 event_counter m_nInsertRetry; ///< Number of attempts to insert new item
79 event_counter m_nInsertReuse; ///< Number of reusing empty node when inserting
80 event_counter m_nInsertReuseFailed; ///< Number of failed attempsof reusing free node when inserting
81 event_counter m_nUpdateNew; ///< Number of new item inserted for \p update()
82 event_counter m_nUpdateExisting; ///< Number of existing item updates
83 event_counter m_nUpdateFailed; ///< Number of failed \p update() call
84 event_counter m_nUpdateRetry; ///< Number of attempts to update the item
85 event_counter m_nEraseSuccess; ///< Number of successful \p erase(), \p unlink(), \p extract() operations
86 event_counter m_nEraseFailed; ///< Number of failed \p erase(), \p unlink(), \p extract() operations
87 event_counter m_nEraseRetry; ///< Number of attempts to \p erase() an item
88 event_counter m_nFindSuccess; ///< Number of successful \p find() and \p get() operations
89 event_counter m_nFindFailed; ///< Number of failed \p find() and \p get() operations
91 event_counter m_nNodeCreated; ///< Number of created internal nodes
92 event_counter m_nNodeRemoved; ///< Number of removed internal nodes
95 void onInsertSuccess() { ++m_nInsertSuccess; }
96 void onInsertFailed() { ++m_nInsertFailed; }
97 void onInsertRetry() { ++m_nInsertRetry; }
98 void onInsertReuse() { ++m_nInsertReuse; }
99 void onInsertReuseFailed() { ++m_nInsertReuseFailed; }
100 void onUpdateNew() { ++m_nUpdateNew; }
101 void onUpdateExisting() { ++m_nUpdateExisting; }
102 void onUpdateFailed() { ++m_nUpdateFailed; }
103 void onUpdateRetry() { ++m_nUpdateRetry; }
104 void onEraseSuccess() { ++m_nEraseSuccess; }
105 void onEraseFailed() { ++m_nEraseFailed; }
106 void onEraseRetry() { ++m_nEraseRetry; }
107 void onFindSuccess() { ++m_nFindSuccess; }
108 void onFindFailed() { ++m_nFindFailed; }
110 void onNodeCreated() { ++m_nNodeCreated; }
111 void onNodeRemoved() { ++m_nNodeRemoved; }
115 /// \p IterableList empty internal statistics
118 void onInsertSuccess() const {}
119 void onInsertFailed() const {}
120 void onInsertRetry() const {}
121 void onInsertReuse() const {}
122 void onInsertReuseFailed() const {}
123 void onUpdateNew() const {}
124 void onUpdateExisting() const {}
125 void onUpdateFailed() const {}
126 void onUpdateRetry() const {}
127 void onEraseSuccess() const {}
128 void onEraseFailed() const {}
129 void onEraseRetry() const {}
130 void onFindSuccess() const {}
131 void onFindFailed() const {}
133 void onNodeCreated() const {}
134 void onNodeRemoved() const {}
139 template <typename Stat = iterable_list::stat<>>
140 struct wrapped_stat {
141 typedef Stat stat_type;
143 wrapped_stat( stat_type& st )
147 void onInsertSuccess() { m_stat.onInsertSuccess(); }
148 void onInsertFailed() { m_stat.onInsertFailed(); }
149 void onInsertRetry() { m_stat.onInsertRetry(); }
150 void onInsertReuse() { m_stat.onInsertReuse(); }
151 void onInsertReuseFailed() { m_stat.onInsertReuseFailed(); }
152 void onUpdateNew() { m_stat.onUpdateNew(); }
153 void onUpdateExisting() { m_stat.onUpdateExisting();}
154 void onUpdateFailed() { m_stat.onUpdateFailed(); }
155 void onUpdateRetry() { m_stat.onUpdateRetry(); }
156 void onEraseSuccess() { m_stat.onEraseSuccess(); }
157 void onEraseFailed() { m_stat.onEraseFailed(); }
158 void onEraseRetry() { m_stat.onEraseRetry(); }
159 void onFindSuccess() { m_stat.onFindSuccess(); }
160 void onFindFailed() { m_stat.onFindFailed(); }
162 void onNodeCreated() { m_stat.onNodeCreated(); }
163 void onNodeRemoved() { m_stat.onNodeRemoved(); }
170 /// \p IterableList traits
173 /// Key comparison functor
175 No default functor is provided. If the option is not specified, the \p less is used.
177 typedef opt::none compare;
179 /// Specifies binary predicate used for key compare.
181 Default is \p std::less<T>
183 typedef opt::none less;
186 typedef CDS_DEFAULT_ALLOCATOR node_allocator;
188 /// Back-off strategy
189 typedef cds::backoff::Default back_off;
191 /// Disposer for removing items
192 typedef opt::v::empty_disposer disposer;
194 /// Internal statistics
196 By default, internal statistics is disabled (\p iterable_list::empty_stat).
197 Use \p iterable_list::stat to enable it.
199 typedef empty_stat stat;
201 /// Item counting feature; by default, disabled. Use \p cds::atomicity::item_counter to enable item counting
202 typedef atomicity::empty_item_counter item_counter;
204 /// C++ memory ordering model
206 Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
207 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
209 typedef opt::v::relaxed_ordering memory_model;
211 /// RCU deadlock checking policy (only for \ref cds_intrusive_IterableList_rcu "RCU-based IterableList")
213 List of available policy see \p opt::rcu_check_deadlock
215 typedef opt::v::rcu_throw_deadlock rcu_check_deadlock;
218 /// Metafunction converting option list to \p iterable_list::traits
220 Supported \p Options are:
221 - \p opt::compare - key comparison functor. No default functor is provided.
222 If the option is not specified, the \p opt::less is used.
223 - \p opt::less - specifies binary predicate used for key comparison. Default is \p std::less<T>.
224 - \p opt::node_allocator - node allocator, default is \p std::allocator.
225 - \p opt::back_off - back-off strategy used. If the option is not specified, the \p cds::backoff::Default is used.
226 - \p opt::disposer - the functor used for disposing removed items. Default is \p opt::v::empty_disposer. Due the nature
227 of GC schema the disposer may be called asynchronously.
228 - \p opt::item_counter - the type of item counting feature. Default is disabled (\p atomicity::empty_item_counter).
229 To enable item counting use \p atomicity::item_counter.
230 - \p opt::stat - internal statistics. By default, it is disabled (\p iterable_list::empty_stat).
231 To enable it use \p iterable_list::stat
232 - \p opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
233 or \p opt::v::sequential_consistent (sequentially consistent memory model).
234 - \p opt::rcu_check_deadlock - a deadlock checking policy for \ref cds_intrusive_IterableList_rcu "RCU-based IterableList"
235 Default is \p opt::v::rcu_throw_deadlock
237 template <typename... Options>
239 # ifdef CDS_DOXYGEN_INVOKED
240 typedef implementation_defined type ; ///< Metafunction result
242 typedef typename cds::opt::make_options<
243 typename cds::opt::find_type_traits< traits, Options... >::type
251 template <typename Stat>
252 struct select_stat_wrapper
255 typedef iterable_list::wrapped_stat<Stat> wrapped_stat;
262 struct select_stat_wrapper< empty_stat >
264 typedef empty_stat stat;
265 typedef empty_stat wrapped_stat;
271 template <typename Stat>
272 struct select_stat_wrapper< iterable_list::wrapped_stat<Stat>>: public select_stat_wrapper<Stat>
276 } // namespace iterable_list
279 // Forward declaration
280 template < class GC, typename T, class Traits = iterable_list::traits >
285 template <typename GC, typename T, typename Traits>
286 struct is_iterable_list< IterableList< GC, T, Traits >> {
293 }} // namespace cds::intrusive
295 #endif // #ifndef CDSLIB_INTRUSIVE_DETAILS_ITERABLE_LIST_BASE_H