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