tests/test-hdr/ordered_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 nEnsureExistsCall;
  20             int nEnsureNewCall;
  21             int nFindCall;
  22             int nEraseCall;
  23
  24             stat()
  25                 : nDisposeCount(0)
  26                 , nEnsureExistsCall(0)
  27                 , nEnsureNewCall(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         struct other_item {
 152             int nKey;
 153
 154             other_item( int n )
 155                 : nKey(n)
 156             {}
 157         };
 158
 159         struct other_less {
 160             template <typename T, typename Q>
 161             bool operator()( T const& i1, Q const& i2) const
 162             {
 163                 return i1.nKey < i2.nKey;
 164             }
 165         };
 166
 167         struct faked_disposer
 168         {
 169             template <typename T>
 170             void operator ()( T * p )
 171             {
 172                 ++p->s.nDisposeCount;
 173             }
 174         };
 175
 176         struct ensure_functor
 177         {
 178             template <typename T>
 179             void operator ()(bool bNew, T& item, T& /*val*/ )
 180             {
 181                 if ( bNew )
 182                     ++item.s.nEnsureNewCall;
 183                 else
 184                     ++item.s.nEnsureExistsCall;
 185             }
 186         };
 187
 188         struct find_functor
 189         {
 190             template <typename T, typename Q>
 191             void operator ()( T& item, Q& /*val*/ )
 192             {
 193                 ++item.s.nFindCall;
 194             }
 195         };
 196
 197         struct erase_functor
 198         {
 199             template <typename T>
 200             void operator()( T const& item )
 201             {
 202                 item.s.nEraseCall++;
 203             }
 204         };
 205
 206         template <class OrdList>
 207         void test_int_common()
 208         {
 209             typedef typename OrdList::value_type    value_type;
 210
 211             value_type v1( 10, 50 );
 212             value_type v2( 5, 25  );
 213             value_type v3( 20, 100 );
 214             {
 215                 OrdList l;
 216                 CPPUNIT_ASSERT( l.empty() );
 217
 218                 CPPUNIT_ASSERT( l.insert( v1 ))     ;   // true
 219                 CPPUNIT_ASSERT( l.find( v1.key() ));
 220
 221                 CPPUNIT_ASSERT( v1.s.nFindCall == 0 );
 222                 CPPUNIT_ASSERT( l.find( v1.key(), find_functor() ));
 223                 CPPUNIT_ASSERT( v1.s.nFindCall == 1 );
 224
 225                 CPPUNIT_ASSERT( !l.find_with( v2.key(), less<value_type>() ));
 226                 CPPUNIT_ASSERT( !l.find( v3.key(), find_functor() ));
 227                 CPPUNIT_ASSERT( !l.empty() );
 228
 229                 //CPPUNIT_ASSERT( !l.insert( v1 ))    ;   // assertion "is_empty" is raised
 230
 231                 {
 232                     value_type v( v1 );
 233                     CPPUNIT_ASSERT( !l.insert( v )) ;   // false
 234                 }
 235
 236                 std::pair<bool, bool> ret = l.ensure( v2, ensure_functor() );
 237                 CPPUNIT_ASSERT( ret.first );
 238                 CPPUNIT_ASSERT( ret.second );
 239                 CPPUNIT_ASSERT( v2.s.nEnsureNewCall == 1 );
 240                 CPPUNIT_ASSERT( v2.s.nEnsureExistsCall == 0 );
 241
 242                 //CPPUNIT_ASSERT( !l.insert( v2 ))    ;   // assertion "is_empty"
 243
 244                 CPPUNIT_ASSERT( l.find( v1.key() )) ;   // true
 245
 246                 CPPUNIT_ASSERT( v1.s.nFindCall == 1 );
 247                 CPPUNIT_ASSERT( l.find( v1.key(), find_functor() ));
 248                 CPPUNIT_ASSERT( v1.s.nFindCall == 2 );
 249
 250                 CPPUNIT_ASSERT( l.find( v2.key() ));
 251
 252                 CPPUNIT_ASSERT( v2.s.nFindCall == 0 );
 253                 CPPUNIT_ASSERT( l.find_with( v2.key(), less<value_type>(), find_functor() ));
 254                 CPPUNIT_ASSERT( v2.s.nFindCall == 1 );
 255
 256                 CPPUNIT_ASSERT( !l.find( v3.key() ));
 257
 258                 {
 259                     CPPUNIT_ASSERT( v2.s.nEnsureExistsCall == 0 );
 260                     CPPUNIT_ASSERT( v2.s.nEnsureNewCall == 1 );
 261
 262                     value_type v( v2 );
 263                     ret = l.ensure( v, ensure_functor() );
 264
 265                     CPPUNIT_ASSERT( ret.first );
 266                     CPPUNIT_ASSERT( !ret.second );
 267                     CPPUNIT_ASSERT( v2.s.nEnsureExistsCall == 1 );
 268                     CPPUNIT_ASSERT( v2.s.nEnsureNewCall == 1 );
 269                     CPPUNIT_ASSERT( v.s.nEnsureExistsCall == 0 );
 270                     CPPUNIT_ASSERT( v.s.nEnsureNewCall == 0 );
 271                 }
 272
 273                 CPPUNIT_ASSERT( !l.empty() );
 274
 275                 CPPUNIT_ASSERT( l.insert( v3 ))     ;   // true
 276                 CPPUNIT_ASSERT( l.find( v3.key() ));
 277
 278                 CPPUNIT_ASSERT( v3.s.nFindCall == 0 );
 279                 CPPUNIT_ASSERT( l.find( v3.key(), find_functor() ));
 280                 CPPUNIT_ASSERT( v3.s.nFindCall == 1 );
 281
 282                 CPPUNIT_ASSERT( l.unlink( v2 ) );
 283                 CPPUNIT_ASSERT( l.find( v1.key() )) ;   // true
 284                 CPPUNIT_ASSERT( !l.find( v2.key() )) ;   // true
 285                 CPPUNIT_ASSERT( l.find( v3.key() )) ;   // true
 286                 CPPUNIT_ASSERT( !l.empty() );
 287                 CPPUNIT_ASSERT( !l.unlink( v2 ) );
 288
 289                 {
 290                     // v1 key is in the list but v NODE is not in the list
 291                     value_type v( v1 );
 292                     CPPUNIT_ASSERT( !l.unlink( v ) );
 293                 }
 294
 295                 CPPUNIT_ASSERT( l.unlink( v1 ) );
 296                 CPPUNIT_ASSERT( !l.unlink( v1 ) );
 297                 CPPUNIT_ASSERT( !l.find( v1.key() ));
 298                 CPPUNIT_ASSERT( !l.find( v2.key() ));
 299                 CPPUNIT_ASSERT( l.find( v3.key() ));
 300                 CPPUNIT_ASSERT( !l.empty() );
 301                 CPPUNIT_ASSERT( !l.unlink( v1 ) );
 302                 CPPUNIT_ASSERT( !l.unlink( v2 ) );
 303
 304                 CPPUNIT_ASSERT( l.unlink( v3 ) );
 305                 CPPUNIT_ASSERT( !l.find( v1.key() ));
 306                 CPPUNIT_ASSERT( !l.find_with( v2.key(), less<value_type>() ));
 307                 CPPUNIT_ASSERT( !l.find( v3.key() ));
 308                 CPPUNIT_ASSERT( l.empty() );
 309                 CPPUNIT_ASSERT( !l.unlink( v1 ) );
 310                 CPPUNIT_ASSERT( !l.unlink( v2 ) );
 311                 CPPUNIT_ASSERT( !l.unlink( v3 ) );
 312
 313                 // Apply retired pointer to clean links
 314                 OrdList::gc::force_dispose();
 315
 316                 stat s( v3.s );
 317                 ret = l.ensure( v3, ensure_functor() );
 318                 CPPUNIT_ASSERT( ret.first );
 319                 CPPUNIT_ASSERT( ret.second );
 320                 CPPUNIT_ASSERT( v3.s.nEnsureNewCall == s.nEnsureNewCall + 1);
 321                 CPPUNIT_ASSERT( v3.s.nEnsureExistsCall == s.nEnsureExistsCall );
 322                 CPPUNIT_ASSERT( !l.empty() );
 323
 324                 s = v2.s;
 325                 ret = l.ensure( v2, ensure_functor() );
 326                 CPPUNIT_ASSERT( ret.first );
 327                 CPPUNIT_ASSERT( ret.second );
 328                 CPPUNIT_ASSERT( v2.s.nEnsureNewCall == s.nEnsureNewCall + 1);
 329                 CPPUNIT_ASSERT( v2.s.nEnsureExistsCall == s.nEnsureExistsCall );
 330                 CPPUNIT_ASSERT( !l.empty() );
 331
 332                 s = v1.s;
 333                 ret = l.ensure( v1, ensure_functor() );
 334                 CPPUNIT_ASSERT( ret.first );
 335                 CPPUNIT_ASSERT( ret.second );
 336                 CPPUNIT_ASSERT( v1.s.nEnsureNewCall == s.nEnsureNewCall + 1);
 337                 CPPUNIT_ASSERT( v1.s.nEnsureExistsCall == s.nEnsureExistsCall );
 338                 CPPUNIT_ASSERT( !l.empty() );
 339
 340                 // Erase test
 341                 CPPUNIT_ASSERT( l.erase( v1.key()) );
 342                 //CPPUNIT_ASSERT( v1.s.nDisposeCount == 0 );
 343                 CPPUNIT_ASSERT( !l.empty() );
 344
 345                 CPPUNIT_ASSERT( v2.s.nEraseCall == 0 );
 346                 CPPUNIT_ASSERT( l.erase_with( v2.key(), less<value_type>(), erase_functor()) );
 347                 CPPUNIT_ASSERT( v2.s.nEraseCall == 1 );
 348                 CPPUNIT_ASSERT( !l.erase_with( v2.key(), less<value_type>()));
 349                 CPPUNIT_ASSERT( v2.s.nEraseCall == 1 );
 350                 //CPPUNIT_ASSERT( v2.s.nDisposeCount == 0 );
 351                 CPPUNIT_ASSERT( !l.empty() );
 352
 353                 CPPUNIT_ASSERT( !l.erase( v2 ));
 354                 CPPUNIT_ASSERT( !l.erase( v1 ));
 355                 //CPPUNIT_ASSERT( v2.s.nDisposeCount == 0 );
 356                 CPPUNIT_ASSERT( !l.empty() );
 357
 358                 CPPUNIT_ASSERT( v3.s.nEraseCall == 0 );
 359                 CPPUNIT_ASSERT( l.erase( v3, erase_functor() ));
 360                 CPPUNIT_ASSERT( v3.s.nEraseCall == 1 );
 361                 //CPPUNIT_ASSERT( v3.s.nDisposeCount == 0 );
 362                 CPPUNIT_ASSERT( l.empty() );
 363
 364                 // Apply retired pointer to clean links
 365                 OrdList::gc::force_dispose();
 366
 367                 // Unlink test
 368                 CPPUNIT_ASSERT( l.insert( v1 ));
 369                 CPPUNIT_ASSERT( l.insert( v3 ));
 370                 CPPUNIT_ASSERT( !l.empty() );
 371                 CPPUNIT_ASSERT( !l.unlink( v2 ));
 372                 CPPUNIT_ASSERT( l.unlink( v1 ));
 373                 CPPUNIT_ASSERT( !l.unlink( v1 ));
 374                 CPPUNIT_ASSERT( l.unlink( v3 ));
 375                 CPPUNIT_ASSERT( !l.unlink( v3 ));
 376                 CPPUNIT_ASSERT( l.empty() );
 377
 378                 // Apply retired pointer
 379                 OrdList::gc::force_dispose();
 380                 CPPUNIT_ASSERT( v1.s.nDisposeCount == 3 );
 381                 CPPUNIT_ASSERT( v2.s.nDisposeCount == 2 );
 382                 CPPUNIT_ASSERT( v3.s.nDisposeCount == 3 );
 383
 384                 // Destructor test (call disposer)
 385                 CPPUNIT_ASSERT( l.insert( v1 ));
 386                 CPPUNIT_ASSERT( l.insert( v3 ));
 387                 CPPUNIT_ASSERT( l.insert( v2 ));
 388
 389                 // Iterator test
 390                 {
 391                     typename OrdList::iterator it = l.begin();
 392                     typename OrdList::const_iterator cit = l.cbegin();
 393                     CPPUNIT_ASSERT( it != l.end() );
 394                     CPPUNIT_ASSERT( it != l.cend() );
 395                     CPPUNIT_ASSERT( cit != l.end() );
 396                     CPPUNIT_ASSERT( cit != l.cend() );
 397                     CPPUNIT_ASSERT( cit == it );
 398
 399                     CPPUNIT_ASSERT( it->nKey == v2.nKey );
 400                     CPPUNIT_ASSERT( it->nVal == v2.nVal );
 401                     CPPUNIT_ASSERT( ++it != l.end() );
 402                     CPPUNIT_ASSERT( it->nKey == v1.nKey );
 403                     CPPUNIT_ASSERT( it->nVal == v1.nVal );
 404                     CPPUNIT_ASSERT( ++it != l.end() );
 405                     CPPUNIT_ASSERT( it->nKey == v3.nKey );
 406                     CPPUNIT_ASSERT( it->nVal == v3.nVal );
 407                     CPPUNIT_ASSERT( ++it == l.end() );
 408                 }
 409
 410                 {
 411                     OrdList const & lref = l;
 412                     typename OrdList::const_iterator it = lref.begin();
 413                     CPPUNIT_ASSERT( it != l.end() );
 414                     CPPUNIT_ASSERT( it->nKey == v2.nKey );
 415                     CPPUNIT_ASSERT( it->nVal == v2.nVal );
 416                     CPPUNIT_ASSERT( ++it != lref.end() );
 417                     CPPUNIT_ASSERT( it->nKey == v1.nKey );
 418                     CPPUNIT_ASSERT( it->nVal == v1.nVal );
 419                     CPPUNIT_ASSERT( ++it != l.end() );
 420                     CPPUNIT_ASSERT( it->nKey == v3.nKey );
 421                     CPPUNIT_ASSERT( it->nVal == v3.nVal );
 422                     CPPUNIT_ASSERT( ++it == l.end() );
 423                 }
 424             }
 425
 426             // Apply retired pointer
 427             OrdList::gc::force_dispose();
 428
 429             CPPUNIT_ASSERT( v1.s.nDisposeCount == 4 );
 430             CPPUNIT_ASSERT( v2.s.nDisposeCount == 3 );
 431             CPPUNIT_ASSERT( v3.s.nDisposeCount == 4 );
 432         }
 433
 434         template <class OrdList>
 435         void test_int()
 436         {
 437             test_int_common<OrdList>();
 438
 439             OrdList l;
 440             typename OrdList::guarded_ptr gp;
 441
 442             static int const nLimit = 20;
 443             typename OrdList::value_type arrItem[nLimit];
 444
 445             {
 446                 int a[nLimit];
 447                 for (int i = 0; i < nLimit; ++i)
 448                     a[i]=i;
 449                 std::random_shuffle( a, a + nLimit );
 450
 451                 for (int i = 0; i < nLimit; ++i) {
 452                     arrItem[i].nKey = a[i];
 453                     arrItem[i].nVal = a[i] * 2;
 454                 }
 455
 456                 // extract/get
 457                 for ( int i = 0; i < nLimit; ++i )
 458                     CPPUNIT_ASSERT( l.insert( arrItem[i] ) );
 459
 460                 for ( int i=0; i < nLimit; ++i ) {
 461                     gp = l.get( arrItem[i].nKey );
 462                     CPPUNIT_ASSERT( gp );
 463                     CPPUNIT_ASSERT( !gp.empty());
 464                     CPPUNIT_ASSERT( gp->nKey == arrItem[i].nKey );
 465                     CPPUNIT_ASSERT( gp->nVal == arrItem[i].nVal );
 466
 467                     gp = l.extract( arrItem[i].nKey );
 468                     CPPUNIT_ASSERT( gp );
 469                     CPPUNIT_ASSERT( !gp.empty());
 470                     CPPUNIT_ASSERT( gp->nKey == arrItem[i].nKey );
 471                     CPPUNIT_ASSERT( gp->nVal == arrItem[i].nVal );
 472
 473                     gp = l.get( arrItem[i].nKey );
 474                     CPPUNIT_ASSERT( !gp );
 475                     CPPUNIT_ASSERT( gp.empty());
 476                     CPPUNIT_ASSERT( !l.extract( arrItem[i].nKey ));
 477                     CPPUNIT_ASSERT( gp.empty());
 478                 }
 479                 CPPUNIT_ASSERT( l.empty() );
 480                 CPPUNIT_ASSERT( !l.get( nLimit/2 ));
 481                 CPPUNIT_ASSERT( !l.extract( nLimit/2 ));
 482
 483                 // Apply retired pointer
 484                 OrdList::gc::force_dispose();
 485
 486                 // extract_with/get_with
 487                 for ( int i = 0; i < nLimit; ++i )
 488                     CPPUNIT_ASSERT( l.insert( arrItem[i] ) );
 489
 490                 for ( int i=0; i < nLimit; ++i ) {
 491                     other_item itm( arrItem[i].nKey );
 492                     gp = l.get_with( itm, other_less() );
 493                     CPPUNIT_ASSERT( gp );
 494                     CPPUNIT_ASSERT( !gp.empty());
 495                     CPPUNIT_ASSERT( gp->nKey == arrItem[i].nKey );
 496                     CPPUNIT_ASSERT( gp->nVal == arrItem[i].nVal );
 497
 498                     gp = l.extract_with( itm, other_less() );
 499                     CPPUNIT_ASSERT( gp );
 500                     CPPUNIT_ASSERT( !gp.empty());
 501                     CPPUNIT_ASSERT( gp->nKey == arrItem[i].nKey );
 502                     CPPUNIT_ASSERT( gp->nVal == arrItem[i].nVal );
 503
 504                     gp = l.get_with( itm, other_less() );
 505                     CPPUNIT_ASSERT( !gp );
 506                     CPPUNIT_ASSERT( gp.empty());
 507                     CPPUNIT_ASSERT( !l.extract_with( itm, other_less() ));
 508                     CPPUNIT_ASSERT( gp.empty());
 509                 }
 510                 CPPUNIT_ASSERT( l.empty() );
 511                 CPPUNIT_ASSERT( !l.get_with( other_item(nLimit/2), other_less() ));
 512                 CPPUNIT_ASSERT( gp.empty());
 513                 CPPUNIT_ASSERT( !l.extract_with( other_item(nLimit/2), other_less() ));
 514                 CPPUNIT_ASSERT( gp.empty());
 515
 516                 // Apply retired pointer
 517                 OrdList::gc::force_dispose();
 518
 519                 for ( int i=0; i < nLimit; i++ ) {
 520                     CPPUNIT_ASSERT( arrItem[i].s.nDisposeCount == 2 );
 521                 }
 522             }
 523         }
 524
 525         template <class OrdList>
 526         void test_rcu_int()
 527         {
 528             test_int_common<OrdList>();
 529
 530             OrdList l;
 531             static int const nLimit = 20;
 532             typename OrdList::value_type arrItem[nLimit];
 533
 534             typedef typename OrdList::rcu_lock rcu_lock;
 535             typedef typename OrdList::value_type value_type;
 536             typedef typename OrdList::gc rcu_type;
 537
 538             {
 539                 int a[nLimit];
 540                 for (int i = 0; i < nLimit; ++i)
 541                     a[i]=i;
 542                 std::random_shuffle( a, a + nLimit );
 543
 544                 for (int i = 0; i < nLimit; ++i) {
 545                     arrItem[i].nKey = a[i];
 546                     arrItem[i].nVal = a[i] * 2;
 547                 }
 548
 549                 typename OrdList::exempt_ptr ep;
 550
 551                 // extract/get
 552                 for ( int i = 0; i < nLimit; ++i )
 553                     CPPUNIT_ASSERT( l.insert( arrItem[i] ) );
 554
 555                 for ( int i = 0; i < nLimit; ++i ) {
 556                     {
 557                         rcu_lock lock;
 558                         value_type * pGet = l.get( a[i] );
 559                         CPPUNIT_ASSERT( pGet != nullptr );
 560                         CPPUNIT_CHECK( pGet->nKey == a[i] );
 561                         CPPUNIT_CHECK( pGet->nVal == a[i] * 2 );
 562
 563                         ep = l.extract( a[i] );
 564                         CPPUNIT_ASSERT( ep );
 565                         CPPUNIT_ASSERT( !ep.empty() );
 566                         CPPUNIT_CHECK( ep->nKey == a[i] );
 567                         CPPUNIT_CHECK( (*ep).nVal == a[i] * 2 );
 568                     }
 569                     ep.release();
 570                     {
 571                         rcu_lock lock;
 572                         CPPUNIT_CHECK( l.get( a[i] ) == nullptr );
 573                         CPPUNIT_CHECK( !l.extract( a[i] ) );
 574                         CPPUNIT_CHECK( ep.empty() );
 575                     }
 576                 }
 577                 CPPUNIT_ASSERT( l.empty() );
 578
 579                 {
 580                     rcu_lock lock;
 581                     CPPUNIT_CHECK( l.get( a[0] ) == nullptr );
 582                     ep = l.extract( a[0] );
 583                     CPPUNIT_CHECK( !ep );
 584                     CPPUNIT_CHECK( ep.empty() );
 585                 }
 586                 // Apply retired pointer
 587                 OrdList::gc::force_dispose();
 588
 589                 // extract_with/get_with
 590                 for ( int i = 0; i < nLimit; ++i ) {
 591                     CPPUNIT_ASSERT( l.insert( arrItem[i] ) );
 592                 }
 593
 594                 for ( int i = 0; i < nLimit; ++i ) {
 595                     other_item itm( a[i] );
 596                     {
 597                         rcu_lock lock;
 598                         value_type * pGet = l.get_with( itm, other_less() );
 599                         CPPUNIT_ASSERT( pGet != nullptr );
 600                         CPPUNIT_CHECK( pGet->nKey == a[i] );
 601                         CPPUNIT_CHECK( pGet->nVal == a[i] * 2 );
 602
 603                         ep = l.extract_with( itm, other_less() );
 604                         CPPUNIT_ASSERT( ep );
 605                         CPPUNIT_ASSERT( !ep.empty() );
 606                         CPPUNIT_CHECK( ep->nKey == a[i] );
 607                         CPPUNIT_CHECK( ep->nVal == a[i] * 2 );
 608                     }
 609                     ep.release();
 610                     {
 611                         rcu_lock lock;
 612                         CPPUNIT_CHECK( l.get_with( itm, other_less() ) == nullptr );
 613                         ep = l.extract_with( itm, other_less() );
 614                         CPPUNIT_CHECK( !ep );
 615                         CPPUNIT_CHECK( ep.empty() );
 616                     }
 617                 }
 618                 CPPUNIT_ASSERT( l.empty() );
 619
 620                 {
 621                     rcu_lock lock;
 622                     CPPUNIT_CHECK( l.get_with( other_item( 0 ), other_less() ) == nullptr );
 623                     CPPUNIT_CHECK( !l.extract_with( other_item(0), other_less() ));
 624                     CPPUNIT_CHECK( ep.empty() );
 625                 }
 626                 // Apply retired pointer
 627                 OrdList::gc::force_dispose();
 628             }
 629         }
 630
 631         template <class OrdList>
 632         void test_nogc_int()
 633         {
 634             typedef typename OrdList::value_type    value_type;
 635             {
 636                 value_type v1( 10, 50 );
 637                 value_type v2( 5, 25  );
 638                 value_type v3( 20, 100 );
 639                 {
 640                     OrdList l;
 641                     CPPUNIT_ASSERT( l.empty() );
 642
 643                     CPPUNIT_ASSERT( l.insert( v1 ))     ;   // true
 644                     CPPUNIT_ASSERT( l.find( v1.key() ) == &v1 );
 645
 646                     CPPUNIT_ASSERT( v1.s.nFindCall == 0 );
 647                     CPPUNIT_ASSERT( l.find( v1.key(), find_functor() ));
 648                     CPPUNIT_ASSERT( v1.s.nFindCall == 1 );
 649
 650                     CPPUNIT_ASSERT( l.find_with( v2.key(), less<value_type>() ) == nullptr );
 651                     CPPUNIT_ASSERT( l.find( v3.key() ) == nullptr );
 652                     CPPUNIT_ASSERT( !l.empty() );
 653
 654                     //CPPUNIT_ASSERT( !l.insert( v1 ))    ;   // assertion "is_empty" is raised
 655
 656                     {
 657                         value_type v( v1 );
 658                         CPPUNIT_ASSERT( !l.insert( v )) ;   // false
 659                     }
 660
 661                     std::pair<bool, bool> ret = l.ensure( v2, ensure_functor() );
 662                     CPPUNIT_ASSERT( ret.first );
 663                     CPPUNIT_ASSERT( ret.second );
 664                     CPPUNIT_ASSERT( v2.s.nEnsureNewCall == 1 );
 665                     CPPUNIT_ASSERT( v2.s.nEnsureExistsCall == 0 );
 666
 667                     //CPPUNIT_ASSERT( !l.insert( v2 ))    ;   // assertion "is_empty"
 668
 669                     CPPUNIT_ASSERT( l.find( v1.key() ) == &v1 ) ;   // true
 670
 671                     CPPUNIT_ASSERT( v1.s.nFindCall == 1 );
 672                     CPPUNIT_ASSERT( l.find( v1.key(), find_functor() ));
 673                     CPPUNIT_ASSERT( v1.s.nFindCall == 2 );
 674
 675                     CPPUNIT_ASSERT( l.find_with( v2.key(), less<value_type>() ) == &v2 );
 676
 677                     CPPUNIT_ASSERT( v2.s.nFindCall == 0 );
 678                     CPPUNIT_ASSERT( l.find_with( v2.key(), less<value_type>(), find_functor() ));
 679                     CPPUNIT_ASSERT( v2.s.nFindCall == 1 );
 680
 681                     CPPUNIT_ASSERT( !l.find( v3.key() ));
 682
 683                     {
 684                         value_type v( v2 );
 685                         ret = l.ensure( v, ensure_functor() );
 686
 687                         CPPUNIT_ASSERT( ret.first );
 688                         CPPUNIT_ASSERT( !ret.second );
 689                         CPPUNIT_ASSERT( v2.s.nEnsureExistsCall == 1 );
 690                         CPPUNIT_ASSERT( v.s.nEnsureExistsCall == 0 && v.s.nEnsureNewCall == 0 );
 691                     }
 692
 693                     CPPUNIT_ASSERT( !l.empty() );
 694
 695                     CPPUNIT_ASSERT( l.insert( v3 ))     ;   // true
 696                     CPPUNIT_ASSERT( l.find( v3.key() ) == &v3 );
 697
 698                     CPPUNIT_ASSERT( v3.s.nFindCall == 0 );
 699                     CPPUNIT_ASSERT( l.find( v3.key(), find_functor() ));
 700                     CPPUNIT_ASSERT( v3.s.nFindCall == 1 );
 701
 702                     {
 703                         typename OrdList::iterator it = l.begin();
 704                         typename OrdList::const_iterator cit = l.cbegin();
 705                         CPPUNIT_ASSERT( it != l.end() );
 706                         CPPUNIT_ASSERT( it != l.cend() );
 707                         CPPUNIT_ASSERT( cit != l.end() );
 708                         CPPUNIT_ASSERT( cit != l.cend() );
 709                         CPPUNIT_ASSERT( cit == it );
 710
 711                         CPPUNIT_ASSERT( it->nKey == v2.nKey );
 712                         CPPUNIT_ASSERT( it->nVal == v2.nVal );
 713                         CPPUNIT_ASSERT( ++it != l.end() );
 714                         CPPUNIT_ASSERT( it->nKey == v1.nKey );
 715                         CPPUNIT_ASSERT( it->nVal == v1.nVal );
 716                         CPPUNIT_ASSERT( it++ != l.end() );
 717                         CPPUNIT_ASSERT( it->nKey == v3.nKey );
 718                         CPPUNIT_ASSERT( it->nVal == v3.nVal );
 719                         CPPUNIT_ASSERT( it++ != l.end() );
 720                         CPPUNIT_ASSERT( it == l.end() );
 721                     }
 722
 723                     {
 724                         OrdList const & lref = l;
 725                         typename OrdList::const_iterator it = lref.begin();
 726                         CPPUNIT_ASSERT( it != l.end() );
 727                         CPPUNIT_ASSERT( it->nKey == v2.nKey );
 728                         CPPUNIT_ASSERT( it->nVal == v2.nVal );
 729                         CPPUNIT_ASSERT( ++it != lref.end() );
 730                         CPPUNIT_ASSERT( it->nKey == v1.nKey );
 731                         CPPUNIT_ASSERT( it->nVal == v1.nVal );
 732                         CPPUNIT_ASSERT( it++ != l.end() );
 733                         CPPUNIT_ASSERT( it->nKey == v3.nKey );
 734                         CPPUNIT_ASSERT( it->nVal == v3.nVal );
 735                         CPPUNIT_ASSERT( it++ != lref.end() );
 736                         CPPUNIT_ASSERT( it == l.end() );
 737                     }
 738                 }
 739
 740                 // Disposer called on list destruction
 741                 CPPUNIT_ASSERT( v1.s.nDisposeCount == 1 );
 742                 CPPUNIT_ASSERT( v2.s.nDisposeCount == 1 );
 743                 CPPUNIT_ASSERT( v3.s.nDisposeCount == 1 );
 744             }
 745         }
 746
 747         void HP_base_cmp();
 748         void HP_base_less();
 749         void HP_base_cmpmix();
 750         void HP_base_ic();
 751         void HP_member_cmp();
 752         void HP_member_less();
 753         void HP_member_cmpmix();
 754         void HP_member_ic();
 755
 756         void DHP_base_cmp();
 757         void DHP_base_less();
 758         void DHP_base_cmpmix();
 759         void DHP_base_ic();
 760         void DHP_member_cmp();
 761         void DHP_member_less();
 762         void DHP_member_cmpmix();
 763         void DHP_member_ic();
 764
 765         void RCU_GPI_base_cmp();
 766         void RCU_GPI_base_less();
 767         void RCU_GPI_base_cmpmix();
 768         void RCU_GPI_base_ic();
 769         void RCU_GPI_member_cmp();
 770         void RCU_GPI_member_less();
 771         void RCU_GPI_member_cmpmix();
 772         void RCU_GPI_member_ic();
 773
 774         void RCU_GPB_base_cmp();
 775         void RCU_GPB_base_less();
 776         void RCU_GPB_base_cmpmix();
 777         void RCU_GPB_base_ic();
 778         void RCU_GPB_member_cmp();
 779         void RCU_GPB_member_less();
 780         void RCU_GPB_member_cmpmix();
 781         void RCU_GPB_member_ic();
 782
 783         void RCU_GPT_base_cmp();
 784         void RCU_GPT_base_less();
 785         void RCU_GPT_base_cmpmix();
 786         void RCU_GPT_base_ic();
 787         void RCU_GPT_member_cmp();
 788         void RCU_GPT_member_less();
 789         void RCU_GPT_member_cmpmix();
 790         void RCU_GPT_member_ic();
 791
 792         void RCU_SHB_base_cmp();
 793         void RCU_SHB_base_less();
 794         void RCU_SHB_base_cmpmix();
 795         void RCU_SHB_base_ic();
 796         void RCU_SHB_member_cmp();
 797         void RCU_SHB_member_less();
 798         void RCU_SHB_member_cmpmix();
 799         void RCU_SHB_member_ic();
 800
 801         void RCU_SHT_base_cmp();
 802         void RCU_SHT_base_less();
 803         void RCU_SHT_base_cmpmix();
 804         void RCU_SHT_base_ic();
 805         void RCU_SHT_member_cmp();
 806         void RCU_SHT_member_less();
 807         void RCU_SHT_member_cmpmix();
 808         void RCU_SHT_member_ic();
 809
 810         void nogc_base_cmp();
 811         void nogc_base_less();
 812         void nogc_base_cmpmix();
 813         void nogc_base_ic();
 814         void nogc_member_cmp();
 815         void nogc_member_less();
 816         void nogc_member_cmpmix();
 817         void nogc_member_ic();
 818
 819
 820         CPPUNIT_TEST_SUITE(IntrusiveLazyListHeaderTest)
 821             CPPUNIT_TEST(HP_base_cmp)
 822             CPPUNIT_TEST(HP_base_less)
 823             CPPUNIT_TEST(HP_base_cmpmix)
 824             CPPUNIT_TEST(HP_base_ic)
 825             CPPUNIT_TEST(HP_member_cmp)
 826             CPPUNIT_TEST(HP_member_less)
 827             CPPUNIT_TEST(HP_member_cmpmix)
 828             CPPUNIT_TEST(HP_member_ic)
 829
 830             CPPUNIT_TEST(DHP_base_cmp)
 831             CPPUNIT_TEST(DHP_base_less)
 832             CPPUNIT_TEST(DHP_base_cmpmix)
 833             CPPUNIT_TEST(DHP_base_ic)
 834             CPPUNIT_TEST(DHP_member_cmp)
 835             CPPUNIT_TEST(DHP_member_less)
 836             CPPUNIT_TEST(DHP_member_cmpmix)
 837             CPPUNIT_TEST(DHP_member_ic)
 838
 839             CPPUNIT_TEST(RCU_GPI_base_cmp)
 840             CPPUNIT_TEST(RCU_GPI_base_less)
 841             CPPUNIT_TEST(RCU_GPI_base_cmpmix)
 842             CPPUNIT_TEST(RCU_GPI_base_ic)
 843             CPPUNIT_TEST(RCU_GPI_member_cmp)
 844             CPPUNIT_TEST(RCU_GPI_member_less)
 845             CPPUNIT_TEST(RCU_GPI_member_cmpmix)
 846             CPPUNIT_TEST(RCU_GPI_member_ic)
 847
 848             CPPUNIT_TEST(RCU_GPB_base_cmp)
 849             CPPUNIT_TEST(RCU_GPB_base_less)
 850             CPPUNIT_TEST(RCU_GPB_base_cmpmix)
 851             CPPUNIT_TEST(RCU_GPB_base_ic)
 852             CPPUNIT_TEST(RCU_GPB_member_cmp)
 853             CPPUNIT_TEST(RCU_GPB_member_less)
 854             CPPUNIT_TEST(RCU_GPB_member_cmpmix)
 855             CPPUNIT_TEST(RCU_GPB_member_ic)
 856
 857             CPPUNIT_TEST(RCU_GPT_base_cmp)
 858             CPPUNIT_TEST(RCU_GPT_base_less)
 859             CPPUNIT_TEST(RCU_GPT_base_cmpmix)
 860             CPPUNIT_TEST(RCU_GPT_base_ic)
 861             CPPUNIT_TEST(RCU_GPT_member_cmp)
 862             CPPUNIT_TEST(RCU_GPT_member_less)
 863             CPPUNIT_TEST(RCU_GPT_member_cmpmix)
 864             CPPUNIT_TEST(RCU_GPT_member_ic)
 865
 866             CPPUNIT_TEST(RCU_SHB_base_cmp)
 867             CPPUNIT_TEST(RCU_SHB_base_less)
 868             CPPUNIT_TEST(RCU_SHB_base_cmpmix)
 869             CPPUNIT_TEST(RCU_SHB_base_ic)
 870             CPPUNIT_TEST(RCU_SHB_member_cmp)
 871             CPPUNIT_TEST(RCU_SHB_member_less)
 872             CPPUNIT_TEST(RCU_SHB_member_cmpmix)
 873             CPPUNIT_TEST(RCU_SHB_member_ic)
 874
 875             CPPUNIT_TEST(RCU_SHT_base_cmp)
 876             CPPUNIT_TEST(RCU_SHT_base_less)
 877             CPPUNIT_TEST(RCU_SHT_base_cmpmix)
 878             CPPUNIT_TEST(RCU_SHT_base_ic)
 879             CPPUNIT_TEST(RCU_SHT_member_cmp)
 880             CPPUNIT_TEST(RCU_SHT_member_less)
 881             CPPUNIT_TEST(RCU_SHT_member_cmpmix)
 882             CPPUNIT_TEST(RCU_SHT_member_ic)
 883
 884             CPPUNIT_TEST(nogc_base_cmp)
 885             CPPUNIT_TEST(nogc_base_less)
 886             CPPUNIT_TEST(nogc_base_cmpmix)
 887             CPPUNIT_TEST(nogc_base_ic)
 888             CPPUNIT_TEST(nogc_member_cmp)
 889             CPPUNIT_TEST(nogc_member_less)
 890             CPPUNIT_TEST(nogc_member_cmpmix)
 891             CPPUNIT_TEST(nogc_member_ic)
 892
 893         CPPUNIT_TEST_SUITE_END()
 894     };
 895 }   // namespace ordlist
 896
 897 #endif // #ifndef CDSTEST_HDR_INTRUSIVE_LAZY_H