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