3 #ifndef __CDS_CONTAINER_SKIP_LIST_SET_NOGC_H
4 #define __CDS_CONTAINER_SKIP_LIST_SET_NOGC_H
6 #include <cds/intrusive/skip_list_nogc.h>
7 #include <cds/container/skip_list_base.h>
8 #include <cds/details/binary_functor_wrapper.h>
9 #include <cds/gc/nogc.h>
10 #include <cds/details/allocator.h>
12 namespace cds { namespace container {
14 namespace skip_list { namespace details {
15 struct set_key_accessor
17 template <typename NodeType>
18 typename NodeType::stored_value_type const& operator()( NodeType const& node ) const
23 }} // namespace skip_list::details
26 template <typename T, typename Traits >
27 struct make_skip_list_set_nogc
29 typedef cds::gc::nogc gc;
31 typedef Traits type_traits;
33 typedef cds::intrusive::skip_list::node< gc > intrusive_node_type;
34 struct node_type: public intrusive_node_type
36 typedef intrusive_node_type base_class;
37 typedef typename base_class::atomic_ptr atomic_ptr;
38 typedef atomic_ptr tower_item_type;
39 typedef value_type stored_value_type;
42 //atomic_ptr m_arrTower[] ; // allocated together with node_type in single memory block
45 node_type( unsigned int nHeight, atomic_ptr * pTower, Q const& v )
49 new (pTower) atomic_ptr[ nHeight - 1 ];
50 base_class::make_tower( nHeight, pTower );
54 # ifdef CDS_EMPLACE_SUPPORT
55 template <typename Q, typename... Args>
56 node_type( unsigned int nHeight, atomic_ptr * pTower, Q&& q, Args&&... args )
57 : m_Value( std::forward<Q>(q), std::forward<Args>(args)... )
60 new (pTower) atomic_ptr[ nHeight - 1 ];
61 base_class::make_tower( nHeight, pTower );
67 node_type() ; // no default ctor
70 typedef skip_list::details::node_allocator< node_type, type_traits> node_allocator;
72 struct node_deallocator {
73 void operator ()( node_type * pNode )
75 node_allocator().Delete( pNode );
79 typedef skip_list::details::dummy_node_builder<intrusive_node_type> dummy_node_builder;
81 typedef typename type_traits::key_accessor key_accessor;
82 typedef typename opt::details::make_comparator< value_type, type_traits >::type key_comparator;
85 template <typename Less>
87 typedef compare_wrapper< node_type, cds::opt::details::make_comparator_from_less<Less>, key_accessor > type;
91 typedef typename cds::intrusive::skip_list::make_traits<
92 cds::opt::type_traits< type_traits >
93 ,cds::intrusive::opt::hook< intrusive::skip_list::base_hook< cds::opt::gc< gc > > >
94 ,cds::intrusive::opt::disposer< node_deallocator >
95 ,cds::intrusive::skip_list::internal_node_builder< dummy_node_builder >
96 ,cds::opt::compare< cds::details::compare_wrapper< node_type, key_comparator, key_accessor > >
97 >::type intrusive_type_traits;
99 typedef cds::intrusive::SkipListSet< gc, node_type, intrusive_type_traits> type;
101 } // namespace details
104 /// Lock-free skip-list set (template specialization for gc::nogc)
105 /** @ingroup cds_nonintrusive_set
106 \anchor cds_nonintrusive_SkipListSet_nogc
108 This specialization is intended for so-called persistent usage when no item
109 reclamation may be performed. The class does not support deleting of list item.
110 See \ref cds_nonintrusive_SkipListSet_hp "SkipListSet" for detailed description.
113 - \p T - type to be stored in the list.
114 - \p Traits - type traits. See skip_list::type_traits for explanation.
116 It is possible to declare option-based list with cds::container::skip_list::make_traits metafunction istead of \p Traits template
117 argument. \p Options template arguments of cds::container::skip_list::make_traits metafunction are:
118 - opt::compare - key comparison functor. No default functor is provided.
119 If the option is not specified, the opt::less is used.
120 - opt::less - specifies binary predicate used for key comparison. Default is \p std::less<T>.
121 - opt::item_counter - the type of item counting feature. Default is \ref atomicity::empty_item_counter that is no item counting.
122 - opt::memory_model - C++ memory ordering model. Can be opt::v::relaxed_ordering (relaxed memory model, the default)
123 or opt::v::sequential_consistent (sequentially consisnent memory model).
124 - skip_list::random_level_generator - random level generator. Can be skip_list::xorshift, skip_list::turbo_pascal or
125 user-provided one. See skip_list::random_level_generator option description for explanation.
126 Default is \p %skip_list::turbo_pascal.
127 - opt::allocator - allocator for skip-list node. Default is \ref CDS_DEFAULT_ALLOCATOR.
128 - opt::back_off - back-off strategy used. If the option is not specified, the cds::backoff::Default is used.
129 - opt::stat - internal statistics. Available types: skip_list::stat, skip_list::empty_stat (the default)
133 #ifdef CDS_DOXYGEN_INVOKED
134 class Traits = skip_list::type_traits
139 class SkipListSet< gc::nogc, T, Traits >:
140 #ifdef CDS_DOXYGEN_INVOKED
141 protected intrusive::SkipListSet< cds::gc::nogc, T, Traits >
143 protected details::make_skip_list_set_nogc< T, typename cds::opt::replace_key_accessor< Traits, skip_list::details::set_key_accessor >::type >::type
147 typedef details::make_skip_list_set_nogc< T, typename cds::opt::replace_key_accessor< Traits, skip_list::details::set_key_accessor >::type > maker;
148 typedef typename maker::type base_class;
151 typedef typename base_class::gc gc ; ///< Garbage collector used
152 typedef T value_type ; ///< Value type stored in the set
153 typedef Traits options ; ///< Options specified
155 typedef typename base_class::back_off back_off ; ///< Back-off strategy used
156 typedef typename options::allocator allocator_type ; ///< Allocator type used for allocate/deallocate the skip-list nodes
157 typedef typename base_class::item_counter item_counter ; ///< Item counting policy used
158 typedef typename maker::key_comparator key_comparator ; ///< key compare functor
159 typedef typename base_class::memory_model memory_model ; ///< Memory ordering. See cds::opt::memory_model option
160 typedef typename options::stat stat ; ///< internal statistics type
161 typedef typename base_class::random_level_generator random_level_generator ; ///< random level generator
165 typedef typename maker::node_type node_type;
166 typedef typename maker::node_allocator node_allocator;
167 typedef typename std::conditional<
168 std::is_same< typename options::key_accessor, opt::none >::value,
169 skip_list::details::set_key_accessor,
170 typename options::key_accessor
171 >::type key_accessor;
173 typedef std::unique_ptr< node_type, typename maker::node_deallocator > scoped_node_ptr;
175 # ifndef CDS_CXX11_LAMBDA_SUPPORT
176 struct ensure_functor
179 void operator ()( bool bNew, node_type& node, node_type& )
189 template <typename Q>
190 void operator ()( node_type& node, Q& )
200 typedef skip_list::details::iterator< typename base_class::iterator > iterator;
202 /// Const iterator type
203 typedef skip_list::details::iterator< typename base_class::const_iterator > const_iterator;
205 /// Returns a forward iterator addressing the first element in a set
208 return iterator( base_class::begin() );
211 /// Returns a forward const iterator addressing the first element in a set
213 const_iterator begin() const
215 return const_iterator( base_class::begin() );
217 const_iterator cbegin()
219 return const_iterator( base_class::cbegin() );
223 /// Returns a forward iterator that addresses the location succeeding the last element in a set.
226 return iterator( base_class::end() );
229 /// Returns a forward const iterator that addresses the location succeeding the last element in a set.
231 const_iterator end() const
233 return const_iterator( base_class::end() );
235 const_iterator cend()
237 return const_iterator( base_class::cend() );
243 static iterator node_to_iterator( node_type * pNode )
246 return iterator( base_class::iterator::from_node( pNode ));
256 /// Destructor destroys the set object
262 The function inserts \p val in the set if it does not contain
263 an item with key equal to \p val.
265 Return an iterator pointing to inserted item if success, otherwise \ref end()
267 template <typename Q>
268 iterator insert( const Q& val )
270 scoped_node_ptr sp( node_allocator().New( base_class::random_level(), val ));
271 if ( base_class::insert( *sp.get() )) {
272 return node_to_iterator( sp.release() );
277 #ifdef CDS_EMPLACE_SUPPORT
278 /// Inserts data of type \ref value_type constructed with <tt>std::forward<Args>(args)...</tt>
280 Return an iterator pointing to inserted item if success \ref end() otherwise
282 This function is available only for compiler that supports
283 variadic template and move semantics
285 template <typename... Args>
286 iterator emplace( Args&&... args )
288 scoped_node_ptr sp( node_allocator().New( base_class::random_level(), std::forward<Args>(args)... ));
289 if ( base_class::insert( *sp.get() )) {
290 return node_to_iterator( sp.release() );
296 /// Ensures that the item \p val exists in the set
298 The operation inserts new item if the key \p val is not found in the set.
299 Otherwise, the function returns an iterator that points to item found.
301 Returns <tt> std::pair<iterator, bool> </tt> where \p first is an iterator pointing to
302 item found or inserted, \p second is true if new item has been added or \p false if the item
303 already is in the set.
305 template <typename Q>
306 std::pair<iterator, bool> ensure( const Q& val )
308 scoped_node_ptr sp( node_allocator().New( base_class::random_level(), val ));
309 # ifdef CDS_CXX11_LAMBDA_SUPPORT
311 std::pair<bool, bool> bRes = base_class::ensure( *sp, [&pNode](bool, node_type& item, node_type&) { pNode = &item; } );
312 if ( bRes.first && bRes.second )
315 return std::make_pair( node_to_iterator( pNode ), bRes.second );
318 std::pair<bool, bool> bRes = base_class::ensure( *sp, cds::ref(f) );
319 if ( bRes.first && bRes.second )
322 return std::make_pair( node_to_iterator( f.pNode ), bRes.second );
327 /** \anchor cds_nonintrusive_SkipListSet_nogc_find_val
329 The function searches the item with key equal to \p key
330 and returns an iterator pointed to item found if the key is found,
331 and \ref end() otherwise
333 template <typename Q>
334 iterator find( Q const& key ) const
336 node_type * pNode = base_class::find( key );
338 return node_to_iterator( pNode );
339 return base_class::nonconst_end();
342 /// Finds the key \p val using \p pred predicate for searching
344 The function is an analog of \ref cds_nonintrusive_SkipListSet_nogc_find_val "find(Q const&)"
345 but \p pred is used for key comparing.
346 \p Less functor has the interface like \p std::less.
347 \p Less must imply the same element order as the comparator used for building the set.
349 template <typename Q, typename Less>
350 iterator find_with( Q const& key, Less pred ) const
352 node_type * pNode = base_class::find_with( key, cds::details::predicate_wrapper< node_type, Less, key_accessor>() );
354 return node_to_iterator( pNode );
355 return base_class::nonconst_end();
358 /// Gets minimum key from the set
360 If the set is empty the function returns \p nullptr
362 value_type * get_min() const
364 node_type * pNode = base_class::get_min();
365 return pNode ? &pNode->m_Value : nullptr;
368 /// Gets maximum key from the set
370 The function returns \p nullptr if the set is empty
372 value_type * get_max() const
374 node_type * pNode = base_class::get_max();
375 return pNode ? &pNode->m_Value : nullptr;
378 /// Clears the set (non-atomic)
380 The function is not atomic.
381 Finding and/or inserting is prohibited while clearing.
382 Otherwise an unpredictable result may be encountered.
383 Thus, \p clear() may be used only for debugging purposes.
390 /// Checks if the set is empty
393 return base_class::empty();
396 /// Returns item count in the set
398 The value returned depends on item counter type provided by \p Traits template parameter.
399 If it is atomicity::empty_item_counter this function always returns 0.
400 The function is not suitable for checking the set emptiness, use \ref empty
401 member function for this purpose.
405 return base_class::size();
408 /// Returns maximum height of skip-list. The max height is a constant for each object and does not exceed 32.
409 static CDS_CONSTEXPR unsigned int max_height() CDS_NOEXCEPT
411 return base_class::max_height();
414 /// Returns const reference to internal statistics
415 stat const& statistics() const
417 return base_class::statistics();
423 #endif // ifndef __CDS_CONTAINER_SKIP_LIST_SET_NOGC_H