3 #ifndef __CDS_CONTAINER_SPLIT_LIST_SET_NOGC_H
4 #define __CDS_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
63 typedef typename maker::cxx_node_allocator cxx_node_allocator;
64 typedef typename maker::node_type node_type;
67 static node_type * alloc_node(Q const& v )
69 return cxx_node_allocator().New( v );
72 template <typename... Args>
73 static node_type * alloc_node( Args&&... args )
75 return cxx_node_allocator().MoveNew( std::forward<Args>(args)...);
78 static void free_node( node_type * pNode )
80 cxx_node_allocator().Delete( pNode );
83 struct node_disposer {
84 void operator()( node_type * pNode )
89 typedef std::unique_ptr< node_type, node_disposer > scoped_node_ptr;
93 /// Initialize split-ordered list of default capacity
95 The default capacity is defined in bucket table constructor.
96 See \p intrusive::split_list::expandable_bucket_table, \p intrusive::split_list::static_bucket_table
97 which selects by \p split_list::dynamic_bucket_table option.
103 /// Initialize split-ordered list
105 size_t nItemCount ///< estimated average of item count
106 , size_t nLoadFactor = 1 ///< load factor - average item count per bucket. Small integer up to 10, default is 1.
108 : base_class( nItemCount, nLoadFactor )
114 \p IsConst - constness boolean flag
116 The forward iterator has the following features:
117 - it has no post-increment operator
118 - it depends on underlying ordered list iterator
120 template <bool IsConst>
121 class iterator_type: protected base_class::template iterator_type<IsConst>
124 typedef typename base_class::template iterator_type<IsConst> iterator_base_class;
125 friend class SplitListSet;
128 /// Value pointer type (const for const iterator)
129 typedef typename cds::details::make_const_type<value_type, IsConst>::pointer value_ptr;
130 /// Value reference type (const for const iterator)
131 typedef typename cds::details::make_const_type<value_type, IsConst>::reference value_ref;
139 iterator_type( iterator_type const& src )
140 : iterator_base_class( src )
145 explicit iterator_type( iterator_base_class const& src )
146 : iterator_base_class( src )
151 /// Dereference operator
152 value_ptr operator ->() const
154 return &(iterator_base_class::operator->()->m_Value);
157 /// Dereference operator
158 value_ref operator *() const
160 return iterator_base_class::operator*().m_Value;
164 iterator_type& operator ++()
166 iterator_base_class::operator++();
170 /// Assignment operator
171 iterator_type& operator = (iterator_type const& src)
173 iterator_base_class::operator=(src);
177 /// Equality operator
179 bool operator ==(iterator_type<C> const& i ) const
181 return iterator_base_class::operator==(i);
184 /// Equality operator
186 bool operator !=(iterator_type<C> const& i ) const
188 return iterator_base_class::operator!=(i);
194 typedef iterator_type<false> iterator;
196 /// Const forward iterator
197 typedef iterator_type<true> const_iterator;
199 /// Returns a forward iterator addressing the first element in a set
201 For empty set \code begin() == end() \endcode
205 return iterator( base_class::begin() );
208 /// Returns an iterator that addresses the location succeeding the last element in a set
210 Do not use the value returned by <tt>end</tt> function to access any item.
211 The returned value can be used only to control reaching the end of the set.
212 For empty set \code begin() == end() \endcode
216 return iterator( base_class::end() );
219 /// Returns a forward const iterator addressing the first element in a set
220 const_iterator begin() const
224 /// Returns a forward const iterator addressing the first element in a set
225 const_iterator cbegin() const
227 return const_iterator( base_class::cbegin() );
230 /// Returns an const iterator that addresses the location succeeding the last element in a set
231 const_iterator end() const
235 /// Returns an const iterator that addresses the location succeeding the last element in a set
236 const_iterator cend() const
238 return const_iterator( base_class::cend() );
243 iterator insert_node( node_type * pNode )
245 assert( pNode != nullptr );
246 scoped_node_ptr p(pNode);
248 iterator it( base_class::insert_( *pNode ));
261 The function inserts \p val in the set if it does not contain
262 an item with key equal to \p val.
263 The \p value_type should be constructible from a value of type \p Q.
265 Return an iterator pointing to inserted item if success \p end() otherwise
267 template <typename Q>
268 iterator insert( const Q& val )
270 return insert_node( alloc_node( val ) );
273 /// Inserts data of type \p value_type created from \p args
275 Return an iterator pointing to inserted item if success \p end() otherwise
277 template <typename... Args>
278 iterator emplace( Args&&... args )
280 return insert_node( alloc_node( std::forward<Args>(args)... ) );
283 /// Ensures that the item \p val exists in the set
285 The operation inserts new item created from \p val if the key \p val is not found in the set.
286 Otherwise, the function returns an iterator that points to item found.
287 The \p value_type should be constructible from a value of type \p Q.
289 Returns <tt> std::pair<iterator, bool> </tt> where \p first is an iterator pointing to
290 item found or inserted, \p second is true if new item has been added or \p false if the item
291 already is in the set.
293 template <typename Q>
294 std::pair<iterator, bool> ensure( const Q& val )
296 scoped_node_ptr pNode( alloc_node( val ));
298 std::pair<typename base_class::iterator, bool> ret = base_class::ensure_( *pNode, [](bool /*bNew*/, node_type& /*item*/, node_type& /*val*/){} );
299 if ( ret.first != base_class::end() && ret.second ) {
301 return std::make_pair( iterator(ret.first), ret.second );
304 return std::make_pair( iterator(ret.first), ret.second );
307 /// Find the key \p key
308 /** \anchor cds_nonintrusive_SplitListSet_nogc_find
310 The function searches the item with key equal to \p key
311 and returns an iterator pointed to item found if the key is found,
312 and \ref end() otherwise.
314 template <typename Q>
315 iterator find( Q const& key )
317 return iterator( base_class::find_( key ));
320 /// Finds the key \p key using \p pred predicate for searching
322 The function is an analog of \ref cds_nonintrusive_SplitListSet_nogc_find "find(Q const&)"
323 but \p pred is used for key comparing.
324 \p Less functor has the interface like \p std::less.
325 \p Less must imply the same element order as the comparator used for building the set.
327 template <typename Q, typename Less>
328 iterator find_with( Q const& key, Less pred )
331 return iterator( base_class::find_with_( key, typename maker::template predicate_wrapper<Less>::type() ));
334 /// Checks if the set is empty
336 Emptiness is checked by item counting: if item count is zero then the set is empty.
337 Thus, the correct item counting feature is an important part of split-list set implementation.
341 return base_class::empty();
344 /// Returns item count in the set
347 return base_class::size();
350 /// Returns internal statistics
351 stat const& statistics() const
353 return base_class::statistics();
357 }} // namespace cds::container
359 #endif // #ifndef __CDS_CONTAINER_SPLIT_LIST_SET_NOGC_H