2 This file is a part of libcds - Concurrent Data Structures library
4 (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016
6 Source code repo: http://github.com/khizmax/libcds/
7 Download: http://sourceforge.net/projects/libcds/files/
9 Redistribution and use in source and binary forms, with or without
10 modification, are permitted provided that the following conditions are met:
12 * Redistributions of source code must retain the above copyright notice, this
13 list of conditions and the following disclaimer.
15 * Redistributions in binary form must reproduce the above copyright notice,
16 this list of conditions and the following disclaimer in the documentation
17 and/or other materials provided with the distribution.
19 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
20 AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
21 IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
22 DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
23 FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
24 DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
25 SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
26 CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
27 OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
28 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
31 #ifndef CDSLIB_CONTAINER_STRIPED_SET_STD_LIST_ADAPTER_H
32 #define CDSLIB_CONTAINER_STRIPED_SET_STD_LIST_ADAPTER_H
34 #include <functional> // ref
36 #include <algorithm> // std::lower_bound
37 #include <cds/container/striped_set/adapter.h>
39 #undef CDS_STD_LIST_SIZE_CXX11_CONFORM
40 #if !( defined(__GLIBCXX__ ) && (!defined(_GLIBCXX_USE_CXX11_ABI) || _GLIBCXX_USE_CXX11_ABI == 0 ))
41 # define CDS_STD_LIST_SIZE_CXX11_CONFORM
45 namespace cds { namespace container {
46 namespace striped_set {
48 // Copy policy for std::list
49 template <typename T, typename Alloc>
50 struct copy_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 itInsert = list.insert( itInsert, *itWhat );
61 // Swap policy for std::list
62 template <typename T, typename Alloc>
63 struct swap_item_policy< std::list< T, Alloc > >
65 typedef std::list< T, Alloc > list_type;
66 typedef typename list_type::iterator iterator;
68 void operator()( list_type& list, iterator itInsert, iterator itWhat )
70 typename list_type::value_type newVal;
71 itInsert = list.insert( itInsert, newVal );
72 std::swap( *itWhat, *itInsert );
76 // Move policy for std::list
77 template <typename T, typename Alloc>
78 struct move_item_policy< std::list< T, Alloc > >
80 typedef std::list< T, Alloc > list_type;
81 typedef typename list_type::iterator iterator;
83 void operator()( list_type& list, iterator itInsert, iterator itWhat )
85 list.insert( itInsert, std::move( *itWhat ) );
88 } // namespace striped_set
89 }} // namespace cds::container
91 namespace cds { namespace intrusive { namespace striped_set {
93 /// std::list adapter for hash set bucket
94 template <typename T, class Alloc, typename... Options>
95 class adapt< std::list<T, Alloc>, Options... >
98 typedef std::list<T, Alloc> container_type ; ///< underlying container type
101 /// Adapted container type
102 class adapted_container: public cds::container::striped_set::adapted_sequential_container
105 typedef typename container_type::value_type value_type ; ///< value type stored in the container
106 typedef typename container_type::iterator iterator ; ///< container iterator
107 typedef typename container_type::const_iterator const_iterator ; ///< container const iterator
109 static bool const has_find_with = true;
110 static bool const has_erase_with = true;
114 typedef typename cds::opt::details::make_comparator_from_option_list< value_type, Options... >::type key_comparator;
117 typedef typename cds::opt::select<
118 typename cds::opt::value<
119 typename cds::opt::find_option<
120 cds::opt::copy_policy< cds::container::striped_set::move_item >
124 , cds::container::striped_set::copy_item, cds::container::striped_set::copy_item_policy<container_type>
125 , cds::container::striped_set::swap_item, cds::container::striped_set::swap_item_policy<container_type>
126 , cds::container::striped_set::move_item, cds::container::striped_set::move_item_policy<container_type>
129 struct find_predicate
131 bool operator()( value_type const& i1, value_type const& i2) const
133 return key_comparator()( i1, i2 ) < 0;
136 template <typename Q>
137 bool operator()( Q const& i1, value_type const& i2) const
139 return key_comparator()( i1, i2 ) < 0;
142 template <typename Q>
143 bool operator()( value_type const& i1, Q const& i2) const
145 return key_comparator()( i1, i2 ) < 0;
152 container_type m_List;
153 # if !defined(CDS_STD_LIST_SIZE_CXX11_CONFORM)
155 // In GCC, the complexity of std::list::size() is O(N)
156 // (see http://gcc.gnu.org/bugzilla/show_bug.cgi?id=49561)
158 size_t m_nSize ; // list size
164 # if !defined(CDS_STD_LIST_SIZE_CXX11_CONFORM)
169 template <typename Q, typename Func>
170 bool insert( const Q& val, Func f )
172 iterator it = std::lower_bound( m_List.begin(), m_List.end(), val, find_predicate() );
173 if ( it == m_List.end() || key_comparator()( val, *it ) != 0 ) {
174 value_type newItem( val );
175 it = m_List.insert( it, newItem );
178 # if !defined(CDS_STD_LIST_SIZE_CXX11_CONFORM)
184 // key already exists
188 template <typename... Args>
189 bool emplace( Args&&... args )
191 value_type val(std::forward<Args>(args)...);
192 iterator it = std::lower_bound( m_List.begin(), m_List.end(), val, find_predicate() );
193 if ( it == m_List.end() || key_comparator()( val, *it ) != 0 ) {
194 it = m_List.emplace( it, std::move( val ) );
195 # if !defined(CDS_STD_LIST_SIZE_CXX11_CONFORM)
203 template <typename Q, typename Func>
204 std::pair<bool, bool> update( const Q& val, Func func, bool bAllowInsert )
206 iterator it = std::lower_bound( m_List.begin(), m_List.end(), val, find_predicate() );
207 if ( it == m_List.end() || key_comparator()( val, *it ) != 0 ) {
210 return std::make_pair( false, false );
212 value_type newItem( val );
213 it = m_List.insert( it, newItem );
214 func( true, *it, val );
215 # if !defined(CDS_STD_LIST_SIZE_CXX11_CONFORM)
218 return std::make_pair( true, true );
222 func( false, *it, val );
223 return std::make_pair( true, false );
227 template <typename Q, typename Func>
228 bool erase( const Q& key, Func f )
230 iterator it = std::lower_bound( m_List.begin(), m_List.end(), key, find_predicate() );
231 if ( it == m_List.end() || key_comparator()( key, *it ) != 0 )
237 # if !defined(CDS_STD_LIST_SIZE_CXX11_CONFORM)
244 template <typename Q, typename Less, typename Func>
245 bool erase( Q const& key, Less pred, Func f )
247 iterator it = std::lower_bound( m_List.begin(), m_List.end(), key, pred );
248 if ( it == m_List.end() || pred( key, *it ) || pred( *it, key ) )
254 # if !defined(CDS_STD_LIST_SIZE_CXX11_CONFORM)
261 template <typename Q, typename Func>
262 bool find( Q& val, Func f )
264 iterator it = std::lower_bound( m_List.begin(), m_List.end(), val, find_predicate() );
265 if ( it == m_List.end() || key_comparator()( val, *it ) != 0 )
273 template <typename Q, typename Less, typename Func>
274 bool find( Q& val, Less pred, Func f )
276 iterator it = std::lower_bound( m_List.begin(), m_List.end(), val, pred );
277 if ( it == m_List.end() || pred( val, *it ) || pred( *it, val ) )
285 /// Clears the container
291 iterator begin() { return m_List.begin(); }
292 const_iterator begin() const { return m_List.begin(); }
293 iterator end() { return m_List.end(); }
294 const_iterator end() const { return m_List.end(); }
296 void move_item( adapted_container& /*from*/, iterator itWhat )
298 iterator it = std::lower_bound( m_List.begin(), m_List.end(), *itWhat, find_predicate() );
299 assert( it == m_List.end() || key_comparator()( *itWhat, *it ) != 0 );
301 copy_item()( m_List, it, itWhat );
302 # if !defined(CDS_STD_LIST_SIZE_CXX11_CONFORM)
309 # if !defined(CDS_STD_LIST_SIZE_CXX11_CONFORM)
312 return m_List.size();
319 typedef adapted_container type ; ///< Result of \p adapt metafunction
327 #endif // #ifndef CDSLIB_CONTAINER_STRIPED_SET_STD_LIST_ADAPTER_H