tests/test-hdr/list/hdr_intrusive_michael.h

   1 /*
   2     This file is a part of libcds - Concurrent Data Structures library
   3
   4     (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016
   5
   6     Source code repo: http://github.com/khizmax/libcds/
   7     Download: http://sourceforge.net/projects/libcds/files/
   8
   9     Redistribution and use in source and binary forms, with or without
  10     modification, are permitted provided that the following conditions are met:
  11
  12     * Redistributions of source code must retain the above copyright notice, this
  13       list of conditions and the following disclaimer.
  14
  15     * Redistributions in binary form must reproduce the above copyright notice,
  16       this list of conditions and the following disclaimer in the documentation
  17       and/or other materials provided with the distribution.
  18
  19     THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
  20     AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  21     IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  22     DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
  23     FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  24     DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
  25     SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
  26     CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
  27     OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  28     OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  29 */
  30
  31 #ifndef CDSTEST_HDR_INTRUSIVE_MICHAEL_H
  32 #define CDSTEST_HDR_INTRUSIVE_MICHAEL_H
  33
  34 #include "cppunit/cppunit_proxy.h"
  35 #include <cds/intrusive/details/michael_list_base.h>
  36
  37 namespace ordlist {
  38     namespace ci = cds::intrusive;
  39     namespace co = cds::opt;
  40
  41     class IntrusiveMichaelListHeaderTest: public CppUnitMini::TestCase
  42     {
  43     public:
  44
  45         struct stat {
  46             int nDisposeCount;
  47             int nUpdateExistsCall;
  48             int nUpdateNewCall;
  49             int nFindCall;
  50             int nEraseCall;
  51
  52             stat()
  53                 : nDisposeCount(0)
  54                 , nUpdateExistsCall(0)
  55                 , nUpdateNewCall(0)
  56                 , nFindCall(0)
  57                 , nEraseCall(0)
  58             {}
  59
  60             stat( const stat& s )
  61             {
  62                 *this = s;
  63             }
  64
  65             stat& operator =(const stat& s)
  66             {
  67                 memcpy( this, &s, sizeof(s));
  68                 return *this;
  69             }
  70         };
  71
  72         template <typename GC>
  73         struct base_int_item: public ci::michael_list::node< GC >
  74         {
  75             int nKey;
  76             int nVal;
  77
  78             mutable stat    s;
  79
  80             base_int_item()
  81             {}
  82
  83             base_int_item(int key, int val)
  84                 : nKey( key )
  85                 , nVal(val)
  86                 , s()
  87             {}
  88
  89             base_int_item(const base_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 GC>
 102         struct member_int_item
 103         {
 104             int nKey;
 105             int nVal;
 106
 107             ci::michael_list::node< GC > hMember;
 108
 109             mutable stat s;
 110
 111             member_int_item()
 112             {}
 113
 114             member_int_item(int key, int val)
 115                 : nKey( key )
 116                 , nVal(val)
 117                 , s()
 118             {}
 119
 120             member_int_item(const member_int_item& v )
 121                 : nKey( v.nKey )
 122                 , nVal( v.nVal )
 123                 , s()
 124             {}
 125
 126             const int& key() const
 127             {
 128                 return nKey;
 129             }
 130         };
 131
 132         template <typename T>
 133         struct less
 134         {
 135             bool operator ()(const T& v1, const T& v2 ) const
 136             {
 137                 return v1.key() < v2.key();
 138             }
 139
 140             template <typename Q>
 141             bool operator ()(const T& v1, const Q& v2 ) const
 142             {
 143                 return v1.key() < v2;
 144             }
 145
 146             template <typename Q>
 147             bool operator ()(const Q& v1, const T& v2 ) const
 148             {
 149                 return v1 < v2.key();
 150             }
 151         };
 152
 153         struct other_item {
 154             int nKey;
 155
 156             other_item( int n )
 157                 : nKey(n)
 158             {}
 159         };
 160
 161         struct other_less {
 162             template <typename T, typename Q>
 163             bool operator()( T const& i1, Q const& i2) const
 164             {
 165                 return i1.nKey < i2.nKey;
 166             }
 167         };
 168
 169         template <typename T>
 170         struct cmp {
 171             int operator ()(const T& v1, const T& v2 ) const
 172             {
 173                 if ( v1.key() < v2.key() )
 174                     return -1;
 175                 return v1.key() > v2.key() ? 1 : 0;
 176             }
 177
 178             template <typename Q>
 179             int operator ()(const T& v1, const Q& v2 ) const
 180             {
 181                 if ( v1.key() < v2 )
 182                     return -1;
 183                 return v1.key() > v2 ? 1 : 0;
 184             }
 185
 186             template <typename Q>
 187             int operator ()(const Q& v1, const T& v2 ) const
 188             {
 189                 if ( v1 < v2.key() )
 190                     return -1;
 191                 return v1 > v2.key() ? 1 : 0;
 192             }
 193         };
 194
 195         struct faked_disposer
 196         {
 197             template <typename T>
 198             void operator ()( T * p )
 199             {
 200                 ++p->s.nDisposeCount;
 201             }
 202         };
 203
 204         struct update_functor
 205         {
 206             template <typename T>
 207             void operator ()(bool bNew, T& item, T& /*val*/ )
 208             {
 209                 if ( bNew )
 210                     ++item.s.nUpdateNewCall;
 211                 else
 212                     ++item.s.nUpdateExistsCall;
 213             }
 214         };
 215
 216         struct find_functor
 217         {
 218             template <typename T, typename Q>
 219             void operator ()( T& item, Q& /*val*/ )
 220             {
 221                 ++item.s.nFindCall;
 222             }
 223         };
 224
 225         struct erase_functor
 226         {
 227             template <typename T>
 228             void operator()( T const& item )
 229             {
 230                 item.s.nEraseCall++;
 231             }
 232         };
 233
 234         template <class OrdList>
 235         void test_int_common()
 236         {
 237             typedef typename OrdList::value_type    value_type;
 238
 239             value_type v1( 10, 50 );
 240             value_type v2( 5, 25  );
 241             value_type v3( 20, 100 );
 242             {
 243                 OrdList l;
 244                 CPPUNIT_ASSERT( l.empty() );
 245
 246                 CPPUNIT_ASSERT( l.insert( v1 ))     ;   // true
 247                 CPPUNIT_ASSERT( l.contains( v1.key() ));
 248
 249                 CPPUNIT_ASSERT( v1.s.nFindCall == 0 );
 250                 CPPUNIT_ASSERT( l.find( v1.key(), find_functor() ));
 251                 CPPUNIT_ASSERT( v1.s.nFindCall == 1 );
 252
 253                 CPPUNIT_ASSERT( !l.contains( v2.key() ));
 254                 CPPUNIT_ASSERT( !l.contains( v3.key(), less<value_type>() ));
 255                 CPPUNIT_ASSERT( !l.empty() );
 256
 257                 CPPUNIT_ASSERT( !l.insert( v1 ))    ;   // assertion "is_empty" is not raised since pNext is nullptr
 258
 259                 {
 260                     value_type v( v1 );
 261                     CPPUNIT_ASSERT( !l.insert( v )) ;   // false
 262                 }
 263
 264                 std::pair<bool, bool> ret = l.update( v2, update_functor() );
 265                 CPPUNIT_ASSERT( ret.first );
 266                 CPPUNIT_ASSERT( ret.second );
 267                 CPPUNIT_ASSERT( v2.s.nUpdateNewCall == 1 );
 268                 CPPUNIT_ASSERT( v2.s.nUpdateExistsCall == 0 );
 269
 270                 //CPPUNIT_ASSERT( !l.insert( v2 ))    ;   // assertion "is_empty"
 271
 272                 CPPUNIT_ASSERT( l.contains( v1.key(), less<value_type>() )) ;   // true
 273
 274                 CPPUNIT_ASSERT( v1.s.nFindCall == 1 );
 275                 CPPUNIT_ASSERT( l.find_with( v1.key(), less<value_type>(), find_functor() ));
 276                 CPPUNIT_ASSERT( v1.s.nFindCall == 2 );
 277
 278                 CPPUNIT_ASSERT( l.contains( v2.key() ));
 279
 280                 CPPUNIT_ASSERT( v2.s.nFindCall == 0 );
 281                 CPPUNIT_ASSERT( l.find( v2.key(), find_functor() ));
 282                 CPPUNIT_ASSERT( v2.s.nFindCall == 1 );
 283
 284                 CPPUNIT_ASSERT( !l.contains( v3.key() ));
 285
 286                 {
 287                     CPPUNIT_ASSERT( v2.s.nUpdateExistsCall == 0 );
 288                     CPPUNIT_ASSERT( v2.s.nUpdateNewCall == 1 );
 289
 290                     value_type v( v2 );
 291                     ret = l.update( v, update_functor() );
 292
 293                     CPPUNIT_ASSERT( ret.first );
 294                     CPPUNIT_ASSERT( !ret.second );
 295                     CPPUNIT_ASSERT( v2.s.nUpdateExistsCall == 1 );
 296                     CPPUNIT_ASSERT( v2.s.nUpdateNewCall == 1 );
 297                     CPPUNIT_ASSERT( v.s.nUpdateExistsCall == 0 );
 298                     CPPUNIT_ASSERT( v.s.nUpdateNewCall == 0 );
 299                 }
 300
 301                 CPPUNIT_ASSERT( !l.empty() );
 302
 303                 CPPUNIT_ASSERT( l.insert( v3 ))     ;   // true
 304                 CPPUNIT_ASSERT( l.contains( v3.key() ));
 305
 306                 CPPUNIT_ASSERT( v3.s.nFindCall == 0 );
 307                 CPPUNIT_ASSERT( l.find( v3.key(), find_functor() ));
 308                 CPPUNIT_ASSERT( v3.s.nFindCall == 1 );
 309
 310                 CPPUNIT_ASSERT( l.unlink( v2 ) );
 311                 CPPUNIT_ASSERT( l.contains( v1.key() )) ;   // true
 312                 CPPUNIT_ASSERT( !l.contains( v2.key() )) ;   // true
 313                 CPPUNIT_ASSERT( l.contains( v3.key() )) ;   // true
 314                 CPPUNIT_ASSERT( !l.empty() );
 315                 CPPUNIT_ASSERT( !l.unlink( v2 ) );
 316
 317                 {
 318                     // v1 key is in the list but v NODE is not in the list
 319                     value_type v( v1 );
 320                     CPPUNIT_ASSERT( !l.unlink( v ) );
 321                 }
 322
 323                 CPPUNIT_ASSERT( l.unlink( v1 ) );
 324                 CPPUNIT_ASSERT( !l.unlink( v1 ) );
 325                 CPPUNIT_ASSERT( !l.contains( v1.key() ));
 326                 CPPUNIT_ASSERT( !l.contains( v2.key() ));
 327                 CPPUNIT_ASSERT( l.contains( v3.key() ));
 328                 CPPUNIT_ASSERT( !l.empty() );
 329                 CPPUNIT_ASSERT( !l.unlink( v1 ) );
 330                 CPPUNIT_ASSERT( !l.unlink( v2 ) );
 331
 332                 CPPUNIT_ASSERT( l.unlink( v3 ) );
 333                 CPPUNIT_ASSERT( !l.contains( v1.key(), less<value_type>() ));
 334                 CPPUNIT_ASSERT( !l.find_with( v2.key(), less<value_type>(), find_functor() ));
 335                 CPPUNIT_ASSERT( !l.find( v3.key(), find_functor() ));
 336                 CPPUNIT_ASSERT( l.empty() );
 337                 CPPUNIT_ASSERT( !l.unlink( v1 ) );
 338                 CPPUNIT_ASSERT( !l.unlink( v2 ) );
 339                 CPPUNIT_ASSERT( !l.unlink( v3 ) );
 340
 341                 // Apply retired pointer to clean links
 342                 OrdList::gc::force_dispose();
 343
 344                 stat s( v3.s );
 345                 ret = l.update( v3, update_functor() );
 346                 CPPUNIT_ASSERT( ret.first );
 347                 CPPUNIT_ASSERT( ret.second );
 348                 CPPUNIT_ASSERT( v3.s.nUpdateNewCall == s.nUpdateNewCall + 1);
 349                 CPPUNIT_ASSERT( v3.s.nUpdateExistsCall == s.nUpdateExistsCall );
 350                 CPPUNIT_ASSERT( !l.empty() );
 351
 352                 s = v2.s;
 353                 ret = l.update( v2, update_functor() );
 354                 CPPUNIT_ASSERT( ret.first );
 355                 CPPUNIT_ASSERT( ret.second );
 356                 CPPUNIT_ASSERT( v2.s.nUpdateNewCall == s.nUpdateNewCall + 1);
 357                 CPPUNIT_ASSERT( v2.s.nUpdateExistsCall == s.nUpdateExistsCall );
 358                 CPPUNIT_ASSERT( !l.empty() );
 359
 360                 s = v1.s;
 361                 ret = l.update( v1, update_functor() );
 362                 CPPUNIT_ASSERT( ret.first );
 363                 CPPUNIT_ASSERT( ret.second );
 364                 CPPUNIT_ASSERT( v1.s.nUpdateNewCall == s.nUpdateNewCall + 1);
 365                 CPPUNIT_ASSERT( v1.s.nUpdateExistsCall == s.nUpdateExistsCall );
 366                 CPPUNIT_ASSERT( !l.empty() );
 367
 368                 // Erase test
 369                 CPPUNIT_ASSERT( v1.s.nEraseCall == 0 );
 370                 CPPUNIT_ASSERT( l.erase( v1.key(), erase_functor()) );
 371                 CPPUNIT_ASSERT( v1.s.nEraseCall == 1 );
 372                 //CPPUNIT_ASSERT( v1.s.nDisposeCount == 0 );
 373                 CPPUNIT_ASSERT( !l.empty() );
 374
 375                 CPPUNIT_ASSERT( l.erase_with( v2.key(), less<value_type>() ) );
 376                 CPPUNIT_ASSERT( !l.erase( v2.key()));
 377                 //CPPUNIT_ASSERT( v2.s.nDisposeCount == 0 );
 378                 CPPUNIT_ASSERT( !l.empty() );
 379
 380                 CPPUNIT_ASSERT( v2.s.nEraseCall == 0 );
 381                 CPPUNIT_ASSERT( !l.erase( v2, erase_functor() ));
 382                 CPPUNIT_ASSERT( v2.s.nEraseCall == 0 );
 383                 CPPUNIT_ASSERT( !l.erase( v1 ));
 384                 //CPPUNIT_ASSERT( v2.s.nDisposeCount == 0 );
 385                 CPPUNIT_ASSERT( !l.empty() );
 386
 387                 CPPUNIT_ASSERT( v3.s.nEraseCall == 0 );
 388                 CPPUNIT_ASSERT( l.erase_with( v3, less<value_type>(), erase_functor() ));
 389                 CPPUNIT_ASSERT( v3.s.nEraseCall == 1 );
 390                 //CPPUNIT_ASSERT( v3.s.nDisposeCount == 0 );
 391                 CPPUNIT_ASSERT( l.empty() );
 392
 393                 // Apply retired pointer to clean links
 394                 OrdList::gc::force_dispose();
 395
 396                 // Unlink test
 397                 CPPUNIT_ASSERT( l.insert( v1 ));
 398                 CPPUNIT_ASSERT( l.insert( v3 ));
 399                 CPPUNIT_ASSERT( !l.empty() );
 400                 CPPUNIT_ASSERT( !l.unlink( v2 ));
 401                 CPPUNIT_ASSERT( l.unlink( v1 ));
 402                 CPPUNIT_ASSERT( !l.unlink( v1 ));
 403                 CPPUNIT_ASSERT( l.unlink( v3 ));
 404                 CPPUNIT_ASSERT( !l.unlink( v3 ));
 405                 CPPUNIT_ASSERT( l.empty() );
 406
 407                 // Apply retired pointer
 408                 OrdList::gc::force_dispose();
 409                 CPPUNIT_ASSERT( v1.s.nDisposeCount == 3 );
 410                 CPPUNIT_ASSERT( v2.s.nDisposeCount == 2 );
 411                 CPPUNIT_ASSERT( v3.s.nDisposeCount == 3 );
 412
 413                 // Destructor test (call disposer)
 414                 CPPUNIT_ASSERT( l.insert( v1 ));
 415                 CPPUNIT_ASSERT( l.insert( v3 ));
 416                 CPPUNIT_ASSERT( l.insert( v2 ));
 417
 418                 // Iterator test
 419                 // begin/end
 420                 {
 421                     typename OrdList::iterator it = l.begin();
 422                     typename OrdList::const_iterator cit = l.cbegin();
 423                     CPPUNIT_ASSERT( it != l.end() );
 424                     CPPUNIT_ASSERT( it != l.cend() );
 425                     CPPUNIT_ASSERT( cit != l.end() );
 426                     CPPUNIT_ASSERT( cit != l.cend() );
 427                     CPPUNIT_ASSERT( cit == it );
 428
 429                     CPPUNIT_ASSERT( it->nKey == v2.nKey );
 430                     CPPUNIT_ASSERT( it->nVal == v2.nVal );
 431                     CPPUNIT_ASSERT( ++it != l.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                 // cbegin/cend
 441                 {
 442                     typename OrdList::const_iterator it = l.cbegin();
 443                     CPPUNIT_ASSERT( it != l.cend() );
 444                     CPPUNIT_ASSERT( it->nKey == v2.nKey );
 445                     CPPUNIT_ASSERT( it->nVal == v2.nVal );
 446                     CPPUNIT_ASSERT( ++it != l.cend() );
 447                     CPPUNIT_ASSERT( it->nKey == v1.nKey );
 448                     CPPUNIT_ASSERT( it->nVal == v1.nVal );
 449                     CPPUNIT_ASSERT( ++it != l.cend() );
 450                     CPPUNIT_ASSERT( it->nKey == v3.nKey );
 451                     CPPUNIT_ASSERT( it->nVal == v3.nVal );
 452                     CPPUNIT_ASSERT( ++it == l.cend() );
 453                 }
 454
 455                 // const begin/end
 456                 {
 457                     OrdList const & lref = l;
 458                     typename OrdList::const_iterator it = lref.begin();
 459                     CPPUNIT_ASSERT( it != l.end() );
 460                     CPPUNIT_ASSERT( it->nKey == v2.nKey );
 461                     CPPUNIT_ASSERT( it->nVal == v2.nVal );
 462                     CPPUNIT_ASSERT( ++it != lref.end() );
 463                     CPPUNIT_ASSERT( it->nKey == v1.nKey );
 464                     CPPUNIT_ASSERT( it->nVal == v1.nVal );
 465                     CPPUNIT_ASSERT( ++it != l.end() );
 466                     CPPUNIT_ASSERT( it->nKey == v3.nKey );
 467                     CPPUNIT_ASSERT( it->nVal == v3.nVal );
 468                     CPPUNIT_ASSERT( ++it == l.end() );
 469                 }
 470             }
 471
 472             // Apply retired pointer
 473             OrdList::gc::force_dispose();
 474
 475             CPPUNIT_ASSERT( v1.s.nDisposeCount == 4 );
 476             CPPUNIT_ASSERT( v2.s.nDisposeCount == 3 );
 477             CPPUNIT_ASSERT( v3.s.nDisposeCount == 4 );
 478         }
 479
 480         template <class OrdList>
 481         void test_int()
 482         {
 483             test_int_common<OrdList>();
 484
 485             OrdList l;
 486             typename OrdList::guarded_ptr gp;
 487
 488             static int const nLimit = 20;
 489             typename OrdList::value_type arrItem[nLimit];
 490
 491             {
 492                 int a[nLimit];
 493                 for (int i = 0; i < nLimit; ++i)
 494                     a[i]=i;
 495                 shuffle( a, a + nLimit );
 496
 497                 for (int i = 0; i < nLimit; ++i) {
 498                     arrItem[i].nKey = a[i];
 499                     arrItem[i].nVal = a[i] * 2;
 500                 }
 501
 502                 // extract/get
 503                 for ( int i = 0; i < nLimit; ++i )
 504                     CPPUNIT_ASSERT( l.insert( arrItem[i] ) );
 505
 506                 for ( int i=0; i < nLimit; ++i ) {
 507                     gp = l.get( arrItem[i].nKey );
 508                     CPPUNIT_ASSERT_EX( gp, "i=" << i );
 509                     CPPUNIT_ASSERT( !gp.empty());
 510                     CPPUNIT_CHECK( gp->nKey == arrItem[i].nKey );
 511                     CPPUNIT_CHECK( gp->nVal == arrItem[i].nVal );
 512                     gp.release();
 513
 514                     gp = l.extract( arrItem[i].nKey );
 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.get( arrItem[i].nKey );
 522                     CPPUNIT_CHECK( !gp );
 523                     CPPUNIT_CHECK( gp.empty());
 524                     CPPUNIT_CHECK( !l.extract( arrItem[i].nKey ));
 525                     CPPUNIT_CHECK( gp.empty());
 526                 }
 527                 CPPUNIT_ASSERT( l.empty() );
 528                 CPPUNIT_ASSERT( !l.get( nLimit/2 ));
 529                 CPPUNIT_ASSERT( gp.empty());
 530                 CPPUNIT_ASSERT( !l.extract( nLimit/2 ));
 531                 CPPUNIT_ASSERT( gp.empty());
 532
 533                 // Apply retired pointer
 534                 OrdList::gc::force_dispose();
 535
 536                 // extract_with/get_with
 537                 for ( int i = 0; i < nLimit; ++i )
 538                     CPPUNIT_ASSERT( l.insert( arrItem[i] ) );
 539
 540                 for ( int i=0; i < nLimit; ++i ) {
 541                     other_item itm( arrItem[i].nKey );
 542                     gp = l.get_with( itm, other_less() );
 543                     CPPUNIT_ASSERT_EX( gp, "i=" << i );
 544                     CPPUNIT_ASSERT( !gp.empty());
 545                     CPPUNIT_CHECK( gp->nKey == arrItem[i].nKey );
 546                     CPPUNIT_CHECK( gp->nVal == arrItem[i].nVal );
 547                     gp.release();
 548
 549                     gp = l.extract_with( itm, other_less() );
 550                     CPPUNIT_ASSERT_EX( gp, "i=" << i );
 551                     CPPUNIT_ASSERT( !gp.empty());
 552                     CPPUNIT_CHECK( gp->nKey == arrItem[i].nKey );
 553                     CPPUNIT_CHECK( gp->nVal == arrItem[i].nVal );
 554                     gp.release();
 555
 556                     gp = l.get_with( itm, other_less() );
 557                     CPPUNIT_CHECK( !gp );
 558                     CPPUNIT_CHECK( gp.empty());
 559                     CPPUNIT_CHECK( !l.extract_with( itm, other_less() ));
 560                     CPPUNIT_CHECK( gp.empty());
 561                 }
 562                 CPPUNIT_ASSERT( l.empty() );
 563                 CPPUNIT_ASSERT( !l.get_with( other_item(nLimit/2), other_less() ));
 564                 CPPUNIT_ASSERT( gp.empty());
 565                 CPPUNIT_ASSERT( !l.extract_with( other_item(nLimit/2), other_less() ));
 566                 CPPUNIT_ASSERT( gp.empty());
 567
 568                 // Apply retired pointer
 569                 OrdList::gc::force_dispose();
 570
 571                 for ( int i=0; i < nLimit; i++ ) {
 572                     CPPUNIT_ASSERT( arrItem[i].s.nDisposeCount == 2 );
 573                 }
 574             }
 575         }
 576
 577         template <class OrdList>
 578         void test_rcu_int()
 579         {
 580             test_int_common<OrdList>();
 581
 582             OrdList l;
 583             static int const nLimit = 20;
 584             typename OrdList::value_type arrItem[nLimit];
 585
 586             typedef typename OrdList::rcu_lock rcu_lock;
 587             typedef typename OrdList::value_type value_type;
 588             typedef typename OrdList::gc rcu_type;
 589
 590             {
 591                 int a[nLimit];
 592                 for (int i = 0; i < nLimit; ++i)
 593                     a[i]=i;
 594                 shuffle( a, a + nLimit );
 595
 596                 for (int i = 0; i < nLimit; ++i) {
 597                     arrItem[i].nKey = a[i];
 598                     arrItem[i].nVal = a[i] * 2;
 599                 }
 600
 601                 // extract/get
 602                 for ( int i = 0; i < nLimit; ++i )
 603                     CPPUNIT_ASSERT( l.insert( arrItem[i] ) );
 604
 605                 typename OrdList::exempt_ptr ep;
 606                 typename OrdList::raw_ptr rp;
 607
 608                 for ( int i = 0; i < nLimit; ++i ) {
 609                     {
 610                         rcu_lock lock;
 611                         rp = l.get( a[i] );
 612                         CPPUNIT_ASSERT( rp );
 613                         CPPUNIT_CHECK( rp->nKey == a[i] );
 614                         CPPUNIT_CHECK( rp->nVal == a[i] * 2 );
 615                     }
 616                     rp.release();
 617
 618                     ep = l.extract( a[i] );
 619                     CPPUNIT_ASSERT( ep );
 620                     CPPUNIT_ASSERT( !ep.empty() );
 621                     CPPUNIT_CHECK( ep->nKey == a[i] );
 622                     CPPUNIT_CHECK( (*ep).nVal == a[i] * 2 );
 623                     ep.release();
 624
 625                     {
 626                         rcu_lock lock;
 627                         CPPUNIT_CHECK( !l.get( a[i] ));
 628                     }
 629                     CPPUNIT_CHECK( !l.extract( a[i] ));
 630                     CPPUNIT_CHECK( ep.empty() );
 631                 }
 632                 CPPUNIT_ASSERT( l.empty() );
 633
 634                 {
 635                     rcu_lock lock;
 636                     CPPUNIT_CHECK( !l.get( a[0] ));
 637                 }
 638                 ep = l.extract( a[0] );
 639                 CPPUNIT_CHECK( !ep );
 640                 CPPUNIT_CHECK( ep.empty() );
 641
 642                 // Apply retired pointer
 643                 OrdList::gc::force_dispose();
 644
 645                 // extract_with/get_with
 646                 for ( int i = 0; i < nLimit; ++i ) {
 647                     CPPUNIT_ASSERT( l.insert( arrItem[i] ) );
 648                 }
 649
 650                 for ( int i = 0; i < nLimit; ++i ) {
 651                     other_item itm( a[i] );
 652                     {
 653                         rcu_lock lock;
 654                         rp = l.get_with( itm, other_less() );
 655                         CPPUNIT_ASSERT( rp );
 656                         CPPUNIT_CHECK( rp->nKey == a[i] );
 657                         CPPUNIT_CHECK( rp->nVal == a[i] * 2 );
 658                     }
 659                     rp.release();
 660
 661                     ep = l.extract_with( itm, other_less() );
 662                     CPPUNIT_ASSERT( ep );
 663                     CPPUNIT_ASSERT( !ep.empty() );
 664                     CPPUNIT_CHECK( ep->nKey == a[i] );
 665                     CPPUNIT_CHECK( ep->nVal == a[i] * 2 );
 666                     ep.release();
 667
 668                     {
 669                         rcu_lock lock;
 670                         CPPUNIT_CHECK( !l.get_with( itm, other_less() ));
 671                     }
 672                     ep = l.extract_with( itm, other_less() );
 673                     CPPUNIT_CHECK( !ep );
 674                     CPPUNIT_CHECK( ep.empty() );
 675                 }
 676                 CPPUNIT_ASSERT( l.empty() );
 677
 678                 {
 679                     rcu_lock lock;
 680                     CPPUNIT_CHECK( !l.get_with( other_item( 0 ), other_less() ));
 681                 }
 682                 CPPUNIT_CHECK( !l.extract_with( other_item(0), other_less() ));
 683                 CPPUNIT_CHECK( ep.empty() );
 684
 685                 // Apply retired pointer
 686                 OrdList::gc::force_dispose();
 687             }
 688         }
 689
 690         template <class OrdList>
 691         void test_nogc_int()
 692         {
 693             typedef typename OrdList::value_type    value_type;
 694             {
 695                 value_type v1( 10, 50 );
 696                 value_type v2( 5, 25  );
 697                 value_type v3( 20, 100 );
 698                 {
 699                     OrdList l;
 700                     CPPUNIT_ASSERT( l.empty() );
 701
 702                     CPPUNIT_ASSERT( l.insert( v1 ))     ;   // true
 703                     CPPUNIT_ASSERT( l.contains( v1.key() ) == &v1 );
 704
 705                     CPPUNIT_ASSERT( v1.s.nFindCall == 0 );
 706                     CPPUNIT_ASSERT( l.find( v1.key(), find_functor() ));
 707                     CPPUNIT_ASSERT( v1.s.nFindCall == 1 );
 708
 709                     CPPUNIT_ASSERT( l.contains( v2.key(), less<value_type>() ) == nullptr );
 710                     CPPUNIT_ASSERT( !l.find_with( v3.key(), less<value_type>(), find_functor() ));
 711                     CPPUNIT_ASSERT( !l.empty() );
 712
 713                     CPPUNIT_ASSERT( !l.insert( v1 ))    ;   // assertion "is_empty" is not raised since pNext is nullptr
 714
 715                     {
 716                         value_type v( v1 );
 717                         CPPUNIT_ASSERT( !l.insert( v )) ;   // false
 718                     }
 719
 720                     std::pair<bool, bool> ret = l.update( v2, update_functor() );
 721                     CPPUNIT_ASSERT( ret.first );
 722                     CPPUNIT_ASSERT( ret.second );
 723                     CPPUNIT_ASSERT( v2.s.nUpdateNewCall == 1 );
 724                     CPPUNIT_ASSERT( v2.s.nUpdateExistsCall == 0 );
 725
 726                     //CPPUNIT_ASSERT( !l.insert( v2 ))    ;   // assertion "is_empty"
 727
 728                     CPPUNIT_ASSERT( l.contains( v1.key() ) == &v1 ) ;   // true
 729
 730                     CPPUNIT_ASSERT( v1.s.nFindCall == 1 );
 731                     CPPUNIT_ASSERT( l.find( v1.key(), find_functor() ));
 732                     CPPUNIT_ASSERT( v1.s.nFindCall == 2 );
 733
 734                     CPPUNIT_ASSERT( l.contains( v2.key() ) == &v2 );
 735
 736                     CPPUNIT_ASSERT( v2.s.nFindCall == 0 );
 737                     CPPUNIT_ASSERT( l.find( v2.key(), find_functor() ));
 738                     CPPUNIT_ASSERT( v2.s.nFindCall == 1 );
 739
 740                     CPPUNIT_ASSERT( !l.contains( v3.key() ));
 741
 742                     {
 743                         value_type v( v2 );
 744                         ret = l.update( v, update_functor() );
 745
 746                         CPPUNIT_ASSERT( ret.first );
 747                         CPPUNIT_ASSERT( !ret.second );
 748                         CPPUNIT_ASSERT( v2.s.nUpdateExistsCall == 1 );
 749                         CPPUNIT_ASSERT( v.s.nUpdateExistsCall == 0 && v.s.nUpdateNewCall == 0 );
 750                     }
 751
 752                     CPPUNIT_ASSERT( !l.empty() );
 753
 754                     CPPUNIT_ASSERT( l.insert( v3 ))     ;   // true
 755                     CPPUNIT_ASSERT( l.contains( v3.key() ) == &v3 );
 756
 757                     CPPUNIT_ASSERT( v3.s.nFindCall == 0 );
 758                     CPPUNIT_ASSERT( l.find( v3.key(), find_functor() ));
 759                     CPPUNIT_ASSERT( v3.s.nFindCall == 1 );
 760
 761                     {
 762                         typename OrdList::iterator it = l.begin();
 763                         typename OrdList::const_iterator cit = l.cbegin();
 764                         CPPUNIT_ASSERT( it != l.end() );
 765                         CPPUNIT_ASSERT( it != l.cend() );
 766                         CPPUNIT_ASSERT( cit != l.end() );
 767                         CPPUNIT_ASSERT( cit != l.cend() );
 768                         CPPUNIT_ASSERT( cit == it );
 769
 770                         CPPUNIT_ASSERT( it->nKey == v2.nKey );
 771                         CPPUNIT_ASSERT( it->nVal == v2.nVal );
 772                         CPPUNIT_ASSERT( ++it != l.end() );
 773                         CPPUNIT_ASSERT( it->nKey == v1.nKey );
 774                         CPPUNIT_ASSERT( it->nVal == v1.nVal );
 775                         CPPUNIT_ASSERT( it++ != l.end() );
 776                         CPPUNIT_ASSERT( it->nKey == v3.nKey );
 777                         CPPUNIT_ASSERT( it->nVal == v3.nVal );
 778                         CPPUNIT_ASSERT( it++ != l.end() );
 779                         CPPUNIT_ASSERT( it == l.end() );
 780                     }
 781
 782                     {
 783                         OrdList const & lref = l;
 784                         typename OrdList::const_iterator it = lref.begin();
 785                         CPPUNIT_ASSERT( it != l.end() );
 786                         CPPUNIT_ASSERT( it->nKey == v2.nKey );
 787                         CPPUNIT_ASSERT( it->nVal == v2.nVal );
 788                         CPPUNIT_ASSERT( ++it != lref.end() );
 789                         CPPUNIT_ASSERT( it->nKey == v1.nKey );
 790                         CPPUNIT_ASSERT( it->nVal == v1.nVal );
 791                         CPPUNIT_ASSERT( it++ != l.end() );
 792                         CPPUNIT_ASSERT( it->nKey == v3.nKey );
 793                         CPPUNIT_ASSERT( it->nVal == v3.nVal );
 794                         CPPUNIT_ASSERT( it++ != lref.end() );
 795                         CPPUNIT_ASSERT( it == l.end() );
 796                     }
 797                 }
 798
 799                 // Disposer called on list destruction
 800                 CPPUNIT_ASSERT( v1.s.nDisposeCount == 1 );
 801                 CPPUNIT_ASSERT( v2.s.nDisposeCount == 1 );
 802                 CPPUNIT_ASSERT( v3.s.nDisposeCount == 1 );
 803             }
 804         }
 805
 806         void HP_base_cmp();
 807         void HP_base_less();
 808         void HP_base_cmpmix();
 809         void HP_base_ic();
 810         void HP_member_cmp();
 811         void HP_member_less();
 812         void HP_member_cmpmix();
 813         void HP_member_ic();
 814
 815         void DHP_base_cmp();
 816         void DHP_base_less();
 817         void DHP_base_cmpmix();
 818         void DHP_base_ic();
 819         void DHP_member_cmp();
 820         void DHP_member_less();
 821         void DHP_member_cmpmix();
 822         void DHP_member_ic();
 823
 824         void RCU_GPI_base_cmp();
 825         void RCU_GPI_base_less();
 826         void RCU_GPI_base_cmpmix();
 827         void RCU_GPI_base_ic();
 828         void RCU_GPI_member_cmp();
 829         void RCU_GPI_member_less();
 830         void RCU_GPI_member_cmpmix();
 831         void RCU_GPI_member_ic();
 832
 833         void RCU_GPB_base_cmp();
 834         void RCU_GPB_base_less();
 835         void RCU_GPB_base_cmpmix();
 836         void RCU_GPB_base_ic();
 837         void RCU_GPB_member_cmp();
 838         void RCU_GPB_member_less();
 839         void RCU_GPB_member_cmpmix();
 840         void RCU_GPB_member_ic();
 841
 842         void RCU_GPT_base_cmp();
 843         void RCU_GPT_base_less();
 844         void RCU_GPT_base_cmpmix();
 845         void RCU_GPT_base_ic();
 846         void RCU_GPT_member_cmp();
 847         void RCU_GPT_member_less();
 848         void RCU_GPT_member_cmpmix();
 849         void RCU_GPT_member_ic();
 850
 851         void RCU_SHB_base_cmp();
 852         void RCU_SHB_base_less();
 853         void RCU_SHB_base_cmpmix();
 854         void RCU_SHB_base_ic();
 855         void RCU_SHB_member_cmp();
 856         void RCU_SHB_member_less();
 857         void RCU_SHB_member_cmpmix();
 858         void RCU_SHB_member_ic();
 859
 860         void RCU_SHT_base_cmp();
 861         void RCU_SHT_base_less();
 862         void RCU_SHT_base_cmpmix();
 863         void RCU_SHT_base_ic();
 864         void RCU_SHT_member_cmp();
 865         void RCU_SHT_member_less();
 866         void RCU_SHT_member_cmpmix();
 867         void RCU_SHT_member_ic();
 868
 869         void nogc_base_cmp();
 870         void nogc_base_less();
 871         void nogc_base_cmpmix();
 872         void nogc_base_ic();
 873         void nogc_member_cmp();
 874         void nogc_member_less();
 875         void nogc_member_cmpmix();
 876         void nogc_member_ic();
 877
 878
 879         CPPUNIT_TEST_SUITE(IntrusiveMichaelListHeaderTest)
 880             CPPUNIT_TEST(HP_base_cmp)
 881             CPPUNIT_TEST(HP_base_less)
 882             CPPUNIT_TEST(HP_base_cmpmix)
 883             CPPUNIT_TEST(HP_base_ic)
 884             CPPUNIT_TEST(HP_member_cmp)
 885             CPPUNIT_TEST(HP_member_less)
 886             CPPUNIT_TEST(HP_member_cmpmix)
 887             CPPUNIT_TEST(HP_member_ic)
 888
 889             CPPUNIT_TEST(DHP_base_cmp)
 890             CPPUNIT_TEST(DHP_base_less)
 891             CPPUNIT_TEST(DHP_base_cmpmix)
 892             CPPUNIT_TEST(DHP_base_ic)
 893             CPPUNIT_TEST(DHP_member_cmp)
 894             CPPUNIT_TEST(DHP_member_less)
 895             CPPUNIT_TEST(DHP_member_cmpmix)
 896             CPPUNIT_TEST(DHP_member_ic)
 897
 898             CPPUNIT_TEST(RCU_GPI_base_cmp)
 899             CPPUNIT_TEST(RCU_GPI_base_less)
 900             CPPUNIT_TEST(RCU_GPI_base_cmpmix)
 901             CPPUNIT_TEST(RCU_GPI_base_ic)
 902             CPPUNIT_TEST(RCU_GPI_member_cmp)
 903             CPPUNIT_TEST(RCU_GPI_member_less)
 904             CPPUNIT_TEST(RCU_GPI_member_cmpmix)
 905             CPPUNIT_TEST(RCU_GPI_member_ic)
 906
 907             CPPUNIT_TEST(RCU_GPB_base_cmp)
 908             CPPUNIT_TEST(RCU_GPB_base_less)
 909             CPPUNIT_TEST(RCU_GPB_base_cmpmix)
 910             CPPUNIT_TEST(RCU_GPB_base_ic)
 911             CPPUNIT_TEST(RCU_GPB_member_cmp)
 912             CPPUNIT_TEST(RCU_GPB_member_less)
 913             CPPUNIT_TEST(RCU_GPB_member_cmpmix)
 914             CPPUNIT_TEST(RCU_GPB_member_ic)
 915
 916             CPPUNIT_TEST(RCU_GPT_base_cmp)
 917             CPPUNIT_TEST(RCU_GPT_base_less)
 918             CPPUNIT_TEST(RCU_GPT_base_cmpmix)
 919             CPPUNIT_TEST(RCU_GPT_base_ic)
 920             CPPUNIT_TEST(RCU_GPT_member_cmp)
 921             CPPUNIT_TEST(RCU_GPT_member_less)
 922             CPPUNIT_TEST(RCU_GPT_member_cmpmix)
 923             CPPUNIT_TEST(RCU_GPT_member_ic)
 924
 925             CPPUNIT_TEST(nogc_base_cmp)
 926             CPPUNIT_TEST(nogc_base_less)
 927             CPPUNIT_TEST(nogc_base_cmpmix)
 928             CPPUNIT_TEST(nogc_base_ic)
 929             CPPUNIT_TEST(nogc_member_cmp)
 930             CPPUNIT_TEST(nogc_member_less)
 931             CPPUNIT_TEST(nogc_member_cmpmix)
 932             CPPUNIT_TEST(nogc_member_ic)
 933
 934         CPPUNIT_TEST_SUITE_END()
 935     };
 936 }   // namespace ordlist
 937
 938 #endif // CDSTEST_HDR_INTRUSIVE_MICHAEL_H