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_CONTAINER_DETAILS_SKIP_LIST_BASE_H
32 #define CDSLIB_CONTAINER_DETAILS_SKIP_LIST_BASE_H
34 #include <cds/intrusive/details/skip_list_base.h>
35 #include <cds/container/details/base.h>
37 namespace cds { namespace container {
39 /// SkipListSet related definitions
40 /** @ingroup cds_nonintrusive_helper
43 /// Option specifying random level generator
44 template <typename Type>
45 using random_level_generator = cds::intrusive::skip_list::random_level_generator<Type>;
47 /// Xor-shift random level generator
48 template <unsigned MaxHeight>
49 using xor_shift = cds::intrusive::skip_list::xor_shift<MaxHeight >;
51 /// Xor-shift random level generator, max height 32
52 typedef cds::intrusive::skip_list::xorshift32 xorshift32;
54 /// Xor-shift random level generator, max height 24
55 typedef cds::intrusive::skip_list::xorshift24 xorshift24;
57 /// Xor-shift random level generator, max height 16
58 typedef cds::intrusive::skip_list::xorshift16 xorshift16;
61 // for backward compatibility
62 using cds::intrusive::skip_list::xorshift;
65 /// Turbo-pascal random level generator
66 template <unsigned MaxHeight>
67 using turbo = cds::intrusive::skip_list::turbo<MaxHeight >;
69 /// Turbo-pascal random level generator, max height 32
70 typedef cds::intrusive::skip_list::turbo32 turbo32;
72 /// Turbo-pascal random level generator, max height 24
73 typedef cds::intrusive::skip_list::turbo24 turbo24;
75 /// Turbo-pascal random level generator, max height 16
76 typedef cds::intrusive::skip_list::turbo16 turbo16;
79 // for backward compatibility
80 using cds::intrusive::skip_list::turbo_pascal;
83 /// Skip list internal statistics
84 template <typename EventCounter = cds::atomicity::event_counter>
85 using stat = cds::intrusive::skip_list::stat < EventCounter >;
87 /// Skip list empty internal statistics
88 typedef cds::intrusive::skip_list::empty_stat empty_stat;
90 /// SkipListSet traits
93 /// Key comparison functor
95 No default functor is provided. If the option is not specified, the \p less is used.
97 typedef opt::none compare;
99 /// specifies binary predicate used for key compare.
101 Default is \p std::less<T>.
103 typedef opt::none less;
107 The type for item counting feature,
108 by defaulr disabled (\p atomicity::empty_item_counter)
110 typedef atomicity::empty_item_counter item_counter;
112 /// C++ memory ordering model
114 List of available memory ordering see \p opt::memory_model
116 typedef opt::v::relaxed_ordering memory_model;
118 /// Random level generator
120 The random level generator is an important part of skip-list algorithm.
121 The node height in the skip-list have a probabilistic distribution
122 where half of the nodes that have level \p i also have level <tt>i+1</tt>
123 (i = 0..30). The height of a node is in range [0..31].
125 See \p skip_list::random_level_generator option setter.
127 typedef turbo32 random_level_generator;
129 /// Allocator for skip-list nodes, \p std::allocator interface
130 typedef CDS_DEFAULT_ALLOCATOR allocator;
132 /// back-off strategy, default is \p cds::backoff::Default
133 typedef cds::backoff::Default back_off;
135 /// Internal statistics, by default disabled. To enable, use \p split_list::stat
136 typedef empty_stat stat;
138 /// RCU deadlock checking policy (for \ref cds_nonintrusive_SkipListSet_rcu "RCU-based SkipListSet")
140 List of available options see opt::rcu_check_deadlock
142 typedef opt::v::rcu_throw_deadlock rcu_check_deadlock;
145 // For internal use only
146 typedef opt::none key_accessor;
150 /// Metafunction converting option list to SkipListSet traits
153 - \p opt::compare - key comparison functor. No default functor is provided.
154 If the option is not specified, the \p opt::less is used.
155 - \p opt::less - specifies binary predicate used for key comparison. Default is \p std::less<T>.
156 - \p opt::item_counter - the type of item counting feature. Default is \p atomicity::empty_item_counter that is no item counting.
157 - \p opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
158 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
159 - \p skip_list::random_level_generator - random level generator. Can be \p skip_list::xor_shift, \p skip_list::turbo or
160 user-provided one. Default is \p %skip_list::turbo32.
161 - \p opt::allocator - allocator for skip-list node. Default is \ref CDS_DEFAULT_ALLOCATOR.
162 - \p opt::back_off - back-off strategy used. If the option is not specified, the \p cds::backoff::Default is used.
163 - \p opt::stat - internal statistics. Available types: \p skip_list::stat, \p skip_list::empty_stat (the default)
164 - \p opt::rcu_check_deadlock - a deadlock checking policy for RCU-based skip-list.
165 Default is \p opt::v::rcu_throw_deadlock
168 template <typename... Options>
170 # ifdef CDS_DOXYGEN_INVOKED
171 typedef implementation_defined type ; ///< Metafunction result
173 typedef typename cds::opt::make_options<
174 typename cds::opt::find_type_traits< traits, Options... >::type
183 template <typename Node, typename Traits>
187 typedef Node node_type;
188 typedef Traits traits;
190 typedef typename node_type::tower_item_type node_tower_item;
191 typedef typename traits::allocator::template rebind<unsigned char>::other tower_allocator_type;
192 typedef typename traits::allocator::template rebind<node_type>::other node_allocator_type;
194 static size_t const c_nTowerItemSize = sizeof(node_tower_item);
195 static size_t const c_nNodePadding = sizeof(node_type) % c_nTowerItemSize;
196 static size_t const c_nNodeSize = sizeof(node_type) + (c_nNodePadding ? (c_nTowerItemSize - c_nNodePadding) : 0);
198 static CDS_CONSTEXPR size_t node_size( unsigned int nHeight ) CDS_NOEXCEPT
200 return c_nNodeSize + (nHeight - 1) * c_nTowerItemSize;
203 static unsigned char * alloc_space( unsigned int nHeight )
205 unsigned char * pMem;
206 size_t const sz = node_size( nHeight );
209 pMem = tower_allocator_type().allocate( sz );
211 // check proper alignments
212 assert( (((uintptr_t) pMem) & (alignof(node_type) - 1)) == 0 );
213 assert( (((uintptr_t) (pMem + c_nNodeSize)) & (alignof(node_tower_item) - 1)) == 0 );
217 pMem = reinterpret_cast<unsigned char *>( node_allocator_type().allocate( 1 ));
222 static void free_space( unsigned char * p, unsigned int nHeight )
224 assert( p != nullptr );
227 node_allocator_type().deallocate( reinterpret_cast<node_type *>(p), 1 );
229 tower_allocator_type().deallocate( p, node_size(nHeight));
233 template <typename Q>
234 node_type * New( unsigned int nHeight, Q const& v )
236 unsigned char * pMem = alloc_space( nHeight );
237 node_type * p = new( pMem )
238 node_type( nHeight, nHeight > 1 ? reinterpret_cast<node_tower_item *>(pMem + c_nNodeSize) : nullptr, v );
242 template <typename... Args>
243 node_type * New( unsigned int nHeight, Args&&... args )
245 unsigned char * pMem = alloc_space( nHeight );
246 node_type * p = new( pMem )
247 node_type( nHeight, nHeight > 1 ? reinterpret_cast<node_tower_item *>(pMem + c_nNodeSize) : nullptr,
248 std::forward<Args>(args)... );
252 void Delete( node_type * p )
254 assert( p != nullptr );
256 unsigned int nHeight = p->height();
257 node_allocator_type().destroy( p );
258 free_space( reinterpret_cast<unsigned char *>(p), nHeight );
262 template <typename IntrusiveNode>
263 struct dummy_node_builder {
264 typedef IntrusiveNode intrusive_node_type;
266 template <typename RandomGen>
267 static intrusive_node_type * make_tower( intrusive_node_type * pNode, RandomGen& /*gen*/ ) { return pNode ; }
268 static intrusive_node_type * make_tower( intrusive_node_type * pNode, unsigned int /*nHeight*/ ) { return pNode ; }
269 static void dispose_tower( intrusive_node_type * pNode )
271 pNode->release_tower();
274 struct node_disposer {
275 void operator()( intrusive_node_type * /*pNode*/ ) const {}
279 template <typename ForwardIterator>
282 typedef ForwardIterator intrusive_iterator;
283 typedef typename intrusive_iterator::value_type node_type;
284 typedef typename node_type::stored_value_type value_type;
285 static bool const c_isConst = intrusive_iterator::c_isConst;
287 typedef typename std::conditional< c_isConst, value_type const&, value_type&>::type value_ref;
288 template <typename FwdIt> friend class iterator;
290 intrusive_iterator m_It;
292 public: // for internal use only!!!
293 iterator( intrusive_iterator const& it )
302 iterator( iterator const& s)
306 value_type * operator ->() const
308 return &( m_It.operator->()->m_Value );
311 value_ref operator *() const
313 return m_It.operator*().m_Value;
317 iterator& operator ++()
323 iterator& operator = (iterator const& src)
329 template <typename FwIt>
330 bool operator ==(iterator<FwIt> const& i ) const
332 return m_It == i.m_It;
334 template <typename FwIt>
335 bool operator !=(iterator<FwIt> const& i ) const
337 return !( *this == i );
341 } // namespace details
344 } // namespace skip_list
346 // Forward declaration
347 template <class GC, typename T, typename Traits = skip_list::traits >
350 // Forward declaration
351 template <class GC, typename K, typename T, typename Traits = skip_list::traits >
354 }} // namespace cds::container
356 #endif // #ifndef CDSLIB_CONTAINER_DETAILS_SKIP_LIST_BASE_H