3 #ifndef CDSLIB_CONTAINER_DETAILS_SKIP_LIST_BASE_H
4 #define CDSLIB_CONTAINER_DETAILS_SKIP_LIST_BASE_H
6 #include <cds/intrusive/details/skip_list_base.h>
7 #include <cds/container/details/base.h>
9 namespace cds { namespace container {
11 /// SkipListSet related definitions
12 /** @ingroup cds_nonintrusive_helper
15 using cds::intrusive::skip_list::implementation_tag;
17 /// Option specifying random level generator
18 template <typename Type>
19 using random_level_generator = cds::intrusive::skip_list::random_level_generator<Type>;
21 /// Xor-shift random level generator
22 typedef cds::intrusive::skip_list::xorshift xorshift;
24 /// Turbo-pascal random level generator
25 typedef cds::intrusive::skip_list::turbo_pascal turbo_pascal;
27 /// Skip list internal statistics
28 template <typename EventCounter = cds::atomicity::event_counter>
29 using stat = cds::intrusive::skip_list::stat < EventCounter >;
31 /// Skip list empty internal statistics
32 typedef cds::intrusive::skip_list::empty_stat empty_stat;
34 /// SkipListSet traits
37 /// Key comparison functor
39 No default functor is provided. If the option is not specified, the \p less is used.
41 typedef opt::none compare;
43 /// specifies binary predicate used for key compare.
45 Default is \p std::less<T>.
47 typedef opt::none less;
51 The type for item counting feature,
52 by defaulr disabled (\p atomicity::empty_item_counter)
54 typedef atomicity::empty_item_counter item_counter;
56 /// C++ memory ordering model
58 List of available memory ordering see \p opt::memory_model
60 typedef opt::v::relaxed_ordering memory_model;
62 /// Random level generator
64 The random level generator is an important part of skip-list algorithm.
65 The node height in the skip-list have a probabilistic distribution
66 where half of the nodes that have level \p i also have level <tt>i+1</tt>
67 (i = 0..30). The height of a node is in range [0..31].
69 See \p skip_list::random_level_generator option setter.
71 typedef turbo_pascal random_level_generator;
73 /// Allocator for skip-list nodes, \p std::allocator interface
74 typedef CDS_DEFAULT_ALLOCATOR allocator;
76 /// back-off strategy, default is \p cds::backoff::Default
77 typedef cds::backoff::Default back_off;
79 /// Internal statistics, by default disabled. To enable, use \p split_list::stat
80 typedef empty_stat stat;
82 /// RCU deadlock checking policy (for \ref cds_nonintrusive_SkipListSet_rcu "RCU-based SkipListSet")
84 List of available options see opt::rcu_check_deadlock
86 typedef opt::v::rcu_throw_deadlock rcu_check_deadlock;
89 // For internal use only
90 typedef opt::none key_accessor;
94 /// Metafunction converting option list to SkipListSet traits
97 - \p opt::compare - key comparison functor. No default functor is provided.
98 If the option is not specified, the \p opt::less is used.
99 - \p opt::less - specifies binary predicate used for key comparison. Default is \p std::less<T>.
100 - \p opt::item_counter - the type of item counting feature. Default is \p atomicity::empty_item_counter that is no item counting.
101 - \p opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
102 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
103 - \p skip_list::random_level_generator - random level generator. Can be \p skip_list::xorshift, \p skip_list::turbo_pascal or
105 Default is \p %skip_list::turbo_pascal.
106 - \p opt::allocator - allocator for skip-list node. Default is \ref CDS_DEFAULT_ALLOCATOR.
107 - \p opt::back_off - back-off strategy used. If the option is not specified, the \p cds::backoff::Default is used.
108 - \p opt::stat - internal statistics. Available types: \p skip_list::stat, \p skip_list::empty_stat (the default)
109 - \p opt::rcu_check_deadlock - a deadlock checking policy for RCU-based skip-list.
110 Default is \p opt::v::rcu_throw_deadlock
113 template <typename... Options>
115 # ifdef CDS_DOXYGEN_INVOKED
116 typedef implementation_defined type ; ///< Metafunction result
118 typedef typename cds::opt::make_options<
119 typename cds::opt::find_type_traits< traits, Options... >::type
128 template <typename Node, typename Traits>
132 typedef Node node_type;
133 typedef Traits traits;
135 typedef typename node_type::tower_item_type node_tower_item;
136 typedef typename traits::allocator::template rebind<unsigned char>::other tower_allocator_type;
137 typedef typename traits::allocator::template rebind<node_type>::other node_allocator_type;
139 static size_t const c_nTowerItemSize = sizeof(node_tower_item);
140 static size_t const c_nNodePadding = sizeof(node_type) % c_nTowerItemSize;
141 static size_t const c_nNodeSize = sizeof(node_type) + (c_nNodePadding ? (c_nTowerItemSize - c_nNodePadding) : 0);
143 static CDS_CONSTEXPR size_t node_size( unsigned int nHeight ) CDS_NOEXCEPT
145 return c_nNodeSize + (nHeight - 1) * c_nTowerItemSize;
147 static unsigned char * alloc_space( unsigned int nHeight )
150 unsigned char * pMem = tower_allocator_type().allocate( node_size(nHeight) );
152 // check proper alignments
153 assert( (((uintptr_t) pMem) & (alignof(node_type) - 1)) == 0 );
154 assert( (((uintptr_t) (pMem + c_nNodeSize)) & (alignof(node_tower_item) - 1)) == 0 );
158 return reinterpret_cast<unsigned char *>( node_allocator_type().allocate(1));
161 static void free_space( unsigned char * p, unsigned int nHeight )
163 assert( p != nullptr );
165 node_allocator_type().deallocate( reinterpret_cast<node_type *>(p), 1 );
167 tower_allocator_type().deallocate( p, node_size(nHeight));
171 template <typename Q>
172 node_type * New( unsigned int nHeight, Q const& v )
174 CDS_TSAN_ANNOTATE_IGNORE_WRITES_BEGIN;
175 unsigned char * pMem = alloc_space( nHeight );
176 node_type * p = new( pMem )
177 node_type( nHeight, nHeight > 1 ? reinterpret_cast<node_tower_item *>(pMem + c_nNodeSize) : nullptr, v );
178 CDS_TSAN_ANNOTATE_IGNORE_WRITES_END;
182 template <typename... Args>
183 node_type * New( unsigned int nHeight, Args&&... args )
185 CDS_TSAN_ANNOTATE_IGNORE_WRITES_BEGIN;
186 unsigned char * pMem = alloc_space( nHeight );
187 node_type * p = new( pMem )
188 node_type( nHeight, nHeight > 1 ? reinterpret_cast<node_tower_item *>(pMem + c_nNodeSize) : nullptr,
189 std::forward<Args>(args)... );
190 CDS_TSAN_ANNOTATE_IGNORE_WRITES_END;
194 void Delete( node_type * p )
196 assert( p != nullptr );
198 unsigned int nHeight = p->height();
199 node_allocator_type().destroy( p );
200 CDS_TSAN_ANNOTATE_IGNORE_WRITES_BEGIN;
201 free_space( reinterpret_cast<unsigned char *>(p), nHeight );
202 CDS_TSAN_ANNOTATE_IGNORE_WRITES_END;
206 template <typename IntrusiveNode>
207 struct dummy_node_builder {
208 typedef IntrusiveNode intrusive_node_type;
210 template <typename RandomGen>
211 static intrusive_node_type * make_tower( intrusive_node_type * pNode, RandomGen& /*gen*/ ) { return pNode ; }
212 static intrusive_node_type * make_tower( intrusive_node_type * pNode, unsigned int /*nHeight*/ ) { return pNode ; }
213 static void dispose_tower( intrusive_node_type * pNode )
215 pNode->release_tower();
218 struct node_disposer {
219 void operator()( intrusive_node_type * /*pNode*/ ) const {}
223 template <typename ForwardIterator>
226 typedef ForwardIterator intrusive_iterator;
227 typedef typename intrusive_iterator::value_type node_type;
228 typedef typename node_type::stored_value_type value_type;
229 static bool const c_isConst = intrusive_iterator::c_isConst;
231 typedef typename std::conditional< c_isConst, value_type const&, value_type&>::type value_ref;
232 template <typename FwdIt> friend class iterator;
234 intrusive_iterator m_It;
236 public: // for internal use only!!!
237 iterator( intrusive_iterator const& it )
246 iterator( iterator const& s)
250 value_type * operator ->() const
252 return &( m_It.operator->()->m_Value );
255 value_ref operator *() const
257 return m_It.operator*().m_Value;
261 iterator& operator ++()
267 iterator& operator = (iterator const& src)
273 template <typename FwIt>
274 bool operator ==(iterator<FwIt> const& i ) const
276 return m_It == i.m_It;
278 template <typename FwIt>
279 bool operator !=(iterator<FwIt> const& i ) const
281 return !( *this == i );
285 } // namespace details
288 } // namespace skip_list
290 // Forward declaration
291 template <class GC, typename T, typename Traits = skip_list::traits >
294 // Forward declaration
295 template <class GC, typename K, typename T, typename Traits = skip_list::traits >
298 }} // namespace cds::container
300 #endif // #ifndef CDSLIB_CONTAINER_DETAILS_SKIP_LIST_BASE_H