3 #ifndef CDSLIB_CONTAINER_STRIPED_SET_ADAPTER_H
4 #define CDSLIB_CONTAINER_STRIPED_SET_ADAPTER_H
6 #include <cds/intrusive/striped_set/adapter.h>
7 #include <cds/intrusive/striped_set/striping_policy.h>
9 namespace cds { namespace container {
10 /// Striped hash set related definitions
11 namespace striped_set {
14 struct copy_item ; // copy_item_policy tag
15 template <typename Container>
16 struct copy_item_policy;
18 struct swap_item ; // swap_item_policy tag
19 template <typename Container>
20 struct swap_item_policy;
22 struct move_item ; // move_item_policy tag
23 template <typename Container>
24 struct move_item_policy;
27 #ifdef CDS_DOXYGEN_INVOKED
28 /// Default adapter for hash set
30 By default, the metafunction does not make any transformation for container type \p Container.
31 \p Container should provide interface suitable for the hash set.
33 The \p Options template argument contains a list of options
34 that has been passed to cds::container::StripedSet.
36 <b>Bucket interface</b>
38 The result of metafunction is a container (a bucket) that should support the following interface:
40 Public typedefs that the bucket should provide:
41 - \p value_type - the type of the item in the bucket
42 - \p iterator - bucket's item iterator
43 - \p const_iterator - bucket's item constant iterator
44 - \p default_resizing_policy - defalt resizing policy preferable for the container.
45 By default, the library defines striped_set::load_factor_resizing<4> for sequential containers like
46 std::list, std::vector, and striped_set::no_resizing for ordered container like std::set,
49 <b>Insert value \p val of type \p Q</b>
50 \code template <typename Q, typename Func> bool insert( const Q& val, Func f ) ; \endcode
51 The function allows to split creating of new item into two part:
52 - create item with key only from \p val
53 - try to insert new item into the container
54 - if inserting is success, calls \p f functor to initialize value-field of the new item.
56 The functor signature is:
58 void func( value_type& item );
60 where \p item is the item inserted.
62 The type \p Q can differ from \ref value_type of items storing in the container.
63 Therefore, the \p value_type should be comparable with type \p Q and constructible from type \p Q,
65 The user-defined functor is called only if the inserting is success.
68 <b>Inserts data of type \ref value_type constructed with <tt>std::forward<Args>(args)...</tt></b>
69 \code template <typename... Args> bool emplace( Args&&... args ) ; \endcode
70 Returns \p true if inserting successful, \p false otherwise.
72 This function should be available only for compiler that supports
73 variadic template and move semantics
76 <b>Updates \p item</b>
77 \code template <typename Q, typename Func> std::pair<bool, bool> update( const Q& val, Func func, bool bAllowInsert ) \endcode
78 The operation performs inserting or changing data.
80 If the \p val key not found in the container, then the new item created from \p val
81 is inserted iff \p bAllowInsert is \p true. Otherwise, the functor \p func is called with the item found.
82 The \p Func functor has interface:
84 void func( bool bNew, value_type& item, const Q& val );
89 void operator()( bool bNew, value_type& item, const Q& val );
94 - \p bNew - \p true if the item has been inserted, \p false otherwise
95 - \p item - container's item
96 - \p val - argument \p val passed into the \p update() function
98 The functor can change non-key fields of the \p item.
100 The type \p Q can differ from \ref value_type of items storing in the container.
101 Therefore, the \p value_type should be comparable with type \p Q and constructible from type \p Q,
103 Returns <tt> std::pair<bool, bool> </tt> where \p first is true if operation is successfull,
104 \p second is true if new item has been added or \p false if the item with \p val key
110 \code template <typename Q, typename Func> bool erase( const Q& key, Func f ) \endcode
111 The function searches an item with key \p key, calls \p f functor
112 and deletes the item. If \p key is not found, the functor is not called.
114 The functor \p Func interface is:
117 void operator()(value_type const& val);
121 The type \p Q can differ from \ref value_type of items storing in the container.
122 Therefore, the \p value_type should be comparable with type \p Q.
124 Return \p true if key is found and deleted, \p false otherwise
128 <b>Find the key \p val </b>
129 \code template <typename Q, typename Func> bool find( Q& val, Func f ) \endcode
130 The function searches the item with key equal to \p val and calls the functor \p f for item found.
131 The interface of \p Func functor is:
134 void operator()( value_type& item, Q& val );
137 where \p item is the item found, \p val is the <tt>find</tt> function argument.
139 The functor can change non-key fields of \p item.
140 The \p val argument is non-const since it can be used as \p f functor destination i.e., the functor
141 can modify both arguments.
143 The type \p Q can differ from \ref value_type of items storing in the container.
144 Therefore, the \p value_type should be comparable with type \p Q.
146 The function returns \p true if \p val is found, \p false otherwise.
149 <b>Clears the container</b>
150 \code void clear() \endcode
153 <b>Get size of bucket</b>
154 \code size_t size() const \endcode
155 This function can be required by some resizing policy
158 <b>Move item when resizing</b>
159 \code void move_item( adapted_container& from, iterator it ) \endcode
160 This helper function is invented for the set resizing when the item
161 pointed by \p it iterator is copied from an old bucket \p from to a new bucket
166 template < typename Container, typename... Options>
170 typedef Container type ; ///< adapted container type
171 typedef typename type::value_type value_type ; ///< value type stored in the container
173 #else // CDS_DOXYGEN_INVOKED
174 using cds::intrusive::striped_set::adapt;
178 using cds::intrusive::striped_set::adapted_sequential_container;
179 using cds::intrusive::striped_set::adapted_container;
182 ///@copydoc cds::intrusive::striped_set::load_factor_resizing
183 template <size_t LoadFactor>
184 using load_factor_resizing = cds::intrusive::striped_set::load_factor_resizing<LoadFactor>;
186 ///@copydoc cds::intrusive::striped_set::rational_load_factor_resizing
187 template <size_t Numerator, size_t Denominator = 1>
188 using rational_load_factor_resizing = cds::intrusive::striped_set::rational_load_factor_resizing<Numerator, Denominator>;
190 ///@copydoc cds::intrusive::striped_set::single_bucket_size_threshold
191 template <size_t Threshold>
192 using single_bucket_size_threshold = cds::intrusive::striped_set::single_bucket_size_threshold<Threshold>;
194 ///@copydoc cds::intrusive::striped_set::no_resizing
195 typedef cds::intrusive::striped_set::no_resizing no_resizing;
197 ///@copydoc cds::intrusive::striped_set::striping
198 template <class Lock = std::mutex, class Alloc = CDS_DEFAULT_ALLOCATOR >
199 using striping = cds::intrusive::striped_set::striping<Lock, Alloc>;
201 ///@copydoc cds::intrusive::striped_set::refinable
203 class RecursiveLock = std::recursive_mutex,
204 typename BackOff = cds::backoff::yield,
205 class Alloc = CDS_DEFAULT_ALLOCATOR
207 using refinable = cds::intrusive::striped_set::refinable<RecursiveLock, BackOff, Alloc >;
213 struct boost_set_copy_policies
215 struct copy_item_policy
217 typedef Set set_type;
218 typedef typename set_type::iterator iterator;
220 void operator()( set_type& set, iterator itWhat )
222 set.insert( *itWhat );
226 typedef copy_item_policy swap_item_policy;
228 struct move_item_policy
230 typedef Set set_type;
231 typedef typename set_type::iterator iterator;
233 void operator()( set_type& set, iterator itWhat )
235 set.insert( std::move( *itWhat ) );
240 template <class Set, typename... Options>
241 class boost_set_adapter: public striped_set::adapted_container
244 typedef Set container_type;
246 typedef typename container_type::value_type value_type ; ///< value type stored in the container
247 typedef typename container_type::iterator iterator ; ///< container iterator
248 typedef typename container_type::const_iterator const_iterator ; ///< container const iterator
250 static bool const has_find_with = false;
251 static bool const has_erase_with = false;
254 typedef typename cds::opt::select<
255 typename cds::opt::value<
256 typename cds::opt::find_option<
257 cds::opt::copy_policy< cds::container::striped_set::move_item >
261 , cds::container::striped_set::copy_item, copy_item_policy<container_type>
262 , cds::container::striped_set::swap_item, swap_item_policy<container_type>
263 , cds::container::striped_set::move_item, move_item_policy<container_type>
267 container_type m_Set;
273 container_type& base_container()
278 template <typename Q, typename Func>
279 bool insert( const Q& val, Func f )
281 std::pair<iterator, bool> res = m_Set.insert( value_type(val) );
283 f( const_cast<value_type&>(*res.first) );
287 template <typename... Args>
288 bool emplace( Args&&... args )
290 std::pair<iterator, bool> res = m_Set.emplace( std::forward<Args>(args)... );
294 template <typename Q, typename Func>
295 std::pair<bool, bool> update( const Q& val, Func func, bool bAllowInsert )
297 if ( bAllowInsert ) {
298 std::pair<iterator, bool> res = m_Set.insert( value_type(val) );
299 func( res.second, const_cast<value_type&>(*res.first), val );
300 return std::make_pair( true, res.second );
303 auto it = m_Set.find( val );
304 if ( it == m_Set.end() )
305 return std::make_pair( false, false );
306 func( false, const_cast<value_type&>(*it), val );
307 return std::make_pair( true, false );
311 template <typename Q, typename Func>
312 bool erase( const Q& key, Func f )
314 const_iterator it = m_Set.find( value_type(key) );
315 if ( it == m_Set.end() )
317 f( const_cast<value_type&>(*it) );
322 template <typename Q, typename Func>
323 bool find( Q& val, Func f )
325 iterator it = m_Set.find( value_type(val) );
326 if ( it == m_Set.end() )
328 f( const_cast<value_type&>(*it), val );
337 iterator begin() { return m_Set.begin(); }
338 const_iterator begin() const { return m_Set.begin(); }
339 iterator end() { return m_Set.end(); }
340 const_iterator end() const { return m_Set.end(); }
342 void move_item( adapted_container& /*from*/, iterator itWhat )
344 assert( m_Set.find( *itWhat ) == m_Set.end() );
345 copy_item()( m_Set, itWhat );
355 struct boost_map_copy_policies {
356 struct copy_item_policy {
357 typedef Map map_type;
358 typedef typename map_type::value_type pair_type;
359 typedef typename map_type::iterator iterator;
361 void operator()( map_type& map, iterator itWhat )
363 map.insert( *itWhat );
367 struct swap_item_policy {
368 typedef Map map_type;
369 typedef typename map_type::value_type pair_type;
370 typedef typename map_type::iterator iterator;
372 void operator()( map_type& map, iterator itWhat )
374 std::pair< iterator, bool > ret = map.insert( pair_type( itWhat->first, typename pair_type::second_type() ));
375 assert( ret.second ) ; // successful insertion
376 std::swap( ret.first->second, itWhat->second );
380 struct move_item_policy {
381 typedef Map map_type;
382 typedef typename map_type::value_type pair_type;
383 typedef typename map_type::iterator iterator;
385 void operator()( map_type& map, iterator itWhat )
387 map.insert( std::move( *itWhat ) );
392 template <class Map, typename... Options>
393 class boost_map_adapter: public striped_set::adapted_container
396 typedef Map container_type;
398 typedef typename container_type::value_type value_type ; ///< value type stored in the container
399 typedef typename container_type::key_type key_type;
400 typedef typename container_type::mapped_type mapped_type;
401 typedef typename container_type::iterator iterator ; ///< container iterator
402 typedef typename container_type::const_iterator const_iterator ; ///< container const iterator
404 static bool const has_find_with = false;
405 static bool const has_erase_with = false;
408 typedef typename cds::opt::select<
409 typename cds::opt::value<
410 typename cds::opt::find_option<
411 cds::opt::copy_policy< cds::container::striped_set::move_item >
415 , cds::container::striped_set::copy_item, copy_item_policy<container_type>
416 , cds::container::striped_set::swap_item, swap_item_policy<container_type>
417 , cds::container::striped_set::move_item, move_item_policy<container_type>
421 container_type m_Map;
424 template <typename Q, typename Func>
425 bool insert( const Q& key, Func f )
427 std::pair<iterator, bool> res = m_Map.insert( value_type( key, mapped_type() ) );
433 template <typename Q, typename... Args>
434 bool emplace( Q&& key, Args&&... args )
436 std::pair<iterator, bool> res = m_Map.emplace( std::forward<Q>(key), std::move( mapped_type( std::forward<Args>(args)...)));
440 template <typename Q, typename Func>
441 std::pair<bool, bool> update( const Q& key, Func func, bool bAllowInsert )
443 if ( bAllowInsert ) {
444 std::pair<iterator, bool> res = m_Map.insert( value_type( key, mapped_type() ));
445 func( res.second, *res.first );
446 return std::make_pair( true, res.second );
449 auto it = m_Map.find(key_type( key ));
451 return std::make_pair( false, false );
453 return std::make_pair( true, false );
457 template <typename Q, typename Func>
458 bool erase( const Q& key, Func f )
460 iterator it = m_Map.find( key_type(key) );
461 if ( it == m_Map.end() )
468 template <typename Q, typename Func>
469 bool find( Q& val, Func f )
471 iterator it = m_Map.find( key_type(val) );
472 if ( it == m_Map.end() )
483 iterator begin() { return m_Map.begin(); }
484 const_iterator begin() const { return m_Map.begin(); }
485 iterator end() { return m_Map.end(); }
486 const_iterator end() const { return m_Map.end(); }
488 void move_item( adapted_container& /*from*/, iterator itWhat )
490 assert( m_Map.find( itWhat->first ) == m_Map.end() );
491 copy_item()( m_Map, itWhat );
500 } // namespace details
503 } // namespace striped_set
504 }} // namespace cds::container
507 #endif // #ifndef CDSLIB_CONTAINER_STRIPED_SET_ADAPTER_H