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_SPLIT_LIST_SET_NOGC_H
32 #define CDSLIB_CONTAINER_SPLIT_LIST_SET_NOGC_H
34 #include <cds/intrusive/split_list_nogc.h>
35 #include <cds/container/details/split_list_base.h>
36 #include <cds/gc/nogc.h>
37 #include <cds/container/details/make_split_list_set.h>
39 namespace cds { namespace container {
41 /// Split-ordered list set (template specialization for \p gc::nogc)
42 /** @ingroup cds_nonintrusive_set
43 \anchor cds_nonintrusive_SplitListSet_nogc
45 This specialization is so-called append-only container when no item
46 reclamation may be performed. The class does not support deleting of list item.
48 See \ref cds_nonintrusive_SplitListSet_hp "SplitListSet" for description of template parameters.
50 @warning Many member functions return an iterator pointing to an item.
51 The iterator can be used to set up field of the item,
52 but you should provide an exclusive access to it,
53 see \ref cds_intrusive_item_creating "insert item troubleshooting".
57 #ifdef CDS_DOXYGEN_INVOKED
58 class Traits = split_list::traits
63 class SplitListSet< cds::gc::nogc, T, Traits>
64 #ifdef CDS_DOXYGEN_INVOKED
65 :protected intrusive::SplitListSet<cds::gc::nogc, typename Traits::ordered_list, Traits>
67 :protected details::make_split_list_set< cds::gc::nogc, T, typename Traits::ordered_list, split_list::details::wrap_set_traits<T, Traits> >::type
72 typedef details::make_split_list_set< cds::gc::nogc, T, typename Traits::ordered_list, split_list::details::wrap_set_traits<T, Traits> > maker;
73 typedef typename maker::type base_class;
77 typedef cds::gc::nogc gc; ///< Garbage collector
78 typedef T value_type; ///< type of value to be stored in the list
79 typedef Traits traits; ///< List traits
81 typedef typename maker::ordered_list ordered_list; ///< Underlying ordered list class
82 typedef typename base_class::key_comparator key_comparator; ///< key comparison functor
84 /// Hash functor for \ref value_type and all its derivatives that you use
85 typedef typename base_class::hash hash;
86 typedef typename base_class::item_counter item_counter; ///< Item counter type
87 typedef typename base_class::stat stat; ///< Internal statistics
91 typedef typename maker::cxx_node_allocator cxx_node_allocator;
92 typedef typename maker::node_type node_type;
95 static node_type * alloc_node(Q const& v )
97 return cxx_node_allocator().New( v );
100 template <typename... Args>
101 static node_type * alloc_node( Args&&... args )
103 return cxx_node_allocator().MoveNew( std::forward<Args>(args)...);
106 static void free_node( node_type * pNode )
108 cxx_node_allocator().Delete( pNode );
111 struct node_disposer {
112 void operator()( node_type * pNode )
117 typedef std::unique_ptr< node_type, node_disposer > scoped_node_ptr;
121 /// Initialize split-ordered list of default capacity
123 The default capacity is defined in bucket table constructor.
124 See \p intrusive::split_list::expandable_bucket_table, \p intrusive::split_list::static_bucket_table
125 which selects by \p split_list::dynamic_bucket_table option.
131 /// Initialize split-ordered list
133 size_t nItemCount ///< estimated average of item count
134 , size_t nLoadFactor = 1 ///< load factor - average item count per bucket. Small integer up to 10, default is 1.
136 : base_class( nItemCount, nLoadFactor )
141 template <bool IsConst>
142 class iterator_type: protected base_class::template iterator_type<IsConst>
144 typedef typename base_class::template iterator_type<IsConst> iterator_base_class;
145 friend class SplitListSet;
148 /// Value pointer type (const for const iterator)
149 typedef typename cds::details::make_const_type<value_type, IsConst>::pointer value_ptr;
150 /// Value reference type (const for const iterator)
151 typedef typename cds::details::make_const_type<value_type, IsConst>::reference value_ref;
159 iterator_type( iterator_type const& src )
160 : iterator_base_class( src )
164 explicit iterator_type( iterator_base_class const& src )
165 : iterator_base_class( src )
169 /// Dereference operator
170 value_ptr operator ->() const
172 return &(iterator_base_class::operator->()->m_Value);
175 /// Dereference operator
176 value_ref operator *() const
178 return iterator_base_class::operator*().m_Value;
182 iterator_type& operator ++()
184 iterator_base_class::operator++();
188 /// Assignment operator
189 iterator_type& operator = (iterator_type const& src)
191 iterator_base_class::operator=(src);
195 /// Equality operator
197 bool operator ==(iterator_type<C> const& i ) const
199 return iterator_base_class::operator==(i);
202 /// Equality operator
204 bool operator !=(iterator_type<C> const& i ) const
206 return iterator_base_class::operator!=(i);
212 ///@name Forward iterators
216 The forward iterator for split-list is based on \p OrderedList forward iterator and has some features:
217 - it has no post-increment operator
218 - it iterates items in unordered fashion
220 The iterator interface:
224 // Default constructor
228 iterator( iterator const& src );
230 // Dereference operator
231 value_type * operator ->() const;
233 // Dereference operator
234 value_type& operator *() const;
236 // Preincrement operator
237 iterator& operator ++();
239 // Assignment operator
240 iterator& operator = (iterator const& src);
242 // Equality operators
243 bool operator ==(iterator const& i ) const;
244 bool operator !=(iterator const& i ) const;
248 typedef iterator_type<false> iterator;
250 /// Const forward iterator
251 typedef iterator_type<true> const_iterator;
253 /// Returns a forward iterator addressing the first element in a set
255 For empty set \code begin() == end() \endcode
259 return iterator( base_class::begin());
262 /// Returns an iterator that addresses the location succeeding the last element in a set
264 Do not use the value returned by <tt>end</tt> function to access any item.
265 The returned value can be used only to control reaching the end of the set.
266 For empty set \code begin() == end() \endcode
270 return iterator( base_class::end());
273 /// Returns a forward const iterator addressing the first element in a set
274 const_iterator begin() const
278 /// Returns a forward const iterator addressing the first element in a set
279 const_iterator cbegin() const
281 return const_iterator( base_class::cbegin());
284 /// Returns an const iterator that addresses the location succeeding the last element in a set
285 const_iterator end() const
289 /// Returns an const iterator that addresses the location succeeding the last element in a set
290 const_iterator cend() const
292 return const_iterator( base_class::cend());
298 iterator insert_node( node_type * pNode )
300 assert( pNode != nullptr );
301 scoped_node_ptr p(pNode);
303 iterator it( base_class::insert_( *pNode ));
316 The function inserts \p val in the set if it does not contain
317 an item with key equal to \p val.
318 The \p value_type should be constructible from a value of type \p Q.
320 Return an iterator pointing to inserted item if success \p end() otherwise
322 template <typename Q>
323 iterator insert( const Q& val )
325 return insert_node( alloc_node( val ));
328 /// Inserts data of type \p value_type created from \p args
330 Return an iterator pointing to inserted item if success \p end() otherwise
332 template <typename... Args>
333 iterator emplace( Args&&... args )
335 return insert_node( alloc_node( std::forward<Args>(args)... ));
340 If \p key is not in the set and \p bAllowInsert is \p true, the function inserts a new item.
341 Otherwise, the function returns an iterator pointing to the item found.
343 Returns <tt> std::pair<iterator, bool> </tt> where \p first is an iterator pointing to
344 item found or inserted (if inserting is not allowed and \p key is not found, the iterator will be \p end()),
346 \p second is true if new item has been added or \p false if the item
347 already is in the set.
349 @warning If the set is based on \ref cds_nonintrusive_MichaelList_nogc "MichaelList",
351 see \ref cds_intrusive_item_creating "insert item troubleshooting".
352 \ref cds_nonintrusive_LazyList_nogc "LazyList" as the base provides exclusive access to inserted item
354 and does not require any node-level synchronization.
356 template <typename Q>
357 std::pair<iterator, bool> update( Q const& key, bool bAllowInsert = true )
359 scoped_node_ptr pNode( alloc_node( key ));
361 std::pair<typename base_class::iterator, bool> ret = base_class::update_( *pNode,
363 [](bool /*bNew*/, node_type& /*item*/, node_type& /*val*/){},
365 if ( ret.first != base_class::end() && ret.second ) {
367 return std::make_pair( iterator(ret.first), ret.second );
370 return std::make_pair( iterator(ret.first), ret.second );
373 template <typename Q>
374 CDS_DEPRECATED("ensure() is deprecated, use update()")
375 std::pair<iterator, bool> ensure( const Q& val )
377 return update( val, true );
381 /// Checks whether the set contains \p key
383 The function searches the item with key equal to \p key
384 and returns an iterator pointed to item found and \ref end() otherwise
386 template <typename Q>
387 iterator contains( Q const& key )
389 return iterator( base_class::find_( key ));
392 template <typename Q>
393 CDS_DEPRECATED("deprecated, use contains()")
394 iterator find( Q const& key )
396 return contains( key );
400 /// Checks whether the set contains \p key using \p pred predicate for searching
402 The function is an analog of <tt>contains( key )</tt> but \p pred is used for key comparing.
403 \p Less functor has the interface like \p std::less.
404 \p pred must imply the same element order as the comparator used for building the set.
406 template <typename Q, typename Less>
407 iterator contains( Q const& key, Less pred )
410 return iterator( base_class::find_with_( key, typename maker::template predicate_wrapper<Less>::type()));
413 // eprecated, use contains()
414 template <typename Q, typename Less>
415 iterator find_with( Q const& key, Less pred )
417 return contains( key, pred );
421 /// Clears the set (not atomic, for debugging purposes only)
427 /// Checks if the set is empty
429 Emptiness is checked by item counting: if item count is zero then the set is empty.
430 Thus, the correct item counting feature is an important part of split-list set implementation.
434 return base_class::empty();
437 /// Returns item count in the set
440 return base_class::size();
443 /// Returns internal statistics
444 stat const& statistics() const
446 return base_class::statistics();
449 /// Returns internal statistics for \p ordered_list
450 typename ordered_list::stat const& list_statistics() const
452 return base_class::list_statistics();
456 }} // namespace cds::container
458 #endif // #ifndef CDSLIB_CONTAINER_SPLIT_LIST_SET_NOGC_H