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
54 atomics::atomic< node* > next; ///< pointer to next node in the list
55 atomics::atomic< value_type* > data; ///< pointer to user data, \p nullptr if the node is free
63 node( value_type * pVal )
70 /// \p IterableList internal statistics
71 template <typename EventCounter = cds::atomicity::event_counter>
73 typedef EventCounter event_counter; ///< Event counter type
75 event_counter m_nInsertSuccess; ///< Number of success \p insert() operations
76 event_counter m_nInsertFailed; ///< Number of failed \p insert() operations
77 event_counter m_nInsertRetry; ///< Number of attempts to insert new item
78 event_counter m_nUpdateNew; ///< Number of new item inserted for \p update()
79 event_counter m_nUpdateExisting; ///< Number of existing item updates
80 event_counter m_nUpdateFailed; ///< Number of failed \p update() call
81 event_counter m_nUpdateRetry; ///< Number of attempts to update the item
82 event_counter m_nEraseSuccess; ///< Number of successful \p erase(), \p unlink(), \p extract() operations
83 event_counter m_nEraseFailed; ///< Number of failed \p erase(), \p unlink(), \p extract() operations
84 event_counter m_nEraseRetry; ///< Number of attempts to \p erase() an item
85 event_counter m_nFindSuccess; ///< Number of successful \p find() and \p get() operations
86 event_counter m_nFindFailed; ///< Number of failed \p find() and \p get() operations
88 event_counter m_nNodeCreated; ///< Number of created internal nodes
89 event_counter m_nNodeRemoved; ///< Number of removed internal nodes
92 void onInsertSuccess() { ++m_nInsertSuccess; }
93 void onInsertFailed() { ++m_nInsertFailed; }
94 void onInsertRetry() { ++m_nInsertRetry; }
95 void onUpdateNew() { ++m_nUpdateNew; }
96 void onUpdateExisting() { ++m_nUpdateExisting; }
97 void onUpdateFailed() { ++m_nUpdateFailed; }
98 void onUpdateRetry() { ++m_nUpdateRetry; }
99 void onEraseSuccess() { ++m_nEraseSuccess; }
100 void onEraseFailed() { ++m_nEraseFailed; }
101 void onEraseRetry() { ++m_nEraseRetry; }
102 void onFindSuccess() { ++m_nFindSuccess; }
103 void onFindFailed() { ++m_nFindFailed; }
105 void onNodeCreated() { ++m_nNodeCreated; }
106 void onNodeRemoved() { ++m_nNodeRemoved; }
110 /// \p IterableList empty internal statistics
113 void onInsertSuccess() const {}
114 void onInsertFailed() const {}
115 void onInsertRetry() const {}
116 void onUpdateNew() const {}
117 void onUpdateExisting() const {}
118 void onUpdateFailed() const {}
119 void onUpdateRetry() const {}
120 void onEraseSuccess() const {}
121 void onEraseFailed() const {}
122 void onEraseRetry() const {}
123 void onFindSuccess() const {}
124 void onFindFailed() const {}
126 void onNodeCreated() const {}
127 void onNodeRemoved() const {}
132 template <typename Stat = iterable_list::stat<>>
133 struct wrapped_stat {
134 typedef Stat stat_type;
136 wrapped_stat( stat_type& st )
140 void onInsertSuccess() { m_stat.onInsertSuccess(); }
141 void onInsertFailed() { m_stat.onInsertFailed(); }
142 void onInsertRetry() { m_stat.onInsertRetry(); }
143 void onUpdateNew() { m_stat.onUpdateNew(); }
144 void onUpdateExisting() { m_stat.onUpdateExisting();}
145 void onUpdateFailed() { m_stat.onUpdateFailed(); }
146 void onUpdateRetry() { m_stat.onUpdateRetry(); }
147 void onEraseSuccess() { m_stat.onEraseSuccess(); }
148 void onEraseFailed() { m_stat.onEraseFailed(); }
149 void onEraseRetry() { m_stat.onEraseRetry(); }
150 void onFindSuccess() { m_stat.onFindSuccess(); }
151 void onFindFailed() { m_stat.onFindFailed(); }
153 void onNodeCreated() { m_stat.onNodeCreated(); }
154 void onNodeRemoved() { m_stat.onNodeRemoved(); }
161 /// \p IterableList traits
164 /// Key comparison functor
166 No default functor is provided. If the option is not specified, the \p less is used.
168 typedef opt::none compare;
170 /// Specifies binary predicate used for key compare.
172 Default is \p std::less<T>
174 typedef opt::none less;
177 typedef CDS_DEFAULT_ALLOCATOR node_allocator;
179 /// Back-off strategy
180 typedef cds::backoff::Default back_off;
182 /// Disposer for removing items
183 typedef opt::v::empty_disposer disposer;
185 /// Internal statistics
187 By default, internal statistics is disabled (\p iterable_list::empty_stat).
188 Use \p iterable_list::stat to enable it.
190 typedef empty_stat stat;
192 /// Item counting feature; by default, disabled. Use \p cds::atomicity::item_counter to enable item counting
193 typedef atomicity::empty_item_counter item_counter;
195 /// C++ memory ordering model
197 Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
198 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
200 typedef opt::v::relaxed_ordering memory_model;
202 /// RCU deadlock checking policy (only for \ref cds_intrusive_IterableList_rcu "RCU-based IterableList")
204 List of available policy see \p opt::rcu_check_deadlock
206 typedef opt::v::rcu_throw_deadlock rcu_check_deadlock;
209 /// Metafunction converting option list to \p iterable_list::traits
211 Supported \p Options are:
212 - \p opt::compare - key comparison functor. No default functor is provided.
213 If the option is not specified, the \p opt::less is used.
214 - \p opt::less - specifies binary predicate used for key comparison. Default is \p std::less<T>.
215 - \p opt::node_allocator - node allocator, default is \p std::allocator.
216 - \p opt::back_off - back-off strategy used. If the option is not specified, the \p cds::backoff::Default is used.
217 - \p opt::disposer - the functor used for disposing removed items. Default is \p opt::v::empty_disposer. Due the nature
218 of GC schema the disposer may be called asynchronously.
219 - \p opt::item_counter - the type of item counting feature. Default is disabled (\p atomicity::empty_item_counter).
220 To enable item counting use \p atomicity::item_counter.
221 - \p opt::stat - internal statistics. By default, it is disabled (\p iterable_list::empty_stat).
222 To enable it use \p iterable_list::stat
223 - \p opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
224 or \p opt::v::sequential_consistent (sequentially consistent memory model).
225 - \p opt::rcu_check_deadlock - a deadlock checking policy for \ref cds_intrusive_IterableList_rcu "RCU-based IterableList"
226 Default is \p opt::v::rcu_throw_deadlock
228 template <typename... Options>
230 # ifdef CDS_DOXYGEN_INVOKED
231 typedef implementation_defined type ; ///< Metafunction result
233 typedef typename cds::opt::make_options<
234 typename cds::opt::find_type_traits< traits, Options... >::type
242 template <typename Stat>
243 struct select_stat_wrapper
246 typedef iterable_list::wrapped_stat<Stat> wrapped_stat;
253 struct select_stat_wrapper< empty_stat >
255 typedef empty_stat stat;
256 typedef empty_stat wrapped_stat;
262 template <typename Stat>
263 struct select_stat_wrapper< iterable_list::wrapped_stat<Stat>>: public select_stat_wrapper<Stat>
267 } // namespace iterable_list
270 // Forward declaration
271 template < class GC, typename T, class Traits = iterable_list::traits >
276 template <typename GC, typename T, typename Traits>
277 struct is_iterable_list< IterableList< GC, T, Traits >> {
284 }} // namespace cds::intrusive
286 #endif // #ifndef CDSLIB_INTRUSIVE_DETAILS_ITERABLE_LIST_BASE_H