3 #ifndef CDSLIB_CONTAINER_SPLIT_LIST_SET_NOGC_H
4 #define CDSLIB_CONTAINER_SPLIT_LIST_SET_NOGC_H
6 #include <cds/intrusive/split_list_nogc.h>
7 #include <cds/container/details/split_list_base.h>
8 #include <cds/gc/nogc.h>
9 #include <cds/container/details/make_split_list_set.h>
11 namespace cds { namespace container {
13 /// Split-ordered list set (template specialization for \p gc::nogc)
14 /** @ingroup cds_nonintrusive_set
15 \anchor cds_nonintrusive_SplitListSet_nogc
17 This specialization is so-called append-only container when no item
18 reclamation may be performed. The class does not support deleting of list item.
20 See \ref cds_nonintrusive_SplitListSet_hp "SplitListSet" for description of template parameters.
22 @warning Many member functions return an iterator pointing to an item.
23 The iterator can be used to set up field of the item,
24 but you should provide an exclusive access to it,
25 see \ref cds_intrusive_item_creating "insert item troubleshooting".
29 #ifdef CDS_DOXYGEN_INVOKED
30 class Traits = split_list::traits
35 class SplitListSet< cds::gc::nogc, T, Traits>
36 #ifdef CDS_DOXYGEN_INVOKED
37 :protected intrusive::SplitListSet<cds::gc::nogc, typename Traits::ordered_list, Traits>
39 :protected details::make_split_list_set< cds::gc::nogc, T, typename Traits::ordered_list, split_list::details::wrap_set_traits<T, Traits> >::type
44 typedef details::make_split_list_set< cds::gc::nogc, T, typename Traits::ordered_list, split_list::details::wrap_set_traits<T, Traits> > maker;
45 typedef typename maker::type base_class;
49 typedef cds::gc::nogc gc; ///< Garbage collector
50 typedef T value_type; ///< type of value to be stored in the list
51 typedef Traits traits; ///< List traits
53 typedef typename maker::ordered_list ordered_list; ///< Underlying ordered list class
54 typedef typename base_class::key_comparator key_comparator; ///< key comparison functor
56 /// Hash functor for \ref value_type and all its derivatives that you use
57 typedef typename base_class::hash hash;
58 typedef typename base_class::item_counter item_counter; ///< Item counter type
59 typedef typename base_class::stat stat; ///< Internal statistics
62 typedef cds::container::split_list::implementation_tag implementation_tag;
67 typedef typename maker::cxx_node_allocator cxx_node_allocator;
68 typedef typename maker::node_type node_type;
71 static node_type * alloc_node(Q const& v )
73 return cxx_node_allocator().New( v );
76 template <typename... Args>
77 static node_type * alloc_node( Args&&... args )
79 return cxx_node_allocator().MoveNew( std::forward<Args>(args)...);
82 static void free_node( node_type * pNode )
84 cxx_node_allocator().Delete( pNode );
87 struct node_disposer {
88 void operator()( node_type * pNode )
93 typedef std::unique_ptr< node_type, node_disposer > scoped_node_ptr;
97 /// Initialize split-ordered list of default capacity
99 The default capacity is defined in bucket table constructor.
100 See \p intrusive::split_list::expandable_bucket_table, \p intrusive::split_list::static_bucket_table
101 which selects by \p split_list::dynamic_bucket_table option.
107 /// Initialize split-ordered list
109 size_t nItemCount ///< estimated average of item count
110 , size_t nLoadFactor = 1 ///< load factor - average item count per bucket. Small integer up to 10, default is 1.
112 : base_class( nItemCount, nLoadFactor )
118 \p IsConst - constness boolean flag
120 The forward iterator has the following features:
121 - it has no post-increment operator
122 - it depends on underlying ordered list iterator
124 template <bool IsConst>
125 class iterator_type: protected base_class::template iterator_type<IsConst>
128 typedef typename base_class::template iterator_type<IsConst> iterator_base_class;
129 friend class SplitListSet;
132 /// Value pointer type (const for const iterator)
133 typedef typename cds::details::make_const_type<value_type, IsConst>::pointer value_ptr;
134 /// Value reference type (const for const iterator)
135 typedef typename cds::details::make_const_type<value_type, IsConst>::reference value_ref;
143 iterator_type( iterator_type const& src )
144 : iterator_base_class( src )
149 explicit iterator_type( iterator_base_class const& src )
150 : iterator_base_class( src )
155 /// Dereference operator
156 value_ptr operator ->() const
158 return &(iterator_base_class::operator->()->m_Value);
161 /// Dereference operator
162 value_ref operator *() const
164 return iterator_base_class::operator*().m_Value;
168 iterator_type& operator ++()
170 iterator_base_class::operator++();
174 /// Assignment operator
175 iterator_type& operator = (iterator_type const& src)
177 iterator_base_class::operator=(src);
181 /// Equality operator
183 bool operator ==(iterator_type<C> const& i ) const
185 return iterator_base_class::operator==(i);
188 /// Equality operator
190 bool operator !=(iterator_type<C> const& i ) const
192 return iterator_base_class::operator!=(i);
198 typedef iterator_type<false> iterator;
200 /// Const forward iterator
201 typedef iterator_type<true> const_iterator;
203 /// Returns a forward iterator addressing the first element in a set
205 For empty set \code begin() == end() \endcode
209 return iterator( base_class::begin() );
212 /// Returns an iterator that addresses the location succeeding the last element in a set
214 Do not use the value returned by <tt>end</tt> function to access any item.
215 The returned value can be used only to control reaching the end of the set.
216 For empty set \code begin() == end() \endcode
220 return iterator( base_class::end() );
223 /// Returns a forward const iterator addressing the first element in a set
224 const_iterator begin() const
228 /// Returns a forward const iterator addressing the first element in a set
229 const_iterator cbegin() const
231 return const_iterator( base_class::cbegin() );
234 /// Returns an const iterator that addresses the location succeeding the last element in a set
235 const_iterator end() const
239 /// Returns an const iterator that addresses the location succeeding the last element in a set
240 const_iterator cend() const
242 return const_iterator( base_class::cend() );
247 iterator insert_node( node_type * pNode )
249 assert( pNode != nullptr );
250 scoped_node_ptr p(pNode);
252 iterator it( base_class::insert_( *pNode ));
265 The function inserts \p val in the set if it does not contain
266 an item with key equal to \p val.
267 The \p value_type should be constructible from a value of type \p Q.
269 Return an iterator pointing to inserted item if success \p end() otherwise
271 template <typename Q>
272 iterator insert( const Q& val )
274 return insert_node( alloc_node( val ) );
277 /// Inserts data of type \p value_type created from \p args
279 Return an iterator pointing to inserted item if success \p end() otherwise
281 template <typename... Args>
282 iterator emplace( Args&&... args )
284 return insert_node( alloc_node( std::forward<Args>(args)... ) );
289 If \p key is not in the set and \p bAllowInsert is \p true, the function inserts a new item.
290 Otherwise, the function returns an iterator pointing to the item found.
292 Returns <tt> std::pair<iterator, bool> </tt> where \p first is an iterator pointing to
293 item found or inserted (if inserting is not allowed and \p key is not found, the iterator will be \p end()),
294 \p second is true if new item has been added or \p false if the item
295 already is in the set.
297 @warning If the set is based on \ref cds_nonintrusive_MichaelList_nogc "MichaelList",
298 see \ref cds_intrusive_item_creating "insert item troubleshooting".
299 \ref cds_nonintrusive_LazyList_nogc "LazyList" as the base provides exclusive access to inserted item
300 and does not require any node-level synchronization.
302 template <typename Q>
303 std::pair<iterator, bool> update( Q const& key, bool bAllowInsert = true )
305 scoped_node_ptr pNode( alloc_node( key ));
307 std::pair<typename base_class::iterator, bool> ret = base_class::update_( *pNode,
308 [](bool /*bNew*/, node_type& /*item*/, node_type& /*val*/){},
310 if ( ret.first != base_class::end() && ret.second ) {
312 return std::make_pair( iterator(ret.first), ret.second );
315 return std::make_pair( iterator(ret.first), ret.second );
318 // Deprecated, use update()
319 template <typename Q>
320 std::pair<iterator, bool> ensure( const Q& val )
322 return update( val, true );
326 /// Checks whether the set contains \p key
328 The function searches the item with key equal to \p key
329 and returns an iterator pointed to item found and \ref end() otherwise
331 template <typename Q>
332 iterator contains( Q const& key )
334 return iterator( base_class::find_( key ));
337 // Deprecated, use contains()
338 template <typename Q>
339 iterator find( Q const& key )
341 return contains( key );
345 /// Checks whether the set contains \p key using \p pred predicate for searching
347 The function is an analog of <tt>contains( key )</tt> but \p pred is used for key comparing.
348 \p Less functor has the interface like \p std::less.
349 \p pred must imply the same element order as the comparator used for building the set.
351 template <typename Q, typename Less>
352 iterator contains( Q const& key, Less pred )
355 return iterator( base_class::find_with_( key, typename maker::template predicate_wrapper<Less>::type() ));
358 // eprecated, use contains()
359 template <typename Q, typename Less>
360 iterator find_with( Q const& key, Less pred )
362 return contains( key, pred );
366 /// Checks if the set is empty
368 Emptiness is checked by item counting: if item count is zero then the set is empty.
369 Thus, the correct item counting feature is an important part of split-list set implementation.
373 return base_class::empty();
376 /// Returns item count in the set
379 return base_class::size();
382 /// Returns internal statistics
383 stat const& statistics() const
385 return base_class::statistics();
389 }} // namespace cds::container
391 #endif // #ifndef CDSLIB_CONTAINER_SPLIT_LIST_SET_NOGC_H