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 typedef cds::intrusive::skip_list::xorshift xorshift;
50 /// Turbo-pascal random level generator
51 typedef cds::intrusive::skip_list::turbo_pascal turbo_pascal;
53 /// Skip list internal statistics
54 template <typename EventCounter = cds::atomicity::event_counter>
55 using stat = cds::intrusive::skip_list::stat < EventCounter >;
57 /// Skip list empty internal statistics
58 typedef cds::intrusive::skip_list::empty_stat empty_stat;
60 /// SkipListSet traits
63 /// Key comparison functor
65 No default functor is provided. If the option is not specified, the \p less is used.
67 typedef opt::none compare;
69 /// specifies binary predicate used for key compare.
71 Default is \p std::less<T>.
73 typedef opt::none less;
77 The type for item counting feature,
78 by defaulr disabled (\p atomicity::empty_item_counter)
80 typedef atomicity::empty_item_counter item_counter;
82 /// C++ memory ordering model
84 List of available memory ordering see \p opt::memory_model
86 typedef opt::v::relaxed_ordering memory_model;
88 /// Random level generator
90 The random level generator is an important part of skip-list algorithm.
91 The node height in the skip-list have a probabilistic distribution
92 where half of the nodes that have level \p i also have level <tt>i+1</tt>
93 (i = 0..30). The height of a node is in range [0..31].
95 See \p skip_list::random_level_generator option setter.
97 typedef turbo_pascal random_level_generator;
99 /// Allocator for skip-list nodes, \p std::allocator interface
100 typedef CDS_DEFAULT_ALLOCATOR allocator;
102 /// back-off strategy, default is \p cds::backoff::Default
103 typedef cds::backoff::Default back_off;
105 /// Internal statistics, by default disabled. To enable, use \p split_list::stat
106 typedef empty_stat stat;
108 /// RCU deadlock checking policy (for \ref cds_nonintrusive_SkipListSet_rcu "RCU-based SkipListSet")
110 List of available options see opt::rcu_check_deadlock
112 typedef opt::v::rcu_throw_deadlock rcu_check_deadlock;
115 // For internal use only
116 typedef opt::none key_accessor;
120 /// Metafunction converting option list to SkipListSet traits
123 - \p opt::compare - key comparison functor. No default functor is provided.
124 If the option is not specified, the \p opt::less is used.
125 - \p opt::less - specifies binary predicate used for key comparison. Default is \p std::less<T>.
126 - \p opt::item_counter - the type of item counting feature. Default is \p atomicity::empty_item_counter that is no item counting.
127 - \p opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
128 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
129 - \p skip_list::random_level_generator - random level generator. Can be \p skip_list::xorshift, \p skip_list::turbo_pascal or
131 Default is \p %skip_list::turbo_pascal.
132 - \p opt::allocator - allocator for skip-list node. Default is \ref CDS_DEFAULT_ALLOCATOR.
133 - \p opt::back_off - back-off strategy used. If the option is not specified, the \p cds::backoff::Default is used.
134 - \p opt::stat - internal statistics. Available types: \p skip_list::stat, \p skip_list::empty_stat (the default)
135 - \p opt::rcu_check_deadlock - a deadlock checking policy for RCU-based skip-list.
136 Default is \p opt::v::rcu_throw_deadlock
139 template <typename... Options>
141 # ifdef CDS_DOXYGEN_INVOKED
142 typedef implementation_defined type ; ///< Metafunction result
144 typedef typename cds::opt::make_options<
145 typename cds::opt::find_type_traits< traits, Options... >::type
154 template <typename Node, typename Traits>
158 typedef Node node_type;
159 typedef Traits traits;
161 typedef typename node_type::tower_item_type node_tower_item;
162 typedef typename traits::allocator::template rebind<unsigned char>::other tower_allocator_type;
163 typedef typename traits::allocator::template rebind<node_type>::other node_allocator_type;
165 static size_t const c_nTowerItemSize = sizeof(node_tower_item);
166 static size_t const c_nNodePadding = sizeof(node_type) % c_nTowerItemSize;
167 static size_t const c_nNodeSize = sizeof(node_type) + (c_nNodePadding ? (c_nTowerItemSize - c_nNodePadding) : 0);
169 static CDS_CONSTEXPR size_t node_size( unsigned int nHeight ) CDS_NOEXCEPT
171 return c_nNodeSize + (nHeight - 1) * c_nTowerItemSize;
173 static unsigned char * alloc_space( unsigned int nHeight )
176 unsigned char * pMem = tower_allocator_type().allocate( node_size(nHeight));
178 // check proper alignments
179 assert( (((uintptr_t) pMem) & (alignof(node_type) - 1)) == 0 );
180 assert( (((uintptr_t) (pMem + c_nNodeSize)) & (alignof(node_tower_item) - 1)) == 0 );
184 return reinterpret_cast<unsigned char *>( node_allocator_type().allocate(1));
187 static void free_space( unsigned char * p, unsigned int nHeight )
189 assert( p != nullptr );
191 node_allocator_type().deallocate( reinterpret_cast<node_type *>(p), 1 );
193 tower_allocator_type().deallocate( p, node_size(nHeight));
197 template <typename Q>
198 node_type * New( unsigned int nHeight, Q const& v )
200 unsigned char * pMem = alloc_space( nHeight );
201 node_type * p = new( pMem )
202 node_type( nHeight, nHeight > 1 ? reinterpret_cast<node_tower_item *>(pMem + c_nNodeSize) : nullptr, v );
206 template <typename... Args>
207 node_type * New( unsigned int nHeight, Args&&... args )
209 unsigned char * pMem = alloc_space( nHeight );
210 node_type * p = new( pMem )
211 node_type( nHeight, nHeight > 1 ? reinterpret_cast<node_tower_item *>(pMem + c_nNodeSize) : nullptr,
212 std::forward<Args>(args)... );
216 void Delete( node_type * p )
218 assert( p != nullptr );
220 unsigned int nHeight = p->height();
221 node_allocator_type().destroy( p );
222 free_space( reinterpret_cast<unsigned char *>(p), nHeight );
226 template <typename IntrusiveNode>
227 struct dummy_node_builder {
228 typedef IntrusiveNode intrusive_node_type;
230 template <typename RandomGen>
231 static intrusive_node_type * make_tower( intrusive_node_type * pNode, RandomGen& /*gen*/ ) { return pNode ; }
232 static intrusive_node_type * make_tower( intrusive_node_type * pNode, unsigned int /*nHeight*/ ) { return pNode ; }
233 static void dispose_tower( intrusive_node_type * pNode )
235 pNode->release_tower();
238 struct node_disposer {
239 void operator()( intrusive_node_type * /*pNode*/ ) const {}
243 template <typename ForwardIterator>
246 typedef ForwardIterator intrusive_iterator;
247 typedef typename intrusive_iterator::value_type node_type;
248 typedef typename node_type::stored_value_type value_type;
249 static bool const c_isConst = intrusive_iterator::c_isConst;
251 typedef typename std::conditional< c_isConst, value_type const&, value_type&>::type value_ref;
252 template <typename FwdIt> friend class iterator;
254 intrusive_iterator m_It;
256 public: // for internal use only!!!
257 iterator( intrusive_iterator const& it )
266 iterator( iterator const& s)
270 value_type * operator ->() const
272 return &( m_It.operator->()->m_Value );
275 value_ref operator *() const
277 return m_It.operator*().m_Value;
281 iterator& operator ++()
287 iterator& operator = (iterator const& src)
293 template <typename FwIt>
294 bool operator ==(iterator<FwIt> const& i ) const
296 return m_It == i.m_It;
298 template <typename FwIt>
299 bool operator !=(iterator<FwIt> const& i ) const
301 return !( *this == i );
305 } // namespace details
308 } // namespace skip_list
310 // Forward declaration
311 template <class GC, typename T, typename Traits = skip_list::traits >
314 // Forward declaration
315 template <class GC, typename K, typename T, typename Traits = skip_list::traits >
318 }} // namespace cds::container
320 #endif // #ifndef CDSLIB_CONTAINER_DETAILS_SKIP_LIST_BASE_H