3 #ifndef __CDS_CONTAINER_SKIP_LIST_BASE_H
4 #define __CDS_CONTAINER_SKIP_LIST_BASE_H
6 #include <cds/intrusive/skip_list_base.h>
7 #include <cds/container/base.h>
9 namespace cds { namespace container {
11 /// SkipListSet related definitions
12 /** @ingroup cds_nonintrusive_helper
16 #ifdef CDS_DOXYGEN_INVOKED
17 /// Typedef for intrusive::skip_list::random_level_generator template
18 struct random_level_generator {};
20 using cds::intrusive::skip_list::random_level_generator;
23 #ifdef CDS_DOXYGEN_INVOKED
24 /// Typedef for intrusive::skip_list::xorshift class
27 using cds::intrusive::skip_list::xorshift;
30 #ifdef CDS_DOXYGEN_INVOKED
31 /// Typedef for intrusive::skip_list::turbo_pascal class
32 class turbo_pascal {};
34 using cds::intrusive::skip_list::turbo_pascal;
37 #ifdef CDS_DOXYGEN_INVOKED
38 /// Typedef for intrusive::skip_list::stat class
41 using cds::intrusive::skip_list::stat;
44 #ifdef CDS_DOXYGEN_INVOKED
45 /// Typedef for intrusive::skip_list::empty_stat class
48 using cds::intrusive::skip_list::empty_stat;
51 /// Type traits for SkipListSet class
54 /// Key comparison functor
56 No default functor is provided. If the option is not specified, the \p less is used.
58 typedef opt::none compare;
60 /// specifies binary predicate used for key compare.
62 Default is \p std::less<T>.
64 typedef opt::none less;
68 The type for item counting feature.
69 Default is no item counter (\ref atomicity::empty_item_counter)
71 typedef atomicity::empty_item_counter item_counter;
73 /// C++ memory ordering model
75 List of available memory ordering see opt::memory_model
77 typedef opt::v::relaxed_ordering memory_model;
79 /// Random level generator
81 The random level generator is an important part of skip-list algorithm.
82 The node height in the skip-list have a probabilistic distribution
83 where half of the nodes that have level \p i also have level <tt>i+1</tt>
84 (i = 0..30). The height of a node is in range [0..31].
86 See skip_list::random_level_generator option setter.
88 typedef turbo_pascal random_level_generator;
90 /// Allocator for skip-list nodes, \p std::allocator interface
91 typedef CDS_DEFAULT_ALLOCATOR allocator;
93 /// back-off strategy used
95 If the option is not specified, the cds::backoff::Default is used.
97 typedef cds::backoff::Default back_off;
99 /// Internal statistics
100 typedef empty_stat stat;
102 /// RCU deadlock checking policy (for \ref cds_nonintrusive_SkipListSet_rcu "RCU-based SkipListSet")
104 List of available options see opt::rcu_check_deadlock
106 typedef opt::v::rcu_throw_deadlock rcu_check_deadlock;
109 // For internal use only
110 typedef opt::none key_accessor;
114 /// Metafunction converting option list to SkipListSet traits
116 This is a wrapper for <tt> cds::opt::make_options< type_traits, Options...> </tt>
117 \p Options list see \ref SkipListSet.
119 template <CDS_DECL_OPTIONS10>
121 # ifdef CDS_DOXYGEN_INVOKED
122 typedef implementation_defined type ; ///< Metafunction result
124 typedef typename cds::opt::make_options<
125 typename cds::opt::find_type_traits< type_traits, CDS_OPTIONS10 >::type
134 template <typename Node, typename Traits>
138 typedef Node node_type;
139 typedef Traits type_traits;
141 typedef typename node_type::tower_item_type node_tower_item;
142 typedef typename type_traits::allocator::template rebind<unsigned char>::other tower_allocator_type;
143 typedef typename type_traits::allocator::template rebind<node_type>::other node_allocator_type;
145 static size_t const c_nTowerItemSize = sizeof(node_tower_item);
146 static size_t const c_nNodePadding = sizeof(node_type) % c_nTowerItemSize;
147 static size_t const c_nNodeSize = sizeof(node_type) + (c_nNodePadding ? (c_nTowerItemSize - c_nNodePadding) : 0);
149 static CDS_CONSTEXPR size_t node_size( unsigned int nHeight ) CDS_NOEXCEPT
151 return c_nNodeSize + (nHeight - 1) * c_nTowerItemSize;
153 static unsigned char * alloc_space( unsigned int nHeight )
156 unsigned char * pMem = tower_allocator_type().allocate( node_size(nHeight) );
158 // check proper alignments
159 assert( (((uintptr_t) pMem) & (alignof(node_type) - 1)) == 0 );
160 assert( (((uintptr_t) (pMem + c_nNodeSize)) & (alignof(node_tower_item) - 1)) == 0 );
164 return reinterpret_cast<unsigned char *>( node_allocator_type().allocate(1));
167 static void free_space( unsigned char * p, unsigned int nHeight )
169 assert( p != nullptr );
171 node_allocator_type().deallocate( reinterpret_cast<node_type *>(p), 1 );
173 tower_allocator_type().deallocate( p, node_size(nHeight));
177 template <typename Q>
178 node_type * New( unsigned int nHeight, Q const& v )
180 unsigned char * pMem = alloc_space( nHeight );
182 node_type( nHeight, nHeight > 1 ? reinterpret_cast<node_tower_item *>(pMem + c_nNodeSize) : nullptr, v );
185 # ifdef CDS_EMPLACE_SUPPORT
186 template <typename... Args>
187 node_type * New( unsigned int nHeight, Args&&... args )
189 unsigned char * pMem = alloc_space( nHeight );
191 node_type( nHeight, nHeight > 1 ? reinterpret_cast<node_tower_item *>(pMem + c_nNodeSize) : nullptr,
192 std::forward<Args>(args)... );
196 void Delete( node_type * p )
198 assert( p != nullptr );
200 unsigned int nHeight = p->height();
201 node_allocator_type().destroy( p );
202 free_space( reinterpret_cast<unsigned char *>(p), nHeight );
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;
233 intrusive_iterator m_It;
235 public: // for internal use only!!!
236 iterator( intrusive_iterator const& it )
245 iterator( iterator const& s)
249 value_type * operator ->() const
251 return &( m_It.operator->()->m_Value );
254 value_ref operator *() const
256 return m_It.operator*().m_Value;
260 iterator& operator ++()
266 iterator& operator = (iterator const& src)
272 template <typename FwIt>
273 bool operator ==(iterator<FwIt> const& i ) const
275 return m_It == i.m_It;
277 template <typename FwIt>
278 bool operator !=(iterator<FwIt> const& i ) const
280 return !( *this == i );
284 } // namespace details
287 } // namespace skip_list
289 // Forward declaration
290 template <class GC, typename T, typename Traits = skip_list::type_traits >
293 // Forward declaration
294 template <class GC, typename K, typename T, typename Traits = skip_list::type_traits >
297 }} // namespace cds::container
299 #endif // #ifndef __CDS_CONTAINER_SKIP_LIST_BASE_H