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_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_nNullPrevABA; ///< Number of ABA-problem for \p nullptr prev node
85 event_counter m_nNewNodeCreated; ///< Number of new node created when we try to insert new data
86 event_counter m_nUpdateNew; ///< Number of new item inserted for \p update()
87 event_counter m_nUpdateExisting; ///< Number of existing item updates
88 event_counter m_nUpdateFailed; ///< Number of failed \p update() call
89 event_counter m_nUpdateRetry; ///< Number of attempts to update the item
90 event_counter m_nEraseSuccess; ///< Number of successful \p erase(), \p unlink(), \p extract() operations
91 event_counter m_nEraseFailed; ///< Number of failed \p erase(), \p unlink(), \p extract() operations
92 event_counter m_nEraseRetry; ///< Number of attempts to \p erase() an item
93 event_counter m_nFindSuccess; ///< Number of successful \p find() and \p get() operations
94 event_counter m_nFindFailed; ///< Number of failed \p find() and \p get() operations
96 event_counter m_nNodeCreated; ///< Number of created internal nodes
97 event_counter m_nNodeRemoved; ///< Number of removed internal nodes
100 void onInsertSuccess() { ++m_nInsertSuccess; }
101 void onInsertFailed() { ++m_nInsertFailed; }
102 void onInsertRetry() { ++m_nInsertRetry; }
103 void onReuseNode() { ++m_nReuseNode; }
104 void onNodeMarkFailed() { ++m_nNodeMarkFailed; }
105 void onNodeSeqBreak() { ++m_nNodeSeqBreak; }
106 void onNullPrevABA() { ++m_nNullPrevABA; }
107 void onNewNodeCreated() { ++m_nNewNodeCreated; }
108 void onUpdateNew() { ++m_nUpdateNew; }
109 void onUpdateExisting() { ++m_nUpdateExisting; }
110 void onUpdateFailed() { ++m_nUpdateFailed; }
111 void onUpdateRetry() { ++m_nUpdateRetry; }
112 void onEraseSuccess() { ++m_nEraseSuccess; }
113 void onEraseFailed() { ++m_nEraseFailed; }
114 void onEraseRetry() { ++m_nEraseRetry; }
115 void onFindSuccess() { ++m_nFindSuccess; }
116 void onFindFailed() { ++m_nFindFailed; }
118 void onNodeCreated() { ++m_nNodeCreated; }
119 void onNodeRemoved() { ++m_nNodeRemoved; }
123 /// \p IterableList empty internal statistics
126 void onInsertSuccess() const {}
127 void onInsertFailed() const {}
128 void onInsertRetry() const {}
129 void onReuseNode() const {}
130 void onNodeMarkFailed() const {}
131 void onNodeSeqBreak() const {}
132 void onNullPrevABA() const {}
133 void onNewNodeCreated() const {}
134 void onUpdateNew() const {}
135 void onUpdateExisting() const {}
136 void onUpdateFailed() const {}
137 void onUpdateRetry() const {}
138 void onEraseSuccess() const {}
139 void onEraseFailed() const {}
140 void onEraseRetry() const {}
141 void onFindSuccess() const {}
142 void onFindFailed() const {}
144 void onNodeCreated() const {}
145 void onNodeRemoved() const {}
150 template <typename Stat = iterable_list::stat<>>
151 struct wrapped_stat {
152 typedef Stat stat_type;
154 wrapped_stat( stat_type& st )
158 void onInsertSuccess() { m_stat.onInsertSuccess(); }
159 void onInsertFailed() { m_stat.onInsertFailed(); }
160 void onInsertRetry() { m_stat.onInsertRetry(); }
161 void onReuseNode() { m_stat.onReuseNode(); }
162 void onNodeMarkFailed() { m_stat.onNodeMarkFailed();}
163 void onNodeSeqBreak() { m_stat.onNodeSeqBreak(); }
164 void onNullPrevABA() { m_stat.onNullPrevABA(); }
165 void onNewNodeCreated() { m_stat.onNewNodeCreated();}
166 void onUpdateNew() { m_stat.onUpdateNew(); }
167 void onUpdateExisting() { m_stat.onUpdateExisting();}
168 void onUpdateFailed() { m_stat.onUpdateFailed(); }
169 void onUpdateRetry() { m_stat.onUpdateRetry(); }
170 void onEraseSuccess() { m_stat.onEraseSuccess(); }
171 void onEraseFailed() { m_stat.onEraseFailed(); }
172 void onEraseRetry() { m_stat.onEraseRetry(); }
173 void onFindSuccess() { m_stat.onFindSuccess(); }
174 void onFindFailed() { m_stat.onFindFailed(); }
176 void onNodeCreated() { m_stat.onNodeCreated(); }
177 void onNodeRemoved() { m_stat.onNodeRemoved(); }
184 /// \p IterableList traits
187 /// Key comparison functor
189 No default functor is provided. If the option is not specified, the \p less is used.
191 typedef opt::none compare;
193 /// Specifies binary predicate used for key compare.
195 Default is \p std::less<T>
197 typedef opt::none less;
200 typedef CDS_DEFAULT_ALLOCATOR node_allocator;
202 /// Back-off strategy
203 typedef cds::backoff::Default back_off;
205 /// Disposer for removing items
206 typedef opt::v::empty_disposer disposer;
208 /// Internal statistics
210 By default, internal statistics is disabled (\p iterable_list::empty_stat).
211 Use \p iterable_list::stat to enable it.
213 typedef empty_stat stat;
215 /// Item counting feature; by default, disabled. Use \p cds::atomicity::item_counter to enable item counting
216 typedef atomicity::empty_item_counter item_counter;
218 /// C++ memory ordering model
220 Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
221 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
223 typedef opt::v::relaxed_ordering memory_model;
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).
243 template <typename... Options>
245 # ifdef CDS_DOXYGEN_INVOKED
246 typedef implementation_defined type ; ///< Metafunction result
248 typedef typename cds::opt::make_options<
249 typename cds::opt::find_type_traits< traits, Options... >::type
257 template <typename Stat>
258 struct select_stat_wrapper
261 typedef iterable_list::wrapped_stat<Stat> wrapped_stat;
268 struct select_stat_wrapper< empty_stat >
270 typedef empty_stat stat;
271 typedef empty_stat wrapped_stat;
277 template <typename Stat>
278 struct select_stat_wrapper< iterable_list::wrapped_stat<Stat>>: public select_stat_wrapper<Stat>
282 } // namespace iterable_list
285 // Forward declaration
286 template < class GC, typename T, class Traits = iterable_list::traits >
290 }} // namespace cds::intrusive
292 #endif // #ifndef CDSLIB_INTRUSIVE_DETAILS_ITERABLE_LIST_BASE_H