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 CDSUNIT_MAP_TEST_MICHAEL_ITERABLE_MAP_H
32 #define CDSUNIT_MAP_TEST_MICHAEL_ITERABLE_MAP_H
34 #include "test_map_data.h"
36 // forward declaration
37 namespace cds { namespace container {} }
41 class michael_iterable_map: public map_fixture
44 static size_t const kSize = 1000;
50 // Precondition: map is empty
51 // Postcondition: map is empty
53 EXPECT_TRUE( m.empty());
54 EXPECT_CONTAINER_SIZE( m, 0 );
56 typedef typename Map::value_type map_pair;
57 size_t const kkSize = kSize;
59 std::vector<key_type> arrKeys;
60 for ( int i = 0; i < static_cast<int>(kkSize); ++i )
61 arrKeys.push_back( key_type( i ));
62 shuffle( arrKeys.begin(), arrKeys.end());
64 std::vector< value_type > arrVals;
65 for ( size_t i = 0; i < kkSize; ++i ) {
67 val.nVal = static_cast<int>( i );
68 val.strVal = std::to_string( i );
69 arrVals.push_back( val );
73 for ( auto const& i : arrKeys ) {
74 value_type const& val( arrVals.at( i.nKey ));
76 EXPECT_FALSE( m.contains( i.nKey ));
77 EXPECT_FALSE( m.contains( i ));
78 EXPECT_FALSE( m.contains( other_item( i.nKey ), other_less()));
79 EXPECT_FALSE( m.find( i, []( map_pair const& ) {
82 EXPECT_FALSE( m.find( i.nKey, []( map_pair const& ) {
85 EXPECT_FALSE( m.find_with( other_item( i.nKey ), other_less(), []( map_pair const& ) {
89 EXPECT_TRUE( m.find( i ) == m.end());
90 EXPECT_TRUE( m.find( i.nKey ) == m.end());
91 EXPECT_TRUE( m.find_with( other_item( i.nKey ), other_less()) == m.end());
93 std::pair< bool, bool > updResult;
95 switch ( i.nKey % 17 ) {
97 EXPECT_TRUE( m.insert( i ));
98 EXPECT_FALSE( m.insert( i ));
99 EXPECT_TRUE( m.find( i.nKey, []( map_pair& v ) {
100 v.second.nVal = v.first.nKey;
101 v.second.strVal = std::to_string( v.first.nKey );
105 EXPECT_TRUE( m.insert( i.nKey ));
106 EXPECT_FALSE( m.insert( i.nKey ));
107 EXPECT_TRUE( m.find( i.nKey, []( map_pair& v ) {
108 v.second.nVal = v.first.nKey;
109 v.second.strVal = std::to_string( v.first.nKey );
113 EXPECT_TRUE( m.insert( std::to_string( i.nKey )));
114 EXPECT_FALSE( m.insert( std::to_string( i.nKey )));
115 EXPECT_TRUE( m.find( i.nKey, []( map_pair& v ) {
116 v.second.nVal = v.first.nKey;
117 v.second.strVal = std::to_string( v.first.nKey );
121 EXPECT_TRUE( m.insert( i, val ));
122 EXPECT_FALSE( m.insert( i, val ));
125 EXPECT_TRUE( m.insert( i.nKey, val.strVal ));
126 EXPECT_FALSE( m.insert( i.nKey, val.strVal ));
129 EXPECT_TRUE( m.insert( val.strVal, i.nKey ));
130 EXPECT_FALSE( m.insert( val.strVal, i.nKey ));
133 EXPECT_TRUE( m.insert_with( i, []( map_pair& v ) {
134 v.second.nVal = v.first.nKey;
135 v.second.strVal = std::to_string( v.first.nKey );
137 EXPECT_FALSE( m.insert_with( i, []( map_pair& ) {
138 EXPECT_TRUE( false );
142 EXPECT_TRUE( m.insert_with( i.nKey, []( map_pair& v ) {
143 v.second.nVal = v.first.nKey;
144 v.second.strVal = std::to_string( v.first.nKey );
146 EXPECT_FALSE( m.insert_with( i.nKey, []( map_pair& ) {
147 EXPECT_TRUE( false );
151 EXPECT_TRUE( m.insert_with( val.strVal, []( map_pair& v ) {
152 v.second.nVal = v.first.nKey;
153 v.second.strVal = std::to_string( v.first.nKey );
155 EXPECT_FALSE( m.insert_with( val.strVal, []( map_pair& ) {
156 EXPECT_TRUE( false );
160 updResult = m.update( i.nKey, []( map_pair&, map_pair* ) {
161 EXPECT_TRUE( false );
163 EXPECT_FALSE( updResult.first );
164 EXPECT_FALSE( updResult.second );
166 updResult = m.update( i.nKey, []( map_pair& v, map_pair* old ) {
167 EXPECT_TRUE( old == nullptr );
168 v.second.nVal = v.first.nKey;
170 EXPECT_TRUE( updResult.first );
171 EXPECT_TRUE( updResult.second );
173 updResult = m.update( i.nKey, []( map_pair& v, map_pair* old ) {
174 ASSERT_FALSE( old == nullptr );
175 EXPECT_EQ( v.first.nKey, old->second.nVal );
176 v.second.nVal = old->second.nVal;
177 v.second.strVal = std::to_string( old->second.nVal );
179 EXPECT_TRUE( updResult.first );
180 EXPECT_FALSE( updResult.second );
183 updResult = m.update( i, []( map_pair&, map_pair* ) {
184 EXPECT_TRUE( false );
186 EXPECT_FALSE( updResult.first );
187 EXPECT_FALSE( updResult.second );
189 updResult = m.update( i, []( map_pair& v, map_pair* old ) {
190 EXPECT_TRUE( old == nullptr );
191 v.second.nVal = v.first.nKey;
193 EXPECT_TRUE( updResult.first );
194 EXPECT_TRUE( updResult.second );
196 updResult = m.update( i, []( map_pair& v, map_pair* old ) {
197 ASSERT_FALSE( old == nullptr );
198 EXPECT_EQ( v.first.nKey, old->second.nVal );
199 v.second.nVal = old->second.nVal;
200 v.second.strVal = std::to_string( v.second.nVal );
202 EXPECT_TRUE( updResult.first );
203 EXPECT_FALSE( updResult.second );
206 updResult = m.update( val.strVal, []( map_pair&, map_pair* ) {
207 EXPECT_TRUE( false );
209 EXPECT_FALSE( updResult.first );
210 EXPECT_FALSE( updResult.second );
212 updResult = m.update( val.strVal, []( map_pair& v, map_pair* old ) {
213 EXPECT_TRUE( old == nullptr );
214 v.second.nVal = v.first.nKey;
216 EXPECT_TRUE( updResult.first );
217 EXPECT_TRUE( updResult.second );
219 updResult = m.update( val.strVal, []( map_pair& v, map_pair* old ) {
220 ASSERT_FALSE( old == nullptr );
221 EXPECT_EQ( v.first.nKey, old->second.nVal );
222 v.second.nVal = old->second.nVal;
223 v.second.strVal = std::to_string( v.second.nVal );
225 EXPECT_TRUE( updResult.first );
226 EXPECT_FALSE( updResult.second );
229 EXPECT_TRUE( m.emplace( i.nKey ));
230 EXPECT_FALSE( m.emplace( i.nKey ));
231 EXPECT_TRUE( m.find( i.nKey, []( map_pair& v ) {
232 v.second.nVal = v.first.nKey;
233 v.second.strVal = std::to_string( v.first.nKey );
237 EXPECT_TRUE( m.emplace( i, i.nKey ));
238 EXPECT_FALSE( m.emplace( i, i.nKey ));
242 std::string str = val.strVal;
243 EXPECT_TRUE( m.emplace( i, std::move( str )));
244 EXPECT_TRUE( str.empty());
246 EXPECT_FALSE( m.emplace( i, std::move( str )));
247 EXPECT_TRUE( str.empty());
252 std::string str = val.strVal;
253 EXPECT_TRUE( m.emplace( i, i.nKey, std::move( str )));
254 EXPECT_TRUE( str.empty());
256 EXPECT_FALSE( m.emplace( i, i.nKey, std::move( str )));
257 EXPECT_TRUE( str.empty());
262 auto res = m.upsert( i, i.nKey, false );
263 EXPECT_FALSE( res.first );
264 EXPECT_FALSE( res.second );
266 res = m.upsert( i, i.nKey );
267 EXPECT_TRUE( res.first );
268 EXPECT_TRUE( res.second );
270 std::string str = val.strVal;
271 res = m.upsert( i, std::move( str ));
272 EXPECT_TRUE( res.first );
273 EXPECT_FALSE( res.second );
274 EXPECT_TRUE( str.empty());
279 EXPECT_TRUE( m.contains( i.nKey ));
280 EXPECT_TRUE( m.contains( i ));
281 EXPECT_TRUE( m.contains( other_item( i.nKey ), other_less()));
282 EXPECT_TRUE( m.find( i, []( map_pair const& v ) {
283 EXPECT_EQ( v.first.nKey, v.second.nVal );
284 EXPECT_EQ( std::to_string( v.first.nKey ), v.second.strVal );
286 EXPECT_TRUE( m.find( i.nKey, []( map_pair const& v ) {
287 EXPECT_EQ( v.first.nKey, v.second.nVal );
288 EXPECT_EQ( std::to_string( v.first.nKey ), v.second.strVal );
290 EXPECT_TRUE( m.find_with( other_item( i.nKey ), other_less(), []( map_pair const& v ) {
291 EXPECT_EQ( v.first.nKey, v.second.nVal );
292 EXPECT_EQ( std::to_string( v.first.nKey ), v.second.strVal );
295 ASSERT_TRUE( m.find( i ) != m.end());
296 ASSERT_TRUE( m.find( i.nKey ) != m.end());
297 ASSERT_TRUE( m.find_with( other_item( i.nKey ), other_less()) != m.end());
299 EXPECT_EQ( m.find( i )->first.nKey, i.nKey );
300 EXPECT_EQ( m.find( i.nKey )->first.nKey, i.nKey );
301 EXPECT_EQ( m.find_with( other_item( i.nKey ), other_less())->first.nKey, i.nKey );
304 EXPECT_FALSE( m.empty());
305 EXPECT_CONTAINER_SIZE( m, kkSize );
306 EXPECT_FALSE( m.begin() == m.end());
307 EXPECT_FALSE( m.cbegin() == m.cend());
309 shuffle( arrKeys.begin(), arrKeys.end());
312 for ( auto const& i : arrKeys ) {
313 value_type const& val( arrVals.at( i.nKey ));
315 EXPECT_TRUE( m.contains( i.nKey ));
316 EXPECT_TRUE( m.contains( val.strVal ));
317 EXPECT_TRUE( m.contains( i ));
318 EXPECT_TRUE( m.contains( other_item( i.nKey ), other_less()));
319 EXPECT_TRUE( m.find( i, []( map_pair const& v ) {
320 EXPECT_EQ( v.first.nKey, v.second.nVal );
321 EXPECT_EQ( std::to_string( v.first.nKey ), v.second.strVal );
323 EXPECT_TRUE( m.find( i.nKey, []( map_pair const& v ) {
324 EXPECT_EQ( v.first.nKey, v.second.nVal );
325 EXPECT_EQ( std::to_string( v.first.nKey ), v.second.strVal );
327 EXPECT_TRUE( m.find_with( other_item( i.nKey ), other_less(), []( map_pair const& v ) {
328 EXPECT_EQ( v.first.nKey, v.second.nVal );
329 EXPECT_EQ( std::to_string( v.first.nKey ), v.second.strVal );
333 switch ( i.nKey % 8 ) {
335 EXPECT_TRUE( m.erase( i ));
336 EXPECT_FALSE( m.erase( i ));
339 EXPECT_TRUE( m.erase( i.nKey ));
340 EXPECT_FALSE( m.erase( i.nKey ));
343 EXPECT_TRUE( m.erase( val.strVal ));
344 EXPECT_FALSE( m.erase( val.strVal ));
347 EXPECT_TRUE( m.erase_with( other_item( i.nKey ), other_less()));
348 EXPECT_FALSE( m.erase_with( other_item( i.nKey ), other_less()));
351 EXPECT_TRUE( m.erase( i, []( map_pair& v ) {
352 EXPECT_EQ( v.first.nKey, v.second.nVal );
353 EXPECT_EQ( std::to_string( v.first.nKey ), v.second.strVal );
355 EXPECT_FALSE( m.erase( i, []( map_pair& ) {
356 EXPECT_TRUE( false );
360 EXPECT_TRUE( m.erase( i.nKey, []( map_pair& v ) {
361 EXPECT_EQ( v.first.nKey, v.second.nVal );
362 EXPECT_EQ( std::to_string( v.first.nKey ), v.second.strVal );
364 EXPECT_FALSE( m.erase( i.nKey, []( map_pair& ) {
365 EXPECT_TRUE( false );
369 EXPECT_TRUE( m.erase( val.strVal, []( map_pair& v ) {
370 EXPECT_EQ( v.first.nKey, v.second.nVal );
371 EXPECT_EQ( std::to_string( v.first.nKey ), v.second.strVal );
373 EXPECT_FALSE( m.erase( val.strVal, []( map_pair& ) {
374 EXPECT_TRUE( false );
378 EXPECT_TRUE( m.erase_with( other_item( i.nKey ), other_less(), []( map_pair& v ) {
379 EXPECT_EQ( v.first.nKey, v.second.nVal );
380 EXPECT_EQ( std::to_string( v.first.nKey ), v.second.strVal );
382 EXPECT_FALSE( m.erase_with( other_item( i.nKey ), other_less(), []( map_pair& ) {
383 EXPECT_TRUE( false );
388 EXPECT_FALSE( m.contains( i.nKey ));
389 EXPECT_FALSE( m.contains( i ));
390 EXPECT_FALSE( m.contains( val.strVal ));
391 EXPECT_FALSE( m.contains( other_item( i.nKey ), other_less()));
392 EXPECT_FALSE( m.find( i, []( map_pair const& ) {
393 EXPECT_TRUE( false );
395 EXPECT_FALSE( m.find( i.nKey, []( map_pair const& ) {
396 EXPECT_TRUE( false );
398 EXPECT_FALSE( m.find_with( other_item( i.nKey ), other_less(), []( map_pair const& ) {
399 EXPECT_TRUE( false );
402 EXPECT_TRUE( m.empty());
403 EXPECT_CONTAINER_SIZE( m, 0 );
405 EXPECT_TRUE( m.begin() == m.end());
406 EXPECT_TRUE( m.cbegin() == m.cend());
409 for ( auto const& i : arrKeys )
410 EXPECT_TRUE( m.insert( i ));
412 EXPECT_FALSE( m.empty());
413 EXPECT_CONTAINER_SIZE( m, kkSize );
417 EXPECT_TRUE( m.empty());
418 EXPECT_CONTAINER_SIZE( m, 0 );
422 } // namespace cds_test
424 #endif // #ifndef CDSUNIT_MAP_TEST_MICHAEL_ITERABLE_MAP_H