tests/test-hdr/list/hdr_intrusive_lazy.h

   1 //$$CDS-header$$
   2
   3 #ifndef CDSTEST_HDR_INTRUSIVE_LAZY_H
   4 #define CDSTEST_HDR_INTRUSIVE_LAZY_H
   5
   6 #include "cppunit/cppunit_proxy.h"
   7 #include <cds/intrusive/details/lazy_list_base.h>
   8
   9 namespace ordlist {
  10     namespace ci = cds::intrusive;
  11     namespace co = cds::opt;
  12
  13     class IntrusiveLazyListHeaderTest: public CppUnitMini::TestCase
  14     {
  15     public:
  16
  17         struct stat {
  18             int nDisposeCount;
  19             int nUpdateExistsCall;
  20             int nUpdateNewCall;
  21             int nFindCall;
  22             int nEraseCall;
  23
  24             stat()
  25                 : nDisposeCount(0)
  26                 , nUpdateExistsCall(0)
  27                 , nUpdateNewCall(0)
  28                 , nFindCall(0)
  29                 , nEraseCall(0)
  30             {}
  31
  32             stat( const stat& s )
  33             {
  34                 *this = s;
  35             }
  36
  37             stat& operator =(const stat& s)
  38             {
  39                 memcpy( this, &s, sizeof(s));
  40                 return *this;
  41             }
  42         };
  43
  44         template <typename GC>
  45         struct base_int_item: public ci::lazy_list::node< GC >
  46         {
  47             int nKey;
  48             int nVal;
  49
  50             mutable stat    s;
  51
  52             base_int_item()
  53             {}
  54
  55             base_int_item(int key, int val)
  56                 : nKey( key )
  57                 , nVal(val)
  58                 , s()
  59             {}
  60
  61             base_int_item(const base_int_item& v )
  62                 : nKey( v.nKey )
  63                 , nVal( v.nVal )
  64                 , s()
  65             {}
  66
  67             const int& key() const
  68             {
  69                 return nKey;
  70             }
  71         };
  72
  73         template <typename GC>
  74         struct member_int_item
  75         {
  76             int nKey;
  77             int nVal;
  78
  79             ci::lazy_list::node< GC > hMember;
  80
  81             mutable stat s;
  82
  83             member_int_item()
  84             {}
  85
  86             member_int_item(int key, int val)
  87                 : nKey( key )
  88                 , nVal(val)
  89                 , s()
  90             {}
  91
  92             member_int_item(const member_int_item& v )
  93                 : nKey( v.nKey )
  94                 , nVal( v.nVal )
  95                 , s()
  96             {}
  97
  98             const int& key() const
  99             {
 100                 return nKey;
 101             }
 102         };
 103
 104         template <typename T>
 105         struct less
 106         {
 107             bool operator ()(const T& v1, const T& v2 ) const
 108             {
 109                 return v1.key() < v2.key();
 110             }
 111
 112             template <typename Q>
 113             bool operator ()(const T& v1, const Q& v2 ) const
 114             {
 115                 return v1.key() < v2;
 116             }
 117
 118             template <typename Q>
 119             bool operator ()(const Q& v1, const T& v2 ) const
 120             {
 121                 return v1 < v2.key();
 122             }
 123         };
 124
 125         template <typename T>
 126         struct cmp {
 127             int operator ()(const T& v1, const T& v2 ) const
 128             {
 129                 if ( v1.key() < v2.key() )
 130                     return -1;
 131                 return v1.key() > v2.key() ? 1 : 0;
 132             }
 133
 134             template <typename Q>
 135             int operator ()(const T& v1, const Q& v2 ) const
 136             {
 137                 if ( v1.key() < v2 )
 138                     return -1;
 139                 return v1.key() > v2 ? 1 : 0;
 140             }
 141
 142             template <typename Q>
 143             int operator ()(const Q& v1, const T& v2 ) const
 144             {
 145                 if ( v1 < v2.key() )
 146                     return -1;
 147                 return v1 > v2.key() ? 1 : 0;
 148             }
 149         };
 150
 151         template <typename T>
 152         struct equal_to {
 153             bool operator ()(const T& v1, const T& v2 ) const
 154             {
 155                 return v1.key() == v2.key();
 156             }
 157
 158             template <typename Q>
 159             bool operator ()(const T& v1, const Q& v2 ) const
 160             {
 161                 return v1.key() == v2;
 162             }
 163
 164             template <typename Q>
 165             bool operator ()(const Q& v1, const T& v2 ) const
 166             {
 167                 return v1 == v2.key();
 168             }
 169         };
 170
 171         struct other_item {
 172             int nKey;
 173
 174             other_item( int n )
 175                 : nKey(n)
 176             {}
 177         };
 178
 179         struct other_less {
 180             template <typename T, typename Q>
 181             bool operator()( T const& i1, Q const& i2) const
 182             {
 183                 return i1.nKey < i2.nKey;
 184             }
 185         };
 186
 187         struct other_equal {
 188             template <typename T, typename Q>
 189             bool operator()( T const& i1, Q const& i2) const
 190             {
 191                 return i1.nKey == i2.nKey;
 192             }
 193         };
 194
 195         struct faked_disposer
 196         {
 197             template <typename T>
 198             void operator ()( T * p )
 199             {
 200                 ++p->s.nDisposeCount;
 201             }
 202         };
 203
 204         struct update_functor
 205         {
 206             template <typename T>
 207             void operator ()(bool bNew, T& item, T& /*val*/ )
 208             {
 209                 if ( bNew )
 210                     ++item.s.nUpdateNewCall;
 211                 else
 212                     ++item.s.nUpdateExistsCall;
 213             }
 214         };
 215
 216         struct find_functor
 217         {
 218             template <typename T, typename Q>
 219             void operator ()( T& item, Q& /*val*/ )
 220             {
 221                 ++item.s.nFindCall;
 222             }
 223         };
 224
 225         struct erase_functor
 226         {
 227             template <typename T>
 228             void operator()( T const& item )
 229             {
 230                 item.s.nEraseCall++;
 231             }
 232         };
 233
 234         template <class OrdList>
 235         void test_int_common()
 236         {
 237             typedef typename OrdList::value_type    value_type;
 238
 239             value_type v1( 10, 50 );
 240             value_type v2( 5, 25  );
 241             value_type v3( 20, 100 );
 242             {
 243                 OrdList l;
 244                 CPPUNIT_ASSERT( l.empty() );
 245
 246                 CPPUNIT_ASSERT( l.insert( v1 ))     ;   // true
 247                 CPPUNIT_ASSERT( l.contains( v1.key() ));
 248
 249                 CPPUNIT_ASSERT( v1.s.nFindCall == 0 );
 250                 CPPUNIT_ASSERT( l.find( v1.key(), find_functor() ));
 251                 CPPUNIT_ASSERT( v1.s.nFindCall == 1 );
 252
 253                 CPPUNIT_ASSERT( !l.contains( v2.key(), less<value_type>() ));
 254                 CPPUNIT_ASSERT( !l.find( v3.key(), find_functor() ));
 255                 CPPUNIT_ASSERT( !l.empty() );
 256
 257                 //CPPUNIT_ASSERT( !l.insert( v1 ))    ;   // assertion "is_empty" is raised
 258
 259                 {
 260                     value_type v( v1 );
 261                     CPPUNIT_ASSERT( !l.insert( v )) ;   // false
 262                 }
 263
 264                 std::pair<bool, bool> ret = l.update( v2, update_functor() );
 265                 CPPUNIT_ASSERT( ret.first );
 266                 CPPUNIT_ASSERT( ret.second );
 267                 CPPUNIT_ASSERT( v2.s.nUpdateNewCall == 1 );
 268                 CPPUNIT_ASSERT( v2.s.nUpdateExistsCall == 0 );
 269
 270                 //CPPUNIT_ASSERT( !l.insert( v2 ))    ;   // assertion "is_empty"
 271
 272                 CPPUNIT_ASSERT( l.contains( v1.key() )) ;   // true
 273
 274                 CPPUNIT_ASSERT( v1.s.nFindCall == 1 );
 275                 CPPUNIT_ASSERT( l.find( v1.key(), find_functor() ));
 276                 CPPUNIT_ASSERT( v1.s.nFindCall == 2 );
 277
 278                 CPPUNIT_ASSERT( l.contains( v2.key() ));
 279
 280                 CPPUNIT_ASSERT( v2.s.nFindCall == 0 );
 281                 CPPUNIT_ASSERT( l.find_with( v2.key(), less<value_type>(), find_functor() ));
 282                 CPPUNIT_ASSERT( v2.s.nFindCall == 1 );
 283
 284                 CPPUNIT_ASSERT( !l.contains( v3.key() ));
 285
 286                 {
 287                     CPPUNIT_ASSERT( v2.s.nUpdateExistsCall == 0 );
 288                     CPPUNIT_ASSERT( v2.s.nUpdateNewCall == 1 );
 289
 290                     value_type v( v2 );
 291                     ret = l.update( v, update_functor() );
 292
 293                     CPPUNIT_ASSERT( ret.first );
 294                     CPPUNIT_ASSERT( !ret.second );
 295                     CPPUNIT_ASSERT( v2.s.nUpdateExistsCall == 1 );
 296                     CPPUNIT_ASSERT( v2.s.nUpdateNewCall == 1 );
 297                     CPPUNIT_ASSERT( v.s.nUpdateExistsCall == 0 );
 298                     CPPUNIT_ASSERT( v.s.nUpdateNewCall == 0 );
 299                 }
 300
 301                 CPPUNIT_ASSERT( !l.empty() );
 302
 303                 CPPUNIT_ASSERT( l.insert( v3 ))     ;   // true
 304                 CPPUNIT_ASSERT( l.contains( v3.key() ));
 305
 306                 CPPUNIT_ASSERT( v3.s.nFindCall == 0 );
 307                 CPPUNIT_ASSERT( l.find( v3.key(), find_functor() ));
 308                 CPPUNIT_ASSERT( v3.s.nFindCall == 1 );
 309
 310                 CPPUNIT_ASSERT( l.unlink( v2 ) );
 311                 CPPUNIT_ASSERT( l.contains( v1.key() )) ;   // true
 312                 CPPUNIT_ASSERT( !l.contains( v2.key() )) ;   // true
 313                 CPPUNIT_ASSERT( l.contains( v3.key() )) ;   // true
 314                 CPPUNIT_ASSERT( !l.empty() );
 315                 CPPUNIT_ASSERT( !l.unlink( v2 ) );
 316
 317                 {
 318                     // v1 key is in the list but v NODE is not in the list
 319                     value_type v( v1 );
 320                     CPPUNIT_ASSERT( !l.unlink( v ) );
 321                 }
 322
 323                 CPPUNIT_ASSERT( l.unlink( v1 ) );
 324                 CPPUNIT_ASSERT( !l.unlink( v1 ) );
 325                 CPPUNIT_ASSERT( !l.contains( v1.key() ));
 326                 CPPUNIT_ASSERT( !l.contains( v2.key() ));
 327                 CPPUNIT_ASSERT( l.contains( v3.key() ));
 328                 CPPUNIT_ASSERT( !l.empty() );
 329                 CPPUNIT_ASSERT( !l.unlink( v1 ) );
 330                 CPPUNIT_ASSERT( !l.unlink( v2 ) );
 331
 332                 CPPUNIT_ASSERT( l.unlink( v3 ) );
 333                 CPPUNIT_ASSERT( !l.contains( v1.key() ));
 334                 CPPUNIT_ASSERT( !l.contains( v2.key(), less<value_type>() ));
 335                 CPPUNIT_ASSERT( !l.contains( v3.key() ));
 336                 CPPUNIT_ASSERT( l.empty() );
 337                 CPPUNIT_ASSERT( !l.unlink( v1 ) );
 338                 CPPUNIT_ASSERT( !l.unlink( v2 ) );
 339                 CPPUNIT_ASSERT( !l.unlink( v3 ) );
 340
 341                 // Apply retired pointer to clean links
 342                 OrdList::gc::force_dispose();
 343
 344                 stat s( v3.s );
 345                 ret = l.update( v3, update_functor() );
 346                 CPPUNIT_ASSERT( ret.first );
 347                 CPPUNIT_ASSERT( ret.second );
 348                 CPPUNIT_ASSERT( v3.s.nUpdateNewCall == s.nUpdateNewCall + 1);
 349                 CPPUNIT_ASSERT( v3.s.nUpdateExistsCall == s.nUpdateExistsCall );
 350                 CPPUNIT_ASSERT( !l.empty() );
 351
 352                 s = v2.s;
 353                 ret = l.update( v2, update_functor() );
 354                 CPPUNIT_ASSERT( ret.first );
 355                 CPPUNIT_ASSERT( ret.second );
 356                 CPPUNIT_ASSERT( v2.s.nUpdateNewCall == s.nUpdateNewCall + 1);
 357                 CPPUNIT_ASSERT( v2.s.nUpdateExistsCall == s.nUpdateExistsCall );
 358                 CPPUNIT_ASSERT( !l.empty() );
 359
 360                 s = v1.s;
 361                 ret = l.update( v1, update_functor() );
 362                 CPPUNIT_ASSERT( ret.first );
 363                 CPPUNIT_ASSERT( ret.second );
 364                 CPPUNIT_ASSERT( v1.s.nUpdateNewCall == s.nUpdateNewCall + 1);
 365                 CPPUNIT_ASSERT( v1.s.nUpdateExistsCall == s.nUpdateExistsCall );
 366                 CPPUNIT_ASSERT( !l.empty() );
 367
 368                 // Erase test
 369                 CPPUNIT_ASSERT( l.erase( v1.key()) );
 370                 //CPPUNIT_ASSERT( v1.s.nDisposeCount == 0 );
 371                 CPPUNIT_ASSERT( !l.empty() );
 372
 373                 CPPUNIT_ASSERT( v2.s.nEraseCall == 0 );
 374                 CPPUNIT_ASSERT( l.erase_with( v2.key(), less<value_type>(), erase_functor()) );
 375                 CPPUNIT_ASSERT( v2.s.nEraseCall == 1 );
 376                 CPPUNIT_ASSERT( !l.erase_with( v2.key(), less<value_type>()));
 377                 CPPUNIT_ASSERT( v2.s.nEraseCall == 1 );
 378                 //CPPUNIT_ASSERT( v2.s.nDisposeCount == 0 );
 379                 CPPUNIT_ASSERT( !l.empty() );
 380
 381                 CPPUNIT_ASSERT( !l.erase( v2 ));
 382                 CPPUNIT_ASSERT( !l.erase( v1 ));
 383                 //CPPUNIT_ASSERT( v2.s.nDisposeCount == 0 );
 384                 CPPUNIT_ASSERT( !l.empty() );
 385
 386                 CPPUNIT_ASSERT( v3.s.nEraseCall == 0 );
 387                 CPPUNIT_ASSERT( l.erase( v3, erase_functor() ));
 388                 CPPUNIT_ASSERT( v3.s.nEraseCall == 1 );
 389                 //CPPUNIT_ASSERT( v3.s.nDisposeCount == 0 );
 390                 CPPUNIT_ASSERT( l.empty() );
 391
 392                 // Apply retired pointer to clean links
 393                 OrdList::gc::force_dispose();
 394
 395                 // Unlink test
 396                 CPPUNIT_ASSERT( l.insert( v1 ));
 397                 CPPUNIT_ASSERT( l.insert( v3 ));
 398                 CPPUNIT_ASSERT( !l.empty() );
 399                 CPPUNIT_ASSERT( !l.unlink( v2 ));
 400                 CPPUNIT_ASSERT( l.unlink( v1 ));
 401                 CPPUNIT_ASSERT( !l.unlink( v1 ));
 402                 CPPUNIT_ASSERT( l.unlink( v3 ));
 403                 CPPUNIT_ASSERT( !l.unlink( v3 ));
 404                 CPPUNIT_ASSERT( l.empty() );
 405
 406                 // Apply retired pointer
 407                 OrdList::gc::force_dispose();
 408                 CPPUNIT_ASSERT( v1.s.nDisposeCount == 3 );
 409                 CPPUNIT_ASSERT( v2.s.nDisposeCount == 2 );
 410                 CPPUNIT_ASSERT( v3.s.nDisposeCount == 3 );
 411
 412                 // Destructor test (call disposer)
 413                 CPPUNIT_ASSERT( l.insert( v1 ));
 414                 CPPUNIT_ASSERT( l.insert( v3 ));
 415                 CPPUNIT_ASSERT( l.insert( v2 ));
 416
 417                 // Iterator test
 418                 {
 419                     typename OrdList::iterator it = l.begin();
 420                     typename OrdList::const_iterator cit = l.cbegin();
 421                     CPPUNIT_ASSERT( it != l.end() );
 422                     CPPUNIT_ASSERT( it != l.cend() );
 423                     CPPUNIT_ASSERT( cit != l.end() );
 424                     CPPUNIT_ASSERT( cit != l.cend() );
 425                     CPPUNIT_ASSERT( cit == it );
 426
 427                     CPPUNIT_ASSERT( it->nKey == v2.nKey );
 428                     CPPUNIT_ASSERT( it->nVal == v2.nVal );
 429                     CPPUNIT_ASSERT( ++it != l.end() );
 430                     CPPUNIT_ASSERT( it->nKey == v1.nKey );
 431                     CPPUNIT_ASSERT( it->nVal == v1.nVal );
 432                     CPPUNIT_ASSERT( ++it != l.end() );
 433                     CPPUNIT_ASSERT( it->nKey == v3.nKey );
 434                     CPPUNIT_ASSERT( it->nVal == v3.nVal );
 435                     CPPUNIT_ASSERT( ++it == l.end() );
 436                 }
 437
 438                 {
 439                     OrdList const & lref = l;
 440                     typename OrdList::const_iterator it = lref.begin();
 441                     CPPUNIT_ASSERT( it != l.end() );
 442                     CPPUNIT_ASSERT( it->nKey == v2.nKey );
 443                     CPPUNIT_ASSERT( it->nVal == v2.nVal );
 444                     CPPUNIT_ASSERT( ++it != lref.end() );
 445                     CPPUNIT_ASSERT( it->nKey == v1.nKey );
 446                     CPPUNIT_ASSERT( it->nVal == v1.nVal );
 447                     CPPUNIT_ASSERT( ++it != l.end() );
 448                     CPPUNIT_ASSERT( it->nKey == v3.nKey );
 449                     CPPUNIT_ASSERT( it->nVal == v3.nVal );
 450                     CPPUNIT_ASSERT( ++it == l.end() );
 451                 }
 452             }
 453
 454             // Apply retired pointer
 455             OrdList::gc::force_dispose();
 456
 457             CPPUNIT_ASSERT( v1.s.nDisposeCount == 4 );
 458             CPPUNIT_ASSERT( v2.s.nDisposeCount == 3 );
 459             CPPUNIT_ASSERT( v3.s.nDisposeCount == 4 );
 460         }
 461
 462         template <class OrdList>
 463         void test_int()
 464         {
 465             test_int_common<OrdList>();
 466
 467             OrdList l;
 468             typename OrdList::guarded_ptr gp;
 469
 470             static int const nLimit = 20;
 471             typename OrdList::value_type arrItem[nLimit];
 472
 473             {
 474                 int a[nLimit];
 475                 for (int i = 0; i < nLimit; ++i)
 476                     a[i]=i;
 477                 shuffle( a, a + nLimit );
 478
 479                 for (int i = 0; i < nLimit; ++i) {
 480                     arrItem[i].nKey = a[i];
 481                     arrItem[i].nVal = a[i] * 2;
 482                 }
 483
 484                 // extract/get
 485                 for ( int i = 0; i < nLimit; ++i )
 486                     CPPUNIT_ASSERT( l.insert( arrItem[i] ) );
 487
 488                 for ( int i=0; i < nLimit; ++i ) {
 489                     gp = l.get( arrItem[i].nKey );
 490                     CPPUNIT_ASSERT( gp );
 491                     CPPUNIT_ASSERT( !gp.empty());
 492                     CPPUNIT_ASSERT( gp->nKey == arrItem[i].nKey );
 493                     CPPUNIT_ASSERT( gp->nVal == arrItem[i].nVal );
 494
 495                     gp = l.extract( arrItem[i].nKey );
 496                     CPPUNIT_ASSERT( gp );
 497                     CPPUNIT_ASSERT( !gp.empty());
 498                     CPPUNIT_ASSERT( gp->nKey == arrItem[i].nKey );
 499                     CPPUNIT_ASSERT( gp->nVal == arrItem[i].nVal );
 500
 501                     gp = l.get( arrItem[i].nKey );
 502                     CPPUNIT_ASSERT( !gp );
 503                     CPPUNIT_ASSERT( gp.empty());
 504                     CPPUNIT_ASSERT( !l.extract( arrItem[i].nKey ));
 505                     CPPUNIT_ASSERT( gp.empty());
 506                 }
 507                 CPPUNIT_ASSERT( l.empty() );
 508                 CPPUNIT_ASSERT( !l.get( nLimit/2 ));
 509                 CPPUNIT_ASSERT( !l.extract( nLimit/2 ));
 510
 511                 // Apply retired pointer
 512                 OrdList::gc::force_dispose();
 513
 514                 // extract_with/get_with
 515                 for ( int i = 0; i < nLimit; ++i )
 516                     CPPUNIT_ASSERT( l.insert( arrItem[i] ) );
 517
 518                 for ( int i=0; i < nLimit; ++i ) {
 519                     other_item itm( arrItem[i].nKey );
 520                     gp = l.get_with( itm, other_less() );
 521                     CPPUNIT_ASSERT( gp );
 522                     CPPUNIT_ASSERT( !gp.empty());
 523                     CPPUNIT_ASSERT( gp->nKey == arrItem[i].nKey );
 524                     CPPUNIT_ASSERT( gp->nVal == arrItem[i].nVal );
 525
 526                     gp = l.extract_with( itm, other_less() );
 527                     CPPUNIT_ASSERT( gp );
 528                     CPPUNIT_ASSERT( !gp.empty());
 529                     CPPUNIT_ASSERT( gp->nKey == arrItem[i].nKey );
 530                     CPPUNIT_ASSERT( gp->nVal == arrItem[i].nVal );
 531
 532                     gp = l.get_with( itm, other_less() );
 533                     CPPUNIT_ASSERT( !gp );
 534                     CPPUNIT_ASSERT( gp.empty());
 535                     CPPUNIT_ASSERT( !l.extract_with( itm, other_less() ));
 536                     CPPUNIT_ASSERT( gp.empty());
 537                 }
 538                 CPPUNIT_ASSERT( l.empty() );
 539                 CPPUNIT_ASSERT( !l.get_with( other_item(nLimit/2), other_less() ));
 540                 CPPUNIT_ASSERT( gp.empty());
 541                 CPPUNIT_ASSERT( !l.extract_with( other_item(nLimit/2), other_less() ));
 542                 CPPUNIT_ASSERT( gp.empty());
 543
 544                 // Apply retired pointer
 545                 OrdList::gc::force_dispose();
 546
 547                 for ( int i=0; i < nLimit; i++ ) {
 548                     CPPUNIT_ASSERT( arrItem[i].s.nDisposeCount == 2 );
 549                 }
 550             }
 551         }
 552
 553         template <class OrdList>
 554         void test_rcu_int()
 555         {
 556             test_int_common<OrdList>();
 557
 558             OrdList l;
 559             static int const nLimit = 20;
 560             typename OrdList::value_type arrItem[nLimit];
 561
 562             typedef typename OrdList::rcu_lock rcu_lock;
 563             typedef typename OrdList::value_type value_type;
 564             typedef typename OrdList::gc rcu_type;
 565
 566             {
 567                 int a[nLimit];
 568                 for (int i = 0; i < nLimit; ++i)
 569                     a[i]=i;
 570                 shuffle( a, a + nLimit );
 571
 572                 for (int i = 0; i < nLimit; ++i) {
 573                     arrItem[i].nKey = a[i];
 574                     arrItem[i].nVal = a[i] * 2;
 575                 }
 576
 577                 typename OrdList::exempt_ptr ep;
 578
 579                 // extract/get
 580                 for ( int i = 0; i < nLimit; ++i )
 581                     CPPUNIT_ASSERT( l.insert( arrItem[i] ) );
 582
 583                 for ( int i = 0; i < nLimit; ++i ) {
 584                     {
 585                         rcu_lock lock;
 586                         value_type * pGet = l.get( a[i] );
 587                         CPPUNIT_ASSERT( pGet != nullptr );
 588                         CPPUNIT_CHECK( pGet->nKey == a[i] );
 589                         CPPUNIT_CHECK( pGet->nVal == a[i] * 2 );
 590
 591                         ep = l.extract( a[i] );
 592                         CPPUNIT_ASSERT( ep );
 593                         CPPUNIT_ASSERT( !ep.empty() );
 594                         CPPUNIT_CHECK( ep->nKey == a[i] );
 595                         CPPUNIT_CHECK( (*ep).nVal == a[i] * 2 );
 596                     }
 597                     ep.release();
 598                     {
 599                         rcu_lock lock;
 600                         CPPUNIT_CHECK( l.get( a[i] ) == nullptr );
 601                         CPPUNIT_CHECK( !l.extract( a[i] ) );
 602                         CPPUNIT_CHECK( ep.empty() );
 603                     }
 604                 }
 605                 CPPUNIT_ASSERT( l.empty() );
 606
 607                 {
 608                     rcu_lock lock;
 609                     CPPUNIT_CHECK( l.get( a[0] ) == nullptr );
 610                     ep = l.extract( a[0] );
 611                     CPPUNIT_CHECK( !ep );
 612                     CPPUNIT_CHECK( ep.empty() );
 613                 }
 614                 // Apply retired pointer
 615                 OrdList::gc::force_dispose();
 616
 617                 // extract_with/get_with
 618                 for ( int i = 0; i < nLimit; ++i ) {
 619                     CPPUNIT_ASSERT( l.insert( arrItem[i] ) );
 620                 }
 621
 622                 for ( int i = 0; i < nLimit; ++i ) {
 623                     other_item itm( a[i] );
 624                     {
 625                         rcu_lock lock;
 626                         value_type * pGet = l.get_with( itm, other_less() );
 627                         CPPUNIT_ASSERT( pGet != nullptr );
 628                         CPPUNIT_CHECK( pGet->nKey == a[i] );
 629                         CPPUNIT_CHECK( pGet->nVal == a[i] * 2 );
 630
 631                         ep = l.extract_with( itm, other_less() );
 632                         CPPUNIT_ASSERT( ep );
 633                         CPPUNIT_ASSERT( !ep.empty() );
 634                         CPPUNIT_CHECK( ep->nKey == a[i] );
 635                         CPPUNIT_CHECK( ep->nVal == a[i] * 2 );
 636                     }
 637                     ep.release();
 638                     {
 639                         rcu_lock lock;
 640                         CPPUNIT_CHECK( l.get_with( itm, other_less() ) == nullptr );
 641                         ep = l.extract_with( itm, other_less() );
 642                         CPPUNIT_CHECK( !ep );
 643                         CPPUNIT_CHECK( ep.empty() );
 644                     }
 645                 }
 646                 CPPUNIT_ASSERT( l.empty() );
 647
 648                 {
 649                     rcu_lock lock;
 650                     CPPUNIT_CHECK( l.get_with( other_item( 0 ), other_less() ) == nullptr );
 651                     CPPUNIT_CHECK( !l.extract_with( other_item(0), other_less() ));
 652                     CPPUNIT_CHECK( ep.empty() );
 653                 }
 654                 // Apply retired pointer
 655                 OrdList::gc::force_dispose();
 656             }
 657         }
 658
 659         template <class OrdList>
 660         void test_nogc_int()
 661         {
 662             typedef typename OrdList::value_type    value_type;
 663
 664             {
 665                 value_type v1( 10, 50 );
 666                 value_type v2( 5, 25  );
 667                 value_type v3( 20, 100 );
 668                 {
 669                     OrdList l;
 670                     CPPUNIT_ASSERT( l.empty() );
 671
 672                     CPPUNIT_ASSERT( l.insert( v1 ))     ;   // true
 673                     CPPUNIT_ASSERT( l.contains( v1.key() ) == &v1 );
 674
 675                     CPPUNIT_ASSERT( v1.s.nFindCall == 0 );
 676                     CPPUNIT_ASSERT( l.find( v1.key(), find_functor() ));
 677                     CPPUNIT_ASSERT( v1.s.nFindCall == 1 );
 678
 679                     CPPUNIT_ASSERT( l.contains( v2.key(), less<value_type>() ) == nullptr );
 680                     CPPUNIT_ASSERT( l.contains( v3.key() ) == nullptr );
 681                     CPPUNIT_ASSERT( !l.empty() );
 682
 683                     //CPPUNIT_ASSERT( !l.insert( v1 ))    ;   // assertion "is_empty" is raised
 684
 685                     {
 686                         value_type v( v1 );
 687                         CPPUNIT_ASSERT( !l.insert( v )) ;   // false
 688                     }
 689
 690                     std::pair<bool, bool> ret = l.update( v2, update_functor() );
 691                     CPPUNIT_ASSERT( ret.first );
 692                     CPPUNIT_ASSERT( ret.second );
 693                     CPPUNIT_ASSERT( v2.s.nUpdateNewCall == 1 );
 694                     CPPUNIT_ASSERT( v2.s.nUpdateExistsCall == 0 );
 695
 696                     //CPPUNIT_ASSERT( !l.insert( v2 ))    ;   // assertion "is_empty"
 697
 698                     CPPUNIT_ASSERT( l.contains( v1.key() ) == &v1 ) ;   // true
 699
 700                     CPPUNIT_ASSERT( v1.s.nFindCall == 1 );
 701                     CPPUNIT_ASSERT( l.find( v1.key(), find_functor() ));
 702                     CPPUNIT_ASSERT( v1.s.nFindCall == 2 );
 703
 704                     CPPUNIT_ASSERT( l.contains( v2.key(), less<value_type>() ) == &v2 );
 705
 706                     CPPUNIT_ASSERT( v2.s.nFindCall == 0 );
 707                     CPPUNIT_ASSERT( l.find_with( v2.key(), less<value_type>(), find_functor() ));
 708                     CPPUNIT_ASSERT( v2.s.nFindCall == 1 );
 709
 710                     CPPUNIT_ASSERT( !l.contains( v3.key() ));
 711
 712                     {
 713                         value_type v( v2 );
 714                         ret = l.update( v, update_functor() );
 715
 716                         CPPUNIT_ASSERT( ret.first );
 717                         CPPUNIT_ASSERT( !ret.second );
 718                         CPPUNIT_ASSERT( v2.s.nUpdateExistsCall == 1 );
 719                         CPPUNIT_ASSERT( v.s.nUpdateExistsCall == 0 && v.s.nUpdateNewCall == 0 );
 720                     }
 721
 722                     CPPUNIT_ASSERT( !l.empty() );
 723
 724                     CPPUNIT_ASSERT( l.insert( v3 ))     ;   // true
 725                     CPPUNIT_ASSERT( l.contains( v3.key() ) == &v3 );
 726
 727                     CPPUNIT_ASSERT( v3.s.nFindCall == 0 );
 728                     CPPUNIT_ASSERT( l.find( v3.key(), find_functor() ));
 729                     CPPUNIT_ASSERT( v3.s.nFindCall == 1 );
 730
 731                     {
 732                         typename OrdList::iterator it = l.begin();
 733                         typename OrdList::const_iterator cit = l.cbegin();
 734                         CPPUNIT_ASSERT( it != l.end() );
 735                         CPPUNIT_ASSERT( it != l.cend() );
 736                         CPPUNIT_ASSERT( cit != l.end() );
 737                         CPPUNIT_ASSERT( cit != l.cend() );
 738                         CPPUNIT_ASSERT( cit == it );
 739
 740                         CPPUNIT_ASSERT( it->nKey == v2.nKey );
 741                         CPPUNIT_ASSERT( it->nVal == v2.nVal );
 742                         CPPUNIT_ASSERT( ++it != l.end() );
 743                         CPPUNIT_ASSERT( it->nKey == v1.nKey );
 744                         CPPUNIT_ASSERT( it->nVal == v1.nVal );
 745                         CPPUNIT_ASSERT( it++ != l.end() );
 746                         CPPUNIT_ASSERT( it->nKey == v3.nKey );
 747                         CPPUNIT_ASSERT( it->nVal == v3.nVal );
 748                         CPPUNIT_ASSERT( it++ != l.end() );
 749                         CPPUNIT_ASSERT( it == l.end() );
 750                     }
 751
 752                     {
 753                         OrdList const & lref = l;
 754                         typename OrdList::const_iterator it = lref.begin();
 755                         CPPUNIT_ASSERT( it != l.end() );
 756                         CPPUNIT_ASSERT( it->nKey == v2.nKey );
 757                         CPPUNIT_ASSERT( it->nVal == v2.nVal );
 758                         CPPUNIT_ASSERT( ++it != lref.end() );
 759                         CPPUNIT_ASSERT( it->nKey == v1.nKey );
 760                         CPPUNIT_ASSERT( it->nVal == v1.nVal );
 761                         CPPUNIT_ASSERT( it++ != l.end() );
 762                         CPPUNIT_ASSERT( it->nKey == v3.nKey );
 763                         CPPUNIT_ASSERT( it->nVal == v3.nVal );
 764                         CPPUNIT_ASSERT( it++ != lref.end() );
 765                         CPPUNIT_ASSERT( it == l.end() );
 766                     }
 767                 }
 768
 769                 // Disposer called on list destruction
 770                 CPPUNIT_ASSERT( v1.s.nDisposeCount == 1 );
 771                 CPPUNIT_ASSERT( v2.s.nDisposeCount == 1 );
 772                 CPPUNIT_ASSERT( v3.s.nDisposeCount == 1 );
 773             }
 774         }
 775
 776         template <class UnordList>
 777         void test_nogc_int_unordered()
 778         {
 779             typedef typename UnordList::value_type    value_type;
 780             {
 781                 value_type v1( 10, 50 );
 782                 value_type v2( 5, 25  );
 783                 value_type v3( 20, 100 );
 784                 {
 785                     UnordList l;
 786                     CPPUNIT_ASSERT( l.empty() );
 787
 788                     CPPUNIT_ASSERT( l.insert( v1 ));   // true
 789                     CPPUNIT_ASSERT( l.contains( v1.key() ) == &v1 );
 790
 791                     CPPUNIT_ASSERT( v1.s.nFindCall == 0 );
 792                     CPPUNIT_ASSERT( l.find( v1.key(), find_functor() ));
 793                     CPPUNIT_ASSERT( v1.s.nFindCall == 1 );
 794
 795                     CPPUNIT_ASSERT( l.contains( v2.key(), equal_to<value_type>() ) == nullptr );
 796                     CPPUNIT_ASSERT( l.contains( v3.key() ) == nullptr );
 797                     CPPUNIT_ASSERT( !l.empty() );
 798
 799                     //CPPUNIT_ASSERT( !l.insert( v1 ))    ;   // assertion "is_empty" is raised
 800
 801                     {
 802                         value_type v( v1 );
 803                         CPPUNIT_ASSERT( !l.insert( v )) ;   // false
 804                     }
 805
 806                     std::pair<bool, bool> ret = l.update( v2, update_functor() );
 807                     CPPUNIT_ASSERT( ret.first );
 808                     CPPUNIT_ASSERT( ret.second );
 809                     CPPUNIT_ASSERT( v2.s.nUpdateNewCall == 1 );
 810                     CPPUNIT_ASSERT( v2.s.nUpdateExistsCall == 0 );
 811
 812                     //CPPUNIT_ASSERT( !l.insert( v2 ))    ;   // assertion "is_empty"
 813
 814                     CPPUNIT_ASSERT( l.contains( v1.key() ) == &v1 ) ;   // true
 815
 816                     CPPUNIT_ASSERT( v1.s.nFindCall == 1 );
 817                     CPPUNIT_ASSERT( l.find( v1.key(), find_functor() ));
 818                     CPPUNIT_ASSERT( v1.s.nFindCall == 2 );
 819
 820                     CPPUNIT_ASSERT( l.contains( v2.key(), equal_to<value_type>() ) == &v2 );
 821
 822                     CPPUNIT_ASSERT( v2.s.nFindCall == 0 );
 823                     CPPUNIT_ASSERT( l.find_with( v2.key(), equal_to<value_type>(), find_functor() ));
 824                     CPPUNIT_ASSERT( v2.s.nFindCall == 1 );
 825
 826                     CPPUNIT_ASSERT( !l.contains( v3.key() ));
 827
 828                     {
 829                         value_type v( v2 );
 830                         ret = l.update( v, update_functor() );
 831
 832                         CPPUNIT_ASSERT( ret.first );
 833                         CPPUNIT_ASSERT( !ret.second );
 834                         CPPUNIT_ASSERT( v2.s.nUpdateExistsCall == 1 );
 835                         CPPUNIT_ASSERT( v.s.nUpdateExistsCall == 0 && v.s.nUpdateNewCall == 0 );
 836                     }
 837
 838                     CPPUNIT_ASSERT( !l.empty() );
 839
 840                     CPPUNIT_ASSERT( l.insert( v3 ))     ;   // true
 841                     CPPUNIT_ASSERT( l.contains( v3.key() ) == &v3 );
 842
 843                     CPPUNIT_ASSERT( v3.s.nFindCall == 0 );
 844                     CPPUNIT_ASSERT( l.find( v3.key(), find_functor() ));
 845                     CPPUNIT_ASSERT( v3.s.nFindCall == 1 );
 846
 847                     {
 848                         typename UnordList::iterator it = l.begin();
 849                         typename UnordList::const_iterator cit = l.cbegin();
 850                         CPPUNIT_ASSERT( it != l.end() );
 851                         CPPUNIT_ASSERT( it != l.cend() );
 852                         CPPUNIT_ASSERT( cit != l.end() );
 853                         CPPUNIT_ASSERT( cit != l.cend() );
 854                         CPPUNIT_ASSERT( cit == it );
 855
 856                         CPPUNIT_ASSERT( it->nKey == v1.nKey );
 857                         CPPUNIT_ASSERT( it->nVal == v1.nVal );
 858                         CPPUNIT_ASSERT( ++it != l.end() );
 859                         CPPUNIT_ASSERT( it->nKey == v2.nKey );
 860                         CPPUNIT_ASSERT( it->nVal == v2.nVal );
 861                         CPPUNIT_ASSERT( it++ != l.end() );
 862                         CPPUNIT_ASSERT( it->nKey == v3.nKey );
 863                         CPPUNIT_ASSERT( it->nVal == v3.nVal );
 864                         CPPUNIT_ASSERT( it++ != l.end() );
 865                         CPPUNIT_ASSERT( it == l.end() );
 866                     }
 867
 868                     {
 869                         UnordList const & lref = l;
 870                         typename UnordList::const_iterator it = lref.begin();
 871                         CPPUNIT_ASSERT( it != l.end() );
 872                         CPPUNIT_ASSERT( it->nKey == v1.nKey );
 873                         CPPUNIT_ASSERT( it->nVal == v1.nVal );
 874                         CPPUNIT_ASSERT( ++it != lref.end() );
 875                         CPPUNIT_ASSERT( it->nKey == v2.nKey );
 876                         CPPUNIT_ASSERT( it->nVal == v2.nVal );
 877                         CPPUNIT_ASSERT( it++ != l.end() );
 878                         CPPUNIT_ASSERT( it->nKey == v3.nKey );
 879                         CPPUNIT_ASSERT( it->nVal == v3.nVal );
 880                         CPPUNIT_ASSERT( it++ != lref.end() );
 881                         CPPUNIT_ASSERT( it == l.end() );
 882                     }
 883                 }
 884
 885                 // Disposer called on list destruction
 886                 CPPUNIT_ASSERT( v1.s.nDisposeCount == 1 );
 887                 CPPUNIT_ASSERT( v2.s.nDisposeCount == 1 );
 888                 CPPUNIT_ASSERT( v3.s.nDisposeCount == 1 );
 889             }
 890         }
 891
 892
 893         void HP_base_cmp();
 894         void HP_base_less();
 895         void HP_base_cmpmix();
 896         void HP_base_ic();
 897         void HP_member_cmp();
 898         void HP_member_less();
 899         void HP_member_cmpmix();
 900         void HP_member_ic();
 901
 902         void DHP_base_cmp();
 903         void DHP_base_less();
 904         void DHP_base_cmpmix();
 905         void DHP_base_ic();
 906         void DHP_member_cmp();
 907         void DHP_member_less();
 908         void DHP_member_cmpmix();
 909         void DHP_member_ic();
 910
 911         void RCU_GPI_base_cmp();
 912         void RCU_GPI_base_less();
 913         void RCU_GPI_base_cmpmix();
 914         void RCU_GPI_base_ic();
 915         void RCU_GPI_member_cmp();
 916         void RCU_GPI_member_less();
 917         void RCU_GPI_member_cmpmix();
 918         void RCU_GPI_member_ic();
 919
 920         void RCU_GPB_base_cmp();
 921         void RCU_GPB_base_less();
 922         void RCU_GPB_base_cmpmix();
 923         void RCU_GPB_base_ic();
 924         void RCU_GPB_member_cmp();
 925         void RCU_GPB_member_less();
 926         void RCU_GPB_member_cmpmix();
 927         void RCU_GPB_member_ic();
 928
 929         void RCU_GPT_base_cmp();
 930         void RCU_GPT_base_less();
 931         void RCU_GPT_base_cmpmix();
 932         void RCU_GPT_base_ic();
 933         void RCU_GPT_member_cmp();
 934         void RCU_GPT_member_less();
 935         void RCU_GPT_member_cmpmix();
 936         void RCU_GPT_member_ic();
 937
 938         void RCU_SHB_base_cmp();
 939         void RCU_SHB_base_less();
 940         void RCU_SHB_base_cmpmix();
 941         void RCU_SHB_base_ic();
 942         void RCU_SHB_member_cmp();
 943         void RCU_SHB_member_less();
 944         void RCU_SHB_member_cmpmix();
 945         void RCU_SHB_member_ic();
 946
 947         void RCU_SHT_base_cmp();
 948         void RCU_SHT_base_less();
 949         void RCU_SHT_base_cmpmix();
 950         void RCU_SHT_base_ic();
 951         void RCU_SHT_member_cmp();
 952         void RCU_SHT_member_less();
 953         void RCU_SHT_member_cmpmix();
 954         void RCU_SHT_member_ic();
 955
 956         void nogc_base_cmp();
 957         void nogc_base_less();
 958         void nogc_base_cmpmix();
 959         void nogc_base_ic();
 960         void nogc_member_cmp();
 961         void nogc_member_less();
 962         void nogc_member_cmpmix();
 963         void nogc_member_ic();
 964
 965         void nogc_base_cmp_unord();
 966         void nogc_base_less_unord();
 967         void nogc_base_equal_to_unord();
 968         void nogc_base_cmpmix_unord();
 969         void nogc_base_equal_to_mix_unord();
 970         void nogc_base_ic_unord();
 971         void nogc_member_cmp_unord();
 972         void nogc_member_less_unord();
 973         void nogc_member_equal_to_unord();
 974         void nogc_member_cmpmix_unord();
 975         void nogc_member_equal_to_mix_unord();
 976         void nogc_member_ic_unord();
 977
 978         CPPUNIT_TEST_SUITE(IntrusiveLazyListHeaderTest)
 979             CPPUNIT_TEST(HP_base_cmp)
 980             CPPUNIT_TEST(HP_base_less)
 981             CPPUNIT_TEST(HP_base_cmpmix)
 982             CPPUNIT_TEST(HP_base_ic)
 983             CPPUNIT_TEST(HP_member_cmp)
 984             CPPUNIT_TEST(HP_member_less)
 985             CPPUNIT_TEST(HP_member_cmpmix)
 986             CPPUNIT_TEST(HP_member_ic)
 987
 988             CPPUNIT_TEST(DHP_base_cmp)
 989             CPPUNIT_TEST(DHP_base_less)
 990             CPPUNIT_TEST(DHP_base_cmpmix)
 991             CPPUNIT_TEST(DHP_base_ic)
 992             CPPUNIT_TEST(DHP_member_cmp)
 993             CPPUNIT_TEST(DHP_member_less)
 994             CPPUNIT_TEST(DHP_member_cmpmix)
 995             CPPUNIT_TEST(DHP_member_ic)
 996
 997             CPPUNIT_TEST(RCU_GPI_base_cmp)
 998             CPPUNIT_TEST(RCU_GPI_base_less)
 999             CPPUNIT_TEST(RCU_GPI_base_cmpmix)
1000             CPPUNIT_TEST(RCU_GPI_base_ic)
1001             CPPUNIT_TEST(RCU_GPI_member_cmp)
1002             CPPUNIT_TEST(RCU_GPI_member_less)
1003             CPPUNIT_TEST(RCU_GPI_member_cmpmix)
1004             CPPUNIT_TEST(RCU_GPI_member_ic)
1005
1006             CPPUNIT_TEST(RCU_GPB_base_cmp)
1007             CPPUNIT_TEST(RCU_GPB_base_less)
1008             CPPUNIT_TEST(RCU_GPB_base_cmpmix)
1009             CPPUNIT_TEST(RCU_GPB_base_ic)
1010             CPPUNIT_TEST(RCU_GPB_member_cmp)
1011             CPPUNIT_TEST(RCU_GPB_member_less)
1012             CPPUNIT_TEST(RCU_GPB_member_cmpmix)
1013             CPPUNIT_TEST(RCU_GPB_member_ic)
1014
1015             CPPUNIT_TEST(RCU_GPT_base_cmp)
1016             CPPUNIT_TEST(RCU_GPT_base_less)
1017             CPPUNIT_TEST(RCU_GPT_base_cmpmix)
1018             CPPUNIT_TEST(RCU_GPT_base_ic)
1019             CPPUNIT_TEST(RCU_GPT_member_cmp)
1020             CPPUNIT_TEST(RCU_GPT_member_less)
1021             CPPUNIT_TEST(RCU_GPT_member_cmpmix)
1022             CPPUNIT_TEST(RCU_GPT_member_ic)
1023
1024             CPPUNIT_TEST(RCU_SHB_base_cmp)
1025             CPPUNIT_TEST(RCU_SHB_base_less)
1026             CPPUNIT_TEST(RCU_SHB_base_cmpmix)
1027             CPPUNIT_TEST(RCU_SHB_base_ic)
1028             CPPUNIT_TEST(RCU_SHB_member_cmp)
1029             CPPUNIT_TEST(RCU_SHB_member_less)
1030             CPPUNIT_TEST(RCU_SHB_member_cmpmix)
1031             CPPUNIT_TEST(RCU_SHB_member_ic)
1032
1033             CPPUNIT_TEST(RCU_SHT_base_cmp)
1034             CPPUNIT_TEST(RCU_SHT_base_less)
1035             CPPUNIT_TEST(RCU_SHT_base_cmpmix)
1036             CPPUNIT_TEST(RCU_SHT_base_ic)
1037             CPPUNIT_TEST(RCU_SHT_member_cmp)
1038             CPPUNIT_TEST(RCU_SHT_member_less)
1039             CPPUNIT_TEST(RCU_SHT_member_cmpmix)
1040             CPPUNIT_TEST(RCU_SHT_member_ic)
1041
1042             CPPUNIT_TEST(nogc_base_cmp)
1043             CPPUNIT_TEST(nogc_base_less)
1044             CPPUNIT_TEST(nogc_base_cmpmix)
1045             CPPUNIT_TEST(nogc_base_ic)
1046             CPPUNIT_TEST(nogc_member_cmp)
1047             CPPUNIT_TEST(nogc_member_less)
1048             CPPUNIT_TEST(nogc_member_cmpmix)
1049             CPPUNIT_TEST(nogc_member_ic)
1050
1051             CPPUNIT_TEST(nogc_base_cmp_unord)
1052             CPPUNIT_TEST(nogc_base_less_unord)
1053             CPPUNIT_TEST(nogc_base_equal_to_unord)
1054             CPPUNIT_TEST(nogc_base_cmpmix_unord)
1055             CPPUNIT_TEST(nogc_base_equal_to_mix_unord)
1056             CPPUNIT_TEST(nogc_base_ic_unord)
1057             CPPUNIT_TEST(nogc_member_cmp_unord)
1058             CPPUNIT_TEST(nogc_member_less_unord)
1059             CPPUNIT_TEST(nogc_member_equal_to_unord)
1060             CPPUNIT_TEST(nogc_member_cmpmix_unord)
1061             CPPUNIT_TEST(nogc_member_equal_to_mix_unord)
1062             CPPUNIT_TEST(nogc_member_ic_unord)
1063
1064         CPPUNIT_TEST_SUITE_END()
1065     };
1066 }   // namespace ordlist
1067
1068 #endif // #ifndef CDSTEST_HDR_INTRUSIVE_LAZY_H