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_MAP_BOOST_LIST_ADAPTER_H
32 #define CDSLIB_CONTAINER_STRIPED_MAP_BOOST_LIST_ADAPTER_H
34 #include <boost/version.hpp>
35 #if BOOST_VERSION < 104800
36 # error "For boost::container::list you must use boost 1.48 or above"
39 #include <functional> // ref
40 #include <algorithm> // std::lower_bound
41 #include <utility> // std::pair
42 #include <cds/container/striped_set/adapter.h>
43 #include <boost/container/list.hpp>
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< boost::container::list< std::pair< K const, T >, Alloc > >
53 typedef std::pair< K const, T> pair_type;
54 typedef boost::container::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< boost::container::list< std::pair< K const, T >, Alloc > >
67 typedef std::pair< K const, T> pair_type;
68 typedef boost::container::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< boost::container::list< std::pair< K const, T >, Alloc > >
83 typedef std::pair< K const, T> pair_type;
84 typedef boost::container::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 /// boost::container::list adapter for hash map bucket
98 template <typename Key, typename T, class Alloc, typename... Options>
99 class adapt< boost::container::list< std::pair<Key const, T>, Alloc>, Options... >
102 typedef boost::container::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;
122 typedef typename cds::opt::select<
123 typename cds::opt::value<
124 typename cds::opt::find_option<
125 cds::opt::copy_policy< cds::container::striped_set::move_item >
129 , cds::container::striped_set::copy_item, cds::container::striped_set::copy_item_policy<container_type>
130 , cds::container::striped_set::swap_item, cds::container::striped_set::swap_item_policy<container_type>
131 , cds::container::striped_set::move_item, cds::container::striped_set::move_item_policy<container_type>
134 struct find_predicate
136 bool operator()( value_type const& i1, value_type const& i2) const
138 return key_comparator()( i1.first, i2.first ) < 0;
141 template <typename Q>
142 bool operator()( Q const& i1, value_type const& i2) const
144 return key_comparator()( i1, i2.first ) < 0;
147 template <typename Q>
148 bool operator()( value_type const& i1, Q const& i2) const
150 return key_comparator()( i1.first, i2 ) < 0;
157 container_type m_List;
164 template <typename Q, typename Func>
165 bool insert( const Q& key, Func f )
167 iterator it = std::lower_bound( m_List.begin(), m_List.end(), key, find_predicate() );
168 if ( it == m_List.end() || key_comparator()( key, it->first ) != 0 ) {
169 //value_type newItem( key );
170 it = m_List.insert( it, value_type( key, mapped_type()) );
176 // key already exists
180 template <typename K, typename... Args>
181 bool emplace( K&& key, Args&&... args )
183 iterator it = std::lower_bound( m_List.begin(), m_List.end(), key, find_predicate() );
184 if ( it == m_List.end() || key_comparator()( key, it->first ) != 0 ) {
185 m_List.emplace( it, std::forward<K>(key), std::move( mapped_type( std::forward<Args>(args)... )) );
191 template <typename Q, typename Func>
192 std::pair<bool, bool> update( const Q& key, Func func, bool bAllowInsert )
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->first ) != 0 ) {
198 return std::make_pair( false, false );
200 value_type newItem( key, mapped_type() );
201 it = m_List.insert( it, newItem );
204 return std::make_pair( true, true );
209 return std::make_pair( true, false );
213 template <typename Q, typename Func>
214 bool erase( Q const& key, Func f )
216 iterator it = std::lower_bound( m_List.begin(), m_List.end(), key, find_predicate() );
217 if ( it == m_List.end() || key_comparator()( key, it->first ) != 0 )
227 template <typename Q, typename Less, typename Func>
228 bool erase( Q const& key, Less pred, Func f )
230 iterator it = std::lower_bound( m_List.begin(), m_List.end(), key, pred );
231 if ( it == m_List.end() || pred( key, it->first ) || pred(it->first, key) )
241 template <typename Q, typename Func>
242 bool find( Q& val, Func f )
244 iterator it = std::lower_bound( m_List.begin(), m_List.end(), val, find_predicate() );
245 if ( it == m_List.end() || key_comparator()( val, it->first ) != 0 )
253 template <typename Q, typename Less, typename Func>
254 bool find( Q& val, Less pred, Func f )
256 iterator it = std::lower_bound( m_List.begin(), m_List.end(), val, pred );
257 if ( it == m_List.end() || pred( val, it->first ) || pred( it->first, val ) )
265 /// Clears the container
271 iterator begin() { return m_List.begin(); }
272 const_iterator begin() const { return m_List.begin(); }
273 iterator end() { return m_List.end(); }
274 const_iterator end() const { return m_List.end(); }
276 void move_item( adapted_container& /*from*/, iterator itWhat )
278 iterator it = std::lower_bound( m_List.begin(), m_List.end(), *itWhat, find_predicate() );
279 assert( it == m_List.end() || key_comparator()( itWhat->first, it->first ) != 0 );
281 copy_item()( m_List, it, itWhat );
286 return m_List.size();
291 typedef adapted_container type ; ///< Result of \p adapt metafunction
295 }}} // namespace cds::intrusive::striped_set
298 #endif // #ifndef CDSLIB_CONTAINER_STRIPED_MAP_BOOST_LIST_ADAPTER_H