test/unit/tree/test_tree_set.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-2016
   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_SET_TEST_TREE_SET_H
  32 #define CDSUNIT_SET_TEST_TREE_SET_H
  33
  34 #include <cds_test/check_size.h>
  35 #include <cds_test/fixture.h>
  36
  37 // forward declaration
  38 namespace cds { namespace container {}}
  39
  40 namespace cds_test {
  41
  42     class container_tree_set : public fixture
  43     {
  44     public:
  45         static size_t const kSize = 1000;
  46
  47         struct stat
  48         {
  49             unsigned int nFindCount;
  50             unsigned int nUpdateNewCount;
  51             unsigned int nUpdateCount;
  52             mutable unsigned int nEraseCount;
  53
  54             stat()
  55             {
  56                 clear_stat();
  57             }
  58
  59             void clear_stat()
  60             {
  61                 memset( this, 0, sizeof( *this ));
  62             }
  63         };
  64
  65         struct other_item {
  66             int nKey;
  67
  68             explicit other_item( int k )
  69                 : nKey( k )
  70             {}
  71
  72             int key() const
  73             {
  74                 return nKey;
  75             }
  76         };
  77
  78         struct int_item: public stat
  79         {
  80             int nKey;
  81             int nVal;
  82             std::string strVal;
  83
  84             int_item()
  85                 : nKey( 0 )
  86                 , nVal( 0 )
  87             {}
  88
  89             explicit int_item( int k )
  90                 : nKey( k )
  91                 , nVal( k * 2 )
  92             {}
  93
  94             template <typename Q>
  95             explicit int_item( Q const& src )
  96                 : nKey( src.key())
  97                 , nVal( 0 )
  98             {}
  99
 100             int_item( int_item const& src )
 101                 : nKey( src.nKey )
 102                 , nVal( src.nVal )
 103                 , strVal( src.strVal )
 104             {}
 105
 106             int_item( int_item&& src )
 107                 : nKey( src.nKey )
 108                 , nVal( src.nVal )
 109                 , strVal( std::move( src.strVal ))
 110             {}
 111
 112             int_item( int k, std::string&& s )
 113                 : nKey( k )
 114                 , nVal( k * 2 )
 115                 , strVal( std::move( s ))
 116             {}
 117
 118             explicit int_item( other_item const& s )
 119                 : nKey( s.key())
 120                 , nVal( s.key() * 2 )
 121             {}
 122
 123             int key() const
 124             {
 125                 return nKey;
 126             }
 127         };
 128
 129         struct key_extractor
 130         {
 131             template <typename T>
 132             void operator()( int& key, T const& val ) const
 133             {
 134                 key = val.key();
 135             }
 136         };
 137
 138         struct simple_item_counter {
 139             size_t  m_nCount;
 140
 141             simple_item_counter()
 142                 : m_nCount( 0 )
 143             {}
 144
 145             size_t operator ++()
 146             {
 147                 return ++m_nCount;
 148             }
 149
 150             size_t operator --()
 151             {
 152                 return --m_nCount;
 153             }
 154
 155             void reset()
 156             {
 157                 m_nCount = 0;
 158             }
 159
 160             operator size_t() const
 161             {
 162                 return m_nCount;
 163             }
 164
 165         };
 166
 167         struct less
 168         {
 169             bool operator ()( int_item const& v1, int_item const& v2 ) const
 170             {
 171                 return v1.key() < v2.key();
 172             }
 173
 174             bool operator()( int lhs, int rhs ) const
 175             {
 176                 return lhs < rhs;
 177             }
 178
 179             template <typename Q>
 180             bool operator ()( int_item const& v1, const Q& v2 ) const
 181             {
 182                 return v1.key() < v2;
 183             }
 184
 185             template <typename Q>
 186             bool operator ()( const Q& v1, int_item const& v2 ) const
 187             {
 188                 return v1 < v2.key();
 189             }
 190         };
 191
 192         struct cmp {
 193             int operator ()( int_item const& v1, int_item const& v2 ) const
 194             {
 195                 if ( v1.key() < v2.key())
 196                     return -1;
 197                 return v1.key() > v2.key() ? 1 : 0;
 198             }
 199
 200             int operator()( int lhs, int rhs ) const
 201             {
 202                 return lhs - rhs;
 203             }
 204
 205             template <typename T>
 206             int operator ()( T const& v1, int v2 ) const
 207             {
 208                 if ( v1.key() < v2 )
 209                     return -1;
 210                 return v1.key() > v2 ? 1 : 0;
 211             }
 212
 213             template <typename T>
 214             int operator ()( int v1, T const& v2 ) const
 215             {
 216                 if ( v1 < v2.key())
 217                     return -1;
 218                 return v1 > v2.key() ? 1 : 0;
 219             }
 220         };
 221
 222         struct other_less {
 223             template <typename Q, typename T>
 224             bool operator()( Q const& lhs, T const& rhs ) const
 225             {
 226                 return lhs.key() < rhs.key();
 227             }
 228
 229             bool operator()( int lhs, other_item const& rhs ) const
 230             {
 231                 return lhs < rhs.key();
 232             }
 233
 234             bool operator()( other_item const& lhs, int rhs ) const
 235             {
 236                 return lhs.key() < rhs;
 237             }
 238         };
 239
 240     protected:
 241         template <typename Set>
 242         void test( Set& s )
 243         {
 244             // Precondition: set is empty
 245             // Postcondition: set is empty
 246
 247             ASSERT_TRUE( s.empty());
 248             ASSERT_CONTAINER_SIZE( s, 0 );
 249             size_t const nSetSize = kSize;
 250
 251             typedef typename Set::value_type value_type;
 252
 253             std::vector< value_type > data;
 254             std::vector< size_t> indices;
 255             data.reserve( kSize );
 256             indices.reserve( kSize );
 257             for ( size_t key = 0; key < kSize; ++key ) {
 258                 data.push_back( value_type( static_cast<int>(key)));
 259                 indices.push_back( key );
 260             }
 261             shuffle( indices.begin(), indices.end());
 262
 263             // insert/find
 264             for ( auto idx : indices ) {
 265                 auto& i = data[idx];
 266
 267                 ASSERT_FALSE( s.contains( i.nKey ));
 268                 ASSERT_FALSE( s.contains( i ));
 269                 ASSERT_FALSE( s.contains( other_item( i.key()), other_less()));
 270                 ASSERT_FALSE( s.find( i.nKey, []( value_type&, int ) {} ));
 271                 ASSERT_FALSE( s.find( i, []( value_type&, value_type const& ) {} ));
 272                 ASSERT_FALSE( s.find_with( other_item( i.key()), other_less(), []( value_type&, other_item const& ) {} ));
 273
 274                 std::pair<bool, bool> updResult;
 275
 276                 std::string str;
 277                 updResult = s.update( i.key(), []( bool, value_type&, int )
 278                 {
 279                     ASSERT_TRUE( false );
 280                 }, false );
 281                 EXPECT_FALSE( updResult.first );
 282                 EXPECT_FALSE( updResult.second );
 283
 284                 switch ( idx % 8 ) {
 285                 case 0:
 286                     ASSERT_TRUE( s.insert( i ));
 287                     ASSERT_FALSE( s.insert( i ));
 288                     updResult = s.update( i, []( bool bNew, value_type& val, value_type const& arg)
 289                         {
 290                             EXPECT_FALSE( bNew );
 291                             EXPECT_EQ( val.key(), arg.key());
 292                         }, false );
 293                     EXPECT_TRUE( updResult.first );
 294                     EXPECT_FALSE( updResult.second );
 295                     break;
 296                 case 1:
 297                     ASSERT_TRUE( s.insert( i.key()));
 298                     ASSERT_FALSE( s.insert( i.key()));
 299                     updResult = s.update( i.key(), []( bool bNew, value_type& val, int arg)
 300                         {
 301                             EXPECT_FALSE( bNew );
 302                             EXPECT_EQ( val.key(), arg );
 303                         }, false );
 304                     EXPECT_TRUE( updResult.first );
 305                     EXPECT_FALSE( updResult.second );
 306                     break;
 307                 case 2:
 308                     ASSERT_TRUE( s.insert( i, []( value_type& v ) { ++v.nFindCount; } ));
 309                     ASSERT_FALSE( s.insert( i, []( value_type& v ) { ++v.nFindCount; } ));
 310                     ASSERT_TRUE( s.find( i.nKey, []( value_type const& v, int key )
 311                         {
 312                             EXPECT_EQ( v.key(), key );
 313                             EXPECT_EQ( v.nFindCount, 1u );
 314                         }));
 315                     break;
 316                 case 3:
 317                     ASSERT_TRUE( s.insert( i.key(), []( value_type& v ) { ++v.nFindCount; } ));
 318                     ASSERT_FALSE( s.insert( i.key(), []( value_type& v ) { ++v.nFindCount; } ));
 319                     ASSERT_TRUE( s.find( i.nKey, []( value_type const& v, int key )
 320                         {
 321                             EXPECT_EQ( v.key(), key );
 322                             EXPECT_EQ( v.nFindCount, 1u );
 323                         }));
 324                     break;
 325                 case 4:
 326                     updResult = s.update( i, []( bool bNew, value_type& v, value_type const& arg )
 327                         {
 328                             EXPECT_TRUE( bNew );
 329                             EXPECT_EQ( v.key(), arg.key());
 330                             ++v.nUpdateNewCount;
 331                         });
 332                     EXPECT_TRUE( updResult.first );
 333                     EXPECT_TRUE( updResult.second );
 334
 335                     updResult = s.update( i, []( bool bNew, value_type& v, value_type const& arg )
 336                         {
 337                             EXPECT_FALSE( bNew );
 338                             EXPECT_EQ( v.key(), arg.key());
 339                             ++v.nUpdateNewCount;
 340                         }, false );
 341                     EXPECT_TRUE( updResult.first );
 342                     EXPECT_FALSE( updResult.second );
 343
 344                     ASSERT_TRUE( s.find( i.nKey, []( value_type const& v, int key )
 345                         {
 346                             EXPECT_EQ( v.key(), key );
 347                             EXPECT_EQ( v.nUpdateNewCount, 2u );
 348                         }));
 349                     break;
 350                 case 5:
 351                     updResult = s.update( i.key(), []( bool bNew, value_type& v, int arg )
 352                         {
 353                             EXPECT_TRUE( bNew );
 354                             EXPECT_EQ( v.key(), arg );
 355                             ++v.nUpdateNewCount;
 356                         });
 357                     EXPECT_TRUE( updResult.first );
 358                     EXPECT_TRUE( updResult.second );
 359
 360                     updResult = s.update( i.key(), []( bool bNew, value_type& v, int arg )
 361                         {
 362                             EXPECT_FALSE( bNew );
 363                             EXPECT_EQ( v.key(), arg );
 364                             ++v.nUpdateNewCount;
 365                         }, false );
 366                     EXPECT_TRUE( updResult.first );
 367                     EXPECT_FALSE( updResult.second );
 368
 369                     ASSERT_TRUE( s.find( i, []( value_type const& v, value_type const& arg )
 370                         {
 371                             EXPECT_EQ( v.key(), arg.key());
 372                             EXPECT_EQ( v.nUpdateNewCount, 2u );
 373                         }));
 374                     break;
 375                 case 6:
 376                     ASSERT_TRUE( s.emplace( i.key()));
 377                     ASSERT_TRUE( s.find( i, []( value_type const& v, value_type const& arg )
 378                         {
 379                             EXPECT_EQ( v.key(), arg.key());
 380                             EXPECT_EQ( v.nVal, arg.nVal );
 381                         }));
 382                     break;
 383                 case 7:
 384                     str = "Hello!";
 385                     ASSERT_TRUE( s.emplace( i.key(), std::move( str )));
 386                     EXPECT_TRUE( str.empty());
 387                     ASSERT_TRUE( s.find( i, []( value_type const& v, value_type const& arg )
 388                         {
 389                             EXPECT_EQ( v.key(), arg.key());
 390                             EXPECT_EQ( v.nVal, arg.nVal );
 391                             EXPECT_EQ( v.strVal, std::string( "Hello!" ));
 392                         } ));
 393                     break;
 394                 default:
 395                     // forgot anything?..
 396                     ASSERT_TRUE( false );
 397                 }
 398
 399                 ASSERT_TRUE( s.contains( i.nKey ));
 400                 ASSERT_TRUE( s.contains( i ));
 401                 ASSERT_TRUE( s.contains( other_item( i.key()), other_less()));
 402                 ASSERT_TRUE( s.find( i.nKey, []( value_type&, int ) {} ));
 403                 ASSERT_TRUE( s.find( i, []( value_type&, value_type const& ) {} ));
 404                 ASSERT_TRUE( s.find_with( other_item( i.key()), other_less(), []( value_type&, other_item const& ) {} ));
 405             }
 406
 407             ASSERT_FALSE( s.empty());
 408             ASSERT_CONTAINER_SIZE( s, nSetSize );
 409
 410             ASSERT_TRUE( s.check_consistency());
 411
 412             // erase
 413             shuffle( indices.begin(), indices.end());
 414             for ( auto idx : indices ) {
 415                 auto& i = data[idx];
 416
 417                 ASSERT_TRUE( s.contains( i.nKey ));
 418                 ASSERT_TRUE( s.contains( i ));
 419                 ASSERT_TRUE( s.contains( other_item( i.key()), other_less()));
 420                 ASSERT_TRUE( s.find( i.nKey, []( value_type& v, int )
 421                     {
 422                         v.nFindCount = 1;
 423                     }));
 424                 ASSERT_TRUE( s.find( i, []( value_type& v, value_type const& )
 425                     {
 426                         EXPECT_EQ( ++v.nFindCount, 2u );
 427                     }));
 428                 ASSERT_TRUE( s.find_with( other_item( i.key()), other_less(), []( value_type& v, other_item const& )
 429                     {
 430                         EXPECT_EQ( ++v.nFindCount, 3u );
 431                     }));
 432
 433                 int nKey = i.key() - 1;
 434                 switch ( idx % 6 ) {
 435                 case 0:
 436                     ASSERT_TRUE( s.erase( i.key()));
 437                     ASSERT_FALSE( s.erase( i.key()));
 438                     break;
 439                 case 1:
 440                     ASSERT_TRUE( s.erase( i ));
 441                     ASSERT_FALSE( s.erase( i ));
 442                     break;
 443                 case 2:
 444                     ASSERT_TRUE( s.erase_with( other_item( i.key()), other_less()));
 445                     ASSERT_FALSE( s.erase_with( other_item( i.key()), other_less()));
 446                     break;
 447                 case 3:
 448                     ASSERT_TRUE( s.erase( i.key(), [&nKey]( value_type const& v )
 449                         {
 450                             nKey = v.key();
 451                         } ));
 452                     EXPECT_EQ( i.key(), nKey );
 453
 454                     nKey = i.key() - 1;
 455                     ASSERT_FALSE( s.erase( i.key(), [&nKey]( value_type const& v )
 456                         {
 457                             nKey = v.key();
 458                         } ));
 459                     EXPECT_EQ( i.key(), nKey + 1 );
 460                     break;
 461                 case 4:
 462                     ASSERT_TRUE( s.erase( i, [&nKey]( value_type const& v )
 463                         {
 464                             nKey = v.key();
 465                         } ));
 466                     EXPECT_EQ( i.key(), nKey );
 467
 468                     nKey = i.key() - 1;
 469                     ASSERT_FALSE( s.erase( i, [&nKey]( value_type const& v )
 470                         {
 471                             nKey = v.key();
 472                         } ));
 473                     EXPECT_EQ( i.key(), nKey + 1 );
 474                     break;
 475                 case 5:
 476                     ASSERT_TRUE( s.erase_with( other_item( i.key()), other_less(), [&nKey]( value_type const& v )
 477                         {
 478                             nKey = v.key();
 479                         } ));
 480                     EXPECT_EQ( i.key(), nKey );
 481
 482                     nKey = i.key() - 1;
 483                     ASSERT_FALSE( s.erase_with( other_item( i.key()), other_less(), [&nKey]( value_type const& v )
 484                         {
 485                             nKey = v.key();
 486                         } ));
 487                     EXPECT_EQ( i.key(), nKey + 1 );
 488                     break;
 489                 }
 490
 491                 ASSERT_FALSE( s.contains( i.nKey ));
 492                 ASSERT_FALSE( s.contains( i ));
 493                 ASSERT_FALSE( s.contains( other_item( i.key()), other_less()));
 494                 ASSERT_FALSE( s.find( i.nKey, []( value_type&, int ) {} ));
 495                 ASSERT_FALSE( s.find( i, []( value_type&, value_type const& ) {} ));
 496                 ASSERT_FALSE( s.find_with( other_item( i.key()), other_less(), []( value_type&, other_item const& ) {} ));
 497             }
 498             ASSERT_TRUE( s.empty());
 499             ASSERT_CONTAINER_SIZE( s, 0 );
 500
 501
 502             // clear
 503             for ( auto& i : data ) {
 504                 ASSERT_TRUE( s.insert( i ));
 505             }
 506
 507             ASSERT_FALSE( s.empty());
 508             ASSERT_CONTAINER_SIZE( s, nSetSize );
 509
 510             s.clear();
 511
 512             ASSERT_TRUE( s.empty());
 513             ASSERT_CONTAINER_SIZE( s, 0 );
 514         }
 515     };
 516
 517 } // namespace cds_test
 518
 519 #endif // CDSUNIT_SET_TEST_TREE_SET_H