tests/test-hdr/ordered_list/hdr_intrusive_michael.h

   1 //$$CDS-header$$
   2
   3 #include "cppunit/cppunit_proxy.h"
   4 #include <cds/intrusive/details/michael_list_base.h>
   5
   6 namespace ordlist {
   7     namespace ci = cds::intrusive;
   8     namespace co = cds::opt;
   9
  10     class IntrusiveMichaelListHeaderTest: public CppUnitMini::TestCase
  11     {
  12     public:
  13
  14         struct stat {
  15             int nDisposeCount;
  16             int nEnsureExistsCall;
  17             int nEnsureNewCall;
  18             int nFindCall;
  19             int nEraseCall;
  20
  21             stat()
  22                 : nDisposeCount(0)
  23                 , nEnsureExistsCall(0)
  24                 , nEnsureNewCall(0)
  25                 , nFindCall(0)
  26                 , nEraseCall(0)
  27             {}
  28
  29             stat( const stat& s )
  30             {
  31                 *this = s;
  32             }
  33
  34             stat& operator =(const stat& s)
  35             {
  36                 memcpy( this, &s, sizeof(s));
  37                 return *this;
  38             }
  39         };
  40
  41         template <typename GC>
  42         struct base_int_item: public ci::michael_list::node< GC >
  43         {
  44             int nKey;
  45             int nVal;
  46
  47             mutable stat    s;
  48
  49             base_int_item()
  50             {}
  51
  52             base_int_item(int key, int val)
  53                 : nKey( key )
  54                 , nVal(val)
  55                 , s()
  56             {}
  57
  58             base_int_item(const base_int_item& v )
  59                 : nKey( v.nKey )
  60                 , nVal( v.nVal )
  61                 , s()
  62             {}
  63
  64             const int& key() const
  65             {
  66                 return nKey;
  67             }
  68         };
  69
  70         template <typename GC>
  71         struct member_int_item
  72         {
  73             int nKey;
  74             int nVal;
  75
  76             ci::michael_list::node< GC > hMember;
  77
  78             mutable stat s;
  79
  80             member_int_item()
  81             {}
  82
  83             member_int_item(int key, int val)
  84                 : nKey( key )
  85                 , nVal(val)
  86                 , s()
  87             {}
  88
  89             member_int_item(const member_int_item& v )
  90                 : nKey( v.nKey )
  91                 , nVal( v.nVal )
  92                 , s()
  93             {}
  94
  95             const int& key() const
  96             {
  97                 return nKey;
  98             }
  99         };
 100
 101         template <typename T>
 102         struct less
 103         {
 104             bool operator ()(const T& v1, const T& v2 ) const
 105             {
 106                 return v1.key() < v2.key();
 107             }
 108
 109             template <typename Q>
 110             bool operator ()(const T& v1, const Q& v2 ) const
 111             {
 112                 return v1.key() < v2;
 113             }
 114
 115             template <typename Q>
 116             bool operator ()(const Q& v1, const T& v2 ) const
 117             {
 118                 return v1 < v2.key();
 119             }
 120         };
 121
 122         struct other_item {
 123             int nKey;
 124
 125             other_item( int n )
 126                 : nKey(n)
 127             {}
 128         };
 129
 130         struct other_less {
 131             template <typename T, typename Q>
 132             bool operator()( T const& i1, Q const& i2) const
 133             {
 134                 return i1.nKey < i2.nKey;
 135             }
 136         };
 137
 138         template <typename T>
 139         struct cmp {
 140             int operator ()(const T& v1, const T& v2 ) const
 141             {
 142                 if ( v1.key() < v2.key() )
 143                     return -1;
 144                 return v1.key() > v2.key() ? 1 : 0;
 145             }
 146
 147             template <typename Q>
 148             int operator ()(const T& v1, const Q& v2 ) const
 149             {
 150                 if ( v1.key() < v2 )
 151                     return -1;
 152                 return v1.key() > v2 ? 1 : 0;
 153             }
 154
 155             template <typename Q>
 156             int operator ()(const Q& v1, const T& v2 ) const
 157             {
 158                 if ( v1 < v2.key() )
 159                     return -1;
 160                 return v1 > v2.key() ? 1 : 0;
 161             }
 162         };
 163
 164         struct faked_disposer
 165         {
 166             template <typename T>
 167             void operator ()( T * p )
 168             {
 169                 ++p->s.nDisposeCount;
 170             }
 171         };
 172
 173         struct ensure_functor
 174         {
 175             template <typename T>
 176             void operator ()(bool bNew, T& item, T& val )
 177             {
 178                 if ( bNew )
 179                     ++item.s.nEnsureNewCall;
 180                 else
 181                     ++item.s.nEnsureExistsCall;
 182             }
 183         };
 184
 185         struct find_functor
 186         {
 187             template <typename T, typename Q>
 188             void operator ()( T& item, Q& val )
 189             {
 190                 ++item.s.nFindCall;
 191             }
 192         };
 193
 194         struct erase_functor
 195         {
 196             template <typename T>
 197             void operator()( T const& item )
 198             {
 199                 item.s.nEraseCall++;
 200             }
 201         };
 202
 203         template <class OrdList>
 204         void test_int_common()
 205         {
 206             typedef typename OrdList::value_type    value_type;
 207
 208             value_type v1( 10, 50 );
 209             value_type v2( 5, 25  );
 210             value_type v3( 20, 100 );
 211             {
 212                 OrdList l;
 213                 CPPUNIT_ASSERT( l.empty() );
 214
 215                 CPPUNIT_ASSERT( l.insert( v1 ))     ;   // true
 216                 CPPUNIT_ASSERT( l.find( v1.key() ));
 217
 218                 CPPUNIT_ASSERT( v1.s.nFindCall == 0 );
 219                 CPPUNIT_ASSERT( l.find( v1.key(), find_functor() ));
 220                 CPPUNIT_ASSERT( v1.s.nFindCall == 1 );
 221
 222                 CPPUNIT_ASSERT( !l.find( v2.key() ));
 223                 CPPUNIT_ASSERT( !l.find_with( v3.key(), less<value_type>() ));
 224                 CPPUNIT_ASSERT( !l.empty() );
 225
 226                 CPPUNIT_ASSERT( !l.insert( v1 ))    ;   // assertion "is_empty" is not raised since pNext is nullptr
 227
 228                 {
 229                     value_type v( v1 );
 230                     CPPUNIT_ASSERT( !l.insert( v )) ;   // false
 231                 }
 232
 233                 std::pair<bool, bool> ret = l.ensure( v2, ensure_functor() );
 234                 CPPUNIT_ASSERT( ret.first );
 235                 CPPUNIT_ASSERT( ret.second );
 236                 CPPUNIT_ASSERT( v2.s.nEnsureNewCall == 1 );
 237                 CPPUNIT_ASSERT( v2.s.nEnsureExistsCall == 0 );
 238
 239                 //CPPUNIT_ASSERT( !l.insert( v2 ))    ;   // assertion "is_empty"
 240
 241                 CPPUNIT_ASSERT( l.find_with( v1.key(), less<value_type>() )) ;   // true
 242
 243                 CPPUNIT_ASSERT( v1.s.nFindCall == 1 );
 244                 CPPUNIT_ASSERT( l.find_with( v1.key(), less<value_type>(), find_functor() ));
 245                 CPPUNIT_ASSERT( v1.s.nFindCall == 2 );
 246
 247                 CPPUNIT_ASSERT( l.find( v2.key() ));
 248
 249                 CPPUNIT_ASSERT( v2.s.nFindCall == 0 );
 250                 CPPUNIT_ASSERT( l.find( v2.key(), find_functor() ));
 251                 CPPUNIT_ASSERT( v2.s.nFindCall == 1 );
 252
 253                 CPPUNIT_ASSERT( !l.find( v3.key() ));
 254
 255                 {
 256                     CPPUNIT_ASSERT( v2.s.nEnsureExistsCall == 0 );
 257                     CPPUNIT_ASSERT( v2.s.nEnsureNewCall == 1 );
 258
 259                     value_type v( v2 );
 260                     ret = l.ensure( v, ensure_functor() );
 261
 262                     CPPUNIT_ASSERT( ret.first );
 263                     CPPUNIT_ASSERT( !ret.second );
 264                     CPPUNIT_ASSERT( v2.s.nEnsureExistsCall == 1 );
 265                     CPPUNIT_ASSERT( v2.s.nEnsureNewCall == 1 );
 266                     CPPUNIT_ASSERT( v.s.nEnsureExistsCall == 0 );
 267                     CPPUNIT_ASSERT( v.s.nEnsureNewCall == 0 );
 268                 }
 269
 270                 CPPUNIT_ASSERT( !l.empty() );
 271
 272                 CPPUNIT_ASSERT( l.insert( v3 ))     ;   // true
 273                 CPPUNIT_ASSERT( l.find( v3.key() ));
 274
 275                 CPPUNIT_ASSERT( v3.s.nFindCall == 0 );
 276                 CPPUNIT_ASSERT( l.find( v3.key(), find_functor() ));
 277                 CPPUNIT_ASSERT( v3.s.nFindCall == 1 );
 278
 279                 CPPUNIT_ASSERT( l.unlink( v2 ) );
 280                 CPPUNIT_ASSERT( l.find( v1.key() )) ;   // true
 281                 CPPUNIT_ASSERT( !l.find( v2.key() )) ;   // true
 282                 CPPUNIT_ASSERT( l.find( v3.key() )) ;   // true
 283                 CPPUNIT_ASSERT( !l.empty() );
 284                 CPPUNIT_ASSERT( !l.unlink( v2 ) );
 285
 286                 {
 287                     // v1 key is in the list but v NODE is not in the list
 288                     value_type v( v1 );
 289                     CPPUNIT_ASSERT( !l.unlink( v ) );
 290                 }
 291
 292                 CPPUNIT_ASSERT( l.unlink( v1 ) );
 293                 CPPUNIT_ASSERT( !l.unlink( v1 ) );
 294                 CPPUNIT_ASSERT( !l.find( v1.key() ));
 295                 CPPUNIT_ASSERT( !l.find( v2.key() ));
 296                 CPPUNIT_ASSERT( l.find( v3.key() ));
 297                 CPPUNIT_ASSERT( !l.empty() );
 298                 CPPUNIT_ASSERT( !l.unlink( v1 ) );
 299                 CPPUNIT_ASSERT( !l.unlink( v2 ) );
 300
 301                 CPPUNIT_ASSERT( l.unlink( v3 ) );
 302                 CPPUNIT_ASSERT( !l.find_with( v1.key(), less<value_type>() ));
 303                 CPPUNIT_ASSERT( !l.find_with( v2.key(), less<value_type>(), find_functor() ));
 304                 CPPUNIT_ASSERT( !l.find( v3.key(), find_functor() ));
 305                 CPPUNIT_ASSERT( l.empty() );
 306                 CPPUNIT_ASSERT( !l.unlink( v1 ) );
 307                 CPPUNIT_ASSERT( !l.unlink( v2 ) );
 308                 CPPUNIT_ASSERT( !l.unlink( v3 ) );
 309
 310                 // Apply retired pointer to clean links
 311                 OrdList::gc::force_dispose();
 312
 313                 stat s( v3.s );
 314                 ret = l.ensure( v3, ensure_functor() );
 315                 CPPUNIT_ASSERT( ret.first );
 316                 CPPUNIT_ASSERT( ret.second );
 317                 CPPUNIT_ASSERT( v3.s.nEnsureNewCall == s.nEnsureNewCall + 1);
 318                 CPPUNIT_ASSERT( v3.s.nEnsureExistsCall == s.nEnsureExistsCall );
 319                 CPPUNIT_ASSERT( !l.empty() );
 320
 321                 s = v2.s;
 322                 ret = l.ensure( v2, ensure_functor() );
 323                 CPPUNIT_ASSERT( ret.first );
 324                 CPPUNIT_ASSERT( ret.second );
 325                 CPPUNIT_ASSERT( v2.s.nEnsureNewCall == s.nEnsureNewCall + 1);
 326                 CPPUNIT_ASSERT( v2.s.nEnsureExistsCall == s.nEnsureExistsCall );
 327                 CPPUNIT_ASSERT( !l.empty() );
 328
 329                 s = v1.s;
 330                 ret = l.ensure( v1, ensure_functor() );
 331                 CPPUNIT_ASSERT( ret.first );
 332                 CPPUNIT_ASSERT( ret.second );
 333                 CPPUNIT_ASSERT( v1.s.nEnsureNewCall == s.nEnsureNewCall + 1);
 334                 CPPUNIT_ASSERT( v1.s.nEnsureExistsCall == s.nEnsureExistsCall );
 335                 CPPUNIT_ASSERT( !l.empty() );
 336
 337                 // Erase test
 338                 CPPUNIT_ASSERT( v1.s.nEraseCall == 0 );
 339                 CPPUNIT_ASSERT( l.erase( v1.key(), erase_functor()) );
 340                 CPPUNIT_ASSERT( v1.s.nEraseCall == 1 );
 341                 //CPPUNIT_ASSERT( v1.s.nDisposeCount == 0 );
 342                 CPPUNIT_ASSERT( !l.empty() );
 343
 344                 CPPUNIT_ASSERT( l.erase_with( v2.key(), less<value_type>() ) );
 345                 CPPUNIT_ASSERT( !l.erase( v2.key()));
 346                 //CPPUNIT_ASSERT( v2.s.nDisposeCount == 0 );
 347                 CPPUNIT_ASSERT( !l.empty() );
 348
 349                 CPPUNIT_ASSERT( v2.s.nEraseCall == 0 );
 350                 CPPUNIT_ASSERT( !l.erase( v2, erase_functor() ));
 351                 CPPUNIT_ASSERT( v2.s.nEraseCall == 0 );
 352                 CPPUNIT_ASSERT( !l.erase( v1 ));
 353                 //CPPUNIT_ASSERT( v2.s.nDisposeCount == 0 );
 354                 CPPUNIT_ASSERT( !l.empty() );
 355
 356                 CPPUNIT_ASSERT( v3.s.nEraseCall == 0 );
 357                 CPPUNIT_ASSERT( l.erase_with( v3, less<value_type>(), erase_functor() ));
 358                 CPPUNIT_ASSERT( v3.s.nEraseCall == 1 );
 359                 //CPPUNIT_ASSERT( v3.s.nDisposeCount == 0 );
 360                 CPPUNIT_ASSERT( l.empty() );
 361
 362                 // Apply retired pointer to clean links
 363                 OrdList::gc::force_dispose();
 364
 365                 // Unlink test
 366                 CPPUNIT_ASSERT( l.insert( v1 ));
 367                 CPPUNIT_ASSERT( l.insert( v3 ));
 368                 CPPUNIT_ASSERT( !l.empty() );
 369                 CPPUNIT_ASSERT( !l.unlink( v2 ));
 370                 CPPUNIT_ASSERT( l.unlink( v1 ));
 371                 CPPUNIT_ASSERT( !l.unlink( v1 ));
 372                 CPPUNIT_ASSERT( l.unlink( v3 ));
 373                 CPPUNIT_ASSERT( !l.unlink( v3 ));
 374                 CPPUNIT_ASSERT( l.empty() );
 375
 376                 // Apply retired pointer
 377                 OrdList::gc::force_dispose();
 378                 CPPUNIT_ASSERT( v1.s.nDisposeCount == 3 );
 379                 CPPUNIT_ASSERT( v2.s.nDisposeCount == 2 );
 380                 CPPUNIT_ASSERT( v3.s.nDisposeCount == 3 );
 381
 382                 // Destructor test (call disposer)
 383                 CPPUNIT_ASSERT( l.insert( v1 ));
 384                 CPPUNIT_ASSERT( l.insert( v3 ));
 385                 CPPUNIT_ASSERT( l.insert( v2 ));
 386
 387                 // Iterator test
 388                 // begin/end
 389                 {
 390                     typename OrdList::iterator it = l.begin();
 391                     typename OrdList::const_iterator cit = l.cbegin();
 392                     CPPUNIT_ASSERT( it != l.end() );
 393                     CPPUNIT_ASSERT( it != l.cend() );
 394                     CPPUNIT_ASSERT( cit != l.end() );
 395                     CPPUNIT_ASSERT( cit != l.cend() );
 396                     CPPUNIT_ASSERT( cit == it );
 397
 398                     CPPUNIT_ASSERT( it->nKey == v2.nKey );
 399                     CPPUNIT_ASSERT( it->nVal == v2.nVal );
 400                     CPPUNIT_ASSERT( ++it != l.end() );
 401                     CPPUNIT_ASSERT( it->nKey == v1.nKey );
 402                     CPPUNIT_ASSERT( it->nVal == v1.nVal );
 403                     CPPUNIT_ASSERT( ++it != l.end() );
 404                     CPPUNIT_ASSERT( it->nKey == v3.nKey );
 405                     CPPUNIT_ASSERT( it->nVal == v3.nVal );
 406                     CPPUNIT_ASSERT( ++it == l.end() );
 407                 }
 408
 409                 // cbegin/cend
 410                 {
 411                     typename OrdList::const_iterator it = l.cbegin();
 412                     CPPUNIT_ASSERT( it != l.cend() );
 413                     CPPUNIT_ASSERT( it->nKey == v2.nKey );
 414                     CPPUNIT_ASSERT( it->nVal == v2.nVal );
 415                     CPPUNIT_ASSERT( ++it != l.cend() );
 416                     CPPUNIT_ASSERT( it->nKey == v1.nKey );
 417                     CPPUNIT_ASSERT( it->nVal == v1.nVal );
 418                     CPPUNIT_ASSERT( ++it != l.cend() );
 419                     CPPUNIT_ASSERT( it->nKey == v3.nKey );
 420                     CPPUNIT_ASSERT( it->nVal == v3.nVal );
 421                     CPPUNIT_ASSERT( ++it == l.cend() );
 422                 }
 423
 424                 // const begin/end
 425                 {
 426                     OrdList const & lref = l;
 427                     typename OrdList::const_iterator it = lref.begin();
 428                     CPPUNIT_ASSERT( it != l.end() );
 429                     CPPUNIT_ASSERT( it->nKey == v2.nKey );
 430                     CPPUNIT_ASSERT( it->nVal == v2.nVal );
 431                     CPPUNIT_ASSERT( ++it != lref.end() );
 432                     CPPUNIT_ASSERT( it->nKey == v1.nKey );
 433                     CPPUNIT_ASSERT( it->nVal == v1.nVal );
 434                     CPPUNIT_ASSERT( ++it != l.end() );
 435                     CPPUNIT_ASSERT( it->nKey == v3.nKey );
 436                     CPPUNIT_ASSERT( it->nVal == v3.nVal );
 437                     CPPUNIT_ASSERT( ++it == l.end() );
 438                 }
 439             }
 440
 441             // Apply retired pointer
 442             OrdList::gc::force_dispose();
 443
 444             CPPUNIT_ASSERT( v1.s.nDisposeCount == 4 );
 445             CPPUNIT_ASSERT( v2.s.nDisposeCount == 3 );
 446             CPPUNIT_ASSERT( v3.s.nDisposeCount == 4 );
 447         }
 448
 449         template <class OrdList>
 450         void test_int()
 451         {
 452             test_int_common<OrdList>();
 453
 454             OrdList l;
 455             typename OrdList::guarded_ptr gp;
 456
 457             static int const nLimit = 20;
 458             typename OrdList::value_type arrItem[nLimit];
 459
 460             {
 461                 int a[nLimit];
 462                 for (int i = 0; i < nLimit; ++i)
 463                     a[i]=i;
 464                 std::random_shuffle( a, a + nLimit );
 465
 466                 for (int i = 0; i < nLimit; ++i) {
 467                     arrItem[i].nKey = a[i];
 468                     arrItem[i].nVal = a[i] * 2;
 469                 }
 470
 471                 // extract/get
 472                 for ( int i = 0; i < nLimit; ++i )
 473                     CPPUNIT_ASSERT( l.insert( arrItem[i] ) );
 474
 475                 for ( int i=0; i < nLimit; ++i ) {
 476                     gp = l.get( arrItem[i].nKey );
 477                     CPPUNIT_ASSERT_EX( gp, "i=" << i );
 478                     CPPUNIT_ASSERT( !gp.empty());
 479                     CPPUNIT_CHECK( gp->nKey == arrItem[i].nKey );
 480                     CPPUNIT_CHECK( gp->nVal == arrItem[i].nVal );
 481                     gp.release();
 482
 483                     gp = l.extract( arrItem[i].nKey );
 484                     CPPUNIT_ASSERT_EX( gp, "i=" << i );
 485                     CPPUNIT_ASSERT( !gp.empty());
 486                     CPPUNIT_CHECK( gp->nKey == arrItem[i].nKey );
 487                     CPPUNIT_CHECK( gp->nVal == arrItem[i].nVal );
 488                     gp.release();
 489
 490                     gp = l.get( arrItem[i].nKey );
 491                     CPPUNIT_CHECK( !gp );
 492                     CPPUNIT_CHECK( gp.empty());
 493                     CPPUNIT_CHECK( !l.extract( arrItem[i].nKey ));
 494                     CPPUNIT_CHECK( gp.empty());
 495                 }
 496                 CPPUNIT_ASSERT( l.empty() );
 497                 CPPUNIT_ASSERT( !l.get( nLimit/2 ));
 498                 CPPUNIT_ASSERT( gp.empty());
 499                 CPPUNIT_ASSERT( !l.extract( nLimit/2 ));
 500                 CPPUNIT_ASSERT( gp.empty());
 501
 502                 // Apply retired pointer
 503                 OrdList::gc::force_dispose();
 504
 505                 // extract_with/get_with
 506                 for ( int i = 0; i < nLimit; ++i )
 507                     CPPUNIT_ASSERT( l.insert( arrItem[i] ) );
 508
 509                 for ( int i=0; i < nLimit; ++i ) {
 510                     other_item itm( arrItem[i].nKey );
 511                     gp = l.get_with( itm, other_less() );
 512                     CPPUNIT_ASSERT_EX( gp, "i=" << i );
 513                     CPPUNIT_ASSERT( !gp.empty());
 514                     CPPUNIT_CHECK( gp->nKey == arrItem[i].nKey );
 515                     CPPUNIT_CHECK( gp->nVal == arrItem[i].nVal );
 516                     gp.release();
 517
 518                     gp = l.extract_with( itm, other_less() );
 519                     CPPUNIT_ASSERT_EX( gp, "i=" << i );
 520                     CPPUNIT_ASSERT( !gp.empty());
 521                     CPPUNIT_CHECK( gp->nKey == arrItem[i].nKey );
 522                     CPPUNIT_CHECK( gp->nVal == arrItem[i].nVal );
 523                     gp.release();
 524
 525                     gp = l.get_with( itm, other_less() );
 526                     CPPUNIT_CHECK( !gp );
 527                     CPPUNIT_CHECK( gp.empty());
 528                     CPPUNIT_CHECK( !l.extract_with( itm, other_less() ));
 529                     CPPUNIT_CHECK( gp.empty());
 530                 }
 531                 CPPUNIT_ASSERT( l.empty() );
 532                 CPPUNIT_ASSERT( !l.get_with( other_item(nLimit/2), other_less() ));
 533                 CPPUNIT_ASSERT( gp.empty());
 534                 CPPUNIT_ASSERT( !l.extract_with( other_item(nLimit/2), other_less() ));
 535                 CPPUNIT_ASSERT( gp.empty());
 536
 537                 // Apply retired pointer
 538                 OrdList::gc::force_dispose();
 539
 540                 for ( int i=0; i < nLimit; i++ ) {
 541                     CPPUNIT_ASSERT( arrItem[i].s.nDisposeCount == 2 );
 542                 }
 543             }
 544         }
 545
 546         template <class OrdList>
 547         void test_rcu_int()
 548         {
 549             test_int_common<OrdList>();
 550
 551             OrdList l;
 552             static int const nLimit = 20;
 553             typename OrdList::value_type arrItem[nLimit];
 554
 555             typedef typename OrdList::rcu_lock rcu_lock;
 556             typedef typename OrdList::value_type value_type;
 557             typedef typename OrdList::gc rcu_type;
 558
 559             {
 560                 int a[nLimit];
 561                 for (int i = 0; i < nLimit; ++i)
 562                     a[i]=i;
 563                 std::random_shuffle( a, a + nLimit );
 564
 565                 for (int i = 0; i < nLimit; ++i) {
 566                     arrItem[i].nKey = a[i];
 567                     arrItem[i].nVal = a[i] * 2;
 568                 }
 569
 570                 // extract/get
 571                 for ( int i = 0; i < nLimit; ++i )
 572                     CPPUNIT_ASSERT( l.insert( arrItem[i] ) );
 573
 574                 typename OrdList::exempt_ptr ep;
 575
 576                 for ( int i = 0; i < nLimit; ++i ) {
 577                     {
 578                         rcu_lock lock;
 579                         value_type * pGet = l.get( a[i] );
 580                         CPPUNIT_ASSERT( pGet != nullptr );
 581                         CPPUNIT_CHECK( pGet->nKey == a[i] );
 582                         CPPUNIT_CHECK( pGet->nVal == a[i] * 2 );
 583                     }
 584
 585                     {
 586                         rcu_lock lock;
 587                         ep = l.extract( a[i] );
 588                         CPPUNIT_ASSERT( ep );
 589                         CPPUNIT_ASSERT( !ep.empty() );
 590                         CPPUNIT_CHECK( ep->nKey == a[i] );
 591                         CPPUNIT_CHECK( (*ep).nVal == a[i] * 2 );
 592                     }
 593                     ep.release();
 594
 595                     {
 596                         rcu_lock lock;
 597                         CPPUNIT_CHECK( l.get( a[i] ) == nullptr );
 598                         CPPUNIT_CHECK( !l.extract( a[i] ));
 599                         CPPUNIT_CHECK( ep.empty() );
 600                     }
 601                 }
 602                 CPPUNIT_ASSERT( l.empty() );
 603
 604                 {
 605                     rcu_lock lock;
 606                     CPPUNIT_CHECK( l.get( a[0] ) == nullptr );
 607                     ep = l.extract( a[0] );
 608                     CPPUNIT_CHECK( !ep );
 609                     CPPUNIT_CHECK( ep.empty() );
 610                 }
 611                 // Apply retired pointer
 612                 OrdList::gc::force_dispose();
 613
 614                 // extract_with/get_with
 615                 for ( int i = 0; i < nLimit; ++i ) {
 616                     CPPUNIT_ASSERT( l.insert( arrItem[i] ) );
 617                 }
 618
 619                 for ( int i = 0; i < nLimit; ++i ) {
 620                     other_item itm( a[i] );
 621                     {
 622                         rcu_lock lock;
 623                         value_type * pGet = l.get_with( itm, other_less() );
 624                         CPPUNIT_ASSERT( pGet != nullptr );
 625                         CPPUNIT_CHECK( pGet->nKey == a[i] );
 626                         CPPUNIT_CHECK( pGet->nVal == a[i] * 2 );
 627                     }
 628
 629                     {
 630                         rcu_lock lock;
 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                     {
 640                         rcu_lock lock;
 641                         CPPUNIT_CHECK( l.get_with( itm, other_less() ) == nullptr );
 642                         ep = l.extract_with( itm, other_less() );
 643                         CPPUNIT_CHECK( !ep );
 644                         CPPUNIT_CHECK( ep.empty() );
 645                     }
 646                 }
 647                 CPPUNIT_ASSERT( l.empty() );
 648
 649                 {
 650                     rcu_lock lock;
 651                     CPPUNIT_CHECK( l.get_with( other_item( 0 ), other_less() ) == nullptr );
 652                     CPPUNIT_CHECK( !l.extract_with( other_item(0), other_less() ));
 653                     CPPUNIT_CHECK( ep.empty() );
 654                 }
 655                 // Apply retired pointer
 656                 OrdList::gc::force_dispose();
 657             }
 658         }
 659
 660         template <class OrdList>
 661         void test_nogc_int()
 662         {
 663             typedef typename OrdList::value_type    value_type;
 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.find( 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.find_with( v2.key(), less<value_type>() ) == nullptr );
 680                     CPPUNIT_ASSERT( !l.find_with( v3.key(), less<value_type>(), find_functor() ));
 681                     CPPUNIT_ASSERT( !l.empty() );
 682
 683                     CPPUNIT_ASSERT( !l.insert( v1 ))    ;   // assertion "is_empty" is not raised since pNext is nullptr
 684
 685                     {
 686                         value_type v( v1 );
 687                         CPPUNIT_ASSERT( !l.insert( v )) ;   // false
 688                     }
 689
 690                     std::pair<bool, bool> ret = l.ensure( v2, ensure_functor() );
 691                     CPPUNIT_ASSERT( ret.first );
 692                     CPPUNIT_ASSERT( ret.second );
 693                     CPPUNIT_ASSERT( v2.s.nEnsureNewCall == 1 );
 694                     CPPUNIT_ASSERT( v2.s.nEnsureExistsCall == 0 );
 695
 696                     //CPPUNIT_ASSERT( !l.insert( v2 ))    ;   // assertion "is_empty"
 697
 698                     CPPUNIT_ASSERT( l.find( 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.find( v2.key() ) == &v2 );
 705
 706                     CPPUNIT_ASSERT( v2.s.nFindCall == 0 );
 707                     CPPUNIT_ASSERT( l.find( v2.key(), find_functor() ));
 708                     CPPUNIT_ASSERT( v2.s.nFindCall == 1 );
 709
 710                     CPPUNIT_ASSERT( !l.find( v3.key() ));
 711
 712                     {
 713                         value_type v( v2 );
 714                         ret = l.ensure( v, ensure_functor() );
 715
 716                         CPPUNIT_ASSERT( ret.first );
 717                         CPPUNIT_ASSERT( !ret.second );
 718                         CPPUNIT_ASSERT( v2.s.nEnsureExistsCall == 1 );
 719                         CPPUNIT_ASSERT( v.s.nEnsureExistsCall == 0 && v.s.nEnsureNewCall == 0 );
 720                     }
 721
 722                     CPPUNIT_ASSERT( !l.empty() );
 723
 724                     CPPUNIT_ASSERT( l.insert( v3 ))     ;   // true
 725                     CPPUNIT_ASSERT( l.find( 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         void HP_base_cmp();
 777         void HP_base_less();
 778         void HP_base_cmpmix();
 779         void HP_base_ic();
 780         void HP_member_cmp();
 781         void HP_member_less();
 782         void HP_member_cmpmix();
 783         void HP_member_ic();
 784
 785         void DHP_base_cmp();
 786         void DHP_base_less();
 787         void DHP_base_cmpmix();
 788         void DHP_base_ic();
 789         void DHP_member_cmp();
 790         void DHP_member_less();
 791         void DHP_member_cmpmix();
 792         void DHP_member_ic();
 793
 794         void RCU_GPI_base_cmp();
 795         void RCU_GPI_base_less();
 796         void RCU_GPI_base_cmpmix();
 797         void RCU_GPI_base_ic();
 798         void RCU_GPI_member_cmp();
 799         void RCU_GPI_member_less();
 800         void RCU_GPI_member_cmpmix();
 801         void RCU_GPI_member_ic();
 802
 803         void RCU_GPB_base_cmp();
 804         void RCU_GPB_base_less();
 805         void RCU_GPB_base_cmpmix();
 806         void RCU_GPB_base_ic();
 807         void RCU_GPB_member_cmp();
 808         void RCU_GPB_member_less();
 809         void RCU_GPB_member_cmpmix();
 810         void RCU_GPB_member_ic();
 811
 812         void RCU_GPT_base_cmp();
 813         void RCU_GPT_base_less();
 814         void RCU_GPT_base_cmpmix();
 815         void RCU_GPT_base_ic();
 816         void RCU_GPT_member_cmp();
 817         void RCU_GPT_member_less();
 818         void RCU_GPT_member_cmpmix();
 819         void RCU_GPT_member_ic();
 820
 821         void RCU_SHB_base_cmp();
 822         void RCU_SHB_base_less();
 823         void RCU_SHB_base_cmpmix();
 824         void RCU_SHB_base_ic();
 825         void RCU_SHB_member_cmp();
 826         void RCU_SHB_member_less();
 827         void RCU_SHB_member_cmpmix();
 828         void RCU_SHB_member_ic();
 829
 830         void RCU_SHT_base_cmp();
 831         void RCU_SHT_base_less();
 832         void RCU_SHT_base_cmpmix();
 833         void RCU_SHT_base_ic();
 834         void RCU_SHT_member_cmp();
 835         void RCU_SHT_member_less();
 836         void RCU_SHT_member_cmpmix();
 837         void RCU_SHT_member_ic();
 838
 839         void nogc_base_cmp();
 840         void nogc_base_less();
 841         void nogc_base_cmpmix();
 842         void nogc_base_ic();
 843         void nogc_member_cmp();
 844         void nogc_member_less();
 845         void nogc_member_cmpmix();
 846         void nogc_member_ic();
 847
 848
 849         CPPUNIT_TEST_SUITE(IntrusiveMichaelListHeaderTest)
 850             CPPUNIT_TEST(HP_base_cmp)
 851             CPPUNIT_TEST(HP_base_less)
 852             CPPUNIT_TEST(HP_base_cmpmix)
 853             CPPUNIT_TEST(HP_base_ic)
 854             CPPUNIT_TEST(HP_member_cmp)
 855             CPPUNIT_TEST(HP_member_less)
 856             CPPUNIT_TEST(HP_member_cmpmix)
 857             CPPUNIT_TEST(HP_member_ic)
 858
 859             CPPUNIT_TEST(DHP_base_cmp)
 860             CPPUNIT_TEST(DHP_base_less)
 861             CPPUNIT_TEST(DHP_base_cmpmix)
 862             CPPUNIT_TEST(DHP_base_ic)
 863             CPPUNIT_TEST(DHP_member_cmp)
 864             CPPUNIT_TEST(DHP_member_less)
 865             CPPUNIT_TEST(DHP_member_cmpmix)
 866             CPPUNIT_TEST(DHP_member_ic)
 867
 868             CPPUNIT_TEST(RCU_GPI_base_cmp)
 869             CPPUNIT_TEST(RCU_GPI_base_less)
 870             CPPUNIT_TEST(RCU_GPI_base_cmpmix)
 871             CPPUNIT_TEST(RCU_GPI_base_ic)
 872             CPPUNIT_TEST(RCU_GPI_member_cmp)
 873             CPPUNIT_TEST(RCU_GPI_member_less)
 874             CPPUNIT_TEST(RCU_GPI_member_cmpmix)
 875             CPPUNIT_TEST(RCU_GPI_member_ic)
 876
 877             CPPUNIT_TEST(RCU_GPB_base_cmp)
 878             CPPUNIT_TEST(RCU_GPB_base_less)
 879             CPPUNIT_TEST(RCU_GPB_base_cmpmix)
 880             CPPUNIT_TEST(RCU_GPB_base_ic)
 881             CPPUNIT_TEST(RCU_GPB_member_cmp)
 882             CPPUNIT_TEST(RCU_GPB_member_less)
 883             CPPUNIT_TEST(RCU_GPB_member_cmpmix)
 884             CPPUNIT_TEST(RCU_GPB_member_ic)
 885
 886             CPPUNIT_TEST(RCU_GPT_base_cmp)
 887             CPPUNIT_TEST(RCU_GPT_base_less)
 888             CPPUNIT_TEST(RCU_GPT_base_cmpmix)
 889             CPPUNIT_TEST(RCU_GPT_base_ic)
 890             CPPUNIT_TEST(RCU_GPT_member_cmp)
 891             CPPUNIT_TEST(RCU_GPT_member_less)
 892             CPPUNIT_TEST(RCU_GPT_member_cmpmix)
 893             CPPUNIT_TEST(RCU_GPT_member_ic)
 894
 895             CPPUNIT_TEST(nogc_base_cmp)
 896             CPPUNIT_TEST(nogc_base_less)
 897             CPPUNIT_TEST(nogc_base_cmpmix)
 898             CPPUNIT_TEST(nogc_base_ic)
 899             CPPUNIT_TEST(nogc_member_cmp)
 900             CPPUNIT_TEST(nogc_member_less)
 901             CPPUNIT_TEST(nogc_member_cmpmix)
 902             CPPUNIT_TEST(nogc_member_ic)
 903
 904         CPPUNIT_TEST_SUITE_END()
 905     };
 906 }   // namespace ordlist