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