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