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 /// Default adapter for intrusive striped/refinable hash set
18 By default, the metafunction does not make any transformation for container type \p Container.
19 \p Container should provide interface suitable for the hash set.
21 The \p Options template argument contains option pack
22 that will be passed to \p cds::intrusive::StripedSet.
24 <b>Bucket interface</b>
26 The result of metafunction is a container (a bucket) that should support the following interface:
28 Public typedefs that the bucket should provide:
29 - \p value_type - the type of the item in the bucket
30 - \p iterator - bucket's item iterator
31 - \p const_iterator - bucket's item constant iterator
32 - \p default_resizing_policy - default resizing policy preferable for the container.
33 By default, the library defines cds::container::striped_set::load_factor_resizing<4> for sequential containers like
34 boost::intrusive::list, and cds::container::striped_set::no_resizing for ordered container like boost::intrusive::set.
36 <b>Insert value \p val of type \p Q</b>
37 \code template <typename Func> bool insert( value_type& val, Func f ) ; \endcode
38 Inserts \p val into the container and, if inserting is successful, calls functor \p f
41 The functor signature is:
44 void operator()( value_type& item );
47 where \p item is the item inserted.
49 The user-defined functor \p f is called only if the inserting is success.
52 <b>Ensures that the \p item exists in the container</b>
53 \code template <typename Func> std::pair<bool, bool> ensure( value_type& val, Func f ) \endcode
54 The operation performs inserting or changing data.
56 If the \p val key not found in the container, then \p val is inserted.
57 Otherwise, the functor \p f is called with the item found.
59 The \p Func functor has the following interface:
61 void func( bool bNew, value_type& item, value_type& val );
66 void operator()( bool bNew, value_type& item, value_type& val );
71 - \p bNew - \p true if the item has been inserted, \p false otherwise
72 - \p item - container's item
73 - \p val - argument \p val passed into the \p ensure function
75 If \p val has been inserted (i.e. <tt>bNew == true</tt>) then \p item and \p val
76 are the same element: <tt>&item == &val</tt>. Otherwise, they are different.
78 The functor can change non-key fields of the \p item.
80 Returns <tt> std::pair<bool, bool> </tt> where \p first is true if operation is successfull,
81 \p second is true if new item has been added or \p false if the item with \p val key
86 \code bool unlink( value_type& val ) \endcode
87 Unlink \p val from the container if \p val belongs to it.
91 \code template <typename Q, typename Func> bool erase( Q const& key, Func f ) \endcode
92 The function searches an item with key \p key, calls \p f functor
93 and erases the item. If \p key is not found, the functor is not called.
95 The functor \p Func interface is:
98 void operator()(value_type& val);
102 The type \p Q can differ from \ref value_type of items storing in the container.
103 Therefore, the \p value_type should be comparable with type \p Q.
105 Return \p true if key is found and deleted, \p false otherwise
109 <b>Find the key \p val </b>
111 template <typename Q, typename Func> bool find( Q& val, Func f )
112 template <typename Q, typename Compare, typename Func> bool find( Q& val, Compare cmp, Func f )
114 The function searches the item with key equal to \p val and calls the functor \p f for item found.
115 The interface of \p Func functor is:
118 void operator()( value_type& item, Q& val );
121 where \p item is the item found, \p val is the <tt>find</tt> function argument.
123 The functor can change non-key fields of \p item.
124 The \p val argument may be non-const since it can be used as \p f functor destination i.e., the functor
125 can modify both arguments.
127 The type \p Q can differ from \ref value_type of items storing in the container.
128 Therefore, the \p value_type should be comparable with type \p Q.
130 The first form uses default \p compare function used for key ordering.
131 The second form allows to point specific \p Compare functor \p cmp
132 that can compare \p value_typwe and \p Q type. The interface of \p Compare is the same as \p std::less.
134 The function returns \p true if \p val is found, \p false otherwise.
137 <b>Clears the container</b>
140 template <typename Disposer> void clear( Disposer disposer )
142 Second form calls \p disposer for each item in the container before clearing.
145 <b>Get size of bucket</b>
146 \code size_t size() const \endcode
147 This function may be required by some resizing policy
153 const_iterator begin() const;
155 const_iterator end() const;
159 <b>Move item when resizing</b>
160 \code void move_item( adapted_container& from, iterator it ) \endcode
161 This helper function is invented for the set resizing when the item
162 pointed by \p it iterator is copied from old bucket \p from to a new bucket
167 template < typename Container, typename... Options >
171 typedef Container type ; ///< adapted container type
172 typedef typename type::value_type value_type ; ///< value type stored in the container
176 struct adapted_sequential_container
178 typedef striped_set::load_factor_resizing<4> default_resizing_policy;
181 struct adapted_container
183 typedef striped_set::no_resizing default_resizing_policy;
189 template <typename Set>
190 class boost_intrusive_set_adapter: public cds::intrusive::striped_set::adapted_container
193 typedef Set container_type;
195 typedef typename container_type::value_type value_type ; ///< value type stored in the container
196 typedef typename container_type::iterator iterator ; ///< container iterator
197 typedef typename container_type::const_iterator const_iterator ; ///< container const iterator
199 typedef typename container_type::value_compare key_comparator;
202 container_type m_Set;
205 boost_intrusive_set_adapter()
208 container_type& base_container()
213 template <typename Func>
214 bool insert( value_type& val, Func f )
216 std::pair<iterator, bool> res = m_Set.insert( val );
222 template <typename Func>
223 std::pair<bool, bool> ensure( value_type& val, Func f )
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 bool unlink( value_type& val )
232 iterator it = m_Set.find( value_type(val) );
233 if ( it == m_Set.end() || &(*it) != &val )
239 template <typename Q, typename Func>
240 value_type * erase( Q const& key, Func f )
242 iterator it = m_Set.find( key, key_comparator() );
243 if (it == m_Set.end())
245 value_type& val = *it;
251 template <typename Q, typename Less, typename Func>
252 value_type * erase( Q const& key, Less pred, Func f )
254 iterator it = m_Set.find( key, pred );
255 if (it == m_Set.end())
257 value_type& val = *it;
263 template <typename Q, typename Func>
264 bool find( Q& key, Func f )
266 return find( key, key_comparator(), f );
269 template <typename Q, typename Compare, typename Func>
270 bool find( Q& key, Compare cmp, Func f )
272 iterator it = m_Set.find( key, cmp );
273 if ( it == m_Set.end() )
284 template <typename Disposer>
285 void clear( Disposer disposer )
287 m_Set.clear_and_dispose( disposer );
290 iterator begin() { return m_Set.begin(); }
291 const_iterator begin() const { return m_Set.begin(); }
292 iterator end() { return m_Set.end(); }
293 const_iterator end() const { return m_Set.end(); }
297 return (size_t) m_Set.size();
300 void move_item( boost_intrusive_set_adapter& from, iterator itWhat )
302 value_type& val = *itWhat;
303 from.base_container().erase( itWhat );
304 insert( val, []( value_type& ) {} );
307 } // namespace details
310 } // namespace striped_set
311 }} // namespace cds::intrusive
313 #endif // #ifndef CDSLIB_INTRUSIVE_STRIPED_SET_ADAPTER_H