test/unit/set/test_feldman_hashset.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_SET_TEST_FELDMAN_HASHSET_H
  32 #define CDSUNIT_SET_TEST_FELDMAN_HASHSET_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 namespace co = cds::opt;
  42 namespace cc = cds::container;
  43
  44 namespace cds_test {
  45
  46     class feldman_hashset : public fixture
  47     {
  48     public:
  49         static size_t const kSize = 1000;
  50
  51         struct stat
  52         {
  53             unsigned int nFindCount;
  54             unsigned int nUpdateNewCount;
  55             unsigned int nUpdateCount;
  56
  57             stat()
  58             {
  59                 clear_stat();
  60             }
  61
  62             void clear_stat()
  63             {
  64                 memset( this, 0, sizeof( *this ));
  65             }
  66         };
  67
  68         struct other_item {
  69             int nKey;
  70
  71             explicit other_item( int k )
  72                 : nKey( k )
  73             {}
  74
  75             int key() const
  76             {
  77                 return nKey;
  78             }
  79         };
  80
  81         struct int_item: public stat
  82         {
  83             int nKey;
  84             int nVal;
  85             std::string strVal;
  86
  87             int_item()
  88                 : nKey( 0 )
  89                 , nVal( 0 )
  90             {}
  91
  92             explicit int_item( int k )
  93                 : nKey( k )
  94                 , nVal( k * 2 )
  95             {}
  96
  97             template <typename Q>
  98             explicit int_item( Q const& src )
  99                 : nKey( src.key())
 100                 , nVal( 0 )
 101             {}
 102
 103             int_item( int_item const& src )
 104                 : nKey( src.nKey )
 105                 , nVal( src.nVal )
 106                 , strVal( src.strVal )
 107             {}
 108
 109             int_item( int_item&& src )
 110                 : nKey( src.nKey )
 111                 , nVal( src.nVal )
 112                 , strVal( std::move( src.strVal ))
 113             {}
 114
 115             int_item( int k, std::string&& s )
 116                 : nKey( k )
 117                 , nVal( k * 2 )
 118                 , strVal( std::move( s ))
 119             {}
 120
 121             explicit int_item( other_item const& s )
 122                 : nKey( s.key())
 123                 , nVal( s.key() * 2 )
 124             {}
 125
 126             int key() const
 127             {
 128                 return nKey;
 129             }
 130         };
 131
 132         struct key_val {
 133             int nKey;
 134             int nVal;
 135
 136             key_val()
 137             {}
 138
 139             key_val( int key )
 140                 : nKey( key )
 141                 , nVal( key )
 142             {}
 143
 144             key_val( int key, int val )
 145                 : nKey( key )
 146                 , nVal( val )
 147             {}
 148
 149             key_val( key_val const& v )
 150                 : nKey( v.nKey )
 151                 , nVal( v.nVal )
 152             {}
 153
 154             int key() const
 155             {
 156                 return nKey;
 157             }
 158         };
 159
 160         struct int_item2: public key_val, public stat
 161         {
 162             std::string strVal;
 163
 164             int_item2()
 165             {}
 166
 167             explicit int_item2( int key )
 168                 : key_val( key )
 169             {}
 170
 171             int_item2( int key, int val )
 172                 : key_val( key, val )
 173             {}
 174
 175             int_item2( int_item2 const& v )
 176                 : key_val( v )
 177                 , stat()
 178                 , strVal( v.strVal )
 179             {}
 180
 181             int_item2( int_item2&& v )
 182                 : key_val( v )
 183                 , stat()
 184                 , strVal( std::move( v.strVal ))
 185             {}
 186
 187             int_item2( int k, std::string&& s )
 188                 : key_val( k, k * 2 )
 189                 , strVal( std::move( s ) )
 190             {}
 191
 192             explicit int_item2( other_item const& s )
 193                 : key_val( s.key(), s.key() * 2 )
 194             {}
 195         };
 196
 197
 198         struct get_hash {
 199             int operator()( int_item const& i ) const
 200             {
 201                 return i.key();
 202             }
 203
 204             int operator()( other_item const& i ) const
 205             {
 206                 return i.key();
 207             }
 208
 209             int operator()( int i ) const
 210             {
 211                 return i;
 212             }
 213         };
 214
 215         struct get_hash2 {
 216             key_val const& operator()( int_item2 const& i ) const
 217             {
 218                 return i;
 219             }
 220
 221             key_val operator()( other_item const& i ) const
 222             {
 223                 return key_val( i.key() );
 224             }
 225
 226             key_val operator()( int i ) const
 227             {
 228                 return key_val( i );
 229             }
 230         };
 231
 232         struct simple_item_counter {
 233             size_t  m_nCount;
 234
 235             simple_item_counter()
 236                 : m_nCount( 0 )
 237             {}
 238
 239             size_t operator ++()
 240             {
 241                 return ++m_nCount;
 242             }
 243
 244             size_t operator --()
 245             {
 246                 return --m_nCount;
 247             }
 248
 249             void reset()
 250             {
 251                 m_nCount = 0;
 252             }
 253
 254             operator size_t() const
 255             {
 256                 return m_nCount;
 257             }
 258
 259         };
 260
 261         struct cmp {
 262             int operator ()( int v1, int v2 ) const
 263             {
 264                 if ( v1 < v2 )
 265                     return -1;
 266                 return v1 > v2 ? 1 : 0;
 267             }
 268         };
 269
 270         struct cmp2 {
 271             int operator ()( key_val const& v1, key_val const& v2 ) const
 272             {
 273                 if ( v1.key() < v2.key() )
 274                     return -1;
 275                 return v1.key() > v2.key() ? 1 : 0;
 276             }
 277         };
 278
 279         struct other_less {
 280             template <typename Q, typename T>
 281             bool operator()( Q const& lhs, T const& rhs ) const
 282             {
 283                 return lhs.key() < rhs.key();
 284             }
 285         };
 286
 287     protected:
 288         template <typename Set>
 289         void test( Set& s )
 290         {
 291             // Precondition: set is empty
 292             // Postcondition: set is empty
 293
 294             ASSERT_TRUE( s.empty());
 295             ASSERT_CONTAINER_SIZE( s, 0 );
 296             size_t const nSetSize = kSize;
 297
 298             typedef typename Set::value_type value_type;
 299
 300             std::vector< value_type > data;
 301             std::vector< size_t> indices;
 302             data.reserve( kSize );
 303             indices.reserve( kSize );
 304             for ( size_t key = 0; key < kSize; ++key ) {
 305                 data.push_back( value_type( static_cast<int>(key)));
 306                 indices.push_back( key );
 307             }
 308             shuffle( indices.begin(), indices.end());
 309
 310             // insert/find
 311             for ( auto idx : indices ) {
 312                 auto& i = data[idx];
 313
 314                 ASSERT_FALSE( s.contains( i.nKey ));
 315                 ASSERT_FALSE( s.find( i.nKey, []( value_type& ) {} ));
 316
 317                 std::pair<bool, bool> updResult;
 318
 319                 std::string str;
 320                 updResult = s.update( i.key(), []( value_type&, value_type * )
 321                 {
 322                     ASSERT_TRUE( false );
 323                 }, false );
 324                 EXPECT_FALSE( updResult.first );
 325                 EXPECT_FALSE( updResult.second );
 326
 327                 switch ( idx % 8 ) {
 328                 case 0:
 329                     ASSERT_TRUE( s.insert( i ));
 330                     ASSERT_FALSE( s.insert( i ));
 331                     updResult = s.update( i, []( value_type& val, value_type * prev )
 332                         {
 333                             ASSERT_TRUE( prev != nullptr );
 334                             EXPECT_EQ( val.key(), prev->key());
 335                         }, false );
 336                     EXPECT_TRUE( updResult.first );
 337                     EXPECT_FALSE( updResult.second );
 338                     break;
 339                 case 1:
 340                     ASSERT_TRUE( s.insert( i.key()));
 341                     ASSERT_FALSE( s.insert( i.key()));
 342                     updResult = s.update( i.key(), []( value_type& val, value_type * prev )
 343                         {
 344                             ASSERT_TRUE( prev != nullptr );
 345                             EXPECT_EQ( val.key(), prev->key());
 346                         }, false );
 347                     EXPECT_TRUE( updResult.first );
 348                     EXPECT_FALSE( updResult.second );
 349                     break;
 350                 case 2:
 351                     ASSERT_TRUE( s.insert( i, []( value_type& v ) { ++v.nFindCount; } ));
 352                     ASSERT_FALSE( s.insert( i, []( value_type& v ) { ++v.nFindCount; } ));
 353                     ASSERT_TRUE( s.find( i.nKey, []( value_type const& v )
 354                         {
 355                             EXPECT_EQ( v.nFindCount, 1u );
 356                         }));
 357                     break;
 358                 case 3:
 359                     ASSERT_TRUE( s.insert( i.key(), []( value_type& v ) { ++v.nFindCount; } ));
 360                     ASSERT_FALSE( s.insert( i.key(), []( value_type& v ) { ++v.nFindCount; } ));
 361                     ASSERT_TRUE( s.find( i.nKey, []( value_type const& v )
 362                         {
 363                             EXPECT_EQ( v.nFindCount, 1u );
 364                         }));
 365                     break;
 366                 case 4:
 367                     updResult = s.update( i, []( value_type& v, value_type * prev )
 368                         {
 369                             EXPECT_TRUE( prev == nullptr );
 370                             ++v.nUpdateNewCount;
 371                         });
 372                     EXPECT_TRUE( updResult.first );
 373                     EXPECT_TRUE( updResult.second );
 374
 375                     updResult = s.update( i, []( value_type& v, value_type * prev )
 376                         {
 377                             ASSERT_TRUE( prev != nullptr );
 378                             EXPECT_EQ( prev->nUpdateNewCount, 1u );
 379                             EXPECT_EQ( v.key(), prev->key());
 380                             ++v.nUpdateCount;
 381                         }, false );
 382                     EXPECT_TRUE( updResult.first );
 383                     EXPECT_FALSE( updResult.second );
 384
 385                     ASSERT_TRUE( s.find( i.nKey, []( value_type const& v )
 386                         {
 387                             EXPECT_EQ( v.nUpdateCount, 1u );
 388                             EXPECT_EQ( v.nUpdateNewCount, 0u );
 389                         }));
 390                     break;
 391                 case 5:
 392                     updResult = s.update( i.key(), []( value_type& v, value_type * prev )
 393                         {
 394                             EXPECT_TRUE( prev == nullptr );
 395                             ++v.nUpdateNewCount;
 396                         });
 397                         EXPECT_TRUE( updResult.first );
 398                         EXPECT_TRUE( updResult.second );
 399
 400                         updResult = s.update( i.key(), []( value_type& v, value_type * prev )
 401                         {
 402                             ASSERT_TRUE( prev != nullptr );
 403                             EXPECT_EQ( v.key(), prev->key());
 404                             EXPECT_EQ( prev->nUpdateNewCount, 1u );
 405                             EXPECT_EQ( v.nUpdateNewCount, 0u );
 406                             ++v.nUpdateNewCount;
 407                         }, false );
 408                         EXPECT_TRUE( updResult.first );
 409                         EXPECT_FALSE( updResult.second );
 410
 411                         ASSERT_TRUE( s.find( i.key(), []( value_type const& v )
 412                         {
 413                             EXPECT_EQ( v.nUpdateNewCount, 1u );
 414                         } ));
 415                         break;
 416                 case 6:
 417                     ASSERT_TRUE( s.emplace( i.key()));
 418                     ASSERT_TRUE( s.contains( i.key()));
 419                     break;
 420                 case 7:
 421                     str = "Hello!";
 422                     ASSERT_TRUE( s.emplace( i.key(), std::move( str )));
 423                     EXPECT_TRUE( str.empty());
 424                     ASSERT_TRUE( s.find( i.key(), []( value_type const& v )
 425                     {
 426                         EXPECT_EQ( v.strVal, std::string( "Hello!" ));
 427                     } ));
 428                     break;
 429                 default:
 430                     // forgot anything?..
 431                     ASSERT_TRUE( false );
 432                 }
 433
 434                 ASSERT_TRUE( s.contains( i.nKey ));
 435                 ASSERT_TRUE( s.find( i.nKey, []( value_type& ) {} ));
 436             }
 437
 438             ASSERT_FALSE( s.empty());
 439             ASSERT_CONTAINER_SIZE( s, nSetSize );
 440
 441             // erase
 442             shuffle( indices.begin(), indices.end());
 443             for ( auto idx : indices ) {
 444                 auto& i = data[idx];
 445
 446                 ASSERT_TRUE( s.contains( i.nKey ));
 447                 ASSERT_TRUE( s.find( i.nKey, []( value_type& v )
 448                 {
 449                     v.nFindCount = 1;
 450                 } ));
 451
 452                 int nKey = i.key() - 1;
 453                 switch ( idx % 2 ) {
 454                 case 0:
 455                     ASSERT_TRUE( s.erase( i.key()));
 456                     ASSERT_FALSE( s.erase( i.key()));
 457                     break;
 458                 case 1:
 459                     ASSERT_TRUE( s.erase( i.key(), [&nKey]( value_type const& v )
 460                     {
 461                         EXPECT_EQ( v.nFindCount, 1u );
 462                         nKey = v.key();
 463                     } ));
 464                     EXPECT_EQ( i.key(), nKey );
 465
 466                     nKey = i.key() - 1;
 467                     ASSERT_FALSE( s.erase( i.key(), [&nKey]( value_type const& v )
 468                     {
 469                         nKey = v.key();
 470                     } ));
 471                     EXPECT_EQ( i.key(), nKey + 1 );
 472                     break;
 473                 }
 474
 475                 ASSERT_FALSE( s.contains( i.nKey ));
 476                 ASSERT_FALSE( s.find( i.nKey, []( value_type const& ) {} ));
 477             }
 478             ASSERT_TRUE( s.empty());
 479             ASSERT_CONTAINER_SIZE( s, 0u );
 480
 481
 482             // clear
 483             for ( auto& i : data ) {
 484                 ASSERT_TRUE( s.insert( i ));
 485             }
 486
 487             {
 488                 typename Set::stat const& statistics = s.statistics();
 489                 CDS_UNUSED( statistics );
 490
 491                 std::vector< typename Set::level_statistics > lstat;
 492                 s.get_level_statistics( lstat );
 493                 EXPECT_EQ( lstat[0].node_capacity, s.head_size());
 494                 for ( size_t i = 1; i < lstat.size(); ++i ) {
 495                     EXPECT_EQ( lstat[i].node_capacity, s.array_node_size());
 496                 }
 497             }
 498
 499             ASSERT_FALSE( s.empty());
 500             ASSERT_CONTAINER_SIZE( s, nSetSize );
 501
 502             s.clear();
 503
 504             ASSERT_TRUE( s.empty());
 505             ASSERT_CONTAINER_SIZE( s, 0u );
 506
 507             ASSERT_TRUE( s.begin() == s.end());
 508             ASSERT_TRUE( s.cbegin() == s.cend());
 509             ASSERT_TRUE( s.rbegin() == s.rend());
 510             ASSERT_TRUE( s.crbegin() == s.crend());
 511         }
 512     };
 513
 514 } // namespace cds_test
 515
 516 #endif // CDSUNIT_SET_TEST_FELDMAN_HASHSET_H