3 #ifndef __CDS_CONTAINER_STRIPED_SET_BOOST_STABLE_VECTOR_ADAPTER_H
4 #define __CDS_CONTAINER_STRIPED_SET_BOOST_STABLE_VECTOR_ADAPTER_H
6 #include <boost/version.hpp>
7 #if BOOST_VERSION < 104800
8 # error "For boost::container::stable_vector you must use boost 1.48 or above"
11 #include <cds/container/striped_set/adapter.h>
13 #include <boost/container/stable_vector.hpp>
14 #include <algorithm> // std::lower_bound
15 #include <utility> // std::pair
18 namespace cds { namespace container {
19 namespace striped_set {
21 // Copy policy for boost::container::stable_vector
22 template <typename T, typename Alloc>
23 struct copy_item_policy< boost::container::stable_vector< T, Alloc > >
25 typedef boost::container::stable_vector< T, Alloc > vector_type;
26 typedef typename vector_type::iterator iterator;
28 void operator()( vector_type& vec, iterator itInsert, iterator itWhat )
30 vec.insert( itInsert, *itWhat );
34 // Swap policy for boost::container::stable_vector
35 template <typename T, typename Alloc>
36 struct swap_item_policy< boost::container::stable_vector< T, Alloc > >
38 typedef boost::container::stable_vector< T, Alloc > vector_type;
39 typedef typename vector_type::iterator iterator;
41 void operator()( vector_type& vec, iterator itInsert, iterator itWhat )
43 typename vector_type::value_type newVal;
44 itInsert = vec.insert( itInsert, newVal );
45 std::swap( *itInsert, *itWhat );
49 #ifdef CDS_MOVE_SEMANTICS_SUPPORT
50 // Move policy for boost::container::stable_vector
51 template <typename T, typename Alloc>
52 struct move_item_policy< boost::container::stable_vector< T, Alloc > >
54 typedef boost::container::stable_vector< T, Alloc > vector_type;
55 typedef typename vector_type::iterator iterator;
57 void operator()( vector_type& vec, iterator itInsert, iterator itWhat )
59 vec.insert( itInsert, std::move( *itWhat ));
64 } // namespace striped_set
65 }} // namespace cds::container
67 namespace cds { namespace intrusive { namespace striped_set {
68 /// boost::container::stable_vector adapter for hash set bucket
69 template <typename T, class Alloc, CDS_SPEC_OPTIONS>
70 class adapt< boost::container::stable_vector<T, Alloc>, CDS_OPTIONS >
73 typedef boost::container::stable_vector<T, Alloc> container_type ; ///< underlying container type
76 /// Adapted container type
77 class adapted_container: public cds::container::striped_set::adapted_sequential_container
80 typedef typename container_type::value_type value_type ; ///< value type stored in the container
81 typedef typename container_type::iterator iterator ; ///< container iterator
82 typedef typename container_type::const_iterator const_iterator ; ///< container const iterator
84 static bool const has_find_with = true;
85 static bool const has_erase_with = true;
89 typedef typename cds::opt::details::make_comparator_from_option_list< value_type, CDS_OPTIONS >::type key_comparator;
91 typedef typename cds::opt::select<
92 typename cds::opt::value<
93 typename cds::opt::find_option<
94 cds::opt::copy_policy< cds::container::striped_set::move_item >
98 , cds::container::striped_set::copy_item, cds::container::striped_set::copy_item_policy<container_type>
99 , cds::container::striped_set::swap_item, cds::container::striped_set::swap_item_policy<container_type>
100 #ifdef CDS_MOVE_SEMANTICS_SUPPORT
101 , cds::container::striped_set::move_item, cds::container::striped_set::move_item_policy<container_type>
105 struct find_predicate
107 bool operator()( value_type const& i1, value_type const& i2) const
109 return key_comparator()( i1, i2 ) < 0;
112 template <typename Q>
113 bool operator()( Q const& i1, value_type const& i2) const
115 return key_comparator()( i1, i2 ) < 0;
118 template <typename Q>
119 bool operator()( value_type const& i1, Q const& i2) const
121 return key_comparator()( i1, i2 ) < 0;
128 container_type m_Vector;
133 /// Insert value \p val of type \p Q into the container
135 The function allows to split creating of new item into two part:
136 - create item with key only from \p val
137 - try to insert new item into the container
138 - if inserting is success, calls \p f functor to initialize value-field of the new item.
140 The functor signature is:
142 void func( value_type& item );
144 where \p item is the item inserted.
146 The type \p Q may differ from \ref value_type of items storing in the container.
147 Therefore, the \p value_type should be comparable with type \p Q and constructible from type \p Q,
149 The user-defined functor is called only if the inserting is success. It may be passed by reference
150 using <tt>boost::ref</tt>
152 template <typename Q, typename Func>
153 bool insert( const Q& val, Func f )
155 iterator it = std::lower_bound( m_Vector.begin(), m_Vector.end(), val, find_predicate() );
156 if ( it == m_Vector.end() || key_comparator()( val, *it ) != 0 ) {
157 value_type newItem( val );
158 it = m_Vector.insert( it, newItem );
159 cds::unref( f )( *it );
165 # ifdef CDS_EMPLACE_SUPPORT
166 template <typename... Args>
167 bool emplace( Args&&... args )
169 value_type val( std::forward<Args>(args)... );
170 iterator it = std::lower_bound( m_Vector.begin(), m_Vector.end(), val, find_predicate() );
171 if ( it == m_Vector.end() || key_comparator()( val, *it ) != 0 ) {
172 it = m_Vector.emplace( it, std::move( val ) );
179 /// Ensures that the \p item exists in the container
181 The operation performs inserting or changing data.
183 If the \p val key not found in the container, then the new item created from \p val
184 is inserted. Otherwise, the functor \p func is called with the item found.
185 The \p Func functor has interface:
187 void func( bool bNew, value_type& item, const Q& val );
192 void operator()( bool bNew, value_type& item, const Q& val );
197 - \p bNew - \p true if the item has been inserted, \p false otherwise
198 - \p item - container's item
199 - \p val - argument \p val passed into the \p ensure function
201 The functor may change non-key fields of the \p item.
203 The type \p Q may differ from \ref value_type of items storing in the container.
204 Therefore, the \p value_type should be comparable with type \p Q and constructible from type \p Q,
206 You may pass \p func argument by reference using <tt>boost::ref</tt>.
208 Returns <tt> std::pair<bool, bool> </tt> where \p first is true if operation is successfull,
209 \p second is true if new item has been added or \p false if the item with \p val key
212 template <typename Q, typename Func>
213 std::pair<bool, bool> ensure( const Q& val, Func func )
215 iterator it = std::lower_bound( m_Vector.begin(), m_Vector.end(), val, find_predicate() );
216 if ( it == m_Vector.end() || key_comparator()( val, *it ) != 0 ) {
218 value_type newItem( val );
219 it = m_Vector.insert( it, newItem );
220 cds::unref( func )( true, *it, val );
221 return std::make_pair( true, true );
225 cds::unref( func )( false, *it, val );
226 return std::make_pair( true, false );
232 The function searches an item with key \p key, calls \p f functor
233 and deletes the item. If \p key is not found, the functor is not called.
235 The functor \p Func interface is:
238 void operator()(value_type const& val);
241 The functor may be passed by reference using <tt>boost:ref</tt>
243 The type \p Q may differ from \ref value_type of items storing in the container.
244 Therefore, the \p value_type should be comparable with type \p Q.
246 Return \p true if key is found and deleted, \p false otherwise
248 template <typename Q, typename Func>
249 bool erase( const Q& key, Func f )
251 iterator it = std::lower_bound( m_Vector.begin(), m_Vector.end(), key, find_predicate() );
252 if ( it == m_Vector.end() || key_comparator()( key, *it ) != 0 )
256 cds::unref( f )( *it );
257 m_Vector.erase( it );
261 template <typename Q, typename Less, typename Func>
262 bool erase( const Q& key, Less pred, Func f )
264 iterator it = std::lower_bound( m_Vector.begin(), m_Vector.end(), key, pred );
265 if ( it == m_Vector.end() || pred( key, *it ) || pred( *it, key ) )
269 cds::unref( f )( *it );
270 m_Vector.erase( it );
274 /// Find the key \p val
276 The function searches the item with key equal to \p val and calls the functor \p f for item found.
277 The interface of \p Func functor is:
280 void operator()( value_type& item, Q& val );
283 where \p item is the item found, \p val is the <tt>find</tt> function argument.
285 You may pass \p f argument by reference using <tt>boost::ref</tt> or cds::ref.
287 The functor may change non-key fields of \p item.
288 The \p val argument is non-const since it can be used as \p f functor destination i.e., the functor
289 may modify both arguments.
291 The type \p Q may differ from \ref value_type of items storing in the container.
292 Therefore, the \p value_type should be comparable with type \p Q.
294 The function returns \p true if \p val is found, \p false otherwise.
296 template <typename Q, typename Func>
297 bool find( Q& val, Func f )
299 iterator it = std::lower_bound( m_Vector.begin(), m_Vector.end(), val, find_predicate() );
300 if ( it == m_Vector.end() || key_comparator()( val, *it ) != 0 )
304 cds::unref( f )( *it, val );
308 template <typename Q, typename Less, typename Func>
309 bool find( Q& val, Less pred, Func f )
311 iterator it = std::lower_bound( m_Vector.begin(), m_Vector.end(), val, pred );
312 if ( it == m_Vector.end() || pred( val, *it ) || pred( *it, val ) )
316 cds::unref( f )( *it, val );
320 /// Clears the container
326 iterator begin() { return m_Vector.begin(); }
327 const_iterator begin() const { return m_Vector.begin(); }
328 iterator end() { return m_Vector.end(); }
329 const_iterator end() const { return m_Vector.end(); }
331 void move_item( adapted_container& /*from*/, iterator itWhat )
333 iterator it = std::lower_bound( m_Vector.begin(), m_Vector.end(), *itWhat, find_predicate() );
334 assert( it == m_Vector.end() || key_comparator()( *itWhat, *it ) != 0 );
336 copy_item()( m_Vector, it, itWhat );
341 return m_Vector.size();
346 typedef adapted_container type ; ///< Result of \p adapt metafunction
349 }}} // namespace cds::intrusive::striped_set
354 #endif // #ifndef __CDS_CONTAINER_STRIPED_SET_BOOST_STABLE_VECTOR_ADAPTER_H