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 // Move policy for map
51 template <typename K, typename T, typename Alloc>
52 struct move_item_policy< boost::container::slist< std::pair< K const, T >, Alloc > >
54 typedef std::pair< K const, T> pair_type;
55 typedef boost::container::slist< pair_type, Alloc > list_type;
56 typedef typename list_type::iterator iterator;
58 void operator()( list_type& list, iterator itInsert, iterator itWhat )
60 list.insert_after( itInsert, std::move( *itWhat ) );
63 } // namespace striped_set
64 }} // namespace cds:container
66 namespace cds { namespace intrusive { namespace striped_set {
68 /// boost::container::slist adapter for hash map bucket
69 template <typename Key, typename T, class Alloc, typename... Options>
70 class adapt< boost::container::slist< std::pair<Key const, T>, Alloc>, Options... >
73 typedef boost::container::slist< std::pair<Key const, T>, Alloc> container_type ; ///< underlying container type
76 /// Adapted container type
77 class adapted_container: public cds::container::striped_set::adapted_sequential_container
80 typedef typename container_type::value_type value_type ; ///< value type stored in the container
81 typedef typename value_type::first_type key_type;
82 typedef typename value_type::second_type mapped_type;
83 typedef typename container_type::iterator iterator ; ///< container iterator
84 typedef typename container_type::const_iterator const_iterator ; ///< container const iterator
86 static bool const has_find_with = true;
87 static bool const has_erase_with = true;
91 typedef typename cds::opt::details::make_comparator_from_option_list< value_type, Options... >::type key_comparator;
93 typedef typename cds::opt::select<
94 typename cds::opt::value<
95 typename cds::opt::find_option<
96 cds::opt::copy_policy< cds::container::striped_set::move_item >
100 , cds::container::striped_set::copy_item, cds::container::striped_set::copy_item_policy<container_type>
101 , cds::container::striped_set::swap_item, cds::container::striped_set::swap_item_policy<container_type>
102 , cds::container::striped_set::move_item, cds::container::striped_set::move_item_policy<container_type>
105 template <typename Q>
106 std::pair< iterator, bool > find_prev_item( Q const& key )
108 iterator itPrev = m_List.before_begin();
109 iterator itEnd = m_List.end();
110 for ( iterator it = m_List.begin(); it != itEnd; ++it ) {
111 int nCmp = key_comparator()( key, it->first );
117 return std::make_pair( itPrev, true );
119 return std::make_pair( itPrev, false );
122 template <typename Q, typename Less>
123 std::pair< iterator, bool > find_prev_item( Q const& key, Less pred )
125 iterator itPrev = m_List.before_begin();
126 iterator itEnd = m_List.end();
127 for ( iterator it = m_List.begin(); it != itEnd; ++it ) {
128 if ( pred( key, it->first ))
130 else if ( pred(it->first, key))
133 return std::make_pair( itPrev, true );
135 return std::make_pair( itPrev, false );
141 container_type m_List;
148 template <typename Q, typename Func>
149 bool insert( const Q& key, Func f )
151 std::pair< iterator, bool > pos = find_prev_item( key );
153 value_type newItem( key, mapped_type() );
154 pos.first = m_List.insert_after( pos.first, newItem );
155 cds::unref( f )( *pos.first );
159 // key already exists
163 template <typename K, typename... Args>
164 bool emplace( K&& key, Args&&... args )
166 std::pair< iterator, bool > pos = find_prev_item( key );
168 m_List.emplace_after( pos.first, std::forward<K>(key), std::move( mapped_type( std::forward<Args>(args)... )));
174 template <typename Q, typename Func>
175 std::pair<bool, bool> ensure( const Q& key, Func func )
177 std::pair< iterator, bool > pos = find_prev_item( key );
180 value_type newItem( key, mapped_type() );
181 pos.first = m_List.insert_after( pos.first, newItem );
182 cds::unref( func )( true, *pos.first );
183 return std::make_pair( true, true );
187 cds::unref( func )( false, *(++pos.first) );
188 return std::make_pair( true, false );
192 template <typename Q, typename Func>
193 bool erase( Q const& key, Func f )
195 std::pair< iterator, bool > pos = find_prev_item( key );
200 iterator it = pos.first;
201 cds::unref( f )( *(++it) );
202 m_List.erase_after( pos.first );
207 template <typename Q, typename Less, typename Func>
208 bool erase( Q const& key, Less pred, Func f )
210 std::pair< iterator, bool > pos = find_prev_item( key, pred );
215 iterator it = pos.first;
216 cds::unref( f )( *(++it) );
217 m_List.erase_after( pos.first );
222 template <typename Q, typename Func>
223 bool find( Q& val, Func f )
225 std::pair< iterator, bool > pos = find_prev_item( val );
230 cds::unref( f )( *(++pos.first), val );
234 template <typename Q, typename Less, typename Func>
235 bool find( Q& val, Less pred, Func f )
237 std::pair< iterator, bool > pos = find_prev_item( val, pred );
242 cds::unref( f )( *(++pos.first), val );
251 iterator begin() { return m_List.begin(); }
252 const_iterator begin() const { return m_List.begin(); }
253 iterator end() { return m_List.end(); }
254 const_iterator end() const { return m_List.end(); }
256 void move_item( adapted_container& /*from*/, iterator itWhat )
258 std::pair< iterator, bool > pos = find_prev_item( itWhat->first );
259 assert( !pos.second );
261 copy_item()( m_List, pos.first, itWhat );
266 return m_List.size();
271 typedef adapted_container type ; ///< Result of \p adapt metafunction
274 }}} // namespace cds::intrusive::striped_set
279 #endif // #ifndef __CDS_CONTAINER_STRIPED_MAP_BOOST_SLIST_ADAPTER_H