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