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