f53fb3d8c7b9f8b85533df7b13c6c34b3d20edaf
[libcds.git] / test / stress / set / del3 / set_del3.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_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_nCuckooInitialSize;    // initial size for CuckooSet
130         static size_t s_nCuckooProbesetSize;   // CuckooSet probeset size (only for list-based probeset)
131         static size_t s_nCuckooProbesetThreshold; // CUckooSet probeset threshold (0 - use default)
132
133         static size_t s_nFeldmanSet_HeadBits;
134         static size_t s_nFeldmanSet_ArrayBits;
135
136         static size_t s_nLoadFactor;
137
138         static std::vector<size_t> m_arrData;
139
140         static void SetUpTestCase();
141         static void TearDownTestCase();
142
143         template <typename Pred>
144         static void prepare_array( std::vector<size_t>& arr, Pred pred )
145         {
146             arr.reserve( m_arrData.size());
147             for ( auto el : m_arrData ) {
148                 if ( pred( el ))
149                     arr.push_back( el );
150             }
151             arr.resize( arr.size());
152             shuffle( arr.begin(), arr.end());
153         }
154
155     protected:
156         typedef key_thread  key_type;
157         typedef size_t      value_type;
158
159         atomics::atomic<size_t> m_nInsThreadCount;
160
161         enum {
162             inserter_thread,
163             deleter_thread,
164             extractor_thread,
165             find_thread
166         };
167
168
169         // Inserts keys from [0..N)
170         template <class Set>
171         class Inserter: public cds_test::thread
172         {
173             typedef cds_test::thread base_class;
174             Set&     m_Set;
175
176             struct update_functor
177             {
178                 template <typename Q>
179                 void operator()( bool /*bNew*/, key_value_pair const&, Q const& ) const
180                 {}
181
182                 void operator()(key_value_pair& /*cur*/, key_value_pair * /*prev*/) const
183                 {}
184             };
185
186             void init_data()
187             {
188                 prepare_array( m_arr, []( size_t ) -> bool { return true; } );
189                 for ( size_t i = 0; i < m_arr.size(); ++i ) {
190                     if ( m_Set.insert( key_type( m_arr[i], id())))
191                         ++m_nInsertInitSuccess;
192                     else
193                         ++m_nInsertInitFailed;
194                 }
195             }
196
197         public:
198             size_t  m_nInsertSuccess = 0;
199             size_t  m_nInsertFailed = 0;
200             size_t m_nInsertInitSuccess = 0;
201             size_t m_nInsertInitFailed = 0;
202
203             std::vector<size_t> m_arr;
204
205         public:
206             Inserter( cds_test::thread_pool& pool, Set& set )
207                 : base_class( pool, inserter_thread )
208                 , m_Set( set )
209             {
210                 init_data();
211             }
212
213             Inserter( Inserter& src )
214                 : base_class( src )
215                 , m_Set( src.m_Set )
216             {
217                 init_data();
218             }
219
220             virtual thread * clone()
221             {
222                 return new Inserter( *this );
223             }
224
225             virtual void test()
226             {
227                 Set& rSet = m_Set;
228                 Set_Del3& fixture = pool().template fixture<Set_Del3>();
229
230                 for ( size_t nPass = 0; nPass < s_nInsertPassCount; ++nPass ) {
231                     if ( nPass & 1 ) {
232                         // insert pass
233                         for ( auto el : m_arr ) {
234                             if ( el & 3 ) {
235                                 if ( rSet.insert( key_type( el, id())))
236                                     ++m_nInsertSuccess;
237                                 else
238                                     ++m_nInsertFailed;
239                             }
240                         }
241                     }
242                     else {
243                         // update pass
244                         for ( auto el : m_arr ) {
245                             if ( el & 3 ) {
246                                 bool success;
247                                 bool inserted;
248                                 std::tie( success, inserted ) = rSet.update( key_type( el, id()), update_functor());
249                                 if ( success && inserted )
250                                     ++m_nInsertSuccess;
251                                 else
252                                     ++m_nInsertFailed;
253                             }
254                         }
255                     }
256                 }
257
258                 fixture.m_nInsThreadCount.fetch_sub( 1, atomics::memory_order_release );
259                 m_arr.resize( 0 );
260             }
261         };
262
263         struct key_equal {
264             bool operator()( key_type const& k1, key_type const& k2 ) const
265             {
266                 return k1.nKey == k2.nKey;
267             }
268             bool operator()( size_t k1, key_type const& k2 ) const
269             {
270                 return k1 == k2.nKey;
271             }
272             bool operator()( key_type const& k1, size_t k2 ) const
273             {
274                 return k1.nKey == k2;
275             }
276             bool operator ()( key_value_pair const& k1, key_value_pair const& k2 ) const
277             {
278                 return operator()( k1.key, k2.key );
279             }
280             bool operator ()( key_value_pair const& k1, key_type const& k2 ) const
281             {
282                 return operator()( k1.key, k2 );
283             }
284             bool operator ()( key_type const& k1, key_value_pair const& k2 ) const
285             {
286                 return operator()( k1, k2.key );
287             }
288             bool operator ()( key_value_pair const& k1, size_t k2 ) const
289             {
290                 return operator()( k1.key, k2 );
291             }
292             bool operator ()( size_t k1, key_value_pair const& k2 ) const
293             {
294                 return operator()( k1, k2.key );
295             }
296         };
297
298         struct key_less {
299             bool operator()( key_type const& k1, key_type const& k2 ) const
300             {
301                 return k1.nKey < k2.nKey;
302             }
303             bool operator()( size_t k1, key_type const& k2 ) const
304             {
305                 return k1 < k2.nKey;
306             }
307             bool operator()( key_type const& k1, size_t k2 ) const
308             {
309                 return k1.nKey < k2;
310             }
311             bool operator ()( key_value_pair const& k1, key_value_pair const& k2 ) const
312             {
313                 return operator()( k1.key, k2.key );
314             }
315             bool operator ()( key_value_pair const& k1, key_type const& k2 ) const
316             {
317                 return operator()( k1.key, k2 );
318             }
319             bool operator ()( key_type const& k1, key_value_pair const& k2 ) const
320             {
321                 return operator()( k1, k2.key );
322             }
323             bool operator ()( key_value_pair const& k1, size_t k2 ) const
324             {
325                 return operator()( k1.key, k2 );
326             }
327             bool operator ()( size_t k1, key_value_pair const& k2 ) const
328             {
329                 return operator()( k1, k2.key );
330             }
331
332             typedef key_equal   equal_to;
333         };
334
335         // Deletes odd keys from [0..N)
336         template <class Set>
337         class Deleter: public cds_test::thread
338         {
339             typedef cds_test::thread base_class;
340             Set&     m_Set;
341
342             void init_data()
343             {
344                 prepare_array( m_arr, []( size_t el ) ->bool { return ( el & 3 ) != 0; } );
345             }
346
347         public:
348             size_t  m_nDeleteSuccess = 0;
349             size_t  m_nDeleteFailed = 0;
350
351             std::vector<size_t> m_arr;
352
353         public:
354             Deleter( cds_test::thread_pool& pool, Set& set )
355                 : base_class( pool, deleter_thread )
356                 , m_Set( set )
357             {
358                 init_data();
359             }
360             Deleter( Deleter& src )
361                 : base_class( src )
362                 , m_Set( src.m_Set )
363             {
364                 init_data();
365             }
366
367             virtual thread * clone()
368             {
369                 return new Deleter( *this );
370             }
371
372             template <typename SetType, bool>
373             struct eraser {
374                 static bool erase( SetType& s, size_t key, size_t /*thread*/)
375                 {
376                     return s.erase_with( key, key_less());
377                 }
378             };
379
380             template <typename SetType>
381             struct eraser<SetType, true> {
382                 static bool erase(SetType& s, size_t key, size_t thread)
383                 {
384                     return s.erase( key_type(key, thread));
385                 }
386             };
387
388             virtual void test()
389             {
390                 Set& rSet = m_Set;
391
392                 size_t const nInsThreadCount = s_nInsThreadCount;
393                 Set_Del3& fixture = pool().template fixture<Set_Del3>();
394
395                 do {
396                     if ( id() & 1 ) {
397                         for ( auto el : m_arr ) {
398                             for ( size_t k = 0; k < nInsThreadCount; ++k ) {
399                                 if ( rSet.erase( key_type( el, k )))
400                                     ++m_nDeleteSuccess;
401                                 else
402                                     ++m_nDeleteFailed;
403                             }
404                         }
405                     }
406                     else {
407                         for ( size_t k = 0; k < nInsThreadCount; ++k ) {
408                             for ( auto el : m_arr ) {
409                                 if ( rSet.erase( key_type( el, k )))
410                                     ++m_nDeleteSuccess;
411                                 else
412                                     ++m_nDeleteFailed;
413                             }
414                         }
415                     }
416                 } while ( fixture.m_nInsThreadCount.load( atomics::memory_order_acquire ) != 0 );
417
418                 m_arr.resize( 0 );
419             }
420         };
421
422         // Extracts odd keys from [0..N)
423         template <typename GC, class Set>
424         class Extractor: public cds_test::thread
425         {
426             typedef cds_test::thread base_class;
427             Set&     m_Set;
428
429             std::vector<size_t> m_arr;
430
431             void init_data()
432             {
433                 prepare_array( m_arr, []( size_t el ) ->bool { return ( el & 3 ) != 0; } );
434             }
435
436         public:
437             size_t  m_nExtractSuccess = 0;
438             size_t  m_nExtractFailed = 0;
439
440         public:
441             Extractor( cds_test::thread_pool& pool, Set& set )
442                 : base_class( pool, extractor_thread )
443                 , m_Set( set )
444             {
445                 init_data();
446             }
447
448             Extractor( Extractor& src )
449                 : base_class( src )
450                 , m_Set( src.m_Set )
451             {
452                 init_data();
453             }
454
455             virtual thread * clone()
456             {
457                 return new Extractor( *this );
458             }
459
460             virtual void test()
461             {
462                 Set& rSet = m_Set;
463                 typename Set::guarded_ptr gp;
464
465                 Set_Del3& fixture = pool().template fixture<Set_Del3>();
466                 size_t const nInsThreadCount = s_nInsThreadCount;
467
468                 do {
469                     if ( id() & 1 ) {
470                         for ( auto el : m_arr ) {
471                             for ( size_t k = 0; k < nInsThreadCount; ++k ) {
472                                 gp = rSet.extract( key_type( el, k ));
473                                 if ( gp )
474                                     ++m_nExtractSuccess;
475                                 else
476                                     ++m_nExtractFailed;
477                                 gp.release();
478                             }
479                         }
480                     }
481                     else {
482                         for ( size_t k = 0; k < nInsThreadCount; ++k ) {
483                             for ( auto el : m_arr ) {
484                                 gp = rSet.extract( key_type( el, k ));
485                                 if ( gp )
486                                     ++m_nExtractSuccess;
487                                 else
488                                     ++m_nExtractFailed;
489                                 gp.release();
490                             }
491                         }
492                     }
493                 } while ( fixture.m_nInsThreadCount.load( atomics::memory_order_acquire ) != 0 );
494
495                 m_arr.resize( 0 );
496             }
497         };
498
499         template <typename RCU, class Set>
500         class Extractor< cds::urcu::gc<RCU>, Set >: public cds_test::thread
501         {
502             typedef cds_test::thread base_class;
503             Set&     m_Set;
504             std::vector<size_t> m_arr;
505
506             void init_data()
507             {
508                 prepare_array( m_arr, []( size_t el ) -> bool { return ( el & 3 ) != 0; } );
509             }
510
511         public:
512             size_t  m_nExtractSuccess = 0;
513             size_t  m_nExtractFailed = 0;
514
515         public:
516             Extractor( cds_test::thread_pool& pool, Set& set )
517                 : base_class( pool, extractor_thread )
518                 , m_Set( set )
519             {
520                 init_data();
521             }
522
523             Extractor( Extractor& src )
524                 : base_class( src )
525                 , m_Set( src.m_Set )
526             {
527                 init_data();
528             }
529
530             virtual thread * clone()
531             {
532                 return new Extractor( *this );
533             }
534
535             virtual void test()
536             {
537                 Set& rSet = m_Set;
538                 typename Set::exempt_ptr xp;
539
540                 Set_Del3& fixture = pool().template fixture<Set_Del3>();
541                 size_t const nInsThreadCount = fixture.s_nInsThreadCount;
542
543                 do {
544                     if ( id() & 1 ) {
545                         for ( size_t k = 0; k < nInsThreadCount; ++k ) {
546                             for ( auto el : m_arr ) {
547                                 if ( Set::c_bExtractLockExternal ) {
548                                     typename Set::rcu_lock l;
549                                     xp = rSet.extract( key_type( el, k ));
550                                     if ( xp )
551                                         ++m_nExtractSuccess;
552                                     else
553                                         ++m_nExtractFailed;
554                                 }
555                                 else {
556                                     xp = rSet.extract( key_type( el, k ));
557                                     if ( xp )
558                                         ++m_nExtractSuccess;
559                                     else
560                                         ++m_nExtractFailed;
561                                 }
562                                 xp.release();
563                             }
564                         }
565                     }
566                     else {
567                         for ( auto el : m_arr ) {
568                             for ( size_t k = 0; k < nInsThreadCount; ++k ) {
569                                 if ( Set::c_bExtractLockExternal ) {
570                                     typename Set::rcu_lock l;
571                                     xp = rSet.extract( key_type( el, k ));
572                                     if ( xp )
573                                         ++m_nExtractSuccess;
574                                     else
575                                         ++m_nExtractFailed;
576                                 }
577                                 else {
578                                     xp = rSet.extract( key_type( el, k ));
579                                     if ( xp )
580                                         ++m_nExtractSuccess;
581                                     else
582                                         ++m_nExtractFailed;
583                                 }
584                                 xp.release();
585                             }
586                         }
587                     }
588                 } while ( fixture.m_nInsThreadCount.load( atomics::memory_order_acquire ) != 0 );
589
590                 m_arr.resize( 0 );
591             }
592         };
593
594         // Finds keys
595         template <class Set>
596         class Observer: public cds_test::thread
597         {
598             typedef cds_test::thread base_class;
599             Set&                m_Set;
600
601         public:
602             size_t m_nFindEvenSuccess = 0;
603             size_t m_nFindEvenFailed = 0;
604             size_t m_nFindOddSuccess = 0;
605             size_t m_nFindOddFailed = 0;
606
607         public:
608             Observer( cds_test::thread_pool& pool, Set& set )
609                 : base_class( pool, find_thread )
610                 , m_Set( set )
611             {}
612
613             Observer( Observer& src )
614                 : base_class( src )
615                 , m_Set( src.m_Set )
616             {}
617
618             virtual thread * clone()
619             {
620                 return new Observer( *this );
621             }
622
623             virtual void test()
624             {
625                 Set& set = m_Set;
626                 Set_Del3& fixture = pool().template fixture<Set_Del3>();
627                 std::vector<size_t> const& arr = m_arrData;
628                 size_t const nInsThreadCount = s_nInsThreadCount;
629
630                 do {
631                     for ( size_t key : arr ) {
632                         if ( key & 3 ) {
633                             for ( size_t k = 0; k < nInsThreadCount; ++k ) {
634                                 if ( set.contains( key_thread( key, k )))
635                                     ++m_nFindOddSuccess;
636                                 else
637                                     ++m_nFindOddFailed;
638                             }
639                         }
640                         else {
641                             // even keys MUST be in the map
642                             for ( size_t k = 0; k < nInsThreadCount; ++k ) {
643                                 if ( set.contains( key_thread( key, k )))
644                                     ++m_nFindEvenSuccess;
645                                 else
646                                     ++m_nFindEvenFailed;
647                             }
648                         }
649                     }
650                 } while ( fixture.m_nInsThreadCount.load( atomics::memory_order_acquire ) != 0 );
651             }
652         };
653
654     protected:
655         template <class Set>
656         void do_test_with( Set& testSet )
657         {
658             typedef Inserter<Set> insert_thread;
659             typedef Deleter<Set> delete_thread;
660             typedef Observer<Set> observer_thread;
661
662             m_nInsThreadCount.store( s_nInsThreadCount, atomics::memory_order_release );
663
664             cds_test::thread_pool& pool = get_pool();
665             pool.add( new insert_thread( pool, testSet ), s_nInsThreadCount );
666             pool.add( new delete_thread( pool, testSet ), s_nDelThreadCount ? s_nDelThreadCount : cds::OS::topology::processor_count());
667             if ( s_nFindThreadCount )
668                 pool.add( new observer_thread( pool, testSet ), s_nFindThreadCount );
669
670             propout() << std::make_pair( "insert_thread_count", s_nInsThreadCount )
671                 << std::make_pair( "delete_thread_count", s_nDelThreadCount )
672                 << std::make_pair( "find_thread_count", s_nFindThreadCount )
673                 << std::make_pair( "set_size", s_nSetSize )
674                 << std::make_pair( "pass_count", s_nInsertPassCount );
675
676             std::chrono::milliseconds duration = pool.run();
677
678             propout() << std::make_pair( "duration", duration );
679
680             size_t nInsertInitFailed = 0;
681             size_t nInsertInitSuccess = 0;
682             size_t nInsertSuccess = 0;
683             size_t nInsertFailed = 0;
684             size_t nDeleteSuccess = 0;
685             size_t nDeleteFailed = 0;
686
687             size_t nFindEvenSuccess = 0;
688             size_t nFindEvenFailed = 0;
689             size_t nFindOddSuccess = 0;
690             size_t nFindOddFailed = 0;
691
692             for ( size_t i = 0; i < pool.size(); ++i ) {
693                 cds_test::thread& thr = pool.get( i );
694                 switch ( thr.type()) {
695                 case inserter_thread:
696                     {
697                         insert_thread& inserter = static_cast<insert_thread&>(thr);
698                         nInsertSuccess += inserter.m_nInsertSuccess;
699                         nInsertFailed += inserter.m_nInsertFailed;
700                         nInsertInitSuccess += inserter.m_nInsertInitSuccess;
701                         nInsertInitFailed += inserter.m_nInsertInitFailed;
702                     }
703                     break;
704                 case deleter_thread:
705                     {
706                         delete_thread& deleter = static_cast<delete_thread&>(thr);
707                         nDeleteSuccess += deleter.m_nDeleteSuccess;
708                         nDeleteFailed += deleter.m_nDeleteFailed;
709                     }
710                     break;
711                 case find_thread:
712                     {
713                         observer_thread& observer = static_cast<observer_thread&>( thr );
714                         nFindEvenSuccess = observer.m_nFindEvenSuccess;
715                         nFindEvenFailed = observer.m_nFindEvenFailed;
716                         nFindOddSuccess = observer.m_nFindOddSuccess;
717                         nFindOddFailed = observer.m_nFindOddFailed;
718                     }
719                     break;
720                 default:
721                     assert( false );
722                 }
723             }
724
725             size_t const nInitialOddKeys = ( s_nSetSize * s_nInsThreadCount ) * 3 / 4;
726
727             EXPECT_EQ( nInsertInitFailed, 0u );
728             EXPECT_EQ( nInsertInitSuccess, s_nSetSize * s_nInsThreadCount );
729             EXPECT_EQ( nFindEvenFailed, 0u );
730             EXPECT_GE( nInsertSuccess + nInitialOddKeys, nDeleteSuccess );
731             EXPECT_LE( nInsertSuccess, nDeleteSuccess );
732
733             propout()
734                 << std::make_pair( "insert_init_success", nInsertInitSuccess )
735                 << std::make_pair( "insert_init_failed", nInsertInitFailed )
736                 << std::make_pair( "insert_success", nInsertSuccess )
737                 << std::make_pair( "insert_failed", nInsertFailed )
738                 << std::make_pair( "delete_success", nDeleteSuccess )
739                 << std::make_pair( "delete_failed", nDeleteFailed )
740                 << std::make_pair( "find_even_success", nFindEvenSuccess )
741                 << std::make_pair( "find_even_failed", nFindEvenFailed )
742                 << std::make_pair( "find_odd_success", nFindOddSuccess )
743                 << std::make_pair( "find_odd_failed", nFindOddFailed );
744         }
745
746         template <class Set>
747         void do_test_extract_with( Set& testSet )
748         {
749             typedef Inserter<Set> insert_thread;
750             typedef Deleter<Set> delete_thread;
751             typedef Extractor< typename Set::gc, Set > extract_thread;
752             typedef Observer<Set> observer_thread;
753
754             m_nInsThreadCount.store( s_nInsThreadCount, atomics::memory_order_release );
755
756             cds_test::thread_pool& pool = get_pool();
757             pool.add( new insert_thread( pool, testSet ), s_nInsThreadCount );
758             if ( s_nDelThreadCount )
759                 pool.add( new delete_thread( pool, testSet ), s_nDelThreadCount );
760             if ( s_nExtractThreadCount )
761                 pool.add( new extract_thread( pool, testSet ), s_nExtractThreadCount );
762             if ( s_nFindThreadCount )
763                 pool.add( new observer_thread( pool, testSet ), s_nFindThreadCount );
764
765             propout() << std::make_pair( "insert_thread_count", s_nInsThreadCount )
766                 << std::make_pair( "delete_thread_count", s_nDelThreadCount )
767                 << std::make_pair( "extract_thread_count", s_nExtractThreadCount )
768                 << std::make_pair( "find_thread_count", s_nFindThreadCount )
769                 << std::make_pair( "set_size", s_nSetSize )
770                 << std::make_pair( "pass_count", s_nInsertPassCount );
771
772             std::chrono::milliseconds duration = pool.run();
773
774             propout() << std::make_pair( "duration", duration );
775
776             size_t nInsertInitFailed = 0;
777             size_t nInsertInitSuccess = 0;
778             size_t nInsertSuccess = 0;
779             size_t nInsertFailed = 0;
780             size_t nDeleteSuccess = 0;
781             size_t nDeleteFailed = 0;
782             size_t nExtractSuccess = 0;
783             size_t nExtractFailed = 0;
784
785             size_t nFindEvenSuccess = 0;
786             size_t nFindEvenFailed = 0;
787             size_t nFindOddSuccess = 0;
788             size_t nFindOddFailed = 0;
789
790             for ( size_t i = 0; i < pool.size(); ++i ) {
791                 cds_test::thread& thr = pool.get( i );
792                 switch ( thr.type()) {
793                 case inserter_thread:
794                     {
795                         insert_thread& inserter = static_cast<insert_thread&>( thr );
796                         nInsertSuccess += inserter.m_nInsertSuccess;
797                         nInsertFailed += inserter.m_nInsertFailed;
798                         nInsertInitSuccess += inserter.m_nInsertInitSuccess;
799                         nInsertInitFailed += inserter.m_nInsertInitFailed;
800                     }
801                     break;
802                 case deleter_thread:
803                     {
804                         delete_thread& deleter = static_cast<delete_thread&>(thr);
805                         nDeleteSuccess += deleter.m_nDeleteSuccess;
806                         nDeleteFailed += deleter.m_nDeleteFailed;
807                     }
808                     break;
809                 case extractor_thread:
810                     {
811                         extract_thread& extractor = static_cast<extract_thread&>(thr);
812                         nExtractSuccess += extractor.m_nExtractSuccess;
813                         nExtractFailed += extractor.m_nExtractFailed;
814                     }
815                     break;
816                 case find_thread:
817                     {
818                         observer_thread& observer = static_cast<observer_thread&>( thr );
819                         nFindEvenSuccess = observer.m_nFindEvenSuccess;
820                         nFindEvenFailed = observer.m_nFindEvenFailed;
821                         nFindOddSuccess = observer.m_nFindOddSuccess;
822                         nFindOddFailed = observer.m_nFindOddFailed;
823                     }
824                     break;
825                 default:
826                     assert( false );
827                 }
828             }
829
830             size_t const nInitialOddKeys = ( s_nSetSize * s_nInsThreadCount ) * 3 / 4;
831
832             EXPECT_EQ( nInsertInitFailed, 0u );
833             EXPECT_EQ( nInsertInitSuccess, s_nSetSize * s_nInsThreadCount );
834             EXPECT_EQ( nFindEvenFailed, 0u );
835             EXPECT_GE( nInsertSuccess + nInitialOddKeys, nDeleteSuccess + nExtractSuccess );
836             EXPECT_LE( nInsertSuccess, nDeleteSuccess + nExtractSuccess );
837
838             propout()
839                 << std::make_pair( "insert_init_success", nInsertInitSuccess )
840                 << std::make_pair( "insert_init_failed", nInsertInitFailed )
841                 << std::make_pair( "insert_success", nInsertSuccess )
842                 << std::make_pair( "insert_failed", nInsertFailed )
843                 << std::make_pair( "delete_success", nDeleteSuccess )
844                 << std::make_pair( "delete_failed", nDeleteFailed )
845                 << std::make_pair( "extract_success", nExtractSuccess )
846                 << std::make_pair( "extract_failed", nExtractFailed )
847                 << std::make_pair( "find_even_success", nFindEvenSuccess )
848                 << std::make_pair( "find_even_failed", nFindEvenFailed )
849                 << std::make_pair( "find_odd_success", nFindOddSuccess )
850                 << std::make_pair( "find_odd_failed", nFindOddFailed );
851         }
852
853         template <typename Set>
854         void analyze( Set& testSet )
855         {
856             // All even keys must be in the set
857             {
858                 for ( size_t n = 0; n < s_nSetSize; n +=4 ) {
859                     for ( size_t i = 0; i < s_nInsThreadCount; ++i ) {
860                         EXPECT_TRUE( testSet.contains( key_type( n, i ))) << "key=" << n << "/" << i;
861                     }
862                 }
863             }
864
865             check_before_clear( testSet );
866
867             testSet.clear();
868             EXPECT_TRUE( testSet.empty()) << "set.size=" << testSet.size();
869
870             additional_check( testSet );
871             print_stat( propout(), testSet );
872             additional_cleanup( testSet );
873         }
874
875         template <class Set>
876         void run_test()
877         {
878             static_assert( !Set::c_bExtractSupported, "Set class must not support extract() method" );
879
880             Set  testSet( *this );
881             do_test_with( testSet );
882             DEBUG(analyze( testSet ));
883         }
884
885         template <class Set>
886         void run_test_extract()
887         {
888             static_assert( Set::c_bExtractSupported, "Set class must support extract() method" );
889
890             Set  testSet( *this );
891             do_test_extract_with( testSet );
892             DEBUG(analyze( testSet ));
893         }
894
895         template <class Map>
896         void run_feldman();
897     };
898
899     class Set_Del3_LF: public Set_Del3
900         , public ::testing::WithParamInterface<size_t>
901     {
902     public:
903         template <class Set>
904         void run_test()
905         {
906             s_nLoadFactor = GetParam();
907             propout() << std::make_pair( "load_factor", s_nLoadFactor );
908             Set_Del3::run_test<Set>();
909         }
910
911         template <class Set>
912         void run_test_extract()
913         {
914             s_nLoadFactor = GetParam();
915             propout() << std::make_pair( "load_factor", s_nLoadFactor );
916             Set_Del3::run_test_extract<Set>();
917         }
918
919         static std::vector<size_t> get_load_factors();
920     };
921
922 } // namespace set