3 #ifndef CDSLIB_CONTAINER_STRIPED_MAP_STD_LIST_ADAPTER_H
4 #define CDSLIB_CONTAINER_STRIPED_MAP_STD_LIST_ADAPTER_H
7 #include <functional> // ref
8 #include <algorithm> // std::lower_bound
9 #include <utility> // std::pair
10 #include <cds/container/striped_set/adapter.h>
12 #undef CDS_STD_LIST_SIZE_CXX11_CONFORM
13 #if !( defined(__GLIBCXX__ ) && (!defined(_GLIBCXX_USE_CXX11_ABI) || _GLIBCXX_USE_CXX11_ABI == 0 ))
14 # define CDS_STD_LIST_SIZE_CXX11_CONFORM
18 namespace cds { namespace container {
19 namespace striped_set {
21 // Copy policy for map
22 template <typename K, typename T, typename Alloc>
23 struct copy_item_policy< std::list< std::pair< K const, T >, Alloc > >
25 typedef std::pair< K const, T> pair_type;
26 typedef std::list< pair_type, Alloc > list_type;
27 typedef typename list_type::iterator iterator;
29 void operator()( list_type& list, iterator itInsert, iterator itWhat )
31 list.insert( itInsert, *itWhat );
35 // Swap policy for map
36 template <typename K, typename T, typename Alloc>
37 struct swap_item_policy< std::list< std::pair< K const, T >, Alloc > >
39 typedef std::pair< K const, T> pair_type;
40 typedef std::list< pair_type, Alloc > list_type;
41 typedef typename list_type::iterator iterator;
43 void operator()( list_type& list, iterator itInsert, iterator itWhat )
45 pair_type newVal( itWhat->first, typename pair_type::second_type() );
46 itInsert = list.insert( itInsert, newVal );
47 std::swap( itInsert->second, itWhat->second );
51 // Move policy for map
52 template <typename K, typename T, typename Alloc>
53 struct move_item_policy< std::list< std::pair< K const, T >, Alloc > >
55 typedef std::pair< K const, T> pair_type;
56 typedef std::list< 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( itInsert, std::move( *itWhat ) );
64 } // namespace striped_set
65 }} // namespace cds:container
67 namespace cds { namespace intrusive { namespace striped_set {
69 /// std::list adapter for hash map bucket
70 template <typename Key, typename T, class Alloc, typename... Options>
71 class adapt< std::list< std::pair<Key const, T>, Alloc>, Options... >
74 typedef std::list< std::pair<Key const, T>, Alloc> container_type ; ///< underlying container type
77 /// Adapted container type
78 class adapted_container: public cds::container::striped_set::adapted_sequential_container
81 typedef typename container_type::value_type value_type ; ///< value type stored in the container
82 typedef typename value_type::first_type key_type;
83 typedef typename value_type::second_type mapped_type;
84 typedef typename container_type::iterator iterator ; ///< container iterator
85 typedef typename container_type::const_iterator const_iterator ; ///< container const iterator
87 static bool const has_find_with = true;
88 static bool const has_erase_with = true;
92 typedef typename cds::opt::details::make_comparator_from_option_list< value_type, 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 , cds::container::striped_set::move_item, cds::container::striped_set::move_item_policy<container_type>
107 struct find_predicate
109 bool operator()( value_type const& i1, value_type const& i2) const
111 return key_comparator()( i1.first, i2.first ) < 0;
114 template <typename Q>
115 bool operator()( Q const& i1, value_type const& i2) const
117 return key_comparator()( i1, i2.first ) < 0;
120 template <typename Q>
121 bool operator()( value_type const& i1, Q const& i2) const
123 return key_comparator()( i1.first, i2 ) < 0;
130 container_type m_List;
131 # if !defined(CDS_STD_LIST_SIZE_CXX11_CONFORM)
133 // In GCC (at least up to 4.7.x), the complexity of std::list::size() is O(N)
134 // (see http://gcc.gnu.org/bugzilla/show_bug.cgi?id=49561)
136 size_t m_nSize ; // list size
142 # if !defined(CDS_STD_LIST_SIZE_CXX11_CONFORM)
147 template <typename Q, typename Func>
148 bool insert( const Q& key, Func f )
150 iterator it = std::lower_bound( m_List.begin(), m_List.end(), key, find_predicate() );
151 if ( it == m_List.end() || key_comparator()( key, it->first ) != 0 ) {
152 //value_type newItem( key );
153 it = m_List.insert( it, value_type( key, mapped_type()) );
156 # if !defined(CDS_STD_LIST_SIZE_CXX11_CONFORM)
162 // key already exists
166 template <typename K, typename... Args>
167 bool emplace( K&& key, Args&&... args )
169 iterator it = std::lower_bound( m_List.begin(), m_List.end(), key, find_predicate() );
170 if ( it == m_List.end() || key_comparator()( key, it->first ) != 0 ) {
171 //value_type newItem( key );
172 it = m_List.emplace( it, value_type( std::forward<K>(key), std::move( mapped_type( std::forward<Args>(args)...) )) );
174 # if !defined(CDS_STD_LIST_SIZE_CXX11_CONFORM)
182 template <typename Q, typename Func>
183 std::pair<bool, bool> ensure( const Q& key, Func func )
185 iterator it = std::lower_bound( m_List.begin(), m_List.end(), key, find_predicate() );
186 if ( it == m_List.end() || key_comparator()( key, it->first ) != 0 ) {
188 value_type newItem( key, mapped_type() );
189 it = m_List.insert( it, newItem );
191 # if !defined(CDS_STD_LIST_SIZE_CXX11_CONFORM)
194 return std::make_pair( true, true );
199 return std::make_pair( true, false );
203 template <typename Q, typename Func>
204 bool erase( Q const& key, Func f )
206 iterator it = std::lower_bound( m_List.begin(), m_List.end(), key, find_predicate() );
207 if ( it == m_List.end() || key_comparator()( key, it->first ) != 0 )
213 # if !defined(CDS_STD_LIST_SIZE_CXX11_CONFORM)
220 template <typename Q, typename Less, typename Func>
221 bool erase( Q const& key, Less pred, Func f )
223 iterator it = std::lower_bound( m_List.begin(), m_List.end(), key, pred );
224 if ( it == m_List.end() || pred( key, it->first ) || pred( it->first, key ) )
230 # if !defined(CDS_STD_LIST_SIZE_CXX11_CONFORM)
237 template <typename Q, typename Func>
238 bool find( Q& val, Func f )
240 iterator it = std::lower_bound( m_List.begin(), m_List.end(), val, find_predicate() );
241 if ( it == m_List.end() || key_comparator()( val, it->first ) != 0 )
249 template <typename Q, typename Less, typename Func>
250 bool find( Q& val, Less pred, Func f )
252 iterator it = std::lower_bound( m_List.begin(), m_List.end(), val, pred );
253 if ( it == m_List.end() || pred( val, it->first ) || pred( it->first, val ) )
266 iterator begin() { return m_List.begin(); }
267 const_iterator begin() const { return m_List.begin(); }
268 iterator end() { return m_List.end(); }
269 const_iterator end() const { return m_List.end(); }
271 void move_item( adapted_container& /*from*/, iterator itWhat )
273 iterator it = std::lower_bound( m_List.begin(), m_List.end(), *itWhat, find_predicate() );
274 assert( it == m_List.end() || key_comparator()( itWhat->first, it->first ) != 0 );
276 copy_item()( m_List, it, itWhat );
277 # if !defined(CDS_STD_LIST_SIZE_CXX11_CONFORM)
284 # if !defined(CDS_STD_LIST_SIZE_CXX11_CONFORM)
287 return m_List.size();
294 typedef adapted_container type ; ///< Result of \p adapt metafunction
297 }}} // namespace cds::intrusive::striped_set
301 #endif // #ifndef CDSLIB_CONTAINER_STRIPED_MAP_STD_LIST_ADAPTER_H