63ff419a2266e2e94e16f2a2a7d786d301c0c4b2
[libcds.git] / 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( gp );
478                     CPPUNIT_ASSERT( !gp.empty());
479                     CPPUNIT_ASSERT( gp->nKey == arrItem[i].nKey );
480                     CPPUNIT_ASSERT( gp->nVal == arrItem[i].nVal );
481
482                     gp = l.extract( arrItem[i].nKey );
483                     CPPUNIT_ASSERT( gp );
484                     CPPUNIT_ASSERT( !gp.empty());
485                     CPPUNIT_ASSERT( gp->nKey == arrItem[i].nKey );
486                     CPPUNIT_ASSERT( gp->nVal == arrItem[i].nVal );
487
488                     gp = l.get( arrItem[i].nKey );
489                     CPPUNIT_ASSERT( !gp );
490                     CPPUNIT_ASSERT( gp.empty());
491                     CPPUNIT_ASSERT( !l.extract( arrItem[i].nKey ));
492                     CPPUNIT_ASSERT( gp.empty());
493                 }
494                 CPPUNIT_ASSERT( l.empty() );
495                 CPPUNIT_ASSERT( !l.get( nLimit/2 ));
496                 CPPUNIT_ASSERT( gp.empty());
497                 CPPUNIT_ASSERT( !l.extract( nLimit/2 ));
498                 CPPUNIT_ASSERT( gp.empty());
499
500                 // Apply retired pointer
501                 OrdList::gc::force_dispose();
502
503                 // extract_with/get_with
504                 for ( int i = 0; i < nLimit; ++i )
505                     CPPUNIT_ASSERT( l.insert( arrItem[i] ) );
506
507                 for ( int i=0; i < nLimit; ++i ) {
508                     other_item itm( arrItem[i].nKey );
509                     gp = l.get_with( itm, other_less() );
510                     CPPUNIT_ASSERT( gp );
511                     CPPUNIT_ASSERT( !gp.empty());
512                     CPPUNIT_ASSERT( gp->nKey == arrItem[i].nKey );
513                     CPPUNIT_ASSERT( gp->nVal == arrItem[i].nVal );
514
515                     gp = l.extract_with( itm, other_less() );
516                     CPPUNIT_ASSERT( gp );
517                     CPPUNIT_ASSERT( !gp.empty());
518                     CPPUNIT_ASSERT( gp->nKey == arrItem[i].nKey );
519                     CPPUNIT_ASSERT( gp->nVal == arrItem[i].nVal );
520
521                     gp = l.get_with( itm, other_less() );
522                     CPPUNIT_ASSERT( !gp );
523                     CPPUNIT_ASSERT( gp.empty());
524                     CPPUNIT_ASSERT( !l.extract_with( itm, other_less() ));
525                     CPPUNIT_ASSERT( gp.empty());
526                 }
527                 CPPUNIT_ASSERT( l.empty() );
528                 CPPUNIT_ASSERT( !l.get_with( other_item(nLimit/2), other_less() ));
529                 CPPUNIT_ASSERT( gp.empty());
530                 CPPUNIT_ASSERT( !l.extract_with( other_item(nLimit/2), other_less() ));
531                 CPPUNIT_ASSERT( gp.empty());
532
533                 // Apply retired pointer
534                 OrdList::gc::force_dispose();
535
536                 for ( int i=0; i < nLimit; i++ ) {
537                     CPPUNIT_ASSERT( arrItem[i].s.nDisposeCount == 2 );
538                 }
539             }
540         }
541
542         template <class OrdList>
543         void test_rcu_int()
544         {
545             test_int_common<OrdList>();
546
547             OrdList l;
548             static int const nLimit = 20;
549             typename OrdList::value_type arrItem[nLimit];
550
551             typedef typename OrdList::rcu_lock rcu_lock;
552             typedef typename OrdList::value_type value_type;
553             typedef typename OrdList::gc rcu_type;
554
555             {
556                 int a[nLimit];
557                 for (int i = 0; i < nLimit; ++i)
558                     a[i]=i;
559                 std::random_shuffle( a, a + nLimit );
560
561                 for (int i = 0; i < nLimit; ++i) {
562                     arrItem[i].nKey = a[i];
563                     arrItem[i].nVal = a[i] * 2;
564                 }
565
566                 // extract/get
567                 for ( int i = 0; i < nLimit; ++i )
568                     CPPUNIT_ASSERT( l.insert( arrItem[i] ) );
569
570                 typename OrdList::exempt_ptr ep;
571
572                 for ( int i = 0; i < nLimit; ++i ) {
573                     {
574                         rcu_lock lock;
575                         value_type * pGet = l.get( a[i] );
576                         CPPUNIT_ASSERT( pGet != nullptr );
577                         CPPUNIT_CHECK( pGet->nKey == a[i] );
578                         CPPUNIT_CHECK( pGet->nVal == a[i] * 2 );
579
580                         ep = l.extract( a[i] );
581                         CPPUNIT_ASSERT( ep );
582                         CPPUNIT_ASSERT( !ep.empty() );
583                         CPPUNIT_CHECK( ep->nKey == a[i] );
584                         CPPUNIT_CHECK( (*ep).nVal == a[i] * 2 );
585                     }
586                     ep.release();
587                     {
588                         rcu_lock lock;
589                         CPPUNIT_CHECK( l.get( a[i] ) == nullptr );
590                         CPPUNIT_CHECK( !l.extract( a[i] ));
591                         CPPUNIT_CHECK( ep.empty() );
592                     }
593                 }
594                 CPPUNIT_ASSERT( l.empty() );
595
596                 {
597                     rcu_lock lock;
598                     CPPUNIT_CHECK( l.get( a[0] ) == nullptr );
599                     ep = l.extract( a[0] );
600                     CPPUNIT_CHECK( !ep );
601                     CPPUNIT_CHECK( ep.empty() );
602                 }
603                 // Apply retired pointer
604                 OrdList::gc::force_dispose();
605
606                 // extract_with/get_with
607                 for ( int i = 0; i < nLimit; ++i ) {
608                     CPPUNIT_ASSERT( l.insert( arrItem[i] ) );
609                 }
610
611                 for ( int i = 0; i < nLimit; ++i ) {
612                     other_item itm( a[i] );
613                     {
614                         rcu_lock lock;
615                         value_type * pGet = l.get_with( itm, other_less() );
616                         CPPUNIT_ASSERT( pGet != nullptr );
617                         CPPUNIT_CHECK( pGet->nKey == a[i] );
618                         CPPUNIT_CHECK( pGet->nVal == a[i] * 2 );
619
620                         ep = l.extract_with( itm, other_less() );
621                         CPPUNIT_ASSERT( ep );
622                         CPPUNIT_ASSERT( !ep.empty() );
623                         CPPUNIT_CHECK( ep->nKey == a[i] );
624                         CPPUNIT_CHECK( ep->nVal == a[i] * 2 );
625                     }
626                     ep.release();
627                     {
628                         rcu_lock lock;
629                         CPPUNIT_CHECK( l.get_with( itm, other_less() ) == nullptr );
630                         ep = l.extract_with( itm, other_less() );
631                         CPPUNIT_CHECK( !ep );
632                         CPPUNIT_CHECK( ep.empty() );
633                     }
634                 }
635                 CPPUNIT_ASSERT( l.empty() );
636
637                 {
638                     rcu_lock lock;
639                     CPPUNIT_CHECK( l.get_with( other_item( 0 ), other_less() ) == nullptr );
640                     CPPUNIT_CHECK( !l.extract_with( other_item(0), other_less() ));
641                     CPPUNIT_CHECK( ep.empty() );
642                 }
643                 // Apply retired pointer
644                 OrdList::gc::force_dispose();
645             }
646         }
647
648         template <class OrdList>
649         void test_nogc_int()
650         {
651             typedef typename OrdList::value_type    value_type;
652             {
653                 value_type v1( 10, 50 );
654                 value_type v2( 5, 25  );
655                 value_type v3( 20, 100 );
656                 {
657                     OrdList l;
658                     CPPUNIT_ASSERT( l.empty() );
659
660                     CPPUNIT_ASSERT( l.insert( v1 ))     ;   // true
661                     CPPUNIT_ASSERT( l.find( v1.key() ) == &v1 );
662
663                     CPPUNIT_ASSERT( v1.s.nFindCall == 0 );
664                     CPPUNIT_ASSERT( l.find( v1.key(), find_functor() ));
665                     CPPUNIT_ASSERT( v1.s.nFindCall == 1 );
666
667                     CPPUNIT_ASSERT( l.find_with( v2.key(), less<value_type>() ) == nullptr );
668                     CPPUNIT_ASSERT( !l.find_with( v3.key(), less<value_type>(), find_functor() ));
669                     CPPUNIT_ASSERT( !l.empty() );
670
671                     CPPUNIT_ASSERT( !l.insert( v1 ))    ;   // assertion "is_empty" is not raised since pNext is nullptr
672
673                     {
674                         value_type v( v1 );
675                         CPPUNIT_ASSERT( !l.insert( v )) ;   // false
676                     }
677
678                     std::pair<bool, bool> ret = l.ensure( v2, ensure_functor() );
679                     CPPUNIT_ASSERT( ret.first );
680                     CPPUNIT_ASSERT( ret.second );
681                     CPPUNIT_ASSERT( v2.s.nEnsureNewCall == 1 );
682                     CPPUNIT_ASSERT( v2.s.nEnsureExistsCall == 0 );
683
684                     //CPPUNIT_ASSERT( !l.insert( v2 ))    ;   // assertion "is_empty"
685
686                     CPPUNIT_ASSERT( l.find( v1.key() ) == &v1 ) ;   // true
687
688                     CPPUNIT_ASSERT( v1.s.nFindCall == 1 );
689                     CPPUNIT_ASSERT( l.find( v1.key(), find_functor() ));
690                     CPPUNIT_ASSERT( v1.s.nFindCall == 2 );
691
692                     CPPUNIT_ASSERT( l.find( v2.key() ) == &v2 );
693
694                     CPPUNIT_ASSERT( v2.s.nFindCall == 0 );
695                     CPPUNIT_ASSERT( l.find( v2.key(), find_functor() ));
696                     CPPUNIT_ASSERT( v2.s.nFindCall == 1 );
697
698                     CPPUNIT_ASSERT( !l.find( v3.key() ));
699
700                     {
701                         value_type v( v2 );
702                         ret = l.ensure( v, ensure_functor() );
703
704                         CPPUNIT_ASSERT( ret.first );
705                         CPPUNIT_ASSERT( !ret.second );
706                         CPPUNIT_ASSERT( v2.s.nEnsureExistsCall == 1 );
707                         CPPUNIT_ASSERT( v.s.nEnsureExistsCall == 0 && v.s.nEnsureNewCall == 0 );
708                     }
709
710                     CPPUNIT_ASSERT( !l.empty() );
711
712                     CPPUNIT_ASSERT( l.insert( v3 ))     ;   // true
713                     CPPUNIT_ASSERT( l.find( v3.key() ) == &v3 );
714
715                     CPPUNIT_ASSERT( v3.s.nFindCall == 0 );
716                     CPPUNIT_ASSERT( l.find( v3.key(), find_functor() ));
717                     CPPUNIT_ASSERT( v3.s.nFindCall == 1 );
718
719                     {
720                         typename OrdList::iterator it = l.begin();
721                         typename OrdList::const_iterator cit = l.cbegin();
722                         CPPUNIT_ASSERT( it != l.end() );
723                         CPPUNIT_ASSERT( it != l.cend() );
724                         CPPUNIT_ASSERT( cit != l.end() );
725                         CPPUNIT_ASSERT( cit != l.cend() );
726                         CPPUNIT_ASSERT( cit == it );
727
728                         CPPUNIT_ASSERT( it->nKey == v2.nKey );
729                         CPPUNIT_ASSERT( it->nVal == v2.nVal );
730                         CPPUNIT_ASSERT( ++it != l.end() );
731                         CPPUNIT_ASSERT( it->nKey == v1.nKey );
732                         CPPUNIT_ASSERT( it->nVal == v1.nVal );
733                         CPPUNIT_ASSERT( it++ != l.end() );
734                         CPPUNIT_ASSERT( it->nKey == v3.nKey );
735                         CPPUNIT_ASSERT( it->nVal == v3.nVal );
736                         CPPUNIT_ASSERT( it++ != l.end() );
737                         CPPUNIT_ASSERT( it == l.end() );
738                     }
739
740                     {
741                         OrdList const & lref = l;
742                         typename OrdList::const_iterator it = lref.begin();
743                         CPPUNIT_ASSERT( it != l.end() );
744                         CPPUNIT_ASSERT( it->nKey == v2.nKey );
745                         CPPUNIT_ASSERT( it->nVal == v2.nVal );
746                         CPPUNIT_ASSERT( ++it != lref.end() );
747                         CPPUNIT_ASSERT( it->nKey == v1.nKey );
748                         CPPUNIT_ASSERT( it->nVal == v1.nVal );
749                         CPPUNIT_ASSERT( it++ != l.end() );
750                         CPPUNIT_ASSERT( it->nKey == v3.nKey );
751                         CPPUNIT_ASSERT( it->nVal == v3.nVal );
752                         CPPUNIT_ASSERT( it++ != lref.end() );
753                         CPPUNIT_ASSERT( it == l.end() );
754                     }
755                 }
756
757                 // Disposer called on list destruction
758                 CPPUNIT_ASSERT( v1.s.nDisposeCount == 1 );
759                 CPPUNIT_ASSERT( v2.s.nDisposeCount == 1 );
760                 CPPUNIT_ASSERT( v3.s.nDisposeCount == 1 );
761             }
762         }
763
764         void HP_base_cmp();
765         void HP_base_less();
766         void HP_base_cmpmix();
767         void HP_base_ic();
768         void HP_member_cmp();
769         void HP_member_less();
770         void HP_member_cmpmix();
771         void HP_member_ic();
772
773         void DHP_base_cmp();
774         void DHP_base_less();
775         void DHP_base_cmpmix();
776         void DHP_base_ic();
777         void DHP_member_cmp();
778         void DHP_member_less();
779         void DHP_member_cmpmix();
780         void DHP_member_ic();
781
782         void RCU_GPI_base_cmp();
783         void RCU_GPI_base_less();
784         void RCU_GPI_base_cmpmix();
785         void RCU_GPI_base_ic();
786         void RCU_GPI_member_cmp();
787         void RCU_GPI_member_less();
788         void RCU_GPI_member_cmpmix();
789         void RCU_GPI_member_ic();
790
791         void RCU_GPB_base_cmp();
792         void RCU_GPB_base_less();
793         void RCU_GPB_base_cmpmix();
794         void RCU_GPB_base_ic();
795         void RCU_GPB_member_cmp();
796         void RCU_GPB_member_less();
797         void RCU_GPB_member_cmpmix();
798         void RCU_GPB_member_ic();
799
800         void RCU_GPT_base_cmp();
801         void RCU_GPT_base_less();
802         void RCU_GPT_base_cmpmix();
803         void RCU_GPT_base_ic();
804         void RCU_GPT_member_cmp();
805         void RCU_GPT_member_less();
806         void RCU_GPT_member_cmpmix();
807         void RCU_GPT_member_ic();
808
809         void RCU_SHB_base_cmp();
810         void RCU_SHB_base_less();
811         void RCU_SHB_base_cmpmix();
812         void RCU_SHB_base_ic();
813         void RCU_SHB_member_cmp();
814         void RCU_SHB_member_less();
815         void RCU_SHB_member_cmpmix();
816         void RCU_SHB_member_ic();
817
818         void RCU_SHT_base_cmp();
819         void RCU_SHT_base_less();
820         void RCU_SHT_base_cmpmix();
821         void RCU_SHT_base_ic();
822         void RCU_SHT_member_cmp();
823         void RCU_SHT_member_less();
824         void RCU_SHT_member_cmpmix();
825         void RCU_SHT_member_ic();
826
827         void nogc_base_cmp();
828         void nogc_base_less();
829         void nogc_base_cmpmix();
830         void nogc_base_ic();
831         void nogc_member_cmp();
832         void nogc_member_less();
833         void nogc_member_cmpmix();
834         void nogc_member_ic();
835
836
837         CPPUNIT_TEST_SUITE(IntrusiveMichaelListHeaderTest)
838             CPPUNIT_TEST(HP_base_cmp)
839             CPPUNIT_TEST(HP_base_less)
840             CPPUNIT_TEST(HP_base_cmpmix)
841             CPPUNIT_TEST(HP_base_ic)
842             CPPUNIT_TEST(HP_member_cmp)
843             CPPUNIT_TEST(HP_member_less)
844             CPPUNIT_TEST(HP_member_cmpmix)
845             CPPUNIT_TEST(HP_member_ic)
846
847             CPPUNIT_TEST(DHP_base_cmp)
848             CPPUNIT_TEST(DHP_base_less)
849             CPPUNIT_TEST(DHP_base_cmpmix)
850             CPPUNIT_TEST(DHP_base_ic)
851             CPPUNIT_TEST(DHP_member_cmp)
852             CPPUNIT_TEST(DHP_member_less)
853             CPPUNIT_TEST(DHP_member_cmpmix)
854             CPPUNIT_TEST(DHP_member_ic)
855
856             CPPUNIT_TEST(RCU_GPI_base_cmp)
857             CPPUNIT_TEST(RCU_GPI_base_less)
858             CPPUNIT_TEST(RCU_GPI_base_cmpmix)
859             CPPUNIT_TEST(RCU_GPI_base_ic)
860             CPPUNIT_TEST(RCU_GPI_member_cmp)
861             CPPUNIT_TEST(RCU_GPI_member_less)
862             CPPUNIT_TEST(RCU_GPI_member_cmpmix)
863             CPPUNIT_TEST(RCU_GPI_member_ic)
864
865             CPPUNIT_TEST(RCU_GPB_base_cmp)
866             CPPUNIT_TEST(RCU_GPB_base_less)
867             CPPUNIT_TEST(RCU_GPB_base_cmpmix)
868             CPPUNIT_TEST(RCU_GPB_base_ic)
869             CPPUNIT_TEST(RCU_GPB_member_cmp)
870             CPPUNIT_TEST(RCU_GPB_member_less)
871             CPPUNIT_TEST(RCU_GPB_member_cmpmix)
872             CPPUNIT_TEST(RCU_GPB_member_ic)
873
874             CPPUNIT_TEST(RCU_GPT_base_cmp)
875             CPPUNIT_TEST(RCU_GPT_base_less)
876             CPPUNIT_TEST(RCU_GPT_base_cmpmix)
877             CPPUNIT_TEST(RCU_GPT_base_ic)
878             CPPUNIT_TEST(RCU_GPT_member_cmp)
879             CPPUNIT_TEST(RCU_GPT_member_less)
880             CPPUNIT_TEST(RCU_GPT_member_cmpmix)
881             CPPUNIT_TEST(RCU_GPT_member_ic)
882
883             CPPUNIT_TEST(nogc_base_cmp)
884             CPPUNIT_TEST(nogc_base_less)
885             CPPUNIT_TEST(nogc_base_cmpmix)
886             CPPUNIT_TEST(nogc_base_ic)
887             CPPUNIT_TEST(nogc_member_cmp)
888             CPPUNIT_TEST(nogc_member_less)
889             CPPUNIT_TEST(nogc_member_cmpmix)
890             CPPUNIT_TEST(nogc_member_ic)
891
892         CPPUNIT_TEST_SUITE_END()
893     };
894 }   // namespace ordlist