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