3 #ifndef CDSLIB_INTRUSIVE_STRIPED_SET_ADAPTER_H
4 #define CDSLIB_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
11 namespace cds { namespace intrusive {
13 /// StripedSet related definitions
14 namespace striped_set {
16 struct implementation_tag;
19 /// Default adapter for intrusive striped/refinable hash set
21 By default, the metafunction does not make any transformation for container type \p Container.
22 \p Container should provide interface suitable for the hash set.
24 The \p Options template argument contains option pack
25 that will be passed to \p cds::intrusive::StripedSet.
27 <b>Bucket interface</b>
29 The result of metafunction is a container (a bucket) that should support the following interface:
31 Public typedefs that the bucket should provide:
32 - \p value_type - the type of the item in the bucket
33 - \p iterator - bucket's item iterator
34 - \p const_iterator - bucket's item constant iterator
35 - \p default_resizing_policy - default resizing policy preferable for the container.
36 By default, the library defines cds::container::striped_set::load_factor_resizing<4> for sequential containers like
37 boost::intrusive::list, and cds::container::striped_set::no_resizing for ordered container like boost::intrusive::set.
39 <b>Insert value \p val of type \p Q</b>
40 \code template <typename Func> bool insert( value_type& val, Func f ) ; \endcode
41 Inserts \p val into the container and, if inserting is successful, calls functor \p f
44 The functor signature is:
47 void operator()( value_type& item );
50 where \p item is the item inserted.
52 The user-defined functor \p f is called only if the inserting is success.
55 <b>Ensures that the \p item exists in the container</b>
56 \code template <typename Func> std::pair<bool, bool> ensure( value_type& val, Func f ) \endcode
57 The operation performs inserting or changing data.
59 If the \p val key not found in the container, then \p val is inserted.
60 Otherwise, the functor \p f is called with the item found.
62 The \p Func functor has the following interface:
64 void func( bool bNew, value_type& item, value_type& val );
69 void operator()( bool bNew, value_type& item, value_type& val );
74 - \p bNew - \p true if the item has been inserted, \p false otherwise
75 - \p item - container's item
76 - \p val - argument \p val passed into the \p ensure function
78 If \p val has been inserted (i.e. <tt>bNew == true</tt>) then \p item and \p val
79 are the same element: <tt>&item == &val</tt>. Otherwise, they are different.
81 The functor can change non-key fields of the \p item.
83 Returns <tt> std::pair<bool, bool> </tt> where \p first is true if operation is successfull,
84 \p second is true if new item has been added or \p false if the item with \p val key
89 \code bool unlink( value_type& val ) \endcode
90 Unlink \p val from the container if \p val belongs to it.
94 \code template <typename Q, typename Func> bool erase( Q const& key, Func f ) \endcode
95 The function searches an item with key \p key, calls \p f functor
96 and erases the item. If \p key is not found, the functor is not called.
98 The functor \p Func interface is:
101 void operator()(value_type& val);
105 The type \p Q can differ from \ref value_type of items storing in the container.
106 Therefore, the \p value_type should be comparable with type \p Q.
108 Return \p true if key is found and deleted, \p false otherwise
112 <b>Find the key \p val </b>
114 template <typename Q, typename Func> bool find( Q& val, Func f )
115 template <typename Q, typename Compare, typename Func> bool find( Q& val, Compare cmp, Func f )
117 The function searches the item with key equal to \p val and calls the functor \p f for item found.
118 The interface of \p Func functor is:
121 void operator()( value_type& item, Q& val );
124 where \p item is the item found, \p val is the <tt>find</tt> function argument.
126 The functor can change non-key fields of \p item.
127 The \p val argument may be non-const since it can be used as \p f functor destination i.e., the functor
128 can modify both arguments.
130 The type \p Q can differ from \ref value_type of items storing in the container.
131 Therefore, the \p value_type should be comparable with type \p Q.
133 The first form uses default \p compare function used for key ordering.
134 The second form allows to point specific \p Compare functor \p cmp
135 that can compare \p value_typwe and \p Q type. The interface of \p Compare is the same as \p std::less.
137 The function returns \p true if \p val is found, \p false otherwise.
140 <b>Clears the container</b>
143 template <typename Disposer> void clear( Disposer disposer )
145 Second form calls \p disposer for each item in the container before clearing.
148 <b>Get size of bucket</b>
149 \code size_t size() const \endcode
150 This function may be required by some resizing policy
156 const_iterator begin() const;
158 const_iterator end() const;
162 <b>Move item when resizing</b>
163 \code void move_item( adapted_container& from, iterator it ) \endcode
164 This helper function is invented for the set resizing when the item
165 pointed by \p it iterator is copied from old bucket \p from to a new bucket
170 template < typename Container, typename... Options >
174 typedef Container type ; ///< adapted container type
175 typedef typename type::value_type value_type ; ///< value type stored in the container
179 struct adapted_sequential_container
181 typedef striped_set::load_factor_resizing<4> default_resizing_policy;
184 struct adapted_container
186 typedef striped_set::no_resizing default_resizing_policy;
192 template <typename Set>
193 class boost_intrusive_set_adapter: public cds::intrusive::striped_set::adapted_container
196 typedef Set container_type;
198 typedef typename container_type::value_type value_type ; ///< value type stored in the container
199 typedef typename container_type::iterator iterator ; ///< container iterator
200 typedef typename container_type::const_iterator const_iterator ; ///< container const iterator
202 typedef typename container_type::value_compare key_comparator;
205 container_type m_Set;
208 boost_intrusive_set_adapter()
211 container_type& base_container()
216 template <typename Func>
217 bool insert( value_type& val, Func f )
219 std::pair<iterator, bool> res = m_Set.insert( val );
225 template <typename Func>
226 std::pair<bool, bool> ensure( value_type& val, Func f )
228 std::pair<iterator, bool> res = m_Set.insert( val );
229 f( res.second, *res.first, val );
230 return std::make_pair( true, res.second );
233 bool unlink( value_type& val )
235 iterator it = m_Set.find( value_type(val) );
236 if ( it == m_Set.end() || &(*it) != &val )
242 template <typename Q, typename Func>
243 value_type * erase( Q const& key, Func f )
245 iterator it = m_Set.find( key, key_comparator() );
246 if (it == m_Set.end())
248 value_type& val = *it;
254 template <typename Q, typename Less, typename Func>
255 value_type * erase( Q const& key, Less pred, Func f )
257 iterator it = m_Set.find( key, pred );
258 if (it == m_Set.end())
260 value_type& val = *it;
266 template <typename Q, typename Func>
267 bool find( Q& key, Func f )
269 return find( key, key_comparator(), f );
272 template <typename Q, typename Compare, typename Func>
273 bool find( Q& key, Compare cmp, Func f )
275 iterator it = m_Set.find( key, cmp );
276 if ( it == m_Set.end() )
287 template <typename Disposer>
288 void clear( Disposer disposer )
290 m_Set.clear_and_dispose( disposer );
293 iterator begin() { return m_Set.begin(); }
294 const_iterator begin() const { return m_Set.begin(); }
295 iterator end() { return m_Set.end(); }
296 const_iterator end() const { return m_Set.end(); }
300 return (size_t) m_Set.size();
303 void move_item( boost_intrusive_set_adapter& from, iterator itWhat )
305 value_type& val = *itWhat;
306 from.base_container().erase( itWhat );
307 insert( val, []( value_type& ) {} );
310 } // namespace details
313 } // namespace striped_set
314 }} // namespace cds::intrusive
316 #endif // #ifndef CDSLIB_INTRUSIVE_STRIPED_SET_ADAPTER_H