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 <functional> // ref
12 #include <algorithm> // std::lower_bound
13 #include <utility> // std::pair
14 #include <cds/container/striped_set/adapter.h>
15 #include <boost/container/stable_vector.hpp>
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 // Move policy for boost::container::stable_vector
50 template <typename T, typename Alloc>
51 struct move_item_policy< boost::container::stable_vector< T, Alloc > >
53 typedef boost::container::stable_vector< T, Alloc > vector_type;
54 typedef typename vector_type::iterator iterator;
56 void operator()( vector_type& vec, iterator itInsert, iterator itWhat )
58 vec.insert( itInsert, std::move( *itWhat ));
62 } // namespace striped_set
63 }} // namespace cds::container
65 namespace cds { namespace intrusive { namespace striped_set {
66 /// boost::container::stable_vector adapter for hash set bucket
67 template <typename T, class Alloc, typename... Options>
68 class adapt< boost::container::stable_vector<T, Alloc>, Options... >
71 typedef boost::container::stable_vector<T, Alloc> container_type ; ///< underlying container type
74 /// Adapted container type
75 class adapted_container: public cds::container::striped_set::adapted_sequential_container
78 typedef typename container_type::value_type value_type ; ///< value type stored in the container
79 typedef typename container_type::iterator iterator ; ///< container iterator
80 typedef typename container_type::const_iterator const_iterator ; ///< container const iterator
82 static bool const has_find_with = true;
83 static bool const has_erase_with = true;
87 typedef typename cds::opt::details::make_comparator_from_option_list< value_type, Options... >::type key_comparator;
89 typedef typename cds::opt::select<
90 typename cds::opt::value<
91 typename cds::opt::find_option<
92 cds::opt::copy_policy< cds::container::striped_set::move_item >
96 , cds::container::striped_set::copy_item, cds::container::striped_set::copy_item_policy<container_type>
97 , cds::container::striped_set::swap_item, cds::container::striped_set::swap_item_policy<container_type>
98 , cds::container::striped_set::move_item, cds::container::striped_set::move_item_policy<container_type>
101 struct find_predicate
103 bool operator()( value_type const& i1, value_type const& i2) const
105 return key_comparator()( i1, i2 ) < 0;
108 template <typename Q>
109 bool operator()( Q const& i1, value_type const& i2) const
111 return key_comparator()( i1, i2 ) < 0;
114 template <typename Q>
115 bool operator()( value_type const& i1, Q const& i2) const
117 return key_comparator()( i1, i2 ) < 0;
124 container_type m_Vector;
129 /// Insert value \p val of type \p Q into the container
131 The function allows to split creating of new item into two part:
132 - create item with key only from \p val
133 - try to insert new item into the container
134 - if inserting is success, calls \p f functor to initialize value-field of the new item.
136 The functor signature is:
138 void func( value_type& item );
140 where \p item is the item inserted.
142 The type \p Q may differ from \ref value_type of items storing in the container.
143 Therefore, the \p value_type should be comparable with type \p Q and constructible from type \p Q,
145 The user-defined functor is called only if the inserting is success. It may be passed by reference
148 template <typename Q, typename Func>
149 bool insert( const Q& val, Func f )
151 iterator it = std::lower_bound( m_Vector.begin(), m_Vector.end(), val, find_predicate() );
152 if ( it == m_Vector.end() || key_comparator()( val, *it ) != 0 ) {
153 value_type newItem( val );
154 it = m_Vector.insert( it, newItem );
161 template <typename... Args>
162 bool emplace( Args&&... args )
164 value_type val( std::forward<Args>(args)... );
165 iterator it = std::lower_bound( m_Vector.begin(), m_Vector.end(), val, find_predicate() );
166 if ( it == m_Vector.end() || key_comparator()( val, *it ) != 0 ) {
167 it = m_Vector.emplace( it, std::move( val ) );
173 /// Ensures that the \p item exists in the container
175 The operation performs inserting or changing data.
177 If the \p val key not found in the container, then the new item created from \p val
178 is inserted. Otherwise, the functor \p func is called with the item found.
179 The \p Func functor has interface:
181 void func( bool bNew, value_type& item, const Q& val );
186 void operator()( bool bNew, value_type& item, const Q& val );
191 - \p bNew - \p true if the item has been inserted, \p false otherwise
192 - \p item - container's item
193 - \p val - argument \p val passed into the \p ensure function
195 The functor may change non-key fields of the \p item.
197 The type \p Q may differ from \ref value_type of items storing in the container.
198 Therefore, the \p value_type should be comparable with type \p Q and constructible from type \p Q,
200 You may pass \p func argument by reference using \p std::ref
202 Returns <tt> std::pair<bool, bool> </tt> where \p first is true if operation is successfull,
203 \p second is true if new item has been added or \p false if the item with \p val key
206 template <typename Q, typename Func>
207 std::pair<bool, bool> ensure( const Q& val, Func func )
209 iterator it = std::lower_bound( m_Vector.begin(), m_Vector.end(), val, find_predicate() );
210 if ( it == m_Vector.end() || key_comparator()( val, *it ) != 0 ) {
212 value_type newItem( val );
213 it = m_Vector.insert( it, newItem );
214 func( true, *it, val );
215 return std::make_pair( true, true );
219 func( false, *it, val );
220 return std::make_pair( true, false );
226 The function searches an item with key \p key, calls \p f functor
227 and deletes the item. If \p key is not found, the functor is not called.
229 The functor \p Func interface is:
232 void operator()(value_type const& val);
235 The functor may be passed by reference using <tt>boost:ref</tt>
237 The type \p Q may differ from \ref value_type of items storing in the container.
238 Therefore, the \p value_type should be comparable with type \p Q.
240 Return \p true if key is found and deleted, \p false otherwise
242 template <typename Q, typename Func>
243 bool erase( const Q& key, Func f )
245 iterator it = std::lower_bound( m_Vector.begin(), m_Vector.end(), key, find_predicate() );
246 if ( it == m_Vector.end() || key_comparator()( key, *it ) != 0 )
251 m_Vector.erase( it );
255 template <typename Q, typename Less, typename Func>
256 bool erase( const Q& key, Less pred, Func f )
258 iterator it = std::lower_bound( m_Vector.begin(), m_Vector.end(), key, pred );
259 if ( it == m_Vector.end() || pred( key, *it ) || pred( *it, key ) )
264 m_Vector.erase( it );
268 /// Find the key \p val
270 The function searches the item with key equal to \p val and calls the functor \p f for item found.
271 The interface of \p Func functor is:
274 void operator()( value_type& item, Q& val );
277 where \p item is the item found, \p val is the <tt>find</tt> function argument.
279 You may pass \p f argument by reference using \p std::ref
281 The functor may change non-key fields of \p item.
282 The \p val argument is non-const since it can be used as \p f functor destination i.e., the functor
283 may modify both arguments.
285 The type \p Q may differ from \ref value_type of items storing in the container.
286 Therefore, the \p value_type should be comparable with type \p Q.
288 The function returns \p true if \p val is found, \p false otherwise.
290 template <typename Q, typename Func>
291 bool find( Q& val, Func f )
293 iterator it = std::lower_bound( m_Vector.begin(), m_Vector.end(), val, find_predicate() );
294 if ( it == m_Vector.end() || key_comparator()( val, *it ) != 0 )
302 template <typename Q, typename Less, typename Func>
303 bool find( Q& val, Less pred, Func f )
305 iterator it = std::lower_bound( m_Vector.begin(), m_Vector.end(), val, pred );
306 if ( it == m_Vector.end() || pred( val, *it ) || pred( *it, val ) )
314 /// Clears the container
320 iterator begin() { return m_Vector.begin(); }
321 const_iterator begin() const { return m_Vector.begin(); }
322 iterator end() { return m_Vector.end(); }
323 const_iterator end() const { return m_Vector.end(); }
325 void move_item( adapted_container& /*from*/, iterator itWhat )
327 iterator it = std::lower_bound( m_Vector.begin(), m_Vector.end(), *itWhat, find_predicate() );
328 assert( it == m_Vector.end() || key_comparator()( *itWhat, *it ) != 0 );
330 copy_item()( m_Vector, it, itWhat );
335 return m_Vector.size();
340 typedef adapted_container type ; ///< Result of \p adapt metafunction
343 }}} // namespace cds::intrusive::striped_set
348 #endif // #ifndef __CDS_CONTAINER_STRIPED_SET_BOOST_STABLE_VECTOR_ADAPTER_H