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_MAP_H
32 #define CDSTEST_HDR_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 // MichaelHashSet based on MichaelList
49 class HashMapHdrTest: public CppUnitMini::TestCase
65 value_type( value_type&& v )
69 value_type( value_type const& v )
73 value_type& operator=( value_type const& v )
80 typedef std::pair<key_type const, value_type> pair_type;
84 bool operator ()(int v1, int v2 ) const
91 int operator ()(int v1, int v2 ) const
95 return v1 > v2 ? 1 : 0;
100 bool operator ()(int v1, int v2 ) const
107 size_t operator()( int i ) const
109 return co::v::hash<int>()( i );
112 template <typename T>
113 size_t operator()( T const& i ) const
115 return co::v::hash<int>()( i.nKey );
119 struct simple_item_counter {
122 simple_item_counter()
141 operator size_t() const
147 template <typename Map>
148 struct insert_functor
150 typedef typename Map::value_type pair_type;
153 void operator()( pair_type& item )
155 item.second.m_val = item.first * 3;
159 void operator()( bool bNew, pair_type& item )
162 item.second.m_val = item.first * 2;
164 item.second.m_val = item.first * 5;
171 check_value( int nExpected )
172 : m_nExpected( nExpected )
175 template <typename T>
176 void operator ()( T& pair )
178 CPPUNIT_ASSERT_CURRENT( pair.second.m_val == m_nExpected );
180 template <typename T, typename Q>
181 void operator ()( T& pair, Q )
183 CPPUNIT_ASSERT_CURRENT( pair.second.m_val == m_nExpected );
187 struct extract_functor
190 void operator()( pair_type const& val )
192 *m_pVal = val.second.m_val;
199 other_item( int key )
206 bool operator ()(int v1, other_item const& v2 ) const
210 bool operator ()(other_item const& v1, int v2 ) const
225 CPPUNIT_ASSERT( m.empty() );
227 const int nLimit = 100;
228 typename Map::guarded_ptr gp;
229 int arrRandom[nLimit];
230 for ( int i = 0; i < nLimit; ++i )
232 shuffle( arrRandom, arrRandom + nLimit );
234 for ( int i = 0; i < nLimit; ++i )
235 CPPUNIT_ASSERT( m.insert( arrRandom[i], arrRandom[i] ));
237 for ( int i = 0; i < nLimit; ++i ) {
238 int nKey = arrRandom[i];
240 CPPUNIT_ASSERT( gp );
241 CPPUNIT_ASSERT( !gp.empty());
242 CPPUNIT_CHECK( gp->first == nKey );
243 CPPUNIT_CHECK( gp->second.m_val == nKey );
246 gp = m.extract( nKey );
247 CPPUNIT_ASSERT( gp );
248 CPPUNIT_ASSERT( !gp.empty());
249 CPPUNIT_CHECK( gp->first == nKey );
250 CPPUNIT_CHECK( gp->second.m_val == nKey );
254 CPPUNIT_CHECK( !gp );
256 CPPUNIT_CHECK( !m.extract(nKey));
257 CPPUNIT_CHECK( gp.empty());
259 CPPUNIT_ASSERT( m.empty() );
261 for ( int i = 0; i < nLimit; ++i )
262 CPPUNIT_ASSERT( m.insert( arrRandom[i], arrRandom[i] ));
264 for ( int i = 0; i < nLimit; ++i ) {
265 int nKey = arrRandom[i];
266 gp = m.get_with( other_item( nKey ), other_less() );
267 CPPUNIT_ASSERT( gp );
268 CPPUNIT_ASSERT( !gp.empty());
269 CPPUNIT_CHECK( gp->first == nKey );
270 CPPUNIT_CHECK( gp->second.m_val == nKey );
273 gp = m.extract_with( other_item( nKey ), other_less() );
274 CPPUNIT_ASSERT( gp );
275 CPPUNIT_ASSERT( !gp.empty());
276 CPPUNIT_CHECK( gp->first == nKey );
277 CPPUNIT_CHECK( gp->second.m_val == nKey );
280 gp = m.get_with( other_item( nKey ), other_less() );
281 CPPUNIT_CHECK( !gp );
283 CPPUNIT_CHECK( !m.extract_with(other_item(nKey), other_less() ));
284 CPPUNIT_CHECK( gp.empty());
286 CPPUNIT_ASSERT( m.empty() );
302 typedef typename Map::gc rcu;
303 typedef typename Map::rcu_lock rcu_lock;
304 typedef typename Map::value_type value_type;
305 typename Map::exempt_ptr ep;
307 static size_t const nLimit = 100;
309 for ( size_t i = 0; i < nLimit; ++i )
311 shuffle( arr, arr + nLimit );
313 for ( size_t i = 0; i < nLimit; ++i )
314 CPPUNIT_ASSERT( m.insert( arr[i], arr[i] ));
316 for ( size_t i = 0; i < nLimit; i += 2 ) {
321 pVal = m.get( nKey );
322 CPPUNIT_ASSERT( pVal != nullptr );
323 CPPUNIT_CHECK( pVal->first == nKey );
324 CPPUNIT_CHECK( pVal->second.m_val == nKey );
326 ep = m.extract( nKey );
327 CPPUNIT_ASSERT( ep );
328 CPPUNIT_ASSERT( !ep.empty() );
329 CPPUNIT_CHECK( pVal->first == ep->first );
330 CPPUNIT_CHECK( pVal->second.m_val == ep->second.m_val );
335 CPPUNIT_CHECK( m.get( nKey ) == nullptr );
336 ep = m.extract( nKey );
337 CPPUNIT_CHECK( !ep );
338 CPPUNIT_CHECK( ep.empty() );
341 pVal = m.get_with( other_item(nKey), other_less() );
342 CPPUNIT_ASSERT( pVal != nullptr );
343 CPPUNIT_CHECK( pVal->first == nKey );
344 CPPUNIT_CHECK( pVal->second.m_val == nKey );
346 ep = m.extract_with( other_item( nKey ), other_less() );
347 CPPUNIT_ASSERT( ep );
348 CPPUNIT_ASSERT( !ep.empty() );
349 CPPUNIT_CHECK( pVal->first == ep->first );
350 CPPUNIT_CHECK( pVal->second.m_val == (*ep).second.m_val );
355 CPPUNIT_CHECK( m.get_with( other_item(nKey), other_less() ) == nullptr );
356 CPPUNIT_CHECK( !m.extract_with( other_item(nKey), other_less() ));
357 CPPUNIT_CHECK( ep.empty() );
360 CPPUNIT_CHECK( m.empty() );
361 CPPUNIT_CHECK( check_size( m, 0 ));
364 CPPUNIT_CHECK( m.get( int(nLimit / 2) ) == nullptr );
365 ep = m.extract( int( nLimit / 2 ) );
366 CPPUNIT_CHECK( !ep );
367 CPPUNIT_CHECK( ep.empty() );
376 void test_rcu_michael_list()
384 typedef typename Map::gc rcu;
385 typedef typename Map::rcu_lock rcu_lock;
386 typedef typename Map::value_type value_type;
387 typename Map::exempt_ptr ep;
388 typename Map::raw_ptr gp;
390 static size_t const nLimit = 100;
392 for ( size_t i = 0; i < nLimit; ++i )
394 shuffle( arr, arr + nLimit );
396 for ( size_t i = 0; i < nLimit; ++i )
397 CPPUNIT_ASSERT( m.insert( arr[i], arr[i] ));
399 for ( size_t i = 0; i < nLimit; i += 2 ) {
404 CPPUNIT_ASSERT( gp );
405 CPPUNIT_CHECK( gp->first == nKey );
406 CPPUNIT_CHECK( gp->second.m_val == nKey );
410 ep = m.extract( nKey );
411 CPPUNIT_ASSERT( ep );
412 CPPUNIT_ASSERT( !ep.empty() );
413 CPPUNIT_CHECK( nKey == ep->first );
414 CPPUNIT_CHECK( nKey == ep->second.m_val );
419 CPPUNIT_CHECK( !m.get( nKey ));
421 ep = m.extract( nKey );
422 CPPUNIT_CHECK( !ep );
423 CPPUNIT_CHECK( ep.empty() );
428 gp = m.get_with( other_item(nKey), other_less() );
429 CPPUNIT_ASSERT( gp );
430 CPPUNIT_CHECK( gp->first == nKey );
431 CPPUNIT_CHECK( gp->second.m_val == nKey );
435 ep = m.extract_with( other_item( nKey ), other_less() );
436 CPPUNIT_ASSERT( ep );
437 CPPUNIT_ASSERT( !ep.empty() );
438 CPPUNIT_CHECK( nKey == ep->first );
439 CPPUNIT_CHECK( nKey == (*ep).second.m_val );
444 CPPUNIT_CHECK( !m.get_with( other_item(nKey), other_less() ));
446 CPPUNIT_CHECK( !m.extract_with( other_item(nKey), other_less() ));
447 CPPUNIT_CHECK( ep.empty() );
449 CPPUNIT_CHECK( m.empty() );
450 CPPUNIT_CHECK( check_size( m, 0 ));
453 CPPUNIT_CHECK( !m.get( int(nLimit / 2) ));
455 ep = m.extract( int( nLimit / 2 ) );
456 CPPUNIT_CHECK( !ep );
457 CPPUNIT_CHECK( ep.empty() );
465 void test_rcu_split_list()
467 test_rcu_michael_list<Map>();
471 void test_int_with( Map& m )
473 std::pair<bool, bool> updateResult;
476 CPPUNIT_ASSERT( m.empty() );
477 CPPUNIT_ASSERT( check_size( m, 0 ));
478 CPPUNIT_ASSERT( !m.contains(25) );
479 CPPUNIT_ASSERT( m.insert( 25 ) ) ; // value = 0
480 CPPUNIT_ASSERT( m.contains(25) );
481 CPPUNIT_ASSERT( !m.empty() );
482 CPPUNIT_ASSERT( check_size( m, 1 ));
483 CPPUNIT_ASSERT( m.contains(25) );
485 CPPUNIT_ASSERT( !m.insert( 25 ) );
486 CPPUNIT_ASSERT( !m.empty() );
487 CPPUNIT_ASSERT( check_size( m, 1 ));
489 CPPUNIT_ASSERT( !m.contains(10, less()) );
490 CPPUNIT_ASSERT( m.insert( 10, 10 ) );
491 CPPUNIT_ASSERT( !m.empty() );
492 CPPUNIT_ASSERT( check_size( m, 2 ));
493 CPPUNIT_ASSERT( m.contains(10, less()) );
495 CPPUNIT_ASSERT( !m.insert( 10, 20 ) );
496 CPPUNIT_ASSERT( !m.empty() );
497 CPPUNIT_ASSERT( check_size( m, 2 ));
499 CPPUNIT_ASSERT( !m.contains(30) );
500 CPPUNIT_ASSERT( m.insert_with( 30, insert_functor<Map>() ) ) ; // value = 90
501 CPPUNIT_ASSERT( !m.empty() );
502 CPPUNIT_ASSERT( check_size( m, 3 ));
503 CPPUNIT_ASSERT( m.contains(30) );
505 CPPUNIT_ASSERT( !m.insert_with( 10, insert_functor<Map>() ) );
506 CPPUNIT_ASSERT( !m.insert_with( 25, insert_functor<Map>() ) );
507 CPPUNIT_ASSERT( !m.insert_with( 30, insert_functor<Map>() ) );
510 CPPUNIT_ASSERT( !m.contains(27) );
511 updateResult = m.update(27, insert_functor<Map>(), false);
512 CPPUNIT_ASSERT(!updateResult.first);
513 CPPUNIT_ASSERT(!updateResult.second);
514 CPPUNIT_ASSERT(!m.contains(27));
516 updateResult = m.update( 27, insert_functor<Map>() ) ; // value = 54
517 CPPUNIT_ASSERT( updateResult.first );
518 CPPUNIT_ASSERT( updateResult.second );
519 CPPUNIT_ASSERT( m.contains(27) );
523 CPPUNIT_ASSERT( m.find( 10, std::ref(chk) ));
525 CPPUNIT_ASSERT( m.find_with( 25, less(), std::ref( chk ) ) );
526 chk.m_nExpected = 90;
527 CPPUNIT_ASSERT( m.find( 30, std::ref( chk ) ) );
528 chk.m_nExpected = 54;
529 CPPUNIT_ASSERT( m.find( 27, std::ref( chk ) ) );
531 updateResult = m.update( 10, insert_functor<Map>() ) ; // value = 50
532 CPPUNIT_ASSERT( updateResult.first );
533 CPPUNIT_ASSERT( !updateResult.second );
534 chk.m_nExpected = 50;
535 CPPUNIT_ASSERT( m.find( 10, std::ref( chk ) ) );
538 CPPUNIT_ASSERT( !m.contains(100) );
539 CPPUNIT_ASSERT( !m.erase( 100 )) ; // not found
541 CPPUNIT_ASSERT( m.contains(25) );
542 CPPUNIT_ASSERT( check_size( m, 4 ));
543 CPPUNIT_ASSERT( m.erase( 25 ));
544 CPPUNIT_ASSERT( !m.empty() );
545 CPPUNIT_ASSERT( check_size( m, 3 ));
546 CPPUNIT_ASSERT( !m.contains(25) );
547 CPPUNIT_ASSERT( !m.erase( 25 ));
549 CPPUNIT_ASSERT( !m.contains(258) );
550 CPPUNIT_ASSERT( m.insert(258))
551 CPPUNIT_ASSERT( check_size( m, 4 ));
552 CPPUNIT_ASSERT( m.contains(258, less()) );
553 CPPUNIT_ASSERT( m.erase_with( 258, less() ));
554 CPPUNIT_ASSERT( !m.empty() );
555 CPPUNIT_ASSERT( check_size( m, 3 ));
556 CPPUNIT_ASSERT( !m.contains(258) );
557 CPPUNIT_ASSERT( !m.erase_with( 258, less() ));
563 CPPUNIT_ASSERT( !m.contains(29) );
564 CPPUNIT_ASSERT( m.insert(29, 290));
565 CPPUNIT_ASSERT( check_size( m, 4 ));
566 CPPUNIT_ASSERT( m.erase_with( 29, less(), std::ref( ext ) ) );
567 CPPUNIT_ASSERT( !m.empty() );
568 CPPUNIT_ASSERT( check_size( m, 3 ));
569 CPPUNIT_ASSERT( nVal == 290 );
571 CPPUNIT_ASSERT( !m.erase_with( 29, less(), std::ref( ext ) ) );
572 CPPUNIT_ASSERT( nVal == -1 );
574 CPPUNIT_ASSERT( m.erase( 30, std::ref( ext ) ) );
575 CPPUNIT_ASSERT( !m.empty() );
576 CPPUNIT_ASSERT( check_size( m, 2 ));
577 CPPUNIT_ASSERT( nVal == 90 );
579 CPPUNIT_ASSERT( !m.erase( 30, std::ref( ext ) ) );
580 CPPUNIT_ASSERT( nVal == -1 );
583 CPPUNIT_ASSERT( m.empty() );
584 CPPUNIT_ASSERT( check_size( m, 0 ));
587 CPPUNIT_ASSERT( m.emplace(126) ) ; // key = 126, val = 0
588 CPPUNIT_ASSERT( m.emplace(137, 731)) ; // key = 137, val = 731
589 CPPUNIT_ASSERT( m.emplace( 149, value_type(941) )) ; // key = 149, val = 941
591 CPPUNIT_ASSERT( !m.empty() );
592 CPPUNIT_ASSERT( check_size( m, 3 ));
595 CPPUNIT_ASSERT( m.find( 126, std::ref(chk) ));
596 chk.m_nExpected = 731;
597 CPPUNIT_ASSERT( m.find_with( 137, less(), std::ref(chk) ));
598 chk.m_nExpected = 941;
599 CPPUNIT_ASSERT( m.find( 149, std::ref(chk) ));
601 CPPUNIT_ASSERT( !m.emplace(126, 621)) ; // already in map
603 CPPUNIT_ASSERT( m.find( 126, std::ref(chk) ));
604 CPPUNIT_ASSERT( !m.empty() );
605 CPPUNIT_ASSERT( check_size( m, 3 ));
608 CPPUNIT_ASSERT( m.empty() );
609 CPPUNIT_ASSERT( check_size( m, 0 ));
616 typedef typename Map::iterator iterator;
617 typedef typename Map::const_iterator const_iterator;
622 CPPUNIT_ASSERT( m.empty() );
623 CPPUNIT_ASSERT( check_size( m, 0 ));
625 CPPUNIT_ASSERT( m.contains(10) == m.end() );
626 iterator it = m.insert( 10 );
627 CPPUNIT_ASSERT( it != m.end() );
628 CPPUNIT_ASSERT( !m.empty() );
629 CPPUNIT_ASSERT( check_size( m, 1 ));
630 CPPUNIT_ASSERT( m.contains(10) == it );
631 CPPUNIT_ASSERT( it->first == 10 );
632 CPPUNIT_ASSERT( it->second.m_val == 0 );
634 CPPUNIT_ASSERT( m.contains(100) == m.end() );
635 it = m.insert( 100, 200 );
636 CPPUNIT_ASSERT( it != m.end() );
637 CPPUNIT_ASSERT( !m.empty() );
638 CPPUNIT_ASSERT( check_size( m, 2 ));
639 CPPUNIT_ASSERT( m.contains(100, less()) == it );
640 CPPUNIT_ASSERT( it->first == 100 );
641 CPPUNIT_ASSERT( it->second.m_val == 200 );
643 CPPUNIT_ASSERT( m.contains(55) == m.end() );
644 it = m.insert_with( 55, insert_functor<Map>() );
645 CPPUNIT_ASSERT( it != m.end() );
646 CPPUNIT_ASSERT( !m.empty() );
647 CPPUNIT_ASSERT( check_size( m, 3 ));
648 CPPUNIT_ASSERT( m.contains(55) == it );
649 CPPUNIT_ASSERT( it->first == 55 );
650 CPPUNIT_ASSERT( it->second.m_val == 55 * 3 );
652 CPPUNIT_ASSERT( m.insert( 55 ) == m.end() );
653 CPPUNIT_ASSERT( m.insert( 55, 10 ) == m.end() );
654 CPPUNIT_ASSERT( m.insert_with( 55, insert_functor<Map>()) == m.end() );
656 CPPUNIT_ASSERT( m.contains(10) != m.end() );
657 std::pair<iterator, bool> updateResult = m.update(10, false);
658 CPPUNIT_ASSERT( updateResult.first != m.end() );
659 CPPUNIT_ASSERT( !updateResult.second );
660 CPPUNIT_ASSERT( !m.empty() );
661 updateResult.first->second.m_val = updateResult.first->first * 5;
662 CPPUNIT_ASSERT( check_size( m, 3 ));
663 CPPUNIT_ASSERT( m.contains(10) == updateResult.first );
665 CPPUNIT_ASSERT( it != m.end() );
666 CPPUNIT_ASSERT( it->second.m_val == 50 );
668 CPPUNIT_ASSERT( m.contains(120) == m.end() );
669 updateResult = m.update(120, false);
670 CPPUNIT_ASSERT(updateResult.first == m.end());
671 CPPUNIT_ASSERT(!updateResult.second);
672 updateResult = m.update( 120 );
673 CPPUNIT_ASSERT( updateResult.first != m.end() );
674 CPPUNIT_ASSERT( updateResult.second );
675 CPPUNIT_ASSERT( !m.empty() );
676 CPPUNIT_ASSERT( check_size( m, 4 ));
677 updateResult.first->second.m_val = updateResult.first->first * 5;
678 CPPUNIT_ASSERT( m.contains(120, less()) == updateResult.first );
679 it = m.contains(120, less());
680 CPPUNIT_ASSERT( it != m.end() );
681 CPPUNIT_ASSERT( it->second.m_val == 120 * 5 );
682 CPPUNIT_ASSERT( m.contains(120, less()) == m.contains(120) );
685 it = m.emplace( 151 ) ; // key = 151, val = 0
686 CPPUNIT_ASSERT( it != m.end() );
687 CPPUNIT_ASSERT( it->first == 151 );
688 CPPUNIT_ASSERT( it->second.m_val == 0 );
690 it = m.emplace( 174, 471 ) ; // key == 174, val = 471
691 CPPUNIT_ASSERT( it != m.end() );
692 CPPUNIT_ASSERT( it->first == 174 );
693 CPPUNIT_ASSERT( it->second.m_val == 471 );
695 it = m.emplace( 190, value_type(91)) ; // key == 190, val = 19
696 CPPUNIT_ASSERT( it != m.end() );
697 CPPUNIT_ASSERT( it->first == 190 );
698 CPPUNIT_ASSERT( it->second.m_val == 91 );
700 it = m.emplace( 151, 1051 );
701 CPPUNIT_ASSERT( it == m.end());
703 it = m.contains( 174 );
704 CPPUNIT_ASSERT( it != m.end() );
705 CPPUNIT_ASSERT( it->first == 174 );
706 CPPUNIT_ASSERT( it->second.m_val == 471 );
708 it = m.contains( 190 );
709 CPPUNIT_ASSERT( it != m.end() );
710 CPPUNIT_ASSERT( it->first == 190 );
711 CPPUNIT_ASSERT( it->second.m_val == 91 );
713 it = m.contains( 151 );
714 CPPUNIT_ASSERT( it != m.end() );
715 CPPUNIT_ASSERT( it->first == 151 );
716 CPPUNIT_ASSERT( it->second.m_val == 0 );
724 for ( int i = 0; i < 500; ++i ) {
725 CPPUNIT_ASSERT( m.insert( i, i * 2 ) != m.end() );
727 CPPUNIT_ASSERT( check_size( m, 500 ));
730 typename Map::iterator it( m.begin() );
731 typename Map::const_iterator cit( m.cbegin() );
732 CPPUNIT_CHECK( it == cit );
733 CPPUNIT_CHECK( it != m.end() );
734 CPPUNIT_CHECK( it != m.cend() );
735 CPPUNIT_CHECK( cit != m.end() );
736 CPPUNIT_CHECK( cit != m.cend() );
738 CPPUNIT_CHECK( it != cit );
739 CPPUNIT_CHECK( it != m.end() );
740 CPPUNIT_CHECK( it != m.cend() );
741 CPPUNIT_CHECK( cit != m.end() );
742 CPPUNIT_CHECK( cit != m.cend() );
744 CPPUNIT_CHECK( it == cit );
745 CPPUNIT_CHECK( it != m.end() );
746 CPPUNIT_CHECK( it != m.cend() );
747 CPPUNIT_CHECK( cit != m.end() );
748 CPPUNIT_CHECK( cit != m.cend() );
752 for ( iterator it = m.begin(), itEnd = m.end(); it != itEnd; ++it ) {
754 CPPUNIT_CHECK( it2 == it );
755 CPPUNIT_CHECK( it2 != itEnd );
756 CPPUNIT_ASSERT( it->first * 2 == (*it).second.m_val );
757 it->second = it->first;
760 Map const& refMap = m;
761 for ( const_iterator it = refMap.begin(), itEnd = refMap.end(); it != itEnd; ++it ) {
762 CPPUNIT_ASSERT( it->first == it->second.m_val );
763 CPPUNIT_ASSERT( (*it).first == (*it).second.m_val );
769 void test_int_nogc_unordered()
771 typedef typename Map::iterator iterator;
772 typedef typename Map::const_iterator const_iterator;
777 CPPUNIT_ASSERT( m.empty() );
778 CPPUNIT_ASSERT( check_size( m, 0 ));
780 CPPUNIT_ASSERT( m.contains(10) == m.end() );
781 iterator it = m.insert( 10 );
782 CPPUNIT_ASSERT( it != m.end() );
783 CPPUNIT_ASSERT( !m.empty() );
784 CPPUNIT_ASSERT( check_size( m, 1 ));
785 CPPUNIT_ASSERT( m.contains(10) == it );
786 CPPUNIT_ASSERT( it->first == 10 );
787 CPPUNIT_ASSERT( it->second.m_val == 0 );
789 CPPUNIT_ASSERT( m.contains(100) == m.end() );
790 it = m.insert( 100, 200 );
791 CPPUNIT_ASSERT( it != m.end() );
792 CPPUNIT_ASSERT( !m.empty() );
793 CPPUNIT_ASSERT( check_size( m, 2 ));
794 CPPUNIT_ASSERT( m.contains(100, equal()) == it );
795 CPPUNIT_ASSERT( it->first == 100 );
796 CPPUNIT_ASSERT( it->second.m_val == 200 );
798 CPPUNIT_ASSERT( m.contains(55) == m.end() );
799 it = m.insert_with( 55, insert_functor<Map>() );
800 CPPUNIT_ASSERT( it != m.end() );
801 CPPUNIT_ASSERT( !m.empty() );
802 CPPUNIT_ASSERT( check_size( m, 3 ));
803 CPPUNIT_ASSERT( m.contains(55) == it );
804 CPPUNIT_ASSERT( it->first == 55 );
805 CPPUNIT_ASSERT( it->second.m_val == 55 * 3 );
807 CPPUNIT_ASSERT( m.insert( 55 ) == m.end() );
808 CPPUNIT_ASSERT( m.insert( 55, 10 ) == m.end() );
809 CPPUNIT_ASSERT( m.insert_with( 55, insert_functor<Map>()) == m.end() );
811 CPPUNIT_ASSERT( m.contains(10) != m.end() );
812 std::pair<iterator, bool> updateResult = m.update( 10 );
813 CPPUNIT_ASSERT( updateResult.first != m.end() );
814 CPPUNIT_ASSERT( !updateResult.second );
815 CPPUNIT_ASSERT( !m.empty() );
816 updateResult.first->second.m_val = updateResult.first->first * 5;
817 CPPUNIT_ASSERT( check_size( m, 3 ));
818 CPPUNIT_ASSERT( m.contains(10) == updateResult.first );
820 CPPUNIT_ASSERT( it != m.end() );
821 CPPUNIT_ASSERT( it->second.m_val == 50 );
823 CPPUNIT_ASSERT( m.contains(120) == m.end() );
824 updateResult = m.update(120, false);
825 CPPUNIT_ASSERT(updateResult.first == m.end());
826 CPPUNIT_ASSERT(!updateResult.second);
827 updateResult = m.update( 120, true );
828 CPPUNIT_ASSERT( updateResult.first != m.end() );
829 CPPUNIT_ASSERT( updateResult.second );
830 CPPUNIT_ASSERT( !m.empty() );
831 CPPUNIT_ASSERT( check_size( m, 4 ));
832 updateResult.first->second.m_val = updateResult.first->first * 5;
833 CPPUNIT_ASSERT( m.contains(120, equal()) == updateResult.first );
834 it = m.contains(120, equal());
835 CPPUNIT_ASSERT( it != m.end() );
836 CPPUNIT_ASSERT( it->second.m_val == 120 * 5 );
837 CPPUNIT_ASSERT( m.contains(120, equal()) == m.contains(120) );
840 it = m.emplace( 151 ) ; // key = 151, val = 0
841 CPPUNIT_ASSERT( it != m.end() );
842 CPPUNIT_ASSERT( it->first == 151 );
843 CPPUNIT_ASSERT( it->second.m_val == 0 );
845 it = m.emplace( 174, 471 ) ; // key == 174, val = 471
846 CPPUNIT_ASSERT( it != m.end() );
847 CPPUNIT_ASSERT( it->first == 174 );
848 CPPUNIT_ASSERT( it->second.m_val == 471 );
850 it = m.emplace( 190, value_type(91)) ; // key == 190, val = 19
851 CPPUNIT_ASSERT( it != m.end() );
852 CPPUNIT_ASSERT( it->first == 190 );
853 CPPUNIT_ASSERT( it->second.m_val == 91 );
855 it = m.emplace( 151, 1051 );
856 CPPUNIT_ASSERT( it == m.end());
858 it = m.contains( 174 );
859 CPPUNIT_ASSERT( it != m.end() );
860 CPPUNIT_ASSERT( it->first == 174 );
861 CPPUNIT_ASSERT( it->second.m_val == 471 );
863 it = m.contains( 190 );
864 CPPUNIT_ASSERT( it != m.end() );
865 CPPUNIT_ASSERT( it->first == 190 );
866 CPPUNIT_ASSERT( it->second.m_val == 91 );
868 it = m.contains( 151 );
869 CPPUNIT_ASSERT( it != m.end() );
870 CPPUNIT_ASSERT( it->first == 151 );
871 CPPUNIT_ASSERT( it->second.m_val == 0 );
879 for ( int i = 0; i < 500; ++i ) {
880 CPPUNIT_ASSERT( m.insert( i, i * 2 ) != m.end() );
882 CPPUNIT_ASSERT( check_size( m, 500 ));
885 typename Map::iterator it( m.begin() );
886 typename Map::const_iterator cit( m.cbegin() );
887 CPPUNIT_CHECK( it == cit );
888 CPPUNIT_CHECK( it != m.end() );
889 CPPUNIT_CHECK( it != m.cend() );
890 CPPUNIT_CHECK( cit != m.end() );
891 CPPUNIT_CHECK( cit != m.cend() );
893 CPPUNIT_CHECK( it != cit );
894 CPPUNIT_CHECK( it != m.end() );
895 CPPUNIT_CHECK( it != m.cend() );
896 CPPUNIT_CHECK( cit != m.end() );
897 CPPUNIT_CHECK( cit != m.cend() );
899 CPPUNIT_CHECK( it == cit );
900 CPPUNIT_CHECK( it != m.end() );
901 CPPUNIT_CHECK( it != m.cend() );
902 CPPUNIT_CHECK( cit != m.end() );
903 CPPUNIT_CHECK( cit != m.cend() );
907 for ( iterator it = m.begin(), itEnd = m.end(); it != itEnd; ++it ) {
909 CPPUNIT_CHECK( it2 == it );
910 CPPUNIT_CHECK( it2 != itEnd );
911 CPPUNIT_ASSERT( it->first * 2 == (*it).second.m_val );
912 it->second = it->first;
915 Map const& refMap = m;
916 for ( const_iterator it = refMap.begin(), itEnd = refMap.end(); it != itEnd; ++it ) {
917 CPPUNIT_ASSERT( it->first == it->second.m_val );
918 CPPUNIT_ASSERT( (*it).first == (*it).second.m_val );
926 typedef typename Map::iterator iterator;
927 typedef typename Map::const_iterator const_iterator;
931 const int nMaxCount = 500;
932 for ( int i = 0; i < nMaxCount; ++i ) {
933 CPPUNIT_ASSERT( s.insert( i, i * 2 ));
937 typename Map::iterator it( s.begin() );
938 typename Map::const_iterator cit( s.cbegin() );
939 CPPUNIT_CHECK( it == cit );
940 CPPUNIT_CHECK( it != s.end() );
941 CPPUNIT_CHECK( it != s.cend() );
942 CPPUNIT_CHECK( cit != s.end() );
943 CPPUNIT_CHECK( cit != s.cend() );
945 CPPUNIT_CHECK( it != cit );
946 CPPUNIT_CHECK( it != s.end() );
947 CPPUNIT_CHECK( it != s.cend() );
948 CPPUNIT_CHECK( cit != s.end() );
949 CPPUNIT_CHECK( cit != s.cend() );
951 CPPUNIT_CHECK( it == cit );
952 CPPUNIT_CHECK( it != s.end() );
953 CPPUNIT_CHECK( it != s.cend() );
954 CPPUNIT_CHECK( cit != s.end() );
955 CPPUNIT_CHECK( cit != s.cend() );
959 for ( iterator it = s.begin(), itEnd = s.end(); it != itEnd; ++it ) {
960 CPPUNIT_ASSERT( it->first * 2 == it->second.m_val );
961 CPPUNIT_ASSERT( (*it).first * 2 == (*it).second.m_val );
962 it->second.m_val = it->first;
965 CPPUNIT_ASSERT( nCount == nMaxCount );
967 Map const& refSet = s;
969 for ( const_iterator it = refSet.begin(), itEnd = refSet.end(); it != itEnd; ++it ) {
970 CPPUNIT_ASSERT( it->first == it->second.m_val );
971 CPPUNIT_ASSERT( (*it).first == (*it).second.m_val );
974 CPPUNIT_ASSERT( nCount == nMaxCount );
978 void Michael_HP_cmp();
979 void Michael_HP_less();
980 void Michael_HP_cmpmix();
982 void Michael_DHP_cmp();
983 void Michael_DHP_less();
984 void Michael_DHP_cmpmix();
986 void Michael_RCU_GPI_cmp();
987 void Michael_RCU_GPI_less();
988 void Michael_RCU_GPI_cmpmix();
990 void Michael_RCU_GPB_cmp();
991 void Michael_RCU_GPB_less();
992 void Michael_RCU_GPB_cmpmix();
994 void Michael_RCU_GPT_cmp();
995 void Michael_RCU_GPT_less();
996 void Michael_RCU_GPT_cmpmix();
998 void Michael_RCU_SHB_cmp();
999 void Michael_RCU_SHB_less();
1000 void Michael_RCU_SHB_cmpmix();
1002 void Michael_RCU_SHT_cmp();
1003 void Michael_RCU_SHT_less();
1004 void Michael_RCU_SHT_cmpmix();
1006 void Michael_nogc_cmp();
1007 void Michael_nogc_less();
1008 void Michael_nogc_cmpmix();
1011 void Lazy_HP_less();
1012 void Lazy_HP_cmpmix();
1014 void Lazy_DHP_cmp();
1015 void Lazy_DHP_less();
1016 void Lazy_DHP_cmpmix();
1018 void Lazy_RCU_GPI_cmp();
1019 void Lazy_RCU_GPI_less();
1020 void Lazy_RCU_GPI_cmpmix();
1022 void Lazy_RCU_GPB_cmp();
1023 void Lazy_RCU_GPB_less();
1024 void Lazy_RCU_GPB_cmpmix();
1026 void Lazy_RCU_GPT_cmp();
1027 void Lazy_RCU_GPT_less();
1028 void Lazy_RCU_GPT_cmpmix();
1030 void Lazy_RCU_SHB_cmp();
1031 void Lazy_RCU_SHB_less();
1032 void Lazy_RCU_SHB_cmpmix();
1034 void Lazy_RCU_SHT_cmp();
1035 void Lazy_RCU_SHT_less();
1036 void Lazy_RCU_SHT_cmpmix();
1038 void Lazy_nogc_cmp();
1039 void Lazy_nogc_less();
1040 void Lazy_nogc_equal();
1041 void Lazy_nogc_cmpmix();
1043 void Split_HP_cmp();
1044 void Split_HP_less();
1045 void Split_HP_cmpmix();
1046 void Split_HP_cmpmix_stat();
1048 void Split_DHP_cmp();
1049 void Split_DHP_less();
1050 void Split_DHP_cmpmix();
1051 void Split_DHP_cmpmix_stat();
1053 void Split_RCU_GPI_cmp();
1054 void Split_RCU_GPI_less();
1055 void Split_RCU_GPI_cmpmix();
1056 void Split_RCU_GPI_cmpmix_stat();
1058 void Split_RCU_GPB_cmp();
1059 void Split_RCU_GPB_less();
1060 void Split_RCU_GPB_cmpmix();
1061 void Split_RCU_GPB_cmpmix_stat();
1063 void Split_RCU_GPT_cmp();
1064 void Split_RCU_GPT_less();
1065 void Split_RCU_GPT_cmpmix();
1066 void Split_RCU_GPT_cmpmix_stat();
1068 void Split_RCU_SHB_cmp();
1069 void Split_RCU_SHB_less();
1070 void Split_RCU_SHB_cmpmix();
1071 void Split_RCU_SHB_cmpmix_stat();
1073 void Split_RCU_SHT_cmp();
1074 void Split_RCU_SHT_less();
1075 void Split_RCU_SHT_cmpmix();
1076 void Split_RCU_SHT_cmpmix_stat();
1078 void Split_nogc_cmp();
1079 void Split_nogc_less();
1080 void Split_nogc_cmpmix();
1081 void Split_nogc_cmpmix_stat();
1083 void Split_Lazy_HP_cmp();
1084 void Split_Lazy_HP_less();
1085 void Split_Lazy_HP_cmpmix();
1086 void Split_Lazy_HP_cmpmix_stat();
1088 void Split_Lazy_DHP_cmp();
1089 void Split_Lazy_DHP_less();
1090 void Split_Lazy_DHP_cmpmix();
1091 void Split_Lazy_DHP_cmpmix_stat();
1093 void Split_Lazy_RCU_GPI_cmp();
1094 void Split_Lazy_RCU_GPI_less();
1095 void Split_Lazy_RCU_GPI_cmpmix();
1096 void Split_Lazy_RCU_GPI_cmpmix_stat();
1098 void Split_Lazy_RCU_GPB_cmp();
1099 void Split_Lazy_RCU_GPB_less();
1100 void Split_Lazy_RCU_GPB_cmpmix();
1101 void Split_Lazy_RCU_GPB_cmpmix_stat();
1103 void Split_Lazy_RCU_GPT_cmp();
1104 void Split_Lazy_RCU_GPT_less();
1105 void Split_Lazy_RCU_GPT_cmpmix();
1106 void Split_Lazy_RCU_GPT_cmpmix_stat();
1108 void Split_Lazy_RCU_SHB_cmp();
1109 void Split_Lazy_RCU_SHB_less();
1110 void Split_Lazy_RCU_SHB_cmpmix();
1111 void Split_Lazy_RCU_SHB_cmpmix_stat();
1113 void Split_Lazy_RCU_SHT_cmp();
1114 void Split_Lazy_RCU_SHT_less();
1115 void Split_Lazy_RCU_SHT_cmpmix();
1116 void Split_Lazy_RCU_SHT_cmpmix_stat();
1118 void Split_Lazy_nogc_cmp();
1119 void Split_Lazy_nogc_less();
1120 void Split_Lazy_nogc_cmpmix();
1121 void Split_Lazy_nogc_cmpmix_stat();
1123 CPPUNIT_TEST_SUITE(HashMapHdrTest)
1124 CPPUNIT_TEST(Michael_HP_cmp)
1125 CPPUNIT_TEST(Michael_HP_less)
1126 CPPUNIT_TEST(Michael_HP_cmpmix)
1128 CPPUNIT_TEST(Michael_DHP_cmp)
1129 CPPUNIT_TEST(Michael_DHP_less)
1130 CPPUNIT_TEST(Michael_DHP_cmpmix)
1132 CPPUNIT_TEST(Michael_RCU_GPI_cmp)
1133 CPPUNIT_TEST(Michael_RCU_GPI_less)
1134 CPPUNIT_TEST(Michael_RCU_GPI_cmpmix)
1136 CPPUNIT_TEST(Michael_RCU_GPB_cmp)
1137 CPPUNIT_TEST(Michael_RCU_GPB_less)
1138 CPPUNIT_TEST(Michael_RCU_GPB_cmpmix)
1140 CPPUNIT_TEST(Michael_RCU_SHT_cmp)
1141 CPPUNIT_TEST(Michael_RCU_SHT_less)
1142 CPPUNIT_TEST(Michael_RCU_SHT_cmpmix)
1144 CPPUNIT_TEST(Michael_RCU_SHB_cmp)
1145 CPPUNIT_TEST(Michael_RCU_SHB_less)
1146 CPPUNIT_TEST(Michael_RCU_SHB_cmpmix)
1148 CPPUNIT_TEST(Michael_RCU_GPT_cmp)
1149 CPPUNIT_TEST(Michael_RCU_GPT_less)
1150 CPPUNIT_TEST(Michael_RCU_GPT_cmpmix)
1152 CPPUNIT_TEST(Michael_nogc_cmp)
1153 CPPUNIT_TEST(Michael_nogc_less)
1154 CPPUNIT_TEST(Michael_nogc_cmpmix)
1156 CPPUNIT_TEST(Lazy_HP_cmp)
1157 CPPUNIT_TEST(Lazy_HP_less)
1158 CPPUNIT_TEST(Lazy_HP_cmpmix)
1160 CPPUNIT_TEST(Lazy_DHP_cmp)
1161 CPPUNIT_TEST(Lazy_DHP_less)
1162 CPPUNIT_TEST(Lazy_DHP_cmpmix)
1164 CPPUNIT_TEST(Lazy_RCU_GPI_cmp)
1165 CPPUNIT_TEST(Lazy_RCU_GPI_less)
1166 CPPUNIT_TEST(Lazy_RCU_GPI_cmpmix)
1168 CPPUNIT_TEST(Lazy_RCU_GPB_cmp)
1169 CPPUNIT_TEST(Lazy_RCU_GPB_less)
1170 CPPUNIT_TEST(Lazy_RCU_GPB_cmpmix)
1172 CPPUNIT_TEST(Lazy_RCU_GPT_cmp)
1173 CPPUNIT_TEST(Lazy_RCU_GPT_less)
1174 CPPUNIT_TEST(Lazy_RCU_GPT_cmpmix)
1176 CPPUNIT_TEST(Lazy_RCU_SHB_cmp)
1177 CPPUNIT_TEST(Lazy_RCU_SHB_less)
1178 CPPUNIT_TEST(Lazy_RCU_SHB_cmpmix)
1180 CPPUNIT_TEST(Lazy_RCU_SHT_cmp)
1181 CPPUNIT_TEST(Lazy_RCU_SHT_less)
1182 CPPUNIT_TEST(Lazy_RCU_SHT_cmpmix)
1184 CPPUNIT_TEST(Lazy_nogc_cmp)
1185 CPPUNIT_TEST(Lazy_nogc_less)
1186 CPPUNIT_TEST(Lazy_nogc_equal)
1187 CPPUNIT_TEST(Lazy_nogc_cmpmix)
1189 CPPUNIT_TEST(Split_HP_cmp)
1190 CPPUNIT_TEST(Split_HP_less)
1191 CPPUNIT_TEST(Split_HP_cmpmix)
1192 CPPUNIT_TEST( Split_HP_cmpmix_stat )
1194 CPPUNIT_TEST(Split_DHP_cmp)
1195 CPPUNIT_TEST(Split_DHP_less)
1196 CPPUNIT_TEST(Split_DHP_cmpmix)
1197 CPPUNIT_TEST( Split_DHP_cmpmix_stat )
1199 CPPUNIT_TEST(Split_RCU_GPI_cmp)
1200 CPPUNIT_TEST(Split_RCU_GPI_less)
1201 CPPUNIT_TEST(Split_RCU_GPI_cmpmix)
1202 CPPUNIT_TEST( Split_RCU_GPI_cmpmix_stat )
1204 CPPUNIT_TEST(Split_RCU_GPB_cmp)
1205 CPPUNIT_TEST(Split_RCU_GPB_less)
1206 CPPUNIT_TEST(Split_RCU_GPB_cmpmix)
1207 CPPUNIT_TEST( Split_RCU_GPB_cmpmix_stat )
1209 CPPUNIT_TEST(Split_RCU_GPT_cmp)
1210 CPPUNIT_TEST(Split_RCU_GPT_less)
1211 CPPUNIT_TEST(Split_RCU_GPT_cmpmix)
1212 CPPUNIT_TEST( Split_RCU_GPT_cmpmix_stat )
1214 CPPUNIT_TEST(Split_RCU_SHB_cmp)
1215 CPPUNIT_TEST(Split_RCU_SHB_less)
1216 CPPUNIT_TEST(Split_RCU_SHB_cmpmix)
1217 CPPUNIT_TEST( Split_RCU_SHB_cmpmix_stat )
1219 CPPUNIT_TEST(Split_RCU_SHT_cmp)
1220 CPPUNIT_TEST(Split_RCU_SHT_less)
1221 CPPUNIT_TEST(Split_RCU_SHT_cmpmix)
1222 CPPUNIT_TEST( Split_RCU_SHT_cmpmix_stat )
1224 CPPUNIT_TEST(Split_nogc_cmp)
1225 CPPUNIT_TEST(Split_nogc_less)
1226 CPPUNIT_TEST(Split_nogc_cmpmix)
1227 CPPUNIT_TEST( Split_nogc_cmpmix_stat )
1229 CPPUNIT_TEST(Split_Lazy_HP_cmp)
1230 CPPUNIT_TEST(Split_Lazy_HP_less)
1231 CPPUNIT_TEST(Split_Lazy_HP_cmpmix)
1232 CPPUNIT_TEST( Split_Lazy_HP_cmpmix_stat )
1234 CPPUNIT_TEST(Split_Lazy_DHP_cmp)
1235 CPPUNIT_TEST(Split_Lazy_DHP_less)
1236 CPPUNIT_TEST(Split_Lazy_DHP_cmpmix)
1237 CPPUNIT_TEST( Split_Lazy_DHP_cmpmix_stat )
1239 CPPUNIT_TEST(Split_Lazy_RCU_GPI_cmp)
1240 CPPUNIT_TEST(Split_Lazy_RCU_GPI_less)
1241 CPPUNIT_TEST(Split_Lazy_RCU_GPI_cmpmix)
1242 CPPUNIT_TEST( Split_Lazy_RCU_GPI_cmpmix_stat )
1244 CPPUNIT_TEST(Split_Lazy_RCU_GPB_cmp)
1245 CPPUNIT_TEST(Split_Lazy_RCU_GPB_less)
1246 CPPUNIT_TEST(Split_Lazy_RCU_GPB_cmpmix)
1247 CPPUNIT_TEST( Split_Lazy_RCU_GPB_cmpmix_stat )
1249 CPPUNIT_TEST(Split_Lazy_RCU_GPT_cmp)
1250 CPPUNIT_TEST(Split_Lazy_RCU_GPT_less)
1251 CPPUNIT_TEST(Split_Lazy_RCU_GPT_cmpmix)
1252 CPPUNIT_TEST( Split_Lazy_RCU_GPT_cmpmix_stat )
1254 CPPUNIT_TEST(Split_Lazy_RCU_SHB_cmp)
1255 CPPUNIT_TEST(Split_Lazy_RCU_SHB_less)
1256 CPPUNIT_TEST(Split_Lazy_RCU_SHB_cmpmix)
1257 CPPUNIT_TEST( Split_Lazy_RCU_SHB_cmpmix_stat )
1259 CPPUNIT_TEST(Split_Lazy_RCU_SHT_cmp)
1260 CPPUNIT_TEST(Split_Lazy_RCU_SHT_less)
1261 CPPUNIT_TEST(Split_Lazy_RCU_SHT_cmpmix)
1262 CPPUNIT_TEST( Split_Lazy_RCU_SHT_cmpmix_stat )
1264 CPPUNIT_TEST(Split_Lazy_nogc_cmp)
1265 CPPUNIT_TEST(Split_Lazy_nogc_less)
1266 CPPUNIT_TEST(Split_Lazy_nogc_cmpmix)
1267 CPPUNIT_TEST( Split_Lazy_nogc_cmpmix_stat )
1268 CPPUNIT_TEST_SUITE_END()
1273 #endif // #ifndef CDSTEST_HDR_MAP_H