test/unit/tree/test_bronson_avltree_map.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_H
  32 #define CDSUNIT_TREE_TEST_BRONSON_AVLTREE_MAP_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: public cds_test::tree_map_fixture
  44     {
  45     public:
  46         static size_t const kSize = 1000;
  47
  48     protected:
  49         template <class Map>
  50         void test( Map& m )
  51         {
  52             // Precondition: map is empty
  53             // Postcondition: map is empty
  54
  55             ASSERT_TRUE( m.empty());
  56             ASSERT_CONTAINER_SIZE( m, 0 );
  57
  58             size_t const kkSize = kSize;
  59
  60             std::vector<key_type> arrKeys;
  61             for ( int i = 0; i < static_cast<int>(kkSize); ++i )
  62                 arrKeys.push_back( key_type( i ));
  63             shuffle( arrKeys.begin(), arrKeys.end());
  64
  65             std::vector< value_type > arrVals;
  66             for ( size_t i = 0; i < kkSize; ++i ) {
  67                 value_type val;
  68                 val.nVal = static_cast<int>( i );
  69                 val.strVal = std::to_string( i );
  70                 arrVals.push_back( val );
  71             }
  72
  73             // insert/find
  74             for ( auto const& i : arrKeys ) {
  75                 value_type const& val( arrVals.at( i.nKey ));
  76
  77                 ASSERT_FALSE( m.contains( i.nKey ));
  78                 ASSERT_FALSE( m.contains( i ));
  79                 ASSERT_FALSE( m.contains( other_item( i.nKey ), other_less()));
  80                 ASSERT_FALSE( m.find( i, []( key_type const&, value_type& ) {
  81                     ASSERT_TRUE( false );
  82                 } ));
  83                 ASSERT_FALSE( m.find( i.nKey, []( key_type const&, value_type& ) {
  84                     EXPECT_TRUE( false );
  85                 } ));
  86                 ASSERT_FALSE( m.find_with( other_item( i.nKey ), other_less(), []( key_type const&, value_type& ) {
  87                     EXPECT_TRUE( false );
  88                 } ));
  89
  90                 std::pair< bool, bool > updResult;
  91
  92                 switch ( i.nKey % 16 ) {
  93                 case 0:
  94                     ASSERT_TRUE( m.insert( i ));
  95                     ASSERT_FALSE( m.insert( i ));
  96                     ASSERT_TRUE( m.find( i.nKey, []( key_type const& key, value_type& val ) {
  97                         val.nVal = key.nKey;
  98                         val.strVal = std::to_string( key.nKey );
  99                     } ));
 100                     break;
 101                 case 1:
 102                     ASSERT_TRUE( m.insert( i.nKey ));
 103                     ASSERT_FALSE( m.insert( i.nKey ));
 104                     ASSERT_TRUE( m.find( i.nKey, []( key_type const& key, value_type& val ) {
 105                         val.nVal = key.nKey;
 106                         val.strVal = std::to_string( key.nKey );
 107                     } ));
 108                     break;
 109                 case 2:
 110                     ASSERT_TRUE( m.insert( std::to_string( i.nKey )));
 111                     ASSERT_FALSE( m.insert( std::to_string( i.nKey )));
 112                     ASSERT_TRUE( m.find( i.nKey, []( key_type const& key, value_type& val ) {
 113                         val.nVal = key.nKey;
 114                         val.strVal = std::to_string( key.nKey );
 115                     } ));
 116                     break;
 117                 case 3:
 118                     ASSERT_TRUE( m.insert( i, val ));
 119                     ASSERT_FALSE( m.insert( i, val ));
 120                     break;
 121                 case 4:
 122                     ASSERT_TRUE( m.insert( i.nKey, val.strVal ));
 123                     ASSERT_FALSE( m.insert( i.nKey, val.strVal ));
 124                     break;
 125                 case 5:
 126                     ASSERT_TRUE( m.insert( val.strVal, i.nKey ));
 127                     ASSERT_FALSE( m.insert( val.strVal, i.nKey ));
 128                     break;
 129                 case 6:
 130                     ASSERT_TRUE( m.insert_with( i, []( key_type const& key, value_type& val ) {
 131                         val.nVal = key.nKey;
 132                         val.strVal = std::to_string( key.nKey );
 133                     } ));
 134                     ASSERT_FALSE( m.insert_with( i, []( key_type const& /*key*/, value_type& /*val*/ ) {
 135                         EXPECT_TRUE( false );
 136                     } ));
 137                     break;
 138                 case 7:
 139                     ASSERT_TRUE( m.insert_with( i.nKey, []( key_type const& key, value_type& val ) {
 140                         val.nVal = key.nKey;
 141                         val.strVal = std::to_string( key.nKey );
 142                     } ));
 143                     ASSERT_FALSE( m.insert_with( i.nKey, []( key_type const& /*key*/, value_type& /*val*/ ) {
 144                         EXPECT_TRUE( false );
 145                     } ));
 146                     break;
 147                 case 8:
 148                     ASSERT_TRUE( m.insert_with( val.strVal, []( key_type const& key, value_type& val ) {
 149                         val.nVal = key.nKey;
 150                         val.strVal = std::to_string( key.nKey );
 151                     } ));
 152                     ASSERT_FALSE( m.insert_with( val.strVal, []( key_type const& /*key*/, value_type& /*val*/ ) {
 153                         EXPECT_TRUE( false );
 154                     } ));
 155                     break;
 156                 case 9:
 157                     updResult = m.update( i.nKey, []( bool, key_type const& /*key*/, value_type& /*val*/ ) {
 158                         EXPECT_TRUE( false );
 159                     }, false );
 160                     ASSERT_FALSE( updResult.first );
 161                     ASSERT_FALSE( updResult.second );
 162
 163                     updResult = m.update( i.nKey, []( bool bNew, key_type const& key, value_type& val ) {
 164                         EXPECT_TRUE( bNew );
 165                         val.nVal = key.nKey;
 166                     });
 167                     ASSERT_TRUE( updResult.first );
 168                     ASSERT_TRUE( updResult.second );
 169
 170                     updResult = m.update( i.nKey, []( bool bNew, key_type const& key, value_type& val ) {
 171                         EXPECT_FALSE( bNew );
 172                         EXPECT_EQ( key.nKey, val.nVal );
 173                         val.strVal = std::to_string( val.nVal );
 174                     } );
 175                     ASSERT_TRUE( updResult.first );
 176                     ASSERT_FALSE( updResult.second );
 177                     break;
 178                 case 10:
 179                     updResult = m.update( i, []( bool, key_type const& /*key*/, value_type& /*val*/ ) {
 180                         EXPECT_TRUE( false );
 181                     }, false );
 182                     ASSERT_FALSE( updResult.first );
 183                     ASSERT_FALSE( updResult.second );
 184
 185                     updResult = m.update( i, []( bool bNew, key_type const& key, value_type& val ) {
 186                         EXPECT_TRUE( bNew );
 187                         val.nVal = key.nKey;
 188                     });
 189                     ASSERT_TRUE( updResult.first );
 190                     ASSERT_TRUE( updResult.second );
 191
 192                     updResult = m.update( i, []( bool bNew, key_type const& key, value_type& val ) {
 193                         EXPECT_FALSE( bNew );
 194                         EXPECT_EQ( key.nKey, val.nVal );
 195                         val.strVal = std::to_string( val.nVal );
 196                     } );
 197                     ASSERT_TRUE( updResult.first );
 198                     ASSERT_FALSE( updResult.second );
 199                     break;
 200                 case 11:
 201                     updResult = m.update( val.strVal, []( bool, key_type const& /*key*/, value_type& /*val*/ ) {
 202                         EXPECT_TRUE( false );
 203                     }, false );
 204                     ASSERT_FALSE( updResult.first );
 205                     ASSERT_FALSE( updResult.second );
 206
 207                     updResult = m.update( val.strVal, []( bool bNew, key_type const& key, value_type& val ) {
 208                         EXPECT_TRUE( bNew );
 209                         val.nVal = key.nKey;
 210                     });
 211                     ASSERT_TRUE( updResult.first );
 212                     ASSERT_TRUE( updResult.second );
 213
 214                     updResult = m.update( val.strVal, []( bool bNew, key_type const& key, value_type& val ) {
 215                         EXPECT_FALSE( bNew );
 216                         EXPECT_EQ( key.nKey, val.nVal );
 217                         val.strVal = std::to_string( val.nVal );
 218                     } );
 219                     ASSERT_TRUE( updResult.first );
 220                     ASSERT_FALSE( updResult.second );
 221                     break;
 222                 case 12:
 223                     ASSERT_TRUE( m.emplace( i.nKey ));
 224                     ASSERT_FALSE( m.emplace( i.nKey ));
 225                     ASSERT_TRUE( m.find( i.nKey, []( key_type const& key, value_type& val ) {
 226                         val.nVal = key.nKey;
 227                         val.strVal = std::to_string( key.nKey );
 228                     } ));
 229                     break;
 230                 case 13:
 231                     ASSERT_TRUE( m.emplace( i, i.nKey ));
 232                     ASSERT_FALSE( m.emplace( i, i.nKey ));
 233                     break;
 234                 case 14:
 235                     {
 236                         std::string str = val.strVal;
 237                         ASSERT_TRUE( m.emplace( i, std::move( str )));
 238                         ASSERT_TRUE( str.empty());
 239                         str = val.strVal;
 240                         ASSERT_FALSE( m.emplace( i, std::move( str )));
 241                         ASSERT_TRUE( str.empty());
 242                     }
 243                     break;
 244                 case 15:
 245                     {
 246                         std::string str = val.strVal;
 247                         ASSERT_TRUE( m.emplace( i, i.nKey, std::move( str )));
 248                         ASSERT_TRUE( str.empty());
 249                         str = val.strVal;
 250                         ASSERT_FALSE( m.emplace( i, i.nKey, std::move( str )));
 251                         ASSERT_TRUE( str.empty());
 252                     }
 253                     break;
 254                 }
 255
 256                 ASSERT_TRUE( m.contains( i.nKey ));
 257                 ASSERT_TRUE( m.contains( i ));
 258                 ASSERT_TRUE( m.contains( other_item( i.nKey ), other_less()));
 259                 ASSERT_TRUE( m.find( i, []( key_type const& key, value_type& val ) {
 260                     EXPECT_EQ( key.nKey, val.nVal );
 261                     EXPECT_EQ( std::to_string( key.nKey ), val.strVal );
 262                 } ));
 263                 ASSERT_TRUE( m.find( i.nKey, []( key_type const& key, value_type& val ) {
 264                     EXPECT_EQ( key.nKey, val.nVal );
 265                     EXPECT_EQ( std::to_string( key.nKey ), val.strVal );
 266                 } ));
 267                 ASSERT_TRUE( m.find_with( other_item( i.nKey ), other_less(), []( key_type const& key, value_type& val ) {
 268                     EXPECT_EQ( key.nKey, val.nVal );
 269                     EXPECT_EQ( std::to_string( key.nKey ), val.strVal );
 270                 } ));
 271             }
 272             ASSERT_FALSE( m.empty());
 273             ASSERT_CONTAINER_SIZE( m, kkSize );
 274
 275             ASSERT_TRUE( m.check_consistency());
 276
 277             shuffle( arrKeys.begin(), arrKeys.end());
 278
 279             // erase/find
 280             for ( auto const& i : arrKeys ) {
 281                 value_type const& val( arrVals.at( i.nKey ));
 282
 283                 ASSERT_TRUE( m.contains( i.nKey ));
 284                 ASSERT_TRUE( m.contains( val.strVal ));
 285                 ASSERT_TRUE( m.contains( i ));
 286                 ASSERT_TRUE( m.contains( other_item( i.nKey ), other_less()));
 287                 ASSERT_TRUE( m.find( i, []( key_type const& key, value_type& val ) {
 288                     EXPECT_EQ( key.nKey, val.nVal );
 289                     EXPECT_EQ( std::to_string( key.nKey ), val.strVal );
 290                 } ));
 291                 ASSERT_TRUE( m.find( i.nKey, []( key_type const& key, value_type& val ) {
 292                     EXPECT_EQ( key.nKey, val.nVal );
 293                     EXPECT_EQ( std::to_string( key.nKey ), val.strVal );
 294                 } ));
 295                 ASSERT_TRUE( m.find_with( other_item( i.nKey ), other_less(), []( key_type const& key, value_type& val ) {
 296                     EXPECT_EQ( key.nKey, val.nVal );
 297                     EXPECT_EQ( std::to_string( key.nKey ), val.strVal );
 298                 } ));
 299
 300
 301                 switch ( i.nKey % 8 ) {
 302                 case 0:
 303                     ASSERT_TRUE( m.erase( i ));
 304                     ASSERT_FALSE( m.erase( i ));
 305                     break;
 306                 case 1:
 307                     ASSERT_TRUE( m.erase( i.nKey ));
 308                     ASSERT_FALSE( m.erase( i.nKey ));
 309                     break;
 310                 case 2:
 311                     ASSERT_TRUE( m.erase( val.strVal ));
 312                     ASSERT_FALSE( m.erase( val.strVal ));
 313                     break;
 314                 case 3:
 315                     ASSERT_TRUE( m.erase_with( other_item( i.nKey ), other_less()));
 316                     ASSERT_FALSE( m.erase_with( other_item( i.nKey ), other_less()));
 317                     break;
 318                 case 4:
 319                     ASSERT_TRUE( m.erase( i, []( key_type const& key, value_type& val ) {
 320                         EXPECT_EQ( key.nKey, val.nVal );
 321                         EXPECT_EQ( std::to_string( key.nKey ), val.strVal );
 322                     }));
 323                     ASSERT_FALSE( m.erase( i, []( key_type const& /*key*/, value_type& /*val*/ ) {
 324                         EXPECT_TRUE( false );
 325                     }));
 326                     break;
 327                 case 5:
 328                     ASSERT_TRUE( m.erase( i.nKey, []( key_type const& key, value_type& val ) {
 329                         EXPECT_EQ( key.nKey, val.nVal );
 330                         EXPECT_EQ( std::to_string( key.nKey ), val.strVal );
 331                     }));
 332                     ASSERT_FALSE( m.erase( i.nKey, []( key_type const& /*key*/, value_type& /*val*/ ) {
 333                         EXPECT_TRUE( false );
 334                     }));
 335                     break;
 336                 case 6:
 337                     ASSERT_TRUE( m.erase( val.strVal, []( key_type const& key, value_type& val ) {
 338                         EXPECT_EQ( key.nKey, val.nVal );
 339                         EXPECT_EQ( std::to_string( key.nKey ), val.strVal );
 340                     }));
 341                     ASSERT_FALSE( m.erase( val.strVal, []( key_type const& /*key*/, value_type& /*val*/ ) {
 342                         EXPECT_TRUE( false );
 343                     }));
 344                     break;
 345                 case 7:
 346                     ASSERT_TRUE( m.erase_with( other_item( i.nKey ), other_less(), []( key_type const& key, value_type& val ) {
 347                         EXPECT_EQ( key.nKey, val.nVal );
 348                         EXPECT_EQ( std::to_string( key.nKey ), val.strVal );
 349                     }));
 350                     ASSERT_FALSE( m.erase_with( other_item( i.nKey ), other_less(), []( key_type const& /*key*/, value_type& /*val*/ ) {
 351                         EXPECT_TRUE( false );
 352                     }));
 353                     break;
 354                 }
 355
 356                 ASSERT_FALSE( m.contains( i.nKey ));
 357                 ASSERT_FALSE( m.contains( i ));
 358                 ASSERT_FALSE( m.contains( val.strVal ));
 359                 ASSERT_FALSE( m.contains( other_item( i.nKey ), other_less()));
 360                 ASSERT_FALSE( m.find( i, []( key_type const& /*key*/, value_type& /*val*/ ) {
 361                     ASSERT_TRUE( false );
 362                 } ));
 363                 ASSERT_FALSE( m.find( i.nKey, []( key_type const& /*key*/, value_type& /*val*/ ) {
 364                     EXPECT_TRUE( false );
 365                 } ));
 366                 ASSERT_FALSE( m.find_with( other_item( i.nKey ), other_less(), []( key_type const& /*key*/, value_type& /*val*/ ) {
 367                     EXPECT_TRUE( false );
 368                 } ));
 369             }
 370             ASSERT_TRUE( m.empty());
 371             ASSERT_CONTAINER_SIZE( m, 0 );
 372
 373             // clear
 374             for ( auto const& i : arrKeys )
 375                 ASSERT_TRUE( m.insert( i ));
 376
 377             ASSERT_FALSE( m.empty());
 378             ASSERT_CONTAINER_SIZE( m, kkSize );
 379
 380             m.clear();
 381
 382             ASSERT_TRUE( m.empty());
 383             ASSERT_CONTAINER_SIZE( m, 0 );
 384
 385
 386             for ( auto const& i : arrKeys )
 387                 ASSERT_TRUE( m.insert( i, arrVals[ i.nKey ] ));
 388             ASSERT_FALSE( m.empty());
 389             ASSERT_CONTAINER_SIZE( m, kkSize );
 390
 391             typedef typename Map::exempt_ptr exempt_ptr;
 392
 393             // extract
 394             shuffle( arrKeys.begin(), arrKeys.end());
 395
 396             exempt_ptr xp;
 397             for ( auto const& i : arrKeys ) {
 398                 value_type const& val = arrVals.at( i.nKey );
 399
 400                 ASSERT_TRUE( m.contains( i.nKey ));
 401
 402                 switch ( i.nKey % 4 ) {
 403                 case 0:
 404                     xp = m.extract( i.nKey );
 405                     break;
 406                 case 1:
 407                     xp = m.extract( i );
 408                     break;
 409                 case 2:
 410                     xp = m.extract( val.strVal );
 411                     break;
 412                 case 3:
 413                     xp = m.extract_with( other_item( i.nKey ), other_less());
 414                     break;
 415                 }
 416                 ASSERT_FALSE( !xp );
 417                 EXPECT_EQ( xp->nVal, i.nKey );
 418
 419                 ASSERT_FALSE( m.contains( i.nKey ));
 420
 421                 switch ( i.nKey % 4 ) {
 422                 case 0:
 423                     xp = m.extract( i.nKey );
 424                     break;
 425                 case 1:
 426                     xp = m.extract( i );
 427                     break;
 428                 case 2:
 429                     xp = m.extract( val.strVal );
 430                     break;
 431                 case 3:
 432                     xp = m.extract_with( other_item( i.nKey ), other_less());
 433                     break;
 434                 }
 435                 EXPECT_TRUE( !xp );
 436             }
 437             ASSERT_TRUE( m.empty());
 438             ASSERT_CONTAINER_SIZE( m, 0 );
 439
 440
 441             // extract_min
 442             shuffle( arrKeys.begin(), arrKeys.end());
 443             for ( auto const& i : arrKeys )
 444                 ASSERT_TRUE( m.insert( i, arrVals[ i.nKey ] ));
 445
 446             size_t nCount = 0;
 447             int nKey = -1;
 448             while ( !m.empty()) {
 449                 switch ( nCount % 3 ) {
 450                 case 0:
 451                     xp = m.extract_min();
 452                     break;
 453                 case 1:
 454                     xp = m.extract_min( [nKey]( key_type const& key ) {
 455                         EXPECT_EQ( nKey + 1, key.nKey );
 456                     });
 457                     break;
 458                 case 2:
 459                     {
 460                         key_type key;
 461                         xp = m.extract_min_key( key );
 462                         EXPECT_EQ( nKey + 1, key.nKey );
 463                     }
 464                     break;
 465                 }
 466                 ASSERT_FALSE( !xp );
 467                 EXPECT_EQ( xp->nVal, nKey + 1 );
 468                 nKey = xp->nVal;
 469                 ++nCount;
 470             }
 471             xp = m.extract_min();
 472             ASSERT_TRUE( !xp );
 473             EXPECT_EQ( kkSize, nCount );
 474             ASSERT_TRUE( m.empty());
 475             ASSERT_CONTAINER_SIZE( m, 0 );
 476
 477             // extract_max
 478             shuffle( arrKeys.begin(), arrKeys.end());
 479             for ( auto const& i : arrKeys )
 480                 ASSERT_TRUE( m.insert( i, arrVals[ i.nKey ] ));
 481
 482             nKey = kkSize;
 483             nCount = 0;
 484             while ( !m.empty()) {
 485                 switch ( nCount % 3 ) {
 486                 case 0:
 487                     xp = m.extract_max();
 488                     break;
 489                 case 1:
 490                     xp = m.extract_max( [nKey]( key_type const& key ) {
 491                         EXPECT_EQ( nKey - 1, key.nKey );
 492                     } );
 493                     break;
 494                 case 2:
 495                     {
 496                         key_type key;
 497                         xp = m.extract_max_key( key );
 498                         EXPECT_EQ( nKey - 1, key.nKey );
 499                     }
 500                     break;
 501                 }
 502                 ASSERT_FALSE( !xp );
 503                 EXPECT_EQ( xp->nVal, nKey - 1 );
 504                 nKey = xp->nVal;
 505                 ++nCount;
 506             }
 507
 508             xp = m.extract_max();
 509             ASSERT_TRUE( !xp );
 510             EXPECT_EQ( kkSize, nCount );
 511             ASSERT_TRUE( m.empty());
 512             ASSERT_CONTAINER_SIZE( m, 0 );
 513
 514         }
 515     };
 516
 517
 518     template <class RCU>
 519     class BronsonAVLTreeMap: public bronson_avltree_map
 520     {
 521         typedef bronson_avltree_map base_class;
 522     public:
 523         typedef cds::urcu::gc<RCU> rcu_type;
 524
 525     protected:
 526         void SetUp()
 527         {
 528             RCU::Construct();
 529             cds::threading::Manager::attachThread();
 530         }
 531
 532         void TearDown()
 533         {
 534             cds::threading::Manager::detachThread();
 535             RCU::Destruct();
 536         }
 537     };
 538
 539     TYPED_TEST_CASE_P( BronsonAVLTreeMap );
 540
 541     TYPED_TEST_P( BronsonAVLTreeMap, compare )
 542     {
 543         typedef typename TestFixture::rcu_type rcu_type;
 544         typedef typename TestFixture::key_type key_type;
 545         typedef typename TestFixture::value_type value_type;
 546
 547         typedef cc::BronsonAVLTreeMap< rcu_type, key_type, value_type,
 548             typename cc::bronson_avltree::make_traits<
 549                 cds::opt::compare< typename TestFixture::cmp >
 550             >::type
 551         > map_type;
 552
 553         map_type m;
 554         this->test( m );
 555     }
 556
 557     TYPED_TEST_P( BronsonAVLTreeMap, less )
 558     {
 559         typedef typename TestFixture::rcu_type rcu_type;
 560         typedef typename TestFixture::key_type key_type;
 561         typedef typename TestFixture::value_type value_type;
 562
 563         typedef cc::BronsonAVLTreeMap< rcu_type, key_type, value_type,
 564             typename cc::bronson_avltree::make_traits<
 565                 cds::opt::less< typename TestFixture::less >
 566             >::type
 567         > map_type;
 568
 569         map_type m;
 570         this->test( m );
 571     }
 572
 573     TYPED_TEST_P( BronsonAVLTreeMap, cmpmix )
 574     {
 575         typedef typename TestFixture::rcu_type rcu_type;
 576         typedef typename TestFixture::key_type key_type;
 577         typedef typename TestFixture::value_type value_type;
 578
 579         typedef cc::BronsonAVLTreeMap< rcu_type, key_type, value_type,
 580             typename cc::bronson_avltree::make_traits<
 581                 cds::opt::less< typename TestFixture::less >
 582                 , cds::opt::compare< typename TestFixture::cmp >
 583             >::type
 584         > map_type;
 585
 586         map_type m;
 587         this->test( m );
 588     }
 589
 590     TYPED_TEST_P( BronsonAVLTreeMap, stat )
 591     {
 592         typedef typename TestFixture::rcu_type rcu_type;
 593         typedef typename TestFixture::key_type key_type;
 594         typedef typename TestFixture::value_type value_type;
 595
 596         struct map_traits: public cc::bronson_avltree::traits
 597         {
 598             typedef typename TestFixture::less  less;
 599             typedef cc::bronson_avltree::stat<> stat;
 600         };
 601
 602         typedef cc::BronsonAVLTreeMap< rcu_type, key_type, value_type, map_traits > map_type;
 603
 604         map_type m;
 605         this->test( m );
 606     }
 607
 608     TYPED_TEST_P( BronsonAVLTreeMap, item_counting )
 609     {
 610         typedef typename TestFixture::rcu_type rcu_type;
 611         typedef typename TestFixture::key_type key_type;
 612         typedef typename TestFixture::value_type value_type;
 613
 614         struct map_traits: public cc::bronson_avltree::traits
 615         {
 616             typedef typename TestFixture::cmp    compare;
 617             typedef cds::atomicity::item_counter item_counter;
 618         };
 619
 620         typedef cc::BronsonAVLTreeMap< rcu_type, key_type, value_type, map_traits > map_type;
 621
 622         map_type m;
 623         this->test( m );
 624     }
 625
 626     struct bronson_relaxed_insert_traits: public cc::bronson_avltree::traits
 627     {
 628         static bool const relaxed_insert = true;
 629     };
 630
 631     TYPED_TEST_P( BronsonAVLTreeMap, relaxed_insert )
 632     {
 633         typedef typename TestFixture::rcu_type rcu_type;
 634         typedef typename TestFixture::key_type key_type;
 635         typedef typename TestFixture::value_type value_type;
 636
 637         struct map_traits: public bronson_relaxed_insert_traits
 638         {
 639             typedef typename TestFixture::cmp    compare;
 640             typedef cds::atomicity::item_counter item_counter;
 641         };
 642
 643         typedef cc::BronsonAVLTreeMap< rcu_type, key_type, value_type, map_traits > map_type;
 644
 645         map_type m;
 646         this->test( m );
 647     }
 648
 649     TYPED_TEST_P( BronsonAVLTreeMap, seq_cst )
 650     {
 651         typedef typename TestFixture::rcu_type rcu_type;
 652         typedef typename TestFixture::key_type key_type;
 653         typedef typename TestFixture::value_type value_type;
 654
 655         struct map_traits: public cc::bronson_avltree::traits
 656         {
 657             typedef typename TestFixture::cmp    compare;
 658             typedef cds::atomicity::item_counter item_counter;
 659             typedef cds::opt::v::sequential_consistent memory_model;
 660         };
 661
 662         typedef cc::BronsonAVLTreeMap< rcu_type, key_type, value_type, map_traits > map_type;
 663
 664         map_type m;
 665         this->test( m );
 666     }
 667
 668     TYPED_TEST_P( BronsonAVLTreeMap, sync_monitor )
 669     {
 670         typedef typename TestFixture::rcu_type rcu_type;
 671         typedef typename TestFixture::key_type key_type;
 672         typedef typename TestFixture::value_type value_type;
 673
 674         struct map_traits: public cc::bronson_avltree::traits
 675         {
 676             typedef typename TestFixture::cmp    compare;
 677             typedef cds::atomicity::item_counter item_counter;
 678             typedef cds::sync::pool_monitor< cds::memory::vyukov_queue_pool< std::mutex >> sync_monitor;
 679         };
 680
 681         typedef cc::BronsonAVLTreeMap< rcu_type, key_type, value_type, map_traits > map_type;
 682
 683         map_type m;
 684         this->test( m );
 685     }
 686
 687     TYPED_TEST_P( BronsonAVLTreeMap, lazy_sync_monitor )
 688     {
 689         typedef typename TestFixture::rcu_type rcu_type;
 690         typedef typename TestFixture::key_type key_type;
 691         typedef typename TestFixture::value_type value_type;
 692
 693         struct map_traits: public cc::bronson_avltree::traits
 694         {
 695             typedef typename TestFixture::cmp    compare;
 696             typedef cds::atomicity::item_counter item_counter;
 697             typedef cds::sync::pool_monitor< cds::memory::lazy_vyukov_queue_pool< std::mutex >> sync_monitor;
 698         };
 699
 700         typedef cc::BronsonAVLTreeMap< rcu_type, key_type, value_type, map_traits > map_type;
 701
 702         map_type m;
 703         this->test( m );
 704     }
 705
 706     TYPED_TEST_P( BronsonAVLTreeMap, rcu_check_deadlock )
 707     {
 708         typedef typename TestFixture::rcu_type rcu_type;
 709         typedef typename TestFixture::key_type key_type;
 710         typedef typename TestFixture::value_type value_type;
 711
 712         struct map_traits: public cc::bronson_avltree::traits
 713         {
 714             typedef typename TestFixture::cmp    compare;
 715             typedef cds::atomicity::item_counter item_counter;
 716             typedef cds::sync::pool_monitor< cds::memory::vyukov_queue_pool< std::mutex >> sync_monitor;
 717             typedef cds::opt::v::rcu_assert_deadlock rcu_check_deadlock;
 718         };
 719
 720         typedef cc::BronsonAVLTreeMap< rcu_type, key_type, value_type, map_traits > map_type;
 721
 722         map_type m;
 723         this->test( m );
 724     }
 725
 726     TYPED_TEST_P( BronsonAVLTreeMap, rcu_no_check_deadlock )
 727     {
 728         typedef typename TestFixture::rcu_type rcu_type;
 729         typedef typename TestFixture::key_type key_type;
 730         typedef typename TestFixture::value_type value_type;
 731
 732         struct map_traits: public cc::bronson_avltree::traits
 733         {
 734             typedef typename TestFixture::cmp    compare;
 735             typedef cds::atomicity::item_counter item_counter;
 736             typedef cds::sync::pool_monitor< cds::memory::lazy_vyukov_queue_pool< std::mutex >> sync_monitor;
 737             typedef cds::opt::v::rcu_no_check_deadlock rcu_check_deadlock;
 738         };
 739
 740         typedef cc::BronsonAVLTreeMap< rcu_type, key_type, value_type, map_traits > map_type;
 741
 742         map_type m;
 743         this->test( m );
 744     }
 745
 746     REGISTER_TYPED_TEST_CASE_P( BronsonAVLTreeMap,
 747         compare, less, cmpmix, stat, item_counting, relaxed_insert, seq_cst, sync_monitor, lazy_sync_monitor, rcu_check_deadlock, rcu_no_check_deadlock
 748     );
 749
 750 } // namespace
 751
 752 #endif // #ifndef CDSUNIT_TREE_TEST_BRONSON_AVLTREE_MAP_H