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