3 #ifndef __CDS_CONTAINER_STRIPED_MAP_STD_LIST_ADAPTER_H
4 #define __CDS_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>
13 namespace cds { namespace container {
14 namespace striped_set {
16 // Copy policy for map
17 template <typename K, typename T, typename Alloc>
18 struct copy_item_policy< std::list< std::pair< K const, T >, Alloc > >
20 typedef std::pair< K const, T> pair_type;
21 typedef std::list< pair_type, Alloc > list_type;
22 typedef typename list_type::iterator iterator;
24 void operator()( list_type& list, iterator itInsert, iterator itWhat )
26 list.insert( itInsert, *itWhat );
30 // Swap policy for map
31 template <typename K, typename T, typename Alloc>
32 struct swap_item_policy< std::list< std::pair< K const, T >, Alloc > >
34 typedef std::pair< K const, T> pair_type;
35 typedef std::list< pair_type, Alloc > list_type;
36 typedef typename list_type::iterator iterator;
38 void operator()( list_type& list, iterator itInsert, iterator itWhat )
40 pair_type newVal( itWhat->first, typename pair_type::second_type() );
41 itInsert = list.insert( itInsert, newVal );
42 std::swap( itInsert->second, itWhat->second );
46 // Move policy for map
47 template <typename K, typename T, typename Alloc>
48 struct move_item_policy< std::list< std::pair< K const, T >, Alloc > >
50 typedef std::pair< K const, T> pair_type;
51 typedef std::list< pair_type, Alloc > list_type;
52 typedef typename list_type::iterator iterator;
54 void operator()( list_type& list, iterator itInsert, iterator itWhat )
56 list.insert( itInsert, std::move( *itWhat ) );
59 } // namespace striped_set
60 }} // namespace cds:container
62 namespace cds { namespace intrusive { namespace striped_set {
64 /// std::list adapter for hash map bucket
65 template <typename Key, typename T, class Alloc, typename... Options>
66 class adapt< std::list< std::pair<Key const, T>, Alloc>, Options... >
69 typedef std::list< std::pair<Key const, T>, Alloc> container_type ; ///< underlying container type
72 /// Adapted container type
73 class adapted_container: public cds::container::striped_set::adapted_sequential_container
76 typedef typename container_type::value_type value_type ; ///< value type stored in the container
77 typedef typename value_type::first_type key_type;
78 typedef typename value_type::second_type mapped_type;
79 typedef typename container_type::iterator iterator ; ///< container iterator
80 typedef typename container_type::const_iterator const_iterator ; ///< container const iterator
82 static bool const has_find_with = true;
83 static bool const has_erase_with = true;
87 typedef typename cds::opt::details::make_comparator_from_option_list< value_type, Options... >::type key_comparator;
90 typedef typename cds::opt::select<
91 typename cds::opt::value<
92 typename cds::opt::find_option<
93 cds::opt::copy_policy< cds::container::striped_set::move_item >
97 , cds::container::striped_set::copy_item, cds::container::striped_set::copy_item_policy<container_type>
98 , cds::container::striped_set::swap_item, cds::container::striped_set::swap_item_policy<container_type>
99 , cds::container::striped_set::move_item, cds::container::striped_set::move_item_policy<container_type>
102 struct find_predicate
104 bool operator()( value_type const& i1, value_type const& i2) const
106 return key_comparator()( i1.first, i2.first ) < 0;
109 template <typename Q>
110 bool operator()( Q const& i1, value_type const& i2) const
112 return key_comparator()( i1, i2.first ) < 0;
115 template <typename Q>
116 bool operator()( value_type const& i1, Q const& i2) const
118 return key_comparator()( i1.first, i2 ) < 0;
125 container_type m_List;
126 # if defined(__GLIBCXX__ ) && !( CDS_COMPILER == CDS_COMPILER_GCC && CDS_COMPILER_VERSION >= 50000 )
128 // In GCC (at least up to 4.7.x), the complexity of std::list::size() is O(N)
129 // (see http://gcc.gnu.org/bugzilla/show_bug.cgi?id=49561)
131 size_t m_nSize ; // list size
137 # if defined(__GLIBCXX__ ) && !( CDS_COMPILER == CDS_COMPILER_GCC && CDS_COMPILER_VERSION >= 50000 )
142 template <typename Q, typename Func>
143 bool insert( const Q& key, Func f )
145 iterator it = std::lower_bound( m_List.begin(), m_List.end(), key, find_predicate() );
146 if ( it == m_List.end() || key_comparator()( key, it->first ) != 0 ) {
147 //value_type newItem( key );
148 it = m_List.insert( it, value_type( key, mapped_type()) );
151 # if defined(__GLIBCXX__ ) && !( CDS_COMPILER == CDS_COMPILER_GCC && CDS_COMPILER_VERSION >= 50000 )
157 // key already exists
161 template <typename K, typename... Args>
162 bool emplace( K&& key, Args&&... args )
164 iterator it = std::lower_bound( m_List.begin(), m_List.end(), key, find_predicate() );
165 if ( it == m_List.end() || key_comparator()( key, it->first ) != 0 ) {
166 //value_type newItem( key );
167 it = m_List.emplace( it, value_type( std::forward<K>(key), std::move( mapped_type( std::forward<Args>(args)...) )) );
169 # if defined(__GLIBCXX__ ) && !( CDS_COMPILER == CDS_COMPILER_GCC && CDS_COMPILER_VERSION >= 50000 )
177 template <typename Q, typename Func>
178 std::pair<bool, bool> ensure( const Q& key, Func func )
180 iterator it = std::lower_bound( m_List.begin(), m_List.end(), key, find_predicate() );
181 if ( it == m_List.end() || key_comparator()( key, it->first ) != 0 ) {
183 value_type newItem( key, mapped_type() );
184 it = m_List.insert( it, newItem );
186 # if defined(__GLIBCXX__ ) && !( CDS_COMPILER == CDS_COMPILER_GCC && CDS_COMPILER_VERSION >= 50000 )
189 return std::make_pair( true, true );
194 return std::make_pair( true, false );
198 template <typename Q, typename Func>
199 bool erase( Q const& key, Func f )
201 iterator it = std::lower_bound( m_List.begin(), m_List.end(), key, find_predicate() );
202 if ( it == m_List.end() || key_comparator()( key, it->first ) != 0 )
208 # if defined(__GLIBCXX__ ) && !( CDS_COMPILER == CDS_COMPILER_GCC && CDS_COMPILER_VERSION >= 50000 )
215 template <typename Q, typename Less, typename Func>
216 bool erase( Q const& key, Less pred, Func f )
218 iterator it = std::lower_bound( m_List.begin(), m_List.end(), key, pred );
219 if ( it == m_List.end() || pred( key, it->first ) || pred( it->first, key ) )
225 # if defined(__GLIBCXX__ ) && !( CDS_COMPILER == CDS_COMPILER_GCC && CDS_COMPILER_VERSION >= 50000 )
232 template <typename Q, typename Func>
233 bool find( Q& val, Func f )
235 iterator it = std::lower_bound( m_List.begin(), m_List.end(), val, find_predicate() );
236 if ( it == m_List.end() || key_comparator()( val, it->first ) != 0 )
244 template <typename Q, typename Less, typename Func>
245 bool find( Q& val, Less pred, Func f )
247 iterator it = std::lower_bound( m_List.begin(), m_List.end(), val, pred );
248 if ( it == m_List.end() || pred( val, it->first ) || pred( it->first, val ) )
261 iterator begin() { return m_List.begin(); }
262 const_iterator begin() const { return m_List.begin(); }
263 iterator end() { return m_List.end(); }
264 const_iterator end() const { return m_List.end(); }
266 void move_item( adapted_container& /*from*/, iterator itWhat )
268 iterator it = std::lower_bound( m_List.begin(), m_List.end(), *itWhat, find_predicate() );
269 assert( it == m_List.end() || key_comparator()( itWhat->first, it->first ) != 0 );
271 copy_item()( m_List, it, itWhat );
272 # if defined(__GLIBCXX__ ) && !( CDS_COMPILER == CDS_COMPILER_GCC && CDS_COMPILER_VERSION >= 50000 )
279 # if defined(__GLIBCXX__ ) && !( CDS_COMPILER == CDS_COMPILER_GCC && CDS_COMPILER_VERSION >= 50000 )
282 return m_List.size();
289 typedef adapted_container type ; ///< Result of \p adapt metafunction
292 }}} // namespace cds::intrusive::striped_set
296 #endif // #ifndef __CDS_CONTAINER_STRIPED_MAP_STD_LIST_ADAPTER_H