gdax-orderbook-hpp/demo/dependencies/libcds-2.3.2/test/unit/striped-set/test_intrusive_set.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_STRIPED_SET_TEST_INTRUSIVE_SET_H
  32 #define CDSUNIT_STRIPED_SET_TEST_INTRUSIVE_SET_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 intrusive {}}
  41
  42 namespace cds_test {
  43
  44     namespace ci = cds::intrusive;
  45     namespace co = cds::opt;
  46
  47     class intrusive_set: public fixture
  48     {
  49     public:
  50         static size_t const kSize = 1000;
  51
  52         struct stat
  53         {
  54             unsigned int nDisposeCount  ;   // count of disposer calling
  55             unsigned int nFindCount     ;   // count of find-functor calling
  56             unsigned int nUpdateNewCount;
  57             unsigned int nUpdateCount;
  58             mutable unsigned int nEraseCount;
  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             typedef Node member_type;
 110
 111             int nKey;
 112             int nVal;
 113
 114             Node hMember;
 115
 116             stat s;
 117
 118             member_int_item()
 119             {}
 120
 121             explicit member_int_item( int key )
 122                 : nKey( key )
 123                 , nVal( key )
 124             {}
 125
 126             member_int_item(int key, int val)
 127                 : nKey( key )
 128                 , nVal(val)
 129             {}
 130
 131             member_int_item(member_int_item const& v )
 132                 : stat()
 133                 , nKey( v.nKey )
 134                 , nVal( v.nVal )
 135             {}
 136
 137             int key() const
 138             {
 139                 return nKey;
 140             }
 141         };
 142
 143         struct hash_int {
 144             size_t operator()( int i ) const
 145             {
 146                 return co::v::hash<int>()( i );
 147             }
 148             template <typename Item>
 149             size_t operator()( const Item& i ) const
 150             {
 151                 return (*this)( i.key());
 152             }
 153         };
 154         typedef hash_int hash1;
 155
 156         struct hash2: private hash1
 157         {
 158             typedef hash1 base_class;
 159
 160             size_t operator()( int i ) const
 161             {
 162                 size_t h = ~(base_class::operator()( i ));
 163                 return ~h + 0x9e3779b9 + (h << 6) + (h >> 2);
 164             }
 165             template <typename Item>
 166             size_t operator()( const Item& i ) const
 167             {
 168                 size_t h = ~(base_class::operator()( i ));
 169                 return ~h + 0x9e3779b9 + (h << 6) + (h >> 2);
 170             }
 171         };
 172
 173         struct simple_item_counter {
 174             size_t  m_nCount;
 175
 176             simple_item_counter()
 177                 : m_nCount(0)
 178             {}
 179
 180             size_t operator ++()
 181             {
 182                 return ++m_nCount;
 183             }
 184
 185             size_t operator --()
 186             {
 187                 return --m_nCount;
 188             }
 189
 190             void reset()
 191             {
 192                 m_nCount = 0;
 193             }
 194
 195             operator size_t() const
 196             {
 197                 return m_nCount;
 198             }
 199         };
 200
 201
 202         template <typename T>
 203         struct less
 204         {
 205             bool operator ()(const T& v1, const T& v2 ) const
 206             {
 207                 return v1.key() < v2.key();
 208             }
 209
 210             bool operator ()(const T& v1, int v2 ) const
 211             {
 212                 return v1.key() < v2;
 213             }
 214
 215             bool operator ()(int v1, const T& v2 ) const
 216             {
 217                 return v1 < v2.key();
 218             }
 219
 220             bool operator()( int v1, int v2 ) const
 221             {
 222                 return v1 < v2;
 223             }
 224         };
 225
 226         template <typename T>
 227         struct cmp {
 228             int operator ()(const T& v1, const T& v2 ) const
 229             {
 230                 if ( v1.key() < v2.key())
 231                     return -1;
 232                 return v1.key() > v2.key() ? 1 : 0;
 233             }
 234
 235             template <typename Q>
 236             int operator ()(const T& v1, const Q& v2 ) const
 237             {
 238                 if ( v1.key() < v2 )
 239                     return -1;
 240                 return v1.key() > v2 ? 1 : 0;
 241             }
 242
 243             template <typename Q>
 244             int operator ()(const Q& v1, const T& v2 ) const
 245             {
 246                 if ( v1 < v2.key())
 247                     return -1;
 248                 return v1 > v2.key() ? 1 : 0;
 249             }
 250         };
 251
 252         template <typename T>
 253         struct equal_to {
 254             int operator ()( const T& v1, const T& v2 ) const
 255             {
 256                 return v1.key() == v2.key();
 257             }
 258
 259             int operator ()( const T& v1, int v2 ) const
 260             {
 261                 return v1.key() == v2;
 262             }
 263
 264             int operator ()( int v1, const T& v2 ) const
 265             {
 266                 return v1 == v2.key();
 267             }
 268         };
 269
 270         struct other_item {
 271             int nKey;
 272
 273             explicit other_item( int k )
 274                 : nKey( k )
 275             {}
 276
 277             int key() const
 278             {
 279                 return nKey;
 280             }
 281         };
 282
 283         struct other_less {
 284             template <typename T>
 285             bool operator()( other_item const& lhs, T const& rhs ) const
 286             {
 287                 return lhs.key() < rhs.key();
 288             }
 289
 290             template <typename T>
 291             bool operator()( T const& lhs, other_item const& rhs ) const
 292             {
 293                 return lhs.key() < rhs.key();
 294             }
 295
 296             bool operator()( other_item const& lhs, int rhs ) const
 297             {
 298                 return lhs.key() < rhs;
 299             }
 300
 301             bool operator()( int lhs, other_item const& rhs ) const
 302             {
 303                 return lhs < rhs.key();
 304             }
 305         };
 306
 307         struct other_equal_to {
 308             template <typename Q, typename T>
 309             bool operator()( Q const& lhs, T const& rhs ) const
 310             {
 311                 return lhs.key() == rhs.key();
 312             }
 313         };
 314
 315         struct mock_disposer
 316         {
 317             template <typename T>
 318             void operator ()( T * p )
 319             {
 320                 ++p->nDisposeCount;
 321             }
 322         };
 323
 324     protected:
 325         template <typename Set>
 326         void test( Set& s, std::vector< typename Set::value_type >& data )
 327         {
 328             test_< true >( s, data );
 329         }
 330
 331         template <bool Sorted, class Set>
 332         void test_( Set& s, std::vector< typename Set::value_type >& data )
 333         {
 334             // Precondition: set is empty
 335             // Postcondition: set is empty
 336
 337             ASSERT_TRUE( s.empty());
 338             ASSERT_CONTAINER_SIZE( s, 0 );
 339
 340             typedef typename Set::value_type value_type;
 341             typedef typename std::conditional< Sorted, other_less, other_equal_to >::type other_predicate;
 342             size_t const nSetSize = kSize;
 343
 344             std::vector< size_t> indices;
 345             data.reserve( kSize );
 346             indices.reserve( kSize );
 347             for ( size_t key = 0; key < kSize; ++key ) {
 348                 data.push_back( value_type( static_cast<int>( key )));
 349                 indices.push_back( key );
 350             }
 351             shuffle( indices.begin(), indices.end());
 352
 353             // insert/find
 354             for ( auto idx : indices ) {
 355                 auto& i = data[ idx ];
 356
 357                 ASSERT_FALSE( s.contains( i.nKey ));
 358                 ASSERT_FALSE( s.contains( i ));
 359                 ASSERT_FALSE( s.contains( other_item( i.key()), other_predicate()));
 360                 ASSERT_FALSE( s.find( i.nKey, []( value_type&, int ) {} ));
 361                 ASSERT_FALSE( s.find_with( other_item( i.key()), other_predicate(), []( value_type&, other_item const& ) {} ));
 362
 363                 std::pair<bool, bool> updResult;
 364
 365                 updResult = s.update( i, []( bool /*bNew*/, value_type&, value_type& )
 366                 {
 367                     ASSERT_TRUE( false );
 368                 }, false );
 369                 EXPECT_FALSE( updResult.first );
 370                 EXPECT_FALSE( updResult.second );
 371
 372                 switch ( i.key() % 3 ) {
 373                 case 0:
 374                     ASSERT_TRUE( s.insert( i ));
 375                     ASSERT_FALSE( s.insert( i ));
 376                     updResult = s.update( i, []( bool bNew, value_type& val, value_type& arg)
 377                         {
 378                             EXPECT_FALSE( bNew );
 379                             EXPECT_EQ( &val, &arg );
 380                         }, false );
 381                     EXPECT_TRUE( updResult.first );
 382                     EXPECT_FALSE( updResult.second );
 383                     break;
 384                 case 1:
 385                     EXPECT_EQ( i.nUpdateNewCount, 0u );
 386                     ASSERT_TRUE( s.insert( i, []( value_type& v ) { ++v.nUpdateNewCount;} ));
 387                     EXPECT_EQ( i.nUpdateNewCount, 1u );
 388                     ASSERT_FALSE( s.insert( i, []( value_type& v ) { ++v.nUpdateNewCount;} ));
 389                     EXPECT_EQ( i.nUpdateNewCount, 1u );
 390                     i.nUpdateNewCount = 0;
 391                     break;
 392                 case 2:
 393                     updResult = s.update( i, []( bool bNew, value_type& val, value_type& arg )
 394                     {
 395                         EXPECT_TRUE( bNew );
 396                         EXPECT_EQ( &val, &arg );
 397                     });
 398                     EXPECT_TRUE( updResult.first );
 399                     EXPECT_TRUE( updResult.second );
 400                     break;
 401                 }
 402
 403                 ASSERT_TRUE( s.contains( i.nKey ));
 404                 ASSERT_TRUE( s.contains( i ));
 405                 ASSERT_TRUE( s.contains( other_item( i.key()), other_predicate()));
 406                 EXPECT_EQ( i.nFindCount, 0u );
 407                 ASSERT_TRUE( s.find( i.nKey, []( value_type& v, int ) { ++v.nFindCount; } ));
 408                 EXPECT_EQ( i.nFindCount, 1u );
 409                 ASSERT_TRUE( s.find_with( other_item( i.key()), other_predicate(), []( value_type& v, other_item const& ) { ++v.nFindCount; } ));
 410                 EXPECT_EQ( i.nFindCount, 2u );
 411             }
 412             ASSERT_FALSE( s.empty());
 413             ASSERT_CONTAINER_SIZE( s, nSetSize );
 414
 415             std::for_each( data.begin(), data.end(), []( value_type& v ) { v.clear_stat(); });
 416
 417             // erase
 418             shuffle( indices.begin(), indices.end());
 419             for ( auto idx : indices ) {
 420                 auto& i = data[ idx ];
 421
 422                 ASSERT_TRUE( s.contains( i.nKey ));
 423                 ASSERT_TRUE( s.contains( i ));
 424                 ASSERT_TRUE( s.contains( other_item( i.key()), other_predicate()));
 425                 EXPECT_EQ( i.nFindCount, 0u );
 426                 ASSERT_TRUE( s.find( i.nKey, []( value_type& v, int ) { ++v.nFindCount; } ));
 427                 EXPECT_EQ( i.nFindCount, 1u );
 428                 ASSERT_TRUE( s.find_with( other_item( i.key()), other_predicate(), []( value_type& v, other_item const& ) { ++v.nFindCount; } ));
 429                 EXPECT_EQ( i.nFindCount, 2u );
 430
 431                 value_type v( i );
 432                 switch ( i.key() % 6 ) {
 433                 case 0:
 434                     ASSERT_FALSE( s.unlink( v ));
 435                     ASSERT_TRUE( s.unlink( i ));
 436                     ASSERT_FALSE( s.unlink( i ));
 437                     break;
 438                 case 1:
 439                     ASSERT_TRUE( s.erase( i.key()));
 440                     ASSERT_FALSE( s.erase( i.key()));
 441                     break;
 442                 case 2:
 443                     ASSERT_TRUE( s.erase( v ));
 444                     ASSERT_FALSE( s.erase( v ));
 445                     break;
 446                 case 3:
 447                     ASSERT_TRUE( s.erase_with( other_item( i.key()), other_predicate()));
 448                     ASSERT_FALSE( s.erase_with( other_item( i.key()), other_predicate()));
 449                     break;
 450                 case 4:
 451                     EXPECT_EQ( i.nEraseCount, 0u );
 452                     ASSERT_TRUE( s.erase( v, []( value_type& val ) { ++val.nEraseCount; } ));
 453                     EXPECT_EQ( i.nEraseCount, 1u );
 454                     ASSERT_FALSE( s.erase( v, []( value_type& val ) { ++val.nEraseCount; } ));
 455                     EXPECT_EQ( i.nEraseCount, 1u );
 456                     break;
 457                 case 5:
 458                     EXPECT_EQ( i.nEraseCount, 0u );
 459                     ASSERT_TRUE( s.erase_with( other_item( i.key()), other_predicate(), []( value_type& val ) { ++val.nEraseCount; } ));
 460                     EXPECT_EQ( i.nEraseCount, 1u );
 461                     ASSERT_FALSE( s.erase_with( other_item( i.key()), other_predicate(), []( value_type& val ) { ++val.nEraseCount; } ));
 462                     EXPECT_EQ( i.nEraseCount, 1u );
 463                     break;
 464                 }
 465
 466                 ASSERT_FALSE( s.contains( i.nKey ));
 467                 ASSERT_FALSE( s.contains( i ));
 468                 ASSERT_FALSE( s.contains( other_item( i.key()), other_predicate()));
 469                 ASSERT_FALSE( s.find( i.nKey, []( value_type&, int ) {} ));
 470                 ASSERT_FALSE( s.find_with( other_item( i.key()), other_predicate(), []( value_type&, other_item const& ) {} ));
 471             }
 472             ASSERT_TRUE( s.empty());
 473             ASSERT_CONTAINER_SIZE( s, 0u );
 474
 475             // clear
 476             for ( auto& i : data ) {
 477                 i.clear_stat();
 478                 ASSERT_TRUE( s.insert( i ));
 479             }
 480             ASSERT_FALSE( s.empty());
 481             ASSERT_CONTAINER_SIZE( s, nSetSize );
 482
 483             s.clear();
 484
 485             ASSERT_TRUE( s.empty());
 486             ASSERT_CONTAINER_SIZE( s, 0u );
 487
 488             // clear_and_dispose
 489             for ( auto& i : data ) {
 490                 i.clear_stat();
 491                 ASSERT_TRUE( s.insert( i ));
 492             }
 493             ASSERT_FALSE( s.empty());
 494             ASSERT_CONTAINER_SIZE( s, nSetSize );
 495
 496             s.clear_and_dispose( mock_disposer());
 497
 498             ASSERT_TRUE( s.empty());
 499             ASSERT_CONTAINER_SIZE( s, 0 );
 500             for ( auto& i : data ) {
 501                 EXPECT_EQ( i.nDisposeCount, 1u );
 502             }
 503
 504         }
 505     };
 506
 507 } // namespace cds_test
 508
 509 #endif // #ifndef CDSUNIT_STRIPED_SET_TEST_INTRUSIVE_SET_H