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