3 #ifndef __CDS_INTRUSIVE_STRIPED_SET_ADAPTER_H
4 #define __CDS_INTRUSIVE_STRIPED_SET_ADAPTER_H
6 #include <functional> // ref
7 #include <cds/opt/options.h>
8 #include <cds/intrusive/striped_set/resizing_policy.h>
9 #include <cds/opt/hash.h>
10 #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
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 \p std::ref
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 \p std::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 container_type m_Set;
212 boost_intrusive_set_adapter()
215 container_type& base_container()
220 template <typename Func>
221 bool insert( value_type& val, Func f )
223 std::pair<iterator, bool> res = m_Set.insert( val );
229 template <typename Func>
230 std::pair<bool, bool> ensure( value_type& val, Func f )
232 std::pair<iterator, bool> res = m_Set.insert( val );
233 f( res.second, *res.first, val );
234 return std::make_pair( true, res.second );
237 bool unlink( value_type& val )
239 iterator it = m_Set.find( value_type(val) );
240 if ( it == m_Set.end() || &(*it) != &val )
246 template <typename Q, typename Func>
247 value_type * erase( Q const& key, Func f )
249 iterator it = m_Set.find( key, key_comparator() );
250 if (it == m_Set.end())
252 value_type& val = *it;
258 template <typename Q, typename Less, typename Func>
259 value_type * erase( Q const& key, Less pred, Func f )
261 iterator it = m_Set.find( key, pred );
262 if (it == m_Set.end())
264 value_type& val = *it;
270 template <typename Q, typename Func>
271 bool find( Q& key, Func f )
273 return find( key, key_comparator(), f );
276 template <typename Q, typename Compare, typename Func>
277 bool find( Q& key, Compare cmp, Func f )
279 iterator it = m_Set.find( key, cmp );
280 if ( it == m_Set.end() )
291 template <typename Disposer>
292 void clear( Disposer disposer )
294 m_Set.clear_and_dispose( disposer );
297 iterator begin() { return m_Set.begin(); }
298 const_iterator begin() const { return m_Set.begin(); }
299 iterator end() { return m_Set.end(); }
300 const_iterator end() const { return m_Set.end(); }
304 return (size_t) m_Set.size();
307 void move_item( boost_intrusive_set_adapter& from, iterator itWhat )
309 value_type& val = *itWhat;
310 from.base_container().erase( itWhat );
311 insert( val, []( value_type& ) {} );
314 } // namespace details
317 } // namespace striped_set
318 }} // namespace cds::intrusive
320 #endif // #ifndef __CDS_INTRUSIVE_STRIPED_SET_ADAPTER_H