2 This file is a part of libcds - Concurrent Data Structures library
4 (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016
6 Source code repo: http://github.com/khizmax/libcds/
7 Download: http://sourceforge.net/projects/libcds/files/
9 Redistribution and use in source and binary forms, with or without
10 modification, are permitted provided that the following conditions are met:
12 * Redistributions of source code must retain the above copyright notice, this
13 list of conditions and the following disclaimer.
15 * Redistributions in binary form must reproduce the above copyright notice,
16 this list of conditions and the following disclaimer in the documentation
17 and/or other materials provided with the distribution.
19 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
20 AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
21 IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
22 DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
23 FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
24 DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
25 SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
26 CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
27 OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
28 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
31 #ifndef CDSLIB_INTRUSIVE_STRIPED_SET_ADAPTER_H
32 #define CDSLIB_INTRUSIVE_STRIPED_SET_ADAPTER_H
34 #include <cds/opt/options.h>
35 #include <cds/intrusive/striped_set/resizing_policy.h>
36 #include <cds/opt/hash.h>
37 #include <cds/opt/compare.h> // cds::opt::details::make_comparator - for some adapt specializations
39 namespace cds { namespace intrusive {
41 /// StripedSet related definitions
42 namespace striped_set {
43 /// Default adapter for intrusive striped/refinable hash set
45 By default, the metafunction does not make any transformation for container type \p Container.
46 \p Container should provide interface suitable for the hash set.
48 The \p Options template argument contains option pack
49 that will be passed to \p cds::intrusive::StripedSet.
51 <b>Bucket interface</b>
53 The result of metafunction is a container (a bucket) that should support the following interface:
55 Public typedefs that the bucket should provide:
56 - \p value_type - the type of the item in the bucket
57 - \p iterator - bucket's item iterator
58 - \p const_iterator - bucket's item constant iterator
59 - \p default_resizing_policy - default resizing policy preferable for the container.
60 By default, the library defines cds::container::striped_set::load_factor_resizing<4> for sequential containers like
61 boost::intrusive::list, and cds::container::striped_set::no_resizing for ordered container like boost::intrusive::set.
63 <b>Insert value \p val of type \p Q</b>
64 \code template <typename Func> bool insert( value_type& val, Func f ) ; \endcode
65 Inserts \p val into the container and, if inserting is successful, calls functor \p f
68 The functor signature is:
71 void operator()( value_type& item );
74 where \p item is the item inserted.
76 The user-defined functor \p f is called only if the inserting is success.
79 <b>Updates the item in the container</b>
80 \code template <typename Func> std::pair<bool, bool> update( value_type& val, Func f, bool bAllowInsert = true ) \endcode
81 The operation performs inserting or changing data.
83 If the \p val key not found in the container, then \p val is inserted iff \p bAllowInsert is \p true.
84 Otherwise, the functor \p f is called with the item found.
86 The \p Func functor has the following interface:
88 void func( bool bNew, value_type& item, value_type& val );
93 void operator()( bool bNew, value_type& item, value_type& val );
98 - \p bNew - \p true if the item has been inserted, \p false otherwise
99 - \p item - container's item
100 - \p val - argument \p val passed into the \p update() function
102 If \p val has been inserted (i.e. <tt>bNew == true</tt>) then \p item and \p val
103 are the same element: <tt>&item == &val</tt>. Otherwise, they are different.
105 The functor can change non-key fields of the \p item.
107 Returns <tt> std::pair<bool, bool> </tt> where \p first is true if operation is successfull,
108 \p second is true if new item has been added or \p false if the item with \p val key
112 <b>Unlink an item</b>
113 \code bool unlink( value_type& val ) \endcode
114 Unlink \p val from the container if \p val belongs to it.
118 \code template <typename Q, typename Func> bool erase( Q const& key, Func f ) \endcode
119 The function searches an item with key \p key, calls \p f functor
120 and erases the item. If \p key is not found, the functor is not called.
122 The functor \p Func interface is:
125 void operator()(value_type& val);
129 The type \p Q can differ from \ref value_type of items storing in the container.
130 Therefore, the \p value_type should be comparable with type \p Q.
132 Return \p true if key is found and deleted, \p false otherwise
136 <b>Find the key \p val </b>
138 template <typename Q, typename Func> bool find( Q& val, Func f )
139 template <typename Q, typename Compare, typename Func> bool find( Q& val, Compare cmp, Func f )
141 The function searches the item with key equal to \p val and calls the functor \p f for item found.
142 The interface of \p Func functor is:
145 void operator()( value_type& item, Q& val );
148 where \p item is the item found, \p val is the <tt>find</tt> function argument.
150 The functor can change non-key fields of \p item.
151 The \p val argument may be non-const since it can be used as \p f functor destination i.e., the functor
152 can modify both arguments.
154 The type \p Q can differ from \ref value_type of items storing in the container.
155 Therefore, the \p value_type should be comparable with type \p Q.
157 The first form uses default \p compare function used for key ordering.
158 The second form allows to point specific \p Compare functor \p cmp
159 that can compare \p value_typwe and \p Q type. The interface of \p Compare is the same as \p std::less.
161 The function returns \p true if \p val is found, \p false otherwise.
164 <b>Clears the container</b>
167 template <typename Disposer> void clear( Disposer disposer )
169 Second form calls \p disposer for each item in the container before clearing.
172 <b>Get size of bucket</b>
173 \code size_t size() const \endcode
174 This function may be required by some resizing policy
180 const_iterator begin() const;
182 const_iterator end() const;
186 <b>Move item when resizing</b>
187 \code void move_item( adapted_container& from, iterator it ) \endcode
188 This helper function is invented for the set resizing when the item
189 pointed by \p it iterator is copied from old bucket \p from to a new bucket
194 template < typename Container, typename... Options >
198 typedef Container type ; ///< adapted container type
199 typedef typename type::value_type value_type ; ///< value type stored in the container
203 struct adapted_sequential_container
205 typedef striped_set::load_factor_resizing<4> default_resizing_policy;
208 struct adapted_container
210 typedef striped_set::no_resizing default_resizing_policy;
216 template <typename Set>
217 class boost_intrusive_set_adapter: public cds::intrusive::striped_set::adapted_container
220 typedef Set container_type;
222 typedef typename container_type::value_type value_type ; ///< value type stored in the container
223 typedef typename container_type::iterator iterator ; ///< container iterator
224 typedef typename container_type::const_iterator const_iterator ; ///< container const iterator
226 typedef typename container_type::key_compare key_comparator;
229 container_type m_Set;
232 boost_intrusive_set_adapter()
235 container_type& base_container()
240 template <typename Func>
241 bool insert( value_type& val, Func f )
243 std::pair<iterator, bool> res = m_Set.insert( val );
249 template <typename Func>
250 std::pair<bool, bool> update( value_type& val, Func f, bool bAllowInsert )
252 if ( bAllowInsert ) {
253 std::pair<iterator, bool> res = m_Set.insert( val );
254 f( res.second, *res.first, val );
255 return std::make_pair( true, res.second );
258 auto it = m_Set.find( val, key_comparator() );
259 if ( it == m_Set.end() )
260 return std::make_pair( false, false );
261 f( false, *it, val );
262 return std::make_pair( true, false );
266 bool unlink( value_type& val )
268 iterator it = m_Set.find( val, key_comparator() );
269 if ( it == m_Set.end() || &(*it) != &val )
275 template <typename Q, typename Func>
276 value_type * erase( Q const& key, Func f )
278 iterator it = m_Set.find( key, key_comparator() );
279 if (it == m_Set.end())
281 value_type& val = *it;
287 template <typename Q, typename Less, typename Func>
288 value_type * erase( Q const& key, Less pred, Func f )
290 iterator it = m_Set.find( key, pred );
291 if (it == m_Set.end())
293 value_type& val = *it;
299 template <typename Q, typename Func>
300 bool find( Q const& key, Func f )
302 return find( key, key_comparator(), f );
305 template <typename Q, typename Compare, typename Func>
306 bool find( Q const& key, Compare cmp, Func f )
308 iterator it = m_Set.find( key, cmp );
309 if ( it == m_Set.end() )
320 template <typename Disposer>
321 void clear( Disposer disposer )
323 m_Set.clear_and_dispose( disposer );
326 iterator begin() { return m_Set.begin(); }
327 const_iterator begin() const { return m_Set.begin(); }
328 iterator end() { return m_Set.end(); }
329 const_iterator end() const { return m_Set.end(); }
333 return (size_t) m_Set.size();
336 void move_item( boost_intrusive_set_adapter& from, iterator itWhat )
338 value_type& val = *itWhat;
339 from.base_container().erase( itWhat );
340 insert( val, []( value_type& ) {} );
343 } // namespace details
346 } // namespace striped_set
347 }} // namespace cds::intrusive
349 #endif // #ifndef CDSLIB_INTRUSIVE_STRIPED_SET_ADAPTER_H