test/unit/intrusive-set/test_intrusive_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_INTRUSIVE_FELDMAN_HASHSET_H
  32 #define CDSUNIT_SET_TEST_INTRUSIVE_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 #include <functional>   // ref
  39
  40 // forward declaration
  41 namespace cds { namespace intrusive {}}
  42 namespace ci = cds::intrusive;
  43
  44 namespace cds_test {
  45     class intrusive_feldman_hashset: public fixture
  46     {
  47     public:
  48         struct stat
  49         {
  50             unsigned int nDisposeCount;   // count of disposer calling
  51             unsigned int nFindCount;   // count of find-functor calling
  52             unsigned int nInsertCount;
  53             mutable unsigned int nEraseCount;
  54
  55             stat()
  56             {
  57                 clear_stat();
  58             }
  59
  60             void clear_stat()
  61             {
  62                 memset( this, 0, sizeof( *this ) );
  63             }
  64         };
  65
  66         struct int_item: public stat
  67         {
  68             int nKey;
  69             int nVal;
  70
  71             int_item()
  72             {}
  73
  74             explicit int_item( int key )
  75                 : nKey( key )
  76                 , nVal( key )
  77             {}
  78
  79             int_item( int key, int val )
  80                 : nKey( key )
  81                 , nVal( val )
  82             {}
  83
  84             int_item( int_item const& v )
  85                 : stat()
  86                 , nKey( v.nKey )
  87                 , nVal( v.nVal )
  88             {}
  89
  90             int key() const
  91             {
  92                 return nKey;
  93             }
  94         };
  95
  96         struct key_val {
  97             int nKey;
  98             int nVal;
  99
 100             key_val()
 101             {}
 102
 103             key_val( int key )
 104                 : nKey( key )
 105                 , nVal( key )
 106             {}
 107
 108             key_val( int key, int val )
 109                 : nKey( key )
 110                 , nVal( val )
 111             {}
 112
 113             key_val( key_val const& v )
 114                 : nKey( v.nKey )
 115                 , nVal( v.nVal )
 116             {}
 117
 118             int key() const
 119             {
 120                 return nKey;
 121             }
 122         };
 123
 124         struct int_item2: public key_val, public stat
 125         {
 126             int_item2()
 127             {}
 128
 129             explicit int_item2( int key )
 130                 : key_val( key )
 131             {}
 132
 133             int_item2( int key, int val )
 134                 : key_val( key, val )
 135             {}
 136
 137             int_item2( int_item2 const& v )
 138                 : key_val( v )
 139                 , stat()
 140             {}
 141         };
 142
 143         struct hash_accessor {
 144             int operator()( int_item const& v ) const
 145             {
 146                 return v.key();
 147             }
 148         };
 149
 150         struct hash_accessor2 {
 151             key_val const& operator()( int_item2 const& v ) const
 152             {
 153                 return v;
 154             }
 155         };
 156
 157         struct simple_item_counter {
 158             size_t  m_nCount;
 159
 160             simple_item_counter()
 161                 : m_nCount(0)
 162             {}
 163
 164             size_t operator ++()
 165             {
 166                 return ++m_nCount;
 167             }
 168
 169             size_t operator --()
 170             {
 171                 return --m_nCount;
 172             }
 173
 174             void reset()
 175             {
 176                 m_nCount = 0;
 177             }
 178
 179             operator size_t() const
 180             {
 181                 return m_nCount;
 182             }
 183         };
 184
 185         struct cmp {
 186             int operator ()( int lhs, int rhs ) const
 187             {
 188                 if ( lhs < rhs )
 189                     return -1;
 190                 return lhs > rhs ? 1 : 0;
 191             }
 192         };
 193
 194         struct cmp2 {
 195             int operator ()( key_val const& lhs, key_val const& rhs ) const
 196             {
 197                 if ( lhs.key() < rhs.key() )
 198                     return -1;
 199                 return lhs.key() > rhs.key() ? 1 : 0;
 200             }
 201         };
 202
 203         struct mock_disposer
 204         {
 205             template <typename T>
 206             void operator ()( T * p )
 207             {
 208                 ++p->nDisposeCount;
 209             }
 210         };
 211
 212     protected:
 213         template <class Set>
 214         void test( Set& s )
 215         {
 216             // Precondition: set is empty
 217             // Postcondition: set is empty
 218
 219             ASSERT_TRUE( s.empty());
 220             ASSERT_CONTAINER_SIZE( s, 0 );
 221             size_t const nSetSize = std::max( s.head_size() * 2, static_cast<size_t>(100));
 222
 223             typedef typename Set::value_type value_type;
 224
 225             std::vector< value_type > data;
 226             std::vector< size_t> indices;
 227             data.reserve( nSetSize );
 228             indices.reserve( nSetSize );
 229             for ( size_t key = 0; key < nSetSize; ++key ) {
 230                 data.push_back( value_type( static_cast<int>( key )));
 231                 indices.push_back( key );
 232             }
 233             shuffle( indices.begin(), indices.end());
 234
 235             // insert/find
 236             for ( auto idx : indices ) {
 237                 auto& i = data[ idx ];
 238
 239                 ASSERT_FALSE( s.contains( i.nKey ));
 240                 ASSERT_FALSE( s.find( i.nKey, []( value_type& ) {} ));
 241
 242                 std::pair<bool, bool> updResult;
 243
 244                 updResult = s.update( i, false );
 245                 EXPECT_FALSE( updResult.first );
 246                 EXPECT_FALSE( updResult.second );
 247
 248                 switch ( i.key() % 3 ) {
 249                 case 0:
 250                     ASSERT_TRUE( s.insert( i ));
 251                     ASSERT_FALSE( s.insert( i ));
 252                     updResult = s.update( i, false );
 253                     EXPECT_TRUE( updResult.first );
 254                     EXPECT_FALSE( updResult.second );
 255                     break;
 256                 case 1:
 257                     EXPECT_EQ( i.nInsertCount, 0u );
 258                     ASSERT_TRUE( s.insert( i, []( value_type& v ) { ++v.nInsertCount;} ));
 259                     EXPECT_EQ( i.nInsertCount, 1u );
 260                     ASSERT_FALSE( s.insert( i, []( value_type& v ) { ++v.nInsertCount;} ));
 261                     EXPECT_EQ( i.nInsertCount, 1u );
 262                     i.nInsertCount = 0;
 263                     break;
 264                 case 2:
 265                     updResult = s.update( i );
 266                     EXPECT_TRUE( updResult.first );
 267                     EXPECT_TRUE( updResult.second );
 268                     break;
 269                 }
 270
 271                 ASSERT_TRUE( s.contains( i.nKey ));
 272                 EXPECT_EQ( i.nFindCount, 0u );
 273                 ASSERT_TRUE( s.find( i.nKey, []( value_type& v ) { ++v.nFindCount; } ));
 274                 EXPECT_EQ( i.nFindCount, 1u );
 275             }
 276             ASSERT_FALSE( s.empty());
 277             ASSERT_CONTAINER_SIZE( s, nSetSize );
 278
 279             std::for_each( data.begin(), data.end(), []( value_type& v ) { v.clear_stat(); });
 280
 281             // get_level_statistics
 282             {
 283                 std::vector< typename Set::level_statistics > level_stat;
 284                 s.get_level_statistics( level_stat );
 285                 EXPECT_GT( level_stat.size(), 0u );
 286             }
 287
 288             // erase
 289             shuffle( indices.begin(), indices.end());
 290             for ( auto idx : indices ) {
 291                 auto& i = data[ idx ];
 292
 293                 ASSERT_TRUE( s.contains( i.nKey ));
 294                 EXPECT_EQ( i.nFindCount, 0u );
 295                 ASSERT_TRUE( s.find( i.nKey, []( value_type& v ) { ++v.nFindCount; } ));
 296                 EXPECT_EQ( i.nFindCount, 1u );
 297
 298                 value_type v( i );
 299                 switch ( i.key() % 3 ) {
 300                 case 0:
 301                     ASSERT_FALSE( s.unlink( v ));
 302                     ASSERT_TRUE( s.unlink( i ));
 303                     ASSERT_FALSE( s.unlink( i ));
 304                     break;
 305                 case 1:
 306                     ASSERT_TRUE( s.erase( i.key()));
 307                     ASSERT_FALSE( s.erase( i.key()));
 308                     break;
 309                 case 2:
 310                     EXPECT_EQ( i.nEraseCount, 0u );
 311                     ASSERT_TRUE( s.erase( v.key(), []( value_type& val ) { ++val.nEraseCount; } ));
 312                     EXPECT_EQ( i.nEraseCount, 1u );
 313                     ASSERT_FALSE( s.erase( v.key(), []( value_type& val ) { ++val.nEraseCount; } ));
 314                     EXPECT_EQ( i.nEraseCount, 1u );
 315                     break;
 316                 }
 317
 318                 ASSERT_FALSE( s.contains( i.nKey ));
 319                 ASSERT_FALSE( s.find( i.nKey, []( value_type const& ) {} ));
 320             }
 321             ASSERT_TRUE( s.empty());
 322             ASSERT_CONTAINER_SIZE( s, 0 );
 323
 324             // Force retiring cycle
 325             Set::gc::force_dispose();
 326             for ( auto& i : data ) {
 327                 EXPECT_EQ( i.nDisposeCount, 1u );
 328             }
 329
 330             // clear
 331             for ( auto& i : data ) {
 332                 i.clear_stat();
 333                 ASSERT_TRUE( s.insert( i ));
 334             }
 335             ASSERT_FALSE( s.empty());
 336             ASSERT_CONTAINER_SIZE( s, nSetSize );
 337
 338             // Forward iterator test
 339             for ( auto it = s.begin(); it != s.end(); ++it ) {
 340                 ++it->nFindCount;
 341             }
 342             for ( auto it = s.cbegin(); it != s.cend(); ++it ) {
 343                 EXPECT_EQ( it->nFindCount, 1u );
 344             }
 345
 346             // Reverse iterator test
 347             for ( auto it = s.rbegin(); it != s.rend(); ++it ) {
 348                 ++it->nFindCount;
 349             }
 350             for ( auto it = s.crbegin(); it != s.crend(); ++it ) {
 351                 EXPECT_EQ( it->nFindCount, 2u );
 352             }
 353
 354             for ( auto& i : data ) {
 355                 EXPECT_EQ( i.nFindCount, 2u );
 356             }
 357
 358             // clear test
 359             s.clear();
 360
 361             ASSERT_TRUE( s.empty());
 362             ASSERT_CONTAINER_SIZE( s, 0u );
 363             ASSERT_TRUE( s.begin() == s.end());
 364             ASSERT_TRUE( s.cbegin() == s.cend());
 365
 366             // Force retiring cycle
 367             Set::gc::force_dispose();
 368             for ( auto& i : data ) {
 369                 EXPECT_EQ( i.nDisposeCount, 1u );
 370             }
 371         }
 372     };
 373
 374 } // namespace cds_test
 375
 376 #endif // #ifndef CDSUNIT_SET_TEST_INTRUSIVE_FELDMAN_HASHSET_H