test/unit/intrusive-set/test_intrusive_michael_iterable.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_INTRUSIVE_MICHAEL_ITERABLE_H
  32 #define CDSUNIT_SET_TEST_INTRUSIVE_MICHAEL_ITERABLE_H
  33
  34 #include <cds_test/check_size.h>
  35 #include <cds_test/fixture.h>
  36
  37 #include <cds/opt/hash.h>
  38 #include <functional>   // ref
  39
  40 // forward declaration
  41 namespace cds { namespace intrusive {}}
  42
  43 namespace cds_test {
  44
  45     namespace ci = cds::intrusive;
  46     namespace co = cds::opt;
  47
  48     class intrusive_set: public fixture
  49     {
  50     public:
  51         static size_t const kSize = 100;
  52
  53         struct stat
  54         {
  55             unsigned int nDisposeCount  ;   // count of disposer calling
  56             unsigned int nFindCount     ;   // count of find-functor calling
  57             unsigned int nUpdateNewCount;
  58             unsigned int nUpdateCount;
  59             mutable unsigned int nEraseCount;
  60
  61             stat()
  62             {
  63                 clear_stat();
  64             }
  65
  66             void clear_stat()
  67             {
  68                 memset( this, 0, sizeof( *this ) );
  69             }
  70         };
  71
  72         struct item_type: public stat
  73         {
  74             int nKey;
  75             int nVal;
  76
  77             item_type( int k )
  78                 : nKey(k)
  79                 , nVal(0)
  80             {}
  81
  82             int key() const
  83             {
  84                 return nKey;
  85             }
  86         };
  87
  88         struct hash_int {
  89             size_t operator()( int i ) const
  90             {
  91                 return co::v::hash<int>()( i );
  92             }
  93             template <typename Q>
  94             size_t operator()( Q const& i ) const
  95             {
  96                 return (*this)( i.key());
  97             }
  98         };
  99
 100         struct simple_item_counter {
 101             size_t  m_nCount;
 102
 103             simple_item_counter()
 104                 : m_nCount(0)
 105             {}
 106
 107             size_t operator ++()
 108             {
 109                 return ++m_nCount;
 110             }
 111
 112             size_t operator --()
 113             {
 114                 return --m_nCount;
 115             }
 116
 117             void reset()
 118             {
 119                 m_nCount = 0;
 120             }
 121
 122             operator size_t() const
 123             {
 124                 return m_nCount;
 125             }
 126
 127         };
 128
 129
 130         template <typename T>
 131         struct less
 132         {
 133             bool operator ()(const T& v1, const T& v2 ) const
 134             {
 135                 return v1.key() < v2.key();
 136             }
 137
 138             template <typename Q>
 139             bool operator ()(const T& v1, const Q& v2 ) const
 140             {
 141                 return v1.key() < v2;
 142             }
 143
 144             template <typename Q>
 145             bool operator ()(const Q& v1, const T& v2 ) const
 146             {
 147                 return v1 < v2.key();
 148             }
 149         };
 150
 151         template <typename T>
 152         struct cmp {
 153             int operator ()(const T& v1, const T& v2 ) const
 154             {
 155                 if ( v1.key() < v2.key() )
 156                     return -1;
 157                 return v1.key() > v2.key() ? 1 : 0;
 158             }
 159
 160             template <typename Q>
 161             int operator ()(const T& v1, const Q& v2 ) const
 162             {
 163                 if ( v1.key() < v2 )
 164                     return -1;
 165                 return v1.key() > v2 ? 1 : 0;
 166             }
 167
 168             template <typename Q>
 169             int operator ()(const Q& v1, const T& v2 ) const
 170             {
 171                 if ( v1 < v2.key() )
 172                     return -1;
 173                 return v1 > v2.key() ? 1 : 0;
 174             }
 175         };
 176
 177         struct other_item {
 178             int nKey;
 179
 180             explicit other_item( int k )
 181                 : nKey( k )
 182             {}
 183
 184             int key() const
 185             {
 186                 return nKey;
 187             }
 188         };
 189
 190         struct other_less {
 191             template <typename Q, typename T>
 192             bool operator()( Q const& lhs, T const& rhs ) const
 193             {
 194                 return lhs.key() < rhs.key();
 195             }
 196         };
 197
 198         struct mock_disposer
 199         {
 200             template <typename T>
 201             void operator ()( T * p )
 202             {
 203                 ++p->nDisposeCount;
 204             }
 205         };
 206
 207     protected:
 208         template <class Set>
 209         void test( Set& s )
 210         {
 211             // Precondition: set is empty
 212             // Postcondition: set is empty
 213
 214             ASSERT_TRUE( s.empty() );
 215             ASSERT_CONTAINER_SIZE( s, 0 );
 216             size_t const nSetSize = kSize;
 217
 218             typedef typename Set::value_type value_type;
 219
 220             std::vector< value_type > data;
 221             std::vector< size_t> indices;
 222             data.reserve( kSize );
 223             indices.reserve( kSize );
 224             for ( size_t key = 0; key < kSize; ++key ) {
 225                 data.push_back( value_type( static_cast<int>( key )));
 226                 indices.push_back( key );
 227             }
 228             shuffle( indices.begin(), indices.end() );
 229
 230             // insert/find
 231             for ( auto idx : indices ) {
 232                 auto& i = data[ idx ];
 233
 234                 ASSERT_FALSE( s.contains( i.nKey ));
 235                 ASSERT_FALSE( s.contains( i ));
 236                 ASSERT_FALSE( s.contains( other_item( i.key()), other_less()));
 237                 ASSERT_FALSE( s.find( i.nKey, []( value_type&, int ) {} ));
 238                 ASSERT_FALSE( s.find_with( other_item( i.key()), other_less(), []( value_type&, other_item const& ) {} ));
 239                 ASSERT_TRUE( s.find( i.nKey ) == s.end());
 240                 ASSERT_TRUE( s.find_with( other_item( i.key() ), other_less()) == s.end());
 241
 242                 std::pair<bool, bool> updResult;
 243
 244                 updResult = s.update( i, []( value_type&, value_type* )
 245                 {
 246                     ASSERT_TRUE( false );
 247                 }, false );
 248                 EXPECT_FALSE( updResult.first );
 249                 EXPECT_FALSE( updResult.second );
 250
 251                 updResult = s.upsert( i, false );
 252                 EXPECT_FALSE( updResult.first );
 253                 EXPECT_FALSE( updResult.second );
 254
 255                 switch ( i.key() % 4 ) {
 256                 case 0:
 257                     ASSERT_TRUE( s.insert( i ));
 258                     ASSERT_FALSE( s.insert( i ));
 259                     updResult = s.update( i, []( value_type& val, value_type* arg)
 260                         {
 261                             ASSERT_TRUE( arg != nullptr );
 262                             EXPECT_EQ( val.key(), arg->key() );
 263                         }, false );
 264                     EXPECT_TRUE( updResult.first );
 265                     EXPECT_FALSE( updResult.second );
 266                     break;
 267                 case 1:
 268                     EXPECT_EQ( i.nUpdateNewCount, 0u );
 269                     ASSERT_TRUE( s.insert( i, []( value_type& v ) { ++v.nUpdateNewCount;} ));
 270                     EXPECT_EQ( i.nUpdateNewCount, 1u );
 271                     ASSERT_FALSE( s.insert( i, []( value_type& v ) { ++v.nUpdateNewCount;} ) );
 272                     EXPECT_EQ( i.nUpdateNewCount, 1u );
 273                     i.nUpdateNewCount = 0;
 274                     break;
 275                 case 2:
 276                     updResult = s.update( i, []( value_type& /*val*/, value_type* arg )
 277                     {
 278                         EXPECT_TRUE( arg == nullptr );
 279                     });
 280                     EXPECT_TRUE( updResult.first );
 281                     EXPECT_TRUE( updResult.second );
 282                     break;
 283                 case 3:
 284                     updResult = s.upsert( i );
 285                     EXPECT_TRUE( updResult.first );
 286                     EXPECT_TRUE( updResult.second );
 287                     break;
 288                 }
 289
 290                 ASSERT_TRUE( s.contains( i.nKey ) );
 291                 ASSERT_TRUE( s.contains( i ) );
 292                 ASSERT_TRUE( s.contains( other_item( i.key() ), other_less()));
 293                 EXPECT_EQ( i.nFindCount, 0 );
 294                 ASSERT_TRUE( s.find( i.nKey, []( value_type& v, int ) { ++v.nFindCount; } ));
 295                 EXPECT_EQ( i.nFindCount, 1 );
 296                 ASSERT_TRUE( s.find_with( other_item( i.key() ), other_less(), []( value_type& v, other_item const& ) { ++v.nFindCount; } ));
 297                 EXPECT_EQ( i.nFindCount, 2 );
 298                 ASSERT_TRUE( s.find( i.nKey ) != s.end() );
 299                 ASSERT_TRUE( s.find_with( other_item( i.key() ), other_less() ) != s.end() );
 300                 EXPECT_EQ( s.find( i.nKey )->nKey, i.key() );
 301                 EXPECT_EQ( s.find_with( other_item( i.key() ), other_less())->nKey, i.key() );
 302             }
 303             ASSERT_FALSE( s.empty() );
 304             ASSERT_CONTAINER_SIZE( s, nSetSize );
 305
 306             std::for_each( data.begin(), data.end(), []( value_type& v ) { v.clear_stat(); });
 307
 308             // erase
 309             shuffle( indices.begin(), indices.end() );
 310             for ( auto idx : indices ) {
 311                 auto& i = data[ idx ];
 312
 313                 ASSERT_TRUE( s.contains( i.nKey ) );
 314                 ASSERT_TRUE( s.contains( i ) );
 315                 ASSERT_TRUE( s.contains( other_item( i.key() ), other_less() ) );
 316                 EXPECT_EQ( i.nFindCount, 0 );
 317                 ASSERT_TRUE( s.find( i.nKey, []( value_type& v, int ) { ++v.nFindCount; } ) );
 318                 EXPECT_EQ( i.nFindCount, 1 );
 319                 ASSERT_TRUE( s.find_with( other_item( i.key() ), other_less(), []( value_type& v, other_item const& ) { ++v.nFindCount; } ) );
 320                 EXPECT_EQ( i.nFindCount, 2 );
 321                 ASSERT_TRUE( s.find( i.nKey ) != s.end() );
 322                 ASSERT_TRUE( s.find_with( other_item( i.key() ), other_less()) != s.end() );
 323                 EXPECT_EQ( s.find( i.nKey )->nKey, i.key() );
 324                 EXPECT_EQ( s.find_with( other_item( i.key() ), other_less())->nKey, i.key() );
 325
 326
 327                 value_type v( i );
 328                 switch ( i.key() % 6 ) {
 329                 case 0:
 330                     ASSERT_FALSE( s.unlink( v ));
 331                     ASSERT_TRUE( s.unlink( i ));
 332                     ASSERT_FALSE( s.unlink( i ) );
 333                     break;
 334                 case 1:
 335                     ASSERT_TRUE( s.erase( i.key()));
 336                     ASSERT_FALSE( s.erase( i.key() ) );
 337                     break;
 338                 case 2:
 339                     ASSERT_TRUE( s.erase( v ));
 340                     ASSERT_FALSE( s.erase( v ) );
 341                     break;
 342                 case 3:
 343                     ASSERT_TRUE( s.erase_with( other_item( i.key()), other_less()));
 344                     ASSERT_FALSE( s.erase_with( other_item( i.key() ), other_less() ) );
 345                     break;
 346                 case 4:
 347                     EXPECT_EQ( i.nEraseCount, 0u );
 348                     ASSERT_TRUE( s.erase( v, []( value_type& val ) { ++val.nEraseCount; } ));
 349                     EXPECT_EQ( i.nEraseCount, 1u );
 350                     ASSERT_FALSE( s.erase( v, []( value_type& val ) { ++val.nEraseCount; } ));
 351                     EXPECT_EQ( i.nEraseCount, 1u );
 352                     break;
 353                 case 5:
 354                     EXPECT_EQ( i.nEraseCount, 0u );
 355                     ASSERT_TRUE( s.erase_with( other_item( i.key() ), other_less(), []( value_type& val ) { ++val.nEraseCount; } ));
 356                     EXPECT_EQ( i.nEraseCount, 1u );
 357                     ASSERT_FALSE( s.erase_with( other_item( i.key() ), other_less(), []( value_type& val ) { ++val.nEraseCount; } ));
 358                     EXPECT_EQ( i.nEraseCount, 1u );
 359                     break;
 360                 }
 361
 362                 ASSERT_FALSE( s.contains( i.nKey ));
 363                 ASSERT_FALSE( s.contains( i ));
 364                 ASSERT_FALSE( s.contains( other_item( i.key()), other_less()));
 365                 ASSERT_FALSE( s.find( i.nKey, []( value_type&, int ) {} ));
 366                 ASSERT_FALSE( s.find_with( other_item( i.key()), other_less(), []( value_type&, other_item const& ) {} ));
 367                 ASSERT_TRUE( s.find( i.nKey ) == s.end() );
 368                 ASSERT_TRUE( s.find_with( other_item( i.key() ), other_less() ) == s.end() );
 369             }
 370             ASSERT_TRUE( s.empty() );
 371             ASSERT_CONTAINER_SIZE( s, 0 );
 372
 373             // Force retiring cycle
 374             Set::gc::force_dispose();
 375             for ( auto& i : data ) {
 376                 EXPECT_EQ( i.nDisposeCount, 1u );
 377             }
 378
 379             // clear
 380             for ( auto& i : data ) {
 381                 i.clear_stat();
 382                 ASSERT_TRUE( s.insert( i ));
 383             }
 384             ASSERT_FALSE( s.empty() );
 385             ASSERT_CONTAINER_SIZE( s, nSetSize );
 386
 387             // Iterator test
 388             for ( auto it = s.begin(); it != s.end(); ++it ) {
 389                 ++it->nFindCount;
 390             }
 391             for ( auto it = s.cbegin(); it != s.cend(); ++it ) {
 392                 EXPECT_EQ( it->nFindCount, 1u );
 393             }
 394             for ( auto& i : data ) {
 395                 EXPECT_EQ( i.nFindCount, 1u );
 396             }
 397
 398             // clear test
 399             s.clear();
 400
 401             ASSERT_TRUE( s.empty());
 402             ASSERT_CONTAINER_SIZE( s, 0u );
 403             ASSERT_TRUE( s.begin() == s.end() );
 404             ASSERT_TRUE( s.cbegin() == s.cend() );
 405
 406             // Force retiring cycle
 407             Set::gc::force_dispose();
 408             for ( auto& i : data ) {
 409                 EXPECT_EQ( i.nDisposeCount, 1u );
 410             }
 411
 412         }
 413     };
 414
 415 } // namespace cds_test
 416
 417 #endif // #ifndef CDSUNIT_SET_TEST_INTRUSIVE_MICHAEL_ITERABLE_H