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
61 next.store( nullptr, atomics::memory_order_release );
62 data.store( marked_data_ptr(), atomics::memory_order_release );
65 node( value_type * pVal )
67 next.store( nullptr, atomics::memory_order_release );
68 data.store( marked_data_ptr( pVal ), atomics::memory_order_release );
73 /// \p IterableList internal statistics
74 template <typename EventCounter = cds::atomicity::event_counter>
76 typedef EventCounter event_counter; ///< Event counter type
78 event_counter m_nInsertSuccess; ///< Number of success \p insert() operations
79 event_counter m_nInsertFailed; ///< Number of failed \p insert() operations
80 event_counter m_nInsertRetry; ///< Number of attempts to insert new item
81 event_counter m_nReuseNode; ///< Number of reusing empty node when inserting/updating
82 event_counter m_nNodeMarkFailed; ///< Number of unsuccessful marking attempts when we try to insert new data
83 event_counter m_nNodeSeqBreak; ///< Number of breaking sequence events of \p prev -> \p next node when we try to insert new data
84 event_counter m_nNewNodeCreated; ///< Number of new node created when we try to insert new data
85 event_counter m_nUpdateNew; ///< Number of new item inserted for \p update()
86 event_counter m_nUpdateExisting; ///< Number of existing item updates
87 event_counter m_nUpdateFailed; ///< Number of failed \p update() call
88 event_counter m_nUpdateRetry; ///< Number of attempts to update the item
89 event_counter m_nEraseSuccess; ///< Number of successful \p erase(), \p unlink(), \p extract() operations
90 event_counter m_nEraseFailed; ///< Number of failed \p erase(), \p unlink(), \p extract() operations
91 event_counter m_nEraseRetry; ///< Number of attempts to \p erase() an item
92 event_counter m_nFindSuccess; ///< Number of successful \p find() and \p get() operations
93 event_counter m_nFindFailed; ///< Number of failed \p find() and \p get() operations
95 event_counter m_nNodeCreated; ///< Number of created internal nodes
96 event_counter m_nNodeRemoved; ///< Number of removed internal nodes
99 void onInsertSuccess() { ++m_nInsertSuccess; }
100 void onInsertFailed() { ++m_nInsertFailed; }
101 void onInsertRetry() { ++m_nInsertRetry; }
102 void onReuseNode() { ++m_nReuseNode; }
103 void onNodeMarkFailed() { ++m_nNodeMarkFailed; }
104 void onNodeSeqBreak() { ++m_nNodeSeqBreak; }
105 void onNewNodeCreated() { ++m_nNewNodeCreated; }
106 void onUpdateNew() { ++m_nUpdateNew; }
107 void onUpdateExisting() { ++m_nUpdateExisting; }
108 void onUpdateFailed() { ++m_nUpdateFailed; }
109 void onUpdateRetry() { ++m_nUpdateRetry; }
110 void onEraseSuccess() { ++m_nEraseSuccess; }
111 void onEraseFailed() { ++m_nEraseFailed; }
112 void onEraseRetry() { ++m_nEraseRetry; }
113 void onFindSuccess() { ++m_nFindSuccess; }
114 void onFindFailed() { ++m_nFindFailed; }
116 void onNodeCreated() { ++m_nNodeCreated; }
117 void onNodeRemoved() { ++m_nNodeRemoved; }
121 /// \p IterableList empty internal statistics
124 void onInsertSuccess() const {}
125 void onInsertFailed() const {}
126 void onInsertRetry() const {}
127 void onReuseNode() const {}
128 void onNodeMarkFailed() const {}
129 void onNodeSeqBreak() const {}
130 void onNewNodeCreated() const {}
131 void onUpdateNew() const {}
132 void onUpdateExisting() const {}
133 void onUpdateFailed() const {}
134 void onUpdateRetry() const {}
135 void onEraseSuccess() const {}
136 void onEraseFailed() const {}
137 void onEraseRetry() const {}
138 void onFindSuccess() const {}
139 void onFindFailed() const {}
141 void onNodeCreated() const {}
142 void onNodeRemoved() const {}
147 template <typename Stat = iterable_list::stat<>>
148 struct wrapped_stat {
149 typedef Stat stat_type;
151 wrapped_stat( stat_type& st )
155 void onInsertSuccess() { m_stat.onInsertSuccess(); }
156 void onInsertFailed() { m_stat.onInsertFailed(); }
157 void onInsertRetry() { m_stat.onInsertRetry(); }
158 void onReuseNode() { m_stat.onReuseNode(); }
159 void onNodeMarkFailed() { m_stat.onNodeMarkFailed();}
160 void onNodeSeqBreak() { m_stat.onNodeSeqBreak(); }
161 void onNewNodeCreated() { m_stat.onNewNodeCreated();}
162 void onUpdateNew() { m_stat.onUpdateNew(); }
163 void onUpdateExisting() { m_stat.onUpdateExisting();}
164 void onUpdateFailed() { m_stat.onUpdateFailed(); }
165 void onUpdateRetry() { m_stat.onUpdateRetry(); }
166 void onEraseSuccess() { m_stat.onEraseSuccess(); }
167 void onEraseFailed() { m_stat.onEraseFailed(); }
168 void onEraseRetry() { m_stat.onEraseRetry(); }
169 void onFindSuccess() { m_stat.onFindSuccess(); }
170 void onFindFailed() { m_stat.onFindFailed(); }
172 void onNodeCreated() { m_stat.onNodeCreated(); }
173 void onNodeRemoved() { m_stat.onNodeRemoved(); }
180 /// \p IterableList traits
183 /// Key comparison functor
185 No default functor is provided. If the option is not specified, the \p less is used.
187 typedef opt::none compare;
189 /// Specifies binary predicate used for key compare.
191 Default is \p std::less<T>
193 typedef opt::none less;
196 typedef CDS_DEFAULT_ALLOCATOR node_allocator;
198 /// Back-off strategy
199 typedef cds::backoff::Default back_off;
201 /// Disposer for removing items
202 typedef opt::v::empty_disposer disposer;
204 /// Internal statistics
206 By default, internal statistics is disabled (\p iterable_list::empty_stat).
207 Use \p iterable_list::stat to enable it.
209 typedef empty_stat stat;
211 /// Item counting feature; by default, disabled. Use \p cds::atomicity::item_counter to enable item counting
212 typedef atomicity::empty_item_counter item_counter;
214 /// C++ memory ordering model
216 Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
217 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
219 typedef opt::v::relaxed_ordering memory_model;
221 /// RCU deadlock checking policy (only for \ref cds_intrusive_IterableList_rcu "RCU-based IterableList")
223 List of available policy see \p opt::rcu_check_deadlock
225 typedef opt::v::rcu_throw_deadlock rcu_check_deadlock;
228 /// Metafunction converting option list to \p iterable_list::traits
230 Supported \p Options are:
231 - \p opt::compare - key comparison functor. No default functor is provided.
232 If the option is not specified, the \p opt::less is used.
233 - \p opt::less - specifies binary predicate used for key comparison. Default is \p std::less<T>.
234 - \p opt::node_allocator - node allocator, default is \p std::allocator.
235 - \p opt::back_off - back-off strategy used. If the option is not specified, the \p cds::backoff::Default is used.
236 - \p opt::disposer - the functor used for disposing removed items. Default is \p opt::v::empty_disposer. Due the nature
237 of GC schema the disposer may be called asynchronously.
238 - \p opt::item_counter - the type of item counting feature. Default is disabled (\p atomicity::empty_item_counter).
239 To enable item counting use \p atomicity::item_counter.
240 - \p opt::stat - internal statistics. By default, it is disabled (\p iterable_list::empty_stat).
241 To enable it use \p iterable_list::stat
242 - \p opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
243 or \p opt::v::sequential_consistent (sequentially consistent memory model).
244 - \p opt::rcu_check_deadlock - a deadlock checking policy for \ref cds_intrusive_IterableList_rcu "RCU-based IterableList"
245 Default is \p opt::v::rcu_throw_deadlock
247 template <typename... Options>
249 # ifdef CDS_DOXYGEN_INVOKED
250 typedef implementation_defined type ; ///< Metafunction result
252 typedef typename cds::opt::make_options<
253 typename cds::opt::find_type_traits< traits, Options... >::type
261 template <typename Stat>
262 struct select_stat_wrapper
265 typedef iterable_list::wrapped_stat<Stat> wrapped_stat;
272 struct select_stat_wrapper< empty_stat >
274 typedef empty_stat stat;
275 typedef empty_stat wrapped_stat;
281 template <typename Stat>
282 struct select_stat_wrapper< iterable_list::wrapped_stat<Stat>>: public select_stat_wrapper<Stat>
286 } // namespace iterable_list
289 // Forward declaration
290 template < class GC, typename T, class Traits = iterable_list::traits >
294 }} // namespace cds::intrusive
296 #endif // #ifndef CDSLIB_INTRUSIVE_DETAILS_ITERABLE_LIST_BASE_H