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