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