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 hash_accessor {
  97             int operator()( int_item const& v ) const
  98             {
  99                 return v.key();
 100             }
 101         };
 102
 103         struct simple_item_counter {
 104             size_t  m_nCount;
 105
 106             simple_item_counter()
 107                 : m_nCount(0)
 108             {}
 109
 110             size_t operator ++()
 111             {
 112                 return ++m_nCount;
 113             }
 114
 115             size_t operator --()
 116             {
 117                 return --m_nCount;
 118             }
 119
 120             void reset()
 121             {
 122                 m_nCount = 0;
 123             }
 124
 125             operator size_t() const
 126             {
 127                 return m_nCount;
 128             }
 129         };
 130
 131         struct cmp {
 132             int operator ()( int lhs, int rhs ) const
 133             {
 134                 if ( lhs < rhs )
 135                     return -1;
 136                 return lhs > rhs ? 1 : 0;
 137             }
 138         };
 139
 140         struct mock_disposer
 141         {
 142             template <typename T>
 143             void operator ()( T * p )
 144             {
 145                 ++p->nDisposeCount;
 146             }
 147         };
 148
 149     protected:
 150         template <class Set>
 151         void test( Set& s )
 152         {
 153             // Precondition: set is empty
 154             // Postcondition: set is empty
 155
 156             ASSERT_TRUE( s.empty() );
 157             ASSERT_CONTAINER_SIZE( s, 0 );
 158             size_t const nSetSize = std::max( s.head_size() * 2, static_cast<size_t>(100) );
 159
 160             typedef typename Set::value_type value_type;
 161
 162             std::vector< value_type > data;
 163             std::vector< size_t> indices;
 164             data.reserve( nSetSize );
 165             indices.reserve( nSetSize );
 166             for ( size_t key = 0; key < nSetSize; ++key ) {
 167                 data.push_back( value_type( static_cast<int>( key )));
 168                 indices.push_back( key );
 169             }
 170             shuffle( indices.begin(), indices.end() );
 171
 172             // insert/find
 173             for ( auto idx : indices ) {
 174                 auto& i = data[ idx ];
 175
 176                 ASSERT_FALSE( s.contains( i.nKey ));
 177                 ASSERT_FALSE( s.find( i.nKey, []( value_type& ) {} ));
 178
 179                 std::pair<bool, bool> updResult;
 180
 181                 updResult = s.update( i, false );
 182                 EXPECT_FALSE( updResult.first );
 183                 EXPECT_FALSE( updResult.second );
 184
 185                 switch ( i.key() % 3 ) {
 186                 case 0:
 187                     ASSERT_TRUE( s.insert( i ));
 188                     ASSERT_FALSE( s.insert( i ));
 189                     updResult = s.update( i, false );
 190                     EXPECT_TRUE( updResult.first );
 191                     EXPECT_FALSE( updResult.second );
 192                     break;
 193                 case 1:
 194                     EXPECT_EQ( i.nInsertCount, 0 );
 195                     ASSERT_TRUE( s.insert( i, []( value_type& v ) { ++v.nInsertCount;} ));
 196                     EXPECT_EQ( i.nInsertCount, 1 );
 197                     ASSERT_FALSE( s.insert( i, []( value_type& v ) { ++v.nInsertCount;} ) );
 198                     EXPECT_EQ( i.nInsertCount, 1 );
 199                     i.nInsertCount = 0;
 200                     break;
 201                 case 2:
 202                     updResult = s.update( i );
 203                     EXPECT_TRUE( updResult.first );
 204                     EXPECT_TRUE( updResult.second );
 205                     break;
 206                 }
 207
 208                 ASSERT_TRUE( s.contains( i.nKey ) );
 209                 EXPECT_EQ( i.nFindCount, 0 );
 210                 ASSERT_TRUE( s.find( i.nKey, []( value_type& v ) { ++v.nFindCount; } ));
 211                 EXPECT_EQ( i.nFindCount, 1 );
 212             }
 213             ASSERT_FALSE( s.empty() );
 214             ASSERT_CONTAINER_SIZE( s, nSetSize );
 215
 216             std::for_each( data.begin(), data.end(), []( value_type& v ) { v.clear_stat(); });
 217
 218             // get_level_statistics
 219             {
 220                 std::vector< typename Set::level_statistics > level_stat;
 221                 s.get_level_statistics( level_stat );
 222                 EXPECT_GT( level_stat.size(), 0u );
 223             }
 224
 225             // erase
 226             shuffle( indices.begin(), indices.end() );
 227             for ( auto idx : indices ) {
 228                 auto& i = data[ idx ];
 229
 230                 ASSERT_TRUE( s.contains( i.nKey ) );
 231                 EXPECT_EQ( i.nFindCount, 0 );
 232                 ASSERT_TRUE( s.find( i.nKey, []( value_type& v ) { ++v.nFindCount; } ) );
 233                 EXPECT_EQ( i.nFindCount, 1 );
 234
 235                 value_type v( i );
 236                 switch ( i.key() % 3 ) {
 237                 case 0:
 238                     ASSERT_FALSE( s.unlink( v ));
 239                     ASSERT_TRUE( s.unlink( i ));
 240                     ASSERT_FALSE( s.unlink( i ) );
 241                     break;
 242                 case 1:
 243                     ASSERT_TRUE( s.erase( i.key()));
 244                     ASSERT_FALSE( s.erase( i.key() ) );
 245                     break;
 246                 case 2:
 247                     EXPECT_EQ( i.nEraseCount, 0 );
 248                     ASSERT_TRUE( s.erase( v.key(), []( value_type& val ) { ++val.nEraseCount; } ));
 249                     EXPECT_EQ( i.nEraseCount, 1 );
 250                     ASSERT_FALSE( s.erase( v.key(), []( value_type& val ) { ++val.nEraseCount; } ));
 251                     EXPECT_EQ( i.nEraseCount, 1 );
 252                     break;
 253                 }
 254
 255                 ASSERT_FALSE( s.contains( i.nKey ));
 256                 ASSERT_FALSE( s.find( i.nKey, []( value_type const& ) {} ));
 257             }
 258             ASSERT_TRUE( s.empty() );
 259             ASSERT_CONTAINER_SIZE( s, 0 );
 260
 261             // Force retiring cycle
 262             Set::gc::force_dispose();
 263             for ( auto& i : data ) {
 264                 EXPECT_EQ( i.nDisposeCount, 1 );
 265             }
 266
 267             // clear
 268             for ( auto& i : data ) {
 269                 i.clear_stat();
 270                 ASSERT_TRUE( s.insert( i ));
 271             }
 272             ASSERT_FALSE( s.empty() );
 273             ASSERT_CONTAINER_SIZE( s, nSetSize );
 274
 275             // Forward iterator test
 276             for ( auto it = s.begin(); it != s.end(); ++it ) {
 277                 ++it->nFindCount;
 278             }
 279             for ( auto it = s.cbegin(); it != s.cend(); ++it ) {
 280                 EXPECT_EQ( it->nFindCount, 1 );
 281             }
 282
 283             // Reverse iterator test
 284             for ( auto it = s.rbegin(); it != s.rend(); ++it ) {
 285                 ++it->nFindCount;
 286             }
 287             for ( auto it = s.crbegin(); it != s.crend(); ++it ) {
 288                 EXPECT_EQ( it->nFindCount, 2 );
 289             }
 290
 291             for ( auto& i : data ) {
 292                 EXPECT_EQ( i.nFindCount, 2 );
 293             }
 294
 295             // clear test
 296             s.clear();
 297
 298             ASSERT_TRUE( s.empty());
 299             ASSERT_CONTAINER_SIZE( s, 0 );
 300             ASSERT_TRUE( s.begin() == s.end() );
 301             ASSERT_TRUE( s.cbegin() == s.cend() );
 302
 303             // Force retiring cycle
 304             Set::gc::force_dispose();
 305             for ( auto& i : data ) {
 306                 EXPECT_EQ( i.nDisposeCount, 1 );
 307             }
 308         }
 309     };
 310
 311 } // namespace cds_test
 312
 313 #endif // #ifndef CDSUNIT_SET_TEST_INTRUSIVE_FELDMAN_HASHSET_H