test/unit/tree/test_bronson_avltree_map_ptr.h

   1 /*
   2     This file is a part of libcds - Concurrent Data Structures library
   3
   4     (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2017
   5
   6     Source code repo: http://github.com/khizmax/libcds/
   7     Download: http://sourceforge.net/projects/libcds/files/
   8
   9     Redistribution and use in source and binary forms, with or without
  10     modification, are permitted provided that the following conditions are met:
  11
  12     * Redistributions of source code must retain the above copyright notice, this
  13       list of conditions and the following disclaimer.
  14
  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.
  18
  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.
  29 */
  30
  31 #ifndef CDSUNIT_TREE_TEST_BRONSON_AVLTREE_MAP_PTR_H
  32 #define CDSUNIT_TREE_TEST_BRONSON_AVLTREE_MAP_PTR_H
  33
  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>
  38
  39 namespace {
  40
  41     namespace cc = cds::container;
  42
  43     class bronson_avltree_map_ptr: public cds_test::tree_map_fixture
  44     {
  45     public:
  46         static size_t const kSize = 1000;
  47
  48         struct value_type: public cds_test::tree_map_fixture::value_type
  49         {
  50             typedef cds_test::tree_map_fixture::value_type base_class;
  51
  52             size_t nDisposeCount = 0;
  53
  54             // Inheriting constructors
  55             using base_class::value_type;
  56         };
  57
  58         struct mock_disposer
  59         {
  60             void operator()( value_type * val ) const
  61             {
  62                 ++val->nDisposeCount;
  63             }
  64         };
  65
  66     protected:
  67         template <class Map>
  68         void test( Map& m )
  69         {
  70             // Precondition: map is empty
  71             // Postcondition: map is empty
  72
  73             ASSERT_TRUE( m.empty());
  74             ASSERT_CONTAINER_SIZE( m, 0 );
  75
  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;
  79
  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());
  84
  85             std::vector< value_type > arrVals;
  86             for ( size_t i = 0; i < kkSize; ++i ) {
  87                 value_type val;
  88                 val.nVal = static_cast<int>( i );
  89                 val.strVal = std::to_string( i );
  90                 arrVals.push_back( val );
  91             }
  92
  93             // insert/find
  94             for ( auto const& i : arrKeys ) {
  95                 value_type& val( arrVals.at( i.nKey ));
  96
  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 );
 102                 } ));
 103                 ASSERT_FALSE( m.find( i.nKey, []( key_type const&, mapped_type& ) {
 104                     EXPECT_TRUE( false );
 105                 } ));
 106                 ASSERT_FALSE( m.find_with( other_item( i.nKey ), other_less(), []( key_type const&, mapped_type& ) {
 107                     EXPECT_TRUE( false );
 108                 } ));
 109
 110                 std::pair< bool, bool > updResult;
 111
 112                 switch ( i.nKey % 6 ) {
 113                 case 0:
 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 ) {
 117                         val.nVal = key.nKey;
 118                         val.strVal = std::to_string( key.nKey );
 119                     } ));
 120                     break;
 121                 case 1:
 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 ) {
 125                         val.nVal = key.nKey;
 126                         val.strVal = std::to_string( key.nKey );
 127                     } ));
 128                     break;
 129                 case 2:
 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 ) {
 133                         val.nVal = key.nKey;
 134                         val.strVal = std::to_string( key.nKey );
 135                     } ));
 136                     break;
 137                 case 3:
 138                     updResult = m.update( i.nKey, &val, false );
 139                     ASSERT_FALSE( updResult.first );
 140                     ASSERT_FALSE( updResult.second );
 141
 142                     updResult = m.update( i.nKey, &val );
 143                     ASSERT_TRUE( updResult.first );
 144                     ASSERT_TRUE( updResult.second );
 145
 146                     updResult = m.update( i.nKey, &val );
 147                     ASSERT_TRUE( updResult.first );
 148                     ASSERT_FALSE( updResult.second );
 149                     break;
 150                 case 4:
 151                     updResult = m.update( i, &val, false );
 152                     ASSERT_FALSE( updResult.first );
 153                     ASSERT_FALSE( updResult.second );
 154
 155                     updResult = m.update( i, &val );
 156                     ASSERT_TRUE( updResult.first );
 157                     ASSERT_TRUE( updResult.second );
 158
 159                     updResult = m.update( i, &val );
 160                     ASSERT_TRUE( updResult.first );
 161                     ASSERT_FALSE( updResult.second );
 162                     break;
 163                 case 5:
 164                     updResult = m.update( val.strVal, &val, false );
 165                     ASSERT_FALSE( updResult.first );
 166                     ASSERT_FALSE( updResult.second );
 167
 168                     updResult = m.update( val.strVal, &val );
 169                     ASSERT_TRUE( updResult.first );
 170                     ASSERT_TRUE( updResult.second );
 171
 172                     updResult = m.update( val.strVal, &val );
 173                     ASSERT_TRUE( updResult.first );
 174                     ASSERT_FALSE( updResult.second );
 175                     break;
 176                 }
 177
 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 );
 184                 } ));
 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 );
 188                 } ));
 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 );
 192                 } ));
 193             }
 194             ASSERT_FALSE( m.empty());
 195             ASSERT_CONTAINER_SIZE( m, kkSize );
 196
 197             ASSERT_TRUE( m.check_consistency());
 198
 199             shuffle( arrKeys.begin(), arrKeys.end());
 200
 201             // erase/find
 202             for ( auto const& i : arrKeys ) {
 203                 value_type const& val( arrVals.at( i.nKey ));
 204
 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 );
 212                 } ));
 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 );
 216                 } ));
 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 );
 220                 } ));
 221
 222
 223                 switch ( i.nKey % 8 ) {
 224                 case 0:
 225                     ASSERT_TRUE( m.erase( i ));
 226                     ASSERT_FALSE( m.erase( i ));
 227                     break;
 228                 case 1:
 229                     ASSERT_TRUE( m.erase( i.nKey ));
 230                     ASSERT_FALSE( m.erase( i.nKey ));
 231                     break;
 232                 case 2:
 233                     ASSERT_TRUE( m.erase( val.strVal ));
 234                     ASSERT_FALSE( m.erase( val.strVal ));
 235                     break;
 236                 case 3:
 237                     ASSERT_TRUE( m.erase_with( other_item( i.nKey ), other_less()));
 238                     ASSERT_FALSE( m.erase_with( other_item( i.nKey ), other_less()));
 239                     break;
 240                 case 4:
 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 );
 244                     }));
 245                     ASSERT_FALSE( m.erase( i, []( key_type const& /*key*/, mapped_type& /*val*/ ) {
 246                         EXPECT_TRUE( false );
 247                     }));
 248                     break;
 249                 case 5:
 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 );
 253                     }));
 254                     ASSERT_FALSE( m.erase( i.nKey, []( key_type const&, mapped_type& ) {
 255                         EXPECT_TRUE( false );
 256                     }));
 257                     break;
 258                 case 6:
 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 );
 262                     }));
 263                     ASSERT_FALSE( m.erase( val.strVal, []( key_type const&, mapped_type& ) {
 264                         EXPECT_TRUE( false );
 265                     }));
 266                     break;
 267                 case 7:
 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 );
 271                     }));
 272                     ASSERT_FALSE( m.erase_with( other_item( i.nKey ), other_less(), []( key_type const& /*key*/, mapped_type& /*v*/ ) {
 273                         EXPECT_TRUE( false );
 274                     }));
 275                     break;
 276                 }
 277
 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 );
 284                 } ));
 285                 ASSERT_FALSE( m.find( i.nKey, []( key_type const& /*key*/, mapped_type& /*val*/ ) {
 286                     EXPECT_TRUE( false );
 287                 } ));
 288                 ASSERT_FALSE( m.find_with( other_item( i.nKey ), other_less(), []( key_type const& /*key*/, mapped_type& /*val*/ ) {
 289                     EXPECT_TRUE( false );
 290                 } ));
 291             }
 292             ASSERT_TRUE( m.empty());
 293             ASSERT_CONTAINER_SIZE( m, 0 );
 294
 295             Map::gc::force_dispose();
 296             for ( auto const& item: arrVals ) {
 297                 EXPECT_EQ( item.nDisposeCount, 1u );
 298             }
 299
 300             // clear
 301             for ( auto const& i : arrKeys ) {
 302                 value_type& val( arrVals.at( i.nKey ));
 303                 ASSERT_TRUE( m.insert( i, &val ));
 304             }
 305
 306             ASSERT_FALSE( m.empty());
 307             ASSERT_CONTAINER_SIZE( m, kkSize );
 308
 309             m.clear();
 310
 311             ASSERT_TRUE( m.empty());
 312             ASSERT_CONTAINER_SIZE( m, 0 );
 313
 314             Map::gc::force_dispose();
 315             for ( auto const& item : arrVals ) {
 316                 EXPECT_EQ( item.nDisposeCount, 2u );
 317             }
 318
 319             ASSERT_TRUE( m.check_consistency());
 320
 321
 322             // RCU-specific test related to exempt_ptr
 323             typedef typename Map::exempt_ptr exempt_ptr;
 324             exempt_ptr xp;
 325
 326             // extract
 327             for ( auto const& i : arrKeys ) {
 328                 value_type& val( arrVals.at( i.nKey ));
 329                 ASSERT_TRUE( m.insert( i, &val ));
 330             }
 331             ASSERT_FALSE( m.empty());
 332             ASSERT_CONTAINER_SIZE( m, kkSize );
 333
 334             for ( auto const& i : arrKeys ) {
 335                 value_type const& val = arrVals.at( i.nKey );
 336
 337                 EXPECT_TRUE( m.contains( i.nKey ));
 338
 339                 switch ( i.nKey % 4 ) {
 340                 case 0:
 341                     xp = m.extract( i.nKey );
 342                     break;
 343                 case 1:
 344                     xp = m.extract( i );
 345                     break;
 346                 case 2:
 347                     xp = m.extract( val.strVal );
 348                     break;
 349                 case 3:
 350                     xp = m.extract_with( other_item( i.nKey ), other_less());
 351                     break;
 352                 }
 353                 ASSERT_FALSE( !xp );
 354                 EXPECT_EQ( xp->nVal, i.nKey );
 355
 356                 EXPECT_FALSE( m.contains( i.nKey ));
 357             }
 358             ASSERT_TRUE( m.empty());
 359             ASSERT_CONTAINER_SIZE( m, 0 );
 360             xp.release();
 361
 362             Map::gc::force_dispose();
 363             for ( auto const& item : arrVals ) {
 364                 EXPECT_EQ( item.nDisposeCount, 3u );
 365             }
 366
 367             // extract_min
 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 ));
 372             }
 373             ASSERT_FALSE( m.empty());
 374             ASSERT_CONTAINER_SIZE( m, kkSize );
 375             ASSERT_TRUE( m.check_consistency());
 376
 377             int nPrevKey = -1;
 378             size_t nCount = 0;
 379             while ( !m.empty()) {
 380                 switch ( nCount % 3 ) {
 381                 case 0:
 382                     xp = m.extract_min();
 383                     break;
 384                 case 1:
 385                     xp = m.extract_min( [nPrevKey]( key_type const& k ) {
 386                         EXPECT_EQ( k.nKey, nPrevKey + 1 );
 387                     } );
 388                     break;
 389                 case 2:
 390                 {
 391                     key_type key;
 392                     xp = m.extract_min_key( key );
 393                     EXPECT_EQ( key.nKey, nPrevKey + 1 );
 394                 }
 395                 break;
 396                 }
 397                 ASSERT_FALSE( !xp );
 398                 EXPECT_EQ( xp->nVal, nPrevKey + 1 );
 399
 400                 nPrevKey = xp->nVal;
 401                 ++nCount;
 402             }
 403             ASSERT_TRUE( m.empty());
 404             ASSERT_CONTAINER_SIZE( m, 0 );
 405             EXPECT_EQ( nCount, kkSize );
 406             xp.release();
 407
 408             Map::gc::force_dispose();
 409             for ( auto const& item : arrVals ) {
 410                 EXPECT_EQ( item.nDisposeCount, 4u );
 411             }
 412
 413             // extract_max
 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 ));
 418             }
 419             ASSERT_FALSE( m.empty());
 420             ASSERT_CONTAINER_SIZE( m, kkSize );
 421             ASSERT_TRUE( m.check_consistency());
 422
 423             nPrevKey = static_cast<int>(kkSize);
 424             nCount = 0;
 425             while ( !m.empty()) {
 426                 switch ( nCount % 3 ) {
 427                 case 0:
 428                     xp = m.extract_max();
 429                     break;
 430                 case 1:
 431                     xp = m.extract_max( [nPrevKey]( key_type const& k ) {
 432                         EXPECT_EQ( k.nKey, nPrevKey - 1 );
 433                     } );
 434                     break;
 435                 case 2:
 436                 {
 437                     key_type key;
 438                     xp = m.extract_max_key( key );
 439                     EXPECT_EQ( key.nKey, nPrevKey - 1 );
 440                 }
 441                 break;
 442                 }
 443                 ASSERT_FALSE( !xp );
 444                 EXPECT_EQ( xp->nVal, nPrevKey - 1 );
 445
 446                 nPrevKey = xp->nVal;
 447                 ++nCount;
 448             }
 449             ASSERT_TRUE( m.empty());
 450             ASSERT_CONTAINER_SIZE( m, 0 );
 451             EXPECT_EQ( nCount, kkSize );
 452             xp.release();
 453
 454             Map::gc::force_dispose();
 455             for ( auto const& item : arrVals ) {
 456                 EXPECT_EQ( item.nDisposeCount, 5u );
 457             }
 458
 459             // extract min/max on empty map
 460             xp = m.extract_min();
 461             EXPECT_TRUE( !xp );
 462             xp = m.extract_min( []( key_type const& ) { EXPECT_FALSE( true ); } );
 463             EXPECT_TRUE( !xp );
 464             xp = m.extract_max();
 465             EXPECT_TRUE( !xp );
 466             xp = m.extract_max( []( key_type const& ) { EXPECT_FALSE( true ); } );
 467             EXPECT_TRUE( !xp );
 468             {
 469                 key_type key;
 470                 key.nKey = -100;
 471                 xp = m.extract_min_key( key );
 472                 EXPECT_TRUE( !xp );
 473                 EXPECT_EQ( key.nKey, -100 );
 474                 xp = m.extract_max_key( key );
 475                 EXPECT_TRUE( !xp );
 476                 EXPECT_EQ( key.nKey, -100 );
 477             }
 478
 479             // checking empty map
 480             ASSERT_TRUE( m.check_consistency());
 481         }
 482     };
 483
 484     template <class RCU>
 485     class BronsonAVLTreeMapPtr: public bronson_avltree_map_ptr
 486     {
 487         typedef bronson_avltree_map_ptr base_class;
 488     public:
 489         typedef cds::urcu::gc<RCU> rcu_type;
 490
 491     protected:
 492         void SetUp()
 493         {
 494             RCU::Construct();
 495             cds::threading::Manager::attachThread();
 496         }
 497
 498         void TearDown()
 499         {
 500             cds::threading::Manager::detachThread();
 501             RCU::Destruct();
 502         }
 503     };
 504
 505     struct bronson_traits: public cds::container::bronson_avltree::traits
 506     {
 507         typedef bronson_avltree_map_ptr::mock_disposer disposer;
 508     };
 509
 510     TYPED_TEST_CASE_P( BronsonAVLTreeMapPtr );
 511
 512     TYPED_TEST_P( BronsonAVLTreeMapPtr, compare )
 513     {
 514         typedef typename TestFixture::rcu_type rcu_type;
 515         typedef typename TestFixture::key_type key_type;
 516         typedef typename TestFixture::value_type value_type;
 517
 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 >
 522             >::type
 523         > map_type;
 524
 525         map_type m;
 526         this->test( m );
 527     }
 528
 529     TYPED_TEST_P( BronsonAVLTreeMapPtr, less )
 530     {
 531         typedef typename TestFixture::rcu_type rcu_type;
 532         typedef typename TestFixture::key_type key_type;
 533         typedef typename TestFixture::value_type value_type;
 534
 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 >
 539             >::type
 540         > map_type;
 541
 542         map_type m;
 543         this->test( m );
 544     }
 545
 546     TYPED_TEST_P( BronsonAVLTreeMapPtr, cmpmix )
 547     {
 548         typedef typename TestFixture::rcu_type rcu_type;
 549         typedef typename TestFixture::key_type key_type;
 550         typedef typename TestFixture::value_type value_type;
 551
 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 >
 557             >::type
 558         > map_type;
 559
 560         map_type m;
 561         this->test( m );
 562     }
 563
 564     TYPED_TEST_P( BronsonAVLTreeMapPtr, stat )
 565     {
 566         typedef typename TestFixture::rcu_type rcu_type;
 567         typedef typename TestFixture::key_type key_type;
 568         typedef typename TestFixture::value_type value_type;
 569
 570         struct map_traits: public bronson_traits
 571         {
 572             typedef typename TestFixture::less  less;
 573             typedef cc::bronson_avltree::stat<> stat;
 574         };
 575
 576         typedef cc::BronsonAVLTreeMap< rcu_type, key_type, value_type*, map_traits > map_type;
 577
 578         map_type m;
 579         this->test( m );
 580     }
 581
 582     TYPED_TEST_P( BronsonAVLTreeMapPtr, item_counting )
 583     {
 584         typedef typename TestFixture::rcu_type rcu_type;
 585         typedef typename TestFixture::key_type key_type;
 586         typedef typename TestFixture::value_type value_type;
 587
 588         struct map_traits: public bronson_traits
 589         {
 590             typedef typename TestFixture::cmp    compare;
 591             typedef cds::atomicity::item_counter item_counter;
 592         };
 593
 594         typedef cc::BronsonAVLTreeMap< rcu_type, key_type, value_type*, map_traits > map_type;
 595
 596         map_type m;
 597         this->test( m );
 598     }
 599
 600     struct bronson_relaxed_insert_traits: public bronson_traits
 601     {
 602         static bool const relaxed_insert = true;
 603     };
 604
 605     TYPED_TEST_P( BronsonAVLTreeMapPtr, relaxed_insert )
 606     {
 607         typedef typename TestFixture::rcu_type rcu_type;
 608         typedef typename TestFixture::key_type key_type;
 609         typedef typename TestFixture::value_type value_type;
 610
 611         struct map_traits: public bronson_relaxed_insert_traits
 612         {
 613             typedef typename TestFixture::cmp    compare;
 614             typedef cds::atomicity::item_counter item_counter;
 615         };
 616
 617         typedef cc::BronsonAVLTreeMap< rcu_type, key_type, value_type*, map_traits > map_type;
 618
 619         map_type m;
 620         this->test( m );
 621     }
 622
 623     TYPED_TEST_P( BronsonAVLTreeMapPtr, seq_cst )
 624     {
 625         typedef typename TestFixture::rcu_type rcu_type;
 626         typedef typename TestFixture::key_type key_type;
 627         typedef typename TestFixture::value_type value_type;
 628
 629         struct map_traits: public bronson_traits
 630         {
 631             typedef typename TestFixture::cmp    compare;
 632             typedef cds::atomicity::item_counter item_counter;
 633             typedef cds::opt::v::sequential_consistent memory_model;
 634         };
 635
 636         typedef cc::BronsonAVLTreeMap< rcu_type, key_type, value_type*, map_traits > map_type;
 637
 638         map_type m;
 639         this->test( m );
 640     }
 641
 642     TYPED_TEST_P( BronsonAVLTreeMapPtr, sync_monitor )
 643     {
 644         typedef typename TestFixture::rcu_type rcu_type;
 645         typedef typename TestFixture::key_type key_type;
 646         typedef typename TestFixture::value_type value_type;
 647
 648         struct map_traits: public bronson_traits
 649         {
 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;
 653         };
 654
 655         typedef cc::BronsonAVLTreeMap< rcu_type, key_type, value_type*, map_traits > map_type;
 656
 657         map_type m;
 658         this->test( m );
 659     }
 660
 661     TYPED_TEST_P( BronsonAVLTreeMapPtr, lazy_sync_monitor )
 662     {
 663         typedef typename TestFixture::rcu_type rcu_type;
 664         typedef typename TestFixture::key_type key_type;
 665         typedef typename TestFixture::value_type value_type;
 666
 667         struct map_traits: public bronson_traits
 668         {
 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;
 672         };
 673
 674         typedef cc::BronsonAVLTreeMap< rcu_type, key_type, value_type*, map_traits > map_type;
 675
 676         map_type m;
 677         this->test( m );
 678     }
 679
 680     TYPED_TEST_P( BronsonAVLTreeMapPtr, rcu_check_deadlock )
 681     {
 682         typedef typename TestFixture::rcu_type rcu_type;
 683         typedef typename TestFixture::key_type key_type;
 684         typedef typename TestFixture::value_type value_type;
 685
 686         struct map_traits: public bronson_traits
 687         {
 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;
 692         };
 693
 694         typedef cc::BronsonAVLTreeMap< rcu_type, key_type, value_type*, map_traits > map_type;
 695
 696         map_type m;
 697         this->test( m );
 698     }
 699
 700     TYPED_TEST_P( BronsonAVLTreeMapPtr, rcu_no_check_deadlock )
 701     {
 702         typedef typename TestFixture::rcu_type rcu_type;
 703         typedef typename TestFixture::key_type key_type;
 704         typedef typename TestFixture::value_type value_type;
 705
 706         struct map_traits: public bronson_traits
 707         {
 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;
 712         };
 713
 714         typedef cc::BronsonAVLTreeMap< rcu_type, key_type, value_type*, map_traits > map_type;
 715
 716         map_type m;
 717         this->test( m );
 718     }
 719
 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
 722     );
 723
 724
 725 } // namespace
 726
 727 #endif // #ifndef CDSUNIT_TREE_TEST_BRONSON_AVLTREE_MAP_PTR_H