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 {
15 /// Default adapter for intrusive striped/refinable hash set
17 By default, the metafunction does not make any transformation for container type \p Container.
18 \p Container should provide interface suitable for the hash set.
20 The \p Options template argument contains option pack
21 that will be passed to \p cds::intrusive::StripedSet.
23 <b>Bucket interface</b>
25 The result of metafunction is a container (a bucket) that should support the following interface:
27 Public typedefs that the bucket should provide:
28 - \p value_type - the type of the item in the bucket
29 - \p iterator - bucket's item iterator
30 - \p const_iterator - bucket's item constant iterator
31 - \p default_resizing_policy - default resizing policy preferable for the container.
32 By default, the library defines cds::container::striped_set::load_factor_resizing<4> for sequential containers like
33 boost::intrusive::list, and cds::container::striped_set::no_resizing for ordered container like boost::intrusive::set.
35 <b>Insert value \p val of type \p Q</b>
36 \code template <typename Func> bool insert( value_type& val, Func f ) ; \endcode
37 Inserts \p val into the container and, if inserting is successful, calls functor \p f
40 The functor signature is:
43 void operator()( value_type& item );
46 where \p item is the item inserted.
48 The user-defined functor \p f is called only if the inserting is success.
51 <b>Updates the item in the container</b>
52 \code template <typename Func> std::pair<bool, bool> update( value_type& val, Func f, bool bAllowInsert = true ) \endcode
53 The operation performs inserting or changing data.
55 If the \p val key not found in the container, then \p val is inserted iff \p bAllowInsert is \p true.
56 Otherwise, the functor \p f is called with the item found.
58 The \p Func functor has the following interface:
60 void func( bool bNew, value_type& item, value_type& val );
65 void operator()( bool bNew, value_type& item, value_type& val );
70 - \p bNew - \p true if the item has been inserted, \p false otherwise
71 - \p item - container's item
72 - \p val - argument \p val passed into the \p update() function
74 If \p val has been inserted (i.e. <tt>bNew == true</tt>) then \p item and \p val
75 are the same element: <tt>&item == &val</tt>. Otherwise, they are different.
77 The functor can change non-key fields of the \p item.
79 Returns <tt> std::pair<bool, bool> </tt> where \p first is true if operation is successfull,
80 \p second is true if new item has been added or \p false if the item with \p val key
85 \code bool unlink( value_type& val ) \endcode
86 Unlink \p val from the container if \p val belongs to it.
90 \code template <typename Q, typename Func> bool erase( Q const& key, Func f ) \endcode
91 The function searches an item with key \p key, calls \p f functor
92 and erases the item. If \p key is not found, the functor is not called.
94 The functor \p Func interface is:
97 void operator()(value_type& val);
101 The type \p Q can differ from \ref value_type of items storing in the container.
102 Therefore, the \p value_type should be comparable with type \p Q.
104 Return \p true if key is found and deleted, \p false otherwise
108 <b>Find the key \p val </b>
110 template <typename Q, typename Func> bool find( Q& val, Func f )
111 template <typename Q, typename Compare, typename Func> bool find( Q& val, Compare cmp, Func f )
113 The function searches the item with key equal to \p val and calls the functor \p f for item found.
114 The interface of \p Func functor is:
117 void operator()( value_type& item, Q& val );
120 where \p item is the item found, \p val is the <tt>find</tt> function argument.
122 The functor can change non-key fields of \p item.
123 The \p val argument may be non-const since it can be used as \p f functor destination i.e., the functor
124 can modify both arguments.
126 The type \p Q can differ from \ref value_type of items storing in the container.
127 Therefore, the \p value_type should be comparable with type \p Q.
129 The first form uses default \p compare function used for key ordering.
130 The second form allows to point specific \p Compare functor \p cmp
131 that can compare \p value_typwe and \p Q type. The interface of \p Compare is the same as \p std::less.
133 The function returns \p true if \p val is found, \p false otherwise.
136 <b>Clears the container</b>
139 template <typename Disposer> void clear( Disposer disposer )
141 Second form calls \p disposer for each item in the container before clearing.
144 <b>Get size of bucket</b>
145 \code size_t size() const \endcode
146 This function may be required by some resizing policy
152 const_iterator begin() const;
154 const_iterator end() const;
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 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
175 struct adapted_sequential_container
177 typedef striped_set::load_factor_resizing<4> default_resizing_policy;
180 struct adapted_container
182 typedef striped_set::no_resizing default_resizing_policy;
188 template <typename Set>
189 class boost_intrusive_set_adapter: public cds::intrusive::striped_set::adapted_container
192 typedef Set container_type;
194 typedef typename container_type::value_type value_type ; ///< value type stored in the container
195 typedef typename container_type::iterator iterator ; ///< container iterator
196 typedef typename container_type::const_iterator const_iterator ; ///< container const iterator
198 typedef typename container_type::value_compare key_comparator;
201 container_type m_Set;
204 boost_intrusive_set_adapter()
207 container_type& base_container()
212 template <typename Func>
213 bool insert( value_type& val, Func f )
215 std::pair<iterator, bool> res = m_Set.insert( val );
221 template <typename Func>
222 std::pair<bool, bool> update( value_type& val, Func f, bool bAllowInsert )
224 if ( bAllowInsert ) {
225 std::pair<iterator, bool> res = m_Set.insert( val );
226 f( res.second, *res.first, val );
227 return std::make_pair( true, res.second );
230 auto it = m_Set.find( val );
231 if ( it == m_Set.end() )
232 return std::make_pair( false, false );
233 f( false, *it, val );
234 return std::make_pair( true, false );
238 bool unlink( value_type& val )
240 iterator it = m_Set.find( value_type(val));
241 if ( it == m_Set.end() || &(*it) != &val )
247 template <typename Q, typename Func>
248 value_type * erase( Q const& key, Func f )
250 iterator it = m_Set.find( key, key_comparator() );
251 if (it == m_Set.end())
253 value_type& val = *it;
259 template <typename Q, typename Less, typename Func>
260 value_type * erase( Q const& key, Less pred, Func f )
262 iterator it = m_Set.find( key, pred );
263 if (it == m_Set.end())
265 value_type& val = *it;
271 template <typename Q, typename Func>
272 bool find( Q& key, Func f )
274 return find( key, key_comparator(), f );
277 template <typename Q, typename Compare, typename Func>
278 bool find( Q& key, Compare cmp, Func f )
280 iterator it = m_Set.find( key, cmp );
281 if ( it == m_Set.end() )
292 template <typename Disposer>
293 void clear( Disposer disposer )
295 m_Set.clear_and_dispose( disposer );
298 iterator begin() { return m_Set.begin(); }
299 const_iterator begin() const { return m_Set.begin(); }
300 iterator end() { return m_Set.end(); }
301 const_iterator end() const { return m_Set.end(); }
305 return (size_t) m_Set.size();
308 void move_item( boost_intrusive_set_adapter& from, iterator itWhat )
310 value_type& val = *itWhat;
311 from.base_container().erase( itWhat );
312 insert( val, []( value_type& ) {} );
315 } // namespace details
318 } // namespace striped_set
319 }} // namespace cds::intrusive
321 #endif // #ifndef CDSLIB_INTRUSIVE_STRIPED_SET_ADAPTER_H