2 This file is a part of libcds - Concurrent Data Structures library
4 (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2017
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_MAP_STD_LIST_ADAPTER_H
32 #define CDSLIB_CONTAINER_STRIPED_MAP_STD_LIST_ADAPTER_H
35 #include <functional> // ref
36 #include <algorithm> // std::lower_bound
37 #include <utility> // std::pair
38 #include <cds/container/striped_set/adapter.h>
40 #undef CDS_STD_LIST_SIZE_CXX11_CONFORM
41 #if !( defined(__GLIBCXX__ ) && (!defined(_GLIBCXX_USE_CXX11_ABI) || _GLIBCXX_USE_CXX11_ABI == 0 ))
42 # define CDS_STD_LIST_SIZE_CXX11_CONFORM
46 namespace cds { namespace container {
47 namespace striped_set {
49 // Copy policy for map
50 template <typename K, typename T, typename Alloc>
51 struct copy_item_policy< std::list< std::pair< K const, T >, Alloc > >
53 typedef std::pair< K const, T> pair_type;
54 typedef std::list< pair_type, Alloc > list_type;
55 typedef typename list_type::iterator iterator;
57 void operator()( list_type& list, iterator itInsert, iterator itWhat )
59 list.insert( itInsert, *itWhat );
63 // Swap policy for map
64 template <typename K, typename T, typename Alloc>
65 struct swap_item_policy< std::list< std::pair< K const, T >, Alloc > >
67 typedef std::pair< K const, T> pair_type;
68 typedef std::list< pair_type, Alloc > list_type;
69 typedef typename list_type::iterator iterator;
71 void operator()( list_type& list, iterator itInsert, iterator itWhat )
73 pair_type newVal( itWhat->first, typename pair_type::second_type());
74 itInsert = list.insert( itInsert, newVal );
75 std::swap( itInsert->second, itWhat->second );
79 // Move policy for map
80 template <typename K, typename T, typename Alloc>
81 struct move_item_policy< std::list< std::pair< K const, T >, Alloc > >
83 typedef std::pair< K const, T> pair_type;
84 typedef std::list< pair_type, Alloc > list_type;
85 typedef typename list_type::iterator iterator;
87 void operator()( list_type& list, iterator itInsert, iterator itWhat )
89 list.insert( itInsert, std::move( *itWhat ));
92 } // namespace striped_set
93 }} // namespace cds:container
95 namespace cds { namespace intrusive { namespace striped_set {
97 /// std::list adapter for hash map bucket
98 template <typename Key, typename T, class Alloc, typename... Options>
99 class adapt< std::list< std::pair<Key const, T>, Alloc>, Options... >
102 typedef std::list< std::pair<Key const, T>, Alloc> container_type ; ///< underlying container type
105 /// Adapted container type
106 class adapted_container: public cds::container::striped_set::adapted_sequential_container
109 typedef typename container_type::value_type value_type ; ///< value type stored in the container
110 typedef typename value_type::first_type key_type;
111 typedef typename value_type::second_type mapped_type;
112 typedef typename container_type::iterator iterator ; ///< container iterator
113 typedef typename container_type::const_iterator const_iterator ; ///< container const iterator
115 static bool const has_find_with = true;
116 static bool const has_erase_with = true;
120 typedef typename cds::opt::details::make_comparator_from_option_list< value_type, Options... >::type key_comparator;
123 typedef typename cds::opt::select<
124 typename cds::opt::value<
125 typename cds::opt::find_option<
126 cds::opt::copy_policy< cds::container::striped_set::move_item >
130 , cds::container::striped_set::copy_item, cds::container::striped_set::copy_item_policy<container_type>
131 , cds::container::striped_set::swap_item, cds::container::striped_set::swap_item_policy<container_type>
132 , cds::container::striped_set::move_item, cds::container::striped_set::move_item_policy<container_type>
135 struct find_predicate
137 bool operator()( value_type const& i1, value_type const& i2) const
139 return key_comparator()( i1.first, i2.first ) < 0;
142 template <typename Q>
143 bool operator()( Q const& i1, value_type const& i2) const
145 return key_comparator()( i1, i2.first ) < 0;
148 template <typename Q>
149 bool operator()( value_type const& i1, Q const& i2) const
151 return key_comparator()( i1.first, i2 ) < 0;
158 container_type m_List;
159 # if !defined(CDS_STD_LIST_SIZE_CXX11_CONFORM)
161 // In GCC (at least up to 4.7.x), the complexity of std::list::size() is O(N)
162 // (see http://gcc.gnu.org/bugzilla/show_bug.cgi?id=49561)
164 size_t m_nSize ; // list size
170 # if !defined(CDS_STD_LIST_SIZE_CXX11_CONFORM)
175 template <typename Q, typename Func>
176 bool insert( const Q& key, Func f )
178 iterator it = std::lower_bound( m_List.begin(), m_List.end(), key, find_predicate());
179 if ( it == m_List.end() || key_comparator()( key, it->first ) != 0 ) {
180 it = m_List.insert( it, value_type( key_type( key ), mapped_type()));
183 # if !defined(CDS_STD_LIST_SIZE_CXX11_CONFORM)
189 // key already exists
193 template <typename K, typename... Args>
194 bool emplace( K&& key, Args&&... args )
196 value_type val( key_type( std::forward<K>( key )), mapped_type( std::forward<Args>( args )... ));
197 iterator it = std::lower_bound( m_List.begin(), m_List.end(), val.first, find_predicate());
198 if ( it == m_List.end() || key_comparator()( val.first, it->first ) != 0 ) {
199 it = m_List.emplace( it, std::move( val ));
201 # if !defined(CDS_STD_LIST_SIZE_CXX11_CONFORM)
209 template <typename Q, typename Func>
210 std::pair<bool, bool> update( const Q& key, Func func, bool bAllowInsert )
212 iterator it = std::lower_bound( m_List.begin(), m_List.end(), key, find_predicate());
213 if ( it == m_List.end() || key_comparator()( key, it->first ) != 0 ) {
216 return std::make_pair( false, false );
218 it = m_List.insert( it, value_type( key_type( key ), mapped_type()));
220 # if !defined(CDS_STD_LIST_SIZE_CXX11_CONFORM)
223 return std::make_pair( true, true );
228 return std::make_pair( true, false );
232 template <typename Q, typename Func>
233 bool erase( Q const& key, Func f )
235 iterator it = std::lower_bound( m_List.begin(), m_List.end(), key, find_predicate());
236 if ( it == m_List.end() || key_comparator()( key, it->first ) != 0 )
242 # if !defined(CDS_STD_LIST_SIZE_CXX11_CONFORM)
249 template <typename Q, typename Less, typename Func>
250 bool erase( Q const& key, Less pred, Func f )
252 iterator it = std::lower_bound( m_List.begin(), m_List.end(), key, pred );
253 if ( it == m_List.end() || pred( key, it->first ) || pred( it->first, key ))
259 # if !defined(CDS_STD_LIST_SIZE_CXX11_CONFORM)
266 template <typename Q, typename Func>
267 bool find( Q& val, Func f )
269 iterator it = std::lower_bound( m_List.begin(), m_List.end(), val, find_predicate());
270 if ( it == m_List.end() || key_comparator()( val, it->first ) != 0 )
278 template <typename Q, typename Less, typename Func>
279 bool find( Q& val, Less pred, Func f )
281 iterator it = std::lower_bound( m_List.begin(), m_List.end(), val, pred );
282 if ( it == m_List.end() || pred( val, it->first ) || pred( it->first, val ))
295 iterator begin() { return m_List.begin(); }
296 const_iterator begin() const { return m_List.begin(); }
297 iterator end() { return m_List.end(); }
298 const_iterator end() const { return m_List.end(); }
300 void move_item( adapted_container& /*from*/, iterator itWhat )
302 iterator it = std::lower_bound( m_List.begin(), m_List.end(), *itWhat, find_predicate());
303 assert( it == m_List.end() || key_comparator()( itWhat->first, it->first ) != 0 );
305 copy_item()( m_List, it, itWhat );
306 # if !defined(CDS_STD_LIST_SIZE_CXX11_CONFORM)
313 # if !defined(CDS_STD_LIST_SIZE_CXX11_CONFORM)
316 return m_List.size();
323 typedef adapted_container type ; ///< Result of \p adapt metafunction
326 }}} // namespace cds::intrusive::striped_set
330 #endif // #ifndef CDSLIB_CONTAINER_STRIPED_MAP_STD_LIST_ADAPTER_H