test/unit/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_MAP_TEST_MAP_H
  32 #define CDSUNIT_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 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 % 16 ) {
  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& v ) {
 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& v ) {
 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& v ) {
 152                         EXPECT_TRUE( false );
 153                     } ));
 154                     break;
 155                 case 9:
 156                     updResult = m.update( i.nKey, []( bool, 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, []( bool bNew, map_pair& v ) {
 163                         EXPECT_TRUE( bNew );
 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, []( bool bNew, map_pair& v ) {
 170                         EXPECT_FALSE( bNew );
 171                         EXPECT_EQ( v.first.nKey, v.second.nVal );
 172                         v.second.strVal = std::to_string( v.second.nVal );
 173                     } );
 174                     EXPECT_TRUE( updResult.first );
 175                     EXPECT_FALSE( updResult.second );
 176                     break;
 177                 case 10:
 178                     updResult = m.update( i, []( bool, map_pair& ) {
 179                         EXPECT_TRUE( false );
 180                     }, false );
 181                     EXPECT_FALSE( updResult.first );
 182                     EXPECT_FALSE( updResult.second );
 183
 184                     updResult = m.update( i, []( bool bNew, map_pair& v ) {
 185                         EXPECT_TRUE( bNew );
 186                         v.second.nVal = v.first.nKey;
 187                     });
 188                     EXPECT_TRUE( updResult.first );
 189                     EXPECT_TRUE( updResult.second );
 190
 191                     updResult = m.update( i, []( bool bNew, map_pair& v ) {
 192                         EXPECT_FALSE( bNew );
 193                         EXPECT_EQ( v.first.nKey, v.second.nVal );
 194                         v.second.strVal = std::to_string( v.second.nVal );
 195                     } );
 196                     EXPECT_TRUE( updResult.first );
 197                     EXPECT_FALSE( updResult.second );
 198                     break;
 199                 case 11:
 200                     updResult = m.update( val.strVal, []( bool, map_pair& ) {
 201                         EXPECT_TRUE( false );
 202                     }, false );
 203                     EXPECT_FALSE( updResult.first );
 204                     EXPECT_FALSE( updResult.second );
 205
 206                     updResult = m.update( val.strVal, []( bool bNew, map_pair& v ) {
 207                         EXPECT_TRUE( bNew );
 208                         v.second.nVal = v.first.nKey;
 209                     });
 210                     EXPECT_TRUE( updResult.first );
 211                     EXPECT_TRUE( updResult.second );
 212
 213                     updResult = m.update( val.strVal, []( bool bNew, map_pair& v ) {
 214                         EXPECT_FALSE( bNew );
 215                         EXPECT_EQ( v.first.nKey, v.second.nVal );
 216                         v.second.strVal = std::to_string( v.second.nVal );
 217                     } );
 218                     EXPECT_TRUE( updResult.first );
 219                     EXPECT_FALSE( updResult.second );
 220                     break;
 221                 case 12:
 222                     EXPECT_TRUE( m.emplace( i.nKey ));
 223                     EXPECT_FALSE( m.emplace( i.nKey ));
 224                     EXPECT_TRUE( m.find( i.nKey, []( map_pair& v ) {
 225                         v.second.nVal = v.first.nKey;
 226                         v.second.strVal = std::to_string( v.first.nKey );
 227                     } ));
 228                     break;
 229                 case 13:
 230                     EXPECT_TRUE( m.emplace( i, i.nKey ));
 231                     EXPECT_FALSE( m.emplace( i, i.nKey ));
 232                     break;
 233                 case 14:
 234                     {
 235                         std::string str = val.strVal;
 236                         EXPECT_TRUE( m.emplace( i, std::move( str )));
 237                         EXPECT_TRUE( str.empty());
 238                         str = val.strVal;
 239                         EXPECT_FALSE( m.emplace( i, std::move( str )));
 240                         EXPECT_TRUE( str.empty());
 241                     }
 242                     break;
 243                 case 15:
 244                     {
 245                         std::string str = val.strVal;
 246                         EXPECT_TRUE( m.emplace( i, i.nKey, std::move( str )));
 247                         EXPECT_TRUE( str.empty());
 248                         str = val.strVal;
 249                         EXPECT_FALSE( m.emplace( i, i.nKey, std::move( str )));
 250                         EXPECT_TRUE( str.empty());
 251                     }
 252                     break;
 253                 }
 254
 255                 EXPECT_TRUE( m.contains( i.nKey ));
 256                 EXPECT_TRUE( m.contains( i ));
 257                 EXPECT_TRUE( m.contains( other_item( i.nKey ), other_less()));
 258                 EXPECT_TRUE( m.find( i, []( map_pair const& v ) {
 259                     EXPECT_EQ( v.first.nKey, v.second.nVal );
 260                     EXPECT_EQ( std::to_string( v.first.nKey ), v.second.strVal );
 261                 } ));
 262                 EXPECT_TRUE( m.find( i.nKey, []( map_pair const& v ) {
 263                     EXPECT_EQ( v.first.nKey, v.second.nVal );
 264                     EXPECT_EQ( std::to_string( v.first.nKey ), v.second.strVal );
 265                 } ));
 266                 EXPECT_TRUE( m.find_with( other_item( i.nKey ), other_less(), []( 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             }
 271             EXPECT_FALSE( m.empty() );
 272             EXPECT_CONTAINER_SIZE( m, kkSize );
 273             EXPECT_FALSE( m.begin() == m.end() );
 274             EXPECT_FALSE( m.cbegin() == m.cend() );
 275
 276             shuffle( arrKeys.begin(), arrKeys.end() );
 277
 278             // erase/find
 279             for ( auto const& i : arrKeys ) {
 280                 value_type const& val( arrVals.at( i.nKey ) );
 281
 282                 EXPECT_TRUE( m.contains( i.nKey ));
 283                 EXPECT_TRUE( m.contains( val.strVal ) );
 284                 EXPECT_TRUE( m.contains( i ));
 285                 EXPECT_TRUE( m.contains( other_item( i.nKey ), other_less()));
 286                 EXPECT_TRUE( m.find( i, []( 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                 EXPECT_TRUE( m.find( i.nKey, []( map_pair const& v ) {
 291                     EXPECT_EQ( v.first.nKey, v.second.nVal );
 292                     EXPECT_EQ( std::to_string( v.first.nKey ), v.second.strVal );
 293                 } ));
 294                 EXPECT_TRUE( m.find_with( other_item( i.nKey ), other_less(), []( map_pair const& v ) {
 295                     EXPECT_EQ( v.first.nKey, v.second.nVal );
 296                     EXPECT_EQ( std::to_string( v.first.nKey ), v.second.strVal );
 297                 } ));
 298
 299
 300                 switch ( i.nKey % 8 ) {
 301                 case 0:
 302                     EXPECT_TRUE( m.erase( i ));
 303                     EXPECT_FALSE( m.erase( i ));
 304                     break;
 305                 case 1:
 306                     EXPECT_TRUE( m.erase( i.nKey ));
 307                     EXPECT_FALSE( m.erase( i.nKey ));
 308                     break;
 309                 case 2:
 310                     EXPECT_TRUE( m.erase( val.strVal ));
 311                     EXPECT_FALSE( m.erase( val.strVal ));
 312                     break;
 313                 case 3:
 314                     EXPECT_TRUE( m.erase_with( other_item( i.nKey ), other_less()));
 315                     EXPECT_FALSE( m.erase_with( other_item( i.nKey ), other_less()));
 316                     break;
 317                 case 4:
 318                     EXPECT_TRUE( m.erase( i, []( map_pair& v ) {
 319                         EXPECT_EQ( v.first.nKey, v.second.nVal );
 320                         EXPECT_EQ( std::to_string( v.first.nKey ), v.second.strVal );
 321                     }));
 322                     EXPECT_FALSE( m.erase( i, []( map_pair& ) {
 323                         EXPECT_TRUE( false );
 324                     }));
 325                     break;
 326                 case 5:
 327                     EXPECT_TRUE( m.erase( i.nKey, []( map_pair& v ) {
 328                         EXPECT_EQ( v.first.nKey, v.second.nVal );
 329                         EXPECT_EQ( std::to_string( v.first.nKey ), v.second.strVal );
 330                     }));
 331                     EXPECT_FALSE( m.erase( i.nKey, []( map_pair& ) {
 332                         EXPECT_TRUE( false );
 333                     }));
 334                     break;
 335                 case 6:
 336                     EXPECT_TRUE( m.erase( val.strVal, []( map_pair& v ) {
 337                         EXPECT_EQ( v.first.nKey, v.second.nVal );
 338                         EXPECT_EQ( std::to_string( v.first.nKey ), v.second.strVal );
 339                     }));
 340                     EXPECT_FALSE( m.erase( val.strVal, []( map_pair& ) {
 341                         EXPECT_TRUE( false );
 342                     }));
 343                     break;
 344                 case 7:
 345                     EXPECT_TRUE( m.erase_with( other_item( i.nKey ), other_less(), []( map_pair& v ) {
 346                         EXPECT_EQ( v.first.nKey, v.second.nVal );
 347                         EXPECT_EQ( std::to_string( v.first.nKey ), v.second.strVal );
 348                     }));
 349                     EXPECT_FALSE( m.erase_with( other_item( i.nKey ), other_less(), []( map_pair& ) {
 350                         EXPECT_TRUE( false );
 351                     }));
 352                     break;
 353                 }
 354
 355                 EXPECT_FALSE( m.contains( i.nKey ));
 356                 EXPECT_FALSE( m.contains( i ));
 357                 EXPECT_FALSE( m.contains( val.strVal ));
 358                 EXPECT_FALSE( m.contains( other_item( i.nKey ), other_less()));
 359                 EXPECT_FALSE( m.find( i, []( map_pair const& ) {
 360                     EXPECT_TRUE( false );
 361                 } ));
 362                 EXPECT_FALSE( m.find( i.nKey, []( map_pair const& ) {
 363                     EXPECT_TRUE( false );
 364                 } ));
 365                 EXPECT_FALSE( m.find_with( other_item( i.nKey ), other_less(), []( map_pair const& ) {
 366                     EXPECT_TRUE( false );
 367                 } ));
 368             }
 369             EXPECT_TRUE( m.empty() );
 370             EXPECT_CONTAINER_SIZE( m, 0 );
 371
 372             EXPECT_TRUE( m.begin() == m.end());
 373             EXPECT_TRUE( m.cbegin() == m.cend());
 374
 375             // clear
 376             for ( auto const& i : arrKeys )
 377                 EXPECT_TRUE( m.insert( i ));
 378
 379             EXPECT_FALSE( m.empty() );
 380             EXPECT_CONTAINER_SIZE( m, kkSize );
 381
 382             m.clear();
 383
 384             EXPECT_TRUE( m.empty() );
 385             EXPECT_CONTAINER_SIZE( m, 0 );
 386         }
 387     };
 388
 389 } // namespace cds_test
 390
 391 #endif // #ifndef CDSUNIT_MAP_TEST_MAP_H