3 #ifndef CDSLIB_CONTAINER_STRIPED_SET_STD_LIST_ADAPTER_H
4 #define CDSLIB_CONTAINER_STRIPED_SET_STD_LIST_ADAPTER_H
6 #include <functional> // ref
8 #include <algorithm> // std::lower_bound
9 #include <cds/container/striped_set/adapter.h>
12 namespace cds { namespace container {
13 namespace striped_set {
15 // Copy policy for std::list
16 template <typename T, typename Alloc>
17 struct copy_item_policy< std::list< T, Alloc > >
19 typedef std::list< T, Alloc > list_type;
20 typedef typename list_type::iterator iterator;
22 void operator()( list_type& list, iterator itInsert, iterator itWhat )
24 itInsert = list.insert( itInsert, *itWhat );
28 // Swap policy for std::list
29 template <typename T, typename Alloc>
30 struct swap_item_policy< std::list< T, Alloc > >
32 typedef std::list< T, Alloc > list_type;
33 typedef typename list_type::iterator iterator;
35 void operator()( list_type& list, iterator itInsert, iterator itWhat )
37 typename list_type::value_type newVal;
38 itInsert = list.insert( itInsert, newVal );
39 std::swap( *itWhat, *itInsert );
43 // Move policy for std::list
44 template <typename T, typename Alloc>
45 struct move_item_policy< std::list< T, Alloc > >
47 typedef std::list< T, Alloc > list_type;
48 typedef typename list_type::iterator iterator;
50 void operator()( list_type& list, iterator itInsert, iterator itWhat )
52 list.insert( itInsert, std::move( *itWhat ) );
55 } // namespace striped_set
56 }} // namespace cds::container
58 namespace cds { namespace intrusive { namespace striped_set {
60 /// std::list adapter for hash set bucket
61 template <typename T, class Alloc, typename... Options>
62 class adapt< std::list<T, Alloc>, Options... >
65 typedef std::list<T, Alloc> container_type ; ///< underlying container type
68 /// Adapted container type
69 class adapted_container: public cds::container::striped_set::adapted_sequential_container
72 typedef typename container_type::value_type value_type ; ///< value type stored in the container
73 typedef typename container_type::iterator iterator ; ///< container iterator
74 typedef typename container_type::const_iterator const_iterator ; ///< container const iterator
76 static bool const has_find_with = true;
77 static bool const has_erase_with = true;
81 typedef typename cds::opt::details::make_comparator_from_option_list< value_type, Options... >::type key_comparator;
84 typedef typename cds::opt::select<
85 typename cds::opt::value<
86 typename cds::opt::find_option<
87 cds::opt::copy_policy< cds::container::striped_set::move_item >
91 , cds::container::striped_set::copy_item, cds::container::striped_set::copy_item_policy<container_type>
92 , cds::container::striped_set::swap_item, cds::container::striped_set::swap_item_policy<container_type>
93 , cds::container::striped_set::move_item, cds::container::striped_set::move_item_policy<container_type>
98 bool operator()( value_type const& i1, value_type const& i2) const
100 return key_comparator()( i1, i2 ) < 0;
103 template <typename Q>
104 bool operator()( Q const& i1, value_type const& i2) const
106 return key_comparator()( i1, i2 ) < 0;
109 template <typename Q>
110 bool operator()( value_type const& i1, Q const& i2) const
112 return key_comparator()( i1, i2 ) < 0;
119 container_type m_List;
120 # if defined(__GLIBCXX__ ) && !( CDS_COMPILER == CDS_COMPILER_GCC && CDS_COMPILER_VERSION >= 50000 )
122 // In GCC, the complexity of std::list::size() is O(N)
123 // (see http://gcc.gnu.org/bugzilla/show_bug.cgi?id=49561)
125 size_t m_nSize ; // list size
131 # if defined(__GLIBCXX__ ) && !( CDS_COMPILER == CDS_COMPILER_GCC && CDS_COMPILER_VERSION >= 50000 )
136 template <typename Q, typename Func>
137 bool insert( const Q& val, Func f )
139 iterator it = std::lower_bound( m_List.begin(), m_List.end(), val, find_predicate() );
140 if ( it == m_List.end() || key_comparator()( val, *it ) != 0 ) {
141 value_type newItem( val );
142 it = m_List.insert( it, newItem );
145 # if defined(__GLIBCXX__ ) && !( CDS_COMPILER == CDS_COMPILER_GCC && CDS_COMPILER_VERSION >= 50000 )
151 // key already exists
155 template <typename... Args>
156 bool emplace( Args&&... args )
158 value_type val(std::forward<Args>(args)...);
159 iterator it = std::lower_bound( m_List.begin(), m_List.end(), val, find_predicate() );
160 if ( it == m_List.end() || key_comparator()( val, *it ) != 0 ) {
161 it = m_List.emplace( it, std::move( val ) );
162 # if defined(__GLIBCXX__ ) && !( CDS_COMPILER == CDS_COMPILER_GCC && CDS_COMPILER_VERSION >= 50000 )
170 template <typename Q, typename Func>
171 std::pair<bool, bool> ensure( const Q& val, Func func )
173 iterator it = std::lower_bound( m_List.begin(), m_List.end(), val, find_predicate() );
174 if ( it == m_List.end() || key_comparator()( val, *it ) != 0 ) {
176 value_type newItem( val );
177 it = m_List.insert( it, newItem );
178 func( true, *it, val );
179 # if defined(__GLIBCXX__ ) && !( CDS_COMPILER == CDS_COMPILER_GCC && CDS_COMPILER_VERSION >= 50000 )
182 return std::make_pair( true, true );
186 func( false, *it, val );
187 return std::make_pair( true, false );
191 template <typename Q, typename Func>
192 bool erase( const Q& key, Func f )
194 iterator it = std::lower_bound( m_List.begin(), m_List.end(), key, find_predicate() );
195 if ( it == m_List.end() || key_comparator()( key, *it ) != 0 )
201 # if defined(__GLIBCXX__ ) && !( CDS_COMPILER == CDS_COMPILER_GCC && CDS_COMPILER_VERSION >= 50000 )
208 template <typename Q, typename Less, typename Func>
209 bool erase( Q const& key, Less pred, Func f )
211 iterator it = std::lower_bound( m_List.begin(), m_List.end(), key, pred );
212 if ( it == m_List.end() || pred( key, *it ) || pred( *it, key ) )
218 # if defined(__GLIBCXX__ ) && !( CDS_COMPILER == CDS_COMPILER_GCC && CDS_COMPILER_VERSION >= 50000 )
225 template <typename Q, typename Func>
226 bool find( Q& val, Func f )
228 iterator it = std::lower_bound( m_List.begin(), m_List.end(), val, find_predicate() );
229 if ( it == m_List.end() || key_comparator()( val, *it ) != 0 )
237 template <typename Q, typename Less, typename Func>
238 bool find( Q& val, Less pred, Func f )
240 iterator it = std::lower_bound( m_List.begin(), m_List.end(), val, pred );
241 if ( it == m_List.end() || pred( val, *it ) || pred( *it, val ) )
249 /// Clears the container
255 iterator begin() { return m_List.begin(); }
256 const_iterator begin() const { return m_List.begin(); }
257 iterator end() { return m_List.end(); }
258 const_iterator end() const { return m_List.end(); }
260 void move_item( adapted_container& /*from*/, iterator itWhat )
262 iterator it = std::lower_bound( m_List.begin(), m_List.end(), *itWhat, find_predicate() );
263 assert( it == m_List.end() || key_comparator()( *itWhat, *it ) != 0 );
265 copy_item()( m_List, it, itWhat );
266 # if defined(__GLIBCXX__ ) && !( CDS_COMPILER == CDS_COMPILER_GCC && CDS_COMPILER_VERSION >= 50000 )
273 # if defined(__GLIBCXX__ ) && !( CDS_COMPILER == CDS_COMPILER_GCC && CDS_COMPILER_VERSION >= 50000 )
276 return m_List.size();
283 typedef adapted_container type ; ///< Result of \p adapt metafunction
291 #endif // #ifndef CDSLIB_CONTAINER_STRIPED_SET_STD_LIST_ADAPTER_H