78a17c50a78176215d8c1b70d4929dae3ec3255d
[libcds.git] / tests / test-hdr / tree / hdr_intrusive_bintree.h
1 //$$CDS-header$$
2
3 #ifndef CDSHDRTEST_INTRUSIVE_BINTREE_H
4 #define CDSHDRTEST_INTRUSIVE_BINTREE_H
5
6 #include "cppunit/cppunit_proxy.h"
7 #include "size_check.h"
8 #include <algorithm>
9
10 namespace tree {
11
12     class IntrusiveBinTreeHdrTest: public CppUnitMini::TestCase
13     {
14     public:
15         typedef int     key_type;
16
17         struct stat_data {
18             size_t  nDisposeCount;
19             size_t  nWaitingDispCount;
20             size_t  nInsertFuncCall;
21             size_t  nEnsureExistFuncCall;
22             size_t  nEnsureNewFuncCall;
23             size_t  nEraseFuncCall;
24             size_t  nFindFuncCall;
25             size_t  nFindConstFuncCall;
26
27             stat_data()
28                 : nDisposeCount(0)
29                 , nWaitingDispCount(0)
30                 , nInsertFuncCall(0)
31                 , nEnsureExistFuncCall(0)
32                 , nEnsureNewFuncCall(0)
33                 , nEraseFuncCall(0)
34                 , nFindFuncCall(0)
35                 , nFindConstFuncCall(0)
36             {}
37         };
38
39         template <typename Hook>
40         struct base_hook_value: public Hook
41         {
42             int     nKey;
43             int     nValue;
44             mutable stat_data   stat;
45
46             base_hook_value()
47             {}
48
49             base_hook_value( int key )
50                 : nKey(key)
51                 , nValue(key * 2)
52             {}
53
54             base_hook_value( int key, int val )
55                 : nKey(key)
56                 , nValue(val)
57             {}
58
59 #   ifdef _DEBUG
60             base_hook_value( base_hook_value&& s )
61                 : Hook()
62                 , nKey(s.nKey)
63                 , nValue(s.nValue)
64             {}
65             base_hook_value& operator=( base_hook_value const& s )
66             {
67                 nKey = s.nKey;
68                 nValue = s.nValue;
69                 return *this;
70             }
71 #   endif
72         };
73
74         template <typename Hook>
75         struct member_hook_value
76         {
77             int     nKey;
78             int     nValue;
79             Hook    hook;
80             mutable stat_data   stat;
81
82             member_hook_value()
83             {}
84
85             member_hook_value( int key )
86                 : nKey(key)
87                 , nValue(key * 2)
88             {}
89
90             member_hook_value( int key, int val )
91                 : nKey(key)
92                 , nValue(val)
93             {}
94 #   ifdef _DEBUG
95             member_hook_value( member_hook_value&& s )
96                 : nKey(s.nKey)
97                 , nValue(s.nValue)
98                 , hook()
99             {}
100             member_hook_value& operator=( member_hook_value const& s )
101             {
102                 nKey = s.nKey;
103                 nValue = s.nValue;
104                 return *this;
105             }
106 #   endif
107         };
108
109         template <typename ValueType>
110         struct less {
111             typedef ValueType value_type;
112
113             bool operator()( int k1, int k2 ) const
114             {
115                 return k1 < k2;
116             }
117             bool operator()( value_type const& v1, value_type const& v2 ) const
118             {
119                 return v1.nKey < v2.nKey;
120             }
121             bool operator()( value_type const& v, int k ) const
122             {
123                 return v.nKey < k;
124             }
125             bool operator()( int k, value_type const& v ) const
126             {
127                 return k < v.nKey;
128             }
129         };
130
131         template <typename ValueType>
132         struct compare {
133             typedef ValueType value_type;
134
135             int cmp( int k1, int k2 ) const
136             {
137                 return k1 < k2 ? -1 : (k1 > k2 ? 1 : 0);
138             }
139             int operator()( int k1, int k2 ) const
140             {
141                 return cmp( k1, k2 );
142             }
143             int operator()( value_type const& v1, value_type const& v2 ) const
144             {
145                 return cmp( v1.nKey, v2.nKey );
146             }
147             int operator()( value_type const& v, int k ) const
148             {
149                 return cmp( v.nKey, k );
150             }
151             int operator()( int k, value_type const& v ) const
152             {
153                 return cmp( k, v.nKey );
154             }
155         };
156
157         struct wrapped_int {
158             int  nKey;
159
160             wrapped_int( int n )
161                 : nKey(n)
162             {}
163         };
164
165         template <typename T>
166         struct wrapped_less
167         {
168             bool operator()( wrapped_int const& w, int n ) const
169             {
170                 return w.nKey < n;
171             }
172             bool operator()( int n, wrapped_int const& w ) const
173             {
174                 return n < w.nKey;
175             }
176             bool operator()( wrapped_int const& w, T const& v ) const
177             {
178                 return w.nKey < v.nKey;
179             }
180             bool operator()( T const& v, wrapped_int const& w ) const
181             {
182                 return v.nKey < w.nKey;
183             }
184         };
185
186         template <typename ValueType>
187         struct key_extractor {
188             void operator()( int& dest, ValueType const& src ) const
189             {
190                 dest = src.nKey;
191             }
192         };
193
194         template <typename ValueType>
195         struct disposer {
196             void operator()( ValueType * v ) const
197             {
198                 ++v->stat.nDisposeCount;
199             }
200         };
201
202         struct insert_functor {
203             template <typename T>
204             void operator()( T& v ) const
205             {
206                 ++v.stat.nInsertFuncCall;
207             }
208         };
209
210         struct ensure_functor {
211             template <typename T>
212             void operator()( bool bNew, T& dest, T& src) const
213             {
214                 if ( bNew )
215                     ++dest.stat.nEnsureNewFuncCall;
216                 else {
217                     dest.nValue *= 2;
218                     ++src.stat.nEnsureExistFuncCall;
219                 }
220             }
221         };
222
223         struct erase_functor {
224             template <typename T>
225             void operator()( T const& v ) const
226             {
227                 ++v.stat.nEraseFuncCall;
228             }
229         };
230
231         struct find_functor {
232             template <typename T, typename Q>
233             void operator()( T const& v, Q& q ) const
234             {
235                 ++v.stat.nFindFuncCall;
236             }
237             template <typename T, typename Q>
238             void operator()( T const& v, Q const& q ) const
239             {
240                 ++v.stat.nFindConstFuncCall;
241             }
242         };
243
244     protected:
245         static const size_t c_nItemCount = 10000;
246
247         template <typename T>
248         class data_array
249         {
250             T *     pFirst;
251             T *     pLast;
252
253         public:
254             data_array()
255                 : pFirst( new T[c_nItemCount] )
256                 , pLast( pFirst + c_nItemCount )
257             {
258                 int i = 0;
259                 for ( T * p = pFirst; p != pLast; ++p, ++i ) {
260                     p->nKey = i;
261                     p->nValue = i * 2;
262                 }
263
264                 std::random_shuffle( pFirst, pLast );
265             }
266
267             ~data_array()
268             {
269                 delete [] pFirst;
270             }
271
272             T * begin() { return pFirst; }
273             T * end()   { return pLast ; }
274         };
275
276     protected:
277         template <typename Tree>
278         void test_common( Tree& t )
279         {
280             typedef Tree tree_type;
281             typedef typename tree_type::key_type     key_type;
282             typedef typename tree_type::value_type   value_type;
283
284             {
285                 value_type v1( 10, 100 );
286                 value_type v2( 20, 200 );
287                 value_type v3( 30, 300 );
288                 value_type v4( 25, 250 );
289                 value_type v5( -50, -500 );
290
291                 // insert/ensure
292                 CPPUNIT_ASSERT( t.empty() );
293                 CPPUNIT_ASSERT( misc::check_size( t, 0 ));
294                 CPPUNIT_CHECK( !t.find( v1.nKey ));
295                 CPPUNIT_CHECK( !t.find( v1 ));
296                 CPPUNIT_CHECK( !t.find( v2.nKey ));
297                 CPPUNIT_CHECK( !t.find( v2 ));
298                 CPPUNIT_CHECK( !t.find( v3.nKey ));
299                 CPPUNIT_CHECK( !t.find( v3 ));
300                 CPPUNIT_CHECK( !t.find( v4.nKey ));
301                 CPPUNIT_CHECK( !t.find( v4 ));
302                 CPPUNIT_CHECK( !t.find( v5.nKey ));
303                 CPPUNIT_CHECK( !t.find( v5 ));
304
305                 CPPUNIT_ASSERT( t.insert( v1 ));
306                 CPPUNIT_ASSERT( t.check_consistency() );
307                 CPPUNIT_ASSERT( !t.empty() );
308                 CPPUNIT_ASSERT( misc::check_size( t, 1 ));
309                 CPPUNIT_CHECK( t.find( v1.nKey ));
310                 CPPUNIT_CHECK( t.find( v1 ));
311                 CPPUNIT_CHECK( !t.find( v2.nKey ));
312                 CPPUNIT_CHECK( !t.find( v2 ));
313                 CPPUNIT_CHECK( !t.find( v3.nKey ));
314                 CPPUNIT_CHECK( !t.find( v3 ));
315                 CPPUNIT_CHECK( !t.find( v4.nKey ));
316                 CPPUNIT_CHECK( !t.find( v4 ));
317                 CPPUNIT_CHECK( !t.find( v5.nKey ));
318                 CPPUNIT_CHECK( !t.find( v5 ));
319
320                 CPPUNIT_ASSERT( v2.stat.nInsertFuncCall == 0 );
321                 CPPUNIT_ASSERT( t.insert( v2, insert_functor() ));
322                 CPPUNIT_ASSERT( t.check_consistency() );
323                 CPPUNIT_ASSERT( v2.stat.nInsertFuncCall == 1 );
324                 CPPUNIT_ASSERT( t.find( v1.nKey ));
325                 CPPUNIT_ASSERT( t.find( v1 ));
326                 CPPUNIT_ASSERT( t.find( v2.nKey ));
327                 CPPUNIT_ASSERT( t.find( v2 ));
328                 CPPUNIT_ASSERT( !t.find( v3.nKey ));
329                 CPPUNIT_ASSERT( !t.find( v3 ));
330                 CPPUNIT_ASSERT( !t.find( v4.nKey ));
331                 CPPUNIT_ASSERT( !t.find( v4 ));
332                 CPPUNIT_ASSERT( !t.find( v5.nKey ));
333                 CPPUNIT_ASSERT( !t.find( v5 ));
334                 CPPUNIT_ASSERT( !t.empty() );
335                 CPPUNIT_ASSERT( misc::check_size( t, 2 ));
336
337                 CPPUNIT_ASSERT( v3.stat.nEnsureNewFuncCall == 0 );
338                 CPPUNIT_ASSERT( v3.stat.nEnsureExistFuncCall == 0 );
339                 CPPUNIT_ASSERT( t.ensure( v3, ensure_functor() ).second );
340                 CPPUNIT_ASSERT( t.check_consistency() );
341                 CPPUNIT_ASSERT( v3.stat.nEnsureNewFuncCall == 1 );
342                 CPPUNIT_ASSERT( v3.stat.nEnsureExistFuncCall == 0 );
343                 CPPUNIT_ASSERT( v3.nValue == 300 );
344                 CPPUNIT_ASSERT( !t.ensure( v3, ensure_functor() ).second );
345                 CPPUNIT_ASSERT( v3.stat.nEnsureNewFuncCall == 1 );
346                 CPPUNIT_ASSERT( v3.stat.nEnsureExistFuncCall == 1 );
347                 CPPUNIT_ASSERT( v3.nValue == 600 );
348                 CPPUNIT_ASSERT( t.find( v1.nKey ));
349                 CPPUNIT_ASSERT( t.find( v1 ));
350                 CPPUNIT_ASSERT( t.find( v2.nKey ));
351                 CPPUNIT_ASSERT( t.find( v2 ));
352                 CPPUNIT_ASSERT( t.find( v3.nKey ));
353                 CPPUNIT_ASSERT( t.find( v3 ));
354                 CPPUNIT_ASSERT( !t.find( v4.nKey ));
355                 CPPUNIT_ASSERT( !t.find( v4 ));
356                 CPPUNIT_ASSERT( !t.find( v5.nKey ));
357                 CPPUNIT_ASSERT( !t.find( v5 ));
358                 CPPUNIT_ASSERT( !t.empty() );
359                 CPPUNIT_ASSERT( misc::check_size( t, 3 ));
360
361                 {
362                     value_type v( v3.nKey, v3.nValue );
363                     CPPUNIT_ASSERT( v.stat.nEnsureExistFuncCall == 0 );
364                     CPPUNIT_ASSERT( v3.stat.nEnsureNewFuncCall == 1 );
365                     CPPUNIT_ASSERT( v3.stat.nEnsureExistFuncCall == 1 );
366                     CPPUNIT_ASSERT( v3.nValue == 600 );
367                     CPPUNIT_ASSERT( !t.ensure( v, ensure_functor() ).second );
368                     CPPUNIT_ASSERT( v3.stat.nEnsureNewFuncCall == 1 );
369                     CPPUNIT_ASSERT( v.stat.nEnsureExistFuncCall == 1 );
370                     CPPUNIT_ASSERT( v3.nValue == 1200 );
371
372                 }
373                 v3.nValue = 300;
374                 CPPUNIT_ASSERT( !t.insert( v3 ));
375
376                 CPPUNIT_ASSERT( t.insert( v4 ));
377                 CPPUNIT_ASSERT( t.check_consistency() );
378                 CPPUNIT_ASSERT( t.find( v1.nKey ));
379                 CPPUNIT_ASSERT( t.find( v1 ));
380                 CPPUNIT_ASSERT( t.find( v2.nKey ));
381                 CPPUNIT_ASSERT( t.find( v2 ));
382                 CPPUNIT_ASSERT( t.find( v3.nKey ));
383                 CPPUNIT_ASSERT( t.find( v3 ));
384                 CPPUNIT_ASSERT( t.find( v4.nKey ));
385                 CPPUNIT_ASSERT( t.find( v4 ));
386                 CPPUNIT_ASSERT( !t.find( v5.nKey ));
387                 CPPUNIT_ASSERT( !t.find( v5 ));
388                 CPPUNIT_ASSERT( !t.empty() );
389                 CPPUNIT_ASSERT( misc::check_size( t, 4 ));
390
391                 CPPUNIT_ASSERT( t.insert( v5 ));
392                 CPPUNIT_ASSERT( t.check_consistency() );
393                 CPPUNIT_ASSERT( t.find( v1.nKey ));
394                 CPPUNIT_ASSERT( t.find( v1 ));
395                 CPPUNIT_ASSERT( t.find( v2.nKey ));
396                 CPPUNIT_ASSERT( t.find( v2 ));
397                 CPPUNIT_ASSERT( t.find( v3.nKey ));
398                 CPPUNIT_ASSERT( t.find( v3 ));
399                 CPPUNIT_ASSERT( t.find( v4.nKey ));
400                 CPPUNIT_ASSERT( t.find( v4 ));
401                 CPPUNIT_ASSERT( t.find( v5.nKey ));
402                 CPPUNIT_ASSERT( t.find( v5 ));
403                 CPPUNIT_ASSERT( !t.empty() );
404                 CPPUNIT_ASSERT( misc::check_size( t, 5 ));
405
406                 //unlink/erase
407                 ++v1.stat.nWaitingDispCount;
408                 CPPUNIT_ASSERT( t.unlink(v1));
409                 CPPUNIT_ASSERT( t.check_consistency() );
410                 CPPUNIT_ASSERT( !t.find( v1.nKey ));
411                 CPPUNIT_ASSERT( !t.find( v1 ));
412                 CPPUNIT_ASSERT( !t.unlink(v1));
413                 CPPUNIT_ASSERT( t.find( v2.nKey ));
414                 CPPUNIT_ASSERT( t.find( v2 ));
415                 CPPUNIT_ASSERT( t.find( v3.nKey ));
416                 CPPUNIT_ASSERT( t.find( v3 ));
417                 CPPUNIT_ASSERT( t.find( v4.nKey ));
418                 CPPUNIT_ASSERT( t.find( v4 ));
419                 CPPUNIT_ASSERT( t.find( v5.nKey ));
420                 CPPUNIT_ASSERT( t.find( v5 ));
421                 CPPUNIT_ASSERT( !t.empty() );
422                 CPPUNIT_ASSERT( misc::check_size( t, 4 ));
423
424                 ++v2.stat.nWaitingDispCount;
425                 CPPUNIT_ASSERT( t.erase( v2.nKey ));
426                 CPPUNIT_ASSERT( t.check_consistency() );
427                 CPPUNIT_ASSERT( !t.find( v1.nKey ));
428                 CPPUNIT_ASSERT( !t.find( v1 ));
429                 CPPUNIT_ASSERT( !t.find( v2.nKey ));
430                 CPPUNIT_ASSERT( !t.find( v2 ));
431                 CPPUNIT_ASSERT( !t.erase(v2));
432                 CPPUNIT_ASSERT( t.find( v3.nKey ));
433                 CPPUNIT_ASSERT( t.find( v3 ));
434                 CPPUNIT_ASSERT( t.find( v4.nKey ));
435                 CPPUNIT_ASSERT( t.find( v4 ));
436                 CPPUNIT_ASSERT( t.find( v5.nKey ));
437                 CPPUNIT_ASSERT( t.find( v5 ));
438                 CPPUNIT_ASSERT( !t.empty() );
439                 CPPUNIT_ASSERT( misc::check_size( t, 3 ));
440
441                 ++v3.stat.nWaitingDispCount;
442                 CPPUNIT_ASSERT( t.erase_with( v3.nKey, less<value_type>() ));
443                 CPPUNIT_ASSERT( t.check_consistency() );
444                 CPPUNIT_ASSERT( !t.find( v1.nKey ));
445                 CPPUNIT_ASSERT( !t.find( v1 ));
446                 CPPUNIT_ASSERT( !t.find( v2.nKey ));
447                 CPPUNIT_ASSERT( !t.find( v2 ));
448                 CPPUNIT_ASSERT( !t.find( v3.nKey ));
449                 CPPUNIT_ASSERT( !t.find( v3 ));
450                 CPPUNIT_ASSERT( !t.erase_with(v3, less<value_type>() ));
451                 CPPUNIT_ASSERT( t.find( v4.nKey ));
452                 CPPUNIT_ASSERT( t.find( v4 ));
453                 CPPUNIT_ASSERT( t.find( v5.nKey ));
454                 CPPUNIT_ASSERT( t.find( v5 ));
455                 CPPUNIT_ASSERT( !t.empty() );
456                 CPPUNIT_ASSERT( misc::check_size( t, 2 ));
457
458                 ++v4.stat.nWaitingDispCount;
459                 CPPUNIT_ASSERT( v4.stat.nEraseFuncCall == 0 );
460                 CPPUNIT_ASSERT( t.erase( v4.nKey, erase_functor() ));
461                 CPPUNIT_ASSERT( t.check_consistency() );
462                 CPPUNIT_ASSERT( v4.stat.nEraseFuncCall == 1 );
463                 CPPUNIT_ASSERT( !t.find( v1.nKey ));
464                 CPPUNIT_ASSERT( !t.find( v1 ));
465                 CPPUNIT_ASSERT( !t.find( v2.nKey ));
466                 CPPUNIT_ASSERT( !t.find( v2 ));
467                 CPPUNIT_ASSERT( !t.find( v3.nKey ));
468                 CPPUNIT_ASSERT( !t.find( v3 ));
469                 CPPUNIT_ASSERT( !t.find( v4.nKey ));
470                 CPPUNIT_ASSERT( !t.find( v4 ));
471                 CPPUNIT_ASSERT( !t.erase( v4.nKey, erase_functor() ));
472                 CPPUNIT_ASSERT( v4.stat.nEraseFuncCall == 1 );
473                 CPPUNIT_ASSERT( t.find( v5.nKey ));
474                 CPPUNIT_ASSERT( t.find( v5 ));
475                 CPPUNIT_ASSERT( !t.empty() );
476                 CPPUNIT_ASSERT( misc::check_size( t, 1 ));
477
478                 ++v5.stat.nWaitingDispCount;
479                 CPPUNIT_ASSERT( t.erase_with( v5.nKey, less<value_type>(), erase_functor() ));
480                 CPPUNIT_ASSERT( t.check_consistency() );
481                 CPPUNIT_ASSERT( v5.stat.nEraseFuncCall == 1 );
482                 CPPUNIT_ASSERT( !t.find( v1.nKey ));
483                 CPPUNIT_ASSERT( !t.find( v1 ));
484                 CPPUNIT_ASSERT( !t.find( v2.nKey ));
485                 CPPUNIT_ASSERT( !t.find( v2 ));
486                 CPPUNIT_ASSERT( !t.find( v3.nKey ));
487                 CPPUNIT_ASSERT( !t.find( v3 ));
488                 CPPUNIT_ASSERT( !t.erase_with(v5, less<value_type>(), erase_functor() ));
489                 CPPUNIT_ASSERT( !t.find( v4.nKey ));
490                 CPPUNIT_ASSERT( !t.find( v4 ));
491                 CPPUNIT_ASSERT( !t.find( v5.nKey ));
492                 CPPUNIT_ASSERT( !t.find( v5 ));
493                 CPPUNIT_ASSERT( t.empty() );
494                 CPPUNIT_ASSERT( misc::check_size( t, 0 ));
495
496                 tree_type::gc::force_dispose();
497
498                 // find
499                 CPPUNIT_ASSERT( t.insert( v1 ));
500                 CPPUNIT_ASSERT( t.insert( v2 ));
501                 CPPUNIT_ASSERT( t.insert( v3 ));
502                 CPPUNIT_ASSERT( t.insert( v4 ));
503                 CPPUNIT_ASSERT( t.insert( v5 ));
504                 CPPUNIT_ASSERT( t.check_consistency() );
505                 CPPUNIT_ASSERT( !t.empty() );
506                 CPPUNIT_ASSERT( misc::check_size( t, 5 ));
507
508                 CPPUNIT_ASSERT( t.find( 10 ));
509                 CPPUNIT_ASSERT( !t.find( 11 ));
510                 CPPUNIT_ASSERT( t.find( v1 ));
511                 CPPUNIT_ASSERT( t.find( v2.nKey ));
512                 CPPUNIT_ASSERT( t.find( v3 ));
513                 CPPUNIT_ASSERT( t.find( v4.nKey ));
514                 CPPUNIT_ASSERT( t.find( v5.nKey ));
515
516                 // find_with
517                 CPPUNIT_ASSERT( t.find_with( 10, less<value_type>() ));
518                 CPPUNIT_ASSERT( !t.find_with( wrapped_int(11), wrapped_less<value_type>() ));
519                 CPPUNIT_ASSERT( t.find_with( v1, less<value_type>() ));
520                 CPPUNIT_ASSERT( t.find_with( wrapped_int(v2.nKey), wrapped_less<value_type>() ));
521                 CPPUNIT_ASSERT( t.find_with( v3, less<value_type>() ));
522                 CPPUNIT_ASSERT( t.find_with( v4.nKey, less<value_type>() ));
523                 CPPUNIT_ASSERT( t.find_with( v5.nKey, less<value_type>() ));
524
525                 // find<Func>
526                 CPPUNIT_ASSERT( v1.stat.nFindFuncCall == 0 );
527                 CPPUNIT_ASSERT( v1.stat.nFindConstFuncCall == 0 );
528                 CPPUNIT_ASSERT( t.find( 10, find_functor() ));
529                 CPPUNIT_ASSERT( v1.stat.nFindFuncCall == 0 );
530                 CPPUNIT_ASSERT( v1.stat.nFindConstFuncCall == 1 );
531
532                 CPPUNIT_ASSERT( !t.find( 11, find_functor() ));
533
534                 CPPUNIT_ASSERT( t.find( v1, find_functor() ));
535                 CPPUNIT_ASSERT( v1.stat.nFindFuncCall == 1 );
536                 CPPUNIT_ASSERT( v1.stat.nFindConstFuncCall == 1 );
537
538                 CPPUNIT_ASSERT( v2.stat.nFindFuncCall == 0 );
539                 CPPUNIT_ASSERT( v2.stat.nFindConstFuncCall == 0 );
540                 CPPUNIT_ASSERT( t.find( v2.nKey, find_functor() ));
541                 CPPUNIT_ASSERT( v2.stat.nFindFuncCall == 1 );
542                 CPPUNIT_ASSERT( v2.stat.nFindConstFuncCall == 0 );
543
544                 CPPUNIT_ASSERT( v3.stat.nFindFuncCall == 0 );
545                 CPPUNIT_ASSERT( v3.stat.nFindConstFuncCall == 0 );
546                 CPPUNIT_ASSERT( t.find( v3, find_functor() ));
547                 CPPUNIT_ASSERT( v3.stat.nFindFuncCall == 1 );
548                 CPPUNIT_ASSERT( v3.stat.nFindConstFuncCall == 0 );
549
550                 CPPUNIT_ASSERT( v4.stat.nFindFuncCall == 0 );
551                 CPPUNIT_ASSERT( v4.stat.nFindConstFuncCall == 0 );
552                 CPPUNIT_ASSERT( t.find( (value_type const&) v4, find_functor() ));
553                 CPPUNIT_ASSERT( v4.stat.nFindFuncCall == 0 );
554                 CPPUNIT_ASSERT( v4.stat.nFindConstFuncCall == 1 );
555
556                 CPPUNIT_ASSERT( v5.stat.nFindFuncCall == 0 );
557                 CPPUNIT_ASSERT( v5.stat.nFindConstFuncCall == 0 );
558                 CPPUNIT_ASSERT( t.find( v5.nKey, find_functor() ));
559                 CPPUNIT_ASSERT( v5.stat.nFindFuncCall == 1 );
560                 CPPUNIT_ASSERT( v5.stat.nFindConstFuncCall == 0 );
561
562                 // find_with<Func>
563                 CPPUNIT_ASSERT( v1.stat.nFindFuncCall == 1 );
564                 CPPUNIT_ASSERT( v1.stat.nFindConstFuncCall == 1 );
565                 CPPUNIT_ASSERT( t.find_with( 10, less<value_type>(), find_functor() ));
566                 CPPUNIT_ASSERT( v1.stat.nFindFuncCall == 1 );
567                 CPPUNIT_ASSERT( v1.stat.nFindConstFuncCall == 2 );
568
569                 CPPUNIT_ASSERT( !t.find_with( 11, less<value_type>(), find_functor() ));
570
571                 CPPUNIT_ASSERT( t.find_with( v1, less<value_type>(), find_functor() ));
572                 CPPUNIT_ASSERT( v1.stat.nFindFuncCall == 2 );
573                 CPPUNIT_ASSERT( v1.stat.nFindConstFuncCall == 2 );
574
575                 CPPUNIT_ASSERT( v2.stat.nFindFuncCall == 1 );
576                 CPPUNIT_ASSERT( v2.stat.nFindConstFuncCall == 0 );
577                 CPPUNIT_ASSERT( t.find_with( v2.nKey, less<value_type>(), find_functor() ));
578                 CPPUNIT_ASSERT( v2.stat.nFindFuncCall == 2 );
579                 CPPUNIT_ASSERT( v2.stat.nFindConstFuncCall == 0 );
580
581                 CPPUNIT_ASSERT( v3.stat.nFindFuncCall == 1 );
582                 CPPUNIT_ASSERT( v3.stat.nFindConstFuncCall == 0 );
583                 CPPUNIT_ASSERT( t.find_with( wrapped_int(v3.nKey), wrapped_less<value_type>(), find_functor() ));
584                 CPPUNIT_ASSERT( v3.stat.nFindFuncCall == 1 );
585                 CPPUNIT_ASSERT( v3.stat.nFindConstFuncCall == 1 );
586
587                 CPPUNIT_ASSERT( v4.stat.nFindFuncCall == 0 );
588                 CPPUNIT_ASSERT( v4.stat.nFindConstFuncCall == 1 );
589                 CPPUNIT_ASSERT( t.find_with( (value_type const&) v4, less<value_type>(), find_functor() ));
590                 CPPUNIT_ASSERT( v4.stat.nFindFuncCall == 0 );
591                 CPPUNIT_ASSERT( v4.stat.nFindConstFuncCall == 2 );
592
593                 CPPUNIT_ASSERT( v5.stat.nFindFuncCall == 1 );
594                 CPPUNIT_ASSERT( v5.stat.nFindConstFuncCall == 0 );
595                 CPPUNIT_ASSERT( t.find_with( v5.nKey, less<value_type>(), find_functor() ));
596                 CPPUNIT_ASSERT( v5.stat.nFindFuncCall == 2 );
597                 CPPUNIT_ASSERT( v5.stat.nFindConstFuncCall == 0 );
598
599                 CPPUNIT_ASSERT( t.check_consistency() );
600                 t.clear();
601                 CPPUNIT_ASSERT( t.check_consistency() );
602                 CPPUNIT_ASSERT( t.empty() );
603                 CPPUNIT_ASSERT( misc::check_size( t, 0 ));
604
605                 tree_type::gc::force_dispose();
606                 CPPUNIT_CHECK_EX( v1.stat.nWaitingDispCount + 1 == v1.stat.nDisposeCount,
607                     "v1.stat.nWaitingDispCount=" << v1.stat.nWaitingDispCount << ", v1.stat.nDisposeCount=" << v1.stat.nDisposeCount );
608                 CPPUNIT_CHECK_EX( v2.stat.nWaitingDispCount + 1 == v2.stat.nDisposeCount,
609                     "v2.stat.nWaitingDispCount=" << v2.stat.nWaitingDispCount << ", v2.stat.nDisposeCount=" << v2.stat.nDisposeCount );
610                 CPPUNIT_CHECK_EX( v3.stat.nWaitingDispCount + 1 == v3.stat.nDisposeCount,
611                     "v3.stat.nWaitingDispCount=" << v3.stat.nWaitingDispCount << ", v3.stat.nDisposeCount=" << v3.stat.nDisposeCount );
612                 CPPUNIT_CHECK_EX( v4.stat.nWaitingDispCount + 1 == v4.stat.nDisposeCount,
613                     "v4.stat.nWaitingDispCount=" << v4.stat.nWaitingDispCount << ", v4.stat.nDisposeCount=" << v4.stat.nDisposeCount );
614                 CPPUNIT_CHECK_EX( v5.stat.nWaitingDispCount + 1 == v5.stat.nDisposeCount,
615                     "v5.stat.nWaitingDispCount=" << v5.stat.nWaitingDispCount << ", v5.stat.nDisposeCount=" << v5.stat.nDisposeCount );
616             }
617
618             {
619                 data_array< value_type> arr;
620                 value_type * pFirst = arr.begin();
621                 value_type * pLast  = arr.end();
622
623                 for ( value_type * p = pFirst; p != pLast; ++p ) {
624                     CPPUNIT_ASSERT( t.insert( *p ) );
625                     CPPUNIT_ASSERT( !t.insert( *p ));
626                 }
627                 CPPUNIT_ASSERT( !t.empty() );
628                 CPPUNIT_ASSERT( misc::check_size( t, c_nItemCount ));
629                 CPPUNIT_ASSERT( t.check_consistency() );
630
631                 for ( int n = 0; n < (int) c_nItemCount; ++n ) {
632                     CPPUNIT_ASSERT_MSG( t.find( n ), n );
633                 }
634                 for ( value_type * p = pFirst; p != pLast; ++p ) {
635                     CPPUNIT_ASSERT( t.find( *p ));
636                     CPPUNIT_ASSERT( t.find( p->nKey ));
637                     CPPUNIT_ASSERT( t.unlink( *p ) );
638                     CPPUNIT_ASSERT( !t.unlink( *p ) );
639                     CPPUNIT_ASSERT( !t.find( p->nKey ));
640                 }
641
642                 tree_type::gc::force_dispose();
643             }
644         }
645
646         template <class Tree, class PrintStat>
647         void test()
648         {
649             typedef Tree tree_type;
650             typedef typename tree_type::key_type     key_type;
651             typedef typename tree_type::value_type   value_type;
652
653             tree_type t;
654             test_common(t);
655
656             {
657                 value_type v1( 10, 100 );
658                 value_type v2( 20, 200 );
659                 value_type v3( 30, 300 );
660                 value_type v4( 25, 250 );
661                 value_type v5( -50, -500 );
662
663                 // extract/extract_min/extract_max
664                 CPPUNIT_ASSERT( t.insert( v1 ));
665                 CPPUNIT_ASSERT( t.insert( v2 ));
666                 CPPUNIT_ASSERT( t.insert( v3 ));
667                 CPPUNIT_ASSERT( t.insert( v4 ));
668                 CPPUNIT_ASSERT( t.insert( v5 ));
669                 CPPUNIT_ASSERT( t.check_consistency() );
670                 CPPUNIT_ASSERT( !t.empty() );
671                 CPPUNIT_ASSERT( misc::check_size( t, 5 ));
672
673                 {
674                     typename tree_type::guarded_ptr gp;
675
676                     gp = t.get( v2.nKey );
677                     CPPUNIT_ASSERT( gp );
678                     CPPUNIT_ASSERT( !gp.empty());
679                     CPPUNIT_CHECK( gp->nKey == v2.nKey );
680                     gp = t.extract( v2.nKey );
681                     CPPUNIT_ASSERT( gp );
682                     CPPUNIT_ASSERT( !gp.empty());
683                     CPPUNIT_ASSERT( t.check_consistency() );
684                     CPPUNIT_ASSERT( !t.empty() );
685                     CPPUNIT_ASSERT( misc::check_size( t, 4 ));
686                     CPPUNIT_ASSERT( gp->nKey == v2.nKey );
687                     gp = t.extract( v2.nKey );
688                     CPPUNIT_ASSERT( !gp );
689                     gp = t.get( v2.nKey );
690                     CPPUNIT_CHECK( !gp );
691                     CPPUNIT_ASSERT( t.check_consistency() );
692                     CPPUNIT_ASSERT( !t.empty() );
693                     CPPUNIT_ASSERT( misc::check_size( t, 4 ));
694
695                     gp = t.extract_min();
696                     CPPUNIT_ASSERT( gp );
697                     CPPUNIT_ASSERT( !gp.empty());
698                     CPPUNIT_ASSERT( t.check_consistency() );
699                     CPPUNIT_ASSERT( !t.empty() );
700                     CPPUNIT_ASSERT( misc::check_size( t, 3 ));
701                     CPPUNIT_ASSERT( gp->nKey == v5.nKey );
702
703                     gp = t.extract_min();
704                     CPPUNIT_ASSERT( gp );
705                     CPPUNIT_ASSERT( t.check_consistency() );
706                     CPPUNIT_ASSERT( !t.empty() );
707                     CPPUNIT_ASSERT( misc::check_size( t, 2 ));
708                     CPPUNIT_ASSERT( gp->nKey == v1.nKey );
709
710                     gp = t.extract_min();
711                     CPPUNIT_ASSERT( gp );
712                     CPPUNIT_ASSERT( t.check_consistency() );
713                     CPPUNIT_ASSERT( !t.empty() );
714                     CPPUNIT_ASSERT( misc::check_size( t, 1 ));
715                     CPPUNIT_ASSERT( gp->nKey == v4.nKey );
716
717                     gp = t.extract_min();
718                     CPPUNIT_ASSERT( gp );
719                     CPPUNIT_ASSERT( t.check_consistency() );
720                     CPPUNIT_ASSERT( t.empty() );
721                     CPPUNIT_ASSERT( misc::check_size( t, 0 ));
722                     CPPUNIT_ASSERT( gp->nKey == v3.nKey );
723
724                     gp = t.extract_min();
725                     CPPUNIT_ASSERT( !gp );
726                     CPPUNIT_ASSERT( !t.extract_max());
727                     CPPUNIT_ASSERT( !t.extract( v1.nKey ));
728                 }
729
730                 tree_type::gc::force_dispose();
731
732                 {
733                     typename tree_type::guarded_ptr gp;
734
735                     CPPUNIT_ASSERT( t.insert( v1 ));
736                     CPPUNIT_ASSERT( t.insert( v2 ));
737                     CPPUNIT_ASSERT( t.insert( v3 ));
738                     CPPUNIT_ASSERT( t.insert( v4 ));
739                     CPPUNIT_ASSERT( t.insert( v5 ));
740                     CPPUNIT_ASSERT( t.check_consistency() );
741                     CPPUNIT_ASSERT( !t.empty() );
742                     CPPUNIT_ASSERT( misc::check_size( t, 5 ));
743
744                     gp = t.get_with( wrapped_int( v4.nKey ), wrapped_less<value_type>());
745                     CPPUNIT_ASSERT( gp );
746                     CPPUNIT_ASSERT( !gp.empty());
747                     CPPUNIT_CHECK( gp->nKey == v4.nKey );
748                     gp = t.extract_with( wrapped_int( v4.nKey ), wrapped_less<value_type>());
749                     CPPUNIT_ASSERT( gp );
750                     CPPUNIT_ASSERT( t.check_consistency() );
751                     CPPUNIT_ASSERT( !t.empty() );
752                     CPPUNIT_ASSERT( misc::check_size( t, 4 ));
753                     CPPUNIT_ASSERT( gp->nKey == v4.nKey );
754
755                     gp = t.extract_with( v4.nKey, less<value_type>());
756                     CPPUNIT_ASSERT( !gp );
757                     CPPUNIT_ASSERT( t.check_consistency() );
758                     CPPUNIT_ASSERT( !t.get_with( v4.nKey, less<value_type>() ) );
759
760                     gp = t.extract_max();
761                     CPPUNIT_ASSERT( gp );
762                     CPPUNIT_ASSERT( t.check_consistency() );
763                     CPPUNIT_ASSERT( !t.empty() );
764                     CPPUNIT_ASSERT( misc::check_size( t, 3 ));
765                     CPPUNIT_ASSERT( gp->nKey == v3.nKey );
766
767                     gp = t.extract_max();
768                     CPPUNIT_ASSERT( gp );
769                     CPPUNIT_ASSERT( t.check_consistency() );
770                     CPPUNIT_ASSERT( !t.empty() );
771                     CPPUNIT_ASSERT( misc::check_size( t, 2 ));
772                     CPPUNIT_ASSERT( gp->nKey == v2.nKey );
773
774                     gp = t.extract_max();
775                     CPPUNIT_ASSERT( gp );
776                     CPPUNIT_ASSERT( t.check_consistency() );
777                     CPPUNIT_ASSERT( !t.empty() );
778                     CPPUNIT_ASSERT( misc::check_size( t, 1 ));
779                     CPPUNIT_ASSERT( gp->nKey == v1.nKey );
780
781                     gp = t.extract_max();
782                     CPPUNIT_ASSERT( gp );
783                     CPPUNIT_ASSERT( t.check_consistency() );
784                     CPPUNIT_ASSERT( t.empty() );
785                     CPPUNIT_ASSERT( misc::check_size( t, 0 ));
786                     CPPUNIT_ASSERT( gp->nKey == v5.nKey );
787                 }
788
789                 tree_type::gc::force_dispose();
790             }
791
792             {
793                 data_array< value_type> arr;
794                 value_type * pFirst = arr.begin();
795                 value_type * pLast  = arr.end();
796
797                 for ( value_type * p = pFirst; p != pLast; ++p ) {
798                     CPPUNIT_ASSERT( t.ensure( *p, ensure_functor()).second );
799                 }
800                 for ( int n = 0; n < (int) c_nItemCount; ++n ) {
801                     typename tree_type::guarded_ptr gp( t.extract_min() );
802                     CPPUNIT_ASSERT( !gp.empty());
803                     CPPUNIT_CHECK( gp->nKey == n );
804                 }
805
806                 for ( value_type * p = pFirst; p != pLast; ++p ) {
807                     CPPUNIT_ASSERT( t.insert( *p ) );
808                 }
809                 for ( int n = (int) c_nItemCount - 1; n >= 0; --n ) {
810                     typename tree_type::guarded_ptr gp( t.extract_max());
811                     CPPUNIT_ASSERT( !gp.empty());
812                     CPPUNIT_CHECK( gp->nKey == n );
813                 }
814
815                 tree_type::gc::force_dispose();
816             }
817
818             PrintStat()( t );
819         }
820
821         template <class Tree, class PrintStat>
822         void test_rcu()
823         {
824             typedef Tree tree_type;
825             typedef typename tree_type::key_type     key_type;
826             typedef typename tree_type::value_type   value_type;
827
828             tree_type t;
829             test_common(t);
830
831             // extract/get
832             {
833                 value_type v1( 10, 100 );
834                 value_type v2( 20, 200 );
835                 value_type v3( 30, 300 );
836                 value_type v4( 25, 250 );
837                 value_type v5( -50, -500 );
838
839                 // extract/extract_min/extract_max
840                 CPPUNIT_ASSERT( t.insert( v1 ));
841                 CPPUNIT_ASSERT( t.insert( v2 ));
842                 CPPUNIT_ASSERT( t.insert( v3 ));
843                 CPPUNIT_ASSERT( t.insert( v4 ));
844                 CPPUNIT_ASSERT( t.insert( v5 ));
845                 CPPUNIT_ASSERT( t.check_consistency() );
846                 CPPUNIT_ASSERT( !t.empty() );
847                 CPPUNIT_ASSERT( misc::check_size( t, 5 ));
848
849                 typename tree_type::exempt_ptr  ep;
850                 typename tree_type::value_type * pVal;
851                 {
852                     typename tree_type::rcu_lock l;
853                     pVal = t.get( v1.nKey );
854                     CPPUNIT_ASSERT( pVal != nullptr );
855                     CPPUNIT_CHECK( pVal == &v1 );
856                 }
857                 ep = t.extract( v1.nKey );
858                 CPPUNIT_ASSERT( !ep.empty());
859                 CPPUNIT_CHECK( ep->nKey == v1.nKey );
860                 {
861                     typename tree_type::rcu_lock l;
862                     CPPUNIT_CHECK( t.get( v1.nKey ) == nullptr );
863                 }
864                 ep.release();
865                 ep = t.extract( v1.nKey );
866                 CPPUNIT_ASSERT( ep.empty());
867
868                 ep = t.extract_min();
869                 CPPUNIT_ASSERT( !ep.empty() );
870                 CPPUNIT_CHECK( ep->nKey == v5.nKey );
871                 {
872                     typename tree_type::rcu_lock l;
873                     CPPUNIT_CHECK( t.get( v5.nKey ) == nullptr );
874                 }
875
876                 ep = t.extract( v5.nKey );
877                 CPPUNIT_ASSERT( ep.empty() );
878
879                 ep = t.extract_max();
880                 CPPUNIT_ASSERT( !ep.empty());
881                 CPPUNIT_CHECK( ep->nKey == v3.nKey );
882                 {
883                     typename tree_type::rcu_lock l;
884                     CPPUNIT_CHECK( t.get( v3.nKey ) == nullptr );
885                 }
886                 ep.release();
887
888                 {
889                     typename tree_type::rcu_lock l;
890                     pVal = t.get_with( wrapped_int(v2.nKey), wrapped_less<value_type>() );
891                     CPPUNIT_ASSERT( pVal != nullptr );
892                     CPPUNIT_CHECK( pVal == &v2 );
893                 }
894                 ep = t.extract_with( wrapped_int( v2.nKey ), wrapped_less<value_type>() );
895                 CPPUNIT_ASSERT( !ep.empty() );
896                 CPPUNIT_CHECK( ep->nKey == v2.nKey );
897                 {
898                     typename tree_type::rcu_lock l;
899                     CPPUNIT_CHECK( t.get_with( wrapped_int( v2.nKey ), wrapped_less<value_type>() ) == nullptr );
900                 }
901                 //ep.release();
902                 ep = t.extract_with( wrapped_int( v2.nKey ), wrapped_less<value_type>() );
903                 CPPUNIT_CHECK( ep.empty());
904
905                 ep = t.extract( v4.nKey );
906                 CPPUNIT_ASSERT( ep );
907                 CPPUNIT_CHECK( ep->nKey == v4.nKey );
908                 ep.release();
909
910                 tree_type::gc::force_dispose();
911
912                 CPPUNIT_CHECK( t.empty());
913                 CPPUNIT_ASSERT( misc::check_size( t, 0 ));
914
915                 {
916                     typename tree_type::rcu_lock l;
917                     CPPUNIT_CHECK( t.get( v1.nKey ) == nullptr );
918                     CPPUNIT_CHECK( t.get( v2.nKey ) == nullptr );
919                     CPPUNIT_CHECK( t.get( v3.nKey ) == nullptr );
920                     CPPUNIT_CHECK( t.get( v4.nKey ) == nullptr );
921                     CPPUNIT_CHECK( t.get( v5.nKey ) == nullptr );
922                 }
923
924                 CPPUNIT_CHECK( !t.extract(v1.nKey));
925                 CPPUNIT_CHECK( !t.extract(v2.nKey));
926                 CPPUNIT_CHECK( !t.extract(v3.nKey));
927                 CPPUNIT_CHECK( !t.extract(v4.nKey));
928                 CPPUNIT_CHECK( !t.extract(v5.nKey));
929
930                 tree_type::gc::force_dispose();
931             }
932
933             PrintStat()( t );
934         }
935
936         void EllenBinTree_hp_base_less();
937         void EllenBinTree_hp_base_cmp();
938         void EllenBinTree_hp_base_cmpless();
939         void EllenBinTree_hp_base_less_ic();
940         void EllenBinTree_hp_base_cmp_ic();
941         void EllenBinTree_hp_base_less_stat();
942         void EllenBinTree_hp_base_cmp_ic_stat();
943         void EllenBinTree_hp_base_cmp_ic_stat_yield();
944         void EllenBinTree_hp_base_less_pool();
945         void EllenBinTree_hp_base_less_pool_ic_stat();
946
947         void EllenBinTree_hp_member_less();
948         void EllenBinTree_hp_member_cmp();
949         void EllenBinTree_hp_member_cmpless();
950         void EllenBinTree_hp_member_less_ic();
951         void EllenBinTree_hp_member_cmp_ic();
952         void EllenBinTree_hp_member_less_stat();
953         void EllenBinTree_hp_member_cmp_ic_stat();
954         void EllenBinTree_hp_member_cmp_ic_stat_yield();
955         void EllenBinTree_hp_member_less_pool();
956         void EllenBinTree_hp_member_less_pool_ic_stat();
957
958         void EllenBinTree_dhp_base_less();
959         void EllenBinTree_dhp_base_cmp();
960         void EllenBinTree_dhp_base_cmpless();
961         void EllenBinTree_dhp_base_less_ic();
962         void EllenBinTree_dhp_base_cmp_ic();
963         void EllenBinTree_dhp_base_less_stat();
964         void EllenBinTree_dhp_base_cmp_ic_stat();
965         void EllenBinTree_dhp_base_cmp_ic_stat_yield();
966         void EllenBinTree_dhp_base_less_pool();
967         void EllenBinTree_dhp_base_less_pool_ic_stat();
968
969         void EllenBinTree_dhp_member_less();
970         void EllenBinTree_dhp_member_cmp();
971         void EllenBinTree_dhp_member_cmpless();
972         void EllenBinTree_dhp_member_less_ic();
973         void EllenBinTree_dhp_member_cmp_ic();
974         void EllenBinTree_dhp_member_less_stat();
975         void EllenBinTree_dhp_member_cmp_ic_stat();
976         void EllenBinTree_dhp_member_cmp_ic_stat_yield();
977         void EllenBinTree_dhp_member_less_pool();
978         void EllenBinTree_dhp_member_less_pool_ic_stat();
979
980         void EllenBinTree_rcu_gpi_base_less();
981         void EllenBinTree_rcu_gpi_base_cmp();
982         void EllenBinTree_rcu_gpi_base_cmpless();
983         void EllenBinTree_rcu_gpi_base_less_ic();
984         void EllenBinTree_rcu_gpi_base_cmp_ic();
985         void EllenBinTree_rcu_gpi_base_less_stat();
986         void EllenBinTree_rcu_gpi_base_cmp_ic_stat();
987         void EllenBinTree_rcu_gpi_base_cmp_ic_stat_yield();
988         void EllenBinTree_rcu_gpi_base_less_pool();
989         void EllenBinTree_rcu_gpi_base_less_pool_ic_stat();
990
991         void EllenBinTree_rcu_gpi_member_less();
992         void EllenBinTree_rcu_gpi_member_cmp();
993         void EllenBinTree_rcu_gpi_member_cmpless();
994         void EllenBinTree_rcu_gpi_member_less_ic();
995         void EllenBinTree_rcu_gpi_member_cmp_ic();
996         void EllenBinTree_rcu_gpi_member_less_stat();
997         void EllenBinTree_rcu_gpi_member_cmp_ic_stat();
998         void EllenBinTree_rcu_gpi_member_cmp_ic_stat_yield();
999         void EllenBinTree_rcu_gpi_member_less_pool();
1000         void EllenBinTree_rcu_gpi_member_less_pool_ic_stat();
1001
1002         void EllenBinTree_rcu_gpb_base_less();
1003         void EllenBinTree_rcu_gpb_base_cmp();
1004         void EllenBinTree_rcu_gpb_base_cmpless();
1005         void EllenBinTree_rcu_gpb_base_less_ic();
1006         void EllenBinTree_rcu_gpb_base_cmp_ic();
1007         void EllenBinTree_rcu_gpb_base_less_stat();
1008         void EllenBinTree_rcu_gpb_base_cmp_ic_stat();
1009         void EllenBinTree_rcu_gpb_base_cmp_ic_stat_yield();
1010         void EllenBinTree_rcu_gpb_base_less_pool();
1011         void EllenBinTree_rcu_gpb_base_less_pool_ic_stat();
1012
1013         void EllenBinTree_rcu_gpb_member_less();
1014         void EllenBinTree_rcu_gpb_member_cmp();
1015         void EllenBinTree_rcu_gpb_member_cmpless();
1016         void EllenBinTree_rcu_gpb_member_less_ic();
1017         void EllenBinTree_rcu_gpb_member_cmp_ic();
1018         void EllenBinTree_rcu_gpb_member_less_stat();
1019         void EllenBinTree_rcu_gpb_member_cmp_ic_stat();
1020         void EllenBinTree_rcu_gpb_member_cmp_ic_stat_yield();
1021         void EllenBinTree_rcu_gpb_member_less_pool();
1022         void EllenBinTree_rcu_gpb_member_less_pool_ic_stat();
1023
1024         void EllenBinTree_rcu_gpt_base_less();
1025         void EllenBinTree_rcu_gpt_base_cmp();
1026         void EllenBinTree_rcu_gpt_base_cmpless();
1027         void EllenBinTree_rcu_gpt_base_less_ic();
1028         void EllenBinTree_rcu_gpt_base_cmp_ic();
1029         void EllenBinTree_rcu_gpt_base_less_stat();
1030         void EllenBinTree_rcu_gpt_base_cmp_ic_stat();
1031         void EllenBinTree_rcu_gpt_base_cmp_ic_stat_yield();
1032         void EllenBinTree_rcu_gpt_base_less_pool();
1033         void EllenBinTree_rcu_gpt_base_less_pool_ic_stat();
1034
1035         void EllenBinTree_rcu_gpt_member_less();
1036         void EllenBinTree_rcu_gpt_member_cmp();
1037         void EllenBinTree_rcu_gpt_member_cmpless();
1038         void EllenBinTree_rcu_gpt_member_less_ic();
1039         void EllenBinTree_rcu_gpt_member_cmp_ic();
1040         void EllenBinTree_rcu_gpt_member_less_stat();
1041         void EllenBinTree_rcu_gpt_member_cmp_ic_stat();
1042         void EllenBinTree_rcu_gpt_member_cmp_ic_stat_yield();
1043         void EllenBinTree_rcu_gpt_member_less_pool();
1044         void EllenBinTree_rcu_gpt_member_less_pool_ic_stat();
1045
1046         void EllenBinTree_rcu_shb_base_less();
1047         void EllenBinTree_rcu_shb_base_cmp();
1048         void EllenBinTree_rcu_shb_base_cmpless();
1049         void EllenBinTree_rcu_shb_base_less_ic();
1050         void EllenBinTree_rcu_shb_base_cmp_ic();
1051         void EllenBinTree_rcu_shb_base_less_stat();
1052         void EllenBinTree_rcu_shb_base_cmp_ic_stat();
1053         void EllenBinTree_rcu_shb_base_cmp_ic_stat_yield();
1054         void EllenBinTree_rcu_shb_base_less_pool();
1055         void EllenBinTree_rcu_shb_base_less_pool_ic_stat();
1056
1057         void EllenBinTree_rcu_shb_member_less();
1058         void EllenBinTree_rcu_shb_member_cmp();
1059         void EllenBinTree_rcu_shb_member_cmpless();
1060         void EllenBinTree_rcu_shb_member_less_ic();
1061         void EllenBinTree_rcu_shb_member_cmp_ic();
1062         void EllenBinTree_rcu_shb_member_less_stat();
1063         void EllenBinTree_rcu_shb_member_cmp_ic_stat();
1064         void EllenBinTree_rcu_shb_member_cmp_ic_stat_yield();
1065         void EllenBinTree_rcu_shb_member_less_pool();
1066         void EllenBinTree_rcu_shb_member_less_pool_ic_stat();
1067
1068         void EllenBinTree_rcu_sht_base_less();
1069         void EllenBinTree_rcu_sht_base_cmp();
1070         void EllenBinTree_rcu_sht_base_cmpless();
1071         void EllenBinTree_rcu_sht_base_less_ic();
1072         void EllenBinTree_rcu_sht_base_cmp_ic();
1073         void EllenBinTree_rcu_sht_base_less_stat();
1074         void EllenBinTree_rcu_sht_base_cmp_ic_stat();
1075         void EllenBinTree_rcu_sht_base_cmp_ic_stat_yield();
1076         void EllenBinTree_rcu_sht_base_less_pool();
1077         void EllenBinTree_rcu_sht_base_less_pool_ic_stat();
1078
1079         void EllenBinTree_rcu_sht_member_less();
1080         void EllenBinTree_rcu_sht_member_cmp();
1081         void EllenBinTree_rcu_sht_member_cmpless();
1082         void EllenBinTree_rcu_sht_member_less_ic();
1083         void EllenBinTree_rcu_sht_member_cmp_ic();
1084         void EllenBinTree_rcu_sht_member_less_stat();
1085         void EllenBinTree_rcu_sht_member_cmp_ic_stat();
1086         void EllenBinTree_rcu_sht_member_cmp_ic_stat_yield();
1087         void EllenBinTree_rcu_sht_member_less_pool();
1088         void EllenBinTree_rcu_sht_member_less_pool_ic_stat();
1089
1090         CPPUNIT_TEST_SUITE(IntrusiveBinTreeHdrTest)
1091             CPPUNIT_TEST(EllenBinTree_hp_base_less)
1092             CPPUNIT_TEST(EllenBinTree_hp_base_cmp)
1093             CPPUNIT_TEST(EllenBinTree_hp_base_less_stat)
1094             CPPUNIT_TEST(EllenBinTree_hp_base_cmpless)
1095             CPPUNIT_TEST(EllenBinTree_hp_base_less_ic)
1096             CPPUNIT_TEST(EllenBinTree_hp_base_cmp_ic)
1097             CPPUNIT_TEST(EllenBinTree_hp_base_cmp_ic_stat)
1098             CPPUNIT_TEST( EllenBinTree_hp_base_cmp_ic_stat_yield )
1099             CPPUNIT_TEST( EllenBinTree_hp_base_less_pool )
1100             CPPUNIT_TEST(EllenBinTree_hp_base_less_pool_ic_stat)
1101
1102             CPPUNIT_TEST(EllenBinTree_hp_member_less)
1103             CPPUNIT_TEST(EllenBinTree_hp_member_cmp)
1104             CPPUNIT_TEST(EllenBinTree_hp_member_less_stat)
1105             CPPUNIT_TEST(EllenBinTree_hp_member_cmpless)
1106             CPPUNIT_TEST(EllenBinTree_hp_member_less_ic)
1107             CPPUNIT_TEST(EllenBinTree_hp_member_cmp_ic)
1108             CPPUNIT_TEST( EllenBinTree_hp_member_cmp_ic_stat )
1109             CPPUNIT_TEST( EllenBinTree_hp_member_cmp_ic_stat_yield )
1110             CPPUNIT_TEST(EllenBinTree_hp_member_less_pool)
1111             CPPUNIT_TEST(EllenBinTree_hp_member_less_pool_ic_stat)
1112
1113             CPPUNIT_TEST(EllenBinTree_dhp_base_less)
1114             CPPUNIT_TEST(EllenBinTree_dhp_base_cmp)
1115             CPPUNIT_TEST(EllenBinTree_dhp_base_less_stat)
1116             CPPUNIT_TEST(EllenBinTree_dhp_base_cmpless)
1117             CPPUNIT_TEST(EllenBinTree_dhp_base_less_ic)
1118             CPPUNIT_TEST(EllenBinTree_dhp_base_cmp_ic)
1119             CPPUNIT_TEST(EllenBinTree_dhp_base_cmp_ic_stat)
1120             CPPUNIT_TEST( EllenBinTree_dhp_base_cmp_ic_stat_yield )
1121             CPPUNIT_TEST( EllenBinTree_dhp_base_less_pool )
1122             CPPUNIT_TEST(EllenBinTree_dhp_base_less_pool_ic_stat)
1123
1124             CPPUNIT_TEST(EllenBinTree_dhp_member_less)
1125             CPPUNIT_TEST(EllenBinTree_dhp_member_cmp)
1126             CPPUNIT_TEST(EllenBinTree_dhp_member_less_stat)
1127             CPPUNIT_TEST(EllenBinTree_dhp_member_cmpless)
1128             CPPUNIT_TEST(EllenBinTree_dhp_member_less_ic)
1129             CPPUNIT_TEST(EllenBinTree_dhp_member_cmp_ic)
1130             CPPUNIT_TEST(EllenBinTree_dhp_member_cmp_ic_stat)
1131             CPPUNIT_TEST( EllenBinTree_dhp_member_cmp_ic_stat_yield )
1132             CPPUNIT_TEST( EllenBinTree_dhp_member_less_pool )
1133             CPPUNIT_TEST(EllenBinTree_dhp_member_less_pool_ic_stat)
1134
1135             CPPUNIT_TEST(EllenBinTree_rcu_gpi_base_less)
1136             CPPUNIT_TEST(EllenBinTree_rcu_gpi_base_cmp)
1137             CPPUNIT_TEST(EllenBinTree_rcu_gpi_base_less_stat)
1138             CPPUNIT_TEST(EllenBinTree_rcu_gpi_base_cmpless)
1139             CPPUNIT_TEST(EllenBinTree_rcu_gpi_base_less_ic)
1140             CPPUNIT_TEST(EllenBinTree_rcu_gpi_base_cmp_ic)
1141             CPPUNIT_TEST(EllenBinTree_rcu_gpi_base_cmp_ic_stat)
1142             CPPUNIT_TEST( EllenBinTree_rcu_gpi_base_cmp_ic_stat_yield )
1143             CPPUNIT_TEST( EllenBinTree_rcu_gpi_base_less_pool )
1144             CPPUNIT_TEST(EllenBinTree_rcu_gpi_base_less_pool_ic_stat)
1145
1146             CPPUNIT_TEST(EllenBinTree_rcu_gpi_member_less)
1147             CPPUNIT_TEST(EllenBinTree_rcu_gpi_member_cmp)
1148             CPPUNIT_TEST(EllenBinTree_rcu_gpi_member_less_stat)
1149             CPPUNIT_TEST(EllenBinTree_rcu_gpi_member_cmpless)
1150             CPPUNIT_TEST(EllenBinTree_rcu_gpi_member_less_ic)
1151             CPPUNIT_TEST(EllenBinTree_rcu_gpi_member_cmp_ic)
1152             CPPUNIT_TEST(EllenBinTree_rcu_gpi_member_cmp_ic_stat)
1153             CPPUNIT_TEST( EllenBinTree_rcu_gpi_member_cmp_ic_stat_yield )
1154             CPPUNIT_TEST( EllenBinTree_rcu_gpi_member_less_pool )
1155             CPPUNIT_TEST(EllenBinTree_rcu_gpi_member_less_pool_ic_stat)
1156
1157             CPPUNIT_TEST(EllenBinTree_rcu_gpb_base_less)
1158             CPPUNIT_TEST(EllenBinTree_rcu_gpb_base_cmp)
1159             CPPUNIT_TEST(EllenBinTree_rcu_gpb_base_less_stat)
1160             CPPUNIT_TEST(EllenBinTree_rcu_gpb_base_cmpless)
1161             CPPUNIT_TEST(EllenBinTree_rcu_gpb_base_less_ic)
1162             CPPUNIT_TEST(EllenBinTree_rcu_gpb_base_cmp_ic)
1163             CPPUNIT_TEST(EllenBinTree_rcu_gpb_base_cmp_ic_stat)
1164             CPPUNIT_TEST( EllenBinTree_rcu_gpb_base_cmp_ic_stat_yield )
1165             CPPUNIT_TEST( EllenBinTree_rcu_gpb_base_less_pool )
1166             CPPUNIT_TEST(EllenBinTree_rcu_gpb_base_less_pool_ic_stat)
1167
1168             CPPUNIT_TEST(EllenBinTree_rcu_gpb_member_less)
1169             CPPUNIT_TEST(EllenBinTree_rcu_gpb_member_cmp)
1170             CPPUNIT_TEST(EllenBinTree_rcu_gpb_member_less_stat)
1171             CPPUNIT_TEST(EllenBinTree_rcu_gpb_member_cmpless)
1172             CPPUNIT_TEST(EllenBinTree_rcu_gpb_member_less_ic)
1173             CPPUNIT_TEST(EllenBinTree_rcu_gpb_member_cmp_ic)
1174             CPPUNIT_TEST(EllenBinTree_rcu_gpb_member_cmp_ic_stat)
1175             CPPUNIT_TEST( EllenBinTree_rcu_gpb_member_cmp_ic_stat_yield )
1176             CPPUNIT_TEST( EllenBinTree_rcu_gpb_member_less_pool )
1177             CPPUNIT_TEST(EllenBinTree_rcu_gpb_member_less_pool_ic_stat)
1178
1179             CPPUNIT_TEST(EllenBinTree_rcu_gpt_base_less)
1180             CPPUNIT_TEST(EllenBinTree_rcu_gpt_base_cmp)
1181             CPPUNIT_TEST(EllenBinTree_rcu_gpt_base_less_stat)
1182             CPPUNIT_TEST(EllenBinTree_rcu_gpt_base_cmpless)
1183             CPPUNIT_TEST(EllenBinTree_rcu_gpt_base_less_ic)
1184             CPPUNIT_TEST(EllenBinTree_rcu_gpt_base_cmp_ic)
1185             CPPUNIT_TEST(EllenBinTree_rcu_gpt_base_cmp_ic_stat)
1186             CPPUNIT_TEST( EllenBinTree_rcu_gpt_base_cmp_ic_stat_yield )
1187             CPPUNIT_TEST( EllenBinTree_rcu_gpt_base_less_pool )
1188             CPPUNIT_TEST(EllenBinTree_rcu_gpt_base_less_pool_ic_stat)
1189
1190             CPPUNIT_TEST(EllenBinTree_rcu_gpt_member_less)
1191             CPPUNIT_TEST(EllenBinTree_rcu_gpt_member_cmp)
1192             CPPUNIT_TEST(EllenBinTree_rcu_gpt_member_less_stat)
1193             CPPUNIT_TEST(EllenBinTree_rcu_gpt_member_cmpless)
1194             CPPUNIT_TEST(EllenBinTree_rcu_gpt_member_less_ic)
1195             CPPUNIT_TEST(EllenBinTree_rcu_gpt_member_cmp_ic)
1196             CPPUNIT_TEST(EllenBinTree_rcu_gpt_member_cmp_ic_stat)
1197             CPPUNIT_TEST( EllenBinTree_rcu_gpt_member_cmp_ic_stat_yield )
1198             CPPUNIT_TEST( EllenBinTree_rcu_gpt_member_less_pool )
1199             CPPUNIT_TEST(EllenBinTree_rcu_gpt_member_less_pool_ic_stat)
1200
1201             CPPUNIT_TEST(EllenBinTree_rcu_shb_base_less)
1202             CPPUNIT_TEST(EllenBinTree_rcu_shb_base_cmp)
1203             CPPUNIT_TEST(EllenBinTree_rcu_shb_base_less_stat)
1204             CPPUNIT_TEST(EllenBinTree_rcu_shb_base_cmpless)
1205             CPPUNIT_TEST(EllenBinTree_rcu_shb_base_less_ic)
1206             CPPUNIT_TEST(EllenBinTree_rcu_shb_base_cmp_ic)
1207             CPPUNIT_TEST(EllenBinTree_rcu_shb_base_cmp_ic_stat)
1208             CPPUNIT_TEST( EllenBinTree_rcu_shb_base_cmp_ic_stat_yield )
1209             CPPUNIT_TEST( EllenBinTree_rcu_shb_base_less_pool )
1210             CPPUNIT_TEST(EllenBinTree_rcu_shb_base_less_pool_ic_stat)
1211
1212             CPPUNIT_TEST(EllenBinTree_rcu_shb_member_less)
1213             CPPUNIT_TEST(EllenBinTree_rcu_shb_member_cmp)
1214             CPPUNIT_TEST(EllenBinTree_rcu_shb_member_less_stat)
1215             CPPUNIT_TEST(EllenBinTree_rcu_shb_member_cmpless)
1216             CPPUNIT_TEST(EllenBinTree_rcu_shb_member_less_ic)
1217             CPPUNIT_TEST(EllenBinTree_rcu_shb_member_cmp_ic)
1218             CPPUNIT_TEST(EllenBinTree_rcu_shb_member_cmp_ic_stat)
1219             CPPUNIT_TEST( EllenBinTree_rcu_shb_member_cmp_ic_stat_yield )
1220             CPPUNIT_TEST( EllenBinTree_rcu_shb_member_less_pool )
1221             CPPUNIT_TEST(EllenBinTree_rcu_shb_member_less_pool_ic_stat)
1222
1223             CPPUNIT_TEST(EllenBinTree_rcu_sht_base_less)
1224             CPPUNIT_TEST(EllenBinTree_rcu_sht_base_cmp)
1225             CPPUNIT_TEST(EllenBinTree_rcu_sht_base_less_stat)
1226             CPPUNIT_TEST(EllenBinTree_rcu_sht_base_cmpless)
1227             CPPUNIT_TEST(EllenBinTree_rcu_sht_base_less_ic)
1228             CPPUNIT_TEST(EllenBinTree_rcu_sht_base_cmp_ic)
1229             CPPUNIT_TEST(EllenBinTree_rcu_sht_base_cmp_ic_stat)
1230             CPPUNIT_TEST( EllenBinTree_rcu_sht_base_cmp_ic_stat_yield )
1231             CPPUNIT_TEST( EllenBinTree_rcu_sht_base_less_pool )
1232             CPPUNIT_TEST(EllenBinTree_rcu_sht_base_less_pool_ic_stat)
1233
1234             CPPUNIT_TEST(EllenBinTree_rcu_sht_member_less)
1235             CPPUNIT_TEST(EllenBinTree_rcu_sht_member_cmp)
1236             CPPUNIT_TEST(EllenBinTree_rcu_sht_member_less_stat)
1237             CPPUNIT_TEST(EllenBinTree_rcu_sht_member_cmpless)
1238             CPPUNIT_TEST(EllenBinTree_rcu_sht_member_less_ic)
1239             CPPUNIT_TEST(EllenBinTree_rcu_sht_member_cmp_ic)
1240             CPPUNIT_TEST(EllenBinTree_rcu_sht_member_cmp_ic_stat)
1241             CPPUNIT_TEST( EllenBinTree_rcu_sht_member_cmp_ic_stat_yield )
1242             CPPUNIT_TEST( EllenBinTree_rcu_sht_member_less_pool )
1243             CPPUNIT_TEST(EllenBinTree_rcu_sht_member_less_pool_ic_stat)
1244
1245         CPPUNIT_TEST_SUITE_END()
1246     };
1247 } // namespace tree
1248
1249 #endif // #ifndef CDSHDRTEST_INTRUSIVE_BINTREE_H