2 This file is a part of libcds - Concurrent Data Structures library
4 (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2017
6 Source code repo: http://github.com/khizmax/libcds/
7 Download: http://sourceforge.net/projects/libcds/files/
9 Redistribution and use in source and binary forms, with or without
10 modification, are permitted provided that the following conditions are met:
12 * Redistributions of source code must retain the above copyright notice, this
13 list of conditions and the following disclaimer.
15 * Redistributions in binary form must reproduce the above copyright notice,
16 this list of conditions and the following disclaimer in the documentation
17 and/or other materials provided with the distribution.
19 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
20 AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
21 IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
22 DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
23 FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
24 DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
25 SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
26 CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
27 OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
28 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
31 #ifndef CDSLIB_CONTAINER_STRIPED_SET_ADAPTER_H
32 #define CDSLIB_CONTAINER_STRIPED_SET_ADAPTER_H
34 #include <cds/intrusive/striped_set/adapter.h>
35 #include <cds/intrusive/striped_set/striping_policy.h>
37 namespace cds { namespace container {
38 /// Striped hash set related definitions
39 namespace striped_set {
42 struct copy_item ; // copy_item_policy tag
43 template <typename Container>
44 struct copy_item_policy;
46 struct swap_item ; // swap_item_policy tag
47 template <typename Container>
48 struct swap_item_policy;
50 struct move_item ; // move_item_policy tag
51 template <typename Container>
52 struct move_item_policy;
55 #ifdef CDS_DOXYGEN_INVOKED
56 /// Default adapter for hash set
58 By default, the metafunction does not make any transformation for container type \p Container.
59 \p Container should provide interface suitable for the hash set.
61 The \p Options template argument contains a list of options
62 that has been passed to cds::container::StripedSet.
64 <b>Bucket interface</b>
66 The result of metafunction is a container (a bucket) that should support the following interface:
68 Public typedefs that the bucket should provide:
69 - \p value_type - the type of the item in the bucket
70 - \p iterator - bucket's item iterator
71 - \p const_iterator - bucket's item constant iterator
72 - \p default_resizing_policy - defalt resizing policy preferable for the container.
73 By default, the library defines striped_set::load_factor_resizing<4> for sequential containers like
74 std::list, std::vector, and striped_set::no_resizing for ordered container like std::set,
77 <b>Insert value \p val of type \p Q</b>
78 \code template <typename Q, typename Func> bool insert( const Q& val, Func f ) ; \endcode
79 The function allows to split creating of new item into two part:
80 - create item with key only from \p val
81 - try to insert new item into the container
82 - if inserting is success, calls \p f functor to initialize value-field of the new item.
84 The functor signature is:
86 void func( value_type& item );
88 where \p item is the item inserted.
90 The type \p Q can differ from \ref value_type of items storing in the container.
91 Therefore, the \p value_type should be comparable with type \p Q and constructible from type \p Q,
93 The user-defined functor is called only if the inserting is success.
96 <b>Inserts data of type \ref value_type constructed with <tt>std::forward<Args>(args)...</tt></b>
97 \code template <typename... Args> bool emplace( Args&&... args ) ; \endcode
98 Returns \p true if inserting successful, \p false otherwise.
100 This function should be available only for compiler that supports
101 variadic template and move semantics
104 <b>Updates \p item</b>
105 \code template <typename Q, typename Func> std::pair<bool, bool> update( const Q& val, Func func, bool bAllowInsert ) \endcode
106 The operation performs inserting or changing data.
108 If the \p val key not found in the container, then the new item created from \p val
109 is inserted iff \p bAllowInsert is \p true. Otherwise, the functor \p func is called with the item found.
110 The \p Func functor has interface:
112 void func( bool bNew, value_type& item, const Q& val );
117 void operator()( bool bNew, value_type& item, const Q& val );
122 - \p bNew - \p true if the item has been inserted, \p false otherwise
123 - \p item - container's item
124 - \p val - argument \p val passed into the \p update() function
126 The functor can change non-key fields of the \p item.
128 The type \p Q can differ from \ref value_type of items storing in the container.
129 Therefore, the \p value_type should be comparable with type \p Q and constructible from type \p Q,
131 Returns <tt> std::pair<bool, bool> </tt> where \p first is true if operation is successful,
132 \p second is true if new item has been added or \p false if the item with \p val key
138 \code template <typename Q, typename Func> bool erase( const Q& key, Func f ) \endcode
139 The function searches an item with key \p key, calls \p f functor
140 and deletes the item. If \p key is not found, the functor is not called.
142 The functor \p Func interface is:
145 void operator()(value_type const& val);
149 The type \p Q can differ from \ref value_type of items storing in the container.
150 Therefore, the \p value_type should be comparable with type \p Q.
152 Return \p true if key is found and deleted, \p false otherwise
156 <b>Find the key \p val </b>
157 \code template <typename Q, typename Func> bool find( Q& val, Func f ) \endcode
158 The function searches the item with key equal to \p val and calls the functor \p f for item found.
159 The interface of \p Func functor is:
162 void operator()( value_type& item, Q& val );
165 where \p item is the item found, \p val is the <tt>find</tt> function argument.
167 The functor can change non-key fields of \p item.
168 The \p val argument is non-const since it can be used as \p f functor destination i.e., the functor
169 can modify both arguments.
171 The type \p Q can differ from \ref value_type of items storing in the container.
172 Therefore, the \p value_type should be comparable with type \p Q.
174 The function returns \p true if \p val is found, \p false otherwise.
177 <b>Clears the container</b>
178 \code void clear() \endcode
181 <b>Get size of bucket</b>
182 \code size_t size() const \endcode
183 This function can be required by some resizing policy
186 <b>Move item when resizing</b>
187 \code void move_item( adapted_container& from, iterator it ) \endcode
188 This helper function is invented for the set resizing when the item
189 pointed by \p it iterator is copied from an old bucket \p from to a new bucket
194 template < typename Container, typename... Options>
198 typedef Container type ; ///< adapted container type
199 typedef typename type::value_type value_type ; ///< value type stored in the container
201 #else // CDS_DOXYGEN_INVOKED
202 using cds::intrusive::striped_set::adapt;
206 using cds::intrusive::striped_set::adapted_sequential_container;
207 using cds::intrusive::striped_set::adapted_container;
210 ///@copydoc cds::intrusive::striped_set::load_factor_resizing
211 template <size_t LoadFactor>
212 using load_factor_resizing = cds::intrusive::striped_set::load_factor_resizing<LoadFactor>;
214 ///@copydoc cds::intrusive::striped_set::rational_load_factor_resizing
215 template <size_t Numerator, size_t Denominator = 1>
216 using rational_load_factor_resizing = cds::intrusive::striped_set::rational_load_factor_resizing<Numerator, Denominator>;
218 ///@copydoc cds::intrusive::striped_set::single_bucket_size_threshold
219 template <size_t Threshold>
220 using single_bucket_size_threshold = cds::intrusive::striped_set::single_bucket_size_threshold<Threshold>;
222 ///@copydoc cds::intrusive::striped_set::no_resizing
223 typedef cds::intrusive::striped_set::no_resizing no_resizing;
225 ///@copydoc cds::intrusive::striped_set::striping
226 template <class Lock = std::mutex, class Alloc = CDS_DEFAULT_ALLOCATOR >
227 using striping = cds::intrusive::striped_set::striping<Lock, Alloc>;
229 ///@copydoc cds::intrusive::striped_set::refinable
231 class RecursiveLock = std::recursive_mutex,
232 typename BackOff = cds::backoff::yield,
233 class Alloc = CDS_DEFAULT_ALLOCATOR
235 using refinable = cds::intrusive::striped_set::refinable<RecursiveLock, BackOff, Alloc >;
241 struct boost_set_copy_policies
243 struct copy_item_policy
245 typedef Set set_type;
246 typedef typename set_type::iterator iterator;
248 void operator()( set_type& set, iterator itWhat )
250 set.insert( *itWhat );
254 typedef copy_item_policy swap_item_policy;
256 struct move_item_policy
258 typedef Set set_type;
259 typedef typename set_type::iterator iterator;
261 void operator()( set_type& set, iterator itWhat )
263 set.insert( std::move( *itWhat ));
268 template <class Set, typename... Options>
269 class boost_set_adapter: public striped_set::adapted_container
272 typedef Set container_type;
274 typedef typename container_type::value_type value_type ; ///< value type stored in the container
275 typedef typename container_type::iterator iterator ; ///< container iterator
276 typedef typename container_type::const_iterator const_iterator ; ///< container const iterator
278 static bool const has_find_with = false;
279 static bool const has_erase_with = false;
282 typedef typename cds::opt::select<
283 typename cds::opt::value<
284 typename cds::opt::find_option<
285 cds::opt::copy_policy< cds::container::striped_set::move_item >
289 , cds::container::striped_set::copy_item, copy_item_policy<container_type>
290 , cds::container::striped_set::swap_item, swap_item_policy<container_type>
291 , cds::container::striped_set::move_item, move_item_policy<container_type>
295 container_type m_Set;
301 container_type& base_container()
306 template <typename Q, typename Func>
307 bool insert( const Q& val, Func f )
309 std::pair<iterator, bool> res = m_Set.insert( value_type(val));
311 f( const_cast<value_type&>(*res.first));
315 template <typename... Args>
316 bool emplace( Args&&... args )
318 std::pair<iterator, bool> res = m_Set.emplace( std::forward<Args>(args)... );
322 template <typename Q, typename Func>
323 std::pair<bool, bool> update( const Q& val, Func func, bool bAllowInsert )
325 if ( bAllowInsert ) {
326 std::pair<iterator, bool> res = m_Set.insert( value_type(val));
327 func( res.second, const_cast<value_type&>(*res.first), val );
328 return std::make_pair( true, res.second );
331 auto it = m_Set.find( value_type( val ));
332 if ( it == m_Set.end())
333 return std::make_pair( false, false );
334 func( false, const_cast<value_type&>(*it), val );
335 return std::make_pair( true, false );
339 template <typename Q, typename Func>
340 bool erase( const Q& key, Func f )
342 const_iterator it = m_Set.find( value_type(key));
343 if ( it == m_Set.end())
345 f( const_cast<value_type&>(*it));
350 template <typename Q, typename Func>
351 bool find( Q& val, Func f )
353 iterator it = m_Set.find( value_type(val));
354 if ( it == m_Set.end())
356 f( const_cast<value_type&>(*it), val );
365 iterator begin() { return m_Set.begin(); }
366 const_iterator begin() const { return m_Set.begin(); }
367 iterator end() { return m_Set.end(); }
368 const_iterator end() const { return m_Set.end(); }
370 void move_item( adapted_container& /*from*/, iterator itWhat )
372 assert( m_Set.find( *itWhat ) == m_Set.end());
373 copy_item()( m_Set, itWhat );
383 struct boost_map_copy_policies {
384 struct copy_item_policy {
385 typedef Map map_type;
386 typedef typename map_type::value_type pair_type;
387 typedef typename map_type::iterator iterator;
389 void operator()( map_type& map, iterator itWhat )
391 map.insert( *itWhat );
395 struct swap_item_policy {
396 typedef Map map_type;
397 typedef typename map_type::value_type pair_type;
398 typedef typename map_type::iterator iterator;
400 void operator()( map_type& map, iterator itWhat )
402 std::pair< iterator, bool > ret = map.insert( pair_type( itWhat->first, typename pair_type::second_type()));
403 assert( ret.second ) ; // successful insertion
404 std::swap( ret.first->second, itWhat->second );
408 struct move_item_policy {
409 typedef Map map_type;
410 typedef typename map_type::value_type pair_type;
411 typedef typename map_type::iterator iterator;
413 void operator()( map_type& map, iterator itWhat )
415 map.insert( std::move( *itWhat ));
420 template <class Map, typename... Options>
421 class boost_map_adapter: public striped_set::adapted_container
424 typedef Map container_type;
426 typedef typename container_type::value_type value_type ; ///< value type stored in the container
427 typedef typename container_type::key_type key_type;
428 typedef typename container_type::mapped_type mapped_type;
429 typedef typename container_type::iterator iterator ; ///< container iterator
430 typedef typename container_type::const_iterator const_iterator ; ///< container const iterator
432 static bool const has_find_with = false;
433 static bool const has_erase_with = false;
436 typedef typename cds::opt::select<
437 typename cds::opt::value<
438 typename cds::opt::find_option<
439 cds::opt::copy_policy< cds::container::striped_set::move_item >
443 , cds::container::striped_set::copy_item, copy_item_policy<container_type>
444 , cds::container::striped_set::swap_item, swap_item_policy<container_type>
445 , cds::container::striped_set::move_item, move_item_policy<container_type>
449 container_type m_Map;
452 template <typename Q, typename Func>
453 bool insert( const Q& key, Func f )
455 std::pair<iterator, bool> res = m_Map.insert( value_type( key_type( key ), mapped_type()));
461 template <typename Q, typename... Args>
462 bool emplace( Q&& key, Args&&... args )
464 std::pair<iterator, bool> res = m_Map.emplace( key_type( std::forward<Q>( key )), mapped_type( std::forward<Args>( args )...));
468 template <typename Q, typename Func>
469 std::pair<bool, bool> update( const Q& key, Func func, bool bAllowInsert )
471 if ( bAllowInsert ) {
472 std::pair<iterator, bool> res = m_Map.insert( value_type( key_type( key ), mapped_type()));
473 func( res.second, *res.first );
474 return std::make_pair( true, res.second );
477 auto it = m_Map.find( key_type( key ));
479 return std::make_pair( false, false );
481 return std::make_pair( true, false );
485 template <typename Q, typename Func>
486 bool erase( const Q& key, Func f )
488 iterator it = m_Map.find( key_type( key ));
489 if ( it == m_Map.end())
496 template <typename Q, typename Func>
497 bool find( Q& val, Func f )
499 iterator it = m_Map.find( key_type( val ));
500 if ( it == m_Map.end())
511 iterator begin() { return m_Map.begin(); }
512 const_iterator begin() const { return m_Map.begin(); }
513 iterator end() { return m_Map.end(); }
514 const_iterator end() const { return m_Map.end(); }
516 void move_item( adapted_container& /*from*/, iterator itWhat )
518 assert( m_Map.find( itWhat->first ) == m_Map.end());
519 copy_item()( m_Map, itWhat );
528 } // namespace details
531 } // namespace striped_set
532 }} // namespace cds::container
535 #endif // #ifndef CDSLIB_CONTAINER_STRIPED_SET_ADAPTER_H