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 get_hash {
 133             int operator()( int_item const& i ) const
 134             {
 135                 return i.key();
 136             }
 137
 138             int operator()( other_item const& i ) const
 139             {
 140                 return i.key();
 141             }
 142
 143             int operator()( int i ) const
 144             {
 145                 return i;
 146             }
 147         };
 148
 149         struct simple_item_counter {
 150             size_t  m_nCount;
 151
 152             simple_item_counter()
 153                 : m_nCount( 0 )
 154             {}
 155
 156             size_t operator ++()
 157             {
 158                 return ++m_nCount;
 159             }
 160
 161             size_t operator --()
 162             {
 163                 return --m_nCount;
 164             }
 165
 166             void reset()
 167             {
 168                 m_nCount = 0;
 169             }
 170
 171             operator size_t() const
 172             {
 173                 return m_nCount;
 174             }
 175
 176         };
 177
 178         struct cmp {
 179             int operator ()( int v1, int v2 ) const
 180             {
 181                 if ( v1 < v2 )
 182                     return -1;
 183                 return v1 > v2 ? 1 : 0;
 184             }
 185         };
 186
 187         struct other_less {
 188             template <typename Q, typename T>
 189             bool operator()( Q const& lhs, T const& rhs ) const
 190             {
 191                 return lhs.key() < rhs.key();
 192             }
 193         };
 194
 195     protected:
 196         template <typename Set>
 197         void test( Set& s )
 198         {
 199             // Precondition: set is empty
 200             // Postcondition: set is empty
 201
 202             ASSERT_TRUE( s.empty() );
 203             ASSERT_CONTAINER_SIZE( s, 0 );
 204             size_t const nSetSize = kSize;
 205
 206             typedef typename Set::value_type value_type;
 207
 208             std::vector< value_type > data;
 209             std::vector< size_t> indices;
 210             data.reserve( kSize );
 211             indices.reserve( kSize );
 212             for ( size_t key = 0; key < kSize; ++key ) {
 213                 data.push_back( value_type( static_cast<int>(key) ) );
 214                 indices.push_back( key );
 215             }
 216             shuffle( indices.begin(), indices.end() );
 217
 218             // insert/find
 219             for ( auto idx : indices ) {
 220                 auto& i = data[idx];
 221
 222                 ASSERT_FALSE( s.contains( i.nKey ) );
 223                 ASSERT_FALSE( s.find( i.nKey, []( value_type& ) {} ));
 224
 225                 std::pair<bool, bool> updResult;
 226
 227                 std::string str;
 228                 updResult = s.update( i.key(), []( value_type&, value_type * )
 229                 {
 230                     ASSERT_TRUE( false );
 231                 }, false );
 232                 EXPECT_FALSE( updResult.first );
 233                 EXPECT_FALSE( updResult.second );
 234
 235                 switch ( idx % 8 ) {
 236                 case 0:
 237                     ASSERT_TRUE( s.insert( i ));
 238                     ASSERT_FALSE( s.insert( i ));
 239                     updResult = s.update( i, []( value_type& val, value_type * prev )
 240                         {
 241                             ASSERT_TRUE( prev != nullptr );
 242                             EXPECT_EQ( val.key(), prev->key() );
 243                         }, false );
 244                     EXPECT_TRUE( updResult.first );
 245                     EXPECT_FALSE( updResult.second );
 246                     break;
 247                 case 1:
 248                     ASSERT_TRUE( s.insert( i.key() ));
 249                     ASSERT_FALSE( s.insert( i.key() ));
 250                     updResult = s.update( i.key(), []( value_type& val, value_type * prev )
 251                         {
 252                             ASSERT_TRUE( prev != nullptr );
 253                             EXPECT_EQ( val.key(), prev->key() );
 254                         }, false );
 255                     EXPECT_TRUE( updResult.first );
 256                     EXPECT_FALSE( updResult.second );
 257                     break;
 258                 case 2:
 259                     ASSERT_TRUE( s.insert( i, []( value_type& v ) { ++v.nFindCount; } ));
 260                     ASSERT_FALSE( s.insert( i, []( value_type& v ) { ++v.nFindCount; } ));
 261                     ASSERT_TRUE( s.find( i.nKey, []( value_type const& v )
 262                         {
 263                             EXPECT_EQ( v.nFindCount, 1u );
 264                         }));
 265                     break;
 266                 case 3:
 267                     ASSERT_TRUE( s.insert( i.key(), []( value_type& v ) { ++v.nFindCount; } ));
 268                     ASSERT_FALSE( s.insert( i.key(), []( value_type& v ) { ++v.nFindCount; } ));
 269                     ASSERT_TRUE( s.find( i.nKey, []( value_type const& v )
 270                         {
 271                             EXPECT_EQ( v.nFindCount, 1u );
 272                         }));
 273                     break;
 274                 case 4:
 275                     updResult = s.update( i, []( value_type& v, value_type * prev )
 276                         {
 277                             EXPECT_TRUE( prev == nullptr );
 278                             ++v.nUpdateNewCount;
 279                         });
 280                     EXPECT_TRUE( updResult.first );
 281                     EXPECT_TRUE( updResult.second );
 282
 283                     updResult = s.update( i, []( value_type& v, value_type * prev )
 284                         {
 285                             ASSERT_TRUE( prev != nullptr );
 286                             EXPECT_EQ( prev->nUpdateNewCount, 1u );
 287                             EXPECT_EQ( v.key(), prev->key() );
 288                             ++v.nUpdateCount;
 289                         }, false );
 290                     EXPECT_TRUE( updResult.first );
 291                     EXPECT_FALSE( updResult.second );
 292
 293                     ASSERT_TRUE( s.find( i.nKey, []( value_type const& v )
 294                         {
 295                             EXPECT_EQ( v.nUpdateCount, 1u );
 296                             EXPECT_EQ( v.nUpdateNewCount, 0u );
 297                         }));
 298                     break;
 299                 case 5:
 300                     updResult = s.update( i.key(), []( value_type& v, value_type * prev )
 301                         {
 302                             EXPECT_TRUE( prev == nullptr );
 303                             ++v.nUpdateNewCount;
 304                         });
 305                         EXPECT_TRUE( updResult.first );
 306                         EXPECT_TRUE( updResult.second );
 307
 308                         updResult = s.update( i.key(), []( value_type& v, value_type * prev )
 309                         {
 310                             ASSERT_TRUE( prev != nullptr );
 311                             EXPECT_EQ( v.key(), prev->key() );
 312                             EXPECT_EQ( prev->nUpdateNewCount, 1u );
 313                             EXPECT_EQ( v.nUpdateNewCount, 0u );
 314                             ++v.nUpdateNewCount;
 315                         }, false );
 316                         EXPECT_TRUE( updResult.first );
 317                         EXPECT_FALSE( updResult.second );
 318
 319                         ASSERT_TRUE( s.find( i.key(), []( value_type const& v )
 320                         {
 321                             EXPECT_EQ( v.nUpdateNewCount, 1u );
 322                         } ) );
 323                         break;
 324                 case 6:
 325                     ASSERT_TRUE( s.emplace( i.key() ) );
 326                     ASSERT_TRUE( s.contains( i.key() ) );
 327                     break;
 328                 case 7:
 329                     str = "Hello!";
 330                     ASSERT_TRUE( s.emplace( i.key(), std::move( str ) ) );
 331                     EXPECT_TRUE( str.empty() );
 332                     ASSERT_TRUE( s.find( i.key(), []( value_type const& v )
 333                     {
 334                         EXPECT_EQ( v.strVal, std::string( "Hello!" ) );
 335                     } ) );
 336                     break;
 337                 default:
 338                     // forgot anything?..
 339                     ASSERT_TRUE( false );
 340                 }
 341
 342                 ASSERT_TRUE( s.contains( i.nKey ) );
 343                 ASSERT_TRUE( s.find( i.nKey, []( value_type& ) {} ) );
 344             }
 345
 346             ASSERT_FALSE( s.empty() );
 347             ASSERT_CONTAINER_SIZE( s, nSetSize );
 348
 349             // erase
 350             shuffle( indices.begin(), indices.end() );
 351             for ( auto idx : indices ) {
 352                 auto& i = data[idx];
 353
 354                 ASSERT_TRUE( s.contains( i.nKey ) );
 355                 ASSERT_TRUE( s.find( i.nKey, []( value_type& v )
 356                 {
 357                     v.nFindCount = 1;
 358                 } ) );
 359
 360                 int nKey = i.key() - 1;
 361                 switch ( idx % 2 ) {
 362                 case 0:
 363                     ASSERT_TRUE( s.erase( i.key() ) );
 364                     ASSERT_FALSE( s.erase( i.key() ) );
 365                     break;
 366                 case 1:
 367                     ASSERT_TRUE( s.erase( i.key(), [&nKey]( value_type const& v )
 368                     {
 369                         EXPECT_EQ( v.nFindCount, 1u );
 370                         nKey = v.key();
 371                     } ) );
 372                     EXPECT_EQ( i.key(), nKey );
 373
 374                     nKey = i.key() - 1;
 375                     ASSERT_FALSE( s.erase( i.key(), [&nKey]( value_type const& v )
 376                     {
 377                         nKey = v.key();
 378                     } ) );
 379                     EXPECT_EQ( i.key(), nKey + 1 );
 380                     break;
 381                 }
 382
 383                 ASSERT_FALSE( s.contains( i.nKey ) );
 384                 ASSERT_FALSE( s.find( i.nKey, []( value_type const& ) {} ) );
 385             }
 386             ASSERT_TRUE( s.empty() );
 387             ASSERT_CONTAINER_SIZE( s, 0u );
 388
 389
 390             // clear
 391             for ( auto& i : data ) {
 392                 ASSERT_TRUE( s.insert( i ) );
 393             }
 394
 395             {
 396                 typename Set::stat const& statistics = s.statistics();
 397                 CDS_UNUSED( statistics );
 398
 399                 std::vector< typename Set::level_statistics > lstat;
 400                 s.get_level_statistics( lstat );
 401                 EXPECT_EQ( lstat[0].node_capacity, s.head_size() );
 402                 for ( size_t i = 1; i < lstat.size(); ++i ) {
 403                     EXPECT_EQ( lstat[i].node_capacity, s.array_node_size());
 404                 }
 405             }
 406
 407             ASSERT_FALSE( s.empty() );
 408             ASSERT_CONTAINER_SIZE( s, nSetSize );
 409
 410             s.clear();
 411
 412             ASSERT_TRUE( s.empty() );
 413             ASSERT_CONTAINER_SIZE( s, 0u );
 414
 415             ASSERT_TRUE( s.begin() == s.end() );
 416             ASSERT_TRUE( s.cbegin() == s.cend() );
 417             ASSERT_TRUE( s.rbegin() == s.rend() );
 418             ASSERT_TRUE( s.crbegin() == s.crend() );
 419         }
 420     };
 421
 422 } // namespace cds_test
 423
 424 #endif // CDSUNIT_SET_TEST_FELDMAN_HASHSET_H