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/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 # ifdef CDS_EMPLACE_SUPPORT
67 template <typename... Args>
68 static node_type * alloc_node( Args&&... args )
70 return cxx_node_allocator().MoveNew( std::forward<Args>(args)...);
74 static void free_node( node_type * pNode )
76 cxx_node_allocator().Delete( pNode );
79 struct node_disposer {
80 void operator()( node_type * pNode )
85 typedef std::unique_ptr< node_type, node_disposer > scoped_node_ptr;
91 # ifndef CDS_CXX11_LAMBDA_SUPPORT
92 struct empty_ensure_functor
94 void operator()( bool /*bNew*/, node_type& /*item*/, node_type& /*val*/ )
102 /// Initialize split-ordered list of default capacity
104 The default capacity is defined in bucket table constructor.
105 See intrusive::split_list::expandable_bucket_table, intrusive::split_list::static_ducket_table
106 which selects by intrusive::split_list::dynamic_bucket_table option.
112 /// Initialize split-ordered list
114 size_t nItemCount ///< estimate average of item count
115 , size_t nLoadFactor = 1 ///< load factor - average item count per bucket. Small integer up to 10, default is 1.
117 : base_class( nItemCount, nLoadFactor )
123 \p IsConst - constness boolean flag
125 The forward iterator has the following features:
126 - it has no post-increment operator
127 - it depends on underlying ordered list iterator
129 template <bool IsConst>
130 class iterator_type: protected base_class::template iterator_type<IsConst>
133 typedef typename base_class::template iterator_type<IsConst> iterator_base_class;
134 friend class SplitListSet;
137 /// Value pointer type (const for const iterator)
138 typedef typename cds::details::make_const_type<value_type, IsConst>::pointer value_ptr;
139 /// Value reference type (const for const iterator)
140 typedef typename cds::details::make_const_type<value_type, IsConst>::reference value_ref;
148 iterator_type( iterator_type const& src )
149 : iterator_base_class( src )
154 explicit iterator_type( iterator_base_class const& src )
155 : iterator_base_class( src )
160 /// Dereference operator
161 value_ptr operator ->() const
163 return &(iterator_base_class::operator->()->m_Value);
166 /// Dereference operator
167 value_ref operator *() const
169 return iterator_base_class::operator*().m_Value;
173 iterator_type& operator ++()
175 iterator_base_class::operator++();
179 /// Assignment operator
180 iterator_type& operator = (iterator_type const& src)
182 iterator_base_class::operator=(src);
186 /// Equality operator
188 bool operator ==(iterator_type<C> const& i ) const
190 return iterator_base_class::operator==(i);
193 /// Equality operator
195 bool operator !=(iterator_type<C> const& i ) const
197 return iterator_base_class::operator!=(i);
203 typedef iterator_type<false> iterator;
205 /// Const forward iterator
206 typedef iterator_type<true> const_iterator;
208 /// Returns a forward iterator addressing the first element in a set
210 For empty set \code begin() == end() \endcode
214 return iterator( base_class::begin() );
217 /// Returns an iterator that addresses the location succeeding the last element in a set
219 Do not use the value returned by <tt>end</tt> function to access any item.
220 The returned value can be used only to control reaching the end of the set.
221 For empty set \code begin() == end() \endcode
225 return iterator( base_class::end() );
228 /// Returns a forward const iterator addressing the first element in a set
229 const_iterator begin() const
231 return const_iterator( base_class::begin() );
234 /// Returns an const iterator that addresses the location succeeding the last element in a set
235 const_iterator end() const
237 return const_iterator( base_class::end() );
242 iterator insert_node( node_type * pNode )
244 assert( pNode != nullptr );
245 scoped_node_ptr p(pNode);
247 iterator it( base_class::insert_( *pNode ));
260 The function inserts \p val in the set if it does not contain
261 an item with key equal to \p val.
262 The \ref value_type should be constructible from a value of type \p Q.
264 Return an iterator pointing to inserted item if success \ref end() otherwise
266 template <typename Q>
267 iterator insert( const Q& val )
269 return insert_node( alloc_node( val ) );
272 #ifdef CDS_EMPLACE_SUPPORT
273 /// Inserts data of type \ref value_type constructed with <tt>std::forward<Args>(args)...</tt>
275 Return an iterator pointing to inserted item if success \ref end() otherwise
277 This function is available only for compiler that supports
278 variadic template and move semantics
280 template <typename... Args>
281 iterator emplace( Args&&... args )
283 return insert_node( alloc_node( std::forward<Args>(args)... ) );
287 /// Ensures that the item \p val exists in the set
289 The operation inserts new item created from \p val if the key \p val is not found in the set.
290 Otherwise, the function returns an iterator that points to item found.
291 The \p value_type should be constructible from a value of type \p Q.
293 Returns <tt> std::pair<iterator, bool> </tt> where \p first is an iterator pointing to
294 item found or inserted, \p second is true if new item has been added or \p false if the item
295 already is in the set.
297 template <typename Q>
298 std::pair<iterator, bool> ensure( const Q& val )
300 scoped_node_ptr pNode( alloc_node( val ));
302 # ifdef CDS_CXX11_LAMBDA_SUPPORT
303 std::pair<typename base_class::iterator, bool> ret = base_class::ensure_( *pNode, [](bool /*bNew*/, node_type& /*item*/, node_type& /*val*/){} );
305 std::pair<typename base_class::iterator, bool> ret = base_class::ensure_( *pNode, empty_ensure_functor() );
307 if ( ret.first != base_class::end() && ret.second ) {
309 return std::make_pair( iterator(ret.first), ret.second );
312 return std::make_pair( iterator(ret.first), ret.second );
315 /// Find the key \p val
316 /** \anchor cds_nonintrusive_SplitListSet_nogc_find
318 The function searches the item with key equal to \p key
319 and returns an iterator pointed to item found if the key is found,
320 and \ref end() otherwise
322 template <typename Q>
323 iterator find( Q const& key )
325 return iterator( base_class::find_( key ));
328 /// Finds the key \p val using \p pred predicate for searching
330 The function is an analog of \ref cds_nonintrusive_SplitListSet_nogc_find "find(Q const&)"
331 but \p pred is used for key comparing.
332 \p Less functor has the interface like \p std::less.
333 \p Less must imply the same element order as the comparator used for building the set.
335 template <typename Q, typename Less>
336 iterator find_with( Q const& key, Less pred )
338 return iterator( base_class::find_with_( key, typename options::template predicate_wrapper<Less>::type() ));
341 /// Checks if the set is empty
343 Emptiness is checked by item counting: if item count is zero then the set is empty.
344 Thus, the correct item counting feature is an important part of split-list set implementation.
348 return base_class::empty();
351 /// Returns item count in the set
354 return base_class::size();
358 }} // namespace cds::container
360 #endif // #ifndef __CDS_CONTAINER_SPLIT_LIST_SET_NOGC_H