3 #ifndef __CDS_INTRUSIVE_STRIPED_SET_ADAPTER_H
4 #define __CDS_INTRUSIVE_STRIPED_SET_ADAPTER_H
6 #include <cds/opt/options.h>
7 #include <cds/intrusive/striped_set/resizing_policy.h>
8 #include <cds/opt/hash.h>
9 #include <cds/opt/compare.h> // cds::opt::details::make_comparator - for some adapt specializations
12 namespace cds { namespace intrusive {
14 /// StripedSet related definitions
15 namespace striped_set {
17 /// Default adapter for intrusive striped/refinable hash set
19 By default, the metafunction does not make any transformation for container type \p Container.
20 \p Container should provide interface suitable for the hash set.
22 The \p SetOptions template argument contains option pack
23 that has been passed to cds::intrusive::StripedSet.
25 <b>Bucket interface</b>
27 The result of metafunction is a container (a bucket) that should support the following interface:
29 Public typedefs that the bucket should provide:
30 - \p value_type - the type of the item in the bucket
31 - \p iterator - bucket's item iterator
32 - \p const_iterator - bucket's item constant iterator
33 - \p default_resizing_policy - default resizing policy preferable for the container.
34 By default, the library defines cds::container::striped_set::load_factor_resizing<4> for sequential containers like
35 boost::intrusive::list, and cds::container::striped_set::no_resizing for ordered container like boost::intrusive::set.
37 <b>Insert value \p val of type \p Q</b>
38 \code template <typename Func> bool insert( value_type& val, Func f ) ; \endcode
39 Inserts \p val into the container and, if inserting is successful, calls functor \p f
42 The functor signature is:
45 void operator()( value_type& item );
48 where \p item is the item inserted.
50 The user-defined functor \p f is called only if the inserting is success. It can be passed by reference
51 using <tt>boost::ref</tt>
54 <b>Ensures that the \p item exists in the container</b>
55 \code template <typename Func> std::pair<bool, bool> ensure( value_type& val, Func f ) \endcode
56 The operation performs inserting or changing data.
58 If the \p val key not found in the container, then \p val is inserted.
59 Otherwise, the functor \p f is called with the item found.
61 The \p Func functor has the following interface:
63 void func( bool bNew, value_type& item, value_type& val );
68 void operator()( bool bNew, value_type& item, value_type& val );
73 - \p bNew - \p true if the item has been inserted, \p false otherwise
74 - \p item - container's item
75 - \p val - argument \p val passed into the \p ensure function
77 If \p val has been inserted (i.e. <tt>bNew == true</tt>) then \p item and \p val
78 are the same element: <tt>&item == &val</tt>. Otherwise, they are different.
80 The functor can change non-key fields of the \p item.
82 You can pass \p f argument by reference using <tt>boost::ref</tt>.
84 Returns <tt> std::pair<bool, bool> </tt> where \p first is true if operation is successfull,
85 \p second is true if new item has been added or \p false if the item with \p val key
90 \code bool unlink( value_type& val ) \endcode
91 Unlink \p val from the container if \p val belongs to it.
95 \code template <typename Q, typename Func> bool erase( Q const& key, Func f ) \endcode
96 The function searches an item with key \p key, calls \p f functor
97 and erases the item. If \p key is not found, the functor is not called.
99 The functor \p Func interface is:
102 void operator()(value_type& val);
105 The functor can be passed by reference using <tt>boost:ref</tt>
107 The type \p Q can differ from \ref value_type of items storing in the container.
108 Therefore, the \p value_type should be comparable with type \p Q.
110 Return \p true if key is found and deleted, \p false otherwise
114 <b>Find the key \p val </b>
116 template <typename Q, typename Func> bool find( Q& val, Func f )
117 template <typename Q, typename Compare, typename Func> bool find( Q& val, Compare cmp, Func f )
119 The function searches the item with key equal to \p val and calls the functor \p f for item found.
120 The interface of \p Func functor is:
123 void operator()( value_type& item, Q& val );
126 where \p item is the item found, \p val is the <tt>find</tt> function argument.
128 You can pass \p f argument by reference using <tt>boost::ref</tt> or cds::ref.
130 The functor can change non-key fields of \p item.
131 The \p val argument may be non-const since it can be used as \p f functor destination i.e., the functor
132 can modify both arguments.
134 The type \p Q can differ from \ref value_type of items storing in the container.
135 Therefore, the \p value_type should be comparable with type \p Q.
137 The first form uses default \p compare function used for key ordering.
138 The second form allows to point specific \p Compare functor \p cmp
139 that can compare \p value_typwe and \p Q type. The interface of \p Compare is the same as \p std::less.
141 The function returns \p true if \p val is found, \p false otherwise.
144 <b>Clears the container</b>
147 template <typename Disposer> void clear( Disposer disposer )
149 Second form calls \p disposer for each item in the container before clearing.
152 <b>Get size of bucket</b>
153 \code size_t size() const \endcode
154 This function may be required by some resizing policy
160 const_iterator begin() const;
162 const_iterator end() const;
166 <b>Move item when resizing</b>
167 \code void move_item( adapted_container& from, iterator it ) \endcode
168 This helper function is invented for the set resizing when the item
169 pointed by \p it iterator is copied from old bucket \p from to a new bucket
174 template < typename Container, typename... Options >
178 typedef Container type ; ///< adapted container type
179 typedef typename type::value_type value_type ; ///< value type stored in the container
183 struct adapted_sequential_container
185 typedef striped_set::load_factor_resizing<4> default_resizing_policy;
188 struct adapted_container
190 typedef striped_set::no_resizing default_resizing_policy;
196 template <typename Set>
197 class boost_intrusive_set_adapter: public cds::intrusive::striped_set::adapted_container
200 typedef Set container_type;
202 typedef typename container_type::value_type value_type ; ///< value type stored in the container
203 typedef typename container_type::iterator iterator ; ///< container iterator
204 typedef typename container_type::const_iterator const_iterator ; ///< container const iterator
206 typedef typename container_type::value_compare key_comparator;
209 # ifndef CDS_CXX11_LAMBDA_SUPPORT
210 struct empty_insert_functor {
211 void operator()( value_type& )
216 container_type m_Set;
219 boost_intrusive_set_adapter()
222 container_type& base_container()
227 template <typename Func>
228 bool insert( value_type& val, Func f )
230 std::pair<iterator, bool> res = m_Set.insert( val );
232 cds::unref(f)( val );
236 template <typename Func>
237 std::pair<bool, bool> ensure( value_type& val, Func f )
239 std::pair<iterator, bool> res = m_Set.insert( val );
240 cds::unref(f)( res.second, *res.first, val );
241 return std::make_pair( true, res.second );
244 bool unlink( value_type& val )
246 iterator it = m_Set.find( value_type(val) );
247 if ( it == m_Set.end() || &(*it) != &val )
253 template <typename Q, typename Func>
254 value_type * erase( Q const& key, Func f )
256 iterator it = m_Set.find( key, key_comparator() );
257 if (it == m_Set.end())
259 value_type& val = *it;
260 cds::unref(f)( val );
265 template <typename Q, typename Less, typename Func>
266 value_type * erase( Q const& key, Less pred, Func f )
268 iterator it = m_Set.find( key, pred );
269 if (it == m_Set.end())
271 value_type& val = *it;
272 cds::unref(f)( val );
277 template <typename Q, typename Func>
278 bool find( Q& key, Func f )
280 return find( key, key_comparator(), f );
283 template <typename Q, typename Compare, typename Func>
284 bool find( Q& key, Compare cmp, Func f )
286 iterator it = m_Set.find( key, cmp );
287 if ( it == m_Set.end() )
289 cds::unref(f)( *it, key );
298 template <typename Disposer>
299 void clear( Disposer disposer )
301 m_Set.clear_and_dispose( disposer );
304 iterator begin() { return m_Set.begin(); }
305 const_iterator begin() const { return m_Set.begin(); }
306 iterator end() { return m_Set.end(); }
307 const_iterator end() const { return m_Set.end(); }
311 return (size_t) m_Set.size();
314 void move_item( boost_intrusive_set_adapter& from, iterator itWhat )
316 value_type& val = *itWhat;
317 from.base_container().erase( itWhat );
318 # ifdef CDS_CXX11_LAMBDA_SUPPORT
319 insert( val, []( value_type& ) {} );
321 insert( val, empty_insert_functor() );
325 } // namespace details
328 } // namespace striped_set
329 }} // namespace cds::intrusive
332 //#if defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
335 #endif // #ifndef __CDS_INTRUSIVE_STRIPED_SET_ADAPTER_H