3 #ifndef __CDS_CONTAINER_STRIPED_MAP_BOOST_SLIST_ADAPTER_H
4 #define __CDS_CONTAINER_STRIPED_MAP_BOOST_SLIST_ADAPTER_H
6 #include <boost/version.hpp>
7 #if BOOST_VERSION < 104800
8 # error "For boost::container::slist you must use boost 1.48 or above"
11 #include <cds/container/striped_set/adapter.h>
13 #include <boost/container/slist.hpp>
14 #include <utility> // std::pair
17 namespace cds { namespace container {
18 namespace striped_set {
20 // Copy policy for map
21 template <typename K, typename T, typename Alloc>
22 struct copy_item_policy< boost::container::slist< std::pair< K const, T >, Alloc > >
24 typedef std::pair< K const, T> pair_type;
25 typedef boost::container::slist< pair_type, Alloc > list_type;
26 typedef typename list_type::iterator iterator;
28 void operator()( list_type& list, iterator itInsert, iterator itWhat )
30 itInsert = list.insert_after( itInsert, *itWhat );
34 // Swap policy for map
35 template <typename K, typename T, typename Alloc>
36 struct swap_item_policy< boost::container::slist< std::pair< K const, T >, Alloc > >
38 typedef std::pair< K const, T> pair_type;
39 typedef boost::container::slist< pair_type, Alloc > list_type;
40 typedef typename list_type::iterator iterator;
42 void operator()( list_type& list, iterator itInsert, iterator itWhat )
44 pair_type newVal( itWhat->first, typename pair_type::mapped_type() );
45 itInsert = list.insert_after( itInsert, newVal );
46 std::swap( itInsert->second, itWhat->second );
50 #ifdef CDS_MOVE_SEMANTICS_SUPPORT
51 // Move policy for map
52 template <typename K, typename T, typename Alloc>
53 struct move_item_policy< boost::container::slist< std::pair< K const, T >, Alloc > >
55 typedef std::pair< K const, T> pair_type;
56 typedef boost::container::slist< pair_type, Alloc > list_type;
57 typedef typename list_type::iterator iterator;
59 void operator()( list_type& list, iterator itInsert, iterator itWhat )
61 list.insert_after( itInsert, std::move( *itWhat ) );
65 } // namespace striped_set
66 }} // namespace cds:container
68 namespace cds { namespace intrusive { namespace striped_set {
70 /// boost::container::slist adapter for hash map bucket
71 template <typename Key, typename T, class Alloc, CDS_SPEC_OPTIONS>
72 class adapt< boost::container::slist< std::pair<Key const, T>, Alloc>, CDS_OPTIONS >
75 typedef boost::container::slist< std::pair<Key const, T>, Alloc> container_type ; ///< underlying container type
78 /// Adapted container type
79 class adapted_container: public cds::container::striped_set::adapted_sequential_container
82 typedef typename container_type::value_type value_type ; ///< value type stored in the container
83 typedef typename value_type::first_type key_type;
84 typedef typename value_type::second_type mapped_type;
85 typedef typename container_type::iterator iterator ; ///< container iterator
86 typedef typename container_type::const_iterator const_iterator ; ///< container const iterator
88 static bool const has_find_with = true;
89 static bool const has_erase_with = true;
93 typedef typename cds::opt::details::make_comparator_from_option_list< value_type, CDS_OPTIONS >::type key_comparator;
95 typedef typename cds::opt::select<
96 typename cds::opt::value<
97 typename cds::opt::find_option<
98 cds::opt::copy_policy< cds::container::striped_set::move_item >
102 , cds::container::striped_set::copy_item, cds::container::striped_set::copy_item_policy<container_type>
103 , cds::container::striped_set::swap_item, cds::container::striped_set::swap_item_policy<container_type>
104 #ifdef CDS_MOVE_SEMANTICS_SUPPORT
105 , cds::container::striped_set::move_item, cds::container::striped_set::move_item_policy<container_type>
109 template <typename Q>
110 std::pair< iterator, bool > find_prev_item( Q const& key )
112 iterator itPrev = m_List.before_begin();
113 iterator itEnd = m_List.end();
114 for ( iterator it = m_List.begin(); it != itEnd; ++it ) {
115 int nCmp = key_comparator()( key, it->first );
121 return std::make_pair( itPrev, true );
123 return std::make_pair( itPrev, false );
126 template <typename Q, typename Less>
127 std::pair< iterator, bool > find_prev_item( Q const& key, Less pred )
129 iterator itPrev = m_List.before_begin();
130 iterator itEnd = m_List.end();
131 for ( iterator it = m_List.begin(); it != itEnd; ++it ) {
132 if ( pred( key, it->first ))
134 else if ( pred(it->first, key))
137 return std::make_pair( itPrev, true );
139 return std::make_pair( itPrev, false );
145 container_type m_List;
152 template <typename Q, typename Func>
153 bool insert( const Q& key, Func f )
155 std::pair< iterator, bool > pos = find_prev_item( key );
157 value_type newItem( key, mapped_type() );
158 pos.first = m_List.insert_after( pos.first, newItem );
159 cds::unref( f )( *pos.first );
163 // key already exists
167 # ifdef CDS_EMPLACE_SUPPORT
168 template <typename K, typename... Args>
169 bool emplace( K&& key, Args&&... args )
171 std::pair< iterator, bool > pos = find_prev_item( key );
173 m_List.emplace_after( pos.first, std::forward<K>(key), std::move( mapped_type( std::forward<Args>(args)... )));
180 template <typename Q, typename Func>
181 std::pair<bool, bool> ensure( const Q& key, Func func )
183 std::pair< iterator, bool > pos = find_prev_item( key );
186 value_type newItem( key, mapped_type() );
187 pos.first = m_List.insert_after( pos.first, newItem );
188 cds::unref( func )( true, *pos.first );
189 return std::make_pair( true, true );
193 cds::unref( func )( false, *(++pos.first) );
194 return std::make_pair( true, false );
198 template <typename Q, typename Func>
199 bool erase( Q const& key, Func f )
201 std::pair< iterator, bool > pos = find_prev_item( key );
206 iterator it = pos.first;
207 cds::unref( f )( *(++it) );
208 m_List.erase_after( pos.first );
213 template <typename Q, typename Less, typename Func>
214 bool erase( Q const& key, Less pred, Func f )
216 std::pair< iterator, bool > pos = find_prev_item( key, pred );
221 iterator it = pos.first;
222 cds::unref( f )( *(++it) );
223 m_List.erase_after( pos.first );
228 template <typename Q, typename Func>
229 bool find( Q& val, Func f )
231 std::pair< iterator, bool > pos = find_prev_item( val );
236 cds::unref( f )( *(++pos.first), val );
240 template <typename Q, typename Less, typename Func>
241 bool find( Q& val, Less pred, Func f )
243 std::pair< iterator, bool > pos = find_prev_item( val, pred );
248 cds::unref( f )( *(++pos.first), val );
257 iterator begin() { return m_List.begin(); }
258 const_iterator begin() const { return m_List.begin(); }
259 iterator end() { return m_List.end(); }
260 const_iterator end() const { return m_List.end(); }
262 void move_item( adapted_container& /*from*/, iterator itWhat )
264 std::pair< iterator, bool > pos = find_prev_item( itWhat->first );
265 assert( !pos.second );
267 copy_item()( m_List, pos.first, itWhat );
272 return m_List.size();
277 typedef adapted_container type ; ///< Result of \p adapt metafunction
280 }}} // namespace cds::intrusive::striped_set
285 #endif // #ifndef __CDS_CONTAINER_STRIPED_MAP_BOOST_SLIST_ADAPTER_H