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_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 )
142 \p IsConst - constness boolean flag
144 The forward iterator has the following features:
145 - it has no post-increment operator
146 - it depends on underlying ordered list iterator
148 template <bool IsConst>
149 class iterator_type: protected base_class::template iterator_type<IsConst>
152 typedef typename base_class::template iterator_type<IsConst> iterator_base_class;
153 friend class SplitListSet;
156 /// Value pointer type (const for const iterator)
157 typedef typename cds::details::make_const_type<value_type, IsConst>::pointer value_ptr;
158 /// Value reference type (const for const iterator)
159 typedef typename cds::details::make_const_type<value_type, IsConst>::reference value_ref;
167 iterator_type( iterator_type const& src )
168 : iterator_base_class( src )
173 explicit iterator_type( iterator_base_class const& src )
174 : iterator_base_class( src )
179 /// Dereference operator
180 value_ptr operator ->() const
182 return &(iterator_base_class::operator->()->m_Value);
185 /// Dereference operator
186 value_ref operator *() const
188 return iterator_base_class::operator*().m_Value;
192 iterator_type& operator ++()
194 iterator_base_class::operator++();
198 /// Assignment operator
199 iterator_type& operator = (iterator_type const& src)
201 iterator_base_class::operator=(src);
205 /// Equality operator
207 bool operator ==(iterator_type<C> const& i ) const
209 return iterator_base_class::operator==(i);
212 /// Equality operator
214 bool operator !=(iterator_type<C> const& i ) const
216 return iterator_base_class::operator!=(i);
222 typedef iterator_type<false> iterator;
224 /// Const forward iterator
225 typedef iterator_type<true> const_iterator;
227 /// Returns a forward iterator addressing the first element in a set
229 For empty set \code begin() == end() \endcode
233 return iterator( base_class::begin() );
236 /// Returns an iterator that addresses the location succeeding the last element in a set
238 Do not use the value returned by <tt>end</tt> function to access any item.
239 The returned value can be used only to control reaching the end of the set.
240 For empty set \code begin() == end() \endcode
244 return iterator( base_class::end() );
247 /// Returns a forward const iterator addressing the first element in a set
248 const_iterator begin() const
252 /// Returns a forward const iterator addressing the first element in a set
253 const_iterator cbegin() const
255 return const_iterator( base_class::cbegin() );
258 /// Returns an const iterator that addresses the location succeeding the last element in a set
259 const_iterator end() const
263 /// Returns an const iterator that addresses the location succeeding the last element in a set
264 const_iterator cend() const
266 return const_iterator( base_class::cend() );
271 iterator insert_node( node_type * pNode )
273 assert( pNode != nullptr );
274 scoped_node_ptr p(pNode);
276 iterator it( base_class::insert_( *pNode ));
289 The function inserts \p val in the set if it does not contain
290 an item with key equal to \p val.
291 The \p value_type should be constructible from a value of type \p Q.
293 Return an iterator pointing to inserted item if success \p end() otherwise
295 template <typename Q>
296 iterator insert( const Q& val )
298 return insert_node( alloc_node( val ) );
301 /// Inserts data of type \p value_type created from \p args
303 Return an iterator pointing to inserted item if success \p end() otherwise
305 template <typename... Args>
306 iterator emplace( Args&&... args )
308 return insert_node( alloc_node( std::forward<Args>(args)... ) );
313 If \p key is not in the set and \p bAllowInsert is \p true, the function inserts a new item.
314 Otherwise, the function returns an iterator pointing to the item found.
316 Returns <tt> std::pair<iterator, bool> </tt> where \p first is an iterator pointing to
317 item found or inserted (if inserting is not allowed and \p key is not found, the iterator will be \p end()),
319 \p second is true if new item has been added or \p false if the item
320 already is in the set.
322 @warning If the set is based on \ref cds_nonintrusive_MichaelList_nogc "MichaelList",
324 see \ref cds_intrusive_item_creating "insert item troubleshooting".
325 \ref cds_nonintrusive_LazyList_nogc "LazyList" as the base provides exclusive access to inserted item
327 and does not require any node-level synchronization.
329 template <typename Q>
330 std::pair<iterator, bool> update( Q const& key, bool bAllowInsert = true )
332 scoped_node_ptr pNode( alloc_node( key ));
334 std::pair<typename base_class::iterator, bool> ret = base_class::update_( *pNode,
336 [](bool /*bNew*/, node_type& /*item*/, node_type& /*val*/){},
338 if ( ret.first != base_class::end() && ret.second ) {
340 return std::make_pair( iterator(ret.first), ret.second );
343 return std::make_pair( iterator(ret.first), ret.second );
346 template <typename Q>
347 CDS_DEPRECATED("ensure() is deprecated, use update()")
348 std::pair<iterator, bool> ensure( const Q& val )
350 return update( val, true );
354 /// Checks whether the set contains \p key
356 The function searches the item with key equal to \p key
357 and returns an iterator pointed to item found and \ref end() otherwise
359 template <typename Q>
360 iterator contains( Q const& key )
362 return iterator( base_class::find_( key ));
365 template <typename Q>
366 CDS_DEPRECATED("deprecated, use contains()")
367 iterator find( Q const& key )
369 return contains( key );
373 /// Checks whether the set contains \p key using \p pred predicate for searching
375 The function is an analog of <tt>contains( key )</tt> but \p pred is used for key comparing.
376 \p Less functor has the interface like \p std::less.
377 \p pred must imply the same element order as the comparator used for building the set.
379 template <typename Q, typename Less>
380 iterator contains( Q const& key, Less pred )
383 return iterator( base_class::find_with_( key, typename maker::template predicate_wrapper<Less>::type() ));
386 // eprecated, use contains()
387 template <typename Q, typename Less>
388 iterator find_with( Q const& key, Less pred )
390 return contains( key, pred );
394 /// Clears the set (not atomic, for debugging purposes only)
400 /// Checks if the set is empty
402 Emptiness is checked by item counting: if item count is zero then the set is empty.
403 Thus, the correct item counting feature is an important part of split-list set implementation.
407 return base_class::empty();
410 /// Returns item count in the set
413 return base_class::size();
416 /// Returns internal statistics
417 stat const& statistics() const
419 return base_class::statistics();
423 }} // namespace cds::container
425 #endif // #ifndef CDSLIB_CONTAINER_SPLIT_LIST_SET_NOGC_H