Disables running some stat analysis for benchmarks & Adds some sequential data structures
[libcds.git] / test / stress / set / iter_erase / set_iter_erase.h
1 /*
2     This file is a part of libcds - Concurrent Data Structures library
3
4     (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2017
5
6     Source code repo: http://github.com/khizmax/libcds/
7     Download: http://sourceforge.net/projects/libcds/files/
8
9     Redistribution and use in source and binary forms, with or without
10     modification, are permitted provided that the following conditions are met:
11
12     * Redistributions of source code must retain the above copyright notice, this
13       list of conditions and the following disclaimer.
14
15     * Redistributions in binary form must reproduce the above copyright notice,
16       this list of conditions and the following disclaimer in the documentation
17       and/or other materials provided with the distribution.
18
19     THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
20     AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
21     IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
22     DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
23     FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
24     DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
25     SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
26     CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
27     OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
28     OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29 */
30
31 #include "set_type.h"
32 #include "../../misc/common.h"
33 #include <cds/os/topology.h>
34
35 namespace set {
36
37     struct key_thread
38     {
39         uint32_t  nKey;
40         uint16_t  nThread;
41
42         key_thread( size_t key, size_t threadNo )
43             : nKey( static_cast<uint32_t>(key))
44             , nThread( static_cast<uint16_t>(threadNo))
45         {}
46
47         key_thread()
48             : nKey()
49             , nThread()
50         {}
51     };
52
53     static_assert(sizeof( key_thread ) % 8 == 0, "Key type size mismatch");
54
55     typedef set_type_base<key_thread, size_t>::key_val     key_value_pair;
56
57     template <>
58     struct cmp<key_thread> {
59         int operator ()(key_thread const& k1, key_thread const& k2) const
60         {
61             if ( k1.nKey < k2.nKey )
62                 return -1;
63             if ( k1.nKey > k2.nKey )
64                 return 1;
65             if ( k1.nThread < k2.nThread )
66                 return -1;
67             if ( k1.nThread > k2.nThread )
68                 return 1;
69             return 0;
70         }
71         int operator ()(key_thread const& k1, size_t k2) const
72         {
73             if ( k1.nKey < k2 )
74                 return -1;
75             if ( k1.nKey > k2 )
76                 return 1;
77             return 0;
78         }
79         int operator ()(size_t k1, key_thread const& k2) const
80         {
81             if ( k1 < k2.nKey )
82                 return -1;
83             if ( k1 > k2.nKey )
84                 return 1;
85             return 0;
86         }
87     };
88
89     template <>
90     struct less<set::key_thread>
91     {
92         bool operator()( set::key_thread const& k1, set::key_thread const& k2 ) const
93         {
94             if ( k1.nKey <= k2.nKey )
95                 return k1.nKey < k2.nKey || k1.nThread < k2.nThread;
96             return false;
97         }
98     };
99
100     template <>
101     struct hash<set::key_thread>
102     {
103         typedef size_t             result_type;
104         typedef set::key_thread    argument_type;
105
106         size_t operator()( set::key_thread const& k ) const
107         {
108             return std::hash<size_t>()(k.nKey);
109         }
110
111         size_t operator()( size_t k ) const
112         {
113             return std::hash<size_t>()(k);
114         }
115     };
116
117
118     class Set_Iter_Del3: public cds_test::stress_fixture
119     {
120     public:
121         static size_t s_nSetSize;              // max set size
122         static size_t s_nInsThreadCount;       // insert thread count
123         static size_t s_nDelThreadCount;       // delete thread count
124         static size_t s_nExtractThreadCount;   // extract thread count
125         static size_t s_nMaxLoadFactor;        // maximum load factor
126         static size_t s_nInsertPassCount;
127         static size_t s_nFindThreadCount;      // find thread count
128
129         static size_t s_nFeldmanSet_HeadBits;
130         static size_t s_nFeldmanSet_ArrayBits;
131
132         static size_t s_nLoadFactor;
133
134         static std::vector<size_t> m_arrData;
135
136         static void SetUpTestCase();
137         static void TearDownTestCase();
138
139         template <typename Pred>
140         static void prepare_array( std::vector<size_t>& arr, Pred pred )
141         {
142             arr.reserve( m_arrData.size());
143             for ( auto el : m_arrData ) {
144                 if ( pred( el ))
145                     arr.push_back( el );
146             }
147             arr.resize( arr.size());
148             shuffle( arr.begin(), arr.end());
149         }
150
151     protected:
152         typedef key_thread  key_type;
153         typedef size_t      value_type;
154
155         atomics::atomic<size_t> m_nInsThreadCount;
156
157         enum {
158             inserter_thread,
159             deleter_thread,
160             extractor_thread,
161             find_thread
162         };
163
164
165         // Inserts keys from [0..N)
166         template <class Set>
167         class Inserter: public cds_test::thread
168         {
169             typedef cds_test::thread base_class;
170             Set&     m_Set;
171
172             struct update_functor
173             {
174                 template <typename Q>
175                 void operator()( bool /*bNew*/, key_value_pair const&, Q const& ) const
176                 {}
177
178                 void operator()(key_value_pair& /*cur*/, key_value_pair * /*prev*/) const
179                 {}
180             };
181
182             void init_data()
183             {
184                 prepare_array( m_arr, []( size_t ) -> bool { return true; } );
185                 for ( size_t i = 0; i < m_arr.size(); ++i ) {
186                     if ( m_Set.insert( key_type( m_arr[i], id())))
187                         ++m_nInsertInitSuccess;
188                     else
189                         ++m_nInsertInitFailed;
190                 }
191             }
192
193         public:
194             size_t  m_nInsertSuccess = 0;
195             size_t  m_nInsertFailed = 0;
196             size_t m_nInsertInitSuccess = 0;
197             size_t m_nInsertInitFailed = 0;
198
199             std::vector<size_t> m_arr;
200
201         public:
202             Inserter( cds_test::thread_pool& pool, Set& set )
203                 : base_class( pool, inserter_thread )
204                 , m_Set( set )
205             {
206                 init_data();
207             }
208
209             Inserter( Inserter& src )
210                 : base_class( src )
211                 , m_Set( src.m_Set )
212             {
213                 init_data();
214             }
215
216             virtual thread * clone()
217             {
218                 return new Inserter( *this );
219             }
220
221             virtual void test()
222             {
223                 Set& rSet = m_Set;
224                 Set_Iter_Del3& fixture = pool().template fixture<Set_Iter_Del3>();
225
226                 for ( size_t nPass = 0; nPass < s_nInsertPassCount; ++nPass ) {
227                     if ( nPass & 1 ) {
228                         // insert pass
229                         for ( auto el : m_arr ) {
230                             if ( el & 3 ) {
231                                 if ( rSet.insert( key_type( el, id())))
232                                     ++m_nInsertSuccess;
233                                 else
234                                     ++m_nInsertFailed;
235                             }
236                         }
237                     }
238                     else {
239                         // update pass
240                         for ( auto el : m_arr ) {
241                             if ( el & 3 ) {
242                                 bool success;
243                                 bool inserted;
244                                 std::tie( success, inserted ) = rSet.update( key_type( el, id()), update_functor());
245                                 if ( success && inserted )
246                                     ++m_nInsertSuccess;
247                                 else
248                                     ++m_nInsertFailed;
249                             }
250                         }
251                     }
252                 }
253
254                 fixture.m_nInsThreadCount.fetch_sub( 1, atomics::memory_order_release );
255                 m_arr.resize( 0 );
256             }
257         };
258
259         struct key_equal {
260             bool operator()( key_type const& k1, key_type const& k2 ) const
261             {
262                 return k1.nKey == k2.nKey;
263             }
264             bool operator()( size_t k1, key_type const& k2 ) const
265             {
266                 return k1 == k2.nKey;
267             }
268             bool operator()( key_type const& k1, size_t k2 ) const
269             {
270                 return k1.nKey == k2;
271             }
272             bool operator ()( key_value_pair const& k1, key_value_pair const& k2 ) const
273             {
274                 return operator()( k1.key, k2.key );
275             }
276             bool operator ()( key_value_pair const& k1, key_type const& k2 ) const
277             {
278                 return operator()( k1.key, k2 );
279             }
280             bool operator ()( key_type const& k1, key_value_pair const& k2 ) const
281             {
282                 return operator()( k1, k2.key );
283             }
284             bool operator ()( key_value_pair const& k1, size_t k2 ) const
285             {
286                 return operator()( k1.key, k2 );
287             }
288             bool operator ()( size_t k1, key_value_pair const& k2 ) const
289             {
290                 return operator()( k1, k2.key );
291             }
292         };
293
294         struct key_less {
295             bool operator()( key_type const& k1, key_type const& k2 ) const
296             {
297                 return k1.nKey < k2.nKey;
298             }
299             bool operator()( size_t k1, key_type const& k2 ) const
300             {
301                 return k1 < k2.nKey;
302             }
303             bool operator()( key_type const& k1, size_t k2 ) const
304             {
305                 return k1.nKey < k2;
306             }
307             bool operator ()( key_value_pair const& k1, key_value_pair const& k2 ) const
308             {
309                 return operator()( k1.key, k2.key );
310             }
311             bool operator ()( key_value_pair const& k1, key_type const& k2 ) const
312             {
313                 return operator()( k1.key, k2 );
314             }
315             bool operator ()( key_type const& k1, key_value_pair const& k2 ) const
316             {
317                 return operator()( k1, k2.key );
318             }
319             bool operator ()( key_value_pair const& k1, size_t k2 ) const
320             {
321                 return operator()( k1.key, k2 );
322             }
323             bool operator ()( size_t k1, key_value_pair const& k2 ) const
324             {
325                 return operator()( k1, k2.key );
326             }
327
328             typedef key_equal   equal_to;
329         };
330
331         // Deletes keys from [0..N)
332         template <class Set, typename Iterator>
333         class Deleter: public cds_test::thread
334         {
335             typedef cds_test::thread base_class;
336             Set&     m_Set;
337
338         public:
339             size_t  m_nDeleteSuccess = 0;
340             size_t  m_nDeleteFailed = 0;
341
342         public:
343             Deleter( cds_test::thread_pool& pool, Set& set )
344                 : base_class( pool, deleter_thread )
345                 , m_Set( set )
346             {}
347
348             Deleter( Deleter& src )
349                 : base_class( src )
350                 , m_Set( src.m_Set )
351             {}
352
353             virtual thread * clone()
354             {
355                 return new Deleter( *this );
356             }
357
358             virtual void test()
359             {
360                 Set& rSet = m_Set;
361
362                 Set_Iter_Del3& fixture = pool().template fixture<Set_Iter_Del3>();
363
364                 do {
365                     auto itEnd = rSet.template get_end<Iterator>();
366                     for ( auto it = rSet.template get_begin<Iterator>(); it != itEnd; ++it ) {
367                         if ( it->key.nKey & 3 ) {
368                             if ( rSet.erase_at( it ))
369                                 ++m_nDeleteSuccess;
370                             else
371                                 ++m_nDeleteFailed;
372                         }
373                     }
374                 } while ( fixture.m_nInsThreadCount.load( atomics::memory_order_acquire ) != 0 );
375             }
376         };
377
378         // Extracts keys from [0..N)
379         template <typename GC, class Set>
380         class Extractor: public cds_test::thread
381         {
382             typedef cds_test::thread base_class;
383             Set&     m_Set;
384
385             std::vector<size_t> m_arr;
386
387             void init_data()
388             {
389                 prepare_array( m_arr, []( size_t el ) ->bool { return ( el & 3 ) != 0; } );
390             }
391
392         public:
393             size_t  m_nExtractSuccess = 0;
394             size_t  m_nExtractFailed = 0;
395
396         public:
397             Extractor( cds_test::thread_pool& pool, Set& set )
398                 : base_class( pool, extractor_thread )
399                 , m_Set( set )
400             {
401                 init_data();
402             }
403
404             Extractor( Extractor& src )
405                 : base_class( src )
406                 , m_Set( src.m_Set )
407             {
408                 init_data();
409             }
410
411             virtual thread * clone()
412             {
413                 return new Extractor( *this );
414             }
415
416             virtual void test()
417             {
418                 Set& rSet = m_Set;
419                 typename Set::guarded_ptr gp;
420
421                 Set_Iter_Del3& fixture = pool().template fixture<Set_Iter_Del3>();
422                 size_t const nInsThreadCount = s_nInsThreadCount;
423
424                 do {
425                     if ( id() & 1 ) {
426                         for ( auto el : m_arr ) {
427                             for ( size_t k = 0; k < nInsThreadCount; ++k ) {
428                                 gp = rSet.extract( key_type( el, k ));
429                                 if ( gp )
430                                     ++m_nExtractSuccess;
431                                 else
432                                     ++m_nExtractFailed;
433                                 gp.release();
434                             }
435                         }
436                     }
437                     else {
438                         for ( size_t k = 0; k < nInsThreadCount; ++k ) {
439                             for ( auto el : m_arr ) {
440                                 gp = rSet.extract( key_type( el, k ));
441                                 if ( gp )
442                                     ++m_nExtractSuccess;
443                                 else
444                                     ++m_nExtractFailed;
445                                 gp.release();
446                             }
447                         }
448                     }
449                 } while ( fixture.m_nInsThreadCount.load( atomics::memory_order_acquire ) != 0 );
450
451                 m_arr.resize( 0 );
452             }
453         };
454
455         template <typename RCU, class Set>
456         class Extractor< cds::urcu::gc<RCU>, Set >: public cds_test::thread
457         {
458             typedef cds_test::thread base_class;
459             Set&     m_Set;
460             std::vector<size_t> m_arr;
461
462             void init_data()
463             {
464                 prepare_array( m_arr, []( size_t el ) -> bool { return ( el & 3 ) != 0; } );
465             }
466
467         public:
468             size_t  m_nExtractSuccess = 0;
469             size_t  m_nExtractFailed = 0;
470
471         public:
472             Extractor( cds_test::thread_pool& pool, Set& set )
473                 : base_class( pool, extractor_thread )
474                 , m_Set( set )
475             {
476                 init_data();
477             }
478
479             Extractor( Extractor& src )
480                 : base_class( src )
481                 , m_Set( src.m_Set )
482             {
483                 init_data();
484             }
485
486             virtual thread * clone()
487             {
488                 return new Extractor( *this );
489             }
490
491             virtual void test()
492             {
493                 Set& rSet = m_Set;
494                 typename Set::exempt_ptr xp;
495
496                 Set_Iter_Del3& fixture = pool().template fixture<Set_Iter_Del3>();
497                 size_t const nInsThreadCount = fixture.s_nInsThreadCount;
498
499                 do {
500                     if ( id() & 1 ) {
501                         for ( size_t k = 0; k < nInsThreadCount; ++k ) {
502                             for ( auto el : m_arr ) {
503                                 if ( Set::c_bExtractLockExternal ) {
504                                     typename Set::rcu_lock l;
505                                     xp = rSet.extract( key_type( el, k ));
506                                     if ( xp )
507                                         ++m_nExtractSuccess;
508                                     else
509                                         ++m_nExtractFailed;
510                                 }
511                                 else {
512                                     xp = rSet.extract( key_type( el, k ));
513                                     if ( xp )
514                                         ++m_nExtractSuccess;
515                                     else
516                                         ++m_nExtractFailed;
517                                 }
518                                 xp.release();
519                             }
520                         }
521                     }
522                     else {
523                         for ( auto el : m_arr ) {
524                             for ( size_t k = 0; k < nInsThreadCount; ++k ) {
525                                 if ( Set::c_bExtractLockExternal ) {
526                                     typename Set::rcu_lock l;
527                                     xp = rSet.extract( key_type( el, k ));
528                                     if ( xp )
529                                         ++m_nExtractSuccess;
530                                     else
531                                         ++m_nExtractFailed;
532                                 }
533                                 else {
534                                     xp = rSet.extract( key_type( el, k ));
535                                     if ( xp )
536                                         ++m_nExtractSuccess;
537                                     else
538                                         ++m_nExtractFailed;
539                                 }
540                                 xp.release();
541                             }
542                         }
543                     }
544                 } while ( fixture.m_nInsThreadCount.load( atomics::memory_order_acquire ) != 0 );
545
546                 m_arr.resize( 0 );
547             }
548         };
549
550         // Finds keys
551         template <class Set>
552         class Observer: public cds_test::thread
553         {
554             typedef cds_test::thread base_class;
555             Set&                m_Set;
556
557         public:
558             size_t m_nFindEvenSuccess = 0;
559             size_t m_nFindEvenFailed = 0;
560             size_t m_nFindOddSuccess = 0;
561             size_t m_nFindOddFailed = 0;
562
563         public:
564             Observer( cds_test::thread_pool& pool, Set& set )
565                 : base_class( pool, find_thread )
566                 , m_Set( set )
567             {}
568
569             Observer( Observer& src )
570                 : base_class( src )
571                 , m_Set( src.m_Set )
572             {}
573
574             virtual thread * clone()
575             {
576                 return new Observer( *this );
577             }
578
579             virtual void test()
580             {
581                 Set& set = m_Set;
582                 Set_Iter_Del3& fixture = pool().template fixture<Set_Iter_Del3>();
583                 std::vector<size_t> const& arr = m_arrData;
584                 size_t const nInsThreadCount = s_nInsThreadCount;
585
586                 do {
587                     for ( size_t key : arr ) {
588                         if ( key & 3 ) {
589                             for ( size_t k = 0; k < nInsThreadCount; ++k ) {
590                                 if ( set.contains( key_thread( key, k )))
591                                     ++m_nFindOddSuccess;
592                                 else
593                                     ++m_nFindOddFailed;
594                             }
595                         }
596                         else {
597                             // that keys MUST be in the map
598                             for ( size_t k = 0; k < nInsThreadCount; ++k ) {
599                                 if ( set.contains( key_thread( key, k )))
600                                     ++m_nFindEvenSuccess;
601                                 else
602                                     ++m_nFindEvenFailed;
603                             }
604                         }
605                     }
606                 } while ( fixture.m_nInsThreadCount.load( atomics::memory_order_acquire ) != 0 );
607             }
608         };
609
610     protected:
611         template <typename Iterator, class Set>
612         void do_test_with( Set& testSet )
613         {
614             typedef Inserter<Set> insert_thread;
615             typedef Deleter<Set, Iterator> delete_thread;
616             typedef Observer<Set> observer_thread;
617
618             m_nInsThreadCount.store( s_nInsThreadCount, atomics::memory_order_release );
619
620             cds_test::thread_pool& pool = get_pool();
621             pool.add( new insert_thread( pool, testSet ), s_nInsThreadCount );
622             pool.add( new delete_thread( pool, testSet ), s_nDelThreadCount ? s_nDelThreadCount : cds::OS::topology::processor_count());
623             if ( s_nFindThreadCount )
624                 pool.add( new observer_thread( pool, testSet ), s_nFindThreadCount );
625
626             propout() << std::make_pair( "insert_thread_count", s_nInsThreadCount )
627                 << std::make_pair( "delete_thread_count", s_nDelThreadCount )
628                 << std::make_pair( "find_thread_count", s_nFindThreadCount )
629                 << std::make_pair( "set_size", s_nSetSize )
630                 << std::make_pair( "pass_count", s_nInsertPassCount );
631
632             std::chrono::milliseconds duration = pool.run();
633
634             propout() << std::make_pair( "duration", duration );
635
636             size_t nInsertInitFailed = 0;
637             size_t nInsertInitSuccess = 0;
638             size_t nInsertSuccess = 0;
639             size_t nInsertFailed = 0;
640             size_t nDeleteSuccess = 0;
641             size_t nDeleteFailed = 0;
642
643             size_t nFindEvenSuccess = 0;
644             size_t nFindEvenFailed = 0;
645             size_t nFindOddSuccess = 0;
646             size_t nFindOddFailed = 0;
647
648             for ( size_t i = 0; i < pool.size(); ++i ) {
649                 cds_test::thread& thr = pool.get( i );
650                 switch ( thr.type()) {
651                 case inserter_thread:
652                     {
653                         insert_thread& inserter = static_cast<insert_thread&>(thr);
654                         nInsertSuccess += inserter.m_nInsertSuccess;
655                         nInsertFailed += inserter.m_nInsertFailed;
656                         nInsertInitSuccess += inserter.m_nInsertInitSuccess;
657                         nInsertInitFailed += inserter.m_nInsertInitFailed;
658                     }
659                     break;
660                 case deleter_thread:
661                     {
662                         delete_thread& deleter = static_cast<delete_thread&>(thr);
663                         nDeleteSuccess += deleter.m_nDeleteSuccess;
664                         nDeleteFailed += deleter.m_nDeleteFailed;
665                     }
666                     break;
667                 case find_thread:
668                     {
669                         observer_thread& observer = static_cast<observer_thread&>( thr );
670                         nFindEvenSuccess = observer.m_nFindEvenSuccess;
671                         nFindEvenFailed = observer.m_nFindEvenFailed;
672                         nFindOddSuccess = observer.m_nFindOddSuccess;
673                         nFindOddFailed = observer.m_nFindOddFailed;
674                     }
675                     break;
676                 default:
677                     assert( false );
678                 }
679             }
680
681             size_t const nInitialOddKeys = ( s_nSetSize * s_nInsThreadCount ) * 3 / 4;
682
683             EXPECT_EQ( nInsertInitFailed, 0u );
684             EXPECT_EQ( nInsertInitSuccess, s_nSetSize * s_nInsThreadCount );
685             EXPECT_EQ( nFindEvenFailed, 0u );
686             EXPECT_GE( nInsertSuccess + nInitialOddKeys, nDeleteSuccess );
687             EXPECT_LE( nInsertSuccess, nDeleteSuccess );
688
689             propout()
690                 << std::make_pair( "insert_init_success", nInsertInitSuccess )
691                 << std::make_pair( "insert_init_failed", nInsertInitFailed )
692                 << std::make_pair( "insert_success", nInsertSuccess )
693                 << std::make_pair( "insert_failed", nInsertFailed )
694                 << std::make_pair( "delete_success", nDeleteSuccess )
695                 << std::make_pair( "delete_failed", nDeleteFailed )
696                 << std::make_pair( "find_even_success", nFindEvenSuccess )
697                 << std::make_pair( "find_even_failed", nFindEvenFailed )
698                 << std::make_pair( "find_odd_success", nFindOddSuccess )
699                 << std::make_pair( "find_odd_failed", nFindOddFailed );
700         }
701
702         template <typename Iterator, class Set>
703         void do_test_extract_with( Set& testSet )
704         {
705             typedef Inserter<Set> insert_thread;
706             typedef Deleter<Set, Iterator> delete_thread;
707             typedef Extractor< typename Set::gc, Set > extract_thread;
708             typedef Observer<Set> observer_thread;
709
710             m_nInsThreadCount.store( s_nInsThreadCount, atomics::memory_order_release );
711
712             cds_test::thread_pool& pool = get_pool();
713             pool.add( new insert_thread( pool, testSet ), s_nInsThreadCount );
714             if ( s_nDelThreadCount )
715                 pool.add( new delete_thread( pool, testSet ), s_nDelThreadCount );
716             if ( s_nExtractThreadCount )
717                 pool.add( new extract_thread( pool, testSet ), s_nExtractThreadCount );
718             if ( s_nFindThreadCount )
719                 pool.add( new observer_thread( pool, testSet ), s_nFindThreadCount );
720
721             propout() << std::make_pair( "insert_thread_count", s_nInsThreadCount )
722                 << std::make_pair( "delete_thread_count", s_nDelThreadCount )
723                 << std::make_pair( "extract_thread_count", s_nExtractThreadCount )
724                 << std::make_pair( "find_thread_count", s_nFindThreadCount )
725                 << std::make_pair( "set_size", s_nSetSize )
726                 << std::make_pair( "pass_count", s_nInsertPassCount );
727
728             std::chrono::milliseconds duration = pool.run();
729
730             propout() << std::make_pair( "duration", duration );
731
732             size_t nInsertInitFailed = 0;
733             size_t nInsertInitSuccess = 0;
734             size_t nInsertSuccess = 0;
735             size_t nInsertFailed = 0;
736             size_t nDeleteSuccess = 0;
737             size_t nDeleteFailed = 0;
738             size_t nExtractSuccess = 0;
739             size_t nExtractFailed = 0;
740
741             size_t nFindEvenSuccess = 0;
742             size_t nFindEvenFailed = 0;
743             size_t nFindOddSuccess = 0;
744             size_t nFindOddFailed = 0;
745
746             for ( size_t i = 0; i < pool.size(); ++i ) {
747                 cds_test::thread& thr = pool.get( i );
748                 switch ( thr.type()) {
749                 case inserter_thread:
750                     {
751                         insert_thread& inserter = static_cast<insert_thread&>( thr );
752                         nInsertSuccess += inserter.m_nInsertSuccess;
753                         nInsertFailed += inserter.m_nInsertFailed;
754                         nInsertInitSuccess += inserter.m_nInsertInitSuccess;
755                         nInsertInitFailed += inserter.m_nInsertInitFailed;
756                     }
757                     break;
758                 case deleter_thread:
759                     {
760                         delete_thread& deleter = static_cast<delete_thread&>(thr);
761                         nDeleteSuccess += deleter.m_nDeleteSuccess;
762                         nDeleteFailed += deleter.m_nDeleteFailed;
763                     }
764                     break;
765                 case extractor_thread:
766                     {
767                         extract_thread& extractor = static_cast<extract_thread&>(thr);
768                         nExtractSuccess += extractor.m_nExtractSuccess;
769                         nExtractFailed += extractor.m_nExtractFailed;
770                     }
771                     break;
772                 case find_thread:
773                     {
774                         observer_thread& observer = static_cast<observer_thread&>( thr );
775                         nFindEvenSuccess = observer.m_nFindEvenSuccess;
776                         nFindEvenFailed = observer.m_nFindEvenFailed;
777                         nFindOddSuccess = observer.m_nFindOddSuccess;
778                         nFindOddFailed = observer.m_nFindOddFailed;
779                     }
780                     break;
781                 default:
782                     assert( false );
783                 }
784             }
785
786             size_t const nInitialOddKeys = ( s_nSetSize * s_nInsThreadCount ) * 3 / 4;
787
788             EXPECT_EQ( nInsertInitFailed, 0u );
789             EXPECT_EQ( nInsertInitSuccess, s_nSetSize * s_nInsThreadCount );
790             EXPECT_EQ( nFindEvenFailed, 0u );
791             EXPECT_GE( nInsertSuccess + nInitialOddKeys, nDeleteSuccess + nExtractSuccess );
792             EXPECT_LE( nInsertSuccess, nDeleteSuccess + nExtractSuccess );
793
794             propout()
795                 << std::make_pair( "insert_init_success", nInsertInitSuccess )
796                 << std::make_pair( "insert_init_failed", nInsertInitFailed )
797                 << std::make_pair( "insert_success", nInsertSuccess )
798                 << std::make_pair( "insert_failed", nInsertFailed )
799                 << std::make_pair( "delete_success", nDeleteSuccess )
800                 << std::make_pair( "delete_failed", nDeleteFailed )
801                 << std::make_pair( "extract_success", nExtractSuccess )
802                 << std::make_pair( "extract_failed", nExtractFailed )
803                 << std::make_pair( "find_even_success", nFindEvenSuccess )
804                 << std::make_pair( "find_even_failed", nFindEvenFailed )
805                 << std::make_pair( "find_odd_success", nFindOddSuccess )
806                 << std::make_pair( "find_odd_failed", nFindOddFailed );
807         }
808
809         template <typename Set>
810         void analyze( Set& testSet )
811         {
812             // All even keys must be in the set
813             {
814                 for ( size_t n = 0; n < s_nSetSize; n +=4 ) {
815                     for ( size_t i = 0; i < s_nInsThreadCount; ++i ) {
816                         EXPECT_TRUE( testSet.contains( key_type( n, i ))) << "key=" << n << "/" << i;
817                     }
818                 }
819             }
820
821             check_before_clear( testSet );
822
823             testSet.clear();
824             EXPECT_TRUE( testSet.empty()) << "set.size=" << testSet.size();
825
826             additional_check( testSet );
827             print_stat( propout(), testSet );
828             additional_cleanup( testSet );
829         }
830
831         template <class Set, typename Iterator=typename Set::iterator>
832         void run_test()
833         {
834             static_assert( !Set::c_bExtractSupported, "Set class must not support extract() method" );
835
836             Set  testSet( *this );
837             do_test_with<Iterator>( testSet );
838             DEBUG(analyze( testSet ));
839         }
840
841         template <class Set, typename Iterator=typename Set::iterator>
842         void run_test_extract()
843         {
844             static_assert( Set::c_bExtractSupported, "Set class must support extract() method" );
845
846             Set  testSet( *this );
847             do_test_extract_with<Iterator>( testSet );
848             DEBUG(analyze( testSet ));
849         }
850
851         template <class Set>
852         void run_feldman();
853     };
854
855     class Set_Iter_Del3_reverse: public Set_Iter_Del3
856     {
857     public:
858         template <class Set>
859         void run_feldman();
860     };
861
862
863     class Set_Iter_Del3_LF: public Set_Iter_Del3
864         , public ::testing::WithParamInterface<size_t>
865     {
866     public:
867         template <class Set>
868         void run_test()
869         {
870             s_nLoadFactor = GetParam();
871             propout() << std::make_pair( "load_factor", s_nLoadFactor );
872             Set_Iter_Del3::run_test<Set>();
873         }
874
875         template <class Set>
876         void run_test_extract()
877         {
878             s_nLoadFactor = GetParam();
879             propout() << std::make_pair( "load_factor", s_nLoadFactor );
880             Set_Iter_Del3::run_test_extract<Set>();
881         }
882
883         static std::vector<size_t> get_load_factors();
884     };
885
886 } // namespace set