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_nReuseNode; ///< Number of reusing empty node when inserting/updating
80 event_counter m_nNodeMarkFailed; ///< Number of unsuccessful marking attempts when we try to insert new data
81 event_counter m_nNodeSeqBreak; ///< Number of breaking sequence events of \p prev -> \p next node when we try to insert new data
82 event_counter m_nNewNodeCreated; ///< Number of new node created when we try to insert new data
83 event_counter m_nUpdateNew; ///< Number of new item inserted for \p update()
84 event_counter m_nUpdateExisting; ///< Number of existing item updates
85 event_counter m_nUpdateFailed; ///< Number of failed \p update() call
86 event_counter m_nUpdateRetry; ///< Number of attempts to update the item
87 event_counter m_nEraseSuccess; ///< Number of successful \p erase(), \p unlink(), \p extract() operations
88 event_counter m_nEraseFailed; ///< Number of failed \p erase(), \p unlink(), \p extract() operations
89 event_counter m_nEraseRetry; ///< Number of attempts to \p erase() an item
90 event_counter m_nFindSuccess; ///< Number of successful \p find() and \p get() operations
91 event_counter m_nFindFailed; ///< Number of failed \p find() and \p get() operations
93 event_counter m_nNodeCreated; ///< Number of created internal nodes
94 event_counter m_nNodeRemoved; ///< Number of removed internal nodes
97 void onInsertSuccess() { ++m_nInsertSuccess; }
98 void onInsertFailed() { ++m_nInsertFailed; }
99 void onInsertRetry() { ++m_nInsertRetry; }
100 void onReuseNode() { ++m_nReuseNode; }
101 void onNodeMarkFailed() { ++m_nNodeMarkFailed; }
102 void onNodeSeqBreak() { ++m_nNodeSeqBreak; }
103 void onNewNodeCreated() { ++m_nNewNodeCreated; }
104 void onUpdateNew() { ++m_nUpdateNew; }
105 void onUpdateExisting() { ++m_nUpdateExisting; }
106 void onUpdateFailed() { ++m_nUpdateFailed; }
107 void onUpdateRetry() { ++m_nUpdateRetry; }
108 void onEraseSuccess() { ++m_nEraseSuccess; }
109 void onEraseFailed() { ++m_nEraseFailed; }
110 void onEraseRetry() { ++m_nEraseRetry; }
111 void onFindSuccess() { ++m_nFindSuccess; }
112 void onFindFailed() { ++m_nFindFailed; }
114 void onNodeCreated() { ++m_nNodeCreated; }
115 void onNodeRemoved() { ++m_nNodeRemoved; }
119 /// \p IterableList empty internal statistics
122 void onInsertSuccess() const {}
123 void onInsertFailed() const {}
124 void onInsertRetry() const {}
125 void onReuseNode() const {}
126 void onNodeMarkFailed() const {}
127 void onNodeSeqBreak() const {}
128 void onNewNodeCreated() const {}
129 void onUpdateNew() const {}
130 void onUpdateExisting() const {}
131 void onUpdateFailed() const {}
132 void onUpdateRetry() const {}
133 void onEraseSuccess() const {}
134 void onEraseFailed() const {}
135 void onEraseRetry() const {}
136 void onFindSuccess() const {}
137 void onFindFailed() const {}
139 void onNodeCreated() const {}
140 void onNodeRemoved() const {}
145 template <typename Stat = iterable_list::stat<>>
146 struct wrapped_stat {
147 typedef Stat stat_type;
149 wrapped_stat( stat_type& st )
153 void onInsertSuccess() { m_stat.onInsertSuccess(); }
154 void onInsertFailed() { m_stat.onInsertFailed(); }
155 void onInsertRetry() { m_stat.onInsertRetry(); }
156 void onReuseNode() { m_stat.onReuseNode(); }
157 void onNodeMarkFailed() { m_stat.onNodeMarkFailed();}
158 void onNodeSeqBreak() { m_stat.onNodeSeqBreak(); }
159 void onNewNodeCreated() { m_stat.onNewNodeCreated();}
160 void onUpdateNew() { m_stat.onUpdateNew(); }
161 void onUpdateExisting() { m_stat.onUpdateExisting();}
162 void onUpdateFailed() { m_stat.onUpdateFailed(); }
163 void onUpdateRetry() { m_stat.onUpdateRetry(); }
164 void onEraseSuccess() { m_stat.onEraseSuccess(); }
165 void onEraseFailed() { m_stat.onEraseFailed(); }
166 void onEraseRetry() { m_stat.onEraseRetry(); }
167 void onFindSuccess() { m_stat.onFindSuccess(); }
168 void onFindFailed() { m_stat.onFindFailed(); }
170 void onNodeCreated() { m_stat.onNodeCreated(); }
171 void onNodeRemoved() { m_stat.onNodeRemoved(); }
178 /// \p IterableList traits
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;
194 typedef CDS_DEFAULT_ALLOCATOR node_allocator;
196 /// Back-off strategy
197 typedef cds::backoff::Default back_off;
199 /// Disposer for removing items
200 typedef opt::v::empty_disposer disposer;
202 /// Internal statistics
204 By default, internal statistics is disabled (\p iterable_list::empty_stat).
205 Use \p iterable_list::stat to enable it.
207 typedef empty_stat stat;
209 /// Item counting feature; by default, disabled. Use \p cds::atomicity::item_counter to enable item counting
210 typedef atomicity::empty_item_counter item_counter;
212 /// C++ memory ordering model
214 Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
215 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
217 typedef opt::v::relaxed_ordering memory_model;
219 /// RCU deadlock checking policy (only for \ref cds_intrusive_IterableList_rcu "RCU-based IterableList")
221 List of available policy see \p opt::rcu_check_deadlock
223 typedef opt::v::rcu_throw_deadlock rcu_check_deadlock;
226 /// Metafunction converting option list to \p iterable_list::traits
228 Supported \p Options are:
229 - \p opt::compare - key comparison functor. No default functor is provided.
230 If the option is not specified, the \p opt::less is used.
231 - \p opt::less - specifies binary predicate used for key comparison. Default is \p std::less<T>.
232 - \p opt::node_allocator - node allocator, default is \p std::allocator.
233 - \p opt::back_off - back-off strategy used. If the option is not specified, the \p cds::backoff::Default is used.
234 - \p opt::disposer - the functor used for disposing removed items. Default is \p opt::v::empty_disposer. Due the nature
235 of GC schema the disposer may be called asynchronously.
236 - \p opt::item_counter - the type of item counting feature. Default is disabled (\p atomicity::empty_item_counter).
237 To enable item counting use \p atomicity::item_counter.
238 - \p opt::stat - internal statistics. By default, it is disabled (\p iterable_list::empty_stat).
239 To enable it use \p iterable_list::stat
240 - \p opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
241 or \p opt::v::sequential_consistent (sequentially consistent memory model).
242 - \p opt::rcu_check_deadlock - a deadlock checking policy for \ref cds_intrusive_IterableList_rcu "RCU-based IterableList"
243 Default is \p opt::v::rcu_throw_deadlock
245 template <typename... Options>
247 # ifdef CDS_DOXYGEN_INVOKED
248 typedef implementation_defined type ; ///< Metafunction result
250 typedef typename cds::opt::make_options<
251 typename cds::opt::find_type_traits< traits, Options... >::type
259 template <typename Stat>
260 struct select_stat_wrapper
263 typedef iterable_list::wrapped_stat<Stat> wrapped_stat;
270 struct select_stat_wrapper< empty_stat >
272 typedef empty_stat stat;
273 typedef empty_stat wrapped_stat;
279 template <typename Stat>
280 struct select_stat_wrapper< iterable_list::wrapped_stat<Stat>>: public select_stat_wrapper<Stat>
284 } // namespace iterable_list
287 // Forward declaration
288 template < class GC, typename T, class Traits = iterable_list::traits >
293 template <typename GC, typename T, typename Traits>
294 struct is_iterable_list< IterableList< GC, T, Traits >> {
301 }} // namespace cds::intrusive
303 #endif // #ifndef CDSLIB_INTRUSIVE_DETAILS_ITERABLE_LIST_BASE_H