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 CDSUNIT_TREE_TEST_BRONSON_AVLTREE_MAP_PTR_H
32 #define CDSUNIT_TREE_TEST_BRONSON_AVLTREE_MAP_PTR_H
34 #include "test_tree_map_data.h"
35 #include <cds/container/bronson_avltree_map_rcu.h>
36 #include <cds/sync/pool_monitor.h>
37 #include <cds/memory/vyukov_queue_pool.h>
41 namespace cc = cds::container;
43 class bronson_avltree_map_ptr: public cds_test::tree_map_fixture
46 static size_t const kSize = 1000;
48 struct value_type: public cds_test::tree_map_fixture::value_type
50 typedef cds_test::tree_map_fixture::value_type base_class;
52 size_t nDisposeCount = 0;
54 // Inheriting constructors
55 using base_class::value_type;
60 void operator()( value_type * val ) const
70 // Precondition: map is empty
71 // Postcondition: map is empty
73 ASSERT_TRUE( m.empty());
74 ASSERT_CONTAINER_SIZE( m, 0 );
76 typedef typename Map::key_type key_type;
77 typedef typename std::remove_pointer< typename Map::mapped_type >::type mapped_type;
78 size_t const kkSize = kSize;
80 std::vector<key_type> arrKeys;
81 for ( int i = 0; i < static_cast<int>(kkSize); ++i )
82 arrKeys.push_back( key_type( i ));
83 shuffle( arrKeys.begin(), arrKeys.end());
85 std::vector< value_type > arrVals;
86 for ( size_t i = 0; i < kkSize; ++i ) {
88 val.nVal = static_cast<int>( i );
89 val.strVal = std::to_string( i );
90 arrVals.push_back( val );
94 for ( auto const& i : arrKeys ) {
95 value_type& val( arrVals.at( i.nKey ));
97 ASSERT_FALSE( m.contains( i.nKey ));
98 ASSERT_FALSE( m.contains( i ));
99 ASSERT_FALSE( m.contains( other_item( i.nKey ), other_less()));
100 ASSERT_FALSE( m.find( i, []( key_type const&, mapped_type& ) {
101 ASSERT_TRUE( false );
103 ASSERT_FALSE( m.find( i.nKey, []( key_type const&, mapped_type& ) {
104 EXPECT_TRUE( false );
106 ASSERT_FALSE( m.find_with( other_item( i.nKey ), other_less(), []( key_type const&, mapped_type& ) {
107 EXPECT_TRUE( false );
110 std::pair< bool, bool > updResult;
112 switch ( i.nKey % 6 ) {
114 ASSERT_TRUE( m.insert( i, &val ));
115 ASSERT_FALSE( m.insert( i, &val ));
116 ASSERT_TRUE( m.find( i.nKey, []( key_type const& key, mapped_type& val ) {
118 val.strVal = std::to_string( key.nKey );
122 ASSERT_TRUE( m.insert( i.nKey, &val ));
123 ASSERT_FALSE( m.insert( i.nKey, &val ));
124 ASSERT_TRUE( m.find( i.nKey, []( key_type const& key, mapped_type& val ) {
126 val.strVal = std::to_string( key.nKey );
130 ASSERT_TRUE( m.insert( std::to_string( i.nKey ), &val ));
131 ASSERT_FALSE( m.insert( std::to_string( i.nKey ), &val ));
132 ASSERT_TRUE( m.find( i.nKey, []( key_type const& key, mapped_type& val ) {
134 val.strVal = std::to_string( key.nKey );
138 updResult = m.update( i.nKey, &val, false );
139 ASSERT_FALSE( updResult.first );
140 ASSERT_FALSE( updResult.second );
142 updResult = m.update( i.nKey, &val );
143 ASSERT_TRUE( updResult.first );
144 ASSERT_TRUE( updResult.second );
146 updResult = m.update( i.nKey, &val );
147 ASSERT_TRUE( updResult.first );
148 ASSERT_FALSE( updResult.second );
151 updResult = m.update( i, &val, false );
152 ASSERT_FALSE( updResult.first );
153 ASSERT_FALSE( updResult.second );
155 updResult = m.update( i, &val );
156 ASSERT_TRUE( updResult.first );
157 ASSERT_TRUE( updResult.second );
159 updResult = m.update( i, &val );
160 ASSERT_TRUE( updResult.first );
161 ASSERT_FALSE( updResult.second );
164 updResult = m.update( val.strVal, &val, false );
165 ASSERT_FALSE( updResult.first );
166 ASSERT_FALSE( updResult.second );
168 updResult = m.update( val.strVal, &val );
169 ASSERT_TRUE( updResult.first );
170 ASSERT_TRUE( updResult.second );
172 updResult = m.update( val.strVal, &val );
173 ASSERT_TRUE( updResult.first );
174 ASSERT_FALSE( updResult.second );
178 ASSERT_TRUE( m.contains( i.nKey ));
179 ASSERT_TRUE( m.contains( i ));
180 ASSERT_TRUE( m.contains( other_item( i.nKey ), other_less()));
181 ASSERT_TRUE( m.find( i, []( key_type const& key, mapped_type& val ) {
182 EXPECT_EQ( key.nKey, val.nVal );
183 EXPECT_EQ( std::to_string( key.nKey ), val.strVal );
185 ASSERT_TRUE( m.find( i.nKey, []( key_type const& key, mapped_type& val ) {
186 EXPECT_EQ( key.nKey, val.nVal );
187 EXPECT_EQ( std::to_string( key.nKey ), val.strVal );
189 ASSERT_TRUE( m.find_with( other_item( i.nKey ), other_less(), []( key_type const& key, mapped_type& val ) {
190 EXPECT_EQ( key.nKey, val.nVal );
191 EXPECT_EQ( std::to_string( key.nKey ), val.strVal );
194 ASSERT_FALSE( m.empty());
195 ASSERT_CONTAINER_SIZE( m, kkSize );
197 ASSERT_TRUE( m.check_consistency());
199 shuffle( arrKeys.begin(), arrKeys.end());
202 for ( auto const& i : arrKeys ) {
203 value_type const& val( arrVals.at( i.nKey ));
205 ASSERT_TRUE( m.contains( i.nKey ));
206 ASSERT_TRUE( m.contains( val.strVal ));
207 ASSERT_TRUE( m.contains( i ));
208 ASSERT_TRUE( m.contains( other_item( i.nKey ), other_less()));
209 ASSERT_TRUE( m.find( i, []( key_type const& key, mapped_type& val ) {
210 EXPECT_EQ( key.nKey, val.nVal );
211 EXPECT_EQ( std::to_string( key.nKey ), val.strVal );
213 ASSERT_TRUE( m.find( i.nKey, []( key_type const& key, mapped_type& val ) {
214 EXPECT_EQ( key.nKey, val.nVal );
215 EXPECT_EQ( std::to_string( key.nKey ), val.strVal );
217 ASSERT_TRUE( m.find_with( other_item( i.nKey ), other_less(), []( key_type const& key, mapped_type& val ) {
218 EXPECT_EQ( key.nKey, val.nVal );
219 EXPECT_EQ( std::to_string( key.nKey ), val.strVal );
223 switch ( i.nKey % 8 ) {
225 ASSERT_TRUE( m.erase( i ));
226 ASSERT_FALSE( m.erase( i ));
229 ASSERT_TRUE( m.erase( i.nKey ));
230 ASSERT_FALSE( m.erase( i.nKey ));
233 ASSERT_TRUE( m.erase( val.strVal ));
234 ASSERT_FALSE( m.erase( val.strVal ));
237 ASSERT_TRUE( m.erase_with( other_item( i.nKey ), other_less()));
238 ASSERT_FALSE( m.erase_with( other_item( i.nKey ), other_less()));
241 ASSERT_TRUE( m.erase( i, []( key_type const& key, mapped_type& val ) {
242 EXPECT_EQ( key.nKey, val.nVal );
243 EXPECT_EQ( std::to_string( key.nKey ), val.strVal );
245 ASSERT_FALSE( m.erase( i, []( key_type const& /*key*/, mapped_type& /*val*/ ) {
246 EXPECT_TRUE( false );
250 ASSERT_TRUE( m.erase( i.nKey, []( key_type const& key, mapped_type& v ) {
251 EXPECT_EQ( key.nKey, v.nVal );
252 EXPECT_EQ( std::to_string( key.nKey ), v.strVal );
254 ASSERT_FALSE( m.erase( i.nKey, []( key_type const&, mapped_type& ) {
255 EXPECT_TRUE( false );
259 ASSERT_TRUE( m.erase( val.strVal, []( key_type const& key, mapped_type& v ) {
260 EXPECT_EQ( key.nKey, v.nVal );
261 EXPECT_EQ( std::to_string( key.nKey ), v.strVal );
263 ASSERT_FALSE( m.erase( val.strVal, []( key_type const&, mapped_type& ) {
264 EXPECT_TRUE( false );
268 ASSERT_TRUE( m.erase_with( other_item( i.nKey ), other_less(), []( key_type const& key, mapped_type& v ) {
269 EXPECT_EQ( key.nKey, v.nVal );
270 EXPECT_EQ( std::to_string( key.nKey ), v.strVal );
272 ASSERT_FALSE( m.erase_with( other_item( i.nKey ), other_less(), []( key_type const& /*key*/, mapped_type& /*v*/ ) {
273 EXPECT_TRUE( false );
278 ASSERT_FALSE( m.contains( i.nKey ));
279 ASSERT_FALSE( m.contains( i ));
280 ASSERT_FALSE( m.contains( val.strVal ));
281 ASSERT_FALSE( m.contains( other_item( i.nKey ), other_less()));
282 ASSERT_FALSE( m.find( i, []( key_type const& /*key*/, mapped_type& /*val*/ ) {
283 ASSERT_TRUE( false );
285 ASSERT_FALSE( m.find( i.nKey, []( key_type const& /*key*/, mapped_type& /*val*/ ) {
286 EXPECT_TRUE( false );
288 ASSERT_FALSE( m.find_with( other_item( i.nKey ), other_less(), []( key_type const& /*key*/, mapped_type& /*val*/ ) {
289 EXPECT_TRUE( false );
292 ASSERT_TRUE( m.empty());
293 ASSERT_CONTAINER_SIZE( m, 0 );
295 Map::gc::force_dispose();
296 for ( auto const& item: arrVals ) {
297 EXPECT_EQ( item.nDisposeCount, 1u );
301 for ( auto const& i : arrKeys ) {
302 value_type& val( arrVals.at( i.nKey ));
303 ASSERT_TRUE( m.insert( i, &val ));
306 ASSERT_FALSE( m.empty());
307 ASSERT_CONTAINER_SIZE( m, kkSize );
311 ASSERT_TRUE( m.empty());
312 ASSERT_CONTAINER_SIZE( m, 0 );
314 Map::gc::force_dispose();
315 for ( auto const& item : arrVals ) {
316 EXPECT_EQ( item.nDisposeCount, 2u );
319 ASSERT_TRUE( m.check_consistency());
322 // RCU-specific test related to exempt_ptr
323 typedef typename Map::exempt_ptr exempt_ptr;
327 for ( auto const& i : arrKeys ) {
328 value_type& val( arrVals.at( i.nKey ));
329 ASSERT_TRUE( m.insert( i, &val ));
331 ASSERT_FALSE( m.empty());
332 ASSERT_CONTAINER_SIZE( m, kkSize );
334 for ( auto const& i : arrKeys ) {
335 value_type const& val = arrVals.at( i.nKey );
337 EXPECT_TRUE( m.contains( i.nKey ));
339 switch ( i.nKey % 4 ) {
341 xp = m.extract( i.nKey );
347 xp = m.extract( val.strVal );
350 xp = m.extract_with( other_item( i.nKey ), other_less());
354 EXPECT_EQ( xp->nVal, i.nKey );
356 EXPECT_FALSE( m.contains( i.nKey ));
358 ASSERT_TRUE( m.empty());
359 ASSERT_CONTAINER_SIZE( m, 0 );
362 Map::gc::force_dispose();
363 for ( auto const& item : arrVals ) {
364 EXPECT_EQ( item.nDisposeCount, 3u );
368 shuffle( arrKeys.begin(), arrKeys.end());
369 for ( auto const& i : arrKeys ) {
370 value_type& val( arrVals.at( i.nKey ));
371 ASSERT_TRUE( m.insert( i, &val ));
373 ASSERT_FALSE( m.empty());
374 ASSERT_CONTAINER_SIZE( m, kkSize );
375 ASSERT_TRUE( m.check_consistency());
379 while ( !m.empty()) {
380 switch ( nCount % 3 ) {
382 xp = m.extract_min();
385 xp = m.extract_min( [nPrevKey]( key_type const& k ) {
386 EXPECT_EQ( k.nKey, nPrevKey + 1 );
392 xp = m.extract_min_key( key );
393 EXPECT_EQ( key.nKey, nPrevKey + 1 );
398 EXPECT_EQ( xp->nVal, nPrevKey + 1 );
403 ASSERT_TRUE( m.empty());
404 ASSERT_CONTAINER_SIZE( m, 0 );
405 EXPECT_EQ( nCount, kkSize );
408 Map::gc::force_dispose();
409 for ( auto const& item : arrVals ) {
410 EXPECT_EQ( item.nDisposeCount, 4u );
414 shuffle( arrKeys.begin(), arrKeys.end());
415 for ( auto const& i : arrKeys ) {
416 value_type& val( arrVals.at( i.nKey ));
417 ASSERT_TRUE( m.insert( i, &val ));
419 ASSERT_FALSE( m.empty());
420 ASSERT_CONTAINER_SIZE( m, kkSize );
421 ASSERT_TRUE( m.check_consistency());
423 nPrevKey = static_cast<int>(kkSize);
425 while ( !m.empty()) {
426 switch ( nCount % 3 ) {
428 xp = m.extract_max();
431 xp = m.extract_max( [nPrevKey]( key_type const& k ) {
432 EXPECT_EQ( k.nKey, nPrevKey - 1 );
438 xp = m.extract_max_key( key );
439 EXPECT_EQ( key.nKey, nPrevKey - 1 );
444 EXPECT_EQ( xp->nVal, nPrevKey - 1 );
449 ASSERT_TRUE( m.empty());
450 ASSERT_CONTAINER_SIZE( m, 0 );
451 EXPECT_EQ( nCount, kkSize );
454 Map::gc::force_dispose();
455 for ( auto const& item : arrVals ) {
456 EXPECT_EQ( item.nDisposeCount, 5u );
459 // extract min/max on empty map
460 xp = m.extract_min();
462 xp = m.extract_min( []( key_type const& ) { EXPECT_FALSE( true ); } );
464 xp = m.extract_max();
466 xp = m.extract_max( []( key_type const& ) { EXPECT_FALSE( true ); } );
471 xp = m.extract_min_key( key );
473 EXPECT_EQ( key.nKey, -100 );
474 xp = m.extract_max_key( key );
476 EXPECT_EQ( key.nKey, -100 );
479 // checking empty map
480 ASSERT_TRUE( m.check_consistency());
485 class BronsonAVLTreeMapPtr: public bronson_avltree_map_ptr
487 typedef bronson_avltree_map_ptr base_class;
489 typedef cds::urcu::gc<RCU> rcu_type;
495 cds::threading::Manager::attachThread();
500 cds::threading::Manager::detachThread();
505 struct bronson_traits: public cds::container::bronson_avltree::traits
507 typedef bronson_avltree_map_ptr::mock_disposer disposer;
510 TYPED_TEST_CASE_P( BronsonAVLTreeMapPtr );
512 TYPED_TEST_P( BronsonAVLTreeMapPtr, compare )
514 typedef typename TestFixture::rcu_type rcu_type;
515 typedef typename TestFixture::key_type key_type;
516 typedef typename TestFixture::value_type value_type;
518 typedef cc::BronsonAVLTreeMap< rcu_type, key_type, value_type*,
519 typename cc::bronson_avltree::make_traits<
520 cds::opt::compare< typename TestFixture::cmp >
521 ,cds::intrusive::opt::disposer< bronson_avltree_map_ptr::mock_disposer >
529 TYPED_TEST_P( BronsonAVLTreeMapPtr, less )
531 typedef typename TestFixture::rcu_type rcu_type;
532 typedef typename TestFixture::key_type key_type;
533 typedef typename TestFixture::value_type value_type;
535 typedef cc::BronsonAVLTreeMap< rcu_type, key_type, value_type*,
536 typename cc::bronson_avltree::make_traits<
537 cds::opt::less< typename TestFixture::less >
538 , cds::intrusive::opt::disposer< bronson_avltree_map_ptr::mock_disposer >
546 TYPED_TEST_P( BronsonAVLTreeMapPtr, cmpmix )
548 typedef typename TestFixture::rcu_type rcu_type;
549 typedef typename TestFixture::key_type key_type;
550 typedef typename TestFixture::value_type value_type;
552 typedef cc::BronsonAVLTreeMap< rcu_type, key_type, value_type*,
553 typename cc::bronson_avltree::make_traits<
554 cds::opt::less< typename TestFixture::less >
555 ,cds::opt::compare< typename TestFixture::cmp >
556 , cds::intrusive::opt::disposer< bronson_avltree_map_ptr::mock_disposer >
564 TYPED_TEST_P( BronsonAVLTreeMapPtr, stat )
566 typedef typename TestFixture::rcu_type rcu_type;
567 typedef typename TestFixture::key_type key_type;
568 typedef typename TestFixture::value_type value_type;
570 struct map_traits: public bronson_traits
572 typedef typename TestFixture::less less;
573 typedef cc::bronson_avltree::stat<> stat;
576 typedef cc::BronsonAVLTreeMap< rcu_type, key_type, value_type*, map_traits > map_type;
582 TYPED_TEST_P( BronsonAVLTreeMapPtr, item_counting )
584 typedef typename TestFixture::rcu_type rcu_type;
585 typedef typename TestFixture::key_type key_type;
586 typedef typename TestFixture::value_type value_type;
588 struct map_traits: public bronson_traits
590 typedef typename TestFixture::cmp compare;
591 typedef cds::atomicity::item_counter item_counter;
594 typedef cc::BronsonAVLTreeMap< rcu_type, key_type, value_type*, map_traits > map_type;
600 struct bronson_relaxed_insert_traits: public bronson_traits
602 static bool const relaxed_insert = true;
605 TYPED_TEST_P( BronsonAVLTreeMapPtr, relaxed_insert )
607 typedef typename TestFixture::rcu_type rcu_type;
608 typedef typename TestFixture::key_type key_type;
609 typedef typename TestFixture::value_type value_type;
611 struct map_traits: public bronson_relaxed_insert_traits
613 typedef typename TestFixture::cmp compare;
614 typedef cds::atomicity::item_counter item_counter;
617 typedef cc::BronsonAVLTreeMap< rcu_type, key_type, value_type*, map_traits > map_type;
623 TYPED_TEST_P( BronsonAVLTreeMapPtr, seq_cst )
625 typedef typename TestFixture::rcu_type rcu_type;
626 typedef typename TestFixture::key_type key_type;
627 typedef typename TestFixture::value_type value_type;
629 struct map_traits: public bronson_traits
631 typedef typename TestFixture::cmp compare;
632 typedef cds::atomicity::item_counter item_counter;
633 typedef cds::opt::v::sequential_consistent memory_model;
636 typedef cc::BronsonAVLTreeMap< rcu_type, key_type, value_type*, map_traits > map_type;
642 TYPED_TEST_P( BronsonAVLTreeMapPtr, sync_monitor )
644 typedef typename TestFixture::rcu_type rcu_type;
645 typedef typename TestFixture::key_type key_type;
646 typedef typename TestFixture::value_type value_type;
648 struct map_traits: public bronson_traits
650 typedef typename TestFixture::cmp compare;
651 typedef cds::atomicity::item_counter item_counter;
652 typedef cds::sync::pool_monitor< cds::memory::vyukov_queue_pool< std::mutex >> sync_monitor;
655 typedef cc::BronsonAVLTreeMap< rcu_type, key_type, value_type*, map_traits > map_type;
661 TYPED_TEST_P( BronsonAVLTreeMapPtr, lazy_sync_monitor )
663 typedef typename TestFixture::rcu_type rcu_type;
664 typedef typename TestFixture::key_type key_type;
665 typedef typename TestFixture::value_type value_type;
667 struct map_traits: public bronson_traits
669 typedef typename TestFixture::cmp compare;
670 typedef cds::atomicity::item_counter item_counter;
671 typedef cds::sync::pool_monitor< cds::memory::lazy_vyukov_queue_pool< std::mutex >> sync_monitor;
674 typedef cc::BronsonAVLTreeMap< rcu_type, key_type, value_type*, map_traits > map_type;
680 TYPED_TEST_P( BronsonAVLTreeMapPtr, rcu_check_deadlock )
682 typedef typename TestFixture::rcu_type rcu_type;
683 typedef typename TestFixture::key_type key_type;
684 typedef typename TestFixture::value_type value_type;
686 struct map_traits: public bronson_traits
688 typedef typename TestFixture::cmp compare;
689 typedef cds::atomicity::item_counter item_counter;
690 typedef cds::sync::pool_monitor< cds::memory::vyukov_queue_pool< std::mutex >> sync_monitor;
691 typedef cds::opt::v::rcu_assert_deadlock rcu_check_deadlock;
694 typedef cc::BronsonAVLTreeMap< rcu_type, key_type, value_type*, map_traits > map_type;
700 TYPED_TEST_P( BronsonAVLTreeMapPtr, rcu_no_check_deadlock )
702 typedef typename TestFixture::rcu_type rcu_type;
703 typedef typename TestFixture::key_type key_type;
704 typedef typename TestFixture::value_type value_type;
706 struct map_traits: public bronson_traits
708 typedef typename TestFixture::cmp compare;
709 typedef cds::atomicity::item_counter item_counter;
710 typedef cds::sync::pool_monitor< cds::memory::lazy_vyukov_queue_pool< std::mutex >> sync_monitor;
711 typedef cds::opt::v::rcu_no_check_deadlock rcu_check_deadlock;
714 typedef cc::BronsonAVLTreeMap< rcu_type, key_type, value_type*, map_traits > map_type;
720 REGISTER_TYPED_TEST_CASE_P( BronsonAVLTreeMapPtr,
721 compare, less, cmpmix, stat, item_counting, relaxed_insert, seq_cst, sync_monitor, lazy_sync_monitor, rcu_check_deadlock, rcu_no_check_deadlock
727 #endif // #ifndef CDSUNIT_TREE_TEST_BRONSON_AVLTREE_MAP_PTR_H