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 gc::nogc)
14 /** @ingroup cds_nonintrusive_set
15 \anchor cds_nonintrusive_SplitListSet_nogc
17 This specialization is intended for so-called persistent usage 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 The interface of the specialization is a slightly different.
26 #ifdef CDS_DOXYGEN_INVOKED
27 class Traits = split_list::type_traits
32 class SplitListSet< cds::gc::nogc, T, Traits>
33 #ifdef CDS_DOXYGEN_INVOKED
34 :protected intrusive::SplitListSet<cds::gc::nogc, typename Traits::ordered_list, Traits>
36 :protected details::make_split_list_set< cds::gc::nogc, T, typename Traits::ordered_list, split_list::details::wrap_set_traits<T, Traits> >::type
41 typedef details::make_split_list_set< cds::gc::nogc, T, typename Traits::ordered_list, split_list::details::wrap_set_traits<T, Traits> > options;
42 typedef typename options::type base_class;
46 typedef typename options::gc gc ; ///< Garbage collector
47 typedef typename options::value_type value_type ; ///< type of value stored in the list
48 typedef typename options::ordered_list ordered_list ; ///< Underlying ordered list class
49 typedef typename base_class::key_comparator key_comparator ; ///< key comparison functor
51 /// Hash functor for \ref value_type and all its derivatives that you use
52 typedef typename base_class::hash hash;
53 typedef typename base_class::item_counter item_counter ; ///< Item counter type
57 typedef typename options::cxx_node_allocator cxx_node_allocator;
58 typedef typename options::node_type node_type;
61 static node_type * alloc_node(Q const& v )
63 return cxx_node_allocator().New( v );
66 template <typename... Args>
67 static node_type * alloc_node( Args&&... args )
69 return cxx_node_allocator().MoveNew( std::forward<Args>(args)...);
72 static void free_node( node_type * pNode )
74 cxx_node_allocator().Delete( pNode );
77 struct node_disposer {
78 void operator()( node_type * pNode )
83 typedef std::unique_ptr< node_type, node_disposer > scoped_node_ptr;
87 /// Initialize split-ordered list of default capacity
89 The default capacity is defined in bucket table constructor.
90 See intrusive::split_list::expandable_bucket_table, intrusive::split_list::static_ducket_table
91 which selects by intrusive::split_list::dynamic_bucket_table option.
97 /// Initialize split-ordered list
99 size_t nItemCount ///< estimate average of item count
100 , size_t nLoadFactor = 1 ///< load factor - average item count per bucket. Small integer up to 10, default is 1.
102 : base_class( nItemCount, nLoadFactor )
108 \p IsConst - constness boolean flag
110 The forward iterator has the following features:
111 - it has no post-increment operator
112 - it depends on underlying ordered list iterator
114 template <bool IsConst>
115 class iterator_type: protected base_class::template iterator_type<IsConst>
118 typedef typename base_class::template iterator_type<IsConst> iterator_base_class;
119 friend class SplitListSet;
122 /// Value pointer type (const for const iterator)
123 typedef typename cds::details::make_const_type<value_type, IsConst>::pointer value_ptr;
124 /// Value reference type (const for const iterator)
125 typedef typename cds::details::make_const_type<value_type, IsConst>::reference value_ref;
133 iterator_type( iterator_type const& src )
134 : iterator_base_class( src )
139 explicit iterator_type( iterator_base_class const& src )
140 : iterator_base_class( src )
145 /// Dereference operator
146 value_ptr operator ->() const
148 return &(iterator_base_class::operator->()->m_Value);
151 /// Dereference operator
152 value_ref operator *() const
154 return iterator_base_class::operator*().m_Value;
158 iterator_type& operator ++()
160 iterator_base_class::operator++();
164 /// Assignment operator
165 iterator_type& operator = (iterator_type const& src)
167 iterator_base_class::operator=(src);
171 /// Equality operator
173 bool operator ==(iterator_type<C> const& i ) const
175 return iterator_base_class::operator==(i);
178 /// Equality operator
180 bool operator !=(iterator_type<C> const& i ) const
182 return iterator_base_class::operator!=(i);
188 typedef iterator_type<false> iterator;
190 /// Const forward iterator
191 typedef iterator_type<true> const_iterator;
193 /// Returns a forward iterator addressing the first element in a set
195 For empty set \code begin() == end() \endcode
199 return iterator( base_class::begin() );
202 /// Returns an iterator that addresses the location succeeding the last element in a set
204 Do not use the value returned by <tt>end</tt> function to access any item.
205 The returned value can be used only to control reaching the end of the set.
206 For empty set \code begin() == end() \endcode
210 return iterator( base_class::end() );
213 /// Returns a forward const iterator addressing the first element in a set
214 const_iterator begin() const
216 return const_iterator( base_class::begin() );
219 /// Returns an const iterator that addresses the location succeeding the last element in a set
220 const_iterator end() const
222 return const_iterator( base_class::end() );
227 iterator insert_node( node_type * pNode )
229 assert( pNode != nullptr );
230 scoped_node_ptr p(pNode);
232 iterator it( base_class::insert_( *pNode ));
245 The function inserts \p val in the set if it does not contain
246 an item with key equal to \p val.
247 The \ref value_type should be constructible from a value of type \p Q.
249 Return an iterator pointing to inserted item if success \ref end() otherwise
251 template <typename Q>
252 iterator insert( const Q& val )
254 return insert_node( alloc_node( val ) );
257 /// Inserts data of type \ref value_type constructed with <tt>std::forward<Args>(args)...</tt>
259 Return an iterator pointing to inserted item if success \ref end() otherwise
261 template <typename... Args>
262 iterator emplace( Args&&... args )
264 return insert_node( alloc_node( std::forward<Args>(args)... ) );
267 /// Ensures that the item \p val exists in the set
269 The operation inserts new item created from \p val if the key \p val is not found in the set.
270 Otherwise, the function returns an iterator that points to item found.
271 The \p value_type should be constructible from a value of type \p Q.
273 Returns <tt> std::pair<iterator, bool> </tt> where \p first is an iterator pointing to
274 item found or inserted, \p second is true if new item has been added or \p false if the item
275 already is in the set.
277 template <typename Q>
278 std::pair<iterator, bool> ensure( const Q& val )
280 scoped_node_ptr pNode( alloc_node( val ));
282 std::pair<typename base_class::iterator, bool> ret = base_class::ensure_( *pNode, [](bool /*bNew*/, node_type& /*item*/, node_type& /*val*/){} );
283 if ( ret.first != base_class::end() && ret.second ) {
285 return std::make_pair( iterator(ret.first), ret.second );
288 return std::make_pair( iterator(ret.first), ret.second );
291 /// Find the key \p val
292 /** \anchor cds_nonintrusive_SplitListSet_nogc_find
294 The function searches the item with key equal to \p key
295 and returns an iterator pointed to item found if the key is found,
296 and \ref end() otherwise
298 template <typename Q>
299 iterator find( Q const& key )
301 return iterator( base_class::find_( key ));
304 /// Finds the key \p val using \p pred predicate for searching
306 The function is an analog of \ref cds_nonintrusive_SplitListSet_nogc_find "find(Q const&)"
307 but \p pred is used for key comparing.
308 \p Less functor has the interface like \p std::less.
309 \p Less must imply the same element order as the comparator used for building the set.
311 template <typename Q, typename Less>
312 iterator find_with( Q const& key, Less pred )
314 return iterator( base_class::find_with_( key, typename options::template predicate_wrapper<Less>::type() ));
317 /// Checks if the set is empty
319 Emptiness is checked by item counting: if item count is zero then the set is empty.
320 Thus, the correct item counting feature is an important part of split-list set implementation.
324 return base_class::empty();
327 /// Returns item count in the set
330 return base_class::size();
334 }} // namespace cds::container
336 #endif // #ifndef __CDS_CONTAINER_SPLIT_LIST_SET_NOGC_H