2 This file is a part of libcds - Concurrent Data Structures library
4 (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016
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_SKIP_LIST_SET_NOGC_H
32 #define CDSLIB_CONTAINER_SKIP_LIST_SET_NOGC_H
34 #include <cds/intrusive/skip_list_nogc.h>
35 #include <cds/container/details/skip_list_base.h>
36 #include <cds/details/binary_functor_wrapper.h>
37 #include <cds/gc/nogc.h>
38 #include <cds/details/allocator.h>
40 namespace cds { namespace container {
42 namespace skip_list { namespace details {
43 struct set_key_accessor
45 template <typename NodeType>
46 typename NodeType::stored_value_type const& operator()( NodeType const& node ) const
51 }} // namespace skip_list::details
54 template <typename T, typename Traits >
55 struct make_skip_list_set_nogc
57 typedef cds::gc::nogc gc;
59 typedef Traits traits;
61 typedef cds::intrusive::skip_list::node< gc > intrusive_node_type;
62 struct node_type: public intrusive_node_type
64 typedef intrusive_node_type base_class;
65 typedef typename base_class::atomic_ptr atomic_ptr;
66 typedef atomic_ptr tower_item_type;
67 typedef value_type stored_value_type;
70 //atomic_ptr m_arrTower[] ; // allocated together with node_type in single memory block
73 node_type( unsigned int nHeight, atomic_ptr * pTower, Q const& v )
77 new (pTower) atomic_ptr[ nHeight - 1 ];
78 base_class::make_tower( nHeight, pTower );
82 template <typename Q, typename... Args>
83 node_type( unsigned int nHeight, atomic_ptr * pTower, Q&& q, Args&&... args )
84 : m_Value( std::forward<Q>(q), std::forward<Args>(args)... )
87 new (pTower) atomic_ptr[ nHeight - 1 ];
88 base_class::make_tower( nHeight, pTower );
92 node_type() = delete; // no default ctor
95 typedef skip_list::details::node_allocator< node_type, traits> node_allocator;
97 struct node_deallocator {
98 void operator ()( node_type * pNode )
100 node_allocator().Delete( pNode );
104 typedef skip_list::details::dummy_node_builder<intrusive_node_type> dummy_node_builder;
106 typedef typename traits::key_accessor key_accessor;
107 typedef typename opt::details::make_comparator< value_type, traits >::type key_comparator;
110 template <typename Less>
111 struct less_wrapper {
112 typedef compare_wrapper< node_type, cds::opt::details::make_comparator_from_less<Less>, key_accessor > type;
116 typedef typename cds::intrusive::skip_list::make_traits<
117 cds::opt::type_traits< traits >
118 ,cds::intrusive::opt::hook< intrusive::skip_list::base_hook< cds::opt::gc< gc > > >
119 ,cds::intrusive::opt::disposer< node_deallocator >
120 ,cds::intrusive::skip_list::internal_node_builder< dummy_node_builder >
121 ,cds::opt::compare< cds::details::compare_wrapper< node_type, key_comparator, key_accessor > >
122 >::type intrusive_type_traits;
124 typedef cds::intrusive::SkipListSet< gc, node_type, intrusive_type_traits> type;
126 } // namespace details
129 /// Lock-free skip-list set (template specialization for gc::nogc)
130 /** @ingroup cds_nonintrusive_set
131 \anchor cds_nonintrusive_SkipListSet_nogc
133 This specialization is intended for so-called persistent usage when no item
134 reclamation may be performed. The class does not support deleting of list item.
135 See \ref cds_nonintrusive_SkipListSet_hp "SkipListSet" for detailed description.
138 - \p T - type to be stored in the list.
139 - \p Traits - type traits. See skip_list::traits for explanation.
141 It is possible to declare option-based list with cds::container::skip_list::make_traits metafunction istead of \p Traits template
142 argument. \p Options template arguments of cds::container::skip_list::make_traits metafunction are:
143 - opt::compare - key comparison functor. No default functor is provided.
144 If the option is not specified, the opt::less is used.
145 - opt::less - specifies binary predicate used for key comparison. Default is \p std::less<T>.
146 - opt::item_counter - the type of item counting feature. Default is \ref atomicity::empty_item_counter that is no item counting.
147 - opt::memory_model - C++ memory ordering model. Can be opt::v::relaxed_ordering (relaxed memory model, the default)
148 or opt::v::sequential_consistent (sequentially consisnent memory model).
149 - skip_list::random_level_generator - random level generator. Can be skip_list::xorshift, skip_list::turbo_pascal or
150 user-provided one. See skip_list::random_level_generator option description for explanation.
151 Default is \p %skip_list::turbo_pascal.
152 - opt::allocator - allocator for skip-list node. Default is \ref CDS_DEFAULT_ALLOCATOR.
153 - opt::back_off - back-off strategy used. If the option is not specified, the cds::backoff::Default is used.
154 - opt::stat - internal statistics. Available types: skip_list::stat, skip_list::empty_stat (the default)
158 #ifdef CDS_DOXYGEN_INVOKED
159 class Traits = skip_list::traits
164 class SkipListSet< gc::nogc, T, Traits >:
165 #ifdef CDS_DOXYGEN_INVOKED
166 protected intrusive::SkipListSet< cds::gc::nogc, T, Traits >
168 protected details::make_skip_list_set_nogc< T, typename cds::opt::replace_key_accessor< Traits, skip_list::details::set_key_accessor >::type >::type
172 typedef details::make_skip_list_set_nogc< T, typename cds::opt::replace_key_accessor< Traits, skip_list::details::set_key_accessor >::type > maker;
173 typedef typename maker::type base_class;
176 typedef typename base_class::gc gc ; ///< Garbage collector used
177 typedef T value_type ; ///< Value type stored in the set
178 typedef Traits options ; ///< Options specified
180 typedef typename base_class::back_off back_off ; ///< Back-off strategy used
181 typedef typename options::allocator allocator_type ; ///< Allocator type used for allocate/deallocate the skip-list nodes
182 typedef typename base_class::item_counter item_counter ; ///< Item counting policy used
183 typedef typename maker::key_comparator key_comparator ; ///< key compare functor
184 typedef typename base_class::memory_model memory_model ; ///< Memory ordering. See cds::opt::memory_model option
185 typedef typename options::stat stat ; ///< internal statistics type
186 typedef typename base_class::random_level_generator random_level_generator ; ///< random level generator
190 typedef typename maker::node_type node_type;
191 typedef typename maker::node_allocator node_allocator;
192 typedef typename std::conditional<
193 std::is_same< typename options::key_accessor, opt::none >::value,
194 skip_list::details::set_key_accessor,
195 typename options::key_accessor
196 >::type key_accessor;
198 typedef std::unique_ptr< node_type, typename maker::node_deallocator > scoped_node_ptr;
202 ///@name Forward iterators
204 /// Forward ordered iterator
206 The forward iterator for a split-list has some features:
207 - it has no post-increment operator
208 - it depends on iterator of underlying \p OrderedList
210 typedef skip_list::details::iterator< typename base_class::iterator > iterator;
212 /// Const iterator type
213 typedef skip_list::details::iterator< typename base_class::const_iterator > const_iterator;
215 /// Returns a forward iterator addressing the first element in a set
218 return iterator( base_class::begin() );
221 /// Returns a forward const iterator addressing the first element in a set
222 const_iterator begin() const
224 return const_iterator( base_class::begin() );
227 /// Returns a forward const iterator addressing the first element in a set
228 const_iterator cbegin() const
230 return const_iterator( base_class::cbegin() );
233 /// Returns a forward iterator that addresses the location succeeding the last element in a set.
236 return iterator( base_class::end() );
239 /// Returns a forward const iterator that addresses the location succeeding the last element in a set.
240 const_iterator end() const
242 return const_iterator( base_class::end() );
244 /// Returns a forward const iterator that addresses the location succeeding the last element in a set.
245 const_iterator cend() const
247 return const_iterator( base_class::cend() );
253 static iterator node_to_iterator( node_type * pNode )
256 return iterator( base_class::iterator::from_node( pNode ));
266 /// Destructor destroys the set object
272 The function inserts \p val in the set if it does not contain
273 an item with key equal to \p val.
275 Return an iterator pointing to inserted item if success, otherwise \ref end()
277 template <typename Q>
278 iterator insert( const Q& val )
280 scoped_node_ptr sp( node_allocator().New( base_class::random_level(), val ));
281 if ( base_class::insert( *sp.get() )) {
282 return node_to_iterator( sp.release() );
287 /// Inserts data of type \ref value_type constructed with <tt>std::forward<Args>(args)...</tt>
289 Return an iterator pointing to inserted item if success \ref end() otherwise
291 template <typename... Args>
292 iterator emplace( Args&&... args )
294 scoped_node_ptr sp( node_allocator().New( base_class::random_level(), std::forward<Args>(args)... ));
295 if ( base_class::insert( *sp.get() )) {
296 return node_to_iterator( sp.release() );
303 The operation inserts new item if \p val is not found in the set and \p bInsert is \p true.
304 Otherwise, if that key exists, the function returns an iterator that points to item found.
306 Returns <tt> std::pair<iterator, bool> </tt> where \p first is an iterator pointing to
307 item found or inserted or \p end() if \p val is not found and \p bInsert is \p false,
308 \p second is \p true if new item has been added or \p false if the item
309 already is in the set.
311 template <typename Q>
312 std::pair<iterator, bool> update( const Q& val, bool bInsert = true )
314 scoped_node_ptr sp( node_allocator().New( base_class::random_level(), val ));
316 std::pair<bool, bool> bRes = base_class::update( *sp, [&pNode](bool, node_type& item, node_type&) { pNode = &item; }, bInsert );
317 if ( bRes.first && bRes.second )
319 else if ( !bRes.first )
320 return std::make_pair( end(), false );
322 return std::make_pair( node_to_iterator( pNode ), bRes.second );
325 template <typename Q>
326 CDS_DEPRECATED("ensure() is deprecated, use update()")
327 std::pair<iterator, bool> ensure( const Q& val )
329 return update( val, true );
333 /// Checks whether the set contains \p key
335 The function searches the item with key equal to \p key
336 and returns an iterator to item found or \p end() if the key is not fund
338 template <typename Q>
339 iterator contains( Q const& key ) const
341 node_type * pNode = base_class::contains( key );
343 return node_to_iterator( pNode );
344 return base_class::nonconst_end();
347 template <typename Q>
348 CDS_DEPRECATED("deprecated, use contains()")
349 iterator find( Q const& key ) const
351 return contains( key );
355 /// Checks whether the set contains \p key using \p pred predicate for searching
357 The function is similar to <tt>contains( key )</tt> but \p pred is used for key comparing.
358 \p Less functor has the interface like \p std::less.
359 \p Less must imply the same element order as the comparator used for building the set.
361 template <typename Q, typename Less>
362 iterator contains( Q const& key, Less pred ) const
365 node_type * pNode = base_class::contains( key, cds::details::predicate_wrapper< node_type, Less, key_accessor>() );
367 return node_to_iterator( pNode );
368 return base_class::nonconst_end();
371 template <typename Q, typename Less>
372 CDS_DEPRECATED("deprecated, use contains()")
373 iterator find_with( Q const& key, Less pred ) const
375 return contains( key, pred );
379 /// Gets minimum key from the set
381 If the set is empty the function returns \p nullptr
383 value_type * get_min() const
385 node_type * pNode = base_class::get_min();
386 return pNode ? &pNode->m_Value : nullptr;
389 /// Gets maximum key from the set
391 The function returns \p nullptr if the set is empty
393 value_type * get_max() const
395 node_type * pNode = base_class::get_max();
396 return pNode ? &pNode->m_Value : nullptr;
399 /// Clears the set (non-atomic)
401 The function is not atomic.
402 Finding and/or inserting is prohibited while clearing.
403 Otherwise an unpredictable result may be encountered.
404 Thus, \p clear() may be used only for debugging purposes.
411 /// Checks if the set is empty
414 return base_class::empty();
417 /// Returns item count in the set
419 The value returned depends on item counter type provided by \p Traits template parameter.
420 If it is atomicity::empty_item_counter this function always returns 0.
421 The function is not suitable for checking the set emptiness, use \ref empty
422 member function for this purpose.
426 return base_class::size();
429 /// Returns maximum height of skip-list. The max height is a constant for each object and does not exceed 32.
430 static CDS_CONSTEXPR unsigned int max_height() CDS_NOEXCEPT
432 return base_class::max_height();
435 /// Returns const reference to internal statistics
436 stat const& statistics() const
438 return base_class::statistics();
444 #endif // ifndef CDSLIB_CONTAINER_SKIP_LIST_SET_NOGC_H