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>
11 #undef CDS_STD_LIST_SIZE_CXX11_CONFORM
12 #if !( defined(__GLIBCXX__ ) && (!defined(_GLIBCXX_USE_CXX11_ABI) || _GLIBCXX_USE_CXX11_ABI == 0 ))
13 # define CDS_STD_LIST_SIZE_CXX11_CONFORM
17 namespace cds { namespace container {
18 namespace striped_set {
20 // Copy policy for std::list
21 template <typename T, typename Alloc>
22 struct copy_item_policy< std::list< T, Alloc > >
24 typedef std::list< T, Alloc > list_type;
25 typedef typename list_type::iterator iterator;
27 void operator()( list_type& list, iterator itInsert, iterator itWhat )
29 itInsert = list.insert( itInsert, *itWhat );
33 // Swap policy for std::list
34 template <typename T, typename Alloc>
35 struct swap_item_policy< std::list< T, Alloc > >
37 typedef std::list< T, Alloc > list_type;
38 typedef typename list_type::iterator iterator;
40 void operator()( list_type& list, iterator itInsert, iterator itWhat )
42 typename list_type::value_type newVal;
43 itInsert = list.insert( itInsert, newVal );
44 std::swap( *itWhat, *itInsert );
48 // Move policy for std::list
49 template <typename T, typename Alloc>
50 struct move_item_policy< std::list< T, Alloc > >
52 typedef std::list< T, Alloc > list_type;
53 typedef typename list_type::iterator iterator;
55 void operator()( list_type& list, iterator itInsert, iterator itWhat )
57 list.insert( itInsert, std::move( *itWhat ) );
60 } // namespace striped_set
61 }} // namespace cds::container
63 namespace cds { namespace intrusive { namespace striped_set {
65 /// std::list adapter for hash set bucket
66 template <typename T, class Alloc, typename... Options>
67 class adapt< std::list<T, Alloc>, Options... >
70 typedef std::list<T, Alloc> container_type ; ///< underlying container type
73 /// Adapted container type
74 class adapted_container: public cds::container::striped_set::adapted_sequential_container
77 typedef typename container_type::value_type value_type ; ///< value type stored in the container
78 typedef typename container_type::iterator iterator ; ///< container iterator
79 typedef typename container_type::const_iterator const_iterator ; ///< container const iterator
81 static bool const has_find_with = true;
82 static bool const has_erase_with = true;
86 typedef typename cds::opt::details::make_comparator_from_option_list< value_type, Options... >::type key_comparator;
89 typedef typename cds::opt::select<
90 typename cds::opt::value<
91 typename cds::opt::find_option<
92 cds::opt::copy_policy< cds::container::striped_set::move_item >
96 , cds::container::striped_set::copy_item, cds::container::striped_set::copy_item_policy<container_type>
97 , cds::container::striped_set::swap_item, cds::container::striped_set::swap_item_policy<container_type>
98 , cds::container::striped_set::move_item, cds::container::striped_set::move_item_policy<container_type>
101 struct find_predicate
103 bool operator()( value_type const& i1, value_type const& i2) const
105 return key_comparator()( i1, i2 ) < 0;
108 template <typename Q>
109 bool operator()( Q const& i1, value_type const& i2) const
111 return key_comparator()( i1, i2 ) < 0;
114 template <typename Q>
115 bool operator()( value_type const& i1, Q const& i2) const
117 return key_comparator()( i1, i2 ) < 0;
124 container_type m_List;
125 # if !defined(CDS_STD_LIST_SIZE_CXX11_CONFORM)
127 // In GCC, the complexity of std::list::size() is O(N)
128 // (see http://gcc.gnu.org/bugzilla/show_bug.cgi?id=49561)
130 size_t m_nSize ; // list size
136 # if !defined(CDS_STD_LIST_SIZE_CXX11_CONFORM)
141 template <typename Q, typename Func>
142 bool insert( const Q& val, Func f )
144 iterator it = std::lower_bound( m_List.begin(), m_List.end(), val, find_predicate() );
145 if ( it == m_List.end() || key_comparator()( val, *it ) != 0 ) {
146 value_type newItem( val );
147 it = m_List.insert( it, newItem );
150 # if !defined(CDS_STD_LIST_SIZE_CXX11_CONFORM)
156 // key already exists
160 template <typename... Args>
161 bool emplace( Args&&... args )
163 value_type val(std::forward<Args>(args)...);
164 iterator it = std::lower_bound( m_List.begin(), m_List.end(), val, find_predicate() );
165 if ( it == m_List.end() || key_comparator()( val, *it ) != 0 ) {
166 it = m_List.emplace( it, std::move( val ) );
167 # if !defined(CDS_STD_LIST_SIZE_CXX11_CONFORM)
175 template <typename Q, typename Func>
176 std::pair<bool, bool> ensure( const Q& val, Func func )
178 iterator it = std::lower_bound( m_List.begin(), m_List.end(), val, find_predicate() );
179 if ( it == m_List.end() || key_comparator()( val, *it ) != 0 ) {
181 value_type newItem( val );
182 it = m_List.insert( it, newItem );
183 func( true, *it, val );
184 # if !defined(CDS_STD_LIST_SIZE_CXX11_CONFORM)
187 return std::make_pair( true, true );
191 func( false, *it, val );
192 return std::make_pair( true, false );
196 template <typename Q, typename Func>
197 bool erase( const Q& key, Func f )
199 iterator it = std::lower_bound( m_List.begin(), m_List.end(), key, find_predicate() );
200 if ( it == m_List.end() || key_comparator()( key, *it ) != 0 )
206 # if !defined(CDS_STD_LIST_SIZE_CXX11_CONFORM)
213 template <typename Q, typename Less, typename Func>
214 bool erase( Q const& key, Less pred, Func f )
216 iterator it = std::lower_bound( m_List.begin(), m_List.end(), key, pred );
217 if ( it == m_List.end() || pred( key, *it ) || pred( *it, key ) )
223 # if !defined(CDS_STD_LIST_SIZE_CXX11_CONFORM)
230 template <typename Q, typename Func>
231 bool find( Q& val, Func f )
233 iterator it = std::lower_bound( m_List.begin(), m_List.end(), val, find_predicate() );
234 if ( it == m_List.end() || key_comparator()( val, *it ) != 0 )
242 template <typename Q, typename Less, typename Func>
243 bool find( Q& val, Less pred, Func f )
245 iterator it = std::lower_bound( m_List.begin(), m_List.end(), val, pred );
246 if ( it == m_List.end() || pred( val, *it ) || pred( *it, val ) )
254 /// Clears the container
260 iterator begin() { return m_List.begin(); }
261 const_iterator begin() const { return m_List.begin(); }
262 iterator end() { return m_List.end(); }
263 const_iterator end() const { return m_List.end(); }
265 void move_item( adapted_container& /*from*/, iterator itWhat )
267 iterator it = std::lower_bound( m_List.begin(), m_List.end(), *itWhat, find_predicate() );
268 assert( it == m_List.end() || key_comparator()( *itWhat, *it ) != 0 );
270 copy_item()( m_List, it, itWhat );
271 # if !defined(CDS_STD_LIST_SIZE_CXX11_CONFORM)
278 # if !defined(CDS_STD_LIST_SIZE_CXX11_CONFORM)
281 return m_List.size();
288 typedef adapted_container type ; ///< Result of \p adapt metafunction
296 #endif // #ifndef CDSLIB_CONTAINER_STRIPED_SET_STD_LIST_ADAPTER_H