tests/test-hdr/list/hdr_intrusive_michael.h

   1 //$$CDS-header$$
   2
   3 #ifndef CDSTEST_HDR_INTRUSIVE_MICHAEL_H
   4 #define CDSTEST_HDR_INTRUSIVE_MICHAEL_H
   5
   6 #include "cppunit/cppunit_proxy.h"
   7 #include <cds/intrusive/details/michael_list_base.h>
   8
   9 namespace ordlist {
  10     namespace ci = cds::intrusive;
  11     namespace co = cds::opt;
  12
  13     class IntrusiveMichaelListHeaderTest: 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::michael_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::michael_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         struct other_item {
 126             int nKey;
 127
 128             other_item( int n )
 129                 : nKey(n)
 130             {}
 131         };
 132
 133         struct other_less {
 134             template <typename T, typename Q>
 135             bool operator()( T const& i1, Q const& i2) const
 136             {
 137                 return i1.nKey < i2.nKey;
 138             }
 139         };
 140
 141         template <typename T>
 142         struct cmp {
 143             int operator ()(const T& v1, const T& v2 ) const
 144             {
 145                 if ( v1.key() < v2.key() )
 146                     return -1;
 147                 return v1.key() > v2.key() ? 1 : 0;
 148             }
 149
 150             template <typename Q>
 151             int operator ()(const T& v1, const Q& v2 ) const
 152             {
 153                 if ( v1.key() < v2 )
 154                     return -1;
 155                 return v1.key() > v2 ? 1 : 0;
 156             }
 157
 158             template <typename Q>
 159             int operator ()(const Q& v1, const T& v2 ) const
 160             {
 161                 if ( v1 < v2.key() )
 162                     return -1;
 163                 return v1 > v2.key() ? 1 : 0;
 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( v2.key() ));
 226                 CPPUNIT_ASSERT( !l.find_with( v3.key(), less<value_type>() ));
 227                 CPPUNIT_ASSERT( !l.empty() );
 228
 229                 CPPUNIT_ASSERT( !l.insert( v1 ))    ;   // assertion "is_empty" is not raised since pNext is nullptr
 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_with( v1.key(), less<value_type>() )) ;   // true
 245
 246                 CPPUNIT_ASSERT( v1.s.nFindCall == 1 );
 247                 CPPUNIT_ASSERT( l.find_with( v1.key(), less<value_type>(), 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( v2.key(), 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_with( v1.key(), less<value_type>() ));
 306                 CPPUNIT_ASSERT( !l.find_with( v2.key(), less<value_type>(), find_functor() ));
 307                 CPPUNIT_ASSERT( !l.find( v3.key(), find_functor() ));
 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( v1.s.nEraseCall == 0 );
 342                 CPPUNIT_ASSERT( l.erase( v1.key(), erase_functor()) );
 343                 CPPUNIT_ASSERT( v1.s.nEraseCall == 1 );
 344                 //CPPUNIT_ASSERT( v1.s.nDisposeCount == 0 );
 345                 CPPUNIT_ASSERT( !l.empty() );
 346
 347                 CPPUNIT_ASSERT( l.erase_with( v2.key(), less<value_type>() ) );
 348                 CPPUNIT_ASSERT( !l.erase( v2.key()));
 349                 //CPPUNIT_ASSERT( v2.s.nDisposeCount == 0 );
 350                 CPPUNIT_ASSERT( !l.empty() );
 351
 352                 CPPUNIT_ASSERT( v2.s.nEraseCall == 0 );
 353                 CPPUNIT_ASSERT( !l.erase( v2, erase_functor() ));
 354                 CPPUNIT_ASSERT( v2.s.nEraseCall == 0 );
 355                 CPPUNIT_ASSERT( !l.erase( v1 ));
 356                 //CPPUNIT_ASSERT( v2.s.nDisposeCount == 0 );
 357                 CPPUNIT_ASSERT( !l.empty() );
 358
 359                 CPPUNIT_ASSERT( v3.s.nEraseCall == 0 );
 360                 CPPUNIT_ASSERT( l.erase_with( v3, less<value_type>(), erase_functor() ));
 361                 CPPUNIT_ASSERT( v3.s.nEraseCall == 1 );
 362                 //CPPUNIT_ASSERT( v3.s.nDisposeCount == 0 );
 363                 CPPUNIT_ASSERT( l.empty() );
 364
 365                 // Apply retired pointer to clean links
 366                 OrdList::gc::force_dispose();
 367
 368                 // Unlink test
 369                 CPPUNIT_ASSERT( l.insert( v1 ));
 370                 CPPUNIT_ASSERT( l.insert( v3 ));
 371                 CPPUNIT_ASSERT( !l.empty() );
 372                 CPPUNIT_ASSERT( !l.unlink( v2 ));
 373                 CPPUNIT_ASSERT( l.unlink( v1 ));
 374                 CPPUNIT_ASSERT( !l.unlink( v1 ));
 375                 CPPUNIT_ASSERT( l.unlink( v3 ));
 376                 CPPUNIT_ASSERT( !l.unlink( v3 ));
 377                 CPPUNIT_ASSERT( l.empty() );
 378
 379                 // Apply retired pointer
 380                 OrdList::gc::force_dispose();
 381                 CPPUNIT_ASSERT( v1.s.nDisposeCount == 3 );
 382                 CPPUNIT_ASSERT( v2.s.nDisposeCount == 2 );
 383                 CPPUNIT_ASSERT( v3.s.nDisposeCount == 3 );
 384
 385                 // Destructor test (call disposer)
 386                 CPPUNIT_ASSERT( l.insert( v1 ));
 387                 CPPUNIT_ASSERT( l.insert( v3 ));
 388                 CPPUNIT_ASSERT( l.insert( v2 ));
 389
 390                 // Iterator test
 391                 // begin/end
 392                 {
 393                     typename OrdList::iterator it = l.begin();
 394                     typename OrdList::const_iterator cit = l.cbegin();
 395                     CPPUNIT_ASSERT( it != l.end() );
 396                     CPPUNIT_ASSERT( it != l.cend() );
 397                     CPPUNIT_ASSERT( cit != l.end() );
 398                     CPPUNIT_ASSERT( cit != l.cend() );
 399                     CPPUNIT_ASSERT( cit == it );
 400
 401                     CPPUNIT_ASSERT( it->nKey == v2.nKey );
 402                     CPPUNIT_ASSERT( it->nVal == v2.nVal );
 403                     CPPUNIT_ASSERT( ++it != l.end() );
 404                     CPPUNIT_ASSERT( it->nKey == v1.nKey );
 405                     CPPUNIT_ASSERT( it->nVal == v1.nVal );
 406                     CPPUNIT_ASSERT( ++it != l.end() );
 407                     CPPUNIT_ASSERT( it->nKey == v3.nKey );
 408                     CPPUNIT_ASSERT( it->nVal == v3.nVal );
 409                     CPPUNIT_ASSERT( ++it == l.end() );
 410                 }
 411
 412                 // cbegin/cend
 413                 {
 414                     typename OrdList::const_iterator it = l.cbegin();
 415                     CPPUNIT_ASSERT( it != l.cend() );
 416                     CPPUNIT_ASSERT( it->nKey == v2.nKey );
 417                     CPPUNIT_ASSERT( it->nVal == v2.nVal );
 418                     CPPUNIT_ASSERT( ++it != l.cend() );
 419                     CPPUNIT_ASSERT( it->nKey == v1.nKey );
 420                     CPPUNIT_ASSERT( it->nVal == v1.nVal );
 421                     CPPUNIT_ASSERT( ++it != l.cend() );
 422                     CPPUNIT_ASSERT( it->nKey == v3.nKey );
 423                     CPPUNIT_ASSERT( it->nVal == v3.nVal );
 424                     CPPUNIT_ASSERT( ++it == l.cend() );
 425                 }
 426
 427                 // const begin/end
 428                 {
 429                     OrdList const & lref = l;
 430                     typename OrdList::const_iterator it = lref.begin();
 431                     CPPUNIT_ASSERT( it != l.end() );
 432                     CPPUNIT_ASSERT( it->nKey == v2.nKey );
 433                     CPPUNIT_ASSERT( it->nVal == v2.nVal );
 434                     CPPUNIT_ASSERT( ++it != lref.end() );
 435                     CPPUNIT_ASSERT( it->nKey == v1.nKey );
 436                     CPPUNIT_ASSERT( it->nVal == v1.nVal );
 437                     CPPUNIT_ASSERT( ++it != l.end() );
 438                     CPPUNIT_ASSERT( it->nKey == v3.nKey );
 439                     CPPUNIT_ASSERT( it->nVal == v3.nVal );
 440                     CPPUNIT_ASSERT( ++it == l.end() );
 441                 }
 442             }
 443
 444             // Apply retired pointer
 445             OrdList::gc::force_dispose();
 446
 447             CPPUNIT_ASSERT( v1.s.nDisposeCount == 4 );
 448             CPPUNIT_ASSERT( v2.s.nDisposeCount == 3 );
 449             CPPUNIT_ASSERT( v3.s.nDisposeCount == 4 );
 450         }
 451
 452         template <class OrdList>
 453         void test_int()
 454         {
 455             test_int_common<OrdList>();
 456
 457             OrdList l;
 458             typename OrdList::guarded_ptr gp;
 459
 460             static int const nLimit = 20;
 461             typename OrdList::value_type arrItem[nLimit];
 462
 463             {
 464                 int a[nLimit];
 465                 for (int i = 0; i < nLimit; ++i)
 466                     a[i]=i;
 467                 shuffle( a, a + nLimit );
 468
 469                 for (int i = 0; i < nLimit; ++i) {
 470                     arrItem[i].nKey = a[i];
 471                     arrItem[i].nVal = a[i] * 2;
 472                 }
 473
 474                 // extract/get
 475                 for ( int i = 0; i < nLimit; ++i )
 476                     CPPUNIT_ASSERT( l.insert( arrItem[i] ) );
 477
 478                 for ( int i=0; i < nLimit; ++i ) {
 479                     gp = l.get( arrItem[i].nKey );
 480                     CPPUNIT_ASSERT_EX( gp, "i=" << i );
 481                     CPPUNIT_ASSERT( !gp.empty());
 482                     CPPUNIT_CHECK( gp->nKey == arrItem[i].nKey );
 483                     CPPUNIT_CHECK( gp->nVal == arrItem[i].nVal );
 484                     gp.release();
 485
 486                     gp = l.extract( arrItem[i].nKey );
 487                     CPPUNIT_ASSERT_EX( gp, "i=" << i );
 488                     CPPUNIT_ASSERT( !gp.empty());
 489                     CPPUNIT_CHECK( gp->nKey == arrItem[i].nKey );
 490                     CPPUNIT_CHECK( gp->nVal == arrItem[i].nVal );
 491                     gp.release();
 492
 493                     gp = l.get( arrItem[i].nKey );
 494                     CPPUNIT_CHECK( !gp );
 495                     CPPUNIT_CHECK( gp.empty());
 496                     CPPUNIT_CHECK( !l.extract( arrItem[i].nKey ));
 497                     CPPUNIT_CHECK( gp.empty());
 498                 }
 499                 CPPUNIT_ASSERT( l.empty() );
 500                 CPPUNIT_ASSERT( !l.get( nLimit/2 ));
 501                 CPPUNIT_ASSERT( gp.empty());
 502                 CPPUNIT_ASSERT( !l.extract( nLimit/2 ));
 503                 CPPUNIT_ASSERT( gp.empty());
 504
 505                 // Apply retired pointer
 506                 OrdList::gc::force_dispose();
 507
 508                 // extract_with/get_with
 509                 for ( int i = 0; i < nLimit; ++i )
 510                     CPPUNIT_ASSERT( l.insert( arrItem[i] ) );
 511
 512                 for ( int i=0; i < nLimit; ++i ) {
 513                     other_item itm( arrItem[i].nKey );
 514                     gp = l.get_with( itm, other_less() );
 515                     CPPUNIT_ASSERT_EX( gp, "i=" << i );
 516                     CPPUNIT_ASSERT( !gp.empty());
 517                     CPPUNIT_CHECK( gp->nKey == arrItem[i].nKey );
 518                     CPPUNIT_CHECK( gp->nVal == arrItem[i].nVal );
 519                     gp.release();
 520
 521                     gp = l.extract_with( itm, other_less() );
 522                     CPPUNIT_ASSERT_EX( gp, "i=" << i );
 523                     CPPUNIT_ASSERT( !gp.empty());
 524                     CPPUNIT_CHECK( gp->nKey == arrItem[i].nKey );
 525                     CPPUNIT_CHECK( gp->nVal == arrItem[i].nVal );
 526                     gp.release();
 527
 528                     gp = l.get_with( itm, other_less() );
 529                     CPPUNIT_CHECK( !gp );
 530                     CPPUNIT_CHECK( gp.empty());
 531                     CPPUNIT_CHECK( !l.extract_with( itm, other_less() ));
 532                     CPPUNIT_CHECK( gp.empty());
 533                 }
 534                 CPPUNIT_ASSERT( l.empty() );
 535                 CPPUNIT_ASSERT( !l.get_with( other_item(nLimit/2), other_less() ));
 536                 CPPUNIT_ASSERT( gp.empty());
 537                 CPPUNIT_ASSERT( !l.extract_with( other_item(nLimit/2), other_less() ));
 538                 CPPUNIT_ASSERT( gp.empty());
 539
 540                 // Apply retired pointer
 541                 OrdList::gc::force_dispose();
 542
 543                 for ( int i=0; i < nLimit; i++ ) {
 544                     CPPUNIT_ASSERT( arrItem[i].s.nDisposeCount == 2 );
 545                 }
 546             }
 547         }
 548
 549         template <class OrdList>
 550         void test_rcu_int()
 551         {
 552             test_int_common<OrdList>();
 553
 554             OrdList l;
 555             static int const nLimit = 20;
 556             typename OrdList::value_type arrItem[nLimit];
 557
 558             typedef typename OrdList::rcu_lock rcu_lock;
 559             typedef typename OrdList::value_type value_type;
 560             typedef typename OrdList::gc rcu_type;
 561
 562             {
 563                 int a[nLimit];
 564                 for (int i = 0; i < nLimit; ++i)
 565                     a[i]=i;
 566                 shuffle( a, a + nLimit );
 567
 568                 for (int i = 0; i < nLimit; ++i) {
 569                     arrItem[i].nKey = a[i];
 570                     arrItem[i].nVal = a[i] * 2;
 571                 }
 572
 573                 // extract/get
 574                 for ( int i = 0; i < nLimit; ++i )
 575                     CPPUNIT_ASSERT( l.insert( arrItem[i] ) );
 576
 577                 typename OrdList::exempt_ptr ep;
 578
 579                 for ( int i = 0; i < nLimit; ++i ) {
 580                     {
 581                         rcu_lock lock;
 582                         value_type * pGet = l.get( a[i] );
 583                         CPPUNIT_ASSERT( pGet != nullptr );
 584                         CPPUNIT_CHECK( pGet->nKey == a[i] );
 585                         CPPUNIT_CHECK( pGet->nVal == a[i] * 2 );
 586                     }
 587
 588                     {
 589                         rcu_lock lock;
 590                         ep = l.extract( a[i] );
 591                         CPPUNIT_ASSERT( ep );
 592                         CPPUNIT_ASSERT( !ep.empty() );
 593                         CPPUNIT_CHECK( ep->nKey == a[i] );
 594                         CPPUNIT_CHECK( (*ep).nVal == a[i] * 2 );
 595                     }
 596                     ep.release();
 597
 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
 632                     {
 633                         rcu_lock lock;
 634                         ep = l.extract_with( itm, other_less() );
 635                         CPPUNIT_ASSERT( ep );
 636                         CPPUNIT_ASSERT( !ep.empty() );
 637                         CPPUNIT_CHECK( ep->nKey == a[i] );
 638                         CPPUNIT_CHECK( ep->nVal == a[i] * 2 );
 639                     }
 640                     ep.release();
 641
 642                     {
 643                         rcu_lock lock;
 644                         CPPUNIT_CHECK( l.get_with( itm, other_less() ) == nullptr );
 645                         ep = l.extract_with( itm, other_less() );
 646                         CPPUNIT_CHECK( !ep );
 647                         CPPUNIT_CHECK( ep.empty() );
 648                     }
 649                 }
 650                 CPPUNIT_ASSERT( l.empty() );
 651
 652                 {
 653                     rcu_lock lock;
 654                     CPPUNIT_CHECK( l.get_with( other_item( 0 ), other_less() ) == nullptr );
 655                     CPPUNIT_CHECK( !l.extract_with( other_item(0), other_less() ));
 656                     CPPUNIT_CHECK( ep.empty() );
 657                 }
 658                 // Apply retired pointer
 659                 OrdList::gc::force_dispose();
 660             }
 661         }
 662
 663         template <class OrdList>
 664         void test_nogc_int()
 665         {
 666             typedef typename OrdList::value_type    value_type;
 667             {
 668                 value_type v1( 10, 50 );
 669                 value_type v2( 5, 25  );
 670                 value_type v3( 20, 100 );
 671                 {
 672                     OrdList l;
 673                     CPPUNIT_ASSERT( l.empty() );
 674
 675                     CPPUNIT_ASSERT( l.insert( v1 ))     ;   // true
 676                     CPPUNIT_ASSERT( l.find( v1.key() ) == &v1 );
 677
 678                     CPPUNIT_ASSERT( v1.s.nFindCall == 0 );
 679                     CPPUNIT_ASSERT( l.find( v1.key(), find_functor() ));
 680                     CPPUNIT_ASSERT( v1.s.nFindCall == 1 );
 681
 682                     CPPUNIT_ASSERT( l.find_with( v2.key(), less<value_type>() ) == nullptr );
 683                     CPPUNIT_ASSERT( !l.find_with( v3.key(), less<value_type>(), find_functor() ));
 684                     CPPUNIT_ASSERT( !l.empty() );
 685
 686                     CPPUNIT_ASSERT( !l.insert( v1 ))    ;   // assertion "is_empty" is not raised since pNext is nullptr
 687
 688                     {
 689                         value_type v( v1 );
 690                         CPPUNIT_ASSERT( !l.insert( v )) ;   // false
 691                     }
 692
 693                     std::pair<bool, bool> ret = l.ensure( v2, ensure_functor() );
 694                     CPPUNIT_ASSERT( ret.first );
 695                     CPPUNIT_ASSERT( ret.second );
 696                     CPPUNIT_ASSERT( v2.s.nEnsureNewCall == 1 );
 697                     CPPUNIT_ASSERT( v2.s.nEnsureExistsCall == 0 );
 698
 699                     //CPPUNIT_ASSERT( !l.insert( v2 ))    ;   // assertion "is_empty"
 700
 701                     CPPUNIT_ASSERT( l.find( v1.key() ) == &v1 ) ;   // true
 702
 703                     CPPUNIT_ASSERT( v1.s.nFindCall == 1 );
 704                     CPPUNIT_ASSERT( l.find( v1.key(), find_functor() ));
 705                     CPPUNIT_ASSERT( v1.s.nFindCall == 2 );
 706
 707                     CPPUNIT_ASSERT( l.find( v2.key() ) == &v2 );
 708
 709                     CPPUNIT_ASSERT( v2.s.nFindCall == 0 );
 710                     CPPUNIT_ASSERT( l.find( v2.key(), find_functor() ));
 711                     CPPUNIT_ASSERT( v2.s.nFindCall == 1 );
 712
 713                     CPPUNIT_ASSERT( !l.find( v3.key() ));
 714
 715                     {
 716                         value_type v( v2 );
 717                         ret = l.ensure( v, ensure_functor() );
 718
 719                         CPPUNIT_ASSERT( ret.first );
 720                         CPPUNIT_ASSERT( !ret.second );
 721                         CPPUNIT_ASSERT( v2.s.nEnsureExistsCall == 1 );
 722                         CPPUNIT_ASSERT( v.s.nEnsureExistsCall == 0 && v.s.nEnsureNewCall == 0 );
 723                     }
 724
 725                     CPPUNIT_ASSERT( !l.empty() );
 726
 727                     CPPUNIT_ASSERT( l.insert( v3 ))     ;   // true
 728                     CPPUNIT_ASSERT( l.find( v3.key() ) == &v3 );
 729
 730                     CPPUNIT_ASSERT( v3.s.nFindCall == 0 );
 731                     CPPUNIT_ASSERT( l.find( v3.key(), find_functor() ));
 732                     CPPUNIT_ASSERT( v3.s.nFindCall == 1 );
 733
 734                     {
 735                         typename OrdList::iterator it = l.begin();
 736                         typename OrdList::const_iterator cit = l.cbegin();
 737                         CPPUNIT_ASSERT( it != l.end() );
 738                         CPPUNIT_ASSERT( it != l.cend() );
 739                         CPPUNIT_ASSERT( cit != l.end() );
 740                         CPPUNIT_ASSERT( cit != l.cend() );
 741                         CPPUNIT_ASSERT( cit == it );
 742
 743                         CPPUNIT_ASSERT( it->nKey == v2.nKey );
 744                         CPPUNIT_ASSERT( it->nVal == v2.nVal );
 745                         CPPUNIT_ASSERT( ++it != l.end() );
 746                         CPPUNIT_ASSERT( it->nKey == v1.nKey );
 747                         CPPUNIT_ASSERT( it->nVal == v1.nVal );
 748                         CPPUNIT_ASSERT( it++ != l.end() );
 749                         CPPUNIT_ASSERT( it->nKey == v3.nKey );
 750                         CPPUNIT_ASSERT( it->nVal == v3.nVal );
 751                         CPPUNIT_ASSERT( it++ != l.end() );
 752                         CPPUNIT_ASSERT( it == l.end() );
 753                     }
 754
 755                     {
 756                         OrdList const & lref = l;
 757                         typename OrdList::const_iterator it = lref.begin();
 758                         CPPUNIT_ASSERT( it != l.end() );
 759                         CPPUNIT_ASSERT( it->nKey == v2.nKey );
 760                         CPPUNIT_ASSERT( it->nVal == v2.nVal );
 761                         CPPUNIT_ASSERT( ++it != lref.end() );
 762                         CPPUNIT_ASSERT( it->nKey == v1.nKey );
 763                         CPPUNIT_ASSERT( it->nVal == v1.nVal );
 764                         CPPUNIT_ASSERT( it++ != l.end() );
 765                         CPPUNIT_ASSERT( it->nKey == v3.nKey );
 766                         CPPUNIT_ASSERT( it->nVal == v3.nVal );
 767                         CPPUNIT_ASSERT( it++ != lref.end() );
 768                         CPPUNIT_ASSERT( it == l.end() );
 769                     }
 770                 }
 771
 772                 // Disposer called on list destruction
 773                 CPPUNIT_ASSERT( v1.s.nDisposeCount == 1 );
 774                 CPPUNIT_ASSERT( v2.s.nDisposeCount == 1 );
 775                 CPPUNIT_ASSERT( v3.s.nDisposeCount == 1 );
 776             }
 777         }
 778
 779         void HP_base_cmp();
 780         void HP_base_less();
 781         void HP_base_cmpmix();
 782         void HP_base_ic();
 783         void HP_member_cmp();
 784         void HP_member_less();
 785         void HP_member_cmpmix();
 786         void HP_member_ic();
 787
 788         void DHP_base_cmp();
 789         void DHP_base_less();
 790         void DHP_base_cmpmix();
 791         void DHP_base_ic();
 792         void DHP_member_cmp();
 793         void DHP_member_less();
 794         void DHP_member_cmpmix();
 795         void DHP_member_ic();
 796
 797         void RCU_GPI_base_cmp();
 798         void RCU_GPI_base_less();
 799         void RCU_GPI_base_cmpmix();
 800         void RCU_GPI_base_ic();
 801         void RCU_GPI_member_cmp();
 802         void RCU_GPI_member_less();
 803         void RCU_GPI_member_cmpmix();
 804         void RCU_GPI_member_ic();
 805
 806         void RCU_GPB_base_cmp();
 807         void RCU_GPB_base_less();
 808         void RCU_GPB_base_cmpmix();
 809         void RCU_GPB_base_ic();
 810         void RCU_GPB_member_cmp();
 811         void RCU_GPB_member_less();
 812         void RCU_GPB_member_cmpmix();
 813         void RCU_GPB_member_ic();
 814
 815         void RCU_GPT_base_cmp();
 816         void RCU_GPT_base_less();
 817         void RCU_GPT_base_cmpmix();
 818         void RCU_GPT_base_ic();
 819         void RCU_GPT_member_cmp();
 820         void RCU_GPT_member_less();
 821         void RCU_GPT_member_cmpmix();
 822         void RCU_GPT_member_ic();
 823
 824         void RCU_SHB_base_cmp();
 825         void RCU_SHB_base_less();
 826         void RCU_SHB_base_cmpmix();
 827         void RCU_SHB_base_ic();
 828         void RCU_SHB_member_cmp();
 829         void RCU_SHB_member_less();
 830         void RCU_SHB_member_cmpmix();
 831         void RCU_SHB_member_ic();
 832
 833         void RCU_SHT_base_cmp();
 834         void RCU_SHT_base_less();
 835         void RCU_SHT_base_cmpmix();
 836         void RCU_SHT_base_ic();
 837         void RCU_SHT_member_cmp();
 838         void RCU_SHT_member_less();
 839         void RCU_SHT_member_cmpmix();
 840         void RCU_SHT_member_ic();
 841
 842         void nogc_base_cmp();
 843         void nogc_base_less();
 844         void nogc_base_cmpmix();
 845         void nogc_base_ic();
 846         void nogc_member_cmp();
 847         void nogc_member_less();
 848         void nogc_member_cmpmix();
 849         void nogc_member_ic();
 850
 851
 852         CPPUNIT_TEST_SUITE(IntrusiveMichaelListHeaderTest)
 853             CPPUNIT_TEST(HP_base_cmp)
 854             CPPUNIT_TEST(HP_base_less)
 855             CPPUNIT_TEST(HP_base_cmpmix)
 856             CPPUNIT_TEST(HP_base_ic)
 857             CPPUNIT_TEST(HP_member_cmp)
 858             CPPUNIT_TEST(HP_member_less)
 859             CPPUNIT_TEST(HP_member_cmpmix)
 860             CPPUNIT_TEST(HP_member_ic)
 861
 862             CPPUNIT_TEST(DHP_base_cmp)
 863             CPPUNIT_TEST(DHP_base_less)
 864             CPPUNIT_TEST(DHP_base_cmpmix)
 865             CPPUNIT_TEST(DHP_base_ic)
 866             CPPUNIT_TEST(DHP_member_cmp)
 867             CPPUNIT_TEST(DHP_member_less)
 868             CPPUNIT_TEST(DHP_member_cmpmix)
 869             CPPUNIT_TEST(DHP_member_ic)
 870
 871             CPPUNIT_TEST(RCU_GPI_base_cmp)
 872             CPPUNIT_TEST(RCU_GPI_base_less)
 873             CPPUNIT_TEST(RCU_GPI_base_cmpmix)
 874             CPPUNIT_TEST(RCU_GPI_base_ic)
 875             CPPUNIT_TEST(RCU_GPI_member_cmp)
 876             CPPUNIT_TEST(RCU_GPI_member_less)
 877             CPPUNIT_TEST(RCU_GPI_member_cmpmix)
 878             CPPUNIT_TEST(RCU_GPI_member_ic)
 879
 880             CPPUNIT_TEST(RCU_GPB_base_cmp)
 881             CPPUNIT_TEST(RCU_GPB_base_less)
 882             CPPUNIT_TEST(RCU_GPB_base_cmpmix)
 883             CPPUNIT_TEST(RCU_GPB_base_ic)
 884             CPPUNIT_TEST(RCU_GPB_member_cmp)
 885             CPPUNIT_TEST(RCU_GPB_member_less)
 886             CPPUNIT_TEST(RCU_GPB_member_cmpmix)
 887             CPPUNIT_TEST(RCU_GPB_member_ic)
 888
 889             CPPUNIT_TEST(RCU_GPT_base_cmp)
 890             CPPUNIT_TEST(RCU_GPT_base_less)
 891             CPPUNIT_TEST(RCU_GPT_base_cmpmix)
 892             CPPUNIT_TEST(RCU_GPT_base_ic)
 893             CPPUNIT_TEST(RCU_GPT_member_cmp)
 894             CPPUNIT_TEST(RCU_GPT_member_less)
 895             CPPUNIT_TEST(RCU_GPT_member_cmpmix)
 896             CPPUNIT_TEST(RCU_GPT_member_ic)
 897
 898             CPPUNIT_TEST(nogc_base_cmp)
 899             CPPUNIT_TEST(nogc_base_less)
 900             CPPUNIT_TEST(nogc_base_cmpmix)
 901             CPPUNIT_TEST(nogc_base_ic)
 902             CPPUNIT_TEST(nogc_member_cmp)
 903             CPPUNIT_TEST(nogc_member_less)
 904             CPPUNIT_TEST(nogc_member_cmpmix)
 905             CPPUNIT_TEST(nogc_member_ic)
 906
 907         CPPUNIT_TEST_SUITE_END()
 908     };
 909 }   // namespace ordlist
 910
 911 #endif // CDSTEST_HDR_INTRUSIVE_MICHAEL_H