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