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 CDSTEST_HDR_STRIPED_MAP_H
32 #define CDSTEST_HDR_STRIPED_MAP_H
33 #include "size_check.h"
35 #include "cppunit/cppunit_proxy.h"
36 #include <cds/os/timer.h>
37 #include <cds/opt/hash.h>
38 #include <functional> // ref
40 namespace cds { namespace container {}}
43 using misc::check_size;
45 namespace cc = cds::container;
46 namespace co = cds::opt;
48 class StripedMapHdrTest: public CppUnitMini::TestCase
64 value_type( value_type&& v )
68 value_type( value_type const& v )
72 value_type& operator=( value_type const& v )
79 typedef std::pair<key_type const, value_type> pair_type;
83 bool operator ()(int v1, int v2 ) const
90 int operator ()(int v1, int v2 ) const
94 return v1 > v2 ? 1 : 0;
99 bool operator ()(int v1, int v2 ) const
106 size_t operator()( int i ) const
108 return co::v::hash<int>()( i );
112 struct simple_item_counter {
115 simple_item_counter()
134 operator size_t() const
140 template <typename Map>
141 struct insert_functor
143 typedef typename Map::value_type pair_type;
146 void operator()( pair_type& item )
148 item.second.m_val = item.first * 3;
152 void operator()( bool bNew, pair_type& item )
155 item.second.m_val = item.first * 2;
157 item.second.m_val = item.first * 5;
164 check_value( int nExpected )
165 : m_nExpected( nExpected )
168 template <typename T>
169 void operator ()( T& pair )
171 CPPUNIT_ASSERT_CURRENT( pair.second.m_val == m_nExpected );
173 template <typename T, typename Q>
174 void operator ()( T& pair, Q )
176 CPPUNIT_ASSERT_CURRENT( pair.second.m_val == m_nExpected );
180 struct extract_functor
183 void operator()( pair_type const& val )
185 *m_pVal = val.second.m_val;
190 void test_int_with( Map& m )
192 std::pair<bool, bool> updateResult;
195 CPPUNIT_ASSERT( m.empty() );
196 CPPUNIT_ASSERT( check_size( m, 0 ));
197 CPPUNIT_ASSERT( !m.contains(25) );
198 CPPUNIT_ASSERT( m.insert( 25 ) ) ; // value = 0
199 CPPUNIT_ASSERT( m.contains(25) );
200 CPPUNIT_ASSERT( !m.empty() );
201 CPPUNIT_ASSERT( check_size( m, 1 ));
202 CPPUNIT_ASSERT( m.contains(25) );
204 CPPUNIT_ASSERT( !m.insert( 25 ) );
205 CPPUNIT_ASSERT( !m.empty() );
206 CPPUNIT_ASSERT( check_size( m, 1 ));
208 CPPUNIT_ASSERT( !m.contains(10) );
209 CPPUNIT_ASSERT( m.insert( 10, 10 ) );
210 CPPUNIT_ASSERT( !m.empty() );
211 CPPUNIT_ASSERT( check_size( m, 2 ));
212 CPPUNIT_ASSERT( m.contains(10) );
214 CPPUNIT_ASSERT( !m.insert( 10, 20 ) );
215 CPPUNIT_ASSERT( !m.empty() );
216 CPPUNIT_ASSERT( check_size( m, 2 ));
218 CPPUNIT_ASSERT( !m.contains(30) );
219 CPPUNIT_ASSERT( m.insert_with( 30, insert_functor<Map>() ) ) ; // value = 90
220 CPPUNIT_ASSERT( !m.empty() );
221 CPPUNIT_ASSERT( check_size( m, 3 ));
222 CPPUNIT_ASSERT( m.contains(30) );
224 CPPUNIT_ASSERT( !m.insert_with( 10, insert_functor<Map>() ) );
225 CPPUNIT_ASSERT( !m.insert_with( 25, insert_functor<Map>() ) );
226 CPPUNIT_ASSERT( !m.insert_with( 30, insert_functor<Map>() ) );
228 // update() (new key)
229 CPPUNIT_ASSERT( !m.contains(27) );
230 updateResult = m.update(27, insert_functor<Map>(), false);
231 CPPUNIT_ASSERT(!updateResult.first);
232 CPPUNIT_ASSERT(!updateResult.second);
233 CPPUNIT_ASSERT(check_size(m, 3));
234 CPPUNIT_ASSERT(!m.contains(27));
235 updateResult = m.update( 27, insert_functor<Map>() ) ; // value = 54
236 CPPUNIT_ASSERT( updateResult.first );
237 CPPUNIT_ASSERT( updateResult.second );
238 CPPUNIT_ASSERT( check_size( m, 4 ));
239 CPPUNIT_ASSERT( m.contains(27) );
243 CPPUNIT_ASSERT( m.find( 10, std::ref(chk) ));
245 CPPUNIT_ASSERT( m.find( 25, std::ref( chk ) ) );
246 chk.m_nExpected = 90;
247 CPPUNIT_ASSERT( m.find( 30, std::ref( chk ) ) );
248 chk.m_nExpected = 54;
249 CPPUNIT_ASSERT( m.find( 27, std::ref( chk ) ) );
251 updateResult = m.update( 10, insert_functor<Map>() ) ; // value = 50
252 CPPUNIT_ASSERT( updateResult.first );
253 CPPUNIT_ASSERT( !updateResult.second );
254 chk.m_nExpected = 50;
255 CPPUNIT_ASSERT( m.find( 10, std::ref( chk ) ) );
258 CPPUNIT_ASSERT( !m.contains(100) );
259 CPPUNIT_ASSERT( !m.erase( 100 )) ; // not found
261 CPPUNIT_ASSERT( m.contains(25) );
262 CPPUNIT_ASSERT( check_size( m, 4 ));
263 CPPUNIT_ASSERT( m.erase( 25 ));
264 CPPUNIT_ASSERT( !m.empty() );
265 CPPUNIT_ASSERT( check_size( m, 3 ));
266 CPPUNIT_ASSERT( !m.contains(25) );
267 CPPUNIT_ASSERT( !m.erase( 25 ));
269 CPPUNIT_ASSERT( !m.contains(258) );
270 CPPUNIT_ASSERT( m.insert(258))
271 CPPUNIT_ASSERT( check_size( m, 4 ));
272 CPPUNIT_ASSERT( m.contains(258) );
273 CPPUNIT_ASSERT( m.erase( 258 ));
274 CPPUNIT_ASSERT( !m.empty() );
275 CPPUNIT_ASSERT( check_size( m, 3 ));
276 CPPUNIT_ASSERT( !m.contains(258) );
277 CPPUNIT_ASSERT( !m.erase( 258 ));
283 CPPUNIT_ASSERT( !m.contains(29) );
284 CPPUNIT_ASSERT( m.insert(29, 290));
285 CPPUNIT_ASSERT( check_size( m, 4 ));
286 CPPUNIT_ASSERT( m.erase( 29, std::ref( ext ) ) );
287 CPPUNIT_ASSERT( !m.empty() );
288 CPPUNIT_ASSERT( check_size( m, 3 ));
289 CPPUNIT_ASSERT( nVal == 290 );
291 CPPUNIT_ASSERT( !m.erase( 29, std::ref( ext ) ) );
292 CPPUNIT_ASSERT( nVal == -1 );
294 CPPUNIT_ASSERT( m.erase( 30, std::ref( ext ) ) );
295 CPPUNIT_ASSERT( !m.empty() );
296 CPPUNIT_ASSERT( check_size( m, 2 ));
297 CPPUNIT_ASSERT( nVal == 90 );
299 CPPUNIT_ASSERT( !m.erase( 30, std::ref( ext ) ) );
300 CPPUNIT_ASSERT( nVal == -1 );
303 CPPUNIT_ASSERT( m.empty() );
304 CPPUNIT_ASSERT( check_size( m, 0 ));
307 CPPUNIT_ASSERT( m.emplace(126) ) ; // key = 126, val = 0
308 CPPUNIT_ASSERT( m.emplace(137, 731)) ; // key = 137, val = 731
309 CPPUNIT_ASSERT( m.emplace( 149, value_type(941) )) ; // key = 149, val = 941
311 CPPUNIT_ASSERT( !m.empty() );
312 CPPUNIT_ASSERT( check_size( m, 3 ));
315 CPPUNIT_ASSERT( m.find( 126, std::ref(chk) ));
316 chk.m_nExpected = 731;
317 CPPUNIT_ASSERT( m.find( 137, std::ref(chk) ));
318 chk.m_nExpected = 941;
319 CPPUNIT_ASSERT( m.find( 149, std::ref(chk) ));
321 CPPUNIT_ASSERT( !m.emplace(126, 621)) ; // already in map
323 CPPUNIT_ASSERT( m.find( 126, std::ref(chk) ));
324 CPPUNIT_ASSERT( !m.empty() );
325 CPPUNIT_ASSERT( check_size( m, 3 ));
328 CPPUNIT_ASSERT( m.empty() );
329 CPPUNIT_ASSERT( check_size( m, 0 ));
333 void test_iter( Map& s)
335 typedef typename Map::iterator iterator;
336 typedef typename Map::const_iterator const_iterator;
338 const int nMaxCount = 500;
339 for ( int i = 0; i < nMaxCount; ++i ) {
340 CPPUNIT_ASSERT( s.insert( i, i * 2 ));
344 for ( iterator it = s.begin(), itEnd = s.end(); it != itEnd; ++it ) {
345 CPPUNIT_ASSERT( it->first * 2 == it->second.m_val );
346 CPPUNIT_ASSERT( (*it).first * 2 == (*it).second.m_val );
347 it->second.m_val = it->first;
350 CPPUNIT_ASSERT( nCount == nMaxCount );
352 Map const& refSet = s;
354 for ( const_iterator it = refSet.begin(), itEnd = refSet.end(); it != itEnd; ++it ) {
355 CPPUNIT_ASSERT( it->first == it->second.m_val );
356 CPPUNIT_ASSERT( (*it).first == (*it).second.m_val );
359 CPPUNIT_ASSERT( nCount == nMaxCount );
366 CPPUNIT_ASSERT( m.bucket_count() == 32 );
367 CPPUNIT_ASSERT( m.lock_count() == 32 );
369 test_striped_with(m);
373 void test_striped_with(Map& m)
375 cds::OS::Timer timer;
379 // Iterators is not yet supported
381 //CPPUNIT_ASSERT( m.empty() );
382 //CPPUNIT_ASSERT( check_size( m, 0 ));
386 CPPUNIT_ASSERT( m.empty() );
387 CPPUNIT_ASSERT( check_size( m, 0 ));
390 for ( int i = 0; i < 40000; i++ ) {
394 CPPUNIT_MSG( " Duration=" << timer.duration() );
397 //*******************************************
398 // If erase_with && find_with are supported
400 void test_int_with2( Map& m )
402 std::pair<bool, bool> updateResult;
405 CPPUNIT_ASSERT( m.empty() );
406 CPPUNIT_ASSERT( check_size( m, 0 ));
407 CPPUNIT_ASSERT( !m.contains(25) );
408 CPPUNIT_ASSERT( m.insert( 25 ) ) ; // value = 0
409 CPPUNIT_ASSERT( m.contains(25) );
410 CPPUNIT_ASSERT( !m.empty() );
411 CPPUNIT_ASSERT( check_size( m, 1 ));
412 CPPUNIT_ASSERT( m.contains(25) );
414 CPPUNIT_ASSERT( !m.insert( 25 ) );
415 CPPUNIT_ASSERT( !m.empty() );
416 CPPUNIT_ASSERT( check_size( m, 1 ));
418 CPPUNIT_ASSERT( !m.contains(10, less()) );
419 CPPUNIT_ASSERT( m.insert( 10, 10 ) );
420 CPPUNIT_ASSERT( !m.empty() );
421 CPPUNIT_ASSERT( check_size( m, 2 ));
422 CPPUNIT_ASSERT( m.contains(10, less()) );
424 CPPUNIT_ASSERT( !m.insert( 10, 20 ) );
425 CPPUNIT_ASSERT( !m.empty() );
426 CPPUNIT_ASSERT( check_size( m, 2 ));
428 CPPUNIT_ASSERT( !m.contains(30) );
429 CPPUNIT_ASSERT( m.insert_with( 30, insert_functor<Map>() ) ) ; // value = 90
430 CPPUNIT_ASSERT( !m.empty() );
431 CPPUNIT_ASSERT( check_size( m, 3 ));
432 CPPUNIT_ASSERT( m.contains(30) );
434 CPPUNIT_ASSERT( !m.insert_with( 10, insert_functor<Map>() ) );
435 CPPUNIT_ASSERT( !m.insert_with( 25, insert_functor<Map>() ) );
436 CPPUNIT_ASSERT( !m.insert_with( 30, insert_functor<Map>() ) );
438 // update() (new key)
439 CPPUNIT_ASSERT( !m.contains(27) );
440 updateResult = m.update(27, insert_functor<Map>(), false);
441 CPPUNIT_ASSERT(!updateResult.first);
442 CPPUNIT_ASSERT(!updateResult.second);
443 CPPUNIT_ASSERT(!m.contains(27));
444 updateResult = m.update( 27, insert_functor<Map>() ) ; // value = 54
445 CPPUNIT_ASSERT( updateResult.first );
446 CPPUNIT_ASSERT( updateResult.second );
447 CPPUNIT_ASSERT( m.contains(27) );
451 CPPUNIT_ASSERT( m.find( 10, std::ref(chk) ));
453 CPPUNIT_ASSERT( m.find_with( 25, less(), std::ref( chk ) ) );
454 chk.m_nExpected = 90;
455 CPPUNIT_ASSERT( m.find( 30, std::ref( chk ) ) );
456 chk.m_nExpected = 54;
457 CPPUNIT_ASSERT( m.find( 27, std::ref( chk ) ) );
459 updateResult = m.update( 10, insert_functor<Map>(), false ) ; // value = 50
460 CPPUNIT_ASSERT( updateResult.first );
461 CPPUNIT_ASSERT( !updateResult.second );
462 chk.m_nExpected = 50;
463 CPPUNIT_ASSERT( m.find( 10, std::ref( chk ) ) );
466 CPPUNIT_ASSERT( !m.contains(100) );
467 CPPUNIT_ASSERT( !m.erase( 100 )) ; // not found
469 CPPUNIT_ASSERT( m.contains(25) );
470 CPPUNIT_ASSERT( check_size( m, 4 ));
471 CPPUNIT_ASSERT( m.erase( 25 ));
472 CPPUNIT_ASSERT( !m.empty() );
473 CPPUNIT_ASSERT( check_size( m, 3 ));
474 CPPUNIT_ASSERT( !m.contains(25) );
475 CPPUNIT_ASSERT( !m.erase( 25 ));
477 CPPUNIT_ASSERT( !m.contains(258) );
478 CPPUNIT_ASSERT( m.insert(258))
479 CPPUNIT_ASSERT( check_size( m, 4 ));
480 CPPUNIT_ASSERT( m.contains(258, less()) );
481 CPPUNIT_ASSERT( m.erase_with( 258, less() ));
482 CPPUNIT_ASSERT( !m.empty() );
483 CPPUNIT_ASSERT( check_size( m, 3 ));
484 CPPUNIT_ASSERT( !m.contains(258) );
485 CPPUNIT_ASSERT( !m.erase_with( 258, less() ));
491 CPPUNIT_ASSERT( !m.contains(29) );
492 CPPUNIT_ASSERT( m.insert(29, 290))
493 CPPUNIT_ASSERT( m.erase_with( 29, less(), std::ref( ext ) ) );
494 CPPUNIT_ASSERT( !m.empty() );
495 CPPUNIT_ASSERT( check_size( m, 3 ));
496 CPPUNIT_ASSERT( nVal == 290 );
498 CPPUNIT_ASSERT( !m.erase_with( 29, less(), std::ref( ext ) ) );
499 CPPUNIT_ASSERT( nVal == -1 );
501 CPPUNIT_ASSERT( m.erase( 30, std::ref( ext ) ) );
502 CPPUNIT_ASSERT( !m.empty() );
503 CPPUNIT_ASSERT( check_size( m, 2 ));
504 CPPUNIT_ASSERT( nVal == 90 );
506 CPPUNIT_ASSERT( !m.erase( 30, std::ref( ext ) ) );
507 CPPUNIT_ASSERT( nVal == -1 );
510 CPPUNIT_ASSERT( m.empty() );
511 CPPUNIT_ASSERT( check_size( m, 0 ));
514 CPPUNIT_ASSERT( m.emplace(126) ) ; // key = 126, val = 0
515 CPPUNIT_ASSERT( m.emplace(137, 731)) ; // key = 137, val = 731
516 CPPUNIT_ASSERT( m.emplace( 149, value_type(941) )) ; // key = 149, val = 941
518 CPPUNIT_ASSERT( !m.empty() );
519 CPPUNIT_ASSERT( check_size( m, 3 ));
522 CPPUNIT_ASSERT( m.find( 126, std::ref(chk) ));
523 chk.m_nExpected = 731;
524 CPPUNIT_ASSERT( m.find_with( 137, less(), std::ref(chk) ));
525 chk.m_nExpected = 941;
526 CPPUNIT_ASSERT( m.find( 149, std::ref(chk) ));
528 CPPUNIT_ASSERT( !m.emplace(126, 621)) ; // already in map
530 CPPUNIT_ASSERT( m.find( 126, std::ref(chk) ));
531 CPPUNIT_ASSERT( !m.empty() );
532 CPPUNIT_ASSERT( check_size( m, 3 ));
535 CPPUNIT_ASSERT( m.empty() );
536 CPPUNIT_ASSERT( check_size( m, 0 ));
540 void test_striped_with2(Map& m)
542 cds::OS::Timer timer;
546 // Iterators is not yet supported
548 //CPPUNIT_ASSERT( m.empty() );
549 //CPPUNIT_ASSERT( check_size( m, 0 ));
553 CPPUNIT_ASSERT( m.empty() );
554 CPPUNIT_ASSERT( check_size( m, 0 ));
557 for ( int i = 0; i < 40000; i++ ) {
561 CPPUNIT_MSG( " Duration=" << timer.duration() );
568 CPPUNIT_ASSERT( m.bucket_count() == 32 );
569 CPPUNIT_ASSERT( m.lock_count() == 32 );
571 test_striped_with2(m);
574 void Striped_hashmap();
577 void Striped_slist();
578 void Striped_boost_list();
579 void Striped_boost_flat_map();
580 void Striped_boost_map();
581 void Striped_boost_unordered_map();
583 void Refinable_hashmap();
584 void Refinable_list();
585 void Refinable_map();
586 void Refinable_slist();
587 void Refinable_boost_list();
588 void Refinable_boost_flat_map();
589 void Refinable_boost_map();
590 void Refinable_boost_unordered_map();
592 CPPUNIT_TEST_SUITE(StripedMapHdrTest)
593 CPPUNIT_TEST(Striped_hashmap)
594 CPPUNIT_TEST(Striped_list)
595 CPPUNIT_TEST(Striped_map)
596 CPPUNIT_TEST(Striped_slist)
597 CPPUNIT_TEST(Striped_boost_list)
598 CPPUNIT_TEST(Striped_boost_flat_map)
599 CPPUNIT_TEST(Striped_boost_map)
600 CPPUNIT_TEST(Striped_boost_unordered_map)
602 CPPUNIT_TEST(Refinable_hashmap)
603 CPPUNIT_TEST(Refinable_list)
604 CPPUNIT_TEST(Refinable_map)
605 CPPUNIT_TEST(Refinable_slist)
606 CPPUNIT_TEST(Refinable_boost_list)
607 CPPUNIT_TEST(Refinable_boost_flat_map)
608 CPPUNIT_TEST(Refinable_boost_map)
609 CPPUNIT_TEST(Refinable_boost_unordered_map)
610 CPPUNIT_TEST_SUITE_END()
615 #endif // #ifndef CDSTEST_HDR_STRIPED_MAP_H