2 This file is a part of libcds - Concurrent Data Structures library
4 (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2017
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_CONTAINER_STRIPED_MAP_BOOST_SLIST_ADAPTER_H
32 #define CDSLIB_CONTAINER_STRIPED_MAP_BOOST_SLIST_ADAPTER_H
34 #include <boost/version.hpp>
35 #if BOOST_VERSION < 104800
36 # error "For boost::container::slist you must use boost 1.48 or above"
39 #include <functional> // ref
40 #include <utility> // std::pair
41 #include <cds/container/striped_set/adapter.h>
42 #include <boost/container/slist.hpp>
45 namespace cds { namespace container {
46 namespace striped_set {
48 // Copy policy for map
49 template <typename K, typename T, typename Alloc>
50 struct copy_item_policy< boost::container::slist< std::pair< K const, T >, Alloc > >
52 typedef std::pair< K const, T> pair_type;
53 typedef boost::container::slist< pair_type, Alloc > list_type;
54 typedef typename list_type::iterator iterator;
56 void operator()( list_type& list, iterator itInsert, iterator itWhat )
58 itInsert = list.insert_after( itInsert, *itWhat );
62 // Swap policy for map
63 template <typename K, typename T, typename Alloc>
64 struct swap_item_policy< boost::container::slist< std::pair< K const, T >, Alloc > >
66 typedef std::pair< K const, T> pair_type;
67 typedef boost::container::slist< pair_type, Alloc > list_type;
68 typedef typename list_type::iterator iterator;
70 void operator()( list_type& list, iterator itInsert, iterator itWhat )
72 pair_type newVal( itWhat->first, typename pair_type::mapped_type());
73 itInsert = list.insert_after( itInsert, newVal );
74 std::swap( itInsert->second, itWhat->second );
78 // Move policy for map
79 template <typename K, typename T, typename Alloc>
80 struct move_item_policy< boost::container::slist< std::pair< K const, T >, Alloc > >
82 typedef std::pair< K const, T> pair_type;
83 typedef boost::container::slist< pair_type, Alloc > list_type;
84 typedef typename list_type::iterator iterator;
86 void operator()( list_type& list, iterator itInsert, iterator itWhat )
88 list.insert_after( itInsert, std::move( *itWhat ));
91 } // namespace striped_set
92 }} // namespace cds:container
94 namespace cds { namespace intrusive { namespace striped_set {
96 /// boost::container::slist adapter for hash map bucket
97 template <typename Key, typename T, class Alloc, typename... Options>
98 class adapt< boost::container::slist< std::pair<Key const, T>, Alloc>, Options... >
101 typedef boost::container::slist< std::pair<Key const, T>, Alloc> container_type ; ///< underlying container type
104 /// Adapted container type
105 class adapted_container: public cds::container::striped_set::adapted_sequential_container
108 typedef typename container_type::value_type value_type ; ///< value type stored in the container
109 typedef typename value_type::first_type key_type;
110 typedef typename value_type::second_type mapped_type;
111 typedef typename container_type::iterator iterator ; ///< container iterator
112 typedef typename container_type::const_iterator const_iterator ; ///< container const iterator
114 static bool const has_find_with = true;
115 static bool const has_erase_with = true;
119 typedef typename cds::opt::details::make_comparator_from_option_list< value_type, Options... >::type key_comparator;
121 typedef typename cds::opt::select<
122 typename cds::opt::value<
123 typename cds::opt::find_option<
124 cds::opt::copy_policy< cds::container::striped_set::move_item >
128 , cds::container::striped_set::copy_item, cds::container::striped_set::copy_item_policy<container_type>
129 , cds::container::striped_set::swap_item, cds::container::striped_set::swap_item_policy<container_type>
130 , cds::container::striped_set::move_item, cds::container::striped_set::move_item_policy<container_type>
133 template <typename Q>
134 std::pair< iterator, bool > find_prev_item( Q const& key )
136 iterator itPrev = m_List.before_begin();
137 iterator itEnd = m_List.end();
138 for ( iterator it = m_List.begin(); it != itEnd; ++it ) {
139 int nCmp = key_comparator()( key, it->first );
145 return std::make_pair( itPrev, true );
147 return std::make_pair( itPrev, false );
150 template <typename Q, typename Less>
151 std::pair< iterator, bool > find_prev_item( Q const& key, Less pred )
153 iterator itPrev = m_List.before_begin();
154 iterator itEnd = m_List.end();
155 for ( iterator it = m_List.begin(); it != itEnd; ++it ) {
156 if ( pred( key, it->first ))
158 else if ( pred(it->first, key))
161 return std::make_pair( itPrev, true );
163 return std::make_pair( itPrev, false );
169 container_type m_List;
176 template <typename Q, typename Func>
177 bool insert( const Q& key, Func f )
179 std::pair< iterator, bool > pos = find_prev_item( key );
181 pos.first = m_List.insert_after( pos.first, value_type( key_type( key ), mapped_type()));
186 // key already exists
190 template <typename K, typename... Args>
191 bool emplace( K&& key, Args&&... args )
193 std::pair< iterator, bool > pos = find_prev_item( key );
195 m_List.emplace_after( pos.first, key_type( std::forward<K>( key )), mapped_type( std::forward<Args>( args )... ));
201 template <typename Q, typename Func>
202 std::pair<bool, bool> update( const Q& key, Func func, bool bAllowInsert )
204 std::pair< iterator, bool > pos = find_prev_item( key );
208 return std::make_pair( false, false );
210 pos.first = m_List.insert_after( pos.first, value_type( key_type( key ), mapped_type()));
211 func( true, *pos.first );
212 return std::make_pair( true, true );
216 func( false, *(++pos.first));
217 return std::make_pair( true, false );
221 template <typename Q, typename Func>
222 bool erase( Q const& key, Func f )
224 std::pair< iterator, bool > pos = find_prev_item( key );
229 iterator it = pos.first;
231 m_List.erase_after( pos.first );
236 template <typename Q, typename Less, typename Func>
237 bool erase( Q const& key, Less pred, Func f )
239 std::pair< iterator, bool > pos = find_prev_item( key, pred );
244 iterator it = pos.first;
246 m_List.erase_after( pos.first );
251 template <typename Q, typename Func>
252 bool find( Q& val, Func f )
254 std::pair< iterator, bool > pos = find_prev_item( val );
259 f( *(++pos.first), val );
263 template <typename Q, typename Less, typename Func>
264 bool find( Q& val, Less pred, Func f )
266 std::pair< iterator, bool > pos = find_prev_item( val, pred );
271 f( *(++pos.first), val );
280 iterator begin() { return m_List.begin(); }
281 const_iterator begin() const { return m_List.begin(); }
282 iterator end() { return m_List.end(); }
283 const_iterator end() const { return m_List.end(); }
285 void move_item( adapted_container& /*from*/, iterator itWhat )
287 std::pair< iterator, bool > pos = find_prev_item( itWhat->first );
288 assert( !pos.second );
290 copy_item()( m_List, pos.first, itWhat );
295 return m_List.size();
300 typedef adapted_container type ; ///< Result of \p adapt metafunction
303 }}} // namespace cds::intrusive::striped_set
308 #endif // #ifndef CDSLIB_CONTAINER_STRIPED_MAP_BOOST_SLIST_ADAPTER_H