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