gdax-orderbook-hpp/demo/dependencies/libcds-2.3.2/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-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_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                 EXPECT_TRUE( m.find( i ) == m.end());
  90                 EXPECT_TRUE( m.find( i.nKey ) == m.end());
  91                 EXPECT_TRUE( m.find_with( other_item( i.nKey ), other_less()) == m.end());
  92
  93                 std::pair< bool, bool > updResult;
  94
  95                 switch ( i.nKey % 17 ) {
  96                 case 0:
  97                     EXPECT_TRUE( m.insert( i ));
  98                     EXPECT_FALSE( m.insert( i ));
  99                     EXPECT_TRUE( m.find( i.nKey, []( map_pair& v ) {
 100                         v.second.nVal = v.first.nKey;
 101                         v.second.strVal = std::to_string( v.first.nKey );
 102                     } ));
 103                     break;
 104                 case 1:
 105                     EXPECT_TRUE( m.insert( i.nKey ));
 106                     EXPECT_FALSE( m.insert( i.nKey ));
 107                     EXPECT_TRUE( m.find( i.nKey, []( map_pair& v ) {
 108                         v.second.nVal = v.first.nKey;
 109                         v.second.strVal = std::to_string( v.first.nKey );
 110                     } ));
 111                     break;
 112                 case 2:
 113                     EXPECT_TRUE( m.insert( std::to_string( i.nKey )));
 114                     EXPECT_FALSE( m.insert( std::to_string( i.nKey )));
 115                     EXPECT_TRUE( m.find( i.nKey, []( map_pair& v ) {
 116                         v.second.nVal = v.first.nKey;
 117                         v.second.strVal = std::to_string( v.first.nKey );
 118                     } ));
 119                     break;
 120                 case 3:
 121                     EXPECT_TRUE( m.insert( i, val ));
 122                     EXPECT_FALSE( m.insert( i, val ));
 123                     break;
 124                 case 4:
 125                     EXPECT_TRUE( m.insert( i.nKey, val.strVal ));
 126                     EXPECT_FALSE( m.insert( i.nKey, val.strVal ));
 127                     break;
 128                 case 5:
 129                     EXPECT_TRUE( m.insert( val.strVal, i.nKey ));
 130                     EXPECT_FALSE( m.insert( val.strVal, i.nKey ));
 131                     break;
 132                 case 6:
 133                     EXPECT_TRUE( m.insert_with( i, []( map_pair& v ) {
 134                         v.second.nVal = v.first.nKey;
 135                         v.second.strVal = std::to_string( v.first.nKey );
 136                     } ));
 137                     EXPECT_FALSE( m.insert_with( i, []( map_pair& ) {
 138                         EXPECT_TRUE( false );
 139                     } ));
 140                     break;
 141                 case 7:
 142                     EXPECT_TRUE( m.insert_with( i.nKey, []( map_pair& v ) {
 143                         v.second.nVal = v.first.nKey;
 144                         v.second.strVal = std::to_string( v.first.nKey );
 145                     } ));
 146                     EXPECT_FALSE( m.insert_with( i.nKey, []( map_pair& ) {
 147                         EXPECT_TRUE( false );
 148                     } ));
 149                     break;
 150                 case 8:
 151                     EXPECT_TRUE( m.insert_with( val.strVal, []( map_pair& v ) {
 152                         v.second.nVal = v.first.nKey;
 153                         v.second.strVal = std::to_string( v.first.nKey );
 154                     } ));
 155                     EXPECT_FALSE( m.insert_with( val.strVal, []( map_pair& ) {
 156                         EXPECT_TRUE( false );
 157                     } ));
 158                     break;
 159                 case 9:
 160                     updResult = m.update( i.nKey, []( map_pair&, map_pair* ) {
 161                         EXPECT_TRUE( false );
 162                     }, false );
 163                     EXPECT_FALSE( updResult.first );
 164                     EXPECT_FALSE( updResult.second );
 165
 166                     updResult = m.update( i.nKey, []( map_pair& v, map_pair* old ) {
 167                         EXPECT_TRUE( old == nullptr );
 168                         v.second.nVal = v.first.nKey;
 169                     });
 170                     EXPECT_TRUE( updResult.first );
 171                     EXPECT_TRUE( updResult.second );
 172
 173                     updResult = m.update( i.nKey, []( map_pair& v, map_pair* old ) {
 174                         ASSERT_FALSE( old == nullptr );
 175                         EXPECT_EQ( v.first.nKey, old->second.nVal );
 176                         v.second.nVal = old->second.nVal;
 177                         v.second.strVal = std::to_string( old->second.nVal );
 178                     } );
 179                     EXPECT_TRUE( updResult.first );
 180                     EXPECT_FALSE( updResult.second );
 181                     break;
 182                 case 10:
 183                     updResult = m.update( i, []( map_pair&, map_pair* ) {
 184                         EXPECT_TRUE( false );
 185                     }, false );
 186                     EXPECT_FALSE( updResult.first );
 187                     EXPECT_FALSE( updResult.second );
 188
 189                     updResult = m.update( i, []( map_pair& v, map_pair* old ) {
 190                         EXPECT_TRUE( old == nullptr );
 191                         v.second.nVal = v.first.nKey;
 192                     });
 193                     EXPECT_TRUE( updResult.first );
 194                     EXPECT_TRUE( updResult.second );
 195
 196                     updResult = m.update( i, []( map_pair& v, map_pair* old ) {
 197                         ASSERT_FALSE( old == nullptr );
 198                         EXPECT_EQ( v.first.nKey, old->second.nVal );
 199                         v.second.nVal = old->second.nVal;
 200                         v.second.strVal = std::to_string( v.second.nVal );
 201                     } );
 202                     EXPECT_TRUE( updResult.first );
 203                     EXPECT_FALSE( updResult.second );
 204                     break;
 205                 case 11:
 206                     updResult = m.update( val.strVal, []( map_pair&, map_pair* ) {
 207                         EXPECT_TRUE( false );
 208                     }, false );
 209                     EXPECT_FALSE( updResult.first );
 210                     EXPECT_FALSE( updResult.second );
 211
 212                     updResult = m.update( val.strVal, []( map_pair& v, map_pair* old ) {
 213                         EXPECT_TRUE( old == nullptr );
 214                         v.second.nVal = v.first.nKey;
 215                     });
 216                     EXPECT_TRUE( updResult.first );
 217                     EXPECT_TRUE( updResult.second );
 218
 219                     updResult = m.update( val.strVal, []( map_pair& v, map_pair* old ) {
 220                         ASSERT_FALSE( old == nullptr );
 221                         EXPECT_EQ( v.first.nKey, old->second.nVal );
 222                         v.second.nVal = old->second.nVal;
 223                         v.second.strVal = std::to_string( v.second.nVal );
 224                     } );
 225                     EXPECT_TRUE( updResult.first );
 226                     EXPECT_FALSE( updResult.second );
 227                     break;
 228                 case 12:
 229                     EXPECT_TRUE( m.emplace( i.nKey ));
 230                     EXPECT_FALSE( m.emplace( i.nKey ));
 231                     EXPECT_TRUE( m.find( i.nKey, []( map_pair& v ) {
 232                         v.second.nVal = v.first.nKey;
 233                         v.second.strVal = std::to_string( v.first.nKey );
 234                     } ));
 235                     break;
 236                 case 13:
 237                     EXPECT_TRUE( m.emplace( i, i.nKey ));
 238                     EXPECT_FALSE( m.emplace( i, i.nKey ));
 239                     break;
 240                 case 14:
 241                     {
 242                         std::string str = val.strVal;
 243                         EXPECT_TRUE( m.emplace( i, std::move( str )));
 244                         EXPECT_TRUE( str.empty());
 245                         str = val.strVal;
 246                         EXPECT_FALSE( m.emplace( i, std::move( str )));
 247                         EXPECT_TRUE( str.empty());
 248                     }
 249                     break;
 250                 case 15:
 251                     {
 252                         std::string str = val.strVal;
 253                         EXPECT_TRUE( m.emplace( i, i.nKey, std::move( str )));
 254                         EXPECT_TRUE( str.empty());
 255                         str = val.strVal;
 256                         EXPECT_FALSE( m.emplace( i, i.nKey, std::move( str )));
 257                         EXPECT_TRUE( str.empty());
 258                     }
 259                     break;
 260                 case 16:
 261                     {
 262                         auto res = m.upsert( i, i.nKey, false );
 263                         EXPECT_FALSE( res.first );
 264                         EXPECT_FALSE( res.second );
 265
 266                         res = m.upsert( i, i.nKey );
 267                         EXPECT_TRUE( res.first );
 268                         EXPECT_TRUE( res.second );
 269
 270                         std::string str = val.strVal;
 271                         res = m.upsert( i, std::move( str ));
 272                         EXPECT_TRUE( res.first );
 273                         EXPECT_FALSE( res.second );
 274                         EXPECT_TRUE( str.empty());
 275                     }
 276                     break;
 277                 }
 278
 279                 EXPECT_TRUE( m.contains( i.nKey ));
 280                 EXPECT_TRUE( m.contains( i ));
 281                 EXPECT_TRUE( m.contains( other_item( i.nKey ), other_less()));
 282                 EXPECT_TRUE( m.find( i, []( 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( i.nKey, []( 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_with( other_item( i.nKey ), other_less(), []( 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
 295                 ASSERT_TRUE( m.find( i ) != m.end());
 296                 ASSERT_TRUE( m.find( i.nKey ) != m.end());
 297                 ASSERT_TRUE( m.find_with( other_item( i.nKey ), other_less()) != m.end());
 298
 299                 EXPECT_EQ( m.find( i )->first.nKey, i.nKey );
 300                 EXPECT_EQ( m.find( i.nKey )->first.nKey, i.nKey );
 301                 EXPECT_EQ( m.find_with( other_item( i.nKey ), other_less())->first.nKey, i.nKey );
 302
 303             }
 304             EXPECT_FALSE( m.empty());
 305             EXPECT_CONTAINER_SIZE( m, kkSize );
 306             EXPECT_FALSE( m.begin() == m.end());
 307             EXPECT_FALSE( m.cbegin() == m.cend());
 308
 309             shuffle( arrKeys.begin(), arrKeys.end());
 310
 311             // erase/find
 312             for ( auto const& i : arrKeys ) {
 313                 value_type const& val( arrVals.at( i.nKey ));
 314
 315                 EXPECT_TRUE( m.contains( i.nKey ));
 316                 EXPECT_TRUE( m.contains( val.strVal ));
 317                 EXPECT_TRUE( m.contains( i ));
 318                 EXPECT_TRUE( m.contains( other_item( i.nKey ), other_less()));
 319                 EXPECT_TRUE( m.find( i, []( map_pair const& v ) {
 320                     EXPECT_EQ( v.first.nKey, v.second.nVal );
 321                     EXPECT_EQ( std::to_string( v.first.nKey ), v.second.strVal );
 322                 } ));
 323                 EXPECT_TRUE( m.find( i.nKey, []( map_pair const& v ) {
 324                     EXPECT_EQ( v.first.nKey, v.second.nVal );
 325                     EXPECT_EQ( std::to_string( v.first.nKey ), v.second.strVal );
 326                 } ));
 327                 EXPECT_TRUE( m.find_with( other_item( i.nKey ), other_less(), []( map_pair const& v ) {
 328                     EXPECT_EQ( v.first.nKey, v.second.nVal );
 329                     EXPECT_EQ( std::to_string( v.first.nKey ), v.second.strVal );
 330                 } ));
 331
 332
 333                 switch ( i.nKey % 8 ) {
 334                 case 0:
 335                     EXPECT_TRUE( m.erase( i ));
 336                     EXPECT_FALSE( m.erase( i ));
 337                     break;
 338                 case 1:
 339                     EXPECT_TRUE( m.erase( i.nKey ));
 340                     EXPECT_FALSE( m.erase( i.nKey ));
 341                     break;
 342                 case 2:
 343                     EXPECT_TRUE( m.erase( val.strVal ));
 344                     EXPECT_FALSE( m.erase( val.strVal ));
 345                     break;
 346                 case 3:
 347                     EXPECT_TRUE( m.erase_with( other_item( i.nKey ), other_less()));
 348                     EXPECT_FALSE( m.erase_with( other_item( i.nKey ), other_less()));
 349                     break;
 350                 case 4:
 351                     EXPECT_TRUE( m.erase( i, []( 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                     EXPECT_FALSE( m.erase( i, []( map_pair& ) {
 356                         EXPECT_TRUE( false );
 357                     }));
 358                     break;
 359                 case 5:
 360                     EXPECT_TRUE( m.erase( i.nKey, []( map_pair& v ) {
 361                         EXPECT_EQ( v.first.nKey, v.second.nVal );
 362                         EXPECT_EQ( std::to_string( v.first.nKey ), v.second.strVal );
 363                     }));
 364                     EXPECT_FALSE( m.erase( i.nKey, []( map_pair& ) {
 365                         EXPECT_TRUE( false );
 366                     }));
 367                     break;
 368                 case 6:
 369                     EXPECT_TRUE( m.erase( val.strVal, []( map_pair& v ) {
 370                         EXPECT_EQ( v.first.nKey, v.second.nVal );
 371                         EXPECT_EQ( std::to_string( v.first.nKey ), v.second.strVal );
 372                     }));
 373                     EXPECT_FALSE( m.erase( val.strVal, []( map_pair& ) {
 374                         EXPECT_TRUE( false );
 375                     }));
 376                     break;
 377                 case 7:
 378                     EXPECT_TRUE( m.erase_with( other_item( i.nKey ), other_less(), []( map_pair& v ) {
 379                         EXPECT_EQ( v.first.nKey, v.second.nVal );
 380                         EXPECT_EQ( std::to_string( v.first.nKey ), v.second.strVal );
 381                     }));
 382                     EXPECT_FALSE( m.erase_with( other_item( i.nKey ), other_less(), []( map_pair& ) {
 383                         EXPECT_TRUE( false );
 384                     }));
 385                     break;
 386                 }
 387
 388                 EXPECT_FALSE( m.contains( i.nKey ));
 389                 EXPECT_FALSE( m.contains( i ));
 390                 EXPECT_FALSE( m.contains( val.strVal ));
 391                 EXPECT_FALSE( m.contains( other_item( i.nKey ), other_less()));
 392                 EXPECT_FALSE( m.find( i, []( map_pair const& ) {
 393                     EXPECT_TRUE( false );
 394                 } ));
 395                 EXPECT_FALSE( m.find( i.nKey, []( map_pair const& ) {
 396                     EXPECT_TRUE( false );
 397                 } ));
 398                 EXPECT_FALSE( m.find_with( other_item( i.nKey ), other_less(), []( map_pair const& ) {
 399                     EXPECT_TRUE( false );
 400                 } ));
 401             }
 402             EXPECT_TRUE( m.empty());
 403             EXPECT_CONTAINER_SIZE( m, 0 );
 404
 405             EXPECT_TRUE( m.begin() == m.end());
 406             EXPECT_TRUE( m.cbegin() == m.cend());
 407
 408             // clear
 409             for ( auto const& i : arrKeys )
 410                 EXPECT_TRUE( m.insert( i ));
 411
 412             EXPECT_FALSE( m.empty());
 413             EXPECT_CONTAINER_SIZE( m, kkSize );
 414
 415             m.clear();
 416
 417             EXPECT_TRUE( m.empty());
 418             EXPECT_CONTAINER_SIZE( m, 0 );
 419         }
 420     };
 421
 422 } // namespace cds_test
 423
 424 #endif // #ifndef CDSUNIT_MAP_TEST_MICHAEL_ITERABLE_MAP_H